基于隨機游走的自動圖像分割算法*

茅正沖， 韓 毅

0 引 言

近年來，基于圖論的圖像分割算法成為研究的熱點，應(yīng)用圖論進(jìn)行圖像處理具有直觀、速度快、效率高等諸多優(yōu)點。依據(jù)用戶參與與否，圖像分割可分為交互式圖像分割和自動圖像分割。Boykkov Y等人[1]提出了Graph Cut算法，結(jié)合了圖像的區(qū)域信息和邊界信息，目前已成為廣泛使用的交互分割方法。Grady L等人[2]率先將隨機游走模型應(yīng)用到圖像分割中，計算速度快，可很好地檢測弱邊緣，并且對噪聲有較強的魯棒性，但需要用戶標(biāo)記標(biāo)記點，是一種半自動分割算法。

郭麗等人[3]利用背景差分實現(xiàn)了自動識別目標(biāo)區(qū)域，通過形態(tài)學(xué)方法求得骨架結(jié)構(gòu)，從中獲取標(biāo)記點，再采用隨機游走算法進(jìn)行自動圖像分割，在多車輛檢測領(lǐng)域解決了交互分割速度慢的問題;但對背景建模時，背景的更新是一個難點。李昌興等人[4]引入了加速均值算法，提出了一種加速譜聚類的圖像分割算法。Qin C C等人[5]對圖像進(jìn)行超像素分割，使用近鄰傳播聚類算法求取超像素區(qū)域中心點，通過固定閾值對中心點標(biāo)記，自動地為隨機游走算法標(biāo)定標(biāo)記點。文獻(xiàn)[6]中采用模式挖掘算法選取標(biāo)記點，在顯著性提取中取得了不錯的效果。

本文提出了一種結(jié)合顯著性,模式挖掘算法和隨機游走的自動分割算法，通過計算圖像的顯著性圖，初步確定感興趣目標(biāo)的區(qū)域；通過模式挖掘算法為隨機游走初步選取標(biāo)記點，結(jié)合位置信息進(jìn)一步篩選標(biāo)記點；使用隨機游走算法對輸入圖像進(jìn)行分割。實驗結(jié)果表明：本文方法可以自動對圖像進(jìn)行較精確地分割。

1 隨機游走算法

根據(jù)圖像構(gòu)成加權(quán)圖G(V,E)，圖中任意頂點v∈V視為圖像中的一個像素點或者超像素塊，將頂點分作VM和VU2個集合，VM表示已標(biāo)記點的集合，VU表示未標(biāo)記點的集合，任意一個邊e∈E?V×V視為兩個相鄰像素之間的關(guān)系，邊的權(quán)值w視為像素之間的相似或差異性度量

di=∑wij

(1)

式中di為頂點vi的度，表示所有與頂點vi連接的邊的權(quán)重之和。

根據(jù)頂點、邊以及權(quán)重可以構(gòu)建圖的Laplace矩陣L,將頂點分為VM和VU后，Laplace矩陣表示為

(2)

隨機游走的求解過程可以轉(zhuǎn)化為求解Dirichlet問題[7]，即尋求一個滿足邊界條件的調(diào)和函數(shù)u(x,y)，使得Dirichlet積分達(dá)到最小值，Dirichlet積分為

(3)

(4)

由以上分析可知，隨機游走算法進(jìn)行圖像分割的數(shù)學(xué)理論完整，度量特征選取合適，可以對圖像進(jìn)行完全地分割，但該算法要求用戶指定標(biāo)記點，限制了其在自動圖像分割中的應(yīng)用。

2 顯著性檢測

為了實現(xiàn)隨機游走算法自動分割，本文通過視覺顯著性初步確定目標(biāo)區(qū)域。Sun J G[7]等人提出了一種基于馬爾科夫吸收概率的(Markov absorption probability,MAP)顯著性檢測算法，對于一個給定的狀態(tài)集S={s1,s2,…,sl}，pij表示狀態(tài)si轉(zhuǎn)移到狀態(tài)sj的概率，馬爾科夫過程表示為轉(zhuǎn)移矩陣P。給定k個吸收節(jié)點，m個暫態(tài)的馬爾科夫鏈，轉(zhuǎn)移矩陣P為

(5)

式中Q∈[0,1]mm為暫態(tài)之間的概率轉(zhuǎn)移矩陣；R∈[0,1]mk為暫態(tài)與吸收狀態(tài)之間的轉(zhuǎn)移概率；I為k×k的單位矩陣?？傻没A(chǔ)矩陣N,N的元素nij表示暫態(tài)si轉(zhuǎn)移到暫態(tài)sj的估計轉(zhuǎn)移次數(shù)

N=(I-Q)-1=I+Q+Q2+…

(6)

馬爾科夫鏈中每個暫態(tài)si都將獨立地轉(zhuǎn)移至吸收狀態(tài)sj，吸收概率矩陣為

B=NR

(7)

式中B的每個元素bij表示暫態(tài)si到吸收狀態(tài)sj的概率。

