基于FCM聚类及其改进的遥感图像分割算法

引用本文

李勇发, 左小清, 杨芳, 林思, 张建柱. 基于FCM聚类及其改进的遥感图像分割算法[J]. 浙江农业科学, 2017,(3):518-520 复制到剪切板

Permissions

《浙江农业科学》编辑部所有

基于FCM聚类及其改进的遥感图像分割算法

李勇发, 左小清, 杨芳, 林思, 张建柱

昆明理工大学国土资源工程学院,云南昆明 650093

作者简介:李勇发(1990—),男,云南宣威人,硕士研究生,主要研究方向为图像处理与数据挖掘,E-mail: 549850669@qq.com。

摘要

在遥感图像分割中,某些像素分类具有不确定性和随机性,模糊C-均值(FCM)聚类算法对处理这种不确定性和随机性具有很大的优势,但传统的FCM算法具有很大的缺点。对此,该研究提出一种改进的FCM遥感图像分割算法。首先,该算法在选取聚类中心和聚类数时使用直方图进行选取,克服了传统FCM算法选取时的随机性和人为性;然后,使用叉熵距离测度代替欧氏距离测度,克服了传统FCM算法依赖于球状分布的缺点;最后,利用传统FCM算法和改进后的FCM算法对某水电站大坝遥感图像进行分割实验,比较2种方法的分割效果,结果显示,改进的FCM算法大大提高了遥感图像聚类的效率和分类的精度。

关键词: 图像分割; 聚类分析; 模糊C-均值

中图分类号:TP75 文献标志码:A 文章编号:0528-9017(2017)03-0518-03 doi: 10.16178/j.issn.0528-9017.20170348

Show Figures

遥感图像作为制作和更新GIS数据库的重要数据源, 已被广泛应用于土地利用、环境监测、资源勘探、灾害评估、城市规划等领域中。随着遥感与信息技术的不断发展, 各种海量的遥感数据都可以通过对地观测技术进行获取, 然而数据转化成信息的过程当中仍存在很多瓶颈, 其中遥感图像分割就是一项非常关键的技术, 同时也是图像处理领域的难点和重点。遥感图像分割是指对遥感图像进行处理、分析, 从中提取目标的技术和过程。当前虽然已经有了大量的图像分割算法, 但由于遥感图像通常具有灰度级多、信息量较大、边界不清晰、目标类型较多等特点, 导致这些算法在实际应用中还存在很多问题, 如适用性差、分割效率低、分割精度不高等^[1], 加之遥感图像的分割本身具有不确定性, 不同的应用目的和用户对图像感兴趣的部分不同, 期望从图像中获得的信息层次也往往不同, 致使难以建立完全准确的分割方法对遥感图像进行分割。总体来看, 在进行遥感图像分割处理时, 通常采用模糊理论的方法。但传统的模糊C-均值(FCM)聚类算法存在以下不足:(1)传统FCM算法的运行效果与初始聚类中心和聚类数密切相关, 而初始聚类中心和聚类数具有随机性, 导致每次运行效果差异较大; (2)由于FCM算法很大程度上依赖于球状样本数据, 对于非球状样本数据, 其聚类效果并不理想^[2]。为此, 本研究提出一种改进的FCM聚类算法。现报道如下。

1 传统聚类的分割算法及其实现

1.1 FCM聚类算法

FCM聚类算法是一种无监督的分类方法, 根据最小二乘原理, 计算目标函数的均方差, 得到每个数据点对类中心的隶属度和目标函数的最小值, 是一种基于目标函数的非线性迭代的最优化方法^[3]。

1.2 FCM聚类算法的原理

1.2.1 聚类目标函数

聚类算法的目标函数由开始的类内误差平方和的形式演化而来, 之后经推广, 演变成了更具普遍意义的形式。类内误差平方和形式的目标函数实际上是Ruspini提出的硬聚类分析的目标函数^[2], 它的形式为:

J(U, V)= $\begin{matrix} \overset{c}{\sum_{i = 1}} \end{matrix} \begin{matrix} \sum_{X_{j} \in X} \end{matrix} \begin{matrix} {d_{ij}}^{2} \end{matrix}$ , s.t.U∈ Ω _f。

