基于復(fù)合稀疏約束的近似消息傳遞CS重構(gòu)算法*

謝中華 馬麗紅 鐘福平

(華南理工大學(xué) 電子與信息學(xué)院, 廣東 廣州 510640)

基于復(fù)合稀疏約束的近似消息傳遞CS重構(gòu)算法*

謝中華 馬麗紅?鐘福平

(華南理工大學(xué) 電子與信息學(xué)院, 廣東 廣州 510640)

壓縮感知(CS)重構(gòu)中的近似消息傳遞(AMP)算法通過迭代執(zhí)行小波閾值操作和殘差更新來快速準(zhǔn)確地實現(xiàn)稀疏信號重構(gòu),但它所采用的小波系數(shù)稀疏約束并不適用于非稀疏的自然圖像,尤其CS觀測過程存在噪聲干擾時.為此,文中提出了一種基于復(fù)合稀疏約束和AMP框架的CS圖像重構(gòu)算法,使用相似圖像塊低秩約束和雙邊濾波約束作為自然圖像的聯(lián)合先驗信息,以改善圖像規(guī)則紋理和邊緣的恢復(fù)效果,從而提升算法的重構(gòu)性能.無噪CS觀測的重構(gòu)實驗表明,文中算法的峰值信噪比(PSNR)比僅用低秩約束的AMP算法提高了0.45 dB,比原始AMP算法高6.19 dB;而在含噪CS觀測的重構(gòu)實驗中,對應(yīng)的PSNR增益則分別是0.25和4.60 dB;無論是無噪觀測還是含噪觀測,文中算法都獲得了更佳的主觀視覺效果.

壓縮感知;近似消息傳遞;復(fù)合稀疏約束;低秩約束;雙邊濾波

壓縮感知重構(gòu)技術(shù)從低維觀測值中恢復(fù)出高維的原始信號,其本質(zhì)是求解一個欠定的線性方程組,而原始信號的稀疏性作為先驗信息,提供觀測值之外的附加信息量,可增加判斷最優(yōu)解的依據(jù).小波稀疏性或梯度稀疏性常被用作信號的先驗信息[1-3],前者提供了信號結(jié)構(gòu)突變位置信息,后者則提供了沿最大變化方向的目標(biāo)輪廓信息.但非稀疏的自然圖像具有過多的突變位置和小目標(biāo)輪廓,不具備小波和梯度稀疏特性.

為非稀疏信號構(gòu)造變換系數(shù)間的高階稀疏表示,可獲得信號結(jié)構(gòu)上的稀疏信息.高階稀疏結(jié)構(gòu)主要包括樹稀疏[4-6]、塊稀疏[7]和非局部稀疏[8-10].在基于樹稀疏的CS重構(gòu)算法中,WaTMRI算法[5]采用了小波樹稀疏正則化項對具有父子關(guān)系的小波系數(shù)進(jìn)行約束,使得它們趨向于共同為零或非零值;Turbo-AMP算法[6]通過條件概率表示小波系數(shù)的父子關(guān)系,并令父子系數(shù)共同為零或非零值的概率很大.父子系數(shù)具有相同稀疏樣式的約定，對于整體結(jié)構(gòu)規(guī)則的核磁共振圖像或雷達(dá)圖像十分有效,但不利于捕捉圖像的局部變化特征,對局部突變明顯的自然圖像效果受限．為此,非局部稀疏結(jié)構(gòu)被挖掘來描述相似圖像塊間的稀疏信息.文獻(xiàn)[8]認(rèn)為相似圖像塊組成的矩陣具有低秩的特性,應(yīng)限定相似圖像塊的稀疏系數(shù)也相似,從而構(gòu)建了一個基于圖像塊的低秩正則化模型;BM3D-AMP算法[9]通過概率圖模型刻畫CS觀測值與原始信號間的統(tǒng)計關(guān)系,通過三維塊匹配(BM3D)去噪算法對相似圖像塊進(jìn)行閾值收縮處理,使其滿足聯(lián)合稀疏結(jié)構(gòu).但當(dāng)參考塊缺少相似塊或受噪聲干擾相似塊匹配錯誤時,基于非局部稀疏的重構(gòu)算法性能會下降，因為最終圖像是重疊劃分的多個重構(gòu)圖像塊的加權(quán)平均結(jié)果,導(dǎo)致重疊區(qū)域的內(nèi)容變得模糊.

