Loop Closure

Loop closure is the part of simultaneous localization and mapping that recognizes when a camera, robot or vehicle has come back to a place it has already mapped, and uses that recognition to correct the map and trajectory. Visual odometry and other incremental trackers let small errors add up, so after a long excursion the estimated position of a revisited place disagrees with where it was first mapped. A detected loop links the current pose to the old one with a measured relative transformation, and the back-end spreads the accumulated discrepancy over the whole loop. The detection half, often called loop-closure detection or appearance-based loop detection, is a form of visual place recognition in which the database is the robot’s own past.

Gálvez-López and Tardós (2012) open their DBoW2 paper by calling robust place recognition one of the most significant requirements for long-term visual SLAM: once areas not observed for a long time are re-observed, standard matching fails, while detected loop closures supply correct data association for a consistent map. The same machinery serves relocalization, recovering the pose after tracking is lost through sudden motion, occlusion or blur. The task has an unusual asymmetry. A missed loop leaves drift in place; an accepted false loop inserts a wrong constraint that can bend the whole map, so detectors have long been judged by how many true loops they find while making no false detections at all (Lowry et al., 2016).

Problem Definition

A sensor produces frames $I_1, I_2, \dots$ (images, or keyframes selected from them; LiDAR scans in the range-sensor case). When frame $I_t$ arrives, loop-closure detection decides whether some earlier frame $I_j$ shows the same place, and if so which one. Angeli, Filliat, Doncieux and Meyer (2008) write the decision as the choice of a hypothesis $S_t = i$ , that the current image $I_t$ closes the loop with past image $I_i$ , against the extra hypothesis $S_t = -1$ that no loop closure occurred, and search only over $i \le t - p$ : the last $p$ frames always look like the current one because they were taken from nearby, and including them would produce trivial detections of the recent past ( $p = 10$ in their experiments, set by frame rate and camera speed).

A detection that will be used as a constraint must also deliver geometry: point correspondences between $I_t$ and $I_j$ and the relative pose between the two viewpoints: a similarity transformation for a single camera, whose map can also drift in scale (Mur-Artal, Montiel and Tardós, 2015), and a rigid transformation when stereo, depth or LiDAR measurements fix the scale. The relative pose becomes a new edge in the estimation problem of the SLAM back-end, and that edge is what removes drift.

What counts as “the same place” is an application choice. Datasets for loop detection usually lack it, and Gálvez-López and Tardós built their ground truth by hand, as lists of query time intervals paired with matching intervals. Others define it by a distance between camera positions, as the place-recognition benchmarks do with their localization radius. The choice changes every reported number; the example below prints its results for two radii.

Input and Output

Input: a stream of images or scans, usually with odometry poses; local features and their descriptors for each frame (often the same features the tracker uses); for keyframe systems, the covisibility structure linking keyframes that observe the same map points.
Output: for each new frame, either “no loop” or a matched past frame with a confidence, the verified feature correspondences, and the relative transformation, $\mathrm{SE}(3)$ or $\mathrm{Sim}(3)$ , with an uncertainty for the back-end.

Variants

Image-to-image, image-to-map and map-to-map. A loop can be found by comparing images, by matching the current image against map features, or by matching submaps. Both Gálvez-López and Tardós (2012) and Mur-Artal et al. (2015) cite a comparison by Williams et al. that concluded that map-to-image methods work well in small environments but appearance-based image-to-image methods scale better in large ones; most of this article concerns the image-to-image family.
Monocular, stereo and RGB-D. With one camera the loop transformation has seven degrees of freedom (three of rotation, three of translation, one of scale), because the map can drift in scale (Mur-Artal et al., 2015); stereo and depth sensors fix scale, leaving six.
LiDAR. Range sensors detect loops by comparing scan descriptors rather than images, and register the scans to get the relative pose (below).
Relocalization and map merging. The query is the same, “where in the map am I?”, but it is triggered by lost tracking or by a new session rather than by a revisit during exploration. DBoW2’s authors note that the same methods serve relocalization, and ORB-SLAM uses one place-recognition database for both.
Online and offline. A robot must decide as frames arrive, against a database that grows; offline mapping can compare all pairs after the fact, as large structure from motion reconstructions do when they choose image pairs to match.

Challenges

Perceptual aliasing. Different places can look alike: office corridors, rows of identical windows, warehouse aisles. Lowry et al. (2016) name this problem, and Gálvez-López and Tardós (2012) give it as the main reason bags of words are not a complete solution for closing loops, which is why they verify candidates geometrically.
The cost of a false positive. Lowry et al. write that place recognition long prioritized avoiding false positive matches, because introducing a false match into a map could cause catastrophic failure. A wrong loop is an edge that disagrees with the odometry around it; a least-squares back-end weights it like any other constraint and bends the trajectory to satisfy it. The SLAM article’s pose-graph example notes that a false loop closure would look just as inconsistent with the odometry as the correct one it adds.
The cost of a false negative. A missed loop leaves the drift uncorrected and may leave the same place mapped twice, with duplicated landmarks.
Appearance and viewpoint change. A place seen at another time of day, in another season, from the other lane or the opposite direction produces different features; the visual place recognition article covers these changes and the descriptors built for them. Dynamic objects matter too: in Angeli et al.’s outdoor sequence, pedestrians and cars passing in front of the camera repeatedly caused correct hypotheses to be rejected for lack of correspondences.
Temporal neighbours. Consecutive frames are nearly identical, so the recent past has to be excluded or grouped, and several frames of one earlier visit compete for the same match.
Scale and real time. The database grows with the trajectory, and the detector shares the processor with tracking and mapping. Gálvez-López and Tardós write that feature extraction is usually the bottleneck of loop-closure algorithms, around ten times more expensive than the remaining steps.

Approaches

From map matching to appearance

