张 嵩，周旭亚

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

图像修复，或者图像补全，简单地说就是利用图像中的已知区域信息来填充待修复区域。图像修复的概念最早由Bertalmio等人提出［1］，他们同时给出了一种有效的基于偏微分方程(PDE)的算法，即将修复转化为求解一个特殊的偏微分方程。类似的算法还有不少［2－4］。基于PDE模型的算法对修复局部狭长的区域比较有效，但对大面积缺失或纹理信息丰富的图像，此类算法修复效果不够理想。非参数纹理合成是图像修复的另外一类重要方法，其基本思想最早可追溯至Efros与 Leung 的工作［5］。在此基础上，Criminisi等人［6］提出了一种全新的基于模板的图像修复算法，被公认为修复技术方面的重要突破，影响甚大。

但是Criminisi算法仍存在缺点，比如修复后图像纹理断层，时间复杂度较高等，对其的改进仍然是图像修复领域的一个重要研究方向。譬如，一种彻底的解决之道是所谓的全局优化方法［7－10］，即将修复问题转化为最小化能量泛函。不过，这类方法的复杂度太大，应用上有不小的限制。我们认为，Criminisi算法框架目前仍是修复效果与实现代价之间的最佳折衷。因此，我们在Criminisi基本算法框架之上融合了一些新的改进元素:我们采用了基于可变大小模板的块搜索方案；并结合改进的修复像素信度(confidence)更新公式及局部搜索模式，以期获得较好的算法综合性能。仿真结果表明系统整体性能确实得到较大提高。

本文第二节简单介绍Criminisi算法流程以方便后续论述，第三节具体介绍改进方法，第四节给出实验结果比较，第五节给出总结与展望。

1 Criminisi算法

为了更好地介绍所提出的改进方案，首先简述Criminisi算法。Criminisi算法本质上仍然属于纹理合成方法，但却能同时修复纹理和结构信息。假设图像为A，待修复区域为Ω，已知(或已修复)区域记为AΩ，当前迭代次数用t表示，Criminisi算法重复以下步骤直至所有像素都被修复。

步骤1:确定当前修复边界∂Ωt，若∂Ωt=∅，算法退出。

步骤2:对边界上的每一点p，以点p为中心的待修复块记为Ψp。对每个待修复边界点计算优先权P(p)如下:

其中，信度项C(p)定义为:

|Ψp|是块或模板大小，也即模板像素总数。初始化时，对于待修复区域所有像素C(p)置0，其他已知像素则置为1。数据项D(p)试图反映点p附近图像结构强度:

这里α是归一化因子，np是点p处边界∂Ωt的法线单位向量，⊥表示向量90°旋转。

步骤3:找出具有最大优先权的待修复块Ψp*。

步骤4:在已知(或已修复)区域中搜索与Ψp*最相似的模板Ψq*:

步骤5:把Ψq*中相应区域的像素值复制到Ψp*中未知区域。

步骤6:更新信度:

2 改进方案

Criminisi算法是一种贪婪算法，本质上是非最优(suboptimal)的，但仍不失为兼顾性能与代价的较好选择。本文在保持算法基本框架不变的情况下加入了一些有意义的改进，以下进行详述。

2.1 基于可变大小模板的匹配搜索

对基于纹理合成的串行修复算法来说，前面模块的匹配搜索精度直接影响到后续块的修复效果。这其中模板大小是一个很关键的参数。单从匹配精度而言，应当选择较小的模板；而从图像正则性及算法复杂性角度，则希望选择较大的模板。Criminisi算法采用固定模板大小，但要设定折衷上述各点并适应不同图像特征的模板大小参数实际上是不可能的，这就构成了Criminisi算法的一个重要不足。本文针对性地提出可变大小模板搜索框架，并对具体的搜索程序进行了细致设计。

图1 可变大小模板的匹配

如图1所示，p*为当前修复像素，q为目标像素。我们从某一最小模板大小PSmin(比如5×5)开始进行当前模块与目标模板之间的匹配，然后逐渐增大模板大小，从5×5到7×7，9×9 等等，直到获得最佳匹配效果。由于相邻大小模板或块成嵌套关系，因此在模板增大匹配过程中，每次只需对图1中的环状区域进行增量计算，而勿需对共同部分重复处理。另外，因模板大小是可变的，我们采用均方误差(MSD)而不是误差平方和(SSD)作为相异性测度:

其中n表示当前模板尺寸，|Σn|是块Ψp*中的已知像素个数。考虑到图像正则性与计算代价，我们还在相异性测度中结合了与模板大小相关的项，如下定义:

引入logn项的目的是鼓励大模板匹配，由此形成的广义测度有点类似于时间序列建模中的Akaike准则。两点间的匹配过程可由以下的伪代码紧凑描述:

其中PSmax为设定的最大模板大小。第四行中的条件语句意味着，一旦发现模板匹配效果有下降的趋势就终止模板扩大过程，这样能达到精度与计算复杂度的较好平衡。匹配结束后得到的最优相异性测度记为M(Ψq，Ψp*)。

通过对已知区域进行搜索，得到最优匹配模板:

所定义的广义相异性测度使不同目标点之间匹配效果的合理比较成为可能。

