Object Retrieval with Large Vocabularies and Fast Spatial Matching

“Object Retrieval with Large Vocabularies and Fast Spatial Matching” by James Philbin, Ondřej Chum, Josef Sivic and Andrew Zisserman of the University of Oxford and Michael Isard of Microsoft Research Silicon Valley was presented at the IEEE Conference on Computer Vision and Pattern Recognition (CVPR) in Minneapolis in June 2007. It set out to make the visual-word retrieval of Video Google work on a million web photographs. The paper made two technical contributions: approximate k-means (AKM), which builds flat vocabularies of a million visual words by replacing the exact nearest-center search of k-means with a forest of randomized k-d trees, and a spatial re-ranking stage that checks the top of the ranked list with affine transformations hypothesized from single correspondences of affine-covariant regions. To measure both, the authors collected the Oxford 5K benchmark of Flickr photographs with 55 query regions on 11 Oxford landmarks, and two distractor sets of about 100,000 and one million images. The benchmark as it is used today, with its labels, protocol and successors, is described in Oxford Buildings; the representation is described in bag of visual words, and the systems that followed in image retrieval. The paper received the IEEE PAMI Technical Committee’s Longuet-Higgins Prize in 2017.

This article follows the authors’ copy of the paper (eight pages) on the Visual Geometry Group’s publications page; section, table and figure numbers refer to it. The IEEE Xplore version was not compared with it.

Problem

In 2007, particular-object retrieval from large image collections followed the text-retrieval recipe that Sivic and Zisserman (2003) had brought to video: detect salient regions, quantize their descriptors into visual words, and rank images by tf-idf-weighted word vectors through an inverted file. The paper’s introduction (§1) names two obstacles to scaling this recipe.

The first was the vocabulary. Video Google’s flat k-means vocabulary had about 16,000 words, built from about 200,000 descriptors, and in the paper’s words was effective but hard to scale to large vocabularies. Nistér and Stewénius (2006) had used a cluster hierarchy, the vocabulary tree, to increase the vocabulary to a million words. Clustering at that size was the bottleneck: the authors computed that even 5% of their 100K set would mean clustering about 28 million 128-dimensional descriptors (§3), which in their view ruled out mean-shift, spectral and agglomerative clustering, and exact k-means as well. Elkan’s accelerated k-means needs $O(K^2)$ extra storage for $K$ centers, which they judged impractical. (By the counts in their Table 1, 5% of the 100K set’s 277.8 million descriptors is about 13.9 million; 28 million is about 10%.)

The second was geometry. A bag of words ignores where its words are, yet, the authors argued, a visual query differs from a text query precisely because it comes with a spatial configuration: the words of an image region always arrive in the layout of one view of the object, whereas a user typing three words may want documents containing them in any order. They also noted that image queries contain many more words than text queries, but noisier ones that the user cannot choose, so retrieval systems accept images containing only part of the query’s words (90% in the paper’s example) instead of requiring all of them. The transformations relating two views (epipolar geometry for rigid scenes, homographies for planes, even deformations) and their estimation were well studied, but the authors doubted that consumer photographs needed such general models, and the question the paper posed was empirical: how general a transformation do they actually need?

The authors framed the task as ranking rather than a yes-or-no decision, because even human judges may disagree about whether an occluded or distorted object is present, and chose building facades as the test domain because repeated architectural elements such as windows and doors make them easy to confuse.

Contribution

• Approximate k-means. Flat k-means with approximate nearest-neighbor assignment by randomized k-d trees, at the cost per iteration of the vocabulary tree but, on the paper’s benchmarks, with better retrieval.
• A comparison of scalable vocabularies. AKM against exact k-means (to measure the cost of the approximation) and against hierarchical k-means, on Nistér and Stewénius’s benchmark and on the new Oxford set, and a study of vocabulary size up to 1.25 million words.
• Fast spatial re-ranking. Hypotheses of restricted affine transformations generated from a single pair of corresponding elliptical regions, enumerated exhaustively instead of sampled, refined by a full affine fit in the manner of LO-RANSAC, with three transformation classes compared.
• A benchmark with distractors. Oxford 5K with manually labelled ground truth for 55 queries, and distractor sets that take the collection to 1,145,645 images, used to measure how accuracy falls as the database grows.

