13
$\begingroup$

I am hoping someone can explain how to use the bag of words model to perform image classification using SIFT/SURF/ORB features and a support vector machine?

At the moment I can compute the SIFT feature vectors for an image, and have implemented a SVM, however am finding it hard to understand the literature on how use the bag of words model to 'vector quantize' the SIFT features and build histograms that give fixed size vectors, that can be used to train and test the SVM.

Any links to tutorials or literature on the topic is welcome, thanks

$\endgroup$
1

1 Answer 1

17
$\begingroup$

If you could implement an SVM, you can quantize the features. :)

Typically the features are quantized using k-means clustering. First, you decide what your "vocabulary size" should be (say 200 "visual words"), and then you run k-means clustering for that number of clusters (200). The SIFT descriptors are vectors of 128 elements, i. e. points in 128-dimensional space. So you can try to cluster them, like any other points. You extract SIFT descriptors from a large number of images, similar to those you wish classify using bag-of-features. (Ideally this should be a separate set of images, but in practice people often just get features from their training image set.) Then you run k-means clustering on this large set of SIFT descriptors to partition it into 200 (or whatever) clusters, i. e. to assign each descriptor to a cluster. k-means will give you 200 cluster centers, which you can use to assign any other SIFT descriptor to a particular cluster.

Then you take each SIFT descriptor in your image, and decide which of the 200 clusters it belongs to, by finding the center of the cluster closest to it. Then you simply count how many features from each cluster you have. Thus, for any image with any number of SIFT features you have a histogram of 200 bins. That is your feature vector which you give to the SVM. (Note, the term features is grossly overloaded).

As I recall, there was a lot of work done concerning how these histograms should be normalized. I might be wrong, but I seem to recall a paper that claimed that a binary feature vector (i. e. 1 if at least 1 feature from this cluster is present, and 0 otherwise) worked better than a histogram. You would have to check the literature for details, and the details are important.

Edit: The Computer Vision System Toolbox for MATLAB now provides the bag of features functionality.

$\endgroup$
6
  • $\begingroup$ Hi Dima, thanks for your answer, I just had one question, when you say "then you run k-means clustering for that number of clusters", what are you running the k-mean clustering on? p.s I'm almost tempted to accept this answer for your comment on the term feature being grossly overload, I'm relevantly new to image processing and I couldn't agree more $\endgroup$ Nov 13, 2012 at 9:28
  • $\begingroup$ @JonoBrogan: You should accept my answer, because it's correct. :) I have edited the answer to try to clarify k-means. $\endgroup$
    – Dima
    Nov 13, 2012 at 13:06
  • $\begingroup$ Does it make sense now? $\endgroup$
    – Dima
    Nov 13, 2012 at 13:17
  • $\begingroup$ Yea, thanks. I've accepted the answer, although I'm just wondering do you know how you go about deciding how many "visual words" to use? $\endgroup$ Nov 13, 2012 at 13:24
  • 3
    $\begingroup$ But the biggest problem is that Kmeans algorithm does not give the same result always. It is greatly randomised. $\endgroup$
    – user7130
    Dec 2, 2013 at 2:15

Your Answer

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

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