層次式圖切分快速分割算法

蔣建國， 張 婕， 詹 曙， 郭艷蓉

（合肥工業(yè)大學(xué)計(jì)算機(jī)與信息學(xué)院, 安徽 合肥 230009）

層次式圖切分快速分割算法

蔣建國， 張 婕， 詹 曙， 郭艷蓉

（合肥工業(yè)大學(xué)計(jì)算機(jī)與信息學(xué)院, 安徽 合肥 230009）

圖切分（Graph Cuts，GC）是近年來興起的基于圖論框架的圖像分割方法，該理論的新穎之處在于它的全局最優(yōu)性和結(jié)合多種知識的統(tǒng)一性。 但當(dāng)圖像較大時(shí)運(yùn)算非常耗時(shí)。該文提出了一種基于GC的層次式圖像分割方法。先在低分辨率中用GC以較低的分割代價(jià)獲取粗尺度的初始分割，再將結(jié)果輪廓映射回高分辨率圖像中并構(gòu)造出窄帶，進(jìn)而采用matting思想，在窄帶內(nèi)獲取精確分割。實(shí)驗(yàn)結(jié)果表明，本文方法在確保分割結(jié)果準(zhǔn)確性的同時(shí)，運(yùn)算速度大幅度提高。

信息處理技術(shù)；圖像分割；圖切分；多層次分割；摳圖

圖像分割是計(jì)算機(jī)視覺以及數(shù)字圖像處理領(lǐng)域的研究熱點(diǎn)和難點(diǎn)之一，由于此問題的重要性和困難性，從70年代起圖像分割問題一直吸引著國內(nèi)外研究人員為此努力， 至今已提出了上千個各種類型的分割算法[1]。傳統(tǒng)的圖像分割方法一般基于區(qū)域的信息或者基于邊界的信息。但是由于這些圖像分割方法只能利用圖像信息中的部分特征分割區(qū)域，因此必然帶有局限性和針對性。近年來，一種結(jié)合了基于區(qū)域和基于邊的圖像分割各自優(yōu)勢的Graph Cuts方法引起眾多學(xué)者的注意[2]。Graph Cuts方法最早是2001年由Boykov等人[3]提出的，該方法將圖論思想應(yīng)用于圖像分割，將組合優(yōu)化理論中的最大流最小割(Max flow-Min Cut)算法用于解決最小能量條件下的圖像分割問題，獲得全局最優(yōu)解，具有較強(qiáng)的魯棒性，集成了機(jī)器學(xué)習(xí)，非線性優(yōu)化和圖論等方面的優(yōu)勢，已經(jīng)廣泛地應(yīng)用于醫(yī)學(xué)領(lǐng)域[4]和自然圖像處理[5]等領(lǐng)域。

Boykov等人提出的Graph Cuts方法[6]，首先分別選定部分像素作為分割目標(biāo)和背景的種子點(diǎn)，然后將圖像中所有像素作為節(jié)點(diǎn)，以像素之間的相鄰關(guān)系作為邊，構(gòu)造一個圖，最后通過最大流最小割算法分割目標(biāo)。最大流最小割算法要窮舉所有從源到匯的增廣路徑[8]，當(dāng)圖像較大時(shí)，巨量的圖節(jié)點(diǎn)使得建立增廣路徑需搜索大量節(jié)點(diǎn)，造成效率低下。為了減少圖節(jié)點(diǎn)數(shù)量，Yin Li等人提出了Lazy Snapping[9]方法，首先利用分水嶺(watershed)方法將圖像預(yù)分割為很多小區(qū)域，然后將每個小區(qū)域作為一個節(jié)點(diǎn)，再利用Graph Cuts方法得到最后分割。雖然該方法將圖像預(yù)分割后構(gòu)造出來的圖節(jié)點(diǎn)數(shù)明顯減少，初始分割速度得到了很大的提高。但是，基于分水嶺法的預(yù)分割也要以一定的時(shí)間開銷為代價(jià)，同時(shí)，分水嶺預(yù)分割后的區(qū)域大小和數(shù)目都是不定的，這樣對于大量的圖像以及視頻序列來說，分割速度和內(nèi)存開銷也都是不確定的。而且這種方法初始分割效果并不理想，為了獲得精確的分割邊界，后期還需要用戶沿著目標(biāo)邊界更多的交互以修正，比較耗時(shí)。

