（计算机应用技术专业论文）纹理合成在视频合成中的应用.pdf

浙江大学硕士学位论文 摘要 摘要 基于样图的纹理合成方法是继纹理映射，过程纹理合成方法后发展起来的一 种纹理合成技术，用于解决传统方法中出现的缝隙、扭曲、变形和参数调整等问 题。本文主要研究了纹理合成技术在向量场可视化和视频合成这两方面的应用。 本文介绍了纹理合成研究领域的一些基本概念，通过一些典型算法描述了目 前基于样图纹理合成技术的发展现状，指出了纹理合成中的一些关键问题。在向 量场可视化的应用中，对于基于纹理合成的向量场可视化算法存在的问题_ 有 时合成块内点的向量场大小和方向差异巨大，不能很好的体现向量场变化的趋 势，本文提出了改进方法，采用点块结合的自适应分割方法进行合成。在约束纹 理合成的框架下，定义了在向量场的指导下相邻两帧之间点位置的相关性约束， 使用纹理合成算法迭代合成连续帧，用视频实现了向量场可视化。这种视频实现 相对于合成图像实现向量场可视化，更直观地展示了基于向量场的纹理变化过 程。在视频合成的应用中，介绍了现有的基于纹理合成的视频合成算法，针对它 们大多需要一段视频作为输入的局限性，本文提出了基于单张图像生成一段视额 的方法，运用图像分割算法提取图像中的流体部分，通过人工交互的方式生成流 体的运动轨迹。对样本进行旋转和缩放等变换丰富了采样空间，使之适用于不同 方向和大小的向量场。定义了多帧之间点位置的相关性约束，在此约束下合成了 一组连续的帧，实现了单张图像中流体部分运动视频的合成。 本文算法在计算机动画片、大规模场景渲染、场景的模拟生成等方面有一定 的应用前景。 关键词：纹理合成，m r f 模型，向量场可视化，g r a p h c u t ，视频合成 浙江大学硕士学位论文 a b s t r a c t a b s t r a c t s a m p l e - b a s e dt e x t u r es y n t h e s i si s ai l c wt e x t u r es y n t h e s i st e c h n i q u ed e v e l o p e d f r o mt h et e x t u r em a p p i n ga n dp r o c e d u r a lt e x t u r es y n t h e s i s i ti se f f i c i e n tt os o l v et h e p r o b l e mw h i c hi nt r a d i t i o n a lt e c h n i q u e s ，s u c hi l l s n o t i c e a b l es e a m sb c t w e e l lt e x t u r e p a t c h e sa n dt h es t r e t c ha n dd i s t o r t i o no fp a t t e r nw h e nf i l i n ga t e x t u r eo ns u r f a c e s t h i s a r t i c l em a i n l ys t u d i e st 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 st e c h n i q u ei nv e c t o rf i e l d v i s u a l i z a t i o na n dv i d e os y n t h e s i s t h i sp a p e rs t a r t sb yi n t r o d u c i n gs e v e r a lb a s i cc o n c e p t so i lt e x t u r es y n t h e s i s a f t e r t h a t , 丽mad e t a i l e dd e s c r i p t i o no nt y p i c a la l g o r i t h m s ，c u r r e n tr e s e a r c hs t a t u so ft e x t u r e s y n t h e s i si sd i s c u s s e da n dk e yi s s u e sa r ea l s op o i n t e do u t i nt h ea p p l i c a t i o n so fv e c t o r f i e l dv i s u a l i z a t i o n , c u r r e n tt e x t u r es y n t h e s i sa l g o r i t h m sh a v et h ep r o b l e mo ft h a tt h e a n g l ea n dl e n g t ho fi n s i d ep o i n tv e c t o r s1 1 1 ed i f f e r e n tf x o me a c ho t h e rg r e a t l ya n dt h e y c a l l ts h o wt h et r e n do fv e c t o rf i e l dp r o p e r l y t os o l v et h i sp r o b l e m , m yp a p e rp r e s e n t s a ni m p r o v e dh y t , r i c la l g o r i t h mw h i c hl l s eb o t l lb l o c k - b a s e da n dp o i n t - b a s e ds y n t h e s i s 弱a d a p t i v es e g m e n t a t i o n u n d e rt h e 缸i l l eo fc o n s t r a i n e dt e x t u r es y n t h e s i s ，t h ea t t i d e d e f i n e st h ec o r r e l a t ec o n s t r a i n i n go fp o i n t si nt w oa d j a c e n tf a m e sg u i d e db yv e c t o r f i e l d ，u s e st e x t u r es y n t h e s i st og e n e r a t ec o n t i n u e sf l a m e sa n di m p l e m e n t st h ev e c t o r f i e l dv i s u a l i z a t i o nb yv i d e o i nc o m p a r i n gt h ev i s u a l i z a t i o nb yg e n e r a t i n gi m a g e s ，t h e v i d e ow a ys h o w st h ef i e l dt r a n s f o r m a t i o n1 1 1 0 1 ed i r e c t l y i nt h ea p p l i c a t i o no fv i d e o g e n e r a t i o n , c u r r e n ts y n t h e s i sb a s e da l g o r i t h m sa r ei n t r o d u c e d t h i sp a p e ra l s og i v e sa n a p p r o a c ho ns i n g l ei m a g ev i d e og e n e r a t i o nw h i c he x t r a c t st h ef l o wp a r to fi n p u ti m a g e b ys e g m e n t a t i o na l g o r i t h m sa n df o r m st h em o v e m e n tt r a c kb yi n t e r a c t i o n i no r d e rt o a c c o m m o d a t ed i f f e r e n tv e c t o rf i e l d ，t h es a m p l ei m a g ei sr o t a t e da n dz o o m e d t h i s p a p e rd e f i n e st h ec o r r e l a t ec o n s t r a i no nm u l t i - f i a m e ，a n ds y n t h e s i z e ag r o u po f c o n s e c u t i v ef r a m eb yt l l i sc o n s t r a i n ，a n da c h i e v ev i d e os y n t h e s i so n l yu s es i n g l e i m a g e o u rr e s e a r c h nb eu s e di nc o m p u t e ra n i m a t i o n ，l a r g es c a l es 啪er e n d e r i n g , s i m u l a t i o no f t h es c e n e sa n ds o0 1 1 - u 浙江大学硕士学位论文 k e y w 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 , v e c t o rf i e l dv i s u a l i z a t i o n , 浙江大学硕士学位论文 图目录 图目录 图2 1 象素点的邻域6 图2 2 块与块之间的重叠区域6 图2 3 基于m r f 的点匹配8 图2 4 扫描线顺序合成纹理。9 图2 5 重叠块间拼接- 1 0 图2 6 基于候选点的合成方式1 1 图2 7 m l e 合成示意图1 2 图2 8 砸l e 的合成1 2 图2 9 大小为1 6 的面l e 集合1 3 图3 1 样本的放缩和旋转。1 8 图3 2 向量场的自适应分19 图3 3 向量场约束下的合成结果2 0 图3 4 金字塔每一层的合成过程2 2 图3 5 当前的最佳匹配对应点2 3 图3 6 k w a 0 5 算法伪代码2 4 图3 7 向量场的纹理表示2 6 图3 8 网络流2 7 图3 9g r a p h - c u t 用于重叠区域处理2 9 图3 1 0 合成示意图3 1 图4 1 瀑布视频中的运动轨迹。3 4 图4 2 普通的视频循环。3 5 图4 3 改进的循环3 5 图4 4 各种视频循环方法的比较3 6 浙江大学硕士学位论文 图目录 图4 5 图像分割结果4 0 图4 6 流场的生成4 1 图4 7 动态规划用于重叠区域处理4 3 i v 浙江大学研究生学位论文独创性声明 本人声明所呈交的学位论文是本人在导师指导下进行的研究工作及取得的 研究成果。除了文中特别加以标注和致谢的地方外，论文中不包含其他人已经发 表或撰写过的研究成果，也不包含为获得逝鎏盘鲎或其他教育机构的学位或 证书而使用过的材料。与我一同工作的同志对本研究所做的任何贡献均已在论文 中作了明确的说明并表示谢意。 学位论文作者签名：瓣新 签字日期：否 年6 月，日 学位论文版权使用授权书 本学位论文作者完全了解澎鎏盘堂 有权保留并向国家有关部门或机 构送交本论文的复印件和磁盘，允许论文被查阅和借阅。本人授权澎姿态堂 可以将学位论文的全部或部分内容编入有关数据库进行检索和传播，可以采用影 印、缩印或扫描等复制手段保存、汇编学位论文。 ( 保密的学位论文在解密后适用本授权书) 学位论文作者签名：灞衔 签字日期：沙矽年6 月卜日 导师签名： 签字日期：ld 日 浙江大学硕士学位论文第1 章绪论 第1 章绪论 基于样图的纹理合成技术是近年来发展起来的新的纹理合成技术，其基本的 思路是对于给定的样图，运用合适的数学分析方法，抽取原样图中的特征数据， 建立相应的数学模型；然后基于该模型做适当的优化处理，形成中间数学模型； 最后依据样图和优化后的数学模型来合成纹理。此类方法一般包括三个部分内容 即：特征提取、模型优化、纹理合成。此类方法不仅能克服传统的纹理技术中存 在的问题，而且其中涉及的思想对其他相关领域的研究也有一定的指导意义。因 而受到越来越多的关注，成为计算机图形学、计算机视觉和图像处理领域的研究 热点之一。 基于样图的纹理合成技术经过若干年的发展，已经取得较大进展。第一个方 向是基于m a r k o v 随机场模型的样图纹理合成技术，将m a r k o v 数学模型应用到纹 理合成领域的思想是由e f r o s 啼1 等人首先提出，由于该模型很好地抽象出纹理视觉 上相似性的数学特征，使其成为样图纹理合成技术的基础模型，本文讨论的一些 纹理合成算法都是基于这个模型。 单样图合成算法发展到现在，已经有了一套成熟的方法，大都是基于点合成， 块合成，或者两者结合，目前在这个领域更多的研究是将纹理合成的应用。利用 纹理合成技术还可以应用到图像的压缩传输、缺损图像的填充等领域；如将该技 术中的思想应用到计算机动画领域，则可利用一段简短视频图像，生成时域内任 意长度的非重复的视频动画等。因此基于样图的纹理合成技术不仅在计大规模场 景的生成以及真实感图形绘制和非真实感绘制等方面，而且在图像编辑、数据压 缩、网络数据的快速传输和视频等领域也有很强的应用前景。 本文首先对应用在向量场可视化的纹理合成算法进行了改进，通过点合成和 块合成结合的方法更加精确的表现了向量场。在向量场的生成上采取了多种方 法，还引入了使用某些特殊的函数来模拟表示一个向量场，适用这些函数生成期 望的向量场，然后在约束纹理合成框架下，用视频实现了向量场的可视化。最后 本文适用图像分割的方法分离出图像中流体部分，定义了多帧之间点位置的相关 1 浙江大学硕士学位论文 第l 章绪论 性约束，实现静态图像生成动态场景视频，达到模拟场景的功能。 本文安排如下： _ 第2 章中阐述了基于样图的纹理合成领域的研究内容和现状，介绍了一 些经典的纹理合成算法，并指出了纹理合成过程中最为关键的一些问题。 第3 章中在约束纹理合成框架下，使用视频来实现向量场可视化。 第4 章在第3 章基础上，改进了约束，实现了单张图像生成一段视频， 从而起到场景的模拟的作用。 _ 第5 章总结本文的成果，提出今后研究中可以考虑的方面。 2 浙江大学硕士学位论文第2 章基于样图的纹理合成 第2 章基于样图的纹理合成 基于样图的纹理合成是近几年迅速发展起来的一种新的纹理合成技术，它基 于给定的小区域纹理样本，按照表面的几何形状，拼合生成视觉上相似而连续的 整个曲面的纹理。下文将在纹理合成过程中基本概念阐述的基础上，对现有的里 程碑式算法做较为详细的介绍。 2 1 概述 2 1 1 纹理 纹理有自身的特点，首先纹理是一类特殊的图像，其次每种纹理都有其不同 于其他纹理的特征，这些特征可以表达为一系列的统计量，每种纹理合成算法都 无一例外地在探索纹理特征的普遍表达方式，以及合成过程中对这些特征的运 用。使用纹理是为了追求视觉的真实性、减少计算的复杂程度，另外对大规模 场景的复杂建模是非常困难的。物体表面纹理即物体表面的外观效果。 2 1 2 纹理映射和纹理合成 纹理映射( t e x t u r em a p p i n g ) 就是使用图像、函数或者其他数据源来改变物体表 面外观，是将空间三维点转化为纹理坐标，对输入纹理的重采样。纹理映射通常 只能在纹理空间和表面参数空间进行一对一的映射。由于采样区域的局限性，所 获取的纹理样本通常为小块纹理。如将小块纹理映射到大的曲面上将导致映射后 表面纹理模糊不清，若采用重复映射技术则出现表面纹理接缝走样等问题。 纹理合成是为了解决纹理映射中存在的接缝变形以及纹理的获取等问题而提 出的。它在图像编辑、数据压缩、大规模场景的绘制、真实感和非真实感绘制等 方面都有重要的应用价值，一直受到计算机图形学、计算机视觉和图像处理领域 的广泛关注。纹理合成技术是对样本纹理的重建和再组织，纹理合成产生了与输 入纹理“相像”的纹理。 浙江大学硕士学位论文第2 章基于样图的纹理合成 2 2 纹理合成的分类 目前，纹理合成可分为过程纹理合成和基于样本的纹理合成两类方法。过程 纹理合成法将纹理的生长过程表达为数学公式或一个迭代运算的过程，可以模拟 出木纹、云雾、大理石以及动物身上的斑纹等多种自然纹理。这种方法虽然可以 获得良好的合成效果，但对每一种新纹理都需要调整参数反复测试，非常不方便， 而且自然界中的大多数纹理是无法用过程的方式表达出来的。实际上，存在大量 的纹理，这些纹理具有自相似性。即- - d , 块纹理就能反映整体纹理的特点。这就 促使人们着手研究基于样本的纹理合成方法。这种技术可以从一小块块样本纹理 产生出任意大小的合成纹理，而合成纹理与样本纹理看起来好像是用同一规则产 生出来的。 2 3 二维图像纹理合成 二维图像纹理合成算法可以归为两类：一种基于特征匹配方法；另一种采用 m a r k o vr a n d o mf i e l d ( m r f ) 模型。 早期的纹理合成基于纹理分析思想的启发，主要采用统计的方法，通过在样 本图中匹配特征的方法生成新的纹理图。s i m o n c e l l i 等采用统计的方法，通过可 操纵金字塔的图像表示来进行纹理合成，取得了一定的效果n 一1 。h e e g e r 口1 提出了 把随机噪声分层的方法，对随机性纹理取得了较好的效果，但对结构性纹理效果 不是很理想。d eb o n e t 做了进一步的研究，采用两个拉普拉斯金字塔及滤波器处 理纹理，按照金字塔从顶到底的顺序，在查找匹配候选点时同时考虑已经合成的 父层结点，从符合一定匹配条件的候选点中随机选一个填充h 1 。基于多分辨率思 想的图像表达对具有统计特征的纹理取得了较为理想的效果，但对结构较明显的 纹理效果不是很好。 在e f r o s 9 9 年的论文凸1 里程碑式的突破后，纹理合成的研究开始转为基于 m a r k o v r a n d o mf i e l d ( m r f ) 模型，实验证明对于大多数的纹理，m r f 模型是一 种很好的逼近模型，许多算法都基于这一模型啼6 7 引，且取得了较好的结果。m r f 模型认为纹理具有局部统计特征，意味着对一张纹理图，任取其中两小块都是相 4 浙江大学硕士学位论文第2 章基于样图的纹理合成 似的。 2 3 1 基本概念 1 ) 马尔可夫随机场模型 马尔可夫随机场方法是建立在m r f 模型和b a y c s 理论的基础上，m r f 模型提供 了不确定性描述与先验知识联系的纽带。马尔可夫随机过程定义如下：假设一个 随机过程 石( f ) ，t n 的状态空间为j ，如果对时间t 的任意n 个数值 t 2 乙，t ，在条件x ( ) = 葺，毛el ，f = 1 ，2 ，n - 1 下，x 瓴) 的条件 分布函数恰等于在条件x ( 乙q ) - - x , 一- fx ( t , ) 的条件分布函数，即 p x ( 乙) 毛ix ( t 1 ) = 毛，x ( t o = x 2 ，x ( t 。- 1 ) = 一l ，o1 、 = p x ( 乙) i 石( 气一1 ) = 一l 上述随即过程称为马尔可夫随机过程。最初在通过采样语言系统构建了广义 的m a r k o v 链，其思想是根据具有先后顺序的字母构成语法，然后由语法决定下 一个要生成的字母的概率分布。这样就可以由一个字母开始作为种子，反复根据 马尔可夫链产生新的字母从而构建出英文句子( 也许这个句子读起来的意思不合 逻辑) 。将这种方法由一维扩展二维，便产生了m a r k o vr a n d o mf i e l d ( m r f ) 模型。 纹理合成中采用的m r f 模型是根据图像中当前要合成纹理单元( 可以是点也可以 是块) 的邻域，在样本中搜索这样的纹理单元满足它的邻域与要合成的纹理单元 的邻域最相似，然后将这个纹理单元复制到当前要合成的位置上。 m r f 模型强调的是纹理具有局部统计特征，而不是全局统计特征。也就是说 纹理中的任意一部分可以由它周围的一些纹理决定，这是对纹理特征的一种认 识，而且结果上看也是比较成功的。m a r k o v 随机场是图像建模的重要工具，在纹 理合成、纹理分析、图像分割、图像增强、图像压缩中具有广泛的应用。 2 ) 像素点的邻域和纹理块的重叠部分 在采用点合成的算法中，当前要合成像素点( 图2 1 ( a ) ) 的邻域指的是以该像素 为中心的矩形区域与已合成的像素点的交集。样本中每个点的像素的邻域如图 5 浙江大学硕士学位论文第2 章基于样图的纹理合成 2 1 ( b ) 所示。当按扫描线顺序从上到下，从左到右进行合成时，对于当前要合成的 像素点，只有邻域中的上部和左部的像素点是已经合成好的，因此有效邻域是类 似于字母l 的形状( 图2 1 ( c ) ) ，因此我们称之为l 型邻域。邻域的大小决定了 合成的质量和消耗的时间。 舞 羼 图2 1 象素点的邻域 在基于块拼贴的样图纹理合成中，通常使用矩形纹理块( 图2 2 中阴影区域所 示) 。纹理块的边界指纹理块边缘具有一定宽度的区域，通常所说的纹理块边界 指该纹理块与已合成区域重叠的部分。如图2 2 ，按扫描线顺序从左至右，从上 至下逐块合成纹理( 图2 2 ( a ) ( b ) ( c ) 演示了合成顺序) ，其中阴影块为当前待合 成的纹理块，其余白色正方形块为已合成纹理块，红色轮廓线区域既是当前待合 成纹理块的边界，也是与已合成部分的重叠区域。 图2 2 块与块之间的重叠区域 3 ) 像素点的邻域匹配和纹理块的重叠区域匹配 6 骷麓曲 浙江大学硕士学位论文 第2 章基于样图的纹理合成 两个像素点的邻域误差指它们邻域中对应像素点的r g b 值误差之和，即为由两 个像素点确定的形状相同的邻域i ，的误差所定义的厶距离， d ( l ，2 ) =( r ( p ) 一尺( g ) ) 2 + ( g ( p ) 一g ( g ”2 + ( 召( p ) 一b ( g ) ) 2 ( 2 2 ) 鹧热 其中函数( p 硼、g ( p 妇d 、b ( p i x e l ) 分别表示纹理图像的红、绿、蓝三种颜 色的像素值。在基于m r f 模型的逐点合成算法中，需比较输出结果图中当前待合 成像素点与纹理样图中每一个像素点的邻域误差，在误差较小的待选邻域中随机 选择一个作为匹配邻域，此过程称为邻域匹配，由邻域匹配决定的像素点称为匹 配点。 纹理块的重叠部分误差指：将纹理样图中某一纹理块置于结果图中当前待合 成纹理块的位置时，其与结果图中已合成区域的重叠部分( 图2 2 ( a ) ( b ) ( c ) 中红 色轮廓线区域) 的厶距离，如公式( 2 2 ) 所示，此时，m ，m 分别代表位于重叠 区域的纹理块边界和已合成区域边界。 在基于m i 江模型的逐块合成算法中，根据结果图中当前待合成纹理块的位置， 计算纹理样图中的每一个纹理块的边界误差，在误差较小的待选纹理块中随机选 择一个，其边界即为匹配边界，此过程称为纹理块的边界匹配，由重叠区域匹配 决定的纹理块称为匹配纹理块。 2 3 2 典型算法 在基于m r f 模型合成的方法中，合成方式主要有“点匹配和“块拼接 两种 合成方式。在基于点匹配合成隋，6 9 1 的过程中，一般采用蛮力的在样图中搜索所有 匹配点，在符合条件的匹配点中随机选取，每次仅能合成一个点，合成一小块纹 理都需要消耗很长时间。w e i 阻1 采用金字塔多分辨率合成和树型结构矢量编码加速 技术，取得了较好的效果。但自x u 等n 们提出了随机块拼接的快速合成方法后，块 拼接方法晦1 2 1 得到了进一步的改进，合成速度和质量都得到了很大的提高，其中 有些已经接近了实时的效果。当今，由于m r f 模型较好地体现了纹理固有的局部 相关性和稳定性，依然被广泛采用，同时块拼接技术由于其在合成速度和合成质 7 浙江大学硕士学位论文 第2 章基于样图的纹理合成 量上的优势也得到了越来越多研究人员的重视，下面我们将对具有上述特点的几 个典型算法进行简要介绍。 1 ) 非参数的纹理合成 早期的纹理合成算法如n 3 钔等，采用多分辨率金字塔及滤波器进行处理，只 能合成随机性纹理，对结构性纹理的合成效果不理想。在1 9 9 9 年的i c c v 会议上， e 6 o s 和l e 豫g 首次提出了一种基于m a r k o vr 趾d o mf i e l d 模型的合成方法嘲，对结 构性纹理取得了比较好的效果，具有里程碑的意义。 醺里 图2 3 基于m r f 的点匹配 如图2 3 ，其基本思想是在纹理的特征提取中使用m r f 模型，在样图中，取 一个点作为种子写到合成图中，然后从种子的相邻点开始，在样图中移动匹配窗 口，把误差最小的匹配点写入合成图中，如此循环直至填满合成图，得到新的纹 理。若希望每次合成的纹理有一定变化，可设定匹配误差。 2 ) 使用矢量树加速的纹理合成 因为e f r o s 9 9 算法每写一个点都需要在样图中从头到尾的匹配一遍，所以该 算法非常耗时。w e i 阳1 的方法是对e f r o s 9 9 年算法的一种改进，同样基于m r f 模 型，但摈弃了e f r o s l 9 9 9 方法中的概率函数而直接采样，邻域采用三形状，如图2 4 所示。计算时按照扫描线顺序，逐点采样合成。算法如下： 矽 一 浙江大学硕士学位论文第2 章基于样图的纹理合成 黧毽 图2 4 扫描线顺序合成纹理 1 ) 用样本上的象素点随机初始化输出图像，合成时采用扫描线的顺序逐点 合成，l 型相邻域的大小由用户设定，选择的大小要权衡质量和运算时间。 2 ) 在输入样图中寻找这样的点p ，使点p 的邻域与输出图像中当前要合成点 的l 邻域的误差值最小，误差用像素点之间的r g p 差异作为度量。 3 ) 把点p 复制至输出图像中。重复上述过程，直至输出图像合成完毕。 在计算当前点和输入图像中样本点的l 型邻域误差时，采用k 距离作为衡量 尺度。l 型邻域的大小必须覆盖样图中基本纹元的大小，而当l 型邻域的尺度增大 时，计算量平方级增加，为了解决逐点合成速度慢的问题，作者采用金字塔多分 辨率模型进行匹配，并用矢量量化的方法加速匹配点的搜索，使得合成速度有一 定的改善。以上方法都是采用逐点合成的方式，对于随机性较强的纹理达到了满 意的合成效果。但是对于结构性较强的样本纹理，那么采用逐点合成的方式往往 不能保持其结构，合成效果不能令人接受。 3 ) 使用图像缝合进行纹理合成和传输 由于每次一个点的合成方法具有较大的局限性，在合成过程中，实际上相当 一部分后续点的选择已由已合成点所决定，这样许多点的合成其实浪费了时间。 继在i c c v 9 9 上发表了非参数采样的纹理合成3 后，e f r o s 在2 0 0 1 年的s i g g r a p h 会议上提出了一种基于块拼贴的纹理合成算法n 驯，相对以往的点合成算法，该算 法在纹理合成的速度、合成结果的视觉效果方面都得到了很大的提高，避免了以 9 浙江大学硕士学位论文 第2 章基于样图的纹理合成 往算法容易引起的模糊、纹元严重错位等问题。在输入样图中任取一块蜀放在输 出图中，然后在输入样图中查找岛，使垦放入输出图后与岛有一定的重叠区域， 且边界匹配误差控制在一定的范围内；接着在墨，最的重叠区域找出一条误差最 小的路径作为岛的边缘，把垦贴入合成图中( 如图2 5 所示) 。反复重复以上 过程直到获得整个结果纹理图。 图2 5 重叠块间拼接 误差最小的路径通过以下方法进行计算：设置，最具有垂直的重叠边，重叠 区域为群”和硝，误差定义为d ( 筇，霹) 。通过下式获得重叠区最后一行的各点 误差。 巨，- ，= 弓，+ m i n ( 互一l ，互一l ，- l ，互一1 ，+ 1 ) ( 2 3 ) 在获得误差最小的一点后，通过反向跟踪便可获得最优切割路径。水平方向 的重叠可以采用类似的方法获得。当水平与垂直方向都有重叠时，两条路径会有 相交，此时分割边界由两条路径共同决定。从以上的描述可知，算法简单且速度 较快，合成效果好。该算法存在的问题是有时会出现纹理块的重复效应，有些边 界不匹配。 4 ) 自然纹理的合成 a s h i k h m i n 的方法是基于点合成过程的更进一步改进，通过有效的引入了候选 点( c a n d i d a t ep o i n t ) 的概念，有效的加快了纹理合成的速度，对于自然纹理的 合成取得了比较好的效果。算法步骤如下图： 1 0 浙江大学硕士学位论文 第2 章基于样图的纹理合成 图2 6 基于候选点的合成方式 1 ) 生成噪声随机纹理图 2 ) 对当前待合成点，根据其邻域得到原样图中的后选点集合，从集合中找 到最合适的匹配点 3 ) 更新此合成点在输入样图中的来源 4 ) 重复步骤2 ，当所有象素点都合成好则结束。 算法的主要思想是利用已经合成的象素的候选集合来进行待合成点的选择， 例如，图2 6 中，黑框的象素是要合成的象素，通过寻找它邻域的其他象素在输 入图像中的位置( 斜条纹) ，然后偏移相对的位置得到待合成点的候选点集合( 黑 色的点) 。 a s h i k h m i n 的算法速度较快，因为其避免了在整幅样图中全部点的搜索，而只 局限于搜索候选点，因而搜索耗时大大减少。从合成的结果来看，对于自然纹理 的合成，该算法可以取得比较好的效果，但对于结构性较强的纹理的合成不是很 理想。 5 ) 块组合的纹理合成 浙江大学硕士学位论文第2 章基于样图的纹理合成 文章n 铂提出了一种非常有趣的类似于块合成的方法，采取了按照规则拼块的 方法。主要思想是从输入样本中产生小的纹理块集合，然后以这些纹理块为基础 按照规则组合成任意大小的纹理。 _ _ 割 氏阳a 一一 一照i 翻吲一_ 一 嘲 母鹾鞠曩一 一溆厂、篇燃 图2 7 - t i l e 合成示意图 如图2 7 ，4 ，e ，g ，口从块a ，b ，c ，d 中切割而来，a ，b ，c ，d 是由输 入样本中的4 个块按照不同的组合方式组合生成，图中4 种颜色表示不同的块。 然后4 ，忍，q ，d f 经过处理生成以，吃，巴，d 。图2 8 描述了以，吃，巴，d 。的生成 方式，其中a 图就是4 ，b ，c ，口，可以发发现他们是样本中的4 个块的某些位置 上的小块拼接而成，因此有明显的内部边界不匹配。为了解决这个问题，从样本 中寻找到与a 图差异最小的块( 图b ) ，然后在红色的圆的范围里做切割，用b 图 的相应位置填充c 图中白色部分，最后得到d 图。最后作者定义了图2 9 所示的 一组- t i l e 集合，在组合的时候唯一原则是相邻块之间的颜色要相同。 蕊 ，2 霭焱 一崮 w 添，嬷 图2 8 l e 的合成 1 2 戮咖麟埔 浙江大学硕士学位论文 第2 章基于样图的纹理合成 t a ) 僻 图2 9 大小为1 6 的_ t e 集合 2 4 纹理合成的核心问题 2 4 1 合成采样 合成采样是纹理合成中的基础问题，它主要包括如何在样图中选择匹配点、 如何提高邻域采样的匹配搜索效率、以及如何保证局部纹理的完整性等。 i v l r f 合成算法一般采用穷尽法在样图中搜索匹配点，在符合统计条件的待选 点中每次随机选取一个，时间代价较大。近年来，人们对m r f 模型进行了改进。 z h a n g 等提出采用后选搜索、全局搜索和中心搜索相结合的方法提高复杂纹理的 合成速度和质量1 。采用邻域限定的方法可提高效率，且有利于保持纹理的整体 结构，w e i 的算法阳1 采用形邻域规则，直接在指定大小的区域上采样。但工形 度量并未考虑人对边、角等特殊图像特性的视觉感知，缺少了对纹理图像中高频 信息部分的考虑。a s h i k h m i n 嘲对w e i 随1 的算法进行了改进，利用相关性原理，把 搜索范围限制在当前点的邻域，根据l 型邻域点在输入图像中的对应位置，偏移 相应量后获得待选点，然后在待选点中寻找最佳匹配点，改进后的算法不但效率 高于w e i 的算法，而且能够处理更多类型的自然纹理。 e f r o s 在2 0 0 1 年提出i m a g eq u i l t i n g 方法，将选择点转为选块，算法取得了 更好的性能，同时在合成速度上也取得了很大的提高n 引。c h a r a l a m p i d i s n 5 1 在i m a g e q u i l t i n g 的基础上提出了改进算法，先将图像按大小相等分块，然后在块之间进 宙胡两毫酽剐霜器嘏酯凿罗崩斟圈毫出帝器尚淘甲南犍啬娶拶幽圈 浙江大学硕士学位论文第2 章基于样图的纹理合成 行聚类生成新的图像块，并按各块的聚类概率标注它们，合成时标注顺序将作为 一个限定条件。类似的还有l e e n 司在处理块拼接方法的边界问题时，结合了基于 象素的方法，在三形邻域度量中提高了边界点的权重，合成结果取得后，再进行 一次重叠区域的处理，在重叠区域内找到最小误差路径，以此路径为中心划分出 5 个像素宽的修正带，若修正带内的点误差超过指定的值，采用从最小误差路径 起源的区域生长法修复超标点。 合成采样研究的发展表明，点匹配方法除了合成速度慢以外，主要缺陷是误 差积累问题，尤其是对非均匀纹理，合成结果明显较差；但要使合成结果能被适 当控制，很大程度上依赖点匹配方法。块拼接方法不但提高了合成效率，也有利 于保持纹理结构，但难以保证各块间相接部分的连续性。已有的研究中通常取固 定大小的矩形块。比较理想的方法可以尝试基于块状可变区域，据实际纹理的结 构特征确定区域的形状和大小，同时考虑对合成目标的要求，样本图像和结果图 像的对象区域可以有不同的形状和大小。最近的“点块”结合方法是要在合 成效率和质量上达到一定的均衡，是值得考虑的一个研究方向。 2 4 2 重叠区域处理 基于块拼接的算法中，纹理合成的基本单位是块( p a t c h ) ，现有的算法中大多 采用的是固定大小的方形块。在块拼接的过程中，不可避免的涉及到对重叠区域 的处理。最早的处理方法有i m a g eq u i l t i n g 【1 3 】中基于动态规划的切割方法，分别对 于水平重叠区域和垂直重叠区域进行处理，在得到两条切割线后通过求交集得到 重叠区域的最优划分。基于动态规划算法的重叠区域处理，其时间复杂度为o ( n ) ， 计算起来很快，且具有比较好的划分效果。但缺点是合成过程中一般是基于方形 区域处理，处理范围受到限制。在e f r o s 0 1 年方法的基础上，n e a l e n 等【1 7 】对于重 叠区域的处理采用了递归划分的方法，如果从候选样图中搜索得到的匹配块的距 离值大于用户设定的阈值，则通过对区域进行四等分，然后将更小块的纹理去样 图中搜索以获得更加匹配的纹理块。这种区块分裂的方式在一定程度上取得了比 i m a g eq u i l t i n g 更好的效果，但其算法在重叠区域的计算上仅仅考虑的是区域间色 1 4 浙江大学硕士学位论文 第2 章基于样图的纹理合成 彩的不匹配，对于细节较多的纹理不太适用。k w a t a 1 3 】等在其方法中提出了利用 g r a p h = c u t 技术来处理重叠区域，其基本思想是将重叠区域看成是一个连通网络， 通过对该网络计算最大的网络流来获得该区域的最优剖分，由于网络流问题被证 明为n p 问题，因此现有的算法都是通过加入一定的限制条件来获得问题的近似 最优解。实验证明，c a a p h - c u t 算法对于大多数纹理的合成都有比较好的效果。 如何提出更好的重叠区域处理技术将直接影响到多样图纹理合成中过渡部分的 视觉效果。 2 5 本章小结 本章首先介绍了基于样图的纹理合成的基本概念和典型算法，包括经典的点 合成，块合成以及 r i l e s 组合合成，同时提出了纹理合成中比较核心的两个问题， 纹理合成技术的进步主要是如何处理好这两个问题。本章为纹理合成在其他领域 中的应用打下基础。 1 5 浙江大学硕士学位论文第3 章视频实现向量场可视化 第3 章视频实现向量场可视化 3 1 基于纹理合成的向量场可视化 向量场的可视化溉魂翦1 对理解复杂的流体机制有着十分重要的作用。为了研 究流场中的物理规律，传统的实验方法是在气体或液体中注入可见物质( 如烟雾、 染色剂) 或用传感器获取测量数据。一方面，由于现在高速流体实验所要求的精度 较高，这些物质或测量工具的存在影响了实验精度，而且高速流体实验对实验设备 的要求较高，也使目前流体实验的费用持续增长。另一方面，由于计算机技术的高 速发展，计算成本不断下降，计算精度和速度不断提高，这就使对复杂物理现象的数 值模拟成为一种更直接、更有效的方法。而且三维大规模数值模拟可产生上百兆 甚至上千兆的数据我们已无法用传统的方法来理解如此大量的数据中所包含的 复杂物理现象。因此，大规模向量场的可视化技术已成为流体力学研究中不可缺少 的手段，具有重大意义。 3 1 1 向量场的常用表示方法 目前已经提出了很多种向量场的表示方法，下面简单的介绍几种： 简化为标量 这种方法不是直接对向量进行可视化处理，而是将其转换为能够反映其物理 本质的标量数据，然后对标量数据可视化。例如，向量的大小、向量与给定方向的 点积、单位体积中粒子的密度等。这些标量的可视化可采用常规的可视化技术， 如等值面抽取、体绘制等方法。 _ 箭头表示法 向量的显示要求同时表示出向量的大小和方向信息，最直接的方法是在向量 场中有限的离散点上显示带有箭头的有向线段，其线段长度表示向量的大小，箭头 表示方向。这种方法适用于二维向量场。对于二维平面上的三维向量，也可用箭头 来表示，箭头可指向显示表面或由显示表面指出。同时，用这种方法可表示定义在 体中的三维向量，并可采用光照处理或深度显示以增加真实感。利用向量的颜色可 1 6 浙江大学硕士学位论文第3 章视频实现向量场可视化 表示另一标量信息或另一个变量。这种箭头表示方法只能表示离散点上的向量， 且仅适用于数据量较少的情况，当数据量太多时，尤其是对于三维向量场，会使图像 杂乱难以理解。 流线、迹线、串线、时线 向量场中，线上所有质点的瞬时速度都与之相切，这样的线称为场线。在流体 力学中速度向量场中的场线称为流线。迹线是在流场中释放的粒子的流动轨迹。 串线是在流场中连续释放的粒子所连成的线。对定常流场，流线、迹线、串线是一 致的，但对非定常场则不然。时线是由一系列相邻流体质点在不同瞬时组成的曲 线。在层流中，某一时刻沿垂直于流动方向的直线同时释放出许多小粒子，这些粒 子在不同时刻组成的线就是时线。 3 1 2 纹理合成实现向量场可视化 使用纹理合的方法实现完整的向量场可视化，需要综合考虑向量场大小和方 向两方面信息，再将变化趋势在同一幅合成图中体现出来。t a p o n e c e o 田1 利用纹理 点合成技术实现了向量场的可视化，其思想是在合成每一个点的时候，根据这点 的向量场大小和方通过对原始纹理进行旋转和缩放生成采样纹理，然后运用传统 的点合成方法进行合成，然而这种方法具有点纹理合成所具有的缺陷台成速 度慢，原始纹理的结构容易被破坏，合成效果不理想。林亮亮扬刚等呦3 改进了点 合成算法的缺点，采用了块纹理合成方法，参照所需要反映的向量场，逐块合成 纹理以实现向量场的可视化。下面简单介绍算法步骤： 样本纹理集的生成 将向量分成n 区间，向量大小分成m 等级，对原始纹理进行旋转和缩放， 生成一个包含n x m 个纹理的样本纹理集。在纹理合成过程中，向量场中每个分 块区域都按照其内部的平均向量值选用相应的样本纹理进行合成。m 和n 越大， 就可以越自然的反映向量场的变化，但同时也增加了空间开销和复杂度。如图3 1 就是对样本进行了放大缩小和旋转产生的样本集中的几张图像，其中对样本作了 4 种大小的放大缩小，并且旋转了2 4 个角度，图中显示的是旋转4 5 度和2 7 5 度 1 7 浙江犬学硕士学位论文第3 章视频实现向量场可视化 之后的样本。 熏囫回 霞 熏 _ 向量场分析与合成方案 图3 1 样本的放缩和旋转 现有的纹理合成采用块和点结合的纹理合成方式对向量场进行逐块合成。由 于同一块内的向量值可能会出现比较大的变化，因此不能笼统的采用同样大小的 合成块进行合成，采用了自适应分割的策略。用合成块内的向量值的方差作为判 断块内向量是否基本一致的标准，如果某合成块内的向量值的方差小于某预设的 分割阈值，就认为此块内的向量值基本一致，此块可以作为最终