辛月蘭

0 引言

近年來(lái)，圖割技術(shù)作為一種魯棒的能量最小化方法，得到越來(lái)越多的重視，通過(guò)對(duì)圖像分割的推廣，圖割技術(shù)已經(jīng)應(yīng)用在整個(gè)計(jì)算機(jī)視覺(jué)領(lǐng)域。

1 圖割基本理論

1.1 圖割基本理論的概述

設(shè)一個(gè)無(wú)向圖為G = 〈V，E〉，V 為圖中節(jié)點(diǎn)的集合，E 為連接節(jié)點(diǎn)的邊集。通常，節(jié)點(diǎn)代表了像素、體元或其它特征，而圖中也包含一些附加的特殊節(jié)點(diǎn)，稱(chēng)為終端節(jié)點(diǎn)。在立體視覺(jué)應(yīng)用的能量最小化方法中，圖的結(jié)構(gòu)有很多種形式，但大多數(shù)都是基于規(guī)則的二維或三維網(wǎng)格圖。

一個(gè)具有兩個(gè)終端節(jié)點(diǎn)的二維圖，定義V = { s，t} ∪P為無(wú)向圖 G 中的節(jié)點(diǎn)，包含了兩個(gè)表示“目標(biāo)”和“背景”標(biāo)簽的特定終端節(jié)點(diǎn)，分別為源點(diǎn)s 和匯點(diǎn)t，以及一系列非終端節(jié)點(diǎn)的集合P。圖中每一邊被賦與一個(gè)非負(fù)的容量( 或稱(chēng)權(quán)值) ，邊緣代價(jià)通過(guò)邊緣厚度（線的粗細(xì)）表現(xiàn)出來(lái)。圖中的邊可以被分為兩類(lèi): n-links 和t-links。連接非終端節(jié)點(diǎn)的邊稱(chēng)為n-links; 連接像素到終端節(jié)點(diǎn)的邊稱(chēng)為t-links。

Boykov[1,2]的交互式分割的具體過(guò)程，如圖1所示：

圖1 二維圖網(wǎng)絡(luò)（基于圖割理論進(jìn)行圖像分割）

1.2 分割能量

其中公式（2）

這里負(fù)對(duì)數(shù)是通過(guò)MAP-MRF構(gòu)想產(chǎn)生的公式（3）

B(A)項(xiàng)包含分割A(yù)的邊界性能，系數(shù)Bp,q≥0應(yīng)該看作p和q之間不連續(xù)的一個(gè)處罰，

如圖 1（a）所示，“O”為交互設(shè)置的目標(biāo)種子點(diǎn)，“B”為交互設(shè)置的背景種子點(diǎn)；圖1（b）是根據(jù)（1）式建立的能量函數(shù)所構(gòu)造的網(wǎng)絡(luò)圖，網(wǎng)絡(luò)圖的權(quán)值，如表1所示：

表1 邊權(quán)值定義

圖1（c）是使用最大流/最小割算法對(duì)圖1（b）建立的網(wǎng)絡(luò)圖進(jìn)行的切割；圖 1（d）是根據(jù)圖割獲得的圖像分割結(jié)果，相當(dāng)于二元分區(qū)將圖像劃分為“目標(biāo)”和“背景”部分。

1.3 圖割的能量最小化

根據(jù)能量?jī)?yōu)化的觀點(diǎn)求解最小圖割，是目前圖割中的主要求解方法。該方法需要根據(jù)圖像的特征信息，建立合適的能量函數(shù)，然后根據(jù)能量函數(shù)，建立圖論中的網(wǎng)絡(luò)圖，通過(guò)對(duì)網(wǎng)絡(luò)圖采用最大流/最小割算法，獲得分割的結(jié)果。

從理論上講，基于圖割的能量函數(shù)最小化方法，可以提供能量函數(shù)的全局最小化；也就是說(shuō)，即使產(chǎn)生的結(jié)果是局部最小值，也是具有很強(qiáng)性質(zhì)的局部最小值。因此對(duì)特定領(lǐng)域里一些有爭(zhēng)議的問(wèn)題，可利用基于圖割的能量最小化方法，得到最準(zhǔn)確的解決方式，因此，將其應(yīng)用到圖像分割上，以期得到更好的分割結(jié)果。

