Confusion grouping of strokes in pattern recognition method and system

• US 4,573,196 A
• Filed: 01/19/1983
• Issued: 02/25/1986
• Est. Priority Date: 01/19/1983
• Status: Expired due to Term

• Current Assignee: Cnfusion Grouping of Strokes In Pattern
• Original Assignee: Communications Intelligence Corporation
• Inventors: Ostrem, John S., Crane, Hewitt D.
• Primary Examiner(s): Boudreau, Leo H.
• Application Number:
  US06/459,180
• Time in Patent Office: 1,133 Days
• Field of Search: 382/13, 382/3, 382/36, 382/37, 382/30, 382/40, 382/18, 382/1, 382/24, 382/56, 381/42
• US Class Current: 382/185
• CPC Class Codes: G06V 30/242 Division of the character sequences into groups prior to recognition; Selection of dictionaries

Abstract

A method and system for recognizing complex patterns, such as Chinese characters (Kanji), which may employ detailed information about an element and specifically curvature characteristics. Selected elements or strokes are grouped into confusion groups. Strokes under examination are categorized and assigned either stroke identity labels or confusion group identity labels by a flexible comparison of distance metrics generated with reference to templates which represent general recognition criteria or groupings of specific strokes. Specific threshold criteria are applied to distance metrics.

Claims

1. A method for identifying patterns by means of a pattern registration means and a data processing means, wherein each pattern comprises at least one unknown stroke generated by relative movement between a pattern-forming means and a pattern-accommodating means of said pattern registration means, said pattern registration means being operative to generate first signal information represented by first signals, said first signal information being representative of stroke information about said unknown stroke, said data processing means being provided with prestored second signal information represented by second signals, said second signal information including templates corresponding to template strokes, said data processing means being operative to generate third signals representing third signal information in response to said first signals and said second signals, said third signal information comprising identity labels for use in developing coded information which identifies said patterns, said method comprising:

defining templates from said second signal information wherein at least one of said templates is a confusion group template, each said confusion group template being derived from information about at least two of said template strokes;

generating distance metric values representative of closeness of stroke shape between said first signal information and said second signal information for at least each one of said confusion group templates; and

determining from said distance metric values which of said confusion group templates or which of said stroke templates yields the least of said distance metric values to obtain an identity label for said unknown stroke by ignoring decision criteria for distinguishing between selected template strokes whenever said selected template strokes are included in a common one of said confusion group templates.

2. The method according to claim 1, further including the steps of:

calculating metric distance between corresponding first signal information and second signal information to obtain a set of difference values;

dividing each one of said difference values by a corresponding permissible deviation value to obtain a set of resultant values; and

summing all said resultant values to obtain said distance metric value.

3. The method according to claim 1, wherein each one of said difference values has a corresponding permissible deviation value, further comprising the steps of

calculating metric distance between corresponding first signal information and second signal information to obtain a set of difference values;

weighting each one of said difference values by its corresponding permissible deviation value to obtain a set of resultant values;

squaring each one of said resultant values to obtain a set of squared values; and

summing all said squared values to obtain said distance metric value.

4. The method according to claim 1 wherein said determining step also includes indicating a match of said unknown stroke with a confusion group template whenever said first signal information is included within a locus circumscribing all of said pattern information of said confusion group template.

5. The method according to claim 1 further including the step of assigning a stroke label as said identity label for said unknown stroke.

6. The method according to claim 1 further including the step of assigning a confusion group label as said identity label for said unknown stroke.

7. A method for identifying patterns by means of a pattern registration means and a data processing means, wherein each pattern comprises at least one unknown stroke generated by relative movement between a pattern-forming means and a pattern-accommodating means of said pattern registration means, said pattern registration means being operative to generate first signal information represented by first signals, said first signal information being representative of stroke information about said unknown stroke, said data processing means being provided with prestored second signal information represented by second signals, said second signal information including templates corresponding to template strokes, said data processing means being operative to generate third signals representing third signal information in response to said first signals and said second signals, said third signal information comprising identity labels for use in developing coded information which identifies said patterns, said method comprising:

defining templates from said second signal information wherein at least one of said templates is a confusion group template, each said confusion group template being derived from information about at least two of said template strokes;

generating distance metric values representative of closeness of stroke shape between said first signal information and said second signal information for at least each one of said confusion group templates;

comparing said distance metric values of said unknown stroke for at least each confusion group template with an upper decision threshold value, with a lower decision threshold value and with a difference decision threshold value; and

assigning a unique identity label corresponding to the template yielding the least distance metric value to the unknown stroke if the least distance metric value is less than the upper decision threshold value and if the next least distance metric value is greater than the sum of the least distance metric value and the difference decision threshold value.

8. The method according to claim 7, wherein said assigning step includes assigning an identity label to said unknown stroke if the distance metric value which is least is less than the lower decision threshold value and if the next least distance metric value is greater than the upper decision threshold value.

