一种改进的Criminisi图像修复算法

欧先锋 晏鹏程 郭龙源

摘要：传统的Criminisi算法使用固定大小的样本块进行修复，无法根据不同区域的纹理和结构进行调整，影响图像的修复质量。为此提出一种自适应选择样本块大小的算法，通过计算图像中像素点的梯度值来反映像素点附近区域的结构信息，进而自适应调整样本块大小。实验结果表明，改进算法可以减少传统Criminisi算法中可能出现的错位、断层等现象，能够较好地提高破损图像的修复效果。

关键词：Criminisi算法；图像修复；样本块；自适应选择；图像错位

中图分类号：TP391.41文献标志码：A

文章编号：2095-5383（2018）01-0027-05

数字图像在传输、处理、保存等过程中容易受到各种因素的影响而丢失部分信息[1]，因此图像修复技术的研究具有重要的意义。图像修复技术是利用图像中的已知区域信息对破损区域进行填充，使得修复图像尽可能与原图像相似，因此图像修复算法的好坏在一定程度上可以通过人眼进行主观判断。图像修复算法可以分为两类：基于变分PDE的图像修复算法[2-3]和基于纹理合成的图像修复算法[4-5]。经典的基于变分PDE的算法有BSCB[6]（Bertalmio、Sapiro、Caselles、Bellester）算法、TV模型[7]和曲率扩散模型（CDD）[8]等，它们都适用于受损区域较小的图像。其中BSCB是最早提出的基于变分PDE的图像修复算法，在处理纹理丰富的受损图像时修复效果较差，同时计算量较大；TV模型是BSCB算法的改进算法，在修复图像时可以祛除噪声，但在修复结构性较强的图像时可能出现错位、断层等视觉不连续性问题；CDD模型改进了TV模型，解决了TV模型的视觉不连续性问题，但是计算量很大。

基于纹理合成的图像修复算法适用于受损面积较大的受损图像，Criminisi算法是最经典的基于纹理合成的图像修复算法，在处理纹理丰富和结构复杂的破损图像时都能取到较好的效果，但是在Criminisi算法的优先权计算过程中可能产生错误的修复顺序，同时，使用固定的样本块大小也可能导致不能将正确的纹理延伸到破损区域内部而产生错位、断层等现象，图像修复质量有待进一步提高。

1 Criminisi算法

Criminisi算法[9]的主要思想是：首先，通过优先权公式计算优先权值，选取待修复区域边缘上优先权最高的像素点；其次，在未破損区域为优先权最高的待修复块寻找最佳匹配块；最后，将最佳匹配块中的像素信息填充到待修复块中，其原理图如图1所示。重复上述过程，直到整个受损区域被填充修补完整。

图1中，I为整幅图像，Ω为待修复区域，Ω表示待修复区域的边缘；Φ表示图像未破损的区域，即为图像已知部分，Φ=I-Ω。算法具体步骤为：

2）在图像已知信息区域寻找与目标块匹配最佳的像素块，再将最佳匹配块的像素值填充到待修复区域的对应位置，根据纹理匹配的SSD标准搜索最佳匹配块Ψq，然后填充Ψp。

3）填充完成后，更新图像的置信度C（p）。当优先权最高的像素块Ψp被填充之后，已经修复完后的点p的置信度C（p）就要更新为新的待修复块中心点的置信度：

重复上述步骤，直到整个破损区域全部修复完成。

2 自适应样本块的Criminisi算法

真实的图像中，图像的受损区域包含了丰富的纹理和复杂的结构，图像修复算法要求图像在修复后纹理一致，结构完整[10]。由于图像中不同位置所包含的纹理和结构信息不同，

传统的Criminisi算法在选择样本块时，使用了固定大小的样本块，在结构性复杂的区域，可能由于样本块取值过大，搜索到错误的最佳匹配块，误差累计将导致修复结果不佳。而在纹理单一的区域，又可能由于固定样本块选择较小，导致算法的修复时间过长。

针对以上问题，本文提出了一种自适应调整样本块大小的Criminisi算法。针对纹理和结构不同的区域，自适应选择不同大小的样本块；同时，采用一种改进的优先权计算公式，防止产生错误的修复顺序。

2.1 优先权公式改进

图像中像素点的梯度值可以反映该点处的纹理信息[11]，梯度值较大说明该点附近的纹理较为丰富。在图像修复过程中，通过修复破损区域边缘的点，使得在修复纹理的同时将结构扩散到待修复区域，所以应该优先修复梯度值较大的点[12]。

传统的Criminisi算法中，优先权值P（p）可能会随着修复的进行而出现为0的情况。如式（3）中，当破损区域上点p点处的等照度线向量⊥p与该点处的法向量np垂直时，D（p）的值为0从而可能产生错误的修复顺序[13]。

本文采用了一种改进的优先权计算公式：

引入C（p）α项后，使得P（p）不会出现等于0的情况，在一定程度上抑制了产生错误的修复顺序。

2.2 自适应样本快

传统的Criminisi算法在修复过程中使用的是9×9的样本块。然而，由于图像中不同区域具有不同的纹理结构，如果在所有的区域都采用大小相同的样本块进行修复，在一定程度上会影响修复效果。本文提出一种自适应选择样本块大小的方法，根据待修复区域内不同的结构信息，自动调节样本块大小，原理图2所示。

