基于预填充策略的纹理合成修复

毕学慧

(阜阳师范大学 计算机与信息工程学院，安徽 阜阳 236037)

1 引言

数字图像修复即在数字图像中填补缺失的区域或破损的区域[1]，目前该技术已经成为数字图像处理的一个重要研究领域。数字图像修复技术应用广泛，在文物修复[2]、目标物移除[3]、视频修复[4]、三维实物修复[5]、图像扩展[6,7]、语义修复[8]等方面均有很深入的应用。

传统的图像修复算法主要分为两类：一类是Bertalmio 等[9]提出的基于偏微分方程（partial differential equations,PDE）模型的图像修复方法，经典 的 模 型 有BSCB 模 型[9]、TV 模 型[10]、CDD 模型[11]，这类方法模仿手工修复过程进行填补，从已知区域向未知区域扩散，着重强调结构信息的填充，但随着填充面积的增大，填充会因平滑产生模糊效应，因此常用来修复小面积区域或细长的区域。另一类是基于纹理合成[3,12,13,14]的图像修复技术，典型的模型有Criminisi 等提出的基于样例[12]的图像修复，Barnes 等提出的patchmatch 修复[14]，这类方法兼顾纹理信息和结构信息，采用样本块修复，通过计算优先权确定修复的次序，然后搜索最佳样本块填充图像，每次只修复一个样本块，适合于修复大面积区域。由于Criminisi 算法思路清晰，过程简单，修复结果好，引起了众多研究者关注并对其进行改进，在优先权函数[15]、样本块匹配[16]、自适应样本块大小[17]等方面提出了很多改进措施。

近年来，随着大数据和人工智能的发展，图像越来越容易获取，这为基于深度神经网络的图像修复提供了数据基础。例如基于上下文编码器[18]（Context Encoders，CE）的图像修复、采用对抗网络的图像修复[19]、多级网络修复[20,21]等。这种利用大数据学习的策略，很大程度上解决了样本资源不足带来的诸多问题，吸引了众多学者的深入研究。虽然基于深度学习的图像修复技术具有传统算法无法比拟的优点，但其需要大量的数据样本进行训练，这也是该技术的缺点之一。

纹理合成技术在修复图像的过程中采用块填充，由于破损区域内的信息是未知的，所以在计算其纹理信息时，容易造成计算错误。为解决此问题，考虑提前填充部分区域，在一定程度上改进图像优先权的计算，进而改变图像的修复次序，最终改善图像的修复结果。本文在Criminisi 算法的基础上，实施预填充策略，并在优先权计算和候选样本块筛选阶段进行了改进，使得修复的精度更高。实验结果表明，本文提出的方法具有很好的修复效果。

2 Criminisi 算法

Criminisi 算法的思路是先寻找破损区域的边界，然后在边界线上找具有最高优先权的填充块，利用填充块中的已知信息，搜索最相似的样本块，利用相似块中的信息填补未知的区域，更新填充边界，重复以上过程，直到所有的破损区域填充完毕。图1 给出了填充的图例。

图1 Criminisi 算法修复过程示意图

下面详细地介绍其修复过程：

Step1.寻找破损区域的边界线。假设待修复图像为I,Mask为图像的掩模图像，其中破损区域用Ω 表示，∂Ω 为待修复区域的边界，样本区域为Φ(Φ=I-Ω).

Step2.设定填充块的大小为W×W，以填充边界上的点为中心，取W×W大小的图像块，计算置信度项和数据项，进而计算优先权。置信度计算公式为：

其中，| Ψp|表示图像块Ψp内像素的个数，C0(q)是置信度的初始值，定义如下：

从式（2）可以看出，位于样本区域的像素，其置信度为1；在破损区域内的像素，其置信度为0。通过置信度项的计算可知，填充块中的已知信息越多，得到的相似块越可靠。

人对图像中的结构信息比较敏感，应优先修复结构信息。而结构信息通常用梯度信息获取。计算数据项是为了优先修复结构区域部分。数据项的公式定义为：

其中，∇I表示图像的梯度值，表示位于点p的梯度垂直方向，⊥表示垂直方向。如图1（b）所示。np是点p处垂直于边界的法线，通过式（3）可知，和np的夹角越小越好。α是归一化因子，当图像为灰度图像时，α=255。

利用置信度和数据项的乘积计算优先权，主要控制填充边界上填充块的修复次序，一方面考虑了置信度因素，包含已知信息越多的填充块，赋予优先修复；另一方面考虑了数据项因素，对结构部分优先修复。优先权的计算公式为：