Matching against the map, predicting where known landmarks should appear and associating them, depends on a pose estimate good enough to make the prediction, which is what drift destroys after a long loop: the SLAM article cites Durrant-Whyte and Bailey on the difficulty of re-observing landmarks after a long traverse, and Gálvez-López and Tardós write that standard matching fails when areas not observed for long are re-observed. Appearance-based methods ask only whether the current image looks like a stored one, so they do not rely on the drifted pose. They borrowed the bag of visual words from image retrieval: local descriptors are quantized into visual words, an image becomes a sparse histogram of words weighted by term frequency and inverse document frequency (tf-idf), and an inverted index, the list of images in which each word occurs, compares a query only with images that share words with it. DBoW2 takes the tf-idf weighting from Video Google and builds its vocabulary as a tree in the manner of Nistér and Stewénius’s vocabulary tree, the two works its bag of words cites. The retrieval side, including the aggregated and learned descriptors that later replaced plain word histograms, belongs to visual place recognition; what follows is the decision layer that turns retrieval scores into accepted loops.

Probabilistic appearance: FAB-MAP and Bayesian filtering

FAB-MAP (Cummins and Newman, 2008; not read for this article, described here through Lowry et al. and DBoW2) learns offline, with a Chow–Liu tree, how SIFT or SURF words co-occur, and gives a low match probability to two images whose shared words are frequently observed (Lowry et al., 2016); the visual place recognition article describes its model. Gálvez-López and Tardós report that FAB-MAP 2.0, the authors’ later system, detected loops with an omnidirectional camera with recalls of 48.4% and 3.1% and no false positives on trajectories of 70 km and 1,000 km; they call FAB-MAP the gold standard of loop detection but note that its robustness decreases when images show very similar structure for a long time, which can happen with frontal cameras.

Angeli et al. (2008) built the vocabulary online instead, incrementally as images arrive. Each image is described in two feature spaces, SIFT descriptors and local hue histograms over a grid of windows, and each space has its own incremental vocabulary. A discrete Bayes filter tracks the posterior over loop-closure hypotheses,

p(S_t \mid I^t) = c \; p(I_t \mid S_t)\; p(S_t \mid I^{t-1}),

where $I^t$ is the image sequence up to $t$ and $c$ a normalizing constant. The prior comes from the previous posterior through a transition model: no loop stays no loop with probability 0.9, and a loop hypothesis $j$ diffuses to its neighbours $j - 2, \dots, j + 2$ through a Gaussian in time, which builds temporal coherence into the decision. The likelihood comes from tf-idf voting through the inverted index: a hypothesis whose score $s_i$ exceeds the mean $\mu$ plus the standard deviation $\sigma$ of all scores gets the likelihood $(s_i - \sigma)/\mu$ , and every other hypothesis gets 1. The no-loop hypothesis is scored like an image, through a virtual image made of the most frequently seen words. When the current image comes from a new place, it shares more words with this “most likely image” than with any stored one; when it comes from a place that resembles several stored ones, part of the virtual image’s words come from those places, so it still scores high and holds back a premature detection. A hypothesis is accepted when the posterior summed over its neighbouring images exceeds 0.8 and the two images then pass an epipolar geometry check by RANSAC on SIFT matches; a rejected hypothesis’s probability does not drop to zero at once but diffuses to its neighbours, so a correct loop can be confirmed a few frames later. On an indoor sequence of 388 images with strong aliasing in its corridors and an outdoor sequence of 531 images, recorded with a handheld camera at 1 Hz and 0.5 Hz, the system made no false positive detections; with both feature spaces it detected 80% and 71% of the hand-labelled loop closures (their Table I), against 68% and 70% with SIFT alone. The table also counts false alarms, hypotheses that reached a high probability but were rejected by the geometric check: one indoors with colour added, none otherwise.

Bags of binary words: DBoW2

Gálvez-López and Tardós (2012) attacked the cost. They replaced SIFT and SURF, which earlier loop detectors computed in 100 to 700 ms per image, by FAST corners with BRIEF descriptors, strings of 256 intensity comparisons compared by Hamming distance, and built for the first time, in their words, a vocabulary tree that discretizes a binary descriptor space. The vocabulary is trained offline on an independent image set by k-medians clustering with k-means++ seeding, with medians that fall between 0 and 1 truncated to 0, repeated at each level: with branching factor $k_w = 10$ and $L_w = 6$ levels it has one million words, trained on 9 million features from 10,000 images of a separate dataset. Words are weighted by tf-idf, the idf computed from the training images as $\ln(N/N_i)$ (DBoW2 code), and two bag-of-words vectors are compared by an $L_1$ score in $[0, 1]$ ,

s(\mathbf{v}_1, \mathbf{v}_2) = 1 - \frac{1}{2}\left\lVert \frac{\mathbf{v}_1}{\lVert \mathbf{v}_1 \rVert_1} - \frac{\mathbf{v}_2}{\lVert \mathbf{v}_2 \rVert_1} \right\rVert_1 .

Besides the inverted index, the database keeps a direct index: for each image, its features grouped by their ancestor node at a chosen level $l$ of the vocabulary tree. The loop detector, released as DLoopDetector, then runs four stages.

