一個(gè)基于卷積稀疏表示的圖像重構(gòu)算法*

陳小陶 許道云

(1.貴州大學(xué)數(shù)學(xué)系 貴陽(yáng) 550025)(2.貴州大學(xué)計(jì)算機(jī)科學(xué)系 貴陽(yáng) 550025)

一個(gè)基于卷積稀疏表示的圖像重構(gòu)算法*

陳小陶1許道云2

(1.貴州大學(xué)數(shù)學(xué)系 貴陽(yáng) 550025)(2.貴州大學(xué)計(jì)算機(jī)科學(xué)系 貴陽(yáng) 550025)

在利用稀疏表示技術(shù)重構(gòu)圖像的應(yīng)用中,傳統(tǒng)的方法是獨(dú)立地計(jì)算一組重疊的圖像塊,在表示中只針對(duì)每個(gè)圖像塊進(jìn)行單獨(dú)稀疏編碼。利用卷積稀疏表示,可以將整個(gè)圖像看做是一個(gè)整體,對(duì)其進(jìn)行稀疏編碼,由濾波器字典與相應(yīng)特征響應(yīng)的卷積總和代替?zhèn)鹘y(tǒng)的字典矩陣與編碼系數(shù)的乘積對(duì)圖像進(jìn)行分解。論文基于卷積稀疏表示方法,提出一個(gè)圖像重構(gòu)算法,利用交替方向乘法器方法(ADMM)對(duì)輸入圖像進(jìn)行稀疏逼近,得到特征響應(yīng)系數(shù),達(dá)到對(duì)圖像卷積分解的目的。實(shí)驗(yàn)結(jié)果說明卷積分解機(jī)制稀疏性能較優(yōu),更適合于圖像重構(gòu)。

稀疏表示; 卷積稀疏表示; ADMM; 圖像重構(gòu)

1 引言

稀疏表示(Sparse Representation)[1～2]是通過用盡可能少的原子系數(shù)線性表示原始信號(hào),它與壓縮感知(Compressed Sensing)[3～4]有著直接的聯(lián)系。壓縮感知提出如果一個(gè)信號(hào)是稀疏的或者壓縮的,原始信號(hào)可以通過這些少量的測(cè)量值進(jìn)行重構(gòu)。信號(hào)可以稀疏表示是壓縮感知的先驗(yàn)條件,由字典矩陣依據(jù)稀疏度量標(biāo)準(zhǔn)求解變換后得到的稀疏向量再通過逆變換從而實(shí)現(xiàn)信號(hào)的精確重構(gòu)或近似重構(gòu)。由字典矩陣依據(jù)稀疏度量標(biāo)準(zhǔn)求解變換后得到的稀疏向量求解變換的過程在稀疏表示中叫做稀疏分解。依據(jù)壓縮感知中的重構(gòu)原理,可以先通過稀疏分解得到稀疏系數(shù),再通過逆變換重構(gòu)圖像。

稀疏分解問題是指,在字典張成的整個(gè)信號(hào)空間下,依據(jù)稀疏度量標(biāo)準(zhǔn)尋找信號(hào)的最優(yōu)解,即稀疏優(yōu)化。典型稀疏度量標(biāo)準(zhǔn)包括l0范數(shù)、l1范數(shù)、l2范數(shù)以及l(fā)p(0

雖然基于傳統(tǒng)的稀疏表示方法可以大大減小問題的計(jì)算,也獲得了很好的效果,但是以往的研究通常是獨(dú)立地處理重疊塊,最后通過平均每一塊之間的重疊像素來獲得結(jié)果。因?yàn)檫@種處理方法使得每個(gè)像素的輸出圖像將被估計(jì)更多次,所以相鄰的塊之間的重疊像素將提供更好的重構(gòu)結(jié)果。然而,在解決塊估計(jì)問題時(shí),這種“重疊平均”機(jī)制忽略了一個(gè)重要的約束,重疊區(qū)域中的像素相鄰的塊應(yīng)該是完全一樣的,即一致性。一致性約束提供了在處理每一個(gè)單一的估計(jì)問題的先驗(yàn)信息。最近,文獻(xiàn)[11]提出了一種聚合方法,以減輕重疊塊之間的不一致,并在圖像恢復(fù)方面取得了較好的效果。然而,對(duì)于圖像重構(gòu)方面,仍需要更好的方法證明一致性約束的重要性。