Step3.比较上一步求得的优先权值，得到具有最高优先权的填充块，假设为 |Ψp|，再在图像的样本区域中寻找相似块，采用欧式距离即SSD(sum of squared difference)作为相似度计算公式，计算公式为：

其中c表示颜色通道，当图像为彩色图像时，c=3；当图像为灰度图像时，c=1。和为两个图像块对应位置上的颜色值。

通过计算距离的最小值，获得最相似的样本块，如式（6）所示。

图1（c）给出了寻找最相似样本块的示意图。

Step4.寻找到最佳样本块后，利用相似样本块填补图像的缺失区域，如图1（d）所示。更新填充边界。

Step5.如果修复没有完成，继续执行Step2-Step4，直到所有的破损区域修复完成。

3 本文方法

从图1（c）可以看出，在计算梯度的过程中，p点周围存在破损和非破损的区域，利用非破损区域的信息计算梯度的值较合理，但这些信息容易对梯度的计算造成干扰。如果填充边界向外扩展，此时计算中心点p 的梯度比较合理，但是每次填充区域较少，修复比较耗时，当图像尺度较大时，耗时更长。在修复填充区域前预填充一些信息，这样计算的梯度值更合理。

在利用颜色距离获取最佳样本块时，得到的样本块并非一定是最合适的样本块，可能导致修复失败。因此，在选择样本块时进行二次挑选，进一步缩小误差。在Criminisi 算法的基础上，本文在填充和样本筛选阶段均进行了改进。

3.1 预填充策略

在利用Criminisi 算法修复图像的过程中，发现有很多点的优先权和最高优先权的值非常接近，因此先考虑这些与最高优先权值相近的填充块，对其预填充，为下次图像填充做准备。图2 给出了一幅填充图像，红色的正方形是填充区域。在填充边界上，计算优先权的值，得到如图3a 所示的柱形图。从中可以看出，有一些点的值与最高优先权的值较为接近，这些点所在的填充块在后期会优先处理。

图2 优先权的计算

通过公式（4）可知，数据项和置信度会影响优先权的计算，置信度的波动范围较小，而数据项的波动范围较大，因此修改优先权的计算，进一步改善因数据项值较小影响优先权值的问题。

改进后的优先权计算公式为：

图3（b）给出了改进后的优先权值。根据式（7），可以看出优先权值的变化不会出现太大的波动。

图3 优先权值的计算

优先权决定填充次序，对填充边界上的点按优先权值从大到小排序，对排名前m 个的填充块进行填充，其中第1 个填充块是优先权值最大的填充块，直接进行填充，而其他m-1 个填充块是预填充。这些预填充的图像块，因为其优先权值较高，后续的填充促使其会尽快得到修补。为能够提高算法的修复效率，本文设定m=5。

预填充策略的算法如下：

输入：待修复图像I，掩模图像Mask。

Step1.利用掩模图像获取图像的破损区域，得到填充边界。利用公式（2）初始化置信度项C0。

Step2.利用公式（1）计算填充边界上每个填充块的置信度。

Step3.利用公式（3）计算填充边界上每个填充块的数据项。

Step4.利用公式（7）计算填充边界上每个填充块的优先权。

Step5.对优先权进行降序排序，取出前5 个待填充块。

Step6.对第1 个填充块（具有最大优先权值的块）进行填充，第2—第5 个填充块进行预填充。

Step7.更新第1 个填充块修复后的边界。

输出：填充第1 个修补块和预填充块图像，以及更新后的掩模图像Mask′。

3.2 相似样本块的度量

为了能够找到更加相似的样本块，采用Lab颜色空间，同时考虑梯度间的差异，对SSD 距离进行修改，得到距离公式的定义为：

其中，∇Lx和∇Ly表示在L 通道水平方向和垂直方向上的梯度值。考虑到颜色一致性，所以在Lab 空间上进行距离度量。加入梯度距离，不仅考虑颜色的整体差异，还考虑梯度分布的差异。

3.3 多候选块筛选策略

利用颜色相似性，在用公式（5）寻找相似样本块时，发现距离最小的样本块，并不一定是最佳的相似块，若选错样本块则会导致图像修复不合理，因此有必要挑选出最优相似块。

