Compression and decompression system with reversible wavelets and lossy reconstruction

• US 20020172429A1
• Filed: 05/01/2000
• Published: 11/21/2002
• Est. Priority Date: 09/21/1994
• Status: Active Grant

• Current Assignee: Alexander F. Keith, Edward L. Schwartz, Martin Boliek, Michael J. Gormish
• Original Assignee: Alexander F. Keith, Edward L. Schwartz, Martin Boliek, Michael J. Gormish
• Inventors: Gormish, Michael J., Schwartz, Edward L., Boliek, Martin, Keith, Alexander F.
• Granted Patent: US 6,754,394 B2
• Time in Patent Office: Days
• 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.

This application is a continuation-in-part of application Ser. No. 08/643,268, entitled “Compression/Decompression Using Reversible Embedded Wavelets”, filed May 3, 1996, which is a continuation-in-part of application Ser. No. 08/498,036, entitled Reversible Wavelet Transform and Embedded Codestream Manipulation, filed Jun. 30, 1995, which is a continuation-in-part of application Ser. No. 08/310,146, entitled Apparatus for Compression Using Reversible Embedded Wavelets, filed Sep. 20, 1994.

Claims

1. A method of performing reconstruction comprising the steps of:

a) saving DS and DD coefficients effected by a boundary;

b) reconstructing SD coefficients to be smooth across the boundary;

c) applying a vertical inverse transform individually on each tile;

d) reconstructing D coefficients to be smooth across the boundary; and

e) applying a horizontal inverse transform individually on each tile.

2. The method defined in claim 1 further comprising the step of repeating steps a)-e) for each level.

3. The method defined in claim 2 wherein said each level comprises an importance level.

4. The method defined in claim 1 further comprising the step of making the SD and D coefficients consistent with actual quantized coefficients.

5. An apparatus for performing reconstruction comprising:

means for saving DS and DD coefficients effected by a boundary;

means for reconstructing SD coefficients to be smooth across the boundary;

means for applying a vertical inverse transform individually on each tile;

means for reconstructing D coefficients to be smooth across the boundary; and

means for applying a horizontal inverse transform individually on each tile.

6. The apparatus defined in claim 5 wherein the means for saving, means for reconstructing SD coefficients, the means for applying a vertical inverse transform, the means for reconstructing D coefficients, and the means for applying a horizontal inverse transform operate on each level individually.

7. The apparatus defined in claim 6 wherein said each level comprises an importance level.

8. The apparatus defined in claim 5 further comprising means for making the SD and D coefficients consistent with actual quantized coefficients.

9. 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, for each level, to:

save DS and DD coefficients effected by a boundary,

reconstruct SD coefficients to be smooth across the boundary,

apply a vertical inverse transform individually on each tile,

reconstruct D coefficients to be smooth across the boundary, and

apply a horizontal inverse transform individually on each tile.

10. A method of performing an inverse transform comprising the steps of:

a) performing an inverse vertical transform on SS and SD coefficients only;

b) performing the inverse vertical transform on DS and DD coefficients on two current lines of coefficients using DS coefficients from two previous lines;

c) performing an inverse horizontal transform for two vertically adjacent S and D coefficient pairs in said two current lines of coefficients; and

d) repeating b) and c) for each pair of lines after the two current lines.

11. The method defined in claim 10 wherein quantization of each SD coefficient controls reconstruction limits of two samples.

12. The method defined in claim 10 wherein quantization of DS and DD coefficients controls reconstruction limits of four samples.

13. The method defined in claim 10 wherein the SS and SD coefficients consumed by performing an inverse vertical transform on SS and SD coefficients only are not saved.

14. The method defined in claim 10 wherein the S components are treated as image data in the spatial domain.

16. The apparatus defined in claim 15 wherein quantization of each SD coefficient controls reconstruction limits of two samples.

17. The apparatus defined in claim 15 wherein quantization of DS and DD coefficients controls reconstruction limits of four samples.

18. The apparatus defined in claim 15 wherein the SS and SD coefficients consumed by performing an inverse vertical transform on SS and SD coefficients only are not saved.

19. The apparatus defined in claim 15 wherein the S components are treated as image data in the spatial domain.

15. An apparatus for performing an inverse transform comprising:

means for performing an inverse vertical transform on SS and SD coefficients only;

means for performing the inverse vertical transform on DS and DD coefficients on two current lines of coefficients using DS coefficients from two previous lines;

means for performing an inverse horizontal transform for two vertically adjacent S and D coefficient pairs in said two current lines of coefficients; and

wherein the means for performing an inverse vertical transform on SS and SD coefficients, the means for performing the inverse vertical transform on DS and DD coefficients, and the means for performing an inverse horizontal transform perform their operations repeatedly for each pair of lines after the two current lines.

