瞿紹軍，李喬良，陳 明，譚 煌

1(湖南師范大學(xué) 信息科學(xué)與工程學(xué)院，長沙 410081)2(湖南師范大學(xué) 數(shù)學(xué)與統(tǒng)計學(xué)院，長沙 410081)

1 引 言

近年，交互式圖像分割在計算機(jī)視覺領(lǐng)域得到了人們的廣泛關(guān)注，圖割是最流行的交互式圖像分割方法.Boykov和Jolly[1]第一次在離散域中構(gòu)建簡單的生成MRF模型，用于處理二值圖像分割任務(wù)，這是交互式分割的基本模型.指定一些目標(biāo)和背景像素作為用戶先驗(yàn)約束，可以通過圖割方法高效地求解全局最優(yōu)解.該方法基本原理是將能量最小化問題轉(zhuǎn)化為基于圖的最大流問題，主要優(yōu)勢在于全局最優(yōu)、實(shí)際效率高，缺點(diǎn)是容易產(chǎn)生孤立割集.為了避免最小割在圖中分割出孤立節(jié)點(diǎn)集合.Shi提出利用歸一化割(Ncut)[2]評價不同組之間的不相似性，以及組內(nèi)的總體相似性.Ncut方法可以穩(wěn)健地生成平衡簇，并且優(yōu)于其他譜圖分割方法.Tao等人[3]開發(fā)了一種基于均值漂移和Ncut方法的彩色圖像分割方法.Yu和Shi[4]擴(kuò)展Ncut來處理硬性必連約束(must-link)，Eriksson等人[5]提出利用Ncut來處理硬性的必連約束和勿連約束(cannot-link)，Subhransu Maji[6]提出了一種修改的“歸一化割”，將先驗(yàn)引入圖像分割，可認(rèn)為是一種修改的Ncut解決方法，以軟方式來滿足必連約束.Chew[7]重新形式化Ncut(Semi-Supervised Normalized Cuts：SSNCuts)，以便以軟約束方式處理必連約束和勿連約束，使用戶能夠調(diào)整約束滿足的程度.

超像素圖像分割是Malik和Ren在2003年提出和發(fā)展起來的一種圖像分割技術(shù)[8]，是指具有相似顏色、紋理、亮度等特征的相鄰像素構(gòu)成的有一定視覺意義的不規(guī)則像素塊.它利用像素之間特征的相似性將像素分組，用少量的超像素代替大量的像素來表示圖像特征，很大程度上降低了圖像后處理的復(fù)雜度.常用的超像素圖像分割方法有：Turbopixel[9]、均值漂移(Mean shift)[10]、SLIC[11]等.甘玲等提出一種基于SLIC超像素初始分割和區(qū)域合并的交互式圖像分割方法[12]，程仙國等提出融合SLIC與改進(jìn)鄰近傳播聚類的彩色圖像分割算法[13]，都獲得了較好的分割結(jié)果.

最小s-t割問題是一個經(jīng)典的組合優(yōu)化問題，它是許多視覺和成像算法中的一個重要構(gòu)建模塊.Hochbaum在文獻(xiàn)[14-17]中介紹了偽流算法并將偽流算法應(yīng)用于求解最小s-t割問題，與push-relabel、增光路徑算法和部分增廣路徑-重標(biāo)記算法在執(zhí)行時間與內(nèi)存利用率方面進(jìn)行了理論對比和實(shí)驗(yàn)驗(yàn)證.實(shí)驗(yàn)結(jié)果表明，偽流算法比這三種算法更高效并且使用更少的內(nèi)存.這對于許多需要解最小s-t割問題的實(shí)時計算機(jī)視覺問題，偽流算法是一個很好的選擇.

本文受Chew的半監(jiān)督歸一化割[7]啟發(fā)，提出將超像素和偽流算法融合進(jìn)行圖像分割.在所提出的方法中，交互信息由用戶以粗略地指示少部分目標(biāo)和背景位置，然后使用SLIC[11]對圖像進(jìn)行超像素分割，再以每個超像素作為圖中的一個頂點(diǎn)進(jìn)行構(gòu)圖，采用與論文[7]中一致的gPb(globalized probability of boundary)[18]計算超像素之間的相似性，最后用偽流算法進(jìn)行超像素分割，并將超像素分割結(jié)果轉(zhuǎn)換到原始像素和圖像得到最終分割.由于在分割中計算gPb非常費(fèi)時，嚴(yán)重影響到分割效率，本文進(jìn)一步用均值漂移進(jìn)行超像素分割和Bhattacharyya系數(shù)[19]計算超像素之間的相似性，實(shí)驗(yàn)結(jié)果顯示，本文提出的方法既提高了分割的準(zhǔn)確性，又提升了分割的效率.

