SURF-based Image Recognition

Here are the steps :

1. Compute the gray-scale and calculate the SURF features from the model image

2. Turn on the camera and get the real-time input image. Convert each frame to gray-scale

3. Compute the SURF features of the gray-scale camera frame

4. At this step, we want to compare between “model image” and “input image” (camera frame).
For all features of the model, for all features of the camera frame, determine if they represent the same point (calculation of their distance and thresholding) ;

5. Once we have obtained the pairs of associated points, we determine the homography matching all these pairs (using RANSAC or least median squares algorithm) ;

6. Drawing of the projection of the input frame in the illustration frame using this homography.

reference : http://wn.com/realtime_sift_tracking

Application in outdoor visual navigation:

SIFT implementation in OpenCV 2.4


/*
 * A Demo to OpenCV Implementation of SURF
 * Further Information Refer to "SURF: Speed-Up Robust Feature"
 * Author: Liu Liu
 * liuliu.1987+opencv@gmail.com
 */

#include <cv.h>
#include <highgui.h>
#include <ctype.h>
#include <stdio.h>
#include <stdlib.h>

#include <iostream>
#include <vector>

using namespace std;

IplImage *image = 0;

double
compareSURFDescriptors( const float* d1, const float* d2, double best, int length )
{
    double total_cost = 0;
    assert( length % 4 == 0 );
    for( int i = 0; i < length; i += 4 )
    {
        double t0 = d1[i] - d2[i];
        double t1 = d1[i+1] - d2[i+1];
        double t2 = d1[i+2] - d2[i+2];
        double t3 = d1[i+3] - d2[i+3];
        total_cost += t0*t0 + t1*t1 + t2*t2 + t3*t3;
        if( total_cost > best )
            break;
    }
    return total_cost;
}

int
naiveNearestNeighbor( const float* vec, int laplacian,
                      const CvSeq* model_keypoints,
                      const CvSeq* model_descriptors )
{
    int length = (int)(model_descriptors->elem_size/sizeof(float));
    int i, neighbor = -1;
    double d, dist1 = 1e6, dist2 = 1e6;
    CvSeqReader reader, kreader;
    cvStartReadSeq( model_keypoints, &kreader, 0 );
    cvStartReadSeq( model_descriptors, &reader, 0 );

    for( i = 0; i < model_descriptors->total; i++ )
    {
        const CvSURFPoint* kp = (const CvSURFPoint*)kreader.ptr;
        const float* mvec = (const float*)reader.ptr;
        CV_NEXT_SEQ_ELEM( kreader.seq->elem_size, kreader );
        CV_NEXT_SEQ_ELEM( reader.seq->elem_size, reader );
        if( laplacian != kp->laplacian )
            continue;
        d = compareSURFDescriptors( vec, mvec, dist2, length );
        if( d < dist1 )
        {
            dist2 = dist1;
            dist1 = d;
            neighbor = i;
        }
        else if ( d < dist2 )
            dist2 = d;
    }
    if ( dist1 < 0.6*dist2 )
        return neighbor;
    return -1;
}

void
findPairs( const CvSeq* objectKeypoints, const CvSeq* objectDescriptors,
           const CvSeq* imageKeypoints, const CvSeq* imageDescriptors, vector<int>& ptpairs )
{
    int i;
    CvSeqReader reader, kreader;
    cvStartReadSeq( objectKeypoints, &kreader );
    cvStartReadSeq( objectDescriptors, &reader );
    ptpairs.clear();

    for( i = 0; i < objectDescriptors->total; i++ )
    {
        const CvSURFPoint* kp = (const CvSURFPoint*)kreader.ptr;
        const float* descriptor = (const float*)reader.ptr;
        CV_NEXT_SEQ_ELEM( kreader.seq->elem_size, kreader );
        CV_NEXT_SEQ_ELEM( reader.seq->elem_size, reader );
        int nearest_neighbor = naiveNearestNeighbor( descriptor, kp->laplacian, imageKeypoints, imageDescriptors );
        if( nearest_neighbor >= 0 )
        {
            ptpairs.push_back(i);
            ptpairs.push_back(nearest_neighbor);
        }
    }
}

