基于符號(hào)規(guī)范化割的半監(jiān)督學(xué)習(xí)與圖像分割

劉先鋒，石 靜，陳 明，楊予丹

(湖南師范大學(xué) 信息科學(xué)與工程學(xué)院，長(zhǎng)沙 410081)

1 引 言

半監(jiān)督學(xué)習(xí)(Semi-supervised learning，簡(jiǎn)稱(chēng)SSL)是機(jī)器學(xué)習(xí)的一個(gè)重要分支[1].SSL研究如何同時(shí)利用無(wú)標(biāo)簽的樣例與部分監(jiān)督信息改進(jìn)學(xué)習(xí)性能.SSL的研究具有重要的實(shí)用價(jià)值，因?yàn)樵趯?shí)際應(yīng)用中減少標(biāo)記樣本的使用能夠大幅縮減人力、時(shí)間和資源的開(kāi)銷(xiāo)，從而降低生產(chǎn)成本[2].在過(guò)去的十幾年時(shí)間里，涌現(xiàn)了許多基于圖的SSL方法.基于圖的SSL以監(jiān)督信息為輔，用圖來(lái)表達(dá)數(shù)據(jù)，通過(guò)對(duì)圖的分析來(lái)完成學(xué)習(xí)任務(wù).鑒于圖的強(qiáng)大表達(dá)力以及關(guān)于圖的成熟數(shù)學(xué)理論與龐大算法體系，這類(lèi)SSL方法取得了大量成果[3].

基于圖的SSL通常以非負(fù)權(quán)重的網(wǎng)絡(luò)表達(dá)數(shù)據(jù)，基于圖拉普拉斯來(lái)構(gòu)建一個(gè)目標(biāo)函數(shù)，將(弱)監(jiān)督信息表達(dá)為目標(biāo)函數(shù)的損失部分或者作為約束條件，通過(guò)優(yōu)化該目標(biāo)函數(shù)來(lái)訓(xùn)練學(xué)習(xí)器，從而預(yù)測(cè)出樣本(簇)標(biāo)簽.圖劃分是在基于圖的SSL上獲得最多關(guān)注的一類(lèi)圖分析技術(shù)，典型的劃分準(zhǔn)則包括最小割、比率割、規(guī)范化割等[1].由于規(guī)范化割(Normalized cut，簡(jiǎn)稱(chēng)NCut)具有劃分平衡性，在許多問(wèn)題上(例如圖像分割)具有較好的表現(xiàn)，因而獲得了更多關(guān)注.對(duì)于類(lèi)標(biāo)簽形式，基于圖的SSL實(shí)際上是在圖上將監(jiān)督信息傳播至未標(biāo)記樣本[1].自從Blum和Chawla[4]提出基于最小割法的SSL方法之后，相繼涌現(xiàn)了比率割、規(guī)范化割等半監(jiān)督方法[1].一些SSL算法假定(弱)監(jiān)督信息可以表達(dá)為成對(duì)約束關(guān)系：必連和勿連關(guān)系，分別用于表達(dá)兩(組)數(shù)據(jù)是否在同一個(gè)分組內(nèi).基于成對(duì)關(guān)系矩陣的圖聚類(lèi)模型能夠自然地刻畫(huà)這類(lèi)成對(duì)關(guān)系，例如，Basu等人利用隱馬爾科夫隨機(jī)場(chǎng)(HMRF)表達(dá)必連和勿連約束[5]；Kulis等[6]對(duì)成對(duì)約束進(jìn)行了規(guī)范化處理以適應(yīng)圖聚類(lèi)的比率形式，提出了經(jīng)典的HMRF-半監(jiān)督圖聚類(lèi)框架.

圖像分割是數(shù)字圖像處理、計(jì)算機(jī)視覺(jué)領(lǐng)域的基本問(wèn)題之一，它是指根據(jù)圖像的灰度、顏色、紋理等特征把圖像劃分為具有某種特性的若干區(qū)域.目前，在處理復(fù)雜和變化多端的現(xiàn)實(shí)世界圖像上，尚無(wú)能夠與人腦媲美的全自動(dòng)分割算法.半監(jiān)督分割利用box、劃線等形式的提示信息來(lái)引導(dǎo)分割過(guò)程，一批典型的交互式圖像分割方法以半監(jiān)督NCut為內(nèi)核.例如，Yu和Shi等[7]提出了可以處理必連約束的方法，Eriksson等[8]、Chew等[9]提出了可以同時(shí)處理必連和勿連約束的方法.

