時(shí)空RPCA在復(fù)雜場景下的運(yùn)動(dòng)目標(biāo)檢測

張超婕，余 勤

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

0 引 言

在計(jì)算機(jī)視覺應(yīng)用中，數(shù)據(jù)的維度通常非常高。主成分分析(PCA)[1]是一種有效降低維數(shù)的方法。然而，PCA對于異常點(diǎn)和稀疏大噪聲的數(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模型。然而該模型并未考慮到時(shí)間和空間上的連續(xù)性，使得復(fù)雜背景下運(yùn)動(dòng)目標(biāo)的檢測效果不理想。Zhou等[7]注意到運(yùn)動(dòng)目標(biāo)具有區(qū)域連續(xù)性，因此在RPCA模型的基礎(chǔ)上加入該先驗(yàn)知識(shí)提出了DECOLOR模型，雖然分割性能得到提高，但該模型嚴(yán)格的平滑約束使得運(yùn)動(dòng)目標(biāo)檢測不完整。為了保留高維空間的局部幾何結(jié)構(gòu)，研究者們提出了圖的降維方法。Yan等[8]提出了圖嵌入框架模型，可將一些經(jīng)典的降維算法如PCA、LDA和LPP等嵌入到該框架中。據(jù)此Jiang等[9]提出了圖拉普拉斯PCA(GLRPCA)，但該模型對數(shù)據(jù)損壞或異常點(diǎn)非常敏感。

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

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

1.1 預(yù)備知識(shí)

定義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個(gè)奇異值。對于任意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ù)稀疏矩陣對大噪聲和異常點(diǎn)具有魯棒性的特點(diǎn),提出魯棒主成分分析模型(RPCA)。將n幀圖像組成的觀測矩陣表示為D=[d1,d2,…dn]∈Rm×n，其中di表示第i幀圖像矢量化的列向量，每幀圖像有m個(gè)像素點(diǎn)。魯棒主成分分析模型(RPCA)認(rèn)為可將觀測矩陣D分解成低秩背景矩陣B∈Rm×n和稀疏前景矩陣F∈Rm×n。 其模型如下所示

(4)

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

(5)

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

1.3 拉普拉斯特征映射

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

(6)

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

(7)

或

(8)

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

(9)

2 模型的建立及其求解

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

(10)

2.1 時(shí)空低秩正則化

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

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

(11)

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

(12)

得到歸一化時(shí)間圖拉普拉斯矩陣ΦT

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

(13)

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

2.2 改進(jìn)RPCA算法

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

(14)

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

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

(15)

算法1：低秩背景矩陣估計(jì)

輸入：μ，觀測矩陣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、μ，更新時(shí)間低秩矩陣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 實(shí)驗(yàn)結(jié)果與分析

3.1 直觀實(shí)驗(yàn)結(jié)果對比

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

圖1 視頻前景提取實(shí)驗(yàn)對比

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

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

(28)

(29)

(30)

(31)

(32)

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

從表1可以看出動(dòng)態(tài)背景的視頻中，本文模型較RPCA、WMPCA與DECOLOR這3種模型在綜合性能指標(biāo)上有明顯的提高。本文模型在低秩背景上進(jìn)行時(shí)空約束從而降低了錯(cuò)分率，使得復(fù)雜背景下的運(yùn)動(dòng)目標(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，通過實(shí)驗(yàn)發(fā)現(xiàn)，若測試場景為靜態(tài)背景，則空間模型優(yōu)于時(shí)間模型，此時(shí)應(yīng)設(shè)置γ1<γ2； 若測試場景為動(dòng)態(tài)場景或光線較暗，例如圖1中的圖(d)，則時(shí)間模型優(yōu)于空間模型，此時(shí)應(yīng)設(shè)置γ1>γ2； 據(jù)此綜合設(shè)置參數(shù)γ1=γ2=0.08。

4 結(jié)束語

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