基于改进Criminisi算法的图像修复

李爱菊，钮文良

北京联合大学，北京 102200

基于改进Criminisi算法的图像修复

李爱菊，钮文良

北京联合大学，北京 102200

1 引言

随着计算机图像技术的迅速发展，其在生物医学、工业生产、遥感测绘等领域得到了成功的应用。但是在图像拍摄和采集过程中，由于受到外界因素的干扰，不可避免会丢失部分信息，一些区域缺失，影响图像质量[1]。图像修复技术是指根据已知信息，对修复区域内丢失信息进行补充，提高图像在视觉上的真实性，已经成为图像处理领域的研究热点和重点[2]。

针对图像修复问题，学者们投入了大量的时间和精力进行相关研究，提出了一些图像修复算法，当前主要分为两类方法：基于非纹理图像修复和基于纹理修复方法[3]。基于非纹理的图像修复方法主要是利用待修复区域附近的已知信息，按一定的规则向待修复区域蔓延，如文献[4]提出的基于高阶偏微分的图像修复算法，文献[5]提出的基于整体变分（TV）模型的图像修复算法等，它们适合于小区域的图像修复，但如果待修复的区域比较大，难以获得比较理想的修复效果。文献[6]提出基于先验模型的图像修复算法，对于结构信息的图像，可以得到较好的修复效果，但是对于含有丰富纹理图像，修复效果较差。基于纹理综合的修复方法指利用块匹配选取合适的纹理块来修复，其中Criminisi算法是最为经典的纹理图像修复算法[7]，其首先从图像完好区域中寻找与待修复区域最匹配的像素块，然后将其填充到受损区域，修复效果较好。然而在实际应用过程，Criminisi算法存在一些不足，如出现马赛克效应和纹理混乱现象。为了克服Criminisi算法的不足，国内外一些学者在该算法的基础上，提出了一些改进Criminisi图像修复算法[8-11]，但是这些算法都存在各自的缺陷，如何提高图像修复效果，值得进一步研究。

为了获得理想的修复效果，针对Criminisi算法存在的不足，提出一种改进Criminisi算法的图像修复算法，并通过仿真实验测试算法的可行性和优越性。首先改进优先权计算方式找到最优待修复块，然后完善最优匹配块搜索策略，并找到最优匹配块，最后采用新的置信值更新方式以获得更为理想的修复效果，并通过仿真实验测试算法性能。结果表明，相对于Criminisi算法，改进Criminisi算法不仅得到了理想的图像修复效果，而且大幅度减少了修复时间，提高了图像的修复效率。

2 Criminisi算法

2.1 基本工作原理

Criminisi算法的工作原理如图1所示，其中，Ω表示破损区域，I是待修复图像，∂Ω表示破损区域的边界，点p为目标像素点，Φ表示样本区域，▽Ip是等照度线的切线方向，np是受损边界切线的法向量，φp是以p中心的目标块[12]。

图1 Criminisi算法原理

2.2 Criminisi算法的工作步骤

（1）计算优先权。先标记出待修复区域Ω，那么Φ=I-Ω，取以受损边缘上像素点p为中心的模版φp，计算受损边缘每个像素点的优先权，并按优先权排序，则优先权P(p)计算为：

其中，D(p)为数据项，C(p)为置信度，它们定义为：

（2）寻找最佳匹配块。计算当前边缘所有像素块的优先权，找出优先权最大的块φp作为当前的目标块，采用全局搜索的方法，将SSD作为匹配准则在未破损区域内搜索与待修补块相似度最高的匹配块。SSD匹配准则定义如下：

式中，d(φp，φq)是φp，φq对应已知像素点颜色RGB。

（3）更新置信度。每次修复的块都在待修复区域边缘上，修复区域边缘总是处在不断的变化中，因此有必要每完成一个纹理块的修复就对边缘进行更新。最高优先级的目标块被填充后，刚刚填充的像素点由受损区域变为样本区，置信度发生了变化，因此需要更新像素点的置信度，置信度更新为：

更新置信度得到一个新的边缘，图像的待修复区域发生了变化，边缘像素点的置信度也就发生了变化。重复上述三个步骤直到待修复区域Ω为空，则修复完毕。

