基于布谷鳥算法的遙感影像智能分類

沈泉飛，曹 敏，史照良，許如琪

(1. 江蘇省基礎(chǔ)地理信息中心，江蘇 南京 210013; 2. 南京師范大學(xué)虛擬地理環(huán)境教育部重點實驗室，江蘇 南京 210023; 3. 江蘇省測繪地理信息局，江蘇 南京 210013)

基于布谷鳥算法的遙感影像智能分類

沈泉飛1，曹 敏2，史照良3，許如琪2

(1. 江蘇省基礎(chǔ)地理信息中心，江蘇 南京 210013; 2. 南京師范大學(xué)虛擬地理環(huán)境教育部重點實驗室，江蘇 南京 210023; 3. 江蘇省測繪地理信息局，江蘇 南京 210013)

提出了一種新的基于布谷鳥算法的智能式遙感分類方法。采用布谷鳥智能優(yōu)化算法，自動搜索遙感影像各波段的最優(yōu)閾值分割點，并定義各波段最優(yōu)閾值分割點和影像分類目標類別的連線為布谷鳥的最佳解，構(gòu)造以If-Then形式表達的遙感分類規(guī)則。將所提的基于布谷鳥算法的影像分類方法應(yīng)用于ALOS影像分類中，并與蜂群智能遙感分類方法和See5.0決策樹方法進行了對比分析。結(jié)果表明，布谷鳥智能遙感分類的總體精度和Kappa系數(shù)均比蜂群智能遙感分類和See5.0決策樹方法更高，該智能遙感分類方法具有更好的分類效果。

布谷鳥算法；仿生智能計算；遙感影像；分類

遙感影像分類一直是遙感影像處理的重要環(huán)節(jié)。傳統(tǒng)的統(tǒng)計分析分類方法如最大似然法、最短距離法、K-Means法、貝葉斯分類法等，以訓(xùn)練數(shù)據(jù)遵循正態(tài)分布為前提，訓(xùn)練樣本的選擇和參數(shù)估計會直接影響遙感影像分類結(jié)果[1]。隨后，學(xué)者們提出神經(jīng)網(wǎng)絡(luò)法[2]、決策樹分類法[3]、模糊分類法[4]、支持向量機分類法[5]和面向?qū)ο蠓诸惙╗6]，總體分類精度優(yōu)于傳統(tǒng)的統(tǒng)計分類方法，具有更好的彈性和穩(wěn)健性。當?shù)匚餇顩r非常復(fù)雜時，一般的遙感分類方法不能很好地處理線性不可分的地物，智能式的分類方法能夠為解決這一問題提供新的手段[7]。

仿生智能計算通過模擬生物的行為或自然界的現(xiàn)象來解決目標優(yōu)化問題，是計算智能領(lǐng)域的研究熱點方向之一[8]。目前，已經(jīng)有多種智能式遙感影像分類方法，如基于蟻群算法的遙感影像分類方法[9-10]、基于粒子群算法的遙感分類方法[11]、基于蜂群算法的遙感分類方法[12]等，這類智能式方法均取得了較好的分類效果。智能優(yōu)化算法仍然有提升的空間，如何提高土地利用分類精度仍是遙感領(lǐng)域的重要研究方向。

近年來，仿生智能計算領(lǐng)域出現(xiàn)了一種新型的元啟發(fā)式算法——布谷鳥算法(cuckoo search, CS)，它是由劍橋大學(xué)Xin-She Yang于2009年結(jié)合布谷鳥種類的巢寄生繁育行為和鳥類、果蠅等的萊維飛行(Lévy flight)行為特征，提出的一種新的全局搜索優(yōu)化算法[13]。該算法增加了群體之間的信息交流，具有控制參數(shù)少，能夠有效保持局部搜索和全局搜索之間平衡，加速收斂速度，易于實現(xiàn)等優(yōu)點[13-14]，已有研究表明該算法性能優(yōu)于粒子群算法和蜂群算法[14]。目前，布谷鳥算法已經(jīng)被廣泛應(yīng)用于多目標優(yōu)化[15]、數(shù)據(jù)聚類[16]、圖像分割[17]等領(lǐng)域，能夠有效地解決各種復(fù)雜優(yōu)化問題。本文以土地利用遙感分類為例，提出一種利用布谷鳥算法對遙感影像進行分類的新方法，通過模仿布谷鳥的巢寄生行為的方式，布谷鳥在多維空間中不斷地搜索各波段的最優(yōu)區(qū)間，將各波段最優(yōu)區(qū)間與土地利用類型連接，形成遙感影像的分類規(guī)則。

1 基于布谷鳥算法的遙感影像分類方法

1.1 布谷鳥算法原理

