基于魯棒高階條件隨機場的視頻自動分割

程婷婷，郭立君，黃元捷

（寧波大學信息科學與工程學院，浙江 寧波315211）

·圖形圖像處理·

基于魯棒高階條件隨機場的視頻自動分割

程婷婷，郭立君，黃元捷

（寧波大學信息科學與工程學院，浙江 寧波315211）

針對交互式分割方法存在用戶標注繁瑣和過分割現象，以及僅考慮二元項不能獲得圖像中準確的物體邊界等問題，結合魯棒高階條件隨機場，提出一種視頻自動分割方法。采用基于超像素顯著性特征的分割方法對視頻初始幀進行自動分割，其結果作為初始化種子建立模型。根據顏色信息設計高斯混合模型，基于紋理、形狀等特征，利用聯合Boosting算法訓練Jointboost強分類器模型，通過條件隨機場提高分割準確度。引入基于超立體像素的高階項，增加像素與區域的關聯，提高分割邊界的平滑度。實驗結果表明，該方法明顯地提高了分割效果。

視頻自動分割；高階勢；超立體像素；條件隨機場；雙模型融合；特征融合

中文引用格式：程婷婷，郭立君，黃元捷.基于魯棒高階條件隨機場的視頻自動分割［J］.計算機工程，2015，41（7）：261?268.

英文引用格式：Cheng Tingting，Guo Lijun，Huang Yuanjie.Automatic Video Segmentation Based on Robust Higher Order Conditional Random Field［J］.Computer Engineering，2015，41（7）：261?268.

1 概述

視頻分割在計算機視覺領域具有廣泛應用，包括目標檢索、視頻壓縮、智能監控等。近年來，視頻分割迅速發展，主要分為交互式分割［1?4］和自動分割［5?7］。前者一般指根據用戶手動標記的若干前景和背景像素建立模型以實現分割的方法，后者主要指基于時空特征聚類的分割方法和自動獲取關鍵對象的分割方法。

本文提出一種基于高階條件隨機場（Conditional Random Field，CRF）的視頻前景對象自動分割方法。針對自動提取主要對象的分割方法時間復雜度高和無法在線分割的問題，采用基于超像素顯著性特征的分割方法對視頻初始幀進行自動分割。初始幀分割結果只包含前景和背景兩類，避免了過分割現象，令其作為種子點訓練概率模型，考慮到前景和背景顏色相近時，在顏色特征基礎上增加局部特征能有效提高分割精度，在使用混合高斯模型描述顏色分布的同時，增加基于局部二值模式（Local Binary Pattern，LBP）、局部特征texton和尺度不變特征變換（Scale Invariant Feature Transform，SIFT） 的Jointboost分類器，利用上述雙模型聯合驗證前景和背景種子點，并將雙模型融入條件隨機場框架中的一元能量函數。在條件隨機場中加入高階勢能，增加像素和超立體像素的時空約束關系，以提高分割邊界準確度。

2 背景介紹

在交互式分割領域，文獻［8］最早將圖割算法用于灰度圖像前景提取。該算法首先需用戶手動標注一部分像素作為前景和背景，然后在滿足手動標注限制的條件下尋找最優解以實現分割。文獻［9］利用混合高斯模型分別對彩色圖像前景和背景像素的顏色特征建模，該概率模型用于計算能量函數中的一元項，根據鄰域系統中每對像素空間和顏色的混合距離，計算能量函數中的二元項以平滑分割邊界。文獻［10］在提出Grabcut方法，該方法總體上仍基于圖割算法和混合高斯模型框架，區別在于用戶交互時增加一個矩形框，并通過迭代圖割方式達到能量函數最小。以上算法只考慮了像素的顏色特征而忽略了其他特征，如紋理、形狀等。文獻［11］在圖像中增加紋理通道，建立基于顏色和紋理特征的混合高斯模型，并在計算能量函數二元項時加入結構張量以有效利用紋理特征。但上述方法均需用戶交互，甚至在分割不準確的情況下需再次交互以得到準確分割，這不僅增加了交互負擔，而且前景和背景模型的建立對用戶標記的差異敏感，所以傳統的交互式圖像分割方法只適用于以編輯為目的的視頻應用，并不適用于以自動分割為基礎的其他視頻應用。

