基于KFCM的三维点云精简算法

林 楷，王威娜,2*

(1.吉林化工学院 信息与控制工程学院，吉林 吉林 132022；2.吉林化工学院 理学院，吉林 吉林 132022)

近年来，随着计算机视觉相关产业的蓬勃发展，三维点云重构逐渐被应用在自动驾驶[1]、智能工业[2]、文物修复[3]等各个领域.在点云信息的获取过程中，传统的点云采集设备采用非接触的方式以激光雷达、TOF相机等对现实世界中的物理模型进行扫描，不可避免地产生大量的噪音、冗余信息点，对后续点云重构步骤产生较大影响.因此，选择合适的算法对点云进行预处理显得尤为重要.

在精简算法的研究中，较为主流的是包围盒法、均匀采样法和曲率采样法.Lee等[4]利用形态算子与点云结构相结合将点云进行精简化处理，结果保证了初始信息点的基本结构特征，但此方法在遇到具有干扰的噪声数据集时，鲁棒性较低，易造成输出点云的特征缺失.Wang等[5]通过处理均匀采样点云数据来精简点云模型，在不同数据集上取得了良好的结果，但当点云数据特征不够明显或点云数据较为稀疏时会产生点云空洞.王玉国等[6]将点云的曲率信息作为保留点云的约束条件，根据曲率变化程度的不同对不同密度的点云数据进行保留，此算法缺陷在于对点云的细节保留度不足，且曲率计算造成了算法较高的时间复杂度.

针对上述精简算法出现的问题，本文提出一种基于核模糊C均值(Kernel Fuzzy C Means,KFCM)的点云精简算法.将模糊聚类的思想与点云精简相融合，利用三维点云数据作为输入样本，通过迭代求解样本数据集的聚类中心，并以此聚类中心描述点云结构.在此基础上，算法可通过调节聚类个数灵活输出不同精简程度的点云信息，以适应后续配准工作的需求.该算法实现原理简单，在良好保留点云细节特征的同时达到简化点云的目的，提升后续点云的配准效率.

1 核模糊C均值算法

KFCM[7]是一种改进的模糊C均值(Fuzzy C Means,FCM)聚类算法.FCM[8]聚类模型可被描述为以下步骤：(1) 给定初始隶属度矩阵；(2) 更新模糊聚类中心；(3) 更新隶属度矩阵.循环执行上述步骤(2)和(3)，直至利用加权误差平方和构造的目标函数收敛，输出最终的聚类中心，完成聚类任务.

KFCM通过核函数将原始空间中的点映射到特征空间中，算法首先设数据集X∈Rs，定义其到特征空间的映射为：

f(x)=y.

(1)

G(x,x′)=G(y,y′)=〈f(x),f(x′)〉.

(2)

其中x、x′∈X为s维向量；G为计算两者的欧式内积，进而通过核函数定义FCM中的距离函数，定义目标函数如下：

(3)

其中H代表范数的处理方式；K(xj,vi)代表高斯径向基函数，其形式表示为：

(4)

U=[uij]代表隶属度矩阵；V=[vi]为聚类中心，其更新方式为：

(5)

(6)

式中，m为模糊指数；xj为聚类信息点.循环执行上述步骤直至目标函数达到收敛，聚类的过程如图1所示.

图1 聚类示意图

在聚类分配过程中，可利用之前获得的聚类信息将数据进行聚类分配，待分配数据可根据第s-1次聚类分配获得其对应的聚类中心.在得到分配区域后，通过隶属度矩阵估计数据点对应的新的聚类中心，即可得到s次迭代所需的隶属度矩阵，进而更新聚类分配.在分配的过程中，同一数据点可能在不同迭代次数时被分配于不同的聚类中心，随着目标函数的逐渐收敛，其函数值逐渐减小，直至聚类过程结束.

2 基于 KFCM算法的点云精简方法

2.1 基于 KFCM算法的点云精简方法

提出的基于KFCM的点云精简算法首先将未精简的点云数据作为输入样本，通过核函数将初始点云数据集在特征空间中进行描述，利用线性函数对稠密点云数据进行划分.聚类分配的步骤中，聚类中心构成的点云信息可对整体点云信息进行描述，通过本次迭代的聚类中心计算下次迭代所需隶属度矩阵，最后将聚类中心作为输出点集样本数据，算法流程如图2所示.

图2 算法流程图

