Image analysis – Image compression or coding – Pyramid – hierarchy – or tree structure
Reexamination Certificate
1996-10-24
2002-11-19
Chen, Wenpeng (Department: 2624)
Image analysis
Image compression or coding
Pyramid, hierarchy, or tree structure
C375S240190
Reexamination Certificate
active
06483946
ABSTRACT:
BACKGROUND OF THE DISCLOSURE
Data compression systems are useful for representing information as accurately as possible with a minimum number of bits and thus minimizing the amount of data which must be stored or transmitted in an information storage or transmission system. One of the primary means of compression used in the art removes redundant information from the original data without significantly impacting the quality of the decompressed data when compared to the original data.
One such compression technique appears in the Proceedings of the International Conference on Acoustics, Speech and Signal Processing, San Francisco, Calif. March 1992, volume IV, pages 657-660, where there is disclosed a signal compression system which applies a hierarchical subband decomposition, or wavelet transform, followed by the hierarchical successive approximation entropy-coded quantizer incorporating zerotrees. The representation of signal data using a multiresolution hierarchical subband representation was disclosed by Burt et al. in IEEE Trans. on Commun., Vol Com-31, No. 4, April 1983, page 533. A wavelet pyramid, also known as critically sampled quadrature-mirror filter (QMF) subband representation, is a specific type of multiresolution hierarchical subband representation of an image. A wavelet pyramid was disclosed by Pentland et al. in Proc. Data Compression Conference Apr. 8-11, 1991, Snowbird, Utah. A QMF subband pyramid has been described in “Subband Image Coding”, J. W. Woods ed., Kluwer Academic Publishers, 1991 and I. Daubechies,
Ten Lectures on Wavelets,
Society for Industrial and Applied Mathematics (SIAM): Philadelphia, Pa., 1992.
Wavelet transforms, otherwise known as hierarchical subband decomposition, have recently been used for low bit rate image compression because such decomposition leads to a hierarchical multi-scale representation of the source image. Wavelet transforms are applied to an important aspect of low bit rate image coding: the coding of a binary map (a wavelet tree) indicating the locations of the non-zero values, otherwise known as the significance map of the transform coefficients. Using scalar quantization followed by entropy coding, in order to achieve very low bit rates, i.e., less than 1 bit/pel, the probability of the most likely symbol after quantization—the zero symbol—must be extremely high. Typically, a large fraction of the bit budget must be spent on encoding the significance map. It follows that a significant improvement in encoding the significance map translates into a significant improvement in the compression of information preparatory to storage or transmission.
To accomplish this task, a new structure called a zerotree has been developed. A wavelet coefficient is said to be insignificant with respect to a given threshold T, if the coefficient has a magnitude less than or equal to T. The zerotree is based on the hypothesis that if a wavelet coefficient at a coarse scale is insignificant with respect to a given threshold T, then all wavelet coefficients of the same orientation in the same spatial location at finer scales are likely to be insignificant with respect to T. Empirical evidence suggests that this hypothesis is often true.
More specifically, in a hierarchical subband system, with the exception of the highest frequency subbands, every coefficient at a given scale can be related to a set of coefficients at the next finer scale of similar orientation according to a structure called a wavelet tree. The coefficients at the coarsest scale will be called the parent nodes, and all coefficients corresponding to the same spatial or temporal location at the next finer scale of similar orientation will be called child nodes. For a given parent node, the set of all coefficients at all finer scales of similar orientation corresponding to the same location are called descendants. Similarly, for a given child node, the set of coefficients at all coarser scales of similar orientation corresponding to the same location are called ancestors. With the exception of the lowest frequency subband, all parent nodes have four child nodes. For the lowest frequency subband, the parent-child relationship is defined such that each parent node has three child nodes.
Nodes are scanned in the order of the scales of the decomposition, from coarsest level to finest. This means that no child node is scanned until after its parent and all other parents in all subbands at the same scale as that parent have been scanned. This is a type of modified breadth-first, subband by subband, traversal performed across all the wavelet trees defined by the coefficients of the wavelet transform of the two-dimensional data set.
Given a threshold level to determine whether or not a coefficient is significant, a node is said to be a ZEROTREE ROOT if 1) the coefficient at a node has an insignificant magnitude, 2) the node is not the descendant of a root, i.e., it is not completely predictable from a coarser scale, and 3) all of its descendants are insignificant. A ZEROTREE ROOT is encoded with a special symbol indicating that the insignificance of the coefficients at finer scales is completely predictable. To efficiently encode the binary significance map, four symbols are entropy coded: ZEROTREE ROOT, ISOLATED ZERO, and two non-zero symbols, POSITIVE SIGNIFICANT and NEGATIVE SIGNIFICANT.
U.S. Pat. No. 5,412,741 issued May 2, 1995 and herein incorporated by reference discloses an apparatus and method for encoding information with a high degree of compression. The apparatus uses zerotree coding of wavelet coefficients in a much more efficient manner than any previous techniques. The key to this apparatus is the dynamic generation of the list of coefficient indices to be scanned, whereby the dynamically generated list only contains coefficient indices for which a symbol must be encoded. This is a dramatic improvement over the prior art in which a static list of coefficient indices is used and each coefficient must be individually checked to see whether a) a symbol must be encoded, or b) it is completely predictable.
The apparatus disclosed in the '741 patent uses a method for encoding information comprising the steps of forming a wavelet transform of the image, forming a zerotree map of the wavelet coefficients, encoding the significant coefficients on an initial dominant list from the coarsest level of the transform and the children of those coefficients whose indices are appended to the dominant list as the coefficient of the parent is found to be significant, reducing the threshold, refining the estimate of the value of the significant coefficients to increase the accuracy of the coded coefficients, and cycling back to scan the dominant list anew at the new, reduced threshold.
To accomplish the iterative process, the method of the '741 patent is accomplished by scanning the wavelet tree subband by subband, i.e., all parent nodes are coded, then all children, then all grandchildren and so on and they are encoded bit-plane by bit-plane. As the process iterates through the wavelet tree representation of the image, this apparatus codes one of four symbols within the zerotree map. Any improvement in the speed at which a wavelet tree is processed would be advantageous.
Therefore, there is a need in the art for an improved method of classifying and coding the nodes of a wavelet tree that leads to more efficient coding and rapid processing.
SUMMARY OF THE INVENTION
The present invention is apparatus and a concomitant method of encoding zerotrees in a wavelet-based coding technique. Specifically, the invention uses a depth-first pattern for traversing the zerotree, i.e., each branch of the tree, from parent to child to grandchild and so on, is fully traversed before a next branch is traversed. The depth-first tree traversal pattern is used to quantize the coefficients of the tree as well as to assign symbols to the quantized coefficients. Additionally, the invention assigns one of three symbols to each node: ZEROTREE ROOT, VALUED ZEROTREE ROOT, and VALUE. By using three symbols
Martucci Stephen A.
Sodagar Iraj
Zhang Ya-Qin
Burke William J.
Chen Wenpeng
Sarnoff Corporation
LandOfFree
Apparatus and method for encoding zerotrees generated by a... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Apparatus and method for encoding zerotrees generated by a..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Apparatus and method for encoding zerotrees generated by a... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2979464