Afastadaptivealgorithmbasedonte_turesynthesis
forimagecompletion
CHENZhi-_iong
(Schoolofinformationscienceandtechnology，_iamenUniversity,_iamenFujian360005,China)
Abstract：Imageinpaintingisakindoftechniquewithawiderangeofapplications,XXX’shuntingzone,precedenceinte_tureblockrepairing,te_tureblocksizeauto-adaptedselectionandblockingeffectelimination,fullyusesimage’spartialcharacteristic,improvesthevisualeffectofimagecompletion,speedsupthespeedofimagecompletionandenhancesthespeedofte_turesynthesis.
Keyword：te_turesynthesis；imagecompletion；adaptive
数字图像修复(imageinpainting)技术是目前图像工程领域一个新的研究热点，其目的是检测图像上的受损部分或被遮挡区域，并根据周围的有效信息进行自动恢复，达到满意的目视效果。有很多因素会引起数字图像的局部信息缺损，如对原本就有破损或者缺失的图片进行数字扫描后得到的图像；为某种特殊目的而移走数字图像上的目标物体或文字等。因此，为保证图像信息的完整性，需要对这些受损图像进行修复。本文主要讨论大尺度破损的纹理图像修复问题。
2图像修复技术
去除图像中的目标物体或大的区域，然后再填充这些丢失的数据，是许多应用中的关键问题，如图像复原和特技效果等。当前，处理这种问题的方法有两类：一类是填充图像中小尺度裂痕的修补技术；另一类是用于填充图像中大块丢失信息的图像补全(completion)技术。
前者[1]利用基于偏微分方程的方法来修补受损的图像，该方法能很好地修复图像的线性结构，如目标轮廓，但不能恢复细节。后者处理纹理具有某种随机性的二维模式的重复，有较好的效果，目前，这类技术包含以下2种方法：(1)基于图像分解的修复技术，它是将图像分解为结构部分和纹理部分，其中结构部分使用修描算法，而纹理部分使用纹理合成方法[2]；(2)基于块的纹理合成技术，如Criminisi算法[3]。
虽然上述基于纹理合成的方法可以产生很好的效果，但它们仍然存在一些缺点，首先，这些方法都是采用在整个图像区域寻找合适的纹理匹配块，这种全局的搜索首先，这些方法都是采用在整个图像区域寻找合适的纹理匹配块。这种全局搜索方法不但耗时，而且忽略了自然图像的局部相似性。另外，通过仿真发现，图像的修复质量，极大依赖于待修补块的合成次序以及纹理模板大小的选取。因此，根据以上分析，本章介
通信工程系2010级基于纹理合成的快速自适应图像补全算法姓名学号：0
绍一种基于纹理合成的快速自适应自然图像补全算法。该算法从寻找纹理匹配块的搜索范围、纹理块修复的优先次序、纹理块大小的自适应选取以及块效应的去除等方面着手，充分利用图像的局部特征，改进了现有算法运行速度慢、易产生误匹配以及引入模糊等缺点，有效地改善了图像补全的视觉效果，加快了图像补全的速度。
3基于纹理合成的快速自适应图像补全算法
该算法在处理受损图像前，首先需要用户确定图像上哪些区域需要要修复，一般采用某种特定颜色将受损区域标注。修补前的图像分区如图1(a)所示，Ω为需要修补的受损区域，为受损区域的边界，Φ为原图像中完好的区域。具体算法步骤如下：
(1)如图1(b)所示，选取受损区域边界上一点p，以p为中心的当前需要修补的块为p。(2)如图1(c)所示，在图像完好区域Φ中搜索p的匹配块，得到的最优匹配块为p。
(3)如图1(d)所示，将最优匹配块p中对应像素点复制到区域p区域所在的位置，并更新受损区域边界。
(4)重复步骤(1)~步骤(3)，直到受损区修补完毕。
(a)受损图像（b）选定修补区域（c）找最佳匹配块（d）补全后图像
图1图像补全示意图
3.1纹理方向的计算
该算法利用图像的边缘信息，给出采用频谱法计算图像纹理主方向的主要步骤。首先给出纹理主方向的定义[4]：一幅纹理图像，经二维离散Fourier变换后的功率谱矩阵，通过(r，θ)极坐标变换，固定θ，F(r,)
关于θ的函数图中突起的峰值所对应的θ，称为纹理主方向。
根据频谱图，用离散逼近法求解纹理主方向的过程如下：
（1）输入一幅纹理图像，同时获取处理窗口参数M，设定离散采样数n。（2）采用边缘检测算子提取纹理图像的边缘。
（3）将边缘图像fMMi,j进行二维傅里叶变换，得到FMu,v，并求其功率谱：PMu,vFMu,v，其中，u,v1,2,,M.
（4）将执教坐标系下功率谱转换到极坐标系，得到Pri,j。
通信工程系2010级基于纹理合成的快速自适应图像补全算法姓名学号：0
（5）固定θ，对r求和，得到PPri,,1,2,n。
（6）根据（5）中公式搜索，使Pma_最大。如果同时有两个i,jij使得Pma_取得最大值时，返回（1），增大n，重新计算，知道搜索到唯一的最大值。
实验中采用的边缘检测算子为Sobel算子，其定义如图2所示。
(a)垂直(b)水平
图2Sobel算子模板
3.2优先权的计算
待修补纹理块的填充次序对纹理合成的效果是非常重要的，因此要得到一个好的修补效果，需要先确定待修补纹理块的优先次序，在确定最高优先权的待修补块之前，首先得计算填充边缘上所有待修补块的优先权，它决定了这个待修补块的填充修补顺序。首先，我们给出一个优先权函数Pp，以保证图像结构和纹理的正确填充。优先权定义为
PpCpDp
式中，使得Dp在决定优先权上占有更为重要的地位。Cp代表置信度项，Dp的最优选择值为3，代表数据项，它们分别定义为
qpCp
Ipnp
当q点在里时，Cp值就等于1，否则就取0。β是一个归一化系数，这里取255，p代表以p为中心的待修复块的面积，np为填充边缘上p点的法向量，I代表p点梯度方向的垂直方向，一般像素的梯度方向，
是像素值在空域上变化最大的方向，其垂直方向即为光照线(同色线)方向，其计算公式如下（I_，Iy分别为像素点在_方向和y方向的偏微分）：
,I(3)
由上可知，优先权P(p)是图像的特征函数，反映了待补全块的置信度和光照线强度的综合特征。由它决定的图像填充补全顺序，能使图像的补全过程有组织地进行，符合视觉连通原理，避免了补全后出现的结构断裂和模糊等现象。
通信工程系2010级基于纹理合成的快速自适应图像补全算法姓名学号：0
3.3模板窗口大小的自适应选择
对比实验发现，被补全图像的质量，依赖于模板窗p的大小。因此，本文提出一种决定窗口大小的自适
应方案，以捕获图像中不同尺度的特征。为了简化，将模板窗口大小的函数size(p)看成是梯度Ip的函数，定义为
sizepk1
Ipl(4)
(4)式中，k和l是常数，它们与size(p)和Ip的取值范围有关；p是任意像素的位置。下面给出模板窗口大小选择的自适应方案。令ma_tempsize表示模板窗口大小的最大取值，mingradvalue表示最小梯度值，有
ma_tempsize,Ipmingraduvaluesizep1sizepkl,其他Ip(5)
3.4块效应的去除
在找到在找到最优匹配块p后，用p中的相应像素填充p中的未知像素。虽然p和p之间的Euclidean距离在搜索方向上是最小的，但是，在将p复制到p时，边界点处容易引起块效应。这是因为，用任何的距离函数都很难判断图像的相似性。因此，为了减少局部振荡，改进图像的复原效果，我们用一种平滑方法来降低块效应。
边界点是产生块效应的关键，如图3(b)所示。我们的目的是减少区域和之间的块效应。我们的方法是：将边界点左右两边的邻域点的平均值作为该边界点的值。如图3所示，(a)中具有阴影的边界点的值由下面的公式给出：
VBi1,j1Vi1,jVi,j1/2
VBi,jVi,j1Vi,j1/2
Bi1,jVi1,j1Vi1,j1/2
图3平滑方案
4图像补全算法的基本步骤
基于上述分析，给出算法的基本步骤：
(l)用户选择需要去除并填充的目标区域Ω定义原始区域中为整个图像区域I减去目标区域Ω：Φ=I-Ω；
(2)根据待修补区域周围的信息，用户选择一块具有主要纹理走向的纹理图像作为输入图像，用离散逼近法近似计算出纹理的主方向θ，然后沿θ方向搜索匹配块，以便将寻找纹理匹配块的搜索范围，在待修补
通信工程系2010级基于纹理合成的快速自适应图像补全算法姓名学号：0
像素的某一方向邻域内，以提高纹理合成效率；
(3)确定计算优先权的块p的大小。文献[5]采用块大小的默认值为99，但实际上要根据图像的纹理特
征来设定。
(4)计算块的优先权。优先权计算的目的，是使那些具有较多已知信息和较多结构信息的区域先被修补。这样，在填充纹理块时，会得到更多的信息，并能同时保证图像的结构信息被修补。
，根据其梯度信息，自适应(5)自适应传播结构和纹理信息。找到具有最大优先权值的模板中心点p
寻找用于纹理匹配的模板块p然后根据公式(5)，在p的某一方向邻域寻找一个匹配块p，使得
dp,q的距离，即这两个像素块里面对应的已知像素点的颜,q为最小。dp,q表示两个像素块p
色值之间的差的平方和。最后，用q中的相应点替代p中的未知点。
(6)在p填充了新的像素之后，更新优先权：最高优先权的待修补块填充好后，刚刚填充的那些像素点，由原来处在受损区域变成处在样本区域。从上面的分析可知知，这些像素点的置信度己经发生了变化，应及时更新。假如p为刚刚填充好的修补块，则其像素点的置信度更新按(7)进行：
Cp'Cp,p'p(7)
(7)自信度更新以后，一个图像抽样过程就算完成了。这时，填充边缘的路径已经发生了变化，将会得到一个新的填充边缘。如果这个填充边缘上的像素点不为零，重复步骤(3)～(6)，直到整个目标区域填充修补完毕。其具体的实现流程图如图4所示：
图4算法实现流程图
通信工程系2010级基于纹理合成的快速自适应图像补全算法姓名学号：0
5仿真分析
利用上述算法进行实验，在实验中将算法应用于大量的自然图像。我们直接利用图像的视觉效果来判断修复图像质量的好坏。所有的实验在配置为文中实验均在CPUintel2.8GHz，内存Kingston1.5GB的PC机上用Matlab2008b实现。
可以得到
kmingradvaluema_tempsizemintempsizesizepmintempsize,ma_tempsizeIpmingradvalue,255(8)
1255mingradvalue255(9)lmintempsizemingradvaluema_tempsizemintempsize(10)
仿真实验取：mintempsize=15，ma_tempsize=M/11，其中，MN是原始图像的大小。
为了验证所提的图像补全算法，在处理时间和补全效果上都要优于其他补全算法，图5给出了所提算法与文献[3]中算法的比较结果，比较图5(c)、(d)，可以发现，文献[3]有明显的错误匹配。如图5(c)所示，白色矩形框标出了错误匹配。而本文算法没有产生类似的错误匹配，其修复效果较好。表1给出了同等条件下，这两种算法的运行时间。从表1中可以看出，本文算法要比文献[3]中的算法快很多。
(a)原始图像(b)目标区域（标注区域）
(c)文献[3]修复结果(d)本文算法结果
图5与文献[3]的对比实验
通信工程系2010级基于纹理合成的快速自适应图像补全算法姓名学号：0
表1不同算法的运行时间比较
原始图像大小去除率（目标区域大小/整幅图大小）/%Criminisi算法的运行时间/s本文所提算法运行时间/s240160
240160
430306
454341XXX265XXXX4295
图6给出了我们的算法结果与文献[6]的结果的比较。图6(c)是由文献」中的算法得到的结果，(d)是我们的算法得到的结果。从这些图可以看出，文献中的算法引入了模糊。
(a)原始图像(b)目标区域（标注区域）
(c)文献[6]修复结果(d)本文算法的结果
图6与文献[6]的比较实验
图7给出了我们的算法与文献[7]的对比实验。图7(c)是文献[7]所得到的结果，(d)是本文算法的结果。从这些图像可以看出，本文算法不会模糊边缘。在图7(d)中，房子的锋利边缘被很好地修复了，这是因为在我们的算法中，没有引入[7]中的扩散操作。
6结束语
基于纹理合成的自然图像补全算法，充分利用多数自然图像都具有一定的纹理走向这一事实，给出了一种计算纹理主方向的方法，并将搜索范围缩小到这一方向，减少了寻找最优匹配块的时间，提高了纹理合成的速度。另外，还定义了块的优先权，尽量使具有较多己知信息和较多结构信息的区域的优先权值最大，使具有最大优先权的块先被修复。最后给出了一种利用局部梯度信息，选择模板窗口大小的自适应方案，来改进图像的补全质量。实验表明，该算法能有效改善补全图像的视觉效果，还可以大大提高纹理合成的速度。
通信工程系2010级基于纹理合成的快速自适应图像补全算法姓名学号：0
(a)原始图像(b)目标区域（标注区域）
(c)文献[7]修复结果(d)所提算法的结果
图7与文献[7]的比较实验
