俞江明，趙杰煜，汪國(guó)鋒

1.寧波大學(xué)信息工程與技術(shù)學(xué)院，浙江寧波 315211

2.浙江省福利彩票發(fā)行中心，杭州 310000

深度圖像的分層圖割算法研究

俞江明，趙杰煜，汪國(guó)鋒

1.寧波大學(xué)信息工程與技術(shù)學(xué)院，浙江寧波 315211

2.浙江省福利彩票發(fā)行中心，杭州 310000

1 引言

圖像分割作為圖像理解和識(shí)別的基礎(chǔ)在計(jì)算機(jī)視覺(jué)中有重要的作用，但由于圖像的復(fù)雜性，沒(méi)有很好的通用的圖像分割算法能解決所有的問(wèn)題，即便如此還是有前赴后繼的國(guó)內(nèi)外學(xué)者投入到圖像分割的研究隊(duì)伍當(dāng)中。在近幾十年的研究當(dāng)中，圖像分割已經(jīng)取得了非常大的進(jìn)展。

在以往的圖像分割算法中，有基于區(qū)域顏色信息的分割[1-2]，也有基于邊緣信息的分割[3-4]，但由于利用的信息太少，都不太能達(dá)到理想的分割效果。

基于圖割的算法由于其非常巧妙地結(jié)合了區(qū)域顏色和邊緣信息而在最近成為了研究的熱點(diǎn)，圖割算法應(yīng)用于圖像是有Greig等[5]人在1989年完成，后續(xù)的研究也有如文[6]應(yīng)用于二值圖像，但其在很長(zhǎng)時(shí)間沒(méi)有得到重視，直到本世紀(jì)初Boykov等人[7]明確了圖割算法應(yīng)用于圖像上圖的定義以及權(quán)值的確定，并且在基于增廣路算法的最大流算法基礎(chǔ)上提出了更為高效的求解最大流的算法[8]，他們開(kāi)創(chuàng)性的工作引發(fā)了再一次的圖割熱，基于圖割的算法層出不窮[9-10]。

Rother等人在文獻(xiàn)[11]中用迭代圖割算法來(lái)減少用戶(hù)交互，只需三四次迭代即能得到精確的分割結(jié)果。由于其非常耗時(shí)的缺點(diǎn)，后續(xù)的以迭代圖割為基礎(chǔ)的研究通常是在不降低分割精度的前提下來(lái)提升分割的速度，取得了比較好的效果，如文獻(xiàn)[12-13]把分水嶺算法過(guò)分割的缺點(diǎn)和圖割算法耗時(shí)的缺點(diǎn)結(jié)合，用分水嶺算法的結(jié)果作為圖割算法的超像素，很好地彌補(bǔ)了兩種方法各自的不足。文獻(xiàn)[14-15]結(jié)合多尺度的金字塔結(jié)構(gòu)來(lái)減少圖割算法的混合高斯EM算法的數(shù)據(jù)規(guī)模，采用三到四層塔結(jié)構(gòu)，正好接近于Rother等[11]人的迭代算法步驟數(shù)，在減少初始化時(shí)間的情況下，沒(méi)有降低最后的分割精度。但其采用最高像素值來(lái)抽取金字塔上層的像素不利于噪聲的去除。圖割算法應(yīng)用于圖像的另一個(gè)分支這是加入形狀先驗(yàn)，分割邊界除了要是梯度最大化之外還要符合形狀先驗(yàn)的約束，如文獻(xiàn)[16-17]中的Kolmogorov等人，但是由于其能量函數(shù)不再符合文獻(xiàn)[18]的能求得全局最優(yōu)解的要求，只能通過(guò)近似方法來(lái)求得圖像分割的邊界，往往非常耗時(shí)。

本文在前人[14-15]的基礎(chǔ)上采用分層的金字塔模型，在提取上層像素中采用下層對(duì)應(yīng)的像素的中值，能有效地解決噪聲問(wèn)題。深度信息的利用也不像Boykov等人[7]那樣采用直接合并的方法，而是引入平衡因子來(lái)決定想要利用的深度信息相對(duì)于顏色信息的重要程度，深度信息的建模采用直方圖建模，引入直方圖的目的是為了計(jì)算平衡因子的方便，而且深度信息是一維信息，直方圖建模是非?？焖俚摹１疚牡幕谏疃葓D像的分層迭代圖割方法取得的結(jié)果優(yōu)于迭代圖割算法而所需的時(shí)間卻大大縮短。

2 圖割理論基礎(chǔ)與改進(jìn)

2.1 能量函數(shù)

