PaleoSketch: Accurate Primitive Sketch Recognition and Beautification

Bibliography Information:
Paulson, Hammond. "PaleoSketch: Accurate Primitive Sketch Recognition and Beautification." IUI '08 Proceedings of the 13th international conference on Intelligent user interfaces. Pages 1-10 . ACM New York, NY, USA 2008.

URL:
http://dl.acm.org/citation.cfm?id=1378775

PaleoSketch, a novel low-level shape recognizer, is one of the flagship projects of the Sketch Recognition Lab. It is a recognition and beautification system that recognizes eight primitive shapes as well as combinations of these primitives themselves to achieve recognition rates upwards of 98.56%, as well as beautifying input input sketches to aid in classification at an early level. Much of this success has been brought about due to the inclusion of two new classification features, Normalized Distance between Direction Extremes (NDDE), and Direction Change Ratio (DCR).

To calculate NDDE, the point with the highest change in direction value (highest change of Y over change of X) and the point with the lowest change are recorded. The stroke length between these two points is the divided by the total stroke length, which essentially provides us with the percentage of the stroke that is between these two extremes. Shapes such as arcs have been observed to yield particularly high NDDE values. Polylines with particularly many "spikes" in their shapes, on the other hand, yield lower NDDE values.

DCR is used to telling polylines and curved strokes apart. DCR is similar to NDDE in that it's also used to see whether there are "spikes" in the drawn shape. DCR is the the max change in direction divided by average change in direction. Polylines will typically have very high DCR values, whereas they will have lower NDDE values.

From there, Paleosketch performs varying tests for classification, each with their own guidelines:

• Line Test: 
• Polyline Test
• Ellipse Test
• Circle Test
• Arc Test
• Spiral Test
• Helix Test
• Complex Test

After collecting two sets of data (the first collecting 900 shapes from 10 users for training, and same amount for testing), it was found that the correct-shape interpretation was 99.89%, but only 98.56% was reported as the top interpretation. Polylines accounted for 1.44% of the error. Overall, the results rival those of state-of-the-art, low-level recognizers that do not recognize as many of these primitives. These are promising results, as they can easily be fitted into fitting higher degree complex interpretations.

As previously mentioned, this paper proved to be one of the most important in the Sketch Recognition Lab, as it was the single most accurate and novel implementation of sketch recognition. The implementation of the different tests, and the fact that there's a difference between, for instance, a circle and an ellipse as two different primitives, makes it clear that the classification categories that were considered prior to this paper could stand to have significant improvement.