以上分析表明,圖像具有多種結(jié)構(gòu)稀疏信息,但每種信息的適用范圍有限.為提供更全面的自然圖像的稀疏描述,文中在AMP框架[11]下構(gòu)建一個由相似圖像塊低秩正則化約束項和雙邊濾波約束組成的復(fù)合稀疏模型.相似圖像塊的低秩約束負(fù)責(zé)圖像規(guī)則紋理的恢復(fù).雙邊濾波具有良好的邊緣保持能力,能改善邊緣模糊的問題.由于雙邊濾波算法在做鄰域加權(quán)平均運算時同時考慮空間鄰近信息和幅度相似性,使得離邊緣較遠(yuǎn)的像素權(quán)值很小,從而保證了邊緣附近像素值的保存.文中算法同時利用相似圖像塊的低秩特性和邊緣像素的空間及幅值信息,以兼顧圖像規(guī)則紋理和邊緣的恢復(fù).文中最后通過無噪觀測和含噪觀測實驗來驗證文中所提算法的性能.

1 近似消息傳遞算法

壓縮感知重構(gòu)技術(shù)從觀測值y=Ax0(yCm)中估計原信號x0Cn,其中ACm×n是觀測矩陣.由于m

(1)

式中:第1項為數(shù)據(jù)保真項;第2項為稀疏約束項;‖x‖1為x的L1范數(shù),等于其元素的絕對值之和;是控制保真項和約束項權(quán)重的正則化因子.

基于置信傳播理論,近似消息傳遞(AMP)算法通過在與觀測值y(或殘差z)相關(guān)的因子節(jié)點和與信號x相關(guān)的變量節(jié)點間迭代傳遞概率消息來推斷CS重構(gòu)問題的最大后驗概率[11].與一般的置信傳播算法不同,在高維的情形下,AMP 算法利用中心極限定理及泰勒展開式來進(jìn)行近似,極大地降低了計算量.從初始狀態(tài)x0=0,z0=y開始,AMP算法求解目標(biāo)函數(shù)(1)的迭代過程如下:

xt+1=η(xt+A*zt)

(2)

(3)

式中,xt為原始信號x0在第t次迭代的估計值,η(y)為小波軟閾值操作,為閾值參數(shù),zt為第t次迭代的殘差,A*為A的共軛轉(zhuǎn)置.這里,殘差zt比迭代閾值算法的殘差y-Axt多了一個Onsager矯正項為閾值函數(shù)η的導(dǎo)數(shù).

2 基于復(fù)合稀疏約束的AMP算法

2.1 基于復(fù)合稀疏約束的圖像CS重構(gòu)新模型

自然圖像中存在著豐富的相似成分,可當(dāng)作CS重構(gòu)算法的先驗信息,即非局部稀疏結(jié)構(gòu).將圖像重疊分塊,以搜索窗為范圍采用基于L2距離的塊匹配方法[8]尋找相似圖像塊組,非局部稀疏約束使得組內(nèi)的相似塊具有相似的稀疏系數(shù).另一方面,雙邊濾波具有良好的邊緣保持能力,它通過兼顧空間鄰近信息和幅度相似性的鄰域加權(quán),即邊緣像素取較大的權(quán)值,保證了邊緣附近像素值的保存.結(jié)合相似塊低秩的特性與雙邊濾波的優(yōu)點,文中構(gòu)建基于復(fù)合約束的CS重構(gòu)的新目標(biāo)函數(shù):

(4)

(5)

式中,Nv是以參考像素為中心的鄰域,權(quán)值ku,v為

(6)

圖1 相似塊低秩約束與雙邊濾波約束復(fù)合的AMP算法流程圖

2.2 基于復(fù)合分解技術(shù)的AMP算法

(7)

(8)

(9)

基于復(fù)合分解技術(shù)[14],該復(fù)合約束問題(qt) 通過變量分離和操作分離分解為兩個易解的子問題,然后分別對子問題獨立求解,再通過線性組合獲得最終解.原始的復(fù)合分解技術(shù)[14]在做線性組合時使用了平均運算,而文中根據(jù)文獻(xiàn)[15]中定理3.4使用更靈活的加權(quán)組合方式.基于復(fù)合稀疏模型的AMP重構(gòu)算法描述如下.

