基于稀疏優(yōu)化算法的視頻運動分割

馮思桐+武堅

摘要：該文提出一種基于子空間模型分割視頻中多個運動目標的方法。實際視頻序列中提取的特征點是復(fù)雜的高維數(shù)據(jù)，本文結(jié)合現(xiàn)有文獻，首次提出使用稀疏主成分分析（SPCA）算法降維，將原始高維數(shù)據(jù)投影到一個具有稀疏表示的低維空間，在此基礎(chǔ)上，提出基于特征角的“稀疏近鄰”估計方法得到相似度矩陣，從而獲得最終的子空間聚類結(jié)果。將該文提出的方法應(yīng)用到視頻序列中，并與現(xiàn)有的運動分割的算法進行比較。實驗結(jié)果表明，本文提出的方法可以準確對視頻中不同運動的物體進行分類，并在精度和運算速度方面與其他算法相比都有很大的提高。

關(guān)鍵詞：視頻分割；稀疏優(yōu)化；子空間模型

中圖分類號：TP302 文獻標識碼：A 文章編號：1009-3044（2016）27-0139-05

1 介紹

視頻的運動分割，旨在從視頻序列中分解出多個連續(xù)移動的不同物體。將不同運動物體的信息從視頻中提取出來之后，可以做很多后續(xù)的研究，如異常行為分析或者運動物體的追蹤。近幾年，基于特征點軌跡聚類的視頻運動分割問題是主要的研究方向，首先對提取的實際視頻序列進行預(yù)處理獲得特征點軌跡，如KLT[1]，SIFT[2]或者SURF[3]等特征點提取算法，基于不同的運動目標對特征點軌跡集合進行聚類。但是長視頻序列中提取和跟蹤的特征點集合往往是高維復(fù)雜的大數(shù)據(jù)，需要尋求一種高精度并能快速對高維復(fù)雜數(shù)據(jù)進行分類的方法?；谧涌臻g模型下的運動分割，是現(xiàn)如今被普遍研究的分類方法。子空間模型下分類的基本思想是，從視頻序列中提取到的每一組特征點軌跡都認為其點集合共同構(gòu)建了一個子空間，那么不同特征點集合的聚類問題，即轉(zhuǎn)化為對一組子空間集合進行聚類的問題。

本文基于LSA聚類算法[7]以及稀疏子空間聚類算法（SSC）[6]的思想，提出一種基于稀疏優(yōu)化對子空間進行聚類的新方法。實驗結(jié)果表示，本文所提出的方法，可以有效且快速地分類實際視頻中的不同運動目標。

2 基于子空間模型下的運動分割

2.1 子空間聚類模型

對特征點集合組成的高維數(shù)據(jù)聚類，基于子空間的模型，首先需要獲得高維數(shù)據(jù)的低維表示，而這個低維表示能夠保持原大數(shù)據(jù)矩陣的本質(zhì)特征。假設(shè)，將原高維數(shù)據(jù)的低維投影看作一個變換后的“全局子空間”，而全局子空間是由不同的更低維度的“本地子空間”相互交疊構(gòu)成，如圖1，三種數(shù)據(jù)點集合構(gòu)成三種子空間S1，S2，S3，集合S={ S1，S2，S3}稱作全局子空間，S1，S2，S3相對的稱作本地子空間。本文中基于子空間模型進行分類的基本思想就是從全局子空間中找出不同的本地子空間，屬于同一本地子空間的數(shù)據(jù)應(yīng)當被劃分到同一類中，即劃分為屬于同一種運動目標。

4 實驗結(jié)果與分析

本文實驗數(shù)據(jù)選自標準的視頻數(shù)據(jù)庫Hopkins 155數(shù)據(jù)集[13]。并將本文提出的優(yōu)化算法與現(xiàn)今其他優(yōu)秀的運動分割算法進行比較，在分割的過程中，假設(shè)所有視頻中運動目標的個數(shù)已知。