因?yàn)閳D像塊之間的一致性,2010年,Zeiler在文獻(xiàn)[12]最早提出卷積稀疏表示,利用帶卷積的稀疏編碼實(shí)現(xiàn)稀疏表示整個(gè)圖像,即利用濾波器與相應(yīng)特征響應(yīng)的卷積總和,代替?zhèn)鹘y(tǒng)的字典矩陣與編碼系數(shù)的乘積對(duì)信號(hào)進(jìn)行分解。同年,文獻(xiàn)[13]提出用卷積匹配追蹤算法訓(xùn)練深層卷積網(wǎng)絡(luò)。2014年,文獻(xiàn)[14]提出用交替方向乘法器的方法(ADMM)進(jìn)行卷積分解,通過濾波器與對(duì)應(yīng)特征響應(yīng)做卷積,減少相鄰位置圖像塊的編碼冗余度。盡管這些算法用來解決卷積稀疏表示問題,但很少注意驗(yàn)證卷積稀疏表示在圖像重構(gòu)方面優(yōu)于傳統(tǒng)的基于塊的稀疏表示。

針對(duì)傳統(tǒng)的稀疏表示算法一般只是對(duì)圖像塊進(jìn)行單獨(dú)編碼,而忽略圖像的整體性,本文構(gòu)建了一個(gè)基于卷積稀疏表示的重構(gòu)算法,以此驗(yàn)證應(yīng)用一致性約束對(duì)整幅圖像進(jìn)行分解優(yōu)于傳統(tǒng)的稀疏編碼。用交替方向乘法器方法(Alternating Direction Method of Multipliers,ADMM)對(duì)輸入圖像進(jìn)行卷積稀疏分解。帶卷積的ADMM算法根據(jù)卷積獨(dú)有的性質(zhì),只需要一個(gè)卷積核,就可表示圖像任意位置的相同特征,即能夠用較少的原子個(gè)數(shù)有效刻畫圖像的幾何特征。通過實(shí)驗(yàn)驗(yàn)證與傳統(tǒng)的稀疏表示模型相比,卷積分解機(jī)制更適合于圖像重構(gòu)。

2 卷積稀疏表示

基于傳統(tǒng)的稀疏表示一幅圖像s,由字典矩陣與編碼系數(shù)的線性結(jié)合對(duì)圖像進(jìn)行分解。其數(shù)學(xué)表達(dá)式為

(1)

式中D表示字典矩陣,x表示稀疏系數(shù),s表示原圖像,λ表示正則化參數(shù),用來調(diào)整正則化程度。這種傳統(tǒng)的基于塊的稀疏編碼方式在圖像處理方面應(yīng)用廣泛。

但是,在傳統(tǒng)意義上的稀疏表示模型中,還存在一些缺陷。如l0范數(shù)的可拓展性貧乏,在處理大規(guī)模問題上限制了稀疏編碼的應(yīng)用。為了減少建模和計(jì)算負(fù)擔(dān),一般都只是對(duì)圖像塊單獨(dú)編碼。其次,只針對(duì)一維信號(hào)進(jìn)行單獨(dú)編碼,忽略了數(shù)據(jù)信息二維空間結(jié)構(gòu)和圖像塊之間的一致性,導(dǎo)致編碼高度冗余。這種稀疏表示方法忽視了圖像塊之間的一致性,現(xiàn)有的聚合和平均策略只能緩解由此帶來的問題。

考慮到圖像塊之間的一致性,2010年,文獻(xiàn)[11]提出利用帶卷積的稀疏編碼實(shí)現(xiàn)稀疏表示整個(gè)圖像,即利用濾波器與相應(yīng)特征響應(yīng)的卷積總和,代替?zhèn)鹘y(tǒng)的字典矩陣與編碼系數(shù)的乘積對(duì)信號(hào)進(jìn)行分解。利用正則化公式表示該模型:

(2)