Database query. The raw scores depend strongly on the query image, so each is divided by the score the query obtains against the previous image, the best score expected in this sequence:
$\eta(\mathbf{v}_t, \mathbf{v}_{t_j}) = \frac{s(\mathbf{v}_t, \mathbf{v}_{t_j})}{s(\mathbf{v}_t, \mathbf{v}_{t-\Delta t})} .$
When the robot turns, the previous-image score is small and can inflate $\eta$ erroneously, so images whose previous-image score falls below a minimum (0.005) are skipped, and candidates with $\eta < \alpha$ are rejected.
Match grouping. Matches with images close in time are grouped into islands so that they do not compete with one another, and each island is ranked by the sum of its normalized scores, $H = \sum_j \eta(\mathbf{v}_t, \mathbf{v}_{t_j})$ , which favours long islands: a real loop closure is similar to several consecutive past images.
Temporal consistency. The best island must be consistent with the islands matched by the previous $k$ queries, their intervals close to overlapping. Only then does the best image of the island become a loop candidate.
Geometric consistency. RANSAC must find a fundamental matrix between the two images supported by at least 12 correspondences. The direct index makes this fast: features are compared only if they fall under the same node at level $l$ , then filtered by the nearest-neighbour distance ratio with threshold 0.6.

All results use one parameter set, chosen on three training datasets and applied unchanged to two evaluation datasets: 300 features per image, $k = 3$ , $\alpha = 0.3$ and $l = 2$ (their Table IV; DLoopDetector’s code defaults add a RANSAC limit of 500 iterations and a reprojection threshold of 2 pixels). The ablations show what each stage buys. Without geometric checking, the authors observed a big improvement between $k = 0$ and $k > 0$ temporally consistent matches at all processing frequencies, and on Bicocca25b $k = 3$ behaved well at 1, 2 and 3 Hz. For the geometric check on the NewCollege dataset at 2 Hz, with precision 100% in every case, correspondences restricted to the same word ( $l = 0$ ) gave 38.3% recall in a median 0.43 ms per query, level $l = 2$ gave 56.1% in 0.78 ms, and exhaustive search 61.2% in 14.17 ms (their Table II); a FLANN k-d tree search was nearly as slow as exhaustive search, because the tree has to be built for every image. On NewCollege processed at 10 Hz, 26,292 images (26,300 in the abstract), the whole system averaged 21.60 ms per image with a maximum of 51.68 ms on an Intel Core i7 at 2.67 GHz, feature extraction included (their Table III), with no false positives.

At 100% precision the final system’s recall was 55.92% on NewCollege, 81.20% on Bicocca25b and 79.45% on Ford2 (training datasets) and 74.75% on Malaga6L and 30.61% on CityCentre (evaluation datasets; their Table V). The authors ran FAB-MAP 2.0 with its default configuration on the evaluation datasets, adding a fundamental-matrix check with exhaustive matching because FAB-MAP returns unverified matches, and choosing its probability threshold of 98% because it gave the highest recall at 100% precision on these datasets; it reached 68.52% on Malaga6L and 38.77% on CityCentre (their Table VI). They attribute the difference on CityCentre to the larger change between loop-closure images there, which hinders their direct-index matching and, in their words, highlights the little invariance of BRIEF, since SURF may produce more similar features; they name this lack of invariance as the main limitation of the technique: enough for indoor and urban robots moving in a plane, but not for all-terrain or aerial vehicles, humanoid robots or wearable cameras. ORB-SLAM’s authors built the same kind of recognizer on ORB descriptors, which they describe as invariant to rotation and to scale within a range.

Loop detection in a keyframe SLAM system

ORB-SLAM (Mur-Artal et al., 2015) embeds a DBoW2 database of ORB words over its keyframes and adapts each stage to the information a SLAM system has. Instead of the previous image, the reference score is the lowest score between the new keyframe and its neighbours in the covisibility graph (keyframes sharing at least 30 map points), and database results below it are discarded, as are keyframes directly connected to the new one. Instead of islands of images close in time, keyframes connected in the covisibility graph are grouped, so that views of one place inserted at different times also reinforce each other, and the database returns every keyframe scoring above 75% of the best. A loop candidate is accepted only after three consecutive consistent detections. Geometric verification then works in 3D: the ORB features attached to map points in both keyframes are matched, again restricted to the same vocabulary node at the second of six levels and checked for a coherent rotation, and RANSAC with Horn’s closed-form method (see the Kabsch algorithm) estimates a similarity transformation from the 3D–3D correspondences; the loop is accepted if the similarity, refined and re-supported by a guided search, keeps enough inliers. The authors note that this similarity both validates the loop and measures the drift accumulated around it, scale included. How ORB-SLAM fuses the duplicated map points and corrects the map is described with ORB-SLAM itself.

Geometric verification

Verification asks whether the tentative feature matches between the two frames agree on one geometric transformation, almost always through RANSAC. The model follows from what is known about the scene and the cameras:

Situation	Model	Minimal sample
Two uncalibrated images of a general scene	Fundamental matrix (DBoW2; Angeli et al.’s epipolar check)	7 or 8 correspondences
Two calibrated images of a general scene	Essential matrix	5 correspondences
A planar scene, or a camera that only rotated	Homography	4 correspondences
3D points in both frames (stereo, RGB-D, map points)	Rigid or similarity transformation (ORB-SLAM)	3 correspondences
Current image against stored map points	Perspective-n-point	3 or more correspondences

The essential matrix and homography articles give the estimators, and perspective-n-point the 2D–3D case used in relocalization. Two practical points follow from the model choice. A fundamental matrix is not determined by points on a single plane, so on a planar scene the epipolar test is degenerate and the homography is the appropriate check. And verification tests consistency, not identity: a different place whose visible structure repeats the query’s, a symmetric facade or identical tiles, can supply a geometrically consistent set of matches, the case the feature matching article lists among its open problems. Minimum inlier counts (12 in DBoW2) and the requirement of several consecutive detections reduce that risk without removing it. Matching rules interact with repetition as well: the ratio test rejects a match whose second-nearest neighbour is nearly as close, which on repeated structure discards correct but ambiguous matches.

Learned place descriptors

