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

彭智東，宣士斌

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

0 引 言

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

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

在上述研究的基礎上，文中提出了一種結合最小生成樹的圖割方法，并通過實驗對其進行驗證，

1 圖割概述

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

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

(1)

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

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

(2)

其中，R(L)為區(qū)域項，決定t-link邊的權值。

(3)

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

(4)

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

B(L)表示邊界項，決定n-link邊的權值。

(5)

其中

(6)

(7)

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

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

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

2.1 結合最小生成樹的權值構造

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

695564141

圖1 隨機3階矩陣

圖2 最小生成樹

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

在圖的構造中借鑒最小生成樹的思想，對圖中邊的權值進行了新的定義：

(8)

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

(9)

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

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

2.2 四叉樹分割方法

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

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

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

(4)P(Gi)=TRUE；

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

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

四叉樹的分解步驟如下：

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

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

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

(4)迭代重復上述過程，直到所有的區(qū)域都符合評判標準。

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

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

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

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

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

(4)重新構造賦權圖G=(V,E)。

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

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

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

3 實驗結果與分析

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

實驗結果如圖4和圖5所示，分割時間對比見表1。

圖4 對比實驗1

圖5 對比實驗2

s

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

4 結束語

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