杨 军,林岩龙,王小鹏,张瑞峰

(兰州交通大学电子与信息工程学院,兰州730070)

基于自适应空间球的k最近邻域快速搜索算法

杨 军,林岩龙,王小鹏,张瑞峰

(兰州交通大学电子与信息工程学院,兰州730070)

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

k最近邻域;曲面重建;点变化云;空间球;分块策略;候选点

1 概述

三维散乱点数据的重建是逆向工程、虚拟现实、医学图像处理等领域的重要研究内容。随着三维激光扫描技术的发展,基于散乱点(也称点云)的曲面重建技术成为国内外学者研究的热点。k邻域的搜索效率直接影响模型的重建速度以及曲面光滑等后续处理,对其搜索算法进行研究具有重要的理论和实际价值。

k邻域搜索的传统方法是计算任一点到其余各点的欧氏距离,然后升序排序,前面的k个点即为此点的k邻域点。这种方法简单直观,易于实现,但其时间复杂度较高,在点云规模较小时,此算法能取得较好的结果。……