Sign in to follow this  
ChrisPepper1989

Recogonising a Circular Guesture

Recommended Posts

Hi Everyone, I'm trying to detect a circular hand guesture, I would also like to differientiate between anti-clockwise and clockwise motions. With every method (e.g.) ive looked into so far the maths goes a little over my head and im wondering if anyone could help break down a simple way for me? Scenario: Im creating a little game test bed and i want a clockwise circular hand motion on the Z plane to cycle to the next weapon and an anti clockwise circular hand motion to go to the previous weapon. Data available: Im analysing I.R points in 3D space using wiimotes, the difference in the position between the ir points is added to my "guesture object". The guesture object records its position every half a second in by pushing it in the front of a deque which stores up to 25 points and then starts popping the back. Thanks for taking the time to read this post! - Chris

Share this post


Link to post
Share on other sites
frob    44920
Seems like you would need to record the change in velocity angle every time you sample. Accumulate the angle change. When the angle has gone a full circle either positive or negative, you know it has gone all the way around. If the change in angle velocity is too low for long enough, you can discard the results because they aren't in a gesture.

Share this post


Link to post
Share on other sites
Palidine    1315
Well the first problem is figuring out what part of the image the hand is. That's not easy. Consider the case where you're walking behind me or lighting conditions change or part of me is in the sun and part in shadow so my hand changes color. This stuff isn't easy.

Are you already at a point where you can recognize where the hand is as a single point? If not, you're way ahead of yourself [smile]. That seems like the hardest problem to me.

If you can already identify the hand as a single point then frob's suggestion seems like a pretty good place to start. I would say you also need ways to mark begin and end of gestures. you'd need checks for things like x frames of no or low velocity = gesture over, or x frames where the angle changes from one direction to the other = gesture over. As soon as one gesture aborts or completes you start a new gesture.

-me

Share this post


Link to post
Share on other sites
@frob Thank you for the quick reply, this seems like a good idea! i shall have a go at implementing this and let you know!

&Palidine well im already up to the point of tracking points using the wiimotes, when i say "circular hand motion" i'm really saying circular motion of an IR source which is atatched to the hand. hmm i suppose would be usefull to mark the begin and end of a guesture, this is true and i could signify this but prefrably i would like the system to be able to simply detect the guesture without being told the gesture is starting and then when its finished. Im going to try frobs suggestion and let everyone know what i got up to!

Thank you both for your quick replies

Share this post


Link to post
Share on other sites
jwezorek    2663
Was the algorithm that Frob gave good enough?

I was thinking you could project your points on a plane and then do least squares circle fitting on the planar points to find the circle closest to all the points, then you could decide if the user made a circular gesture or not based on the error. Although circle fitting is probably too slow to do in real time...

Three points determine a circle. Maybe you could randomly sample a few sets of three points from your 25 points, find the average circle from the circles the samples define, and calculate the error between all the points and the average circle?

Share this post


Link to post
Share on other sites
frob    44920
As an extra detail to what I suggested above, you'll want to make sure that there is maximum angle magnitude and a minimum sample size to prevent small wiggles from setting it off.

Share this post


Link to post
Share on other sites
ooo thanks guys, unforntunatley ive not had a chancce to try it out, shortly after putting togeether an implementation and fiddling with some other bits, i managed to break a few other things and have been wrestling with that! ill probably run another little test today and hopefully start testing the guesture stuff! I promise i will post back when i have some results! thank you guys so much for your help!

Share this post


Link to post
Share on other sites
I've implemented a simple gesture recognition system after reading an interesting article somewhere on the net. Unluckily I don't remember where I saw it, so I can't give the inventor proper credit.

The algorithm was really easy:
1. record the deltas between sample points
2. "normalize" this collection of 2D vectors into a set of known size, for example 100 vectors
2. a) this can be regarded as a 100-dimensional vector
3. do a dot product between this 100-dimensional vector and each of your well-known gesture vectors (i.e. multiply-add)
4. this gives you a measure of how closely the gesture points into the same general direction as each recorded gesture (averaged over the whole curve)
5. define some (more or less arbitrary) threshold, for example 0.7 or 0.8 and discard everything below as "not recognised"
6. choose the gesture that gives the biggest dot product, this is the one that matches best

