基于改进匹配区域的虚拟化图像修复算法

文/封啸 何金鑫 高溪 戴磊

在图像修复领域，经典的图像修复算法有两类:第一类是图像润饰（inpainting）方法，由Bertalmio[4]等人提出通过修复边界的等照度线方向传播信息的各项异性扩散的三阶PDEs 模型(BSCB 模型)，Chan等将图像去噪中的（TV）模型应用于图像修复，提出了整体变分模型以及基于曲率驱动扩散模型等，但当面临修复较大区域或纹理较强的破损区域问题时，修复效果不理想。第二类是基于纹理合成的图像修复方法，以Criminisi [5]等人提出的结合待修复点的几何结构以及相关领域的置信度，计算出修复的顺序从而实现模拟人工修复图像的过程，基于块的纹理合成修复模型，通过全局搜索来匹配样本块，然后借助复制对图像缺损区域进行填充，实现图像由边缘缺损逐步向内修复的算法。本文针对第二类算法的不足进行了改进。

1 算法简介

1.1 原始的Criminisi算法

如图1所示，此算法先通过计算目标区域中沿轮廓线截取的方形模板Ψp的优先级，它的优先级大小由下面两部分构成：第一部分是该模板中的数据值，第二部分是该模板的置信值，最终的该模板的优先级就由这2部分共同构成。计算出最高优先级后对该区域进行扩散纹理和结构处理，方法是从源区域取样，寻找和该模板最匹配的模板，然后将相应的像素点复制填充到目标区域的待修复模板中。随着模板内剩余像素的填充完毕，重新更新该模板内像素的置信值。算法重复以上过程，直到填充全部完成。

1.2 原始算法存在的问题

Criminisi原始算法的缺点主要体现在以下两个方面：

（1）算法对于优先级的计算：随着目标区域修复算法填充的进行,对模板数据的值没有进行更新，从而导致模板数据会随着修补过程不断降低，这便导致后面修补过程中计算出的置信值不可靠。因此产生错误的填充顺序,最终使修复效果不尽人意。

（2）该算法采用全局搜索算法来寻找最优匹配块，这不仅产生大量多余运算影响修复速度，还会产生错误的修复顺序。

1.3 原始算法改进

我们对算法进行了如下几点的改进，其主要分为以下两个步骤：

1.3.1 计算优先级（改进Criminisi算法公式）针对原始Criminisi算法中计算模板优先级只是简单的由模板数据值和模板置信值的乘积构成，未能充分反映模板中纹理信息和结构信息的分布情况对图像恢复造成的影响，改进算法特设置了分段函数针对不同的情况分别处理。

公式1中，C(p)和D(p)分别表示模板的置信度值和数据值，α和β为调节参数，取α=0.382，β=0.618。公式2中，C(q)表示模板内像素点的置信值，np是轮廓线在p点的单位法向量，是在点p的等照度线的强度和方向。

图1：基于纹理合成的图像修复

公式1中的分段函数表示当数据项为零时,只要置信度项足够高,模板也可以得到优先修复；当数据项不为零且置信度项值大于等于0.5时，变乘为加，让数据项占主导因素,即采用结构优先的修复方法；当数据项不为零且置信度项值小于0.5时，仍采用Criminisi算法的优先级计算方法，可使两项相互抑制，保证修复顺序从外向内逐渐扩散。

1.3.2 匹配区域和最佳匹配块的改进

使用来自整个图像的已知信息执行Criminisi算法下的匹配，以确定具有轮廓线上具有最高优先级的模板的最佳匹配块。搜索空间由模板组成，模板由已知区域的像素组成。这个过程很耗时。与要恢复的模板相关的源图像的信息仅存在于特定区域中。基于纹理局部性和稳定性的马尔可夫随机场模型，新算法将匹配区域缩小到S×S方形邻域，其中像素点将被恢复为中心像素。匹配邻域S×S的大小可以由损坏区域的形状确定。重复测试和验证大量图像可以将受损区域的大小保持在m×n之内。新算法设置K = min（m，n）和S =2×K + 1。

