目标移除的Criminisi图像修复算法

李 尊，吴 谨，刘 劲



目标移除的Criminisi图像修复算法

李 尊，吴 谨，刘 劲

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

待修复区域标记、优先权、最佳匹配模块的搜索及填充和更新置信度是Criminisi图像修复算法的4个重要组成部分，每一部分对Criminisi算法的图像修复结果都有不可忽视的作用。针对大目标移除的Criminisi图像修复，从数学的角度优化待修复区域标记和提高优先权可信度，并将蝙蝠算法运用到最佳匹配模板搜索中，提高修复效率。实验表明：本文改进的算法能够有效的减少错误信息的累积，具有较好的实用性。

Criminisi图像修复算法；修复区域标记；优先权；蝙蝠算法

0 引言

图像修复[1-2]就是利用图像中原有的信息来恢复缺失的信息。目前图像修复技术广泛应用到文物保护，冗余目标的移除，影视特效制作等方面，是当前计算机视觉研究的一个热点。

图像修复主要由两种代表性计算机自动修复算法构成，基于结构的图像修复[3-4]和基于纹理的图像修复。

Criminisi图像修复算法[5]是基于纹理的典型算法，由Criminisi等人于2004年提出。其将纹理特征和结构信息结合起来进行修复，取得了不错的效果。

近年来，Criminisi图像修复算法的改进主要是提升优先权的可信度。但是Criminisi图像修复算法是一个有机整体，由修复区域标记、优先权计算、最佳匹配块搜索与填充和更新置信度组成，每一步在Criminisi图像修复算法中都不可或缺。

本文针对目标移除的情况进行研究，探究其修复效果的影响因素，从数学的角度改进Criminisi图像修复算法，提高目标移除的Criminisi图像修复质量。

1 Criminisi图像修复算法

图1为Criminisi图像修复算法示意图，图中，表示待修复区域；表示待修复区域的轮廓；表示完好区域。

Criminisi图像修复算法核心思想就是通过优先权公式确定要修补的目标块，进而根据一定的匹配原则在已知信息区域进行搜索并填充，直至待修复区域修复完毕。

对图1中目标块的优先权的计算公式如式(1)所示：

priority()＝()() (1)

其中：

式中：()为置信度，用于衡量目标块中已知信息的比重；()为数据项，决定图像修复是沿等照度线的方向进行；在灰度图中通常取＝255。

图1 Criminisi算法示意图

通过优先权确定最大值的待修补块后，在样本区域根据式(4)的匹配原则选取最佳匹配模块进行填充：

Criminisi图像修复算法通过上述原则不断地进行填充，直至待修复区域修复完成。

2 Criminisi算法的分析与改进

2.1 待修复区域的标记

在进行Criminisi算法修复前，图像的待修复区域需要一种特定的颜色进行标记，通常选用白色。

但是预先标记往往会影响待修复区域的结构信息和纹理信息。因此本文引入数学形态学中的腐蚀与膨胀[6]对待修复图像进行预处理。本文引入数学形态学来保证Criminisi图像修复算法的进行是在合理的标记的基础上。

形态腐蚀与膨胀对图像处理有如下效果：

1）形态膨胀使得孔隙消失，缝变粗，扩展图像；

2）形态腐蚀使得孔隙扩大，缝变细，收缩图像。

本文采用形态膨胀与腐蚀的基本组合形式，对待修复图像进行处理,即先膨胀后腐蚀：

式中：、都为结构元素。

2.2 优先权的计算

优先权处于Criminisi图像修复算法第一步，处于核心地位，决定了修补的先后次序。

优先权的计算存在两点不足：

1）随着修补次数的增加，置信度()中的原图的信息会减少甚至出现数量级的差别，造成优先权完全是由纹理信息所决定的；

2）数据项()是人为设定的修补方向按照等照度方向进行的，极易出现线性修补方向现象，人为修复的痕迹增强。

为了提高填充次序的可信度，近几年改进的Criminisi图像修复算法侧重点在优先权。其中文献[7]将优先权中数据项和置信度转换成加权和的形式，一定程度上提升了优先权的可信度，且修复质量有所提升；文献[8]通过引入曲率决定目标块的优先权，增强了修复图像的结构连续性。

本文对优先权的改进是基于数学的角度，当输出正比于输入时能够很好的抵抗噪声及外部的干扰。所以为了增强修复边缘结构过程的鲁棒性，本文引用正规化函数平滑数据项()曲线。因此得出的新数据项如式(6)所示：

()＝＋(1－)() (6)

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

新优先权为新数据项与置信度的加权形式，如式(7)所示：

Newpriority()＝×()＋×() (7)

式中：＋＝1，本文取＝＝0.5。

2.3 匹配模块搜索与填充

Criminisi图像修复算法的最佳匹配模块就是完好区域的样本块中已知元素与待修补块的的颜色平方和最小值的模块，其从数学原理上来说就是差方和法，即SSD。

但在实际的修复过程中，全局搜索时最佳模块可能不止一个，系统会随机地选择一个进行填充，且全局搜索增加计算机的工作量同时影响最佳模块的选择。

