Image Retrieval

Image retrieval, or content-based image retrieval (CBIR), searches a collection of images using an image as the query. Given a photograph of a building, a product or a painting, the system ranks the collection so that the images showing the same thing come first: other photographs of that building from other viewpoints, other copies of the painting, other items of the same kind. It is search by example rather than by keywords, and the everyday phrasings for it are “reverse image search”, “find similar images” and “where else does this picture appear”. Retrieval is also a component of larger systems: structure from motion uses it to choose which image pairs to match, visual localization and loop closure in SLAM use it to recognize places, and image–text retrieval applies the same ranking machinery across modalities.

This article is the hub for the task. The representations it relies on have their own articles: the bag of visual words (vocabularies, tf-idf and inverted files), embeddings (global image vectors and their normalization), similarity and distance measures, metric learning, and approximate nearest neighbor search for searching large galleries. The ranking metrics are Recall@K and average precision.

Problem Definition

A database (also called the gallery or index set) $\mathcal{X} = \{x_1, \dots, x_N\}$ of images is given in advance and may be preprocessed. At query time a query image $q$, or a region of it, arrives, and the system returns a permutation of $\mathcal{X}$, usually only its first $K$ entries, ordered by decreasing relevance. Relevance is defined by the benchmark, not by the system: in instance-level retrieval a database image is relevant when it depicts the same physical object or scene as the query; in category-level retrieval when it depicts something of the same class.

Smeulders, Worring, Santini, Gupta and Jain (2000), reviewing the field’s early years, distinguished three aims a user may have: target search, for one specific image or for other images of an object the user has a picture of; category search, for any image representative of a class; and search by association, browsing without a precise aim and refining the query interactively. Most of what follows concerns target search by example, which is what the standard benchmarks measure.

Two assumptions are usually made. The database is large compared with the number of relevant images per query, so most of the ranking is spent separating a few true matches from many distractors. And the query is unseen: nothing about it, including its own image in the database, may be used before it is issued, a point the revisited Oxford and Paris protocol makes explicit (below).

Input and Output

The input is a query image, sometimes with a bounding box that marks the object of interest (all Oxford and Paris queries are such regions), and a database that has been processed offline into an index: inverted files of visual words, a matrix of global descriptors, or compressed codes. The output is a ranked list of database identifiers, often with scores, and optionally the region or transformation that locates the query object in each result.

Every system has the same three parts:

• Representation. Each image becomes either a set of local descriptors (hundreds to thousands of vectors, each attached to a keypoint with position, scale and orientation, such as SIFT) or one global descriptor, a vector $f(x) \in \mathbb{R}^d$, usually $\ell_2$-normalized so that for unit vectors $\lVert u - v \rVert^2 = 2 - 2\cos(u, v)$ and Euclidean and cosine rankings agree.
• Indexing and search. Local descriptors are quantized into visual words and searched through an inverted file, as the bag of visual words article describes; global descriptors are searched exhaustively by a matrix product or with an approximate index such as an inverted file with product quantization or a proximity graph, as in approximate nearest neighbor search.
• Ranking and re-ranking. The first, cheap ranking of the whole collection is refined on its head by more expensive steps: geometric verification of local matches, query expansion, diffusion over a neighborhood graph.

Variants

• Instance and landmark retrieval. Find every image of the same object: a building, a painting, a book cover, a product. Landmark retrieval, on Oxford, Paris and Google Landmarks, is the most studied case, because photo-sharing sites supply many views of the same places. Weyand, Araujo, Cao and Sim (2020) pair it with landmark recognition, which predicts a landmark label (or none) for each query instead of a ranking.
• Category-level retrieval. Relevance means sharing a class, as in the deep metric learning benchmarks on bird species, car models and online products described in metric learning and Recall@K. The descriptor must then be invariant to the differences between instances, which instance retrieval must keep.
• Near-duplicate and copy detection. Find edited copies of one image (cropped, rescaled, recompressed, overlaid); relevance is narrower than in instance retrieval, and the Easy setup of the revisited Oxford benchmark was judged by its authors still useful for it.
• Visual place recognition. Find database photographs taken near the query’s location, with relevance defined by GPS distance; NetVLAD, below, was designed for it.
• Person re-identification and product search. Re-identification retrieves images of the same person across cameras; product search retrieves catalogue items from a shopper’s photograph. Both are instance retrieval over a specialized domain, usually with descriptors trained by metric learning.
• Cross-modal retrieval. A sentence queries images or an image queries captions; the image–text retrieval article covers it, including joint embeddings such as CLIP. Sketch-based retrieval, where a drawing queries photographs, is another cross-modal variant.

Challenges

Smeulders et al. (2000) named two gaps that still organize the difficulties. The sensory gap lies between an object in the world and what a recording of it captures, so that viewpoint, illumination, occlusion and clutter change the image of one object; the semantic gap lies between what can be computed from the pixels and what the image means to the user. Instance retrieval is mostly a fight with the first, category retrieval with the second.

