自适应匹配窗口的Criminisi 图像修复算法*

周彩月，周崇波，吴冬梅，孙 琳

（曲阜师范大学，山东 曲阜 273165）

0 引言

图像修复的目的是填补图像缺失部分，使图像看起来尽可能自然。基于扩散的图像修复算法使用偏微分的扩散来传播等照度线或线性结构[1-4]和变分方法[5]来计算受损区域的等照度线信息、梯度信息、曲率信息等，并通过扩散机制将周围有用信息传播至受损的区域内，从而完成修复工作。基于扩散的算法主要是用于修复小尺度缺损的数字图像，比如有划痕、折痕或者污点一类的图像。该类方法由于缺少纹理的合成，对于较大的缺失区域修复效果不佳。基于纹理合成的方法，适用于大面积的修复，比如目标移除。Ciminisi 等[6]提出了一种基于样本的经典图像修复算法，通过将最相似的目标块填充到待修复区域来达到修复的目的，取得了较好的效果。但是该算法在修复过程中因为优先级的计算顺序和样本块搜索的问题，导致纹理的错误延伸和结构线断裂。Yao 等人[7]利用生物地理学优化算法的迁移和突变来搜索最佳匹配块，大大地降低了计算的复杂度。Ou 等人[8]引入影响因子，提高数据项的比重，避免优先权趋于零。Dai 等人[9]对优先权点的计算改为分式，并缩小搜索区域进行局部搜索。Liu 等人[10]使用并行算法来进行修复，保证了修复过程的快速。一些学者提出了一系列利用图像信息的自适应算法[11-13]。另一类是涉及使用稀疏先验和稀疏近似的图像修复算法，该类方法通过对图像的信号用一组稀疏组合来表示图像，然后通过信号重构的方式实现图像缺失部分的恢复。Zhang等人[14]提出了基于组的稀疏表示方法，并针对每组设计了一种有效的低复杂度自适应字典学习方法。Mo 等人[15]提出了一种自适应相似度组的概念，在自适应组上建立了自适应字典和稀疏表示模型。此外还有对整个图像执行能量函数的全局优化[16]的方法。

Criminisi 算法具有4 个主要的缺陷。第一，在计算优先权的过程中，模板的数据值将随着填充而迅速降为零，从而导致优先级的计算不可靠，以及填充顺序的不正确，影响最终的修复效果。第二，模板窗口的大小是固定的，不区分纹理结构复杂还是简单，这样会导致错误的现象。假如处理纹理信息复杂的色彩丰富的图像时，如果样本块大，则会导致修复误差变大，使修复结果不够理想。第三，匹配策略使用全局搜索方式来识别最佳的候补块，搜索过程的时间大大增加。第四，用于搜索类似块的最广泛使用的指标是差值平方和（Sum of Squared Difference，SSD），不考虑纹理，只考虑了待修块与候补块对应位置的色差。Bugeau 等人[17]的研究表明SSD 距离度量方式偏向于从统一区域复制像素。

因此，为了克服Criminisi 算法的缺陷，本文提出一种新的基于Criminisi 算法的图像修复算法，该算法包括以下三个方面的内容：

（1）稳定的优先级计算。为了保证图像结构信息的连续性，引入图像的局部亮度特征和修复块的边缘信息，将其作为优先级计算的一部分，保证图像结构的连续性，避免修复图像中断开边界，更好地恢复对象边界和；将传统的优先级函数乘法变换为更稳定的加法运算，避免了优先级值快速趋近于零。

（2）自适应确定搜索窗口的大小。根据已修复点的统计信息变化，确定一种自适应搜索范围大小，从而减少了候选块的数量，提高了图像的全局一致性。与此同时，通常只搜索与已修复点相关的位置来获取匹配块，对于模板块的大小变得不那么敏感，固定模板块的大小缺陷问题也随之解决。

（3）提出了一种新的匹配函数，在SSD 的基础上将加权的巴氏距离和互信息引入公式，确保了两个块最小的颜色和纹理的差异。

