基于錨點建圖的半監督分類在遙感圖像中的應用

童佳楠

摘 要： 針對基于圖的半監督圖像分類方法擴展性差的問題，結合了mean shift圖像聚類算法和基于錨點建圖的方法并將其應用于遙感圖像的分類中。首先采用mean shift聚類算法對遙感圖像聚類；其次根據基于錨點建圖的半監督分類方法，選取聚類中心作為錨點，利用錨點集和標記樣本集建圖，達到縮小圖規模的目的，并建立錨點與樣本間的關聯矩陣；然后通過分類器得到錨點的標記信息；最后由樣本與錨點間的關聯矩陣還原得到遙感圖像的分類結果。實驗結果表明，該方法對遙感圖像分類時，能夠有效地降低計算復雜度，同時獲取較好的分類結果。

關鍵詞： 遙感圖像； 圖像分類； mean shift； 錨點

中圖分類號： TN957.52?34； TP79 文獻標識碼： A 文章編號： 1004?373X（2016）22?0092?0

0 引 言

遙感圖像具有較高的光譜分辨率，在航天、地質勘探、農業等領域獲得了越來越多的應用，遙感圖像分類在遙感圖像應用中具有重要的作用。但對遙感圖像分類也面臨以下難題：其一是如果采用傳統的非監督方法對遙感圖像直接分類，因遙感圖像的復雜性和特殊性，很難獲得比較滿意的結果；其二采用監督方法，需要運用大量的訓練樣本才能獲取較好的分類結果，而標記樣本的獲取代價高昂，也容易出現分類器過擬合與訓練樣本的問題。

半監督學習[1]可以很好地解決上述問題，首先大量的廉價的無標記樣本也包含樣本特征信息，其次遙感圖像中標記樣本的獲取十分昂貴。半監督學習可以利用少量的已標記樣本，結合大量的無標記樣本建立分類器完成學習任務。基于圖的半監督圖像分類在近年來圖像研究領域成為了一個研究熱點，此方法結合圖理論，能夠充分利用圖像中的無標記樣本信息，分類性能較好，且目標函數優化簡單，因此更加高效，目前也有許多基于圖的半監督分類方法[2?6]。

基于圖的半監督圖像分類方法是建立在圖理論的基礎上，但算法計算速度依賴于所構建圖的規模大小，當數據規模過大時，如果還是每一個圖節點代表一個樣本點，圖規模就會很龐大，計算的時間復雜度會很高，例如線性近鄰傳遞算法（Linear Neighborhood Propagation）、局部與全局一致性算法（Local and Global Consistency），其計算復雜度為[O（n3）]，[n]為樣本個數。為了降低算法的復雜度，Blum 和Chawla提出了圖的最小割（Mincut）算法，并將其時間復雜度降低到了[O（cn2）]，這里[c]為類別數。但最小割算法可能存在多個解，得到不同的分類結果。

2010年Liu等提出基于錨點建圖的半監督分類方法[7]（Anchor Graph Regularization，AGR）。首先采用K?means算法對數據聚類，將聚類中心作為錨點得到錨點集，其次利用錨點與已標記樣本建圖，縮小了圖規模，時間復雜度降為[Om2n，m?n]，[n]為樣本總數，[m]為聚類個數。但K?means聚類算法消耗時間過長，且遙感圖像混合像元問題使部分像元很難進行非此即彼的劃分，部分區域地物類別邊界是過渡性的，沒有明顯邊界劃分，因此K?means不適宜對遙感圖像聚類。針對上述問題，本文采用mean shift聚類算法代替K?means算法對遙感圖像聚類，縮短了聚類時間，mean shift算法對噪聲也有一定的魯棒性，可以解決噪聲點帶來的干擾，提高聚類的有效性。其次在每個聚類中隨機選取一個點作為錨點，得到錨點集，并與標記樣本集建立圖。該方法不僅降低了算法復雜度，可以處理大規模圖像分類問題，同時在遙感圖像分類中具有較好的分類結果。

1 AGR圖像分類方法

設樣本數據集為[x=xini=l?Rd]，共有[n]個樣本，[l]個是已標記樣本，剩余的為未標記樣本。為了解決大規模數據問題，將標記預測函數定義為一個對錨點的加權平均函數，當得到錨點的類別信息后，就可以通過映射關系得到與錨點密切相關的無標記樣本的類別信息。將錨點加權平均函數表示為：[UA=ukmk=1?Rd]，其中[uk]代表錨點，標記預測函數為：

[f（xi）=k=1mZikf（uk）] （1）

在這里定義兩個向量[f=[f（x1），f（x2），…，f（xn）]T]和[a=[f（u1），f（u2），…，f（um）]T]；[a]為錨點的軟標簽預測矩陣；[m]為錨點個數。式（1）可以寫成：

