Sketch Based Interfaces: Early Processing for Sketch Understanding

Comments

Daniel's blog

Summary
This paper describes about the algorithm which accroding to the author is a directed study for creating the pen input devices to be more usable in terms of the end user’s ability to interact with the system like he/she would do on a paper. This paper tries to define methods which can allow the user interaction more intuitive combined with the power of computing.
The author’s approach for the early processing of sketch is based on three phases approximation, beautification, and basic recognition.

Stroke Approximation:
It is to approximate the stoke with a more compact and abstract description, while both minimizing error and avoiding overfitting. The first step in stroke approximation is Vertex Detection. Vertex detection explains the methods used to find corners in a stroke. First a direction graph of the stroke is generated. From the direction curvature graph can be determined. The peaks in the curvature graph can pointed out as the vertexes or the corners of the stroke. The curvature graph has limitation is that it cannot properly identify the strokes which has a small curvature value so that it falls below the mean. To identify such corners the authors also presents the idea of speed graph. The speed graph algorithm works on the assumption that the user tends to slow down when it is drawing a corner. Using the speed graph alone has it’s own limitation. Poly lines formed from a short and long vertexes can be problematic. In such cases two corners can be regarded as on corner.
The author next presents the idea of Hybrid fit which uses both the above mentioned techniques to identify the best set of vertices.
The next problem in stroke approximation is the related to handling curves. The above mentioned techinques are good for polygons. The author approximate the curve regions with Bezier curves which are defined by two endpoints and two control points.

Beautification:
It refers to adjusting the sketch output to make it look as it was intended by the user. Here the author adjusts the slopes of line segments in order to ensure that were apparently meant to have the same slope end up being parallel.
Basic Object Recognition:
In this final step the author tries to recognize the basic objects that were built from line segments and curve segments. These simple geometric objects include ovals, circles, rectangles and squares.

Evaluation:
Overall the users of the system were very happy when they drew sketches on it. They could interact with the system very naturally. The recognition of the system for vertices and approximation of shapes with lines and curves was correct 96% of time.

Discussion
The presents some very good ideas in corner detection particularly the hybrid approach. But what I think that the paper lacks is the proper description of the ideas beautification and basic object recognition. After reading the paper it seems quite difficult to implement these with only the explanation in this paper.