Note: Descriptions are shown in the official language in which they were submitted.
11 B ckground of the Invention
12 The present invention relates to electrical
13 communications, and particularly concerns systems for the
14 machine recognition of patterns such as lexical characters.
Machines for the recognition of characters
16 and other patterns are subject to two types of errors.
17 Reject errors are those for which the machine is incapable
18 of placing the input character into any of -the possible
19 classes. A rejected character is usually represented by
a special code or symbol, such as "@". Substitution
21 errors are those for which the machine places the character
22 in an incorrect class, such as the improper recognition of
23 a "B" as an "8". Within a recognition unit of a given
24 size and complexity, the relative number of substitutions `
may be minimized by rejecting all input characters which
26 are not recognized with a high degree of confidence.
27 Since this approach increases the relative number of
28 reject errors, it is said to have a high reject/substitution
29 ratio. Conversely, a low reject/substitution ratlo may be
achieved by allowing non-confident guesses as to the
~ .
~'
r .. , . ,, ~ . . . . -:
.: : :. ' ' :' ' : ~ :: ,. " "' .. .. ' ' `::. :.
: . , : ' . : '' ' '' '
: .'' ., , ' ' , : :
- :' , ' " . , : - :,
: ,~ . ' : ,'' , :
: ' : ' ' ' ~ ' . ,
: . .
965~
1 identity of the input character. The designer of a recogni-
tion system may choose any reject/substitution ratio between
these extremes as a parameter of his system. Once chosen, how-
ever, it is immutable e~cept 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 appli-
cations 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 in- ~ -
formation, however, the expense of manually correcting reject
errors may be reduced by allowing a higher relative substitu-
tion rate. The redundancy of normal English text, for example,
is sufficiently large that occasional incorrect characters
are cf 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 re-
scanning critical character fields and comparing the identifi-
cations with each other. If they differ, the character is
; rejected. In all other fields, only one identification is
produced. The difficulty
*Registered Trade Mark
RO972-013 - 2 -
: :
~, s
1~49~iS7
with 1 ~1i8 approach i5 that the same recognition logic is
2 used for all recognition attempts, and the rescanning
3 operation impGses a considerable time penalty.
4 Summary of the Invention
The present invention overcomes the
6 above and other problems by providing an improved ~;
7 means for selectively altering the reject/substitution
8 characteristics of pattern-recognition systems, thus
9 rendering such systems more flexible in a wider variety ~
of applications. --
.. . .
11 Generally speaking, the invention is
12 practiced by producing independent recognition codes ;~
13 for the s ame input pattern, and comparing them with each
14 other and/or with a reject code indicating that the
15 pattern has failed to be identified. The results of
j
16 these comparisons then coact with a received reject/
17 substitution mode indication to gate out one of the ~ ~
,-~ , ,.
18 recognition codes or the reject code. The invention
19 may be implemented by plural recognition means producing
20 independent codes, comparison means, control means for
` 21 receiving mode signals, and output means for selectively
22 gating one of the recognition or reject codes. -~
23 Other objects, advantages and features ~;
24 of the invention, as well as modifications obvious to
25 those skilled in the art, will appear in the following
26 detailed description of several preferred embodiments
27 thereof, taken in conjunction with the accompanying
28 drawings.
29 Description of the Drawings
.:
Fig. 1 is a simplified block diagram
:'.,
- ::
RO972-013 --3-
~ ,~
: ..
: - , - . - - ,. . . - .,
:~'. . . ' - .': . ' , : .
~ . . . . . . .
i5~
of an exemplary character~recognition sy~tem in which
2 the invention finds utility.
3 Fig. 2 shows a first embodiment of the
4 invention.
Fig. 3 illustrates an exemplary form of
6 recognition logic useful in the embodiment of Fig. 2.
7 Fig. 4 shows a second embodiment of the
8 invention.
9 Description of the Embodiments
Fig. 1 shows a representative
11 recognition system 100 in which the invention finds
12 utility. Optical scanner 110 produces a vertical raster or
13 other scan pattern over a document 120 containing
14 characters to be recognized. Video detector 130 converts
light reflected from the document into electrical signals.
16 These signals may then be thresholded to produce a sequence
17 of binary digits on line 131 indicating whether the
18 character or the background is present within particular
19 small areas or cells of the document. Video processor 140
provides conventional functions such as filtering noise,
21 segmenting and storing character images, smoothing contours,
22 registering the images to a desired position and normalizing ~;~
23 them to a desired size, and may derive a set of features
24 or measurements representing each character. Recognition
unit 150 receives the measurements or the processed pattern
26 image on line 141 and produces a standard output code, such as
27 EBCDIC or ASCII, representing the identity of each character.
28 This code is passed via line 151 system control 160, which
29 may store it or transmit it to an external device such as a
bulk storage or computer (not shown). System control 160
`; '
ROg72-013 -~~
: ~:
. . .
. - . . . . . .
:; ,
~496S7
may yer~orm other conv~n~ional ~unctions, ~u~h a~ con~rol
2 of the format of scanner 110 (line 161), document-transport
3 control, and input/output (I/O) handling. Control 160
4 also provides mode-selection signals on line 162, as will
be described hereinafter.
6 Fig. 2 shows a digital circuit 200
7 according to the invention, which may be employed for
8 recognition unit 150.
9 Recognition means 210 receives the
aforementioned measurement signals on line 141 and produces
11 at least two recognition codes on lines 211, 212 representing
12 probable identities of the character under investigation.
13 Line 213 carries a "reject" code from a conventional
14 fixed code generator 214. The two recognition codes
are generated by separate recognition logics 215, 216.
16 Although these recognition means are of conventional design,
17 they are independent of each other insofar as practicable.
18 That is, they use different measurements in different orders
19 to arrive at their respective recognition codes. Since -
many diverse methods of recognition design are available to
21 the art, this requirement is not a difficult one. Any
22 logics which differ from each other will provide the benefits
23 of the invention.
24 Comparison means 220 receives the codes
on lines 211-213 and produces comparison signals from their ~;
26 interrelationships. Digital comparator 221 produces a
27 signal when the code from logic 215 is the same as that
28 from logic.216, i.e., when both logics assign the same
29 identity to the input character. Comparator 222 produces
a signal when a "reject" code from logic 215 indicates
31 that that logic is unable to identify the character.
RO972-013 -5-
. :.
~ 4~6~7
1 Similarly, comparator 223 indicates an inability of logic
2 216 to identify thie character. At a particular point in
3 the recognition cycle, a signal 231 from sys-tem timing
~ unit 230 gates the three comparison signals through
AND gates 224-226 to set respective latches 227-229. These
6 latches had been previously reset by a signal 232 at the
7 end of the preceeding cycle.
8 At a further point in the current
g recognition cycle, a timing signal 233 causes output
gating means 240 to couple one of the lines 211-213 to
11 output line 151, in response to signals from comparison
12 means 220 and from mode-control means 250. In the
13 simplest case, identical codes from logics 215 and
14 216 cause the "1" output of latch 227 to enable AND 241
~.
to transmit the common recognition code on line 211
16 through OR 242 to output line 151.
.-- : .
17 The code on line 211 is also
~ 18 passed to OR 242, via AND 243, when latch 229 indicates
-~ 19 that logic 216 has failed (i.e., produced a "reject" code),
if a signal on line 251 specifies that control means 250
21 calls for the low-reject mode. AND 244 couples line 212
22 to output line 151 in the low-reject mode (line 251) when
23 the "1" output of latch 228 signals that logic 215
24 has failed. When either of the gates 243, 244 is enabled
because one of the logics has failed, it is possible ;
26 that the other logic has also failed. In this situation,
27 AND's 241, 243 and 244 are all enabled; but then both of
28 the lines 211, 212 carry the same "reject" code, so that
- 29 the "reject" code is passed to output line 151 through
OR 242.
:
RO972-013 -6-
:. ' ~ . '' '' ' ., , -. ' ' .
: . ,, , . .,.. ~ ~
~491~7
1 ~ND gate 245 couples a "reject" code on line
2 213 from generator 214 to output line 151 under either of
two conditions. First, AND 246 enables AND 245 through OR
4 247 in the low-reject mode (line 251) when the "0" outputs
of latches 227-229 indicate tha-t logics 215, 216 have
6 produced dif~erent recognition codes for the input character,
neither of which is a "reject" code. When the two logics
8 report successful but contradictory recognitions, the
g character must be rejected. (It would be possible, if
desired, to resolve such a conflict in a more complex
11 machine by taking a vote among additional logics, or to
12 prefer the output of one logic over the other because of
13 some design factor.) AND 245 further transmits a "reject"
14 code to line 151 when OR 247 is enabled by AND 248.
This condition occurs in the low-substitution mode
16 (line 252) whenever the "0" output of latch 227 signifies
17 a disagreement between the codes from the two logics 215,
18 216. That is, AND 248 is enabled when the logics produce
19 successful but contradictory recognition codes, or when
either logic produces a valid character code but the
` 21 other logic outputs a "reject" code. Although AND 248
22 is not enabled when both logics fail in the
23 low-substitution mode, the identical "reject" codes
24 on lines 211 and 212 enables AND 241 to pass the "reject"
code from logic 215 to output 151 in this situation.
26 The signals for selecting either the low-
27 reject or the low-substitution mode are received and i ~ ,
28 staticized,by latch 253 of mode-control means 250.
Z9 They are shown as emanating from system control 160, Fig. lr
over lines 162. The source of these signals is arbitrary;
RO972-013 -7-
? ` ` -.... ..
S7
1 ~hey may be selected by an operator through a manual
2 switch (not 5hown) on the machine. They may also be produced
3 automaticall~, if desired, by a program in system control
4 160, or by an external device (not shown) connected to
control 160.
6 Fig. 3 shows an exemplary circuit 300
7 useful in the implementation of logics 215 and 216. The
8 measurement signals, labelled "STRRnnn", are received
g on line 141. In a first level 310, AND gate 311 produces
a signal when measurement STRR109 is present, if
11 measurement STRR141 is also present. If STRR109 is not
12 present in the character, AND 312 is enabled by inverter
13 313 to produce a signal when STRR016 is present. AND 321
14 of second level 320 is enabled by the output of first- `
level AND 311 to produce a signal when measurement STRR142
16 is detected. AND 321 in turn enables AND 331 of a third
17 level 330 upon detection of STRR031, and so forth.
18 Inverter 322 enables AND 323 to pass measurement STRR008
19 when AND 311 is not satisfied. When AND 323 is satisfied,
it ena~les another third-level AND (not shown) in the
21 decision tree; when it is not satisfied, inverter 332
22 produces a RECO4 signal indicating that the character
23 has been successfully recognized as a numeral "4".
24 Gates 324-326 operate in a similar manner from the output
of AND 312 and the measurements STRR052, STRR001.
26 Inverter 333 recognizes the character as a "2" upon the
27 non-satisfaction of AND 324, while the direct output
28 o~ AND 325 produces a RECO7 signal identifying the
29 character as a numeral "7". The output of AND 325 is also
transmitted to third-level AND 334 through inverter 335;
31 its output is recognized as a "5".
RO972-013 -8
..
::
10~ 7
1 Conventional coding matrix 340 receives the RECO sig-
nals 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. ~he 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. Patent 3,573,731, issued April 6, 1971 or in commonly
assigned Canadian Patent 985,790 issued March 16, 1976 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 parti-
cular 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 aforementloned Canadian Patent 985,79G. 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 Rl and R2, respectively. In this embodiment, it is
preferred that the logics internally
RO972-013 - 9 -
~, .
.:.
,
. :. . .
~ 9~5'~ ~
derlve ~ach oh~racter meaeurement durlng the execution
2 of the logics themselves, and on:Ly when required by a
3 particular character. Thus, the data inputs to logics
4 403, 404 are preferably the video bits directly from the
stored character image, rather than pre-derived
6 measurements or features.
7 Next, block 405 tests the state of the
8 mode-control signal set in block 402. If the low-
g substitution mode has been selected, block 406 compares
10 the recognition code in register Rl with that in R2.
11 If they are the same, block 407 transfers the common
12 code in Rl to an output register. If they differ,
13 block 408 produces a "reject" or "fail" code F in the
14 output register. Returning to block 405, the detection
15 of the low-reject mode from block 402 again initiates
16 a comparison of the recognition codes in Rl and R2,
17 and an equality therebetween again causes block 407
18 to output the code from Rl. But an inequality causes
19 block 410 to ask whether the code in Rl is the "fail" code,
20 indicating that logic 403 is unable to recognize the ~;
21 character. If so, block 411 outputs the contents of R2,
22 i.e., the recognition code from the other logic 404.
23 If logic 403 has not failed, block 410 initiates a
24 comparison, in block 412, of the recognition code in R2
25 with the "fail" code. An equality from block 412
26 signifies that logic 404 has failed the character, but
27 ~hat logic 403 has made a successful recognition.
28 Therefore, the code from R1 is output in this case. On
29 the other hand, the "no" output from block 412 means that
30 both logic 403 and logic 404 have produced successful
RO972-013 -10-
. . . .
~49t;~7
1 but different recognitions of the same input character. In
this situation, block 408 ou-tputs the "fail" code. Here again,
provision may be made for breaking this type of con~lict 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.
The appended Table shows a complete set of exemplary
logics gO3,404 for recognizing machine-printed go-thic
numerals. These logics are executable in the recognition pro-
cessor disclosed in the aforementioned Canadian Patent 985,790
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 measure-
ments "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 measure-
ment 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 des-
cribed and/or
RO972-013 - 11 -
~ ~ .
;' :
:.
- ' ' , ' '. ,
~ 491f~57
1 provide a larger number of selectable reject/substitution
2 modes. It is also possible to provide another selectable
3 mode in which only one of -the logics is used for particular
4 input characters. Such a balanced mode would allow
the choice of a reject/substitution ratio intermediate
6 between those of the low-substitution and lcw-reject
7 modes, and might result in a hardware, storage or
8 execution-time advantage in some instances. Other
9 modifications within the scope and spirit of the invention
10will also be apparent to those skilled in the art. -
11Having described several preferred
12 embodiments thereof, I claim as my invention:
'
.. ' .
~ .
'~
. ~ . .
.- '. " ~ ''
. ~,
'
' ''~;'
'~ ' ;~:-
~ RO972-013 -12-
'
':. ~ " '
