Thursday, March 1, 2012

SURF - Algorithm for matching

Many people talk about SURF and using it for recognition. But no one actually tells you, how it is used or what might be the algorithm for doing it. This series of posts, will detail you of using it practically. If you followed my previous posts, understanding this would be a lot more easier. You can skip the next paragraph. For noobs they have to read the next paragraph.

This post is made, assuming that you have openCV installed in your computer. If you haven't, go to my previous post for Installing openCV. To practice some openCV programming go to the assignments . If you don't know anything of openCV and are a complete absolute beginner, then go to the Easy navigation and start reading all the posts in the serial order. Most of them are practicals though to get your hands dirty. Also, if you have an open source OS, then this post will be more straight forward; although it isn't necessary. I know that many people use it in matlab. The code can be easily ported if you are well versed with C.

Let me start with giving a quick overview of SURF, so that understanding certain parts of the code we are going to write, will be easier to you. SURF stands for Speeded up Robust Features. In a given image, SURF tries to find the interest points - The points where the variance is maximum. It then constructs a 64-variable vector around it to extract the features (A 128-variable one is also possible, but it would consume more time for matching). In this way, there will be as many descriptors in an image as there are interest points. Now, when we use SURF for matching, we follow the below steps for every probe image (The image we need to match against)

1. Take a descriptor of the probe image
2. Compare this with all the descriptors of the gallery image (One of the set of possible matching images)
3. Find the nearest descriptor which is the one with the lowest distance to our descriptor compared to all the other descriptors
4. The nearest descriptor distance is stored
5. Take a descrptor other than the one's already taken from probe image and go to step-2
6. Now all the nearest descriptor distances are added, and the sum is divided with the total number of probe descriptors. This gives us the average distance
7. This average distance, along with the name of the gallery image we just matched, can be outputted to a file
8. For every gallery image, go to step-1
9. When all the gallery images get over, sort the distances in the outputted file and the one with the lowest distance is the best match for our probe image

There is already a function in openCV called cvExtractSURF to extract the SURF features of images. But there is no function to directly compare two images using SURF and give their distance. In the next post, we will be talking about doing this


Ahirnish said...

I read your blog I want to possibly, discuss one thing with you. In step #3 of your procedure, you are finding the nearest matched gallery image descriptor. Now, there may occur chances that a optimally matched descriptor is not found according to 2 NN theory i.e., dist(nearest neighbor)<0.6*dist(2nd nearest neighbor). Are you considering this matching or are you considering just nearest neighbour i.e., a neighbor will always be found?

Dileep Kumar said...

By default, we are taking the nearest descriptor value to be a very large one(some thing like 100000000), so always a nearest neighbor will be found

Ahirnish said...

void surf(Mat image1, Mat image2)

IplImage obj = image1;
IplImage* object = &obj;
IplImage source1 = image2;
IplImage* image = &source1;
IplImage* source = cvCreateImage(cvSize(92,112),8,1);

Hi, i am having a doubt and I dont know why the code is behaving in such manner. I am using the code of find_obj.cpp for SURF and in the beginning I have added some lines which I have posted above. Instead of giving IplImage*, I am giving Mat as argument and then converting it to IplImage so that I dont have to change whole code. The error that I am getting is ---
Assertion Failed (!img.empty() && img.depth() == CV_8U)

Both of my matrices are greyscaled and histogramed. When I debugged the code with breakpoints, it stopped on 2nd line of function i.e., IplImage obj = image1;


Sagar Shinde said...

whatever the work given here is for finding match
between the reference image and group of images.
I want to use the surf for human detection,for that purpose I have taken image of human(for e.g. image of man) and take another image, I have extracted the features of both images but what next have to be done to find that whether the second image is human or not
so please guide to complete the task or suggest any other method which is more efficient and faster than surf to complete my task.

Dileep Kumar said...

If you want just for detection i.e., whether the given image is a human or not, I suggest you to go to the post

Actually, detection is a very easy process, and I have detailed the steps very succinctly there.

bharath kumar said...

I tried the above code surf but i am getting blank screen.

bharath kumar said...

I tried the above surf code for human face detection but i am getting blank screen.

Cindy Dy said...

When someone writes an article he/she keeps the thought of a user in his/her brain that how a user can be aware of it. Therefore that’s why this post is outstanding.Thanks!



Hi,is it posible to detect cows,trees,human in a single image with surf feature.

Kalpana said...

Hi, we are doing the project on face detection and recognition by image processing.When we tried to extract the features by using surf, we got 2 values-key points and descriptors. We are confused which values are to be considered. Help me out!

Dileep Kumar said...

Hi Kalpana,
You can ignore the keypoints, only use descriptors. They are enough for detection/recognition.

It's not possible. Only one entity at a time.

Post a Comment