fort =1toTdo

∥Onsager項近似及殘差更新

zt=y-Axt+zt-1‖′(xt-1+A*zt-1)‖1/m;

qt=xt+A*zt;∥計算含噪圖像

∥低秩校正

∥雙邊濾波校正

end for

其中,低秩校正的步驟是一個加權(quán)核范數(shù)最小化問題,等價于

(10)

(11)

式(11)為一個加權(quán)核范數(shù)最小化問題,根據(jù)文獻(xiàn)[8]中的定理1,式(11)的最優(yōu)解可通過加權(quán)奇異值閾值(SVT)操作求得:

(12)

(13)

(14)

(15)

(16)

這里圖像塊奇異值的零范數(shù)定義為奇異值個數(shù)之和.該值越小,表明這組重構(gòu)后的圖像塊的稀疏程度越高,恢復(fù)效果越好,因此權(quán)值越大.

實施近似消息傳遞算法求解復(fù)合約束問題的一個難點在于Onsager校正項的估計,因為它需要計算鄰近復(fù)合校正函數(shù)(qt)的導(dǎo)數(shù)(式(9)),而(qt)函數(shù)沒有明確的輸入輸出關(guān)系.文中采用蒙特卡洛(MC)[17]隨機數(shù)近似的方法來估計Onsager校正項1/m中的導(dǎo)數(shù)運算:((qt+εb)-(qt))/ε]≈

E[bT((qt+εb)-(qt))/ε]

(17)

式中,E[·]表示求數(shù)學(xué)期望，獨立同分布的隨機矢量b～N(0,I),ε是一個很小的正數(shù).具體步驟如下:

(1)生成L個獨立同分布的隨機矢量b1,b2,…,bL;

(2)對每個矢量bj計算估計值

(3)計算這些估計值的平均值

按照弱大數(shù)定理,當(dāng)L→ ∞時,該估計值收斂到真實的導(dǎo)數(shù)值.

3 實驗與結(jié)果分析

為驗證文中算法的重構(gòu)性能,分別在無噪觀測和含噪觀測兩種情況下比較文中算法與其他7種算法(原始AMP算法、僅使用低秩正則化的AMP算法LR-AMP (即令文中算法的線性組合參數(shù)ω1=1,ω2=0)、基于樹稀疏的算法WaTMRI[5]和Turbo-AMP[6]、基于非局部稀疏的算法NLR-CS[8]、BM3D-AMP[9]和BM3D-CS[10])重構(gòu)的客觀質(zhì)量和主觀質(zhì)量.由于僅使用雙邊濾波的AMP 算法與文中算法的性能相差較大,因此未給出其重構(gòu)結(jié)果.實驗測試圖像為圖2所示的22幅128×128的自然圖像.所有實驗均在Matlab R2014a 平臺上運行,使用的計算機CPU型號為AMD A10-5800K 3.80 GHz.

圖2 實驗所用的測試圖像

3.1 無噪觀測實驗

在無噪環(huán)境下,采用8種算法分別在5個采樣率(16%、18%、20%、22%和24%)下進(jìn)行重構(gòu)實驗.由于采用隨機觀測方式,重構(gòu)結(jié)果存在一些浮動,因此對每幅圖像進(jìn)行5次隨機觀測和重構(gòu),再計算PSNR的平均值,結(jié)果如圖3所示.從圖中可知:文中算法較其他算法有更佳的客觀重構(gòu)質(zhì)量;基于非局部稀疏的5種重構(gòu)算法(包括文中算法、LR-AMP、NLR-CS、BM3D-AMP、BM3D-CS)比WaTMRI、Turbo-AMP和原始AMP算法的PSNR平均值更高,說明非局部稀疏約束比樹稀疏結(jié)構(gòu)或小波稀疏約束更適合于自然圖像的重構(gòu);與僅用低秩正則化的LR-AMP算法相比,文中算法獲得了高的PSNR平均值,說明在低秩約束的基礎(chǔ)上使用復(fù)合約束能進(jìn)一步提升AMP算法的重構(gòu)性能.事實上,文中算法的PSNR比LR-AMP算法平均提高了0.45dB,而比原始AMP算法平均提高了6.19dB.由于采用高階稀疏結(jié)構(gòu),文中算法改善了原始AMP算法的重構(gòu)質(zhì)量;又因為復(fù)合約束的合理引入,文中算法比基于非局部稀疏的其他4種算法具有更優(yōu)的重構(gòu)質(zhì)量.