3 模式挖掘算法

文獻(xiàn)[6]提出了通過模式挖掘算法選取標(biāo)記點。給定一個有M項的集合I={i1,i2,…,iM}，交易集T為I的子集，交易數(shù)據(jù)庫D={T1,T2,…,TN}由N個不同的交易集組成。集合A由交易集T∈D中部分元素組成，且滿足A?I，A的支持度定義為

(8)

當(dāng)supp(A)大于固定的閾值tmin時，集合A稱為頻繁項集。

關(guān)聯(lián)規(guī)則A→p描述A和p同時出現(xiàn)的可能性，關(guān)聯(lián)規(guī)則強度可以用支持度和自信度描述，關(guān)聯(lián)支持度、自行度分別定義為

supp(A→p)=supp(A∪{p})

(9)

(10)

支持度和自信度越高，關(guān)聯(lián)規(guī)則越強，二者相關(guān)性越強。

4 基于隨機游走的自動圖像分割

4.1 顯著性確定目標(biāo)區(qū)域

為了選擇一種更有效的顯著性提取方法，本文使用若干常見算法求取顯著性圖，結(jié)果如圖1所示，圖中依次采用的CA[8]，SR[9]，MSS[10]，F(xiàn)ASA[11]，MAP[7]算法。由實驗結(jié)果分析可知:CA和SR得到的顯著圖中目標(biāo)外輪廓較清晰，但內(nèi)部信息未很好地顯示，MSS和FASA算法部分對背景的抑制能力相對較弱，而基于馬爾科夫鏈的MAP算法提取顯著圖目標(biāo)鮮明，對背景抑制較好，本文根據(jù)顯著圖進(jìn)行目標(biāo)的初步定位，采用基于馬爾科夫鏈的MAP算法確定目標(biāo)區(qū)域。

圖1 不同算法顯著性檢測結(jié)果

4.2 基于模式挖掘的標(biāo)記點確定

基于模式挖掘算法確定的標(biāo)記點如圖2所示。首先對給定的圖像進(jìn)行超像素分割，通過顯著圖確定目標(biāo)區(qū)域，將顯著區(qū)域的像素塊標(biāo)記為正樣本，顯著區(qū)域外的像素塊標(biāo)記為負(fù)樣本，采用模式挖掘算法確定和正樣本相關(guān)的超像素塊。具體流程如下：

1)采用SLIC[12]算法在三個尺度對圖像進(jìn)行超像素分割，得到一個超像素集S={s1,s2,…,sN},結(jié)合顯著圖，當(dāng)每個超像素塊在顯著圖中對應(yīng)區(qū)域亮度值大于一定閾值時，該像素塊認(rèn)定為正樣本；否則，認(rèn)定為負(fù)樣本。

2)對每個超像素塊進(jìn)行K均值聚類，計算其聚類中心在整幅圖像中的索引，表示超像素塊的全局位置信息。

3)將包含樣本標(biāo)簽和全局位置信息的超像素輸入到Apriori頻繁項挖掘算法中，得到顯著性的頻繁超像素集。

4)對相同尺度的超像素和頻繁超像素集進(jìn)行關(guān)聯(lián)規(guī)則分析，求取顯著的超像素，并將其中心認(rèn)定為標(biāo)記點。

結(jié)合上述流程，部分初步提取的標(biāo)記點如圖2(b)所示，分析可知，通過模式挖掘算法求得的標(biāo)記點較豐富，標(biāo)記點也聚集在目標(biāo)區(qū)域，部分標(biāo)記點位于目標(biāo)周圍。為了進(jìn)一步地將標(biāo)記點分為前景標(biāo)記點和背景標(biāo)記點，本文對標(biāo)記點的位置進(jìn)行分析，將顯著目標(biāo)內(nèi)部的標(biāo)記點判定為前景標(biāo)記點，外部的標(biāo)記點判定為背景標(biāo)記點，處理后的結(jié)果如圖2(c)所示。

圖2 模式挖掘算法確定的標(biāo)記點

4.3 隨機游走算法圖像分割

本文結(jié)合顯著圖和模式挖掘算法，自動提取標(biāo)記點，融合顯著性特征進(jìn)一步將標(biāo)記點分為前景標(biāo)記點和背景標(biāo)記點兩類，最終使用隨機游走算法對圖像進(jìn)行分割，整體流程如圖3所示。

圖3 自動圖像分割算法流程

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

為了驗證本文算法的有效性，選取若干樣本進(jìn)行仿真實驗，數(shù)據(jù)來自Berkeley數(shù)據(jù)集。作為實驗對比，使用人工給定標(biāo)記點，經(jīng)典隨機游走算法進(jìn)行圖像分割，同時采用Grab Cut算法對樣本進(jìn)行交互分割，本文提出的隨機游走進(jìn)行自動分割，對比結(jié)果如圖4所示。

圖4 圖像分割結(jié)果對比

