視頻背景分離中一種新的非凸秩近似的RPCA模型

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

1 引言

隨著監(jiān)控設(shè)備的普及，監(jiān)控視頻在社會管理和安全中發(fā)揮著重要的作用。這些視頻信號往往是大規(guī)模帶有噪聲的數(shù)據(jù)，給數(shù)據(jù)分析帶來了困難。監(jiān)控視頻信號的自動識別已成為目標(biāo)追蹤、交通檢測以及場景分析等領(lǐng)域的關(guān)鍵環(huán)節(jié)。其中，如何有效地從視頻幀序列中分離出背景和移動前景受到學(xué)者的廣泛關(guān)注。

2006年，Donoho等[1]提出了壓縮傳感(compressed sensing)理論，認(rèn)為高維信號在某個變換域上具有稀疏性，可以以很大的概率從較少的線性測量信號中高維信號恢復(fù)出來。之后基于壓縮傳感理論的秩極小化技術(shù)被廣泛應(yīng)用于高維數(shù)據(jù)分析及圖像處理領(lǐng)域。

為了對視頻序列的前景與背景進行有效分離，學(xué)者們把矩陣秩的極小化技術(shù)引入主成分分析(principal component analysis，PCA)模型[2]。大量數(shù)值實驗結(jié)果表明，當(dāng)觀測矩陣只含較小的高斯隨機噪聲時，PCA模型可以準(zhǔn)確地分離出視頻序列的前景與背景。考慮到PCA模型對于含有異常值或者尖銳噪聲的觀測數(shù)據(jù)非常敏感，且不適用于帶有稀疏噪聲的矩陣，Candes等[3]提出了魯棒主成分分析(robust principod component analysis,RPCA)模型，在原有的模型中加入矩陣稀疏表示，并利用交替方向法對模型進行求解。實驗結(jié)果表明，RPCA模型對數(shù)據(jù)矩陣的噪聲更加穩(wěn)健。目前，RPCA模型已被廣泛應(yīng)用于視頻前景提取[4]、人臉識別[5]和圖像對齊[6]等領(lǐng)域。

傳統(tǒng)的RPCA模型可描述為如下優(yōu)化問題：

(1)

(2)

對于模型(2)，為了降低求解模型的計算時間，提高處理效果，Lin等[7]提出了IALM(Inexact augmented Lagrange multipliers)模型，在RPCA模型中加入了低秩稀疏矩陣的正則項，并利用非精確拉格朗日乘子法求解提出的模型，大幅度降低了運算時間。Zhou等[8]采用雙邊隨機投影模型，利用投影算子代替奇異值分解(singular value decomposition,SVD)，提出了Go分解(go decomposition，GoDec)模型，提高了圖像的處理效果。上述方法均基于核范數(shù)近似的RPCA改進模型，但由于核范數(shù)是對秩函數(shù)的有偏估計，當(dāng)矩陣出現(xiàn)過大奇異值時，會出現(xiàn)核范數(shù)的秩估計過大問題，導(dǎo)致圖像處理效果不理想，且模型求解的每一步都要對矩陣進行奇異值分解，隨著問題規(guī)模增加，計算時間也會大幅度增加。因此，很多學(xué)者開始嘗試?yán)梅峭购瘮?shù)近似秩函數(shù)[9-11]，數(shù)值實驗結(jié)果表明，用非凸函數(shù)近似秩函數(shù)的效果更優(yōu)。

另一方面，傳統(tǒng)的RPCA模型通常采用矩陣的L1范數(shù)來描述圖像整體的稀疏性。但由于L1范數(shù)未考慮前景像素之間的相關(guān)性以及空間上的連續(xù)性，使分離效果受到很大的影響。許多學(xué)者進而考慮用矩陣的L2,1范數(shù)來代替L1范數(shù)，與L1范數(shù)的稀疏性要求不同，L2,1范數(shù)在要求整體稀疏的同時還要求列稀疏，以充分考慮稀疏項元素之間的相關(guān)性，更好地分離運動前景[12]。

