Cached k-d tree search for ICP algorithms

Andreas Nüchter, Kai Lingemann, and Joachim Hertzberg
University of Osnabrück, Institute of Computer Science
Knowledge-Based Systems Research Group
Albrechtstraße 28, D-49069 Osnabrück, Germany
nuechter @ informatik.uni-osnabrueck.de

Abstract:

The ICP (Iterative Closest Point) algorithm is the de facto standard for geometric alignment of three-dimensional models when an initial relative pose estimate is available. The basis of ICP is the search for closest points. Since the development of ICP, k-d trees have been used to accelerate the search. This paper presents a novel search procedure, namely cached k-d trees, exploiting iterative behavior of the ICP algorithm. It results in a significant speed-up of about 50% as we show in an evaluation using different data sets.