改進(jìn)的截?cái)嗪朔稊?shù)及在視頻前背景分離中的應(yīng)用

楊永鵬，楊真真，李建林，范 露

(1.南京信息職業(yè)技術(shù)學(xué)院 網(wǎng)絡(luò)與通信學(xué)院，江蘇 南京 210023；2.南京郵電大學(xué) 寬帶無線通信與傳感網(wǎng)技術(shù)教育部重點(diǎn)實(shí)驗(yàn)室，江蘇 南京 210023)

視頻前背景分離一直是計(jì)算機(jī)視覺等領(lǐng)域研究的熱點(diǎn)，但是由于自然界存在的噪聲、模糊、遮擋和光照變化等的干擾，使其成為最具有挑戰(zhàn)性的問題之一。在此背景下，如何根據(jù)視頻先驗(yàn)信息，構(gòu)造魯棒性強(qiáng)、復(fù)雜度低的視頻前背景分離方案是其關(guān)鍵難題。魯棒主成分分析（robust principal component analysis，RPCA）[1]作為多媒體信息處理領(lǐng)域的前沿技術(shù)，被廣泛應(yīng)用于視頻前背景分離[2–5]中，同時(shí)，也是視頻去噪[6]和人臉陰影移除[7]等領(lǐng)域的關(guān)鍵技術(shù)。傳統(tǒng)RPCA是一種將觀測矩陣分解為低秩矩陣和稀疏矩陣的方法，所以又被稱為稀疏低秩分解（sparse and low-rank decomposition，SLRD）。但是，由于該問題的非凸、非連續(xù)性等特點(diǎn)使傳統(tǒng)RPCA問題難以直接求解，且其是NP–難問題。為了求解該問題，主成分追蹤（principal component pursuit，PCP）算法[8]被提出，該算法分別采用核范數(shù)和L1范數(shù)替代傳統(tǒng)RPCA模型中的秩函數(shù)和L0范數(shù)。PCP算法能夠較好地解決多媒體信息處理領(lǐng)域中的諸多問題[8]，尤其是推動了視頻前背景分離[9]、矩陣填充[10]等技術(shù)領(lǐng)域的發(fā)展，并逐漸成為引領(lǐng)RPCA方法發(fā)展的基礎(chǔ)框架。但PCP算法也存在諸如時(shí)間復(fù)雜度高，平等對待所有奇異值，不能較好逼近秩函數(shù)和L0范數(shù)，抗噪聲能力弱以及不考慮結(jié)構(gòu)化、運(yùn)動化信息等缺陷。針對PCP算法存在的以上問題，改進(jìn)的RPCA算法被提出并被應(yīng)用于視頻前背景分離。

改進(jìn)的算法主要分為凸替代RPCA方法、非凸替代RPCA方法、加入輔助信息的RPCA方法以及截?cái)嗪朔稊?shù)方法。例如，去分解（go decomposition，GoDec）算法[11]是一種經(jīng)典的凸替代RPCA方法，它將受環(huán)境污染的觀測矩陣分解為低秩、稀疏和噪聲矩陣，增強(qiáng)了PCP算法的魯棒性，同時(shí)，采用雙邊隨機(jī)預(yù)測（bilateral random projections，BRP）方法[11]優(yōu)化算法時(shí)間復(fù)雜度，提高算法收斂速度，但是，凸替代方法對秩函數(shù)和稀疏度函數(shù)的逼近程度不高，效果欠佳。在此基礎(chǔ)上，一系列非凸替代RPCA方法被陸續(xù)提出，例如，非凸非光滑加權(quán)核范數(shù)（nonconvex nonsmooth weighted nuclear norm，NNWNN）算法[12]、非凸低秩稀疏分解（nonconvex low-rank and sparse decomposition，NonLRSD）算法[13]、非凸秩逼近（nonconvex rank approximation，NRA）算法[14]、廣義雙步長（general dual step-size，GDSS）算法[15]、線性分類非凸（linear spectral clustering and non-convex，LSCNC）算法[16]、帶有分割稀疏的非凸RPCA（non-convex and segmentation constraint，NCSC）算法[17]、核化的非凸全變差RPCA（nonconvex total variation regularized RPCA with kernelization，KRPCA–NTV）算法[18]等，這些非凸替代RPCA方法采用較為先進(jìn)的非凸替代函數(shù)替換傳統(tǒng)RPCA中的秩函數(shù)和稀疏度函數(shù)。但是，由于該類算法的替代函數(shù)仍然非最優(yōu)，同時(shí)，容易忽略視頻中的結(jié)構(gòu)化信息，使得視頻前背景分離的效果差強(qiáng)人意。考慮到視頻中存在大量的時(shí)空信息，于是許多基于輔助信息的RPCA方法被提出并應(yīng)用于視頻前背景分離中，例如：基于低秩和結(jié)構(gòu)化的稀疏分解（lowrank and structured sparse decomposition，LSD）算法[19]采用結(jié)構(gòu)化稀疏誘導(dǎo)范數(shù)描述矩陣的稀疏成分，并將空間信息引入到RPCA算法模型中；基于運(yùn)動信息輔助的矩陣恢復(fù)（motion-assisted matrix restoration，MAMR）算法[20]將運(yùn)動信息引入到傳統(tǒng)RPCA模型中，輔助信息的加入促進(jìn)了矩陣分解的準(zhǔn)確性，尤其對受光照變化、水紋波動等影響的觀測矩陣分解效果明顯。但是，該類算法較難描述視頻中的輔助信息，視頻前背景分離效果不穩(wěn)定，同時(shí)，由于大量輔助信息計(jì)算的引入導(dǎo)致算法時(shí)間復(fù)雜度較高，視頻前背景分離的時(shí)間較長。

