基于圖論Ｇｏｍｏｒｙ－Ｈｕ算法的快速圖像分割
2008-12-31 00:00:00劉丙濤田錚周強鋒李小斌
計算機應用研究 2008年9期
摘 要：
GomoryHu算法是圖論中的經典算法，用于尋找圖的最小流割等價樹，具有最優解，但是該算法很難處理較大的圖像，而且傾向于分割出孤立點集。為此，給出了孤立點的判定方法，并提出一種基于GomoryHu算法的圖像分割方法。該算法首先通過快速聚類減少圖中頂點數目，然后構造新的賦權圖，并應用GomoryHu算法對圖進行最優劃分，得到分割結果。提出的算法對多幅自然圖像進行了分割實驗，平均分割時間在3 s內。實驗結果證明了算法的有效性和快速性。
關鍵詞：圖像分割； GomoryHu算法； 聚類； 圖論
中圖分類號：TP391 文獻標志碼：A
文章編號：10013695(2008)09286503
Fast image segmentation based on GomoryHu algorithm
LIU Bingtao1， TIAN Zheng1，2， ZHOU Qiangfeng1， LI Xiaobin1
（1.Dept. of Applied Mathematics， Northwestern Polytechnical University， Xi’an 710072， China; 2.National Key Laboratory of Remote Sensing Science， Institute of Remote Sensing Applications， Chinese Academy of Sciences， Beijing 100101， China）
Abstract:
GomoryHu algorithm is a classical algorithm for finding the minimum flow and cut equivalent tree of the graph in graph theory， it had the optimal solution. But it was very difficult to deal with large images， and it was biased toward finding small components. In order to solve this problem， this paper presented a novel definition of isolated node， and proposed a novel algorithm based on improved GomoryHu algorithm. This algorithm first used the fast clustering algorithm to reduce the number of vertices ，then used the improved GomoryHu algorithm in the new graph and achieve the optimal solution. Then applied the new algorithm to a number of natural images. The experimental results demonstrate that the algorithm is effective and efficient.
Key words：image segmentation; GomoryHu algorithm; clustering; graph theory
0 引言
圖像分割是圖像理解的基礎，在計算機視覺領域占有很重要的地位。基于圖的圖像分割方法能夠很好地把握圖像的全局特征，而且更加符合人類的視覺系統，因此這種方法發展很快，尤其是基于圖割的方法。
從1993年Wu等人[1]首先將圖論中割的方法用于圖像分割開始，不斷有新的模型提出。特別是1997年Shi與Malik提出標準割模型[2，3]以后，各種割模型相繼提出，主要有最大最小割模型[4]、網巢割模型[5]、最優割模型[6]等。目前的研究按照是否具有理論最優解而被分為兩支：a)可以從理論上得到最優解；b)NP難問題，無法從理論上得到最優解，通過算法逼近得到次優解。可見尋找具有理論最優解的分割方法是非常重要的，也是眾多研究者所希望找到的。Wu等人提出的最小割模型屬于第一類，它可以獲得最優解，但是最小割模型傾向于分割出孤立點集[2，3]，標準割模型雖然可以避免這個缺點，但它卻傾向于將圖像分成兩個大小相等的塊[5]，并且與最小割模型一樣，標準割算法相當耗時。算法耗時也幾乎成為割模型方法不可逾越的障礙，其他幾種割模型方法同樣受到這個問題的困擾。很多模型均可以得到相當好的分割結果，但是算法運行時間很長，無法達到實時性的要求。Sharon等人在文獻[7，8]中提出了一種多尺度方法，能夠快速、有效地進行圖像分割，基本滿足算法實時性的要求，但是其無法得到理論最優解。因此研究同時具有理論最優解和實時處理的方法是非常有意義的工作。為此，本文從GomoryHu算法入手，研究可以解決上述問題的方法。
GomoryHu算法是圖論中的經典算法，用于求解圖的最小流割等價樹，具有理論最優解的特性。它只需要求解n-1（n是圖的頂點數）次最大流就能夠最優地將圖劃分為k個子圖。在基于圖的圖像分割中，對于適當的賦權圖（大約2 000個頂點），通過GomoryHu算法構造圖的最小流割等價樹，并對圖的流割等價樹去邊，從而得到圖的最優化分割。然而對于較大的圖來說其計算量將變得很大，基本無法實現。為了克服這個困難，最好的辦法是能夠找到一種減少圖頂點的方法，從而能夠利用GomoryHu算法構造割等價樹，進行最優分割[1]。
為了解決這些問題，本文提出一種新的基于GomoryHu算法的圖像分割方法，不僅可以得到理論最優解，而且能夠達到實時性的要求。該算法首先對原圖進行快速聚類來減少圖中的頂點數目。當圖的頂點達到算法要求時，則利用GomoryHu算法對圖進行最優劃分，再映射回圖像，得到對原圖像的最優分割。
1 GomoryHu割樹
對于一個無向賦權圖來說，可以構造一個具有如下性質的樹[9]：
a) 樹中的頂點就是原圖中的頂點；
b) 樹中的每一條邊均有一個非負的權wij；
c) 對于樹中的頂點s和t，有一條惟一的路徑，令邊eij為這條路徑中權值最小的邊，那么頂點s與t之間的最小割值為wij，這樣的最小割可以通過去掉邊eij得到。
這樣的樹就稱做GomoryHu割樹，通過去邊就可以得到對原圖的最優劃分。
筆者可以通過GomoryHu算法構造割樹，它的主要原理[9]是根據最大流最小割定理，利用EdmondsKarp算法求解任意相鄰頂點間的最大流（即最小割），從而得到與圖對應的最小流割等價樹（GomoryHu割樹），即樹上的每條邊的權值均是兩個端點的最小割值。對最小流割等價樹的每條邊按照權值由小到大的順序進行去邊，即可得到圖的子圖，當子圖數目達到k時停止。此時即可得到對原圖的k個最優劃分，映射回原圖像則可得到相應圖像的k個塊。
GomoryHu算法首先任意選擇兩個頂點s和t，利用EdmondsKarp算法計算其最小割值和割邊，去掉最小割邊后，原圖被分為兩個子圖，然后分別對這兩個子圖重復上述過程。最終得到原圖的最小流割等價樹。
GomoryHu算法的目的是通過構造GomoryHu割樹，然后按照割值大小依次去掉割值較小的邊，這樣做可以使得類內的割值最大，也就是相似度最大，而類間的相似度最小。這也充分符合圖像分割的原則，就是使得塊內相似度最大，塊間相似度最小。從理論上考慮這也是最優的分割方法，但是也正因如此，這種算法很容易將圖像中的孤立點分離出來，如圖1所示。圖1（b）是根據GomoryHu算法構造的割樹，按照割值由小到大去邊，那么頂點d與f之間的邊首先去掉，其次是頂點f與e之間的邊。如果圖像中存在孤立點i，它與其他頂點的割值必然很小，那么它將被單獨分割出來，這樣就會影響圖像的整體分割效果。
為了解決這個問題，首先對原圖進行聚類，這樣做不僅可以減少頂點數目以達到GomoryHu算法的要求，還可以通過聚類盡量減少孤立點的存在，讓孤立點聚合到相近的類中，這樣就會避免分割出孤立點。
如果一個頂點與其所有鄰接頂點的權值之和小于其鄰接頂點之間權值和的某一個比例，那么這個頂點就是孤立點。下面給出孤立點的定義：
∑j∈Vwij≤β∑j∈V，k∈Vwjk(1)
其中：j是頂點i的鄰域頂點；V是頂點i的鄰域頂點集合。
2 基于圖聚類的GomoryHu算法
首先根據原圖像構造無向賦權圖，圖中的頂點代表圖像中的像素。設無向賦權圖為=G(V，E，W)。其中:V=(v1，v2，…，vn)是頂點集合；E={eij=(vi，vj)}是邊集合；eij表示該邊連接頂點vi與vj。邊權矩陣W=(wi，j)中的元素wij反映了頂點i和j之間的相似程度。當頂點i與j很相似時，wij較大；當i與j不相似時，w
其中：Ii代表頂點i的亮度；σ1、σ2代表尺度參數，根據經驗選取；Dij代表頂點i與j之間的歐式距離。
為了加快算法速度，定義原始圖為八連通無向賦權圖，經過第一次聚類后，需要重新定義賦權圖并應用GomoryHu算法。這時需要對每一類內的頂點進行頂點收縮，合并為一個新的頂點，該頂點繼承原類內頂點的鄰接關系，如圖2所示。圖2(a)中的頂點1、2、3同屬于類A，頂點4、5、6同屬于類B，頂點7、8、9同屬于類C。經過頂點收縮后得到圖2(b)，頂點A 代表類A，頂點B代表類B，頂點C代表類C。
下面定義頂點收縮后新頂點的亮度值為
其中：Vi代表第i個類的頂點總數。由于此時圖中頂點數目不是很多，為了保證計算的精度，定義此圖為全連通無向賦權圖，相似度函數定義為
聚類的最重要原則是使得類內相似度最大，類間相似度最小。為此，本文定義聚類原則如下：
其中：頂點i是類Vi的代表元素；S是代表元素集合；vol為圖的頂點總數；頂點l是頂點j的鄰接頂點；α是頂點j與其周圍鄰接頂點權值之和的一個比例權重，按照經驗一般選取為0.1。如果滿足式(5)則認為頂點i和j屬于同一類，不滿足則不屬于同類，即頂點j代表另一類，令j∈S，vol=vol-1。為了加速算法，筆者采用并行聚類方法，只需要遍歷一次就可以使得每一個頂點找到所屬的類。
該算法的具體步驟如下：
a)令圖中第一個頂點i為類Vclass的代表元素，令vol=vol-1。
b)遍歷G中的頂點j，如果滿足式（5），則令j∈Vclass，Vclass=Vclass+{j}，vol=vol-1；如果不滿足，則根據孤立點定義式（1）判斷頂點j是否為孤立點。如果是，則j∈Vclass，Vclass=Vclass+{j}，vol=vol-1，轉向d)；如果不是孤立點，則轉向c)。
c)令class=class+1，j為類Vclass的代表元素，且j∈S，S=S+{j}，vol=vol-1。
d) 判斷vol是否為空，如果為空，則圖中的所有元素均已處理完畢，并根據圖2所述規則重新構造賦權圖，轉到e)；否則，轉到c)繼續對未處理的元素進行聚類。
e) 對新的賦權圖G，應用GomoryHu算法得到對圖的最優k個劃分。
f)映射回原圖像得到最優分割。
3 實驗結果與分析
本算法在P4 2.6 GHz CO、CPU計算機Visual C++6.0平臺上實現。為了驗證其有效性和快速性，對多幅自然圖像進行了實驗，平均分割時間在3 s以內，基本滿足了實時性的要求。為了能夠更好地說明本算法的流程，圖3給出了本算法分步得到的結果。圖3(b)是對原圖像進行快速聚類后得到的結果，在這一過程中，圖像被分為很多類，接下來以每一類為一個頂點，構造新的賦權圖，并利用GomoryHu算法尋找它的流割等價樹，去邊后得到第二步分割（圖3(c)）。
圖4給出了本文方法分別與SWA算法、標準割算法的分割結果比較。三幅自然圖像(灰度圖像)大小分別為256×170、300×200和256×170，本文方法分割時的尺度參數δ分別為30、30、18。從算法運行時間來比較，標準割算法耗時最長，分別為72、38和90 s；SWA算法與本文方法耗時基本相當，均在3 s左右。分割質量從視覺角度來看，本文方法要明顯優于其他兩種方法，尤其是第一幅圖，分割結果相當精確。對于第二幅圖，三種方法的結果相當，但是如果仔細觀察可以發現，本文方法更好地保留了目標的細節。第三幅圖，本文方法分割結果也相當精確。綜上所述，本文方法不僅處理時間短，而且分割結果邊緣更精確，更符合人類的視覺特性，分割結果相對較好。
4 結束語
研究具有理論最優解的方法在基于圖論的圖像分割中是非常有意義的工作。為此本文給出了利用GomoryHu算法應用于圖像分割的一種新方法，它充分結合了聚類和GomoryHu算法的優點，使該算法不僅具有實時性，而且繼承了GomoryHu算法的最優分割特性。實驗結果也充分說明了本算法的有效性和快速性。然而SAR圖像與光學圖像有著很大的區別，同時也具有更重要的價值，所以將本算法應用于SAR圖像將是很有意義的，這也是筆者正在研究的工作。
參考文獻：
[1]WU Z， LEAHY R. An optimal graph theoretic approach to data clustering: theory and its application to image segmentation[J]. IEEE Trans on Pattern Analysis and Machine Intelligence，1993， 15(11):11011113.
[2]SHI J， MALIK J. Normalized cuts and image segmentation[C]//Proc ofIEEE Conference on Computer Vision and Pattern Recognition.1997:731737.
[3]SHI J， MALIK J. Normalized cuts and image segmentation[J]. IEEE Trans on Pattern Analysis and Machine Intelligence. 2000，22(8): 888905.
[4]DING C， HE X， ZHA H， et al. A minmax cut algorithm for graph partitioning and data clustering[C]//Proc of IEEE Intl Conf on Data Mining.2001:107114.
[5]VEKSLER O. Image segmentation by nested cuts[C]//Proc of IEEE CS Conf Computer Vision and Pattern Recognition.2000:339344.
[6]LI X， TIAN Z. Optimum cutbased clustering[J].Signal Processing，2007， 87(11):24912502.
[7]SHARON E， BRANDT A， BASRI R. Fast multiscale image segmentation[C]//Proc of IEEE Conference on Computer Vision and Pattern Recognition.2000:7077.
[8]SHARON E， BRANDT A， BASRI R. Segmentation and boundary detection using multiscale intensity measurements[C]//Proc of IEEE Conference on Computer Vision and Pattern Recognition.2001:469476.
[9]GOMORY R，HU T. Multiterminal network flows[J].Society for Industrial and Applied Mathematics Journals， 1961，9:551570.
