Lucent Technologies Inc.

Paul David Davis

Richard Robert Shively

Egbert Ammicht

An improved method is disclosed for the encoding phase for Wavelet-based compression of digital data representing an object or image. Subband decomposition transforms the data into hierarchical tree data. Two terms are precomputed: the highest bit-plane in which any descendant of a node v has a non-zero bit (B(v) and the highest bit-plane in which any indirect descendant (grandchild and beyond) becomes significant (B(v). Node traversal is initiated but its extent is limited by a fixed bit-budget. The number of bits emitted by a node as a function of the bit-plane are counted through to the last bit-plane which exhausts the bit-budget. The user can predetermine the coefficient, bit-plane and specific bit at which the algorithm will halt. The tree structure is read only once, thus greatly accelereating the encoding and reducing the memory reference rate by a factor of 2 or more. Accumulators for each of the stacked bit-planes are provided which are incremented as each said Wavelet coefficient is produced, by the number of bits that the coefficient adds to the relevant bit-plane.

Coefficient computation in image compression using set partitioning in hierarchical trees

A multi-stage wavelet transform of an image signal is implementing using a first processing element to perform computations for a first stage of the transform, and a second processing element operating in a time-multiplexed manner to perform computations for subsequent stages of the transform. The first processing element includes first and second adder trees for implementing horizontal and vertical filtering operations, respectively, and a set of row buffers configured such that the total number of row buffers is only one more than the number of pixels required to generate a given vertically-filtered output. In a four-stage illustrative embodiment in which the first processing element processes image pixel data at a sample rate of f , the multi-stage processing element receives inputs from the first stage processing element at a sample rate of f /4, and generates coefficients for the second, third and fourth stages using sample rates of f /16, f /64 and f /256, respectively. The particular number of stages may be considered a design parameter, and other embodiments may have more or less than four stages. In accordance with the invention, operations performed by the first stage processing element correspond to lowest-level nodes of a binary tree representation of a processing schedule for the multi-stage wavelet transform, and the operations performed by the multi-stage processing element correspond to the remaining nodes of the binary tree representation.

Methods and apparatus for wavelet-based image compression

Data compression achieved by set partitioning of hierarchical trees is made more efficient by a family of related traversal schemes which act upon the tree structure and the significance values derived from the tree structure. The tree structure may be traversed in any of a number of sequences. In accordance with significance tests applied to the node data, bits are produced or not. The order in which the bits are produced may be freely chosen. Trees are traversed and bits are emitted which describe the relative magnitude of coefficients in the sub-trees of the current tree-node. The manner of traversal can either be known to the remote decoder or can be derived from the incoming data stream. The encoding scheme typically specifies all bits emitted by a given node v as a function of the traversal of its parents, the bit-plane b, the coefficient value c of v, the significances B (v) and B (v), and whether the parent node p still emits B (p).

Growing community of inventors

Mount Tabor, NJ, United States of America

Paul David Davis