基于滑動窗非負矩陣分解的運動目標檢測方法

祝加祥，胡鵬程，何 璇，王營冠

(1.安徽大學 計算機科學與技術學院，安徽 合肥 230601；2.中國科學院上海微系統與信息技術研究所 中國科學院無線傳感網與通信重點實驗室，上海 200050)

基于滑動窗非負矩陣分解的運動目標檢測方法

祝加祥1，胡鵬程1，何 璇1，王營冠2

(1.安徽大學 計算機科學與技術學院，安徽 合肥 230601；2.中國科學院上海微系統與信息技術研究所 中國科學院無線傳感網與通信重點實驗室，上海 200050)

主要研究了智能視頻監控系統中的運動目標檢測算法，試圖將非負矩陣分解算法引入運動目標檢測算法中，通過非負矩陣分解算法對視頻序列的背景進行建模，使用背景差分法將當前視頻幀圖像與建立的背景模型比較獲得運動目標。針對運動目標檢測中基本非負矩陣分解批處理算法的不足，提出一種基于滑動窗非負矩陣分解的運動目標檢測算法。通過滑動窗處理控制非負矩陣分解模型中被分解矩陣的規模，降低了算法的計算復雜度和空間復雜度，并在一定程度上增加了模型的非記憶性。實驗結果表明，該算法能夠更好地自適應背景模型的動態改變，并且在視頻場景中存在光照突變和較小運動目標時具有較好的檢測效果。

非負矩陣分解；運動目標檢測；背景差分；滑動窗

0 引 言

智能視頻監控系統[1]是智能視頻分析中的一個重要應用，同時也是計算機視覺領域中一直活躍的研究課題。智能視頻監控對攝像機等視頻采集設備獲取的視頻圖像信息進行分析，試圖在一系列視頻序列中檢測出運動目標，對目標進行識別，跟蹤并對其行為進行理解并做出相應反應，最終取代傳統視頻監控中由值班人員監控攝像機的現狀。其中，運動目標檢測[2]是智能視頻監控系統的基礎，只有實時、準確、可靠地檢測出運動目標，才能保證后續目標定位、識別和行為理解等步驟的可靠性。

目前常用于智能視頻系統中的運動目標檢測方法有光流法[3]、幀差法[4]和背景差分法[5]。幀差法利用相鄰兩幀或者多幀之間的差異來提取運動目標，是一種基于時間域的運動目標檢測算法。幀差法比較簡單，計算復雜度較低，易于實現，該算法對光照的變化不敏感并且對于環境的動態改變具有很強的魯棒性。但是，幀差法不能提取出運動目標的所有像素點，只能檢測出運動目標的部分輪廓，容易出現“空洞”現象。光流法是在適當的平滑性約束條件下，根據圖像序列時空梯度估算運動場[6]，通過分析運動場的變化對運動目標和場景進行檢測和分割。光流法的優點在于光流不僅攜帶了運動物體的運動信息，而且還攜帶了有關場景三維結構的豐富信息，它能夠在不知道場景任何信息的情況下檢測出運動目標。但是采用光流法計算耗時，實時性和實用性都較差。

使用背景差分法進行運動目標檢測。首先對視頻序列中的場景進行建模得到背景模型，然后通過計算當前幀與背景模型之間的差異來獲得運動目標區域。當前幀圖像與背景模型顯著變化的區域認為有運動目標出現，變化區域的像素被標記為前景像素點以供下一步處理。背景差分法的關鍵在于背景模型的建立和更新，背景模型建立的好壞直接影響運動目標檢測率的高低。目前，常用于背景模型的建立和更新算法有單高斯背景模型[7](SGM)、混合高斯背景模型[8](GMM)等。其中，SGM在多模態場景下存在背景模型不能更好地自適應、檢測率不完整的問題；GMM能夠在一定程度上解決視頻場景中的多模態問題，但是隨著高斯分布個數的增加，計算復雜程度也隨之增加，并且在光照突變時效果也較差。

文中在非負矩陣分解批處理算法基礎上，提出一種基于滑動窗非負矩陣分解的運動目標檢測算法。通過滑動窗非負矩陣分解算法進行視頻場景背景模型建立及更新，最終使用背景差分法獲得運動目標。

1 非負矩陣分解算法原理與步驟

1.1 算法描述

非負矩陣分解算法[9-11](NMF)可以看作是解決以下問題的算法：在給定非負矩陣V的情況下，尋找兩個非負矩陣W和H使得：

V≈WH

(1)

其中，V=[v1,v2,…,vm]是n×m維的非負矩陣；W=[w1,w2,…,wr]是n×r維的非負矩陣；H=[h1,h2,…,hm]是r×m維的非負矩陣。

多元數據統計分析中，NMF可以被理解為：給定一系列的n維數據向量，這些向量作為列向量組成矩陣V∈Rn*m，這里的m是數據樣本集的大小。矩陣V被分解成兩個非負矩陣W∈Rn*r和H∈Rr*m的乘積。通常r的選擇遠遠小于n和m，因此分解后的W和H矩陣的規模都小于原始矩陣V。該過程實際上是對原始數據矩陣V的壓縮過程。

更重要的是式(1)可以重寫成兩個列向量乘積的形式：v≈Wh。其中，v和h是矩陣V和H的對應列。換句話說，每個數據向量v可以近似認為是W矩陣中列向量的線性組合，并且相應的權重是h。因此W可以看作對V進行線性組合近似的一組基向量，H可以認為是對V進行線性組合近似的系數。所以在非負矩陣分解中，W稱作是基矩陣，H稱作是系數矩陣。由于原始大規模的數據矩陣V由相對規模較小的基矩陣W來表示，因此只有當基向量能夠表示原始數據的隱含結構信息時才能得到有效的近似分解。

1.2 代價函數

為了能夠得到式(1)中對于V的近似分解，首先需要定義一個代價函數來衡量分解的近似程度。可以使用兩個非負矩陣的距離程度來構建一個代價函數用來衡量兩個矩陣的近似程度。文中使用的度量公式是測量矩陣V和WH的歐氏距離的平方，即：

(2)

矩陣V和WH的歐氏距離的平方大于等于0，當且僅當V=WH時為0。

因此將NMF問題可以轉化成在W和H非負約束下求解代價函數最小值的優化問題，問題描述如下：

在W，H≥0非負約束下，尋找W和H使得F(V‖WH)達到最小值,即

(3)

1.3 乘性迭代規則

盡管代價函數F(V‖WH)和D(V‖WH)在單一求解W和H的情況下是凸優化[12]問題，但是同時求解W和H的情況下并不是一個凸優化問題。所以通過設計一個算法來尋找式(3)的全局最小值是不切實際的。但是有很多數值優化算法可以用來求解上述問題的局部最小值。

梯度下降算法是用來解決上述優化問題最易于實現的方法，但是梯度下降算法收斂速度較慢。共軛梯度算法的收斂速度相比于梯度下降算法較快，至少在局部最小值區域很顯著，但是[13]實現起來更加復雜。另外基于梯度的優化算法的收斂性對步長的選擇比較敏感，這在大型應用場景中很不方便。因此解決上述優化問題時，在速度和實現復雜度上采取了上述兩種方法的折中：乘性迭代算法[14]，采用迭代規則分別更新W和H，在求取W的時候，固定矩陣H，然后利用W計算下一步的H，保證算法收斂快并且算法復雜度低。

以歐氏距離的平方作為代價函數時，將F(V‖WH)兩邊分別對W和H求偏導，得到:

(4)

采用梯度下降數值優化方法，以梯度方向的負方向為下降方向，分別使用ηau和δia作為梯度法的步長，也稱為學習率，得到:

(5)

梯度法中步長的選擇對算法的收斂速度影響大，當式(5)中步長選擇較大時，可能成之字形收斂甚至發散不能達到局部最小值；根據優化理論，式(5)中的學習率選取充分小的正數時，代價函數的值會逐漸減小，但是并不能保證每部迭代后的結果非負，乘性迭代規則正好能克服這個缺點。在乘性迭代規則中，只要W和H的初始值非負，在后續迭代過程中得到的W和H都為非負。為了得到乘性迭代公式，式(5)中學習率ηau和δia分別選取為：

(6)

將式(6)代入式(5)中，得到使用歐氏距離的平方作為代價函數的NMF算法乘性迭代規則為：

(7)

2 基于滑動窗非負矩陣分解運動目標檢測算法

在運動目標檢測中，通常認為一個視頻場景由背景和包含運動目標的前景組成，在攝像頭固定的情況下，一段連續視頻序列的背景基本變化不大，并且背景在視頻序列中所占的比例較大，而前景所占比例較小。NMF方法可以對數據的整體進行感知，基于此理論，可以通過NMF方法對視頻序列的背景建模，然后通過背景差法比較當前幀與背景模型之間的差異提取出運動目標。

在實際的運動目標檢測應用中，隨著視頻序列的增加，非負矩陣分解模型中被分解矩陣的規模增大，基本非負矩陣分解算法所需要的內存空間和計算時間都線性增加，這在實際應用中是不切實際的。針對基本非負矩陣分解的批處理算法的不足，以及視頻序列在時間上的連續性，之前的視頻內容對后續背景模型的影響逐漸減小等特點，提出一種基于滑動窗非負矩陣分解的運動目標檢測算法。算法步驟如下(其中矩陣運算采用Matlab語言中矩陣運算表示方式)：

(1)讀取視頻信息，視頻的總幀數為NumberOfVideo，初始化用于分解的矩陣V=[];

(2)讀取當前幀視頻，判斷當前幀序號NumberOfFrame是否大于預定的訓練樣本數量NumberOfTrain，大于，跳轉至步驟(4)；

(3)讀取第NumberOfFrame幀中的灰度圖像frame，對frame進行預處理，并轉換成列向量的形式ColFrame，將當前ColFrame加入到被分解矩陣中，即V=[V，ColFrame]；

(4)對V進行非負矩陣分解得到分解結果的基矩陣W和系數矩陣H，并進行重構得到矩陣ReconstructedData=W*H；

(5)獲取重構后的矩陣ReconstructedData的最后一列作為背景模型信息，重構成圖像形式BackgroundFrame；

(6)當前幀圖像frame與BackgroundFrame進行比較提取出運動目標，并進行后續處理；

(7)讀取下一幀圖像，如果NumberOfFrame大于NumberOfVideo，算法結束；

(8)讀取第NumberOfFrame幀中的灰度圖像frame，對frame進行預處理，并轉換成列向量的形式ColFrame，將當前ColFrame以滑動窗的形式加入到被分解矩陣中，即V=[V(2:end,:)，ColFrame],跳轉至步驟(4)。

3 實驗結果

為了驗證基于滑動窗非負矩陣分解的運動目標檢測方法的性能，使用2段視頻序列進行實驗測試，同時將其與幀差法、SGM算法和GMM算法進行對比。實驗平臺為Matlab2012b，處理器為Intel(R)Core(TM)i5-2450MCPU@2.5GHz。采用的基本非負矩陣分解方法中，基矩陣W和系數矩陣H隨機初始化為非負正數，迭代終止條件選取為不超過預定的迭代次數，在該實驗中預定迭代次數選取為10；滑動窗大小為20；幀差法中的閾值設置為25。SGM算法中參數選取為：K=15，α=0.02；GMM算法中的參數選取為：K=3，β=0.2，τ=0.8，c=2.9，T=15，α=0.02。

實驗1中使用的視頻數據為Matlab2012b中自帶的道路交通監控視頻，視頻中的運動目標主要為行駛的車輛和光照的變化。對比測試結果如圖1所示。其中，圖(a)～(c)為視頻序列中第30、46、77幀原始視頻圖像;圖(d)～(f)為采用幀差法得到的前景圖像;圖(g)～(i)為使用SGM算法得到的前景圖;圖(j)-(l)為使用GMM算法得到的前景圖;圖(m)～(o)為使用基于滑動窗非負矩陣分解得到的前景圖。

圖1 實驗1結果對比圖

通過實驗結果可知，在視頻場景相對簡單、攝像頭固定的情況下，基于滑動窗非負矩陣分解的運動目標檢測算法能夠在一定程度上有效地檢測出運動目標。例如在第34幀中，當運動目標較小時也能比較完整地檢測出運動車輛。相較于幀差法，滑動窗NMF算法能夠得到更完整的運動目標，并且能夠有效地抑制光照變化產生的噪聲。在第46幀和第77幀時，視頻序列中光照發生整體性突變，SGM和GMM均無法很好地抑制噪聲，導致大量的背景信息被誤判為前景目標。NMF算法作為一種盲源分離算法，能夠提取出觀測數據中的主要成分，單幀圖像的突變對模型的影響不大，基于滑動窗NMF的運動目標檢測算法在整體光照發生突變時仍能正確地檢測出運動目標。

為了更好地驗證基于滑動窗非負矩陣分解的運動目標檢測方法的性能，選取了一段視頻場景比較復雜的視頻序列對滑動窗NMF算法進行實驗測試，并且將其與幀差法、SGM算法和GMM進行對比。實驗所選取的視頻為一段合成的仿真視頻，視頻中運動目標包括行駛的車輛、跳躍的行人以及爬行的貓，并且視頻場景中出現了樹葉搖晃和光照閃爍變化等多模態現象。圖2為對比實驗結果圖。其中，圖(a)～(c)為視頻序列中第245、285、473幀原始視頻圖像;圖(d)～(f)為采用幀差法得到的前景圖像;圖(g)～(i)為使用SGM算法得到的前景圖;圖(j)-(l)為使用GMM算法得到的前景圖;圖(m)～(o)為使用基于滑動窗非負矩陣分解得到的前景圖。

從實驗結果對比圖來看，滑動窗NMF算法得到的運動目標比幀差法檢測結果更加完整。在視頻場景中搖曳的樹枝和閃爍的燈光造成的運動目標噪聲，基于滑動窗NMF的檢測結果都能很好地處理，檢測效果與GMM算法接近。因此，在復雜的環境下，基于滑動窗非負矩陣分解的運動目標檢測方法能夠在一定程度上抑制光照閃爍變化等多模態現象帶來的噪聲，具有較好的檢測效果。

4 結束語

在非負矩陣分解批處理算法的基礎上進行改進，使用滑動窗非負矩陣分解算法對視頻場景中背景進行建模和更新，然后使用背景差分法獲得運動目標。該算法有效降低了基本非負矩陣分解批處理算法的計算復雜度和空間復雜度，通過對比實驗可知，該算法能更好地自適應背景模型的動態改變，且在視頻場景存在光照突變和較小運動目標時都具有較好的檢測效果。

圖2 實驗2結果對比圖

[1] 黃斯茜,李 光.智能視頻監控系統運動目標檢測技術研究綜述[J].信息通信,2012(4):57-58.

[2] 侯宏錄,李寧鳥,劉迪迪,等.智能視頻監控中運動目標檢測的研究[J].計算機技術與發展,2012,22(2):49-52.

[3] 楊葉梅.基于改進光流法的運動目標檢測[J].計算機與數字工程,2011,39(9):108-110.

[4] 王孝艷,張艷珠,董慧穎,等.運動目標檢測的三幀差法算法研究[J].沈陽理工大學學報,2011,30(6):82-85.

[5] 汪 沖,席志紅,肖春麗.基于背景差分的運動目標檢測方法[J].應用科技,2009,36(10):16-18.

[6]KaehlerA,BradskiG.LearningOpenCV[M].[s.l.]:O'ReillyMedia,Inc.,2014.

[7] 王小平,張麗杰,常 佶.基于單高斯背景模型運動目標檢測方法的改進[J].計算機工程與應用,2009,45(21):118-120.

[8] 馬義德,朱望飛,安世霞,等.改進的基于高斯混合模型的運動目標檢測方法[J].計算機應用,2007,27(10):2544-2546.

[9] 李 樂,章毓晉.非負矩陣分解算法綜述[J].電子學報,2008,36(4):737-743.

[10]AlbrightR,CoxJ,DulingD,etal.Algorithms,initializations,andconvergenceforthenonnegativematrixfactorization[R].USA:NorthCarolinaStateUniversity,2006.

[11]YangS,YiZ,YeM,etal.Convergenceanalysisofgraphregularizednon-negativematrixfactorization[J].IEEETransactionsonKnowledgeandDataEngineering,2014,26(9):2151-2165.

[12]BoydS,VandenbergheL.凸優化[M].王書寧,譯.北京:清華大學出版社,2013.

[13] 伏思華,姜廣文,龍學軍,等.隨機并行梯度下降圖像匹配方法[J].實驗力學,2013,28(6):663-668.

[14]MaoYijun,ZhaoZhijin,ShangJunna.Blindsourceseparationalgorithmsbasedonnonnegativematrixfactorizationusingdifferentlearningrates[J].HansJournalofWirelessCommunications,2015,5(5):91-97.

Moving Target Detection Method Based on Non-negative Matrix Factorization of Sliding Window

ZHU Jia-xiang1,HU Peng-cheng1,HE Xuan1,WANG Ying-guan2

(1.School of Computer Science and Technology,Anhui University,Hefei 230601,China; 2.Key Lab of Wireless Sensor Network and Communication,Shanghai Institute of Microsystem and Information Technology,Chinese Academy of Science,Shanghai 200050,China)

The algorithms of detecting the moving objects in the intelligent video surveillance system are mainly studied.The Non-negative Matrix Factorization (NMF) algorithm is introduced into the moving target detection algorithm for modeling the background of a video sequences,and the background subtraction method is used to obtain the moving target by comparing the differences of the current video frame and the background model.In order to solve the problem of the NMF algorithm with a batch process,a moving target detection algorithm of NMF based on sliding window is put forward,which controls the size of the decomposed matrix in NMF matrix decomposition model by adjusting the length of the sliding window.The proposed algorithm can reduce the computation and space complexity,and to some extent,it can increase non-memory characteristic of the model.The experiments show that the proposed method can adaptively change the background model and has better detection effect when there is light change and small moving target in video scene.

non-negative matrix factorization;moving object detection;background difference;sliding window

2015-06-03

2015-09-23

時間：2017-01-04

安徽省科技攻關強警專項(1101b0403030);中國科學院上海微系統與信息技術橫向研發基金課題

祝加祥(1991-)，男，碩士，研究方向為圖像處理。

http://www.cnki.net/kcms/detail/61.1450.TP.20170104.1017.008.html

TP391.9

A

1673-629X(2017)01-0020-05

10.3969/j.issn.1673-629X.2017.01.005