在Criminisi算法中，搜索最佳匹配块的顺序是从上到下，从左到右。该算法在匹配区域中搜索要恢复的块的候选块。实现SSD计算以识别最佳匹配块。给定与将要恢复的块的最小SSD相同的匹配过程创建多个候选块。如果最佳匹配块与要恢复的块相距很远，则仅确保与块中的已知像素的特征一致以进行恢复。其余部分的特征可能与预期结果不一致。一旦复制了错误匹配块，以下匹配块搜索将导致差的再现过程。图2显示了具有5×5测量的类似块。图2（b）和图2（c）中的任何块都可用于恢复图2（a）。图2（c）的修复效果应该是最好的，因此图2（c）是真正的最佳匹配块。

Criminisi算法中的匹配使用SSD计算。不考虑图像纹理，仅考虑将要恢复的块的对应像素与所选择的匹配块之间的色差，不包括对应位置的梯度差。提出以下匹配函数来解决问题：

在公式（5）中，表示最佳匹配块并表示要恢复的块。在公式（6）中，表示待恢复块与匹配块之间的距离，m表示待修复块中的像素数，Vip待恢复块中第i个像素的颜色值，Vip表示匹配块中第i个像素的颜色值，Iip表示待恢复块中第i个像素的梯度值，Iiq'表示匹配块中第i个像素的梯度值。新的匹配功能确保了两个块的颜色和纹理的最小差异。

2 系统实现流程

2.1 项目实施的具体步骤

（1）标记确定待修复图像中的待修复区域，本算法采用手工标记；

（2）选取待修复区域和已知区域交界的轮廓线；

（3）计算轮廓线上模板的数据值和置信度值，引入Sobel算子，优化数据值和置信度值的计算；

（4）引入调节参数，根据模板的数据值和置信度值计算模板的优先级，确定具有最高优先级的待修复模块；

（5）在待修复模块邻近的已知区域内，按照与待修复模块中心点的距离远近，由近及远的搜索所有匹配块，寻找与待修复模块最相似的最优匹配块；

（6）在待修复模块的相应位置用最优的匹配块所对应的像素点填充，然后依据最优匹配块对应的SSD值和设定的颜色阈值的大小关系的不同，更新新填充像素点的置信度值；

（7）对待修复区域重复步骤（2）～（6），直到待修复区域全部填充完毕。

2.2 效果展示

图3、图4为本文章法修复效果对比图。

2.3 实验结果分析

本修复系统采用VisualC++6.0作为开发平台，表1中分别对图3、图4中缺失像素的个数以及两种算法修复所需要的时间进行统计，图像修复效果如图3、图4所示，在改进其优先级计算和最优匹配块搜索的基础上，明显看出本文所使用的算法恢复效果良好，基本没有瑕疵，在还原背景区域时，没有出现断层区，以及纹理扭曲、色素差不匹配等问题。

3 结论

本文在基于Criminisi算法上，针对其所存在的问题，通过引入颜色直方图以及待修复块周边像素的信息，对Criminisi算法的优先级计算方式、样本块大小和相似性度量等方面进行了部分改进。最终得出实验结果，本文的算法在视觉修复效果上要优于Criminisi算法,更加与人类视觉系统的特征相吻合;另外本算法只是在局部进行运算,所以大大的减少了修复所需要的时间。此算法对于破损区域复杂、结构性很强、纹理不太明显的图片上，其修复效果依然会存在一定的修复误差。针对不同类型的图像修复,本文算法的通用性仍存在不足。如何更好的建立算法的通用性和自适应性,这是今后的工作需要进一步研究的问题。

表1：原始算法与改进后算法修复时间对比

图2：类似的样本块

图3：文物瓷盘的修复效果

图4：海滨风光的修复效果