bag of visual words

The bag of visual words borrows a trick from text retrieval. To compare documents, a search engine can ignore word order and represent each document simply as a histogram of how often each vocabulary word appears (a bag of words); two documents about the same topic share many words and so have similar histograms. The bag of visual words applies the same idea to images: treat an image as a collection of local features and represent it by counting how many of each 'visual word' it contains, discarding where in the image they appeared. This turns a variable-length set of local descriptors into a single fixed-length vector that is easy to compare, classify, and index, which is why it dominated image retrieval and recognition before deep learning.

The catch is that images have no predefined vocabulary; SIFT descriptors are points in a continuous high-dimensional space, not discrete words. So a vocabulary is learned by quantization. Extract local descriptors (typically SIFT) from a large collection of training images, then cluster them with k-means into, say, a few thousand clusters. Each cluster centre becomes a visual word, and the whole set of centres is the visual vocabulary or codebook. The number of clusters is the vocabulary size, a key parameter: too few words and distinct structures get lumped together; too many and matching becomes noisy and sparse.

To encode a new image, extract its local descriptors and assign each one to its nearest visual word (its nearest cluster centre). The image is then represented by the histogram of visual-word counts: a vector whose i-th entry is how many descriptors fell into word i. As in text retrieval, raw counts are usually reweighted by TF-IDF, which boosts visual words that are frequent in this image but rare across the database (and therefore discriminative) and down-weights words that appear everywhere. For large-scale retrieval, an inverted index maps each visual word to the list of images containing it, so a query touches only the relevant images rather than the whole database, enabling search over millions of images.

Bag of visual words powered landmark recognition, near-duplicate detection, and loop-closure in SLAM (the DBoW library is a classic example). Its built-in weakness is exactly what made text bag-of-words work: it discards spatial layout, so a scrambled image and its original have the same representation. Extensions restore some geometry: the spatial pyramid partitions the image into regions and concatenates per-region histograms, and richer encodings such as VLAD and Fisher vectors store how descriptors deviate from cluster centres rather than mere counts. Deep convolutional and transformer embeddings (and CLIP-style models) have largely replaced bag of visual words for classification and retrieval, but its vocabulary-and-histogram idea persists in the design of pooling layers and in efficient retrieval systems.