視頻識別中基于簇的在線運動分割算法研究

徐向藝，廖夢怡

視頻識別中基于簇的在線運動分割算法研究

徐向藝，廖夢怡

仿射相機模型下，運動分割問題轉化為子空間分離問題，處理這類問題的算法大多是離線算法，當假設不滿足時性能很不理想。針對上述問題，提出一種在線運動分割算法，通過動態標簽傳輸和簇分割進行運動分割。首先，根據固定數量的幀進行初始化，接著，通過在線策略更新軌跡相似性，最后，利用動態標簽傳輸技術在幀間傳輸信息，對簇進行評估和歸一化切分成本估計，實現動態的簇分割。基于基準數據集的仿真實驗結果表明，算法的運行結果與離線算法相當。

仿射相機模型；運動分割；動態標簽；簇；軌跡

0 引言

最近幾年，來自電視直播、網絡視頻流和移動設備流的視頻數量大量增加。然而，大多數運動分割算法[1,2]是離線算法，且計算開銷大。因此，處理流媒體視頻的效率較低，需要開發新的在線運動分割算法。在線運動分割算法可為大量應用帶來幫助。例如，一是基于靜態相機的拍攝視頻，可以使用當前背景去除技術[3]實現不同運動者的分割。一是使用運動分割技術離線處理視頻。如果處理之后出現更多可用數據，則情況會更為復雜，因為必須要重頭重新處理整個視頻。可從在線運動分割技術獲益的另一領域是3D電視處理。有了實時運動分割技術后，用戶設備處于移動之中也可以進行2D到3D轉換和視頻重新定位。其他應用包括移動目標的在線檢測和分割，以及基于移動平臺的視覺監視，等等。

運動分割主要處理基于場景不同運動的特征軌跡分割問題，因此是實現目標分割和動態場景理解的重要步驟。鑒于此，本文提出一種在線運動分割算法，算法的成功實施對于動態場景理解、視頻識別等應用的發展具有重要意義。marple 7序列第40幀和150幀及基于本文算法的分割結果如圖1所示：

圖1 marple 7序列的第40和150幀及基于本文方法獲得的相應的分割結果

可以看到，即使marple 7的第40幀受到遮蔽影響，但在整個幀序列中仍然得到正確跟蹤。

1 相關工作

運動分割問題是目前視頻應用領域研究的熱點問題，相繼有眾多學者提出了一系列有代表性的方法，如文獻[4]提出一種基于均值偏移的自動運動分割算法。文獻[5]針對已有的基于流形學習的分割算法多采取全局或局部線性化的學習策略，無法解決序列數據的局部高曲率問題，利用數據的幾何特征描述運動的連貫性，提出一種時序流形學習的人體運動分割方法。文獻[6]針對復雜視頻監控場景中不同運動行為的人群分割，提出了將視頻粒子流和有限時間李雅普諾夫指數（FTLE）場相結合的人群運動分割算法。

另外還有，文獻[7]針對攝像機運動的情況，提出多目標分割和跟蹤的新方法。利用主動輪廓模型，將運動估計和運動分割融合在同一基于時空域的能量泛函中。文獻[8] 使用運動目標軌跡周圍的局部信息來計算相似度矩陣。然后通過衡量子空間間的角度來構建仿射矩陣。然后使用譜聚類方法進行軌跡簇來實現運動目標分割。文獻[9]基于分解的方法直接對軌跡矩陣進行分解。當運動獨立時這些方法性能優異。然而，大多數情況下，多種剛性運動不是獨立的，比如關節運動。總的來說，以上的大多數運動分割算法都還存在如下的問題：1）將視頻的運動分割問題表示為軌跡矩陣的分解問題，因此許多算法假設軌跡橫跨整個幀序列。為了處理部分軌跡丟失問題，這些方法借鑒矩陣填充思想。然而，這種做法的效果有限，因為它假設存在部分軌跡橫跨整個幀序列；2）仿射相機的假設[3]也限制了把運動分割應用到滿足假設的視頻中；3）當前的算法大多是離線算法，且計算開銷大。因此，處理流媒體視頻的效率較低，需要開發新的在線運動分割算法。

