This invention relates, but is not limited, to optical character recognition systems such as optical character readers and, more particularly, to methods and apparatus for correcting for skew conditions in text lines being optically read.
A basic requirement for Optical Character Recognition (OCR) is to locate and bound each line of text on a document. For the usual OCR application, this is a constrained task in that apriori it is known that the page contains one font, all character spaces are defined, and all text line spaces are given. Furthermore, the document usually contains only textual material, or, if non-textual data exists, it is field-formatted to eliminate it from consideration in line finding. Text line tilt is carefully controlled, and many commercial OCR machines utilize the top line of the text on a page for a reference to physically deskew the page prior to line finding.
For many standard fonts, FIG. 1 is illustrative of the basic types of character elements. Generally, capital letters, such as the "A" and "B", are bounded by levels 2 and 4. Lower case such as the "a", is bounded by levels 3 and 4, and is shorter in stature than the capitals. Lower case such as the "b", is constrained by levels 1 and 4, and is taller than the capitals. Lower case such as the "g", is bounded by levels 3 and 5, and is about as tall as the capitals, but with a segment dropping below the capital bottoms. Punctuation marks such as the period, quotations, and commas are short in stature, and are attached to either levels 2 or 4. Arithmetic operators such as the plus sign or asterisk are also short, and congregate around level 3.
A typical situation of skewing is shown in FIG. 2. The document 10 contains lines of text generally indicated as 12. As document 10 moves through an optical character reader in the direction of arrow 14, the scanning optics continually scan across the document 10 in the direction of the arrow 16, which is normal to the document margin 18. If the text margin 20 is parallel to the document margin 18, such a scanning pattern causes each line of text to be scanned along its length as it passes under the optic scanning head. As shown in FIG. 2, however, in the skewed document 10, the text margin 20 is not parallel to the document margin 18 but, rather, is at an angle to it. Thus, the lines of text 12 are at the same angle to the optic scan direction of arrow 16. As a consequence, for example, instead of scanning the first text line 22 and then the second line 24, the right half of line 22 (as FIG. 2 is viewed) is encountered first, followed by the left half of line 22 and the right half of line 24, and finally the left half of line 24. If the data thus scanned are then searched on the normal basis, it yields a meaningless interpretation of the text 12. In a similar fashion, depending on interline spacing and document tilt, the left portion of text line 22 may be encountered on the early part of the scan while the right portion of that line 22 is encountered later in the scan.
In certain optical character recognition applications, it is essential that character line rotational effects be removed prior to processing to avoid the generation of meaningless date. Such rotations are usually caused by document feed skewing or typewriter induced skewed text in the actual source document such as that of FIG. 2.
One prior art method of circumventing the skew problem is to physically rotate the document or the scanning head in the machine. Such an approach is inconvenient at best, however. What would be preferable, and is therefore the object of the present invention, is a completely non-mechanical correction system and method which identifies and bounds lines of text and which:
1. Automatically accommodates to arbitrary fonts and sizes thereof.
2. Automatically accommodates to inter-mixed fonts.
3. Automatically accepts random inter-character and inter-text line spacings.
4. Automatically accommodates to a wide range of document skew angles.
5. Automatically accepts text lines of variable lengths and locations.
6. Automatically recognizes non-textual data and ignores it in text line finding and bounding.