一種新的魯棒主成分分析方法及其應用

陳甲英，趙建偉，曹飛龍

(中國計量學院 理學院，浙江 杭州 310018)

?

一種新的魯棒主成分分析方法及其應用

陳甲英，趙建偉，曹飛龍

(中國計量學院 理學院，浙江 杭州 310018)

【摘要】背景建模在視頻運動分析中具有重要作用.視頻序列背景圖像通常具有低秩性，為了更好地刻畫該特性，精確提取視頻背景，提出了一種基于截斷核范數(shù)的魯棒主成分分析模型.同時設(shè)計了一種兩步迭代算法來求解該模型，最后將該算法應用于視頻背景建模.不同視頻數(shù)據(jù)庫實驗表明，該算法對于求解背景建模問題是有效的.

【關(guān)鍵詞】矩陣恢復；截斷核范數(shù)；魯棒主成分分析；背景建模

如何較準確地從視頻流中提取運動目標是計算機視覺研究領(lǐng)域中的一個重要的方向.同時，也是行為理解和運動分析的重要前提.在實際應用中，常見的運動目標檢測算法主要有三類：光流法[1]，相鄰幀間圖像差分法[2]以及背景圖像差分法[3].相比于前兩種方法，背景圖像差分法更加精確、速度更快并且實現(xiàn)比較簡單，是目標檢測中一種常用的方法.其基本原理如下：首先估計背景圖像，然后利用背景圖像與當前幀圖像的差進行目標檢測.因此，背景圖像建模是背景圖像差分法進行目標檢測的關(guān)鍵.

根據(jù)攝像機拍攝方法的不同，視頻可以被分為攝像機固定拍攝的定視角視頻和攝像機運動拍攝的變視角視頻兩類，本文主要針對前者進行背景建模問題研究.國內(nèi)外對于這一問題已有很多學者進行了研究，提出了一些不同的建模方法.如：Wren等人[4]提出的單高斯分布模型，在單高斯模型的基礎(chǔ)之上Friedman和Russell[5]提出了混合高斯背景模型.而混合高斯分布模型的缺點是參數(shù)估計較慢，模型個數(shù)難以確定.為了從根本上解決混合高斯背景模型中參數(shù)估計運算量過大的問題，編碼本(Codebook)背景建模方法[6-7]及非參數(shù)背景建模[8]被提出.從本質(zhì)上看，由于這些方法全部是建立在對像素點的分析上，算法雖然實現(xiàn)簡便，但是忽視了像素點間的聯(lián)系和物體的整體屬性，在一些視頻中，僅通過像素值出現(xiàn)的頻率和穩(wěn)定性并不能準確區(qū)分前景和背景.例如，體積較大的單色物體在運動過程中，其內(nèi)部經(jīng)常會判定為穩(wěn)定的背景.近年來，隨著壓縮感知理論研究的深入，稀疏表示成為一種更加有效的數(shù)據(jù)表示方式.然而，現(xiàn)實世界中很多數(shù)據(jù)是以矩陣形式存儲的，因此，將向量樣例的稀疏表示推廣到矩陣的低秩情形的低秩矩陣恢復理論應運而生.考慮到視頻序列各幀之間的相關(guān)性，Candès等人[9]用矩陣恢復方法來提取攝像機固定的情況下的視頻圖像的背景，并且得到了理想的提取效果.已有的矩陣恢復方法雖然考慮了每幀圖像像素之間的聯(lián)系，但是核范數(shù)可能不是刻畫各幀圖像之間的低秩性的最好方法.因此，尋找一種更好的矩陣恢復方法并用其進行背景提取無疑是具有重要的理論和現(xiàn)實意義.

本文結(jié)構(gòu)如下：第一節(jié)簡單介紹基于核范數(shù)的魯棒主成分分析方法；第二節(jié)提出一種新的基于截斷核范數(shù)的魯棒主成分分析算法并給出了相應的求解方法；第三節(jié)是實驗部分，包括人工數(shù)據(jù)有效性實驗和背景提取兩個實驗；第四節(jié)是結(jié)論.

1基于核范數(shù)的魯棒主成分分析方法

在固定攝像機位置的情況下，可得到一段時間內(nèi)的一個視頻序列.由于攝像機是靜止的，所以只要沒有運動物體經(jīng)過，視頻背景是固定的.也就是說，在一段視頻圖像中，可將運動物體看作背景部分的噪聲項，除去噪聲項，各幀圖像的背景部分是線性相關(guān)的，即一段視頻中，所有背景圖像構(gòu)成的矩陣是低秩的，運動的前景可以看作是稀疏的噪聲.

