Method for Recognizing a Machine Encoded Character

This invention relates to a method for recognizing a machine encoded character font and more particularly to an accurate character finding and recognition algorithm for a more reliable optical character recognition method.

For documents which can frequently be found to have within a scan band, backgrounds, teller bank stamps, or customer signatures, optical character recognition of a machine encoded character font is difficult. When no optical clear band exists, backgrounds, signatures, etc. can be interpreted as characters thereby leading to rejected, misread (substituted), or extra (a blank location interpreted as data) characters.

Optical character recognition of a machine encoded character font, such as the E13B Magnetic Ink Character Recognition (MICR) font, is a difficult process as no optical standard exists for this font because the E13B characters were originally designed for magnetic reading and recognition. Because of the lack of an Optical Character Recognition (OCR) standard, foreign signals such as customers' signatures, bank teller stamps, scenic check backgrounds, etc., can be overlayed on top of the E13B MICR characters. These foreign signals will also be lifted optically together with the E13B MICR characters resulting in increased character rejects and misreads. Precise location of the E13B MICR characters within the scan band is a difficult but very important task for any optical character recognition scheme. Characters not precisely located can be rejected or misread due to the increased background noise of the optical E13B scan band.

Previous optical character recognition methods utilize a single pass character location and recognition approach. This has the disadvantage in that any MICR character would have to be precisely located by a fairly sophisticated and accurate character finding and recognition algorithm. The present invention is an optical character recognition technique devised to recognize E13B font MICR characters. The optical character recognition technique of the present invention utilizes a two pass operation wherein the MICR scan band image is processed two times. The two passes utilized by the present invention for the optical location and recognition of the E13B font character results in a reliable recognition of the E13B characters in an optically contaminated scan band.

In accordance with the present invention a new optical character recognition technique has been devised. The present invention utilizes a method for optically reading and determining machine encoded characters from a printed document. The method comprises the steps of scanning an area of the printed document to be read, outputting digitized data and storing the digitized data. The digitized data is analyzed for ascertaining the existence of determinable characters and an associated starting location for each determinable character, the starting locations being stored in a location table. The machine encoded character for each starting location stored in the location table is then determined. The location table is edited for predicting the probable starting locations of additional characters, including blanks, and the additional characters are determined based upon the predicted location.

From the foregoing it can be seen that it is a primary object of the present invention to provide an optical character recognition method for determining a machine-encoded character font.

These and other objects of the present invention will become more apparent when taken in conjunction with the following description and attached drawings, wherein like characters indicate like parts, and which drawings form a part of the present application.

FIG. 1 shows a block diagram of an optical character recognition system;

FIG. 2 is a functional flow diagram of the optical character recognition system of the present invention;

FIG. 3 shows a sample X--Y coordinate table which might be generated by the character finding algorithm of the present invention;

FIG. 4 is a version of the X--Y coordinate table of FIG. 3 after the editing function of the present invention has been performed;

FIG. 5 depicts the results of the steps in the optical character recognition process of the present invention;

FIG. 6 shows the organization of the working buffer utilized by the character finding algorithm of the present invention;

FIG. 7 depicts an 18-bit wide by 22-bit high matrix within the working buffer of the optical character recognition system of the present invention;

FIG. 8 shows the E13B Font Character Templates of the preferred embodiment of the present invention;

FIG. 9 shows the shift positions utilized in the character recognition process of the present invention; and

FIG. 10 depicts an example of the character recognition process of the present invention.

The optical character recognition system 10, herein referred to as the system 10, is shown in FIG. 1. The system 10 comprises an optical scanner 12 which is coupled to a buffer 14, the optical scanner 12 being under the control of a controller 16. The buffer 14, at least sufficiently large to store the digitized data of an entire optical scan area of the document 1 to be read having a machine-encoded character font within the optical scan area, is also coupled to controller 16. The controller 16 is further coupled to a ROM 18 which stores the control firmware, masks, algorithms, etc., and to a working storage memory 20 for storing the digitized data of a character matrix utilized by the algorithms for determining the characters and for storing intermediate and final results. The output of the working storage memory 20 forms the output of the system 10, the results in working storage memory 20 containing a digital representation indicative of the characters read from the document. Controller 16 contains the registers, control circuitry, and arithmetic and logic unit as required to perform the steps required by the character finding and character recognition algorithms. Controller 16 may be a CPU or microprocessor known in the art and is not discussed further herein.