• Viewpoint, scale and illumination. A landmark photographed from the side, at night or from far away shares few local patterns with a frontal daytime query. The revisited Oxford and Paris annotation labels such views Hard and scores them separately.
• Small objects and clutter. When the object covers a small part of a database image, a global descriptor of the whole image is dominated by everything else; Iscen et al. (2017) describe small objects as a common failure case of CNN-based retrieval.
• Repeated and ambiguous structure. Windows, bricks and text produce many identical local patterns (the burstiness discussed in bag of visual words), and different buildings of one architectural style share them; Philbin et al. (2007) chose building facades as their test domain and described them as challenging for this reason.
• Scale. A database of millions of images must fit in memory and answer in a fraction of a second. Radenović et al. (2018, Table 4) measured 62.0 GB for an ASMK index of local features over ROxford with one million distractors, against 7.68 GB for ResNet-101 GeM global descriptors.
• Few relevant images. Re-ranking methods that spread relevance from the top results (query expansion, diffusion) need several correct results to start from, and hurt queries that have only a few (Radenović et al., 2018).

Approaches

From global features to local features

The early systems that Smeulders et al. reviewed described whole images by color, texture and shape features and compared them with histogram distances (see similarity and distance measures). Such features cannot find an object that occupies part of an image under a new viewpoint. Local invariant features changed this: a SIFT descriptor matches the same patch across large changes of view, and an object is found when many of its patches match. Matching every descriptor of the query against every database image is too slow, which is the problem the bag of visual words solved: Sivic and Zisserman (2003) searched quantized descriptors through an inverted file as text engines do, and the vocabulary tree (Nistér & Stewénius, 2006) and approximate k-means (Philbin et al., 2007) scaled the vocabularies to a million words.

Two refinements reduced the errors that quantization introduces. Philbin et al. (2008) assigned each descriptor softly to several nearby words. Jégou, Douze and Schmid (2008) kept a coarse vocabulary but attached to each descriptor a binary signature encoding where it lies within its visual word’s cell (Hamming embedding), so that two descriptors match only if they share the word and their signatures are within a Hamming threshold; their weak geometric consistency filtered matches whose differences in orientation and scale disagreed with the dominant ones in the image pair. Later match kernels on the inverted file, such as ASMK, extend Hamming embedding and handle burstiness; Radenović et al. (2018) use them as their strongest local-feature baselines.

Spatial verification

A bag of words ignores where the words are, so an image that contains the same patterns in another arrangement scores as well as a true match. Spatial verification re-ranks the top of the list by checking that the matched features are consistent with one geometric transformation between the query region and the database image. Philbin et al. (2007) treated pairs of features assigned to the same visual word as tentative correspondences and estimated the transformation with LO-RANSAC, a variant of RANSAC. Because each of their features is an affine-covariant region, a single correspondence already fixes a restricted transformation (translation with isotropic or anisotropic scaling, or with vertical shear: 3 to 5 degrees of freedom, keeping images upright); they could therefore enumerate every hypothesis instead of sampling, which made the procedure deterministic, and refined the best ones to a full affine transformation using the inliers. A database image counted as verified with at least four inliers; verified images were placed above unverified ones and scored by the sum of the idf weights of their inlier words, and up to the top 1,000 images were checked, stopping early after 20 consecutive failures.

On Oxford 5K, verification raised mAP from 0.385 to 0.560 with a 20,000-word vocabulary when re-ranking the top 800 (5-degree-of-freedom hypotheses), but only from 0.618 to 0.664 with a million words (their Table 7); the more discriminative the first stage, the less is left to fix. Verification also produces the inlier count, which Radenović et al. (2018) called one of the most intuitive similarity measures, and the transformation, which tells where the object lies in the result. The general machinery of tentative matches and robust model fitting is in feature matching and homography estimation.

Query expansion

A query region shows only some of the features of its object; a database image of the object from another side shares too few of them to rank high. Query expansion, borrowed from text retrieval, issues a second query built from the best results of the first. In text, it can drift when the top results are wrong. Chum, Philbin, Sivic, Isard and Zisserman (2007) observed that spatial verification makes visual query expansion safe, because the results used to expand the query can be verified first, and its transformation maps each result’s features back into the query region. Their average query expansion (AQE) averages the query’s normalized term-frequency vector $d_0$ with those of the $m$ top verified results,

$$d_{\mathrm{avg}} = \frac{1}{m + 1} \left( d_0 + \sum_{i=1}^{m} d_i \right), \qquad m < 50,$$

using the features of each result that fall inside the back-projected query region, and re-queries once. They also tested transitive closure, recursive averaging and averaging within resolution bands. On Oxford with 100,000 distractor images, mean mAP over the 55 queries rose from 55.0 without expansion to 71.1 with average expansion and 78.2 with resolution expansion, while the naive text-style baseline, averaging the top five results without verification, scored 52.9, below no expansion (their Table 2). Arandjelović and Zisserman (2012) replaced the average by a linear SVM trained with the verified results as positives and low-ranked images as negatives (discriminative query expansion); in their consistent reimplementation on Oxford 5K with SIFT, mAP went from 0.636 for tf-idf ranking to 0.672 with spatial re-ranking, 0.839 with average expansion and 0.847 with the discriminative version (their Table 1). The related database-side augmentation expands each database image offline with the words of its verified neighbors.