本文以Graph Cuts算法框架為基礎(chǔ)，運(yùn)用多層次分析思想，對圖像進(jìn)行多尺度分解，建立金字塔式的多尺度數(shù)據(jù)結(jié)構(gòu)。在低分辨率通過Graph Cuts算法提取出目標(biāo)物體的邊緣后，通過線性插值方式將其投射到高分辨率圖像。由于待分割目標(biāo)物體內(nèi)部區(qū)域已經(jīng)確定，因而在高分辨率圖像主要進(jìn)行邊界細(xì)化，本文采用一種閉合求解的alpha matting算法在物體輪廓周圍的窄帶內(nèi)進(jìn)行細(xì)化分割，獲得了精確的邊緣。

本文把粗糙尺度的易分割性與精細(xì)尺度的精確性兩者有機(jī)的統(tǒng)一起來，使得算法效率顯著提高。通過實(shí)驗(yàn)表明，相比于直接Graph Cuts方法，本文算法不僅使得內(nèi)存開銷和運(yùn)算時(shí)間都成倍降低，而且能夠獲得更加精確的分割結(jié)果。

1 Graph Cuts

首先簡要介紹一下Graph Cuts的分割思想。對于一幅給定的圖像I，我們可用圖論的思想描述為G=，其中V表示頂點(diǎn)集，E為連接相鄰頂點(diǎn)的邊集（對于2D圖像來說，可以是4鄰域或者8鄰域，本文采用4鄰域系統(tǒng)），W為邊的權(quán)重。圖的頂點(diǎn)集V包括圖像I中的像素點(diǎn)和兩個特殊的頂點(diǎn)：源點(diǎn)s和匯點(diǎn)t。同樣，網(wǎng)絡(luò)圖中的邊也分為兩種：n-links和 t-links。n-links表示圖像中鄰接像素對之間的邊， t-links表示兩個特殊頂點(diǎn)s、t與圖像中各個像素之間的邊。如圖1所示，圖中連接邊的粗細(xì)代表權(quán)重大小。因此我們就可以把圖像分割問題轉(zhuǎn)換為求圖G中的最小割問題。

圖1 圖的構(gòu)造

上式中，E1是數(shù)據(jù)項(xiàng)代價(jià)，表示將每個像素點(diǎn)i標(biāo)記為ix的代價(jià)，即將每個像素點(diǎn)分配到前景或者背景的懲罰值，與 t-links有關(guān)。E2是平滑項(xiàng)代價(jià)，表示相鄰節(jié)點(diǎn)被分別標(biāo)記為xi與xj的代價(jià)，與n-links有關(guān)。

本文采用交互式圖像分割思想，先對一幅圖像通過不同的顏色分別標(biāo)記出部分前景點(diǎn)和背景點(diǎn)，作為前景種子點(diǎn)F和背景種子點(diǎn)B，圖中剩余未被標(biāo)記的區(qū)域稱為未知區(qū)域，記為U。為計(jì)算E1，我們先通過K均值算法分別將種子點(diǎn)F和B聚類，各聚類中心分別表示為｝與｛｝。然后，對于每個節(jié)點(diǎn)i，我們分別計(jì)算該點(diǎn)顏色C(i)到前景與背景每聚類中心的顏色距離的最小值，分別記為本文定義E1公式如下

對于平滑項(xiàng)代價(jià)E2，定義如下

Graph Cuts方法最顯著的特點(diǎn)之一就是具有全局尋優(yōu)的能力。在尋求最小代價(jià)切割問題的過程中，為了快速的計(jì)算最小能量，避免冗余且緩慢的組合計(jì)算方法，本文采用Boykov提出的基于增廣路徑的新最大流/最小割算法[11]。該算法與DINIC算法相似，都通過建立查找樹來尋找增廣路徑，但是有兩個顯著的區(qū)別：第一，建立兩個搜索樹，一個起于源s，另一個起于匯t；第二，重用而不是重新構(gòu)造搜索樹。

2 層次式Graph Cuts

