Method and apparatus for compression using reversible wavelet transforms and an embedded codestream
First Claim
Patent Images
1. An encoder for encoding input data into a compressed data stream, said entropy coder comprising:
- a reversible wavelet filter transforming the input data into a plurality of coefficients;
an ordering and modeling mechanism coupled to the reversible wavelet filter, said ordering and modeling mechanism generating an embedded codestream in response to the plurality of coefficients, wherein the ordering and modeling mechanism orders the plurality of coefficients and orders binary values within the plurality of coefficients in order to create the embedded codestream; and
an entropy coder, coupled to the ordering and modeling mechanism, operable to entropy code the embedded codestream to produce the compressed data stream.
1 Assignment
0 Petitions
Accused Products
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.
289 Citations
61 Claims
-
1. An encoder for encoding input data into a compressed data stream, said entropy coder comprising:
-
a reversible wavelet filter transforming the input data into a plurality of coefficients;
an ordering and modeling mechanism coupled to the reversible wavelet filter, said ordering and modeling mechanism generating an embedded codestream in response to the plurality of coefficients, wherein the ordering and modeling mechanism orders the plurality of coefficients and orders binary values within the plurality of coefficients in order to create the embedded codestream; and
an entropy coder, coupled to the ordering and modeling mechanism, operable to entropy code the embedded codestream to produce the compressed data stream. - View Dependent Claims (2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18)
-
-
19. An encoder for encoding input data into a compressed data stream, said entropy coder comprising:
-
a reversible wavelet filter transforming the input data into a plurality of coefficients;
an ordering and modeling mechanism coupled to the reversible wavelet filter, said ordering and modeling mechanism generating an embedded codestream in response to the plurality of coefficients, wherein the ordering and modeling mechanism models bits within a coding unit based on spatial and spectral dependencies of coefficients; and
an entropy coder, coupled to the ordering and modeling mechanism, operable to entropy code the embedded codestream to produce the compressed data stream, wherein the entropy coder performs coding based on the bits modeled by the ordering and modeling mechanism. - View Dependent Claims (20, 21)
-
-
22. An encoder for encoding input data into a compressed data stream, said entropy coder comprising:
-
a reversible wavelet filter transforming the input data into a plurality of coefficients;
and ordering and modeling mechanism coupled to the reversible wavelet filter, said ordering and modeling mechanism performing embedded quantization on the plurality of coefficients to generate an embedded codestream in response to the plurality of coefficients, wherein the ordering and modeling mechanism comprises a context model using contexts based on neighboring and parent coefficient values, and wherein the contexts are based on whether a first non-zero magnitude bit has been observed and the number of bit-planes since said first non-zero magnitude bit, if said first non-zero magnitude bit was observed; and
a binary entropy coder, couple to the ordering and modeling mechanism, operable to binary entropy code the embedded codestream to produce the compressed data stream. - View Dependent Claims (23, 24, 25, 26, 27, 28, 29, 30, 31, 32, 33, 34, 35, 36, 37, 38, 39, 40, 41, 42, 43, 44, 45, 46, 47, 48, 49, 50)
(a) said first non-zero magnitude bit occurred at last bit-plane, (b) said first non-zero magnitude bit occurred between two and three bit-planes earlier, or (c) said first non-zero magnitude bit occurred more than three bit-planes earlier.
-
-
38. The encoder defined in claim 22 wherein a sign bit of the present coefficient is encoded immediately after the present bit of the present coefficient is the first non-zero magnitude bit.
-
39. The encoder defined in claim 22 wherein a context for coding a sign bit when the sign of the coefficient immediately north is not known comprises a fixed probability.
-
40. The encoder defined in claim 39 wherein the fixed probability comprises approximately 0.5.
-
41. The encoder defined in claim 22 wherein contexts for coding binary values after the first non-zero magnitude bit comprise fixed probabilities.
-
42. The encoder defined in claim 41 wherein a context for coding a first binary value after the first non-zero bit comprises a fixed probability of approximately 0.7.
-
43. The encoder defined in claim 22 wherein a context for coding second and third binary values after the first non-zero bit comprises a fixed probability of approximately 0.6.
-
44. The encoder defined in claim 22 wherein a context for coding fourth and subsequent binary values after the first non-zero bit is coded at a fixed probability of 0.5.
-
45. The encoder defined in claim 22 wherein the entropy coder comprises a Q-coder.
-
46. The encoder defined in claim 22 wherein the entropy coder comprises a QM-coder.
-
47. The encoder defined in claim 22 wherein the entropy coder comprises a finite state machine coder.
-
48. The encoder defined in claim 22 wherein the entropy coder comprises a parallel coder.
-
49. The encoder defined in claim 22 wherein if said first non-zero magnitude bit has not been observed, then the context model uses contexts to condition a coefficient that includes information corresponding to a parent of the coefficient.
-
50. The encoder defined in claim 22 wherein if said first non-zero magnitude bit has not been observed, then the context model uses contexts to condition a coefficient that includes information from at least one coefficient positioned NW, N, NE, W, E, SW, S or SE of the coefficient.
-
51. A method of encoding input data into a compressed data stream comprising:
-
transforming the input data into a plurality of coefficients using a reversible wavelet filter;
generating an embedded codestream in response to the plurality of coefficients, wherein generating the embedded codestream comprises the steps of ordering the plurality of coefficients and ordering binary values within the plurality of coefficients in order to create the embedded codestream; and
entropy coding the embedded codestream to produce the compressed data stream. - View Dependent Claims (52, 53, 54, 55, 56)
-
-
57. A method of decoding an encoding data stream comprising:
-
retrieving coded data for a coding unit;
modeling a bit of each coefficient with a context model and an entropy decoder, reordering coefficients based on spatial and spectral dependencies of coefficients; and
applying an inverse wavelet filter on the coefficients starting with the coarsest level. - View Dependent Claims (58, 59)
-
-
60. A decoder for decoding encoded data comprising:
-
an entropy decoder for entropy decoding the encoded data into a codestream of coefficients;
a reordering mechansim to reorder coefficients within a coding unit based on spatial and spectral dependencies of coefficients to create a reordered codestream; and
an inverse reversible wavelet filter coupled to the reordering mechanism for transforming the reordered codestream of coefficients into reconstructed data. - View Dependent Claims (61)
-
Specification