基于区域分割和均方误差改进的图像修复算法

李光耀，耿瑞全，谭云兰2,，肖 莽

基于区域分割和均方误差改进的图像修复算法

*李光耀1，耿瑞全1，谭云兰2,1，肖 莽1

（1.同济大学电子与信息工程学院，上海 201804；2. 井冈山大学电子与信息工程学院，江西，吉安 343009)

基于样本块的Criminisi图像修复算法在搜索匹配块时，使用全局搜索并用均方误差（sum of squared differences）来衡量样本块差异。该方法存在搜索范围过大，效率较低，仅考虑颜色的差异，容易导致修复结果边界错位等不足，本文提出了一种基于区域分割和均方误差改进的图像修复算法。为了提高样本块匹配速度，先采用区域分割法分割整个图像区域，使待修复样本块只在对应区域内搜索。在比较样本块差异时，本文算法对颜色差异、纹理差异、曲线特征差异进行了加权综合，从而保证了修复后图像在颜色和纹理上均与已知区域保持一致，解决了Criminisi算法效率低且容易出错等问题。实验结果表明本文算法修复结果在执行效率、视觉效果上要比Criminisi算法好。

图像修复；区域分割；均方误差；纹理合成

0 引言

图像修复是计算机图形学中的一个研究热点，具有广泛的应用前景。图像修复是为了让破损的图像恢复视觉上“合理”而且“完整”[1]。从视觉心理学出发，向内按一定的方向进行扩展延伸、连接边界、合成纹理，以达到视觉上的连通性和一致性。其目的是研究和解决如何更好地实现检测图像上的受损部分，并根据受损图像周围的有效信息自动进行恢复。从数学角度来看，图像修复就是要根据待修补区域周围的信息将图像填充到待修补区域中。如图1所示，设为一副图像，为信息丢失的待修复区域，为图像中完好的可利用的图像部分。图像修复的问题即用已知信息填充区域，使整幅图像取得良好的视觉效果，图1（c）为修复后的结果。

图1 (a) 原图，(b) 修复掩膜图（黑色部分为修复区域），(c) 图修复结果。

图像修复算法大体分为两大类，基于变分偏微分方程的算法和基于纹理合成算法。基于纹理合成算法[3]把待修复图像的已知区域作为纹理样本，对于丢失区域基于纹理合成生成新的图像块，以解决基于变分偏微分方程修复算法出现模糊的问题。基于纹理合成的算法是对已知图像块进行采样，对丢失的像素及相邻像素组成的块从样本中查找与之最相似的匹配块来修补，该迭代过程反复进行直到所有丢失区域被修复完。但是这种方法很难保持图像的结构信息，Criminisi等人[4]从人工依据图像结构信息依次修复图像中得到启发，即对于修复图像中的每个部分的修复先后顺序非常关键，因此对待修复区域边界上的像素计算其修复优先级，从而确定其修复顺序，使得图像修复质量得到质的提升，该算法在解决图像修复问题中具有里程碑意义。随后，研究人员基于Criminisi算法提出了多种改进算法。Tang等人[5]通过减少最佳匹配块的搜索范围来加快算法的运行，同时改进了匹配准则来避免计算错误。Nie等人[6]对Criminisi算法进行改进，对构成优先权的置信项和数据项进行了归一化，这样保证了两者对优先权的影响程度一致，同时修正了块之间差异的计算方法。Wong等人[7]采用线性加权的方式合成最佳匹配块填充待修复块。肖春霞等人[8]提出了一种结合图像细节特征的全局优化纹理合成算法，利用非线性分解方法获取纹理细节作为特征图，将其作为纹理图像一个新的信息通道来引导纹理合成。Xu等人[9]借助稀疏表示的概念指导修复顺序并合成最佳匹配块，大大提高了修复质量。刘建明等人[10]则采用组合样本块匹配度量来加强结构的传播也得到不错的效果。

本文分析了Criminisi算法搜索效率和修复效果方面的不足，本文提出了一种基于区域分割和均方误差改进的图像修复算法。

1 Criminisi基于样本块纹理合成修复算法

Criminisi等[4]采用一种基于样本块的纹理合成修补算法，其实质是使用纹理合成的方法来移除图像中的物体，取得了较好的修复效果。Criminisi算法由优先权计算、搜索和复制3步组成。具体方法如下：

其中：为的信心因子项，是的数据因子项，计算方法如下：

图2 优先权符号注释图

3）复制：将最佳匹配块复制到中处于待修复区域内的部分。

