Not logged in, Join Here! or Log In Below:  
 
News Articles Search    
 

 Home / General Programming / Recognizing patterns in mouse input Account Manager
 
Archive Notice: This thread is old and no longer active. It is here for reference purposes. This thread was created on an older version of the flipcode forums, before the site closed in 2005. Please keep that in mind as you view this thread, as many of the topics and opinions may be outdated.
 
Corre

May 18, 2005, 07:09 AM

I've been thinking about a specific control mechanism for a game idea I have.

For this, I would like to be able to recognize shapes that the user "draws" with the mouse... for example, if the player moves the mouse in a crude circle, it would be classified as "circle", but the program should be clever enough to distinguish this from a C or a U shape. The system would need to be fairly robust, being able to recognize shapes that similar to the desired shapes, not just those that are a perfect match.

Anyone know of any sources on the internet for this, or does anyone have any ideas on how to start doing something like this?

Thanks

 
pauljan

May 18, 2005, 07:15 AM

A good term to search on is 'mouse gestures'. The following article is a nice place to get started http://www.codeproject.com/cpp/gestureapp.asp

Hope that helps...

 
sylphaleya

May 18, 2005, 07:55 AM

An outline of my algorithm that works well:

- Record all mouse positions while you drag the mouse
- Calculate a 2D ABB
- Convert all coordinates into a given range (e.g. -1.0 ... 1.0). Use the 2D AABB for this.
- Calculate the length of your gesture (sum of dx^2 + dy^2)
- Try to create a gesture that contains a fixed number of coordinates. Insert and delete coordinates while you follow your gesture. Use linear interpolation for simplicity. (Length of a segment is based on the gesture length)
- Draw the perfect gesture once and save the resulting coordinate set.
- Whenever the user paints a new gesture on your screen compare the coordinates with all of your templates (sum of dx^2 + dy^2) after normalization (step 1 - 5)

Hope that helps

 
Victor Widell

May 18, 2005, 10:07 AM

"sum of dx^2 + dy^2"

How will this distinguish different shapes? Wouldn't a circle and an 8 give about the same result? (or any 2 horizontal lines?)

 
Corre

May 19, 2005, 01:40 AM

Hmm, I think he means that you "normalize" the captured data into a set of evenly distributed normalized points, same number of points as in your similarly normalized template data. Then you calculate the distance of each point in your captured data to each corresponding point in your template data and sum these distances. The template from which it deviates the least would be the matching one....

Thanks all for your replies, it gets me somewhere to start!

 
Rhinoid

May 19, 2005, 05:11 AM

My initial hunch would be to NOT compare real coordinates with eachother but to convert the input into angles and forward momentum. (Just like the good old "turtle language" (move forward, rotate right 10degrees, move forward, etc))

So wherever you start to draw, you start with angle 0. Then if you draw forward you're still at angle 0. If you draw an arc slightly clockwise, the angle starts incrementing. So you end up with a data set of angles instead of real coordinates.

This way it doesn't matter if the user draws the gesture slightly rotated, or squashed or otherwise misformed, since the data will be roughly the same. If you would compare with real coordinates it is really difficult to still recognize these gestures.

 
adel

May 22, 2005, 05:21 PM

Try recording the user's input as a set of control points that constitute a curve. For example, add a control point for every n pixels that the user moves, then compare these control points to the control points of whatever shape you have in mind. Of course, you might want to create a bounding shape for the curve then scale the curve for easier comparison. I'm not sure how good this info is, bu that's how I would try to do it.

 
bscalp

May 22, 2005, 07:38 PM

http://www.dtc.umn.edu/~ashesh/papers/rubine-reference%20from%20sketch.pdf

This PDF explains a method rather similar to the one sylphaleya described. The author uses more 'features' describing the gesture, and a statistical approach to match user input to a gesture class.

 
pistachioed

May 23, 2005, 03:01 PM

As part of the project I’m working on, I had to develop a system that recognizes and assesses the quality of a small number of shapes drawn with the mouse.

By choosing only shapes that could be easily defined mathematically, I was able to quickly code the recognition logic for each of them as special cases.

First, I convert the mouse gesture into a set of evenly spaced points. Then I figure out how well the points match all of the possible shapes using special case logic, and return that shape that fits best.

Here are some outlines of the algorithms I used:

Circle:
* Calculate the average position of all the points and treat that as the center.
* Calculate the average distance each point is away from the center and treat that as the radius.
* Calculate the standard deviation of the distance of each point against the average distance.
* Normalize the standard deviation against the average distance, and return that as the quality.
One potential problem with this algorithm is that multiple identical circles drawn on top of each other will receive a high quality rating. To prevent this, you could figure out the circumference of the circle the user is trying to make and compare it against the number of points in the data set over the sampling rate. If the two values were approximately equal, you’d know you had a single circle.

Line:
* Just run a linear regression on the points and return the R squared value (make sure your regression tests for actual distances from the line, not just vertical distances).

Triangles, Quadrangles, etc.:
* Detect corners. I use a system where I basically go through each sample and compute the dot product between the vector pointing at the current sample from the previous one, and the vector pointing from the current sample at the next. If the dot product is low, that means the angle between the vectors is sharp, which means the sample is a corner.
* The number of corners determines what kind of polygon you’re looking for (3=triangle, 4=quadrangle, etc.).
* Finally, perform linear regressions on all of the lines between the corners. Return the average of the R squared values.
Depending on what you’re going for, you may want to make sure that none of the lines between corners intersect before returning a high quality value.

5-Sided Star:
* Perform the above test for a pentagon.
* The lines forming a star intersect in a certain way. Return the pentagon quality value if the lines forming the user-input shape intersect in that way. Return 0 otherwise.

I also did one for a spiral, but you get the idea.

The nice thing about this system is that it can recognize and differentiate the shapes pretty well, even if they are rotated are skewed. The big (potentially fatal) disadvantage is that all the shapes you use have to be procedurally defined, which limits the types of shapes you can recognize, and costs a non-trivial amount of time for each shape you add.

 
pocketmoon

May 23, 2005, 05:26 PM

The fantastic "Blank and White" from Lionhead used mouse gestures to cast spells etc.

I always though that gesture driven shortcuts would be a great idea for IDE's etc.

e.g. a big C to compile and S to save :)

 
timm

May 23, 2005, 05:59 PM

SUPPORT VECTOR MACHINE

 
 
Victor Widell

May 24, 2005, 12:03 PM

Actually, gestures as shortcuts sounds great. (With a confirmation of course, since gestures can be mis-interpreted.)

A bit like transforms in Blender.

 
This thread contains 13 messages.
 
 
Hosting by Solid Eight Studios, maker of PhotoTangler Collage Maker.