Reading #16. An Efficient Graph-Based Symbol Recognizer(Lee)

COMMENTS:


SUMMARY:

The recognizer presented here is based on recognition of symbols in the form of attributed relational graphs representing the symbols' geometry and topology.  The nodes of the graphs (geometric primitives) and the edges (geometric relationships) are compared to determine if there's a match.  This approach is tolerant to large variations in size and rotation.

The authors compare four different graph matching techniques: stochastic matching, error-driven matching, greedy matching, and sort matching.  The first 3 methods achieved a recognition rate between 93.7% and 92.3%.  The Sort method had an accuracy rate of 78.5%, however it was significantly faster than any of the other methods and provided the correct match in the top 3 results 93% of the time.

DISCUSSION:

This paper gives a good overview of how symbols are represented and using attributed relational graphs.  It also gives a brief but clear explanation of the 4 graph matching techniques that were compared.  My only complaint is that I would have liked to see some of the ARGs of the symbols used in the user study.  I also wondered, since the Sort method assumed consistent orientation, how the results would have improved if that were in fact true.