孙劲光　刘双九

1(辽宁工程技术大学电子与信息工程学院　辽宁 葫芦岛 125105)

2(辽宁工程技术大学研究生学院　辽宁 葫芦岛 125105)



尺寸自适应的T-Tile三维纹理合成

孙劲光1刘双九2

1(辽宁工程技术大学电子与信息工程学院辽宁 葫芦岛 125105)

2(辽宁工程技术大学研究生学院辽宁 葫芦岛 125105)

摘要以Wang Tiles纹理合成算法思想为基础，提出一种新的三维网格纹理合成算法。首先，分析给定的样本纹理，得到适当的纹理块尺寸，根据该尺寸从样本纹理中选取3个菱形纹理块，生成T-Tile初始框架；其次，从样本纹理中提取与T-Tile初始框架尺寸相同的纹理块作为替代纹理块，与初始框架完全重叠放置，制作T-Tile；最后，调整给定的三角网格模型为等边三角形网格模型，按照T-Tile边界颜色匹配的原则进行三角形面片的纹理合成。实验结果表明，该算法能够以较快的速度进行纹理合成，达到了实时纹理合成的效果，同时也可以得到较高的纹理合成质量。

关键词纹理三维纹理合成T-Tile初始框架替代纹理块最佳缝合路径T-Tiles集合

T-TILE 3D TEXTURE SYNTHESIS ALGORITHM WITH SIZE ADAPTED

Sun Jinguang1Liu Shuangjiu2

1(School of Electronic Information Engineering,Liaoning Technical University,Huludao 125105,Liaoning,China)2(School of Graduate,Liaoning Technical University,Huludao 125105,Liaoning,China)

AbstractThis paper presents a new three dimensional mesh texture synthesis algorithm based on the idea of Wang Tiles texture synthesis algorithm. First,we analysed the given sample texture to get appropriate size of texture blocks,and picked up three diamond texture blocks from sample texture according the size,and generated initial framework of T-Tile. Secondly,we extracted the texture blocks having the same sizes as the initial T-Tile framework from texture sample as the alternative blocks,and placed them completely overlapping with initial framework and designed the T-Tile. Finally,we adjusted the given triangular mesh model to an equilateral triangle mesh model,realised the triangular facets texture synthesis according to the principle of colour matching of T-Tile’s border. Experimental results show that this algorithm can complete texture synthesis quickly,achieves the effect of real-time texture synthesis,and can meanwhile reach higher quality of texture synthesis.

KeywordsTexture3D texture synthesisInitial T-Tile frameworkAlternative texture blockOptimal stitching pathT-Tiles set

0引言

纹理能够表现出物体表面的丰富细节，因此三维纹理的实时绘制成为真实感图形学等多领域的研究热点。基于样本的纹理合成能够在网格曲面上快速、准确地生成纹理，它的主要思想是根据用户给定的样本纹理，生成目标纹理，同时保证目标纹理自身的连续性以及它与样本纹理的相似性。基于样本的纹理合成自提出以来，迅速成为众多文献的研究热点。

基于样本的纹理合成根据合成单元分为基于像素点的纹理合成与基于块的纹理合成两大类。基于像素点的纹理合成是以像素为纹理单元进行纹理合成[1-3]，该类算法虽然能够取得较高的纹理合成质量，但受到了纹理合成速度的限制。基于块的纹理合成能够很大程度上提高合成速度。2001年，Efros等人[4]首次基于纹理块这一思想提出Image Quilting算法，该算法取得了较好的纹理合成质量与合成速度。2003年，Cohen[5]等人提出Wang Tiles纹理合成算法，该算法为基于块的纹理合成开辟了一个新的思路。它将纹理合成分为两个阶段，即纹理块制作阶段与纹理合成阶段，通过分离纹理块制作与合成达到纹理的实时合成。随后，受该算法启发，众多相关文献相继提出[6，7]。

