VLAD

VLAD, the vector of locally aggregated descriptors, turns the set of local descriptors of an image into one fixed-length vector. Like the bag of visual words, it assigns each descriptor, for example a SIFT vector, to the nearest of $k$ visual words learned by k-means. Instead of counting how many descriptors fall on each word, it adds up their differences from the word’s centre, the residuals, and concatenates the $k$ sums into a vector of $k \times d$ numbers. Jégou, Douze, Schmid and Pérez introduced it in 2010 (CVPR) for image search at a scale where the descriptors of every image must fit in memory, and a journal version by Jégou, Perronnin, Douze, Sánchez, Pérez and Schmid followed in 2012 (TPAMI). Neither paper could be read for this article; it describes them through Arandjelović and Zisserman’s “All About VLAD” (2013), which reviews the encoding and its normalizations, and through later papers that analyse it (Tolias, Avrithis and Jégou, 2013; Jégou and Zisserman, 2014). Arandjelović and Zisserman called it the state-of-the-art compact descriptor in 2013; it was evaluated on instance-retrieval benchmarks such as Oxford Buildings and Holidays, and became the basis of DenseVLAD for visual place recognition, and, made differentiable, the NetVLAD layer of convolutional networks.

Problem

An image yields hundreds to thousands of local descriptors, and their number changes from image to image. Search and classification need one vector per image that can be compared with a dot product, stored compactly and indexed. The bag of visual words solves this with a histogram, but a histogram distinguishes descriptors only by which cell of the vocabulary they fall in, so it needs very large vocabularies (hundreds of thousands to millions of words) and sparse inverted files to be discriminative, and its index grows with the number of descriptors. Arandjelović and Zisserman summarize the aim behind VLAD as an image descriptor small enough (for example 16 bytes per image) that the descriptors of a billion-image collection could stay in main memory; they credit it with opening a line of research on the trade-off between memory per image and retrieval accuracy.

Inputs and Outputs

• Input: the local descriptors $X = \{x_1, \dots, x_n\}$ of one image, each $x \in \mathbb{R}^d$ (for SIFT, $d = 128$), and a vocabulary $C = \{c_1, \dots, c_k\}$ learned beforehand by k-means on descriptors of training images. All About VLAD describes $k$ as typically 64 or 256, so the cells are coarse.
• Output: a vector $v \in \mathbb{R}^{kd}$, normalized as described below, compared with other images’ vectors by the dot product (equivalently, by Euclidean distance between unit vectors). With $k = 64$ and SIFT it has 8,192 dimensions; full-size VLADs in All About VLAD’s tables have 20,000 to 32,000. For large collections the vector is then reduced, usually by principal component analysis with whitening, and compressed or indexed for approximate nearest-neighbour search.

Intuition

A bag of words records only that a descriptor fell into a cell. A coarse cell holds descriptors of many different patches, and the histogram cannot tell them apart. VLAD keeps, for each cell, the sum of the vectors that point from the centre to the descriptors in it: a $d$-dimensional summary of where in the cell the image’s descriptors lie. Two images that put descriptors in the same part of a cell get residual sums that point the same way, and their dot product is large; two images whose descriptors share the cell but lie on opposite sides of the centre get a negative contribution. Each word thus carries $d$ numbers instead of one, so far fewer words are needed. The cost is that the representation is dense, so it cannot use inverted files, and that it depends on where the centres are: All About VLAD’s Figure 1 shows the sign of a contribution flipping when the centre moves.

The second idea concerns weight. Because the residuals are summed, a block’s size grows with the number of descriptors in the cell. Repeated structure, such as the windows of a facade, a tiled floor or the letters of a text, produces many nearly identical descriptors in one cell, and that one block can dominate the whole vector and so the similarity. The normalizations that followed the original VLAD all aim at this effect, known as burstiness.

Algorithm

1. Vocabulary (offline). Run k-means on a sample of descriptors from training images, giving centres $c_1, \dots, c_k$.
2. Assign. For each descriptor $x$ of the image, find its nearest centre $\mathrm{NN}(x)$.
3. Aggregate. For each word $i$, sum the residuals $x - c_i$ of the descriptors assigned to it; a word with no descriptors gets a zero block. Concatenate the $k$ blocks into $v$ (the “unnormalized VLAD”, in All About VLAD’s term).
4. Normalize. Apply one of the normalizations below (none, $\ell_2$, signed square root then $\ell_2$, or intra-normalization then $\ell_2$).
5. Reduce and index (optional). Project with PCA, whiten and renormalize, and compress the result for search.
6. Compare. Score a query against database images by the dot product of their vectors.

Mathematical Formulation

The encoding

With $\mathrm{NN}(x) = \arg\min_i \lVert x - c_i \rVert$, the block of word $i$ is

$$v_i = \sum_{x \in X:\, \mathrm{NN}(x) = c_i} \left( x - c_i \right) \in \mathbb{R}^d, \qquad v = \left[ v_1^\top, \dots, v_k^\top \right]^\top \in \mathbb{R}^{kd}.$$

The block equals $n_i (\bar{x}_i - c_i)$, where $n_i$ is the number of descriptors assigned to word $i$ and $\bar{x}_i$ their mean: the count of the bag of words times the offset of the image’s descriptors from the centre. If the vocabulary is learned on the same collection, each centre is the mean of all descriptors assigned to it over that collection, so the residuals of one image measure how it departs from the average, an observation All About VLAD uses for vocabulary adaptation (below).

VLAD as a match kernel

Tolias, Avrithis and Jégou (2013) write VLAD and the bag of words in one framework of match kernels. The dot product of two VLADs decomposes over words, and within a word over pairs of descriptors:

$$v(X)^\top v(Y) = \sum_{i=1}^{k} v_i(X)^\top v_i(Y) = \sum_{i=1}^{k} \; \sum_{x \in X_i} \sum_{y \in Y_i} (x - c_i)^\top (y - c_i),$$

where $X_i$ and $Y_i$ are the descriptors of the two images assigned to word $i$ (their Eq. 10–12, up to the normalization factors). The bag of words is the same sum with every pair contributing 1. Two consequences follow from the formula. Only descriptors in the same cell interact, and every pair counts linearly: a cell with $n$ near-identical descriptors in one image and $m$ in the other contributes about $nm$ times as much as a single match. That is how bursts dominate. Jégou and Zisserman (2014) make the same point for any sum-aggregated embedding $\varphi$: the contribution of a descriptor $x$ to the self-similarity of its own set is $\lVert \varphi(x) \rVert^2 + \sum_{x' \neq x} \varphi(x)^\top \varphi(x')$ (their Eq. 8), so strong descriptors weigh quadratically and the second term, which they call interference, adds descriptors’ interactions with all others.

Normalizations

Let $v$ be the unnormalized VLAD.

• $\ell_2$ normalization, the original scheme as All About VLAD describes it: $v \leftarrow v / \lVert v \rVert_2$. It removes the dependence on the number of descriptors but not on how they are distributed over words.
• Signed square root (SSR), a form of power-law normalization: each component becomes $\operatorname{sign}(v_j) \lvert v_j \rvert^{\alpha}$ with $\alpha = 1/2$, followed by $\ell_2$ normalization. All About VLAD says SSR was introduced for VLAD by Jégou and Chum and by the 2012 journal version, following its use for Fisher vectors by Perronnin, Liu, Sánchez and Poirier (2010); Tolias et al. instead attribute the power-law normalization to Perronnin, Sánchez and Mensink (2010), and judge its effect similar to the burstiness weighting of Jégou, Douze and Schmid (2009). Jégou and Zisserman set $\alpha = 0.5$ as the standard value. It compresses large components and so discounts bursts, but cannot be expanded as a sum over pairs, as Tolias et al. note.
• Intra-normalization (Arandjelović and Zisserman, 2013): normalize each block separately, $v_i \leftarrow v_i / \lVert v_i \rVert_2$ for every non-empty block, then $\ell_2$-normalize the whole vector. After it, every non-empty word contributes the same energy, $1/m$ of the total if $m$ words are occupied, however many descriptors it holds. The similarity of two images becomes a sum of cosines between their residual sums in corresponding words, divided by $\sqrt{m_X m_Y}$: it depends on the directions of the aggregated residuals and not on their magnitudes, which is the geometric reading All About VLAD gives.

The three treat bursts differently. $\ell_2$ normalization lets a burst take as much of the vector as its residual sum is large; SSR, in Arandjelović and Zisserman’s words, only discounts it; intra-normalization caps it at one word’s share. Chen et al.’s alternative, as All About VLAD describes it, divides each block by its count (a mean instead of a sum), which still depends on the magnitude of the residuals.

For the bag of words, the burstiness weighting of Jégou, Douze and Schmid (2009) that Torii et al. (2013) describe multiplies the term frequency of a word occurring $n$ times in an image by $1/\sqrt{n}$; in our reading, this is the same square root applied to counts, and square-rooted counts are what the example below uses as its bag-of-words baseline.

Relation to Fisher vectors and NetVLAD

The Fisher vector, described in image classification, models descriptors with a Gaussian mixture and describes an image by the gradient of their log-likelihood with respect to the mixture’s parameters. All About VLAD calls the two similar in spirit, since both record aspects of the distribution of descriptors in each cell, and it groups VLAD with Fisher vectors and super-vector coding as encodings that record residuals; the published Bag of Visual Words article gives Jégou et al.’s description of VLAD as a simplification of the Fisher kernel. NetVLAD (Arandjelović, Gronat, Torii, Pajdla and Sivic, 2016) replaces the hard assignment, the only non-differentiable step, by a softmax over centres, so that VLAD becomes a layer of a convolutional network whose inputs are the activations of the last convolutional layer; its output is intra-normalized, flattened and $\ell_2$-normalized. The Visual Place Recognition article derives the layer and covers its training and results.

Parameters

• Vocabulary size $k$. It sets the dimension $kd$ and the coarseness of the cells. Small vocabularies suffice because each word stores $d$ numbers; All About VLAD uses $k = 256$ for its main results and $k = 64$ to make the blocks visible in its Figure 3. Larger $k$ separates more kinds of patch but leaves more words empty or holding a single descriptor, and lengthens the vector. The example below measures accuracy against $k$.
• Local descriptor. VLAD inherits the descriptor’s invariances. All About VLAD notes in-plane rotation invariance from SIFT and some tolerance to scaling and cropping, and uses RootSIFT descriptors of affine-invariant regions; DenseVLAD samples RootSIFT densely instead of at detected keypoints.
• Where the vocabulary comes from. A vocabulary learned on other images gives centres that are not the means of the cells’ descriptors on the new collection, and VLAD’s residuals depend on the centres. On Oxford 5k with full-size VLADs, All About VLAD measured the share of the mAP obtained with a vocabulary learned on Oxford 5k itself: with a Paris vocabulary, 98% for plain VLAD and 97% for VLAD with SSR, but with a Flickr60k vocabulary 61% and 68% (their Table 3). Centre adaptation (under Variants) raised the Flickr60k case to 86% when combined with intra-normalization.
• Normalization. All About VLAD recommends intra-normalization together with a good vocabulary or centre adaptation, because with inconsistent clusters and no adaptation SSR sometimes did better.
• Reduced dimension. After PCA and whitening, Jégou and Chum’s 128-dimensional VLADs are the comparison point of All About VLAD’s Table 2; the embeddings article explains why whitening helps and why renormalization after it matters.

