融合最小生成樹和四叉樹的圖割圖像分割方法

彭智東，宣士斌

(廣西民族大學(xué) 信息科學(xué)與工程學(xué)院，廣西 南寧 530006)

0 引 言

圖像分割是將圖像中人們感興趣的部分提取出來的一個(gè)過程，是圖像處理環(huán)節(jié)中最關(guān)鍵的步驟，直接影響圖像的后續(xù)處理。現(xiàn)有的圖像分割方法主要分為兩大類：傳統(tǒng)的圖像分割方法和基于特定理論的方法。在基于特定理論方法中，基于圖的方法近年來備受關(guān)注，最常見的有minimum cut[1]、average cut[2]、ratio cut[3]、normalized cut[4]、min-max cut[5]。其中min-max cut是一種經(jīng)典的基于圖論的分割方法。

1989年，基于圖論的方法[6]首次引入到圖像處理領(lǐng)域，由于當(dāng)時(shí)技術(shù)的限制，該方法并沒有得到較好的發(fā)展。21世紀(jì)初，Boykov等[7]通過引入最大流算法[8]，提出了一種快速的基于圖論的圖像分割算法，加快了對(duì)圖割的研究。在隨后數(shù)年中，圖割算法逐漸應(yīng)用到各領(lǐng)域，如醫(yī)學(xué)[9]、地理[10]、人體行為識(shí)別[11]、視頻分割[12]等，使得人們不斷地去改進(jìn)圖割算法。而對(duì)算法的改進(jìn)，無非是從圖的構(gòu)造和能量函數(shù)的構(gòu)造這兩個(gè)方面進(jìn)行。文獻(xiàn)[13-14]使用了分水嶺和均值漂移的方法，將圖像劃分為多個(gè)小型區(qū)域，最后使用最大流最小割實(shí)現(xiàn)圖像分割。文獻(xiàn)[15]在原有圖割方法的基礎(chǔ)上加入了自適應(yīng)的形狀先驗(yàn)?zāi)Ｐ?。文獻(xiàn)[16]在傳統(tǒng)的方法上加入了非局部信息，并且用像素片替代了像素，從算法的效率和效果兩方面提高了算法的性能。文獻(xiàn)[17]使用了對(duì)目標(biāo)和背景種子點(diǎn)特征向量聚類的方法，以改進(jìn)算法的分割效果。文獻(xiàn)[18-19]通過重新構(gòu)造邊上的權(quán)值和刪除圖中簡(jiǎn)單邊的方法來改進(jìn)算法等。

在上述研究的基礎(chǔ)上，文中提出了一種結(jié)合最小生成樹的圖割方法，并通過實(shí)驗(yàn)對(duì)其進(jìn)行驗(yàn)證，

1 圖割概述

圖像分割問題從本質(zhì)上來說是像素分配的問題，也可以說是像素的標(biāo)記問題。給定一個(gè)標(biāo)簽集合L，圖像中的一個(gè)像素為Pi(i=1,2,…,n)，圖像分割就是對(duì)圖像中的每一個(gè)像素分配一個(gè)標(biāo)簽Pi∈Lo或者Pi∈Lp(Lo為目標(biāo)，Lp為背景)的過程。圖割是基于圖論的一種方法，首先將一幅圖像映射為一個(gè)網(wǎng)絡(luò)圖G=(V,E)，在這個(gè)圖中有兩類節(jié)點(diǎn)，即普通節(jié)點(diǎn)Pi，端節(jié)點(diǎn)S和T，其中S為前景目標(biāo)，T為背景目標(biāo)。邊E={(u,v)|u∈P,v∈P}表示圖中邊的集合，一般的圖割方法中只有相鄰的節(jié)點(diǎn)間才存在邊，每條邊上都有權(quán)值ω(u,v)。所要解決的問題就是在已知能量函數(shù)的前提下，如何將這個(gè)圖切割開，并且隔開后所花的代價(jià)最小。G1,G2為被割開后的子圖。

Cut(G1,G2)min=∑ω(u,v)

(1)

一般情況下，用到的能量函數(shù)的形式為：

E(L)=αR(L)+B(L)

