Normal Distributions Transform (NDT)

NDT maps a 3D point cloud into a collection of local normal distributions. The space is discretized into a grid of cells, and for each cell containing points, a mean vector and covariance matrix are computed. This transforms the discrete, noisy scan into a continuous, differentiable probability density function (PDF) that represents the likelihood of finding a surface at any location. The resulting representation is piecewise-smooth, providing a well-defined gradient for optimization.

Unlike Iterative Closest Point (ICP) which relies on explicit point correspondences, NDT formulates scan matching as a nonlinear optimization problem. The goal is to find the rigid-body transformation (rotation and translation) that maximizes the sum of probability densities evaluated at the points of a second scan. The score function's analytical Jacobian and Hessian are derived from the Gaussian parameters, allowing standard Newton or quasi-Newton methods to efficiently converge to the optimal alignment without a costly nearest-neighbor search in each iteration.

The grid cell size is the critical hyperparameter that controls the trade-off between registration accuracy and computational efficiency:

• Large cells capture broader surface structures and increase the convergence basin, making the algorithm robust to large initial misalignments but less precise.
• Small cells model fine geometric details with high fidelity, enabling precise alignment but requiring a better initial guess to avoid local minima. A multi-resolution approach, starting with coarse cells and refining with finer ones, is a common strategy.

A fundamental advantage of NDT is that it eliminates the brittle step of explicit point correspondence. ICP must guess which point in the target scan corresponds to each point in the source scan, a process prone to error in noisy or partially overlapping data. NDT instead evaluates the source points against a continuous spatial distribution, making it inherently more robust to measurement noise, varying point densities, and partial occlusions. This statistical approach naturally handles the uncertainty present in real-world sensor data.

NDT achieves significant speed advantages over classical ICP for large point clouds. The most expensive operation—building the grid of normal distributions—is performed once on the static target scan and is independent of the source scan size. Each optimization iteration then requires only a constant-time lookup and evaluation of the Gaussian parameters for each source point, avoiding the O(N log N) cost of a kd-tree nearest-neighbor search. This makes NDT particularly well-suited for real-time Simultaneous Localization and Mapping (SLAM) applications.

An extension known as Distribution-to-Distribution (D2D) NDT registers two NDT maps directly, rather than a point cloud to an NDT map. This is achieved by minimizing the L2 distance between the Gaussian distributions in corresponding cells. D2D registration is highly efficient for large-scale mapping and loop closure detection because it avoids reprocessing raw point data. The transformation is computed by aligning the statistical summaries of two previously built local maps, enabling consistent global map construction.

NDT is the de facto standard for localizing self-driving cars within pre-built High-Definition (HD) maps. By transforming a live LiDAR scan into a set of Gaussian probability distributions and matching it against a pre-computed NDT map, the vehicle can determine its precise 6-DOF pose.

• Mechanism: The algorithm maximizes the likelihood of finding the current scan points within the reference map's distributions.
• Advantage: Provides a gradient-based optimization surface that is smoother and more continuous than raw point clouds, enabling robust convergence even with poor initial guesses.
• Performance: Achieves centimeter-level accuracy at update rates exceeding 10 Hz on embedded hardware.

NDT is used to identify temporal discrepancies between a live sensor view and a static reference map, a critical function for maintaining fresh autonomous vehicle maps.

• Process: The live scan is registered to the reference NDT map. The per-cell likelihood score is then evaluated; cells with persistently low likelihood indicate a structural change in the environment.
• Application: Detecting new construction, road closures, or shifted lane markings without requiring a full remapping mission.
• Output: A probabilistic change mask that triggers targeted map updates, reducing bandwidth and storage costs.

In metrology and reverse engineering, NDT provides a robust alternative to Iterative Closest Point (ICP) for aligning multiple high-density scans of manufactured parts.

• Why NDT over ICP?: NDT does not require a costly nearest-neighbor search for every point. Instead, it evaluates points against a piecewise-smooth probability density function, making it faster and more robust to sensor noise.
• Use Case: Aligning scans from a structured light scanner to build a complete digital twin of a turbine blade for defect analysis.
• Benefit: Handles large datasets efficiently by abstracting the surface into a compact set of statistical moments.

NDT serves as a powerful objective function for automatically calibrating the rigid-body transform between a LiDAR and an inertial measurement unit (IMU) or camera.

• Methodology: A LiDAR scan is accumulated into an NDT map. The calibration parameters are optimized to maximize the consistency of the LiDAR points within their own map, often fused with visual or inertial constraints.
• Key Metric: Minimizes the negative log-likelihood of the LiDAR points under the NDT representation.
• Result: Fully automated, targetless calibration that eliminates the need for checkerboards or specialized calibration rooms in large outdoor robots.

NDT is employed in graph-based SLAM systems to verify loop closure candidates by performing a fast, rigid registration between a current scan and a historical submap.

• Workflow: A place recognition system proposes a loop closure. NDT registration computes the relative transform and provides a fitness score that quantifies the alignment quality.
• Decision Gate: If the NDT fitness score exceeds a strict threshold, the loop closure constraint is accepted and added to the pose graph for global optimization.
• Advantage: The fitness score provides a more discriminative validation metric than simple nearest-neighbor distance thresholds used in ICP.

NDT can segment and filter moving objects from a static scene during map building by analyzing the statistical consistency of points over time.

• Technique: A time-series of scans is registered to a common frame. For each voxel, the variance of the likelihood of containing a point is computed.
• Classification: Voxels with high temporal variance are classified as dynamic objects (e.g., pedestrians, other vehicles) and removed from the static map.
• Outcome: Generates clean, static-only point cloud maps essential for reliable long-term localization.