2 半監(jiān)督歸一化分割方法

(1)

圖的最優(yōu)的分割是最小化(1)的割值.在圖的劃分過程中，先驗(yàn)知識告訴我們應(yīng)該將某些頂點(diǎn)劃分在一起，某些頂點(diǎn)不應(yīng)該劃分在一起，分別稱它們?yōu)楸剡B約束和勿連約束.

必連約束：假設(shè)知道集合C={(vil，vjl)|l=1，…，m}表示兩個頂點(diǎn)應(yīng)該分組在同一劃分中.一個修改的違反必連約束的懲罰的割的成本形式：

(2)

(3)

(4)

通過以下方式定義半監(jiān)督歸一化割(SSNCuts)成本：

(5)

3 偽流算法

近年來，Hochbaum在基于圖的分割方面做出了突破性的工作，文獻(xiàn)[14-17]中介紹了偽流算法并將偽流算法應(yīng)用于求解最小s-t割問題.她將該算法與push-relabel、增廣路徑算法和部分增廣路徑-重標(biāo)記算法在執(zhí)行時間與內(nèi)存利用率方面進(jìn)行了理論對比和實(shí)驗(yàn)驗(yàn)證.實(shí)驗(yàn)結(jié)果表明，偽流算法比這三種算法更高效并且使用更少的內(nèi)存.Hochbaum對歸一化割、等周常數(shù)、Cheeger常數(shù)、conductance等問題之間的關(guān)系進(jìn)行了系統(tǒng)的分析，證明了在離散變量上最小化Rayleigh比問題是多項(xiàng)式時間可解的.對這些問題可以表示成不同的正交約束下的離散變量上的Rayleigh比問題[20].傳統(tǒng)上，這些問題利用譜方法啟發(fā)式求近似解.該文還提出了一個新的約束割集問題——次歸一化割集問題，這一問題是多項(xiàng)式時間可解的.因此，Hochbaum偽流算法算法可以給出比譜方法更好的對歸一化參數(shù)的估計.將上述結(jié)果應(yīng)用到歸一化分割，可以得到更好的分割效果.

最大流問題定義在有向s，t-圖Gst=(Vs，t，Ast)，標(biāo)準(zhǔn)形式的最大流問題用變量fij表示弧(i ，j)上流的總量.

maxfts
滿足 ∑ifki-∑jfjk=0，?k∈Vs，t
0≤fij≤cij，?(i，j)∈Ast

(6)

公式(6)中目標(biāo)函數(shù)值，也是離開源(或到達(dá)匯)的總流，表示為|f|，第一個約束(等式)叫流平衡約束.第二個約束(不等式)叫容量約束.一個“預(yù)流”可違反流平衡約束，在一個方向允許非負(fù)過剩(流出的小于流入的)，∑ifki-∑jfjk≤0.而“偽流”可能在兩個方向違反流平衡約束.容量約束都是滿足的.

使用動態(tài)樹數(shù)據(jù)結(jié)構(gòu)的偽流算法如[14-17]具有O(mnlogn)的時間復(fù)雜性，之后被改進(jìn)到O(mnlog(n2/m)).

4 基于超像素和偽流算法的圖像分割

首先由用戶交互引入目標(biāo)和背景的先驗(yàn)信息；其次分別使用SLIC和均值漂移對圖像進(jìn)行超像素分割(產(chǎn)生的超像素個數(shù)為n)；再以每個超像素作為一個頂點(diǎn)建立鄰接矩陣(鄰接矩陣大小為n*n)，分別用gPb[18]和Bhattacharyya系數(shù)[19]計算超像素之間的相似性；最后利用偽流算法進(jìn)行超像素分割，并將超像素分割結(jié)果轉(zhuǎn)換到原始像素和圖像得到最終分割.其過程如圖1所示.

圖1 交互式圖像分割過程Fig.1 Interactive image segmentation process

4.1 目標(biāo)和背景標(biāo)記

在交互式圖像分割中，用戶需要指定目標(biāo)和背景像素或區(qū)域，用戶可以通過繪制線條、曲線和涂鴉輸入交互信息.圖1(a)展示了通過使用簡單的曲線標(biāo)記目標(biāo)和背景像素，使用白色標(biāo)記來表示目標(biāo)，用淺黑色標(biāo)記來表示背景.

