利用平衡方法的非凸圖像修復(fù)

吳玉蓮,馮象初

(1.西安電子科技大學(xué)數(shù)學(xué)與統(tǒng)計(jì)學(xué)院,陜西西安 710071; 2.西安醫(yī)學(xué)院公共課部,陜西西安 710021)

利用平衡方法的非凸圖像修復(fù)

吳玉蓮1,2,馮象初1

(1.西安電子科技大學(xué)數(shù)學(xué)與統(tǒng)計(jì)學(xué)院,陜西西安 710071; 2.西安醫(yī)學(xué)院公共課部,陜西西安 710021)

自然圖像通?？梢钥闯捎蓛刹糠謽?gòu)成:卡通部分和紋理部分,這兩部分在一些緊框架下,比如曲線波、局部余弦變換、樣條小波等都有稀疏表示.該文研究在兩個可分離緊框架下的圖像修復(fù)問題.與大部分算法普遍采用基于分析的或者合成的稀疏先驗(yàn)的不同之處在于:文中采用基于平衡的方法,且對稀疏系數(shù)使以非凸限制;最后給出了迭代算法.數(shù)值實(shí)驗(yàn)表明了建議的非凸圖像修復(fù)方法比普通的l1凸方法和經(jīng)典的變分TV方法有更好的修復(fù)效果.

圖像修復(fù);卡通紋理;非凸;緊框架

數(shù)字圖像修復(fù)是當(dāng)前數(shù)字圖像處理和計(jì)算機(jī)圖像學(xué)中的一個熱點(diǎn)問題,其在文物保護(hù)、剔除圖像或視頻中的一些文字,修復(fù)網(wǎng)絡(luò)傳輸中丟失或損壞的視頻信息等方面都有很高的應(yīng)用價值.

變分和偏微分方程是最流行的圖像修復(fù)方法之一,其基本思想是根據(jù)整個目標(biāo)區(qū)域的外部鄰域內(nèi)已知像素的幾何方向,向區(qū)域內(nèi)部各向異性地?cái)U(kuò)散灰度信息,從而實(shí)現(xiàn)目標(biāo)區(qū)域的重構(gòu).這類方法對于目標(biāo)區(qū)域相對較小的非紋理圖像能夠獲得較好的修復(fù)結(jié)果.但當(dāng)目標(biāo)區(qū)域較大時,區(qū)域內(nèi)部信息并不能由外部鄰域內(nèi)的已知信息簡單估計(jì);同理,當(dāng)目標(biāo)區(qū)域內(nèi)包含有復(fù)雜的紋理特征時,變分和偏微分方程的處理結(jié)果并不能保持周期性、重復(fù)性的紋理信息.此類方法的優(yōu)點(diǎn)就是能保持圖像的邊界,尤其適用于分片光滑圖像.文獻(xiàn)[1-2]等都屬于此類修復(fù)方法.

為了能同時修復(fù)結(jié)構(gòu)和紋理,文獻(xiàn)[3]提出了一種基于圖像分解的非參數(shù)采樣紋理合成修復(fù)方法.文獻(xiàn)[5]提出了一種基于稀疏表示的圖像分解修復(fù)方法,文獻(xiàn)[6-7]提出了基于小波緊框架的結(jié)構(gòu)紋理圖像修復(fù)方法.這類基于分解的修復(fù)算法對圖像的結(jié)構(gòu)和紋理都能取得較好的修復(fù)效果.

文中基于緊框架[4-6]的方法,是拉直圖像矩陣的所有列排成n維向量的形式,而緊框架是Rn中的冗余系統(tǒng)(其中R為實(shí)數(shù)集).具體來說,假設(shè)W∈Rm×n(m≥n),滿足WTW=I,I是單位矩陣,這樣W的所有行向量就形成Rn中的一個緊框架.對每一個向量u∈Rn,u=WT(Wu),向量Wu為u在冗余系統(tǒng)W下的系數(shù).一般情況下,WTW≠I.當(dāng)WTW=I時,此時W構(gòu)成一個正交系統(tǒng).

既然緊框架是冗余系統(tǒng),那么圖像u與其相應(yīng)的稀疏系數(shù)之間就不是一一對應(yīng)的,正因?yàn)槿绱藞D像的稀疏表示就有3種方法,即基于分析的方法、基于合成的方法及基于平衡的方法.在基于分析的方法中,假設(shè)分析系數(shù)Wu是稀疏逼近的,通常解決一個帶有懲罰項(xiàng)的最小二乘問題[5].而基于合成的方法,則假設(shè)圖像u由稀疏系數(shù)向量α合成的,滿足u=WTα,通常解決一個關(guān)于的最小化問題[10].基于平衡的方法則可以看成對前兩種方法進(jìn)行平衡的一種方法,此方法最先用于高分辨率重構(gòu)[11],后來又用于各種各樣的圖像恢復(fù)問題[6-7].