計(jì)算機(jī)視覺(jué)中的很多相關(guān)問(wèn)題，都可以歸結(jié)為能量最小化的問(wèn)題[3]。能量最小化存在很多優(yōu)點(diǎn)：首先，它可以與解決它的算法分開(kāi)，清楚地描述需要解決的問(wèn)題；其次，它可以用空間光滑的結(jié)果來(lái)求解多義性的問(wèn)題；最后，能量最小化避免了陷入早期硬約束的窘境。

能量最小化在計(jì)算機(jī)視覺(jué)中，已經(jīng)存在很長(zhǎng)的一段歷史，并廣泛應(yīng)用于很多問(wèn)題中，如光流、圖像恢復(fù)、表面重構(gòu)、紋理合成以及邊緣檢測(cè)等。梯度下降和模擬退火算法，是兩種典型的能量最小化方法，前者適用于所有連續(xù)變量的函數(shù)，而后者幾乎可以用于所有的離散變量函數(shù)。但這些方法可能會(huì)產(chǎn)生比較差的結(jié)果，因?yàn)樗鼈兘?jīng)常陷于局部最小化中，或者是花費(fèi)很長(zhǎng)時(shí)間才能收斂。在實(shí)踐中，即使在非常簡(jiǎn)單的二值圖像修復(fù)中，模擬退火得到的解，離全局最小也很遠(yuǎn)。

1989年，Greig等人[3]將圖割理論引入計(jì)算機(jī)視覺(jué)領(lǐng)域，出現(xiàn)了基于圖割的能量最小化方法，它克服了以上兩者的不足，實(shí)現(xiàn)了能量的全局最優(yōu)化。它將圖像分割問(wèn)題轉(zhuǎn)換為圖論中網(wǎng)絡(luò)圖的切割問(wèn)題，依據(jù)最小割準(zhǔn)則，使切割后劃分的區(qū)域間具有最小的相似性?；趫D割的圖像分割，將圖像分割問(wèn)題轉(zhuǎn)換為能量函數(shù)的優(yōu)化問(wèn)題，通過(guò)合適的能量函數(shù)建立相應(yīng)的網(wǎng)絡(luò)圖，通過(guò)最大流/最小割算法求解網(wǎng)絡(luò)圖最小割，從而獲取圖像分割的結(jié)果。

2 圖割的研究現(xiàn)狀

2.1 圖割的發(fā)展?fàn)顩r

近年來(lái)，基于圖割的能量最小化方法在圖像處理和計(jì)算機(jī)視覺(jué)中的應(yīng)用越來(lái)越廣泛。圖割理論自1989年首次被發(fā)現(xiàn)，可以最小化計(jì)算機(jī)視覺(jué)中的某個(gè)能量函數(shù)，且只限于二值圖像。1998年Roy和Cox首次用來(lái)解決非二值圖像問(wèn)題，其方法是圖的最大流/最小割算法。Yuri Boykov和Maric-Pierre Jolly[4]2001年首次將圖割（graph cuts）理論引入計(jì)算機(jī)視覺(jué)領(lǐng)域，他們提出并實(shí)踐了一種新的基于能量最小化進(jìn)行目標(biāo)分割的方法，并提出了利用最大流/最小割算法，進(jìn)行全局組合優(yōu)化的目標(biāo)提取方法。自此以后，利用圖割來(lái)解決計(jì)算機(jī)視覺(jué)的問(wèn)題越來(lái)越受到歡迎。許多研究者提出了多種分割算法，如 Rother[5]等人，在 2004年提出的GrabCut算法，是目前目標(biāo)提取效果較好的方法；Ning Xu[6]等人提出的基于圖割理論的活動(dòng)輪廓（GCBAC）算法，克服了傳統(tǒng)的活動(dòng)輪廓算法容易陷入局部最優(yōu)的缺陷，能夠快速、準(zhǔn)確地收斂到目標(biāo)的邊界。

國(guó)內(nèi)自2006年有論文發(fā)表以來(lái)，用圖割研究的領(lǐng)域也越來(lái)越廣。電子科技大學(xué)、安徽大學(xué)和吉林大學(xué)在圖像復(fù)原、圖像匹配、三維重構(gòu)和目標(biāo)提取、圖像去噪、運(yùn)動(dòng)目標(biāo)檢測(cè)、合成、分割等多個(gè)領(lǐng)域都有研究。

為得到更加魯棒的分割性能，許多學(xué)者試圖將形狀先驗(yàn)引入到圖割分割過(guò)程中。這種將高層先驗(yàn)引入到底層分割的做法是近年來(lái)的新趨勢(shì)。文獻(xiàn)［7］用一個(gè)初始輪廓在終端邊緣和執(zhí)行圖割迭代開(kāi)始加強(qiáng)了形狀先驗(yàn)?zāi)Ｐ停o出一組訓(xùn)練的形狀，他們的方法是利用核主成分分析（kPCA），建立一個(gè)統(tǒng)計(jì)形狀空間，在每一步迭代，這個(gè)形狀空間標(biāo)記的上一個(gè)圖用來(lái)作為先驗(yàn)概率圖，負(fù)記錄被分配到終端權(quán)重。雖然這方法取得了可喜成果，但他們的外形產(chǎn)生的能量不是基于形狀的度量標(biāo)準(zhǔn)，此外，該方法不能同時(shí)處理形狀的仿射變換和同時(shí)分割多目標(biāo)物體。文獻(xiàn)［8］提出了一個(gè)新的廣義形狀先驗(yàn)，稱(chēng)為星型先驗(yàn)。它可以表示比緊湊先驗(yàn)更為一般的形狀，而且同樣只需提供一個(gè)內(nèi)部點(diǎn)就滿足分割需要。特別是對(duì)于凸形狀，這個(gè)點(diǎn)可以選在內(nèi)部任意位置而不會(huì)對(duì)最終分割結(jié)果產(chǎn)生影響。但文獻(xiàn)中星型先驗(yàn)的計(jì)算方法略顯復(fù)雜，需要計(jì)算圖像中內(nèi)部點(diǎn)的所有離散直線。Lang 等人［9］對(duì)其提出了改進(jìn)，在簡(jiǎn)化計(jì)算步驟的同時(shí)，保證了與原算法分割效果的一致性，而且，可以處理目標(biāo)具有復(fù)雜紋理的情況。

圖割理論在國(guó)外的計(jì)算機(jī)視覺(jué)領(lǐng)域中，得到了成功且廣泛應(yīng)用，但在國(guó)內(nèi)的研究還處于初級(jí)階段，尤其是圖割理論用于圖像分割這一領(lǐng)域的研究報(bào)道并不多，將圖像的形狀等先驗(yàn)知識(shí)引入圖割技術(shù)的研究更是寥寥無(wú)幾，因此，基于圖割理論的圖像分割在現(xiàn)階段仍然是一個(gè)研究熱點(diǎn)。

2.2 圖割的應(yīng)用

圖割技術(shù)因其能量全局最優(yōu)化而格外引人注目，是計(jì)算機(jī)視覺(jué)中正在興起的一個(gè)有用的工具。

目前，通過(guò)各種方法將形狀先驗(yàn)融入到圖割技術(shù)中是圖割研究的熱點(diǎn)之一。 例如文獻(xiàn)[23]的作者提出一種全新的方法分割一個(gè)特殊類(lèi)的形狀，調(diào)整光滑項(xiàng)防止過(guò)大，如果違反這個(gè)規(guī)則用一個(gè)緊湊形狀來(lái)維護(hù)，然而，在實(shí)際應(yīng)用中涉及到變化的形狀時(shí)該方法是受限的。文獻(xiàn)[24]的作者提出了一種分割時(shí)執(zhí)行迭代的類(lèi)似方法，每步迭代擬合一個(gè)橢圓到當(dāng)前分割，定義為形狀先驗(yàn)聯(lián)合分割內(nèi)部，然而，如緊湊的方法。該方法也不能推廣到高度可變的形狀，同時(shí)，這種方法合并形狀先驗(yàn)作為一個(gè)附加的固定權(quán)重，不是概率意義上的貝葉斯先驗(yàn)。為獲取更多的任意形狀，文獻(xiàn)[25]作者在光滑項(xiàng)中使用一個(gè)距離函數(shù)幫助邊界定位，執(zhí)行圖割前決定形狀分割和固定對(duì)準(zhǔn)，該方法似乎對(duì)初始估計(jì)相當(dāng)敏感，還有，因?yàn)樾螤钕闰?yàn)在邊界項(xiàng)的作用，在某種意義上有一個(gè)局部效應(yīng)和對(duì)錯(cuò)位的敏感。

2004年，Boykov和Kolmogorov在增廣路算法基礎(chǔ)上，提出了一種新算法[11]求解最大流，并將其應(yīng)用于圖像分割及計(jì)算機(jī)視覺(jué)中，大幅度地提高了求解速度。在 push-relabel算法基礎(chǔ)上，Hochbaum[12,13]提出采用pseudoflow解決最大流問(wèn)題，在Olivier Juan和Yuri Boykov提出的Active Graph cuts[14]圖割方法中，應(yīng)用此最大流算法對(duì)網(wǎng)絡(luò)能量函數(shù)進(jìn)行了求解；文獻(xiàn)[15]提出了一種基于簡(jiǎn)化網(wǎng)格圖的立體匹配算法.算法通過(guò)區(qū)域匹配，得到每個(gè)像素的初始視差值，然后只保留完整網(wǎng)格圖的部分可能的視差值，去除其余大部分的節(jié)點(diǎn)和邊緣，建立簡(jiǎn)化的網(wǎng)格圖.該方法大為縮減了網(wǎng)格圖的容量，縮短匹配所用時(shí)間，并且能夠選用更大的視差范圍.

Boykov[1]等人在2000年發(fā)表了一篇在N維空間交互式的圖像分割方法，以其簡(jiǎn)潔的交互方式、較快的處理速度以及能將各種信息融合，而引起人們的關(guān)注；Rother[16]等在Boykov等人的基礎(chǔ)上提出Grab cut算法，通過(guò)高斯混合建模與數(shù)據(jù)的估計(jì)代替 Boykov的直方圖模型，可對(duì)彩色圖像進(jìn)行分割，而且使得交互更為方便，目前是交互式圖像分割中最好的一種方法；文獻(xiàn)[17]提出一種新的基于圖割(graph cuts)的交互式圖像分割方法。該方法將圖像的紋理、色彩、邊緣等多種特征，通過(guò)一個(gè)概率模型結(jié)合在一起，其中紋理和色彩用以Texton 為基的直方圖來(lái)建模，并用Fisher 判別準(zhǔn)則來(lái)對(duì)特征空間進(jìn)行降維。利用圖割方法，可以快速求解該模型下的最優(yōu)分割；文獻(xiàn)[18]針對(duì)腹部CT 圖像中組織分割的問(wèn)題，提出了一種基于圖割與改進(jìn)的快速水平集的交互式分割方法；文獻(xiàn)[19]提出一種基于圖割的全變差( TV) 圖像去噪算法， 該算法將全變差去噪模型的能量函數(shù)最小化問(wèn)題轉(zhuǎn)化為圖的最小割問(wèn)題, 然后采用圖割技術(shù)( 最大流/最小割算法) 求得能量函數(shù)的全局最優(yōu)解。

文獻(xiàn)[20]基于多尺度思想對(duì)圖像分割，它先對(duì)原始圖像下采樣，用圖割對(duì)低分辨率圖像分割，然后將分割的結(jié)果映射到較高分辨率圖像的帶狀區(qū)域，并逐級(jí)在較高分辨率圖像的窄帶狀區(qū)域分割，直至得到原分辨率圖像的分割結(jié)果；文獻(xiàn)[21]將圖割技術(shù)與分水嶺算法相結(jié)合進(jìn)行分割，先用分水嶺將圖像分成若干小的區(qū)域，再對(duì)這些小區(qū)域采用圖割技術(shù)，提高了分割速度。

文獻(xiàn)[22]將圖割與主動(dòng)輪廓相結(jié)合，通過(guò)設(shè)置初始化輪廓建立輪廓區(qū)域，利用圖割全局能量最優(yōu)在一定的輪廓區(qū)域?qū)ふ夷繕?biāo)邊界的最優(yōu)解；文獻(xiàn)[23]提出圖割計(jì)算測(cè)地線和最小表面的方法，通過(guò)建立網(wǎng)格圖及設(shè)置邊緣權(quán)使得割的代價(jià)任意接近相應(yīng)輪廓的長(zhǎng)度或表面面積。

圖割可用于3D目標(biāo)或序列的分割，在文獻(xiàn)[1]中，通過(guò)交互式選取若干幀的種子點(diǎn)，采用3D圖對(duì)運(yùn)動(dòng)目標(biāo)進(jìn)行了分割。

圖割技術(shù)還在圖像修復(fù)、圖像合成、區(qū)域融合、多攝像機(jī)場(chǎng)景重建、聚類(lèi)、目標(biāo)識(shí)別、形狀重建等諸多方面都有廣泛的應(yīng)用，充分表明圖割的應(yīng)用前景是非常廣泛的。

3 能量函數(shù)的構(gòu)造及求解

