Method and Apparatus for Thinning Alphanumeric Characters for Optical Character Recognition

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 copyrigh rights whatsoever.

1. Technical Field

The invention is related to pre-processing devices for optical character recognition systems and in particular to pre-processing devices which thin or skeletonize an image of an individual character to facilitate its recognition by an optical character recognition system.

2. Background Art

Various techniques are known in the art for thinning or skeletonizing images of patterns. Some of these techniques are directed specifically to thinning patterns of alphanumeric characters to facilitate their recognition by an optical character recognition system. Such techniques essentially strip away the outer boundary pixels of a character one layer at a time in repeated succession until the character has been sufficiently thinned. Many of these techniques avoid stripping away the end point of a character stroke under certain conditions in order to preserve the stroke. For example, Hilditch, "Linear Skeletons from Square Cupboards", Machine Intelligence, Vol. 4, Edinburgh University Press (1969) pp. 403-420 discloses thinning n image with the constraints that a pixel may not be erased if the erasure would change connectivity or if the pixel is an end point.

U.S. Pat. No. 3,975,709 (Beun et al.) discloses a character skeletonization process in which edge pixels of a character are detected by sensing their connectivity in a local neighborhood and are removed as long as such removal does not create a void in a character stroke. This process is repeated until a final repetition in which less than a threshold number of pixels are removed. Then, further repetitions of the process are performed with the added constraint that end points cannot be removed. One problem with this concept is that the shape of the skeletonized character thus generated may depend upon the sequence in which the character pixels are processed.

U.S. Pat. Nos. 3,735,349 (Beun et al.) and 4,034,344 (Saraga et al.) disclose similar concepts.

U.S. Pat. No. 3,940,737 (Beun) discloses a similar concept with an improvement directed to ameliorating the problem that the shape of the skeletonized character can depend upon the sequence in which the pixels are processed. This improvement comprises additional or repetitive testing of each pixel with respect to constraints against its removal. As in the previous references, these constraints are based upon the pixels in a local neighborhood. A disadvantage of this concept is that the additional or repetitive testing consumes additional processing time.

U.S. Pat. No. 4,162,482 (Su), U.S. Pat. No. 4,115,760 (Ito) and JP 62-160595 (Watanabe) disclose thinning processes employing different criteria during different cycles.

The main problem with such techniques is that the criteria for removing or not removing an end point of a character stroke bears no relationship to the desired results. For example, in some techniques similar to those disclosed in the publication by Hilditch referred to above, the end points are apparently preserved throughout the entire skeletonization process. As applied to alpha-numeric characters such as the letter "V", this creates distracting artifacts which may prevent the resulting thinned character from being recognized by an optical character recognition system. This may be seen by referring to the thinning sequence for the letter "V" starting with FIG. 1b and concluding with FIG. 1d. The end point 10 at the base of the letter "V" is preserved from the start (FIG. 1b) of this particular sequence as boundary pixels are removed in successive iterations, so that the letter V of FIG. 1b is converted to a letter Y in FIG. 1d. Such a result is unacceptable for optical character recognition.

The U.S. Patents to Buen et al. referred to above represent a limited improvement, in that they teach that during an initial part of the thinning process, end points are removed, provided that the connectivity criteria is not violated. Thus, starting with the letter V of FIG. 1a, all boundary pixels are removed in successive iterations until the letter has been reduced to the thinner image of FIG. 1b. Then, subsequent iterations of the boundary pixel removal step are performed with the restriction that end points may not be removed, generating the sequence of images of FIGS. 1c and 1d. In this example, the protection of the end points was begun too soon during the process. Thus, the transition point at which protection of the end pixels is begun during the thinning process is critical.

Buen et al. teaches that the protection of end points is begun during the process immediately upon the conclusion of a boundary pixel removing step at which the number of pixels actually removed was less than a predetermined threshold. There is no suggestion by Buen et al. of how to select the predetermined threshold to avoid the unacceptable results illustrated in the sequence of FIGS. 1a-1d. In the sequence of FIGS. 1a-1d, the threshold was set too high, so that the protection of end points was begun too early in the process.

If a way could be found to correctly select the point at which the protection of end points is begun during the boundary removal process, the result would be that of FIG. 2 instead of FIG. 1d. In the example of FIG. 2, the protection of the end points was not begun prematurely as in the preceding example.

The effect of beginning the protection of end points too late (or not at all) during the boundary pixel removal process is illustrated in the sequence of FIGS. 3a-3d illustrating the thinning of a letter "P". In this example, the vertical stroke 20 at the base of the "P" distinguishes the character from a letter "D". In this example, the vertical stroke 20 is somewhat thinner than the remainder of the "P", which can occur if the document containing the "P" is scanned at a high speed with a low resolution, for example. In order for an optical character recognition system to correctly recognize the thinned version of the "P", preservation of at least a distinguishing portion of the base vertical stroke 20 is critical.

