視頻識(shí)別中基于簇的在線運(yùn)動(dòng)分割算法研究

徐向藝，廖夢(mèng)怡

視頻識(shí)別中基于簇的在線運(yùn)動(dòng)分割算法研究

徐向藝，廖夢(mèng)怡

仿射相機(jī)模型下，運(yùn)動(dòng)分割問題轉(zhuǎn)化為子空間分離問題，處理這類問題的算法大多是離線算法，當(dāng)假設(shè)不滿足時(shí)性能很不理想。針對(duì)上述問題，提出一種在線運(yùn)動(dòng)分割算法，通過動(dòng)態(tài)標(biāo)簽傳輸和簇分割進(jìn)行運(yùn)動(dòng)分割。首先，根據(jù)固定數(shù)量的幀進(jìn)行初始化，接著，通過在線策略更新軌跡相似性，最后，利用動(dòng)態(tài)標(biāo)簽傳輸技術(shù)在幀間傳輸信息，對(duì)簇進(jìn)行評(píng)估和歸一化切分成本估計(jì)，實(shí)現(xiàn)動(dòng)態(tài)的簇分割?；诨鶞?zhǔn)數(shù)據(jù)集的仿真實(shí)驗(yàn)結(jié)果表明，算法的運(yùn)行結(jié)果與離線算法相當(dāng)。

仿射相機(jī)模型；運(yùn)動(dòng)分割；動(dòng)態(tài)標(biāo)簽；簇；軌跡

0 引言

最近幾年，來自電視直播、網(wǎng)絡(luò)視頻流和移動(dòng)設(shè)備流的視頻數(shù)量大量增加。然而，大多數(shù)運(yùn)動(dòng)分割算法[1,2]是離線算法，且計(jì)算開銷大。因此，處理流媒體視頻的效率較低，需要開發(fā)新的在線運(yùn)動(dòng)分割算法。在線運(yùn)動(dòng)分割算法可為大量應(yīng)用帶來幫助。例如，一是基于靜態(tài)相機(jī)的拍攝視頻，可以使用當(dāng)前背景去除技術(shù)[3]實(shí)現(xiàn)不同運(yùn)動(dòng)者的分割。一是使用運(yùn)動(dòng)分割技術(shù)離線處理視頻。如果處理之后出現(xiàn)更多可用數(shù)據(jù)，則情況會(huì)更為復(fù)雜，因?yàn)楸仨氁仡^重新處理整個(gè)視頻?？蓮脑诰€運(yùn)動(dòng)分割技術(shù)獲益的另一領(lǐng)域是3D電視處理。有了實(shí)時(shí)運(yùn)動(dòng)分割技術(shù)后，用戶設(shè)備處于移動(dòng)之中也可以進(jìn)行2D到3D轉(zhuǎn)換和視頻重新定位。其他應(yīng)用包括移動(dòng)目標(biāo)的在線檢測和分割，以及基于移動(dòng)平臺(tái)的視覺監(jiān)視，等等。

運(yùn)動(dòng)分割主要處理基于場景不同運(yùn)動(dòng)的特征軌跡分割問題，因此是實(shí)現(xiàn)目標(biāo)分割和動(dòng)態(tài)場景理解的重要步驟。鑒于此，本文提出一種在線運(yùn)動(dòng)分割算法，算法的成功實(shí)施對(duì)于動(dòng)態(tài)場景理解、視頻識(shí)別等應(yīng)用的發(fā)展具有重要意義。marple 7序列第40幀和150幀及基于本文算法的分割結(jié)果如圖1所示：

圖1 marple 7序列的第40和150幀及基于本文方法獲得的相應(yīng)的分割結(jié)果

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

1 相關(guān)工作

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

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

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

2 運(yùn)動(dòng)分割轉(zhuǎn)化為簇分割

本節(jié)主要討論如何把運(yùn)動(dòng)分割問題轉(zhuǎn)化為多重分割問題。首先，給出3維空間中的軌跡如何形成3維簇。然后，給出這些軌跡如何投影到2維圖片上時(shí)形成3維簇。

