Complex pattern recognition method and system

• US 4,561,105 A
• Filed: 01/19/1983
• Issued: 12/24/1985
• Est. Priority Date: 01/19/1983
• Status: Expired due to Term

• Current Assignee: Communications Intelligence Corporation
• Original Assignee: Communications Intelligence Corporation
• Inventors: Ostrem, John S., Crane, Hewitt D.
• Primary Examiner(s): Boudreau, Leo H.
• Application Number:
  US06/459,282
• Time in Patent Office: 1,070 Days
• Field of Search: 382/3, 382/13, 382/18, 382/24, 382/30, 382/38, 382/42, 382/46, 382/57, 381/42
• US Class Current: 382/185
• CPC Class Codes: G06F 18/00 Pattern recognition
• CPC Class Codes: G06V 30/142 using hand-held instruments; Constructional details of the instruments
• CPC Class Codes: G06V 30/196 using sequential comparisons of the image signals with a plurality of references
• CPC Class Codes: G06V 30/287 of Kanji, Hiragana or Katakana characters
• CPC Class Codes: G06V 30/347 Sampling; Contour coding; Stroke extraction

Abstract

A method and system for recognizing complex patterns, such as Chinese characters (or Kanji), identifies patterns by stroke recognition using detailed information about stroke shape and specifically curvature characteristics. Written strokes are categorized into different specific stroke types and are assigned stroke identity labels by comparison of distance metrics generated with reference to stroke templates, each template comprising information specifying position of a point and permissible deviation for each such point along a stroke. Deviation values may differ from point to point and from stroke type to stroke type. The data on the written stroke may be rotated or displaced relative to each stroke template to enhance the likelihood of stroke recognition. Limited information about stroke position relative to other strokes may be preserved and employed to resolve ambiguities among accumulations of stroke identity labels found to ambiguously indicate more than one pattern or character.

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 stroke based upon relative movement between a pattern-forming means and a pattern-accommodating means of said registration means, said registration means being operative to generate first signal information represented by first signals specifying relative position sequentially along a stroke, said data processing means being provided with prestored second signal information represented by second signals and being operative to generate third signals representing third signal information, said third signal information comprising specification of identity labels for strokes for use in developing coded information specifying said pattern, said method comprising for at least one stroke:

designating from said first signal information a set of sequential first data points, said set of first data points being selected from or interpolated on the basis of said first signal information along said stroke;

defining templates consisting of said second signal information, each said template comprising a set of second data points defining relative sequentially related position values and a set of permissible tolerance values, each of said tolerance values representing a preselected deviation for its associated second data point, at least one of said permissible tolerance values differing from at least one other of said permissible tolerance values for a single template; and

comparing said first data points with said second data points to determine which of said templates provides best correspondence between said first and second signal information to produce said third signal information.

2. The method according to claim 1, wherein position is represented in terms comprising angular numerical values in a polar coordinate system.

3. The method according to claim 1, wherein position is represented in terms comprising locations in a Cartesian coordinate system.

4. The method according to claim 1 or 2, further including the step, in the absence of acceptance of an identity label, of modifying said first signal information by adding or subtracting an incremental numerical value of at least one of said first data points and again comparing said first data points with each said template.

5. The method according to claim 4, wherein said modifying step comprises rotating said first signal information of at least one of said first data points relative to said second data points.

6. The method according to claim 1 or 2, further including the step of spacing said first and second data points evenly along a stroke, at least some of said first data points being points interpolated from said first signal information.

7. The method according to claim 1 or 2, characterized in that first data points are represented in terms comprising angular position values in a polar coordinate system at locations interpolated to correspond to locations of said second data points of said template.

8. The method according to claim 1 or 2, wherein said stroke registration means is a signal-receiving means responsive to movement of said character-forming means, and including the step of registering a stroke upon said stroke registration means.

