METHOD FOR COMPRESSION USING REVERSIBLE EMBEDDED WAVELETS

• US 20020048405A1
• Filed: 09/30/1997
• Published: 04/25/2002
• Est. Priority Date: 09/20/1994
• Status: Active Grant

• Current Assignee: Ahmad Zandi, Edward L. Schwartz, James Allen, Martin Boliek
• Original Assignee: Ahmad Zandi, Edward L. Schwartz, James Allen, Martin Boliek
• Inventors: ALLEN, JAMES D., BOLIEK, MARTIN, SCHWARTZ, EDWARD L., ZANDI, AHMAD
• Granted Patent: US 7,418,142 B2
• Time in Patent Office: Days
• US Class Current: 382/232
• 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/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/146 Data rate or code amount at the encoder output
• 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/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/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/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/4382 : Demodulation or channel decoding, e.g. QPSK demodulation analog 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/6379 : directed to encoder , e.g. for requesting a lower encoding rate
• CPC Class Codes: H04N 21/658 : Transmission by the client directed to the server

Abstract

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.

Claims

1. A method for encoding input data comprising the steps of:

generating transformed signals in response to the input data, wherein the transformed signals are generated using a reversible wavelet transform; and

compressing the transformed signals into data representing a losslessly compressed version of the input data.

2. The method defined in claim 1 wherein the transformed signals comprises a plurality of coefficients.

3. The method defined in claim 1 wherein the step of generating comprises decomposing the input data using at least one non-minimal length reversible filter to produce a series of coefficients.

4. The defined in claim 3 wherein said at least one non-minimal length reversible filter comprises a plurality of one-dimensional filters.

5. The method defined in claim 1 wherein the input data comprises image data.

6. The method defined in claim 1 wherein the step of compressing comprises embedded coding the transformed signals, including the steps of ordering the series of coefficients and performing bit significance embedding on the transformed signals.

7. The method defined in claim 1 further comprising the steps

decompressing the losslessly compressed version of the input data into transformed signals;

and

generating the input data from the transformed signals into a reconstructed version of the input data using an inverse reversible wavelet transform.

8. A method for decoding data into original data comprising the steps of:

decompressing a losslessly compressed version of input data into a plurality of transformed signals; and

generating a reconstructed version of original data from the plurality of transformed signals using an inverse reversible wavelet transform.

9. The method defined in claim 8 wherein the transformed signals comprises a plurality of coefficients.

10. The method defined in claim 8 wherein the step of generating comprises composing the input data using at least one non-minimal length reversible filter to produce a series of coefficients.

11. The method defined in claim 10 wherein said at least one non-minimal length reversible filter comprises a plurality of one-dimensional filters.

14. The method defined in claim 13 wherein the step of transform coding comprises wavelet filtering the input data.

15. The method defined in claim 13 wherein the first type of embedded coding comprises tree coding.

16. The method defined in claim 13 wherein the step of embedded coding comprises formatting the series of coefficients into sign-magnitude format.

18. The method defined in claim 15 further comprising entropy coding the single bit stream.

19. The method defined in claim 17 wherein the first type of coding comprises tree order coding.

20. The method defined in claim 17 wherein the first portion comprises the high order bits and the second portion comprises the lower order bits.

21. The method defined in claim 17 wherein the single bit stream represents a losslessly compressed version of the input data.

12. A method for encoding input data comprising the steps of:

generating a first plurality of transformed signals in response to the input data, wherein the transformed signals are generated using a reversible wavelet transform;

compressing the first plurality of transformed signals into data representing a losslessly compressed version of the input data;

decompressing the losslessly compressed version of the input data into a second plurality of transformed signals; and

generating the input data from the second plurality of transformed signals into a reconstructed version of the input data using an inverse reversible wavelet transform.

13. A method for encoding input data comprising the steps of:

transform coding the input data into a series of coefficients; and

embedded coding the series of coefficients, including the steps of ordering the series of coefficients and performing bit significance embedding on the series of coefficients, wherein a first type of embedded coding is performed on a first portion of the data and a second type of embedded coding is performed on a second portion of the data.

17. A method for encoding input data comprising the steps of:

transforming input data into a series of coefficients using reversible wavelets;

converting the series of coefficients into sign-magnitude format into a series of formatted coefficients;

coding a first portion of the series of formatted coefficients using a first type of embedded coding to produce a first bit stream; and

coding a second portion of the series of formatted coefficients using a second type of embedded coding to produce a second bit stream, wherein the first bit stream and second bit stream are combined into a single bit stream.