M5-T10 — Map Construction and Loop Closure

Learning objectives

After this lesson, you should be able to:

• Compare a sliding local map, keyframe submaps and a voxel map, and say what each is used for.
• Explain why loop candidates cannot be found by the drifted position alone.
• Compute a Scan Context descriptor and its column-shift distance on a small example.
• Describe the verification step and what happens when a false loop is accepted.

The problem and the intuition

Two things limit a long mission. First the map: if every scan ever taken were kept for matching, memory and time would grow without bound. Systems therefore match against a local map around the robot (the last few keyframes or a moving cube of voxels) and keep older parts only as keyframes in a graph. Second, drift: after a kilometre the position estimate can be tens of metres off, so asking “which earlier poses are within 10 m of here?” finds nothing, or the wrong thing.

The way out is to recognise places by how they look. A place has a shape signature, such as the height profile of the surroundings seen from above. If two scans taken at different times have the same signature (up to a rotation of the robot), the robot is probably at the same place. That recognition gives a candidate; geometry then checks it; and only a verified candidate becomes a loop factor in the graph (M4-T4).

Match the local map for odometry; recognise places by appearance for loop closure; verify geometrically before you let a loop change the graph.

The algorithm: maps, descriptors, retrieval, verification

Problem. Maintain a map that supports fast scan-to-map matching over unbounded trajectories, detect revisits despite accumulated drift and a change of heading, and add only correct loop constraints.

Assumptions. Places keep their large-scale structure between visits; the sensor is mounted with a consistent up axis; the environment contains enough vertical structure to describe a place; the verification step can reject look-alikes that differ in detail.

Map management

• Sliding local map. The union of the last n keyframes’ points (LIO-SAM) or a cube of side L around the robot (FAST-LIO2). Bounded size, used for odometry.
• Keyframe submaps. Each keyframe stores its (downsampled) scan with its pose in the graph. When the graph moves after a loop closure, the keyframes move with it and the global map can be rebuilt by re-projecting the stored scans.
• Voxel hashing / voxel grids. Store at most one point (or a plane fit) per voxel to bound memory per area; used as the compact global map.
• Pruning. Drop points far from the robot, merge near-duplicates and cap the points per voxel.

Scan Context (Kim and Kim, 2018)

1. Descriptor. Divide the plane around the sensor into N_r rings and N_s sectors (for example 20 × 60). In each cell store the maximum height of the points that fall in it (0 if empty). The result is a matrix I of size N_r × N_s. A rotation of the robot about the vertical axis is a cyclic shift of the columns.
2. Distance. For two descriptors I^q and I^c, take the average over columns of the cosine distance between column j of I^q and the corresponding column of I^c after shifting by s sectors; minimise over all shifts s: d(I^q, I^c) = min_s (1/N_s) Σ_j (1 − cos(I^q_j, I^c_j+s)). The minimising shift gives a coarse estimate of the relative yaw to initialise ICP.
3. Retrieval. Comparing a query with every stored descriptor under all shifts is too slow for long runs. A rotation-invariant ring key (one number per ring, such as the occupancy of that ring) is stored in a KD-tree; the nearest ring keys give a short list of candidates for the full distance.
4. Threshold and verify. Accept a candidate if d is below a threshold (for example 0.2), then run ICP between the query and the candidate’s submap, initialised with the yaw from the best shift; accept only if the registration fitness is good. Add the resulting relative pose as a loop factor with a robust kernel (M4-T5).

N_r, N_s

number of rings (radial bins) and sectors (angular bins).

ring key

rotation-invariant summary of each ring; used for fast candidate retrieval.

shift k

cyclic column shift that aligns the query with the candidate; k × (360° / N_s) is the yaw estimate.

fitness

a measure of how well the verified registration aligns the points (for example mean inlier distance).

Strengths, limitations, failure modes

A worked example: a four-sector Scan Context

