李志丹，和红杰，尹忠科，陈　帆

(1.西南交通大学信号与信息处理四川省重点实验室，四川成都610031; 2.北京遥感信息研究所，北京100192)



基于Curvelet方向特征的样本块图像修复算法

李志丹1，和红杰1，尹忠科2，陈帆1

(1.西南交通大学信号与信息处理四川省重点实验室，四川成都610031; 2.北京遥感信息研究所，北京100192)

摘要：能否保持修复后图像的结构连贯性和邻域一致性决定了修复性能的优劣.为提高现有样本块修复算法性能，本文提出基于Curvelet变换的样本块图像修复算法.首先利用Curvelet变换估计待修复图像的4方向特征.然后利用颜色信息与方向信息共同衡量样本块间的相似度，在此基础上构造颜色-方向结构稀疏度函数.同时根据构造的加权颜色-方向距离寻找合适的多个匹配块，并利用多个匹配块在构造的颜色和方向空间内的邻域一致性约束下稀疏表示目标块，同时根据目标块所处区域特性自适应确定误差容限.实验结果表明提出算法较现有算法可获得更优的修复效果，尤其是在修复富含结构纹理破损类型的图像时.

关键词：图像修复;方向特征;加权的颜色-方向距离;颜色-方向结构稀疏度; Curvelet变换;稀疏表示

1　引言

图像修复的目的即是通过填充丢失区域的信息以获得视觉上的合理效果.图像修复根据破损区域大小可以分为适合于小区域破损类型的修复算法和针对大区域破损图像修复算法.

适合于小区域破损的修复算法主要可以分为基于扩散的方法［1］和基于稀疏的方法［2］.基于扩散的方法是利用偏微分方程决定扩散系数，采用破损信息周围的邻域信息进行加权平均.基于稀疏的方法利用图像在变换域内的稀疏性来重构破损图像［2］.近年来，有研究人员训练不同的基来构造原子库以重构不同类型的图像［3，4］.基于扩散的方法和基于稀疏的方法修复破损区域较大或富含结构纹理破损的图像时易产生平滑效应.

适合于大区域破损的图像修复算法为基于样本块的方法［5］，主要包括块选择(即填充顺序)和块填充两个部分.此后，研究者在这两个方面进行了诸多研究.在块选择方面，Xu和Sun［6］提出基于结构稀疏度的填充顺序.文献［7］根据图像分割方法来指导修复顺序.Hareesh等人［8］利用梯度函数的分数阶导数来构造优先权函数.文献［9］利用局部梯度特征来提高填充顺序的稳定性.尽管上述方法均是为了保证填充结果的结构连贯性，但在针对富含纹理结构信息的破损图像进行修复时，很难保持其结构连贯性.

在块填充方面，文献［9］在匹配准则中增加平均值补偿和惩罚项.范冠鹏［10］引入多方向特征来构造匹配准则.但这些方法［5，7～10］仍旧采用单个最优匹配块进行填充，易产生块效应.因此，研究人员提出利用多个块的加权来进行填充.如Xu和Sun［7］将多个块的稀疏表示作为填充信息.课题组［11］自适应选择邻域一致性约束的权重.文献［12］利用低秩矩阵求取填充信息.Ogawa等人［13］利用傅里叶幅度来估计丢失信息.虽然上述多个块填充方法可削弱块效应，但因缺乏考虑方向信息，使得修复效果趋于平滑和模糊.

为提高修复后图像的结构连贯性和邻域一致性，本文利用Curvelet变换估计待修复图像的4方向特征，将其与颜色信息结合构造加权颜色-方向距离(Weighted Color-Direction Distance，WCDD).而后构造颜色-方向结构稀疏度函数以获得稳定的填充顺序.并根据WCDD寻找多个匹配块，而后利用多个块在构造的颜色和方向空间内的邻域一致性约束条件下稀疏表示待填充块，同时自适应确定误差容限值.

2　本文方法

为更好的保持修复后图像中的结构连贯性，纹理清晰性及与邻域信息的连续一致性，本文提出基于Curvelet方向特征的样本块图像修复算法.

2.1方向特征提取方法

Curvelet变换具有高度的各向异性等优点［14］，故本文利用Curvelet变换来提取图像的方向特征［15］.首先采用文献［11］算法对破损图像I进行预修复，得到预修复图像Ir，采用Curvelet变换对Ir进行多尺度多方向分解:

其中，C+表示Curvelet正变换，Q为Curvelet系数矩阵，可表示为{ Qj，l|j代表尺度，l代表方向} .

将2-5尺度上的Curvelet系数矩阵Qj，l(j = 2，3，4，5)按方向划分为四个集合Z1，Z2，Z3，Z4，如图1所示.第k个方向的方向特征矩阵Ak(k =1，2，3，4)为

其中，C-1代表Curvelet逆变换，Hk(Q)为

按式(2)可得到方向特征图像A1，A2，A3和A4.

2.2加权的颜色-方向距离

利用上节中提取的4方向特征Ak(k =1，2，3，4)和颜色信息构造WCDD dw，定义为:

其中Ψp，Ψq分别为待修复图像I中以点p，q为中心的样本块，Λp和Λq分别为方向特征图像Ak中以点p，q为中心的方向特征块; d表示样本块间的均方距离，η为加权系数，用以平衡颜色信息和方向信息.

为了说明引入方向信息的重要性，对图2(b1)～(b2)进行修复，分别根据SSD(Sum of Squared Distance)［5］，CGD(Color-Gradient Distance)和WCDD来寻找单个最优匹配块并进行填充，修复算法中其余部分是采用相同的设置，因此修复结果仅依赖于匹配准则.从修复结果及PSNR值中可以看出，利用WCDD得到的修复效果最优，故采用WCDD可以更好的度量样本块间的差异性.

2.3填充顺序

为了更好的保持修复后图像中结构部分的连贯性，本文根据WCDD构造颜色-方向结构稀疏度函数(Color-Direction Structure Sparsity，CDSS)来确定填充顺序，样本块Ψp的颜色-方向结构稀疏度S(p)如下定义所示:

其中Ns(p)为以点p为中心的邻域N(p)(N(p)的大小大于样本块的大小)内的已知块集合，而Xp，k为样本块Ψp和Ψk的相似度函数，Ns(p)和Xp，k分别定义为:

其中C(p)表示样本块Ψp中包含已知信息的多少，若p ∈Ω，C(p)初始化为0，否则初始化为1.

2.4稀疏表示

为更好的保持纹理信息的清晰性，本文要求稀疏表示信息要同时保证与邻域信息在颜色与方向信息上的连续一致性.

令Ψt和Λt分别为根据WCDD寻找到的M个匹配块{Ψq}q =1，…，M和对应的方向块{Λq}q =1，…，M的稀疏表示，即为:

为防止CDSS值过小导致不稳定的填充顺序，本文将S(p)取值范围变换到0.2～1之间.而后再将S(p)用于计算优先权P(p):

其中C(p)为样本块的置信度项，定义为:

则首先要求稀疏表示后信息Ψt和Λt在已知信息部分与当前待填充块Ψm和方向特征块Λm充分接近:

且要求Ψt和Λt在未知信息部分要与邻域信息保持连续一致:

其中E和F分别表示提取样本块中未知信息的矩阵，β为邻域连续一致性的权重系数，用来平衡上述两项约束.

将颜色空间和方向空间内的邻域一致性约束写入一个更紧的框架中:

现有文献［6，11，12］一般选择固定的误差容限δ值，但这是不合理的.因为若误差容限值选择过大时，则在平滑区域内易产生块效应;而若误差容限值选择过小时，则会降低结构纹理区域的清晰性.为更好的保持邻域一致性，本文采用当前待填充块的标准差值作为误差容限:

其中SD(Ψm)表示当前待填充块Ψm的标准差，λ为一乘子，本文中设为3，同时设置δ的最大值为125，最小值为5.

3　实验与结果分析

本文实验部分分为三个部分，首先是分析权重系数对修复性能的影响，然后从小尺度破损和目标移除两个方面验证本文算法的修复性能.计算CDSS的邻域N(p)设置为25* 25，其他参数η，β，λ和M分别为0.3，0.5，3和25.

3.1参数η分析

首先探讨关于参数η对修复效果的影响，对图3中包含不同破损类型的图像进行修复.

