上一文對(duì)主要的分割方法做了一個(gè)概述。那下面我們對(duì)其中幾個(gè)比較感興趣的算法做個(gè)學(xué)習(xí)。下面主要是Graph Cut，下一個(gè)博文我們?cè)賹W(xué)習(xí)下Grab Cut，兩者都是基于圖論的分割方法。另外OpenCV實(shí)現(xiàn)了Grab Cut，具體的源碼解讀見博文更新。接觸時(shí)間有限，若有錯(cuò)誤，還望各位前輩指正，謝謝。

?????? Graph cuts是一種十分有用和流行的能量?jī)?yōu)化算法，在計(jì)算機(jī)視覺領(lǐng)域普遍應(yīng)用于前背景分割（Image segmentation）、立體視覺（stereo vision）、摳圖（Image matting）等。

?????? 此類方法把圖像分割問題與圖的最小割（min cut）問題相關(guān)聯(lián)。首先用一個(gè)無向圖G=<V，E>表示要分割的圖像，V和E分別是頂點(diǎn)（vertex）和邊（edge）的集合。此處的Graph和普通的Graph稍有不同。普通的圖由頂點(diǎn)和邊構(gòu)成，如果邊的有方向的，這樣的圖被則稱為有向圖，否則為無向圖，且邊是有權(quán)值的，不同的邊可以有不同的權(quán)值，分別代表不同的物理意義。而Graph Cuts圖是在普通圖的基礎(chǔ)上多了2個(gè)頂點(diǎn)，這2個(gè)頂點(diǎn)分別用符號(hào)”S”和”T”表示，統(tǒng)稱為終端頂點(diǎn)。其它所有的頂點(diǎn)都必須和這2個(gè)頂點(diǎn)相連形成邊集合中的一部分。所以Graph Cuts中有兩種頂點(diǎn)，也有兩種邊。

第一種頂點(diǎn)和邊是：第一種普通頂點(diǎn)對(duì)應(yīng)于圖像中的每個(gè)像素。每?jī)蓚€(gè)鄰域頂點(diǎn)（對(duì)應(yīng)于圖像中每?jī)蓚€(gè)鄰域像素）的連接就是一條邊。這種邊也叫n-links。

第二種頂點(diǎn)和邊是：除圖像像素外，還有另外兩個(gè)終端頂點(diǎn)，叫S（source：源點(diǎn)，取源頭之意）和T（sink：匯點(diǎn)，取匯聚之意）。每個(gè)普通頂點(diǎn)和這2個(gè)終端頂點(diǎn)之間都有連接，組成第二種邊。這種邊也叫t-links。

?????? 上圖就是一個(gè)圖像對(duì)應(yīng)的s-t圖，每個(gè)像素對(duì)應(yīng)圖中的一個(gè)相應(yīng)頂點(diǎn)，另外還有s和t兩個(gè)頂點(diǎn)。上圖有兩種邊，實(shí)線的邊表示每?jī)蓚€(gè)鄰域普通頂點(diǎn)連接的邊n-links，虛線的邊表示每個(gè)普通頂點(diǎn)與s和t連接的邊t-links。在前后景分割中，s一般表示前景目標(biāo)，t一般表示背景。

?????? 圖中每條邊都有一個(gè)非負(fù)的權(quán)值w_e，也可以理解為cost（代價(jià)或者費(fèi)用）。一個(gè)cut（割）就是圖中邊集合E的一個(gè)子集C，那這個(gè)割的cost（表示為|C|）就是邊子集C的所有邊的權(quán)值的總和。

???????? Graph Cuts中的Cuts是指這樣一個(gè)邊的集合，很顯然這些邊集合包括了上面2種邊，該集合中所有邊的斷開會(huì)導(dǎo)致殘留”S”和”T”圖的分開，所以就稱為“割”。如果一個(gè)割，它的邊的所有權(quán)值之和最小，那么這個(gè)就稱為最小割，也就是圖割的結(jié)果。而福特-富克森定理表明，網(wǎng)路的最大流max flow與最小割min cut相等。所以由Boykov和Kolmogorov發(fā)明的max-flow/min-cut算法就可以用來獲得s-t圖的最小割。這個(gè)最小割把圖的頂點(diǎn)劃分為兩個(gè)不相交的子集S和T，其中s?∈S，t∈?T和S∪T=V?。這兩個(gè)子集就對(duì)應(yīng)于圖像的前景像素集和背景像素集，那就相當(dāng)于完成了圖像分割。

????????也就是說圖中邊的權(quán)值就決定了最后的分割結(jié)果，那么這些邊的權(quán)值怎么確定呢？

?????? 圖像分割可以看成pixel labeling（像素標(biāo)記）問題，目標(biāo)（s-node）的label設(shè)為1，背景（t-node）的label設(shè)為0，這個(gè)過程可以通過最小化圖割來最小化能量函數(shù)得到。那很明顯，發(fā)生在目標(biāo)和背景的邊界處的cut就是我們想要的（相當(dāng)于把圖像中背景和目標(biāo)連接的地方割開，那就相當(dāng)于把其分割了）。同時(shí)，這時(shí)候能量也應(yīng)該是最小的。假設(shè)整幅圖像的標(biāo)簽label（每個(gè)像素的label）為L= {l_1,l_2,,,, l_p?}，其中l_i為0（背景）或者1（目標(biāo)）。那假設(shè)圖像的分割為L時(shí)，圖像的能量可以表示為：

E(L)=aR(L)+B(L)

