楊章瓊

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

?

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

楊章瓊

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

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

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

0 引 言

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

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

1 多人體視頻運動分割

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

1.1 剛性人體運動的運動子空間

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

(1)

(2)

1.2 多對象剛性人體運動的運動子空間

(3)

(4)

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

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

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

2.1 流形去噪

文獻(xiàn)[12]中的流形去噪模型假設(shè)數(shù)據(jù)點位于帶有噪聲的未知p維流形M上，其中維度p為數(shù)據(jù)中的獨立參數(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的核映射，對元素x,y可以通過核函數(shù)

進(jìn)行評估。

2.2 嵌入式流形去噪

(13)

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

(14)

(15)

(16)

由于相同的原因，

(17)

證畢

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

(18)

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

(19)

很顯然，如果：

(20)

則：

(21)

這表明：

(22)

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

(23)

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

(24)

證明

其中：

證畢

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

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

K=W

Sij=Kci1ci2-2Kci1cj2+Kcj1cj2,對c中的每個i,j

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

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

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

(25)

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

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

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

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

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

步驟4：

fort=1:Tdo

endfor

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

3 仿真實驗

3.1 實驗設(shè)置

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

3.2 結(jié)果評估

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

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

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

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

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

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

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

4 結(jié) 語

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

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

[2] 馮 林, 劉勝藍(lán), 王 靜, 等. 人體運動分割算法: 序列局部彎曲的流形學(xué)習(xí)[J]. 計算機(jī)輔助設(shè)計與圖形學(xué)學(xué)報, 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)健主成分分析的視頻運動目標(biāo)分割[J]. 中國圖象圖形學(xué)報, 2013, 18(9): 1124-1132.

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

[9] 馬志強(qiáng), 張曉燕, 朱子健, 等. 一種動態(tài)場景下運動對象分割新算法[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