出于應用的考慮，視頻自動分割技術得到重視，出現了基于時空特征一致性的視頻自動分割方法［12?13］，其主旨為令光亮和運動一致的像素組合使其成為立體區域，但在前景和背景無明顯界限時，視頻幀中前景對象被分割成多個區域，出現過分割問題。最近出現的基于對象性檢測的自動視頻分割方法解決了過分割問題，文獻［6］使用譜聚類的方法從視頻相鄰幀的對象假設中檢測出主要對象作為先驗，但其缺乏相鄰幀的對象形狀預測，所以不能準確地分割快速移動的對象。而文獻［5］采用有向無環圖從視頻幀的所有對象假設中提取主要對象并通過光流預測對象的形狀，從而能夠處理快速移動對象，但該方法提取視頻所有幀中對象假設的過程非常耗時，使得整個算法的時間復雜度很高，另外，提取主要對象涉及整個視頻從而無法在線分割。

3 先驗信息初始化

建立前景和背景概率模型時需要種子點作為初始化信息。針對圖 1（a）所示的原始圖，使用SLIC［14］方法對初始幀進行無監督分割，獲得如圖1（b）所示的超像素。假定圖像中只有二類對象（前景和背景），并設定其模型為基于顯著性特征的有參函數Rf和Rb，根據每個超像素的得分給予前景或背景的標號，通過模型更新和超像素標號2個子過程迭代優化，取所有超像素標號劃分中得分最大的組合作為分割結果。最終得到如圖1（c）所示的前景和背景粗分割，將其作為初始化先驗信息。由于初始化信息中包含分割錯誤的前景和背景像素，因此需使用概率模型迭代優化以提高分割精度。

圖1 初始化示意圖

4 高階CRF結構

分割問題常被視為隨機場中像素標記問題，即為圖像中像素配置適當的標簽使得隨機場的后驗概率最大。本文將視頻分割理解為CRF中二值標記問題，假設｛f1，f2，…，ft，…，fn｝是視頻幀序列，條件隨機場X由頂點 V ＝｛x1，x2，…，xN｝、鄰域系統 ε和子團（clique）C組成。頂點為取值范圍L＝｛0，1｝的隨機變量，0代表背景，1代表前景，鄰域系統由所有像素在同一幀的8鄰域組成，子團由超立體像素S構成。

根據Hammersley Clifford隨機場定理可知，馬爾科夫隨機場的后驗概率分布即為Gbbis分布：

而條件隨機場［15］本質上是給定了觀察值集合的馬爾科夫隨機場，解決了其他判別式模型難以避免的標記偏置問題。

4.1 CRF中的一元項

視頻分割中顏色是一項重要的特征，本文運用混合高斯模型描述像素的RGB顏色分布。考慮到前景和背景顏色相近時，增加局部特征texton、LBP和SIFT能有效提高分割精度，故基于這些局部特征訓練一個Jointboost分類器。針對不同視頻圖像，將上述雙模型以不同的權重結合計算一元項。

4.1.1 基于局部特征的Jointboost分類器

本文采用一種改進型的聯合 Boosting算法［16］學習一個二類強分類器。選取的特征包括：（1）用于學習視頻圖像形狀上下文信息的 texton特征［17］；（2）用于處理對象尺度和旋轉變化的 SIFT特征；（3）用于描述紋理信息的LBP特征。圖2即為這些特征的映射圖。

圖2 特征映射圖

聯合Boosting算法在每次迭代r中找到一個最佳弱分類器hr（li），R個弱分類器疊加形成強分類器，其形式如下：

其中，每個弱分類器是一個決策樹樁。

其中，δ（·）是取值為{0，1}的指示函數；S（N）是N的子集；是像素 i的特征值；θ為閾值。利用softmax轉換方法，將式（3）變成概率形式：

因此關于texton，LBP和SIFT特征的勢能方程為：

4.1.2 混合高斯模型