針對核范數(shù)的缺陷以及非凸秩近似函數(shù)所展現(xiàn)出的良好特性，提出一種新的非凸函數(shù)來近似秩函數(shù)，同時利用矩陣的L2,1范數(shù)來近似L0范數(shù)，得到一個改進的RPCA模型，采用增廣拉格朗日交替方向法求解該模型，并將該模型應(yīng)用于視頻背景分離。數(shù)值實驗結(jié)果表明，與核范數(shù)及現(xiàn)有的非凸近似模型相比，提出的非凸函數(shù)及非凸秩似模型具有更好的數(shù)值效果及魯棒性。

2 改進的RPCA模型

文獻[13]對目前的主流非凸秩近似函數(shù)特征進行了分析，要求非凸秩近似函數(shù)要滿足矩陣范數(shù)的一般性質(zhì)，且具有良好的秩近似效果。為更好地近似秩函數(shù)，提高RPC模型的數(shù)值計算效率，本研究提出一個新的非凸函數(shù)來近似秩函數(shù)，進而得到一個改進的RPCA模型NC-ALM(non-convex Augmented Lagrange method)模型。

考慮如下非凸函數(shù)

(3)

其中，g(x)為[0,∞)上的增函數(shù)，t為模型參數(shù)。

定義非凸秩近似函數(shù)

(4)

其中，σi(L)為L的第i個奇異值。

由文獻[13]，可得如下結(jié)論：

2) 當(dāng)σi(L)=0時，g(σi(L))=0；

圖1 秩近似函數(shù)與核范數(shù)對比圖Fig.1 Comparison of rank approximation function and nuclear norm

為了更加直觀展示提出的非凸函數(shù)的性質(zhì)，圖1給出了近似函數(shù)對秩的近似效果，可以看出，當(dāng)矩陣奇異值為0時，提出的非凸函數(shù)值為0；當(dāng)矩陣的奇異值大于0時，該函數(shù)會快速的逼近于1；而當(dāng)矩陣奇異值增大時，該函數(shù)值會穩(wěn)定的逼近于1。而隨著參數(shù)t取值增大，該函數(shù)會更加迅速地逼近真實秩。因此，該非凸秩近似函數(shù)的近似效果要優(yōu)于核范數(shù)。

3 增廣拉格朗日乘子法

(5)

本節(jié)利用增廣拉格朗日交替方向乘子法，來求解模型(5)。

模型(5)的增廣拉格朗日函數(shù)為：

(6)

其中，〈A,B〉=Trace(ATB)表示兩個矩陣的內(nèi)積，Y是拉格朗日乘子，μ是正則參數(shù)。

給定初始的L0以及Y0，增廣拉格朗日交替方向乘子法的求解框架如下：

(7)

(8)

Yk+1=Yk+μk(Lk+1+Sk+1-X)，

(9)

μk+1=ρμk。

(10)

3.1 求解問題(7)

對于子問題(7)的求解，有如下結(jié)論：

(11)

問題(11)是一個凹函數(shù)與凸函數(shù)的組合，利用文獻[15]的算法進行求解可得

(12)

式(12)的封閉解

(13)

Lk+1=Udiag(σ*)VT。

(14)

3.2 求解問題(8)

S的更新可以通過文獻[16]的引理3.3進行計算。

引理3[16]對于給定的矩陣M∈Rm×n以及τ>0，則優(yōu)化問題：

存在唯一的封閉解S*。那么 ：

(15)

其中Mj表示矩陣M的第j列。

由上述結(jié)論可得求解問題(5)的算法框架如下：

算法1: 非凸增廣拉格朗日乘子法(NC-ALM)輸入: 觀測矩陣X,參數(shù)λ,μ>0,最大迭代kmax; 初始化: S=0,Y=0,迭代次數(shù)k=0; 步驟1:利用式(14)更新Lk+1; 步驟2:利用式(15)更新Sk+1; 步驟3:計算 Yk+1=Yk+μk(Lk+1+Sk+1-X); 步驟4:計算 μk+1=ρμk; 直到k>kmax或{Lk,Sk,Yk}收斂;輸出:L=Lk+1,S=Sk+1。

