Segmentation of overwritten online handwriting input

• US 9,418,281 B2
• Filed: 12/30/2013
• Issued: 08/16/2016
• Est. Priority Date: 12/30/2013
• Status: Active Grant

• Current Assignee: Google LLC (Alphabet Inc.)
• Original Assignee: Google Inc. (Alphabet Inc.)
• Inventors: Rowley, Henry Allan, Deselaers, Thomas, Wang, Li-Lun
• Primary Examiner(s): Patel, Jayesh A
• Application Number:
  US14/142,964
• Publication Number:
  US 20150186718A1
• Time in Patent Office: 960 Days
• Field of Search: None
• US Class Current: 1/1
• CPC Class Codes: G06V 30/32 Digital ink

Abstract

Implementations of the disclosed subject matter provide methods and systems for identifying a candidate character cut for an overwritten character. A method may include providing a handwriting input area. The handwriting input area may be divided into multiple sections and a first portion of the multiple sections may be located in an end point region. A first handwritten input comprising a first stroke that ends in a section located in the end point region may be received. A second handwritten input comprising a second stroke that begins in a section that is not located in the end point region may be received. As a result, a first candidate character cut may be identified between the first stroke and the second stroke.

Claims

1. A computer-implemented method comprising:

receiving, by a computing device, a sequence of strokes that represent a handwritten input that trace shapes of one or more handwritten characters along a handwriting input area of the computing device;

determining, by the computing device, a predetermined sub-area of the handwriting input area that is characterized as a character end point sub-area;

determining, by the computing device, that (i) an end point of a first stroke of the sequence of strokes occurs in the predetermined sub-area of the handwriting input area that is characterized as a character end point sub-area, and (ii) a beginning point of a second stroke of the sequence of strokes that immediately follows the first stroke occurs in a second sub-area of the handwriting input area that is not characterized as a character end point sub-area;

based on determining that (i) the end point of the first stroke of the sequence of strokes occurs in the predetermined sub-area of the handwriting input area that is characterized as a character end point sub-area and (ii) the beginning point of the second stroke of the sequence of strokes that immediately follows the first stroke occurs in the second sub-area of the handwriting input area that is not characterized as a character end point sub-area, designating, by the computing device, the end point of the first stroke as a candidate end point of a first handwritten character traced by the sequence of strokes; and

obtaining, by the computing device, a recognized character corresponding to the first handwritten character based at least in part on the designated candidate end point of the first handwritten character.

2. The method of claim 1, comprising:

based on determining that (i) the end point of the first stroke of the sequence of strokes occurs in the predetermined sub-area of the handwriting input area that is characterized as a character end point sub-area and (ii) the beginning point of the second stroke of the sequence of strokes that immediately follows the first stroke occurs in the second sub-area of the handwriting input area that is not characterized as a character end point sub-area, designating, by the computing device, the second stroke as being associated with a second handwritten character.

3. The method of claim 1, wherein a location of the predetermined sub-area of the handwriting input area that is characterized as a character end point sub-area is based on a script associated with the handwritten input.

4. The method of claim 3, wherein the script is associated with a language.

5. The method of claim 1, wherein the predetermined sub-area of the handwriting input area that is characterized as a character end point sub-area is located in a bottom right portion of the handwriting input area.

6. The method of claim 1, comprising:

determining, by the computing device, that a beginning point of a third stroke of the sequence of strokes that immediately follows the second stroke occurs in the predetermined sub-area of the handwriting input area that is characterized as a character end point sub-area.

7. The method of claim 1, comprising:

determining, by the computing device, a distance between a left edge of the second stroke and a right edge of the second stroke.

8. The method of claim 7, comprising:

determining, by the computing device, that a beginning point of a third stroke of the sequence of strokes that immediately follows the second stroke occurs between the left edge of the second stroke and the right edge of the second stroke.

9. The method of claim 8, comprising:

determining, by the computing device, that a distance between the beginning point of the third stroke and the left edge of the second stroke satisfies a threshold distance.

