1 引言

三维激光扫描技术作为一种新型技术,主要采用非接触的方式获取目标物体表面数据点的三维坐标,具有高效、高精度等优点,广泛应用于各个领域^[1]。但是,海量的点云数据减缓了数据处理的速度^[1-3]。所以在保证目标物体模型精度的前提下,研究点云数据的精简问题很有必要。

国内外学者针对点云数据精简的问题进行了大量的研究,主要有3类方法:包围盒法、随机采样法和曲率采样法^[4]。这3种方法都有其适用条件和不足:包围盒法多适用于曲率较小的数据,对于曲率起伏较大的数据,若压缩率较大,则精简后的点云数据不能保留较多的特征点,会影响数据的细节表达^[5];随机采样法没有考虑目标物的形状和特征,而是随机地保留点云数据,若压缩率较大,则可能导致数据失真^[6];曲率采样法适合于曲率较大的数据,对于平坦的数据,若压缩率较大,则可能造成点云数据的大量缺失^[7-8]。在利用上述3种方法进行点云精简时,精简后的点云数据量往往较多,达不到较好的精简效果。为了保证点云数据精度,确保精简后的点云数据能较好地表达细节特征,需要引进一种方法,使精简后的点云数据量较少,且能较好地保留特征点,真正达到精简点云的效果。

鉴于此,本文提出一种新的点云精简方法。引入k均值(k-means)聚类方法(k为聚类数目),对点云数据进行分类,将每一聚类中的点云数据拟合成曲面,通过比较每一点的均方根曲率值和所有点的均方根曲率的平均值,删减点云数据,达到精简点云的目的。不同于包围盒法,k-means聚类方法充分考虑到点云整体的形状,根据距离直接进行点云分类,不需要建立格网,提高了程序运行的速度。

2 k-means聚类方法

k-means聚类算法是硬聚类算法的一种,根据目标函数进行聚类^[9]。本文中,目标函数即为点云数据到初始聚类中心的欧氏距离。具体过程如下^[10]。

1) 原始点云数据P=(p₁,p₂,…,p_n)(其中,n为点云个数),给定分类组数B(B≤n),根据B值的大小,点云数据会随机产生B个聚类中心O=(O₁,O₂,…,O_B)。

2) 计算所有点云数据P与每个聚类中心O的欧氏距离,根据距离的最小值,选择最近的聚类,从而得到B个聚类。

3) 分别计算每个聚类中点云数据的重心值,作为新的聚类中心。

4) 所有点云数据按照新的聚类中心重新进行聚类。

5) 重复步骤3)、4),直到聚类中心不再变化,以此得到的B个聚类即为聚类结果。

3 点云曲率计算和精简过程

3.1 曲率计算

根据每个聚类中的点云数据,利用最小二乘法拟合曲面,并计算每个三维点的均方根曲率值。设曲面方程为

z=a0+a1x+a2y+a3x2+a4y2+a5xy,(1)

式中:x、y为某一点云数据的横、纵坐标;a₀、a₁、a₂、a₃、a₄、a₅为系数。

根据文献[ 11],令

u=∂z∂x,(2)v=∂z∂y,(3)

式中:u、v为曲面方程函数对某一点云数据横、纵坐标的偏导。

为简化公式,令:

E=1+u2,(4)F=uv,(5)G=1+v2,(6)L=∂u∂x1+u2+v2,(7)M=∂u∂y1+u2+v2=∂v∂x1+u2+v2,(8)N=∂v∂y1+u2+v2。(9)

则高斯曲率可表示为

K=k1k2=LN-M2EG-F2,(10)

式中:k₁、k₂为曲面上某一点云数据的主曲率。

平均曲率可表示为

H=k1+k22=EN-2FM+GL2(EG-F2)。(11)

均方根曲率可表示为

C=k12+k222=2H2-K。(12)

3.2 点云精简

以均方根曲率作为点云精简的依据。以第i(i=1,2,…,B)个聚类为例,根据聚类中各点的均方根曲率C_ij(表示第i个聚类中第j个点云数据的均方根曲率),计算出均方根曲率的平均值 C-i,比较C_ij和 C-i的大小:若C_ij< C-i,认为此点曲率过小,所包含的特征信息较少,删除该点;若C_ij≥ C-i,认为此点曲率过大,所包含的特征信息较多,保留该点。

