基于布谷鸟算法的遥感影像智能分类

沈泉飞，曹 敏，史照良，许如琪

(1. 江苏省基础地理信息中心，江苏 南京 210013; 2. 南京师范大学虚拟地理环境教育部重点实验室，江苏 南京 210023; 3. 江苏省测绘地理信息局，江苏 南京 210013)

基于布谷鸟算法的遥感影像智能分类

沈泉飞1，曹 敏2，史照良3，许如琪2

(1. 江苏省基础地理信息中心，江苏 南京 210013; 2. 南京师范大学虚拟地理环境教育部重点实验室，江苏 南京 210023; 3. 江苏省测绘地理信息局，江苏 南京 210013)

提出了一种新的基于布谷鸟算法的智能式遥感分类方法。采用布谷鸟智能优化算法，自动搜索遥感影像各波段的最优阈值分割点，并定义各波段最优阈值分割点和影像分类目标类别的连线为布谷鸟的最佳解，构造以If-Then形式表达的遥感分类规则。将所提的基于布谷鸟算法的影像分类方法应用于ALOS影像分类中，并与蜂群智能遥感分类方法和See5.0决策树方法进行了对比分析。结果表明，布谷鸟智能遥感分类的总体精度和Kappa系数均比蜂群智能遥感分类和See5.0决策树方法更高，该智能遥感分类方法具有更好的分类效果。

布谷鸟算法；仿生智能计算；遥感影像；分类

遥感影像分类一直是遥感影像处理的重要环节。传统的统计分析分类方法如最大似然法、最短距离法、K-Means法、贝叶斯分类法等，以训练数据遵循正态分布为前提，训练样本的选择和参数估计会直接影响遥感影像分类结果[1]。随后，学者们提出神经网络法[2]、决策树分类法[3]、模糊分类法[4]、支持向量机分类法[5]和面向对象分类法[6]，总体分类精度优于传统的统计分类方法，具有更好的弹性和稳健性。当地物状况非常复杂时，一般的遥感分类方法不能很好地处理线性不可分的地物，智能式的分类方法能够为解决这一问题提供新的手段[7]。

仿生智能计算通过模拟生物的行为或自然界的现象来解决目标优化问题，是计算智能领域的研究热点方向之一[8]。目前，已经有多种智能式遥感影像分类方法，如基于蚁群算法的遥感影像分类方法[9-10]、基于粒子群算法的遥感分类方法[11]、基于蜂群算法的遥感分类方法[12]等，这类智能式方法均取得了较好的分类效果。智能优化算法仍然有提升的空间，如何提高土地利用分类精度仍是遥感领域的重要研究方向。

近年来，仿生智能计算领域出现了一种新型的元启发式算法——布谷鸟算法(cuckoo search, CS)，它是由剑桥大学Xin-She Yang于2009年结合布谷鸟种类的巢寄生繁育行为和鸟类、果蝇等的莱维飞行(Lévy flight)行为特征，提出的一种新的全局搜索优化算法[13]。该算法增加了群体之间的信息交流，具有控制参数少，能够有效保持局部搜索和全局搜索之间平衡，加速收敛速度，易于实现等优点[13-14]，已有研究表明该算法性能优于粒子群算法和蜂群算法[14]。目前，布谷鸟算法已经被广泛应用于多目标优化[15]、数据聚类[16]、图像分割[17]等领域，能够有效地解决各种复杂优化问题。本文以土地利用遥感分类为例，提出一种利用布谷鸟算法对遥感影像进行分类的新方法，通过模仿布谷鸟的巢寄生行为的方式，布谷鸟在多维空间中不断地搜索各波段的最优区间，将各波段最优区间与土地利用类型连接，形成遥感影像的分类规则。

1 基于布谷鸟算法的遥感影像分类方法

1.1 布谷鸟算法原理

自然界中，布谷鸟自己不做窝，不会孵化，也不会育雏，而是通过寻找质优的宿主巢窝，将其卵产在宿主的鸟巢中，让宿主代为孵化和育雏。大布谷鸟在产卵前，通常会把宿主一枚或数枚卵移走，使得巢穴中的卵数量相等或相近,一旦靠养母孵化的雏鸟孵出，布谷鸟有将养母本身的雏鸟推出巢外的本性，从而独享养母抚养，大大增加自己成活的概率，最大限度地提高其成功繁殖的能力。CS算法中，布谷鸟的卵代表一种新的、潜在比较好的解决方案，来代替这个原有的、可能没那么好的解决方案[13]。

CS算法是一种随机全局搜索算法，通过莱维飞行随机游走的方式，步长较小的短距离行走与偶尔较大步长的长距离行走相互交替，搜索得到一个最优的鸟窝来孵化自己的鸟蛋，这种方式可以达到一种高效的寻优模式。莱维飞行在搜索前期采用大步长用于探索发现，有利于增加种群多样性，并扩大搜索范围，不至于陷入局部最优；在搜索后期，采用小步长，有助于提高搜索精度，使得群体在小范围内收敛于全局最优解[13-15]。

