董懷琴，潘彬彬，陳文勝，徐　晨

1) 深圳大學(xué)數(shù)學(xué)與統(tǒng)計(jì)學(xué)院，廣東深圳 518060；2) 深圳大學(xué)智能計(jì)算科學(xué)研究所，廣東深圳 518060

?

【電子與信息科學(xué) / Electronics and Information Science】

基于增量非負(fù)矩陣分解的自適應(yīng)背景模型

董懷琴1，潘彬彬1，陳文勝1，徐晨2

1) 深圳大學(xué)數(shù)學(xué)與統(tǒng)計(jì)學(xué)院，廣東深圳 518060；2) 深圳大學(xué)智能計(jì)算科學(xué)研究所，廣東深圳 518060

提出一種基于增量非負(fù)矩陣分解的自適應(yīng)背景模型，以處理動(dòng)態(tài)背景變化．當(dāng)有新的數(shù)據(jù)流到達(dá)時(shí)，利用增量非負(fù)矩陣分解有效地更新背景模型．實(shí)驗(yàn)結(jié)果表明，與非負(fù)矩陣分解相比，增量非負(fù)矩陣分解不僅運(yùn)算時(shí)間更少，而且能夠提取出更好的前景．

應(yīng)用數(shù)學(xué)；非負(fù)矩陣分解；背景建模；增量學(xué)習(xí)；特征提取；滿秩分解；前景提取

背景模型是一種檢測(cè)運(yùn)動(dòng)物體的常用方法．通過將當(dāng)前幀與背景相減，可以得到前景，以此進(jìn)行物體分割、檢測(cè)和追蹤[1-5]．背景是包含靜止物體的場(chǎng)景，如房子、樹、墻壁及家具等．前景則是非靜止的物體，包括運(yùn)動(dòng)的汽車、行走或跑動(dòng)的人．由于背景隨著物體的運(yùn)動(dòng)而動(dòng)態(tài)變化，如原本靜止的汽車離開了，或者是運(yùn)動(dòng)的人靜止了，因此，需要自適應(yīng)地更新背景模型．

當(dāng)從一系列的幀之中提取背景時(shí)，由于這些幀的背景是一致的，可以認(rèn)為背景是這些幀的主要成分，而前景為稀疏成分．因此，可以采用子空間的方法，如主成分分析(principal component analysis, PCA)[6]和非負(fù)矩陣分解(non-negative matrix factorization, NMF)[7]，對(duì)一系列幀提取其主要成分．這些主要成分就是所需要的背景，通過將一幀在這些成分張成的子空間上進(jìn)行投影，再重構(gòu)回來，就可以得到這幀的背景表達(dá)．于是，前景可以通過此幀與背景的相減得到．

然而當(dāng)背景變化時(shí)，由于PCA和NMF只能處理靜態(tài)的數(shù)據(jù)，因此它們需要將所有幀重新進(jìn)行分解，這樣會(huì)非常耗時(shí)．監(jiān)控視頻數(shù)量的不斷增長(zhǎng)迫切需要高效率的自適應(yīng)背景建模算法[8-10]．Bucak等[11]提出增量子空間學(xué)習(xí)的方法，采用重構(gòu)誤差作為目標(biāo)函數(shù)，在求解過程中利用之前得到的子空間信息，自適應(yīng)地更新子空間，從而加快分解速度，有效對(duì)自適應(yīng)背景建模．然而，Bucak的方法每次只能增量地學(xué)習(xí)1幀．若需要增量學(xué)習(xí)多幀，則算法需要執(zhí)行多次，這樣就降低了算法的效率．Cao 等[12]提出利用在線非負(fù)矩陣分解(online non-negative matrix factorization, ONMF)來檢測(cè)和追蹤潛在因子．因子是隨著數(shù)據(jù)流而動(dòng)態(tài)變化的，ONMF能較好追蹤到變化的因子，成功運(yùn)用到了主題檢測(cè)．

