Image analysis – Image compression or coding – Gray level to binary coding
Reexamination Certificate
2000-03-02
2002-02-26
Lee, Thomas D. (Department: 2624)
Image analysis
Image compression or coding
Gray level to binary coding
C382S270000, C358S451000, C358S466000
Reexamination Certificate
active
06351566
ABSTRACT:
FIELD OF THE INVENTION
The present invention relates generally to methods and apparatus for image processing, and specifically to methods for binarization of gray-level images.
BACKGROUND OF THE INVENTION
Methods of image binarization are well-known in the art. Generally speaking, these methods take a gray-level image, in which each pixel has a corresponding multi-bit gray-level value, and convert it into a binary image, in which each pixel has a binary value, either black (foreground) or white (background). Binarization is used particularly in simplifying document images, in order to process and store information that is printed or written on the document.
The fastest and simplest binarization method is simply to fix a threshold and to determine that all pixels having a gray-level value above the threshold are white, while those below the threshold are black. This method, however, frequently results in loss or confusion of the information contained in the gray-level image. This information is embodied mainly in edges that appear in the image, and depends not so much on the absolute brightness of the pixels as on their relative brightness in relation to their neighbors. Thus, depending on the choice of threshold, a meaningful edge in the gray-level image will disappear in the binary image if the pixels on both sides of the edge are binarized to the same value. On the other hand, artifacts in the binary image with the appearance of edges may occur in an area of continuous transition in the gray-level image, when pixels with very similar gray-level values fall on opposite sides of the chosen threshold.
These problems are exemplified by the following tables. Table I represents pixel values in a 5×5 image, wherein higher values represent brighter pixels:
TABLE I
Gray
Col 1
Col 2
Col 3
Col 4
Col 5
Row 1
10
10
10
11
11
Row 2
10
11
12
13
14
Row 3
16
17
18
19
20
Row 4
14
16
14
16
18
Row 5
16
14
16
14
90
If this image is binarized using a threshold of 85, the result will be as shown in Table II:
TABLE II
Thr = 85
Col 1
Col 2
Col 3
Col 4
Col 5
Row 1
0
0
0
0
0
Row 2
0
0
0
0
0
Row 3
0
0
0
0
0
Row 4
0
0
0
0
0
Row 5
0
0
0
0
1
The large gaps surrounding the pixel in the lower right corner are represented in the binarized image, but all of the other gaps are lost. (The term “gap” is used in the context of the present patent application and in the claims to denote the absolute difference in gray level between a pair of neighboring pixels.)
On the other hand, if the threshold is set to 15, the resulting binary image will be as shown in Table III:
TABLE III
Thr = 85
Col 1
Col 2
Col 3
Col 4
Col 5
Row 1
0
0
0
0
0
Row 2
0
0
0
0
0
Row 3
1
1
1
1
1
Row 4
0
1
0
1
1
Row 5
1
0
1
0
1
The gap of size 6 between rows 2 and 3, which probably corresponds to a real edge in the image, is represented in the binary image. The large gaps in the lower right corner are lost, however. At the same time, small gaps (of size 2) between rows 4 and 5 , which could be due to noise, are represented in the binary image. Thus, significant edges in the gray-level image are lost, while insignificant gaps are allowed to generate artifacts.
For the reasons exemplified by these tables, practical binarization algorithms allow the binarization threshold to vary. These algorithms generally make assumptions about image content in determining the best threshold to use over the whole image or in specific areas of the image. The assumptions may relate to the sizes of objects in the image, histogram properties, noise levels or other image properties. Because they are dependent on such assumptions, binarization algorithms tend to work well on the specific type of images or objects for which they are designed, but to fail on others. For example, a text-oriented binarization algorithm can work well on a document image that contains text on a plain background, but may fail when the background is textured. Furthermore, document images frequently contain salient features other than simple text, such as symbols, lines and boxes, which are important to preserve in the binary image and are lost when text-oriented binarization is used.
Image “trinarization” has been suggested as a method for processing gray-level images, although not in the context of document imaging. Typically, a range of “gray” pixel values is defined intermediate the low values of the black range and the high values of the white range. The resultant trinary image has been found to be useful in a number of image recognition and image correlation applications.
For example, U.S. Pat. No. 5,067,162, whose disclosure is incorporated herein by reference, describes a method and apparatus for verifying identity using image correlation, typically based on fingerprint analysis. In order to eliminate uncertainty and variability of edge determinations in the fingerprint image, a trinarization technique is used to divide all pixels into one of three levels: black, gray or white. A histogram of gray values of the gray-scale image is determined, and black-gray and gray-white threshold values are established according to equal one-third distributions. All pixels having gray values darker than the black-gray threshold value are converted into black pixels; all pixels having gray values lighter than the gray-white threshold value are converted into white pixels; and all other pixels are ignored in subsequent correlation calculations. Thus, the black and white pixels represent with high confidence ridge and valley regions of the fingerprint image, while the gray pixels represent the transition regions between the ridges and valleys.
As another example, U.S. Pat. No. 5,715,325, whose disclosure is incorporated herein by reference, describes apparatus and methods for detecting a face in a video image. Face images are processed to eliminate fine detail and provide a hard contrast, resulting in an image that is nearly binarized (having dark blocks and light blocks) but still contains some blocks that cannot be clearly categorized. To promote simplicity in processing, the image is treated as a trinary image, wherein dark regions are identified with negative ones (−1's), light regions are identified with ones (1's), and undefinable regions are identified with zeros (0's). The trinary image is then compared with different face templates to find an optimal match.
SUMMARY OF THE INVENTION
It is an object of the present invention to provide improved methods and apparatus for image processing, and particularly for processing of document images.
It is a further object of some aspects of the present invention to provide improved methods for image binarization.
It is still a further object of some aspects of the present invention to provide a method for trinarization of an image.
In preferred embodiments of the present invention, a gray-level input image is trinarized, generally as a preparatory step in generating a binary output image. The input image is first analyzed in order to characterize variations among the gray-level values of the pixels in the image, such as gaps between the values of neighboring pixels. Based on these variations, upper and lower binarization thresholds are determined, such that pixels having gray-level values above the upper threshold are classified as white, and those below the lower threshold are classified as black. The pixels having gray-level values between the lower and upper thresholds, referred to hereinafter as intermediate or gray pixels, are then preferably processed so as to determine an optimal classification of these pixels as black or white.
Preferably, the upper and lower binarization thresholds are chosen in a manner designed to increase the number of significant edges in the input image that are preserved in the output binary image, while decreasing the number of artifact edges that occur. Generating the binary image in this manner conveys the salient features of the input image clearly, substantially without dependence on the type of image content. A range of different threshold values are evaluated against the gray-level v
Darby & Darby
International Business Machines
Lee Thomas D.
LandOfFree
Method for image binarization does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Method for image binarization, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Method for image binarization will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2941844