為了解決以上方法的不足，本文提出看了一種改進的運動分割算法，與先前方法相比，本文方法是實現在線運動分割的首個算法，且每幀計算時間相同。文中明確地以簇為基礎對軌跡建模，因此即使仿射相機假設沒有滿足，也可以處理視頻。另外，本文方法在計算相似度矩陣時考慮了軌跡的整個歷史信息。最后的仿真實驗也驗證了本文算法的有效性。

2 運動分割轉化為簇分割

本節主要討論如何把運動分割問題轉化為多重分割問題。首先，給出3維空間中的軌跡如何形成3維簇。然后，給出這些軌跡如何投影到2維圖片上時形成3維簇。

設X表示由構成一個剛性對象的一組 3維點構成。它與歐氏度量一起構成3維簇。時間 t = 2,… ,F時的對象運動可被分別表示為剛性轉換，且為相機坐標系中的一個3維點。于是，軌跡空間可定義為如下帶有子空間拓撲的集合：

此外，將3維軌跡投影到圖像坐標系也將生成一個簇。

場景中的每種不同運動均會生成一個簇。在本文中，利用標簽傳輸和密集軌跡技術解決簇分離問題。為了驗證標簽傳輸是否適合簇分離問題，如圖2所示：

圖2 譜聚類(a)VS標簽傳輸(b)

圖2(a)是兩個月形示例。將這兩個月形分離可以看成簇分離問題。然而，在對該例子實行譜聚類時，由于距離較近，一個簇泄露到另一簇上。另一方面，經過適當的初始化，標簽傳輸可以有效分離兩個月形如圖2(b)所示，。如下節所述，基于先前幀進行初始化。

3 本文方法

本文方法從不斷擴展和引入的密集軌跡入手，不斷更新與不同運動相對應的軌跡分割。為此，首先給出如何通過在線策略更新軌跡相似性（3.1節）。然后，給出標簽傳輸的必要背景，并談論當簇不斷變化時如何使用標簽傳輸方法維護分割（3.2節）。最后，在3.3節提出兩種不同的初始化方法。3.1 在線相似度計算

如上文所述，屬于同一個對象的軌跡位于3維簇上。然而，這些簇不是靜態的，因為它們是對象運動的函數，而對象的運動隨時間發生變化。為了對這些動態簇建模，且避免對每個幀重復求解，本文設計了一種可以通過步進策略進行計算的距離指標。該計算過程必須及時進行且與軌跡長度無關。此外，該指標還需描述空間位置和運動的相似性。直觀來說，如果兩個軌跡距離較近且運動特點類似，因此更有可能屬于同一對象。鑒于此，下面將給出如何通過步進策略計算該指標。

3.2 標簽傳輸

3.2.1 機器學習

本節介紹本文在線對象分割算法使用的機器學習方法。已知圖G和權重矩陣W 且是結點i和 j間的鏈接權重，半監督學習的一種簡單思路就是在圖中傳輸標簽。設表示被貼標的結點的標簽。此外，表示結點標簽估計，且和分別對應于被貼標和未被貼標的結點。和基于二進制編碼方法進行編碼，Y的每個行向量如果元素為1，則表明對應于結點的標簽，否則為 0。為了估計標簽概率，文獻[10]給出的算法對圖進行馬爾科夫隨機游走，從i到j的轉換概率為：

然后，算法流程如下：當從結點i開始進行隨機游走直至找到標簽時，向結點分配到達被貼上正值標簽的示例的概率。這一概率可以表示為。可矩陣形式表示為：

可以證明，固定點解為：

3.2.2 基于動態標簽傳輸的簇分離

已知幀 t?1時的軌跡分段情況，本文的目標是獲得幀t時的更新標簽。為此，需要處理如下幾種情形。首先，新軌跡可能被引入到距離矩陣中；其次，當前軌跡的運動信息可能要求我們必須對當前簇進行分割或融合。此外，在前種情況下，新的軌跡可能屬于當前對象或者屬于新的對象。在本節中，我們描述如何利用本文方法處理這兩種情況。

首先，本文研究假設沒有新的對象進入場景后，如何利用新的信息更新簇標簽。對每個幀，假設擴展后的軌跡具有不同段標簽的概率分布。推斷標簽定義為概率最大的標簽。然后，一種方法就是使用這些標簽作為有監督標簽，再根據利用被標記樣本學習而得的分類器確定新軌跡的標簽。這種方法有幾個問題。首先，沒有重訪當前標簽，因此無法根據標簽糾正差錯。其次，分類器沒有考慮本文已經獲得的圖結構。

