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

• US 6,873,734 B1
• Filed: 02/07/2000
• Issued: 03/29/2005
• 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
• Primary Examiner(s): TRAN, PHUOC
• Application Number:
  US09/499,255
• Time in Patent Office: 1,877 Days
• Field of Search: 382/232, 382/233, 382/239, 382/240, 382/251, 382/248, 375/240.18, 375/240.19
• US Class Current: 382/233
• 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 of using an embedded codestream comprising:

identifying a target device to receive data in the embedded codestream; and

decoding each bit-plane to provide data to the target device by truncating each bit-plane in the embedded codestream for data necessary to support the target device, wherein each bit-plane is truncated based on an indication in each coding unit denoting a location where truncation may occur.

2. The method defined in claim 1 wherein the indication comprises a marker.

3. The method defined in claim 1 wherein the indication comprises a pointer.

4. The method defined in claim 1 wherein each bit-plane is truncated based on one of a plurality of indications in each coding unit denoting where truncation may occur further comprises selecting one of the indications based on the target device.

5. The method defined in claim 1 wherein truncating comprises truncating target resolution coefficients, coded separately in each coding unit, from the embedded codestream.

6. The method of claim 1 wherein the target device comprises a low resolution, high pixel depth embedded target such that decoding decodes as many higher level coefficients as needed to achieve full pixel depth and low spatial resolution of the target device.

7. The method defined in claim 1 wherein the target device comprises a high resolution, low pixel depth embedded target and truncating each coding unit at a number of bit-planes and inverse wavelet transforming the non-truncated data of each coding unit to achieve the low pixel depth and high spatial resolution of the target device.

8. The method defined in claim 1 further comprising:

selecting coding units based on an amount of available buffering at the target device; and

truncating each coding unit with more data than available buffering.

9. The method defined in claim 1 wherein truncating further comprises:

determining a uniform amount to truncate each coding unit; and

truncating at least a portion of at least one importance level in each coding unit.

10. The method defined in claim 9 wherein truncation is performed using information in a header of the codestream setting forth importance level information.

11. The method defined in claim 9 wherein truncation is performed using information in a header of the codestream setting forth importance level information for each coding unit in the codestream.

12. The method defined in claim 9 being performed after encode time.

13. An apparatus comprising a computer-readable medium having stored thereon sequences of instructions that, when executed, cause one or more processors to:

identify a target device to receive data in the embedded codestream;

decode each bit-plane to provide data to the target device by truncating each bit-plane in the embedded codestream for data necessary to support the target device, wherein each bit-plane is truncated based on an indication in each coding unit denoting a location where truncation may occur.

14. The apparatus defined in claim 13 wherein the indication comprises a marker.

15. The apparatus defined in claim 13 wherein the indication comprises a pointer.

16. The apparatus defined in claim 13 wherein the instructions that cause each bit-plane is truncated based on one of a plurality of indications in each coding unit denoting where truncation may occur further comprise instructions that, when executed, cause the one or more processors to select one of the indications based on the target device.

17. The apparatus defined in claim 13 wherein the instructions that cause the one or more processors to truncate comprises instructions that, when executed, cause the one or more processors to truncate target resolution coefficients, coded separately in each coding unit, from the embedded codestream.

18. The apparatus of claim 13 wherein the target device comprises a low resolution, high pixel depth embedded target such that the instructions that cause the one or more processors to decode cause the one or more processors to decode as many higher level coefficients as needed to achieve full pixel depth and low spatial resolution of the target device.

19. The apparatus defined in claim 13 wherein the target device comprises a high resolution, low pixel depth embedded target and truncating each coding unit at a number of bit-planes and inverse wavelet transforming the non-truncated data of each coding unit to achieve the low pixel depth and high spatial resolution of the target device.

20. The apparatus defined in claim 13 further comprising instructions that, when executed, cause the one or more processors to:

select coding units based on an amount of available buffering at the target device; and

truncate each coding unit with more data than available buffering.

21. The apparatus defined in claim 18 wherein the instructions that cause the one or more processors to truncate further comprise instructions that, when executed cause the one or more processors to:

determine a uniform amount to truncate each coding unit; and

truncate at least a portion of at least one importance level in each coding unit.

22. The apparatus defined in claim 21 wherein truncation is performed using information in a header of the codestream setting forth importance level information.

23. The apparatus defined in claim 21 wherein truncation is performed using information in a header of the codestream setting forth importance level information for each coding unit in the codestream.