融合增强型模糊聚类遗传算法与ISODATA算法的遥感影像分类

郭云开1，曾　繁2

(1. 长沙理工大学交通运输工程学院，湖南 长沙 410076； 2. 湖南交通职业技术学院

路桥工程学院，湖南 长沙 410132)

Remote Sensing Classification of Combined Enhanced Fuzzy Clustering Genetic

Algorithm with ISODATA Algorithm

GUO Yunkai，ZENG Fan



融合增强型模糊聚类遗传算法与ISODATA算法的遥感影像分类

郭云开1，曾繁2

(1. 长沙理工大学交通运输工程学院，湖南 长沙 410076； 2. 湖南交通职业技术学院

路桥工程学院，湖南 长沙 410132)

RemoteSensingClassificationofCombinedEnhancedFuzzyClusteringGenetic

AlgorithmwithISODATAAlgorithm

GUOYunkai，ZENGFan

摘要：针对ISODATA算法预设参数较多，其聚类中心与最优迭代数目很难预先准确设定，且在聚类时没有将影像自身特点充分考虑，对个体适应度函数重视不够的问题，本文提出一种融合增强型模糊聚类GA与ISODATA的聚类方法，对聚类原型矩阵进行编码，构造隶属度矩阵，解求个体适应度函数值，在影像特征空间中搜索得到样本全局收敛极值点。通过试验证明，该方法能避开随机初选值的敏感问题，避免聚类过程的随机性，使分类结果与实际情况更为接近，该算法精度优于传统的ISODATA算法与模糊聚类GA算法，提高了分类的精度，整体效果较好。

关键词：ISODATA；增强型模糊聚类GA；适应度函数；遥感影像分类

一、引言

聚类是把具有相似性质的事物区分开并加以分类[1-3]，所谓物以类聚。迭代自组织数据分析技术算法(iterativeself-organizingdataanalysistechniquesalgorithm，ISODATA)是人们熟悉的非监督聚类算法之一，可自动执行类别合并与分裂，是成批样本修正法[2]。但这种硬分类算法没有充分考虑图像本身的特点，最优迭代次数很难设定[3]。李前进等提出了基于直觉模糊的ISODATA算法[4]，改进了隶属度函数，提高了算法速度；沈照庆等[5]在模糊ISODATA算法的基础上改进了隶属度的计算公式，使算法在实际应用中更易实现。尽管如此，该算法仍需面对随机初选值的敏感问题，在一定程度上受人为的事先干预。

遗传算法(geneticalgorithm，GA)属于进化计算之一，许多聚类分析领域内的学者利用进化计算来降低传统聚类算法对初始化的要求。早在20世纪90年代，Bezdek等就提出用遗传算法指导聚类的思路[6]。由于聚类分析仅凭自然聚类的特性进行盲目分类，在结合遗传算法后能增大真正达到物以类聚的可能性，增强型模糊聚类遗传算法将遗传算法与传统的模糊聚类算法有机结合起来，收敛速度远大于之前[7]。即便如此，遗传算子的搜索能力仍不够全面，该算法的操作参数与聚类分析性能可以进一步提高[7]。

本研究提出将增强型模糊聚类遗传算法与ISODATA算法融合，能避开随机初选值的敏感问题，减少人为事先干预，避免聚类过程的随机性，比单纯应用传统ISODATA和模糊聚类分析方法得到的聚类结果更符合实际。

二、融合增强型模糊聚类GA与ISODATA的聚类分析算法

1. 普通ISODATA算法

ISODATA算法是一种基于统计模式识别的非监督学习动态聚类算法。其实质是用将输入的模式样本生成初始类别作为种子，依据最小距离准则进行自动迭代聚类的过程。ISODATA算法是个循环过程，其步骤如下：

1) 预设聚类分析可调参数，读入N个模式样本{Xi，i=1,2,3，…，N}。一般需要先定义最大聚类中心数Nmax，能作为独立聚类的最少样本数θN，一集群中样本的距离标准差θS，两聚类中心间的最小距离θC，能一次合并的最多聚类中心对数L，最大迭代次数I。

2) 初始分类，根据式(1)按距离最小原则将模式样本分给最近的聚类Sj，依照式(2)、式(3)分别修正与计算各聚类中心值和各聚类中心间的距离均值

(1)

(2)

(3)

式(1)—式(3)中，Nc为预选的初始聚类中心数，Nc可≠Nmax；Nj为Sj类中的样本数。

3) 根据预设参数，将已获取的聚类集进行分裂、合并处理，得到新的聚类中心，依据式(4)计算全部聚类中心的距离

