Spatial recognition and grouping of text and graphics

• US 20060045337A1
• Filed: 08/26/2004
• Published: 03/02/2006
• Est. Priority Date: 08/26/2004
• Status: Active Grant

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Corporation
• Inventors: Chellapilla, Kumar H., Shilman, Michael, Viola, Paul A.
• Granted Patent: US 7,729,538 B2
• Time in Patent Office: Days
• US Class Current: 382/181
• CPC Class Codes: G06V 30/10 Character recognition
• CPC Class Codes: G06V 30/153 using recognition of characters or words
• CPC Class Codes: G06V 30/18029 filtering with Haar-like subimages, e.g. computation thereof with the integral image technique
• CPC Class Codes: G06V 30/274 Syntactic or semantic context, e.g. balancing
• CPC Class Codes: G06V 30/32 Digital ink

Abstract

The present invention leverages spatial relationships to provide a systematic means to recognize text and/or graphics. This allows augmentation of a sketched shape with its symbolic meaning, enabling numerous features including smart editing, beautification, and interactive simulation of visual languages. The spatial recognition method obtains a search-based optimization over a large space of possible groupings from simultaneously grouped and recognized sketched shapes. The optimization utilizes a classifier that assigns a class label to a collection of strokes. The overall grouping optimization assumes the properties of the classifier so that if the classifier is scale and rotation invariant the optimization will be as well. Instances of the present invention employ a variant of AdaBoost to facilitate in recognizing/classifying symbols. Instances of the present invention employ dynamic programming and/or A-star search to perform optimization. The present invention applies to both hand-sketched shapes and printed handwritten text, and even heterogeneous mixtures of the two.

Claims

1. A system that facilitates recognition, comprising:

a component that receives at least one input comprising at least one entity; and

a recognition component that utilizes a simultaneous segmentation and recognition process to recognize the entity in the input.

2. The system of claim 1, the input comprising a geometric structure existing in a P-dimensional space.

3. The system of claim 2, the P-dimensional space comprising at least one selected from the group consisting of a 1-dimensional space, a 2-dimensional space, and a 3-dimensional space.

4. The system of claim 1, the recognition component employs dynamic programming to facilitate the simultaneous segmentation and recognition process.

5. The system of claim 1, the recognition component utilizes context information to facilitate the simultaneous segmentation and recognition process.

6. The system of claim 1, the recognition component utilizes stroke feature information to facilitate the simultaneous segmentation and recognition process.

7. The system of claim 1, the entity comprising at least one selected from the group consisting of a textual entity and a graphical entity.

8. The system of claim 1, the entity comprising at least one selected from the group consisting of a set of strokes and a set of pixels.

9. The system of claim 1, the input comprising at least one selected from the group consisting of a non-linear sequence in time and a non-linear sequence in space.

10. The system of claim 1, the recognition component employs spatial cues obtained from the input to recognize the entity.

11. The system of claim 1, further comprising:

a training component that automatically trains the recognition component to identify an entity from an input.

12. The system of claim 11, the training component employs machine learning to solve segmentation parameters.

13. The system of claim 1, the entity comprising characters related to an equation.

14. The system of claim 13, the recognition component determines sub-expressions of the equation based on the characters that it recognizes.

15. The system of claim 14, the recognition component derives the equation based on the determined sub-expressions.

16. The system of claim 1, the recognition component employs a classifier to facilitate in the simultaneous segmentation and recognition process.

17. The system of claim 16, the classifier comprising a trainable classifier that learns a function that penalizes incorrect segmentations.

18. The system of claim 1 further comprising:

an optimization component that facilitates the segmentation and recognition process via an optimization that resolves an optimum segmentation and recognition.

19. The system of claim 18, the optimization comprising a cost-directed search method.

20. The system of claim 19, the cost-directed search method comprising at least one selected from the group consisting of an A-star search method, a best-first search method, and a branch-and-bound search method.

21. The system of claim 18, the optimization comprising an optimization that employs a dynamic programming process.

22. The system of claim 1, the recognition component utilizes ambiguities in segmentation to facilitate recognition.

23. The system of claim 1, the recognition component utilizes ambiguities in recognition to facilitate segmentation.

