基于显著结构重构与纹理合成的图像修复算法

朱晓临， 陈晓冬， 朱园珠， 陈 嫚，李雪艳

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

图像修复大体上可分为两类：一类是针对小尺度缺损的基于结构的算法[1-10]；另一类是针对基于大面积破损的纹理合成算法[11-19]。

近年来，人们试图找到一种对待修复域较大且结构相对复杂的图像的综合修复方法；此类算法尚属起步阶段。

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

早在2003年，Bertalmio等[22]率先提出了一种对结构和纹理同时进行修复的方法。该算法主要包含3个步骤：把图像分解为结构图像和纹理图像；对结构图像部分使用基于结构的修复方法进行修复；对纹理图像部分使用纹理合成的方法进行修复；然后进行合成。

2008年，邵肖伟等[23]提出一种基于Poisson方程的分离型修复算法，与文献[22]相仿，其结构图像使用 Laplacian 算子先强化结构图像的结构信息，随后对 Laplacian 场进行修复处理，再使用 Poisson方程对其进行重建；此法有一定成效，但难以克服大面积破损的待修复图像的修复问题，且修复后的图像会有明显的平滑锐化痕迹，导致一定程度的失真。

本文对既有显著结构同时又包含丰富纹理的待修复图像进行了修复尝试，考虑到结构修复算法及纹理合成算法各自的优点，以及显著结构对图像修复的巨大影响，提出基于显著结构重构与纹理合成的图像修复算法。算法先利用形态学算子剥离待修复图像中细小结构与大块区域；然后利用快速结构修复算法对图像进行处理；再利用插值对待修复图像进行显著结构重构；最后利用基于改进优先级的加权匹配图像修复算法进行后续修复。实验结果表明，与传统算法相比，本文的算法修复效果更好，耗时更少。

1 Criminisi算法简介

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

图1 Criminisi算法示意图

Criminisi算法的要旨在于考虑了待修复区域的修复顺序，提出了按优先级进行修复的思路。取

作为决定修复顺序的优先级。其中np是待修复区域Ω的边界δΩ上点p处的法向量，∇Ip⊥是已知区域Φ的边界的梯度向量的垂直向量（即等照度线方向），α是标准归一化因子（典型的灰度图像中取α=255）：

C ( p)称为置信项，即填充块中已知信息所占的比例；D(p)称为数据项，即结构信息；初始时，对∀p∈Ω，置信项C(p)=0；对∀p∈I-Ω时，置信项C(p)=1。Ψp表示以p点为中心的小块，Ψp表示Ψp的面积。

根据预先定义好的优先级，在待修复域的边界δΩ上选取一点p，然后选择一个以p点为中心的小块Ψp，即具有最高优先级的待修复块；再从已知区域Φ中寻找与Ψp最匹配的块。若Ψqˆ是已知信息区域中与Ψp最匹配的块（通常情况下，Ψqˆ应完全包含在已知区域Φ中），则分别是像素和与之对应的像素的灰度值。对于彩色图像，其像素灰度可由其对应像素的R、G、B的平均值代替。找到Ψqˆ之后，将Ψqˆ中相应的图像信息拷贝至Ψp∩Ω的位置，并更新边界δΩ，重复上述过程直至Ω为空集。

2 本文的算法

2.1 改进优先级和加权匹配块

Criminisi合成算法的两大关键要素是：①优先级的确定；②匹配块的选择。

2.1.1 改进优先级

针对第1个要素，因为式(1)中数据项D(p)可能为零，所以可能导致修复发生偏差，如图2所示。为此，文献[24]等对此做了改进。

本文在文献[13]的基础上，增加考虑了图像中对优先级有较大影响的显著边缘的作用，在优先级的计算项中增加考虑：

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

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

（3）其他突出的显著边缘线对优先级的影响。

即在优先级P(p)的计算中增加了边缘项E ( p)(edge term)，改进后的优先级P(p)为

其中，λ1、λ2、λ3是非负常数。C(p)和D(p)的表达式与式(2)相同。E(p)定义如下其中，Ep是显著边缘。

显然，E(p)的确定是至关重要的。显著边缘顾名思义是图像中十分明显且特别突出的边缘特征，若能精确地提取E(p)，则能对修复效果起到明显改善作用。而现有的边缘提取算法所提取的边缘特征几乎包含了整幅图像所有边缘特征信息，因此需要剔除哪些不期待出现的的冗余边缘特征。为此，应当做好以下几方面，以确保能获得无冗余的显著边缘特征。

图2 Criminisi算法修复示例