This surprisingly simple scheme is able to detect all kinds of movements, clockwise or counter-clockwise circles, all kinds of sweeps, and even complicated zig-zag movements.

Share this post


Link to post
Share on other sites
iMalc    2466
What samoth posted is basically like what I worked with once, 10 years ago. It is very generic, able to be taught a huge range of gestures! However you might be able to do something simpler if circles are all you're interested in...

To detect a circle, you want to find a series of points whose sum-of-angles sums to either very close to 360 or very close to -360 degrees, and whose sum-of-angles-squared is minimised, and the number of points needs to be between a certain minimum and maximum. Any sharper turns inflate the sum-of-angle-squared, and by rejecting series with a sum-of-angle-squared values above a certain value, you will reject say the drawing of a rough triangle, square, pentagon, or hexagon whilst being relaxed enough to accept an octagon etc. Or perhaps rejecting a highly eliptical oval, whilst accepting a less-eliptical one.

I believe that minmising the sum-of-angles-squared is the key to detecting near circular motion, though you will need to vary your tolerance value according to the number of points. Perhaps rating each sum-of-angle-squared values against the corresponding value for an optimal circle approximation with the same number of points, e.g. perfect octagon for 8 points. You could use a precalculated table for that, or just approximate it with a function.

To find the most recent sequence of points whose angles sum to about 360 without brute forcing it, you should be able to have a cursor walk some number of points behind the realtime data, staying between some minimum and some maximum number of points behind, and moving forward somewhat sporadically over time so to try and line up with a sum of 360 or -360 degrees between itself and the most recent data point.

Share this post


Link to post
Share on other sites
Hi Everyone, thank you for all your replies,

ive been aiming towards the summing of angles methods posted by iMalc and frob but...my vector math clearly sucks as im getting no were with the summing bit.

First i thought that a dot product would do the trick:

vecAngle = acos(vec1Normalised.dotProduct(vec2Normalised)); //angle to increase by
[\source]

but that cant give me minus angles due to the fact the vectors are normalised.

I also tried something mad trig with working out the velocity and then using acos
which went something like this:

vecAngle = acos( pos1.squaredlength() / velocity.squaredlength())[\source]

and now im trying this:

vecAngle = atan2(vec1.x-vec2.x,vec1.y-vec2.y); //this one does give me minus angles, but only because the velocity is now technically the other way
[\source]

and all are not working....and now im just stabbing at ideas can anyone point me in the right direction for this?

When i say they are not working i mean they are often giving high angles even when im slowly going round, the acculation will quickly add up to 360.

here is the full code:

cicular guesture function

CircularGestureResult GuestureObject::CircularGuesture()
{

float acuumulatatedAngle = 0;
CircularGestureResult result = CircularGestureResult::NONE;;
if( mLastposistions.empty())return result;

std::deque<Ogre::Vector3>::iterator it = mLastposistions.begin();
std::deque<Ogre::Vector3>::iterator it2 = mLastposistions.begin();
++it2;
int sharpTurns = 0;


float vecAngle = 0.0f;
for(; it2 != mLastposistions.end(); ++it2,++it)
{


Ogre::Vector3 vec13D = (*it);
Ogre::Vector3 vec23D = (*it2);
Ogre::Vector2 vec1 = Ogre::Vector2(vec13D.x,vec13D.z);
Ogre::Vector2 vec2 = Ogre::Vector2(vec23D.x,vec23D.z);
Ogre::Vector2 vec1Normalised = vec1.normalisedCopy();
Ogre::Vector2 vec2Normalised = vec2.normalisedCopy();
vecAngle = 0.0f;


vecAngle = atan2(vec1.x-vec2.x,vec1.y-vec2.y);
vecAngle*=DEG; //convert to degrees;




if((vecAngle) > mTurnThreshold || (vecAngle) < -mTurnThreshold)
{
//to sharp return
sharpTurns++;

if(sharpTurns > 3)
{
SSELOG << "points cleared";
this->mLastposistions.clear();
return CircularGestureResult::NONE;
}

}
else
{

acuumulatatedAngle+=vecAngle;
}


if(acuumulatatedAngle > 360)
{
result = CircularGestureResult::CLOCKWISE;
}
else if(acuumulatatedAngle < -360)
{
result = CircularGestureResult::ANTICLOCKWISE;
}

if(acuumulatatedAngle > 360+mCicularThreshold)
{
result = CircularGestureResult::NONE;
this->mLastposistions.clear();
return result;
}
if(acuumulatatedAngle < -360-mCicularThreshold)
{
result = CircularGestureResult::NONE;
this->mLastposistions.clear();
return result;
}

}
SSELOG << "last angle added:" << vecAngle;
SSELOG << acuumulatatedAngle;
return result;
}
[\source]