Method

The retrieval engine

Each image yields affine-covariant Hessian regions, typically 3,300 on a 1024 × 768 image, each described by a 128-dimensional SIFT descriptor (§2.2; the regions are of the kind described in feature detection). The engine uses the vector-space model with tf-idf weighting and ranks by the L2 distance between query and image vectors, computed through an inverted index stored in a binary-packed structure; when the index does not fit in memory, a version flattened to disk caches the lists of the most frequently requested words. In every Oxford experiment the vocabulary is computed on the 5K images themselves, a choice later criticized (see Limitations). The weighting and the inverted file are covered in bag of visual words.

Approximate k-means and the vocabulary tree

AKM (§3.1) keeps the k-means iteration and replaces only its expensive step, finding each point’s nearest center. At the start of every iteration a forest of 8 randomized k-d trees is built over the current centers, using code by David Lowe optimized for SIFT descriptors. In a randomized tree each node splits on a dimension chosen at random among those of highest variance, at a value chosen at random near the median, so the trees partition the space differently and a point near a cell boundary in one tree is likely to be well inside a cell in another. A point is assigned by descending every tree to a leaf, keeping one priority queue of unexplored branches across all trees, and exploring the most promising branches until a fixed number of paths has been examined. One iteration then costs $O(N \log K)$ instead of $O(NK)$ for $N$ descriptors and $K$ centers. The authors reported that, for moderate $K$, fewer than 1% of points were assigned to a different center than by exact search, and that the method has the time and memory complexity of the vocabulary tree; if memory ran out, the top branches of each tree could be placed on different machines. The search structure itself is described in approximate nearest-neighbor search.

The comparison method (§3.2) is Nistér and Stewénius’s hierarchical k-means (HKM): cluster all points into 10 groups, cluster each group into 10 again, and so on, so that 6 levels give a million leaves. A descriptor can be scored at internal nodes as well as at its leaf, which is meant to soften quantization errors near cell boundaries. The authors’ theoretical objection is that flat k-means minimizes the total distortion between points and their centers, whereas the tree minimizes it only locally at each node, which in general does not minimize the total.

Spatial re-ranking

The filtering stage returns a ranked list, and §4 re-ranks its head by estimating a transformation between the query region and each image. The estimator is LO-RANSAC, introduced by Chum, Matas and Kittler in 2003, which the paper cites from Chum, Matas and Obdržálek (2004): hypotheses come from a simpler, approximate model, and promising ones are re-estimated with the full model. That 2004 paper had already let this local optimization step switch to a model with more degrees of freedom, and had used region-to-region correspondences, each of which carries more than one point correspondence. Philbin et al. exploit the shape of the affine regions so that one pair of corresponding regions fixes a hypothesis. With hypotheses that cheap, they enumerate all of them, one per tentative correspondence, which removes the randomness of RANSAC and makes the procedure deterministic.

Three classes of hypothesis are compared (their Table 6(a)), each mapping a query point to $A\mathbf{x} + \mathbf{t}$:

$$A_{3} = \begin{bmatrix} a & 0 \\ 0 & a \end{bmatrix}, \qquad A_{4} = \begin{bmatrix} a & 0 \\ 0 & b \end{bmatrix}, \qquad A_{5} = \begin{bmatrix} a & 0 \\ b & c \end{bmatrix}.$$

• 3 degrees of freedom (translation and isotropic scale) cover a change of zoom or distance but not foreshortening. The translation comes from the two regions’ centroids and the scale from their sizes.
• 4 degrees of freedom (anisotropic scale) approximate foreshortening by a horizontal or vertical scaling; the $x$ scaling is the ratio of the two regions’ $x$ extents, and likewise for $y$.
• 5 degrees of freedom (anisotropic scale and vertical shear) keep the vertical direction. For each ellipse the paper takes the transformation $H_i$ that maps it to a unit circle while keeping $(0, 1)^\top$ an eigenvector, and sets $H = H_2^{-1} H_1$ (its Table 6(b)).

