Automatic character recognition device employing dynamic programming

• US 3,979,722 A
• Filed: 05/30/1975
• Issued: 09/07/1976
• Est. Priority Date: 05/31/1974
• Status: Expired due to Term

• Current Assignee: Nippon Electric Company Limited (NEC Corporation)
• Original Assignee: Nippon Electric Company Limited (NEC Corporation)
• Inventors: Sakoe, Hiroaki
• Primary Examiner(s): Thesz, Joseph M.
• Application Number:
  US05/582,520
• Time in Patent Office: 466 Days
• Field of Search: 340/146.3 Q, 340/146.3 H, 340/146.3 AE
• US Class Current: 382/215
• CPC Class Codes: G06V 10/754 involving a deformation of the sample pattern or of the reference pattern; Elastic matching

Abstract

A character recognition device comprises a memory for memorizing standard patterns, each given by fundamental vectors. A dynamic matching unit finds out a maximum of degrees of coincidence between an input character and line patterns derived from each of the standard patterns by varying the magnitudes of the vectors between predetermined minima and maxima and derives similarity measures defined by the maximum degrees of coincidence between the input character and the line patterns derived from the respective standard patterns and specific line patterns for which the maximum degrees of coincidence are found. A decision unit compares the similarity measures with one another, judges whether or not the input character has a feature predetermined for each of the standard patterns, and delivers a result of the recognition in response to results of the comparison and judgment.

Claims

1. A device for automatically recognizing an input pattern of one of a predetermined number of sorts by comparing said input pattern successively with standard patterns of at least said predetermined number of sorts, said input pattern being specifiable by two-dimensional array of meshes of different optical characteristics, each of said standard patterns being given by a series of fundamental vectors, which comprises:

an input pattern buffer memory means for memorizing input electric signals representative of said optical characteristics;

a standard pattern memory means for memorizing standard electric signals representative of the directions and predetermined minima and maxima of magnitudes of vectors of the standard patterns;

a dynamic matching means responsive to said input and standard electric signals for finding an extremum of degrees of coincidence between said input pattern and a plurality of line patterns derived from each of said standard patterns by varying the magnitudes between the predetermined minima and maxima to produce first electric signals representative of similarity measures defined by the extremum degrees of coincidence between said input pattern and the line patterns derived from the respective standard patterns and second electric signals representative of specific line patterns for which said extremum degrees of coincidence are found; and

a decision means comprising, in turn, first means for memorizing feature electric signals representative of a predetermined feature common to the line patterns derivable from each of said standard patterns, second means for comparing said first signals with one another, third means responsive to said input, second, and feature electric signals for judging whether or not said input pattern has said predetermined feature, and fourth means responsive to results of the comparison and judgement carried out by said second and third means for producing an output electric signal representative of a result of recognition of said input pattern.

2. A device for automatically recognizing an input pattern as recited in claim 1 wherein said dynamic matching means comprises:

a recurrence coefficient calculator means connected to said input pattern buffer memory means and to said standard pattern memory means for calculating recurrence coefficients of input pattern and standard pattern vectors represented by said input and standard electric signals, respectively,

a recurrence coefficient register means connected to said recurrence coefficient calculator means for accumulating and storing said recurrence coefficients, and

a maximum coefficient finder means connected to said recurrence coefficient register means for calculating said similarity measures defined by the maximum degrees of coincidence between said input pattern and the line patterns derived from the respective standard patterns, said maximum coefficient finder means generating said first electric signals supplied to said decision means.

3. A device for automatically recognizing an input pattern as recited in claim 2 wherein said dynamic matching means further comprises:

a specific vector length register means connected to said recurrence coefficientt calculator means for storing signals representing specific vector lengths, and

a specific line pattern finder means connected to said specific vector length register means and to said maximum coefficient finder means for calculating specific vector end points, said specific line pattern finder means generating said second electric signals supplied to said decision means.

4. A device as claimed in claim 1, said input pattern buffer memory having memory locations corresponding to the respective meshes, said standard pattern memory comprising means responsive to standard pattern sort electric signals successively designating the respective standard patterns for producing said standard electric signals, wherein said dynamic matching unit comprises:

means responsive to each of said sort signals for successively producing vector number signals representative of ordinal numbers of the fundamental vectors in the series of the standard pattern designated by said each sort signal;