10. The method of claim 9, wherein determining, by the computing device, that the distance between the beginning point of the third stroke and the left edge of the second stroke satisfies the threshold distance comprises:

determining, by the computing device, that the distance between the beginning point of the third stroke and the left edge of the second stroke is less than 25% of the distance between the left edge of the second stroke and the right edge of the second stroke.

11. The method of claim 10, comprising:

designating, by the computing device, the third stroke as being associated with a third handwritten character that is not associated with the first stroke or the second stroke.

12. The method of claim 9, wherein determining, by the computing device, that the distance between the beginning point of the third stroke and the left edge of the second stroke satisfies the threshold distance comprises:

determining, by the computing device, that the distance between the beginning point of the third stroke and the left edge of the second stroke is greater than 75% of the distance between the left edge of the second stroke and the right edge of the second stroke.

13. The method of claim 12, comprising:

designating, by the computing device, the third stroke as being associated with a same handwritten character as the second stroke.

14. The method of claim 7, comprising:

determining, by the computing device, that a first distance between (i) a beginning point of a third stroke of the sequence of strokes and (ii) the left edge of the second stroke satisfies a first threshold;

determining, by the computing device, that a second distance between (i) an end point of the third stroke and (ii) the right edge of the second stroke satisfies a second threshold; and

designating, by the computing device, the third stroke as being associated with a same handwritten character as the second stroke.

34. The method of claim 1,

wherein determining, by the computing device, the predetermined sub-area of the handwriting input area that is characterized as a character end point sub-area comprises determining, by the computing device, the predetermined sub-area of the handwriting input area to be used for evaluating each stroke in the sequence of strokes, and

wherein the method further comprises determining, by the computing device and for each stroke in the sequence of strokes, whether the end point of the stroke occurs in the predetermined sub-area of the handwriting input area to be used for evaluating each stroke in the sequence of strokes.

35. The method of claim 1, wherein the candidate end point of the first handwritten character defines a candidate boundary between the first stroke and the second stroke that separates (i) a first group of strokes of the sequence of strokes that includes the first stroke and that corresponds to the first handwritten character, and (ii) a second group of strokes of the sequence of strokes that includes the second stroke and that corresponds to a second handwritten character.

36. The method of claim 1, further comprising:

determining, by the computing device, a predetermined sub-area of the handwriting input area that is characterized as a character start point sub-area, the character start point sub-area being different from the character end point sub-area; and

wherein determining, by the computing device, that the beginning point of the second stroke of the sequence of strokes that immediately follows the first stroke occurs in the second sub-area of the handwriting input area that is not characterized as a character end point sub-area comprises;

determining, by the computing device, that the beginning point of the second stroke of the sequence of strokes occurs in the predetermined sub-area of the handwriting input area that is characterized as a character start point sub-area.

37. The method of claim 36, further comprising:

determining, by the computing device, a script associated with a particular language;

wherein determining, by the computing device, the predetermined sub-area of the handwriting input area that is characterized as a character start point sub-area comprises;

selecting, by the computing device and from among multiple predetermined sub-areas of the handwriting input area that are characterized as character start point sub-areas and each correspond to a respective language, a particular sub-area that corresponds to the particular language with which the determined script is associated; and

wherein determining, by the computing device, the predetermined sub-area of the handwriting input area that is characterized as a character end point sub-area comprises;

selecting, by the computing device and from among multiple predetermined sub-areas of the handwriting input area that are characterized as character end point sub-areas and each correspond to a respective language, a particular sub-area that corresponds to the particular language with which the determined script is associated.

38. The method of claim 36, wherein the predetermined sub-area of the handwriting input area that is characterized as a character end point sub-area and the predetermined sub-area of the handwriting input area that is characterized as a character start point sub-area are partially overlapping sub-areas of the handwriting input area.

39. The method of claim 36, wherein the handwriting input area is divided into multiple regions, and each of the multiple regions is included in (i) the predetermined sub-area of the handwriting input area that is characterized as a character end point sub-area or (ii) the predetermined sub-area of the handwriting input area that is characterized as a character start point sub-area.