With global descriptors, expansion averages descriptors instead of word histograms. Radenović, Tolias and Chum (2019; details here and below from the arXiv version, 1711.02512v2) found the number of averaged images, $n_{\mathrm{QE}}$, hard to tune across datasets with different numbers of relevant images per query, and proposed α-weighted query expansion (αQE): average the top $n_{\mathrm{QE}}$ descriptors with weights $(\bar f(q)^\top \bar f(x_i))^\alpha$, the similarity to the query raised to a power, which reduces to AQE for $\alpha = 0$. They set $\alpha = 3$ and $n_{\mathrm{QE}} = 50$.

Diffusion

Query expansion uses only the query’s direct neighbors. Diffusion propagates relevance further, along a graph of the database’s own nearest-neighbor relations, so that an image reachable from the query through a chain of similar images ranks high even if it is far from the query itself. Iscen, Tolias, Avrithis, Furon and Chum (2017) follow Zhou et al.’s ranking on data manifolds: with an affinity matrix $A$ of pairwise similarities kept only between mutual $k$-nearest neighbors, its symmetric normalization $\mathcal{S} = D^{-1/2} A D^{-1/2}$ ($D$ the diagonal degree matrix), and a vector $y$ marking the query’s nearest neighbors, the ranking scores are

$$f^\star = (1 - \alpha)\,(I - \alpha \mathcal{S})^{-1} y ,$$

the limit of repeatedly spreading scores to neighbors with probability $\alpha$ and returning to the query with probability $1 - \alpha$. They solve this sparse system by conjugate gradients, use similarities $\max(x^\top z, 0)^3$ and $\alpha = 0.99$, and diffuse over descriptors of image regions rather than whole images, which helped most when the query object is small. Radenović et al. (2018) found diffusion among the strongest re-ranking methods on the revisited benchmarks, but also that it, like query expansion, degrades queries with few relevant images, because the query’s nearest neighbors then include false positives; starting it from images verified with local features worked better.

Deep global descriptors

From 2014, activations of convolutional networks replaced aggregated local features as global descriptors. The first studies, the off-the-shelf features of Razavian et al. and the neural codes of Babenko, Slesarev, Chigorin and Lempitsky (2014), and the PCA whitening that retrieval descriptors need are covered in embeddings; Babenko et al. found that retraining on landmark photos helped landmark retrieval and hurt retrieval of indoor objects. Later work pooled the last convolutional feature map $\mathcal{X}_k$, $k = 1, \dots, K$, instead of using fully connected layers:

• MAC and R-MAC. Taking the maximum of each channel gives the MAC vector (maximum activations of convolutions). Tolias, Sicre and Jégou (2016) computed it over square regions sampled at $L$ scales with about 40% overlap ($L = 3$ in their experiments), $\ell_2$-normalized, PCA-whitened and renormalized each regional vector, and summed them into one $K$-dimensional R-MAC vector, which encodes several regions at the cost of one; the same activations let them localize the query object for re-ranking. Gordo, Almazán, Revaud and Larlus (2017) showed that R-MAC can be written as a differentiable network and trained it end to end with a triplet loss on an automatically cleaned set of landmark photos.
• NetVLAD. Arandjelović, Gronat, Torii, Pajdla and Sivic (2016) turned VLAD into a trainable layer by replacing the hard assignment of each local feature to its nearest cluster with a softmax over distances, and trained it for place recognition with a weakly supervised triplet ranking loss on Google Street View Time Machine panoramas, whose only labels are approximate GPS positions.
• GeM. Radenović, Tolias and Chum (2019) pooled each channel by a generalized mean,

$$f_k = \left( \frac{1}{|\mathcal{X}_k|} \sum_{x \in \mathcal{X}_k} x^{p_k} \right)^{1/p_k},$$

which is average pooling (SPoC) for $p_k = 1$ and tends to max pooling as $p_k \to \infty$; $p_k$ is learned by backpropagation, and a single shared $p$ worked better than one per channel. They fine-tuned networks with a contrastive loss on matching and non-matching pairs mined from 3D models that a retrieval and structure-from-motion pipeline had reconstructed from unlabeled photo collections, with no human annotation, learned the whitening from the same pairs, and searched by exhaustive inner products of the $\ell_2$-normalized vectors.

A global descriptor costs 4 bytes per dimension and one matrix product per query, can be compressed further, and needs no geometry in the index; it pays for this with weaker invariance to small objects and clutter. Deep local features were trained too: Radenović et al. (2018) evaluated DELF, a learned local feature, extracted at most 1,000 per image, inside the same ASMK and spatial-verification pipeline as hand-crafted features.

Combining both

