基于矩陣分解的小計(jì)算代價(jià)RPCA模型及應(yīng)用

王永麗，苑慶美，陳勇勇，孫志鵬，徐 菲，鐘 勇

（山東科技大學(xué) 數(shù)學(xué)與系統(tǒng)科學(xué)學(xué)院，山東 青島266590）

視頻監(jiān)控系統(tǒng)通常用于場景分析和運(yùn)動(dòng)目標(biāo)檢測［1］等實(shí)際問題。前景-背景分離［2］作為求解這類問題的一個(gè)關(guān)鍵預(yù)處理步驟，已在目標(biāo)跟蹤、行為識別、交通監(jiān)控以及顯著運(yùn)動(dòng)檢測等領(lǐng)域得到了廣泛應(yīng)用，其基本操作是將靜態(tài)的背景與運(yùn)動(dòng)的前景進(jìn)行精確有效地分割。魯棒主成分分析（robust principal component analysis，RPCA）［3-4］作為主成分分析（principal component analysis，PCA）模型的改進(jìn)，是處理前景-背景分離問題的最有效模型之一。該模型的優(yōu)勢在于：即使存在較大誤差或異常值，也能充分利用原始數(shù)據(jù)中潛在的低秩結(jié)構(gòu)。

2009年Wright等［3］提出了RPCA模型。2011年，Candès等［4］將該模型應(yīng)用于前景-背景分離。原始RPCA模型可表述為：

其中：λ 是一個(gè)正參數(shù)，用以平衡低秩背景B 和稀疏前景F；X= ［x1，x2，…，xn］∈Rm×n表示n幀原始輸入圖像序列，且xi為X 中第i列包含m 個(gè)元素的向量。

然而，由于秩函數(shù)和l0范數(shù)的非凸非連續(xù)性，導(dǎo)致模型（1）的求解是一個(gè)NP-難問題。為了更好地求解該問題，最為常用的方法是分別用核范數(shù)和l1范數(shù)來代替秩函數(shù)和l0范數(shù)，進(jìn)而得到如下凸優(yōu)化模型：

盡管上述凸近似模型（2）在一些實(shí)際場景的應(yīng)用中取得了成功，但仍然存在以下缺點(diǎn)：①將所有奇異值進(jìn)行簡單求和意味著每個(gè)奇異值被同等對待［5-7］，使得較大的奇異值受到過度懲罰，進(jìn)而導(dǎo)致有偏差估計(jì)的產(chǎn)生；②核范數(shù)的求解往往需要在每次迭代中對一個(gè)大規(guī)模的矩陣進(jìn)行奇異值分解（singular value decomposition，SVD），這一過程非常耗時(shí)，使計(jì)算代價(jià)變得十分昂貴；③傳統(tǒng)的RPCA 可能無法處理比較復(fù)雜的動(dòng)態(tài)背景問題。例如，對數(shù)據(jù)集“Fall”而言，傳統(tǒng)RPCA會(huì)將其背景中不斷隨風(fēng)飄動(dòng)的樹葉也視為運(yùn)動(dòng)的前景，與真實(shí)前景一起提取，導(dǎo)致前景-背景分離的精確度降低。

針對以上缺陷，近年來幾種改進(jìn)的前景-背景分離方法［8-12］被相繼提出。IALM［8］是解決秩最小化問題的一種高效且省時(shí)的經(jīng)典算法，通常用于前景-背景分離問題。2010年，Zhou等［9］提出穩(wěn)定主成分追蹤（SPCP）模型，該模型的優(yōu)勢在于：即使存在噪聲，每一項(xiàng)仍然可以被較為穩(wěn)定和準(zhǔn)確地恢復(fù)。隨后，Oreifej等［10］提出三項(xiàng)分解（3WD）模型，該模型可以看作SPCP模型的進(jìn)一步改進(jìn)。為了更好地處理前景-背景分離問題，Ye等［11］于2015年提出運(yùn)動(dòng)輔助矩陣恢復(fù)（MAMR）模型及其擴(kuò)展模型（RMAMR）。在3WD 和RMAMR兩種改進(jìn)模型的基礎(chǔ)上，Sobral等［12］提出了基于形狀和置信圖的雙約束RPCA 模型（SCM-RPCA）以改進(jìn)前景檢測效果。此外，Cao等［13］針對前景-背景分離問題，提出新的TVRPCA 模型，該模型使用全變差正則化將前景分成平滑分量和稀疏分量。與原始模型相比，上述模型在前景檢測應(yīng)用中檢測效果顯著提高。但遺憾地是，計(jì)算耗時(shí)這一根本問題仍然沒有得到有效解決。