文獻［5?6，9］均使用高斯混合模型（GMM）描述像素RGB顏色空間分布，可見GMM能有效地描述顏色特征并具有判別性。本文根據初始化種子像素的顏色特征，分別建立前景高斯混合模型和背景高斯混合模型。定義 PGMM（xi）為像素 xi屬于前景（xi＝1）或背景（xi＝0）的概率，一元項中采用該模型的負對數形式：

在不同視頻圖像中以上2個模型重要性有差異，因此設置參數α（0＜α＜1）控制其權重，在CRF中一元項的形式為：

在本文實驗中設置α＝0.3時，使得顏色特征權重大于形狀、紋理特征，其分割效果最佳。

在CRF結構中，根據先驗信息得到的概率模型作為一元項初始化，結合下文的二元項和高階項，使用迭代圖割方法更新模型，直至能量函數最小。

在圖3中，像素亮度越大表示屬于前景概率越大，可以看出模型結合后前景分割更準確。

圖3 概率映射圖

4.2 CRF中的二元項

在CRF能量函數中二元項的作用是去除鋸齒、平滑邊界。在基于圖割的分割方法中，二元項作用于相鄰像素促進邊界平滑，其形式如下：

其中，第1項是二值函數，當li≠lj時為1，反之為0，li≠lj表示像素xi，xj在分割邊界上；函數dist（）用來度量像素 xi，xj的歐式距離；是二范式，計算相鄰像素顏色差異；參數β控制分割邊界平滑性與準確度，可用如下公式計算：

其中，EP（）是相關數據的期望函數。

4.3 CRF中的高階項

考慮到條件隨機場中二階項在提高分割精度的同時導致過平滑現象，引入高階項，通過增加像素與所屬區域約束關系以緩解二元項帶來的負面影響。

本文將高階項建立在時空一致的超立體像素上，實現視頻分割中時空邊界一致性。假設超立體像素具備2個屬性：（1）每個supervoxel只屬于一個對象；（2）每個supervoxel時空邊界一致。首先使用streamGBH算法［18］對視頻進行分割，獲得如圖4所示時空邊界一致的超立體像素，然后創建高階項約束超立體像素，使其內部像素標注保持一致。

圖4 視頻超立體像素

高階項最初是以Potts模型引入計算機視覺。圖像分割時在能量函數中增加高階勢能的作用是促使子團里所有像素標注一致，其形式如下：其中，表示子團c中像素個數，在本文中使用圖4所示的超立體像素s作為子團，式（11）表明只有s中所有像素標注一樣時高階項為0，反之為。盡管這樣可以促使標注一致，但式（11）太過嚴格與苛刻，假設 s中含有像素｛x1，x2，x3，x4，x5，x6，x7｝，在標注分別為｛1，1，1，1，1，0，1｝和｛1，0，1，0，1，0，1｝的情況下，其代價函數是一樣的。當視頻聚類后獲得的超立體像素屬于不同對象或者時空邊界不一致時，采用式（11）的高階勢函數作為像素和超立體像素間的標注約束將導致分割邊界錯誤。為緩解這一問題，本文采用魯棒的Potts模型［19］，其定義如下：

基于魯棒的Potts模型和原始的Potts模型的高階項均促使超立體像素中像素標注一致，但前者允許一部分像素的標注和超立體像素的主要標注不一致，其高階勢函數和標注不一致的像素個數成線性關系，而后者只要出現一個像素的標注和主要標注不一致將給予最大代價值，實驗表明，魯棒的Potts模型能有效改善分割邊界。

因此高階條件隨機場框架中每幀的能量函數為以下形式：

4.4 抗噪性分析

