Pattern recognition data processing device using an associative matching method

• US 5,214,717 A
• Filed: 02/25/1991
• Issued: 05/25/1993
• Est. Priority Date: 02/26/1990
• Status: Expired due to Term

• Current Assignee: Fujitsu Limited
• Original Assignee: Fujitsu Limited
• Inventors: Suzuki, Kenji, Kimura, Masayuki, Katsuyama, Yutaka, Hayasaka, Hisayoshi, Sakurai, Yoshiyuki, Aso, Hirotomo
• Primary Examiner(s): COUSO, JOSE L
• Application Number:
  US07/660,756
• Time in Patent Office: 820 Days
• Field of Search: 382/9, 382/10, 382/13, 382/21, 382/30, 382/34
• US Class Current: 382/202
• CPC Class Codes: G06V 30/248 involving plural approaches, e.g. verification by template match; Resolving confusion among similar patterns, e.g. "O" versus "Q" G06V30/242 takes precedence

Abstract

This invention pertains to a data processing system for pattern recognition by sorting the scores of the candidate patterns by their feature vectors per an associative matching method. It aims first at determining feature vectors at a high speed even if a recognition device obtains dictionary data in dot units, second at determining scores by an association conformance recognition device, and third at sorting inputted data from the highest score at a high speed. The feature of this invention resides in a data processing device that incorporates a first memory for memorizing stroke information for patterns supplied in dot units; a first address generator for generating first addresses for specifying the positions at which the stroke information is memorized; a second memory for memorizing weight data for the stroke information; a second address generator for generating second addresses for reading stroke information memorized in the first memory and third addresses for reading, from the second memory, the weight data corresponding to the stroke information read by the second addresses; accumulators of the number of the stroke directions supplied with weight data outputted from the second memory; and a decoder for decoding the stroke information memorized in the first memory and for accumulating weights for the respective stroke directions to enable the accumulators per the decoding result.

Claims

1. A data processing device for processing feature data for a plurality of characters being compared through an associative matching method of character recognition, comprising:

a first data memory means for memorizing at least stroke information for input character pattern supplied in dot units;

a first address generating means for generating first addresses for specifying positions at which the stroke information is memorized;

a second data memory means for memorizing weight data for the stroke information;

a second address generating means for generating second addresses for reading the stroke information memorized in said first data memory means and third addresses for reading, from the second data memory means, the weight data corresponding to the stroke information read by the second addresses;

a plurality of accumulation means provided in correspondence with a number of stroke directions, for accumulating weight data outputted from said second data memory means;

a decoding means for decoding the stroke information memorized in said first data memory means and for determining weights in respective stroke directions to enable said plurality of accumulation means according to decoding results from said decoding means so as to generate feature data of the input character patterns;

a dictionary memory for memorizing feature data of dictionary patterns, the feature data being divided into classes of features;

a plurality of distance computing means operatively connected to receive feature data of input character patterns, for computing distances between the feature data of the dictionary patterns memorized in said dictionary memory and the feature data of the input character patterns, and for sequentially inputting result values from computing the distances to a first stage of plural pairs of serially connected plural class selection means;

plural pairs of serially connected plural class selection means operatively connected to said plurality of distance computing means, for comparing the sequentially inputted result values with memorized result values of distances inputted sequentially earlier by said plurality of distance computing means so as to at least one of maintain memory of the earlier memorized result values and output the inputted result values when the earlier memorized result values are less than the inputted result values, and of output the earlier memorized result values and memorize the inputted result values;

a plurality of score computing means operatively connected to respective outputs from said plural paris of serially connected plural class selection means, for obtaining scores corresponding to the feature data of the input patterns of the characters to be recognized; and

a score sorting means for determining rankings of the dictionary patterns in terms of which of the dictionary patterns derived highest scores obtained at said plurality of score computing means.

2. The data processing device according to claim 1, wherein said plurality of accumulation means are provided in m pairs for processing the stroke information in parallel in m-bit units.

3. The data processing device according to claim 1, wherein said dictionary memory memorizes feature data classified in classes of standard pattern units and codes of the patterns belonging to the classes.

4. The data processing device according to claim 1, wherein said dictionary memory memorizes feature data in classes of pattern units.

5. The data processing device according to claim 3 or 4, wherein the classes are in region units divided from pattern areas.

6. The data processing device according to claim 1, wherein said plural pairs of serially connected plural class selection means being further for selecting classes in said dictionary memory to which the characters to be recognized are associated, identification of selected classes being inputted from said plural pairs of serially connected plural class selection means to respective ones of said plurality of score computing means, and

said plurality of score computing means including a class memory for memorizing classes to which the characters to be recognized belong, means for determining whether the classes inputted from said plural pairs of plural class selection means match the classes to which the characters belong, and means for accumulating weighted scores for the respective ones of said plural pairs of plural class selection means when both classes match.

7. The data processing device according to claim 1, wherein each of said plurality of score sorting means respectively incorporates a plurality of sorting cells, each of the plurality of sorting cells respectively including two input terminals, the plurality of sorting cells being connected in a tree form in a plurality of stages so as to receive in a current stage higher scores inputted into the two input terminals, reset the sorting cells in a preceding stage supplying the scores, and output higher scores to sorting cells in a following stage.

