Compression/decompression using reversible embedded wavelets

• US 6,757,437 B1
• Filed: 01/30/2001
• Issued: 06/29/2004
• Est. Priority Date: 09/21/1994
• Status: Expired due to Fees

• Current Assignee: Ricoh Company Limited, Ricoh Corporation (Ricoh Company Limited)
• Original Assignee: Ricoh Company Limited, Ricoh Corporation (Ricoh Company Limited)
• Inventors: Gormish, Michael J., Schwartz, Edward L., Boliek, Martin, Zandi, Ahmad, Keith, Alexander F.
• Primary Examiner(s): Tran, Phuoc
• Application Number:
  US09/773,322
• Time in Patent Office: 1,246 Days
• Field of Search: 382/166, 382/233, 382/240, 382/246, 382/248, 382/251, 382/260, 382/263, 382/264, 382/261, 341/81, 375/240.19, 375/240.25
• US Class Current: 382/240
• CPC Class Codes: G06F 17/148 Wavelet transforms
• CPC Class Codes: H03M 7/30 Compression speech analysis-synthesis for redundancy reduction G10L19/00; for image communication H04N; Expansion; Suppression of unnecessary data, e.g. redundancy reduction
• CPC Class Codes: H04N 19/102 characterised by the element, parameter or selection affected or controlled by the adaptive coding
• CPC Class Codes: H04N 19/115 Selection of the code volume for a coding unit prior to coding
• CPC Class Codes: H04N 19/12 Selection from among a plurality of transforms or standards, e.g. selection between discrete cosine transform [DCT] and sub-band transform or selection between H.263 and H.264
• CPC Class Codes: H04N 19/129 Scanning of coding units, e.g. zig-zag scan of transform coefficients or flexible macroblock ordering [FMO]
• CPC Class Codes: H04N 19/13 Adaptive entropy coding, e.g. adaptive variable length coding [AVLC] or context adaptive binary arithmetic coding [CABAC]
• CPC Class Codes: H04N 19/14 Coding unit complexity, e.g. amount of activity or edge presence estimation H04N19/146 takes precedence
• CPC Class Codes: H04N 19/146 Data rate or code amount at the encoder output
• CPC Class Codes: H04N 19/15 by monitoring actual compressed data size at the memory before deciding storage at the transmission buffer
• CPC Class Codes: H04N 19/162 User input
• CPC Class Codes: H04N 19/167 Position within a video image, e.g. region of interest [ROI]
• CPC Class Codes: H04N 19/176 the region being a block, e.g. a macroblock
• CPC Class Codes: H04N 19/186 the unit being a colour or a chrominance component
• CPC Class Codes: H04N 19/36 Scalability techniques involving formatting the layers as a function of picture distortion after decoding, e.g. signal-to-noise [SNR] scalability
• CPC Class Codes: H04N 19/42 characterised by implementation details or hardware specially adapted for video compression or decompression, e.g. dedicated software implementation H04N19/635 takes precedence
• CPC Class Codes: H04N 19/46 Embedding additional information in the video signal during the compression process H04N19/517, H04N19/68, H04N19/70 take precedence
• CPC Class Codes: H04N 19/593 involving spatial prediction techniques
• CPC Class Codes: H04N 19/60 using transform coding
• CPC Class Codes: H04N 19/61 in combination with predictive coding
• CPC Class Codes: H04N 19/63 : using sub-band based transform, e.g. wavelets
• CPC Class Codes: H04N 19/635 : characterised by filter definition or implementation details
• CPC Class Codes: H04N 19/647 : using significance based coding, e.g. Embedded Zerotrees of Wavelets [EZW] or Set Partitioning in Hierarchical Trees [SPIHT]
• CPC Class Codes: H04N 19/98 : Adaptive-dynamic-range coding [ADRC]
• CPC Class Codes: H04N 21/234354 : by altering signal-to-noise ratio parameters, e.g. requantization
• CPC Class Codes: H04N 21/2383 : Channel coding or modulation of digital bit-stream, e.g. QPSK modulation arrangements for detecting or preventing errors in the information received by adapting the channel coding H04L1/0009; analogue front ends or means for connecting modulators, demodulators or transceivers to a transmission line H04L27/0002
• CPC Class Codes: H04N 21/6377 : directed to server one-way streaming services wherein the source is controlled by the destination H04L65/613
• CPC Class Codes: H04N 21/658 : Transmission by the client directed to the server

