This invention relates to and is an improvement of the technique described in copending application Ser. No. 848,521, filed Apr. 7, 1986, by which an alphanumeric character is recognized by the geographical features (e.g. bays and lagoons) which comprise that character.
Optical character recognition (OCR) devices have long been used to sense and interpret alphanumeric characters that, typically, are provided on a printed page. However, as pointed out in the aforementioned application, such devices usually are limited to the extent that characters are recognizable only if they are printed in one (or, at best, a limited few) predetermined font. Printed characters which, nevertheless, may be clear and formed uniformly as, for example, by a typewriter or other printing machine, will not be recognized if they are formed in some other font.
Another operating limitation of conventional optical character recognition devices that is mentioned in that patent application relates to what is known as "line finding" and "segmentation". A line finding operation is carried out by many conventional OCR devices to locate the lines of characters that are printed on a page. This distinguishes character lines from the spaces between lines and usually is implemented by detecting the distribution of pixel information in the vertical direction. A greater concentration of black pixels represents a line of characters and a low concentration represents a space between lines.
A segmentation operation is intended to locate the spacing between characters in a line of characters. This isolates a block of pixel data, which then is presumed to be limited solely to a character to be identified, whereafter the data block is examined and recognized. Typical segmentation operations are successful if the characters in a line are spaced uniformly and are printed in, for example, Roman-type font. Characters that are printed at angles, such as italics, often cannot be isolated. Rather, the segmentation operation senses portions of adjacent characters, presumes that such portions comprise a single character, and then attempts, unsuccessfully to identify a "character" formed of such portions. Similarly, typical segmentation operations often cannot separate (or "segment") characters that are smudged or blurred because of the lack of a well-defined space between such characters. Thus, a block of data representing a character to be identified cannot be formed. Likewise, a break that might be present in a character may be interpreted erroneously as a space between adjacent characters, resulting in two separate blocks representing partial characters rather than a single block representing a whole (albeit broken) character.
The aforementioned application suggests that these disadvantages of conventional optical character recognition devices are attributed primarily to the fact that, in most such devices, character segmentation (or separation) might not be successful, thus impeding the comparison of a properly scanned character to a reference, or standard geometric form of that character. Significant deviations between the scanned and reference characters, such as differences in font, misalignment of the scanned character, apparent "connections" between independent characters, or "breaks" in a single character, largely due to improper character segmentation, prevent accurate identification. While various comparison techniques have been proposed heretofore, most optical character recognition methods rely upon a "template" comparison of scanned characters in order to identify those characters.
In the OCR technique disclosed in the above-mentioned application, predetermined geographical features in a scanned character are detected, and the detected geographical features are compared to a store of particular geographical features of which known alphanumeric characters are comprised. The scanned character is identified as the alphanumeric character having geographical features which compare favorably to the detected geographical features. The relative positions of the detected geographical features with respect to each other is a primary factor in identifying the scanned character.
The detected geographical features are lagoons, which are formed as enclosed areas, and bays, which are formed as open areas. The types and relative positions of the bays, as well as the relative positions of those bays to detected lagoons, determine the identity of the scanned character.
In the technique of the aforementioned application, the number of "class 1" and "class 3" points included in the scanned area are detected. A "class 1" point is defined as the free end of a link (a link is a portion of a line included in the character), and a "class 3" point is defined as a point formed by the juncture of three links. Also considered are "class 4" points which are defined as points formed by the juncture of four links; and one "class 4" point is equivalent to two "class 3" points. The number of "class 1" and "class 3" points included in the scanned character significantly narrows the set of characters in which the scanned character is included. The geographical features of the scanned character then are compared to the geographical features of the characters in that set. Since geographical features are detected and analyzed, the particular font of which the character is formed is not significant because a given character includes certain minimum geographical features irrespective of its font.
In carrying out this geofeature identification technique, pixels are detected as a character is scanned, and the coordinates of each detected pixel (for example, the XY coordinates) are stored. Only the XY coordinate at the start of a link and the XY coordinate at its end need be stored; and these XY coordinates are determined and stored in real time, as the character is scanned. Depending upon the number of links connected to a particular XY coordinate, the class of the point defined by that XY coordinate is established. The presence of lagoons and bays is ascertained by tracing paths, in predetermined directions, from one connected link to the next, that is, from one stored XY coordinate at the beginning of a link to the next stored XY coordinate which, in most cases, is the end point of one link and the beginning point of a connected link. A lagoon is sensed when the traced path returns to a particular XY coordinate included therein; and a bay is ascertained as a function of changes in the X and Y directions as a path is traced.