式中:J表示目标函数; U=[u_ij]_{c× n}表示硬划分矩阵, 取值范围为{0, 1}; V=(v_1,v_2,…, v_c)是一个聚类中心向量, 对所有的i=1, 2, …c, 有v₁(v_i₁, v_i₂, …, v_is)∈ R^s, 它代表第i类聚类中心; d_ij表示第j个样本点与第i类聚类中心之间的失真度, 经常用距离函数来度量。

利用硬划分矩阵的取值不是0就是1的特点, 可以将u_ij作为权值对距离函数进行加权, 此时目标函数可以表示为:

J(U, V)= $\begin{matrix} \overset{c}{\sum_{i = 1}} \end{matrix} \begin{matrix} \sum_{X_{j} \in X} \end{matrix}$ u_ij $\begin{matrix} {d_{ij}}^{2} \end{matrix}$ , s.t. U∈ Ω _h。

把硬聚类算法的目标函数运用到模糊情形, 将隶属度的平方对聚类中心与样本点之间的距离进行加权, 就把类内误差平方和目标函数变成类内加权误差平方和目标函数^{[3, 4]}, 如下所示:

J(U, V)= $\begin{matrix} \overset{n}{\sum_{j = 1}} \end{matrix} \begin{matrix} \overset{c}{\sum_{i = 1}} \end{matrix} \begin{matrix} {u_{ij}}^{2} \end{matrix} \begin{matrix} {d_{ij}}^{2} \end{matrix}$ , s.t.U∈ Ω _f。

式中, U=[u_ij]_{c× n}表示模糊划分矩阵, 取值范围为[0, 1], 其他变量不改变含义, 将其推广为更广泛的形式, 并对FCM目标函数的表示作更广泛的描述:

式中α ∈ [1, +∞ )为模糊因子, 主要用它来控制分享程度, α 越大, 表明隶属关系越模糊, 反之表明隶属关系越清楚。

当α → +∞ 时, J→ 0且U中全部元素都靠近1/c, 就会失去模糊聚类的意义; 当α =1时, 就成为了硬聚类。因此主要由α 来控制隶属度的值, 使模糊分类的特点更加明确。

1.2.2 拉格朗日(Lagrange)乘数法^[5]

FCM算法中数据集的模糊划分是采用迭代的方法来实现, 用数学的方式表示为:

min{J(U, V)}=min{ $\begin{matrix} \overset{n}{\sum_{j = 1}} \end{matrix} \begin{matrix} \overset{c}{\sum_{i = 1}} \end{matrix} \begin{matrix} {u_{ij}}^{α} \end{matrix} \begin{matrix} {d_{ij}}^{2} \end{matrix}$ }= $\begin{matrix} \overset{n}{\sum_{j = 1}} \end{matrix}$ min{ $\begin{matrix} \overset{c}{\sum_{i = 1}} \end{matrix} \begin{matrix} {u_{ij}}^{α} \end{matrix} \begin{matrix} {d_{ij}}^{2} \end{matrix}$ }。

式中利用了矩阵U中各列独立的性质, 且隶属度函数应满足 $\begin{matrix} \overset{c}{\sum_{i = 1}} \end{matrix}$ u_ij=1, 再运用Lagrange乘数法, 得到一个无约束的准则函数:

ψ = $\begin{matrix} \overset{c}{\sum_{i = 1}} \end{matrix} \begin{matrix} {u_{ij}}^{α} \end{matrix} \begin{matrix} {d_{ij}}^{2} \end{matrix}$ +ζ (1- $\begin{matrix} \overset{c}{\sum_{i = 1}} \end{matrix}$ u_ij)。

用欧氏距离表示失真度d_ij, 则目标函数的表达式为:

J(U, V)= $\begin{matrix} \overset{n}{\sum_{j = 1}} \end{matrix} \begin{matrix} \overset{c}{\sum_{i = 1}} \end{matrix} \begin{matrix} {u_{ij}}^{α} \end{matrix} \begin{matrix} {d_{ij}}^{2} \end{matrix}$ = $\begin{matrix} \overset{n}{\sum_{j = 1}} \end{matrix} \begin{matrix} \overset{c}{\sum_{i = 1}} \end{matrix} \begin{matrix} {u_{ij}}^{α} \end{matrix} \begin{matrix} ‖ x_{f} - v_{i} ‖^{2} \end{matrix}$ 。

对目标函数J求导, 可获得聚类中心的更新式, 即:

$\begin{matrix} \frac{\partial J}{\partial v_{i}} \end{matrix}$ = $\begin{matrix} \overset{n}{\sum_{j = 1}} \end{matrix} \begin{matrix} {u_{ij}}^{α} \end{matrix} \begin{matrix} \frac{\partial}{\partial v_{i}} \end{matrix} \begin{matrix} ‖ x_{j} - v_{i} ‖^{2} \end{matrix}$ =2 $\begin{matrix} \overset{n}{\sum_{j = 1}} \end{matrix} \begin{matrix} {u_{ij}}^{α} \end{matrix}$ x_j-2 $\begin{matrix} \overset{n}{\sum_{j = 1}} \end{matrix} \begin{matrix} {u_{ij}}^{α} \end{matrix}$ v_i=0。

2 基于改进的FCM聚类的遥感图像分割算法

2.1 改进FCM聚类算法的原理

2.1.1 初始聚类中心与聚类数的选取

在传统FCM算法中, 初始聚类中心与聚类数的选取对于聚类效果具有很大的影响^[4]。为解决聚类中心和聚类数在选取过程中的随机性, 利用直方图交互获取初始聚类中心与聚类数。具体做法如下:将彩色的遥感图像从RGB颜色空间变为特征颜色空间, 并计算出它的直方图, 利用直方图波峰的个数来确定图像的聚类数, 然后再利用在原先基础上减1或加1的方法进一步修正聚类数。聚类中心为波峰处的像素值。

2.1.2 距离测度的选择

传统FCM算法假定样本呈球状或者椭球状排列, 并据此选用了欧氏距离测度。但实际情况中。样本数据并不完全呈球状排列, 因此, 传统FCM算法不能很好地用于非球状排列数据的聚类。为提高其鲁棒性, 本研究选用交叉熵距离测度。

交叉熵距离是用来衡量2种概率分布之间信息量差异的量, 又称为特征散度距离, 设样本数据集X={x₁, x₂, …, x_n}, Y={y₁, y₂, …y_n}, 则交叉熵距离可表示为:

D(X:Y)=[d(x₁, y₁), d(x₂, y₂), …d(x_n, y_n)]^T;

d(x_i, y_i)=x_iln $\begin{matrix} \frac{x_{i}}{y_{i}} \end{matrix}$ +y_iln $\begin{matrix} \frac{x_{i}}{y_{i}} \end{matrix}$ (i=1, 2, …n)。

若样本集中数据取值为正值时, 则特征散度的分量满足同一性和非负性。

鉴于人的视觉感受相同, 所以考虑在Lab均匀颜色空间中分割图像。L分量表示图像的亮度, a分量和b分量分别对称。人对于通过均匀颜色空间内任意一点距离相同的地方的视觉感受是一样的, 因此本文在Lab均匀颜色空间中对图像进行分割。L分量表示图像的亮度, a分量和b分量分别对称, Δ C代表图像色差, 图像中第i、j个像素在Lab空间中的色差可以表示为:

Δ C= $\begin{matrix} \sqrt{(L_{i} - L_{j})^{2} + (a_{i} - a_{j})^{2} + (b_{i} - b_{j})^{2}} \end{matrix}$ 。

Δ C的值越小, 表明两点间的色差越小。因此, 可用下列目标函数描述像素间相似程度的非相似性:

J= $\begin{matrix} \overset{c}{\sum_{i = 1}} \end{matrix}$ J_i= $\begin{matrix} \overset{c}{\sum_{i = 1}} \end{matrix} \begin{matrix} \sum_{(L, a, b) \in c} \end{matrix} \begin{matrix} \sqrt{d^{2} (L_{j}, L_{i}) + d^{2} (a_{j}, a_{i}) + d^{2} (b_{j}, b_{i})} \end{matrix}$ 。

式中d是利用叉熵测度定义的距离。

2.2 改进FCM聚类算法的步骤

根据以上原理, 改进的FCM算法分割步骤如下:首先, 将彩色图像从RGB颜色空间转换到Lab空间; 其次, 提取图像像素的ab分量(色度空间); 然后, 计算ab分量的直方图, 并运用直方图交互获取图像的聚类中心与聚类数; 最后, 利用目标函数进行FCM聚类, 记录聚类结果。

3 传统FCM与改进FCM聚类的图像分割对比实验

对某水电站大坝遥感图像进行分割实验, 图1为传统FCM分割算法在不同聚类次数下的效果图和最终分割效果图, 图2为改进的FCM分割算法在不同聚类次数下的效果图和最终分割效果图。传统FCM聚类算法和改进的FCM聚类算法对比结果如表1所示。

	Figure Option View Download New Window
	图1 传统FCM分割算法在不同聚类下的效果以及最终分割效果

	Figure Option View Download New Window
	图2 改进的FCM分割算法在不同聚类下的效果以及最终分割效果

