基于均方差快速增强的图像修复算法

杨筱平， 刘 勍， 董 忠， 李志锋， 王书文

(1. 天水师范学院物理与信息科学学院，甘肃 天水 741001；2. 天水师范学院化学工程与技术学院，甘肃 天水 741001；3. 西北民族大学电气工程学院，甘肃 兰州 730030)

基于均方差快速增强的图像修复算法

杨筱平1， 刘 勍1， 董 忠1， 李志锋2， 王书文3

(1. 天水师范学院物理与信息科学学院，甘肃 天水 741001；2. 天水师范学院化学工程与技术学院，甘肃 天水 741001；3. 西北民族大学电气工程学院，甘肃 兰州 730030)

在分析几种关键图像修复算法的实现原理、适用性及其优劣的基础上，针对目前图像修复算法可能存在适用性有限、优化修复算法中存在的算法复杂度较高或者未考虑破损图像的结构信息的情况，提出了一种基于数据融合的加权均方差快速增强图像修复算法，并将其应用于壁画和自然图像的修复实验中。通过系统仿真实验证明，在修复强结构纹理自然图像和壁画时该方法能紧密结合图像结构信息进行有效地修复，同时，其适用性在原有的基础上有所提高。

数据融合；均方差；图像修复；算法

图像修复(image inpainting)是图像处理、计算机视觉和计算机图形学领域研究热点之一，其目的是利用算法对图像中缺失部分、多余目标进行修复和去除，从而使图像看上去自然合理，不留修复痕迹。近年来，图像修复技术除了用于旧照片复原外，还应用于影视特效制作和文物保护等领域。文物壁画是传承古代文明的主要载体之一。它以绘画方式，通过二维空间构图，利用各种线条和色彩在墙壁上描绘出形态各异的人物画像和场景，故被称为“墙壁上的博物馆”，具有极高的史学价值、考古价值和艺术价值。许多壁画因常年暴露在外界环境中而严重受损，出现画面裂隙、层状剥落、酥粉、起甲、空鼓、烟熏黑及大面积的生物病害等物理现象。为了保护和修复这些壁画，国内外研究人员致力于数字化图像修复探讨研究中，壁画修复技术也得到快速发展，如：基于样本块的敦煌壁画修复、颜色对比度增强和空白纹理合成的古画修复等[1-2]。这些算法尽管利用破损区域周边信息修复破损区域，可是对于较大范围的色变壁画则无法修复或者修复有误。对此采用了GrabCut分割和自动采样色彩传递算法[3]。在目前广泛流行的几种关键图像修复算法(Criminisi等[4]提出的基于样本块纹理合成算法、Cheng等[5]提出的改进优先权的纹理合成算法、Wang和Xu[6]提出的基于D-S数据融合优先权改进算法)的实现原理、适用性及其优劣的基础上，本文提出了一种加权均方差(meanSquared error，MSE)模型快速增强的图像修复算法。通过修复实验表明，该算法首先能紧密结合图像结构信息快速准确地找到相匹配的样本块；其次，其适用性有所提高，不仅可以修复强结构纹理自然图像，还可以修复强结构纹理壁画。

1 几种图像修复算法比较

1.1 文献[4]、文献[5]和文献[7]算法对于自然图像修复效果比较

为了对文献[4]、文献[5]和文献[7]算法的性能进行分析，选用了自然图像中不同类型图像——大块单一纹理破损图像、大块直线型结构和纹理破损图像以及不同纹理破损图像进行修复验证。其修复效果分别如图1~3所示。

图1 针对大块单一纹理的自然图像修复

