基于L邻域分割的结构性纹理合成方法

张雨禾，耿国华，刘伦椿，周子骏

(西北大学信息科学与技术学院，陕西西安710127)

纹理技术可以表现几何模型无法体现的细节和特征，弥补几何绘制的不足，在计算机基于图像的真实感绘制中占据重要的地位。常见的纹理技术主要有纹理映射、过程纹理合成和基于样图的纹理合成。基于样图的纹理合成技术，既克服了传统纹理映射的缺点，同时避免了过程纹理合成中的参数选择等繁琐过程，因而受到越来越多的关注。目前，基于样图的纹理合成技术基本上都是基于马尔可夫随机场模型［1］的。在1999年的ICCV会议上，Eorfs和Lueng率先提出了非参数采样的算法［2］，该方法利用纹理图像中邻近点相关性强的特征，根据预先在待合成图中设置的种子，从而在给定的邻域中查找匹配点来合成纹理，随后的纹理合成算法都受到了该方法的影响。Ashikhmin利用相邻像素间的相关性原理进行纹理合成［3］，对自然纹理的合成取得了很好的效果。针对纹理块的拼接，Efros提出了一种基于块缝合的纹理合成算法［4］，通过查找误差最小的路径实现各块的拼接，对一些纹理取得了非常好的效果。Kwatra使用GraphCut进行纹理合成［5］，并将ImageQuilting算法中的矩形纹理块推广到任意形状，获得了较高的合成质量。随后在这些基本合成算法的基础上，研究学者又提出了一些改进的合成方法［6-8］，合成速度和质量都得到了很大的提高。

纹理合成的主要步骤是:1)确定当前需要合成的点(或块)的位置;2)根据当前位置的邻域的特征，从样图或自身图像中寻找相似块;3)将搜索到的相似块和已存在的图像合并。3)图像拼合的好坏往往依赖于2)中寻找的相似块，如果相似块与输出图像不能较好地匹配，即使后续运用较好的拼接算法，最后也难免存在视觉上的不连贯。现有的算法通常都是精确到像素点的计算，采用基于RGB色彩空间的L2距离，即对二者L邻域中的每个像素点对，求其在颜色空间中的差值和，如果差值和小于给定的阈值，则认为相匹配。从视觉的角度观察图像，每个像素对人眼和心理的刺激是不同的，像点之间的相关性也是不同的。而在L2距离公式中，却将L邻域中的所有像点放在同等的地位对待。目前已有很多学者认为将L邻域作为邻域的相似性判断条件，存在着不足，将其不足归因为使用其整体匹配误差［9-10］。该误差直接造成合成后纹理的不连续，或者丢失样本纹理中的某些特征信息，从而严重影响纹理的合成质量。

本文就针对以上使用L邻域的整体匹配误差而造成的纹理合成质量差的问题进行了讨论，利用结构性纹理中像点间的相关性信息，提出了一种新的邻域匹配方法，改进了现有算法运行速度慢以及易产生误匹配等缺点，有效地改善了纹理合成的视觉效果，加快了纹理合成中预处理的速度。

1 L邻域的分割理论

结构性纹理中存在纹元(保持纹理局部特性的最小纹理块)，整个纹理图像可以由一系列的纹元及其摆放规则决定，因此，结构性纹理往往具有一定的周期重复性和方向性(在这里主要指纹理的主方向)。从视觉角度来讲，纹元相同，摆放规则不同，则构成的纹理图像也不同，纹理图像的周期和主方向也就不同。纹理的主方向体现在纹理图像的结构构成上，就是像点之间的相关性，即处于(或接近)纹理主方向上的像点之间相关性较强，否则，相关性较弱。纹理的方向是一个区域上的概念，是在一个大的邻域内的统计特性。依据这一特性，要保证生成的图像与样图图像在视觉上保持相似性，在L邻域的相似性度量中，就应将L邻域中与待合成像点相关性较强的像点放在更重要的位置，优先考虑其相似性。

在像点P的L邻域中(如图1所示)，像点的位置不同，其与待合成像点的相关性也不同。结合L邻域的特点，取4个特殊方向，将L邻域分割为4个区域(如图2所示)。其中，区域1与像点P成45°;区域2与像点P成90°;区域3与像点P成135°;区域4与像点P成0°。

图1 像点P的L邻域Fig.1 L neighbor of pixel P

图2 像点P的分割L邻域Fig.2 Segmented L neighbor of pixel P

2 L邻域分割纹理合成方法

基于L邻域分割的合成方法，如果只用分割后的一部分邻域来寻找匹配块，同样只是考虑到了局部匹配的误差，也会出现匹配错误。所以本文方法兼顾局部和整体的误差，设计了一种新的匹配规则:对L邻域进行分割，采用基于优先级的多次匹配，完成L邻域的完整匹配。

