Criminisi图像修复算法的优化
王文豪++周静波++高尚兵++严云洋
摘 要： 针对Criminisi算法在修复时会出现结构断裂和误匹配问题，在原有算法基础上提出一些新的改进思想，改进优先级函数的计算方法，将优先级函数表示为数据项、置信度项和邻域相关性项的加权和，以保证图像结构信息的连续性。设计一种样本块大小可变的算法，以增强局部协调性和边界的平滑性。改进模板间相似性度量方法，融入颜色直方图，以提高模板匹配的准确性。实验结果表明，该方法能够弥补Criminisi算法的不足，获得较好的视觉效果，提高图像的修复质量。
关键词： Criminisi算法； 图像修复； 可变大小样本块； 模块相似性度量； 颜色直方图
中图分类号： TN911.73?34； TP391 文獻标识码： A 文章编号： 1004?373X（2017）11?0053?05
Optimization of Criminisi algorithm for image inpainting
WANG Wenhao， ZHOU Jingbo， GAO Shangbing， YAN Yunyang
（Huaiyin Institute of Technology， Huaian 223001， China）
Abstract： Since the Criminisi algorithm has the problems of structure fracture and wrong matching while making image inpainting， some new improvement thoughts are proposed on the basis of the original algorithm， with which the calculation method of the priority function is improved， and the priority function is represented as the weighted sum of the data item， confidence coefficient item and neighborhood correlation term to ensure the information continuity of the image structure. An algorithm of variable?size exemplar block was designed to enhance the local harmony and boundary smoothness. The similarity measure method for templates was improved， and integrated with color histogram to improve the accuracy of template matching. The experimental results show that the method can make up the deficiencies of Criminisi algorithm， obtain better visual effect， and improve the quality of image inpainting.
Keywords： Criminisi algorithm； image inpainting； variable?size exemplar block； module similarity measure； color histogram
0 引 言
图像修复技术主要利用图像受损区域的邻域信息对受损区域按照一定的规则进行填充，使修复后的图像尽可能地与原图保持一致，具有较好的视觉效果。其在文物保护、艺术品修补、影视特技、多余物体消除和虚拟现实等领域中具有广泛的实际应用价值，现已成为图像处理和计算机视觉领域的研究热点[1?2]。
目前图像修复算法可以分为两类：一类是基于结构的方法[3]，这类方法主要是通过计算等照度的方向，将受损区域周围已知信息平滑地传进受损区域内部完成图像的修复，其较为经典的模型有BSCB[4]，TV（Total Variation）[5]，CDD（Curvature?Driven Diffusions）[6]三个模型，这类算法对修复局部狭长的区域有较好的效果，但对大面积破损和纹理丰富的图像，修复效果较差；另一类是基于纹理合成的方法[7]，这类算法主要通过在受损区域选择合适的纹理块，然后从完好区域寻找与之最相似的块代替该块，这类算法中最具有代表性的是Criminisi等人提出的基于样本块修复算法[8]，在修复大面积受损区域时可以获得较好的修复效果，但该算法在搜索最优修复块和最优匹配块时存在一些不足[9]。于是研究者们提出了一些改进算法：文献[10]提出一种基于样本块大小的自适应图像修复算法，根据图像的梯度信息自适应地调整样本块的大小，但极易出现结构不连续现象。文献[11]将优先级函数中的置信度修改成指数函数形式，以避免其随着修复过程的进行而迅速下降为零，从而影响修复顺序，但该方法修复的图像存在边界效应。文献[12]将优先级函数表示为数据项和置信度的加权和，改善修复顺序，但在修复边缘处有错层现象。文献[13]采用局部搜索策略，缩小样本块的搜索范围，提高算法运行速度，但匹配不够准确。文献[14]提出一种基于结构传播的图像修复算法，取得了较好的修复效果，但算法时间复杂度较高。
上述文献没有很好地解决结构连续性和误匹配问题。本文在Criminisi算法的基础上加入一些有意义的改进，通过增加邻域相关性项改进优先级计算方法，使得修复顺序更加可靠；利用邻域相关信息自动调整样本块大小，以适应不同纹理和结构的修复；在模块相似性计算中融入颜色直方图，提高匹配的准确性。实验表明该方法能取得较好的修复效果。
3 修复算法
综合第2节讲述的改进方法，最终的改进算法流程如下：
（1） 读入受损图像并进行预处理，确定修复边界
（2） 采用9×9的模板，利用本文改进的优先级计算方法计算边界上像素的优先级，找到优先级最高的像素点；
（3） 利用本文提出的样本块大小可变算法确定以点为中心的样本块的最大尺寸，若该尺寸大于13，记录其边界；
（4） 按照本文改进的模板相似性度量准则搜索最优匹配块；
（5） 将最优模块的像素信息复制到相应的待修复模块中的未知部分，并更新置信度和优先权等信息；
（6） 若边界不为空，转到第（2）步继续执行；否则，转到下一步；
（7） 根据第（3）步记录的较大模块的边界，对其采用FMM算法再进行一次快速修复，以消除边界效应。
4 仿真实验结果与分析
为了验證算法的有效性，本文在内存2 GB、主频2.93 GHz的双核奔腾处理器上，使用VC++和OpenCV编程进行仿真实验，并与Criminisi，文献[12，14]修复结果比较，实验中，文中的一些参数由实验经验得出，其取值分别为：。
实验1： 修复效果比较
图8和图9是两组实验结果比较图。图8为“十”字型的待修复区域，结构信息较为复杂。图8（c）为Criminisi算法修复结果，可以看出，有明显的裂缝和错误匹配情形，这主要是由修复顺序出现偏差和匹配方式单一导致的。图8（d）为文献[12]的修复结果，该算法虽然改进了优先级的计算方式，但由于没有考虑待修复区域周边的信息和图像特征信息，以致于还出现了断裂和错误匹配；图8（e）为文献[14]修复结果，效果较好，但时间复杂度较高。图8（f）为本文方法的修复效果，可以看出，虽然存在少许错误匹配，竖着的窗框上也存在修复痕迹，但总体效果而言比图8（c）、图8（d）的修复效果要好，与图8（f）相差无几。这主要是因为该算法能够根据待修复区域周边的信息，自动调整样本块的大小、改变修复顺序，在模板匹配时，考虑了更多的因素。
图9是去除较大物体之后的背景修复，该图的纹理和非结构都较复杂，本文的修复效果如图9（f）所示，没有出现纹理不和谐的地方，而Criminisi算法修复的结果在草地上出现栏杆的一部分，文献[12]修复的结果有明显的修复痕迹，文献[14]修复的结果与本文相当。
实验2： 算法运行时间比较
表1是各个算法在上述实验结果耗费的时间对比。从表1中可以看出，文献[12]与Criminisi算法运行时间相差无几，这是因为文献[12]只是将Criminisi算法的优先权的计算方式由乘法改为加法。本文方法由于在确定样本块大小、优先极计算和样本块匹配时需要花费额外的时间，因此时间复杂度比Criminisi算法高一些，然而修复质量却有较大提高。文献[14]虽然修复效果较好，然而其时间复杂度太高。
从以上两组实验比较结果可以看出，不论是修复受损区域，还是去除较大的多余目标，改进算法比Criminisi算法具有更好的修复效果，但算法耗费的时间比Criminisi算法多。
5 结 语
本文在分析Criminisi算法的基础上，针对其存在的缺陷，通过引入待修复块周边像素的信息和颜色直方图，对Criminisi算法的优先级计算方式、样本块大小和相似性度量等方面进行了一些有意义的改进，实验结果表明，本文的方法比Criminisi算法可以获得更好的视觉效果，但对于具有曲线边界的物体，修复效果还有待提高。
参考文献
[1] 韩明珠，郭树旭，臧玲玲，等.基于样本块的图像修复改进算法[J].计算机工程与应用，2015，51（16）：192?194.
[2] 翟东海，肖杰，鱼江，等.基于自适应模板的图像修复算法[J].计算机应用，2013，33（10）：2891?2894.
[3] CHAN T， SHEN J. Mathematical models for local non?texture inpaintings [J]. SIAM journal on applied mathematics， 2001， 62（3）： 1019?1043.
[4] BERTALMIO M， SAPIRO G， CASELLES V， et al. Image inpainting [C]// Proceedings of 2000 ACM Computer Graphics， Annual Conference Series. New Orleans： ACM， 2000： 417?424.
[5] CHAN T F， SHEN J H. Mathematical models for local non?texture inpainting [J]. Journal of applied mathematics， 2001， 62（3）： 1019?1043.
[6] CHAN T F， SHEN J H. Non?texture inpainting by curvature?driven diffusions （CDD） [J]. Journal of visual communication and image representation， 2001， 12（4）： 436?449.
[7] 任澍，唐向宏，康佳伦.纹理和边缘特征相结合的图像修复算法[J].计算机辅助设计与图形学学报，2013，25（11）：1682?1693.
[8] CRIMINISI A， PEREZ P， TOYAMA K. Region filling and object removal by exemplar?based image inpainting [J]. IEEE transactions on image processing， 2004， 13（9）： 1200?1212.
[9] 李爱菊，钮文良.基于改进Criminisi算法的图像修复[J].计算机工程与应用，2014，50（18）：167?170.
[10] 孟春芝，何凯，焦青兰.自适应样本块大小的图像修复方法[J].中国图象图形学报，2012，17（3）：237?241.
[11] 刘业妃，王福龙，奚祥艳，等.改进的Criminisi图像修复算法[J].小型微型计算机系统，2014，35（12）：2754?2758.
[12] 李俊栢，黄文清，黄牧，等.改进的Criminisi图像修复算法[J].工业控制计算机，2014，27（7）：127?129.
[13] ZHOU H， ZHANG J. Adaptive patch size determination for patch?based image completion [C]// Proceedings of 2010 IEEE 17th International Conference on Image Processing. [S.l.]： IEEE， 2010： 421?424.
[14] SUN Jian， YUAN Lu， JIA Jiaya， et al. Image completion with structure propagation [J]. ACM transactions on graphics， 2005， 24（3）： 861?868.
[15] TELA A. An image inpainting technique based on the fast marching method [J]. Journal of graphics tools， 2004， 9（1）： 23?33.
摘 要： 针对Criminisi算法在修复时会出现结构断裂和误匹配问题，在原有算法基础上提出一些新的改进思想，改进优先级函数的计算方法，将优先级函数表示为数据项、置信度项和邻域相关性项的加权和，以保证图像结构信息的连续性。设计一种样本块大小可变的算法，以增强局部协调性和边界的平滑性。改进模板间相似性度量方法，融入颜色直方图，以提高模板匹配的准确性。实验结果表明，该方法能够弥补Criminisi算法的不足，获得较好的视觉效果，提高图像的修复质量。
关键词： Criminisi算法； 图像修复； 可变大小样本块； 模块相似性度量； 颜色直方图
中图分类号： TN911.73?34； TP391 文獻标识码： A 文章编号： 1004?373X（2017）11?0053?05
Optimization of Criminisi algorithm for image inpainting
WANG Wenhao， ZHOU Jingbo， GAO Shangbing， YAN Yunyang
（Huaiyin Institute of Technology， Huaian 223001， China）
Abstract： Since the Criminisi algorithm has the problems of structure fracture and wrong matching while making image inpainting， some new improvement thoughts are proposed on the basis of the original algorithm， with which the calculation method of the priority function is improved， and the priority function is represented as the weighted sum of the data item， confidence coefficient item and neighborhood correlation term to ensure the information continuity of the image structure. An algorithm of variable?size exemplar block was designed to enhance the local harmony and boundary smoothness. The similarity measure method for templates was improved， and integrated with color histogram to improve the accuracy of template matching. The experimental results show that the method can make up the deficiencies of Criminisi algorithm， obtain better visual effect， and improve the quality of image inpainting.
Keywords： Criminisi algorithm； image inpainting； variable?size exemplar block； module similarity measure； color histogram
0 引 言
图像修复技术主要利用图像受损区域的邻域信息对受损区域按照一定的规则进行填充，使修复后的图像尽可能地与原图保持一致，具有较好的视觉效果。其在文物保护、艺术品修补、影视特技、多余物体消除和虚拟现实等领域中具有广泛的实际应用价值，现已成为图像处理和计算机视觉领域的研究热点[1?2]。
目前图像修复算法可以分为两类：一类是基于结构的方法[3]，这类方法主要是通过计算等照度的方向，将受损区域周围已知信息平滑地传进受损区域内部完成图像的修复，其较为经典的模型有BSCB[4]，TV（Total Variation）[5]，CDD（Curvature?Driven Diffusions）[6]三个模型，这类算法对修复局部狭长的区域有较好的效果，但对大面积破损和纹理丰富的图像，修复效果较差；另一类是基于纹理合成的方法[7]，这类算法主要通过在受损区域选择合适的纹理块，然后从完好区域寻找与之最相似的块代替该块，这类算法中最具有代表性的是Criminisi等人提出的基于样本块修复算法[8]，在修复大面积受损区域时可以获得较好的修复效果，但该算法在搜索最优修复块和最优匹配块时存在一些不足[9]。于是研究者们提出了一些改进算法：文献[10]提出一种基于样本块大小的自适应图像修复算法，根据图像的梯度信息自适应地调整样本块的大小，但极易出现结构不连续现象。文献[11]将优先级函数中的置信度修改成指数函数形式，以避免其随着修复过程的进行而迅速下降为零，从而影响修复顺序，但该方法修复的图像存在边界效应。文献[12]将优先级函数表示为数据项和置信度的加权和，改善修复顺序，但在修复边缘处有错层现象。文献[13]采用局部搜索策略，缩小样本块的搜索范围，提高算法运行速度，但匹配不够准确。文献[14]提出一种基于结构传播的图像修复算法，取得了较好的修复效果，但算法时间复杂度较高。
上述文献没有很好地解决结构连续性和误匹配问题。本文在Criminisi算法的基础上加入一些有意义的改进，通过增加邻域相关性项改进优先级计算方法，使得修复顺序更加可靠；利用邻域相关信息自动调整样本块大小，以适应不同纹理和结构的修复；在模块相似性计算中融入颜色直方图，提高匹配的准确性。实验表明该方法能取得较好的修复效果。
3 修复算法
综合第2节讲述的改进方法，最终的改进算法流程如下：
（1） 读入受损图像并进行预处理，确定修复边界
（2） 采用9×9的模板，利用本文改进的优先级计算方法计算边界上像素的优先级，找到优先级最高的像素点；
（3） 利用本文提出的样本块大小可变算法确定以点为中心的样本块的最大尺寸，若该尺寸大于13，记录其边界；
（4） 按照本文改进的模板相似性度量准则搜索最优匹配块；
（5） 将最优模块的像素信息复制到相应的待修复模块中的未知部分，并更新置信度和优先权等信息；
（6） 若边界不为空，转到第（2）步继续执行；否则，转到下一步；
（7） 根据第（3）步记录的较大模块的边界，对其采用FMM算法再进行一次快速修复，以消除边界效应。
4 仿真实验结果与分析
为了验證算法的有效性，本文在内存2 GB、主频2.93 GHz的双核奔腾处理器上，使用VC++和OpenCV编程进行仿真实验，并与Criminisi，文献[12，14]修复结果比较，实验中，文中的一些参数由实验经验得出，其取值分别为：。
实验1： 修复效果比较
图8和图9是两组实验结果比较图。图8为“十”字型的待修复区域，结构信息较为复杂。图8（c）为Criminisi算法修复结果，可以看出，有明显的裂缝和错误匹配情形，这主要是由修复顺序出现偏差和匹配方式单一导致的。图8（d）为文献[12]的修复结果，该算法虽然改进了优先级的计算方式，但由于没有考虑待修复区域周边的信息和图像特征信息，以致于还出现了断裂和错误匹配；图8（e）为文献[14]修复结果，效果较好，但时间复杂度较高。图8（f）为本文方法的修复效果，可以看出，虽然存在少许错误匹配，竖着的窗框上也存在修复痕迹，但总体效果而言比图8（c）、图8（d）的修复效果要好，与图8（f）相差无几。这主要是因为该算法能够根据待修复区域周边的信息，自动调整样本块的大小、改变修复顺序，在模板匹配时，考虑了更多的因素。
图9是去除较大物体之后的背景修复，该图的纹理和非结构都较复杂，本文的修复效果如图9（f）所示，没有出现纹理不和谐的地方，而Criminisi算法修复的结果在草地上出现栏杆的一部分，文献[12]修复的结果有明显的修复痕迹，文献[14]修复的结果与本文相当。
实验2： 算法运行时间比较
表1是各个算法在上述实验结果耗费的时间对比。从表1中可以看出，文献[12]与Criminisi算法运行时间相差无几，这是因为文献[12]只是将Criminisi算法的优先权的计算方式由乘法改为加法。本文方法由于在确定样本块大小、优先极计算和样本块匹配时需要花费额外的时间，因此时间复杂度比Criminisi算法高一些，然而修复质量却有较大提高。文献[14]虽然修复效果较好，然而其时间复杂度太高。
从以上两组实验比较结果可以看出，不论是修复受损区域，还是去除较大的多余目标，改进算法比Criminisi算法具有更好的修复效果，但算法耗费的时间比Criminisi算法多。
5 结 语
本文在分析Criminisi算法的基础上，针对其存在的缺陷，通过引入待修复块周边像素的信息和颜色直方图，对Criminisi算法的优先级计算方式、样本块大小和相似性度量等方面进行了一些有意义的改进，实验结果表明，本文的方法比Criminisi算法可以获得更好的视觉效果，但对于具有曲线边界的物体，修复效果还有待提高。
参考文献
[1] 韩明珠，郭树旭，臧玲玲，等.基于样本块的图像修复改进算法[J].计算机工程与应用，2015，51（16）：192?194.
[2] 翟东海，肖杰，鱼江，等.基于自适应模板的图像修复算法[J].计算机应用，2013，33（10）：2891?2894.
[3] CHAN T， SHEN J. Mathematical models for local non?texture inpaintings [J]. SIAM journal on applied mathematics， 2001， 62（3）： 1019?1043.
[4] BERTALMIO M， SAPIRO G， CASELLES V， et al. Image inpainting [C]// Proceedings of 2000 ACM Computer Graphics， Annual Conference Series. New Orleans： ACM， 2000： 417?424.
[5] CHAN T F， SHEN J H. Mathematical models for local non?texture inpainting [J]. Journal of applied mathematics， 2001， 62（3）： 1019?1043.
[6] CHAN T F， SHEN J H. Non?texture inpainting by curvature?driven diffusions （CDD） [J]. Journal of visual communication and image representation， 2001， 12（4）： 436?449.
[7] 任澍，唐向宏，康佳伦.纹理和边缘特征相结合的图像修复算法[J].计算机辅助设计与图形学学报，2013，25（11）：1682?1693.
[8] CRIMINISI A， PEREZ P， TOYAMA K. Region filling and object removal by exemplar?based image inpainting [J]. IEEE transactions on image processing， 2004， 13（9）： 1200?1212.
[9] 李爱菊，钮文良.基于改进Criminisi算法的图像修复[J].计算机工程与应用，2014，50（18）：167?170.
[10] 孟春芝，何凯，焦青兰.自适应样本块大小的图像修复方法[J].中国图象图形学报，2012，17（3）：237?241.
[11] 刘业妃，王福龙，奚祥艳，等.改进的Criminisi图像修复算法[J].小型微型计算机系统，2014，35（12）：2754?2758.
[12] 李俊栢，黄文清，黄牧，等.改进的Criminisi图像修复算法[J].工业控制计算机，2014，27（7）：127?129.
[13] ZHOU H， ZHANG J. Adaptive patch size determination for patch?based image completion [C]// Proceedings of 2010 IEEE 17th International Conference on Image Processing. [S.l.]： IEEE， 2010： 421?424.
[14] SUN Jian， YUAN Lu， JIA Jiaya， et al. Image completion with structure propagation [J]. ACM transactions on graphics， 2005， 24（3）： 861?868.
[15] TELA A. An image inpainting technique based on the fast marching method [J]. Journal of graphics tools， 2004， 9（1）： 23?33.