On the revisited benchmarks no single method was best everywhere. In Radenović et al.’s evaluation (2018, Table 5; mAP, Medium protocol), local features with ASMK and spatial verification reached 60.6 on ROxford and 46.8 with a million distractors, against 64.7 and 45.2 for a fine-tuned ResNet-101 with GeM; GeM was clearly better on RParis (77.2 against 61.4). Re-ranking added more: GeM with αQE reached 67.2 on ROxford and with diffusion 69.8, and diffusion started from spatially verified local-feature results 79.1. The authors read this as evidence that each family has its own benefits. Spatial verification itself added little to these strong first stages, at most about two points (ASMK 60.4 to 60.6 on ROxford, 45.0 to 46.8 with distractors), compared with Philbin et al.’s gains of 2007. Systems in the Google Landmarks challenges described by Weyand et al. (2020) followed the same pattern: an ensemble of global descriptors for the first ranking, then local-feature re-ranking, query expansion or database-side augmentation.

Example: Spatial Verification and Query Expansion on Synthetic Photographs

The script builds a small instance-retrieval benchmark whose ground truth is known exactly. Each of 30 objects is a planar layout of 12 distinct glyphs in a $4 \times 4$ grid, drawn from a pool of 40 random glyphs, so different objects share many glyphs and differ mainly in their arrangement. The query shows the left three quarters of an object almost frontally, like an Oxford query region. The database holds, for each object, three views of increasing difficulty: the whole object under a mild rotation, the right three quarters under up to 25° of rotation with foreshortening, and the right half under up to 40° with more foreshortening, which shares only one column of glyphs with the query. Each object also has a scrambled copy, its own 12 glyphs placed in other cells, and there are 30 unrelated objects: 150 database images, 3 relevant per query. Every image has a cluttered background, three stray glyphs, an illumination change and noise; intensities are in $[0, 1]$.

Keypoints and descriptors come from scikit-image 0.25.2’s SIFT, converted to RootSIFT; a 1,024-word vocabulary is learned with NumPy k-means on 15,000 database descriptors, and images are ranked by the cosine of their $\ell_2$-normalized tf-idf vectors (the inverted file is omitted, since the bag-of-visual-words article shows it gives the same scores). Spatial verification of the top 30 follows Philbin et al. (2007) in spirit: every pair of features with the same word proposes a similarity transform from the two keypoints’ positions, scales and orientations, all hypotheses are scored, the best is refined by a least-squares affine fit, and an image is verified with at least 30 inliers, a threshold we chose by inspecting inlier counts on this benchmark, above those of most scrambled copies (a few reach it). Average query expansion follows Chum et al. (2007) with the five best verified images, but averages whole-image tf-idf vectors and does not verify the expanded query’s results. The same expansion with the five best unverified results is the naive baseline. Average precision is computed with the trapezoidal rule of the official Oxford and revisitop code. The script runs in about 25 seconds with NumPy 2.3.5 and SciPy 1.16.3.

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

S, CELL, G = 128, 24, 40  # image size; layout cell size (pixels); glyph pool size


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


def layout(rng):
    """An object: 12 distinct glyphs in 12 of the 16 cells of a 4x4 grid (96x96 pixels)."""
    cells = rng.choice(16, 12, replace=False)
    return list(zip(cells, rng.choice(G, 12, replace=False)))


def render(rng, obj, glyphs, cols=(0, 4), rot=10, aniso=0.0):
    """One photograph, intensities in [0, 1]: the object's glyphs in columns cols[0]..cols[1]-1,
    under a random rotation (up to rot degrees), scale and foreshortening (aniso), on a
    cluttered background, with an illumination change and noise."""
    panel, mask = np.zeros((96, 96)), np.zeros((96, 96))
    for c, g in obj:
        y, x = divmod(c, 4)
        if cols[0] <= x < cols[1]:
            y0, x0 = CELL * y + 4, CELL * x + 4
            panel[y0:y0 + 15, x0:x0 + 15] = glyphs[g]
    mask[:, CELL * cols[0]:CELL * cols[1]] = 1
    a = np.deg2rad(rng.uniform(-rot, rot))
    s = rng.uniform(0.85, 1.15)
    R = np.array([[np.cos(a), -np.sin(a)], [np.sin(a), np.cos(a)]])
    A = R @ np.diag([s, s * (1 - rng.uniform(0, aniso))])          # panel -> image
    centre = np.array([48, CELL * (cols[0] + cols[1]) / 2])
    Ainv = np.linalg.inv(A)
    off = centre - Ainv @ (np.array([S / 2, S / 2]) + rng.uniform(-8, 8, 2))
    warp = lambda z: ndimage.affine_transform(z, Ainv, off, output_shape=(S, S), order=1)
    o, m = warp(panel), warp(mask)
    img = 0.5 + 0.08 * ndimage.gaussian_filter(rng.standard_normal((S, S)), 3)
    for _ in range(3):                                              # clutter glyphs
        y, x = rng.integers(0, S - 15, 2)
        img[y:y + 15, x:x + 15] = 0.25 + 0.5 * glyphs[rng.integers(G)]
    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.02, img.shape), 0, 1)


def features(img):
    """SIFT keypoints (row, col), scales and orientations; RootSIFT descriptors."""
    det = SIFT()
    det.detect_and_extract(img)
    d = np.sqrt(det.descriptors / det.descriptors.sum(1, keepdims=True))
    return det.keypoints.astype(float), det.sigmas, det.orientations, d


