Image analysis – Image compression or coding
Reexamination Certificate
1996-08-09
2001-04-24
Couso, Jose L. (Department: 2621)
Image analysis
Image compression or coding
Reexamination Certificate
active
06222941
ABSTRACT:
FIELD OF THE INVENTION
The present invention relates to the field of data compression and decompression systems; particularly, the present invention relates to a method and apparatus for lossless and lossy encoding and decoding of data in compression/decompression systems.
BACKGROUND OF THE INVENTION
Data compression is an extremely useful tool for storing and transmitting large amounts of data. For example, the time required to transmit an image, such as a facsimile transmission of a document, is reduced drastically when compression is used to decrease the number of bits required to recreate the image.
Many different data compression techniques exist in the prior art. Compression techniques can be divided into two broad categories, lossy coding and lossless coding. Lossy coding involves coding that results in the loss of information, such that there is no guarantee of perfect reconstruction of the original data. The goal of lossy compression is that changes to the original data are done in such a way that they are not objectionable or detectable. In lossless compression, all the information is retained and the data is compressed in a manner which allows for perfect reconstruction.
In lossless compression, input symbols or intensity data are converted to output codewords. The input may include image, audio, one-dimensional (e.g., data changing spatially or temporally), two-dimensional (e.g., data changing in two spatial directions (or one spatial and one temporal dimension)), or multi-dimensional/multi-spectral data. If the compression is successful, the codewords are represented in fewer bits than the number of bits required for the uncoded input symbols (or intensity data). Lossless coding methods include dictionary methods of coding (e.g., Lempel-Ziv), run length encoding, enumerative coding and entropy coding. In lossless image compression, compression is based on predictions or contexts, plus coding. The JBIG standard for facsimile compression and DPCM (differential pulse code modulation—an option in the JPEG standard) for continuous-tone images are examples of lossless compression for images. In lossy compression, input symbols or intensity data are quantized prior to conversion to output codewords. Quantization is intended to preserve relevant characteristics of the data while eliminating unimportant characteristics. Prior to quantization, lossy compression system often use a transform to provide energy compaction. JPFG is an example of a lossy coding method for image data.
Recent developments in image signal processing continue to focus attention on a need for efficient and accurate forms of data compression coding. Various forms of transform or pyramidal signal processing have been proposed, including multiresolution pyramidal processing and wavelet pyramidal processing. These forms are also referred to as subband processing and hierarchical processing. Wavelet pyramidal processing of image data is a specific type of multi-resolution pyramidal processing that may use quadrature mirror filters (QMFs) to produce subband decomposition of an original image. Note that other types of non-QMF wavelets exist. For more information on wavelet processing, see Antonini, M., et al., “Image Coding Using Wavelet Transform”,
IEEE Transactions on Image Processing
Vol. 1, No. 2, Apr. 1992; Shapiro, J., “An Embedded Hierarchical Image Coder Using Zerotrees of Wavelet Coefficients”,
Proc. IEEE Data Compression Conference
pgs. 214-223, 1993.
One problem associated with much of prior art wavelet processing is that a large memory is required to store all of the data while it is being processed. In other words, in performing wavelet processing, all of the data must be examined before encoding is performed on the data. In such a case, there is no data output until at least one full pass has been made through all of the data. In fact, wavelet processing typically involves multiple passes through the data. Because of this, a large memory is often required. It is desirable to utilize wavelet processing, while avoiding the requirement of a large memory. Furthermore, it is desirable to perform wavelet processing using only a single pass through the data.
Many wavelet or subband transform implementations require filters in a particular canonical form. For example, low and high-pass filters must be the same length, the sum of the squares of the coefficients must be one, the high-pass filter must be the time and frequency reverse of the low-pass filter, etc. (See U.S. Pat. No. 5,014,134 issued May 1991 to Lawton et al.). It is desirable to allow a wider class of filters. That is, it is desirable to provide wavelet or subband transform implementations that use low and high-pass filters that are not the same length, the sum of the squares of the coefficients need not be one, the high-pass filter need not be the time and frequency reverse of the low-pass filter, etc.
The present invention provides lossy and lossless compression using a transform that provides good energy compaction. The present invention also provides for modeling of joint spatial/frequency domain data (wavelet transform domain) to permit efficient compression. Also provided is progressive transmission with rate or distortion being selectable by the user after encoding.
SUMMARY OF THE INVENTION
A method and apparatus for encoding and decoding data is described. The present invention includes a method and apparatus for generating transformed signals in response to input data. In one embodiment, the transformed signals are generated using a reversible wavelet transform. The present invention also includes a method and apparatus for compressing the transformed signals into data representing a losslessly compressed version of the input data. In one embodiment, the present invention decomposes the input data using a non-minimal length reversible filter. The decomposition may be performed using multiple one-dimension filters.
The present invention also includes a method and apparatus to perform embedded coding of the transformed signals. The embedded coding of the present invention includes ordering the series of coefficients and performing bit significance embedding on the transformed signals.
The present invention also includes a method and apparatus for decompressing the losslessly compressed version of the input data into transformed signals. The present invention also provides for lossy compression of input signals by truncation of losslessly compressed data. The present invention also includes a method and apparatus for generating the input data from the transformed signals into a reconstructed version of the input data using an inverse reversible wavelet transform.
REFERENCES:
patent: 3580655 (1971-05-01), Leith et al.
patent: 3950103 (1976-04-01), Schmidt-Weinmar
patent: 4136954 (1979-01-01), Jamieson
patent: 4155097 (1979-05-01), Lux
patent: 4190861 (1980-02-01), Lux
patent: 4223354 (1980-09-01), Noble et al.
patent: 4393456 (1983-07-01), Marshall, Jr.
patent: 4569075 (1986-02-01), Nussbaumer
patent: 4599567 (1986-07-01), Goupillaud et al.
patent: 4652881 (1987-03-01), Lewis
patent: 4663660 (1987-05-01), Fedele et al.
patent: 4674125 (1987-06-01), Carlson et al.
patent: 4701006 (1987-10-01), Perlmutter
patent: 4751742 (1988-06-01), Meeker
patent: 4760563 (1988-07-01), Beylkin
patent: 4785348 (1988-11-01), Fonsalas et al.
patent: 4785349 (1988-11-01), Keith et al.
patent: 4799179 (1989-01-01), Masson et al.
patent: 4805129 (1989-02-01), David
patent: 4815023 (1989-03-01), Arbeiter
patent: 4817182 (1989-03-01), Adelson et al.
patent: 4821223 (1989-04-01), David
patent: 4827336 (1989-05-01), Acampora et al.
patent: 4829378 (1989-05-01), Legall
patent: 4837517 (1989-06-01), Barber
patent: 4839889 (1989-06-01), Gockler
patent: 4864398 (1989-09-01), Avis et al.
patent: 4868868 (1989-09-01), Yazu et al.
patent: 4894713 (1990-01-01), Delogne et al.
patent: 4897717 (1990-01-01), Hamilton et al.
patent: 4904073 (1990-02-01), Lawton et al.
patent: 4918524 (1990-04-01), Ansari et al.
patent: 4922544 (1990-05-01), Stansfield et al.
patent:
Allen James D.
Boliek Martin
Schwartz Edward L.
Zandi Ahmad
Blakely , Sokoloff, Taylor & Zafman LLP
Couso Jose L.
Ricoh Co. Ltd.
LandOfFree
Apparatus for compression using reversible embedded wavelets 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 for compression using reversible embedded wavelets, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Apparatus for compression using reversible embedded wavelets will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2476538