截?cái)嗪朔稊?shù)（truncated nuclear norm，TNN）算法[21–23]是為了解決PCP算法中核范數(shù)平等對待所有奇異值的問題而提出的一種更逼近秩函數(shù)的方法。與傳統(tǒng)RPCA不同的是，TNN算法是對 min(m,n)?r個(gè)奇異值進(jìn)行最優(yōu)化計(jì)算，并最終將傳統(tǒng)RPCA模型轉(zhuǎn)換為一個(gè)凸優(yōu)化問題進(jìn)行求解。通過大量的理論論證和實(shí)驗(yàn)驗(yàn)證表明TNN能夠取得較好的視頻前背景分離效果。在TNN算法的基礎(chǔ)上，諸多改進(jìn)的TNN算法陸續(xù)被提出并廣泛應(yīng)用于視頻前背景分離中，例如，Hu等[21]提出了一種基于截?cái)嗪朔稊?shù)和稀疏正則化（truncated nuclear norm and a sparse regularizer，TNNSR）的低秩稀疏分解算法，該算法在TNN的基礎(chǔ)上增加了稀疏先驗(yàn)項(xiàng)，提高了TNN算法的魯棒性。雖然大量實(shí)驗(yàn)表明TNN及其改進(jìn)算法在視頻前背景分離中具有較好的效果，但是由于TNN模型中的核范數(shù)仍然是凸替代函數(shù)，逼近程度弱，算法效果欠優(yōu)，仍然亟待改進(jìn)。

本文提出了一種改進(jìn)的截?cái)嗪朔稊?shù)（improved truncated nuclear norm，ITNN）算法，為了增強(qiáng)TNN算法對傳統(tǒng)RPCA算法的逼近度，該算法采用非凸γ范數(shù)替代TNN算法中的核范數(shù)，并從理論上分析了非凸γ范數(shù)比核范數(shù)逼近度更高的原因。同時(shí)，本文采用廣義交替方向乘子法（generalized alternating direction method of multipliers，GADMM）[24–25]求解ITNN算法模型。最后，將ITNN算法及其對比算法應(yīng)用到視頻前背景分離實(shí)驗(yàn)中，驗(yàn)證ITNN算法的有效和優(yōu)越性。

1 改進(jìn)的截?cái)嗪朔稊?shù)

1.1 改進(jìn)的截?cái)嗪朔稊?shù)的模型

鑒于矩陣M的秩與其較小的 min(m,n)?r個(gè)非零奇異值相關(guān)，TNN算法將傳統(tǒng)的RPCA模型轉(zhuǎn)換為如式（1）所示的模型：

式中，M∈Rm×n為已知的觀測矩陣，L∈Rm×n為低秩矩陣，S∈Rm×n為 稀疏矩陣，σi(L)為 矩陣L的 奇異值，r為截?cái)嗟钠娈愔祩€(gè)數(shù)。

由文獻(xiàn)[21]可知，式（2）可以轉(zhuǎn)換為如下問題：

式中：A=(u1,u2,···,ur)∈Rm×r為低秩矩陣L的前r個(gè)左奇異向量；B=(v1,v2,···,vr)∈Rn×r為低秩矩陣L的前r個(gè)右奇異向量；核范數(shù) //L//?為秩函數(shù)的凸有偏估計(jì)，其對秩函數(shù)的逼近程度低。研究表明非凸替代函數(shù)能更好地逼近傳統(tǒng)RPCA模型中的秩函數(shù)[12–18]。本文采用非凸γ范數(shù)[14]替代TNN算法中的核范數(shù)，γ范數(shù)的表達(dá)式如下：

式中，i=1,2,···,min(m,n)。又因?yàn)椋?/p>

所以，γ范數(shù)比核范數(shù)更逼近秩函數(shù)。另外，為了進(jìn)一步說明γ范數(shù)的逼近度，本文給出了γ 范數(shù)（γ=0.1, 0.01）和核范數(shù)的函數(shù)圖形，如圖1所示。從圖1可以看到，本文提出的γ范數(shù)比核范數(shù)更逼近秩函數(shù)，同時(shí)， γ=0.01的 逼近效果比 γ =0.1更好，本實(shí)驗(yàn)中所用的 γ =0.01。

圖1 不同范數(shù)逼近秩函數(shù)的對比Fig. 1 Comparison of different norms approximating to the rank function

于是，本文提出ITNN模型如下：

1.2 改進(jìn)的截?cái)嗪朔稊?shù)模型求解

步驟1：給定Lk對Lk進(jìn)行奇異值分解即[Uk,Σk,Vk]=S VD(Lk) ，得到Lk對應(yīng)的左、右奇異向量如下：

并通過取對應(yīng)的前r個(gè)左、右奇異向量得到：

步驟2：在步驟1的基礎(chǔ)上求解優(yōu)化問題：

本文采用GADMM算法求解式（6）所示的優(yōu)化問題，其對應(yīng)的增廣拉格朗日函數(shù)為：

式中，Y為拉格朗日乘子， μ＞0 為懲罰參數(shù)， // ·//F是Frobenius范數(shù)。通過以下步驟對問題（6）進(jìn)行求解：

首先，固定St、Yt和μt，更新Lt+1，即

式（9）可以用凸規(guī)劃差分（difference of convex，DC）算法[14]進(jìn)行求解。

于是，得到式（8）的最優(yōu)解為：

其次，固定Lt+1、Yt和μt，更新變量St+1，即

式中， α∈(0,2) 為 松弛因子。當(dāng) α=1時(shí)，GADMM算法退化為經(jīng)典的ADMM算法?？梢岳密涢撝凳湛s算子對式（11）的變量St+1進(jìn)行更新，得到迭代格式如下：

式 中， Θξ(·) 為 軟 閾 值 收 縮 算 子，定 義 為Θξ(E)=max(|E|?ξ,0)·sign(E)， 其中，ξ ＞0 為參數(shù)，s ign(·)為符號函數(shù)。

最后，固定Lt+1、St+1， 更新拉格朗日乘子Yt+1和懲罰因子μt+1：

式中，ρ為放大系數(shù)。

綜上所述，使用算法1、2求解問題（5）。

算法1求解問題（5）的總算法

1）初始化：L0=0。

2）給定Lk，計(jì)算Lk的奇異值分解：

[Uk,Σk,Vk]=S VD(Lk),

得到左、右奇異向量Uk和Vk，進(jìn)而得到其分別對應(yīng)的截?cái)嗥娈愊蛄緼k和Bk。

3）求解如下優(yōu)化問題：

下面給出采用GADMM算法求解算法1中步驟3）（問題（6））的具體算法2，。

算法2采用GADMM求解算法1中步驟3）的算法

2）根據(jù)式（10）更新變量Lt+1。

3）根據(jù)式（12）更新變量St+1。

4）根據(jù)式（13）更新Yt+1。

5）根據(jù)式（14）更新 μt+1。

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

為了驗(yàn)證提出的ITNN算法的優(yōu)勢，以8個(gè)實(shí)驗(yàn)視頻序列為實(shí)驗(yàn)對象，進(jìn)行視頻前背景分離仿真實(shí)驗(yàn)，并隨機(jī)選取Airport視頻的第1 656幀、ShoppingMall視頻的第1 862幀、WaterSurface視頻的第1 624幀、Escalator視頻的第4 595幀、Curtain視頻的第22 774幀、Cubicle視頻的第1 303幀、Corridor視頻的第817幀和Car視頻的第689幀的實(shí)驗(yàn)效果進(jìn)行分析，實(shí)驗(yàn)結(jié)果如圖2所示。

圖2 各算法提取的視頻前景對比Fig. 2 Comparison of video foreground extracted by different methods

從圖2可以看出：本文提出的ITNN算法較其他對比算法具有更好的分離效果。例如：從Airport視頻提取前景的效果（圖2的第1行）可以看出，本文提出的ITNN算法提取的前景圖片的中間偏右部分和中間偏上部分比其他對比算法的噪聲更少。從對Shopping-Mall視頻提取前景的效果（圖2的第2行）可以看出，ITNN算法提取的前景的右上角部分具有較少的噪聲。從WaterSurface視頻提取前景的效果（圖2的第3行）可以看出，ITNN算法從視頻中提取的人的輪廓信息更加豐富和完整，噪聲更少；同等條件下，其他算法只能提取人輪廓的一半乃至更少的信息，且提取的前景所包含的噪聲較多，產(chǎn)生噪聲最明顯的是Godec算法。從Curtain視頻提取前景的效果（圖2的第5行）可以看出，ITNN算法提取的前景中人的信息較豐富，尤其是比TNN算法提取的人的信息豐富，并且比GDSS、MAMR、NNWNN、NonLRSD、Godec和PCP算法產(chǎn)生的噪聲更少。綜上所述，從視覺角度來看，本文提出的ITNN算法與其他對比算法相比提取的前景效果更好，前景信息更豐富和完整。

ITNN算法與上述7種對比算法進(jìn)行視頻前背景分離的F-measure值如表1所示。表1的最后一行給出了每種算法在視頻前背景分離過程中的平均F-measure值。

表1 不同算法的視頻前背景分離的F-measure值Tab. 1 F-measure of different methods in the experiments of foreground-background separation

從表1可以看出：ITNN算法在對Airport、Water-Surface、Escalator、Curtain和Car進(jìn)行視頻前背景分離的F-measure值較其他對比算法更高。例如，對Airport視頻，ITNN算法的F-measure值比PCP算法高9%；對WaterSurface視頻，ITNN算法的F-measure值比TNN算法高42%；對Escalator視頻，ITNN算法的F-measure值比Godec算法高3%；對Curtain視頻，ITNN算法的F-measure值比Godec算法高12%；對Car視頻，ITNN算法的F-measure值比TNN算法高12%。平均F-measure值最高的為本文提出的ITNN算法，比次高的NonLRSD算法高3%，比最低的TNN算法高12%，也即本文提出的ITNN算法比其他7種基于RPCA的視頻前背景分離算法的效果更好，從而定量地驗(yàn)證了提出的ITNN算法的優(yōu)越性。

為了驗(yàn)證ITNN算法的時(shí)間復(fù)雜度，實(shí)驗(yàn)記錄了ITNN算法與上述7種對比算法進(jìn)行視頻的前背景分離的運(yùn)行時(shí)間，如表2所示。

表2 不同算法的視頻前背景分離運(yùn)行時(shí)間比較Tab. 2 Comparison of running time of each algorithm in the foreground-background separation s/幀

從表2中的平均時(shí)間可以看出：由于GoDec算法使用了加速算法，所以其運(yùn)行時(shí)間最快；除GoDec算法外，ITNN算法的平均運(yùn)行時(shí)間只比GDSS算法略慢，但比其他5種算法要快，其中，比MAMR算法快0.18 s/幀，比NNWNN算法快0.02 s/幀，比NonLRSD算法快0.017 s/幀，比TNN算法快0.5 s/幀，比PCP算法快0.3 s/幀。進(jìn)一步驗(yàn)證了ITNN算法在時(shí)間復(fù)雜度上的優(yōu)勢。

綜上所述，本文從視覺和量化（即F-measure值和運(yùn)行時(shí)間）兩個(gè)角度驗(yàn)證了提出的ITNN算法的優(yōu)越性。

3 結(jié) 論

以截?cái)嗪朔稊?shù)方法為代表的傳統(tǒng)魯棒主成分分析方法中的核范數(shù)對魯棒主成分分析模型中的秩函數(shù)逼近程度不高，進(jìn)而影響到視頻前背景分離的效果。在此背景下，本文提出了一種改進(jìn)的截?cái)嗪朔稊?shù)（ITNN）算法模型，該模型采用逼近程度較高的非凸γ范數(shù)代替TNN算法模型中的核范數(shù)，同時(shí)，從理論上分析了非凸γ范數(shù)與核范數(shù)對秩函數(shù)的逼近度，并采用GADMM算法對提出的模型進(jìn)行求解。將該模型應(yīng)用于視頻前背景分離實(shí)驗(yàn)中，從實(shí)驗(yàn)結(jié)果的視覺角度可以看到本文提出的ITNN算法具有較好的視頻前背景分離效果。另外，實(shí)驗(yàn)中記錄了ITNN及其對比算法對不同視頻前背景分離的F-measure值和運(yùn)行時(shí)間。ITNN的平均F-measure值為0.625 5，平均運(yùn)行時(shí)間為0.076 0 s/幀，進(jìn)一步驗(yàn)證了本文提出的ITNN算法模型的有效性和優(yōu)越性。但是，本文提出的ITNN算法仍然不是最優(yōu)的秩函數(shù)的替代函數(shù)，尋找更優(yōu)的替代函數(shù)仍然是下一步研究工作的重點(diǎn)。