综合上述可知，基于Criminisi算法的图像修复流程图具体如图2所示。

图2 Criminisi算法流程图

3 改进Criminisi算法

3.1 优先权的改进

作为Criminisi算法的第一步，待修复块优先权的判定至关重要，根据文献[13]中的实验结果，对式（1）改进，具体做法如下：

3.2 最佳匹配块搜索算法完善

在Criminisi算法中，由上至下、左到右的最优匹配块的搜索顺序，最终找到最优匹配块，然而在图像修复块的匹配过程中，会产生大量候选块，若找到最优匹配块与相差较远待修复块，那么对待修复块的已知像素点进行较好修复，其他部分修复效果差。为此，提出一种改进最优匹配块搜索策略，具体为：

（1）根据优先权值确定的当前待修复点。

（2）以当前待修复点为中心，顺序搜索到与其距离为n的匹配点。

（3）以这些匹配点为中心，生成候选块与待修复块做SSD计算。

（4）不断重复上述步骤，直到搜索完匹配区域为止。

3.3 置信值更新的改进

在Criminisi算法修改过程中，同等对待修补后的像素点和非破损区域的像素点，这与实际情况不相符，这样可能会破坏图像模板，对图像的修复结果产生不利影响。为了解决该难题，先设定一颜色阈值th，该阈值根据图像修复模板对应的SSD的值确定，具体改进方式为：

4 仿真实验

4.1 仿真环境

为了测试改进Criminisi算法的图像修复性能，在Intel酷睿i5 4570 CPU，RAM 4 GB，Windows XP的计算机上，采用VC++编程实现，为了使改进Criminisi算法结果具有可比性，采用标准Criminisi算法对比算法的性能，仿真对象为：Girl、Bungee和Grass图像[14]，原图和待修复图像具体如图3和图4所示。

图3 原图

图4 待修复图像

4.2 结果与分析

4.2.1 主观评价结果对比

分别采用改进Criminisi算法和Criminisi算法对图3的图像进行修复，结果如图5～7所示。

图5 Girl修复效果对比

图6 Bungee修复效果对比图

图7 Grass修复效果对比图

从图5～7可知，从标记方框可以明显看出，标准Criminisi算法修复后的图像中出现了严重的结构断裂以及不连续现象，但是改进Criminisi算法的视觉效果得到明显改善，这主要由于改进Criminisi算法在图像修复过程中，对优先权值进行改进，可以有效地保证结构信息较强的待修复块，并完善最优匹配块搜索策略以及置信值更新方式，提高了图像修复后的视觉效果。

4.2.2 客观评价结果对比

对图像修复算法性能的评价，除了采用主观评价外，通常还采用客观评价标准进行衡量。为了更进一步评价图像的修复质量，采用峰值信噪比（Peak Signal to Noise Ratios，PSNR）和计算时间对图像修复质量进行客观评价，它们结果分别如图8，9所示。对图8，9进行分析，可以得到如下结论：

（1）相对于Criminisi算法，改进Criminisi算法的计算时间相对减少，计算复杂度较低，提高了图像修复的效率，对比结果表明，改进Criminisi算法更加适合于图像的在线修复，应用范围更广，实用价值更高。

（2）相对于Criminisi算法，改进Criminisi算法修复后图像的信噪比大，修复效果更佳，这说明通过对Criminisi算法进行改进和完善，较好地克服了其不足，可以确保确修复后图像的视觉效果，改进Criminisi算法是一种性能优异、效率高的图像修复算法。

图8 修复后图像信噪比的对比

图9 图像修复时间的对比

5 结束语

针对Criminisi算法存在的缺陷，提出了一种改进Criminisi的图像修复算法，从优先权计算、最优匹配块搜索策略以及置信值更新等方面进行改进和完善，并进行了仿真对比实验。结果表明，改进Criminisi算法不仅能有效确保修复后图像的视觉效果，而且能有效地节约对应的修复时间，是一种性能更为优异的图像修复算法。