图1是对大块单一纹理破损的自然图像修复实验图，图1(c)中有一小块破损区域修复有误。经系统仿真实验和图 1(f)得出，该误修原因是迭代次数从 350~440次优先权值趋近于 0而随机修复造成的。图1(d)中有一块比图1(c)稍大点的破损区域修复有误。从图1(g)得出：该误修原因是在修复过程中该算法优先权值不稳定、迭代次数比图1(f)减少了40次以及样本块匹配错误造成的。图1(e)修复效果较图1(c)和图1(d)满意。从图1(h)得出：文献[7]算法在图像修复过程中优先权值稳定，且其迭代次数为640次。这3种图像修复算法对于大块纹理自然图像修复的实验结果证明：文献[7]算法较其他2种算法优越。

图2是针对大块直线型结构纹理破损的自然图像修复实验图，从图2(c)中可以看出纹理部分修复有误，但结构部分修复较为合理。图2(d)中纹理部分修复自然、完整，不留修复痕迹，而结构部分修复不太合理。图2(e)中纹理部分修复效果较好，结构部分修复合理、完整。从3张修复图对比可知，文献[7]算法对大块直线型结构纹理自然图像修复优于其他2种算法。

图 3是针对不同纹理破损自然图像修复实验图。从图3(c)~(e)可以看出，图3(c)和图3(d)修复较为自然，但从视觉心理学角度分析其强结构纹理部分修复有误。图3(e)虽然修复效果不太满意，尤其对于强结构纹理区域的图像修复不太完整。但从视觉心理学角度分析其 2种不同纹理修复都较为合理。这说明3种算法在修复强结构纹理的图像方面都不太满意，有待进一步改进。

图2 针对大块直线型结构纹理的自然图像修复

图3 针对不同纹理的自然图像修复

1.2 文献[4]、文献[5]和文献[7]图像修复算法异同及其优劣

结合上述修复实验，研究人员进一步对文献[4]、文献[5]和文献[7]图像修复算法的异同及其优劣进行分析比较。文献[4]提出的算法利用纹理生成方法中的思想，在修复结构特征的同时修复纹理信息。但在纯纹理破损区域修复方面却存在一定的缺陷，而且在图像修复过程中，该算法的优先权值有可能为 0而导致修复结果有误。文献[5]提出的算法对Ciminisi算法做了改进，改进后的算法优先权值很难趋近于0。并且修复纹理图像时，其修复效果较为逼真、完整。但其修复大块直线型结构图像时，修复结果出现了明显的不连续现象，同时，其优先权值表现出不稳定性。为此，文献[7]中对文献[5]算法做了改进，同时，将其用于壁画修复实验中。文中再次将其应用于自然图像修复。多次实验表明：文献[7]的算法不但稳定，而且很好地继承了文献[4]和文献[5]算法的优势。但是，这3种算法都具有贪婪性，存在错误信息传递的问题，难以做到全局最优，同时，一旦一个破损块被合成修复，就无法获得重修。本文相对于这些算法的基本思想做一比较分析，企图去探究出较好的算法。目前几种关键图像修复算法分析如表1所示。

表1 文献[4]、文献[5]和文献[7]图像修复算法对照表

2 改进的图像修复算法

2.1 对文献[7]算法的改进及实现原理

从图1~3中的修复图可知：文献[7]算法能够修复纹理、大块直线型结构纹理及不同纹理破损的壁画和自然图像。并且其修复效果明显优于其他2种算法。因此，文献[7]算法的适用性和优越性都有所提高和增强。然而，在修复强结构纹理破损区域的图像(如图 3)时，文献[7]算法就存在修复效果欠佳的现象，与此同时，在所有图像修复实验中其运行机时最长。从表1可知：文献[7]和其他2种算法在修复图像过程中采样方法相同，都是通过公式计算样本块 Ψq像素颜色值，并在未破损区域Φ中找出最接近于目标块 Ψp(优先级最高)的一个样本块 Ψq。

