Compression and decompression system with reversible wavelets and lossy reconstruction

• US 6,996,281 B2
• Filed: 11/19/2003
• Issued: 02/07/2006
• 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, Keith, Alexander F.
• Primary Examiner(s): Couso, Jose L.
• Application Number:
  US10/718,226
• Publication Number:
  US 20040114810A1
• Time in Patent Office: 811 Days
• Field of Search: 382232-234, 382/236, 382/238, 382/239, 382/248, 382/250, 382/251, 358/426.04, 358/426.06, 358/426.07, 358/426.11, 348/390.1, 348/394.1, 348/395.1, 348/403.1, 375/240.01, 375/240.12, 375/240.18, 375/240.19, 375/240.24
• US Class Current: 382/236
• 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 for processing encoded data, said method comprising:

receiving an indication of an amount of data used to encode importance levels over a plurality of tiles, the indication embedded in the encoded data;

determining a predetermined amount of the encoded data to decode based on the amount of data used to encode the importance levels in order to maintain substantially identical fidelity over the plurality of tiles; and

decoding only the predetermined amount of the encoded data over the plurality of tiles.

2. The method defined in claim 1 wherein the decoding only the portion of the encoded data comprises decoding the encoded data starting with highest importance level and continuing in succession to lower importance levels until the predetermined amount of the encoded data has been decoded.

6. The method of claim 2, wherein at least two of the tiles have different amounts of data decoded for at least one of the importance levels.

7. The method of claim 1, wherein the indication comprises a tag having bits versus importance (BVI) information for each of the importance levels, each tag indicating an amount of data encoded for a respective importance level.

8. The method of claim 7, wherein the BVI tag comprises:

a first portion to indicate a number of importance levels encoded in a component currently being described by the BVI tag; and

a second portion to indicate an amount of data encoded for the importance levels specified by the first portion.

9. The method of claim 8, wherein the first portion of the BVI tag is selected at encode time to communicate with interest points in a rate-distortion curve.

10. The method of claim 8, wherein the BVI tag further comprises:

a third portion to indicate a length of the BVI tag; and

a fourth portion to identify the component associated with the first portion.

11. The method of claim 10, wherein the BVI tags for all importance levels are arranged staffing with all importance level description for a first component followed by all importance level description of a next component.

12. The method of claim 10, wherein the BVI tag further comprises an optional fifth portion to pad a predetermined value at an end of the BVI tag to enable the BVI tag to have a number of even bytes indicated in the third portion.

13. The method of claim 7, wherein the BVI tag is stored within a main header of the encoded data.

14. The method of claim 2, further comprising:

determining a percentage of data to be decoded for one importance levels; and

decoding the tiles for the determined percentage of encoded data for each of the importance levels until the predetermined amount of the encoded data has been decoded.

15. The method of claim 14, wherein for each tile in each importance level, a substantially identical percentage of encoded data over each tile and each importance level is decoded.

16. The method of claim 7, wherein the encoded data is arranged in a pyramidal alignment, wherein the BVI tag further indicates an amount of data from which an amount of data allocated for decoding is subtracted.

17. The method of claim 16, further comprising:

for each pyramid level, determining an amount of encoded data to be truncated across all importance levels using the BVI tag; and

decoding the encoded data for a respective pyramid level by truncating the determined amount of encoded data.

18. The method of claim 17, wherein the determined amount of encoded data to be truncated represents one or more importance levels to be truncated.

19. The method of claim 16, further comprising:

for each pyramid level, determining an amount of encoded data to be skipped prior to decoding across all importance levels using the BVI tag; and

decoding the encoded data for a respective pyramid level by skipping the determined amount of encoded data.

20. The method of claim 19, wherein the determined amount of encoded data to be truncated represents one or more importance levels to be skipped prior to decoding.

3. An apparatus for processing encoded data, said apparatus comprising:

means for receiving an indication of an amount of data used to encode importance levels over a plurality of tiles, the indication embedded in the encoded data;

means for determining a predetermined amount of the encoded data to decode based on the amount of data used to encode the importance levels in order to maintain substantially identical fidelity over the plurality of tiles; and

means for decoding only the predetermined amount of the encoded data over the plurality of tiles.

4. The apparatus defined in claim 3 wherein the means for decoding comprises means for decoding the encoded data starting with highest importance level and continuing in succession to lower importance levels until the predetermined amount of the encoded data has been decoded.

21. The apparatus of claim 4, wherein at least two of the tiles have different amounts of data decoded for at least one of the importance levels.

22. The apparatus of claim 3, wherein the indication comprises a tag having bits versus importance (BVI) information for each of the importance levels, each tag indicating an amount of data encoded for a respective importance level.

23. The apparatus of claim 22, wherein the BVI tag comprises:

a first portion to indicate a number of importance levels encoded in a component currently being described by the BVI tag; and

a second portion to indicate an amount of data encoded for the importance levels specified by the first portion.

24. The apparatus of claim 23, wherein the first portion of the BVI tag is selected at encode time to communicate with interest points in a rate-distortion curve.

25. The apparatus of claim 23, wherein the BVI tag further comprises:

a third portion to indicate a length of the BVI tag; and

a fourth portion to identify the component associated with the first portion.

26. The apparatus of claim 25, wherein the BVI tags for all importance levels are arranged starting with all importance level description for a first component followed by all importance level description of a next component.

