Corresponding author: PENG Juhuan, E-mail: pengjunhuan@163.com
1 引 言
众多聚类算法中，模糊c-均值聚类算法(fuzzy c-means clustering algorithm，FCM)[1, 2, 3, 4]是人们熟悉的方法之一。作为一种无监督聚类算法已成功地应用在图像分析、医疗诊断、目标识别和图像分割等领域[5, 6, 7, 8, 9]。与硬聚类的k均值聚类算法相比，FCM允许某个样本以不同程度同时隶属于所有类别，采用模糊隶属度描述归属程度，这种思想真实地反映了自然界的模糊性和不确定性，因此聚类效果优于k均值聚类算法。但是传统的FCM聚类算法存在很大的局限性，聚类效果受初始聚类中心的影响很大，算法采用梯度法求解极值，结果往往局部最优；同时应用于遥感影像分类时，传统的FCM算法只考虑了像素的光谱信息，而忽略了像素邻域的空间信息，如果影像存在较大的噪声，分类图像往往出现许多离散空洞或杂乱点。一种解决方法就是先对原始影像进行低通滤波，然后再进行FCM分类。然而这种方式会导致影像细节的缺失，而且没有一种合适的方法在图像平滑和图像特征聚类之间进行有效的平衡。
近年来，国内外许多研究者对如何选择好的初始中心和在顾及像素空间信息的前提下，对传统的FCM算法的目标函数进行了修正，提出了多种修正算法。选择合适的初始值算法包括：直方图方法、模拟退火方法、禁忌搜索法、遗传算法、粒子群算法和蚁群算法等[10, 11, 12]。这些方法尽可能地避免FCM算法陷入局部最优，但是复杂度很高，效率低下。顾及像元空间信息的FCM算法大多数都在标准FCM算法基础上引入邻域信息。文献[13]改进了FCM的目标函数，引入空间约束项，使算法在迭代过程中估计空间平滑的隶属函数。文献[5]将邻域均值项引入目标函数。这两种方法虽然能够很好地克服图像噪声的影响，但是算法每一次迭代都需要对邻域信息进行计算，复杂度高。文献[14]提出修正后的快速FCM算法，该算法对每个像素点进行统计分析，依据这些点的中值、最大值和最小值，自动计算出该邻域各点对中心点的影响权重并以此更新中心点的像素值，这种方法能够很好地保持边缘，但是迭代过程过于复杂。文献[15]将马尔可夫随机场(Markov random fields,MRF)引入到FCM算法中，将像素特征域相似性与空间域相邻性结合起来，改善了图像分割的效果，但是这种方法对初始值敏感，分割结果存在不确定性。上述方法中没有一个既能为FCM算法提供合适的初始值，又能顾及像素空间相关信息，一般都不是完整的分类算法。针对这些情况，本文把非参数核密度函数和马尔可夫随机场引入到FCM算法中，采用第一主成分的核密度函数[16, 17]为FCM算法提供初始值；引入MRF度量空间相关性，并采用模拟数据和实际遥感影像数据来验证本文方法的有效性。
2 基于马尔可夫随机场的模糊c-均值模型 2.1 传统的模糊c-均值模型模糊聚类由Dunn首先提出，并由Bezdek推广为一般的模糊c-均值聚类算法[1, 18]。该算法通过最小化一个二次目标函数(1)来实现图像的优化分类
根据拉格朗日极值法得到目标函数(1)取得条件极值的必要条件为
式(1)中，I(i,j)为(i,j)位置像元的灰度值；vk为第k类的均值；μk(i,j)为像元点(i,j)隶属第k类的隶属度；C为分类数；q为控制聚类结果模糊度的参数，一般取[1.5,2.5]之间的数；‖·‖为欧氏距离；
μk(i,j)q=1。迭代更新式(2)和(3)直到聚类中心
<ε。
马尔可夫随机场(Markov random field，MRF)对二维影像空间中的邻域相关关系有着良好的描述能力[18, 19]。在MRF理论中，图像指标集s中的像素点的空间关系通过邻域系统N={Ni,i∈S}来体现。
根据Hamersley-Clifford定理[19]，MRF分布可以等效地刻画为Gibbs随机场分布
式中，Z=
exp(－U(x))为配分函数，是正则化常量；U(x)是能量函数，其表达式为U(x)=
Vc(x)，其中Vc(x)为势团C上的函数。能量函数属于非凸函数，如果要获得全局最优解可以使用模拟退火、遗传等算法，但计算时间成本比较高。本文采用了ICM(iterated conditional modes)算法，以获得局部最优解。
设像元I(i,j)的邻域为N(i,j)，如果点(i,j)某类发生的概率为pk(i,j)，则其邻域对其标记的拒绝概率为1－pk(i,j)。据此将目标函数(1)修正为[18]
式中,pk(i,j)为在邻域N(i,j)作用下，将点(i,j)标记为第k类的概率。采用拉格朗日极值法求得式(5)取极值的必要条件为
从上面过程中可以看出，改进的算法即包含像素特征域信息，又融入了局部邻域中的分类信息，因此可以有效地抗击噪声的干扰。MRF模型有多种形式，如MLL(multi-level logic)、GMRF(Gaussian Markov random field)模型[19]等。在图像分割中，大多数基于MRF模型使用MLL模型来表示分类标签的先验分布。假定MLL模型是二阶的，则其势函数可以表示为
式中，i是一像素；i′是一相邻像素；S是像素空间；Ni是像素i的邻域集合。并且
式中，I为一类标签；αI和βc是子团参数，在本文中都取1。可以看出模型与具体的像素值无关，只与一个基团内的像素之间的空间位置有关，因此很好地描述了图像纹理。
算法步骤：① 对数据进行数据变换(对数或指数变换)后，进行主成分分析(针对多波段和高光谱数据)；② 依据原始数据(单波段数据)或者第一主成分的核密度函数图像确定初始分类数和分类中心；③ 采用传统FCM算法确定初始分类，为改进的FCM提供初始参数；④ 计算每个点的邻域；⑤ 依据式(6)和式(7)更新隶属度和聚类中心，直到聚类中心V的变化小于阈值ε(ε>0)。
3 试验结果与分析为了验证本文提出的算法相对于传统FCM算法的优越性，本文设计了两组试验。第1组采用模拟灰度图像，以便于对算法的分类效果进行定量分析；第2组采用真实的多波段遥感影像，进一步对算法进行评价。
3.1 模拟灰度图像图 2是由Gibbs Sampler生成的模拟灰度图像[19]，图像大小为512像素×512像素。把图像分成4块，分别加入高斯噪声(均值：0，方差：0.01)、泊松噪声(均值：140)、斑点噪声[20](均值：0，方差：0.04)和盐椒噪声(加入5%的盐椒噪声)；图 3为加入噪声后的图像(左上为高斯噪声，左下为斑点噪声；右上为泊松噪声，右下为盐椒噪声)。图 1为含噪声图像的核密度函数图像；依据图 1可以得到初始分类数为3和初始分类中心为[55 110 225]。分别采用传统FCM和改进后的FCM算法进行分类，结果如图 4和5所示。
|
| 图 1 含噪图像的密度函数图(横轴表示灰度值，纵轴为概率密度值) Fig. 1 Density function of the contaminated image |
|
| 图 2 Gibbs Sampler模拟图像 Fig. 2 The simulated image based on Gibbs Sampler |
|
| 图 3 噪声污染后的图像 Fig. 3 The contaminated image |
|
| 图 4 传统FCM分类结果图像 Fig. 4 FCM clustering image |
|
| 图 5 本文算法的分类结果图 Fig. 5 Markov-FCM clustering image |
从分类结果图像4、5和表 1可以看出，改进的FCM算法优于传统FCM算法，改进的FCM算法结果图像是平滑的。该方法对泊松噪声和盐椒噪声有很好的抑制作用，对高斯噪声和斑点噪声点比较密集的区域存在误判。本文方法依据核密度函数确定分类初始值，避免随机选择初始中心，逐步迭代寻找最优中心的过程，因此分类效率提高了34%。
试验区主要地类包括绿地、水体、道路、裸地、居民建筑用地等。试验采用的遥感影像是QuickBird数据(图 6所示)，2004-03-17日获取。图像大小为300像素×300像素，空间分辨率为2.44m，有4个波段(蓝光波段、绿光波段、红光波段和近红外波段)。
|
| 图 6 原始图像 Fig. 6 Original image |
采用传统FCM方法的分类结果如图 7所示；采用改进FCM算法的分类结果如图 8所示；采用stratified random随机布点方式选择采样点[21]，建立混淆矩阵，计算总体分类精度和Kappa系数，如表 2所示。
|
| 图 7 传统FCM分类图像 Fig. 7 FCM clustering image |
|
| 图 8 本文算法的分类结果图 Fig. 8 Markov-FCM clustering image |
从图 7和8可以看出，传统的FCM算法获得分类图质量较差，分类结果存在离散空洞和杂乱点，再次证明了传统FCM 方法的不足。从原始图像随机选择500个像元点，通过目视判断，得到混淆矩阵，求得分类精度[21](表 2)，改进后的FCM分类结果的总体分类精度优于传统的FCM 7%。
这个试验中，根据第一主成分的密度函数图(图 9(a))确定初始分类数(6类：绿地1、绿地2、房屋、裸地1、裸地2和水域)和类别几何中心[-1 -0.5 0.3 0.8 1.8 2.2]，避开了随机选取初值，可以给最终的类别中心提供一个近似值，减少了迭代次数，保证了分类结果的稳定性，因此提出的方法是一种快速分类方法。
|
| 图 9 对数变换后各个主成分密度函数图 Fig. 9 Density function of Log-principal component transformation |
遥感影像某点像素值与其类别标签和它周围像元的像素值与标签有一定关系，遥感卫星成像时受到噪声的影响，采用FCM算法进行分类时，由于仅考虑了像素值，忽略了像素邻域的空间信息，最终得到的分类图像存在误分现象。因此构建一个既考虑像素值又顾及像素的空间相关信息的FCM算法是必要的。本文提出了改进的FCM算法，采用对数变换后的第一主成分的密度函数图确定初始分类数和初始分类中心，避开了随机选择初始值；把马尔可夫随机场引入到传统的FCM算法，引入邻域分类信息作为像素分类的空间约束，这样既考虑了像素的波谱信息，又顾及了像素间的空间相关信息，有效地抑制了噪声的影响。通过本文理论分析与实际算例验证得出结论：所构造的改进的FCM算法是可行的，能够改善分类精度。
| [1] | BEZDEK J C.Pattern Recognition with Fuzzy Objective Function Algorithms[M].New York:Plenum Press,1981. |
| [2] | KRISHNAPURAM R,KELLER M.Possibilistic Approach to Clustering[J].IEEE Transactions on Fuzzy Systems,1993,2(1):98-110. |
| [3] | PAL N R,PAL K,BEZDEK J C.A Mixed c-means Clustering Model[C]//Proceedings of the 6th IEEE International Conference on Fuzzy Systems.Barcelona:IEEE,1997:11-21. |
| [4] | CHENG T W,GOLDGOF D B,HALL L O.Fast Fuzzy Clustering[J].Fuzzy Sets and Systems,1998,93(1):49-56. |
| [5] | AHMED M N,YAMANY S M,MOHAMED N,et al.A Modified Fuzzy c-means Algorithm for Bias Field Estimation and Segmentation of MRI Data[J].IEEE Transactions on Medical Imaging,2002,21(3):193-199. |
| [6] | LI X,LI L,LU H,et al.Inhomogeneity Correction for Magnetic Resonance Images with Fuzzy C-mean Algorithm[C]//Proceedings of SPIE,Medical Imaging 2003:Image Processing.San Diego:[s.n.],2003:995-1005. |
| [7] | SRINIVASA K G,ENUGOPAL K R V,PATNAIK L M.Feature Extraction Using Fuzzy c-means Clustering for Data Mining Systems[J].International Journal of Computer Science and Network Security,2006,6(3):231-236. |
| [8] | HATHAWAY R J,BEZDEK J C.Fuzzy c-means Clustering of Incomplete Data[J].IEEE Transactions on Systems,Man,and Cybernetics,Part B:Cybernetics,2001,31(5):735-744. |
| [9] | WU Lin,GUO Dayong,SHI Keren,et al.Modified Fuzzy c-means Algorithm for Image Segmentation in Brain Magnetic Resonance Images[J].Journal of Tsinghua University:Science and Technology,2004,44(2):157-159).(吴林,郭大勇,施克仁,等.改进的FCM在人脑MR图像分割中的应用[J].清华大学学报:自然科学版,2004,44(2):157-159.) |
| [10] | KUANG Tai,ZHU Qingxin,SUN Yue.Research on Initialization of Image Segmentation with FCM Algorithm[J].Journal of Computer Applications,2006,26(4):784-786.(匡泰,朱清新,孙跃.FCM算法用于灰度图像分割的初始化方法的研究[J].计算机应用,2006,26(4):784-786.) |
| [11] | NIU Qiang,XIA Shixiong,ZHOU Yong,et al.Improved Fuzzy c-means Clustering Algorithm[J].Journal of University of Electronic Science and Technology of China,2007,36(6):1257-1230.(牛强,夏士雄,周勇,等.改进的模糊c-均值聚类方法[J].电子科技大学学报,2007,36(6):1257-1230.) |
| [12] | FAHRMEIR L,TUTZ G.Multivariate Statistical Modeling Based on Generalized Linear Models[M].New York:Springer-Verlag,1996. |
| [13] | PHAM D L,PRINCE J L.Adaptive Fuzzy Segmentation of Magnetic Resonance Images[J].IEEE Transactions on Medical Imaging,1999,18(9):737-752. |
| [14] | SZILÀGYI L,BENYÓZ,SZILÀGYI S M,et al.MR Brain Image Segmentation Using an Enhanced Fuzzy c-means Algorithm[C]//Proceedings of the 25th Annual International Conference of the IEEE Engineering in Medicine and Biology Society.Cancun:[s.n.],2003:724-726. |
| [15] | CAI Tao,XU Guohua,XU Xiaolong.Image Segmentation Based on FCM and Markov Random Fields[J].Computer Engineering,2007,33(20):34-37.(蔡涛,徐国华,徐筱龙.基于模糊c-均值与Markov随机场的图像分割[J].计算机工程,2007,33(20):34-37.) |
| [16] | BOWMAN A W,AZZALINI A.Applied Smoothing Techniques for Data Analysis[M].Oxford:Oxford University Press,1997. |
| [17] | YANG Honglei,PENG Junhuan,LI Shuhui,et al.Log-principal Component Transformation Based EM Algorithm for Remote Sensing Classification[J].Acta Geodaetica et Cartographica Sinica,2010,39(4):378-382.(杨红磊,彭军还,李淑慧,等.基于对数-主成分变换的EM算法用于遥感影像分类[J].测绘学报,2010,39(4):378-382.) |
| [18] | WANG Shunfeng,ZHANG Jianwei.Brain MR Image Segmentation Based on Anisotropic Gibbs Random Field and Fuzzy c-means Clustering Model[J].Computer Applications,2008,28(7):1750-1752.(王顺凤,张建伟.基于Gibbs场与模糊c-均值聚类的脑MR图像分割[J].计算机应用,2008,28(7):1750-1752.) |
| [19] | LI S Z.Markov Random Field Modeling in Image Analysis[M].Berlin:Springer-Verlag,1995. |
| [20] | EOM K B.Speckle Noise Removal by Robust Modeling[J].Proceedings of the 2003 International Conference on Image Processing.Barcelona:[s.n.],2003:165-168. |
| [21] | STEHMAN S V.Estimating the Kappa Coefficient and Its Variance under Stratified Random Sampling[J].Photogrammetric Engineering and Remote Sensing,1996,62(4):401-407. |