Graph Cuts是基于圖論框架興起的分割方法，通過最大流最小割算法計(jì)算得到最小切割代價(jià)，具有全局最優(yōu)，不限制物體拓?fù)浣Y(jié)構(gòu)，可用于多維圖像等優(yōu)勢。但傳統(tǒng)的Graph Cuts方法對海量數(shù)據(jù)進(jìn)行分割時(shí)內(nèi)存開銷巨大、運(yùn)算時(shí)間也無法忍受。例如，Boykov的最大流算法需要24|V|+14|E|Bytes的內(nèi)存開銷來構(gòu)造圖，對5123的三維CT數(shù)據(jù)進(jìn)行分割時(shí)需要8GBytes的運(yùn)行內(nèi)存開銷，且需要近小時(shí)的處理時(shí)間。為此，本文提出了一種層次式分割方法，以減少Graph Cuts在分割大量數(shù)據(jù)時(shí)的內(nèi)存開銷和處理時(shí)間，算法流程如圖2所示。

圖2 本文算法流程圖

1） 在進(jìn)行分割之前，需要先通過用戶交互方式在原圖像I0指定部分區(qū)域分別作為前景和背景的種子點(diǎn)，用白色線段標(biāo)記前景F，黑色線段標(biāo)記背景B。然后對交互后圖像進(jìn)行高斯低通濾波，并以一定采樣因子進(jìn)行下采樣，建立高斯金字塔。下采樣獲得低分辨率圖像I1（包括交互指定區(qū)域）。

2） 在低分辨率圖像I1上進(jìn)行Graph Cuts分割。按照本文第2部分所描述方法對I1構(gòu)造對應(yīng)賦權(quán)圖G1=，利用最大流最小割算法計(jì)算得最小割，由此獲得I1上的分割結(jié)果。

3） 將低分辨率圖像的分割邊界位置記錄下來，并通過線性插值方式投影到高級分辨率圖像I0，得到原圖像待分割物體的模糊輪廓。

4） 在輪廓內(nèi)外各膨脹w像素寬度，形成一個包含帶分割物體邊界的窄帶作為不確定區(qū)域Tu，窄帶寬度為w2 ，并將該帶狀最內(nèi)一層設(shè)定為前景種子點(diǎn)，最外一層設(shè)定為背景種子點(diǎn)。這里w大小的選取根據(jù)下采樣因子的大小自適應(yīng)確定。

5） 最后在這個窄帶內(nèi)進(jìn)行邊界細(xì)化，以獲得精確的物體分割邊界。

初始快速分割結(jié)果映射到高分辨率圖像，必然會帶來分割結(jié)果不準(zhǔn)確，這里需要解決邊界粗糙問題。圖像上物體的邊界附近顏色是由前景和背景以一定系數(shù)α線性組合而成的，為了解決初始分割邊界粗糙問題，獲得真實(shí)自然的分割結(jié)果，本文采用alpha matting方法在高分辨率圖像對分割邊界進(jìn)行細(xì)化。現(xiàn)行的alpha matting有很多種方法，一般都是通過非線性迭代來同時(shí)計(jì)算出α，F(xiàn)和B，會花費(fèi)大量的計(jì)算時(shí)間，而且需要較多的用戶交互使得未知區(qū)域盡可能小，提取效果卻不是很好。本文采用一種求前景映射圖的閉式解決方案[7]，基于對圖像顏色的局部平滑性假設(shè)導(dǎo)出一個關(guān)于α的二次代價(jià)函數(shù)，然后通過解一個稀疏線性方程組（4）就可以獲得全局最優(yōu)解。該方法對于前景和背景顏色變化復(fù)雜的圖像，甚至自然圖像中的動物毛發(fā)，仍可得到精確的邊緣。

這里，L為一個N×N的矩陣，它的第(i,j)項(xiàng)為

對于本文要細(xì)化的物體邊界窄帶，構(gòu)造一個對角矩陣Ds（N×N，這里N為該窄帶內(nèi)像素?cái)?shù)目），對于已經(jīng)標(biāo)記為前景或者背景的像素，它對應(yīng)的對角元素為1，其余元素為0。另設(shè)一個向量bs(N×1)，對于標(biāo)記為白色像素點(diǎn)（前景點(diǎn)），其對應(yīng)的值為1；黑色像素點(diǎn)（背景點(diǎn)）以及其余未知像素部分，對應(yīng)為0。在式（4）的基礎(chǔ)上加上用戶約束，本文邊界細(xì)化只需在該窄帶內(nèi)計(jì)算下式即可

