next up previous
Next: Background

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 @


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.

root 2007-05-31