設(shè)X表示由構(gòu)成一個(gè)剛性對(duì)象的一組 3維點(diǎn)構(gòu)成。它與歐氏度量一起構(gòu)成3維簇。時(shí)間 t = 2,… ,F時(shí)的對(duì)象運(yùn)動(dòng)可被分別表示為剛性轉(zhuǎn)換，且為相機(jī)坐標(biāo)系中的一個(gè)3維點(diǎn)。于是，軌跡空間可定義為如下帶有子空間拓?fù)涞募希?/p>

此外，將3維軌跡投影到圖像坐標(biāo)系也將生成一個(gè)簇。

場景中的每種不同運(yùn)動(dòng)均會(huì)生成一個(gè)簇。在本文中，利用標(biāo)簽傳輸和密集軌跡技術(shù)解決簇分離問題。為了驗(yàn)證標(biāo)簽傳輸是否適合簇分離問題，如圖2所示：

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

圖2(a)是兩個(gè)月形示例。將這兩個(gè)月形分離可以看成簇分離問題。然而，在對(duì)該例子實(shí)行譜聚類時(shí)，由于距離較近，一個(gè)簇泄露到另一簇上。另一方面，經(jīng)過適當(dāng)?shù)某跏蓟?，?biāo)簽傳輸可以有效分離兩個(gè)月形如圖2(b)所示，。如下節(jié)所述，基于先前幀進(jìn)行初始化。

3 本文方法

本文方法從不斷擴(kuò)展和引入的密集軌跡入手，不斷更新與不同運(yùn)動(dòng)相對(duì)應(yīng)的軌跡分割。為此，首先給出如何通過在線策略更新軌跡相似性（3.1節(jié)）。然后，給出標(biāo)簽傳輸?shù)谋匾尘埃⒄務(wù)摦?dāng)簇不斷變化時(shí)如何使用標(biāo)簽傳輸方法維護(hù)分割（3.2節(jié)）。最后，在3.3節(jié)提出兩種不同的初始化方法。3.1 在線相似度計(jì)算

如上文所述，屬于同一個(gè)對(duì)象的軌跡位于3維簇上。然而，這些簇不是靜態(tài)的，因?yàn)樗鼈兪菍?duì)象運(yùn)動(dòng)的函數(shù)，而對(duì)象的運(yùn)動(dòng)隨時(shí)間發(fā)生變化。為了對(duì)這些動(dòng)態(tài)簇建模，且避免對(duì)每個(gè)幀重復(fù)求解，本文設(shè)計(jì)了一種可以通過步進(jìn)策略進(jìn)行計(jì)算的距離指標(biāo)。該計(jì)算過程必須及時(shí)進(jìn)行且與軌跡長度無關(guān)。此外，該指標(biāo)還需描述空間位置和運(yùn)動(dòng)的相似性。直觀來說，如果兩個(gè)軌跡距離較近且運(yùn)動(dòng)特點(diǎn)類似，因此更有可能屬于同一對(duì)象。鑒于此，下面將給出如何通過步進(jìn)策略計(jì)算該指標(biāo)。

3.2 標(biāo)簽傳輸

3.2.1 機(jī)器學(xué)習(xí)

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

然后，算法流程如下：當(dāng)從結(jié)點(diǎn)i開始進(jìn)行隨機(jī)游走直至找到標(biāo)簽時(shí)，向結(jié)點(diǎn)分配到達(dá)被貼上正值標(biāo)簽的示例的概率。這一概率可以表示為?？删仃囆问奖硎緸椋?/p>

可以證明，固定點(diǎn)解為：

3.2.2 基于動(dòng)態(tài)標(biāo)簽傳輸?shù)拇胤蛛x

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

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

為了解決這些問題，將當(dāng)前軌跡的標(biāo)簽作為先驗(yàn)知識(shí)，然后在考慮圖結(jié)構(gòu)的基礎(chǔ)上確定由先前幀擴(kuò)展而來的軌跡及新軌跡的標(biāo)簽。我們向當(dāng)前幀中的每個(gè)結(jié)點(diǎn)（軌跡）增添一個(gè)與先前幀的軌跡標(biāo)簽相對(duì)應(yīng)的安保結(jié)點(diǎn)。設(shè) Puu表示通過相似度矩陣 Wt獲得的轉(zhuǎn)換概率，增強(qiáng)后圖形的新轉(zhuǎn)換矩陣為：

