Bag of Visual Words

The bag of visual words (BoVW) represents an image by how often each of a fixed set of local patterns occurs in it. Local descriptors such as SIFT are computed at many points of the image, each descriptor is replaced by the nearest of $k$ prototype descriptors, the visual words, and the image becomes a $k$-bin histogram of word counts. The prototypes, together called the visual vocabulary or codebook, are learned once by clustering descriptors from training images, usually with k-means. The representation is also called the bag of features, the bag of keypoints, the codebook model, or simply bag of words, after the bag-of-words model of text, which it copies: an image is treated as a document whose words are quantized descriptors, and their order and position are ignored.

Two papers established its two main uses. Sivic and Zisserman’s Video Google paper (ICCV 2003) built a visual vocabulary to retrieve the frames of a film that contain a user-selected object, borrowing the term weighting, stop lists and inverted files of text search engines; earlier image databases had borrowed weighting and inverted files from text retrieval, but they described theirs as the first systematic application of these ideas to object retrieval in video. Csurka et al. (2004) used word histograms as feature vectors for classifiers that assign images to categories such as faces, cars and bikes; they credit Zhu et al. with quantizing square image windows (“keyblocks”) earlier, without invariance. By 2008–2009 most state-of-the-art image search systems were built on visual words, according to Philbin et al. (2008) and Jégou, Douze and Schmid (2009), and with its successors the representation served image classification until learned embeddings took its place.

Problem

Local descriptors match well between views of the same object, but an image yields hundreds or thousands of them, and feature matching by nearest-neighbor search compares every descriptor of the query with every descriptor of each candidate image. Sivic and Zisserman wanted object search over feature films with the immediacy of web search, which rules out matching the query against every frame at query time. Csurka et al. wanted to feed images to standard classifiers, which expect one fixed-length vector per image, while the number of descriptors varies from image to image.

Quantization solves both. Once each descriptor is a word index, two descriptors “match” when they have the same index, matches can be precomputed, and an image of any size becomes a vector of length $k$.

Inputs and Outputs

Offline the input is a large set of training descriptors, for example 128-dimensional SIFT vectors computed on keypoints or a dense grid of a few thousand images. The output is the vocabulary: $k$ centers in descriptor space, from a few hundred for classification to a million or more for large-scale retrieval.

Per image the input is the image’s set of local descriptors, of variable size. The output is a sparse $k$-dimensional vector of word counts, usually reweighted and normalized. For retrieval, the database vectors are stored in an inverted file, and the output of a query is a ranked list of database images. For categorization, the vectors go to a classifier, which outputs a label.

Intuition

A visual word stands for a small region of descriptor space, and therefore for a family of image patches that look alike to the descriptor: a particular corner, blob or texture element, at whatever position, scale and rotation the detector and descriptor normalize away. Two images that show the same object share many of these patch types, so their histograms overlap; unrelated images share fewer. Counting replaces matching: instead of finding which descriptor corresponds to which, the method only asks how many patches of each type each image contains.

The text analogy goes further than the counting. Words that occur in almost every document (“the”, “and”) say little about any of them, so search engines down-weight them by their inverse document frequency or drop them with a stop list; a visual word that fires on a texture found in most photos, such as foliage or brickwork, is in the same position. And because a document contains only a small fraction of the vocabulary, a search engine keeps, for each word, the list of documents that contain it, an inverted file, so that a query visits only the documents that share at least one of its words.

The price is quantization error. Two descriptors of the same physical patch that fall on opposite sides of a cell boundary get different words and do not match at all, while two different patches in the same cell match perfectly. A coarse vocabulary merges distinct patterns; a fine one splits a single pattern across words. Nistér and Stewénius described this as a trade-off between distinctiveness, which needs small cells, and repeatability, which needs large ones.

Algorithm

Building the vocabulary (offline)

1. Detect keypoints or sample a dense grid on a set of training images, and compute a descriptor at each point.
2. Cluster a sample of the descriptors into $k$ clusters, usually with k-means; the cluster centers are the visual words.

Indexing a database (offline)

3. For each database image, compute its descriptors and assign each to its nearest visual word (or, with soft assignment, to a few nearby words with weights).
4. Count the occurrences of each word to get the image’s term-frequency vector.
5. Compute each word’s inverse document frequency from how many database images contain it; optionally put the most frequent (and sometimes the rarest) words on a stop list.
6. Weight and normalize each image’s vector, and store its nonzero entries in the inverted file: for each word, the list of images containing it and the weighted entries.