其中{dm}是一組濾波器構(gòu)成的M維卷積字典,每個(gè)濾波器的大小為n×n,?表示卷積符號(hào),{xm}是一組特征響應(yīng),每個(gè)特征響應(yīng)的大小與s相同,s表示輸入圖像,為了表示上的方便s和xm為N維向量,N是圖像中像素的個(gè)數(shù)。在這個(gè)帶卷積的稀疏表示模型中,充分考慮了圖像塊之間的相關(guān)性。本文將基于這個(gè)模型,構(gòu)建一個(gè)圖像重構(gòu)算法,并與傳統(tǒng)的基于塊的稀疏表示重構(gòu)圖像進(jìn)行比較。

3 帶卷積的ADMM算法

帶卷積的稀疏表示模型,對(duì)應(yīng)的正則化問題可以表示為式(2)。式(2)利用一種圖像先驗(yàn),即對(duì)整幅圖像變換稀疏性。引入輔助變量{ym}(其中{ym}也是一個(gè)維向量)式(2)變換成:

s.t.xm-ym=0, ?m

(3)

再利用對(duì)偶變量,引入拉格朗日乘子u,則約束優(yōu)化問題式(3)變?yōu)榉羌s束等價(jià)形式:

(4)

式中ρ是一個(gè)正則化參數(shù)。

本文用交替方向乘法器(ADMM)求解式(4)描述的優(yōu)化問題,交替方向乘法器是一種對(duì)偶凸優(yōu)化算法,其可以將可分結(jié)構(gòu)的凸規(guī)劃問題分解為若干子問題交替地求解[15]。依據(jù)交替方向乘法器的運(yùn)算規(guī)則將本文中求解式(4)分為三個(gè)子問題,步驟如下:

1) 固定特征響應(yīng)系數(shù){xm},乘子u,更新輔助變量{ym}。

(5)

式(5)為典型的l1范數(shù)優(yōu)化問題,處理該問題較常用的方法是閾值法,采用閾值法可得:

(6)

式中shrink(.,.),表示軟閾值函數(shù),定義為

shrink(g,u)=sign(g)max{0,|g|-u}

(7)

2) 固定輔助變量{ym},乘子u,更新特征響應(yīng)系數(shù){xm}。

(8)

3) 按照ADMM算法規(guī)則更新乘子u。

(9)

在求解這些子問題的時(shí)候,最大的計(jì)算代價(jià)是在求解式(8)中也就是更新特征響應(yīng)系數(shù),接下來本文具體介紹求解子問題2)。表示如下:

(10)

下面詳細(xì)介紹子問題2)的求解:

在子問題2)中,出現(xiàn)了卷積的求解,又卷積定理[16]表明了兩個(gè)傅里葉變換之間的關(guān)系構(gòu)成了空間域和頻率域之間的基本關(guān)系,即一個(gè)域中卷積對(duì)應(yīng)于另一個(gè)域中的乘積,也就是說可以將卷積運(yùn)算轉(zhuǎn)變成乘積運(yùn)算。從而在求解子問題2)時(shí),首先應(yīng)用DFT(離散傅里葉變換)卷積定理,將離散的卷積運(yùn)算轉(zhuǎn)換成乘積運(yùn)算。

(11)

(12)

從而式(11)的問題可以表示為

(13)

(14)

(15)

基于上述討論,本文引入一個(gè)圖像重構(gòu)算法,稱為CSR_ADMM算法,具體步驟如下:

輸入:樣本s,濾波器字典{dm},參數(shù)λ,ρ。

初始化:{ym}={um}=0。

步驟1:通過引進(jìn)輔助參數(shù)的拉格朗日函數(shù),構(gòu)建問題(2)的限制最優(yōu)化問題；

步驟5:通過式(6)更新{ym}；

步驟6:通過式(9)更新{um}；

步驟7:重復(fù)步驟2～6。

4 實(shí)驗(yàn)分析

在卷積稀疏表示模型下,應(yīng)用上述的CSR-ADMM算法,計(jì)算出圖像的特征響應(yīng)系數(shù),并利用得到的特征響應(yīng)系數(shù)重構(gòu)圖像,與基于傳統(tǒng)的稀疏表示算法ADMM得到的稀疏系數(shù)重構(gòu)圖像的峰值信噪比進(jìn)行比較。

