摘  要： 在研究Criminisi修复算法的基础上，提出了改进的基于样本块的图像修复方法。根据图像的待修复面积及其纹理特征，自适应选取样本块大小，提高修复的速度；采用新的数据项，改进优先权公式，避免阶梯效应的产生；重新定义置信度的更新公式，引入曲率距离，减少因置信度更新而累计的误差，提高修复顺序的准确性。实验表明，改进的方法能够有效提高修复的效果，减少修复所需时间。

　　关键词： 图像修复；样本块；优先权；置信度的更新

0 引言

　　图像修复的本质是通过不完整信息重新构造出完整信息，对图像上信息缺损区域进行填充，恢复受损的图像，让观察者无法用肉眼看出图像曾损坏过。对图像修复技术的深入研究也是当前计算机视觉领域中的一个热点。

　　图像修复技术可分为两大类：基于偏微分的修复方法[1-3]和基于纹理的修复方法[4-7]。前者是通过建立偏微分方程，将图像中完好的信息向受损区域内部扩散，进行图像修复，这类方法能够保留图像的线性结构，对小尺度破损的图像的修复效果较好，但对修复破损区域较大的图像时，计算量大，耗时长，易产生模糊效应。后者是利用图像纹理的重复性以及规则性进行纹理合成，填补丢失的信息，修复受损区域。2003年，Criminisi等人[4]提出了一种基于样本块的图像修复算法，利用待修复块在信息完整区域匹配选择纹理块，结合扩散修复方法的优点，按照一定的先后顺序进行填充，保证了图像纹理修复的自然顺畅，其简单有效的特点使其成为纹理修复的经典算法。但是利用该算法进行修复的图像会产生冗余，出现结构不连续现象，影响最终的修复效果。本文以Criminisi算法为基础，对其不足之处进行改进，自适应选择最佳样本块大小，改进优先权公式和置信度更新方式，使纹理和结构信息得到有效利用。通过实验结果对比分析，证明改进的方法不仅能得到较好的修复结果，且能够大幅度提高修复的速度。

1 Criminisi算法简介

　　Criminisi算法的核心是找到具有最高优先权值的待修复点p，设置以p为中心的9×9像素的待修复块，在未受损的图像区域中寻找最佳样本块，将该样本块的信息复制到待修复块中，待修复区域发生变化，最后更新边界和置信度的值，其过程如图1所示。图中的是未受损的区域，是待修复区域，是待修复区域的边界，p是上的一点，p是待修复块，q为最佳样本块。

　　算法的具体步骤如下：

　　（1）根据图像的特征结构，求出优先权值最高的点，确定填充的顺序。优先权P（p）的计算公式为：

　　P（p）=C（p）D（p）（1）

　　其中，C（p）是待修复点p的置信度，用来衡量?鬃p包含的可用信息量。D（p）是数据项，反映?鬃p的结构特征。表达如下：

　　式中q∈时，c（q）=1，否则c（q）=0。|p|是p像素的数量，是点p的等照度线方向，np是在点p处的单位法向量，是归一化因子，一般取值为255。

　　（2）在已知区域?椎中寻找与?鬃p最相近的样本块q，要求q满足：

　　式中的d（p，q′）是p和q′对应的已知像素点的颜色差的平方和。之后将最佳样本块q中对应的像素复制到待修复块p中的未知像素点。

　　（3）p被修复后，待修复区域的范围和边界都发生变化，待修复区域点的置信度也有了改变，因此需要更新p内所有点的置信度：

　　重复上述3个步骤直至完成修复。

2 改进的算法

　　2.1 模板块大小的自适应选择

　　原始算法中，Criminisi经过多次试验分析和比较，最终选择修复模板块的大小固定为9×9。由文献[7]知对不同的图像，采用不同的样本块大小进行处理，会得到不同的修复效果，但过小的模板块影响修复的速度，在不影响修复效果的情况下选取较大的模板块，能够提高修复的效率。为选取最优样本块，本文利用图像纹理特征[8]及破损面积自适应选择样本块的大小r，通过大量实验数据的拟合，得到式（6）中样本块大小选择和它们之间的关系：

　　其中，S是图像受损面积占整幅图像的百分比，待修复区域越大，用较大的样本块去修复，运行的速度和修复的质量都有所提高。T建立图像几种纹理特征与r选取的关系，其中I是图像的粗糙度，G是图像的熵均值，L是图像的能量惯性矩。

　　2.2 优先权的改进

　　计算优先权，确定填充顺序，使得修补过程有序进行，但原始算法采用C（p）和D（p）直接相乘的形式，当C（p）急剧下降直趋近为零时，无论D（p）值多大，都可能会导致优先权函数值接近为零，图像中的结构信息无法作为填充顺序的参考，使得图像填充顺序变得不准确，影响图像修复的效果。数据项D（p）采用受损边缘梯度向量垂直的等照度线向量和法线向量相乘的形式，不能有效提取图像结构信息，本文引入基于偏微分模型中的平滑扩散因子D1和D2[5]，将其作为数据项，定义新的优先权公式如下：

