基于符號規范化割的半監督學習與圖像分割

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

(湖南師范大學 信息科學與工程學院，長沙 410081)

1 引 言

半監督學習(Semi-supervised learning，簡稱SSL)是機器學習的一個重要分支[1].SSL研究如何同時利用無標簽的樣例與部分監督信息改進學習性能.SSL的研究具有重要的實用價值，因為在實際應用中減少標記樣本的使用能夠大幅縮減人力、時間和資源的開銷，從而降低生產成本[2].在過去的十幾年時間里，涌現了許多基于圖的SSL方法.基于圖的SSL以監督信息為輔，用圖來表達數據，通過對圖的分析來完成學習任務.鑒于圖的強大表達力以及關于圖的成熟數學理論與龐大算法體系，這類SSL方法取得了大量成果[3].

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

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

上述SSL方法需根據樣例之間的關系預先構造圖.這類方法通常采用無符號圖(或稱網絡)表征數據，它用非負權重衡量節點之間的相似性，難以區分無關、消極/對立等關系.實際上，有許多真實復雜網絡系統中本就包含著對立/消極關系，比如萬維網、信任網絡等[10].人們越來越意識到，邊的符號屬性在許多挖掘任務中體現了附加價值[11].對于非圖型數據，在構圖時引入邊的符號屬性，具有更強的表達力.缺失的邊具有0權重，可能是由于兩個節點的距離太遠或者它們的特征具有極低的相似性，也有可能是它們本就相異、甚至相斥的.然而，無符號網絡并不能區別對待這些情形，符號網絡則可借助負邊將所隱含的互斥關系顯式地表達出來.

本文在符號網絡的規范化割(Signed Normalized Cut，SNCut)基礎上，提出了基于成對約束的半監督學習方法，并在典型數據集上驗證了負邊的附加價值.進一步的，將SNCut應用于半監督圖像分割，展示了負邊對分割效果的提升效果.為了提升邊界對齊性，引入了馬爾科夫隨機場(Markov Random Field，MRF)正則化項，構建SNCut&MRF目標函數，并采用界優化思想和圖割算法進行求解.實驗結果表明，SNCut&MRF相比一些經典分割方法有更好的分割性能，在邊界處表現良好.

本文的組織結構如下：第2節介紹了無符號網絡與符號網絡的規范化割；第3節在基于符號網絡的規范化割基礎上，提出了一種半監督學習途徑，并在UCI數據集上進行了測試，驗證了負邊的附加價值；第4節將其應用于圖像分割，進一步展示了負邊的效應，并針對邊界問題引入了MRF正則化項，提出了改進模型和相應的優化算法；第5節對本文所提出的方法進行了詳細的實驗分析.

2 規范化割

本節首先介紹了(無向的)無符號網絡與符號網絡上的規范化割，然后提出了基于符號網絡的半監督聚類準則.與無符號圖不同，我們以負邊表達了勿連約束.這里，我們僅考慮2-way的劃分問題.

2.1 無符號圖的規范化割

(1)

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

2.2 符號規范化割

圖1 符號網絡示意

我們將符號網絡上的規范化割稱為符號規范化割(Signed Normalized Cut，SNCut).根據文獻[12,13]，SNCut定義為：

(2)

3 基于符號規范化割的半監督學習

NCut應用于標簽預測問題時，將所有數據點視為圖G上的頂點，構建數據點之間的權重矩陣W.在無符號網絡中，權重大小是對結點間相似(或不相似度)的度量，無法同時表達相似性與相斥性.在許多的基于無符號網絡的半監督學習方法中，結點之間的標簽互斥性與缺失邊通常均被處理為0權重，從而丟失了這種互斥信息.

3.1 基于符號規范化割的成對約束半監督學習

在無符號網絡中，勿連約束所對應的連接權重為0，而缺失的連邊也是0權重.這里，我們用負邊相連cannotlink點對，顯式地表達出了這種互斥關系，可以區分以上兩種情形.通過構建符號網絡，對χ的分類或聚類問題均可以轉換為符號網絡的劃分問題來完成.

(3)

對上述目標的最小化，意味著最大化組內的正邊權重之和且最小化組內的負邊權重之和.也就是說，盡量使得必連的點對在同一組，勿連的點對不在同一組.與無符號網絡相比，該目標顯式地強化了勿連約束.

3.2 2-way符號規范化割的實驗分析

我們從UCI數據庫中選取了數值型屬性的幾個樣本集，用于驗證2-way符號規范化割在半監督學習上的有效性.表1描述了數據集的基本信息.部分數據集有少量缺失數據，我們對其進行了剔除.

表1 UCI數據集

Table 1 UCI datasets

數據集數據個數維數BreastcancerWisconsin(WBC)6999Haberman3063Sonar20860Ionosphere35134Jain3732Blood7485

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

4 基于符號規范化割的半監督圖像分割

本節針對半監督圖像分割問題，首先將圖像映射為符號網絡，然后利用譜松弛法優化SNCut，對圖像像素進行聚類.對結果分析時，發現SNCut在目標邊界處表現不夠平滑，引入MRF平滑項以提升目標邊界貼合度.

