1

I have a set of a few thousand images, and for each image I have extracted a set of SIFT feature descriptors (currently bound to 200 per image).

I am required to form a complete graph of the distances between each of the images. That is, I need to work out the distance from each image to every other image via some metric.

So far I have tried using FLANN to calculate the 20 nearest neighbouring descriptors between the two nodes, and then calculating the mean distance between each of the matched descriptors. Unfortunately this process is taking far too long to perform.

Is there any way for me to compare the descriptors of these images more efficiently?

3
  • You can binarize SIFT descriptors without great loss of performance.
    – Maurits
    Mar 16, 2015 at 15:49
  • 1
    If there is the possibility to switch to SURF, you can use the build-in GPU implementation of OpenCV including feature extraction and brute-force matching(I think you have to build it with an enabled CUDA CMake flag). It was 40 times faster with my application and my GPU is quite slow.
    – gfkri
    Mar 17, 2015 at 12:31
  • 1
    Have you heard about Bag-of-Words model? I think you should consider using it.
    – zedv
    Mar 18, 2015 at 16:38

1 Answer 1

5

You can considerate to aggregate your SIFT descriptord into a Bag-of-visual words (BoV) or a Vector of Locally Aggregated Descriptor (VLAD). Basically:

1 - compute a codebook (K SIFT descriptors) with e.g K-means

2 - For each image, extract the SIFT descriptors, then look for the nearest neighbor of each into the codebook. Hence, compute an histogram of the SIFT of the image according to the codebook. This is the simplest method (hard coding, Sum pooling) but alternative exists (and often give better results for computer visions problems)

3 - Hence, each image is represented with a unique vector of size K (the histogram). You can then simply compute the distance between the images as the (e.g euclidean) distance between these histograms.

3
  • also note, that it's already builtin with opencv (as long as you're using float descriptors) and you can train an SVM or similar on the resulting histogram vectors, much more efficient than brute-force or flann based comparison.
    – berak
    Apr 1, 2015 at 16:48
  • Ended up going with this, I tried a variety of methods, from Binarized-SIFT, PCA-SIFT, and using histogram from codebook as you suggested. Your method was by far the quickest (~5000x quicker than my original method, with ~1000 descriptors per image), and had only a very small drop in results, where some of the others suffered greatly with my data. Apr 7, 2015 at 18:54
  • Leaving this here for future reference Sep 8, 2018 at 9:08

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.