自然界中，布谷鳥自己不做窩，不會孵化，也不會育雛，而是通過尋找質(zhì)優(yōu)的宿主巢窩，將其卵產(chǎn)在宿主的鳥巢中，讓宿主代為孵化和育雛。大布谷鳥在產(chǎn)卵前，通常會把宿主一枚或數(shù)枚卵移走，使得巢穴中的卵數(shù)量相等或相近,一旦靠養(yǎng)母孵化的雛鳥孵出，布谷鳥有將養(yǎng)母本身的雛鳥推出巢外的本性，從而獨享養(yǎng)母撫養(yǎng)，大大增加自己成活的概率，最大限度地提高其成功繁殖的能力。CS算法中，布谷鳥的卵代表一種新的、潛在比較好的解決方案，來代替這個原有的、可能沒那么好的解決方案[13]。

CS算法是一種隨機全局搜索算法，通過萊維飛行隨機游走的方式，步長較小的短距離行走與偶爾較大步長的長距離行走相互交替，搜索得到一個最優(yōu)的鳥窩來孵化自己的鳥蛋，這種方式可以達到一種高效的尋優(yōu)模式。萊維飛行在搜索前期采用大步長用于探索發(fā)現(xiàn)，有利于增加種群多樣性，并擴大搜索范圍，不至于陷入局部最優(yōu)；在搜索后期，采用小步長，有助于提高搜索精度，使得群體在小范圍內(nèi)收斂于全局最優(yōu)解[13-15]。

在自然界中，布谷鳥以隨機的或類似隨機的方式尋找適合自己產(chǎn)卵的鳥窩位置，為了便于模擬布谷鳥的尋窩行為，CS算法設(shè)定以下3個理想狀態(tài)[13]：①一只布谷鳥一次只產(chǎn)一個卵，并隨機選擇寄生巢進行孵化；②在隨機選擇的寄生巢中，最好的寄生巢會被保留到下一代；③可利用的寄生巢數(shù)量是固定的，被宿主發(fā)現(xiàn)的概率為pa,pa∈[0,1]。若宿主發(fā)現(xiàn)，則宿主會將布谷鳥的卵推出巢外，或拋棄該巢。

1.2 基于布谷鳥算法的遙感分類方法

1.2.1 分類規(guī)則構(gòu)造

遙感影像分類規(guī)則挖掘的關(guān)鍵在于搜索遙感影像各波段的最優(yōu)判定區(qū)間，即在多維空間搜索最優(yōu)分割閾值，即多目標值的最優(yōu)化問題。遙感影像分類中，定義分類規(guī)則為遙感影像各波段判斷范圍的最優(yōu)分割點和地物類型節(jié)點的連線，其中各波段最優(yōu)區(qū)間最多只出現(xiàn)一次，且必須有地物類型節(jié)點。每條分類規(guī)則對應(yīng)一條搜索路徑，分類規(guī)則的挖掘相當于是對最優(yōu)路徑的搜索，即最優(yōu)分割閾值的求解。遙感影像分類規(guī)則的格式如下

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

(1)

式中，If部分為分類規(guī)則的條件項；Then部分為分類規(guī)則的結(jié)論項，即分類類別；Xjlow為波段最優(yōu)區(qū)間的下界閾值；Xjup為波段最優(yōu)區(qū)間的上界閾值,j=1,2,…,k,k為遙感影像波段的個數(shù);Classi為地物類別，i=1,2,…,m，m為地物類別的個數(shù)。

基于CS算法的遙感影像分類規(guī)則挖掘本質(zhì)上是多維空間上的優(yōu)化求解過程，CS算法在每一維空間上具有等價性，要求每一維樣本數(shù)據(jù)具有相同的數(shù)值范圍。遙感影像各波段的連續(xù)值和離散值都要求進行歸一化處理，歸一化后各波段數(shù)據(jù)范圍為[0,1]。

1.2.2 分類規(guī)則挖掘

基于CS算法的遙感影像分類規(guī)則挖掘的最終目的是搜索遙感影像各波段判斷區(qū)間最優(yōu)上界和最優(yōu)下界。在標準布谷鳥算法中，一只布谷鳥一次只產(chǎn)一個卵，一只卵對應(yīng)一個鳥窩[13]。假設(shè)鳥窩(卵、布谷鳥)總數(shù)為n，遙感影像波段數(shù)為k,個體向量維度為D=2k，則X=X1,X2,…,Xi,…,Xn，代表一個布谷鳥種群，用X(0)表示初始的布谷鳥種群，X(t)表示第t代布谷鳥種群。利用布谷鳥搜索算法進行遙感影像分類規(guī)則挖掘的主要步驟如下：

(1) 對于t=0時刻，隨機生成n個鳥窩的初始位置，初始化計算公式為