表1 传统FCM聚类算法和改进的FCM聚类算法对比

通过实验可以看出:运用改进的FCM聚类算法分割后的遥感图像, 分割效果明显, 程序运行时间较短, 能够有效地提高图像分割的精度与效率。这是因为改进的FCM算法利用图像直方图获取初始聚类中心和聚类数, 克服了传统FCM算法获取初始聚类中心和聚类数的随机性, 同时又选用了叉熵距离测度, 使得该方法不必依赖于球状数据分布, 聚类分割效果较好, 边缘清晰, 效率也大大提高。

4 小结

本研究基于集合论、模糊数学的相关理论, 介绍了基于FCM聚类的遥感图像分割算法, 通过引入叉熵距离测度, 对其做了改进, 提出一种基于改进的FCM聚类的遥感图像分割算法, 并进行验证实验, 结果表明, 该方法具有更高的分割效率和分割精度, 解决了传统方法对球状数据分布的依赖。

The authors have declared that no competing interests exist.

参考文献:

View Option

[1]	周家香. Mean Shift遥感图像分割方法与应用研究[D]. 长沙: 中南大学, 2012. [本文引用:1]
[2]	贲志伟, 赵勋杰. 基于改进的FCM算法提取彩色图像有意义区域[J]. 计算机工程与设计, 2010, 31(18): 4082-4084. [本文引用:2]
[3]	王洪蕾. 基于模糊聚类的图像分割算法研究[D]. 长沙: 湖南大学, 2008. [本文引用:2]
[4]	QIU C, XIAO J, YU L, et al. A modified interval type-2 fuzzy C-means algorithm with application in MR image segmentation[J]. Pattern Recognition Letters, 2013, 34(12): 1329-1338. [本文引用:2]
[5]	贲志伟. 彩色图像有意义区域提取算法研究[D]. 苏州: 苏州大学, 2010. [本文引用:1]

2012

0.0

周家香. Mean Shift遥感图像分割方法与应用研究[D]. 长沙: 中南大学, 2012.

随着遥感技术的发展,对地观测系统已获取了海量各种类型遥感数据。现有研究表明,数据转化为信息存在许多不足,而遥感图像分割又是实现数据转化为信息过程中起着重要作用的一项关键技术,也是遥感图像处理领域的重点及难点课题。虽然已发展了大量的图像分割方法,并取得了一些研究成果,但应用到遥感图像分割中仍存在算法的适用性差、分割效率低、分割精度不高等不足。针对这些不足,本文拟采用Mean Shift算法进行遥感图像分割,充分利用图像的多维特征,自适应降噪的同时有效保留目标物体的边缘信息,以提高图像分割的精度和可靠性。本文研究工作主要包括： (1)提出一种结合纹理特征的自适应带宽遥感图像分割方法,以解决Mean Shift算法分割精度不高的问题。传统Mean Shift算法只使用了图像的“位置-颜色”域特征,导致图像分割精度不高。该方法则充分利用遥感图像的“位置-颜色-纹理”域组成多维特征空间,发展自适应带宽策略。先对“位置-颜色”域特征数据进行聚类,再对聚类结果计算每一聚类区域的空间带宽、灰度带宽和纹理带宽,最后在“位置-颜色-纹理”域进行自适应聚类,得到分割结果。实验结果表明,该方法具有自适应性和稳健性,可以较好地提高遥感图像分割精度。 (2)引入一种区域合并方法,用于图像分割的后续处理中,以解决Mean Shift分割算法易产生的过分割问题。该方法先根据待处理遥感图像的空间分辨率确定固定空间带宽,再利用plug-in规则计算遥感图像每个波段的颜色带宽。采用基于区域面积加权的区域相似度准则和基于区域熵的合并停止准则来进行分割后的区域合并,从而解决过分割问题。 (3)提出了一种改进的快速遥感图像分割方法,以解决Mean Shift算法迭代时间长不适于处理海量的遥感图像的问题。针对影响Mean Shift算法的时间复杂度的各个变量分别提出加速策略；先利用固定带宽的高斯Mean Shift算法进行聚类得到超像素,再计算每个超像素的自适应带宽；最后采用基于区域的超像素融合来完成遥感图像分割,以达到快速地分割遥感图像。 (4)采用成熟的分割评价方法,用以评估遥感图像分割效果。对比分析了马丁误差估量法和对象级一致性误差估量法。实验比较得出：对象级一致性误差估量法是基于对象水平,能够很好地量化分割图像与参考图像之间的差异；相对于马丁误差估量法而言,对象级一致性误差估量法能够正确地反映分割图像中存在的过分割和欠分割状况,其评价结果与主观评价更加相符。 (5)发展一种基于Mean Shift遥感图像分割的道路提取方法。该方法首先应用Mean Shift算法实现道路图像的初步分割,再合并灰度相似的区域,并依据直方图选取最佳的阈值,进行二值化分割；然后引入形状因子去除混杂在图像中与道路形状特征不相似的区域,对于仍然与道路相连的非道路区域,则构造多方向形态学滤波对其进行剔除,从而分割出独立的道路区域,同时提取出道路线；最后连接断裂的道路线,实现道路网的提取。多组实验结果表明,该方法能很好地从复杂环境中提取道路网,特别是对直线型道路尤其有效。最后,总结了本文的研究成果。下一步需要深入的研究工作有：(1)考虑分割的多尺度性,实现基于Mean Shift算法的多尺度遥感图像分割；(2)考虑利用Gabor滤波器来提取纹理特征,或将更多的特征如形状等特征用于Mean Shift遥感图像分割中。

