局部顏色模型的交互式Graph－Cut分割算法

鄭加明，陳昭炯

(福州大學數學與計算機科學學院，福建福州 350108)

局部顏色模型的交互式Graph－Cut分割算法

鄭加明，陳昭炯

(福州大學數學與計算機科學學院，福建福州 350108)

由于目前大多數交互式Graph－Cut分割算法很難達到精確分割且實時交互的效果.對此，提出一種基于局部顏色模型的改進算法.該算法利用Mean－Shift預分割，建立基于局部顏色模型的交互式分割框架，并將像素級的Graph－Cut算法轉化為基于區域的算法進行快速求解.預分割之后的區域保持了原有圖像的結構，不僅提高了采用局部顏色模型估計分布的準確性，而且基于區域Graph－Cut的算法明顯降低了計算的復雜度.實驗結果表明，改進后的算法不僅保證了分割的精確性，而且還達到了實時交互.

Graph－Cut;交互式圖像分割;Mean－Shift;實時交互性

交互式圖像分割方法主要用于提取靜態圖像或視頻序列中的前景目標，其目的是希望通過盡量少的用戶交互，快速精確地提取出感興趣的對象，該方法在一定程度上解決了全自動分割存在的通用性差和分割效果不精確等問題.

近年來，有關交互式圖像分割的算法已越來越多，如蛇形算法［1］、交互式 Graph－Cut分割算法［2］、Grabcut［3］和 Lazy snapping［4］等.其中，交互式 Graph－Cut分割算法將交互式圖像分割轉化為求解一個包含區域和邊界信息能量函數的最小化過程，很好地將圖像的區域信息與邊界信息結合起來，分割的效果較為準確.

然而，大多數交互式 Graph－Cut分割算法還很難達到交互式分割所要求的快速精確分割的效果.這主要由兩方面原因造成的.一方面，由于圖像的像素個數一般是海量的，因而基于像素級的Graph－Cut算法的計算量和儲存量過大.為了解決此問題，可以通過對圖像進行預分割來降低算法的計算復雜度.如文獻［4］提出的Lazy snapping算法，將圖像進行分水嶺過分割，建立基于區域的Graph－Cut算法，在一定程度上實現了實時交互.但是采用分水嶺過分割，對原有圖像的結構會造成破壞，需要更多的交互以彌補過分割帶來的錯誤，另一方面，采用全局顏色模型不能反映圖像的空間結構，對復雜圖像分布的估計不準確.如文獻［3－6］提出的改進 Graph－Cut算法，都采用高斯混合模型(Gaussian mixture model，GMM)對前景和背景的顏色分布進行估計.采用高斯混合模型雖然比文獻［2］采用直方圖進行分布估計要準確，卻耗費了大量的時間，影響分割的速度.而且這種采用全局顏色模型的算法，很難反映圖像的空間信息，不能準確估計復雜圖像的分布.

為了在保證分割效果精確的同時，提高交互式分割的效率，提出一種基于局部顏色模型的交互式Graph－Cut分割算法.新算法采用 Mean－Shift對圖像進行預分割，利用預分割之后的區域集來估計前景和背景分布的候選局部顏色模型，并建立基于區域的 Graph－Cut模型.由于 Mean－Shift能夠很好地分析具有多峰分布的特征空間［7］，因此所建立的候選局部顏色模型能夠較好地估計出圖像的分布.又由于Mean－Shift分割考慮了圖像的顏色特征和空間信息，分割后的區域能夠很好地保持原有圖像的結構，因此采用基于區域的Graph－Cut模型，可以大大減少每次交互的計算量.而且在每次迭代時，前景和背景分布的模型可根據用戶標記直接選取候選模型來重新建立分布，進一步減少了交互的延遲時間.另外，還根據前景和背景局部顏色模型的重疊程度，計算估計分布可能造成的錯誤率，自適應地調整模型的參數.從實際檢驗的結果看，改進后的算法不僅保證了分割的精確性，還明顯減少了交互延遲時間.

1 交互式Graph－Cut分割框架

1.1 交互式圖像分割的能量函數

交互式圖像分割問題實際上是一個二值標記組合優化問題.通常，將一幅圖像看作一個無向圖G=＜V，E＞，其中頂點集V對應所有的像素，邊集E對應各個像素與相鄰像素的鄰接關系.二值標記組合優化問題的目標就是根據圖G，按照一定原則，找到一個最優解X，解中每個頂點都標記上惟一的標簽(背景為“back”，前景為“fore”).最優解X可以采用E(X)能量函數求得:

式中:R(X)是用來反應區域信息的區域項能量，B(X)是用來反應邊界信息的邊界項能量，區域項與邊界項的比重由參數λ確定.

