Image analysis – Image compression or coding – Pyramid – hierarchy – or tree structure
Reexamination Certificate
1998-06-30
2001-07-31
Johnson, Timothy M. (Department: 2623)
Image analysis
Image compression or coding
Pyramid, hierarchy, or tree structure
C341S079000, C375S240190, C382S247000
Reexamination Certificate
active
06269192
ABSTRACT:
The invention relates to image and video processing systems and, more particularly, to image and video processing systems for coding wavelet trees, which generates bitstreams with flexible degrees of spatial, quality and complexity scalabilities.
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. 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, e.g., 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 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.
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.
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 methods as discussed in the '741 patent are known as the “Embedded Zerotree Wavelet” (EZW) method.
Alternatively, the coding of wavelet trees (e.g., zerotree) can be performed depth-first across all the wavelet trees defined by the coefficients of the wavelet transform of the two-dimensional data set. This method of wavelet coding is known as Zerotree Entropy (ZTE) encoding, which is described in an U.S. patent application filed on Dec. 31, 1997 with the title “Apparatus And Method For Encoding Wavelet Trees Generated By A Wavelet-Based Coding Method” (attorney docket SAR 12234; Ser. No. 09/002,251), hereby incorporated by reference.
Although it has been found that ZTE is an effective wavelet coding method, various applications can benefit from a flexible wavelet coding method that can provide multi-scale wavelet coding, i.e., providing scalability in spatial resolution and quality.
Therefore, there is a need in the art for coding wavelet trees, which generates bitstreams with flexible degrees of spatial, quality and complexity scalabilities.
SUMMARY OF THE INVENTION
The present invention is an apparatus and a concomitant method of encoding wavelet trees to generate bitstreams with flexible degrees of spatial, quality and complexity scalabilities. The ZTE method is extended to achieve a fully scalable coding method by implementing a multiscale zerotree coding scheme.
More specifically, the wavelet coefficients of the first spatial resolution (and/or quality (signal-to-noise (SNR))) layer are first quantized with a first quantizer Q
0
. These quantized coefficients are scanned using the zerotree concept and then the significant maps and quantized coefficients are entropy coded. The output of the entropy coder at this level, BS
0
, comprises the first portion of the bitstream.
Next, the quantized wavelet coefficients of the first layer are also reconstructed and subtracted from the original wavelet coefficients. These “residual” wavelet coefficients are fed into the next stage of the coder in which the wavelet coefficients are quantized with a second (next) quantizer, Q
1
, which is then followed by zerotree scanned and entropy coded. The output of this stage, BS
1
, comprises the second portion of the output bitstream.
The quantized coefficients of the second stage are again reconstructed and subtracted from the original coefficients. This process is continued for N stages to provide N layers of scalability. Each stage represents one layer of SNR or spatial (or both) scalability. Spatial scalability is provided by applying the above N-stage coder to different spatial resolutions of the input image. Thus, a wide range of scalability levels or layers are efficiently generated and inserted into the resulting bitstreams, where they are extracted, e.g., by a decoder as needed for a particular application.
REFERENCES:
patent: 5315670 (1994-05-01), Shapiro
patent: 5636033 (1997-06-01), Maeda
patent: 5896176 (1999-04-01), Das et al.
patent: 5982938 (1999-11-01), Dube
patent: 6026198 (2000-02-01), Okada
Ang et al., Robst Image Compression using the Depth-First Search on the Wavelet Zerotree, Aug. 1999,p. 797-800, IEEE.*
International Search Report for corresponding application PCT/US98/14160.
Jerome M. Shapiro, An Embedded Hierarchical Image Coder Using Zerotrees of Wavelet Coefficients, The David Sarnoff Research Center, 1993, pp. 214-223.
Chai Bing-Bing
Hatrack Paul
Lee Hung-Ju
Sodagar Iraj
Burke William J.
Johnson Timothy M.
Sarnoff Corporation
LandOfFree
Apparatus and method for multiscale zerotree entropy encoding 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 multiscale zerotree entropy encoding, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Apparatus and method for multiscale zerotree entropy encoding will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2465199