摘 要： 采用Graph cut的圖像分割分為交互式分割與自動(dòng)分割，為了彌補(bǔ)交互式分割需要用戶(hù)的參與、分割結(jié)果依賴(lài)種子點(diǎn)的選取與模型的建立、需要用戶(hù)的進(jìn)一步修正才能得到滿(mǎn)意結(jié)果等不足，介紹基于相似性的自動(dòng)圖像分割。該方法采用Mean?shift平滑圖像、轉(zhuǎn)換成YCbCr空間后將圖像分割成若干區(qū)域塊等方法，建立合適的能量函數(shù)后利用最大流/最小割定理求最小割。并通過(guò)實(shí)驗(yàn)證明，該方法在自動(dòng)性、準(zhǔn)確性、時(shí)間效率方面都獲得較好結(jié)果。

關(guān)鍵字： 交互式分割； 自動(dòng)分割分割； Graph cut； 像素相似性

中圖分類(lèi)號(hào)： TN919?34 文獻(xiàn)標(biāo)識(shí)碼： A 文章編號(hào)： 1004?373X（2014）02?0045?03

0 引 言

數(shù)字圖像處理就是圖像分析、理解的過(guò)程，而圖像分割是這一過(guò)程的基礎(chǔ)。圖像分割的目的是對(duì)圖像中有意義的特征部分進(jìn)行提取，所謂有意義的特征包括圖像中的邊緣和區(qū)域等。目前有許多分割方法在應(yīng)用領(lǐng)域都有長(zhǎng)足的發(fā)展?；趫D論的Graph cut技術(shù)，根據(jù)圖像的特征信息建立合適的能量函數(shù)，然后構(gòu)建網(wǎng)絡(luò)圖，利用最大流/最小割算法通過(guò)對(duì)網(wǎng)絡(luò)圖進(jìn)行分割的得到結(jié)果，其能量全局最優(yōu)，分割結(jié)果精確，因此受到人們的廣泛關(guān)注。Graph cut算法可分為三類(lèi)[1]：一是為了提高分割速度加速Graph cut算法，例如文獻(xiàn)[2]的基于GPU上的快速Graph cut算法；二是通過(guò)用戶(hù)的交互優(yōu)化分割結(jié)果的交互式Graph cut算法，例如文獻(xiàn)[3?6]等；三是增加形狀先驗(yàn)條件使得分割更合理的形狀先驗(yàn)Graph cut算法，例如文獻(xiàn)[7?9]等。

1 交互式分割與自動(dòng)分割

2000年，Boykov等提出一種基于Graph cut的交互式分割方法，通過(guò)該方法用戶(hù)提供分割約束，指定前景與背景，對(duì)圖像數(shù)據(jù)的分布用直方圖進(jìn)行估計(jì)，使用Graph cut對(duì)能量函數(shù)實(shí)現(xiàn)最小化，實(shí)現(xiàn)圖像分割[3?4]。

2004年，Rother等人在Boykov的基礎(chǔ)上在采用用高斯混合模型，對(duì)彩色圖像進(jìn)行分割等方面做出了改進(jìn)，提出Grab Cut算法[5]。Rother的方法使得交互變得更簡(jiǎn)潔。Grab Cut是基于Graph cut交互式分割方法中最好的一種。

由于交互式分割需要用戶(hù)的參與，分割結(jié)果依賴(lài)種子點(diǎn)的選取與模型的建立，需要用戶(hù)的進(jìn)一步修正才能得到滿(mǎn)意結(jié)果。雖然用途廣泛，較之自動(dòng)分割有很多的優(yōu)點(diǎn)[6]，但某些場(chǎng)合下還需要圖像的自動(dòng)分割。自動(dòng)分割的方法有很多，比如通過(guò)相位展開(kāi)獲取種子點(diǎn)的PUMA[7]方法；Suga等人通過(guò)SIFT算子來(lái)獲取種子后利用Graph cut的方法[8]；文獻(xiàn)[9]給出了利用加權(quán)核密度估計(jì)的自動(dòng)分割方法；侯葉提出GCB?SBP算法[10]等。

2 基于像素相似性的圖像自動(dòng)分割

2.1 相似性的計(jì)算

