谢伙生，潘姣君

(福州大学数学与计算机科学学院，福建福州 350116)

0 引言

图像修复主要是利用图像中已知区域的信息对信息缺损区域进行填充的一个过程，其目的在于恢复图像中信息缺损的区域，以便使观察者察觉不出图像曾经缺损或已被修复［1］.目前对图像中具有大面积信息缺损的区域进行修复的主要方法为纹理合成算法，该方法主要是根据图像中已知区域的纹理特性，来复制已知区域中纹理较为相似的图像块到缺损区域.图像修复技术在古文物的保护、影视特技的制作、旧照片的修补、图像中文字及障碍物的去除等领域具有广泛的应用.

在基于纹理合成的数字图像修复算法中，主要有两个难点需要解决:一是纹理块的填充次序问题，虽然在算法中图像的纹理特性可以较好地被保留下来，但是仅仅依靠纹理合成而忽略纹理块的填充次序常常会使得待修复区域的边缘特征不够清晰，从而影响修复后图像的视觉效果，因此合理安排纹理块的合成次序显得尤为重要.二是最佳匹配块的搜索问题，一般采用的匹配准则是纹理合成中常用的SSD(sum of squared differences).目前基于块的纹理合成修复技术中代表性的成果就是Criminisi等人提出的算法［2－3］，其中文献［2］提出的修复算法可用来修复具有较大面积区域信息缺损的图像，其修复后图像的结构信息和纹理信息都得到较好的保留.文献［3］也同样描述了此算法，主要是用较多的例子进一步说明此算法的可行性及有效性.Criminisi算法在修复大面积区域信息缺损的图像时虽然可以取得较为满意的修复效果，但时间复杂度高，同时优先权的计算还存在一定的不足，容易造成偏差的延续，使修复结果不够理想.

针对Criminisi算法中存在时间复杂度高的不足，文献［4］提出一种基于图像特征值的纹理修复算法，该方法通过在匹配过程中先利用图像平均灰度值进行快速比较，减少了大量的匹配时间，从而大幅度提高Criminisi算法的修复效率，保证了实时性.但该算法旨在保证修复效果同Criminisi算法相当的前提下提高修复效率.

为了解决Criminisi算法修复中偏差延续的问题，文献［5］提出一种优先权递减法，该方法使修复顺序能够按照待修复边界上所有的强边缘点逐个进行，保持了图像的边缘结构.但是其使用的递减因子为0～1之间的值，并未指出具体取多大的值才能使修复效果达到最佳.文献［6］在算法运行中按照队列的先来先服务(FCFS)原则逐层对待修复区域进行修复.然而该算法没有较好地解决待修复边界存在非线性的问题，从而使修复效果不够理想.文献［7］在Criminisi算法优先权计算的基础上，除了考虑置信度项和数据项外，还增加一个边界项，使优先权值的计算更为合理，从而使修复结果更好.然而该方法侧重于修复效果的提高，其修复所需的时间较长.

本文针对Criminisi算法存在的上述两个问题，基于文献［4］及文献［7］的思想，提出一种在时间和视觉效果上进行权衡优化的方法.实验证明，该优化方法合理有效.

1 Criminisi算法分析

Criminisi算法的核心思想是在填充待修复区域时先计算边界上所有待修复块的优先权，寻找优先权最高的块作为当前待修复块，然后在已知区域中搜索与之最为匹配的纹理块并将其复制到缺损区域，最后更新置信度及待修复边界，这样就完成一次的修复过程，如此循环，直至缺损区域已被完全修复为止.

如图1所示，对于待修复图像I，首先手工选定待修复区域Ω，图像的已知区域用Φ表示(Φ=I－Ω)，δΩ为缺损区域的边界，是以点p为中心的待修复块.

p点优先权的计算:

式中:

图1 符号图Fig.1 Symbol diagram

搜索到最佳匹配块后，复制其对应位置处的颜色信息到待修复块中相应的位置，然后根据式(7)更新置信度C(p)，并抽取新的待修复边界.

