Reading #7. Sketch Based Interfaces: Early Processing for Sketch Understanding (Sezgin)

Comment Location:
http://christalks624.blogspot.com/2010/09/reading-7-sketch-based-inferfaces.html

Summary:
This paper was written before 2001, before the $1.  $1 algorithm was a key basis algorithm like Otsu and Niblack are to document image binarization; it impressed upon me how early the development of sketch recognition truly is.  That basic algorithm was created only a few years ago; it could easily take another 10-20 years before we see some really impressive stuff.  This paper focuses on providing a basis for other algorithms by recognizing basic geometric shapes within a single stoke.  Vertex detection is the core of the algorithm.  The algorithm locates all the vertices, filters out the noise, and applies speed data to locate the actual vertices of the stroke. 

The algorithm uses Brezier curves to detect curved strokes.  The Brezier curves procedure seems sound, but not perfect.  The combination of the vertex detection and Brezier curve detection constitutes the bulk of the algorithm.  This algorithm is definitely dealing with the basics because the test data consisted of only 10 geometric shapes; the algorithm classified correctly 96% of the time, but only for those 10 shapes.  The author mentioned an extension on this algorithm but elaborated very little.

Discussion:
The vertex filter leaves room for improvement.  Simply using the mean of the data is quick and simple, but not very robust; a better method could involve smoothing the data and then choosing the highest peaks as the vertices.  Of course, that method assumes all vertices possess sharp corners; I do not know of an all-purpose answer (I don't think one even exists--yet).  The author combines speed data on assumption that a user will always slow down when drawing corners, and he reported good results (though I cannot personally be sure).

Overall, the algorithm seems a little simplistic (compared to some other algorithms I've seen) and the test data was criminally small.  It's good for proof-of-concept (which is important), but I would like to see something more substantial from this person (or someone who improves upon his research) in the future.