基于圖論Ｇｏｍｏｒｙ－Ｈｕ算法的快速圖像分割

摘 要：

GomoryHu算法是圖論中的經(jīng)典算法，用于尋找圖的最小流割等價(jià)樹(shù)，具有最優(yōu)解，但是該算法很難處理較大的圖像，而且傾向于分割出孤立點(diǎn)集。為此，給出了孤立點(diǎn)的判定方法，并提出一種基于GomoryHu算法的圖像分割方法。該算法首先通過(guò)快速聚類減少圖中頂點(diǎn)數(shù)目，然后構(gòu)造新的賦權(quán)圖，并應(yīng)用GomoryHu算法對(duì)圖進(jìn)行最優(yōu)劃分，得到分割結(jié)果。提出的算法對(duì)多幅自然圖像進(jìn)行了分割實(shí)驗(yàn)，平均分割時(shí)間在3 s內(nèi)。實(shí)驗(yàn)結(jié)果證明了算法的有效性和快速性。

關(guān)鍵詞：圖像分割； GomoryHu算法； 聚類； 圖論

中圖分類號(hào)：TP391 文獻(xiàn)標(biāo)志碼：A

文章編號(hào)：10013695(2008)09286503

Fast image segmentation based on GomoryHu algorithm

LIU Bingtao1， TIAN Zheng1，2， ZHOU Qiangfeng1， LI Xiaobin1

（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:

GomoryHu 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 GomoryHu algorithm. This algorithm first used the fast clustering algorithm to reduce the number of vertices ，then used the improved GomoryHu 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; GomoryHu algorithm; clustering; graph theory

0 引言

圖像分割是圖像理解的基礎(chǔ)，在計(jì)算機(jī)視覺(jué)領(lǐng)域占有很重要的地位。基于圖的圖像分割方法能夠很好地把握?qǐng)D像的全局特征，而且更加符合人類的視覺(jué)系統(tǒng)，因此這種方法發(fā)展很快，尤其是基于圖割的方法。

從1993年Wu等人^[1]首先將圖論中割的方法用于圖像分割開(kāi)始，不斷有新的模型提出。特別是1997年Shi與Malik提出標(biāo)準(zhǔn)割模型^[2，3]以后，各種割模型相繼提出，主要有最大最小割模型^[4]、網(wǎng)巢割模型^[5]、最優(yōu)割模型^[6]等。目前的研究按照是否具有理論最優(yōu)解而被分為兩支：a)可以從理論上得到最優(yōu)解；b)NP難問(wèn)題，無(wú)法從理論上得到最優(yōu)解，通過(guò)算法逼近得到次優(yōu)解。可見(jiàn)尋找具有理論最優(yōu)解的分割方法是非常重要的，也是眾多研究者所希望找到的。Wu等人提出的最小割模型屬于第一類，它可以獲得最優(yōu)解，但是最小割模型傾向于分割出孤立點(diǎn)集^[2，3]，標(biāo)準(zhǔn)割模型雖然可以避免這個(gè)缺點(diǎn)，但它卻傾向于將圖像分成兩個(gè)大小相等的塊^[5]，并且與最小割模型一樣，標(biāo)準(zhǔn)割算法相當(dāng)耗時(shí)。算法耗時(shí)也幾乎成為割模型方法不可逾越的障礙，其他幾種割模型方法同樣受到這個(gè)問(wèn)題的困擾。很多模型均可以得到相當(dāng)好的分割結(jié)果，但是算法運(yùn)行時(shí)間很長(zhǎng)，無(wú)法達(dá)到實(shí)時(shí)性的要求。Sharon等人在文獻(xiàn)[7，8]中提出了一種多尺度方法，能夠快速、有效地進(jìn)行圖像分割，基本滿足算法實(shí)時(shí)性的要求，但是其無(wú)法得到理論最優(yōu)解。因此研究同時(shí)具有理論最優(yōu)解和實(shí)時(shí)處理的方法是非常有意義的工作。為此，本文從GomoryHu算法入手，研究可以解決上述問(wèn)題的方法。

GomoryHu算法是圖論中的經(jīng)典算法，用于求解圖的最小流割等價(jià)樹(shù)，具有理論最優(yōu)解的特性。它只需要求解n-1（n是圖的頂點(diǎn)數(shù)）次最大流就能夠最優(yōu)地將圖劃分為k個(gè)子圖。在基于圖的圖像分割中，對(duì)于適當(dāng)?shù)馁x權(quán)圖（大約2 000個(gè)頂點(diǎn)），通過(guò)GomoryHu算法構(gòu)造圖的最小流割等價(jià)樹(shù)，并對(duì)圖的流割等價(jià)樹(shù)去邊，從而得到圖的最優(yōu)化分割。然而對(duì)于較大的圖來(lái)說(shuō)其計(jì)算量將變得很大，基本無(wú)法實(shí)現(xiàn)。為了克服這個(gè)困難，最好的辦法是能夠找到一種減少圖頂點(diǎn)的方法，從而能夠利用GomoryHu算法構(gòu)造割等價(jià)樹(shù)，進(jìn)行最優(yōu)分割^[1]。