本文引言之后的部分安排如下：第1 部分简要地回顾传统Criminisi 算法；第2 部分详细介绍对Criminisi 算法的改进；第3 部分给出实验结果和比较；第4 部分对全文进行总结。

1 传统的Criminisi 算法

Criminisi 算法[6]的核心思想是通过优先权计算出破损区域边缘最先修复的待修复块，根据待修复块中未破损区域信息，在整幅图像的完好区域寻找匹配的样本块，利用最优样本块填充待修复块从而完成修复。Criminisi 算法修复过程主要包括3 个部分：优先级的计算，最佳匹配块的选择，更新置信项。在算法过程中，沿破损边界的待修复块被赋予一个临时的优先级值，这决定了它们被填充的顺序。一旦完成计算所有的优先级，具有最高优先级的待修复块被找到，然后用从未受损区域提取的数据填充该待修复块。当待修复块被新的像素值填充后，该区域的置信度被更新。

1.1 优先权计算

如图1 所示，设I为破损待修复图像，待修复区域（白色区域）表示为Ω，未受损区域（黑色和灰色区域）表示为Φ（Φ=1-Ω），为待修复区域与未受损区域的边界，p是位于边界上的任意一点。Ψp以p为中心的待修复块。

图1 criminisi 算法符号图

Criminisi 算法把边界上像素点的优先权P(p)定义为：

式中：C(p)表示置信度项，为待修复块中的已知信息之和与待修复块面积的比值；D(p)表示数据项，反映了图像结构的信息强度。它们的定义如下：

在式（2）中，|Np|为待修复块的面积。在初始化过程中，当q∈Φ时，C(q)=1；当q∈Ω时，C(q)=0。在式）中，为像素点的等照度线方向，为破损边界在点p处的单位法线向量，α为归一化因子（一般取α=255）。

1.2 最佳匹配块的选择

在边界像素点上找到优先权最大的点p之后，然后搜索最佳样本块，设Ψp表示优先级最高的待修复块，那么完好区域的最佳样本块Ψp确定方式为：

式中，d表示Ψp和Ψq之间的距离。匹配准则为欧式距离（SSD），代表待修复块和匹配块之间对应点颜色RGB 值的方差和，计算公式具体为：

1.3 更新置信项

在找到最佳样本块以后，将Ψp^中的已知像素对应复制到Ψp中破损的未知像素点。Ψp修复完毕后，更新置信项：

重复以上的步骤，直到将所有破损区域修复完为止。

2 改进的Criminisi 算法

本部分纠正上述传统Criminisi 算法的问题，提出了一种改进的Criminisi 算法。为了提高算法的性能，本文将输入图像移动到YCbCr 颜色空间中提取图像梯度，有效地提高了修复效果。在此基础上，首先改进优先权，将边缘特征和局部亮度引入优先权模型，寻找最优的待修复块。然后改进匹配策略，在这一部分，根据已修复点的统计信息确定搜索窗口的大小，并且将巴氏距离和互信息引入匹配公式，寻找最佳的匹配块，重复以上步骤，重构得到修复后的图像。整个算法的流程如下。

{修复部分}

2.1 改进的优先权的计算

在传统的Criminisi 算法中，优先级函数P(p)被定义为置信项C(p)和数据项D(p)的乘积。但在图像的修复过程中，会找到一些置信项很大且数据项值为零的像素，导致优先级值接近于零，导致填充序列不正确。为了更好地保证恢复图像修复效果，将优先级公式改进为更加稳定的加法计算。通过对边缘和局部亮度特征的提取，将Ψp内的边缘项A(p)和亮度方差信息L(p)引入优先权模型。改进的优先权为：

式中，C(p)为置信项，D(p)为数据项。α为参数，用于调整数据项D(p)所代表的结构信息在优先权中所占的比重。A(p)表示包含在待修复块Ψq内使用Canny 边缘检测器提取的边缘像素的集合与待修复块中未受损区域面积的比值，公式为：

