Parallel difference coding method for lossless compression and real time decompression

• US 6,529,633 B1
• Filed: 09/10/1999
• Issued: 03/04/2003
• Est. Priority Date: 09/16/1998
• Status: Expired due to Term

• Current Assignee: Texas Instruments, Inc.
• Original Assignee: Texas Instruments, Inc.
• Inventors: Easwar, Venkat V., Payne, Ralph E.
• Primary Examiner(s): Johnson, Timothy M.
• Application Number:
  US09/394,114
• Time in Patent Office: 1,271 Days
• Field of Search: 382/166, 382/232, 382/233, 382/239, 382/243, 382/244, 382/245, 382/246, 382/248, 382/250, 382/251, 382/253, 375/240.02, 375/240.08, 375/240.12, 375/240.24, 358/462, 358/464, 358/539
• US Class Current: 382/239
• CPC Class Codes: G06T 9/00 Image coding bandwidth or redundancy reduction for static pictures H04N1/41; coding or decoding of static colour picture signals H04N1/64; methods or arrangements for coding, decoding, compressing or decompressing digital video signals H04N19/00

Abstract

A block based hybrid compression method where the input page is classified as SOLID, TEXT, SATURATED TEXT or IMAGE type, and the compression method most appropriate for each class is chosen on a block by block basis. Blocks classified as IMAGE may be compressed using Parallel Differential Pulse Code Modulation. This method allows the decompression algorithm to decode multiple pixels in parallel, thus making real time decompression significantly easier to implement. The methods shown will execute very efficiently on a Texas Instruments TMS302C82 multiprocessing Digital Signal Processor.

Claims

1. A data processing method for compressing data representing a composite page comprising of solid, text and image areas, comprising the steps of:

dividing an uncompressed page into equal size non-overlapping blocks before compression;

classifying each block as being part of an area containing TEXT, SATURATED TEXT, IMAGE or SOLID components;

compressing blocks classified as IMAGE blocks using a Differential Pulse Code Modulation algorithm, including

logically subdividing IMAGE blocks to be compressed into rectangular sub blocks and coding all the pixels in said sub blocks coded with the same code,

determining within each sub block the maximum difference between the predictions and the actual pixel values, and

using the maximum difference for each sub block as an 8-bit index into a Look Up Table (LUT) to determine the actual number of bits (use_bits) used for coding each pixel in the sub block.

2. The data processing method of claim 1 further comprising the step of:

determining the maximum and minimum gray level values of a block, and if the maximum value is equal to the minimum value classifying the block as SOLID.

3. The data processing method of claim 1 further comprising the step of:

determining the maximum and minimum gray level values of a block are determined, and if all pixels in the block are equal to either the maximum or the minimum, classifying the block as TEXT.

4. The data processing method of claim 1 further comprising the step of:

determining the maximum and minimum gray level values of a block are determined, and if the maximum is equal to the maximum gray level possible and the minimum is equal to the minimum gray level possible, classifying the block as SATURATED TEXT.

5. The data processing method of claim 1 further comprising the step of:

classifying all blocks not classified as SOLID, TEXT or SATURATED TEXT as IMAGE.

6. The data processing method of claim 1 further comprising the step of:

predicting the value of each pixel in the sub block from the value of the pixel to its left, in column order.

7. The data processing method of claim 1 further comprising the step of:

predicting the value of each pixel in the sub block from the value of the pixel above it in row order, thus rotating the pixel during the compression step.

8. The data processing method of claim 1 further comprising the step of:

bit stuffing each difference pixel with 0 to the nearest byte boundary in order to eliminate the need for bit stream alignment during decompression.

9. The data processing method of claim 1 further comprising the step of:

restricting the value of use_bits to be 0, 2, 4 or 8 in order to guarantee byte alignment of the compressed data.

10. The data processing method of claim 1 further comprising the step of:

if use_bits equals 8, transmitting the actual pixel value without compression.

11. The data processing method of claim 1 further comprising the step of:

using the same Look Up Table to determine the mode of the sub block, and where the mode represents the bit pattern used to encode the use_bits associated with said sub block.

12. The data processing method of claim 11 further comprising the step of:

transmitting the mode bits individually before each sub block.

13. The data processing method of claim 11 further comprising the step of:

transmitting the mode bits together for all the sub blocks within one block.

14. The data processing method of claim 12 further comprising the steps of:

decompressing the compressed data in real time as a page is printed; and

determining upon decompression the number of bits used to represent each pixel (use_bits) in the sub block from the mode bits associated with said sub block.

