基于蚁群算法的Criminisi图像修复

郑玉婷，吴 谨



基于蚁群算法的Criminisi图像修复

郑玉婷，吴 谨

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

提出了一种基于蚁群算法的Criminisi图像修复算法，将蚁群算法应用到Criminisi图像修复算法的最佳匹配模板搜索中。首先计算待修复区域优先权；然后蚁群寻找搜索路径中留下的信息素，沿着信息素最多的路径寻找到最佳匹配模板；最后更新置信度，直到修复结束。实验结果表明，修复后的图像PSNR较高不易陷入局部最优，能较快速地搜索到最佳匹配模板。

蚁群算法；Criminisi算法；最佳匹配模板

0 引言

图像修复是利用图像中已知的有效信息，按照一定规则对破损的图像进行信息填充，得到连续、完整、自然的图像视觉效果。主要应用于文物保护、老照片的修复、图像中文本信息以及障碍物的去除、影视特技制作等领域。

目前图像修复算法主要分为两大类：基于偏微分方程的图像修复法[1]和基于纹理的图像修复法[2]。

BSCB模型算法[3]、TV模型算法[4]是对图像中的像素点进行修复，属于偏微分方程的图像修复法，主要适用于小区域信息缺失的图像修复。

Criminisi经典算法[5]是对图像中的像素块进行修复，属于基于纹理的图像修复法，主要适用于大区域信息缺失的图像修复。

Criminisi经典算法是Criminisi等于2004年提出的一种基于样本块的修复方法，该算法采用SSD搜索最优匹配块。其修复过程由待修复区域标记、优先权计算、最佳匹配模板搜索与填充、更新置信度组成。该算法的改进主要是针对优先权、最佳匹配模板搜索进行的。文献[6]重新定义了数据项，引入新的度量函数以更新置信度，使优先权的计算更加准确；文献[7]将P-M方程引入数据项进行梯度和等照度线两个方向同时修补，以提高修复效率；文献[8]重新定义了模板匹配准则，以提高匹配准确率；文献[9]引入数学形态学对待修复图像进行预处理，进而提高图像修复质量。

针对Criminisi经典算法中最佳匹配块搜索易陷入局部最优的问题，引入蚁群算法[10]，减少误差累积传递，以提高修复质量；同时引用文献[7]重新定义数据项，以提高修复效率。

1 基于蚁群算法的Criminisi修复

基于蚁群算法的Criminisi图像修复方法包括优先权计算、蚁群算法搜索最佳匹配模板、更新置信度。

1.1 优先权的计算

优先权是Criminisi经典图像修复算法第1步，处于核心地位，决定了修补的先后次序。假设修补前的图像如图1所示。

图1 Criminisi经典算法

图1中，为完好区域，即未标记的区域；为破损区域，也称待修复区域；d为待修复区域的域边界，在填充过程中，边界d会向待修补目标区域不断收缩，又称填充边缘；点为目标像素点；ÑI^为点的等照度线方向；n为点的法向量；为以点为中心确定的矩形块。

点优先权Priority()计算如式(1)所示。

Priority()＝()*() (1)

式中：||为面积；()为置信度，表示的是中完好信息所占的比重，()越高，单位面积内已知像素就越多，能为最佳匹配块的选择提供更多可靠信息，即越早被修复，()保证了图像的修复由待修复区域外向内进行；()为数据项，表示ÑI^与法向量n的模。夹角越小，()的值就越大，即线性结构强度高的部分优先得到填充；在灰度图中通常取255。

本文引用文献[7]重新定义数据项()，如下式：

()＝|(|Ñ|)|＋|(|Ñ|)|(4)

式中：为等照度线的切线方向；为等照度线的法线方向；(|Ñ|)是边缘停止函数。重新定义的数据项使优先权计算从梯度和等照度线两个方向同时进行，以提高修复效率。该式采用P-M方程约束的填充算法，将平滑去噪P-M方程按梯度和等照度线两个方向分解进而获得可靠的填充顺序和信息进化方向。

1.2 最佳匹配模板的搜索与填充

通过优先权的计算，确定最大优先权待修补块后，在完好区域进行最佳匹配模板的搜索与填充，匹配原则为：

式中：¢为待修复目标块；为完好区域内样本块；d(¢,)为两个像素块对应像素点灰度差值的平方和，SSD匹配原则表示为当目标块¢与样本块的像素点灰度差值平方和距离最小时，样本块便替代目标块¢，即为最佳匹配模块。

本文将采用蚁群算法进行最佳匹配模板的搜索。蚁群算法是一种源于生物世界的仿生类进化算法。它由Marco Dorigo于1992年提出，灵感来源于蚁群在寻找食物过程中释放信息素发现最佳路径的行为。

