劉鑫,張釗強,姚佳文,郭莉莉,齊春

(1.西安交通大學電子與信息工程學院,710049,西安;2.云南大學信息學院,650091,昆明)

?

低秩矩陣和結(jié)構(gòu)化稀疏分解的視頻背景差分方法

劉鑫1,張釗強1,姚佳文1,郭莉莉2,齊春1

(1.西安交通大學電子與信息工程學院,710049,西安;2.云南大學信息學院,650091,昆明)

針對基于矩陣分解的視頻前景檢測傳統(tǒng)算法中忽視前景元素之間相關(guān)性會導致檢測結(jié)果容易受噪聲干擾和運動目標檢測不完整等問題,提出了一個低秩矩陣和結(jié)構(gòu)化稀疏分解的視頻背景差分算法。該算法充分考慮到視頻前景區(qū)域的結(jié)構(gòu)化分布特征,利用結(jié)構(gòu)化稀疏范數(shù)對前景進行約束;針對矩陣分解方法中參數(shù)選擇的難題,采用了一種基于運動顯著性判定的兩步法來實現(xiàn)動態(tài)背景去除和正則化參數(shù)的自適應(yīng)選擇,即第一步利用低秩和結(jié)構(gòu)化稀疏分解獲得運動候選塊,第二步對運動候選塊進行顯著性分析并利用自適應(yīng)正則化參數(shù)的塊稀疏分解進行前景檢測。實驗結(jié)果表明:與現(xiàn)有的基于矩陣分解的前景檢測方法相比,該算法能夠更加適應(yīng)復雜多變的視頻環(huán)境,在I2R測試庫中檢測出的前景有較高的精確度和召回率。

前景檢測;背景差分;矩陣分解;低秩表示;結(jié)構(gòu)化稀疏

視頻前景檢測是智能視頻監(jiān)控、行為分析[1]等計算機視覺系統(tǒng)的關(guān)鍵步驟,伴隨著近幾年來人們對于社會安全問題的日益關(guān)注而得到廣泛的研究和應(yīng)用。在各種檢測算法中,背景差分被認為是提取前景目標的最有效方法,而背景差分算法核心問題在于如何進行有效的背景建模。作為更高層視覺任務(wù)(如目標跟蹤和行為識別)的基礎(chǔ)環(huán)節(jié),背景模型的好壞將直接影響到整個系統(tǒng)的準確性和魯棒性。

目前國內(nèi)外關(guān)于背景建模的方法大致可以歸為以下2類。一類方法為基于像素級的背景模型,包括混合高斯(MoG)模型[2-3]、貝葉斯模型[4]、馬爾科夫隨機場(MRF)模型[5]、背景字典(Code Book)模型[6]、像素采樣(ViBe)模型[7]等,但以上基于單像素建模的方法都對背景做了特殊的、固定的假設(shè),并且單像素的獨立建模往往忽略了像素間的聯(lián)系和相關(guān)性。綜上原因,在復雜多變的視頻場景下,基于像素的前景檢測算法的表現(xiàn)往往不盡人意。另外一類方法是基于圖像級的背景模型,最新的研究熱點是基于壓縮感知理論的前景檢測方法。在壓縮感知的理論框架下,Candes等人提出了一種魯棒主成分分析法(RPCA)[8-9],假設(shè)由視頻中的幀組成的矩陣可以分解成2個分別具有低秩和稀疏特性的矩陣,認為背景矩陣具有低秩特性,前景矩陣具有稀疏特性,從而提出了一個基于主成分追蹤(PCP)的魯棒主成分分析法[9],用核范數(shù)對背景矩陣進行約束,用l1范數(shù)對前景矩陣進行約束。與之前所介紹的方法相比,這類視頻前景檢測算法僅僅需要矩陣分解,同時矩陣分解的機制不需要初始訓練,因而可以實現(xiàn)背景估計和前景檢測任務(wù)的同步進行,而傳統(tǒng)的背景提取方法(如混合高斯法等)有著繁多的輸入?yún)?shù)。