Abstract

A compression and decompression system in which a reversible wavelet filter are used to generates coefficients from input data, such as image data. The reversible wavelet filter is an efficient transform implemented with integer arithmetic that has exact reconstruction. The present invention uses the reversible wavelet filter in a lossless system (or lossy system) in which an embedded codestream is generated from the coefficients produced by the filter. An entropy coder performs entropy coding on the embedded codestream to produce the compressed data stream.

Claims

1. An encoder, comprising:

a multi-component handling mechanism to process a plurality of pixels, wherein each pixel includes a plurality of components, wherein each component of the plurality of components is coded separately;

a high pass and low pass filter pair coupled to the multi-component handling mechanism to perform a reversible wavelet transform to produce a series of coefficients in response to the plurality of pixels, the series of coefficients being groups of coefficients, where each group of coefficients corresponds to one of the plurality of components for the plurality of pixels, wherein the reversible wavelet transform is implemented in integer arithmetic such that a signal with integer coefficients is losslessly recoverable; and

at least one coder coupled to the reversible wavelet transform filter pair and responsive to the series of coefficients to generate entropy coded data.

2. The encoder defined in claim 1, wherein the plurality of components comprise color space components.

3. The encoder defined in claim 1, wherein the plurality of components comprise spectral components.

4. The encoder defined in claim 1, further comprising a storage to store entropy coded data associated with each component of the plurality of components separately.

5. The encoder defined in claim 4, further comprising:

a decompressor; and

a parser coupled to the decompressor and the storage.

6. The encoder defined in claim 5, wherein the parser obtains one or more components from the storage to generate a first type of image, the one or more components are associated with one or more decomposition levels, wherein the one or more decomposition levels are selected based on desired resolution of the first type of image.

7. An encoder defined in claim 6 wherein the first type of image is a lossy output image.

8. An encoder defined in claim 1, wherein the at least one coder includes an entropy coder to generate entropy coded data for each component of the plurality of components, the entropy coded data is separated from each other.

9. An encoder defined in claim 8, further comprising a parser to quantize the plurality of components independently.

10. An encoder defined in claim 1, wherein the entropy coded data of the plurality of components is interleaved by frequency band.

11. An encoder defined in claim 1, wherein the entropy coded data of the plurality of components is interleaved by importance level.

12. An encoder defined in claim 1, wherein the entropy coded data of the plurality of components is interleaved for each pixel of the plurality of pixels.

13. An encoder defined in claim 1, wherein the entropy coded data of the plurality of components is interleaved for each of a plurality of coefficients.

14. A decoder comprising:

at least one entropy decoder to generate a series of coefficients by decoding entropy encoded data, the series of coefficients being a plurality of groups of coefficients, where each group of coefficients corresponds to one of a plurality of components for a plurality of pixels;

a high pass and low pass filter pair coupled to the at least one entropy decoder to perform a reversible inverse wavelet transform to produce data for the plurality of components for the plurality of pixels in response to the series of coefficients, wherein the reversible inverse wavelet transform is implemented in integer arithmetic such that a signal with integer coefficients is losslessly recoverable; and

a multi-component handling mechanism coupled to the high pass and low pass filter pair to create the plurality of pixels in response to the plurality of components.

15. The decoder defined in claim 14 wherein the plurality of components comprise one selected from a group consisting of color space components and spectral components.

16. The decoder defined in claim 14 further comprising:

a storage coupled to the at least one entropy decoder to store entropy coded data associated with each of the plurality of components; and

a parser coupled to the storage.

17. The decoder defined in claim 16 wherein the parser selects entropy coded data associated with one or more components of the plurality of components to cause the at least one entropy decoder and the inverse wavelet transform to generate an image, wherein the one or more components are associated with one or more decomposition levels selected based on a desired resolution of the image.

18. The decoder defined in claim 17 wherein the image is lossy.

19. The decoder defined in claim 14 wherein the reversible inverse wavelet transform is implemented using only addition, subtraction, and bit shifting operations.