Simple gesture recognition in AS3

A few years ago I coded a simple AS2 gesture recognition package in the hope I could use it in the future. Well. 5 years have passed. No real project have ever made use of it, except a small prototype for a (successful) pitch for Nintendo… well… you know… they’ve got that little DS thing… seemd appropriate, I guess. As often though, that which have been pitched wasn’t built, and the whole gesture/drawable UI component got ditched. And now I need this thing to work again, and I’m scared to even take a look at the old AS2 base code. Well it turns out, that stuff (in this simple form) isn’t really complicated and rewriting the whole thing from scratch didn’t take long at all.

Gesture recognition, the basic kind

GestureRecognition.swf, draw the symbols

How it works

This gesture recognition method is done in three steps:

• Capture user input
• Homogenize and normalize input
• Match to a predefined pattern

The first step is trivial and won’t be discussed. The second step is best described with a diagram. I chose to use an approach relying on a line segment/circle intersection algorithm. The goal is to get a path defined by equally distanced points, scaled to fit a 1×1 square. We can obtain this by iterating through the initial path, and finding intersections with a circle of radius r. This radius is very simply determined by dividing the length of the initial path by the number of points desired in the resulting path.

Note that the simplified path is most certainly going to be shorter than the initial path as a result of the process (see the diagram). In some occasions, the final path will effectively “miss” points. In this implementation we stop as soon as there is no intersection left with the next circle. We could think of lots of complicated and/or “expensive” ways to get that done more accurately. But really, as will show the next diagram, this does not affect the recognition itself.

Processing user input

Once we have a normalized path, we can find a matching pattern in the dictionary. Comparing the data sets is now simply a matter of comparing where the points are relatively to each other within this 1×1 square.

Finding a match

Since the points are ordered (there is a first point and a last point, and the order matters) we can find the average distance between the paths. We can expect the best matching pattern to have the lower average distance between its points and the normalized user generated path, as pictured on the diagram.

Note that the implementation I propose shows no optimization whatsoever. It will bluntly go through each and every pattern in the dictionary. There is also a total lack of quality control (or threshold value) regarding the “best match”. Whatever you draw, a match will be found. I personally think it is the way it should work, but well, you can disagree and add some extra checks yourself (see in the source, there are a couple hints on where to look).

I can see two very easy ways to optimize the search though. The relative position of the first points is absolutely important. Should you draw one of these symbols backwards, matching exactly the shape, well… it’s very unlikely it’ll be the best match. We can easily extrapolate that too great of a distance between the first points should discard the pattern (let’s say something like >=.5). What is also meaningful is the length of these paths, which should be “close enough”. A very first check combining a comparison in length and relative position of first points could discard a good number of irrelevant patterns. Then… we can look for the best match in whatever remains. Writing this, I suddenly feel like implementing it. Well. I certainly will if this gets used, as I hope, in a real project. Which, yes, is still up in the air.

Useful links

Github repo (includes rough gesture creation tool)
Paul Bourke’s line/sphere intersection algorithm