1. Setup. Use two rings and four sectors. The query descriptor has columns (1,2), (2,3), (3,1), (4,0); that is A = [[1, 2, 3, 4], [2, 3, 1, 0]]. (Row 1 is the inner ring, row 2 the outer.)
2. A revisit at a different heading. Let B be A with its columns cyclically shifted by one sector: B = [[4, 1, 2, 3], [0, 2, 3, 1]]. Comparing A with B directly (shift 0) gives an average column cosine distance of 0.206, which looks like a poor match. Over the four shifts the distances are 0.206, 0.369, 0.206 and 0.000. The minimum, 0, is at shift 3 (shifting B’s columns by three restores A). The scans are identical up to a 90° turn (360° / 4 sectors), and the minimum over shifts finds it.
3. A different place. Let C = [[4, 0, 1, 0], [0, 2, 0, 3]]. The shifted distances to A are 0.443, 0.309, 0.443 and 0.309. The best is 0.309: no shift makes the two agree, so with a threshold of 0.2 the pair is rejected.
4. Cost of the search. With a 20 × 60 descriptor, the full distance over all 60 shifts costs 60 × 60 column comparisons of length 20, about 72 000 multiplications per candidate pair. Against 10 000 stored keyframes that is 7 × 10⁸ operations per query. Ring keys reduce the pool to, say, 10 candidates: 7 × 10⁵ operations.
5. Verification. Suppose the best shift is 14 of 60 sectors: a yaw guess of 14 × 6° = 84°. ICP initialised at 84° converges to a relative pose with mean residual 0.07 m. A look-alike aisle would converge to a poor fit (mean residual 0.4 m), so it is rejected. A threshold of, say, 0.15 m separates them in this scene.

If an aliased loop is accepted nevertheless, the pose graph is pulled together at a wrong place; the map folds on itself. The next lab and M4-L3 ask you to find such failures from the logs.

Engineering implications and limitations

Engineering implications

• Two thresholds, not one. A descriptor distance threshold controls recall; the geometric verification threshold controls precision. Tune both on logged data with known ground truth, and favour precision: one false loop costs more than a missed one.
• Use temporal consistency. Require several consecutive keyframes to agree on the same loop, or add the loop with a robust kernel and switchable constraints.
• Exclude the recent past. Do not search among keyframes just taken; require a minimum time or path-length gap so that the previous scan is not reported as a loop.
• Re-build the map after loops. Keep keyframe scans so that the global map follows the optimised graph.
• Know the alternatives. Learned global descriptors (for example PointNetVLAD, OverlapNet) can be more robust to viewpoint and dynamics, at the cost of training data and a GPU; see Module 8.
• Test on your environment. Warehouses and orchards defeat descriptors that work on city streets.

Limits

Scan Context is a hand-designed descriptor with fixed assumptions: a level sensor, vertical structure, limited translation between visits. It gives candidates, not truth. The quality of the verification step and of the robust back end decide whether the system survives aliasing.

Common misconceptions

Engineering takeaways

1. Odometry matches a bounded local map; older data live as keyframes in the graph.
2. Scan Context turns a scan into a ring-by-sector matrix of maximum heights; a column shift handles rotation.
3. Ring keys give fast retrieval; the shift distance ranks candidates; ICP verifies and refines.
4. Only verified loops should be added, with robust kernels, because false loops damage the whole map.
5. Perceptual aliasing, dynamics and flat scenes are the main failure modes.

References and further reading

Primary papers and authoritative documentation.

• Kim, G. and Kim, A. (2018). Scan Context: Egocentric spatial descriptor for place recognition within 3D point cloud map. IEEE/RSJ IROS.
• Kim, G., Choi, S. and Kim, A. (2022). Scan Context++: Structural place recognition robust to rotation and lateral variations in urban environments. IEEE Transactions on Robotics 38(3).
• Shan, T. and Englot, B. (2018). LeGO-LOAM. IEEE/RSJ IROS: radius-search loop closure with ICP verification.
• Uy, M. A. and Lee, G. H. (2018). PointNetVLAD: Deep point cloud based retrieval for large-scale place recognition. IEEE CVPR.

Knowledge check

Three conceptual questions. Write an answer, then reveal the explanation. Your answers stay in your browser.

What’s next

A corrected trajectory and a point cloud are enough to localise. The last lesson of the module covers the maps built for planning and reconstruction: octrees, signed distance fields and surfels.

Related content

Nothing below is required to finish this lesson.

• Before
  M5-T9: FAST-LIO and FAST-LIO2

  Describe the iterated error-state Kalman filter and the ikd-tree map of FAST-LIO and FAST-LIO2.

• Lab
  M5-L5: Investigate a Failed LiDAR Mapping Run

  Given the logs of a failed run, find the root cause among several candidate failures.