?????? 其中，R(L)為區(qū)域項(xiàng)（regional term），B(L)為邊界項(xiàng)（boundary term），而a就是區(qū)域項(xiàng)和邊界項(xiàng)之間的重要因子，決定它們對(duì)能量的影響大小。如果a為0，那么就只考慮邊界因素，不考慮區(qū)域因素。E(L)表示的是權(quán)值，即損失函數(shù)，也叫能量函數(shù)，圖割的目標(biāo)就是優(yōu)化能量函數(shù)使其值達(dá)到最小。

區(qū)域項(xiàng)：

，其中R_p(l_p)表示為像素p分配標(biāo)簽l_p的懲罰，R_p(l_p)能量項(xiàng)的權(quán)值可以通過比較像素p的灰度和給定的目標(biāo)和前景的灰度直方圖來獲得，換句話說就是像素p屬于標(biāo)簽l_p的概率，我希望像素p分配為其概率最大的標(biāo)簽l_p，這時(shí)候我們希望能量最小，所以一般取概率的負(fù)對(duì)數(shù)值，故t-link的權(quán)值如下：

R_p(1) = -ln Pr(I_p|’obj’)；?R_p(0) = -ln Pr(I_p|’bkg’)

??????? 由上面兩個(gè)公式可以看到，當(dāng)像素p的灰度值屬于目標(biāo)的概率Pr(I_p|’obj’)大于背景Pr(I_p|’bkg’)，那么R_p(1)就小于R_p(0)，也就是說當(dāng)像素p更有可能屬于目標(biāo)時(shí)，將p歸類為目標(biāo)就會(huì)使能量R(L)小。那么，如果全部的像素都被正確劃分為目標(biāo)或者背景，那么這時(shí)候能量就是最小的。

邊界項(xiàng)：

??????? 其中，p和q為鄰域像素，邊界平滑項(xiàng)主要體現(xiàn)分割L的邊界屬性，B_<p,q>可以解析為像素p和q之間不連續(xù)的懲罰，一般來說如果p和q越相似（例如它們的灰度），那么B_<p,q>越大，如果他們非常不同，那么B_<p,q>就接近于0。換句話說，如果兩鄰域像素差別很小，那么它屬于同一個(gè)目標(biāo)或者同一背景的可能性就很大，如果他們的差別很大，那說明這兩個(gè)像素很有可能處于目標(biāo)和背景的邊緣部分，則被分割開的可能性比較大，所以當(dāng)兩鄰域像素差別越大，B_<p,q>越小，即能量越小。

????????好了，現(xiàn)在我們來總結(jié)一下：我們目標(biāo)是將一幅圖像分為目標(biāo)和背景兩個(gè)不相交的部分，我們運(yùn)用圖分割技術(shù)來實(shí)現(xiàn)。首先，圖由頂點(diǎn)和邊來組成，邊有權(quán)值。那我們需要構(gòu)建一個(gè)圖，這個(gè)圖有兩類頂點(diǎn)，兩類邊和兩類權(quán)值。普通頂點(diǎn)由圖像每個(gè)像素組成，然后每?jī)蓚€(gè)鄰域像素之間存在一條邊，它的權(quán)值由上面說的“邊界平滑能量項(xiàng)”來決定。還有兩個(gè)終端頂點(diǎn)s（目標(biāo)）和t（背景），每個(gè)普通頂點(diǎn)和s都存在連接，也就是邊，邊的權(quán)值由“區(qū)域能量項(xiàng)”R_p(1)來決定，每個(gè)普通頂點(diǎn)和t連接的邊的權(quán)值由“區(qū)域能量項(xiàng)”R_p(0)來決定。這樣所有邊的權(quán)值就可以確定了，也就是圖就確定了。這時(shí)候，就可以通過min cut算法來找到最小的割，這個(gè)min cut就是權(quán)值和最小的邊的集合，這些邊的斷開恰好可以使目標(biāo)和背景被分割開，也就是min cut對(duì)應(yīng)于能量的最小化。而min cut和圖的max flow是等效的，故可以通過max flow算法來找到s-t圖的min cut。目前的算法主要有：

1) Goldberg-Tarjan

2) Ford-Fulkerson

3)?上訴兩種方法的改進(jìn)算法

?

權(quán)值：

???????? Graph cut的3x3圖像分割示意圖：我們?nèi)蓚€(gè)種子點(diǎn)（就是人為的指定分別屬于目標(biāo)和背景的兩個(gè)像素點(diǎn)），然后我們建立一個(gè)圖，圖中邊的粗細(xì)表示對(duì)應(yīng)權(quán)值的大小，然后找到權(quán)值和最小的邊的組合，也就是（c）中的cut，即完成了圖像分割的功能。

上面具體的細(xì)節(jié)請(qǐng)參考：

《Interactive Graph Cuts for Optimal Boundary & Region Segmentation of Objects in N-D Images》（Boykov，iccv01）這篇paper講怎么用graphcut來做image segmentation。

在Boykov?和?Kolmogorov?倆人的主頁上就有大量的code。包括maxflow/min-cut、stereo algorithms等算法：

http://pub.ist.ac.at/~vnk/software.html

http://vision.csd.uwo.ca/code/

康奈爾大學(xué)的graphcuts研究主頁也有不少信息：

http://www.cs.cornell.edu/~rdz/graphcuts.html

《Image Segmentation: A Survey of Graph-cut Methods》（Faliu Yi，ICSAI 2012）

總結(jié)

以上是生活随笔為你收集整理的图像分割之（二）Graph Cut（图割）的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。