因此,基于矩陣分解的視頻前景檢測方法如PCP方法是近年來的一個研究熱點。然而,PCP方法有2個可改進之處:①PCP方法沒有考慮到前景信號的結(jié)構(gòu)特性;②PCP方法中單一的、固定的尺度參數(shù)設(shè)置導致模型容易受到動態(tài)背景的干擾。針對這2個問題,本文提出了一個兩步的框架,如圖1所示。首先利用結(jié)構(gòu)化稀疏范數(shù)對前景進行建模,提出了一個基于低秩和結(jié)構(gòu)化稀疏分解的前景檢測方法,該方法考慮了前景元素的結(jié)構(gòu)信息;然后采用一種時間片段數(shù)據(jù)運動顯著性分析的方法,通過對分解后得到的候選目標進行統(tǒng)計,并計算出相應(yīng)的平均運動顯著性,再根據(jù)平均顯著性值對每個目標塊給予相應(yīng)的正則參數(shù)值;最后采用塊稀疏魯棒主成分分析法進行前景檢測。

圖1 本文兩步框架算法圖

1 低秩和結(jié)構(gòu)化稀疏分解前景檢測

1.1 PCP方法回顧

PCP法可用公式表示為

‖L‖*+λ‖S‖1,D=L+S

(1)

式中:D∈Rm×n為觀測數(shù)據(jù),由多個視頻幀通過列重排后構(gòu)成,即D矩陣中的每一列對應(yīng)原始視頻的一幀;L和S分別表示進行分解之后得到的背景矩陣和前景矩陣;‖L‖*表示矩陣L的核范數(shù)(nuclear norm),即矩陣L的奇異值之和;‖S‖1為矩陣的l1范數(shù),即矩陣S中元素絕對值之和。

統(tǒng)計信號處理的知識表明[10],當PCP法利用l1范數(shù)約束問題中的稀疏度時,其假設(shè)稀疏信號的每一個元素是獨立分布的,然而在許多實際問題當中,稀疏信號的分布并不是獨立的。例如,在人臉識別領(lǐng)域,實際進行測試的人臉圖像中由光照變化造成的陰影、遮擋等不屬于人臉部分的異常值在空間上是連續(xù)分布的;在視頻前景檢測中,前景信號可以看成是不屬于背景模型的異常值,但前景像素并不是無意義的隨機出現(xiàn)在某個位置,它們通常在空間上具有結(jié)構(gòu)化分布的特征。

1.2 基于重疊塊的結(jié)構(gòu)化稀疏誘導范數(shù)

為了能夠定義更加復雜的結(jié)構(gòu),Mairal等人提出了重疊塊結(jié)構(gòu)的結(jié)構(gòu)化稀疏誘導范數(shù)[11],定義式為

(2)

式中:s為具有結(jié)構(gòu)化分布特性的稀疏信號;sj為s的第j個元素;‖·‖∞代表l∞范數(shù),指所有元素的最大絕對值;ηg為每個組的權(quán)重,一般取值為1;G為預先定義的組分布的集合,其中每一個組分布為g;sg為組分布為g的s的子集。

圖2給出了本文所采用的基于3×3像素大小重疊塊的圖結(jié)構(gòu)G。在一個8×8像素大小圖片上,從最左上角開始,每一個塊分別向右和向下移動一個像素,直至完成整個遍歷。在這種設(shè)計下,3×3像素大小重疊塊的組結(jié)構(gòu)對于一個8×8像素大小的圖片有36個組,即G={g1,…,g36},每一個塊與其4鄰域的鄰居塊會重疊6個元素,而每一個塊內(nèi)元素就構(gòu)成了一個組g。

圖2 3×3像素大小重疊塊圖結(jié)構(gòu)

1.3 低秩和結(jié)構(gòu)化稀疏模型

因為結(jié)構(gòu)化稀疏范數(shù)允許定義復雜的結(jié)構(gòu),所以能夠很好地體現(xiàn)出實際問題中稀疏信號的結(jié)構(gòu)化分布特性,本文利用重疊塊作為結(jié)構(gòu)特征對視頻中的前景信號進行約束。

對于視頻前景檢測問題,式(2)給出的是一幀視頻中前景信號的結(jié)構(gòu)化約束,這相當于對前景矩陣的一列元素進行定義。通過對式(2)進行擴展,本文引入如下一個能夠?qū)φ麄€前景矩陣進行結(jié)構(gòu)化稀疏的約束

