US6166664A
Expired / Lapsed
US
⏱️ 0.0 years remaining
Efficient data structure for entropy encoding used in a DWT-based high performance image compression
Assignee: Intel Corp
•
Filing: 1998-08-26
•
Granted: 2000-12-26
•
Expires: 2018-08-26
Abstract
Abstract What is disclosed is a method that allows a fixed length (L) codeword and flag to serve as a structure for encoding large run of identical values, a single bit capable of representing 2 L such values. The zero non coding method may be utilized to efficiently encode data sets, such as images or other data files with large consecutive runs of a particular value such as zero. In an entropy encoding scheme, such enhanced zero run coding may be combined with variable length coding for non-zero values.
Inventors
- 👤 Tinku Acharya
Bibliographic Details
Application Number
—
Jurisdiction
US
Data Source
google_patents
Last Synchronized
2026-11-09 22:10
CPC Classifications
H; H03; H03M; H03M7/00; H03M7/30; H03M7/40; H03M7/4006; H04; H04N; H04N19/00; H04N19/10; H04N19/169; H04N19/1883; H04N19/60; H04N19/63; H04N19/90; H04N19/91; H04N19/102; H04N19/124
Claims Analysis
Total Claims: 20
Claim 1
Independent Claim
85 words
A method of run-length encoding comprising: determining a number of bits L utilized to store a word R, said word R accompanied by a flag, said flag and word R comprising a structure; and encoding the length of a run of similar data values, said length larger than allowable by said L bits of the word R even if each of said L bits were fully utilized, said encoding achieved by utilizing a single bit to represent 2 L similar data values in the run.
Claim 2
Independent Claim
85 words
A method of run-length encoding comprising: determining a number of bits L utilized to store a word R, said word R accompanied by a flag, said flag and word R comprising a structure; and encoding the length of a run of similar data values, said length larger than allowable by said L bits of the word R even if each of said L bits were fully utilized, said encoding achieved by utilizing a single bit to represent 2 L similar data values in the run.
Claim 3
Dependent Claim
24 words
The method according to claim 1, wherein said run refers to the number of zeroes between two non-zero values in a set of data.
Claim 4
Dependent Claim
17 words
The method according to claim 2, wherein said non-zero values are encoded using a variable length code.
Claim 5
Dependent Claim
21 words
The method according to claim 2, wherein said set of data is sub-band data obtained from a Discrete Wavelet Transform (DWT).
Claim 6
Dependent Claim
28 words
The method according to claim 3, wherein said non-zero values are used to address a look-up table and derive therefrom the Huffman code corresponding to said non-zero values.
Claim 7
Dependent Claim
26 words
The method according to claim 4, wherein each sub-band of data is assigned a separate value of L concordat with the entropy properties of that sub-band.
Claim 8
Dependent Claim
18 words
The method according to claim 6, wherein said set of sub-band data is quantized prior to being encoded.
Claim 9
Dependent Claim
49 words
The method according to claim 2, wherein the encoding includes: specifying a structure with a flag of 1 indicating that the corresponding word R in said structure with a flag of 1 forms a portion of the length of the run, said portion smaller than 2 L in length.
Claim 10
Dependent Claim
36 words
The method according to claim 8, wherein a structure with a flag of 1 and a word R having L bits of zeroes indicates that a variable length code of a non-zero value is to follow.
Claim 11
Dependent Claim
70 words
The method according to claim 4, wherein encoding comprises: setting a counter to count in L bits, and resetting said counter to have L zeroes; fetching a data value; and determining if said fetched data value is a zero or non-zero value, if said fetched data value is a zero then performing a first sub-procedure, and if said fetched data value is a non-zero value, then performing a second sub-procedure.
Claim 12
Dependent Claim
34 words
The method according to claim 10, wherein said first sub-procedure includes: incrementing said counter; and determining whether a counter overflow has occurred, and if so outputting a single zero to encode 2 L zeroes.
Claim 13
Dependent Claim
104 words
A machine-readable medium having stored thereon data representing sequences of instructions, said sequences of instructions which, when executed by a processor, cause said processor to: determine a number of bits L utilized to store a word R, said word R accompanied by a flag, said flag and word R comprising a structure; and encode the length of a run of similar data values, said length larger than allowable by said L bits of the word R even if each of said L bits were fully utilized, said encoding achieved by utilizing a single bit to represent 2 L similar data values in the run.
Claim 14
Dependent Claim
104 words
A machine-readable medium having stored thereon data representing sequences of instructions, said sequences of instructions which, when executed by a processor, cause said processor to: determine a number of bits L utilized to store a word R, said word R accompanied by a flag, said flag and word R comprising a structure; and encode the length of a run of similar data values, said length larger than allowable by said L bits of the word R even if each of said L bits were fully utilized, said encoding achieved by utilizing a single bit to represent 2 L similar data values in the run.
Claim 15
Dependent Claim
105 words
An imaging system comprising: an encoder, said encoder configured to binary encode a data set of zero and non-zero values, said zero values encoded by determining a number of bits L utilized to store a word R, said word R accompanied by a flag, said flag and word R comprising a structure, and then encoding the length of a run of similar data values, said length larger than allowable by said L bits of the word R even if each of said L bits were fully utilized, said encoding achieved by utilizing a single bit to represent 2 L similar data values in the run.
Claim 16
Dependent Claim
105 words
An imaging system comprising: an encoder, said encoder configured to binary encode a data set of zero and non-zero values, said zero values encoded by determining a number of bits L utilized to store a word R, said word R accompanied by a flag, said flag and word R comprising a structure, and then encoding the length of a run of similar data values, said length larger than allowable by said L bits of the word R even if each of said L bits were fully utilized, said encoding achieved by utilizing a single bit to represent 2 L similar data values in the run.
Claim 17
Dependent Claim
31 words
The imaging system according to claim 13, further comprising a compressor coupled to said encoder, said encoder configured to receive said data values as compressed image data output by said compressor.
Claim 18
Dependent Claim
27 words
The imaging system according to claim 13, comprising: a storage array coupled to said encoder, said storage array configured to store the encoded output of said encoder.
Claim 19
Dependent Claim
20 words
The imaging system according to claim 14, comprising a digital camera, said digital camera incorporating said encoder and said compressor.
Claim 20
Dependent Claim
37 words
The imaging system according to claim 16, further comprising: a computer system coupled to said encoder configured to decode said encoded data, said computer system further configured to decompress said decoded data and display an image therefrom.
References Cited (Backward Citations)
US5845243A
Cited
US6023296A
Cited
USPTO Annuity & Maintenance Windows
| Annuity Stage | Window Opens | Payment Deadline | Surcharge Period Until | Estimated Fee | Status |
|---|---|---|---|---|---|
| 3.5 Years (Year 4) | 2003-12-26 | 2004-06-26 | 2004-12-26 | $2000.00 | Window Closed / Lapsed |
| 7.5 Years (Year 8) | 2007-12-26 | 2008-06-26 | 2008-12-26 | $3760.00 | Window Closed / Lapsed |
| 11.5 Years (Year 12) | 2011-12-26 | 2012-06-26 | 2012-12-26 | $7700.00 | Window Closed / Lapsed |