通过对Criminisi算法的分析，其仍存在一定的不足.①算法在匹配过程中，每次搜索最佳匹配块时都要遍历图像已知区域中的所有纹理块，计算每一纹理块与待修复块的SSD，而SSD的计算较复杂，这样就要消耗大量的匹配时间，增加修复的时间开销.②对纯色区域来说D(p)=0，如果仍用C(p)D(p)来计算优先权，显然不可靠.算法先填充具有最高优先权的点，并用缺损图像已知区域中与其最为匹配的块中对应的颜色信息来填充，执行一次后更新待修复边界，如此循环.如果循环中优先权最高的点出现在刚刚填充的块的边界上，并且刚填充的块中被填充了不符合视觉效果的颜色信息，这将会导致不合理的颜色信息向缺损区域内部继续填充，从而使修复效果不理想.

2 优化方法

首先在进行SSD准确匹配之前事先计算待修复图像已知区域中所有纹理块的平均灰度值，然后在匹配过程中结合平均灰度值阈值Tagv对已知区域中纹理块及当前待修复块的平均灰度值进行比较，筛选淘汰灰度差异较大的一些纹理块，这样在进行准确匹配时就只需与较少的候选块匹配，从而节省大量复杂的SSD计算，减少匹配时间，提高修复效率.其次在对待修复边界点优先权的计算时，定义一种新的优先权计算公式，增加是否接近原始边界因素对优先权的影响，使优先权的计算更为合理，修复的结果更理想.

在SSD准确匹配之前选平均灰度值作比较:其一，可预计算，且计算简单.通过平均灰度值的比较后，减少大量SSD的复杂计算，使单次搜索只需计算较少次的SSD，节省匹配时间，提高了修复效率.其二，阈值可控性好.只要对平均灰度值阈值进行合理的控制，就可以在不明显降低修复效果的同时提高修复效率.实际上，若平均灰度值阈值取足够大(灰度图像最大为255)，此时修复效果与文献［7］算法相当.

在Criminisi算法基础上对优先权的计算进行改进，不仅考虑了置信度项和数据项，而且增加了是否接近原始边界因素对优先权的影响.这是由于新的待修复边界点中离原始边界越近的，相对越可靠，也就越应当优先修复这些点所在的块.这里，是否接近原始边界的因素用二值项来表示，记为B(p)(p∈δΩ).

为了权衡置信度项、数据项和二值项对优先权的影响，定义新的优先权计算公式［7］:

式中:参数a、b、c为非负常数，分别为是否接近原始边界、待修复块中已知区域比例和结构信息对优先权的影响权重.若参数a的取值远大于b、c，则接近原始边界的区域将被优先修复;若参数b的取值远大于a、c，则待修复块中已知区域比例较大的区域将被优先修复;若参数c的取值远大于a、b，则待修复块中具有明显边缘的区域将被优先修复.a、b、c的取值情况决定着修复次序，并最终影响修复结果.因此，在值的选择上，对不同特征的图像，需通过调试a、b、c值来使修复的效果达到最好.一般情况下，a、b、c的值均取为1，使3个影响因素具有一样的权重.如果取a为0，b、c均为1，此时得到的结果类似于Criminisi算法.因为这时优先权值的计算也只考虑了置信度项和数据项，且两者对优先权的影响权重相同.

对于是否接近原始边界的因素B(p)的取值情况，考虑到C(p)、D(p)的取值范围均为0～1，这里B(p)(∀p∈δΩi)的取值按照式(9)、式(10)进行设置，以使B(p)也具有同样的数量级.

其中:δΩi表示对缺损图像修复i(i≥0)次后待修复区域的边界.

综上所述，该方法的具体实现过程为(初始时i=0):

首先用绿色标出图像中待修复区域，设置平均灰度值阈值Tagv及参数a、b、c的值.

