Visual Localization

Visual localization estimates where a camera is and which way it points, all six degrees of freedom of its pose, from an image taken in a scene that has been mapped before. The map is usually a 3D point cloud from structure from motion, a set of posed database images, or a learned model trained on such images. The task is also called camera relocalization, especially in SLAM and robotics, where it answers the “lost robot” question after tracking fails, and image-based localization in the older literature. It is how an augmented reality device places content at a known real-world location, how a robot or vehicle recovers a global position where satellite positioning is unavailable or imprecise, and how a new photograph is registered to an existing reconstruction.

Two families of methods dominate the field’s history. Structure-based methods match local features of the query image to 3D points of the map and solve perspective-n-point (PnP) inside RANSAC. Image-based methods, close relatives of visual place recognition, retrieve the most similar database image and take its pose as an approximation (Sattler et al., 2018). Learned methods added two more: networks that predict the 3D scene coordinate of each pixel, and networks that regress the pose directly. The benchmarks of the last decade measure how far each family gets in accuracy and in robustness to changes such as day and night.

Problem Definition

A map $\mathcal{M}$ of a scene is given in a fixed world frame, together with a query image $I$ and, in most formulations, the query camera’s intrinsics. The task is to estimate the query’s rotation $R$ and translation $\mathbf{t}$, with the convention of the PnP article that world points map to camera coordinates as $\mathbf{X}_c = R\mathbf{X} + \mathbf{t}$, so that the camera centre is $\mathbf{C} = -R^\top\mathbf{t}$.

Structure-based localization reduces this to absolute pose estimation from 2D–3D correspondences $\mathbf{x}_i \leftrightarrow \mathbf{X}_i$:

$$(R^*, \mathbf{t}^*) = \arg\max_{R,\,\mathbf{t}} \; \bigl|\{\, i : \lVert \mathbf{x}_i - \pi(K(R\mathbf{X}_i + \mathbf{t})) \rVert < \tau \,\}\bigr|,$$

the pose that makes the most map points project within $\tau$ pixels of their matched image features, followed by a least-squares refinement of the reprojection error on those inliers. Sattler et al. (2019, §4) describe the structure-based pipeline in these terms: as long as enough of the matches are correct, it can estimate a pose. Every other family replaces one part of this pipeline: scene coordinate regression replaces descriptor matching by a learned prediction of $\mathbf{X}_i$ for each pixel, retrieval replaces the whole pipeline by the pose of a database image, and pose regression replaces it by a network that outputs $(R, \mathbf{t})$.

The map defines what “correct” means. Ground-truth poses of benchmark queries are themselves estimates, from structure from motion, depth-based SLAM or hand-labelled correspondences, and their errors bound how finely any method can be scored.

Input and Output

• Input: a query image, RGB or RGB-D, usually with known intrinsics; a map built from mapping images with known poses: a sparse 3D model with a descriptor for each point, the posed images themselves, or the weights of a network trained on them.
• Output: a 6-DoF pose $(R, \mathbf{t})$, often with the set of inlier correspondences or another confidence measure. A method may also return no pose, which benchmarks count as a failure.

Variants

• Visual place recognition returns a nearby database image rather than a metric pose; the place-recognition article distinguishes the two tasks and describes retrieval as one stage of a localization pipeline.
• Relocalization in SLAM localizes a frame against the system’s own map after tracking is lost. ORB-SLAM, for example, queries a bag-of-words database for candidate keyframes and runs RANSAC with a PnP solver against their map points; the loop closure article describes the shared place-recognition step.
• RGB-D localization uses depth in the query, so that each pixel gives a 3D point in camera coordinates and the pose follows from 3D–3D correspondences with the Kabsch algorithm; the 7-Scenes benchmark was introduced for this case (Shotton et al., 2013).
• Multi-image queries. A rig of cameras with known relative poses, or a short sequence, can be treated as a generalized camera and localized together. Sattler et al. (2018) found a clear benefit from using several images and noted that little work existed on it.
• Localization with priors. A rough position from satellite positioning or the previous frame limits the part of the map that has to be searched; on RobotCar Seasons, the authors simulated such a prior by querying only the relevant sub-model and found that night-time queries benefited significantly from the easier matching problem (Sattler et al., 2018, §5.2, Table 6).

Challenges

• Ambiguous matches at scale. In large or complex scenes, locally similar structures in different parts of the scene make descriptor matches ambiguous, and Sattler et al. (2018) cite outlier ratios of up to 99%. RANSAC’s cost grows steeply with the outlier ratio, which the example below makes concrete.
• Appearance change. Day–night changes, seasons and vegetation change local feature descriptors between mapping and query time. On Aachen Day-Night, Active Search fell from 57.3% of day-time queries within (0.25 m, 2°) to 43.9% of night-time queries even within the coarsest night interval (5 m, 10°) (Sattler et al., 2018, Table 3).
• Viewpoint change. Queries taken far from the mapping trajectories see the scene from angles the map has not seen. Structure-based methods fail when too few features match (Sattler et al., 2019, §4), and learned regressors fail differently, as discussed below.
• Little texture and repetition. Textureless walls, repeated steps and reflective surfaces, all present in 7-Scenes, defeat feature detection and make poses ambiguous (Shotton et al., 2013, §4.1).
• Map size and cost. A city-scale model holds millions of points; Aachen Day-Night’s reference model has 1.65 million points triangulated from 10.55 million features (Sattler et al., 2018, Table 2). Matching against all of them is expensive and increases ambiguity, which motivated prioritized matching and hierarchical localization.
• Ground-truth quality. For the 98 night-time Aachen queries, the authors estimated their own ground truth to have mean median position and orientation errors of 36 cm and 1° (Sattler et al., 2018, §3.1), which is why the original night thresholds were looser than the day ones.

