一种改进的基于块的图像修复算法

赵子岩 ， 齐 敏 ， 齐 榕 ， 李 珂

（1.西北工业大学 电子信息学院，陕西 西安 710129；2.西北工业大学 自动化学院，陕西 西安 710129）

图像修复是根据图像已知区域的像素信息来推断缺失的未知区域信息，并且要求最终图像的已知区域与修补区域过渡自然，从而达到人眼看不出修补的痕迹。图像修复应用相当广泛，包括珍贵的历史文物、旧照片、目标移除、图像压缩与编码等。

目前图像修复的算法主要分为两大类：基于像素点的图像修复算法与基于块的图像修复算法。前者主要是针对小范围破损区域的图像进行修复，这类方法包括基于偏微分方程的图像修复的三种模型，即 BSCB模型[1]、整体变分（TV）模型[2]和基于曲率驱动扩散的修复模型 （CDD）模型[3]以及基于插值及邻域模板的方法。基于偏微分方程修复的方法主要是利用物理学上的热扩散原理，通过建立图像的偏微分方程，然后解偏微分方程，从而实现对图像的修复，而基于插值与邻域模板的方法是套用某种类型，而不用循环迭代，得到待修复点的值。比如邻域点的值套用范本或者直接带入插值公式，然后通过计算得到待修复区域的像素值。后者主要是针对大范围破损区域的图像进行修复，这类方法包括基于样本块的纹理合成图像修复方法、变换域（傅里叶变换或小波变换）图像修复方法以及基于分形理论以及基于稀疏性的图像修复方法等。在这类方法中，以图像块为基本操作单位[4]，根据未知区域边界处的信息，通过从图像的已知区域中搜索相似匹配块，并通过相关计算找到最佳匹配块，最后将最佳匹配块复制到未知区域块中，从而逐步填充缺损区域，完成图像修复。Criminisi等人在2003年提出了基于样本块的图像修复算法，该算法利用局部边界等照度线方向和单位法线方向定义块的填充次序，得到优先填充的样本块后，在图像已知区域寻找最佳匹配块，并通过待修复匹配块填充待修复样本块。此方法的优点是同时兼顾了图像的纹理信息以及结构信息，是至今研究大范围破损区域图像修复的主流，然而Criminisi算法也存在一些缺陷:

1）算法中优先项的计算采用了置信项与数据项乘积的形式。这样，当数据项为零时，即使置信项很高，由于优先项为零也不能得到优先修复。但是在纹理丰富的区域，数据项是不为零的，这就造成了纹理丰富的区域修复先于纹理信息较少的区域，出现纹理丰富区域修复过渡的现象。

2）算法中采用固定的样本块窗口大小，这样有可能会导致在图像的平坦区域产生块状效应，在图像纹理丰富的区域产生错误衍生的现象。另外算法中只是利用先前计算出来的源图像块的置信度来更新填充未知像素的置信度，未考虑到样本块与匹配块之间存在误差，从而造成修复过程中的误差累积，导致Criminisi算法的贪婪性。

本文针对以上Criminisi算法的缺陷进行改进，实验结果表明，本文改进算法取得了较好的效果。

1 算法的描述

1.1 Criminisi算法的原理

如图1所示，整幅图像为I，待修复区域为Ω，源区域为Φ，∂Ω为待修复区域的边界。该算法的图像修复过程分为如下3个步骤：

图1 算法标记图Fig.1 Signature of criminisi algorithm

1）计算优先级

定义待修复边界处任意像素点p优先级函数P（p）为：

式中C（p）为置信度项，用来度量以像素点p为中心的目标块 ψp内已知信息的数目；D（p）为数据项。 C（p）和 D（p）表达式如下：

式中|ψp|表示ψp的面积，α是归一化的系数（对于8位的灰度图像，一般取值为 255），Δ的大小与梯度相等，方向垂直于梯度，即等照度线方向，为待修复区域边界∂Ω的单位法向量。初始化时图像中的各像素点的置信度值为：

其中d（ψp^，ψq）定义为两个块中已知像素的差的平方和，搜索整幅图像的已知信息后，找到最小的d（ψp^，ψq）即为最佳的匹配块ψq^。其计算公式为

3）置信度 C（p）的更新

重复（1）、（2）、（3）直至修复边缘为零。

1.2 优先权函数的改进

本文运用的优先权计算公式为：

式中：α+ β=1，当 D（p）=0 且 C（p）<0 时，α=0，β=0；当D（p）≠0 且 C（p）≠0 时，α=0.4，β=0.6；当 D（p）=0 且 C（p）>0.8 时，α=1，β=0。通过这就能保证当 D（p）为零时，只要 C（p）高，也能够优先修复；当 D（p）为零和 C（p）很低时，令 P（p）为零，表示该像素块后修复；当 D（p）和 C（p）都不为零时，令β>α，使数据项占主导因素。实验表明，这种方法能够避免纹理丰富区域修复过渡扩展的现象以及解决Criminisi算法中修复方向严格按照线性结构方向进行出现断层的问题。

1.3 根据梯度自适应选择样本模板以及置信度更新

