一种改进的立体栅格K邻域搜索算法

摘 要：文章针对利用规则栅格进行K邻域搜索容易遗漏点云局部特征点以及自动化程度不高的问题，对K邻域搜索算法进行了改进。该算法是在规则立体栅格的基础上融入八叉树思想，根据点云阈值查找点云特征栅格，对特征栅格按此栅格点云数与阈值的关系自动计算棱长并进行精划分，并采用自适应空间动态球算法扩展并搜索采样点的K邻域点集。实验表明，与其他算法相比，该算法不仅具有较高的自动化能力和较强的稳定性，还能快速、准确搜索采样点的K邻域。

关键词：立体栅格；八叉树；动态空间球；K邻域

中图分类号：TP301.6 文献标志码：A 文章编号：2095-2945（2017）29-0005-02

引言

邻域是散乱点云中各点与其相邻点间建立的拓扑关系，能有效的提高点云数据处理的速度和效率[1]。点云的数据处理和曲面重构都受点云邻域的搜索效率的影响[2]。K邻域能同时处理均匀分布和非均匀分布的点云，且搜索速度快[1]。

本文的K邻域搜索算法是在规则立体栅格法中融入八叉树思想，使获得的小立体栅格中包含数目适中的采样点；再以改进的自适应空间动态球算法实现对完成了空间划分点云数据的K邻域搜索，增强搜索的自动化程度和稳定性，并提高搜索的速度。

1 点云空间划分

空间划分是将点云模型的空间包围区域按一定的边长进行规则划分，从而获得多个完全相同的小立体栅格，完成K邻域搜索的第一步。点云空间划分分为点云初划分和点云精划分。由此获得的每个小立体栅格中都具有类似的曲面空间信息。

1.1 点云初划分

点云模型的初划分是将点云模型的空间包围盒按照合适的边长划分成m×n×l个小立体栅格[3][4]，并完成对每个栅格中点云的标号，同时对每个栅格进行扫描并记录栅格中是否含有点云，并对无点云栅格进行标记为已访问，其效果如图1所示。

1.2 点云精划分

针对复杂的点云模型，若只采用规则立体栅格划分所得的小立体栅格，因其点云分布不均，使得所获栅格内所含有的空间曲面信息具有非常大的差异，假如此时便进行K邻域搜索，那么将极易漏掉模型的某些关键特征点，使得K邻域的搜索结果不正确。在初划分后，利用点云阈值查找出具有特征信息的特征栅格，并对此类栅格根据点云密度与再划分栅格边长成反比的关系进行精划分[4]，并对所有小栅格进行标号。此时每个小栅格内的点云数量相对均匀。

2 动态球K邻域搜索

搜索算法采用了改进的自适应动态空间球算法完成。根据采样点的近似密度自动算出其动态球的初始半径r，接着使用动态球的外切立方体向外扩展且搜索K邻域点集[2]，动态球扩展方式如图2所示。

（1）根据采样点P的局部近似密度、所处子空间内采样点数目、子空间体积以及k值确定动态半径。

（2）以步骤2为依据建立的动态球Pi的外切立方体内的

点为K邻域候选点。

（3）设置点云阈值k，若K邻域候选点小于阈值，则持续更新动态球，计算其外切立方体，寻找邻域候选点并搜索。

当动态球的外切立方体中点云数达到阈值k时，只需再扩展一次便可确保完成K邻域搜索。本算法提高了算法的效率并减少了动态球的扩展次数。

3 实验分析

本文根据上述理论设计K邻域算法（如图3所示）并编写程序，且以模型cat（n=10000）和bunny（n=31607）（如图4所示）作为实验对象，并在本人电脑上按以上算法完成对点云的K邻域搜索，所得时间为完成点云模型内每点K邻域搜索的平均时间。

对于本文的算法，主要的影响参数是由空间划分中的调节因子α决定的空间球搜索时子块内点云的数目Ns，调控因子α由点云密度ρ决定，本文取调控因子α的值为0.20、0.26、0.30，K取值为10、20、30、50、100分别对以上模型进行K邻域搜索，结果如表1所示。

由表1可知是本文算法对cat和bunny点云模型平均每点K邻域的搜索时间結果，根据公式σ=■计算搜索时间标准差进行分析可知本算法对α具有较好的稳定性；对于相同模型在相同α的情况下，搜索时间随着K值的增大而增大，但增幅很小；对于不同模型在相同α和K值时，搜索时间随模型的复杂度和点云数的增大而增大，但其变化处于相对稳定状况。该算法分别与经典算法（八叉树、KD树）以及文献[2]中的算法进行比较，把α设为0.26，其K邻域搜索结果如表2所示。由实验结果可知，本文算法相对其他算法对点云模型的K邻域搜索所用时间较短。综上，本算法对点云K邻域的搜索不仅速度较快，针对不同复杂程度的模型其对每个点的K邻域搜索耗时也较稳定，且对α也有较好的稳定性。

4 结束语

本文算法在规则立体栅格法的基础上加入八叉树的思维，使得每个栅格内包含相对均匀的点云，即含有相似的空间曲面信息，在对点云进行K邻域搜索时可及时并正确的获取其局部特征点，利用动态空间球的外切立方体扩展动态球并搜索K邻域，减少了计算量并提高了搜索速度。实验表明，本算法对调控因子具有较强的稳定性，并且针对不同数量的点云模型其搜索时间也较为稳定，与其他算法相比在搜索速度上具有相对的优势。

参考文献：

[1]孙金虎.点云模型分割与融合关键技术研究[D].南京航空航天大学，2013.

[2]杨军，林岩龙，王小鹏，等.基于自适应空间球的k最近邻域快速搜索算法[J].计算机工程，2014，40（10）：270-275.

[3]赵俭辉，龙成江，丁乙华，等.一种基于立方体小栅格的K邻域快速搜索算法[J].武汉大学学报（信息科学版），2009，34（5）：114-117.

[4]张蓉.散乱点云的数据分割与特征提取技术研究[D].南昌大学，2016.endprint