基于低秩稀疏分解的自適應(yīng)運(yùn)動目標(biāo)檢測算法

朱 林，郝元宏，蔣秀蓉

北方自動控制技術(shù)研究所，太原 030000

1 引言

運(yùn)動目標(biāo)檢測是許多計(jì)算機(jī)視覺應(yīng)用的第一步，例如交通監(jiān)控、機(jī)器人導(dǎo)航、增強(qiáng)現(xiàn)實(shí)等[1]。運(yùn)動目標(biāo)檢測的任務(wù)就是把被稱為“前景”的運(yùn)動目標(biāo)區(qū)域從被稱為“背景”的場景中分離出來，為目標(biāo)識別、目標(biāo)跟蹤、目標(biāo)行為分析提供可靠而準(zhǔn)確的數(shù)據(jù)[2]。因此，運(yùn)動目標(biāo)檢測是計(jì)算機(jī)應(yīng)用中十分關(guān)鍵的一步。

常見的運(yùn)動目標(biāo)檢測算法有差分法、光流法、背景減除法等。其中背景減除法是最主要的一類方法。在此類方法中，背景通常被假設(shè)是靜止的，通過比較當(dāng)前圖像與背景模型的不同來得到前景。在過去的幾十年內(nèi)，國內(nèi)外學(xué)者們建立了一系列的背景建模方法，包括單高斯模型[3]、混合高斯模型[4]、非參數(shù)核模型[5]、隱馬爾科夫模型[6]、線性回歸模型[7]、ViBe背景減除[8]方法等。然而，實(shí)際場景下的運(yùn)動目標(biāo)檢測問題，往往受到背景雜波、噪聲、光照變化、場景中存在的陰影等因素的影響，現(xiàn)有的運(yùn)動目標(biāo)檢測算法難以處理各種復(fù)雜的場景[9]。

近幾年，魯棒主成分分析理論（Robust Principle Component Analysis，RPCA）[10-11]出現(xiàn)，其在運(yùn)動目標(biāo)檢測領(lǐng)域受到了越來越多的關(guān)注。其核心思想在于在攝像頭靜止的條件下，將各視頻幀作為列向量依次排列形成視頻矩陣，由于視頻矩陣中的背景一般變化不大，所以背景應(yīng)具有低秩特性；前景目標(biāo)一般占整個圖像的一小部分，其具有稀疏性且不具有低秩性，具有離群值的特征。此種方法可以把視頻圖像分解為低秩背景和稀疏前景，與傳統(tǒng)方法相比在算法的準(zhǔn)確性和魯棒性上具有十分明顯的優(yōu)勢。與先前的背景建模方法相比，低秩模型能夠?qū)υ肼?、?shù)據(jù)缺失、緩慢的光照變化等退化因素保持魯棒，對于前景目標(biāo)的運(yùn)動方式無特殊要求，能夠處理非剛體對象，并且需要調(diào)節(jié)的參數(shù)較少。經(jīng)過一系列的實(shí)驗(yàn)驗(yàn)證，魯棒PCA模型取得了較好的靜態(tài)背景建模效果，這為RPCA模型在運(yùn)動目標(biāo)檢測問題中的應(yīng)用奠定了良好的基礎(chǔ)。

然而，在實(shí)際應(yīng)用中RPCA仍然有一些不足。首先，RPCA模型使用l1范數(shù)來約束矩陣元素的稀疏性，l1范數(shù)并未考慮矩陣元素之間內(nèi)在的空間相關(guān)聯(lián)系。在處理復(fù)雜的場景時，傳統(tǒng)RPCA模型的性能會受到極大影響。實(shí)際上，前景目標(biāo)的像素之間往往是空間連續(xù)的。如果能把此先驗(yàn)知識引入到RPCA模型中，其準(zhǔn)確性和魯棒性會大大提高。其次，由于RPCA模型對參數(shù)十分敏感，并且沒有一個參數(shù)可以很好地處理所有場景，因此其正則化參數(shù)λ的選取是十分困難的。

為解決以上問題，本文提出了一種新的運(yùn)動目標(biāo)檢測算法。通過把空間融合稀疏約束引入到RPCA模型中，約束了前景模型的稀疏性和空間連續(xù)性；同時，為了解決正則化參數(shù)的選取問題，本文設(shè)計(jì)了一種自適應(yīng)參數(shù)估計(jì)方法。最后，在低秩稀疏分解的框架下，使用基于交替迭代思想的增廣拉格朗日乘子法對新的目標(biāo)函數(shù)進(jìn)行求解，得到稀疏前景矩陣。在公共數(shù)據(jù)集上的大量實(shí)驗(yàn)證明，在處理動態(tài)背景等復(fù)雜環(huán)境時，本文算法的魯棒性和準(zhǔn)確性有很大提高。

2 相關(guān)知識

希望結(jié)合低秩系數(shù)分解與Fused lasso模型，找到一種魯棒性和準(zhǔn)確性更強(qiáng)的運(yùn)動目標(biāo)檢測算法。因此，首先給出低秩稀疏分解和Fused lasso模型的介紹。

2.1 低秩稀疏分解

低秩稀疏方法在計(jì)算機(jī)視覺中有著很廣泛的應(yīng)用。其最經(jīng)典的方法是RPCA方法，受低秩矩陣分析的相關(guān)研究啟發(fā)，文獻(xiàn)[10]提出通過主元追求（Principal Component Pursuit，PCP）求解RPCA問題，其核心思想在于將視頻矩陣分解為一個低秩矩陣和一個稀疏矩陣。

矩陣D對應(yīng)觀測矩陣；矩陣E對應(yīng)于分解后矩陣的稀疏部分，即視頻數(shù)據(jù)中的目標(biāo)部分；矩陣A對應(yīng)于分解后矩陣的低秩部分，其表示原始觀測數(shù)據(jù)中恢復(fù)出來的低秩數(shù)據(jù)部分，即背景部分。根據(jù)背景矩陣A與前景矩陣E分別具有低秩與稀疏的特性，可以將視頻矩陣分解成為低秩矩陣和稀疏矩陣兩部分，其具體原理如下：

式中，‖A‖*為矩陣A的核范數(shù)，即矩陣所有奇異值之和；‖E‖1為矩陣E的l1范數(shù)，即矩陣所有元素絕對值之和。通過求解此模型，可以分解出低秩背景矩陣A和稀疏前景矩陣E。

但在實(shí)際應(yīng)用中，視頻序列圖像本身包含動態(tài)背景（如樹葉晃動、水面波紋等），在時空域分布上呈現(xiàn)為類似噪聲特性，l1范數(shù)往往不能對前景目標(biāo)很好地建模?？紤]到前景目標(biāo)具有很強(qiáng)的空間相關(guān)性，即使視頻圖像受到噪聲影響或動態(tài)背景的干擾，前景目標(biāo)區(qū)域內(nèi)的相近像素之間的灰度值也通常不會有很大變化，其整體呈現(xiàn)線性關(guān)系。因此希望利用前景目標(biāo)的空間連續(xù)性先驗(yàn)信息對前景目標(biāo)進(jìn)行建模，結(jié)合矩陣低秩稀疏分解框架，提出一種魯棒性和準(zhǔn)確性更強(qiáng)的運(yùn)動目標(biāo)檢測算法。

2.2 Fused lasso模型

Lasso[12]（Least absolute shrinkage and selection operator）將l1范數(shù)作為懲罰項(xiàng)加入最小二乘回歸，l1范數(shù)懲罰項(xiàng)對向量中所有元素的絕對值和進(jìn)行懲罰，其產(chǎn)生的結(jié)果一定是稀疏的。傳統(tǒng)RPCA方法的稀疏矩陣就是通過求解LASSO問題得到的：

LASSO模型只能誘導(dǎo)元素的稀疏性，為了同時誘導(dǎo)元素的稀疏性和元素之間差異的稀疏性，R.Tibshirani等人提出了Fused LASSO 模型[13]：

式中，第一個約束項(xiàng)可以約束元素的稀疏性，第二個約束項(xiàng)可以約束元素之間的平滑性。因此，F(xiàn)used LASSO模型可以使元素在稀疏化的基礎(chǔ)上產(chǎn)生分段的平滑性，可以有效地去除數(shù)據(jù)中的噪聲及數(shù)據(jù)缺失等情況。在實(shí)際運(yùn)動目標(biāo)檢測應(yīng)用中，F(xiàn)used lasso能夠比lasso取得更好的效果。

3 基于低秩稀疏分解的運(yùn)動目標(biāo)檢測

傳統(tǒng)的RPCA方法使用l1范數(shù)對前景進(jìn)行建模，在實(shí)際應(yīng)用中并不能有效地區(qū)分目標(biāo)和動態(tài)背景。為了提升檢測的準(zhǔn)確性，本文結(jié)合空間先驗(yàn)知識和稀疏先驗(yàn)知識，對前景模型進(jìn)行建模，定義了空間融合稀疏約束如下（Spatial fused sparse constraint）：

式中，D(?)表示在矩陣空間鄰域上的差分操作，c是平衡空間平滑約束和稀疏約束強(qiáng)度的正則化系數(shù)。誘導(dǎo)矩陣X中元素的稀疏性，誘導(dǎo)矩陣X中元素的空間平滑度。

假設(shè)待檢測視頻序列為M∈?m×n×p，其中m、n分別是每幀圖像的長和寬，p是視頻序列的幀數(shù)。把每一幀拉伸成一個列向量，得到觀測矩陣D∈?mn×p。通過把空間融合稀疏約束引入到低秩稀疏分解模型中，得到待解決的目標(biāo)式：

式（7）可以通過增廣拉格朗日乘子法[14]進(jìn)行求解。其增廣拉格朗日方程為：

式中，Y是拉格朗日乘子，μ是懲罰參數(shù)。為保證求解過程的效率和準(zhǔn)確性，采用交替方向法求解式（8）。

3.1 低秩背景矩陣估計(jì)

首先，固定前景矩陣E，低秩背景矩陣A可以通過優(yōu)化下式求解：

式（9）可以表示為如下形式：

式（10）可以通過軟閾值收縮算法[15]求解。下面介紹引理1。

引理1給定一個矩陣W∈Rmn×p，矩陣W 的奇異值分解為，則奇異值收縮算子定義為：

式中：

運(yùn)用引理1，可以求得式（10）的最優(yōu)解：

3.2 稀疏前景矩陣估計(jì)

對于稀疏前景矩陣估計(jì)問題，可以通過最優(yōu)化下式解決：

式（13）可以轉(zhuǎn)化為如下形式：

設(shè)Q=D-Ak+1+μ-1Yk，則式（14）可以轉(zhuǎn)化為：

式（15）的形式與式（5）中的Fused lasso問題相似，可以通過SLEP package[16]快速求解。

3.3 自適應(yīng)參數(shù)更新策略

當(dāng)算法框架搭建完成后，如何選擇合適的參數(shù)是一個重要的問題。參數(shù)λ控制著空間融合稀疏約束的強(qiáng)度，即對前景矩陣空間連續(xù)性和稀疏性的約束；參數(shù)c用來平衡空間連續(xù)性約束和稀疏性約束的強(qiáng)度。文獻(xiàn)[17]提出了一種在線性回歸模型中的參數(shù)估計(jì)方法，受此啟發(fā)，設(shè)計(jì)了一種自適應(yīng)參數(shù)更新策略以提升算法的魯棒性。

本文算法中參數(shù)λ的選擇問題與基追蹤去噪問題類似[18]。受此啟發(fā)，首先根據(jù)實(shí)驗(yàn)經(jīng)驗(yàn)把λ的值設(shè)置為，其中M對應(yīng)于觀測矩陣中元素的數(shù)量，σ是需要估計(jì)的尺度參數(shù)。同時考慮算法的計(jì)算復(fù)雜度和自適應(yīng)性能，選用了一種基于絕對中位差的策略來估計(jì)σ：

式中，K是用來完善λ的一個常量。在本文的實(shí)驗(yàn)中，K的值被設(shè)置為2。

3.4 基于低秩稀疏分解的自適應(yīng)運(yùn)動目標(biāo)檢測算法

本文算法步驟如下：

輸入：觀測矩陣D

輸出：前景位置矩陣E

步驟1初始化：A=E=0，Y=0

步驟2交替迭代求解矩陣A和E

步驟2.1通過式（10）～（13）估計(jì)背景矩陣A。

步驟2.2 通過式（16）～（17）計(jì)算正則化參數(shù) λ。

步驟2.3通過式（13）～（15）估計(jì)前景位置矩陣E。

步驟2.4檢查是否符合算法收斂條件：

若符合，停止迭代。

步驟3輸出結(jié)果。

整個算法流程如上所示，在本文實(shí)驗(yàn)中迭代停止閾值ε被設(shè)為10-7，ALM參數(shù)被設(shè)為ρ=1.5。關(guān)于ALM算法求解的更多細(xì)節(jié)請參考文獻(xiàn)[14]。

4 實(shí)驗(yàn)結(jié)果與分析

在本章，為了證明本文算法的有效性，將本文算法與7種常用的算法比較，分別是DECOLOR[19]，PCP[10]，VBRPCA[20]，PRMF[21]，MoG-RPCA[22]，ViBe[8]和 MoG[4]。其中，前五種算法是近幾年提出的基于低秩稀疏分解的算法，后兩種算法是工程實(shí)踐中常用的有效算法。為了公平比較，所有的算法參數(shù)都以原作者給出的最佳參數(shù)設(shè)置。實(shí)驗(yàn)視頻均來自于公共數(shù)據(jù)集I2R dataset[23]，CDnet dataset[24]和 UCSD dataset[25]。在實(shí)驗(yàn)中，選取每段視頻中帶有前景目標(biāo)的48幀圖片，并以最后一幀的檢測結(jié)果作為比較。

圖1使用了來自I2R數(shù)據(jù)集的7個視頻序列進(jìn)行測試。I2R數(shù)據(jù)集包含一系列具有動態(tài)背景和靜止背景的視頻序列，它常被用作前景背景分離問題的基準(zhǔn)數(shù)據(jù)集。“Boostrap”“Hall”“Lobby”和“Shopping Mall”描述了具有地面反光的室內(nèi)擁擠場景。從檢測結(jié)果可以看出，本文算法可以消除大部分的陰影；由于引入了馬爾科夫隨機(jī)場，DECOLOR方法傾向于提取大的前景區(qū)域，其檢測結(jié)果無法消除陰影；VBRPCA、PRMF和MoGRPCA是基于概率的RPCA方法，其仍然不能完整去除陰影；ViBe檢測出的前景目標(biāo)不夠完整；PCP和MoG則產(chǎn)生了大量虛警。視頻序列“Escalator”“Fountain”和“Water Surface”是具有動態(tài)背景的場景。只有本文算法和DECOLOR方法可以消除動態(tài)背景的影響，但DECOLOR方法會使多個相近的目標(biāo)連成一起，從而產(chǎn)生大量虛警；本文算法能夠在消除動態(tài)背景影響的基礎(chǔ)上檢測出準(zhǔn)確的前景。另外，對于目標(biāo)緩慢移動的情形（water surface），只有本文算法可以檢測出準(zhǔn)確的前景目標(biāo)。

為了進(jìn)一步證明算法的優(yōu)越性，從CDnet和UCSD數(shù)據(jù)集中選擇了5個具有較大動態(tài)背景的視頻序列進(jìn)行實(shí)驗(yàn)，這些視頻序列比I2R數(shù)據(jù)集更具有挑戰(zhàn)性。如圖2所示，視頻序列“Birds”描述了海鳥在海岸邊走過，具有十分劇烈的動態(tài)背景。不難看出，只有本文算法檢測出了準(zhǔn)確前景，其他七種算法均不能處理此種情況。在視頻序列“Bottle”的檢測結(jié)果中，同樣只有本文算法取得了較好的效果；ViBe算法雖然消除了動態(tài)背景的影響，但也丟失了大量前景像素；DECOLOR算法的檢測結(jié)果則在前景目標(biāo)周圍檢測出了大片的錯誤區(qū)域；其他幾種算法均不能消除水波影響。對于視頻序列“Boats”“Rain”和“Fall”，相比其他幾種算法，本文算法能夠在徹底消除動態(tài)背景的情況下檢測出較為準(zhǔn)確的前景區(qū)域，取得了較好的效果。

圖1 I2R dataset檢測結(jié)果

圖2 CDnet dataset和UCSD dataset檢測結(jié)果

表1 圖1和圖2中檢測結(jié)果的F-measure值（最高值：加粗，次高值：下劃線）

為了定量評估算法結(jié)果，使用召回率（recall）和準(zhǔn)確率（precision）評估前景檢測的準(zhǔn)確性：

式中，TP，F(xiàn)P，F(xiàn)N分別表示真實(shí)正樣本，錯誤正樣本和錯誤負(fù)樣本。TP可以通過計(jì)算被正確檢測出的前景像素的數(shù)量得到，F(xiàn)P可以通過計(jì)算背景像素被錯誤檢測為前景像素的數(shù)量得到，F(xiàn)N指前景像素被錯誤檢測為背景像素的數(shù)量。

為了同時衡量召回率和準(zhǔn)確率，使用F-measure對檢測結(jié)果進(jìn)行評估：

如表1所示，本文算法在大部分視頻序列中取得了最高或者次高的F-measure值，并且得到了最高的平均F-measure值。相比其他算法，本文算法在每個視頻序列中均取得了最高的準(zhǔn)確率。對于一些室內(nèi)擁擠場景（如Bootstrap、Shopping Hall），本文算法未取得最高的F-measure值，這是因?yàn)橛捎诳臻g融合稀疏約束的引入，一些趨于靜止的目標(biāo)會被消除掉，從而降低了召回率。DECOLOR方法的平均F-measure值僅次于本文算法，其檢測結(jié)果在大部分序列中取得了值最高的召回率，但是由于該方法會產(chǎn)生大量虛警，其準(zhǔn)確率會相對較低。其他六種算法在個別視頻序列中有較好的表現(xiàn)，但綜合表現(xiàn)均不如本文算法。

本文算法代碼使用Matlab編寫，在臺式計(jì)算機(jī)上運(yùn)行，配置為3.6 GHz Inter i7 CPU及4 GB RAM。由于RPCA相關(guān)的方法是批處理的算法，為了對RPCA相關(guān)的方法進(jìn)行運(yùn)行效率對比，本文使用100幀圖像來對算法進(jìn)行測試：在分辨率為320×240的情況下，本文算法需要182 s，DEC需要176 s，PCP為197 s，VBRPCA為72 s，PRMF 為 69 s，MoG-RPCA 為 83 s；在分辨率為160×120的情況下，算法運(yùn)算時間分別為42 s，19 s，32 s，18 s，15 s，22 s。

5 結(jié)論

RPCA方法被廣泛應(yīng)用于目標(biāo)檢測應(yīng)用中，但是仍有一些問題需解決。為提高算法的魯棒性和準(zhǔn)確性，本文提出了一種基于低秩稀疏分解的運(yùn)動目標(biāo)檢測算法。首先，使用空間融合范數(shù)對前景像素的空間連續(xù)性和稀疏性進(jìn)行約束，使前景模型更符合實(shí)際情況。其次，提出了一種自適應(yīng)參數(shù)更新策略，使算法的魯棒性更強(qiáng)。大量實(shí)驗(yàn)證明，相比傳統(tǒng)方法，本文算法的性能有很大提高。特別是在處理動態(tài)背景等復(fù)雜環(huán)境時，本文算法的魯棒性和準(zhǔn)確性均比傳統(tǒng)方法優(yōu)越。