4.2 生成超像素

在提出的方法中，需要先將圖像分割成許多區(qū)域(超像素)以提供初始分割.首先選擇與 SSNcuts一樣的SLIC進(jìn)行初始分割，之后進(jìn)行改進(jìn)和實(shí)驗(yàn)比較，使用均值漂移方法進(jìn)行初始分割.圖1(b)顯示了SLIC初始分割的一個例子.SLIC中參數(shù)選擇和SSNcuts論文中保持一致，取regionSize=10，regularizer=10000.均值漂移中的參數(shù)，根據(jù)論文作者建議，取Spatial=7，Color=6.5，MinimumRegion=20，對絕大部分圖像都能得到比較好的預(yù)分割結(jié)果.

超像素生成后，根據(jù)目標(biāo)標(biāo)記，找到具有目標(biāo)種子像素的超像素區(qū)域，并將這些頂點(diǎn)對應(yīng)的超像素區(qū)域作為新的目標(biāo)種子點(diǎn)集合(ObjectSet，ObjectSet={i|超像素i中至少一個像素∈目標(biāo)種子點(diǎn)}).根據(jù)背景標(biāo)記，找到具有背景種子像素的超像素區(qū)域，并將這些頂點(diǎn)對應(yīng)的超像素區(qū)域作為新的背景種子點(diǎn)集合(BackgroundSet，BackgroundSet={i|超像素i中至少一個像素∈背景種子點(diǎn)}).

4.3 計算超像素之間相似性

以每個超像素作為一個頂點(diǎn)來構(gòu)造圖，用圖的邊權(quán)來表示超像素之間的相似性關(guān)系.分別用gPb和Bhattacharyya系數(shù)兩種方法計算超像素之間的相似性.

1)gPb定義圖的邊權(quán).在每個像素計算邊界的全局化概率(gPb)，找出8個方位角上的最大gPb，并定義超像素i和j之間的權(quán)重為[7，18]：

(7)

如果‖pi，j‖≤r，則Wi，j=0，否則，Pi，j是連接超像素i和j的質(zhì)心的線段，ρ是常數(shù). 將r設(shè)置為圖像寬度和高度的最大值的0.1倍.ρ設(shè)置與論文[18]一致，取ρ=0.1.

2)Bhattacharyya系數(shù)定義圖的邊權(quán).由于計算gPb對硬件配置要求非常高，并且耗時，嚴(yán)重影響分割效率，在改進(jìn)實(shí)驗(yàn)中使用RGB顏色空間來計算顏色直方圖，將每個顏色通道統(tǒng)一量化為16個等級，然后在16×16×16 = 4096個bins的特征空間中計算每個超像素的直方圖.Hi表示超像素i的歸一化直方圖.然后定義兩個超像素i和j之間的相似性度量W(i，j)，以提供各超像素之間的比較，這里選擇使用Bhattacharyya系數(shù)[19]來衡量i和j之間的相似度：

(8)

如果超像素的個數(shù)為n，則權(quán)矩陣W的大小為n×n.

4.4 構(gòu) 圖

給定圖G=(V，A)，V是頂點(diǎn)的集合，包括產(chǎn)生地超像素共n個節(jié)點(diǎn)、新增終端節(jié)點(diǎn)S與T，A是邊的集合，包括兩類邊：

第1類邊是超像素頂點(diǎn)之間的關(guān)系，即任意兩個超像素塊之間的相似性.對任意兩個超像素i和j，如果Wi，j>0，則超像素i和j之間連接一條邊Ai，j，其權(quán)值設(shè)為Wi，j*1000.因4.3節(jié)中計算出的權(quán)是歸一化的權(quán)，其值的大小在0～1之間，而偽流計算的時候需要整數(shù)權(quán)，通過實(shí)驗(yàn)分析，當(dāng)權(quán)值擴(kuò)大到100-1000倍，分割結(jié)果的趨于穩(wěn)定，因此，實(shí)驗(yàn)中對W擴(kuò)大1000倍，即W=1000*W.

第2類邊是終端節(jié)點(diǎn)S到標(biāo)記為目標(biāo)種子點(diǎn)的邊和終端節(jié)點(diǎn)T到標(biāo)記為背景種子點(diǎn)的邊.對任何目標(biāo)種子點(diǎn)集(object)，設(shè)置As，object=INFINITE_FLOW，對任何背景種子點(diǎn)集(background)設(shè)置AT，background=INFINITE_FLOW.INFINITE_FLOW是一個很大的數(shù)，如108.權(quán)值越大，表示分割的時候一條邊關(guān)聯(lián)的兩個頂點(diǎn)越不應(yīng)該被分開.其邊權(quán)設(shè)置方法如表1所示.

