Thread: Find corners in array of points

Do you have some pictures?
Apart from the 4 points which make up the corners, how are the rest of the points distributed?

I think by bent he means bulging sides, though he does mention that the corners aren't right angles (a la diamond, parallelogram). Googling "corner detection" came up with a handful of algorithms, most of which look somewhat complex, and are geared toward image processing, not dealing simply with points.

Is your array of points "in order". That is, are they in the order you would encounter them if you walked around the shape? If so, you could walk around the image, looking at the angle from the previous point to the current point, and from the current point to the next point. If the difference between those two angles is more than some threshold (say 15 degrees)*, you have yourself a corner. Depending on the closeness of your points, and what they're measured in, you may need to use points farther from your current point, like say 10 spaces back and 10 spaces forward. It's crude, but might work for your purposes.

* EDIT: The threshold really should check if you're more than X degrees from a straight line, i.e. for a 15 degree threshold, the difference should be less than 165 degrees, or more than 195. Also, there may be some slicker way to get the angle between those 3 points, but I'm not feeling like digging up any of my trig knowledge right now.

Ok.. Here is what I came up with:

First I'll explain the opencv specific variables:
CvSeq = A struct containing my contour, from which i can extract CvPoint objects
CvPoint = A struct containing int x and int y

Prototype of function for extracting CvPoints from CvSeq:
CVAPI(schar*) cvGetSeqElem( const CvSeq* seq, int index );

Here is my function:

Code:

CvPoint *findCorners( CvSeq *contour, int max_corners, int min_angle, int min_distance )
{
    CvPoint *ret = malloc( sizeof( CvPoint ) * max_corners );
    CvPoint *p1, *p2, *p3;
    double prevAngle = 0;
    double distance = 0;

    int cc = 0;

    for( int i = 0; i < (contour->total + 3); i++ )
    {
        if( i > 2 )
        {
            if( i - contour->total < 0 ) //Handle the overlapping steps of the loop
            {
                p1 = (CvPoint *)cvGetSeqElem( contour, i - 2 );
                p2 = (CvPoint *)cvGetSeqElem( contour, i - 1 );
                p3 = (CvPoint *)cvGetSeqElem( contour, i );
            }
            else if( i - contour->total == 0 )
            {
                p1 = (CvPoint *)cvGetSeqElem( contour, i - 2 );
                p2 = (CvPoint *)cvGetSeqElem( contour, i - 1 );
                p3 = (CvPoint *)cvGetSeqElem( contour, 0 );
            }
            else if( i - contour->total == 1 )
            {
                p1 = (CvPoint *)cvGetSeqElem( contour, i - 2 );
                p2 = (CvPoint *)cvGetSeqElem( contour, 0 );
                p3 = (CvPoint *)cvGetSeqElem( contour, 1 );
            }
            else
            {
                p1 = (CvPoint *)cvGetSeqElem( contour, i - contour->total - 2 );
                p2 = (CvPoint *)cvGetSeqElem( contour, i - contour->total - 1 );
                p3 = (CvPoint *)cvGetSeqElem( contour, i - contour->total );
            }

            //Calculate angle between points 1 and 3
            double currAngle = atan2( p1->y - p3->y, p1->x - p3->x ) * 180 / PI;
            if( currAngle < 0 )
                currAngle = (currAngle * -1);

            if( i > 3 )
            {
                //calculate the difference between this angle and the previous one
                double diffAngle = prevAngle - currAngle;

                if( diffAngle < 0 ) //Make sure sign is positive
                    diffAngle = (diffAngle * -1);


                //Add point to return array if angle diff is above threshold
                if( diffAngle > min_angle )
                {
                    //Ignore points that are closer than "min_distance pixels" to the previous point
                    if( cc > 0 )
                    {
                        double dx;
                        if(p1->x > ret[cc - 1].x)
                            dx = (double)(p1->x - ret[cc - 1].x);
                        else
                            dx = (double)(ret[cc - 1].x - p1->x);

                        double dy;
                        if(p1->y > ret[cc - 1].y)
                            dy = p1->y - ret[cc - 1].y;
                        else
                            dy = ret[cc - 1].y - p1->y;

                        distance = sqrtf( (dx * dx) + (dy * dy) );

                        if( distance >= min_distance )
                        {
                            ret[cc] = *p1;
                            cc++;
                        }
                    }
                    else
                    {
                        ret[cc] = *p1;
                        cc++;
                    }

                    if( cc > max_corners )
                        break;

                }
            }

            prevAngle = currAngle;
        }

    }
    
    if( cc < max_corners )
        fprintf( stderr, "Find corners: found %d of %d corners\n", cc, max_corners );
        
    return ret;
}

I would appreciate any feedback on this function. Not only on its functionality, but also general mistakes or bad behaviors in my coding.

Thanks

//John

Code:

double currAngle = atan2( p1->y - p3->y, p1->x - p3->x ) * 180 / PI;
            if( currAngle < 0 )
                currAngle = (currAngle * -1);

1. It's a bit odd to scale the angles to degrees instead of radians. When dealing with angles, you usually will eventually feed that angle back into a trig function, and those functions want angles in radians.
2. Negating the angle is incorrect -- this produces a mirror of the true angle. You just want to add 2*Pi to it. EDIT: Ahh, you're just trying to get the size of the angle, not its correct sign. Guess you're okay then.