三分解模型與算法及其在圖像恢復中的應用*

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

1.東南大學 計算機科學與工程學院，南京 210009

2.南京審計大學 信息工程學院，南京 211815

3.南京理工大學 江蘇省社會安全圖像與視頻理解重點實驗室，南京 210094

4.閩江學院 物聯網產業化與智能生產協同創新中心，福州 350108

1 引言

近年來，大規模的圖像數據無時不在、無處不在，這為計算機視覺、模式識別、數據挖掘和機器學習等領域的發展帶來機遇和挑戰。這些圖像數據含有豐富的信息以供挖掘利用，但與此同時，也大大增加了學習和研究的成本和困難，其中之一是在圖像采集或處理過程中，往往受到各種噪聲干擾。如何從觀測到的含噪聲圖像中恢復真實圖像對于后續應用意義重大。

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

最近，有研究者[9]提出了基于雙核范數的矩陣分解方法（double nuclear norm based matrix decomposition，DNMD），并得到進一步擴展和應用[10-12]。DNMD使用統一的低秩假設來表征真實圖像數據和遮擋數據，它假設所有圖像向量形成低秩矩陣，并且因遮擋導致每個誤差圖像也是低秩矩陣。與RPCA相比，DNMD的低秩假設對于描述遮擋更直觀。

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

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

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

2 相關知識

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

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

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

作為RPCA的重要擴展，低秩表示（LRR）可以將數據分解為多個線性子空間的并集。與RPCA一樣，LRR也假設誤差項是稀疏的。

最近，研究者[9]提出了基于雙核規范的矩陣分解（DNMD），DNMD旨在將每個圖像分解為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 三分解模型及其算法

首先給出如何將圖像恢復問題表示為數據的三分解模型，然后具體介紹其算法。

3.1 三分解模型

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

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

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

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

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

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

3.2 三分解算法

在統計學習和機器學習等領域諸多優化問題都有一個共同特點，即數據量大，導致對應的優化問題變量規模也大，而傳統的許多優化方法無法直接應用于大規模變量，乘子交替方向法（alternating direction method of multipliers，ADMM）[3,22-23]是近年興起的，行之有效的處理大規模優化問題的算法，尤其適合變量可分離的優化模型。故本文使用ADMM求解三分解模型。首先給出Tri-Decom對應的增廣Lagrange函數如下：

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

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

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

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

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

軟閾值算子將絕對值小于ε的數全部置零，而將絕對值大于ε的數做一個特殊處理：大于ε的數統一減去ε，小于 -ε的數統一加ε。一組數字經過軟閾值算子的作用之后會比較光滑，符合圖像像素值連續變化的特點。具體到式（8）中ε=λ/μ。

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

3.3 算法最優性條件分析

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

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

對于 式（13）,在第k+1步迭代時的殘差X-Dk+1-Ek+1-Fk+1稱為原始殘差，記為rk+1。當原始殘差小到某個閾值，則可認為(Dk+1,Ek+1,Fk+1)符合原始可行性條件。

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

其中，μ(Ek+1+Fk+1-Ek-Fk)為對偶殘差，記為sk+1。

在迭代過程中，對偶殘差sk+1和原始殘差rk+1收斂到0。一個合理的終止準則可以做如下選擇：, 其中，εpri和εdual定義為：

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

三分解模型求解算法：

1.輸入:觀測數據D,參數λ、γ、εabs、εrel，進行初始化：

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

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

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

4 實驗

為了驗證算法的性能，將提出的算法應用于視頻背景建模和人臉圖像數據的恢復，作為對比，同時采用了其他典型算法如RPCA、RPCA-Lp[24]和DNMD。

4.1 參數分析

為了分析模型中的參數影響，以視頻監控的背景建模為例。背景建模是計算機視覺應用中非常重要的主題。對于一段視頻，將其中的每一幀拉成一個列向量，然后按列排成一個矩陣，記為X；通過各種算法對X中的背景和目標進行恢復。

Tri-Decom的兩個參數λ和γ分別用于在噪聲項和干凈數據項之間保持平衡。作為評估不同參數值影響的說明性示例，使用100幀并將每一幀堆疊到矩陣X中，矩陣X的大小為4 800×100；接著通過Tri-Decom檢測前景目標，實驗結果如圖2所示。

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

4.2 視頻背景建模

背景建模是從視頻的背景中抽取出活動行為（也稱前景目標）。背景建模在事件監測、人體行為識別中都扮演著重要角色[25]。

實驗使用九段視頻[26]（http://perception.i2r.a-star.edu.sg/bk_model）。對于每段視頻，使用200幀，每幀的大小為60×80。將這些幀堆疊到矩陣X中，矩陣X的大小為4 800×200。為了進行量化評估，使用F-score來測量恢復精度，F-score定義如下：

其中，precision=|G?T||T|,recall=|G?T||G|，G是真實行為，T是恢復后的行為。

Fig.2 Measure values of 3 decomposition terms versus different parameters圖2 在不同參數下三個分量的測量值

實驗具體指標結果見表1，F-score值越大，代表行為恢復得越準確。從表1可以看出，在大多數情況下，Tri-Decom明顯優于其他方法，這驗證了Tri-Decom對背景提取的有效性。圖3顯示本文方法的恢復結果。這里需要指出的是，為實現可視化，將恢復的活動和非稀疏噪聲中的像素值進行了二值化處理。

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

Table 1 F-score on 9 video surveillance表1 九段不同監控場景下的F-score值

4.3 人臉圖像恢復

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

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

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

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

Fig.3 Background modeling from video surveillance圖3 監控視頻的背景建模

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

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

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

最后表2中列出了在Extended Yale B數據集上算法計算時間的比較，由于Tri-Decom優化變量多于RPCA，導致時間略高于RPCA，由于RPCA-Lp求解一個非凸問題，耗時最長，而DNMD迭代中比Tri-Decom更頻繁進行奇異值分解，也需要較多時間。

5 結論

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