基于纹理合成的快速自适应图像补全算法

陈志雄

（厦门大学 信息科学与技术学院，福建 厦门 360005）

摘  要：图像修复是一种修复图像中破坏部分的技术，具有广泛的应用。对基于纹理合成的快速自适应图像补全算法进行了研究，算法从寻找纹理匹配块的搜索范围、纹理块修复的优先次序、纹理块大小的自适应选取以及块效应的去除等方面着手，充分利用图像的局部特征，有效改善了图像补全的视觉效果，加快了图像补全的速度，提高了纹理合成的速度。

关键词： 纹理合成；图像补全；自适应

A fast adaptive algorithm based on texture synthesis

for image completion

CHEN Zhi-xiong

(School of information science and technology，Xiamen University, Xiamen Fujian 360005, China)

Abstract：Image inpainting is a kind of technique with a wide range of applications, which repairing the damaged sect ion of the image. Researching on fast adaptive algorithm based on texture synthesis for image completion which focus on seeking the texture match block’s hunting zone, precedence in texture block repairing, texture block size auto-adapted selection and blocking effect elimination, fully uses image’s partial characteristic, improves the visual effect of image completion, speeds up the speed of image completion and enhances thespeed of texture synthesis.

Keyword：texture synthesis；image completion；adaptive

1 绪论

数字图像修复(image inpainting)技术是目前图像工程领域一个新的研究热点，其目的是检测图像上的受损部分或被遮挡区域，并根据周围的有效信息进行自动恢复，达到满意的目视效果。有很多因素会引起数字图像的局部信息缺损，如对原本就有破损或者缺失的图片进行数字扫描后得到的图像；为某种特殊目的而移走数字图像上的目标物体或文字等。因此，为保证图像信息的完整性，需要对这些受损图像进行修复。本文主要讨论大尺度破损的纹理图像修复问题。

2 图像修复技术

去除图像中的目标物体或大的区域，然后再填充这些丢失的数据，是许多应用中的关键问题，如图像复原和特技效果等。当前，处理这种问题的方法有两类：一类是填充图像中小尺度裂痕的修补技术；另一类是用于填充图像中大块丢失信息的图像补全(completion)技术。

前者[1] 利用基于偏微分方程的方法来修补受损的图像，该方法能很好地修复图像的线性结构，如目标轮廓，但不能恢复细节。后者处理纹理具有某种随机性的二维模式的重复，有较好的效果，目前，这类技术包含以下2种方法：(1)基于图像分解的修复技术，它是将图像分解为结构部分和纹理部分，其中结构部分使用修描算法，而纹理部分使用纹理合成方法[2] ；(2)基于块的纹理合成技术，如Criminisi算法[3] 。

虽然上述基于纹理合成的方法可以产生很好的效果，但它们仍然存在一些缺点，首先，这些方法都是采用在整个图像区域寻找合适的纹理匹配块，这种全局的搜索首先，这些方法都是采用在整个图像区域寻找合适的纹理匹配块。这种全局搜索方法不但耗时，而且忽略了自然图像的局部相似性。另外，通过仿真发现，图像的修复质量，极大依赖于待修补块的合成次序以及纹理模板大小的选取。因此，根据以上分析，本章介绍一种基于纹理合成的快速自适应自然图像补全算法。该算法从寻找纹理匹配块的搜索范围、纹理块修复的优先次序、纹理块大小的自适应选取以及块效应的去除等方面着手，充分利用图像的局部特征，改进了现有算法运行速度慢、易产生误匹配以及引入模糊等缺点，有效地改善了图像补全的视觉效果，加快了图像补全的速度。

3 基于纹理合成的快速自适应图像补全算法

该算法在处理受损图像前，首先需要用户确定图像上哪些区域需要要修复，一般采用某种特定颜色将受损区域标注。修补前的图像分区如图 1(a)所示，Ω为需要修补的受损区域，为受损区域的边界， Φ为原图像中完好的区域。具体算法步骤如下：

(1)如图 1(b)所示，选取受损区域边界上一点p，以p为中心的当前需要修补的块为。

(2)如图 1(c)所示，在图像完好区域Φ 中搜索的匹配块，得到的最优匹配块为。

(3)如图 1(d)所示，将最优匹配块中对应像素点复制到区域 区域所在的位置，并更新受损区域边界。

(4)重复步骤(1)~步骤(3)，直到受损区修补完毕。

(a)受损图像        （b）选定修补区域        （c）找最佳匹配块       （d）补全后图像

图 1 图像补全示意图

3.1 纹理方向的计算

该算法利用图像的边缘信息，给出采用频谱法计算图像纹理主方向的主要步骤。首先给出纹理主方向的定义[4] ：一幅纹理图像，经二维离散Fourier变换后的功率谱矩阵，通过(r，θ)极坐标变换，固定θ，关于θ的函数图中突起的峰值所对应的θ，称为纹理主方向。

