"PaleoSketch: Accurate Primitive Sketch Recognition and Beautification"

by Brandon Paulson, Tracy Hammond

Summary

In addition to placing few drawing constraints on users, the recognizer introduced in this paper is also able to return multiple interpretations as well as support more primitive shapes (line, circle, ellipse, arc, curve, spiral, helix). The recogizer in this paper is geometric-based. Strokes are pre-recognized before going on to low-level shape recognizers, beautification and the subsequent hierarchy.

Pre-recognition begins with removing consecutive points with duplicate position or time. Then the direction graph, speed graph, and curvature graph are computed. And corners are found by 1) going through points on the sketch and find all points before the points that fail line test, 2) merging corners that fall within a neighborhood with their average index, and 3) replacing non-end corners with the points that hasve the highest curvature in their neighborhood. In addition, two new features are introduced: normalized distance between direction extremes (NDDE = stroke length between point with highest direction and point with lowest direction / total stroke length), and direction change ratio (DCR = maximum change in direction / average change in direction). Curves typically have high NDDE and low DCR while polylines have low NDDE and high DCR. For long and many-points strokes, if the highest curvature within first and last 20% of the stroke, then tail removal is performed. Then overtracing and closure is tested.

Then low-level shape tests (line, polyline, ellipse, circle, arc, curve, spiral, helix, and complex test) are performed by computing various features of the stroke, comparing feature values with the thresholds and calculating errors. Of them, complex test is the default test that recursively divide the substroke into two parts at the highest curvature point and send back into the recognizer until all non-polyline primitives are got. Beautified shapes are returned after tests.

Hierarchy uses a ranking algorithm to find the best fit among multiple interpretations. Assgin scores to shapes: line = 1, arc = 3, curve = 5, circle = 5, ellipse = 5, helix = 5, spiral = 5, and sum all the scores of the substrokes. The interpretations are ranked by the total score, interpretation with lower score has higher ranking. Lastly, tails are removed, and the substrokes at both ends will be removed or adjusted accordingly.

Results show that its accuracy is as high as 99.89%, and 98.56% of the correct interpretation is the top interpretation. Most of the misclassified strokes would actually also be misclassified by human recognizer. And this low-level recognizer is integrated into a high-level system - LADDER.


Discussion

In terms of recogition accuracy, this recognizer is amazing, and it supports a handful of primitive shapes, which enables it to recognize quite complex sketches. Tons of thresholds are defined to distinguish minute differences between shapes. And NDDE and DCR are really useful features. The ideas of "continuation strokes" and "invisible corners" seems promising, for rounded rectangle or polygon, the edges can be moved to pass the centroid of the relevant substroke and parallel to the originally recognized edge.