鄭加明，陳昭炯

(福州大學(xué)數(shù)學(xué)與計(jì)算機(jī)科學(xué)學(xué)院，福建福州 350108)

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

鄭加明，陳昭炯

(福州大學(xué)數(shù)學(xué)與計(jì)算機(jī)科學(xué)學(xué)院，福建福州 350108)

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

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

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

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

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

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

1 交互式Graph－Cut分割框架

1.1 交互式圖像分割的能量函數(shù)

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

式中:R(X)是用來反應(yīng)區(qū)域信息的區(qū)域項(xiàng)能量，B(X)是用來反應(yīng)邊界信息的邊界項(xiàng)能量，區(qū)域項(xiàng)與邊界項(xiàng)的比重由參數(shù)λ確定.

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

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

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

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

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

2 改進(jìn)的交互式Graph－Cut分割算法

2.1 基于局部顏色模型的能量函數(shù)構(gòu)造

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

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

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

式中:μ為自適應(yīng)因子，由前景與背景顏色模型估計(jì)分布產(chǎn)生的錯誤率ρ確定，可定義為

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

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

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

當(dāng)頂點(diǎn)i屬于未確定區(qū)域，根據(jù)前景和背景分布計(jì)算頂點(diǎn)i區(qū)域項(xiàng)的值Sfore(i)和Sback(i).另外將邊界項(xiàng)能量定義為相鄰頂點(diǎn)xi和xj的權(quán)值:

式中:σ為所有鄰接邊權(quán)重的平均值.

表1 區(qū)域項(xiàng)的值Table 1 Region term values

2.3 改進(jìn)算法的基本步驟

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

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

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

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

4)根據(jù)表1，計(jì)算3種類型頂點(diǎn)區(qū)域項(xiàng)的值.其中，Sfore(i)和Sback(i)區(qū)域值的計(jì)算方法為:

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

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

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

6)用戶根據(jù)分割的結(jié)果，決定是否添加新的標(biāo)記或者刪除之前的標(biāo)記.如果分割結(jié)果達(dá)到用戶的要求，則算法結(jié)束，輸出分割結(jié)果.如果用戶仍然對分割結(jié)果不滿意，則添加新的標(biāo)記，或者刪除之前的標(biāo)記，并轉(zhuǎn)到2).

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

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

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

3.1 交互延遲時(shí)間對比

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

將本文算法的交互延遲時(shí)間與文獻(xiàn)［2］及Grabcut算法進(jìn)行對比，3個算法所對應(yīng)的延遲時(shí)間如表2所示.

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

文獻(xiàn)［2］算法和本文算法的用戶交互形式是一樣的，都是采用基于筆畫的形式進(jìn)行的.而Grabcut算法則先采用矩形框?qū)⒎指顚ο罂蜃?，先自動迭代地完成初步分?這里Grabcut算法的交互延遲時(shí)間表示為初步分割的時(shí)間.通過以上對比實(shí)驗(yàn)，發(fā)現(xiàn)改進(jìn)后的算法只需要很短的交互延遲時(shí)間，達(dá)到了實(shí)時(shí)交互的效果.

3.2 錯誤率及自適應(yīng)情況

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

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

圖2 “shrinking bias”現(xiàn)象對比(F和B對應(yīng)前景和背景標(biāo)記)Fig.2 Comparison of the“shrinking bias”phenomenon

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

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

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

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

4 結(jié)束語

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

［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］劉陳，李鳳霞，張艷.圖割與泛形信息結(jié)合［J］.計(jì)算機(jī)輔助設(shè)計(jì)與圖形學(xué)學(xué)報(bào)，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年生，碩士研究生，主要研究方向?yàn)閳D形圖像處理.

陳昭炯，女，1964年生，教授，主要研究方向?yàn)閳D形圖像處理與智能算法設(shè)計(jì)等，主持及參與多項(xiàng)國家和省級基金項(xiàng)目，發(fā)表學(xué)術(shù)論文50余篇.

Interactive Graph-Cut for image segmentation using local color models

ZHENG Jiaming，CHEN Zhaojiong
(College of Mathematics and Computer Science，F(xiàn)uzhou University，F(xiàn)uzhou 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.

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

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