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

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

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

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

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

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

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

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

1 概述

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

k邻域搜索的传统方法是计算任一点到其余各点的欧氏距离,然后升序排序,前面的k个点即为此点的k邻域点。这种方法简单直观,易于实现,但其时间复杂度较高,在点云规模较小时,此算法能取得较好的结果。然而,随着三维扫描设备的发展以及建模精度的不断提高,点云数据的规模也不断增大,这种方法的耗时惊人。国内外众多学者对此问题提出了一些比较快速的搜索算法,大致分为3类:

(1)利用树的层级结构对点云进行k邻域搜索[1-2],但是这些方法思想比较复杂,不易实现,而且若邻近点和待搜索点处于不同层时会造成搜索范围扩大,降低搜索效率。同时,树结构的创建也具有一定的时间消耗。此外,此类方法不适合大规模点云数据的k邻域搜索[3-4]。

(2)利用 Voronoi图对数据集进行邻域搜索[5-6],但是在构建点集 Voronoi图时需进行较多的浮点运算,计算量仍然较大。

(3)利用立方体栅格或球空间缩小k邻域的搜索范围,然后按传统方法搜索。文献[7]在点云分块后进行搜索,但是每个子块内边界点的k邻域需要搜索与其最近的26个子空间,浪费了较多的时间。文献[8]在文献[7]的基础上,推广了文献[9]中只能解决二维问题的搜索方法,提出一种新的搜索算法,该算法利用子块扩张方法避免搜索相邻子空间,但是如果点云分布不均匀,可能会造成某个子空间内的采样点特别多,在进行k邻域搜索时会进行大量的浮点运算,降低了搜索效率。文献[10]采用二次分块策略,利用多个小立方体栅格逐步缩小k邻域的搜索范围以提高搜索效率,不过该算法仍然存在分块不均匀问题,而且算法的稳定性不是很理想。文献[11]将点云进行微小分块,虽然算法预想每个子块内点数在2～5之间,但是由于模型的多样性和采样的不均匀性,实际和预想有一定差距。文献[12]利用点的三维坐标序号形成一个动态网格缩小k邻域的搜索范围,算法视角独特,搜索效率得到了一定的提高,但是不能有效保证搜索结果的正确性,限制了算法的应用。文献[13]在文献[12]的基础上,利用自身小立方体有效解决算法搜索结果不正确的问题,而且采用分块策略,在较大程度上降低了算法的搜索范围和排序算法的复杂度,提高了搜索效率。文献[14]对参数k进行了研究,提出了依据最小分类样本尺寸确定参数k的方法,并将其应用到聚类分析中,但该方法中参数k对噪声非常敏感。

本文针对大规模散乱点云数据,提出一种新的k邻域快速搜索算法。采用与k无关的分块策略对整个点云空间分块;以候选点所在子块的采样点近似密度确定初始动态球半径;以球的外切立方体搜索k邻域候选点;当k邻域候选点数目不满足要求或搜索不成功时,以外切立方体的外接球扩大搜索范围,直至满足要求或邻域搜索成功。

2 算法描述

2.1 点云空间分块

设点云数据集合内采样点总数为N,其最小包围盒的体积为V,点云空间中采样点分布均匀,且每个子块内点云数目为num。将包围盒划分为若干个子空间,则子空间的边长L为[11]:其中,xmax,xmin分别为点云空间中在x方向的最大值和最小值;ymax,ymin分别为点云空间中在y方向的最大值和最小值;zmax,zmin分别为点云空间中在z方向的最大值和最小值。

根据点集中采样点坐标值计算其所处的子空间序号,将采样点归入相应的子空间中。

2.2 初始动态球半径的计算

在完成点云空间分块后,对任意子空间S内任一采样点p,其初始动态球半径计算方法如下:假设p所在的子空间内采样点分布均匀,以此子空间内点的分布密度作为采样点局部的近似采样密度,根据近似密度和k值自适应计算初始动态球半径r,其计算公式如下:

其中,Ns为空间S内采样点数目;Vs为空间S的体积。由式(2)可知,本文算法初始r的确定仅和子块内点云数目num相关,减少了参数控制,提高了算法的自动化程度。

2.3 k邻域快速搜索算法

2.3.1 k邻域候选点的计算

首先,以任一点p为圆心,r为半径确定p的动态球O,根据动态球O确定其覆盖的子空间范围;其次,计算O的外切立方体,从覆盖的子空间内搜索位于外切立方体内的点,这些点即为k邻近候选点。

