Analyzing scripts and determining characters in expression recognition

• US 20060062468A1
• Filed: 06/20/2005
• Published: 03/23/2006
• Est. Priority Date: 09/22/2004
• Status: Active Grant

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Corporation
• Inventors: Wang, Xianfang, Zhang, Dongmei, Hou, Xiaohui, Zou, Yu, Zhou, Jian-Lai, Huang, Lei, Wang, Jian, Xu, Mingqing, Lin, Zhouchen
• Granted Patent: US 7,561,739 B2
• Time in Patent Office: Days
• US Class Current: 382/186
• CPC Class Codes: G06V 30/1423 the instrument generating sequences of position coordinates corresponding to handwriting preprocessing or recognising digital ink G06V30/32

Abstract

A mechanism for recognizing and inputting handwritten mathematical expressions into a computer by providing part of a multi-path framework is described. The part of the multi-path framework includes a subscript/superscript analysis and character determination component that is designed to identify subscript and superscript elements. A method for analyzing a handwritten mathematical expression includes receiving a symbols corresponding to handwritten mathematical expression input strokes, identifying subscript and/or superscript structures, and determining a character for each symbol of the set. A graph of vertexes and edges may be created based upon the set of symbols and the graph may be searched to determine optimized candidates.

Claims

1. A system for handwritten mathematical expression recognition, the system comprising a subscript/superscript analysis and character determination component configured to identify subscript/superscript structures and to determine a character which comes from a character candidates list for each symbol corresponding to handwritten mathematical expression input strokes.

2. The system of claim 1, wherein the subscript/superscript analysis and character determination component is further configured to sort the symbols to create a graph of vertexes and edges, and to search the graph to determine a predefined number of optimized candidates.

3. The system of claim 2, wherein a vertex represents one of the symbols.

4. The system of claim 2, wherein an edge represents characters of two linked symbols, a relational type between the characters of the two linked symbols, and a score.

5. The system of claim 4, wherein the score is determined based upon a spatial score representative of a spatial relationship between two symbols, a context probability score representative of a short syntax grammar, and confidences of each character of the two symbols.

6. The system of claim 2, wherein the subscript/superscript analysis and character determination component is further configured to determine whether each edge may be pruned based on the score of the edge.

7. The system of claim 2, wherein the subscript/superscript analysis and character determination component is further configured to verify the optimized candidates according to syntax analysis of valid mathematical expressions.

8. The system of claim 7, wherein the subscript/superscript analysis and character determination component is further configured to store information of verified optimized candidates in a parse tree.

9. The system of claim 8, wherein the subscript/superscript analysis and character determination component is further configured to pass the parse tree to a graphical user interface component configured to display the verified optimized candidates.

10. A method for analyzing a handwritten mathematical expression, the method comprising steps of:

receiving a set of symbols corresponding to handwritten mathematical expression input strokes;

identifying subscript/superscript structures; and

determining a character for each symbol of the set of symbols.

11. The method of claim 10, further comprising steps of:

sorting the set of symbols;

creating a graph of vertexes and edges; and

searching the graph to determine a predefined number of optimized candidates.

12. The method of claim 11, wherein a vertex represents the one of the symbols of the set of symbols.

13. The method of claim 11, wherein an edge represents the characters of two linked symbols, a relational type between the characters of the two linked symbols, and a score.

14. The method of claim 13, wherein the score is determined based upon a spatial score representative of a spatial relationship between the two symbols, a context probability score representative of a short syntax grammar, and confidences of each character of the two symbols.

15. The method of claim 11, further comprising a step of determining whether each edge may be pruned based on the score of the edge.

16. The method of claim 11, further comprising a step of verifying the optimized candidates according to syntax analysis of valid mathematical expressions.

17. The method of claim 16, further comprising a step of storing information of verified optimized candidates in a parse tree.

18. The method of claim 17, further comprising a step of passing the parse tree to a graphical user interface component configured to display the verified optimized candidates.

19. A software architecture stored on one or more computer readable media for processing data representative of a handwritten mathematical expression, comprising:

at least one component configured to identify subscript/superscript structures within a handwritten mathematical expression; and

at least one application program interface to access the component.

20. The software architecture of claim 19, wherein the at least one component is further configured to sort symbols corresponding to input strokes, to create a graph of vertexes and edges, and to search the graph to determine a predefined number of optimized candidates.