考慮一個視頻序列中的N幀圖像，分別記為{I1,I2,…,IN}，其中Ii(i=1,2,…,N)是一個m×n的圖像矩陣.將每個圖像矩陣Ii拉成列向量，按照原來視頻序列中各幀圖像的順序重新生成一個mn×N的矩陣D.對于矩陣D，可以分解成運動目標E和固定背景Z的和，即D=Z+E.根據(jù)前面的分析，各幀圖像的背景拉成的向量是線性相關(guān)的，即矩陣Z具有低秩性，而運動目標在圖像中可以看作噪聲，具有一定的稀疏性.因此，背景建模問題事實上就是求解以下低秩矩陣恢復問題：

s.tD=Z+E.

(1)

然而，由于秩函數(shù)以及零范數(shù)的非凸性，該模型是一個NP難問題[10-11].Fazel[12]首次在控制系統(tǒng)中用核范數(shù)作為秩函數(shù)的近似，之后大量理論研究說明：在滿足強不相干性條件[9,13]和約束等距條件[14]的前提下，核范數(shù)可以作為秩函數(shù)的一種凸替代；同時，l1范數(shù)可以作為l0范數(shù)的凸替代[10,13].在文獻[9]和[14]中，Candès等人提出了一種主成分追蹤方法:

s.tD=Z+E.

(2)

我們將這種基于核范數(shù)的背景提取方法又稱為基于核范數(shù)的魯棒主成分分析方法(Robust Principal Component Analysis Method with Nuclear Norm，RPCA-NN).此外，一些研究者還考慮了有噪聲存在的情況下的低秩矩陣恢復問題[15-16]，并給出了相關(guān)算法.

事實上，模型(2)可以用迭代閾值方法求解(Iterative Threshold，IT)[15,17]來求解，但是，IT迭代步長不好選擇，而且需要迭代很多次才能收斂.為了克服IT收斂速度慢的局限性，Lin等人[18]提出了兩種新的求解該問題的方法，分別是加速近端梯度算法(Accelerated Proximal Gradient，APG)和對偶算法(Dual Method，DM).此外，文獻[19]提出了增廣拉格朗日算法(Augmented Lagrange Multiplier，ALM)和非精確增廣拉格朗日算法(Inexact Augmented Lagrange Multiplier, IALM)來求解(2)式，使得其迭代解能夠收斂到該優(yōu)化問題的精確解，并且耗時相對較少.

2基于截斷核范數(shù)的魯棒主成分分析方法

由于在提取背景時，人們期望背景部分是低秩的，Hu等人指出核范數(shù)不是秩函數(shù)的最佳近似，因為原始的秩函數(shù)只需要考慮非零奇異值的個數(shù)，且每個非零奇異值對秩函數(shù)有著同等的貢獻，而核范數(shù)是所有非零奇異值的和，但不同的非零奇異值對核范數(shù)的影響不同，大的奇異值起了主要的作用.對于一個矩陣D∈Rm×n，它的秩在很大程度上是取決于最小的min(m,n)-r個奇異值的非零元素的個數(shù)，前r個奇異值在估計秩時提供的信息是非常有限的，而核范數(shù)中起決定作用的恰恰是前面的較大的奇異值.基于此Hu等人[20]提出了一種更精確的低秩性的刻畫方式，即截斷核范數(shù)正則化方法(Truncated Nuclear Norm，TNN).

首先，介紹截斷核范數(shù)的概念：

其中σi(D)是D的第i個奇異值，r為整數(shù)，且r小于矩陣的秩rank(D).

受Hu等人研究的啟發(fā)，本文提出了一種基于截斷核范數(shù)的魯棒主成分分析方法(Robust Principal Component Analysis Method with Nuclear Norm，RPCA-TNN):

s.tD=Z+E.

(3)

然而，由于截斷核范數(shù)是非凸的，因此模型(3)是一個NP-Hard問題[10-11]，無法用凸優(yōu)化的方法來求解該模型.然而，截斷核范數(shù)具有以下性質(zhì)[20]:

引理1[20]對于任意的矩陣Z∈Rm×n，任意的非負整數(shù)r(r≤min(m,n))，存在秩為r的矩陣A∈Rr×m和B∈Rr×n，且有AAΤ=I，BBΤ=I，有如下的結(jié)論：

(4)

其中σi(Z)是Z的第i個奇異值.

