Hybrid image compression with compression ratio control

• US 6,567,559 B1
• Filed: 09/10/1999
• Issued: 05/20/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.
• Primary Examiner(s): Johnson, Timothy M.
• Application Number:
  US09/393,840
• Time in Patent Office: 1,348 Days
• Field of Search: 382/238, 382/239, 382/243, 382/245, 382/250, 382/253, 382/224, 382/228, 375/240.02, 375/240.08, 375/240.1, 375/240.12, 375/240.2, 375/240.21, 375/240.22, 375/240.24, 348/420.1, 348/421.1, 358/1.15
• 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
• CPC Class Codes: H04N 1/41 Bandwidth or redundancy reduction by scanning H04N1/17 ; methods or arrangements for coding, decoding, compressing or decompressing digital video signals H04N19/00

Abstract

A block based hybrid compression method with compression ratio control. 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. The compression methods shown include Block Truncation Coding, Lossy or Lossless Differential Pulse Code Modulation, Run Length Coding and Discrete Cosine Transforms, but other algorithms may also be used. The compression ratio is dynamically controlled by selection of the compression algorithm, and by the adjustment of control parameters on a block by block or a row of blocks basis. 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 to a specified compression ratio, comprising the steps of:

dividing the uncompressed page is divided into equal size non-overlapping blocks before compression;

classifying each block as TEXT, SATURATED TEXT, IMAGE or SOLID as follows;

blocks with absolute central moments less than a predetermined alpha solid threshold are classified as SOLID,

blocks with a per pixel absolute reconstruction error less than a predetermined error threshold and with a difference between a foreground value and a background value greater than or equal to a predetermined foreground/background threshold are classified as TEXT;

TEXT blocks where the foreground color is 0 and the background color is at the maximum gray level are further classified as SATURATED TEXT, and

all other blocks are classified as IMAGE;

compressing the classified block with a compression algorithm best suited for that particular block'"'"'s characteristics; and

decompressing said compressed data in real time.

2. The data processing method of claim 1 where blocks classified as TEXT are compressed by using a Block Truncation Coding algorithm, with the foreground and background color values being further compressed using Differential Pulse Code Modulation.

3. The data processing method of claim 2 wherein the binary bitmap pattern of the block is compared to a set of pre-stored binary bitmap patterns, and if a reasonable match is found, only an index into a pattern table of pre-stored binary bitmap patterns is transmitted.

4. The data processing method of claim 1 where blocks classified as SATURATED TEXT are compressed using Block Truncation Coding, but only the binary bitmap is transmitted with the foreground and background inherently set to respective maximum and minimum gray levels.

5. The data processing method of claim 1, where blocks classified as IMAGE blocks are decimated by a variable decimation factor and then further compressed by Block Truncation Coding.

6. The data processing method of claim 1, where blocks classified as IMAGE blocks are decimated by a variable decimation factor and then further compressed by Differential Pulse Code Modulation.

7. The data processing method of claim 1, where blocks classified as IMAGE blocks are decimated using a variable decimation factor and then further compressed by Discrete Cosine Transform.

8. The data processing method of claim 1 where the compression ratio is dynamically adjusted to assure a compression ratio adequate to prevent frame buffer overflow by changing the quantization step used during the compression stage.

9. The data processing method of claim 1 wherein the compression ratio is dynamically adjusted to assure a compression ratio adequate to prevent frame buffer overflow by adjusting the block classification, with the overall compression ratio increasing when the number of blocks classified as SOLID or as IMAGE are increased.

10. The data processing method of claim 1 wherein the compression ratio is dynamically adjusted to assure a compression ratio adequate to prevent frame buffer overflow by grouping a number of blocks into a macroblock and processing at the macroblock level.

11. A data processing method of claim 1 wherein the compression ratio is dynamically adjusted to assure a compression ratio adequate to prevent frame buffer overflow by adjusting the decimation factor previous to compression.

12. 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 the bitmap into plural equally sized non-overlapping blocks of pixels;

calculating a mean pixel value for each block;

forming a binary bitmap of each block by assigning a foreground digital value to each pixel having a pixel value greater than the mean pixel value and a background digital value different from the foreground digital value to each pixel having a pixel value less than or equal to the mean pixel value;

calculating a first absolute central moment alpha for each block;