為了解決上述模型中存在的計(jì)算耗時(shí)問題，本研究引入矩陣分解技巧，利用核范數(shù)的正交不變性，將原始大規(guī)模矩陣轉(zhuǎn)化為兩個(gè)小規(guī)模因子矩陣乘積的形式，來有效避免模型求解過程中計(jì)算代價(jià)昂貴的問題。此外，考慮到時(shí)空約束信息對前景-背景分離的關(guān)鍵作用，為了提高前景-背景的分離效果，引入二值模板對前景稠密運(yùn)動(dòng)進(jìn)行估計(jì)，同時(shí)加入置信圖以期獲得有關(guān)運(yùn)動(dòng)物體位置的先驗(yàn)信息，提出一種基于矩陣分解的小計(jì)算代價(jià)RPCA模型，并應(yīng)用增廣拉格朗日乘子法進(jìn)行求解。最后，將新模型應(yīng)用于視頻序列的前景-背景分離問題，通過大量實(shí)驗(yàn)驗(yàn)證了改進(jìn)模型的有效性。

1 預(yù)備知識

本節(jié)分別對二值模板M 和置信圖Π 的求解進(jìn)行詳細(xì)介紹，同時(shí)給出矩陣分解的定義及性質(zhì)。

1.1 二值模板

為了對運(yùn)動(dòng)顯著的前景區(qū)域進(jìn)行稠密運(yùn)動(dòng)估計(jì)，參照文獻(xiàn)［14］，引入二值模板，即表示稠密運(yùn)動(dòng)信息的權(quán)重矩陣M。為了確定M，首先計(jì)算原始輸入圖像序列中每連續(xù)兩幀圖片之間的密集光流區(qū)域，以獲得水平運(yùn)動(dòng)矢量Vx和垂直運(yùn)動(dòng)矢量Vy兩個(gè)分量，具體計(jì)算方法如下：

假設(shè)xi和xi-1分別表示原始視頻序列X 在t和t-1時(shí)刻的兩幀連續(xù)圖片，則相應(yīng)二值模板M 中列向量mi中的每個(gè)元素mi，k∈{0，1 }可由下式計(jì)算：

1.2 置信圖

為了獲得有關(guān)運(yùn)動(dòng)物體位置的先驗(yàn)信息，引入置信圖。首先對原始輸入視頻序列X 中的每一幀圖片xi進(jìn)行標(biāo)準(zhǔn)化處理，將每一項(xiàng)標(biāo)準(zhǔn)化到0～1范圍內(nèi)。具體計(jì)算公式如下：

其中，Π= ［π1，…，πi，…，πn］為表示置信圖的線性算子。xi，（a，b）表示第i幀圖片中第a 行和第b列的像素值。xi，min和xi，max分別是第i幀圖片中的最小像素值和最大像素值。

通過將置信圖Π 作用于稀疏前景項(xiàng)F 上，可使最可能屬于運(yùn)動(dòng)前景的像素值幾乎保持不變，而對應(yīng)于背景的像素值則變得非常小，幾乎趨近于零。這樣，屬于背景的部分就會(huì)被消除，而屬于前景的部分則會(huì)更加凸顯，進(jìn)而有利于前景和背景的進(jìn)一步分離。

1.3 矩陣分解

考慮到現(xiàn)有的大多數(shù)運(yùn)用核范數(shù)近似矩陣秩函數(shù)的文獻(xiàn)中，求解過程每步迭代都要進(jìn)行奇異值分解，當(dāng)矩陣規(guī)模較大時(shí)通常會(huì)導(dǎo)致計(jì)算代價(jià)昂貴這一問題，引入矩陣分解技巧，以期降低原始RPCA 模型及相關(guān)改進(jìn)模型中計(jì)算量過大問題。

