童佳楠

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

關(guān)鍵詞： 遙感圖像； 圖像分類； mean shift； 錨點

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

0 引 言

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

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

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

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

1 AGR圖像分類方法

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

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

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

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

其中Z是一個權(quán)值矩陣，表示了錨點與所有樣本點的線性關(guān)系：

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

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

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

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

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

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

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

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

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

2 本文方法流程

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

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

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

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

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

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

最后，就可以得到全局最優(yōu)解：

[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}]

輸出：圖像分類結(jié)果

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

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

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

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

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

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

3 算法復(fù)雜度分析

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

4 實驗結(jié)果與分析

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

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

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

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

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

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

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

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

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

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

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

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

5 結(jié) 語

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

參考文獻

[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的遙感圖像監(jiān)督分類方法比較研究[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.