Gestures without Libraries, Toolkits or Training: A $1 Recognizer for User Interface Prototypes

Summary:

Wobbrock et al.'s $1 recognizer is a system designed to be a simple recognizer that does not rely on any mathematical background. With this recognizer, novices to sketch recognition can have an use simple gestures in their interfaces.

The $1 recognizer has four steps: (1) resampling, (2) rotation, (3) scaling, and (4) classification. Points in a gesture are resampled into N equidistant points defined by the developer. The gesture is then rotated so that the line between the center of the gesture and the starting point is at the 0 degree position, i.e. the center-start point axis is at 3 o'clock. The gesture is then scaled to fit within a square of some size and translated so that the center of the gesture is at the (0,0) origin.

Finally, the gesture is classified by first calculating the average distance between points in the gesture and the points in all templates (known gestures). This is called the path-distance by the authors. A score is determined directly from this path distance and the scaled square's size.

Overall, the recognizer has good results with around 98% accuracy for simple gestures. The classification relies heavily on the number of templates in the system.

Discussion:

This recognizer really does not introduce anything new to sketch recognition, but it does wrap up some basic vision and sketch recognition techniques into a simple (and given) algorithm. The technique used by $1 is not much different then general template/bitmap comparison, except using the points is a bit nicer when working with single strokes. On the other hand, bitmap comparison allows for multiple strokes in any order. This technique also relies highly on visual differences in gestures, and it does not allow for the same gesture at different scales or rotations. For instance, a forward slash gesture with a mouse or pen is a common gesture to indicate move forward in a web browser. Similarly, a backwards slash/dash indicates "page back". This recognizer cannot handle these cases.

Ambiguous Intentions: a Paper-like Interface for Creative Design

Summary:

Gross and Do describe the Electronic Cocktail Napkin program that allows users to draw ambiguously as if they were sketching a design on a piece of scrap paper. The Napkin then takes the sketch, examines objects within the ambiguous drawing, interprets the drawing's context, and recognizes the objects.

Domain recognizers are user defined, where the user draws examples and the Napkin identifies the symbols and patterns. Symbols can span across multiple domains, such as a circle acting as a table in a floor plan domain, and the same circle representing a node in a graph domain.

As a user draws in a new, blank Napkin, the system discerns whether each stroke or symbol can be recognized, is ambiguous, or has failed to be recognized. If a symbol is recognized then it can only be recognized in the known domain, or only one domain. If a symbol is ambiguous then it can be recognized in multiple domains. Otherwise, the system cannot recognize the symbol at the time and stores that information for later. A user can also manually specify a symbol, if need be.

Symbols are related to each other via constraints specific to a domain. For instance, graphs and circuits have connected constraints, and floor plans can have perpendicular constraints for walls. Low-level recognition is accomplished with 3x3 normalized "glyphs" with features. Glyphs can also be grouped into configurations, which are ranked hierarchically above individual glyphs.

Discussion:

Overall, I think the Electronic Cocktail Napkin was a good idea that was too ahead of its time and too tied down to one system. The authors even mentioned that the system suffered from not having access to the best type of technology for the system, which they mentioned as LCD digitizing displays the user could draw on. The equipment that the Napkin was using involved a separate digitizing pad and display, which breaks the entire mapping from napkin to sketch pad.

Recognizing and Beautifying Low-level Sketch Shapes with Two New Features and Ranking Algorithm

Summary:

Paulson's paper describes a sketch recognition system for recognizing primitive shapes, and combinations of these shapes, with high accurarcy. The system constrains the user to draw each shape to recognize in a single stroke, but does not constrain the user in drawing style (i.e. not gestures). The shapes that the system recognizes include lines, polylines, circles, ellipses, arcs, curves, spirals, and helixes. Complex fits can be formed from these eight shapes.

Feature calculation for each stroke incorporates computing direction, speed, and curvature graphs, as well as finding the corners of the stroke. Furthermore, Paulson introduces two new metrics: NDDE and DCR. NDDE is the normalized distance between extremes, and calculates the difference between the stroke length between the highest and lowest directional values in the stroke, and divides this segment length by the total stroke length. Arcs and curves tend to have high NDDE values, whereas polylines have lower NDDE values. DCR is the direction change ratio of a stroke, and is calculated by dividing the maximum change in direction by the average direction change. Arcs tend to have little changes in direction over time, whereas the direction graph for a polyline contains spikes in direction change.

After this preprocessing, the stroke and computed features are passed to individual shape testers. These testers, once for each shape (line, arc, etc.), see if the stroke follows set rules for each primitive. For instance, in the case of a circle test, the stroke must have a minor and major axis ratio close to 1.0, the stroke's NDDE value must be high, and the feature area error of the stroke must be low. Each shape tester returns whether the stroke passed the test.

Finally, for each shape test passed, the interpretation is placed in a sorted hierarchy. The hierarchy assigns weights for shapes, based on the shape's commonness and how complex a fit is. The interpretations added to the hierarchy in a certain order, described in the paper.

Paulson's system obtains a 98.6% recognition rate for the entire system, and a 99.89% rate where the correct interpretation is within the top 3 handed to the user. The recognition gain comes from his two new features, which increase the system's accuracy by over 20%. The system ranking system helps sort the interpretations so that the system is 7% more likely to rank the correct interpretation as the top interpretation.

Discussion:

Paulson's results are quite amazing in that the system's recognition improves by 20% with just two new features. When analyzing his results table, I noticed that Sezgin's algorithm worked better than Paulson's when returning complex fits, but performed worse on every other shape test. Since Sezgin's method heavily favors complex fits these results seem logical.

I noticed that circles and ellipses are given the same hierarchy score (5) in the system, which striked me as odd since I'd want to try and favor circles more than ellipses. Since a circle is always an ellipse, but an ellipse is not always a circle, I would want to favor circles in the final ranking. In this way, the system will slightly prefer circles over ellipses when the two tests pass.