基于像素相似性與Graph?Cut的圖像自動分割

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

關鍵字： 交互式分割； 自動分割分割； Graph cut； 像素相似性

中圖分類號： TN919?34 文獻標識碼： A 文章編號： 1004?373X（2014）02?0045?03

0 引 言

數字圖像處理就是圖像分析、理解的過程，而圖像分割是這一過程的基礎。圖像分割的目的是對圖像中有意義的特征部分進行提取，所謂有意義的特征包括圖像中的邊緣和區域等。目前有許多分割方法在應用領域都有長足的發展。基于圖論的Graph cut技術，根據圖像的特征信息建立合適的能量函數，然后構建網絡圖，利用最大流/最小割算法通過對網絡圖進行分割的得到結果，其能量全局最優，分割結果精確，因此受到人們的廣泛關注。Graph cut算法可分為三類[1]：一是為了提高分割速度加速Graph cut算法，例如文獻[2]的基于GPU上的快速Graph cut算法；二是通過用戶的交互優化分割結果的交互式Graph cut算法，例如文獻[3?6]等；三是增加形狀先驗條件使得分割更合理的形狀先驗Graph cut算法，例如文獻[7?9]等。

1 交互式分割與自動分割

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

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

由于交互式分割需要用戶的參與，分割結果依賴種子點的選取與模型的建立，需要用戶的進一步修正才能得到滿意結果。雖然用途廣泛，較之自動分割有很多的優點[6]，但某些場合下還需要圖像的自動分割。自動分割的方法有很多，比如通過相位展開獲取種子點的PUMA[7]方法；Suga等人通過SIFT算子來獲取種子后利用Graph cut的方法[8]；文獻[9]給出了利用加權核密度估計的自動分割方法；侯葉提出GCB?SBP算法[10]等。

2 基于像素相似性的圖像自動分割

2.1 相似性的計算

計算相似性時，文獻[10]給出了三種處理措施如下圖1所示。

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

（2） 轉換到YCbCr顏色空間：其中Y是指亮度分量，Cb指藍色色度分量，而Cr指紅色色度分量，其三個分量相互獨立，有利于相似性計算。RGB與YCbCr可有如下關系相互轉換：

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

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

由此相似性計算公式為：

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

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

2.2 能量函數的建立

預處理：將整個圖像區域分割內外兩個同質區域。設圖像的行數r，列數c，以[min（r6，c6）] 為半徑，取閉合輪廓曲線[C]，將[C]與[C]的內部歸為一類，表示內部區域[Ci]，[C]的外部為一類，表示[Co]。最小割的目標就是[Ci]與[Co]之間的最小類似性，[Ci]與[Co]各自內部像素之間相似性的定義是根據特性差別的程度，差別越小越相似。

能量函數表示為數據懲罰項與光滑項的和，即：

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

式中：[Dp（Lp）]是數據懲罰項；[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]為光滑項，[Vp，q（Lp，Lq）=V（Lp，Lq）?wpq]，[V（Lp，Lq）]反映像素空間位置的關系；[Lp，Lq]為相鄰像素[p，q]的標號，[wpq]是空間變化參數，反映空間像素變化[V（Lp，Lq）=1，Lp≠Lq0，Lp=Lq]，則有：如果[Lp≠Lq]，[Vp，q（Lp，Lq）=wpq]；如果[Lp=Lq]，[Vp，q（Lp，Lq）=0]。

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

2.3 網絡圖的構建

由上，建立網絡圖：網絡圖權值如表1所示。表中[λ=內部區域的面積圖像的寬×高]。

2.4 求最小割

根據最大流/最小割定理求取網絡圖的最小割，滿足最小花費，并對產生的結果重新計算數據項，進行迭代5次，得到最終結果。

3 實驗結果與分析

實驗平臺是Intel core T6500 2.1 Hz，2 GB在Matlab 7.0上實現。

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

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

從結果可以看出，通過基于像素性的Graph cut分割，得到較為滿意的結果，在花費時間方面，通過進一步實驗，與GPAC比較，本文方法時間消耗很少。

實驗表明，基于相似性采用圖切割對圖像的自動分割有良好的分割結果和較快的速度，是一種實用的分割方法。

4 結 語

Graph Cut作為全局優化技術受到了廣泛的關注，基于交互式的Graph Cut方法雖然應用廣泛，但需要用戶參與，不用用戶、不同情況下種子點的選取有很大的差異，而對種子點的選取直接影響了圖像分割的質量，本文介紹自動分割技術，彌補了交互式的不足，而通過基于圖像相似性的圖像分割，得到較滿意的實驗結果，值得深入研究與改進。

參考文獻

[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].自動化學報，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].西安：西安電子科技大學，2011.