一個(gè)圖像分割的問(wèn)題可以看做給圖像中所有的像素分配一系列對(duì)應(yīng)標(biāo)號(hào)的問(wèn)題。如對(duì)于一個(gè)二值標(biāo)號(hào)的問(wèn)題，如果像素點(diǎn)i屬于前景，設(shè)其標(biāo)號(hào)值為1，反之，如果像素點(diǎn)i屬于背景，設(shè)其標(biāo)號(hào)值為 0，這樣通過(guò)對(duì)像素標(biāo)號(hào)實(shí)現(xiàn)對(duì)圖像前景和背景的分割。在不確定的情況下，找到最好的標(biāo)號(hào)成為一個(gè)優(yōu)化問(wèn)題。優(yōu)化的方法通常由兩步構(gòu)成：構(gòu)造能量函數(shù)及求解能量函數(shù)的最優(yōu)解。

3.1 能量函數(shù)的構(gòu)造

圖割是解決優(yōu)化能量函數(shù)問(wèn)題的，因此需要將要解決的問(wèn)題構(gòu)造成能量函數(shù)，這是前提。

在圖像分割問(wèn)題中，能量函數(shù)的構(gòu)造包含兩個(gè)通常的約束：數(shù)據(jù)項(xiàng)約束和平滑項(xiàng)約束公式（4）其中數(shù)據(jù)項(xiàng)Edata(f)對(duì)應(yīng)t-links，它評(píng)價(jià)分配一個(gè)標(biāo)簽到給定區(qū)域的懲罰；光滑項(xiàng) Esmooth(f)對(duì)應(yīng)n-links，評(píng)價(jià)兩個(gè)相鄰像素不同區(qū)域的懲罰，即邊界不連續(xù)性。

然而對(duì)于具體問(wèn)題來(lái)說(shuō)，可以在這兩項(xiàng)的基礎(chǔ)上加上符合自己?jiǎn)栴}的約束條件。例如：基于Potts模型的能量形式公式（5）

式中，E（.）是能量，p和q是像素， N是像素的連通鄰域點(diǎn)集合； Dp(·)是一個(gè)數(shù)據(jù)補(bǔ)償函數(shù)，表示數(shù)據(jù)約束，用于保證每個(gè)像素盡可能地找到其對(duì)應(yīng)標(biāo)號(hào)；V{p,q}是平滑項(xiàng)，是對(duì)相鄰像素標(biāo)號(hào)不一致的懲罰，V{p,q}通過(guò)衡量像素之間的不連續(xù)性來(lái)決定空間一致性。

在二元標(biāo)號(hào)問(wèn)題中，即將圖像分為目標(biāo)和背景兩部分的情形，能量函數(shù)得公式（6）

其中f是一個(gè)從像素集p到標(biāo)號(hào)集L{0,1}的映射值，對(duì)每個(gè)像素點(diǎn)給定一個(gè)標(biāo)號(hào)值f，f值為0的像素集設(shè)定為目標(biāo)，f值為1的像素集設(shè)定為背景。

在加入形狀先驗(yàn)知識(shí)的分割問(wèn)題中，基于potts模型的能量函數(shù)得公式（7）

在圖像修復(fù)中，基于Potts模型的能量函數(shù)得公式（8）

3.2 能量函數(shù)的求解

對(duì)公式（5）這種組合優(yōu)化問(wèn)題，找到全局最優(yōu)值是一個(gè)難以解決的問(wèn)題。

1956年，ford[24]等證明了著名的最大流/最小割定理，即在任何網(wǎng)絡(luò)圖中，最大流的值等于最小割的容量，并給出了求解的具體算法，該算法可以依據(jù)多項(xiàng)式時(shí)間完成計(jì)算；1989年，Greig[23]等人首先發(fā)現(xiàn)最大流/最小割算法，能被用來(lái)最優(yōu)化某些重要的能量函數(shù)，并根據(jù)公式（5）的結(jié)構(gòu)，建立了具有兩個(gè)終點(diǎn)的一個(gè)圖，使圖的最小割給出了全局最優(yōu)的二元標(biāo)號(hào)。目前，解決最大流常用Ford-fulkerson算法、push-relabel算法及Boykov等人的新算法。

總之，采用圖割求解能量函數(shù)的基本思路，就是對(duì)一個(gè)給定的能量函數(shù)構(gòu)造對(duì)應(yīng)的網(wǎng)絡(luò)圖，然后通過(guò)對(duì)網(wǎng)絡(luò)圖的最小割求解，使得能量函數(shù)最優(yōu)。

4.基于圖割提取圖像信息的解題步驟