文献[9]引入待匹配块的再筛选策略，降低了匹配模块选择的随机性，增强了图像的修复效果；文献[10]将像素点间的空间距离引入，且采用全局搜索，能够很好地避免“贪婪性”的缺点。

本文采用蝙蝠算法[11]进行最佳模板的搜索，且匹配原则仍为SSD。蝙蝠算法能将全局搜索和局部搜索高效的融合，且具有很好的适应性和鲁棒性，能够降低错误信息的累积。

蝙蝠算法公式化基于以下3个原则：

1）蝙蝠采用特定的方式判别目标物与障碍物，且利用回声定位方式感知距离；

2）在任意位置X处，蝙蝠以速度V任意飞行，以确定大小的频率min和大小可变的波长、响度0找寻目标物，且根据目标物与自身的距离远近自动调节波长或者频率，并在靠近目标物时候调整发射脉冲的频度Î[0,1]。

3）默认响度的变化是从最大值0到最小值min，0必须为正值。

基于上述原则，蝙蝠算法的步骤如下所示：

步骤一：参数初始化：目标函数()，其中维度集合＝(1,2,3,…,x)，为维度，1,2,3,…,x为变量数，蝙蝠群体的个体采用标识，初始化蝙蝠群体的个体在X处的速度V并定义X处的脉冲频率f，初始化脉冲速率r和响度A，本文目标函数()采用SSD匹配原则。

步骤二：通过调整频率产生新的解并更新速度和位置。

步骤三：根据rand1＞r进行判断，从最佳解的集合中选出一个解，在最佳解周围形成一个局部解，其中rand1表示产生一个随机数。

步骤四：通过不确定飞行确定一个新的解。

步骤五：根据判断条件rand2＜A&(x)＜(*)进行判断，若条件满足，增大r减小A，然后进入步骤六，其中rand2表示产生一个随机数。若不满足则直接进入步骤六。

步骤六：排列蝙蝠找到最佳解*。

步骤七：处理结果：若结束条件满足，则结束迭代输出最优解；不满足则返回第二步进行迭代。

第次迭代执行到步骤二时，其中速度、位置的更新如式(8)～式(10)所示：

f＝min＋(max－min)(8)

V＝V－1＋(X－*)×f(9)

X＝X－1＋V(10)

当＝1时，X－1、V－1采用初始化所得结果。

可根据问题的领域大小确定脉冲频率f的值，比如取min＝0，max＝100，开始时每只蝙蝠随机分配频率，频率可从[min,max]平均得出的。min为最小脉冲频率，max为最大脉冲频率，可自行预先设定取值。Î[0,1]为随机向量，*为当前全局的最佳解。在固定(f)的同时改变f()，且在局部搜索的过程中，每只蝙蝠的新的位置就近得出，其中表示对应脉冲频率的波长，如式(11)所示：

new＝old＋A(11)

式中：Î[－1,1]为随机数；old表示蝙蝠所处的旧位置；new表示蝙蝠所处的的新位置；A为所有蝙蝠在本次迭代中的平均值。

随着蝙蝠的速度与位置的更新，脉冲发射的响度A和速率r也会更新。通常目标物一旦发现，其脉冲的发射响度A会降低，脉冲的发射速度r会升高，其表达式如下所示：

A＋1＝A(12)

r＋1＝r0(1－e－) (13)

式中：、为恒量，且满足0＜＜1，＞0。在、的取值范围定义下，随着迭代次数的增加，脉冲发射的响度A会逐渐趋于0，脉冲发射的速率r会逐渐趋于初始化脉冲的发射速率r0，其数值通常选用在0附近，满足蝙蝠算法公式化的原则。

本文采用标准的Rosenbroke检测函数对蝙蝠算法进行测试，其函数表达式如下所示：

其中，本文取值＝2，应用情景是二维，蝙蝠的种群中个体的个数为25只，即1≤≤25且Î*，＝＝0.9。*为正整数。

本文利用蝙蝠算法寻找()的最小值，由数学理论可知，()在(1,1)时，可取得最小值0，其蝙蝠搜索路径如图2所示。

图2 蝙蝠算法搜索路径图

从图2中，可以看出标准的Rosenbroke检测函数通过25只蝙蝠将搜索区域确定，然后在确定的小范围的搜索区域进行最优解的搜索。最后最优解的点坐标为(1.0006,1.0011)与理论值相差不大。

因此在最佳匹配模板的搜索的过程中，SSD原则作为蝙蝠算法的目标函数，搜索方式即为蝙蝠算法，如式(15)所示：

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

蝙蝠算法能很好地将全局搜索和局部搜索高效的融合。且此算法具有很好的适应性和鲁棒性，提升图像修复效果。

综上，本文对待修复区域标记、优先权的计算、最佳匹配模板的搜索方式3方面进行改进，旨在降低错误信息的累积进行修复，提高修复质量，满足人的视觉需要。

3 仿真实验结果分析