/* a rough implementation for object location */
int
locatePlanarObject( const CvSeq* objectKeypoints, const CvSeq* objectDescriptors,
                    const CvSeq* imageKeypoints, const CvSeq* imageDescriptors,
                    const CvPoint src_corners[4], CvPoint dst_corners[4] )
{
    double h[9];
    CvMat _h = cvMat(3, 3, CV_64F, h);
    vector<int> ptpairs;
    vector<CvPoint2D32f> pt1, pt2;
    CvMat _pt1, _pt2;
    int i, n;

    findPairs( objectKeypoints, objectDescriptors, imageKeypoints, imageDescriptors, ptpairs );
    n = ptpairs.size()/2;
    if( n < 4 )
        return 0;

    pt1.resize(n);
    pt2.resize(n);
    for( i = 0; i < n; i++ )
    {
        pt1[i] = ((CvSURFPoint*)cvGetSeqElem(objectKeypoints,ptpairs[i*2]))->pt;
        pt2[i] = ((CvSURFPoint*)cvGetSeqElem(imageKeypoints,ptpairs[i*2+1]))->pt;
    }

    _pt1 = cvMat(1, n, CV_32FC2, &pt1[0] );
    _pt2 = cvMat(1, n, CV_32FC2, &pt2[0] );
    if( !cvFindHomography( &_pt1, &_pt2, &_h, CV_RANSAC, 5 ))
        return 0;

    for( i = 0; i < 4; i++ )
    {
        double x = src_corners[i].x, y = src_corners[i].y;
        double Z = 1./(h[6]*x + h[7]*y + h[8]);
        double X = (h[0]*x + h[1]*y + h[2])*Z;
        double Y = (h[3]*x + h[4]*y + h[5])*Z;
        dst_corners[i] = cvPoint(cvRound(X), cvRound(Y));
    }

    return 1;
}

int main(void)
{
	//template image to be recognized
        const char* object_filename = "C:/images/image2.png";

	// Initialize capture device
	CvCapture* capture = cvCaptureFromCAM( CV_CAP_ANY );
	if(!capture) printf("No Capture");

    CvMemStorage* storage = cvCreateMemStorage(0);

    cvNamedWindow("Template", 1);
	cvNamedWindow("Matching Display", 1);

    static CvScalar colors[] =
    {
        {{0,0,255}}, //0=red
        {{0,128,255}},
        {{0,255,255}},
        {{0,255,0}}, //3=green
        {{255,128,0}},
        {{255,255,0}},
        {{255,0,0}},
        {{255,0,255}},
        {{255,255,255}}
    };

    IplImage* object = cvLoadImage( object_filename, CV_LOAD_IMAGE_GRAYSCALE );
    IplImage* image = NULL, *image_layer=NULL/*, *image_layer2*/;
	IplImage* image_color = NULL;

	while(1){
		image = cvQueryFrame(capture);
		image_layer = cvCreateImage(cvSize(image->width,image->height),image->depth,1);
		//Convert frame to gray and store in image
		cvCvtColor(image, image_layer, CV_BGR2GRAY);

		IplImage* object_color = cvCreateImage(cvGetSize(object), 8, 3);
		cvCvtColor( object, object_color, CV_GRAY2BGR );

		CvSeq *objectKeypoints = 0, *objectDescriptors = 0;
		CvSeq *imageKeypoints = 0, *imageDescriptors = 0;
		int i;
		CvSURFParams params = cvSURFParams(100, 1);

		double tt = (double)cvGetTickCount();
		//Calculate and extract feature point from template image
		cvExtractSURF( object, 0, &objectKeypoints, &objectDescriptors, storage, params );
		printf("Object Descriptors: %d\n", objectDescriptors->total);

		//Calculate and extract feature point from camera frame
		cvExtractSURF( image_layer, 0, &imageKeypoints, &imageDescriptors, storage, params );
		printf("Image Descriptors: %d\n", imageDescriptors->total);
		tt = (double)cvGetTickCount() - tt;
		printf( "Extraction time = %gms\n", tt/(cvGetTickFrequency()*1000.));

		CvPoint src_corners[4] = {{0,0}, {object->width,0}, {object->width, object->height}, {0, object->height}};
		CvPoint dst_corners[4];

		CvPoint img_corners[4] = {{0,0}, {image_layer->width,0}, {image_layer->width, image_layer->height}, {0, image_layer->height}};
		CvPoint dstimg_corners[4];

		//Mark the matching area with green rectangle
		if( locatePlanarObject( objectKeypoints, objectDescriptors, imageKeypoints,
			imageDescriptors, src_corners, dst_corners ))
		{
			for( i = 0; i < 4; i++ )
			{
				CvPoint r1 = dst_corners[i%4];
				CvPoint r2 = dst_corners[(i+1)%4];
				//cvPutText(image, "Matched!!", cvPoint(r1.x+5, r1.y+5), );
				//Green rectangle
				cvLine( image, cvPoint(r1.x, r1.y ),
					cvPoint(r2.x, r2.y ), colors[3], 2 );
			}

			for( i = 0; i < 2; i++)
			{
				CvPoint r1 = dst_corners[i];
				CvPoint r2 = dst_corners[(i+2)];
				cvLine(image, cvPoint(r1.x, r1.y), cvPoint(r2.x, r2.y), colors[1]);

			}
		}

		vector<int> ptpairs;
		findPairs( objectKeypoints, objectDescriptors, imageKeypoints, imageDescriptors, ptpairs );
		printf("Matching points = %d\n\n", (int)ptpairs.size());

		//Display the feature point
		for( i = 0; i < objectKeypoints->total; i++ )
		{
			CvSURFPoint* r = (CvSURFPoint*)cvGetSeqElem( objectKeypoints, i );
			CvPoint center;
			int radius;
			center.x = cvRound(r->pt.x);
			center.y = cvRound(r->pt.y);
			radius = cvRound(r->size*1.2/9.*2);
			cvCircle( object_color, center, radius, colors[4], 1, 8, 0 );
		}

		cvShowImage( "Template", object_color );
		cvShowImage("Matching Display", image);

		cvWaitKey(1);
	}

    cvDestroyWindow("Template");
	cvDestroyWindow("Matching Display");

	cvReleaseCapture( &capture );

    return 0;
}