為了解決這些問題，將當前軌跡的標簽作為先驗知識，然后在考慮圖結構的基礎上確定由先前幀擴展而來的軌跡及新軌跡的標簽。我們向當前幀中的每個結點（軌跡）增添一個與先前幀的軌跡標簽相對應的安保結點。設 Puu表示通過相似度矩陣 Wt獲得的轉換概率，增強后圖形的新轉換矩陣為：

看上去對每個即將到來的幀再次進行標簽傳輸的做法有些多余，但是其實不然，這主要是因為：首先，通過使用先前標簽作為錨點，避免了在譜聚類中的“標簽泄露”問題（圖 2）。其次，在實踐中用迭代方式求解式（4），通過將以前的幀標簽作為初始解，可以在少量迭代內實現收斂。

獲得了新標簽后，需要評估有沒有新對象進入場景，原來處于靜止狀態的對象有沒有開始移動。請注意，標簽傳輸只傳輸當前標簽，不引入新的標簽。如果有新的對象進入場景，則必有新軌跡的一個相關集合。這些新軌跡必將通過標簽傳輸接收到部分標簽，并在相關簇中導致集群內部發生顯著變化。類似的，如果有靜態對象開始移動，則將降低對象軌跡和同一簇內其他軌跡間的相似性。因此，需要挨個檢查簇，確定有沒有簇需要分割。具體方法是通過歸一化切割來計算最優二元切割，然后評估歸一化切割成本。如果成本大于閾值，則保持簇不動。

本文使用如下的方法進行切割。首先，提取與將要評估的簇相對應的子矩陣。然后，求解廣義特征值問題。此時，提取與第二最小特征值對應的本征向量，對不同的閾值評估歸一化切割成本。歸一化切割成本表示為其中y表示閾值本征向量。然后，選擇使歸一化切割成本最小的向量y作為最優切割。歸一化切割成本范圍為0到1。在本文方法中，如果切割成本低于閾值，便分割簇。

3.3 初始化

假設在時刻t時的幀，知道時刻t?1時的軌跡標簽。本文有兩種方法啟動系統。首先，可以使用與偏向相機假設無關的離線運動分段算法，以生成初始標簽。另一種方法是在開始時為所有軌跡分配一個標簽，利用本文簇分割算法確定類別數量。在本文實驗中，使用后一種方法，并證明即使不用初始化，也可以檢測出場景中的移動對象。簇分割流程如何從單個簇的初始分配開始，進而分割出場景中的兩個人，如圖3所示：

圖3 marple6序列的初始化。

從上至下為第100，160和260幀及其相應的分割結果。在第1個幀中，所有軌跡的標簽相同，且場景中幾乎沒有運動。100幀之后，倚在墻上的男人開始移動，并從背景簇中被自動分割出來。類似地，第160幀之后，靠近攝像機的男人也被檢測并從背景中分割出來。

4 仿真實驗

本節利用文獻[8]中的Berkley數據集評估本文算法，仿真工具為Matlab2012。數據集有26個序列，包括剛性和關節運動。將數據集的真實數據作為189個幀的幀注釋。數據集包括一個評估工具。然而，請注意，評估工具只能用于離線算法。例如，它假設整個序列中的每個軌跡均被分配一個標簽；如果軌跡在視頻序列開始時被分配了一個錯誤標簽，那么即使標簽在后續幀中被糾正，軌跡也會受到懲罰。類似地，如果一個對象是靜止對象然后運動，那么該方法也會因為當對象處于靜止狀態時沒有分割對象而受到懲罰。這會給本文方法帶來不利影響，因為無法在運動出現前實現運動檢測。在實際應用中，通過預測流程可以緩解上述問題，此時，算法被允許提前幾幀運行以延緩決策。出于一致性考慮，本文使用相同的評估工具衡量誤差。

