（计算机软件与理论专业论文）基于样图的纹理合成算法优化.pdf

中文摘要 纹理是在计算机图形学中一种普遍存在的视觉现象。纹理通常用来描述自然 界中具有重复性的现象，如机房中的噪声，物体移动，物体表面细节特征以及人 类的活动等等。计算机图形学的主要目标就是再现真实世界，那么纹理合成在图 像处理和动画领域上有着重要的意义。 首先，提炼多种纹理合成算法共性，提出一种基于马尔可夫随机场( m i 江) 的纹理合成算法框架设计，该架构比较简单灵活，由两个相对独立的模块组成： 多分辨率图像金字塔和匹配查询。每个模块都可以进行独立的扩展。该框架是本 文纹理合成算法扩展和优化的原型。 其次，基于这种算法框架，提出一系列应在纹理合成过程中进行提取的纹理 特征。假设纹理为空间上分布的信号，挖掘出四个纹理特征作为合成过程的参考： 纹理能量，像素颜色值，梯度和空间频率。纹理能量是纹理的全局信息，那么纹 理合成过程就转换为能量最小化的优化过程。在能量约束下误差不会在纹理生成 过程中累积，纹理的全局信息可以在大范围内得到交换。像素颜色值是纹理合成 的基本依据。梯度为合成过程加入了高通滤波效应，增强了合成纹理的高频信息。 邻域尺寸的设置对最终结果影响颇大，通过动态空间频率检测，可以在适当的场 景中使用适当的邻域尺寸。 最后，对算法的迭代过程和匹配查询过程进行加速。提出基于遗传算法的混 合迭代优化以及多分辨率多尺度的方式进行纹理合成，可以有效降低在迭代过程 中陷入局部极值的可能性。同时，使用k d 树或t s v q ( t r e e s t r u c t u r e d v e c t o r q u a n t i z a t i o n ) 树等技术，对邻域匹配操作进行加速。 关键字：纹理合成、能量最小化、运算优化 a bs t r a c t t e x t u r e sc a nd e s c r i b eaw i d ev a r i e t yo fn a t u r a lp h e n o m e n aw i t hr a n d o m v a r i a t i o n so v e rr e p e a t i n gp a t t e r n s e x a m p l e so ft e x t u r e si n c l u d ei m a g e s ，m o t i o n s ，a n d s u r f a c eg e o m e t r y s i n c er e p r o d u c i n gt h er e a l i s mo ft h ep h y s i c a lw o r l di sam a j o rg o a l f o rc o m p u t e rg r a p h i c s ，t e x t u r es y n t h e s i si si m p o r t a n tf o rr e n d e r i n gs y n t h e t i ci m a g e s a n da n i m a t i o n s f i r s t l y , w ei n t r o d u c eab a s i ca r c h i t e c t u r eo ft e x t u r es y n t h e s i sb a s e du p o nm a r k o v r a n d o mf i e l d 卫1 ea r c h i t e c t u r ei sf l e x i b l ea n di ti sc o m p o s e df r o ms e v e r a lo r t h o g o n a l c o m p o n e n t s ：m u l t i - r e s o l u t i o ni m a g ep y r a m i da n ds e a r c h i n g e a c hc o m p o n e n tc a nb e e x t e n d e do ro p t i m i z e di n d e p e n d e n t l y t h ea r c h i t e c t u r ei st h ep r o t o t y p ef o rf u r t h e r e x t e n s i o na n do p t i m i z a t i o ni nt h i sp a p e r s e c o n d l y , b a s e du p o nt h ea r c h i t e c t u r e ，w ep u tf o r w a r das e r i e s o ft e x t u r e v a r i a b l e sw h i c hs h o u l db ec o n s i d e r e di nt h ep r o c e s so ft e x t u r es y n t h e s i s o nt h e a s s u m p t i o nt h a tt e x t u r ei sa k i n do fs i g n a ld i s t r i b u t e ds p a t i a l l y , w ef m do u tf o u ru s e f u l v a r i a b l e sf o rr e f e r e n c e ：g l o b a le n e r g y , p i x e lc o l o r , g r a d i e n ta n ds p a c ef r e q u e n c y t e x t u r ee n e r g yi st h eg l o b a li n f o r m a t i o na n dt h i sa l l o w su st of o r m u l a t et h es y n t h e s i s p r o b l e ma sm i n i m i z a t i o no fa l le n e r g yf u n c t i o n ，w h i c hc a l lb eo p t i m i z e d e r r o rc a l l t b ea c c u m u l a t e dt h r o u g ht h ep r o c e s so fs y n t h e s i sa n di n f o r m a t i o ni s e x c h a n g e di na l a r g e - s c a l ed o m a i n p i x e lc o l o ri st h eb a s i so fs y n t h e s i s g r a d i e n tw o r k sa sah i g hp a s s f i l t e rw h i c he n h a n c e sh i 曲f r e q u e n c yc o m p o n e n to ft h et e x t u r es y n t h e s i s f i n a l s y n t h e s i sr e s u l ti s s e n s i t i v et oi n i t i a ln e i g h b o r h o o ds e t t i n g t h r o u g hd y n a m i cs p a c e f r e q u e n c yd e t e c t i o n ，p r o p e rn e i g h b o r h o o dc a l lb es e ti nt h ea l g o r i t h mc o n t e x t f i n a l l y , w ei n t r o d u c es e v e r a ls o l u t i o n sf o ra c c e l e r a t i o n t h ep r o t o t y p ec a l lg e t s t u c ki nl o c a lm i n i m a h y b r i dg e n e r i ca l g o r i t h md e c r e a s e si t e r a t i o nc o u n ti ne a c h r e s o l u t i o n m u l t i - l e v e l m u l t i s c a l es y n t h e s i sp a r t i a l l ya l l e v i a t e st h i sp r o b l e mb y b r i n g i n gd i s t a n tn e i g h b o r h o o d sc l o s e rt oe a c ho t h e rv i ad o w n s a m p l i n g i na d d i t i o n ， o u ra l g o r i t h mc a nb ed i r e c t l ya c c e l e r a t e db yap o i n ts e a r c h i n ga l g o r i t h ms u c ha s 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 na n dk - dt r e e k e y w o r d s ：t e x t u r es y n t h e s i s ，e n e r g ym i n i m i z a t i o n ，c o m p u t i n go p t i m i z a t i o n 独创性声明 本人声明所呈交的学位论文是本人在导师指导下进行的研究工作和取得的 研究成果，除了文中特别加以标注和致谢之处外，论文中不包含其他人已经发表 或撰写过的研究成果，也不包含为获得丞鲞盘鲎或其他教育机构的学位或证 书而使用过的材料。与我一同工作的同志对本研究所做的任何贡献均已在论文中 作了明确的说明并表示了谢意。 学位论文作者签名：南寺勿 签字日期：2 p 。1 年二月占日 学位论文版权使用授权书 本学位论文作者完全了解墨鲞盘堂有关保留、使用学位论文的规定。 特授权墨鲞盘堂可以将学位论文的全部或部分内容编入有关数据库进行检 索，并采用影印、缩印或扫描等复制手段保存、汇编以供查阅和借阅。同意学校 向国家有关部门或机构送交论文的复印件和磁盘。 ( 保密的学位论文在解密后适用本授权说明) 学位论文作者签名： 高扬 导师签名： 签字日期：2 砌 年z 月6 日签字日期：五岬年l 月石日 阿撕 第一章绪论 第一章绪论 纹理是在计算机图形学中一种普遍存在的视觉现象。纹理通常用来描述自然 界中具有重复性的现象，如机房中的噪声，物体移动，物体表面细节特征以及人 类的活动等等。计算机图形学的主要目标就是再现真实世界，那么纹理合成在图 像处理和动画领域上有着重要的意义。但是，由于纹理的多样性，往往很难找到 一个公认的标准来描述并合成所有的纹理。在本文中，将展示一个纹理合成框架 以及一些相关优化与扩展工作。首先简单介绍一些纹理合成相关的概念，然后介 绍纹理合成的研究现状，接着将会详细描述纹理合成的基本理论和基本算法。 本章剩余部分安排如下：在1 1 中，给出纹理两种得到普遍认可的定义：在1 2 中，详细解释纹理合成的由来和纹理合成的定义。在1 3 中，列举纹理合成的应 用；在1 4 中，简明扼要地介绍纹理合成的研究现状：在1 5 中阐述本文所做的工 作。 1 1 纹理 物体的表面细节一般具有两类特征，一类是颜色特征，如花瓶上各种非立体 的图案，墙面上的拼花图案等等。另一类是几何特征，如桔子皱褶表皮等。相应 地，基于纹理的表现形式，纹理也可分为颜色纹理、几何纹理等。我们可以去感 受纹理，却很难对纹理的精确定义形成统一的认识。一般来说，纹理中的灰度分 布具有某种周期性，即便灰度变化是随机的，它也具有一定的统计特征。霍金斯 认为纹理有三个要素：一是某种局部的序列性，在该序列更大的范围内不断重复； 二是序列是由基本部分非随机排列组成的；三是各部分大致都是均匀的统一体， 纹理区域内任何地方都有大致相同的结构尺寸。因而根据具体应用的需要，有两 种较常采用的定义： 定义l 按一定规则对元素( e l e m e n t s ) 或基元( p r i m i t i v e s ) 进行排列所形成 的重复模式。 定义2 如果图像函数的一组局部属性是恒定的，或者是缓变的，或者是近似 周期性的，则图像中的对应区域具有恒定的纹理。 纹理技术在计算机图形学、虚拟现实和计算机视觉以及真实感绘制等相关领 域中，一直受到广泛的重视，并蓬勃发展。纹理合成有着广泛的应用前景，如大 规模纹理生成，t i l e a b l e 纹理生成，背景填充，纹理压缩，特殊纹理效果制作，以 及曲面上的纹理合成等领域。 第一章绪论 1 2 纹理合成 在光滑曲面上添加纹理即纹理映射( t e x t u r em a p p i n g ) ，最早应用于曲面剖 分，由c a t m u l l 首先提出的。b l i n n 扩展了这一思路，在曲面上添加了反射和高光 效果。纹理映射一直是复杂场景的真实感图形绘制中最为常用的技术之一，它通 过纹理来表达表面丰富的几何细节和光照细节，不仅提高了绘制的效率和质量， 而且降低了场景建模的复杂度。但纹理映射通常只能在纹理空间和表面参数空间 进行一对一的映射。由于采样区域的局限性，所获取的纹理样本通常为小块纹理， 若强行将小块纹理映射到大的曲面上将导致映射后表面纹理的变形、扭曲以致模 糊不清，若采用重复映射技术则出现表面纹理接缝走样等问题。 为解决上述问题，纹理合成技术应运而生。首先是过程纹理合成( p r o c e d u r a l t e x t u r es y n t h e s i s ，p t 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 ，s b t s ) 是近年来发 展起来的新的纹理合成技术，其基本的思路是对于给定的样图，运用合适的数学 分析方法，抽取原样图中的特征数据，建立相应的数学模型；然后基于该模型做 适当的优化处理，形成中间数学模型；最后依据样图和优化后的数学模型来合成 纹理。此类方法一般包括三个部分内容即：特征提取、模型优化、纹理合成。此 类方法不仅能克服传统的纹理技术中存在的问题，而且其中涉及的思想对其他相 关领域的研究也有一定的指导意义。因而受到越来越多的关注，成为计算机图形 学、计算机视觉和图像处理领域的研究热点之一。利用s b t s 技术还可以应用到 图像的压缩传输、缺损图像的填充等领域；如将该技术中的思想应用到计算机动 画领域，则可利用一段简短视频图像，生成时域内任意长度的非重复的视频动画 等。因此基于样图的纹理合成技术不仅在大规模场景的生成以及真实感图形绘制 和非真实感绘制( n o n - p h o t o r e a l i s t i cr e n d e r i n g ，n p r ) 等方面，而且在图像编辑、 数据压缩、网络数据的快速传输和视频等领域也有很强的应用前景。 基于样图的纹理合成技术经过若干年的发展，已在以下3 个方向上取得较大 进展。第一个方向是基于m a r k o v 随机场模型的样图纹理合成技术，将m a r k o v 数 学模型应用虱j s b t s 领域的思想是f l j e f r o s 等人 1 首先提出，由于该模型很好地抽 象出纹理视觉上相似性的数学特征，使其成为样图纹理合成技术的基础模型，许 多后续算法都基于这一模型 1 7 1 。第二个方向是任意曲面上的纹理合成，需要解 决的主要问题是如何有效地在样图和目标曲面间建立一对多的对应关系。为建立 这种对应关系，不仅需要有效而合理地提取样图的纹理特征，而且需对目标曲面 第一章绪论 进行矢量化处理，然后通过高效的搜索在样图和目标曲面之间进行匹配。基于上 述思路的算法有 1 7 。第三个方向是逼真显示的纹理合成，要合成逼真显示的纹 理，不仅需要抽取纹理的微观结构特征，而且还要表现由于空间的颜色和反射率 的变化引起的显示变化。p o r t i l l a 和s i m o n c e l l i 提出用b t f ( b i d i r e c t i o n a lt e x t u r e f u n c t i o n ) 来描述，t o n g 等人基于b t f 提出相应的算法，取得了理想的显示效 果。 1 3 纹理合成应用 纹理合成在计算机图形学，图像处理和计算机视觉方面都有着广泛的应用， 主要有五个方面： 绘制 在绘制领域，无论是表面法向量扰动( 凹凸映射) ，还是表面几何变形( 位 移映射) ，纹理可以模拟绝大部分真实物体的表观细节。在笔墨特别是在钢 笔化风格中，纹理还可以表现物体的色调，阴影和格调 8 ，9 】。 动画 计算机生成的动画通常会包含脚本事件和随机性的运动。脚本事件往往是非 重复的动作，如开门或捡拾物品，这些往往可以通过直接控制来实现。相反，随 机性的运动往往是重复性的背景运动，如海洋波浪、袅袅升烟或熊熊篝火。这种 在时空上不定性扩展的变化通常被称作时间纹理 1 0 。使用传统的技术，很难在 物理模型上绘制时间纹理，因为在不同的物理过程中，产生的表观特征也很不相 同。如果将其视为纹理，就可以采用某种纹理合成算法进行建模并生成相应的纹 理。 除了时间纹理外，具有隅接关节的特定移动也可使用一维纹理来建模。这种 纹理可以用来表现如眨眼、人物走动等精巧动作。 压缩 图像往往用来描述自然场景的，而它们往往是大规模纹理的区域，如一大片 草地或一块沙滩。使用传统的基于转换的压缩技术( 如口e g ) ，压缩往往得不 到很好的效果，因为纹理中通常包含显著的高频信息。但是，在预处理中对这些 纹理区域进行分割，然后使用纹理合成技术，就会得到比较满意的压缩效果。此 外，纹理合成技术还可以应用到大规模纹理数据的场景合成中f 1 1 】。 修复和编辑 有时候，在照片、电影和图片上可能会含有瑕疵。瑕疵可能是扫描照片上的 模糊区域，可能是电影胶片上留下的电线或道具，也可能是图片上一个不想要的 物体。既然导致这些瑕疵的过程是不可逆的，所以需要一种可修复瑕疵的算法。 第一章绪论 因为所谓的瑕疵大多数情况下都在处于同一个纹理区域中，则可以使用纹理合成 技术来替换瑕疵【l ，1 2 1 。 计算机视觉 许多计算机视觉应用都采用了纹理，如分割，识别和分类。这些应用都是基 于某种纹理模型的，而这些纹理模型大多数都是基于某种成功的纹理合成算法衍 生出来的。 1 4 研究现状 在纹理合成研究的早期，纹理合成主要作为图像处理的一个分支。纹理合成 往往通过一些复杂的数学模型和数学工具来实现的，这种方式使纹理合成很难进 行优化。在1 9 9 5 年以后，很多学者不再使用复杂的图像处理工具，转而使用简单 的数学模型，效果却大大改进。h e e g e r 2 建立图像金字塔，使用了直方图一致化 技术，而d eb o n e t 5 2 1 采样的方法是从样图中寻找特征匹配点填入合成纹理中。 后来，马尔可夫随机场( m r f ) 的应用较为广泛，e f r o s 1 对合成纹理中的某点， 采用匹配查找的方式，从原纹理中寻找与此点的邻域相匹配的点。w e i 4 】在 e f r o s 1 基础上进行了改进，使用扫描线的合成顺序，l 形固定大小的临域，同时 利用图像金字塔和t s v q 进行加速。很多人沿此思路跟进，a s h i k h m i n 5 改变了 匹配点的确定方法，不再是大范围的比较查找，而是采用一种“邻域候选点”的方 法，另一个创新是可以通过一幅t a r g e tm a p 来影响合成结果。h e r t z m a n 5 0 对 t a r g e t m a p 这一点进行了极力的发挥，提出“i m a g ea n a l o g i e s ”的思想，实现了各种各样 的合成效果。可以用来产生很多图象特效。z e l i n k a 5 3 提出了 j u m pm a p ”方法， 可看成a s h i k l a m i n 5 方法的加速，进行了纹理预处理，将可能的邻域跳转存为一 张表。h a r r i s o n 5 4 在纹理合成的顺序上下工夫，先合成优先权高的点。w e i 3 7 研究o r d e r - i n d e p e n d e n t 纹理合成方法。t o n i e t t o 5 5 提出一种方法，可使合成纹 理的纹元大小产生渐变效果。x u 2 8 提出块乱贴方法，遵循某种数学规则来贴纹 理块，块间的重叠区进行融合。e f r o s 7 利用块的重叠区作为选块的依据，仍然 采用了m i 强。 纵观纹理合成的近期发展历史，可以大致把目前主流的纹理合成算法分成两 类：区域生长和全局优化方法。区域生成算法在每次迭代时，只生长出一个像素 或- - , b 块纹理，并在生长时保持纹理的一致性【4 ，7 。但缺点是，错误会随着纹 理的生成不断累积，最终导致纹理合成的失败。而全局优化方法则不同，它首先 针对整块纹理制定一个衡量标准，如相似度，然后在相关标准下，合成整块纹理。 不过大多数现有的全局优化方法，要么因使用像素级交互技术而无法捕获结构化 纹理中的全局信息 2 ，3 0 ，要么使用过于复杂的方程式而难于优化 3 1 ，5 l 】。本 第一章绪论 文提出的算法采用马尔可夫随机场( m r f ) 作为纹理合成模型，通过采用多分 辨率多尺度的方式，可以得到一种介于区域生长和全局优化之间一种纹理合成方 式。本文的方案设计简单，使用标准的图像处理操作且是基于标准纹理框架的扩 展( 本文下面会提到) 。该算法的内核是一个基于马尔科夫随机场的纹理合成质 量评价函数，那么纹理合成问题就很自然地转换为能量最小化问题，可以很好地 抑制迭代局部极值。 1 5 本文工作 本文的主要工作分为以下三个方面： 1 设计并实现了一个基于m r f 和样图的纹理合成算法合成架构。 该架构是一个开放的架构，简单灵活，主要由两个相对独立的模块组成，多 分辨率和匹配查询。多分辨率即为多分辨率图像金字塔，算法的开始和结束分别 是多分辨率图像金字塔初始化创建( b u i l d l m a g e p y r a m i d ) 和最终结果的构建 ( r e e o n l m a g e p y r a m i d ) 。最终结果的构建一般都很简单，因为合成最高分辨率 的图像就可以作为最终结果返回。在构建金字塔时，可以采用各种方案，如高斯 金字塔 3 8 】，拉普拉斯金字塔 2 ，可控金字塔 2 ，3 1 等。本文在算法中采用了高 斯金字塔。在高斯金字塔中，除了最高分辨率那层，其它每层都是通过连续的滤 镜操作和缩减操作( d o w n s a m p l i n g ) 后，得到原始图像的模糊版本。匹配查询来 确定样图中哪个邻域是最匹配的，最简单的方式就是暴力搜索，也就是遍历整个 邻域集找出最优的。 i 2 提取纹理特征，优化合成算法内核。 在本文中，视纹理为空间上分布的信号序列。成功提取信号的特征是纹理合 成成功的前提。将纹理能量最小化做为合成的基本基石，为了达到优化目的，在 本文中还攫取了像素颜色值，梯度，空间频率等信息。像素颜色值是纹理合成的 基本参数。通过引入梯度，相当于为纹理合成过程加入高通滤波，提高了纹理合 成质量。此外，动态空间频率检测为临域尺寸设置提供参考值，可以在适当的场 景中使用适当的邻域尺寸。 3 匹配查找加速。 基本算法框架中使用的是暴力搜索，这会使速度急剧下降。据实验统计，如 果使用暴力搜索来合成一张5 1 2 x 5 1 2 的纹理，至少需要1 2 天时间，其中查询占 用时间达9 5 以上。如果把领j 或n ( p ) 看成一个多维空间中数据的话，可将所有邻 域投射到多维空间中，那么当前查找问题就转化成了一个最近邻搜索问题 4 8 。 向量化树结构( t r e e s t r u c t u r e dv e c t o rq u a n t 础i o n ，t s v q ， 4 7 】) 就是一种著名的 最近邻搜索技术，其可以大大加速纹理合成中的查找过程。本文实现 7 t s v q 和 第一章绪论 k - d 树两种树形加速结构，同时对加速的结果和不加速的结果进行比较。 1 6 文章结构 本文剩余章节的安排如下：在第二章中，详细介绍目前的纹理合成发展状况 及主要学术分支：在第三章中，着重描述基于m r f 的纹理合成算法架构中的技 术细节；在第四章中，主要展示针对基本算法框架所做的纹理特征分析工作；在 第五章中，对扩展算法进行加速并对实验结构加以分析；在第六章中，对本文的 算法进行总结得出一定结论，并指出未来工作的方向。 第二章纹理合成研究现状 等二章纹理合成研究现状 多年来，纹理合成一直是活跃的研究领域。很多学者对纹理提出了多种纹理 分析与合成算法。此外，经实践证明，纹理合成采用的模型也可应用于图像处理， 计算机视觉等领域。本章节主要讲述纹理合成的发展现状，纹理分析常用模型和 技术，以及基于样图纹理合成技术的目前发展方向。 本章安排如下：在2 1 中，讲述一下纹理合成发展历史中的三个阶段；在2 2 中，举目前常用的纹理分析方法；在2 3 中，介绍一些基于m r f 模型的纹理合成 算法中的一些概念；在2 4 中，介绍任意曲面上的纹理合成；在2 5 中，介绍逼真 显示的纹理合成。 2 1 纹理合成历史 自1 9 5 0 年g i b s o n 1 3 提出纹理的概念以来，纹理合成技术的发展历经三个主 要阶段。第一个是纹理映射阶段，因为该技术没有特征提取和模型优化，只是把 样图直接匹配到目标表面，所以可看成是简化的基于样图的纹理合成；第二个阶 段是过程纹理合成阶段，虽然该技术没有直接利用样图，但是在构造物理仿真模 型时需要深刻认识样图纹理的物理特征，再依据此认识来构造相应的物理仿真模 型，由于该技术隐藏了特征提取，并强化了模型构造和优化，因而是近似的基于 样图的纹理合成；第三阶段是基于样图的纹理合成，该技术目前发展很快，取得 了很好的效果。下面详细介绍纹理合成的三个阶段。 2 1 1 纹理映射 纹理映射作为应用于真实感图形绘制中的一项常用技术，首先由c a t m u l l 算法 提出 1 4 】，改进的方法有很多，其目标是减少或避免拼贴引起的接缝和扭曲。基 于能量最小化的思想先后提出了多种改进 1 5 1 7 1 ，p e d e r s e n 提出了一种在隐式曲 面上通过用户交互实现映射的方法。针对纹理映射中的纹理走样问题，先后提出 很多纹理反走样改进算法【3 ，5 】。b l i n n 1 8 提出利用扰动函数来生成凹凸效果的纹 理。 2 1 2 过程纹理 纹理映射( p t s ) 虽然简单，但是可改进的空间不大，于是出现了过程纹理 合成。p e r l i n 1 9 和p e a c h e y 2 0 提出了固体纹理函数( s o l i dt e x t u r e ) ，固体纹理在 模拟雕刻表面时取得了较好的效果。p e r l i n 1 9 还引进了三维的噪声函数，可以对 水波、大理石等进行很好的模拟，w o r l e y 2 u 对噪声函数进行改进，提出了c e u u a r 噪声函数，可用于模拟水波、宝石。n e y r e t 和c a n i 2 2 提出了一种新的生成少量 的三角片的方法，实现纹理拼接。采用一个基本的r e a c t i o n d i f f u s i o n 方程，w i t k i n 第二章纹理合成研究现状 和k a s s 2 3 模拟了许多种纹理，如毛发、云雾等。t u r k 2 4 i e 明了r e a c t i o n d i f f u s i o n 的模拟可以直接在多边形表面进行，实现无缝的拼接。f l e i s c h e r 2 5 等人实现了 鳞状和刺状纹理的仿真。w a l t e r 和f o u m i e r 2 6 采用细胞分裂的方法可以模拟许多 动物的纹理。 2 1 3 基于样图的纹理合成 p t s 虽然可以获得良好的效果，但对每一种新的纹理都需要调整参数反复测 试，非常不便。纹理本身具有的局部相似性，这启发了人们着手研究基于样图的 纹理合成方法：给定一小块纹理，生成大块相似而连续的纹理。s i m o n c e l l i 和 p o r t i l l a 利用统计的方法，通过可控的金字塔进行纹理合成，对多种纹理都取得了 理想的效果。h e e g e r 和b e r g e n 2 利用拉普拉斯和可控的金字塔进行纹理合成。 d e b o n e t 也利用多尺度的金字塔进行纹理合成，他采用两个拉普拉斯金字塔及滤 波器处理纹理，在查找匹配时，考虑已合成的父层的点，从符合条件的待选点中 随机选一个填写。e f r o s 和l e u n g 1 提出了一种更直接的方法，先在待合成图中设 置一些种子，然后通过给定的邻域在样图中查找匹配点，从中随机选取一个进行 填写。w e i 和l e v o y 也提出了类似的算法，并采用多尺度模型进行匹配，利用矢 量量化方法极大地加速了合成过程。在2 0 0 1 年的s i g g r a p h 会议上，又有多篇文 章提出了各自的纹理合成算法。e f r o s 6 提出了一种基于块拼贴的纹理合成算法， 通过查找误差最小的路径实现各块的拼贴，对一些纹理取得了非常好的效果。 w e i 等人提出的方法与t u r k 2 7 类似，也采用了多尺度的方法进行曲面纹理合成， 合成的质量很高。y i n g 等人提出的两种算法直接在曲面上合成纹理。 2 2 纹理分析方法 尽管目前基于样图的纹理合成技术很多，但其基本的思路都可以概括为：特 征提取、模型优化、纹理合成。对照这个思路，把现有的基于样图的纹理合成技 术，按照其不同的侧重点，可以分成三个阶段：早期使用统计方法，几何方法； 中期多为基于模型的方法；现在处于研究主流的有三种，一种是基于马尔可夫数 学模型的改进：一种是在纹理合成的目标选择上，侧重于任意曲面；一种是模型 优化过程中为实现逼真显示而采取相应的特殊处理。 2 2 1 统计方法 直观上，纹理可以看成空间上的灰度级内的分布。因而，统计特征的使用是 最早在计算机视觉文献中提出的。有关统计方法的学术文献很多，不过大致可以 分成两种基本类型。一种是灰度级同现矩阵( g r e yl e v e lc o - o c c u r r e n c em a t r i c e s ， g l c m ) ，另一种是自相关函数( a u t o c o r r e l a t i o nf u n c t i o n ) 。在本文中，使用下 式表示一幅n x n 的图像： ，g ，少) ，o 工n 一1 ，0 s y n 一1 ) 8 公式( 2 1 ) 。第二苹纹理合成研究现状 灰度级同现矩阵 空间分布的灰度级图像属性往往跟二级统计信息有关。h a r a l i c k 建议使用 g l c m ，这种技术已经成为目前最为广泛使用的纹理特征。 对于具有g 个灰度级的图像，受位移矢量控制的灰度级同现矩阵的行列表示 各个灰度级，矩阵元素反映两种灰度在相距一定距离的位置上同时出现的次数， 具体按下式计算： 另( f ，) = ( ( r ，s ) ( f ，v ”：，o ，s ) = f ，( f ，v ) = _ ) o ，s ) ，( f ，y ) n x n ，( f ，v ) = ( ，+ 出，j + 砂) o 1 2 公式( 2 - 2 ) 图2 一l ：左边为一幅5 x 5 的图像，具有三个灰度级，右边为灰度级同现矩阵，位移矢量d = ( 1 - 1 ) l010lo1o 010l0lol l 010 l01o 0l0l ol01 l0l0lolo olol0l 01 l0l0l0l0 ol0iol0l 击圈：) i j d = ( 1 ，1 ) “n p i j 】 嘉日? i j d = o ，0 ) u , 拍：jp i j 图2 - 2 ：左边为棋格图像，中间为位移矢量为d = ( 1 , 1 ) 的灰度级同现矩阵，右边为位移矢 量为d = ( 1 ，o ) 的灰度级同现矩阵。 如图2 1 和图2 2 ，灰度级同现矩阵在一定程度上反映了纹理图像中各灰度级 在空间上的分布特性，如果灰度级同现矩阵集中于对角线上，则对应位移矢量接 近于该纹理中基元的排列规则在灰度级同现矩阵的基础上，可定义多种纹理特 征。基于灰度级同现矩阵的纹理特征是纹理分析领域中广为人知和最经常采用的 9 第二章纹理合成研究现状 特征之一，主要用于纹理分类，在纹理分割中使用较少。h a r a l i c k 建议了一些比 较实用的基于灰度级同现矩阵的纹理特征，表2 一l 列举了其中的一部分。 表2 1 ：灰度级同现矩阵的纹理特征 纹理特征公式 熵( e n 仃o p y ) - z 乃( f ，j ) l o g p d ( i ，j f ) i j 能量( e n e r g y ) 巧( j ，_ ) i j 对比度( c o n t r a s t )- z ( i - j ) p a ( f ，_ ，) i j 均匀度( h o m e g e n e i t y ) 一军手粥 z z ( i 一以渺一y ) p a ( i ，) 相关性( c o r r e l a t i o n ) i i o l o ， 在灰度级同现矩阵中，位移矢量是定义灰度级同现矩阵的重要参数，但缺乏 选择位移矢量的有效方法。不过其仍处于发展中，有人提出自适应多尺度灰度级 同现矩阵( a d a p t i v em u l t i s c a l eg l c m ) ，应用于种子区域增长。另一方面，有人提 出基于遗传算法的g l c 特征提取( g e n e t i ca l g o r i t h mb a s e dg l c f e a t u r ee x t r a c t i o n ) ， 从而达到用遗传算法实现高斯加权优化的目的。 自相关函数 许多纹理的一个重要的特性就是图像中纹理元素的周期性。一个图像的自相 关函数就是用来评估纹理规律性以及纹理的精密度的。 图像的自相关函数( a u t o c o r r e l a t i o nf u n c t i o n ) 定义如下： bg，y)：豳i毒v-xl毒w-y：竺二兰竺：三二：二! 公式。2 3 ， 丽1 ，2 0 ，y ) 自相关函数的周期性反映纹理基元重复出现的周期性，其下降速度反映纹理 基元的粗细度( c o a r s e n e s s ) ：纹理粗，则缓降；纹理细，则速降，如图2 3 。规则纹 理的自相关函数具有峰值和谷值，可用于检测纹理基元的排列情况 1 0 第二章纹理合成研究现状 ( 固 ( 固 l l - ( d- l i ：dl i 图2 3 ：纹理粗细度与自相关函数的关系。左边的纹理重复单元比较粗大，故自相关函 数曲线的坡度就比较缓和：右边的纹理重复单元比较细小，故自相关函数的坡度就比较陡峭。 t 讨 图2 _ 4 ：自相关函数于f o u r i e r 变化对比示意图。左图是规则纹理的f o u r i e r 对数谱， 右图是自相关函数三维曲线 如图2 - 4 所示，自相关函数与f o u r i e r 变换存在联系。事实上，自相关函数可在 频域中计算，而且效率更高。本文就是使用这种特性来计算纹理的空间重复性的。 2 2 2 结构方法 结构方法认为纹理基元的规则排列构成纹理，因此根据基元来分析与合成纹 理，包括两种策略： 1 计算各个基元的统计特征，作为纹理特征，如平均强度、i 面积、周长、方 向、离心率 2 基于基元组合规则分析与合成纹理：图模型、树文法等等。 结构方法的主要问题是纹理基元的提取，常利用纹理区域灰度一致的特点， 用多尺度l o g 滤波进行提取。 2 2 3 基于模型的方法 在基于模型的纹理中，需要建立纹理图像的参数模型，该模型不仅可以用于 表示纹理，而且可以用于合成纹理。纹理合成主要采用基于模型的方法。基于模 第二章纹理合成研究现状 型方法的主要问题是估计模型参数，使根据模型合成的纹理图像逼近原纹理图 像。目前主要有两种模型：m a r k o v 随机场( m a r k o vr a n d o mf i e l d , o rg i b b sr a n d o m f i e l d ) 和分形( f r a c t a l ) 。 马尔可夫随机场( m r f ) m a r k o v 随机场是图像建模的重要工具，在纹理合成、纹理分析、图像分割、 图像增强、图像压缩中有着广泛应用 首先介绍一下标记( 1 a b e l i n g ) 集合的概念。标记集合，是一种位上可能发生 事件的集合，可以是连续的，也可以是不连续的。标注是为位集合中的每个位指 定一个标志的过程，可以认为是在位集合和标志集合之间建立一种映射( 如图2 5 所示) ： 嘏 蓄 ：菱 j 水 爿疹 妥更 、 一 图2 5 ：位集合和标志集映射示意图 厂= ( 工，六，a ，无，) f ：s - - - - yl 标注就是从如下f 空间中导出珀勺过程： f = 厶2 匕，当厶= 三2 = a = 三，时，f = l 公式( 2 - 4 ) 在图像领域中，标注可理解为一幅图像，则是全部可允许图像的集合显然， 如果没有任何约束，标注是没有意义的。标注也被称为着色( c o l o r i n g ，数学规划) 或配置( c o n f i g u r a t i o n ，随机场) 。如果各个位为随机变量，则位集合称为随机场。 在随机场中，从f 导出珀勺过程就是确定f 出现的概率，即各个位标注值的联合概 率。假设各个位的标注是彼此无关的，则有 尸u ) = n 尸) ，尸l 扔。) ) = 尸) 公式( 2 5 ) 实际应用时，需要考虑上下文约束。当且仅当以下两个条件满足时，随机场 为m a r k o v 随机场： 尸杪) 0 正性( p o s i t i v i t y ) p 0i 铍却 ) ) = p i ) m a r k o v 性( m a r k o v i a n i t y ) 公式( 2 6 ) 可以看出，在m a r k o v 随机场中，每个元素的值只受近期值的影响。m a r k o v 1 2 第二章纹理合成研究现状 随机场是m a r k o v 随机过程的推广，除了考虑历史信息的影响外，还考虑未来信 息的影响。在图像处理领域，通常有两种概念来诠释图像中的m a r k o v 随机场： 一种是临域( n e i g h b o rs e t ，如图2 - 6 ) ，通常临域集有一阶域( 四连通) ，二阶 域( 八连通) 等；另一种是团( c l i q u e s ，如图2 7 ) ，是由邻域关系限定的位子 集，有单位 羽( s i n g l e - s i t e ) ，双位 圃( p a i r - s i t e ) ，三位n ( t r i p l e s i t e ) 等。下面给出 临域和团的直观形象。 田 吕j 4e z12 ax土 a 2i2 暑3e ( a )( b )( c ) 图2 - 6 ：邻域示意图。( a ) 是一阶域( 四连通) ，( b ) 是二阶域( 八连通) ， ( c ) 是三阶域( - - 十四连通) 。 口 a ) 田日 b 一 由昭出甲田 图2 7 ：团示意图。( a ) 是一位团，( b ) ( c ) 是二团，( d ) 是三位团，( e ) 是四位团 有许多种不同的m a r k o v 随机场纹理模型，其中比较著名的有d e r i n - e l l i o t t 模 型，自二项( a u t o - b i n o m i a l ) 模型。这两种模型是采用了单个图像象素，双位团， 二阶邻域的m a r k o v 随机场模型，那么它们的能量的吉布斯域为： 1 w u ( 厂) = 去训，矽 比，) = h k h n ) p = 瞳，幺，岛，幺】r 其中口是控制参数 公式( 2 7 ) 第二章纹理合成研究现状 w ，) = v ，z 。) + v ，丘，) 1 ，4 那么有d c r i n e l l i o t t 模型： r l ，口= b v g ，6 ) = l i 1 ，a b 自二项模型：w r ) = v ，z 一，) + v ，z ”) 1 ，4 公式( 2 8 ) 公式( 2 9 ) 在纹理合成中，通过选择不同的参数，可以合成不同的纹理图像，也可从真 实图像中估计参数，使合成图像逼近原始图像。在纹理分析中，首先估计参数， 然后或者用估计的参数作为纹理特征矢量，或者用估计的参数合成纹理图像，作 为特征图像，以实现纹理分类或分割。 分行算法 很多自然表面上，在不同尺度下都有一定程度上的自相似性。分行算法擅长 于针对这些特性进行建模，并且越来越受欢迎。首先介绍一些基本概念 自相似性( s e l f - s i m i l a r i t y ) 与分形维( f r a c t a ld i