Efficient way for SIFT descriptor matching

Question

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?

Answer 1

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));