Complexity

Assigning $n$ descriptors to $k$ centres by exhaustive search costs $O(nkd)$, the same as the bag of words with the same vocabulary, and aggregation adds $O(nd)$. Because $k$ is small, exhaustive assignment is cheap compared with the very large vocabularies of the bag of words, which need trees or approximate k-means. Memory is the opposite: a bag-of-words vector is sparse, with at most $n$ non-zero entries, while a VLAD is dense, $kd$ floats (32 KB per image for $k = 64$ and SIFT in single precision), which is why it is reduced and compressed before indexing. Comparing two full vectors costs $O(kd)$. All About VLAD reports, from Jégou and Chum, exhaustive search over one million 128-dimensional vectors in 6 ms per query on a 12-core machine.

Implementation

The example asks what each normalization does about bursts, and what VLAD’s vocabulary buys against a bag of words. Its images have a known answer and a controlled amount of repetition. Every image is 128 × 128 pixels on a grid of 16-pixel cells, each filled with a tile, a random 4 × 4 pattern of light and dark bits. An object is a 4 × 4 block of 16 tiles drawn from a pool of 120, placed near the centre and shifted by 0 or 8 pixels in each direction. The rest of the image is background. A fraction of its cells, the facade share (0, 0.5 or 1), repeat one “facade” tile, one of four per seed, like rows of identical windows; the other background cells get fresh random tiles, clutter that no other image shares. The facade tiles are aligned with the 16-pixel grid in every image. Each of 48 objects has one database image and one query; the query shows the object on a different facade, so 12 wrong database images share the query’s facade and the correct one never does. Blur, gain, offset and noise differ between the two views.

Local descriptors are dense DAISY descriptors from scikit-image (104 dimensions, every 8 pixels, centres at rows and columns $8i + 7$, $\ell_2$-normalized), 225 per image. Vocabularies are learned by k-means on 48 separate training images of other objects, drawn from the same tile pool and shown on the same four facades. Part A compares, at $k = 32$, VLAD with no normalization (ranked by Euclidean distance), with $\ell_2$, with SSR and $\ell_2$, and with intra-normalization and $\ell_2$ (ranked by dot product). An oracle encodes only the descriptors that lie wholly inside the object, using the generator’s mask: it checks that the object can be recognized from these descriptors at all. Part B varies $k$ from 4 to 1,024 and adds a bag of words with square-rooted counts on the same vocabulary. The measures are Recall@1 (Recall@K) with its range over five seeds, mean average precision (with one relevant image per query, the mean reciprocal rank of the correct image), the share of queries whose top result is a wrong object on the query’s facade, and the largest share of a vector’s squared norm held by one word’s block. At facade share 0 there is no facade, so the same-facade column there only counts wrong top results whose facade label matches the query’s.

The Visual Place Recognition article runs VLAD with intra-normalization at $k = 32$ on dense DAISY descriptors of a synthetic street whose buildings share four facade styles, and measures it against average pooling and geometric re-ranking, by day and night and with two vocabulary sources. This example fixes the pipeline instead and varies the normalization and the amount of repetition; the Bag of Visual Words article measures the bag of words alone against vocabulary size and term weighting.

The script loops over seeds 0–4 and ran in about 30 seconds (NumPy 2.3.5, SciPy 1.16.3, scikit-image 0.25.2, scikit-learn 1.7.2, Python 3.13).

import os
for var in ("OMP_NUM_THREADS", "OPENBLAS_NUM_THREADS", "MKL_NUM_THREADS"):
    os.environ[var] = "1"                      # one BLAS thread: reproducible sums
import sys
import numpy as np
from scipy.ndimage import gaussian_filter
from skimage.feature import daisy
from sklearn.cluster import KMeans

SIZE, TILE, NT = 128, 16, 8           # 128 x 128 images made of an 8 x 8 grid of 16-px cells
N_OBJ, N_FACADE, N_TRAIN = 48, 4, 48  # objects (= queries = database images), facades, training images
FACADE_SHARES = (0.0, 0.5, 1.0)       # share of background cells covered by the repeated facade tile
K_MAIN = 32                           # vocabulary for the normalization comparison
K_SWEEP = (4, 8, 16, 32, 64, 128, 256, 1024)
SEEDS = [int(sys.argv[1]) + i for i in range(5)] if len(sys.argv) > 1 else [0, 1, 2, 3, 4]
REACH = len(sys.argv) > 2 and sys.argv[2] == "reach"   # reachable values: facade share 0 only


def random_tile(rng):
    """A 16 x 16 cell: a random 4 x 4 binary pattern (grey 0.2 / 0.8), each bit 4 x 4 px."""
    while True:
        bits = rng.random((4, 4)) < 0.5
        if 0 < bits.sum() < 16:
            return np.kron(np.where(bits, 0.8, 0.2), np.ones((4, 4)))


def render(rng, obj_tiles, facade, share):
    """Background cells: the facade tile on round(share*64) random cells, a fresh random
    tile elsewhere. A 4 x 4 block of the object's tiles (64 x 64 px) near the centre,
    shifted by a whole descriptor step (8 px) or not at all in each direction."""
    n_fac = int(round(share * NT * NT))
    is_fac = np.zeros(NT * NT, bool)
    is_fac[rng.permutation(NT * NT)[:n_fac]] = True
    img = np.empty((SIZE, SIZE))
    for i in range(NT * NT):
        r, c = divmod(i, NT)
        img[r * TILE:(r + 1) * TILE, c * TILE:(c + 1) * TILE] = facade if is_fac[i] else random_tile(rng)
    r0, c0 = 32 + 8 * rng.integers(-1, 2, size=2)       # object position: 24, 32 or 40 px
    for i in range(16):
        r, c = divmod(i, 4)
        img[r0 + r * TILE:r0 + (r + 1) * TILE, c0 + c * TILE:c0 + (c + 1) * TILE] = obj_tiles[i]
    img = gaussian_filter(img, 0.7)
    img = rng.uniform(0.8, 1.2) * img + rng.uniform(-0.1, 0.1)   # gain and offset
    img = img + rng.normal(0, 0.02, img.shape)
    return img, (r0, c0), n_fac