圖割理論應(yīng)用于圖像處理，要求是交互式的圖像分割，交互式圖像分割給了用戶(hù)希望劃分的目標(biāo)的先驗(yàn)信息，這些先驗(yàn)信息往往可以增加圖像分割的準(zhǔn)確度，減少分割難度。用戶(hù)給定一些像素作為希望分割的目標(biāo)，一些像素作為圖像的背景，把這些信息當(dāng)做圖像分割的先驗(yàn)信息，即硬約束。其余部分的像素就自動(dòng)分割出來(lái)，只需求得符合這些硬約束的圖像分割中最優(yōu)的那個(gè)分割即可。

首先定義分割為一個(gè)圖像的分割邊界，要求得到圖像的最優(yōu)割，需要定義懲罰函數(shù)，懲罰函數(shù)也可稱(chēng)作能量函數(shù)，最優(yōu)割對(duì)應(yīng)著能量函數(shù)最小值。能量函數(shù)可以分為兩個(gè)部分，一個(gè)代表割的邊界信息，叫做邊界項(xiàng)，另一個(gè)代表割的區(qū)域信息，叫做區(qū)域項(xiàng)，這兩項(xiàng)同時(shí)對(duì)應(yīng)著圖像的軟約束和硬約束。硬約束就是用戶(hù)已經(jīng)給定的先驗(yàn)知識(shí)，軟約束是保證同一前景或同一背景的相鄰像素間的平滑性而引入的。

假設(shè)一幅圖像用數(shù)學(xué)表示為：oi(i=1,2,…,N)，其中oi表中圖像中的第i個(gè)像素，像素按圖像的行排列，N表示圖像中像素的個(gè)數(shù)。用li表示第i個(gè)像素所對(duì)應(yīng)的標(biāo)簽，li取值范圍為li∈{0,1}，通過(guò)MAP-MRF可以得到圖能量函數(shù)的表達(dá)式如下：

式（1）中能量函數(shù)E中的R(L,O)即對(duì)應(yīng)了割的區(qū)域信息，而B(niǎo)(L)則代表了一個(gè)割的邊界信息，λ≥0為區(qū)域似然項(xiàng)R(L,O)相對(duì)于邊界梯度項(xiàng)B(L)的相對(duì)重要程度。區(qū)域項(xiàng)R(L,O)表示了把一個(gè)像素賦給前景或背景的懲罰。在實(shí)際的操作中，往往首先用用戶(hù)給定的硬約束，即哪些像素屬于背景，哪些像素屬于前景，根據(jù)這些像素分別建立前景和背景的概率模型，而R(L,O)就表示觀察的像素值oi與前景或背景概率模型的符合程度，如果觀察值oi與前景概率模型很相似卻給了背景的標(biāo)簽則懲罰值會(huì)很大，反之則會(huì)很小。平滑項(xiàng)B(L)表示了一個(gè)圖像分割L的邊界性質(zhì)。g(li,lj)表示了對(duì)相鄰像素oi，oj之間的不平滑的懲罰，懲罰項(xiàng)可以采用很多形式，比如梯度，或者是方向梯度等等[7]。

區(qū)域似然項(xiàng)R(L,O)是圖像中的觀察像素值與前景和背景概率模型的相似程度，在公式（2）中通過(guò)f(oi|li)可以得知給標(biāo)簽li值0則表示觀察值和背景概率模型是符合的，如果給標(biāo)簽li值1則表示觀察值與前景概率模型是符合的。

在Boykov等人[7]的圖割算法中利用直方圖作為概率模型，并且認(rèn)為他們的方法可以推廣到N維圖像，但是事實(shí)上直方圖在對(duì)高于二維的數(shù)據(jù)進(jìn)行建模時(shí)將變得非常困難，在文獻(xiàn)[11]中已經(jīng)提到，他們?cè)诓噬珗D像中采用的是混合高斯模型，并且減少了用戶(hù)的交互。本文由于引入了深度信息概率模型的選擇將對(duì)分割的有效性產(chǎn)生重大影響，考慮到深度信息是一維的可以采用快速的直方圖建模，顏色文理信息仍然采用混合高斯模型，兩者之間的權(quán)衡用平衡因子α來(lái)表示。假設(shè)用P(oi|F)表示前景概率模型，P(oi|B)表示背景概率模型，則根據(jù)上面描述可以定義加入深度信息的概率模型如下：

其中ci表示圖像像素的RGB觀察值，di為從圖像的深度信息，θF為前景混合高斯模型的參數(shù)，θB為背景混合高斯模型的參數(shù)，?F為前景直方圖概率模型的參數(shù)，?B為背景直方圖概率模型的參數(shù)。其中Pr(ci|θF)和Pr(oi|θB)表示的前背景混合高斯概率模型的具體公式如下：

