劉光明，孟祥偉，楊祥紅，程 煥

（1.海軍航空工程學(xué)院a.青島校區(qū)，山東青島266041；b.電子信息工程系；c.軍事教育訓(xùn)練系，山東煙臺264001；2.91967部隊(duì)，河北沙河054102）

Graph cuts方法[1]是一種快速優(yōu)化技術(shù)，有效解決計(jì)算機(jī)視覺的低層次問題，如表面重構(gòu)、分割、去噪等問題。其優(yōu)點(diǎn)是迭代計(jì)算的高效性和能得到全局最優(yōu)解。其缺點(diǎn)在于精度限于像素精度和只能用各項(xiàng)異性算子AO（Anisotropic Operators），不能用各項(xiàng)同性算子IO（Isotropic Operators）。Graph cuts方法是計(jì)算1個(gè)圖（Graph）中的最大流的方法，等價(jià)于最小割。在圖像處理問題中，圖是指像素網(wǎng)絡(luò)，而割（Cut）表示輪廓。圖像去噪、圖像分割等問題的能量全局最優(yōu)解都可以通過求解圖的最大流或最小割問題來準(zhǔn)確地實(shí)現(xiàn)。Graph cuts方法定義在最大后驗(yàn)-馬爾科夫隨機(jī)場框架，是一種比模擬退火快的離散優(yōu)化技術(shù)。近年來，國際上用Graph cuts方法進(jìn)行圖像分割處理的研究也很深入，發(fā)表了大量的研究成果。本文對Ayed等人[2]提出的SAR圖像水平集分割模型采用Graph cuts方法優(yōu)化處理，充分利用Graph cuts方法的優(yōu)點(diǎn)，只須幾次迭代算法就可收斂，表明了算法的有效性。

1 最大流/最小割模型

在1個(gè)有向圖中，只有出去的邊沒有進(jìn)來邊的節(jié)點(diǎn)叫做源節(jié)點(diǎn)s（source），只有進(jìn)來的邊沒有出去的邊的節(jié)點(diǎn)叫做匯節(jié)點(diǎn)t（sink），其他的節(jié)點(diǎn)進(jìn)來的邊和出去的邊應(yīng)該是平衡的，見圖1所示。邊上有加權(quán)值，假設(shè)對于一個(gè)交通圖來說，可以認(rèn)為邊上的權(quán)重為一條道路上的最大流量。對于圖中任意2個(gè)節(jié)點(diǎn)來說，它們之間可以存在很多路徑，每條路徑上可以承載的最大流量取決于這條路徑上權(quán)重最小的那條邊所能承載的流量，而所有路徑上所能承載流量之和就是這2個(gè)節(jié)點(diǎn)之間能通過的最大流。任一網(wǎng)絡(luò)圖（Graph）中，最大流的流量=最小割集的割量。

圖1 有向圖網(wǎng)絡(luò)Fig.1 Directed graph

假設(shè)G=(V,E)是1個(gè)包含1個(gè)頂點(diǎn)集v ∈V 和1個(gè)邊緣集e ∈E ?V×V的圖。V 包括離散圖像的所有節(jié)點(diǎn)和2個(gè)終端，即1個(gè)源節(jié)點(diǎn)s 和1個(gè)匯節(jié)點(diǎn)t，其余均為中間節(jié)點(diǎn)。E 包括圖像節(jié)點(diǎn)鄰域系統(tǒng)的所有連接（如4-連接或8-連接，見圖2所示），類似源節(jié)點(diǎn)s 或者匯節(jié)點(diǎn)t 與每個(gè)圖像節(jié)點(diǎn)u ∈V/{s,t}的連接。對E 中的每條邊均有權(quán)w(eij)＞0（簡記為wij，稱為邊容量），則稱這樣的賦權(quán)有向圖G為容量網(wǎng)絡(luò)，記為G=(V,E,w)，通過G 中邊eij的流量pij，可稱為邊eij的流量。所有邊上流量的集合p={pij}可稱為該網(wǎng)絡(luò)G的1個(gè)流。

圖2 圖像鄰域Fig.2 Image neighborhood

對于1個(gè)圖中的2個(gè)節(jié)點(diǎn)來說，如果把圖中的一些邊去掉，剛好讓它們之間無法連通，這些被去掉的邊組成的集合就叫做割，最小割就是指所有割中權(quán)重之和最小的1個(gè)割。

最大流/最小割定理（max flow/min cut theory）：對于任意1個(gè)只有1個(gè)源點(diǎn)和1個(gè)匯點(diǎn)的網(wǎng)絡(luò)圖來說，從源點(diǎn)到匯點(diǎn)的最大流等于最小割，見圖3所示。

