Early Processing for Sketch Understanding

Sketch Based Interfaces: Early Processing for Sketch Understanding

Introduction:

This paper comes from the idea of utilizing the powerful processing capability of a computer to realize an easy and flexible UI for sketch recognition. In other words, this interface should give users a feeling as if they are drawing in a paper. To realize this target, the first problem is how to convert digitalized pen strokes into intended geometric objects. This is done by interpreting the pixels of user sketch and completing three-step processing.

Three-step processing:

(1)Approximation:

Aim: Match the most basic geometric primitives ( lines and curves ) to a given set of pixels.

Vertex detection:

Mark corners of sketch with vertices.

(1.1)How to determine vertices in sketch?

---Curvature: Change in direction with respect to arc length.

Those points with a maximum of the absolute value of curvature are vertices.

In Figure 1, the points in red circle are vertices

---Speed:

Those points with a minimum of speed are vertices.

In Figure 1, the points in green circle are vertices.

Figure 1 Direction, Curvature and Speed graph for Stroke

   To avoid the bad influence of noise in data, the authors introduce Average  Based Filtering. In Figure 2 and Figure 3, the red line is threshold. We are looking for maxima of curvature only where the curvature is already high and minima of speed only where the speed is already low. Thresholds are selected empirically. For Curvature Graph, it is the mean value. However, for Speed Graph, it is 90% of the mean value.

Figure 2 Speed Graph for Square with threshold

Figure 3 Curvature Graph for Square with threshold

(1.2)Generating Hybrid Fits:

       Computing vertex certainties:

      Our certainty metric for a curvature candidate vertex v_i is the scaled magnitude of the curvature in a local neighborhood around the point, computed as |d_i−k − d_i+k|/L. Here L is curve length between points S_i-k and S_i+k. k is a small integer defining the neighborhood size around v_i. The certainty metric for a speed fit candidate vertex v_i is a measure of the pen slowdown at the point, 1 − v_i/v_max. v_max is the maximum pen speed in the stroke. The     certainty values are normalized to [0, 1]. 

      Generating a set of hybrid fits:

      The initial hybrid fit H₀ is the intersection of F_d (curvature data) and F_s (speed data). A succession of additional fits is then generated by appending to H_i the highest scoring curvature and speed candidates not already in H_i. To do this, on each cycle we create two new fits: H_i=H_i+v_s (i.e., H_i augmented with the best remaining speed fit candidate) and H_i= H_i+v_d (i.e., H_i augmented with the best remaining curvature candidate).

      Selecting the best fit:

     We set an error upper bound and designate as our final fit Hf, the Hi with the fewest vertices that also has an error below the threshold.

Handling curves:

Approximate curved region with Bezier curves, defined by two end points and two control points. Let u = s_i, v = s_j, i < j be the end points of the part of S to be approximated with a curve. We compute the control points as:

Figure 4 Control points calculation formula

Where t₁ and t₂ are the unit length tangent vectors pointing inwards at the curve segment to  be approximated. The 1/3 factor in k controls how much we scale t₁ and t₂ in order to reach the control points; the summation is simply the length of the chord between S_i and S_j.

(2)Beautification:

Modifies the output of the approximation layer to make it visually more appealing without changing its meaning, and secondarily aid the third phase, basic recognition.

Figure 5 The effect of Beautification

(3)Basic Recognition:

The recognition of the most basic objects that can be built from the line segments and curve segments produced so far. Eg. simple geometric objects( ovals, circles, rectangles and squares )

Bibliography:

Tevfik Metin Sezgin, Thomas Stahovich, Randall Davis, Proceeding PUI '01 Proceedings of the 2001 workshop on Perceptive user interfaces Pages 1-8
http://faculty.cs.tamu.edu/hammond/courses/SR/papers/Sezgin/Sezgin2001Sketchbased.pdf