一种基于区域搜索的快速图像修复算法

张巧焕，唐向宏，任 澍

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

0 引言

图像修复是图像处理的一个分支，属于图像复原的研究领域。图像修复是指根据图像破损区域的已知邻域信息来对破损区域进行修复的技术［1－4］。目前，图像修复主要分为基于结构图像的修复和基于纹理图像的修复两种方法。前者由文献1最早提出，它使用一种偏微分方程来实现图像的修复，适用于修复小尺度的缺损。后者最早由文献2提出一种基于象素的纹理合成，主要适用于修复大面积的破损。之后，文献3提出一种基于样本的图像修复算法，本文称之为Criminisi算法，它将结构信息和纹理特征结合起来，取得了不错的合成效果，目前已经成为纹理合成技术中的典型算法。国内的一些学者针对图像修复中存在的问题，也提出了一些改进算法［5－7］。本文针对文献3中采用全局搜索进行匹配耗时严重的问题，探讨在保证图像修复质量的前提下，图像最优匹配块的搜索区域的确定准则。

1 Criminisi算法的基本原理

Criminisi算法的修复图像过程主要分为3个步骤:(1)优先级的计算;(2)搜索最优匹配块并填充待修补区域;(3)更新置信度和提取新的修复边缘。

优先级的定义，即是待修复边缘上任意象素点p的优先级函数P(p)定义为［3］:

式中，置信度项C(p)和数据项D(p)分别为:

式中，|Ψp|表示Ψp的面积，α是归一化系数(例如，对于8位的灰度图像，α=255)。C(p)用来度量象素点p周围可靠信息的数目。初始化时，置C(p)=0∀p∈Ω;C(p)=1∀p∈I－Ω。D(p)表示每次迭代时轮廓∂Ω处等照度线与边界法向量的内积，两者的夹角越小，优先级越高，它反映的是图像的结构信息。

Criminisi算法采用中颜色平方差的和(Sum of Squared Differences，SSD)为匹配准则，SSD的大小定义为:

式中，p表示待修复象素块中的象素点，q表示匹配块中的象素点，m和n分别表示图像的长度和宽度。当搜索整幅图像的已知信息区域后，找到SSD最小的象素块即为最优匹配块Ψ。

算法中未知象素的置信度更新公式如下:

2 算法的改进

对于置信度的更新。在Criminisi算法修复的过程中，是用最优匹配块中的相应象素信息填充源图像块中对应的未知象素，并用先前计算出来的源图像块的置信度来更新填充的未知象素的置信度［2］。在此过程中，没有考虑到本次修复的效果。显然，如果最优匹配块对应的SSD值越大，C(p)也应越小，Criminisi算法容易导致修复效果越来越差，从而形成它的贪婪性。

为了突出填充的象素点的置信度与本次修复效果的关系，本文规定了置信度的更新原则［5、6］:如果最优匹配块对应的SSD值小于阈值th，则填充象素点的置信度值，用源图像块的置信度值直接更新;如果SSD的值大于th，则采用下式进行更新:

对搜索区域的重新定义。在Criminisi算法中，为了找到与源图像块最匹配的象素块，搜索在整个图像区域的已知信息中进行，因此耗费时间较多。事实上，源图像中与待修复素块中信息相关的信息只存在于一定的区域中，根据马尔可夫随机场模型对纹理局域性和稳定性的认识［7］，本文将搜索区域限定在以待修补象素点为中心的S×S正方形邻域内。

搜索邻域S×S的大小可根据破损区域的形状来确定。首先确定破损区域的大致走向，即偏横向破损或偏纵向破损。假设破损区域为偏横向破损，破损区域纵向方向的最大宽度值为max。如果破损区域为‘狭长形’，即max较小，则直接用max作为正方形边长减1的一半;如果max足够大，破损区域中则包含足够多的信息，此时应当给正方形邻域增加一定的尺度，以此得到更合理的修复结果。对大量的图像进行反复实验和验证，本文取max的临界值为30，即当max＜=30，则取S=2×max+1;max＞30，S=2×max+n±1，在n为偶数时取‘+’，n为奇数时取‘－’。其中表示相邻的较大整数。反之，若破损区域为偏纵向，则max为破损区域横向方向的最大宽度值。

3 实验仿真

本文选取了多幅具有代表性的图像进行修复，并比较了改进算法与原算法进行性能。图像修复块大小为5×5，阈值th=11，图像的修复效果采用峰值信噪比值(Peak Signal to Noise Ratio，PSNR)作为客观评价指标。

首先，本文选取原算法中的图像验证本文算法的正确性，同时改进原有算法对图像进行修复，如图1所示。

图1 原文献图像Triangle图

为了验证改进算法的有效性，本文选取不同的图像进行试验，如图2、3所示。

图2 Barbara图

图3 Balls去除实验

从以上两组图像修复实例中可以发现，本文提出的改进算法在修复图2中较强结构处以及图3中较大修复区域时，修复效果比原有算法的修复效果更加贴近原始图像，也更加符合人眼视觉。

4 结束语

本文在Criminisi算法的基础上，充分结合图像结构和纹理特征，从最优匹配块的搜索区域和置信度更新角度，探讨Criminisi算法的改进方法。实验结果表明，改进算法的修复效果比原算法的有一定的提高，同时大大减少了修复时间，实现了修复的实时性。但是由于破损区域的不定形性和包含信息的不同，以及算法固有的贪婪性，在一定情况下，修复结构性很强的区域时仍会出现一定的修复误差，这也是今后的工作需要解决的问题。

［1］ Bertalmio M，Sapiro G.Image Inpainting［C］.New York:Proceedings of SlGGRAPH，2000:417－424.

［2］ Efros A，Leung T.Texture synthesis by non-parametric sampling［C］.Kerkra:Proceeding of the Intemational Conference on Computer Vision，1999:1 033 － 1 038.

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

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

［5］ 代仕梅，张红英，曾超.一种基于样例的快速图像修复算法［J］.微型机与应用，2010，29(22):34－36.

［6］ 杨秀红，王慧琴，李苏莉.基于自适应模板和置信度更新的图像修复算法［J］.电子科技，2009，22(12):69－72.

［7］ 付绍春，楼顺天.基于区域纹理合成的图像修补算法［J］.电子与信息学报，2009，31(6):1 319－1 322.