FA－Criminisi快速图像修复

李 尊，吴 谨，刘 劲，吴秋红

（武汉科技大学 信息科学与工程学院，湖北 武汉 430081）

1 引 言

图像修复［1］主要是修复图像中破损区域或者移除多余的目标。其是计算机视觉的研究热点，广泛应用于文物的修复，影视特技等方面。主要分为基于偏微分方程算法［2］和基于纹理合成算法［3］两大类。

Criminisi图像修复算法［4］是由Criminisi等人于2004年提出，是纹理合成图像修复技术的代表。算法的思想是在完好区域进行全局搜索，确定最佳匹配块并填充到待修复区域，达到修复图像的目的。此算法步骤由优先权的计算、最佳模板的搜索与填充和更新置信度构成。但在修复过程中，优先权计算可信度不高，最佳匹配模板搜索精确度低等问题影响修复效果，不能满足视觉需求。

自从Criminisi算法被提出，国内外学者就针对其缺点进行改进。文献［5］将优先权中数据项和置信度转换成加权和的形式，一定程度上提升了优先权的可信度；文献［6］引入曲率到优先权，并将算式改成各项加权和，增强了图像结构的连续性；文献［7］根据修复区域边缘的复杂性，动态的选择搜索区域，降低了时间成本，且一定程度上改善了修复质量；文献［8］采用区域分割的变尺寸样本块高效图像修复算法，降低了时耗且改进修复质量。

本文针对Criminisi图像修复算法中优先权可信度不高，影响修复顺序和采用穷尽方法搜索最佳匹配模板，具有随机性大，效率低的缺点进行改进。引入正规化函数，提升优先权计算的可信度；将萤火虫算法（FA）引入最佳模板的搜索与填充中，保证修复质量，提高效率。

2 萤火虫算法

萤火虫算法［9］是基于种群搜索的随机优化算法。实施简单，并行处理能力强，鲁棒性能强。此算法由Yang于2008年提出，核心思想基础是萤火虫发光的生物学原理。

对于萤火虫发光生物学原理的数学化需要以下理想化原则：

（1）在目标函数的寻优过程中，萤火虫之间的相互吸引只有亮度这个因素；

（2）吸引力只和亮度有关，与亮度成正比例关系；

（3）目标函数决定萤火虫的亮度；

（4）亮度和吸引力随距离的增大而减小，与之成反比例关系。

基于上述原则，萤火虫算法可以数学化为以下步骤：

步骤一：初始化萤火虫群体，设置萤火虫群体个体数为n，最大吸引力β0，光强吸收系数γ，步长因子α，其中α∈［0，1］。

步骤二：随机设置萤火虫个体的坐标位置，计算各自的最大荧光亮度I0。其中I0的大小可由萤火虫的目标函数值确定。

步骤三：确定萤火虫的相对亮度I和吸引力β，可由公式（1）、（2）得出。

其中：I0，β0取处为光源，γ为光强吸收系数，其设置的原因是能量会随距离的增大或是介质的存在而降低，所以设置此参数，符合实际客观的要求，sij表示萤火虫之间的距离。

步骤四：萤火虫位置更新。萤火虫算法实质是逐渐靠近亮度最大个体，因此萤火虫个体的位置会不断更新。位置的更新可由公式（3）得出。

其中：xi、xj表示萤火虫个体i，j的空间位置，rand为随机因子，服从0～1的均匀分布。

步骤五：根据萤火虫的新位置，重新计算萤火虫个体的亮度。

步骤六：终止条件判断。终止条件可设置为误差精度条件或设置迭代次数上限，则输出最优解；否则，进入下一次搜索。

本文采用标准Rosenbroke检测函数对萤火虫算法进行测试，其函数表达式如式（4）所示。

其中：本文取值d＝1，应用情景是二维，萤火虫的种群个数为25只，α＝γ＝0.9。

本文利用萤火虫算法寻找f（X）的最小值，由数学理论可知，f（X）在（1，1）时，可取的最小值0。萤火虫算法搜索途径如图1、图2所示。

图1 萤火虫搜索路径1Fig.1 Fireflies search path 1

图2 萤火虫搜索路径2Fig.2 Fireflies search path 2

图1在坐标（1.002 50，1.005 83）停止搜索，图2是在（1.003 38，1.006 94）处。