为能够找到最优相似块，在计算最相似样本块的过程中，保存每个候选块的颜色距离，利用距离值对样本块相似性进行排序。Criminisi 算法选用最小距离的样本块，我们对其进行了优化，取前10 个相似的样本块进行筛选。两个图像块的协方差矩阵可以表达两个图像块之间的结构相似性。利用协方差矩阵之间的距离计算两个图像块之间的距离，则Ψp和Ψq之间的距离可以表示为：

其中，μΨp和μΨq分别是图像块Ψp和Ψq中像素值的均值，CΨp和CΨq分别是图像块Ψp和Ψq的协方差矩阵。

再利用公式（9）筛选样本块，定义如下：

多候选块筛选策略如下：

输入：候选样本块的位置、SSD 距离值和待修复块。

Step1.利用SSD 距离对候选样本块从小到大进行排序。

Step2.挑选出前10 个距离最小的候选块。

Step3.利用公式（9）计算这10 个候选块与具有最高优先权的填充块间的S 距离。

Step4.利用公式（10）找出S 距离最小的候选块。

输出：S 距离最小的候选块。

4 实验结果与分析

4.1 参数设置

于WIN10 平台运行，Matlab2019Rb 语言编程环境下进行实验。公式（8）中的λ=0.8。修复采用的块大小为9×9。

4.2 实验结果与分析

图4 是一幅具有结构的图像，其中图（a）—（h）分别是原图、标记图、本文方法结果、Criminisi方法[12]结果、Barnes 方法[14]结果、Newson 方法[22]结果、Jurio 方法[23]结果、Anupam 方法[24]结果。通过观察可以发现，Criminisi 方法、Jurio 方法、Anupam 方法的修复结果较差。本文方法、Barnes 方法、Newson 方法的修复结果较为令人满意。表1给出了PSNR 指标值，数据表明了本文方法的修复结果较好。

图4 格子图像修复

图5 是金字塔图像，其中图（a）是原图，图（b）是标记图、图（c）—（h）分别是利用本文方法、Criminisi 方法、Barnes 方法、Darabi 方法[25]、Newson方法、Deng 方法[26]修复图像的结果。从图5 可以看出，Criminisi 方法和Deng 方法的修复结果较差。从表1 中PSNR 值可知，本文方法的PSNR值最高，表明本文的修复方法优于Barnes 方法、Darabi 方法和Newson 方法。

图5 金字塔图像修复

图6 是一幅栅栏图像，其中图（a）是原图，图（b）是标记图、图（c）—（h）分别是利用本文方法、Criminisi 方法、Barnes 方法、Darabi 方法[25]、Newson 方法、Deng 方法[26]修复图像的结果。从图6 可以看出，Criminisi 方法、Barnes 方法和Newson 方法的修复结果出现了模糊和瑕疵。通过表1 给出的PSNR 值可以看出，本文方法的修复结果优于其他方法。

图6 栅栏图像修复

表1 各种方法修复结果的PSNR 对比

除了利用PSNR 评价修复结果外，还采用了SSIM 指标进行评价。SSIM 指标是评价结构一致性的度量指标，其值越大说明修复结果和原图在结构上越相似。通过表2 可以看出，在修复金字塔图像时，Newson 方法的SSIM 指标值最大，修复效果优于本文方法。但本文方法在修复其他2幅图像时，SSIM 指标值均最高。这说明本文方法在整体上修复能力较强。

表2 各种方法修复结果的SSIM 对比

将本文提出的方法与Criminisi 方法、Barnes方法、Newson 方法和Jurio 方法的修复所耗费的时间相比，本文提出的方法比Criminisi 方法需要更多的时间。这是因为本文方法在修复过程中进行了预填充和多个候选块的筛选，所以需要花费较多的时间。但是，本文方法与Newson 方法相比，所需要的时间更少。通过对比分析可知，为了更好地修复图像，在处理过程中，本文方法加入了更多处理环节，虽然耗费了一些时间，但较好地提升了图像的修复质量。

5 结语

利用Criminisi 算法计算出的优先权容易受梯度影响，进而影响图像修复次序和修复结果。为解决此问题，本文提出了基于预填充策略纹理合成技术，对优先权的计算进行了改进，使优先权的计算更合理。在每次填充的过程中，除了修复最高优先权的填充块外，还对其他次级优先权的样本块进行了预填充，进一步保证了优先权的计算更加准确。考虑到距离最近的样本块可能并非最合理的修复块，因此利用协方差矩阵进行筛选，从而得到最相似样本块。通过理论分析和实验验证，表明了本文方法具有较好的修复效果。然而，对于旋转等复杂情况，还需要进一步研究，以提高图像的修复质量。