具體地，設(shè)矩陣B ∈Rm×n且rank（B）=r（r ?min{m，n }），則由文獻(xiàn)［15］可知，存在因子矩陣U ∈Rm×r，V ∈Rr×n，使得B=UV 成立，其中，因子矩陣U 為正交規(guī)范列矩陣，即UTU=Ir，V 是一個(gè)秩為r的行滿秩矩陣。

根據(jù)上述矩陣分解的定義及核范數(shù)的正交不變性，有：

由（5）式可知，利用矩陣分解技術(shù)可以將一個(gè)大規(guī)模低秩矩陣的核范數(shù)轉(zhuǎn)換為一個(gè)較小矩陣的核范數(shù)，且小矩陣的規(guī)模遠(yuǎn)小于原始矩陣的規(guī)模，從而可以有效解決原始RPCA 模型求解過程中存在的計(jì)算量過大問題。

2 基于矩陣分解的小計(jì)算代價(jià)RPCA 模型

本節(jié)將把第1節(jié)中介紹的二值模板、置信圖以及矩陣分解等技術(shù)引入RPCA 模型，建立新模型，利用增廣拉格朗日乘子法對新模型進(jìn)行求解，并對求解過程的計(jì)算復(fù)雜度進(jìn)行分析。

2.1 模型建立

將第1節(jié)中介紹的矩陣分解技巧與文獻(xiàn)［10］中的三項(xiàng)分解模型相結(jié)合，并類似于文獻(xiàn)［12］引入二值模板M 和置信圖Π 等時(shí)空約束信息，可得如下基于矩陣分解的小計(jì)算代價(jià)魯棒主成分分析模型（MFRPCA）：

其中，U ∈Rm×r是一個(gè)正交規(guī)范列矩陣，V ∈Rr×n是一個(gè)秩為r（r≤min{m，n}）的較小矩陣。相較于模型（2），此處矩陣U 和V 的規(guī)模都小于原始矩陣B 的規(guī)模，從而使得求解過程的計(jì)算復(fù)雜度大大降低。M 和Π 分別是1.1和1.2節(jié)中定義的二值模板與置信圖矩陣，其作用是為了提高前景-背景分離效果。

2.2 模型求解

本節(jié)將采用交替方向策略的增廣拉格朗日乘子法［8，16］求解凸優(yōu)化模型（6）。首先給出問題（6）的增廣拉格朗日函數(shù)如下：

其中，Y ∈Rm×n和μ ＞0分別表示增廣拉格朗日乘子和懲罰參數(shù)。如公式（13）所示，在每次迭代中，μ 的取值逐漸增大，以使低秩背景B、稀疏前景F 和噪聲項(xiàng)S 之和更接近原始觀測矩陣X。采用交替方向策略迭代求解每個(gè)變量U，V，F(xiàn)，S，Y，μ，具體迭代如下：

由上可知，對原始問題的求解可分別轉(zhuǎn)化為對子問題U、V、F、S、Y 和μ 的迭代求解過程。當(dāng)交替更新每個(gè)變量時(shí)，將其他變量固定為其最新值。以下是對每個(gè)子問題的詳細(xì)求解過程。

2.2.1 Uk+1的更新

給定Vk、Fk、Sk、Yk、μk，通過求解簡化公式（8）來更新子問題U：

問題（14）是著名的Orthogonal Procrustes問題，其全局最優(yōu)解可以通過SVD求出。具體地，設(shè)R1的奇異值分解為可以通過如下公式更新：

其中，R1=（X-M?Fk-Sk+μ-kYk）（Vk）T，A1、B1和Σ1分別是左奇異向量、右奇異向量矩陣和矩陣R1的奇異值矩陣。

2.2.2 Vk+1的更新

在（9）式中，固定Uk+1為其最新值，并基于U 的正交不變性，即UTU=Ir，求解如下子問題來更新Vk+1：

其中，R2的奇異值分解為：，閾值算子Tt（Σ2）=diag（max{σi-t，0}）是一個(gè)對角矩陣，σi是Σ2的對角元素。

2.2.3 Fk+1的更新

固定Uk+1，Vk+1在（18）式中的最新值，求解子問題來更新Fk+1：

3.2.4 Sk+1的更新

固定Uk+1、Vk+1、Fk+1為其最新值，子問題（11）可以寫為如下形式：

