The iterative closest point (ICP) algorithm is widely used for the registration of geometric data and it applies to a wide field of activities that range from 3D object modeling to object recognition. One of the main drawbacks of the algorithm is its quadratic time complexity O(N^2) with the shape size N, which implies long processing time, especially when using high resolution data. Several methods were proposed to accelerate the process. The most effective ones focus on reducing the closest point computation time like the k-D tree search and the neighbor search algorithms. This paper proposes to further accelerate the process by a coarse to fine multiresolution approach in which a solution at a coarse level is successively improved at a finer level of representation. Specifically, it investigates this multiresolution ICP approach when coupled with the mentioned tree search or the neighbor search closest point algorithms. A theoretical and practical analysis and a comparison of the considered algorithms are presented. Confirming the success of the multiresolution scheme, the results also show that this combination permits to create a very fast ICP algorithm, gaining speed up to a factor 25 over the standard fast ICP algorithm.
