高光谱图像波段选择的改进二进制布谷鸟算法

宋广钦，杜正舜，贺 智

(1. 中山大学地理科学与规划学院综合地理信息研究中心，广东 广州 510275; 2. 广东省城市化与地理环境空间模拟重点实验室，广东 广州 510275)

高光谱遥感是当今遥感技术的前沿，与多光谱遥感相比，其具有独特的光谱分辨率(通常达到10 nm或更精细数量级)，能准确区分地物的细微差异，具有准确识别地物类型的潜能。目前高光谱遥感图像已广泛应用于多个领域，如地质勘探、精准农业和军事用途[1]。但是，高光谱图像波段多且波段之间具有较高的冗余性，易产生Hughes现象，不利于后续处理[2]，对高光谱图像进行降维处理显得尤为重要。剔除冗余和噪声波段，选择在图像中起主要作用且相关性较低的波段，能在保证地物识别精度的前提下有效提高计算速度[3]。因此，波段选择是高光谱数据降维的主要途径之一，探究波段选择方法对高光谱遥感图像处理研究有着重要意义。

常用的波段特征选择算法主要有Relief算法和最小冗余最大相关算法(minimum redundancy maximum relevance,mRMR)。其中，Relief算法通过计算特征与类别相关程度的权重进行波段选择，该算法较为简单且运行效率高，但不能有效去除冗余特征[4]。mRMR算法通过计算特征与类别最大相关性，以及特征与特征之间最小冗余性来进行特征选择，但获得的结果难以反映不同特征对分类作用的差异[5]。为了更好地解决复杂的目标寻优问题，有学者提出了通过模拟生物行为习惯或自然现象的仿生智能算法[6]，如遗传算法(genetic algorithm,GA)[7]、蚁群算法(ant colony optimization,ACO)[8]、粒子群算法(particle swarm optimization,PSO)[9]、布谷鸟算法(cuckoo search,CS)[10]等。其中，CS算法的参数较少且稳健性较强，具有较好的寻优能力[11]。为了应用CS算法解决离散型目标寻优问题，有学者提出了二进制布谷鸟算法(binary cuckoo search，BCS)[12]。在高光谱降维研究中，有学者应用BCS算法进行波段选择实现降维并取得较好的试验结果[13]，但是BCS算法存在后期不能很好均衡全局性与收敛性及后期搜索效率低等缺点[14]。

基于以有研究，本文从两方面对现有BCS进行改进：①使用混合二进制编码算法更新子代鸟巢；②通过遗传交叉更新被发现鸟巢位置，得到改进二进制布谷鸟算法(improved binary cuckoo search，IBCS)并运用于高光谱图像波段选择，然后与BCS算法及其他常用智能算法进行对比分析。

1 改进二进制布谷鸟算法波段选择方法

1.1 标准布谷鸟算法

CS是由文献[10]于2009年结合布谷鸟种类的巢寄生繁殖行为和Levy飞行特征提出的一种全局搜索算法。该方法采用Levy飞行游走及偏好随机游走方式，使得全局搜索和局部搜索能力得到平衡，从而具有较好的寻优能力。在繁殖期间，布谷鸟会随机选择鸟巢进行产蛋，寻找鸟巢的游走方式是较短距离与偶尔长距离交替进行，搜索得到最优的鸟巢来对鸟蛋进行孵化，以达到高效的寻优效果。

CS算法为了更好拟合布谷鸟的巢寄生繁殖行为，假设了以下3个理想状态：

(1) 每只布谷鸟只对应一个鸟巢和一个蛋，并且随机选择鸟巢。

(2) 在所有随机选择的鸟巢中，最优质的鸟巢会被保留给下一代。

(3) 可利用的鸟巢总数不变，鸟巢中的布谷鸟蛋被宿主发现的概率为Pa，Pa∈[0,1]。宿主发现后，会舍弃该鸟巢。

基于以上3个理想状态，布谷鸟使用Levy飞行模式更新寻优鸟巢位置的公式如下

(1)

1.2 标准二进制布谷鸟算法的波段选择

假设鸟巢总数为n，高光谱遥感图像波段数为d，X=X1,X2,…,Xn代表一个布谷鸟种群，X(0)表示初始布谷鸟种群，X(t)表示第t代布谷鸟种群，波段集合b=b1,b2,…,bd代表高光谱数据集D中的d个特征波段，x=(x1,x2,…,xd)为二进制向量，xi∈(0,1)，基于BCS进行高光谱遥感图像波段选择主要步骤如下：

(1) 初始化n个原始鸟巢。在t=0时刻对n个鸟巢进行初始化并对第1～d个波段进行二进制编码。初始化公式为

xi=random{0,1}

(2)

式中，random0,1代表随机产生0或1。xi=1表示第i个波段被选择，反之，xi=0表示第i个波段未被选择。