4 實驗結(jié)果與比較

本節(jié)將提出的NC-ALM模型應(yīng)用到不同的場景中，包括靜態(tài)/動態(tài)背景下的背景前景分離，并與APG[17]，IALM和GoDec 3種模型進行比較。4種模型用到的數(shù)據(jù)集以及運行環(huán)境相同，數(shù)值實驗均基于PC Intel Core i3-3240T 2.90GHz CPU,4GB RAM環(huán)境，使用MATLAB R2014a實現(xiàn)。

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

NC-ALM模型中主要用到4個參數(shù)：μ、λ、ρ以及t。參考文獻[18]中的λ取值規(guī)則，取λ=10-3。對于懲罰參數(shù)μ，采用逐步遞增的方式，并取初始值μ0=2.4×10-5。為了加快算法收斂速度，參數(shù)ρ=1.2。t為非凸函數(shù)的參數(shù)，實驗中取t=300。

算法迭代停止標(biāo)準(zhǔn)為：

Err≤εor Iter≥Imax，

(16)

其中

(17)

ε為預(yù)先輸入的終止誤差，ε=10-6，Iter為當(dāng)前的迭代次數(shù)，Imax為預(yù)先輸入的最大迭代次數(shù)，Imax=300。

4.2 實驗比較

實驗采用了12R數(shù)據(jù)集，其中包括Hall、Escalator、Lobby、Fountain、Campus和Restaurant視頻集。對于用到的每個視頻序列，截取了連續(xù)的幾百幀作為觀測數(shù)據(jù)集。

表1 實驗中的數(shù)據(jù)集統(tǒng)計信息
Table 1 Statistical information of data sets in the experiment

數(shù)據(jù)集圖像維數(shù)數(shù)據(jù)集幀數(shù)截取數(shù)據(jù)集幀數(shù)Hall144?1763 584100Escalator130?1603 000100Lobby128?1602 000100Fountain128?1602 750170Campus 128?1601 439210Restaurant120?1603 055500

為了使不同的算法具有可比性，實驗統(tǒng)一采用APG算法的停機準(zhǔn)則。GoDec模型需要預(yù)先設(shè)置矩陣的秩，根據(jù)文獻[8]，秩設(shè)置為5。表2給出了4種模型處理不同數(shù)據(jù)集的迭代次數(shù)以及運行時間對比。無論在動態(tài)背景還是靜態(tài)背景的數(shù)據(jù)集中，由于GoDec模型采用隨機投影的方式，難以保證計算精度，故迭代次數(shù)固定為101。而APG模型需要迭代100次以上，IALM模型需要迭代32次，本模型需要迭代3到5次。由于迭代次數(shù)遠(yuǎn)低于其他三種模型，NC-ALM模型的運行時間最短。因此在處理大規(guī)模的數(shù)據(jù)信息時，NC-ALM模型優(yōu)勢更大。

表 2 模型迭代次數(shù)與運行時間比對Tab.2 Comparison of model iteration number and running time

表 3 算法恢復(fù)背景矩陣秩與計算誤差對比Tab.3 Comparison of model recovery background matrix rank and calculation error

表3給出了4種模型恢復(fù)出低秩矩陣的秩以及計算精度比較。由于監(jiān)控設(shè)備是固定的，視頻背景相對固定，因此每一幀的背景像素大致相同，真實低秩矩陣的秩為1。通過表3可以看出，APG模型的秩大大偏離了真實低秩矩陣的秩，GoDec模型由于添加了秩約束，恢復(fù)的低秩矩陣秩固定為5,而本文的NC-ALM模型恢復(fù)的低秩矩陣最接近真實的背景矩陣秩。特別在Restaurant數(shù)據(jù)集中，視頻中移動目標(biāo)移動緩慢，APG模型以及IALM模型將部分本屬于前景中的像素歸類于背景中，導(dǎo)致背景矩陣的秩遠(yuǎn)遠(yuǎn)高于真實秩，而NC-ALM模型可以很好地恢復(fù)出矩陣的真實秩。此外，NC-ALM算法的計算精度高于GoDec以及APG模型。

