基于自適應(yīng)流形去噪的視頻運(yùn)動(dòng)分割算法

楊章瓊

(宜賓職業(yè)技術(shù)學(xué)院， 四川 宜賓 644000)

?

基于自適應(yīng)流形去噪的視頻運(yùn)動(dòng)分割算法

楊章瓊

(宜賓職業(yè)技術(shù)學(xué)院， 四川 宜賓 644000)

針對(duì)現(xiàn)有運(yùn)動(dòng)分割算法的不足，提出一種新的運(yùn)動(dòng)分割算法，通過自適應(yīng)流形去噪實(shí)現(xiàn)剛性和非剛性對(duì)象的運(yùn)動(dòng)分割。首先，引入一種自適應(yīng)核空間，如果2個(gè)特征軌跡屬于同一剛性對(duì)象，則將其映射到相同點(diǎn)上。然后，采用一種基于自適應(yīng)內(nèi)核的嵌入式流形去噪算法分割出剛性和非剛性對(duì)象的運(yùn)動(dòng)，證明了對(duì)內(nèi)核空間進(jìn)行流形去噪等價(jià)于在列空間進(jìn)行流形去噪。結(jié)果表明，該自適應(yīng)流形去噪算法適合于剛性和非剛性運(yùn)動(dòng)分割，在多種當(dāng)前最新算法均失效的場(chǎng)景下，算法仍然具有優(yōu)異性能。

視頻運(yùn)動(dòng)分割； 計(jì)算機(jī)視覺； 自適應(yīng)流形去噪； 核空間

0 引 言

視頻運(yùn)動(dòng)分割問題[1-2]是計(jì)算機(jī)視覺和圖像理解領(lǐng)域的一個(gè)重要研究課題，其目的是通過一組圖像或視頻序列來預(yù)測(cè)并估計(jì)對(duì)象在一段時(shí)間內(nèi)的運(yùn)動(dòng)。它也是許多實(shí)際應(yīng)用中一個(gè)重要的計(jì)算機(jī)視覺處理步驟。傳統(tǒng)的視頻運(yùn)動(dòng)分割方法[3-5]將視頻序列中的每一幀圖像分離為相干二維或三維運(yùn)動(dòng)的不同區(qū)域(光流)。然后，研究人員將包含不同運(yùn)動(dòng)對(duì)象的場(chǎng)景綜合起來，試圖將每個(gè)對(duì)象及其運(yùn)動(dòng)作為一種相干實(shí)體進(jìn)行識(shí)別。這些研究可以分為仿射算法和透視算法[6-9]。文獻(xiàn)[7]中提出一種多特征穩(wěn)健主成分分析(MFRPCA)算法，文獻(xiàn)[8]中提出一種基于時(shí)空信息的運(yùn)動(dòng)對(duì)象分割算法。文獻(xiàn)[9]中提出一種基于全局運(yùn)動(dòng)補(bǔ)償和核密度檢測(cè)的動(dòng)態(tài)場(chǎng)景下視頻運(yùn)動(dòng)對(duì)象分割算法。然而，之前的研究均假設(shè)同一對(duì)象的關(guān)鍵點(diǎn)位于嚴(yán)格的仿射子空間上，該假設(shè)在許多實(shí)際應(yīng)用中尤其是出現(xiàn)非剛性對(duì)象時(shí)并不成立。更糟糕的是，類似對(duì)象在帶噪流形上往往具有共同的區(qū)域或子空間，使傳統(tǒng)算法難以用于對(duì)象分割。

本文提出一種新的運(yùn)動(dòng)分割算法。該算法假設(shè)對(duì)象點(diǎn)的軌跡位于平滑流形上，并通過自適應(yīng)流形去噪獲得分割結(jié)構(gòu)。實(shí)驗(yàn)結(jié)果表明，本文算法對(duì)剛性和非剛性運(yùn)動(dòng)分割均具有優(yōu)異性能。在部分場(chǎng)景下即使當(dāng)前其他算法失效，本文算法仍然有效。

1 多人體視頻運(yùn)動(dòng)分割