20. 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:

a) perform an inverse vertical transform on SS and SD coefficients only,

b) perform the inverse vertical transform on DS and DD coefficients on two current lines of coefficients using DS coefficients from two previous lines,

c) perform an inverse horizontal transform for two vertically adjacent S and D coefficient pairs in said two current lines of coefficients, and

d) repeat b) and c) for each pair of lines after the two current lines.

21. A method of creating a preferred reconstruction comprising the steps of:

a) for each SD coefficient, computing a preferred reconstruction and clipping the preferred reconstruction to be consistent with quantization;

b) performing an inverse vertical transform on SS and SD coefficients only;

c) for each DS and DD coefficient, computing a preferred reconstruction and clipping the preferred reconstruction to be consistent with quantization;

d) performing the inverse vertical transform on DS and DD coefficients on two current lines of coefficients using DS coefficients from two previous lines;

e) performing an inverse horizontal transform for two vertically adjacent S and D coefficient pairs in said two current lines of coefficients; and

f) repeating d) and e) for each pair of lines after the two current lines.

23. The method defined in claim 21 further comprising the step of clipping the preferred reconstruction using minimum and maximum possible values of the bits that are unknown.

22. The method defined in 21 further comprising the step of repeating steps a)-f) for each subband.

26. The apparatus defined in claim 24 further comprising means for clipping the preferred reconstruction using minimum and maximum possible values of the bits that are unknown.

29. The method defined in claim 28 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 a predetermined amount of the encoded data has been decoded.

24. An apparatus for creating a preferred reconstruction comprising:

means for computing, for each SD coefficient, a preferred reconstruction and clipping the preferred reconstruction to be consistent with quantization;

means for performing an inverse vertical transform on SS and SD coefficients only;

means for computing, for each DS and DD coefficient, a preferred reconstruction and clipping the preferred reconstruction to be consistent with quantization;

means for performing the inverse vertical transform on DS and DD coefficients on two current lines of coefficients using DS coefficients from two previous lines;

means for performing an inverse horizontal transform for two vertically adjacent S and D coefficient pairs in said two current lines of coefficients; and

wherein the means for performing the inverse vertical transform on DS and DD coefficients and the means for performing an inverse horizontal transform for two vertically adjacent S and D coefficient pairs operate repeatedly for each pair of lines after the two current lines.

25. The apparatus defined in 24 further the operations are repeated for each subband.

27. 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:

a) for each SD coefficient, compute a preferred reconstruction and clipping the preferred reconstruction to be consistent with quantization,

b) perform an inverse vertical transform on SS and SD coefficients only,

c) for each DS and DD coefficient, compute a preferred reconstruction and clipping the preferred reconstruction to be consistent with quantization,

d) perform the inverse vertical transform on DS and DD coefficients on two current lines of coefficients using DS coefficients from two previous lines,

e) perform an inverse horizontal transform for two vertically adjacent S and D coefficient pairs in said two current lines of coefficients, and

f) repeat d) and e) for each pair of lines after the two current lines.

28. A method for processing encoded data, said method comprising the steps of:

receiving an indication of the amount of data used to encode importance levels over n tiles in the encoded data;

determining a predetermined amount of the encoded data to decode; and

decoding only the predetermined amount of the encoded data so that decoded data is obtained with the same fidelity over each tile.

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

means for receiving an indication of the amount of data used to encode importance levels over n tiles in the encoded data;

means for determining a predetermined amount of the encoded data to decode; and

means for decoding only the predetermined amount of the encoded data so that decoded data is obtained with the same fidelity over each tile.

31. The apparatus defined in claim 30 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 a predetermined amount of the encoded data has been decoded.

32. 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 n tiles in the encoded data;

determine a predetermined amount of the encoded data to decode; and

decode only the predetermined amount of the encoded data so that decoded data is obtained with the same fidelity over each tile.

33. A method of processing data comprising:

receiving a plurality of quantized zero coefficients;

injecting noise into the image by selecting appropriate reconstruction values for the quantized zero coefficients.

34. The method defined in claim 33 wherein the noise injected is a function of noise in an original image from which the plurality of quantized zero coefficients were generated.

35. The method defined in claim 34 further comprising the step of receiving information regarding the noise in the original image in a tag accompanying compressed coefficients from which the plurality of quantized zero coefficients are derived.

36. The method defined in claim 35 wherein the information comprises a distribution of noise in the original image.

37. The method defined in claim 35 wherein the information comprises the amplitude of noise in the original image.

38. The method defined in claim 35 wherein the information comprises the variance of noise in the original image.

40. The apparatus defined in claim 39 wherein the noise injected is a function of noise in an original image from which the plurality of quantized zero coefficients were generated.

