一种改进的基于样例的图像修复算法

一种改进的基于样例的图像修复算法

张绚;尹立新;李振杰

【摘 要】Classic Criminisi image inpainting algorithm inpaints both the

texture and structure of the image simultaneously by combining the

advantages of partial differential equation and texture synthesis

algorithm,so gets better visual effect.But this exemplar-based image

inpainting algorithm takes the confidence and the data term into

consideration only while defining the priority,which leads to the

propagation of error information,and attenuates the inpainting

results.Based on Criminisi algorithm,we propose an improved exemplar-based image inpainting scheme.By redefining the priority of the inpainting

patches,the scheme adds a geometrical parameter that measures the

smoothness of image and enlarges the limitation condition of optimal

matching patch at the same time,so that the inpainted images attains

better visual effects.%经典的Criminisi图像修复算法，通过结合偏微分方程算法和纹理合成算法两者的优点，对图像的纹理和结构同时进行修复，获得了较好的视觉效果。但基于样例的图像修复算法在定义优先权时仅考虑了置信度和数据项，导致错误信息的繁衍，使修复结果不理想。在Criminisi算法基础上，提出一种改进的基于样例的图像修复方法。通过重新定义修复块的优先权，增加一种度量图像平滑性的几何量，同时增加最佳匹配块的限制条件，从而使修复后的图像获得了更好的视觉效果。

【期刊名称】《计算机应用与软件》 【年(卷),期】2014(000)010

【总页数】4页(P216-219)

【关键词】图像修复;样本;优先权;平滑性

【作 者】张绚;尹立新;李振杰

【作者单位】山东大学信息科学与工程学院 山东 济南250100;山东大学信息科学与工程学院 山东 济南250100;山东大学信息科学与工程学院 山东 济南250100

【正文语种】中 文

【中图分类】TP391

图像修复第一次被Bertalmio等人[1]应用到图像处理领域中，该技术应用范围很广泛： 对破损图像的修补以及旧照片和文字中损坏的区域修补，或者对于特定背景下物体等目标对象的移除修复。Chen和Shen提出了一种TV模型[2]，继而Chen等人介绍了基于欧拉弹力曲率的修复模型，这种模型能沿曲率正确传播信息[3]。以上方法都是基于偏微分方程(PDE)的修复方法，即以像素为单位向目标区域扩散。PDE根据图像的性质进行扩散，所以图像的线性结构很好地被保留。但是在扩散过程中，PDE能使图像平滑，如果破损区域比较大或者图像的纹理比较复杂，修复区域会出现模糊。

基于样例的图像修复用于纹理合成中，将图像的纹理信息复制到待填充的区域内[4-7]，这些修复模型思想是从图像的已知区域中寻找与受损区域最匹配的块进行填充，在修复时可能会丢失部分结构纹理。Criminisi [8]提出的是一种沿等照度线扩散的基于样例的图像修复方法，该算法很好地结合前述各修复算法的优点，能够正确修复破损区域比较大的图像，即保留了图像的结构信息，也保留了图像的纹理信息。虽然Criminisi算法能够正确地修复图像的结构和纹理信息，但对部分图像内含有较强的结构信息，强结构信息可能持续优先权处理，会导致不正确的修复结果，由于算法是直接将匹配纹理块复制到破损区域进行填充，这样很容易造成错误信息的积累延续，导致图像的整体结构出现较大偏差。

目前，国内外数字图像修复领域内，很多学者研究了Criminisi算法并在此基础上，针对Criminisi算法的不足，提出大量的改进算法，文献[9-11]分别从计算效率、匹配准确度和全局信息平均值等方面来进行改进，并且与Criminisi算法相比较，在效率和效果上都得到了很好的改善。这些算法在定义优先权时仅考虑了置信度和数据项，在图像修复过程中可能引起错误信息的繁衍，使修复结果不理想。文献[12]在对Criminisi算法进行改进时，考虑到等照度线的几何信息即曲率对填充效果的影响，提高了修复图像的修复正确度。

本文提出了一种改进的基于样例的图像修复方法，同样也是在Criminisi算法基础上进行改进，与其他改进方法不同的是重新定义修复块的优先权，考虑了图像的平滑度对填充次序及搜索匹配块的影响，增加了一种度量图像平滑性的几何量，同时增加最佳匹配块的限制条件，经过多组实验证明，本文改进的算法能够获得更为理想的修复图像。

基于样例的纹理合成算法是目前大区域纹理修复的经典算法，其基本原理是： 如图1所示，其中I表示整个原图像，Ω为破损区域，又称待修复区域，δΩ为待修复区域边界，Φ为图像的已知源区域，p为边界上的一点，Ψp为以p为中心的待填充的目标块。

图像修复的优先权顺序至关重要，它是决定图像最终修复结果的关键因素。边界点p的优先权P(p)=C(p)D(p)。式中：C(p)表示当前块的置信度；D(p)表示过p点的等照度线强度。

式中： ▽表示等照度线的切线方向；np为p点外边界线的单位法向向量；|Ψp |是Ψp内像素个数；α为归一化因子，取255。

确定具有最大优先权的待修复块Ψp后，在原图有效区域内搜索Ψp的最优匹配块Ψq，使之满足关系：

式中，Ψq′为图中匹配块；为Ψp，Ψq′对应点颜色RGB值的误差的平方和(SSD);

