A multi-resolution ICP with heuristic closest point search for fast and robust 3D registration of range images

The iterative closest point (ICP) algorithm is widely used for the registration of 3D geometric data. One of the main drawbacks of the algorithm is its quadratic time complexity O(N/sup 2/) with the number of points N. Consequently, several methods have been proposed to accelerate the process. We present a new solution for the speeding up of the ICP algorithm and special care is taken to avoid any tradeoff with the quality of the registration. The proposed solution combines a coarse to fine multiresolution approach with the neighbor search algorithm. The multiresolution approach permits to successively improve the registration using finer levels of representation and the neighbor search algorithm speeds up the closest point search by using a heuristic approach. Both multiresolution scheme and neighbor search algorithm main features are presented. Confirming the success of the proposed solution, typical results show that this combination permits to create a very fast ICP algorithm, with a closest point search complexity of O(N), while preserving the matching quality.