本研究利用ONMF算法進(jìn)行動(dòng)態(tài)的背景建模，稱此方法為增量非負(fù)矩陣分解(incremental non-negative matrix factorization, INMF)．與文獻(xiàn)[11]的方法相比，INMF方法能同時(shí)處理多幀，因此具有更好的計(jì)算效率．實(shí)驗(yàn)結(jié)果表明，INMF不僅在計(jì)算時(shí)間上，而且在前景檢測(cè)上，都要優(yōu)于NMF．

1　非負(fù)矩陣分解

NMF的思想是將一個(gè)非負(fù)矩陣V近似分解為2個(gè)非負(fù)矩陣的乘積，即

Vm×n≈Wm×rHr×n

其中， Wm×r和Hr×n都是非負(fù)矩陣； r為基向量的個(gè)數(shù)，一般選擇r滿足(m+n)r

V和WH之間的誤差定義為[6]

(1)

NMF要解決如下最優(yōu)化問題

以上最優(yōu)化問題可用如下迭代公式求解[13]

文獻(xiàn)[13]證明了目標(biāo)函數(shù)(1)在上述迭代算法下是非遞增的．

2　增量非負(fù)矩陣分解

利用傳統(tǒng)NMF對(duì)數(shù)據(jù)流進(jìn)行處理是不現(xiàn)實(shí)的．假設(shè)在t時(shí)刻得到數(shù)據(jù)V, 并采用NMF算法得到如下分解：

V=WH

在t+1時(shí)刻，有新的數(shù)據(jù)U到達(dá)．因此，數(shù)據(jù)矩陣變?yōu)?/p>

引理1[12]若V=WH和V=W′H′是V的兩個(gè)滿秩分解，那么存在可逆矩陣P， 滿足W=W′P和H=P-1H′．

考慮分解

(2)

(3)

其中， P為可逆矩陣．于是，分解問題(2)轉(zhuǎn)變?yōu)?/p>

(4)

為了求解問題(4)，考慮如下分解

可得

更新規(guī)則為

3　背景模型實(shí)驗(yàn)

3.1實(shí)驗(yàn)數(shù)據(jù)庫及實(shí)驗(yàn)方法

在背景模型實(shí)驗(yàn)中，我們使用PET2001的 “dataset1_camera1” 的視頻數(shù)據(jù)庫[14]．這段視頻時(shí)長(zhǎng)2 min 2 s，共3 064幀，每幀大小為576×768．為提高計(jì)算效率，每幀采樣都降到144×192，然后排成144×192=27 648維的列向量．

其中， W+為廣義逆．重構(gòu)誤差使用Frobenius范數(shù)，即

3.2動(dòng)態(tài)背景建模結(jié)果

在第1部分實(shí)驗(yàn)中，第1次選取181～200幀及281～290幀，共30幀用NMF做訓(xùn)練，然后選取第250幀做測(cè)試．隨后新的視頻流2 781～2 790幀到達(dá)，這時(shí)背景已發(fā)生變化，此時(shí)分別用NMF和INMF做訓(xùn)練，然后用第2 800幀做測(cè)試，比較運(yùn)算時(shí)間與重構(gòu)誤差．第1次訓(xùn)練的第181幀和第2次訓(xùn)練的第2 781幀見圖1．值得注意的是，第2次訓(xùn)練時(shí)，背景已發(fā)生變化，圖1(a)中標(biāo)注車輛在圖1(b)中已消失．

第1次訓(xùn)練的兩個(gè)背景基見圖2(a)和圖2(b)．也許是因?yàn)橛?xùn)練幀里都包含前景的人，所以背景基不能很好地將人剔除出去．將測(cè)試幀投影到子空間的圖像和提取的前景見圖2(c)和圖2(d)．可見，NMF能夠提取出需要的前景圖像．