2.2.5 Yk+1和μk+1的更新

最后，固定Uk+1，Vk+1，F(xiàn)k+1，Sk+1為其最新值，分別由（12）式和（13）式更新增廣拉格朗日乘子Yk+1和懲罰參數(shù)μk+1。

綜上可得凸優(yōu)化模型（6）的求解算法。

算法1：基于矩陣分解的小計(jì)算代價(jià)魯棒主成分分析模型（MFRPCA）的求解算法

2.2.6 計(jì)算復(fù)雜度分析

本模型的主要計(jì)算量在于對子問題U 和V 的求解。U 和V 的計(jì)算時(shí)間分別為Ο（mr2+mnr）和Ο（nr2+mnr），而子問題F，S 以及Y 的計(jì)算復(fù)雜度均為Ο（mn）。由上述分析可知，當(dāng)矩陣的秩r滿足r?n＜m時(shí)，在每次更新迭代中，本模型的整體計(jì)算量為Ο（mnr），大大提高了模型的求解效率。

3 數(shù)值實(shí)驗(yàn)

本節(jié)將分別對包含靜態(tài)背景和動(dòng)態(tài)背景的真實(shí)數(shù)據(jù)集進(jìn)行實(shí)驗(yàn)，以驗(yàn)證模型的有效性。其中，動(dòng)態(tài)背景相較于前景-背景分離而言，是一個(gè)更具挑戰(zhàn)性的問題。將本模型分別與IALM［8］、3WD［10］、RMAMR［11］、SCM-RPCA［12］和TVRPCA［13］等5種方法進(jìn)行比較。為了保持比較的公正客觀性，5種算法用到的數(shù)據(jù)集以及運(yùn)行環(huán)境均相同。所有方法采用相同的停止標(biāo)準(zhǔn)，即當(dāng)最大迭代次數(shù)達(dá)到100次或者相對誤差小于10-5時(shí)，停止計(jì)算。此外，所有的數(shù)值實(shí)驗(yàn)都是基于PC Intel Core i3-3240T 2.90 GHz CPU，4GB RAM 環(huán)境，使用MATLAB R2014a實(shí)現(xiàn)。

3.1 測試數(shù)據(jù)集與定量評估指標(biāo)

實(shí)驗(yàn)使用的數(shù)據(jù)集主要包括Scene background modeling.net（SBM.net）、Change Detection.net（CDnet）2014［17］和12R［18］。這些數(shù)據(jù)集包括各種具有挑戰(zhàn)性的場景，如動(dòng)態(tài)背景、室外和室內(nèi)環(huán)境、突然的光照變化等。表1給出了所選數(shù)據(jù)集的具體信息，其中，前三列分別代表3個(gè)不同的數(shù)據(jù)集、每個(gè)數(shù)據(jù)集的子數(shù)據(jù)集以及幀分辨率和處理的幀數(shù)量，最后一列給出了背景的靜態(tài)或動(dòng)態(tài)描述。

前景檢測本質(zhì)上是一項(xiàng)二進(jìn)制分割任務(wù)，將每個(gè)像素分成背景和前景。為了準(zhǔn)確、全面地衡量改進(jìn)模型的前景檢測效果，分別使用召回率、精確度、相似度和F-measure（具體定義見表2）四個(gè)指標(biāo)來衡量各模型的客觀性能。通過對每個(gè)公式的分析，發(fā)現(xiàn)每個(gè)評價(jià)指標(biāo)的取值范圍均在0～1之間，且最理想的結(jié)果是1，即地面真實(shí)情況（文獻(xiàn)［17-18］中給出）。

表1 實(shí)驗(yàn)中選用數(shù)據(jù)集的詳細(xì)信息Tab.1 Details of datasets selected in our tests

表2 召回率、精確度、相似度和F-Measure指標(biāo)Tab.2 Recall，precision，similarity and F-measure metrics

3.2 參數(shù)設(shè)置

本模型主要包括兩類參數(shù)：①收斂性參數(shù)μ、ρ和r，主要影響模型收斂的速度；②性能參數(shù)λ1、λ2和r，主要影響模型的性能。

