Scan registration with multi-scale k-means normal distributions transform

The normal distributions transform (NDT) scan registration algorithm has been shown to produce good results, however, has a tendency to converge to a local minimum if the initial parameter error is large. In order to improve the convergence basin for NDT, a multi-scale k-means NDT (MSKM-NDT) variant is proposed. This approach divides the point cloud using k-means clustering and performs the optimization step at multiple scales of cluster sizes. The k-means clustering approach guarantees that the optimization will converge, as it resolves the issue of discontinuities in the cost function found in the standard NDT algorithm. The optimization step of the NDT algorithm is performed over a decreasing scale, which greatly improves the basin of convergence. Experiments show that this approach can be used to register partially overlapping scans with large initial transformation error.