9. The method according to claim 8, wherein said character-forming means comprises a writing implement and said stroke-registration means comprises a pressure-sensitive position-registering tablet, including the step of writing with said writing implement upon said tablet.

10. The method according to claim 1 or 2, wherein said character-forming means and said stroke-registration means comprise an instrumented writing implement operative to generate transducer signals specifying pressure and direction versus time, including the step of supplying said signals representing said first signal information to said data processing means in response to writing on a friction surface.

11. The method according to claim 1 or 2, further including the step, in the absence of acceptance of an identity label, modifying said first signal information to effect a displacement of said first data points relative to said second data points and again compares said first data points with each said template.

12. In the method according to claim 11, wherein said modifying step further comprises shifting said first data points relative to said second data points along stroke length.

13. In the method according to claim 1 or 2, further including the step of resolving said first signal information with an angular resolution at each one of said first data points to within no greater than 1.5 degrees.

14. In the method according to claim 1 or 2, further including the step of resolving said first signal information with an angular resolution at each one of said first data points to within no greater than 0.15 degrees.

15. In the method according to claim 1 or 2, wherein said comparing step comprises computing the closeness between each one of said first data points and said second data points to obtain a distance metric value.

16. The method according to claim 15, further including the step of comparing said distance metric value for each said template with an upper decision threshold value, with a lower decision threshold value and with a difference decision threshold value in order to obtain said identity label.

17. The method according to claim 16, further including the step of assigning a specific identity label of one of said predefined template strokes 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.

18. In the method according to claim 1 or 2, further including the step of calculating distance between corresponding first data points and second data points to obtain difference values;

dividing each one of said difference values by the corresponding permissible angular deviation value to obtain quotient values; and

summing all quotient values to obtain a distance-metric value.

19. In the method according to claim 18, further including the step of squaring each one of said quotient values prior to summing.

20. In the method according to claim 1 or 2, further including the steps of:

combining said third signals representing said identity label with other third signals representing other identity labels so obtained to form fourth signals representing a group of related identity labels; and

comparing said fourth signals against fifth signals, said fifth signals representing an index to character labels specified by sets of related identity labels to produce sixth signals, said sixth signals representing a character label corresponding to said group.

21. The method according to claim 20, further including the step of employing said sixth signals to form a visual pattern representing the character identified by said character label.

22. The method according to claim 20, wherein said character label corresponds to a Kanji character.

23. The method according to claim 22 wherein said Kanji character is handwritten relative to preceding first data points.

24. The method according to claim 20, further including the step of using information regarding sequence of said identity labels to produce said sixth signals representing character labels.

25. The method according to claim 1 or 2, further including the step of comparing said second signal information with said first signal information independent of absolute stroke position values.

26. The method according to claim 25, further including the step of preserving selected absolute stroke position values of said first signal information independent of said identifying step, and employing said selected absolute stroke position values to resolve ambiguity among recognized patterns only in the event a plurality of patterns is indicated for a single accumulation of identity labels.

27. 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 stroke based on relative movement between a pattern-forming means and a pattern-accommodating means of said stroke registration means, said stroke registration means being operative to generate first signal information represented by first signals specifying relative position sequentially along a stroke, said data processing means being provided with prestored second signals and being operative to generate third signals representing third signal information, said third signal information comprising specification of identity labels for strokes for use in developing coded information specifying said pattern, the improvement characterized in that:

said data processing means includes means for designating from said first signal information a set of sequential first data points, said set of first data points being selected from or interpolated on the basis of said first signal information, along said stroke means defining templates consisting of said second signal information, each said template comprising a set of second data points defining relative sequential position values and set of permissible tolerance values, each of said tolerance values representing a preselected deviation for its associated second data point, at least one of said permissible tolerance values differing from at least one other of said permissible tolerance values for a single template; and

means for comparing said first data points with said second data points to determine which of said templates provides best correspondence between said first and second signal information to produce said third signal information.

