時空RPCA在復(fù)雜場景下的運動目標(biāo)檢測

張超婕，余 勤

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

0 引 言

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

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

1 魯棒主成分分析及相關(guān)研究

1.1 預(yù)備知識

定義2[12]加權(quán)奇異收縮算子T。在矩陣D∈Rm×n中，D可以通過奇異值分解為D=UΣV，Σ=Diag({σi(D),1≤i≤n})。 對于任意的v>0,加權(quán)奇異值收縮算子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 非凸加權(quán)核范數(shù)求解。對于任意v>0,W=diag(w)，給定矩陣X，Y∈Rm×n(n

(2)

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

(3)

1.2 魯棒主成分分析(RPCA)

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

(4)

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

(5)

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

1.3 拉普拉斯特征映射

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

(6)

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

(7)

或

(8)

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

(9)

2 模型的建立及其求解

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

(10)

2.1 時空低秩正則化

由于傳統(tǒng)的RPCA模型缺乏結(jié)構(gòu)信息，因此對于復(fù)雜背景場景運動目標(biāo)檢測效果較差。通過對低秩背景矩陣B實施時空約束以更有效處理該問題。

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

(11)

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

(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表示行矩陣間鄰接矩陣?？臻g圖GS編碼了空間位置之間的相似性。對于空間圖的拉普拉斯算子的構(gòu)造，選擇在觀測矩陣D的補丁級上實施平滑，對于矩陣D第一幀中的每個像素，采用一個大小為u2的補丁。同理得到空間拉普拉斯矩陣ΦS。

2.2 改進RPCA算法

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

(14)

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

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

(15)

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

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

輸出：Bk+1

初始化：k=0,Bk=0

迭代：

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

(16)

固定B、L、H、X、Y、Z、μ，更新目標(biāo)矩陣F

(17)

根據(jù)引理2，可得到F的封閉解為

(18)

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

(19)

由上式為光滑函數(shù)，采用投影共軛梯度法求出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)

其中，ρ為常數(shù)。根據(jù)KKT條件，其收斂條件如下

(27)

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

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

輸出：B，F(xiàn)

初始化：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)根據(jù)式(27)檢查是否收斂。

3 實驗結(jié)果與分析

3.1 直觀實驗結(jié)果對比

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

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

3.2 實驗結(jié)果分析

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

(28)

(29)

(30)

(31)

(32)

其中，r為召回率(recall)，p為準(zhǔn)確率(precision, p)。TP(true positives)為檢測中被正確分類的前景像素點數(shù)，F(xiàn)P(false positives)為檢測中背景像素被錯誤分為前景的像素點數(shù)，F(xiàn)N(false negatives)為檢測中前景被錯誤分為背景的像素點數(shù)。當(dāng)綜合性能指標(biāo)越高，表示該模型的運動目標(biāo)提取效果越好。

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

表1 各模型召回率、準(zhǔn)確率及綜合性能指標(biāo)F比較

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

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

4 結(jié)束語

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