該引理的證明已在文獻[20]中給出.

根據(jù)引理1和奇異值分解的知識，我們可以得到下面的結(jié)論：

(5)

因此，在A和B確定的情況下，根據(jù)(5)式，上述優(yōu)化問題(3)可以轉(zhuǎn)化為求解下面的優(yōu)化問題：

s.tD=Z+E.

(6)

(7)

其中Y是拉格朗日乘子，μ>0是懲罰參數(shù)，<.,.>為矩陣內(nèi)積.

通過交替方向法求解下面的無約束優(yōu)化問題：

即固定其中兩個變量，求解剩下的一個變量：

(8)

為了求解上面的問題，給出以下定義和引理：

定義2[21-22]矩陣D∈Rm×n的奇異值分解為：

D=USVT,S=diag({σi}1≤i≤min(m,n))，定義奇異值閾值算子：

Θτ(D)=UΘτ(Σ)VT,

其中σi是D的第i個奇異值.

引理2[21-22]對于τ>0，Y∈Rm×n，下面的結(jié)論成立：

引理3[9,23]對于τ>0，Y∈Rm×n設(shè)Sτ:R→R是軟閾值算子，則它是下面優(yōu)化問題的解：

且軟閾值算子

其中Y=(yij).

我們首先固定E和Y，更新Z,即求解下面的優(yōu)化模型：

從而根據(jù)引理2和定義2，可以得到Z的解為下面的形式：

(9)

然后，我們固定Z和Y，更新E：

再根據(jù)引理3得到E的迭代解如下：

(10)

最后，計算拉格朗日乘子Y和懲罰參數(shù)μ：

Yk+1=Yk+μk(D-Zk+1-Ek+1),

(11)

μk+1=min(ρμk,μmax),

(12)

其中ρ>1是一個常數(shù).

應用兩步迭代策略交替迭代直到算法收斂.算法總結(jié)如下.

兩步迭代算法：

步驟一，初始化

1)給定初值Z1=D；

2)給定第二步迭代收斂誤差eps；

3)給定終止誤差ε.

步驟二，計算Al和Bl

計算Zl的奇異值分解

其中，

Ul=(u1,u2,…,um)∈Rm×m,

Vl=(v1,v2,…,vn)∈Rn×n，

從而，Al=(u1,u2,…,ur)Τ，

Bl=(v1,v2,…,vr)Τ.

步驟三，用交替方向法求解優(yōu)化子問題(6)

1)用(9)式更新變量Z；

2)用(10)式更新變量E；

3)用(11)式更新拉格朗日乘子Y.

4)用(12)式更新懲罰參數(shù)μ.

直到算法收斂,即

步驟四，轉(zhuǎn)到步驟二重復迭代循環(huán)，更新變量，直到外部算法收斂，即

3實驗結(jié)果及分析

3.1人工數(shù)據(jù)實驗

根據(jù)文獻[24]，人工數(shù)據(jù)矩陣按如下方式生成：首先生成一個秩為r的低秩方陣Z0∈Rm×n和一個相同大小的稀疏矩陣E0，則待恢復的矩陣D0可以表示為D0=Z0+E0.

為說明提出的基于截斷核范數(shù)的魯棒主成分分析方法要優(yōu)于基于核范數(shù)的魯棒主成分分析方法,本文用RPCA-TNN和RPCA-NN分別提取人工數(shù)據(jù)D0的低秩部分Z，并用Z的秩、低秩誤差以及總體誤差來刻畫兩種方法的有效性，其中低秩誤差和總體誤差的定義形式如下[24]：

本文用到的矩陣大小分別是200、600、1 000、1 300的人工數(shù)據(jù)方陣來做實驗，從表1可以發(fā)現(xiàn)：不論是RPCA-TNN,還是RPCA-NN都能夠很好地提取人工數(shù)據(jù)矩陣的低秩部分.但是，RPCA-TNN不論是總誤差還是低秩誤差都要比

表1　RPCA-TNN和RPCA-NN在人工數(shù)據(jù)上的實驗結(jié)果

圖1　利用RPCA-TNN和RPCA-NN來提取背景并檢測單一前景Figure 1　Background subtraction and simple foreground object detection by RPCA-TNN and RPCA_NN

RPCA-NN小至少三個數(shù)量級.這說明較之RPCA-NN，RPCA-TNN能夠更好地處理低秩提取相關(guān)的問題.此外，從表1看出，RPCA-TNN耗時更多一些，但是，這是可以理解的：奇異值分解是比較耗時的運算.

