b-log – betriebsraum weblog

Software Development, Human-Computer Interaction, Projects…

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 de.betriebsraum.geom.cornerfinder.ShortStraw.
The 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).

$1 Gesture Recognizer & ShortStraw Demo

$1 Gesture Recognizer & ShortStraw Demo (click on the image)

Filed under: Flex/AS3, HCI, RIA

7 Responses to “Efficient Gesture Recognition and Corner Finding in AS3”

  1. […] petit article sur la reconnaissance des gestes en As3 et une petite […]

  2. alex says:

    great app! works really good.

  3. Og2t says:

    Good to see you blogging again Felix! Amazing post, I will try the corner finder with my face tracking experiment. Keep Flashin’!

  4. jrg says:

    fascinating subject, thanks for this!

  5. Flo says:

    Hi, thanks for sharing!
    Really efficient… You rock!

  6. Simon says:

    Great little app. I love it!

  7. Joshua Koo says:

    Hi Felix,

    Thank you for the recommendation of these 2 papers, (it sparked some interest of reading papers in me) and the great AS3 implementation.

    I’ve ported the shortstraw implementation for Javascript, and it works pretty well too, and I’ll try to post the js implementation on my site shortly.

    Glad to have found your blog!

    Joshua

Add a comment

You must be logged in to post a comment.