δ(·)为指示函数，当参数为真时返回1，否则返回0。Edge 表示使用Canny 边缘检测器提取边缘像素的集合。在修复过程中，通过考虑待匹配块中的边缘信息，“强边缘”的待修复块具有更高的优先级。这样可以优先处理边缘信息，然后填充具有均匀纹理特征的块。L(p)为局部的亮度方差，将原始图像的rgb 格式转变成hsv 格式，提取h分量，计算已知像素点的亮度平均值和局部亮度方差。引入局部亮度信息L(p)，使得图像亮度均匀部分优先处理，更好地描述局部特征。

通过对优先权公式的改进，将原来算法的乘法改为加法，能够有效处理D(p)的急剧下降。在修复过程中充分考虑边缘和亮度信息，优先修复边缘块，其次纹理均匀纹理部分优先修复的概率也增加，修复过程更加合理，像素优先级修复顺序更加可靠。

2.2 匹配策略的改进

搜索范围的大小对修复有重要影响。传统的Criminisi 算法采用全局搜索，这使得搜索过程时间成本较高。由于与待修复块相关的候补块只存在待修复块的周围区域，本文利用已修复点的统计信息对搜索范围和匹配公式进行了改进。在最近邻使用较少的候选块，虽可能不是最佳的匹配块，但提高了局部图像一致性，在视觉上具有更好的效果。整个匹配策略的具体的过程如下。

（1）检查已经修复的点，以确定图像的哪些区域可能包含当前处理的点的相关块，统计相关块的合集，记作O(p)。需要注意，当前处理点的待修复块本身也被考虑在内。

（2）根据已修复点的统计信息，确定搜索窗口W的大小。窗口大小的确定为：

这里，|O(p)|=1 代表只包含当前处理点的待修复块，没有寻找到相关块。λ为参数，用于调整W的大小。可见，统计信息越多，搜索窗口越小。

（3）从搜索窗口中提取出与当前处理点的相关块，把这些相关块看作新的待修复块，以最初的待修复块为搜索窗口的中心，在搜索窗口中执行匹配。

（4）执行匹配过程，寻找最佳的匹配块。本文改进了用于匹配的距离度量，在dSSD的基础上引入巴氏距离[17]和互信息（Mutual Information，MI）。匹配具体公式如下：

在式（11）中，dMI表示待修复块和匹配块之间的互信息计算公式。互信息（Mutual Information，MI）在信息论中是根据特征和类别共同出现的概率，用来度量样本特征和类别之间的相关性，互信息越大，表示类别之间的相关程度越高。这里用来衡量匹配块的相似度。其中，H(Ψp)和H(Ψq)分表示了待修复块Ψp和匹配块Ψq的信息熵值，H(Ψp,Ψq)表示了待修复块Ψp和匹配块Ψq之间的联合熵值。具体的计算公式如下：

式中：Pi为待修复块Ψp中第i个灰度等级的像素点占整体已知像素点数的概率；Qi为匹配块Ψq中第i个灰度等级的像素点占匹配块中计算像素点数的概率；PQi为待修复块Ψp和匹配块Ψq中第i个灰度等级的像素点所占的概率。通过式（11）、式（12）、式（13）、式（14），计算待修复块和匹配块的互信息相似程度。

式（15）中，dBC代表了巴氏距离，取值介于[0,1]之间。ρp、ρq分别代表了待修复块块Ψp和匹配块Ψq的归一化直方图。当待修复块Ψp与匹配块Ψq具有相似分布时，dBC→0，导致d(SSD,MI,BC)(Ψp,Ψq)→0。为了避免这种情况，使用加权的巴氏距离，使d(SSD,MI)与1+dBC相乘。

3 实验结果与分析

本文提供了实验结果用于验证所提修复算法的有效性。为了验证本文所提算法的有效性和可靠性，选取具有代表性的传统Criminisi 算法[6]、文献[9]和文献[14]作为对照算法与本文所提算法进行主观和客观的对比分析。

3.1 主观对比

主观对比的结果常常因为评价者和评价内容的不同而产生较大差异。本文根据实验得到的图像进行主观对比，即针对同一幅破损图像使用不同的算法分别完成修复，对比得到的修复效果。