上述SSL方法需根據(jù)樣例之間的關(guān)系預(yù)先構(gòu)造圖.這類(lèi)方法通常采用無(wú)符號(hào)圖(或稱(chēng)網(wǎng)絡(luò))表征數(shù)據(jù)，它用非負(fù)權(quán)重衡量節(jié)點(diǎn)之間的相似性，難以區(qū)分無(wú)關(guān)、消極/對(duì)立等關(guān)系.實(shí)際上，有許多真實(shí)復(fù)雜網(wǎng)絡(luò)系統(tǒng)中本就包含著對(duì)立/消極關(guān)系，比如萬(wàn)維網(wǎng)、信任網(wǎng)絡(luò)等[10].人們?cè)絹?lái)越意識(shí)到，邊的符號(hào)屬性在許多挖掘任務(wù)中體現(xiàn)了附加價(jià)值[11].對(duì)于非圖型數(shù)據(jù)，在構(gòu)圖時(shí)引入邊的符號(hào)屬性，具有更強(qiáng)的表達(dá)力.缺失的邊具有0權(quán)重，可能是由于兩個(gè)節(jié)點(diǎn)的距離太遠(yuǎn)或者它們的特征具有極低的相似性，也有可能是它們本就相異、甚至相斥的.然而，無(wú)符號(hào)網(wǎng)絡(luò)并不能區(qū)別對(duì)待這些情形，符號(hào)網(wǎng)絡(luò)則可借助負(fù)邊將所隱含的互斥關(guān)系顯式地表達(dá)出來(lái).

本文在符號(hào)網(wǎng)絡(luò)的規(guī)范化割(Signed Normalized Cut，SNCut)基礎(chǔ)上，提出了基于成對(duì)約束的半監(jiān)督學(xué)習(xí)方法，并在典型數(shù)據(jù)集上驗(yàn)證了負(fù)邊的附加價(jià)值.進(jìn)一步的，將SNCut應(yīng)用于半監(jiān)督圖像分割，展示了負(fù)邊對(duì)分割效果的提升效果.為了提升邊界對(duì)齊性，引入了馬爾科夫隨機(jī)場(chǎng)(Markov Random Field，MRF)正則化項(xiàng)，構(gòu)建SNCut&MRF目標(biāo)函數(shù)，并采用界優(yōu)化思想和圖割算法進(jìn)行求解.實(shí)驗(yàn)結(jié)果表明，SNCut&MRF相比一些經(jīng)典分割方法有更好的分割性能，在邊界處表現(xiàn)良好.

本文的組織結(jié)構(gòu)如下：第2節(jié)介紹了無(wú)符號(hào)網(wǎng)絡(luò)與符號(hào)網(wǎng)絡(luò)的規(guī)范化割；第3節(jié)在基于符號(hào)網(wǎng)絡(luò)的規(guī)范化割基礎(chǔ)上，提出了一種半監(jiān)督學(xué)習(xí)途徑，并在UCI數(shù)據(jù)集上進(jìn)行了測(cè)試，驗(yàn)證了負(fù)邊的附加價(jià)值；第4節(jié)將其應(yīng)用于圖像分割，進(jìn)一步展示了負(fù)邊的效應(yīng)，并針對(duì)邊界問(wèn)題引入了MRF正則化項(xiàng)，提出了改進(jìn)模型和相應(yīng)的優(yōu)化算法；第5節(jié)對(duì)本文所提出的方法進(jìn)行了詳細(xì)的實(shí)驗(yàn)分析.

2 規(guī)范化割

本節(jié)首先介紹了(無(wú)向的)無(wú)符號(hào)網(wǎng)絡(luò)與符號(hào)網(wǎng)絡(luò)上的規(guī)范化割，然后提出了基于符號(hào)網(wǎng)絡(luò)的半監(jiān)督聚類(lèi)準(zhǔn)則.與無(wú)符號(hào)圖不同，我們以負(fù)邊表達(dá)了勿連約束.這里，我們僅考慮2-way的劃分問(wèn)題.

