Efficient Gesture Recognition and Corner Finding in AS3
July 21, 2009
Gesture recognition and corner finding are two techniques that can be useful for all sorts of things. For example, gesture recognition can be used to recognise shapes in graphics applications, to control the user interface on a mobile device or to build creative games. In this context, I’m referring to shapes drawn with an input device that may or may not leave an ink trail on the screen, and not to physical gestures, such as waving a hand (however, most of the time a drawn shape also implies a physical gesture). Corner finding is a technique that finds all corner points of an arbitrary stroke and can be used for shape simplification, node finding or another exciting field, which I’m going to reveal later this year… ;)
While gesture recognition and corner finding are not necessarily related to each other, they are both concerned with the processing and recognition of lines and can be utilised to create interesting forms of human-computer interfaces. Furthermore, both approaches have in common that extensive research has been carried out and new algorithms have been continuously developed. Some of those algorithms are quite complex to implement and require advanced mathematics…
The »$1 Gesture Recognizer« (Wobbrock et al. 2007) and the »ShortStraw« Corner Finder (Wolin et al. 2008) are two very efficient algorithms that are straightforward to implement, i.e. using only basic mathematics and trigonometry, and (despite of or because of their simplicity) outperform most other approaches. The »$1 Gesture Recognizer« is a template-based recognition algorithm that matches a gesture against one or more stored templates, which is the preferred method for many use cases since it requires no training period by the user (such as in Rubine’s algorithm, for example). The gestures are also rotation, position and scale invariant, meaning that a gesture will be recognised even if it’s drawn with a different rotation, position or scale than that of the stored template. However, the algorithm can be easily modified to disable those features if, for instance, a recogniser is needed that also takes the rotation of drawn shapes into account.
»ShortStraw« is a corner finding algorithm for polylines that returns all corner points for the input points of any free-form stroke by calculating and comparing »straw distances«.
If you want to know more about how exactly they work, you can read the papers about the »$1 Gesture Recognizer« and »ShortStraw« (btw, this also fits nicely into my new series of blog posts about relevant academic papers).
I’ve implemented both algorithms in ActionScript 3 and put together a simple Flex based demo application for testing (as for the »$1 Gesture Recognizer«, there are some versions for different languages available but I’ve implemented it from scratch as I wanted to understand the approach. For ShortStraw I couldn’t find any source code). You can view the demo and download all source code at the end of the article. The main classes for $1 can be found in
de.betriebsraum.gestures.recognizer.* and for ShortStraw in
DollarRecognizer class has some convenience methods to add and remove
DollarTemplates and the main
recognize() method, which accepts an array of points and returns an instance of
DollarResult with the id and score of the best match.
ShortStraw has two public static methods:
getCornerIndices() and a convenience method
getCornerPoints(), which both accept an array of input points.
getCornerIndices() returns the array indices of all found corners in the source array and
getCornerPoints() returns an array of new points. It’s also noteworthy that there are a lot of other handy methods in the classes, for example to resample points or calculate the median, so have a look at them too…
Please note that I haven’t explicitly tuned the implementations to squeeze out the last bit of performance with various AS3 optimisation tricks and hacks as they perform quite well for me.
Here’s the demo (you can view and download the full source code by right-clicking and selecting “View Source” in the demo).