(2)

其中，R(L)為區(qū)域項(xiàng)，決定t-link邊的權(quán)值。

(3)

其中，Rp(lp)表示像素p分配給標(biāo)簽lp的代價(jià)，也可以說是Pi∈lp的概率。

(4)

當(dāng)像素p屬于前景的概率P(lp|obj)大于屬于背景的概率P(lp|bkg)時(shí)，就給p分配標(biāo)簽lp=1，反之，給p分配標(biāo)簽0。如果全部的像素都被正確劃分后，此時(shí)區(qū)域項(xiàng)R(L)的能量值就達(dá)到最小。

B(L)表示邊界項(xiàng)，決定n-link邊的權(quán)值。

(5)

其中

(6)

(7)

其中，B(L)為權(quán)重函數(shù)，表示像素p和像素q之間被切割開所要花費(fèi)的代價(jià)；為圖像鄰域，p,q∈表示p和q為兩個(gè)相鄰的像素，‖p-q‖表示兩像素點(diǎn)之間的歐氏距離；σ為圖像噪聲參數(shù)。當(dāng)兩個(gè)像素之間的變化不大時(shí)，表示它們更可能是圖像的邊界點(diǎn)，它們之間的局部權(quán)值就越小，反之亦然。

參數(shù)α是一個(gè)作為平衡區(qū)域項(xiàng)與邊界項(xiàng)的平衡參數(shù)，α的大小直接會(huì)影響到圖像分割的結(jié)果。當(dāng)α越大時(shí)，表示分割的結(jié)果受區(qū)域項(xiàng)的影響更大，當(dāng)α=0時(shí)，只考慮邊界項(xiàng)。對(duì)于α的取值并沒有明確的規(guī)定。文獻(xiàn)[20]中介紹了一種自適應(yīng)α的方法。

2 融合最小生成樹和四叉樹的圖割方法

2.1 結(jié)合最小生成樹的權(quán)值構(gòu)造

傳統(tǒng)圖割算法的復(fù)雜度較高，對(duì)于部分圖像來說，還容易造成錯(cuò)誤的分割。在一幅圖像中，將圖像映射成圖，在圖中可能存在本不應(yīng)該被割開的邊，然而實(shí)際卻被分割開了，這就造成了錯(cuò)誤的分割。對(duì)此，文中借鑒最小生成樹的思想[21]，最小生成樹也可以用來做圖像切割。加入最小生成樹后，能有效降低錯(cuò)誤分割。在實(shí)驗(yàn)中，隨機(jī)生成一個(gè)3階矩陣，然后將這個(gè)矩陣映射成圖，如圖1所示。然后對(duì)圖進(jìn)行最小生成樹處理，結(jié)果如圖2所示。

695564141

圖1 隨機(jī)3階矩陣

圖2 最小生成樹

由圖2和圖3的比較可以看出，原來每?jī)蓚€(gè)相鄰節(jié)點(diǎn)之間都存在著一條邊，而現(xiàn)在只有部分相鄰節(jié)點(diǎn)之間還存在著邊，另一部分相鄰節(jié)點(diǎn)之間的邊被刪除，并且被刪除邊后的兩個(gè)節(jié)點(diǎn)之間的距離也隨之發(fā)生變化。例如，節(jié)點(diǎn)4和7之間的距離為5，節(jié)點(diǎn)8和9之間的距離為3等。

在圖的構(gòu)造中借鑒最小生成樹的思想，對(duì)圖中邊的權(quán)值進(jìn)行了新的定義：

(8)

其中，p,q為圖像中兩個(gè)相鄰的像素，p,q?表示像素p,q在最小生成樹中不相鄰；0≤γ≤1為一個(gè)調(diào)節(jié)參數(shù)，當(dāng)γ=1時(shí)φ退化為傳統(tǒng)權(quán)重函數(shù)；Spq表示像素p和q在最小生成樹中的相似程度。

(9)

其中，∑ω(p,q)=ω(p,p1)+ω(p1,p2)+…+ω(pn,q)表示從像素p到像素q所經(jīng)過最短路徑的權(quán)值之和；d(p,q)表示兩個(gè)像素之間的距離，即像素p到q之間最短路徑上邊的條數(shù)。