圖2為視覺效果比較，第一行至第六行分別為Hall、Escalator、Lobby、Fountain、Campus和Restaurant視頻集。第1列是六個數(shù)據(jù)集中選取的某一幀原始圖片；2～3列是APG模型恢復(fù)的背景前景圖片；4～5列為IALM模型恢復(fù)的背景前景圖片； 6～7列為GoDec模型恢復(fù)的背景前景圖片；8～9列為本文模型恢復(fù)的背景前景圖片。由圖2對比可以看出，在Escalator和Restaurant數(shù)據(jù)集中，APG、IALM、GoDec模型都存在將前景像素歸類于背景的情況，導(dǎo)致恢復(fù)的背景不清晰(背景圖像中殘留了移動目標(biāo)的陰影)。 特別是Restaurant視頻集，APG、IALM模型將大量前景像素歸類于背景，GoDec模型存在少量陰影，而NC-ALM模型分離出了更為干凈的背景。

在圖3中以Escalator數(shù)據(jù)集為例給出了4個模型的像素值對比，用縱坐標(biāo)表示Escalator數(shù)據(jù)集每一幀中的坐標(biāo)(36,55)的像素值，橫坐標(biāo)表示幀數(shù)。Escalator數(shù)據(jù)集的橫坐標(biāo)分為4個區(qū)間，分別是[0,13],[14,29],[30,40],[41,100]。第1個區(qū)間中，人即將出現(xiàn)，影子先到達了標(biāo)記的坐標(biāo)；第2個區(qū)間中，人出現(xiàn)在標(biāo)記的坐標(biāo)上；第3個區(qū)間，人剛離開，影子出現(xiàn)在了該坐標(biāo)上；第4個區(qū)間中的坐標(biāo)為背景，沒有移動物體。從圖3可以看出，在人即將經(jīng)過的第1個區(qū)段[0,13]幀以及人剛經(jīng)過、但留有影子的第2個區(qū)間[30-40]幀，APG，IALM，GoDec背景像素值接近原始幀的像素，說明并未檢測出影子。而本文算法在這2個階段更接近于真實的背景像素；在人經(jīng)過標(biāo)記點的第二個區(qū)間[14-29]幀，GoDec跟IALM比較接近真實背景像素值，但本模型恢復(fù)效果更好。

圖2 不同模型視頻背景分離效果比較Fig.2 Comparison of background separation effect for different models

圖3 Escalator數(shù)據(jù)集像素值對比

從圖3中有人經(jīng)過的3個區(qū)間中各選取了一幀，即視頻序列的第1幀、第20幀和第30幀進行比對，得到圖4?？梢姡珿oDec、IALM和APG模型提取的背景含有前景像素的干擾(框內(nèi)部分)，而本算法恢復(fù)了干凈的背景。

5 結(jié)論

為了改進傳統(tǒng)RPCA模型中核范數(shù)近似秩函數(shù)存在的秩估計過大且計算效率低下缺陷，設(shè)計了一種新的非凸函數(shù)近似秩函數(shù)，并且采用了結(jié)構(gòu)性稀疏的模型，以在保證稀疏約束的前提下，考慮運動目標(biāo)在空間上的相關(guān)性，得到了一種新的非凸秩函數(shù)PCA模型NC-ALM。從實驗定量分析來看，NC-ALM模型在保證精度的前提下，減少了運算時間，提高了圖像處理的效果。且隨著數(shù)據(jù)規(guī)模的擴大，NC-ALM模型具有更好的應(yīng)用前景。