Distinguishing text from non-text in digital ink

• US 20050286771A1
• Filed: 06/23/2004
• Published: 12/29/2005
• Est. Priority Date: 06/23/2004
• Status: Active Grant

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Corporation
• Inventors: Markus Svensen, Johan Fredrik, Hinton, Geoffrey, Bishop, Christopher M.
• Granted Patent: US 7,496,232 B2
• Time in Patent Office: Days
• US Class Current: 382/202
• CPC Class Codes: G06V 30/36 Matching; Classification
• CPC Class Codes: G06V 30/413 Classification of content, e.g. text, photographs or tables

Abstract

A discriminative machine learning system for labels text and non-text strokes in digital ink. The learning system considers stroke features and the context of the strokes, such as temporal information about one or more strokes, in a probabilistic framework. The learning system can also consider gap features within the probabilistic framework to label associated strokes.

Claims

1. A method of distinguishing between text strokes and non-text strokes in digital ink, the method comprising:

detecting a gap between a first stroke and a second stroke in the digital ink;

generating a classification model based on at least one gap feature of the gap, wherein the model defines a posterior probability of the second stroke being a test stroke or a non-text stroke; and

labeling the gap as a change gap or a non-change gap based on the posterior probability.

2. The method of claim 1 wherein the detecting operation comprises:

detecting a pen-up event for the first stroke and a pen-down event for the second stroke.

3. The method of claim 1 wherein the detecting operation comprises:

detecting a time of a pen-down event for the second stroke.

4. The method of claim 1 further comprising:

detecting the at least one gap feature of the gap as a logarithm of a difference of pen-down event locations of temporally proximal strokes in the digital ink.

5. The method of claim 1 further comprising:

detecting the at least one gap feature of the gap as a coordinate difference of pen-down event locations of temporally proximal strokes in the digital ink.

6. The method of claim 1 further comprising:

detecting the at least one gap feature of the gap as a coordinate difference of a pen-up event location of the first stroke and a pen-down event location of the second stroke.

7. The method of claim 1 wherein the generating operation comprises:

generating the classification model from a bipartite hidden Markov model based on the at least one gap feature.

8. The method of claim 1 wherein the generating operation comprises:

generating the classification model from a bipartite hidden Markov model based on the at least one gap feature and at least one stroke feature of the second stroke.

9. A computer program product encoding a computer program that executes a computer process for distinguishing between text strokes and non-text strokes in digital ink, the computer process comprising:

detecting a gap between a first stroke and a second stroke in the digital ink;

generating a classification model based on at least one gap feature of the gap, wherein the model defines a posterior probability of the second stroke being a test stroke or a non-text stroke; and

labeling the gap as a change gap or a non-change gap based on the posterior probability.

10. The computer program product of claim 9 wherein the detecting operation comprises:

detecting a pen-up event for the first stroke and a pen-down event for the second stroke.

11. The computer program product of claim 9 wherein the detecting operation comprises:

detecting a time of a pen-down event for the second stroke.

12. The computer program product of claim 9 wherein the computer process further comprises:

detecting the at least one gap feature of the gap as a logarithm of a difference of pen-down event locations of temporally proximal strokes in the digital ink.

13. The computer program product of claim 9 wherein the computer process further comprises:

detecting the at least one gap feature of the gap as a coordinate difference of pen-down event locations of temporally proximal strokes in the digital ink.

14. The computer program product of claim 9 wherein the computer process further comprises:

detecting the at least one gap feature of the gap as a coordinate difference of a pen-up event location of the first stroke and a pen-down event location of the second stroke.

15. The computer program product of claim 9 wherein the generating operation comprises:

generating the classification model from a bipartite hidden Markov model based on the at least one gap feature.

16. The computer program product of claim 9 wherein the generating operation comprises:

generating the classification model from a bipartite hidden Markov model based on the at least one gap feature and at least one stroke feature of the second stroke.

17. A method of distinguishing between text strokes and non-text strokes in digital ink, the method comprising:

detecting a sequence of at least two strokes in the digital ink;

generating a classification model based on at least one stroke feature of at least one of the strokes, wherein the model incorporates a transition probability between the at least two stokes; and

labeling the sequence as a sequence of text strokes or non-text strokes based on the transition probability.

18. The method of claim 17 further comprising:

detecting the at least one stroke feature of the second stroke as a stroke arc length of the second stroke in the digital ink.

19. The method of claim 17 further comprising:

detecting the at least one stroke feature of the second stroke as a total absolute curvature of the second stroke in the digital ink.

20. The method of claim 17 further comprising:

detecting the at least one stroke feature of the second stroke as a direction of the second stroke in the digital ink.

21. The method of claim 17 further comprising:

detecting the at least one stroke feature of the second stroke as a length-width ratio of a total least squares model fitted to the second stroke in the digital ink.

22. The method of claim 17 further comprising:

dividing the second stroke into fragments at points corresponding to local maxima in the curvature of the second stroke; and