在自然界中，布谷鸟以随机的或类似随机的方式寻找适合自己产卵的鸟窝位置，为了便于模拟布谷鸟的寻窝行为，CS算法设定以下3个理想状态[13]：①一只布谷鸟一次只产一个卵，并随机选择寄生巢进行孵化；②在随机选择的寄生巢中，最好的寄生巢会被保留到下一代；③可利用的寄生巢数量是固定的，被宿主发现的概率为pa,pa∈[0,1]。若宿主发现，则宿主会将布谷鸟的卵推出巢外，或抛弃该巢。

1.2 基于布谷鸟算法的遥感分类方法

1.2.1 分类规则构造

遥感影像分类规则挖掘的关键在于搜索遥感影像各波段的最优判定区间，即在多维空间搜索最优分割阈值，即多目标值的最优化问题。遥感影像分类中，定义分类规则为遥感影像各波段判断范围的最优分割点和地物类型节点的连线，其中各波段最优区间最多只出现一次，且必须有地物类型节点。每条分类规则对应一条搜索路径，分类规则的挖掘相当于是对最优路径的搜索，即最优分割阈值的求解。遥感影像分类规则的格式如下

IfX1lowlt;Band1lt;X1up…AndXjlowlt;Bandjlt;Xjup
Then Class=Classi

(1)

式中，If部分为分类规则的条件项；Then部分为分类规则的结论项，即分类类别；Xjlow为波段最优区间的下界阈值；Xjup为波段最优区间的上界阈值,j=1,2,…,k,k为遥感影像波段的个数;Classi为地物类别，i=1,2,…,m，m为地物类别的个数。

基于CS算法的遥感影像分类规则挖掘本质上是多维空间上的优化求解过程，CS算法在每一维空间上具有等价性，要求每一维样本数据具有相同的数值范围。遥感影像各波段的连续值和离散值都要求进行归一化处理，归一化后各波段数据范围为[0,1]。

1.2.2 分类规则挖掘

基于CS算法的遥感影像分类规则挖掘的最终目的是搜索遥感影像各波段判断区间最优上界和最优下界。在标准布谷鸟算法中，一只布谷鸟一次只产一个卵，一只卵对应一个鸟窝[13]。假设鸟窝(卵、布谷鸟)总数为n，遥感影像波段数为k,个体向量维度为D=2k，则X=X1,X2,…,Xi,…,Xn，代表一个布谷鸟种群，用X(0)表示初始的布谷鸟种群，X(t)表示第t代布谷鸟种群。利用布谷鸟搜索算法进行遥感影像分类规则挖掘的主要步骤如下：

(1) 对于t=0时刻，随机生成n个鸟窝的初始位置，初始化计算公式为

(2)

(2) 选择适应度函数，并计算每个鸟窝位置(解向量)的目标函数值，得到当前的最优函数值。分类规则的适应度用来衡量鸟窝位置的优劣，合理地构造适应度函数是分类规则挖掘的关键。本文的适应度函数如下

(3)

式中，TP为满足规则，且与规则预测类型一致的样本数；FP为满足规则，且与规则预测不一致的样本数；TN为不满足规则，且与规则预测不一致的样本数；FN为不满足规则，且与规则预测一致的样本数。

(3) 对于第t步的可行解，使用莱维飞行方式更新布谷鸟寻优搜索的位置，具体搜索公式如下

(4)

使用式(4)计算更新位置后的目标函数值，比较现有位置函数值与上一代最优函数值，选取具有更优适应度的保留给下一代的布谷鸟种群，从而保证布谷鸟种群能保留精英个体，朝更优适应度值的方向进化。

当全局最优适应度值达到一定的稳定值或迭代次数达到最大迭代次数，则循环终止，输出全局最优位置向量和相应的适应度值，并按式(1)格式构造分类规则；否则，返回步骤(2)，继续进行搜索。

获取一条分类规则后，对规则进行修剪，除去对分类结果贡献不大的条件项，提高分类规则的有效性，避免规则对样本数据的过度拟合。同时，移除满足当前规则且分类正确的样本数据，继续搜索下一条分类规则。当某地类的分类规则样本覆盖度，即满足规则且分类正确的样本数/该地物类别样本数，达到一定阈值时，终止该地物类别的规则挖掘，开始下一地物类别的规则挖掘，直至所有地物类别的规则挖掘完毕。基于布谷鸟算法的遥感分类规则挖掘的伪代码如下：

Input training dataset/*导入训练样本数据*/

Initialize control parameters /*初始化控制参数*/

Normalize SampleSet;/*归一化训练样本数据*/

