基于网格化曲率聚类的点云分割算法

基于网格化曲率聚类的点云分割算法

现在，在3d工程中，点云数据通常被划分为具有独特几何特征的拓扑结构区域并进行区域重建。因此，点云数据的分割是整个剖面重建过程的重要因素之一。多年研究形成了三种方法。首先，在基于边缘的方法、边缘的方法和混合方法（hybdi）的方法中检测到分散边界点，并将边界点连接到边界线作为整个块过程的基础。主曲线的方法通常也被广泛使用。然而，由于噪声和云的不规则性，它们对噪声和点云的不规则性非常敏感。在基于面的方法中，首先选择合适的种子数据，然后评估云旁边点云的局部几何特性（如法针、曲线等），并将具有类似几何属性的点云添加到当前区域，以将数据点划分为不同的区域。由于区域生长受到阈值的影响，因此很难选择合适的生长模式。为了克服两种方法的限制，yokyaa和leven提出了一种混合区域分割方法，该方法结合了基于边缘和区域生长的方法。可以看出,以上的区域分割方法的本质在于找到点邻域的微分信息,然后利用所求出的微分信息来识别边界点或边界曲线.在求取曲率等微分几何信息之前,一般首先要进行三角化,然后进行微分信息的求解,计算量比较大.为了克服计算量大的问题,柯映林等提出对点云数据进行网格划分建立散乱点之间的拓扑关系,并将距空间栅格中心最近点的曲率作为栅格曲率,根据空间栅格与其26近邻的曲率差识别边特征栅格,最后基于连通性准则实现空间散乱数据的区域分割.本文在此基础上采用一种优化的动态网格划分方法,下面具体讨论这种算法.1点云聚类分析本算法的基本思想是:首先对点云数据进行动态网格划分,建立点云的拓扑关系,求出网格内距离网格中心点最近的点Pi,拟合局部抛物面求出该点Pi的曲率等微分信息,然后用K-means方法利用特征相似性进行点云数据的聚类,分割特征区域.1.1ymin-e,zmin-e针对散乱点云分布的不规则性,以及直接网格划分时Pi点的微分特性无法代表所有点的微分特性,本文采用动态网格划分的方法,对点云数据进行网格化建立点云之间的拓扑关系.采用动态层法和局部重划法相结合的动态网格划分方法对点云特征突变区等部分网格进行动态调整.设点云数据中最大与最小x、y、z坐标值分别是{Xmax,Ymax,Zmax,Xmin,Ymin,Zmin},且给定容差e,经多次实验,容差设定为点间距的3倍.并随机抽取3对邻近点云,估算点云数据的密度.动态网格划分的具体步骤如下:1)首先定义以点(Xmax+e,Ymax+e,Zmax+e)和(Xmin-e,Ymin-e,Zmin-e)为对角点,且表面平行于坐标平面的空间六面体为点云的空间包围盒.2)根据点云密度设定阈值t,将点云包围盒沿坐标轴方向按等间隔t划分成空间六面体网格,则在包围盒内,沿X,Y,Z方向,以t为步长分段.可以得到,在三个方向上划分的段数分别为m,n,l:{m=ΙΝΤ((Xmax+e)-(Xmin-e)t)+1n=ΙΝΤ(Ymax+e)-(Ymin-e)t)+1l=ΙΝΤ((Ζmax+e)-(Ζmin-e)t)+1(1)那么对于空间内任意一个点P,它都会属于某一个位置的基本正方体(i,j,k)内,它的坐标(xp,yp,zp)满足:{xp∈((Xmin-e+i×t)‚(Xmin-e+(i+1)×t))yp∈((Ymin-e+j×t)‚(Ymin-e+(j+1)×t))zp∈((Ζmin-e+k×t)‚(Ζmin-e+(k+1)×t))(2)3)统计每一个网格内点云的个数并计算点云密度,将空网格删掉.求出每一个网格的中心点Oi,在网格数据集中找到离中心点Oi最近的点Pi.对网格内数据在XYZ方向进行排序,判断数据的分布状况.a.如果网格内的数据分布比较密,点云个数超过了抛物面拟合的需要,但是点云数据之间在X,Y,Z方向的角度偏差在一定的允许范围内,则不必对网格进行调整.b.如果网格内的数据分布比较密,点云个数超过了抛物面拟合的需要,但是点云数据之间在X,Y,Z方向的角度偏差超出了允许范围,则根据点云偏差的突变,将原网格在一定方向上进行细分,添加网格.c.如果网格内数据分布均匀,点云个数满足抛物面拟合的需要,并且点云数据之间在X,Y,Z方向的角度偏差在一定的允许范围内,则不必对网格进行调整.d.如果网格内的数据分布比较稀疏,点云个数不满足抛物面拟合的需要,但是点云数据之间在X,Y,Z方向的角度偏差在一定的允许范围内,则判断邻近网格内数据的分布情况,以原网格为中心,边长2t扩大网格,或沿某一方向将网格与邻近网格合并.然后重新判断,直到满足需要.1.2基于变异值分解的解析法法矢和曲率是曲面的基本特性,也是曲面特征识别的重要依据之一.空间数据点曲面曲率计算方法一般有五种,分别是坐标转化法、正交步进法、交叉曲面片法、曲面三角化法和TW法.1992年stokely和wu对这五种曲率计算方法进行了试验比较,证明坐标转化法是这几种方法中比较实用的方法,并且计算步骤亦比较简单.本文亦采用坐标转化法,在每个网格内进行局部曲面拟合.其基本思想是:每一个网格内,求出距离网格中心点最近的点集中的点Pi,利用Pi的k近邻拟合抛物面S,通过计算S的曲率特性来确定该数据点的曲率特性.每一个网格内点Pi的k近邻,记为Nd(Pi)拟合平面估算测量点法矢,目标函数为min∑p∈Νd(pi)((p-pi)ni)2(3)经简单计算,可得到对称的半正定矩阵(3阶矩阵):Cv=∑p∈Νd(pi)(p-pi)(p-pi)T(4)式中:Cv最小特征值对应的特征向量单位化,即为曲面在点Pi的法矢Ni.多次实验表明,当k取为24~30,曲率计算一般都能获得较好效果.在点Pi处建立局部坐标系(u,v,h),且坐标原点为Pi,坐标轴h设为法矢Ni,坐标轴u和v可以在过点Pi垂直于Ni的平面内任意确定.将点Pi的k近邻由全局坐标(xi,yi,zi)转化为局部坐标系(ui,vi,hi),并用转换后数据拟合如下面的抛物面.S(u,v)=a0+a1u+a2v+a3uv+a4u2+a5v2(5)抛物面拟合通过求解目标函数mink∑i=1[hi-(a0+a1u+a2v+a3uivi+a4u2i+a5v2i)]2实现.应用奇异值分解法可获得拟合抛物面的最小二乘解.具体实现过程如下:Step1将网格邻域内点的坐标代入式抛物面S方程中,设每个网格内有k个点,则得到方程组AX=Z(6)式中有A=|1,u0,v0,u0,v0,u20,v201,u1,v1,u1v1,u21,v211,uk,vk,ukvk,u2k,v2k|X={a0,a1,a2,a3,a4,a5}Τ,Ζ={h0,h1,⋯,hk}ΤStep2采用奇异值分解法求解线性方程组(5),由X=A′Z求解曲面方程的系a,b,c.Step3通过对拟合抛物面S(u,v,h)=S(u,v,au2+buv+cv2)求一、二阶偏导数,得到Pi点(局部坐标系的原点)的平均曲率与高斯曲率:Su=(1,0,2au+bv)Suu=(0,0,2a)Sv=(0,1,bu+2cv)Svv=(0,0,2c)Suv=(0,0,b)Pi点的法矢为:n=Su×Sv|Su×Sv|由抛物面的第一、第二基本形式,可以得到:E=SuSu,F=SuSv,G=SvSv,L=Suu·n,M=Suv·n,N=Svv·n则得到Pi点的平均曲率(H)和高斯曲率(K):Κ=LΝ-Μ2EG-F2Η=EΝ-2FΜ+GL2(EG-F2)(7)1.3网格点云产业分割的实现通过计算得到每一个空间网格的平均曲率、高斯曲率和法矢等微分几何信息后,通过曲率、法矢与曲面的关系,采用K-means的方法,对点云数据进行区域分割.首先为了更快更准的进行分割,根据如下图1,2所示的曲率分布图,选择比较合适的K个(K=2)初始聚类中心(初始聚类中心也可以随机选取的),并把每个对象分配给离它最近的中心,从而得到两个初始聚类.然后,计算出当前每个聚类的中心作为新的聚类中心,并把每个对象重新分配到最近的中心.如果新的聚类的质量优于原先的聚类,则用新聚类代替原聚类.循环执行这一过程直至聚类质量不再提高为止或设定一定的迭代次数.用K1,K2表示初始分割后的两个区域,经过了初始分割后,每一个空间网格的点,都带有一个属性值Kind,其值等于K1,K2中的一个.利用网格的拓扑关系,比较每一个网格和其邻近的26个网格之间的Kind属性以及曲率的变化趋势,来检查和纠正初始分割结果,并对点云数据进行重新分割.具体实现过程如下:按照网格的索引号(i,j,k),搜索每一个网格和其邻近网格的分类情况和曲率的变化趋势.可以分为下面三种情况:1)如果该网格内的Kind值与其他邻近网格的Kind值全不相同,则该点为分类错误的点,重新对其进行分类.2)如果该网格内的Kind值与其他邻近网格的Kind值不完全相同,则利用曲率的变化趋势,判断其分类是否正确.3)如果该网格内的Kind值与其他邻近网格的Kind值全相同,并且曲率无明显变化趋势,则证明该点是分类正确的点.依照上面的方法,完成所有网格点云数据的检查和纠正,在利用网格的拓扑关系,将曲率值没有明显的区别,但是,物理上属于不用曲面的点云数据进行分割,得到比较满足精度的分割后的数据.2点云数据区域分割作者提出的算法已在C#平台上,以directX为图形显示工具编程实现.本实例使用由莱卡公司的近距离扫描仪HDS4500扫描获得的点云数据,如下图3(a)所示,所扫描的是古建筑天花上梁的一部分,包含13917个散乱点.在进行空间网格划分时,考虑到点与点之间的距离在6?mm左右,所以网格尺寸是50?mm.古建筑的构件结构一般是由平面和圆柱或是圆弧等几何特征组成,从下图3(a)可以看出该构件是由平面和圆柱面组成.采用本文方法对点云数据进行区域分割,由曲率和二次曲面的关系,可以得知经过该算法初始分割后,只能将平面和圆柱面初始分割开,如下图3(b)所示是点云数据,是经过曲率的分割后的数据结果显示,黑色为平面几何特征,黄色为圆柱面几何特征.对初始分割后的点云数据,通过空间网格拓扑关系的检查、纠正和二次分割后,得到如下图3(c)所显示的比较满意的点云数据区域分割效果.用不同的颜色表示不同的区域.3采用三角化运算和动态网格本文通过点云数据动态网格的空间划分建立测