Method and apparatus for compression using reversible wavelet transforms and an embedded codestream

• US 7,215,820 B2
• Filed: 01/10/2003
• Issued: 05/08/2007
• Est. Priority Date: 09/21/1994
• Status: Expired due to Fees

• Current Assignee: Ricoh Company Limited
• Original Assignee: Ricoh Company Limited
• Inventors: Gormish, Michael J., Schwartz, Edward L., Boliek, Martin, Zandi, Ahmad
• Primary Examiner(s): Tran; Phuoc
• Application Number:
  US10/340,491
• Publication Number:
  US 20030169936A1
• Time in Patent Office: 1,579 Days
• Field of Search: 382/232, 382/233, 382/240, 382/244, 382/248, 375/240.19
• 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/122 Selection of transform size, e.g. 8x8 or 2x4x8 DCT; Selection of sub-band transforms of varying structure or type
• 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/15 by monitoring actual compressed data size at the memory before deciding storage at the transmission buffer
• CPC Class Codes: H04N 19/156 Availability of hardware or computational resources, e.g. encoding based on power-saving criteria
• 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/1883 the unit relating to sub-band structure, e.g. hierarchical level, directional tree, e.g. low-high [LH], high-low [HL], high-high [HH]
• CPC Class Codes: H04N 19/34 Scalability techniques involving progressive bit-plane based encoding of the enhancement layer, e.g. fine granular scalability [FGS]
• 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/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. A method for processing data, the method comprising:

transforming the input data into a plurality of coefficients using a reversible wavelet filter, the reversible wavelet filter to apply a reversible wavelet transform to the input data;

generating an embedded codestream in response to the plurality of coefficients;

binary entropy coding the embedded codstream to produce the compressed data stream; and

parsing the compressed data stream.

3. The method defined in claims 1 or 2 further comprising:

decoding data in the codestream; and

supplying decoded data to a target device.

4. The method defined in claim 3 further comprising truncating a portion of the codestream based on the target device.

5. The method defined in claim 4 wherein truncating a portion of the codestream comprises truncating coding units in the codestream.

6. The method defined in claim 5 wherein truncating coding units in the code stream is based on information in the header of the codestream.

7. The method defined in claim 6 wherein the information in the header includes significance information indicating the significance of coding units.

8. The method defined in claim 7 wherein the information in the header indicates where truncation may occur.

9. The method defined in claim 8 wherein the information comprises a marker.

10. The method defined in claim 8 wherein the information comprises a pointer.

11. The method defined in claim 8 wherein the information indicates where truncation may occur in each bit plane.

12. The method defined in claim 5 wherein truncating coding units in the codestream is based on significance.

13. The method defined in claim 3 wherein the target device comprises a low resolution, high pixel depth embedded target, and further wherein decoding data in the codestream comprises decoding only higher level coefficients needed to achieve full pixel depth and low spatial resolution of the target device.

14. The method defined in claim 3 wherein the target device comprises a high resolution, low pixel depth embedded target, and further wherein decoding data in the codestream comprises decoding only higher level coefficients needed to achieve low pixel depth and high spatial resolution of the target device.

2. A method comprising:

receiving coded data that has been generated by

transforming the input data into a plurality of coefficients using a reversible wavelet filter, including the reversible wavelet filter applying a reversible wavelet transform to the input data,

generating an embedded codestream in response to the plurality of coefficients, and

binary entropy coding the embedded codestream to produce the coded data in a codestream; and

parsing the codestream.

15. An article of manufacture comprising one or more computer-readable media having executable instructions stored thereon which, when executed by a system, causes the system to process data by:

transforming the input data into a plurality of coefficients using a reversible wavelet filter, including applying a reversible wavelet transform to the input data using the reversible wavelet filter;

generating an embedded codestream in response to the plurality of coefficients;

binary entropy coding the embedded codstream to produce the compressed data stream; and

parsing the compressed data stream.

17. The article of manufacture defined in claims 15 or 16 further comprising instructions which, when executed by the system, cause the system to:

decode data in the codestream; and

supply decoded data to a target device.

18. The article of manufacture defined in claim 17 further comprising instructions which, when executed by the system, cause the system to truncate a portion of the codestream based on the target device.

