（信号与信息处理专业论文）基于样图的纹理合成方法研究.pdf

-、：毒 声明尸明 本人郑重声明：此处所提交的硕士学位论文 ：基于样图的纹理合成方法研究，是 本人在华北电力大学攻读硕士学位期间，在导师指导下进行的研究工作和取得的研究成 果。据本人所知，除了文中特别加以标注和致谢之处外，论文中不包含其他人已经发表 或撰写过的研究成果，也不包含为获得华北电力大学或其他教育机构的学位或证书而使 用过的材料。与我一同工作的同志对本研究所做的任何贡献均已在论文中作了明确的说 明并表示了谢意。 学位论文作者签名：二鎏牛日期：二掣 关于学位论文使用授权的说明 本人完全了解华北电力大学有关保留、使用学位论文的规定，即：学校有权保管、 并向有关部门送交学位论文的原件与复印件；学校可以采用影印、缩印或其它复制手 段复制并保存学位论文；学校可允许学位论文被查阅或借阅；学校可以学术交流为 目的，复制赠送和交换学位论文；同意学校可以用不同方式在不同媒体上发表、传播学 位论文的全部或部分内容。 ( 涉密的学位论文在解密后遵守此规定) 作者签名：送蛰 日 期：型业趟 导师签名： 日期： 华北电力大学硕士学位论文 摘要 纹理合成技术是当前计算机图形学、计算机视觉和图像处理领域的研究热点之 一，具有广泛的应用价值。基于样图的纹理合成克服了传统纹理映射的缺点，同时 又避免了通过物理模型模拟生成过程进行纹理合成的繁琐过程，因而受到越来越多 的关注。本文介绍了纹理合成技术的几种经典算法，并对其中的两种经典算法提出 改进方法，包括基于共生矩阵聚类分析判断纹理细节的综合纹理合成方法和点匹配 方法中根据邻域的选取达到最佳合成效果。其中共生矩阵聚类分析思想是对纹理细 节进行分类，对随机性纹理部分采用点匹配方法进行纹理合成、结构性纹理采用块 匹配方法进行纹理合成。对于随机纹理部分结合基于图像金字塔的多分辨率合成方 法有效提高合成速度，并通过实验说明点匹配过程中邻域的选择对试验速度及结果 产生的影响。 关键词：纹理细节，结构性纹理，随机性纹理，点匹配 a b s t r a c t t e x t u r es y n t h e s i st e c h n o l o g yi so n eo ft h eh o t t e s tr e s e a r c ht o p i ci nt h ef i e l d so f c u r r e n t l yc o m p u t e rg r a p h i c s ，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 n g ，w h i c hh a sw i d e l y a p p l yv a l u e s i n c et s f sh a sn o to n l yo v e r c o m ew e a k n e s s e s o ft r a d i t i o n a lt e x t u r e m a p p i n ga n da l s oa v o i d e do f t h et e d i o u sp r o c e s sc a u s e db yp h y s i c a lm o d e lw h i c hi su s e d t os y n t h e s i st e x t u r e ，i ti sg a i n i n gm o r ea n dm o r ea t t e n t i o ni nt h er e s e a r c ha r e a s e v e r a l c l a s s i c a la l g o r i t h m so nw h i c hw ea p p l i e ss o m ea d v a n c e dm e t h o do na r ei n t r o d u c e dh e r e i nt h i sp a p e r , i n c l u d i n gas y n t h e t i c a la l g o r i t h mo nt e x t u r es y n t h e s i z i n gb a s e do nt e x t u r e d e t a i li n t e n s i t yc a l c u l a t i n gb yu s i n gc o o c c u r r e n c em a t r i xa n a l y s i si sp r o p o s e di nt h e p a p e r c l a s s i f y i n gt h et e x t u r ei n t ot h er a n d o mt e x t u r ep a r ta n dt h es t r u c t u r a lt e x t u r ep a r t u s i n g t h ec o - o c c u r r e n c em a t r i x a n a l y s i s t o s y n t h e s i s t h et w od i f f e r e n t p a r t s r e s p e c t i v e l y t od ot h i s ，w ec o m b i n et h ea d v a n t a g e so ft w oa p p r o a c h e ss ot h a tw ec a r l s p e e du pt h et i m ea n dg a i nab e t t e rr e s u l t m e a n w h i l e ，w ep r e s e n t sa ne f f i c i e n ta l g o r i t h m a p p l i e st h em u i t i r e s o l u t i o nm e t h o di n t ot h er a n d o mt e x t u r es y n t h e s i z i n g f u r t h e r , t h i s p a p e rp r o v i d e se x p e r i m e n t a lr e s u l t st od e m o n s t r a t et h ei n f l u e n c ec a u s e db yt h ed i f f e r e n t n e i g h b o r h o o ds i z ea p p l i e dt ot h ee x p e r i m e n t k e y w o r d s ：t e x t u r ed e t a i li n t e n s i t y , s t r u c t u r a lt e x t u r e ，r a n d o mt e x t u r e ，p i x e l m a t c h ， i m a g e q u i l t i n g h o n gy a n ( s i g n a la n di n f o r m a t i o np r o c e s s i n g ) d i r e c t e db yp r o f x ug a n g l 华北电力大学硕士学位论文 目录 摘要1 目录2 第一章绪论4 1 1 研究意义及选题背景4 1 2 问题描述4 1 2 1 纹理合成概述4 1 2 1 1 纹理的分类5 1 2 1 2 纹理合成的方法类别5 1 3 纹理合成技术的研究现状6 1 4 纹理合成技术的应用6 1 4 1 旧照片的修复6 1 4 2 合成特殊效果图7 1 4 3 图像压缩7 1 4 4 动画7 1 5 论文结构8 第二章基于点像素的纹理合成方法9 2 1 基于点像素经典纹理合成方法9 2 1 1a s h i k h m i n 纹理合成算法9 2 1 1 1 算法描述9 2 1 1 2 算法优点与存在的问题1 0 2 1 2w e i - l e o y 纹理合成算法1 l 2 1 2 1 算法描述1 l 2 1 2 2 算法优点与存在的问题1 2 2 2 基于多分辨率的像素纹理合成1 2 2 3 矢量量化技术1 3 2 4 邻域选取1 3 第三章块匹配的纹理合成方法1 5 3 1 基于块匹配的经典纹理1 5 3 1 1i m a g eo u i i t i n g 算法1 5 3 1 1 1 算法描述1 5 3 1 2 多种子快速合成算法1 6 3 1 2 1 算法描述1 6 3 1 2 2 算法优点与存在的问题1 8 3 2 邻域选取1 8 第四章纹理合成算法在数字图像中的运用2 0 4 1 运h j 背景2 0 4 2 基t - s - t i1 e s 实时合成算法2 3 4 2 2w a n gt i1 e s 合成算法2 3 4 2 3 基t - s - t il e s 的实时纹理合成算法2 5 4 2 3 1 算法描述2 5 4 2 3 2s - t i l e s 生成算法2 6 2 1 一 华北电力大学硕士学位论文 4 3 方向可控多分辨率纹理合成算法2 7 第五章基于共生矩阵分析的快速纹理合成2 9 5 1 共生矩阵判断纹理细节强度2 9 5 2 算法流程3 2 5 3 实验结果与分析3 3 第六章总结与展望3 4 6 1 内容总结3 4 6 2 未来工作的展望3 4 参考文献3 6 致谢4 0 附录4 l 在学期间发表的学术论文和参加科研情况4 4 3 j 华北电力大学硕士学位论文 1 1 研究意义及选题背景 第一章绪论 纹理合成是当前计算机图形学、计算机视觉和图像处理领域的研究热点之一。 在图像处理、压缩数据以达到加快数据的传输、计算机图形动画、大规模场景的生 成以及真实感和非真实感绘制等方面该技术具有广泛的应用前景。 在纹理映射、过程纹理合成方法已发展成熟之后，基于样图的纹理合成技术 ( t e x t u r es y n t h e s i sf r o ms a m p l e st s f s ) 是随之发展起来的一种新的纹理合成技术。基 于样图的纹理合成技术因为可以用于处理过去纹理合成方法中出现的拼接接缝、参 数设置和变形等问题而逐渐成为目前计算机图形学和图像处理等领域的研究热点 之一。t s f s 技术的思想是在已给定的小区域纹理样本基础上，依据某种算法而拼合 出所需的纹理图像，且合成的图像自然无明显拼接接缝，其大小可以通过参数设定。 经过多年的努力，基于样图的纹理合成技术已经取得了很大的进展。 然而，目前基于样图的纹理合成技术主要存在以下几个问题： 一、在现有的纹理合成算法中，其中有一些算法已经实现了实时处理，但其图 像输出效果出现明显接缝、菱形图样等质量问题，因此合成效果仍有待提高。 二、相当一部分纹理合成算法具有运算量大、耗时长的缺点，若要提高合成速 度往往又需要以牺牲合成质量为代价。 三、自然界中存在的纹理很大程度上是结构性纹理和随机性纹理混合的纹理类 型，现有的算法针对上述两类纹理的合成均已取得了较好的效果，但对于混合类纹 理的合成仍存在一定的问题。 本课题的主要工作就是在已有算法的基础上，对基于样图的块拼贴算法进行改 进，进一步提高纹理合成的质量和速度，力求寻找一种应用更为普遍的纹理合成方 法，使纹理合成技术能够更好的应用到现实生活中的各个方面。针对不同的应用需 求，现有的各种纹理合成算法也仍然存在着这样或那样的缺陷，针对以上纹理合成 方法还存在的不足本文进行了简要概述。同时，纹理合成算法中涉及的理论和思想 也对其他相关领域的研究具有一定的指导意义，所以对纹理合成算法的研究具有较 高的理论和现实意义。 1 2 问题描述 1 2 1 纹理合成概述 纹理合成技术是当前计算机图形学、计算机视觉和图像处理领域的研究热点之 一，具有广泛的应用价值。纹理合成算法总体上可以分为三类，包括通过物理模型 4 i - k l 华北电力大学硕士学位论文 模拟生成过程来进行纹理合成，通过对样图进行纹理分析派生出参数模型，用得到 的参数模型来进行纹理合成，和基于样图的纹理合成。其中基于样图的纹理合成是 近几年发展起来的一种新的纹理合成技术，其主要思想是基于给定小样图的纹理特 征，生成大面积的纹理，并保证纹理结构的连续性和相似性。基于样图的纹理合成 克服了传统纹理映射的缺点，同时又避免了通过物理模型模拟生成过程进行纹理合 成的繁琐过程，因而受到越来越多的关注。 基于样图的纹理合成是于近几年快速发展起来的一种新的纹理合成技术，在基 于图像的真实感绘制的应用中占有重要的地位。基于样图的纹理合成技术不仅克服 了传统纹理映射方法所固有的缺陷的同时将过程纹理合成参数调解的繁琐过程这 一弊端也同时得到解决，传统的样图纹理合成利用统计学方法是通过分析和纹理样 图的直方图匹配，但是这样方法只对随机性纹理的处理有效；基于m r f 模型是对 于大多数纹理采用的合成方法，该方法所具有的缺点是虽然在样图纹理合成的质量 上得到了较大的改善，但是却同时存在速度较慢的问题；基于块匹配纹理合成技术 则很大程度的提高了纹理合成算法的速度，其中则是在充分利用了基于块匹配邻域 间的相似度的基础上进行合成的，从而增加了纹理可处理的范围，这将是样图纹理 合成技术的发展方向。随着研究的深入，纹理的类型又涉及到了完全无结构的纹理 ( 例如烟、雾等) 、整体有结构的纹理( 例如织物等) ，甚至是同时考虑了多种纹理之间 的混合，因此产生了基于用户控制和多输入样图的纹理合成的纹理合成这类扩展技 术。 1 2 1 1 纹理的分类 在自然界中，纹理可以归为重复纹理和随机纹理两类，其中重复纹理可以看成 是由规则性的纹元组成，如规则排列的墙砖、鹅卵石等。而如树皮、沙滩等这类无 法找出规则纹元的纹理则为随机性纹理。在现实世界中，几乎所有的纹理都介于规 则性纹理及随机性纹理之间，如一些织物、犁过的地等，这些纹理可以被认为是具 有一定的随机性的重复结构化元素的集合，则可将其视为混合性纹理。 1 2 1 2 纹理合成的方法类别 纹理合成技术有块拼接方法和像素点匹配两种方法，例如c h e n 提出一种基于 w a n gt i l e s 的块拼接方法，但它对低频纹理合成效果不理想。a s h i k h m i n 1 提出的基 于像素点匹配的合成方法实用于随机自然纹理，且不会存在块拼接方法容易产生拼 缝痕迹的缺陷。在本文中将多分辨率法运用到a s h i k h m i n 的方法中，有效提高合成 速度和合成质量。 5 华北电力大学硕士学位论文 1 3 纹理合成技术的研究现状 基于样图的纹理合成( t s f s ) 技术从上世界9 0 年代发展至今已逐渐在计算机图 形学、计算机视觉和图像处理等领域成为研究热点。每年在e u r o g r a p h 和 c i f i c g r a p h 等重要国际会议上都有大批的论文发表。基于样图的纹理合成算法可 分为基于点和基于块的方法。t s f s 技术主要可以分为二维纹理合成、三维纹理合 成和视频纹理合成。基于点的合成方法是指一个一个像素逐一进行合成，因此在时 间上的消耗比较大；基于块的合成方法虽然合成速度快，这相对于点合成的方法有 所优势，但如果接缝处理不好，合成质量就会较低。经过多年的发展，基于样图的 纹理合成技术己经取得了较大的进展。 基于马尔可夫随机场的利用在对样图纹理合成技术的应用中，马尔可夫随机 场( m a r k o vr a n d o mf i e l d s ，m r f ) 模型对于大多数的纹理合成都是一种较好的逼近。 在s i g g r a p h2 0 0 1 会议上，e f r o s 就提出了一种基于块匹配拼接( i m a g eq u i t i n g ) 的 算法【2 】，通过计算待合成纹理块与己合成纹理块在重叠区域的累积误差( s s d ) 和最 小误差路径( m i n i m u me r r o r ) 来完成对纹理的合成，对大多数纹理合成取得很好的效， 果，并且合成速度很快，避免了以往算法引起的模糊、纹元错位等现象。同年在a c m 图形学报上，l l i a n g 等人提出了基于块采样的实时纹理合成算法【3 】，也取得了很好； 的效果。k w a t r a 则使用图像分割的方法进行纹理合成【4 】，并将i m a g eq u i l t i n g 算法 7 中的矩形纹理块推广到任意形状，获得了很好的合成质量。而在1 9 9 9 的i c c v 会议 上，e f r o s 和l e u n g 提出的非参数采样算法 5 】，该算法就是基于点进行合成的，利 用纹理图像中邻近点相关性强的特征，根据预先在待合成图中设置的种子，通过给 定的邻域在样图中查找匹配点来合成纹理。由于该模型可以很好地抽象出纹理视觉 上相似的数学特征，已成为纹理合成技术的基础模型，随后的许多算法都是基于这 一模型进行展开的。这一算法虽然对大多数纹理都取得了很好的效果，但由于是按 像素点进行逐个扫描，耗费时间过长，并不实用。在s i g g r a p h2 0 0 0 会议上w e i 和l e v o y 对该算法进行了改进，提出了一种基于像素点的l 形邻域搜索纹理合成算 法 6 】，并采用多分辨率模型进行匹配，同时利用树形矢量量化技术( t s v q ) 力1 1 速合成 过程：a s h i k h m i n 利用相邻像素间的相关性原理对w 萌l e v o y 的方法作了进一步的 简化，在自然纹理的合成中取得了很好的效果。 1 4 纹理合成技术的应用 1 4 1 旧照片的修复 旧照片一般存放时间较长，在存储的过程中容易磨损和认为的损坏，而当代人 们习惯利用例如p h o t o s h o p 等图像处理工具手工对照片的数字扫描图像进行编辑， 6 华北电力大学硕士学位论文 修补图像上缺失的信息。然而利用手工修复方法效率一般比较低下，与此同时对软 件的熟悉也是对操作者的基本要求。如今图像修复技术的目的就是研究和解决如何 更好地根据图像周围的有效信息，利用特定的修补算法自动地恢复图像上的受损部 分，同时要使观察者无法察觉到图像的修复痕迹，如今它已成为图像工程领域的一 个新的活跃研究方向。总体而言，研究图像修复技术的成果可以达到高效地修复大 批量的受损图像的目标，从而帮助普通用户方便地修复图像，因此具有很强的受用 价值。 图像修复技术主要分为两大类，第一类是主要用于修复小尺度缺损的技术， 称为i n p a i n t i n g 。另一大类图像修复技术可以用于填充图像中大块丢失信息。其中一 种是基于图像分解的修复技术，其主要思想是首先将图像分为纹理部分和结构部 分，其中纹理部分用纹理合成方法填充，而结构部分则用i n p a i n t i n g 算法修补。代 表性的成果如b e r t a l m i o 7 】、y a m a u c h i 8 】、h a r a l d 9 等提出的方法。 1 4 2 合成特殊效果图 普通照片，人工设计的图案，均可以由一个纹理样本和一个用来控制纹理合成 的目标图像来合成一个新的纹理图像，合成特殊效果图是纹理合成技术的一个重要 应用。纹理合成目标图控制合成结果图像所要呈现的形状。从纹理图中选取需要合 成的颜色来完成所需的图案。对普通照片进行纹理合成时可对照片进行适当编辑以 期获得所需的效果。由于需要根据颜色误差进行匹配来进行纹理合成，即与纹理颜 色相近则取该纹理的概率越大。针对自然纹理合成，图案的边缘不需要太规则，因 为这样可以避免合成出的纹元不完整，使合成结果无法达到较高的视觉效果。 1 4 3 图像压缩 纹理通常由高频和重复的图案( p a t t e n s ) 的信息组成，因此当使用基于比如 j p e g 的变换技术并不能实现很好的压缩效果。这里以l e v o y 的t s v q 加速纹理合成 算法举例，实际的压缩过程其实就是建立码书的过程，图像进行传输时实际仅仅传 输的是码书，而码字的数量可以决定压缩的大小进行控制。然而，基于码书的压缩 技术能够达到对纹理较好的处理效果。对于接收方而言，解压缩的过程实际上是变 成了一个纹理合成过程，可以生成任意大小的纹理图像，与其它图像压缩技术相比， 此算法的压缩率是比较高的。 1 4 4 动画 计算机产生的动画经常包含脚本事件和随机运动，脚本事件是非重复的动作， 7 1j 华北电力大学硕士学位论文 例如打开门捡起一个物体，并且通常是被直接控制的。例如冉冉上升的烟雾、波浪 或者燃烧的火焰，这些随机运动都是重复性的背景运动，这类运动在时间和空间上 有不确定的范围，通常被称为时间纹( e t m p o r a l t x e u t e r ) 。在时间纹理中，一些特定 的运动例如关节运动的接合角，可以被建模成一维纹理。这些纹理能够被合成用于 模拟精巧的动作，例如眨眼睛或人的走动。 1 5 论文结构 本文可大致分为五个部分，分别从基于点像素的纹理合成方法、基于块匹配的 纹理合成方法、纹理合成算法在数字图像中的运用和基于共生矩阵分析的快速纹理 合成五个角度进行阐述。其中基于点像素纹理合成算法中以经典算法介绍为主，包 括a s h i k h m i n 合成算法和w d l e o y 合成算法。针对a s h i k h m i n 算法给出了基于多分 辨率的快速算法。针对w d l e o y 算法中的矢量量化技术也给出了具体介绍。基于块 匹配的纹理合成方法中，着重介绍了e f r o s 的i m a g eq u i l t i n g 算法及多种子快速合成 算法。上述的算法中都详细给出了算法的描述及优缺点介绍。第四章主要介绍纹理 合成在数字图像中的运用，这一章中给出了基于s - t i l e s 实时合成算法和s - t i l e s 的生 成算法的同时介绍了w a n gt i l e s 合成算法的描述。在第五章中提出基于共生矩阵分 析的快速纹理合成算法，是对经典算法的改进与结合，本节给出了理论基础及算法 流程描述，最后以实验结果与分析说明了此算法的优越性。在本文的最后一节对全 文作出了总结并对纹理合成技术的发展及未来的工作的进行提出目标及展望。 l 0 华北电力大学硕士学位论文 第二章基于点像素的纹理合成方法 2 1 基于点像素经典纹理合成方法 e f f o r s 首次将使用m r f 模型运用于纹理的特征提取中。基于点的纹理合成的思 想是把输出像素从随机噪声强迫变换成与样图类似的这一过程，即在样图中，取 一个像素点写入合成图的待合成像素点位置，然后从像素点的相邻点开始，在样 图中移动匹配窗口，把误差最小的匹配点写入合成图中，如此循环直至填满合成 图，得到新的纹理 3 2 】。样图的纹理特征能够在合成图中得到很好的保存和再现依 赖于邻域窗口的大小的恰当选择。 w e i 和l e v o y 与a s h i k h m i n 使用l 型邻域进行合成，不论邻域窗1 ：3 中的所有像 素是否已经被合成，一律按顺序扫描的方向进行合成。e f r o s & l e u n g 使用矩形区 域进行合成，但是仅仅使用矩形邻域窗口区域中已合成完毕的像素来进行比较、输 出。利用基于点纹理合成算法合成图像在很多情况下都会损失一些纹理特征之间的 边界信息，使得诸多纹理特征信息杂糅在一起，导致合成图中一些纹理特征模糊。 例如a s h i k h m i n 的方法如同块匹配方法一样，同样容易产生明显的接缝感，因此多 数情况下仅仅适用于合成包含很多高频信息的自然纹理。 2 1 1a s hik h m in 纹理合成算法 2 1 1 1 算法描述 a s h i k b a n i n 是一种基于像素点匹配的方法，实现简单。如图2 1 所示，按照从 上到下、从左到右的合成顺序，因此待合成点总在已合成点的右下角位置。待合成 点p 的合成过程如下：输出图像中灰色部分为已合成区域，即待合成点p 的左侧及 上方的邻域点均为已合成点，这里以点p 周围4 个邻域点为例，每个邻域点都可以 在输入图像中找到匹配点，而每个邻域的位置都可以通过待合成点p 经过相应的偏 移得到，因此在输入图像中找到4 个邻域点分别通过相同偏移量得到4 个像素位置， 这样得到的4 个位置的像素我们称它们为候选像素点，最终选择哪一个候选像素点 复制到待合成点p 要经过厶距离公式的计算 3 】，选择厶距离最小的候选点复制到待 合成点p 。厶的距离公式为： 9 x l 华北电力大学硕士学位论文 d ( l ，8 2 ) = s q r t ( r ( p ) - r ( q ) ) 2 + ( g ( p ) 一g ( g ) ) 2 + p 搿徽 ( 1 1 ) q 为对应点 - 。- ， ( 曰( p ) 一曰( g ) ) 2 ) 式中p 为输入图像中像素点，q 为输出图像中像素点。m ，2 分别为点p 与 点q 的邻域( i ，2 必须形状大小相同) ，r ，g ，b 为像素点的三基色。 a s h i k m i n 算法和w l 算法【6 】都比较直观，实现简单，与w l 算法比较，a s h i k m i n 速度更快，在自然纹理的合成方面取得了很好的效果，如花丛、草地等。但对于砖 墙这类结构性较强的纹理图像合成效果不佳，主要原因是a s h i k m i n 算法采取的方法 是基于点像素匹配，逐个点像素合成不利于很好保存结构性纹理纹元的完整性。 图2 - 1a s h i k h m i n 算法示意图 2 1 1 2 算法优点与存在的问题 优点：【1 】由原来的遍历搜索改为只搜索当前点的l 型邻域内像素点，方法比较 直观。采用这中方法不但进一步提高了合成速度，而且合成效果上也比较好。 存在的问题： 1 】适合用于合成自然纹理，对于结构性纹理的合成质量不高，且 该算法不能处理平滑度较强的纹理。总体来说，【1 】合成方法适用范围较小。 1 0 华北电力大学硕士学位论文 2 1 2w e i - l e o y 纹理合成算法 2 1 2 1 算法描述 w l 算法 2 】针对e f r o s 和l e u n g 算法 3 】进行了改进，与e f r o s 和l e u n g 一样的是 采用基于m r f 模型的算法，改进之处在于算法【2 】避免了概率构造的环节而采取直 接从样本中取样。图2 2 描述了w l 算法的过程示意图，包括给定样本纹理，初始 化输出纹理，最后合成输出纹理。 图2 2w e i l e o y 合成过程示意图 搜索到的像素拷贝到当前待合成像素的位置。 算法步骤描述如下： ( 1 ) 初始化输入纹理，同时确定出l 邻域的尺寸大小。 ( 2 ) 按照扫描线顺序逐点进行纹理合成，对于当前待合成的像素点，在样图纹 理中找出令厶最小的像素点。 ( 3 ) 找出的像素点即为待批配像素点，将其拷贝至输出纹理。重复上述步骤， 最后得到争幅输出纹理。 另：算法过程中邻域之间的相似度同样采用厶距离来度量，见公式( 1 ) 。 w e i l e v o y 算法的缺点是合成速度慢，可以通过使用多分辨率合成的方法来降 低邻域的采样范围，或者通过树结构的矢量量化方法进行加速，这样可以取得较好 的加速效果。l 邻域的尺寸必须大于纹元的尺寸，但同时存在随着合成的过程进行， 计算量也将成倍的增加，所以邻域尺寸不应选择过大而应适中。 华北电力大学硕士学位论文 2 1 2 2 算法优点与存在的问题 优点：w e i l e o y 方法适用范围广的同时合成效率也较高，能够合成高质量的纹 理图像，且算法中需要调整的参数很少，较为方便。 存在的问题：不能用于处理随机性纹理图像。 2 2 基于多分辨率的像素纹理合成 多分辨率纹理合成算法的基本原理是使用低分辨率层来实现合成高分辨率层， 因此计算成本低，速度快。它对每一层输出纹理金字塔进行两步合成：第一步使用 其上一层的对应邻域在输入纹理中搜索最佳匹配像素第二步实用本层像素邻域和 上一层像素邻域在输入纹理中搜索最佳匹配像素 3 1 】。具体过程如图2 3 所示： 瓴，马) 输入图像输出图像 图2 - 3金字塔图像层示意图 l ，厶一。分别为输入图像金字塔中的第n 层图像( 高分辨率层) 和第n - 1 层图像( 低分辨 率层) ，q ，q 一。分别为输出图像金字塔中的第r l 层图像( 高分辨率层) 和第n - 1 层图像 ( 低分辨率层) 。输出图像q 层中点( 以，b ) 对应q 一。层中的点( 譬，i p y ) ( 由图像金字塔 采样决定) ，点( 譬，了p y ) 的像素值已经利用a s h i k h m i n 方法在输入图像厶一- 中找到， 这罩假设点( 了p x ，了p y ) 最终是复制了点( 吼，吼) 的像素值。而l 一。层点( 以，郇) 对应l 层的 华北电力火学硕士学位论文 ( 2 q ，2 以+ 1 ) ，( 2 吼+ l ，2 q ，+ 1 ) ，( 2 以，2 q y ) ，( 2 吼+ l ，2 q y ) 四个点，因此点( p x ，岛) 的匹配只需 在这四个点中选择。 2 3 矢量量化技术 为了加快纹理的合成速度，原算法中采用了矢量量化技术( t s v q ) 。量化是指把 所有邻域组成的集合划分成有限个不重叠的小子集，这些子集大小不一定相等，每 个子集都由内部的一个值来代表。通过这种方式很容易在样图中寻找与输出图像的 当前邻域误差最小的邻域【7 】。无论是单分辨率还是多分辨率的方法，对邻域误差最 小的像素点的查找都是对一个样图的全域进行搜索的过程。如果能减少搜索的范 围，将可大大提高纹理的合成速度。w d l e v o y 采用的是t s v q 技术，大大减少了 在样本纹理中的搜索空间，加速了纹理的合成。t s v q 的基本思想是输入一个训练 矢量的集合，生成一个二叉树结构的码书。 t s v q 技术的第一步是求根结点的码字：可以把邻域看作是多维空间中的训练矢 量，如大小为5 x 5 的l 邻域包含1 2 个像素，每个像素值用r 、g 、b 三个颜色分量 来表示，那么训练矢量的空间维数为3 ( 1 2 + 1 ) = 3 9 。计算训练矢量集合的并作为码 字。第二步是求两个子结点的码字：首先要将这两个子结点的码字分别初始化为父结 点的码字( 中心) 和一个扰动的中心，然后使用l l o y d 算法来为两个码字寻找最优局 部最优码字【8 - 9 】。l o y d 算法用于计算两个中心并最终根据计算好的中心基于最近 点的原则对向量进行划分。全部过程是一个循环、且过程不断的逼近。这样，所有 经过训练的矢量最终被分成两组，两组的中心即是两个子结点的码字。最后要做的 是用递归的方法建立码书：分别以两个子结点为根，递归运算对训练矢量继续进行划 分建立二叉树。当树的深度达到用户需求的条件时，则可以终止整个建树的过程。 码书即为一个树叶层码字的集合。当码书完成建立以后，对样图的搜索就变成了对 二叉树的搜索。假设训练矢量数目为1 1 ，建立在满二叉树的情况下，在样图中所有 矢量都是树中一个叶子结点，合成一个点搜索的时间复杂度为o ，而之前的时间复 杂度为o ( n ) 。通过设定树的深度，用一个最接近该叶子结点的中心的矢量来表示叶 子结点上的矢量集合，这样可以大大减少搜索量。假设此时树的叶子结点数目为s ， 建立完全二叉树，则时间复杂度为0 ，从而加快了搜索的速度。 2 4 邻域选取 本文在计算厶距离时，对候选点周围邻域大小进行调整，l 邻域的尺寸对于算 法的合成时间和合成质量有会产生一定影响，图2 4 实验结果说明了这种影响。从 图中可以看出，合成时间随着l 邻域尺寸的增大而增加，合成质量随着l 邻域尺寸 1 3 1j 华北电力大学硕士学位论文 的增大而逐渐得到改善，但是当邻域尺寸达到一定的大小时，l 邻域尺寸的增加不 仅会大大增加合成时间，并且会降低合成质量。经过实验结果表明，选择7 x 7 至9 x 9 的邻域尺寸大小较为合适，图2 - 4 说明了尺寸的影响。 邻域尺寸：3 x 3 邻域尺寸：5 5 邻域尺寸：9 x 9邻域尺寸：l l l l 图2 - 4 邻域大小选取 1 4 华北电力大学硕士学位论文 第三章块匹配的纹理合成方法 3 1 基于块匹配的经典纹理 2 0 0 0 年微软亚洲研究院提出基于块的纹理合成思想，也就是每次合成- d , 块纹 理，而不是每次合成一个像素点，采用重复映射得到新纹理。下面对基于块匹配的 经典纹理合成技术进行介绍。 3 1 1im a g e0 uiitin g 算法 3 1 1 1 算法描述 继在i c c v 1 9 9 9 上发表影响较大的非参数采样的纹理合成算法之后，e f r o s 在 2 0 0 1 年的s i g g a p h 会议上提出了一种给予块拼接的纹理合成算法。与以往算法相 比，它避免了以往算法容易引起的模糊、纹元错位严重等问题，该算法在纹理合成 速度和质量等方面都得到了很大的提高。 i m a g oq u i l t i n g 算法的基本思想是：按照扫描线顺序，每次依据一定的匹配规则 从输入纹理中选择固定大小的纹理块，将其拷贝至输出纹理，直至达到输出纹理大 小。由于i m a g oq u i l t i n g 算法将合成单位从单个像素提高到纹理块，从而大大提高 了合成速度。在i m a g oq u i l t i n g 算法中，不同的纹理块匹配准则对纹理合成质量影 响很大，下图3 1 中说明了这种影响。 图3 1 中，如( a ) 图所示，开始随机从输入纹理中选取出一个固定大小的纹理块拼 接到当前位置得到的输出纹理。在他们的边界处有明显的纹理断裂现象是因为这些 纹理块在选取时没有任何约束条件。在( b ) 上方，假设b l 为输出纹理中的已合成的 纹理块，b 2 为待拼接的纹理块，采用b 1 和b 2 之间的重叠区域的误差作为匹配准 则，从输入纹理中搜索具有最小重叠区像素误差的纹理块，将其填充到输出纹理的 当前位置。纹理块b l 和b 2 之间重叠区域的误差采用对应像素的l 2 距离度量，如 下式所示： 1 5 华北电力大学硕士学位论文 田 i ； i lb i l 眦j 随机放置纹理块重叠区相似度 约束放置纹理块 圈 计算纹理块之间 的最佳路径 输入纹理( a ) 明显纹理拼接痕迹效果( ”较好的拼接效果( c ) 无明显拼接痕迹效果 图3 - 1i m a g e0 u il t i n g 算法示意图 其中，图3 1 ( b ) 下方为采用重叠区相似度约束得到的合成纹理，与图3 1 ( a ) 相比， 纹理块与纹理块之间的边缘处的纹理断裂现象有明显好转，但是在局部仍然存在纹 理不连续现象，图3 1 ( c ) 在图3 1 ( b ) 的基础上使用最小误差路径对重叠区进行缝合， 其中误差最小的路径通过以下方法进行计算：设b 1 、b 2 沿垂直边重叠，误差曲面 定义为：e = ( 砰r 一群r ) 2 。算法通过下面公式获得重叠区域最后一行的各点误差： 互，_ ，= e l + m i n ( e i l ，- i 互，_ l ，互+ l ，一1 ) ( 3 1 ) 取误差最小的一点，反向跟踪获得最佳路径。对于水平方向的重叠，可以采用 类似的方法得到最佳缝合路径。i m a g eq u i l t i n g 算法在合成纹理时，在水平和垂直方 向都会出现重叠，两条路径会在某一点相交，可以选取误差最小的路径为最佳缝合 线。 3 1 1 2 算法优点与存在的问题 优点：该算法通过计算输入纹理中的纹理块与已合成纹理在重叠区的累积误差 采用最佳缝合路径算法，原理及算法简单，计算量小，算法处理快的同时输出纹理 图像合成质量较高。 存在的问题：根据大量的试验结果表明，此算法可能引起少量局部纹理不连续 的现象。 3 1 2 多种子快速合成算法 3 1 2 1 算法描述 ( 1 ) 采用多个种子在纹理合成图像中进行预填充。种子既可以选取单一象素点， 1 6 l 华北电力大学硕士学位论文 也可以选取具有某种形状的象素点集合。多种子的方法可以通过减少计算匹配点的 数量从而实现加速效果。一般选取导九嵋，冬以吃可以获得较理想的结果， 二二 这里以，丸分别为种子在水平方向和垂直方向的间隔距离，比，吃分别为匹配窗的 宽和高。这样是为了避免造成前后写入的种子粘连或者覆盖从而破坏了最终的合成 效果，因此应该使各种子互相尽量间隔一定的距离。 ( 2 ) 种子的形状可以多种多样。种子的形状可以根据纹理的不同采用点、线或 者矩形等多种不同形状。多种种子的选择可以使纹理合成方法能够应用到更大的范 围。 图3 2 螺旋线状搜索示意图 ( 3 ) 合成纹理的顺序可以变化。可以根据纹理不同情况进行合成顺序地选择，一 般对线状的种子沿种子线的方向进行合成；其它的可以选种子邻域的任一点开始， 按螺旋线状顺序进行合成；也可以从种子邻域的任一点开始按其他顺序合成。 ( 4 ) 螺旋线状搜索方式。螺旋状搜索的过程为：搜索的初始位置设定为上一点已 匹配位置，以其为中心从周边开始进行。当前点的匹配点分布在邻点匹配点邻域的 概率较大。因此，在后面的点的搜索过程中，在满足匹配误差小于设定的值时，从 上一个一点的匹配点的当前位置开始，由其邻域向外做螺旋线状搜索，则搜索终止， 把该点写至合成图中；若整幅样图都没有找到满足误差范围内需要的像素点，则选 取所有点中误差最小的点写入合成图中，如图3 2 所示，采用此搜索方式可以大大 提高合成速度。 徐晓刚算法与w l 算法不同之处在于合成图像的搜索方式、初始化方式和合成 方式上，其最终需要达到的目的是通过减少搜索的像素数量而从减少时耗、提高合 成速度。同时通过选择种子的形状，而且对方向性纹理的处理也给出了处理方法。 算法具体描述如下： a 在原样图上反复采样，然后随机或者按照顺序把种子填充至合成图中。 b 从合成纹理图像上预置种子位置开始，取出当前矩形邻域，然后按照螺旋状 1 7 华北电力大学硕士学位论文 的顺序在样图中搜索合适的匹配点，当邻域误差小于设定的域值大小时，停止搜索 进程，同时把匹配点复制至合成图中。 c 按照选定的合成顺序进行下一个点的合成。反复进行直至完成合成过程。 3 1 2 2 算法优点与存在的问题 优点：该算法采用多种子预填充以及螺旋状匹配搜索，因此合成速度比较快。 同时对于某些纹理，通过阈值合适的设定，能实现纹理合成速度和样图大小无关的 目的。 存在的问题：该算法采用块拼接方法，达到了实时合成的效果，但它步骤比较 复杂，如对于不同的纹理，为了不影响合成的速度，种子大小以及种子之间间隔大 小设置都需要改变。算法也相对难于理解和编程实现，且在特定情况也会出现合成 图像不连续的现象。 3 2 邻域选取 块匹配方法能很好的保存图像的纹理信息，因此这里借鉴文章【l 】的方法，利用 已合成的纹理块，使用邻域块匹配的方法。针对结构性纹理的图像使用块匹配的方 法可以很好的避免结构性纹理合成模糊的情况。图3 3 是文章 3 0 】的试验结果，图 中可以看出纹理块尺寸不同对合成结果的影响。其中( a ) 图为样图纹理( 长宽都为1 2 8 像素) ，( b ) ，( c ) ，( d ) ，( e ) 图是使用不同尺寸邻域时合成的结果，( b ) 图的块尺寸是边 长为1 2 像素的正方形，( c ) 图的块尺寸是边长为2 4 像素的正方形，( d ) 图的块尺寸是 边长为3 2 像素的正方形，( e ) 图的块尺寸是边长为1 2 0 像素的正方形。 华北电力人学硕士学位论文 鬻