Introduction
This paper introduces a graph based system for recognizing symbols. Graph structures are used to represent the primitives that make up a symbol and how they are connected, geometrically and topologically. The recognizer is trained by creating these graph structures for each example sketch, then building average graphs that represent the individual symbol classifications. Four graph comparison algorithms were then compared for use in recognition, a stochastic search, error driven matching, greedy search and geometric sort matching. Stochastic, error driven and greedy search all achieved similar top-1 recognition rates, around 93% with relatively close running time, with stochastic being the slowest and greedy being the quickest. Geometric search was much faster, 2ms compared to the 12ms of greedy or 68ms of stochastic, however its top-1 recognition rate was lower, at 78%, and was aided by drawing consistency between users in the study.
Discussion
I like the search methods presented in this paper, and the fact that they can be applied directly to a symbol recognition system. Such a system lends itself to future improvements in search speeds, and would seem ideally suited for other optimizations like parallelization. This is in contrast with other recognition systems we have been introduced to which have not appeared trivially parallelizeable.
Parallelize the 4 searches? Interesting... you could present possible results while the slower, more accurate searches run. Most of the time, the result may be correct and therefore you can abort the time-intensive searches.
ReplyDelete