US 5,689,255 AGranted

Method and apparatus for compressing and decompressing image data

AssigneeHewlett-Packard Company

InventorsAllen L. Frazier, Brent M. Bradburn

Life of this patent

Estimating the term…

Loading patent…

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.

Claims8

Dependent claims

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.

7 more elements

Dependencies are inferred from the claim text.