第2次訓(xùn)練時(shí)，有新的幀到達(dá)，NMF和INMF分別使用第2 781～2 790幀訓(xùn)練，提取的背景基分別見圖3(a)、圖3(b)和圖4(a)、圖4(b)．由于背景變化了，而INMF進(jìn)行加權(quán)方案，新到的幀對(duì)背景基的貢獻(xiàn)更大，所以INMF提取的背景基效果會(huì)更好一些．

圖2　第1次訓(xùn)練的結(jié)果Fig.2　The results of the first training

圖3　NMF的結(jié)果Fig.3　The results of NMF

圖4　INMF的結(jié)果Fig.4　The results of INMF

將測(cè)試幀投影到NMF訓(xùn)練出的子空間的圖像和提取的前景見圖3(c)和圖3(d)；同樣，投影到INMF訓(xùn)練出的子空間圖像和提取的前景見圖4(c)和圖4(d)．可見，INMF能很好地將前景提取出來，而NMF則留有殘影．NMF和INMF的重構(gòu)誤差與運(yùn)行時(shí)間見表1．可見，INMF具備更小的重構(gòu)誤差及更快的運(yùn)算速度．

表1　重構(gòu)誤差與運(yùn)行時(shí)間比較

3.3運(yùn)算時(shí)間與重構(gòu)誤差比較

在第2部分實(shí)驗(yàn)中，首先選取181～280幀總共100幀作為第1次訓(xùn)練，隨后新的視頻流到達(dá)，分別采用NMF和INMF對(duì)新到達(dá)的數(shù)據(jù)做第2次訓(xùn)練．新的視頻流分別選取2 781～2 800、2 781～2 820、2 781～2 840、2 781～2 860及2 781～2 880幀5種情況，然后用第2 900幀做測(cè)試，比較運(yùn)算時(shí)間與重構(gòu)誤差．此時(shí)p的取值分別為20、40、60、80和100．

NMF和INMF算法的運(yùn)行時(shí)間和重構(gòu)誤差如圖5．可見，INMF用時(shí)比NMF少，且兩個(gè)算法的運(yùn)算時(shí)間隨著幀數(shù)的增加呈線性增長(zhǎng)趨勢(shì)．同時(shí)，INMF具備更小的重構(gòu)誤差．當(dāng)幀數(shù)很少時(shí)，INMF的重構(gòu)誤差顯著低于NMF，表明INMF只需少量的新數(shù)據(jù)流即可取得不錯(cuò)的結(jié)果．在幀數(shù)增加時(shí)，NMF的重構(gòu)誤差漸趨于INMF．這說明新數(shù)據(jù)流足夠多時(shí)，兩個(gè)算法的結(jié)果比較接近．

圖5　運(yùn)行時(shí)間與重構(gòu)誤差Fig.5　Running time and reconstruction error

結(jié)　語

本研究使用INMF進(jìn)行自適應(yīng)背景建模．與靜態(tài)NMF相比，INMF能很好地根據(jù)視頻流進(jìn)行背景模型更新．通過實(shí)驗(yàn)比較，INMF能夠提取出更好的前景，并具有更短的運(yùn)算時(shí)間．下一步工作可考慮使用二維或張量非負(fù)矩陣方法進(jìn)行背景建模，這樣可以更有效地提高運(yùn)算效率，滿足視頻監(jiān)控的實(shí)時(shí)要求．

/

[1] Jeeva S，Sivabalakrishnan M．Survey on background modeling and foreground detection for real time video surveillance[J]．Procedia Computer Science，2015，50：566-571．

[2] Bouwmans T．Traditional and recent approaches in background modeling for foreground detection：an overview[J]．Computer Science Review，2014，11(12)：31-66．

[3] Cristani M，F(xiàn)arenzena M，Bloisi D，et al．Background subtraction for automated multisensory surveillance：a comprehensive review[J]．Eurasip Journal on Advances in Signal Processing，2010，43(24)：25-31．

