US5689255A
Expired / Lapsed
US
⏱️ 0.0 years remaining
Method and apparatus for compressing and decompressing image data
Assignee: HP Inc
•
Filing: 1995-08-22
•
Granted: 1997-11-18
•
Expires: 2015-08-22
Abstract
Abstract Image data such as text or half-tone images is compressed and decompressed. A compressor has three phases: a bit-run length phase that counts the length of each run of consecutive identical pixels; a pairs-repetition phase that compresses repeated pairs of pixel run values to one copy of the repeated pair and a repeat count; and an optional dictionary-based micro-table encoder. The micro-table, which may be used in any application calling for a least recently used (LRU) mechanism, has multiple qualification layers, with elements within a qualification layer being promoted to the next higher qualification layer upon the occurrence of a table hit for that element, and being demoted to the next lower qualification layer by being bumped by elements promoted up from below. The result is a table that is weighted both by frequency and recency of hits.
Inventors
- 👤 Allen L. Frazier
- 👤 Brent M. Bradburn
Bibliographic Details
Application Number
—
Jurisdiction
US
Data Source
google_patents
Last Synchronized
2026-10-27 06:24
CPC Classifications
G; G06; G06T; G06T1/00; H; H03; H03M; H03M7/00; H03M7/30; H03M7/46; G06T9/00; G06T9/005; H03M7/3084
Claims Analysis
Total Claims: 9
Claim 1
Independent Claim
202 words
A method of compressing a binary input data stream comprised of binary bits, comprising the steps of: (a) bit-run encoding the binary input data stream to produce a first compressed data stream, the bit-run encoding step comprising the substeps of: (a1) replacing a first run comprising a number of consecutive identical bits in the input data stream, with a first symbol representing a number of bits in the first run; and (a2) replacing a second run comprising a number of consecutive identical bits in the input data stream, with a second symbol representing a number of bits in the second run, the second run immediately following the first run within the input data stream, the second run having bits of opposite polarity from the bits in said first run; and (b) pairs-rep compressing the first compressed data stream to produce a second compressed data stream, the pairs-rep compression step comprising the substeps of: (b1) identifying a consecutively repeating pair of symbols in the first compressed data stream; (b2) determining a number of times the pair of symbols consecutively repeats; and (b3) generating a first set of values corresponding to the repeating symbol pair and the number of times the symbol pair repeats.
Claim 2
Independent Claim
202 words
A method of compressing a binary input data stream comprised of binary bits, comprising the steps of: (a) bit-run encoding the binary input data stream to produce a first compressed data stream, the bit-run encoding step comprising the substeps of: (a1) replacing a first run comprising a number of consecutive identical bits in the input data stream, with a first symbol representing a number of bits in the first run; and (a2) replacing a second run comprising a number of consecutive identical bits in the input data stream, with a second symbol representing a number of bits in the second run, the second run immediately following the first run within the input data stream, the second run having bits of opposite polarity from the bits in said first run; and (b) pairs-rep compressing the first compressed data stream to produce a second compressed data stream, the pairs-rep compression step comprising the substeps of: (b1) identifying a consecutively repeating pair of symbols in the first compressed data stream; (b2) determining a number of times the pair of symbols consecutively repeats; and (b3) generating a first set of values corresponding to the repeating symbol pair and the number of times the symbol pair repeats.
Claim 3
Dependent Claim
46 words
A method as in claim 1, wherein: the first symbol produced in substep (a1) does not include an example of the bits within said first run; and the second symbol produced in substep (a2) does not include an example of the bits within said second run.
Claim 4
Dependent Claim
82 words
A method as in claim 1, further comprising the step of: (c) compressing the second compressed data stream using dictionary-based compression to produce a third compressed data stream, the dictionary-based compression step comprising the substeps of: (c1) storing a dictionary element in a location within the dictionary, the dictionary element corresponding to the first set of values; (c2) generating an index corresponding to the location; and (c3) replacing said first set of values in the second compressed data stream with said index.
Claim 5
Dependent Claim
20 words
A method as in claim 3, wherein: said dictionary elements within said dictionary are a maximum of 32 in number.
Claim 6
Dependent Claim
64 words
A method as in claim 3, wherein the dictionary comprises a stack coming a plurality of said dictionary elements and a pointer indicating a lowest priority element in the stack, and wherein the stack is updated according to the steps of: (d1) demoting elements in the stack by replacing the lowest priority element with a most recently used element; and (d2) advancing the pointer.
Claim 7
Dependent Claim
127 words
A method as in claim 3, wherein the dictionary is a multi-tiered stack, the multi-tiered stack comprising a first sub-stack and a second sub-stack, each sub-stack including an identified lowest priority element therein, and wherein the stack is updated according to the steps of: (e1) upon an occurrence of a first dictionary element being detected in said second compressed data stream, promoting said first element by moving said first element from said first sub-stack to said second sub-stack; and (e2) when said first element is the lowest priority element within said second sub-stack, upon the occurrence of a second element being promoted from said first sub-stack to said second sub-stack, demoting said first element by moving said first element from said second sub-stack to said first sub-stack.
Claim 8
Dependent Claim
150 words
A method as in claim 3, wherein the dictionary is a multi-tiered stack, the multi-tiered stack comprising first, second and third sub-stacks; each sub-stack including an identified lowest priority element therein; said first, second and third sub-stacks being defined as from lowest to highest respectively; and wherein the stack is updated according to the steps of: (e1) when a first dictionary element is located in a lower sub-stack, upon an occurrence of said first dictionary element being detected in said second compressed data stream, promoting said first element by moving said first element from the lower sub-stack to a higher sub-stack; and (e2) when said first element is a lowest priority element within a higher sub-stack, upon the occurrence of a second element being promoted from said lower sub-stack to said higher sub-stack, demoting said first element by moving said first element from said higher sub-stack to said lower sub-stack.
Claim 9
Dependent Claim
29 words
A method as in claim 7, wherein: said first sub-stack contains 8 dictionary elements; said second sub-stack contains 8 dictionary elements; and said third sub-stack contains 16 dictionary elements.
References Cited (Backward Citations)
US3726993A
Cited
US3883847A
Cited
US4258392A
Cited
US4464650A
Cited
US4543612A
Cited
US4814746A
Cited
US4558302A
Cited
US4558302B1
Cited
US4586027A
Cited
US4631521A
Cited
US4626829A
Cited
US4872009A
Cited
US4943869A
Cited
US4881075A
Cited
US5282256A
Cited
US5153591A
Cited
US5126739A
Cited
US5146221A
Cited
US5034968A
Cited
US5177622A
Cited
US4988998A
Cited
US5179711A
Cited
US5049880A
Cited
US5049881A
Cited
US5220440A
Cited
US5237460A
Cited
US5245337A
Cited
US5179378A
Cited
US5155484A
Cited
US5229768A
Cited
US5327254A
Cited
US5287420A
Cited
US5239298A
Cited
US5339076A
Cited
USPTO Annuity & Maintenance Windows
| Annuity Stage | Window Opens | Payment Deadline | Surcharge Period Until | Estimated Fee | Status |
|---|---|---|---|---|---|
| 3.5 Years (Year 4) | 2000-11-17 | 2001-05-19 | 2001-11-18 | $2000.00 | Window Closed / Lapsed |
| 7.5 Years (Year 8) | 2004-11-17 | 2005-05-19 | 2005-11-18 | $3760.00 | Window Closed / Lapsed |
| 11.5 Years (Year 12) | 2008-11-17 | 2009-05-19 | 2009-11-18 | $7700.00 | Window Closed / Lapsed |