15. The data processing method of claim 14 further comprising the step of:

interpreting upon decompression the use_bits value of 0 to mean that each column in the sub block is identical with the column to it'"'"'s left.

16. The data processing method of claim 14 further comprising the steps of:

using a Look Up Table upon decompression to expand multiple coded pixels in one step.

17. The data processing method of claim 14 further comprising the step of:

during decompression expanding in the case of use_bits=2, four 2-bit difference values into four 8-bit pixels contained in a 32-bit word by the use of the said Look Up Table.

18. The data processing method of claim 14 further comprising the step of:

during decompression expanding in the case of use_bits=4, two 4-bit difference values into two 8-bit pixels.

19. A method of printing comprising the steps of:

receiving page data to be printed in a page description language;

converting the page data from the page description language into a bitmap of a page to be printed;

compressing the bitmap of the page to be printed by;

dividing an uncompressed page into equal size non-overlapping blocks before compression;

classifying each block as being part of an area containing TEXT, SATURATED TEXT, IMAGE or SOLID components;

compressing each block according to a compression algorithm corresponding to the classification of that block;

compressing blocks classified as IMAGE blocks using a Differential Pulse Code Modulation algorithm, including

logically subdividing IMAGE blocks to be compressed into rectangular sub blocks and coding all the pixels in said sub blocks coded with the same code,

determining within each sub block the maximum difference between the predictions and the actual pixel values, and

using the maximum difference for each sub block as an 8-bit index into a Look Up Table (LUT) to determine the actual number of bits (use_bits) used for coding each pixel in the sub block;

storing the compressed bitmap of the page in a frame buffer; and

decompressing the compressed bitmap of the page from the frame buffer in real time as the page is printed.

20. The data processing method of claim 19 further comprising the step of:

determining the maximum and minimum gray level values of a block, and if the maximum value is equal to the minimum value classifying the block as SOLID.

21. The data processing method of claim 19 further comprising the step of:

determining the maximum and minimum gray level values of a block, and if all pixels in the block are equal to either the maximum or the minimum, classifying the block as TEXT.

22. The data processing method of claim 19 further comprising the step of:

determining the maximum and minimum gray level values of a block, and if the maximum is equal to the maximum gray level possible and the minimum is equal to the minimum gray level possible, classifying the block as SATURATED TEXT.

23. The data processing method of claim 19 further comprising the step of:

classifying all blocks not classified as SOLID, TEXT or SATURATED TEXT as IMAGE.

24. The data processing method of claim 19 further comprising the step of:

predicting the value of each pixel in the sub block from the value of the pixel to its left, in column order.

25. The data processing method of claim 19 further comprising the step of:

predicting the value of each pixel in the sub block from the value of the pixel above it in row order, thus rotating the pixel during the compression step.

26. The data processing method of claim 19 further comprising the step of:

bit stuffing each difference pixel with 0 to the nearest byte boundary in order to eliminate the need for bit stream alignment during decompression.

27. The data processing method of claim 19 further comprising the step of:

restricting the value of use_bits to be 0, 2, 4 or 8 in order to guarantee byte alignment of the compressed data.

28. The data processing method of claim 19 further comprising the step of:

if use_bits equals 8, transmitting the actual pixel value without compression.

29. The data processing method of claim 19 further comprising the step of:

using the same Look Up Table to determine the mode of the sub block, and where the mode represents the bit pattern used to encode the use_bits associated with said sub block.

30. The data processing method of claim 29 further comprising the step of:

transmitting the mode bits individually before each sub block.

31. The data processing method of claim 29 further comprising the step of:

transmitting the mode bits together for all the sub blocks within one block.

32. The data processing method of claim 29 further comprising the steps of:

determining upon decompression the number of bits used to represent each pixel (use_bits) in the sub block from the mode bits associated with said sub block.

33. The data processing method of claim 32 further comprising the step of:

interpreting upon decompression the use_bits value of 0 to mean that each column in the sub block is identical with the column to it'"'"'s left.

34. The data processing method of claim 32 further comprising the steps of:

using a Look Up Table upon decompression to expand multiple coded pixels in one step.

35. The data processing method of claim 32 further comprising the step of:

during decompression expanding in the case of use_bits=2, four 2-bit difference values into four 8-bit pixels contained in a 32-bit word by the use of the said Look Up Table.

36. The data processing method of claim 32 further comprising the step of:

during decompression expanding in the case of use_bits=4, two 4-bit difference values into two 8-bit pixels by the use of the said Look Up Table.