一种改进的基于纹理合成的图像修复算法

黄淑兵， 朱晓临， 许云云， 朱 坤

(合肥工业大学数学学院，安徽合肥 230009)

图像修复是对图像上信息缺损区域进行信息填充的过程，其目的是为了对有信息缺损的图像进行恢复，并使观察者无法察觉到图像曾经缺损或已被修复[1]。图像修复技术主要应用于破损图像的修补以及文字或物体等目标对象的移除。

文献[2]首次将偏微分方程方法应用于图像修复，其基本思想是将待修复区域边界的外部信息沿图像等照度线方向扩散到中间待修复区域，该算法对破损区域较小的结构图像修复效果较好。而对于破损区域较大的纹理图像，大多采用类似文献[3]的纹理合成的方法进行修复。该类算法的思想是从图像的已知区域中寻找与受损区域最匹配的块进行填充，从而实现图像修复。

文献[4]提出的修复方法继承了以上2类图像修复算法的优点，可以用来修复破损区域较大的图像，同时能保留图像的结构和纹理信息。此后，文献[5]中描述了该算法，并通过更多的实例说明该算法的有效性。虽然Criminisi的算法保留了图像中原有的结构信息，但对较强的结构信息持续优先处理也会带来不好的结果，由于这种方法是直接复制纹理进行填充，很容易造成偏差延续，导致整体结构出现较大偏差。

为了解决偏差延续的问题，文献[6]提出一种优先权递减的方法，在一定程度上解决了偏差延续的问题，但并未指出递减因子如何选择才能达到最佳修复效果，这使得该方法的实用性成为一个问题;此外，文中提出的递减因子并无实际的物理含义，很难在理论上进行分析。

文献[7]在Crim inisi算法的基础上，使用数据结构中队列的先来先服务(FCFS)的原则，并结合“剥洋葱”的方法，逐层按照优先队列的顺序进行修复。但是，这种方法过分考虑了边缘区域信息，把“洋葱皮”的层与层之间完全孤立开来了，这又会导致另一种问题:无明显边缘、变化较弱的区域可能会出现在本应该有较强边缘的位置，导致修复效果不够理想。

本文对Crim inisi算法造成偏差延续的原因进行了分析，在Crim inisi提出的信任项(confidence term)和数据项(data term)的基础上，又增加了一个边界项(boundary term)，充分考虑已知区域比例、结构信息和是否接近原始边界3个因素对优先权的影响。实验证明，改进的算法更为合理，修复的结果更好。

1 Criminisi算法及存在的问题

1.1 Crim inisi算法主要思想

Criminisi算法示意图如图1所示。

图1 C rim inisi算法示意图

图1中，I为待修复图像;Ω为待修复区域;其边界为∂Ω;Φ为待修复图像的已知区域。Criminisi算法的思想是在边界∂Ω上根据优先权选取一点p，选定以p点为中心的小方块 Ψp为当前需要修复的块，然后在已知区域 Φ中寻找最匹配的块Ψq，最后将 Ψq中对应点的颜色信息复制到Ψp∩Ω，并更新边界∂Ω，重复上述过程直至 Ω为空。该算法最核心的思想就是考虑了目标区域修复的顺序，提出了按优先权的顺序进行修复。

Crim inisi的算法考虑已知区域比例和结构信息对优先权的影响，并分别用信任项C(p)和数据项D(p)来表示这2个因素(p∈∂Ω)。它们分别被定义为:

其中，n p是待修复区域Ω的边界∂Ω在点p处的法向量;▽I⊥p是已知区域Φ的边界的梯度向量的垂直向量;α是标准化因子(灰度图像取α=255);对∀p∈Ω，C(p)=0;对∀p∈I-Ω，C(p)=1。最后，取

(2)式作为决定修复顺序的优先权。

确定了待修复的目标块之后，利用类似文献[3]的方法在已知区域中直接采样，并复制颜色信息到待修复区域中。假设待修复块 Ψˆp具有最高优先级，Ψˆq是待修复区域中与 Ψˆp最匹配的块(一般情况下，Ψˆq整块都应完全包含在已知区域 Φ中)，则