In the sequence of FIGS. 3a-3d, the protection of end points is begun too late, so that the base vertical stroke 20 has been so shortened in the final thinned image of FIG. 3d that the P has been virtually converted to a letter D. This result would be reached in Buen et al. by setting their threshold number of removed pixels too high.

The ideal result is obtained by beginning the protection of end points immediately following the boundary pixel removal step of FIG. 3c. In FIG. 3c the length of the vertical base stroke 20 has been shortened to an acceptable length "a", and this length is preserved through the conclusion of the process with the result illustrated in FIG. 4.

From the foregoing, one solution might be to set the transition point at which the preservation of end points is begun to the step corresponding to that of FIG. 3c. However, while this may be the correct transition point for thinning a letter P in the sequence of FIGS. 3 and 4, it may not be the correct transition point for thinning the letter V in the sequence of FIGS. 1 and 2. Moreover, if a significant change in character size, thickness or font is encountered while scanning the document, the transition point previously selected will necessarily be incorrect for the subsequent characters.

Accordingly, there is a need for a method of determining the transition point in the thinning process at the preservation of end points is begun which avoids the formation of confusing artifacts such as that illustrated in FIG. 1d and avoids the excessive shortening of a character stroke as illustrated in FIG. 3d in a reliable and automatic manner.

In accordance with the thinning process of the invention, a certain character stroke width found in an individual unknown character is first determined. Then, a single layer of boundary pixels in a bit-map image of the character are all removed except for those boundary pixels whose removal would change connectivity in the image. This step is repeated a number of times corresponding to the number of pixels spanned by a given fraction of the certain character stroke width previously determined. At this point, a transition is made so that during subsequent repetitions of the boundary pixel removal step, all pixels which are end points of character strokes are protected from removal. The process concludes when the character image has been skeletonized.

In the preferred embodiment of the invention, the certain character stroke width is the minimum character stroke width found in the image and the given fraction is one half the minimum character stroke width.

By basing the transition point during the character thinning process at which the preservation of end point pixels is begun upon a character stroke width found in the current character image (e.g., one half the minimum stroke width of the character), the locations of such protected end points in the final skeletonized image are less likely to result in confusion of the original character with another character. Thus, the stem at the bottom of the letter "V" in FIG. 2 skeletonized by the invention is reduced (relative to the inferior result illustrated FIG. 1d) by at least one half the minimum stroke width of the original character of FIG. 1a. As a result, the letter "V" of FIG. 2 skeletonized by the invention is not as likely to be confused with the letter "Y" as in the prior art. Furthermore, the base stem 20 of the letter P of FIG. 4 skeletonized by the invention is increased (relative to the inferior result illustrated in FIG. 2d) to its original length minus no more than the minimum stroke width of the original character of FIG. 2a and in most cases minus half the minimum stroke width, depending upon how the boundary pixel removal is implemented. As a result, the letter "P" of FIG. 4 skeletonized by the invention is not as likely to be confused with the letter "D" as in the prior art.

The preferred modes of the invention are described in detail with reference to the accompanying drawings, of which:

FIGS. 1a-1d illustrate a first exemplary thinning process in accordance with the prior art;

FIG. 2 illustrates the results of a thinning process in accordance with the invention;

FIGS. 3a-3d illustrate a second exemplary thinning process in accordance with the prior art;

FIG. 4 illustrates the results of a thinning process in accordance with the invention;

FIG. 5 is a simplified block diagram of a system embodying the invention;

FIG. 6 is a flow diagram illustrating the process performed by the system of FIG. 5;

FIG. 7 is a pictorial diagram depicting how a typical character stroke width is determined in accordance with an exemplary embodiment of the invention;

FIG. 8 is a pictorial diagram illustrating an advantage of the invention; and

FIG. 9 is a flow diagram illustrating the steps performed by the system of FIG. 5 to determine a transition point in the process of FIG. 6.

Referring to FIG. 5, a system embodying the invention includes a document scanner 30 which transmits individual bit map character images to a memory 32. A thinning processor 34 thins each image stored in the memory 32. However, the processor 34 begins by first determining a character stroke thickness typical of the current character image and stores this thickness in a width memory 36 in terms of a pixel count. The processor 34 then removes each layer of boundary pixels from the image, with the constraint that any boundary pixel whose removal would change connectivity in the character image is not removed. The processor 34 increments the contents of a loop count memory 38 with the removal of each successive layer of boundary pixels. As soon as the loop count memory contents equals a predetermined fraction of the count stored in the stroke width memory 36, the processor 34 continues removing subsequent layers of boundary pixels from the image, but with the additional constraint that no end point pixels are removed.

The process performed by the system of FIG. 5 will now be described by reference to FIG. 6. The first step is to store the current character image in the memory 32 and determine a certain character stroke width w which is found in the character (block 40 of FIG. 6). (In the preferred embodiment, this certain stroke width is the minimum character stroke width found in the character.) Then, the loop count stored in the memory 38 is initialized to 1 (block 42). If the loop count is less than w', a predetermined fraction of w, (TRUE branch of block 44), a layer consisting of all boundary pixels or "border points" of the object in the image stored in the memory 32 are erased (block 46 of FIG. 6). However, any pixel whose removal would break a connection in the character image is not removed during this step. Boundary pixels whose removal would not break a connecting in the character image are referred to a "simple" border points.

