基于颜色信息和阈值的图像修复算法

许文杰，张相芬，严 实

(上海师范大学 信息与机电工程学院，上海200234)

责任编辑:时 雯

图像修复是近几年新兴的一个研究领域，它广泛应用于古文字画、旧照片的修复以及字幕和一些图片中人物的去除。图像修复的原理即是根据破损图像周围的已知信息，通过特定的算法使图像按规则从已知区域向破损区域传播，从而修复破损区域，并使修复后的图像达到或接近原图的效果。一般人为的修复需要花费大量的时间和劳力，且修复效果较差。图像修复技术使人们从繁琐的图像修复工作中解脱出来，并减少人为失误，提高准确度和可信度。由于图像修复在理论和实际中都有着重要的意义，因此近年来受到国内外的广泛关注。

目前的数字图像修复算法主要分为两类，即针对纹理图像和非纹理[1](即结构)图像进行研究，研究方法也大致被分成以下两类，对于非纹理结构的图像主要采用变偏微分方程模型[2]，它包括变分模型和偏微分方程模型两种。由Bertalmio[3]等人提出一种分解图像修复的算法，主要思想是首先找到待修复区域，利用边缘信息，获得等照线度的方向，从而沿边缘轮廓向边界内扩散。该方法虽然考虑到了扩散信息和扩散方向，但是不稳定，对损坏图像的修复效果也不是很好，只适合于划痕、污迹和文字等细窄的区域修复。而对于具有纹理结构的图像，需要通过特征匹配来进行纹理合成[4]。还原方法有以下两种，一种是将图像中的结构部分和纹理部分区分开，独立进行修复，这就是在分解图像基础上的修复技术;另一种是寻找目标区域的合成技术，通过选取以一个像素点为中心的区域块，在待修复区域周围寻找和它相近的目标区域块进行修复。该算法运行时间长，修复效果不佳。基于样例的同步处理纹理和结构区域[5]，不需要分割图像的方法是Criminisi等人在2003年提出的，即将待修复区域周围的图像作为样本，从中提取特征并选取匹配的纹理[6]，将其合成到待修复区域内，这种算法适用于较大区域的修复，取得了较好的修复效果，但是耗费时间过长，另外由于在计算的过程中，置信度会很快变为0，使修复顺序变的不可靠。同时，寻找匹配块是在整个图像中进行的，会花费很长的时间，因此在优先权和相似度的计算中还存在一定不足。

本文是在Criminisi算法的基础上对图像修复算法进行的改进。为了使优先权计算更加准确，本文采用梯度数据项、置信度和颜色共同决定填充顺序;同时为了达到更好的修复细节和边缘信息，将通过方差和梯度共同决定模板窗口的大小，最后通过改变搜索的顺序和阈值来减少修复时间，其中最优匹配块[7]由颜色和梯度共同决定相似性，使得修复后的图像具有更好的视觉效果。通过实验，证实可以产生较好的实验效果。

1 Criminisi算法

在一幅待修复图像中，有很多点需要修复，到底应该先修复哪个区域，对整幅图的修复效果非常重要，这样修复的顺序就变得很重要，它会影响到整幅图的修复质量。因此，本文首先要确定修复块的先后顺序。Criminisi算法说明见图1。

图1 Crinimisi算法说明图

优先权公式定义为

式中:C(p)和D(p)分别为数据项和置信度项，其中

对于常用的灰度图像，初始化时

当找到需要修复的块，即以点p为中心的修复块后，就需要寻找最佳的匹配块，公式为

式中:d表示两个区域块之间的差距，以SSD公式计算区域块内存在像素之间颜色的差距，找到合适的匹配块，然后将待修复区域块中的值用找到的目标区域块的值替换。

当匹配块对待修复区域进行替换后，按照式(5)来更新数据项和置信度项，如此循环计算，直到待修复块完全被修复。

2 算法改进

2.1 优先权算法

在Criminisi等人的算法中P (p)=C(p)D(p)，直接用已知像素与Ψp中像素量的比值作为置信项C(p)，经过分析置信度会很快降到接近于0，这时即使C(p)很大，两者相乘的结果也为0，优先顺序会被打乱，从而影响待修复区域的修复效果。针对此问题在计算优先级时，将它们分别乘以x1和x2的次方。若取x1=1，则x2=0，则优先级定义中没有考虑结构部分D(p)的强弱;若取x1=x2=1，则为Criminisi的方法，还通过G(P)使置信项的比重变大。在G(p)中，D(p)越大，表示Ψp内有关结构的信息就越多。R(p)代表了待修复块附近的RGB颜色的变化大小，R(p)的值越大，表明Ψp内RGB颜色变化越明显。因为在离待修复区域远的地方，置信度会越来越小，因此在一定程序上置信度项会阻碍线性结构的优先修补，所以在新的方法中加大了G(p)的权重。

目标区域的优先级的公式为

式中:x1和x2为正有理数;R(p)中σ代表Ψ(p)内的均方差;u表示Ψ(p)内均值。

在计算等照度线时需要用到目标区域的邻近像素值，而目标区域的值需要填充，是未知的，因此结果会有所偏差，为了避免这种情况，需要对待修复区域进行膨胀处理[8]。这样所有需要用到的像素值都是是已知的，从而可以增加结果的可靠性。

2.2 Ψp大小的确定

模板窗口的大小会对图像的修复结果有一定的影响。在高频部分包含有很多的细节和边缘，采用大的窗口模板，会丢失很多有用的信息。为了包含更多的细节和边缘信息，应当选取小的窗口。同样，在低频部分因为图像的变化很小。如果采用小的窗口，会浪费很多的时间。因此，Criminisi算法中选取的窗口模板大小相同是不合理的。

