$1 Recognizer

Summary

This paper seeks to create a gesture recognizer that would allow novice programmers to incorporate gestures into their UI. The $1 algorithm is easy, cheap, and usable anywhere. It involves only basic geometry and trigonometry and requires about 100 lines of code. It supports configurable rotation, scale, and position invariance, does not require feature selection or training examples, is resilient to variations in input sampling, and supports high recognition rates.

The algorithm has 4 steps.

1. Resample the Point Path. It resamples the gestures by splitting the path into N equidistant points.
2. Rotate Once Based on the Indicative Angle. The indicative angle is the angle formed between the centroid of the gesture and the gesture's first point. The gesture is rotated so that this angle is 0 degrees.
3. Scale and translate. The gesture is scaled to a reference square and then translated to a reference point (the origin of the frame)
4. Find the optimal Angle for the Best Score. A candidate is compared to each stored template to find the average distance between corresponding points.

The recognizer cannot distinguish gestures that depends on orientations, aspect ratios, or locations. Horizontal and vertical lines are abused by non-uniform scaling. Also, the recognizer does not distinguish based on time.

The user study consisted of 10 subjects using a Pocket PC with a stylus. They were given a series of gestures to do at slow, medium, and fast speeds. They compared the recognizer with Rubine and Dynamic Time Warping. $1 had a 99.02% accuracy. The number of templates affected the recognition error rate. $1 improved as more templates were added, with an error rate from 2.73% at 1 template to 0.45% at 9 templates. Slow and fast gestures had higher errors than medium. $1 took 1.6 minutes to run 14400 tests for 160 gestures.

---------------------------------------

Commentary

I like this algorithm. It is easy and fast. However, there are some drawbacks (ie the limitations listed). I think that there has to be some drawbacks for a "simple" algorithm. In order to simplify things, you have to leave some things out, otherwise it would be too complicated. I liked the paper since it went into the quantitative and qualitative aspects of the experiment.

--------------------------------------------------------

Jacob O. Wobbrock, Andrew D. WIlson, Yang Li. Gestures without Libraries, Toolkits or Training: A $1 Recognizer for User Interface Prototypes. UIST 2007.