In the preferred embodiment, the character image is a bi-tonal image in which each pixel is either "ON" or "OFF". The character in the image consists of an object of "ON" pixels in a field of "OFF" pixels. The boundary pixels are the "ON" pixels lying on the edge of the object. Erasing a pixel consists of converting an "ON" pixel to an "OFF" pixel. In the step of block 46, boundary pixels are located using conventional techniques as exemplified in the references discussed previously herein. Whether removal of a particular boundary pixel would break a connection in the image is also determined using conventional techniques as exemplified in the referenced discussed previously herein. For example, a determination is made for each "ON" pixel on the boundary of the character whether its immediate neighbors form a single object when the pixel is turned "OFF". If not, erasure of the pixel of interest would break a connection and therefore its removal is prevented.

In the preferred embodiment, the removal step of block 46 is performed in only two of four possible directions, N, S, E and W indicated in FIG. 3a, namely the N and E directions. Thus, in the step of block 46, only the "north" and "east"-facing boundaries of a square object would be affected. This prevents the width of a given character stroke from being reduced by more than one pixel in a single iteration of the process of FIG. 6.

The loop count stored in the memory 38 is incremented at this point (block 48 of FIG. 6). If the loop count is still less than w' (TRUE branch of block 50), a boundary pixel removal step similar to that of block 46 is performed, except that the removal is performed in the S and W directions only (block 52). As an example, a single layer of west-facing boundary pixels are so labeled in the character image of FIG. 3a. The loop count is again incremented (block 54). At this point, if the previous removal step failed to remove any pixels, the process is deemed to be complete (TRUE branch of block 56). Otherwise (FALSE branch of block 56), the process returns to the step of block 44.

At the step of block 44, if the loop count is found to be not less than w' (FALSE branch of block 44), a boundary pixel removal step similar to that of block 46 is performed, except that no boundary pixels which are end points are removed in this step (block 58). The process then returns to the step of block 48 and continues in the manner described above.

At the step of block 50, if the loop count is found to be not less than w' (FALSE branch of block 50), a boundary pixel removal step similar to that of block 52 is performed, except that no boundary pixels which are end points are removed in this step (block 60). The process then returns to the step of block 54 and continues in the manner described above.

In the preferred embodiment of the invention, w is determined by the processor 34 as the smallest character stroke width found in the current character image stored in the memory 32 and w'=w/f, where f=2 in the preferred embodiment. FIG. 7 illustrates the preferred method of determining w. Horizontal and vertical intercept lines 70, 72 are superimposed on the character image (which in the case of FIG. 7 is the image of a letter "E"). The locations along each intercept line 70, 72 of each intersection with a boundary of a character stroke is noted and the distance between each pair of intersections spanning a character stroke is determined. The intersections or "intercepts" are indicated in FIG. 7 by X's. From all of the distances thus determined from a given character image, a particular character stroke width w is determined. In the preferred embodiment, w is the smallest of these distances, or the minimum character stroke width.

FIG. 8 illustrates the advantage of setting w'=w/2. A character stroke 74 of width w.sub.S surrounds its skeleton line image (indicated by dashed line). The end point 75 of the skeleton is preferably set back from the actual end 76 of the character stroke 74 by w.sub.S /2 because the character stroke width decreases near the stroke end 76 by virtue of the rounding of the corners 78, 79 of the stroke 74. Setting w'=w.sub.S /2 will preserve the end point 75 of the skeleton through successive boundary pixel removal steps.

The process for determining w' is illustrated in FIG. 9. The locations of the intercept lines 70, 72 are computed (block 80 of FIG. 9). Then, the distances between pairs of intersections spanning individual character strokes are computed along the horizontal intercept line 70 (block 82) and along the vertical intercept line 72 (block 84). These distances are all sorted to find the shortest distance w.sub.S (block 86). The value w'=w.sub.S /2 is then stored in the width memory 36 in terms of the number of pixels spanned by the width w'. However, if w.sub.S exceeds a predetermined maximum character stroke width, then the predetermined maximum character stroke width is stored in the width memory 36 instead of w'. The predetermined width is a selected fraction of either the height or width of the character image, depending upon the anticipated font or shape of the character in the image.

A computer program which implements the invention is listed in C-language in Appendices A and B. The portion of the program in Appendix A performs the character thinning process of the invention (the process of FIG. 6). The portion of the program in Appendix B performs the computation of w' (the process of FIG. 9).

The invention is useful for thinning characters in preparation for optical character recognition. An advantage of the invention is that the characters thinned by the invention are relatively free of confusing artifacts characteristic of prior thinning processes.

While the invention has been described in detail by specific reference to its preferred embodiments, it is understood that variations and modifications thereof may be made without departing from the true spirit and scope of the invention. ##SPC1##