update function:

GestureObjectResult GuestureObject::Update( Ogre::Vector3 trackingPos,float dT )
{

newGivenPosition = trackingPos;

Ogre::Vector3 differnce = newGivenPosition - oldGivenPosition;
if(differnce.length() > MaxChangeThreshold)
{
newGivenPosition = oldGivenPosition;
return GestureObjectResult::ThresholdExceeded; //we assume that the points have become confused
}

mPosition+=differnce;

oldGivenPosition = newGivenPosition;

mTimePassed+=(dT);
if(mTimePassed >
)
{
RecordPos(mPosition );
mTimePassed = 0.0f;
}

if(mDebugDraw)
{
Draw();
}
return GestureObjectResult::SUCCESS;
}
[\source]
recording positions:

void GuestureObject::RecordPos( Ogre::Vector3 pos )
{
this->mLastposistions.push_front(pos);

if(mLastposistions.size() > MAX_GUESTURE_STORAGE)
{

this->mLastposistions.pop_back();
}

}
[\source]

mTimeThreshold is set to 0.2 (1/5th of a second). and MAX_GUESTURE_STORAGE is 36 points.

and im running with
mCicularThreshold = 1000000.0f;
mTurnThreshold = 1000000.0f;
just so i can actually print some values of vecangle and see what im getting.

Any help will be greatly appreciated!

Share this post


Link to post
Share on other sites
iMalc    2466
You could use the Perp Dot Product, I.e. the Dot product of one of the vectors with the Perpendicular Vector of the other.
If the dot product with the perpendicular vector is positive, then the other vector points in the same direction as it, otherwise, it is negative and thus points the other way.

float dotProd = vec1.x * vec2.x + vec1.y * vec2.y;
float perpProd = -vec1.y * vec2.x + vec1.x * vec2.y;
float angle = acos(dotProd / (vec1.length() * vec2.length()) * DEG;
if (perpProd < 0)
angle = -angle;

Being a Wii owner and a developer, I too had a quick look at WiiYourself and tried to imagine something neat I could make with it, though I haven't pursued this as yet. I'd be interested to hear how it goes.

Share this post


Link to post
Share on other sites
Quote:
Original post by iMalc
You could use the Perp Dot Product, I.e. the Dot product of one of the vectors with the Perpendicular Vector of the other.
If the dot product with the perpendicular vector is positive, then the other vector points in the same direction as it, otherwise, it is negative and thus points the other way.

float dotProd = vec1.x * vec2.x + vec1.y * vec2.y;
float perpProd = -vec1.y * vec2.x + vec1.x * vec2.y;
float angle = acos(dotProd / (vec1.length() * vec2.length()) * DEG;
if (perpProd < 0)
angle = -angle;


Thank you very much, this appears to be giving me the good looking angles, some are still quite high, but im thinking this has something to do with noise or my sampling rates....

I ran into the article that i think samoth was talking about!I even tried using the normalising of sizes and cetroid stuff that is mentioned there. Although i was expecting this to put all the vectors into the range of -1 to 1 and it doesnt seem to have done that, i need to re-check the coding though.

Im now logging all my results to a nice big file....

[*i ended up going away dabling in the code for another 2 hours at this point and.....*]

I think i may have cracked it, its not perfect but i have a system that seems to be picking up clockwise and anticlockwis guestures! suffice to say im chuffed to bits at the moment hopefully this isnt some kind of 3.25am still-awake dream, if its still doing all this tommorrow i shall mark this as solved =]!

Ok as mentioned above i started logging all my numbers and stuff to a file instead of the odd ones i could afford to log to our custom console window. I also formated the out put file so it could copy and paste to an Excell file so i could really number crunch them. After looking at them and making some graphs and writing all the formulas excel style to check workings...

I started playing with the idea of measuring the angle between the directions of the points, which i think is what frob meant, but this time i played with it in excell and noticed the patterns it was making and my formulas were looking good, i applied this to my program and with a bit of tweaking i got some guestures being recognised!

I then applied the perpendicular dot product idea from iMalc to work out when to flip the angle, and i had a differenciation between clockwise and anticlockwise guestures! yey! ill post up a better explanation and some code tommorow, im rather sleepy now but i just wanted to share my tired joy with you all and say a HUGE HUGE thank you to you all for helping me out with this one!!!!!!! THANKS! =]