2.1 無(wú)符號(hào)圖的規(guī)范化割

(1)

其中(X1,…,XK)∈I，I是分組指示矩陣取值空間，D=diag(d1,…,dn)為度矩陣，L=D-W為圖G的拉普拉斯矩陣.

2.2 符號(hào)規(guī)范化割

圖1 符號(hào)網(wǎng)絡(luò)示意

我們將符號(hào)網(wǎng)絡(luò)上的規(guī)范化割稱(chēng)為符號(hào)規(guī)范化割(Signed Normalized Cut，SNCut).根據(jù)文獻(xiàn)[12,13]，SNCut定義為：

(2)

3 基于符號(hào)規(guī)范化割的半監(jiān)督學(xué)習(xí)

NCut應(yīng)用于標(biāo)簽預(yù)測(cè)問(wèn)題時(shí)，將所有數(shù)據(jù)點(diǎn)視為圖G上的頂點(diǎn)，構(gòu)建數(shù)據(jù)點(diǎn)之間的權(quán)重矩陣W.在無(wú)符號(hào)網(wǎng)絡(luò)中，權(quán)重大小是對(duì)結(jié)點(diǎn)間相似(或不相似度)的度量，無(wú)法同時(shí)表達(dá)相似性與相斥性.在許多的基于無(wú)符號(hào)網(wǎng)絡(luò)的半監(jiān)督學(xué)習(xí)方法中，結(jié)點(diǎn)之間的標(biāo)簽互斥性與缺失邊通常均被處理為0權(quán)重，從而丟失了這種互斥信息.

3.1 基于符號(hào)規(guī)范化割的成對(duì)約束半監(jiān)督學(xué)習(xí)

在無(wú)符號(hào)網(wǎng)絡(luò)中，勿連約束所對(duì)應(yīng)的連接權(quán)重為0，而缺失的連邊也是0權(quán)重.這里，我們用負(fù)邊相連cannotlink點(diǎn)對(duì)，顯式地表達(dá)出了這種互斥關(guān)系，可以區(qū)分以上兩種情形.通過(guò)構(gòu)建符號(hào)網(wǎng)絡(luò)，對(duì)χ的分類(lèi)或聚類(lèi)問(wèn)題均可以轉(zhuǎn)換為符號(hào)網(wǎng)絡(luò)的劃分問(wèn)題來(lái)完成.

(3)

對(duì)上述目標(biāo)的最小化，意味著最大化組內(nèi)的正邊權(quán)重之和且最小化組內(nèi)的負(fù)邊權(quán)重之和.也就是說(shuō)，盡量使得必連的點(diǎn)對(duì)在同一組，勿連的點(diǎn)對(duì)不在同一組.與無(wú)符號(hào)網(wǎng)絡(luò)相比，該目標(biāo)顯式地強(qiáng)化了勿連約束.

3.2 2-way符號(hào)規(guī)范化割的實(shí)驗(yàn)分析

我們從UCI數(shù)據(jù)庫(kù)中選取了數(shù)值型屬性的幾個(gè)樣本集，用于驗(yàn)證2-way符號(hào)規(guī)范化割在半監(jiān)督學(xué)習(xí)上的有效性.表1描述了數(shù)據(jù)集的基本信息.部分?jǐn)?shù)據(jù)集有少量缺失數(shù)據(jù)，我們對(duì)其進(jìn)行了剔除.

表1 UCI數(shù)據(jù)集

Table 1 UCI datasets

數(shù)據(jù)集數(shù)據(jù)個(gè)數(shù)維數(shù)BreastcancerWisconsin(WBC)6999Haberman3063Sonar20860Ionosphere35134Jain3732Blood7485