None of the three allows in-plane rotation, because photographs on the web are usually displayed upright; the paper calls the property that the 5-dof model keeps “upness”. Promising hypotheses are then re-estimated as a general 6-dof affine transformation from the centroids of its current inliers. Of the error functions tried for deciding inliers (one-way transfer error in either direction, two-way transfer error, and two-way transfer error with a threshold on scale), the last worked best. Where a one-way error suffices, verification can be sped up when many features share a word, by finding the spatially closest matching target feature with a 2D k-d tree.

In every experiment marked “spatial”, up to the top 1,000 images are re-ranked. An image counts as verified if some transformation has at least 4 inliers; verified images are placed above unverified ones and scored by the sum of the idf weights of their inlier words, and re-ranking stops early once 20 consecutive images fail verification. The authors described this as a good trade-off between speed and accuracy. Image retrieval places this procedure among the verification methods that followed, and RANSAC covers the estimator.

The datasets

§2 introduces the data the experiments use; Oxford Buildings describes them in full. Oxford 5K holds 5,062 images of 1024 × 768 pixels, retrieved from Flickr with searches for 11 landmarks (a “landmark” being a particular part of a building) and for “Oxford” alone. Each landmark has five query regions, chosen so that results average over the peculiarities of single queries (Fig. 2 shows all 55). Every image was labelled by hand for every landmark as Good, OK (more than 25% of the object clearly visible), Junk (less than 25% visible, or heavily occluded or distorted) or Absent, with between 7 and 220 Good and OK images per landmark. Average precision (§2.1) is the area under the precision–recall curve, with Good and OK as positives, Absent as negatives, and Junk treated as though absent from the database; AP is averaged over the five queries of each landmark and then over landmarks. The paper does not specify how the area is computed; the official program’s trapezoidal rule is described in Oxford Buildings, and the measure itself in average precision.

Two distractor sets were crawled from Flickr’s most popular tags, with exact duplicates removed, and assumed to contain none of the landmarks:

Set	Images	Resolution	Source of images	Features	Descriptor size
5K	5,062	1024 × 768	11 landmark searches and “Oxford”	16,334,970	1.9 GB
100K	99,782	1024 × 768	145 most popular tags	277,770,833	33.1 GB
1M	1,040,801	500 × 333	450 most popular tags	1,186,469,709	141.4 GB
Total	1,145,645			1,480,575,512	176.4 GB

Counts from the paper’s Table 1; resolutions and sources from §2.

Results

All results are mAP on the 5K set unless stated, as printed.

AKM against exact k-means (Table 2), with identical initialization:

Training descriptors	Words	k-means	AKM
800K	10K	0.355	0.358
1M	20K	0.384	0.385
5M	50K	0.464	0.453
16.7M	1M		0.618

The text says the two differ in mAP by less than 1%, with AKM ahead in two cases. The table supports that for the 10K and 20K vocabularies; at 50K words AKM is 0.011 lower, which is 1.1 points of mAP and about 2.4% of the k-means score. Exact k-means was not run at a million words.

AKM against HKM. On Nistér and Stewénius’s recognition benchmark (10,200 images in groups of four views of one object, scored by the average number of the group’s images among the top four), with the benchmark authors’ own training and test descriptors, a million words and L1 distance, AKM scored 3.45 against at best 3.29 for HKM scored at 3 or 4 levels (Table 3; 3.16 and 3.07 at 1 and 2 levels). The HKM figures were taken from the benchmark’s web page, and an accompanying plot shows AKM ahead at every subset size up to the full set. The image retrieval article explains how this score is counted. On Oxford 5K, using their own HKM implementation (which, they reported, reproduced almost identical figures on the benchmark’s data) and a million words from all 16.7 million descriptors:

Method	5K	5K + 100K	5K + 100K + 1M
HKM, scored at 1 level	0.439 (spatial 0.469)
HKM, scored at 2 / 3 / 4 levels	0.418 / 0.372 / 0.353
AKM	0.618 (spatial 0.647)	0.490 (spatial 0.541)	0.393 (spatial 0.465)

Table 4. “Spatial” is the re-ranked result.

