Pattern-Recognition Systems Having Selectively Alterable Reject/Substitution Characteristics

The present invention relates to electrical communications, and particularly concerns systems for the machine recognition of patterns such as lexical characters.

Machines for the recognition of characters and other patterns are subject to two types of errors. Reject errors are those for which the machine is incapable of placing the input character into any of the possible classes. A rejected character is usually represented by a special code or symbol, such as "at". Substitution errors are those for which the machine places the character in an incorrect class, such as the improper recognition of a "B" as an "8". Within a recognition unit of a given size and complexity, the relative number of substitutions may be minimized by rejecting all input characters which are not recognized with a high degree of confidence. Since this approach increases the relative number of reject errors, it is said to have a high reject/substitution ratio. Conversely, a low reject/substitution ratio may be achieved by allowing non-confident guesses as to the identity of the input character. The designer of a recognition system may choose any reject/substitution ratio between these extremes as a parameter of his system. Once chosen, however, it is immutable except by redesign of the system.

The problem with the choice of a fixed reject/substitution ratio is that no single ratio is optimum for different applications of a recognition system. In reading monetary amount and account number character fields, for instance, it is usually desirable to minimize substitutions at the expense of a higher reject rate. The amount of redundancy in such fields is usually low, and the consequences of mistaken recognition are usually more serious. In reading connected text and non-critical information, however, the expense of manually correcting reject errors may be reduced by allowing a higher relative substitution rate. The redundancy of normal English text, for example, is sufficiently large that occasional incorrect characters are of little concern to intelligibility. Moreover, present-day context-recognition devices are capable of automatically correcting many substitution errors, especially when they are presented with some indication as to the possible identity of a character.

This problem has been addressed in the past. In the IBM 1287 Optical Reader, provision is made for selectively rescanning critical character fields and comparing the identifications with each other. If they differ, the character is rejected. In all other fields, only one identification is produced. The difficulty with this approach is that the same recognition logic is used for all recognition attempts, and the rescanning operation imposes a considerable time penalty.

The present invention overcomes the above and other problems by providing an improved means for selectively altering the reject/substitution characteristics of pattern-recognition systems, thus rendering such systems more flexible in a wider variety of applications.

Generally speaking, the invention is practiced by producing independent recognition codes for the same input pattern, and comparing them with each other and/or with a reject code indicating that the pattern has failed to be identified. The results of these comparisons then coact with a received reject/substitution mode indication to gate out one of the recognition codes or the reject code. The invention may be implemented by plural recognition means producing independent codes, comparison means, control means for receiving mode signals, and output means for selectively gating one of the recognition or reject codes.

Other objects, advantages and features of the invention, as well as modifications obvious to those skilled in the art, will appear in the following detailed description of several preferred embodiments thereof, taken in conjunction with the accompanying drawings.

FIG. 1 is a simplified block diagram of an exemplary character-recognition system in which the invention finds utility.

FIG. 2 shows a first embodiment of the invention.

FIG. 3 illustrates an exemplary form of recognition logic useful in the embodiment of FIG. 2.

FIG. 4 shows a second embodiment of the invention.

FIG. 1 shows a representative recognition system 100 in which the invention finds utility. Optical scanner 110 produces a vertical raster or other scan pattern over a document 120 containing characters to be recognized. Video detector 130 converts light reflected from the document into electrical signals. These signals may then be thresholded to produce a sequence of binary digits on line 131 indicating whether the character or the background is present within particular small areas or cells of the document. Video processor 140 provides conventional functions such as filtering noise, segmenting and storing character images, smoothing contours, registering the images to a desired position and normalizing them to a desired size, and may derive a set of features or measurements representing each character. Recognition unit 150 receives the measurements or the processed pattern image on line 141 and produces a standard output code, such as EBCDIC or ASCII, representing the identity of each character. This code is passed via line 151 system control 160, which may store it or transmit it to an external device such as a bulk storage or computer (not shown). System control 160 may perform other conventional functions, such as control of the format of scanner 110 (line 161), document-transport control, and input/output (I/O) handling. Control 160 also provides mode-selection signals on line 162, as will be described hereinafter.

FIG. 2 shows a digital circuit 200 according to the invention, which may be employed for recognition unit 150.