(2)

(2) 選擇適應(yīng)度函數(shù)，并計算每個鳥窩位置(解向量)的目標函數(shù)值，得到當前的最優(yōu)函數(shù)值。分類規(guī)則的適應(yīng)度用來衡量鳥窩位置的優(yōu)劣，合理地構(gòu)造適應(yīng)度函數(shù)是分類規(guī)則挖掘的關(guān)鍵。本文的適應(yīng)度函數(shù)如下

(3)

式中，TP為滿足規(guī)則，且與規(guī)則預(yù)測類型一致的樣本數(shù)；FP為滿足規(guī)則，且與規(guī)則預(yù)測不一致的樣本數(shù)；TN為不滿足規(guī)則，且與規(guī)則預(yù)測不一致的樣本數(shù)；FN為不滿足規(guī)則，且與規(guī)則預(yù)測一致的樣本數(shù)。

(3) 對于第t步的可行解，使用萊維飛行方式更新布谷鳥尋優(yōu)搜索的位置，具體搜索公式如下

(4)

使用式(4)計算更新位置后的目標函數(shù)值，比較現(xiàn)有位置函數(shù)值與上一代最優(yōu)函數(shù)值，選取具有更優(yōu)適應(yīng)度的保留給下一代的布谷鳥種群，從而保證布谷鳥種群能保留精英個體，朝更優(yōu)適應(yīng)度值的方向進化。

當全局最優(yōu)適應(yīng)度值達到一定的穩(wěn)定值或迭代次數(shù)達到最大迭代次數(shù)，則循環(huán)終止，輸出全局最優(yōu)位置向量和相應(yīng)的適應(yīng)度值，并按式(1)格式構(gòu)造分類規(guī)則；否則，返回步驟(2)，繼續(xù)進行搜索。

獲取一條分類規(guī)則后，對規(guī)則進行修剪，除去對分類結(jié)果貢獻不大的條件項，提高分類規(guī)則的有效性，避免規(guī)則對樣本數(shù)據(jù)的過度擬合。同時，移除滿足當前規(guī)則且分類正確的樣本數(shù)據(jù)，繼續(xù)搜索下一條分類規(guī)則。當某地類的分類規(guī)則樣本覆蓋度，即滿足規(guī)則且分類正確的樣本數(shù)/該地物類別樣本數(shù)，達到一定閾值時，終止該地物類別的規(guī)則挖掘，開始下一地物類別的規(guī)則挖掘，直至所有地物類別的規(guī)則挖掘完畢?；诓脊萨B算法的遙感分類規(guī)則挖掘的偽代碼如下：

Input training dataset/*導(dǎo)入訓(xùn)練樣本數(shù)據(jù)*/

Initialize control parameters /*初始化控制參數(shù)*/

Normalize SampleSet;/*歸一化訓(xùn)練樣本數(shù)據(jù)*/

forObjectClass=1:m /*依次為每個類型搜索規(guī)則*/

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); /*修剪規(guī)則*/

Re_normalize(best_rule);/*分類規(guī)則的逆歸一化*/

SaveRule(best_rule,fmax,ObjectClass);/*輸出規(guī)則*/

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

rulecount=rulecount+1;

end

end

2 試驗研究

試驗使用ALOS影像(1995×2000像素)如圖1(a)所示，經(jīng)全色波段與多光譜波段融合后，影像空間分辨率為2.5 m，共有藍色、綠色、紅色和近紅外4個波段，同時提取了1個光譜特征(植被指數(shù)NDVI)和8個紋理特征(均值、方差、一致性、對比度、非相似度、熵、二階矩陣、灰度相關(guān))作為影像分類的屬性依據(jù)，每個特征作為一個波段，試驗數(shù)據(jù)共有13個波段屬性。挖掘分類規(guī)則時，對試驗數(shù)據(jù)進行均勻采樣，獲取了10 000個樣本數(shù)據(jù),其中，5000個樣本數(shù)據(jù)用于訓(xùn)練分類規(guī)則，剩余的5000個樣本數(shù)據(jù)用于測試分類規(guī)則。在Matlab平臺中，編程實現(xiàn)訓(xùn)練樣本數(shù)據(jù)的分類規(guī)則挖掘，并根據(jù)所挖掘的分類規(guī)則對遙感影像進行分類。設(shè)置初始化參數(shù)如下：鳥窩(卵、布谷鳥)總數(shù)n=200，地物類別的個數(shù)m=6，遙感影像波段數(shù)k=13，宿主發(fā)現(xiàn)概率pa=0.25，最大迭代次數(shù)Max_Iter=2500，樣本覆蓋度Max_cover=0.95，共獲得b9條分類規(guī)則，部分分類規(guī)則如下：

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

