大规模散乱点的k邻域快速搜索算法

针对大规模散乱点数据k最近邻域搜索速度慢和稳定性差的问题,提出一种新的k邻域快速搜索算法.首先,引入空间分块策略将数据集中的点归入不同的子空间;其次,动态控制搜索步长的改变量,根据点到其自身小立方体边界的最小距离保证搜索结果的准确性;最后,通过改变预筛选点数量的右侧控制阈值来消除已有算法中由于初始数值不当引起的死循环.实验结果表明该算法对初始搜索步长、搜索步长增量、采样密度和不同的拓扑结构具有较强的稳定性,并且能更快地完成k邻域搜索.

Fast algorithm for finding the k-nearest neighbors of a large-scale scattered point cloud

To solve the problem of low efficiency and weak stability in searching the k-nearest neighbors of a large-scale scattered point cloud, a fast algorithm for finding k-nearest neighbors is presented. First, the point cloud data is divided into different sub-spaces by using a space block strategy. Second, the variation of the search step length is controlled dynamically. The accuracy of the algorithm is ensured by the minimum distance from the point to the small cube boundary. Finally, the infinite loop problem due to improper initial values in existing algorithms is avoided by altering the right-side threshold, which controls the number of pre-screening points. The experiment results show that the proposed method obtains not only a good stability for the initial searching step, the step increment, and the sampling density at different topology structures, but also a better performance than the existing algorithms.