高光譜圖像波段選擇的改進(jìn)二進(jìn)制布谷鳥算法

宋廣欽，杜正舜，賀 智

(1. 中山大學(xué)地理科學(xué)與規(guī)劃學(xué)院綜合地理信息研究中心，廣東 廣州 510275; 2. 廣東省城市化與地理環(huán)境空間模擬重點(diǎn)實(shí)驗(yàn)室，廣東 廣州 510275)

高光譜遙感是當(dāng)今遙感技術(shù)的前沿，與多光譜遙感相比，其具有獨(dú)特的光譜分辨率(通常達(dá)到10 nm或更精細(xì)數(shù)量級(jí))，能準(zhǔn)確區(qū)分地物的細(xì)微差異，具有準(zhǔn)確識(shí)別地物類型的潛能。目前高光譜遙感圖像已廣泛應(yīng)用于多個(gè)領(lǐng)域，如地質(zhì)勘探、精準(zhǔn)農(nóng)業(yè)和軍事用途[1]。但是，高光譜圖像波段多且波段之間具有較高的冗余性，易產(chǎn)生Hughes現(xiàn)象，不利于后續(xù)處理[2]，對(duì)高光譜圖像進(jìn)行降維處理顯得尤為重要。剔除冗余和噪聲波段，選擇在圖像中起主要作用且相關(guān)性較低的波段，能在保證地物識(shí)別精度的前提下有效提高計(jì)算速度[3]。因此，波段選擇是高光譜數(shù)據(jù)降維的主要途徑之一，探究波段選擇方法對(duì)高光譜遙感圖像處理研究有著重要意義。

常用的波段特征選擇算法主要有Relief算法和最小冗余最大相關(guān)算法(minimum redundancy maximum relevance,mRMR)。其中，Relief算法通過(guò)計(jì)算特征與類別相關(guān)程度的權(quán)重進(jìn)行波段選擇，該算法較為簡(jiǎn)單且運(yùn)行效率高，但不能有效去除冗余特征[4]。mRMR算法通過(guò)計(jì)算特征與類別最大相關(guān)性，以及特征與特征之間最小冗余性來(lái)進(jìn)行特征選擇，但獲得的結(jié)果難以反映不同特征對(duì)分類作用的差異[5]。為了更好地解決復(fù)雜的目標(biāo)尋優(yōu)問(wèn)題，有學(xué)者提出了通過(guò)模擬生物行為習(xí)慣或自然現(xiàn)象的仿生智能算法[6]，如遺傳算法(genetic algorithm,GA)[7]、蟻群算法(ant colony optimization,ACO)[8]、粒子群算法(particle swarm optimization,PSO)[9]、布谷鳥算法(cuckoo search,CS)[10]等。其中，CS算法的參數(shù)較少且穩(wěn)健性較強(qiáng)，具有較好的尋優(yōu)能力[11]。為了應(yīng)用CS算法解決離散型目標(biāo)尋優(yōu)問(wèn)題，有學(xué)者提出了二進(jìn)制布谷鳥算法(binary cuckoo search，BCS)[12]。在高光譜降維研究中，有學(xué)者應(yīng)用BCS算法進(jìn)行波段選擇實(shí)現(xiàn)降維并取得較好的試驗(yàn)結(jié)果[13]，但是BCS算法存在后期不能很好均衡全局性與收斂性及后期搜索效率低等缺點(diǎn)[14]。

基于以有研究，本文從兩方面對(duì)現(xiàn)有BCS進(jìn)行改進(jìn)：①使用混合二進(jìn)制編碼算法更新子代鳥巢；②通過(guò)遺傳交叉更新被發(fā)現(xiàn)鳥巢位置，得到改進(jìn)二進(jìn)制布谷鳥算法(improved binary cuckoo search，IBCS)并運(yùn)用于高光譜圖像波段選擇，然后與BCS算法及其他常用智能算法進(jìn)行對(duì)比分析。

1 改進(jìn)二進(jìn)制布谷鳥算法波段選擇方法

1.1 標(biāo)準(zhǔn)布谷鳥算法