从两个图可以看出，萤火虫的最佳解搜索是从无序到有序，最后趋向最佳解的过程。萤火虫算法将全局搜索和局部搜索自然结合在一起，在保证精度的前提下，提高了效率。

3 经典Criminisi图像修复算法

3.1 优先权的计算

假设待修复图像如图3所示。其中φ表示的区域是完好区域；Ω表示的区域是破损区域；δΩ表示待修复区域的边界。

图3 符号说明图Fig.3 Figure of Symbol

Criminisi算法优先权共有C（p）和D（p）两项所决定。其中C（p）为置信度，表示的是以P为中心的待修补块ψP中原图的像素所占的比重；D（p）为数据项，表示的是边界ψP在P处的梯度法向量np与完好区域的边缘梯度向量.I⊥p的乘积。

Criminisi算法提出的P点优先权计算如式（5）所示，C（p）、D（p）如式（6）、（7）所示：

其中：α是归一化算子，在灰度图中我们取α＝255。

3.2 最佳匹配块的搜索与填充

确定优先权数值最大的待修补块后，在完好区域搜索确定最佳匹配模板并填充。其匹配原则如式（8）所示：

为了实现工程进度前紧后松的总体匀速管控，前期准备阶段编制进度规划纲要的同时，要制定进度管理实施细则和考核办法，从分包合同中提取1%的费用作为工程施工过程中的奖励基金，每月末总包组织相关负责人对各合同标段的进度、质量、安全、基础4项指标进行严格考核打分，按照实施细则进行考评，考评结束后进行评比，评比结果通报，奖罚按月兑现。对关键线路或次关键线上的节点重点关注跟踪检查，影响工期的主要节点制定奖罚对等措施，未按期完成节点的项目部进行重罚，使其被动控制工期，使工期总体受控。

式（8）表示待修补块与完好区域中样本块的已知元素的颜色平方和最小时，即为最佳匹配块。

3.3 更新置信度

通过最佳匹配块的搜索与填充，使得待修补块变成完好区域中的样本块，置信度也会相应的更新，成为接下来修复工作的依据。

Criminisi算法通过不断重复上述3个步骤，直至待修复区域被填充完毕，则修复完成。

4 FA－Criminisi快速图像修复

本文在按照Criminisi图像算法流程的前提下，对优先权的确定和最佳模板的搜索方式进行改进。

4.1 优先权的改进

随着修补次数的增加，置信度C（p）中的原图的信息会急剧减少，并且很快减为0。在这种情况下，本文从数学的角度，引入正规化函数平滑置信度函数。正规化函数所起到的作用是当输出正比于输入时能够很好地抵抗噪声及外部的干扰。

因此得出的新置信度如式（9）所示：

新置信度的引入，保证其取值的范围在ω～1之间，置信度的曲线被平滑了，且其曲线的形状保留，通常选取ω＝0.7。

新优先权能够避免置信度为0时，随机抽取修补块进行修复的现象。

4.2 最佳匹配模板的搜索方式改进

经典Criminsi图像修复算法是全局搜索最佳匹配模板，耗时且准确率不高，其原因是当全局搜索出现最佳匹配模板不止一个时，系统会随机选取最佳匹配模板进行填充。本文将萤火虫算法引入作为最佳匹配模板的搜索方式，能够首先确定最佳匹配模板的重点区域，然后在重点区域进行搜索，提高效率，鲁棒性强。

因此本文将模板匹配原则即公式（8）作为萤火虫算法的目标函数，如式（11）所示。

式（11）从数学角度可以看作为SSD原则，即差方和。

最佳模板的匹配与填充过程就改进为采用萤火虫算法的方式寻找灰度差方和值最小的模板。

综上即为本文的FA－Criminisi算法的核心思想。

5 仿真实验结果分析

本文实验仿真平台是MATLAB7.0和VC＋＋6.0，且本文用峰值信噪比PSNR客观评价图像的修复质量。

图像修复主要是针对破损图像修复或是冗余目标的移除。因此本文选用这两大类图像进行仿真实验。

图4 垃圾桶移除图像修复结果Fig.4 Image inpainting of trash removal

图5 荷花信息缺失图像修复结果Fig.5 Image inpainting of lotus’s missing information