2.3.2 动态球的扩充

若外切立方体内的k邻近候选点数目不满足要求,即小于k,或搜索不成功,则扩充动态球,并根据新动态球的外切立方体重新计算k邻近候选点或重新搜索。扩充方法如图1所示。

由图1可知,O0和Cube0为p的当前动态球和动态球的外切立方体,灰色区域为动态球覆盖的子空间范围。当需要扩充时,计算Cube0的外接球O1,并计算O1的外切立方体Cube1,O1和Cube1即为扩充后p的新的动态球和动态球的外切立方体。如果Cube1内的点云数目满足要求,或p的k邻域搜索成功,则停止扩充,否则继续扩充。本文算法在采样点动态球的外切立方体内点云数目K满足要求的情况下,至多扩充一次即能保证p的k邻域搜索成功,这在一定程度上减少了扩充次数,提高了算法效率。

图1 动态球扩充方法

2.3.3k邻域搜索

按2.1节的方法完成点集的划分后,对子空间中任一点p完成k邻域搜索的步骤如下:

(1)利用式(2)计算p的初始动态球半径,并根据2.3.1节中方法从球覆盖的子空间中搜索位于外切立方体内的点,即k邻域候选点。

(2)计算k邻域候选点数目K,若K＜k,则按2.3.2节方法扩大动态球O,并重新计算k邻域候选点和点数K,若K满足要求则停止,否则继续扩大p的动态球,直至其点数满足要求。

(3)若K满足要求,则分别计算K个点和p的距离d,将其保存至数组并标记,重新搜索时已标记的点不再计算。若d≤r,则将其保存至数组array中,否则不保存。若array内点数m＜k,说明k邻域搜索不成功,则按2.3.2节方法重新扩充O和计算其外切立方体,计算其内未计算过的点和p的距离d,并和新动态球的半径r进行比较,若d≤r则保存至array,直至array内点数m≥k。若m≥k,则对其排序,前k个点即为p的k邻近点。其中,r为当前p的动态球半径。

2.4 整体算法流程

输入散乱数据点集合P,输出任意点的k邻域。算法整体实现框架如下:

Step 1 按2.1节方法对点云空间分块。

Step 2 对子空间内任一点p,按2.2节方法计算其初始动态球。

Step 3 按2.3.3节方法完成p的k邻域搜索,直至整个子空间内所有采样点搜索完成。

Step 4 对点云空间中所有子空间进行搜索。

Step 5 结束。

算法的流程如图2所示。

图2 k邻域快速搜索算法流程

3 实验结果与分析

在实验中,点云数据均为真实物体的扫描数据,如图3、图4所示。

图3 常用点云模型

图4 Cat重采样模型

所有实验均在酷睿双核CPU,主频2.20 GHz,内存2 GB的个人笔记本电脑上完成,测量时间为1个点的k邻域搜索的平均 CPU时间,单位为ms。

实验1 不同子块预设值num对算法效率的影响。实验模型采用图3(a)、图3(d),实验结果如表1所示,其中,n表示该模型总共包含的点数。由表1中数据可知,对本文算法来说,当k分别取10,50和100时,Cat模型搜索时间的标准差分别为0.003 15, 0.007 84和0.040 46,Bunny模型搜索时间的标准差分别为0.036 85,0.034 57和0.108 44;对文献[11]算法来说,当k分别取10,50和100时,Cat模型搜索时间的标准差分别为 0.018 56,0.043 61和0.064 41,Bunny模型搜索时间的标准差分别为0.099 78,0.175 87和0.263 48。由实验数据的标准差可知,本文算法比文献[11]算法对num的稳定性更好。由表1中数据可知,对同一模型,相同的k和num,本文算法在搜索效率上明显高于文献[11]算法,随着k的增加,本文算法的搜索时间增加幅度较小,而且对相同k值,不同num值,算法的稳定性也高于文献[11]算法。对同一模型,随着k值的增加,或者对同一k值,随着模型的增大,本文算法和文献[11]算法的稳定性都有所降低,但是本文算法的幅度更小。至于本文算法稳定性降低的原因可能是因为在k值较大的情况下估算的局部采样点密度信息对k值的有效性降低,造成num的稳定性有所下降。

表1 不同子块点数预设值num时的算法效率

