趙奉營(yíng) 楊宏偉 趙麗娜*

(北京化工大學(xué)1.數(shù)理學(xué)院;2.信息中心, 北京 100029)

引 言

魯棒主成分分析(RPCA)是低秩恢復(fù)問題的一種。 Candès 等[1]提出基于矩陣的RPCA 方法(matrix RPCA, MRPCA),能夠從被稀疏大噪聲損壞的觀測(cè)數(shù)據(jù)中恢復(fù)出隱含的低秩分量;MRPCA 將觀測(cè)數(shù)據(jù)分解為低秩分量和稀疏分量,用矩陣核范數(shù)約束低秩分量,矩陣范數(shù)約束稀疏分量。 該模型簡(jiǎn)單且易于求解,被廣泛應(yīng)用在視覺處理任務(wù)中,如圖像恢復(fù)和背景建模[1-2]。 但是MRPCA 方法會(huì)將觀測(cè)數(shù)據(jù)矩陣化,這樣的預(yù)處理步驟會(huì)導(dǎo)致不必要的信息損失,帶來次優(yōu)的恢復(fù)結(jié)果。 針對(duì)此問題,許多基于張量的RPCA 方法被相繼提出,如基于Tucker 分解[3]的求和核范 數(shù)(sum nuclear norm,SNN) 模型[4]、基于張量火車分解[5]的張量火車核范數(shù)(tensor train nuclear norm,TTNN)模型[6]和基于張量環(huán)(tensor ring,TR) 分解的魯棒張量環(huán)補(bǔ)全(robust tensor ring completion,RTRC)模型[7]等。 為了刻畫張量不同模型之間的相關(guān)性,研究者們?cè)赟NN、TTNN 和RTRC 中通過特殊的矩陣化策略將張量展開為一組矩陣,提出了可用交替方向乘子算法(ADMM) 求解的張量魯棒主成分分析(tensor-RPCA,TRPCA)模型。 Kilmer 等[8]提出了一種新的張量乘法t 積(tensor-tensor product)和張量奇異值分解(tensor singular value decomposition,t-SVD)策略。 在t 積和t-SVD 的張量框架下,Lu 等[2]提出了張量核范數(shù)(tensor nuclear norm,TNN)概念,Zhou等[9]提出了張量低秩表示(low rank tensor representation,LRTR)模型。 在TNN 和LRTR 模型中,以基于t 積的張量核范數(shù)t-TNN 作為tubal 秩的凸包絡(luò),t-TNN 等價(jià)于張量的所有前切片組成的塊循環(huán)矩陣的核范數(shù)或者張量按模3 方向作離散傅里葉變換所得張量的所有前切片組成的塊對(duì)角矩陣的核范數(shù),因此t-TNN 可以看作一種特殊的矩陣化方式,用來刻畫張量的空間信息和第三通道的相關(guān)性。 此外,t-SVD 可以利用快速傅里葉變換加速計(jì)算,并且tubal 秩可以描述張量子空間結(jié)構(gòu)。 上述模型在圖像恢復(fù)和背景建模中取得了較好的效果,但是對(duì)輸入數(shù)據(jù)低秩結(jié)構(gòu)的強(qiáng)依賴性問題仍然沒有得到解決。

針對(duì)上述問題,本文在t 積和t-SVD 的張量框架下提出一個(gè)增強(qiáng)的張量魯棒主成分分析模型(E-TRPCA)用于圖像恢復(fù)和背景建模。 首先學(xué)習(xí)得到一個(gè)字典張量,并構(gòu)造了一個(gè)增強(qiáng)的張量核范數(shù)(E-TNN)正則項(xiàng);其次,在低秩張量表示的基礎(chǔ)上,提出了一個(gè)去隨機(jī)噪聲的模型;最后,設(shè)計(jì)了一個(gè)高效的交替方向乘子算法來解決所提出的問題。在圖像恢復(fù)和背景建模上的實(shí)驗(yàn)證明了所提方法的優(yōu)越性。

1 張量奇異值分解框架

1.1 符號(hào)說明

給定 張量A ∈Rh×w×s,A(1,:,:)、A(:,1,:)以 及A(:,:,1)分別是A 的第一個(gè)橫切片、第一個(gè)側(cè)切片和第一個(gè)前切片,Ai,j,k是A 在(i,j,k)位置的元素。unfold()運(yùn)算將張量展開為矩陣,fold()運(yùn)算是其逆運(yùn)算。

A=fft(A,[],3)記為對(duì)A 的每個(gè)管道的離散傅里葉變換。