1.2 Graph－Cut算法求最小化能量函數的過程

Graph－Cut算法需要用戶采用基于筆畫的交互形式對前景和背景進行標記，被標記上的像素稱為前景或背景種子，并根據前景和背景種子估計前景和背景的顏色分布.

區域項R(X)用來懲罰解X與觀察數據不一致的程度.一般可以將區域項定義為如下形式:通常，R(xi)用來反映像素xi顏色特征適合前景或者背景顏色分布的程度.

邊界項B(X)用來刻畫解X的邊界信息，其定義形式如下:

為了求解能量函數E(X)的最優解，Graph－Cut算法在無向圖G=＜V，E＞的基礎上構建源點s和匯點t的s－t網絡流圖.源點、匯點與圖G中的每個頂點由一條邊相連，邊的權重由R(xi)計算得到.圖G中頂點鄰接邊的權重由B(xi，xj)計算得到.Graph－Cut算法利用最大流/最小割原理［2］，通過求s－t網絡流圖中的最大流，解得能量的最小值，即最小割.

2 改進的交互式Graph－Cut分割算法

2.1 基于局部顏色模型的能量函數構造

局部顏色模型融合了原有圖像的空間結構與顏色信息，可以更好地估計復雜圖像的分布.因此，采用局部顏色模型對前景和背景的分布進行估計，構造基于局部顏色模型的能量函數.

利用Mean－Shift預分割來估計前景和背景分布的候選局部顏色模型.先對圖像中所有n個像素{zi}i=1，2，…，n經過 Mean－Shift過濾，再合并相似區域和小區域，得到m個聚簇.這m個聚簇的集合就是圖像分布的m個模式，也就是候選局部顏色模型{Cp}p=1，2，…，m.對于每一個像素zi所屬的局部顏色模型為Li={p|zi∈Cp}，對應的模式特征值為yi={M(p)|zi∈Cp}.接著，根據用戶標記從候選局部顏色模型{Cp}p=1，2，…，m中選取前景和背景顏色模型.設用戶標記的g個前景種子集合為{Fg}，h個背景種子集合為{Bh}.如果zi∈ {Fg}，則候選局部顏色模型中的Li模型晉升為前景顏色模型.若晉升num(F)個局部顏色模型為前景顏色模型，將其定義為θF.同樣，可以得到num(B)個局部顏色模型為背景顏色模型，定義為θB.則像素zi屬于前景和背景分布的概率為P(zi|θF)和P(zi|θB).當用戶添加新的標記時，前景和背景分布的模型根據用戶標記直接從候選模型中選取，不需要重新進行Mean－Shift分割，提高了算法的效率.

為了達到實時交互，將預分割后的區域作為圖的頂點，并在此基礎上構造基于局部顏色模型的能量函數.設基于區域的圖結構為G'=＜V'，E'＞，其中頂點p的值為該區域的模式特征值M(p)，若區域中任一個像素與另一區域中某像素滿足8－鄰域關系，則這2個區域對應的頂點是相鄰關系.本文所定義的種子是指包含前景或背景種子的區域塊.對于誤分割產生的錯誤結果，可以對局部區域進行基于像素的Graph－Cut分割.對此，將主要研究基于區域的交互式Graph－Cut分割算法，構造基于局部顏色模型的能量函數如下:

式中:μ為自適應因子，由前景與背景顏色模型估計分布產生的錯誤率ρ確定，可定義為

式中:δ為常量因子，ρ可根據貝葉斯分類的錯誤率定義為

2.2 利用最大流原理求解能量函數的最小值

將能量函數(1)中的區域項和邊界項能量映射到s－t網絡流圖，并將圖G'中的頂點分為前景種子、背景種子和未確定區域3種類型.其中，未確定區域是指除了用戶標記過的前景和背景種子外的其他區域.頂點與源點s、匯點t連接的權重分別為R(xfore)和R(xback).不同類型頂點，所對應的R(xfore)和R(xback)的值如表1所示.為了保證種子確定屬于前景或者背景，L(i)必須大于頂點i鄰接邊權重的總和.根據頂點i的鄰接邊條數neigh(i)不同，L(i)的計算方法如下:

當頂點i屬于未確定區域，根據前景和背景分布計算頂點i區域項的值Sfore(i)和Sback(i).另外將邊界項能量定義為相鄰頂點xi和xj的權值:

式中:σ為所有鄰接邊權重的平均值.

表1 區域項的值Table 1 Region term values

2.3 改進算法的基本步驟

采用候選局部顏色模型，并建立基于區域的交互式Graph－Cut分割框架，算法的基本步驟如下.