输出后的点集极大地减少了原点样本的数据量，达到了优化后续配准算法输入信息的目的.在此基础上，将模糊聚类中心个数h为精简后三维点云数据量的描述符，利用保留点与初始信息点个数的比值表示精简率，即可通过调节h的数值对精简后点云疏密程度进行控制，以适应后续配准工作的需求.

综上所述，基于KFCM的三维点云精简算法具体执行步骤为：

步骤1：利用径向基函数将三维点云数据映射到高维空间；

步骤2：提供聚类个数，初始化隶属度矩阵；

步骤3：根据数据分布情况进行聚类划分，获得初始聚类中心

(7)

式中Pij用于描述第i个点集中第j个信息点；uij表示其信息点的隶属度矩阵；m为模糊系数，默认参数值为2；

步骤4：更新隶属度矩阵

(8)

步骤5：循环更新聚类中心与隶属度矩阵，直至迭代达到预设次数，将聚类中心作为精简后数据输出.

2.2 多视角三维点云配准

三维点云的配准是指将不同视角的三维点云数据利用刚性参数变换使其同步至同一坐标系下的更新过程，三维点云配准示意图如图3所示.

图3 三维配准示意图

Zhu等[9]利用聚类思想描述三维点云模型从而恢复对齐的三维点云结构，算法首先给定初始变换参数，再利用下采样对三维点云数据进行精简处理，通过K均值聚类选出聚类中心.将整体点云对齐到由聚类中心组成的分辨率较低的模型上，利用此对应关系进行点云的旋转与平移变换，以求在迭代更新聚类中心的同时优化刚性变换参数，具体执行步骤如下：

步骤1：更新聚类.

a.设聚类数为K，对精简后点云进行随机采样，选出K个聚类中心{v1,v2,…,vK}；

b.根据欧氏距离最短的原则将每个点分配到相应类中；

c.更新聚类中心：

(9)

其中Qij为点Pij的类标；N为信息点个数；M为点集个数.

步骤2：更新刚性变换参数(R,t).

a.计算第i个视图的刚性变换参数(R,t):

(10)

在刚性变换参数的求解过程中，采用奇异值分解(SVD)[10]方法，求解源点云与目标点云的加权中心，在去中心化操作后计算其协方差矩阵W，奇异值分解此矩阵即可得到U、V两个酉矩阵，则旋转矩阵R可被表示为：

R=UVT.

(11)

再据此估计平移向量t的具体数值.

b.利用求得的R、t对各个视图进行变换：

(12)

基于K均值聚类的三维点云配准方法在进行源点云与目标点云的特征提取过程中较为简单地利用下采样对不同视角点云进行预处理，在一定程度上降低了算法的鲁棒性.实验过程中，利用基于K均值聚类的三维点云配准方法对本文提出的算法进行了验证，实验表明通过基于KFCM的三维点云精简算法对原始稠密三维点云数据进行预处理，可减少噪声与冗余信息对配准算法的影响、弥补K均值聚类对噪声敏感的不足，提升了算法的准确性.

3 实验结果与分析

为验证算法有效性，实验具体分为两部分：(1)不同参数下的点云精简测试；(2)与后续配准算法的适用性实验.实验设备为64位Windows操作系统，CPU频率为2.40GHz，运行内存为8GB的电脑，使用的编程软件为Matlab.使用数据集分别为ModeNet40[11]以及斯坦福大学数据库[12].

3.1 不同参数下的点云精简测试

为验证KFCM的点云精简方法的有效性，首先对Airplane模型进行精简实验，实验将初始点云利用不同精简参数处理后结果如图4所示.

图4 不同精简参数下的Airplane模型

实验结果显示，输出点云样本数据随着精简参数h的增加而逐渐减小，但精度与特征信息并未损失.由此可通过改变聚类的参数用以控制精简后信息点的密度，灵活调节三维点云的精简率.

与此同时为验证算法在处理含噪点云时的滤波效果与精简后点云保留程度，对Flowerpot模型进行测试，在原模型中添加2%的随机噪声，实验中遗传算法的步长设置为20，结果如图5所示.

图5 不同精简参数下的Flowerpot模型

结果表明在精简比率为12.5%与5%的情况下，算法有效地将含噪点云去除了所有噪声点，并有效地对原点集进行了稀疏，点云部位轮廓清晰.模型预处理前点云稠密，经过算法精简处理后各部位细节明显，很好地保留了原模型的特征.