計(jì)算相似性時(shí)，文獻(xiàn)[10]給出了三種處理措施如下圖1所示。

（1） Meanshift處理：采用均值漂移（Meanshift）對(duì)圖像進(jìn)行平滑處理，濾除了一定干擾，保留了邊緣性。

（2） 轉(zhuǎn)換到Y(jié)CbCr顏色空間：其中Y是指亮度分量，Cb指藍(lán)色色度分量，而Cr指紅色色度分量，其三個(gè)分量相互獨(dú)立，有利于相似性計(jì)算。RGB與YCbCr可有如下關(guān)系相互轉(zhuǎn)換：

[YCbCr=0.2990.5870.114-0.168 7-0.331 30.5000.500-0.418 7-0.081 3RGB+0128128] （1）

（3） 塊劃分：通過(guò)塊劃分，增加快速性，GPAC算法也采用了區(qū)域塊。在文獻(xiàn)[10]的算法中，將YCbCr圖像按一定的大小進(jìn)行塊劃分，即將圖像[Ic]劃分成[n×m]塊[（m=c-115+1，n=r-115+1），]每塊大小為15×15，劃分后記為[Ib]。

由此相似性計(jì)算公式為：

[S（i，j）=（Tiy-Tjy′）2+（Ticb-Tjcb′）2+（Ticr-Tjcr′）2]

式中[Tiy]表示像素[i]的亮度分量；[Ticb]與[Ticr]為像素[i]的色差分量；[Tjy′] 表示[j]的亮度分量；[Tjcb′]與[Tjcr′]表示[j]的色差分量。

2.2 能量函數(shù)的建立

預(yù)處理：將整個(gè)圖像區(qū)域分割內(nèi)外兩個(gè)同質(zhì)區(qū)域。設(shè)圖像的行數(shù)r，列數(shù)c，以[min（r6，c6）] 為半徑，取閉合輪廓曲線[C]，將[C]與[C]的內(nèi)部歸為一類(lèi)，表示內(nèi)部區(qū)域[Ci]，[C]的外部為一類(lèi)，表示[Co]。最小割的目標(biāo)就是[Ci]與[Co]之間的最小類(lèi)似性，[Ci]與[Co]各自?xún)?nèi)部像素之間相似性的定義是根據(jù)特性差別的程度，差別越小越相似。

能量函數(shù)表示為數(shù)據(jù)懲罰項(xiàng)與光滑項(xiàng)的和，即：

[E（L）=p∈PDp（Lp）+p，q∈NVp，q（Lp，Lq）]

式中：[Dp（Lp）]是數(shù)據(jù)懲罰項(xiàng)；[P]是圖像的像素集；[p]是[P]中的像素；[n]是[Ci]中像素；[f]是[Co]中像素；[S（p，n）]，[S（p，f）]分別表示[p]與[n]，[f]的相似性，令[DP（Ci）]，[DP（Co）]表示相似性之和：

[DP（Ci）=p∈P，n∈CiS（p，n）， DP（Co）=p∈P，n∈CoS（p，f）]

[Vp，q]為光滑項(xiàng)，[Vp，q（Lp，Lq）=V（Lp，Lq）?wpq]，[V（Lp，Lq）]反映像素空間位置的關(guān)系；[Lp，Lq]為相鄰像素[p，q]的標(biāo)號(hào)，[wpq]是空間變化參數(shù)，反映空間像素變化[V（Lp，Lq）=1，Lp≠Lq0，Lp=Lq]，則有：如果[Lp≠Lq]，[Vp，q（Lp，Lq）=wpq]；如果[Lp=Lq]，[Vp，q（Lp，Lq）=0]。

其中邊緣信息可以使用高斯濾波器對(duì)圖像首先做平滑處理，然后利用Sobel算子進(jìn)行邊緣檢測(cè)，獲得水平與垂直邊緣為[hv]和[vv]。以[p=（r，c）]為[r]行[c]列的像素點(diǎn)，[h（r，c）]、[v（r，c）]分別為[r]行[c]列像素點(diǎn)有關(guān)邊緣的水平和垂直信息，設(shè)置：[h（r，c）=exp（-5hv（r，c））]，[v（r，c）=][exp（-5vv（r，c））]。