圖2利用調(diào)整的RI指標(biāo)(ARI)與互信息指標(biāo)(NMI)來(lái)衡量聚類(lèi)精度.這里，ML+Ncut即用M集合強(qiáng)化了必連約束，SNCut同時(shí)使用了M與C集合，從而出現(xiàn)了負(fù)邊.從圖上可以看出，使用M集合的表現(xiàn)略好于NCut本身.當(dāng)引入負(fù)邊后，SNCut的效果獲得了顯著提升.值得一提的是，在實(shí)驗(yàn)中我們觀測(cè)到，在UCI的小數(shù)據(jù)集中，僅使用C集合的SNCut便可獲得與SNCut幾乎一樣的效果.

4 基于符號(hào)規(guī)范化割的半監(jiān)督圖像分割

本節(jié)針對(duì)半監(jiān)督圖像分割問(wèn)題，首先將圖像映射為符號(hào)網(wǎng)絡(luò)，然后利用譜松弛法優(yōu)化SNCut，對(duì)圖像像素進(jìn)行聚類(lèi).對(duì)結(jié)果分析時(shí)，發(fā)現(xiàn)SNCut在目標(biāo)邊界處表現(xiàn)不夠平滑，引入MRF平滑項(xiàng)以提升目標(biāo)邊界貼合度.

如圖3所示，分別用兩條線提示了前景與背景.本文通過(guò)將監(jiān)督信息表達(dá)為成對(duì)約束從而構(gòu)造加權(quán)符號(hào)圖.假定劃線所包含的前景像素點(diǎn)集為F，背景點(diǎn)集為B.在本文中構(gòu)造M與C如圖3所示，F(xiàn)與B上實(shí)線點(diǎn)對(duì)為M，F(xiàn)與B之間虛線點(diǎn)對(duì)為C.

將圖像映射為圖時(shí)，我們并不會(huì)為每?jī)蓚€(gè)像素建立邊，因?yàn)檫^(guò)稠密的圖會(huì)使得計(jì)算復(fù)雜性大幅度增加.此時(shí)，導(dǎo)致邊權(quán)為0的因素，可能是兩點(diǎn)顏色特征相似性低，也可能由于兩點(diǎn)之間的空間距離過(guò)大.在無(wú)監(jiān)督圖像分割中，F(xiàn)與B的點(diǎn)對(duì)之間距離較大，權(quán)重很可能為0.然而，實(shí)際上它們是屬于相斥的類(lèi)別.引入輔助信息后，必連約束指示了顏色等特征的相似性極強(qiáng)，用強(qiáng)化的正邊相連.勿連約束則表達(dá)了相異性，用負(fù)邊連接勿連點(diǎn)對(duì)，從而將其與空間距離過(guò)大區(qū)分開(kāi)來(lái).

圖2 不同種子點(diǎn)數(shù)目下的ARI與NMI

圖3 監(jiān)督信息的成對(duì)約束表示

4.1 基于符號(hào)圖譜的半監(jiān)督圖像分割

我們首先構(gòu)建無(wú)符號(hào)網(wǎng)絡(luò)，然后引入監(jiān)督信息，轉(zhuǎn)化為符號(hào)網(wǎng)絡(luò).以某種方式構(gòu)建非負(fù)權(quán)重矩陣W，滿足Wij∈[0,1].在本文的實(shí)驗(yàn)中，采用了文獻(xiàn)[13]的W生成方式.符號(hào)網(wǎng)絡(luò)的權(quán)重矩陣構(gòu)造如下：

(4)

其中，

⊙表示Hadamard乘積；βant、β為參數(shù)，它們的增大會(huì)引起負(fù)邊.

圖4 不同約束下的分割結(jié)果圖

4.2 利用MRF正則化子改進(jìn)SNCut

考慮到SNCut的分割結(jié)果在目標(biāo)邊界處表現(xiàn)不夠平滑，本文在其上引入了典型的MRF正則化項(xiàng)，以加強(qiáng)其邊界對(duì)齊性.MRF將圖像映射為隨機(jī)場(chǎng)，圖中每個(gè)像素點(diǎn)都與某個(gè)隨機(jī)變量相關(guān).而MRF中的每個(gè)隨機(jī)變量只與其鄰域的隨機(jī)變量有關(guān).MRF勢(shì)函數(shù)作為正則化子已廣泛應(yīng)用于計(jì)算機(jī)視覺(jué)領(lǐng)域.本文使用可保證邊界對(duì)齊的二階Potts模型：

(5)