Approaches

Structure-based localization: direct 2D–3D matching

The map is an SfM point cloud in which each 3D point carries the descriptors of the image features it was triangulated from. A query’s local features, such as SIFT or RootSIFT, are matched against these descriptors (feature matching in its 2D–3D form), and the pose is estimated from the resulting 2D–3D matches (Sattler et al., 2018, §2), in the configurations described below with a P3P solver inside RANSAC and a final nonlinear refinement. The two engineering problems are speed and ambiguity. Descriptor matching can be accelerated by prioritization and efficient search, and ambiguous matches can be handled with co-visibility information or geometric outlier filtering (Sattler et al., 2018, §2).

Active Search by Sattler, Leibe and Kobbelt, in the journal version that later papers cite (2017), is the benchmarks’ representative of efficient direct matching; its paper could not be read for this article, so its description here comes from the benchmark papers that evaluate it. As configured by Sattler et al. (2019, §4), it uses RootSIFT features, matches with prioritization, stops the correspondence search once 200 matches have been found, and estimates the pose with a P3P solver in RANSAC followed by nonlinear refinement. City-Scale Localization, the other structure-based method in the 2018 benchmark, is a deterministic geometric outlier filter that assumes a known gravity direction (Sattler et al., 2018, §2).

Image retrieval as localization

Image-based methods approximate the query pose by the pose of the most similar retrieved database image (Sattler et al., 2018, §2), using the global descriptors of image retrieval and place recognition, such as the aggregated descriptors (VLAD, NetVLAD, DenseVLAD) described in the place-recognition article, or earlier bags of visual words. Retrieval is robust and scales well, but its accuracy is limited by how densely the database samples the scene. On Aachen day-time queries, NetVLAD and DenseVLAD put 0.0% of queries within (0.25 m, 2°) and 18.9% and 22.8% within (5 m, 10°), against 96.6% for Active Search (Sattler et al., 2018, Table 3). Retrieval can also be refined: the poses of the top-$k$ images can be interpolated (Sattler et al., 2019, §5), or relative poses to the retrieved images can be estimated.

The opposite case also appears in the benchmark. On RobotCar night queries, DenseVLAD and NetVLAD outperformed every other method in the coarse-precision regime, which Sattler et al. (2018, §5.2) read as evidence that global descriptors still carry distinctive information when local feature matching fails.

Hierarchical localization

Hierarchical localization combines the two: retrieval first narrows the map, and local matching against that part gives an accurate pose. In the formulation that Sarlin et al. (2019, §3) build on, a query’s global descriptor retrieves the $k$ nearest database images (prior frames); these are clustered into places, connected components of the co-visibility graph linking database images to the 3D points they observe; for each place in turn, the query’s keypoints are matched to the place’s 3D points, and PnP inside RANSAC estimates a pose, stopping at the first valid one. The authors describe the local search as efficient because a place holds far fewer 3D points than the whole model, and they credit the image-wide information of the retrieval step with helping to disambiguate matches (§3, §5.3).

Sarlin et al. (2019) used NetVLAD for retrieval and SuperPoint keypoints and descriptors for local matching (NV+SP), and then proposed HF-Net, a single network with one encoder and three heads, for keypoint scores, dense local descriptors and a global descriptor, trained by multitask distillation, with NetVLAD supervising the global head and SuperPoint the descriptor head (§4–5). On Aachen Day-Night, NV+SP localized 40.8% / 56.1% / 74.5% of night queries in the three night intervals, against 19.4% / 30.6% / 43.9% for Active Search; by day, Active Search’s 57.3% in the finest interval compared with 79.7% for NV+SP and 82.8% for an NV+SIFT baseline that runs the same hierarchy with RootSIFT (2019, Table 3). Since NV+SIFT and Active Search use the same RootSIFT features, the authors attribute the difference to the coarse retrieval prior, which helps disambiguate matches. HF-Net itself stayed within an average of 2.6% recall of NV+SP on most sequences, but was clearly worse on RobotCar night, which the authors attribute to the distilled global descriptor on blurry images; they note that a complete failure of global retrieval directly becomes a failure of the hierarchical localization (§5.3).

The authors’ open-source toolbox, hloc, implements this pipeline with interchangeable retrieval, features and matchers. As of commit c13273b (December 2025), its README reports, for SuperPoint features matched by SuperGlue with the top 50 NetVLAD images, 89.6% / 95.4% / 98.8% of Aachen day queries and 86.7% / 93.9% / 100% of night queries within the benchmark thresholds, the results also listed in the benchmark site’s Aachen Day-Night (v1.0) table (read November 2026). These night numbers use the thresholds the site now applies to every condition, (0.25 m, 2°), (0.5 m, 5°) and (5 m, 10°), which are stricter than the night intervals of the 2018 paper, so they cannot be set beside the 2018 and 2019 night results above. In localize_sfm.py, the RANSAC reprojection threshold defaults to 12 pixels and co-visibility clustering is optional and off by default.

Scene coordinate regression

Shotton et al. (2013) removed descriptor matching altogether. Their scene coordinate regression forest (SCoRe Forest) is trained on RGB-D images of one scene with known poses; at each pixel the depth gives a camera-frame point $\mathbf{x}$, and the label is its world position $\mathbf{m} = H\mathbf{x}$, where $H$ is the camera-to-world pose. The forest learns to predict $\mathbf{m}$ from simple depth and colour pixel-comparison features at any pixel, so no keypoint detector is needed and the scene is encoded in the forest rather than in an explicit 3D model. At test time, pose hypotheses come from the Kabsch algorithm on three predicted correspondences, and a preemptive RANSAC evaluates the forest at batches of randomly sampled pixels, scores each hypothesis by its number of outliers under a top-hat error of width 0.1 m, discards the worse half of the hypotheses, refines the rest on their inliers and repeats until one remains (2013, §3).