2.3 網(wǎng)絡(luò)圖的構(gòu)建

由上，建立網(wǎng)絡(luò)圖：網(wǎng)絡(luò)圖權(quán)值如表1所示。表中[λ=內(nèi)部區(qū)域的面積圖像的寬×高]。

2.4 求最小割

根據(jù)最大流/最小割定理求取網(wǎng)絡(luò)圖的最小割，滿(mǎn)足最小花費(fèi)，并對(duì)產(chǎn)生的結(jié)果重新計(jì)算數(shù)據(jù)項(xiàng)，進(jìn)行迭代5次，得到最終結(jié)果。

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

實(shí)驗(yàn)平臺(tái)是Intel core T6500 2.1 Hz，2 GB在Matlab 7.0上實(shí)現(xiàn)。

對(duì)彩色圖像的分割（大小為216×144×3）如圖2所示。

對(duì)灰度圖像的分割（大小為200×200）如圖3所示。

從結(jié)果可以看出，通過(guò)基于像素性的Graph cut分割，得到較為滿(mǎn)意的結(jié)果，在花費(fèi)時(shí)間方面，通過(guò)進(jìn)一步實(shí)驗(yàn)，與GPAC比較，本文方法時(shí)間消耗很少。

實(shí)驗(yàn)表明，基于相似性采用圖切割對(duì)圖像的自動(dòng)分割有良好的分割結(jié)果和較快的速度，是一種實(shí)用的分割方法。

4 結(jié) 語(yǔ)

Graph Cut作為全局優(yōu)化技術(shù)受到了廣泛的關(guān)注，基于交互式的Graph Cut方法雖然應(yīng)用廣泛，但需要用戶(hù)參與，不用用戶(hù)、不同情況下種子點(diǎn)的選取有很大的差異，而對(duì)種子點(diǎn)的選取直接影響了圖像分割的質(zhì)量，本文介紹自動(dòng)分割技術(shù)，彌補(bǔ)了交互式的不足，而通過(guò)基于圖像相似性的圖像分割，得到較滿(mǎn)意的實(shí)驗(yàn)結(jié)果，值得深入研究與改進(jìn)。

參考文獻(xiàn)

[1] YI Fa?liu， MOON Inkyu. Image segmentation： a survey of Graph?cut methods [C]// 2012 International Conference on System and Informatics. Yantai， China： ICSAI， 2012， 1936?1941.

[2] VINEET V， NARAYANAN P J. CUDA cuts： fast graph cuts on the GPU [C]// IEEE Computer Society Conference on Computer Vision and Pattern Recognition Workshops. Anchorage， AK： IEEE， 2008： 1?8.

[3] BOYKOV Y， JOLLY M P. Interactive organ segmentation using graph cuts [C]// Third International Conference on Medical Image Computing and Computer?Assisted Intervention. [S.l.]： MICCAI， 2000：276?286.

[4] BOYKOV Y， JOLLY M P. Interactive Graph Cuts for optimal boundary and region segmentation of objects in n?d images [C]// IEEE International Conference on Computer Vision. [S.l.]： IEEE， 2001： 105?112.

[5] 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.

[6] 劉松濤，殷福亮.基于圖割的圖像分割方法及其新進(jìn)展[J].自動(dòng)化學(xué)報(bào)，2012，38（6）：911?922.

[7] BIOUCAS?DIAS J， VALADAO G. Phase unwrapping via graph cuts [J]. IEEE Transactions on Image Processing， 2007， 16（3）： 698?709.

[8] SUGA A， FUKUDA K， TAKIGUCHI T， et al. Object recogni?tion and segmentation using SIFT and graph cuts [C]// Proceedings of the 19th International Conference on Pattern Recognition. Tampa， USA： IEEE， 2008： 222?232.

[9] TANG Z， MIAO Z J， WAN Y L， et al. Automatic foreground extraction for images and videos [C]// Proceedings of the 17th IEEE International Conference on Image Processing. Hong Kong， China： IEEE， 2010： 111?121.

[10] 侯葉.基于圖論的圖像分割研究[D].西安：西安電子科技大學(xué)，2011.