Top-Down Search with Bottom-Up Evidence for Recognizing Handwritten Mathematical Expressions

In handwritten mathematical expressions (ME), understanding the general structure of an ME is often easier than resolving local ambiguities. For instance, identifying a key operator in terms of its spatial relationship with its subordinates is relatively easier than resolving the ambiguities of single symbol identity and local spatial relationships. In addition, decisions related to key operators often occur close to the top (root) of the parse tree, while local decisions take place at the bottom of it. Based on these observations, we propose an incremental search framework in which a parse tree is expanded by tentatively selecting the key operators of an expression. The goodness of the selection is defined by the likelihood of key symbol, the goodness of the sub expressions, and their spatial relationships. In this framework, ambiguous local parts are processed after tentative decisions have been made at the global level. To handle explosiveness of key operator selection, an admissible heuristic function is defined based on the direct relationship of the key operator with the symbols at the bottom level. An experimental evaluation shows that our system is promising. Using it a robust interpretation can be made by utilizing global information and an interpretation can be reached quickly by the admissible heuristic function.