1 引 言

遥感影像因其分辨率的限制存在着大量混合像元，混合像元现象制约了遥感影像的提取精度和应用范围^{[1, 2, 3]}。传统的遥感影像聚类方法，如k均值^[4]和ISODATA^[5]等，大多属于硬聚类方法，该类方法直接将像元归属到某个类别，由于未考虑到同一像元中可能包含不同类别地物的情况，难以解决地物混合问题^[6]。传统的模糊聚类方法(如模糊k均值)因采用隶属度表示像元属于各个类别的程度，能够获得比传统的硬聚类方法更好的分类结果，被广泛应用于遥感影像分类中^{[1, 2, 7, 8]}，但其仍然存在以下3个难点问题有待解决：① 无法自动地确定类别数^{[9, 10]}；② 容易陷入局部最优解^[6]，其聚类精度仍有待提高；③ 分类结果受初始聚类中心位置的影响较大^[11]。

针对以上难点，近年来国内外学者开始尝试利用进化算法进行影像自动聚类的研究^[10]，提出了不同的影像自动聚类方法。文献^[12]提出了一种利用PSO算法，通过硬聚类有效性指标来确定影像类别数的影像自动分类方法；文献^[9]提出了基于差分进化算法(DE)来寻找影像的类别数的硬聚类算法。之后，文献^[6]和文献^[10]分别将模糊聚类有效性指标引入自动聚类，实现了对遥感影像的自动模糊聚类。但是这些方法由于搜索空间巨大，往往仅适用于较小的模拟数据，在处理波段较多的遥感影像时需要对影像进行降维处理才能得到较好的效果。

为了提高自动模糊聚类方法的性能，解决当搜索空间过大时进化自动聚类算法无法有效寻找到聚类中心的合理位置等问题，本文提出一种基于自适应差分进化的遥感影像自动模糊聚类方法(automatic fuzzy clustering based on self-adaptive differential evolution for remote sensing imagery，AFCDE)。该方法能够在无需先验类别数目信息的情况下，自动获取最优遥感影像聚类结果。差分进化算法由文献^[13]于1995年提出，因其具有编码简单、搜索速度快等优点，已广泛应用于信号处理、数值优化、模式识别等多个领域^[14]。然而传统差分进化算法也存在依赖先验知识，需要人工选择控制参数的问题。为了充分利用差分进化最优化能力和避免其参数选择问题，本文算法以Xie-Beni指数^{[15, 16]}作为适应度指标，利用自适应变异方法对DE算法的主要参数步长因子F以及交叉率CR进行自适应选择，构建自适应DE方法，在对聚类中心进行实数和二进制掩码(1表示该聚类中心被选择，0表示不选择)编码后，通过自适应DE算法进行聚类数目自动搜索，并针对遥感影像自动聚类空间较大的特点，结合局部搜索操作以减小算法搜索范围，获取合理类别数及最优聚类结果。

差分进化算法(differential evolution,DE)是近年来快速发展的一种简单而有效的进化算法，已被成功应用于求解无约束单目标和多目标优化问题^{[12, 13]}。该算法在保留基于种群的全局搜索方式的基础上，采用实值编码，通过差分变异与交叉产生后代。子代个体与父代个体之间进行一对一的淘汰选择，保留适应度高的个体，从而在迭代过程中实现进化，最终达到搜索全局最优解的目的。具体过程如下：

首先，对种群进行随机初始化。之后，进行变异操作，变异公式如式(1)所示，其中，v_i为新产生的个体；F是步长因子，0＜F≤1；G_r1、G_r2、G_r3代表从种群中随机选取的3个个体；r₁、r₂、r₃为1到NP之间的随机整数，且r₁≠r₂≠r₃

点击浏览公式

点击浏览公式

点击浏览公式

DE算法具有计算简单等优点，已在影像处理^[17]、电力系统设计^[18]、生物信息^[19]、传感网优化^[20]、信号处理^[21]等领域得到了广泛应用，但主要控制参数 F和CR通常需要人工指定，依赖于先验知识，这也限制了其适用范围，特别是对于数据量较大的遥感影像聚类，其参数的选择往往需要耗费很多的时间。

