US 6,549,673 B1Granted

Wavelet-based compression of images for storage, transmission and reconstruction using hierarchical subband decomposition

AssigneeLucent Technologies Inc.

InventorsEgbert Ammicht, Paul David Davis, Richard Robert Shively

Life of this patent

Estimating the term…

Loading patent…

Abstract

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 B1(v) and B2(v), and whether the parent node p still emits B2(p).

Claims6

Dependent claims

In an imaging system using Wavelet-based image compression, a process for generating a compressed bit stream comprising the steps of:

a. performing a sub-band decomposition of data representing a source image into hierarchical tree data sets contained in bit-planes, each node of each tree in said tree data set containing a Wavelet coefficient and associated parameters;
b. traversing a predetermined sequence of trees and subtrees in said tree data set and examining a data-dependent sequence of tree and subtree nodes to detect defined parameters including the identity of the bit-plane, and the significant bit positions B1(v) and B2(v) associated with said Wavelet coefficients at said nodes;
c. for each said node, emitting at least one bit characterizing the Wavelet coefficient and its associated parameters as soon as said node is examined;
and
d. compiling said emitted bits in an output bit stream by
channeling into a first output queue produced bits if the current said node was already emitting value v bits in the previous plane and if B(v) is the current bit plane;
channeling into a second output queue produced bits if the current said node was already emitting value v bits in the previous plane but B(v) is not the current bit plane and the current said node was already emitting value v bits in the previous plane;
writing all other bits to a third output queue;
and
transmitting sequentially the contents of said first, second and third output queues.

7 more elements

In an imaging system using Wavelet-based image compression, a process for generating a compressed bit stream comprising the steps of:

a. performing a subband decomposition of an image to create wavelet coefficients represented by an ordered set of bits in a plurality of bit_plains;
b. said wavelet coefficients being arranged in a set of hierarchical trees of parent and child nodes, one per tree node, and a set of subtreeless nodes;
c. said decomposition being such that the input data dependency of any given parent node in said tree includes the input data dependency of the child nodes of said given parent node;
d. defining the set D1(v) of all descendants of any given node v in any one of said trees;
e. defining the set D2(v) of all grandchildren of said given node v and their descendants;
f. traversing all nodes in each tree from the lower-most said children nodes to the said parent node, and for each node traversed, precomputing the associated significance parameters B1(v)=B(D1(v)) and B2(v)=B(D2(v));
g. defining the significance parameter B(v) of the wavelet coefficient associated said nodes v to be the position of its most significant bit;
h. traversing treeless nodes and trees in a predetermined order based on a specification of the number of bit-planes to be treated at a time, and emitting bits 0 and 1 for each of the nodes visited, as determined by the wavelet coefficient and the B1(v) significance parameter alone or the B1(v) and B2(v) significance parameters together that are associated with each of said nodes;
i. determining the exact bits and exact bit order that each particular node emits;
and
j. assembling into a single stream said bits of values 1,0.

8 more elements

Dependencies are inferred from the claim text.