為了解決這些問(wèn)題，本文提出一種新的基于GomoryHu算法的圖像分割方法，不僅可以得到理論最優(yōu)解，而且能夠達(dá)到實(shí)時(shí)性的要求。該算法首先對(duì)原圖進(jìn)行快速聚類來(lái)減少圖中的頂點(diǎn)數(shù)目。當(dāng)圖的頂點(diǎn)達(dá)到算法要求時(shí)，則利用GomoryHu算法對(duì)圖進(jìn)行最優(yōu)劃分，再映射回圖像，得到對(duì)原圖像的最優(yōu)分割。

1 GomoryHu割樹(shù)

對(duì)于一個(gè)無(wú)向賦權(quán)圖來(lái)說(shuō)，可以構(gòu)造一個(gè)具有如下性質(zhì)的樹(shù)^[9]：

a) 樹(shù)中的頂點(diǎn)就是原圖中的頂點(diǎn)；

b) 樹(shù)中的每一條邊均有一個(gè)非負(fù)的權(quán)wij；

c) 對(duì)于樹(shù)中的頂點(diǎn)s和t，有一條惟一的路徑，令邊eij為這條路徑中權(quán)值最小的邊，那么頂點(diǎn)s與t之間的最小割值為wij，這樣的最小割可以通過(guò)去掉邊eij得到。

這樣的樹(shù)就稱做GomoryHu割樹(shù)，通過(guò)去邊就可以得到對(duì)原圖的最優(yōu)劃分。

筆者可以通過(guò)GomoryHu算法構(gòu)造割樹(shù)，它的主要原理^[9]是根據(jù)最大流最小割定理，利用EdmondsKarp算法求解任意相鄰頂點(diǎn)間的最大流（即最小割），從而得到與圖對(duì)應(yīng)的最小流割等價(jià)樹(shù)（GomoryHu割樹(shù)），即樹(shù)上的每條邊的權(quán)值均是兩個(gè)端點(diǎn)的最小割值。對(duì)最小流割等價(jià)樹(shù)的每條邊按照權(quán)值由小到大的順序進(jìn)行去邊，即可得到圖的子圖，當(dāng)子圖數(shù)目達(dá)到k時(shí)停止。此時(shí)即可得到對(duì)原圖的k個(gè)最優(yōu)劃分，映射回原圖像則可得到相應(yīng)圖像的k個(gè)塊。

GomoryHu算法首先任意選擇兩個(gè)頂點(diǎn)s和t，利用EdmondsKarp算法計(jì)算其最小割值和割邊，去掉最小割邊后，原圖被分為兩個(gè)子圖，然后分別對(duì)這兩個(gè)子圖重復(fù)上述過(guò)程。最終得到原圖的最小流割等價(jià)樹(shù)。

GomoryHu算法的目的是通過(guò)構(gòu)造GomoryHu割樹(shù)，然后按照割值大小依次去掉割值較小的邊，這樣做可以使得類內(nèi)的割值最大，也就是相似度最大，而類間的相似度最小。這也充分符合圖像分割的原則，就是使得塊內(nèi)相似度最大，塊間相似度最小。從理論上考慮這也是最優(yōu)的分割方法，但是也正因如此，這種算法很容易將圖像中的孤立點(diǎn)分離出來(lái)，如圖1所示。圖1（b）是根據(jù)GomoryHu算法構(gòu)造的割樹(shù)，按照割值由小到大去邊，那么頂點(diǎn)d與f之間的邊首先去掉，其次是頂點(diǎn)f與e之間的邊。如果圖像中存在孤立點(diǎn)i，它與其他頂點(diǎn)的割值必然很小，那么它將被單獨(dú)分割出來(lái)，這樣就會(huì)影響圖像的整體分割效果。

為了解決這個(gè)問(wèn)題，首先對(duì)原圖進(jìn)行聚類，這樣做不僅可以減少頂點(diǎn)數(shù)目以達(dá)到GomoryHu算法的要求，還可以通過(guò)聚類盡量減少孤立點(diǎn)的存在，讓孤立點(diǎn)聚合到相近的類中，這樣就會(huì)避免分割出孤立點(diǎn)。