图4的修复目的是垃圾箱的移除，图5的修复目的是进行荷花缺失部分的修复。

主观上，从图4可以看出，（c）、（d）、（e）图的修复效果存在错误信息的累积。（c）图将远方房屋和栏杆信息在目标移除区域进行填充；（d）图存在少量错误信息累积，但人为修复痕迹明显；（e）图仍存在灰度跨度大的错误信息的累积，无法满足人的视觉需要；（f）中虽然有台阶少许错误信息的累积，但无跨度较大错误信息修复，整体效果较好；满足人的视觉需要；从图5可以看出，（c）、（d）中，荷花与茎的修复效果不佳，无法很好地区分边缘结构的信息；（e）中虽然能够很好地区分边缘结构，但是在荷叶上出现了黑块，有错误信息的累积；（f）中能够很好地区分边缘结构且无错误信息的累积，达到了较理想的修复效果。

表1 耗时与PSNR统计表Tab.1 Time－consuming and PSNR

客观上，由表1可以得出，在保证图像修复质量的前提下，本文FA－Criminisi算法提高了修复的效率。

因此本文FA－Criminisi算法能够降低时耗，提高效率，修复效果图满足人的视觉需求。

6 结 论

针对Criminisi图像修复算法核心部分的不足，对优先权的计算和最佳匹配模板的搜索方式进行改进。本文FA－Criminisi算法提高了优先权的可信度；且引入萤火虫算法，提高了修复效率。因此，本文算法在保证修复效果的同时降低了时耗，具有一定的实用价值，可应用于当代的影视特技制作、图片的美化等方面，具有较好的应用前景。

［1］ Bertalmio M，Sapiro G，Caselles V，et al.Image inpainting［C］.Proceedings of International Conference on Conputer Graphics and Interactive Techniques，USA：John Seely Brown，2000：417－424.

［2］ 林云莉，赵俊红，朱学峰，等.基于图像分解的图像修复技术［J］.计算机工程，2010，36（10）：187－192.Lin Y L，Zhao J H，Zhu X F，et al.Image inpainting technology based on image decomposition［J］.Computer Engineering，2010，36（10）：187－192.（in Chinese）

［3］ 朱文浩，魏国刚.基于样本的纹理合成［J］.中国图形图像学报，2008，13（11）：2063－2069.Zhu W H，Wei B G.The technology of sampled－based texture synthesis［J］.Journal of Image and Graphics，2008，13（11）：2063－2069.（in Chinese）

［4］ Criminisi A，Perez P，Toyama K.Region filling and object removal by exemplar based inpainting［J］.IEEE Trans Image Process，2004，13（9）：1200－1212.

［5］ 郭勇，王梅.基于改进样本块的数字图像修复算法研究［J］.软件导刊，2013，12（10）：156－158.Guo Y，Wang M.Research on exemplar based digital improving image inpainting algorithms［J］.Software Guide，2013，12（10）：156－158.（in Chinese）

［6］ 常晨，尹立新，方宝龙.一种改进的Criminisi图像修复算法［J］.计算机应用与软件，2012，29（9）：238－267.Chang C，Yin L X，Fang B L.An improved Criminisi algorithm for image inpainting ［J］.Computer Applications and Software，2012，29（9）：238－267.（in Chinese）

［7］ 姚建亮，彭宏京.一种改进的基于样图的图像修复法［J］.电子科技，2010，23（1）：100－103.Yao J L，Peng H J.An improved exemplar－based method for image inpainting［J］.Electronic Science and Technology，2010，23（1）：100－103.（in Chinese）

［8］ 刘洋，王昊京，田小建，等.采用区域分割的变尺寸样本块高效图像修复［J］.光学精密工程，2010，18（12）：2657－2664.Liu Y，Wang H J，Tian X J，et al.Efficient image inpainting based on region segmentation and varying exemplar［J］.Optics and Precision Engineering，2010，18（12）：2657－2664.（in Chinese）

［9］ 刘长平，叶春明.一种新颖的仿生群智能优化算法：萤火虫算法术［J］.计算机应用研究，2011，28（9）：3295－3297.Liu C P，Ye C M.Novel bioinspired swarm intelligence optimization algorithm：firefly algorithm ［J］.Application Research of Computers，2011，28（9）：3295－3297.（in Chinese）