張洪超， 張 磊， 黃 華

（1. 西安交通大學(xué)電子與信息工程學(xué)院，陜西 西安 710049 2. 北京理工大學(xué)計(jì)算機(jī)學(xué)院，北京 100081）

隨著視頻數(shù)據(jù)規(guī)模的日漸擴(kuò)大以及視頻內(nèi)容的不斷豐富，如何準(zhǔn)確高效的提取視頻中的對象目標(biāo)是視頻分析和處理的重要任務(wù)。視頻分割是將前景物體從背景中摳取出來，形成單獨(dú)的對象序列，從而達(dá)到對象提取的目標(biāo)。分割的前景物體可以進(jìn)一步用于視頻壓縮、目標(biāo)識(shí)別、視頻檢索、編輯合成等應(yīng)用，為語義級(jí)別的視頻處理提供了素材。因此，視頻分割一直是視頻處理研究的熱點(diǎn)問題，在模式識(shí)別、計(jì)算機(jī)圖形學(xué)以及計(jì)算機(jī)視覺等領(lǐng)域受到了廣泛的關(guān)注[1-5]。

最近幾年，出現(xiàn)了很多有效的視頻分割算法，這些方法大致可以分為自動(dòng)分割算法和人工交互分割算法。

視頻自動(dòng)分割算法不需要人工交互，大致可分為基于光流法的分割[6-7]、運(yùn)動(dòng)跟蹤法[8]和基于變化區(qū)域檢測的時(shí)空法[9-10]3種。由于視頻分割問題的復(fù)雜性，自動(dòng)分割算法有時(shí)很難分割出理想的前景目標(biāo)。適當(dāng)?shù)匾肴斯そ换?，可以在很大程度上提高視頻分割的效果。

Wang等[1]將基于最小割算法的圖像分割算法推廣到視頻領(lǐng)域，取得了比較好的視頻分割效果。該算法允許用戶在圖像平面空間和時(shí)間構(gòu)成的三維空間中進(jìn)行交互，提高了交互效率。Li等[2]將二維圖像分割中的圖割算法推廣到視頻分割領(lǐng)域，每一個(gè)結(jié)點(diǎn)不僅與同幀中的鄰居結(jié)點(diǎn)相連，而且與其前一幀和后一幀中空間距離較近的局部結(jié)點(diǎn)相連，從而將視頻分割問題轉(zhuǎn)化為三維的圖割問題。Bai等[4]引入局部分類器，提出SnapCut視頻分類算法，該算法基于運(yùn)動(dòng)跟蹤結(jié)果，可以將用戶在關(guān)鍵幀上的交互分割結(jié)果傳遞到下一幀，有效地減少了用戶的交互。從顏色建模方面入手，Bai等[5]將運(yùn)動(dòng)估計(jì)加入顏色模型的創(chuàng)建過程中，得到了運(yùn)動(dòng)自適應(yīng)的顏色模型，該模型可以根據(jù)運(yùn)動(dòng)的局部特征對所建模型參數(shù)進(jìn)行自適應(yīng)地調(diào)整，并根據(jù)建立的運(yùn)動(dòng)模型，實(shí)現(xiàn)對運(yùn)動(dòng)物體的分割。

無論是基于視頻局部鄰域關(guān)系建圖[1-2]，還是引入運(yùn)動(dòng)跟蹤來輔助視頻分割[4-5]，都要求視頻的前景目標(biāo)在相鄰幀之間的位移較小。對于一些幀率較小或者前景目標(biāo)發(fā)生快速運(yùn)動(dòng)、遮擋等情況的視頻進(jìn)行分割時(shí)，上述算法往往失效。Huang等[11]對圖割算法進(jìn)行了改進(jìn)，基于該改進(jìn)圖割算法提出了RepSnapping圖像分割方法，用戶只需要很少的交互，即可對圖像中大量的重復(fù)物體進(jìn)行快速有效的分割。本文將上述算法推廣到視頻分割領(lǐng)域，并且認(rèn)為視頻片段中每一幀圖像的待分割前景目標(biāo)具有一定的相似性，并且視頻背景沒有發(fā)生較大的變化。在上面兩條假設(shè)的前提下，對于待分割視頻片段，用戶只需要在一幀圖像上進(jìn)行交互，同時(shí)對少數(shù)幀進(jìn)行修正，即可實(shí)現(xiàn)對整段視頻的分割。實(shí)驗(yàn)結(jié)果表明，本文所提出的算法在保證分割效果的同時(shí)，有效地解決了上面提到的待分割目標(biāo)遮擋、快速運(yùn)動(dòng)等情況；并且，只需要用戶在關(guān)鍵幀圖像上進(jìn)行少量的交互，所需交互量遠(yuǎn)少于上述分割方法。