(4)

4) 反复进行迭代运算，判别聚类结果是否符合要求，如有需要可修改输入参数，直到获得理想的聚类结果。

2. 增强型模糊聚类遗传算法

遗传算法的基本原理是1962年由J.H.Holland提出的，在一定条件下，遗传算法可以在搜索空间中收敛到全局最优解。模糊聚类需要将原始数据矩阵进行无量纲化处理，使每一指标值统一在某一共同的数据特性范围内[10-11]。增强型模糊聚类GA需要将聚类问题的解进行编码，构造衡量各个体码链对聚类问题适应程度的适应度函数；并选择遗传算子，自适应选取操作参数，如选种概率Pi、交叉率Pc及浮动区间中心点等[7]。

聚类的最终目标是获得样本集X的模糊划分矩阵U和聚类原型P，两者是相关的，求其一便知其二[12]。该增强型模糊聚类遗传算法对聚类原型矩阵P编码，把n组表示聚类原型的参数连接起来，根据各自的取值范围，根据式(5)将其量化值用二进制串表示，式(6)定义适应度函数，并将进化结束的准则改为范数准则。

(5)

(6)

式中，ζ为一给定的常数；D(xk，pi)为相似性测度函数。

3. 融合增强型模糊聚类GA与ISODATA算法

(1) 适应度函数

模糊聚类问题可由一目标函数Tn(U，P)表示，其最优聚类结果则对应于目标函数的极小值[10]。本文提出的融合算法需要计算个体适应度函数的值。

D2(xk,Pi)=(xk-pi)T(xk-pi)-(〈xi-pi,di〉)2

(7)

(8)

(2) 融合遗传算子

该融合算法需要借助融合遗传算子找到待优化问题的解，其中包括：

1) 选种算子Ts(·)：根据样本中个体的适应度值Fi在聚类中心附近选取双亲的过程。Fi越大，则赋予更大的选种概率Pi。

(9)

3) 梯度算子Tg(·)：此算子将适应度值最高的字符串对应的解作为初始点作梯度优化获得极值点，保证每次迭代都能至少搜索到极值点。

4) 解释算子Te(·)：是解码算子的扩展，将解码得到的实数转换为编码区间所对应的值

(10)

式中，Ai为Si对应的实数编码区间中心点；B为编码区间大小；C为L比特位的二进制码的全1串所表示的实数值。

(3) 算法步骤

1) 读入影像数据区域样本，用Gray码进行编码，得到二进制的一组数列。

2) 预设聚类间最小距离为3，结合样本个体适应度值与传统ISODATA距离最小原则进行初始分类。

3) 设置进化停止的允许误差为0.02，借助融合遗传算子自适应选取操作参数，将已有聚类域与领域像元对比分析，对聚类结果进行分裂、重组等必要的优化。

4) 更新适应度函数与聚类中心，反复迭代，直到获得满意的聚类结果(全部聚类中心平均变化量小于所设阈值)。

三、试验研究分析

分类对比试验前需要先完成影像裁减、几何纠正、大气纠正等预处理工作[12]，本文采用2010年11月2日长株潭部分地区的SPOT-5 1A影像作为试验数据，影像空间分辨率为10m，共4个波段(绿、红、近红外、短波红外)，如图1所示。

图1　原图

图2是用ISODATA算法得到的聚类结果，本次试验按照影像区域内主要地物统一划分为水体、林地、草地、耕地、道路及房屋5大类(影像中道路与房屋的反射率接近，单借助光谱分类法很难区分，故两者作为一个大类表示)。图2中的河流能被完全搜索提取出来，但将与水体挨很近的部分房屋道路也误判成水体大类，总水体面积占总区域面积7.683%(见表1)，与实际不符；此外由于11月份的农田大都处于收割状态，耕地表层覆盖有干稻草，ISODATA算法不能将其与他类准确区分，在河流的西北部把耕地误判成道路房屋大类、河流南部将耕地误判成林地和草地的结果较严重，而本身属于道路房屋大类的区域没有准确提取，总体精度不高。

图2　ISODATA分类图

图3　模糊聚类GA分类图

图4　融合法分类图

图4是经过将融合增强型模糊聚类GA与ISODATA的算法应用到遥感影像分类得到的聚类结果，所设参数包括最小类间距离为5，变化阈值3%。从图3、图4中都可看出河流中部的横跨桥梁，且没有将部分房屋道路误判成水体，耕地也能被很好地提取出来，与道路房屋大类有鲜明区分。表1为3种分类方法得到的各地物所占图像百分比对比表，据统计，后两者总水体面积都少于图2，耕地面积大于图2。当然，图4中对水体、道路房屋的提取相比图3更为完全，可以反映出道路的连贯性与房屋群的成片特点通过，对比能够明显看出该图的分类结果与实际情况更为符合。