def describe(img, corner):
    """Dense DAISY descriptors (unit l2 norm) every 8 px; mask of those whose
    15 x 15 support lies inside the object block."""
    d = daisy(img, step=8, radius=7, rings=2, histograms=6, orientations=8, normalization="l2")
    rows = np.arange(d.shape[0]) * 8 + 7                 # descriptor centres
    cols = np.arange(d.shape[1]) * 8 + 7
    r0, c0 = corner
    inr = (rows - 7 >= r0) & (rows + 7 < r0 + 64)
    inc = (cols - 7 >= c0) & (cols + 7 < c0 + 64)
    return d.reshape(-1, d.shape[2]), np.outer(inr, inc).ravel()


def assign(X, C):
    d2 = (X ** 2).sum(1)[:, None] - 2 * X @ C.T + (C ** 2).sum(1)[None, :]
    return d2.argmin(1)


def vlad(X, C):
    a = assign(X, C)
    V = np.zeros_like(C)
    np.add.at(V, a, X - C[a])                            # sum of residuals per word
    return V


def l2(v):
    return v / np.linalg.norm(v)


def normalize(V, how):
    if how == "none":
        return V.ravel()
    if how == "L2":
        return l2(V.ravel())
    if how == "SSR+L2":
        return l2(np.sign(V.ravel()) * np.sqrt(np.abs(V.ravel())))
    if how == "intra+L2":
        n = np.linalg.norm(V, axis=1, keepdims=True)
        return l2((V / np.where(n > 0, n, 1)).ravel())
    raise ValueError(how)


def bow(X, C):
    h = np.bincount(assign(X, C), minlength=len(C)).astype(float)
    return l2(np.sqrt(h))                                # square-rooted counts, l2


def retrieve(Q, D, euclid):
    """Rank of the correct database image (query i <-> database image i) and the top-1 index."""
    if euclid:
        score = -((Q ** 2).sum(1)[:, None] - 2 * Q @ D.T + (D ** 2).sum(1)[None, :])
    else:
        score = Q @ D.T
    order = np.argsort(-score, axis=1, kind="stable")
    rank = np.array([np.where(order[i] == i)[0][0] + 1 for i in range(len(Q))])
    return rank, order[:, 0]


def top_block_share(V):
    """Largest share of a vector's squared norm held by one word's block (k x d layout)."""
    e = (V ** 2).sum(1)
    return e.max() / e.sum()


METHODS = ("none", "L2", "SSR+L2", "intra+L2")
shares = FACADE_SHARES[:1] if REACH else FACADE_SHARES
resA = {}    # (share, method) -> list of (R@1, mAP, same-facade errors, top-block share) per seed
resB = {}    # (share, k, method) -> list of R@1 per seed
datachk = {}
for seed in SEEDS:
    rng = np.random.default_rng(seed)
    pool = [random_tile(rng) for _ in range(120)]                 # object tiles
    facades = [random_tile(rng) for _ in range(N_FACADE)]
    objects = [rng.choice(120, 16, replace=False) for _ in range(N_OBJ)]
    db_fac = np.arange(N_OBJ) % N_FACADE                         # database facade of object o
    q_fac = (db_fac + 1) % N_FACADE                              # query sees another facade

    # vocabulary: k-means on descriptors of separate training images (other objects, all shares)
    Xtr = []
    for t in range(N_TRAIN):
        tiles = [pool[j] for j in rng.choice(120, 16, replace=False)]
        img, corner, _ = render(rng, tiles, facades[rng.integers(N_FACADE)], FACADE_SHARES[t % 3])
        Xtr.append(describe(img, corner)[0])
    Xtr = np.vstack(Xtr)
    vocab = {k: KMeans(n_clusters=k, n_init=1, max_iter=100, random_state=seed).fit(Xtr).cluster_centers_
             for k in K_SWEEP}

    for share in shares:
        views = {}
        for side, fac in (("db", db_fac), ("q", q_fac)):
            Xs, Ms, nf = [], [], []
            for o in range(N_OBJ):
                img, corner, n_fac = render(rng, [pool[j] for j in objects[o]], facades[fac[o]], share)
                X, M = describe(img, corner)
                Xs.append(X); Ms.append(M); nf.append(n_fac)
            views[side] = (Xs, Ms, nf)
        Xd, Md, nfd = views["db"]
        Xq, Mq, nfq = views["q"]
        C = vocab[K_MAIN]
        top_word = np.mean([np.bincount(assign(X, C), minlength=K_MAIN).max() / len(X) for X in Xd])
        sharing = [int(np.sum(db_fac == q_fac[o])) for o in range(N_OBJ)]
        correct_shares = int(np.sum(db_fac == q_fac))
        datachk.setdefault(share, []).append((np.mean(nfd + nfq) / 64, len(Xd[0]), np.mean([m.sum() for m in Md]),
                                              top_word, min(sharing), max(sharing), correct_shares))

        # part A: normalizations at k = 32, plus the oracle that sees only object descriptors
        Vd = [vlad(X, C) for X in Xd]
        Vq = [vlad(X, C) for X in Xq]
        rows = {"oracle (object only), intra+L2": (
            np.array([normalize(vlad(X[M], C), "intra+L2") for X, M in zip(Xq, Mq)]),
            np.array([normalize(vlad(X[M], C), "intra+L2") for X, M in zip(Xd, Md)]), False, None)}
        for how in METHODS:
            Dn = np.array([normalize(V, how) for V in Vd])
            Qn = np.array([normalize(V, how) for V in Vq])
            tb = np.mean([top_block_share(v.reshape(K_MAIN, -1)) for v in Dn])
            rows[how] = (Qn, Dn, how == "none", tb)
        for name, (Qn, Dn, euclid, tb) in rows.items():
            rank, top = retrieve(Qn, Dn, euclid)
            wrong_same = np.mean((top != np.arange(N_OBJ)) & (db_fac[top] == q_fac))
            resA.setdefault((share, name), []).append((np.mean(rank == 1), np.mean(1 / rank), wrong_same, tb))
        # exact check: after intra-normalization every non-empty block holds 1/m of the energy
        dev = max(abs(top_block_share(normalize(V, "intra+L2").reshape(K_MAIN, -1)) * np.sum(np.abs(V).sum(1) > 0) - 1)
                  for V in Vd)
        resA.setdefault((share, "intra check"), []).append(dev)

        # part B: vocabulary size against dimension, at facade shares 0 and 0.5 (0 only in reach mode)
        if share in (0.0, 0.5):
            for k in K_SWEEP:
                Ck = vocab[k]
                Vd_k = [vlad(X, Ck) for X in Xd]
                Vq_k = [vlad(X, Ck) for X in Xq]
                for how in METHODS[1:]:
                    rank, _ = retrieve(np.array([normalize(V, how) for V in Vq_k]),
                                       np.array([normalize(V, how) for V in Vd_k]), False)
                    resB.setdefault((share, k, "VLAD " + how), []).append(np.mean(rank == 1))
                rank, _ = retrieve(np.array([bow(X, Ck) for X in Xq]), np.array([bow(X, Ck) for X in Xd]), False)
                resB.setdefault((share, k, "BoW"), []).append(np.mean(rank == 1))