[f=Za， Z∈Rn×m， m?n] （2）

其中Z是一個權值矩陣，表示了錨點與所有樣本點的線性關系：

[Zik=Kh（xi，uk）k∈Kh（xi，uk）， ?k∈] （3）

這里使用的是高斯核函數[Kh（xi，uk）=][exp-xi-uk22h2]。[?[1：m]]是一個保存[xi]的[s]個最近鄰錨點的索引，為了提高計算效率，規定每一個樣本[xi]只與[s]個[Zik]中值最大的錨點具有連接關系，其他連接均為0。

由Z矩陣可以得到鄰接矩陣：

[W=ZΛ-1ZT] （4）

式中，[Λ∈Rm×m]是一個對角矩陣：

[Λkk=i=1nZik] （5）

由[s]的取值可以知道，所有的樣本點都只與部分近鄰錨點存在連接關系，所以矩陣W是稀疏的。Zhu提出稀疏圖對算法的性能的影響優于全連通圖[1]。因為全連通圖中，每個樣本的鄰接信息中含有大量重復的、干擾的信息，而稀疏圖在連接不同樣本時含有較少的錯誤信息，對算法結果有正確的指導。由式（4）定義的鄰接矩陣所構造的圖就是Anchor Graph。最后Anchor Graph的圖拉普拉斯矩陣為：

[L=D-W=I-ZΛ-1ZT] （6）

式中：D為對角線矩陣，[Dii=j=1nWij]。

2 本文方法流程

假設已標記樣本[xi（i=1，2，…，l）]，其標記信息為[yi∈{1，2，…，c}]，[c]為類別個數。用[Y=[y1，y2，…，yc]∈Rl×c]表示已標記樣本的標記信息，如果[yi=j]，[Yij=1]，否則[Yij=0]。用mean shift聚類算法對遙感圖像進行聚類，得到各個類別的聚類中心，把每個聚類中心作為一個錨點，得到AGR方法中的錨點集合。此時就需要求得錨點的標簽預測矩陣[A=[a1，a2，…，ac]∈Rm×c]。選擇被廣泛應用的圖拉普拉斯正則化項[ΩG（f）=12fTLf]，可得到半監督學習框架 ：

[minA=[a1，a2，…，ac]Γ（A）=12j=1cZlaj-yj2+γj=1cΩG（Zaj） =12ZlA-Y2F+γ2tr（ATZTLZA）] （7）

式中：[Zl∈Rl×m]是[Z]矩陣的子矩陣，只包含標記樣本；[·F]是Frobenius范數；取[γ>0]，為正則化參數。那么縮小后的拉普拉斯矩陣為：

[L=ZTLZ=ZT（I-ZΛ-1ZT）Z =ZTZ-（ZTZ）Λ-1（ZTZ）] （8）

縮小后的拉普拉斯矩陣存儲空間更小，易于計算，空間復雜度為[O（m2）]，時間復雜度為[O（m3+m2n）]。這時，目標函數[Γ（A）]進一步簡化為：

[Γ（A）=12ZlA-Y2F+γ2tr（ATLA）] （9）

最后，就可以得到全局最優解：

[A*=（ZTlZl+γL）-1ZTlY] （10）

得到了錨點的標記信息，那么未標記樣本的標記信息就可以通過下式得到：

[yi=argmaxj∈{1，2，…，c}Ziajλj， i=l+1，l+2，…，l+n] （11）

式中：[Zi∈Rl×m]表示Z矩陣的第i行。[λj=ITZaj]表示歸一化因子，作用是平衡傾斜的類分布。

具體的算法步驟如下：

輸入：已標記樣本[xi（i=1，2，…，l）]，標記信息[yi∈{1，2，…，c}]

輸出：圖像分類結果

（1） 用mean shift算法對遙感圖像進行聚類，得到m個類，從每一個聚類中選取一個點作為錨點；

（2） 選擇合適的[γ]；近鄰錨點個數s取3；

（3） 計算Z矩陣，根據式（4）計算鄰接矩陣W；

（4） 根據式（6）計算圖拉普拉斯矩陣L；

（5） 根據式（10）計算錨點標簽預測矩陣[A*]；

（6） 根據式（11）計算未標記樣本的標記。

3 算法復雜度分析

基于圖的半監督分類方法，大多數方法中是每個樣本作為一個圖節點建立圖，所以計算復雜度為[O（n3）]，其中[n]是樣本個數。本文方法中，mean shift的計算復雜度是[O（dn2t）]，其中[d]是數據的空間維度，[t]是迭代次數；基于錨點的算法的計算復雜度[7]是[O（m2n）]，所以本文方法的計算復雜度是[O（dn2t）]+[O（m2n）]，且m是聚類后得到的聚類中心個數，[m?n]，所以本文方法的計算復雜度是遠小于原始基于圖的半監督分類方法的計算復雜度[O（n3）]。

