The ICP algorithms spends most of its time in creating the point pairs. D-trees (here ) 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 at average.
Recently, Greenspan and Yurick have introduced approximate d-trees (Apr-d-tree)[4]. The idea behind this is to return as an approximate nearest neighbor the closest point in the bucket region where the given point 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-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.
point pairing method | time | # ICP iterations |
brute force search | 4 h 25 min | 87 |
D-tree | 14.2 sec | 87 |
Apx-D-tree | 10.9 sec | 85 |