def mr(vals):
    v = np.array(vals)
    return f"{v.mean():.2f} [{v.min():.2f}, {v.max():.2f}]"


print(f"seeds {SEEDS}; {N_OBJ} queries, {N_OBJ} database images, 1 correct each; chance R@1 = {1 / N_OBJ:.3f}")
for share in shares:
    d = np.array(datachk[share])
    print(f"\nfacade share {share:.1f}: facade cells/64 = {d[:, 0].mean():.3f}, descriptors/image = {int(d[0, 1])}, "
          f"object-only descriptors = {d[:, 2].mean():.1f}, share in most used word (k=32) = {d[:, 3].mean():.2f}")
    print(f"  database images sharing the query's facade: {int(d[:, 4].min())}-{int(d[:, 5].max())}; "
          f"correct image shares it: {int(d[:, 6].max())}")
    print(f"  {'k = 32':32s} {'R@1 mean [min, max]':20s} {'mAP':>5s} {'same-facade err':>16s} {'top block':>10s}")
    for name in ["oracle (object only), intra+L2", *METHODS]:
        r = np.array(resA[(share, name)], dtype=object)
        tb = "" if r[0, 3] is None else f"{np.mean(r[:, 3].astype(float)):.3f}"
        print(f"  {name:32s} {mr(r[:, 0].astype(float)):20s} {np.mean(r[:, 1].astype(float)):5.2f} "
              f"{np.mean(r[:, 2].astype(float)):16.2f} {tb:>10s}")
    print(f"  intra check: max |m * top-block share - 1| = {max(resA[(share, 'intra check')]):.1e}")

for share in [s for s in (0.0, 0.5) if s in shares]:
    print(f"\nvocabulary size at facade share {share}: R@1 mean [min, max] over seeds (D = 104)")
    print(f"{'k':>5s} {'VLAD dim':>9s} {'VLAD L2':>18s} {'VLAD SSR+L2':>18s} {'VLAD intra+L2':>18s} {'BoW (sqrt) dim k':>18s}")
    for k in K_SWEEP:
        print(f"{k:5d} {k * 104:9d} " + " ".join(f"{mr(resB[(share, k, m)]):>18s}" for m in
              ("VLAD L2", "VLAD SSR+L2", "VLAD intra+L2", "BoW")))

seeds [0, 1, 2, 3, 4]; 48 queries, 48 database images, 1 correct each; chance R@1 = 0.021

facade share 0.0: facade cells/64 = 0.000, descriptors/image = 225, object-only descriptors = 49.0, share in most used word (k=32) = 0.08
  database images sharing the query's facade: 12-12; correct image shares it: 0
  k = 32                           R@1 mean [min, max]    mAP  same-facade err  top block
  oracle (object only), intra+L2   1.00 [1.00, 1.00]     1.00             0.00           
  none                             0.54 [0.48, 0.58]     0.67             0.10      0.125
  L2                               0.66 [0.58, 0.71]     0.77             0.08      0.125
  SSR+L2                           0.77 [0.69, 0.85]     0.85             0.07      0.071
  intra+L2                         0.77 [0.67, 0.85]     0.86             0.05      0.035
  intra check: max |m * top-block share - 1| = 6.7e-16

facade share 0.5: facade cells/64 = 0.500, descriptors/image = 225, object-only descriptors = 49.0, share in most used word (k=32) = 0.10
  database images sharing the query's facade: 12-12; correct image shares it: 0
  k = 32                           R@1 mean [min, max]    mAP  same-facade err  top block
  oracle (object only), intra+L2   1.00 [1.00, 1.00]     1.00             0.00           
  none                             0.03 [0.00, 0.06]     0.13             0.97      0.138
  L2                               0.02 [0.00, 0.06]     0.12             0.98      0.138
  SSR+L2                           0.04 [0.00, 0.10]     0.17             0.96      0.075
  intra+L2                         0.11 [0.02, 0.17]     0.26             0.89      0.035
  intra check: max |m * top-block share - 1| = 8.9e-16

