Method for CCITT compression of image data

• US 6,556,715 B1
• Filed: 10/29/1999
• Issued: 04/29/2003
• Est. Priority Date: 10/29/1999
• Status: Expired due to Term

• Current Assignee: Unisys Corporation
• Original Assignee: Unisys Corporation
• Inventors: Kozlowski, William L.
• Primary Examiner(s): Johns, Andrew W.
• Assistant Examiner(s): Dang, Duy M.
• Application Number:
  US09/430,313
• Time in Patent Office: 1,278 Days
• Field of Search: 382/232, 382/298, 382/169, 382/171, 382/172, 382/237, 358/430, 358/431, 358/419, 358/451, 358/447, 358/448
• US Class Current: 382/232
• CPC Class Codes: G06T 9/005 Statistical coding, e.g. Huffman, run length coding

Abstract

A method of compressing image data utilizing CCITT Group 4 coding criteria reduces compression time and the amount of required data transfer by combining pixel data thresholding and transposition steps through the capabilities of a customized processing chip. Additional economies are achieved by using black/white and white/black transition pointers rather than the conventional approach requiring examination of every pixel to locate the transitions in preparation for conventional CCITT Group 4 encoding.

Claims

1. A method for CCITT compression of image data comprising the steps of:

a) creating and saving a scaled background of the image by calculating a background average for each array of pixels of a predetermined size;

b) thresholding each pixel to a black or white rendition and storing the thresholded pixel in a manner which automatically transposes the pixels to a predetermined order;

c) determining run lengths of adjacent pixels having like color and storing the run lengths as color transition pointers in a memory table; and

d) processing two rows of thresholded pixels simultaneously pursuant to CCITT Group 4 encoding principles using the color transition pointers from the memory table in place of retrieving and examining each pixel individually to determine transition locations in the two rows.

2. The method of claim 1 wherein the step of determining run lengths is performed using a white look-up table when searching for a pixel transition from black to white and a black look-up table when searching for a pixel transition from white to black.

3. The method of claim 1 wherein each array of pixels used for calculating a background average has a size of four pixels by four pixels.

4. The method of claim 3 wherein the background is created using a five tap image filter in both the horizontal and vertical directions.

5. The method of claim 1 wherein the step of thresholding utilizes a 12×

12 pixel window surrounding a pixel to be thresholded, the 12×

12 window comprising an average of nine background values.

6. The method of claim 5 wherein the step of thresholding includes simultaneous processing of two sets of four pixel by four pixel backgrounds.

7. The method of claim 1 wherein the determined run lengths are stored as eight bit bytes, with a byte of all zeros indicating a run of 256 pixels.

8. The method of claim 1 wherein the step of thresholding includes the further steps of:

determining a background threshold as a predetermined function of an input background for a pixel being thresholded;

comparing a grayscale level of the pixel being thresholded to the background threshold; and

setting the pixel being thresholded to a first predetermined color whenever its value is above the background threshold and setting the pixel being thresholded to a second predetermined color whenever its value is equal to or less than the background threshold.

9. In a method for compressing document image data in accordance with CCITT wherein a document to be imaged is scanned in a first format and the resultant image data is compression processed in a second format, wherein image data pixels are transposed into the second format, wherein each image data pixel is next thresholded to a black or white value, and wherein the transposed and thresholded image pixels are examined to determine run lengths of a same color, the improvement comprising:

combining the steps of transposing and thresholding into a single step.

10. In a method for compressing document image data in accordance with CCITT Group 4 wherein preselected run lengths of a same pixel color in two adjacent rows of image data are examined for each encoding step, the improvement comprising:

alternately using a first color look-up table and a second color look-up table to determine locations in each pixel row of respective transitions between the first and second colors; and

using the determined transition locations in lieu of examining each pixel of the two adjacent rows to perform the CCITT Group 4 encoding process.