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

1 引言

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

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

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

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

(1)

(2)

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

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

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

2 改進(jìn)的RPCA模型

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

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

(3)

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

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

(4)

其中，σi(L)為L(zhǎng)的第i個(gè)奇異值。

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

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

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

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

3 增廣拉格朗日乘子法

(5)

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

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

(6)

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

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

(7)

(8)

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

(9)

μk+1=ρμk。

(10)

3.1 求解問(wèn)題(7)

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

(11)

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

(12)

式(12)的封閉解

(13)

Lk+1=Udiag(σ*)VT。

(14)

3.2 求解問(wèn)題(8)

S的更新可以通過(guò)文獻(xiàn)[16]的引理3.3進(jìn)行計(jì)算。

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

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

(15)

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

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

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

4 實(shí)驗(yàn)結(jié)果與比較

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

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

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

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

表1 實(shí)驗(yàn)中的數(shù)據(jù)集統(tǒng)計(jì)信息
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

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

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

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

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

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

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

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

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

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

5 結(jié)論

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