基于塊無縫拼接的紋理合成算法及C++程序?qū)崿F(xiàn)

解 慧

（晉中學(xué)院數(shù)學(xué)學(xué)院，山西晉中030619）

（編輯 張 瑛）

在現(xiàn)實(shí)世界中，很多物體表面圖像具有紋理的特征，在3D圖像學(xué)中，由于給定的紋理較小，既能滿足較大物體表面的紋理要求，又能體現(xiàn)物體自身的內(nèi)在紋理特征，故提出了基于樣本的紋理合成（Texture Synthesis From Sample，TSFS）技術(shù).紋理技術(shù)把紋理映射到三維模型上，可以彌補(bǔ)模型細(xì)節(jié)的不足，在基于紋理圖像的真實(shí)性上起著關(guān)鍵的作用，3DMax和Mays軟件就是此原理上實(shí)現(xiàn)的.TSFS是根據(jù)給定小樣本的紋理特征，合成大面積的紋理，并且保證合成的紋理具有連續(xù)性和相似性.TSFS既保持了紋理的特性又提高了合成速度，在現(xiàn)實(shí)中應(yīng)用范圍越來越廣.

1 二維TSFS技術(shù)

TSFS一般包括二維、三維和視頻三種紋理合成.其中二維TSFS技術(shù)的發(fā)展主要分為以下三個(gè)階段.

1.1 基于紋理特征分析與匹配的合成算法

David等人[1]采用典型的多分辨率濾波器方法，用噪聲對(duì)可控的金字塔初始化，與樣本紋理的金字塔的RGB分辨率匹配，迭代多次后實(shí)現(xiàn)紋理合成.Bonet等人[2]采用拉普拉斯金字塔對(duì)紋理進(jìn)行特征處理，按從上到下的順序搜索紋理塊，最終找到相匹配的紋理，實(shí)現(xiàn)紋理合成.Simoncel等人[3]采用統(tǒng)計(jì)方法，并在David和Bonet等人方法的基礎(chǔ)上作出改進(jìn)，在合成質(zhì)量上取得較好的結(jié)果.

1.2 基于馬爾可夫隨機(jī)場(chǎng)模型的合成算法

馬爾可夫隨機(jī)場(chǎng)模型（Markov RandomFields,MRF）根據(jù)紋理具有局部性特征，在樣本紋理的周圍附近紋理中搜索到合適的紋理，實(shí)現(xiàn)紋理的合成.Efros和Leung等人［4］采用非參數(shù)采樣算法，根據(jù)MRF對(duì)待合成的紋理進(jìn)行種子設(shè)置，從而在樣本紋理中搜索與該種子相匹配的紋理塊.徐曉剛等人[5]在文獻(xiàn)[4]方法的基礎(chǔ)上作出改進(jìn)，提出在待合成紋理中設(shè)置多個(gè)種子，提高了合成速度.Wei和Levoy等人[6]根據(jù)MRF，采用樹形矢量量化方法進(jìn)行紋理合成，從而加快了合成速度.Liang等人［7］把利用MRF模型搜索紋理塊，能夠保持良好的紋理局部性，用模糊化方法實(shí)現(xiàn)紋理塊之間的重疊部分，減少了紋理塊間邊界的誤差.

1.3 基于紋理塊拼接的紋理合成算法

Praun等人[8]利用紋理自身相似性特征進(jìn)行紋理搜索，提出適用于隨機(jī)性紋理的不規(guī)則形狀簡(jiǎn)單的覆蓋，實(shí)現(xiàn)快速紋理合成.Liu and Lin[9]提出格子點(diǎn)（Lattice）算法，采用混合的、動(dòng)態(tài)的思維來進(jìn)行塊的紋理合成.Kopf等人[10]提出基于tiling的實(shí)時(shí)紋理合成，利用少的空間進(jìn)行邊界約束，該法有利于GPU的實(shí)現(xiàn)，該法的弊端是合成紋理的種類局限較大和合成的速度慢.Efros和Freeman等人［11］利用優(yōu)化紋理的切向矢量場(chǎng)方法，提出基于塊縫合的方法，使得紋理塊邊界交叉wangtiles性.Kwatra等人［12］利用Graph-Cut方法尋找最優(yōu)路徑，并動(dòng)態(tài)地實(shí)現(xiàn)塊樣本紋理的無縫過渡.Cohen等人［13］提出了非周期tiling的隨機(jī)系統(tǒng)的wangtiles的紋理合成方法，紋理實(shí)現(xiàn)創(chuàng)建和合成共同進(jìn)行.ZhouKun等人［14］用Graph-Cut來優(yōu)化紋理塊間邊緣覆蓋，并采用新的編程模型（Compute Unified Device Architecture）實(shí)現(xiàn)并行處理，加快了合成速度.

