（信号与信息处理专业论文）基于样图的纹理合成技术及其应用研究.pdf

武汉理工大学硕士学位论文 摘要 基于样图的纹理合成是近年来发展起来的一种新的纹理合成技术：给定一 小块纹理，生成大块相似的纹理。它用于解决传统方法中出现的接缝、扭曲和 参数调整问题，在图像编辑、缺损图像的填充、数据压缩、网络数据的快速传 输、大规模场景的生成以及真实感和非真实感图像的绘制等方面都显示了广泛 的应用前景，受到越来越多研究人员的关注，是目前计算机图形学、计算机视 觉和图像处理等领域的研究热点之一。 本文研究了三种经典的纹理合成算法，分析了其各自的特点和不足。在结 合各自的优点基础上，设计并实现了一种改进算法。另外，还研究了纹理合成 在数字图像修复中的应用，针对现有算法的不足，提出了改进算法，通过仿真 实验证明了改进算法的有效性。本文的具体研究内容如下： ( 1 ) 研究了基于m r f 模型的纹理特征分析在纹理合成中的应用。重点研究 了w l 、a s h i k h m i n 和e f r o s 0 1 三种经典的基于m r f 模型的纹理合成算法，详细 论述了这三种算法的原理，特点以及步骤。 ( 2 ) 在研究和总结现有的纹理合成算法的基础上，根据纹理的邻域相关性相 关性，设计并实现了一种改进的纹理合成算法，通过实验证明了改进的纹理合 成算法的有效性。 ( 3 ) 研究了纹理合成算法的三个主要参数( 样本块的尺寸、重叠区域的尺寸 以及样本块的数量) 对纹理合成质量和速度的影响。在分析了实验结果的基础上， 得出了应对不同纹理合成需求的参数选取方案。 ( 4 ) 研究了基于样图的纹理合成在图像修复中的应用原理，在现有算法的基 础上，分析了修复过程的具体实现步骤，讨论了其中的关键因素( 修复顺序) 对图 像修复结果产生的影响。 ( 5 ) 通过对图像进行纹理分割的预处理来指导匹配块的搜索，以及采用新的 修复顺序来改进已有的图像修复算法。通过实验表明，改进算法在移除物体和 破损区域填充时的图像修复效果均优于已有的算法。 关键字：纹理合成，马尔科夫随机场，块匹配，图像修复 武汉理工大学硕十学位论文 a b s t r a c t t e x t u r es y n t h s i sf r o ms a m p l ei san e wt e x t u r es y n t h e s i st e c h n o l o g yw h i c hi s d e v e l o p e di nr e c e n ty e a r s i t su s e dt os o l v et h ep r o b l e m so fj o i n t 、d i s t o r t i o n , a n d p a r a m e t e ra d j u s t m e n tw h i c ha p p e a r i nt h ec o n v e n t i o n a lm e t h o d i ts h o w sa w i d e s p r e a da p p l i c a t i o np r o s p e c ti ni m a g ee d i t i n g , d a m a g ei m a g ei n p a i n t i n g , d a t a c o m p r e s s i o n , n e t w o r kd a t at r a n s m i s s i o n ，l a r g e s c a l ep r o d u c t i o na sw e l la sr e n d e r i n g o fr e a l i t yg r a p h i c sa n ds oo n i ti so n eo ft h er e s e r hh o ts p o t si nc o m p u t e rg r a p h i c ， c o m p u t e rv i s i o na n di m a g ep r o c e s s i o n i nt h i s p a p e r , w eh a v er e s e a r c h e dt h r e ec l a s s i ct e x t u r es y n t h e s i sa l g o r i t h m s ， a n a l y s i st h e i rr e s p e c t i v ec h a r a c t e r i s t i c sa n di n a d e q u a t e s a n dd e s i g na ni m p r o v e d a l g o r i t h mb a s e do nt h ec o m b i n a t i o nw i t ht h e i ra d v a n t a g e s i na d d i c t i o n ，h a v e r e s e a r c h e dt h ea p p l i c a t i o no ft e x t u r es y n t h e s i si nd i g i t a li m a g ei n p a i n t i n g ，a c c o r d i n g t ot h ei n a d e q u a c yo ft h ee x i s t i n ga l g o r i t h m s ，p r o p o s e da ni n p r o v e da l g o r i t h m t h e m a i nr e s e a r c hc o n t e n t si nt h i sp a p e rb e l l o w s ： ( 1 ) r e s e a r c ht h ea p p l i c a t i o no ft e x t u r ef e a t u r e sa n a l y s i sb a s e do nm r f m o d e li n t e x t u r es y n t h e s i s m a i n l yr e s e a c h e dt h ew l 、a s h i k h m i na n de f r o s 0 1e c tt h r e ec l a a s i c t e x t u r es y n t h e s i sa l g o r i t h m sb a s e do nm r fm o d e l ，d e s c r i b et h et h r e ea l g o r i t h m s s i m p l e m e n t a t i o ns t e p s i n d e t a i l s ，a n a l y s e t h e i r p r i n c i p l e ，d i s c u s st h e i rr e s p e c t i v e c h a r a c t e r s ( 2 ) b a s e do nt h ee x i s t i n gt e x t u r es y n t h e s i sa l g o r i t h m s ，d e s i g na n di m p l e m e n ta n i m p r o v e da l g o r i t h ma c c o r d i n gt or e l a t i o no ft e x t u r ef i e l da n dm a t c h i n gp o i n t ，p r o v e d t h ee f f c t i o no ft h ei m p r o v e da l g o r i t h m sb ye x p e r i m e n t ( 3 ) d i s c u s st h et h r e em a i np a r a m e t e r s ( b l o c ks i z e ，o v e r l a ps i z e ，s a m p l en u m b e r ) s e f f e c t i o nt ot e x t u r es y n t h e s i sq u a l i t ya n ds p e e d a n db y a n a l y s et h ee x p e r i m e n tr e s u l t s ， g e tt h ep a r a m e t e r ss e t t i n gs u g g e s t i o na c c o r d i n gt od i f f e r e n td e m a n d s ( 4 ) r e s e a r c ht h et s f s sa p p l i c a t i o np r i n c i p l ei ni m a g ei n p a i n t i n g ，b a s e do nt h e e x i s t i n ga l g o r i t h m ，d e s c r i b et h ea l g o r i t h m s sd e t a i l si m p l e m e n t a t i o ns t e p s ，d i s c u s s i n p a i n t i n go r d e r se f f e c t i o nt oi n p a i n t i n gr e s u l t h 武汉理工大学硕士学位论文 ( 5 ) g u i d et h es e a r c ho fm a t c h i n gb l o c k sb yt e x t u r es e g m e n tp r e t r e a t m e n t ，a n d a p p l yt h en e wi n p a i n t i n go r d e rt oi m p r o v et h ee x i s t i n ga l g o r i t h m t h ee x p e r i m e n t s h o w st h a t ，t h ei m p r o v e da l g o r i t h r ni sb e t t e rt h a nt h ee x i s t i n ga l g o r i t h mw h e nr e m o v e t h eo b j e c to rf i l lt h ed a m a g er e g i o n k e yw o r d s ：t e x t u r es y n t h e s i s ，m a r k o vr a n d o mf i e l d ，b l o c km a t c h ，i m a g e i n p a i n t i n g i l l 独创性声明 本人声明，所呈交的论文是本人在导师指导下进行的研究工作及取得的研 究成果。尽我所知，除了文中特别加以标注和致谢的地方外，论文中不包含其 他人已经发表或撰写过的研究成果，也不包含为获得武汉理工大学或其它教育 机构的学位或证书而使用过的材料。与我一同工作的同志对本研究所做的任何 贡献均已在论文中作了明确的说明并表示了谢意。 关于论文使用授权的说明 本人完全了解武汉理工大学有关保留、使用学位论文的规定，即学校有权 保留、送交论文的复印件，允许论文被查阅和借阅；学校可以公布论文的全部 或部分内容，可以采用影印、缩印或其他复制手段保存论文。 ( 保密的论文在解密后应遵守此规定) 签名：廛逸煎导师签名： 矿日期： 武汉理工大学硕士学位论文 1 1 研究的背景和意义 第1 章绪论 用计算机重现现实世界是计算机科学发展的一大方向。自1 9 7 4 年c a t m u l 发明纹理映射技术以来，纹理合成成为一个重要的研究方向。最初的过程纹理 合成通过直接仿真表面纹理的生成过程来模拟物体表面精细的结构。过程纹理 合成技术对许多纹理都有非常逼真的效果。但它的计算量大，合成速度慢。对 于每一种新的纹理，都需要调整参数，进行反复的测试。给实际的操作带来不 便。 基于样图的纹理合成技术( t e x t u r es y n t h e s i sf r o ms a m p l e s ，t s f s ) 是继纹理映 射、过程纹理合成方法之后发展起来的一种新的纹理合成技术。它基于给定的 小区域纹理样本，按照物体表面的几何形状，拼合生成任意大小的纹理图像， 它在视觉上是相似而连续的。t s f s 技术克服了传统纹理映射方法的缺点，又避 免了过程纹理合成调整参数的繁琐，因而受到越来越多研究人员的关注，成为 计算机图形学、计算机视觉和图像处理领域的研究热点之一。 t s f s 技术可以用来解决传统方法中出现的缝隙、扭曲、变形和参数调整等 问题，在图像编辑、缺损图像的填充、数据压缩、网络数据的快速传输、大规 模场景的生成以及真实感和非真实感图像的绘制等方面都显示了广泛的应用l j i 景。其具体的应用如下： ( 1 ) 真实感绘制 传统的的曲面绘制采用的是多边形或三角形网格细化来实现，其效果比较 平淡。这种几何的方法不能满足人们的需求，而采用纹理合成却可以得到高质 量的绘制结果。此外，纹理还可以模拟某些物体的细节。 ( 2 ) 计算机动画 计算机生成的动画通常会包含脚本事件和随机性的运动。脚本事件往往是 非重复的动作，如开门或捡拾物品，这些往往可以通过直接控制来实现。相反， 随机性的运动往往是重复性的背景运动，如海洋波浪、袅袅升烟或熊熊篝火。 这种在时空上不定性扩展的变化通常被称作时间纹理。使用传统的技术，很难 武汉理工大学硕十学位论文 在物理模型上绘制时间纹理，因为在不同的物理过程中，产生的表观特征也很 不相同。如果将其视为纹理，就可以采用某种纹理合成算法进行建模并生成相 应的纹理。 ( 3 ) 图像压缩 很多图像中经常包含大片的纹理，如草地、森林、沙滩等。因为纹理通常 包含一些高频信息，使用j p e g 等压缩技术很难得到较高的压缩比。可以把图像 中的纹理部分先分割出来，再使用纹理合成的方法对其进行压缩，这样可以获 得较高的压缩比。这种压缩结果对于提高网络数据的传输效率有重要意义。 ( 4 ) 图像修复和编辑 图像或视频中经常有时会出现一些瑕疵( 如划痕、污点、破损等) ，严重影响 其质量和实用价值，因此，图像修补技术成为人们越来越多关注的一个热点。 纹理合成技术可在图像修补中发挥较好的作用，若瑕疵出现在图像的背景区域 或草地、海滩、水面等带有纹理性质的场景中，则可以通过约束纹理合成的方 法对其进行修补。 1 2 国内外研究现状 早期的纹理合成算法受到纹理分析思想的影响，主要采用统计的方法，并 使用多分辨率滤波器进行处理。s i m o n c e l l i 和p o r t i l l a 通过可控的金字塔模型进 行纹理合成，成功地捕获全局的纹理结构特征，对多数纹理都取得了较好的合 成效果，特别是显著提高了对结构性纹理的合成质量，但缺乏有效的对局部纹 理特征的描述，用于合成的概率模型也不明确的【l 】。h e e g e r 和b e r g e n 提出了一 种渐近的基于分析的合成算法，利用拉普拉斯和图像金字塔进行纹理合成，该 算法对随机性纹理取得了较好的效果，但对结构性纹理效果不理想【2 】；d e b o n e t 也利用多分辩率金字塔进行纹理合成，他采用两个拉普拉斯金字塔及滤波器处 理纹理图像，这种方法对结构性纹理能够取得较好的效果，但对结构不明显的 纹理容易造成人工痕迹1 3 ；h z u 等人引进了一个称为f r a m e 的数学模型，通过 特征抽取和特征融合两个过程来获得该模型，这个模型把滤波器和直方图结合 到m r f 模型中，并使用最大最小平均信息量原则来选择特征统计量，对一些纹 理( 包括一些强结构性纹理) 取得了较好的合成效果，但是时间花费也是非常惊人 的【4 】。 2 武汉理1 = 大学硕士学位论文 基于特征匹配的方法，算法往往很复杂，而且需要花费大量的合成时间， 对于很多纹理，其合成质量也不能够达到令人满意的效果。为此人们发展了基 于m r f 模型的纹理合成技术。 在9 9 年的i c c v 会议上，e f r o s 和l e u n g 提出了一种基于非参数采样的纹理 合成算法，首先在待合成图中设置一些种子，然后通过给定的矩形邻域在样图 中查找匹配点，在符合条件的待选点中随机选取一个进行填写。这种方法主要 利用了纹理图像中邻近点的相关性较强这一特征，使得合成算法能够对多种纹 理都取得不错的合成效果，尤其适用于约束纹理合成( 比如图像的修补等) 【5 】。在 s i g g r a p h 0 0 会议上，w 萌和l e v o y 也提出了类似的算法，不同的是将匹配块 邻域改成l 形，并采用多尺度模型、矢量量化方法，极大地加速了算法的合成 过程【6 】。在2 0 0 1 的3 d 会议上，a s h i k h m i n 提出了一种更简洁的算法，对自然纹 理获得了更好的合成效果，速度也很快【_ 7 1 。 在2 0 0 1 年的s i g g r a p h 会议上，又有多篇文章提出了各自的纹理合成算 法。e f r o s 提出了种基于块缝合的纹理合成算法，合成的基本单位不再是单个 像素，而是使用样本纹理图中的纹理块，要缝合的纹理块间允许有一定的重叠 区域，在重叠区域中查找误差最小的路径作为纹理块的缝合边界，实现各块的 拼接。这种方法对多种类型的纹理都取得了非常好的效果，特别是对以往算法 处理效果都不够理想的结构性纹理【8 】。微软亚洲研究院的l i nl i a n g 提出的合成 算法是一种基于块采样的方法，按照局部条件m r f 密度函数的非参数估计对纹 理块进行采样，避免了纹理块边缘特征不匹配等问题的发生。该算法能够处理 广泛的纹理类型，而且对于那些基于像素的非参数采样算法处理不好的纹理， 该算法仍能够取得理想的效梨们。 在国内，这方面的研究起始于2 0 0 0 年左右，主要研究单位有浙江大学、清 华大学、吉林大学和合肥工业大学等。国内的主要研究主要是在国外研究成果 的基础上进行探索，并做进一步的改进或应用。浙江大学的徐晓刚博士提出了 一种快速纹理合成算法【l o 】，在搜索匹配点时采用了新的搜索规则，利用螺旋线 状搜索顺序代替扫描线顺序加速匹配搜索的过程，同时采用多种子进行预填充， 其优点就是不仅能处理一般的纹理，还能根据方向性要求合成纹理图像，且合 成速度与原样图的大小基本无关。总的来说，国内的基于样图的纹理合成研究 仍处于起步阶段，目前尚未出现重大的研究成果。 3 武汉理t 大学硕+ 学位论文 1 3 本文的内容安排 本文对基于样图的纹理合成技术及其在图像修复中的应用进行研究。 本文的主要内容安排如下： 第l 章阐述了基于样图的纹理合成研究的背景和意义，描述了国内外研究 现状，并对论文的工作做了统一安排。 第2 章首先论述了纹理以及纹理合成的一些基本概念，研究了基于m r f 模 型的纹理特征分析在纹理合成中的应用。重点研究了w l 、a s h i k h m i n 和e f r o s 0 1 三种经典的基于m r f 模型的纹理合成算法，详细论述了这三种算法的实现步骤， 分析了它们的原理，讨论了其各自的特点。 第3 章在研究和总结现有的纹理合成算法的基础上，根据纹理的邻域相关 性，设计并实现了一种改进的纹理合成算法，通过实验证明了改进算法的有效 性。研究了纹理合成算法的三个主要参数( 样本块的尺寸、重叠区域的尺寸以及 样本块的数量) 对纹理合成质量和速度的影响。 第4 章研究了基于样图的纹理合成在图像修复中的应用原理，在现有算法 的基础上，通过对图像进行纹理分割的预处理来指导匹配块的搜索，以及采用 新的修复顺序来改进已有的算法。通过实验表明，改进算法在移除物体和破损 区域填充时的图像修复效果均优于已有的算法。 第5 章总结了本文所做的工作，并指出下一步的展望。 4 武议理1 人学硕十学位论文 2 1 基本概念 2 1 1 纹理的定义 第2 章纹理合成典型算法 只前对纹理( t e x t l i r e ) 图像还没有精确的定义。一般来蜕纹理可以看成是图像 中具有某种特殊性质的一个类别，是具有局部性和稳定性的随机过程的实现。 也就是说，纹理中的每一个像素点都可以由其空洲邻域内的像素的集合来表达， 并且这种表逃对每个像素都是一样的。如图2 1 所示，假设给定一张图像，但只 允许脱察者通过较小的可移动窗口( 图中黑框) 束观察它，当移动窗口时观察者可 以石到图像的不同部分，而对于纹理图像则发现观察结果是基本一致的。这罩 要提到两个概念：幽像的稳定性和局部性。图像的稳定性足指：在观察窗【】人 小合适的| j i 提下，观察者看到的部分总是相似的；图像的局部性是指：窗1 3 中 的任一像素町以山其周| _ f 爿邻域内的像素预测得到，而与图像中的剩余部分无关。 目曲认为具备了局部性和稳定性的图像称之为纹理。 懋鬻糕 武汉理1 人一学硕+ 学化论文 2 l2 纹理的分类 现实世界中物体的多样性决定了纹理形式的多样性。根据纹理特征分都的 方式小l 司，通常把纹理j ! h 略分为三类：结构性纹理、随机性纹理和既有结构性 义有随机性的中恻型纹理。结构性纹理是指含有保持纹理局部性的最小纹理块， 整个纹理叮以出一系列这样的纹理块以及它们的摆放规则来决定，例如砖墙、 地板等，如图2 - 2 ( a ) ；随机性纹理足没有确定纹理块的纹理，例如草地、沙粒等， 如图2 - 2 ( c ) ：但更多的从现实世界得到的纹理同时包含了以七两种特性，称之为 中自j 性纹理，例如石块，花丛等，如图2 - 2 ( b 1 。 秦溪黧 一囊iq 嬲。暑c ? 矗搿驴曩饕舞蚤毖磁曩匿p 謦 舅舅簟，啤一 ；寥；i 茸：，i 笤按$ 嚣螺窿匿叠谶羁糕 蔓豳回国l矗i 。咒撼；舅i ：- 霹黛强粥矗凳g 弼囝 瞌_ 囊蕊_，押确斟孟罾、0 麓i 霹髫嘶邂目2 日涔 然漤糍黼 ( a ) 结构忭纹，i 。( b ) 叶1 侧性纹理( c ) 随机性纹理 罔2 - 2 纹理的分类 2 i3 像素点的邻域和纹理块的边界 当前待合成像索点的邻域是指红合成过程叶1 ，以当时待合成像素点为c j 心 的i f 方形区域与已合成像素点的交集。样本网中缚个像索点郝有根据当前待合 成像索点所确定的邻域( 图2 - 3 ( b ) ) 。当按从尤至右、从上至下_ 的扫描线顺序含成 纹理时，对1 当前待合成像索点，h 有其 ：部和卜部的像桑是已合成的，其邻 域类似t 。母l 的形状( 罔2 - 3 ( c ) ) ，冈i 们称之为像素的l 型邻域。如果l 型邻域 i i 边k 大小为n ( 幽2 - 3 ( a ) 中的n ：方形边k ) ，称l 型邻域为n n 的l 型邻域。 正了 盔；一 蓦 武汉理i 大学硕+ 学位论文 盆麓 ( c )( d ) 图2 - 3 像素点的邻域 在基于块拼接的样图纹理合成中，通常使用方形纹理块( 图2 4 中阴影区 域所示) 。纹理块的边界指该纹理块与已合成区域重叠的部分。如图2 4 ，按 扫描线顺序从左至右，从上至下逐块合成纹理，图2 - 4 ( a ) ( b ) ( c ) 演示了合成顺 序，其中阴影块为当前待合成的纹理块，其余白色f 方形块为已合成纹理块， 粗线条轮廓区域既是当前待合成纹理块的边界也是与己合成部分的重叠区 域。 膨 ( a ) u 黝 ( c ) 图2 4 纹弹块的边界 2 1 4 像素点的邻域匹配和纹理块的边界匹配 两个像素点的邻域误筹指它们邻域中对应像素点的r g b 值误差之和，即为 i 两个像素点确定的形状相同的邻域_ v ，m 的误差所定义的厶距离， d ( ，m ) = f f ( r ( p ) - r ( q ) ) 2 + ( g ( p ) 一g ( g ) ) 2 + ( b ( p ) 一口( q ) ) 2( 2 一1 ) # 巍茄巍 武汉理工大学硕士学位论文 其中函数r ( p i x e l ) 、g ( p i x e l ) 、b ( p i x e l ) 分别表示纹理图像的红、绿、蓝三 种颜色的像素值。在基于m r f 模型的逐点合成算法中，需比较输出结果图中当 前待合成像素点与纹理样图中每一个像素点的邻域误差，在误差较小的待选邻 域中随机选择一个作为匹配邻域，此过程称为邻域匹配，由邻域匹配决定的像 素点称为匹配点。 纹理块的边界误差指：将纹理样图中某一纹理块置于结果图中当前待合成 纹理块的位置时，其与结果图中已合成区域的重叠部分( 图2 - 4 ( a ) ( b ) ( c ) 中粗线条 轮廓区域) 的厶距离，这个距离也按照公式2 1 来计算，此时m ，2 分别代表位 于重叠区域的纹理块边界和已合成区域边界。 在基于m r f 模型的逐块合成算法中，根据结果图中当前待合成纹理块的位 置，计算纹理样图中的每一个纹理块的边界误差，在误差较小的待选纹理块中 随机选择一个，其边界即为匹配边界，此过程称为纹理块的边界匹配，由边界 匹配决定的纹理块称之为匹配纹理块。 2 2m a r k o vr a n d o mf i e l d 模型 马尔科夫随机过程定义如下【1 0 】：假设一个随机过程 彳( f ) ，t t 的状态空间 为，如果对时间t 的任意刀个数值 t 2 0 ，并且 p ( z ( x i ) iz ( x a ，v 一) = p ( z ( 蕾) lz ( x s ) ，t 以，) ( 2 - 3 ) 马尔科夫随机场有两个特点：一是所有可能的状态概率非零，二是一个特 定点的局部条件概率密度函数仅仅依赖于该点的邻域内随机场的值。通常假定 纹理图像有两个统计特点：一是局部统计，即某一点的值仅依赖于其局部的邻 8 武汉理t 大学硕士学位论文 近点；二是平稳统计，即这种依赖性对于每个点都是相同的。也就是m r f 模型 认为纹理具有局部统计特，纹理中的任一部分都可以由其周围部分( a p 邻域) 完全 决定。因此m r f 模型适于描述纹理图像。 纹理合成所采用的m r f 模型是根据结果图中当前待合成像素点的邻域( 或 当前待合成纹理块的边界) ，在样本图中搜索具有匹配邻域的像素点( 或具有匹配 边界的纹理块) ，将其作为当前待合成像素点( 或纹理块) 的最佳近似拷贝到结果 图中。 m r f 模型认为纹理具有局部统计特征，即纹理中的任一部分都可以由其周 围部分( 即邻域) 完全决定，这是对纹理的一种比较客观的认识。m r f 模型是图 像建模的重要工具，在纹理合成、纹理分析、图像分割、图像增强、图像压缩 中具有广泛的应用。 2 3 基于m r f 模型的纹理合成典型算法 在基于m r f 模型合成的方法中，合成方式主要有“点匹配”和“块拼接”两种 合成方式。在基于点匹配合成的过程中，一般采用穷尽法在样图中搜索匹配点， 在符合条件的匹配点中随机选取，每次仅能合成一个像素点，合成一小块纹理 都需要花费较长时间。x u 1 等提出了随机块拼接的快速合成方法后，块拼接方 法取得到了进一步的改进，合成速度和质量都得到了很大的提高，其中有些已 经达到了实时的效果。当今，由于m r f 模型较好地体现了纹理固有的局部相关 性和稳定性，依然被广泛采用，同时块拼接合成方式由于其在合成速度和合成 质量上的优势也得到了越来越多研究人员的重视，下面对基于m r f 模型的三个 典型算法进行论述。 2 3 1w l 算法 w l 算法是一种典型的点匹配纹理合成算法，该算法实现简单，能合成的纹 理种类较多，合成质量也较高。缺点是不适合处理较多细节的自然纹理，合成 速度也比较慢。 2 3 1 1 单分辩率方法 图2 5 描述了该算法在单分辩率下合成纹理的过程：给出样本纹理，初始化 9 武汉理l 人学硕十学位论文 输出纹理，合成输出纹理。图2 - 6 是算法合成过程中不同阶段的的图像，合成时 采用l 型邻域。 裂黧瓣 ( a ) 样本纹理( b ) 初始化噪声( c ) 输出纹理 图2 - 5w l 算法合成纹理过程 麓麓黛氇 ( a ) ( i o )( c )( d ) 图2 - 6w l 算法合成纹理不问阶段 w l 算池步骤描述如下： ( 1 ) 川随机噪，打初始化输出幽像，按 ! i 扫描线顺序确定输h _ 图像中每个点的 像素值。驭出当| i 点的l 邻域，l 邻域其大小 i 用户指定。 ( 2 ) 按照h 拙线顺序逐点进行纹理合成，对于当前待合成的像素点，根据l 邻域的误差最小原则，在输入样目中找出+ 个像素点。 ( 3 ) 把缓血像素值拷叭至待合成的像素点。重复卜述过程，卣到图像全部合 成好。 邻域一般设置为边长为奇数的谁方形，图2 - 6 中邻域的大小为5 5 。一般地， 为保汪合成质量，l 型邻域大小的设置麻该覆盖基本纹元的尺寸。当l 型邻域尺 寸增大时，合成质量也更高，但是也成倍增加合成时问。 231 2 多分辩率方法 多分辨率合成方法通过建市幽像余字塔，利用较低分辨率的图像来获得纹 理的宏观特征，并存此辈础上合成高分辨率的图像。山1 ：合成低分辨率的罔像 武汉理工大学硕士学位论文 所采的l 邻域较小，故可以减小邻域的采样范围，达到减少纹理合成时间的目 的。 算法步骤描述如下： ( 1 ) 按照同样的比例分别在样图和噪声图像中建立图像金字塔。 ( 2 ) 使用单分辩率的方法，首先合成图像金字塔的最低分辩率层。邻域的设 置与单分辩率下相同，使用l 型邻域。 ( 3 ) 按照分辩率由低到高的顺序合成每一层图像，直到最高分辩率层合成结 束。使用多分辩率邻域，当前要合成的像素邻域包括两部分：该层中的l 形部 分和上一层的方形部分。 2 3 2a s h i k h m i n 算法 a s h i k h m i n 算法是w l 算法的进一步改进，该算法利用相关性的原理，把纹 理的搜索范围限制在当前点领域，如图2 7 所示，大大减少了搜索空间，有效地 提高了纹理合成的速度，使合成速度基本与样图大小无关。a s h i k h m i n 算法对于 自然纹理的合成能取得了比较好的效果。 已合成区域 。a ，。 昏 幛 旧b p 醉 、 c ( a ) 输入图像( b ) 输出图像 图2 7a s h i k h m i n 算法的候选点 该算法的基本思想就是根据l 型邻域点在样本纹理中的对应位置( 如图2 7 中箭头所示) 偏移相应量获得候选点。以输出图像中当前点p 的右上角邻域点a 为例，a 在样本中的匹配位置为b ，根据空间偏移得到待选点c 。如果候选点超 出了有效地区域，则随机取一个位于有效区域内的像素点代替。最后比较各候 选点邻域与当前点的邻域误差值，选取邻域误差最小的点作为匹配点，把它的 武汉理工大学硕+ 学位论文 像素值拷贝到当前待合成像素点的位置。 a s h i k h m i n 算法步骤描述如下： ( 1 ) 用随机噪声初始化输出图像。 ( 2 ) 对当前待合成点，根据其邻域得到原样图中的后选点集合，从集合中找 到最合适的匹配点。 ( 3 ) 更新此合成点在输入样图中的来源。 ( 4 ) 重复步骤2 ，当所有像素点都合成好则结束。 a s h i k h m i n 的算法很直观，也很简单，在合成速度上比w l 算法要快，算法 的复杂度与w l 算法差不多。该算法对自然纹理的合成取得了很好的效果，如 草地、沙石等，但对于结构性较强的纹理，合成质量不如w l 算法，其主要原 因是相关性度量的范围过窄，把搜索范围限制在当前点的邻域，对许多边界比 较明显的结构性纹理，此相关性度量范围相对过小。另外，该算法也不能处理 诸如云、波纹等平滑感较强的纹理。 2 3 3e f r o s 0 1 算法 e f r o s 0 1 算法一种块拼接的纹理合成算法，与以往的点匹配算法相比较，该 算法在纹理合成的速度、合成结果的视觉效果方面都得到了很大的提高，避免 了以前算法容易引起的模糊、纹元错位等问题。 ( a ) 最小误差路径( b ) 最优路径示意图 图2 8 重叠区域的最优分割 1 2 武汉理工大学硕士学位论文 在输入样图中任取一块墨放在输出图中，然后在输入样图中查找垦，使垦 放入输出图后与e 有一定的重叠区域，且边界匹配误差控制在一定的范围内； 接着8 ，及的重叠区域找出一条误差最小的路径作为反的边缘，把展贴入合成 图( 如图2 8 ( a ) 。反复重复以上过程直到获得整个结果纹理图。 误差最小的路径通以下方法进行计算：设e ，垦具有垂直的重叠边，重叠 区域为群”，巧，误定义为d ( 群7 ，蟛) 。通过式2 4 获得重叠区最后一行的各点 误差。 互，= 弓，+ 商n ( 互吐，骂- i ，- i ，巨l ，_ ，+ i ) ( 2 - 4 ) 在获得误差最小的一点后，通过反向跟踪便可获得最优切割路径。水平方 向重叠可以采用类似的方法获得。当水平与垂直方向都有重叠时，两条路径会 有交，此时分割边界由两条路径共同决定。从以上的描述可知，算法简单且速 度快，合成效果好。该算法存在的问题是有时会出现纹理块的重复效应，有些 边不匹配。 e f r o s 0 1 算法步骤描述如下： ( 1 ) 按照扫描线顺序逐块合成输出纹理。 ( 2 ) 在输入图像中搜索符合条件的匹配块，从中随机选择一块。 ( 3 ) 计算选取的纹理块和已合成块重叠区域的误差，找到最佳分割路径作为 新纹理块的边界，将新纹理块贴入到合成图中。 ( 4 ) 重复以上过程，直至合成结束。 e f o r s 0 1 算法实现简单，合成速度快，对许多纹理的合成质量也较好。该算 法的缺点是当样本纹理较小时，会产生过多的重复，合成的纹理视觉上感觉生 硬。对很多自然纹理如草地、水波纹等因为产生边界不匹配，造成合成质量不 理想。 2 4 本章小结 本章介绍了基于样图的纹理合成的基本概念，研究了基于m r f 模型的纹理 特征分析及其在纹理合成中的应用，重点研究了三种典型的基于m r f 模型的纹 理合成算法( w l 、a s h i k h m i n 、e f r o s 0 1 ) 的原理、实现步骤、分析了其各自的特点 等。这些为后面的研究分析奠定了理论基础。 1 3 武汉理工大学硕士学位论文 第3 章块拼接的纹理合成算法 通常为了准确地获取纹元大小特征，纹理合成算法的匹配邻域大小设置需 要覆盖基本的纹元。这意味着，对于纹元较小的纹理，可以用小的邻域去匹配； 而对于纹元较大的纹理，需要大的邻域去匹配。而大的邻域会带来大的计算量， 增加了匹配搜索的时间。w l 算法的多分辨率方法使用多分辩率图像金字塔来解 决这个问题，通过多分辨率的“邻域扩张效应，减小邻域的采样范围，达到 减少纹理合成时间的目的。另外，从徐晓刚得螺旋状点匹配算法【1 6 】可知，利用 了纹理的相关性原理，将匹配点的搜索范围限制在前一个已合成像素点的邻域， 可以避免的整幅图像的全局搜索，可以提高匹配搜索效率。 本文将多分辩率合成思想和纹理相关性原理用于基于块匹配的纹理合成算 法中，设计了一种块拼接的纹理合成算法。 3 1 算法原理 在深入研究已有的纹理合成算法基础上，本文设计了一种块拼接的纹理合 成算法，借鉴了w l 多分辩率方法的思想，采用多分辩率图像金字塔来减小邻 域的采样范围，并使用螺旋状匹配块搜索策略寻找匹配块，在保证纹理合成质 量的同时，减少了纹理合成的时间。本文算法简述如下： ( 1 ) 通过为输入纹理图像建立图像金字塔，较低分辨率的纹理图像获得合成 纹理的宏观特征，利用合成好的低分辨率纹理图像来合成高分辨率纹理图像图 像。由于合成低分辨率的图像的纹理快边界较小，故可以减小计算量，达到减 少纹理合成时间的目的。 ( 2 ) 匹配块的搜索过程中，在每个单分辨率层按照螺旋状匹配块搜索策略为 待合成纹理块寻找匹配块。即在前一个已合成纹理块在样本纹理中位置的周围 进行搜索，避免了穷尽搜索，到达减少搜索范围的目的。 ( 3 ) 按照光栅扫描线顺序逐块合成各个分辩率层纹理图像，高分辨率纹理图 像的合成借助已合成的低分辨率纹理图像，按分辩率从低到高的顺序逐层合成 纹理，直至最高分辨率层合成完成，最高分辨率层即为最终输出纹理。 1 4 武汉理工大学硕十学位论文 3 1 1 建立图像金字塔 对图像进行多分辩率分析的含义为：如果图像在较大尺度里变化平缓，可 以采用较低的分辩率来分析图像；如果图像在较小的尺度里变化剧烈，需要采 用更高的分辨率。然而实际中的图像往往比较复杂，可能既包含变化平缓的区 域，也同时拥有很多细节的区域。因此，对图像进行多分辩率分析具备一定的 优势。 实际中常采用图像金字塔对图像进行多分辨分析。图像金字塔是对一幅图 像不同的分辩率表示按照分辩率由高到低的顺序进行排列，底部是图像的高分 辨率表示，顶部是图像的低分辨率表示，向上层移动时，尺寸减小，分辨率降 低，整个排列呈金字塔形状。为纹理图像构建多分辨率的图像金字塔，在低分 辨率层可以采用较大边界分析大的纹理结构，也就是图像的整体内容；高分辨 率图像采用较小边界分析纹理的细节。这样，不仅减少了在单分辨率图像中采 用较大纹理边界寻找最佳匹配块所带来的大量计算，而且能够使合成纹理图像 更好的保持样本纹理的结构特征。 本文采用的图像金字塔为高斯图像金字塔，它的产生过程为： ( 1 ) 用高斯滤波器对样本图像图像进行低通滤波。 ( 2 ) 对样本图像下采样得到新的图像。 ( 3 ) 重复上面两个过程得到高斯金字塔g ，。 金字塔底部是图像的高分辨率表示，顶部是低分辨率表示。 当向金字塔的上层移动时，图像的尺寸和分辨率就逐层降低，以原始样本 图像为金字塔的第0 层g 0 ，则g 0 的多分辨率缩减形式g ，为高斯会字塔的第，层， 其中第，层图像的像素值的各个分量是通过第z l 层图像窗口内的像素的对应分 量的加权平均计算得到的，即式3 1 。 三三 g ，( f ，j ) = w ( m ，1 ) g ，一i ( 2 x i + m ，2 x j + n ) ( 3 - 1 ) m = - - 2n = - 2 式3 1 中，0 j n ，n 表示高斯金字塔的总层数；0 i 彬，0 q ， 彬和日，分别为高斯金字塔结构中第，层图像的水平宽度和垂直高度。实际中为 方便处理，第，层的尺寸恰好为第，一l 层的l 2 ，即彬= 形一。2 ，q = 局一。2 。 这样第，层图像可以通过对第，一l 层图像进行隔行采样得到。式3 1 中的权值定 义如下： 1 5 武汉理工大学硕士学位论文 w ( m ，露) = 识朋) 议摆)( 3 2 ) 烈研) = l ( 3 - 3 ) 端- 2 三裂1 心4 - a 2 ( 3 4 ) 识) = 颤2 ) = ”7 式3 4 中，a 是一个常数，取a = 0 5 。由于高斯金字塔结构中第，层图像是 第z l 层图像的加权平均，所以第z 层图像包含了前一层图像的低频信息，尺寸 为第，一1 层的l 2 。第，层要获得与第，一1 层层尺寸一样的高斯金字塔分解图像 g ( 0 ， 忉，可通过对图像进行插值运算得到。 3 1 2 寻找匹配块 按照由低到高的顺序合成金字塔的各个分辨率层时，要为当前待合成纹理块 搜索最佳匹配块。在以往的块拼贴算法都是按照扫描线顺序对样本纹理进行穷 尽搜索，查找匹配块，所以合成效率低。根据纹理相关性原理，待合成纹理块 处于前一个已合成块在样本纹理中位置的邻域范围的概率更大，也就是说当前 待合成纹理块和已合成纹理块具有空间的连贯性，所以在搜索匹配的纹理块时， 在前一个已合成纹理块在样本纹理中位置的周围进行搜索，以提高合成速度。 另外由于引入了多分辩率纹理合成的思想，需要将螺旋状匹配搜索方法应 用到多维空间的块匹配算法中。具体的实现机制如下所述： 定义一个用来存放搜索结果的匹配块数组 岛】，刀表示样本块的数量，在本 文中其最大值设置为1 0 0 。 见】包含待合成纹理块的所有匹配块，【见】可表示如 下： p k 】= p ，id ( p ，q ) 屯。，p j g ；) ( 3 5 ) 式3 5 中，d ( p ，q ) 表示两个纹理块p ，和g 之间的距离，其计算公式如式 3 - 6 。d m 。，表示纹理块边界的最大误差，其计算公式如式3 7 。为了增加输出纹 理的随机性，可以从【以】随机选择一个纹理块作为当前待合成纹理块的最佳匹 配块。如果【见】为空，选取搜索过程中具有最小边界区域误差的纹理块作为最 佳匹配块。 1 6 武汉理工大学硕士学位论文 撕，= 瞌产叫2 仔6 ， = 噱扔2 j ( 3 - 7 ) 其中，a 为纹理块边界区域所包含的像素个数，p 和q 表示像素的r g b 值。 参数g 控制待合成纹理块和匹配块之间的相似度。s 越小，相似度越大；反之亦 然，一般情况下选取占= 0 2 。 从上面可以看出，搜索待合成纹理块g 的最佳匹配块的过程就是计算a 与q 的距离d ( 岛，q ) 的过程，计算出的距离小于阈值的块，即其边界匹配误差小于阈 值，该块就被存放到当 见】中，作为候选的匹配块。 图3 1 螺旋状搜索匹配块 3 2 纹理合成算法步骤 经过上面的分析，本文的纹理合成算法步骤如下： ( 1 ) 对输入的样本纹理图像进行高斯低通滤波和其下采样操作，建立高斯图 像金字塔； ( 2 ) 设定样本块的尺寸、样本块数量、重叠区域大小、边界匹配的阈值以及 初始化记录匹配纹理块的数组【以】； ( 3 ) 从金字塔的最低分辩率层开始合成纹理图像； ( 4 ) 按照螺旋线搜索策略搜索待合成块的匹配纹理块，将搜索的结果放入匹 配块数组中，记录匹配块的位置。 ( 5 ) 按扫描线顺序合成纹理块，若到达终点，转步骤6 ；否则转步骤2 ； ( 6 ) 进入更高的分辨率层进行合成，在计算纹理块的边界匹配误差时，同时 1 7 武汉理工人学顼士学位论文 考虑当前分辩率层中纹理块边界中的像素值和低分辨率层中对应位置上的像素 值； ( 7 ) 若最高分辨率层合成完成，输出最高分辨率层，程序结束：否则，转到 步骤2 ，继续循环。 3 3 实验与结果分析 3 3 1 算法比较实验 本文在m a t l a b 7 0 软