Querying (online)

7. Compute and quantize the query’s descriptors (from the whole image or a selected region) and form its weighted, normalized vector the same way.
8. For each word in the query, walk that word’s list in the inverted file and accumulate each listed image’s contribution to its similarity score.
9. Sort the images by score. Image retrieval systems then usually re-rank the top of the list by checking that the matched words are geometrically consistent, and may expand the query with words from the verified results.

For categorization steps 5–9 are replaced by training a classifier on the labeled training images’ histograms and applying it to the histogram of a new image.

Mathematical Formulation

Vocabulary by k-means

Given training descriptors $x_1, \dots, x_M \in \mathbb{R}^d$, k-means chooses centers $c_1, \dots, c_k$ that minimize the total squared distance of each descriptor to its nearest center,

$$J(c_1, \dots, c_k) = \sum_{m=1}^{M} \min_{1 \le j \le k} \lVert x_m - c_j \rVert^2 ,$$

by Lloyd’s alternation: assign every descriptor to its nearest center, move every center to the mean of its descriptors, and repeat. As Csurka et al. note, the iteration converges only to a local minimum and does not choose $k$; Sivic and Zisserman ran k-means several times and kept the best result, and Csurka et al. kept the clustering that gave the lowest classification error rather than the lowest $J$, since the goal is accurate categorization, not a correct clustering. The cells of the vocabulary are the Voronoi regions of the centers. Sivic and Zisserman first transformed SIFT space by a Mahalanobis whitening estimated from the descriptors of their 48 training shots, so that Euclidean k-means down-weighted noisy descriptor components; Nistér and Stewénius and Philbin et al. quantized SIFT descriptors directly. RootSIFT, a remapping of SIFT under which the Euclidean distance used by k-means corresponds to the Hellinger kernel on the original histograms, is described in SIFT.

Hard and soft assignment

Hard assignment maps each descriptor to one word,

$$q(x) = \arg\min_{j} \lVert x - c_j \rVert ,$$

and image $I$ with descriptors $\{x\}$ gets the count vector $n_j(I) = \lvert \{ x \in I : q(x) = j \} \rvert$.

Soft assignment spreads each descriptor over several words. Philbin et al. (2008) assigned a descriptor to its $r$ nearest words with weights

$$w_j(x) \propto \exp\!\left( -\frac{\lVert x - c_j \rVert^2}{2\sigma^2} \right),$$

normalized to sum to 1 over the $r$ words, and added these weights instead of counts. van Gemert et al. (2010) separated two effects of hard assignment with a kernel $K_\sigma$ on the descriptor–word distance $D$, writing the weight of word $w$ in an image with $n$ descriptors $r_1, \dots, r_n$ in three ways:

$$\begin{aligned} \mathrm{KCB}(w) &= \frac{1}{n} \sum_{i=1}^{n} K_\sigma\big(D(w, r_i)\big) && \text{kernel codebook} \\ \mathrm{UNC}(w) &= \frac{1}{n} \sum_{i=1}^{n} \frac{K_\sigma\big(D(w, r_i)\big)}{\sum_{v \in V} K_\sigma\big(D(v, r_i)\big)} && \text{codeword uncertainty} \\ \mathrm{PLA}(w) &= \frac{1}{n} \sum_{i=1}^{n} K_\sigma\big(D(w, r_i)\big)\, [\, w = \arg\min_{v \in V} D(v, r_i) \,] && \text{codeword plausibility} \end{aligned}$$

Uncertainty lets a descriptor that lies between several words share its unit weight among them; plausibility keeps only the nearest word but gives little weight to a descriptor that is far from every word; the kernel codebook does both. With a constant kernel and only the nearest word, the formula reduces to the ordinary normalized histogram. They used a Gaussian kernel, the shape that pairs with the Euclidean distance on SIFT, and tuned $\sigma$ by cross-validation for classification accuracy rather than for the best fit to the data.

Term weighting

With $N$ database images, $n_{jd}$ occurrences of word $j$ in image $d$ and $n_d$ words in image $d$, the tf-idf weight of word $j$ in image $d$ is

$$t_{jd} = \frac{n_{jd}}{n_d} \, \log \frac{N}{N_j} ,$$