facade share 1.0: facade cells/64 = 1.000, descriptors/image = 225, object-only descriptors = 49.0, share in most used word (k=32) = 0.20
  database images sharing the query's facade: 12-12; correct image shares it: 0
  k = 32                           R@1 mean [min, max]    mAP  same-facade err  top block
  oracle (object only), intra+L2   1.00 [1.00, 1.00]     1.00             0.00           
  none                             0.00 [0.00, 0.00]     0.05             1.00      0.346
  L2                               0.00 [0.00, 0.00]     0.07             1.00      0.346
  SSR+L2                           0.03 [0.00, 0.04]     0.13             0.97      0.165
  intra+L2                         0.91 [0.81, 1.00]     0.95             0.09      0.040
  intra check: max |m * top-block share - 1| = 6.7e-16

vocabulary size at facade share 0.0: R@1 mean [min, max] over seeds (D = 104)
    k  VLAD dim            VLAD L2        VLAD SSR+L2      VLAD intra+L2   BoW (sqrt) dim k
    4       416  0.18 [0.17, 0.21]  0.18 [0.12, 0.21]  0.18 [0.12, 0.21]  0.05 [0.00, 0.10]
    8       832  0.26 [0.15, 0.35]  0.29 [0.12, 0.33]  0.29 [0.25, 0.33]  0.05 [0.00, 0.12]
   16      1664  0.44 [0.35, 0.50]  0.51 [0.42, 0.60]  0.47 [0.42, 0.58]  0.07 [0.04, 0.10]
   32      3328  0.66 [0.58, 0.71]  0.77 [0.69, 0.85]  0.77 [0.67, 0.85]  0.10 [0.04, 0.15]
   64      6656  0.95 [0.94, 0.98]  0.99 [0.98, 1.00]  0.98 [0.96, 1.00]  0.23 [0.12, 0.29]
  128     13312  1.00 [0.98, 1.00]  1.00 [1.00, 1.00]  1.00 [1.00, 1.00]  0.37 [0.27, 0.52]
  256     26624  1.00 [1.00, 1.00]  1.00 [1.00, 1.00]  1.00 [1.00, 1.00]  0.72 [0.67, 0.77]
 1024    106496  1.00 [1.00, 1.00]  1.00 [1.00, 1.00]  1.00 [1.00, 1.00]  1.00 [1.00, 1.00]

vocabulary size at facade share 0.5: R@1 mean [min, max] over seeds (D = 104)
    k  VLAD dim            VLAD L2        VLAD SSR+L2      VLAD intra+L2   BoW (sqrt) dim k
    4       416  0.00 [0.00, 0.00]  0.00 [0.00, 0.00]  0.00 [0.00, 0.00]  0.00 [0.00, 0.02]
    8       832  0.00 [0.00, 0.00]  0.00 [0.00, 0.00]  0.00 [0.00, 0.00]  0.00 [0.00, 0.00]
   16      1664  0.00 [0.00, 0.00]  0.00 [0.00, 0.00]  0.00 [0.00, 0.00]  0.00 [0.00, 0.00]
   32      3328  0.02 [0.00, 0.06]  0.04 [0.00, 0.10]  0.11 [0.02, 0.17]  0.00 [0.00, 0.00]
   64      6656  0.26 [0.21, 0.35]  0.60 [0.48, 0.69]  0.85 [0.79, 0.94]  0.00 [0.00, 0.00]
  128     13312  0.67 [0.52, 0.83]  0.96 [0.90, 1.00]  1.00 [0.98, 1.00]  0.00 [0.00, 0.00]
  256     26624  0.92 [0.83, 1.00]  1.00 [1.00, 1.00]  1.00 [1.00, 1.00]  0.00 [0.00, 0.00]
 1024    106496  1.00 [1.00, 1.00]  1.00 [1.00, 1.00]  1.00 [1.00, 1.00]  0.00 [0.00, 0.00]

The data and the label check. The facade covers exactly the planned share of cells, every query has 12 wrong database images on its facade and the correct image never shares it, and the share of an image’s descriptors in its most used word rises from 0.08 to 0.10 to 0.20 as the facade spreads: the bursts are in the data. The oracle finds the right image for every query at every share, so the object can be recognized from these descriptors and this vocabulary, and any failure of the full-image vectors comes from the rest of the image. The exact check confirms that after intra-normalization each of the $m$ occupied blocks holds $1/m$ of the energy, to rounding error.

Bursts and normalization (part A). Without a facade, all four vectors find most objects (Recall@1 0.54 to 0.77 against a chance level of 0.02), with SSR and intra-normalization ahead of $\ell_2$ and the unnormalized vector. As the facade spreads, $\ell_2$ VLAD collapses, from 0.66 to 0.02 to 0.00, and the unnormalized vector likewise; at share 1 every query’s top result is a wrong object on the query’s facade. The top-block column shows why: with the facade everywhere, one word holds on average 35% of the energy of an $\ell_2$-normalized database vector, and by construction the 12 wrong images contain the same facade tile at the same alignment, so their descriptors fall in the same words. SSR halves that share (0.165) but still fails (0.03). Intra-normalization keeps every block at about 1/25 to 1/29 of the energy (0.035 to 0.040) and recovers 0.91 at share 1. The pattern resembles All About VLAD’s Figure 3, which plots the energy of each dimension across the Holidays images: concentrated in a few components under $\ell_2$, discounted by SSR, with no peaks after intra-normalization.

