改进的基于样本块的图像修复方法

常 晨，何建农

（福州大学 数学与计算机科学学院，福建 福州 350116）

改进的基于样本块的图像修复方法

常 晨，何建农

（福州大学 数学与计算机科学学院，福建 福州 350116）

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

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

0 引言

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

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

1 Criminisi算法简介

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

图1 基于样本块算法的过程图

算法的具体步骤如下：

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

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

式中 q∈Φ时，c（q）=1，否则 c（q）=0。|ψp|是 ψp像素的数量，▽Ip⊥是点 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，保证其不会迅速降为零，▽u是拉普拉斯梯度，uηη与 uξξ分别表示沿着梯度方向和垂直于梯度方向的二阶方向导数，填充顺序要考虑这两个方向的图像特征变化，像素变化越小的块，具有更大的优先权，保证图像能够沿着边缘处平滑扩散，避免在平滑区域产生阶梯效应，在边缘处出现信息延伸的现象。

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.4GHz处理器，2 GB内存。用文献［4］和本文改进的算法对四幅受损图像进行修复实验，如图2～图5所示，其中图2和图3是对受损的区域进行填充，本文用峰值信噪比（Peak Signal to Noise Ratio，PSNR）和修复所需的时间对图像进行评价，见表1和表2。图4和图5是对目标物的移除，在实际情况中，很难找到原始图进行 PSNR对比，这里主要借用人眼的观测和消耗的时间进行评价。

图2 实验图1

图3 实验图2

图4 实验图3

图5 实验图4

表1 两种算法的PSNR值 （dB）

从表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］BERTALMIOm，SAPIRO G，CASELLES V，et al.Image inpainting［C］.Proceedings of the 27th Annual Conference on ComputerGraphicsand Interactive Techniques.New York：ACM Press，2000：417-424.

［2］CHAN T F，SHEN J.Mathematical models for local nontextureinpaintings［J］.SIAM Journalon 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.

Improvement of image inpainting method based on sample patch

Chang Chen，He Jiannong
（College of Mathematics and Computer Science，Fuzhou University，Fuzhou 350116，China）

Based on the research of Criminisi repair algorithm，an improved image inpainting method based on sample block is proposed.According to the area of image restoration and texture feature，adaptively select sample block size to improve the speed of repair.New data items are used to improve the priority formula.Using new data items and the improved priority formula to avoid the step effect.The new formula of the reliability is introduced.The curvature distance is introduced to reduce the accumulated error and improve the accuracy of the sequence.Experiments show that the improved method can effectively improve the repair effect，reduce the time needed for repair.

image restoration；sample patch；priority；update of confidence term

TP391

A

1674-7720（2015）23-0045-03

常晨，何建农.改进的基于样本块的图像修复方法［J］.微型机与应用，2015，34（23）：45-47.

2015-09-13）

常晨（1991-），女，硕士研究生，主要研究方向：图像处理。

何建农（1960-），女，副教授，硕士生导师，主要研究方向：智能图像处理、信息安全、网络 GIS。