next up previous
Next: d-trees Up: Range Image Registration and Previous: Diffusing the Error.

Computing point correspondences

The time complexity of the algorithm described above is dominated by the time for determining the closest points (brute force search $ {\cal O}(n^2)$ for 3D scans of $ n$ points). Several enhancements have been proposed [6,7,24]. We have implemented $ k$d-trees as proposed by Simon et al. Fig. [*] shows two slices taken from a $ k$d-tree.

Figure: A $ k$d-tree of scanned 3D data ($ k=3$) of Fig. [*] (top) first/black 3D scan. Two $ (x,y)$-projections of slices at depths $ z=100$ cm (a) and $ z=550$ cm (b) are given.
(a) \includegraphics[width=75mm,height=30mm]{tree_kd_100} (b) \includegraphics[width=75mm,height=30mm]{tree_kd_550}


root 2005-05-03