利用平衡方法的非凸圖像修復

吳玉蓮,馮象初

(1.西安電子科技大學數學與統計學院,陜西西安 710071; 2.西安醫學院公共課部,陜西西安 710021)

利用平衡方法的非凸圖像修復

吳玉蓮1,2,馮象初1

(1.西安電子科技大學數學與統計學院,陜西西安 710071; 2.西安醫學院公共課部,陜西西安 710021)

自然圖像通常可以看成由兩部分構成:卡通部分和紋理部分,這兩部分在一些緊框架下,比如曲線波、局部余弦變換、樣條小波等都有稀疏表示.該文研究在兩個可分離緊框架下的圖像修復問題.與大部分算法普遍采用基于分析的或者合成的稀疏先驗的不同之處在于:文中采用基于平衡的方法,且對稀疏系數使以非凸限制;最后給出了迭代算法.數值實驗表明了建議的非凸圖像修復方法比普通的l1凸方法和經典的變分TV方法有更好的修復效果.

圖像修復;卡通紋理;非凸;緊框架

數字圖像修復是當前數字圖像處理和計算機圖像學中的一個熱點問題,其在文物保護、剔除圖像或視頻中的一些文字,修復網絡傳輸中丟失或損壞的視頻信息等方面都有很高的應用價值.

變分和偏微分方程是最流行的圖像修復方法之一,其基本思想是根據整個目標區域的外部鄰域內已知像素的幾何方向,向區域內部各向異性地擴散灰度信息,從而實現目標區域的重構.這類方法對于目標區域相對較小的非紋理圖像能夠獲得較好的修復結果.但當目標區域較大時,區域內部信息并不能由外部鄰域內的已知信息簡單估計;同理,當目標區域內包含有復雜的紋理特征時,變分和偏微分方程的處理結果并不能保持周期性、重復性的紋理信息.此類方法的優點就是能保持圖像的邊界,尤其適用于分片光滑圖像.文獻[1-2]等都屬于此類修復方法.

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

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

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

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

1 迫近p范數

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

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

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

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

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

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

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

2 非凸稀疏的圖像修復模型及算法

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

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

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

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

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

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

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

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

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

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

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

3 數值實驗

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

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

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

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

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

圖2 “Barbara“圖像修復結果

圖3 “Fingerprint“圖像修復結果

圖4 “Barbara“圖像結構紋理修復結果

圖5 Fingerprint圖像結構紋理修復結果

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

4 結束語

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

表2 不同圖像3種算法的修復結果

圖6 PSNR與迭代次數隨著平衡參數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]許建樓,馮象初,郝巖.二階總廣義變分圖像修復模型及其算法[J].西安電子科技大學學報,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">網絡出版時間:

時間:2014-01-12

國家自然科學基金資助項目(61271294)

吳玉蓮(1978-),女,西安電子科技大學博士研究生,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