CS是由文獻(xiàn)[10]于2009年結(jié)合布谷鳥種類的巢寄生繁殖行為和Levy飛行特征提出的一種全局搜索算法。該方法采用Levy飛行游走及偏好隨機(jī)游走方式，使得全局搜索和局部搜索能力得到平衡，從而具有較好的尋優(yōu)能力。在繁殖期間，布谷鳥會(huì)隨機(jī)選擇鳥巢進(jìn)行產(chǎn)蛋，尋找鳥巢的游走方式是較短距離與偶爾長(zhǎng)距離交替進(jìn)行，搜索得到最優(yōu)的鳥巢來(lái)對(duì)鳥蛋進(jìn)行孵化，以達(dá)到高效的尋優(yōu)效果。

CS算法為了更好擬合布谷鳥的巢寄生繁殖行為，假設(shè)了以下3個(gè)理想狀態(tài)：

(1) 每只布谷鳥只對(duì)應(yīng)一個(gè)鳥巢和一個(gè)蛋，并且隨機(jī)選擇鳥巢。

(2) 在所有隨機(jī)選擇的鳥巢中，最優(yōu)質(zhì)的鳥巢會(huì)被保留給下一代。

(3) 可利用的鳥巢總數(shù)不變，鳥巢中的布谷鳥蛋被宿主發(fā)現(xiàn)的概率為Pa，Pa∈[0,1]。宿主發(fā)現(xiàn)后，會(huì)舍棄該鳥巢。

基于以上3個(gè)理想狀態(tài)，布谷鳥使用Levy飛行模式更新尋優(yōu)鳥巢位置的公式如下

(1)

1.2 標(biāo)準(zhǔn)二進(jìn)制布谷鳥算法的波段選擇

假設(shè)鳥巢總數(shù)為n，高光譜遙感圖像波段數(shù)為d，X=X1,X2,…,Xn代表一個(gè)布谷鳥種群，X(0)表示初始布谷鳥種群，X(t)表示第t代布谷鳥種群，波段集合b=b1,b2,…,bd代表高光譜數(shù)據(jù)集D中的d個(gè)特征波段，x=(x1,x2,…,xd)為二進(jìn)制向量，xi∈(0,1)，基于BCS進(jìn)行高光譜遙感圖像波段選擇主要步驟如下：

(1) 初始化n個(gè)原始鳥巢。在t=0時(shí)刻對(duì)n個(gè)鳥巢進(jìn)行初始化并對(duì)第1～d個(gè)波段進(jìn)行二進(jìn)制編碼。初始化公式為

xi=random{0,1}

(2)

式中，random0,1代表隨機(jī)產(chǎn)生0或1。xi=1表示第i個(gè)波段被選擇，反之，xi=0表示第i個(gè)波段未被選擇。

(2) 計(jì)算種群鳥巢適應(yīng)度。選擇適應(yīng)度函數(shù)并計(jì)算每一個(gè)鳥巢的適應(yīng)度值，得到當(dāng)前的最優(yōu)適應(yīng)度值。由于鳥巢的適應(yīng)度值可用來(lái)判斷鳥巢的優(yōu)劣程度，因此構(gòu)造合適的適應(yīng)度函數(shù)是篩選出最優(yōu)鳥巢的關(guān)鍵步驟。本文使用的適應(yīng)度函數(shù)如下

(3)

式中，overall是分類器對(duì)鳥巢中所選擇的波段進(jìn)行分類得到的總體精度，本文采用支持向量機(jī)(support vector machine,SVM)[15]作為分類器；bands為鳥巢中所選擇的波段數(shù)目；λ為控制系數(shù)。

(3) 更新群體鳥巢位置。對(duì)于第t步的可行解，使用Levy飛行的二進(jìn)制變換公式進(jìn)行位置更新。再次對(duì)更新位置后的鳥巢進(jìn)行適應(yīng)度計(jì)算，并且與上一代最優(yōu)適應(yīng)度值進(jìn)行對(duì)比，保留具有更優(yōu)適應(yīng)度值的鳥巢，從而使得鳥巢的更新是朝著更優(yōu)質(zhì)鳥巢的位置方向進(jìn)行。