Global descriptors trained for place recognition, such as NetVLAD and the foundation-model descriptors that followed, are built to retrieve candidates across changes of lighting and season, and the visual place recognition article covers them with their benchmarks; there, too, a geometric re-ranking stage such as Patch-NetVLAD’s checks the shortlist. Lowry et al. (2016) describe a related shift in how place recognition is used for loop closure: rather than demanding that the place recognizer itself make no false positive, systems accept more candidate matches and correct the wrong ones afterwards in a topological post-processing step, which matters most in changing environments, where strict matching fails.

LiDAR loop closure in outline

LiDAR odometry registers successive scans, for example with iterative closest point, and drifts like visual odometry; LOAM, as the SLAM article notes, performs no loop closure. Loop detection for LiDAR needs a descriptor of a whole scan that is cheap to compare and does not depend on the sensor’s heading. Scan Context (Kim and Kim, 2018; the paper was not read for this article, and the description follows the authors’ code) divides the area around the sensor into 20 rings and 60 sectors out to 80 m, the values of the original paper according to the code’s comments, and stores the maximum point height in each bin, giving a $20 \times 60$ matrix in egocentric polar coordinates. A heading change shifts its columns circularly, so the row means (the ring key) are invariant to heading. Candidates are retrieved by a k-d tree on the ring keys (10 candidates, excluding the 50 most recent scans), and each candidate is compared by shifting its columns to the best alignment and averaging the cosine similarity of corresponding non-empty columns (the code first estimates the shift from the column means and then searches a few shifts around it, a speed-up its comments mark as not in the original paper); one minus this average is the distance, and the best shift also gives the yaw between the scans. A loop is declared below a distance threshold, 0.13 in the code, whose comment calls values from 0.1 to 0.2 fine with rare false alarms for the $20 \times 60$ size and recommends a robust kernel or an ICP fitness check at larger thresholds. The README presents the combination of LiDAR odometry with Scan Context for loop detection and a factor-graph library for the correction as a complete LiDAR SLAM system. The detected pair still has to be registered, for example by ICP started from the estimated yaw, to obtain the relative pose that enters the graph; the code’s comments mention an ICP fitness score as an extra check.

From a detected loop to a corrected map

Once verified, a loop becomes a relative-pose constraint between the two frames, a loop-closure factor in the factor graph of the back-end, alongside the odometry factors between consecutive frames. Optimizing the graph distributes the discrepancy the loop reveals over the poses of the loop, as the SLAM article’s example shows for a 2D pose graph; in monocular systems the constraint is a similarity transformation so that scale drift is corrected too (Mur-Artal et al., 2015). Because no front-end is free of false positives, back-ends are made to tolerate them: Lowry et al. (2016) cite methods that correct false positive matches afterwards, among them inference on networks of mixtures (Olson and Agarwal), switchable constraints (Sünderhauf and Protzel) and robust loop closing over time (Latif, Cadena and Neira). Pose graph optimization covers the optimization and these robust formulations, and ORB-SLAM the correction of a complete visual SLAM map.

Example

The script below detects loops along a route with known ground truth and scores the detections by precision and recall. A downward-looking camera drives twice over part of a square route on a tiled floor. Each floor tile is $24 \times 24$ pixels with three random grey rectangles on a grey background; the floor is $42 \times 42$ tiles. On the unique floor every tile is different; on the repeated floor every tile is one of six designs, turned by a multiple of 90°, so that every place is built from the same few patterns, like a corridor or a warehouse floor. The camera, 120 pixels above the floor with a focal length of 120 pixels and tilted by 8° about its image $x$ -axis, which points along the direction of travel (the code’s comment calls this a forward pitch, forward in the image’s own frame), renders $120 \times 120$ images by intersecting each pixel’s ray with the floor plane, so two views of the same floor are related by a homography. Rotations are camera-to-world; the yaw is the direction of travel plus 3° of noise. The route is a square of side 600 floor pixels driven in 8-pixel steps: 300 frames complete the first lap, and 120 more frames repeat 40% of it on a path 15 pixels further in and with 15% less light, with small random changes of gain, offset and noise in every frame.

The detector follows DBoW2 in simplified form. Features are 150 ORB keypoints per image from scikit-image, binary like DBoW2’s BRIEF. The vocabulary of 400 words is learned on a separate floor by binary k-medians (each bit of a centre is the majority of its members’ bits), flat rather than a tree and seeded randomly rather than with k-means++; idf weights, $L_1$ -normalized tf-idf vectors, the $L_1$ score and the normalized score $\eta$ follow the formulas above. Frame $t$ is compared with every frame up to $t - 41$ (the last 40 frames, 320 floor pixels of travel, are excluded), and its best match $j^\ast$ becomes a detection when $\eta \ge \alpha$ . The verified detector also requires that RANSAC find a homography, the right model for a plane, with at least 12 inliers within 2 pixels among the matches between $t$ and $j^\ast$ ; 500 random four-point samples are drawn, each solved by the normalized direct linear transform. How to form those matches is left open by the sources for a floor like this, so the script prints two rules: DBoW2’s nearest-neighbour ratio test with threshold 0.6 (over all features, not within vocabulary nodes) and mutual nearest neighbours. There are no islands or temporal consistency, so the example isolates the effect of geometric verification.

A query frame is a loop event if some earlier frame outside the exclusion window was taken within $R$ floor pixels of it, and a detection $(t, j^\ast)$ is correct if the two camera positions are within $R$ ; precision is the fraction of detections that are correct, recall the fraction of loop events detected correctly, as DBoW2 defines them. The radius is an evaluation choice that the sources leave open, so the script prints $R = 40$ pixels and $R = 60$ pixels, half the image width. For each detector it prints the recall at 100% precision for each seed, the largest recall at a threshold $\alpha$ that admits no wrong detection, and the mean precision and recall over three seeds at $\alpha = 0.3$ (DBoW2’s value), 0.7 and 0.9, followed by the share of best candidates that pass each verification rule, split by whether the candidate lies within 60 pixels of the query.

