尺寸自適應的T-Tile三維紋理合成

孫勁光　劉雙九

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)。孫勁光，教授，主研領域：圖形理論與技術，圖像工程，數據挖掘。劉雙九，碩士生。