[Windows Mobile Development and Hacking General] mr_deimos:
I recently saw this tread:

http://xdaforums.com/showthread.php?t=370632

i liked the idea, and when i thought about it, gesture recognition didn't seem to hard. And guess what - it really wasn't hard :D

I made a simple application recognizing gestures defined in an external configuration file. It was supposed to be a gesture launcher, but i didn't find out how to launch an app from a winCE program yet. Also, it turned out to be a bit to slow for that because of the way i draw gesture trails - i'd have to rewrite it almost from scratch to make it really useful and i don't have time for that now.

So i decided to share the idea and the source code, just to demonstrate how easy it is to include gesture recognition in your software.

My demo app is written in C, using XFlib for graphics and compiled using CeGCC so you'll need both of them to compile it (download and install instructions are on the Xflib homepage: www.xflib.net)

The demo program is just an exe file - extract it anywhere on your device, no installation needed. You'll also need to extract the gestureConfig.ini to the root directory of your device, or the program won't run.

Try some of the gestures defined in the ini (like 'M' letter - 8392, a rectangle - 6248, a triangle - 934), or define some of your own to see how the recognition works. Make sure that you have a string consisting of numbers, then space of a tabulator (or more of them) and some text - anything will do, just make sure that there's more than just the numbers in each line. Below you can set the side sensitivity to tweak recognition (see the rest of the post for description on how it works). Better leave the other parameter as it is - seems to work best with this value.

Now, what the demo app does:

It recognizes direction of drawn strokes, and prints them on the bottom of the screen as a string of numbers representing them (described bellow). If a drawn gesture matches one of the patterns in the config file, the entire drawn gesture gets highlited. It works the best with stylus, but is usable with finger as well.

Clicking the large rectangle closes the app.

And how it does it:

The algorithm i used is capable of recognizing strokes drawn in eight directions - horizontally, vertically and diagonally. Directions are described with numbers from 1 to 9, arranged like on a PC numerical keyboard:

7 8 9
4 6
1 2 3

So a gesture defined in config as 6248 is right-down-left-up - a ractangle.

All that is needed to do the gesture recognition is last few positions of the stylus. In my program i recorded the entire path for drawing if, but used only 5 last positions. The entire trick is to determine which way the stylus is moving, and if it moves one way long enough, store this direction as a stroke.

The easiest way would be to subtract previous stylus position from current one, like

vectorX=stylusX[i]-stylusX[i-1];
vectorY=stylusY[i]-stylusY[i-1];
[code]
But this method would be highly inaccurate due to niose generated by some digitizers, especially with screen protectors, or when using a finger (try drawing a straight line with your finger in some drawing program)
That's why i decided to calculate an average vector instead:
[code]
averageVectorX=((stylusHistoryX[n]-stylusHistoryX[n-5])+
(stylusHistoryX[n-1]-stylusHistoryX[n-5])
(stylusHistoryX[n-2]-stylusHistoryX[n-5])
(stylusHistoryX[n-3]-stylusHistoryX[n-5])
(stylusHistoryX[n-4]-stylusHistoryX[n-5]))/5;
//Y coordinate is calculated the same way

where stylusHistoryX[n] is the current X position of stylus, and stylusHistoryX[n-1] is the previous position, etc.

Such averaging filters out the noise, without sacrificing too much responsiveness, and uses only a small number of samples. It also has another useful effect - when the stylus changes movement direction, the vector gets shorter.

Now, that we have the direction of motion, we'll have to check how fast the stylus is moving (how long the vector is):

if(sqrt(averageVectorX*averageVectorX+averageVectorY*averageVectorY)>25)
(...)

If the vector is long enough, we'll have to determine which direction it's facing. Since usually horizontal and vertical lines are easier to draw than diagonal, it's nice to be able to adjust the angle at which the line is considered diagonal or vertical. I used the sideSensitivity parameter for that (can be set in the ini file - range its is from 0 to 100). See the attached image to see how it works.

The green area on the images is the angle where the vector is considered horizontal or vertical. Blue means angles where the vector is considered diagonal. sideSensitivity for those pictures are: left one - 10, middle - 42 (default value, works fine for me ;) ), right - 90. Using o or 100 would mean that horizontal or vertical stroke would be almost impossible to draw.

to make this parameter useful, there are some calculations needed:

sideSensitivity=tan((sideSensitivity*45/100)*M_PI/180);

First, the range of the parameter is changed from (0-100) to (0-22), meaning angle in degrees of the line dividing right section (green) and top-right (blue). hat angle is then converted to radians, and tangent of this angle (in radians) is being calculated, giving slope of this line.

Having the slope, it's easy to check if the vector is turned sideways or diagonal. here's a part of source code that does the check, it is executed only if the vector is long enough (condition written above):

if( abs(averageVectorY)<sideSensitivity*abs(averageVectorX) ||
abs(averageVectorX)<sideSensitivity*abs(averageVectorY))	//Vector is turned sideways (horizontal or vertical)
{
/*Now that we know that it's facing sideways, we'll check which side it's actually facing*/
if( abs(averageVectorY)<sideSensitivity*averageVectorX) //Right Gesture
gestureStroke='6'; //storing the direction of vector for later processing

if( abs(averageVectorY)<sideSensitivity*(-averageVectorX)) //Left Gesture
gestureStroke='4';

if( abs(averageVectorX)<sideSensitivity*(averageVectorY)) //Down gesture
gestureStroke='2';

if( abs(averageVectorX)<sideSensitivity*(-averageVectorY)) //Up gesture
gestureStroke='8';
}
else
{ //Vector is diagonal
/*If the vector is not facing isdeways, then it's diagonal. Checking which way it's actually facing
and storing it for later use*/
if(averageVectorX>0 && averageVectorY>0) //Down-Right gesture
gestureStroke='3';

if(averageVectorX>0 && averageVectorY<0) //Up-Right gesture
gestureStroke='9';

if(averageVectorX<0 && averageVectorY>0) //Down-Left gesture
gestureStroke='1';

if(averageVectorX<0 && averageVectorY<0) //Up-Left gesture
gestureStroke='7';
}

Now, we have a character (i used char type, so i can use character strings for string gestures - they can be easily loaded from file and compared with strcmp() ) telling which way the stylus is moving. To avoid errors, we'll have to make sure that the stylus moves in the same direction for a few cycles before storing it as a gesture stroke by increasing a counter as long as it keeps moving in one direction, and resetting it if it changes the direction. If the counter value is bigger than some threshold (pathSensitivity variable is used as this threshold in my program), we can store the gestureStroke value into a string, but only if it's different from previous one - who needs a gesture like "44444" when dragging the stylus left?

After the stylus is released, you'll have to compare generated gesture string to some patterns (eg. loaded from a configuration file), and if it matches, do an appropriate acton.

See the source if you want to see how it can be done, this post already is quite long :)

If you have any questions, post them and i'll do my best to answer.

Feel free to use this method, parts of, or the entire source in your apps. I'm really looking forward to seeing some gesture-enabled programs :)