一种基于样例的快速图像修复算法*

代仕梅,张红英,曾 超

(西南科技大学 信息工程学院，四川 绵阳621010)

图像修复是图像复原研究中的一个重要内容，它的主要思想是:对图像中遗失或者损坏的区域，利用未损坏的图像信息，按照一定的规则进行填充，并且尽可能地使修复后的图像接近或达到原来的视觉效果。随着近几年数字技术的发展以及数码产品的普及，这一技术除了应用于破损照片的修复，还被用于文本提取、目标移除、超分辨率、图像压缩/传输以及视频错误隐藏等方面。

目前，图像修复中占主流的修复模型有：偏微分方程的修复模型[1-2]、纹理合成[3]的修复模型。 前者计算量大、耗时长、对纹理的还原能力有限，处理大区域图像会有明显的模糊现象，因此只适合于划痕、污迹和文字等细窄的区域修复。相比之下，后者将待修复区域周围的图像作为样本,从中提取特征并选取匹配的纹理，将其合成到待修复区域内，适用于较大区域的修复。

现实中的图像不是由简单结构和单一纹理拼接而成的，而是同时包含复杂的结构和多种纹理特征。参考文献[4]将图像分割为结构和纹理两部分，然后分别用偏微分方法和纹理合成技术进行处理，最后将两种处理结果进行融合。但对实际图像而言，该方法修复区域较小，速度较慢，对较大区域修复仍然有一定的模糊。Criminisi等人在2003年提出了一种不用分割图像，同步处理纹理和结构的基于样例的图像修复算法[5]。他们的算法取得了满意的效果，但是耗费的时间过长，另外优先权和相似度的计算还存在一定不足。本文改进了参考文献[5]的图像修补算法。为了使优先权计算更加准确，本文采用梯度数据项和置信度共同决定填充顺序；为加快修复速度，本文采用局部窗口搜索的策略；最后利用颜色和梯度共同决定相似性，使得修复后的图像具有更好的视觉效果。大量实验结果表明，该算法提高了修复效率，同时产生了更满意的视觉效果。

1 算法的基本步骤

对于待修复图像，手工选定待修补区域Ω，也称为目标区。如图1所示，Φ代表目标区域以外的部分(Φ=I-Ω)，提供修复过程中的样本资源，又称为样本区。Ψ为模板窗口，也称为最小的填充单元 (略微大于样本区的最大纹理元)。

算法描述如下：

(1)手工选定待修复区域或待移除的目标区域Ω;

(2)初始化需要修复图像的边界∂Ω0;

(3)while(提取修复边界 ∂Ωn且 Ωn≠Φ)

①优先权的计算：目标块 Ψp的大小初始化为 9×9，根据不同图像调整它的尺寸,计算目标块Ψp的优先权P(p)，∀p∈∂Ωn；

②选出具有最大优先权的块，作为待匹配块；

③在I-Ω区域内，使用局部窗口搜索目标块Ψp的最近似的匹配块Ψq。

④将Ψq的信息复制到Ψp需要修复的相应位置；

⑤更新置信度 C(p)=C(p′)e-kd2,∀p∈(Ψp∩Ω);

⑥重复①～⑤的过程，直到边界为空。

2 算法的实现细节

2.1 模板大小的自适应选择

在反复的实验过程中发现，用固定大小的模板窗口Ψ，修复误差比较大。对于包含丰富的细节及边缘的区域，应该采用小的模板窗口，以获取较多的细节信息，减少畸变；对于平滑的纹理区域，由于样本块和目标块的相似距离非零，修复采用直接复制样本，应该采用较大的窗口，减少修复后的图像产生明显的假象。因此模板窗口的大小应当根据图像的局部特征自适应地变化。本文采用梯度函数自适应地改变模板窗口大小。模板尺寸size(p)的定义为：

2.2 块的优先权

基于样例的图像修复算法，为了兼顾结构和纹理部分的修复效果，填充顺序是这类方法的关键。填充顺序的优先权函数大小要考虑两方面的因素:一方面是模板窗口中已知信息量的多少,另一方面要考虑待修复区域周围的结构特征。因为已知信息多的待填充块的周围可以利用的信息大，结构特征明显的区域包含了丰富的结构信息。Criminisi定义的优先权函数为：P(p)=C(p)×D(p)。当等照度线与单位法向量垂直时，D(p)=0，这时即使C(p)很大，甚至整个块中只有几个未知像素，块也得不到及时填充。这样优先权的计算就变得不可靠，导致错误的填充顺序，进而影响修复的效果。为了解决这个问题，本文直接引入梯度信息来计算块的优先权。P为修复边界∂Ω上的点，Ψp是以点 P为中心的块，点 P的优先权函数P(p)定义为:

式中,C(p)为置信度项，G(p)为梯度数据项，分别定义为:

2.3 匹配块的搜索空间

Criminisi等人采用在整幅未破损的图像中全局搜索，这样能够找到与目标区域块最相似的匹配块。但是许多图像的匹配块就在目标区域的附近，因此全局搜索提供了巨大的搜索空间，降低了算法的效率。为了减少搜索过程的时间消耗，一些学者提出了纹理主方向的搜索方法[6]（水平、垂直等）。这种纹理主方向的搜索方法对于方向性很强的图像能达到很满意的效果，但是对于其他的图像修复效果达不到满意效果。为了既要减少搜索空间，又要达到满意的修复效果，采用局部窗口空间搜索匹配块。在Criminisi的算法中，设置的填充块大小为 PatchSize，然后在整幅图像的未破损区域搜索匹配块。局部窗口尺寸设置如下:

其中，PatchSize仍然为填充块的尺寸大小，StepLength为步长，搜索空间以当前具有最大优先权的点为中心，分别向上、下、左、右延伸WindowLength这样长一段距离。因此实际搜索空间localspace为:

这一局部窗口搜索空间与全局搜索相比,窗口尺寸从 N×M(N、M 分别为图像的行和列)减少到 n×m(n、m分别为局部窗口的行和列)。这一改进减少了搜索时间，提高了图像修复的效率。但是，当有稀疏的边缘和复杂的样例的图像在修复中，简单地缩小窗口尺寸来寻找最佳匹配块会失败。

2.4 块的匹配准则

选出具有最大优先权的块作为待匹配块，然后根据颜色和梯度差异共同来计算目标块Ψp和样本块Ψq之间的相似度。相似度函数 d(Ψp,Ψq)的定义为:

式中，M是目标块上的已知像素点的数目，CL(p)为颜色差的平方的和，W(p)为梯度的差的平方的和，分别定义为:

其中，R、G、B分别代表像素的红、绿、蓝分量值，G代表图像的梯度值。通过反复实验发现，在匹配块的匹配过程中，同时考虑颜色和梯度差异的相似度的计算，获得的最佳匹配块更能够满足人们的视觉效果。

2.5 置信度的更新

完成一次填充过程后，置信度需要更新。文中置信度的更新定义为:

式中，k是一个可调参数，d是前面提到的相似度函数。显然，由这个方程可知相似度函数值越大，像素点误差越大，置信度值越低。

3 实验结果

将本文所提的算法应用于许多的自然图像,采用对比图像的视觉效果来判断修复质量的好坏，用程序的运行时间来衡量算法的效率。所有的实验是在配置为2.1 GHz处理器、2 GB内存的计算机上运行的，仿真环境为Matlab 7.0。本文用文本移除、单一目标物移除和多目标物移除，来说明本文算法的优越性。

3.1 文本移除

图2为文本移除实验。其中，(a)为原始图像，(b)为Criminisi算法，(c)为本文算法。从原始图像中可以看出，图中的文字“JAPANESE ANIMATION”只在图片的下端，其文字移走后的空白区域，修补只需要搜索不到图片一半的空间就可以找到最佳匹配块；而Criminisi采取全局搜索，大量的时间浪费在不必要的搜索中。对比发现，Criminisi所用的修复时间远远大于本文算法，而其修复效果略好于本文算法。

3.2 单一目标物的移除

图3为单一目标物的移除。其中，(a)为原始图像，(b)为Criminisi算法，(c)为本文算法。从 Criminisi算法可以看出，台阶恢复出现了明显的不相容的“垃圾块”，而且台阶下面的绿地延伸到黑色区域中；而本文算法很好地恢复了台阶的线性结构，黑色区域内也没有绿地的延伸块，几乎看不出人工痕迹。

3.3 多目标物的移除

图4为多目标物的移除实验。其中，图4(a)为原始图像，图 4(b)为 Criminisi算法，图4(c)为本文算法。从图4中可以看出，移走多棵树以后，本文算法修复的海平面非常自然，而Criminisi算法修复的海平面有轻微的人工痕迹。

表1给出了这三组实验的运行时间。从表1可以看出，运行时间与图像本身大小、破损区域大小以及破损区域周围的结构复杂度都有一定关系。本文方法与参考文献[5]所用方法相比，根据图像自身特征局部搜索运行时间更短，然而得出的效果差不多或者更好，说明了本方法的高效优质性。

表1 参考文献[5]算法与本文算法运行时间比

图像修复在图像处理和计算机图形学领域中有许多重要应用。本文提出了一种能够满足破损图片修复、文本移除、目标物体去除等多类修复要求的快速算法。本算法改进了基于样例的修复算法，为了正确地传播信息，有效地利用梯度值来计算目标块的填充顺序和匹配块的相似度。因此该算法更有能力对细小结构和复杂的纹理优先传播。

文中提出的方法不需要人为干预分割纹理和结构信息，算法根据图像的局部特征计算出优先权，接着根据优先权的大小先后填充。在匹配块的搜索空间，采用局部窗口搜索，大大缩短了修复时间。然而，该算法仍然存在着一定局限性：首先，局部窗口不能完全找到最匹配的块，如果没有局部特性的图像或者有明显跳变结构的图像修复都会失败；其次，图像的破损区域周围必须有大量的样本块，以满足待修复区域内的结构和纹理传播。所以，在今后的工作中，应该对该算法的局限性进行逐步改进，扩大它的应用范围，使其能够应用到视频和网格的修复工作当中。

[1]BERTALMIO M,SAPIRO G,CASELLES V,et al.Image inpainting[A].In:Proceedings of International Conference on Computer Graphics and Interactive Techniques[C].New Orleans,Louisiana,USA,2000:417-424.

[2]CHAN T,SHEN J.Mathematical models for local nontexture inpainting[J].SlAM Journal of Applied Mathematics,2001,62(3):1019-1043.

[3]EFROS A A,FREEMAN W T.Image quilting for texture synthesis and transfer[A].Computer Graphics Proceedings,Annual Conference Series,ACM SIGGRAPH[C].Los Angeles,2001:341-347.

[4]BCAALMIO M,VESE L,SAPIRO G,et a1.Simultaneous texture and structure image inpainting[J].IEEE Transactions on Image Processing,2003,12(8):882-889.

[5]CRIMINISI A,PEREZ P,TOYAMA K.Object removal by exemplar-based inpainting[A].in:Proceedings of IEEE Computer Society Conference on Computer Vision and Pattern Recognition[C].Monona Terrace Convention Center Madison,Wisconsin,USA,2003,2:18-20.

[6]魏琳,陈秀宏.基于纹理方向的图像修复算法[J].计算机应用,2008,9(28):2315-2317.