Recognition means 210 receives the aforementioned measurement signals on line 141 and produces at least two recognition codes on lines 211, 212 representing probable identities of the character under investigation. Line 213 carries a "reject" code from a conventional fixed code generator 214. The two recognition codes are generated by separate recognition logics 215, 216. Although these recognition means are of conventional design, they are independent of each other insofar as practicable. That is, they use different measurements in different orders to arrive at their respective recognition codes. Since many diverse methods of recognition design are available to the art, this requirement is not a difficult one. Any logics which differ from each other will provide the benefits of the invention.

Comparison means 220 receives the codes on lines 211-213 and produces comparison signals from their interrelationships. Digital comparator 221 produces a signal when the code from logic 215 is the same as that from logic 216, i.e., when both logics assign the same identity to the input character. Comparator 222 produces a signal when a "reject" code from logic 215 indicates that that logic is unable to identify the character. Similarly, comparator 223 indicates an inability of logic 216 to identify the character. At a particular point in the recognition cycle, a signal 231 from system timing unit 230 gates the three comparison signals through AND gates 224-226 to set respective latches 227-229. These latches had been previously reset by a signal 232 at the end of the preceeding cycle.

At a further point in the current recognition cycle, a timing signal 233 causes output gating means 240 to couple one of the lines 211-213 to output line 151, in response to signals from comparison means 220 and from mode-control means 250. In the simplest case, identical codes from logics 215 and 216 cause the "1" output of latch 227 to enable AND 241 to transmit the common recognition code on line 211 through OR 242 to output line 151.

The code on line 211 is also passed to OR 242, via AND 243, when latch 229 indicates that logic 216 has failed (i.e., produced a "reject" code), if a signal on line 251 specifies that control means 250 calls for the low-reject mode. AND 244 couples line 212 to output line 151 in the low-reject mode (line 251) when the "1" output of latch 228 signals that logic 215 has failed. When either of the grates 243, 244 is enabled because one of the logics has failed, it is possible that the other logic has also failed. In this situation, AND's 241, 243 and 244 are all enabled; but then both of the lines 211, 212 carry the same "reject" code, so that the "reject" code is passed to output line 151 through OR 242.

AND gate 245 couples a "reject" code on line 213 from generator 214 to output line 151 under either of two conditions. First, AND 246 enables AND 245 through OR 247 in the low-reject mode (line 251) when the "0" outputs of latches 227-229 indicate that logics 215, 216 have produced different recognition codes for the input character, neither of which is a "reject" code. When the two logics report successful but contradictory recognitions, the character must be rejected. (It would be possible, if desired, to resolve such a conflict in a more complex machine by taking a vote among additional logics, or to prefer the output of one logic over the other because of some design factor.) AND 245 further transmits a "reject" code to line 151 when OR 247 is enabled by AND 248. This condition occurs in the low-substitution mode (line 252) whenever the "0" output of latch 227 signifies a disagreement between the codes from the two logics 215, 216. That is, AND 248 is enabled when the logics produce successful but contradictory recognition codes, or when either logic produces a valid character code but the other logic outputs a "reject" code. Although AND 248 is not enabled when both logics fail in the low-substitution mode, the identical "reject" codes on lines 211 and 212 enables AND 241 to pass the "reject" code from logic 215 to output 151 in this situation.

The signals for selecting either the low-reject or the low-substitution mode are received and staticized by latch 253 of mode-control means 250. They are shown as emanating from system control 160, FIG. 1, over lines 162. The source of these signals is arbitrary; they may be selected by an operator through a manual switch (not shown) on the machine. They may also be produced automatically, if desired, by a program in system control 160, or by an external device (not shown) connected to control 160.

FIG. 3 shows an exemplary circuit 300 useful in the implementation of logics 215 and 216. The measurement signals, labelled "STRRnnn", are received on line 141. In a first level 310, AND gate 311 produces a signal when measurement STRR109 is present, if measurement STRR141 is also present. If STRR109 is not present in the character, AND 312 is enabled by inverter 313 to produce a signal when STRR016 is present. AND 321 of second level 320 is enabled by the output of first-level AND 311 to produce a signal when measurement STRR142 is detected. AND 321 in turn enables AND 331 of a third level 330 upon detection of STRR031, and so forth. Inverter 322 enables AND 323 to pass measurement STRR008 when AND 311 is not satisfied. When AND 323 is satisfied, it enables another third-level AND (not shown) in the decision tree; when it is not satisfied, inverter 332 produces a RECO4 signal indicating that the character has been successfully recognized as a numeral "4". Gates 324-326 operate in a similar manner from the output of AND 312 and the measurements STRR052, STRR001. Inverter 333 recognizes the character as a "2" upon the non-satisfaction of AND 324, while the direct output of AND 325 produces a RECO7 signal identifying the character as a numeral "7". The output of AND 325 is also transmitted to third-level AND 334 through inverter 335; its output is recognized as a "5".

