Method and system for velocity-based handwriting recognition

• US 5,768,417 A
• Filed: 12/01/1995
• Issued: 06/16/1998
• Est. Priority Date: 09/09/1994
• Status: Expired due to Term

• Current Assignee: Google Technology Holdings LLC (Alphabet Inc.)
• Original Assignee: Motorola, Inc. (Motorola Solutions, Inc.)
• Inventors: Errico, James H., Wang, Shay-Ping T., Murdock, Michael C.
• Primary Examiner(s): Couso, Yon J.
• Assistant Examiner(s): NGUYEN, HA T
• Application Number:
  US08/566,358
• Time in Patent Office: 928 Days
• Field of Search: 382/186, 382/187, 382/122, 382/119, 382/120, 382/188, 382/189, 382/185, 382/207, 382/137
• US Class Current: 382/186
• CPC Class Codes: G06F 18/2453 non-linear, e.g. polynomial classifier
• CPC Class Codes: G06V 30/10 Character recognition
• CPC Class Codes: G06V 30/1423 the instrument generating sequences of position coordinates corresponding to handwriting preprocessing or recognising digital ink G06V30/32
• CPC Class Codes: G06V 30/153 using recognition of characters or words
• CPC Class Codes: G06V 30/2268 using stroke segmentation
• 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
• CPC Class Codes: G06V 30/262 using context analysis, e.g. lexical, syntactic or semantic context
• CPC Class Codes: G06V 30/347 Sampling; Contour coding; Stroke extraction
• CPC Class Codes: G06V 30/36 Matching; Classification

Abstract

The invention provides a computer-implementable method for detecting substroke boundaries in handwriting input. The method selects pen tip velocity extremas to represent. substroke boundaries. The method includes steps for generating a velocity profile from the handwriting input; identifying a plurality of peak extrema within the velocity profile; identifying a plurality of in-line extrema within the velocity profile; and detecting the substroke boundaries by filtering the plurality of peak extrema and the plurality of in-line extrema.

Claims

1. In a computer, a method for detecting a plurality of substroke boundaries in handwriting input, the method comprising the following steps:

(a) generating a velocity profile from the handwriting input;

(b) identifying a plurality of peak extrema within the velocity profile;

(c) identifying a plurality of in-line extrema within the velocity profile;

(d) selecting a plurality of filtered extrema from the plurality of peak extrema and the plurality of in-line extrema, the plurality of filtered extrema being separated one from another by a minimum number of intervening samples; and

(e) equating the substroke boundaries to the plurality of filtered extrema.

2. The method of claim 1, wherein step (b) includes the following sub-steps:

identifying a plurality of local extrema within the velocity profile, each of the plurality of local extrema having a direction;

selecting a first local extrema from the plurality of local extrema;

comparing the first local extrema with a subsequent local extrema having an opposite direction to generate a difference; and

determining whether the difference is greater than a peak threshold, if so, identifying the first local extrema and the subsequent local extrema as each being a peak extrema.

3. The method of claim 1, wherein step (c) includes the following sub-steps:

identifying a peak group within the velocity profile, the peak group including a plurality of local extrema and being bounded by a pair of peak extremas having opposite directions, each of the plurality of local extrema having a direction;

selecting a first local extrema from the plurality of local extrema;

comparing the first local extrema with a subsequent local extrema having an opposite direction to generate a difference; and

determining whether the difference is greater than an in-line threshold, if so, identifying the first local extrema and the subsequent local extrema as each being an in-line extrema.

4. The method of claim 1, wherein step (c) includes the following sub-steps:

identifying a peak group within the velocity profile, the peak group including a plurality of local extrema and being bounded by a pair of peak extremas having opposite directions, each of the plurality of local extrema having a direction;

selecting a first local extrema from the plurality of local extrema;

comparing the first local extrema with a subsequent local extrema having an opposite direction to generate a first difference;

comparing the first local extrema and the subsequent local extrema to at least one of the pair of peak extremas to generate a pair of second differences; and