19. The article of manufacture defined in claim 18 wherein the instructions that cause the system to truncate a portion of the codestream comprises instructions, which when executed by the system cause the system to truncate coding units in the codestream.

20. The article of manufacture defined in claim 19 wherein the instructions that cause the system to truncate coding units in the codestream operate on information in the header of the codestream.

21. The article of manufacture defined in claim 20 wherein the information in the header includes significance information indicating the significance of coding units.

22. The article of manufacture defined in claim 21 wherein the information in the header indicates where truncation may occur.

23. The article of manufacture defined in claim 22 wherein the information comprises a marker.

24. The article of manufacture defined in claim 22 wherein the information comprises a pointer.

25. The article of manufacture defined in claim 22 wherein the information indicates where truncation may occur in each bit plane.

26. The article of manufacture defined in claim 19 wherein instructions causing the system to truncate coding units in the codestream causes truncation based on significance.

27. The article of manufacture defined in claim 17 wherein the target device comprises a low resolution, high pixel depth embedded target, and further wherein instructions to cause the system to decode data in the codestream comprises instructions which, when executed by the system, cause the system to decode only higher level coefficients needed to achieve full pixel depth and low spatial resolution of the target device.

28. The article of manufacture defined in claim 17 wherein the target device comprises a high resolution, low pixel depth embedded target, and further wherein instructions to cause the system to decode data in the codestream comprises instructions which, when executed by the system, cause the system to decode only higher level coefficients needed to achieve low pixel depth and high spatial resolution of the target device.

16. An article of manufacture comprising one or more computer-readable media having executable instructions stored thereon which, when executed by a system, causes the system to process data by:

receiving coded data that has been generated by

transforming the input data into a plurality of coefficients using a reversible wavelet filter, including applying a reversible wavelet transform to the input data using the reversible wavelet filter,

generating an embedded codestream in response to the plurality of coefficients, and

binary entropy coding the embedded codestream to produce the coded data in a codestream; and

parsing the codestream.

29. An apparatus for processing data comprising:

means for transforming the input data into a plurality of coefficients using a reversible wavelet filter, the reversible wavelet filter to apply a reversible wavelet transform to the input data;

means for generating an embedded codestream in response to the plurality of coefficients;

means for binary entropy coding the embedded codstream to produce the compressed data stream; and

means for parsing the compressed data stream.

31. The apparatus defined in claims 29 or 30 further comprising:

means for decoding data in the codestream; and

means for supplying decoded data to a target device.

32. The apparatus defined in claim 31 further comprising means for truncating a portion of the codestream based on the target device.

33. The apparatus defined in claim 32 wherein the means for truncating a portion of the code stream comprises means for truncating coding units in the codestream.

34. The apparatus defined in claim 33 wherein the means for truncating coding units in the codestream operates based on information in the header of the codestream.

35. The apparatus defined in claim 34 wherein the information in the header includes significance information indicating the significance of coding units.

36. The apparatus defined in claim 35 wherein the information in the header indicates where truncation may occur.

37. The apparatus defined in claim 36 wherein the information comprises a marker.

38. The apparatus defined in claim 36 wherein the information comprises a pointer.

39. The apparatus defined in claim 36 wherein the information indicates where truncation may occur in each bit plane.

40. The apparatus defined in claim 33 wherein the means for truncating coding units in the codestream operates based on significance.

41. The apparatus defined in claim 31 wherein the target device comprises a low resolution, high pixel depth embedded target, and further wherein the means for decoding data in the codestream comprises means for decoding only higher level coefficients needed to achieve full pixel depth and low spatial resolution of the target device.

42. The apparatus defined in claim 31 wherein the target device comprises a high resolution, low pixel depth embedded target, and further wherein the means for decoding data in the codestream comprises means for decoding only higher level coefficients needed to achieve low pixel depth and high spatial resolution of the target device.

30. An apparatus comprising:

means for receiving coded data that has been generated by

transforming the input data into a plurality of coefficients using a reversible wavelet filter, including applying a reversible wavelet transform to the input data using the reversible wavelet filter,

generating an embedded codestream in response to the plurality of coefficients, and

binary entropy coding the embedded codestream to produce the coded data in a codestream; and

means for parsing the codestream.