Method for high-quality compression of binary text images

• US 5,204,756 A
• Filed: 07/30/1990
• Issued: 04/20/1993
• Est. Priority Date: 08/04/1989
• Status: Expired due to Term

• Current Assignee: IPG Healthcare 501 Limited (Coller IP Capital Limited)
• Original Assignee: International Business Machines Corporation
• Inventors: Walach, Eugeniusz, Karnin, Ehud D., Chevion, Dan S.
• Primary Examiner(s): Brinich, Stephen
• Assistant Examiner(s): Grant, II, Jerome
• Application Number:
  US07/559,734
• Time in Patent Office: 995 Days
• Field of Search: 358/429, 358/430, 358/426, 358/261.1, 358/261.2, 358/261.3, 358/261.4, 358/427, 358/267.1, 358/432, 358/433, 358/462, 358/464, 358/463, 358/467
• 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/411 for the transmission or storage or reproduction of two-tone pictures, e.g. black and white pictures

Abstract

The invention relates to a method for the compression and decompression of binary test images. The method distinguishes between large low-frequency areas and small high-frequency areas in the original frame. For the low-frequency areas, a scheme for lossy compression is used, whereas for the high-frequency areas, a scheme permitting lossless compression is applied. The compression/decompression process involves five stages; namely prefiltering to remove all black patches (e.g. by removing all black pixels, except where they belong to a large black segment), fast evaluation of compressibility by partitioning the images into mutually exclusive segments and applying different compression modes to each segment, connectivity-oriented subsampling to reduce the reslolution in horizontal and vertical directions which cause the image to be segmented into blocks and a 1-pixel representation for each block is determined, lossless compression and decompression where the reduced file is compressed by conventional techniques, and reconstruction by sequence reversal so that lossless decompression will retrieve the subsampled file, expansion of the subsampled file through replacement of each pixel by a block having equal value and postfiltering.

Claims

1. Method for high-quality compression of binary text images for storage and possible future processing including transmission over data links, involving the scanning thereof on the record carrier on which they are presented in a pixel-by-pixel raster scan and deriving a string of digital data from the scanner output, characterized by the step of determining the degree of compressibility of the individual features of the original image based on the nature of the scan data derived from a specific vicinity of pixels in the original image, and, depending on the frequency of the information content of the data from said vicinity, assigning one of at least two different compression ratios to the data from each vicinity, and compressing said data in accordance with said one compression ratio.

2. Method in accordance with claim 1, characterized in that those vicinities of pixels having a high information content are assigned a first compression ratio corresponding to lossless compression, and that those vicinities of pixels having a low information content are assigned a second compression ratio corresponding to lossy compression.

3. Method in accordance with claim 1, characterized in that the said vicinity of pixels are defined by partitioning the entire image area into mutually exclusive segments of uniform size, that for each segment the average length (w) of intervals comprising pixels with a "1" and "0" value is determined, that if, for any one segment, the said length exceeds a predetermined value (w_t), the next segment is interrogated, otherwise, the contents of a previously cleared pair of registers (m, n) is incremented by 1, and m by w, and that at the end of the segment the feasibility of compression is determined by checking whether n is lower than a predetermined first threshold (n_t), or whether the ratio m/n exceeds a predetermined second threshold ([m/n]_t), in which cases lossy compression is performed while in all other cases lossless compression is performed.

4. Method in accordance with claim 3, characterized in that the said vicinity are defined as 2×

2 blocks of pixels, and that for each such block a 1-bit representation is developed by assigning a "0"-value to all blocks having less than two black pixels, a "1"-value to all blocks having more than two black pixels and a "0"-value to all blocks having exactly two black pixels, provided assigning "0"-value for two black pixels does not break a connection between two lines and does not distort line curvature, if it does, a "1"-value is assigned to all blocks having exactly two black pixels.

5. Method in accordance with claim 1, characterized in that said step of determining the degree of compressibility of the individual features of the original image is preceded by a prefiltering step involving the filtering of the scan data prior to compression through forced changing of all isolated "1" pixels as well as all horizontal and vertical sequences of "1" pixels to "0" if the said sequences are shorter than a predetermined length.

6. Method in accordance with claim 5, characterized in that the said predetermined length is set to three pixels.

7. Method in accordance with claim 6, characterized in that the said predetermined length value (w_t) is 12, that said first threshold (n_t) is 5, and that said second threshold ([m/n]_t) is 4.

8. Method for high-quality compression of binary text images for storage and possible future processing including transmission over data links, involving the scanning thereof on the record carrier on which they are presented in a pixel-by-pixel raster scan and deriving a string of digital data from the scanner output, characterized by the step of determining the degree of compressibility of the individual features of the original image based on the nature of the scan data and depending on the frequency of the information content of the data derived from a specific vicinity of pixels in the original document, said vicinity of pixels are defined by partitioning the entire image area into mutually exclusive segments of uniform size, that for each segment the number (m) of nonzero bytes is counted and each such byte is translated into a binary number which equals 1 if the byte under consideration contains a small black or white interval, that is, that byte does not equal either 00000000 or 11111111 and the first bit of the byte equals the last one, and which equals 0 in all other cases, that the number (n) of pairs of consecutive "1'"'"'s" is counted, and that lossy compression is performed if n is smaller than a predetermined threshold and/or if n is smaller than a predetermined fraction of m, assigning one of at least two different compression ratios to the data from each vicinity, and compressing said data in accordance with said one compression ratio.

9. Method in accordance with claim 8, characterized in that the said predetermined threshold is 3, and that said predetermined fraction equals 5%.

10. Method in accordance with claim 8, characterized in that the said segments each correspond to a line of scan of the original binary text image.

11. Method in accordance with claim 8, characterized in that the said segments each correspond to two consecutive lines of scan of the original binary text image.

12. Method for high-quality compression of binary text images for storage and possible future processing including transmission over data links, involving the scanning thereof on the record carrier on which they are presented in a pixel-by-pixel raster scan and deriving a string of digital data from the scanner output, characterized by the step of determining the degree of compressibility of the individual features of the original image based on the nature of the scan data derived from a specific vicinity of pixels in the original image, and depending on the frequency of the information content of the data from said vicinity, assigning one of at least two different compression ratios to the data from each vicinity, and compressing said data in accordance with said one compression ratio, with a compression ratio being determined by a compression operation involving a reconstruction and postfiltering step applicable to vicinities in accordance with an array of the type ##EQU14## which is executed as follows:

- if C=1 and G=F=H=0 (case of a small curve), then said array should be transformed to the following new array;

##EQU15## - and if C=D=E=F=0 (case of a diagonal line), then said array should be transformed to the following new array;

##EQU16## in order to preserve curves and sharp angles between lines, and to smooth the reconstructions of diagonal lines.