蚁群算法优化过程的本质基于3个原则：①信息素越大的路径，被选择的概率越大；②信息素会随着蚂蚁的经过而增多，同时也会随着时间的推移而减小，即信息素的更新；③蚂蚁之间是通过信息素来互相通信、协同工作的，这种方式使得蚁群算法具有很强的发现路径能力，即协调性。

蚁群算法数学模型如下：

设有个样本块，只蚂蚁，d(,＝1, 2, …,)表示节点和间的距离，()为时刻块和之间的信息素浓度，设初始时刻各条路径上的信息素浓度均为（常数）。则在时刻蚂蚁（1≤≤）在节点选择节点的转移概率为：

式中：U为蚂蚁下一步允许选择的块；为信息启发式因子，反映了蚂蚁在路径d所积累的信息素在蚁群运动时所起的作用，其值越大，蚁群之间协作性越强；为期望启发式因子，反映了启发信息对蚂蚁选择转移方向时的影响权重，一般取＝1/d。

经过个时刻，蚁群完成一次循环。这时蚁群所经过的每条路径上的信息素需要进行一次更新：

(＋)＝×D(7)

式中：为信息素的挥发程度；D为整个蚁群在此次路径d上信息素的增量：

D为蚂蚁留在路径d上的信息素：

式中：是一个常数；L是蚂蚁在本次路径中所爬行距离。

基于上述原则及数学模型，蚁群算法的步骤如下：

Step1：＝0（为迭代步数或搜索次数），和D初始化；将个蚂蚁置于条路径的起点；

Step2：将蚁群的初始出发点置于当前解集中；对每个蚂蚁(＝1,2,…,)计算概率P()，将蚂蚁移到下一个节点，将置于当前解集；

Step3：计算各蚂蚁的路径长度L（＝1,2,…,）；记录当前最优解；

Step4：按式(7)更新最佳路径，修改轨迹强度；

Step5：对各边弧(,)，置D＝0，＝＋1；

Step6：若＜预定的迭代次数且无退化行为（即找到的都是相同解或进化趋势相差明显），则重复Step2；

Step7：输出当前最优解。

1.3 置信度的更新

最高优先权的目标块修补完成后，块中原来的边界变为已知点，区域内中的点变为已知点或者边界点，这时需要重新计算已知点的置信度，以及边界点的优先权。置信度更新公式如下：

(¢)＝(),"΢Ç(10)

通过不断重复计算优先权、搜索与填充最佳匹配模板、更新置信度，直至待修复区域为空集，则修复完成。

综上所述，基于蚁群算法的Criminisi图像修复流程如下：

Step1：标记待修复区域；

Step2：待修复区域是否为空集，若是空集则输出图像；若不是空集进行下一步；

Step3：计算优先权；

Step4：基于蚁群算法的最佳匹配模板搜索填充（即蚁群在运动路径上留下信息素，信息素最大的路径为匹配模块）；

Step5：更新置信度；

Step6：重复Step2，直到待修复区域为空集，即修复完成。

2 仿真实验结果分析

本文实验仿真平台是MATLAB7.0和VC＋＋6.0。并采用峰值信噪比PSNR评价图像的修复质量，其函数表达式如下：

式中：MSE为原图像与处理图像之间均方误差，PSNR值越大，代表失真越少；2－1为信号最大值；为每个采样值的比特数。

图像修复主要针对冗余目标移除修复，本文将Criminisi经典算法、文献[6]、[8]算法及本文算法对两百幅图像进行比较，选取图2、图3，为了移除小女孩和沙滩上的行人，得到所需的前景图像。表1为4种算法移除小女孩图像和行人图像的PSNR与耗时比较。

图2(c)、图2(d)的修复结果中均有错误信息的累积，无法满足视觉要求。图2(c)中出现了大面积错误的结构纹理修复信息，将背景山间的信息填充到目标移除区域；图2(d)处理好了台阶的边缘结构信息，但错误的修复无法与周围信息相协调；图2(e)、图2(f)修复效果最好，一定程度上区分了边缘结构信息，且错误信息累积较少，图像修复质量较好。

图2 移除图像修复结果

Fig.2 Image inpainting of the little girl removal

图3 行人移除图像修复结果

表1 种算法移除小女孩和行人图像PSNR与耗时

针对图3仿真结果：(c)图将树叶部分信息填充到目标移除区域，得不到理想修复结果；(d)图仍然是将树叶部分信息填充到目标移除区域，错误结构纹理修复信息相比(c)图较少，但仍然无法满足视觉需求；(e)、(f)边缘结构信息处理较好，基本满足人的视觉需求。

