基于阈值分界和区域划分的Criminisi 改进算法的图像修复*

周先春 陈 璟 张 婕 殷新鹏 郭亮可

（1.南京信息工程大学电子与信息工程学院 南京 210044）

（2.南京信息工程大学江苏省大气环境与装备技术协同创新中心 南京 210044）

1 引言

图像修复［1~3］是通过数字图像的原有部分信息来获取缺失信息的图像处理技术。目前主流的图像修复算法主要为两类：一类是基于偏微分方程［4~7］的图像修复算法，最早Bertalmio［8］等提出等照度线方向扩散的BSCB 图像修复模型，其后CHAN［9］等将全变分模型（TV）和曲率驱动模型（CDD）［10］作为算法模型进行图像修改，这类方法对较大区域破损图像具有较好的修复效果；另一类是基于纹理合成［11~12］的图像修复算法，其中Criminisi［13］等提出的Criminisi 算法就是最经典的算法之一。后来的很多学者在其基础之上进行了更深层次的研究，崔天卿［14］等将Sobel算子的边缘检测项引入优先权函数的模型构造中，提升算法对边缘轮廓的识别能力，弥补了边缘延伸的缺陷。PATEL［15］等通过邻域检索的方式改进搜素策略来提升模型的匹配效率。LIANG［16］等将优先权函数由乘法模型变更为加权求和的形式，且引入正则化因子，更好地修复图像纹理特征。REN［17］等结合边缘结构和纹理信息，通过引入差分因子对算法进行改进，有效缓解原算法纹理延伸的现象。曾接贤［18］等将棋盘距离取代优先权函数中的匹配准则，减少修复顺序不合理导致的错误匹配现象。WANG［19］等提出用结构一致的块匹配来优化匹配准则，并引入傅里叶变换全局搜索策略，在结构相似性上有显著提升。王凤随［20］等将信息熵和梯度因子引入优先权函数，更合理地找到最优样本块来达到更好的视觉效果。周先春［21］等引入结构相似性到优先权函数构造中，且加入HSV 颜色空间来解决原算法模型匹配准则单一化的问题。

2 Criminisi算法原理

Criminisi 算法作为图像修复中的经典算法，其基于图像样本块进行图像修复。该算法主要按照边界样本块的优先级顺序，在图像信息完好区域中匹配与待修复样本块相似的目标块，然后将匹配最佳的样本块填充到待修复的破损区域，至待修复图像的破损区域被填充完全为止。

如图1 所示，是Criminisi 算法的基本原理。其中，Ω 表示图像待修复的破损区域，Φ 表示图像的信息完好区域，∂Ω 表示两区域边界轮廓；p表示目标像素点，ψp表示以p为中心的样本块；np为待修复破损区域的单位法矢量；为p的等照度矢量，其与p的梯度矢量大小相同，方向相反。

图1 Criminisi算法原理图

Criminisi算法的基本步骤如下。

2.1 优先权函数

Criminisi 算法先通过优先权函数计算区域边界的所有样本块优先级来得到样本块修复的优先顺序，优先权函数由置信度项C(p)和数据项D(p)组成，其表达式如式（1）所示：

其中，置信度项C(p)表示待修复的样本块ψp中已知像素信息所占比重，已知像素信息较多的样本块可靠性越好，其优先级越高，则应该优先修复；数据项D(p)表示样本块的结构强度信息，数据项的值较大说明边缘纹理特征信息较多，其可能处于结构边界处，优先修复可以较好保留图像结构特征的整体连贯性。置信度项C(p)和数据项D(p)如式（2）和式（3）所示：

其中，α为归一化因子，一般取值为255。

2.2 最佳匹配准则

在计算完所有轮廓边界样本块的优先权函数后，选取其数值最大的样本块作为待修复块，运用SSD 像素差平方作为匹配准则，采用全局搜索的方式从信息完整区域选择最佳匹配块用以修复图像。

SSD匹配准则如式（4）所示：

其中d(ψp′,ψq)表示待修复样本块ψp′与匹配块ψq对应像素的差值平方和，表达式如式（5）所示：

