基于分形的图像修复算法

摘要：基于纹理合成的图像修复方法通过在图像中搜索合适的背景块填充修复区域，但在搜索过程中可能由于缺乏合适的匹配块造成误匹配，影响修复效果。提出一种基于分形思想的搜索方法，在搜索匹配块时，不仅仅将候选块与边界块比较，而且将候选块进行仿射变换后的结果与边界块进行比较。为提高搜索速度，在搜索前对图像进行分割，以减小解空间。实验表明该算法在视觉效果和速度方面达到了良好的平衡。

关键词：分形； 图像修复； 搜索

中图分类号：TP391 文献标识码：A文章编号：2095-2163（2013）02-0068-03

0引言

图像修复是图像处理中的一项实用技术，可将图像中某些缺失区域依据一定算法进行填补，以收取良好的视觉效果。图像修复技术主要用于历史图片破损修复，图像中的物体或文字移除等。

图像修复的主流算法有两大类。第一类基于偏微分方程（PDE）[1]，主要思想是将图像建模为分片光滑函数，通过边界区域向缺失区域内部扩散，用边界区域的梯度控制扩散参数，完成图像修复。这类方法对于修复小范围光滑图像区域效果良好，但在修复纹理区域时，则难以保证纹理的一致性，同时也容易产生过度平滑，影响视觉效果。第二类算法基于纹理合成[2]（Texture Synthesis），主要思想是在图像中寻找与边界内容相似的图像块，填充到缺失区域中。此类算法应用更为广泛，但该算法在搜索时对相似性的界定还不够全面，一方面对图像内容比较能力仍显不足，难以找到最佳匹配的图像块，另一方面容易发生误匹配，造成修复错误。

本文算法基于纹理合成的实现原理，引入了分形思想对其进行改进。该算法首先对图像进行分割，确定不同位置的搜索区域。在搜索时，将候选块的多个仿射变换结果与边界块进行比较，寻找最优匹配的结果用于填充。这一算法减少了误匹配的概率，提高了修复的视觉效果，同时由于控制了搜索区域，增大了填充尺度，也保持了较低的运算量。

1纹理合成算法简介

图像修复中，纹理合成算法的基本实现主要分为四步，分别是：修复区域标记、优先度计算、块搜索和填充。

首先，需要手动标注原始图像待修补区域，标注后的图形区域如图1所示。

由图1可知，Y表示原始图像区域，X表示待修补区域，δΩ为两个区域的边界线。

标注修复区域后，对该区域所有边界点计算优先度，优先度最高的那一点将作为参考块的中心。文献[2]中，优先度P（p）计算公式为：

确定优先修复的位置后，在整个图像中搜索与参考块最为接近的图像块，搜索过程中匹配度的评价使用最小均方误差准则（Sum of Squared Differences，SSD）。搜索到最高匹配度的图像块后将其复制到待修复位置。

将上述步骤运行一次后，即更新修复区域边缘点的优先度，而后重复这一过程，直到图像修复结束。第2期甘羽，等：基于分形的图像修复算法智能计算机与应用第3卷

2算法描述

21分形理论简介

分形的概念可表达为一种由多个与整体有某种相似性的局部堆叠累加而构成的形体。分形可以使用迭代函数系统（Iterated Function System，IFS）生成，而由拼贴定理[3]可知，任何图像都可以表示为一个IFS。

分形的思想已经应用于图像压缩中[4]，分形图像压缩编码的过程是依据拼贴定理，通过给定的图像寻找一组压缩映射，使其组成的迭代函数系统的吸引子逼近给定图像，并记录得到相应参数。解码过程则由对应参数确定迭代函数系统，再根据迭代函数系统定理反复迭代生成图像。

分形图像压缩的基本步骤为：

（1）将待压缩图像进行K×K分块，记为Ri。

（2）将图像进行重叠的L×L分块，记为Di.通常L=2K。

（3）根据最小均方误差准则，在Di中搜索最佳的分割块和合适的压缩映射变换ωi，满足Ri=ωi（Di），即对每个像素点：

上述过程表示Di经过一组仿射变换和亮度调整后，收敛于Ri。

由以上论述可以推知，图像内部存在的自相似性和仿射变换是分形图像处理的核心。本文也即借鉴分形思想，利用仿射变换，提高图像修复算法的性能。

22算法步骤

算法的实现过程主要分为以下几个步骤：

（1）手动标注原始图像待修补区域。

（2）对图像进行分割，并标注缺失区域对应的背景区域。

（a） 原始图像

（a） Test image

（b） Criminisi算法修复结果

（b） Inpainting result by Criminisi's method

（c） 本文算法修复结果

（c） Inpainting result by proposed method

（3）对原始图像进行仿射变换，生成仿射变换集。仿射变换参数为缩放50%、80%、120%、150%，旋转30°～180°，间隔30°。

（4）采用第1节介绍的纹理合成算法计算，如图1中，δΩ边界上所有点的修补优先度。

（5）在仿射变换集中搜索候选解。首先，对放射变换集中的图像进行不重叠分块，计算所有子块的平均灰度。然后，在与待修复区域对应的图像局部空间中找出接近于待修复块平均灰度的块作为候选块。接下来，在两倍于侯选块的范围内展开像素级搜索，并基于最小均方误差准则得到用于修复的图像块。

（6）重新计算下次修补的优先度。重复第（5）步，直到图像修复结束。

3实验结果与讨论

算法采用VC 2010实现，在Thinkpad T420上运行。本文选取了USC-SIPI Miscellaneous 图像库[5]中的20幅图像，并从网络上节选了20幅图像作为测试样本，图像类别涉及人物、风景、遥感图像等广泛门类在内。在将图像中物体删除后，利用本文算法与Criminisi原始算法分别进行修复。原始算法典型结果如图2（b）所示，本文算法结果如图2（c）所示。由图中比较得出，本文算法具有更好视觉效果。

4结束语

本文提出了一种基于分析的图像修复算法，与传统基于纹理合成的图像修复算法相比，取得了更好的视觉效果，同时也实现了较高的效率。但算法为减小搜索空间，还需要一定的手工标注，下一步需对算法进行优化，增加自动分割与区域标注功能以提高算法的灵活性。

参考文献：

[1] CHAN T， SHEN J. Mathematical models for local non-texture inpainting [J]. SIAM J. Appl. Math， 2001， 62（3）： 1019-1043.

[2]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）： 1200-1212.

[3] JACQUIN A E. Image coding based on a fractal theory of iterated contractive image transformations[J]. IEEE Transactions on Image Processing， 1992， 1（1）：18-30

[4] DAN C P ， DIMCA A， YAN H. A nonlinear model for fractal image coding[J]. IEEE Transactions on Image Processing， 1997， 6（3）：373-38.

[5] USC Signal and Image Processing Institute. USC–SIPI Image Database. http：//sipi.usc.edu/database.