Runs of adaptive pixel patterns (RAPP) for lossless image compression

• US 6,038,346 A
• Filed: 01/29/1998
• Issued: 03/14/2000
• Est. Priority Date: 01/29/1998
• Status: Expired due to Term

• Current Assignee: Seiko Epson Corporation (Seiko Group)
• Original Assignee: Seiko Epson Corporation (Seiko Group)
• Inventors: Ratnakar, Viresh
• Primary Examiner(s): Lee, Thomas D.
• Assistant Examiner(s): Chen, Wenpeng
• Application Number:
  US09/015,408
• Time in Patent Office: 775 Days
• Field of Search: 382/239, 382/238, 382/240, 382/236, 382/232, 348/415, 348/409, 348/384, 348/420, 348/408, 341/51, 341/107, 341/106, 358/261.2, 358/430
• US Class Current: 382/239
• CPC Class Codes: G06T 9/005 Statistical coding, e.g. Huffman, run length coding
• CPC Class Codes: H04N 1/64 Systems for the transmission or the storage of the colour picture signal; Details therefor, e.g. coding or decoding means therefor H04N19/00 takes precedence

Abstract

A new lossless compression technique is provided that is specifically designed for palettized synthetic images which typically consist of several sharply delineated uniform-color regions with overlaid text and symbols. The associated algorithm uses patterns of previously-coded neighboring pixels to predict and code each pixel. Preferably, the four immediate and previously-coded neighbors of the current pixel are used. That is, the pixel immediately to the left (or west), the pixel immediately above and diagonally to the left (or northwest), the pixel immediately above (or north), and the pixel immediately above and diagonally to the right (or northeast). The basic pattern determined by the neighboring pixels is augmented by incorporating the number of times the value of each of the neighboring pixels is repeated in the corresponding direction. The prediction rules for different patterns are learned and updated from the image itself during the coding and decoding processes.

Claims

1. A method of coding a pixel in a digitized image, comprising the steps of:

determining an augmented pattern of said pixel based on a plurality of previously-coded neighboring pixels, each having a value, wherein the augmented pattern comprises a basic pattern which assigns a label to each previously-coded neighboring pixel, and a character for each previously-coded neighboring pixel that represents the number of times the value of that previously-coded neighboring pixel is repeated in a particular direction;

determining a probability for each label of the basic pattern;

predicting a label of said pixel based on a comparison of the determined probability for each label;

determining the actual label of said pixel; and

coding said pixel based on the predicted label and the determined actual label of said pixel.

2. The method as recited in claim 1, wherein the labels of the basic pattern identify which of the previously-coded neighboring pixels are identical.

3. The method as recited in claim 1, further comprising the step of:

producing one of a plurality of symbols to indicate that one of a plurality of conditions has been satisfied.

4. The method as recited in claim 3, wherein said producing stop comprises producing a first symbol, if the predicted label is the same as the determined actual label.

5. The method as recited in claim 4, wherein said producing step comprises producing a second symbol indicating which of the previously-coded neighboring pixels has the same value as said pixel, if the predicted label is not the same as the determined actual label and if at least one of the previously-coded neighboring pixels is determined to have the same value as said pixel.

6. The method as recited in claim 5, wherein said producing step comprises producing a third symbol indicating prediction failure, if the predicted label is not the same as the determined actual label and if the value of said pixel is determined not to be the same as the value of any of the previously-coded neighboring pixels.

7. The method as recited in claim 1, further comprising the steps of:

producing a first symbol, if the predicted label is the same as the determined actual label.

determining whether a value of said pixel is the same as the value of at least one of the previously-coded neighboring pixels, if the predicted label is not the same as the determined actual label;

producing a second symbol indicating which of the previously-coded neighboring pixels has the same value as said pixel, if the predicted label is not the same as the determined actual label and if the value of said pixel is determined to be the same as the value of at least one of the previously-coded neighboring pixels; and

producing a third symbol indicating prediction failure, if the predicted label is not the same as the determined actual label and if the value of said pixel is determined not to be the same as the value of at least one of the previously-coded neighboring pixels.

8. The method as recited in claim 1, wherein the plurality of previously-coded neighboring pixels comprise at least a first pixel located to the west of said pixel and a second pixel located to the northwest of said pixel.