‖sj,g‖∞

(3)

式中:S∈Rm×n是由具有結(jié)構(gòu)化分布特性的前景信號組成的矩陣,其第j列向量sj∈Rm,利用式(2)對sj進行約束。

由于背景矩陣的每一列表示一幀視頻的背景信號,這些不同列的背景信號前后之間具有很大的相關(guān)性,可以分布到一個較低維度的空間上。因此,用低秩特性對背景矩陣進行約束。同時,受到文獻[12-13]的啟發(fā),對于L,本文還采用了l2,1約束,以及對應(yīng)的正則化參數(shù)κ、v設(shè)置,從而保證恢復得到的背景矩陣L中對應(yīng)于前景所在的位置具有零值。最終得到本文模型

‖L‖*+κ(1-v)‖L‖2,1+κvΩ(S)

s.t.D=L+S

(4)

1.4 模型的求解

采用增廣拉格朗日乘子法(ALM)求解式(4)的目標函數(shù)

L(L,S,Y;μ)=‖L‖*+κ(1-v)‖L‖1,2+

(5)

式中:μ為正懲罰參數(shù);Y為拉格朗日乘子向量;〈·〉代表內(nèi)積操作;‖·‖F(xiàn)表示Frobenius范數(shù)。

最小化拉格朗日函數(shù)式(5)的問題可以轉(zhuǎn)化為下面3個子問題

(6)

(7)

Y=Y+μ(D-L-S)

(8)

當S和Y固定時,求解L的子問題式(6)可以寫為

‖L‖*+κ(1-v)‖L‖2,1

(9)

‖L‖*+κ(1-v)‖L‖2,1

(10)

本文采用了文獻[13]中的Douglas/Peaceman-Rachford(DR)迭代算法進行求解。DR迭代算法在第j次迭代中分別更新L(j+1/2)和L(j+1)兩個值,然后進行循環(huán)迭代,直至收斂得到最優(yōu)的解L。

采用類似的方法,將求解S的子問題式(7)化簡為

(11)

對于問題式(11),本文采用一個二次最小割方法[12]去求解。

當L和S都求解完畢后,最后更新拉格朗日乘子Y,即式(8)。

利用ALM方法求解本文低秩和結(jié)構(gòu)化稀疏分解問題式(4)的計算流程如下(具體的參數(shù)設(shè)置請參考文獻[12-13]):

(1) 輸入矩陣D,參數(shù)初始化;

(2) while not converge do;

(6) while not converge do;

(10)j←j+1;

(11)end while;

(16)Yk+1=Yk+μk(D-Lk+1-Sk+1);

(17)μk+1=ρμk;k←k+1;

(18) end while。

圖3給出了利用本文算法在光照突變的情況下進行前景檢測的結(jié)果,并且與現(xiàn)有的基于矩陣分解的檢測方法DECOLOR法[14]、LBD法[12]和PCP法[9]進行了對比。從圖中可以看出,由于采用了結(jié)構(gòu)化特征的約束,采用本文法得到的前景檢測結(jié)果更加完整,并且能夠及時響應(yīng)光線的變化,得到了更加準確的背景估計。

(a)視頻幀得到的背景 (b)本文方法得到的背景 (c)DECOLOR法到的背景 (d)LBD法得得到的背景 (e)PCP法得到的背景

(f)本文方法得得到的前景 (g)DECOLOR法到的前景 (h)LBD法得到的前景 (i)PCP法得到的前景圖3 本文低秩和結(jié)構(gòu)化稀疏分解方法與DECOLOR、LBD及PCP方法結(jié)果比較

2 自適應(yīng)正則參數(shù)設(shè)置的塊稀疏分解

利用上述低秩和結(jié)構(gòu)化稀疏分解,可以得到運動候選塊,但是由于矩陣分解的方法存在參數(shù)選擇的難題,這些運動候選塊既包含真正前景,也包含背景部分的運動。本文利用運動顯著性分析技術(shù)來判斷經(jīng)過分解后得到的運動候選塊中哪些屬于背景運動,哪些屬于真正的前景運動。

