US5682152A
Expired / Lapsed
US
⏱️ 0.0 years remaining
Data compression using adaptive bit allocation and hybrid lossless entropy encoding
Assignee: Citrix Systems Inc
•
Filing: 1996-03-19
•
Granted: 1997-10-28
•
Expires: 2016-03-19
Abstract
Abstract A method and apparatus for adaptive bit allocation and hybrid lossless entropy encoding in a lossy compression system. The invention includes three components: (1) a transform stage to decorrelate image data into a baseband and multiple subbands, (2) a quantization stage to quantize the resulting transform coefficients, and (3) a lossless entropy coder stage to encode the quantized indexes. In the preferred embodiment, the transform stage uses a wavelet transform algorithm. The quantization stage adaptively estimates values for parameters defining an approximation between quantization size and the logarithm of quantization error, and recursively calculates the optimal quantization size for each band to achieve a desired bit rate. The baseband and subbands are transformed into quantization matrices using the corresponding quantization sizes. The lossless entropy coder stage uses the observation that the entropy property of run lengths of zero index values in the subband quantization matrices is different from the entropy property of non-zero indices. Each quantization matrix is parsed so that each non-zero index is extracted into a separate stream, and the remaining position information is parsed into an odd stream of run length values for "0" and an even stream of run length values for "1". These three streams are Huffman coded separately in conventional fashion. This hybrid algorithm gives an approximately 10% percent improvement over conventional run length and Huffman coding for similar images. The overall compression algorithm gives about 2 DIFFERENCE 6 dB improvement in terms of peak signal-to-noise ratio (PSNR) over JPEG algorithms for similar images at similar bit rates.
Inventors
- 👤 Zhengrong Wang
- 👤 Paul Steven Houle
Bibliographic Details
Application Number
—
Jurisdiction
US
Data Source
google_patents
Last Synchronized
2026-11-01 06:36
CPC Classifications
H; H03; H03M; H03M7/00; H03M7/30; H03M7/46; H04; H04N; H04N19/00; H04N19/10; H04N19/102; H04N19/117; H04N19/124; H04N19/126; H04N19/134; H04N19/136; H04N19/14; H04N19/146; H04N19/152; H04N19/169; H04N19/17; H04N19/172; H04N19/176; H04N19/186; H04N19/189; H04N19/192; H04N19/60; H04N19/61; H04N19/63; H04N19/115; H04N19/13
Claims Analysis
Total Claims: 24
Claim 1
Independent Claim
128 words
A hybrid lossless entropy coding method for compressing data comprising a matrix including a plurality of zero indices and non-zero indices, the method including the steps of: (a) replacing each non-zero index in the matrix by a unique token, thereby generating a parsed matrix including a plurality of zero indices and token indices; (b) placing each non-zero index from the matrix into a first data stream; (c) run length coding the parsed matrix into alternating run length codes for the zero indices and unique token indices; (d) placing the even run length codes into a second data stream; (e) placing the odd run length codes into a third data stream; and (f) coding each of the first, second, and third data streams with a lossless entropy coding algorithm.
Claim 2
Dependent Claim
128 words
A hybrid lossless entropy coding method for compressing data comprising a matrix including a plurality of zero indices and non-zero indices, the method including the steps of: (a) replacing each non-zero index in the matrix by a unique token, thereby generating a parsed matrix including a plurality of zero indices and token indices; (b) placing each non-zero index from the matrix into a first data stream; (c) run length coding the parsed matrix into alternating run length codes for the zero indices and unique token indices; (d) placing the even run length codes into a second data stream; (e) placing the odd run length codes into a third data stream; and (f) coding each of the first, second, and third data streams with a lossless entropy coding algorithm.
Claim 3
Dependent Claim
199 words
A hybrid lossless entropy coding method for compressing data, the method being implemented in a programmed computer comprising a processor, a data storage system, and at least one output device, the method including the steps of: (a) storing data in the data storage system of the programmed computer, the data comprising a matrix including a plurality of zero indices and non-zero indices; (b) replacing each non-zero index in the matrix by a unique token using the processor, thereby generating a parsed matrix including a plurality of zero indices and token indices; (c) placing each non-zero index from the matrix into a first data stream using the processor; (d) run length coding the parsed matrix using the processor into alternating run length codes for the zero indices and unique token indices; (e) placing the even run length codes into a second data stream using the processor; (f) placing the odd run length codes into a third data stream using the processor; (g) coding each of the first, second, and third data streams with a lossless entropy coding algorithm using the processor to thereby generate output information; and (h) applying the output information to at least one of the output devices.
Claim 4
Dependent Claim
199 words
A hybrid lossless entropy coding method for compressing data, the method being implemented in a programmed computer comprising a processor, a data storage system, and at least one output device, the method including the steps of: (a) storing data in the data storage system of the programmed computer, the data comprising a matrix including a plurality of zero indices and non-zero indices; (b) replacing each non-zero index in the matrix by a unique token using the processor, thereby generating a parsed matrix including a plurality of zero indices and token indices; (c) placing each non-zero index from the matrix into a first data stream using the processor; (d) run length coding the parsed matrix using the processor into alternating run length codes for the zero indices and unique token indices; (e) placing the even run length codes into a second data stream using the processor; (f) placing the odd run length codes into a third data stream using the processor; (g) coding each of the first, second, and third data streams with a lossless entropy coding algorithm using the processor to thereby generate output information; and (h) applying the output information to at least one of the output devices.
Claim 5
Independent Claim
13 words
The method of claims 1 or 2, wherein the unique token is "1".
Claim 6
Independent Claim
16 words
The method of claims 1 or 2, wherein the lossless entropy coding algorithm is Huffman coding.
Claim 7
Independent Claim
16 words
The method of claims 1 or 2, wherein the lossless entropy coding algorithm is arithmetic coding.
Claim 8
Independent Claim
25 words
The method of claims 1 or 2, wherein the matrix comprises quantization indices derived from an image by a lossy data compression and quantization system.
Claim 9
Dependent Claim
160 words
A computer program for compressing data using a hybrid lossless entropy coding algorithm, the data comprising a matrix including a plurality of zero indices and non-zero indices, the computer program being stored on a media readable by a computer system, for configuring the computer system upon being read and executed by the computer system to perform the functions of: (a) replacing each non-zero index in the matrix by a unique token, thereby generating a parsed matrix including a plurality of zero indices and token indices; (b) placing each non-zero index from the matrix into a first data stream; (c) run length coding the parsed matrix into alternating run length codes for the zero indices and unique token indices; (d) placing the even run length codes into a second data stream; (e) placing the odd run length codes into a third data stream; and (f) coding each of the first, second, and third data streams with a lossless entropy coding algorithm.
Claim 10
Dependent Claim
160 words
A computer program for compressing data using a hybrid lossless entropy coding algorithm, the data comprising a matrix including a plurality of zero indices and non-zero indices, the computer program being stored on a media readable by a computer system, for configuring the computer system upon being read and executed by the computer system to perform the functions of: (a) replacing each non-zero index in the matrix by a unique token, thereby generating a parsed matrix including a plurality of zero indices and token indices; (b) placing each non-zero index from the matrix into a first data stream; (c) run length coding the parsed matrix into alternating run length codes for the zero indices and unique token indices; (d) placing the even run length codes into a second data stream; (e) placing the odd run length codes into a third data stream; and (f) coding each of the first, second, and third data streams with a lossless entropy coding algorithm.
Claim 11
Dependent Claim
156 words
A computer-readable storage medium, configured with a computer program for compressing data using a hybrid lossless entropy coding algorithm, the data comprising a matrix including a plurality of zero indices and non-zero indices, where the storage medium so configured causes a computer to operate in a specific and predefined manner to perform the functions of: (a) replacing each non-zero index in the matrix by a unique token, thereby generating a parsed matrix including a plurality of zero indices and token indices; (b) placing each non-zero index from the matrix into a first data stream; (c) run length coding the parsed matrix into alternating run length codes for the zero indices and unique token indices; (d) placing the even run length codes into a second data stream; (e) placing the odd run length codes into a third data stream; and (f) coding each of the first, second, and third data streams with a lossless entropy coding algorithm.
Claim 12
Dependent Claim
156 words
A computer-readable storage medium, configured with a computer program for compressing data using a hybrid lossless entropy coding algorithm, the data comprising a matrix including a plurality of zero indices and non-zero indices, where the storage medium so configured causes a computer to operate in a specific and predefined manner to perform the functions of: (a) replacing each non-zero index in the matrix by a unique token, thereby generating a parsed matrix including a plurality of zero indices and token indices; (b) placing each non-zero index from the matrix into a first data stream; (c) run length coding the parsed matrix into alternating run length codes for the zero indices and unique token indices; (d) placing the even run length codes into a second data stream; (e) placing the odd run length codes into a third data stream; and (f) coding each of the first, second, and third data streams with a lossless entropy coding algorithm.
Claim 13
Dependent Claim
13 words
The invention of claims 7 or 8, wherein the unique token is "1".
Claim 14
Dependent Claim
16 words
The invention of claims 7 or 8, wherein the lossless entropy coding algorithm is Huffman coding.
Claim 15
Dependent Claim
16 words
The invention of claims 7 or 8, wherein the lossless entropy coding algorithm is arithmetic coding.
Claim 16
Dependent Claim
25 words
The invention of claims 7 or 8, wherein the matrix comprises quantization indices derived from an image by a lossy data compression and quantization system.
Claim 17
Independent Claim
127 words
A method for compressing image data, comprising the steps of: (a) storing an image in a computer as image data; (b) applying a transform algorithm to decorrelate the image data into a baseband and multiple subbands; (c) generating quantization coefficients by the steps of: (1) adaptively estimating values for parameters defining an approximation between quantization size and the logarithm of quantization error for each such band; (2) recursively calculating an optimal quantization size for each of the baseband and multiple subbands to achieve a desired bit rate; (d) applying the quantization coefficients to the baseband and multiple subbands to generate corresponding quantization matrices each comprising a plurality of zero indices and non-zero indices; (e) applying a hybrid lossless entropy coding algorithm to losslessly compress each quantization matrix.
Claim 18
Independent Claim
127 words
A method for compressing image data, comprising the steps of: (a) storing an image in a computer as image data; (b) applying a transform algorithm to decorrelate the image data into a baseband and multiple subbands; (c) generating quantization coefficients by the steps of: (1) adaptively estimating values for parameters defining an approximation between quantization size and the logarithm of quantization error for each such band; (2) recursively calculating an optimal quantization size for each of the baseband and multiple subbands to achieve a desired bit rate; (d) applying the quantization coefficients to the baseband and multiple subbands to generate corresponding quantization matrices each comprising a plurality of zero indices and non-zero indices; (e) applying a hybrid lossless entropy coding algorithm to losslessly compress each quantization matrix.
Claim 19
Dependent Claim
156 words
A computer program for compressing image data, the computer program being stored on a media readable by a computer system, for configuring the computer system upon being read and executed by the computer system to perform the functions of: (a) storing an image in a computer as image data; (b) applying a transform algorithm to decorrelate the image data into a baseband and multiple subbands; (c) generating quantization coefficients by the steps of: (1) adaptively estimating values for parameters defining an approximation between quantization size and the logarithm of quantization error for each such band; (2) recursively calculating an optimal quantization size for each of the baseband and multiple subbands to achieve a desired bit rate; (d) applying the quantization coefficients to the baseband and multiple subbands to generate corresponding quantization matrices each comprising a plurality of zero indices and non-zero indices; (e) applying a hybrid lossless entropy coding algorithm to losslessly compress each quantization matrix.
Claim 20
Dependent Claim
156 words
A computer program for compressing image data, the computer program being stored on a media readable by a computer system, for configuring the computer system upon being read and executed by the computer system to perform the functions of: (a) storing an image in a computer as image data; (b) applying a transform algorithm to decorrelate the image data into a baseband and multiple subbands; (c) generating quantization coefficients by the steps of: (1) adaptively estimating values for parameters defining an approximation between quantization size and the logarithm of quantization error for each such band; (2) recursively calculating an optimal quantization size for each of the baseband and multiple subbands to achieve a desired bit rate; (d) applying the quantization coefficients to the baseband and multiple subbands to generate corresponding quantization matrices each comprising a plurality of zero indices and non-zero indices; (e) applying a hybrid lossless entropy coding algorithm to losslessly compress each quantization matrix.
Claim 21
Independent Claim
292 words
A method for compressing image data, comprising the steps of: (a) storing an image in a computer as image data; (b) applying a transform algorithm to decorrelate the image data into a baseband and multiple subbands; (c) generating quantization coefficients by the steps of: (1) estimating values for parameters defining an approximation between quantization size and the logarithm of quantization error for each subband; (2) estimating values for parameters defining an approximation between quantization size and the logarithm of quantization error for the baseband; (3) calculating an optimal bit rate R k for each of the baseband and subbands; (4) marking each subband k and excluding it from the subbands if R k <0 for such subband k, and then looping to step (3); (5) calculating a quantization size Q k for each of the baseband and subbands as: ##EQU13## (d) applying each quantization size Q k to corresponding ones of the baseband and multiple subbands to generate corresponding quantization matrices each comprising a plurality of zero indices and non-zero indices; (e) applying a hybrid lossless entropy coding algorithm to losslessly compress each quantization matrix by the steps of: (1) replacing each non-zero index in the quantization matrix by a unique token, thereby generating a parsed matrix including a plurality of zero indices and token indices; (2) placing each non-zero index from the quantization matrix into a first data stream; (3) run length coding the parsed matrix into alternating run length codes for the zero indices and unique token indices; (4) placing the even run length codes into a second data stream; (5) placing the odd run length codes into a third data stream; and (6) coding each of the first, second, and third data streams with a lossless entropy coding algorithm.
Claim 22
Independent Claim
292 words
A method for compressing image data, comprising the steps of: (a) storing an image in a computer as image data; (b) applying a transform algorithm to decorrelate the image data into a baseband and multiple subbands; (c) generating quantization coefficients by the steps of: (1) estimating values for parameters defining an approximation between quantization size and the logarithm of quantization error for each subband; (2) estimating values for parameters defining an approximation between quantization size and the logarithm of quantization error for the baseband; (3) calculating an optimal bit rate R k for each of the baseband and subbands; (4) marking each subband k and excluding it from the subbands if R k <0 for such subband k, and then looping to step (3); (5) calculating a quantization size Q k for each of the baseband and subbands as: ##EQU13## (d) applying each quantization size Q k to corresponding ones of the baseband and multiple subbands to generate corresponding quantization matrices each comprising a plurality of zero indices and non-zero indices; (e) applying a hybrid lossless entropy coding algorithm to losslessly compress each quantization matrix by the steps of: (1) replacing each non-zero index in the quantization matrix by a unique token, thereby generating a parsed matrix including a plurality of zero indices and token indices; (2) placing each non-zero index from the quantization matrix into a first data stream; (3) run length coding the parsed matrix into alternating run length codes for the zero indices and unique token indices; (4) placing the even run length codes into a second data stream; (5) placing the odd run length codes into a third data stream; and (6) coding each of the first, second, and third data streams with a lossless entropy coding algorithm.
Claim 23
Dependent Claim
324 words
A computer program for compressing image data, the computer program being stored on a media readable by a computer system, for configuring the computer system upon being read and executed by the computer system to perform the functions of: (a) storing an image in a computer as image data; (b) applying a transform algorithm to decorrelate the image data into a baseband and multiple subbands; (c) generating quantization coefficients by the steps of: (1) estimating values for parameters defining an approximation between quantization size and and the logarithm of quantization error quantization error for each subband; (2) estimating values for parameters defining an approximation between quantization size and the logarithm of quantization error for the baseband; (3) calculating an optimal bit rate R k for each of the baseband and subbands; (4) marking each subband k and excluding it from the subbands if R k <0 for such subband k, and then looping to step (3); (5) calculating a quantization size Q k for each of the baseband and subbands as: ##EQU14## (d) applying each quantization size Q k to corresponding ones of the baseband and multiple subbands to generate corresponding quantization matrices each comprising a plurality of zero indices and non-zero indices; (e) applying a hybrid lossless entropy coding algorithm to losslessly compress each quantization matrix by the steps of: (1) replacing each non-zero index in the quantization matrix by a unique token, thereby generating a parsed matrix including a plurality of zero indices and token indices; (2) placing each non-zero index from the quantization matrix into a first data stream; (3) run length coding the parsed matrix into alternating run length codes for the zero indices and unique token indices; (4) placing the even run length codes into a second data stream; (5) placing the odd run length codes into a third data stream; and (6) coding each of the first, second, and third data streams with a lossless entropy coding algorithm.
Claim 24
Dependent Claim
324 words
A computer program for compressing image data, the computer program being stored on a media readable by a computer system, for configuring the computer system upon being read and executed by the computer system to perform the functions of: (a) storing an image in a computer as image data; (b) applying a transform algorithm to decorrelate the image data into a baseband and multiple subbands; (c) generating quantization coefficients by the steps of: (1) estimating values for parameters defining an approximation between quantization size and and the logarithm of quantization error quantization error for each subband; (2) estimating values for parameters defining an approximation between quantization size and the logarithm of quantization error for the baseband; (3) calculating an optimal bit rate R k for each of the baseband and subbands; (4) marking each subband k and excluding it from the subbands if R k <0 for such subband k, and then looping to step (3); (5) calculating a quantization size Q k for each of the baseband and subbands as: ##EQU14## (d) applying each quantization size Q k to corresponding ones of the baseband and multiple subbands to generate corresponding quantization matrices each comprising a plurality of zero indices and non-zero indices; (e) applying a hybrid lossless entropy coding algorithm to losslessly compress each quantization matrix by the steps of: (1) replacing each non-zero index in the quantization matrix by a unique token, thereby generating a parsed matrix including a plurality of zero indices and token indices; (2) placing each non-zero index from the quantization matrix into a first data stream; (3) run length coding the parsed matrix into alternating run length codes for the zero indices and unique token indices; (4) placing the even run length codes into a second data stream; (5) placing the odd run length codes into a third data stream; and (6) coding each of the first, second, and third data streams with a lossless entropy coding algorithm.
References Cited (Backward Citations)
USPTO Annuity & Maintenance Windows
| Annuity Stage | Window Opens | Payment Deadline | Surcharge Period Until | Estimated Fee | Status |
|---|---|---|---|---|---|
| 3.5 Years (Year 4) | 2000-10-27 | 2001-04-28 | 2001-10-28 | $2000.00 | Window Closed / Lapsed |
| 7.5 Years (Year 8) | 2004-10-27 | 2005-04-28 | 2005-10-28 | $3760.00 | Window Closed / Lapsed |
| 11.5 Years (Year 12) | 2008-10-27 | 2009-04-28 | 2009-10-28 | $7700.00 | Window Closed / Lapsed |