Fast ICP algorithms for the registration of 3D data

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 its main drawbacks is its quadratic time complexity O(N2) with the shape size N, which implies heavy computations. Consequently, there is a need to speed up the ICP algorithm and several methods have been proposed. The most effective ones focus on reducing the closest point computation time and complexity like the k-D tree search or projection methods. This paper proposes a review of the existing fast ICP methods and places emphasis on a recently proposed solution that combines the neighbor search algorithm with a multiresolution scheme to create a very fast and robust ICP. Confirming the success of the latter, the results show that it is possible to gain speed up to a factor 1600 over the standard, non-accelerated ICP algorithm, while avoiding the tradeoff with matching quality that is imposed by many existing solutions.