SYMBOL GRAPH GENERATION IN HANDWRITTEN MATHEMATICAL EXPRESSION RECOGNITION

• US 20080240570A1
• Filed: 03/29/2007
• Published: 10/02/2008
• Est. Priority Date: 03/29/2007
• Status: Active Grant

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Corporation
• Inventors: Zhang, Dongmei, Shi, Yu, Soong, Frank Kao-Ping, Zhou, Jian-lai
• Granted Patent: US 7,885,456 B2
• Time in Patent Office: Days
• US Class Current: 382/189
• CPC Class Codes: G06F 18/29 Graphical models, e.g. Bayesian networks
• CPC Class Codes: G06V 30/10 Character recognition

Abstract

A forward pass through a sequence of strokes representing a handwritten equation is performed from the first stroke to the last stroke in the sequence. At each stroke, a path score is determined for a plurality of symbol-relation pairs that each represents a symbol and its spatial relation to a predecessor symbol. A symbol graph having nodes and links is constructed by backtracking through the strokes from the last stroke to the first stroke and assigning scores to the links based on the path scores for the symbol-relation pairs. The symbol graph is used to recognize a mathematical expression based in part on the scores for the links and the mathematical expression is stored.

Claims

1. A method comprising:

receiving strokes representing a handwritten equation;

for each stroke, forming path scores for a combination of a symbol-relation pair that represents a symbol in a particular relation to a predecessor symbol and a predecessor symbol-relation pair that represents the predecessor symbol in a particular relation to a further predecessor symbol;

using the path scores to construct a symbol graph comprising nodes connected by path segments, each path segment having a path segment score that is based in part on a path score and representing at least a symbol-relation pair;

using the symbol graph to identify a recognized mathematical expression that represent the handwritten equation; and

storing the recognized mathematical expression.

2. The method of claim 1 wherein forming path scores comprises forming path scores based in part on a duration model probability that provides the probability of a number of strokes being assigned to a symbol given the symbol.

3. The method of claim 2 wherein forming the path scores further comprises forming the path scores based in part on a spatial relation model probability that provides the probability of a spatial relation between first and second symbols given a spatial relation between the second symbol and a third symbol.

4. The method of claim 1 wherein forming path scores comprises forming a plurality of path scores for the combination of the symbol-relation pair and the predecessor symbol-relation pair, each path score being associated with a different number of strokes being assigned to the symbol in the symbol-relation pair and selecting a best path score from the plurality of path scores.

5. The method of claim 1 wherein forming an arc score based in part on a path score comprises forming a path segment score based on a path score that ends at the symbol-relation pair and based on a path score that ends at the predecessor symbol-relation pair.

6. The method of claim 1 wherein each path segment further represents a stroke index representing the last stroke assigned to the symbol in the symbol-relation pair.

7. The method of claim 1 wherein using path scores to construct a symbol graph comprises adding nodes and path segments to the graph while backtracking through path scores from the last stroke in the received strokes to the first stroke in the received strokes.

8. A computer-readable medium having computer-executable instructions for performing steps comprising:

accessing data representing a sequence of strokes in a handwritten equation;

performing a forward pass through the sequence of strokes from the first stroke in the sequence to the last stroke in the sequence, the forward pass comprising at each stroke, determining a path score for a plurality of symbol-relation pairs that each represents a symbol and its spatial relation to a predecessor symbol;

constructing a symbol graph comprising nodes and links by backtracking through the strokes from the last stroke to the first stroke and assigning scores to the links based on the path scores for the symbol-relation pairs;

using the symbol graph to recognize a mathematical expression based in part on the scores for the links; and

storing the mathematical expression.

9. The computer-readable medium of claim 8 wherein assigning scores to the links comprises determining a score for the link based on a path score for a symbol-relation pair and a separate path score for a predecessor symbol-relation pair.

10. The computer-readable medium of claim 8 further comprising providing the mathematical expression to a user, receiving a modification to the mathematical expression, using the modification to alter the symbol graph to form an altered symbol graph, using the altered symbol graph to recognize a new mathematical expression, and storing the new mathematical expression.

11. The computer-readable medium of claim 10 wherein the new mathematical expression comprises at least one symbol-relation pair that was not found in the mathematical expression and was not found in the modification to the mathematical expression.

12. The computer-readable medium of claim 8 wherein determining a path score comprises determining a path score that is associated with a symbol-relation pair, a predecessor symbol-relation pair and a stroke.

13. The computer-readable medium of claim 12 wherein determining a path score comprises determining a plurality of path scores for a symbol-relation pair, a predecessor symbol-relation pair and a stroke, each path score being associated with a different number of strokes being assigned to the symbol in the symbol-relation pair and selecting one of the plurality of path scores to thereby select a number of strokes assigned to the symbol.

14. The computer-readable medium of claim 13 wherein backtracking comprises placing a node in the graph for a predecessor symbol-relation pair based on a path score associated with a symbol-relation pair, the predecessor symbol-relation pair and a stroke, the node being placed at a stroke based on the number of strokes assigned to the symbol in the symbol-relation pair when computing the path score.

15. A method comprising:

accessing data representing strokes of a handwritten equation;

for each stroke, determining a set of scores for each of a plurality of combinations of symbol-relation pairs, previous symbol-relation pairs, and stroke where a symbol-relation pair comprises a symbol and a spatial relation between the symbol and a previous symbol, each score in a set of scores being associated with a different number of strokes being assigned to the symbol in the symbol-relation pair;

for each combination of stroke, symbol-relation pair, and previous symbol-relation pair, selecting one of the set of scores for that combination and thereby identifying a grouping of strokes for the symbol in the symbol-relation pair; and

storing the grouping and the score.

16. The method of claim 15 wherein determining a score comprises determining a score based in part on a duration model probability that provides the probability of a number of strokes being assigned to a symbol given the symbol.

17. The method of claim 15 wherein determining a score comprises determining a score based in part on a spatial structure probability that provides the probability of a spatial relation between a first symbol and a second symbol given a spatial relation between the second symbol and a third symbol.

18. The method of claim 15 further comprising using the grouping and the score to construct a symbol graph.

19. The method of claim 18 wherein using the grouping and the score to construct a symbol graph comprises forming a node for the symbol-relation pair and a node for the previous symbol-relation pair, forming a link between the nodes, and determining a score for the link based in part on the selected path score.

20. The method of claim 19 further comprising using the graph to identify a recognized mathematical expression and storing the recognized mathematical expression.