看上去對(duì)每個(gè)即將到來的幀再次進(jìn)行標(biāo)簽傳輸?shù)淖龇ㄓ行┒嘤?，但是其?shí)不然，這主要是因?yàn)椋菏紫?，通過使用先前標(biāo)簽作為錨點(diǎn)，避免了在譜聚類中的“標(biāo)簽泄露”問題（圖 2）。其次，在實(shí)踐中用迭代方式求解式（4），通過將以前的幀標(biāo)簽作為初始解，可以在少量迭代內(nèi)實(shí)現(xiàn)收斂。

獲得了新標(biāo)簽后，需要評(píng)估有沒有新對(duì)象進(jìn)入場景，原來處于靜止?fàn)顟B(tài)的對(duì)象有沒有開始移動(dòng)。請(qǐng)注意，標(biāo)簽傳輸只傳輸當(dāng)前標(biāo)簽，不引入新的標(biāo)簽。如果有新的對(duì)象進(jìn)入場景，則必有新軌跡的一個(gè)相關(guān)集合。這些新軌跡必將通過標(biāo)簽傳輸接收到部分標(biāo)簽，并在相關(guān)簇中導(dǎo)致集群內(nèi)部發(fā)生顯著變化。類似的，如果有靜態(tài)對(duì)象開始移動(dòng)，則將降低對(duì)象軌跡和同一簇內(nèi)其他軌跡間的相似性。因此，需要挨個(gè)檢查簇，確定有沒有簇需要分割。具體方法是通過歸一化切割來計(jì)算最優(yōu)二元切割，然后評(píng)估歸一化切割成本。如果成本大于閾值，則保持簇不動(dòng)。

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

3.3 初始化

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

圖3 marple6序列的初始化。

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

4 仿真實(shí)驗(yàn)

本節(jié)利用文獻(xiàn)[8]中的Berkley數(shù)據(jù)集評(píng)估本文算法，仿真工具為Matlab2012。數(shù)據(jù)集有26個(gè)序列，包括剛性和關(guān)節(jié)運(yùn)動(dòng)。將數(shù)據(jù)集的真實(shí)數(shù)據(jù)作為189個(gè)幀的幀注釋。數(shù)據(jù)集包括一個(gè)評(píng)估工具。然而，請(qǐng)注意，評(píng)估工具只能用于離線算法。例如，它假設(shè)整個(gè)序列中的每個(gè)軌跡均被分配一個(gè)標(biāo)簽；如果軌跡在視頻序列開始時(shí)被分配了一個(gè)錯(cuò)誤標(biāo)簽，那么即使標(biāo)簽在后續(xù)幀中被糾正，軌跡也會(huì)受到懲罰。類似地，如果一個(gè)對(duì)象是靜止對(duì)象然后運(yùn)動(dòng)，那么該方法也會(huì)因?yàn)楫?dāng)對(duì)象處于靜止?fàn)顟B(tài)時(shí)沒有分割對(duì)象而受到懲罰。這會(huì)給本文方法帶來不利影響，因?yàn)闊o法在運(yùn)動(dòng)出現(xiàn)前實(shí)現(xiàn)運(yùn)動(dòng)檢測。在實(shí)際應(yīng)用中，通過預(yù)測流程可以緩解上述問題，此時(shí)，算法被允許提前幾幀運(yùn)行以延緩決策。出于一致性考慮，本文使用相同的評(píng)估工具衡量誤差。

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

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

圖4 增加窗口尺寸后對(duì)滑動(dòng)窗口RANSAC結(jié)果的影

雖然增加滑動(dòng)窗口大小可以提升效果，但是尋找橫跨整個(gè)窗口的軌跡會(huì)更加困難，進(jìn)而顯著降低密度。最右側(cè)圖像：cars4序列的第40幀。右面3個(gè)圖像：滑動(dòng)窗口值為10、20和30時(shí)的分割結(jié)果。當(dāng)滑動(dòng)窗口大小增加時(shí)，橫跨整個(gè)窗口的軌跡數(shù)量變少。

