Bag of Visual Words

Bag of Visual Words (BoVW) applies text-retrieval ideas to images (Sivic & Zisserman, 2003): quantize local feature descriptors into a discrete vocabulary of “visual words,” describe an image as a histogram of word occurrences, and compare images by comparing histograms. It is the classical engine behind loop-closure detection and relocalization in SLAM (DBoW2 in ORB-SLAM, for example).

Pipeline

Vocabulary construction (offline). Collect a large set of local descriptors (e.g., ORB, SIFT) from a training corpus and cluster them with k-means into $K$ cluster centers — the visual words. For binary descriptors, cluster centers are computed with Hamming-space medians rather than Euclidean means.
Image representation. For each new image, extract descriptors and assign each to its nearest visual word. The image becomes a $K$ -dimensional histogram $\mathbf{v}$ , where bin $k$ counts the keypoints assigned to word $k$ . All spatial layout is discarded — hence “bag.”
TF-IDF weighting. Not all words are equally informative. Each bin is weighted by term frequency times inverse document frequency:

$v_k = \frac{n_{k,d}}{n_d} \cdot \log\frac{N}{n_k}$

where $n_{k,d}$ is the count of word $k$ in image $d$ , $n_d$ the total words in the image, $N$ the number of database images, and $n_k$ the number of database images containing word $k$ . Words that appear everywhere (floor texture, foliage) get down-weighted; rare, distinctive words dominate the score.

Retrieval. Normalize the weighted histograms and score similarity — DBoW2 uses an L1-based score

$s(\mathbf{v}_1, \mathbf{v}_2) = 1 - \frac{1}{2}\left\lVert \frac{\mathbf{v}_1}{\lVert \mathbf{v}_1 \rVert} - \frac{\mathbf{v}_2}{\lVert \mathbf{v}_2 \rVert} \right\rVert_1$

— and return the top-scoring database images as loop-closure candidates.

The hierarchical vocabulary tree

A flat vocabulary requires $O(K)$ distance computations to assign each descriptor, which is too slow for the $K \sim 10^5$ – $10^6$ words needed for discriminative retrieval. DBoW2/DBoW3 arrange words in a vocabulary tree built by hierarchical k-means: $k$ branches per node, $L$ levels, giving $K = k^L$ leaf words. Assigning a descriptor walks the tree comparing against $k$ children per level — $O(kL)$ , i.e., logarithmic in $K$ .

Two index structures make retrieval and verification fast:

Inverted index: for each word, the list of database images containing it (with weights). Scoring a query only touches images that share at least one word.
Direct index: for each image, the features grouped by tree node at some intermediate level. When a candidate is retrieved, correspondences for geometric verification are found by matching only features that fall in the same node — much faster than brute-force descriptor matching.

Practical notes

Vocabulary size matters: small vocabularies make dissimilar features collide into the same word (low distinctiveness); very large ones split matching features across words (low repeatability). Retrieval systems use large vocabularies precisely because the hierarchical tree keeps assignment cheap.
Normalization for loop closure: raw scores depend on scene texture richness, so systems like ORB-SLAM normalize a candidate’s score by the best score among the query’s covisible keyframes, turning an absolute threshold into a relative one that transfers across environments.
Same vocabulary everywhere: a pre-trained, environment-independent vocabulary (e.g., the ORB vocabulary shipped with ORB-SLAM) works surprisingly well in practice, avoiding per-deployment training.

Limitations and the verification step

BoVW throws away geometry, so two images with similar texture statistics can score high without depicting the same place (perceptual aliasing — corridors, brick walls). Practical loop-closure pipelines therefore treat BoVW output as candidates only and confirm them with geometric verification: match features, estimate an essential/fundamental matrix or PnP pose with RANSAC, and accept the loop only if enough inliers support a consistent geometry. Temporal consistency checks (requiring several consecutive matching frames) further suppress false positives. A vocabulary trained on one visual domain also transfers imperfectly to very different environments.

Why it matters for SLAM

Odometry drifts; loop closure is what makes SLAM more than dead reckoning, and BoVW is the classical way to find loops in constant time regardless of map size. It also powers relocalization after tracking loss and multi-session map alignment. Even as learned global descriptors (NetVLAD and successors) replace the retrieval stage in newer systems, the BoVW architecture — quantize, weight, invert, verify — remains the reference design, and DBoW2-style vocabularies still run in many deployed systems because they are fast, compact, and CPU-only.

Hands-on

Global feature detection