基于最速上升算法的超光譜圖像波段選擇搜索算法
2008-12-31 00:00:00周爽張鈞萍蘇寶庫
計算機應用研究 2008年11期
(哈爾濱工業大學 a.電子與信息技術研究院；b.航天學院， 哈爾濱 150001)
摘要：超光譜遙感數據具有的波段數目多、波段寬度窄、數據量龐大等特點，給圖像的進一步解譯帶來困難。結合超光譜圖像波段選擇的具體應用，根據波段之間的相關性將整個波段劃分為幾個子波段，采用最速上升的特征選擇搜索算法在各子波段中快速提取最優波段。為了驗證本算法的有效性，分別選取JM距離、BH距離以及類內類間離散度作為評價準則，針對一幅200波段的AVIRIS超光譜圖像進行分類實驗，并將該方法與傳統的SFFS算法進行對比。實驗結果表明所采用的算法用于特征選擇具有搜索能力強、分類精度高的特點，完全可以替代傳統的SFFS算法。
關鍵詞：超光譜圖像；特征選擇；最速上升搜索算法
中圖分類號：TP391文獻標志碼：A
文章編號：1001-3695(2008)11-3501-03
Band selection algorithm of hyperspectral imagebased on steepest-ascent search algorithm
ZHOU Shuanga，b，ZHANG Jun-pinga，SU Bao-kub
(a.School of Electronics Information Technology，b.School of Astronautics， HarbinInstitute of Technology， Harbin 150001， China)Abstract:This paper proposed a band selection approach of hyperspectral image based on steepest-ascent search algorithm. The approach needed to divide the whole hyperspectral band into several subgroups in terms of the relativity between bands firstly， and then applied the steepest-ascent search strategy to quickly extracting optimal band in every subgroup in which the combinations of bands was indicated by binary vectors and the search was being along the steepest direction until the local extreme was acquired. In order to verify the ralidity of this algorithm， the approach was compared with the classical sequential forward floating selection suboptimal techniques， using hyperspectral remote sensing images as a data set. Experimental results prove the ralidity of this algorithms， which can be regarded as a valid alternative to classical SFFS method.
Key words:hyperspectral image; feature selection; steepest-ascent search algorithm
隨著成像光譜儀的發展， 遙感成像由多光譜發展到超光譜(hyperspectral)，由于譜分辨率高，其數據通常稱為超光譜數據或超光譜圖像。雖然超光譜數據攜帶的信息多，理論上其辨識不同類別的能力應該更強，但是由于超光譜數據量的劇增以及高維數據特有的性質給超光譜數據的處理帶來困難。尤其是在不損失系統類別可分性的前提下，減小數據維、提取有效信息對于超光譜圖像的分析處理是極其必要的[1]。不論特征選擇還是特征提取，均可以達到降維的目的，但特征提取策略往往算法復雜，且計算量較大。更主要的是，針對超光譜影像分類的具體實踐，僅僅從數學角度實現維數降低的目的，無形中造成原始波段所包含的地物輻射或反射信息的丟失，而這對于指導超光譜遙感是十分不利的。特征選擇的降維策略可以使得地物的各種信息得以保留，但超光譜影像波段眾多、各波段相關性強，使得當前特征選擇的一些方法或由于計算量太大而無法進行，或由于各特征獨立的假定不成立而無法獲得理想的降維結果，最終使得超光譜影像所包含的豐富地物信息無法得到充分挖掘[2，3]。研究一種特征選擇效率高且所選特征能代表眾多光譜特征的特征選擇方法是非常必要的。
本文首先就特征選擇技術進行了概述，重點評述了當前常用的幾種特征搜索方法，從中可見最優和次優搜索方法的局限性。在此基礎上提出一種最速上升的特征選擇搜索算法。算法首先通過劃分特征子空間的方法對特征空間進行預處理，然后分別選擇三種類別可分性判據作為評價函數，利用一幅200波段的AVIRIS超光譜圖像進行了仿真實驗，并使用最大似然分類器對所選特征進行分類。
1特征選擇
超光譜圖像數據位于一個高維數據空間中，它的每一個波段均可以被看成一個特征。因此在超光譜圖像中進行特征選擇即是進行波段選擇(band selection)，從所有光譜波段中選擇起主要作用的子集(subset)，該子集既能明顯地降低數據維數，又能比較完整地保留感興趣的信息。該過程也就是從一組特征中去除冗余的特征來降維，即從一組數量為D的特征中選擇出數量為d(d 特征選擇技術包括兩個關鍵問題：a)選擇合適的準則函數來衡量特征組合是否最優，得到特征獲取操作的停止條件；b)采用高效率的特征子集搜索方法[4]。 在超光譜圖像的具體應用中，準則函數主要分為兩類:a)類別可分性判據。主要包括基于幾何距離的可分性判據、基于類的概率密度函數的可分性判據（如Bhattacharyya判據、Chernoff判據、散度等）、基于后驗概率的可分性判據。b)基于信息量原則。選擇信息量大的波段，主要從熵、最佳指數等來考慮[5~7]。 搜索方法分為最優(optimal)搜索算法和次優(suboptimal)搜索算法。最優搜索算法是根據采用的準則函數，找到一組最佳特征組合的過程，也可看做是一種狀態空間的搜索。要找到最佳子集，原則上需要窮盡所有可能的組合。隨著波段數目的增加，波段組合的數量將呈指數增長，因此最佳子集的搜索方法計算量太大，不適合應用于超光譜圖像。目前實際超光譜圖像的波段選擇均使用次優搜索算法。次優搜索算法是依照準則函數選擇一組性能較好的，但不一定是最好的特征集合。傳統的次優搜索方法有單獨最優特征選擇法、增添特征法(sequential forward selection，SFS)和剔減特征法(sequential backward selection，SBS)、增l減r法（l-r法）、Zl-Zr法（廣義l-r法）和可分性判據遞推算法等。單獨最優特征選擇法的基本思路是計算各特征單獨使用時的判據值并以遞減排序，選取前d個分類效果最好的特征，該法要求只有可分性判據J是可分的才能選出一組最優特征；SFS 法是自下而上的搜索方法，每次從未選入的特征中選擇一個特征，使它與已選入的特征組合在一起時J值最大，直到選入特征數目達到指定的維數為止；SBS法是一種自上而下的搜索方法，從全部特征開始每次剔除一個特征，所剔除的特征應使尚保留的特征組合的J值最大； l-r法克服了SFS和SBS法中一旦某特征被選入或剔除后就不能再被剔除和選入的缺點，可在選擇過程中加入局部回溯；Zl-Zr法每次增加或剔除r個特征，交替進行，既考慮了選入或剔除特征之間的相關性，又不至于引起計算量過大，同時對計算復雜性和特征選擇的合理性兼顧考慮；可分性判據遞推算法在求判據時，在J(Xk-1)的基礎上把新加入或剔出的特征的影響加進去，不必從頭計算，一定程度上簡化了計算工作。 超光譜數據由于數據量大、數據維數高，傳統降維方法又由于自身的局限性，在特征集的特征選擇問題上， 盡管有很大的進展，已有的算法或者得到的解的優化程度仍然很低， 或者計算量太大， 處理時間長，遠未達到令人滿意的程度[8]。本文重點研究特征搜索算法，以期實現在計算量和處理效果方面的改善。 2最速上升搜索算法 21預處理 波段選擇依據的原則之一是要使所選擇的波段與其他波段的相關性小。通過對200個波段AVIRIS超譜圖像的相關矩陣的研究可以發現，相鄰波段之間的相關性一般比間隔較遠的波段之間的相關性要高，而且這種高相關性是成塊或成組出現的，不同波段間的相關性隨著波段間隔的增加而減弱。 預處理過程也就是對超譜圖像這個數據空間進行特征子空間劃分的過程。當兩個波段間的相關性滿足給定的閾值參數δ(0＜δ＜1)時，這兩者之間的波段便構成一個子空間，每個子空間中的波段都具有類似的相關性。閾值參數δ的值大，則子空間數少；閾值參數δ的值小，則子空間數多。在子空間劃分完成后，由于每個子空間內的波段相關性較強，而各個子空間之間的波段相關性較弱，因此在后續的處理中可以將各個子空間近似看做是彼此相對獨立的數據源。被保留下來的特征構成一個降維的特征集，對每個降維的特征集分別進行最優波段搜索。波段劃分與特征提取框圖如圖1所示。 22最速上升搜索算法(SA) 將超譜數據看成是一個特征集，設特征集合X包含n個特征，X={x1，x2，…，xn}，通過預處理產生m個特征子集，即X={X1，X2，…，Xm:Xi∈X，i=1，2，…，m}(m＜n)，每個特征子集的維數遠小于n。這樣只要對每個降維的特征子集進行最優特征搜索即可，如圖2所示。 最優波段的搜索采用一種最速上升的搜索算法(steepest-ascent)快速提取最優波段，算法使用二進制向量表示波段組合，即每種可能的波段組合均以一個長為N的“0”“1”串表示。其中“1”的個數為M，表示所選波段。該算法的基本思想是沿J(S)增加最快的方向進行搜索，直至達到局部極值點。具體來說，就是定義一個離散向量空間B。其中任意一個二進制向量b的長度均為N，且包含M個“1”和(N-M)個“0”。顯然，B中共有向量CMN個。在此基礎上，定義向量b的鄰域為與b至多有兩位不同向量的M集合?？紤]到上述“0”“1”個數的約束，B中并不含有與b只差一位的向量，因此，b的鄰域為由M×(N-M)個向量組成的集合。直觀地講，假設b代表的波段組合為S，那么b的鄰域中任意向量所代表的波段組合與S只有一個波段不同。算法實現具體步驟如下： 將整個特征集設為X。首先執行預處理：將X劃分為m個特征子集，每個特征子集Xi(1≤i≤m)可能具有不同的維數wi(1≤i≤m)，然后對每個特征子集執行以下迭代過程： a)在Xi中隨機抽取v個特征組成初始子集S0i，未被抽取的（w-v）個特征組成補集D0i，使用向量b0i代表S0i，并令判決函數Jmaxi=J(S0i)。 b)在第k次迭代中，計算bk-1i鄰域的一組特征子集Ski，將它賦值給Sk-1i，更新Ski的補集Dki。其中Ski里面的元素是用Dki中的Si來分別替換Sk-1i中的Sj得到的。 c)計算新的子集Ski的準則函數J(Ski)。 d)將得到的J(Ski)與Jmaxi比較，若Jmaxi＞J(Ski)，則繼續執行b)c)；否則令Jmaxi=Jki。 e)當Dki中沒有元素時算法終止，輸出Jmaxi所對應的Ski，并將Jmaxi放入判決函數集Ji中。以上過程可重復運行多次，每次可隨機選擇不同的初始特征子集，并將每次產生的最優判決函數放入判決函數集Ji中。 在多次運行之后選擇判決函數集中最大的Jmaxi所對應的特征子集即為最終所選擇的特征子集。該算法搜索最優評價函數的過程運行次數為mi=1[vi×(wi-vi)×k]。其中：m為預處理階段劃分的子特征集個數；wi為劃分后子特征集中的特征數，vi為在劃分后的子特征集中選擇的特征數；k為對每個特征集搜索Jmaxi所需的迭代次數。 3實驗結果 為檢驗本文所提出算法的有效性，使用在美國印第安納州某農林混合試驗場獲取的220 波段AVIRIS超光譜圖像進行了仿真實驗。波長是14~215 μm，每幅圖像的空間分辨率為25 m，大小為144×144像素。在去除水汽吸收波段、低信噪比波段后，保留了其中的200個波段進行數據處理。圖3給出了該AVIRIS數據的第29波段圖像。圖像所示區域內地物類別總數為9，包括玉米地、大豆耕地、草場、牧場、樹林、干草垛等。各地物類別如表1所示。在選取不同的波段數目的情況下，分別采用BH距離、JM距離和類內類間離散度三種評價函數對實驗數據進行仿真實驗，獲得測試樣本精度如表2所示。 表1各類地物類別名稱及訓練、檢驗樣本數目 各地物類別訓練樣本數目檢驗樣本數目總樣本數目 由表1、2的數據可以看出，JM距離準則函數的精度是最高的，然后是BH距離準則函數，離散度準則函數最低。為了驗證SA搜索算法的有效性，筆者選擇 SFFS搜索算法與SA進行比較，如圖4~6所示。圖4~6分別為選擇JM距離、BH距離和類內類間離散度為評價準則時SA和SFFS兩種算法分類樣本精度的比較結果。從圖中可以看出，選擇JM準則函數時，SA的有效性與SFFS相比不是很明顯，在選擇BH距離和離散度準則函數后，使用SA得到的結果明顯比使用SFFS得到的結果的分類精度高。上述實驗充分說明使用本文提出的最速上升搜索算法選擇的波段組合在超光譜圖像目標識別中的有效性，該算法具有搜索能力強的特點。 4結束語 本文提出的基于最速上升算法的特征選擇搜索算法在超光譜圖像的特征選擇中有效地選擇出用于分類的波段組合。在預處理階段，多特征集的劃分極大地簡化了算法的搜索復雜性，而在使用BH距離和類內類間離散度作為準則函數后，其分類精度明顯高于SFFS算法。該算法的搜索能力較強，分類精度高，能夠很好地處理超光譜圖像。 參考文獻： ［1］JAIN A，ZONGKER D.Feature selection: evaluation， application， and small sample performance[J].IEEE Trans on Pattern Analysis and Machine Intelligence，1997，19(2): 153-158. [2]WARNER T，SHAND M.Spatial autocorrelation analysis of hyperspectral imagery for feature selection[J].Remote Sensing of the Environment，1997，60:58-70. [3]KIRA K，RENDELL L A.The feature selection problem:traditional methods and a new algorithm[C]//Proc of the 9th National Conf on AI.1992:129-134. [4]SEBASTIANO B S，BRUZZONE L.A new search algorithm for feature selection in hyperspectral remote sensing images[J].IEEE Trans on Geoscience and Remote Sensing，2001，39(7):1360-1367. [5]劉建平，趙英時.超光譜遙感數據解譯的最佳波段選擇方法研究[J].中國科學院研究生院學報，1999，16(2): 152-161. [6]孫即祥，王曉華，鐘山，等.模式識別中的特征提取與計算機視覺不變量[M].北京：國防工業出版社，2001. [7]KOLLER D，SAHAMI M.Toward optimal feature selection[C]//Proc of Int’l Conf on Machine Learning.1996:284-292. [8]DASH M，LIU H.Feature selection for classification[J].Intelligent Data Analysis，1997，1(3):131-156.