The example was planned with its hypotheses before running. A pilot on the unique floor confirmed that the ground truth contains loop events, that a detector picking the nearest earlier position scores perfect precision and recall, and that all three detectors find true loops at 100% precision. After the pilot, before the first run, three changes were made and logged: the second radius was added because the pilot counted verified detections of overlapping views as false at $R = 40$ ; of the planned operating points, “alpha = 0.3 (DBoW2’s value), 0.5, 0.7”, 0.5 was replaced by 0.9, because in the pilot 0.5 admitted the same detections as 0.3; and scikit-image’s ransac was replaced by the batched NumPy version below, with the same sampling, model, threshold and inlier test, for speed. Nothing changed after the first run, and a second run printed identical output. The script ran in two to four minutes in our runs (multithreaded), with Python 3.13, NumPy 2.3.5, SciPy 1.16.3 and scikit-image 0.25.2.

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

T, NT, SIZE, H, PITCH = 24, 42, 120, 120.0, np.radians(8)  # tile px, tiles per side, view px, height, pitch
P_EXCL, K_WORDS = 40, 400                                    # excluded recent frames; vocabulary size

def make_tile(rng):
    t = np.full((T, T), rng.uniform(0.3, 0.7))
    for _ in range(3):
        y, x = rng.integers(0, T - 6, 2); h, w = rng.integers(4, 12, 2)
        t[y:y + h, x:x + w] = rng.uniform(0, 1)
    return ndimage.gaussian_filter(t, 0.8)

def make_floor(rng, n_designs=None):
    """Unique tiles, or every tile one of n_designs designs turned by a multiple of 90 degrees."""
    if n_designs is None:
        rows = [[make_tile(rng) for _ in range(NT)] for _ in range(NT)]
    else:
        lib = [make_tile(rng) for _ in range(n_designs)]
        rows = [[np.rot90(lib[rng.integers(n_designs)], rng.integers(4)) for _ in range(NT)] for _ in range(NT)]
    return np.block(rows)

def render(floor, X, Y, yaw):
    """Downward camera at (X, Y), height H, pitched forward: each pixel's ray meets the floor plane."""
    v, u = np.mgrid[0:SIZE, 0:SIZE].astype(float)
    d = np.stack([u - SIZE / 2, v - SIZE / 2, np.full_like(u, H)], -1)   # focal length H pixels
    cy, sy, cp, sp = np.cos(yaw), np.sin(yaw), np.cos(PITCH), np.sin(PITCH)
    Rz = np.array([[cy, -sy, 0], [sy, cy, 0], [0, 0, 1]])
    Rx = np.array([[1, 0, 0], [0, cp, -sp], [0, sp, cp]])
    dw = d @ (Rz @ np.diag([1.0, -1.0, -1.0]) @ Rx).T                    # camera-to-world rotation
    t = -H / dw[..., 2]
    return ndimage.map_coordinates(floor, [Y + t * dw[..., 1], X + t * dw[..., 0]], order=1, mode="nearest")

