基于动态搜索策略的快速图像修复算法

南京航空航天大学计算机科学与技术学院　赵政康



基于动态搜索策略的快速图像修复算法

南京航空航天大学计算机科学与技术学院赵政康

【摘要】本文在样本全局搜索算法的基础上，设计了一种新的算法，算法在匹配样本策略上着手，使用动态的对比算法，在相似性计算结束之前排除掉差异较大的样本，减少了样本匹配的平均计算量。实验结果表明，与对比算法相比较，本文算法在不降低修复质量的前提下有效的提高了算法的修复速度。

【关键词】图像修复；相似性衡量；动态搜索

图像修复是数字图像处理领域的一个重要分支，为了恢复损毁图像的完整性，利用图像的已知信息，按照一定的规则，来修补图像中缺失部分，是图像修复算法重点关注的问题。图像修复算法可以分为基于扩散的修复方法和基于样本纹理合成的修复方法。基于扩散的修复方法典型的算法是Bertalmio于2000年提出的基于偏微分方程的数字图像修复算法[1]，2003年Criminisi等人另辟蹊径提出了基于样本的图像修复算法[2]，它是基于纹理合成的修复方法，借鉴了纹理生成方法中的思想来寻找样本区域并匹配复制。Criminisi给出的大量实验表明，该算法在修复效果和时间上都略胜一筹。接着，大量的科研工作者开始研究Criminisi的算法：文献3通过分析Criminisi算法的不足之处，提出一种新的算法，该算法采用一种新的最优样本块的匹配准则，降低了传播误差的几率。文献4则提出了基于结构信息扩散的图像修复算法[4]，获得了不错的效果。

1　Criminisi算法

Criminisi修复算法[2]的具体步骤简述如下：

第一步：明确标记出待修复区域的边缘；

第二步：对于每一个破损区域边缘上的点p为中心的待修复块，计算修复优先权P(p)；

第三步：根据每一个待修复点的优先权值找到具有最高修复优先权的待修复块；

第四步：当确定本次迭代所要修复的块后，通过样本块相似性计算公式在整个先验区域内匹配最佳样本块。通常算法使用欧几里得距离作为相似性衡量准则。

第五步：将选定的最佳匹配块拷贝到待修复区域，完成本次迭代的修复。

2　本文改进算法的提出

分析修复算法复杂度可知，修复过程中最耗时的步骤是迭代过程中样本块与待修复块一一匹配的过程。考虑到欧氏距离的计算是一种累加计算，使用穷举的方式计算量太大，然而修复算法计算欧式距离是为了找出距离最小的样本块，因此本文设计了一种动态对比搜索策略来处理每次迭代过程中的样本选择问题，即在累加还没结束之前就可以排除掉一部分相似性差异很大的样本。具体的实现方式如下：使用一个变量d来记录当前迭代过程中产生的最小的距离，修复迭代过程按照以下步骤进行：

第一步：初始化d为样本空间中第一个样本与待修复块之间的距离；

第二步：该次迭代中其余样本块与待修复块之间的距离计算方式为累加一次比较一次，即每累加一次，将临时结果与d作比较，如果值大于d，则排除当前样本块；若d被更新成0，则停止这一次迭代，当前样本块为最佳匹配。

第三步：取当前d保持者的样本块作为最佳匹配，完成本次迭代。

3　实验结果与分析

本节主要对所提算法进行功能验证和性能评估，首先介绍实验环境及实验设计，然后通过实验结果对比算法的修复效果和修复时间。本章实验在PC机上使用Matlab 2013b编程实现，系统环境为64 位WIN 8系统，PC配置为Intel(R) Core(TM) i5-4210M CPU @ 2.60GHz，8GB内存。实验设计了两组实验，通过对比Criminisi算法与本文所提算法的修复质量和修复速度来验证本文算法的可行性。表格1记录了两组实验的实验数据，PSNR为修复质量衡量指标，PSNR值越大，修复结果越接近原图像。

表1　修复质量指标与修复时间对比

分析表1中数据，本文算法的修复质量与对比算法相比平均下降了0.125分贝，这是一个相对比较小的数量级，可以认为本文算法的修复质量没有受到搜索策略改变的影响。继续观察表中实验的修复速度数据，本文算法的修复时间平均比对比算法降低了45.08秒，很明显在修复速度方面本文算法具有明显的优势。在此得出结论，本文的改进算法在没有影响修复质量的前提下有效的提高了修复速度，本文算法是可行的。

参考文献

[1]Bertalmio M,Sapiro G,Caselles V,et al. Image inpainting[C].Proceedings of the 27th Annual Conference on Computer Graphics and Interactive Technique,2000: 417-424.

[2]Criminisi A,Perez P,Toyama K.Object Removal by Exemplar-based Inpainting[C].Proc.of Conf.on Comp.Vision Pattern Rec.Madison,WI,USA,2003.

[3]Tang Feng,Ying Yiting,Wang Jin,Peng Qunsheng. A Novel Texture Synthesis Based Algorithm for Object Removal in Photographs[C].Ninth Asian Computing Science Conference.Chiang Mai.

[4]Sun Jian,Lu Yuan,Jia Jiaya,et al.Image Completion with Structure Propagation [EB/OL].[2015.7.30].http:// researeh.microsoft.com/asia/dload_files/group/VC/2005/ Imagecompletion/Siggraph05_0265. final.pdf.

赵政康（1990－），男，南京航空航天大学硕士研究生，研究方向：数字图像处理。

作者简介：