在實(shí)驗(yàn)中,卷積分解機(jī)制使用一組12×12×36的濾波器字典[17],其中λ=0.01,ρ=2,迭代次數(shù)為500次。傳統(tǒng)分解機(jī)制使用一個(gè)64×256的DCT字典,λ=0.01,迭代次數(shù)同為500次,輸入圖像采用標(biāo)準(zhǔn)圖像lena,house,peppers,bird,city,fruits(大小均為512×512),作為測(cè)試圖像。

圖1 原始圖像

圖2 基于卷積稀疏表示重構(gòu)圖像

其中圖1表示上述六幅標(biāo)準(zhǔn)圖像的原始圖像,圖2表示基于卷積分解機(jī)制的重構(gòu)圖像,圖3表示傳統(tǒng)基于塊的稀疏分解機(jī)制的重構(gòu)圖像。表1給出了針對(duì)不同的測(cè)試圖像,基于帶卷積的與傳統(tǒng)的基于塊的稀疏分解機(jī)制下優(yōu)化算法重構(gòu)圖像的峰值信噪比(Peak Signal-to-Noise Ratio,PSNR)。

圖3 基于傳統(tǒng)稀疏表示重構(gòu)圖像

表1 基于不同分解機(jī)制下的重構(gòu)圖像峰值信噪比(PSNR)[dB]

從表1中它們的均值可以看出,帶卷積的ADMM重構(gòu)圖像峰值信噪比不帶卷積基于塊的提高了7.49dB。由此,說明在帶卷積的稀疏表示模型下,稀疏表示性能更優(yōu),卷積分解機(jī)制更適合圖像重建。

為了進(jìn)一步說明卷積分解機(jī)制更適合于圖像重構(gòu),表2給出了在標(biāo)準(zhǔn)圖像lena(512×512)下,當(dāng)λ=0.01固定時(shí),針對(duì)不同的迭代次數(shù)與不同的ρ的取值CSR_ADMM重構(gòu)圖像峰值信噪比的對(duì)比。

表2 基于不同的迭代次數(shù)與ρ的取值CSR_ADMM重構(gòu)圖像PSNR[dB]

從表2可以看出,當(dāng)ρ的取值固定時(shí),隨著迭代次數(shù)的增加,圖像的峰值信噪比也在增加,當(dāng)?shù)螖?shù)固定時(shí),ρ的值從變化10-2到103圖像的峰值信噪比基本沒有改變。從表2也可以看出當(dāng)?shù)螖?shù)為200時(shí),基于卷積的稀疏分解機(jī)制得到的圖像峰值信噪比,比傳統(tǒng)的稀疏分解機(jī)制在迭代500次時(shí)高。這也充分說明,基于卷積的稀疏分解機(jī)制得到的特征響應(yīng)系數(shù)優(yōu)于傳統(tǒng)的稀疏分解機(jī)制。

5 結(jié)語(yǔ)

本文基于卷積稀疏表示模型,利用ADMM將其分解為幾個(gè)簡(jiǎn)單的非約束優(yōu)化子問題,從而得到特征響應(yīng)系數(shù)。卷積稀疏表示直接把整個(gè)圖像進(jìn)行濾波,充分考慮了重疊圖像塊像素之間的一致性,較之前傳統(tǒng)的基于塊的稀疏表示,卷積分解機(jī)制可以保持特征響應(yīng)中輸入信號(hào)的空間信息,進(jìn)而達(dá)到較優(yōu)的稀疏逼近,更有利于對(duì)圖像進(jìn)行重構(gòu)。下一步可將本文的CSR_ADMM優(yōu)化算法應(yīng)用于圖像去噪,圖像超分辨率等問題。

[1] Elad M, Figueiredo M A T, Ma Y. On the role of sparse and redundant representations in image processing[J]. Proceedings of the IEEE,2010,98(6):972-982.

[2] Cheng H, Liu Z, Yang L, et al. Sparse representation and learning in visual recognition: Theory and applications[J]. Signal Processing,2013,93(6):1408-1425.