其中，IR、IG、IB和IR'、IG'、IB'分别为样本块和匹配块的像素点，且分别对应三基色通道。

2.3 更新置信度

在最佳匹配的样本块被填充到边界待修复块时，轮廓边界会发生变化，边界样本块的优先权函数值也随之改变，因此需要更新边界待修复块的中心像素点置信度。其公式如式（6）所示：

通过重复以上算法步骤，至所有待修复区域为零，即完成整幅图像的图像修补。

3 改进的Criminisi算法

3.1 优先权函数的改进

Criminisi 算法的优先权函数是采用乘积的形式进行计算，置信度项和数据项之间数据相互抑制，在平衡稳定中进行图像修复。但随着迭代次数的增加，置信度项会逐渐下降乃至趋近于零，使得优先权函数效果降低，图像块修复顺序不合理，最终导致图像修复效果差。

针对该问题，本文算法对置信度项进行改进，当其在迭代过程中衰减到指定阈值时，置信度项将被设置为常量，整个优先权函数由数据项主导来优先修复结构部分，其改进后的表达式如式（7）所示：

其中C(p)表示待修复块中像素个数占总像素个数的比例，取值范围0 ≤C(p)≤1，随着迭代次数增加，C(p)有快速下降的趋势，一方面通过使用具有平滑特性的对数函数来缓解下降趋势，另一方面当C(p)值小于阈值T时，将C(p)值设置为常量。

同时，在计算数据项时引入结构张量，结构张量能够获取图像的局部结构信息和方向信息，相较于梯度向量在修复图像时可更好地保持图像的结构连贯性。结构张量Sρ的定义如下式所示：

其中，∇I为图像梯度矢量，Ix和Iy分别为两个方向的偏导数，Gρ为标准差为ρ的高斯核函数，⊗为卷积操作。λ1和λ2分别代表了结构张量在该像素点处的最大特征值和最小特征值，通过其取值情况可以获得该处的结构信息。其表达式如式（10）所示：

当λ1和λ2值较小时，说明像素点周围灰度变化较小，其处于平坦区域；当λ1和λ2值一个较大一个较小时，说明像素点周围变化较大，其处于边缘区域；当λ1和λ2值都较大时，说明像素点周围灰度变化很大，其处于角点区域。

改进后的优先权函数如式（11）所示：

其中，S(p) 表示结构张量，α和β分别为数据项和结构张量的权重系数。

3.2 最佳匹配准则的改进

选取合适的匹配准则是Criminisi 算法的关键步骤，原算法使用单一的SSD匹配准则在匹配时只考虑待修复块与样本块的像素间距离，而没有考虑颜色、形状和结构等特征信息，易出现错误匹配的“块状效应”和混乱的纹理现象。本文将Jaccard 距离引入匹配准则，将待修复块和匹配块的像素作为集合，计算其Jaccard 距离和SSD 准则相互作用来获取更合理的匹配块。

Jaccard 指数是有限样本集合之间相似性的一种衡量指标，其定义为

式（12）中，A和B为两个集合，定义A和B为空集合时J(A,B)=1，其取值范围0 ≤J(A,B)≤1。Jaccard距离和Jaccard指数互为补充，定义如下：

两个集合的Jaccard 距离取值越小，则两者相似度越高。改进后的最佳匹配准则为

其中，η为Jaccard距离的权重指数。

3.3 样本块大小的改进

Criminisi 算法的样本块采用固定的9×9 像素大小，但这样不考虑图像纹理的局部情况，样本块过大会导致修复延伸，影响修复效果；样本块过小会使得修复时间过长，降低修复效率，因此本文提出自适应的样本块大小来匹配不同像素点的纹理情况，其样本块大小M如式（15）所示：当像素点处于角点区域，使用5×5 大小样本块；当像素点处于边缘区域，使用7×7 大小样本块；当像素点处于平坦区域，使用11×11 大小样本块；其他情况使用原来的9×9 大小样本块。

式中，λ1和λ2为结构张量的两个特征值。

3.4 搜索策略的改进