在CRF能量函數中一元項是最為關鍵的一項，本文訓練雙模型以計算一元項，其中基于 texton，LBP，SIFT特征訓練Jointboost分類器，而SIFT特征對旋轉、尺度變換、噪聲保持一定的穩定性。另外，在CRF中引入基于超立體像素的高階項，使得圖像分割不僅與其像素特征相關，而且與其所屬超立體像素相關，增加了像素與時空鄰域像素的約束關系，提高了本文方法的抗噪性。圖5（a）為加入密度為0.02椒鹽噪聲的圖像，圖5（b）是本文方法的分割結果，圖5（c）是經濾波處理后的圖像，而圖5（d）為濾波處理后本文方法的分割結果，通過圖5（b）和圖5（d）對比可知，本文方法對存在噪聲污染的圖像分割具有抑制噪聲的能力，而且抑制效果比通過濾波預處理更佳。

圖5 椒鹽噪聲圖像及分割結果

5 實驗結果與分析

本文以Visual Studio 2012與OpenCV 2.43為開發平臺，在CPU為Intel Corei3?2130 3.40 GHz，內存為4 GB的計算機上進行實驗。實驗所用數據庫為來自文獻［20］的5個視頻序列和公開的SegTrack［21］數據庫中girl和parachute視頻。圖6分別為文獻［20］中5個視頻序列（名稱分別為 AN119T，DO01013，DO01030，DO01014，DO02001）的初始幀圖像及其初始化結果，每個視頻序列中包含至少一個前景對象。

這5個視頻序列的分割難點分別在于：AN119T中牛在行進過程中頭部鉆入草叢引起的遮擋問題，DO01013中多匹馬多前景對象問題，DO01030中向日葵復雜的邊緣，DO010014中狐貍的影子，DO02001中滑雪人的快速移動。

為驗證本文方法中模型的融合作用以及CRF中高階項的作用，首先在5個視頻序列的實驗中分別比較了基于單模型的CRF方法（包括單獨應用GMM模型的CRF_GMM方法、單獨應用Jointboost分類器模型的CRF_Boost方法），雙模型融合的CRF方法（CRF_GMM_Boost）以及本文提出的雙模型融合加高階項的方法。表1給出了上述4個方法在5個視頻序列上分割結果，圖像分辨率為352×288像素。表中使用平均錯誤像素數avg_err和錯誤像素率err_rate的方法衡量分割精確度，其計算方式如下：

其中，fi表示第i幀圖像分割結果；XOR為異或操作；GT為第i幀的地面情況；n是視頻總幀數；resolution指圖像的分辨率。

從表1可以看出，雖然在DO01014視頻中不含高階項的方法效果更佳，但在AN119T，DO01013，DO01030和DO02001視頻序列中本文方法的平均錯誤像素數均低于不含高階項的方法，這表明高階項能有效提高分割準確度。此外前2種方法的平均錯誤像素數均少后2種方法，這表明同時考慮顏色、紋理和 SIFT特征的模型能顯著改善分割結果。

表1 錯誤像素數量和錯誤率統計

為進一步驗證本文方法的分割效果，實驗中還將本文方法和其他相近的方法進行比較，包括Textonboost［17］，ALE方法［19］和 Akamine方法［20］。為了公平對比，Textonboost和ALE方法均為條件隨機場框架下的分割方法，采用和本文同樣的自動化方法獲得初始化信息。而Akamine的方法［20］是基于顯著性特征獲得初始化先驗。表2為本文方法與上述3種方法在5個視頻序列中的定量對比結果。從中可以看出，本文方法的錯誤率均低于Akamine方法［20］、ALE［19］和 Textonboost［17］。 圖7為使用本文方法的視頻分割效果圖，提取的牛、馬和向日葵等前景皆更準確。

表2 定量分析結果對比 %

圖7 本文方法分割結果

本文還在公開數據庫SegTrack上測試本文方法的有效性，并與其他最新的有監督［21，23］和無監督［5?6，22］分割方法做定量對比實驗。圖8顯示了本文方法的分割結果。表3為各種方法的定量分析對比，其中，girl視頻中本文的分割結果優于其他方法的結果，而在parachute視頻中文獻方法［6］的結果最優，這是因為本文方法處理光照變化的視頻分割存在一定的局限性。

圖8 本文方法在SegTrack數據庫中的分割結果

表3 各種方法在SegTrack數據集上的錯誤像素對比

