EN中文

Journal of Geo-information Science >

2014 , Vol. 16 >Issue 5: 769 - 775

DOI: https://doi.org/10.3724/SP.J.1047.2014.00769

Orginal Article

An Algorithm of Remote Sensing Image Clustering Based on Kernel Fuzzy C-Means with Local Spatial Information

  • WU Yiquan , 1, 2, 3, * ,
  • SHEN Yi 1 ,
  • TAO Feixiang 1
Expand
  • 1. College of Electronic and Information Engineering, Nanjing University of Aeronautics and Astronautics, Nanjing 210016, China
  • 2. Key Laboratory of Agricultural Information Technology, Ministry of Agriculture, Beijing 100081, China
  • 3. Jiangxi Province Key Laboratory for Digital Land, East China Institute of Technology, Nanchang 330013, China
*Corresponding author: WU Yiquan, E-mail:

Received date: 2013-07-27

  Request revised date: 2013-12-27

  Online published: 2014-09-04

Copyright

《地球信息科学学报》编辑部 所有
Fold

Abstract

Aiming at the problem that the fuzzy c-means (FCM) algorithm cannot effectively segment remote sensing images with noise, an algorithm of remote sensing image clustering based on Kernel Fuzzy C-Means (KFCM) clustering with local spatial information is proposed in this paper. Firstly, all pixels of a remote sensing image are mapped into a high-dimensional feature space through the kernel function. Different contributions of each feature vector to the clustering results are fully taken into consideration as well. Thus the influence of noise on the clustering results is greatly reduced and the high-dimensional non-clustered data can be divided nonlinearly. Then, the useful features of the remote sensing image are optimized by non-linear mapping. Next, according to the correlation between adjacent pixels, a space function is used to redefine the fuzzy membership of the pixels. Additionally, the local spatial information of pixels is introduced into the FCM algorithm and the pixels are clustered within the high-dimensional feature space by applying the above-mentioned FCM algorithm based on local spatial information. Accordingly, the clustering results are more accurate. Because of the introduction of local spatial information of pixels, the proposed algorithm can be directly applied to the original remote sensing image without filtering preprocesses and its robustness is adequately strong. A large number of experiments are performed and the results show that the proposed remote sensing image clustering algorithm based on KFCM with local spatial information has stronger noise reduction capabilities and can obtain better homogeneous regions. Therefore, the clustering effect of remote sensing image can be further improved. It is superior to the existing algorithms of remote sensing image clustering such as FCM algorithm, Fuzzy Local Information C-Means (FLICM) algorithm and KFCM algorithm. The proposed algorithm lays a good foundation for the next step of high-spatial-resolution remote sensing image processing.

Key words： remote sensing image; image clustering; fuzzy c-means algorithm; kernel fuzzy c-means clustering; local spatial information

Cite this article

WU Yiquan , SHEN Yi , TAO Feixiang . An Algorithm of Remote Sensing Image Clustering Based on Kernel Fuzzy C-Means with Local Spatial Information[J]. Journal of Geo-information Science, 2014 , 16(5) : 769 -775 . DOI: 10.3724/SP.J.1047.2014.00769

1 引言

