結合APO算法的高光譜圖像波段選擇

王立國，魏芳潔

(哈爾濱工程大學信息與通信工程學院，150001哈爾濱)

高光譜圖像具有波段數多、數據量龐大、數據不確定和小樣本分類等特點，而且其波段間相關性強、數據冗余度高，這直接影響了高光譜圖像分類的精度和速度［1］.因此，在保證地物分類識別率的情況下，減少數據量、節(jié)省資源的降維處理是非常有必要的.對高光譜圖像進行降維主要有兩種途徑:特征提取和波段選擇.特征提取是將原始高維數據空間進行變換，再取子空間，該方法通常算法復雜、計算量較大，且不利于圖像的解譯［2］.相比之下，波段選擇是從高光譜圖像所有波段中選出一些最有效的波段以達到降維的目的，不僅有效地去除了冗余特征，避免了“維數禍根”，而且在樣本數較少的情況下改善了分類器的性能.

高光譜圖像波段選擇常常是一個NP難問題［3］.一般地，為了獲得最優(yōu)波段子集，即波段子集有較好的性能，必須進行窮舉搜索，但這樣就會消耗大量的搜索、運算時間，因此不可能得到廣泛應用.后來出現(xiàn)的順序前進法、順序后退法以及改進的廣義順序前進法、廣義順序后退法等啟發(fā)式搜索策略，實際上都屬于貪心類算法，其搜索計算量較小，在原始數據波段間相關性較小的情況下，能夠獲得較好的效果.但其存在明顯的缺點，比如:某一波段一旦被加入或剔除，則該波段就不能再被剔除或加入，這樣容易陷入局部最優(yōu).為了克服這些缺陷，后來又出現(xiàn)增減r算法，但其中l(wèi)和r很難確定.因此，尋找一種計算耗時少、收斂性能好的波段選擇方法是亟待解決的問題.智能尋優(yōu)算法是利用智能尋優(yōu)搜索策略結合適應度函數來獲得次優(yōu)或近似最優(yōu)波段子集，并且以降低搜索、運算時間為代價.近些年來，出現(xiàn)了許多將智能尋優(yōu)算法應用于高光譜圖像的波段選擇中，并取得了一定的效果.比如，趙冬和趙光恒［4］利用遺傳算法進行高光譜圖像波段選擇;周爽［5］利用蟻群算法進行高光譜圖像降維處理;黃睿［6］利用粒子群算法進行高光譜遙感數據特征約簡，等等.這些尋優(yōu)算法中，遺傳算法是一種概率搜索尋優(yōu)算法，可以較好地解決波段選擇過程中波段組合數目多、難以遍歷的問題，但其收斂速度問題目前仍無法得到滿意的解決，即在有限的時間內無法有效收斂.蟻群算法是一種群智能的搜索算法，可以搜索到性能較好的波段組合，但其一般需要較長的搜索時間，而且容易出現(xiàn)停滯現(xiàn)象，產生早熟［7］.粒子群算法是一種基于種群迭代的優(yōu)化算法，其雖然收斂速度較快，但收斂精度不高，而且容易早熟［8］.而擬態(tài)物理學優(yōu)化算法是一種新的群體隨機搜索算法，受牛頓第二力學定律的啟發(fā)，通過個體間的虛擬作用力來改變個體的運動速度和位置，使其向較優(yōu)解的方向移動，最后收斂于全局最優(yōu)解的附近.并且其具有較好的全局搜索能力，不易陷入局部最優(yōu)，且具有穩(wěn)定和快速收斂的特點以及較好的魯棒性［9］.擬態(tài)物理學優(yōu)化算法已經在單、多目標優(yōu)化問題中得到很好的應用.因此本文提出了結合擬態(tài)物理學優(yōu)化(APO)算法的高光譜圖像波段選擇，并通過實驗驗證該算法的有效性.

1 擬態(tài)物理學優(yōu)化算法