On 7-Scenes, with RGB-D input, SCoRe Forests with depth-adaptive RGB features localized between 27.8% (Stairs) and 92.6% (Chess) of test frames within 5 cm and 5°, against 9.2% to 70.7% for a sparse ORB baseline that matched features to a 3D point cloud and solved P3P in RANSAC, and almost 0% for a tiny-image retrieval baseline that took a weighted average of the poses of the 100 closest training images (2013, Table 1). The authors name imprecise localization and ambiguities, such as the repeated steps of Stairs, as the main failure modes.

DSAC (Brachmann et al., 2017) builds on an earlier RGB-only, forest-based pipeline of Brachmann et al.: it predicts one scene coordinate per $42 \times 42$ patch with a CNN instead of a forest, forms pose hypotheses by PnP from minimal sets of four predicted scene coordinates, and scores them with a second CNN. To train the whole pipeline end to end, it replaces RANSAC’s deterministic choice of the best hypothesis, which is not differentiable, with a probabilistic selection according to a softmax over hypothesis scores, so that the expected loss of the final pose can be differentiated. On the complete 7-Scenes test set (17,000 frames), the end-to-end trained DSAC localized 58.0% of frames within 5 cm and 5°, against 56.8% for the same pipeline trained component-wise with ordinary RANSAC and 55.2% for the earlier forest-based RGB pipeline of Brachmann et al. (2017, Table 1).

Later systems made the approach practical. ACE (Brachmann, Cavallari & Prisacariu, 2023) splits the network into a generic convolutional backbone and a scene-specific MLP head that maps backbone features to scene coordinates; training only the head lets each training batch mix features from many mapping images, which the authors report gives stable gradients at high learning rates. ACE maps a scene in 5 minutes into 4 MB of weights from posed RGB images alone, and in the authors’ Table 1 it localized 97.1% of 7-Scenes frames within 5 cm and 5° against SfM ground truth, where DSAC* (full, trained without depth) took 15 hours to reach 96.0% with 28 MB. The authors’ own caveat applies to the comparison: map sizes and mapping times are hard to compare across hardware and implementations, and they re-ran only DSAC* themselves (§4.1).

Absolute pose regression

PoseNet (Kendall, Grimes & Cipolla, 2015) regressed the pose directly with a convolutional network: a modified 23-layer GoogLeNet takes a $224 \times 224$ image and outputs a position $\mathbf{x}$ and a quaternion $\mathbf{q}$, trained with

$$\mathcal{L}(I) = \lVert \hat{\mathbf{x}} - \mathbf{x} \rVert_2 + \beta \left\lVert \hat{\mathbf{q}} - \frac{\mathbf{q}}{\lVert \mathbf{q} \rVert} \right\rVert_2,$$

where $\beta$ balances position against orientation; the authors tuned it by grid search, between 120 and 750 indoors and 250 and 2,000 outdoors. Transfer learning from large classification datasets made training possible on scenes with a few hundred to a few thousand training images, and structure from motion supplied the training poses. The network ran in 5 ms per image and reached about 2 m and 3° outdoors and 0.5 m and 5° indoors; the authors report it robust to difficult lighting, motion blur and different camera intrinsics where point-based SIFT registration failed (2015, abstract and Fig. 8). PoseNet chose quaternions because any 4-vector maps to a valid rotation by normalization (§3); the rotation representations article compares quaternions with the alternatives.

Pose regression stayed well short of structure-based accuracy, and Sattler, Zhou, Pollefeys and Leal-Taixé (2019) explained why. They write a pose regressor as feature extraction, a nonlinear embedding $\boldsymbol{\alpha}^I \in \mathbb{R}^n$, and a final linear layer, so that the predicted pose is

$$\hat{\mathbf{c}}^I = \mathbf{c}_b + \sum_{j=1}^{n} \alpha^I_j \mathbf{c}_j, \qquad \hat{\mathbf{r}}^I = \mathbf{r}_b + \sum_{j=1}^{n} \alpha^I_j \mathbf{r}_j,$$

a combination of learned base poses $(\mathbf{c}_j, \mathbf{r}_j)$ weighted by how the image looks (2019, Eq. 3). Two consequences follow. If all training positions lie on a line, as for data captured from a car, one admissible solution puts every base translation on that line, and no combination of them ever leaves it; on recorded scenes with training data on a line, MapNet and PoseNet placed test poses along the training line instead of generalizing to the true, diverging viewpoints, while Active Search handled them (§4, Fig. 2). And because the weights come from appearance, the prediction for an image $I$ similar to a training image $J$ is $J$’s prediction plus an offset (Eq. 6), which makes pose regression conceptually closer to retrieval with interpolation than to geometric pose estimation.

Their experiments bore this out. On Cambridge Landmarks and 7-Scenes, none of the absolute or relative pose regressors they compared consistently outperformed the DenseVLAD retrieval baseline or its interpolated variant (2019, Table 2). With a synthetic Shop Façade scene whose training set was enlarged to up to 9,412 renderings, from extra poses on a grid with spacing down to 25 cm, PoseNet and MapNet improved, MapNet to 0.33 m and 1.46° at best, but Active Search, using renderings from the original training poses only, reached 0.01 m and 0.04° (Table 1). The authors also note that updating the map requires retraining the network.

Relative pose regression