如果一個(gè)頂點(diǎn)與其所有鄰接頂點(diǎn)的權(quán)值之和小于其鄰接頂點(diǎn)之間權(quán)值和的某一個(gè)比例，那么這個(gè)頂點(diǎn)就是孤立點(diǎn)。下面給出孤立點(diǎn)的定義：

∑j∈Vwij≤β∑j∈V，k∈Vwjk(1)

其中：j是頂點(diǎn)i的鄰域頂點(diǎn)；V是頂點(diǎn)i的鄰域頂點(diǎn)集合。

2 基于圖聚類的GomoryHu算法

首先根據(jù)原圖像構(gòu)造無(wú)向賦權(quán)圖，圖中的頂點(diǎn)代表圖像中的像素。設(shè)無(wú)向賦權(quán)圖為=G(V，E，W)。其中:V=(v1，v2，…，vn)是頂點(diǎn)集合；E={eij=(vi，vj)}是邊集合；eij表示該邊連接頂點(diǎn)vi與vj。邊權(quán)矩陣W=(wi，j)中的元素wij反映了頂點(diǎn)i和j之間的相似程度。當(dāng)頂點(diǎn)i與j很相似時(shí)，wij較大；當(dāng)i與j不相似時(shí)，w

其中：I(xiàn)i代表頂點(diǎn)i的亮度；σ1、σ2代表尺度參數(shù)，根據(jù)經(jīng)驗(yàn)選取；Dij代表頂點(diǎn)i與j之間的歐式距離。

為了加快算法速度，定義原始圖為八連通無(wú)向賦權(quán)圖，經(jīng)過(guò)第一次聚類后，需要重新定義賦權(quán)圖并應(yīng)用GomoryHu算法。這時(shí)需要對(duì)每一類內(nèi)的頂點(diǎn)進(jìn)行頂點(diǎn)收縮，合并為一個(gè)新的頂點(diǎn)，該頂點(diǎn)繼承原類內(nèi)頂點(diǎn)的鄰接關(guān)系，如圖2所示。圖2(a)中的頂點(diǎn)1、2、3同屬于類A，頂點(diǎn)4、5、6同屬于類B，頂點(diǎn)7、8、9同屬于類C。經(jīng)過(guò)頂點(diǎn)收縮后得到圖2(b)，頂點(diǎn)A 代表類A，頂點(diǎn)B代表類B，頂點(diǎn)C代表類C。

下面定義頂點(diǎn)收縮后新頂點(diǎn)的亮度值為

其中：Vi代表第i個(gè)類的頂點(diǎn)總數(shù)。由于此時(shí)圖中頂點(diǎn)數(shù)目不是很多，為了保證計(jì)算的精度，定義此圖為全連通無(wú)向賦權(quán)圖，相似度函數(shù)定義為

聚類的最重要原則是使得類內(nèi)相似度最大，類間相似度最小。為此，本文定義聚類原則如下：

其中：頂點(diǎn)i是類Vi的代表元素；S是代表元素集合；vol為圖的頂點(diǎn)總數(shù)；頂點(diǎn)l是頂點(diǎn)j的鄰接頂點(diǎn)；α是頂點(diǎn)j與其周圍鄰接頂點(diǎn)權(quán)值之和的一個(gè)比例權(quán)重，按照經(jīng)驗(yàn)一般選取為0.1。如果滿足式(5)則認(rèn)為頂點(diǎn)i和j屬于同一類，不滿足則不屬于同類，即頂點(diǎn)j代表另一類，令j∈S，vol=vol-1。為了加速算法，筆者采用并行聚類方法，只需要遍歷一次就可以使得每一個(gè)頂點(diǎn)找到所屬的類。

該算法的具體步驟如下：

a)令圖中第一個(gè)頂點(diǎn)i為類Vclass的代表元素，令vol=vol-1。

b)遍歷G中的頂點(diǎn)j，如果滿足式（5），則令j∈Vclass，Vclass=Vclass+{j}，vol=vol-1；如果不滿足，則根據(jù)孤立點(diǎn)定義式（1）判斷頂點(diǎn)j是否為孤立點(diǎn)。如果是，則j∈Vclass，Vclass=Vclass+{j}，vol=vol-1，轉(zhuǎn)向d)；如果不是孤立點(diǎn)，則轉(zhuǎn)向c)。

c)令class=class+1，j為類Vclass的代表元素，且j∈S，S=S+{j}，vol=vol-1。