1 算法介紹

RepSnapping算法通過求解一基于相似特征構(gòu)建的二維圖得到最優(yōu)化目標(biāo)函數(shù)的解，實(shí)現(xiàn)對重復(fù)物體快速、有效地分割。本算法將上述二維圖推廣到視頻領(lǐng)域，通過求解相似性鄰接圖分割問題，得到最優(yōu)化目標(biāo)函數(shù)的解，實(shí)現(xiàn)對視頻片段的分割。下面首先對RepSnapping算法進(jìn)行簡要介紹，然后詳細(xì)介紹視頻分割問題模型的建立和相應(yīng)相似性鄰接圖分割問題的構(gòu)建與求解。

1.1 RepSnapping圖像分割算法簡介

對于輸入圖像I，圖像分割的目的是為每一個(gè)像素p∈I指定一個(gè)標(biāo)簽，得到前景像素集合｝和背景像素集合標(biāo)簽集合｛fp｝通常是通過最優(yōu)化一個(gè)能量函數(shù)得到。首先，將輸入圖像用一個(gè)圖G=(N , E)來表示，其中N表示圖中的結(jié)點(diǎn)集合，每一個(gè)結(jié)點(diǎn)ni∈N對應(yīng)于輸入圖像中的一個(gè)像素，E表示圖中結(jié)點(diǎn)之間的邊的集合，每一條邊對應(yīng)于一對具有特定關(guān)系的結(jié)點(diǎn)。

RepSnapping圖像分割算法在傳統(tǒng)的基于馬爾可夫隨機(jī)場的圖像分割方法[12]的基礎(chǔ)上進(jìn)行了改進(jìn)，在其最優(yōu)化目標(biāo)函數(shù)的基礎(chǔ)上增加了一項(xiàng)基于特定特征相似性的平滑項(xiàng)懲罰，使其適用于同時(shí)分割多個(gè)重復(fù)物體。RepSnapping算法的最優(yōu)化目標(biāo)函數(shù)如下

其中，Dn( fn)表示將結(jié)點(diǎn)n的標(biāo)簽設(shè)為fn時(shí)帶來的數(shù)據(jù)項(xiàng)懲罰，即按照先驗(yàn)知識(shí)，該結(jié)點(diǎn)為前景，系統(tǒng)將其判為背景帶來的懲罰，或者按照先驗(yàn)知識(shí)，該結(jié)點(diǎn)為背景，系統(tǒng)將其判為前景帶來的懲罰； np＜nq表示圖中相鄰結(jié)點(diǎn)之間的單向組合，這里的“相鄰”可以是四鄰域相鄰或者八鄰域相鄰；表示兩相鄰結(jié)點(diǎn)分別被判為前、背景時(shí)帶來的基于空間連續(xù)性的平滑項(xiàng)懲罰；H表示相似像素點(diǎn)對的集合，表示兩相似結(jié)點(diǎn)分別被判為前、背景時(shí)帶來的基于特定特征相似性的平滑項(xiàng)懲罰。各結(jié)點(diǎn)的標(biāo)簽｛fn｝通過最小化上述目標(biāo)函數(shù)得到。

1.2 跨時(shí)空域相似性鄰接圖的建立

本文算法將RepSnapping算法的框架推廣到視頻領(lǐng)域，實(shí)現(xiàn)對視頻片段的快速、高效的分割，并且對前景目標(biāo)發(fā)生遮擋、快速運(yùn)動(dòng)等現(xiàn)象的視頻分割具有很好的穩(wěn)定性。