首先对图像进行深度去噪，这样，图像中的噪声点以及那些结构相似区域（即弱边缘区域）就会被逐步平滑，然后对所得到的图像进行边缘检测时，便只会检测出图像中保留下来的显著边缘特征；同时，为了避免因深度去噪对图像边缘可能产生的影响，保证得到的显著边缘精确性，本文利用曲率的知识，计算出图像各像素点的曲率分布图，并结合原始图像的边缘检测结果，以及通过深度去噪后的边缘图进行融合，从而最终达到期待的显著边缘特征图E(p)，再按式(5)计算优先级。

2.1.2 加权匹配块

针对Criminisi合成算法的第2个关键要素，在充分考虑图像各像素点的干扰机制及边缘项E ( p)的视觉影响作用情况下，需对块的匹配过程进行更为合理的改进，通过反复试验，提出新的匹配块控制权因子

下节的实验结果验证了本文提出的权因子的合理性。于是与Ψp最匹配的块为

2.1.3 显著边缘重构

传统算法通常是在整幅图像上进行搜索，再寻找匹配块，这样可能因为偏差延续等问题导致视觉上原本不太匹配的块被填充在待修复区域，同时耗时多。为此，人们大多采用以下两种区域搜索方法：一是局部搜索；二是分块修复。

选择局部搜索与分块修复虽然能降低修复耗时，一定程度上保证算法的效果，但有时难免会因搜索域限制难以找到合适的匹配块，或是因分块对完整的显著结构造成破坏，这样便不能保证修复后图像中显著结构在视觉上的完整性。

为此，本文利用插值对显著边缘特征预先进行重构。本文算法不但能对图像中直线型特征进行重构，而且还能对曲线结构的显著特征进行重构，从而很好地避免了分块修复对显著结构完整性造成的破坏。

在对重构后的图像进行修复时，本文采用全局与局部相结合的方法来进行修复。首先对重构后显著边缘与待修复域相交处进行修复。因为此处特征变化剧烈，所以采用全局搜索；待图像中变化剧烈的地方修复完成，剩余的部分变化相对比较平缓，故而后续修复只需采用局部搜索便可以确保修复效果、省时。

2.2 快速结构修复

虽然纹理修复算法可以修复大面积破损的图像，但是在一幅图像中，除大破损区域外，可能还有诸多纷乱无序的小尺度破损。如果仅利用纹理修复技术对此图像进行修复，一方面，由于小破损域也需要利用块搜索匹配的思想，必将浪费很长的时间；另一方面，由于破损处过多，有时难以找到一个完全包含在已知区域内的块来对图像进行填充，必然会导致修复效果发生严重偏差。为此，本文预先利用快速结构修复算法对细小破损处进行修复，然后再利用纹理合成算法进行大面积填充，实验结果证明了改进算法的优越性。

2.3 算法步骤

综上，本文提出一种基于显著结构重构与纹理合成的图像修复算法。该算法步骤如下：

首先，人工选取待修复区域或待移除的目标，并将待修复域置为纯色；然后根据需要进行适度的掩码膨胀找到恰当的边界，再将待修复区域的边界标记为设置。执行如下步骤（初始i=0）：

（1）根据形态学算子对待修复图进行掩膜膨胀与腐蚀，剥离大块与小线条结构；

（2）找出剥离后的线条结构的提取掩码，利用快速结构修复算法修复；

（3）找出剥离后的待修复大块区域的边界δΩi，如果 Ωi=Ø，退出循环，修复结束；

（4）E(p)项的提取；在E(p)上用Cubic Spline完成显著结构重构；

（6）找出具有最大优先权值的待修复区域块Ψp，即；

（7）根据式(6)、(7)、(8)、(9)、(10)找出最匹配的块Ψˆq∈Φ；

（8）将Ψˆq中对应的图像信息复制到Ψp∩Ω；

（9）令i=i+1，重复步骤(3)～(8)。

3 实验结果

本文实验用MATLAB 7.10作为工具，在Intel酷睿I3双核处理器(2.6 GHz)、2 G内存的PC机上实现。图3～5是文献[24]及与本文算法之间修复结果的比较。

图3第一组，从修复效果上来看，本文算法所得的修复效果(d1)不仅满足视觉上要求，相较其他修复结果(b1)和(c1)，在河堤与河面交汇处也更为自然流畅，同时也大大缩短了修复时间（见表1）。图3第二组，文献[24]算法与 Criminisi算法的修复效果与本文算法相比差别比较明显；其中图(b2)和(c2)存在严重的偏差延续情况，出现大面积的崩溃。

