Image analysis – Image compression or coding – Pyramid – hierarchy – or tree structure
Reexamination Certificate
2000-10-23
2004-08-03
Do, Anh Hong (Department: 2624)
Image analysis
Image compression or coding
Pyramid, hierarchy, or tree structure
C382S232000, C382S248000
Reexamination Certificate
active
06771829
ABSTRACT:
FIELD OF THE INVENTION
This invention relates to the processing of images such as photographs, drawings, and other two dimensional displays. It further relates to the processing of such images after they have been captured in digital format or after they have been converted to or otherwise expressed in digital format. This invention further relates to use of novel coding methods to increase the speed and compression ratio for digital image storage and transmission.
BACKGROUND OF THE INVENTION
Recently subband coding has emerged as the leading standardization candidate in future image compression systems due to the development of the discrete wavelet transform (DWT). The multiresolution characteristics of the wavelet transform establish an intuitive foundation on which simple yet sophisticated methods of encoding the transform coefficients are developed. Exploiting the relationship between the parent and the offspring coefficients in wavelet tree, zerotree-based wavelet coders, for example, J. M. Shapiro, “Embedded image coding using zerotrees of wavelet coefficients,”
IEEE Trans. on SP,
vol. 41, pp. 3445-3462, December 1993 [hereinafter EZW]; A. Said and W. A. Pearlman, “A new fast and efficient image codec on set partitioning in hierarchical trees,”
IEEE Trans on Circuits Syst. Video Tech.,
vol. 6, pp. 243-550, June 1996 [hereinafter SPIHT]; and “Compression with reversible embedded wavelets,” RICOH Company Ltd. submission to ISO/IEC JTC1/SC29/WG1 for the JTC1.29.12 work item, 1995. http://www.crc.ricoh.com/CREW [hereinafter CREW] can effectively order the coefficients by bit planes and transmit more significant bits first. This elegant coding scheme results in an embedded bit stream (i.e., it can be truncated at any point by the decoder to yield the best corresponding reconstructed image) and many other interesting features such as exact bit rate control and idempotency capability. It became apparent that the same idea can be applied to block transform coefficients as well if these are grouped in a wavelet-like octave-band fashion, e.g., Z. Xiong, O. Guleryuz, and M. T. Orchard, “A DCT-based embedded image coder,”
IEEE SP Letters,
vol. 3, pp. 289-590, November 1996; H. Malvar, “Lapped biorthogonal transforms for transform coding with reduced blocking and ringing artifacts,”
ICASSP
97, Munich, April 1997;] T. Klausutis and V. Madisetti, “Adaptive lapped transform-based image coding,”
IEEE SP Letters,
vol. 4, pp. 245-547, September 1997; T. D. Tran and T. Q. Nguyen, “A lapped transform embedded image coder,”
ISCAS,
Monterey, May 1998, as illustrated in FIG.
1
. Global information is fully taken into account in these subband coders, leading to excellent performance.
However, perfect embeddedness is achieved at a high computational cost. Such embeddedness requires a full buffering of all the transform coefficients. First of all, this requirement becomes burdensome when the input images have high resolution (in desktop publishing applications for example) and/or the decoder has limited resources. Second, a full buffering with multiple passes is very costly in hardware implementation. Finally, full buffering prevents the application of powerful parallel processing techniques.
It is therefore an object of the current invention to sacrifice progressive transmission capability for a faster coder with a lower implementation complexity and a comparable quality performance. It is a further object of the current invention to construct such a coder by partitioning the transform coefficients into small local groups and encoding them independently using popular zerotree-based algorithms. It is yet a further object of this invention to provide a coder with negligible performance penalty. It is another object of this invention to provide a coder with performance almost identical to the fully embedded version when the partition size is reasonably large. It is another object of this invention to maintain embeddedness within the local groups while losing global embeddedness in the final output bitstream.
SUMMARY OF THE INVENTION
The LZT coding algorithm of this invention has at least the following fundamental steps:
1) Partitioning the input image into many local blocks. (The size of the partition is chosen based on a tradeoff between the desired level of resolution and the availability of computing resources, which determine an allowable level of implementation complexity.)
2) Transforming each partition, that is, each local block, independently using a block coder. (Some special attention is required at the partition boundaries to ensure continuity in the reconstructed image.)
3) Quantizing the coefficients in each partition by the appropriate JND thresholds or by truncating a certain number of least significant bit planes.
4) Arranging the quantized coefficients in wavelet-like quad-tree fashion as shown in FIG.
2
and encode each group separately using any zerotree coding algorithm.
5) Concatenating the bitstreams to yield the final output.
Most generally, this invention comprises the steps of partitioning the image into a plurality of local blocks, performing a block coding transform on each local block of the plurality of local blocks so as to produce a corresponding plurality of sets of local block transform coefficients using a block coding algorithm, quantizing the local block transform coefficients in each set of local block transform coefficients of the plurality of local block transform coefficients, arranging the plurality of sets of quantized local block transform coefficients in a wavelet-like quad-tree structure, and concatenating the bit-streams of the encoded quantized coefficients from each of the plurality of local blocks.
REFERENCES:
patent: 5315670 (1994-05-01), Shapiro
patent: 5748786 (1998-05-01), Zandi et al.
patent: 5764805 (1998-06-01), Martucci et al.
patent: 6069977 (2000-05-01), Kim et al.
patent: 6101279 (2000-08-01), Nguyen et al.
patent: 6243496 (2001-06-01), Wilkinson
patent: 6269192 (2001-07-01), Sodagar et al.
patent: 6381280 (2002-04-01), Lynch et al.
Shapiro, “Embedded Image Coding Using Zerotrees of Wavelet Coefficients”, IEEE Transactions on Signal Processing, vol. 41, No. 12, Dec. 1993, pps. 3445-3462.*
Sweldens, “The Lifting Scheme: A Custom-Design Construction of Biorthogonal Wavelets”, Appl. Comput. Harmon. Anal, vol. 3, No. 2, Nov. 1994, pps. 1-29.*
Shapiro, “A Fast Technique for Identifying Zerotrees in the EZW Algorithm”, IEEE International Conference on Acoustic, Speech, and Signal Processing, vol. 3, 1996, pps. 1455-1458.*
Shapiro, “An Embedded Hierarchical Image Coder Using Zerotrees of Wavelet Coefficients”, IEEE Data Compression Conference, 1993, pps. 214-223.*
Antonini et al., “Image Coding Using Wavelet Transform”, IEEE Transaction on Image Processing, vol. 1, No. 2, Apr. 1992, pps. 205-220.*
Tran, “The LiftLT: Fast Lapped Transform Via Lifting Steps”, ICASSP, Mar. 1999, pps. 1-7.
Topiwala Pankaj N.
Tran Trac D.
Burns & Levinson LLP
Do Anh Hong
Fastvdo LLC
Lan Yan
Williams Frederick C.
LandOfFree
Method for local zerotree image coding does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Method for local zerotree image coding, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Method for local zerotree image coding will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3279680