the product of the term frequency $n_{jd}/n_d$, which favors words that occur often in this image, and the inverse document frequency $\log(N/N_j)$, which down-weights words common in the database. Nistér and Stewénius define $N_j$ as the number of database images that contain word $j$ at least once, and report that using the word’s total number of occurrences instead made little difference; the Video Google paper’s text describes its $n_i$ as the number of occurrences of the word in the whole database, while the 2009 journal version counts the documents that contain the word. Under the image-count definition, a word that occurs in every image gets weight $\log 1 = 0$. A stop list sets the weight of chosen words to zero outright. With soft assignment, Philbin et al. (2008) used the summed weights as term frequencies but counted any nonzero weight as one occurrence when computing the idf, which gave their best results.

Similarity and the inverted file

Each image’s weighted vector $t_d$ is normalized, $v_d = t_d / \lVert t_d \rVert$, and the database is ranked by a similarity to the query vector $v_q$. Sivic and Zisserman used the cosine similarity $v_q^\top v_d$, as text retrieval does. For unit vectors this is equivalent to ranking by Euclidean distance, since

$$\lVert v_q - v_d \rVert_2^2 = 2 - 2 \sum_{j \,:\, q_j \ne 0,\ d_j \ne 0} q_j d_j ,$$

where $q_j$ and $d_j$ are the entries of $v_q$ and $v_d$. Nistér and Stewénius found the ℓ1 norm, used for both the normalization and the difference, better than ℓ2, and showed that it, too, needs only the words the two vectors share: for ℓ1-normalized vectors,

$$\lVert v_q - v_d \rVert_1 = 2 + \sum_{j \,:\, q_j \ne 0,\ d_j \ne 0} \big( \lvert q_j - d_j \rvert - \lvert q_j \rvert - \lvert d_j \rvert \big) .$$

Both sums run over words present in both images, exactly the pairs an inverted file enumerates: for each nonzero $q_j$, the list for word $j$ holds the images with $d_j \ne 0$ and their values. Scores accumulated this way equal the full similarity, but the work is proportional to the lengths of the query’s lists, not to $N k$. The measures themselves, including histogram intersection and χ², are compared in similarity and distance measures.

Classifiers on word histograms

Csurka et al. compared two classifiers. Their Naïve Bayes model treats each word of an image as drawn independently from a class-specific distribution over the vocabulary, so that with $N(t, I)$ the count of word $v_t$ in image $I$,

$$P(C_j \mid I) \propto P(C_j) \prod_{t=1}^{k} P(v_t \mid C_j)^{N(t, I)}, \qquad P(v_t \mid C_j) = \frac{1 + \sum_{I_i \in C_j} N(t, I_i)}{k + \sum_{s=1}^{k} \sum_{I_i \in C_j} N(s, I_i)} ,$$

where the added 1 and $k$ (Laplace smoothing) keep unseen words from giving zero probability. Their second classifier was a support vector machine on the histograms, one-against-all for the seven classes, in which linear kernels beat quadratic and cubic ones except for one class.

Recognition and Retrieval

Instance retrieval. In the Video Google system, a user outlines an object in one frame, and the frames of the film are ranked by the tf-idf similarity of their word vectors to the words inside the outline; a stop list removes the most frequent words, and the top of the ranking is re-ordered by how many matched words have spatially consistent neighbors. The later retrieval systems cited here keep this two-stage design: a bag-of-words filtering stage ranks the whole collection and a geometric stage re-ranks its head. Nistér and Stewénius argued that at web scale only a small fraction of the database can be verified geometrically, so the bag-of-words stage itself must rank the right images first, and concentrated on that stage.

Two benchmarks recur below. Nistér and Stewénius’s set of objects photographed four times each is described in their paper as 6,376 images and scored by the percentage of perfect retrievals, but on its official page and in later papers as 10,200 images scored by the average number of the group’s four images among the top four results (best score 4; the official page’s scoring code counts the query); Oxford 5K (Philbin et al., 2007) has 5,062 Flickr photographs and 55 landmark queries, scored by mean average precision.

Category recognition. Csurka et al.’s pipeline is summarized in image classification. They built the vocabulary from random samples of 5,000 descriptors per class, so that classes with more interest points would not dominate it, and on their seven-class dataset, with 10-fold cross-validation, the error rate improved only slightly from $k = 1000$ to $k = 2500$, so they chose 1,000 words. Where Csurka et al. detected Harris-affine regions, Lazebnik, Schmid and Ponce (2006) computed SIFT densely, on $16 \times 16$ patches every 8 pixels, citing evidence that dense features work better for scenes, and used vocabularies of 200 to 400 words.