Relative pose regression predicts the pose of the query relative to one or more database images and composes it with their known poses. RelocNet (Balntas, Li & Prisacariu, 2018) learns a global descriptor for retrieval with a metric-learning loss based on the overlap of camera frusta, so that descriptor differences reflect pose differences, and then regresses the relative pose between the query and its nearest neighbour with a geometric loss. Because the network is not tied to one scene’s coordinates, such methods can be trained on other scenes (Sattler et al., 2019, §2). In Sattler et al.’s comparison, RelocNet and the Relative PN of Laskar et al. (2017) were among the best regression methods, but the variants trained on unrelated data (ScanNet for RelocNet, a university dataset for Relative PN) were less accurate on 7-Scenes than DenseVLAD, which needs no training (2019, §5.1, Table 2).

How the families compare

The documented pattern is consistent across the papers read here. On 7-Scenes, Sattler et al. (2019, Table 2) list median errors of 0.04 m and 1.96° on Chess for Active Search and 0.02 m and 0.5° for DSAC++, against 0.32 m for PoseNet and 0.21 m for DenseVLAD; on King’s College in Cambridge Landmarks, 0.42 m and 0.55° for Active Search and 0.18 m and 0.3° for DSAC++, against 1.92 m for PoseNet and 2.80 m for DenseVLAD. Scene coordinate regression was the most accurate family at small scale; the same paper notes that, at the time, coordinate regression had not been shown to scale to larger scenes, while descriptor-based methods handled city-scale scenes (§2). Retrieval and regression trade accuracy for robustness or speed. The tables of different papers disagree on some values: PoseNet’s orientation errors in Sattler et al.’s Table 2 are twice those printed in the PoseNet paper’s own table (5.40° against 2.70° on King’s College, 8.12° against 4.06° on Chess), with identical position errors, so values for one method should be taken from a single table.

Example

The script below compares a structure-based localizer with retrieval-only localization on the same synthetic map, as the share of wrong 2D–3D matches grows. It uses NumPy 2.3.5 and SciPy 1.16.3 and ran in about 15 to 20 seconds.

The map is a street canyon: two facades at $y = \pm 8$ m, 160 m long and 12 m high, with 4,000 random 3D points on each. The camera has a focal length of 500 pixels and a $640 \times 480$ image, and uses the convention of the PnP and camera-pose articles: world-to-camera $\mathbf{X}_c = R\mathbf{X} + \mathbf{t}$, camera $z$ forward, $x$ right, $y$ down; world $x$ runs along the street, $y$ to the left, $z$ up. Fifty-seven database images, the “SfM model”, are taken every 2 m along the centre of the street, 1.6 m above the ground, looking along the street. A point is visible in an image if it lies 1 to 40 m in front of the camera and projects inside the frame. The 100 queries stand anywhere between 10 and 110 m along the street, up to 3 m to either side and 0.3 m above or below the database height, turned by up to 15° of yaw, 5° of pitch and 2° of roll. Each query gets 200 correspondences to visible map points with 1-pixel noise, and a fraction $\varepsilon$ of them is given a wrong 3D point, any other point of the map, as a wrong descriptor match would.

Four localizers are scored:

• PnP + RANSAC: P3P from Grunert’s quartic, solved for batches of 100 random samples at a time, with the number of samples adapted to 99% confidence from the best inlier ratio found so far and capped at 2,000; inliers lie within 4 pixels with positive depth; a pose needs at least 8 inliers, and it is refined by Gauss–Newton on the inliers, which are then re-classified and refined again. The 8-inlier minimum is our choice, not a value from the sources.
• Correct retrieval: the pose of the database image nearest to the true query position, as if retrieval never failed. This is the best a retrieval-only method can do with this database.
• Vote retrieval: the pose of the database image that sees the most of the query’s matched 3D points, wrong matches included, a retrieval that depends on the same matches as PnP.
• PnP, else vote: the PnP pose when RANSAC accepts one, otherwise the vote-retrieval pose.

The sources leave open how retrieval relates to the local matches; real systems retrieve with a global descriptor computed from the whole image, so the two retrieval rules bracket the cases of retrieval independent of the matches and retrieval that sees their errors. Errors are the camera-centre distance and the rotation angle, scored like the Aachen benchmark as the percentage of queries within (0.25 m, 2°), (0.5 m, 5°) and (5 m, 10°) (Sattler et al., 2018); a query PnP rejects counts as not localized, with infinite error.

The example was planned, with its hypotheses, before it was run. A pilot at the planned sizes confirmed that PnP recovers every query pose from noise-free matches (to $10^{-13}$ m) and puts every query in the finest bin with 1-pixel noise, and that correct retrieval returns the nearest database pose. Two repairs were made before the first run: the planned 120 m facades left the last database cameras with no points in view, because with this field of view a facade 8 m to the side enters the image only about 12.5 m ahead, so the facades were lengthened to 160 m at the same point density; and the P3P solver now discards degenerate samples, those in which wrong matches repeat a 3D point or whose quartic has a vanishing leading coefficient, which had produced division by zero. Nothing was changed after the first run.

import numpy as np
from scipy.spatial.transform import Rotation

K = np.array([[500.0, 0, 320], [0, 500, 240], [0, 0, 1]])
W, H = 640, 480
R_BASE = np.array([[0.0, -1, 0], [0, 0, -1], [1, 0, 0]])   # world-to-camera: looks along +x, z up


def make_map(rng, n=4000):
    x = rng.uniform(0, 160, 2 * n)
    z = rng.uniform(0, 12, 2 * n)
    y = np.r_[np.full(n, 8.0), np.full(n, -8.0)]
    return np.c_[x, y, z]


def project(R, t, X):
    Xc = X @ R.T + t
    x = Xc @ K.T
    return x[:, :2] / x[:, 2:], Xc[:, 2]


def visible(R, t, X):
    x, z = project(R, t, X)
    return (z > 1) & (z < 40) & (x[:, 0] >= 0) & (x[:, 0] < W) & (x[:, 1] >= 0) & (x[:, 1] < H)