擬態(tài)物理學(physicomimetics or artificial physics，AP)最早是由Spear等［10］提出的，因受物理力學定律的啟發(fā)而稱其為“擬態(tài)”，該算法本質上是模擬了牛頓第二力學定律(F=ma)，主要用于解決多機器人系統(tǒng)的分布式控制.王艷和曾建潮［11-12］研究了擬態(tài)物理學，并首次將其成功應用于解決優(yōu)化問題，提出了擬態(tài)物理學優(yōu)化算法(physicomimetics or artificial physics optimization，APO).該算法是一種群體隨機搜索算法，其每個個體代表解空間中的1個可行解.每個個體依據自己的慣性以及所受其他個體的作用力合力來調整自己的速度和位置，最后整個群體得到的最優(yōu)位置就是目前得到的全局最優(yōu)解，個體的好壞由優(yōu)化問題的適應度來評價.每個個體根據全局最優(yōu)、最差適應度和自身適應度不斷更新其質量，通過質量的變化影響虛擬力的變化，來更新個體的速度和位置.

APO算法中，設群體規(guī)模為n，則第i(i=1，2，…，n)個個體的質量表示為mi，在第k維個體i的速度表示為vi，k，在第k維個體i的位置表示為xi，k.個體的質量不是一個常量，而是一個用戶定義的關于其適應度值的函數.個體的適應度值越好，其質量就越大;個體的適應度值越差，其質量就越小.在求解最大化問題時，個體的適應度值越大，表明該個體的適應度值越好，則其質量就越大;在求解最小化問題時，個體的適應度值越小，表明個體的適應度值越好，則其質量就越大.個體i的質量計算如下:

其中:xbest為當前種群中的最優(yōu)個體;xworst為當前種群中的最差個體;f(xbest)為最優(yōu)個體的適應度值;f(xworst)為最差個體的適應度值;f(xi)為個體xi的適應度值.從公式可看出，個體質量在(0，1］內變化，個體的適應度值越接近最優(yōu)解，個體的質量越大，反之，個體的適應度值越接近最差解，個體的質量越小.因此，個體質量的大小是該個體在整個種群中優(yōu)劣的一個評價.

在第k維上，個體i受個體j的虛擬作用力為Fij，k，其計算如下:

其中?i≠j＆i≠best;G為引力常量;｜xj，k-xi，k｜為個體j到個體i在第k維上的絕對距離.適應度值好的個體吸引適度值差的個體，適應度值差的個體排斥適應度值好的個體，作用力的方向和大小由式(2)給出.且其他個體不作用于全局最優(yōu)個體.

在第k維上，個體i(除最優(yōu)個體外)受到群體中其他所有個體的作用力合力為Fi，k，其計算公式下:

除最優(yōu)個體外，每個個體在作用力合力的作用下進行運動.在t+1時刻，個體i每一維的速度和位置的更新方程如式(4)和式(5):

其中w為慣性權重，α～N(0，1)的隨機數.任意個體i的運動速度滿足Vi=［-Vmax，Vmax］，任意個體i的運動空間滿足Xi=［Xmin，Xmax］.

由式(4)～(5)可以看出，對全局最優(yōu)個體的速度和位置不進行更新，而直接被保留進入下一次的迭代.

目前，關于APO算法的應用較少，但由于其具有較好的全局搜索能力，不易陷入局部最優(yōu)，且具有穩(wěn)定和快速收斂的特點以及較好的魯棒性優(yōu)點，將在組合優(yōu)化問題中有很好的應用前景.

2 結合APO算法的波段選擇

結合APO算法的上述優(yōu)點，本文將該算法應用于高光譜圖像的波段選擇，其主要包括3個部分:種群初始化，計算個體所受合力以及個體運動更新.

2.1 初始化種群

1)運動空間的設置.根據APO算法中種群個體的特點，首先對高光譜圖像按照波段間的相關系數矩陣進行子空間劃分［13］，設子空間的個數為s，其對應APO算法中個體的維數l，即在每個子空間內選擇一個波段(l=s).當然，根據實際目標探測和分類的需要以及計算機快速處理的能力，可以在子空間j(j=1，2，…，s)中同時選擇多個波段作為個體在此子空間中的維數lj，個體在所有子空間中維數之和即為個體的總維數，即其中在每個子空間中該選擇幾個波段，可根據子空間中波段的數目，按一定的比例取值.每個個體代表一個高光譜圖像的波段組合，即組合優(yōu)化問題的一個可行解.這樣也使得選擇的波段組合相關性小，降低了信息的冗余度.

2)初始化.設置算法中的控制參數以及產生初始種群、初始速度.

控制參數:種群規(guī)模為n，每個個體的維數為l，終止迭代次數tmax，引力常量G，慣性權重w=wmax-(wmax-wmin)/tmax×t，初始狀態(tài)下，個體所受其他個體的虛擬作用力和合力均為零.