[3] Donoho D L. Compressed sensing[J]. Information Theory, IEEE Transactions on,2006,52(4):1289-1306.

[4] Baraniuk R G. Compressive sensing[J]. IEEE signal processing magazine,2007,24(4):118-121.

[5] Figueiredo M A T, Nowak R D, Wright S J. Gradient projection for sparse reconstruction: Application to compressed sensing and other inverse problems[J]. Selected Topics in Signal Processing,2007,1(4):586-597.

[6] Kim S J, Koh K, Lustig M, et al. An interior-point method for large-scale-regularized least squares[J]. IEEE journal of selected topics in signal processing,2007,1(4):606-617.

[7] Yang J, Zhang Y. Alternating direction algorithms for l1-problems in compressive sensing[J]. SIAM journal on scientific computing,2011,33(1):250-278.

[8] Mallat S G, Zhang Z. Matching pursuits with time-frequency dictionaries[J]. Signal Processing, IEEE Transactions on,1993,41(12):3397-3415.

[9] Engan K, Aase S O, Hakon Husoy J. Method of optimal directions for frame design[C]//Acoustics, Speech, and Signal Processing,1999:2443-2446.

[10] Zhang Z, Xu Y, Yang J, et al. A survey of sparse representation: algorithms and applications[J]. Access, IEEE,2015,3:490-530.

[11] Kervrann C. PEWA: Patch-based Exponentially Weighted Aggregation for image denoising[C]//Advances in Neural Information Processing Systems,2014:2150-2158.

[12] Zeiler M D, Krishnan D, Taylor G W, et al. Deconvolutional networks[C]//Computer Vision and Pattern Recognition(CVPR),2010:2528-2535.

[13] Szlam A, Kavukcuoglu K, LeCun Y. Convolutional matching pursuit and dictionary training[J/OL]. [2010-10-3]. http://arXiv.org/abs/1010.0422.

[14] Wohlberg B. Efficient convolutional sparse coding[C]//International Conference on Acoustics, Speech and Signal Processing(ICASSP),2014:7173-7177.

[15] Gabay D, Mercier B. A dual algorithm for the solution of nonlinear variational problems via finite element approximation[J]. Computers & Mathematics with Applications,1976,2(1):17-40.

[16] 楊帆.數(shù)字圖像處理與分析[M].北京:北京航空航天大學(xué)出版社,2010:39-44. YANG Fan. Digital Image Processing and Analysis[M]. Beijing: Beijing University of Aeronautics and Astronautics Press,2010:39-44.

[17] Wohlberg B. Convolutional sparse representation of color images[C]//Southwest Symposium on Image Analysis and Interpretation(SSIAI),2016:57-60.

Image Reconstruction AlgorithmBased on Convolution Sparse Representation

CHEN Xiaotao1XU Daoyun2

(1. Department of Mathematics, Guizhou University, Guiyang 550025)(2. Department of Computer Science, Guizhou University, Guiyang 550025)

In the application of sparse representation in image reconstruction, the traditional method is to compute a set of overlapping image blocks independently. Using convolution sparse representation, the whole image is seen as a whole, the of sparse coding and by the filter dictionary and corresponding characteristic response of the convolution sum instead of the product of traditional dictionary matrix and coding coefficients for image decomposition. In this paper, based on the sparse representation model of convolution, an image reconstruction algorithm is proposed, the input image is approximated by the alternating direction multiplier method(ADMM), and the characteristic response coefficient is obtained. The experimental results show that the sparse performance of the convolution decomposition mechanism is better, and it is more suitable for image reconstruction.

sparse representation, convolution sparse representation, ADMM, image reconstruction Class Number TP391

2016年10月5日,

2016年11月26日

國(guó)家自然科學(xué)基金(編號(hào):61262006)資助。

陳小陶,女,碩士研究生,研究方向:密碼學(xué)理論與工程。許道云,男,博士,教授,博士生導(dǎo)師,研究方向:SAT問題、可計(jì)算性與計(jì)算復(fù)雜性、算法設(shè)計(jì)與分析等。

TP391

10.3969/j.issn.1672-9722.2017.04.029