def pose_from(C, ypr_deg):
    """World-to-camera (R, t) of a camera at centre C, turned by yaw/pitch/roll in the world."""
    R_wc = Rotation.from_euler("ZYX", ypr_deg, degrees=True).as_matrix() @ R_BASE.T
    R = R_wc.T
    return R, -R @ C


def kabsch_batch(Pw, Pc):
    """R, t with Pc = R Pw + t for batches (M, k, 3)."""
    mw, mc = Pw.mean(1, keepdims=True), Pc.mean(1, keepdims=True)
    Hm = np.einsum("mki,mkj->mij", Pw - mw, Pc - mc)
    U, S, Vt = np.linalg.svd(Hm)
    d = np.sign(np.linalg.det(np.einsum("mji,mkj->mik", Vt, U)))
    D = np.zeros_like(Hm); D[:, 0, 0] = 1; D[:, 1, 1] = 1; D[:, 2, 2] = d
    R = np.einsum("mji,mjk,mlk->mil", Vt, D, U)
    t = mc[:, 0] - np.einsum("mij,mj->mi", R, mw[:, 0])
    return R, t


def p3p_grunert(f, P):
    """f: (N,3,3) unit rays, P: (N,3,3) world points. Returns R (M,3,3), t (M,3)."""
    a = np.linalg.norm(P[:, 1] - P[:, 2], axis=1); b = np.linalg.norm(P[:, 0] - P[:, 2], axis=1)
    c = np.linalg.norm(P[:, 0] - P[:, 1], axis=1)
    good = np.minimum(np.minimum(a, b), c) > 1e-6        # a wrong match can repeat a 3D point
    f, P, a, b, c = f[good], P[good], a[good], b[good], c[good]
    ca = np.sum(f[:, 1] * f[:, 2], 1); cb = np.sum(f[:, 0] * f[:, 2], 1); cg = np.sum(f[:, 0] * f[:, 1], 1)
    a2, b2, c2 = a**2, b**2, c**2
    p, q = (a2 - c2) / b2, (a2 + c2) / b2
    A4 = (p - 1) ** 2 - 4 * c2 / b2 * ca**2
    A3 = 4 * (p * (1 - p) * cb - (1 - q) * ca * cg + 2 * c2 / b2 * ca**2 * cb)
    A2 = 2 * (p**2 - 1 + 2 * p**2 * cb**2 + 2 * (b2 - c2) / b2 * ca**2
              - 4 * q * ca * cb * cg + 2 * (b2 - a2) / b2 * cg**2)
    A1 = 4 * (-p * (1 + p) * cb + 2 * a2 / b2 * cg**2 * cb - (1 - q) * ca * cg)
    A0 = (1 + p) ** 2 - 4 * a2 / b2 * cg**2
    keep = np.abs(A4) > 1e-12
    f, P, A0, A1, A2, A3, A4 = f[keep], P[keep], A0[keep], A1[keep], A2[keep], A3[keep], A4[keep]
    p, ca, cb, cg, b2 = p[keep], ca[keep], cb[keep], cg[keep], b2[keep]
    N = len(f)
    comp = np.zeros((N, 4, 4))
    comp[:, 0, :] = -np.c_[A3, A2, A1, A0] / A4[:, None]
    comp[:, 1, 0] = comp[:, 2, 1] = comp[:, 3, 2] = 1
    roots = np.linalg.eigvals(comp)                       # (N, 4)
    ok = np.abs(roots.imag) < 1e-6 * (1 + np.abs(roots.real))
    v = roots.real
    u = ((p - 1)[:, None] * v**2 - 2 * (p * cb)[:, None] * v + (1 + p)[:, None]) / (2 * (cg[:, None] - v * ca[:, None]))
    s1sq = b2[:, None] / (1 + v**2 - 2 * v * cb[:, None])
    ok &= (s1sq > 0) & (u > 0) & (v > 0)
    s1 = np.sqrt(np.where(ok, s1sq, 1.0))
    idx, r = np.nonzero(ok)
    s = np.stack([s1[idx, r], u[idx, r] * s1[idx, r], v[idx, r] * s1[idx, r]], 1)   # (M, 3)
    Pc = f[idx] * s[:, :, None]
    return kabsch_batch(P[idx], Pc)


def refine(R, t, X, x, iters=8):
    """Gauss-Newton on reprojection error, R <- exp([w]x) R, t <- t + dt."""
    for _ in range(iters):
        Xc = X @ R.T + t
        r = (project(R, t, X)[0] - x).ravel()
        X_, Y_, Z_ = Xc.T
        dp = np.zeros((len(X), 2, 3))
        dp[:, 0, 0] = K[0, 0] / Z_; dp[:, 0, 2] = -K[0, 0] * X_ / Z_**2
        dp[:, 1, 1] = K[1, 1] / Z_; dp[:, 1, 2] = -K[1, 1] * Y_ / Z_**2
        RX = Xc - t
        skew = np.zeros((len(X), 3, 3))
        skew[:, 0, 1], skew[:, 0, 2], skew[:, 1, 2] = -RX[:, 2], RX[:, 1], -RX[:, 0]
        skew[:, 1, 0], skew[:, 2, 0], skew[:, 2, 1] = RX[:, 2], -RX[:, 1], RX[:, 0]
        J = np.concatenate([-dp @ skew, dp], 2).reshape(-1, 6)
        d = np.linalg.lstsq(J, -r, rcond=None)[0]
        R = Rotation.from_rotvec(d[:3]).as_matrix() @ R
        t = t + d[3:]
    return R, t


