Email this article 
Open Access
Subscription or Fee Access
Effectiveness of Kd- Tree in Ray Tracing of Dynamic Point Clouds
Abstract
A kd-tree is basically defined as a data structure which is mainly used for accumulating a fixed set of points in a k-dimensional space. Kd-tree is predominantly a binary tree. Kd-tree is attracting an increasing interest in recent decades for ray tracing due to its advantages in generating detailed images based on natural physical behaviors, flexibility, and ease of coding. Both point-based representations and ray tracing provide means to efficiently show very complicated 3D models. Computational effectiveness has been the main focus of past work on ray tracing point-sampled surfaces. Kd-tree solves the complication in searching nearest neighbors of a given point in k dimensional space. Kd-trees are also used in pattern recognition and machine learning. Nearest neighbor search algorithm on kd-trees can be slightly improved to allow incremental nearest neighbor search. Kd-tree was invented by john Louis Bentley and it is an abstraction of a binary search tree. It is mainly used in a large amount of graphics applications, inclusive of nearest neighbor search in point cloud (Set of data point) modeling. Kd-tree is also used for accumulating a group of points in the Cartesian co-ordinate plane means in 3-D space. Kd-tree establishment can also be cast-off for dynamic point clouds for accelerating the nearest neighbor queries. Kd-trees are mainly used for Nearest neighbor searching, Query processing in sensor network, Database searching using multiple keys, Fingerprint matching and Optimization ray tracing.
Keywords
References
Jon Louis Bentley, “Multidimensional Binary Search Trees Used for Associative Searching,” Communications of the ACM, Vol. 18, No. 9, pp. 509-517, September 1975.
Jan Elseberg, Stehane Magnenat, Roland Siegwart, and Andreas Nuchter. “Comparison of nearest-neighbor-search strategies and implementations for efficient shape registration.” Journal of SoftwareEngineering for Robotics (JOSER), pp. 1-12, 2012.
D. T. Lee and C. K. Wong, “Worst-case analysis for region and partial region searches in multidimensional binary search trees and balanced quad trees," Acta Informatica, Vol. 9, No. 1, pp. 23–29, 1977.
David G. Lowe, “Object Recognition from Local Scale-Invariant Features,” Proc. of the International Conference on Computer Vision, pp. 1150-1157, 1999.
Herbert Bay, Andreas Ess, Tinne Tuytelaars, and Luc Van Gool, “Speeded-Up Robust Features (SUFT),” Computer Vision and Image Understanding, Vol. 110, Issue. 3, pp. 346-359, 2008.
C. Silpa-Anan and R. Hartley, “Optimised KD-trees for fast image descriptor matching,” Computer Vision and Pattern Recognition(CVPR), 2008, pp. 1-8, 2008.
K. Fukunaga and P. M. Narendra, “A branch and bound algorithm for computing k-nearest neighbors,” IEEE Trans. Comput., 24:750–753. 1975.
Piotr Indyk and Rajeev Motwani, “Approximate Nearest Neighbors: Towards Removing the Curse of Dimensionality,” In Proceedings ofthe 30th Annual ACM Symposium on Theory of Computing, pp. 604– 613, 1998.
Marius Muja and David G. Lowe, "Fast Approximate Nearest Neighbors with Automatic Algorithm Configuration", InternationalConference on Computer Vision Theory and Applications (VISAPP'09), 2009.
W.-S. Choi, Y.-S. Kim, S.-Y. Oh, and J. Lee, “Fast Iterative Closest Point framework for 3D LIDAR data in Intelligent Vehicle,” in Intelligent Vehicles Symposium (IV), 2012 IEEE, 2012, pp. 1029-1034.
Nuchter, A., Lingemann, K., Hertzberg, J. “Cached k-d tree search for ICP algorithms,” In Proceedings of Sixth International Conference on3-D Imaging and Modeling (3DIM), pp. 419–426 (2007).
D. Simon, M. Hebert, and T. Kanade,”Real–time 3–D pose estimation using a high–speed range sensor,” In Proceedings of IEEEInternational Conference on Robotics and Automation (ICRA ’94), volume 3, pages 2235 – 2241, San Diego, CA, USA, May 1994.
J. H. Friedman, J. L. Bentley, and R. A. Finkel, “An Algorithm for Finding Best Matches in Logarithmic Expected Time,” ACM Trans.Math. Softw., vol. 3, pp. 209-226, 1977.
S. Maneewongvatana and D. M. Mount, “It's Okay to Be Skinny, If Your Friends Are Fat,” Center for Geometric Computing 4th AnnualWorkshop on Computational Geometry, 1999.
A. Nuchter, K. Lingemann, J. Hertzberg, H. Surmann, “6D SLAM with approximate data association,” in Advanced Robotics, 2005. ICAR '05.Proceedings., 12th International Conference on, pp.242-249, 2005.
Michael Greenspan, Mike Yurick, “Approximate K-D Tree Search for Efficient ICP,” Proceedings of the Fourth International Conference on3-D Digital Imaging and Modeling, 2003.
S. Arya and D. M. Mount, “Approximate nearest neighbor queries in fixed dimensions,” In Proceedings of the 4th ACMSIAM Symposium onDiscrete Algorithms, pp. 271 – 280, 1993.
A. Bosch, A. Zisserman, and X. Munoz, “Image classification using random forests and ferns,” in Proc. ICCV, 2007.
X. Qingsong, S. Juan, and L. Tiantian, “A detection and recognition method for prohibition traffic signs,” in Image Analysis and SignalProcessing (IASP), 2010 International Conference on. IEEE, 2010, pp. 583–586.
I. Creusen, R. Wijnhoven, E. Herbschleb, and P. de With, “Color exploitation in hog-based traffic sign detection,” in Image Processing(ICIP), 2010 17th IEEE International Conference on, 2010, pp. 2669 –2672.
KDTree Assignment 2 CS106L Fall 2013 Handout #03 November 21, 2013
Refbacks
- There are currently no refbacks.
This work is licensed under a Creative Commons Attribution 3.0 License.