WO1997009665B1

WO1997009665B1 - Method and apparatus for compressing and decompressing image data

Info

Publication number: WO1997009665B1
Application number: PCT/US1996/012719
Authority: WO
Filing date: 1996-08-05
Publication date: 1997-08-28

Abstract

Image data such as text or half-tone images is compressed and decompressed. A compressor has three phases: a bit-run length phase (32) that counts the length of each run of consecutive identical pixels; a pairs-repetition phase (36) 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 (50). The micro-table (80), which may be used in any application calling for a least recently used (LRU) mechanism, has multiple qualification layers (82, 84, and 86), 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.

Claims

AMENDED CLAIMS

[received by the International Bureau on 21 July 199 (21 07 97), original claims 1-5 cancelled, original claims 26-39 amended, new claims 40-43 added, remaining claims unchanged (7 pages)]

6. A method of updating a least recently used (LRU) stack in which the LRU stack contains elements therein, and a pointer indicates a lowest priority element in the LRU stack, the method comprising the steps of:

(a) demoting elements in the LRU stack by replacing the lowest priority element with a most recently used element; and

(b) advancing the pointer.

7. A method as in claim 6, in which the LRU stack is a dictionary in a dictionary-based data compression process.

8. A method as in claim 7, further comprising the step of:

(c) locating an element within the dictionary by using an element value as a hash table address, in which a value stored at the hash table address indicates where the element resides within the dictionary.

9. A method of updating a least recently used (LRU) stack having a first sub-stack and second sub-stack, each sub-stack containing elements therein, the method comprising the steps of: promoting an element by moving said promoted element from said first sub-stack to said second sub-stack; and demoting an element by moving said demoted element from said second sub-stack to said first sub-stack.

10. A method as in claim 9, where each sub-stack includes a corresponding pointer which indicates a lowest priority element within the sub-stack, the method further comprising the steps of: replacing the lowest priority element with a most recently used element; and incrementing the pointer. 26. 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:

(al ) 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:

(bl ) 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.

27. A method as in claim 26, wherein: the first symbol produced in substep (al) 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. 28. A method as in claim 26. 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:

(cl ) 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.

29. A method as in claim 28, wherein: said dictionary elements within said dictionary are a maximum of 32 in number.

30. A method as in claim 28, wherein the dictionary comprises a stack containing 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:

(dl ) demoting elements in the stack by replacing the lowest priority element with a most recently used element; and

(d2) advancing the pointer.

31. A method as in claim 28, 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:

(el) 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.

32. A method as in claim 28, 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:

(el) 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.

33. A method as in claim 32, 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.

34. A method of decompressing a compressed data stream, the method comprising the steps of:

(a) pairs-rep decompressing said compressed data stream, the pairs-rep decompression step comprising the substeps of:

(al ) identifying a first symbol and a second symbol in the compressed data stream;

(a2) identifying a repeat count in the compressed data stream, said repeat count being associated with the first and second symbols; (a3) generating a first decompressed data stream corresponding to the first and second symbols repeated a number of times according to the repeat count;

(b) bit-run decompressing the first decompressed data stream to produce a second decompressed data stream, said bit-run decompression step comprising the substeps of:

(bl ) generating a first run of consecutive bits, said first run having bits of a first polarity, the number of bits in the first run corresponding to the first symbol;

(b2) generating a second run of consecutive bits, said second run having bits of opposite polarity as the bits in the first run, the number of bits in the second run corresponding to the second symbol.

35. A method as in claim 34 further comprising the step of:

(c) decompressing an input data stream, said input data stream decompression comprising the substeps of:

(c 1 ) identifying an index within the input data stream;

(c2) retrieving a set of values from a dictionary location indicated by the index within a dictionary; and

(c3) replacing the index with said set of values in the input data stream to produce a dictionary output data stream, the dictionary output data stream being used as said compressed data stream.

36. A method as in claim 35, wherein the dictionary comprises a stack containing a plurality of dictionary elements and a pointer indicating a lowest priority element in the stack, and wherein the stack is updated according to the steps of:

(dl) demoting elements in the stack by replacing the lowest priority element with a most recently used element; and

(d2) advancing the pointer.

37. A method as in claim 35, 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: (el ) upon an occurrence of a first dictionary element being detected in the input 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.

38. A method as in claim 35, 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:

(el) when a first dictionary element is located in a lower sub-stack, upon an occurrence of said first dictionary element being detected in said input data stream, promoting said first element by moving said first element from the lower sub-stack to a higher sub-stack; and

39. A method as in cl aim 38 , 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.

40. A method as claim 9, wherein each of the sub-stacks has a top and a bottom, each stack has an associated bottom pointer indicating an element at the bottom of the sub- stack, and wherein said promoting and demoting steps are performed according to a "simple swap" method comprising the substeps of: upon the occurrence of an element match within the first sub-stack, swapping the matched element in the first sub-stack with a lowest priority element within the second sub- stack; and incrementing the second sub-stack's bottom pointer.

41. A method as in claim 9. wherein each of the sub-stacks has a top and a bottom, each stack has an associated bottom pointer indicating an element at the bottom of the sub-stack, and wherein said promoting and demoting steps are performed according to a "move to top" method comprising the substeps of: upon the occurrence of an element match within the first sub-stack, moving the matched element from a first vacated position within the first sub-stack to the bottom of the second sub- stack, thereby displacing a displaced element; moving an element from the bottom of the first sub-stack from a second vacated position to the first vacated position; inserting the displaced element into the second vacated position; incrementing the first sub-stack's bottom pointer; and incrementing the second sub-stack's bottom pointer.

42. The method of claim 9, further comprising the steps of: providing a third sub-stack; promoting elements from the second sub-stack to the third sub-stack; and demoting elements from the third sub-stack to the second sub-stack.

43. The method of claim 42, wherein: the first, second, and third sub-stacks contain 16, 8, and 8 elements, respectively.

STATEMENT UNDER ARTICLE 19

On June 4, 1997, the Applicant filed an Amendment Under Article 34. By that Amendment, claims 26-39 were presented. Claims 26-39 are drawn to a multi-stage data compressor and decompressor especially suited for image data.

Claims 26-33 correspond to claims which have now been allowed in the U.S. case, U.S. Patent Application S N 08/518.031. drawn to a multi-stage data compressor. The claims were allowed in the U.S. case over the O 'Brien and Hauk references. O 'Brien and Hauk are the only references in the international search report listed as being of particular relevance to the claims drawn to the multi-stage data compressor. Claims 33-39 are drawn to a corresponding data decompressor.

Accordingly, it is believed that claims 26-39 contain patentable subject matter over the same art that has been made of record in both the U.S. and PCT cases.