Feature descriptor comparison report
Sharing my research work of behavior of several types of feature descriptors. This article is an update of old "Comparison of feature descriptors" post. I've added a brand new ORB feature descriptor to the test suite, also SIFT descriptor included as well. And a new version of LAZY descriptor present in this test too.
Introduction
For this test i have written special test framework, which allows me to easily add the new kind of descriptors and test cases and generate report data in CSV-like format. Than i upload it in Google docs and create this awesome charts. Five quality and one performance test was done for each kind of descriptor.
Test cases
- Rotation test - this test shows how the feature descriptor depends on feature orientation.
- Scaling test - this test shows how the feature descriptor depends on feature size.
- Blur test - this test shows how the feature descriptor is robust against blur.
- Lighting test - this test shows how the feature descriptor is robust against lighting.
- Pattern detection test - this test performs detection of planar object (image) on the real video. In contrast to the synthetic tests, this test gives a real picture of the overall stability of the particular descriptor.
- Performance test is a measurement of description extraction time.
All quality tests works in similar way. Using a given source image we generate a synthetic test data: transformed images corresponding feature points. The transformation algorithm depends on the particular test. For the rotation test case, it's the rotation of the source image around it's center for 360 degrees, for scaling - it's resizing of image from 0.25X to 2x size of original. Blur test uses gaussian blur with several steps and the lighting test changes the overall picture brightness.
The pattern detection test deserves a special attention. This test is done on very complex and noisy video sequence. So it's challenging task for any feature descriptor algorithm to demonstrate a good results in this test.
The metric for all quality tests is the percent of correct matches between the source image and the transformed one. Since we use planar object, we can easily select the inliers from all matches using the homography estimation. I use OpenCV's function cvFindHomography for this. This metric gives very good and stable results. I do no outlier detection of matches before homography estimation because this will affect the results in unexpected way. The matching of descriptors is done via brute-force matching from the OpenCV.
Rotation test
In this test i obtain pretty expectable results, because all descriptors are rotation invariant expect the BRIEF. Slight changes in stability can be explained by the feature orientation calculation algorithm and descriptor nature. A detailed study of why the descriptor behaves exactly as it is, takes time and effort. It's a topic for another article. Maybe later on....
Scaling test
SURF and SIFT descriptors demonstrate us very good stability in this test because they do expensive keypoint size calculation. Other descriptors uses fixed-size descriptor and you can see what it leads to. Currently for LAZY descriptor i do not have separate LAZY feature detector (i use ORB detector for tests) but I'm thinking on lightweight feature detector with feature size calculation, because it's a must-have feature. Actually, scale invariance is much more important rather than precise orientation calculation.
Blur test
In this test i tried to simulate the motion blur which can occurs if camera moves suddenly. All descriptors demonstrate good results in this test. By “good” I mean that the more blur size is applied the less percent of correct matches is obtained. Which is expected behavior.
Lighting test
In lighting test the transformed images differs only in overall image brightness. All kinds of descriptors works well in this case. The major reason is that all descriptors extracted normalized, e.g the norm_2 of the descriptor vector equals 1. This normalization makes descriptor invariant to brightness changes.
Pattern detection on real video
Detection of the object on real video is the most complex task since ground truth contains rotation, scaling and motion blur. Also other objects are also present. And finally, it’s not HD quality. These conditions are dictated by the actual conditions of application of computer vision.
As you can see on diagram, the SIFT and SURF descriptors gives the best results, nevertheless they are far away from ideal, it’s quite enough for such challenging video. Unfortunately, scale-covariant descriptors show very bad results in this test because pattern image appears in 1:1 scale only at the beginning of the video (The “spike” near frame 20). On the rest of the video sequence target object moves from the camera back and scale-covariant descriptors can’t handle this situation.
Performance summary
This chart shows the extraction time for N features. I made Y-axis as logarithm scale to make it more readable. For all descriptor extraction algorithm the extraction time depends on number of features linearly. Local spikes is probably caused by some vector resizing or L2 cache misses. This performance test was done on Mac Book Pro 2.2 with Core 2 Duo 2.13 Ghz.
Further works
Add new quality test cases. One additional test i know for sure - affine transformations. Your ideas for other tests are welcome!
- Add new kind of descriptors. Definitely will add an A-SIFT implementation.
- Create an LAZY detector with feature size and orientation estimation.
- Improve the LAZY descriptor extraction procedure. Expect at least 20% performance gain.
- Generate matching video for each test to demonstrate the behavior of each descriptor algorithm.
Updates in Twitter
- I love Dropbox because it gives additional space if you mention it in tweet :)
http://t.co/0t6sHj8U
Become a subscriber!
Tags
Categories
- Analytics (2)
- Announces (3)
- News (2)
- Offtopic (1)
- Optimization (1)
- Q&A (1)
- Reciples (9)
- Research (8)
- Showcase (2)
- Tutorials (5)
- Uncategorized (7)
Archives
- May 2012 (1)
- April 2012 (1)
- March 2012 (2)
- December 2011 (1)
- November 2011 (1)
- August 2011 (4)
- July 2011 (2)
- June 2011 (1)
- April 2011 (5)
- March 2011 (2)
- February 2011 (5)
- January 2011 (5)
- December 2010 (2)
August 20th, 2011 - 10:51
Nice work Eugene!! I’m working on 3D slam using 2D feature matching in conjunction with 3D pointclouds and I found this post really helpful. I have tested FAST, SURF, SIFT, BRIEF and ORB and I have decided to use SURF for the moment as a compromise between robustness and performance. I would like see a comparison between the OpenCV gpu-SURF against the cpu version, if you can add it would be great!
Best regards!
December 13th, 2011 - 13:35
Congratulations on the comparision report, it is very detailed, and it was very helpful on my research. I hope to see a new report as soon as OpenCV launches the new ORB+BRISK detector in January.
Best regards
August 20th, 2011 - 20:55
Hi!
Thanks for the comment.
I also thought about adding gpu version of SIFT and SURF descriptors. But the one thing prevents me of doing this – all my mac’s has ATI videocards
So i’m waiting for new MBP with NVidia graphics. I also very interested in the results.
August 22nd, 2011 - 10:22
Hi!
Thanks for the nice review.
It would probably be interesting to compare data requirements of the detection algorithms, say, a table with
- number of bytes per feature;
- number of features for the sample image;
- total amount of data used by each algorithm.
August 22nd, 2011 - 16:05
Hi, thank for the comment.
I agree some statistical information can be helpful.
Can you clarify the last option ” total amount of data used by each algorithm”. Did you mean the memory consumption?
September 1st, 2011 - 14:55
Sorry, I haven’t noticed your reply.
Yes, I mean how much memory (per object to be recognized) is required by each algorithm. This is often a really restricting issue on mobile platforms.
August 22nd, 2011 - 10:42
Hi again Eugene, I have tested the gpu SURF version on my Macbook (Nvidia 9400M [16 shaders]) and runs near 3 times faster than it does on my cpu (Core 2 Duo 2.0Ghz) detecting keypoints and computing descriptors. I have tested on 640×480 grayscale images. I believe that it would perform better on bigger images. In the other hand, matching is faster in the cpu (for now).
August 22nd, 2011 - 16:08
Thank you for sharing this information!
I am increasingly convinced that i should add the gpu accelerated implementations in the next review.
August 25th, 2011 - 06:30
Hi!
All your articles and postings are so useful. Thanks!
Actually, I’m using OpenCV 2.3 in iOS and trying to use ORB feature detector and descriptor.
The problem is that BruteForceMatcher is not working with ORB descriptors.
I found that ORB descriptor’s type is 0, which is ‘uchar’, so I set up BruteForceMatcher like this:
cv::BruteForceMatcher<cv::L2 > matcher;
And the number of matched pair is always zero. Can you let me know how can I use BruteForceMatcher with ORB feature descriptors?
August 25th, 2011 - 10:26
Hi
Try using cv::OrbFeatureDetector and cv::OrbDescriptorExtractor classes. This wrappers over cv::ORB does implicit conversion of the computed descriptors to double type, so you will be able to use it with BruteForceMatcher directly.
Other workaround is to explicitly convert the descriptor matrix to floating-point element type using cv::Mat.convertTo function.
August 25th, 2011 - 23:33
Hi
I tried cv::OrbDescriptorExtractor but it doesn’t seem that it converts descriptors to floating point implicitly. So I used cv::Mat.convertTo to convert it after cv::ORB(). It works fine! Thank you.
August 25th, 2011 - 06:36
Oops sorry! I missed some keywords. Here’s my codes:
std::vector keypointsSrc, keypointsDst;
cv::Mat descriptorsMatSrc, descriptorsMatDst;
cv::ORB orb;
orb(imgSrc, cv::Mat(), keypointsSrc, descriptorsMatSrc);
orb(imgDst, cv::Mat(), keypointsDst, descriptorsMatDst);
cv::BruteForceMatcher<cv::L2 > matcher;
std::vector<std::vector > matches1;
std::vector<std::vector > matches2;
matcher.knnMatch(descriptorsMatSrc, descriptorsMatDst, matches1, 2); // zero matches…
matcher.knnMatch(descriptorsMatDst, descriptorsMatSrc, matches2, 2); // zero matches…
August 25th, 2011 - 06:40
this is weird… does this editor handle double brackets differently? all double brackets are missing in my code
September 19th, 2011 - 23:14
This is nice work. But I am a little confused by the extraction time chart. From my experience, SUFR is much faster than SIFT.
September 20th, 2011 - 11:18
There is logarithmic scale for Y axis for the extraction time chart.
October 5th, 2011 - 06:51
Nice work! Would you consider releasing your test code, so that those of us who have a little less familiarity with OpenCV and image processing in general could have a working example of how to use these various feature descriptors? It would be very interesting to be able to repeat your test, only with images that are more appropriate to a user’s likely environment.
October 12th, 2011 - 22:57
Hi
I’d like to know how you chose the threshold for the matching. Is the total number of matches the same for each method ? Because if the total number of matches is small, a higher percentage of correct matches can be expected.
I maybe missed something, but basically my question is: how do you make your test “fair” when all the methods have different descriptors length and the distance measure used is not always the same (Euclidean, Hamming,…) ?
October 26th, 2011 - 20:41
Hi,
Nice work, I suggest you to test the descriptors for robustness to noise (by adding white or colored noise) or compression to your images. Those degradations are typical of videos taken by surveillance cameras.
October 27th, 2011 - 19:03
Hi, thanks for tip. It’s easy to add this test case.
November 28th, 2011 - 10:45
Hello~ thanks you for your great job~
could you give some advises on building a test framework?
December 12th, 2011 - 20:25
Hi,
What is the matching algorithm used? namely:
NN
NNDR
?
And How do you match keypoints? one by one? or hash table or…?
December 29th, 2011 - 21:04
Thanks for posting this, very informative.
January 19th, 2012 - 12:52
Great post, but everyone would appreciate more info on the implementations that you used, since opencv doesn’t implement all those descriptors. Can you share the implementation of RIFF or LAZY?
January 28th, 2012 - 19:39
very impressive contribution for sharing info
March 21st, 2012 - 05:03
This job is impressive, I saw it in August, 2011. I ‘m interest it, and want to cite this job in my article. But i didn’t see any published type. Can you send me the original published article.
March 21st, 2012 - 09:22
Hi, this is an original article. I haven’t published it.
So if you want to cite it, refer to it’s URL.
March 26th, 2012 - 03:37
Ok, Thanks.