(2) 计算种群鸟巢适应度。选择适应度函数并计算每一个鸟巢的适应度值，得到当前的最优适应度值。由于鸟巢的适应度值可用来判断鸟巢的优劣程度，因此构造合适的适应度函数是筛选出最优鸟巢的关键步骤。本文使用的适应度函数如下

(3)

式中，overall是分类器对鸟巢中所选择的波段进行分类得到的总体精度，本文采用支持向量机(support vector machine,SVM)[15]作为分类器；bands为鸟巢中所选择的波段数目；λ为控制系数。

(3) 更新群体鸟巢位置。对于第t步的可行解，使用Levy飞行的二进制变换公式进行位置更新。再次对更新位置后的鸟巢进行适应度计算，并且与上一代最优适应度值进行对比，保留具有更优适应度值的鸟巢，从而使得鸟巢的更新是朝着更优质鸟巢的位置方向进行。

(4) 更新被发现鸟巢。位置更新后，将(0,1)范围的随机数r与宿主发现概率Pa进行对比，Pa∈[0,1]。若r>Pa，则使用步骤(1)中初始化方法对鸟巢位置进行随机更新，反之则不变，比较后保留最优质的鸟巢。

当迭代次数到达设定次数时，终止循环，输出全局最优的鸟巢，该鸟巢所选择的特征即为算法最终筛选出的目标波段。算法操作流程图如图1所示。

1.3 改进二进制布谷鸟算法的波段选择

本文对标准二进制布谷鸟算法中的更新子代鸟巢位置方式和更新被发现鸟巢位置方式进行改进，使用混合二进制编码更新子代鸟巢并使用遗传交叉方式更新被发现鸟巢位置(如图1的虚线框所示)。下面对这两方面的改进进行重点阐述。

1.3.1 使用混合二进制编码算法更新子代鸟巢

为了解决离散型寻优问题，有学者基于PSO算法提出了二进制粒子群算法(binary particle swarm optimization，BPSO)[16]。借鉴BPSO的构建方法，学者基于CS算法构建了Levy飞行的二进制公式[12]，得到BCS算法中子代鸟巢位置更新公式

(4)

(5)

文献[17]经分析BPSO算法后提出了优化后的BPSO变换公式。借鉴改进后BPSO变换公式，文献[18]得出了Levy飞行的二进制变换公式

当Step≤0时

(6)

(7)

当Step>0时

(8)

(9)

式(4)—式(9)中，k=1,2,…,N，N为种群数；i=1,2,…,d，d代表波段数；Sig(Step)为Sigmond函数，自变量为Levy飞行步长Step；rand()表示产生的随机数。

本文采用二进制编码混合更新方法。当仅使用式(4)、式(5)进行二进制编码更新时，算法全局性很强，但收敛性比较弱；仅使用式(6)、式(9)进行二进制编码更新时，算法全局性较弱，但收敛性较强[18]。为了平衡算法全局性与收敛性、提高的算法性能，本文在二进制编码更新过程中引入控制系数pr∈[0,1]。引入pr后的更新方法如下：

if rand()≤pr

使用式(1)、式(2)进行二进制编码更新

Else

If Step≤0

使用式(3)、式(4)进行二进制编码更新

Else

使用式(5)、式(6)进行二进制编码更新

在进行混合更新过程中，若pr较大，则IBCS算法的全局性会比较强；若pr较小，则IBCS的收敛性会比较强。通过调整该系数能较好地平衡IBCS的全局性和收敛性。

1.3.2 基于遗传交叉更新被发现鸟巢

在标准BCS中，当布谷鸟蛋被宿主发现时，布谷鸟会舍弃原有鸟巢并随机寻找新的鸟巢，但直接进行简单随机游走获得的新鸟巢位置并不理想。鉴于此，为了使BCS算法更新被发现鸟巢时能够更好地利用已有资源，本文基于遗传算法[19]中的交叉思想，利用现有资源交叉产生新的资源来选择被发现鸟巢的位置，从而提高寻优效率。

首先，对新发现的N个鸟巢的位置进行随机乱序操作并将结果暂存作为遗传父代染色体，然后重复上一次的操作，将原来N个鸟巢的位置再次进行随机乱序操作得到的结果暂存作为遗传母代染色体。通过随机数确定父代与母代交叉位置，交叉位置前面后的染色体部分进行交叉对调，获得新的子代。

本文使用(0,1)范围内的随机数作为是否进行交叉的判断。如果生成的(0,1)之间的随机数小于预定的交叉率，则父代和母代进行交叉，否则，使用偏好游走更新被发现鸟巢位置。

2 试验流程

2.1 数据介绍

试验所采用的高光谱数据集共有两个。一个数据集是来自ROSIS传感器的图像，图像覆盖区域为意大利的Pavia大学，由640×310个像元组成。该图像光谱范围为0.43—0.86 μm，共包括113个波段。地物真实图像包含9种类型的地物。

