（计算机应用技术专业论文）块纹理合成的优化计算.pdf

中国科学技术大学硕士学位论文 摘要 纹理合成是当前计算机图形学、计算机视觉和图形图像处理领域的研究热点之 一。它在大规模场景的绘制、图像压缩、图像编辑、科学计算可视化等诸多领域都 具有重要的应用价值。人们通常是通过扫描仪或数码相机获取纹理，这些纹理图像 一般大小有限，对于复杂大型的三维场景表面，就需要重复映射多次才能将其覆盖。 对于没有严格周期性的纹理图像，单纯地重复拼接会造成纹理块之间明显的接缝及 重复。为此，人们提出并发展了基于样本的纹理合成技术。这种方法可以描述为： 给定一小块纹理，纹理合成技术可以生成与这个小块纹理视觉效果类似的大块纹 理。而且这种技术可以在三维场景表面直接合成，从而避免纹理映射产生的走样。 基于样本的纹理合成技术一般可分为基于像素的纹理合成技术和基于块的纹理合 成技术。由于基于块的纹理合成技术以包含多个像素的块作为纹理合成的操作单 元，因此合成速度很快，且能较好地保持纹理中大尺度的结构信息，是目前纹理合 成技术中探讨的热点方法。本文针对基于样本的纹理合成技术进行研究，致力于开 发一种适用于块合成方法的优化算法，使块合成方法能够得到更加有效地运用，本 文主要工作包括： 一在基于块的纹理合成方法中，对于同一幅样本纹理，采用不同的块参数( 包 括块的形状、大小以及相邻块之间的重叠区域的宽度) 进行合成，在合成 质量、合成速度上的差别很大。为此，我们深入分析了块参数变化趋势对 纹理合成质量的影响。 从纹理自身的结构信息特征出发，提出了有效的度量方法，以反映纹理块 参数对纹理信息特征的表达能力。在此基础上，我们提出一个自适应的计 算方法，能为样本纹理找到合适的优化合成参数，使得块合成方法能合成 高质量的纹理。这样，将有力地提高块合成方法的效率。 关键词：基于样本的纹理合成，摹于块的纹理合成，块参数，纹理特征，自适应优 化 中国科学技术大学硕士学位论文 o p t i m i z i n gi m p l e m e n t a t i o no fp a t c h - b a s e dt e x t u r es y n t h e s i s y i p i n gw a n g ( c o m p u t e ra p p l i c a t i o nt e c h n o l o g y ) d i r e c t e db yp r o f e s s o rw e n c h e n gw a n g a b s t r a c t t e x t u r es y n t h e s i si so n eo f t h em o s tp o p u l a rt e c h n i q u e si nc o m p u t e rg r a p h i c si th a sb e e n w i d e l ya p p l i e di nm a n yp r o s p e r o u sf i e l d s ，s u c h a s l a r g e s c a l es c e n er e n d e r i n g ，i m a g e c o m p r e s s i o na n ds c i e n t i f i cv i s u a l i z a t i o n p e o p l eu s u a l l yo b t a i nt e x t u r e sf r o ms c a n n e r s a n dc a m e r a s ，t h e s et e x t u r e s s i z e sa r ea l w a y sc o n s t r a i n e db yt h er e s o l u t i o n ，s ot h e y c a n tb ed i r e c t l ya p p l i e dt o3 ds u r f a c eu n l e s sm a p p e dr e p e a t e d l y h o w e v e r , p l a c i n gt h e t e x t u r ep a t c h e ss i m p l yw i l ll e a dt oo b v i o u ss e a m sa n dr e p e t i t i o n sb e t w e e np a t c h e s w i t h r e g a r d t o t h i s ，p e o p l e a d d r e s sa n dd e v e l o pt h ee x a m p l e - b a s e dt e x t u r e s y n t h e s i s t e c h n i q u e s t h e s et e c h n i q u e sc a nb ed e s c r i b e da sf o l l o w s ：g i v e na ne x a m p l et e x t u r e ，t h e y c a np r o d u c el a r g et e x t u r e st h a th a v es i m i l a ra p p e a r a n c ew i t ht h ee x a m p l e t h et e c h n i q u e s c a na l s os y n t h e s i st e x t u r e so n t ot h e3 ds u r f a c ed i r e c t l yt oa v o i dd i s t o r t i o nb yt e x t u r e m a p p i n g g e n e r a l l ys p e a k i n g ，e x a m p l e - b a s e dt e x t u r es y n t h e s i st e c h n i q u e sc a nb ed i v i d e d i n t ot w oc a t e g o r i e s ：p i x e l - b a s e dt e x t u r es y n t h e s i st e c h n i q u e sa n dp a t c h b a s e dt e x t u r e s y n t h e s i st e c h n i q u e sp a t c h - b a s e dt e x t u r es y n t h e s i sm e t h o d st a k ep a t c h e sa st h eo p e r a t i o n u n i t s ，w h e r ee v e r yp m c hc o n t a i n sm o r et h a no n ep i x e l i nc o m p a r i s o nw i t hp i x e l b a s e d m e t h o d s ，t h e s em e t h o d sc a nr u af a s t e ra n dp r o d u c eh i g hq u a l i t yt e x t u r e s o u rr e s e a r c hi s o ns a m p l e b a s e dt e x t u r es y n t h e s i st e c h n i q u e s w et r yt om a k ea no p t i m i z a t i o na l g o r i t h m t oa d a p t i v e l yf i n ds u i t a b l ep a r a m e t e r sf o rp a t c h - b a s et e x t u r es y n t h e s i st e c h n i q u e st or u n m o r ee f f e c t i v e l y ，w h e r et h ep a r a m e t e r si n c l u d e st h es i z eo fb a s i cp a t c h e sf o rs y n t h e s i s a n dt h ew i d t ho fo v e r l a p p e dr e g i o n sb e t w e e nn e i g h b o u rb a s i cp a t c h e sf o rc o n s t r a i n i n g s y n t h e s i s t h em a i nc o n t r i b u t i o no f t h i st h e s i si si nt h ef o l l o w i n ga s p e c t ： _ i n p a t c h - b a s e dt e x t u r es y n t h e s i st e c h n i q u e s t h ep a r a m e t e r sf o rs y n t h e s i sp l a ya n i m p o r t a n tr o l e ，w h e r et h ep a r a m e t e r si n c l u d e st h es h a p ea n ds i z eo fb a s i cp a t c h e s ， a n dt h ew i d t ho ft h eo v e r l a p p e dr e g i o n sb e t w e e nn e i g h b o u rb a s i cp a t c h e sf o r c o n s t r a i n i n gs y n t h e s i s i nt r e a t i n gas a m ee x a m p l et e x t u r e ，d i f f e r e n tp a r a m e t e r sw i l l l e a dg r e a tv a r i a t i o ni nt h es p e e da n dq u a l i t yf o rs y n t h e s i s i nt h i st h e s i s ，w em a k ea d e e pi n v e s t i g a t i o n o nh o wt h ep a r a m e t e r si n f l u e n c et h ee f f i c i e n c yo nt e x t u r e s y n t h e s i s _ w e p r e s e n te f f e c t i v et e c h n i q u e st om e a s u r et h ei n f l u e n c e sf o rt h ep a r a m e t e r so nt h e s y n t h e s i sa n db a s e do n t h em e a s u r e m e n t ，w eg i v eam e t h o dt oo p t i m i z et h e 中国科学技术大学硕士学位论文 块纹理合成的优化计算 p a r a m e t e r sa d a p t i v e l yf o r t h ep a t c h b a s e dt e x t u r es y n t h e s i sm e t h o d st op r o d u c eh i 曲 q u a l i t yt e x t u r e st h u s ，p a t c h b a s e dt e x t u r es y n t h e s i sm e t h o d sc a nb ep r o m p t e dal o t i na p p l i c a t i o n s k e y w o r d s ：s a m p l e b a s e dt e x t u r es y n t h e s i s ，p a t c h b a s e dt e x t u r es y n t h e s i s ，p a t c h p a r a m e t e r s ，t e x t u r ec h a r a c t e r i s t i c s ，a d a p t i v eo p t i m i z a t i o n i v 中国科学技术大学硕士学位论文 第一舒绪论 第一章绪论 纹理技术楚诗葬税图形掌中痘矮豢广泛魏装拳之一，在不增蕊兹 搴表蘑且簿复 杂庾的情况下，它可以有效地模拟和增强景物表面的细节特征，增加模型绘制的真 实感，或台戏菜秘姆定静稷甏效暴。 l1 背景介罐 行么是绞毽? 纹理是种普遍感觉羲糍鏊糯象，我餐霹数去感受纹理，去难疆瓣绞瑾豹精确 定义形成统一的认识。虽然肖许多关于纹理的定义，但大多是根据各自应用需求给 崮戆。嚣懿较为一裂缝获毒鬟蹩，纹臻 乍炎一滚强豫，在褪爨上其寿耋复豹结捣单元 ( 称为纹元) ，并且伴有一定的随机扰动( 如在相对位置、方向、颜色上有随机性 交讫) 。困熬，可敬说纹理楚垒鼹魏翔牲积鲻罄照搬瞧麴统一。 0 ) ( a 1 )( a 2 ) ( b t )国2 ) 圈l 。l ：纹瑷鹫豫翟一般錾豫数嚣 l 如图l ，l 惩示，曲是一蝠普通图像，( b ) 楚一蝠纹理图像。我们照两个尉榉大小 的滑动窗口分别在两幅图形l 二移动，随祝得捌两幅予图。对于纹理阐像而言，不同 中国科学技术大学硕士学位论文 块纹理合成的优化计算 位置的子图依然具有相似的内容( 如( b 1 ) ，( b 2 ) ) ，而普通图像则不具备此特性( 如 ( a 1 ) ，( a 2 ) ) 。 什么是纹理合成? 在计算机图形学中，我们通常需要在场景的表面贴上纹理以使得整个场景更加 具有真实感。早先的方法是采用纹理映射技术( t e x t u r e m a p p i n g ) 。它可以通过纹理 来表达表面丰富的几何细节和光照细节，甚至可以通过映射后纹理的变形来表达物 体的几何形状。但纹理映射通常只能在纹理空间和表面参数空间进行一对一的映 射。由于采样区域的局限性，所获取的纹理样本通常为小块纹理。若将小块纹理映 射到大的曲面上，它将导致映射后表面纹理模糊不清，若采用重复映射技术，则可 能出现表而纹理重每、楮缝、走样等问题。 输入纹理 厂、 纹理合成 图1 2 ：纹理合成示意图 输出纹理 相比于纹理映射，纹理合成技术以其自动、简单、合成效果好等优点受到广泛 的关注。这种技术可以描述为，给定- - + 块纹理样本，可以生成和该小块样本视觉 效果类似的大块纹理。这个大块纹理没有明显的接缝，也不是小块的简单重复，它 看起来与小块样本纹理是用同一规则产生出来的( 如图1 2 ) 。随着m a r k o v r a n d o m f i e l d 模型被引入到纹理合成中，基于样本的纹理合成技术获得了很大发展，现在已 经成为计算机图形学、计算机视觉和图像处理领域的一个热点研究内容。而且随着 研究的深入，纹理合成技术在图像编辑、数据压缩、几何处理、流场可视化等诸多 方面都开始得到应用。 中国科学技术大学硕士学位论文第一章绪论 1 2 本文的研究内容及组织结构 本文对纹理合成技术中流行的基于块的纹理合成方法进行了研究。首先对块的 大小以及重叠区域宽度对纹理的合成效果的影响进行了深入的探讨。并进一步建立 了针对样本纹理结构特征的度量方法，以反映块参数( 包括块的形状、大小以及相 邻块之间重叠区域的宽度) 对纹理信息特征的表达能力。在此基础上，本文提出自 适应计算方法以便为样本纹理找到合适的优化合成参数，使得基于块的合成方法能 合成高质量的纹理。这将有力地提高块合成方法在实践应用中的工作效率。 本文的组织结构如下： 在第二章中综述了纹理合成技术的主要方法及纹理合成技术在图形学和图像处 理方面的应用： 在第三章介绍基于块合成方法的优化算法； 在第四章总结本文的成果，并对未来的研究工作进行展望。 中国科学技术大学硕士学位论文 第二章基于样本的纹理含成技术综述 第二章基于样本的纹理合成技术综述 纹理合成技术的研究受到了很多研究人员的关注，已成为计算机图形学、计算 机视觉和图像处理的一个重要研究领域。目前，针对纹理合成的研究已有许多出色 的工作，本章将对这些已有的纹理合成技术进行概述。 纹理合成技术通常可以分为以下两类：基于过程的纹理合成技术和基于样本的 纹理合成技术。过程纹理合成法( 如文献 1 4 ) 通过模拟纹理的自然生长过程来合 成纹理，能够成功地模拟木纹、云雾、动物身上的斑纹等多种自然纹理。但是该方 法对每一种新纹理都需要调整参数反复测试，而且可能无法得到有效的参数，很不 方便。基于样本的合成技术是近几年发展起来的新技术，它建立在统计理论的基础 之上，认为合成出来的纹理图像与样本纹理图像应由同一个随机过程产生，从而在 视觉上是相似的。这种方法可以从- - + 块样本纹理合成出任意大小的纹理，而合成 纹理与样本纹理看起来好像是用同一规则产生出来的。基于样本的纹理合成技术避 免了过程纹理合成方法中调整参数的繁琐，而且适用于合成更多种类的纹理，因而 受到了越来越多研究人员的关注，己成为纹理合成技术发展的主流。 目前，基于样本的纹理合成技术大多以m a r k o vr a n d o mf i e l d ( m r f ) 作为纹理合 成的计算模型【5 】，即：一个区域的纹理特征仅由其局部邻域的纹理特征所决定。基 于m r f 模型，人们又提出了基于像素的纹理合成方法( 简称为点合成方法) 和基 于块的纹理合成方法( 简称为块合成方法) ，使纹理合成的质量和速度都有很大的 提高。本章将对一些主要的基于样本的纹理合成技术进行介绍，并简要介绍一些纹 理合成在图形学及图像处理方而的应用。 21 基本概念 在介绍具体算法之前，先阐明几个基本概念： 中国科学技术太学硕士学位论文 块纹理合成的优化计算 21 1m a r k o vr a n d o mf i e l d ( m r f ) 模型 1 9 4 8 年，s h a n n o n 在通信的数学理论一文中提出了一种利用n 语法自动产 生英文句子的方法。他首先通过采样语言系统构建广义m a r k o v 链：由n 个具有先 后顺序的字母构成n 语法，并由n 语法完全决定下一个将要生成的字母的概率分布。 使用较大的语言样本( 例如一本书) 可以形成每一个n 语法的概率表；然后从一个 种子字母开始反复采样m a r k o v 链产生新的字母，从而构成英文句子。这种方法由 一维扩展到二维，便产生了m a r k o vr a n d o mf i e l d ( m r f ) 模型 5 】。 在纹理合成中，m r f 模型可以表述如下：一个区域的纹理特征仅由其局部邻域 的纹理特征所决定。对于基于像素的纹理合成方法，m r f 模型根据输出纹理中当 前待合成像素点的邻域，在样本图中搜索所有像素，得到具有匹配邻域的像素点的 最佳近似合成到结果图中；对于基于块的纹理合成方法，m r f 模型根据输出纹理中 当前待合成纹理块的边界，在样本纹理中搜索与之最为匹配的纹理块合成到结果图 中。 2 12 待合成位置的邻域 根据当前待合成区域的大小，又分为待合成像素的邻域和待合成块的邻域。 待合成像素的邻域 鼍零一。罄 i 警j 霹孽曼捌! 蔫藕陶嘲嘲聃霸黑粼l 图2 - 1 ：基于像素的纹理合成 如图2 - 1 所示，当前待合成像素点的邻域是指在合成过程中，以当前待合成象 素( 图2 一l 左图中p 点) 为中心的正方形邻域与已合成像素点的交集。在样本纹理 中，按照当前待合成象紊点的邻域大小及相对位置关系确定样本纹理中每一个像素 的邻域( 图2 一l 右图) 。 中国科学技术大学硕士学位论文 第二章基于样本的纹理台成技术综述 待合成块的邻域 壁熏黑蟹豳懿篇 嚆熏鬻鬻舅一勖囊勇薹霸。 薹隧鬻錾争甏漕熏嚣露 图2 - 2 ：基于块的纹理合成 在基于块的纹理合成方法中，我们采用多个像素包含的块作为纹理合成的操作 单元。如图2 - 2 所示，图2 2 左图中绿色实心矩形为当前待合成的纹理块，取该纹 理块周围一定区域与己合成的纹理部分的交集作为当前纹理块的邻域。在样本纹理 中，对每一个可能被选中的纹理块建立同样大小及相对位置的邻域( 如图2 - 2 右图) 。 2 1 3 邻域匹配规则 以m a r k o vr a n d o mf i e l d o 强) 作为纹理合成计算模型的方法。往往需要进行邻 域的匹配计算，即，以当前待合成的像素或块的邻域作为查找向量在样本纹理中搜 索与之匹配的邻域，以获得最接近的像素或块。首先定义邻域的匹配误差如下： 给定两个形状、大小相同的邻域l 和2 ，这两个邻域的匹配误差为对应位置 像素的r g b 颜色值误差的累加，如公式2 1 。 d ( 1 ，n g = s q r t ( ( r ( p ) 一尺国) ) 2 + ( g ( p ) 一g 国) ) 2 + ( b ( p ) 一b ( q ) ) 2 ) ( 公式2 - 1 ) p n 1 q “2 其中r ( p ) 、g ( p ) 、b ( p ) 分别表示纹理图像中p 点的r 、g 、b 伪- - m - ，公式2 1 采用各对应像素r g b 颜色空问的l 2 距离描述匹配误差。 在基于m a r k o vr a n d o mf i e l d 计算模型的逐点台成算法中，我们需比较输出纹 理图像中当前待合成像素与样本纹理中每一个像索的邻域误差，在误差较小的候选 邻域中随机选择一个作为匹配邻域，这个过程称为邻域匹配，由匹配邻域决定的像 素称为匹配像索。 纹理块的边界误差指：将样本纹理中某一纹理块置于输出纹理中当前待合成纹 理块的位置，其与结果图中己合成区域的重叠区域部分通过公式2 1 计算得到的l 2 距离。 中国科学技术大学硕士学位论文块纹理合成的优化计算 在基于m a r k o vr a n d o mf i e l d 计算模型的逐块合成算法中，我们根据输出纹理 中当前待合成纹理块的位置，计算样本纹理中的每一个纹理块的边界误差，在误差 较小的候选纹理块中随机选择个，其边界就是匹配边界，这个过程称为纹理块的 边界匹配，由匹配边界决定的纹理块称为匹配纹理块。 基于m a r k o vr a n d o mf i e l d 模型的特点是，需要在样本纹理中进行邻域查找， 因此时间上消耗比较大。但是由于m r f 模型能够较好地体现纹理固有的局部相关 特性和稳定性，所以依然被广泛采用，下面介绍几种具有上述特点的典型方法。 2 2 基于像素的纹理合成方法 首先发展起来的是基于像素的纹理合成方法。此类方法在合成时每次仅对一个 像素进行操作。 2 21 基于统计方法的纹理合成技术 h e e g e r 等最早采用统计方法进行基于样本的纹理合成 6 】。他们利用l a p l a c i a n p y r a m i d 或s t e e r a b l e p y r a m i d 进行纹理合成。输入一个样本纹理以及一个与输出纹理 相同大小的噪声纹理，他们首先把样本和噪声都分解为层数相同的金字塔，然后在 金字塔的每一层对噪声纹理进行修改，使其颜色直方图与同一层样本的颜色直方图 一致；再将金字塔各层图像合并，得到一个新的噪声。当然这个新噪声和样本纹理 可能还相差甚远，这时候需要重新分解噪声图像，在各层重新匹配直方图，然后又 一次合成。如此迭代数次，最后把原始噪声图像转化为一个和样本纹理相似的新纹 理。d e b o n e t 在1 9 9 7 年提出的方法在文献【6 方法的基础上进行改进 7 】。他同样利 用l a p l a c i a n p y r a m i d 分解样本和噪声，但是采用自顶( 低分辨率) 向下( 高分辨率) 的顺序合成，在合成高分辨率图形时，同时考虑已经合成的低分辨率结果对它的影 响，从众多的符合条件的点中随机选取一个。这两种基于统计的纹理合成方法对一 些随机性较强的纹理效果不错，但并不适合有较强结构性的纹理。 2 2 2 基于非参数采样的纹理合成方法 1 9 9 9 年，e f r o s 和l e u n g 提出了种采用m a r k o vr a n d o mf i e l d 模型的合成方法 8 】，这也是第一次将m a r k o vr a n d o mf i e l d 的概念引入到纹理合成中。这种方法很 好地利用了纹理局部统计特征相似的性质，即，纹理图像中某一位置像素的颜色仅 由其邻域位置像素颜色所决定，而与其他位置像素颜色无关。在文中，作者取以当 一8 - 中困科学技术大学硕士学位论文 第二章基于样本的纹理台成技术综述 前像素为中心的一个正方形作为该像素的邻域。这个正方形的边长则作为一个可以 调节的参数，通常由样本纹理的纹元尺度所决定。 图2 - 3 ：非参数采样合成方法示意图 合成步骤如下： 对于当前待合成点p ( 输出图像中正方形框的中心就是待合成点) ，在样本纹理 中搜索与其有最相近邻域的k 。( p ) ( 国( p ，为以p 为中心点，以棚为边长的正 方形纹理块，如图2 - 3 右图黄色正方形框) 。算法采用了公式2 - 2 作为匹配查找 的规则。 在满足条件d ( p ) ，印) ( 1 + 6 ) d ( p ) ，。) 的所有纹理块国中，随机选择一个作为 待合成纹理的匹配区域，并将其中心点的颜色赋给待合成像素。 同之前的方法相比，e f r o s 算法的执行过程非常简单直观，而且合成纹理的质量 也有很大提高。此后的大量研究都采用了这种逐点预测合成的方式和l 2 1 q o r e 3 的匹 配规则。但是在文献 8 】方法中，对于有较大纹理结构的样本纹理，为了保证合成效 果，需要使用很大的查找邻域，这使得计算的开销呈几何级数增长：最严重的是文 献【8 】采用了穷尽搜索的策略，很小的纹理也需要花费相当长的时间。 2 2 3 基于树型矢量量化的纹理合成方法 w e i 和l e o v y 在2 0 0 0 年提出的方法是对文献 8 】的一种完善与改进【9 ，该方法 同样基于m r f 计算模型。文献 9 酐j p b - 法用噪声初始化纹理，然后按照扫描线顺序 来逐像素合成纹理。与文献 8 方法中采用正方形邻域不同，浚方法采用仅包含己合 成像素的上型邻域，每次从输入纹理样本中直接选取三型邻域误差最小的采样点， 作为当前待合成像素的值( 图2 - 4 ) 。更好地保证了合成结果。 中国科学技术大学硕士学位论文 块纹理合成的优化计算 图2 - 4 ：l 型邻域合成方法示意图 作者还使用了多分辨率的方法，为样本纹理图像和输出纹理图像分别建立图像 金字塔，然后白顶( 低分辨率) 向下( 高分辨率) 逐层合成，在合成当前层纹理时， 考虑上一层相应邻域对它的影响。图像的多分辫率表示有助于提高算法的合成速度 和合成质量。为了进一步对算法加速，作者采用树形矢量量化( t r e e s t r u c t u r e dv e c t o r q u a n t i z a t i o n ) 的方法组织样本纹理的搜索空间，大大降低了搜索的时问开销。 2 2 4 自然纹理合成方法 虽然文献 9 1 q h 算法的速度比文献【8 有了较大改进，但是仍然比较耗时。在文献 9 】的算法的基础上，a s h i k h m i n 在2 0 0 1 年提出了一种邻域限定的算法来进一步提高 合成速度并改善自然纹理的合成质量 1 0 】。该方法主要针对那些含有相似较小纹理 特征的纹理，而此类纹理在自然界中非常常见，如花、草、树皮等等。 图2 - 5 ：局部相关台成方法示意图 文献 1 0 】的算法根据图像的局部相关性，首先找到当前待合成位置的邻域中每 中国科学技术大学硕士学位论文第二章基于样本的纹理舍成技术综述 个像素在样本纹理中的原始位置；然后计算待合成位置与邻域像素的偏移量，以与 样本纹理中该邻域像素原始位置有同样偏移量的位置的像素作为待合成位置像素 的一个候选点；最后在所有候选点中随机选取一个像素填充( 图2 5 ) 。这种搜索方 法更容易找到与当前已合成纹理区域邻接的属于同一纹理特征的区域。由于此方法 比原来搜索整幅图像的方法大大减少了搜索空间，所以合成速度很快，相比于文献 9 中的方法，速度提升大约一个数量级左右。但是，这种方法由于搜索范围实在太 小，所以对结构性较强的纹理合成效果较差。 在文中，作者还进一步加入用户交互，使得纹理合成结果可以满足用户需求。 如将纹理图像中不同的纹理区域按照用户的要求来重新分布以产生特殊效果。 2 25 基于跳转映射的纹理合成方法。 虽然文献 1 0 1 中的算法在合成速度上有很大提高，但是仍然不能达到实时处理 的程度。2 0 0 2 年，z e l i n k a 等人提出了基于跳转映射的( j u m pm a p ) 的纹理合成方 法【1 1 。作者将纹理合成分为两个阶段：一个是分析阶段，一个是合成阶段。分析 阶段速度较慢，但是对于一幅纹理图像只要分析一次就可以反复用于多次的纹理合 成。 a 。镩，t ；露箸成区域。 团 固 i 萨锋赫。i ；m 囝 b 二。l _ 国 团豳 待台成区域 样本纹理 输出纹理 图2 - 6 ：基于跳转映射的方法的示意图 在分析阶段，作者为样本纹理的每一个像素建立一个数组，以存储该像素可能 跳转的下一个位置及跳转到该位置的概率，即i u m pm a p 。如图2 - 6 所示，输出纹理 中已合成像素a o 在样本纹理中对应多个相似的像素( 图中阴影部分的区域) ，这些 像素所在的位嚣就是a o 可能跳转到的位置：在合成阶段，合成每一个像素时，通 过查找邻域中某个像素在j u m pm a p 中对应的数组，选择其中的一个像素，如a o 选 择b t 作为下一步跳转的位置，那么b ，下的像素值就是待合成像素的值。这样在合 成过程中，不再需要进行邻域匹配汁算，纹理的合成速度| 旦达到了实时。 中国科学技术大学硕士学位沦文块纹理合成的优化计算 2 2 6 与合成路径无关的点合成方法 以上介绍的几剥- 点合成方法，合成的结果往往依赖于合成顺序，很不灵活，而 这种路径相关的方法，也不能达到所见即所得的合成效果。w e i 在2 0 0 2 年提出了一 种与合成路径无关的点合成方法 1 2 1 ，很好地解决了这一问题。 n e i 曲b o f h o o dp i x e l 豳圈豳 圈田田一 g e n e r a t i o n2g e n e r a t i o n lg c n m o n 0 图2 7 ：路径无关的点合成方法 w e i 的方法受到图像处理中卷积操作的启发。在图像卷积中，如果将一个模板 作用到一幅图像上，得到的新的图像中的每个值都来自原图像的旧值。w e i 的合成 方法采用多分辨率的图像塔，但和其他方法不同的是，在塔的每一层，建立多个级 ( g e n e r a t i o n ) ，如图2 7 所示。在合成第厶层、第g t 级( 记为 ) 中的像素， 遵循如下的一个偏序关系： _ i f f z , l j o r l i = j a n d g j a 一) ，则将该块分为四( 如图( c ) ) ， 对切分后的小块进行邻域匹配，若匹配误差小于阈值( 。 ) ，则将满足条件 的小块贴到当前区域。按此规则合成整幅纹理。在处理合成块的重叠区域时，采用 点合成方法将重叠区域内不匹配( 误差大于阈值) 的像素重新进行合成，以保证合 成效果。 23 5 基于图切分的纹理合成方法 在文献【1 5 的算法中通过最小误差路径法计算块之间重叠区域的最小误差边 界，k w a t r a 等人在2 0 0 3 年提出了基于图切分( g r a p h c u t ) 的方法对上述最小误差边 界的计算作出了重要改进 2 h 。相比于l e f r o s2 0 0 0 1 中的动态规划法，g r a p h c u t 方法 可以保留之前已合成块中的所有路径，在合成过程中可以随时修复已合成部分中效 果不佳的区域。 o l dn e w 图2 1 3 ：基于图切分的纹理合成方法 作者首先对于纹理块之间的重叠区域建立一个图结构，邻接的像素以边相连。 对于重叠区域图结构巾两个邻接的像素s 和t ，爿( ，) 、a ( t ) 为已合成块4 在s 、，位 中国科学技术大学硕士学位论文 块纹理合成的优化计算 置的颜色值，b ( s ) 、8 ( t ) 为待合成块b 在s 、f 位置的颜色值。作者用公式2 5 表示 相邻像素位置的权重： m ( s ，f ，a ，b ) = l | 4 ( s ) 一曰( s ) i i + l | 4 0 ) 一曰( f ) 然后算法通过屉大流算法在图中找到两个纹理块之间误差最小的路径。以此路 径对不同的纹理块进行拼接。该方法中纹理块之间的重叠区域可以是任意形状，因 此提高了合成方法的灵活性。而且由于对以往的分割边界有记忆，该方法可以在合 成效果不佳的区域上重新覆盖一个纹理块进行修补，直到效果满意为止。 2 3 6 基于w a n gt ii e s 的纹理合成方法 以上的块合成方法中，在合成中需要进行邻域匹配，计算量消耗很大。2 0 0 3 年， c o h e n 等人提出基于w a n gt i l e s 的纹理合成方法【2 2 】。这种方法的特点是，当从一 幅纹理图像中生成w a n g t i l e s 后，就可以反复用于多次合成，且合成过程只是简单 的拼接，合成速度非常快。 w a n gt i l e s 由一组正方形构成，这些正方形的每条边都用一种颜色标记。将这 些正方形按照如下规则紧密排列：相邻的两个正方形的邻接边颜色一样。在数学上 可以证明八个不同的正方形就可反复拼接出非重复性的纹理。如图2 一1 4 所示，图 2 - 1 4 ( a ) 是八个边染色正