本文從多個(gè)仿射角度分析了三維運(yùn)動(dòng)分割問題的幾何特征，并證明該問題等價(jià)于對(duì)高維空間的多個(gè)低維線性子空間進(jìn)行聚類。這一問題可表述如下：假設(shè)運(yùn)動(dòng)點(diǎn)軌跡對(duì)應(yīng)于相對(duì)攝像機(jī)進(jìn)行C種不同剛性人體運(yùn)動(dòng)的C個(gè)對(duì)象，在該條件下，根據(jù)C個(gè)運(yùn)動(dòng)對(duì)軌跡進(jìn)行聚類。此外，大多數(shù)真實(shí)應(yīng)用場(chǎng)景既需處理剛性對(duì)象又需處理非剛性對(duì)象。例如，機(jī)器人需要從剛性環(huán)境中采集信息，又需識(shí)別人體等非剛性對(duì)象。先前算法[6-9]并不能同時(shí)處理剛性和非剛性對(duì)象。

1.1 剛性人體運(yùn)動(dòng)的運(yùn)動(dòng)子空間

攝像機(jī)變換往往為仿射變換，對(duì)于幀f中圖像點(diǎn)Xp∈P3的非均勻坐標(biāo)xfp∈R2，滿足如下投影方程：

(1)

(2)

1.2 多對(duì)象剛性人體運(yùn)動(dòng)的運(yùn)動(dòng)子空間

(3)

(4)

其中:S表示分塊對(duì)角矩陣，有多種方法可實(shí)現(xiàn)上述分解[10-11]。本文重點(diǎn)研究假設(shè)通過熱傳播過程由平滑低維流形生成B后的直接聚類算法，即B圖像的子空間可被認(rèn)為是R2F中Grassmannian空間上的點(diǎn)。

2 自適應(yīng)流形去噪

自適應(yīng)流形去噪的目的是刪除傳感器、關(guān)鍵點(diǎn)匹配和非剛性效應(yīng)帶來的噪聲。然而，先前的流形去噪算法[12]無法直接應(yīng)用于運(yùn)動(dòng)分割問題，本文提出一種新的基于流形去噪的運(yùn)動(dòng)分割算法。

2.1 流形去噪

文獻(xiàn)[12]中的流形去噪模型假設(shè)數(shù)據(jù)點(diǎn)位于帶有噪聲的未知p維流形M上，其中維度p為數(shù)據(jù)中的獨(dú)立參數(shù)數(shù)量。更具體地講，假設(shè)數(shù)據(jù)從平滑流形M:i→Rd映射到特征空間Rd上，其中d表示數(shù)據(jù)的初始維度，且數(shù)據(jù)受到噪聲干擾，形式如下：

(5)

(6)

(7)

(8)

(9)

其中:σ表示模型參數(shù)。為了求解式(7)中的微分方程，本文采用隱式歐拉算法[13]，可得：

(10)

(11)

為了將核矩陣作為輸入進(jìn)行處理，求解如下問題：

(12)

其中:

φ表示從x到內(nèi)積為〈·,·〉H的希爾伯特空間H的核映射，對(duì)元素x,y可以通過核函數(shù)

進(jìn)行評(píng)估。

2.2 嵌入式流形去噪

(13)

下面證明基于式(12)和(13)進(jìn)行更新從理論上來說可以獲得等價(jià)結(jié)果。具體來說，有如下定理：

(14)

(15)

(16)

由于相同的原因，

(17)

證畢

定理1表明，在其PCA子空間和在核空間進(jìn)行流形去噪是等效的。本文中，已知核矩陣K后，進(jìn)行特征值分解：

(18)

2.3 面向運(yùn)動(dòng)分割的自適應(yīng)內(nèi)核

(19)

很顯然，如果：

(20)

則：

(21)

這表明：

(22)

依據(jù)上述分析，對(duì)投影P，來自同一對(duì)象的點(diǎn)被投影到同一點(diǎn)上。然后，利用如下投影作為新映射：

(23)

采用投影后，投影后的核函數(shù)可表示為：

(24)

證明

其中：

證畢

綜上所述，局部增強(qiáng)內(nèi)核的構(gòu)建方法如下。