长期以来,国内外众多学者所提出的图像分类算法,主要分为监督分类和非监督分类2种。常用的非监督分类方法有贝叶斯学习、最大似然度分类以及聚类,其中聚类方法应用较多。聚类算法主要有K-means均值算法[1]、ISODATA[2]算法、主成分分析算法[3]、正交子空间投影方法[4]、模糊聚类[5-9]等。其中,模糊C均值(Fuzzy C-Means,FCM)聚类算法是一种简单有效的聚类算法,在图像分割[10-12]、变化检测[13-15]、图像分类[16-17]等领域有着广泛的应用。其基本原理是按照某种相似性度量和隶属度函数,将相似的样本归为一类,不相似的样本归为不同的类。但FCM聚类算法主要应用在数据挖掘领域,不是针对图像处理,样本之间相互独立的特点使其无法利用图像中像元之间的相关性,这就造成了该算法对图像中的噪声十分敏感。对内容复杂的图像,尤其是高空间分辨率遥感图像,聚类算法就会得到破碎的结果,分割区域在拓扑空间上连通性很差。所以,文献[18-19]在使用聚类算法对遥感图像分割前,应先通过滤波方法降低噪声的影响。文献[20]提出一种模糊局部信息C均值(Fuzzy Local Information C-Means, FLICM)聚类算法,将像元的邻域信息引入传统的模糊C均值(Fuzzy C-Means, FCM)算法中,能高效地去除噪声对分割结果的影响,与经滤波后再采用FCM算法分割图像的方式相比,FLICM算法具有更强的鲁棒性。另一方面,由于FCM算法直接利用未经优化的样本特征进行聚类,导致算法的有效性在很大程度上取决于样本的分布情况。如果样本分布比较混乱,则算法基本失效。随后,通过在FCM算法中引入像元的邻域信息所得到的FLICM算法也存在类似问题。针对这一问题,文献[21]提出一种核聚类算法,增加了对样本特征的优化,通过利用Mercer核,把输入空间的样本映射到高维特征空间后,在特征空间中进行FCM聚类。由于经过了核函数的非线性映射,使原来没有显现的特征凸显出来,从而能够较好地分辨、提取有用的信息,实现更为准确的聚类。因此,如果在模糊C均值聚类中引入核思想所得核模糊C均值聚类算法的基础上,再加入像元的空间邻域信息,将其应用于遥感图像分类,那么,有望进一步提高聚类的准确度和抗噪能力,改善遥感图像的分类效果。
本文针对高空间分辨率遥感图像的特点,提出了一种基于局部空间信息核模糊C均值的遥感图像聚类算法。该算法通过一种模糊的方式将局部空间信息加入到KFCM算法中,不需要滤波预处理,可直接应用于高空间分辨率遥感图像,对噪声不敏感,改善了聚类效果。文中给出了针对农业地区和城郊地区的遥感图像所进行的聚类实验结果,并与现有的FCM算法、模糊局部信息C均值(FLICM)算法及KFCM算法进行了比较。

2 基于局部空间信息KFCM的遥感图像聚类算法原理及步骤

2.1 算法原理