為了直觀清晰的了解本文算法思路，圖3通過一個分割實(shí)例給出了本文算法過程圖。圖3(a)為待分割圖像；(b)是用戶交互后圖像，白色標(biāo)記為前景種子點(diǎn)F，黑色標(biāo)記為背景種子點(diǎn)B；(c)是對標(biāo)記后圖像進(jìn)行下采樣后所得圖像，這里所選下采樣因子為2；(d)是對(c)所得低分辨率圖像進(jìn)行Graph Cuts分割結(jié)果；(e)為將低分辨率分割出的物體邊界映射到原圖像，并在邊界周圍膨脹一定像素寬度，形成一個待細(xì)化邊界窄帶；(f)為對該窄帶通過alpha matting進(jìn)行細(xì)化得到精確的分割結(jié)果。

圖3 本文算法分割過程實(shí)例圖

3 實(shí)驗(yàn)與分析

本文實(shí)驗(yàn)是在Matlab7.4平臺上實(shí)現(xiàn)，其中Graph Cuts的優(yōu)化算法部分是通過調(diào)用C程序?qū)崿F(xiàn)，所用計(jì)算機(jī)為 Inter(R) CoreTM2 CPU 2.0GHz，3GB內(nèi)存。下采樣因子的選擇可由用戶根據(jù)實(shí)際需要選定，對于一般圖像選擇下采樣因子θ為2即可，在實(shí)現(xiàn)快速分割的同時(shí)保證結(jié)果的精確度，對于較大的圖像（如實(shí)驗(yàn)中選用的1024×1024遙感圖像）可選擇下采樣率為4對圖像進(jìn)行分割。窄帶寬度選取經(jīng)驗(yàn)值θ2。

為了驗(yàn)證本文所提算法的有效性，對同一組灰度圖像用本文方法和Graph Cuts進(jìn)行實(shí)驗(yàn)，分別在分割效果、內(nèi)存開銷、時(shí)間消耗三方面進(jìn)行比較，如圖4所示。圖4中第1列為標(biāo)記后原圖像并給出圖像大?。坏?2列為直接使用 Graph Cuts分割結(jié)果，并給出內(nèi)存開銷和時(shí)間消耗；第3列為本文算法分割結(jié)果圖，以及所消耗的內(nèi)存和運(yùn)算時(shí)間。這里下采樣因子均為2。由對比實(shí)驗(yàn)結(jié)果可以看出，本文算法較直接采用 Graph Cuts方法，不僅在分割速度上提高近4倍（對于本文算法的分割時(shí)間計(jì)算包括邊界優(yōu)化所用時(shí)間），而且節(jié)省了約4倍的內(nèi)存開銷。與此同時(shí)，由于本文采用 matting方法對分割圖像的邊界進(jìn)行優(yōu)化，仔細(xì)對比第2列與第3列分割結(jié)果，可以看出，本文算法所獲得分割結(jié)果邊界更加精確。

圖4 本文算法與Graph Cuts分割對比圖

為了進(jìn)一步驗(yàn)證本文算法的優(yōu)勢，分別將本文算法與直接用Graph Cuts方法對32幅不同尺寸圖像進(jìn)行分割，統(tǒng)計(jì)兩種算法分割的時(shí)間代價(jià)和內(nèi)存開銷如圖5所示。

圖5 本文算法與Graph Cuts分割時(shí)間和內(nèi)存對比

圖6是對彩色自然圖像進(jìn)行分割的實(shí)例，進(jìn)一步說明了本文分割的效果，觀察圖6 ii（b）老虎的胡須部位的分割結(jié)果可以看出，即使對于毛發(fā)這類細(xì)小的物體，本文算法依然可以獲得精確的分割結(jié)果。

圖6 自然圖像分割實(shí)例

圖7是本文算法應(yīng)用于醫(yī)學(xué)圖像分割，圖8是對遙感圖像進(jìn)行分割，可以看出均獲得了較為滿意的結(jié)果。這類圖像含有較多噪聲，由此可以看出本文算法具有一定的抗噪性能。

圖7 醫(yī)學(xué)圖像分割實(shí)例

圖8 遙感圖像分割實(shí)例

4 結(jié) 論