輸入：特征軌跡數(shù)據(jù)X，約束集合c。

K=W

Sij=Kci1ci2-2Kci1cj2+Kcj1cj2,對(duì)c中的每個(gè)i,j

2.4 局部子空間內(nèi)核

(2) 局部子空間估計(jì)。對(duì)每個(gè)點(diǎn)i，利用向量間的角度或其歐氏距離作為度量來計(jì)算點(diǎn)i第k個(gè)最近鄰。然后，就局部子空間Bi對(duì)點(diǎn)及其近鄰進(jìn)行擬合。子空間Bi的維度di取決于運(yùn)動(dòng)類型(比如普通運(yùn)動(dòng)，完全平移運(yùn)動(dòng)，等等)及三維點(diǎn)的位置(比如普通位置，所有點(diǎn)均位于同一平面上，等等)，利用模型選擇方法來確定維度di。

(3) 相似度圖形構(gòu)建和譜聚類。將成對(duì)點(diǎn)i,j=1,2,…,P間的相似度矩陣計(jì)算為：

(25)

然后對(duì)相似度矩陣W執(zhí)行文獻(xiàn)[9,7]中的譜聚類操作。

2.5 自適應(yīng)流形去噪算法

輸入：軌跡數(shù)據(jù)X，聚類數(shù)量C。

步驟1：利用式(25)計(jì)算K=W。

步驟2：對(duì)W中的非對(duì)角線元素排序，選擇最前列的αC對(duì)數(shù)據(jù)作為集合c。

步驟4：

fort=1:Tdo

endfor

步驟5：通過譜聚類將數(shù)據(jù)點(diǎn)劃分為U上的C個(gè)類別：π1,π2,…,πC。

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

3.1 實(shí)驗(yàn)設(shè)置

本文利用2個(gè)數(shù)據(jù)集評(píng)估本文算法。第一個(gè)數(shù)據(jù)集是文獻(xiàn)[4]中的Hopkins 155數(shù)據(jù)集，它包括155個(gè)動(dòng)作序列(120個(gè)二運(yùn)動(dòng)序列和35個(gè)三運(yùn)動(dòng)序列)。該數(shù)據(jù)集是運(yùn)動(dòng)分割標(biāo)準(zhǔn)數(shù)據(jù)集，包含剛性和非剛性運(yùn)動(dòng)對(duì)象，但是分辨率較低，且序列中存在錯(cuò)誤匹配關(guān)鍵點(diǎn)。第2個(gè)數(shù)據(jù)集(在結(jié)果表中表示為Nonrigid(非剛性))包含3個(gè)視頻運(yùn)動(dòng)序列，用于測(cè)試流形去噪算法的性能。這些視頻序列的分辨率較高，且用手動(dòng)方式刪除被錯(cuò)誤匹配的關(guān)鍵點(diǎn)。丟棄錯(cuò)誤匹配的關(guān)鍵點(diǎn)的目的是將非剛性運(yùn)動(dòng)效應(yīng)之外的所有擾動(dòng)刪除。我們采集視頻的分辨率為(1 280 × 720)，并仔細(xì)選擇軌跡關(guān)鍵點(diǎn)，以便主要擾動(dòng)來自于非剛性運(yùn)動(dòng)而不是非匹配關(guān)鍵點(diǎn)或其他噪聲。所以，這些序列適合于測(cè)試流形去噪的性能。為了驗(yàn)證本文算法的有效性，將本文算法與目前較為典型的廣義主成分分析法(GPCA)、LSA算法(本文采用LSA的兩種配置：5個(gè)最近鄰算法和4C個(gè)最近鄰算法)[14]、隨機(jī)樣本合意算法(RANSAC)[9]、投影因式分解(PF)算法[10]和多階段學(xué)習(xí)算法(MSL)[15]進(jìn)行了比較。

3.2 結(jié)果評(píng)估