在实验中，为了更直观地描述算法对三维点云模型整体结构的细节保留程度，表1给出了Airplane及Flowerpot模型在精简率为12.5%情况下的精简误差与下采样精简方法的精度对比.实验以不同邻域划分范围的平均法向量作为衡量标准，表中x_normal、y_normal、z_normal分别表示模型在x、y、z轴方向的平均法向量误差，其中最优结果已用黑体标出.

表1 精度误差对比

由表1可知，提出的算法在不同邻域覆盖情况下的不同方向法向量误差较低，相比于下采样精简方法，基于KFCM的点云精简算法在各方向上点云结构信息保存良好，具有更高的准确性，并给出在不同精简参数下，Airplane模型保持率与点云平均密度变化的对照表2.

表2 平均密度对照表

如表2所示，在聚类参数由1至90的变化过程中，三维点云数据保持率不断降低，实验点云模型逐渐稀疏，点云间的平均间距随之增加.由此可见，在算法的实现过程中，可通过调节精简参数h以灵活控制输出点云的疏密程度.

3.2 精简后配准结果测试

为验证精简后的点云数据对后续配准任务的适用性，利用基于K均值聚类的点云配准方法与ICP[13]算法对其进行测试，并给出待配准点云的具体信息，如表3所示.

表3 待配准点云信息

3.2.1 基于K均值聚类的点云配准方法

在验证过程中，实验选取Bunny、Buddha模型进行效果测试，在给定初始变换矩阵后，使用基于KFCM算法的点云精简方法的输出结果作为初始聚类中心的描述符，实验中迭代次数设置为200，算法运行迭代次数小于预设次数之前，不断迭代，直至收敛.图6和图7为Bunny、Buddha模型经过KFCM精简后利用基于K均值聚类的点云配准方法配准前后的对比图.

图6 Bunny配准结果

图7 Buddha配准结果

如图6和7所示，精简后的多站点云配准效果良好，经配准的点云边缘清晰、特征部位明显.Buddha截面图可见佛像的身体与底座部位未对齐的部分经刚性变换后得到了完美的还原，初始点云截面图层次较为混乱，配准处理后的佛像模型边界平滑、结构保存良好.Bunny中双耳、腹部以及背部未对齐的部分配准精确.截面图可见模型躯体重影部分配准效果明显.由此可见，基于 KFCM算法的点云精简方法可较好地适应基于聚类的三维点云模型精确配准任务需求，算法可移植性较高.

3.2.2 ICP配准效果测试

在ICP配准效果测试实验中，选取精简率为12.5%的Guitar以及Flowerpot模型进行适应性测试，在给定初始的变换矩阵后，进行最近点迭代估计，图8和图9给出配准中的运行时间、迭代次数与配准误差.

迭代次数n图8 Guitar ICP配准结果

图9 Flowerpot ICP配准结果

如图8和图9所示，针对不同模型，精简后的三维点云数据可良好地适应迭代最近点算法的处理步骤，在给定初始误差的情况下可对原模型进行精确的配准处理.待配准Guitar模型得到较好的拟合，Flowerpot模型配准后边缘整齐、细节特征配准精确，迭代均方根误均小于0.05 m.在点云结构保存方面：迭代最近点算法是基于点云特征的精配准算法，迭代收敛次数在一定程度上反映了点云模型对整体结构的描述程度，两模型5～10次迭代后即可达到收敛，可见基于 KFCM算法的点云精简方法可较好地保持源点云的细节特征.在时效性方面：经过精简后的点云数据处理速度较快,算法耗时不足0.1 s.

综上所述，本文提出的基于 KFCM算法的点云精简方法能较好地处理点云精简任务，在便捷调节点云精简率的同时，具有良好的特征保留性能，提升了后续点云处理任务的效率，故此方法具有较高的实际应用价值.

4 结 论

基于核模糊C均值聚类的思想提出一种针对冗余点云的精简方法，在处理数据量较大的稠密点云数据时具有良好的性能，该方法可在减少点云数据量的同时对模型的细节特征进行保留，且可通过聚类参数h对输出点云的分辨率进行调节.实验结果表明，利用基于K均值聚类算法的点云配准方法与ICP配准算法对精简后的点云进行配准测试时，精简后的点云数据可提升配准效率，且得到的点云模型清晰、边缘光滑、数据点分布均匀.综上所述，提出算法具有较高的实际应用价值.

本文算法虽然可以有效地处理三维点云数据的精简与去噪任务，但存在着聚类参数的选择不够系统、收敛条件设置不够精确等问题，如何系统地选取聚类数量以精确地设置收敛条件将是未来研究的重点.