forObjectClass=1:m /*依次为每个类型搜索规则*/

rulecount=1;

whileremoveCover lt; Max_cover

InitialRule(SampleSet, n, k); /*步骤1*/

Cal_fitness_get_best(rule, ObjectClass); /*步骤2*/

N_iter=0;

whileN_iter lt; Max_Iter

first_update_strategy(rules,best_rule); /*步骤3*/

Cal_fitness_get_best(rule, ObjectClass);

second_update_strategy(rules,Pa); /*步骤4*/

Cal_fitness_get_best(rule, ObjectClass);

end

PruningRule(best_rule,fmax,ObjectClass); /*修剪规则*/

Re_normalize(best_rule);/*分类规则的逆归一化*/

SaveRule(best_rule,fmax,ObjectClass);/*输出规则*/

RefreshSamples(best_rule,ObjectClass);/*刷新样本*/

rulecount=rulecount+1;

end

end

2 试验研究

试验使用ALOS影像(1995×2000像素)如图1(a)所示，经全色波段与多光谱波段融合后，影像空间分辨率为2.5 m，共有蓝色、绿色、红色和近红外4个波段，同时提取了1个光谱特征(植被指数NDVI)和8个纹理特征(均值、方差、一致性、对比度、非相似度、熵、二阶矩阵、灰度相关)作为影像分类的属性依据，每个特征作为一个波段，试验数据共有13个波段属性。挖掘分类规则时，对试验数据进行均匀采样，获取了10 000个样本数据,其中，5000个样本数据用于训练分类规则，剩余的5000个样本数据用于测试分类规则。在Matlab平台中，编程实现训练样本数据的分类规则挖掘，并根据所挖掘的分类规则对遥感影像进行分类。设置初始化参数如下：鸟窝(卵、布谷鸟)总数n=200，地物类别的个数m=6，遥感影像波段数k=13，宿主发现概率pa=0.25，最大迭代次数Max_Iter=2500，样本覆盖度Max_cover=0.95，共获得b9条分类规则，部分分类规则如下：

Rule1:

IF Band2gt;95 and Band2lt;=111 and Band3gt;121 and Band4gt;57 and Band4lt;=72 and Band7gt;2 and Band10gt;2 and Band10lt;=4

THENclass=Road confidence=0.786

Rule2:

IF Band1lt;=58 and Band3lt;=94 and Band4gt;64 and Band4lt;=70 and Band6gt;10 and Band7lt;=3 and Band9gt;2 and Band10lt;=2

THENclass=water confidence=0.762

使用所挖掘的分类规则，对试验区遥感影像进行分类，CS分类结果如图1(b)所示，结合实地调查，该分类结果比较真实地反映了实际的土地利用覆盖类型。在试验影像范围内随机均匀选取10 000个点，计算影像的分类精度(见表1)，CS遥感分类方法的总体精度为85.36%，Kappa系数为0.822。

图1 影像分类方法结果

类名实际/像素分类/像素判断正确/像素生产精度/(%)用户精度/(%)公路13621412118787．1584．07水域17561874156288．9583．35耕地23402296198684．8786．50建设用地21872108182883．5886．72林草地1124117697887．0183．16其他1231113499580．8387．74总和10000100008536——总体分类精度：85．36% Kappa系数=0．822

同时，为便于对比分析遥感分类精度，对相同的训练样本数据，使用蜂群遥感分类(ABC)、See5.0决策树方法获取分类规则，并对试验区相同影像进行了分类[12]，对比分析影像分类精度见表2，可见3种方法的精度有一定的差异，CS遥感分类方法具有更高的分类精度，其分类效果更好。

表2 影像分类精度对比分析

3 结束语

智能计算方法智能挖掘遥感影像分类规则，搜索遥感影像各波段最优分类区间，将遥感影像分类问题转化成多维个体向量的优化问题，该智能式遥感影像分类方法能有效提高复杂地物分类精度。布谷鸟搜索算法是一种结合布谷鸟巢寄生性和莱维飞行模式的群智能搜索算法，通过随机游走的方式搜索得到一个最优的鸟窝来孵化鸟蛋，具有参数少、易实现、随机搜索路径优和寻优能力强等优点。本文将布谷鸟搜索算法引进到遥感影像分类中，通过模仿布谷鸟巢寄生行为的方式，搜索遥感影像各波段的最优分类区间，以If-Then表达形式构造遥感分类规则。并且以ALOS遥感影像分类为例，分别应用布谷鸟遥感分类方法、蜂群智能遥感分类和See5.0决策树方法对影像进行了分类，并对比分析了3种方法的分类精度。通过本文理论分析和实例验证得出结论，应用布谷鸟算法进行遥感影像分类方法是可行的，所挖掘的分类规则能够更清晰地描述复杂地物分类中的非线性关系，能够提高分类精度。

