利用平衡方法的非凸图像修复

吴玉莲,冯象初

(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