本文实验仿真平台是MATLAB7.0和VC＋＋6.0，峰值信噪比PSNR是目前最普遍用来评鉴图像质量的客观量，因此本文实验结果修复结果质量用此客观地评价。

图3的修复目的是对于前景人群而言，背景人群是冗余目标，需要移除。其中，(a)是原图，(b)为预先标记图像，(c)为经过数学形态学处理后的标记图。

图4的修复目的是对于风景而言，垃圾桶是冗余目标，需要移除。其中，(a)是原图，(b)为预先标记图像。(c)为经过数学形态学处理后的标记图。

本文数学形态学处理的结构元素为圆形，目的是能够很好地强化边缘结构信息。本文的图像修复是在经过数学形态学处理后的标记图的基础上进行的。

图5、图6中，(a)表示传统Criminisi图像修复算法的修复效果；(b)表示文献[7]图像修复算法的修复效果；(c)表示文献[8]图像修复算法的修复效果；(d)表示本文改进的Criminisi图像修复算法的修复效果。

主观上：在图5、图6的(a)、(b)、(c)和(d)中，(a)、(b)、(c)的修复效果图中均有错误信息的累积，无法满足人的视觉效果；(d)的修复效果最好，能够很好地区分边缘结构信息，较少的错误信息的累积，满足人的视觉需要。

客观上：在表1、表2中，数据显示(d)的PSNR数值最大，则其修复的效果最好。

因此针对目标移除这一类图像修复，本文改进的算法具有很好的实用性，错误信息累积减少，视觉需求得以满足。

4 结束语

本文针对Criminisi算法的不足，对待修复区域的标记、优先权的计算、最佳匹配模板的搜索方法进行改进。针对目标移除这一类图像修复，本文改进的算法提高了优先权和匹配原则的可信度，能够有效地避免错误信息的累积，增强图像修复效果，具有很高的实用价值。

图3 人群移除的图像

图4 垃圾桶移除的图像

图5 改进的Criminisi算法在人群的对比实验

图6 改进的Criminisi算法在垃圾桶的对比实验

表1 改进的Criminisi算法在人群的PSNR值

表2 改进的Criminisi算法在垃圾桶的PSNR值

[1] Bertalmio M, Sapiro G, Caselles V, et al. Image inpainting[C]//, John Seely Brown, USA, 2000: 417-424．

[2] 陈钱. 红外图像处理技术现状及发展趋势[J]. 红外技术, 2013, 35(6): 311-318.

CHEN Qian. The status and development trend of infrared image processing technology[J]., 2013, 35(06): 311-318.

[3] Ballester C, Bertalmio M, Caselles V, et al. Filling-in by joint interpolation of vector field and gray levels[J]., 2001, 10(8): 1200-1211．

[4] Chan T, Shen F. Mathematical models for local non-texture inpaintings[J]., 2002, 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] 任获荣. 数学形态学及其应用[D]. 西安: 西安电子科技大学, 2004．

REN Huorong. Mathematical morphology and its application[D]. Xi’an: Xidian University, 2004.

[7] 郭勇, 王梅. 基于改进样本块的数字图像修复算法研究[J]. 软件导刊, 2013, 12(10): 156-158.

GUO Yong, WANG Mei. Research on exemplar-based digital improving image inpainting algorithms[J]., 2013, 12(10): 156-158.

[8] 常晨, 尹立新, 方宝龙. 一种改进的Criminisi图像修复算法[J]. 计算机应用与软件, 2012, 29(9): 238-267.

CHANG Chen, YIN Lixin, FANG Baolong. An improved Criminisi algorithm for image inpainting[J]., 2012, 29(9): 238-267.

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

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

[10] 潘姣君, 谢伙生. 结合灰度共生矩阵和熵的图像修复算法[J]. 图形、图像与多媒体, 2012, 31(21): 44-49.

PAN Jiaojun, XIE Huosheng. Image inpainting algorithm combining gray-level co-occurrence matrix and entropy[J]., 2012, 31(21): 44-49.

[11] Yang X S．A new metaheuristic bat-inspired algorithm[C]//2010,284, 2010: 65-74.

Criminisi Image Restoration Algorithm for Object Removal

LI Zun，WU Jin，LIU Jin

(,,438001,)

Criminisi algorithm consists of four steps which are marking area, the priority, the best sample patch and updating the degree of confidence and each step has the important effect. For removing a big target, this paper uses the reasonable marked and improved priority, and then the bat algorithm is applied to search the best match template in Criminisi image restoration. Experiment results show that this method can reduce the inaccurate matching and has relatively high practical value.

Criminisi algorithm，the marked area，the priority，bat algorithm

TP391.41

A

1001-8891(2016)01-0028-05

2014-05-26；

2014-08-19.

李尊（1988-），女，河南省新乡，硕士研究生，从事图像修复研究工作。E-mail：895310276@qq.com。

湖北省自然科学基金（2013CFB333）；高等学校博士学科点专项科研基金（20124219120002）；湖北省教育厅科研计划（Q20131110）。