(4) 更新被發(fā)現(xiàn)鳥巢。位置更新后，將(0,1)范圍的隨機(jī)數(shù)r與宿主發(fā)現(xiàn)概率Pa進(jìn)行對(duì)比，Pa∈[0,1]。若r>Pa，則使用步驟(1)中初始化方法對(duì)鳥巢位置進(jìn)行隨機(jī)更新，反之則不變，比較后保留最優(yōu)質(zhì)的鳥巢。

當(dāng)?shù)螖?shù)到達(dá)設(shè)定次數(shù)時(shí)，終止循環(huán)，輸出全局最優(yōu)的鳥巢，該鳥巢所選擇的特征即為算法最終篩選出的目標(biāo)波段。算法操作流程圖如圖1所示。

1.3 改進(jìn)二進(jìn)制布谷鳥算法的波段選擇

本文對(duì)標(biāo)準(zhǔn)二進(jìn)制布谷鳥算法中的更新子代鳥巢位置方式和更新被發(fā)現(xiàn)鳥巢位置方式進(jìn)行改進(jìn)，使用混合二進(jìn)制編碼更新子代鳥巢并使用遺傳交叉方式更新被發(fā)現(xiàn)鳥巢位置(如圖1的虛線框所示)。下面對(duì)這兩方面的改進(jìn)進(jìn)行重點(diǎn)闡述。

1.3.1 使用混合二進(jìn)制編碼算法更新子代鳥巢

為了解決離散型尋優(yōu)問(wèn)題，有學(xué)者基于PSO算法提出了二進(jìn)制粒子群算法(binary particle swarm optimization，BPSO)[16]。借鑒BPSO的構(gòu)建方法，學(xué)者基于CS算法構(gòu)建了Levy飛行的二進(jìn)制公式[12]，得到BCS算法中子代鳥巢位置更新公式

(4)

(5)

文獻(xiàn)[17]經(jīng)分析BPSO算法后提出了優(yōu)化后的BPSO變換公式。借鑒改進(jìn)后BPSO變換公式，文獻(xiàn)[18]得出了Levy飛行的二進(jìn)制變換公式

當(dāng)Step≤0時(shí)

(6)

(7)

當(dāng)Step>0時(shí)

(8)

(9)

式(4)—式(9)中，k=1,2,…,N，N為種群數(shù)；i=1,2,…,d，d代表波段數(shù)；Sig(Step)為Sigmond函數(shù)，自變量為L(zhǎng)evy飛行步長(zhǎng)Step；rand()表示產(chǎn)生的隨機(jī)數(shù)。

本文采用二進(jìn)制編碼混合更新方法。當(dāng)僅使用式(4)、式(5)進(jìn)行二進(jìn)制編碼更新時(shí)，算法全局性很強(qiáng)，但收斂性比較弱；僅使用式(6)、式(9)進(jìn)行二進(jìn)制編碼更新時(shí)，算法全局性較弱，但收斂性較強(qiáng)[18]。為了平衡算法全局性與收斂性、提高的算法性能，本文在二進(jìn)制編碼更新過(guò)程中引入控制系數(shù)pr∈[0,1]。引入pr后的更新方法如下：

if rand()≤pr

使用式(1)、式(2)進(jìn)行二進(jìn)制編碼更新

Else

If Step≤0

使用式(3)、式(4)進(jìn)行二進(jìn)制編碼更新

Else

使用式(5)、式(6)進(jìn)行二進(jìn)制編碼更新

在進(jìn)行混合更新過(guò)程中，若pr較大，則IBCS算法的全局性會(huì)比較強(qiáng)；若pr較小，則IBCS的收斂性會(huì)比較強(qiáng)。通過(guò)調(diào)整該系數(shù)能較好地平衡IBCS的全局性和收斂性。

1.3.2 基于遺傳交叉更新被發(fā)現(xiàn)鳥巢

在標(biāo)準(zhǔn)BCS中，當(dāng)布谷鳥蛋被宿主發(fā)現(xiàn)時(shí)，布谷鳥會(huì)舍棄原有鳥巢并隨機(jī)尋找新的鳥巢，但直接進(jìn)行簡(jiǎn)單隨機(jī)游走獲得的新鳥巢位置并不理想。鑒于此，為了使BCS算法更新被發(fā)現(xiàn)鳥巢時(shí)能夠更好地利用已有資源，本文基于遺傳算法[19]中的交叉思想，利用現(xiàn)有資源交叉產(chǎn)生新的資源來(lái)選擇被發(fā)現(xiàn)鳥巢的位置，從而提高尋優(yōu)效率。

