尤鸿霞，王寿兵

（江苏工程职业技术学院素质教学部，江苏南通226007）

0 引言

现实世界中存在着各种各样的纹理，纹理合成是计算机图形学的一个重要研究方向，纹理合成技术可广泛应用于图像编辑、图像修复、虚拟现实中大面积场景绘制等领域[1]。纹理合成主要有过程纹理合成和基于样图的纹理合成。过程纹理合成通过仿真纹理的生成过程来合成纹理，其合成效果非常逼真，但计算量大且合成速度慢，对每一种新的纹理都需要调整参数反复测试。基于样图的纹理合成基本思想是根据给定的小区域的纹理样本，拼合生成任意大小的纹理图像并且在视觉上与样本是相似而连续的。

基于样图的纹理合成主要有两大类方法：基于像素的纹理合成和基于块的纹理合成。Efros等人1999年提出基于像素的邻域匹配算法[2]，主要思想是对于每一个待合成的像素，都是在样图图像的相似邻域中确定像素值。对于输出图像中待合成的点，是通过比对该点的邻域和输入样图图像中所有点的邻域来查找匹配点，并将查找到的与待合成点最匹配的点作为该点的值。Efros在2001年的FIGGAPH会议上提出了一种基于块拼接的纹理合成算法[3]，又称图像缝合算法，即image quilting算法。与基于像素的纹理合成相比，基于块的纹理合成每次向输出图像填充一个图像块，有效地减少了搜索和匹配的次数，在纹理合成的速度和质量等方面都得到了很大的提高。Image quilting算法存在的问题是有时纹理出现重复，有些边界不匹配。

J.chen和B.zeng[4]提出将纹理合成引入到了小波域内，使得纹理合成的速度得到了提高，但合成时丢失了图像的高频信息。LeandroTonietto等人[5]通过用小波变换后的小波系数来体现图像的细节信息，在一定程度上考虑了图像结构信息的匹配，但是由于在搜索最佳匹配块时需对整个样图进行搜索，使得该方法的合成时间较长。

本文基于image quilting算法，考虑纹理的结构信息，将小波变换引入到纹理块的特征分析与匹配过程中，结合小波变换后的小波系数和小波变换后的低频域图像来进行块的匹配和分析。实验表明，该算法能够获得良好的纹理合成图。

1 Image Quilting算法描述

Image quilting纹理合成算法[3]的基本思想是：按照扫描线的顺序，每次根据一定的匹配规则从纹理样图中选择固定大小的纹理块，将其拷贝至输出纹理，直至达到输出纹理大小。Image quilting算法的合成单位是纹理块，合成速度较快。

Image quilting算法采用最小误差路径来缝合纹理，即：设B1为已合成纹理块，B2为待合成纹理块，B1和B2沿着垂直方向重叠，B1ov和B2ov分别为B1和B2各自的重叠区域，误差定义为e=(B1ov-B2ov)，通过式(1)获得重叠区域最后一行各点的累积误差：

图1 三种块缝合

选取累积误差最小的一点，通过反向跟踪可获得最佳缝合路径。对水平方向有重叠的区域，采用相同的方法得到最佳缝合路径，当同时具有垂直和水平重叠区域，两条路径会在某点相交，选取总体误差最小的路径作为最佳缝合路径。

2 基于小波变换的纹理合成

2.1 haar小波变换

Haar小波函数是最简单的正交函数，其构造简单，计算方便，本文采用haar小波变换将图像的低频信息和高频信息分离，即在对样图进行纹理合成之前，先对样图进行小波分解，将样图分解为低频、水平高频、垂直高频、高频四部分。经过小波变换后，样图的大部分能量都集中在小波变换后的低频部分，经过一次小波变换，其低频部分的的面积缩小为原来的1/4，在搜索最佳匹配块的时候只在低频部分搜索。传统的纹理合成方法在搜索最佳匹配块时，直接对样图进行全局搜索，可能导致搜索时间过长，而搜索小波变换低频域，能够节约大量的搜索时间使合成速度得到提升。

图2 织物纹理小波变换样图

2.2 纹理合成过程算法描述

本文纹理合成算法是在image quilting算法基础上加以改进，首先从样本图像中随机选择一块指定大小的图片块作为输出图像的第一个块B1，然后根据一定的规则从样本图像中选择合适的图片块B2拼接在B1之后，并且使拼接后的输出图像看上去与样图的纹理是相似的而且是连续的，无明显的拼贴痕迹。