由圖4(b)可以觀察到，傳統(tǒng)的隨機游走算法的圖像分割結(jié)果依賴于人工給定的標(biāo)記點，在標(biāo)記點不很充分的情況下容易出現(xiàn)過分割和欠分割現(xiàn)象。分析圖4(d)可知，本文算法取得了良好的檢測結(jié)果，基于模式挖掘算法選取的標(biāo)記點數(shù)量豐富，對背景抑制能力較強，分割的目標(biāo)輪廓清晰，為圖像的后續(xù)處理奠定了良好的基礎(chǔ)。將結(jié)果與圖4(c)Grab Cut算法迭代分割結(jié)果進(jìn)行對比，在背景不是特別復(fù)雜的情況下，本文算法的分割結(jié)果接近交互分割，可以注意到Grab Cut處理后圖像輪廓更完整，本文算法有少量邊界出現(xiàn)了過分割現(xiàn)象，如飛機的后部機翼和犀牛的牛角部分，但本文算法可以無需用戶參與自動地完成圖像分割。

為了進(jìn)一步說明算法的有效性，提取分割結(jié)果邊界與圖像標(biāo)準(zhǔn)輪廓進(jìn)行對比，采用正確率(P)、召回率(R)以及F值量化評價實驗結(jié)果。P表征檢測點為真正的輪廓的概率；R表征檢測檢測點的數(shù)量比例；F=2×P×R/(P+R)為準(zhǔn)確率和召回率的調(diào)和評價，反映整體效果。部分實驗樣本的評價結(jié)果平均值如圖5所示。

圖5 3種算法仿真數(shù)值評價結(jié)果

由數(shù)值可以看出，相較于傳統(tǒng)隨機游走分割算法，本文算法分割的結(jié)果在正確率和召回率方面均具有明顯的提升，圖像分割質(zhì)量較好，但與Grab Cut算法相比，分割結(jié)果表現(xiàn)略微欠佳。在要求精細(xì)分割的應(yīng)用中，更好的選擇是交互分割方法，但在自動圖像檢測和批量處理圖像時，本文算法分割效果良好，具有一定的優(yōu)勢。

6 結(jié) 論

為了實現(xiàn)自動圖像分割，重點研究了顯著性提取、模式挖掘算法以及隨機游走算法。采用模式挖掘算法進(jìn)行初步確定標(biāo)記點，進(jìn)一步結(jié)合顯著圖將標(biāo)記點分類為前景和背景標(biāo)記點，算法自動地為隨機游走提供標(biāo)記點；應(yīng)用顯著圖和模式挖掘算法確定標(biāo)記點，隨機游走算法最終實現(xiàn)圖像分割，效果較好，且分割過程不需用戶指定區(qū)域。實驗結(jié)果表明：本文方法處理效果較好，具有一定的應(yīng)用研究價值。

參考文獻(xiàn):

[1] Boykov Y,Veksler O,Zabih R.Fast approximate energy minimization via graph cuts[J].IEEE Transactions on Pattern Analysis and Machine Intelligence,2001,23(11):1222-1239.

[2] Grady L．Random walks for image segmentation[J].IEEE Tran-sactions on Pattern Analysis and Machine Intelligence，2006，28(11):1768-1783．

[3] 郭 麗，高立群，劉 濛，等.一種新的隨機游走多車輛檢測算法[J].中國圖象圖形學(xué)報，2010(3)：392-396.

[4] 李昌興,黃艷虎,支曉斌,等.基于加速k均值的譜聚類圖像分割算法改進(jìn)[J].傳感器與微系統(tǒng),2016,35(9):137-140.

[5] Qin C C,Zhang G P,Zhou Y C,et al.Integration of the saliency-based seed extraction and random walks for image segmentation[J].Neuro Computing,2014,129:378-391.

[6] Kong Y Q,Wang L J,Liu X P,et al.Pattern Mining Saliency[C]∥ECCV,2016.

[7] Sun J G,Lu H C,Liu X P.Saliency region detection based on Markov absorption probabilities[J].IEEE Transaction on Image Processing,2015,24(5):1639-1649.

[8] Goferman S,Zelnik-Manor L,Tal A.Context-aware saliency detection[C]∥Computer Vision and Pattern Recognition,2010:2376-2383.

[9] Hou X,Zhang L.Saliency detection.A spectral residual approa-ch[C]∥IEEE Conference on Computer Vision and Pattern Recognition,2007:1-8.

[10] Radhakrishna Achanta,Sabine Susstrunk.Saliency detection using maximum symmetric surround[C]∥International Conference on Image Processing(ICIP),Hong Kong,2010.

[11] Yildirim G,Süsstrunk S.FASA:Fast,accurate,and size-aware salient object detection[C]∥Asian Conferenceon Computer Vision,ACCV 2014,2014:514-528.

[12] Achanta Radhakrishna,Shaji Appu,Smith Kevin,et al.SLIC superpixels compared to state-of-the-art superpixel methods[J].IEEE Transactions on Pattern Analysis and Machine Intelligence,2012,34(11):2274-2282.