自然圖像通?？梢钥闯煽ㄍ?圖像的光滑部分)與紋理(圖像的振蕩部分)兩部分構(gòu)成,并且兩部分在一些緊框架下有稀疏表示.比如卡通部分在曲線波和小波緊框架下都有很好的稀疏逼近[8-9].為了更好地完成圖像修復(fù)問題,筆者采用兩個緊框架分別稀疏表示圖像的卡通和紋理部分[5,7],并且用非凸的迫近p (0＜p＜1)范數(shù)[12]代替經(jīng)典的l1范數(shù)對稀疏系數(shù)進(jìn)行約束.

1 迫近p范數(shù)

一個向量S的迫近p范數(shù)是對常見的l1范數(shù)的一種非凸形式的推廣.求解未知向量S的l1范數(shù)問題為

式(1)是可分離的,即對?t∈T,都有

式(2)的解是大家熟知的軟閾值算子:

稱此軟閾值算子為l1范數(shù)的迫近函數(shù).關(guān)于t的函數(shù)式(2)也可以通過下面的Huber函數(shù)直接計(jì)算得到:

為了在非凸情況下對式(1)進(jìn)行推廣,需要重構(gòu)一個非凸函數(shù)g,滿足如下非凸問題:

希望能用式(3)的推廣閾值形式得到式(1)在非凸情形下推廣問題的最優(yōu)解.為了重構(gòu)相應(yīng)的非凸函數(shù)g,可以先對式(4)的Huber函數(shù)進(jìn)行推廣:

迫近p范數(shù)定義[12]:如果gμ,p定義為 :,稱懲罰項(xiàng)為S的迫近p范數(shù).迫近p范數(shù)的性質(zhì)[12]:G,p(S)的迫近函數(shù)由推廣的p-shrin kge算μ子給出:

2 非凸稀疏的圖像修復(fù)模型及算法

假設(shè)希望的完整圖像u∈Ω={1,2,…,N},非空集Λ?Ω是給定的觀測區(qū)域,觀測到的破損圖像f滿足:

其中,ε表示噪聲,圖像修復(fù)的目的就是從f恢復(fù)出u,即找一幅圖像u∈Ω,滿足PΛf≈PΛu,PΛ是一個對角矩陣,定義為

文獻(xiàn)[7]提出了基于平衡方法的卡通紋理圖像修復(fù)模型(Ⅰ):

式(11)假設(shè)恢復(fù)后的圖像u是由卡通部分u1和結(jié)構(gòu)部分u2構(gòu)成,緊框架W1,W2分別稀疏逼近卡通部分和紋理部分,α1,α2分別為其逼近系數(shù).式(11)的第1項(xiàng)是數(shù)據(jù)忠誠項(xiàng),后兩項(xiàng)是正則項(xiàng),用來平衡解的光滑性和稀疏性.

求解式(12)可采用迫近的前向后向分裂算法[19].令

為了求解式(13),可將其分裂如下:

為了求出式(12)的迭代解,需要先求出?F2和迫近算子PγF1.

當(dāng)i=1時,閾值參數(shù)τ=diag(u1);當(dāng)i=2時,閾值參數(shù)τ=diag(u2).由迫近p范數(shù)的性質(zhì),可以得到

求得改進(jìn)的圖像修復(fù)卡通紋理模型(Ⅱ)的迭代解,即

因此,修復(fù)圖像的卡通部分u1為α1,紋理部分u2為α2.

值得注意的是,當(dāng)Λ=Ω時,上述算法將會給出完整圖像u的卡通紋理分解,對此不做詳細(xì)討論.

3 數(shù)值實(shí)驗(yàn)

為了驗(yàn)證筆者建議的改進(jìn)模型(Ⅱ)的可行性及實(shí)用性,首先用大小為512×512的標(biāo)準(zhǔn)圖像“Barbara”和“Fingerprint”進(jìn)行實(shí)驗(yàn).原圖像和觀測到的破損圖像見圖1.分片線性B-spline小波緊框架[15]W1再現(xiàn)卡通部分,冗余的局部離散余弦緊框架W2再現(xiàn)紋理部分.模型式(Ⅱ)中的步長參數(shù)γ選取與文獻(xiàn)[7]中的相同和γ=0.5max{1,k}時,算法比較穩(wěn)定.在文中的實(shí)驗(yàn)中,用峰值信噪比(PSNR)來衡量修復(fù)圖像的質(zhì)量.改進(jìn)的模型(Ⅱ)中的參數(shù)選取以使修復(fù)結(jié)果達(dá)到最好,即使修復(fù)圖像PSNR達(dá)到最高.將改進(jìn)模型(Ⅱ)與卡通紋理修復(fù)模型(Ⅰ)[7]和經(jīng)典的TV修復(fù)方法[1]進(jìn)行比較.當(dāng)k=1時,針對“Barbara”圖像不同的p (0＜p≤1)值得到的實(shí)驗(yàn)結(jié)果見表1.