圖6，7，8是采用本文所提出算法進行聚類的結(jié)果，不同顏色代表不同的運動目標。圖6中包含3中運動，紅色點代表背景，藍色和綠色代表兩種汽車的運動，圖7中包含2種運動，人的手臂以及手上拿的物體分別用紅色和綠色進行區(qū)分，圖8代表了3種物體的運動，紅色點代表背景，由圖7可知，對于特征點多且復(fù)雜的難以區(qū)分運動模式，我們所提出的算法可以有效的對不同的運動目標進行區(qū)分。為了進一步表明本文所提出算法的優(yōu)勢，我們將從錯誤率和運算時間與SSC [6]， LSA [7]， RANSAC [4]， GPCA [5]， LLMC [14]算法進行對比。

從表1、2、3、4可以得出，我們所提出的算法具有比較好的準確度，雖然相比SSC算法來說準確度略低，但是我們的優(yōu)化算法與SSC相比加快了運算的速度。

5 總結(jié)

本文提出了一種基于子空間的運動分割優(yōu)化方法，可以對實際視頻序列中不同的運動物體進行有效分類。首先通過SPCA算法[15]將高維數(shù)據(jù)投影在一個低維的空間上，并且具有少數(shù)的非零元素；基于SMCE [9]的思想，對投影后低維空間中不同的子空間進行估計，尋找在低維空間中每一個數(shù)據(jù)點的稀疏近鄰（隸屬于同一子空間），將投影后分布于低維空間中的不同子空間分割出來，這種方式相比較LSA算法來說，改善了過度估計和不同子空間相互交叉的問題，大大提高了準確率。與SSC算法相比，運算時間得到提升。在未來的研究中，將對長視頻序列中運動目標分割的研究作為主要方向，并側(cè)重數(shù)據(jù)缺失或不完整軌跡等問題，進一步提升算法的準確性和實用性。

參考文獻：

[1] Tomasi C， Kanade T. Detection and tracking of point features. School of Computer Science， Carnegie Mellon Univ. Pittsburgh，1991.

[2] Zhou H， Yuan Y， Shi C. Object tracking using sift features and mean shift.Computer vision and image understanding， （2009，113：345，352.

[3] Bay H， Ess A， Tuytelaars T， Van Gool L.Speeded-up robust features （surf）. Computer vision and image understanding， 2008，110：346，359.

[4] Fischler M A， Bolles R C. Random sample consensus： a paradigm for model fitting with applications to image analysis and automated cartography. Communications of the ACM 1981：24：381，395.

[5] Vidal R， Ma Y， Sastry S.Generalized principal component analysis （gpca）. Pattern Analysis and Machine Intelligence， IEEE Transactions，2005，27：1945，1959.

[6] Elhamifar E， Vidal R. Sparse subspace clustering. In： Computer Vision and Pattern Recognition， 2009. CVPR 2009. IEEE Conference on IEEE，2009：2790，2797.

[7] Yan J， PollefeysM.A general framework for motion segmentation： Independent，articulated， rigid， non-rigid， degenerate and non-degenerate. In： Computer Vision ECCV 2006. Springer （2006，94：106.

[8] Hartley R， Zisserman A.Multiple View Geometry in Computer Vision. 2 edn. Cambridge University Press， New York， NY， USA.2003.

[9] Elhamifar E， Vidal R. Sparse manifold clustering and embedding. In： NIPS，2011：55，63.

[10] Journ_ee ， Nesterov ， Richt_arik ， Sepulchre . Generalized power method for sparse principal component analysis. The Journal of Machine Learning Research，2010， 11：517，553.

[11] dAspremont A， El Ghaoui L， Jordan M I， Lanckriet G R.A direct formulation for sparse pca using semidefinite programming. In： NIPS. Volume，2004， 16.：41，48.

[12] Tibshirani R.Regression shrinkage and selection via the lasso. Journal of the Royal Statistical Society. Series B （Methodological，1996：267，288

[13] Tron R， Vidal R.A benchmark for the comparison of 3-d motion segmentation algorithms. In： Computer Vision and Pattern Recognition， 2007. CVPR07. IEEE Conference on， IEEE，2007：1，8.

[14] Goh A， Vidal R.Segmenting motions of di_erent types by unsupervised manifold clustering. In： Computer Vision and Pattern Recognition， 2007. CVPR07. IEEE Conference on， IEEE，2007：1，6.

[15] Zou H， Hastie T， Tibshirani R. Sparse principal component analysis. Journal of computational and graphical statistics，2006，15：265，286.