一种基于空间分块策略的快速搜索算法

一种基于空间分块策略的快速搜索算法

1快速快速算法随着激光扫描仪设备的发展，将包含测量对象更详细的个人信息数据采集到能够，成为高精细测量建模的发展方向。基于大量数据的海面重建技术已成为研究的热点问题。在基于大量数据的数据分析中，如基于磁盘面积和信息系统的数据分析，通常需要频繁搜索点k的下一个点。例如，在重建磁盘面积时，需要使用k附近相邻零的最小平方来计算测量点的切面，并且需要替换k附近相邻零的二乘数。在搜索点和切割点的下一个点时，需要使用k附近的信息。因此，附近相邻点的检测算法的速度直接影响到重建曲线的速度。设X={x1,x2,…xn}是未知曲面M上的空间采样点集,点集X中与某一测点xi的直线距离最短的k个点,称为xi的k近邻,记为Nbhd(xi),k近邻中的每个测点称为xi的邻近点.通常,计算某点的k个近邻的方法是求出测点与其余n-1个点的直线距离,并按从小到大的顺序排列,前面的k个点即为测点的k近邻,这种方法很简单,但是当数据量达到上万甚至几十万个点的时候,用此方法来计算数据点的k近邻必然会花费很多时间.许多学者针对此问题进行了一些快速算法的研究,文献利用点集Voronoi图来进行k个最近点的搜索,但点集的Voronoi图计算量非常大;文献基于空间索引树的遍历,适合于空间实体对象的查询,不适合于大量的空间点云数据;文献利用空间分块策略进行k近邻搜索,但文献只研究了平面点集的k近邻搜索问题,文献将文献的算法推广到三维空间数据点集,并综合考虑了数据集的范围、点的总数及最近点数目k,通过实验得出了接近于最佳搜索速度的子立方体大小的参数值范围,但是文献只考虑了数据集的范围,没有充分考虑到子立方体的划分与空间数据点密度的关系,如果不同密度的点云数据划分的子立方体边长接近,子立方体内包含的点数是不同的,查找k近邻的速度就会受到影响.针对上述问题本文提出一种快速有效的K近邻的搜索算法,本算法采用空间分块策略,把包含数据的最小长方体划分成多个子立方体,综合考虑了空间数据的范围、点的数量、近邻点数k以及空间数据点的密度,给出了一种新的估算立方体边长的方法;通过实验得出了不同点集的情况下,子立方体的边长与近邻点数目k的关系,在内存分配策略、搜索终止条件上进行了改进,进一步提高k近邻的搜索速度.2子方位空间和数据点首先根据子立方体边长的计算值,把数据空间分成多个子立方体空间;然后记录子立方体内包含的数据点;最后利用子立方体内点的信息对每个测点进行k近邻的搜索.2.1生成项目由来typedefstructtagOBJECT{intnOHSum;//结构中具有的句柄个数DWORDlOElementSum;//图形元素结构数目HANDLEhOElement;//图形元素块头句柄DWORDlOCubeSum;//立方体结构数目HANDLEhOCube;//立方体内存块头句柄DWORDlOPolylineSum;//多边形结构数目HANDLEhOPolyline;//多边形内存块头句柄charcOUse;//使用标记charcODelete;//删除标记}OBJECT;图形元素的数据结构:typedefstructtagELEMENT{intnEHSum;//结构中具有的句柄个数doublefE1,fE2,fE3,fE4,fE5,fE6;//坐标intcEDeleteFlag;//删除标记intcETypeFlag;//点,边标记intcEEdgeFlag;//边界点、边标志:intcEProcFlag;//处理标记intcECubeIndexNo;//点所属的立方体编号HANDLEhPKNEIHANDLE;//点的K近邻内存块的头句柄intnKPcount;//点的近邻数}ELEMENT;子立方体结构的定义typedefstructtagCube{intCubeNo;//元素编号POINTSETCoVex;//立方体左下角、右上角坐标intPointCount;//立方体中点的数量intDeleteF;//删除标记KNCUBEKNCubes;//立方体的27个近邻(包括自身)HANDLEhPHANDLE;//立方体中包含的点的内存块的头句柄}CUBE;2.2子：子：子：子：子：子：子快速识别的可扩张性算法速度的快慢取决于子立方体划分的是否合理,如果子立方体划分的过大,子立方体数少,计算某子立方体的近邻时,查找速度快,但是一旦在本立方体中不能成功的找到测点的k近邻,到近邻立方体中查找时数据量会大大增加,又降低查找速度;如果子立方体划分的小,子立方体数多,计算某子立方体的近邻时,查找速度慢,但是一旦在本立方体中查找k近邻不能成功,那么到近邻立方体中查找时数据量会减小,也会提高查找速度,两者相互制约,所以如何来确定子立方体的边长,得到一个最佳的搜索速度,是本算法的关键.空间数据点集的总数、近邻数k、数据范围、数据点的密度等信息都将制约着子立方体的边长L的确定,本算法综合考虑了这些因素,通过两次划分子立方体调整边长.设空间数据点集的总数:N需要查找的近邻数:k点集的密度:d子立方体的边长:L不包含任何数据点的小立方体称为空小立方体空间:vkong首先计算包含所有数据的最小长方体空间的体积vzongvzong=(xmax-xmin)×(ymax-ymin)×(zmax-zmin)(1)将最小长方体空间进行指定边长l的划分,计算所有空的小立方体空间的体积和包含数据点的有效小立方体的体积vyx:其中l=(vzong×1.5k/N)1/3,n为空子立方体数.d=vyx/N(3)假设子立方体包含的点数是近邻点数k的α倍,则有:L3/d=α×k(4)整理(2)、(3)、(4)式得:L=C·α1/3(5)其中C=(vyx×k/N)1/3在k,N,vyx确定后,通过调整α值就可以调整子立方体边长,通过实验分析,不同疏密程度的海量空间数据,都可以给出一个近似统一的接近于最佳k近邻搜索速度的α值,使本搜索算法具有更强的适应性.立方体边长L确定后,最小长方体空间在x,y,z方向上的分辨率分别为:LX=(xmax-xmin)/LLy=(ymax-ymin)/LLy=(zmax-zmin)/L则子立方体的总数为:NCUBE=LX×LY×LZ;然后把每个数据点分配到相应的子立方体空间,记录点所在的子立方体的编号,以便后续的查询操作.由于每个子空间内含有数据点的个数是未知的,为了节省存储空间,提高运算速度,本文采用图元数据结构,动态地分配内存空间,采用指针变量存储方式.一个图元为多个基本图形元素的集合,点、边、面、体称为基本图形元素.3计算测点到当前子部分的距离利用上面的图元数据结构,对每个测点进行k近邻的搜索步骤如下:第1步.计算子立方体边长,划分子立方体,并按编号存入内存,记录每个立方体所包含的数据点及每个点所属的子立方体编号;第2步.计算候选点到当前子立方体到六个侧面的最短距离ds;第3步.根据测点所在的子立方体编号,判断当前子立方体内的点数是否大于所要搜索的近邻数k,如果不大于,则进入第四步,如果大于则计算当前子立方体内所有点与测点的距离,按距离升序的方式,如果第k个近邻点与测点的距离小于ds,则查找成功,记录k个近邻点,否则进入第四步;第4步.找出当前子立方体的26个近邻,计算测点到26个近邻立方体中心的距离,排序后从最近的子立方体中查找测点的K近邻,查找成功,记录k个邻近点;否则,进行外围扩展迭代,继续查找,直到查找成功,记录k个邻近点.4算法的有效性验证为了验证本文算法的正确性和有效性,我们在三星1.5GHz的笔记本PC机上进行了下述3组实验.实验数据为真实物体的空间点云数据,图2～6所示,分别给出了兔子、龙、马、彩陶壶、瓶盖的点数据模型,在VC++6.0环境下,用OpenGL显示.表1～3中给出了不同物体20个点的k近邻搜索的实验数据.测试时间为搜索20个点k近邻的CPU运行时间,用API函数GetSystemTime()得到,单位为ms.实验1.从不同算法的对比研究发现本算法的搜索速度大大提高.从实验数据分析可以发现搜索k近邻算法速度的快慢主要受到子立方体数与子立方体内包含的点数的影响,从表1中可以看出,在测点所在的子立方体中搜索到k近邻的情况是很少的,因此需要合理的划分子立方体,协调两者的关系.本算法由于在计算子立方体边长时,计算了立方体的有效空间,考虑了点云数据的密度,数据的范围,点云的数量,近邻点数,通过调整系数α,即子立方体内包含的点数与近邻点数k的倍数关系,使得子立方体数目不至于太多和太少,子立方体的划分更加合理,从而可以得到接近最佳搜索速度的子立方体边长.在到近邻子立方体搜索测点的k近邻时,文献向外扩展一圈,而本算法只是扩展了7个最近邻的子立方体,它的测点在一个子立方体内的角上,所处位置最差,需要到近邻子立方体中查找k近邻时所需的子立方体数最多的情况,因此改善了搜索的终止条件,使本算法速度大大提高.实验2:验证本文算法对不同物体的点云数据的适应性.对每个物体分别设置不同的k、α值的组合进行实验,结果如表2所示:从表3中可以得出本文算法对于不同数量的点云数据和不同近邻个数k的最快搜索速度的α值范围比较集中,在1-4之间,当k值较小时,α值应取大些,如3、4,即子立方体内包含的点数是k的3或4倍,当k值较大时,α值应取小些,如1、2,这样可控制子立方体边长不会过大或过小.实验3:数据是对图2所示兔模型点云数据进行二次采样,使其数据点总数分别为35947、17974、7190和3595,对α、k值的不同组合进行测试,结果如表3所示,从表中可以看出,本文算法于不同密度的点云数据和不同邻域个数的k近邻搜索速度的α值范围比较集中,在1-4之间,类似于实验2的结果,并且α值在此范围内搜索时,搜索时间差很小.这说明了本文算法对处理不同的点云数据具有很好的适应性.5海量空间数据测试本文算法在