圖1 兩種測試圖像及破損圖像

表1 “Barbara”圖像在不同p值下的PSNR及迭代次數(shù)

從表1可以看出,0＜p＜1時得到PSNR均高于文獻(xiàn)[7]p=1的情況,并且當(dāng)p=0.6時得到的結(jié)果比文獻(xiàn)[7]p=1高出0.51 d B.從圖2、圖3也可以看出文中修復(fù)算法比文獻(xiàn)[7]中的算法和文獻(xiàn)[1]中的算法有更好的視覺修復(fù)效果,并且該算法得到的卡通紋理修復(fù)部分比文獻(xiàn)[7]中算法得到的卡通紋理修復(fù)部分更加合理,比如圖5中文獻(xiàn)[7]中的算法得到的修復(fù)圖像“Fingerprint”的結(jié)構(gòu)部分還有少許的紋理,而該算法則避免了此現(xiàn)象出現(xiàn).

為了更有力地說明改進(jìn)的算法比文獻(xiàn)[7]的算法和文獻(xiàn)[1]中的算法能更好地對圖像進(jìn)行修復(fù),筆者還對9幅大小為512×512的標(biāo)準(zhǔn)圖像進(jìn)行了實(shí)驗(yàn).實(shí)驗(yàn)數(shù)據(jù)比較見表2.從表2可看到,所有的測試圖像在p=0.6下的修復(fù)效果均明顯好于文獻(xiàn)[1],且比文獻(xiàn)[7]p=1時的修復(fù)效果也有不同程度的提高,實(shí)驗(yàn)終止條件(前后兩次迭代的實(shí)驗(yàn)結(jié)果之差小于某個常數(shù))完全一致時,其所需的迭代次數(shù)略多.

圖2 “Barbara“圖像修復(fù)結(jié)果

圖3 “Fingerprint“圖像修復(fù)結(jié)果

圖4 “Barbara“圖像結(jié)構(gòu)紋理修復(fù)結(jié)果

圖5 Fingerprint圖像結(jié)構(gòu)紋理修復(fù)結(jié)果

下面以“Barbara”圖像為例,研究當(dāng)參數(shù)p固定時,不同的參數(shù)k對實(shí)驗(yàn)結(jié)果的影響.當(dāng)p=0.6時,從圖6(a)可以看出不同的參數(shù)k對實(shí)驗(yàn)結(jié)果的影響不大,但當(dāng)k＞1時,隨著k的增大,步長參數(shù)γ越來越小,實(shí)驗(yàn)所需的迭代次數(shù)越來越多,見圖6(b).為了對算法進(jìn)行加速,文中對閾值參數(shù)τ采用連續(xù)性策略.τ首先選取較大的值,隨著迭代的進(jìn)行,τ分別乘以常數(shù)因子逐漸減小,最終達(dá)到預(yù)先指定的值.綜合考慮修復(fù)圖像的質(zhì)量及實(shí)驗(yàn)運(yùn)行速度,文中所有實(shí)驗(yàn)統(tǒng)一選取參數(shù)k=1.

4 結(jié)束語

筆者基于非凸稀疏正則化考慮了卡通紋理圖像修復(fù)最小化問題,并且建立了此問題的迫近前項(xiàng)后項(xiàng)分裂算法.大量的數(shù)值實(shí)驗(yàn)表明了此非凸稀疏圖像修復(fù)算法比經(jīng)典的TV修復(fù)和常見的l1稀疏修復(fù)算法有更好的修復(fù)結(jié)果,圖像的紋理結(jié)構(gòu)信息修復(fù)較好.值得注意的是,該算法的運(yùn)行速度與l1稀疏算法相比有稍慢的缺點(diǎn),下一步將研究此算法的快速算法.

表2 不同圖像3種算法的修復(fù)結(jié)果

圖6 PSNR與迭代次數(shù)隨著平衡參數(shù)k的變化曲線圖

[1]Chan T,Shen J.Mathematical Models of Local Non-Texture Inpaintings[J].SIAM Journal on Applied Mathematics, 2002,62(3):1019-1043.

[2]許建樓,馮象初,郝巖.二階總廣義變分圖像修復(fù)模型及其算法[J].西安電子科技大學(xué)學(xué)報(bào),2012,39(5):18-23. Xu Jianlou.Feng Xiangchu,Hao Yan.Second Order Total Generalized Variational Inpainting Model and Its Algorithm [J].Journal of Xidian University,2012,39(5):18-23.

[3]Bertalmio M,Vese L,Sapiro G,et al.Simultaneous Structure and Texture Image Inpainting[J].IEEE Transactions on Image Processing,2003,12(8):882-889.