I为对应各颜色通道的像素值。

在利用上述两公式找到与Ψp最匹配的匹配块后，把匹配块中的已知像素对应复制到目标块中破损的未知像素点。

具有最高优先权的待目标块Ψp，修复完毕后，将Ψp块内修复好的像素点的置信度更新为此目标块中心点p的置信度，并更新待修复区域的边界δΩ。

重复以上步骤，直到将所有破损区域修复完为止。

基于样例的图像修复算法，结合偏微分方法和纹理合成方法两者优点，同时进行图像的纹理信息和结构信息的修复，避免了扩散产生的模糊和纹理合成中错误的结构信息，得到了较为理想的视觉修复效果。虽然基于样本的图像修复算法取得了很好的修复效果，但对于图像修复过程中，随着边界的更新，置信度C(p)迅速趋于0，优先权的定义是置信度和数据项两者相乘，优先权大小几乎区别不大，则优先权的定义就失去意义。如果循环中某个块被填充了不符合视觉效果的信息，可能就在此基础上，错误信息慢慢积累，最终导致修复效果出错。

2.1 重新定义优先权

针对以上分析的优先权定义的不足，本文在原来定义的优先权的基础上，新增一项图像重要的几何量，称之为平滑项L(p),重新定义的优先权形式为：

并定义L(p)为图像的拉普拉斯算子，即L(p)=ΔI，具有锐化作用，可以使平滑处理后的图像的模糊边缘变得清晰。L(p)越大表示图像的边缘越清晰，有强边缘信息。当置信度C(p)趋于0时，D(p)几乎不起作用，平滑项对优先权作出比较大的贡献，优先修复图像具有强边缘的区域。a和b是调节因子，a和b均取值为0～1之间，并且设定a+b=1。当图像平滑、纹理简单时，前一项作用大，控制a增大，b减小；当图像的纹理结构比较复杂，边缘信息比较突出时，减小a，增大b。因此a和b用于控制各项为优先权作贡献的比重，图像本身具有多样性，对各种类型的图像，图像具有不一样的纹理信息和结构信息。因此，对于各类图像来说，图像内信息的各几何量在优先权中占比重各不相同。针对各种类型的图像，根据图像的信息，可以设置不同的权系数，以便提高算法修复的正确度。

2.2 增加限制参数的相似匹配块

本文寻找最佳匹配块的原理方法与Criminisi算法搜索匹配块一样，都是利用相似性在已知区域寻找最佳匹配块。通过分析Criminisi算法，在搜索过程中，可能求得相同的SSD，虽然值都是最小，但是无法判断其颜色信息是否符合待修复区域以及人的视觉系统。因此，不排除出现错误信息的繁衍现象的可能性，导致整个修复结果不理想。为避免在求解最佳匹配块中出现相同的SSD，得到更精确的匹配信息。本文加入限制参数，如下：

式中，AVi为具有最大优先权块的R,G,B三个分量上的像素平均值。

式中，NSSD是目标块与匹配块的各颜色差值之和与匹配块与目标块颜色平均值差值之和的总和。计算最小NSSD就可以得相对较为准确的匹配块。

2.3 改进后的算法流程

步骤1 确定待修复区域。利用“掩膜”法找出待修复的区域，即在破损区域填充一种指定的颜色，如绿色(0,255,0)；

步骤2 找出待修复区域边界δΩ；

步骤3 找出具有最大优先权的目标块，即第一个被修复的块。根据式(6)计算以边界上δΩ的点为中心的所有目标块的优先权，确定出具有最大优先权的目标块；

步骤4 在已知源区域中搜索最佳匹配块。根据式(9)在已知区域内搜寻最佳匹配块，把匹配块中的已知像素对应复制到目标块中破损的未知像素点； 步骤5 根据式(5)更新每一次修复好的像素点的置信度，同时更新待修复区域的边界δΩ；

步骤6 重复执行步骤2-步骤5直至δΩ=∅。

用Matlab实现的核心编程如下:

为了证明本文改进的新算法的优势，在Matlab7.10(R2010a)为平台进行仿真实验，并作分析比较。以下对三组不同类型的图像做实验，所用实验环境是PD 2.66GHz，1.92GB内存。将本文算法所得实验结果分别与Criminisi算法、文献[12]改进算法结果进行比较。

图2是对图中蹦极人的移除修复。图像大小是308×206像素，且待修复区域是7

996个像素。如(b)所示是Criminisi算法修复结果；文献[12]改进算法修复结果如(c)所示；如(d)所示，是本文改进算法a=0.88,b=0.12时修复结果。观察(b)，(c)和(d)，图(b)中屋檐下虽然被填充，但有部分绿草被修复到屋顶上，导致视觉效果不理想；同时，岸边的草丛延伸到水面上来。(c)，(d)都很好地克服这两处错误，整幅图像修复的较为合理，更符合人类的视觉系统。

图3是对多物体移除修复。图像大小是200×200像素，图片来源是文献[13]提供的图片库，待修复区域为3 535个像素。修复此图时，取a=0.65,b=0.35时，得到最佳视觉效果修复图。Criminisi算法修复中，(b)中路标地图不能完全修复，出现了部分丢失现象，台阶处修复模糊，而且大树的根部有明显的修复错误；而(c)，(d)很明显地在一定程度上改善了两处缺陷，使修复效果更加理想。