初始種群:在確定每個子空間波段序號上、下界的情況下，依次在每個子空間的波段區(qū)間范圍內，即運動的空間內，隨機產生一個n×lj矩陣，且保證矩陣同一行中的元素各不相同(即同一波段組合中選擇不同的波段)，最后將產生的s個矩陣以列優(yōu)先的順序合并為一個n×l矩陣，矩陣中每個元素代表被選中的波段序號，每一行代表一個波段組合，即擬態(tài)物理學優(yōu)化算法中的一個個體，這樣產生了n個初始種群個體，本文算法中省去了編、解碼的復雜過程，更方便于波段的選擇，提高了搜索效率.

初始速度:首先，根據每個子空間中的波段數目，確定個體速度分量在各個子空間中的最大值，則任意個體在第j個子空間中的最大速度計算公式下:

其中c(j)和d(j)表示第j個子空間波段序號的下界和上界.然后，根據個體在該子空間的維數lj，且在最大速度的約束范圍Vj=［-Vmax(j)，Vmax(j)］內，隨機產生速度分量子塊vn×lj，以此類推，產生s個速度分量子塊.最后，將s個速度分量子塊依次按列優(yōu)先的順序組成初始速度矩陣Vn×l.其中，初始速度矩陣的每一行依次代表各個個體在每一維上的初始速度.

3)適應度函數.為了使選擇的波段組合性能更優(yōu)，本文采用類間可分性和波段組合的信息量兩個性能指標的權重組合作為適應度函數.由于Jeffries-Matusita距離［14］同時兼顧一次統(tǒng)計變量和二次統(tǒng)計變量，在測度高光譜多維空間中兩類統(tǒng)計距離時，該距離是最佳測度.因此，本文采用Jeffries-Matusita距離作為適應度函數中的類間可分性函數，其計算如公式為

其中:μi、μj分別為第i類和第j類在波段組合上的度量均值矢量;Σi、Σj分別為第i類和第j類在波段組合上的協(xié)方差矩陣;T為轉置符.

適應度函數中的信息量函數采用最佳索引因子(BOIF)［15］，其計算公式下:

其中:Si為波段i的標準差，且

式中:M為圖像的行像素個數;N為圖像的列像素個數;fi是第i波段;ui是第i波段的像素平均值.Rij為波段i和波段j的相關系數，且

本文采用類間可分性和波段組合的信息量兩個性能指標的權重組合作為適應度函數，其計算如式(12)，并依據該公式計算初始種群個體的適應度值.

其中a和b為權重系數.

2.2 計算個體所受合力

1)個體質量.在本文的算法中，個體質量與個體的適應度值成正比例關系，即個體適應度值越大，個體的質量就越大;反之亦然.

2)個體所受其他個體的虛擬作用力.個體所受其他個體的虛擬作用力與個體的質量和個體間的距離相關，依據式(2)計算各個個體受其他個體虛擬作用力，適應度值較優(yōu)的個體對適應度值較差的個體有引力作用，適應度值較差的個體對適應度值較優(yōu)的個體有斥力作用，且最優(yōu)個體不受其他個體的作用力，即最優(yōu)個體不受其他個體引、斥力的作用.依據式(3)計算各個個體受其他個體虛擬作用力合力，這樣使得次優(yōu)的個體逐漸向最優(yōu)的個體靠攏，最終收斂于最優(yōu)解.

2.3 個體運動更新

每個個體在其所受合力的作用下進行速度和位置的更新，在算法中引入一個服從正態(tài)分布的隨機變量α，即α ～ N(0，1)，使得個體將以不為零的概率訪問高光譜圖像子空間中的各個波段，大大提高了算法解的多樣性.除了最優(yōu)個體外，在第t+1次迭代中，其他任意個體按式(4)和式(5)更新每一維的速度和位置，并且保證速度和位置在約束范圍之內，對超出約束范圍的速度和位置做如式(13)和式(14)的處理.

2.4 結合APO算法的高光譜圖像波段選擇流程

第一步:初始化種群.首先對所處理的高光譜數據進行子空間劃分，然后按照2.1節(jié)講述的方法產生初始波段組合種群和初始速度，計算各個個體的適應度值，找到初始種群最優(yōu)適應度值和最差適應度值，記進化代數t=0.

第二步:計算各個個體所受合力.

