Conclusion

In this paper we present a simple search method that improves k-d tree search for ICP algorithms for point clouds. The algorithm exploits the iterative fashion of the ICP by caching pointers to tree buckets containing the closest points. Since the transformations in each step become smaller from iteration to iteration, the number of tree operations is drastically reduced. The resulting ICP variant is usually about 50% faster than the conventional k-d tree ICP algorithm.

Needless to say, a lot of work remains to be done. In future work we plan to develop an algorithm suite that contain implementations of Elias' algorithm [19], search methods that include the exploitation of the triangle equation [9] and other caching methods, e.g. [21]. Such a framework is necessary to allow an unbiased evaluation.

Furthermore, we are currently working on global registration methods for several 3D point clouds. Here, the ICP error function is replaced by a global error function, that moves all scans in the minimization step. New search methods are needed, since after applying the transformation, the (cached or approximate) k-d trees have to be time-consumingly altered or reconstructed.