基于小波的纹理合成方法
2008-07-22
作者：闫怀平，赵凤群，戴 芳，张晓艳
摘 要：将KL变换与小波" title="小波">小波变换相结合提出了一种新的纹理合成方法，利用KL变换克服了合成彩色图时存在的颜色失真；对样图进行二维小波分解使得最佳匹配块的搜索仅在原样图的低频部分进行，从而提高了合成速度。在搜索最佳匹配块时,使用多尺度小波变换" title="小波变换">小波变换后的小波系数的差异作为误差度量，并在比较匹配误差时增加高频系数的权重，突出了纹理结构的匹配。实验结果表明，该方法不仅得到了较好的合成质量，而且在很大程度上减少了合成时间。
关键词：纹理合成 小波变换 KL变换
纹理合成是当前计算机视觉、计算机图形学、计算机图像处理等多个领域的研究热点之一。该技术可以由样本纹理得到与其相似的大块纹理，而且可以进行纹理填充、纹理传输等。纹理合成在图像修复、图像的真实感图形绘制、图像视频压缩等方面有着广泛的应用。
基于样图的纹理合成是近几年才发展起来的一门技术，由于该技术克服了早期的纹理映射和过程纹理合成的许多缺点，所以发展速度很快，并且逐渐成为了纹理合成的主流技术。根据合成方式的不同，基于样图的纹理合成可以分为两大类：基于点的纹理合成和基于块的纹理合成。早期的基于样图的纹理合成方法采用的都是基于点的合成方式。基于点的合成方式对于随机性纹理能够得到很好的合成效果，但是对结构性信息较强的纹理合成效果比较差，而且时间花费也较长。Efros[1]，Liang[2]等人采用基于块的合成方式合成纹理，一定程度上保证了结构的连贯性，而且合成速度也得到了很大提高。这些基于块的方法在匹配时直接用L2距离比较两个块的误差，由于没有突出图像结构信息的匹配，所以对于结构不太规则的纹理合成效果较差。近几年随着小波技术的发展与完善，有的学者将小波应用到纹理合成中，希望借助这个数学工具来达到较好的合成效果。使用小波的纹理合成方法，虽然在一定程度上改善了合成效果，但合成时间较长。有鉴于此，笔者将KL变换与小波变换相结合，提出一种新的纹理合成方法。
1 纹理合成时引入小波的方法
图像信号经过小波变换后可以用小波系数来描述，小波系数体现了原图像性质，图像信息的局部特征可以通过处理小波系数而改变。多尺度小波变换能够将图像的低频信息和高频信息分离，并通过对低频部分的逐层分解，将包含图像细节信息的高频部分提取出来，为分析图像的特征细节提供了很大的方便。
J.Chen和B.Zeng于2004年提出一种实时的基于块的多尺度的纹理合成方法[3]，将纹理合成引入到了小波域内，合成过程中仅对图像小波分解后的低频部分进行合成，使得合成得到了实时，但合成时却丢失了图像的高频信息，而这些部分恰恰是合成具有结构信息的纹理所不可或缺的。
Leandro Tonietto等人于2005年提出一种基于块的纹理合成[4]，对纹理合成时误差的度量做了修改，采用下式计算两个块的匹配误差：
式中，cBik和cBjk分别代表两个块重叠部分经过多尺度小波变换后的第k个小波系数，A是重叠部分像素的个数。在搜索最佳匹配块时，选择匹配误差最小的块作为当前块的最佳匹配块。该方法通过对重叠部分进行多尺度变换，用变换后的小波系数来体现图像的细节信息，在一定程度上考虑了图像结构内容的匹配，得到了较好的合成效果。但是在合成时没有做任何的预处理，导致了合成时间较长。
受上面方法的启发，这里提出一种基于小波的纹理合成方法，先对图像进行二维小波分解，然后只在分解后的低频部分进行最佳匹配块的搜索，这样可以在很大程度上减少搜索时间。在搜索最佳匹配块时，对计算匹配误差的公式(1)做了修改，比较匹配误差时增加了高频系数的权重，突出了结构信息的匹配。合成彩色图时，借鉴参考文献[5]的方法，用KL变换消除颜色失真，得到了较好的合成效果。
2 基于小波的纹理合成方法
传统的方法在搜索最佳匹配块时，直接对样图进行全局搜索，若样图较大将导致合成时间过长。在纹理合成之前先对样图进行二维小波分解，将样图分解为低频、水平高频、垂直高频、斜线高频四个部分。由于低频部分包含了样图大部分的能量，所以合成时只在低频部分搜索最佳匹配块，这样在很大程度上减少了搜索时间。对于其他部分则不再进行最佳匹配块的搜索，而是将其内部与在低频部分搜索到的最佳匹配块相对应的块作为最佳匹配块。如图1 所示，Bi块的左上角在图1(a)中的位置为(m，n)，Bj块的左上角在图1(b)中的位置也是(m，n)，则认为Bj块是Bi块在图1(b)中的对应块。这样就使全局搜索时的样图缩小为原样图的1/4，从而很大程度上缩短了搜索时间，提高了合成速度。四部分合成完以后，再通过小波重构" title="重构">重构得到输出图。
在低频部分搜索最佳匹配块时，与直接通过比较图像块的L2距离刻画其相似程度不同[3]，这里先对两个块的重叠部分进行一维多尺度小波变换，然后通过变换后的小波系数差异度量两个块的匹配程度。由于对图像进行多层小波分解，可以把图像中的高频信息逐层提取出来，而高频信息又往往表现为图像中的结构特征，所以可以通过比较两个块高频信息的匹配误差来度量纹理中结构特征的匹配程度。为了突出结构信息的匹配，在比较匹配误差时，对每一层的高频系数都赋予比低频系数高的权重。匹配误差的计算公式如下：
式中，Ah+Al=A(重叠部分像素的个数)，Ah、Al分别代表高频系数和低频系数的个数，α、β分别代表高频系数和低频系数所占的比重，搜索时选择d(Bi，Bj)最小的块作为当前块Bi的最佳匹配块。图2是使用不同匹配误差公式计算的合成效果图的比较。由图可以看出，对纹理块的重叠部分进行三层小波分解时，使用参考文献[4]方法计算匹配误差的合成效果图图2(b)中存在纹理错位、结构杂乱现象，与样图的纹理结构有较大出入，而使用本文方法的合成图较好地保持了原样图的结构，如图2(c)所示(其中α=2,β=1)。
上面的方法因为需要进行小波分解与重构，所以仅对灰度图适用。对于彩色纹理，由于每一个像素点都由R、G、B三基色表示，可以对三基色分别进行合成，但是这样会引起颜色失真，如图3所示。借鉴参考文献[5]的方法，使用KL变换解除R、G、B三基色的相关性，将彩色纹理变换成相互独立的三分量I1、I2、I3，然后对每个独立分量用上面提出的方法进行合成，生成相应的纹理图像，最后将三幅纹理图像变换回R、G、B彩色空间，生成最后的彩色纹理。
综上所述，将本文的算法总结如下：
(1)对彩色样图进行KL变换，将彩色图R、G、B分量变换成相互独立的I1、I2、I3分量。
(2)对每个独立分量Ii(i=1，2，3)进行二维小波分解，将图像分解为低频、水平高频、垂直高频、斜线高频四个部分。
(3)同时对低频、水平高频、垂直高频、斜线高频四个部分进行合成，但仅在低频部分进行最佳匹配块的搜索。
(4)对合成后的四个部分进行小波重构，得到该独立分量Ii的合成图像。
(5)重复(2)～(4)，得到I1、I2、I3三分量的合成图像。
(6)将I1、I2、I3三分量的合成图像变换回R、G、B彩色空间，输出最终的彩色合成" title="彩色合成">彩色合成图。
3 实验参数及结果分析
所有实验都是在CPU主频2.66GHz、内存512MB" title="512MB">512MB的Pentium IV PC机上使用Matlab实现。
实验中纹理块的大小对合成结果有较大影响，如果纹理块太小，则块内包含的信息较少，将导致合成的结果呈现较大的随机性，不能很好地匹配当前块；纹理块太大的话，每次小波变换的时间会较长。所选纹理块的尺寸一般应该能够涵盖一个纹理基本元素，重叠部分取纹理块的1/4～1/2。表1给出了实验时对于不同样图所选的参数。
二维小波分解和多尺度小波变换时都采用haar小波，多尺度小波分解到三层或者分解到低频系数的个数少于4。
图4给出了本文方法与参考文献[1]方法的比较，可以看出本文方法克服了参考文献[1]方法引起的纹理错位的问题。图5给出了本文方法与参考文献[2]方法、参考文献[4]方法的比较。可以看出，本文方法和参考文献[4]方法在效果上都优于参考文献[2]方法，较好地克服了参考文献[2]方法引起的纹理错位，结构杂乱的问题。而且，由表2可以看出本文方法的合成时间明显少于参考文献[4]方法的合成时间。为了比较其效果，实验时对不同方法选择了相同的初始点。实验所用时间为多次实验的平均。
本文提出了一种基于小波的纹理合成方法，将KL变换及小波变换应用于彩色纹理的合成中，不仅得到了较好的合成效果，合成速度也得到了很大提高。该算法虽然使得合成速度得到了很大提高，但是要想实时地合成纹理，还有很多工作要做。
参考文献
[1] EFROS A A，FREEMAN W T.Image quilting for texture synthesis and transfer[J].Proc SIGGRAPH，2001，(8)：341-346.
[2] LIANG L，LIU C，XU Y et al.Real-time texture synthesis by patch-based sampling[R].Technical Report MSR- TR-2001-40，Microsoft Research，2001.
[3] CHEN J，ZENG B.Patch-Based Multi-Resolution Real-Time Texture Synthesis in Wavelet Domain[J].Chengdu(CN)：International Conference on Communications，Circuits and Systems，2004，2：788-791.
[4] TONIETTO L，WALTER M，JUNG C R.Patch-based texture synthesis using wavelets[C].Proceedings of SIBGRAPI(Natal，Brazil，October 2005)，IEEE Computer Society，2005：383-389.
[5] 李厚强，董朋朋，叶中付.基于无参数Markov随机场模型的彩色纹理综合方法[J].计算机工程，2003，29(18)：34-36.