Stroke segmentation for template-based cursive handwriting recognition

• US 20050100214A1
• Filed: 11/10/2003
• Published: 05/12/2005
• Est. Priority Date: 11/10/2003
• Status: Active Grant

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Corporation
• Inventors: Abdulkader, Ahmad A., Zhang, Qi, Rowley, Henry A., Guha, Angshuman
• Granted Patent: US 7,302,099 B2
• Time in Patent Office: Days
• US Class Current: 382/179
• CPC Class Codes: G06V 30/1423 the instrument generating sequences of position coordinates corresponding to handwriting preprocessing or recognising digital ink G06V30/32

Abstract

Ink strokes of cursive writing are segmented to make the cursive writing more like print writing, particularly with respect to the number of strokes of a character. A stroke-segmentation module first finds the local extrema points on a stroke of input ink. Then the local extrema points are stepped through, two (or three) at a time. The stroke-segmentation module may compare the three (or four) ink segments that are adjacent to the two (or three) local extrema points to a set of predefined stroke-segmentation patterns to find a closest matching pattern. Strokes are then segmented based on a stroke-segmentation rule that corresponds to the closest matching pattern. Additional stroke segmentation may be performed based on the change of curvature of the segmented ink strokes. Then, a character-recognition module performs character recognition processing by comparing the segmented ink strokes to prototype samples at least some of which have been similarly segmented.

Claims

1. A method of segmenting at least one ink stroke into at least one plurality of segmented ink strokes, the method comprising:

finding at least one pair of local extrema points on the at least one ink stroke;

identifying a closest matching stroke-segmentation pattern by comparing at least first, second, and third stroke segments of the at least one ink stroke to a set of stroke-segmentation patterns, wherein the first, second, and third stroke segments are adjacent to the at least one pair of local extrema points; and

segmenting the at least one ink stroke into the at least one plurality of segmented ink strokes based on a stroke-segmentation rule that corresponds to the identified closest matching stroke-segmentation pattern.

2. The method of claim 1, wherein finding the at least one pair of local extrema points comprises:

traversing a plurality of points along the at least one ink stroke and detecting when the at least one ink stroke changes direction along an x-axis or a y-axis and moves more than a threshold distance in the changed direction.

3. The method of claim 1, wherein segmenting the at least one ink stroke further comprises at least one of:

removing at least one of the first, second, and third stroke segments, and breaking the at least one ink stroke at or near at least one local extrema point of the pair of local extrema points.

4. The method of claim 1, further comprising segmenting the at least one plurality of segmented ink strokes based on a property of a curvature of the at least one plurality of segmented ink strokes, wherein the property is selected from the group consisting of:

an inflection point between rotation of the at least one segmented ink stroke from a first direction to a second direction, and a cumulative curvature change of the at least one segmented ink stroke of greater than approximately 360 degrees.

5. The method of claim 1, wherein the at least one ink stroke is at least a part of an East Asian cursive character.

6. The method of claim 5, wherein the stroke-segmentation rule is based on common patterns in East Asian cursive writing.

7. The method of claim 6, further comprising:

performing character-recognition processing on the plurality of segmented ink strokes.

8. The method of claim 7, wherein the character-recognition processing uses East Asian print prototype samples.

9. At least one computer-readable medium having computer-executable instructions for performing steps comprising:

finding at least one pair of local extrema points on at least one ink stroke;

identifying a stroke-segmentation rule to be applied to at least one segment of ink that is adjacent to a point of the at least one pair of local extrema points; and

applying the identified stroke-segmentation rule to segment the at least one ink stroke into at least one plurality of ink strokes, wherein the stroke-segmentation rule causes to occur at least one of;

removing an ink segment from between the at least one pair of local extrema points, and

breaking the ink stroke at or near at least one local extrema point of the at least one pair of local extrema points.

10. The at least one computer-readable medium of claim 9, wherein finding the at least one pair of local extrema points comprises:

