（计算机应用技术专业论文）形状上下文保持的二维变形及其图示可视化.pdf

浙江大学硕士学位论文摘要 摘要 图示可视化( i l l u s t r a t i v ev i s u a l i z a t i o n ) 融入艺术表达方法，将物体或对象的视 觉特征直观地、抽象地表达出来，被广泛应用于医学教学、手术训练、流体模 拟等领域。本文提出一种基于梯度域网格编辑的二维形变算法，并将其用于物 体形变的图示可视化。 本文的核心思路是将形状变形的问题转化为对二维微分网格的操纵，并用 泊松方程进行求解。与前人方法相比，我们对传统的泊松网格编辑有如下改进： 首先，引入了各向异性的物理特性，可以为不同区域设置暑y 方向上不同 的材质属性。这样既可以模拟骨骼的刚性，又可以模拟类似肌肉组织等在各向 异性的弹性。 其次，本文重点探讨了从已有图例中学习形状风格的方法，可以将参照图 例的形状风格通过轮廓学习移植到目标图例中，这对于图例的再创作有重要的 意义。 最后，我们从生物形态学引入了形状上下文的概念，即用一系列关键特征 点之间的相对位置描述不同物体之间的形状区别。通过形状上下文对变形的约 束，本文方法可以在变形中保持对象的重要全局形状特征不变。 实验结果表明，本文方法在视觉效果和物理真实度上效果理想，交互速度 达到实时，用户操作较常规的三维变形方法简单。专业医学图例艺术家对我们 开发的系统给出了较高的评价。 关键词：图例图示可视化图像变形微分网格泊松方程 浙江大学硕十学位论文a b s t r a c t a b s t r a c t i l l u s t r a t i v ev i s u a l i z a t i o n e x p l o i t s e f f e c t i v ev i s u a la b s t r a c t i o n st o e x p r e s s t h e v i s u a l i z a t i o ni nac l e a r l yu n d e r s t a n d a b l ew a y i th a sb e e nw i d e l yu s e di nm e d i c a l e d u c a t i o n ，s u r # c a lt r a i n i n g ，a n df l u i ds i m u l a t i o n w ep r e s e n tan o v e l2 ds h a p e d e f o r m a t i o na l g o r i t h ma n de x p l o i ti tf o ri l l u s t r a t i v ev i s u a l i z a t i o n i nt h ek e r n e lo fo u ra p p r o a c hi san e w2 dg r a d i e n td o m a i nb a s e dm e s h m a n i p u l a t i o na l g o r i t h m w h i c hi ss o l v e dw i mp o i s s o ne q u a t i o n c o m p a r e dw i t h p r e v i o u sm e t h o d s , o u rs o l u t i o nh a st h ef o l l o w i n gi m p r o v e m e n t s ： f i r s t , w ei n t r o d u c ea na n i s o t r o p i ep h y s i c a lp r o p e r t i e sf o ri n d i v i d u a li l l u s t r a t e d o b j e c t s ，l e ，a s s i g n i n gd i f f e r e n tr i g i d i t i e st os e p a r a t e d2 dr e g i o n sg o n gxa n d ya x e t h i ss c h e m ef a c i l i t a t e sp h y s i c a l l yp l a u s i b l es i m u l a t i o nf o rn o to n l yt h ef u l lr i g i d o b j e c t sl i k eb o n e s ，b u ta l s oa n i s o t r o p i co b j e c t sl i k em u s c l e o u rs e c o n dc o n t r i b u t i o ni sac u r v ea n a l o g yb a s e ds h a p es t y l et r a n s f e rt e c h n i q u e f r o mr e f e r e n c ei l l u s t r a t i o n s o u ra p p r o a c ha l l o w sf o rl e a r n i n gd i s t i n c t i v es h a p e s t y l e si na ni n t u i t i v ef a s h i o n , g r e a t l yc o m p r e h e n d i n gt h er e - c r e a t i o nc a p a b i l i t yo f i l l u s t r a t i v ev i s u a l i z a t i o n a g a i n , i ti sa c c o m p l i s h e du n d e rt h ed i f f e r e n t i a lc u r v ea n d m e s he d i t i n gf r a m e w o r k f i n a l l y , w ei n t r o d u c et h ec o n c e p to fs h a p ec o n t e x tt h a th a sb e e na d o p t e di n b i o m o r p h i s m w ef o r m u l a t et h es h a p ec o n t e x to fa nu n d e r l y i n go b j e c ta sam e s h e n n s t r u e t e df r o mas e to fs e l e c t e df e a t u r ep o i n t s b yk e e p i n gt h ed i f f e r e n t i a l p r o p e r t i e so ft h em e s hu n c h a n g e dd u r i n gd e f o r m a t i o n ，s h a p ep r e s e r v i n gi l l u s t r a t i v e v i s u a l i z a t i o ni sc o n v e n i e n t l ya c h i e v e d w eh a v eb u i l ta i li n t e r a c t i v es y s t e ma n dt e s t e dc o m p r e h e n s i v ee x a m p l e s e x p e r i m e n t a lr e s u l t ss h o wt h a tv i s u a l l ya n dp h y s i c a l l yp l a u s i b l ei l l u s t r a t i o n so f a n a t o m yd e f o r m a t i o nc a nb ee a s i l yf u l f i l l e di nr e a l - t i m e p r e l i m i n a r ye v a l u a t i o n s a n df e e d b a c k sf r o mm e d i c a li l l u s t r a t o r sa r eq u i t ee n c o u r a g i n g k e y w o r d s ：i l l u s t r a t i o ni l l u s t r a t i v ev i s u a l i z a t i o ni m a g ed e f o r m a t i o n d i f f e r e n t i a l m e s hp o i s s o ne q u a t i o n 浙江大学硕士学位论文第1 章绪论 第1 章绪论 图1 1 两个图示可视化例子。( a ) 手工生成的头部图例；( b - c ) 使用本文方法的变形结果， 分别为过度扭曲( h y p e r f l e x i o n ) 和过度伸展州y p e 雠t e m i o n ) ；( d ) 人的足部体绘制图例；( e ) 根据图中缩略图的样式，通过三维变形获得的体绘制结果；( d 采用本文方法的变形结果。 用户对( e ) 和( 帔形所耗费的时间约为1 5 分钟和1 分钟。 1 1 图示可视化简介 图例( i l l u s t r a t i o n ) 又称插图、插画，它的主要功能是将文字内容、故事或思想 以可视化的方式呈现。图例的功能十分广泛，凡书籍、杂志、报纸、说明书、文 献、教科书等刊物，在文字中插入的装饰文案、绘画，都统称为图例。传统的图 例由艺术家手工绘制生成。 图示可视化( i l l u s t r a t i v ev i s u a l i z a t i o n ) 是一种通过有效提取对象的视觉特征， 并将其直观地表现出来的计算机绘制方法。它的目的是让读者更加容易理解图例 中的重要信息，增强图例的描述性。在计算机图形学和科学计算可视化领域，科 浙江大学硕i 学位论文第1 章绪论 研人员提出了大量基于非真实感绘制( 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 ) 3 和体图解 ( v o l u m ei l l u s t r a t i o n ) 1 4 的可视化方法，广泛应用于艺术风格和概念的模拟，这其 中包括对颜色、模式、纹理、媒介和阴影等效果的变化和增强【3 ，7 ，2 5 ，2 8 ，3 2 。 迄今为止，图示可视化的研究的对象大多为静态物体。而模拟物体对象的变 形和运动的动态过程，对于医学科研教学、手术模拟训练、流体运动模拟等具有 重要的意义。例如，医学训练时需要解释人体四肢和器官等运动，它们通常由两 块以上骨骼和软骨联合运动而组成【3 l 】。在教学过程中用文字难以描述清楚，而 用可视化的方式表达则清晰直观。传统的手工绘制方法要求艺术家逐个测量模型 尺寸，手工制作运动的关键帧模型【2 2 】。这不仅对艺术家的创作能力提出高要求， 而且制作一组图例序列需要耗费大量的精力和时间。以计算机为工具的图示可视 化技术可以辅助艺术家交互构建模拟对象的三维模型，并利用已有的变形技术得 到一系列图例 2 5 ，2 7 ，3 8 ，4 0 。这种方法适用于场景并不复杂的简单图例，但对 于场景或变形十分复杂的情形( 如图1 1 ( a ) ，( c ) 所示) ，整个处理过程将非常繁琐 和耗时。现有的物体变形可基于曲面表示或体素表示，由于三维数据的巨大计算 量，便捷、交互式的三维曲面变形仍然面临巨大的挑战。另一方面，采用体素表 示并利用三维体变形需要更多的处理单元( 通常的体素个数以百万计) 。现有大 多数可视化方法只能对有限种类的变形进行模拟 7 ，8 ，1 1 ，1 6 ，4 6 。 1 2 相关工作 1 2 1 计算机生成科学可视化图例( c o m p u t e r - g e n e r a t e ds c i e n t i f i ci l l u s t r a t i o n ) 科学可视化图例 1 0 ，3 7 1 是一种通过对物体局部特征和艺术特征的抽象来获 得更加直观的图例的方法。除了画笔和画j 目1 2 2 1 ，现代的图例艺术家常常使用诸 如a d o b ei l l u s t r a t o r 和c o r e l d r a w 之类的商业软件来辅助完成二维图例的设计工 作。这些软件允许用户采用鼠标拖取控制点生成物体的几何变形。 在计算机图形学和体可视化领域，图例对象通常用三维表面模型或体模型表 示。在此基础上展开的工作有基于点、线段、表面和体绘制【9 ，1 4 ，1 5 ，1 8 ，2 9 等， 同时还包括切割视1 虱 1 1 ，1 3 ，物体横切面纹理合成【3 2 】和体变形【6 ，8 ，1 1 ，4 6 等多 种可视化手段。相比之下，二维图示可视化所受关注不多，一个已知的例子是二 维不可压缩流的多值数据可视化算法【2 6 】。 一2 一 浙江大学硕士学位论文 第1 章绪论 1 2 2 基于样例的建模与绘制( e x a m p l e - b a s e dm o d e l i n ga n dr e n d e r i n g ) 基于样例的建模与绘制方法通过模拟已有样本的风格和模式来合成新的图 例。纹理合成 2 8 ，3 2 是这类方法中一个有代表性的工作，它已经被广泛应用于 体图例的绘制中。基于样例的方法还包括图像类 = l ( i m a g ea n a l o g y ) 2 0 和绘制风 格类比( r e n d i t i o n a n a l o g y ) 1 9 等。这类方法的核心是学习已有对比图例的变化规 则，并将此规则应用到新的图例上。其中，常用的曲线类t ： ：( c u r v e a n a l o g y ) 算法 【2 1 的基本思想是将一条曲线上的标记顶点位移转移到另外一条曲线上；而网格 类e g ( m e s ha n a l o g y ) 算法【4 5 】则是在网格的轮廓上进行曲线类比操纵，从而达到 修改网格形状的效果。 ( a )( b )(c)(d) 图1 2 图像类比( i m a g e a n a l o g ) , ) 【2 0 】中的图例。( a ) 输入的图例；( b ) 与( a ) 类比的图例；( c ) 输 入的图例；( d ) 根据( a x b ) 样例风格学习的类比结果。 1 2 3 微分网格操纵( d i f f e r e n t i a lm e s hm a n i p u l a t i o n ) 受泊松图像编辑( p o i s s o ni m a g ee d i t i n g ) 3 3 的理论启发，微分网格操纵技术 【3 6 ，4 4 在近年来逐渐成为研究热点。与传统的表面模型操作不同，微分网格操 纵技术使用微分属性作为变形过程中的参照量。由于微分属性常常和几何细节与 特征相关，因此，通过改变网格微分属性并用全局最优化方法重建顶点位置，微 分网格操纵技术能够最大程度上保持原有的几何特征，还可以避免逐点编辑所引 起的误差。 一j 一 浙江大学硕十学位论文 第1 章绪论 (a)(b) 图1 3 文献【4 4 】基于梯度场的泊松网格编辑方法中的图例。( a ) 输入的网格模型；( 帔形结果。 1 2 4 基于体模型操纵的图例( v o l u m e t r i cm a n i p u l a t i o nb a s e di l l u s t r a t i o n ) 传统的体模型操纵和体变形使用体素或四面体作为基本元素，在实现内部结 构描述和保持体积等物理变形效果方面要优于曲面变形。然而，体操纵中使用的 三维像素数量众多，其困难远大于曲面操纵。 在体图例中，已有的切割、重影和选择性的变形技术【6 ，7 】采用改变可见性 的方式来显示内部结构和重要特征，但并不涉及物体的变形模拟。尽管特征对齐 的变形( f e a t u r e a l i g n e dd e f o r m a t i o n ) 1 1 】和分解视图( e x p l o d e dv i e w ) 8 的方法能 交互地操纵体模型，却局限于规则的、简单的变形效果，对于复杂的、需要高度 物理真实感的变形无能为力。 一4 一 浙江大学硕士学位论文第1 章绪论 图1 4 基于体模型操纵的图例。( a ) 文献【1 1 】中有关特征对齐变形的图例；( b ) 文献【8 】中分 解视图( e x p l o d e dv i e w ) 的图例。 1 2 5 图像变形和操纵( i m a g ed e f o r m a t i o na n dm a n i p u l a t i o n ) 已有的图像变形和操纵方法大多直接以像素为操纵对象直接变形。例如， b a r r e t t 等提出了一种空间扭曲变形方式对图像进行编辑【1 】。b o o k s t e n 等使用薄 板样条( t h i n p l a t es p l i n e s ) 来拟合多个特征点，从而达到空间变形目的【4 】。这类方 法的一个缺点是将变形表达为一个全局的光滑曲面变形，导致在局部上可能出现 不一致的缩放或剪切。尽管最近提出的移动最小二乘法( m o v i n gl e a s ts q u a r e ) 3 4 】 综合仿射、相似和刚体变换并获得作用于局部图像区域的解析解，但它仍然属于 图像扭曲方法，且难以模拟不同变形区域的不同物理属性。 通过对图像的不同区域进行三角网格化，并依赖二维网格的拓扑关系进行变 形，i g a r a s h i 等提出一种交互的刚性保持( a s r i g i d a s - p o s s i b l e ) 的形状操纵系统 【2 3 。为了达到交互，该算法采用两步法近似优化刚体变换中的未知参数。这种 方法的缺点在于不适用于非刚体形变的模拟( 如肌肉组织的弹性模拟) 。此后， w e n g 等使用了一种新的基于l a p l a c i a n 微分坐标的非线性最小二乘形状变形算 法【4 2 】。通过保存形状边界上的拉普拉斯坐标，这种方法能够较好地保持物体外 形。它的缺点在于难于保持内部各结构之间形状，因而其变形结果与物理效果并 一5 一 浙江大学硕士学位论文第1 章绪论 不一致。 图1 5 文献 4 2 1 q b 基于l a p l a c i a n 微分坐标的非线性最小二乘形状变形图例。 1 3 论文的工作及结构 1 3 1 本文的主要工作 本文创造性地提出一种可视化物体变形的新思路，即直接在输入的可视化图 例或艺术图像上进行变形。它的一个直接优点是将复杂的三维物体变形的可视化 转化成为对二维可视化结果的变形，不仅操作简单直观，而且大大降低了计算量， 获得的变形结果不受绘制条件的限制，视觉效果逼真。 本文方法的一个非常有潜力的应用是对三维体可视化的结果进行变形后处 理。如图1 1 ( d ) 所示，在用户指定了视角和光照参数后，可以获得一张二维图例， 对其变形即可得到图1 1 ( f ) 。从这个角度上说，本文的方法可以作为已有三维图 示可视化技术的一个有力补充，尤其在解剖学、医学研究等需要动态演示的应用 场合具有重要意义。图1 1 ( b ) 和( c ) 展示了用本文方法获得的变形效果，其结果与 现有的三维可视化方法相比毫不逊色。 从计算机视觉的角度来看，形状是视觉系统中物体识别的一个重要特征，因 此图例的表现力好坏直接受其形状和形状变化的影响。一个好的手绘图例想要传 递更多信息，消除歧义，表现复杂的动态过程，除了需要有效的绘制技术，还必 须对模拟对象的形状和形状处理风格进行更深层次的挖掘 1 0 ，2 2 ，3 7 。然而，现 在大多数计算机生成的可视化方法都着重考虑物体的外观和光照效果，忽视了形 一6 一 浙江大学硕士学位论文 第1 章绪论 状的变化对视觉效果的影响。 根据几何学理论，形状可以定义为变化过程中的一系列等价类。但是这个定 义只能用于判断两个形状是否完全相等【2 】，而不能量化两者的相似程度。为此， 在图示可视化时，我们必须拓展形状的定义。生物医学领域的形态测定学中提出 了形状坐标概念【5 】，通过对形状和其变化的程度来判断生物种类。例如，图1 6 ( a ) 和( b ) 示例了两条不同品种的鱼，它们的形状可以通过一个简单的几何形变来描 述，因此它们属于同一个物种【3 9 】。为了区分不同的物种，需要对这些变化进行 进一步分析，并基于此结果定义一系列的形状描述符【5 ，2 ，4 3 1 。 圈1 6 鱼的图例。伉b ) 神仙鱼( p o m a e a m h u s ) 和鹦嘴鱼( s c a r u s ) 的手绘图例，它们的外形可以 用基于区域的线性或非线性坐标变换关联【3 0 】；( c ) 神仙鱼的图例 2 4 】；( d ) 本文方法分析 出( a ) 和( b ) 的形状上下文特征，并将之应用于( c ) 获得的变形结果。 迄今为止，对如何描述和量化两个物体的相关度的研究不多。本文将这种形 状上的不相似度称为形状上下文( s h a p ec o n t e x t ) ，它将几何细节抽象化，并表达 为形状上的风格。尽管已有大量有关自动或半自动学习绘制风格 1 9 ，2 0 ，2 1 ，2 8 ， 4 5 1 约i - 1 - 作，但如何描述和学习形状风格仍然是一个有挑战性的问题。其中很大 部分原因是当前基于三维曲面或体模型的变形对用户的操作水平要求高。即使对 一 一 浙江大学硕士学位论文第l 章绪论 于有经验的艺术家，直接编辑三维模型达到随心所欲的效果也非易事。 在二维图示可视化方案中，本文方法将二维图像变形视为对用户指定的微分 网格进行操纵。与面向数字娱乐的二维变形方法相比，我们的方法充分考虑了材 质属性对变形的影响，并将材质属性和形状上下文属性集成到交互变形的框架 中，因此适用于对形状风格要求高的图示可视化领域。此外，为了允许用户学习 参考图例中的形状风格，我们的系统还研究了基于学习的形状转移技术，如图 1 1 ( f ) 所示。 1 3 2 本文的结构安排 本文的内容组织安排如下： 第二章介绍微分网格编辑和泊松方程数值解法的原理和预备知识； 第三章介绍基于形状上下文的图示可视化变形算法； 第四章介绍在变形算法框架下的形状风格学习算法； 第五章介绍基于本文方法开发的图例变形平台； 第六章展示部分图例实验结果并讨论失败案例； 第七章总结本文贡献并展望前景。 一8 一 浙江大学硕士学位论文第2 章微分网格处理原理 第2 章微分网格处理原理 2 1 三角网格化 网格( m e s h ) 是几何模型的常用表示方法，任意网格s 可以表示成为二元组 s = ( k ，v ) ，其中矿是二维顶点坐标的集合，记为v = 1 ，r 2 ，k 描述了网格 中各个顶点问的连接关系。如果网格s 中出现重合的顶点v ，= v ，( i 力，则称为 退化网格，否则称为非退化网格。对于退化网格，在计算一些重要几何参数时会 出现退化现象。 域网格( d o m a i nm e s h ) 是作为定义域的网格，其上顶点坐标可以视为定义在 其上的函数。由于网格本身除了包含拓扑信息之外还具有几何信息，因此它为考 察所定义函数提供了内在的几何度量。 网格三角化指根据已有的顶点集合生成符合一定条件三角网格，是计算几何 中重要的研究课题，它在有限元非结构化网格生成、实体造型、曲面逼近等领域 有着广泛的应用。根据不同的优化准则产生不同的三角化方法，其中d e l a u n a y 算法是应用最广泛的方法，它的三角化结果在整体形态上最优。 2 1 1d d a u n a y 三角化 图2 1v o r o n o i 图和d d a u n a y 三角网格 一9 一 浙江大学硕士学位论文 第2 章微分蜘格处理原理 在一个顶点集合v = v ，r 2l f 3 上定义一个区域胄，用d ( 一，v ，) 表示和 v ，问的欧氏距离。若矿所有顶点均不三点共线或四点共圆，且区域r ，满足条件 r ，= 和r lc l ( x ，e ) a ( x ，v a i j ) ，则称r ，为顶点v 的v o r o n o i 图。 在区域胄上定义线段集合k = “v ，iv ，v ，v ，置a 月，妒，i ，) ，则 s = ( 足，矿) 称为矿点集的d e l a u n a y 三角网格，如图2 1 所示。d e l a u n a y 三角网格 的外边界是凸多边型，它由连接v 集中的凸集而成，通常称为凸包。 d e l a u n a y 三角化的输入数据通常为散乱点，即位置分布不规则，没有空间拓 扑关系的点集。d e l a u n a y 三角化方法能自动求出任意离散数据点的空间拓扑关 系，且由这种方法产生的单形簇不存在循环式的遮挡关系。d e l a u n a y 网格具有两 个重要的性质。第一，在由顶点集y 所形成的d e l a u n a y 网格中的每个三角形的 外接圆均不包含点集y 中的其它任意点；第二，在由点集矿所能形成的所有三 角网格中，d e l a u n a y 网格中三角形的最小角度最大。这些性质决定d e l a u n a y 网 格是用于网格变形的最佳二维平面三角网格。 2 1 2 带约束的d e l a u n a y 三角化 如果给定的初始条件出了点集，还有一些连接部分点之间的约束线段( 即 d e l a u n a y 三角化必须通过这些线段) ，需要采用改进的d e l a u n a y 三角化方法，即 带约束的d e l a u n a y 三角化。为了满足此约束，生成的网格边界上的三角形并不 完全符合d e l a u n a y 标准( 参见图2 2 ) 。 图2 2 带约束的d e l a u n a y 三角化结果。边界上的k 边所对应的三角形并不符合d e l a u n a y 三 角形标准，但是如果忽略边界外的顶点则符合约束的d e l a u n a y 标准。 一1 0 一 浙江大学硕士学位论文第2 章微分嘲格处理原理 2 1 3 保形d e l a u n a y 三角化 保形d e l a u n a y 三角化方法除了允许添加约束线段，还允许在线段上增加 s t e i n e r 点，从而将线段细分为多段。由此生成的网格不但可以保持d e l a u n a y 属 性，还可以满足对三角形的最小角度和最大面积的约束。 2 1 4 带约束的保形d e l a u n a y 三角化 带约束的保形d e l a u n a y 三角化方法也包含s t e i n e r 点，与保形的d e l a u n a y 三 角化方法不同的是，它仅要求生成的三角形满足约束的d e l a u n a y 标准，而不需 满足d e l a u n a y 标准。因此，通常情况下，这种方式生成的网格的顶点数比同等 质量的保形d c l a u n a y 三角化方法少。 2 2 网格微分表示方法的理论框架 网格的微分表示建立在微分几何领域的一些最新成果上，涉及了离散微分几 何理论和定义在离散网格上的微分方程理论。它的建立为分析几何特征和理解内 部结构提供了新的手段，构成了一整套与已有表示方法不同的新框架，其特有性 质为设计新的网格处理方法提供了新的理论基础。下面介绍一些基本定义： 2 2 1 网格上的场 对于一个任意的平面非退化域网格s ，如果存在标量函数，在网格上任意一 点v f 处取值八_ ) = z ，在其它任意点处取值为厂( v ) = ，办( v ) ，其中z 是一个 标量，痧( ) 是分段线性基函数，在顶点v ，处值为1 ，在其它顶点处值为0 。则称 函数厂是定义在域网格s 上的标量场。 对于一个域网格s ，如果存在向量函数w 在网格上任一三角形z 处取值为常 数m ，则称函数w 为定义在域网格s 上的向量场。 2 2 2 离散微分算子 离散梯度算子的定义依赖于域网格上的分段线性基函数的梯度v 破( d ，由此 一1 1 浙江大学硕士学位论文第2 章微分网格处理原理 可定义在s 上任意标量场，上的离散梯度算子为： v ( v ) = ，v 以( 力 ( 2 1 ) 在网格s 上三角形7 = ( q ，v 2 ，v 3 ) 内任意点v 处，其三个顶点的分段线性基函 数破、欢、丸的数值与v 点相对于三个顶点的重心坐标分量相等。因此，在每个 三角形内，其值为常数。 由此可以定义v ，处离散散度算予耳丁( v ) 为： d v 夥( 一) = ( v 厂( r ) v 谚i t ) - 4 ， 其中， 0 0 ，) 表示项点一所处的一阶邻域集合，4 表示三角形丁的面积。 结合上述梯度算予和散度算子的定义，可以得到h 处的离散拉普拉斯算子： 矽( v f ) 净去( c o t 马+ c o t c j x f 。一乃) ( 2 3 ) r ，e n r ( v t ) - 其中，( q ) 的定义与公式2 2 相同，只和c j 分别为( e ，v ，) 边的对角，参见图2 3 。 2 2 3 二维变换 图2 3 顶点”的一阶邻域 二维变换是二维网格变形的常用手段，在计算机图形学中被广泛使用。常见 一1 2 浙江大学硕士学位论文第2 章微分网格处理原理 的变换包括平移、旋转和缩放。如果顶点使用齐次坐标表示，这些变换可以由3 3 的矩阵表示。平移矩阵可以如下定义： r = 医i：； 其中( ，t ，) 是平移向量；绕坐标原点旋转的变换矩阵可以定义为： r c o s 8 r ：is i l l 占 【0 一s i n 0 0 c 。s 口ol 0 1 j 其中口为旋转角度；而缩放矩阵则可以定义为： s = 瞳渊 其中( s ，s ，) 是缩放因子。 使用矩阵定义后，网格的二维变换则可以使用矩阵乘法的形式表示。 2 3 微分网格操纵框架 ( 2 4 ) ( 2 5 ) ( 2 6 ) 任何不破坏网格顶点拓扑关系的变形算法都可以视为构造一个映射m ) ，将 网格中任意顶点v ，从空间坐标映射到变形后的空间位置v j 。以自由变形技术为 例： s = c ( s 。) ， s = c ( 砖) 一1 3 一 ( 2 7 ) 浙江大学硕十学位论文第2 章微分删格处理原理 其中s ，s ，分别表示原始模型网格和代理模型网格，c 表示原始模型相对于代理 模型的参数化函数，同样s + ，表示变形后的原始模型网格和代理模型网格。由 此可见，在变形过程中函数c 不变，因此映射关系d 可以直接通过c 和s ：求出。 由于自由变形中映射d 是逐点定义的，而代理模型网格的变形是任意的，因此原 始网格中邻接顶点的位移可能不一致，从而不能保证变形结果中的几何细节得到 有效的保持。 微分变形技术则可以概括为： s = p ( g ”) ， s = p ( g “、m = x , y 其中，g “和g 1 表示变形前后网格顶点坐标五y 分量对应的梯度场，以) 表示 基于泊松方程的重建算子。 由于梯度场的操纵建立在局部变换基础上，因此在微分网格变形中，其微分 属性保持不变。与自由变形技术不同，微分变形技术并不逐点定义映射关系，而 是通过线性全局优化过程获得结果，因此变形结果中几何细节得到了有效保持。 微分网格操纵整体框架可以分为三个组成部分：微分表示、属性操纵和坐标 重建。 2 3 1 网格的微分表示 微分网格操纵中最重要的步骤是将网格模型的顶点坐标转化为定义在域网 格上的标量场，即给出它的微分表示形式。 给定域网格s ，可以将它的顶点坐标视为在域网格上的两个标量场 s ”( 所= 工，j ，) ，使用离散梯度算子对其进行梯度运算，可以得到两个梯度场 v s ”沏= x ，y ) ，即网格的微分表示。这个变换将需要分析的变形问题从传统欧 式空间中的顶点坐标转换到域网格上的离散微分属性。 由于网格任一顶点v 的微分属性直接依赖于它的邻接顶点，因此微分属性构 建了各个顶点坐标之间的全局联系。 一1 4 浙扛大学硕士学位论文第2 章微分网格处理原理 2 3 。2 微分属性的操纵 有了网格微分表示，就可以通过微分属性的操纵完成几何处理过程。本文采 用的是基于泊松方程的梯度场操纵方法。作为微分属性，梯度可以方便地进行局 部修改。在编辑过程中，用户通过交互工具对控制区域进行变形，系统会自动将 形变结果映射为局部变换，然后将局部变换扩散到全局中。由于扩散的过程是一 个连续光滑的过程，因此得到的扩散结果也必然光滑。 交互的方式也有要求。常规的二维变换，即平移、缩放和旋转并不会改变彼 变换区域的微分属性，因此可以保持网格的局部细节。 2 3 3 坐标的重建 坐标的重建指在微分属性操纵之后将其结果转换为顶点坐标。从修改后的梯 度场得到标量场s ”沏= x ，y ) 的过程，可以通过求解以下的泊松方程完成： 矽= d i v w( 2 9 ) 其中w 表示修改后的梯度场，表示拉普拉斯算子，为重建的坐标分量值。对 于二维网格，需要依次对暑y 坐标分量分别求解泊松方程。 2 4 泊松方程及边界条件 2 4 1 泊松方程 泊松方程是数学中一类二阶椭圆偏微分方程，广泛应于静电学和理论物理 中。它的基本形式为： a f = - p( 2 1 0 ) 其中a 表示拉普拉斯算子，和p 是离散网格上的实数和复数值的方程。如果 p * 0 ，则泊松方程将退化为拉普拉斯方程。 一1 5 一 浙江大学硕士学位论文第2 章微分喇格处理原理 2 4 2d i r i c h l e t 边界条件 网格操纵中常用的泊松方程边界条件为d i r i c h l e t 边界条件，它直接给定泊松 方程在边界区域上的函数值，一般形式如下： ，( _ ) = f ( v ，) ，一a q ( 2 1 1 ) 其中厂( ) 表示已知的函数值，a q 表示边界。 这类边界条件，可以分为硬约束( h a r dc o n s t r a i n t s ) 和软约束( s o f tc o n s t r a i n t s ) 两种。前者将方程组中对应的变量用指定的函数值替换，而不将其作为未知量进 行求解；后者仍将指定的函数值作为未知量参加方程组求解，最终由最小二乘法 给出方程组的解，因此软约束变量最终解未必等于指定的函数值。 实际应用中，软约束边界的方法经常使用大数法，即在方程组中约束点的对 应项中增加一个系数，同时在方程组右侧常量中增加对应的系数。当系数趋向于 无穷时，可以视为硬约束。因此，大数法提供了从无约束到硬约束的自然过渡。 图2 4 泊松方程边界条件示意图。，v ，是约束顶点，函数值已知。 图2 4 是一个简单的三角网格模型，对其建立几何无关的拉普拉斯算子【3 6 】， 使用硬约束条件，则方程组为： 一1 6 浙江大学硕上学位论文第2 章微分网格处理原理 爿m = 3一ll 3 1 一l l一16一l一1 一l一14一l 一114 13 11 1 1 3 ( 2 1 2 ) 其矩阵的对应向量为( 心，屹，屹，v ，) 。可见对于约束点v l ，v ，已从矩阵中去 除，其值直接由约束值代替。若使用软约束，则方程组为： 一埘= 3 + 口一lll l3 + 口 一l l 一13 + 口一l l一116 + 口一l ll4 + 口 一l一1 1 一l 一1 1 7 一 一l 一1 4 + 口 一l 一1 1 11 1 一l 5 + 口一l l 一13 + 瑾一l 一1一l3 + 口 ( 2 1 3 ) 浙江大学硕士学位论文第3 章基于形状上下文的图示可视化算法 第3 章基于形状上下文的图示可视化算法 我们将图像变形技术应用于二维可视化图像和已有的二维图例。与文献 2 3 1 的方法类似，我们对图像的不同区域建立三角网格，并在此基础上进行微分网格 变形。 在本章中，3 1 节简单介绍基于泊松的微分网格操纵的定义和方法。相对已 有的二维微分网格变形方法，本文方法主要有两个改进。第一，方法将力学属性 集成到网格中，因此变形时可以获得更加真实的效果。3 2 节将对这种增加力学 属性的改进泊松网格编辑方法加以介绍。第二，方法引入了形状上下文的概念来 描述图例对象中固有的形状特征，因此在变形中可以较好地保持特征。为了保持 形状上下文，我们必须在方程中加入额外的约束，具体内容将在3 3 节中介绍。 本文方法的流程如图3 1 所示。 输入图例生成网格 ” 图例变形 i 图像或图片 ； 构造区域轮廓”指定感兴趣区域 一“三i 乇 i 交互式操纵l 构造网格 i 手绘图例 ； “； j ，麓8 镕；“m 。 l体图例 l 。 i 形状转移 指定刚度信息 图3 1 本文方法的三个步骤，其中虚线框表示可选项。 3 1 基于泊松的微分网格操纵 根据第2 章介绍，如果对项点_ 坐标的两个维度分别设置函数z ，则s 可以 被视为两个离散标量场( s ，s ，) 组成的向量。对其分别求离散梯度算予 s ”( m = x ，力，可以得到： v s ”( v ) = v v 谚( v ) ( m = x ，) ，) ( 3 1 ) 一1 8 浙江大学硕士学位论文 第3 章基于形状t 下文的图示可视化算法 每一个v s ”都是一个分段常数向量场，因此可以将其视为解泊松方程中的导 引向量场( g u i d a n c ev e c t o rf i e l d ) w ： a f = d i v w , f i 规= 厂i 施 ( 3 2 ) 其中，是待计算标量场，厂提供了在茵2 边界上的条件。对导引场w 的操纵正 是基于泊松的梯度场操纵方法的核，1 l , 1 4 4 。 我们将导引场w 定义为v s ”沏= x ，力。为了实现对网格的操纵，用户首先 需要指定一个顶点集合以构造边界信息a q 和厂ia q 。接下来，用户选择一些控 制点并修改它们的坐标，由此可以得到修改后的导引场w 。通过公式3 2 ，我们 可以重建出基于w 的新网格。这个过程可以视为一个求解最小二乘法的能量最 小化的过程： m i n 4l l v s 4 一w 0 2 ( 所= - x ，力( 3 3 ) s“t 3 2 属性相关的泊松方程 以医学图例为例，人体各个部分的组织硬度不同，如骨骼比脂肪部位硬度大， 变形程度也有很大的区别。对于这种图例，如果不考虑各个区域的属性，其变形 结果往往不自然。为了解决这种问题，我们采用一种对网格不同区域指定合适的 属性值并用这些属性值驱动网格变形的方法。 与变形相关的常用物理属性有刚度( r i g i d i t y ) 和弹性( e l a s t i c i t y ) 两种，本文选 择刚度属性作为变形的约束。在三角化网格中，各个三角形的剐度属性可以被视 为分段常数标量场。考虑到材质的各向异性，我们为每一个三角形r 设定两个刚 度值砰( m = x ，y ) ，分别代表丁在x , y 两个坐标方向上的刚度。 根据以上定义，公式3 1 中的分段线性基函数v 谚( ) 可以改写为鲜v 谚( ) 。 直观上看，系数硝沏= x ，y ) 对x , y 坐标方向上的离散梯度向量进行缩放，因此 一1 9 一 浙江大学硕士学位论文 第3 章基于形状上下文的图示可视化算法 可以表示为二维变换矩阵 苫昙 。如果将三角形r 上的变形意图视为仿射变 化，那么k ；c m = x ，y ) 恰好定义在工和y 轴上丁对变形意图的响应系数。 由此，我们定义带有刚度属性的离散散度算子机w ： 帆以v j ) = ，。景，) 鲜一r v 谚i ，w ( 朋= 工，y )( 3 4 ) 同理，新的离散拉普拉斯算子定义为： k ( v j ) = ；，吉( ( ) 2c o t e + ( 七暑) 2c o t c ，) ( f , 一) ( 3 5 ) ，e 肌n ) 二 其中，k l m 和喝分别是共享边( h ，v ，) 的两个三角形的刚度值a 综合上述公式，属性相关的泊松方程可以定义为： k f ( v ，) = d v 矿- w , f l a q = f l a q ( 3 6 ) 在应用过程中，用户需要手工为不同区域指定不同的刚度值，其值与区域的 属性特点相关，一般可取值域为【1 0 ，1 0 o 】。最小值1 0 表示柔软的部位，这类区 域产生弹性形变，在变形过程中特征很难保持，例如人体中的脂肪；最大值1 0 0 表示坚硬的部分，例如骨骼等。对于各向异性的材质，则需要将x , y 坐标上的刚 度设置为不同值。如图3 2 所示，将图例中标记五角星的骨骼设置为不同的刚度 值，在相同的操作下，其变形结果有很大的区别。 一2 0 一 浙江大学硕士学位论文 第3 章基于形状上下文的图示可视化算法 ( a )( b )( c )( d ) 图3 2 在不同刚度设置下的变形结果。变形的骨骼由红色五角星标示，另外两块骨骼的刚度 值均设置为巧= 1 0 0 , k r = 1 0 0a ( a ) 输入的图例；( b ) 各向同性，弹性：睇= 1 0 ，蟛= 1 0 ； ( c ) 各向异性：群= 1 0 o ，吖= 1 0 ；( d ) 各向同性，刚性：簖= 1 0 o ，群= 1 0 0 3 3 保持形状上下文的变形 在变形过程中，有时候需要保留某些全局的形状特征，如成年人的面部有1 6 个特征点【5 】，这些点的相对关系并不随年龄的增长而改变，因此这些特征点构 成的形状可以作为面孔识别的重要依据。 尽管在图形学和计算机视觉领域中已经有很多不同的方法来对形状进行描 述，然而适用于图像变形的却不多。文献【2 】提出一种形状描述符，它描述了形 状上所有点相对于任意一点的分布。该算法给出的是统计属