bcirc()運(yùn)算是將張量A 變?yōu)閴K循環(huán)矩陣的運(yùn)算

1.2 t 積和張量奇異值分解

定義1(t 積) 給定張量A ∈Rh×l×s,B ∈Rl×w×s,則t 積定義為[8]

定義2(正交張量) 如果Q∈Rn×n×l滿足QT*Q = Q*QT= I∈Rn×n×l,則Q 為正交張量。 進(jìn)一步,如果Q∈Rp×q×l滿足QT*Q=I∈Rq×q×l,則Q 為部分正交張量。

定義3(張量奇異值分解)[2]給定張量A∈Rh×w×s,它可以分解為如下形式

式中,U∈Rh×h×s,V∈Rw×w×s是正交張量,S∈Rh×w×s是f-diagonal張量。

定義4(管道秩) 給定張量A∈Rh×w×s,則張量的管道秩為S 中非零管道的個(gè)數(shù)[10],記為rankt(A)

式中,A=U*S*VT是A 的t-SVD 分解。

定義5(張量核范數(shù))[2]A =U*S*VT是A 的t-SVD,A∈Rh×w×s,則A 的核范數(shù)表示為

其中,r=rankt(A)。

引理1張量A∈Rh×w×s,B∈Rw×h×s,令F =A*B,則有:

引理2[11]?A∈Rm×n,則問題

根據(jù)引理1,本文給出了引理2 的張量推廣形式。

定理1任給張量A∈Rh×w×s,問題

證明由引理1 以及的塊對(duì)角結(jié)構(gòu)可知,問題(2)可以分解為以下子問題

2 E-TRPCA 方法

2.1 基于t-SVD 的E-TRPCA 模型

如圖1 所示,矩陣可以分解為兩個(gè)矩陣的積[12]

圖1 低秩分解Fig.1 Low-rank factorization

借助t 積,可以把矩陣的情形推廣到張量情形

事實(shí)上,如果對(duì)V 施加一個(gè)正交約束,則有U=L*V。 與傳統(tǒng)的核范數(shù)最小化(nuclear norm minimization,NNM)問題相同,對(duì)分量U施加低秩約束,則可以構(gòu)造如下E-TNN 正則項(xiàng)

第一個(gè)是約束在變換結(jié)果L*V 上的Frobenius范數(shù),這有助于避免變換引起的信息損失;第二個(gè)是對(duì)V 的正交約束,傾向于使變換后的結(jié)果L*V 盡可能保留低秩張量L 的信息,此外它還可以幫助獲得該變量的閉式解。 由于不容易直接求解上述問題,因此將式(6)重新表述為以下等價(jià)問題

與TNN 一樣,E-TNN 同樣作用在分量L 上,不同之處在于E-TNN 不直接約束L 本身,而是約束從L 中學(xué)習(xí)得到的一組基,這組基是L 的所有側(cè)切面的一個(gè)線性表示[9]。 矩陣分解可以把矩陣分解為字典和稀疏矩陣的積,因此,借助上述張量工具,把分量L 分解為字典張量U 和投影張量V 的共軛轉(zhuǎn)置的乘積。 字典張量U 由分量L 經(jīng)過正交變換得到:U = L*V,V 是正交變換張量,維度為w×r×s,r＜w。 另外,字典張量U 的規(guī)?？偸切∮诘椭确至縇,這使得它們受到噪聲損壞的影響較小,從而可以獲得更魯棒的恢復(fù)效果。

將E-TNN 正則項(xiàng)嵌入到TRPCA 模型,得到如下低秩張量恢復(fù)模型

式中X,L,e∈Rh×w×s分別為觀測(cè)張量、低秩張量和稀疏張量,l1范數(shù)來約束稀疏張量,λ為超參數(shù)。

2.2 ADMM 優(yōu)化

本節(jié)中,通過ADMM 算法[13]求解模型(8)。 由模型(8)得到以下增廣拉格朗日函數(shù)。

式中,μ為懲罰項(xiàng)系數(shù)。 ADMM 可以把上述問題分解為如下的5 個(gè)子問題,在每一個(gè)子問題中,固定其余變量不變,只更新一個(gè)變量。

L 子問題 從式(9)中找出所有包含L 的項(xiàng),得到如下更新公式

U 子問題 從式(9)中找出所有包含U 的項(xiàng),得到如下問題

這個(gè)子問題可以通過張量奇異值閾值算子[2]求解

V 子問題 從式(9)中找出所有包含V 的項(xiàng),令P=L+,得到如下問題

由定理1 可知

e 子問題 從式(9)中找出所有包含e 的項(xiàng),得到如下問題

這個(gè)子問題可以通過軟閾值收縮算子[14]來得到閉式解

拉格朗日乘子 y1,y2通過如下公式來更新

綜上所述,求解E-TRPCA 模型(8)的ADMM算法(算法1)詳細(xì)過程如下。

2.3 復(fù)雜度分析

算法1 以三階張量X∈Rh×w×s作為輸入,主要的計(jì)算成本是在更新U,V 時(shí)產(chǎn)生的。 更新U 需要計(jì)算一個(gè)大小為h×w×s張量的t-SVD,更新V時(shí)需要計(jì)算一個(gè)大小為w×r×s張量的t-SVD,那么算法1 的時(shí)間復(fù)雜度為O(max(h,w)rslogs+(max(h,w)r2s))。

3 實(shí)驗(yàn)驗(yàn)證

以圖像恢復(fù)作為仿真實(shí)驗(yàn)、背景建模作為真實(shí)實(shí)驗(yàn)來測(cè)試所提方法,并與RPCA 方法[1]、基于Tucker 分解的SNN 方法[4]、基于t-SVD 的TNN 方法[2]、基于張量火車分解的TTNN 方法[6]和基于張量環(huán)分解的RTRC 方法[7]這5 種方法進(jìn)行對(duì)比。 其中,RTRC 方法被用來解決張量補(bǔ)全問題,在本文中用于張量魯棒主成分分析,記為TRNN(tensor ring nuclear norm)。 圖像恢復(fù)實(shí)驗(yàn)中的圖片和背景建模中的視頻分別用三階張量和四階張量存儲(chǔ),它們的值均被縮放到[0,1]。

3.1 圖像恢復(fù)

使用伯克利分割數(shù)據(jù)集[15]中的彩色圖像進(jìn)行測(cè)試。 圖片的大小為321 ×481 ×3 或481 ×321 ×3。 RPCA、TNN、TRNN 和本文方法可以直接處理三階張量,TTNN 方法在數(shù)據(jù)輸入模型之前采用ketaugmentation (KA)技術(shù)作了數(shù)據(jù)增強(qiáng)處理,因此需要把圖片大小調(diào)整為320×480×3,再利用KA 方法將圖片尺寸轉(zhuǎn)化為[4×4×4×5×4×4×5×6×3]。

噪聲模擬 本文主要去除圖像中的隨機(jī)噪聲,隨機(jī)噪聲比例p分別設(shè)為0.1、0.2、0.3,以p=0.1為例,即圖像有10%的像素被設(shè)為區(qū)間[0,1]之間的一個(gè)隨機(jī)值,被破壞的像素的位置是隨機(jī)的。

評(píng)價(jià)指標(biāo) 為了評(píng)價(jià)比較方法去除隨機(jī)噪聲的性能,選取峰值信噪比(peak signal-to-noise ratio,PSNR)和結(jié)構(gòu)相似度(structural similarity index,SSIM)作為評(píng)價(jià)指標(biāo)[16],PSNR 值和SSIM 值越高,表示恢復(fù)結(jié)果越好。

圖2 p=0.1,0.2,0.3 時(shí),PSNR 值隨λ 的變化曲線Fig.2 PSNR values changing with λ for p=0.1,0.2,0.3

Tubal 秩r用于刻畫圖像的低秩性。 本文通過遍歷r來分析tubal 秩對(duì)PSNR 的影響。 由圖3(b)可知,隨著r的增大,圖像的恢復(fù)效果也越來越好。為了在效率和性能之間取得一個(gè)平衡,將r設(shè)為。

圖3 管道秩對(duì)PSNR 值的影響Fig.3 The effect of tubal rank on PSNR value

1)視覺效果比較

為了直觀地對(duì)比圖像的恢復(fù)結(jié)果,從伯克利分割數(shù)據(jù)集中選取了6 張示例圖片進(jìn)行可視化展示。從圖4 ～9 中可以看出,RPCA、SNN、TTNN 和TRNN算法雖然能夠去除圖片中的隨機(jī)噪聲和椒鹽噪聲,但這4 種方法不能很好地保留圖像中的細(xì)節(jié)。圖4(h) ～9(h)展示了本文所提模型的恢復(fù)結(jié)果,可以看到添加的噪聲被去除,并且圖像中的紋理和邊緣也得到了很好的保留。 這說明本文提出的E-TNN正則項(xiàng)要比t-SVD 張量框架下的張量核范數(shù)更有效。

圖4 所有對(duì)比方法在示例圖片1 下的恢復(fù)結(jié)果(p=0.1)Fig.4 Restoration results of all competing methods for example image 1(p=0.1)

圖5 所有對(duì)比方法在示例圖片2 下的恢復(fù)結(jié)果(p=0.1)Fig.5 Restoration results of all competing methods for example image 2(p=0.1)

圖6 所有對(duì)比方法在示例圖片3 下的恢復(fù)結(jié)果(p=0.1)Fig.6 Restoration results of all competing methods for example image 3(p=0.1)

圖7 所有對(duì)比方法在示例圖片4 下的恢復(fù)結(jié)果(p=0.1)Fig.7 Restoration results of all competing methods for example image 4(p=0.1)

圖8 所有對(duì)比方法在示例圖片5 下的恢復(fù)結(jié)果(p=0.1)Fig.8 Restoration results of all competing methods for example image 5(p=0.1)

2) 定量結(jié)果比較

表1 ～3 分別是6 張示例圖片在不同隨機(jī)噪聲比例p=0.1、0.2、0.3 下的PSNR 值和SSIM 值。 可以看出,本文所提模型的PSNR 評(píng)價(jià)指標(biāo)在所有的噪聲比例中都取得了最好的結(jié)果,而且在SSIM 評(píng)價(jià)指標(biāo)上也基本上取得了最優(yōu)或次優(yōu)的結(jié)果。

圖10 給出了在p=0.1 時(shí)伯克利分割數(shù)據(jù)集50張圖片的PSNR 值和運(yùn)行時(shí)間的比較。 可以看出,與其他幾種算法相比,本文所提方法取得的PSNR值最高,并且運(yùn)行所需時(shí)間也僅次于TRNN 方法,遠(yuǎn)低于其他方法。

圖10 各對(duì)比方法在伯克利分割數(shù)據(jù)集50 張圖像上的定量結(jié)果比較Fig.10 Quantitative comparison of all competing methods on 50 images of the Berkeley segmentation dataset

此外,由表1 ～3 可知,在示例圖片1 和示例圖片5 中,所有方法都沒有取得比較好的恢復(fù)效果,而示例圖片4 和示例圖片6 的恢復(fù)效果較好。

表1 各對(duì)比方法在p=0.1 下的PSNR 和SSIM 值比較Table 1 Comparison of the PSNR and SSIM values obtained using all competing methods with p=0.1

表2 各對(duì)比方法在p=0.2 下的PSNR 和SSIM 值比較Table 2 Comparison of the PSNR and SSIM values obtained using all competing methods with p=0.2

表3 各對(duì)比方法在p=0.3 下的PSNR 和SSIM 值比較Table 3 Comparison of the PSNR and SSIM values obtained using all competing methods with p=0.3

RPCA、SNN、TNN、TTNN、TRNN 等方法都假設(shè)數(shù)據(jù)具有低秩結(jié)構(gòu),對(duì)低秩性有強(qiáng)依賴性。 我們發(fā)現(xiàn),對(duì)于結(jié)構(gòu)比較復(fù)雜、紋理較為豐富的示例圖片5(圖11(a)),其張量奇異值并沒有迅速接近于0(圖11(b)),這表明其tubal 秩相對(duì)較大,上述方法難以取得好的恢復(fù)效果。 而在背景空曠的示例圖片6 (圖11(c))中,其奇異值則迅速接近于0(圖11(d)),表明tubal 秩較小,上述方法可以取得較好的恢復(fù)效果。 對(duì)此,本文新增了一個(gè)參數(shù)r用于控制tubal 秩對(duì)數(shù)據(jù)恢復(fù)效果的影響,ETRPCA模型中的λ參數(shù)可以協(xié)調(diào)核范數(shù)正則項(xiàng)和l1正則項(xiàng),參數(shù)r則可以進(jìn)一步控制核范數(shù)正則項(xiàng)。 由圖3 可知,當(dāng)隨機(jī)噪聲比例p=0.1 時(shí),在不改變其他參數(shù)的情況下,r從0 增加300,PSNR 也從25 增加到42,這為處理不同場(chǎng)景的圖像提供了一個(gè)優(yōu)化手段。

圖11 不同圖片的奇異值分布Fig.11 Singular value distribution of different images

為了更好地評(píng)估本文模型的泛化性,圖12 給出了r=150 和r=300 兩種情況下本文方法與其他5種方法的PSNR 值比較。 從圖中可以看出,當(dāng)r取150 和300 時(shí),本文所提方法取得的PSNR 值都要高于RPCA、SNN、TNN、TTNN 和TRNN 方法,而且r=300 時(shí)所得的結(jié)果要好于r=150 時(shí)的結(jié)果。 這說明在數(shù)據(jù)是否具有低秩性的先驗(yàn)信息未知的情況下,本文所提方法具有較好的泛化性。

圖12 r=150,300 時(shí),50 張圖片的PSNR 值Fig.12 PSNR values of 50 images for r=150,300

3.2 背景建模

視頻的前景和背景分離任務(wù)一直以來都是研究的熱點(diǎn)。 視頻由連續(xù)的幀圖像序列組成,其中結(jié)構(gòu)穩(wěn)定、變動(dòng)很小的場(chǎng)景內(nèi)容是視頻的背景。由于背景之間的相關(guān)性,可以將其視作一個(gè)低秩分量,而在視頻中所占像素較小且變動(dòng)顯著的物體,如汽車或行人,即為視頻的前景,可以視為稀疏分量。 本文選取了driverway(117 幀)[17]和shop(100 幀)[18]兩個(gè)視頻。 在RPCA 算法中,將視頻張量h×w× 3 ×f展開為矩陣hw× 3f;在SNN、TNN、TRNN 算法中,將視頻張量的大小轉(zhuǎn)化為hw×3 ×f;在本文所提方法中,將視頻張量轉(zhuǎn)化為hw×f×3,f表示視頻的幀數(shù)。

表4 為RPCA、SNN、TNN、TRNN 和本文方法運(yùn)行時(shí)間的比較,圖13 ～16 給出了5 種方法在兩個(gè)視頻上的結(jié)果(TTNN 方法難以找到一個(gè)合適的KA參數(shù),故不參與比較)。 可知5 種方法都可以將運(yùn)動(dòng)的行人從背景中提取出來,但本文方法的用時(shí)最短。

圖13 driverway 視頻的背景圖像Fig.13 Background image for driveway video

表4 運(yùn)行時(shí)間比較Table 4 Running time comparison

3.3 去除高斯噪聲

本文在原有模型的基礎(chǔ)上新增了一個(gè)正則項(xiàng)‖N‖21來刻畫高斯噪聲。 通過最小化核范數(shù)、l1范數(shù)和l21的組合,分離出被混合噪聲破壞的干凈數(shù)據(jù)。

l21范數(shù)定義如下。

此時(shí),模型(8)可以改寫為

模型(18)的增廣拉格朗日函數(shù)為

圖14 driverway 視頻的前景圖像Fig.14 Foreground image for driveway video

圖15 shop 視頻的背景圖像Fig.15 Background image for shop video

圖16 shop 視頻的前景圖像Fig.16 Foreground image for shop video

式(19)依然采取ADMM 算法求解,與算法1 相比,求解模型(8)多出一個(gè)子問題,即求解‖N‖21子問題,該子問題可以寫成如下格式。

本文將模型(18)應(yīng)用于圖片恢復(fù)。 圖17 給出了本文方法去除混合噪聲的可視化結(jié)果。 圖17(b)是添加了均值為0、方差為0.05 的高斯噪聲和隨機(jī)噪聲比例p=0.2 的示例圖片2。 從圖17(c) ～(e)可以看出,圖像的低秩部分、隨機(jī)噪聲部分和高斯噪聲部分都被很好地分離出來。

圖17 混合噪聲去除Fig.17 Mixture noise removal

4 結(jié)束語(yǔ)

本文引入了增強(qiáng)的TNN 正則項(xiàng)(E-TNN),提出一種增強(qiáng)的TRPCA 模型。 與TNN 相比,E-TNN能夠在張量數(shù)據(jù)的子空間投影上計(jì)算低秩性,可刻畫張量數(shù)據(jù)中各成分的相關(guān)性和差異,從而更真實(shí)地反映張量數(shù)據(jù)的潛在低秩結(jié)構(gòu)。 與張量魯棒主成分分析方法相比,本文所提算法可以有效地恢復(fù)出被噪聲破壞的圖像,并縮短運(yùn)行所需時(shí)間。 下一步可以基于不同維度的張量數(shù)據(jù)自動(dòng)調(diào)整字典張量的維度。 此外,基于廣義線性變換的t 積張量框架在張量低秩恢復(fù)問題中的應(yīng)用將是未來的研究方向之一。