Mouse gestures

[Ifat Glassman]

My browser uses mouse gestures, which means that I am making a certain shape on the screen with the mouse, and my smart web browser can identify the shape and perform the required action.

What intrigues me is that it is able to identify that shape in all sizes, variations, and with a large amount of inaccuracies .

For example, the gesture to close a tab is |_ (moving the mouse down and then right).

It can also be recognized as that shape if one of the lines is substantially shorter, if the shape comes in a tiny tiny size, or all over the screen, if the line is not very straight, and it is able to identify it no matter where on the screen I am making the gesture.

Can anyone explain to me (in simple words please) how is this task of identifying a shape is accomplished?

[DavidOdden]

Can anyone explain to me (in simple words please) how is this task of identifying a shape is accomplished?

Math.

[DavidOdden]

Okay, a bit more. It's only approximate. So the can do the down and right gesture in a lot of ways, but it can't be too curvey; the up has to be fairly up and not too slanted to the left (as I tend to do). I think it comes down to some essential elements, like "straight up" is from lower y to higher y with not much change in x (perhaps 0 change in x if you rescale the coordinates, dividing by some number like 25). I found it annoyingly hard to use, but then I like command lines.

[Ifat Glassman]

Okay, a bit more. It's only approximate. So the can do the down and right gesture in a lot of ways, but it can't be too curvey; the up has to be fairly up and not too slanted to the left (as I tend to do). I think it comes down to some essential elements, like "straight up" is from lower y to higher y with not much change in x (perhaps 0 change in x if you rescale the coordinates, dividing by some number like 25). I found it annoyingly hard to use, but then I like command lines.

Thanks How nice.

I also found something about it in a site called codeproject.com

Recognition algorithm:

1) record a mouse path

2) smooth a path to a base points

3) transform points to angles' vector

4) compute sines and cosines

5) pass values (cosines and sines) to network's inputs

6) apply softmax function on an output network vector

7) find and verify a winner

I think that a "winner" means a shape that this gesture is most close to.

The recording of the gesture is done by using the right button in the mouse.

I guess that the movement of the mouse is being sampled at enough points. I'm not sure what the role of stage 4 is, though. Processing the signal by using Fourier?? And I also don't get stages 5 and 6... but eventually there is a winner... I would appreciate an explanation to stages 4-6.

[softwareNerd]

A popular Java development tool uses a simple gesture-recognition add-on from smardec. The gestures are very simple, comprising of sub-gestures that are always straight up/down/left/right (i.e. always more or less parallel to the Y-axis or the Y-axis). It works something like this:

1. The basic input is a series of mouse positions (x1, y1), (x2, y2)....(xN,yN)
   
2. For each consecutive pair -- say (x1,y1) and (x2,y2), the algorithm classifies the change as: UP, DOWN, RIGHT or LEFT. [it does this by computing (x2-x1) and (y2-y1) and then seeing which one is absolutely larger. If neither is larger enough to be significant, the second point is discarded and that move is ignored. Instead, it will compared (x1,y1) against (x3,y3).] The original series of points is thus translated into a series of changes (i.e. movements), e.g. (LEFT, LEFT, LEFT, DOWN, DOWN)
   
3. Then repeated moves are then ignored, because the scale of the move is not important to the simple gestures supported by this algorithm. So, the series above becomes, simply: (LEFT, DOWN)
   

It is easy to see how one could extend the idea by trying to detect 45-degree sub-movements (NE, SE, SW, NW). Also, once could add in some recognition of the relative size of each sub-movement. Finally, if the result is not recognized as a know gesture, the algorithm might try to compute how close it is to the known ones, and might go with a close fit.

[McGroarty]

I make video games, and have seen a number of different methods for games using mouse or stylus gestures.

The way many most games work is to normalize the path so it perfectly fits a 3x3 grid, like a Tic-Tac-Toe board. Then, look at the order that the path visits an inner portion of each division (the whole division isn't used so that diagonals don't have to cross exactly on corners). There are also some restriction as to how much the path will be scaled, so strict vertical or horizontal lines would just cover the center column or row.

Taking the above, if the divisions are numbered like this...

123

456

789

...then 456 would be a left-to-right stroke, 14789 would be an L, 2684 a clockwise O, and so on. If it's assumed that every input is a valid gesture (for example if there's a click and relese or a pen down and pen up surrounding the gesture), some extra code can be added to allow for slop, such as the O starting somewhere other than at the top, corners being visited when going from top to side, or the L being drawn from the lower-right instead of the top-left.

The above method is good because it requires very little math, and can be executed in a frame even on a processor as slow as what's in the Nintendo DS.

Handwriting systems are much more complex, and usually work with a combination of systems. The above is often used, as is a system breaking strokes down into splines and comparing them against a database of common strokes, or perhaps something like Ifat and softwareNerd found.

Edited September 1, 2006 by McGroarty