An overview of the entire character recognition operation will now be described in conjunction with FIGS. 1 and 2. The document 1 containing the characters to be read is introduced into the system 10 via some document transport mechanism (not shown) which places the document 1 in a position to be read by the optical scanner 12. Fundamentally, any type optical scanner 12 well known in the art can be used in which the output data from the optical scanner 12 may be serially fed column-wide into a register. In the preferred embodiment, the system 10 is designed to process an E13B MICR optical scan band of 96-bits high and 1348-bits wide based on a scanning resolution of 154 pixels per inch (i.e., a scan band about 5/8 of an inch high and 8.75 inches long). The digitized data for the entire scan band of document 1 is stored in buffer 14 comprising the data input step (block 30).

After all the data has been inputted, the character finder algorithm is initiated (block 35). The E13B optical scan band data stored in buffer 14 is passed through the character finding algorithm. An X--Y character start location is determined, and stored in working storage memory 20 with each potential E13B character found. Assuming the scan band is scanned from top to bottom, with successive scanning lines moving from right to left, the starting location becomes the character start position of the top right hand corner of the potential character that was located. When a potential E13B character has been located, the character recognition of the potential character is initiated (block 40). The character recognition takes place by obtaining a data block 16 pixels wide by 20 pixels high from the X--Y character start coordinate generated from the above step. The character start position is designated as the top righthand corner of the located character. The coordinates of the block become (X, X+15), (Y, Y+19). This data block is now used for the character recognition process, discussed in detail hereinunder. Blocks 35 and 40 comprise Pass 1.

An editing function (block 45) is then performed by taking the X--Y coordinates and more accurately defining the E13B MICR band. This is done by taking the Y coordinates, determining the most frequent Y value (Y1) of all of the starting locations in Pass 1 and then eliminating any coordinates whose values do not fall into the range Y1.+-.D (block 45). The value of D is determined by taking into consideration the amount of document skew that will be found in the transport mechanism, as well as variations in the printing of the E13B characters (notably, the vertical misalignment). The preferred embodiment utilizing D has the value of eight (8). By way of illustrating the editing function, reference is made to FIGS. 3 and 4. FIG. 3 is a sample of an X--Y coordinate table which might be generated by the character finding algorithm. In the example set forth in FIG. 3, the most frequently occurring Y coordinate of the twelve starting locations listed there is 36. Thus the range of allowable Y values lies between 28 and 44, thereby eliminating coordinate 7. This character was a misread (a noisy document background image being mistaken as an E13B MICR character). By analyzing the X--Y coordinates remaining in FIG. 3 with regards to character pitch, line skew, etc., it is apparent that there is no progressive change in the Y values and therefore no skew of the document relative to its line of travel. The most common difference between successive X values is 19, but there is a distance of 5.times.19 between the X coordinates of locations 9 and 10 and a distance of 2.times.19 between locations 11 and 12. Using this information, the editing function then predicts where additional E13B characters can be located by assigning X--Y character start coordinates to gaps in the buffer table. FIG. 4, the complete edited version of the X--Y coordinate table of FIG. 3, shows gaps between coordinates 9 and 10, between 11 and 12, and after 12. (In this example the X boundary ends at coordinate X=360.)

It will be recognized by those skilled in the art that the editing function may be achieved in a variety of ways. For example, the editing function can be done on a document basis, or the document may be segmented into fields with the X--Y coordinates associated within each field treated separately. Treating the document by segments has advantages when the E13B characters are printed at different times, as is true when a check has the amount entered on it by a bank at the time the check is cashed. This approach can compensate for any differences in the vertical positions between the fields printed at different times.