def pnp_ransac(X, x, rng, thr=4.0, max_hyp=2000, batch=100, min_inl=8):
    f = np.c_[x, np.ones(len(x))] @ np.linalg.inv(K).T
    f /= np.linalg.norm(f, axis=1, keepdims=True)
    n, best, best_inl, tried, need = len(X), None, np.zeros(len(X), bool), 0, max_hyp
    while tried < min(need, max_hyp):
        idx = np.array([rng.choice(n, 3, replace=False) for _ in range(batch)])
        tried += batch
        Rs, ts = p3p_grunert(f[idx], X[idx])
        if len(Rs) == 0:
            continue
        Xc = np.einsum("mij,nj->mni", Rs, X) + ts[:, None]
        z = Xc[..., 2]
        xp = (Xc @ K.T)[..., :2] / np.where(np.abs(z) < 1e-9, 1e-9, z)[..., None]
        inl = (np.linalg.norm(xp - x, axis=2) < thr) & (z > 0)
        k = inl.sum(1).argmax()
        if inl[k].sum() > best_inl.sum():
            best, best_inl = (Rs[k], ts[k]), inl[k]
            w = best_inl.mean()
            need = np.log(0.01) / np.log(1 - w**3) if w < 1 else 0
    if best is None or best_inl.sum() < min_inl:
        return None, tried
    R, t = refine(*best, X[best_inl], x[best_inl])
    xp, z = project(R, t, X)
    inl = (np.linalg.norm(xp - x, axis=1) < thr) & (z > 0)
    if inl.sum() < min_inl:
        return None, tried
    return refine(R, t, X[inl], x[inl]), tried


def errors(R, t, Rg, tg):
    ang = np.degrees(np.arccos(np.clip((np.trace(Rg.T @ R) - 1) / 2, -1, 1)))
    return np.linalg.norm(-R.T @ t + Rg.T @ tg), ang


# Map: two facades of a street canyon; database images every 2 m along the street.
rng = np.random.default_rng(0)
Xmap = make_map(rng)
db_C = np.array([[x, 0.0, 1.6] for x in np.arange(4, 117, 2.0)])
db = [pose_from(C, [0, 0, 0]) for C in db_C]
Vis = np.array([visible(R, t, Xmap) for R, t in db])          # which db image sees which point

# Queries: off the database path by up to 3 m, turned by up to 15 deg of yaw.
qrng = np.random.default_rng(1)
queries = []
for _ in range(100):
    C = np.array([qrng.uniform(10, 110), qrng.uniform(-3, 3), 1.6 + qrng.uniform(-0.3, 0.3)])
    ypr = [qrng.uniform(-15, 15), qrng.uniform(-5, 5), qrng.uniform(-2, 2)]
    queries.append((C, pose_from(C, ypr)))


def correspondences(qi, eps, n=200, sigma=1.0):
    """n 2D-3D matches of query qi; a fraction eps get a wrong 3D point."""
    C, (R, t) = queries[qi]
    r = np.random.default_rng([2, qi, int(round(eps * 100))])
    ids = r.choice(np.flatnonzero(visible(R, t, Xmap)), n, replace=False)
    x = project(R, t, Xmap[ids])[0] + sigma * r.standard_normal((n, 2))
    for j in r.choice(n, int(round(eps * n)), replace=False):
        new = r.integers(len(Xmap) - 1)
        ids[j] = new + (new >= ids[j])                         # any other map point
    return ids, x


bins = [(0.25, 2), (0.5, 5), (5.0, 10)]                         # Sattler et al. (2018)
print("eps   method              % within (0.25 m, 2) / (0.5 m, 5) / (5 m, 10)   median m / deg")
for eps in [0.0, 0.25, 0.5, 0.75, 0.9, 0.95]:
    E = {k: [] for k in ["PnP + RANSAC", "correct retrieval", "vote retrieval", "PnP, else vote"]}
    hyps = []
    for qi in range(100):
        C, (Rg, tg) = queries[qi]
        ids, x = correspondences(qi, eps)
        pose, tried = pnp_ransac(Xmap[ids], x, np.random.default_rng([3, qi, int(round(eps * 100))]))
        hyps.append(tried)
        near = db[np.argmin(np.linalg.norm(db_C - C, axis=1))]
        vote = db[np.argmax(Vis[:, ids].sum(1))]
        fail = (np.inf, np.inf)
        E["PnP + RANSAC"].append(errors(*pose, Rg, tg) if pose else fail)
        E["correct retrieval"].append(errors(*near, Rg, tg))
        E["vote retrieval"].append(errors(*vote, Rg, tg))
        E["PnP, else vote"].append(errors(*(pose or vote), Rg, tg))
    for name, e in E.items():
        e = np.array(e)
        rec = " / ".join(f"{100 * np.mean((e[:, 0] < m) & (e[:, 1] < d)):3.0f}" for m, d in bins)
        print(f"{eps:4.2f}  {name:18s}  {rec:>45s}   {np.median(e[:, 0]):5.2f} / {np.median(e[:, 1]):5.2f}")
    print(f"      (RANSAC hypotheses per query: mean {np.mean(hyps):.0f}, max {max(hyps)})")

Output:

eps   method              % within (0.25 m, 2) / (0.5 m, 5) / (5 m, 10)   median m / deg
0.00  PnP + RANSAC                                      100 / 100 / 100    0.02 /  0.04
0.00  correct retrieval                                   0 /   5 /  61    1.51 /  7.99
0.00  vote retrieval                                      0 /   5 /  61    1.95 /  7.99
0.00  PnP, else vote                                    100 / 100 / 100    0.02 /  0.04
      (RANSAC hypotheses per query: mean 100, max 100)