根据频谱图，用离散逼近法求解纹理主方向的过程如下：

（1）输入一幅纹理图像，同时获取处理窗口参数M，设定离散采样数n。

（2）采用边缘检测算子提取纹理图像的边缘。

（3）将边缘图像进行二维傅里叶变换，得到，并求其功率谱：，其中，.

（4）将执教坐标系下功率谱转换到极坐标系，得到。

（5）固定θ，对r求和，得到

（6）根据（5）中公式搜索，使最大。如果同时有两个使得取得最大值时，返回（1），增大n，重新计算，知道搜索到唯一的最大值。

实验中采用的边缘检测算子为Sobel算子，其定义如图 2所示。

(a)  垂直                             (b)水平

图 2 Sobel算子模板

3.2 优先权的计算

待修补纹理块的填充次序对纹理合成的效果是非常重要的，因此要得到一个好的修补效果，需要先确定待修补纹理块的优先次序，在确定最高优先权的待修补块之前，首先得计算填充边缘上所有待修补块的优先权，它决定了这个待修补块的填充修补顺序。首先，我们给出一个优先权函数，以保证图像结构和纹理的正确填充。优先权定义为

                                                                                                                       

式中，的最优选择值为3，使得在决定优先权上占有更为重要的地位。代表置信度项，代表数据项，它们分别定义为

                                                                                                                          

当q点在里时，值就等于1，否则就取0。β是一个归一化系数，这里取255，代表以p为中心的待修复块的面积，为填充边缘上p点的法向量，代表p点梯度方向的垂直方向，一般像素的梯度方向，是像素值在空域上变化最大的方向，其垂直方向即为光照线(同色线)方向，其计算公式如下（，分别为像素点在x方向和y方向的偏微分）：

                                                                                                                               

由上可知，优先权P(p)是图像的特征函数，反映了待补全块的置信度和光照线强度的综合特征。由它决定的图像填充补全顺序，能使图像的补全过程有组织地进行，符合视觉连通原理，避免了补全后出现的结构断裂和模糊等现象。

3.3 模板窗口大小的自适应选择

对比实验发现，被补全图像的质量，依赖于模板窗的大小。因此，本文提出一种决定窗口大小的自适应方案，以捕获图像中不同尺度的特征。为了简化，将模板窗口大小的函数size(p)看成是梯度的函数，定义为

                                                                                                                       

式中，k和l是常数，它们与size(p)和的取值范围有关；p是任意像素的位置。下面给出模板窗口大小选择的自适应方案。令max tempsize表示模板窗口大小的最大取值，min gradvalue表示最小梯度值，有

                                                                 

3.4 块效应的去除

在找到在找到最优匹配块后，用中的相应像素填充中的未知像素。虽然和之间的Euclidean距离在搜索方向上是最小的，但是，在将复制到时，边界点处容易引起块效应。这是因为，用任何的距离函数都很难判断图像的相似性。因此，为了减少局部振荡，改进图像的复原效果，我们用一种平滑方法来降低块效应。

边界点是产生块效应的关键，如图 3(b)所示。我们的目的是减少区域和之间的块效应。我们的方法是：将边界点左右两边的邻域点的平均值作为该边界点的值。如图 3所示，(a)中具有阴影的边界点的值由下面的公式给出：

                                                                                 

                   

(a)                                   (b)

图 3 平滑方案

4 图像补全算法的基本步骤

基于上述分析，给出算法的基本步骤：

(l)用户选择需要去除并填充的目标区域Ω定义原始区域中为整个图像区域 I 减去目标区域Ω：Φ=I-Ω；

(2)根据待修补区域周围的信息，用户选择一块具有主要纹理走向的纹理图像作为输入图像，用离散逼近法近似计算出纹理的主方向θ，然后沿θ方向搜索匹配块，以便将寻找纹理匹配块的搜索范围，限制在待修补像素的某一方向邻域内，以提高纹理合成效率；

(3)确定计算优先权的块的大小。文献[5] 采用块大小的默认值为，但实际上要根据图像的纹理特征来设定。

(4)计算块的优先权。优先权计算的目的，是使那些具有较多已知信息和较多结构信息的区域先被修补。这样，在填充纹理块时，会得到更多的信息，并能同时保证图像的结构信息被修补。

(5)自适应传播结构和纹理信息。找到具有最大优先权值的模板中心点，根据其梯度信息，自适应寻找用于纹理匹配的模板块然后根据公式，在的某一方向邻域寻找一个匹配块，使得为最小。表示两个像素块的距离，即这两个像素块里面对应的已知像素点的颜色值之间的差的平方和。最后，用中的相应点替代中的未知点。