4 實驗結果與分析

本文在Matlab R2012a下計算機內存為2 GB，CPU為Intel Core i3，頻率為2.53 GHz的機器上運行實驗。實驗采用的遙感圖像是IKONOS衛星圖像，IKONOS衛星圖像包含一個全色波段，分辨率為1 m，四個多光譜波段，分辨率為4 m。圖像大小為400×400，實驗中對四個多光譜波段構成的遙感圖像進行分類，3個RGB多光譜波段構成的真彩色圖像如圖1所示。根據實驗區的特點，具體樣本分類類別如表1所示。

圖1中最左側兩片顏色灰白的區域是水泥建筑場地，右上側灌木林中間的一個藍色區域是一個房屋，這兩片區域在本文實驗中都歸為“公路居民區”類別。因此本次實驗樣本類別個數為：“農田”像元點數32 433，“荒裸地”像元點數41 825，“植被”像元點數67 978，“公路居民區”像元點數17 764。

原文方法采用K?means聚類算法，不適應對遙感圖像聚類，所以本文對遙感圖像的分類結果并未與原文方法進行對比，而與遙感圖像處理平臺ENVI自帶的監督支持向量機（SVM）方法進行對比。

本文實驗SVM方法參數取值：核類型（Kernel Type）選擇Polynomial，核心多項式的次數取4，Classification Probability Threshold取0，其他參數采用默認值。

本文實驗中標記樣本均為人工選取，實驗分四次，四次實驗中每類標記樣本個數分別為5，20，50，100，每一次實驗中所有實驗方法均采用相同的標記樣本，且每次實驗都在上次已有標記樣本的基礎上添加新的標記樣本。本文對實驗結果的評價采用了Kappa系數和像元分類正確率（Pixel Classification Rate，PCR）：

[PCR=正確分類像元數圖像總像元數] （12）

圖2和圖3分別為每類標記樣本為50和100時，本文方法和監督SVM方法的實驗結果。遙感圖像中樣本分為四類，紅色代表“荒裸地”的樣本點，綠色代表“植被”的樣本點，藍色代表“農田”的樣本點，黃色代表“公路居民區”的樣本點。對比圖2和圖3，可以發現，本文方法優于監督SVM方法，圖4中區域標號圖像為1的區域是農田和沒有農作物荒裸地區域，沒有灌木植被，本文方法明確地分為農田和荒裸地兩類，而SVM方法中將一部分樣本錯分為植被；在標號為2的區域與右上角的空白區域一樣均為裸地，本文方法分類效果很好，而SVM方法分類效果顯然較差，部分樣本錯分為農田類別；標號為3的區域中，有一排灌木植被在農田中間，即右側的很少一部分還屬于農田，可以看到還有農作物存在，SVM方法中將此少部分農田錯分為裸地，本文方法大部分樣本分類正確；在標號4的區域，可以看到是農田和裸地的分界處，而可以明顯看到此處屬于農田，只不過左側部分不存在農作物，所以歸為裸地類別，在SVM方法分類結果中許多樣本點被錯分為植被，而本文方法只有極少量樣本分錯，這是因為半監督學習的流形假設，處于很小局部區域內的樣本可能具有相似的標記，此處的樣本明顯與鄰近的農田相似性更大。

對遙感圖像的分類精度的評價指標是以分類結果的混淆矩陣為基礎，總體分類精度和Kappa系數都要通過混淆矩陣計算得到，而為了更直觀地評價兩種方法的分類效果和優缺點，本文列出了每類標記樣本數為100的分類結果的混淆矩陣：兩種方法在每類標記樣本為100時的分類結果見表2和表3。

混淆矩陣中每行的總和為每一類樣本的真實樣本數，每一列的總和為分類結果中每一類的總樣本數，括號內的值為混淆矩陣對角線的和，即分類正確的樣本總數。漏分誤差即每類真實樣本中沒有被正確識別出來的樣本比例；錯分誤差為分類結果中其他類別樣本被錯分為此類的樣本占總和的比例。

通過混淆矩陣的數字可以直觀地看到，本文方法的每一類樣本的錯分誤差都小于SVM方法的錯分誤差；本文方法對“植被”類別的分類正確率不如SVM方法的分類結果，但本文方法對細節處的分類效果更優于SVM方法，例如在圖4中右側的灌木林，本文方法的分類結果中，瑣碎的極少量的裸地都被分出來；“荒裸地”和“農田”類別的樣本分類正確率都明顯優于SVM方法；而“公路居民”類別正確率低于SVM方法，由混淆矩陣可以看到是錯分為“荒裸地”的樣本較多，這是因為圖4中最左側的居民區建筑因為曝光太強，錯分為“荒裸地”； “公路居民區”類別和“農田”類別樣本差別明顯，本文方法把“公路居民區”錯分為“農田”的樣本數為零，而SVM方法的錯分數是9，本文方法對類別“公路居民區”和“農田”之間的區分更優；本文方法總體精度和Kappa系數也明顯高于監督SVM的。具體的分類結果統計如表4所示。