本文提出了一種基于Graph Cuts的多層次圖像分割算法，先在低分辨率圖像上進(jìn)行Graph Cuts分割出初始目標(biāo)，然后將物體輪廓通過線性插值投影到高分辨率圖像，為了解決邊界粗糙問題，采用一種alpha matting對其進(jìn)行細(xì)化，從而得到精確的摳像結(jié)果。由于低分辨率圖像具有較小尺寸，Graph Cuts方法分割初始圖像的計(jì)算代價(jià)很低，而對高分辨率圖像只在邊界的帶狀區(qū)域進(jìn)行細(xì)化分割。通過與直接使用Graph Cuts方法進(jìn)行分割的對比實(shí)驗(yàn)結(jié)果表明，本文算法不僅成倍降低了運(yùn)算時(shí)間和內(nèi)存開銷，而且獲得了更加精確的分割結(jié)果。實(shí)驗(yàn)中將本文算法分別應(yīng)用于自然圖像，醫(yī)學(xué)圖像，遙感圖像，均取得了理想的分割結(jié)果。因此可以看出本文算法具有一定的實(shí)用價(jià)值。

[1]Nikhil R P, Sankar K P. A review on image segmentation techniques [J]. Pattern Recognition,1993, 26(9)：1277-1294.

[2]Qiu G, Yuen P C. Interactive imaging and vision——Ideas, algorithms and applications [J]. Pattern Recognition, 2010, 43：431-433.

[3]Boykov Y, Veksler O, Zabih R. Fast approximate energy minimization via graph cuts [J]. IEEE Transaction on PAMI, 2001, 23(11)：1222-1239.

[4]Chittajallu D R, Brunner G, Kurkure U, et al.Fuzzy-cuts：a knowledge driven graph-based method for medical image segmentation[C]//IEEE Conference on Computer Vision and Pattern Recognition, Miami,USA：2009：715 – 722.

[5]Jong S K, Kisang H. Color-texture segmentation using unsupervised graph cuts [J]. Pattern Recognition, 2009,(42)：735-750.

[6]Boykov Y, Funka-Lea G. Graph cuts and efficient N-D image segmentation [J]. International Journal of Comouter Vision, 2006, 70(2)：109-131.

[7]Levin A, Lischinski D, Weiss Y. A closed fom solution to natural image matting[C]//Proceedings of IEEE International Conference on Computer Vision and Pattern Recognition, New York, USA：2006：61-68.

[8]Ahuja R K, Magnanti T L. Network flows：theory,algorithms and application [M]. 北京：機(jī)械工業(yè)出版社, 2005：111-159.

[9]Li Yin, Sun Jian, Tang Chikeung, et al. Lazy snapping [C]//Proceedings of ACM SIGGRAPH,2004：303-308.

[10]Geman S, Geman D. Stochastic relaxation, gibbs distributions, and the bayesian restoration of images [J].Journal of Applied Statistics, 1993, 20(6)：25- 62.

[11] Boykov Y, Kolmogorov V. An experimental comparison of mincut/max-flow algorithms for energy minimization in vision [J]. IEEE Transactions on Pattern Analysis and Machine Interlligence, 2004,26(9)：1124-1137.

Multilevel graph cuts for fast image segmentation

Jiang Jianguo, Zhang Jie, Zhan Shu, Guo Yanrong
( School of Computer and Information, Hefei University of Technology, Hefei Anhui 230009, China )

Graph Cuts (GC) is a novel image segmentation method based on graph theory framework. The innovations of this theory lie in its global optimization and the unity of knowledge. However, if the image is large, computation will be very time-consuming. This paper presents a GC-based Hierarchical image segmentation method. First the initial segmentation is obtained through GC in the low-resolution with a very low computational cost. Then the contour is projected back to the high-resolution image to construct a narrow band. At last accurate segmentation in the narrow-band is achieved by using of matting arithmetic. Experimental results show that this method can ensure the accuracy of segmentation results with a significant increasing in computing speed.

information processing technology; image segmentation; graph cuts; multilevel segmentation; matting

TP 391

A

1003-0158(2012)01-0044-06

2010-04-01

安徽省2010高校省級自然科學(xué)研究重點(diǎn)資助項(xiàng)目（KJ2010A193）；教育部博士點(diǎn)基金資助項(xiàng)目（20060359004）；教育部留學(xué)歸國人員科研啟動基金資助項(xiàng)目（413117）

蔣建國（1955-），男，安徽廣德人，教授，主要研究方向?yàn)閿?shù)字圖像分析與處理、數(shù)字信號處理、分布式智能系統(tǒng)。