determining whether the first difference is greater than an in-line threshold and the pair of second differences is greater than an in-line/peak threshold, if so, identifying the first local extrema and the subsequent local extrema as each being an in-line extrema.

5. The method of claim 1, wherein the substroke boundaries are represented by extremas having same directions.

6. The method of claim 5, wherein the substroke boundaries are indicated by minimas in the velocity profile.

7. The method of claim 1, further comprising the steps of:

identifying a half-substroke in the handwriting input, the half-substroke being delimited by a pair of substroke boundaries having opposite directions; and

concatenating the half-substroke to an adjoining substroke.

8. The method of claim 1, further comprising the steps of:

identifying a half-substroke in the handwriting input, the half-substroke being delimited by a pair of substroke boundaries having opposite directions; and

indicating the half-substroke to be a regular substroke.

9. In a computer, a method for detecting a substroke boundary in handwriting input, the method comprising the following steps:

(a) generating a velocity profile from the handwriting input;

(b) identifying a plurality of local extrema within the velocity profile, each of the plurality of local extrema having a direction;

(c) selecting a first local extrema from the plurality of local extrema;

(d) comparing the first local extrema with a subsequent local extrema having an opposite direction to generate a difference;

(e) identifying the first local extrema and the subsequent local extrema as each being a peak extrema based on a comparison between the difference and a peak threshold, whereby identifying a plurality of peak extrema;

(f) identifying a plurality of in-line extrema within the velocity profile;

(g) detecting a substroke boundary by filtering the plurality of peak extrema and the plurality of in-line extrema.

10. The method of claim 9, wherein step (f) includes the following sub-steps:

identifying a peak group within the velocity profile, the peak group including a plurality of local extrema and being bounded by a pair of peak extrema having opposite directions, each of the plurality of local extrema having a direction;

selecting a first local extrema from the plurality of local extrema;

comparing the first local extrema with a subsequent local extrema having an opposite direction to generate a difference; and

determining whether the difference is greater than an in-line threshold, if so, identifying the first local extrema and the subsequent local extrema as each being an in-line extrema.

11. The method of claim 9, wherein step (f) includes the following sub-steps:

identifying a peak group within the velocity profile, the peak group including a plurality of local extrema and being bounded by a pair of peak extremas having opposite directions, each of the plurality of local extrema having a direction;

selecting a first local extrema from the plurality of local extrema;

comparing the first local extrema with a subsequent local extrema having an opposite direction to generate a first difference;

comparing the first local extrema and the subsequent local extrema to at least one of the pair of peak extremas to generate a pair of second differences; and

determining whether the first difference is greater than an in-line threshold and the pair of second differences is greater than an in-line/peak threshold, if so, identifying the first local extrema and the subsequent local extrema as each being an in-line extrema.

12. The method of claim 9, wherein step (g) includes the following sub-steps:

selecting a plurality of filtered extrema from the plurality of peak extrema and the plurality of in-line extrema, the plurality of filtered extrema being separated one from another by a minimum number of intervening coordinate pairs; and

equating the sequence of substroke boundaries to the plurality of filtered extrema.

13. The method of claim 9, wherein a plurality of substroke boundaries are based on extremas having same directions.

14. The method of claim 13, wherein a plurality of substroke boundaries are indicated by minimas in the velocity profile.

15. In a computer, a method for generating a substroke frame from handwriting input, the method comprising the following steps:

receiving a sequence of coordinate pairs that represent the handwriting input;

generating a velocity profile from the sequence of coordinate pairs;

identifying a plurality of local extrema within the velocity profile, each of the plurality of local extrema having a direction;

selecting a first local extrema from the plurality of local extrema;

comparing the first local extrema with a subsequent local extrema having an opposite direction to generate a first difference;

determining whether the first difference is greater than a peak threshold, if so, identifying the first local extrema and the subsequent local extrema as each being a peak extrema, whereby identifying a plurality of peak extrema;

identifying a peak group within the velocity profile, the peak group being bounded by a pair of peak extremas having opposite directions;