traversing a plurality of points along the at least one ink stroke and detecting when the at least one ink stroke changes direction along an x-axis or a y-axis and moves more than a threshold distance in the changed direction.

11. The at least one computer-readable medium of claim 9 having further computer-executable instructions for performing the step of:

identifying the stroke-segmentation rule by comparing at least first, second, and third stroke segments of the at least one ink stroke to a set of stroke-segmentation patterns, wherein the first, second, and third stroke segments are adjacent to the at least one pair of local extrema points and wherein the identified stroke-segmentation rule is associated with a closest matching stroke-segmentation pattern of the set of stroke-segmentation patterns.

12. The at least one computer-readable medium of claim 9, further comprising segmenting a stroke of the at least one plurality of segmented ink strokes based on a property of a curvature of the stroke of the at least one plurality of segmented ink strokes, wherein the property is selected from the group consisting of:

an inflection point between rotation of the stroke of the at least one plurality of segmented ink strokes from a first direction to a second direction, and a cumulative curvature change of the stroke of the at least one plurality of segmented ink strokes of greater than approximately 360 degrees.

13. The at least one computer-readable medium of claim 9, wherein the at least one ink stroke is at least a part of an East Asian cursive character.

14. The at least one computer-readable medium of claim 13, wherein the stroke-segmentation rule is based on common patterns in East Asian cursive writing.

15. The at least one computer-readable medium of claim 14, further comprising:

performing character-recognition processing on the plurality of segmented ink strokes.

16. The at least one computer-readable medium of claim 15, wherein the character-recognition processing uses East Asian print prototype samples.

17. A system for segmenting at least one ink stroke into at least one plurality of segmented ink strokes, the system comprising:

an ink creation module that captures handwritten characters; and

a stroke segmentation module that;

finds at least one pair of local extrema points on the at least one ink stroke,

identifies a stroke-segmentation rule to be applied to at least one segment of ink that is adjacent to a point of the at least one pair of local extrema points, and

applies the identified stroke-segmentation rule to segment the at least one ink stroke into at least one plurality of ink strokes.

18. The system of claim 17, wherein finding the at least one pair of local extrema points comprises:

traversing a plurality of points along the at least one ink stroke and detecting when the at least one ink stroke changes direction along an x-axis or a y-axis and moves more than a threshold distance in the changed direction.

19. The system of claim 17, wherein applying the identified stroke-segmentation rule causes to occur at least one of:

removing an ink segment from between the at least one pair of local extrema points, and breaking the ink stroke at or near at least one local extrema point of the at least one pair of local extrema points.

20. The system of claim 17, wherein identifying the stroke-segmentation rule comprises:

comparing at least first, second, and third stroke segments of the at least one ink stroke to a set of stroke-segmentation patterns, wherein the first, second, and third stroke segments are adjacent to the at least one pair of local extrema points and wherein the identified stroke-segmentation rule is associated with a closest matching stroke-segmentation pattern of the set of stroke-segmentation patterns.

21. The system of claim 17, further comprising segmenting a stroke of the at least one plurality of segmented ink strokes based on a property of a curvature of the stroke of the at least one plurality of segmented ink strokes, wherein the property is selected from the group consisting of:

an inflection point between rotation of the stroke of the at least one plurality of segmented ink strokes from a first direction to a second direction, and a cumulative curvature change of the stroke of the at least one plurality of segmented ink strokes of greater than approximately 360 degrees.

22. The system of claim 17, wherein the at least one ink stroke is at least a part of an East Asian cursive character.

23. The system of claim 22, wherein the stroke-segmentation rule is based on knowledge of at least one pattern that is likely to appear in East Asian cursive writing.

24. The system of claim 23, further comprising:

a character recognition module that performs character-recognition processing on the plurality of segmented ink strokes.

25. The system of claim 24, wherein the character-recognition processing uses East Asian print prototype samples.