基于局部型面特征的散点云数据获取

基于局部型面特征的散点云数据获取

0局部型面高效确定在3d工程中，基于云的特性几何特征来简化分散的云，可以减少云的冗余，提高网格结构等几何计算的处理效率。Chen等对点云数据进行三角网格化,计算三角面片的法向量,并估算三角面片所在位置的曲率,依据该曲率精简点云数据,该算法可实现散乱点云的非均匀精简,但需耗费大量的系统资源,运行效率低。洪军等采用包围盒和角度-弦高法精简点云数据,该方法不能准确计算点云的曲率分布,且只适用于扫描线型点云。周绿等采用抛物面拟合法求解局部曲率,根据曲率分布精简点云,该方法可准确估算点云曲率分布状况,但在获取点云局部型面参考数据时需对点云进行三角剖分,运算量大,算法运行效率低。针对上述问题,本文基于文献提出的曲率估算方法分析点云型面特征,依据型面特征,通过调整局部点集空间范围及曲率标准差对点云进行精简。此外,针对文献索引结构不能有效索引维数退化的点云数据及节点聚类效率低等问题,改进R*-tree索引结构,将数据点及索引节点的最小绑定矩形(minimumboundingrectangle,MBR)统一表示为四维点对象,结合k-means算法对R*-tree进行节点分裂,建立点云动态空间索引结构,实现局部型面参考数据的快速获取。该算法可在保留点云型面特征的基础上,快速有效地对点云进行精简。1点云动态域的构建通过改进R*-tree建立散乱点云动态空间索引结构,实现点云的动态维护及局部型面参考数据的快速获取。1.1局部点集平行,影响节点mbr文献采用R*-tree建立点云动态空间索引结构,该结构的节点插入算法基于MBR体积增量,应用于散乱点云的空间聚类分簇时,若点云中的局部点集平行于坐标平面分布,则节点MBR将由三维退化为二维,导致R*-tree节点插入失效,破坏了R*-tree节点的聚合性。为解决该问题,将数据点及叶节点的MBR统一表示为四维点对象(x,y,z,r),其中(x,y,z)为MBR中心坐标,r为MBR的外接球半径。1.2聚类分簇中心坐标采用k-means算法实现散乱点云的空间聚类分簇。将任意一对节点的MBR中心作为初始分簇中心,形成两个初始分簇,将数据点添加到与分簇中心最近的初始分簇中。为使节点MBR均匀,根据R*-tree定义,当分裂所得某一簇节点的子节点数k小于R*-tree最小子节点数m时,将另一簇中距离当前簇较近的m-k个节点插入到当前簇中,并调整分簇结果。采用k-means算法对R*-tree叶节点进行聚类分簇时,需要迭代定位最终的分簇中心。对于同簇节点中的N个叶节点,其四维标准化坐标pi=(xi,yi,zi,ri),i=1,2,…,N,分簇中心坐标(ˉx,ˉy,ˉz,ˉr)(x¯,y¯,z¯,r¯)计算公式为ˉx=Ν∑i=1xiri/Ν∑i=1riˉy=Ν∑i=1yiri/Ν∑i=1riˉz=Ν∑i=1ziri/Ν∑i=1riˉr=Ν∑i=1ri/Ν}(1)x¯=∑i=1Nxiri/∑i=1Nriy¯=∑i=1Nyiri/∑i=1Nriz¯=∑i=1Nziri/∑i=1Nrir¯=∑i=1Nri/N⎫⎭⎬⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪(1)各叶节点至聚类分簇中心的距离为d=√(xi-ˉx)2+(yi-ˉy)2+(zi-ˉz)2+(ri-ˉr)2(2)d=(xi−x¯)2+(yi−y¯)2+(zi−z¯)2+(ri−r¯)2−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−√(2)该索引结构由3种节点组成,最上层的节点为根节点,最底层的节点为叶节点,其余的节点为内部节点,内部节点可以由多层节点构成。除根节点外,每个节点的子节点数n满足m≤n≤M,其中,m、M分别为节点的最小子节点数和最大子节点数,通常取8和20。基于四维点表示的散乱点云动态空间索引结构如图1所示。2云的局部表面附近2.1局部型面参考点集的生成采用R*-tree的k近邻查询算法获取点云任意点P的k近邻点Nj(j=0,1,…,k-1),将其与点P组成局部型面参考点集X,逼近生成该点集的微切平面。2.2局部坐标系如图2所示,设局部型面参考点集X在微切平面上的投影为X′={P′i|i=0,1,…,k},以点P的投影点P′为原点,以P′与X′中距其最远的点所构成的向量作为u轴,以微切平面的法向轴为w轴,由右手规则确定v轴,建立局部坐标系C。然后将X′变换到坐标系C下得点集X″={(ui,vi)|i=0,1,…,k}。2.3求点集x的mbr+v向边边分别对X″中数据点的u坐标和v坐标递增排序,可得两个坐标分量序列UC={uci|i=0,1,…,k}和VC={vci|i=0,1,…,k}。在坐标系C下,求点集X″的MBR及其u向边长lu和v向边长lv。点集X″中任意数据点(ui,vi)的参数为u´i=(ui-uc0)/luv´i=(vi-vc0)/lv}(3)u′i=(ui−uc0)/luv′i=(vi−vc0)/lv}(3)2.4解析正演矩阵采用n×m阶的Bézier曲面逼近点云的局部型面。设qt∈X,其四维化坐标qt=(xt,yt,zt,rt),t=0,1,…,k,则Bézier曲面可表示为S(ui,yi)=n∑i=0m∑j=0Bi,n(ut)Bj,m(vt)pi,j=qt(4)S(ui,yi)=∑i=0n∑j=0mBi,n(ut)Bj,m(vt)pi,j=qt(4)式中,pi,j为待求Bézier曲面的控制点。设Di,j(u,v)=Bi,n(u)Bj,m(v)i=0,1,…,n;j=0,1,…,m将式(4)写为式(5)所示的矩阵形式:D[p1p2…pn]T=[q0q1…qk]T(5)pi=[pi,1pi,2…pi,m]TD=[D0(u0,v0)D1(u0,v0)⋯Dn(u0,v0)D0(u1,v1)D1(u1,v1)⋯Dn(u1,v1)⋮⋮⋮D0(uk,vk)D1(uk,vk)⋯Dn(uk,vk)]D=⎡⎣⎢⎢⎢⎢⎢D0(u0,v0)D0(u1,v1)⋮D0(uk,vk)D1(u0,v0)D1(u1,v1)⋮D1(uk,vk)⋯⋯⋯Dn(u0,v0)Dn(u1,v1)⋮Dn(uk,vk)⎤⎦⎥⎥⎥⎥⎥(6)Ds(ui,vi)=[Ds,0(ui,vi)Ds,1(ui,vi)…Ds,m(ui,vi)]s=0,1,…,n系数矩阵D的奇异值分解为D=UWVT(7)式中,U为(k+1)×[(m+1)(n+1)]阶的列正交矩阵;W为[(m+1)(n+1)]×[(m+1)(n+1)]阶半正定对角阵;V为[(m+1)(n+1)]×[(m+1)(n+1)]阶正交矩阵。最小二乘Bézier曲面控制点为[p1p2…pn]T=VW-1U-1[q0q1…qk]T(8)3张量积be能er曲面的两极化反应点云中各点及其近邻点所构成的点集均能以Bézier曲面逼近。遍历点云数据,对当前点和其近邻点所构成的点集逼近生成Bézier曲面,由于当前点的参数值是已知的,可以由下式计算出逼近曲面上对应参数位置的曲率:c=(Suu⋅n)(Svv⋅n)-(Suv⋅n)2(Su⋅Su)(Sv⋅Sv)-(Su⋅Sv)2(9)c=(Suu⋅n)(Svv⋅n)−(Suv⋅n)2(Su⋅Su)(Sv⋅Sv)−(Su⋅Sv)2(9)n=Su×Sv|Su×Sv|(10)n=Su×Sv|Su×Sv|(10)式中,Su、Sv分别为n×m的张量积Bézier曲面的一阶偏导;Suu、Svv、Suv分别为张量积Bézier曲面在u向、v向和uv向的二阶偏导。以c作为当前点曲率值的估计。4基于型面特征的疏散点云精制算法采用R*-tree空间查询算法,查找与点P的距离小于r的数据点集Y,该点集的曲率标准差σ为σ=√k∑i=0(ci-ˉc)2/k(11)ˉc=k∑i=0ci/(k+1)(12)曲率标准差越大说明其型面越陡峭,否则越平坦。为保留点云型面细节特征,在曲率标准差较大区域将r适当调小,删除距离点P小于r的点,实现点云的非均匀精简。基于型面特征的散乱点云精简算法流程如图3所示。实际应用中根据点云的疏密程度确定r,令随机两点间的距离为r0,通常r取3r0～4r0时可较好保留点云的型面特征,根据型面特征的复杂度确定σ0,一般σ0取0.0001时可较好保留点云的型面特征。5点云精制算法制定三组实验方案验证本文算法的有效性,测试环境为:联想启天2800台式计算机(处理器为IntelPⅣ2.4GHz,内存256MB),操作系统GNU/Linux。方案一分别采用Bézier曲面及抛物面逼近图4所示点云的局部点集,计算点集到两逼近曲面的距离。点到Bézier曲面的最大距离是12.0μm,平均距离是4.2μm;点到抛物面的最大距离是46.5μm,平均距离是32.5μm。采用Bézier曲面可更准确地拟合点集曲面,基于该曲面可更准确地计算点集曲率。方案二采用文献算法及本算法对米老鼠点云进行精简。图4a为米老鼠原始点云,点数为20631;图4b为采用文献算法对米老鼠点云精简后的结果,点云点数为5430;图4c为采用本文算法在r=1mm、σ=0.005时的精简结果,点云点数为5235。从图4c中可以看出,本文算法在曲率较大区域保留了较多点,在曲率较小区域保留了较少点,更好地保留了点云的型面特征,显著减小了点云冗余度。文献算法和本文算法对米老鼠点云精简所耗时间分别为3.683s和0.672s。方案三采用本文精简算法,通过调节r与σ的取值(表1)对维纳斯点云进行精简,结果分别如图5b～图5d所示。结合图5及表1分析可知,r越大,