（计算机应用技术专业论文）大规模场景绘制中的纹理合成技术研究.pdf

哈尔滨理t 大学工学硕十学位论文 大规模场景绘制中的纹理合成技术研究 摘要 大规模场景绘制技术是游戏编程世界中的热点技术，同时它在其它诸如 g i s 系统、飞行模拟系统、v r 系统以及数字地球技术等领域都有着同样重 要的作用。大规模场景绘制技术是虚拟现实、实时仿真以及交互三维设计等 许多重要应用的底层支撑技术，也是计算机图形学本身的一个基础性研究课 题。 纹理合成技术是大规模场景绘制中的重要一环，可以提高场景真实感显 示效果，更加细腻的显示地形；多样图纹理合成用于将鲜花，绿草，黄沙等 多种元素更自然的显示在大规模地形当中；曲面纹理合成则用于将二维真实 纹理合成于凹凸不平的三维场景中；这两项技术直接影响到大规模场景绘制 中的渲染质量。 本文在对传统基于马尔可夫模型纹理合成理论进行深入研究的基础上， 以加快纹理合成速度，提高输出纹理质量为目的，针对曲面纹理合成和多样 图纹理合成，提出了相应的算法： 一 针对传统的基于顶点上色曲面纹理合成方法合成速度慢，合成曲面纹理 分辨率过分依赖于网格大小等问题，提出了网格拼接块的概念，将点合成与 块拼接相结合，提出了一种网格内点合成，网格间块拼接的新的曲面纹理合 成方法，并对拼贴块优化计算进行了深入探讨。 应用粒子群优化算法作为像素寻优策略，应用于多样图纹理合成算法 中，将群智能中经典的粒子群优化算法引入到纹理合成领域。应用粒子群优 化多样图纹理合成方法是传统的基于像素纹理合成方法和基于块的纹理合成 方法的折衷，除了大大提高了多样图纹理合成的速度，样图的质量也得到了 很大改善；经实验证明，该算法有效解决了徐晓刚混合纹理合成中输出纹理 出现的条痕问题。 最后，本文通过将以上算法应用于h u s tf i y 3 d 引擎之中，实现了一个 大规模场景漫游系统，对上述算法进行了验证，证明了算法的有效性。 关键词纹理合成；马尔可夫模型；网格拼贴块；粒子群优化 r e s e a r c ho nt e x t u r es y n t h e s i sf o rl a r g e - s c a l es c e n e r e n d e r i n g a bs t r a c t l a r g e s c a l es c e n er e n d e r i n gt e c h n o l o g yi s o n eo ft h eh i g h l yc o n c e r n e d t e c h n o l o g i e si nt h eg a m ep r o g r a m m i n gw o r l d ，a n di ta l s op l a y sa l li m p o r t a n tr o l e i nt h ea r e as u c ha sg i ss y s t e m ，f l i g h ts i m u l a t i o n ，v rs y s t e ma n dd i g i t a le a r t h t e c h n o l o g y l a r g e s c a l es c e n er e n d e r i n gi s t h et e c h n i c a lb a s i sf o rm a n yi m p o r t a n t a p p l i c a t i o n ss u c h a sv i r t u a lr e a l i t y , r e a l t i m es i m u l a t i o n ，i n t e r a c t i v e3 dm o d e l d e s i g n ，a n ds oo n m o r e o v e r , i th a sb e e naf u n d a m e n t a lr e s e a r c hf i e l di nc o m p u t e r g r a p h i c sf o rd e c a d e s t e x t u r e s y n t h e s i s ，w h i c h c a ni m p r o v et h eq u a l i t y o fr e a l i s t i c r e p r e s e n t a t i o no nt h es c e n ea n dd i s p l a y t h el a n d f o r mm o r ee x q u i s i t e ，i sa na n i m p o r t a n tp a r to fl a r g e s c a l es c e n er e n d e r i n g t h em u l t i s a m p l et e x t u r es y n t h e s i s i su s e dt om i x i n gt h es a m p l e s s u c ha sf l o w e r s ，g r a s s ，y e l l o w s a n dt o g e t h e ri no n e o u t p u ts c e n c e ，w h i l et h e t e x t u r es y n t h e s i so ns u r f a c e si su s e dt op u tt h e2 dt e x t u r e o nt h e3 ds c e n c e ；t h e s et w ot e c h n o l o g yp l a yai m p o r t a n tp a r to nt h eq u a l i t yo ft h e s c e n c er e a l i s t i cr e p r e s e n t a t i o n b a s e do nt h et r a d i t i o n a lm a r k o vm o d e lm e t h o d s0 1 1t e x t u r es y n t h e s i s ，t h i s p a p e rp a ym o r ea t t e n t i o no ni m p o v i n gt h es y n t h e s i z i n gs p e e d a n dt h eq u a l i t yo f t h eo u t p u tt e x t u r ei m a g e ，p u t t i n gf o r w a r dt h ea l g o r i t h mb e l o w ： a i ma tt h ec u r r e n tv e r t e xp i x e lc o l o r i n gb a s e dt e x t u r es y n t h e s i so ns u r f a c e , t h er e s o l u t i o ni sd e p e n do nm e s hs i z e ，a n dt h ep r o b l e mo fl o ws p e e do n s y n t h e s i z i n g ，p u tf o r w a r dac o n c e p to fp a i n t i n gb l o c ko fm e s h ，p u t t h ep i x e l s y n t h e s i sa n db l o c km o s a i ct o g e t h e r ，p u tf o r w a r da n e wt e x t u r es y n t h e s i sm e t h o d o ns u r f a c e ，w h i c hc a np i x e lc o l o r i n gi n s i d et h em e s h e sa n db l o c km o s a i ca m o n g t h em e s h e s a n dt h i sp a p e ra l s od oad e e p r e s e a r c ho nt h e o p t i m i z i n g i 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 u s i n gt h ep s om e t h o da sao p t i m i z a t i o ns t r a t e g y f o rt h em u l t i s a m p l e s t e x t u r es y n t h e s i s ，i n t r o d u c i n gt h ec l a s s i c a lp s om e t h o do fs w a r mi n t e l l i g e n c et o i i t h ea r e ao ft e x t u r es y n t h e s i s m u l t i s a m p l e s s y n t h e s i su s i n gp s oi sa ne c l e c t i c s c h e m eb e t w e e np i x e lb a s e dt e x t u r es y n t h e s i sm e t h o d sa n d p a t c h b a s e dt e x t u r e s y n t h e s i sm e t h o d s i ti m p r o v et h es p e e do fs y n t h e s i z i n ga n dt h eq u a l i t yo ft h e o u t p u ti m a g e ；t h ei m p l e m e n t a t i o no fa l g o r i t h mp r o v et h ee f f e c t i v e n e s so ft h i s m e t h o d a tl a s t ，t h i sa r t i c l eh a sr e a l i z e dt h ea b o v ea l g o r i t h mw i t ht h eh u s t f l y3d e n g i n e ，b yw h i c hal a r g e s c a l ew a l k t h r o u g hs y s t e mi si m p l e m e n t e d ，a n dp r o v e d t h ee f f e c t i v e n e s so ft h em e t h o d sa l la b o v e k e y w ordst e x t u r es y n t h e s i s ，m a r k o vm o d e l ，p a i n t i n gb l o c ko fm e s h ，p a r t i c l e s w a r mo p t i m i z m i o n i i i ， 哈尔滨理工大学硕士学位论文原创性声明 本人郑重声明：此处所提交的硕士学位论文大规模场景绘制中的纹理合 成技术研究，是本人在导师指导下，在哈尔滨理工大学攻读硕士学位期间独立 进行研究工作所取得的成果。据本人所知，论文中除已注明部分外不包含他人 已发表或撰写过的研究成果。对本文研究工作做出贡献的个人和集体，均已在 文中以明确方式注明。本声明的法律结果将完全由本人承担。 作者签名：奎峰 日期：z 口。g 年；月f 乙日 哈尔滨理工大学硕士学位论文使用授权书 4 ( - ；j c 规模场景绘制中的纹理合成技术研究系本人在哈尔滨理工大学攻读硕 士学位期间在导师指导下完成的硕士学位论文。本论文的研究成果归哈尔滨理 工大学所有，本论文的研究内容不得以其它单位的名义发表。本人完全了解哈 尔滨理工大学关于保存、使用学位论文的规定，同意学校保留并向有关部门提 交论文和电子版本，允许论文被查阅和借阅。本人授权哈尔滨理工大学可以采 用影印、缩印或其他复制手段保存论文，可以公布论文的全部或部分内容。 本学位论文属于 保密口，在年解密后适用授权书。 不保密口。 ( 请在以上相应方框内打) 作者签名：念哞 日期：b px 年；月，l 日 导师签名：扣纱绍 日期：枷绛乡月7 阳 哈尔滨理t 大学t 学硕士学位论文 1 1 研究背景及其意义 第1 章绪论 长期以来，图形真实感问题一直是计算机图形学研究的一个主要课题。由 于客观世界变化万千、错综复杂，要把客观世界的各种细微结构直接用几何模 型表示出来，不仅计算量大，而且建模难，难以满足实际需要。为了解决这些 问题，人们将图像处理技术与计算机图形技术相结合来完成真实感显示问题， 取得了长足的发展。它利用对图像的分析、处理及合成等技术获得许多有成效 的绘制效果，表现目前几何模型尚不能体现的细节，弥补了几何绘制的不足。 在最近几十年，基于图像的真实感绘制技术一直是国际上研究热点，而在其中 占有重要地位的纹理合成技术，也取得了重大的突破，引起了各国研究人员的 广泛关注。 1 1 1 纹理合成综述 自从1 9 7 4 年c a t m u l l 发明纹理映射技术【l 】以来，纹理合成即成为一个重要 的研究方向。该技术不断完善，直到今天已成为计算机成像中不可缺少的技 术，对增强三维场景真实感起着至关重要的作用【2 1 。根据表面纹理生成方法的 不同，可以把纹理合成技术分为三类：纹理映射、过程纹理合成、基于样图的 纹理合成【4 1 。 纹理映射( t e x t u r em a p p i n g ) 是绘制复杂场景真实感图形最为常用的技术， 它可以通过纹理来表达表面丰富的几何细节和光照细节，甚至可以通过映射后 纹理的变形来表达物体的几何形状。但纹理映射通常只能在纹理空间和表面参 数空间进行一对一的映射。由于采样区域的局限性，所获取的纹理样本通常为 小块纹理。若将小块纹理映射到大的曲面上，它将导致映射后表面纹理模糊不 清，若采用重复映射技术，则可能出现表面纹理接缝走样等问题1 4 1 。为此，先 后有许多文献对此提出了反走样的方法【5 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 ) ) 通 过对物体物理生成过程的仿真直接在曲面上生成纹理，如毛发、云雾、水纹 等，从而避免了纹理映射带来的失真【8 9 l 。上世纪八九十年代，很多学者致力于 过程纹理合成的研究。过程纹理合成效果很好，但对每一种新的纹理，都需要 哈尔滨理- t 人学工学硕一l j 学位论文 调整参数反复测试，非常不便，有的甚至无法得到有效的参数【1 0 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 ) 技术是近几年迅速发 展起来的一种新的纹理拼接技术，它基于给定的小区域纹理样本，按照表面的 几何形状，拼合生成整个曲面的纹理，它在视觉上是相似而连续的 i 1 , 1 2 】。纹理 合成技术可以克服传统纹理映射方法的缺点，又避免了过程纹理合成调整参数 的繁琐【1 3 1 ，因而受到越来越多研究人员的关注，成为计算机图形学、计算机视 觉和图像处理领域的研究热点之一。利用纹理合成技术还可以进行纹理填充 ( 如修补破损的图片，重现原有图片效果) ，纹理传输( 把一张图的纹理贴到另一 张图中) ，扩展到时域则可以用- - d , 段视频图像，生成任意长度的非重复的视 频动画等f 1 4 l 卯。所以纹理合成技术在图象编辑、网络数据的快速传输、大规模 场景的生成以及真实感和非真实感绘制等方面具有广泛的应用前景【1 6 1 。 1 1 2 纹理合成在大规模场景绘制中的应用 大规模复杂场景的快速绘制是计算机图形学和虚拟现实的一个重要的研究 课题，在包括计算机辅助设计、战场可视化、建筑漫游、驾驶模拟、虚拟仿真 和游戏娱乐等众多领域都有着非常重要的应用。纹理合成是解决场景真实感和 实时性矛盾的重要途径之一i l7 】。纹理可以在不增加场景中几何对象模型复杂性 的前提下得到逼真的表面细节，得到越来越广泛的研究和应用。基于样图的纹 理合成技术有效解决了传统的纹理映射方法中由于强行映射而产生表面细节分 辨率过低，纹理尺寸失真，图像连接处走样等问题；且由于输入样图是小块纹 理，保证了在有限的系统带宽的前提下传输大量的纹理数据到纹理缓存，以及 对资源的有效利用率( 1 8 】。 对于一定复杂度的虚拟环境，实时性和真实感仍是虚拟现实引擎的关键问 题所在。对于这两个密切相关的问题，基于样图的纹理合成技术取得了较好的 平衡。通过纹理合成，不仅可以降低对场景中景物模型复杂度的要求，而且还 可以得到真实细致的景物表面细节，获得满意的视觉效果。目前，在大规模场 景绘制中，主要用到了以下纹理合成技术： 1 曲面纹理合成大规模场景绘制中的地形场景并非一片坦荡，而是充满 了各种林林总总的山脉、土坡，对这些场景进行绘制，就涉及到了曲面纹理合 成方面的问题，如何能够有效地在曲面上进行快速，高质的纹理合成，成为了 大规模场景绘制中的重要问题。 2 多输入样图的纹理合成现实世界场景中的景物往往是多种纹理的组 哈尔滨理t 大学工学硕一i 二学位论文 合，例如一个开阔的草原并不都是草丛，还会有灌木丛、沙石、河流等，这些 景物交织在一起所展现的整体风貌才使人们感受到自然景物的美丽。 本文将对大规模场景绘制中纹理合成涉及到的以上两个方面进行深入探讨 并提出有效方案和实现。 1 2 国内外研究现状 根据合成时选用基本单元的不同，m r f 模型下的纹理合成分为基于像素的 合成( p i x e l b a s e ds y n t h e s i s ) 与基于块的纹理合成( p a t c h b a s e ds y n t h e s i s ) 垤】两 类，几乎所有的算法都可以归入这两类中。两类算法各有所长，总体上，基于 像素的方法擅长于匹配小的纹理细节，但难于再现突显的或全局的特征；相对 的，基于块的方法能更好地捕捉纹理的全局特征，但却苦于边界匹配不好时出 现的明显人工加工痕迹【2 0 l 。 在基于像素的合成中，设输入样图大小为m * m ，输出图像大小为n * n ，邻 域大小为k * k ，为输出图像中每一个待合成的单元寻找匹配时，如果采用穷举 法在样图中搜索，则算法的时间复杂度为o ( m 宰n 宰k ) 。而在基于块的合成中，虽 然以块为单位可使合成单元的数量大大减少，但同时也直接导致待合成单元的 邻域大小大幅度增加。所以无论是基于像素还是基于块的纹理合成，计算复杂 度是要解决的首要问题。为了加快合成算法的运行速度，研究者们使用了各种 策略，如t e x t o n 统计分析【2 l 】、图像金字塔加速【2 2 1 、主元分析【2 引、局部搜索【2 4 1 、 p s o 力h 速 2 5 , 2 6 】等各种数学方法。 合成纹理图像的质量是另一个需要解决的问题。首先，算法虽然以m r f 作 为合成时的基本准则，但多数算法都是基于贪心策略的一遍合成。多数情况 下，贪心策略并不能得到全局最优解，因而合成的图像整体上并不是严格遵守 m r f 模型；尽管少数算法通过多次迭代计算一定程度上解决了这个问题，却为 此付出了数倍甚至数十倍的计算代价。其次，单一的m r f 模型并非描述现实中 纹理图像的理想模型。在k v i v e k 的t e x t u r eo p t i m i z a t i o n 算法鲫中，输出图像的 结果理论上已非常接近严格的m r f 模型，但正如作者在结论中指出的：由于算 法在每次叠代时尽量减少能量，会受困于局部最小值，表现为纹理元素的模糊 或对齐错误。 总体上，使用迭代和优化的纹理合成方法以计算量数量级的提升为代价， 得到了更加符合m r f 模型的输出图像，代表了当前纹理合成算法图像质量的高 水准。 哈尔滨理t 大学工学硕1 ：学位论文 总得来说，基于样图的纹理合成当前面对的主要难点如下： 1 高速度算法与高质量合成图像的结合。合成纹理图像的质量与合成算法 的速度是难以兼顾的两点，高质量的算法无一例外需要大量的计算，速度通常 比普通算法慢两个数量级以上。即使以当前主流p c 机配置，即使合成一张数万 像素级别的高质量图像，所需要的时间往往也达到数十分钟。 2 在合成单元有顺序的前提下尽量使算法的输出接近全局意义上的m r f 最优。在纹理合成的过程中，为待合成单元寻找匹配时，这些单元的有序直接 导致其邻域有效信息通常只能达到邻域大小的1 2 。合成过程成了多次基于局 部邻域信息的匹配，从整体来看是局部贪心策略的叠加，无法从根本上保证 m r f 模型的局部性。 3 克服m r f 模型的局限性。m r f 模型虽然很好的描述了纹理的局部性， 却难以体现纹理的其它一些必要特性，如结构化纹理中特征的完整性及均匀分 布等。对于结构化纹理，纯粹基于m r f 模型的算法在合成时往往拘泥于局部最 小值而忽略纹理中的特征分布规律，容易导致输出图像出现结构性错误。一些 算法已经开始使用其它模型辅助合成，弥补m r f 模型的不足。 1 3 本文主要工作 本课题将从理论和原型系统两个方面对大规模场景绘制所涉及的纹理合成 中两个主要问题一曲面纹理合成和多样图纹理合成进行深入理论研究和实验验 证。本文中提出的方法主要旨在提高纹理合成的速度，并力求在速度和质量上 达到一个很好的平衡，即以高质量快速纹理合成算法为目标，提出了若干有效 解决方法，本课题的研究内容主要包括： 1 对纹理合成的相关重要概念进行了深入研究和探讨，对纹理合成的重要 方法如马尔可夫域，特征匹配等进行了理论分析； 2 对纹理合成的经典算法进行了探讨和实现，并分析了其优缺点和适用情 况； 3 提出了一种基于网格拼贴块的曲面纹理合成方法，这种方法是对二维块 纹理合成方法的三维化，通过网格拼贴块的概念的提出，结合网格的连续性与 块拼贴的快速性，有效解决了大规模场景绘制中快速曲面纹理合成的问题； 4 针对大规模场景中对于多样图纹理合成的需求，在传统点像素纹理合成 的基础上，提出了基于粒子群优化的多样图纹理合成方法，以粒子群算法来优 化输入样图点像素搜索策略，在提高合成速度的同时，也解决了合成质量条形 哈尔滨理工人学工学硕上学位论文 化问题。 5 最后，介绍了h u s tf l y 3 d 引擎的实现，并以此引擎为基础，应用前边 提到的两种纹理合成方法，实现了一个大规模场景漫游系统，证实了本文提出 的方案的可行性。 哈尔滨理t 大学丁学硕上学位论文 2 1 问题描述 第2 章典型算法分析与实现 2 1 1 纹理的定义 纹理是计算机视觉和真实感造型领域常常使用的概念，有着非常重要的应 用价值。在计算机图形学领域中，纹理的概念非常一般化，包含任何图形表面 上的表现都可以称之为纹理。但是在计算机视觉和图像处理领域中，更倾向于 种狭义的定义，到目前为止人们对纹理的概念还没有一个准确和统一的定 义，j a i n 认为：纹理一般指基本纹理元素一纹元的重复口”。纹元由几个像素组 成，纹元的位置是周期性的、类似周期性的或随机性的。自然纹理一般是随机 的，而人造的纹理通常是确定的或周期性的。纹理可以是粗糙的、细致的、平 滑的、颗粒状的、有波纹的、规则的、不规则的或线性的。 纹理可由图像扫描或手工绘制得到，也可用图形生成技术得到，其形式是 千变万化的。目前比较流行的纹理分类是按纹理特征进行分类，大体可以分为 三类：结构性纹理，随机性纹理，以及既有结构性又有随机性的纹理口”。结构 性纹理包含保持纹理局部性最小的纹理块即纹元，整个纹理都可以由这一系列 纹元组成，例如砖墙、地板等，如图2 - 1 ( a ) 所示；随机性纹理找不到明确的纹 元，例如沙子和草等，如图2 - i ( b ) 所示：但从自然界得到的纹理更多的是属于 第三类，即有结构性又有随机性，例如织物等，如图2 - l ( c ) 所示。 盛 簪。1 r 女r _ 擘：誊 i 。 。 + 曩_ 一? 蕊；，。一_ 1 *一- _ _ ；攀。囊圈飘 一“囵唧薯 图2 - 1 三种特征的纹理 f i g2 1 t h r e e k i n do f c h a r a c t e r s o f t h e t e x t u r e 纹理是具备大范围相似性与重复性的采样数据，这是大尺寸纹理能够从小 哈尔滨理工大学工学颀l ：学位论文 尺寸采样数据合成的基础。它区别于一般图像的两个特性是平稳性( s t a t i o n a r y ) 和局部性( l o c a l ) t 30 1 。不满足这种相似性与重复性的采样数据虽然也可以通过纹 理映射技术与三维场景中模型的表面相关联，但并不满足纹理的定义，也不具 备被合成的必要条件。纹理平稳性指纹理的不同区域看上去是相似的；纹理局 部性指纹理中一个像素点的颜色取决于它的一个小邻域内其它点的颜色，而与 其它剩余部分无关。如图2 2 、图2 3 所示，图2 2 是一个普通图像，图2 3 是 一个纹理图像，通过一个大小适当的可移动窗口去观察图像，当小窗口移动的 时候，能够看到图像的不同部分。图中黑色的矩形框代表可移动观察窗口处于 不同的位置，能够发现图2 2 黑色矩形框里面的内容看起来相差甚远，而图2 3 黑色矩形框里面的内容看起来总是相似的。另外可以发现图2 3 黑色窗口中 的任一像素可以由其周围邻域内的像素预测得到，而与图像中的剩余部分无 关。通过图2 2 和图2 。3 可以很好的说明纹理具有平稳性和局部性。 图2 - 2 普通图像 f i g 2 - 2c o m m o ni m a g e 图2 3 纹理图像 f i g 2 3t e x t u r ei m a g e 2 1 2 基于样图的纹理合成 根据对输出的不同要求，基于样图的纹理合成主要分为二维图像纹理合 成、三维曲面纹理合成和视频纹理合成 3 1 , 3 2 t 。前两者以二维纹理图像作为输 入，合成规模更大的二维像素点阵数据，不同的是前者输出为二维图像，后者 则是将输出数据定位到三维空间中的曲面上，二者在本质上都是二维图像通过 相似性和重复性将其采样规模进行扩充。而视频纹理合成与声音纹理合成则是 将普通的纹理合成概念推广到时域后的产物【3 3 1 。视频纹理合成用于将一段短时 哈尔滨理t 大学工学硕士学位论文 问视频扩充为长时间不间断视频，由于视频纹理合成只需在时域上进行扩展， 因此本质上是一维纹理的合成。 2 1 3 基本数学模型 无论随机性还是结构化纹理，马尔可夫随机场( m a r k o vr a n d o mf i e l d ，m r f ) 模型都被证明是描述纹理图像的有效模型，长期以来，基于该模型的纹理合成 普遍取得了较好的效果。该模型至今为止仍然是绝大多数基于样图的纹理合成 算法所使用的基本数学模型。 m r f 相关理论最早由香农于1 9 4 8 年提出。当时香农发明了一种利用n 语 法自动产生英文句子的算法，该算法通过对语言系统的采样而建立广义马尔可 夫链，并由n 个具有先后顺序的字母构成n 语法，由n 语法决定下一个待生成 字母的概率分布。当语言样本空间较大时，可以形成每一个1 1 语法的概率表， 通过从种子字母开始反复采样马尔可夫链，可以陆续产生新的字母序列，从而 构成英文句子。这种算法由一维扩展n - 维时便产生了m r f 模型【3 4 1 。 严格m r f 模型下的二维纹理图像，其点阵数据被看作概率密度采样，采 样数据具备局部性，即一个采样的静态概率分布完全由其一定范围内邻域采样 的取值决定，而与整个场中其它采样的取值无关。每个像素的取值由其周围像 素的取值所决定，这是对纹理图像一种比较客观的认识。在m r f 模型下，纹 理合成的主要过程就是根据当前待合成单元邻域的取值不断在输入样图中寻找 匹配。一般情况下，输出图像被划分为多个有序的待合成单元( 通常是单个像 素或像素块) ，按照顺序被逐个处理。每次算法直接提取输出图像中当前待合 成部分的邻域，在样本图中进行比较搜索，得到邻域区域相近似的单元，然后 将该单元拷贝到输出图像中的当前待合成部分。这一过程反复进行，直到输出 图像被填满为止。这种基本框架较好的表现了m r f 模型的局部统计特征，即 纹理中的任一部分的取值都可以由其邻域的取值完全决定，因而是一种比较理 想的框架。 2 1 4 优化问题及求解方法 所谓优化问题，就是在满足一定的约束条件下，寻找一组参数值，使系统 的某些性能指标达到最大或最d , t 3 5 1 。优化是科学研究，工程技术和经济管理领 域中的一种常见问题。例如，工程设计中怎样选择参数，使设计方案既满足使 用要求又能降低成本；资源分配中，怎样分配有限资源，使分配方案既满足各 哈尔滨理工大学工学硕十学位论文 方面的基本需求，又能获得好的经济效益；在人类活动的各个领域中，诸如此 类，不胜枚举。 优化问题是个古老的课题。长期以来，人们对优化问题进行了不懈地探讨 和研究。早在1 7 世纪，在英国科学家n e w t o n 发明微积分的时代，已经提出极 值问题，后来又提出约束优化问题并对此问题提出了l a g r a n g e 乘数法。1 9 3 9 年苏联数学家k a n t o r o u i c z 为解决生产组织中的问题，发表了生产组织与计 划中的数学方法等论文，这是世界上最早研究线性规划的文章。1 9 4 7 年法国 数学家c a u c h y 通过研究了函数值沿什么方向下降最快的问题，提出了最速下 降法【3 6 1 。本文所用到的粒子群优化算法，就是一种对搜索寻优的有效方法。 2 2 m r f 模型分析 马尔可夫模型是纹理合成中十分重要的一个理论，纹理合成的很多后续研 究都是在这种理论之上提出的，下面对马尔可夫模型进行深入的分析。 2 2 1 马尔可夫随机场理论 纹理合成算法要求在样本纹理中搜索匹配点，而这些待匹配的相邻像素点 之间存在着一定的依赖关系。m a r k o v 随机场模型就提供了关于图像的这种统 计描述，这种模型着眼于考虑每个像素点，关于它的一组邻近像素点的条件分 布，能够有效的描述图像的局部统计特征。 马尔可夫模型是指随机过程中的某个值仅与其最近的前一个数值有关，给 出该数值后，此随机过程值与前面更远处所有的值无关。如果该过程是离散 的，则称此马尔可夫过程为马尔可夫过程或者马尔可夫链。 如果过程的第f 个模式被分类为缈。，我们就说该决策过程在时刻f 的状态 是( 1 9 f 。用c o 和z 分别表示：时刻的类型和特征向量，p ( 彻是马尔可夫链的 转移概率【3 7 1 ，即： p ( i j ) = p r 矿= q 力1 = 哆) ，i ，= 1 , 2 ，m ( 2 - 1 ) 经简单推导，可以得到贝叶斯定理表达形式【3 8 】：该公式既可以对时刻r 状 态c of 做最佳决策，也可以计算时刻f + l 的状态彩f + 1 的先验概率。 p ( 国r ：哆z - ，x z ，石r ) ：_ l 竺垒竺= _ 三竺l 乙兰三三= = ! 二兰堕盟( 2 - 2 ) p ( c 0 7 = 哆x i , x 2 ，x f _ 1 ) p ( z 7 a ，j ) j = l 哈尔滨理工大学t 学硕上学位论文 设 s ，g ) 为任一图，x ) ( s ，s s ) 表示s 上的一簇随机变量x s i , x s 2 ，x 观， e = l ，2 ，l 1 ) 。则称彩= ( x s l ，t 2 ，x s n ) 为一个组态，q = 扣：f e ，1si 以) 为组态空间，马尔可夫随机场可以定义为： p ( x s i = x $ 1 五2 = t 2 ，叉_ = 靠) o ，v x ，l e ，1 i 九 ( 2 3 ) p ( t = f x r = ，r j ) = p ( x ，= i x r = 工，g ) ，协s ，( t l ，工，2 ，) q ( 2 4 ) 则x 为关于g 的马尔可夫随机场，简记为m r f 。m r f 模型认为纹理具有局部 统计特征，即纹理中的任一部分都可以由其周围部分( 即邻域) 完全决定，这是 对纹理的一种比较客观的认识。m a r k o v 随机场是图像建模的重要工具，在纹 理合成、纹理分析、图像分割、图像增强、图像压缩中具有广泛的应用。 2 2 2 m r f 模型优缺点分析 m r f 模型代表了纹理合成的主流方向，对于多数纹理，直接以m r f 为模 型或采用隐式m r f 模型，都可以产生较好的效果。m r f 模型关注纹理的局部 特性，用一块图像或一个像素的邻域部分唯一决定该图像块或像素的取值，所 以可以保证图像细节的连续过渡。因而对结构性纹理，合成图像的细节部分得 到了改善。 图像的整体特性方面，对一些纹元随机度和纹元分布随机度都比较弱的纹 理，通过连续的局部匹配，也可以很好地再现纹理的整体特性。当纹元本身随 机度比较高时，关注局部特性的m r f 模型可能会造成输出图像中纹元的变 形；而当纹元分布的随机度比较高时，单纯的局部匹配也容易造成输出图像纹 儿结构的混乱。 2 3 动态特征匹配算法分析 特征分析匹配的思路来源于人对纹理的感知，其基本策略是先抽取样图纹 理的表面特征，定义成特征规则集合，然后通过特征匹配生成新的纹理图案， 这种方法比马尔可夫随机场方法效率更高。h e e g e r 等通过匹配图像金字塔的边 缘直方图为纹理建模，在随机纹理合成中非常有效，但在具有结构特征的纹理 上效果较差【3 9 1 。b o n e t 等用多分辨率采样进行纹理分析和合成，在一定程度上 部分解决了纹理的结构特征提取【4 0 】。w i c k r a m a n a y a k e 利用小波变换对图像进行 3 级分解，再进行基于块的纹理合成，算法速度较快，但块的大小选择主要依 据水平和垂直重叠误差，并不能真正反映纹理的实际分布【4 1 1 。l e f e b v r e 等尝试 哈尔滨理t 大学t 学硕士学位论文 了并行可控的纹理合成 4 2 1 ，其算法是基于点的邻域匹配，采用了高斯栈作为新 的分析结构，以及结构坐标关联的向上取样、多次矫正方法等来达到各种约束 规则在纹理合成中的引入，由于在渲染的过程中基于g p u 的实现从而达到了 实时的效果。n i c o l l 等通过低通滤波和傅立叶分析实现了全局规则结构与非规 则结构的分离，并按规则结构生成掩码，控制非规则纹理细节的合成，在点匹 配和块匹配两种情况下都取得了进展【4 3 1 。 特征( f e a t u r e ) 是图像中的一类区域，通常位于图像中所表现实体的边沿轮 廓处，如楼房、汽车的轮廓，人脸上的鼻子、嘴、眼睛以及黑痔的边沿等。人 体视觉系统的相关研究表明，人眼对于图像中特征部分的敏感程度大大超过非 特征部分。具体到纹理图像中，特征就是纹元的边界。显然，纹理图像特征对 纹理合成有重要意义。通过特征匹配，可以减弱纹元形状变化对邻域匹配计算 的干扰，在输出图像中保持纹元形状的完整性，从而提升合成纹理的质量。 涉及特征分析与匹配的纹理合成研究相对较少，从目前的研究成果来看， 多分辨率的合成具有“邻域扩张 的效应，即用较小的邻域即可获得单分辨率 中较大的邻域的合成效果，有利于保持纹理的整体结构，而且可以有效地提高 合成速度。但目前主要问题是纹理特征多以统计信息为主，缺乏更细致的定 义。直接使用特征匹配的纹理合成需要解决以下三个问题： 1 有用特征区域的识别在随机性较强的纹理中，由于随机噪声的存在， 图像中除了纹元的边界外，会存在大量小规模的、零散的特征，这些特征由随 机噪声引起，可以出现在图像的任何地方，相互之间不存在对应关系。为了对 纹理特征进行匹配，必须想办法消除这些无用特征区域的干扰，将这些特征与 纹元边界处的大规模有用特征区分开。 2 提取用于匹配的形式化特征经特征识别得到的只是特征所在的区域， 而用于特征匹配的特征形式可以是点、线等其它形式，如何从特征区域得到这 些形式化的特征是必须解决的问题。 3 制定特征匹配的准则特征之间的匹配形式可以是点与点、线与线、区 域与区域等，还可以涉及到色彩比较等。制定出的特征匹配准则必须有效反映 受关注的特征特性，体现这些受关注特性在特征之间的相似程度。 由以上分析可知特征匹配方法如果能够和m r f 方法相结合，将有助于提 高纹理合成的质量，弥补单纯m r f 模型的不足。是一个很值得研究的方法理 论。 哈尔滨理t 大学工学硕十学位论文 2 4 基于像素的纹理合成方法分析 2 4 1 基本思想 基于像素的纹理合成是纹理合成的基础，它的基本思想是以像素为单位， 根据邻域相似性从输入样图中选择合适的像素，拷贝到输出图像中，该过程不 断重复，直到输出图像被填充满为止。 2 4 2 w 萌l e v o y 算法 w 萌l e v o y 算法是一种典型的基于样图的纹理合成，它基于m r f 模型， 采用直接采样的方式，邻域为l 型，计算时按照扫描线顺序，逐点进行采样合 成【4 5 1 ，其算法如下： 1 用随机噪声初始化输出图象，对输出图象的每一个点，按照扫描线顺序 查找。在输出图象中，取出当前点l 形状的邻域，l 邻域的大小由人工给定。 2 在输入的样图中找出一点，使该点的l 邻域与输出图象中l 邻域的误差 最小。 3 把该点拷贝放入输出图象中。重复上述过程，得到最后合成图象。 该算法是典型的基于像素纹理合成的方法，相对于其他纹理合成方法，它 具有实现简单，能够处理纹理类型多等优点，且随着l 邻域尺度的增大，合成 质量会更高，但计算量会成倍增加，且合成时间也会加长。w e i 和l e v o y 为了 解决这个问题，采用了多分辨率合成的方法来降低邻域采样范围，同时通过树 结构矢量量化( t r e e - s t r u c t u r e dv e c t o rq u a n t i z a t i o n ，t s v q ) 方法进行加速，取得很 好效果。该方法不适合处理具有较多细节的自然纹理。本文对w e i l e v o y 算法 进行了实现，图2 - 4 展示了w 静l e v o y 算法的纹理合成效果，图2 - 4 左边小图 为输入样图，右侧为合成后的输出样图。 哈尔滨理_ t 人学工学硕士学位论文 r 捌怄塑j 堕； l 团圈国i 图2 _ 4w e i l e v o y 算法纹理合成效果 f i g 2 _ 4t e x t u r es y n t h e s i sr e s u l tu s i n gw e i l e v o ya l g o r i t h m 2 4 3 多种子快速纹理合成算法 在w l e i l e v o y 算法的基础上，徐晓刚在他的博士后出站论文中提出了多种 子快速纹理合成算法【稻1 ，与w e i l e v o y 方法相比，具有如下不同： 1 采用多个种子在合成纹理图象中采用多个种子进行预填充。多种子方 法可以减少计算匹配点的数量，实现加速效果，同时，从每个种子点开始往邻 域扩充，使算法实现并行计算。 2 采用多种形状的种子种子的形状可以根据纹理的不同，采用点、线、 矩形等多种形状。多种种子的选择可以使纹理合成方法能够应用到更大的范 围。 3 采用螺旋线状搜索与w 昏l e v o y 算法的扫描线顺序搜索不同，如图2 5 所示采用螺旋线状搜索，搜索的初始位置为上一点的匹配位置，然后向邻域扩 张。螺旋线状搜索方法可以大大提高合成的速度。 4 多种顺序合成纹理合成的顺序可以根据纹理不同情况进行选择，一般 对线状的种子沿种子线的方向进行合成；其它的可以选种子邻域的任一点开 始，按螺旋线状顺序进行合成；也可以从种子邻域的任一点开始按其他顺序合 成。 哈尔滨理t 大学f t 学硕二 学位论文 _ i _ ji 1r 图2 5 螺旋线状搜索示意图 f i g 2 5s c h e m a t i cd i a g r a mo fs p i r a ll i n es e a r c h 该算法可以简述如下：首先在原样图上进行反复采样，以随机或顺序方式 把种子填到合成图中。然后从合成纹理画面上预置种子位置开始，按照一定顺 序，在样图中查找匹配点，每次合成一个点。具体是使匹配窗的中心与合成像 素点重合，在样图上按螺旋线状顺序移动匹配窗，计算两匹配窗内图像的误 差，若误差小于所设的门限，即把它写入合成图中，如此反复直至填满合成 图。 该算法由于采用了多种子预填充技术，大大加快了纹理合成的速度，且对 于某些纹理，如果设置了合适的阈值大小，可以做到合成速度基本与样图大小 无关。但是，由于需要人工设置阈值，且设置合适的阈值非常困难，使纹理合 成的时会出现一些偏颇和不便。 2 5 基于块的纹理合成方法分析 基于像素的纹理合成具有一定的局限性，由于是一次一个点的合成，在 合成过程中，实际上相当一部分后续点的选择已由已合成点决定了。这样许多 点在查找上浪费了时间。继在i c c v 9 9 上发表影响较大的非参数采样的纹理合 成后，e f r o s 在2 0 0 1 年的s i g g r a p h 会议上提出了一种基于块拼贴的纹理合成算 法【4 7 】，比起以往的算法，该算法在纹理合成的时间，合成纹理的视觉效果方面 都得到了很大的提高，避免了以往的算法容易引起的模糊，纹元错位严重等问 题。 2 5 1 基本思想 在基于块的纹理合成以像素块为基本单位，每次在输出图像中合成一个 块，直至输出图像被填满为止。每次进行块合成时，根据马尔可夫邻域匹配的 准则，首先先在输出图像中提取对应块的邻域，以该邻域为模板在输入样图中 哈尔滨理t 大学工学硕十学位论文 所有可能的位置不断进行比较，找到误差足够小的块，并将该图像块拷贝到输 出图像中。 与基于像素的合成