US 4,797,938 AGrant
Method of Identifying Magnetic Ink (MICR) Characters
Issue Date:1989-01-10
•8 Claims
•13 Drawing Sheets
Abstract
A method of improving the accuracy of identifying or reading magnetic ink characters (MICR) of the type used on checks and other documents, by choosing key values of a waveform selected using one of several templates which best fits recognized peaks. The steps of the improved method include periodically sampling the signal generated from a magnetic read head, digitizing each sample, locating peaks (in an absolute-value sense), comparing the pattern of peaks against templates (stored values preferably in the form of a saw-tooth) representative of various periods and offsets between positive and negative peaks to determine which template fits the sensed peaks best, then using that template to select samples for identification of the character. The samples thus selected are preferably in the location of the peaks and zero-crossings predicted by the best template or pattern, but are not necessarily the peaks of zero-crossings themselves. If the character is not recognized, it may be identified as a reject, or alternatively, another template (such as the next best template) may be used. Advantageously, means for differentiating an ink spot from a character are also included in the system as is a system which normalizes the character over all the peaks and not just the initial perceived peak of the character.
Metadata
Assignee
- International Business Machines Corporation
Inventor
- Terry A. Will
Application Information
Application Number:US 1787934
Filing Date:1988-03-31
Priority Date:1985-10-15
Art Unit:266
Classifications
IPC:
G06K 900
Field of Search:
3822357;29;64;53449
Patent Drawings (13 sheets)
Description
Background of the Invention
1. Field of the Invention
The present invention relates to improvements in methods of identifying magnetic ink characters. More particularly, the present invention relates to identification of characters which are written in magnetic ink and read at high speed by check reader/sorters. This invention has particular application, but is not necessarily limited to characters which are printed in magnetic ink (referred to as Magnetic Ink Character Recognition, or MICR) in a standardized format or font such as the "E13B" font and are included spaced from the lower edge of bank checks, deposit slips and other documents. Such bank checks or other documents are typically processed on a machine such as an IBM Model 3694 document processor (also referred to as a check reader/sorter) at speeds of 200-1000 documents per minute and with approximately 250-1000 characters passing by a single magnetic read head each second.
2. Prior Art
Several different techniques have previously been used for reading MICR characters on checks and other documents at varying speeds. Some reading techniques are based upon multiple vertically-spaced magnetic reading heads, each head for reading a horizontal portion or slice of the each entire code line (or each character, in sequence.) Such character machines are generally (at least in relative terms) expensive because of the additional hardware and logic required to coordinate, correlate and interpret the readings of the multiple heads. Another technique is to read characters optically using an optical character recognition (OCR) apparatus, either by itself or in combination with a magnetic sensing apparatus.
Another technique for reading magnetic ink character includes a rather large single magnetic read head which spans the entire height of a magnetic ink character. A voltage proportional to the amount of flux change sensed by the reading head is generated as an indication of the character features in such single gap magnetic ink character readers. Such machines are generally easier to design and build and less expensive, but have the limitation of requiring sophisticated algorithms to determine the characters which have been read. These machines have the limitation that either the characters on some number of the documents are not read (identified) at all (a condition designated as a "reject" in the industry) or if read, generates an identification of a character other than the character which is printed. The improper identification is referred to in the industry as a "substitution". The banking industry has determined that both substitutions and rejects are undesirable, yet the number of checks and other MICR-coded documents handled each year is ever increasing, requiring more reliable equipment in the banking and similar channels.
While checks are preprinted with MICR bank routing and customer account numbers when blank checks are printed, the right portion of the MICR-line is left blank and reserved for the amount of the check. This amount field is typically added in a process called "inscribing" the amount field when the first bank receives the check. Various check inscribing machines are commercially available and in use today, each of which is somewhat different in the quality with which characters are formed on the check and in terms of spacing between features on the individual characters.
In some machines, the checks can have perfectly formed characters, but apparatus for moving the check past the magnetic read heads may not move the check at a uniform rate, making the code line difficult to read.
A concept of "re-timing" or adjusting recognition logic for variations in speed of transport or printing variations is known in single gap magnetic reading systems of the prior art. All such known systems, however, make adjustments on the fly, or in real time, based upon the past history and not in response to a total character. Such systems, which are disclosed in U.S. Pat. Nos. 3,316,536; 3,528,058; and 4,356,472; can not adjust for isolated variations, and therefore can lead to errors in the reading of magnetic ink characters.
The magnetic ink character recognition systems in use today have the additional disadvantage that a small ink spot in certain regions of the character prevent the reading of the character, even if the remainder of the character is perfectly legible. This occurs, in part, because some machines assume that the first peak detected must normalize the reading for the entire character. While that system may work well when the first peak of a read character is a part of a real character, the reading of an ink spot as the first character "portion" ruins the system, leading to either a reject or a substitution in many cases, both of which are undesirable.
Yet another method of identifying characters simply identifies character peaks, either ignoring their location completely or assuming that the peaks occur at regular time intervals after an opening peak. U.S. Pat. Nos. 3,851,309 and 4,143,355 are illustrative of this technique. However, this technique is not reliable in the identification of characters, because the timing of the peaks is important to the proper recognition of characters (e.g., to determine whether a character is a "2" or a "5", the timing between the peaks is the significant factor.)
U.S. Pat. No. 2,995,727 illustrates a system for comparing signals to determine their similarity in a complex amplitude versus time arrangement such as speech and character recognition. U.S. Pat. No. 3,605,092 detects MICR characters while avoiding misstarts by looking at the slope of the MICR wave form to determine whether a peak is present. U.S. Pat. No. 4,148,010 reads magnetic ink characters with the timing set from the center of gravity of the sensed peaks.
U.S. Pat. No. 4,245,211 includes a method of adjusting the system timing to align the character feature changes with the intervals; it employs a phased locked loop response to the detected peaks to accomplish this.
Other limitations and disadvantages are well known to those skilled in the art of reading magnetic ink characters and processing the information obtained by magnetic reading heads.
Summary of the Invention
The present invention overcomes the limitations and disadvantages of the present invention by providing a system for improved character reading in a single magnetic reading head. This improvement reduces the reject rate without a corresponding increase in the substitution rate.
The present invention achieves the imprvoed character reading by periodically sampling the signal generated from a magnetic read head, digitizing each sample, locating peaks (in an absolute-value sense), comparing the pattern of peaks against templates (stored values preferably in the form of a saw-tooth) representative of various periods and offsets between positive and negative peaks to determine which template fits the sensed peaks best, then using that template to select samples for identification of the character. The samples thus selected are preferably in the location of the peaks and zero-crossings predicted by the best template or pattern, but are not necessarily the peaks or zero-crossings themselves.
This invention has the advantageous effect that characters which have been printed by a low quality inscriber may be read without substantial rejects or substitutions being incurred. Thus, it has the advantage that a greater percentage of the documents which a bank or other establishment might have can be read using automated (high speed) equipment, rather than low speed manual processing which is more subject to error.
A further advantage of the present system is that the appropriate timing for a character is determined by reference to the entire chracter, and not merely by a portion of that character. This allows the system to compensate for random, or not periodic, variations in the reading of a character. The application of the adjustment process to a stored character as provided in the present invention also allows a second pattern to be applied to the character should the character remain unidentified after the first pattern has been used. Of course, those systems which provide retiming on the fly have lost forever the information which might have been acquired through the use of a second pattern.
The provision of an accurate and dependable method for identifying characters allows for the system of the present invention to ignore small ink spots which otherwise lead to a reject (unread) character, or worse yet, a substituted character, in which the system reads incorrectly the character which is there. This ignoring of ink spots is accomplished in the present system by retrying a character which cannot be identified by ignoring the introductory peak if the distance between characters is consistent with the opening peak being an ink spot. Later ink spots may be automatically ignored merely by being located at places where peaks are not expected.
In the present system, each character is normalized over all the peaks in the character and not just the opening peak of the character, which may be abnormally large or small. This normalizing, or scaling the magnetic reading of the character, based upon all of the peaks allows a narrower band to be specified for the character without sacrificing accuracy in the recognition of the character.
Other objects and advantages of the present invention will be apparent to those skilled in the art in view of the following description of the preferred embodiment, taken together with the appended claims and the accompanying drawings.
Brief Description of the Drawings
FIG. 1 is a perspective view of a check having a MICR code line and a magnetic character reading system.
FIG. 2 is a time/voltage plot of electrical signals which may be produced by the magnetic ink character reading system of FIG. 1 when reading characters from the E13B type font printed on checks and other documents in the United States.
FIG. 3 is a block diagram flow chart of the information processing used to process the information read from the a check in FIG. 1, particularly signals shown in FIG. 2.
FIGS. 4-7 are detailed block diagrams of portions of the the block diagram of FIG. 3.
FIGS. 8A-8D are plots of the electrical signal reading of one character from a representative document, illustrating the character and various templates used to select certain key values from the plot in accordance with the present invention.
Best Mode of Carrying Out the Invention
FIG. 1 illustrates the environment of one application of the present invention in which a check 10 bearing a code line 12 including a plurality of magnetic ink characters 14 is carried past a single gap magnetic read head 20. The check 10 (or other document) is driven in its preferred embodiment at a relatively uniform rate by drive mechanism such as rollers (not shown.) The environment for the check magnetic ink reader of the present invention might be an IBM Model 3694 check reader/sorter which is presently known, but many other check readers are known and used.
FIG. 2 illustrates the magnetic ink chracters of a font known as E13B used in processing checks in the United States. The associated electrical waveform generated by scanning from right to left on the check as the viewer looks at the codeline 12 on the check are also shown in this view associated with each such character. This font is limited to the characters shown in this view, and is an industry standard as agreed by the American Bankers Association, but other predetermined fonts could be used to advantage in the present invention.
FIG. 3 shows a block diagram of the system of the present invention. As shown herein, the magnetic read head 20 described in connection with FIG. 1 provides a time-varying analog signal to band pass filter and amplifier 30, which in turn is coupled to an analog to digital converter 40 to digitize the signals on a periodic basis. The digitized values are then stored sequentially in a waveform storage random access memory 50, which is used an an input to the digital signal processor 60 which is described in connection with FIGS. 4-7. The digital signal processor 60 uses two tables, a character location table 62 and a peak location table 64 interactively during its processing as described later. The output from the signal processor 60 are recognized characters shown at block 66. Block 68 depicts a table of time zone widths and time zone offsets which are stored as a result of testing various templates against a pattern of identified peaks, preferably in a sorted arrangement with the best template first.
Other inputs to the digital signal processor 60 are a time zone correlation patterns read-only-memory (ROM) 70 and a class limits read-only-memory 80, both of which will also be described in greater detail in connection with FIGS. 4-7.
FIG. 4 shows the initial processing performed by the digital signal processor 60 of FIG. 3. From a start block 100, control passes to block 110 where the next sample from the waveform storage RAM 50 is obtained. Offset adjustment and digital filtering are performed at the block 120, then at block 130, the updated and corrected value is stored back into the block 50. Next, whether it is a positive or negative peak is determined at block 140 by comparing the present value to its adjacent value, in an absolute sense. If the present value is a relative peak, it is stored in the peak location table 64 via block 150; otherwise, control passes to the block 180 where whether this is the last sample is determined. If this is not the last sample, the process of this FIG. 4 from the block 110 is repeated; if this is the last sample, this FIG. 4 is exited through the connector A (block 190) to FIG. 5, as described later. From block 150, after the peak has been stored, whether this is (or could be) the start of a character is determined at block 160. If this is the start of a character, then at block 170 the location of the start of the character is stored in the character location table 62 before again testing at the block 180 whether this is the last sample and going either to block 190 if it is or to block 110 if it is not.
FIG. 5 shows the continuing processing from the exit block 190 of FIG. 4. At block 200, the location of the next (or first) character is obtained from the character location table 62. At block 210, all peaks associated with that character are obtained from the peak location table 64. At block 220, these peaks associated with this character are tested against respective time zone correlation patterns stored in the ROM 70. Each time zone pattern includes time-values of a repeating pattern, saw-toothed in its preferred embodiment, of slightly differing periods and offsets between its positive and negative peaks as will be discussed later, so that the amount of correlation between the peak pattern and each time zone pattern is noted. At block 230 these correlations are sorted and stored into a table of the time zone widths and offsets from the best correlation to the worst correlation, which correlation is obtained by summing the products of each peak with the stored time zone correlating patterns, the greatest sum then indicating the best fit.
At block 240 then the next (best, starting with the first) time zone width and correlation from the table 68 is then used to attempt to match the pattern at block 250. This is accomplished by using this presumed best pattern to select 15 waveform samples at the peaks and zero-crossings (for example) to identify the waveform character in due course through the following steps. At this point the processing shifts from using the identified peaks to using the selected patterns of presumed peaks and zero crossings from the original waveform storage RAM 50. These 15 samples are then normalized at block 260 to average all of the peaks and not just scale the readings based upon the first peak as prior art systems have done.
Referring now to FIG. 6, the normalized samples are compared to class limits stored in ROM which are representative of maximum and minimums of the selected 15 samples chosen at the block 250 against the historical values determined for each character. This comparison is similar to that proposed by Rohrer and described in IBM Technical Disclosure Bulletin, Volume 23, No. 6, Pages 2261-2262. At block 280, a character is recognized if the sum of the variation from the stored values for class limits in 80 for a given character is less than a preset threshold. If the character is recognized, control transfers to block 310, otherwise, the question of whether a limit on the number of trials has been reached (perhaps only the best six time zone widths and offsets will be tried) is answered. If the character was not identified and the retry limit has not been reached, then control returns to the block 240 for trying the next best time zone pattern. If the retry limit was reached at the block 290, then the character is identified at block 300 as a reject (at least temporarily, see FIG. 7 and the related description) and control continues to block 310 where the character or reject is stored in the recognized characters list 66.
Then, if this is not the last character as determined at block 320, control returns to block 200 (FIG. 5) to get the next character and repeat the process. If this was the last character on a given document, then a first pass in the process of identifying characters has been completed and only the rejects remain to be identified, if possible, as described in connection with FIG. 7 from block 330.
FIG. 7 begins the process of attempting to identify reject characters from the block 330 (the end of FIG. 6), by locating the first reject at block 340 from the recognized character list 66. At block 350, the first peak is ignored and the second peak is presumed to be the beginning of the character. Then at block 360 the time zone selection process of blocks 200-290 is repeated. If the character is identified through this process, then the reject is replaced with the character identified, otherwise the reject status continues and the system decides whether the present reject is the last reject. If it is, the system has been completed and it exits from block 380, otherwise it returns to the block 340 to process the next reject.
FIG. 8 illustrates a waveform 400 of a typical character--in this case a "0"--read by the magnetic head 20 of FIG. 1 and samples at the rate of 80,000 per second. This is in a system in which the checks or other documents are passing the reading head at the rate of 150 inches per second, to permit a nominal value of seven samples per standard MICR time zone. In the ABA standard, each time zone is 0.013 inches in width, although experience has shown that some inscribers print time zones which are either somewhat greater or smaller than the standard.
FIG. 8A, 8B, 8C and 8D illustrate a waveform 400 from a character after reading and digitization, which is stored in the waveform storage RAM 50. Also shown in each figure is the corresponding saw-tooth waveforms 420, 430, 440 and 450 in FIGS. 8A, 8B, 8C and 8D, respectively. Each of the saw-tooth waveforms are stored, in the preferred embodiment for this invention, in the time zone correlation pattern ROM 70. Each saw-tooth pattern includes a positive or upper saw tooth pattern and a lower or negative saw tooth pattern. For ease in description, the upper saw-tooth pattern will be referenced with the suffix "a" (as in 420a for the upper saw tooth pattern in FIG. 8A) and the lower or negative saw-tooth pattern will be referenced by the suffix "b" (as in 420b).
FIG. 8A represents a plot of the saw tooth 420 in which the period of the saw-tooth is chosen to be 7.0 samples per time zone (0.013 inches of travel), with negative peaks in its lower saw tooth portion 420b being two samples advanced from positive peaks in its upper saw-tooth portion 420a. For the purpose of correlation, positive peaks in the actual waveform 400 from the waveform storage RAM 50 are compared with the upper saw tooth pattern (e.g., 420a) and the negative peaks in the waveform 400 stored in the RAM 50 are compared with each lower, or negative, saw-tooth pattern (e.g., 420b).
As shown in FIG. 8A, the waveform 400 includes four peaks (in an absolute value sense, where magnitude is considered and not its sign or direction). These peaks are marked 400a, 400b, 400c, and 400d and represent a relative positive peak, a relative negative peak, a relative positive peak and a relative negative peak, respectively. For each peak location, its stored value is determined and multiplied by a corresponding value for the saw-tooth waveform of the same polarity (positive or negative). Thus, for the peak 400a, its stored value (9) is multiplied by the corresponding value in the saw tooth (at location 420aa) which is 4 to get a first product of 36. Similarly, for the second peak 400b, the product of its value (-8) is multiplied by the value of 420bb (-4) to obtain a second product of 32. Likewise, a third product and a fourth product representing the value of 400c times 420ac and 400d times 420bd are obtained. The sum of all products for a given time zone width and offset are calculated and stored in association with the width and offset for later ordering to determine the best fit. The best fit is defined as the width and offset which produces the greatest sum of the products, thereby indicating the best correlation of the saw-tooth with the actual pattern of the peaks.
For the time zone width and offset shown in FIG. 8A, the sum is 132, calculated as described above. Similar calculations for the time zone width of 7.0 and no offset between positive and negative peaks as shown in FIG. 8B leads to a sum of 98. Likewise, in FIG. 8C, a time zone width of 7.0 and a negative peak offset of -2, or having the negative peaks lead the positive peaks by two periods, leads to a sum of the products of the waveform peaks and the saw-tooth values of 72. In FIG. 8D, the offset between positive and negative peaks is chosen to be zero, but the period of the time zone (its width) is chosen to be 7.25 samples per nominal character width of 0.013 inches. In this case, the sum of the products (calculated as in FIG. 8A, but with different values for the saw tooth) is 102.
In practice, it has been found that three different time zone widths (e.g., 6.75, 7 and 7.25) and seven different offsets between positive and negative peaks should be enough different trials to determine a best fit for many different printings of magnetic ink characters. However, depending on the experience and other factors, more or less may be desirable in actual prctice. Additionally, different time zone widths such as 6.875, 7, and 7.125 may be tried. Additionally, while the preferred embodiment includes the storage of the waveform values as saw-tooth patterns in a ROM for quick look-up, in some instances it may be desirable to calculate or approximate the values of the pattern without storage, or from some analog generator. It may also be desirable to use a sine or cosine generator, rather than the saw-tooth values.
If the four examples shown in FIGS. 8A, 8B, 8C and 8D are the only widths and offsets to be tried, one obtains the result that FIG. 8A is the best correlation (132 as the sum), FIG. 8D is the next best correlation (sum=102), followed by FIG. 8B (sum of 98) and 8C (sum of 72). The values of some key locations (preferably predicted peaks and zero-crossings), perhaps approximately 15 in number, would then be chosen using the period and offset of FIG. 8A first to determine values to be tested using the maximum and minimum expected values for each character in the repertoire to determine if these selected values identify a character, using the method described in Rohrer's article in the IBM Technical Disclosure Bulletin mentioned above. If the offset and period or width from FIG. 8A do not produce an acceptable match of a character, then the period and offset from the next best pattern are used to select key locations for identification, in this case using the values of FIG. 8D. The process is then repeated using FIG. 8B values if the character still is not identified. Of course, other methods of evaluating the matching or non-matching nature of waveform samples could be used after using the sample selection algorithms described in this patent are used.
Program listings written in PL1 to accomplish the functions of FIGS. 3-7 is as follows, with portions of the program annotated to correspond to blocks described in connection with FIGS. 3-7. Of course, other programs in other languages could be used to advantage in the present invention. Is also possible that hard wired logic could be used to advantage to implement the functions, or at least some of them, described in the present patent. ##SPC1## 16
Of course, many alternatives to the preferred mode of carrying out the present invention are apparent to those skilled in the art of reading magnetic ink characters through automatic machinery having character recognition algorithms, and furthermore, some features of the present invention may be used without the corresponding use of other features described in this description. For example, while the present invention has been described in terms of identifying characters written in the E13B font which is the preferred use for the present invention, the present system is by no means limited to that font and may have use for the bar code font (CMC-7) used in European checks. Further, by suitable modifications to the apparatus and techniques, the use in optical character recognition is believed feasible. Thus, the foregoing description should be considered as merely illustrative of the preferred embodiment of the present invention and not in limitation thereof, the scope of which invention being defined solely by the appended claims.
Claims
Having thus described the invention, what is claimed is:
1. A method for identifying a character printed on a document comprising the steps of: generating an analog signal representative of said character as the document passes a read element; digitizing and storing values representing said analog signal for said character; locating positive and negative peaks associated with said analog signal for said character; testing the peaks associated with said character against a first plurality of repeating patterns, having different combinations of period and offset between positive and negative peaks, to determine which of said first plurality of repeating patterns best fit the peaks stored for said character; using the one of said plurality of repeating patterns which best fits the peaks to select at least some of the stored digitized values and, testing said selected stored digitized values against a second plurality of patterns representing the set of characters which can be identified, to identify the character.
2. A method including the steps of claim 1 and further including the step of: using a second-best pattern to select a second set of the stored digitized values if the character is not recognized using the best-fit pattern.
3. A method of identifying a character including the steps of claim 1 and further including the steps of: using patterns which fit the patterns of peaks less accurately in successive order until a pattern is used to select samples which leads to an identification of the character.
4. The method including the steps of claim 3 and further including the step of terminating the use of succeeding patterns after a predetermined number of trials has been reached.
5. A method of identifying a character as described in claim 1 wherein the method further includes the step of ignoring an opening peak and attempting to use the remainder of the the stored information to identify the character.
6. A method of identifying a character including the steps of claim 1 and further including the step of normalizing the character over all of the peaks to scale the readings based upon all peaks of the character.
7. A method of identifying a magnetic ink character using a single gap magnetic read head generating a time varying analog signal indicative of change of magnetic ink passing by the magnetic head over time, the steps of the method comprising: digitizing and storing values at successive time intervals representative of the analog signal at that time; locating peaks in an absolute value sense; determining an apparent period of the located peaks and an apparent offset between positive and negative peaks of the located peaks; using the apparent period and apparent offset to select from the stored values; and testing the selected stored values against a set of values representing the set of characters which can be identified, to attempt to identify the character.
8. The method of identifying a character including the steps described in claim 7 and further including the step of determining a second period and second offset in the event that the character cannot be identified using the stored values selected using the apparent period and apparent offset, and using the second period and second offset to determine a second set of selected stored values which are used to identify the character.