Reading 17 : PaleoSketch

Citation:

Paulson, Brandon, and Tracy Hammond. "PaleoSketch: accurate primitive sketch recognition and beautification." Proceedings of the 13th international conference on Intelligent user interfaces. ACM, 2008.

Publication Link 

 

Summary:

Paleosketch is one of the landmark techniques used for primitive shape recognition, i.e after early processing of corners is completed. Many current applications make use of Paleosketch as the technique to obtain individual shapes before passing it to higher level recognizers to obtain further groupings.

 

Discussion:

 

The pre-processing involves a few stages,  such as computing corners (Using a three step process of selecting consecutive corners, merging similar corners in a neighborhood and finally selecting the highest curvature point in a neighborhood as the corner), plotting direction, curvature and speed graphs and using them to compute NDDE and DCR.  We also detect closed shapes, overtracing and tails at this time.

 

Next,  the strokes are passed to a series of shape detectors. Each shape detector subjects the stroke to a set of geometric constraints, returns the shape if all the constraints are passed. If the stroke does not pass any test, it is recursively broken down at the point of highest curvature. Later, the detector also tries to recombine primitive shapes by passing it to a secondary function (as dividing at point of highest curvature may not necessarily give individual shapes all the time)

The geometric tests are designed for the following shapes:

1. Line

2. Polyline

3. Circle

4. Ellipse

5. Curve

6. Spiral

7. Helix

(Refer paper for the exact details of these geometric constraints)

Finally, to select the final set of shapes the defines a stroke, a hierarchical ordering is used that tries to minimize the number of lines returned (i.e it favors arcs over lines, and complex shapes over heavily segmented polylines)