如圖3所示，分別用兩條線提示了前景與背景.本文通過將監督信息表達為成對約束從而構造加權符號圖.假定劃線所包含的前景像素點集為F，背景點集為B.在本文中構造M與C如圖3所示，F與B上實線點對為M，F與B之間虛線點對為C.

將圖像映射為圖時，我們并不會為每兩個像素建立邊，因為過稠密的圖會使得計算復雜性大幅度增加.此時，導致邊權為0的因素，可能是兩點顏色特征相似性低，也可能由于兩點之間的空間距離過大.在無監督圖像分割中，F與B的點對之間距離較大，權重很可能為0.然而，實際上它們是屬于相斥的類別.引入輔助信息后，必連約束指示了顏色等特征的相似性極強，用強化的正邊相連.勿連約束則表達了相異性，用負邊連接勿連點對，從而將其與空間距離過大區分開來.

圖2 不同種子點數目下的ARI與NMI

圖3 監督信息的成對約束表示

4.1 基于符號圖譜的半監督圖像分割

我們首先構建無符號網絡，然后引入監督信息，轉化為符號網絡.以某種方式構建非負權重矩陣W，滿足Wij∈[0,1].在本文的實驗中，采用了文獻[13]的W生成方式.符號網絡的權重矩陣構造如下：

(4)

其中，

⊙表示Hadamard乘積；βant、β為參數，它們的增大會引起負邊.

圖4 不同約束下的分割結果圖

4.2 利用MRF正則化子改進SNCut

考慮到SNCut的分割結果在目標邊界處表現不夠平滑，本文在其上引入了典型的MRF正則化項，以加強其邊界對齊性.MRF將圖像映射為隨機場，圖中每個像素點都與某個隨機變量相關.而MRF中的每個隨機變量只與其鄰域的隨機變量有關.MRF勢函數作為正則化子已廣泛應用于計算機視覺領域.本文使用可保證邊界對齊的二階Potts模型：

(5)

其中，二元因子F和N包含了相鄰結點所組成的邊f={pq}.[?]為艾弗森括號，Bpq是p與q的標簽不連續時的罰值.

定義新的能量函數：

(6)

其中，常數γ為MRF項的相對權重.我們將此模型稱為：SNCut & MRF.該目標函數不能使用譜方法求解，本文采用界優化思想[14]來構造式(6)的一個更易求解的輔助函數，在迭代過程中，利用圖割算法求解該輔助函數，以逼近式(6)的最優解.式(6)的輔助函數為：

At(x)=

(7)

5 參數設置與圖像分割實驗分析

在MSRA1K數據集上實驗，共1000張圖片，每張圖片均有人工標記真值圖.為定量分析實驗結果，采用四個評估指標進行衡量，分別為Error rate(ER)、F1-measure(F1)、Jaccard系數(JC)、修正的Hausdorff距離(MHD).若ER、MHD越小，F1、JC越大，則表示圖像分割效果越好.

5.1 基于SNCut的半監督圖像分割

在圖表中，ML、CL分別是指必連約束和勿連約束，對權重矩陣的構造采用了式(4)，其中勿連約束會產生負邊.式(4)中βant與β的不同取值對應不同的相似矩陣，對最終分割結果有較大影響.如表2所示，對βant與β統一取1、10、102、103、104、105、106，比較SNCut在各取值下的評價指標值.從對比結果可以看出，βant與β取值為100時，各項指標均值較優，故取βant=β=100.

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

表2 SNCut在βant與β各取值下的圖像分割結果評價

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的半監督圖像分割

表3 分割結果的評價指標值

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展示了幾種方法的分割結果圖.SSNCut與SNCut的分割效果相當，在前景邊界復雜的圖像上表現較差，不能很好地識別邊界位置.但是，SNCut比SSNCut的優化過程更為簡單.在加入MRF項之后，SNCut & MRF能夠顯著提升邊界對齊性.在分割結果圖上，SNCut & MRF與Kernel cut效果相當.表3的后幾行則可以量化比較三種算法的優劣.由于Kernel cut沒有很好的利用監督信息，在評價指標上，劣于SNCut & MRF.表4中，我們列出了圖5的幾張圖片所需的計算時間，以秒為單位.括號(without)是指不包含超像素生成的時間.由于SSNCut與SNCut均以超像素為結點構建無符號(符號)網絡，即便調用了特征值函數，其所需時間仍然較少.其中，SNCut所需的時間則更少.SNCut & MRF與Kernel cut均比前兩種譜方法的時間長，因為它們迭代地使用了最大流/最小割算法.SNCut & MRF以負邊表達半監督信息，在程序中多執行了約束信息的處理代碼，因而比Kernel cut的執行時間稍多.

圖5 分割結果比對

表4 典型圖片的計算時間

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 結束語

本文基于符號網絡上的規范化割(SNCut)，提出了成對約束的半監督學習算法.將SNCut應用于UCI數據集與圖像分割，驗證SNCut用于半監督學習問題的有效性.SNCut引入少量負邊，聚類性能有明顯提升，但在分割問題上目標邊界處表現不理想.為了進一步提升分割精度，將SNCut與MRF正則項結合，并利用圖割法迭代優化.下一步將本文方法應用于分組數K>2的其它數據集以及多相分割，以進一步驗證其有效性.同時，引入一些預測算法，獲得更多的負邊，進一步提升負邊的價值.