時空RPCA在復雜場景下的運動目標檢測

張超婕，余 勤

(四川大學 電氣信息學院，四川 成都 610065)

0 引 言

在計算機視覺應用中，數據的維度通常非常高。主成分分析(PCA)[1]是一種有效降低維數的方法。然而，PCA對于異常點和稀疏大噪聲的數據非常敏感。為解決此問題，Candes等[2]提出魯棒主成分分析(RPCA)，該模型將觀測數據利用原始數據矩陣的低秩性和誤差矩陣的稀疏性分為低秩背景部分和稀疏前景部分。RPCA模型廣泛應用于圖像去噪、視頻處理和生物信息等領域[3-5]。但RPCA模型中核范數并不是秩函數的最佳近似。為更準確刻畫低秩背景部分，He等[6]根據矩陣的非凸加權核范數能更準確地逼近矩陣的秩函數，提出了WMPCA模型。然而該模型并未考慮到時間和空間上的連續性，使得復雜背景下運動目標的檢測效果不理想。Zhou等[7]注意到運動目標具有區域連續性，因此在RPCA模型的基礎上加入該先驗知識提出了DECOLOR模型，雖然分割性能得到提高，但該模型嚴格的平滑約束使得運動目標檢測不完整。為了保留高維空間的局部幾何結構，研究者們提出了圖的降維方法。Yan等[8]提出了圖嵌入框架模型，可將一些經典的降維算法如PCA、LDA和LPP等嵌入到該框架中。據此Jiang等[9]提出了圖拉普拉斯PCA(GLRPCA)，但該模型對數據損壞或異常點非常敏感。

本文提出一種基于非凸加權核范數的時空低秩RPCA算法。首先將RPCA模型中核范數替換為非凸加權核范數對低秩背景矩陣進行約束。其次構造觀測矩陣的時空圖，通過計算時空圖拉普拉斯算子以得到局部相似性。在改進RPCA算法的基礎上融入時空圖拉普拉斯正則項以提高模型對噪聲和動態背景的魯棒性。最后用自適應懲罰項線性化交替方向法[10](LADMAP)求解出本文提出的模型。

1 魯棒主成分分析及相關研究

1.1 預備知識

定義2[12]加權奇異收縮算子T。在矩陣D∈Rm×n中，D可以通過奇異值分解為D=UΣV，Σ=Diag({σi(D),1≤i≤n})。 對于任意的v>0,加權奇異值收縮算子T(D,W) 可以表示為

T(D,W)=Udiag(σi(D)-λωi)+VT

(1)

其中，ωi(i=1,2,…,n) 是g(·)的次梯度，σi(i=1,2,…,n) 是D的第i個奇異值。對于任意a∈R，(t-a)+=max(t-a,0)。