本文采用圖割算法求解CRF中能量函數最小，其時間復雜度為O（mn2），n和m分別為圖中頂點數和邊數，分別對應CRF中隨機變量數和隨機變量間相關邊數。表4統計了實驗中每個視頻分割所用的總時間，各視頻總幀數和分辨率存在差異，故所用時間也存在差異。

表4 各視頻分割時間統計

6 結束語

本文提出一種基于魯棒高階條件隨機場的雙模型視頻自動分割方法。通過基于超像素顯著性特征的方法分割視頻初始幀以獲得初始化先驗信息。根據初始幀圖像的texton，LBP和SIFT特征使用聯合Boosting算法訓練一個強分類器模型，同時基于像素的RGB顏色信息學習GMM模型，使用雙模型聯合計算CRF中能量函數的一元項，并在CRF中加入基于超立體像素的高階項，最后使用迭代圖割算法使得高階CRF中的能量函數達到最小。在與同類方法的對比實驗中驗證了本文方法在分割準確性方面的優勢。在未來的工作中，可以研究將本文中的前景和背景分割擴展到語義分割，進而為視頻場景分析打下基礎。

［1］ Price B L，Morse B S，Coheb S.LIVEcut：Learning?based Interactive Video Segmentation by Evaluation of Multiple Propagated Cues［C］／／Proceedings of International Conference on Computer Vision.Washington D.C.，USA：IEEE Press，2009：779?786.

［2］ Bai Xue，Wang Jue，Simons D，et al.Video SnapCut：Robust Video Object Cutout Using Localized Classifiers［J］.ACM Transactions on Graphics，2009，28（3）：1?11.

［3］ Zhong Fan，Qin Xueying，Peng Qunsheng，et al.Discontinuity?aware Video Object Cutout［J］.ACM Transactions on Graphics，2012，31（6）：1?10.

［4］ 吳 琳，李海燕.面向生物醫學圖像的交互式分割算法［J］.計算機工程，2010，36（16）：208?209，212.

［5］ Zhang Dong，Javed O， Shah M.Video Object Segmentation Through Spatially Accurate and Temporally Dense Extraction of Primary Object Regions［C］／／Proceedings of Conference on Computer Vision and Pattern Recognition.Washington D.C.，USA：IEEE Press，2013：628?635.

［6］ Lee Y J，Kim J，Grauman K.Key?segments for Video Object Segmentation［C］／／Proceedings of International Conference on Computer Vision.Washington D.C.，USA：IEEE Press，2011：1995?2002.

［7］ 郭寶龍，侯 葉.基于圖切割的圖像自動分割方法［J］.模式識別與人工智能，2011，24（5）：604?609.

［8］ Boykov Y Y，Jolly M P.Interactive Graph Cuts for Optimal Boundary and Region Segmentation of Objects in ND Images［C］／／Proceedings of International Conference on Computer Vision.Washington D.C.，USA：IEEE Press，2001：105?112.

［9］ Blake A，Rother C，Brown M，et al.Interactive Image Segmentation Using an Adaptive GMMRF Model［M］.Berlin，Germany：Springer，2004.

［10］ Rother C，Kolmogorov V，Blake A.Grabcut：Interactive Foreground Extraction Using Iterated Graph Cuts［J］.ACM Transactions on Graphics，2004，23（3）：309?314.

［11］ Zhou Hailing，Zheng Jianm in，Wei Lei.Texture Aware Image Segmentation Using Graph Cuts and Active Contours［J］.Pattern Recognition，2013，46（6）：1719?1733.

［12］ Cheng Hsien?Ting， Ahuja N.Exploiting Nonlocal Spatiotemporal Structure for Video Segmentation［C］／／Proceedings of IEEE Conference on Computer Vision and Pattern Recognition.Washington D.C.，USA：IEEE Press，2012：741?748.

［13］ Lezama J，Alahari K，Sivic J，et al.Track to the Future：Spatio?temporal Video Segmentation with Long?range Motion Cues［C］／／Proceedings of Conference on Com?puter Vision and Pattern Recognition.Washington D.C.，USA：IEEE Press，2011：20?25.