detecting the at least one stroke feature of the second stroke as a total number of fragments of the second stroke in the digital ink.

23. The method of claim 17 further comprising:

dividing the second stroke into fragments at points corresponding to local maxima in the curvature of the second stroke; and

detecting the at least one stroke feature of the second stroke as an arc length of the largest fragment of the second stroke in the digital ink.

24. The method of claim 17 further comprising:

dividing the second stroke into fragments at points corresponding to local maxima in the curvature of the second stroke; and

detecting the at least one stroke feature of the second stroke as a total absolute curvature of the largest fragment of the second stroke in the digital ink.

25. The method of claim 17 further comprising:

dividing the second stroke into fragments at points corresponding to local maxima in the curvature of the second stroke; and

detecting the at least one stroke feature of the second stroke as a direction of the largest fragment of the second stroke in the digital ink.

26. The method of claim 17 further comprising:

dividing the second stroke into fragments at points corresponding to local maxima in the curvature of the second stroke; and

detecting the at least one stroke feature of the second stroke as a length of the long size of a rectangle bounding the largest fragment of the second stroke in the digital ink.

27. The method of claim 17 wherein the generating operation comprises:

generating the classification model from a unipartite hidden Markov model based on the at least one stroke feature.

28. The method of claim 17 wherein the generating operation comprises:

generating the classification model from a bipartite hidden Markov model based on the at least one gap feature and at least one stroke feature of the second stroke.

29. A computer program product encoding a computer program that executes a computer process for distinguishing between text strokes and non-text strokes in digital ink, the computer process comprising:

detecting a sequence of at least two strokes in the digital ink;

generating a classification model based on at least one stroke feature of at least one of the strokes, wherein the model incorporates a transition probability between the at least two strokes; and

labeling the sequence as a sequence of text strokes or non-text strokes based on the transition probability.

30. The computer program product of claim 29 wherein the computer process further comprises:

detecting the at least one stroke feature of the second stroke as a stroke arc length of the second stroke in the digital ink.

31. The computer program product of claim 29 wherein the computer process further comprises:

detecting the at least one stroke feature of the second stroke as a total absolute curvature of the second stroke in the digital ink.

32. The computer program product of claim 29 wherein the computer process further comprises:

detecting the at least one stroke feature of the second stroke as a direction of the second stroke in the digital ink.

33. The computer program product of claim 29 wherein the computer process further comprises:

detecting the at least one stroke feature of the second stroke as a length-width ratio of a total least squares model fitted to the second stroke in the digital ink.

34. The computer program product of claim 29 wherein the computer process further comprises:

dividing the second stroke into fragments at points corresponding to local maxima in the curvature of the second stroke; and

detecting the at least one stroke feature of the second stroke as a total number of fragments of the second stroke in the digital ink.

35. The computer program product of claim 29 wherein the computer process further comprises:

dividing the second stroke into fragments at points corresponding to local maxima in the curvature of the second stroke; and

detecting the at least one stroke feature of the second stroke as an arc length of the largest fragment of the second stroke in the digital ink.

36. The computer program product of claim 29 wherein the computer process further comprises:

dividing the second stroke into fragments at points corresponding to local maxima in the curvature of the second stroke; and

detecting the at least one stroke feature of the second stroke as a total absolute curvature of the largest fragment of the second stroke in the digital ink.

37. The computer program product of claim 29 wherein the computer process further comprises:

dividing the second stroke into fragments at points corresponding to local maxima in the curvature of the second stroke; and

detecting the at least one stroke feature of the second stroke as a direction of the largest fragment of the second stroke in the digital ink.

38. The computer program product of claim 29 wherein the computer process further comprises:

dividing the second stroke into fragments at points corresponding to local maxima in the curvature of the second stroke; and

detecting the at least one stroke feature of the second stroke as a length of the long size of a rectangle bounding the largest fragment of the second stroke in the digital ink.

39. The computer program product of claim 29 wherein the generating operation comprises:

generating the classification model from a unipartite hidden Markov model based on the at least one stroke feature.

40. The computer program product of claim 29 wherein the generating operation comprises:

generating the classification model from a bipartite hidden Markov model based on the at least one gap feature and at least one stroke feature of the second stroke.

41. A method of distinguishing between text strokes and non-text strokes in digital ink, the method comprising:

detecting a stroke in the digital ink;

generating a classification model based on at least one stroke feature of the stroke, wherein the model defines a posterior probability that the stroke is a text stroke; and

labeling the stroke as a text stroke or a non-text stroke based on the posterior probability.

42. The method of claim 41 further comprising:

detecting the at least one stroke feature of the stroke as a stroke arc length of the stroke in the digital ink.

43. The method of claim 41 further comprising:

detecting the at least one stroke feature of the stroke as a total absolute curvature of the stroke in the digital ink.

44. The method of claim 41 further comprising:

detecting the at least one stroke feature of the stroke as a direction of the stroke in the digital ink.