def kmeans(X, k, rng, iters=10):
    C = X[rng.choice(len(X), k, replace=False)].copy()
    for _ in range(iters):
        lab = quantize(X, C)
        for j in np.unique(lab):
            C[j] = X[lab == j].mean(0)
    return C


def quantize(X, C):
    return np.argmin((C ** 2).sum(1) - 2 * X @ C.T, axis=1)


def verify(fq, fd, wq, wd, idf, eps=3.0):
    """Spatial verification in the manner of Philbin et al. (2007): every tentative
    correspondence (same visual word) proposes a similarity transform from its two
    keypoints' positions, scales and orientations; all hypotheses are scored, and the
    best is refined by a least-squares affine fit to its inliers. Returns the idf
    sum of the inlier words and the number of inliers."""
    i, j = np.nonzero(wq[:, None] == wd[None, :])
    if len(i) < 3:
        return 0.0, 0
    p, q = fq[0][i], fd[0][j]
    sc = fd[1][j] / fq[1][i]
    th = fd[2][j] - fq[2][i]
    c, s = np.cos(th), np.sin(th)
    # Hypothesis h maps p to sc_h * R_h p + t_h; skimage orientations are measured in
    # (row, col) coordinates, so R rotates (row, col) vectors.
    R = np.stack([np.stack([c, -s], -1), np.stack([s, c], -1)], -2) * sc[:, None, None]
    t = q - np.einsum('hab,hb->ha', R, p)
    pred = np.einsum('hab,nb->hna', R, p) + t[:, None, :]
    err = np.linalg.norm(pred - q[None], axis=2)
    scale_ok = np.abs(np.log(sc[None, :] / sc[:, None])) < np.log(1.5)
    inl = (err < eps) & scale_ok
    best = inl[np.argmax(inl.sum(1))]
    if best.sum() >= 3:                                             # affine refinement
        P = np.c_[p[best], np.ones(best.sum())]
        M = np.linalg.lstsq(P, q[best], rcond=None)[0]
        best = np.linalg.norm(np.c_[p, np.ones(len(p))] @ M - q, axis=1) < eps
    # Count each query feature and each database feature at most once.
    _, first = np.unique(i[best], return_index=True)
    keep = np.flatnonzero(best)[first]
    keep = keep[np.unique(j[keep], return_index=True)[1]]
    return idf[wq[i[keep]]].sum(), len(keep)


def average_precision(ranked_pos, n_pos):
    """AP as the Oxford Buildings / revisitop code computes it: trapezoids under the
    precision-recall curve; ranked_pos are the 0-based ranks of the positives."""
    ap = 0.0
    for k, r in enumerate(ranked_pos):
        p0 = 1.0 if r == 0 else k / r
        ap += (p0 + (k + 1) / (r + 1)) / (2 * n_pos)
    return ap


def evaluate(rankings, gt):
    aps, hit = [], []
    for order, pos in zip(rankings, gt):
        ranks = np.flatnonzero(np.isin(order, pos))
        aps.append(average_precision(ranks, len(pos)))
        hit.append(order[0] in pos)
    return np.mean(aps), np.mean(hit)