(6)在填充了新的像素之后，更新优先权：最高优先权的待修补块填充好后，刚刚填充的那些像素点，由原来处在受损区域变成处在样本区域。从上面的分析可知知，这些像素点的置信度己经发生了变化，应及时更新。假如为刚刚填充好的修补块，则其像素点的置信度更新按进行：

                                                                                                              

 (7)自信度更新以后，一个图像抽样过程就算完成了。这时，填充边缘的路径已经发生了变化，将会得到一个新的填充边缘。如果这个填充边缘上的像素点不为零，重复步骤(3)～(6)，直到整个目标区域填充修补完毕。其具体的实现流程图如图4所示：

图 4 算法实现流程图

5 仿真分析

利用上述算法进行实验，在实验中将算法应用于大量的自然图像。我们直接利用图像的视觉效果来判断修复图像质量的好坏。所有的实验在配置为文中实验均在CPU intel 2.8GHz， 内存Kingston1.5GB 的PC机上用Matlab2008b实现。

令

                                                                                                 

可以得到

                                                                                  

                                                           

仿真实验取：min tempsize=15，max tempsize=M/11，其中，是原始图像的大小。

为了验证所提的图像补全算法，在处理时间和补全效果上都要优于其他补全算法，图 5给出了所提算法与文献[3] 中算法的比较结果，比较图 5(c)、(d)，可以发现，文献[3] 有明显的错误匹配。如图 5(c)所示，白色矩形框标出了错误匹配。而本文算法没有产生类似的错误匹配，其修复效果较好。表1给出了同等条件下，这两种算法的运行时间。从表 1中可以看出，本文算法要比文献[3] 中的算法快很多。

(a)      原始图像                    (b) 目标区域（标注区域）

(c) 文献[3]修复结果                          (d) 本文算法结果

图 5 与文献[3] 的对比实验

表 1 不同算法的运行时间比较

图 6给出了我们的算法结果与文献[6] 的结果的比较。图 6(c)是由文献」中的算法得到的结果，(d)是我们的算法得到的结果。从这些图可以看出，文献中的算法引入了模糊。

(a) 原始图像                              (b) 目标区域（标注区域）

(c) 文献[6]修复结果                            (d) 本文算法的结果

图 6 与文献[6] 的比较实验

图 7给出了我们的算法与文献[7] 的对比实验。图 7(c)是文献[7] 所得到的结果，(d)是本文算法的结果。从这些图像可以看出，本文算法不会模糊边缘。在图 7(d)中，房子的锋利边缘被很好地修复了，这是因为在我们的算法中，没有引入[7] 中的扩散操作。

6 结束语

基于纹理合成的自然图像补全算法，充分利用多数自然图像都具有一定的纹理走向这一事实，给出了一种计算纹理主方向的方法，并将搜索范围缩小到这一方向，减少了寻找最优匹配块的时间，提高了纹理合成的速度。另外，还定义了块的优先权，尽量使具有较多己知信息和较多结构信息的区域的优先权值最大，使具有最大优先权的块先被修复。最后给出了一种利用局部梯度信息，选择模板窗口大小的自适应方案，来改进图像的补全质量。实验表明，该算法能有效改善补全图像的视觉效果，还可以大大提高纹理合成的速度。

(a) 原始图像                              (b) 目标区域（标注区域）

(c) 文献[7]修复结果                            (d) 所提算法的结果

图 7 与文献[7] 的比较实验

参考文献

[1]       Bertalmio M，Sapiro G，Caselles V，et al．Image inpainting[J]．Proceedings of ACM SIGGRAPH，New York：ACM Press，2000：417-424．

[2]       Efros A A, Leung T K. Texture Synthesis by Non-parametric Sampling[C]．Proc. of the IEEE Computer Society Int’l Conf．on Computer Vision. Washington D. C., USA: [s. n.]，1999．

[3]       Criminisi A, Perez P, Toyama K. Region Filling and Object Removal by Exemplar-based Image Inpainting[J]．IEEE Trans. on Image Processing, 2004, 13(9)：1200-1212．

[4]       敖波．纹理合成技术的研究[D]．西安：西北工业大学硕士学位论文，2004．

[5]       Efros A A，Leung T K．Texture synthesis using tree-structured vector quantization[J]．Proceedings of ACM SIGGRAPH，2000：479-488．

[6]       Iddo D，Daniel C，Hezy Y．Fragment based image completion[J]．ACM Transactions on Graphics，2003,22（3）：303-312．

[7]       Harald G，Otmar S．Using the complex Ginzburg-Landau equation for digital inpainting in 2D and 3D．Scale-Space[J]．2003：225-236．

[8]       吴亚东，张红英，吴斌．数字图像修复技术[M]．北京：科学出版社，2010．