其中zi為維度為C的單位向量，假設(shè)圖像深度信息的最大值為D，則zi中第[di·C/D]為1，表示di屬于直方圖中的哪一個(gè)類(lèi)別，表示用戶(hù)標(biāo)定的數(shù)據(jù)統(tǒng)計(jì)的直方圖類(lèi)別概率，nk表示第k類(lèi)的樣本個(gè)數(shù)，E為樣本總數(shù)。這樣基于深度的直方圖概率模型通過(guò)樣本概率的形式可以簡(jiǎn)單地用數(shù)學(xué)公式表示出來(lái)。以上就是全部的概率模型公式，其中的顏色部分利用了和文獻(xiàn)[11]中類(lèi)似的混合高斯模型，事實(shí)上他們已經(jīng)通過(guò)實(shí)踐確定用直方圖來(lái)建立高維的概率模型是很難實(shí)際操作的，對(duì)于深度的建模，采用的是直方圖建模，因?yàn)榛旌细咚骨蠼獾臅r(shí)候要用到EM算法，而EM算法是循環(huán)迭代的算法，其時(shí)間復(fù)雜度較高，但是直方圖卻能在很短時(shí)間內(nèi)建立一維數(shù)據(jù)的概率模型，對(duì)于深度信息的建模是非常合適的，并且在本文的方法中對(duì)于深度的直方圖建模的α的確定也是有利的，本文的α就是在直方圖概率向量的基礎(chǔ)上來(lái)確定的?？傊x擇直方圖來(lái)概率建模不僅耗時(shí)較少，而且有利于本文的深度信息與顏色信息之間重要性的平衡。

2.2 權(quán)值確定和圖結(jié)構(gòu)

在圖割算法中，一般把圖中的每個(gè)像素看成數(shù)據(jù)結(jié)構(gòu)中圖的節(jié)點(diǎn)，通過(guò)前面的馬爾科夫隨機(jī)場(chǎng)的馬爾科夫性質(zhì)假設(shè)每個(gè)像素的標(biāo)號(hào)只受相鄰像素的標(biāo)號(hào)的影響，本文采用的是8鄰域系統(tǒng)，所以像素之間的邊的連接如圖1所示。

圖1 鄰域系統(tǒng)

在圖1的基礎(chǔ)上加入兩個(gè)額外的節(jié)點(diǎn)一個(gè)是source節(jié)點(diǎn)一個(gè)是terminal節(jié)點(diǎn)，簡(jiǎn)稱(chēng)S節(jié)點(diǎn)和T節(jié)點(diǎn)，S代表目標(biāo)，T代表背景，并把圖中所有的像素節(jié)點(diǎn)與這兩個(gè)節(jié)點(diǎn)相連接。

在圖割算法的圖模型中，圖中的節(jié)點(diǎn)包括每個(gè)像素對(duì)應(yīng)一個(gè)節(jié)點(diǎn)外加兩個(gè)終結(jié)節(jié)點(diǎn)，一個(gè)是S節(jié)點(diǎn)，一個(gè)是T節(jié)點(diǎn)，S節(jié)點(diǎn)又叫目標(biāo)節(jié)點(diǎn)，找到最小割以后與S仍然相連的節(jié)點(diǎn)即為所要提取的目標(biāo)物體，相應(yīng)的T節(jié)點(diǎn)又叫背景節(jié)點(diǎn)，執(zhí)行最大流算法找到最小割以后與T仍然相連的就是背景。

圖中的邊如前所述，也可以分為兩類(lèi)邊，一類(lèi)是n-link，為圖中相鄰像素節(jié)點(diǎn)之間的連接邊，一類(lèi)是t-link，為像素節(jié)點(diǎn)與終結(jié)節(jié)點(diǎn)之間相連邊，圖2表述了以上的節(jié)點(diǎn)和邊。

圖2 圖割算法圖結(jié)構(gòu)

如圖所示的兩類(lèi)邊如果細(xì)分可以分為三類(lèi)，一類(lèi)是與S相連的t-link，一類(lèi)是與T相連的t-link，這兩類(lèi)邊的賦值與2.1小節(jié)的概率模型相關(guān)，采用與文獻(xiàn)[5]類(lèi)似的log-likelihook函數(shù)，n-link采用ad-hoc函數(shù)，其中深度信息在ad-hoc中的引入也采用概率模型類(lèi)似的方法，引入平衡因子α，來(lái)平衡深度信息在懲罰項(xiàng)中的重要性。剩下的問(wèn)題將是如何確定α，由于引入了直方圖來(lái)對(duì)深度信息建模，看到由直方圖組成的概率向量能清楚地表達(dá)深度信息的分布，而這種分布之間的差異可以用向量之間的距離來(lái)表達(dá)。

圖3即為一個(gè)關(guān)于深度信息的概率直方圖，前景和背景的概率直方圖類(lèi)似。給出的是前景深度的概率直方圖。

圖3 深度信息直方圖

不同的圖形即表示不同的類(lèi)，柱狀的高低則表示概率大小，這樣由概率組成的向量可以完全表示直方圖的形狀，向量之間的距離可以表示直方圖之間的差異程度，而且在概率直方圖中可以直接來(lái)用于α值，即：，由如上公式可知0≤α≤1，并且α值越大則說(shuō)明前背景之間的深度信息差異越大，僅僅依靠深度信息即能有效地把目標(biāo)分割出來(lái)。

對(duì)于圖割來(lái)說(shuō)權(quán)值確定是非常重要的，怎樣有效地利用不同的信息以及這些信息之間有效地結(jié)合在一起從而達(dá)到對(duì)圖像的有效分割，各種顏色、文理、深度以及區(qū)域邊界之間的結(jié)合和平衡的掌握對(duì)于一個(gè)圖像分割的方法來(lái)說(shuō)非常重要。如前所述，已經(jīng)對(duì)于兩種t-link和一種n-link的值的確定已經(jīng)基本了解，t-link采用log-likelihoods函數(shù)，n-link采用ad-hoc函數(shù)，但是與S節(jié)點(diǎn)相連的t-link和與T節(jié)點(diǎn)相連的t-link都是采用log-likelihoods函數(shù)，它們的概率模型訓(xùn)練的參數(shù)卻不一樣，即雖然它們有相同的概率模型，都是混合高斯模型和直方圖模型結(jié)合的概率模型，但是人為先驗(yàn)卻是不同的，用戶(hù)交互時(shí)已經(jīng)把需要的前景像素和背景像素基本確定，所以以?xún)煞N不同的權(quán)值來(lái)定義這兩類(lèi)t-link，具體的權(quán)值如表1所示。

表1 各種邊的權(quán)值

通過(guò)α可以有效地結(jié)合顏色紋理和深度信息，使圖像在前背景顏色相似卻深度不同的情況下能有效地利用深度的不同，即α值的偏大而偏重利用深度信息，這對(duì)于自動(dòng)的圖像分割是非常有效的，能自動(dòng)確定圖像分割時(shí)所利用的深度信息和顏色信息的比重，從而得到精確分割。

2.3 分層求解

通過(guò)實(shí)驗(yàn)發(fā)現(xiàn)圖割算法求解是非常緩慢的，而圖割中時(shí)間的消耗主要在于混合高斯概率模型的EM迭代算法，這種循環(huán)迭代的耗時(shí)是非常不可容忍的，因?yàn)樵诘鷪D割算法中前幾輪迭代中用戶(hù)給出的前景信息大概只是包括了前景信息，同時(shí)也包含了背景的信息，同時(shí)前幾輪的分割也沒(méi)有達(dá)到精確的分割，分割的目的是在最后一步分割中得到理想的分割要求，了解到這樣后，由于通過(guò)大量實(shí)驗(yàn)絕大部分情況下，圖割算法只需迭代三到四輪后就可以得到用戶(hù)理想的要求，很多國(guó)內(nèi)學(xué)者了解到此種情況后，紛紛用多尺度的方法來(lái)加快EM概率建模的過(guò)程，把圖像金字塔建立三四層高度使得和迭代圖割算法的迭代次數(shù)相當(dāng)?shù)那闆r下，可以有效地減少得到理想圖割效果的時(shí)間，并且不降低分割的精度，這是肯定的，因?yàn)榧热粓D割算法的大部分時(shí)間花在概率建模上，在初始的階段又不需要精確的概率模型。通過(guò)多尺度來(lái)降低建模的樣本數(shù)量當(dāng)然可以有效地減少分割所消耗的時(shí)間。

如文獻(xiàn)[14-15]就是通過(guò)多尺度來(lái)研究迭代圖割加快算法的一個(gè)例子，他們通過(guò)取四鄰域中的最大值作為圖像金字塔上層的像素來(lái)對(duì)上層進(jìn)行概率建模，這種取最大值的方法對(duì)于圖像有噪聲的情況下是非常不利的，他們的分割加快算法明顯忽視了圖像噪聲的情況，并且對(duì)于沒(méi)有噪聲的情況下，去最大值也是很牽強(qiáng)的。本文采用了多尺度的思想，但是幅度更大，不是通過(guò)四鄰域來(lái)對(duì)圖像像素進(jìn)行抽取，而是通過(guò)四領(lǐng)域，這種大幅度的抽取過(guò)程可以通過(guò)桶排序來(lái)有效地抽取典型樣本，從而有效地避免噪聲點(diǎn)和不重要的樣本點(diǎn)，另一層原因是在深度信息往往含有很多噪聲點(diǎn)，這些點(diǎn)的深度信息由于透明或者別的什么原因而無(wú)法獲取，如果利用去掉最大和最小的顏色和深度都典型的樣本點(diǎn)，然后用樣本點(diǎn)的深度信息，來(lái)對(duì)那些無(wú)法獲取深度信息的噪聲點(diǎn)的信息進(jìn)行替換，則可以取得一舉兩得的好處。通過(guò)對(duì)小樣本的一遍掃描即可排除那些噪聲點(diǎn)也不會(huì)對(duì)分割時(shí)間產(chǎn)生很大的影響，消耗時(shí)間和文獻(xiàn)[14]是一樣的。文獻(xiàn)[16-17]中的分水嶺算法在分水嶺的過(guò)分割的基礎(chǔ)上，把分水嶺的分割結(jié)果當(dāng)做圖割算法的超像素，雖然也能做圖像分割，但是分水嶺方法無(wú)法適用于深度圖像。

本文采用2×2小塊作為上層圖像像素的抽取單位，通過(guò)找出2×2像素中顏色絕對(duì)值和最大和最小的像素點(diǎn)，并且找到深度信息最大和最小的像素點(diǎn)，排除這些像素點(diǎn)后，如果剩余的點(diǎn)還有，則用剩余的點(diǎn)代表這4個(gè)點(diǎn)，如果沒(méi)有剩余的點(diǎn)，則忽略深度信息的最大和最小點(diǎn)，用顏色信息所剩余的兩個(gè)點(diǎn)作為抽樣點(diǎn)來(lái)進(jìn)行上層圖像的搭建，通過(guò)此方法得到的樣本像素點(diǎn)可以充分代表圖像的本質(zhì)信息而不會(huì)受噪聲點(diǎn)以及深度信息無(wú)法獲取的點(diǎn)的影響。

2.4 能量最小化

對(duì)于圖割算法來(lái)說(shuō)，最重要的就是圖結(jié)構(gòu)以及圖中邊權(quán)值的確定，求解可以采用最大流/最小割算法。文獻(xiàn)[8]對(duì)于圖割算法求解的最大流/最小割算法進(jìn)行了實(shí)驗(yàn)性的研究，發(fā)明了一種雖然在理論上時(shí)間復(fù)雜度比一般最大流算法的時(shí)間復(fù)雜度O(ne2)高的算法，它的理論最大復(fù)雜度為O(|c|ne2)，其中|c|為割的數(shù)量，但在實(shí)際的實(shí)驗(yàn)過(guò)程中由于圖割算法圖的特殊性，導(dǎo)致這個(gè)算法可以比一般的算法節(jié)省幾倍的時(shí)間，它是通過(guò)在圖的兩端構(gòu)建樹(shù)并擴(kuò)展和領(lǐng)養(yǎng)孤兒節(jié)點(diǎn)來(lái)增加圖中的通路，并最終求得最大流。本文采用了文獻(xiàn)[8]類(lèi)似的方法來(lái)求解最大流。

3 改進(jìn)圖割實(shí)施流程

本文的方法是融合深度的分層圖割算法研究，此算法的精髓在于用直方圖來(lái)對(duì)深度信息建模，并且引入平衡因子α來(lái)對(duì)圖像的顏色紋理信息和深度信息之間的協(xié)調(diào)因子，當(dāng)前景和背景的深度信息相差明顯時(shí)，α因子就接近于1，也就是說(shuō)僅僅依靠深度信息就能夠很好地分割出圖像中的目標(biāo)，當(dāng)前景和背景的深度信息相差不大時(shí)，α接近于0時(shí)，就利用顏色和紋理信息來(lái)對(duì)圖像進(jìn)行分割。除了引入深度信息，對(duì)于分層的引入也能夠加快圖割算法的步驟，因?yàn)槿缥墨I(xiàn)[11]中所述圖割只有在最后一次循環(huán)時(shí)才得到精確的分割結(jié)果，所以前幾次的前景和背景的分層提取并不影響最終的分割結(jié)構(gòu)。

下面詳細(xì)闡述算法的總體流程，首先的第一步是用戶(hù)用鼠標(biāo)拖出一個(gè)矩形框，在矩形框中的像素為可能前景，但是在概率建模的時(shí)候先當(dāng)這個(gè)矩形框內(nèi)的為前景，至少它包含了前景的像素，在循環(huán)迭代的過(guò)程中，一次一次地以上一次的分割結(jié)果作為下一次的概率建模依據(jù)就能逐漸接近于用戶(hù)想要的概率模型。在矩形框外的就是絕對(duì)背景用它作為背景概率建模的樣本數(shù)據(jù)。以用戶(hù)的矩形和圖像作為本算法的輸入，接下去就是執(zhí)行本算法，算法的第一個(gè)基本初始化工作時(shí)建立三層金字塔，以2×2為提取像素的基本單位，在源圖像的基礎(chǔ)上以2×2為單位提取這當(dāng)中的樣本像素，掃描這4個(gè)像素找出其中的顏色絕對(duì)值最大的和最小的像素，并且同時(shí)掃描深度圖像也找出深度的最大值和最小值，在去除這四個(gè)像素的基礎(chǔ)上，用隨機(jī)算法在剩下的像素中隨機(jī)選擇一個(gè)像素用作多尺度圖像分割上層的概率建模樣本，同理可以在提取一次建立三層的圖像金字塔。當(dāng)這些初始化工作做好之后，在最上層用EM算法對(duì)顏色進(jìn)行混合高斯建模，并通過(guò)一遍掃描深度圖建立深度信息直方圖，即概率向量，再同時(shí)結(jié)合用戶(hù)給定的矩形框，當(dāng)然在金字塔上層時(shí)矩形框也要相應(yīng)的縮小，建立前景概率模型和背景概率模型，用得到的概率模型結(jié)合表1建立起圖割算法的圖結(jié)構(gòu)，建立圖結(jié)構(gòu)時(shí)是用原始圖像來(lái)建立的，也就是說(shuō)執(zhí)行最大流算法時(shí)在原圖上進(jìn)行，在第二次迭代中通過(guò)第一次得到的分割結(jié)果，再通過(guò)2×2的樣本抽取方法，在圖像金字塔的中間層建立起概率模型，再在原始圖像上通過(guò)重新建立起來(lái)的圖結(jié)果執(zhí)行最大流算法得到分割結(jié)果，最后就一直在原始的圖像上建立概率模型和執(zhí)行最大流算法分割。雖然只進(jìn)行了3層的多尺度的結(jié)合，但是對(duì)于迭代圖割算法的結(jié)合是非常到位的，因?yàn)橥ㄟ^(guò)大量實(shí)驗(yàn)得到在大部分的情況下，圖割的執(zhí)行基本上3～4次就能得到理想的分割效果，下面以更加簡(jiǎn)潔的語(yǔ)言及步驟來(lái)解釋本文算法的流程：

（1）對(duì)于圖像像素，用戶(hù)通過(guò)框定矩形得到圖像的可能前景和絕對(duì)背景。

（2）通過(guò)2×2的樣本抽樣建立起三層的圖像金子塔，抽取方法如上所述，去掉極端值隨機(jī)選擇算法。

（3）在最上層圖像上進(jìn)行EM混合高斯和直方圖概率建模得到前景和背景的概率模型，概率模型公式如下：

（4）建立圖割圖結(jié)構(gòu)執(zhí)行最大流改進(jìn)算法。

（5）執(zhí)行邊界映射到第二層繼續(xù)概率建模。

（6）建立圖割圖結(jié)構(gòu)執(zhí)行最大流改進(jìn)算法。

（7）分割結(jié)構(gòu)在原圖上建立概率模型。

（8）執(zhí)行步驟（6）直到分割滿(mǎn)意為止。

以上就是本文提到的深度圖像分層分割的全部算法流程，其優(yōu)點(diǎn)在于利用直方圖來(lái)對(duì)深度信息建模，并通過(guò)引入平衡因子α來(lái)對(duì)顏色紋理信息和深度信息之間進(jìn)行自動(dòng)的取舍，并用分層提取的方法避免噪聲和有效地加快圖割算法的執(zhí)行時(shí)間。在前人研究的基礎(chǔ)上可以說(shuō)做了很大的改進(jìn)，改進(jìn)的方式在于引入了深度信息，可以利用更多的信息來(lái)進(jìn)行圖像分割后，怎樣平衡這引入的信息和原來(lái)信息之間的重要性程度將是非常關(guān)鍵的，在以往的前人的研究中都只是單純當(dāng)做新的一維的信息而加入到混合高斯模型中去建立四維的混合高斯模型，這種不加區(qū)分的加入雖然也能取得一定的效果，通過(guò)引入平衡因子則更加有效。下面將給出本文方法的實(shí)驗(yàn)結(jié)果和對(duì)實(shí)驗(yàn)結(jié)果的分析。

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

利用本文算法來(lái)對(duì)圖像進(jìn)行分割，在時(shí)間和分割進(jìn)度上來(lái)對(duì)標(biāo)準(zhǔn)的圖割算法進(jìn)行對(duì)比，在分割精度基本不變的情況下大大縮短了分割所需的時(shí)間，并且可以在顏色信息無(wú)法正確區(qū)分的情況下依然對(duì)圖像進(jìn)行正確的分割。

由于本算法實(shí)行的是深度圖像的分割，而一些圖割算法的標(biāo)準(zhǔn)圖沒(méi)有深度信息，所以本文采用隨機(jī)生成灰度圖的方法來(lái)自動(dòng)生成深度信息來(lái)對(duì)標(biāo)準(zhǔn)圖形進(jìn)行分割，由于是隨機(jī)生成的，所以前景和背景的深度信息直方圖即概率向量基本相同，這導(dǎo)致平衡參數(shù)α非常小，所以本質(zhì)上來(lái)說(shuō)主要看的還是顏色紋理信息，并不影響分割精度，接下去就把這種用自動(dòng)生成的深度圖的方法應(yīng)用于圖割算法的標(biāo)準(zhǔn)圖中來(lái)對(duì)耗時(shí)和分割結(jié)果進(jìn)行對(duì)比，目標(biāo)是在耗時(shí)下降的情況下，分割的精度上卻沒(méi)有下降。

有圖可知，在圖4（a）的原始圖像輸入和用戶(hù)矩形輸入的情況下，本文的算法可以建立起圖像金字塔模型，每層圖像都是前一次的分割結(jié)果的輸入，第一次的輸入是用戶(hù)輸入的矩形，由圖4（b）可知圖像的概率模型是在圖像金字塔基礎(chǔ)之上的，每次的分割結(jié)果都用黑線(xiàn)來(lái)表示，在黑線(xiàn)內(nèi)部為用作前景概率建模的像素樣本，在黑線(xiàn)以外的是用作背景概率建模的像素樣本，由于深度信息采用的是隨機(jī)生成的灰度圖，實(shí)驗(yàn)得到的三次結(jié)果的α都很小，每一次α≤0.01基本不起什么作用，所以可以看出基本還是顏色的混合高斯模型在起作用，但是時(shí)間卻大大縮短，下面給出三次迭代的時(shí)間消耗比。

圖4 算法精度對(duì)比

由圖5和表2可知算法在前面階段上的耗時(shí)減少了將近一半，在總體上的算法執(zhí)行時(shí)間也節(jié)約了30%，但是圖像分割最后的精度卻沒(méi)有受到任何影響。

圖5 算法時(shí)間對(duì)比

表2 算法耗時(shí)比

下面再用真正的深度圖像來(lái)作為算法輸入，比較兩算法的性能。

圖6 （a）RGB圖像

圖6 （b）深度圖像

圖7 深度圖像分割結(jié)果比較

圖7左邊為迭代圖割算法的分割結(jié)果（深度信息單純作為第四維信息）右邊為算法分割結(jié)果由實(shí)驗(yàn)結(jié)果發(fā)現(xiàn)此時(shí)的深度信息在實(shí)驗(yàn)過(guò)程中將起決定性作用，事實(shí)也是這樣通過(guò)追蹤α的值可知，在三次迭代中α的值都大于0.7由此可知完全可有深度信息作為圖像分割的依據(jù)，由圖7可知單純把深度作為第四維信息加入到混合高斯建模中是行不通的，這樣完全不知道深度信息的重要性。通過(guò)實(shí)驗(yàn)得知算法可以自動(dòng)判斷深度信息的重要程度，從而來(lái)對(duì)深度圖像進(jìn)行正確分割，在深度信息明顯時(shí)利用深度信息，在深度信息不明顯時(shí)則利用顏色信息來(lái)對(duì)圖像進(jìn)行分割。

5 結(jié)論

雖然本文改進(jìn)了迭代圖割算法的執(zhí)行效率，對(duì)深度圖像的深度信息進(jìn)行了有效的利用，但是本文的方法也有很大的局限性，且并沒(méi)有確切給出σ的計(jì)算公式，在迭代圖割算法中利用了矩陣來(lái)求σ的值，本文也只是在其中加入深度信息，單純地利用四維矩陣求出了σ的值，在以后的研究中，將對(duì)這里做改進(jìn)，以期能更好地理解圖割算法的意義和圖割算法的性能。

[1]Reese L J.Intelligent paint：Region-based interactive image segmentation[D].Brigham Young University，1999.

[2]Najman L，Couprie M，Bertrand G.Watersheds，mosaics，and the emergence paradigm[J].Discrete Applied Mathematics，2005，147（2/3）：301-324.

[3]Mortensen E N，Barrett W A.Interactive segmentation with intelligent scissors[J].Graphical Models and Image Processing，1998，60：349-384.

[4]Lindeberg T，Li M X.Segmentation and classification of edges using minimum description length approximation andcomplementaryjunctioncues[J].ComputerVision and Image Understanding，1997，67（1）：88-98.

[5]Greig M D，Porteous B T，Seheult H A.Exact maximum a posteriori estimationfor binaryimages[J].Journal of the Royal Statistical Society，1989，51（2）：271-279.

[6]Shi J，Malik J.Normalized cuts and image segmentation[C]// CVPR，1997：731-737.