表1 邊權(quán)計算方法Table 1 Calculation of edge weight

圖G建好后，利用偽流算法計算最優(yōu)解，獲得最優(yōu)的分割.最后，將超像素分割結(jié)果轉(zhuǎn)換到原始像素和圖像得到最終分割，結(jié)果如圖1(c)所示，其二值掩碼分割結(jié)果如圖1(d)所示.

5 實(shí)驗(yàn)對比及結(jié)果

為了定性和定量的評估采用偽流算法之后對分割質(zhì)量的改善，在標(biāo)準(zhǔn)數(shù)據(jù)集上進(jìn)行對比測試，圖片選自Berkeley分割數(shù)據(jù)庫[21]和MSRA顯著對象數(shù)據(jù)集[22]共250張圖片，包括背景較單一，紋理較少，背景比較復(fù)雜，紋理較多，前背景顏色非常相似等圖片.MSRA顯著對象數(shù)據(jù)集本身提供了二值分割真值，Berkeley分割數(shù)據(jù)庫中圖片的二值分割真值來自Kevin[23]提供的96張圖片的真值.

5.1 與SSNCuts對比實(shí)驗(yàn)

通過幾組不同圖片對SSNCuts進(jìn)行分割實(shí)驗(yàn)，其中約束條件選取必連約束+勿連約束組合情況，從中選取最好的分割結(jié)果，如圖2所示.

圖2 SSNCuts分割結(jié)果Fig.2 Segmentation results of SSNCuts

在圖2(第1、第3行圖片)，人工不斷修改標(biāo)記，從分割結(jié)果可以發(fā)現(xiàn)，SSNCuts方法對標(biāo)記的選取非常敏感，標(biāo)記相差不大的時候，但對分割結(jié)果影響非常大；當(dāng)圖片中目標(biāo)和背景顏色非常相似，紋理復(fù)雜分割效果不好；從分割過程來看，標(biāo)記非常費(fèi)時和困難，標(biāo)記種子點(diǎn)的時候，無法預(yù)測分割的結(jié)果，不能保證標(biāo)記為目標(biāo)區(qū)域的像素分割為目標(biāo)，標(biāo)記為背景的像素分割為背景.當(dāng)圖片背景較為單一時(圖2中第5行圖片)，圖片中目標(biāo)較小的時候(圖2中第7行圖片)，圖片中存在多個相似的目標(biāo)(圖2中第9行第1列)，要得到較好的分割效果也很困難.在圖2中第9行第2列，SSNCuts將圖片邊界的區(qū)域誤分成目標(biāo)或背景.在圖2中第9行第3列，花朵左邊中間有小部分背景，SSNCuts將其誤分為目標(biāo)，在圖2中第9行第4列，在誤分為目標(biāo)的背景上增加背景標(biāo)記，分割結(jié)果更差了.

本文提出的方法一是SLIC、gPb和偽流算法的融合(簡稱SGH)；二是Mean shift、Bhattacharyya和偽流算法的融合(簡稱MBH)，對圖2中圖片分割結(jié)果如圖3所示，從實(shí)驗(yàn)結(jié)果來看，整體優(yōu)于SSNcuts.

5.2 目標(biāo)精確性指標(biāo)評價

目標(biāo)精確性指標(biāo)又稱Jaccard 相似性系數(shù)[24].計算公式如下：

(9)

其中S是真值分割，S’是算法的分割結(jié)果.通過Jaccard相似系數(shù)來量化分割的準(zhǔn)確性，提出的方法和SSNcut比較結(jié)果如圖4所示.

圖3 本文提出方法對圖2中圖片分割結(jié)果(a)和(d)為原始圖片(b)和(e)為SGH分割結(jié)果 (c)和(f)為MBH分割結(jié)果Fig.3 Results of our method in Fig.2

從實(shí)驗(yàn)結(jié)果可以看出，對絕大部分圖片，當(dāng)超像素分割和計算超像素之間的相似性與SSNcuts一致時，當(dāng)超像分割使用均值漂移，計算超像素之間的相似性使用Bhattacharyya系數(shù)時，提出方法的分割準(zhǔn)確性都高于SSNcuts方法.在分割效率方面，由于計算gPb對硬件配置要求非常高，并且耗時，對分辨率為400*300左右大小圖像，在Intel Xeon CPU E5-2680 v2 2.80GHz、32GB內(nèi)存的機(jī)器上測試，計算gPb需要60秒左右的時間，嚴(yán)重影響分割效率.而采用Bhattacharyya系數(shù)定義圖的邊權(quán)，在普通計算機(jī)上分割時間一般都在2秒內(nèi)完成，大大提高了分割的效率.因此，基于偽流和超像素的分割方法整體上優(yōu)于SSNcut.