使用所挖掘的分類規(guī)則，對試驗區(qū)遙感影像進行分類，CS分類結(jié)果如圖1(b)所示，結(jié)合實地調(diào)查，該分類結(jié)果比較真實地反映了實際的土地利用覆蓋類型。在試驗影像范圍內(nèi)隨機均勻選取10 000個點，計算影像的分類精度(見表1)，CS遙感分類方法的總體精度為85.36%，Kappa系數(shù)為0.822。

圖1 影像分類方法結(jié)果

類名實際/像素分類/像素判斷正確/像素生產(chǎn)精度/(%)用戶精度/(%)公路13621412118787．1584．07水域17561874156288．9583．35耕地23402296198684．8786．50建設(shè)用地21872108182883．5886．72林草地1124117697887．0183．16其他1231113499580．8387．74總和10000100008536——總體分類精度：85．36% Kappa系數(shù)=0．822

同時，為便于對比分析遙感分類精度，對相同的訓(xùn)練樣本數(shù)據(jù)，使用蜂群遙感分類(ABC)、See5.0決策樹方法獲取分類規(guī)則，并對試驗區(qū)相同影像進行了分類[12]，對比分析影像分類精度見表2，可見3種方法的精度有一定的差異，CS遙感分類方法具有更高的分類精度，其分類效果更好。

表2 影像分類精度對比分析

3 結(jié)束語

智能計算方法智能挖掘遙感影像分類規(guī)則，搜索遙感影像各波段最優(yōu)分類區(qū)間，將遙感影像分類問題轉(zhuǎn)化成多維個體向量的優(yōu)化問題，該智能式遙感影像分類方法能有效提高復(fù)雜地物分類精度。布谷鳥搜索算法是一種結(jié)合布谷鳥巢寄生性和萊維飛行模式的群智能搜索算法，通過隨機游走的方式搜索得到一個最優(yōu)的鳥窩來孵化鳥蛋，具有參數(shù)少、易實現(xiàn)、隨機搜索路徑優(yōu)和尋優(yōu)能力強等優(yōu)點。本文將布谷鳥搜索算法引進到遙感影像分類中，通過模仿布谷鳥巢寄生行為的方式，搜索遙感影像各波段的最優(yōu)分類區(qū)間，以If-Then表達形式構(gòu)造遙感分類規(guī)則。并且以ALOS遙感影像分類為例，分別應(yīng)用布谷鳥遙感分類方法、蜂群智能遙感分類和See5.0決策樹方法對影像進行了分類，并對比分析了3種方法的分類精度。通過本文理論分析和實例驗證得出結(jié)論，應(yīng)用布谷鳥算法進行遙感影像分類方法是可行的，所挖掘的分類規(guī)則能夠更清晰地描述復(fù)雜地物分類中的非線性關(guān)系，能夠提高分類精度。

[1] 杜培軍.遙感原理與應(yīng)用[M].徐州:中國礦業(yè)大學(xué)出版社,2006.

[2] 賈永紅.人工神經(jīng)網(wǎng)絡(luò)在多源遙感影像分類中的應(yīng)用[J].測繪通報,2000(7):7-8.

[3] 申文明,王文杰,羅海江,等.基于決策樹分類技術(shù)的遙感影像分類方法研究[J].遙感技術(shù)與應(yīng)用,2007,22(3):336-337.

[4] 楊紅磊,彭軍還. 基于馬爾可夫隨機場的模糊c-均值遙感影像分類[J].測繪學(xué)報,2012,41(2):213-218.

[5] 譚琨,杜培軍. 基于再生核Hilbert空間小波核函數(shù)支持向量機的高光譜遙感影像分類[J]. 測繪學(xué)報, 2011,40(2):143-147.

[6] 陳云浩,馮通,史培軍,等.基于面向?qū)ο蠛鸵?guī)則的遙感影像分類研究[J].武漢大學(xué)學(xué)報(自然科學(xué)版), 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].遙感學(xué)報,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] 劉小平,黎夏,彭曉鵑,等.一種基于生物群集智能優(yōu)化的遙感分類方法[J].中國科學(xué)(D輯：地球科學(xué)), 2007, 37(10): 1400-1408.

[12] 曹敏,史照良,陽建逸. 蜂群智能算法的遙感影像分類方法[J].測繪學(xué)報,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

國家自然科學(xué)基金(41101349)；江蘇省高校自然科學(xué)基礎(chǔ)研究項目(13KJB420003); 江蘇高校優(yōu)勢學(xué)科建設(shè)工程資助項目(PAPD)

沈泉飛(1980—)，男，碩士，工程師，研究方向為遙感影像處理。E-mail: sqf1980@126.com

曹 敏