三维纹理合成是对二维纹理合成的推广。2000年，Praun等人[8]提出的Lapped Texture算法通过将纹理块重复粘贴到目标网格直到整个网格被纹理覆盖，从而完成曲面纹理合成。2001年，Turk等人[9]以及Wei等人[10]先后提出三维曲面纹理合成算法，都是采用多分辨率思想，基于像素点进行纹理合成。随后，一类基于块的曲面纹理合成算法相继提出[11-14]，其基本思想都是以三角形纹理块为纹理单元进行合成。将当前待合成三角形面片相邻的已合成的纹理块作为约束条件，提取匹配模版，在样本纹理中搜索适当的三角形纹理块合成。在合成复杂的网格模型时，该类算法由于大量的搜索匹配操作导致合成速度很低。2009年，薛峰等人[15]提出基于Triangle-Tiles的三维曲面实时纹理合成算法，该算法采用Wang Tiles纹理合成算法的基本思想。首先从样本纹理中选择菱形纹理块制作一系列可以拼接的三角形纹理块称为Triangle-Tile，然后调整给定的网格曲面，根据边界颜色匹配的原则在网格上拼接三角形纹理块完成纹理合成。该算法取得了较高的纹理合成质量，同时在很大程度上提高了曲面纹理合成的速度。

本文受基于Triangle-Tiles的三维曲面实时纹理合成算法启发，以Wang Tiles纹理合成算法思想为基础，提出一种新的三维纹理合成算法。相对于文献[15]，本文算法有几个改进之处。首先是对纹理样本进行分析，取得适当的尺寸，这使得纹理结构在很大程度上得到保护。其次，在制作Tiles的方式上进行改进，使得Tile质量有一定的提高，即Tile内部接缝的明显程度要降低。

1Wang Tiles纹理合成算法思想

Cohen等人提出的Wang Tiles纹理合成算法主要思想就是制作一系列边界可以进行无缝拼接的正方形纹理块。通过这些纹理块的拼接完成纹理合成，该算法称这些正方形纹理块为Tile。

它将纹理合成分为两个阶段。首先是制作Tile阶段，该阶段从样本纹理中提取4个菱形纹理块进行有重叠拼接，重叠部分通过Image Quilting算法中求取最佳缝合路径方式拼接两纹理块，最终生成Tile。其次，排列4个菱形纹理块顺序，制作Tiles集合，选取Tiles集合中的Tile，按照边界颜色匹配的原则进行拼接，实现纹理合成。

2尺寸自适应的T-Tile三维纹理合成

基于Wang Tiles纹理合成算法的思想，本文提出一种新的三维纹理合成算法。从样本纹理中选择3个等边菱形纹理块，无重叠拼接生成T-Tile初始框架。提取与T-Tile尺寸相同的三角形纹理块，称为替代纹理块，与T-Tile完全重叠求取最佳缝合路径，生成T-Tile。改变菱形纹理块位置，同时选择新的替代纹理块，制作T-Tile，从而得到T-Tiles集合。由于生成的T-Tiles集合中的T-Tile是边界可以进行无缝拼接的等边三角形纹理块，因此，对于给定的目标网格曲面。首先要进行网格调整，使得网格上每个三角形面片均为等边三角形。最后，按照边界颜色匹配的原则在网格上进行纹理合成。下面给出本文算法的简单步骤描述，以及算法流程图，如图1所示。

1) 制作T-Tile，并生成T-Tiles集合，详见2.1节；

2) 调整目标网格模型为等边三角形网格模型，在目标网格上根据T-Tile边界颜色匹配的原则进行纹理合成。具体见2.2节所述。

图1　本文算法流程图

2.1制作T-Tile

2.1.1构造T-Tile初始框架

图2　T-Tile尺寸确定图

图3　T-Tile初始框架提取示意图

2.1.2制作T-Tile

从样本纹理中提取与T-Tile初始框架尺寸相同的三角形纹理块，称为替代纹理块，与T-Tile重叠，重叠区域分为3个部分，如图4所示，分别求其最佳缝合路径。每个重叠区域都看作一个倒三角形，按照Image Quilting算法分别求取重叠部分的最佳缝合路径，最终得到T-Tile，如图5所示。

图4　T-Tile初始框架与替代纹理块重合

图5　T-Tile示意图

改变三个菱形纹理块的位置，同时，重新从样本纹理中提取替代纹理块与T-Tile初始框架重叠，生成新的T-Tile，从而生成T-Tiles集合。

本文算法中，最初选择的菱形纹理块主要是为了进行T-Tile边界颜色匹配，而替代纹理块作为T-Tile的主要填充部分。当三维网格模型过于复杂时，可以通过选择不同的替代纹理块与同一T-Tile初始框架重叠，生成不同的T-Tile，增加T-Tile的数量，从而避免纹理块大量重复。

2.2三维纹理合成

2.1节所制作的T-Tile都是等边三角形纹理块，而给定的目标网格是由非等边三角形面片构成的，因此想要将T-Tile无扭曲映射到三角面片上，需要对给定的目标网格进行调整，使得网格上三角形尽可能趋向于等边三角形。