引理1 非凸加權核范數求解。對于任意v>0,W=diag(w)，給定矩陣X，Y∈Rm×n(n

(2)

Sτ(X)=sgn(Y)·max(|Y|-τ,0)

(3)

1.2 魯棒主成分分析(RPCA)

為克服主成分分析(PCA)在前景檢測應用中的缺陷，根據稀疏矩陣對大噪聲和異常點具有魯棒性的特點,提出魯棒主成分分析模型(RPCA)。將n幀圖像組成的觀測矩陣表示為D=[d1,d2,…dn]∈Rm×n，其中di表示第i幀圖像矢量化的列向量，每幀圖像有m個像素點。魯棒主成分分析模型(RPCA)認為可將觀測矩陣D分解成低秩背景矩陣B∈Rm×n和稀疏前景矩陣F∈Rm×n。 其模型如下所示

(4)

但由于上式的求解是一個非確定性多項式難題(NP-Hard)，故引入凸優化方法：核范數是矩陣秩的包絡，而矩陣中l1范數是l0范數的凸包，故可以將式(4)松弛優化為式(5)，如下所示

(5)

通過最小化上式可以有效分離出視頻的前景和背景。雖然RPCA模型對異常點具有魯棒性，但是由于該模型采用l1范數去表征運動目標的稀疏矩陣，并沒有考慮到運動目標的時空連續性，因此在復雜背景下運動目標的檢測效果不佳。

1.3 拉普拉斯特征映射

傳統的矩陣分解模型很難將運動目標從復雜背景中分離出來。而拉普拉斯特征映射(LE)[14]在一定程度上保留了局部信息，并在低維空間中最大化數據集內部流形的平滑性，使得對誤差噪聲或離群值不太敏感，具有很好的穩定性。對于數據集Y={y1,y2,…yn}，其目標函數定義如下

(6)

其中，Wij表示近鄰點之間的權值，用于度量yi與yj之間的相似性。其中Wij有k近鄰和ε近鄰兩種形式

(7)

或

(8)

其中，ε中為大于0的常數，N(xi)表示數據集中距離xi最近的k個鄰居的集合。σ為熱核參數，通過熱核函數可知，當兩個點間距越小時，Wij值越大，即映射到低維空間時兩個點越接近。化簡式(6)可得

(9)

2 模型的建立及其求解

根據上部分理論的鋪墊，本文得到以下模型

(10)

2.1 時空低秩正則化

由于傳統的RPCA模型缺乏結構信息，因此對于復雜背景場景運動目標檢測效果較差。通過對低秩背景矩陣B實施時空約束以更有效處理該問題。

構造GT=(D,WT) 為時間圖，其中頂點d為觀測矩陣D的某一幀圖像，WT表示鄰接矩陣。該圖采用k近鄰法構造。首先根據歐幾里德距離搜索所有列的最近的k個鄰居，其中每個節點都與最近的鄰居連接。對于時間圖GT，WT是包含所有成對相似性的wij矩陣

(11)

其中，σ為熱核因子，將其計算為節點之間的平均距離。其正則化約束由下式給出

(12)

得到歸一化時間圖拉普拉斯矩陣ΦT

ΦT(i,j)ij=A-1/2(A-W)A-1/2=I-A-1/2WA-1/2

(13)

GS=(D′,WS) 為空間圖，其中頂點為觀測矩陣D的某一行，WS表示行矩陣間鄰接矩陣。空間圖GS編碼了空間位置之間的相似性。對于空間圖的拉普拉斯算子的構造，選擇在觀測矩陣D的補丁級上實施平滑，對于矩陣D第一幀中的每個像素，采用一個大小為u2的補丁。同理得到空間拉普拉斯矩陣ΦS。

2.2 改進RPCA算法

模型(10)本質上為凸優化問題，故采用增廣拉格朗日乘子法ALM求解，構造的增廣拉格朗日函數如下式

(14)

其中，X,Y,Z∈Rm×n為拉格朗日乘子,μ>0為懲罰因子，<·>為矩陣內積。該模型采用自適應懲罰項線性化交替方向法(LADMAP)進行求解，具體求解方法為：每次迭代只更新一個變量且固定其它所有變量。相對于傳統的交替方向法而言，該算法只需要引入輔助變量，在減少計算量的同時提高了計算精度。其求解過程如下。

固定F、L、H、X、Y、Z、μ，更新背景矩陣B

(15)

算法1：低秩背景矩陣估計

輸入：μ，觀測矩陣D∈Rm×n，稀疏前景矩陣F∈Rm×n

輸出：Bk+1

初始化：k=0,Bk=0

迭代：

(1)根據引理1更新Bk+1

(16)

固定B、L、H、X、Y、Z、μ，更新目標矩陣F

(17)

根據引理2，可得到F的封閉解為

(18)

固定B、F、H、X、Y、Z、μ，更新時間低秩矩陣L

(19)

由上式為光滑函數，采用投影共軛梯度法求出L封閉解為

(20)

固定B、F、L、X、Y、Z、μ，更新空間低秩矩陣H

(21)

同理用投影共軛梯度法求出L封閉解為

(22)

固定B、F、L、H、μ，更新拉格朗日乘子X、Y、Z

Xk+1=Xk+μk(D-Bk+1-Fk+1)

(23)

Yk+1=Yk+μk(Bk+1-Lk+1)

(24)

Zk+1=Zk+μk(Bk+1-Hk+1)

(25)

固定B、F、L、H、X、Y、Z，更新懲罰因子μ

μk+1=min(ρμk,μmax)

(26)

其中，ρ為常數。根據KKT條件，其收斂條件如下

(27)

算法2：式(10)模型求解算法

輸入：D∈Rm×n,λ,γ1,γ2,ΦS,ΦT

輸出：B，F

初始化：k=0,B0=F0=L0=H0=0,X0=Y0=Z0=0, μ0=0.1,μmax=1010,ρ=1.1,ε=10-4,ρ=1.1

迭代：

(5)Xk+1=Xk+μk(D-Bk+1-Fk+1)參見式(23)；

(6)Yk+1=Yk+μk(Bk+1-Lk+1) 參見式(24)；

(7)Zk+1=Zk+μk(Bk+1-Hk+1) 參見式(25)；

(8)μk+1=min(ρμk,μmax) 參見式(26)；

(9)根據式(27)檢查是否收斂。

3 實驗結果與分析

3.1 直觀實驗結果對比

為了進行驗證，我們從數據庫change detection video database[15]中選取了5組具有挑戰性的數據集：①boats、②water surface、③fountain、④fall、⑤overpass對本文所提出的算法進行評估。實驗的運行環境為Intel Core i5處理器，8 GB內存，win10操作系統；實驗的軟件環境為Matlab R2015a。將本文提出的算法與RPCA、WMPCA和DECOLOR模型進行比較，得到的結果如圖1所示。本數據集分為3類：目標在復雜動態背景內緩慢運動：①boats、②water surface。背景包含可被檢測運動前景的高動態區域：③fountain、④fall。運動目標在復雜場景中運動：⑤overpass。對比RPCA模型、WMPCA模型、DECOLOR模型和本文提出的模型在3種不同場景下的目標檢測結果。其中RPCA模型和WMPCA模型對復雜背景的運動目標檢測不適用，容易將運動背景誤檢成目標前景,但WMPCA模型相對于RPCA模型能取得更好的效果，其主要的原因在于WMPCA模型采用非凸加權核函數逼近秩函數，能夠更好體現視頻中低秩背景幀之間的強相關性；而DECO-LOR模型對比WMPCA模型和RPCA模型雖然融合了運動目標區域連續性提高了檢測精度，但由于該模型過度的平滑約束導致檢測到的運動目標不完整或誤檢現象；而本文融合了WMPCA的優點，同時在低秩背景矩陣上進行時空約束以保持局部信息，最終得到完整的運動目標。

圖1 視頻前景提取實驗對比

3.2 實驗結果分析

本文采用峰值信噪比(peak signal to noise ratio，PSNR)對3種模型的背景恢復效果進行衡量，公式如下

(28)

(29)

(30)

(31)

(32)

其中，r為召回率(recall)，p為準確率(precision, p)。TP(true positives)為檢測中被正確分類的前景像素點數，FP(false positives)為檢測中背景像素被錯誤分為前景的像素點數，FN(false negatives)為檢測中前景被錯誤分為背景的像素點數。當綜合性能指標越高，表示該模型的運動目標提取效果越好。

從表1可以看出動態背景的視頻中，本文模型較RPCA、WMPCA與DECOLOR這3種模型在綜合性能指標上有明顯的提高。本文模型在低秩背景上進行時空約束從而降低了錯分率，使得復雜背景下的運動目標檢測準確率提高。從表2可以看出本文提出的方法信噪比PSNR比其它模型高得多。主要在于本文利用圖拉普拉斯正則化的相似性思想從而保留了低秩背景的內在結構。即使被前景目標遮擋，也能夠生成較為精確的背景模型。

表1 各模型召回率、準確率及綜合性能指標F比較

表2 各算法峰值信噪比PSNR比較

在本文所提出的算法中，我們設置參數λ=1/max(m,n)。 對于參數γ1,γ2，通過實驗發現，若測試場景為靜態背景，則空間模型優于時間模型，此時應設置γ1<γ2； 若測試場景為動態場景或光線較暗，例如圖1中的圖(d)，則時間模型優于空間模型，此時應設置γ1>γ2； 據此綜合設置參數γ1=γ2=0.08。

4 結束語

本文提出了一種基于非凸加權核范數的時空低秩RPCA模型用于對復雜場景的運動目標檢測，該模型在動態背景、光照漸變等復雜場景中能較準確地檢測出運動目標。首先，利用加權核范數替代核范數用于視頻的背景建模，同時對背景矩陣進行時空約束以保留局部信息，從而提高運動目標的檢測精度。本文分別在5種不同的復雜場景下進行實驗，與其它模型相比，本文所提出的模型對目標檢測的效果最佳，且適用性最強。