2 基于塊無縫拼接的紋理合成算法的程序C++實(shí)現(xiàn)

基于塊無縫拼接的紋理合成算法（Seamless Tiling Texture Synthesis Algorithm，STTSA）是建立在紋理塊拼接的紋理合成算法的基礎(chǔ)上提出的，但由于該算法實(shí)現(xiàn)比較復(fù)雜，只停留在理論的層面，沒有付諸實(shí)踐.本文把這種算法用C++程序具體實(shí)現(xiàn)，使該理論的算法得到了實(shí)踐性的應(yīng)用，并通過實(shí)際程序的運(yùn)行取得了滿意的合成效果.下面對(duì)STTSA的C++程序的關(guān)鍵代碼進(jìn)行詳細(xì)介紹.

STTSA是在ImgOp.GnrtTxt（String Txt_Img_Nm）函數(shù)中實(shí)現(xiàn)的，Txt_Img_Nm表示輸入的樣本紋理名字，并把此樣本紋理的像素值存于數(shù)組Txt_Pxls中.在ImgOp.Gnr_tTxt中最關(guān)鍵的子函數(shù)是：this.Gnrt_Txt_Pxls（int Txt_Pxls[]，int Txt_Wdth，int Txt_Hght，int Sz,int Edg,int Hght，int Cnt，int X_0，int Y_0）.

Gnrt_Txt_Pxls函數(shù)作用是確定合成矩陣中每行的索引，使得已合成紋理與待合成紋理之間像素點(diǎn)的距離最小.其中，Txt_Pxls[]數(shù)組中存放輸入樣本紋理的像素值；Sz表示無縫拼接的塊樣本紋理的長(zhǎng)度；參數(shù)Edg表示用于無縫拼接的塊樣本紋理的寬度（如圖1中A表示用于無縫拼接的塊樣本紋理）.其中Sz和Edg值的初始化對(duì)紋理合成的質(zhì)量起著關(guān)鍵性的作用，Sz初始化較小導(dǎo)致不完整的紋理特征，初始化過大導(dǎo)致紋理合成不光滑.本文?。篠z=min（Txt_Wdth，Txt_Hght）/5；Edg=Sz/3；Lgth=Edg+Sz+EdgM.

為達(dá)到合成紋理的連續(xù)性，STTSA要求每行中已合成的目標(biāo)輸出紋理（如圖1中B）的右側(cè)與樣本紋理的左側(cè)無縫拼接，每列中已合成的目標(biāo)輸出紋理的下側(cè)與樣本紋理的上側(cè)無縫拼接，如圖1所示.

圖1 無縫拼接的紋理合成過程

目標(biāo)輸出紋理的首個(gè)塊樣本紋理是隨機(jī)生成的，首先實(shí)現(xiàn)從左到右第一行的無縫拼接，再實(shí)現(xiàn)從上到下第一列的無縫拼接；然后在待合成紋理中從左到右，從上到下的無縫拼接.一直循環(huán)到最終實(shí)現(xiàn)整個(gè)目標(biāo)紋理的合成.程序?qū)崿F(xiàn)如下：

for（intX_0=Sz；X_0≤Img_Wdth_Sz；X_0+=Sz）{

for（intY_0=Edg；Y_0≤Img_Hght_Edg；Y_0+=Edg）{

this.Gnrt_Txt_Pxls（int Txt_Pxls[],int Txt_Wdth,int Txt_Hght，int Sz，int Edg,int Hght，int Cnt,int X_0,int Y_0）；}}

