EP0411232A2
Expired / Lapsed
EP
⏱️ 0.0 years remaining
Method for high-quality compression by binary text images
Assignee: International Business Machines Corp
•
Filing: 1989-10-10
•
Granted: —
•
Expires: 2009-10-10
Abstract
Abstract The invention relates to a method for the compression and decompression of binary text 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: 1. Prefiltering to remove all black patches (e.g. by removing all black pixels, except where they belong to a large black segment. 2. Fast Evaluation of Compressibility by partitioning the images into mutually exclusive segments and applying different compression modes to each segment. 3. Connectivity-Oriented Subsampling to reduce the resolution in horizontal and vertical directions. The image is segmented into blocks, and a 1-pixel representation for each block is determined. 4. Lossless Compression and Decompression where the reduced file is compressed by conventional techniques. 5. Reconstruction by sequence reversal. Lossless decompression will retrieve the subsampled file, expansion of the subsampled file through replacement of each pixel by a block having equal value, postfiltering.
Inventors
- 👤 Dan Shmuel Dr. Chevion
- 👤 Ehud Dov Dr. Karnin
- 👤 Eugeniusz Dr. Walach
Bibliographic Details
Application Number
—
Jurisdiction
EP
Data Source
google_patents
Last Synchronized
2026-10-24 19:27
CPC Classifications
H; H04; H04N; H04N1/00; H04N1/41; H04N1/411; G; G06; G06T; G06T9/00
Claims Analysis
Total Claims: 13
Claim 1
Independent Claim
126 words
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.
Claim 2
Dependent Claim
126 words
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.
Claim 3
Dependent Claim
49 words
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.
Claim 4
Dependent Claim
72 words
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.
Claim 5
Dependent Claim
18 words
Method in accordance with claim 1, characterized in that the said predetermined length is set to three pixels.
Claim 6
Dependent Claim
148 words
Method in accordance with claim 1, characterized in that the said vicinities 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) 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.
Claim 7
Dependent Claim
39 words
Method in accordance with claim 4, 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.
Claim 8
Dependent Claim
134 words
Method in accordance with claim 1, characterized in that the said vicinities 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.
Claim 9
Dependent Claim
21 words
Method in accordance with claim 7, characterized in that the said threshold is 3, and that said fraction equals 5 %.
Claim 10
Dependent Claim
25 words
Method in accordance with claim 7, characterized in that the said segments each correspond to a line of scan of the original binary text image.
Claim 11
Dependent Claim
26 words
Method in accordance with claim 7, characterized in that the said segments each correspond to two consecutive lines of scan of the original binary text image.
Claim 12
Dependent Claim
110 words
Method in accordance with claim 5, characterized in that the said vicinities 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, and a "1"-value to all blocks having more than two black pixels, and by assigning a "0"-value to all blocks having exactly two black pixels, provided such an assignment does not break a connection between two lines and does not distort line curvature, , and by assigning a "1"-value to all blocks having exactly two black pixels if said break and/or was otherwise to occur.
Claim 13
Dependent Claim
94 words
Method in accordance with claim 1, characterized in that the said compression operation involves a reconstruction and postfiltering step applicable to vicinities in accordance with an array of the type which is executed as follows: - if C=1 and B=F=H=0 (case of a small curve), then said array should be transformed to the following new array: - and if C=D=E=F=0 (case of a diagonal line), then said array should be transformed to the following new array: in order to preserve curves and sharp angles between lines, and to smooth the reconstructions of diagonal lines.
References Cited (Backward Citations)
No citation records indexed.
USPTO Annuity & Maintenance Windows
Maintenance schedule is calculated for granted US utility patents.