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

彭智東，宣士斌

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

0 引 言

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

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

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

1 圖割概述

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

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

(1)

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

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

(2)

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

(3)

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

(4)

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

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

(5)

其中

(6)

(7)

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

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

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

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

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

695564141

圖1 隨機3階矩陣

圖2 最小生成樹

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

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

(8)

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

(9)

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

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

2.2 四叉樹分割方法

令G表示一幅圖像，將G分割成n個子區域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個)大小相同的區域。

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

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

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

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

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

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

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

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

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

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

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

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

3 實驗結果與分析

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

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

圖4 對比實驗1

圖5 對比實驗2

s

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

4 結束語

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