從左到右的行和從上到下的列無縫拼接實(shí)現(xiàn)原理相似，故下面介紹行的無縫拼接的實(shí)現(xiàn)原理.在給定的樣本紋理中，首先對(duì)可取的樣本紋理進(jìn)行范圍設(shè)定：

Max_Wdth=Txt_Wdth_Sz；Max_Hght=Txt_Hght_Edg；再將已合成的目標(biāo)輸出紋理的右側(cè)紋理的像素值復(fù)制到Rght_Edg_xPls中；然后在給定可取的樣本紋理中，進(jìn)行Cnt次循環(huán)，每次隨機(jī)抽取塊樣本紋理，并把抽取的塊樣本紋理的坐標(biāo)值分別賦予x,y；

int x=（int）（max_Wdth*Math.randmo（）），int y=（int）（max_Hght*Math.randmo（））.

通過Dstc（P_1，P_2）計(jì)算目標(biāo)輸出紋理的右側(cè)紋理與已隨機(jī)抽取的塊樣本紋理的左側(cè)紋理的距離絕對(duì)值（Dis=|R_1-R_2|+|G_1-G_2|+|B_1-B_2|R，G，B分別表示紅、綠、藍(lán) 3個(gè)分量），Lft_Edg[]中存放 Dis的最小塊樣本紋理的像素點(diǎn)的值，并且把該像素值復(fù)制到目標(biāo)輸出紋理中.函數(shù)Gnrt_Txt_Pxls實(shí)現(xiàn)的具體程序如下（C++語(yǔ)言描述）：

