基于块无缝拼接的纹理合成算法及C++程序实现
2015-04-01解慧
解 慧
(晋中学院数学学院,山西晋中030619)
(编辑 张 瑛)
在现实世界中,很多物体表面图像具有纹理的特征,在3D图像学中,由于给定的纹理较小,既能满足较大物体表面的纹理要求,又能体现物体自身的内在纹理特征,故提出了基于样本的纹理合成(Texture Synthesis From Sample,TSFS)技术.纹理技术把纹理映射到三维模型上,可以弥补模型细节的不足,在基于纹理图像的真实性上起着关键的作用,3DMax和Mays软件就是此原理上实现的.TSFS是根据给定小样本的纹理特征,合成大面积的纹理,并且保证合成的纹理具有连续性和相似性.TSFS既保持了纹理的特性又提高了合成速度,在现实中应用范围越来越广.
1 二维TSFS技术
TSFS一般包括二维、三维和视频三种纹理合成.其中二维TSFS技术的发展主要分为以下三个阶段.
1.1 基于纹理特征分析与匹配的合成算法
David等人[1]采用典型的多分辨率滤波器方法,用噪声对可控的金字塔初始化,与样本纹理的金字塔的RGB分辨率匹配,迭代多次后实现纹理合成.Bonet等人[2]采用拉普拉斯金字塔对纹理进行特征处理,按从上到下的顺序搜索纹理块,最终找到相匹配的纹理,实现纹理合成.Simoncel等人[3]采用统计方法,并在David和Bonet等人方法的基础上作出改进,在合成质量上取得较好的结果.
1.2 基于马尔可夫随机场模型的合成算法
马尔可夫随机场模型(Markov RandomFields,MRF)根据纹理具有局部性特征,在样本纹理的周围附近纹理中搜索到合适的纹理,实现纹理的合成.Efros和Leung等人[4]采用非参数采样算法,根据MRF对待合成的纹理进行种子设置,从而在样本纹理中搜索与该种子相匹配的纹理块.徐晓刚等人[5]在文献[4]方法的基础上作出改进,提出在待合成纹理中设置多个种子,提高了合成速度.Wei和Levoy等人[6]根据MRF,采用树形矢量量化方法进行纹理合成,从而加快了合成速度.Liang等人[7]把利用MRF模型搜索纹理块,能够保持良好的纹理局部性,用模糊化方法实现纹理块之间的重叠部分,减少了纹理块间边界的误差.
1.3 基于纹理块拼接的纹理合成算法
Praun等人[8]利用纹理自身相似性特征进行纹理搜索,提出适用于随机性纹理的不规则形状简单的覆盖,实现快速纹理合成.Liu and Lin[9]提出格子点(Lattice)算法,采用混合的、动态的思维来进行块的纹理合成.Kopf等人[10]提出基于tiling的实时纹理合成,利用少的空间进行边界约束,该法有利于GPU的实现,该法的弊端是合成纹理的种类局限较大和合成的速度慢.Efros和Freeman等人[11]利用优化纹理的切向矢量场方法,提出基于块缝合的方法,使得纹理块边界交叉wangtiles性.Kwatra等人[12]利用Graph-Cut方法寻找最优路径,并动态地实现块样本纹理的无缝过渡.Cohen等人[13]提出了非周期tiling的随机系统的wangtiles的纹理合成方法,纹理实现创建和合成共同进行.ZhouKun等人[14]用Graph-Cut来优化纹理块间边缘覆盖,并采用新的编程模型(Compute Unified Device Architecture)实现并行处理,加快了合成速度.
2 基于块无缝拼接的纹理合成算法的程序C++实现
基于块无缝拼接的纹理合成算法(Seamless Tiling Texture Synthesis Algorithm,STTSA)是建立在纹理块拼接的纹理合成算法的基础上提出的,但由于该算法实现比较复杂,只停留在理论的层面,没有付诸实践.本文把这种算法用C++程序具体实现,使该理论的算法得到了实践性的应用,并通过实际程序的运行取得了满意的合成效果.下面对STTSA的C++程序的关键代码进行详细介绍.
STTSA是在ImgOp.GnrtTxt(String Txt_Img_Nm)函数中实现的,Txt_Img_Nm表示输入的样本纹理名字,并把此样本纹理的像素值存于数组Txt_Pxls中.在ImgOp.Gnr_tTxt中最关键的子函数是: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函数作用是确定合成矩阵中每行的索引,使得已合成纹理与待合成纹理之间像素点的距离最小.其中,Txt_Pxls[]数组中存放输入样本纹理的像素值;Sz表示无缝拼接的块样本纹理的长度;参数Edg表示用于无缝拼接的块样本纹理的宽度(如图1中A表示用于无缝拼接的块样本纹理).其中Sz和Edg值的初始化对纹理合成的质量起着关键性的作用,Sz初始化较小导致不完整的纹理特征,初始化过大导致纹理合成不光滑.本文取:Sz=min(Txt_Wdth,Txt_Hght)/5;Edg=Sz/3;Lgth=Edg+Sz+EdgM.
为达到合成纹理的连续性,STTSA要求每行中已合成的目标输出纹理(如图1中B)的右侧与样本纹理的左侧无缝拼接,每列中已合成的目标输出纹理的下侧与样本纹理的上侧无缝拼接,如图1所示.
图1 无缝拼接的纹理合成过程
目标输出纹理的首个块样本纹理是随机生成的,首先实现从左到右第一行的无缝拼接,再实现从上到下第一列的无缝拼接;然后在待合成纹理中从左到右,从上到下的无缝拼接.一直循环到最终实现整个目标纹理的合成.程序实现如下:
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);}}
从左到右的行和从上到下的列无缝拼接实现原理相似,故下面介绍行的无缝拼接的实现原理.在给定的样本纹理中,首先对可取的样本纹理进行范围设定:
Max_Wdth=Txt_Wdth_Sz;Max_Hght=Txt_Hght_Edg;再将已合成的目标输出纹理的右侧纹理的像素值复制到Rght_Edg_xPls中;然后在给定可取的样本纹理中,进行Cnt次循环,每次随机抽取块样本纹理,并把抽取的块样本纹理的坐标值分别赋予x,y;
int x=(int)(max_Wdth*Math.randmo()),int y=(int)(max_Hght*Math.randmo()).
通过Dstc(P_1,P_2)计算目标输出纹理的右侧纹理与已随机抽取的块样本纹理的左侧纹理的距离绝对值(Dis=|R_1-R_2|+|G_1-G_2|+|B_1-B_2|R,G,B分别表示红、绿、蓝 3个分量),Lft_Edg[]中存放 Dis的最小块样本纹理的像素点的值,并且把该像素值复制到目标输出纹理中.函数Gnrt_Txt_Pxls实现的具体程序如下(C++语言描述):
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); }}}} 在VC2009中运行上述程序,对4个样本纹理进行STTSA.其中,Texture1,Texture2,Texture3,Texture 4分别对应的合成结果为Texture5,Texture6,Texture7,Texture8.从4个样本纹理的合成效果看,都达到不错的合成效果. 图1 Texture1 图2 Texture2 图3 Texture3 图4 Texture4 图5 Texture5 图6 Texture6 图7 Texture7 图8 Texture8 从合成效果看,用C++程序实现的STTSA,可以较好地实现纹理合成.本文把理论化的STTSA用具体的C++程序来实现,实验证明该程序代码的编写是合理的,并且通过多次的测试达到稳定的合成结果,且运行上述程序可在2~3s内输出合成结果,合成速度快.但是此程序算法是对相邻两个样本纹理的无缝拼接,没有进行重叠羽化合成,故需要进一步的程序改进和测试,去掉隐藏的bug,使程序能够更快速更稳定. [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].中国图象图形学报,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,Freeman 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.3 实验结果及其分析
4 结束语