8. The data processing device according to claim 6, wherein said plurality of score computing means are provided for respective characters for sequentially accumulating scores for respective regions divided from a pattern area of a character in said dictionary memory.

9. A data processing device for processing a plurality of accumulated score data used in computing a plurality of characters for an associative matching method used in character recognition, comprising:

a first data memory means for memorizing at least stroke information for a character pattern supplied in dot units;

a first address generating means for generating first addresses for specifying positions at which the stroke information is memorized;

a second data memory means for memorizing weight data for the stroke information;

a second address generating means for generating second addresses for reading the stroke information memorized in said first data memory means and third addresses for reading, from the second data memory means, the weight data corresponding to the stroke information read by the second addresses;

a plurality of accumulation means provided in correspondence with a number of stroke directions, for accumulating weight data outputted from said second data memory means;

a decoding means for decoding the stroke information memorized in said first data memory means and for determining weights in respective stroke directions to enable said plurality of accumulation means according to decoding results from said decoding means so as to generate score data of input character patterns to be recognized;

first and second selection memory means for receiving and memorizing inputted score data such that one of said first and second selection memory means memorizes an inputted first score data while the other of said first and second selection memory means maintains memory of an earlier inputted second score data,

said first and second selection memory means being operatively connected to each other so as at least one of said first and second selection memory means outputs the first score data while the other of said first and second selection memory means maintains memory of the second earlier inputted second score data, and one of the first and second selection memory means outputs the earlier received second score data while the other of said first and second selection memory means transfers memory of the first score data to the one of the first and second selection memory means, said first and second selection memory means being controlled by a received selection signal; and

comparison means for comparing the earlier inputted second score data with the first score data so as to control output operation of said first and second selection memory means.

10. The data processing device according to claim 9, wherein said first and second selection memory means include

a first memory means for temporarily memorizing the inputted first score data,

a second memory means for memorizing the earlier inputted second score data,

a first selection means operatively connected to receive the first score data temporarily memorized in the first memory means at a first input terminal and the second score data memorized by the second memory means at a second input terminal, for outputting at least one of the first and second score data according to a comparison by said comparison means, and

a second selection means operatively connected to receive second data memorized in the second memory means at a first input terminal and the first score data temporarily memorized in the first memory means at a second input terminal, for outputting at least one of the first and second score data according to the comparison by said comparison means.

11. The data processing device according to claim 9, wherein said comparison means includes at least an output terminal for outputting data indicating a comparison result showing whether data inputted from the first input terminal are at least one of greater than, less than and equal to data supplied from the second input terminal.

12. A data processing device used in an associative matching method in which feature areas are divided into a plurality of classes represented by division area units and scores are assigned to the classes to which the division area units belong, so that the scores of the classes to which a plurality of codes of candidates belong are accumulated by the code units for recognition, said data processing device comprising:

a first data memory means for memorizing at least stroke information for input character pattern supplied in dot units;

a first address generating means for generating first addresses for specifying positions at which the stroke information is memorized;

a second data memory means for memorizing weight data for the stroke information;

a second address generating means for generating second addresses for reading the stroke information memorized in said first data memory means and third addresses for reading, from the second data memory means, the weight data corresponding to the stroke information read by the second addresses;

a plurality of accumulation means provided in correspondence with a number of stroke directions, for accumulating weight data outputted from said second data memory means;

a decoding means for decoding the stroke information memorized in said first data memory means and for determining weights in respective stroke directions to enable said plurality of accumulation means according to decoding results from said decoding means so as to generate feature data of the input character patterns;

a dictionary memory for memorizing feature data of dictionary patterns, the feature data being divided into classes of features, said dictionary means including a counter for specifying the plurality of codes, a plurality of latch circuits sequentially shifting memorized values, each time a value of the counter changes, and a plurality of class dictionaries, addressed by a value of the counter and values memorized in the latch circuits, for memorizing classes to which the plurality of codes belong in the division area units;

a plurality of distance computing means operatively connected to receive feature data of input character patterns, for computing distances between the feature data of the dictionary patterns memorized in said dictionary memory and the feature data of the input character patterns, and for sequentially inputting result values from computing the distances to a first stage of plural pairs of serially connected plural class selection means;

plural pairs of serially connected plural class selection means operatively connected to said plurality of distance computing means, for comparing the sequentially inputted result values with memorized result values of distances inputted sequentially earlier by said plurality of distance computing means so as to at least one of maintain memory of the earlier memorized result values and output the inputted result values when the earlier memorized result values are less than the inputted result values, and of output the earlier memorized result values and memorize the inputted result values;

a plurality of score computing means operatively connected to respective outputs from said plural paris of serially connected plural class selection means, for obtaining scores corresponding to the feature data of the input patterns of the characters to be recognized, said plurality of score computing means incorporating a plurality of score buffers operatively connected to receive class outputs from the class dictionaries at their addresses, for memorizing, as class addresses, scores corresponding to the classes in the division area units; and

a score sorting means for determining rankings of the dictionary patterns in terms of which of the dictionary patterns derived highest scores obtained at said plurality of score computing means, said score computing means including a plurality of address, provided in correspondence with said score buffers, for sequentially adding the class scores outputted from the score buffers.