Referring back to FIG. 2, Pass 2 then takes each of the predicted X--Y character start locations generated by the edit step, obtains a 16.times.20 data block from buffer 14, and performs character recognition to determine the MICR character or "blank" condition (block 50). The character recognition algorithm will be described in detail hereinunder. The controller 16 then performs a second editing function combining the recognized characters from Pass 1 and Pass 2 in the sequence in which they appear on the document image (block 55). The output data, which is the digital representation of the characters read from the document, is then outputted (block 60) or made available to a subsequent processor or user. Thus, the two pass character recognition technique needs only a fairly simple character finding algorithm, since in Pass 1, character finding is based on locating relatively easily recognizable characters. In Pass 2, no time need be wasted looking at areas of the scan band where no E13B characters were initially found since the X--Y coordinates of the characters have already been accurately predicted.

FIG. 5 synopsizes the results of the steps of the optical character recognition process. FIG. 5A shows the original MICR scan band having a length L and a width W and which also includes some foreign material. (In the preferred embodiment, the value of L is 8 3/4 inches max, and the value of W is 5/8 inches.) FIG. 5B depicts possible MICR characters as would be located by the character finder algorithm with their X--Y character start coordinates. FIG. 5C shows the characters recognized after Pass 1, each cross-hatched rectangle signifying a character that was not recognized. FIG. 5D depicts the revised MICR band with the predicted X--Y character start positions represented by X symbols for characters not previously found or determined for use in Pass 2. FIG. 5E shows the characters recognized in Pass 2, the symbols being blanks on the document. Handling of any rejected characters remaining after Pass 2, such as the left-most "2" character, can be performed in a number of ways. The operator of the system 10 could input the correct character from the document, or from a screen which would display the particular character. Input/output devices for implementing this approach, and devices for implementing alternative manual input corrective schemes are not shown in System 10 and will not be discussed further herein as such discussion is not necessary for understanding the present invention. FIG. 5A includes the X-Y coordinate system utilized by the system 10.

The character finding technique used to precisely locate E13B characters will now be described. The working storage memory 20 of the preferred embodiment consists of five 256.times.4 RAMs organized as a recirculating shift register. The E13B optical scan band data stored in buffer 14 is transferred to working storage memory 20 on a column basis, the working storage memory 20 being organized as a two-dimensional matrix to contain a 96 bit high (corresponding to the height of the optical scan area) by 20 bit wide working buffer. The working buffer is organized as shown in FIG. 6, a little larger than the amount for one character. The working buffer is first filled and then continually updated by column after the character finding algorithm has processed the working buffer. The working buffer is updated by fetching the next column of 96-bit data and storing that data in the bit 19 column of the working buffer, the data already contained therein being shifted such that bits in column 19 shift to columns 18 (i.e. bit 19 word 1 shifts to bit 18 word 1, bit 19 word 2 shifts to bit 18 word 2, . . . and bit 19 word 96 shifts to bit 18 word 96), bits 18 shift to bits 17, etc. The character finder algorithm continually monitors an 18-bit wide by 22-bit high matrix within the working buffer and looks for twelve possible conditions, to determine whether an E13B character has been located. The twelve conditions are delineated in Table 1 below. The character finding conditions related to the 18.times.22-bit matrix are shown in FIG. 7.

Conditions 1 through 7 are used to locate all E13B characters with the exception of the dash symbol. All conditions 1 through 7 have to be true. As shown in FIG. 7, conditions 1 and 2 are fulfilled in columns 1 and 0 and are used to locate the transition of the right edge of the character. Conditions 3 and 4 are fulfilled in rows 1 and 0 and are used to locate the transition to the top edge of the character. Condition 5 determines that the character is not physically broken. Condition 6 locates a white boundary to the bottom of the character. Condition 7 locates a white boundary to the left of the character. This maintains the condition that characters are physically separated.

Conditions 6 through 12 (when all conditions are true) are used to locate the dash symbol. Conditions 8 and 9 locate a white boundary above and below the dash symbol. This prevents false triggering of the dash symbol when strong document backgrounds prevail in the scan band. Condition 10 maintains that the dash symbol is not physically broken. Condition 11 and 12 locates the transition to the top edge of the dash symbol.