9. The method as recited in claim 8, wherein the plurality of previously-coded neighboring pixels further comprise a third pixel located to the north of said pixel and a fourth pixel located to the northeast of said pixel.

10. The method as recited in claim 7, wherein a plurality of pixels in the digitized image are coded to compress the digitized image, and wherein said coding step comprises entropy-coding the produced symbols to obtain the compressed image.

11. The method as recited in claim 10, wherein said produced symbols are entropy-coded using arithmetic coding.

12. The method as recited in claim 10, wherein said produced symbols are entropy-coded using Huffman coding.

13. The method as recited in claim 10, further comprising the step of:

updating the probability for the label that would have correctly predicted said pixel in the augmented pattern.

14. An encoder for coding a plurality of pixels in a digitized image, comprising:

means for applying a transform to the digitized image to determine an augmented pattern of each pixel based on a plurality of previously-coded neighboring pixels, each having a value, wherein the augmented pattern comprises a basic pattern which assigns a label to each previously-coded neighboring pixel, and a character for each previously-coded neighboring pixel that represents the number of times the value of that previously-coded neighboring pixel is repeated in a particular direction;

wherein said transform applying means determines, for each augmented pattern, a probability for each label of the basic pattern, predicts a label of each pixel based on a comparison of the determined probability for each label and determines the actual label of each pixel; and

means for coding each pixel based on the predicted label and the determined actual label of that pixel.

15. The encoder as recited in claim 14, wherein said transform applying means determines an augmented pattern of each pixel based on a plurality of previously-coded neighboring pixels comprising first, second, third and fourth pixels, the augmented pattern comprising a basic pattern that includes first, second, third and fourth labels, one for each of said first, second, third and fourth previously-coded neighboring pixels respectively, and a first character indicative of the number of times the value of said first pixel is repeated in a first direction, a second character indicative of the number of times the value of said second pixel is repeated in a second direction, a third character indicative of the number of times the value of said third pixel is repeated in a third direction and a fourth character indicative of the number of times the value of said fourth pixel is repeated in a fourth direction.

16. The encoder as recited in claim 14, wherein said transform applying means determines, for each augmented pattern, a probability for each label of the basic pattern based on a number of times that label would have been a successful predictor for that augmented pattern at any point in the coding of the plurality of pixels.

17. The encoder as recited in claim 14, wherein, for each augmented pattern, said transform applying means updates the probability for the label that would have correctly predicted the pixel associated with that augmented pattern.

18. The encoder as recited in claim 14, further comprising:

means for producing one of a plurality of symbols for each augmented pattern to indicate that one of a plurality of conditions has been satisfied.

19. The encoder as recited in claim 18, wherein said plurality of conditions comprise a first condition which is satisfied if the predicted label is the same as the determined actual label of the pixel associated with that augmented pattern, a second condition which is satisfied if the predicted label is not the same as the determined actual label of the pixel associated with that augmented pattern and the value of the associated pixel is the same as the value of at least one of the previously-coded pixels for that augmented pattern, and a third condition which is satisfied if the predicted label is not the same as the determined actual label of the pixel associated with that augmented pattern and the value of the associated pixel is not the same as the value of at least one of the previously-coded pixels for that augmented pattern.

20. The encoder as recited in claim 18, wherein said coding means codes one of a plurality of symbols produced for each augmented pattern using arithmetic coding.

21. The encoder as recited in claim 18, wherein said coding means codes one of a plurality of symbols produced for each augmented pattern using Huffman coding.

22. An encoder/decoder system, comprising:

an encoder for coding a plurality of pixels in the digitized image, comprising;

means for applying a transform to the digitized image to determine an augmented pattern of each pixel based on a plurality of previously-coded neighboring pixels, each having a value, wherein the augmented pattern comprises a basic pattern which assigns a label to each previously-coded neighboring pixel, and a character for each previously-coded neighboring pixel that represents the number of times the value of that previously-coded neighboring pixel is repeated in a particular direction, wherein said transform applying means determines, for each augmented pattern, a probability for each label of the basic pattern, predicts a label of each pixel based on a comparison of the determined probability for each label and determines the actual label of each pixel, wherein said transform applying means generates one of a plurality of symbols for each augmented pattern to indicate that one of a plurality of conditions has been satisfied; and

