Compression and decompression system with reversible wavelets and lossy reconstruction
First Claim
Patent Images
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.
0 Assignments
0 Petitions
Accused Products
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.
-
Citations
86 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. - View Dependent Claims (2, 3, 4)
-
-
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. - View Dependent Claims (6, 7, 8)
-
-
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. - View Dependent Claims (11, 12, 13, 14)
-
-
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. - View Dependent Claims (16, 17, 18, 19)
-
-
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. - View Dependent Claims (23)
-
-
22. The method defined in 21 further comprising the step of repeating steps a)-f) for each subband.
-
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. - View Dependent Claims (26)
-
-
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. - View Dependent Claims (29)
-
-
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. - View Dependent Claims (31)
-
-
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. - View Dependent Claims (34, 35, 36, 37, 38)
-
-
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. - View Dependent Claims (40, 41, 42, 43, 44)
-
-
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. - View Dependent Claims (47, 48, 49)
-
-
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. - View Dependent Claims (51, 52, 53)
-
-
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. - View Dependent Claims (56, 57)
-
-
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. - View Dependent Claims (59, 60)
-
-
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. - View Dependent Claims (63, 64, 65, 66, 67, 68, 69)
-
-
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. - View Dependent Claims (71, 72, 73, 74, 75)
-
-
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. - View Dependent Claims (77, 78)
-
-
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. - View Dependent Claims (80, 81, 82, 83, 84, 85, 86)
-
Specification