A Simple Algorithm for High Curvature Point Detection in 2D Graph

Introduction:

A new algorithm is proposed to detect corners and high curvature points in a 2D graph. A corner is defined as a location where a triangle with specified opening angle and size can be inscribed in the curve. Detecting a corner in a 2D graph is related to detecting corners in a gray scale image.

Applications:

This algorithm is developed to be used in shape analysis problems. It cans measure important features in a graph like: number of corners, number of lines and the slope of lines. All of these features can be measured from the output of this algorithm. These features can be used in a pattern recognition technique to classify a given graph.

Technique:

We have a set of points belongs to a curve some internal points and two end points. We will follow a path from one end point to the second end point. We will start from one of the end points of the curve (figure 1).

In each step we will add a point to a list Q. PF: is the first point in the set Q. PL: is the last point of the set Q.PM is the middle point of the set Q. Also two lines will be defined L1 and L2. L1: is the line connecting the PF and PM. L2: is the line connecting the PM and PL. The angle between the two lines L1 and L2 called N. (figure 2)


We continue adding points to L and calculate the angle N until the angle is more than the threshold value T. If N is higher than T, then there is a corner in the set Q initially the corner is PM. (figure 3)

To make our choice more accurate, define two angles NL and NR. The angle NL is the angle between the left neighbor of PM, PF and PL. the angle NR is the angle between the right neighbor of PM, PF and PM. If the value of NL greater than the value of NR and the value of N we will continue moving to the left direction. If the value of NR is greater than N and greater than or equal NL then move to right direction. Keep move to the next point in the specified direction until the angle between the new point, PF and PL is less than the previous angle or the current point is PL. So the corner will be the previous point. (figure 4)


Algorithm:

PF= start_point

Q={PF};

FOREAH (point p in Points)

{

PL=p;

Add p to q;

PM= mid point of Q;

N=angle(PF,PM,PL);

If(N>threshold)

{

corner=PM;

NL=angle(PF,Q[PM_index-1],PL);

NR=angle(PF,Q[PM_index+1],PL);

IF(NL>N&&NL>NR)

Step=-1;

ELSE if(NR>N&&NR>=NL)

Step=1;

Else

Return corner;

Index=PM_index+step;

Max=0;

While(index within Q range)

{

A=angle(PF,Q[index],PL);

If(A>Max)

{

Max=A;

Courner=Q[index];

}

Else

Return max

}

Return max

}

}

Results:

The set of shapes used to test the algorithm listed in (figure 5).

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: