基于四叉樹分解與圖割的彩色圖像快速分割*

胡志立，郭 敏

(1.現(xiàn)代教育技術(shù)教育部重點(diǎn)實(shí)驗(yàn)室，陜西 西安 710062;2.陜西師范大學(xué)計(jì)算機(jī)科學(xué)學(xué)院，陜西 西安 710062)

1 引言

圖像分割將圖像劃分為有意義的若干區(qū)域或者用于提取人們感興趣的區(qū)域，它在計(jì)算機(jī)視覺、模式識(shí)別和圖像工程等學(xué)科中都發(fā)揮著重要的作用。圖割作為一種基于圖論的組合優(yōu)化方法，可以用來最小化計(jì)算機(jī)視覺中的能量函數(shù)問題。Greig D等[1]首次將圖割應(yīng)用于圖像處理領(lǐng)域，同時(shí)他們最早提出使用功能強(qiáng)大的最小割/最大流算法來最小化計(jì)算機(jī)視覺中的能量函數(shù)；隨著Boykov Y等[2,3]將其應(yīng)用到圖像分割領(lǐng)域，引發(fā)了國際上對(duì)圖割理論及其應(yīng)用的研究熱潮。Boykov Y等[4]提出了基于增廣路徑的新方法：擴(kuò)展移動(dòng)(Expansion-moves)和交換移動(dòng)(Swap-moves)，有效地提高了最小割/最大流算法的效率。Li Y等[5]首先利用分水嶺(Watershed)算法對(duì)圖像進(jìn)行預(yù)分割，將圖像分成很多內(nèi)部顏色較為一致的小區(qū)域；然后將每個(gè)小區(qū)域作為一個(gè)節(jié)點(diǎn)，利用圖割方法進(jìn)行劃分，得到最終分割的圖像；利用小區(qū)域代替區(qū)域內(nèi)部像素點(diǎn)構(gòu)造出來的圖的節(jié)點(diǎn)明顯減少，然而由于預(yù)分割本身的時(shí)間較長(zhǎng)，所以對(duì)圖割時(shí)間上的改進(jìn)較少。Blake A等[6]使用高斯混合模型GMM(Gaussian Mixture Model)對(duì)前景和背景顏色空間進(jìn)行建模，從而能夠較好地利用圖像的顏色信息對(duì)彩色圖像進(jìn)行分割。Rother C等[7]提出的GrabCut采用多次迭代圖割進(jìn)行圖像分割，它只需要用戶指定一個(gè)圍繞目標(biāo)的矩形框便可提取感興趣的目標(biāo)，有效減少了用戶交互量。

利用GrabCut多次迭代圖割進(jìn)行圖像分割，在處理海量級(jí)圖像數(shù)據(jù)時(shí)，耗時(shí)往往比較大。其切割實(shí)質(zhì)是迭代使用圖割進(jìn)行高斯混和模型GMM參數(shù)估計(jì)，直到滿足收斂條件，從而完成圖像分割。整個(gè)過程中確定GMM參數(shù)成本高，這制約了整個(gè)算法的時(shí)效性。徐秋平等[8]引入多尺度分析方法，以塔式分解的多尺度圖像序列代替原始圖像進(jìn)行GMM參數(shù)迭代估計(jì)，以較少樣本快速確定GMM參數(shù)，分割精度不減而效率顯著提高。徐秋平等[9]使用分水嶺變換對(duì)圖像進(jìn)行預(yù)處理，以部分具有典型代表的樣本點(diǎn)來估計(jì)GMM參數(shù)，這有效地提高了GrabCut算法的效率。韓守東等[10]利用多尺度非線性張量紋理特性(MSNST)描述圖像的紋理特征并構(gòu)建基于MSNST的GMM，使得MSNST能有效地與GrabCut結(jié)合；他們還提出一種自適應(yīng)融合策略來調(diào)整混合因子，以有效地融合圖像的色彩特征和MSNST紋理特征，從而得到比GrabCut更好的分割效果。韓守東等[11]在MSNST空間利用獨(dú)立尺度分量形式黎曼協(xié)方差高斯混合模型(ICRGMM)在紋理聚類中的優(yōu)勢(shì)取代GMM，為了更精確地估計(jì)和更新統(tǒng)計(jì)參數(shù)，使用分量形式期望最大化代替GrabCut原有的K-means算法，使得算法能有效地分割紋理圖像而且對(duì)自然場(chǎng)景圖像也有不錯(cuò)的分割效果；韓守東等[12]使用高斯超像素來構(gòu)建圖割模型以實(shí)現(xiàn)加速，他們使用快速均值漂移算法對(duì)圖像進(jìn)行預(yù)分割，從而構(gòu)建精簡(jiǎn)的加權(quán)圖。為了準(zhǔn)確而精煉地對(duì)先驗(yàn)知識(shí)進(jìn)行參數(shù)化學(xué)習(xí)，他們還使用了分量形式的期望最大化混合高斯算法對(duì)用戶交互進(jìn)行聚類，使得算法在精確性方面和高效性方面都有較好的性能。

基于合并區(qū)域然后將整個(gè)區(qū)域看作一個(gè)超像素進(jìn)行GMM參數(shù)估計(jì)以減小問題規(guī)模的思想，本文使用四叉樹分解來得到區(qū)域內(nèi)顏色相近的圖像塊，我們將整個(gè)區(qū)域塊描述成超像素，每個(gè)超像素點(diǎn)對(duì)應(yīng)著網(wǎng)絡(luò)圖的節(jié)點(diǎn)，相鄰像素間的差異對(duì)應(yīng)著邊上的容量，以此構(gòu)建精簡(jiǎn)的網(wǎng)絡(luò)圖，并用塊內(nèi)的RGB均值代替該塊內(nèi)的所有像素點(diǎn)的值進(jìn)行高斯混合模型參數(shù)估計(jì)，從而減小問題規(guī)模，達(dá)到提高GrabCut算法時(shí)效的目的。

2 相關(guān)研究

2.1 四叉樹分解

四叉樹分解的目標(biāo)是將原始圖像逐步分成小塊，操作的原理是將具有一致性(像素間的灰度差值小于給定的閾值)的像素分到同一小塊中。四叉樹分解過程如下：令R表示當(dāng)前進(jìn)行分解的圖像區(qū)域，并選擇一個(gè)屬性Q(區(qū)域的像素間滿足一致性標(biāo)準(zhǔn))。如果有Q(R)=FALSE，則將該圖像區(qū)域分割為四個(gè)象限區(qū)域。對(duì)于其中的任意一個(gè)區(qū)域，如果仍有Q(R)=FALSE，則將該象限區(qū)域再次細(xì)分為四個(gè)象限區(qū)域，以此類推，直到圖像中的所有區(qū)域都滿足一致性標(biāo)準(zhǔn)才停止。最后，四叉樹分解的結(jié)果可能包括多種不同尺寸的方塊。由此原理可知，當(dāng)圖像是正方形，且像素點(diǎn)的行數(shù)和列數(shù)是2的整數(shù)次冪時(shí)，四叉樹分解算法是最適用的。對(duì)于其它圖形可以通過適當(dāng)填充來獲得合適的圖像。

2.2 圖割簡(jiǎn)介

圖割是一種基于圖論的組合優(yōu)化方法，它將一幅圖像映射成一個(gè)網(wǎng)絡(luò)圖，并建立關(guān)于標(biāo)號(hào)的能量函數(shù)；然后運(yùn)用最大流/最小割算法對(duì)網(wǎng)絡(luò)圖進(jìn)行切割，得到網(wǎng)絡(luò)圖的最小割，即能量函數(shù)的最小值。設(shè)G=(V,E)為一個(gè)帶有非負(fù)邊權(quán)的有向圖，其中V為頂點(diǎn)集，對(duì)應(yīng)圖像的像素點(diǎn)集P，E為邊集。V包含兩個(gè)特殊的頂點(diǎn)，通常一個(gè)稱為源S，一個(gè)稱為匯T。每個(gè)頂點(diǎn)有兩個(gè)邊，連接源和匯的邊稱為t-links，反映當(dāng)前頂點(diǎn)對(duì)于標(biāo)記的偏好程度；鄰域連接n-links反映了頂點(diǎn)之間的差異性。最小割就是圖G所有割中容量最小的割，它可根據(jù)Ford L和Fulkerson D[13]提出的網(wǎng)絡(luò)流理論，通過求網(wǎng)絡(luò)圖的最大流而得到。

2.3 GrabCut算法

GrabCut將圖像表示為矢量Z={z1,z2,…,zn,…,zN}，將該圖像的分割表示為求每個(gè)像素點(diǎn)的值α={α1,α2,…,αn,…,αN}，αn∈{0,1}，其中0表示背景，1表示前景。GrabCut使用兩個(gè)GMM，一個(gè)對(duì)應(yīng)背景，另一個(gè)對(duì)應(yīng)前景。每個(gè)GMM由K個(gè)高斯模型混合而成(通常K=5)，每個(gè)像素有一個(gè)參數(shù)kn(kn∈{1,…,K})，參數(shù)來自前景還是背景取決于αn的取值。GrabCut算法的Gibbs能量函數(shù)形式為[7]：

E(α,k,θ,z)=U(α,k,θ,z)+V(α,z)

(1)

其中，θ代表圖像的GMM參數(shù)。

數(shù)據(jù)項(xiàng)U定義為：

(2)

其中：

D(αn,kn,θ,zn)=

-logp(zn|αn,kn,θ)-logπ(αn,kn)

(3)

其中，p(·)為高斯概率分布；π(·)為混合權(quán)重系數(shù)，也就是kn為某一個(gè)值的像素?cái)?shù)占總的像素?cái)?shù)的比例。

于是有：

D(αn,kn,θ,zn)=-logπ(αn,kn)+

0.5log det∑(αn,kn)+0.5[zn-

μ(αn,kn)]T∑(αn,kn)-1[zn-μ(αn,kn)]

(4)

那么，參數(shù)θ可表示為：

θ={π(α,k),μ(α,k),

∑(α,k),α=0,1,k=1,…,K}

(5)

平滑項(xiàng)V可用RGB空間的歐幾里德距離求得：

(6)

GrabCut算法的主要流程如下：

整個(gè)GMM參數(shù)的迭代估計(jì)是在TU中進(jìn)行的，根據(jù)標(biāo)定的背景區(qū)域和未知區(qū)域初始化GMM，以下述(1)～(3)對(duì)TU迭代直至收斂：

如果當(dāng)前得到的能量值記為E(i)，上次迭代輸出的能量值為E(i-1)，那么可以將能量變化率定義為：Rate=(E(i-1)-E(i))/E(i-1)，可以將能量變化率是否小于給定的閾值作為判斷GMM參數(shù)估計(jì)是否收斂的條件。算法收斂后，TF=TU,這樣就分隔出所需的前景部分。

3 基于四叉樹分解和GrabCut的彩色圖像分割方法

3.1 GrabCut算法改進(jìn)分析

從GrabCut算法的流程可知，其N次迭代收斂過程可分為兩部分：前N-1次迭代使用最大流進(jìn)行分割，目的是學(xué)習(xí)、修正GMM參數(shù)，第N次分割實(shí)現(xiàn)最終的圖像分割。既然前N-1次分割是為了確定GMM參數(shù)，而每次使用最大流去最小化能量函數(shù)的時(shí)間開銷往往比較大，那么使用超像素的方法合并相似的區(qū)域，然后再對(duì)該塊狀圖構(gòu)造網(wǎng)絡(luò)圖并求解該網(wǎng)絡(luò)圖的最大流/最小割，這樣就可以有效減少確定GMM參數(shù)的時(shí)間消耗。最后，為了使得分割結(jié)果盡可能地接近原始算法的精度，我們使用最終得到的GMM參數(shù)對(duì)原始圖像的TU部分進(jìn)行分割，從而得到最終結(jié)果。

對(duì)于一幅2N×2N(如果圖像不是2N×2N，可以適當(dāng)?shù)剡M(jìn)行填充)的圖像，給定閾值進(jìn)行四叉樹分解，能夠快速地找到圖像中滿足一致性標(biāo)準(zhǔn)的正方形區(qū)域。對(duì)于灰度圖像，灰度變化值小于給定閾值的像素將會(huì)被合并到同一個(gè)區(qū)域；對(duì)于彩色圖像，在RGB分量上變化的均值小于給定閾值的像素會(huì)被合并到同一個(gè)區(qū)域。閾值設(shè)置得越高，就會(huì)有越多的像素被劃分到同一分塊中，從而分割速度越快，然而過高的閾值使得圖像細(xì)節(jié)喪失過多，使得最終出現(xiàn)過分割。

綜上所述，本文提出的改進(jìn)思路是：設(shè)置適當(dāng)?shù)拈撝颠M(jìn)行四叉樹分解，得到區(qū)域內(nèi)相似度比較高且拓?fù)浣Y(jié)構(gòu)相對(duì)規(guī)則的塊狀圖，進(jìn)而使用各個(gè)塊中的RGB均值作為該塊的超像素值，然后再進(jìn)行GMM參數(shù)估計(jì)，最后為保證精度，我們使用得到的GMM參數(shù)對(duì)原始的圖像進(jìn)行分割，從而達(dá)到提高分割速度而精度不減的目的。對(duì)于默認(rèn)的閾值，如果分割結(jié)果跟原算法相比存在明顯的過分割，可以降低閾值，直到達(dá)到原算法的精度。一般情況下，待提取目標(biāo)的邊界兩側(cè)在顏色上會(huì)有一定程度的差異，只要設(shè)置好適當(dāng)?shù)拈撝?，本文的算法便是可行的?/p>

3.2 塊狀圖的生成

由于四叉樹分解總是將滿足一致性的區(qū)域分解成大小相同的四個(gè)正方形區(qū)域，所以首先要將不是2N×2N的圖像填充成使N盡可能小的2N×2N的圖像再將其轉(zhuǎn)換成灰度圖像，然后進(jìn)行四叉樹分解，最后分別將此分解應(yīng)用到彩色圖像的RGB分量上?？紤]到直接對(duì)填充后的圖像進(jìn)行處理，填充的區(qū)域會(huì)擁有較多的塊數(shù)(如將一幅513×513的圖像填充成1 024×1 024)，這樣會(huì)增加額外的處理時(shí)間，我們將分解后的圖像裁剪成原始大小，然后對(duì)裁剪后的圖像建立每塊的索引，并將方形區(qū)域內(nèi)每個(gè)像素的RGB值用該區(qū)域的RGB均值代替。將分塊圖中的每個(gè)分塊看作一個(gè)超像素，整個(gè)超像素圖可記作B={b1,b2,…,bn,…,bN}，N為節(jié)點(diǎn)個(gè)數(shù)。對(duì)于一幅牡丹圖像的處理效果如圖1所示(由圖1b可以看出，四叉樹分解算法可以在一定程度上保持原有的邊界信息和顏色信息，對(duì)原有邊界信息和顏色信息保持得越好，最終的分割結(jié)果就越接近GrabCut算法的精度)。

Figure 1 Comparison of quadtree decomposition result and orignal image圖1 四叉樹分解預(yù)處理結(jié)果與原始圖像對(duì)比圖

3.3 GMM參數(shù)迭代估計(jì)

3.3.1 初始化GMM參數(shù)

3.3.2 最小割進(jìn)行分割

Figure 2 Network graph and minmum cuts圖2 網(wǎng)絡(luò)圖與最小割

Figure 3 Results of the first cut圖3 第一次分割的結(jié)果

3.3.3 更新GMM參數(shù)、判斷收斂及后續(xù)處理

每一次最小割分割之后都會(huì)將TU中的節(jié)點(diǎn)分割成前景或者背景并輸出當(dāng)前的能量值，將TU中的前景節(jié)點(diǎn)作為樣本估計(jì)前景GMM參數(shù)，TU中的背景節(jié)點(diǎn)及TB作為樣本估計(jì)背景GMM參數(shù)。按照初始化GMM參數(shù)的方法計(jì)算kn、μ(α,k)、∑(α,k)、π(α,k)，并以此更新GMM參數(shù)。判斷收斂的方法與GrabCut一致。程序收斂以后分割的結(jié)果鋸齒現(xiàn)象十分明顯，為了保證處理的結(jié)果更接近GrabCut算法，我們用得到的GMM參數(shù)對(duì)原始像素圖的TU部分進(jìn)行一次分割得到最終結(jié)果。

3.4 算法的實(shí)現(xiàn)步驟

綜上所述，基于四叉樹與GrabCut的彩色圖像快速分割主要實(shí)現(xiàn)步驟如下：

(1)輸入彩色圖像I，將其填充成使得N盡可能小的2N×2N的圖像，再將其轉(zhuǎn)換成灰度圖像，然后進(jìn)行四叉樹分解，再將分解后的圖像裁剪成原始大小，然后根據(jù)此分解，生成塊狀圖，并建立關(guān)于每塊的索引。

(2)根據(jù)塊索引，初始化分塊圖的GMM：

②對(duì)于bn∈TB，有αn=0；bn∈TU，有αn=1；其中αn=0代表背景，αn=1代表前景，并以此初始化GMM。

(3)迭代估計(jì)GMM參數(shù)：

①初始化GMM參數(shù)。

②學(xué)習(xí)GMM參數(shù)。

③對(duì)超像素圖構(gòu)造網(wǎng)絡(luò)圖，并用最小割進(jìn)行分割。

④迭代①～③直至滿足收斂條件。

(4)根據(jù)所得到的GMM參數(shù)對(duì)原始圖像I構(gòu)造S-T網(wǎng)絡(luò)，并用最小割算法進(jìn)行分割。

(5)輸出分割的結(jié)果。

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

本文實(shí)驗(yàn)平臺(tái)為：64位Windows 7,Matlab R2011a,Microsoft Visual Studio 2010,CPU:Core i5-2450M,RAM:8 GB。對(duì)于每一幅圖像，人工設(shè)置一個(gè)矩形框選中目標(biāo)區(qū)域，然后輸出GrabCut算法、基于分水嶺變換改進(jìn)的GrabCut算法[8]和本文算法所提取到的目標(biāo)、二值的分割結(jié)果及三者的時(shí)間消耗對(duì)比圖。無論是使用分水嶺算法預(yù)處理得到分塊圖還是使用本文算法預(yù)處理得到分塊圖，都因問題規(guī)模的減小導(dǎo)致有時(shí)改進(jìn)的算法會(huì)比GrabCut算法早收斂，為了方便得到三者的時(shí)間消耗對(duì)比圖，我們使用規(guī)定最大迭代次數(shù)這種方法進(jìn)行處理，只要GrabCut算法已經(jīng)收斂,就不會(huì)對(duì)實(shí)驗(yàn)結(jié)果造成較大的影響。對(duì)于圖1中的原始圖片分割的效果如圖4所示。

Figure 4 Comparison of segmentation of three algorithms圖4 三種算法分割效果對(duì)比圖

由實(shí)驗(yàn)結(jié)果可看出，本文算法的精度與GrabCut基本一致，但時(shí)間上要優(yōu)于GrabCut。本文算法的時(shí)間消耗是1.295 s，GrabCut算法耗時(shí)8.814 s，本文算法的時(shí)間消耗僅占GrabCut算法的14.69%，通常情況下，基于分水嶺變換改進(jìn)的GrabCut算法與本文算法在時(shí)間上的改進(jìn)大致相當(dāng)，且能達(dá)到GrabCut算法的精度。

本文算法在運(yùn)用于圖像分辨率比較高且細(xì)節(jié)較少的情況下效果更好，圖5和圖6是對(duì)一組圖像測(cè)試的結(jié)果(其中企鵝圖像(680×509)、獵人圖像(680×500)、鯨圖像(1 024×720))。表1是對(duì)伯克利圖像分割測(cè)試圖庫的另一組圖片測(cè)試的結(jié)果。

Table 1 Time comparison between our algorithm and GrabCut

Figure 5 Segmentation resutls of three algorithms圖5 三種算法分割效果圖

Figure 6 Time comparison among three algorithms圖6 三種算法分割時(shí)間對(duì)比圖

從上面的圖和表可以看出，本文算法的分割效果與GrabCut非常接近，有的圖像人眼很難分辨兩種算法分割結(jié)果的優(yōu)劣，而時(shí)間上明顯優(yōu)于GrabCut。基于分水嶺變換改進(jìn)的GrabCut算法與本文算法一樣，都明顯提高了算法的時(shí)效性，而且精度上與GrabCut算法十分接近。

5 結(jié)束語

