三分解模型與算法及其在圖像恢復(fù)中的應(yīng)用*

楊章靜，張凡龍，張 輝，楊國(guó)為，李佐勇 ，羅立民

1.東南大學(xué) 計(jì)算機(jī)科學(xué)與工程學(xué)院，南京 210009

2.南京審計(jì)大學(xué) 信息工程學(xué)院，南京 211815

3.南京理工大學(xué) 江蘇省社會(huì)安全圖像與視頻理解重點(diǎn)實(shí)驗(yàn)室，南京 210094

4.閩江學(xué)院 物聯(lián)網(wǎng)產(chǎn)業(yè)化與智能生產(chǎn)協(xié)同創(chuàng)新中心，福州 350108

1 引言

近年來(lái)，大規(guī)模的圖像數(shù)據(jù)無(wú)時(shí)不在、無(wú)處不在，這為計(jì)算機(jī)視覺(jué)、模式識(shí)別、數(shù)據(jù)挖掘和機(jī)器學(xué)習(xí)等領(lǐng)域的發(fā)展帶來(lái)機(jī)遇和挑戰(zhàn)。這些圖像數(shù)據(jù)含有豐富的信息以供挖掘利用，但與此同時(shí)，也大大增加了學(xué)習(xí)和研究的成本和困難，其中之一是在圖像采集或處理過(guò)程中，往往受到各種噪聲干擾。如何從觀測(cè)到的含噪聲圖像中恢復(fù)真實(shí)圖像對(duì)于后續(xù)應(yīng)用意義重大。

為了恢復(fù)真實(shí)圖像，在建模時(shí)必須訴諸于圖像固有的低維結(jié)構(gòu)。對(duì)于矩陣形式的數(shù)據(jù)，矩陣秩的大小可以直接反映這種低維性質(zhì)，因此受到越來(lái)越多研究者的關(guān)注，其中魯棒主成分分析（robust principal component analysis，RPCA）[1-2]是一種經(jīng)典的基于低秩假設(shè)的模型。它假設(shè)數(shù)據(jù)矩陣具有低秩性并且誤差矩陣是稀疏的。RPCA存在許多求解算法，如：乘子交替方向法[3]、梯度下降法[4]和基于隨機(jī)優(yōu)化的算法[5]。RPCA由于其可以擴(kuò)展到處理部分?jǐn)?shù)據(jù)丟失的情況，這實(shí)際上是矩陣補(bǔ)全問(wèn)題的擴(kuò)展，RPCA因此已經(jīng)成功應(yīng)用于視頻背景建模、排名協(xié)同過(guò)濾和人臉識(shí)別等領(lǐng)域中。作為RPCA的重要擴(kuò)展，低秩表示（low rank representation，LRR）[6-8]可以將數(shù)據(jù)分解為多個(gè)線性子空間的并集。與RPCA一樣，LRR也假設(shè)誤差項(xiàng)是稀疏的。

最近，有研究者[9]提出了基于雙核范數(shù)的矩陣分解方法（double nuclear norm based matrix decomposition，DNMD），并得到進(jìn)一步擴(kuò)展和應(yīng)用[10-12]。DNMD使用統(tǒng)一的低秩假設(shè)來(lái)表征真實(shí)圖像數(shù)據(jù)和遮擋數(shù)據(jù)，它假設(shè)所有圖像向量形成低秩矩陣，并且因遮擋導(dǎo)致每個(gè)誤差圖像也是低秩矩陣。與RPCA相比，DNMD的低秩假設(shè)對(duì)于描述遮擋更直觀。

在此基礎(chǔ)上，用于圖像去噪的加權(quán)核范數(shù)最小化[13-14]和基于Transformed-L1最小化的壓縮感知[15-16]相繼被提出，它們都是僅限于低秩分量正好低秩，稀疏分量完全稀疏。但是，這些假設(shè)中的任何一個(gè)在實(shí)踐中未必一定滿足，應(yīng)該予以松弛。為適應(yīng)更復(fù)雜的噪音，Cao等人[17]通過(guò)假設(shè)噪聲分布符合指數(shù)冪分布，提出了基于混合分布的恢復(fù)模型。在此基礎(chǔ)上，Yao等人[18]提出了一種子空間聚類方法，該方法對(duì)各種噪聲分布均具有魯棒性。Hu等人[19]采用了一種新的矩陣范數(shù)，稱為截?cái)嗪朔稊?shù)，用于近似秩函數(shù)。為了揭示數(shù)據(jù)矩陣中的局部模式，Abdolali等人[20]提出了一種將數(shù)據(jù)矩陣分解為不同尺度的低秩分量的方法。Bouwmans等人[21]對(duì)這些不同問(wèn)題的最新發(fā)展進(jìn)行了綜述。