def run(seed, n_obj=30, k=1024, top=30, min_inl=30, m_qe=5):
    rng = np.random.default_rng(seed)
    glyphs = make_glyphs(rng)
    objs = [layout(rng) for _ in range(n_obj)]
    db, owner = [], []
    for o, obj in enumerate(objs):
        db += [render(rng, obj, glyphs, (0, 4), rot=10),               # whole object, mild
               render(rng, obj, glyphs, (1, 4), rot=25, aniso=0.2),    # right 3/4, harder
               render(rng, obj, glyphs, (2, 4), rot=40, aniso=0.35)]   # right half, hardest
        owner += [o, o, o]
        scrambled = list(zip(rng.permutation([c for c, _ in obj]), [g for _, g in obj]))
        db.append(render(rng, scrambled, glyphs, (0, 4), rot=10))      # same glyphs, moved
        owner.append(-1)
    for _ in range(n_obj):                                              # unrelated objects
        db.append(render(rng, layout(rng), glyphs, (0, 4), rot=25, aniso=0.2))
        owner.append(-1)
    owner = np.array(owner)
    queries = [render(rng, obj, glyphs, (0, 3), rot=5) for obj in objs]  # left 3/4
    gt = [np.flatnonzero(owner == o) for o in range(n_obj)]

    fdb = [features(x) for x in db]
    fq = [features(x) for x in queries]
    X = np.concatenate([f[3] for f in fdb])
    C = kmeans(X[rng.choice(len(X), min(len(X), 15000), replace=False)], k, rng)
    wdb = [quantize(f[3], C) for f in fdb]
    wq = [quantize(f[3], C) for f in fq]
    tf = lambda w: np.bincount(w, minlength=k).astype(float)
    Tdb = np.array([tf(w) for w in wdb])
    idf = np.log(len(db) / np.maximum((Tdb > 0).sum(0), 1))
    unit = lambda v: v / (np.linalg.norm(v, axis=-1, keepdims=True) + 1e-12)
    D = unit(Tdb * idf)                                     # tf-idf, l2-normalized
    Q = unit(np.array([tf(w) for w in wq]) * idf)

    bow = np.argsort(-(Q @ D.T), axis=1)                    # 1. bag of words
    sv, qe, naive, stats = [], [], [], []
    for n, order in enumerate(bow):
        head = order[:top]                                  # 2. spatial re-ranking
        res = [verify(fq[n], fdb[d], wq[n], wdb[d], idf) for d in head]
        score = np.array([r[0] if r[1] >= min_inl else -1.0 for r in res])
        ok = head[score > 0][np.argsort(-score[score > 0], kind='stable')]
        rest = np.array([d for d in order if d not in set(ok)])
        sv.append(np.r_[ok, rest])
        top5 = order[:m_qe]
        stats.append([(owner[top5] == n).sum(), np.isin(top5, np.arange(3, 4 * n_obj, 4)).sum(),
                      (owner[ok] == n).sum(), (owner[ok] != n).sum()])
        # 3. average query expansion with the verified images (Chum et al., 2007)
        e = unit(Q[n] + D[ok[:m_qe]].sum(0))
        later = np.argsort(-(D @ e))
        qe.append(np.r_[ok[:m_qe], [d for d in later if d not in set(ok[:m_qe])]])
        # 4. the same expansion with the unverified top results
        e = unit(Q[n] + D[order[:m_qe]].sum(0))
        later = np.argsort(-(D @ e))
        naive.append(np.r_[order[:m_qe], [d for d in later if d not in set(order[:m_qe])]])
    hard = [g[owner[g] >= 0][2:] for g in gt]               # the hardest view only
    out = {name: evaluate(r, gt) for name, r in
           [("bag of words", bow), ("+ spatial verification", sv),
            ("+ verified query expansion", qe), ("unverified query expansion", naive)]}
    rank_hard = {name: np.median([np.flatnonzero(r == h[0])[0] + 1 for r, h in zip(rr, hard)])
                 for name, rr in [("bag of words", bow), ("+ spatial verification", sv),
                                  ("+ verified query expansion", qe),
                                  ("unverified query expansion", naive)]}
    return out, rank_hard, np.mean([len(f[0]) for f in fdb]), np.mean(stats, 0)


seeds = [0, 1, 2]
runs = [run(s) for s in seeds]
print(f"{len(seeds)} seeds; 30 queries and 150 database images per seed; "
      f"{np.mean([r[2] for r in runs]):.0f} SIFT keypoints per image")
print(f"{'':28}{'mAP':>20}{'R@1':>20}{'hardest view, median rank':>28}")
for name in runs[0][0]:
    m = [r[0][name][0] for r in runs]
    h = [r[0][name][1] for r in runs]
    rk = [r[1][name] for r in runs]
    print(f"{name:28}{np.mean(m):.3f} [{min(m):.3f}, {max(m):.3f}]"
          f"   {np.mean(h):.2f} [{min(h):.2f}, {max(h):.2f}]"
          f"      {np.mean(rk):5.1f} [{min(rk):.0f}, {max(rk):.0f}]")
st = np.mean([r[3] for r in runs], 0)
print(f"per query: bag-of-words top 5 holds {st[0]:.1f} correct views and {st[1]:.1f} "
      f"scrambled copies; {st[2]:.1f} correct and {st[3]:.1f} wrong images verified")

Output (mean [min, max] over seeds 0–2; the median rank of the hardest view is taken over queries and averaged over seeds):

3 seeds; 30 queries and 150 database images per seed; 228 SIFT keypoints per image
                                             mAP                 R@1   hardest view, median rank
bag of words                0.479 [0.465, 0.498]   0.97 [0.93, 1.00]       98.3 [80, 123]
+ spatial verification      0.626 [0.613, 0.634]   1.00 [1.00, 1.00]       98.3 [80, 123]
+ verified query expansion  0.702 [0.685, 0.715]   1.00 [1.00, 1.00]       22.8 [11, 35]
unverified query expansion  0.488 [0.480, 0.503]   0.97 [0.93, 1.00]       80.0 [54, 94]
per query: bag-of-words top 5 holds 1.6 correct views and 1.6 scrambled copies; 1.8 correct and 0.3 wrong images verified

R@1 is near perfect from the start and says almost nothing: the mild full view of the object is easy to find, and the hit rate stops looking after it, as the Recall@K article explains. Mean average precision, which needs all three views, starts below one half. The diagnostic line shows why: the bag of words ranks the scrambled copies as high as the true views, because they contain exactly the object’s glyphs. Spatial verification separates them, since a copy’s matches agree with no single transformation, and raises mean mAP by about 0.15, so that the worst seed after verification scores above the best seed before it; it verifies about 1.8 of the 3 correct images per query and lets about 0.3 wrong ones through, by our reading mostly images in which two glyphs happen to keep their relative position.