Parameters

Parameter	Typical values in the sources	Effect
Vocabulary size $k$	1,000 (Csurka et al., classification); 200–400 (Lazebnik et al., with spatial pyramid); about 6,000 + 10,000 for two region types (Sivic & Zisserman); $10^6$ (Nistér & Stewénius; Philbin et al.)	Larger vocabularies are more distinctive and make the index sparser, but split one pattern across words
Training descriptors	Random samples of 5,000 per class (Csurka et al.); up to 16.7 million (Philbin et al., 2007)	A large vocabulary needs many descriptors per word
Assignment	Hard; soft with $r = 3$, $\sigma^2 = 6{,}250$ on Philbin et al.’s descriptor scale	Soft assignment recovers matches lost at cell boundaries, at a cost in index size
Weighting	tf-idf; binary; raw counts	idf suppresses words common to the database
Stop list	Top 5% and bottom 10% of words by frequency (Sivic & Zisserman)	Removes uninformative words and shortens the longest lists
Normalization and distance	ℓ2 and cosine (Sivic & Zisserman; Philbin et al.); ℓ1 (Nistér & Stewénius)	Changes ranking; ℓ1 was better in Nistér and Stewénius’s tests

Vocabulary size is the main parameter, and its best value depends on the task. In retrieval, where the query and the target show the same physical object, larger vocabularies helped up to very large sizes. Nistér and Stewénius found performance rising with the number of leaves up to somewhere between 1 and 16 million, and on a subset of about 1,400 images a 1-million-word tree with ℓ1 scoring scored 90.6% perfect retrieval, against 81.3% for a 10,000-word tree and 76.0% for a flat 10,000-word vocabulary scored with ℓ2, the setting of Video Google (their Table 1, whose caption counts queries with perfect retrieval while the text counts partner images found perfectly). Philbin et al. (2007) found a peak at 1 million words on Oxford 5K (0.618 mAP, against 0.473 with 50,000 words and 0.602 with 1.25 million; their Table 5). In categorization, where words must generalize across different instances of a class, the systems cited here used far smaller vocabularies, and van Gemert et al. found that with hard assignment, vocabularies that are large relative to the number of training descriptors severely degrade accuracy: on 15-category scenes with five training images per class (about 67,000 descriptors), performance of all methods fell beyond 800 words, and hard assignment deteriorated severely from 6,400 words, while codeword uncertainty declined only slightly.

Training data. Nistér and Stewénius trained the vocabulary on video separate from the database and found that more training frames improved results with a large vocabulary. Training on different but similar images costs accuracy: Philbin et al. (2008) built a second vocabulary from 6,300 Paris landmark photos and tested it on Oxford, where bag-of-words mAP fell from 0.614 with an Oxford-trained vocabulary to 0.403 with hard assignment (their Table 3; their 2007 paper reported 0.618 for the Oxford-trained 1-million-word baseline).

Stop lists help less than the text analogy suggests. Sivic and Zisserman chose their limits empirically to reduce mismatches and the size of the inverted file; Nistér and Stewénius blocked very long inverted lists mainly for speed and reported that in most cases they could not improve retrieval quality with stop lists.

Complexity

Vocabulary construction. One Lloyd iteration costs $O(Mkd)$ for $M$ descriptors, which becomes impractical for vocabularies of $10^5$ to $10^6$ words and tens of millions of descriptors. Two remedies, described under Variants, reduce the assignment step to roughly $O(M d \log k)$: the vocabulary tree and approximate k-means.

Quantization. Assigning one descriptor to a flat vocabulary costs $k$ distance computations; a tree with branch factor $b$ and $L$ levels needs $bL$, for $b^L$ words. Nistér and Stewénius reported 0.2 s of feature extraction for a $640 \times 480$ frame and stored a tree with $b = 10$, $L = 6$ (one million leaves) of 128-dimensional descriptors in 143 MB, about $d \, b^L$ bytes for byte-valued descriptors.