46. A computer readable medium having stored thereon computer executable components of the system of claim 1.

48. A device employing the system of claim 1 comprising at least one selected from the group consisting of a computer, a server, and a handheld electronic device.

24. A method for facilitating recognition, comprising:

receiving at least one P-dimensional input; and

employing a simultaneous segmentation and recognition process to recognize an entity in the input.

25. The method of claim 24, the P-dimensional input comprising at least one selected from the group consisting of a 1-dimensional input, a 2-dimensional input, and a 3-dimensional input.

26. The method of claim 24, the input comprising at least one selected from the group consisting of a textual input and a graphical input.

27. The method of claim 24, the input comprising at least one selected from the group consisting of a set of optically recognizable marks and a set of pixels.

28. The method of claim 24, the input comprising at least one selected from the group consisting of a non-linear sequence in time and a non-linear sequence in space.

29. The method of claim 24, the simultaneous segmentation and recognition process comprising a scale and rotation invariant spatial recognition process.

30. The method of claim 24, the simultaneous segmentation and recognition process comprising:

linking strokes of the input in a graph to form connected subgraphs;

applying a search method over the connected subgraphs of the proximity graph to determine an optimal decomposition; and

recognizing the optimal decomposition via employment of a classifier.

31. The method of claim 30, the classifier comprising a classifier based on, at least in part, rendered images of strokes, stroke features, and context.

32. The method of claim 30, the linking of strokes to form subgraphs comprising:

constructing a neighborhood graph G=(V, E);

where vertices, V, correspond to strokes and edges, E, correspond to neighbor relationships between strokes;

linking vertices based on geometric relationships; and

enumerating connected subsets, V_i, where |V_i|≦

K;

where K is a threshold value that limits a size of a subgraph.

33. The method of claim 30 further comprising:

determining a context of a subgraph; and

employing the context for facilitating classification of the connected subgraphs.

34. The method of claim 30, the simultaneous segmentation and recognition process further comprising:

automatically learning the classifier and/or classification parameters from a training set of examples.

35. The method of claim 30, the search method comprising a cost-directed search method.

36. The method of claim 35, the cost-directed search method comprising at least one selected from the group consisting of an A-star search method, a best-first search method, and a branch-and-bound search method.

37. The method of claim 30, the search method employs an optimization method comprising:

utilizing a cost optimization function to facilitate in segmentation and recognition to determine an optimum grouping and labeling according to Equation (1);

C({V_i}))=Φ

(R(V_i), R(V₂), . . . , R(V_n));

 

 

(Eq.

     1)

where V_i is a subset of vertices which form a decomposition of an input, R is a best recognition result for the set of vertices, the function Φ

is a combination cost, and C represents an overall cost of a particular grouping {V_i}.

38. The method of claim 30, the stroke features comprising at least one selected from the group consisting of a curvature of a stroke, orientation of a stroke, and at least one end point of a stroke.

39. The method of claim 30 further comprising:

limiting the connected subgraphs to a predetermined fixed size.

40. The method of claim 30, the recognizing the optimal subgraph further comprising:

employing a machine learning-based classifier to distinguish valid and invalid subgraphs.

41. The method of claim 40, the machine learning-based classifier comprising at least one selected from the group consisting of AdaBoost, Neural Networks, Support Vector Machines, and Bayesian Classification.

42. The method of claim 40 further comprising:

utilizing limited-depth decision trees to facilitate the AdaBoost-based recognition method.

43. The method of claim 30, the recognizing the optimal decomposition further comprising:

providing validity of a decomposition and a label for each valid subgraph.

47. A device employing the method of claim 24 comprising at least one selected from the group consisting of a computer, a server, and a handheld electronic device.

44. A system that facilitates recognition, comprising:

means for receiving at least one input comprising, at least in part, an P-dimensional space of at least one entity; and

means for utilizing a simultaneous segmentation and recognition process to recognize the entity from the input.

45. A data packet, transmitted between two or more computer components, that facilitates recognition, the data packet comprising, at least in part, information relating to a spatial recognition system that utilizes, at least in part, a simultaneous segmentation and recognition process to recognize an entity.