Fast ICP algorithms for shape registration

Shape registration plays an important role in applications such as 3D object modeling or object recognition. The iterative closest point (ICP) algorithm is widely used for the registration of geometric data. One of its main drawback is its time complexity O(N²), quadratic with the shape size N, which implies long processing time, especially when using high resolution data. Several methods were proposed to accelerate the process. One of the most effective one uses a tree search (k-D tree) to establish closest point relationships and reduces the complexity to O(N logN). This paper reviews several of the existing methods and proposes and analyses a new, even less complex ICP algorithm, that uses a heuristic approach to find the closest points. Based on a local search it permits to reduce the complexity to O(N) and to greatly accelerate the process. A comprehensive analysis and a comparison of the considered algorithm with a tree search method are presented.