在矩陣分解方法的模型中,很難選擇單一的參數(shù)去適應(yīng)所有場景。簡單來講,在式(1)中,因為參數(shù)λ控制著矩陣分解后背景和前景的比例,對于前景檢測任務(wù),希望λ值小一點從而使得得到完整的前景目標;對于背景估計任務(wù),同樣也希望λ值小一點,從而使得恢復的背景中不會具有前景的殘影?？紤]到得到完整目標的重要性,在以往的算法中往往采用了一個較小的、固定的λ值,但是這種全局的、統(tǒng)一的參數(shù)設(shè)置使得模型很難去除復雜多變的背景運動的干擾。

2.1 運動顯著性分析

(a)視頻幀 (b)候選塊 (c)運動顯著圖圖4 利用運動顯著圖進行運動分析

2.2 塊稀疏分解

經(jīng)過運動顯著性分析之后,平均運動顯著性值較低的(背景運動)塊會被濾掉。對于其他候選塊,已知塊的大小和位置以及運動顯著性參數(shù),在第二步中采用塊稀疏魯棒主成分分析方法[15](Block-sparse RPCA)進行最終的前景檢測

(12)

式中:D為觀測數(shù)據(jù);L為分解得到的低秩部分;S為分解得到的塊稀疏部分;‖·‖F(xiàn)為矩陣的Frobenius范數(shù);pi代表一個操作函數(shù),用來將S的每一列中表示第i塊的元素提取出來,用作下一步的處理。根據(jù)文獻[15,17],第i塊的正則化參數(shù)計算如下

(13)

由于本文提出的兩步框架是在圖像塊的層面上對視頻進行處理,并且針對背景變化和前景運動來設(shè)置不同的正則參數(shù)值,因此能夠在得到準確的背景估計的同時得到完整的前景檢測結(jié)果(見圖5b和圖5e),而PCP方法采用單一的參數(shù)設(shè)置,如圖5c、圖5f所示,雖然λ較小時能得到較完整的前景目標(人),但是同時也誤檢出運動的背景(海浪);如果設(shè)置較大的λ,那么運動目標被融入背景中,動態(tài)背景(海浪)也并沒有被完全過濾掉,如圖5d及圖5g所示。

(a)視頻幀

(b)本文方法得 (c)λ=m-1/2時PCP (d)λ=2m-1/2時PCP到的背景方法得到的背景方法得到的背景

(e)本文方法得 (f)λ=m-1/2時PCP (g)λ=2m-1/2時PCP到的前景方法得到的前景方法得到的前景圖5 本文方法與PCP方法前背景分離結(jié)果對比

3 實驗結(jié)果及分析

為了驗證本文算法的有效性,在實驗部分,與現(xiàn)有的4種方法進行了對比,包含3個目前最新的基于矩陣分解的方法(DECOLOR[14],LBD[12]和PCP[9])和一個基于單像素建模的經(jīng)典算法ViBe[7]。

本文采用I2R測試視頻數(shù)據(jù)庫[4]進行實驗,這個測試庫共包含9段視頻,主要包括了動態(tài)背景(樹枝、水面、窗簾運動、噴泉、電梯等)、光照漸變及突變(開關(guān)燈)、

陰影等測試場景。首先給出針對復雜動

態(tài)背景的定性對比實驗的結(jié)果圖。從圖6～8可以看出,針對包含復雜動態(tài)背景的視頻Campus(CAM),Fountain(FT),Escalator(ES),本文方法能有效地去除動態(tài)背景的干擾,同時也能準確地檢測出前景目標。DECOLOR方法往往得出過于光滑的檢測效果,產(chǎn)生了大量的誤檢,其他方法則不能有效地去除動態(tài)背景的干擾,本文方法有效地處理了這些視頻,比其他算法得到了更好的檢測結(jié)果。

定量實驗中,采用以下3個指標來評價檢測結(jié)果

(14)

(a)視頻幀 (b)標準結(jié)果 (c)本文方法 (d)DECOLOR (e)LBD (f)PCP (g)ViBe圖6 I2R綜合測試視頻數(shù)據(jù)庫CAM視頻的前景檢測結(jié)果比較