通過對(duì)圖中邊的權(quán)值進(jìn)行重新定義，能夠盡可能地提高圖像分割的精確度，使分割結(jié)果更加理想。圖3為加入最小生成樹方法后使用最大流/最小割得到的分割結(jié)果。通過實(shí)驗(yàn)證明，該方法有效提高了分割的精確度，但在精確度提高的同時(shí)，勢(shì)必會(huì)增加算法的復(fù)雜度，于是考慮從減少圖的節(jié)點(diǎn)上去減少算法運(yùn)行的時(shí)間。因此，引入了一種四叉樹方法[22]來減少圖中節(jié)點(diǎn)的數(shù)量。

2.2 四叉樹分割方法

令G表示一幅圖像，將G分割成n個(gè)子區(qū)域G1,G2,···,Gn的過程就叫分割，滿足的條件如下：

(2)Gi(i=1,2,…,n)是一個(gè)連通域；

(3)Gi∩Gj=?,i≠j；

(4)P(Gi)=TRUE；

(5)P(Gi∪Gj)=FALSE，對(duì)于任意相鄰像素Gi和Gj。

其中，P(Gi)是定義在集合Gi的點(diǎn)上的邏輯謂詞，?表示空集。

四叉樹的分解步驟如下：

(1)將原圖像分成幾個(gè)(一般為4個(gè))大小相同的區(qū)域。

(2)將所分圖像的每個(gè)區(qū)域依次判定是否滿足判定標(biāo)準(zhǔn)，如果不滿足，就將這個(gè)區(qū)域繼續(xù)細(xì)分，直到所有的區(qū)域都滿足這個(gè)評(píng)判標(biāo)準(zhǔn)為止。使用的評(píng)判標(biāo)準(zhǔn)為，同一區(qū)域內(nèi)像素值的方差不超過某個(gè)閾值，即S(Ri)

(3)使用像素點(diǎn)合并的方法，合并孤立的像素點(diǎn)。

(4)迭代重復(fù)上述過程，直到所有的區(qū)域都符合評(píng)判標(biāo)準(zhǔn)。

2.3 融合最小生成樹和四叉樹的圖割方法

文中將graph cut方法和最小生成樹方法相結(jié)合，在圖權(quán)值的構(gòu)造中，考慮了原本相鄰的兩個(gè)節(jié)點(diǎn)在最小生成樹中也相鄰或者不相鄰的情況。重新構(gòu)造了邊的權(quán)值。但是當(dāng)面對(duì)圖中節(jié)點(diǎn)數(shù)過多時(shí)，生成最小生成樹和使用最大流最小割求解能量函數(shù)的過程中非常耗時(shí)，于是又引入四叉樹的方法，將原始圖像分割成各個(gè)小區(qū)域，將各個(gè)小區(qū)域建立賦權(quán)圖G=(V,E)，最后采用最大流最小割的方法完成區(qū)域的劃分。這樣會(huì)大大減少圖中節(jié)點(diǎn)的數(shù)量，縮短算法的時(shí)間。該方法的詳細(xì)步驟如下：

(1)選取一個(gè)合適的閾值，根據(jù)四叉樹的分解方法分解該圖像。

(2)將分解后的圖像映射成賦權(quán)圖G=(V,E)。

(3)對(duì)該圖進(jìn)行最小生成樹處理，并求出φpq。

(4)重新構(gòu)造賦權(quán)圖G=(V,E)。

(5)使用最大流/最小割進(jìn)行分割。

EN(L)=αR(L)+BN(L)

此時(shí)的p，q分別表示區(qū)域p和區(qū)域q，并且p和q是兩個(gè)相鄰的小區(qū)域。區(qū)域p和q的像素值為該區(qū)域內(nèi)所有像素的平均值，區(qū)域p到q的歐氏距離為兩個(gè)區(qū)域中心點(diǎn)之間的距離。

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

