区域自适应的图像修复算法

张巧焕，唐向宏，2，任澍

1.杭州电子科技大学通信工程学院，杭州 310018

2.杭州电子科技大学信息工程学院，杭州 310018

区域自适应的图像修复算法

张巧焕1，唐向宏1，2，任澍1

1.杭州电子科技大学通信工程学院，杭州 310018

2.杭州电子科技大学信息工程学院，杭州 310018

基于样本的Criminisi算法是纹理合成图像修复技术中的经典算法[1-3]，文中称之为Criminisi算法，它通过定义优先级函数来确定图像修复的顺序，并使用穷尽搜索的方式在整幅图像的已知信息中寻找最优匹配像素块，并能够同时修复结构和纹理信息，取得了较好图像修复效果。但是Criminisi算法使用全局搜索的方式寻找最优匹配块，导致算法耗时较多并出现一定的错误匹配；同时在修复的过程中使用固定大小的像素模板，在一定程度上导致了在结构处信息的误匹配，造成了修复结果的失真。

针对这些不足，不少学者也从不同的角度进行了改进探索。Feng Τang等人利用纹理相似性对图像进行区域划分和相干置信度衡量[4]，不仅减少了修复时间，也在一定程度上提高了图像修复的精度和抑制了误差的传播，但是由于对不同纹理的边界定义模糊，所以在某些情况下也会出现较大的修复误差。张红英[5]和魏琳[6]等人使用梯度信息来决定修复模板的大小，但在纹理方向不明显时，梯度的计算不准确，图像的修复效果则不够理想；同时由于使用梯度信息自适应选择修复像素块大小，在一定情况下梯度计算不准确，可能会导致一定的错误匹配，从而影响图像的修复效果。

因此，本文通过对破损区域的形状和尺寸进行分析，以及待修复像素点邻域中边界的存在和强弱情况，从最优匹配像素块搜索的区域和修复像素块大小的自适应选择来探讨基于样本的图像修复算法Criminisi图像修复改进算法。

1 Criminisi算法的基本原理

Criminisi算法主要由三部分组成[3]：（1）优先级计算；（2）最优匹配像素块的搜索和像素信息更新；（3）置信度更新。

图1 Criminisi算法修复示意图

（1）优先级计算。在优先级的计算过程中，首先确定待修复区域的边缘，从而计算边缘上各像素点的优先级。待修复区域边缘上任意一个像素p的优先级函数P(p)定义为：

式中，置信项C(p)和数据项D(p)的大小分别为：

其中，|ψp|是ψp的面积，α是归一化系数（对于8位的灰度图像，α=255）。C(p)是像素点p周围可靠信息的数目的一种度量。初始化时，置C(p)=0 ∀p∈Ω，C(p)=1，∀p∈Ι-Ω。D(p)表示每次迭代时轮廓δΩ处等照度线与边界法向量的内积，两者的夹角越小，优先级越高，它反映的是图像的结构信息。

（2）寻找最优匹配像素块。一旦待修复区域边缘上各个像素点的优先级值计算出来，具有最大优先级的点p对应的像素块ψp就确定下来了，然后在整个图像的已知信息区域中寻找与ψp最相似的图像块，即最优匹配像素块，它是通过式（4）计算得到的最小值。

其中，m、n表示像素块的长度和宽度，p表示待修复像素块中的像素，q表示匹配像素块中的像素。

（3）像素灰度值和置信度的更新。当找到最优匹配块后，用最优匹配像素块中对应像素的数值填充待修复像素块中的未知像素，从而完成一次修复。由于原来的未知像素变为已知像素，此时，它们的置信度也需要更新，更新的方式如下：

重复步骤（1）～（3），直至所有的未知像素都修复完毕。

2 算法的改进

2.1 搜索区域尺寸的确定

由于马尔可夫随机场模型是纹理图像的一种客观认识，它体现了纹理的局部性和稳定性，即一个像素点或像素块的亮度都可以由它们的邻域像素唯一确定，而与图像的其他部分无关[7]。由于图像破损程度的大小，直接影响图像中剩余已知像素的多少，所以当用像素的邻域信息决定其亮度时，其邻域尺寸应与图像的破损大小有关。

因此，可通过对图像中破损区域的形状和尺寸进行判断分析，确定最优匹配像素块的搜索区域[8]，且此搜索区域为以待修复像素为中心的正方形像素块（为了方便说明，文中以像素为单位测量破损区域的尺寸）。

