基于自適應流形去噪的視頻運動分割算法

楊章瓊

(宜賓職業技術學院， 四川 宜賓 644000)

?

基于自適應流形去噪的視頻運動分割算法

楊章瓊

(宜賓職業技術學院， 四川 宜賓 644000)

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

視頻運動分割； 計算機視覺； 自適應流形去噪； 核空間

0 引 言

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

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

1 多人體視頻運動分割

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

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

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

(1)

(2)

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

(3)

(4)

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

2 自適應流形去噪

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

2.1 流形去噪

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

(5)

(6)

(7)

(8)

(9)

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

(10)

(11)

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

(12)

其中:

φ表示從x到內積為〈·,·〉H的希爾伯特空間H的核映射，對元素x,y可以通過核函數

進行評估。

2.2 嵌入式流形去噪

(13)

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

(14)

(15)

(16)

由于相同的原因，

(17)

證畢

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

(18)

2.3 面向運動分割的自適應內核

(19)

很顯然，如果：

(20)

則：

(21)

這表明：

(22)

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

(23)

采用投影后，投影后的核函數可表示為：

(24)

證明

其中：

證畢

綜上所述，局部增強內核的構建方法如下。

輸入：特征軌跡數據X，約束集合c。

K=W

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

2.4 局部子空間內核

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

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

(25)

然后對相似度矩陣W執行文獻[9,7]中的譜聚類操作。

2.5 自適應流形去噪算法

輸入：軌跡數據X，聚類數量C。

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

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

步驟4：

fort=1:Tdo

endfor

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

3 仿真實驗

3.1 實驗設置

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

3.2 結果評估

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

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

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

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

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

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

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

4 結 語

本文提出一種新的視頻運動分割算法，通過利用新的嵌入式流形去噪方法和局部增強核函數實現視頻運動分割。由于存在噪聲和離群點，在實際應用中進行運動分割的難度很大，導致傳統的分割算法性能有限。通過研究軌跡所在流形的平滑度，本文算法可以獲取剛性對象和非剛性對象等移動對象的隱藏結構。當其他多種最新算法失效尤其是同時存在剛性和非剛性對象時，本文算法仍然具有優異性能。

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

[2] 馮 林, 劉勝藍, 王 靜, 等. 人體運動分割算法: 序列局部彎曲的流形學習[J]. 計算機輔助設計與圖形學學報, 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] 甘 超, 王 瑩, 王向陽. 多特征穩健主成分分析的視頻運動目標分割[J]. 中國圖象圖形學報, 2013, 18(9): 1124-1132.

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

[9] 馬志強, 張曉燕, 朱子健, 等. 一種動態場景下運動對象分割新算法[J]. 計算機工程與科學, 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-)，女，四川宜賓人，碩士，講師，主要研究方向：圖像處理、多媒體技術。

E-mail: 279J135162@qq.com

TP 391

A

1006-7167(2016)09-0041-06