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

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

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

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

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

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

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

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

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

1 預(yù)備知識

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

1.1 二值模板

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

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

1.2 置信圖

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

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

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

1.3 矩陣分解

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

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

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

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

2 基于矩陣分解的小計算代價RPCA 模型

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

2.1 模型建立

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

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

2.2 模型求解

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

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

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

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}）是一個對角矩陣，σ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：基于矩陣分解的小計算代價魯棒主成分分析模型（MFRPCA）的求解算法

2.2.6 計算復雜度分析

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

3 數(shù)值實驗

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

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

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

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

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

表2 召回率、精確度、相似度和F-Measure指標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ù)r 的取值是同時影響計算效率和實驗效果的一個關(guān)鍵性因素。實驗發(fā)現(xiàn)，r 的取值過大將無法實現(xiàn)降低計算復雜度這一根本性目標，進而導致矩陣分解技巧的引入失去意義。相反，r的取值過小，單方面追求計算效率，則又無法得到預(yù)期的前景-背景分離效果。因此，為同時兼顧計算效率和實驗效果兩方面，根據(jù)多次實驗結(jié)果的總結(jié)，最終設(shè)定參數(shù)r=4作為其最優(yōu)取值并用于本研究所有實驗。

2）性能參數(shù)：參數(shù)λ1和λ2的選擇是否恰當，對于協(xié)調(diào)低秩、稀疏和噪聲項至關(guān)重要。為了選出最優(yōu)參數(shù)并獲得最佳實驗結(jié)果，首先建立λ1、λ2與最優(yōu)指標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)指標Fm有顯著影響，并且當λ1=50，λ2=1和λ1=500，λ2=10以及λ1=5 000，λ2=100時，均可以獲得動態(tài)背景數(shù)據(jù)集WaterSurface的最優(yōu)指標值，即Fm=0.91。需要特別強調(diào)的是，對于沒有給出地面實況的靜態(tài)背景數(shù)據(jù)集而言，本研究則主要是基于具體實驗的視覺效果來選擇相對應(yīng)的最優(yōu)參數(shù)λ1和λ2的取值。

3.3 對比實驗結(jié)果分析

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

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

由 圖2 可 見，與 現(xiàn) 有 模 型IALM［8］、3WD［10］、RMAMR［11］、SCM-RPCA［12］和TVRPCA［13］相比，本模型實現(xiàn)了更好的前景-背景分離。具體來說，由圖2中的第1行Highway可以看出，本方法不易受移動物體的遮擋和污染，可以獲得更為干凈的背景（見矩形符號），并可以提取出更完整的前景運動目標，如圖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 動態(tài)背景數(shù)據(jù)集實驗

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

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

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

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

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

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

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

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

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

4 總結(jié)與展望

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