可以推断，在未破损区域Φ中单凭像素颜色值找到的匹配样本块很多，而从中找出纹理结构最匹配的一个样本块 Ψq实属不易，在这种情况下，许多图像纹理结构修复效果欠佳。从图3可以看出，图像破损区域不仅是纹理和强结构纹理2种破损类型共存，而且这2种纹理的像素颜色值还较为接近。在这种复杂图像修复过程中，算法单一地计算像素颜色值并找匹配的样本块就容易出错。这就造成图 3(c)~(e)修复有误的原因。在此基础上，为了减小图像修复算法的计算复杂度并提高图像修复效果，引进加权均方差计算像素点的颜色值，在指定窗口范围内寻找最佳样本块的方法。

对文献[7]算法改进的主要步骤为：

(1) 计算破损区域边缘∂Ω上以 p为中心 3×3的目标块Ψp优先权M(C)[7]：

其中，m1和m2是相同识别框架I上的2个基本概率赋值，A1,···,Ak和 B1,···,Bk分别为焦元，m1(A)2m(B)是一个归一化因子。

(2) 快速寻找最佳样本块：采用加权MSE方法寻找最佳样本块。加权MSE的公式为[8]：

其中，fk是目标块Ψp中每个已知像素点值，即 fk代表Φ ∩Ψ中的像素点值。以p点为中心，在X和Y方向分别以间距S进行稀疏采样，并以每个采样点为中心，构建w×w的窗口块(w=1.5S，s为2个像素间距离)。gk是窗口块中找到的最佳样本块 Ψq第k个像素点值，N是样本块像素总数。ϖk是窗口块的重要性权值，其公式[9]为：

式中，n是采样点个数，β为衰减系数，0<β<1，M(q)分别为p和q点优先权值， tk是窗口块被选中作为当前初始修复的先后序号，越早被选中，衰减越小。显然，权值计算公式保证了初始修复时优先级越高越早被选中的窗口块权值越大。

(3) 更新信任因子m(A)，对文献[7]改进算法的流程图如图4所示。

图4 文献[7]算法流程图

2.2 本文改进的图像修复算法实验结果

为了测试算法的有效性，用matlab实现了本文改进算法并在Intel双核CPU E6850 3 G上进行了实验。并在系统仿真修复实验中先后选择了2组图片进行实验修复，一组是含有不同纹理破损区域的自然图像，另一组是存在严重破损的复杂的不同纹理结构的壁画图像。

(1) 用改进后的图像修复算法分别对自然图像——图1(b)、图2(b)进行修复实验分析：本文改进的图像修复算法修复效果较为满意。从视觉心理学角度分析，其修复结果自然、合理、不留修复痕迹(如同图1(e)、图2(e))。尤其对图3(b)进行修复的效果比图3(e)要自然、合理一些，修复效果图如图5所示。同时，本文改进的图像修复算法计算复杂度有所减小，修复过程的运行机时也有所缩短。实验表明：对于具有强结构纹理的图像而言，基于像素颜色值的度量难以反映出其在结构纹理特征上的相似度，而在图像修复中，显著结构纹理特征的相似更加重要。本文算法不但考虑像素值的相似度，还考虑显著结构纹理特征的相似度。

图5 本文修复算法对大块不同纹理自然图像修复

(2) 用本文改进算法对多处不同纹理、大面积破损的敦煌壁画进行修复实验，其修复效果如图6所示。从图6(c)、图6(d)的效果对比可以得出：在大面积连续破损且其周边有效信息较少以及修复工作很难进行的情况下，本文改进算法修复效果基本达到了结构纹理的一致性，如图6(d)中左边第二束花朵结构纹理修复连续，中间花束下部纹理修复自然合理。因此，本文改进算法考虑了结构纹理信息后，具有较高适用性和优越性。

图6 针对多处破损敦煌壁画修复

3 结 束 语

