针对匹配块不存在的Criminisi算法改进研究

任 澍，唐向宏，康佳伦

(杭州电子科技大学通信工程学院，浙江杭州310018)

0 引言

图像修复技术主要是用来修复图像中的破损区域或者用来去除图像中的物体。属于纹理合成技术的Criminisi图像修复算法［1］，通过将最相似的目标块填充到待修复区域来达到修复的目的，取得了较好的修复效果。但是在图像修复的过程中，当已知区域中不存在合适匹配块的情况下，该算法根据相似性所选择的匹配块往往并不能满足修复需求，容易造成修复效果的失真。针对这一情况，文献2通过对优先权和搜索方式进行改进，并采用新的相似性准则来寻找匹配块，虽然获得了一定的效果，但是对于某些区域的修复仍然不是十分理想。Bertalmio利用图像分解模型将图像分解为结构部分和纹理部分，然后分别对其进行修复，对小尺度破损区域有较好的修复效果，但是对大尺度破损区域的修复容易产生模糊［3］。本文利用匹配块相似度量，即误差平方和(Sum of Squared Differences，SSD)对Criminisi算法进行了改进。通过对不良修复区域的定位，分别对结构部分和纹理部分的不良修复区域进行修复，以克服Criminisi算法中因不存在合适匹配块造成的修复失真。

1 Criminisi修复算法特征分析

Criminisi算法是一种基于样本的图像修补算法，实质是直接结合结构传输和纹理合成的方法。这种纹理合成主要由3步组成:优先权计算、搜索和复制［4－6］。在实际研究中发现，Criminisi算法在进行搜索的时候，若在已知区域中不存在合适的匹配块，算法会使用不恰当的匹配块去对破损区域进行填充，从而影响最终的修复效果。算法的修复效果如图1所示，图1(c)给出了Criminisi算法对图像破损区域的修复效果。从图1(c)中可以看到，Criminisi算法在修复肩膀处的曲线时没有保持其线性结构的平滑性，使得修复边缘出现了一定的凹凸。出现这种修复效果的主要原因是在已知区域中不存在合适的匹配块，算法所找到的匹配块并不能满足曲线的修复要求。

2 Criminisi算法的改进

基于对Criminisi修复算法的分析，本算法的改进思路为先利用匹配块的相似性度量，完成对修复失真区域的定位，然后利用基于图像分解的图像修复算法对失真区域重新修复。

图1 Criminisi算法对lena的修复效果图

2.1 修复失真区域的定位

在寻找最佳匹配块的过程中，Criminisi算法是通过对已知象素点的SSD进行计算，并将其值最小的匹配块选择为最佳匹配块［6，7］。

若将SSD值除以待修复块中已知象素个数所得的均值设为均值象素差平方和(Average Sum of Squared Differences，ASSD)。在实验中发现，当图像的已知区域不存在最佳匹配块时，虽然此时所寻找到的块具有最小SSD，但是其ASSD相比于其他待修复块仍会较大。如表1所示，表1列出了图1(b)破损区域的部分ASSD变化情况。从表1中可以看出，当修复顺序号为18时，修复块的ASSD为350，将它与先前已修复的9 个修复块的 ASSD(8、63、17、12、123、56、45、5、27)进行比较后可以发现，虽然算法在搜索时所寻找到的SSD已是最小，但它的ASSD相比于先前已修复块仍然较大，大于它们均值的3倍(350＞212)。此时若采用匹配块替换，就不能保证待修复块能得到满意的修复效果，易造成较大的偏差，从而造成如图1(c)所示的不良修复效果。为寻找这些由于不存在最佳匹配块而造成修复失真的区域(定义为un-matching)，本文采用以下方法来对其进行定位:

(1)对已修复块，按修复先后顺序以10个为一组，计算该修复组的ASSD均值(记为mean_ASSD)，并将该组中每个修复块的ASSD分别与3×mean_ASSD进行比较。若修复块的ASSD大于3×mean_ASSD，则判定该修复块为un－matching。然后，右移一位，将该组剩余修复块与后续已修复块重新组成新的一组，进行类似的判断处理，直到图像修复完毕;

(2)在修复过程中，若待修复块的中心点属于un-matching(已修复)中的坐标点(即该待修复块不完全属于un-matching)，则在其修复完之后也归为un-matching;