其中，d(Ψˆp，Ψq)是2个块中已知像素的平方误差和。找到 Ψˆq后，将 Ψˆq中相应的颜色信息拷贝至Ψˆp∩Ω的位置。重复上述过程直至修复完毕。

1.2 Criminisi算法中存在的问题

对于纯色区域，D(p)为0，若用C(p)D(p)来决定优先权，显然是不合理的。Criminisi算法首先处理优先权最大的点，填充的颜色信息是图像已知区域中与之所在的块最匹配的，循环执行一次后更新边界，这极有可能导致新边界上优先权最大的点就处于刚填充的块中，然后继续向内部延伸。如果循环中某个块被填充了不符合视觉效果的颜色信息，而下一次循环又以这次的边界为基础，就会导致不合理的颜色信息继续延伸下去，最终导致修复的视觉效果不佳。

2 改进的算法

Crim inisi算法在计算优先权时，修复之后的边界点中越靠近原始边界的，可靠性相对越高，也越应当被优先处理。接近原始边界的因素为边界项(boundary term)，记为B(p)(p∈∂Ω)。同时，为了避免过分考虑边界项[7]，本文提出了优先权公式，即

其中，λ1、λ2、λ3是非负常数，它们决定着优先权中接近原始边界、已知区域比例和结构信息3个因素的权重。C(p)、D(p)的表达式与(1)式相同。设{Ωi}是每执行一次修复之后新的待修复区域的序列，其中0≤i≤N，Ω=Ω0⊇Ω1⊇…⊇ΩN=Ø，则

其中，∂Ωi表示第i次修复后待修复区域的边界。

由于C(p)、D(p)的取值均在0～1之间，为了使B(p)与C(p)、D(p)具有相同的数量级，取ˆB(p)上的点的边界项值为0.5。

参数λ1决定着修复过程中B(p)的权重，如果λ1取值比较大(相对λ2、λ3)，则修复时会优先修复靠近边界的部分;参数λ2决定修复过程中C(p)的权重，如果λ2取值比较大(相对λ1、λ3)，则修复时会优先修复小方块中已知区域比例较大的区域;参数λ3决定着修复过程中D(p)的权重，如果λ3取值比较大(相对λ1、λ2)，则修复时会优先修复颜色变化最剧烈的区域。即λ1、λ2、λ3的取值决定修复的顺序，修复的顺序不同，结果也就可能不同。

本文的算法可以通过选取不同的参数值来修复不同特征的破损图像，这大大增加了该算法的应用范围。通常情况下，取λ1=λ2=λ3=1，3个因素取相同的权重。若取λ1=0，λ2=λ3=1，则计算优先权时不考虑边界项，只考虑信任项和数据项，并且两者具有相同的权重，此时该算法的结果恰好与Criminisi算法相当。若取λ1≫λ2，λ3＞0，则计算优先权时主要考虑边界项，类似于“洋葱皮”算法，由于边界上点的边界项值相同，比较每层信任项和数据项的大小，此时该算法的结果恰好与文献[7]的算法相当。由此可以看出，本文的算法模型较为灵活和全面，具有更好的实用性。

改进的算法过程为:初始时，手工选择待修复区域或待移除的目标，抽取待修复区域的边界∂Ω0(=∂Ω)，置ˆB(p)=∂Ω0，∀p∈∂Ω0。执行步骤(初始i=0)如下:

(1)找出待修复区域的边界∂Ωi，如果 Ωi= Ø，退出循环，修复结束。如果ˆB(p)∩Ωi=Ø，置ˆB(p)=∂Ωi，∀p∈∂Ωi。

(2)根据(1)式、(4)式、(5)式计算优先权P(p)，∀p∈∂Ωi。

(4)根据(3)式找出最匹配的块 Ψˆq∈Φ。

(5)将 Ψˆq中相应的颜色信息拷贝至 Ψˆp，∀p∈Ψˆp∩Ω。