2.1 灰度共生矩阵

灰度共生矩阵(记为W阵)［11］是统计空间上具有某种位置关系的一对像元灰度对出现的频度。其实质是从图像灰度为i的像元(位置为x，y)出发，统计与其距离为d，灰度为j的像元(x+Dx，y+Dy)同时出现的频度p(i，j，dH)，数学表达式为

式 中:(x，y)是 图 像 的 像 元 坐 标;i、j=0，1，...，L－1是灰度级，Dx、Dy是位置偏移量，d为W阵的生成步长。基于L邻域自身的特点，本文方法计算灰度共生矩阵时，取d=1，即灰度共生矩阵的生长步长为1;θ为W阵的生成方向，当Dx=1，Dy=0时，像素对是水平的，即0°扫描，θ=0°;当Dx=0，Dy=1时，像素对是竖直的，即90°扫描，θ=90°;当Dx=1，Dy=1时，像素对是右对角线，即45°扫描，θ=45°;当Dx=－1，Dy=1时，像素对是左对角线，即135°扫描，θ=135°。

灰度共生矩阵的相关值如式(2)所示，被用来度量灰度共生矩阵元素在行或列方向上的相似程度［12］，如果图像的某方向上纹理性较强，则该方向的相关值W3将大于其他方向的值。因此，W3可用来判断纹理在4个特殊方向上的相关程度。如图3所示。由图可见，该纹理样图像素对在竖直方向上具有较大的相关性，其次是水平方向，并且水平方向和竖直方向上的像点间相关性较接近，像点间相关性较小的是右对角线方向及左对角线方向。

图3 样本纹理及其相关值Fig.3 Sample texture and its IDM

2.2 基于灰度共生矩阵相关值的优先级分配

根据计算出的灰度共生矩阵的相关值，按照由高到低的顺序依次对已分割好的L邻域的4个区域进行优先级的分配:使得相关值最大的θ值对应的区域，分配最高的优先级，使得相关值次大的值对应的区域，分配次高的优先级，依次类推，完成L邻域所有已分割区域的优先级分配。如图4所示，按照优先级分配原则，优先级由高到低的次序依次为:区域1、区域 2、区域3、区域 4。

图4 优先级分配示意图Fig.4 Priority assignment

2.3 L邻域的多次匹配

使用分割L邻域的方法对结构性纹理合成时，需要经过多次匹配才能找到最符合条件的L邻域，然后将其拼贴到合成图中，这种分而治之的方法，虽然步骤增加了，但是计算量却明显下降了，具体步骤如下:

1)选取L邻域中优先级最高的部分进行匹配。即在原样图中搜索与该部分颜色差最小的块，如果误差大于给定的阈值K1，则丢弃此块继续搜索，若小于K1，转到步骤2);

2)选取L邻域中优先级次高的部分进行匹配。即在原样图中搜索与该部分颜色差最小的块，如果误差大于给定的阈值K2，则丢弃此块，转向步骤1)，重新搜索;若小于K2，转到步骤3);

3)选取L邻域中优先级次低的部分进行匹配。即在原样图中搜索与该部分颜色差最小的块，如果误差大于给定的阈值K3，则丢弃此块，转向步骤1)，重新搜索;若小于K3，转到步骤4);

4)选取L邻域中优先级最低的部分进行匹配。即在原样图中搜索与该部分颜色差最小的块，如果误差大于给定的阈值K4，则丢弃此块，转向步骤1)，重新搜索;若小于K4，L邻域匹配完成。

在多次匹配的过程中，如果一步不能找到最优值，即没有块的颜色差值小于给定的阈值，则在全局中选择最接近阈值的块，进行下一步的搜索匹配。

新的匹配规则，加快了预处理过程，并减少了传统的L邻域在整体邻域匹配搜索过程中存在的计算复杂性和匹配误差。

2.4 分割法的算法流程

使用分割法进行纹理合成，其步骤可以简单的描述为:

1)计算纹理样图的灰度共生矩阵的相关值;

2)找到待合成的像点(或块);

3)对待合成像点(或块)的L邻域进行分割和优先级的分配;

4)进行L邻域的多次匹配;在L邻域的多次匹配过程中，利用式(3)，计算匹配误差，最终找到最佳匹配块;

5)对待合成像点(或块)进行合成，若已完成图像的合成，则转向6)，否则转向2);

6)算法结束。

3 实验结果分析

3.1 实验结果

本文方法通过Matlab7进行了实现，对于给定输入基本图，为减少计算量，对原始图像灰度级进行压缩，量化成16级。实验分别采用文献［13］、文献［14］及本文方法(在实现本文方法时，采用与文献［14］相同的匹配块搜索策略，在匹配块的相似性度量中采用本文方法)，在计算机上进行了大量的实验。