For intra-normalization at $k = 32$, share 0.5 is harder than share 1: it reaches only 0.11 there, against 0.77 without a facade and 0.91 with a full one (the other three vectors score no higher at share 1 than at share 0.5). No hypothesis predicted this. In our reading, at share 1 the background consists of a few appearance types (the facade tile seen at the few offsets the 8-pixel grid allows), which occupy a few words, and the object’s descriptors have the other words to themselves; at share 0.5 the clutter tiles scatter descriptors into every word, so each block of the correct image mixes object residuals with clutter that differs between query and database, while the facade descriptors, identical in the query and the wrong images, still give those images a few blocks with cosine near 1. Part B is consistent with this reading: at share 0.5, intra-normalized VLAD reaches 0.85 at $k = 64$ and 1.00 at $k = 128$, where finer words can separate object patches from clutter.

Vocabulary size and dimension (part B). Without a facade, VLAD needs about 64 words (6,656 dimensions) to find nearly every object, while the bag of words, on the same vocabularies, needs 1,024 words: at every $k$ up to 256 it is far behind (0.05 to 0.72 against 0.18 to 1.00). At equal dimension the order reverses: the 1,024-word bag of words (1,024 dimensions) reaches 1.00, VLAD with 8 or 16 words (832 or 1,664 dimensions) 0.29 and 0.47 with intra-normalization. Words, not dimensions, are what VLAD saves. With half the background a facade, the bag of words scores a mean of 0.00 at every vocabulary size, even with 1,024 words (its only success is one query in one seed at $k = 4$). A short derivation shows how little it takes. With square-rooted counts $\sqrt{n_j}$, the squared norm of an image’s vector is $\sum_j n_j = 225$, the number of descriptors, so the cosine of two images is $\sum_j \sqrt{n_j m_j} / 225$. A word that holds $n$ identical facade descriptors in both the query and a wrong image contributes $n/225$, while each object patch that falls in its own word once in each image contributes $1/225$; in our reading, the facade descriptors whose support lies inside a single facade cell (by construction, 64 of the 225 descriptor positions, 8 of 15 along each axis, have their 15 × 15 support inside one 16-pixel cell), nearly identical in every image with that facade, outweigh the object patches that land in the same word in the query and its true match. Intra-normalized VLAD, which caps the facade’s words, reaches 1.00 from $k = 128$; $\ell_2$ VLAD needs 1,024 words to reach 1.00.

Planned hypotheses. The example was planned before it ran, with these hypotheses, and every outcome below is read from the output above.

• The Recall@1 of $\ell_2$ VLAD and of the unnormalized vector falls with every increase of the facade share (0.66, 0.02, 0.00 and 0.54, 0.03, 0.00): held. At share 1, more than half of $\ell_2$’s errors are same-facade errors (all of them: 1.00 of the queries, all wrong): held.
• At shares 0.5 and 1, intra-normalization scores at least as high as SSR and SSR at least as high as $\ell_2$ (0.11, 0.04, 0.02 and 0.91, 0.03, 0.00): held. The drop in Recall@1 from share 0 to share 1 is smaller for intra-normalization than for $\ell_2$: held, since intra-normalization does not drop at all (0.77 to 0.91, a gain of 0.14) while $\ell_2$ loses 0.66; it does not stay level along the way (0.77, 0.11, 0.91).
• The top-block share is ordered $\ell_2$ > SSR > intra-normalization at every share (0.125 > 0.071 > 0.035, 0.138 > 0.075 > 0.035, 0.346 > 0.165 > 0.040), with the unnormalized vector equal to $\ell_2$, and $\ell_2$’s share rises with the facade (0.125, 0.138, 0.346): held.
• At share 0.5, intra-normalized VLAD scores at least as high as the bag of words with the same vocabulary for every $k$ up to 256: held from $k = 8$ on, with ties at $k = 8$ and 16, where both score 0.00 in every seed, and VLAD ahead from $k = 32$ (0.11, 0.85, 1.00, 1.00 against 0.00). At $k = 4$ both means print as 0.00, but the ranges show the bag of words finding one query in one seed ([0.00, 0.02]) and intra-normalized VLAD none in any seed ([0.00, 0.00]), so the bag of words’ mean is the higher one there and the hypothesis failed at $k = 4$.
• At share 0.5, the 1,024-word bag of words scores higher than intra-normalized VLAD with 8 and 16 words: this hypothesis failed. All three score 0.00. The prediction came from the planning run at share 0, not from a source; at share 0 the order does hold, as above.

The example was planned before it ran. A planning run of an earlier version, with a smaller 3 × 3 object that moved by up to 2 pixels, failed its label check, so before any pilot the object was enlarged to 4 × 4 tiles and moved only in whole 8-pixel steps; the burst mechanism was not changed. A pilot with other seeds (200–204) ran every part, the editor approved the set-up unchanged, and the output above is the first run with seeds 0–4, run twice with identical output.

Properties and Behavior

