Segmentation of an Input by Cut Point Classification

• US 20150235097A1
• Filed: 02/20/2014
• Published: 08/20/2015
• Est. Priority Date: 02/20/2014
• Status: Active Grant

• Current Assignee: Google LLC (Alphabet Inc.)
• Original Assignee: Google Inc. (Alphabet Inc.)
• Inventors: Wang, Li-Lun, Deselaers, Thomas, Rowley, Henry Allan
• Granted Patent: US 9,286,527 B2
• Time in Patent Office: Days
• US Class Current: 1/1
• CPC Class Codes: G06F 18/214 Generating training patterns; Bootstrap methods, e.g. bagging or boosting
• CPC Class Codes: G06N 20/00 Machine learning
• CPC Class Codes: G06V 10/267 by performing operations on regions, e.g. growing, shrinking or watersheds
• 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/1423 the instrument generating sequences of position coordinates corresponding to handwriting preprocessing or recognising digital ink G06V30/32
• CPC Class Codes: G06V 30/2268 using stroke segmentation
• CPC Class Codes: G06V 30/32 Digital ink

Abstract

Techniques are provided for segmenting an input by cut point classification and training a cut classifier. A method may include receiving, by a computerized text recognition system, an input in a script. A heuristic may be applied to the input to insert multiple cut points. For each of the cut points, a probability may be generated and the probability may indicate a likelihood that the cut point is correct. Multiple segments of the input may be selected, and the segments may be defined by cut points having a probability over a threshold. Next, the segments of the input may be provided to a character recognizer. Additionally, a method may include training a cut classifier using a machine learning technique, based on multiple text training examples, to determine the correctness of a cut point in an input.

Claims

1. A computer-implemented method comprising:

receiving, by a computerized text recognition system, an input in a script;

applying a heuristic to the input to insert a plurality of cut points;

generating a probability for each of the plurality of cut points, wherein the probability indicates a likelihood that the cut point is correct;

selecting a plurality of segments of the input defined by cut points having a probability over a threshold; and

providing the plurality of segments of the input to a character recognizer.

2. The computer-implemented method of claim 1, wherein generating the probability for each of the plurality of cut points is based on at least one feature selected from the group consisting of:

a coordinate of an endpoint of a first segment adjacent to a second segment defined at least in part by the cut point, a type of cut point associated with the cut point, a curvature of the input at the cut point, an input speed associated with strokes in the input, and a region of the input in which the cut point is located.

3. The computer-implemented method of claim 1, wherein the probability is generated by a trained cut classifier.

4. The computer-implemented method of claim 3, wherein the trained cut classifier is trained using a machine learning technique.

5. The computer-implemented method of claim 4, wherein the machine learning technique is selected from the group consisting of:

neural network, k-nearest neighbor, support vector machine, logistic regression, adaboost, Gaussian mixture model, and linear discriminant analysis.

6. The computer-implemented method of claim 3, wherein the trained cut classifier is associated with at least one selected from the group consisting of:

the heuristic and the script.

7. The computer-implemented method of claim 1, wherein the heuristic is based on the script of the input.

8. The computer-implemented method of claim 1, wherein the number of cut points having a probability over the threshold is less than the number of cut points in the plurality of cut points.

9. The computer-implemented method of claim 1, wherein the input is an online handwritten input received from a user.

10. The computer-implemented method of claim 1, wherein the input is a scanned image of text selected from the group consisting of:

handwritten text, typewritten text, and printed text.

11. A computer-implemented method comprising:

receiving a plurality of text training examples, each text training example including;

a portion of text,

a plurality of cut points that separate the portion of text into a plurality of segments, and

for each of the plurality of cut points in the text training example, an indication of the correctness of the cut point; and

training a cut classifier using a machine learning technique, based on the plurality of text training examples, to determine the correctness of a cut point in an input.

12. The computer-implemented method of claim 11, wherein the plurality of cut points that separate the portion of text into a plurality of segments includes a set of known character segmentations.

13. The computer-implemented method of claim 11, wherein the machine learning technique uses at least one feature, to train the cut classifier for each of the plurality of cut points, selected from the group consisting of:

a coordinate of an endpoint of a first segment adjacent to a second segment defined at least in part by the cut point, a type of cut point associated with the cut point, a curvature of the input at the cut point, an input speed associated with strokes in the input, and a region of the input in which the cut point is located.

14. The computer-implemented method of claim 11, wherein the machine learning technique is selected from the group consisting of:

neural network, k-nearest neighbor, support vector machine, logistic regression, adaboost, Gaussian mixture model, and linear discriminant analysis.

15. The computer-implemented method of claim 11, further comprising generating a trained cut classifier model based on the plurality of text training examples.

16. The computer-implemented method of claim 15, further comprising receiving, at the cut classifier, a first input and applying the trained cut classifier model to the first input.

17. The computer-implemented method of claim 11, wherein the cut classifier is trained to classify the cut point in the input as one of:

a segmenting cut point or a non-segmenting cut point.

18. The computer-implemented method of claim 11, wherein the cut classifier is trained based on a script of the plurality of text training examples.

19. A system comprising:

a processor configured to;

receive, by a computerized text recognition system, an input in a script;

apply a heuristic to the input to insert a plurality of cut points;

generate a probability for each of the plurality of cut points, wherein the probability indicates a likelihood that the cut point is correct;

select a plurality of segments of the input defined by cut points having a probability over a threshold; and

provide the plurality of segments of the input to a character recognizer.

20. The system of claim 19, wherein generating the probability for each of the plurality of cut points is based on at least one feature selected from the group consisting of:

a coordinate of an endpoint of a first segment adjacent to a second segment defined at least in part by the cut point, a type of cut point associated with the cut point, a curvature of the input at the cut point, an input speed associated with strokes in the input, and a region of the input in which the cut point is located.

21. The system of claim 19, wherein the probability is generated by a trained cut classifier.

22. The system of claim 21, wherein the trained cut classifier is trained using a machine learning technique.

23. The system of claim 22, wherein the machine learning technique is selected from the group consisting of:

neural network, k-nearest neighbor, support vector machine, logistic regression, adaboost, Gaussian mixture model, and linear discriminant analysis.

24. The system of claim 21, wherein the trained cut classifier is associated with at least one selected from the group consisting of:

the heuristic and the script.

25. The system of claim 19, wherein the heuristic is based on the script of the input.

26. The system of claim 19, wherein the number of cut points having a probability over the threshold is less than the number of cut points in the plurality of cut points.

27. The system of claim 19, wherein the input is an online handwritten input received from a user.

28. The system of claim 19, wherein the input is a scanned image of text selected from the group consisting of:

handwritten text, typewritten text, and printed text.

29. A system comprising:

a processor configured to;

receive a plurality of text training examples, each text training example including;

a portion of text,

a plurality of cut points that separate the portion of text into a plurality of segments, and

for each of the plurality of cut points in the text training example, an indication of the correctness of the cut point; and

train a cut classifier using a machine learning technique, based on the plurality of text training examples, to determine the correctness of a cut point in an input.

30. The system of claim 29, wherein the plurality of cut points that separate the portion of text into a plurality of segments includes a set of known character segmentations.

31. The system of claim 29, wherein the machine learning technique uses at least one feature, to train the cut classifier for each of the plurality of cut points, selected from the group consisting of:

a coordinate of an endpoint of a first segment adjacent to a second segment defined at least in part by the cut point, a type of cut point associated with the cut point, a curvature of the input at the cut point, an input speed associated with strokes in the input, and a region of the input in which the cut point is located.

32. The system of claim 29, wherein the machine learning technique is selected from the group consisting of:

neural network, k-nearest neighbor, support vector machine, logistic regression, adaboost, Gaussian mixture model, and linear discriminant analysis.

33. The system of claim 29, wherein the processor is further configured to generate a trained cut classifier model based on the plurality of text training examples.

34. The system of claim 33, wherein the processor is further configured to receive, at the cut classifier, a first input and applying the trained cut classifier model to the first input.

35. The system of claim 29, wherein the cut classifier is trained to classify the cut point in the input as one of:

a segmenting cut point or a non-segmenting cut point.

36. The system of claim 29, wherein the cut classifier is trained based on a script of the plurality of text training examples.