童佳楠

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

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

中圖分類號： TN957.52?34； TP79 文獻(xiàn)標(biāo)識碼： 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)督方法，需要運(yùn)用大量的訓(xùn)練樣本才能獲取較好的分類結(jié)果，而標(biāo)記樣本的獲取代價(jià)高昂，也容易出現(xiàn)分類器過擬合與訓(xùn)練樣本的問題。

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

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

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

1 AGR圖像分類方法

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

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

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

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

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

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

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

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

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

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

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

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

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

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

2 本文方法流程

假設(shè)已標(biāo)記樣本[xi（i=1，2，…，l）]，其標(biāo)記信息為[yi∈{1，2，…，c}]，[c]為類別個(gè)數(shù)。用[Y=[y1，y2，…，yc]∈Rl×c]表示已標(biāo)記樣本的標(biāo)記信息，如果[yi=j]，[Yij=1]，否則[Yij=0]。用mean shift聚類算法對遙感圖像進(jìn)行聚類，得到各個(gè)類別的聚類中心，把每個(gè)聚類中心作為一個(gè)錨點(diǎn)，得到AGR方法中的錨點(diǎn)集合。此時(shí)就需要求得錨點(diǎn)的標(biāo)簽預(yù)測矩陣[A=[a1，a2，…，ac]∈Rm×c]。選擇被廣泛應(yīng)用的圖拉普拉斯正則化項(xià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]矩陣的子矩陣，只包含標(biāo)記樣本；[·F]是Frobenius范數(shù)；取[γ>0]，為正則化參數(shù)。那么縮小后的拉普拉斯矩陣為：

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

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

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

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

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

得到了錨點(diǎn)的標(biāo)記信息，那么未標(biāo)記樣本的標(biāo)記信息就可以通過下式得到：

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

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

具體的算法步驟如下：

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

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

（1） 用mean shift算法對遙感圖像進(jìn)行聚類，得到m個(gè)類，從每一個(gè)聚類中選取一個(gè)點(diǎn)作為錨點(diǎn)；

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

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

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

（5） 根據(jù)式（10）計(jì)算錨點(diǎn)標(biāo)簽預(yù)測矩陣[A*]；

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

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

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

4 實(shí)驗(yàn)結(jié)果與分析

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

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

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

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

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

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

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

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

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

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

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

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

5 結(jié) 語

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

參考文獻(xiàn)

[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.