假設(shè)待分割視頻片段中的連續(xù)k幀圖像為fr1, fr2,… , f rk，則輸入視頻片段可以用 1個(gè)相似性鄰接圖來表示，其第 1、2個(gè)維度對應(yīng)于視頻圖像所在的平面空間，第3個(gè)維度為時(shí)間軸，對應(yīng)于視頻片段中的幀數(shù)，如圖1所示。對視頻片段進(jìn)行前景分割的目的是為每一個(gè)像素p ∈ f rs = ｛ fr1, fr2, … , f rk｝指定一個(gè)標(biāo)簽 fp∈ ｛ 0,1｝，得到每一幀圖像的前景像素集合 F =｛p : fp=0｝和背景像素集合 B =｛p : fp= 1 ｝。假設(shè)對于視頻片段中的圖像幀frj，其像素點(diǎn)集合對應(yīng)的在相似性鄰接圖中的結(jié)點(diǎn)集合為Nj，則整個(gè)相似性鄰接圖中的結(jié)點(diǎn)集合 N = ｛ N1, N2,… ,Nk｝，整個(gè)相似性鄰接圖中的邊的集合E中的元素對應(yīng)于一對具有特定關(guān)系的結(jié)點(diǎn) np, nq，其中np和nq是結(jié)點(diǎn)集合N中的兩個(gè)結(jié)點(diǎn)。如果在第i幀fri上進(jìn)行交互，則標(biāo)簽集合通過最優(yōu)化下述能量函數(shù)得到

其中， Dn( fn)表示將交互幀fri中的像素對應(yīng)的結(jié)點(diǎn)n的標(biāo)簽設(shè)為 fn時(shí)帶來的數(shù)據(jù)項(xiàng)懲罰；np＜nq表示圖中相鄰結(jié)點(diǎn)之間的單向組合，這里的“相鄰”除了包括該幀圖像中與特定結(jié)點(diǎn)相鄰的8個(gè)結(jié)點(diǎn)外，還包括前一幀和后一幀圖像中與該結(jié)點(diǎn)相鄰的18個(gè)結(jié)點(diǎn)；H表示N中相似結(jié)點(diǎn)對的集合，如果兩像素特定的特征空間中的距離小于一個(gè)給定的閾值，其中ni和nj分別為像素i和 j對應(yīng)的結(jié)點(diǎn)；義同式（1），只是這里的“相鄰”和“相似”關(guān)系已經(jīng)被推廣到了三維相似性鄰接圖中。

圖1 相似性鄰接圖割算法圖構(gòu)建示意圖

下面詳細(xì)介紹求解式（2）所用的相似性鄰接圖的具體構(gòu)建過程。首先，用戶通過在第i幀進(jìn)行交互，確定種子前景區(qū)域F和種子背景區(qū)域B，用作分割時(shí)的先驗(yàn)信息。根據(jù)用戶提供的先驗(yàn)信息，確定式（2）中的數(shù)據(jù)懲罰項(xiàng)Dp，在相似性鄰接圖中對應(yīng)于交互幀fir中的像素對應(yīng)的結(jié)點(diǎn)與s、t結(jié)點(diǎn)（如圖1中紅色結(jié)點(diǎn)所示）之間的連接權(quán)值Dp

其中C( p)表示像素p在給定特征空間中的坐標(biāo)。

其中， np, nq∈N，λ為常量，用來平衡數(shù)據(jù)懲罰項(xiàng)和平滑懲罰項(xiàng)之間的權(quán)重，β為常量，用來控制在分割過程中對梯度變化的容忍程度。

根據(jù)像素點(diǎn)對在給定特征空間中的距離，確定結(jié)點(diǎn)集合N中的相似點(diǎn)對集合H：如果結(jié)點(diǎn)ni對應(yīng)的像素i和結(jié)點(diǎn)nj對應(yīng)的像素 j在給定特征空間中的距離小于一個(gè)給定的閾值ε，則應(yīng)的式(2)中的第3項(xiàng)，在相似性鄰接圖中對應(yīng)于結(jié)點(diǎn)np與其相似結(jié)點(diǎn)（如圖1中綠色結(jié)點(diǎn)所示）之間的連接權(quán)值，定義為

1.3 最大流/最小割的視頻圖分割

根據(jù)上述對數(shù)據(jù)項(xiàng)懲罰、基于空間連續(xù)性的平滑項(xiàng)懲罰和基于相似性的平滑項(xiàng)懲罰的定義，可以通過最大流/最小割優(yōu)化算法對所構(gòu)建的跨時(shí)空域相似性鄰接圖（如1所示）在多項(xiàng)式時(shí)間內(nèi)進(jìn)行快速求解，從而實(shí)現(xiàn)對視頻片段的分割[12-14]。