calculating a background value for each block from the mean pixel value, the number of pixels in the block and the number of background pixels in the block;

calculating a foreground value for each block from the mean pixel value, the number of pixels in the block and the number of foreground pixels in the block;

calculating a per pixel absolute reconstruction error for each block from the average of the absolute difference between the pixel value and the foreground value for each foreground pixel and the pixel value and the background value for each background pixel;

classifying a block as a SOLID block if the first absolute central moment alpha of that block is less than a predetermined alpha threshold;

classifying a block as an IMAGE block if the per pixel absolute reconstruction value for that block is greater than a predetermined error threshold;

classifying a block as an IMAGE block if the per pixel absolute reconstruction value for that block is less than a predetermined error threshold and a difference between the foreground value and the background value is less than a predetermined foreground/background threshold;

classifying a block as an TEXT block if the per pixel absolute reconstruction value for that block is less than a predetermined error threshold and a difference between the foreground value and the background value is greater than or equal to a predetermined foreground/background threshold;

compressing each block according to a compression algorithm corresponding to the classification of that 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.

13. The method of printing of claim 12, wherein:

said step of calculating a mean pixel value for each block employs the following equation;

$m=\frac{1}{N}<br><br>\text{\hspace{1em}<br><br>}<br><br>\underset{i,j}{\sum <br><br>}<br><br>\text{\hspace{1em}<br><br>}<br><br>g<br><br>\left(i,j\right)$

where;

m is the mean pixel value to be calculated;

N is the number of pixels in each block; and

g(i,j) is the pixel value of the pixel in the i-th row and the j-th column of the block.

14. The method of printing of claim 12, wherein:

said step of calculating a first absolute central moment alpha for each block employs the following equation;

$\mathrm{\alpha <br><br>}=\frac{1}{N}<br><br>\underset{i,j}{\sum <br><br>}<br><br>\text{\hspace{1em}<br><br>}<br><br><br><br>g<br><br>\left(i,j\right)-m<br><br>$

where;

α

is the first absolute moment alpha to be calculated;

N is the number of pixels in each block;

g(i,j) is the pixel value of the pixel in the i-th row and the j-th column of the block; and

m is the mean pixel value.

15. The method of printing of claim 12, wherein:

said step of calculating a background value for each block employs the following equation;

$\mathrm{bg}=m-\frac{N*\mathrm{\alpha <br><br>}}{2*\mathrm{bgCount}}$

where;

bg is the background value to be calculated;

m is the mean pixel value;

N is the number of pixels in each block;

α

is the first absolute moment alpha; and

bgcount is the number of background pixels in the block.

16. The method of printing of claim 12, wherein:

said step of calculating a foreground value for each block employs the following equation;

$\mathrm{fg}=m+\frac{N*\mathrm{\alpha <br><br>}}{2*\mathrm{fgCount}}$

where;

fg is the foreground value to be calculated;

m is the mean pixel value;

N is the number of pixels in each block;

α

is the first absolute moment alpha; and

fgcount is the number of foreground pixels in the block.

17. The method of printing of claim 12, wherein:

said step of calculating a per pixel absolute reconstruction error for each block employs the following equation;

$\mathrm{err}=\frac{1}{N}<br><br>\text{\hspace{1em}<br><br>}<br><br>\left(\underset{g<br><br>\left(i,j\right)><br><br>m}{\sum <br><br>}<br><br>\text{\hspace{1em}<br><br>}<br><br><br><br>g<br><br>\left(i,j\right)-\mathrm{fg}<br><br>+\underset{g<br><br>\left(i,j\right)\le <br><br>m}{\sum <br><br>}<br><br>\text{\hspace{1em}<br><br>}<br><br><br><br>g<br><br>\left(i,j\right)-\mathrm{bg}<br><br>\right)$

where;

err is the per pixel absolute reconstruction error to be calculated;

N is the number of pixels in each block;

g(i,j) is the pixel value of the pixel in the i-th row and the j-th column of the block;

m is the mean pixel value;

fg is the foreground value; and

bg is the background value.

18. The method of printing of claim 12, further comprising:

classifying a TEXT block as a SATURATED TEXT block if the calculated background value is a minimum pixel value and the calculated foreground value is a maximum pixel value.

19. The method of printing of claim 12, wherein:

said step of compressing each block includes

specifying compressed data if the current block has the same classification as the prior block; and

specifying an escape code, a block classification indicator and compressed data if the current block has a classification that differs from the classification of the prior block.

20. The method of printing of claim 19, wherein;

said compressed data of a SOLID block is;

Δ

m the difference between the mean pixel value of the prior block and the calculated mean pixel value of the current block.

21. The method of printing of claim 19, wherein:

said compressed data of a TEXT block is;

Δ

fg the difference between the calculated foreground value of the prior block and the calculated foreground value of the current block;

Δ

bg the difference between the calculated background value of the prior block and the calculated background value of the current block; and

the binary bitmap.

22. The method of printing of claim 19, further comprising:

classifying a TEXT block as a SATURATED TEXT block if the calculated background value is a minimum pixel value and the calculated foreground value is a maximum pixel value; and

said compressed data of SATURATED TEXT block is;

the binary bitmap, the foreground value assumed to be the maximum pixel value and the background value assumed to be the minimum pixel value.

23. The method of printing of claim 19, wherein:

said step of compressing each block includes encoding a run of SOLID blocks having the same mean pixel value m as;

a SOLID block;

followed by a RUN block consisting of the escape code, the block classification indicator of a SOLID block and a run count, the mean pixel value assumed to be the mean pixel value of the preceding SOLID block.

24. The method of printing of claim 19, wherein:

said step of compressing each block includes

encoding a run of SOLID blocks greater than a predetermined minimum run length having the same mean pixel value m as;

a SOLID block;

followed by a RUN block consisting of the escape code, the block classification indicator of a SOLID block and a run count, the mean pixel value assumed to be the mean pixel value of the preceding SOLID block; and

encoding a run of SOLID blocks less than or equal to the predetermined minimum run length having the same mean pixel value m as a set of SOLID blocks.

25. The method of printing of claim 19, wherein:

said step of compressing each block includes

encoding a run of SOLID blocks less than or equal to a predetermined maximum run length having the same mean pixel value m as;

a SOLID block;

followed by a RUN block consisting of the escape code, the block classification indicator of a SOLID block and a run count, the mean pixel value assumed to be the mean pixel value of the preceding SOLID block; and

encoding a run of SOLID blocks greater than the predetermined maximum run length having the same mean pixel value m as;

a SOLID block;

a RUN block consisting of the escape code, the block classification indicator of a SOLID block and a maximum run count, the mean pixel value assumed to be the mean pixel value of the preceding SOLID block;

followed by at least one further RUN block.

26. The method of printing of claim 19, further comprising:

storing a predetermined number of predetermined binary bitmap patterns corresponding to TEXT blocks, each binary bitmap pattern having an index;

comparing the binary bitmap of a TEXT block with each of the predetermined binary bitmap patterns; and

said compressed data of a TEXT block is;

Δ

fg the difference between the calculated foreground value of the prior block and the calculated foreground value of the current block;

Δ

bg the difference between the calculated background value of the prior block and the calculated background value of the current block; and

the binary bitmap if the binary bitmap does not match any binary bitmap pattern; and

Δ

fg the difference between the calculated foreground value of the prior block and the calculated foreground value of the current block;

Δ

bg the difference between the calculated background value of the prior block and the calculated background value of the current block; and

the index of a binary bit map pattern if the binary bitmap matches a binary bitmap pattern.

27. The method of printing of claim 19, further comprising:

storing a predetermined number of predetermined invalid binary bitmap patterns corresponding to invalid TEXT blocks;

comparing the binary bitmap of a TEXT block with each of the predetermined invalid binary bitmap patterns; and

reclassifying the TEXT block as an IMAGE block if the binary bitmap of the TEXT block matches any one of the invalid binary bitmap patterns.

28. The method of printing of claim 12, further comprising:

reclassifying an block initially classified as a TEXT block as an IMAGE block if the prior block is a TEXT block and either the calculated foreground value of the current block does not match the calculated foreground value of the prior block or the calculated background value of the current block does not match the calculated background value of the prior block.

29. The method of printing of claim 12, further comprising:

reclassifying an block initially classified as a TEXT block as an IMAGE block if the prior block is a SOLID block and neither the calculated foreground value of the current block nor the calculated background value of the current block matches the mean pixel value the prior block.