图像大多会受到噪声的影响，梯度对噪声比较敏感，虽然会影响其准确性，但是梯度可以间接反映图像空间频率的变化。同时方差对噪声不敏感，还能体现图像的局部差异性，因此本文利用方差和梯度函数共同来决定模板的大小。

本文算法先将待处理的图片经过归一化处理后再计算待求点的方差值，然后与梯度函数进行相加，采用梯度函数和方差来共同决定变Ψp窗口的大小。对于颜色变化比较大的区域采用小的修复块，可以更好地保留其颜色信息，同时也更符合人眼的视觉效果，而对于颜色变化小的区域就采用大的修复块，可以缩短修复的时间。这样，待修复区域的大小就可以根据图像纹理变化的方向性和颜色变化是否明显来自动调节大小。

本文选择的窗口大小计算函数为

式中:size(p)表示模板的大小;var(p)表示点的方差值。

2.3 最佳目标区域的选用

当选取出优先级最高的待修补区域后，就是要找到最合适的目标块对其进行修补，本文根据颜色和梯度差异共同来计算目标块Ψp和样本块Ψq之间的距离为G(Ψp，Ψq)[9]，定义为

式中:d(Ψp，Ψq)为待修复块与目标区域的像素值差的平方;L(Ψp，Ψq)为梯度的差的平方和，公式为

在Criminisi算法中搜索最佳匹配块的顺序是从左到右、从上到下，依次搜索，这样不仅需要的时间长，而且效率很低。已知在一幅纹理图像中，相邻的像素间的变化很小，因此可以只选取待修复区域的周围的点作为待匹配区域，在候选块与待修复块进行SSD计算得出最优匹配块，可以节约时间。

文中采用搜索最近最优匹配区域的搜索方法。根据前面计算优先权得到的修复点p，确定待修复块，然后根据p的棋盘距离为n(n=1，2，3，…)的各点作为q点，然后依次将以q点为中心的区域块与待修复的区域Ψp做SSD计算。将计算得到的值依次与阈值进行比较，当计算值小于阈值时，将待选区域块的值替换到待修复的区域;反之，如果计算值大于阈值时，将棋盘距离值加1，然后继续按这个顺序搜索，直到搜索到有计算值小于阈值，如果一直到搜索区域全部搜索完仍然没有找到比阈值小的计算值，就在计算值中选取一个最小的计算值的待选区域去替换待修复区域。

如图2所示，设p为待修复块的边缘上的点，从图中可以看出与p棋盘距离为1的像素分别为q11，q12，…，q18，首先会对棋盘距离为1的值进行搜索，如果没有找到小于阈值的计算值，则对距离为2的像素q21，q22，q23，…，q216进行搜索，一直重复下去，直到找到需要的区域块。这样得到的修复结果与其邻域的相关性较大，也更加符合视觉上的效果。

图2 区域块中像素值的表示

3 实验结果及结论

实验结果见图3～图6。图4中黑色部分为需要修复的部分，从图中5和6可以看出，改进的算法中由于可以调节窗口模板的大小，修复的速度会有所提高，同时修复效果较好。

图3 原图

图4 需要修复的图

图5 Criminisi算法修复的图

图6本文算法修复的图

图7 为待修复的图片，其中黑色为要修复的区域;图8为用Criminisi算法修复的图片。图9为待修复区域进行膨胀化处理后用Criminisi修复的图;图10为通过改进后的算法修复的图片。图9中水中的图的修复效果好些，图10中不仅水中没有多余的草，岸上的修复效果感觉也更贴近视觉效果。

4 实验结果分析

实验结果显示，经过改进后的方法具有更好的修复效果。首先，Criminisi算法的修复顺序是根据同线性结构的信息来决定的，对于一幅破损的图像，这种顺序有时并不是合理的，本文加入颜色信息，优化了算法，实验结果表明对于纹理颜色的变化能进行更好的修复，根据方差值与梯度来决定修复块的大小，从图4和图5就可看出明显的不同，修复效果更好，也更灵活。最后通过设定阈值来减少搜素的范围和时间，不过当阈值过小时修复效果会比较差，但可以节约时间。本文的缺点是算法过于复杂，特别是参数设置过多，对于部分图片，不能快速选择合适的参数。

[1]IDDO D，DANIEL C，HEZY Y，et al.Fragment based image completion[C]//Proc.ACM SIGGRAPH 2003.New York，USA:ACM Press，2003:303-312.

[2]SUN J，LU Y，JIA J，et al.Image completion with structure.propagation[C]//Proc.ACM SIGGRAPH 2005.Los Angels.USA:ACM Press，2005:961-969.

[3]BERTALMIO M，SAPIRO G，CASELLES V，et a1.Image inapaint inapainting[C]//Proc.the 27th Annum Conference on Computer Graphics and Interactive Techniques.New Or Ieans，USA:ACM Press，2000:417-424.

[4]BERTALMIO M，VESE L，SAPIRO G，et al.Simultaneous structure and texture image inpainting[J].IEEE Trans.Image Processing，2003，12(8):882-889.

[5]PENG H，HOU W，GONG N.Anim proved exemp larbased inpaint ingmethod for object removal[J].Journal of Computer-Aided Design& Computer Graphics，2006，18(9):1345-1349.

[6]张显全，高志卉.一种块匹配的图像修复算法[J].光电子激光，2012(4):805-811.

[7]CRIMINISI A，PEREZ P，TOYAMA K.Region filling and object removal by exemplar-based image inpainting[J].IEEE Trans.Image Processing，2004，13(9):1200-1212.

[8]王黎明.基于样本块的图像修补方法研究[D].北京:首都师范大学，2008.

[9]代仕梅，张红英，曾超.一种基于样例的快速图像修复算法[J].微型机与应用，2010(8):34-36.