Abstract
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(N2) with the number of points N. Consequently, several methods have been proposed to accelerate the process. This paper presents 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 in this paper. 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.