圖4 三種方法的Jaccard相似性系數(shù)比較Fig.4 Jaccard similarity coefficient comparison results of the three methods

提出的方法與SSNCuts在圖片集上更多分割結(jié)果比較如圖5所示，整體上來看，提出的方法優(yōu)于SSNCuts.

提出的方法與SSNcut的主要區(qū)別：

1)SSNcut中采用軟形式的必連約束和勿連約束，提出的方法采用硬性必連約束和勿連約束，保證了標(biāo)記為目標(biāo)區(qū)域的像素分割為目標(biāo)，標(biāo)記為背景的像素分割為背景.

圖5 提出方法與SSNcuts分割結(jié)果比較(a)原始圖像，(b-d)分割結(jié)果.(b)MBH，(c)SGH，(d)SSNcutsFig.5 Comparison of our method with SSNcuts

2)構(gòu)圖和優(yōu)化方式不同，SSNcut使用譜方法求解，提出的方法使用偽流優(yōu)化求解.

3)采用Bhattacharyya系數(shù)定義圖的邊權(quán)比gPb具有更高的的效率.

5.3 與多種主流算法比較結(jié)果

提出的方法進(jìn)一步與OneCut[25]，Random Walker (RW)[26]，Normalized Random Walker(NRW)[27]，Normalized Lazy Random Walker (NLRW)[27]，Pseudo-Bound Optimization (PBO)[28]五種方法進(jìn)行了比較，評價指標(biāo)采用Precision(查準(zhǔn)率)，Recall(召回率)，F(xiàn)-Measure和ME(平均錯誤率).F-Measure定義為查準(zhǔn)率和召回率的調(diào)和平均值：

(10)

其中，β是用來確定查準(zhǔn)率對于召回率的重要性，一般設(shè)置取β2=0.3使得查準(zhǔn)率略高于召回率.

給定兩個有限點(diǎn)集S和S′，ME定義為：

(11)

p1表示S和S′對應(yīng)位置像素標(biāo)簽是背景的數(shù)量.p4表示S和S′對應(yīng)位置像素標(biāo)簽是前景的數(shù)量.r和c分別表示圖像的寬度和高度.實(shí)驗(yàn)中為了顯示的方便取ME=1-ME.

圖6顯示了平均查準(zhǔn)率、平均召回率、平均F-Measure和平均錯誤率.

1)平均查準(zhǔn)率比較：MBH的值為0.960，SGH的值為0.962，KL_PBO略高于本文提出的方法，其值為0.967，其它方法都低于本文提出的方法.

圖6 平均precision、recall、F-Measure和ME比較Fig.6 Average precision，recall，F(xiàn)_Measure and ME comparison

2)平均召回率比較：MBH的值為0.951，SGH的值為0.928，SSNCUT的值為0.934，NLRW的值為0.936，NRW的為0.939，KL_PBO的值為0.938.SSNCUT、NLRW、NRW和KL_PBO略高于SGH，最高的為MBH.

3)平均F-Measure比較：MBH的值為0.958，SGH的值為0.954，KL_PBO略高于本文提出的方法，其值為0.960，其它都方法都低于本文提出的方法.

4)平均錯誤率比較：MBH的值為0.982，SGH的值為0.983，NLRW的值為0.982，NRW的為0.983，KL_PBO的值為0.982，其它方法都低于0.982.綜合來看，本文提出的方法在幾種指標(biāo)上都取得了較好的結(jié)果.

6 總 結(jié)

本文提出將超像素和偽流算法結(jié)合起來進(jìn)行交互式圖像分割，提出的算法有效的解決了SSNcut分割的缺陷：當(dāng)目標(biāo)和背景顏色相似，或紋理復(fù)雜的圖片分割時效果不佳，對標(biāo)記的種子像素非常敏感等問題，提高了分割精度，獲得了很好的分割結(jié)果.通過使用Bhattacharyya系數(shù)計算超像素之間的相似性，大幅度獲提高了分割的效率.進(jìn)一步的研究是將偽流算法運(yùn)用到多個目標(biāo)的分割和語義分割.