Verification cannot help the hardest view, which shares one column of glyphs with the query: its median rank is near 100 of 150, so for most queries it lies outside the top 30 that verification examines. Query expansion can: the verified full view contains the right half of the object, so the expanded query shares many more words with the hardest view, whose median rank improves about fourfold and lifts mAP by another 0.08. The same expansion from the five unverified top results barely moves mAP, because, in our interpretation of the diagnostic line, only about a third of the five images it averages are correct views, and the rest, scrambled copies and other wrong images, pull the expanded query toward their words. This reproduces at small scale Chum et al.’s argument that verification is what makes visual query expansion work. The example has no viewpoint change out of the plane and only 150 images; the magnitudes are not those of real benchmarks.

Datasets and Benchmarks

Benchmark	Images	Queries	Relevance	Official score
UKBench (Nistér & Stewénius, 2006)	10,200 (2,550 objects × 4)	every image	the other images of its group of four	mean number of the group’s 4 images in the top 4, from 0 to 4
INRIA Holidays (Jégou et al., 2008)	1,491 in 500 groups	500 (first image of each group)	the rest of the group	mAP, query ignored
Oxford 5K (Philbin et al., 2007)	5,062	55 regions, 11 landmarks	Good and OK; Junk ignored	mAP
Paris 6K (Philbin et al., 2008)	6,412 listed, 20 corrupted	55 regions, 11 landmarks, as documented by Arandjelović & Zisserman (2012) and Radenović et al. (2018)	as Oxford	mAP
ROxford, RParis (Radenović et al., 2018)	4,993 and 6,322, plus R1M distractors	70 each	Easy, Hard, Unclear by protocol	mAP and mP@K, Easy, Medium and Hard setups
Google Landmarks v2 (Weyand et al., 2020)	4.1M train, 762K index	118K (1/3 public, 2/3 private)	index images of the same landmark	mAP@100 (retrieval), GAP (recognition)

UKBench. The University of Kentucky recognition benchmark consists of groups of four $640 \times 480$ photographs of one object each, from CD covers to flowers and computer equipment. The sources describe it differently, and the official page reconciles them. Nistér and Stewénius’s CVPR 2006 paper used the 6,376 images they had at the time, or a subset of about 1,400, and their default measure, which they called quite unforgiving, was how many percent of the other three images in each group were “found perfectly” (at the top of the ranking, by our reading of their figure caption). The full, revised set on the official page has 10,200 images (2,550 groups; the page warns that results on the first version it published, which had duplicated and transposed images, are invalid), and the page defines the score now in use: for each query, count how many of the four images of its group are among the top four results, and average over all queries. The page’s scoring code counts the query itself, so a perfect system scores 4 and one that finds only the query scores 1. Philbin et al. (2007) and Babenko et al. (2014) report this 0-to-4 score on the 10,200 images without saying whether the query is counted. Because it is, a top-4 score is not a recall of the three other images (a score of 3 means two of the three were found); it is four times the precision at 4.

INRIA Holidays. Jégou, Douze and Schmid (2008) collected 1,491 photographs, mainly their own holiday photos, in 500 groups of one scene or object; the first image of each group is the query and the rest of the group its relevant results. Some images are not upright, and results on the manually rotated version that Babenko et al. (2014) and several earlier papers used are not comparable with results on the original; the protocol is described in Oxford Buildings.

Oxford 5K and Paris 6K. Philbin et al. (2007) collected 5,062 Flickr photographs of Oxford, chose five query regions on each of 11 landmarks, and labeled every image for every landmark as Good, OK, Junk or Absent; Good and OK images are positives, and Junk images are removed from the ranked list before scoring, so returning them neither helps nor hurts. Paris 6K, collected the same way from Paris landmarks, served Philbin et al. (2008) only to train vocabularies and later became a second test set with 55 queries; the collections, their distractor sets and their image counts are described in Oxford Buildings.

Revisited Oxford and Paris. Radenović, Iscen, Tolias, Avrithis and Chum (2018) relabeled both datasets after finding annotation errors and near-perfect scores that no longer separated methods: every image is now Easy, Hard, Unclear or Negative for each query group, 15 harder queries were added to each dataset (70 per dataset), the Easy, Medium and Hard setups count different labels as positive, and the R1M set adds a million distractors. On the revisited annotation, a fine-tuned ResNet-101 GeM descriptor scored 84.8, 64.7 and 38.5 mAP on ROxford in the Easy, Medium and Hard setups, against 87.8 on the original Oxford (their Table 3). The authors consider Easy saturated and report Medium and Hard; the labels, setups and distractors are described in Oxford Buildings.

Google Landmarks Dataset v2. Weyand et al. (2020) built GLDv2 from Wikimedia Commons: a training set of 4.1 million images of 203,000 landmarks, an index set of 762,000 images of 101,000 landmarks, and 118,000 query images (117,577 queries and 761,757 index images in the dataset repository’s README), with images under licenses that allow redistribution. Its class distribution is extremely long-tailed, and most query images show no landmark at all, so a system must also know when nothing matches. The query set is split randomly into a third for validation, used for the public leaderboard of the 2019 Kaggle challenges, and two thirds for testing. A cleaned training subset of 1.6 million images and 81,000 landmarks was made by keeping images that could be verified with local features. As a baseline, a ResNet-101 with GeM pooling trained with an ArcFace loss on the cleaned set reached 24.15 mAP@100 on the test split (Table 5 of the CVPR version; 25.57 in the revised arXiv version, 2004.01804v2).

