Image analysis – Image compression or coding
Reexamination Certificate
1998-09-25
2001-07-17
Couso, Jose L. (Department: 2724)
Image analysis
Image compression or coding
C382S236000, C382S240000, C382S248000
Reexamination Certificate
active
06263109
ABSTRACT:
BACKGROUND OF THE INVENTION
The invention relates to data compression. More specifically, the invention relates to the generation of embedded bitstreams.
Data compression is often used for reducing the cost of storing large data files on computers as well as reducing the time for transmitting large data files between computers. In the so-called “transform methods” data is transformed into coefficients that represent the data in a frequency domain. Coefficients may be quantized (lossy compression) without significantly affecting the quality of data that is reconstructed from the quantized coefficients. Redundancy in the coefficients may then be reduced or eliminated (lossless compression) without affecting quality of the reconstructed data.
One well known class of transforms are Wavelet transforms. The Wavelet transforms may be used to perform subband decomposition and produce coefficients that describe the data in a hierarchical multiscale representation. Wavelet transforms have proven useful for the compression of images and the analysis of signals. They have been proposed as the transform for the emerging JPEG-2000 standard.
Among the advantages of the Wavelet transforms, the transform coefficients can be ordered in a hierarchical structure and transmitted in an “embedded bitstream.” The embedded bitstream has a property whereby prefixes of the bitstream yield a continuum of lower rate descriptions of the data at the highest possible levels of quality. If the embedded bitstream is truncated during transmission of image data, for instance, the information already transmitted will allow an entire image to be reconstructed. The quality of the reconstructed image is dependent upon the amount information transmitted. If an embedded bitstream is truncated, a complete image of reduced quality can be reconstructed from the transmitted bits. In contrast, truncation of a non-embedded transmission might only allow several rows of an image to be reconstructed.
As additional information is transmitted, the quality of the reconstructed image is improved. If the entire bitstream is transmitted without truncation, a lossless or near-lossless image can be reconstructed.
The transmission just described is often referred to as a progressive-by-quality image transmission. The coefficients are described by bit-planes, and the most significant coefficient bits (that is, the coefficient bits conveying the most important information) are transmitted first.
Another type of transmission is often referred to as a progressive-by-resolution transmission. The progressive-by-resolution transmission involves ordering the coefficients according to different levels of image resolution. The different levels are identified by markers in the embedded bitstream. A computer may use the markers to parse the bitstream and transmit the data for the coefficients corresponding to a resolution that is specified by the receiving computer. The receiving computer can reconstruct an image according to the specified resolution.
A number of coding algorithms have been proposed for ordering the description of transform coefficients such that the retained number of bits of the description can produce the best quality image. Algorithms have been proposed by Shapiro (the “Zerotree” algorithm) and Said-Pearlman (the “SPIHT” algorithm) among others.
There are a number of problems associated with Zerotree and SPIHT algorithms. Both the Zerotree and SPIHT algorithms are based on the construction of a data structure known as a Zerotree. The Zerotree data structure is complex and memory-intensive. The encoding of quantized coefficient bit-planes relies on the use of a complex arrangement of lists and pointers.
Moreover, the Zerotree and SPIHT algorithms minimize image distortion only at bit-plane boundaries. As long as the transmission is truncated at a bit-plane boundary, the image distortion will be minimized. However, if a transmission is truncated at a point other than a bit-plane boundary, the image distortion will not be minimized.
Very often, however, the bit rate of the transmission is not controllable such that the transmission is truncated at a bit-plane boundary. For example, bit rate control might depend upon buffer size in a client. The transmission will be truncated when the buffer is full. Thus, the bit rate will depend upon the size of the buffer in the client.
Truncation of a progressive quality transmission might also occur if a network goes down. Again, the truncation might not occur at a bit-plane boundary. Thus, the image distortion might not be minimized given the amount of information that was transmitted.
Additionally, the Zerotree coders do not provide a clean separation between modeling, ordering, coding and algorithmic components. Consequently, it is difficult to tailor the Zerotree coders to satisfy certain constraints on memory and complexity. Additionally, it is difficult for Zerotree coders to provide a single bitstream that can be parsed efficiently to address both progressive-by-quality and progressive-by-resolution transmissions. Zerotree coders do not directly yield resolution-scalable bitstreams that allow for efficient progressive-by-resolution transmissions. Modifying the coding for the progressive-by-resolution transmission results in a sacrifice in performance of the progressive-by-quality transmission.
There is a need for ordering the description of the transform coefficients in a relatively simple and fast manner and to reduce image distortion over a wider range of bit rates. Overall, there is a need for a coder that is less complex than a Zerotree coder. There is also a need for a coder that has a clean separation between modeling, ordering, coding and algorithmic components.
SUMMARY OF THE INVENTION
These needs are met by the present invention. An embedded bitstream is built from data (e.g., a subband decompostion of an image) separated into a plurality of subsequences (e.g., sub bit-planes). The subsequences are ordered according to decreasing expected distortion reduction per expected bit of description. At least some of the ordered subsequences are encoded, and the encoded subsequences are placed in the bitstream as ordered.
Other aspects and advantages of the present invention will become apparent from the following detailed description, taken in conjunction with the accompanying drawings, illustrating by way of example the principles of the invention.
REFERENCES:
patent: 5412741 (1995-05-01), Shapiro
patent: 5764374 (1998-06-01), Seroussi et al.
patent: 5764807 (1998-06-01), Pearlman et al.
patent: 5825929 (1998-10-01), Chen et al.
patent: 5867602 (1999-02-01), Zandi et al.
patent: 5909513 (1999-06-01), Liang et al.
patent: 5995668 (1999-11-01), Corset et al.
Ordentlich et al., “A Low Complexity Modeling Approach for Embeded Coding of Wavelet Coefficients” , Data Compression Conference, 1998. DCC '98. Proceedings, pp. 408-417.*
Seroussi et al., “On Adaptive Strategies for an Extended Family of Golomb type Codes” , Data Compression Conference, 1997. DCC'97 . Proceedings, pp. 131-140.*
Jin Li et al., “Sharp Rate-Distortion Optimized Embedded Wavelet Coding ---An Algorithm Proposal for JPEG 2000,”Oct. 10, 1997.
Ordentlich Erik
Seroussi Gadiel
Weinberger Marcelo
Couso Jose L.
Do Anh Hong
Hewlett--Packard Company
LandOfFree
Context-based ordering and coding of transform coefficient... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Context-based ordering and coding of transform coefficient..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Context-based ordering and coding of transform coefficient... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2454435