2.2 信度更新方式的修正

Criminisi算法在更新信度时，直接用C(p*)更新本次修复像素的信度。这样做没有考虑到本次模板匹配的精度，明显有缺陷。我们将信度更新的方式修正为:

也即匹配效果越差，修复信度也应越小，反之亦然。

2.3 模板局部匹配搜索

Criminisi算法的时间代价主要是最优匹配模板的搜索。为了减小时间复杂度，我们采用局部搜索，也即将搜索区域限制在以当前待修复点为中心的一个窗口中。这样做能使计算复杂度大幅减少，而修复精度的损失并不大。

3 实验结果

本文在VC++下进行实验，修复试验包括全彩自然图像的物体去除(object removal)以及已知图像的修复仿真。处理器平台为3GHZ的Pentium Dual-Core E5700 CPU。所有实验中，PSmin设为 5×5，PSmax为17×17；局部搜索窗口大小定为51×51。需要说明的是，在计算边界∂Ωt上的像素点修复优先权时，我们采用固定的模板大小(9×9)。

3.1 修复效果比较

图2～图6是对几幅自然图像进行物体去除试验的结果。图2是经典的Bungee图像，可以看出，改进算法在修复视觉效果方面有明显提高。对照图2(c)与图2(d)，Criminisi算法修复结果中的赝像，譬如不连续的屋顶及延伸到水中的植被等通过改进算法基本得到消除。图3和图4分别是Criminisi算法和改进算法的修复过程。图5与图6是另外两幅典型图像的修复效果，改进算法都表现出类似的优越性。

图2

图3 Criminisi算法修复过程

图4 改进算法修复过程

图7是对已知图像进行修复仿真实验的结果。对这种情况还可计算修复客观效果，也即结果图像与原图像间的PSNR，具体数据见表1，同样证明了修复效果的提升。

图5

图6

图7

3.2 时间复杂度比较

表1同时列出了Criminisi算法和改进算法的时间成本。可以看出，改进算法的时间复杂度也明显比原算法低，综合性能的改善十分显著。

表1 时间成本和PSNR

4 结论

本文在保持Criminisi图像修复算法基本框架不变的情况下，提出了一些较新颖的改进方案。我们的主要工作是设计了基于可变大小模板的高效块匹配程序，并结合信度更新修正和局部搜索以提高算法的综合性能。实验结果表明了改进措施的有效性。

我们下一步的工作希望将改进方案与多分辨率修复框架［11－12］进行结合。此外，探索结合图像结构的模板广义相异性测度［8，13］和图像分割［14］亦是很有意义的研究方向。

［1］Bertalmio M，Sapiro G，Ballester C，et al，Image Inpainting［C］//ACM SIGGRAPH，2000，417－424.

［2］Chan T，Shen J.Local Inpainting Models and TV Inpainting［J］.SIAM J.Appl Math，2001，62:1019－1043.

［3］Chan T，Shen J.Non-Texture Inpainting by Curvature Driven Diffusion(CDD)［J］.J Visual Comm Image Rep，2001，12(4):436－449.

［4］Chan T，Kang S，Shen J.Euler’s Elastica and Curvature Based Inpainting［J］.SIAM J Appl Math，2002，63(2):564－592.

［5］Efros A，Leung T.Texture Synthesis by Non-Parametric Sampling［C］//Proc IEEE Int Conf Computer Vision，1999，2，1033－1038.

［6］Criminisi A，Perez P，Toyama K.Region Filling and Object Removal by Exemplar-Based Image Inpainting［J］.IEEE Trans Image Process，Sep 2004，13(9):1200－1212.

［7］Komodakis N，Tziritas G.Image Completion Using Global Optimization［C］//Proc IEEE Computer Soc Conf Computer Vision and Pattern Recognition，2006，442－452.

［8］Bugeau A，Bertalmio M，Caselles V，et al，A Comprehensive Framework for Image Inpainting［J］.IEEE Trans Image Process，2010，19(10):2634－2645.

［9］Hsin H F，Leou J J，Lin C S，et al.Image Inpainting Using Structure-Guided Priority Belief Propagation and Label Transformations［C］//Pattern Recognition(ICPR)，2010 20th International Conference on，2010，4492－4495.

［10］Wohlberg B.Inpainting by Joint Optimization of Linear Combinations of Exemplars.Signal Processing Letters［J］.Signal Processing Letters，IEEE，2011，18(1):75－78.

［11］Fang C W，Lien J J.Rapid Image Completion System Using Multiresolution Patch-Based Directional and Nondirectional Approaches［J］.IEEE Trans Image Process，2009，18(12):2769－2779.

［12］蔡念，张海员，张楠.基于Contourlet的改进双线性插值图像超分辨率算法［J］.传感技术学报，2011，24(1):59－64.

［13］朱良销，余学才，陈涛，等.一种扩展动态范围的图像处理算法［J］.传感技术学报，2011，24(1):65－67.

［14］Ojeda S，Vallejos R，Bustos O.A New Image Segmentation Algorithm with Applications to Image Inpainting［J］.Comput Stat Data Anal，2010，54(9):2082－2093.