Conventional coding matrix 340 receives the RECO signals to generate therefrom a coded representation of the identity of the character recognized by the decision tree, or a "reject" code if no character is recognized. The coded representation, or recognition code, is then transmitted to line 211 (or to line 212, for logic 216).

Circuit 300 is but one example of an implementation for logics 215, 216. The levels 310-330 could be collapsed into a single rank of N-way AND gates, for instance. Similarly, sequential logics could be executed by implementing the logics in the form of a special-purpose processor such as that shown in U.S. Pat. No. 3,573,731, or in commonly assigned application Ser. No. 272,698, filed July 17, 1972 by M. J. Kimmel. The logics need not be decision trees; either or both of them may be correlation networks, for example. That is, the invention is completely independent of the particular type of recognition means 215, 216 employed.

FIG. 4 shows a method 400 of performing the invention when all or part of recognition unit 150, FIG. 1, is embodied in the form of a data processor, such as that described in the aforementioned application Ser. No. 272,698. After the start 401 of the recognition cycle, block 402 senses the state of a manually or automatically settable mode-control signal. Blocks 403 and 404 evaluate first and second recognition logics and store the resulting recognition codes in first and second registers R1 and R2, respectively. In this embodiment, it is preferred that the logics internally derive each character measurement during the execution of the logics themselves, and only when required by a particular character. Thus, the data inputs to logics 403, 404 are preferably the video bits directly from the stored character image, rather than pre-derived measurements or features.

Next, block 405 tests the state of the mode-control signal set in block 402. If the low-substitution mode has been selected, block 406 compares the recognition code in register R1 with that in R2. If they are the same, block 407 transfers the common code in R1 to an output register. If they differ, block 408 produces a "reject" or "fail" code F in the output register. Returning to block 405, the detection of the low-reject mode from block 402 again initiates a comparison of the recognition codes in R1 and R2, and an equality therebetween again causes block 407 to output the code from R1. But an inequality causes block 410 to ask whether the code in R1 is the "fail" code, indicating that logic 403 is unable to recognize the character. If so, block 411 outputs the contents of R2, i.e., the recognition code from the other logic 404. If logic 403 has not failed, block 410 initiates a comparison, in block 412, of the recognition code in R2 with the "fail" code. An equality from block 412 signifies that logic 404 has failed the character, but that logic 403 has made a successful recognition. Therefore, the code from R1 is output in this case. On the other hand, the "no" output from block 412 means that both logic 403 and logic 404 have produced successful but different recognitions of the same input character. In this situation, block 408 outputs the "fail" code. Here again, provision may be made for breaking this type of conflict if it is deemed to be worth the added cost and/or time penalty. Blocks 407, 408 and 411 all lead to end block 413, completing the procedure.

Table I hereinbelow shows a complete set of exemplary logics 403, 404 for recognizing machine-printed gothic numerals. These logics are executable in the recognition processor disclosed in the aforementioned application Ser. No. 272,698, and they may moreover be routinely converted to hard-wired digital-circuit implementations if desired. In the Table, the measurement designations "MEASnnn" correspond to the measurements "STRRnnn" having the same numerals "nnn". The variable "Annn" and "Bnnn" refer to pattern bits in a rectangular grid obtained from a vertical raster scan. The last two digits in each variable designate one of 40 vertical cells 0-39 in each scan, while the first letter and first digit represent one of 20 scans A0-A9, B0-B9; the origin is located at the bottom left corner of the character. The routine for each measurement also shows the logic equation which is evaluated for that measurement. These equations may be employed for the direct implementation of the corresponding measurements in hardwired logic circuits.

It has been mentioned that more than two logics may be in included in either of the embodiments of FIGS. 2 and 4. Such additional logics may operate to break conflicts as described and/or provide a larger number of selectable reject/substitution modes. It is also possible to provide another selectable mode in which only one of the logics is used for particular input characters. Such a balanced mode would allow the choice of a reject/substitution ratio intermediate between those of the low-substitution and low-reject modes, and might result in a hardware, storage or execution-time advantage in some instances. Other modifications within the scope and spirit of the invention will also be apparent to those skilled in the art. ##SPC1##