基于Criminisi算法的图像修复研究

Research on Image Restoration Based on Criminisi Algorithm

摘要: 数字图像修复在2000年首次提出，关键应用领域包括文物保护和电影特效制作，其中Criminisi算法备受研究关注。本文针对Criminisi算法仅适用于纹理信息丰富或大区域破损图像修复的局限性展开研究，结合权重与距离参数更新Criminisi算法的优先权计算公式和匹配块匹配策略，提出一种新的Criminisi改进方法，以提高算法的适用范围和修复的图像质量。本文引入权重系数以度量优先权公式中置信度项和数据项的信息，同时引入待修复块与全局最佳匹配块间的欧氏距离作为匹配块搜索新策略，通过调节比例系数调整不同应用场景的搜索策略，以增强匹配块与待修复块的相似性。最后，本文使用PSNR作为客观评价指标，在Matlab平台完成不同图像修复任务和应用场景的修复对比实验，结果表明，本文方法不仅有效提高修复图像的平均PSNR，还能更好地适应不同修复任务及其应用场景，为数字图像修复领域的深入研究与应用提供一定价值的参考。

Abstract: Digital image restoration was first proposed in 2000, and the key application fields include cultural relics protection and film special effects production, among which the Criminisi algorithm has at-tracted much research attention. Aiming at the limitation that Criminisi algorithm is only suitable for repairing damaged images with rich texture information or large areas; this paper proposes a new Criminisi improvement method by combining weight and distance parameters to update the priority calculation formula and matching block matching strategy of Criminisi algorithm to im-prove the application range of the algorithm and the quality of the restored image. In this paper, the weight coefficient is introduced to measure the information of confidence items and data items in the priority formula, and the Euclidean distance between the block to be repaired and the glob-ally best matched block is introduced as a new search strategy for matched blocks. The search strategy for different application scenarios is adjusted by adjusting the proportional coefficient to enhance the similarity between the matched block and the block to be repaired. Finally, this paper uses PSNR as an objective evaluation index to complete repair comparison experiments of different image repair tasks and application scenarios on the Matlab platform. The results show that the proposed method can not only effectively improve the average PSNR of repaired images, but also better adapt to different repair tasks and their application scenarios. It provides a valuable refer-ence for the in-depth research and application of digital image restoration.

1. 引言

数字图像修复技术 [1] 是数字图像处理技术的一个重要分支，广泛应用于文艺创作、文物保护和电影特效制作等领域 [2] 。信息丢失在图像的压缩、存储和传输过程中普遍存在，特别是老旧照片、壁画、书籍等受损文物 [3] [4] 。过去只能依靠人工方法进行繁琐而严谨的修复工作，尤其在文物保护方面风险较大，一旦出现错误就可能永久损坏文化遗产。随着计算机技术的飞速发展，人们可以通过数字化手段将这些作品传输至计算机，由专业人士进行修复，既能提高效率，也可以降低成本、提高安全性，为文物保护和文艺作品修复带来新的机遇。

此外，数字图像修复技术在电影特效制作等领域也发挥着关键作用。不论是电影制作还是日常生活，人们可能需要从图像中移除人物或物体，同时保持图像的协调性和完整性，数字图像修复技术的应用能有效解决此类问题、获得期望图像 [5] 。

数字图像修复方法可分为基于结构 [6] [7] [8] 、基于纹理 [9] [10] [11] 和基于深度学习 [11] [12] [13] [14] 三大类 [15] [16] 。基于结构的方法以单个像素为基本修复单元，利用扩散原理进行修复，它的鲁棒性较差，容易导致修复区域模糊。基于纹理的方法，典型的代表是Criminisi等人提出的基于样本块的算法，即Criminisi算法，它能够有效修复图像并保留纹理信息，适用于大区域破损图像的修复。基于深度学习的方法，依赖卷积神经网络进行图像修复，它包括基于生成对抗网络(Generative adversarial network, GAN)、自编码器(Auto-Encoder, AE)和Context Encoders (CE)等算法。GAN算法需要大规模数据集进行反复训练，要求迭代次数多，且容易产生伪影，小数据集的应用效果较差。AE算法修复结果会导致模糊，而CE算法原理复杂，难以实现。

Criminisi算法 [17] 是一种基于样本块和纹理的图像修复算法，在纹理信息丰富的文化遗产修复工作方面表现出色，如壁画等古建筑及文物 [18] 。尽管该算法已取得显著成果，但仍然存在改进潜力与提升空间需要学者们深入研究与完善 [19] [20] 。许多学者已提出涵盖算法中的分块 [21] 、结构 [22] 和边缘信息 [23] 等关键特征的改进算法，它们表现出更好的性能 [24] 。本文更新Criminisi算法的匹配块匹配策略和优先级计算公式，结合实验结果和客观指标评估，验证改进方法提升图像修复效果的有效性及实用性。

