Handwriting recognition device, method and alphabet, with strokes grouped into stroke sub-structures

• US 6,275,611 B1
• Filed: 10/17/1996
• Issued: 08/14/2001
• Est. Priority Date: 10/17/1996
• Status: Expired due to Term

• Current Assignee: Google Technology Holdings LLC (Alphabet Inc.)
• Original Assignee: Motorola, Inc. (Motorola Solutions, Inc.)
• Inventors: Parthasarathy, Kannan
• Primary Examiner(s): Bella, Matthew C.
• Application Number:
  US08/732,957
• Time in Patent Office: 1,762 Days
• Field of Search: 382/185, 382/186, 382/187, 382/188, 382/189, 382/190, 382/191, 382/197, 382/200, 382/202, 382/209, 382/213, 382/214, 382/215, 382/220, 382/225, 382/228, 382/229 , 382/231, 382/288, 345/173, 345/175
• US Class Current: 382/187
• CPC Class Codes: G06V 10/44 Local feature extraction by analysis of parts of the pattern, e.g. by detecting edges, contours, loops, corners, strokes or intersections; Connectivity analysis, e.g. of connected components
• CPC Class Codes: G06V 30/10 Character recognition
• CPC Class Codes: G06V 30/373 using a special pattern or subpattern alphabet

Abstract

A method of representing handwriting which includes receiving a pen input, for example at a digitizer (10), segmenting the input into strokes (13), grouping the strokes into stroke sub-structures (14) and quantizing the stroke sub-structures according to a predefined set (the “alphabet”) of stroke sub-structures. For handwriting recognition, distance measurements are computed between the input stroke sub-structures and members of a predefined set or “alphabet” (19) of stroke sub-structures.

Claims

1. A method of recognizing handwriting comprising the steps of:

receiving a pen input comprising one or more alphanumeric symbols;

determining the maximum number of segments that an alphanumeric symbol may have;

segmenting the pen input into strokes at significant bends in the pen input;

preprocessing the strokes to enable cursive forms of writing and print forms of writing to be handled in the same manner;

grouping the strokes into stroke substructures; and

computing distance and angle measurements between the input stroke substructures and members and members of a predefined set of strokes and primitive stroke substructures.

2. The method of claim 1 wherein the primitive stroke substructures comprise between 2 and 4 straight line strokes.

3. The method of claim 1 further comprising storing a set of templates, each template comprising stroke sub-structures selected from the predefined set of stroke sub-structures.

4. The method of claim 1 further comprising:

storing a set of templates, each template comprising stroke substructures selected from the predefined set of stroke substructures; and

computing distance measurements between input stroke substructures and stroke sub-structures of a template.

5. The method of claim 3, wherein the stroke sub-structures of each template are quantized according to the predefined set of stroke substructures.

6. The method of claim 4 further comprising selecting, from the set of templates, a selected subset of templates dependent on the step of computing distance measurements, where the templates of the selected subset provide lower distance measurements with respect to the stroke sub-structures that other templates not included in the selected subset.

7. The method of claim 6 further comprising using the selected subset of templates for recognition of the pen input.

8. The method of claim 7 further comprising performing distance computations between templates of the selected subset of templates and the pen input to establish at least one template most closely matching the pen input.

9. The method of claim 7, wherein the step of computing distance measurements includes a relatively coarse distance computation and the step of using the selected subset of templates includes a relatively fine distance computation.

10. The method of claim 7 further comprising unpacking the templates of the selected subset into unpacked data defining strokes of the stroke sub-structures and matching the pen input with the unpacked data.

11. The method of claim 3, further comprising establishing a window of comparison for stroke sub-structures including, where present, at least one stroke in front of a stroke sub-structure to be compared and one stroke following the stroke sub-structure to be compared and computing distance measurements for stroke sub-structures within the window.

12. A method of providing an alphabet of sub-strokes for handwriting recognition comprising:

collecting pen input from a plurality of writers of a selected language;

determining the maximum number of segments that an alphanumeric symbol may have;

identifying segmentation points in the pen input that are at significant bends in the pen input;

segmenting the pen input at the segmentation points into strokes and stroke sub-structures;

parameterizing the strokes and stroke substructures to provide stroke parameters;

establishing an alphabet size;

deriving an alphabet of a first set of strokes and at least a second set of stoke sub-structures, by clustering the strokes and stroke sub-structures and averaging stroke parameters across samples in a cluster, where the total number of elements in the sets is equal to the alphabet size; and

introducing during a preprocessing procedure any required artificial strokes to correspond to pen motion to enable cursive forms of writing to be handled the same way as print forms of writing.

13. The method according to claim 12, further comprising generating cluster centers.

14. The method according to claim 13, further comprising storing the cluster centers in terms of parameters defining the cluster centers.

15. A device for handwriting recognition comprising:

a memory having instructions and data stored therein that, when executed cause a digital processor to comprise;

a pen stroke information input;

a segmenter and grouper coupled to the input, having a stroke and stroke sub-structure output;

a processor to preprocess the strokes to enable cursive forms of handwriting and print forms of handwriting to be handled in the same manner the process further for determining the maximum number of segments that an alphanumeric symbol may have;

a template store having stored therein templates quantized according to a predefined alphabet of strokes and stroke substructures; and

a quantizer operative on the segmenter and grouper to compute distance and angle measurements between parameters of strokes and stroke sub-structures of the stroke and stroke sub-structure output and parameters of strokes and stroke sub-structures of templates in the template store and thereby to select at least one template.

16. A device according to claim 15, wherein the memory further has instructions and data stored therein that, when executed cause a digital processor to comprise a predefined set of stroke sub-structures, and cause the quantizer to accept sub-structures of the predefined set as input.

17. A method of recognizing handwriting comprising the steps of:

receiving a pen input;

segmenting the input into parameterized straight-line strokes at significant bends in the pen input;

preprocessing the strokes to enable cursive and print character entry to be handled in the same manner;

determining the maximum number of segments that an alphanumeric symbol may have;

grouping the straight-line strokes into input stroke sub-structures comprising combinations of straight-line strokes; and

computing distance and angle measurements between parameters of the input stroke sub-structures and corresponding parameters of members of a predefined set of strokes and primitive stroke sub-structures.

18. The method of claim 17, wherein the step of grouping includes grouping straight-line strokes that span a pen-up event into straight-line stroke sub-structures.