实验结果对比图如图5～7所示。

图5 实验结果图:纹理中像点在一个方向上相关性较强Fig.5 Comparison of experimental results:Strong correlation in 1-direction

图6 实验结果图:纹理中像点在2个方向上相关性较强Fig.6 Comparison of experimental results:Strong correlation in 2-direction

图7 实验结果图:纹理中像点在3个方向上相关性较强Fig.7 Comparison of experimental results:strong correlation in 3-direction

图5中的纹理样图的像点在一个方向(角度)上相关性较强而在其他3个方向上相关性较弱;图6中的纹理样图的像点在2个方向上相关性较强且在其余2个方向上相关性较弱;图7中的纹理样图的像点则在3个方向上相关性较强而在另一个方向上相关性较弱。结果表明，本文的方法在处理结构性纹理时，效果好坏不依赖于其自身方向的复杂性，能够较好的保留结构性纹理样图中的结构性信息、周期性、颜色、基本纹元信息及其摆放规则等特征分布规律，获得令人满意的效果。

3组实验执行时间如表1所示，不难看出，采用分割法进行纹理合成，加快了纹理合成中预处理的速度，进而提高了纹理合成的速度。

表1 3种方法执行时间比较Table 1 Execution time comparison of 3 methedss

3.2 性能评价

1)纹理合成时间

本文方法与传统方法在进行L邻域匹配中，分别利用L邻域的分割区域与L邻域整体进行计算以度量L邻域的相似度。下面分别通过邻域不匹配和邻域匹配2种情况对其时间性能进行分析。

①L邻域不匹配

原样图中当前搜索到的L邻域与待合成块的L邻域不匹配时，传统方法利用L邻域整体做相似性度量，在误差计算过程中，需要参与计算的像点数F为

式中:n为邻域的规模。

而本文方法在对L邻域的相似性度量中，将L邻域分割成4个区域分别进行计算，每个区域的像点数约为整个L邻域像点数的1/4。因此，需要参与计算的像点数F'为

式中:θ≤1，为匹配阶段计数值。即:当优先级最高的分割区域不匹配时，θ=1/4;当优先级次高区域不匹配时，θ=2/4;当优先级次低的区域不匹配时，θ=3/4;当优先级最低的区域不匹配时，θ=1。

②L邻域匹配

当原样图中当前块L邻域匹配时，本文方法中L邻域的4个区域都已参与计算，与传统方法相同，因此，参与计算的像点数相同，如式(4)所示。

综上所述，在保证匹配精度相同的情况下，当L邻域匹配时，本文方法计算的像点数与传统方法相同;但在不匹配时，本文方法需要计算的像点数明显少于传统方法。因此，本文方法能够有效地减少L邻域匹配过程中的计算时间，降低纹理合成的预处理速度，进而提高纹理合成的速度。并且，在大规模绘制中，随着邻域规模的增大，本文方法的性能越好，如图8所示。

图8 时间对比图Fig.8 Comparison of time

2)纹理适用性

结构性纹理中含有纹元，每个纹元基本相同且其排列具有一定的结构性及周期性，本文在处理结构性纹理时，能够有效的保持结构性纹理中的周期性等结构特征，获得了令人满意的效果，如图5所示。

本文在上述实验基础上，还对自然纹理、随机型纹理(即纹元大小、颜色等不全相同，但是又呈现出一定的规律性)、纹元结构较简单型纹理及纹元结构较复杂型纹理分别进行了仿真实验，结果如图9～12所示。实验结果表明，本文方法在处理不同类型纹理时，都获得了较好的视觉效果，表现出了较强的适用性。

图9 自然纹理Fig.9 Natural texture

图10 随机型结构Fig.10 Random structural texture

图11 简单纹元结构Fig.11 Simple texel

图12 复杂纹元结构Fig.12 Complex texel

3)L邻域匹配块优化性

传统方法在进行L邻域的匹配时，采用了L邻域整体误差作为相似性度量标准，因为其只反映了邻域中像点颜色的统计分布差异，并未考虑到邻域中像点颜色的空间分布特征。如图8所示，空间分布差别很大的2个块，统计分布差异却很小。因此，采用传统方法进行邻域匹配时，会造成一定的匹配误差，甚至是匹配错误，从而导致在纹理合成全局误差的累积，严重影响合成效果。

图13 空间分布差别说明图Fig.13 Different spatial distribution