Criminisi算法由于引进了修复次序优先权，算法取得了很好的修复效果。但同时由于使用整个块的复制填充而不是单个像素点，算法的速度相对更快，仍存在一些不足。首先，搜索时在整个已知区域内搜索，该过程非常耗时。其次在搜索最佳相似块时使用均方误差（SSD）来衡量样本块差异，仅考虑了两个样本块之间颜色差异，修复结果有时存在边界错位的情况。

2 区域分割和均方误差改进的图像修复算法

针对Criminisi算法上述两方面的不足，本文首先分割整个图像区域，使待修复样本块只在对应区域内搜索，提高了算法的执行效率；同时在比较样本块差异时，对颜色差异、纹理差异、曲线特征差异进行了加权综合，弥补了单纯考虑颜色误差的不足，保证了修复结果在颜色和纹理曲线上的一致性。

2.1 图像区域分割

Criminisi算法搜索样本块时采用全局搜索，样本量巨大，非常耗时。本文首先对待修复图进行区域分割，搜索匹配块时只在对应区域，而不是全局搜索，提高了算法的执行效率。

在纹理合成的过程，块搜索被限制在当前待修复样本块覆盖的相关区域中：

图3 区域分割图

2.2 均方误差改进

Criminisi算法在搜索最佳匹配块时使用均方误差SSD，只考虑了两个样本块之间颜色差异，导致修复结果有时存在边界错位的情况。受基于内容的图像检索（CBIR）的启发，在搜索最佳匹配块时，本文使用在比较样本快差异时，除了颜色信息，还包含纹理、曲线特征方面的差异，其中颜色差异描述了两个样本块局部颜色成分差异，纹理差异描述了两个样本块的局部灰度级成分差异，而曲线特征描述了显著结构的几何差异性，这三个方面能简洁且有效地描述样本块之间的差异，分别在下面论述。

2.2.1 颜色差异

2.2.2 纹理差异

2.2.3 曲线特征差异

除了颜色和纹理差异，本文考虑样本块曲线特征差异。通过上述区域分割图，可以得到的曲线信息图，从而进行曲线级别的匹配，衡量两个样本块的曲线特征差异。

其中为对应曲线的数目。

综合式（7）（8）（10），改进的均方误差综合加权计算公式如下：

2.3 本文算法步骤

本文提出了一种基于区域分割和均方误差改进的图像修复算法。主要分成两个步骤：区域分割和最佳匹配块的生成。初始时，人工选择带修复区域，算法流程见图4。其中从带修复块相关区域中选择最相似块步骤中使用改进的均方误差。

3 实验结果与分析

3.1 实验修复效果对比

本实验首先使用区域分割算法得到分割图和曲线信息图，如图5、图6。其中：图5大小416*316，算法耗时1.05 s，图6大小为206*308，耗时0.37 s。

本实验选取了一些比较的图像，样本块大小设定为9*9。图像的修复结果以尽可能合理为目的，而非与原图像一致。图7-9为本文算法和Criminisi算法修复结果比较。图7：（c）中修复结果红色圈出的部分海平面存在错位，蓝天部分由于未对搜索区域进行限制，结果中存在大量白云，不够合理。（d）中修复结果存在少量瑕疵，但相比较更为合理；图8：（c）中修复结果的河岸交界处出现了多余块，屋顶线结构也出现断裂，这些在（d）中都得到了改善；图9：（c）中红圈内修复结果应该为山和树木的部分被填充为房屋，而（d）中更加合理。

图4 本文算法步骤

综上，Criminisi 算法的修复结果存在明显的边界不连续和错位现象，同时存在大量的冗余图像块。而使用本文算法由于限制了搜索区域，改进了均方误差，修复结果相对较好。

图5 (a)待修复图 (b)区域分割图 (c)曲线信息图

图6 (a)待修复图 (b)区域分割图 (c)曲线信息图

图7 (a)原图 (b)待修复图 (c) Criminisi 修复结果 (d)本文算法修复结果

图8 (a)原图 (b)待修复图 (c) Criminisi 修复结果 (d)本文算法修复结果

图9 (a)原图 (b)待修复图 (c) Criminisi 修复结果 (d)本文算法修复结果

3.2 执行效率对比

表1对Criminisi算法和本文算法作具体的比较，表中数据表明本文算法由于限制了搜索区域，显著地缩短了修复时间，提高了图像修复的效率。

表1 Criminisi算法和本文算法执行效率比较

4 总结

本文提出了一种基于区域分割和均方误差改进的图像修复算法。该方法在比较样本块相差异的时候不仅考虑了它们之间的颜色差异，而且也整合了样本块间的纹理、曲线特征差异，保证了修复后图像在颜色和纹理上均与已知区域保持一致。同时采用区域分割，在搜索匹配块时只在对应区域内搜索，提高了算法的执行效率。实验结果表明，本文算法修复结果在执行效率、视觉效果上要比Criminisi算法好。本文算法也存在着其他不足：部分实验结果存在少量冗余图像块；算法对区域分割结果比较依赖，因此，如何有效地提高区域分割的质量、加强综合系数的感知，从而改进修复的效果是今后进一步研究的方向。

