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

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

(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

曹 敏