features2d: Keypoint matching very slow
Hello!
I'm using OpenCV features2d to match a pair of high resolution images for stereo reconstruction. What I do looks as follows:
- Detect keypoints
- Extract descriptors
- Do a knn match with k=2
- Drop matches using the distance ratio
- Estimate a homography and drop all outliers
Basically this works fine for me. I retrieve between 60000 and 120000 initial keypoints from the images. BUT: Some combinations of Detector/Extractor/Matcher need a lot of time to finish.
For the time measurements here I measured detecting/extracting/matching.
Surf/Surf/FLANN takes about 82 seconds. This amount of time is reasonable for my needs. It gives me about 100k initial keypoints. My parameters here are as follows. 6 octaves, 2 layers per octave, hessian thres. 50, extended descriptors
Surf/Freak/BFMatcher needs 9m 50s which is quite a long time, with more than 9 min spent for matching. Surf has the same config as before. Is there a way to speed this up? Should FLANN with LSH give a speedup here? Does the time BFMatcher needs solely depend on the total number of descriptors, or does the quality of the descriptors have an influence on this?
http://answers.opencv.org/question/924/lsh-matching-very-slow/ Looking at these time emasurements for 1.000.000 ORB descriptors I wonder. Are ORB descriptors faster to match than FREAK ones? Have they been matched on the GPU?
If you have some additional advice for me I would appreciate it. I need as much good matches as I can get :).
Thanks
For your amount of keypoints BruteForceMatching will be slow of course, since it compares every Descriptor with all the other Descriptors. Although one match is fast, since the standard bfmatcher is just the hamming distance, the total amount of matching attempts results in a slow process. Also, Orb should be faster than Freak in comparison, since Orb has a 256bit Descriptor and Freak 512bit as far as I know. Some more information when to use what, you might find here: http://answers.opencv.org/question/18413/freak-or-brisk-neither-good-nor-faster-than/
Well thank you for the link, I think I'm a little bit wiser now, answers my questions.
I actually could break down the computation time of the binary descriptors by using FLANN with LSH indices. BRISK this way also gave me some good matches for images with much perspective change in a reasonable time.
Is the accuracy of the stereo reconstruction much lower if you reduce the size of the two input images? You should try that because keypoint extraction will speed up significantly (also lower number of keypoints to process, of course).
From my experience, a distance ratio about 0.75 is a good value, 0.65 or lower reduces the number of matches and only the best matches will remain. This depends on the matched patterns, of course.
I hope you combined the distance ratio with a cross-matching stage?
Reducing the size would be a possibility, but actually I want to maximize the number of obtained keypoints. I used the distance ratio and knn match with k=2 to drop ambigous points, I dind't use cross matching of the matcher if this is what you mean, since it needs k=1 to be set in the knn match afaik. But at the moment I'm satisfied with the first results, it's not superfast but fast enough and gives quiet good results.