由于基于像素所構(gòu)建的圖通常包含大量的結(jié)點(diǎn)和邊，計(jì)算復(fù)雜度較高。為了降低計(jì)算量，本算法借鑒 Lazy Snapping[15]的方法，對輸入視頻片段各幀采用均值偏移算法[16]進(jìn)行過分割預(yù)處理，并以分割得到的區(qū)域?yàn)榛A(chǔ)進(jìn)行相似性鄰接圖的構(gòu)建。圖的結(jié)點(diǎn)對應(yīng)于每個(gè)分塊，圖的邊對應(yīng)于相鄰、相似分塊，其中分塊之間的相鄰關(guān)系除了同幀圖像中直接毗鄰的區(qū)域外，還包括相鄰幀中包含具有相同空間坐標(biāo)的像素的區(qū)域?qū)?，如圖2中藍(lán)色結(jié)點(diǎn)代表的區(qū)域，相似關(guān)系定義為在給定特征空間中的坐標(biāo)距離小于給定閾值的區(qū)域?qū)?，如圖2中綠色結(jié)點(diǎn)代表的區(qū)域所示。由于分割所得分塊數(shù)目相對于原像素?cái)?shù)目大為減少，所得相似性鄰接圖在復(fù)雜性上遠(yuǎn)遠(yuǎn)小于基于像素所構(gòu)建的圖；同時(shí)，過分割所得分塊很好地保留了物體的局部結(jié)構(gòu)，從而保證了在加入預(yù)分割過程之后，分割效果不會(huì)降低。經(jīng)過均值偏移進(jìn)行預(yù)分割之后，本算法在保證分割效果的基礎(chǔ)上，大大提升了運(yùn)算速度，對于用戶的交互，可以實(shí)時(shí)得到分割結(jié)果。

圖2 基于均值偏移預(yù)分割圖的構(gòu)建示意圖

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

為了驗(yàn)證本文算法的有效性，我們實(shí)驗(yàn)了很多視頻片段。在相似性特征選取方面，本文實(shí)驗(yàn)以 RGB顏色特征為例進(jìn)行，也可以選取 Gabor紋理特征或者SIFT特征進(jìn)行相似性檢測。并且將實(shí)驗(yàn)結(jié)果與 Bai等[4]于 2009年提出的 Video SnapCut方法進(jìn)行了比較。Video SnapCut方法（Roto Brush）已經(jīng)集成到了After Effects CS5中，是一個(gè)比較成熟的方法。

本實(shí)驗(yàn)需要調(diào)節(jié)的參數(shù)包括同時(shí)分割的視頻片段幀數(shù)k、式（3）中的λ和β、式（4）中的μ和求解相似性結(jié)點(diǎn)對集合H時(shí)的閾值ε。實(shí)驗(yàn)中，k取10，即每次同時(shí)分割10幀圖像；式（2）中各懲罰項(xiàng)之間的平衡參數(shù)λ=2、u=10；β直接影響最終分割結(jié)果的平滑程度，實(shí)驗(yàn)中取為0.1；ε決定著相似性結(jié)點(diǎn)對集合H中的元素，實(shí)驗(yàn)中取為4。預(yù)分割過程所用的均值偏移算法中的3個(gè)參數(shù)設(shè)定如下：位置空間帶寬設(shè)為5，顏色空間帶寬設(shè)為5，分割區(qū)域最小面積設(shè)為50個(gè)像素。

實(shí)驗(yàn)中所用的機(jī)器配置如下：AMD速龍雙核CPU，2GHz，2GB內(nèi)存，32位操作系統(tǒng)。實(shí)驗(yàn)中以 10幀為單位進(jìn)行同時(shí)分割，各階段所用時(shí)間和交互筆畫數(shù)比較見表1。

表1 視頻分割所用時(shí)間及交互筆畫數(shù)比較

本文算法在能量函數(shù)中引入了基于相似性的平滑項(xiàng)懲罰，使得在應(yīng)用本文算法進(jìn)行視頻分割時(shí)，只需要用戶在第1幀圖像上進(jìn)行交互，算法可以自動(dòng)將用戶交互信息傳遞到其它各幀，大大減少了用戶的交互量（如圖 3所示）；并且用戶交互信息的傳遞不會(huì)因?yàn)榍熬澳繕?biāo)出現(xiàn)快速運(yùn)動(dòng)（如圖3中視頻1、2所示）、遮擋（如圖3中視頻3所示）等情況而中斷，提高了算法的穩(wěn)定性。