算法的关键问题有三。第一，确定搜索路径，快速准确地在样图中搜索到能够合适拼贴在已合成图片块B1后面的图片块B2。经分析，因在输出纹理图像中B2是拼贴在B1之后，在样图中B2出现在B1附近的概率较高，所以，确定搜索路径时，首先在样图中B1的位置附近搜索，如图3a中，极易在B1的附近找到合适的B2，这样可快速定位B2，提高搜索速度。另外，也有一些情况，在B1位置的附近，没有适合可以作为B2的块，如图3b，那么当在B1位置附近搜索失败，则从样图的起始处开始搜索。

第二，确定已合成块B1和待合成块B2的匹配准则。对于已合成块和待合成块的重合区域，如果待合成区域的位置不同，则重叠区域也是不同的[3]，共有三种情况：（1）待合成块位于第一行，只有左边的垂直重叠区域。如图4a所示。（2）待合成块位于第一列，只有上边的水平重叠区域，如图4b所示。（3）其余情况，同时包含水平和垂直两个重叠区域，即L形重叠区域，如图4c所示。

图3 搜索策略

图4 重叠区域

将图像进行2级小波变换，用小波变换后的小波变换系数来进行重叠区域匹配计算。设B1ov和B2ov为已合成块B1和待合成块B2各自的重叠区域，将B1ov和B2ov的二级小波变换系数做匹配计算，使其匹配误差控制在一定范围内。为提高搜索速度，设定阈值，当匹配计算误差值小于设定阈值时，则认为找到了合适的B2并停止本次搜索，以避免每次都进行全局搜索。用小波变换系数来进行匹配计算，充分考虑了纹理的结构信息，但是从实验结果分析，拼贴缝合时，重叠处的图像纹理边缘处偶见不能准确对接或是出现明显的纹理结构循环现象，如图5b1和图5b2。

为解决此问题，将一级小波变换低频域的图像以一定的权重参与到重叠区域匹配中，步骤为：首先将样图做小波变换，获得其一级小波变换的低频域图像BL；其次在输出图像中取得重叠区域，将其做小波变换，并将重叠区域一级小波变换后的低频域图像在BL图像中做搜索对比，以获合适的B2。一级小波变换后的低频域图像包含了原图像的大部分信息而大小仅为原图像的1/4，匹配次数较少，从实验结果分析，结合小波系数和小波变换低频域图像进行纹理块匹配能够得到较好的纹理合成效果。

第三，将搜索到的纹理块B2缝合在B1的后面，使其缝合的边缘无明显拼贴痕迹，本文使用最小路径法将待合成纹理块缝合在已合成纹理块之后。

本文算法步骤如下：

步骤一：指定纹理块的大小，以及纹理块之间重叠区域的大小。

步骤二：随机取样本纹理中的一个纹理块B1放在输出图像中，作为输出图像的第一个拼贴块。

步骤三：从输出图像中取出重叠区域，结合小波系数和小波变换低频域图像进行重叠区域纹理匹配，从样图中找到合适的待合成块B2。

步骤四：将B2其拼贴到已合成区域B1的后面，拼贴的缝合过程采用最小路径法。

步骤五：重复以上步骤三和步骤四过程，获得合成纹理图。

实验结果如图5所示，图中a1、a2为样图，b1、b2为在块匹配步骤中只采用小波系数进行重叠区域匹配得到的纹理图，c1、c2为本文算法的合成纹理图。

图5 纹理合成结果图

3 结论

纹理合成是计算机图形学领域的研究热点之一，本文基于原有image quilting纹理合成方法的优势与不足，从待匹配块的搜索路径、合成块的匹配策略等方面对算法进行了改进。从实验结果分析，对于多数纹理模型合成质量较好，但是对于不同类型的纹理，合成块的大小的选择需要做适当的调整以取得最佳合成效果，所以未来工作中应进一步研究此问题，以获取更好的解决方案。

[1]朱文浩，魏宝刚.基于样本的纹理合成技术综述[J].中国图像图形学报，2008(11)：2063-2069.

[2]Efros A,Leung T.Texture synthesis by non-parametric sampling[A].In:Proceedings of IEEE International Confer⁃ence on Computer Vision[C],Corfu,Greece,1999:1033-1038.

[3]Efros A,Freeman W T.Image quilting for texture synthesis and transfer[A].In Proceedings of SIGGRAPH 2001[C],USA,2001:341-346.

[4]J.chen,B.zeng.Patch-Based Multi-Resolution Real-Time Texture synthesis in wavelet domain[J].International Confer⁃ence on Communications,Circuits and Systems,2004(2):788-791.

[5]L.Tonietto,M.walter and C.R.Jung.Patch-based texture synthesis using wavelets[C].IEEE Computer Society,Proceed⁃ings of SIBGRAPI,Natal:IEEE Press,2005:383-389.