(a)視頻幀 (b)標準結(jié)果 (c)本文方法 (d)DECOLOR (e)LBD (f)PCP (g)ViBe圖7 I2R綜合測試視頻數(shù)據(jù)庫ES視頻的前景檢測結(jié)果比較

(a)視頻幀 (b)標準結(jié)果 (c)本文方法 (d)DECOLOR (e)LBD (f)PCP (g)ViBe圖8 I2R綜合測試視頻數(shù)據(jù)庫FT視頻的前景檢測結(jié)果比較

(15)

(16)

式中:T為檢測結(jié)果當中屬于正確分割的前景像素個數(shù);FN為結(jié)果當中沒有檢測出來的部分,即漏檢的前景像素的數(shù)目;FP為結(jié)果當中錯誤認為前景的部分,即誤檢為前景像素的數(shù)目;F為綜合測量指標,是綜合考慮召回率(r)和精確率(p)后可代表方法性能的指標,若某個方法的F值越高,則表明該方法對于該視頻的前景檢測結(jié)果越好。

表1給出了定量實驗下的F測量指標,由表1可以看出,本文方法在6段視頻下的F最高,在其余3段視頻中排名第2。綜合來看,本文方法在I2R綜合測試視頻數(shù)據(jù)庫上有最高的平均F測量值。

表1 I2R綜合測試視頻數(shù)據(jù)庫各個方法的F指標

注:黑體數(shù)據(jù)為同一條件下的最高值。

4 結(jié) 論

本文充分考慮了視頻前景的結(jié)構(gòu)化分布特性以及背景圖像之間的相關(guān)性,提出了一個基于低秩和結(jié)構(gòu)化稀疏分解的視頻前景檢測方法,實現(xiàn)了背景矩陣估計和前景矩陣分割的同步進行。此外,針對目前基于矩陣分解方法中存在參數(shù)選擇的尺度問題,利用一個基于運動顯著性的兩步框架來實現(xiàn)參數(shù)的自適應(yīng)選擇。實驗結(jié)果表明,本文提出的兩步框架可以處理動態(tài)背景視頻下的正則化參數(shù)選擇問題,在標準測試數(shù)據(jù)庫上進行視頻場景的對比實驗中取得了更好的檢測效果。目前,本文方法的討論只局限于固定相機下的視頻處理,未來將考慮處理其他運動特征從而可以將工作擴展到移動相機下的視頻前景檢測。

[1] 王偉嘉, 劉輝, 沙莉, 等. 滯留與偷竊物體實時檢測與分類算法 [J]. 計算機應(yīng)用, 2007, 27(10): 2591-2594. WANG Weijia, LIU Hui, SHA Li, et al. Real time detection and classification algorithm for abandoned and stolen objects [J]. Computer Applications, 2007, 27(10): 2591-2594.

[2] STAUFFER C, GRIMSON W E L. Adaptive background mixture models for real-time tracking [C]∥Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition. Piscataway, NJ, USA: IEEE, 1999: 246-252.

[3] 劉鑫, 劉輝, 強振平, 等. 混合高斯模型和幀間差分相融合的自適應(yīng)背景模型 [J]. 中國圖象圖形學報, 2008, 13(4): 729-734. LIU Xin, LIU Hui, QIANG Zhengping, et al. Adaptive background modeling based on mixture Gaussian model and frame subtraction [J]. Journal of Image and Graphic, 2008, 13(4): 729-734.

[4] LI L Y, HUANG W M, GU I H, et al. Statistical modeling of complex backgrounds for foreground object detection [J]. IEEE Transactions on Image Processing, 2004, 13(11): 1459-1472.

[5] SHEIKH Y, SHAH M. Bayesian modeling of dynamic scenes for object detection [J]. IEEE Transactions on Pattern Analysis and Machine Intelligence, 2005, 27(11): 1778-1792.

[6] KIM K, CHALIDABHONGSE T H, HARWOOD D, et al. Realtime foreground-background segmentation

using codebook model [J]. Real-Time Imagine, 2005, 11(3): 172-185.

[7] BARNICH O, VAN DROOGENBROECK M. ViBe: a universal background subtraction algorithm for video sequences [J]. IEEE Transactions on Image Processing, 2011, 20(6): 1709-1724.