2.2.1网格模型调整

本文使用文献[15]中提到的对基于二次误差的网格简化算法改进后的算法进行网格调整，最终得到的网格模型能够在保证与给定网格模型拓补一致的前提下，满足网格上所有三角形面片尽可能趋向于等边三角形。

基于二次误差的网格简化算法为每个顶点v=[vx,vy,vz,1]T定义收缩误差Δ(v)，用p(v)表示以点v为其一个顶点的三角面片，Δ(v)表示v到p(v)中所有三角面片的距离平方和，定义其计算公式如下所示：

(1)

其中，p=[a,b,c,d]T表示p(v)中的一个平面，Kp计算公式如下：

(2)

基于以上定义，网格简化具体步骤描述如下：

1) 计算网格中每个顶点的收缩误差矩阵Q。

3) 将所有边的折叠误差从小到大排序放入队列中。队首元素出队，该边进行折叠，同时更新与该边相关的边的折叠误差。重复该步骤，知道满足网格简化要求为止。

2.2.2纹理合成

由2.2.1节得到的等边三角形网格模型与2.1节得到的T-Tiles集合，进行纹理合成。具体步骤如下：

1) 建立一个存储三角形面片的队列，该队列中三角形面片按照其约束度从大到小排序，称该队列为待合成面片队列。初始化待合成面片队列为空队列。

2) 随机选择网格上一个三角形面片，同时，随机从T-Tiles集合中选择T-Tile纹理映射到该三角形面片上。将该三角形面片相邻的三角形面片按照约束度从大到小加入到待合成面片队列中。

3) 取队列首元素出队，同时将其作为当前待合成三角形面片，根据其相邻的已合成三角形面片边界颜色从T-Tiles集合中选择T-Tile进行纹理映射。按照需要更新队列中已存在的三角形面片的约束度并排序，同时将与当前合成的三角形相邻并且没有进行纹理合成的三角形面片按照约束度大小加入到队列中。重复该步骤，直到整个网格曲面片都覆盖到纹理为止。

2.3算法实现部分

本文采用面向对象思想进行程序设计与实现，主要涉及到的实体对象有纹理样本，用来制作T-Tile初始框架的菱形纹理块、替代纹理块、T-Tile、T-Tiles集合、原始三维模型、等边三角形网格模型等。控制类对象主要有分析纹理块得到边长操作、选取纹理块操作、制作T-Tile操作、三角网格模型简化操作、纹理合成操作等。下面给出本文算法几个主要对象的类设计以及算法核心伪代码。

纹理样本类：CTexSam

Class CTexSam

{

QImage* tex;

//图像句柄

int twidth;

//纹理样本宽度

int theight;

//纹理样本高度

};

菱形纹理块类：CDiaTex

Class CDiaTex

{

QImage* tex;

//图像句柄

int len;

//等边菱形纹理块边长

int tid;

//标记该纹理块

}

三角形纹理块：CTriTex

Class CTriTex

{

QImage* tex;

//图像句柄

int len;

//等边三角形纹理块边长

}

T-Tile类：CTtile

Class CTtile : public CTriTex

{

int tid1;

//标记制作该T-Tile的纹理块顺序(位置)

int tid2;

//标记制作该T-Tile的纹理块顺序(位置)

int tid3;

//标记制作该T-Tile的纹理块顺序(位置)

}

T-Tile制作函数：ttilemake，根据输入的T-Tile初始框架tframe与替代纹理块otex，进行重叠，重叠部分分为3个区域，分别求取最佳缝合路径，沿着该路径进行纹理块拼接得到T-Tile。

ttilemake(tframe,otex)

{

for(每一个重叠区域)

{

for(每一个像素)

{

计算ei,j，Ei,j;

}

}

for(每一个重叠区域)

{

for(最后一行开始，向上寻找每一行)

{

找到该行Ei,j最小像素，标记;

}

}

for( T-Tile每一行)

{

for(每一列像素)

{

根据该像素与标记像素位置关系判断其取值为tframe像素值还是otex像素值;

}

}

得到最终T-Tile;

}

三角网格模型简化函数：tmeshcut，根据输入的三角网格模型otrimesh，进行二次误差网格简化算法，生成等边三角形网格ntrimesh。

tmeshcut(otrimesh)