图2 和图3 分别是本文算法和对照算法在Lena图像和Pigeon 图像上的视觉实验结果。图2（c）和图3（c）为经典的Criminisi 算法修复实验结果。从修复的结果可以看出，结果中出现了多处匹配错误，修复的边缘出现了明显的断裂现象，修复的结果变成了正方形，看起来非常不自然。图2（d）和图3（d）为文献[9]方法的实验结果，从修复结果可以看出，边缘闭合度和平滑度明显优于Criminisi算法，但存在一些纹理信息进行了过度延伸，出现了很多错位现象，导致内部纹理不连贯。

图2（e）和图3（e）为文献[14]方法的实验结果，该算法减少了图像结构的断裂现象和纹理的错误延伸现象，但修复部分存在模糊。而图2（f）和图3（f）为本文中该方法的修复结果，可以看出视觉效果优于上述算法，修复结果无明显的块匹配误差，修复区域分布均匀，边缘比上述其他算法平滑。本文算法对结构信息和纹理信息进行了正确的修复，达到了理想的修复效果，说明本文对Criminisi 算法的改进是有效的。改进的算法能对损坏区域进行较好的修复，能提供更加完整、视觉效果更优的修复结果。

图2 Lena 图像处理结果

图3 Pigeon 图像处理结果

3.2 客观对比

客观评价方法是指采用合理的客观评价算子对修复质量进行评价。本文选择峰值信噪比（Peak Signal-to-Noise Ratio，PSNR）作为客观评价算子对修复质量进行评价，其计算公式为：

式中，f(i,j)和分别表示原图和修复后的图像，其大小为M×N。

表2 给出图2 和图3 实验结果的PNSR 量化指标。从表2 可以看出，本文方法修复后的图像PSNR 均大于3 种比较算法，Lena 图像的PSNR 最大差值为7.05，最小差值为0.59。Pigeon 图像的PSNR 最大差值为17.09，最小差值为7.04。根据客观评价值，本文算法能较大程度地恢复破损图像的纹理和结构，从而更好地保持图像结构的一致性。

表2 图像修复后各种算法的PSNR 对比

3.3 参数的影响

为了全面衡量本文的改进算法，本文提供了不同参数α对应的实验结果。实验中，经验地选择了多组α参数都获得了较为满意的实验结果。图4 和图5 给出了不同参数下Lena 和Pigeon 图像的视觉修复结果。

图4 Lena 图像不同参数处理结果

图5 Pigeon 图像不同参数处理结果

从图4 和图5 可以看出，两个实验图像在不同参数下的修复结果无明显的块匹配误差，修复区域分布均匀，修复效果能满足人类视觉的需要。但对于图4，由于Lena 图像的纹理和色彩丰富，其结果在α=1,5,7 时，存在少量细微的色差点。对于图5，Pigeon 图像相比于Lena 图像，其纹理和色彩比较单一，因此不同参数上的修复效果在视觉上无明显的差别。

表3 给出了不同参数α下图4 和图5 实验结果的PNSR。在经验地设置参数过程中，发现将α的值大约设置为3 时，PNSR 最大，若将α值设置的比3 大或小许多，PNSR 值变小。但是，即使将α设置的值偏离经验最优值时，获得的PNSR 依然较为理想，这也证明图4 和图5 在不同参数下实验结果视觉效果差别不大。

表3 图像修复后不同参数的PSNR 对比

4 结语

本文在Criminisi 算法的基础上，提出了一种改进的优先级函数，以解决Criminisi 图像修复算法中图像结构不连续的问题。本文算法增加了结构信息优先级的比例、边缘信息和局部亮度特征，使其在填充图像结构信息时更加考虑其一致性，并提出了一种自适应搜索范围的方法，避免了固定样本容量对修复效果的影响。在寻找最优匹配块时，结合候选块和修复块的结构相似程度，采用基于像素和统计度量，可更准确地找到最优匹配块，并将该方法与基于其他方法的分析结果进行了对比。主观上，该方法可以保持视觉上的连通性。客观上，峰值信噪比（PSNR）值高于其他方法。