将η从0到1变化，测试η取不同值时对图3中各个图像的修复结果的影响，其PSNR值如图4所示.从图4中可以看出，最初随着η的逐渐增大，PSNR值也逐渐增大;而后随着η的继续增大，各个图像的PSNR值是呈下降趋势，尽管下降的幅度较小.从图4(a)中可以看出，每个图像取得最大PSNR值时对应的η值不是完全相同的，但是η取值均在0.3 -0.4之间，且这个区间内的PSNR值相差不大.从图4(b)中可以看出，当η取值为0.3时取得最大平均PSNR值.因此在下面的实验中，将η取值为0.3.

3.2小尺度破损

为说明本文算法能够较好的修复富含结构和纹理信息的图像，选择包含不同结构及纹理信息的图像作为测试图像，并与文献［4，6，9～11］进行修复性能对比，修复结果分别如图5～7所示.

从图5～7中可以看出，文献［4］的修复结果中存在平滑效应，且不能很好的修复富含结构纹理的图像.文献［6，11］的修复结果中出现了些微的结构不连贯性，并未能很好的保持与邻域信息的连续一致性.文献［9，10］均出现了结构不够连贯的情形以及接缝效应.而本文算法获得了良好的修复效果，很好的保持了结构连贯性及与邻域信息的连续一致性，如图5(e)～7(e)所示.并且由表1可知，本文算法修复结果的PSNR值最高.从视觉效果和客观评价指标可以得出，本文算法对于富含结构纹理的图像能够获得优良的修复效果，满足人眼视觉要求.

3.3目标移除

为进一步说明本文算法的有效性，针对目标移除图像进行修补，并与算法［6，9～11］及嵌入到Photoshop中的算法［16］进行修复性能对比.

从修复效果图8～9可以看出文献［16］并不能很好的保持结构部分的连贯性，且出现了错误匹配的现象.文献［6，11］未能总是保持结构部分的连贯性，且存在些微的邻域不连续性.而文献［9，10］不能很好的保持结构连贯性，且出现了严重的邻域不连续性以及明显的块效应.本文算法能够保持修复后图像的结构连贯性，纹理信息的清晰性及与邻域信息的连续一致，取得了优于文献［6，9～11，16］算法的修复效果.

表1　不同修复算法的修复性能对比表(PSNR/dB)

4　结论

为更好的保持结构连贯性及与邻域的连续一致性，本文利用Curvelet变换来提取图像中的4方向特征，以此构造WCDD;并提出了基于CDSS的填充顺序;根据WCDD寻找多个匹配块;最后在颜色和方向空间内构造局部一致性约束的能量优化方程，并自适应确定误差容限值.实验结果表明本文算法较现有算法在块移除及目标移除上均有明显提高，充分说明了本文算法的有效性.但本文方法仅提取了图像中的4个方向的特征，未来还将深入探讨不同方向特征个数以及利用不同超小波变换提取方向特征对图像修复性能的影响.

参考文献

［1］Bertalmio M，Sapiro G，Caselles V，et al.Image inpainting［A］.Proceedings of the 27th Annual Conference on Computer Graphics and Interactive Techniques［C］.New Orleans: ACM Press，2000.417 - 424.

［2］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.

［3］Mairal J，et al.Non-local sparse models for image restoration［A］.Proceedings of 12th IEEE International Conference on Computer Vision［C］.Kyoto: IEEE Press，2009.2272 -2279.

［4］Dong W S，Shi G M，Li X.Nonlocal image restoration with bilateral variance estimation: a low-rank approach［J］.IEEE Transactions on Image Processing，2013，22(2): 700 -711.

［5］Criminisi A，Perez P，Toyama K.Object removal by exemplar-based inpainting［A］.Proceedings of IEEE Computer Society Conference on Computer Vision and Pattern Recognition［C］.Madison Wisconsin: IEEE Press，2003.721 -728.

［6］Xu Z B，Sun J.Image inpainting by patch propagation using patch sparsity［J］.IEEE Transactions on Image Processing，2010，19(5): 1153 -1165.

［7］吴晓军，李功清.基于样本和线性结构信息的大范围图像修复算法［J］.电子学报，2012，40(8): 1509 -1514.Wu Xiaojun，Li Gongqing.Large scale image inpainting based on exemplar and structure information［J］.Acta Electronica Sinica，2012，40(8): 1509 - 1514.(in Chinese)

［8］Hareesh A S，Chandrasekaran V.Exemplar-based color image inpainting: a fractional gradient function approach［J］.Pattern Analysis and Applications，2014，17: 389 -399.