［14］ Achanta R，Shaji A，Smith K，et al.SLIC Superpixels Compared to State?of?the?Art Superpixel Methods［J］.IEEE Transactions on Pattern Analysis and Machine Intelligence，2012，34（11）：2274?2282.

［15］ Lafferty J，Mccallum A.Conditional Random Fields：Probabilistic Models for Segmenting and Labeling Sequence Data［C］／／Proceedings of the 18th Inter?national Conference on Machine Learning.San Francisco，CA，USA：Morgan Kaufmann，2001：282?289.

［16］ Torralba A，Murphy K P，Freeman W T.Sharing Features：Efficient Boosting Procedures for Multiclass Object Detection［C］／／Proceedings of Conference on Computer Vision and Pattern Recognition.Washington，D.C.，USA：IEEE Press，2004：762?769.

［17］ Shotton J，W inn J，Rother C，et al.Textonboost：Joint Appearance，Shape and ContextModeling for Multi?class Object Recognition and Segmentation［M］.Berlin，Germany：Springer，2006.

［18］ Xu Chenliang，Xiong Caim ing，Corso J J.Stream ing Hierarchical Video Segmentation［M］.Berlin，Germany：Springer，2012.

［19］ Kohli P，Torr P H.Robust Higher Order Potentials for Enforcing Label Consistency［J］.International Journal of Computer Vision，2009，82（3）：302?324.

［20］ Akam ine K，Fukuchi K，Kimura A，et al.Fully Automatic Extraction of Salient Objects from Videos in Near Real Time［J］.The Computer Journal，2012，55（1）：3?14.

［21］ Tsai D，Flagg M，Rehg JM.Motion Coherent Tracking w ith Multi?label MRF Optim ization［J］.International Journal of Computer Vision，2012，100（2）：190?202.

［22］ Ma Tianyang，Latecki L J.Maximum Weight Cliquesw ith Mutex Constraints for Video Object Segmentation［C］／／Proceedings of Conference on Computer Vision and Pattern Recognition.Washington D.C.，USA：IEEE Press，2012：670?677.

［23］ Chockalingam P，Pradeep N，BitchfieldI S.Adaptive Fragments?based Tracking of Non?rigid Objects Using Level Sets［C］／／Proceedings of International Conference on Computer Vision.Washington D.C.，USA：IEEE Press，2009：1530?1537.

編輯 顧逸斐

Automatic Video Segmentation Based on Robust Higher Order Conditional Random Field

CHENG Tingting，GUO Lijun，HUANG Yuanjie
（College of Information Science and Engineering，Ningbo University，Ningbo 315211，China）

This paper presents an automatic video segmentation method based on robust higher order Conditional Random Field（CRF），which alleviates the problem that interactive segmentation is time?consum ing and labor?intensive，and oversegmentation is generated in unsupervised segmentation，and simple pairw ise?pixel segmentation cannot get accurate boundary.It utilizes the saliency based segmentation of the first frame of video as initial seeds instead of user labeling.The Gaussian m ixturemodel and a strong jointboost classifier model are respectively learned on the features of color，texture and shape，the combination of both in CRF improves the accuracy of segmentation.It adds higher order potential based on supervoxel to solve the shortcom ing of oversmoothing of pairw ise?pixel segmentation.Experimental results demonstrate that themethod ismore effective and efficient than the state?of?artmethods.

automatic video segmentation；higher order potential；supervoxel；Conditional Random Field（CRF）；double model fusion；feature fusion

1000?3428（2015）07?0261?08

A

TP391

10.3969／j.issn.1000?3428.2015.07.050

國家自然科學基金資助項目（61175026）；寧波市自然科學基金資助項目（2014A610031，2014A610032）；“信息與通信工程”浙江省重中之重學科開放基金資助項目（xkxl1426）；寧波大學胡嵐優秀博士基金資助項目（ZX2013000319）；寧波大學人才工程基金資助項目（20111537）。

程婷婷（1989-），女，碩士，主研方向：計算機視覺；郭立君，副教授、博士；黃元捷，碩士。

2015?01?04

2015?02?19E?mail：guolijun＠nbu.edu.cn