面向图像修复的域相似算法

何文韬，叶学义，何志伟，汪云路

杭州电子科技大学模式识别与信息安全实验室，杭州310018

1 引言

图像修复是指利用图像中的已知信息，对图像中遗失的或者损坏的区域按照一定的规则自动的进行填充，并且尽可能地使修复后的图像接近或达到原始图像的视觉效果，使观察者无法察觉[1-2]。近几年来，该技术得到了国内外专家的广泛关注，并且将该技术深入到越来越多的应用领域中，例如，将图像修复技术应用于去交织[3]、高效图像压缩[4]以及恶劣信道中JPEG图像传输时丢失块的恢复[5]等方面。

目前的数字图像修复算法大致可以分为两类：基于形态特征的图像修复和基于纹理特征的图像修复。基于形态特征的图像修复中比较常用的方法是使用偏微分方程（PDE）进行修复。Marcelo Bertalmio等人[2]提出了一种模拟博物馆艺术家修复艺术作品过程的PDE图像修复算法；随后一些基于PDE的改进算法和衍生模型也被提出，例如TV模型[6-7]、CDD模型[8]等。虽然大部分基于PDE的图像修复算法对于划痕等小尺度破损有较好的修复效果，但是它们的修复效率不高，而且对于破损区域较大或破损区域周围纹理比较丰富的图像，修复后一般都会出现部分失真和模糊[1，9]。

基于纹理特征的图像修复算法的基本思路是通过从图像完好区域中寻找与图像受损区域最匹配的块进行修复。其中，Criminisi等人[10]提出一种基于优先级的纹理合成修复算法，使得当破损区域的周围已知像素比例大且结构特征明显时，该破损区域被优先修复。然而，现有的算法在寻找匹配块的时候，大多数采用的都是全局搜索的方法。这种方法不但修复的时间很长，而且容易产生错误的匹配，影响了图像修复的效率[11-12]。

在基于偏微分方程的图像修复和基于纹理合成的图像修复算法的基础上，针对这些修复方法在修复效率上的不足，提出了一种新的基于域相似的图像修复算法。本文算法先计算待修复区域边界上的所有待修复点优先级，然后按照优先级从大到小的顺序来设置图像的修复顺序，算法采用像素点邻域的相似来衡量两个像素点的相似程度，充分考虑了待修复像素的邻域中已知信息对该像素的影响，而每个待修复点的值等于该点邻域中所有满足相似度要求的已知点像素值的求和平均。仿真实验结果表明，在同等的修复区域和保证修复效果的条件下，本文算法显著地缩短了修复时间，提高了图像修复的效率。

2 域相似算法的修复

2.1 算法的基本框架

设I为待修复图像，Ω为待修复区域，即目标区域；∂Ω为待修复区域的边界；Φ表示待修复区域以外的部分(Φ=I-Ω)，即已知区域；边界上待修复点p的邻域记为Ψp，即以p点为中心的N×N的区域，如图1所示。

图1 待修复区域及像素的邻域

修复从待修复边界∂Ω开始，由外向内，逐层推进，按照修复顺序修复每一层上的待修复点。本文修复顺序设定为优先级从大到小的顺序，因此先对待修复区域边界点p计算优先级（优先级定义见2.2节），按照修复顺序逐个的修复待修复区域边界中的像素点。在对待修复点p修复时，因为每个像素点受其邻近像素点的影响比较大，所以先计算待修复点p与其Ψp邻域中已知点的相似度值（相似度的定义见2.3节），如果Ψp邻域中已知点的相似度值小于预先设定好的相似度阈值，那么将这些已知点求和并平均，并将该值作为待修复点p的像素值。

为了降低在修复过程中的误差，采用从待修复区域边界向内逐步推进的修复方法[9]。因此，算法的修复流程是先获取待修复区域边界上的所有点，计算这些点的优先级，然后把优先级按照从大到小的顺序设置为修复顺序依次修复每一个待修复点。在每一个待修复点修复完成之后更新图像，这样可以提高接下来其他待修复点修复的准确性，在待修复区域所有的边界点修复完成后，再更新图像，重新提取边界，直到整个图像修复完成。而在修复每一个待修复点时，先计算出待修复点邻域中所有已知点与该点的相似度值，然后根据预先设定好的相似度阈值判断这些已知点与待修复点的相似关系，最后将邻域中符合相似度要求的所有已知点的像素值求和平均，并作为待修复点的值。

具体的修复流程如图2所示。

图2 图像修复流程图

2.2 优先级函数