本文方法運(yùn)行于文獻(xiàn)[8]中數(shù)據(jù)集時(shí)獲得的定量結(jié)果，如表1所示：

表1Berkley數(shù)據(jù)集的評(píng)估結(jié)果

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

當(dāng)幀數(shù)超過 10個(gè)時(shí)，本文方法的性能優(yōu)于 GPCA、RANSAC、LSA，且運(yùn)行結(jié)果與文獻(xiàn)[8]相當(dāng)。實(shí)際上，如果把范圍限定于更長的序列，則本文方法結(jié)果優(yōu)于文獻(xiàn)[8]，如第2組實(shí)驗(yàn)所示。這表明本文方法的性能優(yōu)于傳統(tǒng)算法，且精度相當(dāng)。當(dāng)序列較長時(shí)，方法性能與RANSAC算法相當(dāng)，這一現(xiàn)象表明任何基于滑動(dòng)窗口的在線算法均存在的一個(gè)重要問題?；瑒?dòng)窗口之外的信息無法被記住，因此往往融合已經(jīng)獲知具有不同運(yùn)動(dòng)特征的對(duì)象。

最后，對(duì)整個(gè)數(shù)據(jù)集，實(shí)現(xiàn)了在線性能，但是本文方法的性能略低于文獻(xiàn)[8]。如果采用預(yù)測策略，軌跡決策延遲數(shù)個(gè)幀，則可進(jìn)一步降低這些誤差。

不同算法對(duì)marple1序列前10幀的運(yùn)行時(shí)間，如表2所示：

表2 marple1序列10個(gè)以上幀時(shí)的計(jì)算時(shí)間

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

marple1序列單獨(dú)一個(gè)幀時(shí)不同階段的計(jì)算時(shí)間，如表3所示：

表3 marple1序列單獨(dú)一個(gè)幀時(shí)不同階段的計(jì)算時(shí)間

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

5 總結(jié)

本文給出了如何將運(yùn)動(dòng)分割問題轉(zhuǎn)化為簇分離問題。以此為基礎(chǔ)，給出了一種在線運(yùn)動(dòng)分割算法，該算法不會(huì)損失當(dāng)前最新算法的精度。通過對(duì)動(dòng)態(tài)變化的圖使用標(biāo)簽傳輸方法，本文方法既可以維護(hù)標(biāo)簽，又可以當(dāng)更多信息可用時(shí)從誤差中恢復(fù)。本文算法在基準(zhǔn)數(shù)據(jù)集上的運(yùn)行結(jié)果與離線算法相當(dāng)。

需要在線處理的多種應(yīng)用場景促使我們研發(fā)本文算法。例如，可以通過實(shí)時(shí)運(yùn)動(dòng)分割實(shí)現(xiàn)用戶設(shè)備的在線視頻定位。當(dāng)視頻可離線獲得時(shí)，使用當(dāng)前離線算法處理2小時(shí)左右的視頻需要耗時(shí)數(shù)周。下一步研究工作的重點(diǎn)是基于壓縮感知技術(shù)來對(duì)運(yùn)動(dòng)分割中的異常目標(biāo)進(jìn)行快速識(shí)別。

[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] 蔣鵬, 秦娜, 周艷, 等. 一種基于均值偏移的自動(dòng)運(yùn)動(dòng)分割方法[J]. 計(jì)算機(jī)科學(xué), 2013, 40(8): 273-276.

[5] 馮林, 劉勝藍(lán), 王靜, 等. 人體運(yùn)動(dòng)分割算法: 序列局部彎曲的流形學(xué)習(xí)[J]. 計(jì)算機(jī)輔助設(shè)計(jì)與圖形學(xué)學(xué)報(bào), 2013, 25(4): 460-467.

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

[7] 王詩言, 于慧敏. 運(yùn)動(dòng)場景下的時(shí)空域跟蹤模型及原始-對(duì)偶算法[J]. 浙江大學(xué)學(xué)報(bào) (工學(xué)版), 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）

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

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

廖夢(mèng)怡（1983-），女，河南南陽人，平頂山學(xué)院，軟件學(xué)院，講師，碩士，研究方向：云計(jì)算、數(shù)字媒體技術(shù)，平頂山，467002

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