Abstract To improve the efficiency of point set registration, an efficient nearest neighbor search approach for 2D/3D point sets is proposed. Firstly, according to the variance of each dimension of the model points, all model points based on the selected dimension information are sorted. By adopting the binary search strategy, each data point is inserted into the sorted model points. Then, the upper bound of search range can be obtained by calculating the distance between the data point and its first left model point. During the search process, the search range can be further reduced by the current nearest neighbor so that the final nearest neighbor can be efficiently searched. Finally, the efficiency of the approach is demonstrated by both the complexity analysis and experimental results comparision.
[1] Barber C B, Dobkin D P, Huhdanpaa H. The Quickhull Algorithm for Convex Hulls. ACM Trans on Mathematical Software, 1996, 22(4): 469-483 [2] Mulchrone K F. Application of Delaunay Triangulation to the Near-est Neighbor Method of Strain Analysis. Journal of Structural Geology, 2003, 25(5): 689-702 [3] Bentley J L. Multidimensional Binary Search Trees Used for Associative Searching. Communications of the ACM, 1975, 18(9): 509-517 [4] Greenspan M, Yurick M. Approximate k-d Tree Search for Efficient ICP // Proc of the 4th International Conference on 3-D Digital Imaging and Modeling. Banff, Canada, 2003: 442-448 [5] Nuchter A, Lingemann K, Hertzberg J. Cached k-d Tree Search for ICP Algorithms // Proc of the 6th International Conference on 3-D Digital Imaging and Modeling. Montreal, Canada, 2007: 419-426 [6] Liu Y, Xiong Y L. Algorithm for Searching Nearest-Neighbor Based on the Bounded k-d Tree. Journal of Huazhong University of Science and Technology: Natural Science Edition, 2008, 36(7): 73-77 (in Chinese) (刘 宇,熊有伦.基于有界k-d树的最近点搜索算法.华中科技大学学报:自然科学版, 2008, 36(7): 73-77) [7] Slaney M, Casey M. Locality-Sensitive Hashing for Finding Nearest Neighbors. IEEE Signal Processing Magazine, 2008, 25(2): 128-131 [8] Hwang Y, Han B, Ahn H K. A Fast Nearest Neighbor Search Algorithm by Nonlinear Embedding // Proc of the IEEE Conference on Computer Vision and Pattern Recognition. Providence, USA, 2012: 3053-3060 [9] Lu X G, Jain A K, Colbry D. Matching 2.5D Face Scans to 3D Models. IEEE Trans on Pattern Analysis and Machine Intelligence, 2006, 28(1): 31-43 [10] Shih S W, Chuang Y T, Yu T Y. An Efficient and Accurate Me-thod for the Relaxation of Multiview Registration Error. IEEE Trans on Image Processing, 2008, 17(6): 968-981 [11] Zhu J H, Zheng N N, Yuan Z J, et al. A SLAM Approach by Combining ICP Algorithm and Particle Filter. Acta Automatica Si-nica, 2009, 35(8): 1107-1113 (in Chinese) (祝继华,郑南宁,袁泽剑,等.基于ICP算法和粒子滤波的未知环境地图创建.自动化学报, 2009, 35(8): 1107-1113) [12] Besl P J, McKay N D. A Method for Registration of 3-D Shapes. IEEE Trans on Pattern Analysis and Machine Intelligence, 1992, 14(2): 239-256 [13] Du S Y, Zheng N N, Ying S H, et al. Affine Iterative Closest Point Algorithm for Point Set Registration. Pattern Recognition Le-tter, 2010, 31(9): 791-799 [14] Ying S H, Peng J G, Du S Y, et al. A Scale Stretch Method Based on ICP for 3D Data Registration. IEEE Trans on Automation Science and Engineering, 2009, 6(3): 559-565 [15] Zhu J H, Zheng N N, Yuan Z J, et al. Robust Scaling Iterative Closest Point Algorithm with Bidirectional Distance Measurement. Electronics Letters, 2010, 46(24): 1604-1605 [16] Ying S H, Peng J G, Zheng K J, et al. Lie Group Method for Data Set Registration Problem with Anisotropic Scale Deformation. Acta Automatica Sinica, 2009, 35(7): 867-874 (in Chinese) (应时辉,彭济根,郑开杰,等.含各向异性尺度形变数据集匹配问题的Lie群方法.自动化学报, 2009, 35(7): 867-874) [17] Nüchter A, Elseberg J, Schneider P, et al. Study of Parameterizations for the Rigid Body Transformations of the Scan Registration Problem. Computer Vision and Image Understanding, 2010, 114(8): 963-980
2014, Vol. 27 
