基于改进优先级的加权匹配图像修复算法

陈晓冬， 朱晓临

（合肥工业大学 数学学院，安徽 合肥 230009）

0 引 言

图像修复是对图像中信息缺损的区域进行信息填充的过程，其目的就是对破损图像进行恢复，并且使观察者无法察觉到图像曾经缺损或已被修复［1］。因此，人们的主观认知及先验知识对图像修复的影响起着重要作用，故从视觉心理学的角度出发，提出了各种假设来解决该问题。

文献［2］提出了基于等照度线的方法；文献［3］提出了一种基于偏微分方程（partial differential equation，简称PDE）的修复算法；文献［4］提出了基于TV模型的修复方案；文献［5］在文献［3］的启发下，提出了CDD（曲率驱动扩散）模型的修复方法。文献［6－7］对TV模型不断地进行改进完善；文献［8－10］分别提出了一些新的修复算法。

尽管上述算法对破损区域相对较小的结构图像有显著的效果，但它们对破损区域较大的图像修复效果不太理想。

对于破损区域较大的纹理图像，文献［11］提出纹理合成方法，该算法的思想是从图像的已知区域中寻找与受损区域最匹配的块进行填充，从而实现图像修复。若图像中包含复杂结构时，这种方法的效果不太理想。

针对这种现象，文献［12］提出了基于样例的目标移除算法，随后将其进一步完善得到基于样例的目标移除与区域填充的图像修复算法［13］。文献［13］的算法在确保可以修复较大破损区域的同时，在一定程度上保留了图像的结构和纹理信息。尽管如此，Criminisi算法［13］在处理图像时，对较强的结构信息持续优先处理很容易造成偏差延续，导致修复效果出现较大偏差。由于这种方法是在整幅待修复图像中搜索、复制图像信息，然后对待修复域直接进行填充，因此会消耗较长时间。

文献 ［14－19］提出了改进方法解决偏差延续的问题，取得了一定的进展，却仍不够理想。

文献［20－21］提出用连接线的方法优先解决图像中存在的显著结构，收到一定成效，但由于其自动化程度较低，实时性效率低，且操作相对复杂，使其应用受到一定的限制。

本文从图像修复算法中的纹理合成算法入手，在对经典的Criminisi算法进行深入研究和分析的基础上，提出了一种基于改进优先级的加权匹配的图像修复算法。

1 Criminisi算法简介

如图1所示，记I为待修复图像，Ω为待修复区域，其边界为∂Ω，Φ为待修复图像的已知信息区域。

Criminisi算法考虑了待修复区域的修复顺序，提出了按优先级进行修复的思路。取P（p）作为决定修复顺序的优先级，即

其中，np是待修复区域Ω的边界∂Ω上点p处的法向量；是已知区域Φ边界的梯度向量的垂直向量（即等照度线方向）；α是标准归一化因子，在典型的灰度图像中取255；C（p）称为置信项，即填充块中已知信息所占的比例；D（p）（p∈∂Ω）称为数据项，即结构信息；当∀p∈Ω时，C（p）＝0；∀p∈I－Ω时，C（p）＝1。

图1 Criminisi算法示意图

根据预先定义好的优先级，在待修复域的边界∂Ω上选取点p，然后选择1个以p点为中心的小方块Ψp，即具有最高优先级的待修复块；再从已知区域Φ中寻找与Ψp最匹配的块。若Ψ＾q是已知信息区域中与Ψp最匹配的块（通常情况下，Ψ＾q应完全包含在已知区域Φ中），则

2 本文算法

2.1 算法思想

Criminisi合成算法的2个关键要素是优先级的确定和匹配块的选择。

针对第1个要素，传统的Criminis算法中优先级P（p）＝C（p）D（p）存在不足，因为其数据项D（p）可能为0，因而可能导致修复发生偏差。为此，文献［22］对此做了改进。

其核心思想是在Criminisi算法提出的信任项C（p）和数据项D（p）的基础上，增加边界项B（p）。与文献［13］相比，文献［22］的修复效果有所改善。不同算法修复结果比较，如图2所示。

传统的边缘提取算子在提取边界时也不够精确，导致待修复区域的边界很难被精确定位（见图2b），因而导致图像在待修复区域的边界附近得不到很好的修复；此外，优先级出现错误，致使预先确定的修复块并非是真正的待修复块，从而产生修复偏差（见图2c）。

图2 不同算法修复结果比较

虽然文献［22］提出了边界项B（p），改善了优先级P（p），但未考虑原始图像中对优先级影响更大的显著边缘的作用。基于此，本文在优先级计算中考虑如下几点：

（1）与待修复块中心点连接的显著边缘线。

（2）与修复块内边界某点连接的显著边缘线。

（3）其他突出的显著边缘线。

因此，在优先级P（p）的计算中增加了边缘项E（p），改进后的优先级P（p）为：