27. The apparatus of claim 25, wherein the BVI tag further comprises an optional fifth portion to pad a predetermined value at an end of the BVI tag to enable the BVI tag to have a number of even bytes indicated in the third portion.

28. The apparatus of claim 22, wherein the BVI tag is stored within a main header of the encoded data.

29. The apparatus of claim 4, further comprising:

means for determining a percentage of data to be decoded for one of the importance levels; and

means for decoding the files for the determined percentage of encoded data for each of the importance levels until the predetermined amount of the encoded data has been decoded.

30. The apparatus of claim 29, wherein for each tile in each importance level, a substantially identical percentage of encoded data over each tile and each importance level is decoded.

31. The apparatus of claim 22, wherein the encoded data is arranged in a pyramidal alignment, wherein the BVI tag further indicates an amount of data from which an amount of data allocated for decoding is subtracted.

32. The apparatus of claim 31, further comprising:

for each pyramid level, means for determining an amount of encoded data to be truncated across all importance levels using the BVI tag; and

means for decoding the encoded data for a respective pyramid level by truncating the determined amount of encoded data.

33. The apparatus of claim 32, wherein the determined amount of encoded data to be truncated represents one or more importance levels to be truncated.

34. The apparatus of claim 31, further comprising:

for each pyramid level, means for determining an amount of encoded data to be skipped prior to decoding across an importance levels using the BVI tag; and

means for decoding the encoded data for a respective pyramid level by skipping the determined amount of encoded data.

35. The apparatus of claim 34, wherein the determined amount of encoded data to be truncated represents one or more importance levels to be skipped prior to decoding.

5. A computer software product including a medium readable by a processor, the medium having stored thereon a sequence of instructions which, when executed by the processor, causes the processor to:

receive an indication of the amount of data used to encode importance levels over a plurality of tiles, the indication embedded in the encoded data;

determine a predetermined amount of the encoded data to decode based on the amount of data used to encode the importance levels in order to maintain substantially identical fidelity over the plurality of iles; and

decode only the predetermined amount of the encoded data over the plurality of tiles.

36. The computer software product of claim 5, wherein the processor is further to decode the encoded data starting with highest importance level and continuing in succession to lower importance levels until the predetermined amount of the encoded data has been decoded.

37. The computer software product of claim 36, wherein at least two of the tiles have different amounts of data decoded for at least one of the importance levels.

38. The computer software product of claim 5, wherein the indication comprises a tag having bits versus importance (BVI) information for each of the importance levels, each tag indicating an amount of data encoded for a respective importance level.

39. The computer software product of claim 38, wherein the BVI tag comprises:

a first portion to indicate a number of importance levels encoded in a component currently being described by the BVI tag; and

a second portion to indicate an amount of data encoded for the importance levels specified by the first portion.

40. The computer software product of claim 39, wherein the first portion of the BVI tag is selected at encode time to communicate with interest points in a rate-distortion curve.

41. The computer software product of claim 39, wherein the BVI tag further comprises:

a third portion to indicate a length of the BVI tag; and

a fourth portion to identify the component associated with the first portion.

42. The computer software product of claim 41, wherein the BVI tags for all importance levels are arranged starting with all importance level description for a first component followed by all importance level description of a next component.

43. The computer software product of claim 41, wherein the BVI tag further comprises an optional fifth portion to pad a predetermined value at an end of the BVI tag to enable the BVI tag to have a number of even bytes indicated in the third portion.

44. The computer software product of claim 38, wherein the BVI tag is stored within a main header of the encoded data.

45. The computer software product of claim 36, wherein the processor is further to:

determine a percentage of data to be decoded for one of the importance levels, and

decode the tiles for the determined percentage of encoded data for each of the importance levels until the predetermined amount of the encoded data has been decoded.

46. The computer software product of claim 45, wherein for each tile in each importance level, a substantially identical percentage of encoded data over each rile and each importance level is decoded.

47. The computer software product of claim 36, wherein the encoded data is arranged in a pyramidal alignment, wherein the BVI tag further indicates an amount of data from which an amount of data allocated for decoding is subtracted.

48. The computer software product of claim 47, wherein the processor is further to:

for each pyramid level, determine an amount of encoded data to be truncated across all importance levels using the BVI tag, and

decode the encoded data for a respective pyramid level by truncating the determined amount of encoded data.

49. The computer software product of claim 48, wherein the determined amount of encoded data to be truncated represents one or mom importance levels to be truncated.

50. The computer software product of claim 47, wherein the processor is further to:

for each pyramid level, determine an amount of encoded data to be skipped prior to decoding across all importance levels using the BVI tag, and

decode the encoded data for a respective pyramid level by skipping the determined amount of encoded data.

51. The computer software product of claim 50, wherein the determined amount of encoded data to be truncated represents one or more importance levels to be skipped prior to decoding.

52. A data processing system, comprising:

a processor;

a memory coupled to the processor for storing instructions, when executed from the memory, cause the processor to

receive an indication of an amount of data used to encode importance levels over a plurality of tiles, the indication embedded in the encoded data,

determine a predetermined amount of the encoded data to decode based on the amount of data used to encode the importance levels in order to maintain substantially identical fidelity over the plurality of tiles, and

decode only the predetermined amount of the encoded data over the plurality of tiles.