GrabCut是一種優(yōu)秀的交互式圖像分割算法，其用戶交互量少且分割精度高，然而它為了達(dá)到一定分割精度而采用多次迭代圖割的方式求解GMM參數(shù)，這使得處理海量級(jí)圖像數(shù)據(jù)時(shí)，時(shí)效性很低。針對(duì)該問題，本文使用了合并相似區(qū)域然后將整個(gè)區(qū)域看作一個(gè)超像素進(jìn)行GMM參數(shù)估計(jì)以減小問題規(guī)模的思想，并用四叉樹分解予以實(shí)現(xiàn)。實(shí)驗(yàn)結(jié)果表明，改進(jìn)的方法在加快GMM參數(shù)估計(jì)的同時(shí)，基本上保持了和原算法相當(dāng)?shù)姆指钚Ч?，這表明了該思想的可行性及有效性。此外，合并相似區(qū)域然后將整個(gè)區(qū)域看作一個(gè)超像素進(jìn)行處理的改進(jìn)思想也可以推廣到基于圖割理論進(jìn)行圖像分割、圖像鑲嵌、圖像拼接等其他算法中。

[1] Greig D, Porteous B, Seheult A. Exact maximum a posteriori estimation for binary images[J]. Journal of the Royal Statistical Society(Series B), 1989, 51(2):271-279.

[2] Boykov Y,Jolly M P.Interactive organ segmentation using graph cuts[C]∥Proc of the 3rd International Conference on Medical Image Computing and Computer-Assisted Intervention, 2000:276-286.

[3] Boykov Y,Jolly M P.Interactive graph cuts for optimal boundary and region segmentation of objects in N-D images[C]∥Proc of the 8th IEEE International Conference on Computer Vision, 2001:105-112.

[4] Boykov Y,Veksler O,Zabih R.Fast approximate energy minimization via graph cuts[J]. IEEE Transactions on Pattern Analysis and Machine Intelligence, 2001, 23(11):1222-1239.

[5] Li Y, Sun J, Tang C K, et al. Lazy snapping[J]. ACM Transactions on Graphics, 2004, 23(3):303-308.

[6] Blake A, Rother C, Brown M, et al. Interactive image segmentation using an adaptive GMMRF model[C]∥Proc of the 8th European Conference on Computer Vision, 2004:428-441.

[7] Rother C,Kologorov V, Blake A.“GrabCut”:Interactive foreground extraction using iterated graph cuts[C]∥Proc of the ACM SIGGRAPH Conference, 2004:309-314.

[8] Xu Qiu-ping, Guo Min, Wang Ya-rong. Fast image segmentation algorithm based on multiscale analysis and graph cuts[J]. Application Research of Computer, 2009,26(10):3989-3991.(in Chinese)

[9] Xu Qiu-ping, Guo Min, Wang Ya-rong. Fast color image segmentation based on watershed transform and graph cuts[J]. Computer Engineering, 2009,35(19):210-215.(in Chinese)

[10] Han S D, Tao W B, Wang D S, et al. Image segmentation based on grabcut framework integrating multiscale nonlinear structure tensor[J]. IEEE Transactions on Image Processing, 2009, 18(10):2289-2302.

[11] Han S D, Tao W B, Wu X L. Texture segmentation using independent-scale component-wise riemannian-covariance Gaussian mixture model in KL measure based multi-scale nonlinear structure tensor space[J]. Pattern Recognition, 2011,44(3):503-518.

[12] Han Shou-dong, Zhao Yong, Tao Wen-bing, et al. Gaussian super-pixel based fast image segmentation using Graph-Cuts[J]. Acta Automatica Sinica, 2011,37(1):11-20.(in Chinese)

[13] Ford L,Fulkerson D.Flows in networks[M] .New Jersey:Princeton University Press, 1962.

附中文參考文獻(xiàn)：

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

[9] 徐秋平,郭敏,王亞榮.基于分水嶺變換和圖割的彩色圖像快速分割[J].計(jì)算機(jī)工程, 2009,35(19),210-215.

[12] 韓守東, 趙勇, 陶文兵, 等. 基于高斯超像素的快速Graph Cuts圖像分割方法[J]. 自動(dòng)化學(xué)報(bào), 2011, 37(1):11-20.