從表4可以看出，本文方法分類結果明顯優于監督SVM方法，而監督SVM方法是ENVI軟件的監督分類方法中效果最優的方法[8]，且監督SVM方法在小樣本時具有良好的分類效果。但半監督的學習方法，結合無標記樣本，優于監督學習方法，提高了分類性能。如標記樣本數較少，為5和20時，無標記樣本作用明顯，分類精度和Kappa系數提高較大。通過觀察圖像和實驗發現，本此實驗的遙感圖像中樣本比較復雜，地物交錯比較嚴重，邊界過度不明顯，不同于城市居民區邊界清晰，這就給分類增加了難度，這也是分類精度不是很高的原因之一。實驗結果驗證了本文方法在遙感圖像分類中的有效性，相比監督SVM方法獲得了更好的分類效果。

本文方法在圖像聚類選取錨點時采用mean shift聚類算法，聚類樣本數160 000，平均用時9.4 s。原文[9]方法采用K?means聚類算法選取錨點，文中給出了兩次實驗結果中的聚類時間，7 291個樣本聚類時間是7.65 s；630 000個樣本聚類時間是195.16 s。因此mean shift聚類算法相比K?means算法縮短了聚類時間。

5 結 語

基于圖的半監督圖像分類方法通常因為數據規模大而導致內存空間不足和分類時間過長，而遙感圖像通常規模較大且地物復雜、信息量大，所以影響了其在遙感圖像分類中的應用。本文首先采用mean shift算法對遙感圖像聚類得到錨點集，利用錨點集和標記樣本集建圖，縮小了圖規模，降低了計算復雜度，其次通過分類方法得到錨點的類別信息，最后映射還原到整個樣本集，得到遙感圖像分類結果。AGR方法解決了大規模圖像分類，本文采用mean shift算法縮短了錨點選取時間。實驗結果表明，本文方法在遙感圖像分類中獲得了較好的分類結果，驗證了其對遙感圖像分類的有效性。

參考文獻

[1] HUANG G， SONG S， GUPTA J， et al. A second order cone programming approach for semi-supervised learning[J]. Pattern recognition， 2013， 46（12）： 3548-3558.

[2] XIE W， LU Z， PENG Y， et al. Graph?based multimodal semi?supervised image classification [J]. Neuro computing， 2014， 138： 167?179.

[3] BLUM A， CHAWLA S. Learning from labeled and unlabeled data using graph mincuts [C]// Proceedings of 2001 International Conference on Machine Learning. San Francisco： ACM， 2001： 19?26.

[4] WANG F， ZHANG C. Label propagation through linear neighborhoods [J]. IEEE transactions on knowledge and data engineering， 2008， 20（1）： 55?67.

[5] ZHOU D， BOUSQUET O， LAL T N， et al. Learning with local and global consistency [J]. Advances in neural information processing systems， 2004， 16（4）： 321?328.

[6] ZHU X J， GHAHARMANI Z， LAFFERTY J. Semi?supervised learning using Gaussian fields and harmonic functions [C]// Proceedings of 20th International Conference on Machine Learning. Menlo Park： AAAI， 2003： 912?919.

[7] LIU W， HE J， CHANG S F. Large graph construction for scalable semi?supervised learning [C]// Proceedings of the 27th International Conference on Machine Learning. Haifa： ACM， 2010： 679?686.

[8] 閆琰，董秀蘭，李燕.基于ENVI的遙感圖像監督分類方法比較研究[J].北京測繪，2011（3）：14?16.

[9] YU G， ZHANG G， DOMENICONI C， et al. Semi?supervised classification based on random subspace dimensionality reduction [J]. Pattern recognition， 2012， 45（3）： 1119?1135.

[10] CHENG Y. Mean shift， mode seeking， and clustering [J]. IEEE transactions on pattern analysis and machine intelligence， 1995， 17（8）： 790?799.

[11] WANG Y， CHEN S， ZHOU Z H. New semi?supervised classification method based on modified cluster assumption [J]. IEEE transactions on neural networks and learning systems， 2012， 23（5）： 689?702.

[12] D?PIDO I， LI J， MARPU P R， et al. Semi?supervised self?learning for hyperspectral image classification [J]. IEEE transactions on geoscience and remote sensing， 2013， 51（7）： 4032?4044.