黃炟鑫， 蔣俊正

(桂林電子科技大學 信息與通信學院，廣西 桂林 541004)

高光譜圖像(hyper spectral image，簡稱HSI)最先應(yīng)用在衛(wèi)星遙感技術(shù)上，現(xiàn)已在軍事、醫(yī)學、地質(zhì)、農(nóng)業(yè)等領(lǐng)域得到廣泛應(yīng)用[1-5]。成像儀對待測目標進行多窄波成像，而后把成像結(jié)果進行組合，得到一個多頻帶的數(shù)據(jù)塊，該數(shù)據(jù)塊即為HSI。在HSI的成像過程中，同一物質(zhì)在接收到不同波長的電磁波時，會因內(nèi)部材料結(jié)構(gòu)等因素的影響而呈現(xiàn)出不同的反射效果，相比于普通圖像只包含空間信息，HSI的成像特點使其攜帶了更多的頻譜信息。對HSI數(shù)據(jù)的研究較為廣泛，有端元提取[6]、端元解混[7-8]、分類[9]等，其中分類是最為基礎(chǔ)的研究內(nèi)容。分類的目的是對HSI數(shù)據(jù)中每個像素點進行類別標記，所得結(jié)果對HSI待測目標的識別與監(jiān)測等任務(wù)而言有很大的參考價值[10]。

HSI分類問題可使用監(jiān)督學習[11-12]算法求解。這類算法在分類時需使用大量已標記數(shù)據(jù)，然而在實際情況中，幾乎沒有原始數(shù)據(jù)是已標記數(shù)據(jù)，而對原始數(shù)據(jù)進行標記需要消耗大量的人力與物力。因此，能有效利用少量已標記數(shù)據(jù)與海量無標記數(shù)據(jù)進行分類任務(wù)的半監(jiān)督學習算法就受到了許多關(guān)注[13]。而在分類問題中，維度過高的特征會引起“休斯現(xiàn)象”“維數(shù)災(zāi)難”等問題，進而影響分類結(jié)果[14]。圖半監(jiān)督學習先使用圖模型對數(shù)據(jù)進行降維，再進行問題建模并優(yōu)化出分類結(jié)果，其中比較具有代表性的有最小割算法[15]、局部全局一致算法[16]和高斯域與調(diào)和函數(shù)算法[17]。這些算法均為直推式學習算法[13]，相比于推導(dǎo)式學習算法在優(yōu)化過程中優(yōu)化的是分類器的參數(shù)[13]，直推式學習算法目標函數(shù)的優(yōu)化直接計算出分類結(jié)果，因此圖半監(jiān)督學習算法在計算速度上有一定優(yōu)勢。經(jīng)過十幾年的發(fā)展，圖半監(jiān)督學習具有堅實的理論支撐，且在不同的應(yīng)用背景下的實用性都得到了驗證[18-19]。

在數(shù)據(jù)規(guī)模較大時，圖半監(jiān)督學習算法的計算復(fù)雜度也隨之提升，針對此問題，提出一種分類算法，從分解優(yōu)化問題出發(fā)，在保證原有的分類精度情況下降低求解所需的時間，且該算法可以分布式實現(xiàn)。在該算法中，用一種較為簡單的方式近似計算目標函數(shù)Hessian矩陣的逆，然后通過迭代求出優(yōu)化問題的解。仿真結(jié)果表明，與現(xiàn)有的圖半監(jiān)督學習算法相比，該算法能在較短時間內(nèi)獲得較好的分類結(jié)果。

1 基礎(chǔ)知識

1.1 高光譜圖像簡介