為了驗(yàn)證算法的準(zhǔn)確性與快速性，選擇MATLAB自帶圖像庫中的經(jīng)典圖像進(jìn)行分析和研究。在參數(shù)的選擇上，并沒有做更深入的研究，而是取了一些常規(guī)參數(shù)。實(shí)驗(yàn)中A取值為20。A的大小是至關(guān)重要的，A越大，算法運(yùn)行所需的時(shí)間就越少，但是圖像對(duì)細(xì)節(jié)的保留也就越少，會(huì)丟失更多的細(xì)節(jié)。例如，圖4(f)相較于圖4(e)就丟失了部分細(xì)節(jié)。這種細(xì)節(jié)的丟失可以通過更改A的大小來彌補(bǔ)。文中并沒有嚴(yán)格地給出參數(shù)A的計(jì)算方式，更多的是根據(jù)實(shí)驗(yàn)對(duì)A進(jìn)行取值。參數(shù)γ的取值為0.4。參數(shù)γ主要決定在邊權(quán)值重新構(gòu)造的過程中，是否要更多的依賴最小生成樹中兩個(gè)節(jié)點(diǎn)之間的距離。γ越小表示在權(quán)值構(gòu)造中，更多的是考慮最小生成樹中兩個(gè)節(jié)點(diǎn)距離對(duì)權(quán)值的影響，反之亦然。參數(shù)γ大小對(duì)算法時(shí)間并沒有直接影響。對(duì)于參數(shù)γ的選取同樣是根據(jù)實(shí)驗(yàn)得出。

實(shí)驗(yàn)結(jié)果如圖4和圖5所示，分割時(shí)間對(duì)比見表1。

圖4 對(duì)比實(shí)驗(yàn)1

圖5 對(duì)比實(shí)驗(yàn)2

s

由圖4和圖5可以看出，使用傳統(tǒng)圖割方法的效果并不是很好，特別是對(duì)背景比較復(fù)雜的圖像，分割效果更是差強(qiáng)人意。在加入最小生成樹的方法之后，分割效果立竿見影，但是在分割的時(shí)間上有所增加，例如，圖4(e)相較于圖4(f)所用時(shí)間增加了0.758 s，圖5(e)相較于圖5(f)所用時(shí)間增加了0.805 s，算法運(yùn)行時(shí)間的增加是不能接受的。在加入四叉樹后，算法運(yùn)行效率明顯提高，并且分割結(jié)果也優(yōu)于傳統(tǒng)的圖割方法，但是，對(duì)于復(fù)雜背景的圖像來說，會(huì)丟失部分細(xì)節(jié)，例如，圖4(f)相較于圖4(e)就丟失了一部分的細(xì)節(jié)，細(xì)節(jié)丟失的程度由參數(shù)A控制。從圖4(c)和(d)中可以看出，復(fù)雜背景中細(xì)節(jié)的丟失是不可避免的。圖5(f)相較于圖5(e)來說，并沒有明顯的變化。所以，對(duì)于簡(jiǎn)單的背景圖像，細(xì)節(jié)的丟失是可以忽略的。因此對(duì)于簡(jiǎn)單圖像的分割，不管是算法的效果還是復(fù)雜度，該方法都無疑是最好的選擇。

4 結(jié)束語

在傳統(tǒng)方法的基礎(chǔ)上加入了最小生成樹和四叉樹的方法，重新定義了能量函數(shù)，重構(gòu)了圖中邊的權(quán)值計(jì)算方法，最后構(gòu)圖并通過最大流/最小割算法進(jìn)行求解。在計(jì)算邊與邊的權(quán)值時(shí)引入最小生成樹方法，提高了相似性計(jì)算的正確性。為了提高算法的效率，采用四叉樹的方法，減少圖中節(jié)點(diǎn)的數(shù)量，在保證算法準(zhǔn)確度的同時(shí)，降低了算法執(zhí)行的時(shí)間，最后實(shí)驗(yàn)也證明了其可行性。但是該算法同時(shí)也存在一些缺陷，如參數(shù)A和γ的設(shè)定并不明確，以及克服圖像細(xì)節(jié)的丟失等，這些問題都將在以后的學(xué)習(xí)和工作中有待進(jìn)一步改進(jìn)。