void Gnrt_Txt_Pxls（int Txt_Pxls[]，int Txt_Wdth，int Txt_Hght，int Sz，int Edg，int Hght，int Cnt，int X_0，int Y_0）{

int Max_Wdth=Txt_Wdth_Hght；

int Max_Hght=Txt_Hght_Hght；

int Rght_Edg_Pxls[Hght*Edg]；

int Bttm_Edg_Pxls[Edg*Hght]；

int Mtch_X=0；

int Mtch_Y=0；

int Mtch_Lft_Edg[Hght]

int Mtch_Tp_Edg[Hght]；

int Min_Dst=Intgr.MAX_VALUE；

for（inti=0；i

{

for（int j=0；j

{

Rght_Edg_pxls[i*Edg+j]=Pxls[（i+Y_0）*Img_Wdth+（j+X_0）]；

}

}

for（inti=0；i

{

for（int j=0；j

{

Bttm_Edg_Pxls[i*Hght+j]=Pxls[（i+Y_0）*Img_Wdth+（j+X_0）]；}

for（int t=0；t

{

int x=（int）（Max_Wdth*Math.random（））；

int y=（int）（Max_Hght*Math.random（））；

int New_Dst=0；

int Lft_Edg[Hght]；

for（inti=0；i

{

int Min_D=Intgr.MAX_VALUE；

for（int j=0；j

{

int P_1=Txt_Pxls[（y+i）*Txt_Wdth+（x+j）]；

int P_2=Rght_Edg_Pxls[i*Edg+j]；

int d=Dstc（P_1，P_2）；

if（d

{

Min_D=d；

Lft_Edg[i]=j；

}

if（d==0）

{

break；

}

}

New_Dst+=Min_D；

}

int Tp_Edg[Hght]；

for（int j=0；j

{

int Min_D=Intgr.MAX_VALUE；

for（inti=0；i

{

int P_1=Txt_Pxls[（y+i）*Txt_Wdth+（x+j）]；

int P_2=Bttm_Edg_Pxls[i*Hght+j]；

int d=Dstc（P_1，P_2）；

if（d

{

Min_D=d；

Tp_Edg[j]=i；

}

if（d==0）

{

break；

}

New_Dst+=Min_D；}

if（New_Dst

{

Min_Dst=New_Dst

Mtch_X=x；

Mtch_Y=y；

for（inti=0；i

{

Mtch_Lft_Edg[i]=Lft_Edg[i]；}

for（int j=0；j

{

Mtch_Tp_Edg[j]=Tp_Edg[j]；}

}

}

for（inti=0；i

{

if（Y_0+i>Img_Hght）

{

break;

}

for（int j=Mtch_Lft_Edg[i]；j

if（X_0+j>Img_Wdth）

{

break；

}

if（i>=Mtch_Tp_Edg[j]）

{this.Pxls[（Y_0+i）*Img_Wdth+（X_0+j）]=Txt_Pxls[（Mtch_Y+i）*Txt_Wdth+（Mtch_X+j）；

}}}}

3 實(shí)驗(yàn)結(jié)果及其分析

在VC2009中運(yùn)行上述程序，對(duì)4個(gè)樣本紋理進(jìn)行STTSA.其中，Texture1，Texture2，Texture3，Texture 4分別對(duì)應(yīng)的合成結(jié)果為Texture5，Texture6，Texture7，Texture8.從4個(gè)樣本紋理的合成效果看，都達(dá)到不錯(cuò)的合成效果.

圖1 Texture1

圖2 Texture2

圖3 Texture3

圖4 Texture4

圖5 Texture5

圖6 Texture6

圖7 Texture7

圖8 Texture8

4 結(jié)束語(yǔ)

從合成效果看，用C++程序?qū)崿F(xiàn)的STTSA，可以較好地實(shí)現(xiàn)紋理合成.本文把理論化的STTSA用具體的C++程序來實(shí)現(xiàn)，實(shí)驗(yàn)證明該程序代碼的編寫是合理的，并且通過多次的測(cè)試達(dá)到穩(wěn)定的合成結(jié)果，且運(yùn)行上述程序可在2~3s內(nèi)輸出合成結(jié)果，合成速度快.但是此程序算法是對(duì)相鄰兩個(gè)樣本紋理的無縫拼接，沒有進(jìn)行重疊羽化合成，故需要進(jìn)一步的程序改進(jìn)和測(cè)試，去掉隱藏的bug，使程序能夠更快速更穩(wěn)定.

［1］David J，Heeger，Bergen.Pyramid-Based textureanalysis/synthesis［J］.Proceedingsof SIGGRAPH，2005，4（3）：229～238．

［2］Bonet，Jeremy S.Multiresolution sampling procedure for analysis and synthesis of texture［J］.Proceedings of SIGGRAPH，2004，8（2）：361～368.

［3］Simoncelli EP.Texture characterization via joint statistics of wavelet coefficient magnitudes［J］.Fifth International Conference on Image Processing，2008，6（10）：1～62.

［4］Efros A，Leung Thomas K.Texture synthesis by non-parametric sampling［J］.International Conference on Computer Vision，2005，8（2）：1033～1038.

［5］徐曉剛，于金輝，馬利莊.多種子快速紋理合成［J］.中國(guó)圖象圖形學(xué)報(bào)，2002，7（10）：994～999．

［6］Wei LiYj，Marc Levoy.Fast texturesynthesis usingtree-structured vector quantization［J］.Proceedingsof SIGGRAPH，2010，6（12）：479～488.

［7］Liang L，Liu C，Shum.Real-time texture synthesis by patch-based sampling［J］.ACM Transactions on Graphics，2011，20（3）：127~150.

［8］Praun E,Finkelstein A.Lapped textures［J］.Proceedingsof SIGGRAPH，2007，12（4）：465～470．

［9］Liu Y，Lin WC.Deformable texture：the irregular-regular-irregular cycle［J］.Proceedings of the 3rd International Workshop on Texture Analysisand Synthesis，2003，10（4）：65~70.

［10］Kopf，Cohen，Lischinski.Recursivewangtiles for real-timebluenoise［J］.ACMTransactionson Graphics，2006，25（3）：509~518.

［11］Efros A，F(xiàn)reeman W.Imagequiltingfor texturesynthesisand transfe［r J］.Proceedings of ACMSIGGRAPH，2005，21（7）：341~346.

［12］Kwatra，Schodl A.Graph-cut textures：image and video synthesis using graph cuts［J］.ACM Transactions on Graphics，2008，22（3）：277～286.

［13］Cohen M，Essa.Wangtiles for imageand texturegeneration［J］.ACMTransactions on Graphics，2009，22（3）：287~294.

［14］Kun Zou，Xiang Xu.Graph-cut based fast texture synthesis with CUDA［J］.Computer Design and Applications，2010，14（8），251~270.