2. 相关工作

Criminisi算法

如图1所示，Φ为破损图像中信息完整的部分，Ω为破损图像中信息缺失的部分， $\partial \Omega$ 为两者的边界，p为边界上的一个像素点， ${\psi }_p$ 为以p点为中心的待修复块， $\nabla I_p^{\perp }$ 为p点的等照度线方向， $n_p$ 为p点的法向量。Criminisi算法主要包含三个步骤：选择并计算待修复块的优先级、最佳匹配块的搜索与填充和置信度的更新。

Figure 1. Schematic diagram of Criminisi image restoration algorithm

图1. Criminisi图像修复算法示意图

首先，在边界 $\partial \Omega$ 上选择并计算修复块 ${\psi }_p$ 的优先级，其计算公式如下：

$P\left(p\right)=C\left(p\right)\cdot D\left(p\right)$ (1)

其中， $C\left(p\right)$ 是像素块 ${\psi }_p$ 的置信度项， $D\left(p\right)$ 是像素块 ${\psi }_p$ 的等照线度强度，它们的计算公式如下：

$C\left(p\right)=\frac{{\displaystyle {\sum }_{q\in {\psi }_p\cap \Phi }C\left(q\right)}}{\left|{\psi }_p\right|},D\left(p\right)=\frac{\left|\nabla I_P^{\perp }\cdot n_p\right|}{a}$ ，a为归一化参数 (2)

Criminisi算法规定：像素块 ${\psi }_p$ 中属于信息缺失区域Ω像素点置信度为0，属于信息完好区域Φ像素点的置信度为1，即：