1)計算個體的質量:首先根據式(7)～(12)計算個體的適應度值，即波段的組合的適應度值，然后根據式(1)計算個體的質量;

2)根據式(2)計算各個個體所受其他個體的虛擬作用力;

3)根據式(3)計算個體所受其他個體作用力合力.

第三步:計算各個個體的運動.

根據式(4)和式(5)更新個體的運動速度和位置，且使更新后的個體運動滿足式(13)和式(14)所示的速度和位置的約束條件.

第四步:計算個體的適應度值.

計算更新后的個體適應度值，更新最優(yōu)適應度值和最差適應度值.

第五步:判斷算法結束條件.

本文設計的算法結束條件是最大迭代次數，若滿足，則停止循環(huán)，并輸出最優(yōu)解;若不滿足，進行迭代次數t=t+1，返回第二步繼續(xù)執(zhí)行，直至達到最大迭代次數為止.

本文算法的流程如圖1所示.

圖1 波段選擇流程

3 波段選擇的結果與評估

本文的硬件環(huán)境是:CPU為 Intel Core i3，2.40 GHz，內存 2 GB的 PC機;軟件環(huán)境是:Window XP操作系統(tǒng)，利用Matlab 2008a對波段選擇算法進行仿真實驗;實驗數據:本實驗所采用的高光譜AVIRIS數據為1992年6月美國西北部印第安納州農林混合試驗場的高光譜圖像，其光譜范圍為0.41～2.45 μm，空間分辨率為25 m，光譜分辨率為 10 nm，圖像的大小為 144×144 pixel，在原始220個波段的圖像中，去除水汽吸收和低信噪比的波段，參與處理的圖像波段數為200.實驗中選擇的地物類別以及訓練樣本數和測試樣本數如表1所示.

表1 實驗數據

本文算法中參數設置［12，16］為:wmin=0.4，wmax=0.9，tmax=200，n=30，l=s=5，G=1，a=40，b=1e-5.為證明本文算法是一種有效的波段選擇方法，用基于蟻群、遺傳和粒子群算法的波段選擇與本文提出算法從精解效率和搜索效率兩個方面進行對比.精解效率是從每種算法輸出最優(yōu)波段組合的相關性、信息量和總體分類精度3個方面進行評判.相關性越小越好，信息量越大越好，分類精度越高越好.本文用最大似然分類法對輸出的最優(yōu)波段組合圖像進行分類，求出其總體分類精度，其計算公式如下:

其中:c為類別數;C為c類測試樣本總數;mii為第i類正確分類個數.

相關性采用波段組合波段間的平均相關性，其計算公式為

信息量采用最佳索引因子(OIF).實驗中，各對比算法均結合了子空間劃分進行波段子集的選擇，且對比算法中參數的設置參考文獻［17-19］.實驗對比結果如表2～4，其中表2為表1中前3種地物類別情況下得到的結果，表3為表1中前5種地物類別情況下得到的結果，表4為表1中9種地物類別情況下得到的結果.

表2 3種地物類別下的不同算法比較

表3 5種地物類別下的不同算法比較

表4 9種地物類別下的不同算法比較

由表2～表4可以看出:本文提出算法搜索到較優(yōu)解的時間效率都優(yōu)于其他算法，尤其本文算法的收斂速度遠遠快于蟻群算法，而且隨著地物類別數的增加，本文算法的搜索效率的優(yōu)越性更加明顯;本文算法選擇的波段子集在精解效率(即平均相關性、信息量和總體分類精度)方面也優(yōu)于蟻群算法.本文算法和遺傳算法相比，盡管遺傳算法執(zhí)行了更多的迭代次數，但是其收斂到最優(yōu)解性能遠次于本文算法搜索到最優(yōu)解的性能，這是由遺傳算法有較強的全局尋優(yōu)能力、而局部尋優(yōu)能力比較差的特點所造成的.本文算法與粒子群算法相比，除了在信息量方面低于粒子群算法，在其他方面，本文算法都優(yōu)于粒子群算法.再者，本文算法收斂到最優(yōu)解的性能較優(yōu)，另一主要原因是本文算法中將類間可分性和波段組合的信息量兩個性能指標以一定的權重組合方式作為適應度函數進行尋優(yōu).

為了更清晰、直觀地反映本文算法的有效性，將本文算法最優(yōu)解與其他算法的最優(yōu)解分類結果比較如圖2～圖4所示.

圖23 種地物類別情況下不同算法最優(yōu)解的分類