Criminisi 算法通过全局搜索策略来寻找最佳匹配块，算法的时间复杂度较高。本文通过基于纹理分割的方式来划分图像区域，在各区域内对应寻找最佳匹配块，这种局部搜索的方式一方面减少匹配时间来提升效率，另一方面提升匹配的准确率。首先通过无监督分割算法将待修复图像进行分割，然后通过颜色直方图特性合并区域，最后通过相似块匹配准则确定搜索区域来进行相似块搜索。

合并区域时，图像中会存在物体相交和间断的情况，如电线杆会将墙面分割成几个部分，或是物体间错乱陈列，因此将这些区域合并需要通过颜色和梯度特征进行分组。通过引入图像强度导数的统计特征来测量各区域颜色和图像特征。对于区域Si(i≠0 )计算其M+1 维强度矢量，前面M维部分代表强度矢量Vi(1 ) ~Vi(M)，即区域i的直方图，最后的Vi(M+1) 定义如式（16）所示：

其中，Ni是中像素点数量，‖ ∇j‖ 为像素点的强度梯度大小，μ为调节梯度信息比重的权重系数。两个相似区域Sx和Sy合并为Sxy需要满足式（17），Qx,y是两区域的相似分数，Vx和Vy为对应区域的强度矢量。

在图像区域合并后，引入图像块p的信息熵来度量待修复样本块的复杂度来缩小搜索范围，其定义如式（18）所示：

其中，pi表示图像样本库中灰度值为i的像素点比例。若是彩色图像则RGB 三通道信息熵的均值为其图像信息熵。

本文通过利用匹配块和待修复块之间的方差来体现两者之间的相似性，最终的相似块度量准则由信息熵和方差共同决定：

其中，μ+ν=1且均取值0.5。

3.5 改进后算法流程

改进后算法流程如图2所示。

图2 改进后算法流程图

4 实验结果与分析

为了验证本文提出算法的有效性，在计算机上利用Matlab2016 平台进行算法仿真试验。本文算法中参数的设置由大量实验测试获得，其中为α为0.7，β为0.3，η为0.5，T为0.5。评价标准是通过主客观结合进行比较，客观评价指标为峰值信噪比（PSNR）和结构相似性（SSIM）。

算法仿真的实验效果图如图3~5所示。

图3 Lena图像修复效果图

图3、图4 和图5 是分别对Lena 图的划痕和dxy图像的楼宇屋顶处，以及海景图像的地板进行图像修复，并将本文的算法同传统的Criminisi算法以及文献［18］提到的改进算法进行比较。通过对图3（a）、图3（b）和图3（c）的恢复图像进行对比，传统的Criminisi 算法对小区域的划痕已经具有较好的处理效果，但其在划痕周围存在纹理延伸的现象，修复后仍能看见比较明显的处理痕迹；文献［18］通过棋盘距离替代传统的数据项，对细小破损具有较好的修复效果；本文改进算法在恢复图像信息时更好地保留了原始图像的边缘结构信息。通过图4可以看出，Criminisi算法在修复屋顶时因为优先权函数的不合理性，出现错误匹配的结果而导致图像修复错误；而图4（d）可以看出文献［18］改进的算法在边缘修复上存在一些边缘不平滑连贯的现象；而本文提出的算法则可以较好地保持图像恢复后的连贯性。通过图5（c）可以看出Criminisi 算法对大区域破损图像修复效果一般，纹理细节信息处理不好；而文献［18］通过优化优先权函数更好地恢复了地板的纹理结构；本文提到的算法在处理后结构信息更加完善，地板缝隙更加清晰，具有较好的视觉效果。

图4 dxy图像修复效果图

图5 海景图像修复效果图

从表1和表2可知本文提出的算法模型在峰值信噪比上较原算法提升了约0.8dB，而在结构相似性上也有所提升，说明其结构纹理也得到更好保留。

表1 各算法仿真峰值信噪比值

表2 各算法仿真结构相似性值

5 结语

本文通过对Criminisi 算法的优先权函数进行阈值划分和结构张量的改进，并结合最佳匹配准则和搜索策略的优化，在算法的效率上有了明显提升，修复后的图像边缘信息和纹理结构得到清晰保留，图像的具有较好的整体连贯性，其峰值信噪比和结构相似性的数值也得到显著增加。