[1]Minh N，Martin V.The contourlet transform：an efficient directional multiresolution image representation[J].IEEE Transactions on Image Processing，2005，14（12）：2091-2106.

[2]林云莉，赵俊红，朱学峰，等.改进的纹理合成图像修复算法[J].计算机应用与软件，2010，27（10）：11-12.

[3]屈磊，韦穗，梁栋，等.快速自适应模板图像修复算法[J].中国图象图形学报，2008，13（1）：24-28.

[4]孟春芝，何凯，焦青兰.自适应样本块大小的图像修复方法[J].中国图象图形学报，2012，17（3）：337-341.

[5]Anamandra S H，Chandrasekaran V.Exemplar-based color image inpainting using a simple and effective gradient function[C]//Sargolzaei S.International Conference on Image Processing and Computer Vision，2010：140-145.

[6]Zhou Y T，Li L，Xia K W.Research on weighted priority of exemplar-based image inpainting[J].Journal of Electronics，2012，29（1）：166-170.

[7]代仕梅，张红英，曾超.一种基于样例的快速图像修复算法[J].图形、图像与多媒体，2010，29（22）：34-39.

[8]付绍春，楼顺天.基于区域纹理合成的图像修补算法[J].电子与信息学报，2009，31（6）：1319-1322.

[9]林胜华，汪继文，沈玉峰，等.利用邻域相似度的图像修复[J].计算机工程与应用，2010，46（7）：190-191.

[10]吴晓军，李功清.基于样本和线性结构信息的大范围图像修复算法[J].电子学报，2012，40（8）：1509-1514.

[11]张伟彬.基于修复顺序的图像修复算法[J].计算机工程与应用，2008，44（22）：195-196.

[12]陈卿，王慧琴，吴萌.基于纹理特征的自适应图像修复算法[J].计算机应用，2011，6（6）：1572-1574.

[13]Kwok T H，Sheung H，Charlie C.Fast query for exemplar-basedimagecompletion[J].IEEE Transactionson Image Processing，2010，19（12）：3106-3115.

[14]任澍，唐向宏，康佳伦.利用纹理和边缘特征的Criminisi改进算法[J].中国图象图形学报，2012，17（9）：1086-1091.

[15]Xu Z B，Sun J.Image inpainting by patch propagation using patch sparsity[J].IEEE Transactions on Image Processing，2010，19（5）：1153-1165.

LI Aiju,NIU Wenliang

Beijing Union University,Beijing 102200,China

A novel image inpainting method based on improved Criminisi algorithm to solve the defects of Criminisi algorithm which hardly yields unfavorable results and costs much inpainting time is proposed.The priority levels of the blocks are obtained and the optimal inpainted block is selected,and then the optimum matching block in the image is found by improving search method,and the confidence value is updated to obtain good inpainting results.The simulation experiments are carried out to test the performance.The experimental results show that compared with Criminisi algorithm,the proposed algorithm is effective in both guaranteeing the quality of repaired images and saving much more repairing time.

image inpainting;Criminisi algorithm;priority levels;image texture

针对Criminisi算法难以获得理想的修复效果，且存在修复时间过长等缺陷，提出一种改进Criminisi算法的图像修复算法。改进优先权计算方式找到最优待修复块，完善最优匹配块搜索策略，找到最优匹配块，采用新的置信值更新方式以获得更为理想修复效果，通过仿真实验测试算法性能，结果表明，相较于Criminisi算法，改进Criminisi算法不仅获得了较理想的图像修复效果，而且大幅度减少了修复时间，提高了图像修复的效果。

图像修复；Criminisi算法；优先级；图像纹理

A

TP919

10.3778/j.issn.1002-8331.1401-0419

LI Aiju,NIU Wenliang.Image inpainting based on improved Criminisi algorithm.Computer Engineering and Applications,2014,50（18）：167-170.

北京高等学校青年英才计划项目（No.YETP1766）。

李爱菊（1980—），女，讲师，主要研究领域：高效计算、大数据、并行处理、图形图像等；钮文良（1958—），男，教授，主要研究领域：网络通信、无线传感网等。E-mail：50310646@qq.com

2014-01-26

2014-03-21

1002-8331（2014）18-0167-04