首先，對(duì)新發(fā)現(xiàn)的N個(gè)鳥巢的位置進(jìn)行隨機(jī)亂序操作并將結(jié)果暫存作為遺傳父代染色體，然后重復(fù)上一次的操作，將原來(lái)N個(gè)鳥巢的位置再次進(jìn)行隨機(jī)亂序操作得到的結(jié)果暫存作為遺傳母代染色體。通過(guò)隨機(jī)數(shù)確定父代與母代交叉位置，交叉位置前面后的染色體部分進(jìn)行交叉對(duì)調(diào)，獲得新的子代。

本文使用(0,1)范圍內(nèi)的隨機(jī)數(shù)作為是否進(jìn)行交叉的判斷。如果生成的(0,1)之間的隨機(jī)數(shù)小于預(yù)定的交叉率，則父代和母代進(jìn)行交叉，否則，使用偏好游走更新被發(fā)現(xiàn)鳥巢位置。

2 試驗(yàn)流程

2.1 數(shù)據(jù)介紹

試驗(yàn)所采用的高光譜數(shù)據(jù)集共有兩個(gè)。一個(gè)數(shù)據(jù)集是來(lái)自ROSIS傳感器的圖像，圖像覆蓋區(qū)域?yàn)橐獯罄腜avia大學(xué)，由640×310個(gè)像元組成。該圖像光譜范圍為0.43—0.86 μm，共包括113個(gè)波段。地物真實(shí)圖像包含9種類型的地物。

另一個(gè)數(shù)據(jù)集為印第安納高光譜AVIRIS數(shù)據(jù)，圖像覆蓋區(qū)域?yàn)槊绹?guó)西北印第安納州某農(nóng)林混合試驗(yàn)場(chǎng)，由144×144個(gè)像元組成。AVIRIS獲得的圖像有224個(gè)波段，其光譜范圍為0.41—2.45 μm。在去除水汽吸收波段和低信噪比波段之后，參加處理的波段為200個(gè)。該數(shù)據(jù)真實(shí)圖像一共包含16類不同的地物。

兩幅高光譜遙感圖像均具有真實(shí)地物分類圖像，在進(jìn)行精度評(píng)價(jià)時(shí)，直接使用真實(shí)圖像與分類圖像進(jìn)行對(duì)比分析，更準(zhǔn)確獲取分類后的總體精度。

2.2 參數(shù)設(shè)置

為了分析波段選擇效果，將本文提出的IBCS與BCS算法、常用二進(jìn)制智能算法(遺傳算法(binary genetic algorithm,BGA)、BPSO、二進(jìn)制蟻群算法(binary ant colony optimization,BACO))、mRMR算法、Relief算法進(jìn)行對(duì)比。每個(gè)智能算法的循環(huán)迭代次數(shù)均設(shè)置為100次，具體參數(shù)設(shè)置如下：在BGA算法中，種群大小Numpop=15，選擇率Selectrate=0.5，變異率Variationrate=0.1，雜交率Crossrate=0.5；在BPSO算法中，粒子種群數(shù)N=15，加速常數(shù)C1=C2=2，粒子權(quán)重w=0.5；在BACO算法中，螞蟻數(shù)量N=15，信息素重要程度α=1，能見(jiàn)度β=0.0、3.0，信息素?fù)]發(fā)ρ=0.5，信息素增強(qiáng)度Q=0.7。為了保證比較的一致性，對(duì)于兩種常用算法mRMR和Relief波段數(shù)本文設(shè)置為與IBCS所選出的相同。

通過(guò)對(duì)IBCS的介紹可知，該算法包含5個(gè)參數(shù)，即初始鳥窩數(shù)量Nest、宿主鳥發(fā)現(xiàn)寄生鳥蛋的概率Pa、進(jìn)制控制系數(shù)Pr、雜交率Crossrate及迭代次數(shù)Iter。初始鳥窩數(shù)量和宿主鳥發(fā)現(xiàn)外來(lái)鳥蛋的概率大小對(duì)算法的搜索速度及收斂性有影響，雜交率和二進(jìn)制控制系數(shù)決定了布谷鳥算法的搜索范圍，以及能否跳出局部最優(yōu)解。通過(guò)對(duì)IBCS的參數(shù)重復(fù)調(diào)試對(duì)比，本文所使用的參數(shù)如下：鳥巢總數(shù)Nest=15，發(fā)現(xiàn)概率Pa=0.5，二進(jìn)制控制系數(shù)Pr=0.5，雜交率Crossrate=0.5，迭代次數(shù)Iter=100。