40. The method of claim 1, further comprising:

providing, by the computing device, data indicating the sequence of strokes and data indicating the designated candidate end point of the first handwritten character to a server system that provides a handwriting recognition service; and

wherein obtaining, by the computing device, the recognized character comprises receiving, by the computing device and from the server system, data indicating a recognized character for the first handwritten character.

41. The method of claim 1, wherein determining, by the computing device, the predetermined sub-area of the handwriting input area that is characterized as a character end point sub-area comprises determining, by the computing device, a predetermined set of multiple sections of the handwriting input area that form the predetermined sub-area of the handwriting input area that is characterized as a character end point sub-area.

42. The method of claim 1, wherein the handwriting input area has an associated grid, and wherein the predetermined sub-area of the handwriting input area that is characterized as a character end point sub-area corresponds to multiple contiguous sections of the grid.

43. The method of claim 1, wherein the predetermined sub-area of the handwriting input area that is characterized as a character end point sub-area includes at least half of the handwriting input area.

44. The method of claim 1, wherein the predetermined sub-area of the handwriting input area that is characterized as a character end point sub-area includes (i) a region that extends along a vertical edge of the handwriting input area and (ii) a region that extends along a horizontal edge of the handwriting input area.

15. A system comprising:

one or more computers and one or more storage devices storing instructions that, when executed by the one or more computers, to cause the one or more computers to perform operations comprising;

receiving, by a computing device, a sequence of strokes that represent a handwritten input that trace shapes of one or more handwritten characters along a handwriting input area of the computing device;

determining, by the computing device, a predetermined sub-area of the handwriting input area that is characterized as a character end point sub-area;

determining, by the computing device, that (i) an end point of a first stroke of the sequence of strokes occurs in the predetermined sub-area of the handwriting input area that is characterized as a character end point sub-area, and (ii) a beginning point of a second stroke of the sequence of strokes that immediately follows the first stroke occurs in a second sub-area of the handwriting input area that is not characterized as a character end point sub-area;

based on determining that (i) the end point of the first stroke of the sequence of strokes occurs in the predetermined sub-area of the handwriting input area that is characterized as a character end point sub-area and (ii) the beginning point of the second stroke of the sequence of strokes that immediately follows the first stroke occurs in the second sub-area of the handwriting input area that is not characterized as a character end point sub-area, designating, by the computing device, the end point of the first stroke as a candidate end point of a first handwritten character traced by the sequence of strokes; and

obtaining, by the computing device, a recognized character corresponding to the first handwritten character based at least in part on the designated candidate end point of the first handwritten character.

16. The system of claim 15, wherein the operations further comprise:

based on determining that (i) the end point of the first stroke of the sequence of strokes occurs in the predetermined sub-area of the handwriting input area that is characterized as a character end point sub-area and (ii) the beginning point of the second stroke of the sequence of strokes that immediately follows the first stroke occurs in the second sub-area of the handwriting input area that is not characterized as a character end point sub-area, designating, by the computing device, the second stroke as being associated with a second handwritten character.

17. The system of claim 15, wherein a location of the predetermined sub-area of the handwriting input area that is characterized as a character end point sub-area is based on a script associated with the handwritten input.

18. The system of claim 15, wherein the operations further comprise:

determining, by the computing device, a distance between a left edge of the second stroke and a right edge of the second stroke.

19. The system of claim 18, wherein the operations further comprise:

determining, by the computing device, that a beginning point of a third stroke of the sequence of strokes that immediately follows the second stroke occurs between the left edge of the second stroke and the right edge of the second stroke.

20. The system of claim 19, wherein the operations further comprise:

determining, by the computing device, that a distance between the beginning point of the third stroke and the left edge of the second stroke satisfies a threshold distance.

21. The system of claim 20, wherein determining, by the computing device, that the distance between the beginning point of the third stroke and the left edge of the second stroke satisfies the threshold distance comprises:

determining, by the computing device, that the distance between the beginning point of the third stroke and the left edge of the second stroke is less than 25% of the distance between the left edge of the second stroke and the right edge of the second stroke.