1)對輸入圖像進行Mean－Shift預分割，建立m個候選局部顏色模型{Cp}p=1，2，…，m.預分割的參數設置參考文獻［7］所提供的數據.如果存在過多誤分割的效果(同一區域同時包含前景和背景)，可以通過調整參數減少誤分割帶來的錯誤.

2)用戶采用基于筆畫的交互方式對輸入圖像進行前景和背景標記，產生前景和背景種子集合{Fg}和{Bh}.根據用戶標記從候選局部顏色模型{Cp}p=1，2，…，m選取前景和背景顏色模型 θF和 θB.

3)將預分割后的區域作為圖G＇的頂點，建立基于區域的交互式Graph－Cut分割框架.計算頂點i與前景和背景種子在顏色特征空間上的最短距離和

4)根據表1，計算3種類型頂點區域項的值.其中，Sfore(i)和Sback(i)區域值的計算方法為:

其中，頂點屬于前景和背景的概率P(i|θF)和P(i|θB)按照以下方法計算:

自適應因子μ根據式(2)、(3)計算得到，常量因子δ取為0.8.同樣，根據式(4)計算邊界項的能量.

5)通過最大流原理，求解能量函數(1)的最小值，求得分割結果.

6)用戶根據分割的結果，決定是否添加新的標記或者刪除之前的標記.如果分割結果達到用戶的要求，則算法結束，輸出分割結果.如果用戶仍然對分割結果不滿意，則添加新的標記，或者刪除之前的標記，并轉到2).

通過基本流程可以看出，本文算法建立在基于區域的交互式Graph－Cut分割框架上，計算量比基于像素的Graph－Cut算法大大減少.且在整個交互過程只需要建立一次圖像的分布模型，即候選局部顏色模型.這些都有利于分割算法滿足實時交互.

3 實驗結果分析