It doesnt spot the guestures 100% of the time probably more like 80/90%, but its not doing any false positives which makes it pretty much what i need!

Quote:

Being a Wii owner and a developer, I too had a quick look at WiiYourself and tried to imagine something neat I could make with it, though I haven't pursued this as yet. I'd be interested to hear how it goes.


Ill probably re-post my answer to this quote as i have a feeling im going to ramble....lol..but..

Playing with the wiimote and the PC is pretty fun but it can be either painless or very painfull indeed. However depending on what your idea is i may have different recommendations.

First off, if you want to make your life much easier with wiimote stuff and you don't mind C# use brian peeks original library for C# you will save yourself alot of library related headaches.

In C++ there is the choice between wiiuse (C++ version) and wii yourself l, i dabbled in both but didnt delve to deep into wiiuse, on the face of it wiiuse seemed better if you want to make a wii like game and its generally more high level, however if what you want to do is exploit the wii motes IR camera wiiyourself seems the better option as it is generally more low level. However both come with the same library headache thanks to something rather annoying set up demands due to the DDK, i talk about this and more on my http://rudematrix.co.uk/?p=322. Bascially there is an include order that you must get right which also annoyingly will conflict with the direct X SDK if you have that installed, i found building into a library solved this and you can also download those built libraries from my blog.

Personally i wanted to do head tracking and finger tracking in 3D so wiiyourself was the route i took but if i could go back in time i think i would have actually used OpenCV, and perhaps took the I.R filter off the wiimotes and still used them like a few people have, tommorrow i shall provide some links.

So it really depends on what you want to do! However if you do choose either of the wii libraries and come up against any barriers please do post a comment on my website, and i will be more then happy to help if i can, i would love to return the favour =]

Share this post


Link to post
Share on other sites
iMalc    2466
Quote:
Original post by ChrisPepper1989
Thank you very much, this appears to be giving me the good looking angles, some are still quite high, but im thinking this has something to do with noise or my sampling rates....
Yeah it could simply be noise and point quantisation.
when the vectors between the points become very short, the angles between them will start to vary rather wildly. To combat this, and hopefully increase your gesture recognition rate, you probably need to implement some smoothing algorithm.

One idea for that would be to throw out points that are too close to another point. Basically, once you accept a point, you then continue reading more points but don't accept another point until you get one that is greater than x distance away from the last point you accepted. You would probably also need to have a timeout, so that if the user holds the device relatively still, you eventually accept a point even though it was closer than the minimum distance away from the last accepted one. When this happens, they're drawing too slowly to possibly be doing your gesture anyway.
Or rather than a hard time-limit cut-off, you could just decrease the cut-off distance as a function of time since the last point was accepted.

It would be kinda fun to get some of your raw point data and test it out with my own algorithm implementations, to see if I could get a very high acceptance rate with a very low false positive rate.

Share this post


Link to post
Share on other sites
@imalc

sorry it took me so long here is some point data in an excell
file .

Those are some interesting ideas, the alogrithm does appear to be working at the moment, im going to test it out on the wiimotes very soon, unfortunatley ive started to notice some issues in getting the 3D point data, it wasnt as accurate as i thought and this is causing issues, im brushing up on how to do it, its a shame my math skills still suck! =]@imalc

sorry it took me so long here is some point data in an excell
file .

Those are some interesting ideas, the alogrithm does appear to be working at the moment, im going to test it out on the wiimotes very soon, unfortunatley ive started to notice some issues in getting the 3D point data, it wasnt as accurate as i thought and this is causing issues, im brushing up on how to do it, its a shame my math skills still suck! =]

Share this post


Link to post
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now

Sign in to follow this