k-curvature / template matching

advanced
#1

Hi everybody!

I’m doing some research on detection peaks/valleys in
contours. I’ve found two methods which are described in lots
of papers. One is template matching and the other uses the
k-curvature. (i.e. http://www.cs.toronto.edu/~smalik/downl-…-report.pdf)

Example of used vectors (as I think they are used)

Now, I’m wondering how they compute the k-curvature based on the dot-product of the vector. If I’m correct the dot product of the vector is this: sqrt(a1 * b1 + a2 * b2). Will they use the: " ||a|| ||b|| cos theta " equation to get the k-curvature?
And, I thaught the ||a|| ||b|| cos theta, equation is used to caclulate the nagle with 0,0 (x,y) ?

Someone here who can explain this a bit?

#2

when you dot product two vectors you get a scalar value. Generally it is very useful to find the projection of one vector on another.

The value of the dot product is like you mention, the multiplication of the magnitudes and the cosine of the angle between them:

  
dot = |a| |b| cos(theta)

(i.e. the projection of vector A on vector B, multiplied by the magnitude of vector B. Or vice versa, same thing).

You can also calculate the same value very quickly by summing the multiplication of the corresponding vector components:

  
dot = ax * bx + ay * by = |a| |b| cos(theta)

(There is no sqrt in calculating the dot product).

The usefulness comes in that you can use the second very quick method to calculate the dot product, and then calculate the angle between the two vectors:

  
  
dot = ax * bx + ay * by;  
theta = acos(dot / (|a| |b|);

but most of the time you don’t even need to do that (acos, sqrt are all slow).

You can simply check if the dot is bigger or smaller than zero, and that will tell you if the angle is smaller or greater than 90 degrees (i.e. they are roughly in the same direction or not):

  
  
float dot = ax * bx + ay * by;  
if(dot<0) printf("angle is > 90);  
else if(dot>0) printf("angle is <90);  
else printf("angle is 90");

So by dotting the adjacent segments you can tell if the curvature changes from >90 to <90. if you need more information, you can divide by the length of the segments to calculate the actual angle. But most of the times you can avoid that and just use the >0 check.

hope that helps!

EDIT:
If you’re going to be doing stuff like this on a contour, you’ll get better results if you blur the contour (the contour points, not the image) first (i.e. run lowpass filter). I’m sure there is a sample of this somewhere on the forum, I think theo posted it I think.

point inside 3d object
#3

Hi Memo,

Thanks alot for your clear explanation!

Do you have experience with template matching to detect fingertop? I’m curious what method is best.

Roxlu

#4

hi,

can you explain better how to get theta.

i’m not very familiar how can i make (|a| |b|).

another thing i’m using dot = ax * bx + ay * by; like you said but my dot is always positive with the contourn of a hand :s

my values came from a vector points where for example ax=points[i].x;

thank you

#5

@roxlu
I’ve never had to do that so don’t have experience with it I’m afraid. I would have thought checking the 2nd derivative of the contour would give you the peaks you need. I.e. check the change in change in direction of the segments (the 2x ‘change in’ is not a typo :wink:

this is all theoretical based on geometry and looking at the picture you’ve attached. I’ve not actually tried to find fingertips so there maybe other issues you need to workaround which I cannot foresee right now. Like I said, i’m sure there is a sample about this somewhere on the forums…

@outdoors
|a| means magnitude of the vector a. So sqrt(ax*ax + ay*ay). Or if you are using ofxVectorMath, simply a.length().
So |a| |b| simply means sqrt(ax*ax + ay*ay) * sqrt(bx*bx + by*by) or a.length()*b.length().

In the situation we are talking about above, the a and b vectors are not directly the values of the contour points, but the segments of the contour. If you look at the diagram roxlu posted and see the little segment on the pink line between the green dots, that is a contour segment, and in our case vector a. So a(x, y) = (points[i].x - points[i-1].x, points[i].y - points[i-1], y) and b(x, y) = (points[i+1].x - points[i].x, points[i+1].y - points[i].y)).

#6

hi,

thnak you for your reply.
Now i’m having another problem how to make the cross Product between two vec3f, i get always 0.0;

im tried the function cross and the function crossed, but the result is the same -> 0 in every pointfor the contourn.

Thank you

#7

hi,

sory for the double post but i solved my problem of the vectors… now i’m back with the main problem background subtraction :s

#8

Hi memo,

I’m still wondering, is the image I’ve created, a correct representation of the method used in the linked PDF to recognize the peaks/valleys. As the dot product is used to return the overlapping ‘part’ of one vector on another one, I’m trying to figure this out in relation with the peaks/valleys. As, when the dot product uses the 0,0 point in relation with the calculation of the angle, I do not understand what the relation with the peak/valley is. The lines I draw was my interpretation which seems to be ‘usefull’.

Greetings Roxlu

#9

Hi Roxlu, your illustration is close but not exactly correct. The two vectors should have a common point, e.g. in your case point J. So you draw two vectors from point J, one going backwards (to the k’th point back) and one going forwards (to the k’th point in front). K is an arbitrary number which you have to tweak and find depending on the resolution of your contour (the article uses 16). Then you can calculate theta with the equations above.

#10

Hey after successful detection of hand contour points, for detection of peaks and valleys of hand region am employing the following method. But it detects far too many spurious points in addition to peaks and valley. Can u please help …

  
 private void DetectFingers(Contour<Point> HandContour)  
        {  
            Point[] Curve = HandContour.ToArray();  
            int threshold_min = 10; // to supress noise  
            double threshold_acc_error=50,cal_error,distance,cos,theta,X=0,Y=0;  
            int kk=0;  
            Point VectorA = new Point();   
            Point VectorB = new Point();  
  
            for (int i = 0; i < Curve.Length - 1; i++) // iterate thru all points on curve  
            {  
                for (int k = 10; k<Curve.Length; k++) // iterate thru all possible k values, k total no. of points  
                {  
                    cal_error=0;  
                    for (int t = 1; t <= k - 1 && cal_error <= threshold_acc_error; t++) // for all t values find max error  
                    {  
                        if (i + k < Curve.Length && i + t < Curve.Length)  
                        distance = Math.Sqrt(Math.Pow((Curve[i + t].X - Curve[i].X) * (Curve[i + k].Y - Curve[i].Y) - (Curve[i + t].Y - Curve[i].Y) * (Curve[i + k].X - Curve[i].X), 2) / (Math.Pow(Curve[i].X - Curve[i + k].X, 2) + Math.Pow(Curve[i].Y - Curve[i + k].Y, 2)));  
                        else if (i + k >= Curve.Length && i + t < Curve.Length)  
                            distance = Math.Sqrt(Math.Pow((Curve[i + t].X - Curve[i].X) * (Curve[i + k - Curve.Length].Y - Curve[i].Y) - (Curve[i + t].Y - Curve[i].Y) * (Curve[i + k - Curve.Length].X - Curve[i].X), 2) / (Math.Pow(Curve[i].X - Curve[i + k - Curve.Length].X, 2) + Math.Pow(Curve[i].Y - Curve[i + k - Curve.Length].Y, 2)));  
                        else  
                            distance = Math.Sqrt(Math.Pow((Curve[i + t - Curve.Length].X - Curve[i].X) * (Curve[i + k - Curve.Length].Y - Curve[i].Y) - (Curve[i + t - Curve.Length].Y - Curve[i].Y) * (Curve[i + k - Curve.Length].X - Curve[i].X), 2) / (Math.Pow(Curve[i].X - Curve[i + k - Curve.Length].X, 2) + Math.Pow(Curve[i].Y - Curve[i + k - Curve.Length].Y, 2)));  
                        if(distance>cal_error) // cal error stores min distance value  
                            cal_error=distance;  
                    }  
                    if(cal_error>threshold_acc_error)  
                    {  
                        kk=k--;  
                        break;  
                    }                      
                }  
                if (i - kk > 0)  
                {  
                    VectorA.X = Curve[i].X -Curve[i - kk].X;  
                    VectorA.Y = Curve[i].Y - Curve[i - kk].Y;  
                }  
                else  
                {  
                    VectorA.X = Curve[i].X - Curve[i - kk+Curve.Length-1].X;  
                    VectorA.Y = Curve[i].Y - Curve[i - kk + Curve.Length - 1].Y;  
                }  
                if (i + kk < Curve.Length)  
                {  
                    VectorB.X = Curve[i].X - Curve[i + kk].X;  
                    VectorB.Y = Curve[i].Y - Curve[i + kk].Y;  
                }  
                else  
                {  
                    VectorB.X = Curve[i].X + Curve[i + kk-Curve.Length].X;  
                    VectorB.Y = Curve[i].Y + Curve[i + kk - Curve.Length].Y;  
                }  
                cos=VectorA.X*VectorB.X + VectorA.Y+VectorB.Y;  
                cos=cos / ( Math.Sqrt( (VectorA.X*VectorA.X)+(VectorA.Y*VectorA.Y) ) * Math.Sqrt( (VectorB.X*VectorB.X)+(VectorB.Y*VectorB.Y) ) );  
   
				if (Math.Abs(cos) < 0.15 )  
                    imgcon.Draw(new CircleF(new Point(Curve[i].X,Curve[i].Y),1), new Bgr(Color.Magenta), 2);  
            }  
              
  
        }