　　其中置信度添加0.5，保证其不会迅速降为零，是拉普拉斯梯度，分别表示沿着梯度方向和垂直于梯度方向的二阶方向导数，填充顺序要考虑这两个方向的图像特征变化，像素变化越小的块，具有更大的优先权，保证图像能够沿着边缘处平滑扩散，避免在平滑区域产生阶梯效应，在边缘处出现信息延伸的现象。

　　2.3 置信度更新改进

　　置信度项的更新是Criminisi算法中重要的一步，因为待修复块p被填充后，未知像素点变为已知点，置信度值发生变化，修复块p和样本块q不是完全相等的，它们有一定的结构误差，这个误差会随着修复过程不断的叠加而增多，填充顺序的可信度逐渐降低，最终影响图像的修复结果。提出的改进的置信度项更新公式如下：

　　式中Ipi，Iqi分别表示待修复块p和样本块q的对应已知点的等照度线的曲率，n表示样本块中p已知像素点的个数，这样可以使得差异度小的块有较大的置信度值，减小误差的累积，避免冗余现象的产生。

　　2.4 本文算法步骤

　　（1）输入待修复的彩色图像，手动选择需要修复的区域；

　　（2）按公式（6）选择最优样本块的大小；

　　（3）利用公式（8）计算待修复区域的边界上各点的优先权P（p），确定待修复区域内的填充顺序；

　　（4）在匹配区域中搜索最佳匹配块q；

　　（5）将q中对应的图像信息复制到待修复块p中；

　　（6）利用公式（10）更新置信度项C（p）；

　　（7）重复步骤（2）~（6），直到整个待修复区域被填充完。

3 实验结果和分析

　　本文算法是以MATLAB7.1为仿真平台实现的，硬件环境是Intel（R）Core（TM）i5-2430M 2.4 GHz处理器，2 GB内存。用文献[4]和本文改进的算法对四幅受损图像进行修复实验，如图2~图5所示，其中图2和图3是对受损的区域进行填充，本文用峰值信噪比（Peak Signal to Noise Ratio，PSNR）和修复所需的时间对图像进行评价，见表1和表2。图4和图5是对目标物的移除，在实际情况中，很难找到原始图进行PSNR对比，这里主要借用人眼的观测和消耗的时间进行评价。

　　从表1和表2可以看出，实验图1和实验图2改进算法的PSNR值比文献[4]要高，而四个实验的修复速度基本上提高了30%~50%。从视觉上比较可以看出：图2（c）出现块匹配错误，使得图像有明显修复痕迹，图2（d）减弱了修复的错误匹配，避免了修复区域不均的现象。图3（c）中图像明显没有很好地进行填充修复，图3（c）从视觉上看基本与原图无差。图4（c）对人物的填充，在修复的边缘处，有明显的纹理延伸，房顶没有得到较好修复，陆地上的草延伸至水中，图4（d）修复的结果在边缘处能够平滑过渡，获得较好修复效果。图5（c）明显没有修复完全，有残余的飞机尾翼未被填充，而图5（d）的结果更为自然。

4 结论

　　本文在文献[4]的基础上进行改进。根据图像破损的面积及其纹理特征，自适应选择最优的样本块大小。引入平滑扩散因子，改进优先权计算公式，增强图像结构特征的影响，避免因置信度的急剧衰减而导致的错误修复顺序。提出新的置信度更新方式，减少在修复过程中，因待修复块和样本块之间的结构差异而累计的误差。实验结果表明，本文改进的算法在提高修复速度的同时，能够获得更好的修复效果。

　　参考文献

　　[1] BERTALMIO M， SAPIRO G， CASELLES V， et al. Image inpainting[C]. Proceedings of the 27th Annual Conference on Computer Graphics and Interactive Techniques. New York： ACM Press，2000：417-424.

　　[2] CHAN T F，SHEN J. Mathematical models for local  non-texture inpaintings[J]. SIAM Journal on Applied Math， 2001，62（3）：1019-1043.

　　[3] DRORI I， DANIEL C-O， YESHURUN H. Fragment based image completion[J]. ACM Transactions on Graphics， 2003，22（3）： 303-312.

　　[4] 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）：1200-1212.

　　[5] 王远敏，朱晓明，孙雁飞，等.基于模板的图像修复算法优先权的改进[J].信息技术，2008（5）：64-67.

　　[6] 张伟伟，何凯，孟春芝.自适应选取样本块大小的纹理合成方法[J].计算机工程与应用，2012：48（17）：170-173.

　　[7] 潘姣君，谢伙生.结合灰度共生矩阵和熵的图像修复算法[J].微型机与应用，2012，31（21）：44-46.

　　[8] 贺双双，戴青云.综合纹理和形状特征的外观专利图像检索算法研究[J].微型机与应用，2013，32（4）：42-44，47.