Compression and decompression system with reversible wavelets and lossy reconstruction

• US 6,754,394 B2
• Filed: 05/01/2000
• Issued: 06/22/2004
• 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., Keith, Alexander F., Schwartz, Edward L., Boliek, Martin
• Primary Examiner(s): Johnson, Timothy M.
• Application Number:
  US09/562,648
• Publication Number:
  US 20020172429A1
• Time in Patent Office: 1,513 Days
• Field of Search: 382/232, 382/233, 382/240, 382/242, 382/243, 382/248, 382/251, 382/263, 382/264, 382/266, 382/275, 341/79, 348/397.1, 348/398.1, 348/405.1, 348/408.1, 348/437.1, 348/438.1, 375/240.03, 375/240.1, 375/240.18, 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/10 using adaptive coding
• 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/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/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/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/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/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 method and apparatus for encoding and decoding data that includes 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 transform signals into data representing a losslessly compressed version of the input data. In one embodiment, the present invention decomposes the input data using reversible wavelet transforms.

Claims

1. A method of reconstruction of image data having a plurality of tiles comprising:

reconstructing coefficients corresponding to low frequency horizontal information and high frequency vertical information to be smooth across each boundary between the plurality of tiles, if applicable;

performing a vertical inverse transform individually on each tile having reconstructed coefficients corresponding to low frequency horizontal information and high frequency vertical information;

reconstructing coefficients corresponding to high frequency horizontal information and high frequency vertical information to be smooth across each boundary between the plurality of tiles, if applicable; and

performing a horizontal inverse transform individually on each tile having reconstructed high frequency horizontal information and high frequency vertical information.

2. The method of claim 1 wherein the coefficients corresponding to low frequency horizontal information and high frequency vertical information comprise horizontal boundary information.

3. The method of claim 1 wherein the vertical inverse transform comprises a Two-Ten (TT) transform.

4. The method of claim 1 wherein the coefficients corresponding to high frequency horizontal information and high frequency vertical information comprise vertical boundary information.

5. The method of claim 1 wherein the horizontal inverse transform comprises a Two-Ten (TT) transform.

6. The method of claim 1 wherein the reconstruction of coefficients corresponding to low frequency horizontal information and high frequency vertical information, the performance of the inverse vertical transform, the reconstruction of coefficients corresponding to high frequency horizontal information and high frequency vertical information, and the performance of the inverse horizontal transform are repeated for each unit of coded data.

7. The method of claim 6 wherein the inverse horizontal transform is preformed on a pair of image lines.

8. The method of claim 6 wherein each unit of coded data comprises an importance level.

9. The method of claim 1 further comprising making the reconstructed coefficients consistent with actual quantized coefficients.

10. The method of claim 1 further comprising:

saving coefficients corresponding to high frequency horizontal information and low frequency vertical information effected by a tile boundary; and

saving coefficients corresponding to high frequency horizontal information and high frequency vertical information effected by a tile boundary.

11. A computer software product including a medium readable by a processor, the medium having stored thereon instructions that, when executed by the processor, cause the processor to:

reconstruct coefficients corresponding to low frequency horizontal information and high frequency vertical information to be smooth across each boundary between the plurality of tiles, if applicable;

perform a vertical inverse transform individually on each tile having reconstructed coefficients corresponding to low frequency horizontal information and high frequency vertical information;

reconstruct coefficients corresponding to high frequency horizontal information and high frequency vertical information to be smooth across each boundary between the plurality of tiles, if applicable; and

perform a horizontal inverse transform individually on each tile having reconstructed high frequency horizontal information and high frequency vertical information.

12. The computer software product of claim 11 wherein the coefficients corresponding to low frequency horizontal information and high frequency vertical information comprise horizontal boundary information.

13. The computer software product of claim 11 wherein the vertical inverse transform comprises a Two-Ten (TT) transform.

14. The computer software product of claim 11 wherein the coefficients corresponding to high frequency horizontal information and high frequency vertical information comprise vertical boundary information.

15. The computer software product of claim 11 wherein the horizontal inverse transform comprises a Two-Ten (TT) transform.

16. The computer software product of claim 11, wherein the reconstruction of coefficients corresponding to low frequency horizontal information and high frequency vertical information, the performance of the inverse vertical transform, the reconstruction of coefficients corresponding to high frequency horizontal information and high frequency vertical information, and the performance of the inverse horizontal transform are repeated for each unit of coded data.

17. The computer software product of claim 16 wherein the inverse horizontal transform is performed on a pair of image lines.

18. The computer software product of claim 16 wherein each unit of coded data comprises an importance level.

19. The computer software product of claim 11 further comprising making the reconstructed coefficients consistent with actual quantized coefficients.

20. The computer software product of claim 11 further comprising that, when executed cause the processor to:

save coefficients corresponding to high frequency horizontal information and low frequency vertical information effected by a tile boundary; and

save coefficients corresponding to high frequency horizontal information and high frequency vertical information effected by a tile boundary.

21. The apparatus for reconstruction of image data having a plurality of tiles comprising:

means for reconstructing coefficients corresponding to low frequency horizontal information and high frequency vertical information to be smooth across each boundary between the plurality of tiles, if applicable;

means for performing a vertical inverse transform individually on each tile having reconstructed coefficients corresponding to low frequency horizontal information and high frequency vertical information;

means for reconstructing coefficients corresponding to high frequency horizontal information and high frequency vertical information to be smooth across each boundary between the plurality of tiles, if applicable; and

means for performing a horizontal inverse transform individually on each tile having reconstructed high frequency horizontal information and high frequency vertical information.

22. The apparatus of claim 21 wherein the coefficients corresponding to low frequency horizontal information and high frequency vertical information comprise horizontal boundary information.

23. The apparatus of claim 21 wherein the coefficients corresponding to high frequency horizontal information and high frequency vertical information comprise vertical boundary information.

24. The apparatus of claim 21 further means for comprising making the reconstructed coefficients consistent with actual quantized coefficients.

25. The apparatus of claim 21 further comprising:

means for saving coefficients corresponding to high frequency horizontal information and low frequency vertical information effected by a tile boundary; and

means for saving coefficients corresponding to high frequency horizontal information and high frequency vertical information effected by a tile boundary.