用3種標(biāo)準(zhǔn)指標(biāo)比較上述各算法的性能：聚類精度，正規(guī)化互信息(NMI)和純度。結(jié)果見表1(Avg表示平均測(cè)量值，Med表示中位數(shù))。從表1可以看到，對(duì)于精度、NMI和純度等各個(gè)指標(biāo)，本文算法的性能均優(yōu)于其他各種算法，如表1黑體所示。對(duì)非剛性運(yùn)動(dòng)序列(交通和非剛性序列)，本文算法的性能遠(yuǎn)優(yōu)于其他算法，對(duì)非剛性序列尤其如此。之所以實(shí)現(xiàn)性能提升，是因?yàn)椴捎昧肆餍稳ピ脒^程。只要對(duì)象為平滑對(duì)象(從流形角度)，則流形去噪便能取得顯著效果。LSA5和LSA4n的平均精度為74.25%和74.30%，低于本文算法(97.09%)。對(duì)非剛性類別，本文算法在其他兩個(gè)指標(biāo)上的性能幾近完美，而其他算法的表現(xiàn)遠(yuǎn)低于本文算法。

AMD的總體聚類精度為98.42%。我們還在表2中單獨(dú)總結(jié)了二運(yùn)動(dòng)和三運(yùn)動(dòng)的聚類精度(包括非剛性對(duì)象)。對(duì)二運(yùn)動(dòng)和三運(yùn)動(dòng)序列，本文算法的總體聚類精度分別為98.94%和97.92%。在各種情況下，本文算法的性能均優(yōu)于當(dāng)前其他最新運(yùn)動(dòng)分割算法。

表1 幾種方法的精度性能比較

表2 幾種方法在整個(gè)數(shù)據(jù)集上的聚類精度性能比較

圖1中給出了算法對(duì)非剛性運(yùn)動(dòng)分割的性能(交通數(shù)據(jù)集三運(yùn)動(dòng)和非剛性序列)。在該圖中，如果一個(gè)點(diǎn)為a%累積百分比(x軸)和b%(y軸)精度/NMI/純度，則表明至少有a%的數(shù)據(jù)點(diǎn)被正確分割的概率大于等于b%?？梢钥闯?，對(duì)這些非剛性序列，本文算法在各個(gè)指標(biāo)上的性能均遠(yuǎn)優(yōu)于其他算法。

GPCA, RANSAC, LSA5, LSA4n及本文算法對(duì)這3個(gè)序列的分割性能見圖2。請(qǐng)注意，該圖只給出了分組信息，即每張圖片用同一標(biāo)識(shí)(顏色)標(biāo)記的關(guān)鍵點(diǎn)被相應(yīng)算法劃分為同一類別(對(duì)象)?？梢园l(fā)現(xiàn)，本文算法的分割性能遠(yuǎn)優(yōu)于其他算法。

圖2 GPCA, RANSAC, LSA5, LSA4n及本文算法(AMD)的關(guān)鍵點(diǎn)分割結(jié)果

4 結(jié) 語

本文提出一種新的視頻運(yùn)動(dòng)分割算法，通過利用新的嵌入式流形去噪方法和局部增強(qiáng)核函數(shù)實(shí)現(xiàn)視頻運(yùn)動(dòng)分割。由于存在噪聲和離群點(diǎn)，在實(shí)際應(yīng)用中進(jìn)行運(yùn)動(dòng)分割的難度很大，導(dǎo)致傳統(tǒng)的分割算法性能有限。通過研究軌跡所在流形的平滑度，本文算法可以獲取剛性對(duì)象和非剛性對(duì)象等移動(dòng)對(duì)象的隱藏結(jié)構(gòu)。當(dāng)其他多種最新算法失效尤其是同時(shí)存在剛性和非剛性對(duì)象時(shí)，本文算法仍然具有優(yōu)異性能。

[1] 閔超波, 張俊舉, 常本康, 等. 采用邊界評(píng)價(jià)的紅外視頻運(yùn)動(dòng)目標(biāo)時(shí)空域分割方法[J]. 紅外與激光工程, 2013, 42(10): 2636-2641.

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

[3] Ochs P, Malik J, Brox T. Segmentation of moving objects by long term video analysis [J]. IEEE Transactions on Pattern Analysis and Machine Intelligence, 2014, 36(6): 1187-1200.