圖3 不同采樣率下8種算法的PSNR平均值

Fig.3AveragePSNRof8algorithmsatdifferentsamplingrates

以Cameraman圖像為例,在20%采樣率下8種算法的重構(gòu)結(jié)果如圖4所示,PSNR隨迭代次數(shù)的變化曲線如圖5所示.從圖4可知,基于非局部稀疏的5種算法重構(gòu)的圖像依然比基于樹稀疏約束的兩種算法和原始AMP算法更整潔、更清晰.在基于非局部稀疏的5種重構(gòu)算法中,文中算法和LR-AMP算法在細(xì)節(jié)紋理(如草地區(qū)域)方面恢復(fù)得更好.這歸功于文中建立的基于加權(quán)核范數(shù)的低秩正則化模型,以及自適應(yīng)的核范數(shù)權(quán)值設(shè)定.文中算法與LR-AMP算法的區(qū)別可通過分別計算它們和原圖對應(yīng)像素的差值,再取絕對值得到的圖像進(jìn)行對比得出.如在衣服邊緣區(qū)域,文中算法重構(gòu)圖像的白色像素比LR-AMP算法少,說明與原圖像的差異更小,因此,引入雙邊濾波約束能增強原始重構(gòu)算法的邊緣保持能力.

圖4 20%采樣率下8種算法對Cameraman圖像的重構(gòu)結(jié)果

由于文中算法整體上基于AMP框架,且在求解復(fù)合約束問題時應(yīng)用了復(fù)合分解技術(shù),因此可以保證算法收斂.從圖5可知,到達(dá)相同PSNR結(jié)果時文中算法所需迭代次數(shù)比LR-AMP算法少,說明復(fù)合約束比單獨低秩約束能進(jìn)一步縮小解空間,從而加快最優(yōu)解的搜索速度.由于BM3D-CS和NLR-CS的迭代次數(shù)(分別為100和260)遠(yuǎn)多于其他算法,為集中顯示所有算法,圖中這兩種算法只分別給出間隔為2和間隔為5的PSNR結(jié)果.

圖5 20%采樣率下7種算法的PSNR隨迭代次數(shù)的變化曲線

Fig.5 Changing curves of PSNR with the iteration number of 7 algorithms at 20% sampling rate

3.2 含噪觀測實驗

現(xiàn)實環(huán)境中壓縮感知觀測普遍存在噪聲的干擾,為了說明使用復(fù)合約束能提升AMP算法對噪聲的魯棒性,文中比較了8種算法在含噪觀測情況下的重構(gòu)質(zhì)量.在實驗中先對CS觀測結(jié)果加入高斯噪聲,即y=Ax0+w,其中w為高斯噪聲,然后使用上述CS重構(gòu)算法進(jìn)行重構(gòu).以采樣率20%為例,在4種噪聲標(biāo)準(zhǔn)差σ(1、5、10和15)下7種算法的PSNR平均值如圖6所示.由于每次迭代時用觀測得到的傅里葉系數(shù)替換重構(gòu)后的系數(shù),本質(zhì)上無法去除觀測值中的噪聲,故本次實驗沒有使用BM3D-CS算法.從圖6可知,添加噪聲后各算法的PSNR值普遍略低于未加入噪聲時的結(jié)果(其中σ=10時文中算法比無噪時平均降低了3.79 dB),但與無噪情況下觀察到的規(guī)律相似:基于非局部稀疏的4種重構(gòu)算法的PSNR平均值比基于樹稀疏約束的兩種算法和原始AMP算法高;在所有采樣率下文中算法的PSNR平均值仍然最高,文中算法的PSNR比僅使用低秩正則化的LR-AMP算法平均提高了0.25 dB,比原始AMP平均提高了4.60 dB.這些結(jié)果進(jìn)一步驗證了在無噪情況下分析得到的結(jié)論,進(jìn)一步說明文中構(gòu)造的復(fù)合約束模型能提升AMP算法對噪聲的魯棒性.