... 当前虽然已经有了大量的图像分割算法,但由于遥感图像通常具有灰度级多、信息量较大、边界不清晰、目标类型较多等特点,导致这些算法在实际应用中还存在很多问题,如适用性差、分割效率低、分割精度不高等^[1],加之遥感图像的分割本身具有不确定性,不同的应用目的和用户对图像感兴趣的部分不同,期望从图像中获得的信息层次也往往不同,致使难以建立完全准确的分割方法对遥感图像进行分割 ...

2010

0.0

贲志伟, 赵勋杰. 基于改进的FCM算法提取彩色图像有意义区域[J]. 计算机工程与设计, 2010, 31(18): 4082-4084.

针对传统的FCM算法随机获取初始聚类中心与分类类别数的缺陷问题,提出了一种获取初始聚类中心与分类类别数的方法,并采用交叉熵测度准则进行FCM聚类,对彩色图像进行分割,提取有意义区域.实验结果表明,该方法不仅能够提高算法的聚类速度与算法的普适度,而且可以改善图像的聚类效果.与传统的FCM算法相比,该算法更易于实现彩色图像有意义区与背景的分离,分割效果令人满意.

... (2)由于FCM算法很大程度上依赖于球状样本数据,对于非球状样本数据,其聚类效果并不理想^[2] ...

... 类内误差平方和形式的目标函数实际上是Ruspini提出的硬聚类分析的目标函数^[2],它的形式为: ...

2008

0.0

... 1 FCM聚类算法FCM聚类算法是一种无监督的分类方法,根据最小二乘原理,计算目标函数的均方差,得到每个数据点对类中心的隶属度和目标函数的最小值,是一种基于目标函数的非线性迭代的最优化方法^[3] ...

... 把硬聚类算法的目标函数运用到模糊情形,将隶属度的平方对聚类中心与样本点之间的距离进行加权,就把类内误差平方和目标函数变成类内加权误差平方和目标函数^[3,4],如下所示: ...

2013

0.0

... 在传统FCM算法中,初始聚类中心与聚类数的选取对于聚类效果具有很大的影响^[4] ...

2010

0.0

贲志伟. 彩色图像有意义区域提取算法研究[D]. 苏州: 苏州大学, 2010.

彩色图像有意义区域提取是计算机视觉领域里最为基础和重要的问题之一。有效合理的提取方法能够为基于内容的图像检索、对象分析等抽象出十分有用的信息,从而使得更高层的图像理解、图像分析成为可能。　　论文围绕如何在彩色图像中自动提取出对人们感兴趣的区域进行了详细、深入的研究。在总结和分析现有有意义区域提取算法的基础上,结合研究的实际应用背景, 以感兴趣区域的颜色特性作为前提,提出了两套有效合理的彩色图像有意义区域提取算法,并对提取算法进行了详细的分析。　　论文的研究成果主要体现以下两大方面:　　 1.对传统的模糊...

... 2 拉格朗日(Lagrange)乘数法^[5] ...