3.2背景提取與前景檢測

本小節(jié)中，我們用七個由靜態(tài)攝像機拍攝的監(jiān)控視頻數(shù)據(jù)做實驗，即：Labby dataset，Escalator dataset，F(xiàn)ountain dataset，Campus dataset，Water Surface dataset，Hall dataset和Bootstrap dataset[25].分別用RPCA-TNN和RPCA-NN提取以上視頻數(shù)據(jù)的背景，并且將提取的結(jié)果進行直觀的比較，實驗結(jié)果顯示在圖1和圖2中.由于實驗條件的限制，在每個視頻數(shù)據(jù)集上，我們分別取35幀視頻圖像做實驗.由于所有的視頻圖像都是彩色的，首先需要將視頻圖像轉(zhuǎn)成灰度圖像，然后將每一幀灰度圖像拉成一個長列向量，最后將這35個列向量并成矩陣D.

圖2　利用RPCA-TNN和RPCA-NN來提取背景并檢測復雜前景Figure 2　Background subtraction and complex foreground object detection by RPCA-TNN and RPCA-NN

圖1和圖2呈現(xiàn)了用RPCA-TNN和RPCA-NN在每個視頻數(shù)據(jù)集上的背景提取結(jié)果.其中前三列是用本文提出的方法得到的結(jié)果，第一列是含有噪聲或運動物體的視頻圖像，第二列是提取背景后剩余的運動物體或噪聲，第三列是利用本文提出的方法提取的背景部分.同樣的，后三列是用RPCA-NN得到的提取結(jié)果.

從圖1直觀觀察，我們發(fā)現(xiàn)當視頻幀數(shù)比較少，視頻場景中的運動物體比較單一的情況下，RPCA-TNN和RPCA-NN都能夠提取出視頻的背景圖像.但是，與RPCA-TNN相比，我們很容易發(fā)現(xiàn)：用RPCA-NN提取出的運動前景物體中還包含了很少的一部分背景，也就是說提取的背景圖像有損失.所以，在處理背景建模問題時，本文提出的RPCA-TNN方法的提取效果要優(yōu)于一般的RPCA-NN.

圖2中的視頻場景比較復雜，含有多運動物體.我們發(fā)現(xiàn)當視頻幀數(shù)很少時，RPCA-NN已經(jīng)不能夠提取出視頻的背景模型了，而本文提出的RPAC-TNN仍然能夠比較精確的提取出視頻背景.

4結(jié)語

本文提出了一種基于截斷核范數(shù)的魯棒主成分分析算法，使其能夠更好地恢復低秩稀疏矩陣.由于截斷核范數(shù)的非凸性，我們設(shè)計了兩步迭代算法，并將該算法應用于背景建模中.實驗結(jié)果表明，本文提出的方法相比一般的基于核范數(shù)的方法能更好地處理背景建模問題.

【參考文獻】

[1]WEI hiqiang, JI Xiaopeng, WANG Peng. Real-time moving object detection for video monitoring systems [J]. Journal of Systems Engineering and Electronics,2006,17(4):731-736.

[2]LIPTON A J, FUJIYOSHI H, PATIL R S. Moving target classification and tracking from real-time video [C]// Proceedings of 4th IEEE Workshop on Applications of Computer Vision. New Jersey: IEEE, 1998: 8-14.

[3]CHEN Baisheng, LEI Yunqi, LI Wangwei. A novel background model for real-time vehicle detection [C]// Proceedings of 7th International Conference on Signal Processing. Beijing: IEEE, 2004, 2: 1276-1279.

[4]WREN C R, AZARBAYEJAIN A, DARRELL T. Pfinder: real-time tracking of the human body [J]. IEEE Transactions on Pattern Analysis and Machine Intelligence, 1997, 19(7): 780-785.

[5]FRIEDMAN N, RUSSELL S. Image segmentation in video sequences: a probabilistic approach [C]// Proceedings of 13th Conference on Uncertainty in Artificial Intelligence (UAI). San Francisco: Morgan Kaufmann Publishers Inc,1997：175-181.

[6]KIM K, CHALIDABHONGSE T H, HARWOOD D, et al. Real-time foreground-background segmentation using Codebook Model [J]. Real-Time Imaging, 2005, 11(3): 172-185.

[7]ILYAS A, SCUTURICI M, MIGUET S. Real time foreground-background segmentation using a modified Codebook Model [C]// Proceedings of 6th IEEE International Conference on Advanced Video and Signal Based Surveillance. Genova: IEEE, 2009: 454-459.