由表1看出，本文改进算法PSNR数值最大，耗时最短，即修复效果最好。文献[8]改进算法之所以PSNR数值较大是因为该算法重新定义最佳模板匹配原则，有利于填充模块与原模块保持一致性。本文改进算法之所以PSNR最大、耗时最短是因为蚁群算法采用释放信息素寻找最佳路径方式使搜索最佳匹配模板不易陷入局部最优，优先选择最佳模板，即修复质量高；引入文献[7]重新定义数据项，使优先权计算同时从梯度和等照度线两个方向同时进行，即耗时短。

综上，针对目标移除这一类图像修复，本文引入的蚁群算法鲁棒性较强具有一定实用性。

3 结论

本文引入蚁群算法对Criminsi经典算法中最佳匹配模板的全局搜索方式进行优化。优化后的算法通过个体间的信息交流与相互协作不易陷入局部最优，易搜索到最佳匹配模板，进而减少错误信息积累。实验结果表明，修复后的图像在一定程度上质量、效率有所提高，相比Criminisi经典算法更满足视觉需求，具有实用价值。

[1] 林云莉, 赵俊红, 朱学峰, 等. 基于图像分解的图像修复技术[J]. 计算机工程, 2010, 36(10): 187-192.

LIN Yunli, ZHAO Junhong, ZHU Xuefeng, et al. Image inpainting technology based on image decomposition[J]., 2010, 36(10): 187-192.

[2] 魏琳, 陈秀宏. 基于纹理方向的图像修复算法[J]. 计算机应用, 2008, 28(9): 2063-2069.

WEI Lin, CHEN Xiuhong. Algorithm of image inpainting based on texture orientation[J]., 2008, 28(9): 128-132.

[3] BERTALMIO M, SAPIRO G, CASELLES V, et al. Image inpainting[C]//, New Orleans, Louisiana, USA, 2000: 417-424.

[4] CHAN T, SHEN J F. Mathematical models for local nontextureinpain- ting[J]., 2001, 62(3): 1019-1043.

[5] CRIMINISI A, PEREZ P, TOYAMA K. Region filling and object removal by exemplar-based inpainting[J]., 2004, 13(9): 1200-1212.

[6] 胡文瑾, 王维兰, 刘仲民. 一种基于样本块的快速图像修复算法[J]. 数据采集与处理, 2011, 26(6): 626-630.

HU Wenjin, WANG Weilan, LIU Zhongmin. Improcedexemplar-based method for image inpainting[J]., 2011, 26(6): 626-630.

[7] 张申华, 祝轩, 雷文娟, 等. 一种改进的基于样例的目标物体移除方法[J]. 计算机工程与应用, 2011, 47(7): 180-182.

ZHANG Shenhua, ZHU Xuan, LEI Wenjuan, et al. An improved exemplar-based method for objet removal[J]., 2011, 47(7): 180-182.

[8] 陈龙, 熊辉, 汪继文. 基于样本块的图像修复方法的改进[J]. 计算机应用, 2011(6):47-50.

CHEN Long, XIONG Hui, WANG Jiwen. Improvement of image inpainting based on sample patch[J]., 2011(6): 47-50.

[9] 李尊, 吴谨, 刘劲, 等. 数学形态学在Criminisi图像修复算法中的应用[J]. 红外技术, 2015, 37(7):574-578.

LI Zun, WU Jin, LIU Jing, et al. The application of mathematical morphology in the Criminisi algorithm of image inpainting[J]., 2015, 37(7): 574-578.

[10] Dorigo M, Gambardella L M. Ant colony system: A cooperative learning approach to the traveling salesman problem[J]., 1997, 1(1): 53-66.

The Criminisi Algorithm Based on Ant Colony Optimization for Image Inpainting

ZHENG Yuting，WU Jin

(,,438001,)

An Criminisi image inpaiting algorithm based on ant colony algorithm is proposed, which applies Ant colony algorithm to search the best matching template in Criminisi image inpaiting algorithm. Firstly, the priority area to be inpainted is calculated. Then, ant colony finds the pheromoneleft in searching path, and follows the path with most pheromones to find the best matching template. Finally, the confidence is updated until the end of inpaiting. Experiments show that the PSNR value of the image after inpaiting is higher and local optimum is avoided. The method can more quickly search for the best matching template.

Ant colony optimization，Criminisi algorithm，the best template

TP391.41

A

1001-8891(2017)03-0221-05

2016-03-30；

2016-06-13.

郑玉婷（1992-），女，湖北孝感人，硕士，主要从事图像修复方面的研究。E-mail：525514824@qq.com。

国家自然科学基金青年项目（61502358)；湖北省自然科学基金（2013CFB333）。