Ambiguity and Constraint in Mathematical Expression Recognition

AAAI 1998

TL;DR

This paper tackles the challenge of recognizing mathematical expressions, which are inherently more ambiguous than standard text due to their 2D layout and lack of clear linear ordering. The authors introduce a novel system that leverages a combination of a geometric "convex hull" constraint and an A-star search with a new cost-to-goal estimate to prune the search space and maintain character ambiguity until context can resolve it, leading to more robust recognition.

What Problem Does This Paper Address?

Recognizing mathematical expressions from images is significantly harder than reading plain text. Unlike prose, where characters have a strong left-to-right dependency, mathematical expressions involve symbols arranged in two dimensions (e.g., superscripts, subscripts, fractions). This spatial arrangement creates a high degree of ambiguity. For instance, a character might be equally close to a superscript or a base, making its role unclear without broader context. Existing methods often struggle with this ambiguity, either by making premature decisions about character identity or by facing computationally intractable search spaces. This paper aims to develop a more effective system that can handle this ambiguity by intelligently constraining the interpretation process.

Methods

The proposed system combines several key innovations:

  • Maintaining Ambiguity: Instead of recognizing characters in isolation, the system maintains multiple hypotheses for each character's identity until contextual information can resolve the ambiguity. This is crucial for handling "confusable" characters (like 'q' and '9') and situations where a character's identity is only clear from its surroundings.
  • Geometric Convex Hull Constraint: A novel pruning criterion is introduced: a subset of characters is considered invalid if its "convex hull" (the smallest convex polygon enclosing all characters in the subset) contains a character not part of that subset. This constraint helps eliminate invalid spatial arrangements and is consistent with typesetting rules.
  • A-Star Search with New Cost-to-Goal Estimate: The system uses A-star search to find the best interpretation. A new, more accurate underestimate of the cost to reach the final goal (a complete parse) is proposed, which significantly improves the efficiency of the search by reducing the number of states explored.
  • Syntactic Classes: To manage the complexity of character ambiguity, characters are grouped into broader "syntactic classes" (e.g., ascending letters, descending letters, small letters, large letters, binary operators). The system maintains hypotheses for these classes rather than for every individual character, reducing the search space while still allowing for context-dependent disambiguation.

Datasets

The paper does not explicitly mention specific datasets used for training or evaluation. However, it states that the typeset examples used in the paper were "generated on-line and are essentially distortion-free." They also mention testing with expressions of varying complexity from 3 to 20 terminals. Preliminary work with handwritten expressions is illustrated, suggesting that handwritten data is a target for future work.

Key Insights and Ideas

  • Ambiguity is Key: The core insight is that mathematical expression recognition is fundamentally about managing and resolving ambiguity, both in character identity and spatial relationships. Prematurely resolving ambiguity can lead to incorrect interpretations.
  • Geometry as a Powerful Constraint: The convex hull constraint is a clever way to leverage geometric properties to prune invalid interpretations without relying solely on probabilistic models. It's a simple yet effective rule that aligns with how mathematical expressions are visually structured.
  • A-Star's Efficiency Boost: The A-star search, combined with a better cost-to-goal estimate, is crucial for making the search tractable. Without such heuristics, the combinatorial explosion of possible interpretations would render the system impractical.
  • Syntactic Classes Simplify Ambiguity Management: Grouping characters into syntactic classes is a pragmatic approach to balance the need for ambiguity maintenance with computational feasibility.

Key Results

The paper presents preliminary results demonstrating the effectiveness of their approach.

  • Significant Speedup: By using both the convex hull constraint and the A-star search heuristic, parse times were reduced from "on the order of minutes" to "seconds" for expressions of varying complexity.
  • Improved Performance: Graphs show that using the convex hull criterion alone significantly prunes the search space, and adding the A-star constraint further improves performance, leading to "even greater improvement when both are used."
  • Handling "Illegal" Inputs: The system demonstrated flexibility by producing reasonable interpretations for "illegal" inputs (expressions not conforming to the grammar), such as interpreting "0°°" as "600."
  • Anecdotal Successes: Several examples of successfully parsed expressions are shown, with parsing times for a 266MHz Pentium Pro ranging from 0.2 to 25 seconds (excluding character hypothesis generation).

Limitations and Future Work

  • Typeset vs. Handwritten: The current system is primarily designed for typeset expressions and makes assumptions about distinct, non-overlapping characters. It does not handle scanner distortion.
  • Handwritten Input: A major limitation is its current inability to robustly handle handwritten input, which introduces more variation and ambiguity. The paper acknowledges that improving the character recognizer and learning geometry models are key for future handwritten expression recognition.
  • Artificial Cases: The authors note that it's possible to construct artificial arrangements of symbols for which the convex hull criterion yields no pruning.
  • Future Directions: The authors plan to improve performance for handwritten input by enhancing the character recognizer and geometry models. They also suggest exploring other forms of contextual information.

Summary updated

BibTeX
@inproceedings{1998ambiguity,
  title = {{Ambiguity and Constraint in Mathematical Expression Recognition}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {1998},
}
Figure