1）收斂性參數(shù)：對于參數(shù)μ 和ρ，分別設(shè)置μ=0.005和ρ=1.6。實(shí)際上，參數(shù)r 的取值是同時(shí)影響計(jì)算效率和實(shí)驗(yàn)效果的一個(gè)關(guān)鍵性因素。實(shí)驗(yàn)發(fā)現(xiàn)，r 的取值過大將無法實(shí)現(xiàn)降低計(jì)算復(fù)雜度這一根本性目標(biāo)，進(jìn)而導(dǎo)致矩陣分解技巧的引入失去意義。相反，r的取值過小，單方面追求計(jì)算效率，則又無法得到預(yù)期的前景-背景分離效果。因此，為同時(shí)兼顧計(jì)算效率和實(shí)驗(yàn)效果兩方面，根據(jù)多次實(shí)驗(yàn)結(jié)果的總結(jié)，最終設(shè)定參數(shù)r=4作為其最優(yōu)取值并用于本研究所有實(shí)驗(yàn)。

2）性能參數(shù)：參數(shù)λ1和λ2的選擇是否恰當(dāng)，對于協(xié)調(diào)低秩、稀疏和噪聲項(xiàng)至關(guān)重要。為了選出最優(yōu)參數(shù)并獲得最佳實(shí)驗(yàn)結(jié)果，首先建立λ1、λ2與最優(yōu)指標(biāo)Fm之間的聯(lián)系。設(shè)定λ1=λ2={0.001，0.01，0.05，0.1，1，10，50，100，500，1 000，5 000}，分別對應(yīng)于圖1中參數(shù)λ1和λ2的取值，即λ1=λ2={1，2，3，…，9，10，11}。由圖1可以看出，參數(shù)λ1和λ2對最優(yōu)指標(biāo)Fm有顯著影響，并且當(dāng)λ1=50，λ2=1和λ1=500，λ2=10以及λ1=5 000，λ2=100時(shí)，均可以獲得動(dòng)態(tài)背景數(shù)據(jù)集WaterSurface的最優(yōu)指標(biāo)值，即Fm=0.91。需要特別強(qiáng)調(diào)的是，對于沒有給出地面實(shí)況的靜態(tài)背景數(shù)據(jù)集而言，本研究則主要是基于具體實(shí)驗(yàn)的視覺效果來選擇相對應(yīng)的最優(yōu)參數(shù)λ1和λ2的取值。

3.3 對比實(shí)驗(yàn)結(jié)果分析

3.3.1 靜態(tài)背景數(shù)據(jù)集實(shí)驗(yàn)

為了驗(yàn)證本研究所提出模型的有效性，首先在靜態(tài)背景視頻序列如Highway、Camouflage以及Blurred等數(shù)據(jù)集上進(jìn)行實(shí)驗(yàn)。具體實(shí)驗(yàn)結(jié)果如圖2所示，其中Highway（1 643）表示視頻序列Highway的第1 643幀的前景-背景分離結(jié)果。

由 圖2 可 見，與 現(xiàn) 有 模 型IALM［8］、3WD［10］、RMAMR［11］、SCM-RPCA［12］和TVRPCA［13］相比，本模型實(shí)現(xiàn)了更好的前景-背景分離。具體來說，由圖2中的第1行Highway可以看出，本方法不易受移動(dòng)物體的遮擋和污染，可以獲得更為干凈的背景（見矩形符號），并可以提取出更完整的前景運(yùn)動(dòng)目標(biāo)，如圖2中第6行Camouflage（見矩形符號）所示。

圖1 參數(shù)對數(shù)據(jù)集“WaterSurface”的影響Fig.1 Effect of parameters for dataset“WaterSurface”

圖2 靜態(tài)背景視頻中前景檢測和背景提取結(jié)果的視覺質(zhì)量比較Fig.2 Visual quality comparison for foreground detection and background extraction results achieved by different methods on static background videos

3.3.2 動(dòng)態(tài)背景數(shù)據(jù)集實(shí)驗(yàn)