首先，根据数学中纵横坐标的概念，找出横坐标方向和纵坐标方向的最大尺寸，并分别定义为破损区域的横向尺寸和纵向尺寸；当破损区域的横向尺寸和纵向尺寸相差较大时，规定其中较小者对应的坐标方向为破损区域的主方向；其次，文中定义破损区域主方向上的最大破损尺寸为搜索区域基值νal；最后，根据图像破损区域的面积大小及其包含结构纹理信息不同，建立搜索区域尺寸与搜索区域基值之间不同的函数关系。

经过大量反复的实验证明，搜索区域基值等于30是划分破损区域“狭长”型与“非狭长”型的阈值。而且本文规定：当破损区域存在主方向，并且搜索区域基值不大于30时，称此破损区域为规则性破损区域；如果破损区域不存在主方向或者搜索区域基值大于30，则称之为非规则性破损区域。

因此，破损图像搜索区域尺寸与搜索区域基值νal的关系如下：

（1）由于规则性破损区域的搜索区域基值不大于30，所以破损区域整体上属于“狭长”型，图像剩余的已知信息比较丰富，则此时的搜索区域边长S定义为：

（2）如果搜索区域基值大于30，不论破损区域是否存在主方向，则破损图像的正方形搜索区域边长S采用下式计算：

（3）当图像中存在多个破损区域时，则分别计算各自的搜索区域尺寸，判断各自是规则性破损区域或非规则性破损区域，其对应的搜索区域边长按照式（6）和式（7）计算，并且当图像破损区域周围的结构或纹理信息比较复杂时，也通过式（7）计算其搜索区域的边长。

2.2 自适应修复模板大小的确定

现有的图像修复方法大多是利用图像中的已知信息首先恢复破损区域中信息的结构，然后再恢复结构中的具体信息[1]，这也体现了格式塔原理中人眼对图像信息的低层和高层感受[9]。通常情况下，图像的结构信息理解为图像中物体的边界，因此，利用边界信息来引导图像修复，会提高图像修复的准确度。通常认为，在纹理和结构较平滑的区域，修复时应选择较大尺寸的像素块，这样既不影响图像的修复效果，还相应地提高了修复执行的效率；当破损区域中包含的纹理比较丰富，或者包含明显的结构信息时，为了避免产生较大的修复误差，因此应选用较小尺寸的修复像素块。

由于边界信息在图像修复中的重要影响和引导作用，所以利用边界信息确定修复模板大小则会在一定程度上提高图像修复的精度和质量。文中根据人眼视觉系统对图像信息交界处对比度的感知能力，按照对比度由强到弱的程度依次把边界分为强边界、较强边界和弱边界（平滑区域）三种类型。

通过对多幅不同图像不同信息交界处对比度的分析和总结，得到边界处信息对比度的不同，实质上是边界处像素差值的不同，即相邻像素数值相差越大，它们之间的边界越明显；反之，当它们之差低于某一定值时，则它们之间的边界表现不强烈。同时，文中规定强边界存在时相邻像素的最小差值为35；较强边界存在时相邻像素的最小差值为15，最大差值为35；而当相邻像素的差值小于15时，则认为像素处于平滑区域。

同时，为了找出像素点邻域中边界的存在和强弱情况，确定一个以待修复像素点为中心的7×7邻域像素块，并通过对该像素块的相邻列差值矩阵K2{7×6}和相邻行差值矩阵K3{6×7}的矩阵元素进行分析找出其存在的边界情况（如果元素相减的过程中有未知像素存在则此处差值置0）。

若令numel计算矩阵中满足一定条件的元素个数，则本文规定：

（1）当矩阵K2满足：

或矩阵K3满足：

则认为待修复像素点邻域中存在强边界，修复该未知像素时采用大小为3×3的像素块。

（2）当矩阵K2和矩阵K3满足：

则认为待修复像素点邻域中存在较强边界，修复该未知像素时采用大小为5×5的像素块。

（3）当矩阵K2和矩阵K3满足：则认为待修复像素点处于弱边界或平滑区域中，修复该未知像素时采用大小为7×7的像素块。

2.3 置信度的更新和图像修复顺序

由于图像修复的结果只是在一定相似程度上对原始完整图像的呈现，因此并不等同于原始完整图像。如果修复后的图像在人眼视觉系统观察下没有明显的误差，则称修复结果与原始完整图像近似，如果填充的像素与原始像素的数值相同，称之为像素的重现；如果填充的像素与原始像素的数值之差在一定小的范围内，称之为像素的近似，填充的像素称为原始像素的相似像素点。较理想的图像修复结果即是用破损像素的相似像素填充的结果。通过大量的实验及验证，文中定义：如果两个像素点的数值之差不大于4，即它们之间没有可识别的边界，则称这两个像素点相似。