為了驗證改進算法的有效性，在2.20 GHz CPU，1 GB內存的PC機上，通過Microsoft VC++6.0實現本文算法.利用 Berkeley圖像分割圖庫(http://www.eecs.berkeley.edu/Research/Projects/CS/vision/grouping/segbench/)和文獻［8］提供的測試圖庫進行測試，從交互延遲時間、分割錯誤率及自適應情況分析算法的性能.

3.1 交互延遲時間對比

假設一幅圖像的像素點個數為N，像素相鄰關系對應的總邊數為E，則采用像素級的Graph－Cut求解所耗費的時間復雜度為O(NE2)［9－10］.圖像預處理后的區域個數為m，邊數為e，Mean－Shift算法預處理時間為O(N2).交互延遲時間表示用戶標記之后Graph－Cut求解所耗費的時間，如果每次交互操作都需要預處理，則交互延遲時間的復雜度為O(N2+me2).一般情況下，邊數與頂點數的比例為常數，則原算法的時間復雜度為O(E3)，新算法為O(N2+e3)，即O(e3).由于預處理后所計算的頂點數和邊數明顯減少，與原算法的時間復雜度相比，新算法的執行效率更高.當圖像分辨率提高時，圖像的像素個數增加，但區域數不變，新算法的效率提高得更顯著.另外，本文算法一般只需要采用一次Mean－Shift分割就可完成預處理，進一步減少了交互過程的計算量.

將本文算法的交互延遲時間與文獻［2］及Grabcut算法進行對比，3個算法所對應的延遲時間如表2所示.

表2 交互延遲時間對比Table 2 Comparison of interactive lag time s

文獻［2］算法和本文算法的用戶交互形式是一樣的，都是采用基于筆畫的形式進行的.而Grabcut算法則先采用矩形框將分割對象框住，先自動迭代地完成初步分割.這里Grabcut算法的交互延遲時間表示為初步分割的時間.通過以上對比實驗，發現改進后的算法只需要很短的交互延遲時間，達到了實時交互的效果.

3.2 錯誤率及自適應情況

為了驗證改進后的算法也能達到分割效果精確，在用戶標記一樣的情況下，將本文算法與文獻［2］算法的分割錯誤率進行比較分析.對分割圖庫的圖像進行分割，分割錯誤率的對比結果如圖1所示，其具體的錯誤率見表3.最終統計出文獻［2］算法的平均錯誤率為1.95%，而本文算法的平均錯誤率為1.01%.

圖1 分割的錯誤率對比Fig.1 Comparison of error rates

圖2 “shrinking bias”現象對比(F和B對應前景和背景標記)Fig.2 Comparison of the“shrinking bias”phenomenon

Graph－Cut算法會產生“shrinking bias”錯誤［5］，不能準確分割含細長對象的圖像，影響分割的精確性.對此，比較了文獻［2］算法與本文算法對含有細長對象圖像的分割錯誤率.圖2列舉了其中的2組對比實驗結果，可以看出本文算法可以在一定程度上緩解“shrinking bias”現象.

改進算法增加了自適應因子，可以適用于大部分圖像的分割(其中本文λ值設置為0.8).圖3列舉了各種不同形狀和類型圖像分割的結果.實驗表明，本文算法可以自適應于各種不同類型的圖像.

圖3 不同類型圖像的分割結果Fig 3 The segmentation results of different types of images

表3 分割錯誤率對比Table 3 Comparison of error rates %

4 結束語

本文采用局部顏色模型對前景和背景顏色分布進行估計，并建立了基于區域的交互式Graph－Cut分割的框架.實驗表明這一改進是有效的，不僅可以更好地估計顏色分布，保持了分割效果的精確性，而且每次迭代不需要重新建立分布，減少了交互延遲時間，達到了實時交互的效果.但是當前景與背景存在過多相似顏色時，與其他算法一樣，本文算法也會產生比較大的分割錯誤率，今后將針對這一問題做進一步的改進.

［1］KASS M，WITKIN A，TERZOLPOULOS D.Snakes:active contour models［J］.International Journal of Computer Vision，1988，1(4):321－331.

［2］YUNRI Y，JOLLY B M P.Interactive graph cuts for optimal boundary and region segmentation of objects in N－D images［C］//Proceedings of International Conference on Computer Vision.Vancouver，Canada，2001，1:105－112.

［3］ROTHER C，KOLMOGOROV V，BLAKE A.Grabcut－in－teractive foreground extraction using iterated graph cuts［J］.ACM Transactions on Graphics，2004，23(3):309－314.

［4］LI Yin，SUN Jian，TANG Chikeung，et al.Lazy snapping［C］//Computer Graphics Proceedings，Annual Conference Series(ACM SIGGRAPH).Los Angeles，USA，2004:303－308.

［5］VICENTE A，KOLMOGOROV V，ROTHER C.Graph cut based image segmentation with connectivity priors［C］//Proceeding of IEEE International Conference on CVPR.［S.l.］，2008:1－8.

［6］劉陳，李鳳霞，張艷.圖割與泛形信息結合［J］.計算機輔助設計與圖形學學報，2009，21(12):1753－1760.

LIU Chen，LI Fengxia，ZHANG Yan.An interactive object cutout algorithm based on graph－cut and generalized shape prior［J］.Journal of Computer－aided Design ＆ Computer Graphics，2009，21(12):1753－1760.

［7］COMANICIU D，MEER P.Mean shift:a robust approach toward feature space analysis［J］.IEEE Transactions on Pattern Analysis and Machine Intelligence，2002，24(5):603－619.

［8］RHEMANN C，ROTHER C，WANG J.A perceptually motivated online benchmark for image matting［C］//Proceedings of IEEE International Conference on CVPR.2009:1826－1833.

［9］YUNRI Y，BOYKOV，KOLMOGOROV V.An experimental comparison of min－cut/max－flow algorithms for energy minimization in vision［J］.IEEE Transactions on Pattern Analysis and Machine Intelligence，2004，26(9):1124－1137.

［10］KOLMOGOROV V，ZABIH R.What energy functions can be minimized via graph cuts［J］.IEEE Transactions on Pattern Analysis and Machine Intelligence，2004，26(2):147－159.

鄭加明，男，1986年生，碩士研究生，主要研究方向為圖形圖像處理.

陳昭炯，女，1964年生，教授，主要研究方向為圖形圖像處理與智能算法設計等，主持及參與多項國家和省級基金項目，發表學術論文50余篇.

Interactive Graph-Cut for image segmentation using local color models

ZHENG Jiaming，CHEN Zhaojiong
(College of Mathematics and Computer Science，Fuzhou University，Fuzhou 350108，China)

Most interactive segmentation algorithms based on Graph－Cut do not usually lend themselves to real time applications with accurate segmentation.In this paper，an improved algorithm using local color models was proposed to deal with the problem.Using Mean－Shift technology，the proposed algorithm built an interactive image segmentation framework based on local color models.A Graph－Cut algorithm was then applied to the pre－segmented regions instead of image pixels.The pre－segmented regions preserve the image structure，which improves the estimation accuracy of distribution based on local color models and dramatically reduces the computational complexity.Experimental results show that the proposed algorithm has good real time interactivity with accurate segmentation.

Graph－Cut;interactive image segmentation;Mean－Shift;real time interactivity

TP391

A

1673－4785(2011)04－0318－06

10.3969/j.issn.1673－4785.2011.04.006

2010－06－05.

國家自然科學基金資助項目(60805042);福建省自然科學基金資助項目(2010J01329).

陳昭炯.E－mail:chenzj@fzu.edu.cn.