next up previous
Next: Matching Multiple 3D Reliefs Up: Automatic 3D Scan Matching Previous: Matching as an Optimization

Time Complexity Reduction

The ICP algorithms spends most of its time in creating the point pairs. $k$D-trees (here $k=3$) have been suggested for speed up the data access[1]. They are a binary tree with terminal buckets. The data is stored in the buckets, the keys are selected, such that a data space is divided into two equal parts. This ensures that a data point can be selected in $O(\log
n)$ at average.

Recently, Greenspan and Yurick have introduced approximate $k$d-trees (Apr-$k$d-tree)[4]. The idea behind this is to return as an approximate nearest neighbor $\V p_a$ the closest point $\V p_b$ in the bucket region where the given point $\V p$ lies. This value is determined from the depth-first search, thus expensive Ball-Within-Bounds tests and backtracking are not necessary[4]. In addition to these ideas we avoid the linear search within the bucket. During the computation of the Apr-$k$d-tree the mean values of the points within a bucket are computed and stored. Then the mean value of the bucket is used as the approximate nearest neighbor, replacing the linear search. Table 1 summarizes the results.



Table 1. Computing time and number of ICP iterations to align two 3D reliefs (Pentium-IV-2400).
point pairing method time # ICP iterations
brute force search 4 h 25 min 87
$k$D-tree 14.2 sec 87
Apx-$k$D-tree 10.9 sec 85



next up previous
Next: Matching Multiple 3D Reliefs Up: Automatic 3D Scan Matching Previous: Matching as an Optimization
root 2004-03-04