$C\left(p\right)=\{\begin{array}{l}0,p\in \Omega \\ 1,p\in \Phi \end{array}$ (3)

在计算优先权并确定选择优先权最高的待修复块后，需要在信息完整的区域Φ寻找最佳匹配块进行填充，待修复块与寻找的最佳样本块(匹配块)的匹配公式如下：

${\psi }_{\hat{p}}=\arg \left(\min \left(d\left({\psi }_{\hat{p}},{\psi }_p\right)\right)\right),{\psi }_p\in \Phi$ (4)

其中， ${\psi }_{\hat{p}}$ 是匹配块、 ${\psi }_p$ 是待修复块， $d\left({\psi }_{\hat{p}},{\psi }_p\right)$ 是两者之间的灰度或颜色差值的平方和，以彩色图像RGB为例：

$d\left({\psi }_{\hat{p}},{\psi }_p\right)={{\displaystyle \sum }}^{\text{}}\left[{\left(R\left(a\right)-R\left(b\right)\right)}^2+{\left(G\left(a\right)-G\left(b\right)\right)}^2+{\left(B\left(a\right)-B\left(b\right)\right)}^2\right],a\in {\psi }_{\hat{p}},b\in {\psi }_p$ (5)

当 $d\left({\psi }_{\hat{p}},{\psi }_p\right)$ 达到最小值时，即视为匹配成功并将匹配块的信息复制填充至待修复块。

最后，需进行置信度的更新，即匹配成功后需要重新计算新边界和更新置信度，置信度的更新公式： $C\left(p\right)=C_{\left(\hat{p}\right),\forall p\in \psi ,\hat{p}\in \Omega }$ ，完成置信度的一轮更新后，循环算法直至图像修复的任务结束。

3. 研究方法

3.1. 更新优先权公式

由式(1)可知，Criminisi算法的第一步是选择并计算待修复块的优先级，优先权的计算公式如下：

$P\left(p\right)=C\left(p\right)\cdot D\left(p\right)$ (6)

其中， $C\left(p\right)$ 为像素块的置信度项，表征像素块中已知信息的多少； $D\left(p\right)$ 为像素块的数据项，表征像素块的等照度线强度，即纹理信息的强弱；本文引入权重系数 $\alpha$ 对优先权公式进行更新：

$P\left(p\right)=\alpha \cdot C\left(p\right)+\left(1-\alpha \right)\cdot D\left(p\right),\alpha \in \left[0,1\right]$ (7)

3.2. 更新匹配块匹配策略

在计算确定待修复块的优先权后，Criminisi算法需在全局搜索最佳匹配块，匹配度量的公式如下：

$d\left({\psi }_{\hat{p}},{\psi }_p\right)={{\displaystyle \sum }}^{\text{}}\left[{\left(R\left(a\right)-R\left(b\right)\right)}^2+{\left(G\left(a\right)-G\left(b\right)\right)}^2+{\left(B\left(a\right)-B\left(b\right)\right)}^2\right],a\in {\psi }_{\hat{p}},b\in {\psi }_p$ (8)

式(8)为待修复块与匹配块的颜色差平方和，它只考虑两者像素颜色之间存在的差异；为了获得更好的匹配效果，本文添加待修复块与匹配块的中心点像素间的欧式距离 [25] 作为空间距离项，示意图2如下：

Figure 2. Distance between the center point of the block to be repaired and the matching block

图2. 待修复块与匹配块中心点间距离

假设P₁、P₂在图像中的位置信息记为 $P_1\left(x,y\right)$ 、 $P_2\left(xx,yy\right)$ ，则两者间的欧式距离可记为：

$d\left(P_1,P_2\right)=\sqrt{{\left(x-xx\right)}^2+{\left(y-yy\right)}^2}$ (9)

本文引入比重系数 $\beta$ 对块差异和块距离进行比重分配，作为匹配块新的搜索匹配策略，其表达式如下：

$d=\beta \cdot d\left({\psi }_{\hat{p}},{\psi }_p\right)+\left(1-\beta \right)\cdot d\left(P_1,P_2\right)$ (10)

其中， $\beta$ 为比例系数， $\beta \in \left[0,1\right)$ 。

4. 结果与评价

4.1. 实验装置

本文在英特尔(R)酷睿(TM) i5-7300HQ CPU和12.0 GB内存的NVIDIA GeForce GTX 1050图形处理器的PC上运行Matlab软件完成所有实验。实验分为两部分：第一部分调节优先权计算公式的权重系数 $\alpha$ ，调整间隔为0.05，记录所有实验组数据及结果；第二部分调节搜索匹配块度量策略的比例系数 $\beta$ ，间隔为0.05，记录所有实验组数据及结果。最后根据实验数据和实验结果绘制图表，分析总结实验。

4.2. 评价指标

本文采用数字图像修复中常用的一种评价指标–峰值信噪比(Peak Signal-to-Noise Ratio, PSNR) [26] ，它用于衡量两张图像之间的差异性，例如压缩图像与原始图像，评估压缩图像质量；复原图像与Ground truth (真实图像)，评估复原算法的性能。PSNR的公式如下：

$\text{PSNR}=10\times \lg \left(\frac{{\text{MaxValue}}^{\text{2}}}{\text{MSE}}\right)$ (11)

其中，MSE为两张图像的均方误差，MaxValue为图像像素的最大值，本文图像为8位比特图像，因此 $\text{MaxValue}=2^8-1=255$ 。

MSE公式：

$\text{MSE}=\frac{1}{mn}{\displaystyle \underset{i=0}{\overset{m-1}{\sum }}{\displaystyle \underset{j=0}{\overset{n-1}{\sum }}{\left[I\left(i,j\right)-K\left(i,j\right)\right]}^2}}$ (12)

PSNR最小值为0，当PSNR低于20 dB时，图像的质量很差、失真严重不可被接受；当PSNR大于20 dB且小于30 dB时，图像的质量较差、失真严重；当PSNR大于30 dB且小于40 dB时，图像的质量较好、失真不易察觉；当PSNR大于40 dB时，图像的质量接近原始图像。PSNR的值越大，说明两张图像的差异越小、失真越少，理论上修复的图像效果越好。

4.3. 优先权公式更新

为了方便对分析实验结果，下面列出Criminisi算法的优先权计算公式和本文的优先权计算公式：

Criminisi：

$P\left(p\right)=C\left(p\right)\cdot D\left(p\right)$ (13)

New Criminisi：

$P\left(p\right)=\alpha \cdot C\left(p\right)+\left(1-\alpha \right)\cdot D\left(p\right),\alpha \in \left[0,1\right]$ (14)

由图3可知，更新Criminisi算法的优先权公式后，在 $\alpha \in \left[0,0.65\right]$ 区间内本文方法修复图像的PSNR明显高于Criminisi算法；但在图4清晰可见，本文方法在运行程序进行修复的时间上成本明显增加，当想要应用区间 $\alpha \in \left[0,0.65\right]$ 取得更高的图像修复质量时，需要增加一定的程序运行时间成本。

Figure 3. PSNR comparison

图3. PSNR对比

Figure 4. Program run time comparison

图4. 程序运行时间对比

我们从人物、物品、文字和纹理四个角度挑选图像测试算法的修复性能，记录的数据如下：

Table 1. Update priority formula test data

表1. 更新优先权公式测试数据

通过表1数据发现，本文更新优先权计算公式的方法虽然能小幅提升修复图像在人物、物品、文字和纹理的PSNR，但会急剧增加执行修复程序的时间成本，在实际应用中需要平衡性能与成本。

如图5所示，本文选取物品修复测试中的一组图片，本文使用纯色对相机三脚架进行“人为”破坏，执行Criminisi算法和更新优先权计算方法，验证本文方法的有效性。观察图组，本文方法在修复的视觉效果上更为合理自然，Criminisi算法修复的三脚架上存在颜色不匹配的“突兀”部分，它们的PSNR分别为35.3053和34.0104，修复时间分别约为163 s和18 s。

Figure 5. Camera tripod repair results

图5. 相机三脚架的修复结果

4.4. 匹配块搜索策略更新

为了方便分析实验结果，这里列出Criminisi算法的匹配块搜索策略和本文的匹配块搜索策略：

Criminisi:

$d\left({\psi }_{\hat{p}},{\psi }_p\right)={{\displaystyle \sum }}^{\text{}}\left[{\left(R\left(a\right)-R\left(b\right)\right)}^2+{\left(G\left(a\right)-G\left(b\right)\right)}^2+{\left(B\left(a\right)-B\left(b\right)\right)}^2\right],a\in {\psi }_{\hat{p}},b\in {\psi }_p$ (15)

New Criminisi:

$d=\beta \cdot d\left({\psi }_{\hat{p}},{\psi }_p\right)+\left(1-\beta \right)\cdot d\left(P_1,P_2\right)$

$d\left(P_1,P_2\right)=\sqrt{{\left(x-xx\right)}^2+{\left(y-yy\right)}^2},\beta \in \left[0,1\right)$ (16)

由图6可见，引入待修复块与匹配块的欧氏距离 $d\left(P_1,P_2\right)$ ，在比例系数的调节下，本文匹配块搜索策略修复图像的PSNR整体表现优于Criminisi算法；当只以欧氏距离作为策略度量项时，即比例系数 $\beta =0$ ，本文新方法的PSNR约为38.2、原方法的PSNR约为39.6，本文方法修复图像的PSNR略低于Criminisi算法，这一结果验证本文综合考量块差异和块距离的正确性和有效性。在实际应用中，可以选取 $\beta \in \left(0,0.3\right]$ 的区间以获得更好的图像修复结果。观察图7，本文策略修复图像的执行时间基本与Criminisi算法持平，在本文算法修复图像的PSNR取得提升的区间，运算速度也得到一定提升，如 $\beta \in \left(0,0.3\right]$ 。综上，本文提出的匹配块搜索策略取得了较为理想的结果。

Figure 6. PSNR comparison

图6. PSNR对比

Figure 7. Program run time comparison

图7. 程序运行时间对比

本文分别从人物、物品、文字和纹理四个角度挑选图像对修复算法进行测试，记录的数据如下：

Table 2. Update the test data that matches the policy

表2. 更新匹配策略的测试数据

通过表2可以发现，本文更新匹配块匹配策略的方法既能提升修复图像在人物、物品、文字和纹理的PSNR、获得更高质量的图像，也能有效降低执行修复程序的时间成本。

如图8所示，本文利用图像修复技术实现目标人物的“移除”，本文修复方法产生更符合自然景观特征、没有明显突兀感的图像，它们的PSNR分别为18.5377、17.4812，执行修复程序的时间分别为41.747427 s、40.312086 s。

Figure 8. Image removal function is realized by image repair

图8. 利用图像修复实现人物移除功能

综上所述，本文研究改进的Criminisi图像修复算法有效地提升人物、物品、文字和纹理图像的修复质量，如图9所示，未来将推广改进的Criminisi算法以满足不用应用场景的图像处理需求。

Figure 9. Examples of different applications of image restoration

图9. 图像修复的不同应用示例

5. 总结与结论

Criminisi图像修复算法虽然可以有效修复大面积破损图像并保持良好的纹理结构信息，但在不同类别及应用场景图像的修复表现上存在性能差异，本文对该问题进行深入研究，并提出改进的Criminisi算法，以期获得更好的修复结果，且能满足不同任务场景的需要。通过对Criminisi算法的优先权计算和最佳匹配块的搜索匹配策略进行改进研究与实验，计算与绘制PSNR、程序运行时间图表数据进行对比，结果表明，本文更新优先权与匹配策略的两个新方法都能有效提升修复图像的PSNR，针对不同应用需求的场景本文方法也表现出更优的性能；但本文方法相较Criminisi算法会增加时间成本，需要在实际应用中综合考量与平衡。在未来的工作中，本文将结合自适应匹配窗口 [27] 和结构张量 [28] 等特征进一步研究、优化算法，持续提高算法的性能，以实现不同场景任务的应用与推广。

致谢

感谢贵州省优秀青年科技人才计划项目(黔科合平台人才-YQK[2023]006)、贵州省基础研究(自然科学)项目(黔科合基础-ZK[2022]一般143)、贵州大学培育项目(贵大培育[2020]76号)对本文研究工作的帮助与支持，向评审人和提供帮助的相关人员表示谢意。

基金项目

贵州省优秀青年科技人才计划项目(黔科合平台人才-YQK[2023]006)；

贵州省基础研究(自然科学)项目(黔科合基础-ZK[2022]一般143)；

贵州大学培育项目(贵大培育[2020]76号)。

参考文献

NOTES

^*通讯作者。