陳甲英，趙建偉，曹飛龍

(中國計(jì)量學(xué)院 理學(xué)院，浙江 杭州 310018)

?

一種新的魯棒主成分分析方法及其應(yīng)用

陳甲英，趙建偉，曹飛龍

(中國計(jì)量學(xué)院 理學(xué)院，浙江 杭州 310018)

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

【關(guān)鍵詞】矩陣恢復(fù)；截?cái)嗪朔稊?shù)；魯棒主成分分析；背景建模

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

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

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

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

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

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

s.tD=Z+E.

(1)

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

s.tD=Z+E.

(2)

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

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

2基于截?cái)嗪朔稊?shù)的魯棒主成分分析方法

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

首先，介紹截?cái)嗪朔稊?shù)的概念：

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

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

s.tD=Z+E.

(3)

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

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

(4)

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

該引理的證明已在文獻(xiàn)[20]中給出.

根據(jù)引理1和奇異值分解的知識(shí)，我們可以得到下面的結(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)化問題：

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

(8)

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

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

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

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

其中σi是D的第i個(gè)奇異值.

引理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)

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

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

(11)

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

(12)

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

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

兩步迭代算法：

步驟一，初始化

1)給定初值Z1=D；

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

3)給定終止誤差ε.

步驟二，計(jì)算Al和Bl

計(jì)算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)到步驟二重復(fù)迭代循環(huán)，更新變量，直到外部算法收斂，即

3實(shí)驗(yàn)結(jié)果及分析

3.1人工數(shù)據(jù)實(shí)驗(yàn)

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

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

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

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

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

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

3.2背景提取與前景檢測

本小節(jié)中，我們用七個(gè)由靜態(tài)攝像機(jī)拍攝的監(jiān)控視頻數(shù)據(jù)做實(shí)驗(yàn)，即：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é)果進(jìn)行直觀的比較，實(shí)驗(yàn)結(jié)果顯示在圖1和圖2中.由于實(shí)驗(yàn)條件的限制，在每個(gè)視頻數(shù)據(jù)集上，我們分別取35幀視頻圖像做實(shí)驗(yàn).由于所有的視頻圖像都是彩色的，首先需要將視頻圖像轉(zhuǎn)成灰度圖像，然后將每一幀灰度圖像拉成一個(gè)長列向量，最后將這35個(gè)列向量并成矩陣D.

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

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

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

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

4結(jié)語

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

【參考文獻(xiàn)】

[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

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

DOI:10.3969/j.issn.1004-1540.2016.01.021

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

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

【作者簡介】陳甲英(1990- )，女，甘肅省金昌人，碩士研究生，主要研究方向?yàn)榫仃嚮謴?fù).E-mail:zccyman@163.com

【中圖分類號(hào)】TP399

【文獻(xiàn)標(biāo)志碼】A

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