文獻[8]的評估工具為每種序列生成5種指標，然后對所有序列求均值。這5種指標是：密度、總體誤差、平均誤差、過分割誤差、以及誤差在10%以下的段數（簡稱為lt10）。密度衡量被標記的軌跡與像素總數量之比。密度越大，表明圖像覆蓋范圍越大。如果算法要求滑動窗口的所有軌跡，則會降低密度。總體誤差是正確標記的軌跡數量與被標記的總軌跡之比。評估工具會自動計算簇相對真實數據區域的分配情況，并有可能將多個簇分配給同一個區域。平均簇誤差表示每個區域被錯誤標記的軌跡與軌跡所有數量之比的均值。因為評估工具可能會把多個段分配給同一個真實數據區域，因此評估工具也會給出過分割誤差，該誤差定義為經過融合以匹配真實數據區域的段的數量。此外，評估工具也會給出誤差低于10%的被覆蓋區域數量，且鑒于背景因素，每個序列需減去一個區域。

將本文算法與RANSAC[11]、GPCA[12]和LSA[13]等離線算法做比較。如文獻[8]所示，當軌跡數量上升時，其他運動分割算法的伸縮性較差。例如，對people1序列的10多個幀，GPCA需要2963秒，LSA需要38614秒，因此，無法基于滑動窗口運行這些窗口。增加窗口大小對密度和分割效果的影響，如圖4所示：

圖4 增加窗口尺寸后對滑動窗口RANSAC結果的影

雖然增加滑動窗口大小可以提升效果，但是尋找橫跨整個窗口的軌跡會更加困難，進而顯著降低密度。最右側圖像：cars4序列的第40幀。右面3個圖像：滑動窗口值為10、20和30時的分割結果。當滑動窗口大小增加時，橫跨整個窗口的軌跡數量變少。

本文方法運行于文獻[8]中數據集時獲得的定量結果，如表1所示：

表1Berkley數據集的評估結果

本文進行3組實驗。首先，針對不包含第1幀的前10幀對本文方法與RANSAC、GPCA和LSA做比較。該實驗的目的是定量評估本文算法相對傳統的運動分割算法的性能，這些傳統的運動分割算法需要橫跨整個序列的軌跡集合。在第2組實驗中，評估了前200幀的算法性能。為了避免初始化在結果中導致的偏差，從第50幀往后結合真實數據幀展開評估。這組實驗的目的是評估算法對長序列的性能。這些序列代表了在線算法的典型應用情景。最后，在第3組實驗中，結合整個序列集合和真實數據注釋圖片進行評估。

當幀數超過 10個時，本文方法的性能優于 GPCA、RANSAC、LSA，且運行結果與文獻[8]相當。實際上，如果把范圍限定于更長的序列，則本文方法結果優于文獻[8]，如第2組實驗所示。這表明本文方法的性能優于傳統算法，且精度相當。當序列較長時，方法性能與RANSAC算法相當，這一現象表明任何基于滑動窗口的在線算法均存在的一個重要問題。滑動窗口之外的信息無法被記住，因此往往融合已經獲知具有不同運動特征的對象。

最后，對整個數據集，實現了在線性能，但是本文方法的性能略低于文獻[8]。如果采用預測策略，軌跡決策延遲數個幀，則可進一步降低這些誤差。

不同算法對marple1序列前10幀的運行時間，如表2所示：

表2 marple1序列10個以上幀時的計算時間

雖然文獻[8]對前10個幀用時19秒，但是將該方法用于滑動窗口時每個幀就需19秒。另一方面，在Matlab2012上未經優化而部署時，每幀需要3秒左右。表3進一步表明，計算時間主要由n n× 距離矩陣的更新和仿射矩陣的計算確定。本文認為，因為這些操作可以基于GPU并行處理，所以實現實時性能的難度不大。

marple1序列單獨一個幀時不同階段的計算時間，如表3所示：

表3 marple1序列單獨一個幀時不同階段的計算時間

各個階段為：跟蹤（track），距離矩陣更新（dist），仿射矩陣(aff)和標簽傳輸（lblprop）。時間以毫秒為單位，軌跡數量為4427。沒有包含跟蹤時消耗的光流計算。

5 總結

本文給出了如何將運動分割問題轉化為簇分離問題。以此為基礎，給出了一種在線運動分割算法，該算法不會損失當前最新算法的精度。通過對動態變化的圖使用標簽傳輸方法，本文方法既可以維護標簽，又可以當更多信息可用時從誤差中恢復。本文算法在基準數據集上的運行結果與離線算法相當。

需要在線處理的多種應用場景促使我們研發本文算法。例如，可以通過實時運動分割實現用戶設備的在線視頻定位。當視頻可離線獲得時，使用當前離線算法處理2小時左右的視頻需要耗時數周。下一步研究工作的重點是基于壓縮感知技術來對運動分割中的異常目標進行快速識別。