45. The method of claim 41 further comprising:

detecting the at least one stroke feature of the stroke as a length-width ratio of a total least squares model fitted to the stroke in the digital ink.

46. The method of claim 41 further comprising:

dividing the second stroke into fragments at points corresponding to local maxima in the curvature of the stroke; and

detecting the at least one stroke feature of the second stroke as a total number of fragments of the stroke in the digital ink.

47. The method of claim 41 further comprising:

dividing the stroke into fragments at points corresponding to local maxima in the curvature of the stroke; and

detecting the at least one stroke feature of the stroke as an arc length of the largest fragment of the stroke in the digital ink.

48. The method of claim 41 further comprising:

dividing the stroke into fragments at points corresponding to local maxima in the curvature of the stroke; and

detecting the at least one stroke feature of the stroke as a total absolute curvature of the largest fragment of the stroke in the digital ink.

49. The method of claim 41 further comprising:

dividing the stroke into fragments at points corresponding to local maxima in the curvature of the stroke; and

detecting the at least one stroke feature of the stroke as a direction of the largest fragment of the stroke in the digital ink.

50. The method of claim 41 further comprising:

dividing the stroke into fragments at points corresponding to local maxima in the curvature of the stroke; and

detecting the at least one stroke feature of the stroke as a length of the long size of a rectangle bounding the largest fragment of the stroke in the digital ink.

51. A computer program product encoding a computer program for distinguishing between text strokes and non-text strokes in digital ink, the computer process comprising:

detecting a stroke in the digital ink;

generating a classification model based on at least one stroke feature of the stroke, wherein the model defines a posterior probability that the stroke is a text stroke; and

labeling the stroke as a text stroke or a non-text stroke based on the posterior probability.

52. The computer program product of claim 51 wherein the computer process further comprises:

detecting the at least one stroke feature of the stroke as a stroke arc length of the stroke in the digital ink.

53. The computer program product of claim 51 wherein the computer process further comprises:

detecting the at least one stroke feature of the stroke as a total absolute curvature of the stroke in the digital ink.

54. The computer program product of claim 51 wherein the computer process further comprises:

detecting the at least one stroke feature of the stroke as a direction of the stroke in the digital ink.

55. The computer program product of claim 51 wherein the computer process further comprises:

detecting the at least one stroke feature of the stroke as a length-width ratio of a total least squares model fitted to the stroke in the digital ink.

56. The computer program product of claim 51 wherein the computer process further comprises:

dividing the stroke into fragments at points corresponding to local maxima in the curvature of the stroke; and

detecting the at least one stroke feature of the stroke as a total number of fragments of the stroke in the digital ink.

57. The computer program product of claim 51 wherein the computer process further comprises:

dividing the stroke into fragments at points corresponding to local maxima in the curvature of the stroke; and

detecting the at least one stroke feature of the stroke as an arc length of the largest fragment of the stroke in the digital ink.

58. The computer program product of claim 51 wherein the computer process further comprises:

dividing the stroke into fragments at points corresponding to local maxima in the curvature of the stroke; and

detecting the at least one stroke feature of the stroke as a total absolute curvature of the largest fragment of the stroke in the digital ink.

59. The computer program product of claim 51 wherein the computer process further comprises:

dividing the stroke into fragments at points corresponding to local maxima in the curvature of the stroke; and

detecting the at least one stroke feature of the stroke as a direction of the largest fragment of the stroke in the digital ink.

60. The computer program product of claim 51 wherein the computer process further comprises:

dividing the stroke into fragments at points corresponding to local maxima in the curvature of the second stroke; and

detecting the at least one stroke feature of the stroke as a length of the long size of a rectangle bounding the largest fragment of the stroke in the digital ink.

61. A system for distinguishing between text strokes and non-text strokes in digital ink, the system comprising:

a stroke feature extractor module that detects a stroke in the digital ink; and

a stroke classifier module that generates a classification model based on at least one stroke feature of the stroke, wherein the model defines a posterior probability that the stoke is a text stroke, and labels the stroke as a text stroke or a non-text stroke based on the posterior probability.

62. A system for distinguishing between text strokes and non-text strokes in digital ink, the system comprising:

a stroke feature extractor module that detects a sequence of at least two strokes in the digital ink; and

a stroke classifier module that generates a classification model based on at least one stroke feature of a least one of the strokes; and

a sequence model that incorporates a transition probability between the at least two strokes and labels the sequence of strokes as a sequence of text strokes or non-text strokes based on the transition probability and the classification model.

63. A system for distinguishing between text strokes and non-text strokes in digital ink, the system comprising:

a gap feature extractor module detecting a gap between a first stroke and a second stroke in the digital ink; and

a gap classifier module generating a classification model based on at least one gap feature of the gap; and

a sequence model that defines a posterior probability of the second stroke being a test stroke or a non-text stroke and labels the gap as a change gap or a non-change gap based on the posterior probability. 308238.01 MS 1-2023US