# How can one classify (match within a certain confidence interval) gestures based on accelerometer readings?

I am using an accelerometer-enabled device (mobile phone, to be specific) that enables sampling acceleration at a rate of about 20 samples per second. The samples contain three values, each corresponding to the X, Y and Z component of the measured acceleration as perceived by the device.

I've built a system where I have logged several gestures (as a time-dependent series of samples, $f(t)$) as examples that I'd like to match against input on the device to classify gestures and execute actions based on recognized gestures.

Ideally, I'd like the evaluation to take place on the device, but given the low computational capacity and the need for near-realtime evaluation, the algorithm would need to be pretty efficient.

How do I approach such a classification problem?

Addendum: An additional problem I've thought of is that the signal could be located anywhere in the stream, eg. the gesture could start and end at any time during capture. Would I use a sliding window and do a compare each time a new sample comes in, truncating off the start of the stream?

Addendum 2: It seems someone's already been tackling this problem using FFTs and SVM. Does anyone have a good explanation and/or pointers as to the implementation of this method and its feasibility for real-time recognition?

-

This sounds like an ideal problem for a neural network.

You should create a training set of examples $(x_i, y_i)$ where each $y_i$ corresponds to one of your gestures, and the $x_i$ is a vector of your measurements (i.e. the time series of $x$, $y$ and $z$ accelerations unpacked into a vector).

If you have $p$ different gestures, then your neural network will output $p$ numbers, which are the probabilities that the gesture performed by the user is each of the $p$ possible gestures. You simply select the gesture with the highest output value.

Once you have fit a network to the training data, it will be very fast to evaluate which gesture has performed: the computations taking place inside a neural network are nothing more than addition, multiplication, division and exponentation.

The tricky part will be fitting the neural network. If you can get your data into an easily accessible format (e.g. a CSV) then you could import it into R and use one of the many excellent neural network packages to get the coefficients that you can then hard-code into your application.

-
While I do understand the principle of training the neural network (and using the resulting trained network to evaluate and classify on the client-side), how would I fit an indetereminately long sample into a fixed-size vector (gestures can be of varying speed and length)? From what I understand, I'd need to squash or stretch the data to fit the input vector? –  Krof Drakula Nov 2 '11 at 18:47
Chris, what training data would you have to use? If you record making the gesture a handful of times, do you also have to record gestures that are similar but wrong? –  Jim Nov 2 '11 at 19:15
@Jim: I'd assume I'd have to record invalid or noisy gestures and add them to an "uncategorized" bucket to strengthen the training samples further. Other than that, I'd love more elaboration on this idea. –  Krof Drakula Nov 2 '11 at 19:23
You shouldn't need to record any deliberately bad data. Your network has one output for each gesture, and it returns a number between 0 and 1 which, roughly, gives the probability that the user's gesture represents each of the recognizable gestures. Ideally, at this stage one of the gestures has a score significantly greater than 0.5 and the others are significantly less than 0.5 - in that case the interpretation is unambiguous. In the case that all of the results are less than 0.5, you could return a 'None' result indicating that none of the gestures were matched. –  Chris Taylor Nov 2 '11 at 22:47
As regards the input data - yes, you would probably need to map the time series to a fixed-size vector in order for a neural network to properly interpret it. This might be desirable, though - presumably different people will perform the gestures at different speeds, and mapping each input to a fixed-size vector at least gets rid of this ambiguity. –  Chris Taylor Nov 2 '11 at 22:48