Visual Design and Engineering Laboratory

Carnegie Mellon University

An Efficient Graph-Based Symbol Recognizer


[Paper PDF]    

[Publisher Version]


We describe a trainable symbol recognizer for pen-based user interfaces. Symbols are represented internally as attributed relational graphs that describe both the geometry and topology of the symbols. Symbol recognition reduces to the task of finding the definition symbol whose attributed relational graph best matches that of the unknown symbol. One challenge addressed in the current work is how to perform this graph matching in an efficient fashion so as to achieve interactive performance. We present four approximate graph matching techniques:

Stochastic Matching, which is based on stochastic search;
Error-driven Matching, which uses local matching errors to drive the solution to an optimal match;
Greedy Matching, which uses greedy search; and
Sort Matching, which relies on geometric information to accelerate the matching.

Finally, we present promising results of initial user studies, and discuss the tradeoffs between the various matching techniques.


WeeSan Lee, Levent Burak Kara, Thomas F. Stahovich. (2006). An Efficient Graph-Based Symbol Recognizer. Eurographics Workshop on Sketch-Based Interfaces and Modeling 2006.

 crossref = {SBM06-proc},
  title = {An Efficient Graph-Based Symbol Recognizer},
 author = {WeeSan Lee and Levent Burak Kara and Thomas F. Stahovich},
 pages = {11-18},
 URL = {},
 DOI = {10.2312/SBM/SBM06/011-018},