（计算机应用技术专业论文）基于样图的纹理合成技术研究.pdf

基于样图的纹理合成技术研究 摘要 基于样图的纹理合成技术( 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 ) 是近年 来发展起来的一种新的纹理生成技术，它不仅克服了传统纹理映射方法的缺点， 而且避免了过程纹理合成调整参数的繁琐，因而受到越来越多研究人员的关注， 成为计算机图形学、计算机视觉和图像处理领域的研究热点之一。 本文对基于样图的纹理合成技术进行了研究，提出了一些新的观点和算法。 本文首先回顾了纹理合成技术的发展历程，对基于样图的纹理合成的经典算法 进行了详细的介绍。接着对图像修复技术和随机顺序纹理合成算法进行深入分 析，从图像修复的要求出发，对随机顺序纹理合成算法进行改进，提出了面向 图像修复的随机顺序纹理合成算法，并将其应用到图像修复中，取得了良好的 效果。讨论纹理的颜色信息和结构信息的作用，探讨在纹理合成过程中引入结 构信息的方法，最后提出一种基于块的随机顺序纹理合成算法。对纹理合成过 程中的控制问题进行了探讨，介绍了三种可控纹理合成算法：大小渐变、方向 变化、形状控制，并将它们都运用到w l 2 0 0 1 算法中，使一种算法可同时具有三 种可控机制，可以得到更多的纹理合成效果。 关键词：计算机图形学：纹理合成；图像修复；随机顺序 r e s e a r c ho nt e x t u r es y n t h e s i sf r o ms a m p l e a b s t r a c t t e x t u r es y n t h e s i sf r o ms a m p l e ( t s f s ) i so n eo ft h en e wt e c h n i q u e sf o rt e x t u r e g e n e r a t i o ni nr e c e n ty e a r s t s f sc a l lo v e r c o m es o m ed e f e c t so ft e x t u r em a p p i n g ，s u c ha s t e x t u r es e a m sa n dt e x t u r ed i s t o r t i o n s m o r e o v e r ，i tc a na v o i dt h eb o r i n gp r o c e s s e so f p a r a m e t e ro p t i m i z a t i o no fp r o c e d u r a lt e x t u r es y n t h e s i s ( p t s ) i nr e c e n ty e a r s ，t s f sh a s b e c o m eo n eo ft h er e s e a r c hh o t s p o t si nc o m p u t e rg r a p h i c sa n dc o m p u t e rv i s i o n i nt h i sp a p e r , w es t u d i e dt h et e c h n i q u eo ft s f sa n db r o u g h tf o r w a r ds o m en e w o p i n i o n sa n da l g o r i t h m so nt s e s f i r s t l y , w er e v i e w e dt h ed e v e l o p m e n ti nt h ea r e ao f t e x t u r es y n t h e s i sa n di n t r o d u c e dt y p i c a la l g o r i t h m so ft s f s s e c o n d l y , w ea n a l y z e di m a g e i n p a i n t i n gt e c h n i q u ea n dr a n d o mo r d e rt e x t u r es y n t h e s i sa l g o r i t h md e e p l ya n dp r e s e n t e da n a l g o r i t h mo fi m a g ei n p a i n t i n go r i e n t e dr a n d o mo r d e rt e x t u r es y n t h e s i s s o m ee x p e r i m e n t r e s u l t ss h o wt h a tt h ea l g o r i t h mw o r k sw e l lo nf i x i n gf l a w e dr e g i o n sa n dc a l lg e ts a t i s f a c t o r y e f f e c t t h i r d l y ，w ed i s c u s se f f e c t so ft e x t u r ec o l o ri n f o r m a t i o na n ds t r u c t u r ei n f o r m a t i o n ， a n dh o wt ou s es t r u c t u r ei n f o r m a t i o ni nt e x t u r es y n t h e s i sp r o c e s s ，p r e s e n ta na l g o r i t h mo f p a t c h b a s e dt e x t u r es y n t h e s i si nr a n d o mo r d e r f o u r t h l y ，w ed i s c u s sl o c a lc o n t r o lp r o b l e m i nt e x t u r es y n t h e s i sp r o c e s s ，i n t r o d u c et h r e ea l g o r i t h m st h a ta l l o w e dl o c a lc o n t r 0 1 w ea p p l y t h e mt ow l 2 0 0 1a l g o r i t h ma n dm a k ei tp o s s i b l et os y n t h e s i sm o r et e x t u r ep a t t e r n s k e y w o r d s ：c o m p u t e rg r a p h i c s ；t e x t u r es y n t h e s i s ；i m a g ei n p a i n t i n g ；r a n d o mo r d e r 插图清单 图1 1 普通图像与纹理的区别1 图1 2 纹理的三种类型2 图1 3 基于样图纹理合成示意图3 图1 4 视频纹理4 图2 1w l 2 0 0 0 算法示意图8 图2 2 a s h i k h m i n 算法示意图9 图2 3 纹理块的重叠区域1 0 图2 4 相邻块的拼接1 0 图2 5f l l x g s 2 0 0 1 边界区域匹配规则u 图2 6c s h d 2 0 0 3 算法示意图1 3 图2 7 两段视频进行缝合1 6 图3 1 输入纹理和输出纹理金字塔2 0 图3 2 两步合成邻域2 1 图3 3w l 2 0 0 1 算法的自可拼接性2 1 图3 4 方形邻域扫描线顺序合成2 2 图3 。5w l 2 0 0 0 和w l 2 0 0 1 算法的修复结果对比2 2 图3 6 方形邻域分层示意图2 3 图3 7 优化前后对比2 3 图3 8e l l 9 9 9 和改进后的随机算法修复结果对比2 4 圉3 9 去除不希望存在的物体2 5 图4 1 纹理样图与其纹元边界图2 7 图4 2 纹理的三种类型2 8 图4 3 “值不同时的合成效果一2 8 图4 4u 与合成纹理质量的关系2 9 图4 5 邻域分区3 0 图4 6 逐块合成纹理3 0 图4 7 修复后的纹理3 0 图4 8 合成结果对比- 3 l 图4 9 算法合成结果3 2 图5 1 真实纹理局部变化一3 3 图5 2 输入样图集3 4 图5 3t w 2 0 0 l 算法示意图3 4 图5 4t w 2 0 0 l 算法合成结果3 5 图s 。5w l 2 0 0 1 合成结果3 5 图5 6 用户控制纹理合成结果3 6 图5 7 用户控制合成的字母3 6 图5 8 p l 2 0 0 1 ) ) 向控制纹理合成结果3 7 图5 9 方向控制纹理合成算法示意图3 8 表格清单 表2 1 二维纹理合成典型算法比较1 7 表2 2 三维曲面纹理合成典型算法比较1 7 表2 3 视频纹理合成典型算法比较1 7 独创性声明 本人声明所呈交的学位论文是本人在导师指导下进行的研究工作及取得的研究成果。 据我所知，除了文中特别加以标志和致谢的地方外，论文中不包含其他人已经发表或撰 写过的研究成果，也不包含为获得盒胆王些盔堂或其他教育机构的学位或证书而使 用过的材料。与我一同工作的同志对本研究所做的任何贡献均已在论文中作了明确的说 明并表示谢意。 学位论文作者签字：江涛2 签字日期；2 0 0 6 年5 月2 7 日 江翩 学位论文版权使用授权书 本学位论文作者完全了解盒胆王些本堂有关保留、使用学位论文的规定，有权 保留并向国家有关部门或机构送交论文的复印件和磁盘，允许论文被查阅或借阅。本人 授权盒世王些盘堂可以将学位论文的全部或部分论文内容编入有关数据库进行检 索，可以采用影印、缩印或扫描等复制手段保存、汇编学位论文。 ( 保密的学位论文在解密后适用本授权书) 学位论文作者签名：江涛江漓导师签名：张佑生 磁孑砒 签字日期：2 0 0 7 年5 月2 7 日签字日期：2 0 0 7 年5 月2 7 日 学位论文作者毕业后去向 工作单位： 通讯地址： 电话 邮编 致谢 首先，衷心感谢我的导师张佑生教授。在张老师的精心指导下，本论文的 研究和撰写工作得以顺利完成。在三年的学习中，张老师渊博的学识，一丝不 苟的治学态度，诲人不倦的风范都给我留下了极为深刻的印象。他的精心指导， 无私关怀，以及他所营造的学术氛围使我受益良多。张老师给我在求知、做事 和为人等方面的熏陶将使我受益终身。正是因为张老师的长期鼓励、引导和启 发，作者才得以顺利完成本文的研究和写作。 其次，感谢薛峰博士、江巨浪博士、胡敏副教授、偶春生博士、王焕宝博 士、袁吴博士，他们思路开阔、研究成果丰富，从他们身上我学到很多做研究 的方法，解决了研究中遇到的难题，拓展了眼界。 第三，感谢刘俊娜、侯顺风、习雅思、王良燕、洪沛霖、黄忠、王臻等同 学，同他们的讨论使我拓展了知识范围，提高了研究方法。 第四，感谢计算机学院的曹航老师，王新生老师和徐静老师在这三年中所 给予的帮助和照顾。 第五，感谢我的同学张国良、李豹等人，以及室友曹力、王冠东，与他们 的相处给了我许多快乐，在学习和研究上他们也给了我许多的帮助。 最后，我要衷心地感谢我的父母，三年来他们给了我大量的理解和支持， 使我安心于学习，希望这篇论文没有辜负他们对我的关心与期望。 感i 9 在这三年中所有给予我帮助的人们! 江涛 2 0 0 7 年5 月 1 i 纹理简介 1 i 1 什么是纹理 第一章绪论 纹理是普遍存在的。纹理可以表现出物体表面丰富的细节特性，可以描述 各种各样有着重复特性的自然现象，例如工厂里机器的噪音、人的有规律的运 动( 跑步、面部表情) 以及物体表面的颜色和形状等。在计算机图形学领域内， 纹理通常是指在局部区域内呈现不规则性，而在整体上表现出某种规律性的特 殊图像。纹理和图像是不同的，纹理显然是图像，但并不是所有的图像都是纹 理。如图1 1 所示，图1 1 ( a ) 是一副l e n a 图像，图1 1 ( b ) 是一种纹理。假设只允 许通过较小的窗口( 图中的线框) 来观察它们。显然，对于图1 1 ( a ) 所示的普通 图像，观察者从不同位置的窗口看到的子图像具有明显区别，而对于图1 1 ( b ) 所示的纹理图像，观察者从不同位置的窗口看到的子图像则十分相似。 纹理图像具有以下两个特征： ( 1 ) 稳定性：不同区域的纹理都彼此相似： ( 2 ) 局部性：图像中的任一像素的颜色可以由其周围邻域内的像素预测得 到。 ( a )( ” 图1 1 普通图像与纹理的区别 我们可以把纹理看作是具有局部性和稳定性的随机过程的实现，即纹理中 的每一个像素点都可以由其空间邻域内的像素的集合来表达和确定 w e i 2 0 0 2 】。 虽然由于纹理的多样性，很难在一个通用的框架下去描绘和重现它们，但 是自1 9 5 0 年g i b s o n g i b s o n ：9 5 0 指出了纹理在可视化感知中的重要意义以来， 纹理技术在计算机图形学、虚拟现实和计算机视觉以及真实感图形绘制等领域， 一直受到广泛的重视，并取得了蓬勃的发展。 1 1 2 纹理的分类 纹理通常由图像扫描或手工绘制而得，其形式是千变万化的，也具有不同 的分类标准。按照分类的标准不同，纹理的分类也不同。 根据纹理的表现形式，纹理可以分为颜色纹理、过程纹理和几何纹理三大 类。其中颜色纹理主要包括呈现在物体表面上的各种花纹，图案和文字等，如 大理石墙面，墙上贴的字画，器皿上的图案等。过程纹理是指用过程来表现规 则或不规则的动态变化的自然景象，如水波、云、水和烟雾等的。几何纹理则 是指基于景物表面微观几何形状的表面纹理，如桔子、树干和岩石等表面呈现 的凹凸不平的纹理细节。 根据纹理特征分布的方式不同，按照能否从其内部分辨出纹元，可以把纹 理分为三类 x u 2 0 0 1 ：结构性纹理，随机性纹理，以及半结构半随机性纹理。结 构性纹理是由固定纹元( 保持纹理局部特性的最小纹理块) 按照一定规则排列而 成的纹理，例如砖墙、地板等。随机性纹理中找不到明确的纹元，例如沙粒、 裂痕等。但现实世界中的大部分纹理同时包含了以上两种特性，人们在其内部 可以分辨出纹元，但是纹元之间有一定的差异，而且纹元的排放也不是很规则， 例如织物、犁过的田地等。这种类型的纹理称为半结构半随机性纹理。 ( a ) 结构性纹理 1 2 纹理合成技术的发展 ( ”随机性纹理( c ) 半结构半随机性纹理 图1 2 纹理的三种类型 纹理绘制技术是计算机图形学中应用最广泛的技术之一。它可以在不增加 表面几何复杂度的情况下，模拟景物表面的细节特征，增加真实感，因此在真 实感图形绘制中占据重要的地位。 纹理映射( t e x t u r em a p p i n g ) 最早由c a t m u l i 【c a t l 9 7 4 】提出，是绘制复杂场景 真实感图形最为常用的技术。它可以通过纹理来表达表面丰富的几何细节。传 统的纹理映射技术在绘制大面积纹理和曲面纹理时会引起纹理接缝和扭曲等问 题。纹理映射通常只能在纹理空间和表面参数空间进行一对一的映射。由于采 样区域的局限性，所获取的纹理样本通常为小块纹理。若将小块纹理映射到大 的曲面上，它将导致映射后表面纹理模糊不清，若采用重复映射技术，则可能 2 出现表面纹理接缝与走样等问题。另外，重复映射所产生的纹理重复问题也是 该技术的一个重要缺陷。解决这些问题的一个方法就是使用更大的纹理样本。 纹理可以从自然界中通过摄像来获取，也可以用手工描绘，或者用过程定义。 但是由于光照条件和摄像角度的不同，从真实物体上摄像所得的纹理往往是不 同的。当场景中的光照与获得纹理时的光照条件不匹配时，我们将看到明显的 人工痕迹。而让艺术家或美工创建纹理则是一件非常耗时的事情。 纹理合成技术的就是用来解决这些问题的，它能有效克服纹理映射技术的 缺陷。目前纹理合成可分为过程纹理合成( p r o c e d u r a lt e x t u r es y n t h e s i s p t s ) 和基于样图的纹理合成( t e x t u r es y n t h e s i sf r o ms a m p l e t s f s ) 。 过程纹理合成通过对物体生成过程的仿真直接在曲面上生成如毛发、云雾、 木纹等类纹理，从而避免纹理映射带来的失真。这种方法可以获得非常逼真的 纹理。过程纹理合成效果很好，但也存在不足，就是对每一种新的纹理，都需 要经过反复调整参数与测试，有时甚至无法得到满意的结果。 基于样图的纹理合成是近几年迅速发展起来的一种新的纹理合成技术，它 的基本思想是基于给定小样图的纹理特征，生成大面积的曲面纹理，并保证纹 理结构的连续性和相似性。如图1 3 所示。基于样图的纹理合成不仅克服了传统 纹理映射方法的缺点，而且避免了过程纹理合成调整参数的繁琐，因而受到越 来越多研究人员的关注。成为计算机图形学、计算机视觉和图像处理领域的研 究热点之一。 潮一 图l - 3 基于样图纹理合成示意图 1 3 基于样图的纹理合成的研究内容 ( 1 ) 二维纹理合成 二维纹理合成的主要内容是根据输入样本纹理，研究一种算法生成与输入 样本纹理在视觉上相似又有足够变化的任意面积的输出纹理图像。二维纹理合 成的研究已经在合成速度、合成质量和合成效果多样性等方面取得了丰硕的成 果。其进一步的目标是：( 1 ) 提高合成质量；( 2 ) 提高合成速度；( 3 ) 合成更 多的纹理效果。 对于纹理合成质量主要可以从结构完整性、相似性和连续性等方面来衡 量。总体上说，基于点的纹理合成往往使合成结果的结构不完整；而基于块的 纹理合成往往使合成结果的重复性较强，且出现可察觉的接缝。也就是说，两 者都存在一定的问题。目前用以改善合成质量的措施有：使用伴随纹理( 纹理结 构图) ，采用更加准确的相似性衡量标准，应用最优路径缝合和图像分割 ( g r a p h c u t ) 等方法。 在合成速度上，基于块的纹理合成算法占有优势。虽然基于点的纹理合成 算法也可以通过各种加速方法达到秒级，但这要牺牲一定的合成质量。目前常 用的加速方法有模拟退火算法、k d 树、树形矢量量化、p s o 粒子群优化算法 等。 在实际应用中，人们往往希望合成多种样式的纹理。为了满足这一需求， 各种扩展纹理合成方法应运而生。通过它们，人们可以按照自己的需要合成纹 理。常见方法有用户控制、方向控制、大小渐变控制、纹理传输、多样图纹理 合成、带约束的多样图纹理合成等。与基于块的纹理合成算法相比，基于点的 纹理合成算法更加灵活，可以合成更多样式的纹理。 ( 2 ) 三维曲面纹理合成 在二维纹理合成技术的基础上，人们提出了三维曲面纹理合成技术。在2 0 0 1 年的s i g g r a p h 会议上w e i 和t u r k 提出了各自的曲面纹理合成算法【w l 2 0 0 1 】 【t u r k 2 0 0 l 】。他们都采用多分辨率的思想，把基于点匹配的思想在三维上拓展， 分别采用松弛算法和插值算法建立矢量场控制纹理的生长方向。 s o l e r 【s o l e r 2 0 0 2 】扩展了基于块的纹理合成方法，将其运用到三维曲面纹理合成 上，提出了基于i m a g eq u i l t i n g 的三维表面纹理合成算法。在 s o l e r 2 0 0 2 之前的 算法都是以基于点的纹理合成方法为基础，以三维表面的每个顶点为合成单位。 基于纹理块匹配的三维曲面纹理合成算法在合成质量和合成速度上有较大提 高。曲面纹理合成在真实感图形绘制、虚拟现实等领域有着广泛的应用前景。 如何提高合成效率和合成质量是需要进一步研究的内容。 ( 3 ) 视频纹理合成 视频纹理是a r n os c h o d l 【s s s e o o 】在s i g g r a p h2 0 0 0 上提出的一种新的媒 体，它介于图像和视频之间，具有两者的特征。例如，图像不随时间而改变， 缺乏动态性。无法反映动态的场景，而视频虽然具有动态性，但由于视频文件 占用存储空间较大，在存储空间有限的情况下其长度会受到一定的限制。 幽1 4 视频纹理 视频纹理具有时序稳定性和内容动态性，通过某种方式不断重复一些视觉 4 上的特征，而从宏观的角度上看又是不同的。利用视频纹理，可以实现利用有 限样本表达无限信息的目标。 河流、烟雾、火焰、瀑布等视频纹理可以视为二维纹理在时域上的扩展， 是三维纹理中的一类，因此也可以应用扩展的纹理合成方法进行合成。 【e l l 9 9 9 w l 2 0 0 0 和【k s e t b 2 0 0 3 都对视频纹理合成进行了讨论。 1 4 基于样图的纹理合成的应用 纹理合成技术在计算机图形学、图像处理以及计算机视觉等领域有着广泛 的应用： ( 1 ) 真实感图形绘制 曲面细节的绘制可以进一步提高所绘场景的真实感。传统上采用多边形或 三角形网格细化的方法实现，但是随着对细节的要求越来越高，这种几何的方 法显得力不从心。采用纹理合成可以得到质量很高的绘制结果。此外，纹理可 以表现物体表面的细节。【w s l 9 9 4 】【w s l 9 9 6 采用纹理合成的方法来描绘石头、 阴影等图案。 ( 2 ) 计算机动画 计算机动画中经常包含一些片断和随机性的动作。这些片断是一些非重复 的动作( 如开门、拾起一样东西等) ，可以通过方向控制而直接绘制。随机性 动作是一些重复性的背景运动，如水波、炊烟、燃烧的火焰等，在空间和时间 上都具有不确定性，可称为“时序纹理”【b a r l 9 9 9 s s s 2 0 0 0 】【s p l 9 9 6 】。这种 纹理通常很难使用基于物理过程的绘制方法获得，基于样图的纹理合成可以很 好实现这类纹理的绘制。 ( 3 ) 数据压缩 很多图像中包含大片的纹理，如草地、森林、沙滩等。由于其中包含一些 高频信息，使用诸如j p e g 等压缩技术很难得到较高的压缩比。通过在预处理 阶段先把图像中的纹理区域分割出来，再使用纹理合成的方法对其进行压缩， 就可以获得很高的压缩比 b a c l 9 9 6 】。这对于提高网络数据的传输效率有重要 意义。 ( 4 ) 图像修补和编辑 图像或视频中有时会出现一些瑕疵( 如划痕、污点、破损等) ，严重影响 其质量和实用价值，因此，图像修补技术引起了人们的关注。纹理合成技术可 在图像修补中发挥较好的作用，比如，若瑕疵出现在图像的背景区域或草地、 海滩、水面等带有纹理性质的场景中，则可以通过约束纹理合成的方法对其进 行修补，重现图像原来的纹理和结构 i p l 9 9 7 】【b s g b 2 0 0 0 】。 ( 5 ) 特殊效果的生成 使用t s f s 技术可以模拟很多特殊场景效果。 w e i 2 0 0 i 】首先提出使用多种 样图作为输入，合成一种新的纹理的算法，取得了很好的效果。 a s h 2 0 0 1 f f 用 一个“目标纹理”作指引，合成得到在亮度上与“目标纹理”相似的纹理。随 后，出现了如艺术图像( 国画、水彩画) 的学习和生成【h j 0 2 0 0 l 】【x z h b 2 0 0 2 】 【x w p 2 0 0 3 】【s l s 2 0 0 4 、褶皱现象仿真 x z j h j 2 0 0 6 、纹理混和 x b m 2 0 0 2 与纹 理传输 e f 2 0 0 1 等基于纹理合成技术的特殊效果生成算法。 1 s 本文的主要工作与章节安排 本文重点探讨基于样图的二维纹理合成的理论和算法。全文安排如下： 第一章绪论，首先介绍纹理的概念、特点和分类，然后介绍纹理合成技术 的发展历程最后对基于样图的纹理合成的研究内容和应用作了简单介绍。 第二章讨论基于样图的纹理合成技术，对典型算法进行综述。 第三章讨论面向图像修复的随机顺序纹理合成算法。在介绍图像修复技术 的概念和常见方法以及随机顺序纹理合成算法的基础上，从图像修复的要求出 发，对随机顺序纹理合成算法进行改进，提出了面向图像修复的随机顺序纹理 合成算法，并将其应用到图像修复中，取得了良好的效果。 第四章讨论基于块的随机顺序纹理合成算法。首先介绍基于点和基于块的 纹理合成方法各自的优点和不足，接着讨论纹理的颜色信息和结构信息的作用， 探讨在纹理合成过程中引入结构信息的方法，最后提出一种基于块的随机顺序 纹理合成算法。 第五章对纹理合成过程中的控制问题进行了探讨，介绍了三种可控纹理合 成算法：大小渐变、方向变化、用户控制，并将它们都运用到w l 2 0 0 1 算法中， 使一种算法可同时具有三种可控机制，可以合成更多的纹理效果。 第六章总结和展望，对本论文的研究成果进行总结，并提出进一步研究的 设想。 6 第二章基于样图的纹理合成典型算法 基于样图的纹理合成方法可以分为三类：二维纹理合成、曲面纹理合成和 视频纹理合成。由于时空不同，三类纹理合成方法既有相似之处，又各有特点。 总体而言，二维纹理合成是基础。很多曲面纹理合成算法和视频纹理合成算法 都是由二维纹理合成算法扩展而来。本文所做的工作主要是二维纹理合成，因 此本章重点介绍基于样图的二维纹理合成典型算法。 2 1 二维纹理合成 2 1 1 二维纹理合成方法的分类 二维纹理合成总体上可分为基于特征匹配和基于马尔可夫随机场( m a r k o v r a n d o mf i e l d 。m r f ) 的方法。 基于特征匹配的方法是把纹理当作一种特征集，通过在样本图中匹配特征 来生成新的纹理图像。受心理学研究的启发，h e e g e r 和b e r g e n 提出了一种渐进 的基于分析的合成算法 h b l 9 9 5 1 。该方法通过对纹理样本图像进行分析计算从 而建立图像金字塔，再经过多次倒塌金字塔来近似匹配图像金字塔的边缘直方 图来实现纹理合成。它对于随机性纹理可取得较好的效果，但结构性纹理的合 成结果不理想。d eb o n e r 采用一种与此类似的方法，对结构纹理的合成取得了 较好的效果，但对结构不明显的纹理会造成人工痕迹【b o n l 9 9 7 】。 近年来的大多数纹理合成算法都是基于m r f 模型的。m r f 模型的由来可追 溯至1 9 4 8 年。香农在通信的数学理论一文中提出了一种利用n 语法自动产生 英文句子的方法。他首先通过采样语言系统构建广义m a r k o v 链：由n 个具有先 后顺序的字母构成n 语法，并由n 语法完全决定下一个将要生成的字母的概率分 布。使用较大的语言样本( 例如一本书) 可以形成每一个n 语法的概率表；然 后从一个种子字母开始反复采样m a r k o v 链产生新的字母，从而构成英文句子。 香农用这种方法产生了经典名句：“is p e n ta ni n t e r e s t i n ge v e n i n gr e c e n t l yw i t ha g r a i no f s a l t 。这种方法由一维扩展到二维，便产生了m a r k o v r a n d o m f i e l d ( m r f ) 模型。 m r f 模型认为纹理具有局部统计特征，即纹理中的任一部分都可以由其 周围部分( 即邻域) 完全决定。这是对纹理的一种比较客观的认识。基于这一 认识，在纹理合成中，根据结果图中当前待合成像素点的邻域( 或当前待合成 纹理块的边界) ，在样本图中搜索所有像素( 或纹理块) ，得到具有匹配邻域 的像素点( 或具有匹配边界的纹理块) ，将其作为当前待合成像素点( 或纹理 块) 的最佳近似合成到结果图中。 基于m r f 模型的纹理合成方法又可细分为基于点和基于块的方法。 7 基于点的纹理合成算法每次合成一个像素点，需要大量的计算时间。对于 随机性较强的纹理取得了令人满意的合成效果，但对结构性较强纹理的合成效 果往往不是很理想。基于点的纹理合成算法可以控制每个像素的值，因此它更 加适合约束合成。经典的基于点的纹理合成算法有e f r o s 和l e u n g 在1 9 9 9 年提出 的非参数采样算法 e l l 9 9 9 】，w e i 在s i g g r a p h2 0 0 0 上提出的基于点的l 形邻域 搜索纹理合成算法【w l 2 0 0 0 】，a s h i k h m i n 对w l 2 0 0 0 算法进行改进后在2 0 0 1 年提 出的自然纹理合成算法 a s h 2 0 0 l 】以及w e i 在s i g g r a p h2 0 0 l 上提出的使用方 形对称邻域并采用随机顺序在任意曲面上进行纹理合成的算法 w l 2 0 0 1 1 。 基于块的方法加快了纹理合成的速度，可以较好的保持纹理全局结构特 征，但会在相邻块之间引入局部人工痕迹。各种基于块的纹理合成算法的不同 往往在于它们处理重叠区域和生成拼接块的策略不同。经典的基于块的纹理合 成算法有e f r o s 提出的通过计算纹理块重叠区域的边界误差进行匹配，并用最小 误差路径实现纹理块缝合的算法 e f 2 0 0 1 1 和c o h e n 提出的通过拼接w a n gt i l e s 实 时合成纹理的方法 c s h d 2 0 0 3 1 。 2 1 2 典型算法介绍 l 。基于点的合成算法 ( 1 ) w l 2 0 0 0 算法 w l 2 0 0 0 算法是对e l l 9 9 9 算法的一种改进，同样基于m r f 模型，但它 摈弃了【e l l 9 9 9 】中的概率函数而直接采样，邻域采用l 形状，如图2 1 。其算 法如下： 用随机噪声初始化输出图像，按照扫描线顺序逐像素合成。在输出图像中 取当前点p 的l 邻域( l 邻域的大小由人工给定) 。 在样图中找出一点，使该点的l 邻域与输出图像中当前点p 的l 邻域的误差最 小，把该点颜色拷贝到输出图像的p 点。 输出幽像样幽 图2 1w l 2 0 0 0 算法示意图 重复上述步骤，合成输出图像中的每个像素，得到最终合成结果。 8 在计算l 邻域间误差时。采用：距离作为衡量尺度。两个像素点的邻域误差 指它们邻域中对应像素的r g b 值误差之和。由两个像素点确定的形状相同的邻 域n l 、n 2 的误差定义为它们间的2 距离，即 一r 。= 。_ ： 碳n ，m ) = 乏：( f a ( 力一局( g ) 旷+ ( ( ；u ，) 一g ( 口妒+ ( 占【功一日( g 旷 ( 2 一1 ) 蕊甜 l 邻域的大小至少要能够覆盖纹元。l 邻域的大小对算法的合成速度和合成 结果质量影响很大。一般来说，邻域越大，合成质量越高，但是计算量增加很 快，导致合成时间也快速增加。为了解决这一问题，w e i 采用多分辨率合成的 方法来减小邻域的采样范围，同时通过树形矢量量化方法进行加速，大大提高 了纹理合成速度。但w e i 方法不适合处理具有较多细节的自然纹理。 ( 2 ) a s h i k h m i n 算法 2 0 0 1 年，a s h i k h m i n 利用相关性原理，对w l 2 0 0 0 算法进行改进与扩展，提 出了一种适合自然纹理合成的方法 a s h 2 0 0 1 】。w l 2 0 0 0 算法对样图进行全局搜 索来寻找最佳匹配点，速度较为缓慢。w e i 采用t s v q 分类进行局部搜索加 速，a s h i k h m i n 贝u 采用了更加巧妙的方法缩小搜索范围以提高合成速度，寻找当 前待合成点邻域内像素在样图中的位置，对它们进行平移，找到相当于输出图 中待合成点位置的候选点，比较这些候选点的l 邻域与当前待合成点的l 邻域的 2 距离，选择距离最小即最佳的匹配点，如图2 2 所示。 图2 2h s h i k h m i n 算法示意图 a s h i k h m i n 算法可简述如下： 随机选取样图中的像素初始化输出图像。设置一个与输出图像大小相同 的二维数组，甩以记录输出图像中像素在样图中的位置。 按照扫描线顺序逐像素进行合成。在输出图像中，考虑当前点的l 邻域。 对邻域中的每一个点，根据位置数组找到样图中该点所在位置。将该点 在样图中的位置进行偏移后，得到候选点的位置。 清除重复候选点。 在候选点中选取其l 邻域与输出图像当前点的l 邻域误差最小的点，拷贝 到输出图像当前点中，并记录该位置于位置数组中。 9 重复上述步骤，得到最终合成结果。 a s h i k h m i n 算法非常直观、简单，对绝大多数自然纹理都能取得很好的合成 效果，并且大大提高了合成速度。 2 基于块的合成算法 ( 1 ) e f 2 0 0 1 算法 e f r o s 在2 0 0 1 年的s i g g r a p h 会议上提出了一种基于块拼贴的纹理合成算 法 e f 2 0 0 1 1 ，与以往算法相比，该算法在纹理合成的时间和视觉效果方面都地 到了很大的提高，避免了以往的算法容易引起模糊与纹元错位等问题。但是存 在有时纹理块出现过多的重复，边界有时不匹配的现象。算法描述如下； 按扫描线颁序逐块合成输出匿像。 在当前待合成位置，在样图中搜索一组候选方块。计算方块和已合成纹 理的重叠区域像素的2 误差，将满足误差阂值的方块作为候选方块。待合 成位置不同时，纹理块的重叠区域也不同，如图2 3 所示。 ( a ) | l | | l l i l | | 匪i ( c ) 图2 3 纹理块的重叠区域 从这组候选方块中，随机选择一个方块放到待合成位置，与已合成的区 域形成一定的重叠。用动态规划算法在重叠区域中找出一条最小误差缝合路 径，沿此路径将当前方块与已合成的区域缝合，如图2 4 ( c ) 所示。 重复上述步骤，得到最终合成结果。 圈圈圈 ( a ) m 和b 2 纹理块( b ) 重叠区域( c ) 最小误差缝合路径 图2 a 相邻块的拼接 求最小误差缝合路径的过程如下：假设b 1 和b 2 是沿着它们的垂直边界重叠 的方块，b l ”和b 2 ”为各自的重叠区域( 如图2 4 ( a ) ( b ) 所示) ，误差表面定义为 e = ( b 1 0 vb 2 0 ) 2 ，为了找到穿过误差表面的最小误差路径，利用下式计算所有路 径的累计误差e ： 1 0 互，= e ，+ m i n ( e i 吐，i ，e - 1 ，巨 ) ( 2 2 ) 最后，e 中最后一行的最小值即为穿过误差表面的最小误差垂直路径的结 束处的值。从此结束处回溯找到最佳缝合路径。 水平重叠区域可以用相似的过程求得水平最佳缝合路径。如果同时有水平 和垂直重叠区域，最小误差路径将在中间相交。 合成中的方块大小是惟一由用户控制的参数。它取决于所给纹理的属性。 方块必须能够获得纹理的有关结构，但也不能过大，否则合成纹理中可能出现 较多重复纹理块。根据经验，重叠区域的宽度取方块宽度的1 6 ，误差的阈值设 置为最小误差的1 1 倍以内。 ( 2 ) l l x g s 2 0 0 1 算法 2 0 0 1 年3 月，微软亚洲研究院的梁林等人提出了和e f 2 0 0 1 算法极为相似的 块拼接算法，该算法也基于m r f 模型，并用纹理块边界匹配原则在样本图中搜 索最佳匹配块，同时采用四叉树金字塔、优化的k d 树和主元分析来加速搜索过 程，得到了实时的合成效果 l l x g s 2 0 0 l 】。 该算法的原理是从输入纹理i i 。中挑选出多个纹理块构成合成纹理i 。u t o 算 法从i i 。中挑选纹理块贴到i 。中。每两个块之间的重叠部分，称为边界 ( b o u n d a r y ) 。为保证合成纹理的质量，挑选的纹理块的边界必须与输出纹理i 。 中已有的纹理匹配。该算法的合成过程如图2 5 所示( 其中灰色区域为已经合 成的部分，阴影区域为边界区，蓝色区域为将要合成的纹理块) ，假设要合成的 纹理块为b k ，它只有部分边界与输出纹理i o u t 中已经合成的纹理块( b o ，b h ，b k 。1 韵边界匹配。在图2 5 中。b k 有宽度为w e 的边界区域瓦，在i 。u t 中已经合成 的纹理块有宽度为w e 的边界区域吃，通过基于纹理块的搜索策略后，矗应 当与或。，匹配。 竹 埘 图2 5 【l l x g s 2 0 0 1 边界区域匹配规则 l l x g s 2 0 0 1 算法为了保证输出纹理1 0 u i 的随机性，采用纹理块集合。包 含输入纹理i i n 中边界和吃匹配的所有纹理块。采用尽。) 表示i i 。中左下角点为 ( x ，y ) 的纹理块，则。可表示如下： 弘名= 置 ) i d ( 毛w ) ，口。) c k ，占厶 ( 2 - 3 ) 式中，d 。表示边界区的最大误差。为了增加输出纹理i 。的随机性， l l x g s 2 0 0 1 从中随机选择一个纹理块作为当前待合成纹理块b k 。如果妒。为 空，则选取i i 。中具有最小边界区域误差的纹理块作为b k 。公式( 2 3 ) 中的误差 计算公式如下： t d ( 岛( 。) ，吃) = 【( 矗一比) 2 严 ( 2 4 ) nt - i 1j = e ( s 比) 2 】l ，2 ( 2 5 ) n 培l 其中，a 表示边界区域所包含的像素个数，p 为像素的r g b 值，参数控制i o u i 与i 。的相似度。8 越小。相似性越大，一般情况下，8 取o 2 。 l l x g s 2 0 0 1 算法具体步骤如下： 1 ) 从l i n 中随机选择一个块b o ，宽度设为呒= 2 x m i n ( w i d t h 。，h e i g h t f | , ) ，其中 o 2 5 九 i ) 时，则可以认为从i j 到i i + l 的切换也 是自然的，我们称( i 。i ) 为跳变帧对，i 为跳变帧。在计算出视频中的跳变帧对后， 当视频播放到跳变帧i i 时，就随机选择往回跳变到帧1 i + i ，或者播放后续帧i + 1 ， 然后顺序播放，由此实现视频纹理的合成。 应用上述算法，s e h o d l 等人成功合成了蜡烛的火焰、钟摆、飘扬的旗帜、 脸部的运动和瀑布等视频纹理。但是，该算法对麦浪、海岸波浪视频纹理的合 成效果不佳，原因在于这些视频纹理难以找出合适的跳变帧对。对于任意两帧 都不相似的视频纹理，此算法不再有效。由于合成过程的计算量小，s s s e 2 0 0 0 算法完全能够实时合成视频纹理。 ( 2 ) s d w 2 0 0 1 算法 s o a t t o 等人提出了可编辑的动态纹理合成算法。这是一种基于图像绘制的 方法，通过对输入图像序列进行学习，然后生成新的、无限长的图像序列。新 生成的序列与原序列在视觉上十分相似。 s d w 2 0 0 1 算法与s s s e 2 0 0 0 算法不同之处在于：s s s e 2 0 0 0 算法只将原有的 帧重新排序，而不生成新的帧，因而不具有可编辑性；s d w 2 0 0 l 算法能够生成 新的帧，生成的图像序列不但具有很强的真实感，而且还具有一定的可编辑性。 s d w 2 0 0 l 算法思想如下： 图像序列表示为 i ( t ) ，t = l ，t ，相应的在时间t 带噪声信号的图像序列表示 为y ( t ) = i ( t ) + w ( t ) 。 令工( f ) = 丸( ，( f ) ) ，丸为一组滤波器，则，( ，) = 葺( f ) 谚= q ( f ) ，c = 0 1 ，0 2 0 。 ， 0 ， 为一组正交基。假设v 似和w 似为白噪声，；c ) 服从n ( o ，q ) 分布，i ，( ，) 服从 ( o ，r ) 分布，x ( o ) = ：c o ，则有： x ( t 十1 ) = a x ( t ) + v ( ，) ( 2 - 6 ) y ( f ) = c ( x ( ，) ) + w ( ，)( 2 - 7 ) 其中a r ，c = r ，要求估计参数a 、c 、q 、r 。一般采用最大似然估计法估 计上述模型。 s o a t t o 用动态纹理合成算法处理了旋涡及讲话的口形等