41. The apparatus defined in claim 40 further comprising means for receiving information regarding the noise in the original image in a tag accompanying compressed coefficients from which the plurality of quantized zero coefficients are derived.

42. The apparatus defined in claim 41 wherein the information comprises a distribution of noise in the original image.

43. The apparatus defined in claim 41 wherein the information comprises the amplitude of noise in the original image.

44. The apparatus defined in claim 41 wherein the information comprises the variance of noise in the original image.

47. The method defined in claim 46 wherein the portion of memory outside the tile stores a predetermined value.

48. The method defined in claim 47 wherein the predetermined number is 0.

49. The method defined in claim 46 wherein the offsets are fixed.

39. An apparatus for processing data comprising:

means for receiving a plurality of quantized zero coefficients;

means for injecting noise into the image by selecting appropriate reconstruction values for the quantized zero coefficients.

45. 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 a plurality of quantized zero coefficients;

inject noise into the image by selecting appropriate reconstruction values for the quantized zero coefficients.

46. A method of processing tiles of encoded data comprising the steps of:

storing a tile having a tile size in a portion of memory larger than the tile size; and

performing decoding operation on coefficients in the tile stored in the portion of memory using a pointer to a location in the tile and a series of offsets from the location to locate a set of coefficients for access during decoding of each individual coefficient.

50. An apparatus processing tiles of encoded data comprising:

means for storing a tile having a tile size in a portion of memory larger than the tile size; and

means for performing decoding operation on coefficients in the tile stored in the portion of memory using a pointer to a location in the tile and a series of offsets from the location to locate a set of coefficients for access during decoding of each individual coefficient.

51. The apparatus defined in claim 50 wherein the portion of memory outside the tile stores a predetermined value.

52. The apparatus defined in claim 51 wherein the predetermined number is 0.

53. The apparatus defined in claim 50 wherein the offsets are fixed.

54. 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:

store a tile having a tile size in a portion of memory larger than the tile size, and

perform decoding operation on coefficients in the tile stored in the portion of memory using a pointer to a location in the tile and a series of offsets from the location to locate a set of coefficients for access during decoding of each individual coefficient.

55. A method of decoding data, said method comprising the steps of:

identifying when a plurality of identical contexts are to be provided to an entropy coder; and

performing a single coding operation for all of the plurality of identical contexts if the plurality of identical contexts occur in succession.

56. The method defined in claim 55 wherein the step of identifying when a plurality of identical contexts are going to be provided to an entropy coder comprises comparing a portion of an encoded input data stream to a prediction of what the encoded input data stream should be if the plurality of identical contexts occur in succession.

57. The method defined in claim 55 wherein the step of identifying when a plurality of identical contexts are going to be provided to an entropy coder comprises comparing a portion of an encoded input data stream to a pair of predictions of what the encoded input data stream should be if the plurality of identical contexts occur in succession, wherein the coding operation is performed when the encoded input data stream is equal to either prediction in the pair of predictions or falls between the pair of predictions.

59. The apparatus defined in claim 58 wherein means for identifying comprises means for comparing a portion of an encoded input data stream to a prediction of what the encoded input data stream should be if the plurality of identical contexts occur in succession.

60. The apparatus defined in claim 58 wherein the means for identifying comprises means for comparing a portion of an encoded input data stream to a pair of predictions of what the encoded input data stream should be if the plurality of identical contexts occur in succession, wherein the coding operation is performed when the encoded input data stream is equal to either prediction in the pair of predictions or falls between the pair of predictions.

58. An apparatus decoding data comprising:

means for identifying when a plurality of identical contexts are to be provided to an entropy coder; and

means for performing a single coding operation for all of the plurality of identical contexts if the plurality of identical contexts occur in succession.

61. 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:

identify when a plurality of identical contexts are to be provided to an entropy coder; and

perform a single coding operation for all of the plurality of identical contexts if the plurality of identical contexts occur in succession.

62. A method of reconstructing comprising the steps of:

determining a difference between a first coefficient and a second coefficient of predetermined number of coefficients where the first coefficient has a minimum value among the coefficients and the second coefficient has a maximum value among the coefficients;

reconstructing to other than a step edge where the difference between the predetermined number of coefficients is less than a predetermined threshold value;

reconstructing to a step edge where the difference between the predetermined number of coefficients is greater than a predetermined threshold value, wherein the step of reconstructing to a step edge comprises the steps of

computing first and second partial reconstruction values based on a predetermined number of coefficient values to the right and to the left of a location of a potential step edge,

computing a reconstruction value using one of the first and second partial reconstruction values based on whether one of the first and second partial reconstruction values is zero and whether signs of the first and second partial reconstruction values are the same.