Querying. With an inverted file the cost of a query is the total length of the lists of its words. Nistér and Stewénius pointed out that with about 10,000 words and on the order of 1,000 words per image, a query traverses roughly a tenth of the database even if words are spread uniformly, and that a million-word vocabulary cuts this by orders of magnitude. They reported 25 ms per query on 50,000 images and about one second on a million images held in 8 GB of RAM. Philbin et al. (2007) reported about 0.1 s per query on 105,000 images with a 1 GB index, and 15–35 s from disk on 1.1 million images, whose index needed 4.3 GB.

Memory. The index stores about one entry per distinct word per image, so it grows with the number of descriptors, not with $k$. Soft assignment multiplies it: Philbin et al. (2008) reported an index of 36 MB for Oxford 5K with hard assignment and 108 MB with soft assignment to three words.

Implementation

The example builds a small retrieval system on synthetic photographs with known ground truth. Each of 60 objects is a layout of eight glyphs drawn from a pool of 36; each image shows one object, warped by a random rotation (±15°), scale (0.85–1.15) and position, on a brick-wall background that is the same in every image, together with twelve glyphs drawn from four “common” ones shared by all images, plus an illumination change and noise. Every object is photographed twice: one view goes into the database and the other is the query, so each query has exactly one correct answer and chance level is $1/60 \approx 0.02$. Keypoints and descriptors come from scikit-image 0.25.2’s SIFT; the vocabulary is trained with NumPy k-means on 10,000 database descriptors, and retrieval runs through an explicit inverted file, checked against the full cosine similarity. The loop compares five vocabulary sizes and three weightings over three seeds, and records how many inverted-file entries each query reads and what fraction of the words occur in every database image.

import numpy as np
from scipy import ndimage
from skimage.feature import SIFT  # scikit-image 0.25.2

S, N = 128, 60  # image size in pixels; objects per run (one database and one query view each)

def make_glyphs(rng, n=40):
    """Random 15x15 glyphs: 5x5 binary patterns, upsampled and slightly blurred."""
    g = np.kron(rng.random((n, 5, 5)) < 0.45, np.ones((3, 3))).astype(float)
    return np.stack([ndimage.gaussian_filter(x, 0.7) for x in g])

def render(rng, layout, glyphs, wall):
    """One photo of an object, intensities in [0, 1]: a brick wall shared by all images,
    12 copies of 4 'common' glyphs, and the object under a random similarity transform."""
    img = 0.45 + 0.12 * wall
    for _ in range(12):
        y, x = rng.integers(0, S - 15, 2)
        img[y:y + 15, x:x + 15] = 0.2 + 0.6 * glyphs[rng.integers(4)]
    obj, mask = np.zeros((64, 64)), np.zeros((64, 64))
    for (y, x), g in layout:
        obj[y:y + 15, x:x + 15], mask[y:y + 15, x:x + 15] = glyphs[g], 1
    a, s = np.deg2rad(rng.uniform(-15, 15)), rng.uniform(0.85, 1.15)
    A = np.array([[np.cos(a), -np.sin(a)], [np.sin(a), np.cos(a)]]) / s
    off = -A @ rng.uniform(24, S - 24 - 64 * s, 2)        # random placement
    o, m = (ndimage.affine_transform(z, A, off, output_shape=(S, S), order=1) for z in (obj, mask))
    img = (1 - m) * img + m * (0.2 + 0.6 * o)
    img = rng.uniform(0.7, 1.3) * img + rng.uniform(-0.1, 0.1)   # illumination change
    return np.clip(img + rng.normal(0, 0.03, img.shape), 0, 1)

def sift(img):
    det = SIFT()
    det.detect_and_extract(img)
    d = det.descriptors.astype(float)
    return d / np.linalg.norm(d, axis=1, keepdims=True)

def kmeans(X, k, rng, iters=10):
    """Lloyd's algorithm, initialized with k randomly chosen descriptors."""
    C = X[rng.choice(len(X), k, replace=False)].copy()
    for _ in range(iters):
        lab = quantize(X, C)
        cnt = np.bincount(lab, minlength=k)
        sums = np.zeros_like(C)
        np.add.at(sums, lab, X)                 # per-word sums of the assigned descriptors
        C[cnt > 0] = sums[cnt > 0] / cnt[cnt > 0, None]   # empty words keep their center
    return C

def quantize(X, C):  # hard assignment to the nearest word (Euclidean)
    return np.argmin((C ** 2).sum(1) - 2 * X @ C.T, axis=1)