图2中，I为整幅图像；Ω为待修复区域，即图像的破损区域；Ω表示待修复区域的边缘；Φ表示图像未破损的区域，即为图像已知部分。P1、P2、P3为待修复区域边缘Ω上的点，ΨP1 （较小框）、ΨP′1（较大框）、ΨP2、ΨP3分别为以P1、P2、P3为中心的待匹配块。图2中，P1、P2附近区域的结构变化比较明显，故选择较小的样本块进行修复，而P3附近区域的结构比较平坦，故选择较大的样本块进行修复。从图中可以看出，比较以点P1为中心的两个大小不同的样本块ΨP1 和ΨP′1，ΨP′1中所包含的已知区域的结构信息较ΨP1更加复杂，在使用ΨP′1将无法使正确的纹理延伸到破损区域内部，从而出现断层、错位等现象，进一步说明了在结构复杂的区域应选择较小的样本块。

2.2.1 确定自适应样本块大小

图像的梯度在一定程度上可以反映图像各区域中细节的反差和纹理结构的变化，通常，图像中某像素点的梯度值越大，其附近区域的纹理越丰富，结构差异越大，在该点处使用较小的样本块；对于梯度值较小的像素点，其附近的区域结构差异相对较小，则使用较大的样本块。

在数字图像中某点P（x，y）处的梯度值可以利用差分近似求导计算：

2.2.2 本文改进算法流程

本文算法的步骤如下：

1）计算待修复区域内优先权最高的点，按照以下方法确定待修复块的大小：

2）全局搜索最佳匹配块，并将最佳匹配块中的像素值填充到待修复块中对应的位置；

3）更新置信度值C（p）；

4）重复以上步骤，直至修复完成。

3 仿真结果与分析

实验仿真过程中，对cloth、leaf和paper三幅具有不同破损程度和不同区域结构的测试图像分别采用Criminisi算法[9]和本文改进算法进行修复。图3、图4和图5分别是cloth、leaf和paper三幅破损图像的修复结果对比图。

由对比图中的修复结果可以看出，Criminisi算法在修复三张不同的测试图像时，均出现了不同程度的错位现象，cloth、paper原图像中部分区域结构性较强，若对这类图像进行修复时采用较大的样本块，则无法将正确的纹理延伸到破损区域的内部，从而导致了错位的产生。而本文的改进算法中，根据测试图像区域特征，修复过程中能够自适应地采用不同大小的样本块，对比三幅测试图像的修复效果，本文改进算法能够较好地修复破损区域，整体修复效果相对于Criminisi算法有较大提升，仿真结果说明了本文改进算法的有效性和优越性。

4 結语

本文研究了基于纹理合成的Criminisi图像修复算法，在采用改进的优先权计算公式，有效降低错误的修复顺序的基础上，通过进一步改进样本块大小的调整方式，提出了一种能够自适应调整样本块大小的方法，能够有效防止修复过程按错误的纹理方向进行。实验结果表明，本文的改进算法相较于Criminisi算法具有较好的修复效果。

参考文献：

[1]王晓华， 许雪， 王卫江，等. 一种稀疏度拟合的图像自适应压缩感知算法[J]. 北京理工大学学报， 2017（1）：88-92.[2]李梅菊， 祁清. 数字图像修复技术综述[J]. 信息通信， 2016（2）：130-131.

[3]徐黎明， 吴亚娟， 张波. 基于八邻域的自适应高阶变分图像修复算法[J]. 图学学报， 2017， 38（4）：558-565.

[4]胡云康， 姜苏， 吴志荣，等. 基于改进的纹理合成图像修复算法[J]. 软件， 2016， 37（4）：60-63.

[5]李英， 杨秋翔， 雷海卫，等. 基于深度图像绘制技术的Criminisi算法的改进[J]. 计算机工程与设计， 2017， 38（5）：1287-1291.

[6] 胡海平， 刘晓振. 一种基于非局部BSCB模型的图像修复方法[J]. 应用数学与计算数学学报， 2015， 29（3）：374-382.

[7] 杨陈东， 侯海娜. 基于改进TV修复模型的椒盐噪声去除算法[J]. 计算机与数字工程， 2016， 44（11）：2118-2123.

[8]王军锋， 裴艳侠， 王涛. 图像修复的CDD模型新算法[J]. 计算机系统应用， 2016， 25（8）：135-138.

[9]韩明珠， 郭树旭， 臧玲玲，等. 基于样本块的图像修复改进算法[J]. 计算机工程与应用， 2015， 51（16）：192-194.

[10]曾接贤， 王璨. 基于优先权改进和块划分的图像修复[J]. 中国图象图形学报， 2017， 22（9）：1183-1193.

[11]胡昭华， 鞠蓉， 李容月，等. 基于梯度纹理特征的稀疏跟踪方法[J]. 小型微型计算机系统， 2016， 37（8）：1857-1861.

[12]王相海， 孙丽， 万宇，等. 非局域样本填充和自适应曲率驱动模型的遥感图像修复算法[J]. 模式识别与人工智能， 2016， 29（8）：735-743.

[13]亓卓亚， 苏红旗. 基于Criminisi算法的图像修复顺序的研究[J]. 无线互联科技， 2016（3）：120-122.