[4] Bouwmans T， El-Baf F，Vachon B．Statistical background modeling for foreground detection： a survey[J]．Handbook of Pattern Recognition and Computer Vision，2010，4(2)：181-199．

[5] Radke R，Andra S，Al-Kofahi O，et al．Image change detection algorithms： a systematic survey[J]．IEEE Transactions on Image Processing，2005，14(3)：294-307．

[6] Jolliffe I T．Principal component analysis[M]．New York, USA: Springer-Verlag，1986．

[7] Lee D，Seung H．Learning the parts of objects by non-negative matrix factorization[J]．Nature，1999，401(6755)：788-791．

[8] Zhang Xiaoguo， Huang Tiejun，Tian Yonghong，et al．Background-modeling-based adaptive prediction for surveillance video coding[J]．IEEE Transactions on Image Processing， 2014，23(2)：769-784．

[9] Popa S，Crookes D, Miller P．Hardware acceleration of background modeling in the compressed domain[J]．IEEE Transactions on Information Forensics and Security，2013，8(10)：1562-1574．

[10] Rodriguez P, Wohlberg B．A Matlab implementation of a fast incremental principal component pursuit algorithm for video background modeling[C]// IEEE International Conference on Image Processing. Paris: IEEE, 2014：3414-3416．

[11] Bucak S，Gunsel B．Incremental subspace learning via non-negative matrix factorization[J]．Pattern Recognition，2009，42(5)：788-797．

[12] Cao Bin，Shen Dou，Sun Jiantao，et al． Detect and track latent factors with online non-negative matrix factorization[C]// Proceedings of the 20th international joint conference on Artifical intelligence. San Francisco, USA: ACM, 2007：2689-2694．

[13] Lee D，Seung H．Algorithms for non-negative matrix factorization[J]．Nips，2010, 32(6): 556-562．

[14] PETS Video Database (http://ftp.pets.rdg.ac.uk/)．

【中文責(zé)編：方圓；英文責(zé)編：木南】

2015-12-31；Revised：2016-07-01；Accepted：2016-07-07

Adaptive background modeling via incremental non-negative matrix factorization

Dong Huaiqin1， Pan Binbin1?，Chen Wensheng1，and Xu Chen2

1) College of Mathematics and Statistics, Shenzhen University, Shenzhen 518060, Guangdong Province, P. R. China 2) Institute of Intelligent Computing Science, Shenzhen University, Shenzhen 518060, Guangdong Province, P. R. China

A method for adaptive background modeling based on the incremental non-negative matrix factorization (INMF) is proposed. INMF is used to update new background models effectively when new data streams arrive. The experimental results show that, compared with non-negative matrix factorization (NMF), INMF not only takes less running time but also can be used to extract better foregrounds.

applied mathematics; non-negative matrix factorization; background modeling; incremental learning; feature extraction; full rank factorization; foreground extraction

Dong Huaiqin， Pan Binbin，Chen Wensheng, et al. Adaptive background modeling via incremental non-negative matrix factorization[J]. Journal of Shenzhen University Science and Engineering, 2016, 33(5): 511-516.(in Chinese)

TP 391

Adoi：10.3724/SP.J.1249.2016.05511

國(guó)家自然科學(xué)基金資助項(xiàng)目(11526145, 61272252, 11501377)

董懷琴 (1992—)，女，深圳大學(xué)碩士研究生．研究方向：模式識(shí)別與機(jī)器學(xué)習(xí). E-mail：1018498868@qq.com

Foundation：National Natural Science Foundation of China (11526145, 61272252, 11501377)

? Corresponding author：Lecturer Pan Binbin. E-mail: pbb@szu.edu.cn

引文：董懷琴，潘彬彬，陳文勝，等. 基于增量非負(fù)矩陣分解的自適應(yīng)背景模型[J]. 深圳大學(xué)學(xué)報(bào)理工版，2016，33(5)：511-516.