The authors suggested that bad splits near the root of the tree send descriptors of the same scene region in different images to different words. Hierarchical scoring, which should soften such errors, lowered HKM’s mAP with L2 distance; with L1 it helped, but the best L1 result (0.427) stayed below the best L2 result (0.439). The paper concludes that more work was needed to understand HKM’s performance on this data.

Vocabulary size (Table 5, AKM on all 16.7 million descriptors):

Words	50K	100K	250K	500K	750K	1M	1.25M
Bag of words	0.473	0.535	0.598	0.606	0.609	0.618	0.602
Spatial	0.599	0.597	0.633	0.642	0.630	0.645	0.625

Bag-of-words mAP peaks at a million words, and the authors expected the curve, quite flat at large sizes, not to fall much for moderately larger vocabularies. Re-ranking helped at every size, most with the smallest vocabulary, where a 50,000-word vocabulary with re-ranking came within 0.02 of a million words without it. The same configuration, a million words on 5K with re-ranking, is printed as 0.647 in Table 4 and 0.645 in Table 5; the paper does not explain the difference.

Scaling. From 5K to 5K + 100K + 1M, a 226-fold increase in images, bag-of-words mAP fell from 0.618 to 0.393. The text calls this a fall of “just over 20%”, which matches the 22.5-point drop in absolute mAP; relative to 0.618 the drop is 36%. The authors attributed it to insufficient discrimination of the quantization in the larger collection. Re-ranking added 0.029, 0.051 and 0.072 on the three collections, which the text summarizes as consistent improvements of around 5%; the gain grew with the collection, so re-ranking recovered part of the loss.

Transformation classes (Table 7), re-ranking the top $N$ images:

Vocabulary (bag of words)	Model	$N$ = 100	200	400	800
20K (0.385)	3 dof	0.468	0.492	0.522	0.556
	4 dof	0.465	0.490	0.521	0.555
	5 dof	0.467	0.491	0.526	0.560
1M (0.618)	3 dof	0.644	0.650	0.652	0.655
	4 dof	0.646	0.656	0.659	0.661
	5 dof	0.648	0.657	0.660	0.664

Re-ranking helps far more with the less discriminative 20,000-word vocabulary. The authors found 5 dof generally better than 4 and 4 better than 3, by small margins, and suggested that the affine re-estimation evens out the differences between hypothesis classes; with 20,000 words and $N \le 200$ the 3-dof model is in fact marginally ahead. The paper says that the “spatial” columns of Tables 4 and 5 re-rank up to 1,000 images with the 20-failure stop, but not which class produced them, nor whether Table 7 used that stop. Every 1M entry of Table 7 from $N = 200$ on exceeds the 0.647 of Table 4, which suggests (our reading) that they differ in configuration.

Speed and examples. With a million words, a typical query on 5K + 100K took about 0.1 s with a 1 GB index in memory; the index for all three sets took 4.3 GB, more than the authors’ machine had, and querying it from disk took about 15–35 s (§2.2). Fig. 4 shows queries on All Souls, the Bridge of Sighs at Hertford, the Ashmolean and a Bodleian window, with results returned before the first false positive under large changes of viewpoint, scale, lighting and occlusion; Fig. 3 shows highly ranked false positives, some visually plausible, others caused by ambiguous local regions and few matched words.

Example: Hypotheses from One Region Correspondence

The script reproduces the hypothesis generation of §4.1 on synthetic features of a facade. Each feature is an elliptical region with a center, a shape matrix $S$ (the region is $\{\mathbf{y} : (\mathbf{y} - \mathbf{x})^\top S^{-1} (\mathbf{y} - \mathbf{x}) \le 1\}$) and a visual word. The query region has 80 features, 40% of which carry one of five “window” words, the repeated structure the paper names as the domain’s difficulty. A target view keeps half of them under a known transformation, adds 1 pixel of position noise and about 8% error in each region’s shape, and adds 150 clutter features, a quarter of them with window words. Tentative correspondences are all pairs with the same word. Each of the three hypothesis classes is enumerated over every correspondence; whenever a hypothesis beats the best so far, an LO step re-fits a 6-dof affine transformation to its inliers. Inliers are decided by two-way transfer error below 4 pixels (the paper’s additional scale threshold is omitted). For the 5-dof class, the transformation $H_i$ that maps an ellipse to the unit circle while keeping $(0,1)^\top$ an eigenvector is taken as the inverse of the Cholesky factor of $S_i$, which is lower triangular; this construction is ours, since the paper does not say how $H_i$ is computed. The script runs in about 2 seconds with NumPy 2.3.5.