任选待修复区域边界上一点p，Ψp表示以p点为中心的N×N正方形区域。由于修复是从边界向内部逐步推进，边界点的修复会影响待修复区域内部的修复，因此应该最大可能的降低边界点的修复错误。对于待修复的边界点p，如果Ψp中含有的已知像素点越多，表示点p周围的有用信息越多，那么点p应该优先被修复，这样就可以提高边界点修复的准确率。而如果Ψp中的结构特征明显，那么点p也应该优先被修复，这样就可以防止结构信息的丢失，保证图像边缘结构的连通。因此，定义p点的优先级函数P(p)如式（1）所示：

P(p)=(αC(p)+ω)(βD(p)+λ)，0＜α，ω，β，λ＜1（1）其中C(p)为置信度项，表示Ψp中已知像素所占的比例，它要求优先修复那些邻域中包含已知像素更多的点；D(p)为数据项，表示Ψp中的结构信息量，它反映了邻域块中结构信息的强弱，从而保证结构特征明显的部分被优先修复。由C(p)和D(p)根据式（1）计算点p优先权的大小。

置信度项和数据项的计算公式引用于文献[9]中，分别如式（2）所示：

其中，|Ψp|为p邻域中所有像素点个数，q为p邻域Ψp中除点p外的像素点，γ为归一化因子，一般图像的灰度值取值范围为0～255，本文取255（对于彩色图像，本文分为R、G、B三个通道分别进行修复）。∇的方向是图像的等照度线方向，即梯度的垂直方向，np是待修复区域边界∂Ω上p点的单位法向量。这里的数据项D(p)是用p点的等照度线方向和边界上p点内法线方向的内积表示，如果p点等照度线方向和内法线方向的夹角越小，由数据项定义可知，就说明p点数据项越大，即优先级越大[9]。

置信度项的初始化如下：

等照度线的计算公式如（4）：

其中Ix、Iy分别表示图像在x方向、y方向上的差分，坐标系示意图如图3所示，计算公式如式（5）所示。

图3 坐标系示意图

与Criminisi等人[9]提出的优先级函数(P(p)=C(p)D(p))相比较，式（1）中的ω能够有效地防止在计算过程中C(p)快速下降到0，导致P(p)计算失去真实性的情况。而λ可以防止在结构特征不明显的区域D(p)为0，导致P(p)计算失去真实性的情况。在本文实验中将这两个参数设置为ω=0.001，λ=0.001。而α、β是权重因子，且α+β=1，修复者可以根据不同的图像要求选择不同的α、β来控制优先级的计算中置信度项和数据项的侧重程度。经过多次实验之后，如果破损区域为平滑区域，设置α=0.7，β=0.3，如果破损区域为结构特征明显区域，设置α=0.3，β=0.7，这样能够达到比较好的修复效果。

2.3 相似度函数

考虑到图像的局部信息能够比单个像素更好地描述图像的特征，因此判断相似性的基本思想是利用图像待修复区域中某一点（这里为点p）的邻域与已知点邻域的相似性来判断已知点和该待修复点的相似程度，而不是直接利用传统的单个像素点来比较相似。邻域块的选择具体如图4所示（灰色区域为破损区域）。

图4 域相似原理图

而对于相似度函数的选取，由于一方面，灰度信息是一种重要的视觉信息属性；另一方面上，灰度信息又丢失了图像的空间关系和结构特征，也就是说图像的信息没有完全的利用起来，而且在图像修复中，显著结构特征的相似更为重要。在此基础上，本文通过多次实验发现，灰度信息和梯度信息共同计算两个像素点之间的相似度可以使得修复后的图像更加能够满足人们的视觉效果。因此，定义待修复点邻域与待修复点邻域中已知点的邻域之间像素差异的和加上在x、y方向上的梯度差异的和为相似度函数，其中第一部分表示了灰度像素信息的直接差异，第二部分代表了图像局部区域之间的空间信息关系和结构特征的相似度，使得像素点间的相对位置关系得到了考虑，从空间关系上弥补了传统方法对于点的相似只考虑灰度信息差异的不足。如果这两个像素点的邻域之间的像素差异和梯度差异越小，那么这两像素点之间的相似度函数值就越大，即这两个像素点就越相似，反之，这两个像素点就越不相似。如果这两个差异值其中一个大，另一个小，但是只要这两个差异的和大于相似度阈值，就认为这两个像素点相似。

其中，N为邻域中已知点的个数，主要作用是将相似度函数进行归一化处理。为像素差异和，代表在x y方向上的梯度差异和，分别定义为式（7）、（8）、（9）：

从式（6）可以看出，其不仅包含了图像的灰度像素值差异，而且也考虑了待修复像素信息的空间位置关系和待修复像素邻域块中的结构特征相似度，因此该算法能够保持图像更多的细节信息，使修复后的图像达到一个很好的视觉效果。

2.4 修复的具体实现

对待修复点p的修复，利用该点邻域Ψp中所有满足相似度要求的已知点，将这些已知点的像素值求和，再取平均赋给待修复点。