(3)在修复线性结构时，往往会因最后一个待修复块的不匹配而造成线性修复的不连续，因此，在修复线性结构时将最后一个待修复块归为un-matching。最后一个待修复块的判定原则为:在图像用Criminisi算法进行修复之后，按修复先后顺序对已修复块进行检索，并利用方差判断其是否为线性结构块。若是线性结构块，则检索该块周围的并且修复顺序号在其之后的修复块中是否有线性结构块，若没有，则判断该块为线性结构修复时的最后一个待修复块。

表1 图1中破损区域的部分ASSD变化情况

2.2 对修复失真区域的重新修复

当Criminisi算法对图1(b)进行修复之后，利用Vese-Osher［8］模型将修复结果分解为结构部分u和纹理部分v。对结构部分u的修复，本文首先利用un-matching将结构部分中没找到最佳匹配块的区域重置为待修复区域，如图1(d)所示。重置之后的待修复区域较小，可以使用TV模型来进行修复，但由于其修复结果容易产生模糊，因此需要使用拉普拉斯滤波器来对已修复部分进行滤波，修复并滤波的结果如图1(e)所示。从图1(e)中可以看到，结构部分修复之后，其肩膀处的曲线得到了较好的保持，取得了比较理想的修复效果。

对纹理部分v的修复本文采用文献9中的纹理合成技术来进行修复。文献9算法不能对所有纹理都有较好的修复效果，但是其中的优先权保证了在修复纹理的过程中能使线性结构部分得到较好的保持。

3 实验结果和分析

为了验证改进算法的有效性，本文在计算机上进行了仿真实验。图1(f)给出了图1(a)的修复效果，与原算法相比，改进算法对曲线等线性结构和纹理都有较好的保持，克服了原算法所固有的不足，峰值信噪比(PSNR)提高了9.108 4dB，取得了较好的修复效果。为了验证本算法的一般适用性，本文选取不同破损区域以及不同图像来进行实验，如图2、3所示。

图2 不同区域的修复效果对比图

图3 圆球去除后的效果

从图2、3的修复结果中可以看到，在修复不同的区域时，改进算法相比原算法和类似算法无论是纹理区域还是边缘区域，都有较好的修复效果，特别是在修复曲线等较强线性结构时，有效保持了边缘的线性特性，具有更好的视觉效果。

4 结束语

本文针对Criminisi算法在已知区域不存在合适匹配块的情况下易产生修复效果失真的问题，对Criminisi算法进行了改进。改进算法首先利用平均误差平方和完成对修复失真区域的定位，然后分别对分解为结构部分和纹理部分的这些区域进行修复。对于结构部分，采用TV模型及拉普拉斯滤波器进行修复滤波，对于纹理部分采用基于块的纹理合成技术进行修复，之后对图像进行重构并得到最终的修复效果。实验证明，改进算法相比Criminisi算法有更好的修复效果。

［1］ Criminisi A，Perez P，Toyama K.Region filling and object removal by exemplar－ based image inpainting［J］.IEEE Transaction on Image Processing，2004，13(9):1 200 －1 212.

［2］ 代仕梅，张红英，曾超.一种基于样例的快速图像修复算法［J］.图形、图像与多媒体，2010，29(22):34－39.

［3］ Bertalmio M，Vese L，Sapiro G，et al.Simultaneous textureand structure image inpainting［J］.IEEE Transactions on Image Processing，2003，12(8):882 －889.

［4］ 张红英，彭启琮.数字图像修复技术综述［J］.中国图象图形学报，2007，12(1):1－10.

［5］ 吴亚东，张红英，吴斌.数字图像修复技术［M］.北京:科学出版社，2010:11.

［6］ 张巧焕，唐向宏，任澍.一种基于区域搜索的快速图像修复算法［J］.杭州电子科技大学学报，2011，31(5):139－142.

［7］ 林云莉，赵俊红，朱学峰，等.改进的纹理合成图像修复算法［J］.计算机应用与软件，2010，27(10):11－12.

［8］ Vese L，Osher S.Modeling textures with total variation minimization and oscillating patterns in image processing［J］.Journal of Scientific Computing，2003，19(1/3):553 －572.

［9］ Wu J Y，Ruan Q Q.A Novel Hybrid Image Inpainting Model［C］.Shanghai:International Conference on Audio Language and Image Processing，2008:138 －142.