本文首先对国内外几种图像修复算法的适用性、优缺点进行了详细讨论。在此基础上，针对目前图像修复算法可能存在适用性有限、优化修复算法中存在的算法复杂度较高或者未考虑破损图像的结构信息的情况，提出了多级合成的数据融合加权MSE图像修复算法，并将其应用于壁画和自然图像的修复实验中。经实验发现，本文改进算法在保证结构信息强、信任度高区域被优先修复的前提下，能够充分修复其纹理信息。与其他合成和最优化算法相比，本文算法在修复强结构纹理图像时更好地保持了纹理和结构的整体一致性，其适用性也有所提高，修复效果也优于其他修复算法，同时，其运行机时也比文献[7]算法短。

[1] PeiS C, Zeng Yichong, Chang C H. Virtual restoration of ancient Chinese paintings using color contrast enhancement and lacuna textureSynthesis [J]. IEEE Transactions on Image Processing, 2004, 13(3):416-429.

[2] 杨筱平, 王书文. 基于马尔可夫采样的敦煌壁画修复[J].计算机应用, 2010, 30(7): 1835-1837, 1840.

[3] 杨筱平, 王书文, 贾建芳, 等. 基于GrabCut分割和自动采样的敦煌壁画色彩修复[J]. 兰州理工大学学报, 2010, 36(3): 114-117.

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

[5] Cheng Wenhuang, Hsieh C W, LinShengkai, et al. Robust algorithm for exemplar-based image inpainting [EB/OL]. [2009-10-13]. http://graphics.csie.ntu. edu.tw/media/publications/Cheng-2005-RAE.pdf, 2005.

[6] WangShuwen, Xu Yongsheng. Improvement of priority computation in exemplar-based image inpainting base on D-S evidence theory and TVModel [C]//Proceedings of the 2nd International Congress on Image andSignal Processing. Washington D C: IEEE ComputerSociety Press, 2009: 1-3.

[7] 杨筱平, 王书文. 基于优先权改进算法的敦煌壁画复杂破损区域修复[J]. 计算机辅助设计与图形学学报, 2011, 23(2): 1-6.

[8] Anupam, Goyal P, DiwakarS. Fast and enhanced algorithm for exemplar based image inpainting [C]//2010 Fourth Pacific-RimSymposium on Image and Video Technology. Nanyang Technological University,Singapore: IEEE ComputerSociety Press, 2010: 325-330.

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

Fast and Enhanced Algorithm ForMeanSquared Error Based on Image Inpainting

Yang Xiaoping1, Liu Qing1, Dong Zhong1, Li Zhifeng2, WangShuwen3(1. College of Physics and InformationScience, Tianshui Normal University, Tianshui Gansu 741001, China;
2. College of Chemical Engineering and Technology, Tianshui Normal University, Tianshui Gansu 741001, China; 3. College of Electrical Engineering, Northwest University for Nationalities, Lanzhou Gansu 730030, China)

On the basis of analysis ofSeveral key image inpainting algorithms about implementation principle, applicability andSuperiority, considering their limited applicability, higher complexity and failured to take into account theStructure information of damaged images, a new faster inpainting algorithm usingStructure and texture optimization was proposed, which is based on the fastMarchingMethod for weightedMeanSquared error and data fusion of Dempster-Shafer evidence theory applications. This technique can be used in reconstruction of damaged portions of ancient painting and also in removing entire objects from natural image. Through repairing theMurals and natural images, the effectiveness of the proposed algorithm was verified byMeans of image completion andSystemSimulation experiment. The proposed algorithm considers theStructure information, achieves better repairing results and improves applicability.

data fusion;MeanSquared error; image inpainting; algorithm

TP 391

A

2095-302X(2015)02-0233-05

2014-04-16；定稿日期：2014-10-06

国家自然科学基金资助项目(61461046)；甘肃省高等学校基本科研业务费资助项目(2050205)；天水市中青年科技支撑资助项目(TSK1201)；天水师范学院中青年教师科研资助项目(TSB1108)

杨筱平(1976–)，女，甘肃庆阳人，讲师，硕士。主要研究方向为图像处理、信号处理等。E-mail：xpyangtsnu@163.com