Background

Registering 3D models is a crucial step in 3D model construction. Many application benefit from efficient ICP algorithms: Nowadays precise 3D scanners are available that are used in architecture, industrial automation, agriculture, cultural heritage conservation, and facility management. These 3D scanners deliver tons of 3D data as point clouds. Other applications of point cloud registration algorithms include medical data processing, art history, archaeology, and rescue and inspection robotics. The advent of 3D cameras is likely to generate another burst of ICP applications in the near future [22,23].

ICP algorithms are widely used for registering geometric 3D models in a common coordinate system. Given two point clouds and a starting guess for the relative poses, the algorithm computes the rotation and translation such that the 3D models fit together. ICP is an iterative algorithm based on searching for closest points. The key of efficient implementation is the fast computation of closest points. This paper presents a novel search method, namely, cached k-d trees, for computing of closest points iteratively. The method is based on k-d trees and a buffer for leaf nodes. The buffer is used to start backtracking in subsequent searches. Therefore, the iterative structure of ICP is exploited for speed-ups. The proposed search algorithm computes exact nearest neighbors as closest point, thus side effects due to approximation cannot occur.

The paper is organized as follows: The next part presents briefly the ICP algorithm, followed by a discussion of related work. The following section describes the data structures used for closest point searches within the ICP algorithm and introduces our novel approach. The obtained results are then evaluated. Section 4 concludes.