Scan Matching
- Also called: scan registration, point cloud registration
- Category: State estimation & navigation › Localisation
- Tags: lidar, localization, slam, point-clouds, registration
Estimating the rigid transform that aligns a range scan with another scan or a map; used in lidar odometry, localization and SLAM to turn raw range data into pose estimates.
Definition
Scan matching takes a new range scan from a lidar, sonar or depth sensor and finds the rotation and translation that best align it with a reference: the previous scan, a recent local map or a global map. The resulting transform is a measurement of how the sensor moved or where it is. It is the core operation behind lidar odometry, map-based localization of wheeled robots and the front ends of most lidar SLAM systems. Scan-to-scan matching is simple but accumulates drift quickly; scan-to-map matching aligns each new scan with an accumulated map, which reduces drift and makes the estimate less sensitive to sparse individual scans.
There are several families of methods. Point-based methods such as iterative closest point (ICP) and its point-to-plane and generalized variants alternate between finding correspondences and solving for the transform. The normal distributions transform (NDT), introduced by Biber and Straßer (2003), represents the reference as a grid of local Gaussian distributions and maximizes the likelihood of the new scan under them. Correlative scan matching, described by Olson (2009), searches over a discretized set of poses against a probability grid, which tolerates poor initial guesses. Feature-based methods, popularized by LOAM (Zhang and Singh, 2014), extract edge and planar points and match them to lines and planes in the map, reducing computation. Grid-based 2D matchers are also at the heart of laser SLAM packages such as Hector SLAM and Cartographer.
Most scan matchers converge only locally and need a reasonable initial guess, usually from the IMU, wheel odometry or a constant-velocity model. They fail in predictable situations: long corridors, tunnels and open fields where the geometry constrains some directions poorly; moving objects that look like structure; and motion distortion when the sensor moves during a single sweep, which must be corrected by de-skewing points with IMU data. Good systems inspect the Hessian or covariance of each match to detect weakly constrained directions and weight the result accordingly when fusing it with other sensors.
Why it matters
Range sensors give accurate geometry but no direct pose. Scan matching is how that geometry becomes motion and position estimates, so its accuracy and failure modes largely set the performance of lidar-based navigation.
Key applications
- Lidar odometry and SLAM
- Localization of warehouse and service robots against a prior map
- Verifying loop-closure candidates between distant scans
- Aligning scans for 3D mapping and surveying
- Extrinsic calibration between multiple lidars
In practice
On a ground robot with a spinning 3D lidar, each sweep is first de-skewed using the rotation measured by the IMU, then edge and planar feature points are extracted. Starting from the IMU-predicted pose, the current keyframe's features are matched against a feature map built from past keyframes, and the solved transform enters the estimator as a lidar odometry factor, as in lidar-visual-inertial systems such as LVI-SAM. In a long, featureless corridor the match constrains motion along the corridor axis only weakly, so the team checks the eigenvalues of the matching Hessian and lets IMU and visual measurements carry that direction until the geometry improves.
Common misconceptions
- Scan matching and ICP are the same thing — ICP is one scan-matching algorithm among several, alongside NDT, correlative and feature-based methods
- A good scan matcher works without an initial guess — most methods converge only locally and need a prior pose from odometry or an IMU
- Scan matching constrains all directions equally — in corridors, tunnels and open areas the geometry can leave some directions almost unconstrained
Who should know this
- Lidar SLAM and localization engineers
- Mobile robot navigation developers
- Autonomous vehicle perception teams
- Surveying and mapping engineers
Related technologies
- Normal Distributions Transform (NDT)
- Generalized ICP
- LOAM
- Cartographer
- Point Cloud Library (PCL)
- KISS-ICP
Related terms
Related projects
- LingBot-Map: Streaming 3D reconstruction from one camera: pose and depth for every frame, live
- oomwoo: Open-source DIY robot vacuum: 3D-printed, ROS2 + 2D LiDAR, fully local.
- PCL: Industry-standard C++ library for point cloud processing in robotics perception
- Cartographer: Google's real-time 2D and 3D SLAM system for multi-platform robotics
- Nav2: ROS 2 navigation stack with path planning and obstacle avoidance for mobile robots
- FAST-LIVO2: Fast, direct LiDAR-inertial-visual odometry from HKU-MARS, published in IEEE T-RO
Videos
- SLAM Course - 12 - Scan-Matching in 5 Min - Cyrill Stachniss: Cyrill Stachniss