Sketch Based Interfaces: Early Processing for Sketch Understanding

Bibliographical Information:
Sezgin, Stahovich, Davis. "Sketch Based Interfaces: Early Processing for Sketch Understanding". Proceedings of PUI-2001. NY. 2001. ACM Press.

URL:
http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.16.8291

This paper is one of the earlier efforts in attempting to generate corner-finding and curve recognition algorithms. The extended intention of this is to recognize shape primitives in such a way that makes geometric sense: drawn squares are converted into geometric squares that a second system would then be able to understand. This paper describes the multiple processes utilized to recognize freehand sketches.

There are three phases to the approach of "early processing" for sketch recognition: Approximation, Beautification, Basic Recognition.

Approximation
Fits lines and curves into a given set of pixels. Intended to streamline data in such a way that it's easier to identify the geometric properties of a given freehand shape.

The first process in this phase is vertex detection. This essentially is what we refer to as "corner finding" in more modern sketch recognition systems. This paper uses three sources of information to help identify vertices: direction, curvature (change in direction with respect to arc length), and speed data. Interestingly enough, speed data was largely considered irrelevant in basic sketch recognition when it was introduced by Rubine, and Long, in fact, removed it entirely from his modified set of features. This vertex detection process uses the extrema in curvature and speed, and notices that the maxima in curvature and minima of speed are correlated. We cannot, for instance, simply take minima in speed to mean that the user was drawing a corner, even if a typical user typically slows down his or her pen when drawing a corner. There also has to be a change in curvature, or else we would consider any abrupt change in speed, even on straight lines, as a "corner". However, even using both of these attributes at once yields false positives, so the paper uses a technique called "average based filtering" that looks for extrema in portions of curvatures that lie beyond a specified threshold. This threshold is based on the mean of each data set. These thresholds help us separate the data into regions that we can then use local and global maxima/minima on to identify which of these are false positives. These thresholds are applied to the curvature data and speed change. From there, the paper generates hybrid fits that implement these together to identify true positives in vertex detection. To generate hybrid fits, the paper computes vertex certainties, generates a set of hybrid fits, and selects the best fit from the previous two.

Beautification
This is the process in which small alterations to the input sketch are generated. For instance, lines that were clearly meant to be drawn as parallel (e.g. a rectangle) are altered so that they are geometrically parallel. Circles drawn imperfectly are changed to have geometrically accurate diameters. Curves that are a hybrid of these two are approximated as a set of several small geometrically accurate ellipses pieced together to form one large curve. Slopes are determined as a weighted average of the slopes of each segmented section of the shape, to determine the intended slope when the user was drawing it.

Basic Recognition
Objects that can be drawn from the user's input sketch are classified into lines and curves, and then classified further into a set of basic geometric shapes such as ovals, circles, squares, and rectangles. These features are hand-tailored from the given information presented by the paper's algorithm. It uses the segmented sections of the shape divided out by the vertices recognized in the 'approximation' phase, and uses template matching to see if they align with the geometric rules given by the algorithm to classify them as each of the geometric shapes.

To evaluate this system, thirteen students used this system and a Unix tool called Xfig. Xfig is a tool that supports freehand sketching but requires users to indicate which sections of his or her sketch are meant to be straight lines, curves, etc. Users were given the chance to get comfortable with both of the systems, and their experiences were documented with qualitative analyses. The students expressed approval at the automated recognition of this new system, and all but one preferred to use this system than Xfig. Additionally, high-level recognizers were written to classify and beautify additional shapes. The paper also reports to be working toward supporting overtracing.

Overall, this paper I felt provides good information on early efforts given toward vertex recognition, and using them to construct a roughly hierarchical recognition system that would identify curves and lines to eventually generate geometrically-correct shapes. Some of the evaluation, particularly with the user study, was unclear and I felt could be expanded more. For instance, what happened when it generated incorrect sketch analyses to the user? Was the user expected to redraw the shape? Was this shortcoming communicated clearly? How did the user react? The only source of evaluation in the user study was whether they preferred this or Xfig, and whether they would use it again, but there is a significant amount of information that could be discerned from the user experience. Additionally, some of the information given with regards to the algorithm was unclear and required significant explanation to fully understand.