另一个数据集为印第安纳高光谱AVIRIS数据，图像覆盖区域为美国西北印第安纳州某农林混合试验场，由144×144个像元组成。AVIRIS获得的图像有224个波段，其光谱范围为0.41—2.45 μm。在去除水汽吸收波段和低信噪比波段之后，参加处理的波段为200个。该数据真实图像一共包含16类不同的地物。

两幅高光谱遥感图像均具有真实地物分类图像，在进行精度评价时，直接使用真实图像与分类图像进行对比分析，更准确获取分类后的总体精度。

2.2 参数设置

为了分析波段选择效果，将本文提出的IBCS与BCS算法、常用二进制智能算法(遗传算法(binary genetic algorithm,BGA)、BPSO、二进制蚁群算法(binary ant colony optimization,BACO))、mRMR算法、Relief算法进行对比。每个智能算法的循环迭代次数均设置为100次，具体参数设置如下：在BGA算法中，种群大小Numpop=15，选择率Selectrate=0.5，变异率Variationrate=0.1，杂交率Crossrate=0.5；在BPSO算法中，粒子种群数N=15，加速常数C1=C2=2，粒子权重w=0.5；在BACO算法中，蚂蚁数量N=15，信息素重要程度α=1，能见度β=0.0、3.0，信息素挥发ρ=0.5，信息素增强度Q=0.7。为了保证比较的一致性，对于两种常用算法mRMR和Relief波段数本文设置为与IBCS所选出的相同。

通过对IBCS的介绍可知，该算法包含5个参数，即初始鸟窝数量Nest、宿主鸟发现寄生鸟蛋的概率Pa、进制控制系数Pr、杂交率Crossrate及迭代次数Iter。初始鸟窝数量和宿主鸟发现外来鸟蛋的概率大小对算法的搜索速度及收敛性有影响，杂交率和二进制控制系数决定了布谷鸟算法的搜索范围，以及能否跳出局部最优解。通过对IBCS的参数重复调试对比，本文所使用的参数如下：鸟巢总数Nest=15，发现概率Pa=0.5，二进制控制系数Pr=0.5，杂交率Crossrate=0.5，迭代次数Iter=100。

2.3 结果分析

试验环境为：Matlab R2016a平台，CPU 2.30 GHz，8 GB RAM，Windows 10操作系统。采用SVM为分类器，两个数据集的每类地物均随机选取10个像元为训练样本，分类结果分别如图2、图3和表1—表4所示。其中，图2、表1和表3为PaviaU数据结果，图3、表2和表4为AVIRIS数据结果。

表1 PaviaU数据集智能算法分类结果

表2 AVIRIS数据集智能算法分类结果

由表1和表2可知，使用基于IBCS及其他智能算法的SVM分类结果精度高于单一使用SVM分类。在所选的智能算法中，IBCS算法获得分类精度最高。其中，在Pavia数据集中，基于IBCS算法的分类精度得到显著提高，达到76.8%，比单纯使用SVM分类器的分类精度提升21.1%。对于PaviaU数据集及AVIRIS数据集，IBCS所选出的波段数分别为30和66，显著降低了待处理数据维度。试验结果说明IBCS算法能够有效降低高光谱维数并且提高分类结果精度。

图3 AVIRIS数据集分类结果

参数mRMRReliefIBCS总体精度0.5650.5070.768Kappa系数0.4840.4330.695

表4 AVIRIS数据集mRMR、Relief和IBCS算法分类结果

表1和表2的标准差为适应度的标准差，是指停止循环后所得到的多个解的标准差，可以用来反映智能算法最终的收敛性。由表1、表2可知，在试验所用的智能算法中IBCS的标准差最小，说明IBCS收敛效果最好。在同样迭代次数的情况下，IBCS耗时最短，说明IBCS具有更高的性能与更快的效率，是一种高效可靠的算法。

从表3和表4可以看出，在两个数据集中，基于IBCS算法选择的目标波段更具优势，精度及Kappa系数相对于mRMR和Relief算法有所提高。结果表明IBCS算法具有更强的稳健性，优化效果更好。

3 结 语

本文提出了改进二进制布谷鸟算法对高光谱图像进行降维，在BCS算法基础上进行两方面改进：①使用混合二进制编码更新子代鸟巢均衡算法的全局性与收敛性；②使用遗传交叉更新被发现鸟巢，加强利用已有资源提升算法寻优效率。试验结果表明，IBCS与BCS、BGA、BPSO、BACO智能算法相比，具有能够有效降低数据维度、后续分类精度更高、寻优效率更高等优点。相对于mRMR算法、RRelief算法，IBCS算法选择的波段对高光谱图像分类作用更大，能够更好地提高分类精度。