PaleoSketch: Accurate Primitive Sketch Recognition and Beautification

Author: Brandon Paulson and Tracy Hammond
Comments:
1. Yuxiang's blog
Summary:
This paper is about primitive shape recognition. The shapes recognised by the system include line,polyline,arcs,curve, circle,ellipse,helix and spiral. First step in the recognition is to calculate some pre-recognition values for a stroke and pass it on to low level shape recognizers.Each of the recognizers return a boolean flag for recognition and a beautified shape object. Then the recognition results are fed into an hierarchy function which sorts them in order of best fit.
Pre recognition -
- Removing duplicate points (Points with same X,Y coordinates / time).
- Direction graph,speed graph, curvature graph and corners are computed.
- Normalized distance between direction extremes (NDDE)- this is calculated by dividing the stroke length between points with highest and lowest direction values by total stroke length.Curves will have high NDDE and polylines have Lowers NDDE.
- Direction change Ratio(DCR) - to find spikes in direction graphs. its is the maximum change in direction by average change in direction. First and last 20% of the stroke is analysed for higher curvature and the stroke till that point is considered tail. this is not performed on the strokes with short length.
- Test for overtracing - count the number of revolutions (2*pi) that the stroke has made. If its more than one revolution and above certain threshold, mark it as overtraced.
- Closed figure test - Ratio of distance between first and last point by the stroke length give measure of this feature.

Line test - Find the orthogonal distance between the best fit line and the real stroke. if the error(orthogonal distance/stroke length) is within a threshold, then mark the stroke as line.Verify overtracing and number of corners in the stroke.

PolyLine Test - Segment stroke into substrokes based on the corners. Berify line test on each substroke and each of them must have high DCR;

Ellipse test -Farthest points make the major axis and the the perpendicular bisector of the major axis is the minor axis. It should pass the closed shape test, NDDE must be high and feature area / area of ideal ellipse must be within a threshold.

Circle test:
Ellipse test+ ratio of major /minor axis should be close to 1.

Arc Test - Perpendicular bisectors of the chords on the arc can be used to determine the center of the arc. average distance of all the points from the center is take as ideal radius. Feature area error is taken into consideration. NDDE high and DCR low.

Curve test - fitting a bezier curve to the points. finding least square error with the bezier parametric values. Curve should have low DCR value.

Spiral test - Must pass Overtrace test, NDDE should be high,substroke should be a circle with ascending / descnding radius, Centers of the substrokes must be close to each other, distance between the farthest of the centers should not be greater than the diameter of spiral. distance between first and last point / the stroke length should be less than a threshold.

helix test -Spirals with moving centers. test on number of revolutions.

Complex test - more than one possible output.The results of the complex shapes are ranked.

Discussion -
Seems to be very powerful solution for identifying primitives. I would like to know the how computationally intensive this algorithm is. I liked the way this algorithm finds center for arcs. I did not understand the recognition part for curves since i do not know much about the bezier curves. Calculating rank for complex shape based on the primitive shapes they are composed of is interesting.