Evaluation Metrics

Retrieval benchmarks score rankings, and the metric is defined by each benchmark’s official code, which differs in details that change the numbers.

Average precision. Oxford, Paris and their revisited versions report mean average precision over queries, but their official code, like that of Holidays, computes it as a sum of trapezoids under the precision–recall curve, starting from precision 1 at recall 0, rather than as the textbook non-interpolated AP, the mean of the precision at each positive. For one positive at rank $r$ (1-based), the trapezoid gives $1/(2r)$ for $r > 1$ and 1 for $r = 1$, half the textbook value of $1/r$ at every rank below the first (our arithmetic from the code); the two rules converge as queries have more positives, and Oxford Buildings describes how the code removes Junk and ignored images.

Precision at K. revisitop also reports mean precision at rank $K$ (mP@K, for $K = 1, 5, 10$), which the authors note reflects what a user sees; in its code the denominator is the smaller of $K$ and the rank of the last positive retrieved, as Oxford Buildings explains.

mAP@100 and GAP. Google Landmarks v2 scores retrieval by AP truncated at 100 results,

$$\mathrm{AP@100}(q) = \frac{1}{\min(m_q, 100)} \sum_{k=1}^{\min(n_q, 100)} P_q(k)\, \mathrm{rel}_q(k),$$

with $m_q$ the number of relevant index images and $n_q$ the number of predictions, averaged over the queries that have at least one relevant index image; queries without one are ignored, so retrieving images for a non-landmark query is not penalized. The official code (metrics.py, commit 3dacd47) uses the non-interpolated sum of precisions, skips duplicate predictions, and drops the queries marked “Ignored” in the solution file. Recognition is scored by global average precision (GAP, or micro AP): one predicted label and confidence per query, all predictions sorted by confidence across queries, and the precision at each correct prediction summed and divided by the number of queries that show a landmark, which, unlike mAP@100, penalizes confident predictions for non-landmark queries and rewards a threshold shared across queries.

Recall@K. Place recognition, re-identification and category-level retrieval report the hit rate at $K$ and its curve; the Recall@K article covers its definitions and its blindness beyond the first correct item, which the example above shows.

Comparisons are meaningful only within one protocol and annotation version (Oxford or ROxford Medium, with or without distractors, rotated or original Holidays, GLDv2 ground truth before or after re-annotation), and with parameters such as vocabularies and whitening learned away from the test images.

Applications

• 3D reconstruction. Large-scale structure from motion retrieves, for each photo, the images worth matching, instead of matching all pairs; Radenović et al. (2019) used the resulting 3D models in turn to train retrieval networks.
• Visual localization and place recognition. Retrieving geotagged or posed database images near the query gives a coarse position that local matching refines; loop closure in SLAM asks the same question of earlier frames.
• Landmark recognition and photo organization. Labeling photos by the landmark they show, as in the GLDv2 recognition task.
• Product and visual search. Finding catalogue items, artworks or book covers from a phone photograph.
• Copy and near-duplicate detection. Finding reuses of an image across the web or within a collection, and removing near-duplicates from training data.
• Video search. Video Google (Sivic & Zisserman, 2003) retrieved the frames of a film that contain an object outlined by the user.
• Re-identification. Retrieving a person, a vehicle or an animal across cameras with learned embeddings.

Open Problems

• Hard viewing conditions and scale. On ROxford and RParis with a million distractors, the best methods in Radenović et al.’s evaluation stayed well below saturation in the Hard setup (at most 48.7 and 76.0 mAP), and the authors concluded that retrieval is far from solved, especially at large scale and under difficult viewing conditions.
• Global versus local. Global descriptors are compact and fast but weak on small objects and clutter; local features with verification are accurate but memory-hungry. How to obtain the accuracy of the second at the cost of the first is still open, and the best results combine both at considerable cost.
• Robust re-ranking. Query expansion and diffusion help queries with many relevant images and hurt those with few; deciding when to expand, from how many results and with what weights, remains heuristic.
• Open-world queries. In GLDv2 most queries show no landmark at all; a retrieval system deployed on real photos must reject them as well as rank matches.
• Labels and benchmark drift. The revisiting of Oxford and Paris showed how annotation errors and saturated protocols can mislead comparisons for a decade; the GLDv2 authors re-annotated part of their test ground truth when inspection of results revealed missing labels, adding 30% more retrieval annotations. Benchmarks with reliable, complete relevance labels at scale are scarce, a problem shared with image–text retrieval and the benchmark overfitting it invites.
• Category versus instance. A descriptor trained for one notion of similarity is worse for another, as Babenko et al.’s landmark retraining showed; general-purpose embeddings from self-supervised or image–text training are evaluated on both kinds of retrieval, and whether one training objective can serve both well is open.