[4] Luo D, Huang H. Video Motion Segmentation Using New Adaptive Manifold Denoising Model[C]// 2014 IEEE Conference on Computer Vision and Pattern Recognition (CVPR),Columbus, OH, USA: IEEE Press, 2014: 65-72.

[5] Galasso F, Keuper M, Brox T,etal. Spectral graph reduction for efficient image and streaming video segmentation[C]// 2014 IEEE Conference on Computer Vision and Pattern Recognition (CVPR), Columbus, OH, USA: IEEE Press, 2014: 49-56.

[6] Pan Y, Wang Y, Liu J,etal. Improved full analytical polygon-based method using Fourier analysis of the three-dimensional affine transformation [J]. Applied Optics, 2014, 53(7): 1354-1362.

[7] 甘 超, 王 瑩, 王向陽. 多特征穩(wěn)健主成分分析的視頻運(yùn)動(dòng)目標(biāo)分割[J]. 中國圖象圖形學(xué)報(bào), 2013, 18(9): 1124-1132.

[8] 魯梅, 盧 忱, 范九倫. 一種有效的基于時(shí)空信息的視頻運(yùn)動(dòng)對(duì)象分割算法[J]. 計(jì)算機(jī)應(yīng)用研究, 2013, 30(1): 303-306.

[9] 馬志強(qiáng), 張曉燕, 朱子健, 等. 一種動(dòng)態(tài)場(chǎng)景下運(yùn)動(dòng)對(duì)象分割新算法[J]. 計(jì)算機(jī)工程與科學(xué), 2012, 34(4): 43-46.

[10] Saha B, Pham D S, Phung D,etal. Clustering patient medical records via sparse subspace Representation[C] //Advances in Knowledge Discovery and Data Mining. Springer Berlin Heidelberg, 2013: 123-134.

[11] Hu H, Lin Z, Feng J,etal. Smooth representation clustering[C]// 2014 IEEE Conference on Computer Vision and Pattern Recognition (CVPR), Columbus, OH, USA: IEEE, 2014: 3834-3841.

[12] Wang B, Tu Z. Sparse subspace denoising for image manifolds[C]// 2013 IEEE Conference on Computer Vision and Pattern Recognition (CVPR), Portland, OR, USA: IEEE Press, 2013: 468-475.

[13] Alfonsi A. Strong order one convergence of a drift implicit Euler scheme: Application to the CIR process [J]. Statistics & Probability Letters, 2013, 83(2): 602-607.

[14] Yan J, Pollefeys M. A general framework for motion segmentation: Independent, articulated, rigid, non-rigid, degenerate and non-degenerate[C]// 12thEuropean Conference on Computer Vision(ECCV), Firenze, Italy: IEEE Press, 2012: 94-106.

[15] Sugaya Y， Kanatani K. Geometric structure of degeneracy for multi-body motion segmentation[J]. In Statistical Methods in Video Processing, 2014, 11(23):13-25.

A Research on Video Motion Segmentation Algorithm Based on Adaptive Manifold Denoising

YANGZhang-qiong

(Yibin Vocational and Technical College, Yibin 644000, China)

Aiming at the disadvantages of the existing motion segmentation algorithms, a novel motion segmentation approach for both rigid and non-rigid objects is proposed by using adaptive manifold denoising. We first introduce an adaptive kernel space in which two feature trajectories are mapped into the same point if they belong to the same rigid object. After that, we employ an embedded manifold denoising approach with the adaptive kernel to segment the motion of rigid and non-rigid objects. We also show that performing manifold denoising on the kernel space is equivalent to denoising on its range space, which theoretically justifies the embedded manifold denoising on the adaptive kernel space. Experimental results indicate that our algorithm, named Adaptive Manifold Denoising (AMD), is suitable to both rigid and non-rigid motion segmentations. Our algorithm works well in many cases where several state-of-the-art algorithms fail.

video motion segmentation; computer vision; adaptive manifold denoising; kernel space

2015-12-12

楊章瓊(1979-)，女，四川宜賓人，碩士，講師，主要研究方向：圖像處理、多媒體技術(shù)。

E-mail: 279J135162@qq.com

TP 391

A

1006-7167(2016)09-0041-06