[1] Unger M, Werlberger M, Pock T, et al. Joint motion estimation and segmentation of complex scenes w ith label costs and occlusion modeling[C]. Computer Vision and Pattern Recognition (CVPR), 2012 IEEE Conference on. IEEE, 2012: 1878-1885.

[2] Zappella L, Lladó X, Provenzi E, et al. Enhanced local subspace affinity for feature-based motion segmentation[J]. Pattern Recognition, 2011, 44(2): 454-470.

[3] Turaga P, Chellappa R, Subrahmanian V S, et al. Machine recognition of human activities: A survey [J]. Circuits and Systems for Video Technology, IEEE Transactions on, 2008, 18(11): 1473-1488.

[4] 蔣鵬, 秦娜, 周艷, 等. 一種基于均值偏移的自動運動分割方法[J]. 計算機科學, 2013, 40(8): 273-276.

[5] 馮林, 劉勝藍, 王靜, 等. 人體運動分割算法: 序列局部彎曲的流形學習[J]. 計算機輔助設計與圖形學學報, 2013, 25(4): 460-467.

[6] 童超, 章東平, 陳非予. 基于視頻粒子流和 FTLE 場的人群運動分割算法[J]. 計算機應用, 2012, 32(1): 252-255.

[7] 王詩言, 于慧敏. 運動場景下的時空域跟蹤模型及原始-對偶算法[J]. 浙江大學學報 (工學版), 2013, 47(4)：521-528

[8] Brox T, Malik J. Object segmentation by long term analysis of point trajectories [M]. Computer Vision–ECCV 2010. Springer Berlin Heidelberg, 2010: 282-295.

[9] Zelnik-Manor L, Machline M, Irani M. Multi-body factorization w ith uncertainty: Revisiting motion consistency [J]. International Journal of Computer Vision, 2012, 68(1): 27-41.

[10] Zhu X, Ghahramani Z, Lafferty J. Sem i-supervised learning using Gaussian fields and harmonic functions[C]. ICML. 2013: 912-919.

[11] Tron R, Vidal R. A benchmark for the comparison of 3-d motion segmentation algorithms[C]. Computer Vision and Pattern Recognition, 2007. CVPR'07. IEEE Conference on. IEEE, 2007: 1-8.

[12] Vidal R, Hartley R. Motion segmentation w ith m issing data using Power Factorization and GPCA[C]. Computer Vision and Pattern Recognition, 2004. CVPR 2004. Proceedings of the 2004 IEEE Computer Society Conference on. IEEE, 2004：310-316

[13] Yan J, Pollefeys M. A general framework for motion segmentation: Independent, articulated, rigid, non-rigid, degenerate and non-degenerate [M]. Computer Vision–ECCV 2011. Springer Berlin Heidelberg, 2011: 94-106

Research on Online M otion Segmentation A lgorithm Based on Clustering in Video Identification

Xu Xiangyi, Liao Mengyi
(School of Software, Pingdingshan University, Pingdingshan, 467002, China)

Under the affine model, the motion segmentation problem becomes that of subspace separation. Due to this assumption, such methods are mainly off-line and exhibit poor performance when the assumption is not satisfied. In order to solve these problem we propose an approach that achieves online motion segmentation through dynam ic label propagation and cluster splitting. Starting from an initialization computed over a m ixed number of frames, we update the sim ilarity between trajectories in an online fashion. A fter that, we propagate the label information from one frame to the next using dynam ic label propagation, at the same time , evaluate each cluster and measure a normalized cut cost of splitting the cluster for dynamic cluster splitting. The performance of the proposed algorithm is evaluated on a benchmark dataset and achieves competitive performance while being online.

Affine Camera Model; Motion Segmentation; Dynamic Label; Cluster; Trajectories

TP393

A

2014.06.25）

國家自然科學基金（NU1204611）；河南省自然科學基金（132300410278）

徐向藝（1979-），女，河南平頂山人，平頂山學院，軟件學院，講師，碩士，研究方向：智能算法、圖像處理，平頂山，467002

廖夢怡（1983-），女，河南南陽人，平頂山學院，軟件學院，講師，碩士，研究方向：云計算、數字媒體技術，平頂山，467002

1007-757X(2014)11-0020-05