As the character finder receives its data, an X-Y co-ordinate generator is updated. The X-Y co-ordinate generator, or position co-ordinate generator is a pair of storage cells which contain an X-coordinate and a Y-coordinate. This X-Y co-ordinate is the character start position of the located character, corresponding to the top right hand corner of this character (intersection of column 1 and row 1 of the character finding matrix).

The character recognition algorithm, which will now be described, utilizes a mask (template) matching techniques. Each template consists of black (character areas), white (non-character areas) and don't care elements (ambiguous areas of a character, notably around the character boundaries where a black/white decision is difficult, due to printing and scanning character imperfections). FIG. 8 shows the E13B Font Character Templates (Masks) of the preferred embodiment based on a scanning resolution of 154 pixels per inch.

Each character to be recognized is set up to reside in a data matrix 16 bits wide by 20 bits high. Each of the 14 E13B templates (one per each E13B character) reside in a matrix 28 bits wide by 18 bits high. Each character template (28.times.18) is actually composed of two subtemplates, each (14.times.18), such that each subtemplate can be shifted over nine positions as shown in FIG. 9 (3 vertical by 3 horizontal) of the data matrix to obtain a best fit, the shaded portion being the 14.times.18 bit matrix of the subtemplates. One subtemplate contains the black/white states, the other subtemplate contains the don't care states. For each of the nine shifting positions, the (14.times.18) don't care state subtemplate is first compared to the data matrix to determine which bits of the data matrix become don't cares. These don't care bits are then ignored and the remaining bits of the data matrix are then compared to the (14.times.18) black/white state subtemplate to determine the total number of mismatched bits (elements). In addition, for shift positions 2, 5 and 8 the number of black bits which reside in column 1 of the data matrix (the column which is not being compared) are added to the respective total mismatch count of each shift position. For shifting positions 3, 6 and 9, columns 1 and 2 are added to the respective totals. This is done to prevent misreads. Thus each pair of character subtemplates will generate nine totals, each total corresponding to the total number of mismatched points for one shifting position.

The character recognition process will be described by an example, making references to FIG. 10. The fourteen (14) E13B character templates are compared to a potential character, TR is the transmit character, AM is the amount character, ON is the ON US character, and DA is the dash character. For each character template, nine totals are generated, one for each shifting position. Each total is the total number of mismatched elements between the character template and the data matrix, FIG. 10 showing the totals. The minimum of the nine totals is found and stored for each character template, thereby generating 14 numbers. The minimum and next minimum values of the 14 numbers are then determined, the numbers being 2 and 30 as indicated by the arrows in FIG. 10. Finally, if the minimum value is less than a preset value (X1), and the difference between the minimum and next minimum value exceeds a second preset value (X2), then the character which had the minimum value becomes the recognized character.

Thus, in the example

MIN 1=2

MIN 2=30

In the preferred embodiment the values of X1 and X2 are set at 36 and 8 for Pass 1, and 48 and 9 for Pass 2, respectively. (In Pass 1, since the entire scan band is being processed, the values of X1 nd X2 are set to prevent false recognition and thereby erroneous XY character start coordinates. In Pass 2, the values of X1 and X2 are raised since the scan band search has been considerably narrowed.) Hence, since MIN 1 is less than 48 and MIN 2-MIN 1 is greater than 9, the character is recognized as the "0". If the above criteria are not met then the character is considered a reject.

Although the above process describes an essentially sequential operation, it will be recognized by those skilled in the art that variations may exist within the true scope of the invention. One such variation includes overlapping the optical scanner 12 read and buffer 14 writing with the character finding algorithm processing.

While there has been shown what is considered to be the preferred embodiment of the invention, it will be manifest that many changes and modifications can be made therein without departing from the essential spirit and scope of the invention. It is intended therefore in the annexed claims to cover all such changes and modifications which fall within the true scope of the invention.