[1] 杜培军.遥感原理与应用[M].徐州:中国矿业大学出版社,2006.

[2] 贾永红.人工神经网络在多源遥感影像分类中的应用[J].测绘通报,2000(7):7-8.

[3] 申文明,王文杰,罗海江,等.基于决策树分类技术的遥感影像分类方法研究[J].遥感技术与应用,2007,22(3):336-337.

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

[5] 谭琨,杜培军. 基于再生核Hilbert空间小波核函数支持向量机的高光谱遥感影像分类[J]. 测绘学报, 2011,40(2):143-147.

[6] 陈云浩,冯通,史培军,等.基于面向对象和规则的遥感影像分类研究[J].武汉大学学报(自然科学版), 2006, 31(4):316-320.

[7] STATHAKIS D，VASILAKOS A. Comparisons of Computational Intelligence Based Classification Techniques for Remotely Sensed Optical Image Classification[J]. IEEE Transactions on Geoscience and Remote Sensing, 2006, 44(8):2305-2318.

[8] SIPPER M. Machine Nature: The Coming Age of Bio-inspired Computing[M]. New York: McGraw-Hill, 2002.

[9] 刘小平,黎夏,何晋强,等.基于蚁群智能的遥感影像分类新方法[J].遥感学报,2008, 12(2):253-262.

[10] LIU Xiaoping, LI Xia, LIU Liu, et al. An Innovative Method to Classify Remote-Sensing Images Using Ant Colony Optimization [J].IEEE Transactions on Geoscience and Remote Sensing, 2008, 46(12): 4198-4208.

[11] 刘小平,黎夏,彭晓鹃,等.一种基于生物群集智能优化的遥感分类方法[J].中国科学(D辑：地球科学), 2007, 37(10): 1400-1408.

[12] 曹敏,史照良,阳建逸. 蜂群智能算法的遥感影像分类方法[J].测绘学报,2013, 42(5): 745-751.

[13] YANG X S, DEB S.Cuckoo Search via Lévy Flights, Proceedings of World Congress on Nature and Biologically Inspired Computing (NaBIC 2009)[M]. [S.l.]: IEEE Publications, 2009: 210-214.

[14] YANG X S. Swarm Intelligence Based Algorithms: A Critical Analysis[J]. Evolutionary Intelligence, 2014, 7: 17-28.

[15] YANG X S, DEB S. Cuckoo Search: Recent Advances and Applications[J]. Neural Computing and Applications, 2014, 24: 169-174.

[16] MANIKANDAN P, SELVARAJAN S. Data Clustering Using Cuckoo Search Algorithm (CSA)[J]. Advances in Intelligent Systems and Computing, 2014, 236: 1275-1283.

[17] LIU Xinni. Application of Cckoo Search Agorithm in Multi-threshold Image Segmentation [J]. Computer Engineering, 2013, 39(7): 274-278.

IntelligentRemoteSensingClassificationBasedonCuckooSearchAlgorithm

SHEN Quanfei1,CAO Min2,SHI Zhaoliang3,XU Ruqi2

(1. Provincial Fundamental Geomatics Centre of Jiangsu, Nanjing 210013, China; 2. College of Geographic Science, Nanjing Normal University, Nanjing 210023, China; 3. Jiangsu Provincial Bureau of Surveying,Mapping and Geoinformation, Nanjing 210013, China)

A new, intelligent approach to classify remote-sensing images based on Cuckoo search algorithm is presented. Cuckoo search algorithm, a new bio-inspired intelligence algorithm, is widely used to solve optimization problems. Cuckoo search algorithm to search for the optimal upper and lower threshold values on each band of remote-sensing image is applied. The classification rules are constructed by the links between the optimal split values and classification type in the explicit formation of 'if-then', and each link corresponds to the optimal solution of one Cuckoo, nest or egg. By taking an example of ALOS image in the north shore of the Yangtze River estuary, the proposed classification method based on CS algorithm is implemented and tested against See5.0 decision-tree method. The overall classification accuracy and Kappa coefficient of CS-based method are higher than the See5.0 decision-tree one. The results demonstrate that the practicability of applying CS algorithm to classify the remote-sensing images.

cuckoo search algorithm (CS); swarm intelligence caculation; remote sensing image; classification

P237

A

0494-0911(2017)01-0065-04

沈泉飞，曹敏，史照良,等.基于布谷鸟算法的遥感影像智能分类[J].测绘通报，2017(1)：65-68.

10.13474/j.cnki.11-2246.2017.0014.

2015-10-27；

2016-06-28

国家自然科学基金(41101349)；江苏省高校自然科学基础研究项目(13KJB420003); 江苏高校优势学科建设工程资助项目(PAPD)

沈泉飞(1980—)，男，硕士，工程师，研究方向为遥感影像处理。E-mail: sqf1980@126.com

曹 敏