Abstract: To solve the problem of low efficiency and weak stability in searching k-nearest neighbor of large-scale scattered point cloud by using sphere space,a fast algorithm for finding k-nearest neighbor is presented. Point cloud data is divided into different sub-space by using partition strategy without considering k. The radius of the initial dynamic sphere is determined adaptively based on the approximate density of sampling points in a sub-space. The k-nearest candidate points are searched by the circumscribed cube of a dynamic sphere. When the number of k-nearest candidate points does not meet the requirement,or the search fails,the expanding extent is ensured by a circumsphere of the circumscribed cube. Experimental results show that the proposed method obtains not only a better performance and automation than the existing algorithms,but also a quite stability for the anticipated point number of the sub-space and sampling density.

Key words: k-nearest neighbor, surface reconstruction, point cloud, spatial sphere, partition strategy, candidate point

摘要： 利用空间球搜索大规模点云数据k 邻域存在速率慢和稳定性差的问题,为此,提出一种新的k 邻域快速搜索算法。利用与k 无关的分块策略对点云进行分块,使用候选点所在子块内采样点的近似密度自适应确定候选点的初始动态球半径,应用动态球的外切立方体搜索k 邻域候选点。当候选点数目不满足要求或搜索不成功时,采用候选点动态球外切立方体的外接球扩大搜索范围。实验结果表明,与已有算法相比,该算法的k 邻域搜索效率明显提高,而且当子块内预设点数变化、采样密度提高时具有较强稳定性,自动化程度较高。

关键词: k 最近邻域, 曲面重建, 点变化云, 空间球, 分块策略, 候选点

CLC Number: 

• TP391． 4