(6)置i=i+1，重复步骤(1)～(5)。

3 实验结果与比较

本文实验用Matlab7.0作为工具，在Intel酷睿2双核处理器(2.0GH z)、2G内存的PC机上实现。

本文算法中参数λ1、λ2、λ3取不同的值时修复顺序的比较如图2所示。3幅图中第1个均为待修复图像，最后1个为修复后的图像。

图2 参数取值对修复顺序的影响

从图2a中可以看出，优先修复靠近边界的部分，该取法与“洋葱皮”算法的修复效果相当，出现了不理想的修复结果。从图2b可以看出，此时优先修复的是小方块中已知区域比例较大的部分。从图2c可以看出，此时优先修复的是颜色变化最剧烈的部分。因此参数值的选取决定着修复的顺序，可以根据待修复图像的特征来选取合适的参数值。

本文算法与Criminisi算法修复结果的比较如图3所示。图3c因为优先权的选取不合理，出现偏差延续的情况。从图3d可以看出，本文的算法(取λ1=λ2=λ3=1)很好地解决了这个问题。其中，修复块的大小均取7×7。

本文算法与文献[7]中的算法修复结果的比较如图4所示。图4c因为文献[7]中的算法过分强调了边界区域的重要性，导致边界附近河流的颜色信息蔓延至本应是陆地的区域。从图4d可以看出本文算法(取λ1=0.1，λ2=λ3=10)模型的灵活性，通过调节3个因素的权重，修复结果非常好。其中，修复块的大小均取5×5。

本文算法与经典的TV模型[8]修复结果的比较如图5所示。图5c左侧竖条修复的结果出现了模糊。从图5d可以看出，本文算法(取λ1= λ2=λ3=1)也可以适用于结构图像，而且修复效果比经典的TV模型还要好。其中，修复块的大小均取5×5。

图3 本文算法与Criminisi算法修复结果的比较

图4 本文算法与文献[7]中的算法修复结果的比较

图5 本文算法与经典的TV模型算法修复结果的比较

4 结束语

本文通过分析Criminisi算法修复某些图像效果不好的原因，提出了一种改进的算法。结果表明，本文改进的算法可以有效修复破损区域较小和较大的图像，同时提出的优先权计算模型比较灵活，适用范围更广。如果已知区域中不存在与待修复区域中相近似的块，修复的效果不是很理想。本文只注重了修复的效果，并没有考虑减少修复所需的时间[9]。

[1] 张红英，彭启琮.数字图像修复技术综述[J].中国图象图形学报，2007，12(1):1-10.

[2] Bertalm io M，Sapiro G，Caselles V，et al.Image inpain ting [C]//Proceedings of SIGGRAPH'2000.ACM Press，2000:411-424.

[3] Efros A，Leung T.Texture synthesis by non-parametric sam pling[C]//Proc In t Con f Com puter Vision，Kerkyra Greece，Sep tember，1999:1033-1038.

[4] Crim inisi A，Perez P，Toyam a K.Ob ject removal by exemplar-based inpainting[C]//Proc Conf Comp V ision Pattern Rec，Madison W I，2003:721-728.

[5] C rim inisi A，Perez P，Toyama K.Region filling and object removal by exemplar-based image inpain ting[J].IEEE Transactions on Image Processing，2004，13(9): 1200-1212.

[6] 朱 为，李国辉，李 丹.纹理合成技术在旧照片修补中的应用[J].计算机工程与应用，2007，43(28):220-222.

[7] 李景辉，张晓峰，马 燕.纹理合成在图像修复中的应用研究[J].计算机工程，2009，35(7):206-208.

[8] Chan T F，Shen J.M athematicalmodels for localnon texture inpain tings[J].SIAM Jou rnal on Applied Mathem atics，2001，62(3):1019-1043.

[9] 薛 峰，张佑生，江巨浪，等.一种快速、有效的纹理合成方法[J].合肥工业大学学报:自然科学版，2005，28(11): 1361-1364.