实验2 同一模型不同采样密度和不同num值对算法效率的影响。实验模型采用图4(a)、图4(d),实验结果如表2所示。对本文算法来说,当k分别取10,50和100时,Cat20%重采样模型搜索时间的标准差分别为0.016 56,0.010 80和0.013 98,Cat60%重采样模型搜索时间的标准差分别为0.002 87,0.009 06和 0.021 08;对文献[11]算法来说,当k分别取10,50和100时, Cat20%重采样模型搜索时间的标准差分别为0.032 01,0.040 18和0.073 70,Cat60%重采样模型搜索时间的标准差分别为0.023 03,0.044 49和0.061 85。由实验数据标准差可知,在模型的相同采样密度和相同k值的情况下,本文算法的稳定性明显高于文献[11]算法。由表2中数据可知,对相同采样密度、num和k时,本文算法搜索效率高于文献[11]算法。当k值较小时(取k=10或50),本文算法随着采样密度的提高稳定性增强,而文献[11]算法的稳定性降低;当k值较大时(取k=100),本文算法的稳定性略微有所降低,但仍高于文献[11]算法。

为了和已有算法的搜索效率进行比较,本文算法取num=3进行实验3。同时,根据已有算法的实验结果,文献[11]算法取初始动态球半径调节因子β=0.3,半径的扩展倍数设为1.1,文献[10]算法调节因子α=0.25,文献[13]算法左侧控制阈值a=2,右侧控制阈值β=20,初始搜索半径l=100,搜索半径增量Δl=100,子空间扩张增量取1(和文献[13]实验取值相同)进行实验3。

表2 同一模型不同采样密度对不同num值时的算法效率

实验3 不同点云模型对算法效率的影响。实验结果如表3所示,实验模型采用图3。本文算法在k=10时,搜索时间偏大,这是因为对任意模型第一次进行k邻域搜索时要对其进行分块,但是其搜索效率仍然高于文献[10]算法、文献[11]算法和文献[13]算法,这是因为文献[10]算法利用采样点的不同立方体栅格缩小k邻域候选点的搜索范围,然后利用球空间进行k邻域搜索,但是在采样点曲率较高的部分可能会造成球空间内点云数目过大,需进行大量的数值计算,而且随着k值和模型规模增加,搜索效率相差更加明显。而文献[11]算法利用与k无关的分块策略,并对计算过的球空间进行点标记,这在较大程度上降低了时间消耗,不过算法需要计算动态球覆盖小立方体栅格内的所有点与候选点的距离,如果小立方体内点过多会进行过多的浮点计算,在一定程度上降低了算法的搜索效率,而且需要较多的参数控制。文献[13]算法在每个子空间内采用候选点的三维坐标排序序号形成的小立方体来缩小点的k邻域搜索范围,很大程度上降低了浮点运算的计算量,在计算合适候选点数目或k邻域搜索失败时动态改变搜索半径加快算法的收敛速度,提高了搜索效率,但是算法在计算合适的候选点时多次进行搜索,在一定程度上增大了搜索时间消耗。另外,文献[13]算法没有针对不同的模型给出比较合适的子空间扩张增量大小的自适应计算方法,仅通过实验手段很难获得适合不同模型的增量值。相反,本文算法首先采用与k无关的分块策略,然后利用候选点所在立方体栅格的采样点近似密度作为候选点局部的采样密度,并结合k值自适应确定候选点的初始动态球半径;其次,当动态球外切立方体内的点数不符合要求,或者搜索不成功时,利用外切立方体的外接球扩大搜索范围,并对计算过的点进行标记,尽量减少采样点的计算次数,提高算法效率。这样算法不仅考虑了候选点的局部密度,而且避免了文献[11]中半径的扩展倍数和β值的参数控制,提高了算法的自动化程度。随着模型规模和k值的增加,本文算法的优势更加明显。由表3实验结果可以看出本文算法的效率明显优于其他相关算法。

表3 不同点云模型时的算法效率

4 结束语

本文算法利用候选点所在的小立方体栅格的估算密度作为候选点的局部密度,结合k值自适应计算候选点的初始动态球半径。当初始动态球内的点数不满足要求或搜索不成功时,根据候选点当前动态球外切立方体的外接球扩大搜索范围。实验结果表明,本文算法不仅对num、采样密度具有较强的稳定性,而且自动化程度较高(仅需一个参数),和已有算法相比在搜索速度上有明显的优势,有较高的理论参考价值和实用性。但是,本文算法也存在一定不足,如分块不均匀等,这将是下一步要研究和解决的主要问题。

