Reading#15 An image-based, trainable symbol recognizer for hand-drawn sketches

Comment
Chris


Summary:


This papers deals with recognition problem using purely off-line approach, which consider each sketch or symbol as sets of pixels. The authors combined four different classifiers which are based on template matching. Most importantly, the author proposed one beautiful way of tacking orient invariant by transforming screen coordinate into polar coordinate. All the example templates are stored in the database, and each input symbol is matched with templates and return the top N best lists.
The four template matching metrics are Hausdorff distance, Modified Hausdoff distance, Tanimoto coefficient and Yule coefficient. The first two measure the dissimilarity which based on distance between two symbols, and the remaining two measure the similarity which based on the number of black pixels, number of white pixels and number of overlapping black or white pixels. After getting these four classifiers, they are normalized into [0,1] range and then combined for recognition.
The most important contribution of this paper is they proposed very smart way to tackle with orientation invariant. Because calculating the rotation angle in screen coordinate is computationally very expensive, they choose to first transform the symbol image into polar coordinates and mapped into [-pi, pi] range. In polar coordinate they can easily calculate the rotation angle and again transformed into screen coordinate to continue their recognition. Besides calculating rotation angle using polar coordinate, another one important usage of this coordinate is to prune template examples before getting into recognition step to decrease the time complexity. They reported that this method can eliminate about 90% template examples before applying classifiers.
The overall result seems very promising, in most of cases, they get more than 90% accuracy for top 1 returned result. And the users studies are based on graph symbols and digit symbols.


Discussion:


Another nice paper, purely off-line approach paper. There are several contribution of this paper. 1) Multi-classifier combination. 2) different distance matching approaches 3) Handling rotation using polar coordinate. 4) Decrease the impact of nearest points of centroid when transforming into polar coordinate. Paper very clearly shows the idea, and nicely organized. However, vision based recognition has difficulty of recognizing similar shapes, as mentioned by author. the future research might be combined vision-based approach with on-line stroke information.