# what is the output of BoW after an image has been trained with SIFT algorithm and k-means

SIFT algorithm provides a 128 dimensional feature vector that is used for image classification.When all the interest points(key points) are taken together and K-means clustering is applied,the image is then clustered into many clusters.My question is how does this clustering/grouping of feature points together help in creating a dictionary(of equivalent image words).Does the output after applying this BoW algorithm yield a single vector for an image.

• Which is the best method for comparing the histogram obtained after BOW ? 1. Euclidian distance 2. Cosine similarity 3. Histogram Intersection 4. Or any other? Consider the importance of the method in case of images. Eg, Cosine Similarity matches angle of two vectors... What impact comparing just the angle or distance has on accuracy of BOW? Detailed explanation is welcome!!! Commented Feb 24, 2014 at 12:33
• Hey, welcome to DSP. I see that what you wrote is related to the question, but it is still not an answer to the question. If you have a related question (like this one), you are always welcome to ask a new question (and include links to any related questions if you want). I have flagged your question and it will soon be deleted, but please post your question as a new question and I am sure it will be answered. Commented Feb 24, 2014 at 13:26

You essentially got it right: the final purpose of the whole BoW clustering algorithm is to somehow produce a single image descriptor for every image.

In case of BoW clustering (either K-means, or hierarchical K-means, or some other clustering), this image descriptor is a histogram of visual words for that image often normalized by the number of local features for each image.

Let me offer a step-by-step explanation of the process:

• first you get all the local features from all the images (or just from your learning dataset), and cluster all those features by a clustering algorithm of choice
• after completing the clustering, for every cluster we calculate the "representative member" by some kind of mean or average over all the local feature samples from that cluster

This "representative member" is actually your visual word -- it's like the "core" of all the features of the cluster (if you would be working with actual words, the samples "work", "working" and "workaround" might all have a common representative member "work").

This step might actually be skipped -- we don't care about exact visual word, as long as we can distinguish between the clusters (e.g. knowing how to classify a new local feature in to "cluster 1", "cluster 2" or "cluster 3" is enough).

• now, for every image in our database we construct the "image descriptor" by making the histogram by clusters for that image.

E.g., if there is 4 clusters in final clustering, and our image has 4 features in cluster 1, 10 in cluster 2, 4 in cluster 3 and 2 more in cluster 4, the descriptor might be: 4|10|4|2.

• finally, we can normalize the histograms

Following with the same example from above, the image had a total of 20 features. We could thus normalize the 4|10|4|2 histogram by dividing everything by 20 and getting: 0.2|0.5|0.2|0.1.

With this, you ended your "database description" -- you have a numeric descriptor for all your images. Now, when a new image arrives, you do the following:

• extract local SIFT (or any other kind) of features
• determine for all the local features of the new image to which cluster they belong
• make a histogram for the new image (+ normalize histogram)
• compare the histogram of the new image to the histograms of database images

You have methods other than BoW to create the "image descriptors". One alternative to BoW is VLAD (Vector of locally aggregated descriptors), which is a bit more compact but has the same purpose.

Yes, output for image is 1-D array of visual words. The word is number of the cluster, feature belongs to. Output for feature is one number.