基于低秩稀疏分解的自適應運動目標檢測算法

朱 林，郝元宏，蔣秀蓉

北方自動控制技術研究所，太原 030000

1 引言

運動目標檢測是許多計算機視覺應用的第一步，例如交通監控、機器人導航、增強現實等[1]。運動目標檢測的任務就是把被稱為“前景”的運動目標區域從被稱為“背景”的場景中分離出來，為目標識別、目標跟蹤、目標行為分析提供可靠而準確的數據[2]。因此，運動目標檢測是計算機應用中十分關鍵的一步。

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

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

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

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

2 相關知識

希望結合低秩系數分解與Fused lasso模型，找到一種魯棒性和準確性更強的運動目標檢測算法。因此，首先給出低秩稀疏分解和Fused lasso模型的介紹。

2.1 低秩稀疏分解

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

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

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

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

2.2 Fused lasso模型

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

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

式中，第一個約束項可以約束元素的稀疏性，第二個約束項可以約束元素之間的平滑性。因此，Fused LASSO模型可以使元素在稀疏化的基礎上產生分段的平滑性，可以有效地去除數據中的噪聲及數據缺失等情況。在實際運動目標檢測應用中，Fused lasso能夠比lasso取得更好的效果。

3 基于低秩稀疏分解的運動目標檢測

傳統的RPCA方法使用l1范數對前景進行建模，在實際應用中并不能有效地區分目標和動態背景。為了提升檢測的準確性，本文結合空間先驗知識和稀疏先驗知識，對前景模型進行建模，定義了空間融合稀疏約束如下（Spatial fused sparse constraint）：

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

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

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

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

3.1 低秩背景矩陣估計

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

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

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

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

式中：

運用引理1，可以求得式（10）的最優解：

3.2 稀疏前景矩陣估計

對于稀疏前景矩陣估計問題，可以通過最優化下式解決：

式（13）可以轉化為如下形式：

設Q=D-Ak+1+μ-1Yk，則式（14）可以轉化為：

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

3.3 自適應參數更新策略

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

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

式中，K是用來完善λ的一個常量。在本文的實驗中，K的值被設置為2。

3.4 基于低秩稀疏分解的自適應運動目標檢測算法

本文算法步驟如下：

輸入：觀測矩陣D

輸出：前景位置矩陣E

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

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

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

步驟2.2 通過式（16）～（17）計算正則化參數 λ。

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

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

若符合，停止迭代。

步驟3輸出結果。

整個算法流程如上所示，在本文實驗中迭代停止閾值ε被設為10-7，ALM參數被設為ρ=1.5。關于ALM算法求解的更多細節請參考文獻[14]。

4 實驗結果與分析

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

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

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

圖1 I2R dataset檢測結果

圖2 CDnet dataset和UCSD dataset檢測結果

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

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

式中，TP，FP，FN分別表示真實正樣本，錯誤正樣本和錯誤負樣本。TP可以通過計算被正確檢測出的前景像素的數量得到，FP可以通過計算背景像素被錯誤檢測為前景像素的數量得到，FN指前景像素被錯誤檢測為背景像素的數量。

為了同時衡量召回率和準確率，使用F-measure對檢測結果進行評估：

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

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

5 結論

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