为了提高DE的自适应性，并利用差分进化稳健的全局搜索能力进行遥感影像聚类，本文提出了AFCDE。该方法对聚类中心进行实数编码，在聚类过程中以模糊聚类类别判决函数Xie-Beni指数作为适应度函数，通过差分进化的变异、交叉、选择等算子自动确定类别数目，同时为了减少算法对于DE参数的影响，采用自适应方法更新DE参数值以获得最优聚类结果。其具体过程如下。

为了实现遥感影像自动聚类，首先对初始种群中的NP个个体进行聚类编码。对于每个个体，其编码为G_i=[G_i,1,G,_i2,…，G_i,j,…，G_i,l]，其中，l=C×d；C为聚类中心的最大个数；d代表着每个聚类中心的维数。对于遥感影像，d表示遥感影像的波段数。为了自动选择聚类中心的个数，每个个体都对应一个长度为C的二值掩膜，Masker_Gi=[B₁,B₂,…B_t…,B_C]，表示C个聚类中心中哪些被选择，当B_t的取值为1时，代表第t个聚类中心被选择；而当B_t为0时，表示第t个聚类中心未被选择。种群个体G_i的初始化采用随机赋值的方式，如式(4)所示

点击浏览公式

点击浏览公式

图 1以波段数为2，最大聚类数为4的遥感影像进行聚类为例，显示其编码及掩码的结果，其中，个体的长度l=2×4，类别1和3的二值掩码为1，表示该聚类中心被选择。

图 1 AFCDE算法个体编码 Fig. 1 Individual encoding of AFCDE algorithm

图选项

为了进行适应度的计算，需要将个体G_i中掩码值为1的部分解码成遥感影像的聚类中心U_i，i为聚类中心的序号，0＜i≤K,0＜K≤C，C为个体G_i包含的最大类别数，K为通过3.1节二值掩码被选中的聚类中心的总数。以图 1中所示个体G_i为例，解码后成为U₁和U₂两个聚类中心，如图 2所示。

图 2 AFCDE算法个体解码 Fig. 2 Individual decoding of AFCDE algorithm

图选项

为了获得最优聚类数，本文利用文献^[15]中 (XB)系列指数作为DE的适应度函数f。Xie-Beni系列指数是一种遥感影像模糊聚类有效性评价指标^[22]，能够有效地获得遥感影像最优分类数，计算如式(6)

点击浏览公式

点击浏览公式

点击浏览公式

在AFCDE中计算适应度时，只有被选择的聚类中心才会用于计算XB值。在每次计算适应度前，使用式(7)和式(8)对聚类中心进行更新，加快算法的运算速度^{[6, 23]}。

为了提高AFCDE的自适应性，本文方法采用自适应变异方法对步长因子F以及交叉率CR进行自适应选择^[24]，提高算法搜索的性能。

首先，在每一代计算的开始，求出每个个体的归一化适应度f′_i

点击浏览公式

为实现该过程，在AFCDE中每个个体G_i均有自己的步长因子F_Gi和交叉率CR_Gi，且以一定的概率遗传至下一代。具体如下：通过式(10)求得每个个体的F_Gi，并进行差分变异操作，产生新的个体v_i，再利用式(11)计算个体的CR_Gi，将v_i与对应父代个体进行交叉，得到候选个体G_i^c ={G_i,1^c,G_i,2^c,…,G_i,j^c,…,G_i,l^c}

点击浏览公式

点击浏览公式

通过自适应地选择F和CR，表现好的个体拥有更多的更新参数的机会，使得计算资源在种群中进行合理的分配，从而提高整个算法的搜索性能。

根据式(12)，将候选个体与相应的父代中的个体进行一对一地比较，淘汰掉适应度低的个体，保留适应度高的个体

点击浏览公式

在进行完以上步骤之后，需要对个体以及个体的掩膜进行更新。若满足条件rand(0,1)＜(f′)²，则使用式(6)对个体的掩膜进行重置。

