Reading #16 graph-based symbol recognizer

Comment on:

Kim

Summary

This paper introduced a graph-based symbol recognize. Basically, it is still a template matching method, however, the template is not the stroke itself, but the attribute relation graph (ARG )of it.

The recognizer treat each symbol as an ARG  that represent the symbol’s geometry and topology. For example, an ideal square can be represented as below

This paper use six error metric to generate the dissimilarity score of the candidates with the templates: Primitive Count Error, Primitive Type Error, Relative Length Error, Number of Intersections Error, Intersection Angle Error and Intersection Location Error. Then, the recognizer use four different matching method to calculate the similarity between graphs: Stochastic Matching, Error-Driven matching, Greedy Matching and Sort Matching.

The result shows all four graph matching method has more than 92% accuracy with different recognition speed.

Discussion:

The critical problem of graph-based recognizer is how to construct accurate ARG.  But the idea of generating ARG for symbol is really interesting, which can make the recognizer rotation and scaling. Also, the comparison between different algorithms is also useful  when choose algorithm for different situation.