其中，λ1、λ2、λ3、λ4是非负常数；C（p）和D（p）的表达式与（2）式相同。B（p）和E（p）定义如下：

其中，Ep是显著边缘；∂Ωi表示第i次（0≤i≤N）修复后待修复区域的边界（Ω＝Ω0⊇Ω1⊇…⊇ΩN＝∅），而｛Ωi｝是每次执行修复之后新的待修复区域的序列集。

因此，在选取待修复域并将其置为纯色后，提取掩模图像，然后根据需要对掩码图像进行适当的掩模膨胀，以获取精准的边界图（见图2d），再按（5）式计算优先级。

针对Criminisi合成算法的第2个关键要素，文献［23］考虑到待修复块中各点与中心点距离的远近对匹配块产生的影响，指出欧氏距离可以看作信息间的相似程度，距离越近关联度越大，就越容易相互干扰，误差就越明显，因而提出了加权匹配的修复算法，对Criminisi算法中计算项d（Ψp，Ψq）进行改进，在该项中设置了一个权因子1／ε），即

其中，（x1，y1）、（x2，y2）分别是像素点的位置坐标，此时（4）式化为加权匹配公式，即

因此，本文在考虑到边缘项E（p）在待修补块与匹配块间影响作用的基础上，根据实验反复验证提出了新的加权因子，即

实验结果验证了改进后的权因子的合理性，于是Ψp的最匹配块为：

此外，传统算法通常是在整幅图像上寻找匹配块，这样不仅会消耗大量时间，而且可能导致视觉上原本不太匹配的块被填充在待修复区域，造成偏差延续。

本文算法基于图像结构相似性特征，首先对图像进行邻域相似分割，然后运用上述方法进行修复，使搜索域的选取变得更加灵活，大大缩短修复所用的时间；另一方面，可以使一些特定区域在修复时不受其他信息的干扰，避免偏差延续，从而保证修复结果更符合人们的视觉效果。

2.2 本文算法实现

本文提出一种改进的基于加权匹配的快速修复算法。初始时，人工选取待修复区域或待移除的目标，并将待修复域置为纯色，然后根据需要进行适度的掩码膨胀找到恰当的边界，再将待修复区域的边界标记为∂Ω0（＝∂Ω），设置＾B（p）＝∂Ω0，∀p∈∂Ω0。

执行步骤如下（初始i＝0）：

（1）找出待修复区域的边界∂Ωi，如果Ωi＝∅，退出循环，修复结束。如果＾B（p）∩Ωi＝∅，置＾B（p）＝∂Ωi，∀p∈∂Ωi。

（2）根据（2）式、（5）～（7）式计算优先权P（p），∀p∈∂Ωi。

（4）根据（8）式、（10）～（12）式找出最匹配的块Ψ＾q∈Φ。

（5）将Ψ＾q中对应的图像信息复制到Ψp∩Ω。

（6）令i＝i＋1，重复步骤（1）～（5）。

3 实验结果

采用Matlab 7.10作为工具，在Intel酷睿I3双核处理器（2.0GHz）、2G内存的PC机上进行实验。

图3～图5所示为本文算法与文献［13］Criminisi算法、文献［22］算法、文献［23］加权匹配算法修复结果的比较；图6所示为本文算法与传统TV算法的比较。

由图3可见，这是纹理修复常规比较的经典蹦极图像，图3c出现偏差延续的情况，存在明显的断痕。从图3d和图3e中看出，屋檐上下也存在一定的偏差延续情况，不能自然流畅地体现屋檐的特征。而从图3f看出，本文算法很好地解决了以上的诸多问题。

图3 本文算法与其他算法修复结果比较（一）

由图4可见，图4c和图4e出现了偏差延续的情况，存在明显的断痕。图4d比图4c和图4e有所改善，但仍然可以看出围墙顶面存在偏差延续的情况。而图4f显示本文的修复算法结果比其他算法视觉效果有了明显改观，且更加自然流畅。

由图5可见，图5c是因为文献［13］中的算法强调强边缘延续，导致草坪区域被路的颜色信息蔓延覆盖。图5e尽管没有大面积的崩溃，但由于文献［23］权因子自身存在的弱点，也导致了修复结果的偏差。图5d保证了图像在大范围上的视觉效果，但其右下角稍有瑕疵。而图5f显示本文算法很好地克服了上述存在的种种瑕疵，视觉效果最好。

在此例中，修复块的大小都是9×9，根据不同的强边缘图，在（5）式中选取不同的参数，λ1＝0，λ2＝1，λ3＝3.8，λ4＝1或λ1＝0.5，λ2＝1，λ3＝3.8，λ4＝0.5，模型相对灵活。

图4 本文算法与其他算法修复结果比较（二）

图5 本文算法与其他算法修复结果比较（三）