a code generator for coding each of the produced plurality of symbols to compress the image; and

a decoder for decoding the coded plurality of symbols, comprising;

a symbol recovery generator for decoding the coded symbols; and

means for applying an inverse transform to recover the digitized image.

23. The encoder/decoder system as recited in claim 22, wherein said code generator codes each of the produced plurality of symbols using arithmetic coding.

24. The encoder/decoder system as recited in claim 22, wherein said code generator codes each of the produced plurality of symbols using Huffman coding.

25. A decoder for decoding a plurality of coded symbols to obtain an uncompressed digitized image represented by a plurality of pixels, each having a value, comprising:

a symbol recovery generator for decoding the plurality of coded symbols to recover the decoded symbols;

means for applying an inverse transform to the decoded symbols to determine the value of each of the plurality of pixels by extracting an augmented pattern of each pixel based on a plurality of neighboring pixels, wherein the augmented pattern comprises a basic pattern which includes a label for each of the neighboring pixels, and a character for each of the plurality of neighboring pixels that represents the number of times the value of that neighboring pixel is repeated in a particular direction, wherein said inverse transform applying means determines a value for each pixel based on the augment pattern of that pixel.

26. A computer system including a processor and a memory having a computer-readable program code embodied therein for causing the processor to code a plurality of pixels in a digitized image;

wherein said processor applies a transform to the digitized image to determine an augmented pattern of each pixel based on a plurality of previously-coded neighboring pixels, each having a value, wherein the augmented pattern comprises a basic pattern which assigns a label to each previously-coded neighboring pixel, and a character for each previously-coded neighboring pixel that represents the number of times the value of that previously-coded neighboring pixel is repeated in a particular direction;

wherein said processor determines, for each augmented pattern, a probability for each label of the basic pattern, predicts a label of each pixel based on a comparison of the determined probability for each label and determines the actual label of each pixel; and

wherein said processor codes each pixel based on the predicted label and the determined actual label of that pixel.

27. A computer-usable medium having a computer-readable program code embodied therein for causing a computer to code a pixel in a digitized image by performing the steps of:

determining an augmented pattern of said pixel based on a plurality of previously-coded neighboring pixels, each having a value, wherein the augmented pattern comprises a basic pattern which assigns a label to each previously-coded neighboring pixel, the labels identifying which of the previously-coded neighboring pixels are identical, said augmented pattern further comprising a plurality of characters, one for each previously-coded neighboring pixel that represents the number of times the value of that previously-coded neighboring pixel is repeated in a particular direction;

determining a probability for each label of the basic pattern;

predicting a label of said pixel based on a comparison of the determined probability for each label;

determining the actual label of said pixel;

producing one of a plurality of symbols to indicate that one of a plurality of conditions has been satisfied; and

entropy-coding the produced symbol.

28. The computer usable medium as recited in claim 27, wherein said plurality of previously-coded neighboring pixels comprise a first pixel located to the west of said pixel, a second pixel located to the northwest of said pixel, a third pixel located to the north of said pixel and a fourth pixel located to the northeast of said pixel.

29. The computer usable medium as recited in claim 28, wherein said plurality of characters comprises a first character that represents the number of times the value of said first pixel is repeated in the west direction, a second character that represents the number of times the value of said second pixel is repeated in the northwest direction, a third character that represents the number of times the value of said third pixel is repeated in the north direction and a fourth character that represents the number of times the value of said fourth pixel is repeated in the northeast direction.

30. The computer usable medium as recited in claim 27, wherein a first symbol is produced, if the predicted label is the same as the determined actual label, wherein a second symbol is produced if the predicted label is not the same as the determined actual label and if a value of said pixel is determined to be the same as the value of at least one of the previously-coded neighboring pixels, said produced second symbol indicating which of the previously-coded neighboring pixels has the same value as said pixel;

and wherein a third symbol is produced indicating prediction failure, if the predicted label is not the same as the determined actual label and if a value of said pixel is determined not to be the same as the value of at least one of the previously-coded neighboring pixels.