4 实验与结果分析

4.1 分类组数对点云精简的影响

利用k-means聚类方法,需要先确定分类组数。本文先分析分类组数对点云精简的影响。以斯坦福大学三维扫描库中的bunny为原数据,点云个数为161032,在Matlab中编写相应的程序,分别设置分类组数为1000、2500、5000、10000、20000,得到精简后的点云数据,导入到Geomagic中,建立相应的模型,分别计算其与原始点云数据模型的标准偏差,计算结果如图1所示(表中压缩率是剩余点云个数与原点云数据的比值)。

图 1. 不同分类组数下的压缩率和标准偏差

Fig. 1. Compression rates and standard deviations for different numbers of clusters

下载图片 查看所有图片

图1采用此方法精简数据,压缩率相对较低,但是却能很好地保存特征点,模型表面也较光滑。随着聚类组数的增加,标准偏差整体上呈下降趋势。当聚类组数为1000~5000时,压缩率会下降;当聚类组数为5000~20000时,压缩率会上升。分析原因:当聚类组数初始增加时,每组中的点云个数减少,且点云曲率差异较小,所以保留的点云数据会减少;当聚类组数继续增加时,每一聚类中至少保留一个点云数据,因此保留的点云数据会随着聚类组数的增加而增加。

4.2 k-means与现有方法的对比分析

由于本文选用的数据曲率变化较小,相比于随机采样法和曲率采样法,包围盒法进行点云精简处理效果较好。因此,为证明k-means聚类方法的可行性,将其与包围盒算法进行对比分析。

4.2.1 三维模型比较

当压缩率分别近似等于0.235和0.154时,将点云数据导入Geomagic软件中,利用同一种方法建模,比较两种方法的标准偏差、全图和头部细节展示图,如图2所示。

图 2. 两种方法的标准偏差和建模结果

Fig. 2. Standard deviations and modeling results for two methods

下载图片 查看所有图片

从图2可以看出,当两种方法的压缩率近似相等,甚至本文方法的压缩率相对低时,本文方法的标准偏差更小,而且压缩率越小,两种方法的标准偏差差值越大,说明本文精简点云数据的方法越有优势。对比两种方法的模型,本文方法构建的模型更加光滑,特征保留效果也更好,而包围盒法构建的模型表面较粗糙,在细节展示图中很难分辨出兔子的眼睛和嘴,精简效果差。

4.2.2 精度评定

精度评定方法主要有3种:表面积法、体积法和切面法。为了进一步说明本文方法在保留细节上的优势,利用切面法处理点云数据。切面法是取任何一平面切割原来的三角格网,将所形成的交线和交点投影到平面上进行比较,一般选择交点^[12]。选取两个平面截取点云数据,将两平面之间的点云数据投影到同一平面上进行比较。在细节展示图中可以看出,脸部数据变化较明显,所以选取脸部的数据进行比较,得到的数据如图3所示。

图 3. 切面法投影后的点云数据

Fig. 3. Point cloud data after projection by section method

下载图片 查看所有图片

图3中点云数据是通过投影得到的,所以存在点云密集和稀疏的地方。当压缩率近似相等时,本文算法得到的点云数据与原始数据的稠密稀疏分布更加一致,而包围盒法得到的点云数据稠密稀疏比较均匀,与原始数据分布不一致。在原始数据中存在一些弯曲部分,本文算法得到的点云数据也在相应位置存在弯曲部分,而包围盒法得到的点云数据较平滑,点云弯曲部分不明显。随着压缩率的降低,本文算法依然可以保留细节特征,而包围盒法的点云数据平缓,未能很好地保留特征数据。

5 结论

基于k-means聚类方法提出了一种新的点云精简方法。利用k-means聚类方法对点云数据进行分类,在每类中利用曲率来精简点云数据。同时,分析了不同分类情况下点云精简的效果,并在压缩率近似相等的前提下,与包围盒法进行比较。结果发现,本文算法能较多地删减点云中的冗余数据,且较好地保留点云特征信息。