王平禄 董昱威
摘 要:聚类算法在图像分割领域有广泛的应用,本文通过对四种聚类算法的介绍与分析,深入了解其算法原理,以及其在图像分割领域中的应用效果,通过四种的算法的比较,总结出了各个算法的优缺点。
关键词:聚类算法;K均值;模糊聚类;均值漂移;近邻传播算法
随着信息技术的高速发展,人们每天都处理大量的图像信息,然而,不是图像中的所有信息都是我们需要的,所以,这就需要我们进一步对图像进行处理,得到能够满足人们需要的信息。这就需要我们通过技术手段把图像中特定的信息从整体中分割出来,这便是图像分割,即将输入的图像分割成若干有意义的目标区域[1]。近年来,聚类算法在图像分割中有着广泛的应用。目前比较经典的聚类算法有:K均值聚类,模糊聚类,均值漂移算法,近邻聚类算法。
1 聚类算法
⑴K均值聚类。K均值算法是最经典的聚类算法。由于其简单高效,是应用最广泛的聚类算法。它的基本思想是:预先设定K类,随机选中K个元素作为每一类的中心。计算其它元素与K个中心之间的聚类,根据距离的大小,归入距离最小的类中。然后重新计算每一个类的中心值,即所有类中元素的平均值,得到新的中心值后。再次重新分类,不断重复此过程,直到目标函数收敛。通常定义的目标函数为:
式中:p为对象空间中一个数据对象;mi为类ci的均值。
⑵模糊聚类。模糊聚类算法是由K均值聚类算法发展而来的。它的基本思想是:把所有元素分为C个模糊聚簇,求出每个簇的中心,使得非相似性指标的函数达到最小值。它在确定每一个元素时,不是K均值非0即1,而是使用0~1之间的数字来赋予元素隶属于某一簇的程度。它的目标函数为:FCM聚类算法目标函数为:
式中:Xj表示样本;N表示样本数目,通常表示图像像素数;C表示聚类数目; 是矢量Xj隶属于第i类的隶属度函数,满足uij∈[0,1]且 ;Z表示聚类中心。
⑶均值漂移算法。均值漂移是一种不需要参数的无监督聚类方法。它的主要思想是,在概率空间中求解概率密度极值的最优算法。它让每一个点漂移到密度函数局部最大值出,即均值漂移向量的方向是数据的密度梯度估计方向一致。[2]文献[3]中对均值漂移算法原理的描述如下:假设核函数H如果满足一定的统计矩约束概率密度函数,可以用于非参数概率密度估计,若样本集{xi}n是依密度函数f(x)经过n次独立抽样得到的,则给出的密度函数估计为[4]:
其中,核函数满足:
⑷近邻聚类算法。近邻传播聚类算法是一种基于近邻信息传播的聚类算法,其目的是找到最优的类代表点集合,一个类代表点对应为实际数据集中的一个数据点,使得所有数据点到最近的类代表点的相似度之和最大。如果设数据点的相似度为数据点的欧式距离的负数,则妙算法的目标函数与经典的K中心聚类算法的目标函数一致。近邻传播聚类算法还有两个重要的信息量参数,分别是responsibility和availability,r(i,k)表示从点i发送到候选聚类中心k的数值消息,反映k点是否适合作为i点的聚类中心。a(i,k)则从候选聚类中心k发送到i的数值消息,反映i点是否选择k作为其聚类中心。r(i,k)与a(i,k)越强,则k点作为聚类中心的可能性就越大,并且i点隶属于以k点为聚类中心的聚类的可能性也越大。对于任意数据点xi,计算所有数据点的r(i,k)和a(i,k)。
3 小结
K均值聚类由于其简单高效,是应用最广泛的聚类算法。但是它也有很多局限性,其中聚类类别的数目需要先验知识,而初试聚类中心的选择不同也对聚类最终结果有很大的影响,所以聚类的稳定性欠缺。
模糊聚类算法,也是比较普遍使用的聚类算法。一般情况下不需要人为干预和设定阈值,就可使圖像分割区域自动化。但是模糊聚类数目的确定也是个难题,需要先验知识,而算法本身迭代过程计算量非常大,而算法对噪音比较敏感,所以,时常会出现过分割现象。
均值漂移算法是一种无需任何参数的聚类算法,对噪音有很好的鲁棒性,可以处理任意形状和特征空间的图像,非常适用于真实世界中的图像。但是该算法受核函数的影响比较大,由于核函数参数的设置问题,图像会产生过分割或欠分割现象。
近邻传播聚类算法,相比较其它算法能更快的处理大规模数据,得到较好的聚类结果。它对数据形成的相似矩阵的对称性没有任何要求,所以其应用的范围很大。但是对于一些本书具有复杂结构的数据集,近邻传播算法通常得不到合理的聚类结果。
[参考文献]
[1]Gonzalez Rafael C,Woods Richard E,Eddins Steven L.Digital Image Processing.阮秋琦,等,译.电子工业出版社,2005.
[2]王爽,夏玉,焦李成.基于均值漂移的自适应纹理图像分割方法[J]. Journal of Software,2010,21(6):1451-1461.
[3]沈占锋,骆剑承,胡晓东,孙卫刚.高分辨率遥感影像多尺度均值漂移分割算法研究[J].武汉大学学报(信息科学版),2010,03:313-316.
[4]Comaniciu D, Meer P.Mean Shift: a Robust Approach Toward Feature Space Analysis[J].IEEE Transactions on Pattern Analysis and Machine Intelligence,2002,24(5):603-619.