綜上所述，基于圖割提取圖像信息的解題步驟，一般為：根據(jù)問(wèn)題建立能量函數(shù)、構(gòu)造有兩個(gè)終端節(jié)點(diǎn)的網(wǎng)絡(luò)圖、用最大流（最小割）算法求解、提取圖像信息，如圖2所示：

圖2 圖割解題步驟

其中最關(guān)鍵的步驟，就是根據(jù)圖像分割問(wèn)題，建立合適的能量函數(shù)及對(duì)能量函數(shù)求解。

4.1 建立能量函數(shù)

能量函數(shù)的建立，主要體現(xiàn)在數(shù)據(jù)項(xiàng)和光滑項(xiàng)的建立上。典型應(yīng)用圖割對(duì)圖像分割的不同只在數(shù)據(jù)項(xiàng)和光滑項(xiàng)的定義上。

4.1.1 數(shù)據(jù)項(xiàng)的建立

圖割在不同領(lǐng)域的應(yīng)用，主要體現(xiàn)在數(shù)據(jù)項(xiàng)的建立上。在不同的應(yīng)用與問(wèn)題中，數(shù)據(jù)項(xiàng)的定義不一樣。

4.1.2 光滑項(xiàng)的建立

如式（3），V{p,q}是光滑項(xiàng)，它是所有相鄰像素的相鄰交互函數(shù)的和。光滑項(xiàng)的建立可以提高圖像分割的質(zhì)量，V{p,q}的形式?jīng)Q定光滑先驗(yàn)信息的類(lèi)型，其主要類(lèi)型有：處處光滑、分段常數(shù)及分段光滑。

處處光滑約束的常用形式得公式（10）

分段常數(shù)約束的常用形式得公式（11）

分段光滑約束的常用形式得公式（12）

對(duì)上式中的系數(shù)u{p,q}可根據(jù)具體問(wèn)題做相應(yīng)的設(shè)置。在公式（12）式中，當(dāng)u{p,q}為常數(shù)時(shí)，式中的光滑能量為potts能量，光滑項(xiàng)給出了兩個(gè)相鄰像素為不同標(biāo)號(hào)時(shí)的懲罰，這個(gè)懲罰不依賴(lài)于設(shè)置的標(biāo)號(hào)。在圖像分割中常采用這樣的約束作為光滑項(xiàng)。

建立了數(shù)據(jù)項(xiàng)和光滑項(xiàng)后，就可建立能量函數(shù)。綜上所述，在圖像分割中，常用的能量函數(shù)為如下的potts模型，如公式（13）

其中T(·)是指示函數(shù)，括號(hào)中的值為真，它為1，否則為0。k(p,q)表示對(duì)相鄰像素標(biāo)號(hào)不一致的懲罰。

4.2 構(gòu)造網(wǎng)絡(luò)圖

如圖3所示：

圖3 網(wǎng)絡(luò)圖

構(gòu)建一個(gè)圖表示這個(gè)能量，每個(gè)像素看作除表示目標(biāo)和背景節(jié)點(diǎn)外的圖節(jié)點(diǎn)，數(shù)據(jù)項(xiàng)實(shí)現(xiàn)每個(gè)像素都連接到目標(biāo)和背景節(jié)點(diǎn)，非負(fù)邊緣權(quán)重 Rp(O)和Rp(B)表示目標(biāo)和背景區(qū)域存在相似像素P。最后，光滑項(xiàng)實(shí)現(xiàn)每對(duì)相鄰像素(p ,q)的連接，非負(fù)邊緣權(quán)重 B(p,q)決定邊緣不連續(xù)的處罰。由此可見(jiàn)，基于能量函數(shù)可以建立網(wǎng)絡(luò)圖。

文獻(xiàn)[29]研究了能量函數(shù)進(jìn)行圖割優(yōu)化應(yīng)該具備的條件，并給出了具體構(gòu)造圖的方法。

4.3 求解網(wǎng)絡(luò)圖

對(duì)于建立的網(wǎng)絡(luò)圖G，可通過(guò)最大流/最小割算法求解，即求取該網(wǎng)絡(luò)的最小割，由于最小割是沿著邊界的總數(shù)，最小割的加權(quán)圖分割表示從背景分離最好的目標(biāo)。這樣對(duì)能量函數(shù)的最優(yōu)解是通過(guò)圖的最小割實(shí)現(xiàn)的。

4.4 獲取圖像的處理結(jié)果

