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.
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:
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|2histogram by dividing everything by 20 and getting:
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.