NDT Scan Matching

The normal distributions transform, NDT, turns the reference scan into a grid of little Gaussians, one per cell, describing where points tend to lie in that cell. A new scan is aligned by sliding it to where its points score highest under those Gaussians, with no point-to-point pairing at all.

Cell size Starting rotation error Starting shift

The NDT score

For each cell with enough reference points, compute their mean $\boldsymbol\mu_c$ and covariance $\Sigma_c$. A transformed scan point $\mathbf{p}'$ in cell $c$ scores

$$s(\mathbf{p}') = \exp\!\left(-\tfrac12\,(\mathbf{p}' - \boldsymbol\mu_c)^\top \Sigma_c^{-1} (\mathbf{p}' - \boldsymbol\mu_c)\right)$$

The total score is smooth in the pose, so it can be maximized with gradient-based steps.

What to notice

Each ellipse is long along a wall and thin across it, so points are pulled onto walls but allowed to slide along them. The score improves smoothly as the scan aligns. Bigger cells give a smoother score that converges from farther away but less precisely. Smaller cells are precise but can trap the scan. NDT is popular for 3D LiDAR localization in self-driving, such as in Autoware, because it is fast and needs no nearest-neighbor search.