與人眼的成像系統(tǒng)類似，傳統(tǒng)成像儀內(nèi)部感光元器件只能感應(yīng)到可見光頻段(360～830 nm)內(nèi)的電磁波，且成像時只能進行單寬波段成像，因此對成像結(jié)果的直觀感受是一張尺寸為m像素×n像素(以下簡寫為m×n)的彩色圖像。由于可見光頻段上的電磁波均可以由紅綠藍(RGB)三色光組合表示而成，傳統(tǒng)圖像也被稱為RGB圖像，并在處理時通常使用對應(yīng)RGB三個顏色分量的3張灰度圖對其進行表示，此時成像結(jié)果即為一個數(shù)據(jù)塊，由3張尺寸為m×n的圖片重疊而成[2]。RGB圖像低頻率分辨率的成像特點，使得相關(guān)研究極度依賴圖像內(nèi)包含的空間信息。因此，對于RGB圖像而言，空間分辨率是最為重要的特性。相比于RGB圖像成像儀，HSI成像儀所能感應(yīng)到的電磁波頻段更為寬廣，覆蓋范圍通常為紫外波段到近紅外波段。此外，HSI成像儀的另一重要特性是能進行多窄波段成像，即成像儀在成像過程中，把待測物體反射回的電磁波切分成多個波段，接著使用每個波段的電磁波進行成像，最后將多個成像結(jié)果合成為數(shù)據(jù)塊。這樣的成像方式使得HSI以尺寸為m×n×d的數(shù)據(jù)塊形式呈現(xiàn)，其中，m×n是成像儀對單個波段響應(yīng)的成像結(jié)果尺寸，d是成像時切分的波段數(shù)，同一個像素點在d個頻率上的不同響應(yīng)構(gòu)成像素點的頻率特性。高光譜圖像頻率特性如圖1所示。成像的特性不同，使得HSI相比RGB圖像擁有更為豐富的頻譜信息與更為精細的頻率分辨率。正因如此，大多數(shù)對HSI數(shù)據(jù)的研究主要從其頻率信息出發(fā)。

圖1 高光譜圖像頻率特性

1.2 分類問題與建模

在HSI各項研究中，分類是較為重要的研究內(nèi)容。其根據(jù)HSI數(shù)據(jù)的頻率信息，對每個像素點進行類別標記。如前所述，HSI表示為一個尺寸為m×n×d的數(shù)據(jù)塊，該數(shù)據(jù)塊由d張對應(yīng)不同波段的圖片組成。由于d張圖片都是對同一個目標進行成像，不同圖片上的相同位置像素點的值實際上就是該點對于不同頻率電磁波的響應(yīng)，而d個響應(yīng)就構(gòu)成該像素點所對應(yīng)物體的光譜特性。在HSI分類問題中，光譜特性是分類時的一個重要參考。光譜特性在引入更多信息的同時，也帶來了特征的維數(shù)問題，而維度過高會導(dǎo)致分類精度下降。因此，先使用圖建模算法對其進行降維，接著建立優(yōu)化問題，進而求解得出分類結(jié)果。圖是一種常見的數(shù)據(jù)結(jié)構(gòu)，目前已在無線傳感器網(wǎng)絡(luò)、社交網(wǎng)等場合中得到應(yīng)用[20]。圖由節(jié)點與邊組成，通常表示為G={V,E,W}，V與E分別為圖的節(jié)點集與邊集，W為圖的權(quán)矩陣，權(quán)矩陣內(nèi)為圖上權(quán)重值。節(jié)點之間通過邊相連接，邊描述節(jié)點間的鄰接關(guān)系與相似關(guān)系，邊上權(quán)重即為權(quán)矩陣中的元素，兩節(jié)點越相似，二者之間的權(quán)重值越大。此外，還常用拉普拉斯矩陣L=D-W、歸一化圖拉普拉斯矩陣Ln=D-1/2LD-1/2來表示圖的相關(guān)特性，其中D為度矩陣，其定義為

(1)

一個像素點數(shù)為N，頻段數(shù)為d的HSI數(shù)據(jù)通常用特征矩陣

X=[x1,x2,…,xN]∈RN×d

表示，矩陣中的每一行為對應(yīng)像素點的頻譜特征。根據(jù)該特征矩陣，用圖對HSI數(shù)據(jù)進行建模，所建模圖使用k近鄰圖(kNN圖)。在建模時，首先計算第一個節(jié)點與余下所有節(jié)點的歐式距離(這一距離由頻譜特征確定)，接著選擇最相近的k個節(jié)點作為鄰居并與之相連，而后重復(fù)這2個步驟直到所有的節(jié)點都與其最近的k個鄰居相連，再用每個節(jié)點與其的距離計算出權(quán)重值：

(2)

該值用于描述邊所連接的節(jié)點的相似程度，其中，xi∈R1×d與xj∈R1×d分別為第i個與第j個像素點的頻譜特征。通過以上步驟，便得到一個kNN圖G。像素點上的標簽用y=[yl;yu]表示，yl代表已知標簽，yu代表未知標簽，值為0。在實際的分類問題中，yl?yu。在圖半監(jiān)督分類問題中，根據(jù)已知部分標簽yl與所建模圖刻畫的數(shù)據(jù)特性學習出yu的標簽，完成分類。

2 分類問題求解

根據(jù)所建立的圖模型G={V,E,W}，關(guān)于HSI的c分類問題可歸結(jié)為