FCM是一种通过迭代以优化目标函数,对数据集合进行模糊聚类的算法。将图像像元灰度值看作是含有N个样本的数据集合 X = x 1 , x 2 , ⋯ , x N ,通过FCM算法将N个像元值聚成c类,可以得到c个聚类中心 { v 1 , v 2 , ... , v c } 和模糊隶属度矩阵U,FCM的目标函数定义为：
J m = ∑ i = 1 c ∑ k = 1 N u ik m d 2 x k , v i (1)
式(1)中, u ik 是第k个样本对于第i类聚类中心的隶属度, u ik ∈ 0,1 且 ∑ i = 1 c u ik = 1 ; { v 1 , v 2 , ... , v c } 表示c个聚类中心; m ∈ [ 1 , ∞ ) 为加权指数; d ( x k , v i ) = x k - v i 表示第k个样本到第i类聚类中心的欧氏距离。
核函数方法是指使用非线性映射把数据从原始样本空间映射到高维特征空间,并在高维特征空间进行相应的线性操作[22-23]。常用的核函数有多项式核函数、高斯核函数和Sigmoid核等,在缺少先验知识的情况下,人们一般选取高斯核函数 K ( x , y ) = exp ( - x - y 2 σ ) 。因为高斯核函数对应的特征空间是无穷维的,故有限的样本在该特征空间肯定是线性可分的。
设原空间样本集为 X = x 1 , x 2 , ⋯ , x N , x k ∈ R d , k = 1,2 , ⋯ , N ,原始样本空间数据 x 到高维特征空间Q的核非线性映射为 Φ ： x → Φ ( x ) , Φ ( x ) ∈ Q ,则高维特征空间中的点积为 K ( x , y ) ≤ Φ ( x ) , Φ ( y ) ≥ Φ ( x ) T Φ ( y ) 。因此,高维特征空间Q中的欧氏距离表达式为 Φ ( x ) - Φ ( y ) 2 = [ Φ ( x ) - Φ ( y ) ] T [ Φ ( x ) - Φ ( y ) ] = K ( x , x ) + K ( y , y ) - 2 K ( x , y ) ,由于采用高斯核函数(选取参数 σ = 500 ), K ( x , x ) = K ( y , y ) = 1 ,所以, Φ ( x ) - Φ ( y ) 2 = 2 - 2 K ( x , y ) 。
因此,KFCM的目标函数 J m 为
J m = ∑ i = 1 c ∑ k = 1 N u ik m Φ ( x k ) - Φ ( v i ) 2 = 2 ∑ i = 1 c ∑ k = 1 N u ik m 1 - K ( x k , v i ) (2)
式(2)中, c 是聚类数目;当用于图像分割时, x k , k = 1,2 , ⋯ , N 表示图像像元灰度值的集合; v i , i = 1,2 , ⋯ , c 是聚类中心的集合; u ik 是第 k 个样本对于第 i 类聚类中心的隶属度, u ik ∈ 0,1 且 ∑ i = 1 c u ik = 1 ;参数 m 为隶属度的加权指数,它决定分类结果的模糊程度。
为使式(2)最小,可求得隶属度 u ik 和聚类中心 v i ,迭代函数如下：
u ik = 1 - K ( x k , v i ) - 1 ( m - 1 ∑ j = 1 c 1 - K ( x k , v j ) - 1 ( m - 1 (3)
v i = ∑ k = 1 N u ik m K ( x k , v i ) x k ∑ k = 1 N u ik m K ( x k , v i ) (4)
相邻像元之间的相关性是图像的重要特征之一,但上述KFCM在聚类的时候只考虑了图像的灰度特征,忽略了图像中丰富的空间邻域信息,所有的样本点都被认为是独立的点,从而导致算法对噪声很敏感,并得到错误的分割结果,降低了分割的准确性。
针对这一问题,可利用一种空间函数将像元的邻域信息引入KFCM中。空间函数定义为：
h ik = ∑ u il (5)
式(5)中, N k 表示以灰度值 x k 的像元k为中心的邻域,取 x k 的8-邻域;l表示邻域 N k 的非中心像元。空间函数 h ik 表示由邻域像元决定的 x k 属于第 i 类聚类中心的可能性。假如 x k 所有的邻域像元点都属于第 i 类,此时 h ik 应取最大值;否则,应取最小值。 u il 是灰度值为 x l 的邻域像元l对于第 i 类聚类中心的隶属度。

2.2 算法步骤

根据上述分析,可将像元的模糊隶属度函数重新定义如下：
u ' ik = u ik p h ik q ∑ j = 1 c u jk p h jk q (6)
式(6)中, p 和 q 是决定2个函数的相关性的参数。参数 p 一定时, q 越大分割结果越好,这是因为增大了空间邻域信息的比重,但是, q 也不能无限增大,否则会导致细节模糊。在同类区域,空间函数仅仅简单地加强了原有的隶属度函数,聚类结果保持不变;然而对于噪声像元,式(6)通过使用邻域像元的空间特性大大地减少噪声点的权重,噪声点得以抑制,纠正了像元的错误分类。新的聚类中心的迭代函数如式(7)所示。
v ' i = ∑ k = 1 N ( u ' ik ) m K ( x k , v i ) x k ∑ k = 1 N ( u ' ik ) m K ( x k , v i ) (7)
本文提出的基于局部空间信息KFCM的遥感图像分割算法的具体步骤如下：
(1)令 ε 为很小的正数, m 为模糊加权指数, T m 为最大迭代次数, c 为聚类数,并初始化聚类中心 v 0 以及迭代次数 t = 0 ;
(2)按式(3)计算每个样本 x k 在特征空间的隶属度函数 u ik ( t ) , i = 1,2 , ⋯ , c , k = 1,2 , ⋯ , N ;
(3)依据式(5)、(6)计算引入像元邻域信息的隶属度函数 u ' ik ( t ) ;
(4)按照式(7)更新新的聚类中心 v ' i ( t + 1 ) ;
(5)算法结束条件为： v ' i ( t + 1 ) - v ' i ( t ) < ε 或 t = T m ,条件满足,算法停止;否则迭代次数t加1,然后转至步骤(2)。

3 算法聚类实验结果与分析

为了验证本文提出的基于局部空间信息KFCM的遥感图像聚类算法的性能,针对农业地区和城郊地区的大量遥感图像进行聚类实验,并与现有的FCM算法、FLICM算法及KFCM算法的聚类结果进行比较。实验运行环境为Intel(R) Core(i3),2.0GHz,2GB内存,Matlab R2009b。参数设置为： m = 2 , ε = 0.1 , T m = 100 , p = 3 , q = 6 。现以上海崇明岛的农业地区、南京城郊、徐州城郊3幅遥感图像及其聚类结果为例加以说明。
由于遥感影像数据量大,数据复杂(地物复杂),因此,需要寻找到合适的分类类别数,以得到更好的分类效果。利用遥感影像分类的模糊有效性指数可以判断该类别数是否有效。常用的模糊聚类有效性指数及其最优判据为：Dunn和Bezdek的划分系数, Bezdek的划分熵,Windham 的比例系数,Dave的修正划分系数,Xie-Beni 指数,KV指数,T指数,Fukuyama和Sugeno的FS指数,PCAES指数和PBMF指数等。
通常,定量化确定分类类别数都要有一定的先验知识。通过目视判读看出研究区域内所包含的基本的地物类型,以确定分类数目。在地面先验知识缺乏的情况下进行遥感影像分类时,可以通过模糊有效性指数来确定分类类别数。Xie-Beni系列指数一般能有效地获得遥感影像最优分类数。在实际应用中, 最优分类数的获得需要根据遥感影像的实际情况来决定。本文根据遥感图像目视解译出所含的地物种类后,直接确定分类类别数。
实验1：图1为一幅上海崇明岛的农业地区遥感图像,原始图像为SPOT5多光谱遥感影像,空间分辨率为10 m,包含绿、红、近红外、短波红外4个波段,实验数据大小为400×600像元。图像中包含了河流、林地、道路、小型建筑物和几种不同类型的农田耕地等。
Fig.1 The remote sensing image of agriculture area

图1 农业地区遥感图像

分别利用上述4种算法对图1进行聚类,类别数设为5,分别为河流、林地、道路、农业用地1和农业用地2,实验结果如图2所示。图2(a)是采用FCM算法所得聚类结果,从图1中看出,不同类型的用地能被较好地区分开,但是椒盐现象非常严重。图2(b)是采用KFCM算法的聚类结果,图像左下角2块用地的椒盐现象得到改善,但是,这2块用地与图像上方的河流被误分为同一类。图2(c)是采用FLICM算法的聚类结果,图2(d)是本文提出的基于局部空间信息KFCM算法的聚类结果,椒盐问题得到了很好地解决,聚类效果较好。这是因为这2种算法都综合了像元的邻域空间信息,可以降低噪声的影响。而且,由于将像元映射到高维特征空间后再聚类,本文算法解决椒盐噪声问题的能力比FLICM算法更强,例如,图像右下方的土地已经形成了一块完整的区域。
Fig.2 The clustering results of remote sensing image on agriculture area

图2 农业地区遥感图像聚类结果

实验2：图3为一幅南京城郊的遥感图像,原始图像为SPOT5多光谱遥感影像,空间分辨率为10m,包含绿、红、近红外、短波红外4个波段,实验数据大小为256×256像元。图像中包含了农田、林地、房屋和道路等。从视觉上看,图中的农田和林地有较为明显的颜色差异,而道路和房屋则颜色分布较为复杂并相近,因此,可将类别数定为3,分别代表建筑、林地和农田。分别利用4种算法对图3进行聚类,实验结果如图4所示。
Fig.3 The remote sensing image of suburban area 1

图3 城郊地区1的遥感图像

图4(a)是采用FCM算法的聚类结果,图中部分农田被误分割为林地,且椒盐噪声情况较严重。图4(b)是采用KFCM算法的聚类结果,除了存在椒盐噪声情况外,有较多的农田被误分割为建筑地。图4(c)是采用FLICM算法的聚类结果,与FCM算法和KFCM算法相比,椒盐噪声问题得到了改善,但是有较多的农田被误分为林地。图4(d)是本文算法的聚类结果,在解决了椒盐噪声问题的同时,聚类结果也比其他3种算法更好,农田、林地都已很好地被区分开,只有少量的农田被误分割为建筑地。之所以道路和房屋被分割为一类,是因为道路和房屋的灰度值非常相近,因此,要想得到单一的目标信息,还需要对聚类结果做进一步处理。
Fig.4 The clustering results of remote sensing image on suburban area 1

图4 城郊地区1遥感图像聚类结果

实验3：图5为一幅徐州城郊遥感图像,原始图像为SPOT5多光谱遥感影像,空间分辨率为10 m,包含绿、红、近红外、短波红外4个波段,实验数据大小为350×350像元。图像中包含了河流、道路、建筑地、林地和农田等。
Fig.5 The remote sensing image of suburban area 2

图5 城郊地区2的遥感图像

分别利用4种算法对图5进行聚类,类别数设为5,分别代表农田、林地、河流、道路、建筑地和裸地,实验结果如图6所示。图6(a)是采用FCM算法的聚类结果,可见该算法已经较好地区分开河流、农田、道路,但是椒盐噪声情况严重。图6(b)是采用KFCM算法的聚类结果,把农田中灰度不同的区域成功地区分开,但部分农田与河流被划为同一类,一些裸地也和道路被聚为一类。图6(c)是采用FLICM算法的聚类结果,该算法较好地解决了FCM聚类结果中的椒盐噪声问题,农田已经形成了完整的区域。图6(d)是采用本文算法的聚类结果,进一步改善了FLICM算法的聚类结果,除农田外,林地部分的噪声点也被消除了很多。
Fig.6 The clustering results of remote sensing image on suburban area 2

图6 城郊地区2遥感图像聚类结果

下面对遥感图像的聚类精度进行定量评价,以实验3为例,从该遥感图像(图6)中随机抽取80组点,比较上述4种方法的总体精度和kappa系数,结果如表1所示。从表1中可看出,本文算法的聚类总体精度和kappa系数最高,说明其聚类结果最好。
Tab.1 Comparison of four methods in clustering accuracy

表1 4种方法的聚类精度比较

算法 生产者精度(%) 总体精度(%) kappa系数
河流 道路 建筑地 农田 林地
FCM 50 86 60 75 77 69 0.59
KFCM 41 56 50 66 79 64 0.54
FLICM 100 50 71 76 71 74 0.65
本文 83 33 52 61 87 78 0.71
为了比较上述聚类算法的运行速度,现将针对3组实验的聚类算法所需运行时间列于表2。从目视解译效果来看,FCM算法、KFCM算法的聚类效果很不理想,椒盐噪声问题严重,且存在着较多的错误分类现象。与FCM算法、KFCM算法相比,FLICM算法的聚类效果有了较大的提升,改善了椒盐噪声问题,聚类效果较好,但仍存在着一些错误聚类,如图4中较多的土地被误分割为农田。本文算法的运行时间与FLICM算法相比相差不大,但聚类效果最好,是一种行之有效的遥感图像聚类方法。
Tab.2 The clustering time of three sets of experiments(s)

表2 3组实验的聚类运行时间(s)

FLICM算法 本文算法
实验1 33.3 36.7
实验2 11.0 25.0
实验3 28.8 34.2

4 结论

基于局部空间信息KFCM的遥感图像聚类算法,综合了特征信息和空间邻域信息,可高效地去除噪声对结果的影响,而且算法可直接应用于原始遥感图像,不需要进行滤波预处理,具有很强的鲁棒性;同时,在FCM算法基础上运用核函数将待聚类的数据映射到高维特征空间,充分考虑了各特征向量对聚类结果贡献度的不同,克服了噪声特征向量对聚类的影响,对于高维非团状数据也能做到很好的非线性划分。大量实验结果表明,本文算法对噪声有更强的鲁棒性,可以得到更好的同质区域,优于现有的FCM算法、FLICM算法及KFCM算法,为遥感图像下一步的优化处理奠定了很好的基础。

The authors have declared that no competing interests exist.

References

Publishing order | Descend order by publishing year | Descend order by cited within
[1]
陈华,陈书海,张平,等. K-means算法在遥感分类中的应用[J].红外与激光工程,2000,29(2):26-30.

[2]
Simpson J J, Mclntire T J.An improved hybrid clustering algorithm for natural scenes[J]. IEEE Transaction on Geoscience and Remote Sensing, 2000,38(2):1016-1032.

[3]
吴昊,郁文贤,匡纲要.一种基于混合概率PCA模型的高光谱图像非监督分类方法[J].国防科技大学学报,2005,27(2):61-64.

[4]
Ren H, Chang C I.A generalized orthogonalsubspace projection approach to unsupervised multi-spectral image classification[J]. IEEE Transactions on Geoscience and Remote Sensing, 2000,38(6):2515-2528.

[5]
王保平. 基于模糊技术的图像处理方法研究[D].西安:西安电子科技大学,2004.

[6]
钟燕飞,张良培,李平湘.遥感影像分类中的模糊聚类有效性研究[J].武汉大学学报(信息科学版),2009,34(4):391-394.

[7]
Cheng H D, Chen Y H, Jiang X H.Thresholding using two-dimensional histogram and fuzzy entropy principle[J]. IEEE Transactions on Image Processing, 2000,9(4):732-735.

[8]
Sampath A, Shan J.Segmentation and reconstruction of polyhedral building roofs from aerial lidar point clouds[J]. IEEE Transactions on Geoscience and Remote Sensing, 2010,48(3):1554-1567.

[9]
Maulik U, Saha I.Automatic fuzzy clustering using modified differential evolution for image classification[J]. IEEE Transactions on Geoscience and Remote Sensing, 2010,48(9):3503-3510.

[10]
Yang C, Bruzzone L, Sun F, et al.A fuzzy statistics based affinity propagation technique for clustering in multispectral images[J]. IEEE Transactions on Geoscience and Remote Sensing, 2010,48(6):2647-2659.

[11]
秦昆,徐敏.基于云模型和FCM聚类的遥感图像分割方法[J].地球信息科学,2008,10(3):302-307.

[12]
吴一全,郝亚冰,吴诗婳,等.基于KFCM和改进CV模型的海面溢油SAR图像分割[J].仪器仪表学报,2012,33(12):2812-2818.

[13]
赵磊,王斌,张立明.基于模糊C均值聚类和邻域分析的无监督多通道遥感图像变化检测[J].数据采集与处理,2011,26(4):395-401.

[14]
贾振红,余银峰,杨杰,等.一种新的无监督的卫星影像变化检测算法[J].光电子·激光,2011,22(3):461-464.

[15]
Sjahputera O, Scott G J, Claywell B C, et al.Clustering of detected changes in high-resolution satellite imagery using a stabilized competitive agglomeration algorithm[J]. IEEE Transactions on Geoscience and Remote Sensing, 2011,49(12):4687-4703.

[16]
王瑞花,宋建社.基于改进FCM算法的SAR图像分类[J].西北大学学报(自然科学版),2008,38(4):193-19.

[17]
刘小芳,何彬彬,李小文.基于半监督核模糊C均值算法的北京一号小卫星多光谱图像分类[J].测绘学报,2011,40(3):301-306.

[18]
Ilea D E, Whelan P F.Ctex-an adaptive unsupervised segmentation algorithm based on color-texture coherence[J]. IEEE Transactions on Image Processing, 2008,17(10):1926-1939.

[19]
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.

[20]
Krinidis S, Chatzis V.A robust fuzzy local information c-means clustering algorithm[J]. IEEE Transactions on Image Processing, 2010,19(5):1328-1337.

[21]
张莉,周伟达,焦李成.核聚类算法[J].计算机学报,2002,25(6):587-590.

[22]
贾建华,胡勇,刘良云.青藏高原数字照片植被覆盖度自动算法与应用[J].地球信息科学学报,2010,12(6):880-885.

[23]
Kim D W, Lee K Y, Lee D, et al.Evaluation of the performance of clustering algorithms in kernel-induced feature space[J]. Pattern Recognition, 2005,38(4):607-611.

Options
Outlines

/

〈 〉