[7]Boykov Y，Jolly M.Interactive graph cuts for optimal boundary ®ion segmentation of objects in N-D images[C]//ICCV，2001.

[8]Boykov Y，Kolmogorov V.An experimental comparison of min-cut/max-flow algorithms for energy minimization in vision[C]//EMMCVPR，2001.

[9]Delong A，Veksler O，Boykov Y.Recursive MDL via graph cuts：Application to segmentation[C]//ICCV，2011：890-897.

[10]Jegelka S，Bilmes J.Submodularity beyound submodular energies：Coupling edges in graph[C]//CVPR，2011：1897-1904.

[11]Rother C，Kolmogorov V，Black A.GrabCut：Interactive foreground extraction using iterated graph cuts[J].ACM Trans on Graphics，2004，23（3）：309-314.

[12]劉榮，彭艷敏.基于分水嶺與圖割的自動(dòng)分割方法[J].北京航空航天大學(xué)學(xué)報(bào)，2012，38（5）.

[13]Couprie C，Grady L，Najman L，et al.Power watershed：a new image segmentation framework extending graph cuts，random walker and optimal spanning forest[C]//ICCV，2009.

[14]徐秋平，郭敏，王亞榮.基于多尺度分析與圖割的快速圖像分割算法[J].計(jì)算機(jī)應(yīng)用研究，2009，26（10）.

[15]Li Y，SunJ，TangCK，etal.A multilevelbanded graphcutsmethodforfastimagesegmentation[C]// Proc of ICCV，2005：259-265.

[16]Vicente S，Kolmogorov V，Rother C.Graph cut based image segmentation with conectivity priors[C]//CVPR，2008.

[17]Vicente S，Kolmogorov V，Rother C.Joint optimization of segmentation and appearance models[C]//ICCV，2009.

[18]Rother C，Kolmogorov V，Boykov Y，et al.Interactive Foreground Extraction using graph cut[R].Microsoft Technical Report，2011.

YU Jiangming,ZHAO Jieyu,WANG Guofeng

1.Research Institute of Information Science and Technology,Ningbo University,Ningbo,Zhejiang 315211,China
2.Zhejiang Provincial Welfare Lottery Center,Hangzhou 310000,China

Based on the iterative graph cut method,this paper uses image pyramid to accelerate the speed of segmentation and introduces a balance factor to determine the significance between the color and depth information.This method can segment the depth image easily and precisely with the pyramid and the balance factor.The balance factor is the measure of the discrimination for the color and depth information.If the depth information is sufficient to distinguish the object from the background,then the depth information plays a more important role in the segmentation process,otherwise the color information takes more important role.By using the image pyramid our method can interact with the iterative graph cuts and greatly reduces the processing time without influencing the segmentation precision.

iterative graph cuts;balance factor;Gaussian mixture;depth histogram

以深度圖像為分割對(duì)象，在迭代圖割算法的基礎(chǔ)上，通過(guò)引入分層機(jī)制加快圖割執(zhí)行速度，并通過(guò)引入平衡因子來(lái)平衡顏色紋理和深度之間的重要程度，從而有效地對(duì)深度圖像進(jìn)行分割。利用平衡因子可以在深度信息能夠明顯區(qū)分前背景的情況下，重點(diǎn)利用深度信息來(lái)分割圖像，反之則重點(diǎn)利用顏色和紋理信息。而在迭代圖割算法中，分層機(jī)制的引入能夠在不降低分割精度的情況下有效地減少圖割算法的執(zhí)行時(shí)間。

迭代圖割；平衡因子；混合高斯；深度直方圖

A

TP393

10.3778/j.issn.1002-8331.1212-0363

YU Jiangming,ZHAO Jieyu,WANG Guofeng.Depth image segmentation using layered graph cuts.Computer Engineering and Applications,2014,50（22）：183-188.

國(guó)家自然科學(xué)基金（No.61175026）；浙江省自然科學(xué)基金重大項(xiàng)目（No.D1080807）；國(guó)家國(guó)際科技合作項(xiàng)目（No.S2013GR0113）。

俞江明（1987—），男，碩士研究生，主要研究領(lǐng)域?yàn)閳D形圖像處理，模式識(shí)別；趙杰煜（1965—），男，博士，教授，主要研究領(lǐng)域?yàn)閳D形圖像處理；汪國(guó)鋒（1971—），男，工程師，主要研究領(lǐng)域?yàn)橛?jì)算機(jī)網(wǎng)絡(luò)和數(shù)據(jù)庫(kù)。E-mail：yjm_luohua@sina.com

2012-12-30

2013-03-04

1002-8331（2014）22-0183-06

CNKI網(wǎng)絡(luò)優(yōu)先出版：2013-03-29,http://www.cnki.net/kcms/detail/11.2127.TP.20130329.1540.002.html