[4]Cai J F,Ji H,Liu C,et al.Framelet Based Blind Motion Deblurring from A Single Image[J].IEEE Transactions on Image Processing,2012,21(2):562-572.

[5]Elad M,Starck J L,Querre P,et al.Simultaneous Cartoon and Texture Image Inpainting Using Morphological Component Analysis(MCA)[J].Applied and Computational Harmonic Analysis,2005,19(3):340-358.

[6]Cai J F,Dong B,Osher S.Image Restoration:Total Variation;Wavelet Frames;and Beyond[J].Journal of American Mathematical Society,2012,25(4):1033-1089.

[7]Cai J F,Chan R H,Shen Z.Simultaneous Cartoon and Texture Inpainting[J].Inverse Problem Imaging,2010,4(3): 379-395.

[8]Candès E J,Donoho D L.New Tight Frames of Curvelets and Optimal Representations of Objects with Piecewise C2 Singularities[J].Communications on Pure and Applied Mathematics,2004,57(2):219-266.

[9]Daubechies I,Han B,Ron A.Framelets:MRA-based Constructions of Wavelet Frames[J].Applied Computational Harmonic Analysis,2003,14(1):1-46.

[10]Yu Guoshen,Sapiro G,Mallat S.Solving Inverse Problems With Piecewise Linear Estimators:From Gaussian MixtureModels to Structured Sparsity[J].IEEE Transactions on Image Processing,2012,21(5):2481-2499.

[11]Chan R H,Chan T F,Shen L,et al.Wavelet Algorithms for High Resolution Image Reconstruction[J].SIAM Journal on Scientific Computing,2003,24(4):1408-1432.

[12]Chartrand R.Nonconvex Splitting for Regularized Low-Rank+Sparse Decomposition[J].IEEE Transactions on Signal Processing,2012,60(11):5810-5819.

[13]Chartrand R,Sidky E Y,Pan Xiaochuan.Frequency Extrapolation by Nonconvex Compressive Sensing[C]//IEEE International Symposium on Biomedical Imaging.Piscataway:IEEE,2011:1056-1060.

[14]Chartrand R,Staneva V.Restricted Isometry Properties and Nonconvex Compressive Sensing[J].Inverse Problems, 2008,24(3):20-35.

[15]Ron A,Shen Z.Affine Systems in L2(Rd)the Analysis of the Analysis Operator[J].Journal of Functional Analysis, 1997,148(2):408-447.

[16]Donoho D.For Most Large Underdetermined Systems of Linear Equations,the Minimal l1-norm Solution is Also the Sparsest Solution[J].Communications on Pure and Applied Mathematics,2006,59(6):797-829.

[17]Xu Zongben,Chang Xiangyu,Xu Fengmin.L-1/2 Regularization:a Thresholding Representation Theory and a Fast Solver[J].IEEE Transactions on Neural Networks and Learning Systems,2012,23(7):1013-1027.

[18]Meinshausen N,Yu B.Lasso-Type Recovery of Sparse Representations for High-Dimensional Data[J].The Annals of Statistics,2009,37(1):246-270.

[19]Combettes P L,Wajs V R.Signal Recovery by Proximal Forward-Backward Splitting[J].Multiscale Modeling& Simulation,2005,4(4):1168-1200.

(編輯:王 瑞)

Nonconvex image inpainting via balanced regularization approach

WU Yulian1,2,FENG Xiangchu1
(1.School of Mathematics and Statistics,Xidian Univ.,Xi’an 710071,China; 2.Common Course Department,Xi’an Medical College,Xi’an 710021,China)

Real images usually have two layers,namely,cartoons and textures,both of these layers have sparse approximations under some tight frame systems such as curvelet,local DCTs,and B-spline wavelet.In this paper, we solve the image inpainting problem by using two separate tight frame systems which can sparsely represent the two parts of the image.Different from existing schemes in the literature which are either analysis-based or synthesis-based sparsity priors,our minimization formulation applies the nonconvex sparsity prior via the balanced approach.We also derive iterative algorithms for finding their solutions.Numerical simulation examples are given to demonstrate that our proposed nonconvex method achieves significant improvements over the classical l1sparse method and the variation TV method in image inpainting.

image inpainting;cartoons and textures;nonconvex;tight frame systems

TP391.41

A

1001-2400(2014)05-0141-07

2013-05-16< class="emphasis_bold">網(wǎng)絡(luò)出版時間:

時間:2014-01-12

國家自然科學(xué)基金資助項(xiàng)目(61271294)

吳玉蓮(1978-),女,西安電子科技大學(xué)博士研究生,E-mail:wyl_wp711@163.com.

http://www.cnki.net/kcms/doi/10.3969/j.issn.1001-2400.2014.05.024.html

10.3969/j.issn.1001-2400.2014.05.024