圖3 流圖Fig.3 Flow configurations

1）連續(xù)最大流模型[3]。

式（1）中：Ω為圖像域；div(?)是散度符號；ps(x)是從源點(diǎn)s 到點(diǎn)x的源流量；pt(x)是從匯點(diǎn)t 到點(diǎn)x的匯流量；p(x)是空間流量；Cs(x)、Ct(x) 和C(x)分別是與ps(x)、pt(x)和p(x)對應(yīng)的約束能量。

引入函數(shù)r（對偶變量），式（1）可以轉(zhuǎn)化為與其等價(jià)的Prime-dual模型[4-5]：

2）連續(xù)最小割模型[4-5]。

對于1個(gè)圖，1個(gè)“s-t”割分割V為2個(gè)子集，即：

式（3）中：Vs包含源點(diǎn)s；Vt包含匯點(diǎn)t。

令C(e)≥0為與每個(gè)邊緣e ∈E 有關(guān)的值。每個(gè)s-t 割的能量是所有邊緣值C(e)之和，其中e ∈Est?E連接2個(gè)節(jié)點(diǎn)，1個(gè)在Vs中，1個(gè)在Vt中。最小割在于找到最小能量“s-t”割，即：

2 基于Graph cuts的活動輪廓模型

Graph cuts方法可以計(jì)算如下形式離散能量的精確解：

式（5）是一類一階各向異性離散二進(jìn)制能量，其中，θ ＞0 和μ ＞0是系數(shù)；表示長度，表示面積。對任意(s,t)，一個(gè)次模（submodular，即最優(yōu)化條件）能量滿足下式：

式（6）表明正則化項(xiàng)R是兩兩相互作用（3個(gè)節(jié)點(diǎn)間不允許有相互作用）的。

Graph cuts方法可近似求得式（7）表示的連續(xù)幾何問題的全局解為

式中：C為邊緣曲線；∫?Cθds表示周長；∫CDinsidedx 和∫ΩCDoutsidedx分別表示內(nèi)部、外部面積。

式（7）的近似式為

可以看出式（8）滿足次模條件。因此，Graph cuts方法可以確保取得全局最優(yōu)解。

3 提出的新模型

Ayed等人提出模型[2]的能量泛函可以用變分水平集[6-10]表示為

式（9）中：?是水平集函數(shù)[6]；M1=H(?)；M2=1-H(?)；ε是較小的整數(shù)；μ ＞0。

由于水平集演化方程的復(fù)雜性，還會造成計(jì)算效率較低，很難滿足實(shí)時(shí)性要求。Graph cuts方法是一種快速優(yōu)化技術(shù)，其優(yōu)點(diǎn)是迭代計(jì)算的高效性和能得到全局最優(yōu)解。下面基于Graph cuts方法對方程（9）進(jìn)行變換，提出圖像分割新的模型。

將圖中的節(jié)點(diǎn)與圖像像素相聯(lián)系，像素集的積分可以被表示為一個(gè)N×1的鏈向量，其定義為：

定義：

對于每個(gè)頂點(diǎn)vk和邊緣eij，其中eij可以任意分配方向。式（9）在圖（Graph）上的對應(yīng)項(xiàng)可以簡單表示為：

對式（12）中含C1和C2的部分分別寫為：

對式（13）關(guān)于C1和C2分別求偏導(dǎo)數(shù)，可得到：

用求和形式，式（12）可寫成一個(gè)簡化的最大流/最小割計(jì)算問題：

將本文提出的新模型簡記作GC_Ayed。

算法步驟總結(jié)如下：

1）初始化C1，C2和r；

2）求式（14）得到C1，C2；

3）求式（15）中的最大流/最小割得到最有輪廓r；

4）重復(fù)步驟2）～3）直到輪廓位置保持不變?yōu)橹埂?/p>

4 數(shù)值實(shí)驗(yàn)與分析

采用2幅實(shí)測Envisat SAR圖像來驗(yàn)證和分析提出模型的分割性能，見圖4。2幅實(shí)測SAR圖像的尺寸分別為179×205 和250×250，灰度范圍為0～255。本文實(shí)驗(yàn)是在CPU為AMD 1.8 GHz、內(nèi)存為1 GB的硬件環(huán)境以及windows XP SP2的軟件環(huán)境下，采用Matlab 編程實(shí)現(xiàn)。將本文提出的GC_Ayed模型、與Ayed模型進(jìn)行比較，驗(yàn)證本文提出模型的有效性。