从图4的两组结果来看，本文算法与传统算法相比，修复结果差异相当明显。本文算法修复效果(d1)和(d2)，具有更强的鲁棒性，保证了相对复杂的破损图像的修复效果。而文献[24]算法与Criminisi算法的修复效果图出现了明显的偏差延续状况，图像右下角都不同程度出现了较为明显的断痕，而且所耗时间为本文算法的7倍左右（见表1）。

同图4的两组结果相似，本文算法具有良好的鲁棒性，修复效果也明显好于传统算法。Criminisi算法与文献[24]算法修复结果在围墙处存在明显不衔接，甚至破损的现象；而本文算法修复后的图像视觉效果却自然流畅，而且耗时较之其他算法要少（见表1）。

表1列出了图3～5，Criminisi算法、文献[24]算法和本文算法的修复时间的比较。

图3 本文算法与其他算法修复结果的比较

图4 本文算法与其他算法修复结果的比较

图5 本文算法与其他算法修复结果的比较

表1 不同算法修复时间比较(s)

4 结 束 语

传统算法在对修复域面积较大且结构相对复杂的图像进行修复时，难以克服修复效果上的偏差以及耗时问题。本文针对上述问题提出了基于显著结构重构与纹理合成的图像修复算法。算法将形态学、数学、图像自身的特征、以及人类视觉等基本原理有机地结合起来，为结构复杂纹理丰富的破损图像修复提供了一种解决思路，并通过实验验证了思路的可行性，效果的优越性。

后面的工作将致力于显著特征的自动化重构问题，同时对修复中出现的其他问题，进行进一步探讨。

[1] 张红英,彭启琮. 数字图像修复技术综述[J]. 中国图象图形学报,2007,12(1): 1-10.

[2] Masnou S,Model J-M. Level lines based disocclusion[C]//Image Processing,1998. ICIP 98. Proceeding. 1998,International Conference on,1998,3: 259-263.

[3] Bertalmio M,Sapiro G,Caselles V,Ballester C. 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 Jianhong. Non-texture inpainting by curvature-driven diffusions (CDD) [J]. Journal of Visual Communication and Image Representation,2001,12(4): 436-449.

[5] Chan T F,Shen Jianhong. Mathematical models for local nontexture inpaintings [J]. SIAM Journal on Applied Math,2001,62(3): 1019-1043.

[6] Lu Xiaobao,Wang Weilan,Duo Jie,Zhuo Ma. A fast image inpainting algorithm based on TV model [C]//Proceeding of the International MultiConference of Engineers and Computer Scientists. Hong Kong,March,2010: 1457-1460.

[7] Li Fang,Shen Chaomin,Liu Ruihua,Fan Jinsong. A fast implementation algorithm of TV inpainting model based on operator splitting method [J]. Computers and Electrical Engineering,2011,37(5): 782-788.

[8] Li Fang,Bao Zheng,Liu Ruihua,Zhang Guixu . Fast image inpainting and colorization by Chambolle’s dual method [J]. Journal of Visual Communication and Image Representation,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].Applied Computional Harmonic Analysis,2012,32(1): 145-154.

[11] Efros A A,Leung T K. Texture synthesis by non parametric sampling [C]//Computer Vision 1999. The Proceedings of the Seventh IEEE International Conference on,Kerkyra,Greece,1999,2: 1033-1038.

[12] Criminisi A,P´erez P,Toyama K. Object removal by exemplar-based inpainting [C]//Madison,Wiscons Proceedings of IEEE Computer Society Conference on Computer Vision and Pattern Recognition,2003:721-728.

[13] Criminisi A,Perez P,Toyama K. Region filling and object removal by exemplar-based image inpainting [J].IEEE Transactions on Image Processing,2004,9(13):1200-1212.

[14] Tae-o-sot S,Nishihara A. Iterative gradient-driven patch-based inpainting [C]//Y-S Ho(Ed),PSIVT 2011,Part II ,LNCS,2011:71-81.

[15] Wu Xinran,Wei Zeng,Li Zhenzhou. Exemplar-based image inpainting with collaborative filtering [C]//Image and Graphics (ICIG),2011 Sixth International Conference on,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 Dr 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 Beddhu,Ali Adel 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] Bertalmio M,Vese L,Sapiro G,Osher S. Simultaneous texture and structure image inpainting [J]. IEEE Transaction on Image Processing,2003,12(8):882-889.

[23] 邵肖伟,刘政凯,李厚强. 一种基于 Poisson 方程的分离型图像修复方法[J]. 电路与系统学报,2008,13(6):1-6.

[24] 黄淑兵,朱晓临,许云云,朱 坤. 一种改进的基于纹理合成的图像修复算法[J]. 合肥工业大学学报(自然科学版),2011,34(2): 313-316,320.