def route(rng):
    """A 600 px square driven in 8 px steps: 300 frames per lap, 420 frames; lap 2 runs 15 px further in."""
    c, half, n_lap = NT * T / 2, 300.0, 300
    dirs, starts = [(1, 0), (0, 1), (-1, 0), (0, -1)], [(-1, -1), (1, -1), (1, 1), (-1, 1)]
    pos, yaw = [], []
    for k in range(420):
        s = (k % n_lap) * 8.0 + 150.0
        side, a = int(s // 600) % 4, s % 600
        off = half - (15.0 if k >= n_lap else 0.0)
        (dx, dy), (sx, sy) = dirs[side], starts[side]
        pos.append((c + sx * off + dx * a * off / half + rng.normal(0, 1),
                    c + sy * off + dy * a * off / half + rng.normal(0, 1)))
        yaw.append(np.arctan2(dy, dx) + rng.normal(0, np.radians(3)))
    return np.array(pos), np.array(yaw), n_lap

def photometric(img, rng, gain=1.0):
    img = gain * rng.uniform(0.9, 1.1) * img + rng.uniform(-0.05, 0.05)
    return np.clip(img + rng.normal(0, 0.02, img.shape), 0, 1)

def features(img):
    orb = ORB(n_keypoints=150, fast_threshold=0.05)
    orb.detect_and_extract(img)
    return orb.keypoints[:, ::-1].copy(), orb.descriptors.astype(bool)   # (x, y) and 256 bits

def hamming(a, b):
    a, b = a.astype(np.float32), b.astype(np.float32)
    return a @ (1 - b).T + (1 - a) @ b.T

def train_vocabulary(rng):
    """Binary k-medians (bitwise majority) on ORB descriptors of a separate floor; idf = ln(N / N_i)."""
    floor = make_floor(rng)
    descs = []
    for _ in range(150):
        X, Y = rng.uniform(150, NT * T - 150, 2)
        descs.append(features(photometric(render(floor, X, Y, rng.uniform(-np.pi, np.pi)), rng))[1])
    allD = np.vstack(descs)
    C = allD[rng.choice(len(allD), K_WORDS, replace=False)].copy()
    for _ in range(8):
        lab = np.argmin(hamming(allD, C), 1)
        for k in range(K_WORDS):
            m = allD[lab == k]
            C[k] = m.mean(0) > 0.5 if len(m) else allD[rng.integers(len(allD))]
    Ni = np.zeros(K_WORDS)
    for d in descs:
        Ni[np.unique(np.argmin(hamming(d, C), 1))] += 1
    idf = np.where(Ni > 0, np.log(len(descs) / np.maximum(Ni, 1)), 0.0)
    return C, idf

def bow(desc, C, idf):
    """tf-idf bag of words, L1-normalized (words with idf 0 carry no weight)."""
    v = np.bincount(np.argmin(hamming(desc, C), 1), minlength=len(C)) / len(desc) * idf
    return v / v.sum()

def l1_score(a, B):
    return 1 - 0.5 * np.abs(B - a).sum(-1)     # DBoW2's L1 score, in [0, 1]

def dlt(src, dst):
    """Batched 4-point homographies, src and dst of shape (M, 4, 2), in normalized coordinates."""
    x, y, u, v = src[..., 0], src[..., 1], dst[..., 0], dst[..., 1]
    z, o = np.zeros_like(x), np.ones_like(x)
    A = np.concatenate([np.stack([x, y, o, z, z, z, -u * x, -u * y, -u], -1),
                        np.stack([z, z, z, x, y, o, -v * x, -v * y, -v], -1)], 1)
    return np.linalg.svd(A)[2][:, -1].reshape(-1, 3, 3)

def normalizer(p):
    m = p.mean(0); s = np.sqrt(2) / np.mean(np.linalg.norm(p - m, axis=1))
    return np.array([[s, 0, -s * m[0]], [0, s, -s * m[1]], [0, 0, 1]])

def ransac_inliers(src, dst, rng, trials=500, tol=2.0):
    """Largest inlier count of 500 random 4-point homographies (one-way transfer error < tol px)."""
    T1, T2 = normalizer(src), normalizer(dst)
    hs = lambda p, Tn: (np.c_[p, np.ones(len(p))] @ Tn.T)[:, :2]
    idx = rng.random((trials, len(src))).argsort(1)[:, :4]
    Hn = dlt(hs(src, T1)[idx], hs(dst, T2)[idx])
    Hs = np.linalg.inv(T2) @ Hn @ T1
    with np.errstate(divide="ignore", invalid="ignore"):
        q = np.einsum("mij,nj->mni", Hs, np.c_[src, np.ones(len(src))])
        err = np.linalg.norm(q[..., :2] / q[..., 2:] - dst, axis=-1)
    return int(np.max(np.sum(err < tol, axis=1)))

def verify(f1, f2, rule, rng):
    """Geometric check of a loop candidate: correspondences by Hamming distance, then RANSAC."""
    (k1, d1), (k2, d2) = f1, f2
    D = hamming(d1, d2)
    nn = np.argmin(D, 1)
    if rule == "ratio 0.6":
        s = np.sort(D, 1)
        keep = s[:, 0] < 0.6 * s[:, 1]
    else:                                         # mutual nearest neighbours
        keep = np.argmin(D, 0)[nn] == np.arange(len(d1))
    if keep.sum() < 12:
        return False
    return ransac_inliers(k1[keep], k2[nn[keep]], rng) >= 12

def detect(seed, n_designs):
    """Run one route; return per-query eta, verification results, and distance to the candidate."""
    rng = np.random.default_rng(seed)
    C, idf = train_vocabulary(np.random.default_rng(seed + 100))
    floor = make_floor(rng, n_designs)
    pos, yaw, n_lap = route(rng)
    feats, V = [], []
    for k in range(len(pos)):
        img = photometric(render(floor, *pos[k], yaw[k]), rng, 0.85 if k >= n_lap else 1.0)
        feats.append(features(img)); V.append(bow(feats[-1][1], C, idf))
    V = np.array(V)
    Q = np.arange(P_EXCL + 1, len(pos))
    dist = np.linalg.norm(pos[:, None] - pos[None], axis=-1)
    eta, jstar = [], []
    for t in Q:
        s = l1_score(V[t], V[:t - P_EXCL])        # database: frames up to t - 41
        prev = l1_score(V[t], V[t - 1:t])[0]
        j = int(np.argmax(s)); jstar.append(j)
        eta.append(s[j] / prev if prev >= 0.005 else -np.inf)   # DBoW2's normalized score
    vrng = np.random.default_rng(seed + 200)
    ver = {r: np.array([verify(feats[t], feats[j], r, vrng) for t, j in zip(Q, jstar)])
           for r in ["ratio 0.6", "mutual NN"]}
    return dict(eta=np.array(eta), ver=ver, dcand=np.array([dist[t, j] for t, j in zip(Q, jstar)]),
                dmin=np.array([dist[t, :t - P_EXCL].min() for t in Q]))

def score(r, ok, R, alphas):
    """Precision/recall of detections (eta >= alpha and ok) against revisits within R px."""
    tp, events = r["dcand"] <= R, (r["dmin"] <= R).sum()
    th = np.unique(r["eta"][ok])[::-1]
    best = 0.0                                    # recall at 100% precision
    for a in th:
        det = ok & (r["eta"] >= a)
        if tp[det].all():
            best = tp[det].sum() / events
    pr = []
    for a in alphas:
        det = ok & (r["eta"] >= a)
        pr.append((tp[det].mean() if det.any() else np.nan, tp[det].sum() / events))
    return best, pr, events

mode = sys.argv[1] if len(sys.argv) > 1 else "full"
seeds = [0] if mode == "pilot" else [0, 1, 2]
floors = [("unique tiles", None)] if mode == "pilot" else [("unique tiles", None), ("6 repeated designs", 6)]
alphas = [0.3, 0.7, 0.9]
for fname, nd in floors:
    runs = [detect(s, nd) for s in seeds]
    print(f"=== floor: {fname}; seeds {seeds}")
    for R in [40, 60]:
        print(f"  ground-truth radius R = {R} px; loop events per seed {[int((r['dmin'] <= R).sum()) for r in runs]}")
        for name in ["appearance only", "verified, ratio 0.6", "verified, mutual NN"]:
            res = []
            for r in runs:
                ok = np.isfinite(r["eta"]) & (r["ver"][name.split(", ")[1]] if "verified" in name else True)
                res.append(score(r, ok, R, alphas))
            r100 = " ".join(f"{b:.2f}" for b, _, _ in res)
            pr = "  ".join(f"a={a}: P {np.nanmean([x[1][i][0] for x in res]):.2f} R {np.mean([x[1][i][1] for x in res]):.2f}"
                           for i, a in enumerate(alphas))
            print(f"    {name:20s} R@P100 per seed {r100} | {pr}")
    for rule in ["ratio 0.6", "mutual NN"]:
        good = np.mean([r["ver"][rule][r["dcand"] <= 60].mean() for r in runs])
        bad = np.mean([r["ver"][rule][r["dcand"] > 60].mean() for r in runs])
        print(f"  {rule}: passes {good:.2f} of candidates within 60 px, {bad:.3f} of candidates farther away")

Output:

=== floor: unique tiles; seeds [0, 1, 2]
  ground-truth radius R = 40 px; loop events per seed [124, 124, 124]
    appearance only      R@P100 per seed 0.37 0.07 0.15 | a=0.3: P 0.32 R 0.98  a=0.7: P 0.40 R 0.98  a=0.9: P 0.88 R 0.80
    verified, ratio 0.6  R@P100 per seed 0.61 0.06 0.15 | a=0.3: P 0.98 R 0.97  a=0.7: P 0.98 R 0.97  a=0.9: P 0.98 R 0.80
    verified, mutual NN  R@P100 per seed 0.61 0.07 0.15 | a=0.3: P 0.98 R 0.98  a=0.7: P 0.98 R 0.98  a=0.9: P 0.98 R 0.80
  ground-truth radius R = 60 px; loop events per seed [127, 127, 127]
    appearance only      R@P100 per seed 0.36 0.57 0.14 | a=0.3: P 0.33 R 0.98  a=0.7: P 0.41 R 0.98  a=0.9: P 0.89 R 0.80
    verified, ratio 0.6  R@P100 per seed 0.97 0.96 0.98 | a=0.3: P 1.00 R 0.97  a=0.7: P 1.00 R 0.97  a=0.9: P 1.00 R 0.79
    verified, mutual NN  R@P100 per seed 0.98 0.98 0.98 | a=0.3: P 1.00 R 0.98  a=0.7: P 1.00 R 0.98  a=0.9: P 1.00 R 0.80
  ratio 0.6: passes 0.99 of candidates within 60 px, 0.000 of candidates farther away
  mutual NN: passes 1.00 of candidates within 60 px, 0.000 of candidates farther away
=== floor: 6 repeated designs; seeds [0, 1, 2]
  ground-truth radius R = 40 px; loop events per seed [125, 124, 125]
    appearance only      R@P100 per seed 0.02 0.03 0.14 | a=0.3: P 0.31 R 0.96  a=0.7: P 0.34 R 0.96  a=0.9: P 0.68 R 0.86
    verified, ratio 0.6  R@P100 per seed 0.94 0.22 0.74 | a=0.3: P 0.98 R 0.91  a=0.7: P 0.98 R 0.91  a=0.9: P 0.98 R 0.82
    verified, mutual NN  R@P100 per seed 0.50 0.25 0.26 | a=0.3: P 0.96 R 0.96  a=0.7: P 0.96 R 0.96  a=0.9: P 0.97 R 0.86
  ground-truth radius R = 60 px; loop events per seed [127, 127, 127]
    appearance only      R@P100 per seed 0.02 0.03 0.13 | a=0.3: P 0.32 R 0.97  a=0.7: P 0.35 R 0.97  a=0.9: P 0.70 R 0.86
    verified, ratio 0.6  R@P100 per seed 0.92 0.88 0.92 | a=0.3: P 1.00 R 0.91  a=0.7: P 1.00 R 0.91  a=0.9: P 1.00 R 0.81
    verified, mutual NN  R@P100 per seed 0.72 0.90 0.98 | a=0.3: P 0.99 R 0.97  a=0.7: P 0.99 R 0.97  a=0.9: P 1.00 R 0.86
  ratio 0.6: passes 0.94 of candidates within 60 px, 0.000 of candidates farther away
  mutual NN: passes 1.00 of candidates within 60 px, 0.006 of candidates farther away

On the unique floor the appearance score finds the right place almost every time: at $\alpha = 0.3$ its recall is 0.98, so for nearly every loop event the best-scoring earlier frame is a true revisit. What it cannot do is say when there is no revisit. Of the 379 queries per route (frames 41 to 419), only about a third are loop events, and the precision at $\alpha = 0.3$ equals that share: the threshold admits nearly every query, so nearly every frame of the first lap reports its best, wrong, match as a loop. Raising $\alpha$ to 0.9 lifts precision to 0.88 but drops a fifth of the true loops, and the recall at 100% precision is small and erratic across seeds, set by the single wrong candidate with the highest $\eta$ . In our reading, the normalization by the previous frame is partly responsible: the route turns by 90° between consecutive frames at its corners, and a weak score with the previous frame inflates $\eta$ , the case DBoW2’s authors warn about for a turning robot. A threshold that separates loops from non-loops would have to be tuned for each sequence, which is the tuning Gálvez-López and Tardós avoided by verifying candidates geometrically instead.

Verification separates the two cleanly here. With $R = 60$ , both verified detectors reach precision 1.00 at every printed threshold, with recall 0.97 to 0.98 at $\alpha = 0.3$ and 0.7 and recall at 100% precision of 0.96 to 0.98 on every seed, and both pass essentially every candidate within 60 pixels and none farther away. At $R = 40$ the same detections score lower and the recall at 100% precision collapses on two seeds; since the detections are identical, the difference is in the labels: some verified detections join views 40 to 60 pixels apart, which overlap over at least half of the image and pass verification, but count as false at the stricter radius. The ground-truth definition decides what a “false positive” is, and comparisons across papers are only valid under the same one.

The repeated floor is where perceptual aliasing appears. Every place shares the same few words, and the appearance-only detector’s recall at 100% precision falls to 0.02 to 0.14, while its precision at $\alpha = 0.9$ drops from 0.88–0.89 to 0.68–0.70: a stricter threshold removes fewer of the false loops, as expected when aliased places score as high as true revisits. Verification restores precision, but the two matching rules now differ. The ratio test passes no candidate farther than 60 pixels and keeps precision at 1.00, at a cost in recall, 0.91 against 0.97: it passes 94% of the candidates within 60 pixels rather than 99% as on the unique floor, in our reading because the same tile design recurs within each view and makes correct matches ambiguous. Mutual nearest neighbours keep essentially every true candidate but let through 0.6% of the wrong ones, enough to lower precision to 0.99 at $R = 60$ and to cap the recall at 100% precision at 0.72 on one seed. In our reading, those are places where a few tiles happen to repeat the query’s designs, rotations and arrangement, so that at least 12 matches agree with one homography: geometrically consistent aliasing, which no single-pair check can exclude. Three of the plan’s predictions failed. For the unique floor it predicted that “both detectors reach 100% precision with recall >= 0.7 at some alpha”, which the appearance-only detector did not at either radius and the verified detectors did only at $R = 60$ pixels; for the repeated floor it predicted “100% precision at alpha = 0.3” for the verified detector with mutual nearest neighbours, which the geometrically consistent false loops prevented, and for the ratio test “lower recall than mutual NN (guess about half)”, whereas the ratio test cost far less than half. The example has no temporal consistency check; DBoW2’s requirement of $k = 3$ consistent previous matches and ORB-SLAM’s three consecutive consistent candidates are aimed at exactly the isolated false loops that remain here.

Datasets and Benchmarks

Loop-closure detectors have mostly been evaluated on robot datasets with hand-labelled or GPS-derived revisits rather than on a shared benchmark. Gálvez-López and Tardós (2012) used five public sequences (their Table I): New College (frontal camera, outdoors and dynamic, 2,260 m of trajectory of which 1,570 m are revisited), Bicocca 2009-02-25b from the Rawseeds project (indoors, 760 m, 113 m revisited), Ford Campus 2 (urban, 4,004 m, 280 m revisited), Malaga 2009 Parking 6L (outdoors, 1,192 m, 162 m revisited) and City Centre (a lateral camera, images gathered at low frequency with little overlap, 2,025 m, 801 m revisited), the last taken from the FAB-MAP paper. The other four record at 8 to 20 Hz and were processed at lower rates. Because most of them do not mark loop closures, the authors labelled the loop intervals by hand.

Among datasets with articles here, the KITTI odometry sequences contain several loops, listed in the SLAM article, and are used to show the effect of loop closing on trajectory error, for example in ORB-SLAM’s comparison of loop-closing strategies on sequence 09; TUM RGB-D includes sequences with loop closures and serves for relocalization experiments, for example ORB-SLAM’s. Place-recognition benchmarks such as Nordland and Mapillary SLS, described in the visual place recognition article, test the retrieval stage under appearance change but not the online loop decision.

Evaluation Metrics

Loop detection is scored as a binary decision per query with precision and recall (Lowry et al., 2016): precision is the fraction of fired detections that are correct, recall the fraction of the true loop events that are detected. Gálvez-López and Tardós spell out details that are usually left implicit: a detection is a pair of query and match timestamps, correct if the ground truth has an interval containing both; the number of loop events is the total length of the ground-truth query intervals times the processing frequency; and a query that matches several earlier traversals counts once. Recall therefore depends on the frame rate and on how the ground truth is drawn, and figures are comparable only under the same protocol.

Sweeping the decision threshold gives a precision–recall curve. Because a single false loop can corrupt a map, the figure most often reported has been the recall at 100% precision, the largest recall reachable without any false detection; Lowry et al. call it, until recently, the key metric for place recognition, and DBoW2’s and FAB-MAP 2.0’s numbers above are of this kind. Lowry et al. also note two developments: systems that correct false matches downstream accept a lower front-end precision in exchange for more candidates, and evaluation for deployment can consider where matches occur, for example the probability of travelling a given distance without a successful match, which McManus, Churchill and colleagues used. The downstream effect of loop closure is measured on the trajectory, by absolute trajectory error against ground truth. Retrieval measures such as Recall@K evaluate the candidate list rather than the final decision.

Applications

SLAM: keeping maps and trajectories consistent over large loops in robots, vehicles and handheld devices, in visual, visual-inertial and LiDAR systems.
Relocalization: recovering the pose after tracking failure, with the same database (Gálvez-López and Tardós, 2012; Mur-Artal et al., 2015).
Multi-session mapping: recognizing that a new session starts in a place an earlier map covers, so that maps can be merged, as in ORB-SLAM3 according to the SLAM article.
Augmented reality and other long-running tracking, where drift would otherwise move virtual content away from its place.

Open Problems

Change over time. Lowry et al. (2016) describe place recognition in changing environments, across lighting, weather and seasons, as the field’s growing focus, and strict matching as liable to fail there.
Repetitive environments. Aliasing that is also geometrically consistent passes single-pair verification, as the example shows; temporal checks and robust back-ends reduce the damage without detecting it directly.
Invariance against speed. Binary features made loop detection cheap, but DBoW2’s authors name their lack of scale and rotation invariance as its main limitation, and learned global descriptors trade speed for robustness in the other direction.
Thresholds. Both the appearance threshold and LiDAR descriptor thresholds trade recall against false alarms in a way that depends on the environment; Scan Context’s code comments recommend different thresholds with and without a robust back-end.
Evaluation. Without shared ground truth for revisits, results depend on hand-labelled intervals, radii and frame rates, which makes cross-paper comparison difficult.