其中，二元因子F和N包含了相鄰結(jié)點(diǎn)所組成的邊f(xié)={pq}.[?]為艾弗森括號(hào)，Bpq是p與q的標(biāo)簽不連續(xù)時(shí)的罰值.

定義新的能量函數(shù)：

(6)

其中，常數(shù)γ為MRF項(xiàng)的相對(duì)權(quán)重.我們將此模型稱(chēng)為：SNCut & MRF.該目標(biāo)函數(shù)不能使用譜方法求解，本文采用界優(yōu)化思想[14]來(lái)構(gòu)造式(6)的一個(gè)更易求解的輔助函數(shù)，在迭代過(guò)程中，利用圖割算法求解該輔助函數(shù)，以逼近式(6)的最優(yōu)解.式(6)的輔助函數(shù)為：

At(x)=

(7)

5 參數(shù)設(shè)置與圖像分割實(shí)驗(yàn)分析

在MSRA1K數(shù)據(jù)集上實(shí)驗(yàn)，共1000張圖片，每張圖片均有人工標(biāo)記真值圖.為定量分析實(shí)驗(yàn)結(jié)果，采用四個(gè)評(píng)估指標(biāo)進(jìn)行衡量，分別為Error rate(ER)、F1-measure(F1)、Jaccard系數(shù)(JC)、修正的Hausdorff距離(MHD).若ER、MHD越小，F(xiàn)1、JC越大，則表示圖像分割效果越好.

5.1 基于SNCut的半監(jiān)督圖像分割

在圖表中，ML、CL分別是指必連約束和勿連約束，對(duì)權(quán)重矩陣的構(gòu)造采用了式(4)，其中勿連約束會(huì)產(chǎn)生負(fù)邊.式(4)中βant與β的不同取值對(duì)應(yīng)不同的相似矩陣，對(duì)最終分割結(jié)果有較大影響.如表2所示，對(duì)βant與β統(tǒng)一取1、10、102、103、104、105、106，比較SNCut在各取值下的評(píng)價(jià)指標(biāo)值.從對(duì)比結(jié)果可以看出，βant與β取值為100時(shí)，各項(xiàng)指標(biāo)均值較優(yōu)，故取βant=β=100.

為驗(yàn)證添加負(fù)邊所帶來(lái)的附加價(jià)值，圖4和表3展示了4種方法的分割效果.ML+Ncut強(qiáng)化了同組約束，分割效果比Ncut強(qiáng).SNCut和CL+Ncut都引入負(fù)邊表征像素間相異性.表3前4行列出了基于以上四種算法的評(píng)價(jià)指標(biāo)值.量化結(jié)果顯示，SNCut表現(xiàn)最優(yōu)，CL+Ncut次之，與未引入負(fù)邊的ML+Ncut和Ncut相比，SNCut更接近真值圖.相比添加正邊，添加負(fù)邊能帶來(lái)更多的提升.SNCut在ML+NCut基礎(chǔ)上，我們與ICCV2015的SSNCut進(jìn)行了比較，該方法也可以同時(shí)處理必連與勿連約束，是一個(gè)較為新穎的譜聚類(lèi)方法.分割圖片與量化結(jié)果分別展示于圖5與表3.總體上來(lái)說(shuō)，SSNCut具有優(yōu)勢(shì)，尤其是在評(píng)價(jià)指標(biāo)上表現(xiàn)較好.但是，本文所利用的SNCut則可以輕易的與其它正則化項(xiàng)相結(jié)合，而SSNCut的復(fù)雜譜分析過(guò)程則難以擴(kuò)展.

表2 SNCut在βant與β各取值下的圖像分割結(jié)果評(píng)價(jià)

Table 2 Image segmentation results evaluation of SNCut under differentβantandβ

ERmeanvarianceF1meanvarianceJCmeanvarianceMHDmeanvariance10.36810.06630.54710.07640.42700.09248.176126.3232100.34560.07780.58200.08540.47660.10577.651030.01201020.30840.06080.60810.07130.49370.09017.141524.09191030.37260.06500.55520.07020.43710.08528.450626.08971040.36360.05560.55320.05930.42640.07078.355321.80681050.36610.05760.54690.06280.42240.07358.392122.06841060.43290.05390.49270.04940.36030.05329.574719.3350

