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

Comment Location:
http://pacocomputer.blogspot.com/2010/12/reading-16-efficient-graph-based-symbol.html

Summary:
The algorithm employs a relational graph as the basis for its recognition.  For homework 1, I used relations between some lines as part of my algorithm, but I did not base my entire algorithm off the relations between strokes.  This algorithm does that.  Once the relational graph is created, the sketch is matched to the template that has the closest relational graph.  There are several ways of doing this, and the paper employs 4 of them:

"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."

A grand total of 23 different symbols were used in the testing.  The only algorithm to perform with less than a 90% accuracy was the sort type; the sort type also had the shortest computation time.  There was very little difference in the accuracy rates of the other 3 algorithms; their comptutation times differed widely though.  Stochastic took the longest to finish.

Discussion:
This algorithm is definitely viable for sketch recognition.  The grand future of sketch recognition no doubt involves an interface that recognizes and fixes up any sketch a user is making.  To encompass "any sketch", a large database is currently required and a significant amount of time to use that database is required.  The question remains, is there a way to get around that?  Is there a method of recognizing sketches that doesn't rely on a large amount of stored memory?  If not, then the cost of using that memory must be made much smaller than it is today and the computational abilities of computers must increase drastically (latter one's always happening).