江南机电设计研究所 贵州贵阳 550009
摘要:由于模糊C均值聚类算法容易受到参数和噪声的影响,同时没有考虑点云数据空间信息,导致聚类分割结果不够准确等问题。本文利用点云法向量,提出了基于法向量加权的模糊C均值算法并且证明其算法的收敛性。通过对建筑物点云和手背点云进行聚类分割,实验结果表明:改进算法的实验结果比模糊C均值算法更精确,更具有实际意义。
关键词:点云数据;聚类分析;数据划分;平面拟合;收敛性;
引言 随着信息时代的发展,人们对社会的认知不断加深,真实的场景模型的建立需求也在不断地增加。在三维点云预处理中,点云数据的聚类分割是重要内容,也是三维重建中的基础和前提,点云数据的聚类分割结果也影响着三维重建的效果。点云数据空间结构复杂,数据量大,现有的相关算法只能对特定的点云数据进行聚类分割,且容易受各种因素影响,导致聚类消耗时间长,聚类结果达不到要求。因此三维点云的分割算法也在不断地研究探索中。
1 模糊C均值算法
在现有的目标函数聚类算法里,FCM算法的理论是最为完善且应用也最为广泛。使用均方逼近理论构造带约束的非线性的规划函数实现了目标函数法解决聚类问题,从此成为聚类目标函数的普遍形式。
在模糊聚类分析算法中,FCM聚类算法因其计算简单,运行速度快等优点,故应用也最为广泛。但FCM聚类算法也有如下问题,例如初始聚类中心的有效性、聚类数c以及初始隶属矩阵U的寻找等。
2 基于法向量加权的FCM算法(NFCM)
设点云数据为,每个包含三维坐标信息。即. 使用数据划分中的方法对点云数据进行划分,把数据划分为j部分,对点云数据进行平面拟合,求得j个平面方程以及。把平面方程以及法向量分别赋给方格内的点云,此时,,计
对传统的FCM算法加权,目标函数为:
(1)
式中为平滑指数,是隶属矩阵并且满足(2)式
(2)
考虑到可能会等于0,为使得为最小,可以使的值为:
(3)
聚类中心的更新公式为:
(4)
2.1 基于法向量加权的FCM算法收敛性分析
改进算法最小化就是隶属度矩阵和聚类中心的彼此影响不断优化的过程。在这个过程中,就会产生一系列的聚类中心和隶属度矩阵。每一次迭代就会产生一组聚类中心和隶属度矩阵的集合。这个集合就可看成一个点向一个点不断逼近的过程。
这里:
由上述定义可知,
若,有且则称是改进的一个迭代数列。
引理2.1令B表示一个距离空间,称一个点到集合的映射在点是闭的,如果当
时,必然有.
引理2.2(Zangwill定理)令B表示一个距离空间,给定一个点,由点到集合的映射定义一个算法,且产生一个序列令表示解集,假如:
1、所有的点属于B中的一个紧子集。
2、存在一个连续的函数使得:
(a)若,则对任何,有.
(b)若,则算法终止或者对任何,有.
3、若,映射A在Z点是闭的。
那么算法终止于一个解,或任何一个收敛的子序列的极限为一个解。
定理2.1 设模糊系数,数据个数,令表示的初始迭代点,
那么,迭代序列终止于,或者存在1个子序列收敛于中的一个点。
证明:函数在是关于的连续函数,迭代数列是一个有界数列且包含于的一个紧子集中。在应用Zangwill定理和魏尔斯特拉斯定理,有界数列必含有收敛子列可知迭代序列终止于,或者存在1个子序列收敛于中的一个点。又因为函数在是关于的连续函数,所以函数具有收敛性。由此可知改进算法具有收敛性。
3 实验结果及分析
为了验证改进算法的有效性以及收敛性,本文采用了建筑物点云数据进行实验。
图1是改进算法和原始算法针点云聚类的收敛图,两个算法都是针对同一组教学楼建筑非边缘点云数据进行实验。在图中,迭代次数在10次之前就可以看出NFCM算法比FCM算法的收敛速度快, NFCM算法大概在12次左右开始趋于稳定,52次迭代达到收敛阀值的终止条件。在图中FCM算法在60次左右才开始趋于稳定,83次迭代才达到收敛阀值的终止条件。以上所述,可以看出改进算法的收敛性以及可行性都要比FCM算法优。
图1 两算法迭代收敛对比图
表1 NFCM算法和FCM算法对比表
有效性指数 | FCM | 改进 |
0.5424 | 0.5603 | |
0.9228 | 0.8917 | |
0.1527 | 0.1073 |
从表1中可以看出当聚类数为5,模糊加权参数为2,收敛阀值为时,改进算法的划分系数高于FCM算法的划分系数,改进算法的划分熵低于FCM算法的划分熵,同时改进算法的有效性函数小于FCM算法的有效性函数,由此可以知道改进算法的聚类结果优于FCM算法的聚类结果。
4 结论
本文提出的基于法向量加权的FCM算法,用于点云数据的聚类分割,实验证明本文改进的NFCM算法要优于FCM算法,聚类分割的结果也比FCM算法分割的结果更有实际意义。在NFCM算法的实验结果中也发现聚类结果还是出现了欠分割的现象,还有待改进。但是从整体分割结果看,NFCM算法还是可取的,整体分割结果优于FCM算法。
参考文献:
[1]何栋,唐婷.基于模糊C均值聚类算法的碳纤维木质复合材料图像分割[J].合成材料老化与应用,2020,49(04):78-80.
[2]高云龙,王志豪,潘金艳,罗斯哲,王德鑫.基于自适应松弛的鲁棒模糊C均值聚类算法[J].电子与信息学报,2020,42(07):1774-1781.
[3]化春键,孙康康,陈莹.基于改进FCM聚类的网孔织物图像分割算法[J].光电子·激光,2020,31(08):857-864.