[1] Sarkar M,Leong T Y.Application of k-nearest NeighborsAlgorithm on BreastCancerDiagnosis Problem[C]//Proc.of American Medical Informatics Association Annual Symposium.Los Angeles,USA: IEEE Computer Society Press,2000:759-763.

[2] Procopiuc O,Agarwal P K,Arge L,et al.Bkd-tree:A Dynamic Scalable kd-tree[C]//Proc.of International Symposium on Spatial and Temporal Databases.Berlin, Germany:Springer,2003:46-65.

[3] Sankaranarayanan J,Samet H,Varshney A.A Fast All Nearest Neighbor Algorithm for Applications Involving Large Point-clouds[J].Computers&Graph,2007,31 (2):157-174.

[4] Connor M,Kumar P.Fast Construction of k-nearest Neighbor Graphs for Point Clouds[J].IEEE Transactions on Visualization&Computer Graphics, 2010,16(4):599-608.

[5] Dickerson M T,Drysdale R L S,Sack J R.Simple Algorithms for Enumerating Interpoint Distance and Finding k Nearest Neighbors[J].International Journal of Computational Geometry and Applications,1992,2(3): 221-239.

[6] Goodsell G.On Finding p-th Nearest Neighbors of Scattered Points in Two Dimensions for Small p[J]. Computer Aided Geometric Design,2000,17(4): 387-392.

[7] 周儒荣,张丽艳,苏 旭,等.海量散乱点的曲面重建算法研究[J].软件学报,2001,12(2):249-255.

[8] 熊邦书,何明一,余华璟.三维散乱数据的k个最近邻域快速搜索算法[J].计算机辅助设计与图形学学报, 2004,16(7):909-912.

[9] Piegl L A,Tiller W.Algorithm for Finding All k Nearest Neighbors[J].Computer-aided Design,2002,34(2): 167-172.

[10] 赵俭辉,龙成江,丁乙华,等.一种基于立方体小栅格的k邻域快速搜索算法[J].武汉大学学报:信息科学版,2009,34(5):615-618.

[11] 马 娟,方源敏,赵文亮,等.利用空间微分块与动态球策略的k邻域搜索算法研究[J].武汉大学学报:信息科学版,2011,36(3):358-362.

[12] 马骊溟,徐 毅,李泽湘.基于动态网格划分的散乱点k邻域快速搜索算法[J].计算机工程,2008,34(8): 10-11.

[13] 杨 军,林岩龙,王阳萍,等.大规模散乱点的k邻域快速搜索算法[J].中国图象图形学报,2013,18(4): 399-406.

[14] Jivani A G.The Novel k Nearest Neighbor Algorithm [C]//Proc.of International Conference on Computer Communicationand Informatics.Coimbatore,India: IEEE Computer Society Press,2013:1-4.

编辑 顾逸斐

Fast Algorithm for k-nearest Neighbor Serch Based on Adaptive Spatial Sphere

YANG Jun,LIN Yan-long,WANG Xiao-peng,ZHANG Rui-feng
(School of Electronic&Information Engineering,Lanzhou Jiaotong University,Lanzhou 730070,China)

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.

k-nearest neighbor;surface reconstruction;point cloud;spatial sphere;partition strategy;candidate point

1000-3428(2014)10-0264-06

A

TP391.4

10.3969/j.issn.1000-3428.2014.10.049

国家自然科学基金资助项目(61261029);中国博士后科学基金资助面上项目(2013M542396);甘肃省自然科学基金资助项目(1208RJZA243);陇原青年创新人才扶持计划基金资助项目(201182)。

杨 军(1973-),男,教授、博士,主研方向:计算机图形学,虚拟现实,数字图像处理;林岩龙,硕士研究生;王小鹏,教授、博士;张瑞峰,硕士研究生。

2013-10-11

2013-12-09E-mail:tom.jun.yang@gmail.com

中文引用格式:杨 军,林岩龙,王小鹏,等.基于自适应空间球的k最近邻域快速搜索算法[J].计算机工程,2014, 40(10):264-269.

英文引用格式:Yang Jun,Lin Yanlong,Wang Xiaopeng,et al.Fast Algorithm for k-nearest Neighbor Search Based on Adaptive Spatial Sphere[J].Computer Engineering,2014,40(10):264-269.