9. A method for identifying patterns by means of a pattern registration means and a data processing means, wherein each pattern comprises at least one unknown stroke generated by relative movement between a pattern-forming means and a pattern-accommodating means of said pattern registration means, said pattern registration means being operative to generate first signal information represented by first signals, said first signal information being representative of stroke information about said unknown stroke, said data processing means being provided with prestored second signal information represented by second signals, said second signal information including templates corresponding to template strokes, said data processing means being operative to generate third signals representing third signal information in response to said first signals and said second signals, said third signal information comprising identity labels for use in developing coded information which identifies said patterns, said method comprising:

defining templates from said second signal information, wherein at least one of said templates is a confusion group template consisting of at least two template strokes, each said template stroke comprising a set of position values specifying position along a stroke and a set of deviation values specifying permissible deviation from said position values; and

comparing said first signal information for best match with said second signal information to obtain an identity label for said second signal information.

10. In an apparatus for identifying patterns by means of a pattern registration means and a data processing means, wherein each pattern comprises at least one unknown stroke generated by relative sequential movement between a pattern-forming means and a pattern-accommodating means of said pattern registration means, said pattern registration means being operative to generate first signal information represented by first signals, said first signal information being representative of stroke information about said unknown stroke, said data processing means being provided with prestored second signal information represented by second signals, said second signal information including templates corresponding to template strokes, said data processing means being operative to generate third signals representing third signal information in response to said first signals and said second signals, said third signal information comprising identity labels for use in developing coded information which identifies said patterns, the improvement comprising:

means for storing said second signal information defining templates wherein at least one of said templates is a confusion group template, each said confusion group template being derived from information about at least two of said template strokes;

means for generating distance metric values representative of closeness of stroke shape between said first signal information and said second signal information for at least each one of said confusion group templates; and

means for determining from said distance metric values which of said confusion group templates or which of said stroke templates yields the least of said distance metric values to obtain an identity label for said unknown stroke by ignoring decision criteria for distinguishing between selected template strokes whenever said selected template strokes are included in a common one of said confusion group templates.

11. In the apparatus according to claim 10, the improvement wherein said determining means is operative to to yield as said identity label a specific stroke label for said unknown stroke.

12. In the apparatus of claim 10, the improvement wherein said determining means is operative to to yield as said identity label a confusion group label specifying a confusion group for said unknown stroke.

13. In the apparatus according to claim 12, further including means for comparing said distance metric values of said unknown stroke for each template with an upper decision threshold value, with a lower decision threshold value and with a difference decision threshold value of yield said identity label.

14. In the apparatus according to claim 13, further including means for assigning an identity label to said unknown stroke if the least distance metric value is less than the lower decision threshold value and if the next least distance metric value is greater than the upper decision threshold value.

15. In the apparatus according to claim 10, wherein said first signal information and said second signal information specify relative position along a stroke describing stroke shape, further including:

means for calculating metric distance between corresponding first signal information and second signal information to obtain a set of difference values;

means for dividing each one of said difference values by a permissible deviation value corresponding to each location of first signal information along a stroke to obtain a set of resultant values; and

means for summing all said resultant values to obtain said distance metric value.

16. In the apparatus according to claim 10, wherein said first signal information and said second signal information specify relative position along a stroke describing stroke shape, further including:

means for calculating metric distance between corresponding first signal information and second signal information to obtain a set of difference values;

means for dividing each one of said difference values by a permissible deviation value corresponding to each location of first signal information along a stroke to obtain a set of resultant values;

means for squaring each one of said resultant values to obtain a set of squared values; and

means for summing all of said set of squared values to obtain said distance metric value.

17. In an apparatus for identifying patterns by means of a pattern registration means and a data processing means, wherein each pattern comprises at least one unknown stroke generated by relative movement between a pattern-forming means and a pattern-accommodating means of said pattern registration means, said pattern registration means being operative to generate first signal information represented by first signals, said first signal information being representative of stroke information about said unknown stroke, said data processing means being provided with prestored second signal information represented by second signals, said second signal information including templates corresponding to template strokes, said data processing means being operative to generate third signals representing third signal information in response to said first signals and said second signals, said third signal information comprising identity labels for use in developing coded information which identifies said patterns, the improvement comprising:

means for storing said second signal information defining templates wherein at least one of said templates is a confusion group template, each said confusion group template being derived from information about at least two of said template strokes;

means for generating distance metric values representative of closeness of stroke shape between said first signal information and said second signal information for at least each one of said confusion group templates; and

means for determining from said distance metric values which of said confusion group templates or which of said stroke templates yields the least of said distance metric values to obtain an identity label for said unknown stroke by ignoring decision criteria for distinguishing between selected template strokes whenever said selected template strokes are included in a common one of said confusion group template;

wherein said determining means includes;

(1) means for comparing said distance metric values of said unknown stroke for at least each confusion group template with an upper decision threshold value, with a lower decision threshold value and with a difference decision threshold value; and

(2) means for assigning a unique identity label to said unknown stroke, said identity label corresponding to the one of said templates yielding said distance metric value which is least if said least distance metric value is less than the upper decision threshold value and if the next least distance metric value is greater than the sum of the least distance metric value and the difference decision threshold value.