表1　分类结果统计　(%)

通过目视判断，从原始影像中随机选取水体、林地、耕地、草地、道路房屋这5大类的样本点，建立混淆矩阵，进而分别求得传统ISODATA、模糊聚类GA与融合算法的分类精度和Kappa系数[11]，表2是3种分类方法的精度对比表，可以看出本文提出的融合方法提高了分类精度，整体效果良好。

表2　分类精度

四、结论

本文提出融合增强型模糊聚类GA与ISODATA算法应用于遥感影像分类，以SPOT-5影像为试验数据，且分析比较了传统ISODATA、模糊聚类GA与该融合方法的分类结果。总体可以得出以下结论：

1) 本文提出的融合算法显示了很好的分类精度，特别是在区分水体、耕地、道路房屋大类时，能有效避免误判现象，总体分类精度达83%，优于另外两种方法。

2) 从算法上分析，融合增强型模糊聚类遗传算法与迭代自组织分析算法缓和了传统ISODATA的“硬”与模糊聚类的“软”，在分类过程中简化了参数的预设选取，能根据融合遗传算子自适应调整操作参数，减少人为事先干预，并对聚类原型矩阵进行编码，计算个体适应度函数值，能在特征空间中搜索得到其收敛极值点，使聚类结果与实际情况更为接近，提高了算法的智能化。

综上所述，该融合算法能改善中等分辨率影像的非监督分类精度，但是否对于高分辨率影像同样适用有待进一步研究。

参考文献：

[1]赵英时．遥感应用分析原理与方法[M]．北京：科学出版社，2003：194-201．

[2]王新洲，史文中，王树良．模糊空间信息处理[M]．武汉：武汉大学出版社，2003：59-63．

[3]吴孔江，曾永年，勒文凭，等．改进利用蚁群规则挖掘算法进行遥感影像分类[J]．测绘学报，2013，2(42)：59-66．

[4]李前进，王寅龙，李志祥，等．基于直觉模糊的ISODATA[J]．计算机工程与应用，2012，48(9)：176-177．

[5]沈照庆，舒宁，龚衍，等．基于改进模糊ISODATA算法的遥感影像非监督聚类研究[J]．遥感信息，2008(5)：28-32．

[6]BEZDEK J C．A Convergence Theoren for the Fuzzy ISODATA Clustering Algorithm[J]．IEEE Trans．PAMI，1980，1(2)：1-8．

[7]高新波．模糊聚类分析及其应用[M].西安：西安电子科技大学出版社，2004．

[8]郭云开，张起森．基于广义夹角的遥感图像计算机分类方法[J]，中国公路学报，2002，15(2):28-30．

[9]杨红磊，彭军还．基于马尔可夫随机场的模糊c-均值遥感影像分类[J]．测绘学报，2012,41(2)：214-218．

[10]ISHIBUCHI H，NOZAKI N，YAMAMOTO N．Selecting Fuzzy If-then Rules for Classification Problems Using Genetic Algorithms[J].IEEE Trans．FS，1995，3(3)：260-270．

[11]尹淑玲，舒宁，刘新华．基于自适应遗传算法和改进BP算法的遥感影像分类[J]．武汉大学学报：信息科学版，2007，32(3)：201-204．

[12]郭云开，曾繁．基于FLAASH与QUAC模型的SPOT5影像大气校正比较[J]．测绘通报，2012(11)：21-23，41．

[13]张俪文 ,汪云甲,王行风. 仿射传播聚类在室内定位指纹库中的应用研究[J].测绘通报,2014(12): 36-39.

作者简介：郭云开(1958—)，男，博士，教授，主要研究方向为道路环境遥感评价等。E-mail：guoyunkai226@163.com

基金项目：国家自科科学基金(41471421)；国家自然科学基金(41171397)；贵州省交通科技计划项目(2014-121-039)

收稿日期：2015-03-20；修回日期： 2015-10-15

中图分类号：P237

文献标识码：B

文章编号：0494-0911(2015)12-0023-04

引文格式： 郭云开，曾繁. 融合增强型模糊聚类遗传算法与ISODATA算法的遥感影像分类[J].测绘通报，2015(12)：23-26.DOI:10.13474/j.cnki.11-2246.2015.369