Monday, December 13, 2010

Reading #16 Graph Based Symbol Recognizer

Comment:
Johnatan.

Summary

As the name suggest, this paper recognizes symbols by building a relational graph and matching the graph to the existing graph templates.

Graph isomorphisim is an np-hard problem in general. This paper uses 4 methods to find the closest match; Stochastic match, Greedy, Sort and Error Driven Matching.

The method scored about %90 accuracy tested on about 20 shapes.

Discussion
This idea is particularly interesting to me since I have been using graphs for my recognition assignments. And actually our final project was almost entirely based on this idea. Graph isomorphisim is an hard problem, but you can reduce the complexity by benefiting from geometry data as we&they did.

1 comment:

  1. I also used graph-based techniques for the first project. Before this class, I had not thought of representing sketches as graphs, since graphs are inherently non-sketchy.

    ReplyDelete