由于遥感影像的波段数较多，搜索空间较大，其进化结果往往难以收敛。为了提高AFCDE的搜索效率和结果，本文采用局部搜索算子提高算法的效率，即当最优个体G_best在进化过程中连续g代不发生变化时，认为程序已搜索到最佳的类别数，将G_best的掩膜所激活的类别个数认为是最优类别数，把G_best的掩膜赋给种群中的其余个体Masker_Gi=Masker_Gbest，停止掩膜更新，再进行类别数固定下的最优聚类中心搜索，以减小算法的搜索空间，提高优化效率。

两代最优个体G_best之间适应度的差值在给定的阈值范围之内或迭代次数达到最大迭代次数T_max时算法终止。算法的流程图如图 3所示。

图 3 AFCDE算法流程图 Fig. 3 Flow chart of AFCDE

图选项

为了验证AFCDE算法的有效性，本文选了两幅真实遥感影像进行分类试验，并与k均值、模糊k均值、ISODATA算法以及自动聚类算法FCIDE^[10] (fuzzy clustering with an improved differential evolution)进行了结果对比。分类过程中对于XB指数中的模糊度指数m，在试验1中设置为3，试验2中设置为2。

本试验影像为机载扫描仪获取的Flightline C1 (FLC1)数据中的一部分，如图 4(a)所示，该数据共12波段，大小为92像素×107像素。影像为美国印第安纳州Tippecanoe县南部的一个农业区。其真实地物类型分布情况如图 4(b)所示。测试样本数据均通过实测获得，共包含玉米、燕麦、红苜蓿和小麦4个类别，各类地物的样本数目分别为1743、715、1700、1472，共计5630。

图 4 FLC影像分类结果图 Fig. 4 Classification result of FLC image

图选项

图 4(c)～(g)分别表示k均值、ISODATA、模糊k均值、FCIDE和AFCDE的分类结果。ISODATA和k均值算法在分类时对聚类的数目进行了人工的指定。从目视效果上可以看出，k均值和ISODATA的分类结果较为相似。两者无法正确地将燕麦类进行区分，并且将苜蓿类以及玉米类中的一部分像素错分成其他类别的作物；模糊k均值算法、FCIDE和AFCDE算法在目视效果上比较接近，明显优于k均值和ISODATA算法，三者对于燕麦和小麦类的划分情况基本相同，但在光谱特征较为接近的红苜蓿以及玉米类的划分中，AFCDE的错分现象要少于模糊k均值算法。

表 1和表 2描述了各分类器的混淆矩阵和精度的定量比较结果。AFCDE算法在无需指定类别数的情况下，其总体精度比需要事先指定类别信息的k均值、ISODATA、模糊k均值算法分别提高了14.62%、14.62%和0.25%。与同样具有搜索类别能力的FCIDE算法相比，AFCDE由于在确定类别数目之后利用局部搜索算子有效地缩小了算法的搜索空间，精度提高了1.34%。AFCDE算法能够比其他算法表现得更优异的原因，在于其利用了自适应差分进化全局搜索能力，并通过自适应调整参数提高算法的性能，摆脱了由于聚类中心初始化以及在迭代过程中陷入局部最优解对结果所造成的影响，从而在处理较为复杂地物的分类问题上取得了最优的结果。

在对FLC数据进行分类的试验中，AFCDE所获得的XB指数值最低，为0.108，优于FCIDE的0.123 5及模糊k均值的0.271。另外，在独立运行的30次试验中，AFCDE找到正确类别数的次数为21，而FCIDE则仅有7次，其原因在于FCIDE方法在原始搜索空间中进行全局搜索，由于遥感影像波段较多，其搜索空间范围太大，降低了搜索到最优类别数的概率。而AFCDE方法采用了局部搜索算子，在保持算法精度的同时，减少了算法的搜索空间，并提高了算法的搜索效率。

本试验采用了一幅武汉地区的TM影像。如图 5(a)所示，该影像共有6个波段，大小为1000像素×1000像素，空间分辨率为30 m，影像的采集时间为2002年7月。其测试样本数据如图 5(b)所示，主要通过实地调查，并结合人工解译的方法获得。该测试数据包含了46 475个样本，主要包含5类地物，分别是树木、道路、农田、水体以及城区，各类地物的测试样本数目分别为 8396、2105、6318、16 675、12 981，各种地物的测试数据均分布广泛，具有较好的代表性。

