Efficient nearest neighbor search approach for registration of low dimensional point sets

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.