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

by Wobbrock, Wilson, Li

Comment
1. Manoj's blog

Summary

Gesture recognition has been the privilege of experts in pattern recognition and AI, not HCI experts. $1 recognizer facilitates incorporation the gestures into UI. It supports configurable rotation, scale, and position invariance, no feature selection or training examples.

Although toolkits like Artkit, Amulet, SATIN and libraries like Siger are powerful, they cannot help in most new prototyping environments where they are not available.

The algorithm is in 4 steps:

Step 1: , resample a points path into n (n = 64 is adequate) evenly spaced points due to variation in hardware and software sampling time.

Step 2: Rotate points so that their indicative angle (angle between centroid of gesture (x¯,y¯) and the gesture's first point) is at 0°.

Step 3: Scale points so that the resulting bounding box will be of
size*size dimension, and move the bounding box so that centroid of the gesture is at (0,0). For gestures serving as templates, Steps 1-3 should be carried out once on the raw input points. For candidates, Steps 1-4 should be used just after the candidate is articulated.

Step 4: Recognition and score. Compare candidate with templates, calculate average distance between corresponding points. The template with least path-distance to candidate is the result of recognition. Scoring can be calculated by 1 - path-distance between template and candidate / largest possible path-distance. Note that Step 2 only finds approximated best angular alignment between template and candidate, so candidate may need further rotation (only rotate in direction that renders a decrease in path-distance, and apply Golden Section Search (GSS) bounded by ±45°and a 2° threshold) to find optimal indicative angle and thus a global minimum path-distance.

Then, experiments are performed that show $1 has very good performance over DTW and Rubine's algorithm.


Discussion

This algorithm is quite useful to novices and non-specialists, at leat the steps really make sense to me. It is a geometric-based algorithm, and it is a good algorithm in terms of computational speed and no need of training examples. One thing I don't quite understand is GSS.