selecting a second local extrema from ones of the plurality of local extrema occurring within the peak group;

comparing the second local extrema with a second subsequent local extrema having an opposite direction to generate a second difference;

determining whether the second difference is greater than an in-line threshold, if so, identifying the second local extrema and the second subsequent local extrema as each being an in-line extrema, whereby identifying a plurality of in-line extremas;

selecting a plurality of filtered extrema from the plurality of peak extrema and the plurality of in-line extrema, the plurality of filtered extrema being separated one from another by a minimum number of intervening coordinate pairs;

equating a sequence of substroke boundaries to the plurality of filtered extrema; and

generating the substroke frame according to the sequence of substroke boundaries, the substroke frame including those of the sequence of coordinate pairs that occur between a subsequent pair of the sequence of substroke boundaries.

16. The method of claim 15, further comprising the steps of:

comparing the plurality of inline-extremas to the pair of peak extremas to generate a plurality of third differences; and

disregarding ones of the plurality of in-line extremas that correspond to those of the plurality of third differences less than or equal to an in-line/peak threshold.

17. The method of claim 15, wherein the substroke boundaries are represented by extremas having same directions.

18. The method of claim 17, wherein the substroke boundaries are indicated by minimas in the velocity profile.

19. The method of claim 15, further comprising the steps of:

identifying a half-substroke in the handwriting input, the half-substroke being delimited by a pair of substroke boundaries having opposite directions; and

concatenating the half-substroke to an adjoining substroke.

20. The method of claim 16, further comprising the steps of:

identifying a half-substroke in the handwriting input, the half-substroke being delimited by a pair of substroke boundaries having opposite directions; and

indicating the half-substroke to be a regular substroke.

21. An article of manufacture, comprising:

a computer-readable memory usable for causing a computer to detect substroke boundaries in handwriting input, the computer-readable memory having a structure defined by storing a computer program in the computer-readable memory, wherein the computer program includes a method for detecting substroke boundaries comprising the following steps;

(a) generating a velocity profile from the handwriting input;

(b) identifying a plurality of peak extrema within the velocity profile;

(c) identifying a plurality of in-line extrema within the velocity profile;

(d) selecting a plurality of filtered extrema from the plurality of peak extrema and the plurality of in-line extrema, the plurality of filtered extrema being separated one from another by a minimum number of intervening samples; and

(e) equating the substroke boundaries to the plurality of filtered extrema.

22. The article of manufacture of claim 21, wherein step (b) of the method includes the following sub-steps:

identifying a plurality of local extrema within the velocity profile, each of the plurality of local extrema having a direction;

selecting a first local extrema from the plurality of local extrema;

comparing the first local extrema with a subsequent local extrema having an opposite direction to generate a difference; and

determining whether the difference is greater than a peak threshold, if so, identifying the first local extrema and the subsequent local extrema as each being a peak extrema.

23. The article of manufacture of claim 21, wherein step (c) of the method includes the following sub-steps:

identifying a peak group within the velocity profile, the peak group including a plurality of local extrema and being bounded by a pair of peak extrema having opposite directions, each of the plurality of local extrema having a direction;

selecting a first local extrema from the plurality of local extrema;

comparing the first local extrema with a subsequent local extrema having an opposite direction to generate a difference; and

determining whether the difference is greater than an in-line threshold, if so, identifying the first local extrema and the subsequent local extrema as each being an in-line extrema.

24. The article of manufacture of claim 21, wherein step (c) includes the following sub-steps:

identifying a peak group within the velocity profile, the peak group including a plurality of local extrema and being bounded by a pair of peak extremas having opposite directions, each of the plurality of local extrema having a direction;

selecting a first local extrema from the plurality off local extrema;

comparing the first local extrema with a subsequent local extrema having an opposite direction to generate a first difference;

comparing the first local extrema and the subsequent local extrema to at least one of the pair of peak extremas to generate a pair of second differences; and