1)抽取用户选定的待修复区域Ω(等于Ω0)的边界δΩ(等于δΩ0)，设置B(p)值;预先计算图像已知区域中所有纹理块的平均灰度值.

2)如果Ωi=φ，退出，算法终止.

5)将当前待修复块及已知区域中纹理块的平均灰度值进行比较，筛选淘汰灰度差异较大的一些纹理块;再根据式(5)、式(6)在候选块中搜索最佳匹配块.

7)更新置信度;置i=i+1，抽取新的待修复边界，并根据式(9)、式(10)更新B(p)值，转步骤2).

3 实验结果分析

仿真实验在环境为Microsoft Visual C++6.0，配置为Windows XP－2002版本、CPU 1.73GHz、内存1GB的计算机上完成.实验选取了几幅具有典型性的缺损图像进行修复，纹理块大小均为9×9，已知区域均设定为缺损图像中完好的部分.算法是在保证图像修复效果不比Criminisi算法差的同时尽量提高修复效率的基础上，对参数(Tagv、a、b、c)进行设置.

3.1 时间对比

表1给出本文算法与Criminisi算法修复缺损图像的运行时间比较.从表1可以看出:本文算法在较大程度上减少了运行时间，提高修复图像的效率.从表1中最后两行的实验数据看，在平均灰度值阈值设置比较大时，本算法仍然可以取得较大程度上的效率提高.

表1 运行时间比较Tab.1 Comparison of the runtime

图2 实验结果1Fig.2 Experiment result 1

3.2 效果比较

效果比较见图2～图6.由图2～图6的比较结果知，本文算法得到的修复效果不比Criminisi算法差.这主要是由于本文算法定义了一种新的优先权计算公式，增加了是否接近原始边界因素对优先权的影响，即新的待修复边界点中离原始边界越近的相对越可靠，也越应当优先修复这些点所在的块.该优先权的计算更为合理，修复的结果更理想.特别地，从图4～图6中可以明显看出本文算法的修复效果更好，更符合人的视觉感知.其中，在图4中对屋檐及树木与水面相接的部分修复得更合理;图5中对三角形内部修复得很好，没有出现白色区域;图6中对线结构修复得更好，没有出现断裂的现象.实验结果证明了本文算法的可行性及有效性，它较好地解决了偏差延续的问题.

图3 实验结果2Fig.3 Experiment result 2

图4 实验结果3Fig.4 Experiment result 3

图5 实验结果4Fig.5 Experiment result 4

图6 实验结果5Fig.6 Experiment result 5

4 结语

分析了Criminisi算法修复图像时存在的几个问题，提出一种在时间及视觉效果上都有所优化的方法.该方法思路简单，容易编程实现.实验结果表明，该方法不仅提高了修复效率，而且在一定程度上优化了修复效果.虽然本算法可通过人为设置一些参数，使修复的图像范围更大，具有更好的实用性，但文中参数的设置没有一个特定的标准，不能根据不同特征的图像进行自动设置，而且如果参数选取不当将会导致修复结果不理想.这是本算法存在的缺陷，还需要进一步的改进.

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

［2］Criminisi A，Perez P，Toyama K.Object removal by exemplar－based inpainting［C］//IEEE Computer Society Conference on Computer Vision and Pattern Recognition.Wisconsin:Monona Terrace Convention Center Madison，2003，2:18－20.

［3］Criminisi A，Perez P，Toyama K.Region filling and object removal by exemplar－ based image inpainting［J］.IEEE Transactions on Image Processing，2004，13(9):1 200－1 212.

［4］彭坤杨，董兰芳.一种基于图像平均灰度值的快速图像修复算法［J］.中国图象图形学报，2010，15(1):50－55.

［5］朱为，李围辉，李丹.纹理合成技术在旧照片修补中的应用［J］.计算机工程与应用，2007，43(28):220－222.

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

［7］黄淑兵，朱晓临，许云云，等.一种改进的基于纹理合成的图像修复算法［J］.合肥工业大学学报:自然科学版，2011，34(2):313－316.