最小割準(zhǔn)則將圖像分割成兩個(gè)區(qū)域。對(duì)于二元標(biāo)號(hào)，通?？芍苯訉⒁粋€(gè)區(qū)域作為目標(biāo)，另一個(gè)區(qū)域作為背景。顯然對(duì)圖像的二元分割可直接采用圖割方法來(lái)獲取全局最優(yōu)解。

5 存在的問(wèn)題和研究前景

圖割是基于圖論的圖像分割方法，且具有二元全局能量最優(yōu)化的特性，盡管它廣泛地應(yīng)用于圖像分割，但它在分割對(duì)象具有弱邊緣、雜波及部分被遮擋時(shí)容易失敗，合并形狀先驗(yàn)信息可防止這樣的失敗，然而將這樣的信息融入圖割是一個(gè)長(zhǎng)期的研究領(lǐng)域。

目前，基于圖割的交互式分割得到了良好的分割結(jié)果與廣泛應(yīng)用，但是基于圖割對(duì)圖像進(jìn)行自動(dòng)分割以及對(duì)運(yùn)動(dòng)目標(biāo)自動(dòng)分割，還沒(méi)有太多研究與應(yīng)用，因此，解決該問(wèn)題是研究的方向之一。

圖割是基于能量?jī)?yōu)化的方法，而現(xiàn)有的許多基于能量函數(shù)優(yōu)化的圖像分割方法，都具有其各自的特性和不足。因此，為克服現(xiàn)有方法的不足，如何將現(xiàn)有的方法與其它基于能量的優(yōu)化方法相結(jié)合，或者重建一個(gè)新的模型，在一定程度上取長(zhǎng)補(bǔ)短是需要研究的問(wèn)題之一。

隨著圖割在計(jì)算機(jī)視覺(jué)中的廣泛應(yīng)用，圖割方法本身也存在許多有待改進(jìn)的不足之處，其中最重要的就是能量函數(shù)的更新和最小化問(wèn)題。利用圖割解決問(wèn)題要利用網(wǎng)絡(luò)圖，而構(gòu)圖時(shí)的計(jì)算量過(guò)大是一個(gè)難題，目前，許多算法已針對(duì)圖割方法構(gòu)圖時(shí)計(jì)算量過(guò)大問(wèn)題進(jìn)行了改進(jìn)，把圖割理論和其他方法結(jié)合，用于圖像分割可達(dá)到很好的效果，如何找到更好的方法解決該問(wèn)題，是我們努力的一個(gè)方向。

正則性是函數(shù)可以用圖表示的必要條件。只給出了F3集合中函數(shù)的構(gòu)造[23]。至于在 F4，F(xiàn)5，…，F(xiàn)k集合中，如果函數(shù)也滿足正則性，圖割法是否仍然適用，是應(yīng)該思考的問(wèn)題。

圖割對(duì)應(yīng)的是二元標(biāo)號(hào)優(yōu)化問(wèn)題，而Multiway cut對(duì)應(yīng)多元標(biāo)號(hào)的問(wèn)題，對(duì)它的能量最優(yōu)求解是一個(gè) NP-Hard問(wèn)題，目前對(duì)Multiway cut的能量最優(yōu)化采用近似求解，如α-βswap算法和α-expansion算法。這種近似算法，目前多用于計(jì)算機(jī)視覺(jué)的其他方面，在圖像分割中很少應(yīng)用。如何更好地應(yīng)用此類(lèi)算法，解決圖像分割是需要研究的問(wèn)題。

6 結(jié)束語(yǔ)

基于圖割的圖像分割，作為目前國(guó)際上圖像分割領(lǐng)域的一個(gè)新的研究熱點(diǎn)，因其具有獨(dú)特的結(jié)構(gòu)，得到了很多研究者的青睞，并得到了廣泛的應(yīng)用。然而正因?yàn)樗且环N新的圖像分割方式，對(duì)它的研究和應(yīng)用還處于初級(jí)階段，仍有大量的問(wèn)題有待研究和解決?；趫D割的圖像分割技術(shù)涉及到的理論知識(shí)和學(xué)科比較廣泛，對(duì)其研究不僅可豐富圖像分割的應(yīng)用，而且在圖像處理領(lǐng)域具有重要的理論價(jià)值和巨大的應(yīng)用潛力，在學(xué)科交叉的研究與應(yīng)用上也具有重要的意義。

[1]Boykov Y,Jolly M P.Interactive organ segmentation using graph [C]cuts.In:Proc.Third International Conference on Medical Image Computing and Computer-Assisted Intervention,2000,276-286.

