Sketch Based Interfaces: Early Processing for Sketch Understanding

In 2001, Sezgin et al. published a paper that re-introduced the idea of finding corners based on speed to the sketch recognition community. Their paper and associated system was aimed at allowing for natural free form sketches that can then be beautified and recognized to convey the same information at was intended when drawn. This smarter non-restrictive sketching was intended to allow for the freedom of freehand sketching while preserving the detail, correctness, and direct manipulation capability usually provided by more rigorous design tools, thus bridging a gap in sketch based software and professional design software and thus ease the creation process for designers.

Their system works in 3 steps:

1. Approximation - to find the vertices
• Vertex Detection
• Uses Speed and direction of the stroke to recognize corners (vertices)
• Maximum change of direction
• Minimum speed
• Reduces noise with average based filtering
• Chooses points above an emperically based threshold of the average value for change of direction
• Chooses points below 90% of the average value for speed
• Use Hybrid Fit Generation to decide which vertices are actual corners
• Uses exactly matching vertices chosen from the change of direction set (Fd) and the speed set (Fs) to generate an initial "hybrid fit" H_0
• adds vertices one at a time to create two new fits where each fit is the previous fit plus one vertex from Fd and Fs
  to produce H'' = H_i + V_d and H' = H_i + V_s , respectively
• calculates the error produced by the new fits and checks if the error is still within an acceptable threshold. 
• Error is calculated as the orthogonal distance squared from the fit from the fit to all points and divides by the number of the points (which produces the average sum of square of the distances from the fit to each point in the stroke)
• The final fit is H_f
• Handling the curves
• Handles Curves
• Finds the curved regions
• if( L_2 / L_1 > 1 + threshold ) { then it's a curve }
• Where L_2 is the arc length between two consecutive points in the input stroke
• Where L_1 is the Euclidean distance between the same two points in H_f
• Approximates the curved regions through the use of Bezier curves (2 endpoints, 2 control points)
• Where C_1 = k * t_1 + S_i
• Where C_2 = k * t_2 + S_j
• Where S_i and S_j are points on the input stroke
• where i < j
• Where t_1 and t_2 are unit length tangent vectors pointing inward to the curve
• Where k is the control to for scaling t_1 and t_2 to reach the control points
• k = 1/3 sum from n = i to j -1 ( abs ( S_n - S_n+1 ) )
2. Beautification
• realigns the lines between vertices to have the average slope of the slopes between points along the line and rotates those lines around its midpoint
3. Basic Recognition
• Uses "hand-tailored" templates to recognize geometric objects constructed from the lines and the curves left after beautification.
• Ovals, Circles, Squares, Rectangles

The evaluation of their system consisted a qualitative comparative study against Xfig to determine relative ease of use and efficiency and a study on recognition rate for vertices and curves.
While claiming "praise" from their 13 participants and 96% recognition rate for identifying vertices and curves  on 10 different figures, little was said on how well it was able to classify the higher level geometric shapes.

There are many problems with the paper including the use of arbitrary threshold such as the thresholds for choosing vertices in Fd and Fs and the neighborhood range value k which normally would make this paper unacceptable. But given its positive results on making sketching more accurate and seamless, this paper was a major contribution for the field.


Tevfik Metin Sezgin, Thomas Stahovich, and Randall Davis. 2006. Sketch based interfaces: early processing for sketch understanding. In ACM SIGGRAPH 2006 Courses (SIGGRAPH '06). ACM, New York, NY, USA, , Article 22 . DOI=10.1145/1185657.1185783 http://doi.acm.org/10.1145/1185657.1185783