28. In the apparatus according to claim 27, characterized in that said pattern-accommodating means is a signal-receiving means responsive to relative movement of said pattern-forming means.

29. In the apparatus according to claim 27 wherein said pattern-forming means comprises a writing implement and said pattern-accommodating means comprises a pressure-sensitive position-registration tablet.

30. In the apparatus according to claim 27 wherein said pattern-forming means and said pattern-accommodating means are characterized by an instrumented writing implement operative to generate transducer signals specifying pressure and direction versus time in response to an act of writing with said implement on a friction surface.

31. In the apparatus according to claim 27, characterized in that said data processing means includes means for rotating said first signal information relative to position values of said second signal information.

32. In the apparatus according to claim 27, characterized in that said data processing means includes means for displacing said first signal information relative to position values of said second signal information.

33. In the apparatus according to claim 27, characterized in that said data processing means includes means for preserving selected absolute stroke position values of said first original information independent of said identifying step and to employ said selected absolute stroke position values to resolve ambiguity among recognized patterns only in the event a plurality of patterns is indicated for a single accumulation of identity labels.

34. In the apparatus according to claim 27, characterized in that said data processing means includes means for comparing said first signal information with said second signal information independent of relative stroke size.

35. In the apparatus according to claim 27, characterized in that said data processing means includes means for comparing said second signal information with said first single information independent of absolute stroke position values.

36. The apparatus according to claim 27 wherein said comprising means includes means coupled to receive said first signal information and said second signal information for computing closeness between each one of said first data points and said second data points to obtain a distance metric value for each one of said templates, means coupled to receive each said distance metric value for comprising each said distance metric value with an upper decision threshold, with a lower decision threshold and a difference decision threshold, and means for assigning a specific identity label of one of said predefined template strokes as said third signal information if the least distance metric value is less than the upper decision thresold 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.

37. A method for identifying patterns by means of a pattern registration means and a data processing means, wherein each pattern comprises at least one stroke based upon relative movement between a pattern-forming means and a pattern-accommodating means of said registration means, said registration means being operative to generate first signal information represented by first signals specifying relative position sequentially along a stroke, said data processing means being provided with prestored second signal information represented by second signals and being operative to generate third signals representing third signal information, said third signal information comprising specification of identity labels for strokes for use in developing coded information specifying said pattern, said method comprising for at least one stroke:

designating from said first signal information a set of first data points on the basis of said first signal information along said stroke;

defining templates consisting of said second signal information, each said template comprising a set of second data points defining at least relative sequentially related position values;

comparing said first data points with said second data points by computing the closeness between each one of said first data points and said second data points to obtain a distance metric value for each of said templates, thereafter comparing said distance metric value for each said template with an upper decision threshold, with a lower decision threshold and with a difference threshold and assigning a specific identity label of one of said predefined template strokes as said third signal information 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.

38. The method according to claim 37, further including the step, in the absence of acceptance of an identity label, of modifying said first signal information by adding or subtracting an incremental numerical value of at least one of said first data points and again comparing said first data points with each said template.

39. The method according to claim 37, further including the step, in the absence of acceptance of an identity label, modifying said first signal information to effect a displacement of said first data points relative to said second data points and again compares said first data points with each said template.

40. In the method according to claim 37, further including the steps of:

combining said third signals representing said identity label with other third signals representing other identity labels so obtained to form fourth signals representing a group of related identity labels; and

comparing said fourth signals against fifth signals, said fifth signals representing an index to character labels specified by sets of related identity labels to produce sixth signals, said sixth signals representing a character label corresponding to said group.

41. The method according to claim 37, further including the step of comparing said second signal information with said first signal information independent of absolute stroke position values.

42. The method according to claim 37, further including the step of preserving selected absolute stroke position values of said first signal information independent of said identifying step, and employing said selected absolute stroke position values to resolve ambiguity among recognized patterns only in the event a plurality patterns is indicated for a single accumulation of identity labels.