Image analysis – Image compression or coding – Pyramid – hierarchy – or tree structure
Reexamination Certificate
1998-12-09
2002-03-12
Couso, Jose L. (Department: 2724)
Image analysis
Image compression or coding
Pyramid, hierarchy, or tree structure
C382S226000, C341S079000
Reexamination Certificate
active
06356665
ABSTRACT:
BACKGROUND OF THE INVENTION
This invention relates to embedded coders and more particularly to an embedded image encoder with improved compression efficiency and decreased implementation complexity.
The ability to adjust the compression ratio by simply truncating an encoded bitstream makes embedded coding attractive for a number of applications such as progressive image transmission, internet browsing, scalable image and video databases, digital cameras, low delay image communications, etc. Taking Internet image browsing as an example, embedded coding makes it feasible to store only one copy of a high quality compressed bitstream on the server.
Depending on user demand, channel bandwidth conditions, and browser monitor quality, selectable amounts of the compressed bitstream are delivered to the browser. At an early stage of browsing, images can be retrieved with coarse quality so that a user can quickly go through a large number of images before choosing one of interest. The chosen image is then fully downloaded with a much better quality level. During the download process, the image quality is incrementally refined. The user can cancel the download process as soon as the quality is satisfactory.
Shapiro describes an Embedded Zerotree Wavelet algorithm (EZW) in his paper J. M. Shapiro, “Embedded Image Coding Using Zerotrees of Wavelet Coefficients,” IEEE Trans. on Signal Processing, Vol. 41, No. 12, pp. 3445-3462, December 1993. The embedded image coded bitstream can be terminated or truncated at any point. This allows the decoded image to always have a reasonable good quality with respect to the number of coded bits actually used. The zero tree symbol contains coefficients across multiple subbands. Therefore, in implementation, the coder has to traverse multiple subbands to establish the zero tree structure, the memory requirement of the codec is thus high. Furthermore, the cross subband zerotree symbol also makes it inefficient for spatial scalable image coding, i.e., to decode only an image of a coarser resolution.
New improvements over the EZW include the Set Partitioning in Hierarchical Trees (SPIHT) encoding algorithm described by Said and Pearlman. A. Said and W. Pearlman, “A New, Fast, and Efficient Image Codec Based on Set Partitioning in Hierarchical Trees,” IEEE Trans. on Circuits and Systems for Video Technology, Vol. 6, No. 3, pp. 243-250, June 1996. SPIHT maintains and manipulates 3 lists during coding: the list of insignificant sets (LIS), the list of insignificant pixels (LIP) and the list of significant pixels (LSP). With arithmetic entropy coding, SPIHT outperforms EZW. Furthermore, one mode of SPIHT achieves good compression efficiency without using any explicit Variable Length Code (VLC) such as a Huffman code or arithmetic code. However, at high bit-rates, the list built by SPIHT becomes very large and memory consuming. Therefore, it is expensive to implement.
Chui and Yi proposed a nested split coding algorithm. C. Chui, R. Yi, “System and method for nested split coding of sparse data sets”, U.S. Pat. No. 5,748,116. The nested coding encodes transform coefficients in data blocks. The algorithm is very fast and cheap to implement, but does not have the embedded functionality which is crucial in many applications.
A need remains for further improving the compression efficiency and reducing the implementation complexity of encoding techniques such as EWZ and SPIHT.
SUMMARY OF THE INVENTION
A quad-tree embedded image coding technique is used in combination with a bit-plane encoding technique to provide an efficient and low complexity embedded image coding system. A simple quad-tree method identifies transform coefficients as significant, insignificant, or refinement at each successive quantization level. The quad-tree technique is used instead of the zero-tree or hierarchical tree used in previous encoders. Since the quad-tree can be restricted within the subband, it may achieve spatial scalability in additional to the quality scalability. The coder does not maintain a list in coding, which also decrease the memory requirement for the coder.
The quad-tree embedded encoder takes as input a two-dimensional array of image coefficients, with each coefficient having values extending over multiple bit-planes. The coefficients are segmented into a certain number of root blocks. The segmentation can be just one root block covering the entire image, or it can be pre-split subbands where one subband is an initial root block, or it can be a number of pre-specified blocks covering the entire image. A block is said to be significant if and only if there is any “1” bit in the current bit-plane or in the more significant bit-plane of the block. The encoder proceeds bit-plane by bit-plane, from the most significant bit-plane to the least significant bit-plane. For each bit-plane, the encoder checks each root block for one of three cases.
In the first case the block was already significant at the previous bit-plane, the encoder then proceeds to each of its four sub-blocks (quadrants). In the second case the block just becomes significant at the current bit-plane, a “1” bit is encoded and the encoder proceeds to each quadrant of the block. In the third case the block remains insignificant, a “0” bit is encoded concluding coding of the block for the current bit-plane.
If the encoder proceeds to each quadrant, it repeats the same operations on each sub-block (quadrant). The quadrant significance information may be optionally entropy encoded by a Huffman or arithmetic coder, or may be simply directly sent into the bitstream.
Once a split quadrant reaches the size of a single coefficient, the bit of the current coefficient at the current bit-plane is encoded, and if the coefficient just becomes significant, its sign bit is encoded right after. The coding and splitting of quadrants is repeated for each progressively lesser significant bit-plane until reaching a predetermined number of encoded bits or image quality.
The foregoing and other objects, features and advantages of the invention will become more readily apparent from the following detailed description of a preferred embodiment of the invention which proceeds with reference to the accompanying drawings.
REFERENCES:
patent: 4261018 (1981-04-01), Knowlton
patent: 4816914 (1989-03-01), Ericsson
patent: 4849810 (1989-07-01), Ericsson
patent: 4868653 (1989-09-01), Golin et al.
patent: 5212742 (1993-05-01), Normile et al.
patent: 5218431 (1993-06-01), Gleicher et al.
patent: 5228098 (1993-07-01), Crinon et al.
patent: 5267334 (1993-11-01), Normille et al.
patent: 5412741 (1995-05-01), Shapiro
patent: 5444489 (1995-08-01), Truong et al.
patent: 5452104 (1995-09-01), Lee
patent: 5576767 (1996-11-01), Lee et al.
patent: 5592227 (1997-01-01), Feng
patent: 5724451 (1998-03-01), Shin et al.
patent: 5748116 (1998-05-01), Chui et al.
patent: 5982434 (1999-11-01), Tong et al.
patent: 5982938 (1999-11-01), Dube
patent: 0701375 (1996-03-01), None
patent: 0855838 (1998-07-01), None
patent: WO 98/52346 (1998-11-01), None
Peter Strobach, “Quadtree-Structured Recursive Plane Decomposition Coding of Images,”IEEE International Conference on Acoustics, Speech, and Signal Processing, Glasgow, Scotland, May 1989, pp. 1380-1397.
Gary J. Sullivan and Richard L. Baker, “Efficient Quadtree Coding of Images and Video,”IEEE Transactions on Image Processing, vol. 3, No. 3, May 1994, pp. 327-331.
Amir Said and William A. Pearlman, “A New, Fast, and Efficient Image Codec Based on Set Partitioning in Hierarchical Trees,”IEEE Transactions on Circuits and Systems for Video Technology, vol. 6, No. 3, Jun. 1996, pp. 243-250.
Jerome M. Shapiro, “Embedded Image Coding Using Zerotrees of Wavelet Coefficients,”IEEE Transactions on Signal Processing, vol. 41, No. 12, Dec. 1993, pp. 3445-3462.
Lei Shaw-Min
Li Jin
Couso Jose L.
Do Anh Hong
Marger Johnson & McCollom PC
Sharp Laboratories of America Inc.
LandOfFree
Quad-tree embedded image compression and decompression... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Quad-tree embedded image compression and decompression..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Quad-tree embedded image compression and decompression... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2844452