Results

This section focuses on three aspects. Firstly, we evaluate the quality of scan matching with approximate nearest neigbour search. Secondly, we investigate the performance of approximate $k$d-trees and approximate bd-trees. Finally, we reproduce results from a robot run given in [27] to demonstrate the general performance of the approach.

To evaluate the quality of the scan matching we restrict the problem to three degrees of freedom. We acquired two 3D scans and measured the pose shift by a reference system, i.e., a meter rule. Fig. (bottom) shows the starting poses from which a correct scan matching is possible. Fig. indicates the initial positions that result in a correct scan matching for different values of $\epsilon$ and the bucket size $b$. Comparing the figures, we conclude that the approximation does not significantly influence the scan matching, due to the large numer of used points and to the iterative nature of the algorithm.

The performance of the proposed tree search is given in Fig. and . In case of no approximation (Fig. ) the $k$d-tree outperforms the bd-tree. The optimal time is reached with 10 points per bucket. In case of approximation, only in a few cases, i.e., 18 out of 124 experiments, the bd-tree is faster than the $k$d-tree. Nevertheless, one notices that with increasing $\epsilon$ the computation time for the scan matching is reduced drastically (up to a factor of 2).

The proposed algorithms have been applied to a data set acquired on the Fraunhofer Campus Birlinghoven campus. 32 3D scans, each containing 302820 (721 $\times$ 420) range data points, were taken by the mobile robot Kurt3D. The robot had to cope with a height difference between the two buildings of 1.05 meter, covered, in the first case, by a sloped driveway in open outdoor terrain, and, in the second case, by a ramp of 12$^\circ$ inside the building. The 3D model was computed after acquiring all 3D scans. Table summarizes the computation time of our 6D SLAM algorithms. Refer to the website http://www.ais.fraunhofer.de/ARC/3D/6D/
for a computed animation and video through the scanned 3D scene. Furthermore, the algorithms have been evaluated at the RoboCup Rescue 2004 competition in Lisbon and precise, reliable, on time 3D maps have been generated (see http://www.ais.fhg.de/ARC/kurt3D/rr.html).

Table: Computing time and number of ICP iterations to align all 32 3D scans (Pentium-IV-2400). In addition the computing time for the SLAM algorithm (closed loop detection and simultaneous matching) is given. About 1 min per 3D scan is needed to do error diffusion in 6D [27].

points & search method	time	iter.
all pts. & brute force	144 h 5 min	2080
all pts. & $k$D-tree	12 min 23 s	2080
all pts. & Apx-$k$D-tree	10 min 1 s	2080
red. pts. & Apx-$k$D-tree	1 min 32 s	2176
6D SLAM with
reduced pts. & Apx-$k$D-tree	38 min	16000

Figure: Computing time in milliseconds for a 3D scan matching depending on the bucket size of approximate $k$d- and approximate bd-tree. Values for $\eps = 1, 5, 10, 50$ are given. In the majority of cases, the approximate $k$d-tree outperforms the approximate bd-tree.