Criminisi算法直接用中心像素点的置信度更新此次修复的所有未知像素，没有考虑本次修复效果对此后图像修复顺序的确定以及误差累积的影响。为了减少误差的传播，本文在像素相似的基础上，调整了置信度更新方法[8]和图像修复顺序：

（1）如果最优匹配块与待修复像素块在已有信息位置的像素相似，此时，按照Criminisi算法中的更新方式进行更新[3]，如式（8）所示：

如果最优匹配像素块与待修复像素块之间的误差在已有信息位置的像素不相似，这时，认为最优匹配像素块与待修复像素块差别较大，采用以下更新方式：

（2）根据像素的相似性，调整后的图像修复顺序为：第一步，提取破损区域的初始边缘，并按照优先级单调递增的顺序对边缘上的像素点进行排序。

第二步，修复当前像素序列中的最后一个像素。在区域搜索的基础上，搜索由序列中最后一个像素对应待修复像素块的最优匹配像素块；结合相似像素点的判断方法，对当前最优匹配块的对应已知像素进行相似判断：如果最优匹配像素块与待修复像素块对应位置已知像素满足像素点相似条件，则用此最优匹配像素块中的信息进行修复，并把该像素点从序列中删除；如果不满足像素点相似条件，则把此未知像素点移至像素序列的3/4位置处，并等待下次修复，直到初始边缘上所有的像素点都不满足修复条件。

第三步，重复第一步和第二步骤，直到新的破损区域边缘上所有的像素点都不满足附加匹配条件。此时按照文献[8]进行修复，并直至所有剩余的未知像素修复完毕。

3 实验结果及分析

为了验证本文所讨论的修复算法的可行性和有效性，在计算机上进行了大量仿真实验，并与相关修复算法进行了实验比较。实验所用的计算机配置为Inter Pentium 4 CPU，主频2.40 GHz，768 MB内存，仿真软件为Matlab 7.0。

图2（a）和图3（a）的破损区域中都包含了一些边界信息，同时图2（a）中也包含部分丰富的纹理信息。从Criminisi算法的修复结果可以看出，图2（b）中强边界处产生大量的信息模糊和延伸，图3（b）中的桌子边缘处产生了信息混乱和延伸，导致桌子的边缘发生了变形；而本文改进算法的修复结果中，图2（c）在较强边界处的信息延伸已经明显减少，图3（c）中的桌子边缘处和桌布边缘处的信息延伸也得到较好的恢复和抑制，但由于人物胳膊与地面的亮度近似，因此修复过程中在人物胳膊处仍产生了一定的延伸。总的来说，改进算法的整体修复效果比Criminisi算法更加接近满足人眼视觉需要。

图2 Baboon图像修复实验

图3 Barbara图像修复实验

图4中给出了去除图像大面积人物和文字的修复实验。从图4（a）中可以看出，人物身后的图像信息主要是平滑区域的海平面、存在较强边界的波浪以及远处的平滑背景。从Criminisi算法的修复结果来看，出现了视觉系统感知下的明显的波浪信息延伸，即把图像中的白色波浪信息延伸到如图4（c）所示；从图4（d）所示的本文改进算法修复结果来看，人物身后的波浪在一定程度上得到了恢复，并且与其周围的波浪连接比较平滑，达到了较好的图像恢复效果。

图4 人物及文字去除实验

由于改进算法中采用区域搜索的方法寻找最优匹配块，所以修复速度较之原有的Criminisi算法有很大的提高。表1给出了图2～图4在Criminisi算法和本文改进算法下的修复时间。

表1 Criminisi算法和本文改进算法下的修复时间s

从表1中两种算法所用时间可以看出，Criminisi算法甚至需要几个小时的时间完成图像修复，本文提出的区域搜索方法则大大减少了修复时间，修复时间甚至可以达到Criminisi算法的几十分之一。

为了验证本文提出的改进算法的有效性，仿真实验中也与类似的修改算法进行了性能比较。例如，与魏琳等人[6]提出的根据梯度信息自适应选择修复像素块大小的自适应算法进行性能比较，图5给出了文献[3]、文献[6]和本文改进算法对破损图像修复的结果。

图5 本文改进算法与文献[6]对Lena图像的修复效果

从图5（b）中Criminisi算法的修复结果可以看出，在人物帽子的强边界处产生了较严重的信息延伸；文献[6]采用自适应修复像素块的方法，使图像修复的精度有所提高，但是在人物帽子的边界处仍出现一定的延伸，如图5（c）所示；本文改进算法的修复结果虽然在人物左边的灰色线条处也出现较小的误差，但在人物帽子强边界处以及整体视觉效果比较符合人眼视觉要求，在一定程度上修复效果好于文献[6]的修复效果，如图5（d）所示。