[2]Yuri Boykov,Olga Veksler.Graph cuts in vision and graphics theories and applications.In [K]Handbook of Mathematical Models in Computer Vision,Springer,2006.

[3]Greig,D.Porteous, B.A.Seheult.Exact maximum a Posteriori estimation for binary images[J], JOumal of the Royal Statistieal Society: SeriesB, 1989, 51(2): 271一279.

[4]Boykov, Y.Jolly, M, P.Interactive Graph cuts for optimal boundary ®ion segmentation of objects in N-D images.[C]Proceedings of “intimation conference on computer vision”, Vancouver, 2001（7）: 105-112

[5]Rother, C.Kolmogorov, V.A.BLAKE.GrabCut:interactive foreground extraction using iterated graph cuts[C], proceeding of the 2004 SIGGRAPH conference，Aug 2004，I：309-314.

[6]Xu, N.Abuja, N.Bansal.R.Object segmentation using graph cuts based active contours[J].computer vision and image understanding，2007,107(3):210-224.

[7]Malcolm, J.Rathi, Y.and Tannenbaum.A.Graph cut segmentation with nonlinear shape priors.[j]In ICIP,2007.1

[8]徐秋萍，郭敏，王亞榮.基于圖割的目標(biāo)提取實(shí)時(shí)修正算法.[j]計(jì)算機(jī)應(yīng)用.2008(12):28(12),3116-3122.

[9]Ford L R,Fulkerson D R.Maximal flow through a network.[M]Canadian Journal of Mathematics, 1956, 8(3):399-404.

[10]Cherkassky B V,Goldberg A V.On implementing the push-relabel method for the maximum flow problem.[M]Algorithmica.1997,19(4):390-410.

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

[12]Hochbaum D.S.The Pseudoflow algorithm:A new algorithm for the maximum flow problem.Operations Research to appear.Extended abstract in The pseudoflow algorithm and the pseudoflow-based simplex for the maximum flow problem.[G]Proc.Int'l Conf.Integer Programming and Combinatorial Optimization, 98:325-337.

[13]Hochbaum D.S.The Pseudoflow algorithm:A new algorithm for the maximum flow problem.[M]Operations Research,2008,58(4):992-1009.

[14]Juan O,Boykov Y.Active graph cuts.Proc.of IEEE Conference on Computer Vision and Pattern Recognition.[C]New York:IEEE Computer Society,2006: 1023-1029.

[15]Rother C, Kolmogorov V,Blake A.GrabCut:interactive foreground extraction using iterated graph cuts.[j]ACM Transactions on Graphics(TOG),2004,23(3): 309～314.

[16]劉嘉，王宏琦.一種基于圖割的交互式圖像分割方法.[j]電子與信息學(xué)

[17]楊昌俊，楊新..基于圖割與快速水平集的腹部CT圖像分割..[j]CT理論與應(yīng)用研究.2011(3): 291-300

[18]吳亞?wèn)|，孫世新，張紅英等.一種基于圖割的全變差圖像去噪算法.[j]電子學(xué)報(bào).2007(2):35(2),265-268.

[19]Herve Lombaert,Yiyong Sun,Leo Grady,et al.A multilevel banded graph cuts method for fast image segmentation.Proceedings of the Tenth IEEE International Conference on Computer Vision, [C]ICCV 2005,1:259-265.

[20]Li Y,Sun J,Tang C K,Shum H Y.Lazy snap-ping.[C]In Proceedings of ACM SIGGRAPH, ACM Press, 2004,23(4):303-308.

[21]Xu N,Bansal R,Ahuja N.Object segmentation using graph cuts based active contours.[C]In IEEE International Conference on Computer Vision and Pattern Recognition,2003,2:46-53.

[22]Greig D,Porteous B,Seheult A.Exact maximum a posteriori estimation for binary images.[C]Journal of the royal statistical society,series B.1989,51(2): 271-279.

[23]Slabaugh G.and Unal, G.“Graph cuts segmentation using an elliptical shape prior,” in Int.Conf.[G]on Image Processing, 2005, pp.1222-5.

[24]D.Freedman and T.Zhang, “Interactive graph cut based segmentation with shape priors,” [j]in Computer Vision and Pattern Recognition, 2005, pp.755-762.

[25]Das, P.Veksler, O.Zavadsky, V.and Boykov, Y.“Semiautomatic segmentation with compact shape prior,”in Canadian Conf.[j]on Computer and Robot Vision,2006, pp.28-36.