Image analysis – Image transformation or preprocessing – Measuring image properties
Reexamination Certificate
1993-03-29
2002-04-16
Mehta, Bhavesh (Department: 2721)
Image analysis
Image transformation or preprocessing
Measuring image properties
Reexamination Certificate
active
06373997
ABSTRACT:
A portion of the disclosure of this patent document contains material which is subject to copyright protection. The copyright owner has no objection to the facsimile reproduction by anyone of the patent document or the patent disclosure, as it appears in the Patent and Trademark Office patent file or records, but otherwise reserves all copyright rights whatsoever.
BACKGROUND OF THE INVENTION
The present invention relates to analysis of an image that includes features with a prominent skew or orientation. More specifically, the invention relates to the measurement of an angle of skew of lines in an image, including lines of text.
Peppers et al., U.S. Pat. No. 4,809,344, describe techniques for preprocessing of character recognition. As shown and described in relation to FIGS. 2, 4, and 5A, masks are used to detect laterally and vertically written documents. Masks could be used that have slits inclined at any angle to discriminate an inclined character string or line of characters. As shown and described in relation to FIGS. 6-8, photosensor arrays have different alignment directions and are operated simultaneously to detect laterally and vertically written documents. Photosensor arrays can also be inclined, as shown and described in relation to FIG. 10, to obtain inclination angle data. Col. 6 lines 39-42 indicate that coarse scanning data may be obtained by the scanner of FIG. 2 such that fine scanning data is obtained by the scanner of FIG. 6.
SUMMARY OF THE INVENTION
The present invention provides automatic techniques that measure skew direction of lines in an image by obtaining a first approximation, then using data indicating the result of the first approximation to obtain a second approximation more precise than the first. In an image of text, the first approximation can be obtained by finding the direction in which characters are closest together, since intercharacter distances are typically smaller than interline distances. Alternatively, it can be obtained by determining which of a number of directions has the largest variance in black pixels per line, because the lines in the direction of skew either have many black pixels due to characters in a line or few black pixels due to spaces between lines. The second approximation can then be obtained by determining which one of a number of directions close to the first approximation has the largest variance in black pixels per line. Similarly, a third, even more precise approximation can be obtained by determining which of a number of directions close to the second approximation has the largest variance in black pixels per line. More generally, this technique can be extended to obtain a sequence of successive approximations of skew direction, each approximation more precise than the previous one.
One aspect of the invention is based on the observation of problems with conventional skew measurement techniques. Some skew measurement techniques are simple but imprecise, providing an angle that is accurate to within several degrees of the actual skew angle. Other skew measurement techniques are more precise, but computationally expensive. In addition, some of the more precise skew techniques are subject to a 90° error resulting from text configurations in which a white space extends in a direction perpendicular to the lines of text, such as between columns of text.
This aspect is based on the discovery of a skew measurement technique that alleviates these problems by making both a coarse or imprecise skew measurement and a fine or more precise skew measurement. The result of the coarse measurement is used as a starting point for the fine measurement. Because it can start within a few degrees of the actual skew angle based on the coarse measurement, the fine measurement may require less computation and is not subject to the 90° error described above. This technique can be repeated on the fine measurement to obtain an even more precise skew measurement. In general, this technique can obtain a sequence of successive approximations of skew direction, each approximation more precise than the previous one.
The coarse measurement can be implemented by finding an approximate skew of lines in an image. In an image that includes text, for example, distances between characters can be measured in each of a number of initial directions. If the connected components within the characters include pixels of a first color, such as black, and the background is of a second color, such as white, then these distances can be measured between edge pixels, which can be pixels of either color that have at least one neighbor of the other color. Specifically, distance could be measured starting from a black edge pixel and extending in each direction to the nearest black pixel.
Measured distance data indicating distances measured in each direction can then be combined, such as by averaging, to obtain central distance data indicating a central value of distances in each direction, and this data can be used to form a profile indicating central value of distance as a function of direction. The minima separated by 180° within the profile indicate the direction of intercharacter spacing within the lines of text, because characters are closer together along a line of text than between lines—in general, the intercharacter distances are smaller than the interline distances. Data indicating the direction of one of these minima can be provided as the first approximation of skew direction.
The coarse measurement can alternatively be implemented by measuring variance of pixels in a number of initial directions. For example, for a pivot pixel of the first color, i.e. the color of pixels within connected components, the coarse measurement can obtain the square of the number of first color pixels lying along a line extending through the pivot pixel in each of the initial directions. The results for a number of such pivot pixels can then be combined to obtain a sum of squares for each direction. The initial direction with the largest sum of squares provides a first approximation of the skew direction of the text lines because the variance in the number of black pixels is larger at the skew direction than at other directions. In text, for example, lines in the skew direction will either pass through the center of a line of text, with many black pixels, or through a region between lines of text, with only a few black pixels from ascenders and descenders, resulting in a large variance. Data indicating the initial direction with the largest sum of squares can be provided as the first approximation.
The fine measurement can be implemented using the approximate skew direction from the coarse measurement and a number of nearby directions. The nearby directions can cover a range that is a small integer multiple of the angle separating the initial directions. For example, for a pivot pixel of the first color, the fine measurement can obtain the square of the number of first color pixels lying along a line extending through the pivot pixel in each of the nearby directions. The results for a number of such pivot pixels can then be combined to obtain a sum of squares for each nearby direction, and the nearby direction with the largest sum of squares provides a second approximation of the skew direction of the text lines. Data indicating the nearby direction with the largest sum of squares can be provided as the second approximation.
An even more precise measurement could be implemented using the second approximation and a number of directions near it.
A machine implementing the invention can include image input means for receiving an input image and providing input image data and image output means for receiving output image data and providing an output image. A processor can store the input image data in memory, modify it in accordance with the skew direction, and then provide output image data to the output means based on the modified image data. For example, the output image could be a deskewed version of the input image. This technique could be applied in a facsimile machine or a
Cass Todd A.
Hopcroft Michael J.
Huttenlocher Daniel P.
Wayner Peter C.
Mehta Bhavesh
Xerox Corporation
LandOfFree
Coarse and fine skew measurement does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Coarse and fine skew measurement, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Coarse and fine skew measurement will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2826468