由图6可见，图6c为经典的TV算法修复结果，其左侧的竖条修复后出现了模糊。由图6d可以看出，本文算法不仅可以适用于结构图像，而且修复效果比TV模型还要好。其中，修复块的大小取7×7。

图6 本文算法与TV模型修复结果比较

修复时间比较见表1所列。

表1 修复时间的比较 s

4 结束语

本文通过分析一些图像修复算法在修复某些图像时，视觉效果产生偏差的原因，提出了改进算法。实验结果表明，本文提出的改进算法不仅可以有效修复破损区域较大的图像，对破损区域较小的结构图像也有显著的修复效果，而且优先权计算更加精准，搜索范围更加灵活，匹配块更加合理，适用范围更广，修复效果更好。

本文方法对于待修复区域过大或已知区域中不存在与待修复区域中相近似的块的图像，修复效果不是很理想。

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

［2］Masnou S，Model J.Level lines based disocclusion［C］／／International Conference on Information Processing，1998：259－263.

［3］Bertalmio M，Sapiro G，Caselles V，et al.Image inpainting［C］／／Proceedings of International Conference on Computer Graphics and Interactive Techniques，New Orleans，Louisiana，USA，2000：417－424.

［4］Chan T F，Shen J.Non－texture inpainting by curvaturedriven diffusions（CDD）［J］.Joumal of Visual Communication and Image Representation，2001，12（4）：436－449.

［5］Chan T F，Shen J.Mathematical models for local nontexture inpaintings［J］.SIAM Journal on Applied Math，2001，62（3）：1019－1043.

［6］Lu Xiaobao，Wang Weilan，Duojie Zhuoma.A fast image inpainting algorithm based on TV model［C］／／Preceeding of the International MultiConference of Engineers and Computer Scientists，Hong Kong，March，2010：1457－1460.

［7］Li Fang，Shen Chaomin，Liu Ruihua，et al.A fast implementation algorithm of TV inpainting model based on operator splitting method［J］.Computers and Electrical Engineering，2011，37：782－788.

［8］Li Fang，Bao Zheng，Liu Ruihua，et al.Fast image inpainting and colorization by，Chambolle’s dual method［J］.J Vis Commun Image R，2011，22：529－542.

［9］Lin Chang，Yu Chongxiu.New interpolation algorithm for image inpainting ［J］. Physics Procedia，2011，22：107－111.

［10］Li Qia，Shen Lixin，Yang Lihua.Split－bregman iteration for framelet based image inpainting［J］.Appl Comput Harmon Ana，2012，32：145－154.

［11］Efros A，Leung T.Texture synthesis by non－parametric sampling［C］／／Proc Int Con Computer Vision，Kerkyra，Greece，September，1999：1033－1038.

［12］Criminisi A，Perez P，Toyama K.Object removal by exemplar－based inpainting［C］／／Proceedings of IEEE Computer Society Conference on Computer Vision and Pattern Recognition，Vol 2，2003：721－728.

［13］Criminisi A，Perez P，Toyama K.Region filling and ob－ject removal by exemplar－based image inpainting［J］.IEEE Transactions on Image Processing，2004，13（9）：1200－1212.

［14］Sarawut T S，Akinori N.Iterative gradient－driven patchbased inpainting［C］／／Ho Y S.PSIVT，2011：71－81.

［15］Wu X，Zeng W，Li Z.Exemplar－based image inpainting with collaborative filtering［C］／／Sixth International Conference on Image and Graphics，Hefei，Anhui，China，Aug，2011：8－11.

［16］Tae－o－sot S，Nishihara A.Exemplar－based image inpainting with patch shifting scheme［C］／／17th International Conference on Digital Signal Processing，2011：1－5.

［17］Wang Minqin.A novel image inpainting method based on image decomposition［J］.Procedia Engineering，2011，15：3733－3738.

［18］Florinabel D J，Juliet S E，Sadasivam V.Combined frequency and spatial domain－based patch propagation for image completion［J］.Computers ＆ Graphics，2011，35：1051—1062.

［19］Sangeetha K，Sengottuvelan P，Balamurugan E.Combined structure and texture image inpainting algorithm for natural scene image completion［J］.Journal of Information Engineering and Applications，2011，1（1）：7－12.

［20］Huan Xiaoli，Murali B，Ali A L.Image restoration based on the fast marching method and block based sampling［J］.Computer Vision and Image Understanding，2010，114（8）：847—856.

［21］Li Shutao，Zhao Ming.Image inpainting with salient structure completion and texture propagation［J］.Pattern Recognition Letters，2011，32：1256－1266.

［22］黄淑兵，朱晓临，许云云，等.一种改进的基于纹理合成的图像修复算法［J］.合肥工业大学学报：自然科学版，2011，34（2）：313－316，320.

［23］刘丽萍.基于加权匹配的图像修复方法［D］.上海：上海华东师范大学，2009.