• Orderless. Like the bag of words, VLAD ignores where descriptors occur in the image, which tolerates viewpoint change and occlusion and cannot tell an object from a rearrangement of its parts.
• Compact before compression. Each word stores a $d$-dimensional sum, so small vocabularies are discriminative. All About VLAD’s Table 1, which takes most figures from the 2012 journal version, lists on Holidays 0.526 mAP for VLAD and 0.598 with SSR, against 0.452 for a 20,000-dimensional bag of words, 0.540 for a 200,000-dimensional one and 0.626 for the improved Fisher vector; Arandjelović and Zisserman’s own centre adaptation with intra-normalization reached 0.646 on average over four vocabularies (0.555 on Oxford 5k, where their re-implementation of VLAD with SSR, with better detector and descriptor, scored 0.532).
• Reducible. VLADs reduced to 128 dimensions by PCA and whitening kept much of their accuracy: in All About VLAD’s Table 2, 0.510 mAP on Holidays for VLAD, 0.557 with SSR and 0.625 for their method with Jégou and Chum’s multiple vocabularies, against 0.452 for a reduced bag of words and 0.365 for GIST. On Holidays with a million Flickr distractors their 128-dimensional vectors scored 0.378.
• Burst-sensitive unless normalized. Under $\ell_2$ normalization the energy concentrates in a few components (All About VLAD, Figure 3); intra-normalization spreads it evenly by construction, as the example’s exact check shows. On Holidays with $k = 64$ and a Paris vocabulary with centre adaptation, intra-normalization improved mAP by 7.2% relative to SSR and 13.5% relative to plain VLAD (Figure 3 caption), and with centre adaptation it beat adaptation with SSR by an average relative 4.7% and 6.6% on Oxford 5k and Holidays (section 4, Figure 2).
• Vocabulary-dependent. Because the residuals are measured from the centres, a vocabulary from a different distribution can change the sign of a word’s contribution; this is what centre adaptation corrects.
• Repetition can be information. Torii et al. (2013) argue that repeated structures such as facades, fences and road markings, while they violate the independence assumed by the bag of words, distinguish many places when they are represented appropriately; they detect repeated groups of features and adapt the bag-of-words weights instead of simply down-weighting bursts.

Limitations

• No geometry and no local descriptors at search time. A VLAD system usually keeps no local descriptors in memory, so it cannot re-rank by spatial verification as bag-of-words systems do; All About VLAD names this as a difference from the bag-of-words approach.
• Small objects and scale. A single VLAD describes the whole image, so an object that covers a small part of it contributes a small part of the vector. All About VLAD describes VLAD as weaker than the bag of words for such objects and less invariant to scale changes, and introduced MultiVLAD for them.
• Sensitivity to the vocabulary. Results depend on the data the centres were learned on (Parameters).
• Fixed, unweighted cells. Every word counts equally after intra-normalization, including words that hold one noisy or background descriptor; in the example, intra-normalization at $k = 32$ fails at facade share 0.5 (Recall@1 0.11), which in our reading is clutter sharing words with the object. Selective kernels and democratic aggregation (below) address this in different ways.
• Dense, high-dimensional vectors. Full VLADs are long and dense, so large collections need dimensionality reduction and vector compression, with a loss of accuracy at short lengths (All About VLAD, Table 2 against Table 1).

Variants

PCA, whitening and multiple vocabularies. Jégou and Chum (2012) reduced VLADs by PCA with whitening and aggregated with four vocabularies, as All About VLAD describes; the Embeddings article explains why centring and whitening help retrieval.

Centre adaptation. Arandjelović and Zisserman (2013) recompute each centre as the mean of the collection’s descriptors assigned to it and recompute the residuals from the adapted centres. Because the assignments do not change, it is enough to store each image’s per-word sums of descriptors, so the original descriptors are not needed. With a Flickr60k vocabulary on Oxford 5k, the mean displacement between adapted and original centres was 0.209 for unit-norm RootSIFT descriptors, against 0.022 with a Paris vocabulary; on Holidays, adaptation raised mAP from 0.432 to 0.474 with a Paris vocabulary and from 0.380 to 0.509 with “no vocabulary” (the first $k$ descriptors as centres).

MultiVLAD. The same paper stores 14 VLADs per image, over a 3 × 3 grid, a 2 × 2 grid and the whole image, computed together from an integral image of unnormalized VLADs, and scores a database image by its best tile. For objects covering less than about 11% of an Oxford image, mAP rose to 0.102 from 0.025 for a single 128-dimensional VLAD and 0.073 for a 1,792-dimensional one of the same storage. Regressing the tile similarities on tile overlaps also localizes the object.

Selective match kernels (ASMK). Tolias, Avrithis and Jégou (2013) keep VLAD’s per-word sum of residuals but $\ell_2$-normalize it, which equals intra-normalization of the block, and pass the cosine between two images’ normalized sums through a selectivity function, $\sigma_\alpha(u) = \operatorname{sign}(u) \lvert u \rvert^{\alpha}$ for $u > \tau$ and 0 otherwise, typically with $\alpha = 3$, which suppresses weak, likely false matches. They use vocabularies of 8k to 65k words (65k unless stated otherwise), also with binarized residuals (ASMK*), and note that normalizing the aggregated vector keeps one representative of all bursty descriptors in a word, like binary bag of words or max pooling. The image retrieval article reports ASMK’s results on the revisited benchmarks.

Triangulation embedding and democratic aggregation. Jégou and Zisserman (2014) separate embedding from aggregation. Their embedding encodes each descriptor by its normalized residuals to all anchors, keeping directions and discarding distances; their aggregation weights the descriptors so that each contributes about equally to the set’s self-similarity, solved by a Sinkhorn-like scaling stopped after 10 iterations. They found it complementary to power-law normalization and not worth its cost for more than 128 anchors, and they rotate the vectors by PCA before the power law so that it addresses co-occurrences as well as bursts.

DenseVLAD and NetVLAD. DenseVLAD, by Torii et al. (2015) as the place-recognition article describes it, aggregates densely sampled RootSIFT into an intra-normalized VLAD for place recognition, and NetVLAD learns soft assignments and centres end to end inside a convolutional network; the Visual Place Recognition article covers both with their benchmarks, and the Embeddings article covers learned global descriptors in general.

Compression for search. Compact codes for reduced VLADs are the subject of product quantization; the search structures that use them are covered in the Approximate Nearest Neighbor Search article.