Take the 2-minute tour ×
Signal Processing Stack Exchange is a question and answer site for practitioners of the art and science of signal, image and video processing. It's 100% free, no registration required.

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

share|improve this question
add comment

1 Answer

up vote 9 down vote accepted

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). Edit: 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.

share|improve this answer
    
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 –  Jono Brogan Nov 13 '12 at 9:28
    
@JonoBrogan: You should accept my answer, because it's correct. :) I have edited the answer to try to clarify k-means. –  Dima Nov 13 '12 at 13:06
    
Does it make sense now? –  Dima Nov 13 '12 at 13:17
    
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? –  Jono Brogan Nov 13 '12 at 13:24
1  
But the biggest problem is that Kmeans algorithm does not give the same result always. It is greatly randomised. –  Clement Dec 2 '13 at 2:15
show 1 more comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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