I'm implementing a Content Based Image Retrieval application (CBIR).

I've read about the Bag of Features model and it's considered an intermediate-step algorithm in some application. For example, the histograms generated could be used for SVM classification.

Since the produced vectors are affected by the curse of dimensionality, it can become expensive to compute some kind if distance between a query histogram and all the dataset histograms. For this reason, techniques like LSH have been implemented for datasets with hundreds of thousands (or millions) of images. As explained here, KD-trees are useless in this context since the histograms high dimensionality and their performance is not going to be better than linear scan.

However, my system is based on (let's say) 50k images, so compute directly the distance should not be so prohibitive.

I have two questions:

  1. Is this approach reasonable? Recap of it: classic BoF approach and then compute the distance between each dataset histogram and the query histogram. The smaller one is returned as the most similar image.
  2. Which distance should I use? I've heard that chi-squared distance is a popular choice. What about euclidean, cosine similarity etc? Which one is the best in such a context?
  • $\begingroup$ Since you are counting "words" in an image, you get essentially a histogram. A chi-square or intersection kernel in SVM has been found a good fit for this data; and there are tricks to compute kernel values and use in SVM very efficiently (see works by Subhransu Maji, "Efficient Classification for Additive Kernel SVMs", "Classification Using Intersection Kernel SVMs is efficient") $\endgroup$ – Vladislavs Dovgalecs Dec 14 '17 at 19:28

The approach is reasonable as long as the bag-of-features representation properly captures your desired concept of similarity/distance between images. For example, it has the property that local features could be spatially re-arranged within an image and the representation wouldn't change. That could be good or bad, depending on your perspective.

Similar reasoning applies to the choice of distance metric. There is no absolute best; it depends entirely on what you want 'similar' and 'distant' to mean in the context of your application. For example, cosine distance measures the relative angle between vectors, but is invariant to magnitude. This would mean that distance between images is determined by the relative frequency of each feature, but not the absolute count. This is a popular choice for measuring distance between bag-of-word models of text documents, because relative word frequencies can better capture the meaning of text documents (e.g. a longer document might contain more occurrences of each word, but this doesn't affect the meaning). Whether cosine distance makes sense for your image retrieval system depends on whether you want your system to have that property.

Your goal is to return the image in your database that's closest to the query image. This is called nearest neighbor search. It isn't necessary to compute the distance between the query and every single image in your database; more efficient procedures exist. The general idea is that distances between images in the database can be exploited, along with properties of the distance metric. If you know that the query image has a particular distance to some database image, you can infer that other database images can't possibly be the nearest neighbor. Therefore, many unnecessary distance computations can be eliminated and the search can be performed in sublinear time. You mentioned locality sensitive hashing, so it sounds like you're aware of this issue. Another popular class of methods uses tree data structures (e.g. KD-trees, ball trees, cover trees) to accelerate the search. Searching for "nearest neighbor search" will return many papers on the topic, and ready-to-use code is available for a number of methods.

  • $\begingroup$ Thanks for your useuful and detailed answer. Now it's clearer to me why cos-sim is used in text BoW applications. I cannot figure out a CBIR application where this feature could be useful. Anyway, read my updated question about why KD-trees are useless. I don't know ball trees and cover trees (funny names though). I don't know any other good LSH C++ implementation than (Falconn)[falconn-lib.org/] ((FLANN)[cs.ubc.ca/research/flann/] can be considered outdated) and it's for cos and eucl distances. Do you? $\endgroup$ – user6321 Jul 20 '16 at 7:08
  • $\begingroup$ Falconn looks interesting. This quora page mentions some other LSH implementations: quora.com/What-are-some-good-LSH-implementations. It's true that KD-trees suffer as dimension increases. Cover trees depend on the intrinsic dimensionality of the data. Performance can be high if intrinsic dimensionality is low, even if data is embedded in a higher dimensional space. $\endgroup$ – user20160 Jul 20 '16 at 10:39

At 50k objects, if you use this offline, you can probably afford pairwise distance computations. Depends on how good your code is!

As for distances, that is a matter of taste. Since the data is a histogram, divergence measures should be most appropriate.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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