next up previous
Next: Evaluation and Results Up: Cached k-d tree search Previous: The cached k-d tree search

Performance of cached k-d tree search

The proposed ICP variant uses exact closest point search. In contrast to the previously discussed approximate k-d tree search for ICP algorithms [10,17], registration inaccuracies or errors due to approximation cannot occur.

Friedman et al. prove that searching for closest points using k-d trees needs logarithmic time [7], i.e., the amount of backtracking is independent of the number of stored points in the tree. Since the ICP algorithm iterates the closest point search, the performance derives to $ {\cal O}(I N_d \log N_m)$, with $ I$ the number of iterations. Note: Brute-force ICP algorithms have a performance of $ {\cal O}(I N_d N_m)$.

The proposed cached k-d tree search needs $ {\cal O}((I + \log N_m)
N_d)$ time in the best case. This performance is reached if constant time is needed for backtracking, resulting in $ N_d\log N_m$ time for constructing the tree, and $ I \cdot N_d$ for searching in case no backtracking is necessary. Obviously the backtracking time depends on the computed ICP transformation ( $ \mathbf{R}, \mathbf{t}$). For small transformations the time is nearly constant.

Cached k-d tree search needs $ {\cal O}(N_d)$ extra memory for the vector $ \mathbf{v}$, i.e., for storing the pointers to the tree leaves. Furthermore, additional $ {\cal O}(N_m)$ memory is needed for storing the backwards pointers in the k-d tree.


next up previous
Next: Evaluation and Results Up: Cached k-d tree search Previous: The cached k-d tree search
root 2007-05-31