Take the 2-minute tour ×

There are 2 images A and B. I extract the keypoints (a[i] and b[i]) from them.
I wonder how can I determine the matching between a[i] and b[j], efficiently?

The obvious method comes to me is to compare each point in A with each point in B. But it over time-consuming for large images databases. How can I just compare point a[i] with just b[k] where k is of small range?

I heard that kd-tree may be a good choice, isn't it? Is there any good examples about kd-tree?

Any other suggestions?

share|improve this question
kd-tree as such are not efficient for descriptors with such a high dimensionality as SIFT (this is known as the curse of dimensionnality). However, there exists other indexing strategies for approximate nearest neighbour search in high dimensional spaces. FLANN, included in OpenCV, is one. And there is an implementation of keypoint matching using FLANN, see the link in my answer –  remi Oct 10 '12 at 9:09
add comment

3 Answers

up vote 9 down vote accepted

KD tree stores the trained descriptors in a way that it is really faster to find the most similar descriptor when performing the matching.

With OpenCV it is really easy to use kd-tree, I will give you an example for the flann matcher:

flann::GenericIndex< cvflann::L2<int> >  *tree; // the flann searching tree
tree = new flann::GenericIndex< cvflann::L2<int> >(descriptors, cvflann::KDTreeIndexParams(4)); // a 4 k-d tree

Then, when you do the matching:

const cvflann::SearchParams params(32);
tree.knnSearch(queryDescriptors, indices, dists, 2, cvflann::SearchParams(8));
share|improve this answer
When you're flagging answers that should be comments or are just link only, please flag them as "Not an answer" instead of "Very low quality", it helps us from a workflow perspective. But keep flagging, we appreciate it! –  casperOne Oct 11 '12 at 12:57
add comment

The question is weather you actually want to determine a keypoint matching between two images, or calculate a similarity measure.

If you want to determine a matching, then I'm afraid you will have to brute-force search through all possible descriptor pairs between two images (there is some more advanced methods such as FLANN - Fast Approximate Nearest Neighbor Search, but the speedup is not significant if you have less then or around 2000 keypoints per image -- at least in my experience). To get a more accurate matching (not faster, just better matches), I can suggest you take look at:

If, on the other hand, you want only a similarity measure over a large database, then the appropriate place to start would be:

share|improve this answer
add comment

In OpenCV there are several strategies implemented to match sets of keypoints. Have a look at documentation about Common Interfaces of Descriptor Matchers.

share|improve this answer
add comment

Your Answer


