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

錢 陽，李 雷，石曼曼

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

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

錢 陽，李 雷，石曼曼

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

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

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

0 引 言

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

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

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

1 背景知識

1.1 盲壓縮感知模型

(1)

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

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

(2)

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

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

(3)

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

(4)

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

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

1.2 分裂Bregman迭代算法(SBI)

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

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

(5)

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

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

(6)

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

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

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

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

(7)

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

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

2.1 稀疏編碼階段

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

(8)

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

s.t.u=ΨΘA

(9)

(10)

(11)

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

(12)

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

2.1.1u子問題

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

(13)

(14)

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

(15)

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

(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取值較大時，A(t+1)中只能包含圖像塊的重要組成部分，這對高噪聲情況非常適用；而當(dāng)λA取值較小時，稀疏表示系數(shù)A(t+1)中將會包含每個圖像塊過多的細節(jié)信息，這些冗余的細節(jié)信息將會使得學(xué)習(xí)過程混亂，且容易導(dǎo)致算法發(fā)散。因此，選擇合適的正則化參數(shù)λA至關(guān)重要。

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

2.2 字典更新階段

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

(18)

(19)

將式(19)代入式(18)，且由于式(6)中對Θ的特殊定義，因此對矩陣Θ的更新則轉(zhuǎn)變?yōu)閷仃嚒浦性拥闹鹆懈拢?/p>

(20)

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

(21)

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

(22)

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

2.3 D-BCS算法流程

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

輸入：CS觀測值Y，觀測矩陣Φ，基字典Ψ，λ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 實驗及分析

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

圖1 測試圖像集

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

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

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

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

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

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

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

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

4 結(jié)束語

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

[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].自動化學(xué)報,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] 焦李成，公茂果，王 爽，等.自然計算、機器學(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ò)出版時間：2017-03-13

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

錢 陽(1991-)，女，碩士生，研究方向為非線性分析及應(yīng)用；李 雷，博士，教授，研究方向為智能信號處理和非線性科學(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