圖6 不同噪聲強度下7種算法的PSNR平均值

在噪聲方差為10和20%采樣率下7種算法對Cameraman圖像的重構(gòu)結(jié)果如圖7和圖8所示.和圖4相比,圖8中每種算法的重構(gòu)圖像質(zhì)量都下降了,但基于非局部稀疏的4種算法的重構(gòu)圖像依然比基于樹稀疏約束的兩種算法和原始AMP算法更整潔,視覺效果更好.在基于非局部稀疏的4種重構(gòu)算法中,NLR-CS算法重構(gòu)圖像的噪聲點更多,BM3D-AMP算法重構(gòu)圖像的細(xì)節(jié)(如相機的支架區(qū)域)更加模糊,LR-AMP算法和文中算法的重構(gòu)結(jié)果較為理想.類似地,通過和原圖像的差值圖像比較,可以發(fā)現(xiàn)文中算法重構(gòu)圖像在邊緣處的白色像素比LR-AMP算法少,即與原圖像的差異更小,因此,文中算法在邊緣保持上優(yōu)于LR-AMP算法.以上結(jié)果表明,在CS觀測中存在噪聲干擾時,文中算法依然能保持最佳的重構(gòu)質(zhì)量.

圖7 在σ=10和20%采樣率下7種算法的PSNR隨迭代次數(shù)的變化曲線

Fig.7 Changing curves of PSNR with the iteration number of 7 algorithms at 20% sampling rate andσ=10

圖8 在σ=10和20%采樣率下7種算法對Cameraman圖像的重構(gòu)結(jié)果

4 結(jié)論

文中提出了一種基于復(fù)合稀疏約束和近似消息傳遞框架的圖像壓縮感知重構(gòu)算法.基于加權(quán)核范數(shù)的相似圖像塊低秩約束和基于邊信息指導(dǎo)的雙邊濾波約束組成的復(fù)合稀疏約束提升了AMP算法對圖像規(guī)則紋理和邊緣的重構(gòu)質(zhì)量.此外,復(fù)合分解技術(shù)的運用實現(xiàn)了復(fù)合約束問題的簡易求解.無噪觀測和含噪觀測實驗結(jié)果表明:與僅用相似塊低秩約束算法相比,文中算法采用的復(fù)合稀疏約束能進(jìn)一步增強圖像邊緣的保持能力;無論是無噪觀測還是含噪觀測,文中算法的重構(gòu)質(zhì)量均優(yōu)于原始AMP算法及其他基于結(jié)構(gòu)化稀疏模型的重構(gòu)算法,驗證了復(fù)合稀疏約束對提升AMP算法性能的有效性.事實上,復(fù)合稀疏約束不僅限于文中所采用的低秩約束和雙邊濾波約束,而文中主要是給出了在AMP框架下如何使用復(fù)合稀疏約束的一種解決措施.

[2] BECK A,TEBOULLE M.A fast iterative shrinkage-thre-sholding algorithm for linear inverse problems [J].SIAM Journal on Imaging Sciences,2009,2(1):183-202.

[3] 曾春艷,馬麗紅,杜明輝.前向預(yù)測與回溯結(jié)合的正交匹配追蹤算法 [J].華南理工大學(xué)學(xué)報(自然科學(xué)版), 2012,40(8):14-19.

ZENG Chun-yan,MA Li-hong,DU Ming-hui.Look ahead and backtracking-based orthogonal matching pursuit algorithm [J].Journal of South China University of Technology(Natural Science Edition),2012,40(8):14-19.

[4] HE L,CARIN L.Exploiting structure in wavelet-based Bayesian compressive sensing [J].IEEE Transactions on Signal Processing,2009,57(9):3488-3497.

[5] CHEN C,HUANG J.Exploiting the wavelet structure in compressed sensing MRI [J].Magnetic Resonance Imaging,2014,32(10):1377-1389.