0.25  PnP + RANSAC                                      100 / 100 / 100    0.02 /  0.04
0.25  correct retrieval                                   0 /   5 /  61    1.51 /  7.99
0.25  vote retrieval                                      0 /   4 /  61    2.04 /  7.99
0.25  PnP, else vote                                    100 / 100 / 100    0.02 /  0.04
      (RANSAC hypotheses per query: mean 100, max 100)
0.50  PnP + RANSAC                                      100 / 100 / 100    0.02 /  0.06
0.50  correct retrieval                                   0 /   5 /  61    1.51 /  7.99
0.50  vote retrieval                                      0 /   4 /  61    2.01 /  7.99
0.50  PnP, else vote                                    100 / 100 / 100    0.02 /  0.06
      (RANSAC hypotheses per query: mean 101, max 200)
0.75  PnP + RANSAC                                      100 / 100 / 100    0.03 /  0.08
0.75  correct retrieval                                   0 /   5 /  61    1.51 /  7.99
0.75  vote retrieval                                      0 /   2 /  58    2.39 /  7.99
0.75  PnP, else vote                                    100 / 100 / 100    0.03 /  0.08
      (RANSAC hypotheses per query: mean 416, max 900)
0.90  PnP + RANSAC                                       71 /  72 /  75    0.08 /  0.18
0.90  correct retrieval                                   0 /   5 /  61    1.51 /  7.99
0.90  vote retrieval                                      0 /   2 /  43    2.92 /  7.99
0.90  PnP, else vote                                     71 /  72 /  85    0.08 /  0.18
      (RANSAC hypotheses per query: mean 2000, max 2000)
0.95  PnP + RANSAC                                        8 /  11 /  11     inf /   inf
0.95  correct retrieval                                   0 /   5 /  61    1.51 /  7.99
0.95  vote retrieval                                      0 /   0 /  25   10.30 /  7.99
0.95  PnP, else vote                                      8 /  11 /  34    7.59 /  7.44
      (RANSAC hypotheses per query: mean 2000, max 2000)

Up to 75% wrong matches, PnP with RANSAC puts every query in the finest bin, with median errors of a few centimetres and under a tenth of a degree, because the pose comes from geometry: once one sample of three correct matches is drawn, the remaining correct matches confirm it and refinement averages out the pixel noise. Correct retrieval never enters the finest bin and reaches the medium bin only for queries that happen to stand close to a database camera with little rotation. Its errors are set by the map, not by the matches: the distance to the nearest database camera, at most about 3.2 m by construction (1 m along the street, 3 m across, 0.3 m in height), and the query’s own rotation relative to the database orientation. Since no position error reaches 5 m, the 61% in the coarse bin are the queries turned by less than 10°. This is a synthetic version of the gap between Active Search and NetVLAD in the Aachen day results.

Structure-based localization fails abruptly rather than gracefully. The RANSAC budget shows why: the adaptive stopping rule needs one or two batches of 100 samples up to 50% outliers, an average of 416 samples at 75%, and the full 2,000 at 90%, where the chance that a random triple is all correct is about $0.1^3 = 0.001$. At $\varepsilon = 0.9$, 71% of queries are still in the finest bin, fewer than the plan’s hypothesis that “about 1 - 0.999^2000 ~ 86% of queries succeed”. Drawing three of the 20 correct matches without replacement has probability $(20 \cdot 19 \cdot 18)/(200 \cdot 199 \cdot 198) \approx 0.00087$, which lowers that figure to about 82%; for the rest of the gap, in our reading, not every all-correct triple of distant, noisy points gives a pose good enough to collect the other inliers within 4 pixels, the effect of noisy minimal samples that the RANSAC article describes. At $\varepsilon = 0.95$, with 10 correct matches among 200, only about one query in ten lands even in the coarse bin, against the plan’s “about 22% succeed”, and the median error is infinite because at least half the queries get no pose. The methods described above attack the ambiguity before RANSAC rather than after it, with prioritized matching, co-visibility and geometric filtering, or the retrieval step of hierarchical localization.

The two retrieval rules diverge as wrong matches grow. Correct retrieval does not use the matches and is unaffected. Vote retrieval is worse even without outliers, since the image that shares the most points with an off-centre or turned query need not be the nearest one, and it degrades with $\varepsilon$, its median position error growing to 10 m, against the plan’s hypothesis of “vote retrieval similar, possibly slightly worse at 0.95”. In our reading of the construction, each database image sees roughly 27 m of each 160 m facade (from about 12.5 m to 40 m ahead), about a sixth of the map, so 190 wrong matches give every image a few dozen random votes, enough to drown the votes of 10 correct matches. Its rotation error stays at 7.99° in every row because all database images share one orientation. In our reading, this is one reason localizers retrieve with a global descriptor computed from the whole image, which Sattler et al. (2018) found can succeed where local matching fails, rather than from the local matches they are trying to verify. The fallback row combines the two behaviours: PnP’s accuracy where it succeeds and a coarse retrieval pose otherwise, which raises the coarse-bin share at $\varepsilon = 0.9$ from 75% to 85%.

Datasets and Benchmarks

7-Scenes

Shotton et al. (2013) recorded seven indoor scenes, Chess, Fire, Heads, Office, Pumpkin, RedKitchen and Stairs, with a handheld Kinect RGB-D camera at $640 \times 480$, and obtained ground-truth camera tracks with an implementation of KinectFusion. Several sequences per scene, recorded by different users, are split into training and test sequences; the scenes span up to 6 m³ and contain between 1,000 and 7,000 training and 1,000 and 5,000 test frames (2013, Table 1). The difficulties are those listed above: repeated steps in Stairs, reflective cupboards in RedKitchen, motion blur, flat surfaces and sensor noise. Although designed for RGB-D, it is also used for RGB-only methods: DSAC’s authors call it widely used, and Sattler et al. (2019, §5.1) note that it and Cambridge Landmarks are commonly used to evaluate pose regression. ACE’s authors report results against two sets of ground-truth poses, from depth-based SLAM and from SfM, because a relocalizer’s performance can be biased toward one or the other; in their Table 1, Active Search localized 98.5% of frames within 5 cm and 5° against SfM poses but 68.7% against depth-SLAM poses (Brachmann et al., 2023).

