茅正沖， 韓 毅

0 引 言

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

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

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

1 隨機(jī)游走算法

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

di=∑wij

(1)

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

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

(2)

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

(3)

(4)

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

2 顯著性檢測(cè)

為了實(shí)現(xiàn)隨機(jī)游走算法自動(dòng)分割，本文通過(guò)視覺(jué)顯著性初步確定目標(biāo)區(qū)域。Sun J G[7]等人提出了一種基于馬爾科夫吸收概率的(Markov absorption probability,MAP)顯著性檢測(cè)算法，對(duì)于一個(gè)給定的狀態(tài)集S={s1,s2,…,sl}，pij表示狀態(tài)si轉(zhuǎn)移到狀態(tài)sj的概率，馬爾科夫過(guò)程表示為轉(zhuǎn)移矩陣P。給定k個(gè)吸收節(jié)點(diǎn)，m個(gè)暫態(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的估計(jì)轉(zhuǎn)移次數(shù)

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

(6)

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

B=NR

(7)

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

3 模式挖掘算法

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

(8)

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

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

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

(9)

(10)

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

4 基于隨機(jī)游走的自動(dòng)圖像分割

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

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

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

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

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

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

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

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

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

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

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

4.3 隨機(jī)游走算法圖像分割

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

圖3 自動(dòng)圖像分割算法流程

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

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

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

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

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

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

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

6 結(jié) 論

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

參考文獻(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ī)游走多車(chē)輛檢測(cè)算法[J].中國(guó)圖象圖形學(xué)報(bào)，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.