为提高点集配准效率，设计一种适用于二维/三维点集的高效最近邻搜索法。该方法根据由模型点集的各维方差所选定的维度信息，排序模型点集中的点。借助二分查找法，将数据点集中的每个点插入至排序后的模型点集中，并利用左边第一个点确定搜索范围的上确界。当在确定范围内搜索最近邻时，可根据当前结果进一步减小待搜索范围，以便快速获得各点的最近邻。最后进行的复杂度分析和实验结果对比均验证文中方法的有效性。%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.
展开▼