以上提到的模型和方法均存在一個(gè)共同的局限：無(wú)法處理混合噪聲。在噪聲符合高斯分布的假設(shè)下，很自然地可以利用L2范數(shù)（F范數(shù)）作為噪聲度量。為了避免L2范數(shù)對(duì)孤立點(diǎn)和非高斯噪聲的敏感性，也可以用L1范數(shù)作為噪聲度量。然而，L1范數(shù)僅僅在處理符合普拉斯分布的噪聲時(shí)才是最優(yōu)的，對(duì)處理各種混合噪聲仍然非常有限。實(shí)際問(wèn)題中遇到噪聲并不單一，僅僅假設(shè)噪聲符合某一種分布并不合理。

針對(duì)此問(wèn)題，本文提出了一種三分解模型（tridecomposition model，Tri-Decom）用于恢復(fù)受到大的稀疏噪聲和小的稠密噪聲破壞的圖像數(shù)據(jù)。該方法通過(guò)不同的度量函數(shù)分別對(duì)干凈數(shù)據(jù)、稀疏噪聲和稠密噪聲進(jìn)行刻畫。此外，為了求解Tri-Decom，提出了乘子交替方向法。在人臉圖像中去除遮擋和監(jiān)控視頻中進(jìn)行背景建模的實(shí)驗(yàn)驗(yàn)證了所提出方法的有效性。

2 相關(guān)知識(shí)

給定數(shù)據(jù)矩陣X，記奇異值分解為X=USVT，其中S=diag(σ1,σ2,…,σr)，U和V是列正交矩陣。核范數(shù)、L2范數(shù)和L1范數(shù)分別定義為：

給定τ>0，奇異值閾值算子Dτ(·)定義為：

數(shù)據(jù)X通常被各種噪聲破壞，包括大的稀疏噪聲和小的稠密噪聲。RPCA的基本思想是將X分解為兩個(gè)矩陣D和E，其中矩陣D具有低秩性，而矩陣E具有稀疏性，其模型如下：

作為RPCA的重要擴(kuò)展，低秩表示（LRR）可以將數(shù)據(jù)分解為多個(gè)線性子空間的并集。與RPCA一樣，LRR也假設(shè)誤差項(xiàng)是稀疏的。

最近，研究者[9]提出了基于雙核規(guī)范的矩陣分解（DNMD），DNMD旨在將每個(gè)圖像分解為Xi=Di+Ei。具體而言，給定圖像X1,X2,…,Xs∈Rm×n，其模型如下：

其中，X=[vec(X1),vec(X2),…,vec(Xs)]，D=[vec(D1),vec(D2),…,vec(Ds)]，E=[vec(E1),vec(E2),…,vec(Es)]。

3 三分解模型及其算法

首先給出如何將圖像恢復(fù)問(wèn)題表示為數(shù)據(jù)的三分解模型，然后具體介紹其算法。

3.1 三分解模型

根據(jù)以上分析，低秩分量正好低秩，稀疏分量完全稀疏。但是，這些假設(shè)中的任何一個(gè)在實(shí)踐中未必一定滿足，為此本文考慮添加一個(gè)新的分解項(xiàng)，它表示非稀疏的擾動(dòng)誤差（稠密誤差）。例如，在監(jiān)控視頻中，可以將每一幀拉成一個(gè)列向量，然后將視頻的所有幀按列排成一個(gè)矩陣，記為X。三分解的目的是將X分解為D、E和F三個(gè)分量。分量D代表視頻背景，由于幀之間的相似性，一個(gè)合理假設(shè)是假設(shè)D具有低秩性；分量E表示視頻中的活動(dòng)目標(biāo)，可以假設(shè)E具有稀疏性；分量F表示由光照、陰影或其他因素引起的擾動(dòng)噪聲。

為此，提出一種新的圖像恢復(fù)方法，稱為三分解模型（Tri-Decom）：

其中，原始數(shù)據(jù)X被分解為三個(gè)分量；分量D是低秩矩陣，代表恢復(fù)后的數(shù)據(jù)；分量E和F分別代表稀疏噪聲和非稀疏噪聲。

函數(shù)Φ(·)表示非稀疏噪聲的度量方法，實(shí)際應(yīng)用中，可以針對(duì)特定問(wèn)題選擇函數(shù)Φ的合適形式。本文下面的研究中選用，主要基于以下考慮：目標(biāo)函數(shù)中的噪聲項(xiàng)E代表了稀疏噪聲，第三項(xiàng)F代表了因密集的小擾動(dòng)引起的稠密噪聲，而F范數(shù)在刻畫稠密小噪聲方面具有明顯優(yōu)勢(shì)。另外，F(xiàn)范數(shù)具有連續(xù)可微性和凸性，利于后續(xù)求解。

Fig.1 Decomposing observation frameXiinto 3 partsDi,EiandFi圖1 將觀察幀Xi分解為Di、Ei和Fi三個(gè)分量

整個(gè)過(guò)程如圖1所示。為可視化，在圖中對(duì)Ei和Fi進(jìn)行了二值化處理。將每一幀拉成向量后可以按列將所有視頻幀組成一個(gè)矩陣，進(jìn)而分別得到對(duì)應(yīng)的X、D、E、F。

3.2 三分解算法

在統(tǒng)計(jì)學(xué)習(xí)和機(jī)器學(xué)習(xí)等領(lǐng)域諸多優(yōu)化問(wèn)題都有一個(gè)共同特點(diǎn)，即數(shù)據(jù)量大，導(dǎo)致對(duì)應(yīng)的優(yōu)化問(wèn)題變量規(guī)模也大，而傳統(tǒng)的許多優(yōu)化方法無(wú)法直接應(yīng)用于大規(guī)模變量，乘子交替方向法（alternating direction method of multipliers，ADMM）[3,22-23]是近年興起的，行之有效的處理大規(guī)模優(yōu)化問(wèn)題的算法，尤其適合變量可分離的優(yōu)化模型。故本文使用ADMM求解三分解模型。首先給出Tri-Decom對(duì)應(yīng)的增廣Lagrange函數(shù)如下：

其中，Y是Lagrange乘子矩陣，μ是罰參數(shù)。接著，采用交替方向法更新每個(gè)變量。算法框架具體如下：

（1）固定E=Ek,F=Fk,Y=Yk，更新D：

其中，Dτ(·)是由式（2）定義的奇異值閾值算子。

（2）固定D=Dk+1,F=Fk,Y=Yk，更新E:

其中，Sε(·)是一個(gè)軟閾值算子，其定義如下：

軟閾值算子將絕對(duì)值小于ε的數(shù)全部置零，而將絕對(duì)值大于ε的數(shù)做一個(gè)特殊處理：大于ε的數(shù)統(tǒng)一減去ε，小于 -ε的數(shù)統(tǒng)一加ε。一組數(shù)字經(jīng)過(guò)軟閾值算子的作用之后會(huì)比較光滑，符合圖像像素值連續(xù)變化的特點(diǎn)。具體到式（8）中ε=λ/μ。

（3）固定D=Dk+1,E=Ek+1,Y=Yk，更新F:

3.3 算法最優(yōu)性條件分析

下面給出最優(yōu)性條件和停止準(zhǔn)則。三元組(D°,E°,F°)是最優(yōu)解的充要條件包括原始可行條件性與對(duì)偶可行性條件。其中原始可行性條件是指(D°,E°,F°)要滿足約束條件，即：

對(duì)偶可行性條件是指目標(biāo)函數(shù)在(D°,E°,F°)處的微分（或次微分）包含0點(diǎn)，即式（14）和式（15）：

對(duì)于 式（13）,在第k+1步迭代時(shí)的殘差X-Dk+1-Ek+1-Fk+1稱為原始?xì)埐睿洖閞k+1。當(dāng)原始?xì)埐钚〉侥硞€(gè)閾值，則可認(rèn)為(Dk+1,Ek+1,Fk+1)符合原始可行性條件。

下面考慮如何判定對(duì)偶可行性條件，由于Dk+1是Lμ(D,Ek,Fk,Yk)的極小點(diǎn)，因此可以表示如下：

其中，μ(Ek+1+Fk+1-Ek-Fk)為對(duì)偶?xì)埐睿洖閟k+1。

在迭代過(guò)程中，對(duì)偶?xì)埐顂k+1和原始?xì)埐顁k+1收斂到0。一個(gè)合理的終止準(zhǔn)則可以做如下選擇：, 其中，εpri和εdual定義為：

其中，εabs、εrel分別是絕對(duì)容差和相對(duì)容差。

三分解模型求解算法：

1.輸入:觀測(cè)數(shù)據(jù)D,參數(shù)λ、γ、εabs、εrel，進(jìn)行初始化：

2.分別利用式（7）、式（8）和式（11），更新(D,E,F)；

3.利用式（12）更新乘子Y；

4.更新μ:μ=min(ρμ,μmax);

4 實(shí)驗(yàn)

為了驗(yàn)證算法的性能，將提出的算法應(yīng)用于視頻背景建模和人臉圖像數(shù)據(jù)的恢復(fù)，作為對(duì)比，同時(shí)采用了其他典型算法如RPCA、RPCA-Lp[24]和DNMD。

4.1 參數(shù)分析

為了分析模型中的參數(shù)影響，以視頻監(jiān)控的背景建模為例。背景建模是計(jì)算機(jī)視覺(jué)應(yīng)用中非常重要的主題。對(duì)于一段視頻，將其中的每一幀拉成一個(gè)列向量，然后按列排成一個(gè)矩陣，記為X；通過(guò)各種算法對(duì)X中的背景和目標(biāo)進(jìn)行恢復(fù)。

Tri-Decom的兩個(gè)參數(shù)λ和γ分別用于在噪聲項(xiàng)和干凈數(shù)據(jù)項(xiàng)之間保持平衡。作為評(píng)估不同參數(shù)值影響的說(shuō)明性示例，使用100幀并將每一幀堆疊到矩陣X中，矩陣X的大小為4 800×100；接著通過(guò)Tri-Decom檢測(cè)前景目標(biāo)，實(shí)驗(yàn)結(jié)果如圖2所示。

圖2（a）中，對(duì)稀疏噪聲E的稀疏性的測(cè)量可以看出：在λ不變的情況下，γ越小||E||1越小，也即E越稀疏；在γ不變的情況下，λ越大||E||1越小。因此λ與γ對(duì)稀疏性有截然相反的影響。同理，圖2（b）～圖2（d）清楚體現(xiàn)了λ與γ對(duì)稠密性噪聲和矩陣秩的影響。從圖2實(shí)驗(yàn)結(jié)果可以看出三個(gè)分量的測(cè)量值隨著參數(shù)的不同而顯著變化，這就說(shuō)明引入的參數(shù)在提出的模型中起著關(guān)鍵作用。一般情況下，最優(yōu)參數(shù)與不同數(shù)據(jù)集的屬性有關(guān)，沒(méi)有適用于不同數(shù)據(jù)庫(kù)的一致規(guī)則。

4.2 視頻背景建模

背景建模是從視頻的背景中抽取出活動(dòng)行為（也稱前景目標(biāo)）。背景建模在事件監(jiān)測(cè)、人體行為識(shí)別中都扮演著重要角色[25]。

實(shí)驗(yàn)使用九段視頻[26]（http://perception.i2r.a-star.edu.sg/bk_model）。對(duì)于每段視頻，使用200幀，每幀的大小為60×80。將這些幀堆疊到矩陣X中，矩陣X的大小為4 800×200。為了進(jìn)行量化評(píng)估，使用F-score來(lái)測(cè)量恢復(fù)精度，F(xiàn)-score定義如下：

其中，precision=|G?T||T|,recall=|G?T||G|，G是真實(shí)行為，T是恢復(fù)后的行為。

Fig.2 Measure values of 3 decomposition terms versus different parameters圖2 在不同參數(shù)下三個(gè)分量的測(cè)量值

實(shí)驗(yàn)具體指標(biāo)結(jié)果見(jiàn)表1，F(xiàn)-score值越大，代表行為恢復(fù)得越準(zhǔn)確。從表1可以看出，在大多數(shù)情況下，Tri-Decom明顯優(yōu)于其他方法，這驗(yàn)證了Tri-Decom對(duì)背景提取的有效性。圖3顯示本文方法的恢復(fù)結(jié)果。這里需要指出的是，為實(shí)現(xiàn)可視化，將恢復(fù)的活動(dòng)和非稀疏噪聲中的像素值進(jìn)行了二值化處理。

由于光照變化（圖3第1、2行）或水紋變化（圖3第3行）所造成的噪聲具有稠密性，而非稀疏性，這可從圖3第（e）列的結(jié)果看出。與此同時(shí)，視頻中的目標(biāo)行為相對(duì)于整段視頻，具有稀疏性，可視為稀疏噪聲，這可從圖3第（d）列看出。對(duì)比圖3的第（d）、（e）兩列，可以清楚看到本文的Tri-Decom能有效地識(shí)別稀疏噪聲（即恢復(fù)的活動(dòng)目標(biāo)）和稠密噪聲。

Table 1 F-score on 9 video surveillance表1 九段不同監(jiān)控場(chǎng)景下的F-score值

4.3 人臉圖像恢復(fù)

在實(shí)際應(yīng)用中，采集到的人臉圖像通常受到光照、遮擋等多種因素的干擾。因此，在進(jìn)一步應(yīng)用之前，需要從損壞的數(shù)據(jù)中恢復(fù)真實(shí)數(shù)據(jù)。這些誤差通常包括大幅度的稀疏噪聲和小幅度的稠密噪聲。正如文獻(xiàn)[1,9]中指到的，如果有同一個(gè)個(gè)體的足夠多的圖像，基于低秩假設(shè)的模型能夠完美恢復(fù)損壞的數(shù)據(jù)。

在Extended Yale B數(shù)據(jù)庫(kù)（http://vision.ucsd.edu/～leekc/ExtYaleDatabase/ExtYaleB.html）中 ，有 38個(gè)個(gè)體。對(duì)于每個(gè)個(gè)體，使用不同光照條件下的14幅圖像，并且每個(gè)樣本具有48×42的分辨率。將每個(gè)圖像堆疊為矩陣列，稱為原始數(shù)據(jù)O，顯然這是一個(gè)2 016×532的矩陣。通過(guò)損壞原始數(shù)據(jù)O中的所有樣本來(lái)構(gòu)建觀察數(shù)據(jù)X，損壞的像素百分比設(shè)為5%，如圖4（a）所示。

接著，通過(guò)Tri-Decom獲得恢復(fù)數(shù)據(jù)D和噪聲數(shù)據(jù)E和F，D中的一些恢復(fù)圖像在圖4（b）中（此時(shí)D的秩為52），E中的稀疏噪聲圖像和F中的稠密噪聲圖像則在圖4（c）和圖4（d）中。同樣出于可視化的目的，對(duì)稠密噪聲分量F進(jìn)行了二值化。作為對(duì)比，RPCA的分解結(jié)果如圖5所示，從圖中可以看出，RPCA也可以較好恢復(fù)出干凈圖像。

對(duì)于訓(xùn)練集中的樣本（例如圖4（a）列），損壞的像素占比5%，導(dǎo)致的誤差具有稀疏性特點(diǎn)，而由于光照等變化引起的誤差具有稠密性特點(diǎn)。這兩種噪聲的混合對(duì)后續(xù)識(shí)別等任務(wù)帶來(lái)不利影響。本文提出的Tri-Decom非常清楚地對(duì)稀疏噪聲和稠密噪聲進(jìn)行了分離（圖4（c）和圖4（d））。這里需要特別指出的是，RPCA的噪聲分量E包含了稀疏噪聲和稠密噪聲（圖5（c）），無(wú)法明確分離開。

Fig.3 Background modeling from video surveillance圖3 監(jiān)控視頻的背景建模

Fig.4 Recovered results by Tri-Decom(λ=0.02,γ=0.09)圖4 三分解模型的恢復(fù)結(jié)果（λ=0.02,γ=0.09）

Fig.5 Recovered results by RPCA(λ=0.014)圖5 RPCA的恢復(fù)結(jié)果（λ=0.014）

Table 2 Running time of different algorithms on Extended Yale B(data size:2 016×532）表2 在Extended Yale B數(shù)據(jù)集上（數(shù)據(jù)尺寸:2 016×532）不同算法計(jì)算時(shí)間 s

最后表2中列出了在Extended Yale B數(shù)據(jù)集上算法計(jì)算時(shí)間的比較，由于Tri-Decom優(yōu)化變量多于RPCA，導(dǎo)致時(shí)間略高于RPCA，由于RPCA-Lp求解一個(gè)非凸問(wèn)題，耗時(shí)最長(zhǎng)，而DNMD迭代中比Tri-Decom更頻繁進(jìn)行奇異值分解，也需要較多時(shí)間。

5 結(jié)論

針對(duì)基于低秩假設(shè)在處理圖像恢復(fù)問(wèn)題時(shí)存在的缺陷，提出了一種新的圖像恢復(fù)模型Tri-Decom，用于處理同時(shí)受到稀疏和稠密噪聲破壞的圖像數(shù)據(jù)。所提出的Tri-Decom模型通過(guò)乘子交替方向法求解，可以有效地從觀測(cè)數(shù)據(jù)中分離干凈數(shù)據(jù)、稀疏噪聲和稠密噪聲。實(shí)驗(yàn)表明該方法能取得比其他算法更好的恢復(fù)效果。但如何利用其他噪聲度量函數(shù)使得算法達(dá)到最優(yōu)效果，比如來(lái)自魯棒統(tǒng)計(jì)文獻(xiàn)的Huber函數(shù)[27]來(lái)降低異常值的影響是今后需要重點(diǎn)研究的問(wèn)題。