[6] SOM S,SCHNITER P.Compressive imaging using appro-ximate message passing and a Markov-tree prior [J].IEEE Transactions on Signal Processing,2012,60(7):3439-3448.[7] ELDAR Y C,KUPPINGER P,BOLCSKEI H.Block-sparse signals:uncertainty relations and efficient recovery [J].IEEE Transactions on Signal Processing,2010,58(6):3042-3054.[8] DONG W,SHI G,LI X,et al.Compressive sensing via nonlocal low-rank regularization [J].IEEE Transactions on Image Processing,2014,23(8):3618-3632.[9] METZLER C,MALEKI A,BARANIUK R G.BM3D-AMP:a new image recovery algorithm based on BM3D denoising [C]∥Proceedings of IEEE International Conference on Image Processing.Quebec City:IEEE,2015:3116-3120.[10] DABOV K,FOI A,KATKOVNIK V,et al.Image denoi-sing by sparse 3-d transform-domain collaborative filtering [J].IEEE Transactions on Image Processing,2007, 16(8):2080-2095.

[11] DONOHO D L,MALEKI A,MONTANARI A.Message passing algorithms for compressed sensing [J].Procee-dings of the National Academy of Sciences,2009,106(45):18914-18919.

[12] VENKATAKRISHNAN S,BOUMAN C A,WOHLBERG B.Plug-and-play priors for model based reconstruction [C]∥Proceedings of IEEE Global Conference on Signal and Information Processing.Austin:IEEE,2013:945-948.[13] XIE Z,MA L,ZENG X.A structured AMP method recovering signals with a forward-backward splitting mode [C]∥Proceedings of IEEE Region 10 Conference. Macao:IEEE,2015:1-4.[14] HUANG J,ZHANG S,METAXAS D.Efficient MR image reconstruction for compressed MR imaging [J].Medical Image Analysis,2011,15(5):670-679.

[15] COMBETTES P L,PESQUET J C.A proximal decomposition method for solving convex variational inverse problems [J].Inverse Problems,2008,24(6):1-27.

[16] DONG W,SHI G,LI X.Nonlocal image restoration with bilateral variance estimation:a low-rank approach [J].IEEE Transactions on Image Processing,2013,22(2):700-711.

[17] METZLER C,MALEKI A,BARANIUK R G.Optimal recovery from compressive measurements via denoising- based approximate message passing [C]∥Proceedings of IEEE International Confence on Sampling Theory and Applications.Washington D C:IEEE,2015:508-512.

An Approximate Message Passing Algorithm with Composite Sparse Constraint for CS Reconstruction

XIEZhong-huaMALi-hongZHONGFu-ping

(School of Electronic and Information Engineering, Guangzhou 510640, Guangdong, China)

In CS reconstruction, approximate message passing (AMP) can realize the reconstruction of sparse signals quickly and accurately by performing both wavelet de-noising and residual updating iteratively. However, the sparse constraints of the wavelet coefficients used in AMP are not suitable for non-sparse natural images, especially when the measuring process of CS is disturbed by noises. In order to solve this problem, a CS image reconstruction algorithm is proposed on the basis of composite sparse constraints and an AMP framework. This algorithm takes both the low-rank constraint of similar image patches and the bilateral filter constraint as the joint prior information of natural images to enhance the recovery effect of image textures and edges, thus improving the performance of the algorithm. The results of the reconstruction experiment with no noise in the measuring process of CS show that, the proposed algorithm averagely improves PSNR (Peak Signal to Noise Ratio) by 0.45 dB and 6.19 dB, respectively in comparison with the AMP algorithm that only uses low-rank constraint and the original AMP algorithm. While in the presence of noise, the corresponding average PSNR gains are respectively 0.25 dB and 4.60 dB. In conclusion, the proposed algorithm can achieve a better visual quality whether it is noiseless or not.

compressed sensing; approximate message passing; composite sparse constraint; low-rank constraint; bilateral filter

1000-565X(2017)01- 0018- 08

2016- 05- 10

國家自然科學(xué)基金資助項目(61471173)

Foundation item： Supported by the National Natural Science Foundation of China(61471173)

謝中華(1985-),男,博士生,主要從事壓縮感知、多維信號重建研究.E-mail:eezhxie@gmail.com

? 通信作者： 馬麗紅(1965-),女,博士,教授,主要從事圖像視頻信號處理、模式識別研究.E-mail:eelhma@scut.edu.cn

TP 391

10.3969/j.issn.1000-565X.2017.01.003