（计算机软件与理论专业论文）基于模拟退火算法的wangtile纹理合成优化技术.pdf

i l l 一 原创性声明和关于论文使用授权的说明 原创性声明 本人郑重声明：所呈交的学位论文，是本人在导师的指导下，独 立进行研究所取得的成果。除文中已经注明引用的内容外，本论文不 包含任何其他个人或集体已经发表或撰写过的科研成果。对本文的研 究做出重要贡献的个人和集体，均已在文中以明确方式标明。本声明 的法律责任由本人承担。 论文作者签名：啦 日期：- j 狂竺丛 关于学位论文使用授权的声明 本人完全了解山东大学有关保留、使用学位论文的规定，同意学 校保留或向国家有关部门或机构送交论文的复印件和电子版，允许论 文被查阅和借阅；本人授权山东大学可以将本学位论文的全部或部分 内容编入有关数据库进行检索，可以采用影印、缩印或其他复制手段 保存论文和汇编本学位论文。 ( 保密论文在解密后应遵守此规定) 糍：烨翩躲盈日 期：兰堕t - 签 ， 山东大学硕士学位论文 目录 摘要i a b s t r a c t 一 第一章绪论1 1 1研究背景1 1 2 研究内容2 1 3 论文结构3 第二章纹理合成技术4 2 1 纹理合成分类4 2 2 纹理合成技术5 2 2 1 点匹配算法5 2 2 2 块匹配算法8 第三章w a n g - t i l e 纹理合成算法的改进及分析1 3 3 1 基于小波变换的纹理合成1 3 3 1 1 小波变换技术1 3 3 1 2 基于小波变换的纹理合成算法15 3 2 基于模拟退火的w a n g t i l e 纹理合成1 8 3 2 1 模拟退火算法1 9 3 2 2 基于模拟退火的t i l e 集的选择优化算法2 0 第四章基于模拟退火的w a n g t i l e 纹理合成优化算法2 3 4 1 算法思路及实现2 3 4 2 实验结果及分析2 5 第五章总结与展望3 1 参考文献3 2 致谢3 4 攻读学位期间发表的学术论文3 5 山东大学硕士学位论文 c o n t e n t s a b s t r a c ti nc h i n e s e i a b s t r a c ti ne n g l i s h ： c h a p t e r o n ei n t r o d u c t i o n - 1 - 1 1r e s e a r c hb a c k g r o u n d 1 1 2r e s e a r c hc o n t e n t s 一2 1 3 s t r u c t u r eo f e s s a y - 3 - c h a p t e r t w ot e x t u r es y n t h e s i st e c h n o l o g y - 4 - 2 1c l a s s i f i c a t i o no f t e x t u r es y n t h e s i s _ 4 - 2 2t e x t u r es y n t h e s i st e c h n o l o g y - 5 - 2 2 1d o t sm a t c ha l g o r i t h m - 5 _ 2 2 2b l o c k sm a t c ha l g o r i t h m - 8 一 c h a p t e r t h r e et h ei m p r o v e m e n ta n da n a l y s i so fw a n g - t i l et e x t u r es y n t h e s i sa l g o r i t h m 13 - 3 1t e x t u r es y n t h e s i sb a s e do nw a v e l e tt r a n s f o i t s 一1 3 - 3 i 1w a v e l e tt r a n s f o r mt e c h n o l o g y 一- 1 3 3 1 2t e x t u r es y n t h e s i sa l g o r i t h mb a s e do nw a v e l e tt r a n s f o r m - 15 - 3 2 w a n g - t i l et e x t u r es y n t h e s i sb a s e do ns i m u l a t e da n n e a l i n g - 1 8 - 3 2 1s i m u l a t e da n n e a l i n ga l g o r i t h m 一1 9 3 2 2s e l e c t i v eo p t i m i z a t i o na l g o r i t h mo ft h et i l ec o l l e c t i o nb a s e do n s i m u l a t e da n n e a l i n g - 2 0 c h a p t e rf o u ro p t i m i z a t i o na l g o r i t h mo fw a n g t i l et e x t u r es y n t h e s i sb a s e do n s i m u l a t e da n n e a l i n g 一- 2 3 。 4 1 a l g o r i t h m t h i n k i n ga n di t sr e a l i z a t i o n - 2 3 _ 4 2 e x p e r i m e n t a lr e s u l t sa n da n a l y s i s 2 5 一 c h a p t e r f i v e s u m m a r ya n dp r o s p e c t s - 3 l - l i t e r a t u r ec i t e d 一3 2 一 e x p r e s s i o no f t h a n k s 一3 4 - t h et h e s i sp u b l i s h e dd u r i n gp o s t g r a d u a t es t u d y 3 5 。 图的纹理合成技术是近几年迅速发展起来的一种新的纹理拼接技术。 c o h e n 等人于2 0 0 3 年提出了一种w a n g t i l e 纹理合成算法。该算法引入了 计算理论中的“w a n gt i l e ”理论，由于其是利用合成的一组w a n gt i l e 来进行一 系列简单的拼接，从而产生了非周期性纹理。首先从输入纹理中任意选择多块菱 形样本纹理，并赋予不同颜色，按照一定的规则对样本纹理进行排列，采用 q u i l t i n g 方法对重叠区域进行合成，并剪切合成后的中心矩形部分得到t i l e 集， 最后根据t i l e 块的边缘颜色匹配进行纹理拼贴。因此，t i l e 集的质量直接决定了 最终生成的合成纹理的质量，而要保证t i l e 集的质量，要求所选择的样本纹理在 合成时的综合误差路径值满足一定的阈值，但是这个阈值是很难确定的，使得算 法效率不高。另外即使综合误差路径值很小，也不能保证所选择的样本纹理是全 局最优的，使得算法在合成某些具有精细纹理特征和鲜明颜色对比的纹理时会产 生明显的菱形接缝。如何避免或减少w a n g t i l e 方法中菱形接缝一直是人们在不 断研究的问题，这对提高纹理合成的质量具有重要意义。 本文提出了一种基于模拟退火的w a n g t i l e 纹理合成算法，本算法结合模拟 退火算法和小波变换技术从效率和效果两个方面对w a n g t i l e 纹理合成算法进行 了改进。首先利用模拟退火算法收敛于全局最优解的特点，在选择生成t i l e 集的 样本时进行优化选择，得到近似最优的t i l e 集，也就是可以得到最佳合成效果的 t i l e 集合，解决了w a n g t i l e 算法出现的菱形接缝的问题，实验证明可以得到很 好的合成效果。其次，为了提高算法的效率，本算法在样本集的选择之前首先对 初始样本进行二维小波分解，只在分解后的低频部分进行最佳匹配块的搜索，样 本图像在分解后的只有原来1 4 大小，也就是实现了纹理的压缩。因此，在选择 匹配块时可以大大减少搜索时间，从而提高了算法效率。实验结果证明了本算法 的有效性。 关键词：纹理合成；模拟退火算法：小波变换；图像处理 山东大学硕士学位论文 a b s t r a c t t e x t u r es y n t h e s i si st h er e s e a r c hh i g h l i g h ti nm a n yf i e l d ss u c ha sc o m p u t e r v i s i o n ，c o m p u t e rg r a p h i c s ，i m a g ep r o c e s s i n ga n ds oo n r e c e n t l yt e x t u r es y n t h e s i si s m a i n l yd i v i d e di n t op r o c e d u r a lt e x t u r es y n t h e s i s ，it sa n dt e x t u r es y n t h e s i sf r o m s a m p l e s ，t s f s t s f si san e wm e r g i n gt e c h n o l o g yo ft e x t u r et h a ti sd e v e l o p i n g r a p i d l yt h e s ey e a r s c o h e na n do t h e rp e o p l ec o m eu pw i t hab l o c ks y n t h e s i sa l g o r i t h m ，t h i sa l g o r i t h m i n t r o d u c e dac o m p u t e rt h e o r yc a l l e d “w a n gt i l et h e o r y ”a si tu s e sag r o u po f s y n t h e s i sw a n gt i l et oc a r r yo u tas e r i e so fe a s ys p l i c e ，a p e r i o d i ct e x t u r ei sp r o d u c e d f i r s t ，c h o o s em u l t i d i a m o n ds a m p l e sf r o mt h ea f f e r e n tt e x t u r e sa n dg i v et h e m d i f f e r e n tc o l o r s ，t h e na r r a n g et h e s et e x t u r e sa c c o r d i n gt oc e r t a i nr u l e s ，a n dt h e n s y n t h e s i z et h eo v e r l a pr e g i o nu s i n gq u i l t i n gm e t h o da n dg e tt h et i l ec o l l e c t i o nb y c u t t i n ga n ds y n t h e s i z i n gt h eb e h i n dc e n t r a lr e c t a n g l e a tl a s t ，c a r r yo u tt h et e x t u r e s p l i c ea c c o r d i n gt ot h ee d g ec o l o rm a t c h i n go ft h et i l eb l o c k t h eq u a l i t yo ft i l e c o l l e c t i o nd i r e c t l yd e c i d e st h eq u a l i t yo ft h es y n t h e s i z e dt e x t u r et h a tw a sc r e a t e d t o g u a r a n t e et h eq u a l i t yo f t i l ec o l l e c t i o n ，t h ep a t hv a l u eo fr e s u l t a n te r r o r st ot h es a m p l e t e x t u r ec h o s e ns h o u l db eu n d e rc e r t a i nt h r e s h o l dv a l u e ，b u tt h et h r e s h o l dv a l u ei sh a r d t ob es u r e ，w h i c hm a k et h ea l g o r i t h mt ob ei n e f f i c i e n t i na d d i t i o n ，e v e ni ft h ep a t h v a l u eo fr e s u l t a n te r r o r si ss m a l l ，t h es a m p l et e x t u r ec h o s e nc a nn o tb eg u a r a n t e e dt o b et h eg l o b a lo p t i m u m , s ot h eq u a l i t yo ft h et e x t u r es y n t h e s i si sn o th i g h ，t h ee v i d e n t d i a m o n ds e a mo f t e no c c u r p e o p l eh a v eb e e nr e s e a r c h i n go nt h ep r o b l e m so fh o wt o a v o i do rr e d u c et h ed i a m o n ds e a mi nw a n gt i l em e t h o d ，a n dt h i si si m p o r t a n tt o i m p r o v et h eq u a l i t yo ft h et e x t u r es y n t h e s i s t h ep a p e rp r e s e n t saw a n g - t i l et e x t u r es y n t h e s i sa l g o r i t h mb a s e do ns i m u l a t e d a n n e a l i n ga l g o r i t h m ，t h ea l g o r i t h mc o m b i n e st h ew a v e l e tt r a n s f o r mt e c h n o l o g ya n d s i m u l a t e d a n n e a l i n ga l g o r i t h m a n di m p r o v e st h e w a n g t i l e t e x t u r e s y n t h e s i s a l g o r i t h mi ne f f i c i e n c ya n de f f e c t s f i r s t ，w et a k ea d v a n t a g eo ft h es i m u l a t e d a n n e a l i n ga l g o r i t h mt oo p t i m a lt h es e l e c t i o no ft i l es e t ，t h i sa l g o r i t h m , w h o s e e 山东大学硕士学位论文 p r o b a b i l i t yi so n e ，i sag l o b a lo p t i m u ma l g o r i t h mw i t hi t ss o l u t i o nt e n d i n gt ob et h e g l o b a lo p t i m u m a n dg e tt h eb e s tr e s u l t t h ed i a m o n d s e a m sp r o b l e mo fw a n g t i l e t e x t u r es y n t h e s i sa l g o r i t h mh a sb e e ns o l v e d e x p e r i m e n t sg e tp e r f e c ts y n t h e s i sr e s u l t s o nt h eo t h e rh a n d ，t h ea l g o r i t h mm a k e st h et w o - d i m e n s i o n a lw a v e l e td e c o m p o s i t i o n o ni m a g e ，a n dt h e ns e a r c hf o rt h eb e s tm a t c h i n gb l o c ki nt h el o wf r e q u e n c yp a r ta f t e r t h ed e c o m p o s i t i o n ，w h i c hc a l lg r e a t l yc u tt h es e a r c h i n gt i m e e x p e r i m e n t sp r o v et h e e f f e c t so ft h ea l g o r i t h m k e yw o r d s ：t e x t u r es y n t h e s i 8 。8 i m u i a t e d a n n e a li n ga i g o r i t h m 。 w a v eie tt r a n s f o r m ， im a g ep r o o e s sin g i i i e ， 纹理、混合性纹理。结构性纹理中存在纹元( 保持纹理局部特性的最小纹理块) ， 视觉上有明显规则的最小结构区域存在，整个纹理可以由一系列的纹元及其摆放 规则决定( 如砖墙、地板) 。随机性纹理在视觉上没有明显的结构区域存在，找不 到明确的纹元，无规律可循，分布与图像位置无关( 如沙粒、裂痕、大理石) 。更 多的从现实世界得到的纹理同时包含了以上两种特性，视觉上可以分辨出有不规 则形状的结构区域存在，但结构区域大小不一，且分布不均。 愚翻黑l 醋瓣鲷 鬃黼骥l 睡黼翱 i 黼鳓l 图1 1 三种不同的纹理 有关纹理的研究是为了满足日益增长的虚拟现实应用的需要。其中纹理映射 ( t e x t u r em a p p i n g ) 是绘制复杂场景真实感图形最为常用的技术，它可以通过纹理 表达表面丰富的几何细节和光照细节，甚至可以通过映射后纹理的变形来表达物 体的几何形状。但纹理映射只能在纹理空间和表面参数空间内进行一对一的映 射。由于采样区域的局限性，所获取的纹理样本通常为小块纹理，若将小块纹理 映射到大的曲面上，势必造成映射后表面纹理模糊不清，而采取重复映射技术， 则表现出表面纹理接缝走样等问题。如图1 - 2 ( b ) 所示。 山东大学硕士学位论文 纹理合成是为了解决纹理映射中存在的接缝走样等问题而提出的，目前纹理 合成主要有过程纹理合成和基于样图的纹理合成，其中过程纹理合成( p r o c e d u r a l t e x t u r es y n t h e s i s ，盯s ) 通过对物理生成过程的仿真直接在曲面上生成纹理，如 毛发、云雾、木纹等，从而避免了纹理映射带来的失真。这种方法可以获得非常 逼真的纹理，缺点在于对每一种新的纹理都需要调整参数反复测试，非常不便， 有的甚至无法得到有效的参数。 基于样图的纹理合成( t e x t u r es y n t h e s i sf r o ms a m p l e s ，t s f s ) 技术是近几 年迅速发展起来的一种新的纹理拼接技术，它基于给定的小区域纹理样本，按照 表面的几何形状，拼合生成整个曲面的纹理，它在视觉上是相似而连续的( 如图 1 - 2 ( c ) 所示) 。t s f s 技术可以克服传统纹理映射方法的缺点，又避免了过程纹理 合成调整参数的繁琐，因而受到越来越多研究人员的关注，成为计算机图形学、 计算机视觉和图像处理领域的研究热点之一。利用t s f s 技术还可以进行纹理填 充( 如修补破损的图片，重现原有图片效果) ，纹理传输，扩展到时域则可以用 一短段视频图像，生成任意长度的非重复的视频动画等。所以纹理合成技术在图 像编辑、数据压缩、网络数据的快速传输、大规模场景的生成以及真实感和非真 实感绘制等方面具有广泛的应用前景。 ( a ) 输入纹理样本( b ) 重复纹理映射( c ) 二维纹理合成 图1 2 二维纹理映射与合成 1 2 研究内容 本论文以二维纹理合成为技术目标，系统研究了各种纹理合成算法和改善算 法，并且在此基础上，结合小波技术和模拟退火算法，针对w a n g - t i l e 纹理合成 过程中由于样本块的选择而导致的最后t i l e 集质量不高，容易出现菱形纹理接缝 的问题，提出了一种基于模拟退火算法的纹理合成优化算法。通过实验证明了本 - 2 - 山东大学硕士学位论文 论文提出的基于模拟退火算法的w a n g t i l e 纹理合成优化算法能够较好的满足二 维纹理合成的要求。 1 3 论文结构 论文在结构上共分五章。 第一章绪论，简要介绍了研究背景、研究意义及论文的主要研究内容。 第二章纹理合成技术，二维纹理合成技术是非常基本的工具，在纹理合成 和编辑中占有非常重要的地位，本章着重介绍了在二维纹理合成方面的发展历程 以及相关的成就及不足。 第三章w a n g - t i l e 纹理合成算法的改进及分析，提出了对w a n g - t i l e 纹理合 成算法改进的两种算法，基于小波变换的纹理合成算法和基于模拟退火的t i l e 集的选择优化算法，并介绍了涉及的相关技术小波技术和模拟退火算法的含义、 原理。这两种算法从效率和效果两个方面展开。效率上，通过小波变换后低频图 像的小波系数拟合，使全局搜索时的样图缩小为原样图的1 4 ，从而很大程度上 缩短了搜索时间，提高了合成速度；效果上，将模拟退火算法应用到样本纹理的 选择过程中，从而得到近似全局最优的t i l e 集，全局最优是指能得到最好的合成 效果，合成质量比任意选择样本有了很大的提高。 第四章基于模拟退火算法的w a n g t i l e 优化技术，将第三章的两种算法进 行结合，同时来提高纹理合成的速度和合成效果。详细介绍小波技术和模拟退火 算法结合实现w a n g t i l e 纹理合成优化的具体实现步骤。并同时给出了纹理合成 过程中使用的实验数据，证实本文提出的纹理合成算法的有效性，并给出纹理合 成结果。经过实验，列举利用本文优化算法进行纹理合成的效果。 第五章总结与展望，对本文所做工作作了总结，提出本文的创新之处及存 在的问题，同时分析问题原因，指出进一步的研究方向。 山东大学硕士学位论文 第二章纹理合成技术 纹理合成就是根据给出的小块样本纹理生成大块纹理的技术，且大块的纹理 跟给出的小块纹理看起来是一致的，仿佛小块样本是从合成的大块纹理上截取下 来的。纹理合成是为了解决纹理映射中存在的接缝变形以及纹理的获取等问题而 提出的，它在图像编辑、数据压缩、大规模场景的绘制、真实感和非真实感绘制 等方面都有重要的应用价值，一直受到计算机图形学、计算机视觉和图像处理领 域的广泛关注。纹理合成技术是对样本纹理的重建和再组织，纹理合成产生了与 输入纹理“相像”的纹理。 2 1 纹理合成分类 目前，纹理合成可分为过程纹理合成和基于样图的纹理合成两类方法。过程 纹理合成法将纹理的生长过程表达为数学公式或一个迭代运算的过程，根据与纹 理有关的某一特定的参数模型，使用数个给定的参数来生成各样的纹理，可以模 拟出木纹、云雾、大理石以及动物身上的斑纹等多种自然纹理，从而避免了纹理 映射带来的失真。这种方法可以获得非常逼真的纹理【卜9 1 。h e e g e r 和b e r g e n 使用 频域色彩直方图作为纹理的描述数据进行纹理合成；p o r t i l l a 和s i m o n e e l l i 研究的模型则包含许多小波特征和它们之间的关系【1 1 1 ，成为过程纹理合成模型中 最好的。这种方法虽然可以获得良好的合成效果，但对每一种新纹理都需要调整 参数反复测试，非常不方便，而且自然界中的大多数纹理是无法用过程的方式表 达出来的。 基于样图的纹理合成( t e x t u r es y n t h e s i sf r o ms a m p l e s ，t s f s ) 技术是近几年 迅速发展起来的一种新的纹理拼接技术，它基于给定的小区域纹理样本，按照表 面的几何形状，拼合生成整个曲面的纹理，它在视觉上是相似而连续的( 如图 1 - 2 ( c ) 所示) 。t s f s 技术可以克服传统纹理映射方法的缺点，又避免了过程纹理 合成调整参数的繁琐，因而受到越来越多研究人员的关注，成为计算机图形学、 计算机视觉和图像处理领域的研究热点之一【1 2 - 1 9 。利用t s f s 技术还可以进行纹 理填充( 如修补破损的图片，重现原有图片效果) ，纹理传输，扩展到时域则可 以用一短段视频图像，生成任意长度的非重复的视频动画等。所以纹理合成技术 在图像编辑、数据压缩、网络数据的快速传输、大规模场景的生成以及真实感和 山东大学硕士学位论文 非真实感绘制等方面具有广泛的应用前景。 t s f s 纹理合成技术与纹理无关，通用性比较好，可以从- d , 块样本纹理产 生出任意大小的合成纹理，而合成纹理与样本纹理看起来好像是用同一规则产生 出来的。最早的研究是d e b o n e t 早在1 9 9 7 年提出的多样本纹理模型使用多路定 标器进行纹理合成，开创了无参数纹理合成的先河【2 们。 近年来，二维纹理合成技术得到了迅速发展，它基于给定的小区域纹理样本， 按照表面的几何形状，生成大范围的纹理，它在视觉上是相似而连续的。其中基 于样图的纹理合成技术避免了过程纹理合成调整参数的繁琐，而且速度更快，适 用的范围更广，已成为计算机图形学、计算机视觉和图像处理领域的研究热点之 2 2 纹理合成技术 基于样本的纹理合成技术是基于马尔可夫随机场( m a r k o vr a n d o mf i e l d ， 腿f ) 模型的，能够适应大多数的纹理合成，也为纹理分析提供了一定的信息。 对于大多数的纹理，m r y 模型是一种很好的逼进模型，许多算法都基于这一模 型，取得较好的结果。m r f 模型认为纹理具有局部统计特征，对一张纹理图， 任取其中两小块都是相似的。另外一些算法把纹理当作一种特征集，通过样本图 中匹配特征的方法生成新的纹理图。 基于马尔可夫随机场模型0 v m a ：) 的方法最多，其主要分为“点匹配”和“块 匹配”两大类。 2 2 1 点匹配算法 即一次合成一个像素点。邻域匹配算法是点匹配算法中最为突出的代表。这 种算法最早由e f r o s 等人于1 9 9 9 年提出2 1 1 ，此后的许多算法是在此基础上改进 的。e f r o s 等人提出的非参数化模型的主要思想是对于每一个将要合成的像素， 都是在输入图像的“相似邻域”中确定像素值。对于输出图像中待合成的点，则 是通过比对该点的邻域和输入图像中所有点的邻域来查找匹配点，并将查找到的 与合成点邻域最“匹配”的点作为该点的值。 e f r o s 的合成方法用一幅已知的小块纹理图像，我们称之为“采样纹理”，合 成一幅与采样纹理致的新纹理，我们称这个新纹理为“待合成纹理”。e f r o s 的 基于点的二维纹理合成算法是一种“生长”式合成方法，即在最初的时候从采样 山东大学硕士学位论文 纹理中取出一小片拷贝到待合成纹理中，作为种子，然后在待合成纹理图片的种 子周围一个像素一个像素的进行合成，原始的种子片即进行了“生长。当种子 生长到填满了整个待合成纹理图像的时候，合成工作即告完成。如图2 1 所示。 ( a ) 采样纹理( b ) 待合成纹理图 图2 - 1e f r o s 的点合成示意图( 图来自文献【2 l 】) e f r o s 点合成结果如图2 2 所示。 囡 ( a )( b )( c )( d ) 图2 - 2e f o r s 点合成( 图来自文献【2 l 】) ，( a ) 、( c ) 为采样纹理，( b ) 、( d ) 为合成纹理。 e f r o s 等人提出的算法不仅能够很好地保持图像局部信息的完整性，且对于 大多数纹理都能取得比较好的合成结果。e f r o s 提出的算法( 以下简称e f r o s 算法) 可以说是现代纹理合成技术的一个里程碑。但是，该算法也存在一些缺陷，主要 包括：( 1 ) 像素合成依赖于邻域匹配，当时并未涉及约束合成，而从后续的一些 基于此算法的改进算法来看，约束的实施往往是在局部细节部分进行；( 2 ) 在产 生了几个错误的合成结果后，还有可能因为比对邻域的错误而一直错下去；( 3 ) 每写一个点都需要在样图中从头到尾地匹配一遍，所以该算法的缺点就是非常耗 时；( 4 ) 对于有较大纹理结构的图像的合成，由于需要使用更大的邻域来保证最 后的合成效果，因而使得计算的开销呈几何级增长。很多人都在此基础上做出了 进一步的改进。 2 0 0 0 年w e i 和l e v o y 等人将e f r o s 算法扩展到频域，并且使用量子向量来 尽搜索策略，但由于采用了数据压缩中的t s v q 算法，因此将合成速度提升了两 个数量级。 2 0 0 1 年，a s h i k h m i n 提出的邻域限定合成算法【2 3 1 放弃了穷尽搜索，根据图 像的局部相关性，将搜索范围由穷尽搜索减少为只对待合成像素邻域的点所对应 相同偏移的像素进行搜索。相对于w e i 等人提出的算法，a s h i k h m i n 提出的算法 非常直观、简单，在进行邻域匹配时仅对这些点进行计算，从而大大减少了运算 量，运算速度几乎提高了一个数量级。试验表明，它对绝大多数的自然纹理合成 都能取得了很好的效果。但是，相对于w e i 等人提出的算法倾向于模糊化目标纹 理来说，a s h i k h m i n 提出的算法正好相反，它是将目标纹理粗糙化，致使该算法 通用性不强，对于水波、云彩等“无结构”的纹理，其合成结果往往较差。 z e l i n k a 等人通过将纹理合成分为分析和合成两个步骤，实现了“实时”的 纹理合成【2 4 1 。该算法借鉴了a s h i k h m i n 提出的算法的思想，其关键改进表现在候 选点是根据分析过程中的“跳跃图”得到的。在分析阶段，先利用邻域匹配算法 得到输入图像中每个点的“跳跃图”，即同该点有相似邻域的其他点及其选择概 率：然后在合成输出图像像素点时，将“跳跃图”作为主要的依据。z e l i n k a 等人 提出的这个算法在合成阶段的速度是非常快的，基本达到了实时的要求。但是由 于该算法在邻域的匹配方面仍然没有更大的突破，因此从合成效果来看并没有太 大的提高。 基于点的纹理合成方法的缺点主要表现为“碎点”。碎点的产生是算法本身 的缺陷，因为合成的最小单元就是像素。因此在单个像素合成欠佳的时候可能会 影响到后面一系列的合成，产生碎点。 山东大学硕士学位论文 2 2 2 块匹配算法 同点匹配算法不同，块匹配算法在进行合成采样时是以纹理块为基本单位。 在提高合成速度和保持纹理局部特征方面，块匹配是较理想的选择。 1 c h a o sm o s a i c 算法 2 0 0 0 年，x u 等人提出c h a o sm o s a i c 块合成算法【2 5 】就是一个块匹配算法。该 算法可以简单地分为以下两步：( 1 ) 先将样本纹理进行反复自映射，并通过混沌变 换得到初步合成纹理；( 2 ) 然后通过平滑边界来得到最终的合成结果。为了产生一 个视觉上随机的合成效果，该算法借鉴了非线性动力学的确定性混沌原理，并利 用a r n o l d 提出的c a t m a p ，将图像中的随机纹理块通过混沌迭代重复映射到其自 身。该算法的最主要缺陷就是图像拼接过程过于随机，因而对于结构性的纹理， 其合成效果往往比较差。 2 q u i l t i n g 算法 2 0 0 1 年，e f r o s 提出了q u i l t i n g 方法【2 6 1 ，使用寻找最小误差路径的方法实现 各块的拼接，极大地提高了合成速度。l i a n g 2 7 1 等人的方法则采用羽化融合方法 处理重叠区域。同混沌拼接的方法不同，此类算法的纹理块拼接过程并不是随机 的，其整个合成过程是按照扫描线顺序，将搜索得到的纹理块经过处理后依次拷 贝到目标纹理图像中。 i n p u t t e x t u r e 田圈 圈 r a n d o mp l a c e m e n t 雠i 誊婚。缸gb i 幽翅姻细嘲m o fb l o c k sc o n s t r a i n e db yo v e r l a p b o u n d a r yc m c o )( c ) 图2 - 3 基于块的纹理合成( 图来自文献 2 6 1 ) ( a ) 块的直接合成；( b ) 重叠区域匹配的块合成；( c ) q u i l t i n g 算法合成 q u i l t i n g 算法考虑两个小块之间用一条曲线作为两者的分界线，使得两块在 结构上匹配。首先计算重叠区域之间每个点的s s d 距离，然后从这个s s d 矩阵 中寻找一条贯穿重叠区域的曲线，使得这条曲线上累积误差最小，这条曲线称为 可以证明上面的算法求出的并不是所有上下贯通切割线中累积误差最小的， 因为我们要求得到的是一条连续的曲线，若要得到真正意义上的“最小误差切割 线”则需要遍历所有的可能的路径，这样的算法也并不复杂，但是时间复杂度将 大大提高。 3 g r a p h c u t 算法 2 0 0 1 年，k w a t r a 等人提出了g r a p h c u t 方法【2 引，g r a p h c u t t 2 8 1 是与q u i l t i n g 作 用类似的一种改善生成纹理接合处匹配的算法。它也搜索一条上下贯通的切割 线，但是基于的模型与q u i l t i n g 完全不同。g r a p h c u t 不仅能够完成两块相互重叠 部分的完美划分，而且能够完成搜索一条闭合的曲线，使得曲线内部取自新贴的 纹理，而外部取自原有的纹理，而且两部分匹配较好。这可以弥补合成过程中多 块接缝处出现断裂的缺陷，在这种情况下可以在断裂的地方再贴上一块纹理，然 后用g - r a p h c u t 算法生成一条闭合的曲线来围住断裂处，这样就解决了接缝处的 断裂问题。 如图2 4 所示，g r a p h c u t 将重叠区域视作一个图，图的每个结点都是一个像 素，相邻的两个像素之间有边，边上有权重。最左边的这些点与p a t c h a 节点之 间有连边，权重为无穷大，表示这些点需要从p a t c h a 中选择；最右边的那些点 与p a t c h b 节点之间有连边，权重为无穷大，表示这些点需要从p a t c h b 中选择。 g r a p h c u t 从两个像素之间划分一条切割线来决定中间的像素点是从哪个纹理片 中取得。g r a p h c u t 切割线考虑的是这些边上的权重，而边上的权重是根据边两 端的端点来决定的。 山东大学硕士学位论文 警瓷警 图2 - 4g r a p h c u t 原理示意图( 图来自文献 3 0 1 ) 由于每个结点处都有分别来自p a t c h a 和p a t c h b 的像素值，因此下面的公式 衡量了这两点之间的边的权重： m ( s ，t ，彳，b ) = 0 4 ( s ) 一b ( s ) 0 + i 陋o ) 一曰( f ) 0 式中s 和t 表示边的两个端点位置编号；么( s ) 和b ( s ) 表示在位置j 处来自纹 理片a 和纹理片b 的像素值。i 操作表示某种计算两个像素点之间差异的算法， 比如最简单的就是直接作差取绝对值。 我们依然希望找到一条从上到下的贯通的低花费路径。这是一个经典的图论 问题，称为“m i n c u t ”或者“m a x f l o w 2 9 - 3 0 1 。 4 w a n g t i l e 算法 w a n g t i l e 最早是由h a ow a n g 3 1 - 3 2 在1 9 6 1 年提出的，w a n g t i l e 是由边缘标 注了颜色的方块组成的集合，使用t i l e 集合通过边缘匹配可以生成任意大小的纹 理，也就是说共享的边缘有相同的颜色，这样生成的输出纹理是连续的，自然的。 c o h e n 在2 0 0 3 年提出了基于w a n g t i l e 的实时纹理合成方法【3 3 1 ，利用自动 生成的t i l e 集来拼贴整个平面，可以生成任意大小非周期纹理，这种方法可以用 于二维的纹理合成，也可以用于任意衄面。其中，每块t i l e 都是四块从输入纹理 中截取的菱形块按照不同排列得到的，组成一块t i l e 的菱形样本可以相同，每个 菱形代表了一种边缘的颜色。四块菱形样本排列如下图2 - 5 所示，每两块之间有 部分的重叠区域，重叠部分通过计算最小误差路径( 最小误差切割线) 来决定选 择取自那块样本的象素。不好的切割路径可能会导致明显的块与块之间的接缝， 因此，切割路径的选择需要有很好的规则， t i l e 集的生成步骤： 1 选择样本。从输入纹理中选择任意的4 片( 或更多) 菱形的样本集，每 个样本都被指定一个颜色。一般选择4 个菱形样本可以得到8 块t i l e ，而选择6 山东大学硕士学位论文 个样本纹理可以得到1 8 块t i l e 。 2 t i l e 集的生成。将菱形样本按不同排列采用q u i l t i n g 进行纹理合成，将 合成后的菱形块中间的正方形进行切割，得到一组t i l e 集，其中每个t i l e 块都 是大小相同的正方形，而且每块的边缘都对应一个颜色。t i l e 集的生成如下图2 - 5 所示，采用数字标注颜色。 ( a ) 纹理样本结合方法；c o ) t i l e 集，不同数字表示不同颜色 图2 - 5t i l e 集的生成方法( 图来自文献1 3 3 1 ) 3 最后将得到的t i l e 集拼贴成任意大小的纹理，合成过程中相邻的两块t i l e 的相邻边缘的颜色要吻合。根据图2 5 方法所得到的t i l e 集按照颜色匹配进行拼 贴。得到的结果如下图2 - 6 所示。 图2 - 6t i l e 集合根据边缘颜色匹配的结果( 图来自文献1 3 3 1 ) 假如t i l e