(3)

其中：yj為標簽one-hot編碼矩陣Y的第j列，表示第j類標簽在數(shù)據(jù)中的分布情況，Y的定義為

(4)

Ln為圖G的歸一化拉普拉斯矩陣。優(yōu)化問題可以理解為學習出一個比較符合所建模圖的標簽one-hot編碼矩陣F。得到F后，通過下式來取得最終的分類結(jié)果。

(5)

不難看出，圖半監(jiān)督學習的主要任務(wù)是在對F，即f1,f2,…,fc的求解上。c個向量f1,f2,…,fc的求解過程相同，因此僅對任一fj的求解進行分析，令f=fj，

(6)

顯然，目標函數(shù)是一個關(guān)于f的凸函數(shù)，且有解析解，解為f*=(I+α-1Ln)-1y。但在數(shù)據(jù)規(guī)模變大時，集中式求解矩陣的逆會變得困難。

2.1 優(yōu)化求解

式(6)可用牛頓法來求解。其一階與二階梯度信息分別為

(7)

即目標函數(shù)的Hessian矩陣H為αI+Ln。在牛頓法求解過程中，需要在每步迭代中計算Hessian矩陣的逆以求出步長sk=H-1▽φ(fk)，而這在矩陣規(guī)模較大的情況下會相當耗時，在此提出一種近似牛頓法。

對于圖歸一化拉普拉斯Ln，有Ln=I-Wn，其中Wn為圖的歸一化權(quán)矩陣，可進一步分解為2個部分；對角部分Wnd與非對角部分Wnu，其中Wnd=diag(Wn)，且Wn=Wnd+Wnu?；诖?，同樣可將Hessian矩陣H分割為對角部分與非對角部分，即

H=A-B，

(8)

其中：

(9)

其中，θ≥0為控制矩陣分解的參數(shù)，設(shè)置為1。此外，所建模的圖都不帶自環(huán)，因此其歸一化權(quán)矩陣的對角部分均為0，即Wnd=0?；诖?，取θ=1時，式(9)可進一步更新為

(10)

此時，式中目標函數(shù)在第k次迭代中時的牛頓步長為sk=-(A-B)-1▽φ(fk)。根據(jù)文獻[21]，可用

sk=-(I-QB)A-1▽φ(fk)

(11)

對其進行近似。由文獻[21]可知，Q與Hessian矩陣的逆等效，并可通過泰勒公式對其進行近似，令P=Wn-αI，則

Q=(I-P)-1≈I+P，

(12)

式(11)中A為對角矩陣，因此無需進行矩陣求逆即可計算出步長，進而降低了計算復(fù)雜度。迭代過程為

(13)

2.2 分布式求解

因所建圖是kNN圖，基于圖的局部特性，上一小節(jié)提出的求解思路可用分布式的方式來實現(xiàn)。在分布式計算中，優(yōu)化問題被分解為多個子問題并分配到計算節(jié)點上，此時復(fù)雜度較大的優(yōu)化問題轉(zhuǎn)換為多個復(fù)雜度較低的小問題。分布式計算可充分有效地利用計算資源，且能降低計算復(fù)雜度。分布式算法中，計算節(jié)點除計算能力外，還具有一定的通信與存儲能力，且每個節(jié)點都已存儲了圖節(jié)點的鄰居信息與已知標簽信息。計算節(jié)點可存儲多個圖節(jié)點信息，在此假設(shè)一個計算節(jié)點僅存儲一個圖節(jié)點，則式(6)可轉(zhuǎn)換為

(14)

其中，fj、yj分別為f、y在圖中第j個節(jié)點上的值。顯然，式(14)的前半部分即為式中匹配項的分解，將匹配項分解為N個相互獨立的部分并分配到每個節(jié)點上。分解后，節(jié)點i上的一階梯度信息為

(15)

其中，wij為Wn中第i行j列的元素，在圖上則對應(yīng)節(jié)點i與節(jié)點j之間的權(quán)重值。由此，節(jié)點i上進行的第k次迭代則為

(16)

在迭代完成后，所有節(jié)點輸出的fi便可組合為one-hot編碼矩陣F的對應(yīng)列。通過式(15)與式(16)可看出，節(jié)點i在迭代過程中僅需獲得其周邊鄰居上f、e以及u的值即可完成迭代。對于節(jié)點i，分布式算法如下：

while (j≤c) do

令y=Y:,j，k=0，f0=0，f1=1

4)計算

6)計算步長