由于Criminisi算法中采用固定的样本块，可能会导致在图像的平坦区域产生块状效应，在图像纹理丰富的区域产生错误衍生的现象。因此，图像修复过程应该根据图像的局部特征自适应的选择样本块模板大小。根据图像梯度的变化能够反映图像频率的变化，本文采用根据梯度值自适应选择样本块大小，在纹理丰富的区域采用较小的样本块；在平坦或者平滑区域采用较大的样本块。另外当待修复块被匹配块填充之后，需要对生成块的置信度进行更新，在Criminisi算法中直接利用源图像块的置信度来更新填充未知点的置信度，但是未考虑到待修复块与匹配块之间存在一定的误差，这样进行会使误差不断地累积。对这些问题，本文采用的自适应样本块大小以及置信度更新方法分别如下：

自适应样本块大小的方法是利用Criminisi算法中选择的9x9的样本块中已知点的平均梯度值的大小来选择不同尺寸的模板窗口。公式表达如下：

式中，|ΔIP|为样本块9x9中已知点的平均梯度模值，size（p）为最终的待修复样本块模板半径的大小。

本文采取置信度的方法为：Ipi令为待修复块ψq中已知点的梯度值，Iqi为最佳匹配块ψq^对应的已知点的梯度值，M为待修复样本块中已知点的个数，令复块与对应的最佳匹配块之间的平均梯度差值，th值越小，说明两块之间的纹理相差越小，复制过来点的置信度就越大。改进的置信度更新方式如下：

1.4 改进算法的步骤

结合改进的优先权方法、自适应选择模板的方法以及改进的置信度更新方式，得到改进后的算法步骤如下：

1）选择一幅图像，由用户利用一种特定的颜色标注出目标区域，然后找出目标区域边缘∂Ω，当∂Ω=φ时，算法结束，输出修复图像。

2）根据式（2）计算出数据项与置信度项的值，然后按照式（7）求出优先权项，对优先项从高到低进行排序，确定最高优先权的边界点作为修复的目标，然后以该点为中心计算其9x9领域中已知点的平均梯度值，根据不同的梯度值按照式（8）选择样本块的大小；

3）确定样本块大小之后根据式（4）在图像的已知区域选择最佳匹配块ψq^；

4）将最佳匹配块ψq^的图像信息复制到待修复样本块ψp^中；

5）根据式（9）更新置信度项；

6）重复（2）到（6），直到全部的目标区域被修复。

2 实验结果与分析

实验环境是在奔腾core 1.86 GHz，1GB内存的PC机上，利用Matlab7.1软件平台实现了Criminisi算法与本文算法对两幅彩色图像分别从R、G、B三种通道进行修复。

图 2（a）是原图，大小是 262x350 的彩色图像，图 2（b）是待修复图，车以及人物部分是标注的待修补区域，图2（c）是Criminisi算法修复图，所用时间为165.57 s，图2（d）是本文算法修复图，所用时间为208.42s。图3（a）是原图，大小是308x206的彩色图像，图3（b）是待修复图，人物部分是标注的待修补区域，图 3（c）是 Criminisi算法修复图，所用时间为 103.20 s，图 3（d）是本文算法修复图，所用时间为123.65 s。通过两组实验对比，本文算法从视觉效果就可以看出明显优于Criminisi算法，尤其是在明显结构变化处的图像修复。另外本文也从客观角度采用峰值信噪比（PSNR）的方法将本文算法与Criminisi算法进行了对比，如表1，PSNR的计算公式如公式（10）。

式中 f（i，j）为原灰度图像，修复后的图像为 f^（i，j），M、N分别为图像的宽和高，

PSNR值越大说明修复图像与参考图像越相似，修复效率越高，算法性能越好。

图2 实验一结果对比图Fig.2 Comparison chart of the first experiment

图3 实验二结果对比图Fig.3 Comparison chart of the second experiment

表1 两种算法的PSNR对比表Tab.1 PSNR comparison table of two algorithms

3 结束语

实验结果表明，本文算法的修复效果明显优于Criminisi算法，对具有明显结构特征的图像修复更有优势，避免了Criminisi算法会造成图像结构性丢失以及错误衍生等现象的发生。但是由于本文算法中需要计算目标块中已知点的平均梯度模值以及目标块与对应匹配块中已知点的平均梯度差值导致修复时间略高于Criminisi算法，以后会在修复时间上进一步的研究。

[1]Bertalmio M，Sapiro G，Caselles V，et al.Image inpainting[C]//Proceedings of SIGGRA PH， ACM Press，2000:417-424.

[2]Chan T，Shen J.Mathematical models for local non-texture inpaintings[J].SIAM Journal on Applied Mathematics，2001，62（3）:1019-1043.

[3]Chan T，Shen J.Non-texture inpainting by curvature-driven diffusions （CDD）[J].Journal of Visual Communication and Image Representation，2001，12（4）:436-449.

[4]胡熹.基于样本图像的图像修补技术研究[D].上海：上海交通大学电子信息工程学院，2013.

[5]范冠鹏，和红杰，陈帆，等.基于局部特性的图像修复算法[J].光电子激光，2012，23（12）:2411-2416.FAN Guan-peng，HE Hong-jie，CHEN Fan，et al.An image inpainting algorithm based on local properties[J].Journal of Optoelectronics and Laser，2012，23（12）:2411-2416.

[6]孟春芝，何凯，焦青兰.自适应样本块大小的图像修复方法[J].中国图像图形学报，2012，17（3）:338-341.MENG Chun-zhi，HE Kai，JIAO Qing-lan.Image completion method with adaptive patch size[J].Journal of Image and Grapphics，2012，17（3）:338-341.