Image analysis – Image compression or coding – Pyramid – hierarchy – or tree structure
Reexamination Certificate
1999-03-25
2002-10-15
Boudreau, Leo (Department: 2621)
Image analysis
Image compression or coding
Pyramid, hierarchy, or tree structure
C232S009000, C375S240190
Reexamination Certificate
active
06466698
ABSTRACT:
BACKGROUND OF THE INVENTION
1. Field of the Invention
The present invention relates generally to a system for the compression and decompression of digitized imagery which is useful both for transmission through narrow bandwidth communications channels and efficient archival storage in a data retrieval system. More specifically, to minimize computational complexity and memory usage, the system described herein uses lifting to implement its wavelet transforms and performs embedded coefficient coding in-place, i.e., without reorganizing the data into traditional subbands. By processing the data in-place, data movement is minimized in both the encoder and decoder and scratch memory requirements are greatly reduced.
2. Brief Description of the Related Art
Digital data compression systems are useful to reduce the number of bits required to represent a signal in digital form. Digital data is typically compressed to either facilitate transmission of the signal through a limited-bandwidth communications channel or to reduce the amount of memory needed to store that signal on some archival media such as a computer hard disk. Digital data compression can be achieved using either lossless or lossy coding techniques. Lossless coding involves only the extraction of statistical redundancy from the signal, and, thus, the amount of compression possible is signal dependent with compression ratios of 2:1 common for natural images.
To get higher levels of compression or to code the signal at a fixed bit rate, some distortion must be accepted in the reconstructed signal, resulting in a loss of information when the signal is passed through the complete encoding and decoding system. The goal of a good lossy coding system, then, is to minimize the distortion introduced into the signal at all of the bit rates for which the system is designed to operate, e.g., attaining the best rate-distortion performance possible.
A variety of image compression algorithms and systems have been proposed in recent years. Many of the algorithms with the best rate-distortion performance such as the Joint Photographics Experts Group (JPEG), described in “Overview of the JPEG (ISO/CCITT) Still Image Compression” by G. K. Wallace in SPIE, Vol. 1244,
Image Proc. Algorithms and Techniques,
1990, pp. 220-233, and Zerotree Coders, described in “Embedded Image Coding Using Zerotrees of Wavelet Coefficients” by J. M. Shapiro in
IEEE Trans. On Signal Processing,
Vol. 41, No. 12, December 1993, pp. 3445-3462, the disclosures of which are herein incorporated by reference, use transforms to decorrelate image pixels before coding of the data. The JPEG standard relies on a block-based discrete cosine transform (DCT). A coding algorithm based on the wavelet-packet transform showing improved rate-distortion performance for difficult images is described in “Wavelet Packet-Based Image Coding Using Joint Space-Frequency Quantization” by Z. Xiong, K. Ramchandran and M. T. Orchard in
Proc. Int. Conf On Image Proc.,
November 1994, Austin, Tex., pp. 324-328, the disclosure of which is herein incorporated by reference.
The zerotree coder uses a multiresolutional wavelet transform and takes advantage of the correlation between insignificant coefficients at different scales. U.S. Pat. No. 5,315,670, to James M. Shapiro, entitled “Digital Data Compression System Including Zerotree Coefficient Coding” discloses a digital data processing system which includes means for generating a tree structure of data representative coefficients with the tree structure having multiple paths from coefficients generated at a level of coarsest information to coefficients generated at a level of relatively finer information. The coefficients are evaluated to distinguish between significant and insignificant coefficients. Means are also included for generating a dedicated symbol representing a related association of insignificant coefficients within the tree structure, from a root coefficient of the tree structure to a set of end coefficients of the tree structure. The symbol represents that neither the root coefficient of the tree structure nor any descendant of the root coefficient has a magnitude greater than a given reference level. A coefficient is considered to be insignificant and a “root of a zerotree”, whereby all descendants are predictably insignificant, if (a) the coefficient has an insignificant magnitude, (b) the coefficient is not the descendant of a root from a coarser level, and (c) all the descendants of the coefficient at finer levels have insignificant magnitudes. A coefficient found to be a zerotree root is coded with a dedicated symbol which is eventually processed by an entropy coder.
Other embedded compression algorithms that rely on inter-subband redundancy extraction are detailed in articles entitled “CREW: Compression with Reversible Embedded Wavelets,” by A. Zandi, J. D. Allen, E. L. Schwartz, and M. Boliek,
Proc. Data Compression Conference,
1995, pp. 212-221; and “An Image Multiresolution Representation for Lossless and Lossy Compression,” by A. Said and W. A. Pearlman,
IEEE Trans. on Image Proc.,
Vol. 5, No. 9, September 1996, pp. 1303-1310 (detailing SPIHT—Set Partitioning in Hierarchical Trees); and “Multirate 3-D Subband Coding of Video,” by D. Taubman and A. Zakhor,
IEEE Trans. on Image Proc.,
Vol.3, No. 5, September 1994, pp. 572-588 (detailing LZC—Layered zero coding), the disclosures of which are herein incorporated by reference.
Fundamental to all of these compression algorithms is the wavelet transform. An infinite number of different wavelets exist, but as detailed in an article entitled “Low Bit-Rate Design Considerations for Wavelet-Based Image Coding,” by M. Lightstone and E. Majani,
Multidimensional Systems and Signal Proc.,
8, pp. 111-128 (1997), the disclosure of which is herein incorporated by reference, short, biorthogonal wavelets tend to provide the best results for image and video compression. Such wavelets are typically constructed using multirate digital filter banks. A wavelet coefficient mapping is created by iteratively decomposing the low-low band (low vertical frequency, low horizontal frequency), where the wavelet coefficients are organized in distinct dyadic subbands ranging from low frequency in the upper left-hand corner to high in the lower right. In the absence of coefficient quantization, i.e., with lossless compression, the original image can be reconstructed by iteratively applying the inverse wavelet transform.
In view of the foregoing, there is a need for a compression system that provides a more efficient and flexible way of correlating between insignificant coefficients at different scales incorporated into a zerotree coder.
SUMMARY OF THE INVENTION
It is an object of the present invention to provide a system that relies on lifted wavelets to perform analysis and synthesis, and processes the coefficients that result from such transforms in-place, using algebraically-calculated parent-child zerotree relationships rather than the memory-consuming linked lists previously known.
It is further an object of the present invention to apply the efficient zerotree indexing scheme to other embedded compression algorithms.
These and other objects are accomplished by the present invention that includes a system for compressing digital data comprising an image, the image collected for electronic manipulation, means for converting the image using lifted wavelet transforms, and, means for applying the converted image.
The present invention further includes a method for converting an image, comprising the steps of acquiring an image, storing the acquired image as a data array in a memory system, progressively replacing pixel elements of the stored data array with transform coefficient elements through the lifted transformation, scanning the transform coefficients to create an embedded symbol stream, and, losslessly encoding the embedded symbol stream to create an embedded bit stream.
Additionally, the present invention includes a digital data compression and decompression system comprising the steps
Bokar Gregory M.
Boudreau Leo
Serventi Anthony J.
Sherali Ishrat
The United States of America as represented by the Secretary of
LandOfFree
Efficient embedded image and video compression system using... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Efficient embedded image and video compression system using..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Efficient embedded image and video compression system using... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2999532