圖4 實(shí)測SAR圖像Fig.4 Real SAR images

對于SAR圖像，本文采用一種區(qū)域內(nèi)部均勻性度量的方法來評估。根據(jù)圖像分割的定義，分割后圖像每個(gè)區(qū)域內(nèi)部應(yīng)該是均勻的，不同區(qū)域之間存在較大的差異，所以區(qū)域內(nèi)部的均勻程度表征了圖像分割的質(zhì)量。定義分割精度度量[11]如下：

式（16）中：Ai為圖像中的不同分割區(qū)域；C為歸一化系數(shù)；f(x)為圖像中點(diǎn)x 處的灰度值；ni為區(qū)域Ai中的像素個(gè)數(shù)；pp值越接近于1，表明分割圖像內(nèi)部各區(qū)域越均勻，圖像的分割質(zhì)量越好。

從圖5可看出，本文提出的GC_Ayed模型能準(zhǔn)確地分割SAR圖像1中的水域，而Ayed模型不能完整地分割出水域邊緣輪廓。從圖6可以看出，GC_Ayed模型也能準(zhǔn)確地提取SAR圖像2中的機(jī)場道路邊緣，而Ayed模型分割效果較差。從表1、2可看出，GC_Ayed模型所需運(yùn)行時(shí)間大約是基于水平集的活動輪廓模型所需時(shí)間的一半，分割精度也得到了較大的提高。

圖5 SAR圖像1的分割結(jié)果Fig.5 Segmentation results of SAR image 1

圖6 SAR圖像2的分割結(jié)果Fig.6 Segmentation results of SAR image 2

表1 運(yùn)行時(shí)間和分割精度的比較（SAR圖像1）Tab.1 Comparsion of running time and segmentation accuracy for SAR image 1

表2 運(yùn)行時(shí)間和分割精度的比較（SAR圖像2）Tab.2 Comparsion of running time and segmentation accuracy for SAR image 2

5 結(jié)論

本文利用Graph cuts方法，將基于活動輪廓模型和水平集方法的SAR圖像分割模型轉(zhuǎn)化成最大流/最小割問題。通過實(shí)測SAR圖像的分割實(shí)驗(yàn)，提出的新模型所需運(yùn)行時(shí)間大約是基于水平集的活動輪廓模型所需時(shí)間的一半，分割精度也得到了較大的提高。

[1]BOYKOV Y，F(xiàn)UNKA-LEA G.Graph cuts and efcient nd image segmentation[J].International Journal of Computer Vision，2006，70（2）：109-131.

[2]BEN AYED I，MITICHE A，BELHADJ Z.Multiregion level set partitioning of synthetic aperture radar Images[J].IEEE Transactions on Pattern Analysis and Machine Intelligence，2005，27（5）：793-800.

[3]ZHU MINGQIANG，CHAN T F.An efficient prime dual hybrid gradient algorithm for total variation image[R].Los Angeles：University of California at Los Angeles，2008：1-29.

[4]YUAN JING，BAE EGIL，TAI XUECHENG，et al.A study on continuous max-flow and min-cut approache[C]//Computer Vision and Pattern Recognition.San Francisco，2010：1-22.

[5]PUNITHAKUMAR K，YUAN JING，BEN AYED I，et al.A convex max-flow approach to distribution based figure-ground separation[J].Journal on Imaging Sciences，2012，5（4）：1333-1354.

[6]STANLEY OSHER，JAMES A SETHIAN.Fronts propagating with curvature-dependent speed algorithms based on hamilton-Jacobi formulations[J].Journal of Computational Physics，1988，79（1）：12-49.

[7]MUMFORD D，SHAH J.Optimal approximation by piecewise smooth functions and associated variational problems[J].Communications on Pure and Applied Mathematics，1989，42（5）：577-685.

[8]TONY F CHAN，LUMINITA A VESE.Active contours without edges[J].IEEE Transactions on Image Processing，2001，10（2）：266-277.

[9]LUMINITA A VESE，TONY F CHAN.A multiphase level set framework for image segmentation[J].International Journal of Computer Vision，2002，50（3）：271-293.

[10]CHUNMING LI，CHIU-YEN KAO，JOHN C GORE，et al.Minimization of region-scalable fitting energy for image segmentation[J].IEEE Transactions on Image Processing，2008，17（10）：1940-1949.

[11]ROSS T D，MOSSING J C.The MSTAR evalution methodology[C]//Proceeding of SPIE.1999：705-713.