（信号与信息处理专业论文）纹理合成技术的研究.pdf

! 望壁兰垫查叁兰堡! ：兰垡兰茎建翼叠堕至盖娃蛔l 摘要 纹理合成是当前计算机图形学、计算机视觉和图像处理领域的研究热点之 一。本文对基于样圈的二维纹理合成技术进行了研究，提出了一些新的观点和算 法。 本文首先介绍了基于像素点和基于块抽样纹理合成的主要算法和应用，并在 a s h i k h m in 算法的基础上提出了一种改进的基于像素点的纹理合成算法，利用温 度函数有效的降低了噪声点对输出纹理的影响。作为进一步的研究，本文提出一 种新颖的参数可调的纹理混合方法，把搜索范围限制在当前点的邻域及其影子点 集合中，在保证纹元完整的基础上有效地提高了纹理的混合基频，通过对尺度闽 j 值和比例系数的调整灵活地控制纹理的混合程度和混合比例，对于大多数种类的 纹理样本，均可以混合出参数不同的多幅纹元完整、连续性好的输出纹理。最后 本文提出一神新的基于邻域子块相关的快速纹理合成方法，在抽样过程中利用邻 域子块的相关性，把搜索范围限制在当前块的邻域，与基于块抽样的纹理合成算 法相比，时间复杂度从o ( m n ) 降至o ( m ) ，并且对于一幅输入纹理合成不同大 小的输出纹理，只需对输入纹理进行一次预处理。在纹理块拼贴过程中采用基于 像素点合成算法，利用模拟退火理论有效的合成出清晰、连续的纹理边界。对于 广泛存在的真实纹理，该算法能合成出视觉效果上更优的输出纹理。 本文算法在计算机动画，影视特技，虚拟现实和数据压缩等方面具有广泛的 应用前景。 【关键词l 纹理合成，m r f 模型，纹理混台，邻域子块块抽样，最近邻搜索 中国科学技术大学硕士学位论文纹理合成技术的研究 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 ft h eh o n e s ta r e a si n c o m p u t e rg r a p h i c s ，c o m p u t e r v i s i o na n di m a g ep r o c e s s i n gf i e l d s i nt h i s p a p e r ，w eb r i n gf o r w a r ds e v e r a ln e w o p i n i o n sa n da l g o r i t h m so n t e x t u r es y n t h e s i s f i r s t l y ，w ei n t r o d u c et h ed e v e l o p m e n t i nt h ea r e ao f p i x e l - b a s e da n d p a t c h b a s e d t e x t u r e s y n t h e s i s ，s e c o n d l y ，w ep r e s e n ta na d v a n c e dp i e x l - b a s e dt e x t u r es y n t h e s i s m e t h o db a s e do na s h i k h m i n sa l g o r i t h m ，w h i c hd e c r e a s e st h ea f f e c to fn o i s ep i x e l s u s i n gs i m u l a t e da n n e a l i n g t h i r d l y ，w ep r e s e n tan e w t e x t u r em i x i n gm e t h o du s i n g a d j u s t a b l ep a r a m e t e r s ，w h i c hl i m i t st h es e a r c h i n gs p a c et ot h en e i 【g h b o r h o o do ft h e c u r r e n tp i x e la n dt h e i rs h a d o wp i x e l s t h i sa p p r o a c hc a ni n c r e a s em i x i n gf r e q u e n c y e f f e c t i v e l yo n t h eb a s i so f g u a r a n t e e i n gt h ei n t e g r a l i t yo f t e x t u r ec e l l s 。s c a l et h r e s h o l d v a l u ea n dr a t i of a c t o rc a nb eu s e dt oc o n t r o lm i x i n gf r e q u e n c ya n dm i x i n gr a t e f o r m o s tt e x t u r e s ，t h em e t h o dc a no b t a i ns e v e r a ls a t i s f a c t o r yo u t p u tt e x t u r e sw i t hd i f f e r e n t p a r a m e t e r s f i n a l l y , w ep r e s e n t s an e wa p p r o a c hf o rt e x t u r e s y n t h e s i sb a s e do n c o h e r e n c eo f n e i g h b o r i n gs u b p a t c h e s i nt h ec o u r s eo fs y n t h e s i st h ea l g o r i t h mu s e s n e i g h b o r i n gs u b - p a t c h e s c o h e r e n c e ，l i m i t st h es e a r c h i n gs p a c et ot h en e i 【g h b o r h o o do f t h ec u r r e n tp a t c h c o m p a r i n gw i t ht h ea l g o r i t h mo ft e x t u r es y n t h e s i sb yp a t c h - b a s e d s a m p l i n g ，t h et i m ec o m p l e x i t yi sr e d u c e df r o mo ( m x n ) t oo ( m ) i no r d e rt og e t s y n t h e s i z e d t e x t u r e sw i t hd i f f e r e n t s i z e ，t h e i n p u t t e x t u r e o n l y n e e d st ob e p r e p r o c e s s e do n c e i nt h ec o u r s eo fp a t c hb l e n d i n gw eu s es i m u l a t e da n n e a l i n gt o p r o d u c t c o n t i n u o u st e x t u r e b o r d e r l i n e e x p e r i m e n t a l r e s u l t si n d i c a t et h a t f o r e x t e n s i v e l ye x i s t e dr e a lt e x t u r e s ，c o h e r e n c eo fs u b - p a t c h e sc a ne x p r e s st h et e x t u r a l c h a r a c t e r i s t i cb e t t e ra n dt h ea l g o r i t h mc a ns y n t h e s i z em o r e s a t i s f a c t o r yo u t p u tt e x t u r e o nt h ev i s u a le f f e c t a l lt h e s em e t h o d sh a v e g r e a tp o t e n t i a l i n m a n ya p p l i c a t i o n s ，e s p e c i a l l y i n c o m p u t e ra n i m a t i o n ，s p e c i a le f f e c t s ，v i r t u a lr e a l i t ya n ds oo n 【k e y w o r d s 】t e x t u r es y n t h e s i s ，m r fm o d e l ，t e x t u r em i x i n g ，s u b - p a t c h ，p a t c h s a m p l i n g ，n e a r e s t n e i g h b o rs e a r c h i n g i l ，十r i f , 中国科学技术大学硕士学位论文 纹理合成技术的研究 第一章绪论 在过去的十年中基于图像的绘制技术得到了长足的发展。它在真实的世界中进行采样， 并用得到的图像合成逼真的场景，避免了几何绘制技术中通过几何建模重建真实世界的繁 琐，并且表现了几何模型无法体现的细节。在最近几年，真实感技术一直是国际的研究热点， 而在其中占重要地位的纹理合成技术，也获得了重大的突破，引起了各国研究人员的j “泛关 注。 在计算机生成的物体上模拟纹理细节主要有两个方法。一个是_ = j 多边形或其他几何原语 对表面细节进行建模，但是当虚拟环境对表面细节要求比较高的时候，这种方法很不实用： 另一个是把图像映射到对象的表面上，这种技术称作纹理映射( t e x t u r em o p p i n g ) 。用于纹 理映射的图形通常是矩形，称为纹理图( t e x t u r em a p ) 或纹理( t e x t u r e ) 纹理可以模拟各种 表面属性如颜色、反射( r e f l e c t i o n ) 、透明等。自c a t m u l l “在二十世纪七十年代首次采 用纹理映射技术模拟物体表面的纹理细节以来，纹理映射技术得到了广泛的研究和应用。 1 i 纹理和纹理合成概述 1 1 i 纹理的定义 在计算机图形学的领域中，纹理的概念非常广泛，包含任何图案的图像都可以称之为纹 理。但是，在计算机视觉和图像处理领域中，更倾向于纹理的一种狭义定义。在w e b s t e r s 词典中是这样定义纹理的： t e x t u r e ，n o u n ( 1 ) s o m e t h i n gc o m p o s e do f c l o s e l yi n t e r w o v e ne l e m e n t s ；s p e c i f i c a l l yaw o v e nc l o t h ( 2 ) t h es t r u c t u r ef o r m e db yt h et h r e a d so f af a b r i c 简而言之，就是指纹理是有着重复部分的图像。大多数自然物体的表面都包含有重复的 元素，使得狭义的定义己经足以描述物体表面的属性，因此在纹理合成这个领域，我们所 说的纹理都指的是狭义定义。 目前纹理主要通过从现实世界直接采样得到( 例如，通过数码相机直接拍摄获取) ，现 实世界中物体的多样性决定了纹理形式的多种多样。目前国际上流行按照纹理特征分布的不 同把纹理分为三类： 1 结构性纹理，含有保持纹理局部性的最小纹理块，整个纹理可以由一系列的纹理块 及其摆放规则决定，例如砖墙、地板等。 2 随机性纹理，没有明确的纹理块，例如沙粒等。 3 半结构性纹理，既有结构性又有随机性的纹理，从自然界中得到的纹理很多都属于 这一类。 中国科学技术大学硕士学位论文 纹理合成技术的研究 图l1 ( a ) 结构性纹理 ( b ) 随机性纹理 ( c ) 半结构性纹理 不同于一般的图像纹理含有两个特殊的属性，称之为局部性( 1 0 c a l i t y ) 和平稳性 ( s t a t i o n a r i t y ) 。局部性是指纹理中的一个像素仅仅由其邻域中的像素决定，例如图1 2 中黑 色的方框就表示邻域的范围：平稳性是指当两个黑色的方框在纹理中任意移动的时候，方框 中的内容在不断的变化。但是又保持一定的相似性。 1 1 2 纹理合成技术概述 图12 纹理和一股图像的比较 在计算机图形学中，纹理映射技术取得了很大的成功但也存在三个严重的问题：第一， 纹理来源单一。目前的纹理主要通过手工绘制或者扫描照片得到。手工绘制的图像可以满足 艺术上的需要，但是缺乏真实感：而照片作为纹理，大小受限制通常不能覆盖整个物体的 表面。此时，简单的粘贴在视觉上会产生重复引起人造的痕迹。第二，从纹理空间到三维 空间没有自然的映射关系，因而映射时会产生严熏的变形。第三，纹理映射占用大量的内存 和带宽。 纹理合成技术的产生正是为了解决以上问题。作为一种新的获取纹理的方法，合成后的 纹理可以是任意大小，相似而不重复。通过适当的处理边界条件，纹理合成还能够生成可粘 贴的图像。 作为近几年来的研究热点，纹理合成技术得到了飞速的发展。一般来说，纹理合成分为 两个步骤：模拟( m o d e l i n g ) 和抽样( s a m p l i n g ) 。模拟是由给定的原始纹理去估计这个随 机过程，描述这个纹理的特性。抽样就是在构建的模型上采用某种抽样方法来生成目标纹理。 根据其实现的原理可以分为基于马科夫随机场( m a r k o vr a n d o mf i e l d ，m r f ) 的纹理合成和 基于特征匹配( f e a t u r em a t c h i n g ) 的纹理合成。m r f 己经被证明能够适用于大多数的纹理， 2 中国科学技术大学硕 ：学位论文纹理合成技术的研究 以之为基础的算法具有一般性，而且能够得到很好的合成效果。因此，以m r f 为基础的纹理 合成算法一直是该领域的一个研究热点，各国研究人员先后提出了很多种方法，先后出现了 基于像素点的纹理合成【1 ，5 ，o 和基于块抽样的纹理合成口3 ，1 - 1 6 1 ”。基于特征匹配的方法则把 纹理看成一系列特征的集合，通过在样本图中匹配特征的方法生成新的纹理。 纹理合成技术被广泛地应用在计算机图形学，数字图像处理以及计算机视觉等领域。 具体如下： 1 绘制：在绘制中，纹理被用于模仿真实物体的表面细节，它可以改变物体表面的颜 色，法向量甚至可以改变物体表面的几何特性。通过纹理合成技术，可以避免因纹理大小受 限而产生的缝隙，重复等问题，极大的增强了虚拟环境的真实感。 2 动画：计算机动画通常包含两个部分：确定的事件和随机的运动。确定的事件是指像 打开一扇门或者拾起一个物体等没有随机性的动作，而随机运动主要包括动画背景的重复运 动，像海浪，烟雾或者火焰等。这类在时问和空间上都有不确定的运动，很难使用基于物理 建横的传统技术来进行绘制，因此一种称为视频纹理的纹理合成技术被提出用来描述和 绘制该类随机运动。它最大的优点是仅仅使用一种算法，就可以合成出多种不同的随机性运 动。 3 压缩：用来描述自然场景的图像经常含有大量的纹理区域，例如，夫片的草地森 林，沙滩等。该类区域拥有明显的高频信息因此常用的压缩算法很难将其有效的压缩。但 是，使用纹理合成技术则可以解决该类问题。在压缩阶段，手j ：勾勒出纹理区域，经过处理， 使用- - j , 块纹理来代表该区域：在解压缩阶段使用纹理合成技术，在小块纹理中进行采样， 最终合成出原有的纹理区域。简而言之，就是使用采样纹理去代替原有的纹理区域。己达到 压缩的目的。 4 修复和编辑：在实际生活中，有的照片，胶卷会因为保存的时间过长而出现裂纹和 瑕疵，或者有时候，想要除去照片上的一些物体，这时候就需要纹理合成技术对这些照片或 者胶卷进行修复或者编辑。修复的时候，在正确的区域进行采样，在破损的区域进行受限制 的纹理合成( c o n s t r a i nt e x t u r es y n t h e s i s ) ，即保证合成后部分能够与周围的区域无缝的 衔接上：对照片的编辑在原理上与修复相同，相当于先删除掉要编辑的物体，然后再进行修 复。 5 计算机视觉：纹理合成技术还大量的应用在计算机视觉的分割识别和归类等】：作 中。 1 1 3 纹理合成存在的问题 纹理合成是当前计算机图形学和计算机视觉研究的热点，有许多研究者进行了富有创造 性的研究工作。但是目前纹理合成主要存在以下的问题： 1 仍然没有一种可以适用普遍纹理的方法，现有大部分基于块抽样的算法都会或多或少引 起纹理块边界的模糊或者不连续。 2 纹理合成大多数是基于单样图的，为了扩大纹理的来源，有些研究者提出多样图的纹理 3 主里型兰垫查查堂堡圭兰垡堡塞 竺堡鱼堕垫查竺! ! 塑 合成算法。但是现有的多样图纹理合成方法合成的效果缺乏自然性，并且缺少对输出纹理的 灵活控制。 3 算法的复杂性和耗时性上有待提高。 1 2 本文的主要工作 本文阐述了作者在纹理合成领域的部分观点，并提出了几种新型的算法。其贡献表现在 以下方面： 在第二章介绍了纹理合成的两类实现方法，基于像素点的合成和基于块抽样的合成，并 且介绍了这两类方法的主要应用。 在第三章提出了一种基于a s h i k h m i n 算法的改进的纹理合成方法，通过k 近邻搜索适度 的扩大了候选邻域并且采用多分辨率分析和模拟遇火的方法，可以产生较a s h i k h m i n 算法更优的纹理结果。 在第四章基于前一章的方法提出一种多样图纹理台成算法，通过预处理，在混合过程中 利用邻域的相关性，把搜索范围限制在当前点的邻域及其影子点集台中，在保证纹元完 整的基础上有效地提高了纹理的混合基频，通过对尺度闽值和比例系数的调整灵活地控 制纹理的混合程度和混合比例。 在第五章提出一种新的基丁邻域子块相关的快速纹理台成方法，在纹理抽样过程中与基 于块抽样的纹理合成算法相比，时间复杂度从o ( m j v ) 降至d ( 彳) ，在纹理块拼贴的 过程中利用第三章所述算法，构造温度图逐次对重叠区域进行基于点合成的纹理修复 输出纹理的视觉连续性好，并且对于一幅输入纹理合成不同大小的输出纹理，只需对输 入纹理进行一次预处理。 在第六章中总结本文的成果，提出了在未来工作中需要进一步研究的问题。 4 中国科学技术大学硕士学位论文 纹理台成技术的研究 第二章纹理合成的典型算法介绍 纹理合成是当前计算机视觉、计算机图形学、图像处理等多个领域的研究热点之一，在 图像的m p e g 压缩编码，图像修复，基于图像类推的滤波器设计等方面都有广泛的应用， 并且随着算法速度的提高，在互联网上的绘图、动画和网站的设计中也越来越多的用到了纹 理合成技术。近年来先后出现了多种纹理合成算法，其中以m a r k o v 场为模型的无参纹理合 成1 4 1 处于优势，并在此基础上先后出现了基于像素点【1 ，5 6 1 的合成和基于块抽样f 2 , 3 , 1 1 , 1 6 】的合成 等。本章将主要介绍一些具有代表性的算法及其应用。 2 i 基于像素点的纹理合成 早期的纹理合成算法都是基于单个像素点的它充分利用纹理的马尔科夫场( m r f ) 模型认为纹理中的每一个像素点的灰度仅与其邻域范围内的点有关，而与其它的点没有关 系。根据这种假设，模拟出当前点与邻域点的函数关系式，进而采用抽样算法逐点的合成出 目标纹理。在对邻域关系的模拟中先后出现了带参数的m a r k o v 场模型和无参的m a r k o v 场 模型。带参数m w k o v 场的联合概率n 中存在若干参数，这些参数控制着纹理的各种特征， 比如纹理的横竖走向纹理的同性异性等。通过对原始纹理中的所有点代入此模型估计其各 参数值从而确定了此纹理所对应的联合概率兀进而可以合成出类似的纹理。但是此种 方法的缺点是运算量巨大，适用面窄，仅对二值纹理有较好的结果，渐渐的以无参t a r k o v 场模型的纹理合成算法成为了主流。这种算法不需要对各种纹理参数进行估计，只需要设计 出一种合理的邻域模型，在合成过程中利用模型自动的生成目标纹理算法鲁棒性强，并且 对丁大部分的彩色纹理都适用。 2 1 1 r p a g e t 的无参m r f 算法 r p a g e t 采用了无参的m a r k o v 场模型对纹理进行合成，他通过对目标纹理定义局部条 件概率密度函数( l c p d f ) ，利用g i b b s 抽样来刻画纹理的特征。对于幅m 行n 列的纹理 其中任意一个像素点5 表示为z 。取值范围工。ca ( 其中 是图像中的灰度级) 丽 五2 的概率仅依靠于它的邻域点z 的取值。l c p d f 的表示如下： p ( 置2 t t = ，r s ) = p ( 矗f 耳- r 、) ( 2 1 ) 其中。为像素点s 的邻域，它是以s 点为中心的正方形区域。区域中各点与中心点的 关系随着距离的增大逐渐减弱。 对于输入纹理l 中的任意邻域均展成一维向量q ，邻域中心点j l ，将待合成点x s 及其邻域展成向量，则t 的m a r k o v 场条件概率密度函数定义如下： 5 中国科学技术大学硕士学位论文 纹理台成技术的研究 mh ：圣竺竺! ：壶竺竺：兰 协。， p ( 一i 一，m ) = 型、一 ( 2 2 ) 州一朋。e x p 【一麦卢训训】 对于t 的所有可能取值代入( 2 2 ) 式，根据g i b b s 抽样策略选取最佳灰度值赋给待合 成点。算法按照自上而下，自左而右的顺序逐点进行合成。该算法的主要缺点是运算量大， 对每一个待合成点都要进行复杂的概率密度的计算与比较。 2 1 2e f r o s 的无参抽样算法 e f r o s 的算法“1 与上一小节算法类似，由一个种子点开始，在合成输出纹理l 。的过程 中，次次的对目标点周围的邻域与输入纹理l 。中韵所有邻域进行比较，对于当前待合成 的点p 。，和它的邻域( p o ) 对输入纹理中的每一个点p 二都构造一个近似的条件概率密度 函数p ( p k 国( 儿，) ) 比较函数采用高斯权重的归一化均方差( s s d ) 目标点为具有最大 条件概率密度的输入点以。此算法对输入纹理进行穷尽搜索，因此非常耗时，并且容易在 搜索空间陷入局部极小，造成输出纹理的循环复制或者断裂。 2 1 3w l 的t s v q 算法 w e i 和l e v o y 对e f r o s 的无参抽样算法进行了改进鸭在算法速度和纹理质量上都得到 了提高。如图2 】所示苜先定义一个初始输出纹理模板( b 图) 。通过邻域匹配的方法，由 上至。f ，由左至右逐点合成。邻域采用l 型结构，使得当前点的邻域都是已经生成的像素 点t 确保了邻域的因果性。对于每一个当前点( c 图) ，先获取其l 形邻域点集，然后与输 入绞理中的每一个l 形邻域点集进行比较( a 图) ，比较采用简单的均方差最小算法，撮后 将得到的最优点复制到当前的像素点。 呼：n e i g h b o r h o o dn 令一 ( a 辘天绞理( b ) 拐始缓理壤块t c ) 舍成过羲审装一夺当蘸像素赢( d ) 输出绽璞 掰2 1 按扫描线颓牟告成纹理 6 中国科学技术大学硕 学位论文 纹理合成技术的研究 为了减小邻域的宽度，加快算法的速度，进一步采用多分辨率( m u l t i r e s o l u t i o n ) 的方 法，使用简单的高斯低通滤波器，同时将输入纹理和输出纹理模块滤波成由高至低不同分辨 率的金字塔结构，低分辨率的图像为纹理的框架结构，包含了低频信息；高分辨率的图像为 纹理的细节结构，包含了高频信息。合成的过程类似于绘画，首先从低分辨率的图像开始合 成，构建出纹理的框架，然后在此基础上，运用低频的信息指导高分辨率图像的合成，最后 得到最终的目标纹理。如图2 2 所示，其中l 层为高分辨率层( 尚未合成完) ，l + i 层为相对的 低分辨率层( 合成完毕) ，对于待合成的像素点x ，箕邻域不仅包括l 层的0 点，还包括l + l 层 的y 点和q 点既利用了邻域的信息又利用了相应的低频信息从而能够合成出质量更优的输 出纹理。 x 口 图2 2 多分辨率金字塔结构 为了加速邻域搜索，采用矢量量化技术t s v o ( t r e es 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 ) ，首 先将原始纹理按照邻域矢量分成码树，每一个树叶由一个邻域矢量或者距离相近的几个矢量 构成。建立码树后对纹理的搜索就变成了对二叉树的搜索。假设训练矢量数目为r l ，在纹 理中所有矢量都是树中一个叶子节点并且建立满二叉树的情况下，合成一个点进行搜索的时 间复杂度为o ( 1 0 9 ，斗) ，而此前的时间复杂度为0 ( n ) 。而且，通过设定树的深度，把叶子 节点上的矢量集合用一个最接近该叶子节点的中心的矢量表示，又可以太大减少搜索量。 2 1 4a s h i k h m i n 的自然纹理合成算法 由于w l 的算法对于一大类灰度丰富的自然纹理的合成效果欠佳，a s h i k h m i n 在此基础上 提出了对于自然纹理的合成算法【1 1 。由于自然纹理常常包括形状各异的不同类型的物体，比 如草地土的鲜花等，简单的均方差算法不能充分模仿人类的视觉特性，从而产生了模糊效果。 a s h i k h m i r t 在邻域搜索中认为当前点的邻域。也就是已生成的像素点在原始纹理中的邻域模 型更应该成为当前点的候选邻域。 7 杖删i 成技术n 勺允 ( a ) ( b ) 删2 3a s h l k h m i n 算法的毕本洫稳手n 缺粥 如图2 3 ( a ) 所示对丁输纹理的当前点，首先在原始纹理中找剑h 邻域再点的处， 然肝 据这o e 点带输出纹舜中的对应似蓖，构造出系列邻域其中邻域的再个中心点( 印 图a 中的黑色点) 都认为延输i | j 纹理当前点的候选点集，最终j 前点采 h 定的选抒j 法“ 候选点集巾选取。该尊法人人l t 竹，时问，不需要构造啄始纹理的码树，而h 候选点集较小， # e 时埔。缺点煺易产 i - n n 的纹理块从输出纹理的椠地打开始一亢向t - 近续亢剑i i 地料， 如图( b ) 所示。 h ) 输入技艘( h ) 1 ：1 怀喇r ) 输纹州 i 埘2 4 埔十h 户挖制的r l 然纹理介啦 在上述基本算法的基础上，a s h i k h m i n 还提出了纂丁控制的纹理合成捭法能够根据用 户的意愿生成些特殊的效震。如图2 4 所示，首先增加个h 标削( b ) 作为个输入对豫。 目标图描述了h j 户希螺合成的纹理图像所节现的概貌，它仅仅勾勒出合成图中一般的特征， 鲤1 y 部分仍南合i 垃算法来进 r “填充”。目标图的获得可以是任意的：可以人工绘制，可以 s 中国科学技术大挚硕士学位论文纹理合成技术的研究 是一幅照片，还可以是计算机生成的渲染图。然后与基本算法一样选择待选点，计算匹配点； 分别在样图和目标图中取矩形邻域的上下部分l 邻域像素，计算厶误差。取误差最小者作为 匹配点复制到合成图中。因为目标图像中有些用户留下的空白，所咀只考虑那些非空白的有 效的像素进行计算。 a s h i k h m i n 算法非常直观、简单，在速度方面该算法比i l 的算法快得多，而算法复杂 度却只与w l 基本算法大致相同。 其存在的问题有： 1 一些结构性较强的纹理，合成的质量不如札算法。主要原因是由于把搜索范围限制 在当前点的邻域对许多边界比较明显的结构性纹理，此相关性度量范围相对过小。 2 不能处理诸如云、波纹等平滑度较强的纹理。 2 1 5 徐晓刚多种子快速合成算法 在w l 算法和e f r o s 算法的基础上，徐晓剐提出了一种新的多种子快速纹理合成算法“。 该算法的主要思想有： 1 在纹理图像中采用多个种子进行预处理。多种子方法可以减少计算匹配点的数量， 实现加速效果。种子可以选取为单一像紊点，也可以选取为具有某种形状的像素点集合。 2 采用多种形状的种子。根据纹理的不同种子的形状可以采用点，线。矩形等多种 形状。多种种子的选择可以使纹理合成方法能够应用到更犬的范围。 3 采用螺旋线状搜索。搜索的初始位置为上一点的匹配位置，然后向邻域扩张。实验 发现，当前点的匹配点分布在邻点匹配点邻域的概率较大。因此在后续点的搜索过程中 从前一点的匹配点的当前位置开始，由其邻域向外傲螺旋线状搜索，若匹配误差小于设定的 闽值，则搜索终l e ，把该点写至台成图中；若遍历了样图仍来找到满足误差要求的点，则选 取其中误差最小的点写入合成图中，采用此搜索方式可以大大提高合成速度。 4 多种顺序合成纹理。可以根据纹理不同情况进行合成顺序的选择，一般对线状的种 子沿种子线的方向进行合成；其它的可以选种子邻域的任一点开始，按螺旋线状顺序进行合 成：也可以从种子邻域的任一点开始按其他顺序合成。 该算法采用多种子预填充以及螺旋线状匹配搜索，大大加快了纹理合成速度。对于某些 纹理，设置合适的蜩值大小，可以做到合成速度基本上与样图的大小无关。此外，该方法将 纹理合成的范围从一般纹理推广到有方向性的纹理，使纹理合成算法更具有一般性。其存在 的问题是： 1 需要人工设置更多的合成参数，不利于用户的操作。 2 不同纹理，种子的大小和种子之间的间隔大小的设置往往不同，否则将影响合成质 量和合成速度。 3 合适的搜索阈值非常困难，而且不同的纹理需要设置不同的阈值，即使针对某一种 纹理，也需要多次试探后才能粗略确定。 9 中国科学技术大学硕士学位论文 纹理合成技术的研究 2 2 基于块抽样的纹理合成 纹理映射是一种将纹理图像映射到三维物体表面的技术，虽然它取得了巨大的成功，但 仍然面对两个主要问题：首先，原始纹理尺寸太小，不能覆盖物体的整个表面，通过纹理的 重复拼贴会造成视觉上的不连续；其次，纹理映射对存储容量和带宽都要求很高，并且需耍 达到实时处理的要求。基于像素点的纹理合成方法虽然可以由一个给定尺寸的输入纹理合成 出理论上任意大小的输出纹理，但是由于是逐点计算，耗时性大：并且对一些纹理结构稀疏 的图像不能准确描述，如果一味扩大邻域范围会在合成时间上带来成倍的增长。在这种情况 f ，基于纹理块的合成算法被提出并逐渐完善。x u 等人首先提出了混沌拼贴( c h a o sm o s a i c ) 的方法，把输入纹理划分为若干小块，然后随机的放置到输出纹理中，在纹理块边缘采用某 种算法进行混合。在此基础上，l l i a n g 等人提出了基于块抽样的算法，将m r f 模型推广到纹 理块的范畴，这种方法可以达到实时的效果并且对绝大多数的纹理都适用。为以后基于块抽 样纹理合成算法的发展打下了基础。本小节我们将介绍几种有代表性的基于块抽样的纹理合 成算法。 2 2 1x u 的混沌拼贴算法 x u 等人j 首先将样本纹理进行重复映射( t i l i n g ) ，然后通过混沌变换得到合成纹理， 使样本纹理中的局部特征具有本质规律但视觉随机的分布。为达到这个目的，他使用了确定 性混沌领域的一个递归系统。所谓确定性混沌，是指由所发生的历史唯一决定将来行为的非 线性动态系统产生的无秩序和不规则状态。具体采用的是a r n o l d 提出的c a tm a p 。它将( 由 重复映射得到的) 图像t 映射到自身，使得其中的点( x 。，y7 ) 通过公式( 2 3 ) 方式映射到 点( x i + ly “) ，其中l 指递归次数，m 指合成纹理的长宽： z “= f x 。+ y 7 1 r o o d m ：( x 。+ 2 y 1 ) m o d 小 “ 为了保持样本纹理的局部相关特性，x u 混沌变换的对象是纹理块而非像素。如图2 5 所 示，算法如下： 1 将样本纹理重复映射得到初步结果。 2 结果图中随机选择纹理块( 红色高亮显示) ，通过公式( 2 6 ) 表达的混沌变换将它 绘制在图中的随机位置( 绿色高亮显示) 。 3 平滑边界。 l o 生里型兰垫查盔兰堡主兰垡堕壅 墼里鱼壁垫查箜堑壅 图2 5 混沌拼贴方法 该方法对随机纹理产生了非常好的合成结果，而且速度也很快，但是在合成带有结构性 的纹理时，会产生比较明显的接缝。 2 2 2l l i a n g 的基于块抽样的算法 l l i g 将m r f 邻域模型推广到块的结构t 2 1 ，也就是在纹理合成过程中，每一次合成是 一次纹理小块的操作而不是前述的一个像素点的操作。对于输出纹理中的一个待合成的块， 首先定义其邻域模型，按照此邻域，在原始输入纹理搜索最近似邻域，然后将所得块和其邻 域一并复制到输出纹理中，对于重合的区域采取一定的方法进行混合，以达到视觉上的连续 性。 i c l ( d ) 图2 6 基于块抽样的纹理台成过程 合成过程按照一定顺序，由下至上，由左至右依次进行，如图2 6 ( a ) ，对于已生成的 区域具有宽度为m 名的边界z 乞。在原始纹理中找到与之匹配的块的集合甲日，集台中的每 一个块尽w ) ( 坐标标示了块的左上角) 都具有宽度为w e 的边界，边界的匹配定义如下： 甲日= 且w ) l a ( e , ( l ，硪) 1 矗 最终，最后一行的最小值就是最小错误路径的终点，以此为起点逆向跟踪即可得到最小 错误路径。这个方法称为最小错误边界切割算法( m e b c ) 。 完整的图像缝合算法描述如下： 1 对输出纹理进行逐行的合成。 2 当前待合成的块在输入纹理中寻找所有小于邻域闽值的纹理块，从中随机抽选一 个块复制到输出纹理中。 3 在已合成纹理和新选择块的重叠区域计算最小错误边界，沿着此边界将新纹理块拼 接到已合成纹理中。 1 3 中国科学技术大学硕士学位论文纹理合成技术的研究 e i l爿i 钆 e e ：0 h o ：+ m i n e 1 1 e l ：，e i i l 图2 9 最小错误边界切割算法示意 该算法的耗时性与ll i a n g 的算法相当，在块拼贴方面克服了前者算法引入的模糊效果 但是最小错误边界方法往往会引入局部性的边界不匹配。 2 2 4 基于图切削的纹理算法 该算法“”在纹理块的选择上与前述的两种方法大体类似，首先从输入纹理中复制一个规 则的矩形块到输出纹理中然后在这个矩形块中切割出一个不规则的纹理块最终拼接到已台 成区域中。其中不规则纹理块的选取采用了图切割的方法。 图2 1 0 基于图切割的纹理合成过程 鸯了游强谂串谣割舞法庭麓鹫纹理会成串来，蓄先定义蘸叠区蠛鹣区配菠爱鼗。撩麓擎 蛇方法裁是聚滕二除藏数比较。镁定黛s ) 张联砖分爨代寝s 点在强块葶曩凝姨上的色嶷壤， 定义两个邻接点s 和t 的瓤配魔晒数如下； m ( s ，矗蠢，嚣) = 錾( 砖一。a 髓埔l 鼻) 一崩l ( 2 9 ) “ 中国科学技术大学硕士学位论文 纹理合成技术的研究 假定一些纹理块已经被复制到输出纹理中，现在需要复制一个新块到多个纹理块相交的 区域，由于在先前的计算中得到了旧块间缝隙上各像素对的代价，因此利用这些代价对新块 应用图切割算法从而决定新块中的哪些像素可以覆盖旧的缝隙，形成代价更小的新的缝隙。 比较e f r o s 的动态规划算法由于它是非记忆性的，不保存旧块间缝隙的代价，因此不能处 理这种多纹理块相交的复杂情况。 图21 1 在旧切割存在的情况下寻找最优新的切割 图2 1 1 展示了图切割算法的主要思想，绿线代表旧缝隙，红线代表新缝隙。假设a 代表 先前的所有旧块，b 代表将要复制的新块，爿代表旧块中s 点的所来自的块。对旧块像素间 的每一个缝隙，设置一个介予像素对之间的缝隙点( $ e s mn o d e ) ，并且将这些缝隙点都以 弧线连接到新块b 上，这些弧线的代价就是这个缝隙的匹配代价。如图所示，在像素点1 ，4 间设置一个缝隙点s ，并且将该点连接到8 上，那么此点的代价为m ( 1 ，4 ，a ，a 。) ，将像素点i 到墨的弧线的代价设为m ( 1 ，4 ，4 ，曰) ，弧线s 到像紊点4 的代价为m ( 1 ，4 ，b ， ) 。如果缝 隙点和新块间的弧线被切割则表示旧的缝隙在输出纹理中不变；如果该弧线没有被切割，则 袭示旧的缝隙被新像素覆盏并且旧缝隙的代价不被计入最终代价：如果缝隙点和像素点间的 任一个弧线被切割，则表示一个新的缝隙被放置在旧缝隙的位置上并且新的缝隙代价( 视哪 一条弧线被切割) 被计入最终代价。具体的切割算法以图论中的最大流最小切割算法为基础。 该算法可以产生出边界拟合非常好的输出纹理，但是缺点是算法太复杂，比较耗时。 2 3 纹理合成的应用 纹理合成技术在计舞机视堂、计算机图形学和图像处理领域有着广泛的成用前景n 随羲 该领域技零研究的逐步涕入，越来越多的算法旋提出采，在岔成速度翱合成艨量上不断得剿 挺赛，放藤程镬对该技零静残耀越来越广泛，持统上羲觳誉太霹艉靛一鳌瘦用逐渎交褥戏为 可能。 2 3 1 绞壤修复 纹理修复悬纹理合成算_ 虫的一种擐宣斌的应用，也叫做有约束纹理台成( c o n s t r a i n e d t e x t u r es y n t h e s i s ) ，它熬对纹壤上的蜉建、演濑、杂物等的覆羲或修笈，娃凝褥圜静纹理效 1 5 尘里型兰丝查苎兰! ! ! ! ! ! ：兰竺堡兰 塑竺! 苎丝苎! ! ! 堕 累。纹娜修复的要求是只对h 标耳域进 j 合成，而对j ：其周闱的像素不进ij ：政动因此邻域 摸刊年| 台成轨迹都“相心的调1 ，并且基本上使【 j 金字塔滤波等加速算法。 2 3 2 纹理传输 州2 1 2 纹理体复 纹理传输_ ；l 不同于纹理合成，它耍求输入为两幅幽像如图2 1 3 ，幅纹卿图像【a ) 作 为原始图像，一幅普通削像( b ) 作为目标图像，它的目的是通过一定的方法使得目标图像 ( c ) 具有原始纹理的特征。 t # ) 辍雅蛙挥 b 鞠耩越像 c 输m 秣鬃 1 9 2 1 3 按理传辕 纹攥传输裁缝艇目标i 璺 像上的纹辞合成，只楚合成过榉中t 邻城搜糍不仅耍满赴慷始纹 理r 的邻域绶性耐馘婴满足与口标l f 像糊都城一缎性。闲北设麓授霞系数q 柬控制：前 对葜戆彩旗。 d = 口b 委t 戍，一r 2 + t t 一鲫瞄r1 要t 盛，或，2 r c z a 越援邋0 ，戮对娃禄 璺| 像靛菠动越套，橱反越接遥l 嘲鼓理敛聚避攥募。 纹蠼传输的进一步j 屺h j 越蕊术风格的纹理传输( a r t is t i cs t y l et r a n s f e r ) ，它的主 要 的楚埘h 橼幽像进行浊濒姓理，它慰甄媲绽理不仅定义了方囊，愿强愆义了举鞠的蘧攀 中国科学技术大学硕士学位论文 纹理台成技术的研究 等，因此产生的结果更加复杂真实。 2 3 3 多样图纹理合成 在实际应用中，从自然界获得的纹理往往不能满足人们的要求，需要通过编辑处理获得 各种不同的纹理样本。如何从已有的纹理样图中生成所需的纹理，满足人们的各种需求是十 分有意义的问题。于是提出了多种样图纹理合成技术。把多种纹理合成到一个新的纹理图像 上，使新的纹理图像兼有多个纹理样本的统计特征，产生一种新的特殊效果图。 图21 4 两种样图的纹理合成 多样i 虱纹理合成也称为纹理混合，混合方法类似于纹理传输，一般方法”j 是在邻域比较 的距离函数中定义各种输入纹理资源的权熏系数，权重系数越大的纹理在目标纹理中所占的 比重就越人。 r1a 7 , 2 拈蕃w 恃蔷( 一彬f 在计算过程中先由简单的距离函数计算得出对每一个原始纹理距离最小的只m ，然后 套用上式得到最佳的邻域。 2 3 4 圈像类推 口 图21 5 图像类推 给定原始图像a 和a ，其中a 为a 的滤波结果，再给定目标图像b ，要求模拟从a 到a 的滤波过程，产生滤波后目标图像b 。 a ：a ：丑：b 。 ( 2 - 1 2 ) 它的算法”也是采用了邻域模型，对于b 中的每一个待合成点，在b 中的相对应位置得 到邻域向量，然后以此向量在a 中找到最匹配的邻域通过此邻域在a 中的相对应位置得到 1 7 中国科学技术大学硕士学位论空 纹理合成技术的研究 它在a 中的亮度信息，最后复制到b 中。在算法中采用多分辨率搜索可以降低邻域大小 aa bb 图2 1 6 图像类推中的邻域搜索 图像类推的应用面很广，比如图像滤波、图像合成、超分辨率、图像传输、艺术滤波等。 2 3 5 超分辨率 纹理传输技术可以应用到图像超分辨率上，对于类视觉上复杂的图像，在一些尺度上 具有重要的细节结构，并且认为这类图像在近邻的不同分辨率上视觉上类似。如图2 ，1 7 ，对 于一幅图像( a ) ，把它作为高分辨率的原始图像首先对其副本进行膨胀得到尺寸上更大 且低分辨率的目标图像( b ) ，然后借助纹理传输技术将高分辨率的原始纹理转移到目标图 像上，从而获得尺寸更大的高分辨率图像( c ) 。 t i t “) 图21 7 基于纹理合成的图像超分耕率 2 3 。6 三维物体表面的纹理合成 在现实世界中，物体表面存在着十分丰富的纹理细节。人们正是根据这些纹理细节区别 各种具有相同形状的物体，因此物体表面纹理细节的模拟在真实感图形绘制中起着举足轻重 的作用。如何在计算机生成的图形中有效的表现这些纹理细节是计算机图形学的一个主要研 究目标。 1 3 中田科学技术人学硕士学位论文纹理合成技术的研究 (