Reading #9: PaleoSketch: Accurate Primitive Sketch Recognition and Beautification (2008)

by Brandon Paulson and Tracy Hammond (paper)

Comments: Jianjie

Paleosketch is a low-level sketch recognition system that can identify primitive shapes from single strokes. It is capable of recognizing Lines, Polylines, Circles, Ellipses, Arcs, Curves, Spirals, and Helixes.

Recognition occurs in three steps: pre-recognition, individual shape tests, and result ranking. Pre-recognition performs is essentially some pre-processing to make recognition easier. This includes removing duplicate points, feature graph generation (speed, curvature, etc) that can be used during recognition, tail removal, and two new features DCR and NDDE. NDDE is the normalized distance between direction extremes, and it is calculated by calculating the stroke length between the point with the highest direction value and the lowest direction value (direction value = change in y over change in x). DCR is the direction change ratio, and it is calculated by taking the "maximum change in direction divided by the average change in direction."

Individual tests are done for lines, polylines, circles, ellipses, arcs, curves, spirals, and helixes. Each test compares some stroke features and calculates the confidence that a stroke is that shape. When all tests are complete, the results are ordered using properties of the corner finding algorithm.

To test this system, data was collected from 10 users. This data was run on Paleosketch and compared with some features disabled as well as with Sezgin's algorithm. Paleosketch achieved a recognition rate of 98.56% across all shapes.

__________

Paleosketch is a good primitive recognition algorithm, essentially combining ideas from previous work and adding in some new stroke features and result ranking. It performs much better than other algorithms we have covered so far, including Rubine's and Sezgin's algorithms. I have used Paleosketch some, and I have found it to be fairly accurate in practice. Its biggest drawback in my opinion is its speed. It runs fairly quick for smaller strokes and collections of a few strokes, but when strokes become long or there are many strokes being analyzed Paleosketch slows down and can take up to a second or more to execute. This makes it a poor choice for online recognition systems. However, it is a great improvement over previous systems.