待修复点的修复公式如式（11）所示：

其中，g(p，q)为约束函数，当已知点的相似度函数满足相似度要求时（即为相似度函数，定义见公式（6）），g(p，q)=1，反之，g(p，q)=0。

如果邻域中没有找到满足相似度要求的已知点，则选择相似度最小的已知点作为待修复点的值。N(p)表示所有用于修复p的像素的个数，具体为式（12）：

3 仿真实验及分析

为了能够体现新的域相似算法在效率上的提高，选择BSCB、Criminisi算法（这两种算法的仿真实验和新的邻域平均算法的仿真实验是在相同的实验平台下实现）与新的域相似算法对比，用程序的运行时间来衡量算法的效率，用细小划痕图像的修复、文本的移除作为实验内容。对于彩色图像的修复，先将彩色图像分为R、G、B三个通道，按照实验流程分别对这三个通道进行修复。

图5是灰度修复的结果对比图，图5（a）是划痕破损图像；图5（b）是BSCB方法的修复结果，由于修复过程的平滑作用使得图像略显模糊，而且图像上仍有修复痕迹；图5（c）是Criminisi算法的修复结果，该算法修复的效果不错，但是在匹配过程中需要重复的全局搜索，导致时间较长；图5（d）为新的算法修复的结果，所花费的时间是最少的，修复效果不错。

图5 灰度图像划痕的修复

图6为灰度图像中文字的移除，从上面几幅图像可以看出，图6（b）的图像比较模糊，图6（c）、（d）两幅图像中则很难发现已修复过的区域。

图7、8为彩色图像修复效果对比图，具体也分为划痕图像的修复和文字的去除。从图7、8中也可以看出，在用BSCB算法修复之后，修复之后的图像比较模糊，而Criminisi算法和新的修复算法修复之后的图像比较自然清晰。具体各个算法所花费的时间对比情况，见表1。

从表1给出的数据来看，运行时间与图像的破损区域大小以及图片尺寸都有一定的关系。而且从表中可以看出，新的修复算法的修复时间明显比其他两种方法的修复时间少了几倍。

图6 灰度图像文字的移除

图7 彩色图像划痕的修复

图8 彩色图像文字的去除

表1 几种不同修复方法运行时间对比

4 结论

针对偏微分方程修复算法和纹理合成修复算法修复效率低的问题，新的修复算法修复时无须进行大量的迭代和搜寻匹配模块，缩短了计算的时间，提高了修复的效率；在修复过程中，充分利用了待修复点邻域中的图像信息，以像素点邻域的相似作为两个像素相似的指标，在对待修复点修复时，仅仅利用到了局部邻域中满足相似度要求的已知像素点，提高了待修复点修复的准确性，有效地降低了边界上修复完成的像素点对待修复内部的修复提供的信息的错误率，因此也能得到比较满意的修复效果。仿真实验结果表明，在同等修复区域和修复效果的条件下，本文算法显著地缩短了修复时间，提高了图像修复的效率。

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

[2]Bertalmío M，Sapiro G.Image inpainting[C]//Proceedings of the ACM Siggraph Processing，2000：417-424.

[3]Ballester C，Bertalm IO M，Caselles V，et al.An inpaintingbased deinterlacing method[J].IEEE Transactions on Image Processing，2007，16（10）：2476-2491.

[4]Liu D，Sun X，Wu F，et al.Image compression with edgebased inpainting[J].IEEE Transactions on Circuits and Systems for Video Technology，2007，17（10）：1273-1287.

[5]Rane S D，Sapiro G，Bertalmio M.Structure and texture filling-in of missing image blocks in wireless transmission and compression applications[J].IEEE Transactions on Image Processing，2003，12（3）：296-303.

[6]Chan T F，Kang S H.Mathematical medels for local nontexture inpainting[J].SIAM Journal of Applied Mathematics，2001，62（3）：1019-1043.

[7]Rudin L I，Osher S，Fatem i E.Nonlinear total variation based noise removal algorithms[J].Nonlinear Phenomena：Physica D，1992，60（1/4）：259.

[8]Chan T F，Shen J.Nontexture inpainting by curvature-driven diffusions[J].Journal of Visual Communication and Image Representation，2001，12（4）：436-449.

[9]叶学义，王靖，赵知劲，等.鲁棒的梯度驱动图像修复算法[J].中国图象图形学报，2012，17（6）：630-635.

[10]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.

[11]Cheng W H.Robust algorithm for exemplar-based image inpainting[C]//Proceedings of the International Conference on Computer Graphics，Imaging，Vision，2005：64-69.

[12]Goyal A P，Diwakar S.Fast and enhanced algorithm for exemplar based image inpainting[C]//Proceedings of the 4th Pacific-Rim Symposium on Image and Video Technology（PSIVT），2010.