Reading 13 : Domain Independant Sketch Recognition

Citation:

Yu, Bo, and Shijie Cai. "A domain-independent system for sketch recognition." Proceedings of the 1st international conference on Computer graphics and interactive techniques in Australasia and South East Asia. ACM, 2003.

 

Publication Link : http://dl.acm.org/citation.cfm?id=604499

 

Summary:

The main approach used in this paper is to combine primitive shape recognition with the early processing (as opposed to having a separate pre-processing stage as with Sezgin). The vertex detection phase is  an implicit part of the stroke detection. The paper then explains its line segment approximation and curve approximation algorithms, along with some of the post processing features. The concept used for determining the fit of strokes against primitives is called 'feature area verification'.

 

Discussion:
The main takeaways from this paper are the approaches to detect lines, circles, arcs and curves.

Line Segment Approximation:

Try to fit a best fit line, and compute the feature area using this candidate line. The stroke area is taken to the length of the stroke into its thickness. If the ratio of the feature area to stroke area is less then 1, the stroke is recorded as a line

Circle Approximation: 

Check if the direction graph of the stroke can be approximated as a circle. If so, take a candidate circle that takes the center of the stroke's bounding box, with radius as mean of distances between the center and the stroke point. Feature area is then applied to try to fit the circle. If the direction graph extends beyond 2pi, then it is checked for over-tracing and helical strokes.

Arc Approximation:

1. Check if direction curve can be approx. using line

2. Find the perpendicular bisector of arc, and find the find the circle on which the end points, and this intersection points lie.

3. Follow the same procedure as for circles

Handling Self-Intersection Strokes:

Uses two heuristics and compares results 

(i)Simple is better

(ii) Specific is better

Finally, the paper also covers some of the post processing routines, including:

-Elimination of false and redundant elements introduced by noise

-Adjust layout of elements

-Basic object recognition