（计算机软件与理论专业论文）二维纹理合成算法及其应用研究.pdf

韩伟东：二维纹理台成算法及其应用研究 摘要 随着计算机技术的飞速发展，多媒体产品在人们的日常生活中变得越来越普遍，越 来越重要，同时人们对其的要求也越来越高，图片要更清晰，虚拟场景要更逼真，甚至 电影特技要更眩目。所有的一切，都对计算机图形学、图像处理、虚拟现实、计算机视 觉以及真实感绘制等相关学科提出了更高的要求。纹理可以表现出物体表面丰富的细节 特性，可以描述各种各样有着重复特性的自然现象。对于绘制合成图像、动画来等来说， 纹理是至关重要的。因此纹理技术在上述相关领域中受到广泛的重视，并取得了蓬勃的 发展。 本文在二二维纹理的合成算法及其应用上进行了研究和探索，提出了基于块的l 冬g 域 搜索纹理合成算法( p a t c h - b a s e dl - s h a p e dn e i g h b o r h o o ds e a r c h ( p b l n s ) ) 。p b l n s 算法 不仅简单快速，且对自然纹理和半结构纹理有很好的合成效果。在纹理合成的选取阶段， 我们提出了一种基于块的l 一邻域搜索算法，与以往的基于像素的l 一邻域不同是，该算 法构建基于块的l 一邻域，在利用l 广邻域减少搜索空间的同时，利用块能够保持纹理结 构信息的特性来保证合成纹理的结构连续性和完整性。在纹理合成的拼接阶段，采用动 态编程方法求出重叠区域上的最小误差边界，并利用羽化进一步光滑边界。 通过扩展p b l n s 算法，本文还提出了新的约束纹理合成算法，该算法中我们把l 广 邻域扩充为正方形邻域，这样就能在合成约束纹理的右部和底部边界时，能够把右部和 底部周围已存在部分包含进来，使得选择出的纹理块能够更好地与四周的纹理相融合， 从而解决了在合成约束纹理时普遍存在的右部和底部边界不连续的问题。同时我们还给 出了一些应用实例。 同样，通过扩展p b l n s 算法，本文还提出了新的多样本纹理合成算法，该算法可 以让用户根据不同的应用，采用不同的纹理特征进行匹配、选取，而不仅仅局限于颜色 匹配，提高了多样本纹理合成的灵活性和适用性。另外，把多样本的混合权值从一维扩 展为二维，从而能够很容易地实现各样本纹理特征在输出纹理中的布局。同时我们也给 出厂一些应用实例。 关键词： 纹理映射，纹理合成，约束纹理合成，多样本纹理合成，纹理混合，邻域搜索，图 像拼接，图像修复 韩伟东；二维纹理台成算法及其应用研究 a b s t r a c t w i t ht h ef a s td e v e l o p m e n to fc o m p u t e rt e c h n i q u e s ，m u l t i m e d i ap r o d u c t sa r eb e c o m i n g m o r ea n dm o r ec o i i l l y i o ni np e o p l e sd a i l yl i f e a sf o ri t sg r o w i n gi m p o r t a n c e ，m o r ea n dm o r e f l e wa n da d v a n c e dt e c h n i q u e sa r ei nn e e d ，e s p e c i a l l yi nt h ef i e l d so fp h o t op r o c e s s i n ga n d v i r t u a ls c e n er e c o n s t r u c t i o n a l lo ft h ea b o v es e tg r e a td e m a n df o rt h ed e v e l o p m e n to f c o m p u t e rg r a p h i c s ，i m a g ep r o c e s s i n g ，v i r t u a lr e a l i t y ，c o m p u t e rv i s i o na n dp h o t o - r e a l i s t i c r e n d e r i n g t e x t u r ei su s e dt or e p r e s e n tt h er i c hd e t a i l so nt h es u r f a c eo ft h eo b j e c t s ，s oi tc a r l b ea l s ou s e dt od e p i c tt h en a t u r a lp h e n o m e n o nt h a th a sr e p e a t e df e a t u r e s a sf o rt h e s y n t h e s i z e di m a g ea n da n i m a t i o n ，t e x t u r es h o w se x t r a o r d i n a r yi m p o r t a n c e d u et oa l lo ft h e a b o v e ，t e x t u r et e c h n i q u e sa r ed r a w i n gm o r ea n dm o r ee x t e n s i v ea t t e n t i o n ，a n de n j o y p r o m i s i n gd e v e l o p m e n t t h i sp a p e rm a i n l yf o c u s e so nt h ea l g o r i t h ma n da p p l i c a t i o no ft w o - d i m e n s i o n a lt e x t u r e s y n t h e s i s w ep r e s e n tan e wt e x t u r es y n t h e s i sa l g o r i t h mw h i c hi s c a l l e dp a t c h b a s e d l s h a p e dn e i g h b o r h o o ds e a r c h ( p b l n s ) p b l n si ss i m p l ea n df a s t ，a n da l s oi ts h o w sg r e a t s y n t h e s i sr e s u l t so nn a t u r a lt e x t u r e sa n dh a l f - s t r u c t u r e dt e x t u r e s i nt h es e l e c t i o np h a s eo f t e x t u r es y n t h e s i s ，w ep u tf o r w a r dap a t c h - b a s e dl - s h a p e dn e i g h b o r h o o ds e a r c ha l g o r i t h m ， w h i c hi sq u i t ed i f f e r e n tf r o mt h ep a s tp i x e l - b a s e da l g o r i t h m s i t sp a t c h - b a s e dn e i g h b o r h o o d m a k e sf u l lu s eo fi t sd i s t i n c tl s h a p e dn e i g h b o r h o o dt or e d u c et h es e a r c hs p a c e ，a sw e l la s p r e s e r v et h es t r u c t u r ec o n t i n u i t ya n di n t e g r i t yo ft h et e x t u r e i nt h eq u i l t i n gp h u s eo ft e x t u r e s y n t h e s i s ，w ec a l c u l a t et h em i n i m u me r r o rb o u n d a r yo ft h eo v e r l a p p e dr e g i o nt h r o u g h d y n a m i c a lp r o g r a m m i n g ，a sw e l la sa d o p tt h ef e a t h e r i n gt of u r t h e rs m o o t ht h eb o u n d a r y b a s e do nt h ee x t e n s i o no fp b l n sa l g o r i t h m ，w ea l s op r e s e n tan e wc o n s t r a i n e dt e x t u r e s y n t h e s i sa l g o r i t h m ，w h i c he x t e n d st h el s h a p e dn e i g h b o r h o o dt os q u a r es h a p e i nt h i sw a y , w ec a nf u r t h e ri n c l u d et h er i g h ta n db o t t o ms i d eo ft h es q u a r e s h a p en e i g h b o r h o o dt om a k e b e t t e ri n t e g r a t i o no ft h es e l e c t e dp a t c ha n dt h es q u a r e s h a p en e i g h b o r h o o dt e x t u r e a n da l lo f t h ee f f o g sf i n a l l yr e s o l v et h ed i s c o n t i n u i t yp r o b l e mo fr i g h ta n db o r o mb o u n d a r yd u r i n g c o n s t r a i n e dt e x t u r es y n t h e s i s w ea l s op r e s e n taf e wa p p l i c a t i o ne x a m p l e so ft h i sk i n d b e s i d e s ，t h i sp a p e rp r e s e n t sn e wm u l t i s o u r c et e x t u r es y n t h e s i sa l g o r i t h m s t h i s a l g o r i t h m c a l le n a b l eu s e rt oa d o p td i f f e r e n tt e x t u r ec h a r a c t e r i s t i c sf o rm a t c h i n ga n ds e l e c t i o n b a s e do nd i f f e r e n ta p p l i c a t i o n s ，a sw e l la si m p r o v et h ef l e x i b i l i t ya n da p p l i c a b i l i t yo f m u l t i s o u r c et e x t u r es y n t h e s i s ，w h i c hi s n tl i m i t e dw i t h i nc o l o rm a t c h i n g w h a t sm o r e ，i t 3 韩伟东：二维纹理合成算法及其应用研究 e x t e n d st h em i x e dw e i g h to fm u l t i - s o u r c ef r o mo n e d i m e n s i o nt ot w o d i m e n s i o nt of a c i l i t a t e t h eo u t p u tt e x t u r el a y o u to fe a c hs a m p l e st e x t u r ec h a r a c t e r i s t i c s a l s o ，s e v e r a la p p l i c a t i o n e x a m p l e sa r eg i v e n k e y w o r d s ： t e x t u r em a p p i n g ，t e x t u r es y n t h e s i s ，c o n s t r a i n e dt e x t u r es y n t h e s i s ，m u l t i s o u r c e t e x t u r e s y n t h e s i s ，t e x t u r em i x t u r e ，n e i g h b o r h o o ds e a r c h ，i m a g eq u i l t i n g ，i m a g e r e s t o r a t i o n d 第一章绪论 1 绪论 纹理是普遍存在的。纹理可以表现出物体表面丰富的细节特性，可以描述各种各样有 着重复特性的自然现象，例如声音( 机房里的噪音) 、运动( 动物奔跑) 、可视化表面( 表 面颜色和几何) 和人类活动( 我们的日常生活) 。自然世界的真实重现是计算机图形学的 主要目的，所以对于绘制合成图像和动画来说，纹理是至关重要的。虽然由于纹理的多 样性，很难在一个通用的框架下去描绘和重现它们，但是自1 9 5 0 年g i b s o n g i b s o n1 9 5 0 1 指出了纹理在可视化感知中的重要意义以来，纹理技术在计算机图形学、虚拟现实和计 算机视觉以及真实感绘制等相关领域中，一直受到广泛的重视，并取得了蓬勃的发展。 1 1 概念介绍 究竟什么是纹理，很难下一个明确的定义。首先，让我们从介绍纹理的概念开始，并 进而描述纹理合成的目标。 1 1 1 什么是纹理 重现物体表面细节对于计算机绘制图像的视觉真实感来说是至关重要的。对表面细节 建模的一一种常用方法是使用多边形或其它几何特性来建模，但是随着细节要求的越来越 精细和复杂，用几何特性来精确建模变得越来越不可行。另一种方法，是把图像映射到 物体表面上，这技术就是纹理映射。被映射的图像。就叫作纹理图像或纹理。纹理能够 调整多种表面属性，包括颜色、反射、透明度和位移。在计算机图形学中，纹理的内容 很广泛。例如，用于映射的彩色纹理，可以是包含任意图案的图像。 但是，纹理的意思在计算机图形学中被误用了。在韦伯斯特( w e b s t e r ) 词典中，纹 理是这样被定义的： t e x t u r e ，n o u n 【1 5 7 8 】 ( a ) s o m e t h i n gc o m p o s e do fc 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 ( b ) 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 faf a b r i c e 的煮露理 纹理台戚 奎- - ( h ) 台藏结果 图ll ：绐定样本纹理( a ) ，我们的目标是要合成卅看起来像样本纹理的新纹理由) 。合成的新纹理 可以被指定为任意尺寸。 也就是说，纹理通常是指由重复图案组成的可见或可触觉的表面，例如纺织物。显然， 这个定义于计算机图形学中的纹理概念相比就显得太狭隘了。然而，在自然界中的大多 数物体表面足由重复元素组成的，所以，这个狭隘的定义足够去表达大多数的物体表面 特征。这个定义也被计算机视觉和图像处理领域广泛采用。 虽然很难给纹理下个明确的定义，1 h 是散来说，纹理中的灰度分布具有某种周期性， 即便灰度变化是随机的，它也具有一定的统计特征。霍金斯 r u a n2 0 0 1 1 认为纹理有三个 要素：一是某种局部的序列性，在该序列更大的范罔内不断重复；二是序列是| 士| 基本部 分非随机排列组成的：三是各部分大致都是均匀的统一体，纹理区域内任何地方都有大 致相同的结构尺寸。 在本文中，除了考虑纹理包含的重复图案，我们也考虑在重复图案之上的一定的随机 性。如图1 1 ，给定的蜂窝纹理是由很多个尺寸和形状上有细微差别的六边形组成的。不 同的纹理随机性是4 i 一样的，比方说，橘子表皮纹理的随机性根大，但是规则地板纹理 的随机性就很小。 1 1 2 什么是纹理合成 计算机图形学中经常用纹理来绘制图像。这些纹理可以从很多地方得到，例如手绘图 或扫描照片。手绘图有审美艺术上的价值，但是它们很难做到真实感。而大多数扫描图 像，有尺寸上的限制，直接用j 二纹理映射会造成明显的边界或重复现象。 纹理合成是一种创建新纹理的有效方法。凼为合成的纹理可以是任意尺寸的，而月可 第一章绪论 以避免明显的图像重复现象。另外，通过适当的边界条件处理，纹理合成也可以合成出 规则的图像。 所以，纹理合成的目标是：给定一个样本纹理，合成出新的纹理，对人的感知系统来 说，新纹理就好像是从样本纹理中自然的衍生出来( 如图1 1 ) 。这里最主要的挑战是： 建模t如何模拟从给定的有限大小的纹理样本合成出新纹理的过程? 模拟过程应该 要对输入纹理的结构部分和随机部分都能够建模。成功的建模取决于合成的新纹理跟 给定的纹理样本在视觉上的相似度。 采样； 根据一定的合成纹理过程，如何发展出一种有效的采样程序去产生新纹理? 采样程序的有效性直接取决于纹理合成的计算复杂度。 本文中，我们呈现了一个简单有效且适合大多数纹理的合成算法。我们通过空间邻域 对纹理建模，然后通过基于上述邻域的搜索程序来合成纹理。通过应用适当的加速技术， 我们的合成过程接近于实时。 1 2 纹理合成技术概述 1 2 1纹理合成技术的发展历史 自1 9 5 0 年g i b s o n g i b s o n1 9 5 0 提出纹理的概念以来，纹理合成技术的发展历经了3 个 主要阶段： 第一个阶段是纹理映射阶段。因为该技术没有特征提取和模型优化，只是把样图宜接 匹配到目标表面，所以可看成是简化的基于样图的纹理合成； 第二个阶段是过程纹理合成阶段。虽然该技术没有直接利用样图，但是在构造物理仿 真模型时需要深刻认识样图纹理的物理特征，再依据此认识来构造相应的物理仿真模型， 由于该技术隐藏了特征提取，并强化了模型构造和优化，因而是近似的基于样图的纹理 合成： 第三阶段是基于样图的纹理合成。该技术目前是研究热点，发展迅速，并且取得了显 著的效果。 1 纹理映射 纹理映射作为应用于真实感图形绘制中的一项常用技术，首先由 c a u n u l l1 9 7 4 提出， 其目标是减少或避免拼贴引起的接缝和扭曲。基于能量最小化的思想，先后提出了多种 改进算 法 b r u n o1 9 9 8 1 d a n 2 0 0 0 j e r o m e1 9 9 3 ，p e d e r s e n p e d e r s e n1 9 9 5 提出了一种在 隐式曲面上通过用户交互实现映射的方法。针对纹理映射中的纹理走样问题，先后提出 很多纹理反走样改进算 法 c a t m u l t1 9 7 4 g i b s o n1 9 5 0 。b l i n n b f i n n1 9 7 6 】提出利用扰动 第一章结论 以避免明显的图像重复现象。另外，通过适当的边界条件处理，纹理台成也可以合成出 规则的图像。 所以，纹理合成的目标是：给定一个样本纹理，合成出新的纹理，对人的感知系统来 说，新纹理就好像是从样本纹理中自然的衍生出来( 如图1 1 ) 。这里摄主要的挑战是： 建模t如何模拟从给定的有限大小的纹理样本合成出新纹理的过程? 模拟过程应该 要对输入纹理的结构部分和随机部分都能够建模。成功的建模取决于合成的新纹理跟 给定的纹理样本在视觉上的相似度。 采样：根据一定的台成纹理过程，如何发展h 1 一种有效的采样程序去产生新纹理? 采样程序的有效性直接取决十纹理合成的计算复杂度。 本文中我们呈现了个简单有效且适合大多数纹理的合成算法。我们通过空间邻域 对纹理建模，然后通过基于上述邻域的搜索程序束合成纹理。通过应用适当的加速技术， 我们的合成过程接近千实盯。 1 2 纹理合成技术概述 l2i 纹理合成技术的发展历史 自1 9 5 0 年g i b s o n g i b s o n1 9 5 0 1 提出纹理的概念以来，纹理合成技术的发展历经了3 个 主要阶段； 第个阶段是纹理映射阶段。冈为该技术没有特征提取和模型优化，只是把样图直接 匹配到目标表面，所以可看成是简化的基于样图的纹理合成； 第二个阶段是过程纹理合成阶段。虽然该技术没有直接利用样图，但是在构造物理仿 真模型时需要深刻认识样图纹理的物理特征，再依据此认识来构造相应的物理仿真模型， 由于该技术隐藏了特征提取，并强化了模型构造和优化，因而是近似的基于样图的纹理 合成； 第三阶段是基于样图的纹理合成。发技术目前是研究热点，发展迅速，并且取得了显 著的效果。 1 纹理映射 纹理映射作为应用于真实感图形绘制中的i 页常用技术，首先 c a m a u l l1 9 7 4 提出， 其目标是减少或避免拼贴引起的接缝和扭曲。基于能量虽小化的思想，先后提出了多种 改进算法 b r u n 0 1 9 9 8 】 d a n2 0 0 0 】 j e r o m e l 9 9 3 ，? e d e r s e n p e d e r s e n l 9 9 5 提出了一种在 隐式曲而r 通过用户交当实现映射的方法。钊对纹理映射中的纹理走样问题，先后提出 根多纹理反走样改进算法 c a t m u l l1 9 7 4 g i b s o n1 9 5 0 。b l i n n b l i n na 9 7 6 t 提出利用扰动 根多纹理反走样改进算法 c a m _ l u l l1 9 7 4 g i b s o nj 9 5 0 l 。b l i n n b l i n n1 9 7 6 1 提出利用扰动 9 第一章绪论 以避免明显的图像重复现象。另外，通过适当的边界条件处理，纹理合成也可以合成出 规则的图像。 所以，纹理合成的目标是：给定一个样本纹理，合成出新的纹理，对人的感知系统来 说，新纹理就好像是从样本纹理中自然的衍生出来( 如图1 1 ) 。这里最主要的挑战是： 建模t如何模拟从给定的有限大小的纹理样本合成出新纹理的过程? 模拟过程应该 要对输入纹理的结构部分和随机部分都能够建模。成功的建模取决于合成的新纹理跟 给定的纹理样本在视觉上的相似度。 采样； 根据一定的合成纹理过程，如何发展出一种有效的采样程序去产生新纹理? 采样程序的有效性直接取决于纹理合成的计算复杂度。 本文中，我们呈现了一个简单有效且适合大多数纹理的合成算法。我们通过空间邻域 对纹理建模，然后通过基于上述邻域的搜索程序来合成纹理。通过应用适当的加速技术， 我们的合成过程接近于实时。 1 2 纹理合成技术概述 1 2 1纹理合成技术的发展历史 自1 9 5 0 年g i b s o n g i b s o n1 9 5 0 提出纹理的概念以来，纹理合成技术的发展历经了3 个 主要阶段： 第一个阶段是纹理映射阶段。因为该技术没有特征提取和模型优化，只是把样图宜接 匹配到目标表面，所以可看成是简化的基于样图的纹理合成； 第二个阶段是过程纹理合成阶段。虽然该技术没有直接利用样图，但是在构造物理仿 真模型时需要深刻认识样图纹理的物理特征，再依据此认识来构造相应的物理仿真模型， 由于该技术隐藏了特征提取，并强化了模型构造和优化，因而是近似的基于样图的纹理 合成： 第三阶段是基于样图的纹理合成。该技术目前是研究热点，发展迅速，并且取得了显 著的效果。 1 纹理映射 纹理映射作为应用于真实感图形绘制中的一项常用技术，首先由 c a u n u l l1 9 7 4 提出， 其目标是减少或避免拼贴引起的接缝和扭曲。基于能量最小化的思想，先后提出了多种 改进算 法 b r u n o1 9 9 8 1 d a n 2 0 0 0 j e r o m e1 9 9 3 ，p e d e r s e n p e d e r s e n1 9 9 5 提出了一种在 隐式曲面上通过用户交互实现映射的方法。针对纹理映射中的纹理走样问题，先后提出 很多纹理反走样改进算 法 c a t m u l t1 9 7 4 g i b s o n1 9 5 0 。b l i n n b f i n n1 9 7 6 】提出利用扰动 第一章绪论 函数来生成凹凸效果的纹理。 2 过程纹理 纹理映射虽然简单，但是可改进的空间不大，于是出现了过程纹理合成。p e r l i n p e r l i n 1 9 8 5 $ 口p e a c h e y p e a c h e y1 9 8 5 提出了实体纹理函数( s o l i dt e x t u r e ) ，实体纹理在模拟 雕刻表面时取得了较好的效果。p e r l i n p e r f i n1 9 8 5 1 还引进了三维的噪声函数，可以对水 波、大理石等进行很好的模拟，w o r l e y w o r l e y1 9 9 6 对噪声函数进行改进，提出了 e e l l u l a r 噪声函数，可用于模拟水波、宝石。n e y r e t n c a n i n e y r e t1 9 9 9 提出了一种新的 生成少量的三角片的方法，实现纹理拼接。采用一个基本的r e a c t i o nd i f f u s i o n 方程， w i t k i n $ 口k a s s w i t k i n1 9 9 1 模拟了许多种纹理，如毛发、云雾等。t u r k t u r k1 9 9 1 1 证明了 r e a c t i o n d i f f u s i o n 的模拟可以直接在多边形表面进行，实现无缝的拼接。 f l e r s c h e r f l e i s c h e r1 9 9 5 等人实现了鳞状和刺状纹理的仿真。w a l t e r 署a f o u r n i e r w a l t e r 1 9 9 8 采用细胞分裂的方法可以模拟许多动物的纹理。 3 基于样图的纹理合成 过程纹理虽然可以获得良好的效果，但对每一种新的纹理都需要调整参数反复测试， 非常不便。利用纹理本身具有的局部相似性，启发人们着手研究基于样图的纹理合成方 法：给定一小块纹理，生成大块相似而连续的纹理。 s i m o n c e l l i 和p o r t a l l i 利用统计的方法，通过可控的金字塔进行纹理合成，对多种纹 理都取得了理想的效果 s i m o n c e l l i1 9 9 8 p o n i l l a1 9 9 9 。 h e e g e r1 9 9 5 1 利用拉普拉斯和可 控的金字塔进行纹理合成。 d eb o n e t1 9 9 7 1 也利用多尺度的金字塔进行纹理合成，他们采 用两个拉普拉斯金字塔及滤波器处理纹理，在查找匹配时，考虑已合成的父层的点，从 符合条件的待选点中随机选一个填写。 e f r o s1 9 9 9 1 提出了一种更直接的方法。先在待合 成图中设置一些种子，然后通过给定的邻域在样图中查找匹配点，从中随机选取一个进 行填写。w e i2 0 0 0 也提出了类似的算法，并采用多尺度模型进行匹配，利用矢量量化方 法极大地加速了合成过程。在近几年的s i g g r a p h 会议上，又有多篇文章提出了各自的纹 理合成算法。f e f r o s2 0 0 1 提出了一种基于块拼贴的纹理合成算法，通过查找误差最小的 路径实现各块的拼贴，对一些纹理取得了非常好的效果。w e i w e i2 0 0 1 a 等人提出的方法 与t u r k t u r k2 0 0 1 类似，也采用了多尺度的方法进行曲面纹理合成，合成的质量很高。 y i n g y i n g2 0 0 1 等人提出的两种算法直接在曲面和成纹理。 k w a g a 2 0 0 3 1 采用图形剪切 ( g r a p hc u t ) 的方法来合成2 2 维图像纹理和视频纹理。【w u2 0 0 4 通过预处理样本纹理， 提取出样本纹理的特征图像，在纹理块的选取过程中，同时匹配特征和颜色，从而保证 纹理基元的结构完整性，对结构性纹理取得了很好的效果。f k w a 仃a2 0 0 5 用优化的方法 来合成纹理，他们定义了马尔可夫随机域( m r f ) 上的纹理能量函数来度量合成纹理的 质量，通过使能量函数变小来提高合成纹理的质量，并且可以迭代改进合成纹理的质量。 l o 第章绪论 1 3 纹理合成应用概述 纹理合成在计算机图形学、图像处理、计算机视觉及真实感绘制领域有广泛的应用。 下面我们简单地介绍一下纹理合成在各个领域中的相关应用。 1 3 1绘制 在绘制中，纹理可以模拟真实物体的表面细节。它既可以改变表面的颜色，扰动表面 法线( b u m pm a p p i n g ) ，还可以使表面几何变形( d i s p l a c e m e n tm a p p i n g ) 。在笔绘风格 的图画中，纹理能够描绘色调、阴影及物体图案 w i n d e n b a c h1 9 9 4 】 w i n d e n b a c h1 9 9 6 。 1 3 2 动画 计算机产生的动画经常包含脚本事件和随机运动，脚本事件是非重复的动作，例如打 开门捡起一个物体，并且通常是被直接控制的。然而，随机运动是重复性的背景运动， 例如波浪、冉冉上升的烟雾或燃烧的火焰。这类运动在时间和空间上有不确定的范围， 通常被称为时间纹理( t e m p o r a lt e x t u r e ) s z u m m e r1 9 9 6 。在时间纹理中，一些特定的运 动例如关节运动的接合角，可以被建模成一维纹理。这些纹理能够被合成用于模拟精巧 的动作，例如眨眼睛或人的走动。 1 3 3 压缩 描述自然场景的图像经常包含很大的纹理区域，例如块草地，一片森林或沙滩。因 为纹理总是包含大量的高频信息，所以基于频域的技术如j p e g 不能很好的压缩它们。通 过在预处理阶段分割那些纹理区域，可以用纹理合成技术来压缩它们。另外，对于图像 压缩，纹理合成也可以被用于合成包含大量纹理的场景 d e b o n e t1 9 9 7 。 1 3 4 修复和编辑 照片、电影和图像中经常会有缺陷的地方，可能扫描照片时出现了模糊的区域，旧电 影画面中出现擦痕，或者图像中出现了一个不想要的物体。由操作引起的这些缺陷一般 是不可逆的，所以修复这些缺陷的算法是很有用的。通常，缺陷部分包含在某个纹理区 域中，且能够通过纹理合成来替换掉缺陷部分 i g e h y1 9 9 7 】 e f i o s1 9 9 9 1 。 1 3 5 计算机视觉 计算机视觉中的很多功能领域都用到了纹理，例如分割、识别和分类，这些功能领域 能够从衍生自纹理合成算法的纹理模型中得到帮助，从而解决问题。 第一章绪论 1 4 研究目的和主要内容 1 4 1 研究目的与意义 随着计算机技术的飞速发展，多媒体可以说已经在人们生活中无处不在，m p 3 ，数 码相机和数码摄影机等数码产品已经成为越来越多人的必备之物。水涨船高，人们对多 媒体产品的要求越来越高，图片要更清晰，虚拟场景要更逼真，甚至电影特技要更眩目。 所有的一切都对计算机图形学、图像处理、计算机视觉等相关技术提出了更高的要求。 在前面介绍的纹理合成应用中( 1 3 节) ，我们能发现纹理合成的广泛应用前景，通过提 高纹理合成技术，可以解决人们生活中的很多需求。 纹理合成在计算机视觉和图形领域是一个热门领域，且已经被深入地研究了很多 年，但是纹理合成中依然存在不少有待解决的问题。比如： _ 结构化很强的纹理有时不能完美地合成。 一s s d ( s u m m e ds q u a r e dd i f f e r e n c e ) 距离测量法不能有效的表现高频信息。 _ 目前还没有一个通用的框架能够快速有效的合成各种纹理。 鉴于纹理合成的广泛应用前景，及其还存在的问题，本文的研究目的就是探索出一 种能够快速有效且能够适用于各种不同纹理的合成算法及其应用框架。本文提出的算法 ( 基于块的l - 邻域搜索纹理合成算法) 简单快速，对自然纹理和半结构纹理有很好的 合成效果，而且能够容易地扩展出相应的约束纹理合成、多样本纹理合成等算法。并且， 针对各种算法，给出了一些应用实例。 1 4 2 主要内容 本文在二维纹理的合成算法及其应用上进行了研究和探索。在算法方面，我们提出 了基于块的l 。邻域搜索纹理合成算法。基于此算法，我们发展了相应的约束纹理合成 算法和多样本纹理合成算法，且对其应用进行了探讨和尝试。本文的主要内容大致分为 以下几部分： 1 基于块的l 邻域搜索纹理合成算法 本文提出的基于块的l 广邻域搜索纹理合成算法( p a t c h - b a s e dl - s h a p e d n e i g h b o r h o o d s e a r c h ( p b l n s ) ) 算法简单快速，对自然纹理和半结构纹理有很好的合成效果。在选取 阶段，我们提出了一种基于块的l 邻域搜索算法，与以往的基于像素的l 一邻域不同是， 该算法构建基于块的l 邻域，在利用l 一邻域减少搜索空间的同时，利用块能够保持纹 理结构信息的特性来保证合成纹理的结构连续性和完整性。在拼接阶段，采用动态编程 方法求出重叠区域上的最小误差边界，并利用羽化进一步光滑边界。 2 约束纹理合成 1 2 第一章绪论 照片、电影和图像经常会包含一些在感官上有缺陷的区域。可能扫描照片时出现了 模糊的区域，旧电影画面中出现擦痕，或者图像中出现了一个不想要的物体。由操作引 起的这些缺陷一般是不可逆的，所以修复这些缺陷的算法是很有用的。用约束纹理合成 的方法来修复这些问题很有效。通过扩展基于块的l 乓域搜索纹理合成算法，本文提 出了新的约束纹理合成算法，并且介绍了一些相关应用。 3 多样本纹理台成 在实际应用中，从自然界获得的纹理往往不能满足人们的要求，需要通过编辑处理 获得各种不同的纹理样本。如何从已有的纹理图样中生成所需的纹理，满足人们的各种 需求是十分有意义的问题。多样本纹理合成就是能够根据现有的多个样本纹理，合成出 “新纹理”。通过扩展基于块的l 广邻域搜索纹理合成算法。本文提出了新的多样本纹 理合成算法，并且介绍了一些相关应用。 1 5 本文的组织结构 本文在总体上可以分为以下几个部分： 第一部分即第一章，对纹理合成技术及其应用进行了简单的介绍与回顾，阐述了本 文的研究背景、目的意义和内容。 第二部分包括第二、三、四章，详细讨论了我们的二维纹理合成算法及其应用。 第三部分为总结和今后工作的展望，在第五章中给出。 下面分章节介绍一下每章的具体内容。 第一章绪论阐述了本文的研究背景、目的意义和内容。对当前纹理合成技术及其 应用进行了简单的介绍与回顾，分析了现有的纹理合成技术的优点、不足及 发展趋势。最后，介绍了本文的研究目的和主要内容。 第二章二维纹理合成算法研究基于现有纹理合成技术的一些不足，我们提出了一 种新的纹理合成算法：基于块的l 厂邻域搜索纹理合成算法。我们的算法简单 快速，对自然纹理和半结构的纹理有很好的合成效果，并且具有很好的扩展 性。 第三章约束纹理合成算法研究及其应用通过扩展我们在第二章中提出的纹理合 成算法，我们提出了一种新的约束纹理合成算法，解决了在合成约束纹理时 普遍存在的右部和底部边界不连续问题。另外，我们给出了一些有趣的应用 实仞i 。 第一章绪论 第四章多样本纹理合成算法研究及其应用通过扩展我们在第二章中提出的纹理 合成算法，我们提出了一种新的多样本纹理合成算法。该算法可以让用户根 据不同的应用，采用不同的纹理特征进行匹配、选取，而不仅仅局限于颜色 匹配，提高了多样本纹理合成的灵活性和适用性。另外，我们给出了一些有 趣的应用实例。 第五章总结和展望对本文的工作进行了总结，介绍了本文主要的贡献、创新之处 和工作中仍需要进步改进和完善的地方。最后，对纹理合成算法及其应用 的下一步工作方向作了展望。 】4 第= 章= 维纹理合成算法研究 _ _ _ _ _ _ _ _ _ - _ _ _ _ _ _ _ _ _ - _ _ _ _ _ _ _ - _ - _ _ _ - _ _ - _ _ - _ _ - _ _ _ _ _ _ _ h _ 一 2 二维纹理合成算法研究 2 1 二维纹理合成算法概述 在前面我们已经介绍过纹理合成技术的发展历史，可以发现，基于样图的纹理合成 技术是近几年迅速发展起来的纹理合成技术。它不仅克服了传统纹理映射方法的缺点， 又避免了过程纹理合成调整参数的繁琐，因而受到越来越多的研究人员的关注，成为计 算机图形学、计算机视觉和图像处理领域的研究热点之。本文提出纹理合成算法就是 基于样图的纹理合成技术。下面我们先来介绍一下基于样图纹理合成算法的概况。 2 ，1 。1 基于金宇塔采样特征匹配 早期的一些纹理合成算法把纹理建模成一组特征集，然后再通过匹配这些特征来产生 新的图像 d eb o n e t1 9 9 7 h e e g e r1 9 9 5 j o s e p h2 0 0 1 p o r t i l l a2 0 0 0 。这些方法很有效， 但是可能不能保存全局 d eb o n e r1 9 9 7 【h e e g e r1 9 9 5 j o s e p h2 0 0 1 或局部 p o r t i l l a2 0 0 0 的图案信息。 2 1 2 基于像素的纹理合成 【e f r o s1 9 9 9 的非参采样纹理合成方法就是通过重复地匹配合成纹理中目标像素的周 围邻域与输入样本纹理，选择出匹配的像素进行下一步合成。他们采用穷尽搜索法来选 出每一个最匹配的像素。 w e i2 0 0 0 的算法是基于 e f r o s1 9 9 9 的算法，并且扩展出允许使 用更小邻域去提高合成质量的合成金字塔。而且，他们采样树结构矢量化( 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 ) 技术来加速他们的合成算法。f a s h i k h m i n2 0 0 1 】 聪明的改进显著地减少了搜索空问，且做到了交互的纹理合成。在文中， a s h i k h m i n2 0 0 1 还详尽地讨论了以前的基于像素合成方法的缺陷，例如会造成模糊。合并 a s h i k h m i n2 0 0 1 】 * n i w e i2 0 0 0 1 的合成算法到同一个框架下，f h e r t z m a n n2 0 0 1 做出了很有意思的效果，并 且开创了一个新的应用领域，例如t e x t u r e b y n u m b e r s 。 z e l i n k a 2 0 0 2 1 展示了一种需要 预处理的实时纹理合成算法。 2 1 3 基于块的纹理合成 基于块的纹理合成方法通过产生每个区块上的纹理能够保存全局纹理结构。 e f r o s 2 0 0 1 1 根据相邻纹理块的重叠区域排齐它们的边界，然后采用动态编程( d y n a m i c p r o g r a m m i n g ) 方法找出重叠区域的最小误差路径作为相邻纹理块的边界，从而减少边界 的锯齿现象。l i a n g l i a n g2 0 0 1 等人的基于块的采样方法使用相同的块选择技术，但是在 相邻纹理块间的重叠区域使用了简单用a l p h a 混合( 羽化) 。他们的实现采用了多种搜索 第二章二维纹理合成算法研究 数据结构来到达实时的合成效果。 k w a t r a2 0 0 3 j 采用图形剪切( g r a p hc u t ) 的方法来合成 二维图像纹理和视频纹理。n e a l e n n e a l e n2 0 0 3 等人采用自适应的块尺寸策略，当最匹配 的纹理块误差超过一定阈值( 用户定义) 时，在重叠区域用适当的块尺寸再进行合成修 复。 w u2 0 0 4 通过预处理样本纹理，提取出样本纹理的特征图像，在纹理块的选取过程 中，同时匹配特征和颜色，从而保证纹理基元的结构完整性，对结构性纹理取得了很好 的效果。 2 2 基于块的l 一邻域搜索纹理合成算法 基于像素的纹理合成技术有很大的局限性，因为在合成过程中，实际上相当一部分 的后续像素点的选择已由已合成像素点所确定。这样许多像素点在查找上浪费了很多的 时间。而由于块能够保留纹理结构信息，基于块的合成技术可以很好地保留样图的全局 纹理结构，在合成结构纹理方面明显强于基于像素的合成方法。同时一次一个块的合成 方法相比于一次一个像素点的合成方法，在合成时间上也明显占优。 基于块的纹理合成，通常可以分为两个阶段：1 选取：根据已合成的纹理在样圈中 搜索到最匹配的块；2 拼接：把选取到的块拼接到已合成的纹理中。本文提出的基于块 的l 一邻域搜索纹理合成算法( p