图 5 武汉TM影像分类结果及测试数据 Fig. 5 Classification image of Wuhan TM and test samples

图选项

图 5(c)～(g)分别为k均值、ISODATA、模糊k均值、FCIDE、AFCDE的分类影像图。此幅影像地物复杂性较高，地物混合分布情况较为严重，而k均值算法和ISODATA算法处理存在大量混合地物的分类能力较弱，因此在指定了正确类别数的情况下仍然出现了较为严重的错分现象，未能区分出道路类别，且水体和城区之间存在着大量的错分现象。FCIDE算法对水体和城区之间做出了正确的划分，但将城区中的部分道路地物错分为了植被。模糊k均值算法在视觉效果上明显优于之前的3种算法，有效地将水体与城区以及道路与植被之间区分开来。AFCDE算法与模糊k均值算法相比，不仅对水体与城区、道路与植被进行了有效的区分，同时显著提高了城区和道路之间分类的准确性。

为了进一步验证AFCDE算法的准确性，将分类结果之间进行了定量的精度比较，比较采用的指标分别为混淆矩阵、总精度和Kappa表 3对各算法的混淆矩阵进行了对比，表 4利用测试样本对5种算法的总精度与Kappa系数进行了比较。在处理武汉地区遥感影像的分类问题时，AFCDE算法在自动获取类别数的同时取得了85.63%的精度，比k均值、ISODATA、模糊k均值以及FCIDE分别提高了23.84%、23.84%、3.38%、3.86%的精度。

在30次的运行中，AFCDE有26次得到了正确的类别数，高于FCIDE的24次。另外，在分类试验中，AFCDE获得了最低的XB指数，为0.144，优于FCIDE的0.149及模糊k均值的0.231。

AFCDE算法的计算复杂度，主要由以下几部分构成：

(1)初始化。AFCDE算法需要的时间为O(NP·l)，其中，NP代表的是种群中的个体数；l代表的是个体向量的长度，l= K·D。其中，K为最大聚类数目;D为遥感影像的波段数。

(2)适应度的计算。① 计算N个点对应于K个聚类中心的时间复杂度为O(N·l)，N代表的是遥感影像中像元的个数;② 更新K个聚类中心的复杂度为O(l)；③ 对应种群中单个个体适应计算的时间复杂度为O(N·l)。因此，计算适应度的总时间复杂度为O(NP·N·l)。

(3)交叉变异操作。每代交叉变异的时间复杂度为O(NP·l)。

(4)个体淘汰。进行新旧个体之间淘汰选择的复杂度为O(NP)。

因此，将以上步骤的所有时间复杂度为O(l·N·NP·G)。其中，G为总的进化代数。文中试验部分FCIDE算法与AFCDE算法的运行时间对比如图 6所示。

图 6 AFCDE与FCIDE算法计算时间对比 Fig. 6 Comparison of time consuming between FICDE and AFCDE

图选项

图 6(a)和图 6(b)分别为FLC数据以及武汉TM影像分类试验时，FCIDE算法与AFCD算法的运行时间对比。由图 6可知，在进行分类试验时，AFCDE算法耗时小于FCIDE算法。这是因为AFCDE算法通过局部搜索增进了搜索的效率，减少了总迭代次数，所以算法效率优于FCIDE算法。

利用差分进化搜索效率高、效果稳定、操作简便的特点，本文提出的算法采用自适应策略对差分进化的参数进行优化，摆脱了传统方法在进行参数选择时需要经验的状况；同时，本算法将XB指数作为优化的适应度值，通过给个体添加掩膜的方式，实现了遥感影像类别个数的自动选择。通过试验表明，本文算法能够在自动寻找类别数目的同时，合理地寻找到每类的聚类中心。该算法与传统聚类算法相比不仅能够获得更高的分类精度，而且具有较高的稳定性。本文提出的算法以XB指数作为唯一的聚类有效性指标，在未来的工作中，将考虑采用多个聚类有效性指标(如XB值、J_m值等)作为适应度函数，利用多目标优化算法进行同时优化^[25]，进一步提升自动聚类方法的稳定性。