Bag of Visual Words model

WHAT THIS TESTS The interviewer wants to know if you can turn a variable number of local features into a single fixed-length descriptor suitable for classification, and to recognize the model's key limitation.

A GOOD ANSWER COVERS Bag of Visual Words borrows from text retrieval. First you extract many local descriptors, such as SIFT, from a large training set. You cluster all these descriptors, typically with k-means, and each of the k cluster centers becomes a visual word; the set of words is the visual vocabulary or codebook. To represent any image you detect its local features, assign each descriptor to the nearest visual word, and accumulate a histogram counting how many of the image's features fall into each word. That histogram is a fixed-length vector regardless of how many keypoints the image had, so it can feed a standard classifier like an SVM. The crucial property, inherited from the text analogy, is that only word frequencies are kept; the spatial arrangement of features is discarded, which is why it is a bag.

COMMON WRONG ANSWERS Claiming BoVW preserves spatial layout. Confusing the vocabulary size k with the number of images. Forgetting the clustering step and thinking each raw descriptor is its own word.

LIKELY FOLLOW-UPS How do you choose the vocabulary size k. How does tf-idf weighting help. How do extensions like spatial pyramids reintroduce some spatial information.

ONE CONCRETE EXAMPLE Suppose you classify photos as beach, forest, or city. You extract SIFT descriptors from thousands of training images and run k-means with k equal to one thousand, yielding a vocabulary of a thousand visual words that capture recurring local patterns like sand texture, leaf edges, or window grids. For a new beach photo you compute its SIFT features, snap each to its nearest word, and build a thousand-bin histogram; beach images tend to have high counts in the sand-texture and horizon words. This histogram becomes a one-thousand-dimensional vector that you feed to a trained SVM, which predicts beach. The model works well even though it ignores where in the frame the sand or sky appeared, because the mix of visual words is itself discriminative. Spatial pyramid pooling can later add coarse position information if needed.