Reading #16: An Efficient Graph-Based Symbol Recognizer

Comments:
Geroge

Summary:
This paper discusses (you guessed it) an efficient graph-based symbol recognizer. Using an Attributed Relational Graph (ARG), the authors can describe symbols in terms of their geometry and topology. A symbols geometry would include its primitive shapes and structures, which are treated as nodes. As the authors state, recognizing sketches involves matching graphs. And FYI, this can be hard as hell. So your user forgot to draw a primitive shape like a circle? There goes a node and a couple of edges. Although representing a symbol in terms of its topology allows for rotations and scaling to be matching, it cannot help the issue of missing components.

ARG for a perfect square.

Given training examples of each symbol class, the system constructs an "average ARG" for that class. To improve the average, the authors maintain stroke order and orientation across all examples. In testing, the system was proven to return the correct symbol in a top 3 list with over 93% accuracy.

Discussion:
I like how complex the symbols are that the authors tested in this paper. Some of them remind me of good old Civil Sketch. The trade-off between accuracy and speed of calculation is important, although even the longest recognition time only took 67.8 ms. Not too bad, but the fastest took 2.0 ms... but with accuracy around 79%. Accuracy vs. Time is an epic battle.