(山東科技大學(xué) 數(shù)學(xué)與系統(tǒng)科學(xué)學(xué)院 ,山東 青島 266590)
隨著監(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ù)值效果及魯棒性。
文獻(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ù)。
(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)
對(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)
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。
本節(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)。
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。
實(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ù)了干凈的背景。
為了改進(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)用前景。