d) 判斷vol是否為空，如果為空，則圖中的所有元素均已處理完畢，并根據(jù)圖2所述規(guī)則重新構(gòu)造賦權(quán)圖，轉(zhuǎn)到e)；否則，轉(zhuǎn)到c)繼續(xù)對(duì)未處理的元素進(jìn)行聚類。

e) 對(duì)新的賦權(quán)圖G，應(yīng)用GomoryHu算法得到對(duì)圖的最優(yōu)k個(gè)劃分。

f)映射回原圖像得到最優(yōu)分割。

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

本算法在P4 2.6 GHz CO、CPU計(jì)算機(jī)Visual C++6.0平臺(tái)上實(shí)現(xiàn)。為了驗(yàn)證其有效性和快速性，對(duì)多幅自然圖像進(jìn)行了實(shí)驗(yàn)，平均分割時(shí)間在3 s以內(nèi)，基本滿足了實(shí)時(shí)性的要求。為了能夠更好地說(shuō)明本算法的流程，圖3給出了本算法分步得到的結(jié)果。圖3(b)是對(duì)原圖像進(jìn)行快速聚類后得到的結(jié)果，在這一過(guò)程中，圖像被分為很多類，接下來(lái)以每一類為一個(gè)頂點(diǎn)，構(gòu)造新的賦權(quán)圖，并利用GomoryHu算法尋找它的流割等價(jià)樹(shù)，去邊后得到第二步分割（圖3(c)）。

圖4給出了本文方法分別與SWA算法、標(biāo)準(zhǔn)割算法的分割結(jié)果比較。三幅自然圖像(灰度圖像)大小分別為256×170、300×200和256×170，本文方法分割時(shí)的尺度參數(shù)δ分別為30、30、18。從算法運(yùn)行時(shí)間來(lái)比較，標(biāo)準(zhǔn)割算法耗時(shí)最長(zhǎng)，分別為72、38和90 s；SWA算法與本文方法耗時(shí)基本相當(dāng)，均在3 s左右。分割質(zhì)量從視覺(jué)角度來(lái)看，本文方法要明顯優(yōu)于其他兩種方法，尤其是第一幅圖，分割結(jié)果相當(dāng)精確。對(duì)于第二幅圖，三種方法的結(jié)果相當(dāng)，但是如果仔細(xì)觀察可以發(fā)現(xiàn)，本文方法更好地保留了目標(biāo)的細(xì)節(jié)。第三幅圖，本文方法分割結(jié)果也相當(dāng)精確。綜上所述，本文方法不僅處理時(shí)間短，而且分割結(jié)果邊緣更精確，更符合人類的視覺(jué)特性，分割結(jié)果相對(duì)較好。

4 結(jié)束語(yǔ)

研究具有理論最優(yōu)解的方法在基于圖論的圖像分割中是非常有意義的工作。為此本文給出了利用GomoryHu算法應(yīng)用于圖像分割的一種新方法，它充分結(jié)合了聚類和GomoryHu算法的優(yōu)點(diǎn)，使該算法不僅具有實(shí)時(shí)性，而且繼承了GomoryHu算法的最優(yōu)分割特性。實(shí)驗(yàn)結(jié)果也充分說(shuō)明了本算法的有效性和快速性。然而SAR圖像與光學(xué)圖像有著很大的區(qū)別，同時(shí)也具有更重要的價(jià)值，所以將本算法應(yīng)用于SAR圖像將是很有意義的，這也是筆者正在研究的工作。

參考文獻(xiàn)：

[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):11011113.

[2]SHI J， MALIK J. Normalized cuts and image segmentation[C]//Proc ofIEEE Conference on Computer Vision and Pattern Recognition.1997:731737.

[3]SHI J， MALIK J. Normalized cuts and image segmentation[J]. IEEE Trans on Pattern Analysis and Machine Intelligence. 2000，22(8): 888905.

[4]DING C， HE X， ZHA H， et al. A minmax cut algorithm for graph partitioning and data clustering[C]//Proc of IEEE Intl Conf on Data Mining.2001:107114.

[5]VEKSLER O. Image segmentation by nested cuts[C]//Proc of IEEE CS Conf Computer Vision and Pattern Recognition.2000:339344.

[6]LI X， TIAN Z. Optimum cutbased clustering[J].Signal Processing，2007， 87(11):24912502.

[7]SHARON E， BRANDT A， BASRI R. Fast multiscale image segmentation[C]//Proc of IEEE Conference on Computer Vision and Pattern Recognition.2000:7077.

[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:469476.

[9]GOMORY R，HU T. Multiterminal network flows[J].Society for Industrial and Applied Mathematics Journals， 1961，9:551570.