5.2 基于SNCut&MRF的半監(jiān)督圖像分割

表3 分割結(jié)果的評(píng)價(jià)指標(biāo)值

Table 3 Quality measurements of image segmentation results

ERmeanvarianceF1meanvarianceJCmeanvarianceMHDmeanvarianceNcut0.36770.06680.54130.07720.42860.09368.173226.5549ML+Ncut0.34780.06550.55940.07580.44050.09297.902226.0625CL+Ncut0.31290.06290.58510.07320.48510.09137.210524.9044SNCut0.30840.06080.60810.07130.49370.09017.141524.0919SSNCut0.34110.14340.66110.11540.58790.13987.07548.2137Kernelcut0.03270.01650.91140.02070.85560.03141.59834.5988SNCut&MRF0.03080.00760.92980.01300.88340.02221.44472.8986

圖5展示了幾種方法的分割結(jié)果圖.SSNCut與SNCut的分割效果相當(dāng)，在前景邊界復(fù)雜的圖像上表現(xiàn)較差，不能很好地識(shí)別邊界位置.但是，SNCut比SSNCut的優(yōu)化過(guò)程更為簡(jiǎn)單.在加入MRF項(xiàng)之后，SNCut & MRF能夠顯著提升邊界對(duì)齊性.在分割結(jié)果圖上，SNCut & MRF與Kernel cut效果相當(dāng).表3的后幾行則可以量化比較三種算法的優(yōu)劣.由于Kernel cut沒(méi)有很好的利用監(jiān)督信息，在評(píng)價(jià)指標(biāo)上，劣于SNCut & MRF.表4中，我們列出了圖5的幾張圖片所需的計(jì)算時(shí)間，以秒為單位.括號(hào)(without)是指不包含超像素生成的時(shí)間.由于SSNCut與SNCut均以超像素為結(jié)點(diǎn)構(gòu)建無(wú)符號(hào)(符號(hào))網(wǎng)絡(luò)，即便調(diào)用了特征值函數(shù)，其所需時(shí)間仍然較少.其中，SNCut所需的時(shí)間則更少.SNCut & MRF與Kernel cut均比前兩種譜方法的時(shí)間長(zhǎng)，因?yàn)樗鼈兊厥褂昧俗畲罅?最小割算法.SNCut & MRF以負(fù)邊表達(dá)半監(jiān)督信息，在程序中多執(zhí)行了約束信息的處理代碼，因而比Kernel cut的執(zhí)行時(shí)間稍多.

圖5 分割結(jié)果比對(duì)

表4 典型圖片的計(jì)算時(shí)間

Table 4 Runtime of different algorithms

圖片SSNCut(without)SNCut(without)KernelcutSNCut&MRF(a)2.72(1.56)1.56(0.15)8.5710.26(b)2.76(1.44)1.32(0.13)9.5911.01(c)3.44(1.99)1.51(0.16)7.129.24(d)3.29(1.70)1.53(0.14)8.0610.94(e)2.49(1.32)1.32(0.13)9.4411.68

6 結(jié)束語(yǔ)

本文基于符號(hào)網(wǎng)絡(luò)上的規(guī)范化割(SNCut)，提出了成對(duì)約束的半監(jiān)督學(xué)習(xí)算法.將SNCut應(yīng)用于UCI數(shù)據(jù)集與圖像分割，驗(yàn)證SNCut用于半監(jiān)督學(xué)習(xí)問(wèn)題的有效性.SNCut引入少量負(fù)邊，聚類(lèi)性能有明顯提升，但在分割問(wèn)題上目標(biāo)邊界處表現(xiàn)不理想.為了進(jìn)一步提升分割精度，將SNCut與MRF正則項(xiàng)結(jié)合，并利用圖割法迭代優(yōu)化.下一步將本文方法應(yīng)用于分組數(shù)K>2的其它數(shù)據(jù)集以及多相分割，以進(jìn)一步驗(yàn)證其有效性.同時(shí)，引入一些預(yù)測(cè)算法，獲得更多的負(fù)邊，進(jìn)一步提升負(fù)邊的價(jià)值.