GSoC 2010 work has already started. As the very first phase, I have to choose a good algorithm to implement the pattern matching technique.Initially I am concentrating on the pattern matching on images and after this I will be concentrating upon integrating into CCV. The application may need to handle multiple image matching in real-time, therefore a good algorithm is needed. So as my mentor Pawel suggested, I looked around for different algorithms on feature extraction. Features of images remain same on different condition of images. Therefore it seems like a good idea.
The very first thing that I got regarding this was SIFT (Scale Invariant Feature Transform). Then I came across SURF (Speeded Up Robust Features) which is inspired by SIFT and has better performance. Also there are some implementations of SURF around internet which are listed in the wiki page. Even SURF has been integrated into openCV. But I have come across another open-source implementation named OpenSURF. It was quite nicely documented and had this Notes on openSURF library which has awesome explanation. But you should really check out the source as that has nice examples. Also each header files contain the use of each function.
One more good feature in SURF is that the Interest Points(IPoints) can be saved to a file and loaded for use which takes very less time than calculating interest points everytime. There are some specific parameters of iPoints which need to be saved/loaded. Those are scale,x,y,laplacian and the 64 descriptors acquainted with it.
I had carried out this experiment on 4 set of images. The results can be downloaded here. Each image features are extracted to a file of the same name and with ".txt" extension.In this post I will be analyzing one of the categories in details. You can see the result of all the categories by downloading the link I provided.
The Categories are :(Click on the Image to see it in actual size)
I will be analyzing the last category in which I got good results.
Here are the results in the image form. The matches are joined together with lines.
If you see the third image, out of the 3 matches, only one match is correct. Similarly I have found from my work that, if the images are very much similar then SURF works very well. But in case there is a major viewpoint change or major difference, then SURF fails to identify the features. With the Samples I have provided, see the Ferrari Images [c1.jpg-c5.jpg], there were no matches found in them (1 wrong match found).
The time taken for calculation depends upon the size of the image and also how the image is . In the process of my work, I have seen images with 2 Ipoints to 5k iPoints.As the number of iPoints increase, the time taken is more.For me some images took ~25 seconds and some tool 0.015 seconds for the iPoints calculation.
So this algorithm is not as good as the one used in Google Similar Images. But yes, if the images are quite similar (with rotation/change in lightening), then SURF seems to work awesome !