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

錢 陽，李 雷，石曼曼

(南京郵電大學 視覺認知計算與應用研究中心，江蘇 南京 210023)

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

錢 陽，李 雷，石曼曼

(南京郵電大學 視覺認知計算與應用研究中心，江蘇 南京 210023)

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

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

0 引 言

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

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

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

1 背景知識

1.1 盲壓縮感知模型

(1)

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

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

(2)

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

通過引入正則化參數λA，式(2)可以轉化為無約束最優化問題：

(3)

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

(4)

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

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

1.2 分裂Bregman迭代算法(SBI)

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

SBI算法解決的是如下的約束優化問題：

(5)

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

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

初始化:設置t=0，b0=0，u0=0，v0=0，選擇參數μ>0

Repeat

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

t←t+1

Until滿足停止迭代條件

1.3 雙稀疏字典

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

(6)

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

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

2 算法設計與分析

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

(7)

其中,λΘ為正則化參數。

與字典學習方法類似，可以通過交替執行稀疏編碼階段和字典更新階段來求得此優化模型的最優解。

2.1 稀疏編碼階段

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

(8)

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

s.t.u=ΨΘA

(9)

(10)

(11)

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

(12)

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

2.1.1u子問題

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

(13)

(14)

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

(15)

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

(16)

2.1.2A子問題

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

(17)

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

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

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

2.2 字典更新階段

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

(18)

(19)

將式(19)代入式(18)，且由于式(6)中對Θ的特殊定義，因此對矩陣Θ的更新則轉變為對矩陣∑中原子的逐列更新：

(20)

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

(21)

從而，式(20) 轉變為如下的LASSO問題：

(22)

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

2.3 D-BCS算法流程

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

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

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

Repeat

(1)稀疏編碼階段。

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

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

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

(2)字典更新階段。

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

t←t+1

Until滿足停止迭代條件

3 實驗及分析

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

圖1 測試圖像集

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

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

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

圖2 三種算法重構性能隨采樣率變化圖

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

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

圖3從直觀上進一步說明了D-BCS算法所表現的優越性。

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

4 結束語

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

[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] 練秋生,石保順,陳書貞.字典學習模型、算法及其應用研究進展[J].自動化學報,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] 焦李成，公茂果，王 爽，等.自然計算、機器學習與圖像理解前沿[M].西安:西安電子科技大學出版社,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 網絡出版時間：2017-03-13

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

錢 陽(1991-)，女，碩士生，研究方向為非線性分析及應用；李 雷，博士，教授，研究方向為智能信號處理和非線性科學及其在通信中的應用。

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