[8] CANDES E J, LI X, MA Y, et al. Robust principal component analysis? [J]. Journal of the ACM, 2011, 58(3): 11-47.

[9] WRIGHT J, YANG A Y, GANESH A, et al. Robust face recognition via sparse representation [J]. IEEE Transactions on Pattern Analysis and Machine Intelligence, 2009, 31(2): 210-227.

[10]TIBSHIRANI R. Regression shrinkage and selection via the lasso [J]. Journal of the Royal Statistical Society: Series B Methodological, 1996, 58(1): 267-288.

[11]MAIRAL J, JENATTON R, BACH F R, et al. Network Flow Algorithms for Structured Sparsity [C]∥Proceedings of Neural Information Processing Systems. Vancouver, Canada: NIPS, 2010: 1558-1566.

[12]GUYON C, BOUWMANS T, ZAHZAH E H. Foreground detection based on low-rank and block-sparse matrix decomposition [C]∥Proceedings of the IEEE International Conference on Image Processing. Piscataway, NJ, USA: IEEE, 2012: 1225-1228.

[13]TANG G, NEHORAI A. Robust principal component analysis based on low-rank and block-sparse matrix decomposition [C]∥Proceedings of the Annual Conference on Information Sciences and Systems. Piscataway, NJ, USA: IEEE, 2011: 1-5.

[14]ZHOU X W, YANG C, YU W. Moving object detection by detecting contiguous outliers in the low-rank representation [J]. IEEE Transactions on Pattern Analysis and Machine Intelligence, 2013, 35(3): 597-610.

[15]GAO Z, CEONG L F, SHAN M. Block-sparse RPCA for consistent foreground detection [C]∥Proceedings of the European Conference on Computer Vision. Heidelberg, Germany: Springer, 2012: 690-703.

[16]CUI X Y, LIU Q S, ZHANG S T, et al. Temporal Spectral Residual for fast salient motion detection [J]. Neurocomputing, 2012, 86: 24-32.

[17]LIN Z, CHEN M, MA Y. The augmented Lagrange multiplier method for exact recovery of corrupted low-rank matrices [EB/OL]. (2013-10-18)[2015-11-20]. http: ∥arxiv.org/pdf/1009.5055v3.pdf.

(編輯 劉楊)

A Background Subtraction Method Based on Decomposition of Low Rank and Sparsity Matrices

LIU Xin1,ZHANG Zhaoqiang1,YAO Jiawen1,GUO Lili2,QI Chun1

(1. School of Electronics and Information Engineering, Xi’an Jiaotong University, Xi’an 710049, China;2. School of Information Science and Engineering, Yunnan University, Kunming 650091, China)

A background subtraction method based on decomposition of low-rank and structured sparsity matrices is proposed to solve the problem that detection results are sensitive to noise and incomplete caused by ignoring the relationship between foreground pixels in traditional foreground detection methods based on matrix decomposition. The method takes the structural distribution of the foreground into account, and a structured sparsity constraint is used on the foreground pixels. Moreover, a two-stage framework based on motion saliency is introduced to address the parameter setting issue in dynamic background videos and to tune regularization parameters adaptively. Motion block candidates are obtained by using the low rank and structured sparsity decomposition in the first step. Then, motion saliency analysis is applied to these candidates and the adapt block sparsity decomposition is used to detect the foreground in the second step. Experimental results show that the performance of the proposed method is more adaptive than the existing foreground detection methods based on matrix decomposition in complex videos, and that the proposed approach outperforms the state-of-the-art methods according to the precision and recall results on dataset I2R.

foreground detection; background subtraction; matrix decomposition; low rank representation; structured sparsity

2015-12-25。 作者簡介:劉鑫(1981—),男,博士生;齊春(通信作者),男,教授,博士生導師。 基金項目:國家自然科學基金資助項目(61572395)。

時間:2016-04-26

10.7652/xjtuxb201606004

TP391

A

0253-987X(2016)06-0023-07

網(wǎng)絡(luò)出版地址:http:∥www.cnki.net/kcms/detail/61.1069.T.20160426.2016.002.html