[8]ELGAMMAL A, DURAISWAMI R, HARWOOD D, et al. Background and foreground modeling using nonparametric kernel density estimation for visual surveillance [J]. Proceedings of the IEEE, 2002, 90(7): 1151-1163.

[10]NATARAJAN B K. Sparse approximate solutions to linear systems [J]. SIAM Journal on Computing, 1995, 24(2): 227-234.

[11]RECHT B, FAZEL M, PARRILO P A. Guaranteed minimum-rank solutions of linear matrix equations via nuclear norm minimization [J]. SIAM Review, 2010, 52(3): 471-501.

[12]FAZEL M. Matrix rank minimization with applications [D]. Stanford: Stanford University, 2002.

[15]GANESH A, WRIGHT J, LI Xiaodong, et al. Dense error correction for low-rank matrices via principal component pursuit [C]// Proceedings of 2010 IEEE International Symposium on Information Theory (ISIT). Austin: IEEE, 2010: 1513-1517.

[16]ZHOU Zihan, LI Xiaodong, WRIGHT J, et al. Stable principal component pursuit [C]// Proceedings of 2010 IEEE International Symposium on Information Theory (ISIT). Austin: IEEE, 2010: 1518-1522.

[17]WRIGHT J, GANESH A, RAO S, et al. Robust principal component analysis: exact recovery of corrupted low-rank matrices via convex optimization [C]// Advances in Neural Information Processing Systems. Granada: NIPS, 2009: 2080-2088.

[18]LIN Zhouchen, GANESH A, WRIGHT J, et al. Fast convex optimization algorithms for exact recovery of a corrupted low-rank matrix [J]. International Workshop on Computational Advances in Multi-Sensor Adaptive Processing (CAMSAP), 2009, 61: 213-216.

[19]LIN Zouchen, LIU Risheng, SU Zhixun. Linearized alternating direction method with adaptive penalty for low-rank representation [C]// Advances in Neural Information Processing Systems. Granada: NIPS, 2011: 612-620.

[20]HU Yao, ZHANG Debing, YE Jieping, et al. Fast and accurate matrix completion via truncated nuclear norm regularization [J]. IEEE Transactions on Pattern Analysis and Machine Intelligence,2013,35(9):2117-2130.

[22]LIU Yuanyuan, JIAO Licheng, SHANG Fanhua, et al. An efficient matrix bi-factorization alternative optimization method for low-rank matrix recovery and completion [J]. Neural Networks, 2013, 48: 8-18.

[23]COMBETTES P L, WAJS V R. Signal recovery by proximal forward-backward splitting [J]. Multiscale Modeling & Simulation, 2005, 4(4): 1168-1200.

[24]YUAN Xxiaoming, YANG Junfeng. Sparse and low-rank matrix decomposition via alternating direction methods [J]. Operations Research & Management Science, 2013, 9(1): 167-180.

[25]Statistical modeling of complex background for foregrou-nd object detection [DB]. http://perception.i2r.a-star.edu.sg/bk_model/bk_index.html[2015-09-28].

A novel robust principal component analysis method and its applications

CHEN Jiaying, ZHAO Jianwei, CAO Feilong

(College of Sciences, China Jiliang University, Hangzhou 310018, China)

Abstract:Background modeling is critical in the video motion analysis. To describe the low rank property of a set of video sequences and to improve the accuracy of background modeling, a novel robust principal component analysis with the truncated nuclear norm method was proposed. A model with a two step iterative strategy was used to solve the problem. Finally, the algorithm was applied in the video background modeling. A series of experiments on different video databases demonstrated that the algorithm was effective for the solving of the background modeling problem.

Key words:matrix recovery; truncated nuclear norm; robust principal component analysis; background modeling

【文章編號】1004-1540(2015)01-0113-08

DOI:10.3969/j.issn.1004-1540.2016.01.021

【收稿日期】2015-10-06《中國計量學院學報》網(wǎng)址：http://zgjl.cbpt.cnki.net

【基金項目】國家自然科學基金資助項目(No.61571410,61272023).

【作者簡介】陳甲英(1990- )，女，甘肅省金昌人，碩士研究生，主要研究方向為矩陣恢復.E-mail:zccyman@163.com

【中圖分類號】TP399

【文獻標志碼】A

通信聯(lián)系人：曹飛龍,男，教授.E-mail:flcao@cjlu.edu.cn