圖3 本文實(shí)驗(yàn)結(jié)果與SnapCut方法[4]的對比（在分割結(jié)果中，紅色筆畫表示前景，藍(lán)色筆畫表示背景）

由于在實(shí)驗(yàn)過程中僅僅選用了顏色特征進(jìn)行相似性判斷，而沒有考慮紋理等特征，在對一些前、背景顏色特征比較相似的視頻片段進(jìn)行分割時(shí)會(huì)出現(xiàn)比較大的誤差，甚至失敗，如圖4所示。

圖4 視頻分割結(jié)果（這兩幅圖像分別為待分割視頻序列中的第1、4幀圖像）

3 結(jié) 論

本文將RepSnapping圖像分割算法推廣到視頻領(lǐng)域，通過基于整個(gè)時(shí)空域相似性構(gòu)建擴(kuò)展的鄰接圖，將視頻序列中出現(xiàn)的前景物體關(guān)聯(lián)，從而借助高效的最大流/最小割算法實(shí)現(xiàn)視頻的快速分割。相比于以前的視頻分割，該方法大大減少了用戶交互，而且對于前景目標(biāo)被遮擋、運(yùn)動(dòng)快速等情況可以得到更準(zhǔn)確的視頻分割結(jié)果，具有很好的穩(wěn)定性。

盡管本文的方法可以取得很好的分割結(jié)果，但是，當(dāng)視頻片段的前景目標(biāo)和背景在選定的特征空間中比較相似的情況下，應(yīng)用本文算法不能得到令人滿意的分割結(jié)果。作為以后的工作方向，我們擬引入更具甄別性的特征，如 SIFT特征，進(jìn)行相似性區(qū)域檢測，從而進(jìn)一步提高視頻分割的準(zhǔn)確度，在少量用戶交互的前提下提取滿足用戶需求的前景對象序列。

[1]Wang J, Thiesson B, Xu Y, et al. Image and video segmentation by anisotropic kernel mean shift [C]//European Conference on Computer Vision, 2004:238-249.

[2]Li Y, Sun J, Shum H. Video object cut and paste [J].ACM Transactions on Graphics (TOG), 2005, 24(3):595-600.

[3]Wang J, Bhat P, Colburn R, et al. Interactive video cutout [C]//ACM SIGGRAPH, 2005: 585-594.

[4]Bai X, Wang J, Simons D, et al. Video snap cut: robust video object cutout using localized classifiers [C]//ACM SIGGRAPH, 2009: 1-11.

[5]Bai X, Wang J, Sapiro G. Dynamic color flow: a motion-adaptive color model for object segmentation in video [C]// European Conference on Computer Vision, 2010: 617-630.

[6]Stiller C. A statistical image model for motion estimation [C]//International Conference on Acoustics,Speech, and Signal Processing, 1993: 193-196.

[7]Chang M, Sezan M, Tekalp A. An algorithm for simultaneous motion estimation and scene segmentation [C]//International Conference on Acoustics, Speech, and Signal Processing, 1994:V/221-V/224.

[8]Meyer F, Bouthemy P. Region-based tracking using affine motion models in long image sequences [J].CVGIP Image Understanding, 1994, 60(2): 199-140.

[9]Mech R, Wollborn M. A noise robust method for 2D shape estimation of moving objects in video sequences considering a moving camera [J]. Signal Processing,1998, 66(2): 203-217.

[10]Kim M, Choi JG, Lee M H. ISO/IEC JTC1/SC29/WG11 MPEG97/m2387, Performance analysis of an ETRI's global motion compensation and Scene cut detection algorithms for automatic segmentation [S].

[11]Huang H, Zhang L, Zhang H C. RepSnapping:efficient image cutout for repeated scene elements [J].Computer Graphics Forum, 2011, 30(7): 2059-2066.

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

[13]Boykov Y, Jolly M. Interactive graph cuts for optimal boundary & region segmentation of objects in ND images [C]//International Conference on Computer Vision, 2001: 105-112.

[14]Felzenszwalb P, Huttenlocher D. Efficient graphbased image segmentation [J]. International Journal of Computer Vision, 2004, 59(2): 167-181.

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

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