圖35 種地物類別情況下不同算法最優(yōu)解的分類

圖49 種地物類別情況下不同算法最優(yōu)解的分類

4 結論

利用高光譜圖像波段選擇來去除冗余信息是高光譜圖像分類、識別的關鍵步驟，近些年來，提出了許多方法進行高光譜圖像波段選擇，但同時兼顧搜索效率和精解效率仍是目前高光譜圖像波段選擇中常常遇到的困難.在本文的算法中，采用了類間可分性和波段組合的信息量兩個主要性能指標的權重組合作為了適應度函數，此外，在波段選擇之前對高光譜圖像進行了子空間劃分，使得最優(yōu)解中的波段間相關性較小，冗余度低.本文算法與基于蟻群、遺傳和粒子群算法的波段選擇方法相比，本文方法是一種搜索效率和精解效率都比較好的波段選擇方法，實驗也證明了該算法的有效性.

值得注意的是，本文提出算法中引力參量G需要進行設置，而且其不同的取值對較優(yōu)波段組合的選擇有一定的影響，但又很難確定其最佳值.雖然本文根據具體實驗數據進行反復測試和觀察，進而取得一個較優(yōu)值，但一種更好的引力參數確定方法有待進一步研究.

［1］丁勝，袁修孝，陳黎.粒子群優(yōu)化算法用于高光譜遙感影像分類的自動波段選擇［J］.測繪學報，2010，39(3):257.

［2］吳昊，李士進，林林，等.多策略結合的高光譜圖像波段選擇新方法［J］.計算機科學與探索，2010，4(5):464-472.

［3］王力軍，歐吉順，周楚新.一種改進的基于禁忌搜索的特征選擇算法［J］.中國制造業(yè)信息化，2011，40(5):63.

［4］趙冬，趙光恒.基于改進遺傳算法的高光譜圖像波段選擇［J］.中國科學院研究生院學報，2009，26(6):795-802.

［5］周爽.蟻群算法在高光譜圖像降維和分類中的應用研究［D］.哈爾濱:哈爾濱工業(yè)大學，2010:42-49.

［6］黃睿.高光譜遙感數據特征約簡技術的研究［D］.西安:西北工業(yè)大學，2005:79-89.

［7］劉穎，谷延鋒，張曄，等.一種高光譜圖像波段選擇的快速混合搜索算法［J］.光學技術，2007，33(2):258-261，265.

［8］倪霖，鄭洪英.基于免疫粒子群算法的特征選擇［J］.計算機應用，2007，27(12):2922-2924.

［9］王艷，曾建潮.解決多目標優(yōu)化問題的擬態(tài)物理學優(yōu)化算法［J］.計算機工程，2010，36(20):188.

［10］SPEARS W M，SPEARS D F，HEIL R，et al.An overview of physicomimetics.Lecture Notes in Computer Science-State of the Art Series，2005，3324:84-97.

［11］王艷.多目標擬態(tài)物理學優(yōu)化算法及其應用研究［D］.蘭州:蘭州理工大學，2011:23-30.

［12］MO Simin，ZENG Jianchao.Performance analysis of the artificial physics optimization algorithm with simple neighborhood topologies［C］//Computational Intelligence and Security.Beijing:［s.n.］，2009:155-160.

［13］JIAX，RICHARDSJA.Segmented principal components transformation for efficient hyperspectral remote sensing image display and classification［J］.IEEE Trans.Geosci.and Remote Sensing，1999，37:538-542.

［14］WACKER A G.The minimum distance approach to classification［D］.West Lafayette:Purdue University，1971.

［15］CHAVEZ P S，BERLIN G L，SOWERS L B.Statistical method for selecting landsat MSS ratios［J］.Journal of Applied Photographic Engineering，1982，8:23-30.

［16］XIELiping，TANYing，ZENGJianchao.The convergence analysis and parameter selection of artificial physics optimization algorithm［C］//Modelling，Identification and Control.Okayama:［s.n.］，2010:562-567.

［17］馬江濤.基于遺傳與蟻群的混合算法路徑優(yōu)化研究［D］.湖北:湖北工業(yè)大學，2011:16-17.

［18］武交峰.應用遺傳算法提高蟻群算法性能的研究［D］.太原:太原理工大學，2004:37-53.

［19］畢曉君.信息智能處理技術［M］.北京:電子工業(yè)出版社，2010:197-199，257-265.