本文方法在进行L邻域的匹配时，将L邻域进行分割，采用基于L邻域分割的优先级多次匹配方法，对各个已分割区域分别进行相似性度量，既能反映出2个L邻域中像点颜色的统计分布差异，又能考虑到其空间分布差异。有效地减少了L邻域匹配过程中的误差，从一定程度上解决了误匹配问题，对提高纹理合成的质量具有明显的效果。

4 结束语

本文在充分考虑了结构性纹理的方向性、周期性等特点的基础上，提出了一种基于L邻域分割的优先级多次匹配方法，通过计算纹理样图的灰度共生矩阵相关值，完成L邻域所有已分割区域的优先级分配，有效地改善了纹理合成的视觉效果，对减少匹配误差、提高运算速度具有明显效果。

通过实验验证，本文方法在处理结构性纹理、随机型纹理以及自然纹理时，均能获得令人满意的效果。同时，本文方法的效果好坏不依赖于纹元结构的复杂性，即在处理简单纹元结构和复杂纹元结构的纹理图像时，均能获得较好的视觉效果。

如何提高纹理中像点间相关性度量的精确度，以及如何在纹理合成的过程中考虑到纹理的结构性信息将作为下一步的研究方向。

［1］王兴梅，印桂生，门志国，等.基于MRF的动态场景中运动目标提取方法研究［J］.哈尔滨工程大学学报，2011，32(8):1029-1034.WANG Xingmei1，YIN Guisheng，MEN Zhiguo，et al.Research on the extraction algorithm for a moving target in a dynamic scene based on Markov random fields(MRF)［J］.Journal of Harbin Engineering University，2011，32(8):1029-1034.

［2］EFROS A A，LEUNG T K.Texture synthesis by non-parametric sampling［C］//The Proceedings of the Seventh IEEE International Conference on Computer Vision.［S.l.］，1999:1033-1038.

［3］ASHIKHMIN M.Synthesizing natural textures［C］//Proceedings of the 2001 symposium on Interactive 3D graphics.NC USA:AMC Press，2001:217-226.

［4］EFROS A A，FREEMAN W T.Image quilting for texture synthesis and transfer［C］//Proceedings of the 28th annual conference on Computer graphics and interactive techniques.Los Angeles:AMC Press，2001:341-346.

［5］KWATRA V，SCHÖDL A，ESSA I，et al.Graphcut textures:image and video synthesis using graph cuts［C］//ACM Transactions on Graphics(TOG).San Diego:AMC Press，2003，22(3):277-286.

［6］李大锦.一种改进的自然纹理合成方法［J］.图学学报，2012，4(33):88-92.LI Dajin.An improved method of natural texture synthesis［J］.Journal of Graphics，2012，4(33):88-92.

［7］杜常青，钱文华.二维纹理合成算法优化研究［J］.计算机科学，2013，4(40):314-316.DU Changqing，QIAN Wenhua.Optimization technique of 2D texture synthesis［J］.Computer Science，2013，4(40):314-316.

［8］王继东，庞明勇，赵瑞斌.旋转的Wang Tiles纹理合成算法［J］.中国图象图形学报，2013，1(18):49-54.WANG Jidong，PANG Mingyong，ZHAO Ruibin.Texture synthesis using rotational wang tiles［J］.Journal of Image and Graphics，2013，1(18):49-54.

［9］ZHU S C，LIU X W，WU Y N.Exploring texture ensembles by efficient markov chain monte carlo-toward a“trichromacy”theory of texture［J］.IEEE Transactions on Pattern Analysis and Machine Intelligence，2000，22(6):554-569.

［10］ZUCKER S W，TERZOPOULOS D.Finding structure in co-occurrence matrices for texture analysis［J］.Computer graphics and image processing，1980，12(3):286-308.

［11］HARALICK R M.Statistical and structural approaches to texture［J］.Proceedings of the IEEE，1979，67(5):786-804.

［12］刘舒，姜琦刚，邵永，等.应用灰度共生矩阵的纹理特征描述的研究［J］.科学技术与工程，2012，33(12):8909-8914.LIU Shu，JIANG Qigang，SHAO Yongshe，et al.Investigation of the textual description based on gray level co-occurrence matrix measurements［J］.Science Technology and Engineering，2012，33(12):8909-8914.

［13］WEI L Y，LEVOY M.Fast texture synthesis using treestructured vector quantization［C］//Proceedings of the 27th annual conference on Computer graphics and interactive techniques.New Orleans:ACM Press/Addison-Wesley Publishing Co，2000:479-488.

［14］岳晓菊，康宝生，闫丽君.利用相关性原理纹理合成的改进算法［J］.计算机工程与应用，2011，10:190-192.YUE Xiaoju，KANG Baosheng，YAN Lijun.Improved algorithm for texture synthesis based on principle of relevance［J］.Computer Engineering and Applications，2011，47(10):190-192.