Cambridge Landmarks

Kendall, Grimes and Cipolla (2015) released Cambridge Landmarks with five outdoor scenes: King’s College, Street, Old Hospital, Shop Façade and St Mary’s Church. A pedestrian recorded high-definition video with a smartphone, subsampled at 2 Hz to about 1 m between camera positions, and structure from motion gave the ground-truth poses. Training and test images come from distinct walking paths, at different times, with pedestrians and vehicles in view. The scenes range from 35 × 25 m (Shop Façade, 231 training and 103 test images) to 500 × 100 m (Street, 3,015 and 2,923) (2015, Fig. 6). hloc’s Cambridge pipeline also downloads a sixth scene, Great Court. ACE’s authors suggest that feature-matching methods do very well here presumably because of their similarity to the SfM algorithm that produced the ground truth (2023, §4.2).

Aachen Day-Night

Sattler et al. (2018) built Aachen Day-Night on an earlier Aachen localization dataset of the old inner city of Aachen. The reference model has 4,328 day-time images and 1.65 million 3D points; the 824 day-time queries got ground truth from a joint COLMAP reconstruction with the reference images, and the 98 night-time queries, taken with a phone using software HDR, got it from 10 to 30 hand-labelled 2D–3D matches each, solved with a 3-point solver and nonlinear refinement (§3.1). The same paper introduced RobotCar Seasons and CMU Seasons, with conditions such as dawn, dusk, snow, rain, night and seasonal foliage. The benchmark site lists a later Aachen Day-Night v1.1 with 6,697 reference images and 1,015 queries, 824 by day and 191 by night, and publishes submitted results for both versions (read November 2026).

Other benchmarks extend the setting: InLoc for indoor localization against a database of RGB-D scans, which hloc supports; and the extended CMU Seasons, which the benchmark site recommends over the original.

Evaluation Metrics

• Position error $\lVert \mathbf{C}_{\text{est}} - \mathbf{C}_{\text{gt}} \rVert$, between camera centres, not translation vectors.
• Orientation error, the smallest rotation angle aligning the two orientations, $2\cos\lvert\alpha\rvert = \operatorname{tr}(R_{\text{gt}}^{-1} R_{\text{est}}) - 1$ (Sattler et al., 2018, §4).
• Median errors in metres and degrees, as reported for Cambridge Landmarks and 7-Scenes by PoseNet and in Sattler et al.’s comparison (Kendall et al., 2015; Sattler et al., 2019). Medians hide failures: a method that fails on 40% of queries can still report a good median.
• Percentage within a threshold. 7-Scenes uses 5 cm and 5°, which Shotton et al. (2013) chose as strict enough for some augmented reality uses and certainly enough to restart model-based tracking. The Aachen-style benchmarks report three intervals, high (0.25 m, 2°), medium (0.5 m, 5°) and coarse (5 m, 10°) precision; the 2018 paper used (0.5 m, 2°), (1 m, 5°) and (5 m, 10°) for the Aachen night queries because of their less certain ground truth, while the benchmark site now applies the day thresholds to every condition. Results computed under different thresholds, ground-truth versions (7-Scenes depth-SLAM or SfM poses; Aachen v1.0 or v1.1) or splits are not comparable.
• Recall@N with a localization radius, borrowed from place recognition, scores only retrieval; the place-recognition article discusses it, and precision and recall defines the terms.
• Cost: mapping time, map size and query time, which ACE’s authors tabulate alongside accuracy.

Applications

• Augmented reality: anchoring content to a stored map, so that it appears in the same real place across sessions and devices; the augmented reality article describes relocalization against shared anchors and its failure mode in look-alike rooms.
• Robotics and vehicles: recovering a global pose against a prior map where satellite positioning is unavailable or imprecise, for visual navigation, robot perception and autonomous driving perception; Sattler et al. (2018) chose their thresholds with the accuracy needed for autonomous driving in mind.
• SLAM: relocalization after tracking loss and in multi-session maps, as in ORB-SLAM and its successors.
• Structure from motion: registering each new image to a partial reconstruction is the same 2D–3D problem, solved by PnP in incremental SfM.

Open Problems

• Day–night and seasonal change. Sattler et al. (2018) concluded that long-term localization was far from solved, that night-time queries against day-time maps were very hard even with a location prior, and that vegetated scenes were hard too. Hierarchical pipelines with learned features and matchers have since reported 86.7% of Aachen night queries within (0.25 m, 2°) on the benchmark site (the hloc result above); the site’s thresholds differ from the 2018 paper’s night intervals, so the figure is not directly comparable with the 2018 and 2019 results.
• Generalization of learned regressors. Absolute pose regression is not guaranteed to generalize beyond its training data (Sattler et al., 2019), and both absolute pose regression and scene coordinate regression must be trained for each scene; ACE reduced that cost from hours to minutes, but not to zero.
• Scale with accuracy. Structure-based methods scale to cities but match against large, ambiguous models; scene coordinate regression was the most accurate family in rooms and small outdoor scenes, but Sattler et al. (2019) noted that it had not yet been shown to scale to larger scenes.
• Ground truth. As accuracy reaches the centimetre level, the error of the reference poses, and their bias toward the method that produced them, becomes part of what benchmarks measure.
• Multi-image and sequential localization. Sattler et al. (2018) found a clear benefit from localizing several images together and little existing work on it.