2.3 結(jié)果分析

試驗(yàn)環(huán)境為：Matlab R2016a平臺(tái)，CPU 2.30 GHz，8 GB RAM，Windows 10操作系統(tǒng)。采用SVM為分類器，兩個(gè)數(shù)據(jù)集的每類地物均隨機(jī)選取10個(gè)像元為訓(xùn)練樣本，分類結(jié)果分別如圖2、圖3和表1—表4所示。其中，圖2、表1和表3為PaviaU數(shù)據(jù)結(jié)果，圖3、表2和表4為AVIRIS數(shù)據(jù)結(jié)果。

表1 PaviaU數(shù)據(jù)集智能算法分類結(jié)果

表2 AVIRIS數(shù)據(jù)集智能算法分類結(jié)果

由表1和表2可知，使用基于IBCS及其他智能算法的SVM分類結(jié)果精度高于單一使用SVM分類。在所選的智能算法中，IBCS算法獲得分類精度最高。其中，在Pavia數(shù)據(jù)集中，基于IBCS算法的分類精度得到顯著提高，達(dá)到76.8%，比單純使用SVM分類器的分類精度提升21.1%。對(duì)于PaviaU數(shù)據(jù)集及AVIRIS數(shù)據(jù)集，IBCS所選出的波段數(shù)分別為30和66，顯著降低了待處理數(shù)據(jù)維度。試驗(yàn)結(jié)果說(shuō)明IBCS算法能夠有效降低高光譜維數(shù)并且提高分類結(jié)果精度。

圖3 AVIRIS數(shù)據(jù)集分類結(jié)果

參數(shù)mRMRReliefIBCS總體精度0.5650.5070.768Kappa系數(shù)0.4840.4330.695

表4 AVIRIS數(shù)據(jù)集mRMR、Relief和IBCS算法分類結(jié)果

表1和表2的標(biāo)準(zhǔn)差為適應(yīng)度的標(biāo)準(zhǔn)差，是指停止循環(huán)后所得到的多個(gè)解的標(biāo)準(zhǔn)差，可以用來(lái)反映智能算法最終的收斂性。由表1、表2可知，在試驗(yàn)所用的智能算法中IBCS的標(biāo)準(zhǔn)差最小，說(shuō)明IBCS收斂效果最好。在同樣迭代次數(shù)的情況下，IBCS耗時(shí)最短，說(shuō)明IBCS具有更高的性能與更快的效率，是一種高效可靠的算法。

從表3和表4可以看出，在兩個(gè)數(shù)據(jù)集中，基于IBCS算法選擇的目標(biāo)波段更具優(yōu)勢(shì)，精度及Kappa系數(shù)相對(duì)于mRMR和Relief算法有所提高。結(jié)果表明IBCS算法具有更強(qiáng)的穩(wěn)健性，優(yōu)化效果更好。

3 結(jié) 語(yǔ)

本文提出了改進(jìn)二進(jìn)制布谷鳥算法對(duì)高光譜圖像進(jìn)行降維，在BCS算法基礎(chǔ)上進(jìn)行兩方面改進(jìn)：①使用混合二進(jìn)制編碼更新子代鳥巢均衡算法的全局性與收斂性；②使用遺傳交叉更新被發(fā)現(xiàn)鳥巢，加強(qiáng)利用已有資源提升算法尋優(yōu)效率。試驗(yàn)結(jié)果表明，IBCS與BCS、BGA、BPSO、BACO智能算法相比，具有能夠有效降低數(shù)據(jù)維度、后續(xù)分類精度更高、尋優(yōu)效率更高等優(yōu)點(diǎn)。相對(duì)于mRMR算法、RRelief算法，IBCS算法選擇的波段對(duì)高光譜圖像分類作用更大，能夠更好地提高分類精度。