Analysis of “PaleoSketch: Accurate Primitive Sketch Recognition and Beautification”
Comments Made Elsewhere:
Summary:
Another curve and polyline recognizer, but also able to ellispes, arcs, curves, circles, helixes and spirals.
Related Works:
Talk about how feature-based recognizers require extensive training for strokes that must be drawn in the same manner, placing lots of constraints on the user. These authors use lots of Sezgin and Yu/Cai research in their work to develop a more robust geometric recognizer. Yu/Cai used curvature to segment strokes. Goal is to recognize lots of primitive shapes.
Implementation: Have a pre-recognition phrase, then a series of pass/fail tests that return a beautified shape, and then a hierarchical organizer.
Pre-recognition:
Remove duplicate points. Create a direction, speed, curvature, and corners graphs. Compute “normalized distance between direction extremes (NDDE)”, or distance between high and low points on the direction graph, and “direction change ratio (DCR)”, or maximum change in direction divided by average change in direction. Both used to help distinguish polylines from curves. Remove tails. Determine if overtraced by computing total rotation. Determine if closed figure.
Line Test:
Compute the least squares test between all the points and the best fit line. If meets a threshold and is not overtraced (less than three corners), it’s a line. Return line between the two endpoints (not best fit line).
Polyline Test:
Find then strokes. Each much pass the line test. The average least squares error must pass meet a threshold. Must have high DCR value.
Ellipse Test, Circle Test, Arc Test, Curve Test, Spiral Test, Helix Test, Complex Test:
Tired of reading…no need to rewrite the constraints here…
Hierarchy:
Whether a polyline or complex shape, all the returned beautified shapes are ranked by their components (example: line - 1, helix - 5). The lowest rank is the shape used, though alternatives are kept for the user.
Discussion:
I’m glad that I read Sezgin first. I think it helped me compare and constrast with this paper better.
In the future work, they said they wanted to be able to handle multiple strokes. One constraint could be to check the distance between endpoints of strokes and, if within a threshold and the time between the two do no vary much, throw the group of strokes through the recognizer. Comparing endpoints is like the user “picked up where he left off”. How these two thresholds are determined, I don’t know. You’ve always got “undo” on your side. Not a universal approach.
I like the “invisible corners” problem…could maybe approach it by shooting vectors off the tangents of points and marking where they regularly intersect. Check the dot product to see if they’re close to being orthogonal.
Another paper I’m excited about.