next up previous
Next: Conclusion Up: 6D SLAM with Approximate Previous: Approximate box decomposition trees


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
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

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.
\includegraphics[width=80mm]{tree_kd_bd_1}        \includegraphics[width=80mm]{tree_kd_bd_5}

\includegraphics[width=80mm]{tree_kd_bd_10}        \includegraphics[width=80mm]{tree_kd_bd_50}

next up previous
Next: Conclusion Up: 6D SLAM with Approximate Previous: Approximate box decomposition trees
root 2005-05-03