［9］范冠鹏，和红杰，陈帆，等.基于局部特性的图像修复算法［J］.光电子·激光，2012，23(12): 2410 -2417.Fan Guanpeng，He Hongjie，Chen Fan，et al.An image inpainting algorithm based on local properties［J］.Journal of Optoelectronics·Laser，2012，23(12):2410 -2417.(in Chinese)

［10］范冠鹏.基于样本块结构特性的图像修复算法［M］.西南交通大学，2013.32 -46.Fan Guanpeng.Image Inpainting Algorithm Based on Exemplar Structure Characteristics［M］.Southwest Jiaotong University，2013.32 -46.(in Chinese)

［11］李志丹，和红杰，尹忠科，等.基于块结构稀疏度的自适应图像修复算法［J］.电子学报，2013，41(3):549 -554.Li Zhidan，He Hongjie，Yin Zhongke，et al.Adaptive image inpainting algorithm based on patch structure sparsity［J］.Acta Electronica Sinica，2013，41(3):549 -554.(in Chinese)

［12］Wang Y X，Zhang Y J.Image inpainting via weighted sparse non - negative matrix factorization［A］.Proceedings of 18th IEEE International Conference on Image Processing［C］.Barcelona: IEEE Press，2011.3409 -3412.

［13］Ogawa T，Haseyama M.Missing texture reconstruction method based on error reduction algorithm using Fourier transform magnitude estimation scheme［J］.IEEE Transactions on Image Processing，2013，22(3):1252 -1257.

［14］Starck J，E Candes，D Donoho.The curvelet transform for image denoising［J］.IEEE Transactions on Image Processing，2002，11(6):670 -684.

［15］赵亮，等.基于Curvelet的纹理方向自适应图像插值［J］.光电子·激光，2012，23(4):798 -804.Zhao Liang，et al.Texture direction adaptive image interpolation based on Curvelet transform［J］.Journal of Optoelectronics·Laser，2012，23(4):798 -804.(in Chinese)

［16］Goldman D，Shechtman E，Barnes C，et al.Content-aware fill ［OL］.http: / /www.adobe.com/technology/projects/content-aware-fill.html，2009.

李志丹女，1985年生于河南，在读博士，主要研究方向数字图像修复.E-mail: dan.807@163.com

和红杰(通信作者)女，1971年生于河南，博士，教授，主要研究方向为数字图像处理、信息隐藏.E-mail: hjhe@swjtu.cn

Exemplar Based Image Inpainting Algorithm Using Direction Features of Curvelet Transform

LI Zhi-dan1，HE Hong-jie1，YIN Zhong-ke2，CHEN Fan1
(1.Sichuan Key Laboratory of Signal and Information Processing，Southwest Jiaotong University，Chengdu，Sichuan 610031，China; 2.Institute of Remote Sensing Information，Beijing 100192，China)

Abstract:Whether the structure coherence and neighborhood consistency can be well maintained directly determines the performance of an inpainting algorithm.To achieve a better inpainting performance，this paper proposes an exemplar based image inpainting algorithm based on direction features extracted by Curvelet transform.Firstly，the super-wavelet transform is applied to extract four direction features of the corrupted image.Then the color and direction information are utilized to measure the similarities between patches.Subsequently，a color-direction structure sparsity function is defined.Afterwards，multiple suitable candidate patches are searched based on the weighted color-direction distance and these candidate patches are applied to sparsely represent target patch under the local neighborhood consistence constraints both in color and direction spaces.Moreover，in searching candidate patches，the error tolerance is adaptively decided according to the feature of target patch.Experiment results show that the proposed method can achieve better inpainted results than the state-of-the-art algorithms，especially when dealing with structure and texture images.

Key words:image inpainting; direction feature; weighted color-direction distance; color-distance structure sparsity; Curvelet transform; sparse representation

作者简介

基金项目:国家自然科学基金(No.61461047，No.61373180); 2014年西南交通大学博士研究生创新基金和中央高校基本科研业务费专项基金;四川省科技创新苗子工程(No.2014-048)

收稿日期:2014-06-03;修回日期: 2014-12-11;责任编辑:李勇锋

DOI:电子学报URL：http: / /www.ejournal.org.cn10.3969/j.issn.0372-2112.2016.01.022

中图分类号：TP391.41

文献标识码：A

文章编号：0372-2112(2016)01-0150-05