為了更好地評估本模型的有效性，本研究進(jìn)一步在更具挑戰(zhàn)性的動(dòng)態(tài)背景視頻上進(jìn)行了大量實(shí)驗(yàn)，分別對9個(gè)典型的動(dòng)態(tài)視頻序列，即Billboard、Boats1以及WaterSurface等數(shù)據(jù)集進(jìn)行了實(shí)驗(yàn)。圖3給出了本模型以及相應(yīng)對比模型［8，10-13］的具體分離效果。由圖3可以看出，本模型對于大多數(shù)動(dòng)態(tài)背景數(shù)據(jù)集而言，尤其是對Billboard、Boats1以及Fall等數(shù)據(jù)集，實(shí)現(xiàn)了良好的前景-背景分離效果。

首先，對于前景檢測而言，如第1行數(shù)據(jù)集Billboard所示，由于廣告牌屏幕一直在變化，進(jìn)而導(dǎo)致對比方法3WD［10］、IALM［8］、RMAMR［11］、SCM-RPCA［12］和TVRPCA［13］會(huì)將其作為運(yùn)動(dòng)前景對象，并與真實(shí)前景（即行駛的車輛）一起提取，尤其是3WD的結(jié)果更差。然而，本方法僅將行駛中的車輛進(jìn)行了提取，避免了背景對前景的干擾（見矩形框）。此外，對于第5行數(shù)據(jù)集Fall而言，所有方法都可以較好地提取行駛的車輛，但是對于馬路對面的行人，只有本模型和SCM-RPCA 模型實(shí)現(xiàn)了更好的檢測和提取（見箭頭所指）。其次，對于背景提取，如第4行Boats1所示，本方法和對比方法RMAMR取得良好的視覺效果，而IALM、SCM-RPCA和TVRPCA的提取效果稍差，3WD最差（見矩形符號）。

圖3 動(dòng)態(tài)背景視頻中前景檢測和背景提取結(jié)果的視覺質(zhì)量比較Fig.3 Visual quality comparison for foreground detection and background extraction results achieved by different methods on dynamic background videos

定量評估實(shí)驗(yàn)結(jié)果如表3所示，本研究所提方法在動(dòng)態(tài)背景視頻中取得了較好的前景檢測效果，在召回率、精確度、相似度和F-Measure等幾乎所有評估指標(biāo)方面都達(dá)到了最佳結(jié)果。表中的粗體數(shù)字表示最優(yōu)結(jié)果，下劃線數(shù)字代表次最優(yōu)結(jié)果。

3.4 運(yùn)行時(shí)間和迭代次數(shù)

為了說明本模型在計(jì)算時(shí)間和計(jì)算量上的優(yōu)勢，將其分別與現(xiàn)有的3WD［10］、IALM［8］、RMAMR［11］、SCM-RPCA［12］和TVRPCA［13］等方法進(jìn)行了比較。通過比較可以看出，對于大多數(shù)數(shù)據(jù)集而言，本方法不僅計(jì)算量少，而且迭代次數(shù)也少。具體結(jié)果詳見表4和表5（100+：迭代限制達(dá)到100）。

表3 不同算法在動(dòng)態(tài)背景視頻上的實(shí)驗(yàn)結(jié)果比較Tab.3 Comparisons results achieved by the different algorithms on dynamic background videos

表4 靜態(tài)背景視頻中不同算法的計(jì)算時(shí)間、迭代次數(shù)和相對誤差的比較Tab.4 Comparison of computation time，iteration times and relative error under different algorithms on static background videos

表5 動(dòng)態(tài)背景視頻中不同算法的計(jì)算時(shí)間、迭代次數(shù)和相對誤差的比較Tab.5 Comparison of computation time，iteration times and relative error under different algorithms on dynamic background videos

4 總結(jié)與展望

通過引入矩陣分解技巧，并結(jié)合二值模板和置信圖，提出了一種改進(jìn)的RPCA 模型用于前景-背景分離問題。通過大量實(shí)驗(yàn)，與現(xiàn)有的方法相比，本模型在節(jié)省計(jì)算時(shí)間和降低計(jì)算復(fù)雜性上具有明顯的優(yōu)勢，且實(shí)驗(yàn)結(jié)果更接近真實(shí)情況。然而，在實(shí)際應(yīng)用中仍然存在一些挑戰(zhàn)，如合理構(gòu)建數(shù)學(xué)模型去處理背景中包含噴泉的情形以及在惡劣天氣情況下的視頻前景-背景分離等問題，將是下一步研究的課題。