import numpy as np

# One tentative correspondence of elliptical regions (x1, S1) <-> (x2, S2), where a
# region is {y : (y - x)^T S^-1 (y - x) <= 1}, gives a hypothesis y = A x + t, t = x2 - A x1.
def hyp_3dof(S1, S2):                     # translation + isotropic scale (ratio of region sizes)
    return (np.linalg.det(S2) / np.linalg.det(S1)) ** 0.25 * np.eye(2)

def hyp_4dof(S1, S2):                     # translation + anisotropic scale (ratio of x and y extents)
    return np.diag(np.sqrt(np.diag(S2) / np.diag(S1)))

def hyp_5dof(S1, S2):                     # translation + anisotropic scale + vertical shear
    L1, L2 = np.linalg.cholesky(S1), np.linalg.cholesky(S2)
    # H_i = L_i^-1 maps ellipse i onto the unit circle and, being lower triangular,
    # keeps (0, 1) as an eigenvector; the hypothesis is H = H_2^-1 H_1.
    return L2 @ np.linalg.inv(L1)

def inliers(A, t, P, Q, thr=4.0):         # two-way transfer error below thr pixels
    fwd = np.linalg.norm(P @ A.T + t - Q, axis=1)
    bwd = np.linalg.norm((Q - t) @ np.linalg.inv(A).T - P, axis=1)
    return (fwd < thr) & (bwd < thr)

def fit_affine(P, Q):                     # 6-dof least squares on region centres
    M = np.linalg.lstsq(np.hstack([P, np.ones((len(P), 1))]), Q, rcond=None)[0]
    return M[:2].T, M[2]

def verify(hyp, P, SP, Q, SQ, lo_steps=5):
    """Enumerate the hypothesis of every tentative correspondence (no sampling). Whenever one
    beats the best so far, run the LO step: re-fit a 6-dof affine to its inliers and re-count."""
    raw = best = np.zeros(len(P), bool)
    for k in range(len(P)):
        A = hyp(SP[k], SQ[k])
        inl = inliers(A, Q[k] - A @ P[k], P, Q)
        if inl.sum() > raw.sum():
            raw = inl
        if inl.sum() > best.sum():
            best = inl
            for _ in range(lo_steps):
                if inl.sum() < 3:
                    break
                inl = inliers(*fit_affine(P[inl], Q[inl]), P, Q)
                if inl.sum() > best.sum():
                    best = inl
    return raw, best

def random_shapes(n, rng):                # ellipses with semi-axes of 3-15 pixels
    a = rng.uniform(0, np.pi, n)
    R = np.stack([np.cos(a), -np.sin(a), np.sin(a), np.cos(a)], -1).reshape(n, 2, 2)
    D = rng.uniform(3, 15, (n, 2)) ** 2
    return R @ (D[:, :, None] * np.eye(2)) @ R.transpose(0, 2, 1)