def run(seed, sizes):
    rng = np.random.default_rng(seed)
    glyphs = make_glyphs(rng)
    wall = np.zeros((S, S))
    wall[::16, :] = wall[:, ::32] = 1
    wall = ndimage.gaussian_filter(wall, 0.7)
    cells = [(y, x) for y in range(0, 64, 16) for x in range(0, 64, 16)]
    # Each object: 8 glyphs (not the 4 common ones) in 8 of the 16 cells of a 64x64 frame.
    objects = [[(cells[c], rng.integers(4, 40)) for c in rng.choice(16, 8, replace=False)]
               for _ in range(N)]
    db = [sift(render(rng, o, glyphs, wall)) for o in objects]
    queries = [sift(render(rng, o, glyphs, wall)) for o in objects]
    train = np.concatenate(db)
    train = train[rng.choice(len(train), 10000, replace=False)]
    results = {}
    for k in sizes:
        C = kmeans(train, k, rng)
        tf_db = np.array([np.bincount(quantize(d, C), minlength=k) for d in db], float)
        tf_q = np.array([np.bincount(quantize(d, C), minlength=k) for d in queries], float)
        df = (tf_db > 0).sum(0)                       # database images containing each word
        idf = np.log(N / np.maximum(df, 1))
        stop = np.argsort(-df)[: k // 20]             # stop list: 5% most frequent words
        for scheme in ["tf", "tf-idf", "tf-idf+stop"]:
            w = np.ones(k) if scheme == "tf" else idf.copy()
            w[stop if scheme == "tf-idf+stop" else []] = 0
            D = tf_db * w
            D /= np.linalg.norm(D, axis=1, keepdims=True) + 1e-12
            postings = {j: np.flatnonzero(D[:, j]) for j in range(k)}   # inverted file
            hits, read = 0, 0
            for i, t in enumerate(tf_q):
                q = t * w
                q /= np.linalg.norm(q) + 1e-12
                score = np.zeros(N)
                for j in np.flatnonzero(q):           # only the query's words are visited
                    ids = postings[j]
                    score[ids] += q[j] * D[ids, j]
                    read += len(ids)
                assert np.allclose(score, D @ q)      # same as the full cosine similarity
                hits += np.argmax(score) == i
            results[k, scheme] = hits / N, read / N
        results[k, "idf0"] = np.mean(df == N)         # fraction of words in every image
    return results

sizes, seeds = [16, 64, 256, 1024, 4096], [0, 1, 2]
runs = [run(s, sizes) for s in seeds]
print("top-1 accuracy, mean [min, max] over seeds 0-2; postings read per query (tf);")
print("fraction of words that occur in every database image (idf = 0)")
print(f"{'k':>5} {'tf':>17} {'tf-idf':>17} {'tf-idf+stop':>17} {'postings':>9} {'idf=0':>6}")
for k in sizes:
    row = []
    for scheme in ["tf", "tf-idf", "tf-idf+stop"]:
        acc = [r[k, scheme][0] for r in runs]
        row.append(f"{np.mean(acc):.2f} [{min(acc):.2f}, {max(acc):.2f}]")
    read = np.mean([r[k, "tf"][1] for r in runs])
    zero = np.mean([r[k, "idf0"] for r in runs])
    print(f"{k:>5} " + " ".join(f"{x:>17}" for x in row) + f" {read:>9.0f} {zero:>6.2f}")

Output (about 25 s on a laptop):

top-1 accuracy, mean [min, max] over seeds 0-2; postings read per query (tf);
fraction of words that occur in every database image (idf = 0)
    k                tf            tf-idf       tf-idf+stop  postings  idf=0
   16 0.03 [0.02, 0.03] 0.02 [0.02, 0.02] 0.02 [0.02, 0.02]       959   0.98
   64 0.13 [0.12, 0.15] 0.04 [0.02, 0.07] 0.04 [0.02, 0.07]      3566   0.43
  256 0.29 [0.23, 0.35] 0.53 [0.47, 0.60] 0.53 [0.47, 0.60]      6662   0.00
 1024 0.50 [0.40, 0.57] 0.87 [0.85, 0.90] 0.89 [0.88, 0.90]      4664   0.00
 4096 0.86 [0.80, 0.93] 0.97 [0.95, 1.00] 0.96 [0.92, 1.00]      2051   0.00

Accuracy rises with vocabulary size under every weighting, from chance with 16 words to nearly perfect with 4,096 words and idf, the direction Nistér and Stewénius and Philbin et al. reported for instance retrieval. Our interpretation: a small vocabulary puts the object’s glyphs in the same few cells as the brick corners and the common glyphs, so all histograms look alike, while a large one gives each glyph type words of its own. The largest vocabulary has fewer than three training descriptors per word and still works best, which suggests that splitting one pattern across several words costs little when the two views differ only by a similarity transform, lighting and noise; real viewpoint changes perturb descriptors more.

Inverse document frequency is the second lesson. From 256 words up, it raises accuracy by 0.1 to 0.4, the largest gains in the middle sizes, because the words generated by the wall and the common glyphs occur in most database images and get small weights, leaving the score to the object’s words. With 16 and 64 words it makes things worse: the last column shows that many of those words (almost all of the 16) occur in every database image and so get weight zero, which leaves the few remaining, noisy words to decide the ranking. The stop list changes almost nothing once idf is in place, as Nistér and Stewénius found on real data. The postings column shows the inverted file’s economy: the work per query first grows with $k$, as each image contains more distinct words, then falls as the lists shorten, and with 4,096 words a query reads about 2,000 entries out of the $60 \times 4{,}096$ in the full matrix.

Properties and Behavior

• Orderless. The histogram discards where words occur, so it is unchanged by any rearrangement of the patches, which brings tolerance to viewpoint change and deformation (and blindness to layout, under Limitations).
• Invariance is inherited. The representation is as invariant as its detector and descriptor. With scale- and rotation-covariant keypoints and SIFT it tolerates scale and rotation changes; Video Google’s affine covariant regions extended this to affine changes.
• Robustness to occlusion and clutter. An occluded object loses some words but keeps the rest, and background clutter adds words that another view of the object is unlikely to share. Csurka et al. showed images classified correctly although most interest points lay on the background.
• Sparsity. By simple arithmetic, the 3,300 regions that Philbin et al. detected on an average image can fill at most 0.33% of the entries of a million-word vector, which is what makes the inverted file efficient. Nistér and Stewénius noted that with a vocabulary tree each patch is stored as one or two integers instead of a 128-dimensional descriptor.
• Dataset dependence. A vocabulary reflects the descriptors it was trained on. Sivic and Zisserman (2003) used the vocabulary learned on one film unchanged on another and judged it expressive enough from example queries, but their journal version measured the cost: on Groundhog Day, mean average precision was 0.71 with the film’s own vocabulary, 0.31 with one built from Casablanca and 0.69 with the two concatenated (Sivic & Zisserman, 2009, Table 2). The Oxford–Paris experiment under Parameters shows the same effect.

Limitations

• No geometry. The plain histogram cannot tell an object from a scrambled arrangement of its parts. Csurka et al. expected that more categories would need geometric information; retrieval systems add a spatial verification stage, and classification systems spatial pyramids (see Variants).
• Quantization loss. Philbin et al. (2008) described hard assignment as a distance that is zero for the same word and infinite otherwise, and traced the descriptor variability that moves patches across cell boundaries to noise, illumination, detector instability and errors in the dominant orientation. Soft assignment, finer vocabularies with verification, and residual encodings such as VLAD reduce the loss but do not remove it.
• Burstiness. Repeated structure, such as windows on a facade, bricks, or the letters of text, produces many occurrences of the same word in one image. Jégou, Douze and Schmid (2009) showed an image of playing cards with 445 regions assigned to one word, measured on a million images that repeated occurrences are far more frequent than an independence model predicts, and argued that burstiness corrupts the similarity scores and that idf does not account for it, since idf weights a word by how many images contain it, not by how often it repeats within one. They proposed removing multiple matches between the same pair of images and down-weighting bursts within an image and across images.
• Scale of the index. Large vocabularies need large training sets, long clustering, and an index that grows with the number of descriptors; Philbin et al.’s index for 1.1 million images no longer fit in their machine’s memory. Jégou et al. (2010) motivated compact aggregated vectors by the memory and search cost of bag-of-words indexes beyond about 10 million images.
• Unsupervised words. The vocabulary is learned without labels, so frequent descriptors get many words whether or not they are discriminative; van Gemert et al. summarize work that reached the same observation and tried discriminative or class-specific vocabularies.

Variants

Vocabulary tree. Nistér and Stewénius (2006) built the vocabulary by hierarchical k-means: cluster the training descriptors into $b$ groups, then recursively cluster each group into $b$ subgroups, down to $L$ levels, giving $b^L$ leaf words. A descriptor is quantized by descending the tree, comparing it with $b$ centers per level. Every node, not only every leaf, can serve as a word with its own inverted file (the inner nodes’ files are virtual concatenations of their leaves’ files), so an image is scored hierarchically over several levels, with idf weights computed relative to the root; very long inverted files are blocked. The tree defines quantization and search together, made million-word vocabularies practical, and allowed new images to be inserted at the speed of feature extraction, which they planned to use for adding places on the fly in SLAM. Vocabulary trees and inverted indexes serve loop-closure detection in SLAM and the choice of image pairs to match in structure from motion, as those articles describe.

Approximate k-means (AKM). Philbin et al. (2007) kept flat k-means but replaced the exact nearest-center search in each iteration by approximate search in a forest of eight randomized k-d trees over the current centers, which reduces an iteration from $O(Mk)$ to $O(M \log k)$, the same time and memory complexity as the tree. For moderate $k$, fewer than 1% of points were assigned differently than by exact k-means, and mAP on Oxford 5K stayed within 0.011 of exact k-means (their Table 2; the text says less than 1%). They pointed out that hierarchical k-means minimizes distortion only locally within each node, and suggested that bad splits near the root send descriptors of the same scene region to different words. With one million words, AKM reached 0.618 mAP on Oxford 5K against 0.439 for the best tree configuration (their Table 4), and a Kentucky benchmark score of 3.45 against 3.29 using descriptors supplied by Nistér and Stewénius (their Table 3). The fast nearest-neighbor search that both methods depend on is the subject of approximate nearest-neighbor search.

Soft assignment. Philbin et al. (2008) applied the Gaussian weighting above with $r = 3$ nearest words and $\sigma^2 = 6{,}250$, a compromise between accuracy and cost, since results changed little across the settings they tried and more than four neighbors brought no gain. With one million words, bag-of-words mAP on Oxford 5K rose from 0.614 to 0.673 with an Oxford-trained vocabulary and from 0.403 to 0.494 with a Paris-trained one (their Table 3), the gain growing with vocabulary size; it persisted, smaller, after spatial re-ranking and query expansion. They also noted that hierarchical scoring in a vocabulary tree approximates soft assignment, but in their tests it did not do even as well as hard assignment. For classification, van Gemert et al. (2010) found codeword uncertainty the best of their three forms and better than hard assignment on all five datasets they tested; in a PASCAL VOC 2007 system with a spatial pyramid and several SIFT variants, it raised mean average precision from 0.580 with hard assignment to 0.605.

Spatial pyramid matching. Lazebnik, Schmid and Ponce (2006) restored coarse layout for classification by computing word histograms over the whole image and over $2 \times 2$, $4 \times 4$, … grids of subregions, and comparing two images by histogram intersection summed over levels, with matches first found at level $\ell$ of $L$ weighted by $1/2^{L-\ell}$, so that matches in finer cells count more. With $L = 0$ it is the ordinary bag of features; with $M$ words the concatenated vector has $M (4^{L+1} - 1)/3$ dimensions. On their 15-category scene dataset with 200-word vocabularies, accuracy rose from 72.2% for the plain histogram to 81.1% for a three-level pyramid (their Table 1), and they reported 64.6% on Caltech-101 with 30 training images per class.

Aggregating residuals: VLAD and Fisher vectors. Instead of only counting the descriptors in each cell, later encodings also record how they lie within it. VLAD (vector of locally aggregated descriptors; Jégou et al., 2010) sums, for each of $k$ words, the differences $x - c_i$ of the descriptors assigned to it, giving a $kd$-dimensional vector that is then ℓ2-normalized; the authors describe it as a simplification of the Fisher kernel representation that Perronnin and Dance (2007) applied to visual vocabularies, the Fisher vector described in image classification. Because each word carries $d$ numbers, far fewer words are needed: on the Holidays dataset, VLAD with 64 words reached 0.526 mAP against 0.404 for a 20,000-word bag of features, both at full dimension (their Table 1). These encodings, their normalization and their reduction with PCA are covered in embeddings and image classification; in video, the same counting and residual encodings were applied to dense trajectories.