基于跨時空域相似鄰接圖的視頻分割算法

張洪超， 張 磊， 黃 華

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

隨著視頻數據規模的日漸擴大以及視頻內容的不斷豐富，如何準確高效的提取視頻中的對象目標是視頻分析和處理的重要任務。視頻分割是將前景物體從背景中摳取出來，形成單獨的對象序列，從而達到對象提取的目標。分割的前景物體可以進一步用于視頻壓縮、目標識別、視頻檢索、編輯合成等應用，為語義級別的視頻處理提供了素材。因此，視頻分割一直是視頻處理研究的熱點問題，在模式識別、計算機圖形學以及計算機視覺等領域受到了廣泛的關注[1-5]。

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

視頻自動分割算法不需要人工交互，大致可分為基于光流法的分割[6-7]、運動跟蹤法[8]和基于變化區域檢測的時空法[9-10]3種。由于視頻分割問題的復雜性，自動分割算法有時很難分割出理想的前景目標。適當地引入人工交互，可以在很大程度上提高視頻分割的效果。

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

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

1 算法介紹

RepSnapping算法通過求解一基于相似特征構建的二維圖得到最優化目標函數的解，實現對重復物體快速、有效地分割。本算法將上述二維圖推廣到視頻領域，通過求解相似性鄰接圖分割問題，得到最優化目標函數的解，實現對視頻片段的分割。下面首先對RepSnapping算法進行簡要介紹，然后詳細介紹視頻分割問題模型的建立和相應相似性鄰接圖分割問題的構建與求解。

1.1 RepSnapping圖像分割算法簡介

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

RepSnapping圖像分割算法在傳統的基于馬爾可夫隨機場的圖像分割方法[12]的基礎上進行了改進，在其最優化目標函數的基礎上增加了一項基于特定特征相似性的平滑項懲罰，使其適用于同時分割多個重復物體。RepSnapping算法的最優化目標函數如下

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

1.2 跨時空域相似性鄰接圖的建立

本文算法將RepSnapping算法的框架推廣到視頻領域，實現對視頻片段的快速、高效的分割，并且對前景目標發生遮擋、快速運動等現象的視頻分割具有很好的穩定性。

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

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

圖1 相似性鄰接圖割算法圖構建示意圖

下面詳細介紹求解式（2）所用的相似性鄰接圖的具體構建過程。首先，用戶通過在第i幀進行交互，確定種子前景區域F和種子背景區域B，用作分割時的先驗信息。根據用戶提供的先驗信息，確定式（2）中的數據懲罰項Dp，在相似性鄰接圖中對應于交互幀fir中的像素對應的結點與s、t結點（如圖1中紅色結點所示）之間的連接權值Dp

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

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

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

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

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

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

圖2 基于均值偏移預分割圖的構建示意圖

2 實驗結果及分析

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

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

實驗中所用的機器配置如下：AMD速龍雙核CPU，2GHz，2GB內存，32位操作系統。實驗中以 10幀為單位進行同時分割，各階段所用時間和交互筆畫數比較見表1。

表1 視頻分割所用時間及交互筆畫數比較

本文算法在能量函數中引入了基于相似性的平滑項懲罰，使得在應用本文算法進行視頻分割時，只需要用戶在第1幀圖像上進行交互，算法可以自動將用戶交互信息傳遞到其它各幀，大大減少了用戶的交互量（如圖 3所示）；并且用戶交互信息的傳遞不會因為前景目標出現快速運動（如圖3中視頻1、2所示）、遮擋（如圖3中視頻3所示）等情況而中斷，提高了算法的穩定性。

圖3 本文實驗結果與SnapCut方法[4]的對比（在分割結果中，紅色筆畫表示前景，藍色筆畫表示背景）

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

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

3 結 論

本文將RepSnapping圖像分割算法推廣到視頻領域，通過基于整個時空域相似性構建擴展的鄰接圖，將視頻序列中出現的前景物體關聯，從而借助高效的最大流/最小割算法實現視頻的快速分割。相比于以前的視頻分割，該方法大大減少了用戶交互，而且對于前景目標被遮擋、運動快速等情況可以得到更準確的視頻分割結果，具有很好的穩定性。

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

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