63. The method defined in claim 62 wherein the resulting reconstruction is to linear where the difference between the predetermined number of coefficients is less than the predetermined threshold value.

64. The method defined in claim 62 wherein the predetermined number of coefficients comprise S coefficients only.

65. The method defined in claim 62 wherein the predetermined number of coefficients is 5.

66. The method defined in claim 62 wherein a partial reconstruction value of 0 is used in computing the reconstruction value if either of the first or second partial reconstruction values is 0.

67. The method defined in claim 62 wherein a partial reconstruction value equal to a partial reconstruction value having a minimum value as between the first or second partial reconstruction values if signs of the first or second partial reconstruction values are the same.

68. The method defined in claim 62 wherein computing at least one of the first and second partial reconstruction values comprises:

determining differences between outer and inner pairs of coefficient values;

testing whether magnitude of the difference between the outer pair is greater to magnitude of the difference between the inner pair;

setting the differences equal to each other if the magnitude of the difference between the outer pair is greater to the magnitude of the difference between the inner pair;

computing a ratio of the difference between the outer pair to the difference between the inner pair; and

setting said at least one of the he first and second partial reconstruction values to a product of the difference between the inner pair and a result derived using the ratio.

69. The method defined in claim 68 wherein the outer and inner pairs of coefficient values comprise S coefficients.

70. A method for performing a reconstruction comprising the steps of:

generating a reconstruction value; and

clipping the reconstruction value if the reconstruction value exceeds the bounds of neighboring coefficients, where the reconstruction value is clipped to a coefficient value within the bounds of the neighboring coefficients. of a neighboring coefficient with a value closest to the reconstruction value.

71. The method defined in claim 70 using a center sample as the reconstruction value if the subsequent reconstruction value does not exceed the bounds of neighboring coefficients.

72. The method defined in claim 70 using a sample value of one of a plurality of immediate neighbors of a center sample as the reconstruction value if the subsequent reconstruction value does not exceed the bounds of neighboring coefficients.

73. The method defined in claim 72 wherein the sample value of the one of the plurality of the immediate neighbors has a value closer to the center sample than the other of the he plurality of the immediate neighbors.

74. The method defined in claim 70 wherein the neighboring coefficients comprise neighboring S coefficients.

75. The method defined in claim 70 where the reconstruction value is clipped to a coefficient value of a neighboring coefficient with a value closest to the reconstruction value.

76. A method of modeling binary data comprising the steps of:

determining whether a first predetermined number of bits in a frequency band are the same;

sending a first bit having a first state and a second bit to a coder if the predetermined number of bits in the frequency band are the same, where the second bit indicates whether the first predetermined number of bits are all 1 or all 0;

sending the first bit having a second state different from the first state to the coder if the first predetermined number of bits in the frequency band are not the same;

if the first predetermined number of bits in the frequency band are not the same, then determining whether a second predetermined number of bits are the same;

sending a third bit indicating whether the second predetermined number of bits are the same; and

sending a context for a target bit based on neighboring coefficients if the second predetermined number of bits are not the same.

77. The method defined in claim 76 wherein the predetermined number of bits comprises all target bits.

78. The method defined in claim 76 wherein the step of determining whether the second predetermined number of bits are the same comprises determining whether the second predetermined number of bit are zero head bits.

80. The method defined in claim 79 wherein the step of first coding comprises coding a bit having a first state with a lookahead context.

81. The method defined in claim 80 further comprising the step of skipping the predetermined number of coefficients.

82. The method defined in claim 79 wherein the data is in a predetermined state when certain bits in the predetermined number of coefficients, parents of those coefficients or northern neighbor coefficients of the predetermined number of coefficients comprise all zero head bits.

83. The method defined in claim 79 wherein the coding of each coefficient independently comprises:

decoding head bits of each coefficient until a first 1 bit occurs;

coding a sign bit of said each coefficient when the first 1 bit occurs; and

coding tail bits of said each coefficient thereafter.

84. The method defined in claim 79 further comprising coding bit planes of individual frequency bands in a child-based order.

85. The method defined in claim 79 wherein bits in each importance level are coded in frequency band order.

86. The method defined in claim 79 wherein the second context model is based on neighboring coefficients in the same frequency band and a parent coefficient.

79. A method for processing data comprising the steps of:

determining whether to attempt to code a predetermined number of coefficients as a group;

coding the predetermined number of coefficients individually using a first context model if not attempting to code the predetermined number of coefficients as a group;

first coding the predetermined number of coefficients when the data is in a predetermined state and attempting to code the predetermined number of coefficients as a group is successful; and

second coding each coefficient in the predetermined number of coefficients independently when the data is not in the predetermined state and attempting to code the predetermined number of coefficients as a group fails, wherein second coding uses a second context model different than the first context model.