means responsive to each of said vector number signals for the last-mentioned standard pattern for successively producing mesh address signals specifying the respective meshes;

means responsive to the standard electric signals for the last-mentioned standard pattern and each of said mesh address signals for successively producing line pattern vector address signals representative of the meshes for line pattern vectors which are derived from the fundamental vector of the ordinal number represented by said each vector number signal by varying the magnitude of the last-mentioned fundamental vector between the relevant minimum and maximum with ends of said line pattern vectors placed in common at the mesh specified by said each mesh address signal, said input pattern buffer memory producing in response to said line pattern vector address signals the input electric signals stored in the memory locations corresponding to said line pattern vectors;

means responsive to the last-mentioned standard electric signals and said each mesh address signal for successively producing line vector end address signals representative of the meshes for ends of the line pattern vectors which are derived in response to the vector number signal produced next prior to said each vector number signal;

first register means having memory cells corresponding to the respective meshes for storing in response to said each vector number signal third electric signals representative of recurrence coefficients dependent on the vector number represented by said each vector number signal and on said meshes at the memory cells specified by said mesh address signals and for producing in response to said vector end address signals the third electric signals which are stored in the respective memory cells specified by the mesh address signals in response to the vector number signal produced next prior to said each vector number signal;

calculator means responsive to the input electric signals produced in response to said line pattern vector address signals and responsive to the third electric signals produced by said first register means for producing the third electric signals to be stored in said first register means, said first register means eventually storing those degrees of coincidence between said input pattern and the last-mentioned standard pattern when the vector number signal represents the number of the fundamental vectors in the last-mentioned standard pattern which are given by the respective third electric signals stored in said memory cells in response to the last-mentioned vector number signal;

second register means responsive to said vector number signals for the last-mentioned standard pattern and to said mesh address signals for storing fourth electric signals, each representative of the magnitude of the the line pattern vector represented by the line pattern vector address signals in response to which the last-mentioned third electric signals are produced and representative of the mesh for the end of the last-mentioned line pattern vector;

means for finding the extremum of said degrees of coincidence to produce fifth electric signals when the last-mentioned extremum is found and to produce said first electric signals as said sort signals successively designate said standard patterns; and

means responsive to said fourth and fifth electric signals and the last-mentioned standard electric signals for producing said second electric signals as said sort signals successively designate said standard patterns.

5. A device as clained in claim 1 wherein said first means comprises means responsive to each of standard pattern sort electric signals designating the respective standard patterns for producing first feature signals representative of an ordinal number of a predetermined fundamental vector in the series of one of said standard patterns that is designated by said each sort electric signal, said predetermined fundamental vector relating to the predetermined feature of said one standard pattern, and means responsive to said each sort electric signal for producing second feature signals defining the last-mentioned predetermined feature, said first and second feature signals serving as said feature electric signals.

6. A device as claimed in claim 5 wherein said third means comprises a specific line pattern memory responsive to the second electric signals representative of the specific line pattern derived from and one standard pattern for memorizing electric signals representative of optical characteristics predetermined for those specific line pattern vectors of the last-mentioned specific line pattern which are derived from the respective fundamental vectors of said one standard pattern, and a processor responsive to said first feature signals for making said specific line pattern memory produce the specific electric signals representative of the predetermined optical characteristics of the specific line pattern vector of said ordinal number, producing specific coordinate address signals for making said input pattern memory produce the input electric signals representative of the different optical characteristics of a line pattern vector corresponding in said input pattern to the last-mentioned specified line pattern vector, for comparing said specific and the last-mentioned input electric signals to judge with reference to said second feature signals whether or not said input pattern has said predetermined feature, and for producing in response to the result of the judgement a gate enable signal in the affirmative case.

7. A device as claimed in claim 6, said standard pattern memory comprising means responsive to said sort signals for producing the standard electric signals representative of the standard patterns successively designated by said sort signals, wherein said second means produces an output pulse each time the first electric signals representative of the similarity measure for one of said standard patterns are greater than the first electric signals representative of the similarity measures for the standard patterns designated prior to the last-mentioned one standard pattern, said output pulse being representative of said result of the comparison.

8. A device as claimed in claim 7 wherein said fourth means comprises an AND gate enabled by said enable signal for gating the output pulses and a register for registering the sort signals in coincidence with the output pulses gated through said AND gate to eventually register and produce said output electric signal.