{

ineqquene();

//初始化折叠误差队列为空

for(每个顶点)

{

vqcalculate();

//计算该点收缩误差矩阵

}

for(每条边)

{

eqcalculate();

//计算该边折叠误差

qenquene();

//该误差值入队

asquene();

//升序更新折叠误差队列

}

while(未达到简化要求)

{

qexquene();

//队首误差值出队

nvcalculate();

//根据该误差对应的矩阵计

//算该边折叠后的新点位置

upequene();

//更新队列中与该边相关的

//边的折叠误差

}

得到等边三角形网格模型ntrimesh;

}

纹理合成函数：texsyn，根据边界颜色匹配的原则，使用T-Tiles集合在ntrimesh上合成纹理。

texsyn(T-Tiles,ntrimesh )

{

intriquene();

//初始化待合成面片队列为空

inransel();

//随机选择网格上一个面片作为当前待合成三角面片

ranselttile();

//随机选择一个T-Tile

textotri();

//映射T-Tile到待合成三角面片，并标记该三角面片

ensdtriquene();

//待合成三角面片相邻且未标记的面片入队列

astriquene();

//约束度升序排序队列

while(triquene!=NULL)

{

txtriquene();

//队首元素出队，作为当前待合成面片

conselttile();

//根据边界颜色匹配原则选择T-Tile

textotri();

//映射T-Tile到待合成三角面片，并标记该三角面片

while(存在三角面片未进入待合成面片队列)

{

ensdtriquene();

//待合成三角面片相邻且未标记的三角面片入队列

astriquene();

//约束度升序排序队列

}

}

}

3实验结果及分析

本文选择Microsoft Visual Studio 2010中visual C++作为开发环境，结合openGL库函数的使用，采用C++语言进行实验，实验机器为2.60 GHz CPU，2.00 GB RAM，32位Windows7操作系统的PC机。实验中原始纹理数据来源于纹理合成发展历程中经典纹理合成算法所使用数据，纹理样本尺寸为400×400像素，分辨率为500 ppi，实验中纹理样本为RGB彩色无噪音png类型文件。三维网格模型数据选择.max文件，由3DMax生成。

选择不同特征的样本会对纹理合成效果产生一定的影响。纹理样本尺寸越大，纹理合成效果越理想，反映到输出纹理上就是纹理的多样性越明显，重复性就越低。反之，纹理样本较小的情况下，由于取样受到限制，输出纹理就会出现重复现象。样本如果存在噪音现象，要首先对样本进行噪音处理，再采用本文算法进行纹理合成。纹理样本其它特征例如分辨率、图像类型则不会对算法产生影响。由于本文算法进行纹理合成之前对三维网格模型进行了一定的简化操作，因此，模型的复杂度不会对纹理合成效果产生很大影响。

图6给出的是由2.1节算法制作的T-Tile，图中可以看出，T-Tile中心处没有明显的接缝，边界纹理重合部分拼接的也比较柔和。由本文算法得到的T-Tile有一个很好的视觉效果。

图7中给出了本文算法在多个三维模型上的合成效果。相同的样本纹理在不同三维模型上的合成效果是不同的。对模型比较复杂、三角面片比较小而面片数目比较大的模型来说，局部会出现纹理扭曲的现象。同一个模型，不同的样本纹理合成效果也不尽相同，对于随机性纹理，纹理合成质量比较高，而对于结构性比较强的纹理，仍然会有小部分纹理结构被破坏。

为了进一步说明该算法的有效性，用三角形纹理块匹配率来衡量纹理合成质量[15]，匹配率越高表示纹理合成质量越高。同时给出纹理合成时间说明算法的实时性，具体数据如表1所示。由表可得，该算法所需合成时间较低，基本上能够达到实时合成效果。约束度为1和2的纹理块基本上都能够在T-Tiles集合中找到匹配的纹理块，约束度为3的纹理块占有很小的比例。因此，算法中纹理块的匹配率基本上达到百分之百，说明纹理合成质量较高。

图6　本文算法制作的T-Tile

图7　三维模型纹理合成

模型网格数不同约束度三角面片个数C=1C=2C=3合成时间(s)匹配率(%)球41022718022.4100狗88061425695.699.3鱼60037022454.299.6

4结语

本文将二维纹理合成中经典算法Wang Tiles纹理合成中心思想拓展到三维纹理合成中，完成三维纹理合成。在制作T-Tile初，通过纹理分析得到适当的纹理块尺寸，以保证纹理结构信息在最大程度上得到保护。由第3节实验结果分析可以得到，本文算法达到了实时合成纹理的效果，同时得到了较高的纹理合成质量。