16 responses to this post.

  1. Posted by Neel on June 16, 2011 at 6:43 pm

    Excellent Job!!! I am a curious student and I would like to take a look at the source code, if its possible? Could you share link/file? if it is not possible, I would really appreciate it if you can give me detailed explanation of points # 4, 5, 6 above. Thanks in anticipation!

    Reply

  2. Posted by nad on February 24, 2012 at 9:38 am

    Hello,
    I downloaded above code. It is working so slowly. Why?
    In video, it is working not slow.

    Reply

    • Posted by fahmifahim on February 24, 2012 at 9:53 am

      Hello there,
      thank you for visiting my blog.

      SURF applies a complicated calculation in determining the feature points,
      this would be the reason why the program is running slowly.
      I would suggest you to execute the program in a computer which has a higher specs.

      Regards,

      Reply

  3. […] Catatan Fahmi – simple explanation about SURF-based Image Recognition […]

    Reply

  4. Posted by zipdia on March 7, 2013 at 1:59 am

    Hi,
    I am new to this. Thanks for posting this. I was able to compile but my problem i don’t know how to have it work with my camera. I have a camera on my mac.

    Thanks for your help

    Reply

    • Hello, thank you for your comment.
      If you were able to compile the codes, the execution program should work just fine.
      (Btw, i developed the code on Windows+Visual Studio2008.)

      Reply

  5. Posted by zipdia on March 7, 2013 at 4:30 pm

    Thanks for the quick reply.
    I am sorry, it builds fine thats when I run it that I have a problem. I get the error:
    OpenCV Error: Bad argument (Array should be CvMat or IplImage) in cvGetSize, file /Users/marie-eve/Documents/OpenCV-2.4.3/modules/core/src/array.cpp, line 1238
    Camera dropped frame!
    libc++abi.dylib: terminate called throwing an exception
    Camera dropped frame!

    Please help

    Reply

  6. Posted by zipdia on March 7, 2013 at 4:32 pm

    By the way I am on a mac, do you think that might be the problem?

    Reply

  7. Posted by zipdia on March 7, 2013 at 10:51 pm

    Thank you very much, my problem was I didnt have the right image location. Thanks again

    Reply

    • Oh okay, thats great! Hope you enjoy the work.
      Btw, if you develop a new project, don’t forget to share 🙂

      Reply

    • Posted by reck on March 14, 2013 at 11:07 pm

      Hi! I also have the same issue :
      OpenCV Error: Bad argument (Array should be CvMat or IplImage) in unknown function

      I changed the image location but still have the problem.

      If you have any suggestion! 🙂

      Reply

  8. Posted by reck on March 19, 2013 at 4:52 pm

    Ok I solved my problem!

    I also made a mistake while liking the image. But that wasn’t the only one issue.
    Indeed, if you have the error “opencv was built without surf support”, don’t forget to link to the module called “nonfree” and make sure you added the line “cv::initModule_nonfree();” in your code :).

    Now it’s working good! And thank you very much for your work! 🙂

    Reply

  9. Posted by slow on July 21, 2013 at 4:06 pm

    its slow! my specs are good: intel i7, 6gb ram, 3gb gfx card. i am getting up to 2500ms extraction time. can you help?

    Reply

  10. can i aply it in android??

    Reply

  11. can i implement this in android?

    Reply

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: