錢 陽(yáng)，李 雷，石曼曼

(南京郵電大學(xué) 視覺認(rèn)知計(jì)算與應(yīng)用研究中心，江蘇 南京 210023)

基于雙稀疏字典的新型盲壓縮感知模型

錢 陽(yáng)，李 雷，石曼曼

(南京郵電大學(xué) 視覺認(rèn)知計(jì)算與應(yīng)用研究中心，江蘇 南京 210023)

針對(duì)壓縮感知理論實(shí)際應(yīng)用過程中，稀疏基先驗(yàn)信息未知的情況下，如何從信號(hào)的壓縮測(cè)量值中學(xué)習(xí)與待重構(gòu)信號(hào)本身相適應(yīng)的字典的同時(shí)，利用該字典重構(gòu)出原始信號(hào)的問題，基于已有的盲壓縮感知理論(BCS)，在稀疏基為雙稀疏字典結(jié)構(gòu)的約束條件下，提出了一種新型的盲壓縮感知算法(D-BCS)。所提算法交替執(zhí)行稀疏編碼階段和字典更新階段。在稀疏編碼階段，采用分裂Bregman迭代求解非凸的l1最小化問題，從而實(shí)現(xiàn)稀疏系數(shù)矩陣的更新；而在字典更新階段，則通過將目標(biāo)優(yōu)化函數(shù)轉(zhuǎn)化為類LASSO問題，并利用LASSO算法來實(shí)現(xiàn)字典原子的逐列更新。在不同采樣率下，對(duì)多個(gè)測(cè)試視頻幀進(jìn)行仿真對(duì)比實(shí)驗(yàn)，實(shí)驗(yàn)結(jié)果表明，所提算法能很好地從壓縮測(cè)量值中恢復(fù)出原始信號(hào)，且表現(xiàn)出了最佳的性能改進(jìn)。

盲壓縮感知；雙稀疏字典；分裂Bregman迭代；LASSO；稀疏表示

0 引 言

近年來，以信號(hào)的稀疏性先驗(yàn)求解圖像反問題吸引著學(xué)者們的廣泛關(guān)注[1-2]，尤其是壓縮感知(Compressed Sensing,CS)領(lǐng)域[3]。CS理論主要包括信號(hào)的稀疏表示、觀測(cè)矩陣的選取和信號(hào)重構(gòu)這三個(gè)階段。其中，稀疏表示是壓縮感知理論應(yīng)用的前提和基礎(chǔ)，它決定了圖像反問題的求解質(zhì)量。目前，稀疏化方法主要分為兩種：解析方法和學(xué)習(xí)方法。前者是基于固定正交基的變換，如DCT變換、傅里葉變換等；而后者則是根據(jù)信號(hào)本身來學(xué)習(xí)過完備字典，再對(duì)信號(hào)進(jìn)行稀疏化，如K-SVD字典學(xué)習(xí)算法[4]?，F(xiàn)有的CS算法一般都是建立在稀疏基已知的先驗(yàn)條件下，因此信號(hào)的先驗(yàn)信息至關(guān)重要。然而，在實(shí)際應(yīng)用過程中，信號(hào)的信息往往無法被事先獲知，能否根據(jù)信號(hào)的測(cè)量值學(xué)習(xí)與待重構(gòu)信號(hào)本身相適應(yīng)的字典并利用該字典重構(gòu)出原始信號(hào)，是壓縮感知領(lǐng)域急需解決的問題[5]。

近幾年，Gleichman等[6]提出的盲壓縮感知(Blind Compressed Sensing,BCS)理論，為稀疏表示領(lǐng)域的研究提供了一個(gè)全新的視野。該理論的思想是省略了信號(hào)的稀疏表示過程，在采樣和重構(gòu)階段避免對(duì)信號(hào)先驗(yàn)知識(shí)的完全掌握，而是通過對(duì)稀疏基施加適當(dāng)?shù)募s束條件來實(shí)現(xiàn)信號(hào)的唯一重構(gòu)。目前，對(duì)BCS的研究仍處于理論發(fā)展初期，只有少量的文獻(xiàn)給出了直接根據(jù)測(cè)量值訓(xùn)練字典的具體算法，如CK-SVD(Compressive K-SVD)[7]算法和CDL(Compressive Dictionary Learning)[8]算法，這兩種算法均是基于稀疏基為雙稀疏字典的約束條件來實(shí)現(xiàn)信號(hào)的唯一重構(gòu)。

基于已有的BCS理論，在稀疏基為雙稀疏字典的約束條件下，提出了一種新型的盲壓縮感知算法(D-BCS)。該算法交替執(zhí)行稀疏編碼階段和字典更新階段，在稀疏編碼階段，利用Split Bregman迭代對(duì)稀疏表示系數(shù)矩陣進(jìn)行求解，而在字典更新階段，將字典更新優(yōu)化問題通過誤差最小準(zhǔn)則轉(zhuǎn)化為可用LASSO求解的最小化問題，從而實(shí)現(xiàn)字典原子的更新。將所提算法用于視頻幀圖像的重構(gòu)中，實(shí)驗(yàn)結(jié)果表明，該算法能有效地從壓縮測(cè)量值中重構(gòu)出視頻幀，且重構(gòu)性能較好。

1 背景知識(shí)

1.1 盲壓縮感知模型

(1)

其中，‖‖0為l0范數(shù)，表示向量中非零元素的個(gè)數(shù)。

s.t.?i,‖ai‖0≤T0

(2)

其中，T0為稀疏表示系數(shù)中非零分量數(shù)目的上限。

通過引入正則化參數(shù)λA，式(2)可以轉(zhuǎn)化為無約束最優(yōu)化問題：

(3)

由于l0范數(shù)模型是NP難題[12]，在多項(xiàng)式時(shí)間內(nèi)只能求得次優(yōu)解。一種最常用的做法是采用l1范數(shù)來最佳凸逼近l0范數(shù)，則BCS模型可轉(zhuǎn)化為如下的優(yōu)化問題

(4)

其中，‖‖1為l1范數(shù)，表示向量中所有元素的絕對(duì)值之和。

然而，BCS的信號(hào)重構(gòu)問題(4)在數(shù)學(xué)上是一個(gè)嚴(yán)重的病態(tài)問題，必須給字典D施加額外的約束條件，才能保證信號(hào)的唯一性重構(gòu)。文獻(xiàn)[6]中討論了三種情況：D為從已知的正交基中根據(jù)重構(gòu)殘差最小準(zhǔn)則選擇出的一個(gè)正交基；D為雙稀疏字典；D具有正交對(duì)角結(jié)構(gòu)化特點(diǎn)。此外，Silva等研究了另一種情況：D為多個(gè)子字典的聯(lián)合，且每個(gè)子字典的原子相互正交，待恢復(fù)的信號(hào)只用其中的某個(gè)子字典表示。若字典D滿足以上4個(gè)條件之一且觀測(cè)矩陣Φ滿足相應(yīng)的條件，則BCS有唯一解。

1.2 分裂Bregman迭代算法(SBI)

由Goldstein等[13]提出的分裂Bregman迭代算法，最初是用來解決TV-L1模型的圖像擴(kuò)散問題。該算法結(jié)合了Split算法和Bregman迭代的優(yōu)點(diǎn)，能夠在提高圖像處理質(zhì)量的同時(shí)保證高效的計(jì)算效率，在圖像處理領(lǐng)域應(yīng)用極其廣泛[14-15]。

SBI算法解決的是如下的約束優(yōu)化問題：

(5)

其中，G∈RN×M，f:RN→R，g:RM→R是凸函數(shù)。

SBI算法對(duì)問題(5)的具體求解步驟如下：

初始化:設(shè)置t=0，b0=0，u0=0，v0=0，選擇參數(shù)μ>0

Repeat

b(t+1)=b(t)-(u(t+1)-Gv(t+1))

t←t+1

Until滿足停止迭代條件

1.3 雙稀疏字典

雙稀疏字典結(jié)構(gòu)是在一個(gè)已知基字典的基礎(chǔ)上再構(gòu)造一個(gè)具有稀疏原子的字典，即定義：D=ΨΘ。其中，Ψn×n是一個(gè)基字典，Θn×k(n≤k)是字典結(jié)構(gòu)的稀疏表示系數(shù)矩陣。該模型表明字典的每個(gè)原子都有它相應(yīng)的在某個(gè)指定基字典上的稀疏表示。對(duì)于Θ的構(gòu)造，顯而易見，若Θ為單位矩陣，則字典D退化為普通基。與文獻(xiàn)[8]一樣，將Θ定義為如下形式：

(6)

其中，δ=k-n；約束Θ(或Σ)為稀疏矩陣。

文獻(xiàn)[8]指出，這種約束能以任意形式保存所學(xué)習(xí)的字典且使字典不易受過匹配的影響。

2 算法設(shè)計(jì)與分析

所提基于雙稀疏字典的新型盲壓縮感知算法的數(shù)學(xué)模型如式(7)所示：

(7)

其中,λΘ為正則化參數(shù)。

與字典學(xué)習(xí)方法類似，可以通過交替執(zhí)行稀疏編碼階段和字典更新階段來求得此優(yōu)化模型的最優(yōu)解。

2.1 稀疏編碼階段

該階段對(duì)壓縮測(cè)量值的稀疏表示系數(shù)A進(jìn)行求解。此階段，固定雙稀疏字典D(t)，亦即固定字典結(jié)構(gòu)的稀疏表示系數(shù)矩陣Θ(t)，其所求優(yōu)化模型如式(8)所示：

(8)

對(duì)于式(8)的求解，采用上一節(jié)中介紹的分裂Bregman迭代法。通過引入變量u，首先將式(8)轉(zhuǎn)化為等價(jià)的約束形式：

s.t.u=ΨΘA

(9)

(10)

(11)

b(t+1)=b(t)-(u(t+1)-ΨΘ(t)A(t+1))

(12)

因此，最小化問題(8)的求解進(jìn)一步轉(zhuǎn)化為對(duì)子問題u和A的求解。接下來，將分別給出兩個(gè)子問題的具體求解過程。

2.1.1u子問題

給定Θ(t)和A(t)，不難看出，u子問題是一個(gè)關(guān)于u的最小二乘問題，其有解析解，通過簡(jiǎn)單的計(jì)算，可以得到：

(13)

(14)

將式(14)代入式(10)中，則有：

(15)

式(15)是一個(gè)簡(jiǎn)單的最小二乘問題，且其解析解為：

(16)

2.1.2A子問題

給定u(t+1)，根據(jù)式(11)，A子問題可演變成如下形式：

(17)

其中，r(t+1)=u(t+1)-b(t)。

其中，正則化參數(shù)λA的選取依賴于壓縮樣本的噪聲水平以及待重構(gòu)圖像的復(fù)雜度。當(dāng)λA取值較大時(shí)，A(t+1)中只能包含圖像塊的重要組成部分，這對(duì)高噪聲情況非常適用；而當(dāng)λA取值較小時(shí)，稀疏表示系數(shù)A(t+1)中將會(huì)包含每個(gè)圖像塊過多的細(xì)節(jié)信息，這些冗余的細(xì)節(jié)信息將會(huì)使得學(xué)習(xí)過程混亂，且容易導(dǎo)致算法發(fā)散。因此，選擇合適的正則化參數(shù)λA至關(guān)重要。

不難發(fā)現(xiàn)，式(17)是一個(gè)典型的LASSO求解[17]問題，可以采用LASSO算法對(duì)其進(jìn)行求解。

2.2 字典更新階段

字典更新階段，即固定稀疏表示系數(shù)A(t+1)，通過求解相應(yīng)的優(yōu)化函數(shù)來實(shí)現(xiàn)雙稀疏字典D的更新。由于D=ΨΘ，且Ψ是一個(gè)事先選定好的基字典，故此階段即為對(duì)字典結(jié)構(gòu)的稀疏表示系數(shù)矩陣Θ的更新。其所求優(yōu)化模型如式(18)所示：

(18)

(19)

將式(19)代入式(18)，且由于式(6)中對(duì)Θ的特殊定義，因此對(duì)矩陣Θ的更新則轉(zhuǎn)變?yōu)閷?duì)矩陣∑中原子的逐列更新：

(20)

Rubinstein在文獻(xiàn)[18]中指出，可以用式(21) 來替代式(20)中的保真項(xiàng)：

(21)

從而，式(20) 轉(zhuǎn)變?yōu)槿缦碌腖ASSO問題：

(22)

可以采用LASSO算法對(duì)其進(jìn)行求解，進(jìn)一步實(shí)現(xiàn)字典原子的更新。

2.3 D-BCS算法流程

基于前面的分析，將給出D-BCS算法的實(shí)現(xiàn)流程，如下所示：

輸入：CS觀測(cè)值Y，觀測(cè)矩陣Φ，基字典Ψ，λA，λΘ，μ，τ

初始化：Σ(0)=In×n，t=0，u(0)=0，b(0)=0

Repeat

(1)稀疏編碼階段。

根據(jù)式(16)更新u(t+1)

r(t+1)=u(t+1)-b(t)

使用LASSO算法求解式(17)，獲得稀疏表示系數(shù)矩陣A(t+1)

(2)字典更新階段。

根據(jù)式(22)，利用LASSO算法逐列更新Σ(t+1)

t←t+1

Until滿足停止迭代條件

3 實(shí)驗(yàn)及分析

選用格式為CIF的標(biāo)準(zhǔn)視頻序列Foreman進(jìn)行實(shí)驗(yàn)仿真，隨機(jī)選取Foreman的第1、6、10、15、23幀作為測(cè)試樣本集，如圖1所示。

圖1 測(cè)試圖像集

實(shí)驗(yàn)中將大小為352×288的視頻幀分成不重疊8×8的圖像塊，利用高斯隨機(jī)矩陣對(duì)每個(gè)圖像塊進(jìn)行觀測(cè)，以獲得CS觀測(cè)值。設(shè)置所訓(xùn)練的字典原子數(shù)為256，最大迭代次數(shù)為30，λA=λΘ=0.1，μ=2.5×10-3。實(shí)驗(yàn)平臺(tái)為ThinkPadX1Carbon3rd,Windows7,Intel(R)Core(TM)i7-5600UCPU,2.6GHz,8GB，基于MatlabR2011a編程實(shí)現(xiàn)。

采用傳統(tǒng)的CS算法(稀疏基分別為DCT、K-SVD字典，重構(gòu)算法選用OMP)和所提D-BCS算法對(duì)測(cè)試圖像集中的每一視頻幀進(jìn)行重構(gòu)。為了評(píng)估各算法的重構(gòu)質(zhì)量，除了選用PSNR作為評(píng)價(jià)標(biāo)準(zhǔn)外，近年來相關(guān)學(xué)者提出的FSIM[19]可用來衡量重構(gòu)圖像的視覺效果。FSIM值越高，則重構(gòu)圖像的視覺效果越好。實(shí)驗(yàn)中，為了消除隨機(jī)性，每一測(cè)試幀的PSNR與FSIM值均取10次執(zhí)行結(jié)果的平均值。

圖2直觀地給出了不同采樣率下三種算法重構(gòu)視頻幀的PSNR和FSIM的對(duì)比情況，其中PSNR和FSIM的數(shù)值均取五幅測(cè)試幀的平均值。

圖2 三種算法重構(gòu)性能隨采樣率變化圖

從圖2中可以發(fā)現(xiàn)，隨著采樣率的增加，三種算法的重構(gòu)性能都在提升，而所提D-BCS算法的重構(gòu)性能最優(yōu)。這是由于該算法在每次迭代過程中，都先進(jìn)行圖像估計(jì)，然后從所估計(jì)的圖像中更新稀疏表示系數(shù)，進(jìn)一步影響算法的重構(gòu)精度。

此外，圖3給出了采樣率為0.375時(shí)三種算法重構(gòu)出視頻序列Foreman第1幀的視覺效果圖。

圖3從直觀上進(jìn)一步說明了D-BCS算法所表現(xiàn)的優(yōu)越性。

圖3 三種算法重構(gòu)出視頻序列Foreman第1幀的視覺效果圖

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

為了解決在稀疏基先驗(yàn)信息未知的情況下，如何能夠從壓縮測(cè)量值中學(xué)習(xí)字典的同時(shí)重構(gòu)出原始信號(hào)的問題，提出了一種基于雙稀疏字典的新型盲壓縮感知模型。實(shí)驗(yàn)結(jié)果表明，所提算法能很好地從壓縮測(cè)量值中恢復(fù)出原始信號(hào)，且表現(xiàn)出更優(yōu)的性能改進(jìn)。

[1]DonohoDL.Compressedsensing[J].IEEETransactionsonInformationTheory,2006,52(4):1289-1306.

[2]CandèsE,TaoT.Nearoptionalsignalrecoveryfromrandomprojections:universalencodingstrategies[J].IEEETransactionsonInformationTheory,2006,52(12):5406-5425.

[3]DonohoDL,TsaigY.Extensionsofcompressedsensing[J].SignalProcessing,2006,86(3):549-571.

[4]AharonM,EladM,BrucksteinA.K-SVD:analgorithmfordesigningovercompletedictionariesforsparserepresentation[J].IEEETransactionsonSignalProcessing,2006,54(11):4311-4322.

[5] 練秋生,石保順,陳書貞.字典學(xué)習(xí)模型、算法及其應(yīng)用研究進(jìn)展[J].自動(dòng)化學(xué)報(bào),2015,41(2):240-260.

[6]GleichmanS,EldarYC.Blindcompressedsensing[J].IEEETransactionsonInformationTheory,2011,57(10):6958-6975.

[7]AnarakiPF,HughesSM.CompressiveK-SVD[C]//Proceedingsofthe2013IEEEinternationalconferenceonacoustics,speech,andsignalprocessing.Vancouver,Canada:IEEE,2013:5469-5473.

[8]AghagolzadehM,RadhaH.Compressivedictionarylearningforimagerecovery[C]//Proceedingsofthe19thIEEEinternationalconferenceonimageprocessing.Orlando,USA:IEEE,2012:661-664.

[9]BaraniukR.Alectureoncompressivesensing[J].IEEESignalProcessingMagazine,2007,24(4):118-121.

[10]DelgadoKK,MurrayJF,RaoBD,etal.Dictionarylearningalgorithmsforsparserepresentation[J].NeuralComputation,2003,15(2):349-396.

[11]RubinsteinR,BrucksteinA,EladM.Dictionariesforsparserepresentationmodeling[J].ProceedingsoftheIEEE,2010,98(6):1045-1057.

[12] 焦李成，公茂果，王 爽，等.自然計(jì)算、機(jī)器學(xué)習(xí)與圖像理解前沿[M].西安:西安電子科技大學(xué)出版社,2008.

[13]GoldsteinT,OsherS.ThesplitBregmanmethodforl1-regularizedproblems[J].SIAMJournalonImagingSciences,2009,2(2):323-343.

[14]CaiJF,OsherS,ShenZ.SplitBregmanmethodsandframebasedimagerestoration[J].SIAMJournalonMultiscaleModeling&Simulation,2009,8(2):337-369.

[15]LuK,WangQ,HeN,etal.NonlocalvariationalimagesegmentationmodelsongraphsusingtheSplitBregman[J].MultimediaSystems,2015,21(3):289-299.

[16]XiaoYH,YangJF,YuanXM.Alternatingalgorithmsfortotalvariationimagereconstructionfromrandomprojections[J].InverseProblemsandImaging,2012,6(3):547-563.

[17]TibshiraniR.Regressionshrinkageandselectionviathelasso[J].JournaloftheRoyalStatisticalSociety,2011,73(3):273-282.

[18]RubinsteinR,Zibulevsky,EladMM.Doublesparsity:learningsparsedictionariesforsparsesignalapproximation[J].IEEETransactionsonSignalProcessing,2010,58(3):1553-1564.

[19]ZhangL,ZhangL,MouX,etal.FSIM:afeaturesimilarityindexforimagequalityassessment[J].IEEETransactionsonImageProcessing,2012,20(8):2378-2386.

A Novel Blind Compressed Sensing Model Based on DoubleSparsity Dictionary

QIAN Yang,LI Lei,SHI Man-man

(Center for Visual Cognitive Computation and Its Application,Nanjing University of Posts and Telecommunications,Nanjing 210023,China)

Aiming at the problem of simultaneous image recovery and dictionary learning from Compressed Sensing (CS) measurements,where the sparse basis or the dictionary is unknown prior in the practical application of CS theory,in view of the existing Blind Compressed Sensing (BCS) theory,a novel Blind Compressed Sensing (D-BCS) algorithm based on the double sparsity dictionary has been proposed.It is an iterative method that alternates between sparse-coding and dictionary update steps.In the sparse coding stage of the proposed scheme,a split Bregman iteration based technique has been utilized to solve the non-convexl1minimizationproblemtoupdatethesparsecoefficientmatrix.Andinthedictionaryupdatestage,theoptimizationfunctionisconvertedintoaLASSO-likeproblemandthedictionaryatomsareupdatedcolumnbycolumnusingLASSOalgorithm.ComparativesimulationexperimentalresultsofseveraltestvideoframeswithavarietyofsamplingratioshavedemonstratedthattheproposedalgorithmcanrecovertheoriginalsignalfromCSmeasurementsverywellandexhibitsstate-of-the-artperformanceimprovementsinitsabilityforrecoveryofthecompressedvideoframes.

blind compressed sensing;double sparsity dictionary;split Bregman iteration;LASSO;sparse representation

2016-05-22

2016-08-30 網(wǎng)絡(luò)出版時(shí)間：2017-03-13

國(guó)家自然科學(xué)基金資助項(xiàng)目(61070234，61071167，61373137，61501251)；江蘇省2015年度普通高校研究生科研創(chuàng)新計(jì)劃項(xiàng)目(KYZZ15_0235)；南京郵電大學(xué)引進(jìn)人才科研啟動(dòng)基金資助項(xiàng)目(NY214191)

錢 陽(yáng)(1991-)，女，碩士生，研究方向?yàn)榉蔷€性分析及應(yīng)用；李 雷，博士，教授，研究方向?yàn)橹悄苄盘?hào)處理和非線性科學(xué)及其在通信中的應(yīng)用。

http://kns.cnki.net/kcms/detail/61.1450.TP.20170313.1545.010.html

TP

A

1673-629X(2017)05-0035-05

10.3969/j.issn.1673-629X.2017.05.008