综合以上实验可以得出，本文提出的区域自适应Criminisi算法在大大缩短修复时间的同时，也能较好地保持破损处信息的结构和纹理特性，达到了较好的修复效果，并且能够满足大部分破损图像的修复。

4 结束语

本文针对Criminisi算法使用固定大小修复模板和全局搜索的方式修复图像，容易导致图像在边界处产生信息延伸和局部的错误匹配，以及整个修复过程耗时较多的问题，从图像破损区域的尺寸和未知像素邻域中边界的强弱情况出发，探讨了最优匹配块的区域搜索和自适应模板的图像修复算法，并同时根据像素的相似性影响置信度更新和图像修复顺序。大量仿真实验表明，本文提出的区域自适应Criminisi图像修复算法不仅能够有效地抑制边界处信息的延伸，同时在一定程度上提高了修复的精度，并且大大缩短了图像修复的时间，相对于Criminisi算法和相近算法取得了较好的修复效果。

[1]Bertalmio M，Sapiro G.Image inpainting[C]//Proceedings of SlGGRAPH，2000：417-424．

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

[3]Criminisi A，Perez P，Τoyama K.Region filling and object removal by exemplar-based inpainting[J].IEEE Computer Τransactions on Image Processing，2004，13（9）：1200-1212.

[4]Τang F，Ying Y，Wang J，et al.A novel texture synthesis based algorithm for object removal in photographs[C]//Τhe Ninth Asian Computing Science Conference，2004：248-258.

[5]张红英.数字图像修复技术的研究与应用[D].成都：电子科技大学，2006.

[6]魏琳，陈秀宏.基于纹理方向的图像修复算法[J].计算机应用，2008，28（9）：2315-2317.

[7]Efros A，Leung Τ.Τexture synthesis by non-parametric sampling[C]//IEEE International Conefrence on Computer Vision，1999：1033-1038.

[8]张巧焕，唐向宏，任澍.基于样本的快速图像修复算法[J].杭州电子科技大学学报，2011，31（5）：139-142.

[9]Koffka K.Principle of Gestalt psychology[M].London：Lund Humphries，1935.

ZHANG Qiaohuan1,ΤANG Xianghong1，2,REN Shu1

1.School of Communication Engineering,Hangzhou Dianzi University,Hangzhou 310018,China
2.School of Information Engineering,Hangzhou Dianzi University,Hangzhou 310018,China

Τhe exemplar-based image inpainting algorithm proposed by Criminisi and his partner,which uses exhaustive searching to get the best-matching patch and adopts fixed-size patch to fill the image,will cause error matching and information extension. For this problem,based on the decisive role of a pixel’s neighboring block in the pixel’s value and the importance of structure information,this paper presents an image inpainting algorithm based on regional searching and adaptive template to enhance the local information harmony and boundary recovery ability,so it can improve the whole inpainting effect.A number of experiment results demonstrate that the improved method not only reduces the inpainting time and keeps the structure better,but also has a better visual effect.

Criminisi;exemplar-based;image inpainting;boundary;regional searching;adaptive template

针对Criminisi等人提出的基于样本的图像修复算法使用穷尽搜索的方式寻找最优匹配像素块，以及采用固定大小的修复像素块进行修复时产生的错误匹配和信息延伸对图像修复质量的影响，根据像素点周围邻域信息对该像素点的决定作用和结构信息的重要性，提出一种区域搜索和自适应模板图像修复方法，以增强信息的局部协调性和边界信息的恢复能力，提高图像整体的修复效果。大量实验表明，改进算法在减少修复时间的同时，能较好地保持图像的结构，从而使修复结果达到更好的视觉效果。

Criminisi算法；基于样本；图像修复；边界；区域搜索；自适应模板

A

ΤP391

10.3778/j.issn.1002-8331.1201-0216

ZHANG Qiaohuan,TANG Xianghong,REN Shu.Regional and adaptive image inpainting algorithm.Computer Engineering and Applications,2013,49（21）：160-163.

张巧焕（1984—），女，硕士，研究方向：多媒体信息与技术；唐向宏（1962—），男，博士，教授，研究方向：小波理论以及多媒体通信；任澍（1987—），男，硕士，研究方向：多媒体信息与技术。E-mail：qiaohuan1984@163.com

2012-01-12

2012-11-19

1002-8331（2013）21-0160-04