determining whether the first difference is greater than an in-line threshold and the pair of second differences is greater than an in-line/peak threshold, if so, identifying the first local extrema and the subsequent local extrema as each being an in-line extrema.

25. The article of manufacture of claim 21, wherein the substroke boundaries are represented by extremas having same directions.

26. The article of manufacture of claim 25, wherein the substroke boundaries are indicated by minimas in the velocity profile.

27. The article of manufacture of claim 21, wherein the method further comprises the steps of:

identifying a half-substroke in the handwriting input, the half-substroke being delimited by a pair of substroke boundaries having opposite directions; and

concatenating the half-substroke to an adjoining substroke.

28. The article of manufacture of claim 21, wherein the method further comprises the steps of:

identifying a half-substroke in the handwriting input, the half-substroke being delimited by a pair of substroke boundaries having opposite directions; and

indicating the half-substroke to be a regular substroke.

29. A system for detecting a plurality of substroke boundaries in handwriting input, comprising:

a velocity profile calculator for generating a velocity profile from the handwriting input;

a peak extrema detector for identifying a plurality of peak extrema within the velocity profile;

an in-line extrema detector for identifying a plurality of in-line extrema within the velocity profile; and

an extrema filter for detecting the substroke boundaries by filtering the plurality of peak extrema and the plurality of in-line extrema, the extrema filter including a selector for equating the substroke boundaries to a plurality of filtered extrema, the selector selecting the plurality of filtered extrema from the plurality of peak extrema and the plurality of in-line extrema, the plurality of filtered extrema being separated one from another by a minimum number of intervening samples.

30. The system of claim 29, wherein the peak extrema detector includes:

a local extrema detector for identifying a plurality of local extrema within the velocity profile, each of the plurality of local extrema having a direction;

a first selector for selecting a first local extrema from the plurality of local extrema; and

a first comparator for comparing the first local extrema with a subsequent local extrema having an opposite direction to generate a difference, the first comparator then determining whether the difference is greater than a peak threshold, and if so, identifying the first local extrema and the subsequent local extrema as each being a peak extrema.

31. The system of claim 29, wherein the in-line extrema detector includes:

a peak group detector for identifying a peak group within the velocity profile, the peak group including a plurality of local extrema and being bounded by a pair of peak extrema having opposite directions, each of the plurality of local extrema having a direction;

a second selector for selecting a first local extrema from the plurality of local extrema; and

a second comparator for comparing the first local extrema with a subsequent local extrema having an opposite direction to generate a difference, the second comparator then determining whether the difference is greater than an in-line threshold, and if so, identifying the first local extrema and the subsequent local extrema as each being an in-line extrema.

32. The system of claim 29, wherein the in-line extrema detector includes:

a peak group detector for identifying a peak group within the velocity profile, the peak group including a plurality of local extrema and being bounded by a pair of peak extrema having opposite directions, each of the plurality of local extrema having a direction;

a second selector for selecting a first local extrema from the plurality of local extrema; and

a second comparator for comparing the first local extrema with a subsequent local extrema having an opposite direction to generate a first difference and for comparing the first local extrema and the subsequent local extrema to one of the pair of peak extremas to generate a pair of second differences, the second comparator determining whether the first difference is greater than an in-line threshold and the pair of second differences is greater than an in-line/peak threshold, if so, identifying the first local extrema and the subsequent local extrema as each being an in-line extrema.

33. The system of claim 29, wherein the substroke boundaries are represented by extremas having same directions.

34. The system of claim 33, wherein the substroke boundaries are indicated by minimas in the velocity profile.

35. The system of claim 29, further comprising:

a half-stroke detector for identifying a half-substroke in the handwriting input, the half-substroke being delimited by a pair of substroke boundaries having opposite directions; and

means for concatenating the half-substroke to an adjoining substroke.

36. The system of claim 29, further comprising:

a half stroke detector for identifying a half-substroke in the handwriting input, the half-substroke being delimited by a pair of substroke boundaries having opposite directions; and

means for indicating the half-substroke to be a regular substroke.