M3-T4 — Scan Matching

Learning objectives

After this lesson, you should be able to:

• State the scan-matching problem and its objective function.
• Distinguish scan-to-scan from scan-to-map matching and say when each is used.
• Compare point-to-point, point-to-line, NDT and correlative methods by cost and robustness.
• Diagnose failures: poor initial guess, geometric degeneracy, dynamic objects, partial overlap.

The problem and the intuition

Take two photographs of a room from slightly different positions and lay them on a light table. Slide and turn one until the furniture lines up. The amount you slid and turned is how far the camera moved. Scan matching does this with laser scans: it searches for the rigid motion that makes the second scan’s points fall on the first scan’s surfaces.

Notice the two things that can go wrong. If you start with the photographs very far out of alignment, you may line up the wrong pieces of furniture. And if the room is a long, bare corridor, you can slide the picture along it forever and it still “fits”.

Scan matching is a local search. It finds the nearest good alignment, not the best one in the world, and some scenes have no unique alignment at all.

The algorithm: choose a transform to minimise misfit

Problem. Given a reference scan (or a map) and a new scan, find the rigid transform T = (Δx, Δy, Δθ) that best aligns the new points to the reference.

Assumptions. The environment is static between scans; the two scans overlap substantially; a reasonable initial guess for T is available (usually from odometry); the scene has enough geometric structure to constrain all three degrees of freedom.

p_i

the points of the new scan, in the sensor frame.

T p_i

the point after transformation into the reference frame.

dist(·, reference)

a measure of how far a point is from the reference surface; it differs between methods.

ρ

a loss function; squared error is standard, robust losses (Huber, Cauchy) reduce the weight of outliers.

Families of methods

Scan-to-scan versus scan-to-map

Scan-to-scan matches the new scan with the previous one: cheap and good for odometry, but each step adds a little error that accumulates (it is a kind of visual odometry for lasers). Scan-to-map matches against the map built so far (or a local submap): errors do not accumulate in the same way because the map holds the average of many scans, at the price of one more thing that must be right.

Failure modes

• Poor initial guess. The search converges to the nearest local minimum, and a rotation of more than about 15–30° or a large translation easily lands in the wrong one.
• Geometric degeneracy. In a long straight corridor every position along the corridor gives the same scan: the objective is flat in that direction, so the matcher returns whatever the initial guess said. The curvature (Hessian) of the objective has a zero eigenvalue.
• Dynamic objects. People and vehicles produce points that have no counterpart: outliers that pull the alignment unless they are rejected.
• Partial overlap. After a turn or a door, only part of the new scan has a counterpart in the old; nearest-neighbour matching pairs the rest with wrong points.
• Sparse or noisy data. Few points or rain, dust and glass distort the structure the matcher relies on.

A worked example: why a corridor cannot be matched along its length

A robot moves in a corridor with two parallel walls at y = +1 and y = −1. Its scan contains points on both walls, with normals (0, −1) and (0, +1). With point-to-line matching, the objective is a sum of squared perpendicular distances, which depend on a candidate motion (Δx, Δy, Δθ) only through the normal components.

1. Each point contributes a Jacobian row [nₓ, n_y, nₓ(−p_y) + n_y p_x] = [0, ±1, ±p_x] for a wall point (p_x, ±1) with normal (0, ∓1). The first entry (sensitivity to Δx) is zero for every point.
2. The information matrix JᵀJ therefore has a zero first row and column. Its eigenvalues are (0, λ₂, λ₃): the Δx direction has zero curvature. Any Δx gives the same objective value.
3. What the matcher does. It cannot correct Δx. The result simply keeps the initial guess for that component, so the odometry’s error along the corridor passes straight through.
4. A single door or pillar breaks the symmetry: points on a feature with a normal along x give non-zero entries in the first column, and Δx becomes observable. One feature is enough to restore all three degrees of freedom, provided it is in view.
5. Detect it. Compute the eigenvalues of JᵀJ (or count the normals by direction) and warn when the smallest is near zero, then increase the weight of odometry or another sensor along that axis.

The lab asks you to see this directly: an ICP that works well in a room slides along a corridor.

Engineering implications and limitations

Engineering implications

• Use odometry as the initial guess and gate the result: if the match moves far from the guess, check the quality score before accepting it.
• Prefer point-to-line or NDT in structured environments and correlative matching for large search windows (loop closure, relocalisation).
• Reject outliers: trimmed matching (keep the best 80% of correspondences), distance thresholds and robust losses (Huber, Cauchy).
• Report a quality score and a covariance with every match (fraction of inliers, eigenvalues of the information matrix). The back end needs them to weight the constraint, and a degenerate match with a confident covariance is a cause of divergence.
• Use a local submap or sliding window rather than a single previous scan: more points, less noise, and fewer accumulated errors.

Limits

Scan matching measures relative motion, so its errors accumulate along a path just as odometry’s do, only more slowly. It cannot recognise a place it has seen before; that needs a global method (Module 4). It also assumes a rigid, static scene: in crowds, the match drifts toward the people it is trying to ignore.

Common misconceptions

Engineering takeaways

1. Scan matching finds the rigid transform that minimises a misfit between a new scan and a reference scan or map.
2. Methods differ in the distance they use (point, line, probability) and in how large a convergence basin they have.
3. The result is a local optimum: a good initial guess (odometry) matters.
4. Degenerate geometry (corridors) leaves a direction unconstrained; detect it from the eigenvalues of the information matrix.
5. Always reject outliers and report a quality measure with the match.

References and further reading

Established fundamentals. Learned and global registration methods are covered in Module 8.

• Besl, P. J. and McKay, N. D. (1992). A method for registration of 3-D shapes. IEEE Transactions on Pattern Analysis and Machine Intelligence 14(2).
• Biber, P. and Straßer, W. (2003). The normal distributions transform: a new approach to laser scan matching. IEEE/RSJ IROS.
• Olson, E. (2009). Real-time correlative scan matching. IEEE International Conference on Robotics and Automation.
• Zhang, J., Kaess, M. and Singh, S. (2016). On degeneracy of optimization-based state estimation problems. IEEE International Conference on Robotics and Automation.
• Pomerleau, F., Colas, F. and Siegwart, R. (2015). A review of point cloud registration algorithms for mobile robotics. Foundations and Trends in Robotics 4(1).

Knowledge check

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

What’s next

The next lesson derives the most widely used scan-matching algorithm, ICP, including its closed-form step and its convergence behaviour.

Related content

Nothing below is required to finish this lesson.

• Before
  M3-T3: Feature-Based Mapping

  Extract lines and corners from scans as features, and compare feature, grid and landmark maps.

• Lab
  M3-L3: Diagnose Scan-Matching Failure

  ICP converges to the wrong alignment: diagnose initial guess, outliers and geometry degeneracy and repair them.