Method for recognizing a machine encoded character

An optical character recognition system and method therefor is disclosed for reading a machine encoded character font, such as the E13B magnetic ink character (MICR) font. The digitized data of an optical scan band of the document to be read is read by an optical scanner and stored in memory. A two pass operation of the digitized data is then performed by the respective algorithms of the system to locate and recognize the characters read.

BACKGROUND OF THE INVENTION 
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. 
SUMMARY OF THE INVENTION 
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.

DETAILED DESCRIPTION 
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. 
TABLE 1 
______________________________________ 
Con- 
dition 
Number Condition Description 
______________________________________ 
1 Column 1 contains at least 5 consecutive blacks 
2 Column 0 doesn't contain at least 5 consecutive 
blacks 
3 Row 1 contains at least 3 consecutive blacks 
4 Row 0 doesn't contain at least 3 consecutive 
blacks 
5 Each row 1 through 13 contains at least one 
black 
6 At least one of rows 19 through 21 doesn't contain 2 
or more consecutive blacks 
7 At least one of columns 14 through 17 doesn't contain 2 
or more consecutive blacks 
8 At least one of rows 14 through 16 doesn't contain 2 
or more consecutive blacks 
9 At least one of rows 1 through 3 doesn't contain 2 or 
more consecutive blacks 
10 Each row 6 through 12 contains at least one 
black 
11 Row 6 contains at least 3 consecutive blacks 
12 Row 5 doesn't contain at least 3 consecutive 
blacks 
______________________________________ 
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.