end while

令Fij=fi；

end while

對算法過程分析可知，每個節(jié)點在一次迭代過程中需要與周邊鄰居節(jié)點進行3次通信。

3 仿真結(jié)果與分析

對Kennedy Space Center(KSC)與Indian Pines數(shù)據(jù)集[22]進行分類仿真。KSC數(shù)據(jù)內(nèi)有202個波段圖片，可分為13類，類別分布不平均。Indian Pines內(nèi)保留了200個波段數(shù)據(jù)，圖片內(nèi)像素分為16類，其類別分布更不平均，各類樣本數(shù)差距更大。

仿真時，設(shè)置單樣本已知個數(shù)分別為5、10、15、20，IndianPines的第7與第9類的已知數(shù)據(jù)最多為10個，且每種設(shè)置下均隨機生成30組待學習數(shù)據(jù)，最后將30組數(shù)據(jù)的學習結(jié)果取平均作為最終結(jié)果。參數(shù)的設(shè)置如表1所示。為了更好衡量分類效果，仿真使用總體精度(OA)、平均精度(AA)以及Kappa系數(shù)三者的平均值作為評價指標。

表1 參數(shù)設(shè)置

圖2、3分別為不同算法在不同數(shù)據(jù)下的OA曲線。從圖2可看出，在KSC數(shù)據(jù)中，本算法的分類效果與文獻[19]算法大致相同，優(yōu)于文獻[20]中算法。從圖3可看出，在Indian Pines數(shù)據(jù)中，本算法結(jié)果與文獻[19]中算法一致，且明顯優(yōu)于文獻[20]算法的結(jié)果。

圖2 KSC數(shù)據(jù)下不同算法OA曲線

圖3 Indian Pines數(shù)據(jù)下不同算法OA曲線

表2與表3分別為在各類已知樣本數(shù)為15的情況下，各算法在不同數(shù)據(jù)下的運行時間和各項分類評估參數(shù)。由于在不同已知樣本數(shù)下的結(jié)果分布一致，僅選取數(shù)量為15的仿真結(jié)果。由表2可看出，在KSC數(shù)據(jù)中，本算法比文獻[19]算法所用時間大大減少，雖然耗時高于文獻[20]算法，但本算法各項評估參數(shù)都表明分類效果要更好。而表2表明，在Indian Pines數(shù)據(jù)中，本算法的分類效果遠超文獻[20]，且所消耗的計算時間與文獻[20]幾乎一致。文獻[19]算法基于各類樣本分布均衡，且類別數(shù)較少的前提，因此會在Indian Pines數(shù)據(jù)中出現(xiàn)分類效果惡化的情況。

表2 KSC數(shù)據(jù)仿真結(jié)果

表3 Indian數(shù)據(jù)仿真結(jié)果

圖4、5分別為本算法在不同數(shù)據(jù)下分類時的迭代情況。由于在每個類別迭代的趨勢一致，任選其中一條做展示。通過2圖可發(fā)現(xiàn)，本算法在不同數(shù)據(jù)下均能較快收斂。而由之前算法分析可知，本算法每步的迭代都需要與鄰居進行3次通信才能完成信息交換。顯然，該算法以單步迭代的多次通信換取了較快的迭代速度。

圖4 KSC數(shù)據(jù)分類迭代曲線

以上2個數(shù)據(jù)的仿真結(jié)果及算法分析表明，本算法在數(shù)據(jù)量較大時更能體現(xiàn)出其優(yōu)勢，更適合數(shù)據(jù)量較大、類別數(shù)較多的HSI分類任務(wù)。

圖5 Indian數(shù)據(jù)分類迭代曲線

4 結(jié)束語

針對HSI分類中未標記數(shù)據(jù)多、數(shù)據(jù)維度高、計算復(fù)雜度高等問題，提出一種基于圖模型的分類算法，且該算法可以分布式運行。該算法把分類任務(wù)歸結(jié)為一個無約束的優(yōu)化問題，首先對優(yōu)化問題進行拆分，并將拆分后的子優(yōu)化問題分配到各個節(jié)點上，再用多計算單元對小優(yōu)化問題迭代求解。仿真結(jié)果表明，本算法在數(shù)據(jù)規(guī)模大、類別多的分類任務(wù)下具有較大優(yōu)勢。后續(xù)工作將通過把圖信號處理理論應(yīng)用到數(shù)據(jù)建模中，克服其對于樣本數(shù)分布不均衡的局限性，使其能更好地處理HSI分類問題。