纹理合成的应用比较广泛。在绘制中，纹理可以用来表现物体的表面细节，因此，可以用纹理合成技术在物体表面生成丰富的纹理。电影、照片和图形中经常会出现有缺陷的地方，而缺陷一定出现在某个纹理区域，可以利用纹理合成技术来填补这块缺陷从而完成修复。描述自然场景时，通常需要包含大部分的纹理区域，这时，可以采用纹理合成技术压缩纹理。本文算法可以很好地运用到三维地形纹理贴图中，当需要对地表建模时，只需要保存部分纹理图像，通过纹理合成技术生成最终的纹理地形图。图8给出本文在三维地形贴图的一个应用实例。

图8　本文纹理合成在三维地形贴图中的应用

如实验结果中提到，纹理的类型、某些特征参数会对纹理合成效果产生不同的影响。接下来的工作中，会针对不同类型的纹理，以及不同特征参数的纹理分别进行研究，增强算法的适用性，提高纹理的合成质量。

参考文献

[1] Efros A A,Leung T K. Texture synthesis by Non-parametricSampling[C]//Proceedings of International Conference on Computer Vision. Greece：IEEE Press,1999:1033-1038.

[2] Wei L Y,Levoy M,Acm A A. Fast texture synthesis using tree-structured vector quantization[C]//Computer Graphics Annual Conference,Assoc Computing Machinery，New Orleans,La,2000:479-488.

[3] Ashikhmin M. Synthesizing natural texture[C]//ACM Symposium on Interactive 3D Graphics,NC,2001:217-226.

[4] Efros A A,Freeman W T. Image quilting for texture synthesis and transfer[C]//International Conference on Computer Graphics and Interactive Techniques,Los Angeles,CA,2001:341-346.

[5] Cohen M F,Shade J,Hiller S,et al. Wang Tiles for image and texture generation[C]//Annual Symposium of the ACM SIGGRAPH，Assoc Computing Machinery,San Diego,Ca,2003:287-294.

[6] 王继东，庞明勇，赵瑞斌.旋转的Wang Tiles纹理合成[J].中国图象图形学报，2013，18(1):49-54.

[7] Zu Yueran,Duan Huichuan.Texture synthesis using diagonal quilting Wang Tiles[C]//Computational Intelligence and Security (CIS),2013:836-840.

[8] Praun E,Finkelstein A.Hoppe H1Lapped texture[C]//Computer Graphics Proceedings,Annual Conference Series,ACM SIGGRAPH,New Orleans,Louisiana,2000: 55-64.

[9] Turk Greg.Texture synthesis on surfaces[C]//Computer Graphics Proceedings,Annual Conference Series,ACM SIGGRAPH,Los Angeles,California,USA,2001. USA: ACM,2001:347-354.

[10] Wei L Y,Levoy M. Texture synthesis over arbitrary manifold surfaces[C]//Computer Graphics Proceedings,Annual Conference Series,ACM SIGGRAPH,Los Angeles,California,USA,2001.USA:ACM,2001: 355-360.

[11] Magda S,Kriegman D.Fast texture synthesis on arbitrary meshes[C]//Proceedings of 14th Eurographics Workshop on Rendering,Leuven Belgium,USA,ACM,2003: 82-89.

[12] 汤颖,孙汉秋,张宏鑫,等.用户控制的纹理合成[J].计算机辅助设计与图形学学报,2004,16(10):1412-1418.

[13] 薛峰,张佑生,江巨浪,等.基于纹理延伸和三角块拼接的快速曲面纹理合成[J].计算机辅助设计与图形学学报,2007,29(2):221-226.

[14] Bao P,Xiaoho Ma.Texture growing on triangle mesh[C]// Signals,Circuits and Systems (ISSCS),2011 10th International Symposium on,2011:1-4.

[15] 薛峰,陆华峰,成诚,等.基于Triangle-Tiles的三维曲面实时纹理合成[J].系统仿真学报,2009,21(22):7168-7171.

[16] 聂俊岚，王艳芬.块纹理合成中尺寸自适应算法[J].计算机辅助设计与图形学学报，2008，20(10)：1353-1357.

中图分类号TP391.14

文献标识码A

DOI:10.3969/j.issn.1000-386x.2016.02.040

收稿日期：2014-09-03。国家科技支撑计划项目(2013BAH120f00)。孙劲光，教授，主研领域：图形理论与技术，图像工程，数据挖掘。刘双九，硕士生。