[1] Zhang H Y, Peng Q C. A survey on digital image inpainting[J]. Journal of Image and Graphics, 2007; 12(1): 1-10.

[2] Bertalmio M, Bertozzi AL, Ballester C, etal. Image inpainting [C]. Proceedings of the 27th Annual Conference on Computer Graphics and Interactive Techniques. New Orleans, Louisiana, USA: ACM Press, 2000: 417-424.

[3] Efros A, Leung TK. Texture synthesis by non-parametric sampling [C]. IEEE International Conference on Computer Vision, Greece, 1999: 1033-1038.

[4] Criminisi A, Perez P, Toyama K. Object removal by exemplar-based inpainting[C].In Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition (CVPR), 2003.

[5] Tang F, Ying Y T, Wang J, Peng Q S. A Novel Texture Synthesis Based Algorithm for Object Removal in Photographs [C]. In Proceedings of Ninth Asian Computing Science Conference, Chiang Mai, Thailand, 2004: 248-258.

[6] Nie D L M, Xiao S. Similarity based image inpainting method [C]. Proceedings of 12th international Conference on Multi-Media Modeling, Beijing: IEEE, 2006: 344-347.

[7] Wong A, Orchard J. A nonlocal-means approach to exemplar-based inpainting [C]. Proceedings of 15th IEEE International Conference on Image Processing, California: IEEE, 2008: 2600-2603.

[8] 肖春霞, 黄志勇, 聂勇伟, 等. 结合图像细节特征的全局优化纹理合成[J].计算机学报, 2009,32(6): 1196-1205.]

[9] Xu Z, Sun J. Image inpainting by patch propagation using patch sparsity [J]. IEEE Transactions on Image Processing, 2010, 19(5): 1153-1165.

[10] 刘建明，鲁东明.采用加权优化的图像修复[J]. 中国图像图形学报，2011,16(4):528-532.

[11] Liu M, Tuzel O, Ramalingam S, Chellappa R. Entropy rate superpixel segmentation[C]. CVPR, 2011.

[12] Chen J Q, Pappas T N, Mojsilovic A, et al. Adaptive perceptual color-texture image segmentation[J]. IEEE Trans, 2005，14 (10)： 1524-1536.

[13] Varma M, Zisserman A. Statistical approach to material classification using image patch Exemplars[J]. IEEE Trans. Pattern Anal. Machine Intell, 2009,13(11): 2032-2047.

Based region segmentation and improved sum of squared differences image completion algorithm

*LI Guang-yao1, GENG Rui-quan1, TAN Yun-lan2,1, XIAO Mang1

(1. College of Electronic Information and Engineering, Tongji University, Shanghai 201804, China; 2．School of Electronic Information and Engineering，Jinggangshan University，Ji’an，Jiangxi 343009，China)

Image inpainting is one of important and challenging research topics in computer graphics, video processing, and computer vision. It provides a strong tool for the reuse of captured images and photos. It also shows extensive applications in cultural heritage protection, special visual effects, image and video editing and virtual reality. The traditional Criminisi based patch image completion algorithms only consider the intensity difference when computing the difference within patches and search the most similar exemplar patches in the source region of image, the computation is too large. A new difference measure for completion is presented. This measure considers the intensity difference, texture difference and curve difference when computing the difference within patches. It successfully overcomes the drawbacks the general intensity difference method has, ensuring the content continuity within the textures and retaining perceptual coherence in synthesized texture and inpainted image. The experiment shows the result inpainted images using our algorithm are better than Criminisi algorithm, and the repair time also has a considerable decrease.

image completion; region segmentation; sum of squared differences; texture synthesis

O159.1

A

10.3969/j.issn.1674-8085.2013.06.010

1674-8085(2013)06-0044-07

2013-10-08；

2013-10-15

国家自然科学基金项目(60771065)

*李光耀(1965-），男，安徽安庆人，教授，博导，主要从事大规模城市建模与仿真、图形图像处理研究(E-mail: lgy@tongji.edu.cn)；

耿瑞全(1991-），男，安徽蚌埠人，硕士生，主要从事图形图像处理，机器学习等研究(E-mail: 871342796@qq.com);

谭云兰(1972-），女，江西新干人，副教授，博士生，主要从事虚拟现实,图像处理研究(E-mail:tanyunlan@163.com);

肖 莽(1982-），男，江西吉安人，博士生，主要从事图像处理研究(E-mail:122018922@qq.com).