22. The system of claim 21, wherein the operations further comprise:

designating, by computing device, the third stroke as being associated with a third handwritten character that is not associated with the first stroke or the second stroke.

23. The system of claim 20, wherein determining, by the computing device, that the distance between the beginning point of the third stroke and the left edge of the second stroke satisfies the threshold distance comprises:

determining, by the computing device, that the distance between the beginning point of the third stroke and the left edge of the second stroke is greater than 75% of the distance between the left edge of the second stroke and the right edge of the second stroke.

24. The system of claim 23, wherein the operations further comprise:

designating, by the computing device, the third stroke as being associated with a same handwritten character as the second stroke.

25. The system of claim 18, wherein the operations further comprise:

determining, by the computing device, that a first distance between (i) a beginning point of a third stroke of the sequence of strokes and (ii) the left edge of the second stroke satisfies a first threshold;

determining, by the computing device, that a second distance between (i) an end point of the third stroke and (ii) the right edge of the second stroke satisfies a second threshold; and

designating, by the computing device, the third stroke as being associated with a same handwritten character as the second stroke.

26. A non-transitory computer-readable medium storing software comprising instructions executable by one or more computers which, upon such execution, cause the one or more computers to perform operations comprising:

receiving, by a computing device, a sequence of strokes that represent a handwritten input that was input through traces shapes of one or more handwritten characters along a handwriting input area of the computing device;

determining, by the computing device, a predetermined sub-area of the handwriting input area that is characterized as a character end point sub-area;

determining, by the computing device, that (i) an end point of a first stroke of the sequence of strokes occurs in the predetermined sub-area of the handwriting input area that is characterized as a character end point sub-area, and (ii) a beginning point of a second stroke of the sequence of strokes that immediately follows the first stroke occurs in a second sub-area of the handwriting input area that is not characterized as a character end point sub-area;

based on determining that (i) the end point of the first stroke of the sequence of strokes occurs in the predetermined sub-area of the handwriting input area that is characterized as a character end point sub-area and (ii) the beginning point of the second stroke of the sequence of strokes that immediately follows the first stroke occurs in the second sub-area of the handwriting input area that is not characterized as a character end point sub-area, designating, by the computing device, the end point of the first stroke as a candidate end point of a first handwritten character traced by the sequence of strokes; and

obtaining, by the computing device, a recognized character corresponding to the first handwritten character based at least in part on the designated candidate end point of the first handwritten character.

27. The medium of claim 26, wherein the operations further comprise:

based on determining that (i) the end point of the first stroke of the sequence of strokes occurs in the predetermined sub-area of the handwriting input area that is characterized as a character end point sub-area and (ii) the beginning point of the second stroke of the sequence of strokes that immediately follows the first stroke occurs in the second sub-area of the handwriting input area that is not characterized as a character end point sub-area, designating, by the computing device, the second stroke as being associated with a second handwritten character.

28. The medium of claim 26, wherein a location of the predetermined sub-area of the handwriting input area that is characterized as a character end point sub-area is based on a script associated with the handwritten input.

29. The medium of claim 26, wherein the predetermined sub-area of the handwriting input area that is characterized as a character end point sub-area is located in a bottom right portion of the handwriting input area.

30. The medium of claim 26, wherein the operations further comprise:

determining, by the computing device, that a beginning point of a third stroke of the sequence of strokes that immediately follows the second stroke occurs in the predetermined sub-area of the handwriting input area that is characterized as a character end point sub-area.

31. The medium of claim 26, wherein the operations further comprise:

determining, by the computing device, a distance between a left edge of the second stroke and a right edge of the second stroke.

32. The medium of claim 31, wherein the operations further comprise:

determining, by the computing device, that a beginning point of a third stroke of the sequence of strokes that immediately follows the second stroke occurs between the left edge of the second stroke and the right edge of the second stroke.

33. The medium of claim 32, wherein the operations further comprise:

determining, by the computing device, that a distance between the beginning point of the third stroke and the left edge of the second stroke satisfies a threshold distance.