def make_pair(A_true, rng, n_query=80, keep=0.5, n_clutter=150, n_window_words=5):
    """Features of a synthetic facade: query-region regions with visual words, 40% of them
    sharing one of five 'window' words. The target view keeps half of them under A_true,
    with position and shape noise, and adds clutter, a quarter of it with window words."""
    xq = rng.uniform([0, 0], [400, 300], (n_query, 2))
    Sq = random_shapes(n_query, rng)
    wq = rng.integers(10, 10**6, n_query)
    win = rng.random(n_query) < 0.4
    wq[win] = rng.integers(0, n_window_words, win.sum())
    kept = np.flatnonzero(rng.random(n_query) < keep)
    N = np.eye(2) + 0.08 * rng.normal(size=(len(kept), 2, 2))      # region-shape error
    xt = xq[kept] @ A_true.T + [150.0, 80.0] + rng.normal(0, 1.0, (len(kept), 2))
    St = (A_true @ N) @ Sq[kept] @ (A_true @ N).transpose(0, 2, 1)
    wc = rng.integers(10, 10**6, n_clutter)
    wc[: n_clutter // 4] = rng.integers(0, n_window_words, n_clutter // 4)
    xt = np.vstack([xt, rng.uniform([0, 0], [1024, 768], (n_clutter, 2))])
    St = np.concatenate([St, random_shapes(n_clutter, rng)])
    wt = np.concatenate([wq[kept], wc])
    i, j = np.nonzero(wq[:, None] == wt[None, :])                # tentative: same visual word
    genuine = (j < len(kept)) & (kept[np.minimum(j, len(kept) - 1)] == i)
    return xq[i], Sq[i], xt[j], St[j], genuine

def rot(deg):
    c, s = np.cos(np.radians(deg)), np.sin(np.radians(deg))
    return np.array([[c, -s], [s, c]])

CASES = {"zoom x1.6": 1.6 * np.eye(2),
         "mild foreshortening": np.diag([1.0, 1.2]),
         "strong fsh. + shear": np.array([[0.75, 0.0], [0.45, 1.3]]),
         "15 deg rotation": 1.3 * rot(15)}
MODELS = {"3dof": hyp_3dof, "4dof": hyp_4dof, "5dof": hyp_5dof}

print("genuine correspondences recovered, mean [min, max] over seeds 0-19")
print("%-20s %-5s %19s %19s %9s" % ("view change", "model", "best hypothesis", "after LO (6 dof)", "false/LO"))
for name, A in CASES.items():
    res = {m: [] for m in MODELS}
    for seed in range(20):
        P, SP, Q, SQ, gen = make_pair(A, np.random.default_rng(seed))
        for m, h in MODELS.items():
            raw, lo = verify(h, P, SP, Q, SQ)
            res[m].append(((raw & gen).sum() / gen.sum(), (lo & gen).sum() / gen.sum(), (lo & ~gen).sum()))
    for m in MODELS:
        r = np.array(res[m])
        print("%-20s %-5s " % (name if m == "3dof" else "", m)
              + "  ".join("%4.2f [%4.2f, %4.2f]" % (c.mean(), c.min(), c.max()) for c in r[:, :2].T)
              + "  %8.1f" % r[:, 2].mean())

# Why enumerate: the cost of sampling at this inlier ratio, and a non-matching image.
rng = np.random.default_rng(0)
P, SP, Q, SQ, gen = make_pair(CASES["strong fsh. + shear"], rng)
w = gen.mean()
print("\nseed 0, strong fsh. + shear: %d tentative correspondences, %d genuine (ratio %.2f)"
      % (len(P), gen.sum(), w))
print("hypotheses enumerated: %d; RANSAC draws for 99%% confidence: %d (1 corr.), %d (3 corr.)"
      % (len(P), *np.ceil(np.log(0.01) / np.log(1 - w ** np.array([1, 3])))))
P, SP, Q, SQ, gen = make_pair(CASES["strong fsh. + shear"], rng)
Q = rng.uniform([0, 0], [1024, 768], Q.shape)                    # same words, scrambled layout
print("non-matching image: %d inliers for the best 5dof hypothesis after LO" % verify(hyp_5dof, P, SP, Q, SQ)[1].sum())

Output:

genuine correspondences recovered, mean [min, max] over seeds 0-19
view change          model     best hypothesis    after LO (6 dof)  false/LO
zoom x1.6            3dof  1.00 [0.98, 1.00]  1.00 [1.00, 1.00]       0.0
                     4dof  0.72 [0.35, 1.00]  1.00 [1.00, 1.00]       0.0
                     5dof  0.33 [0.19, 0.56]  1.00 [0.97, 1.00]       0.0
mild foreshortening  3dof  0.20 [0.14, 0.27]  1.00 [1.00, 1.00]       0.1
                     4dof  0.83 [0.49, 1.00]  1.00 [1.00, 1.00]       0.0
                     5dof  0.43 [0.25, 0.85]  1.00 [1.00, 1.00]       0.0
strong fsh. + shear  3dof  0.05 [0.00, 0.09]  0.05 [0.00, 0.09]       0.9
                     4dof  0.12 [0.05, 0.18]  0.68 [0.05, 1.00]       0.2
                     5dof  0.40 [0.24, 0.82]  0.99 [0.83, 1.00]       0.0
15 deg rotation      3dof  0.03 [0.00, 0.07]  0.04 [0.00, 0.20]       0.9
                     4dof  0.05 [0.00, 0.10]  0.14 [0.00, 1.00]       0.8
                     5dof  0.08 [0.03, 0.14]  0.40 [0.03, 1.00]       0.3

seed 0, strong fsh. + shear: 333 tentative correspondences, 43 genuine (ratio 0.13)
hypotheses enumerated: 333; RANSAC draws for 99% confidence: 34 (1 corr.), 2137 (3 corr.)
non-matching image: 2 inliers for the best 5dof hypothesis after LO

The first columns show how good a single correspondence is as a seed. A hypothesis with more freedom fits the true transformation class better but inherits more of the noise in one region’s shape: under a pure zoom, the best 5-dof hypothesis alone finds a third of the genuine matches, and the 3-dof one finds nearly all of them. After the LO step the three classes agree whenever the view change is a zoom or a mild foreshortening, because a seed that captures a few nearby inliers is enough for the affine fit to recover the rest. This is the mechanism the authors proposed for the small differences in their Table 7. The classes separate only when the view change lies outside what a class can approximate locally: under strong foreshortening with shear the 3-dof model fails in every seed, the 4-dof model in some, and the 5-dof model almost never. All three assume an upright camera, and a 15° in-plane rotation, which none of them can represent, defeats them most of the time. The 4- and 5-dof models still succeed in some seeds, the 5-dof model more often on average, presumably (our reading) because its shear can absorb part of a small rotation. In the paper’s domain, the upright prior is a bet about how people photograph buildings, and the small differences in Table 7 suggest (our reading) that most Oxford views were close enough to it.

The second block shows why single-correspondence hypotheses make exhaustive enumeration affordable. With 13% of tentative correspondences genuine, 333 deterministic hypotheses cover every possibility, while sampling three correspondences for a full affine transformation would need about 2,100 random draws for 99% confidence of one clean sample. Random sampling of single correspondences would need only 34 draws for one clean seed, but enumeration also guarantees that the best seed is found, which matters when seeds differ as much as the first columns show. A scrambled image with the same words produces 2 inliers, below the paper’s threshold of 4 for a verified image.

Impact

The IEEE Computer Society’s Technical Committee on Pattern Analysis and Machine Intelligence lists the paper among the two winners of the 2017 Longuet-Higgins Prize, which in the committee’s description recognizes CVPR papers from ten years earlier with significant impact on computer vision research (as of October 2026). The 2016 prize had gone to, among others, Nistér and Stewénius’s vocabulary tree.

The system became the baseline of the group’s later work and of others’. Chum et al.’s query expansion paper at ICCV 2007, by the same authors in a different order, used this engine and referred to the 2007 paper for its details, and its spatial verification is what made the expanded queries safe. Philbin et al. (2008) followed the same architecture, with a million-word AKM vocabulary, when they introduced soft assignment and collected the Paris images. Perd’och, Chum and Matas (2009) credited the paper with introducing the “gravity vector” into geometric verification, that is, using the upright orientation of photographs instead of each region’s computed orientation, and carried the assumption into the descriptors as well. Arandjelović and Zisserman (2012) described their baseline as the standard bag-of-words framework of this paper (Hessian-affine regions, a million AKM words, re-ranking of the top 200 with an affine transformation) and reported 0.672 mAP on Oxford 5K for their implementation, against 0.657 for the original. That 0.657 matches the 5-dof entry for $N = 200$ in Table 7(b), not the “spatial” results of Tables 4 and 5 (our reading). When Radenović et al. (2018) revised the benchmark, they cited the paper for the point that spatial verification is crucial for particular-object retrieval, and verified the top 100 images with RANSAC in their local-feature baselines.

Oxford 5K became the standard evaluation of instance retrieval for about a decade, often with the 100K distractors as Oxford 105K; its later history, including the 2018 revision, is in Oxford Buildings. Approximate k-means, in the authors’ framing, showed that flat vocabularies need not be abandoned for trees at large scale; bag of visual words places it beside the vocabulary tree and soft assignment.

Limitations

Stated by the authors.

• Spatial information is not in the index. The conclusion (§5) states the authors’ belief that retrieval will not scale unless part of the spatial matching moves from the re-ranking stage into the filtering stage, and leaves this as future work. Re-ranking sees only the top 1,000 images, and on the largest collection the index no longer fitted in memory.
• The HKM results were not understood. The authors could not explain why hierarchical scoring hurt the vocabulary tree with L2 distance.
• More evaluation. They wrote that more evaluation was needed to judge how close the ranking function was to returning the right objects as the corpus grows.

Found or argued later.

• Vocabularies learned on the test images. Jégou, Douze and Schmid (2008) argued that a vocabulary learned on a distinct dataset shows the behavior of search in very large collections more accurately, and that the large gain from small to large vocabularies on Oxford was much reduced when, as in their experiments, the vocabulary came from the unrelated Flickr60K set: their Oxford baseline rose only from 0.385 with 20,000 words to 0.395 with 200,000 (their Table 2). With vocabularies learned on the Oxford images, Philbin et al. had reported 0.385 with 20,000 words (Table 2, from 1 million descriptors) and 0.598 with 250,000 (Table 5, from all 16.7 million); the two papers differ in training data as well as vocabulary source, so the comparison is indicative (our reading). Philbin et al. (2008) measured the same effect with a vocabulary trained on Paris, and later papers reported the two cases separately (see Oxford Buildings).
• Geometric verification is expensive. Jégou et al. (2008) judged that full geometric matching could not reasonably be applied to more than a few hundred images and proposed weak geometric consistency inside the inverted file, a partial answer to the future work of §5. Perd’och et al. (2009) noted that each feature’s ellipse, stored naively, is noticeably bigger than its visual-word label and tf-idf weight, and compressed it to 24 bits per feature.
• The distractors and the labels. Radenović et al. (2018) reported that Oxford 100K was not cleaned by hand and contains images of the Oxford and Paris landmarks, contrary to the 2007 assumption, and that many views now expected to be retrieved had been excluded from scoring as Junk. They also called some distractor sets in use biased because their images differ in resolution from Oxford and Paris, which in our reading applies to the 1M set at 500 × 333. These and the other annotation problems are covered in Oxford Buildings.
• Reporting. In our reading, the paper does not state which hypothesis class produced the “spatial” columns of Tables 4 and 5 or whether Table 7 used the early stop, prints two values for the same setting (0.647 and 0.645), and describes its Table 2 and scaling results in percentages that the tables match only in absolute mAP points or not at all. None of this changes its conclusions, but the “original” figure that Arandjelović and Zisserman (2012) quote, 0.657, appears in neither Table 4 nor Table 5.
• Upright images. The hypothesis classes exclude in-plane rotation by design, a reasonable prior for web photographs of buildings that the example above shows failing for rotated views; collections such as INRIA Holidays include rotated images (see Oxford Buildings).

What Came After

The paper’s two directions were pursued separately. On quantization, Philbin et al. (2008) traced the remaining errors to descriptors that fall across cell boundaries and assigned each descriptor softly to several words, and Jégou et al. (2008) kept a coarser vocabulary and refined matches with binary signatures (Hamming embedding). On geometry, Chum et al. (2007) used verified results for query expansion, Jégou et al. (2008) brought weak geometry into the index, and Perd’och et al. (2009) compressed the stored geometry. The benchmark outlived the methods: aggregated descriptors and then learned global embeddings were evaluated on Oxford 5K, and spatial verification remained part of the local-feature baselines on the revised benchmark of 2018. Image retrieval traces these developments, and Oxford Buildings records the results that marked them.