（计算机应用技术专业论文）基于样图实体纹理合成的加速算法.pdf

摘要 相对于曲面上其他产生纹理的方法( 如纹理映射、直接曲面上纹理合成等) ， 实体纹理合成方法可以避免纹理接缝、变形等问题，而且实体一旦合成可以被使 用，因此它越来越受到人们的关注。实体纹理合成中基于样图的方法相对简单且 对大部分纹理产生了很好的结果，但其合成速度慢影响了它的应用范围。本文主 要对基于样图的实体纹理合成方法进行加速，包括串行和并行两种方法。 串行加速方法将小波变换引入实体纹理合成过程中。该方法引入了多分辨率 金字塔的概念，然而与传统的多分辨率金字塔方法不同。本方法通过多级小波变 换处理输入图像获得输入金字塔，然后把最低分辨率的样图作为输入合成最低分 辨率实体，最后通过各级小波逆变换得到较高级分辨率实体。由于不需要通过纹 理合成的方法得到高分辨率实体，该方法极大的提高了合成速度。同时因为小波 变换是无损的，所以并不会降低合成实体的质量。 并行化方法将整个实体分成几个部分，每个部分由一个计算节点处理。在计 算结束后，头节点负责收集所有数据并写入文件。这种方法能够极大提高合成速 度。另外，由于每个机器只维护和处理部分实体，本方法可以节省内存。并行化 算法以微软的w c c s 2 0 0 3 为平台，它能简化对节点的管理。 关键词：小波变换实体纹理合成w c c s 2 0 0 3 并行 a b s t r a c t c o m p a r e dt oo t h e rt e x t u r es y n t h e s i sm e t h o d so na r b i t r a r ys u r f a c e s ，s u c ha s t e x t u r em a p p i n g ，s y n t h e s i z i n gt e x t u r eo ns u r f a c e sd i r e c t l ye t c ，s o l i dt e x t u r es y n t h e s i s c a l la v o i ds e a n l sa n dd i s t o r t i o n ，a n do n c et h es o l i di ss y n t h e s i z e d ，i tc a nb eu s e dm a n y t i m e s ，t h u s ，t h i sm e t h o dg e t sm o r ea t t e n t i o nr e c e n t l y e x e m p l a r - b a s e ds o l i dt e x t u r e s y n t h e s i si ss i m p l ea n dc a ng e tg o o dr e s u l t sf o rm o s tk i n d so ft e x t u r eb u ti t sh i g ht i m e c o m p l e x i t ya f f e c t si t sw i d ea p p l i c a t i o n t h i st h e s i si n t r o d u c e st w ow a y st os p e e du p e x e m p l a r - b a s e ds o l i dt e x t u r es y n t h e s i s ，i n c l u d i n gs e r i a la n dp a r a l l e lm e t h o d s t h es e r i a lm e t h o di n t r o d u c e sw a v e l e tt r a n s f o r mt ot h ep r o c e s so fs o l i dt e x t u r e s y n t h e s i s i ta p p l i e s m u l t i r e s o l u t i o np y r a m i d s s t r a t e g y , b u t d i f f e r e n tf r o mt h e t r a d i t i o n a lm u l t i r e s o l u t o np y r a m i d sm e t h o d m u l t i l e v e lw a v e l e tt r a n s f o r mi su s e do n t h ee x e m p l a rt oc o n s t r u c ti n p u tp y r a m i d s a n dt h e nt h el o w e s tr e s o l u t i o ni m a g ei s u s e da s i n p u tt os y n t h e s i z et h el o w e s tr e s o l u t i o ns o l i d a f t e rt h a t ，u s i n gi n v e r s e w a v e l e tt r a n s f o r m ，a l lo t h e rh i g h e rr e s o l u t i o ns o l i dp y r a m i d sa r er e c o n s t r u c t e d t h e s e r i a ls t r a t e g yd o e s n tn e e dt os y n t h e s i z es o l i dw h e ng e e i n gt h eh i g h e rr e s o l u t i o n s o l i d s ，w h i c hc a nr e d u c et h es y n t h e s i st i m eg r e a t l y f o rw a v e l e tr a n s f o r mi sr e v e r s i b l e ， t h i sm e t h o dw i l ln o td e b a s eq u a l i t y i nt h ep a r a l l e ls o l i dt e x t u r es y n t h e s i sp r o c e s s ，t h eo r i g i n a ls o l i di sd i v i d e di n t o s e v e r a lp a r t s ，e a c ho n ei sc o m p u t e db yac o m p u t en o d e t h eh e a dn o d eg a t h e r sa l lo f t h ec o m p u t i n gr e s u l t sf r o mo t h e rc o m p u t en o d e sa n dp u t st h e mi n t oaf i l e t h ep a r a l l e l p r o c e s ss p e e d su pt h es o l i dt e x t u r es y n t h e s i sg r e a t l y i na d d i t i o n ，t h em e t h o dc a na l s o s a v em e m o r y , f o re v e r yc o m p u t e rj u s tn e e d st od e a lw i t ho n ep a r to ft h es o l i d t h e p a r a l l e lm e t h o di sb a s e do i lm i c r o s o f t sw c c s 2 0 0 3 ，w h i c hs i m p l i f yt h em a n a g e m e n t o fc o m p u t en o d e s k e yw o r d s - w a v e l e tt r a n s f o i i l l ，s o l i dt e x t u r es y n t h e s i s ，w c c s2 0 0 3 ，p a r a l l e l 独创性声明 本人声明所呈交的学位论文是本人在导师指导下进行的研究工作和取得的 研究成果，除了文中特别加以标注和致谢之处外，论文中不包含其他人已经发表 或撰写过的研究成果，也不包含为获得苤盗盘堂或其他教育机构的学位或证 书而使用过的材料。与我一同工作的同志对本研究所做的任何贡献均已在论文中 作了明确的说明并表示了谢意。 学位论文作者签名：衙翠 签字日期： 刎髟 年月j 7r 学位论文版权使用授权书 本学位论文作者完全了解鑫盗盘堂有关保留、使用学位论文的规定。 特授权叁盗盘堂可以将学位论文的全部或部分内容编入有关数据库进行检 索，并采用影印、缩印或扫描等复制手段保存、汇编以供查阅和借阅。同意学校 向国家有关部门或机构送交论文的复印件和磁盘。 ( 保密的学位论文在解密后适用本授权说明) 学位论文作者躲看罕 签字同期：獬年月j 一日 新繇孑撕 签字r 期：矽孑年6 月歹同 第一章堵论 第一章绪论 在计算机图形学中，经常用纹理来表现物体的表面细节。纹理是指含有重复 模式并在重复模式上有一定数量随机性的图像。纹理合成是一个很好的产生纹理 的方法，用纹理合成的方法可以由一块小纹理产生任意大小的纹理，产生的纹理 看上去与小纹理相似但没有重复。所以，纹理合成在计算机图形学、图像处理和 计算机视觉上有很多应用。针对纹理合成速度慢的问题，本文主要展示了对基于 样图实体纹理合成的加速。首先介绍纹理合成的相关概念、理论、方法，然后实 现了一个实体纹理合成方法井在单机上实现了加速，最后把该实体纹理台成方法 进行并行化加速。 本章剩余部分先介绍纹理合成和实体纹理合成的概念以及纹理合成的应用， 接着介绍纹理合成的研究现状。之后介绍本文的主要贡献，最后介绍本文的组织 结构。 11 实体纹理合成 1 1 1 纹理合成 纹理技术在计算机图形学、虚拟现实和计算机视觉以及真实感绘制等相关领 域中一直受到广泛地重视，并蓬勃发展。 纹理是整体上表现出某种规律性而在局部区域内呈现不规则性的图像，如图 1 - 1 。不同纹理图像舍有的随机部分的多少不同，据此纹理分为随机纹理、半随 机纹理和结构性纹理。 圈1 1 纹理图像与非纹理罔像 第一章绪论 在计算机图形学中，再现表面细节信息对于真实感是非常重要的。一种方法 就是用原始的几何信息来建模表面细节，但是随着细节越来越复杂，这种方法变 得不太现实了。另外的一个方法就是把一张图片贴到物体表面，这种方法叫做纹 理映射。纹理映射一直是绘制复杂场景真实感图形最常用的技术，不仅提高了绘 制的效率和质量，而且降低了场景建模的复杂度。但是纹理映射通常只能在纹理 空间和表面参数空间进行一对一的映射。由于采样所获得的纹理样本通常为小纹 理，若强行将小块纹理映射到大的曲面上将导致映射后表面纹理的变形、扭曲以 至模糊不清。若采用重复映射技术则会出现表面纹理接缝走样等问题。为解决以 上问题，纹理合成技术应运而生。 与纹理映射不同，过程纹理合成( 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 s f r o ms m n p l e s ，t s f s ) 方法是近几年迅 速发展起来的一种新的纹理合成技术。它基于给定的小的纹理样图，通过提取纹 理样图的各种信息生成大的纹理图片。该大图在视觉上与样图相似而连续，而且 不存在明显的重复。t s f s 技术可以克服传统纹理映射方法的缺点，又避免了过 程纹理合成方法调参的繁琐，因而受到越来越多的关注，成为现在计算机图形学、 计算机视觉和图像处理领域的研究热点之一。 图1 - 2 纹理台成 基于样图的纹理台成发展到现在，已经在以下几个方面获得了很大的成功。 第一，基于m a r k o v 随机场模型的样图纹理合成。e f r o s 等人将m a r k o v 模型引入 样图纹理合成。该模型认为，任何一个像素，它的值只跟其周围像素点的值有关 系，跟其他像素无关。该方法对大多纹理都产生了很好的结果。后续的很多方法 都是基于这一模型【l 】。第二，曲面上的纹理合成该方法要解决的主要是如何设 定纹理方向、如何建立曲面与纹理样图之间的映射关系，以及如何获得匹配点的 第一章绪论 问题。基于上述思想的相关的文献有p ”。第三，逼真显示的纹理合成，要合成 逼真显示的纹理，不仅需要抽取纹理的纹理结构特征而且还要表现由于空间的 颜色和反射率的变化引起的显示变化。p o r t i l l a 和s i m o n c c l t i 提出用b t f ( b i d i r e c t i o n a l t e x t u r e f u n c t i o n ) 来描述，t o n g 等人基于b t f 提出相应的算法， 取得了理想的显示效果。第四，实体纹理合成。无扭曲失真、可重复利用等优点 使实体纹理台成受到了大家的关注。实体纹理一般都通过过程纹理来台成，鉴于 过程纹理的复杂和难于控制，现在出现了些基于样图的实体纹理合成方法，产 生了很好的结果，但是合成速度很慢，本文的内容主要研究基于样图的实体纹理 台成方法的加速和优化。 112 实体纹理合成 图1 - 3 实体纹理台成示意图 纹理可阻用来表现任意曲面的细节信息。纹理映射技术一直是绘制复杂场景 真实感图形最为常用的技术之，然而在任意曲面上，由于缺乏统一的参数化方 法，纹理映射会产生很大的纹理变形和不连续。取而代之的是曲面上的直接纹理 合成方法，该方法一定程度上缓解了上述缺陷。然而不能完全避免这些不足，在 曲率报大的曲面上仍然不能得到满意的结果。实体纹理中的每个体素都有纹理 值。由实体纹理雕刻出来的物体表面纹理不会出现变形和接缝等问题。尤其对于 曲率大的曲面，效果更加明显。而且，实体纹理一旦产生，就可以被用来纹理任 何三维物体，不用重新台成。实体纹理一般通过过程纹理的方法产生。该方法确 实能产生很好的结果，但是它只能操作某些特殊的纹理如木纹、毛发等。另一方 面，该方法需要调节很多参数，难于控制。另一种产生实体纹理的方法就是基于 纹理样图的合成方法。最初的方法是通过小尺寸实体产生大尺寸实体，但是由于 三维实体很难获得，这种方法没有受到研究者的重视。一些研究者将基于二维样 图的实体纹理合成方法用于合成实体纹理，产生了很好的结果，而且该方法简单 易于控制，受到越来越多的重视成为实体纹理合成研究的热点之一。 唧 第一章绪论 1 1 3 纹理合成的应用 纹理合成在计算机图形学、图像处理和计算机视觉上有很多应用。 1 ) 渲染 纹理可以模仿真实物体的表面细节：颜色、走向甚至模型的形状。 2 ) 压缩 描绘自然场景的图像经常含有很大的纹理区域，如草地、森林、沙滩等。由 于纹理一般都含有很重要的高频信息，它们很难被压缩。在预处理阶段，通过纹 理合成技术，它们是可以压缩的。然后通过纹理合成的技术来产生含有大量纹理 的人造场景。 3 ) 图像修复和编辑 照片、图像等经常含有瑕疵或有破损区域。有些时候这些是不能接受的。所 以就需要一个算法来处理这些瑕疵。很多时候，这些瑕疵出现在纹理区域内，并 且可以通过纹理合成来取代。 4 ) 计算机视觉 几种计算机视觉的任务使用纹理，如分割、识别、分类。这些任务需要纹理 模型，这些纹理模型来自于纹理合成。 5 ) 动画 计算机生成的动画通常会包含脚本事件和随机性的运动。脚本事件往往是非 重复的动作，如开门或捡拾物品，这些往往可以通过直接控制来实现。相反，随 机性的运动往往是重复性的背景运动，如海洋波浪、袅袅升烟或熊熊篝火。这种 在时空上不定性扩展的变化通常被称作时间纹理。使用传统的技术，很难在物理 模型上绘制时间纹理，因为在不同的物理过程中，产生的表观特征也很不相同。 如果将其视为纹理，就可以采用某种纹理合成算法进行建模并生成相应的纹理。 除了时间纹理外，关节的特定移动也可使用一维纹理来建模。这种纹理可以 用来表现如眨眼、人物走动等精巧动作。 1 2 纹理合成的研究现状 早期的纹理合成，作为图像处理的一个分支，往往通过复杂的数学模型和数 学工具来实现，这使得纹理合成很难进行优化。1 9 9 5 年之后纹理合成方法进步 很快。近十几年来，纹理合成的方法走过了从参数化方法到无参数方法的过程。 参数化方法试图基于样图建造一个纹理的参数化模型，这种方法一般适合于均匀 的和随机的纹理。1 9 9 5 年h e e g e r 和g e r g e n 2 1 采用参数化方法，引入多分辨率金 4 第一章绪论 字塔和直方图比较原图与结果的相似度。无参数纹理合成方法，一次只合成一个 像素或者一块纹理，实验显示该方法可以处理更多种纹理。d eb o n e t i s 从样图中 寻找特征匹配点填入纹理合成中。随着马尔可夫随机场( m r f ) 的应用，e f r o s 3 j 基于m r f 思想，认为待合成点的值只与其邻域值相关，通过在样图中查找匹配 的方法得到待合成点的值。该方法产生了令人意想不到的好结果，但是合成速度 很慢。w e i 5 1 采用固定l 型邻域进行查找，该方法的一个优点就是便于加速，同 时w e i 引入t s v q 的树形结构对纹理合成方法进行加速，使合成速度大大提高。 另外，w e i 引入多分辨率金字塔，这使得该方法更适合含有较大结构的纹理样图。 a s h i k h m i n 6 i j i 入一致搜索思想，每次查找时只从几个候选邻域中选择，这种方 法极大地提高了合成速度。c l a i r e 9 】在基于像素的纹理合成方法中引入小波变换， 一方面能极大的提高合成速度，另一方面可以控制合成纹理的结构大小。上述几 种方法均属于基于点的合成方法，e f r o s 和f r e e m a n 【7 k w a t r a 1 0 】引入基于块的纹 理合成方法，这种方法每次合成一个纹理块。基于块的纹理合成方法比基于点的 方法快很多，而且更适合结构性纹理，但是块与块之间的接缝问题一直是这种方 法的难点。t o n i e t t o j 以小波系数作为块之间距离比较的标准，提高了块合成质 量。k w a t r a 1 2 】是一种基于优化的方法，该方法整合了基于点和基于块纹理合成的 方法，把待合成纹理看成一个整体，在每次迭代中试图增加样图和结果图之间的 相似度。该方法能对大多纹理产生非常好的结果。 二维纹理合成的方法被应用来产生曲面上的纹理。w 萌和l e v o y 1 3 j 以及 t u r k h 】都用2 d 上的基于点的纹理合成方法在曲面上直接生成纹理。n e y r e t 1 5 j 、 p r a u l l 4 】、d i s h c h l e r 1 6 】以及f u l i w u 1 7 1 等直接把基于块的纹理合成方法应用到曲面 上。t o n g 1 8 】以及l i u 【1 9 】直接在任意曲面上合成b t f s 。这些直接合成的方法可以 取得很好的结果。w d 2 0 】【2 l 】引入基于样图的无参方法合成实体纹理，但是产生了 一定的模糊。q i n 和y i n g 2 2 】同样使用基于样图的方法合成实体纹理，该方法使 用b g l a m s ( b a s i cg r a yl e v e la u r am a t r i c e s ) 可以产生一些很好的结果，不过 它只适用于灰度图像。k o p f 2 4 整合了二维优化的方法和柱状图匹配来合成实体 纹理。该方法适用于较多纹理。但是高复杂度使该方法的广泛应用受到很大限制。 受到c l a i r e 的启发，本文将小波变换的思想应用到实体纹理合成，在不损失质量 的前提下，使合成速度得到了极大的提高。 1 3 本文的主要工作 本文的主要工作分为以下几个方面： 1 、实现并研究k o p f 2 3 1 的实体纹理合成方法。该方法将基于优化的纹理合成 第一章绪论 方法应用于三维，并整合直方图匹配，对大多纹理都能产生很好的结果。由于该 方法是基于m r f 模型的迭代过程，同时实体纹理中待合成点的数量很大，所以 合成速度很慢，成为该方法的致命问题。 2 、引入小波变换来加速实体纹理合成过程。本方法采用基于小波的多分辨 率金字塔方法，与传统的多分辨率金字塔方法不同。在传统的多分辨率金字塔方 法中，所有分辨率级别的实体都需要通过纹理合成的方法得到。由于基于小波的 多分辨率方法在构建输入金字塔时记录了小波系数，所以在合成得到最低分辨率 实体后，可以通过小波逆变换得到其他高分辨率实体。这使得本方法可以极大提 高实体纹理合成速度。 3 、本文将该实体纹理合成方法并行化。由于制约实体纹理合成速度的一个 重要因素是实体中待合成点的数量很大，所以本文将整个实体分成几个部分，每 个部分由一个计算节点维护。计算结束后，再把各个节点所维护的数据收集起来 得到最终结果。实验表明这种方法也可以极大提高合成速度。另外，由于并行化 算法中每个计算节点只维护部分实体，使得该方法可以减小内存消耗。 1 4 本文结构 本文剩余章节安排：第二章介绍纹理合成技术相关知识。第三章为实体纹理 合成方法研究，并介绍小波加速的实体纹理合成以及并行化算法的设计。第四章 介绍基于小波的实体纹理合成的技术细节。第五章介绍实体纹理合成方法的并行 化。第六章为总结与展望，总结本文主要贡献，展望未来研究方向。 第二章纹理合成相关知识综述 第二章纹理合成相关知识综述 近几年来，纹理合成已经成为研究领域的热门。在计算机视觉中，纹理合成 用来表现纹理模型，这样可以更好的进行纹理分割和纹理分类。在计算机图形学 和图像处理中，纹理合成也被应用到渲染、压缩以及图像编辑等领域。本章首先 介绍纹理合成的方法，然后深入展开介绍基于m r f 的方法及其相关概念。最后 介绍跟本文算法相关的小波变换的知识。 2 1 纹理合成方法 计算机图形学中，经常用纹理来渲染手工产生的图像。纹理合成是产生纹理 的很好的方法，所合成的纹理可以是任意大小，而且可以避免视觉上的重复。 物理仿真通过直接模仿纹理的物理产生过程合成纹理。通过反射传播a n d r e w 、矾t k m 和m i c h a e lk a s s 2 4 】的方法以及蜂窝纹理s t e v e np w o r l e y 2 5 方法对生物 模式，如毛发等进行建模。通过细节仿真j u l i ed o r s e y , a l a ne d e l m a n 3 u s t i n 等 2 6 1 可以很真实地再现一些风化和矿石的信号。这些技术可以直接在3 d 网格上产生 纹理，而且可以避免纹理映射的变形失真问题。然而，不同的纹理要通过不同的 物理过程产生，这使得这种方法只能用于产生有限的几类纹理。 近来很多纹理合成的算法通过m a r k o vr a n d o mf i e l d ( m l 玎) 来建模纹理， 并通过概率采样产生纹理。e f r o s 3 1 ，r p a g e t 2 7 1 ，k p o p a t 2 8 i s z h u 2 9 】证明m r f 建 模纹理可以实现对大量纹理的很好近似。这类纹理合成方法越来越多，且其中一 些方法产生了很好的结果。基于m r f 采样方法的一个缺点就是它的计算花费很 高。一个很小的纹理块的产生需要几个小时甚至几天时间。 一些算法【8 】【2 】【3 0 1 把纹理建模为一系列的特征结构，并通过在样图中匹配这些 结构来产生新的图像。一般来说这些算法比m r f 算法更加有效。h e e g e ra n d b e r g e n 【2 j 通过匹配图像金字塔来建模纹理。他们的方法适合随机性纹理。d e b o n e tf 8 】的方法更适合结构性纹理。s i m o n c e l l ia n dp o r t i l l a 3 0 】通过匹配图像金字塔 的边缘统计特性来产生纹理。这些方法都能成功地获得全局纹理结构却不能表现 局部特征。 第二章纹理合成相关知识综述 2 2 基于样图的纹理合成 对于大多数纹理，m r f 模型是一种很好的逼近模型。这种基于m r f 模型的 方法对很多纹理都能取得很好的结果。本文的所有研究都基于m r f 模型。 2 2 1 纹理合成相关概念 1 、邻域 m r f 模型认为，图像中任何一个像素的值只取决于它周围点的值，跟图像 中其他像素的值无关。图2 1 中实心点周围的空心点区域即为该实心点的邻域。 实心点的值与且仅与其邻域点值相关。邻域的大小由用户自己确定，但一般邻域 大小应该覆盖一个纹理结构，然而邻域太大将增加查找匹配的计算量。对于不同 的纹理应选择不同大小的邻域。 图2 1 不同大小的邻域 2 、邻域之间的距离 邻域之间的距离用来衡量两个邻域之间的相似度。一般使用欧几里得距离和 ( s s d ) 来计算邻域之间的距离，如公示( 2 1 ) d ( n i ，2 ) = ( p ) 一r 2 ( p ) ) ：+ ( g 。( p ) 一g ：( p ) ) ：+ ( b l ( p ) 一b 2 ( p ) ) 2 ( 2 - 1 ) p i nn m 、m 为两个邻域，p 为邻域中的像素，r j 例为邻域m 中像素p 的r 值。 2 2 2 基于样图纹理合成技术 e f r o s 3 1 将m r f 模型引入纹理合成产生了很好的结果。该方法的基本思想是， 根据结果图中当前待合成像素的邻域，在样图中搜索所有像素，找到具有匹配邻 域的像素集合，然后随机选择一个像素作为当前待合成点的最佳近似，合成到结 第= 章牧理音成相关知识睬述 果图中。这种用邻域的相似度来估计每个像素的方法对很多纹理都能产生很好的 结果。很多典型的算法：基于点的纹理合成方法、基于块的纹理合成方法以及基 于优化的纹理合成方法，都是基于这种思想。 e f r e s p l 的合成方法是基于点的纹理台成方法，但是合成速度很慢。w e i n 在 e f r o s 等人的基础上进行改进，以光栅扫描线顺序由一个噪声图像合成最终纹理， 并通过多分辨率架构和树结构向量量化的方法提高算法的性能。下面以w e i 嘲的 算法为倒来介绍基于点的纹理合成方法。 首先用随机噪声初始化结果纹理，这样可以增加结果纹理的随机性。在w e i 的方法中，采用扫描线的合成顺序。使用这个顺序合成，对于每个待台成像素， 它之前的像素一定已经被合成，而其后的像素都还没有颜色值。鉴于此，w e i 使 用l 型邻域进行查找匹配。每台成一个像素，邻域后移一个像素，直到整个图片 合成完。如图2 - 2 对于每个待台成点，根据它的邻域，通过s s d 到样圈中找匹 配邻域，一般会找到几个满足误差条件的邻域，然后选择最接近的邻域并取得相 应像素值付给当前待合成像素。 l a p u t 图2 - 2 基于点的纹理合成过程 基于像素的纹理合成方法计算简单，而且可控性强，但是由于每台成一个像 素点都要遍历整个输入图像来进行查找匹配，所以计算消耗非常大，合成一个很 小的图像往往需要几个小时甚至几天的时间。另外对于基于像素的纹理合成方 法，误差会随着合成过程不断积累。 e f r o sa n df r o 锄锄【”和k w a t r a i 州使用基于块的方法合成纹理，该方法尤其适 合结构性纹理。块的合成过程如图2 - 3 ，同样按照扫面线的顺序进行合成，对于 每个待合成的块，获得它的l 型邻域( 图中的红色框) ，基于该l 型邻域，到样 圉中查找最佳匹配邻域。在所有满足误差条件的结果中，选择最接近的邻域，然 后将整块复制到待合成块区域，这样就合成了一块。 # = 搜4 e 成相关知识综述 m 口啦 o f f , h t 图2 - 3 块的台成过程示意图 相对于基于像素的方；击，该方法尤其适合于结构性纹理，而且合成速度明显 提高。但是，块与块之间的接缝处会出现明显的不连续。而且基于块的纹理合成 方法可控性差。 针对该方法的主要缺点即块与块之间的不连续，e f r o s 采用最小能量线方法 处理块与块之间的区域如图2 4 。最小能量线是指在块占，和块岛的重叠区域 找到一条线，b ，和历中在这条线上的像素最匹配，也就是在这条线上重叠错误 最小。找到这条线后，重叠区域中最小能量线左边的像素取矗，中的颜色值，能 量线右边的像素值取毋中的颜色值。该方法可以有效的减小块之间的不连续。 圈 图2 4 星小能量线方法 基于优化的纹理合成方法v k k i ”】：定义一个能量函数，该能量函数表示合成 结果与原图之间的差别。能量函数越小，则合成结果与样图越接近。首先，待合 成结果中每个像素点的值随机地从样图中取得。然后。通过迭代优化结果纹理， 使结果纹理越来越接近输入样图。由于本文的方法是基于优化的方法，细节将在 后面提到，在此不在详述。 2 23 多分辨率图像金字塔 基于m r f 模型的纹理台成理论认用来进行查找匹配的邻域大小必须包含整 个纹理结构，对于大结构的纹理，必须使用大的邻域，这使得该方法的计算复杂 度很高。上述问题可以通过引入多分辨率金字塔解决”。 多分辨率合成方法：首先通过低采样由输入样图e 获得输入金字塔6 口。然 后，通过输入金字塔的最低分辨率层通过纹理合成方法获得输出金字塔矗的最 第二章纹理合成相关知识综述 低分辨率层，最后从低到高逐步得到整个输出金字塔q 。输出金字塔中每层的 合成方法类似于单分辨率方法。在得到高分辨率金字塔时，多分辨率方法中每个 待比较邻域由当前层里和低分辨率层中的像素组成。低分辨率邻域体现纹理的结 构，作为纹理合成的种限制，这样加入的高频信息就可以跟已合成的低频结构 统一起来。 j 7 ? ，“7t e z t u r em o d e l，厂丁7 +，。j ，一7 ，；。i i ，。”：+ 。“ d e c r e a s i n g i 。0 乏芝三。7t e z t u r em o d e l一乞乏冀7i i m a g e i ；二：乙一：，；：乏o l r e s o l u t i o n ? j ；：j ；答；， 。：；i ，t e x t u r em o d e l。；i ；y 4 。 o r i g i n a it e x t u r es y n t h e 右c 亿( t l j r e 图2 5 传统多分辨率纹理合成示意图 l e v e i = 2 l e v e i = 1 l e v e l = 0 图2 5 显示了多分辨率的合成过程。合成过程由低分辨率到高分辨率，右边 最底层分辨率纹理作为合成结果。在合成高分辨率层时，所选择邻域既包含本层 的像素同时也包含它的下一级低分辨率层中像素。图2 - 6 中l 为当前待合成分辨 率层，l - t - 1 显示下一级分辨率层。当前输出像素点x 所在位置( 厶x ，y ) ，为当 前分辨率级数，( x ，y ) 为x 点位置。在级，只有x 之前的像素被合成。所以此 时只能用三型邻域，即包含d 的邻域。当前像素x 的父亲点的位置为 + 1 ，x 2 ，y 2 ) ，图中表示为y 。由于三+ 1 级已经合成，所以邻域为方形。在搜 索时，邻域由三和+ 1 级中的邻域共同决定。该方法对大结构的纹理图像可以产 生很好的结果。 ( 1l l t 一， 0 0l( il 0 00、- l l + i 图2 - 6 多分辨率方法中的邻域选取5 】 第= 章毂理台威相关知识综述 2 3 三维纹理合成 2 3 1 直接在曲面上合成纹理 直接在曲面上合成纹理的方法不同于2 d 纹理合成，此种纹理合成需要设定 纹理的方向，以使物体表面纹理达到彼此一致。纹理分为各向同性纹理和各向异 性纹理。图2 7 ( a ) ( b ) 为各向同性纹理，这种纹理没有方向性。( c ) ( d ) 为各 向异性纹理，这种纹理有自己的方向性。对于各向同性纹理可以直接在曲面上合 成，不需要设定纹理方向；对于各向异性纹理需要设定纹理方向。设定纹理方向 的方法如：h o p p e 中用户直接定义纹理方向；w e il i y i “】中的松弛算法：g r e g t u r k 1 4 1 的插值算法等都产生了较好的结果。 攀溪蓁黧。皇筮三三三器：醢i ( a ) ( b )( c )( d ) 圈2 7 纹理类型 由于待合成的面为曲面，所以需要采取一定的方法将曲面映射到纹理空间。 将一个三角面片映射到纹理空间，选中的点处于该三角面片的中心，该点在曲 面上的坐标映射到纹理坐标，然后该面片周围的三角面片按距离由远及近逐个映 射到它的周围。口“中对于一个耍参数化的块( p a t c h ) ，把p a t c h 内部的所有三角 面片都投影到它的参考面。然后为投影到参考面坐标系统的每个三角面片的顶点 定义纹理坐标。吲中采用保角映射的方法。 曲面上的纹理合成方法不同于平面的方法，沿扫描线顺序合成的方法不再起 作用。w e i 【1 目随机扫描曲面上的顶点来合成纹理，而t u r k “i 按照所定义的矢量方 向扫描曲面上的待合成点。 在2 0 0 1 年的s i g g r a p h 会议上，w e i i 3 1 和t u r k “培自提出曲面上纹理合成 算法。他们把二维上基于点匹配的思想在三维上进行拓展，并采用多分辨率思想。 y i n g 口”等人，在w c i 和a s h i k h m i n 的启发下，提出两种新的合成方法。一种为 与w e i 等人类似的多分辨率方法，通过映射建立图表，在曲面的邻域和纹理样图 点邻域问建立对应联系；另一种基于a s h i k l m a i n 的思想，通过纹理映射图，为曲 面点的邻域查找在样本纹理上的对应点，实现纹理合成。上述第一种方法不适合 处理细节较多的纹理：第二种方法会出现接缝，对变化比较平缓的纹理效果不佳。 第二章纹理合成相关知识综述 在w e i 的算法中用到多分辨率思想。首先从样图中随机选择颜色值付给低分 辨率m e s h ，然后根据低分辨率m e s h 上点的值在低分辨率样图中的位置，找到高 分辨率m e s h 上对应点在高分辨率样图中的位置，并赋值。然后取得高分辨率 m e s h 上未获得值的点的邻域，并到样图中查找最近邻。邻域中的点部分来自低 分辨率m e s h 部分来自本分辨率级别m e s h 上已经合成的点。如此直到最高分辨 率m e s h 上所有点都获得颜色值。 基于块的曲面纹理合成算法也产生了很好的结果。文酬1 5 】通过预计算得到少 数几种带纹理的三角面片样本，这些带纹理的三角面片样本可以沿三角形边界无 缝地拼接，形成更大面积的带纹理三角网格，然后将曲面分割为大量可以局部参 数化为等腰三角形的曲面补丁，这样任意曲面上的纹理都可以用这些带纹理的三 角面片拼接而成。文献【4 】是三维曲面上重叠摆放不规则形状样本纹理的算法。首 先把曲面分割成不同大小且相互重叠的曲面补丁，进行纹理映射时把每个曲面补 丁局部参数化到纹理空间，通过重复地粘贴样本纹理覆盖曲面补丁，直至整个曲 面被完全覆盖。文献1 1 6 基于纹理粒子的曲面纹理合成方法，首先分析样本纹理， 通过定义颜色的阈值，提取样本中纹理粒子作为曲面纹理合成的基本单元，然后 分析样本纹理中纹理粒子的分布，在曲面上模拟这个分布合成曲面的纹理。上述 三种方法的特点( 1 ) 对样本纹理作预处理，生成无缝拼接的样本纹理集、不规 则形状的样本纹理和纹理粒子等( 2 ) 对三角化的曲面作预处理，生成曲面补丁。 文献【l7 】无须任何预处理，适合任意三角化的曲面和不同类型的样本纹理。 下面通过算法【l7 j 来展示基于块的纹理合成方法：算法中，用户指定若干三角 面片的切向矢量方向来控制纹理在曲面上的大致走向，余下的三角面片切向矢量 通过这些指定的切向矢量的加权插值得到，最终生成统一平滑的切向矢量场。对 于曲面上两个相邻的三角面片五和兀，当五被纹理化后，需要为三角面片正选择 纹理面片时，在样本纹理空间搜索纹理面片兀的纹理坐标，使得它和已纹理化的 三角面片z 的纹理相匹配。上述匹配过程中，根据用户指定的若干种子三角面片， 采用广度优先算法在纹理空间搜索匹配曲面的余下三角面片，直到整个曲面被覆 盖为止。 算法采用文献k w a t r a2 0 0 3 1 0 】的方法处理曲面上三角纹理补丁匹配区域之间 的拼接。对于图2 8 中，4 和以是全等梯形区域。需要找到它们在区域a ( a 和 4 重叠) 中最优拼接路径。彳中的部分像素从4 中选取，部分象素从4 中选取。 此时需要计算在区域彳中它们对应的每个象素的颜色差值，定义相邻象素a ，b 的匹配误差m 为： m ( a ，b ，a i ，a 2 ) = j | 彳l ( 口) 一a 2 ( a ) | | + | | as ( b ) - a 2 ( b ) i | ( 2 - 2 ) 镕= $ 纹理e 成相关自识综述 其中a 。表示f 的匹配区域纹理， 表示的匹配区域纹理。如图2 - 8 每个 节点表示一中的象素，相邻节点的线段赋权值为象素匹配误差值盯。找到最小 分割路径。分割路径决定节点代表的像素从或 中选取。 熊 232 实体纹理合成 实体纹理可以用来模拟物体的表面，实体纹理为物体的每个三维点定义颜 色，实体纹理可以避免变形和不连续性。过程纹理是产生实体纹理的主要方法。 但是这些方法只适用一些特定的物体，如木头，云等，而且不能建模通用的纹理， 对于它能建模的物体也需要努力去获得正确的参数。2 0 0 2 年w e il i - y i i “) 提出可 以通过输入纹理样图获得实体纹理的方j 击，合成过程为通过一个输入样图，产生 一个纹理实体，然后用模型雕刻出纹理目标。 合成的实体纹理是所有输入纹理的一个综合表现，从相应的观察方向，实体 纹理要与2 d 样图相似。一般从三个相交的方向表现实体纹理。输入观察点彼此 的一致性很重要，否则会产生模糊。尤其对于结构性纹理，要达到各个方向上纹 理一致性很难。而且当观察点越多的时候越难确定。 实体纹理的一些优踺点：实体纹理一旦合成，可以被重复应用于不同的物体。 合成的实体纹理没有扭曲失真。由于实体纹理要求在所有的观察方向看起来一 致，所以当观察方向很多时比较难控制。变体纹理计算花费较大，因为它要产生 整个实体的纹理而不止是物体表面的纹理。对于有主要方向的纹理，方向对整个 实体纹理都是固定的，不能局部调整。 2 0 0 7 年q l n 和y a n g 口1 提出种基于样图的基于b g l a m s 的实体纹理合成 方法，产生了一些较好的结果，但是这个算法只工作于灰度图像：】也提出了一 个基于样图的实体纹理合成的方法，扩展了2 d 纹理合成的优化方法，且应用全 局的柱状图匹配，产生较好的效果。 第二章纹理合成相关知识综述 2 4 小波变换以及小波变换的特性 2 4 1 小波变换 小波是近十几年才发展起来并迅速应用到图像处理和语音分析等众多领域 的一种数学工具。小波变换理论具有许多优良特性，如正交性、可重构性、方向 选择性、可变的时( 空) 频域分辨率等，这些良好的分析特性使小波变换成为信 号处理的一种强有力的工具和手段【3 4 1 。 1 、离散小波变换 执行离散小波变换的有效方法是使用滤波器。该方法是m a l l a t 在1 9 8 8 年开 发的，叫做m a l l a t 算法 3 5 1 ，这种方法实际上是一种信号的分解方法，在数字信 号处理中成为双通道子带编码。 一sh m 一 i 通 滤波器 高通 、l、l l a ii d l 图2 - 9 离散小波变换示意图 用滤波器执行离散小波变换的概念如图2 - 9 ，s 表示原始输入信号，通过两 个滤波器分别产生a 和d 两个信号，a 是由低通滤波器产生的信号的近似值， d 为由高通滤波器产生的信号的细节值。在许多应用中，信号的低频部分是最重 要的，而高频部分起一个“添加剂”的作用。在小波分析中，近似值是大的缩放 因子产生的系数，表示信号的低频分量。而细节值是小的缩放因子产生的系数， 表示信号的高频分量。原始信号通过这样的一对滤波器进行的分解叫做一级分 解。信号的分解过程可以叠代，也就是多级分解。 2 、小波重构 离散小波变换可以用来分解信号，这个过程叫做分解。把分解的系数还原成 原始信号的过程叫做小波重构( w a v e l e tr e c o n s t r u c t i o n ) ，数学上叫做逆离散小波 变换( i n v e r s ed i s c r e t ew a v e l e tt r a n s f o r m , i d w t ) 。 在使用滤波器做小波变换时包含滤波和降采样两个过程，在小波重构时要包 含升采样( u p s a m p l i n g ) 和滤波过程。 重构过程中滤波器的选择也是一个重要的研究问题，这是关系到能否重构出 第二章纹理合成相关知识综述 满意的原始信号的问题。在信号的分解期间，降采样会引起畸变，这种畸变叫做 混叠( a l i a s i n g ) 。这就需要在分解和重构阶段精心选择关系紧密但不一定一致的 滤波器才有可能取消这种混叠。低通分解滤波器和高通分解滤波器以及重构滤波 器构成一个系统，这个系统叫做正交镜像滤波器。 2 4 2h a a r 小波 本文在合成实体纹理时，加入h a a r 小波变换加速合成过程。下面介绍h a a r 小波的基本知识。 h a a r 小波是小波系列中最简单的小波。在众多正交函数中，h a a r 小波函数 是最