Paleo-Sketch: For Primitive Shape Recognition and Beautification

Citation

B. Paulson and T. Hammond, “PaleoSketch : Accurate Primitive Sketch Recognition and Beautification,” pp. 1–10, 2008.

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

Summary

Paleosketch is a Recognizer for Primitive-Shape like Lines, Arc, Circles etc. Besides recognition, it is also used for beautifying them. Since it uses Geometric recognition at its helm, so it is free from the vagaries from the system using Gesture Recognition techniques like Rotation, direction, starting point etc. That's the reason it performs much better for domains where the system should have rotation invariance etc. It doesn't distinguish between a Circle drawn clockwise or anti-clockwise.

Approach

1. Each stroke consists of sequence of points represented by (x, y, time)
2. It, then, removes duplicates points. Points with either the same (x, y) co-ordinates or the same timestamp,
3. It computes two new exciting and innovative features for finding Corners:
1. NDDE: Normalized Distance between Direction Extremes
2. DCR: Direction Change Ratio
4. It then performs two tests to determine:
1. If the line is over-traced (no of revolutions are greater than a threshold),
2. If the shape is a closed-shape (Compares the distance between two end-points and the total length of the stroke)

NDDE:

1. It calculates the distance between the points of highest direction value and points of lowest direction value where direction value is arctan of change of y over change of x,
2. NDDE = above value/ total length of the stroke
3. Since for Arcs, two points of direction extremes are the starting point and the ending points, this value is pretty high
4. While for Polylines, these two points can be pretty near and hence this value is pretty low

DCR:

1. DCR = Max change in direction value/avg change in direction value,
2. Since in case of Polylines, average change in direction value is very less (mostly at corners), DCR value is pretty high,
3. Since in the case of Arcs, there is a change in the direction at every point, the average value is pretty high and hence the low value of DCR,
4. We normally ignore the first and the last 5% of the stroke to mitigate noise

It then performs a series of tests to distinguish between different kind of shapes.

1. Line Test,
2. Arc Test,
3. Polyline Test
4. Ellipse and Circle Test
5. Curve Test
6. Spiral and Helix Test
7. Complex Test

To determine Complex Shapes, it uses a Ranking Algorithm where it ranks the each interpretation and chooses the one with with Lowest Rank.

Thoughts:

It performed really better than the existing recognizers. This was evident from the high accuracy it achieved during the testing.

Future Ideas

This can be used as Primitive Recognizer in domains with Complex Shapes. This has already shown good results with a system named LADDER. This idea can be expanded into other domains as well.