（计算机系统结构专业论文）图像变形算法的研究及改进.pdf

大连理工大学硕士学位论文 摘要 图像变形算法很久前就被广泛关注，并且有过很多相关研究。图像变形技术在电影 动画制作、图像编辑、用户接口、动作表情控制等多个领域有着广泛的应用。本论文结 合项目需求为完成图像变形，将主要围绕较新的两种变形算法：基于移动最小二乘的图 像变形和基于非线性最小二乘规划的2 d 图像变形展开讨论研究。 首先，论文中讨论了最小移动二乘算法的图像变形m l s ( m o v i n gl e a s ts q u a r e s ) 。这 种方法利用线性函数的变换类包括仿射，相似和刚性变换。这种实在的变换将会给用户 一种操纵真实世界物体的感觉。系统的设计也允许用户通过一系列点或是线段来指明变 形，然后通过函数变换将有用的控制曲线和轮廓再现在图像上。用点和线段控制的变形 方法与点控制的形式类似，其中也是刚性变换的效果最好。 本论文还进一步介绍了另一种方法即基于非线性最小二乘规划的2 d 图像变形。这 个新颖的算法目的是要保持两个图形的局部性质：边缘曲线的拉普拉斯坐标以及图形内 部的局部面积，除了要保留局部图形性质，这篇论文还引入一个框架，用来保留图形的 整体面积。 最后，本论文尝试采用三角形网格作为初始条件，在变形过程中只保持边的长度不 变，就足以保持图形的局部特性、全局面积、外轮廓曲线与内部点位置关系。通过减少 约束这样的改进使得问题成为简化的非线性最小二乘问题。充分的理论分析与大量实验 对比证明，这样的改动不仅保证了变形效果，也提高了运算速度。、 关键词：图像变形；变换函数；最小移动二乘；面积保持；非线性最小二乘规划 图像变形算法的研究及改进 r e s e a r c ha n di m p r o v e m e n to nt h ei m a g ed e f o r m a t i o n a b s t r a c t i m a g ed e f o r m a t i e l la l g o r i t h mh a sb e e nf o c u s e do na n dr e s e a r c h e df o rm a n yy e a r s i ti sa u s e f u lt o o lv a r i o u sa p p l i c a t i o ns u c ha sf i l ma n dc a l t o o nm a k a i , i m a g ee d i t i n g , e n r i c h i n g g r a p h i c a lu s e fi n t e r f a c e sa n dc o n t r o l l i n go ff a c eo ra c t i o n t 1 l i sp a p e rc o n n e c t i n g 、v i t ht h e r e q u i r e m e n to fc o m p a n yd i s c u s s e st h el a t e s tt w oi m a g ed e f o r m a t i o na l g o r i t h m s ：i m a g e d e f o r m a t i o nu s i n gm o v i n gl e a s ts q u a r e sa n d2 ds h a p ed e f o r m a t i o nu s i n gn o n - l i n e a rl e a s t s q u a r e so p t i m i z a t i o n f i r s t , t h ep a p e rw i l ld i s c u s st h em l sa l g o r i t h mw h i c hu s e sl m e gf u n c t i o nt om a pp o i n t s i nt h eu n d e f o r m e di m a g et ot h ed e f o r m e di m a g e t h e s ef u n c t i o n sc o n t a i na f f i n c , s i m i l a r i t y a n dr i g i dt r a n s f o r m a t i o n s t h e s ed e f o r m a t i o n sa r er e a la n dg i v et h eu s e rt h ei m p r e s s i o no f m a n i p u l a t i o nr e a l - w o r l do b j e c t s 1 1 1 ed e s i g no fs y s t e ma l s oa l l o w st h eu s e rt os p e c i f yt h e d e f o r m a t i o n su s i n ge i t h e rs e t so fp o i n t so rl i n es e g m e n t s , t h el a t e ru s e f u lf o rc o n t r o l l i n g o n v e sa n dp r o f i l e sp r e s e n ti nt h ei m a g e t h ep a p e rw i l li n t r o d u c et h ed e f o r m a t i o nc o n t r o l l i n g b yp o i n t sa n dl i n e s r i g i dt r a i l s f o r m a t i o nh a st h eb e s tr e s u l ti na l lt h et h r e ed e f o r m a t i o i l s t h e n , t h ep a p e rw i l ld oa d v a n c e dr e s e a r c ho na n o t h e rm e t h o do fd e f o r m a t i o nn o n l i n e a r l e a s ts q u a r e so p t i m i z a t i o n t h en o v e la l g o r i t h ma i m st op r e s e r v et w og c o m e m c p r o p e r t i e so f 2 ds h a p e s ：t h el a p l a c i a nc o o r d i n a t e so ft h eb o u n d a r yc u r v eo ft h es h a p ea n dl o c a la r e a s i n s i d et h es h a p e b e s i d e sp r e s e r v i n gl o c a ls h a p e p r o p e r t i e s ，t h i sp a p e ra l s oi n t r o d u c eas c h e m e t op r e s e r v et h eg l o b a la r e ao f t h es h a p ew h i c hi su s e f u lf o rd e f o r m i n gi n c o m p r e s s i b l eo b j e c t s a tl a s t , t h ep a p e rb a s e so nt r i a n g l em e s h , p r e s e r v i n gt h el e n g t ho fe d g e sd u r i n g d e f o r m i n gi se n o u g h t op r e s e r v et h el o c a lp r o p e r t i e s ，g i o b a la r e a , b o u n d a r yc u r v ea n dr e l a t i v e p o i n ti o c a t i o no ft h es h a p ei nt h ep r o c e s so fd e f o r m a t i o n t h e r e f o r e , s e m ei m p r o v e m e n t st o t h ed e f o r m a t i o na l g o r i t h mb a s e do nn o n - l i n e a rl e a s ts q u a r e so p t i m i z a t i o n sa r ec a r r i e do u t , a n d i n e f f e c t i v ec o n s t r a i n t sa r ed i s c a r d e d , s ot h ep r o b l e mi s s i m p l i f i e d s u 伍c i e n tt h e o r e t i c a l a n a l y s i sa n de x p e r i m e n t sp r o v e dt h ea d v a n t a g eo ft h ei m p r o v e da l g o r i t h mt h a tf i r s ti ti sm o l - e s t a b l e ，s e c o n d l yt h ec a l c u l a t i n gl o a di sr e d u c e da n dt h ec o m p u t i n gs p e e di sa c c e l e r a t e d k e yw o r d s ：i m a g ed e f o r m a t i o n ；t r a n s f e rf u n c t i o n ；m o v i n gl e a s ts q u a r e s ；a r e ap r e s e r v i n g ； n o n l i n c a rl e a s ts q u a r e so p t i m i z a t i o n 独创性说明 作者郑重声明：本硕士学位论文是我个人在导师指导下进行的研究工 作及取得研究成果。尽我所知，除了文中特别加以标注和致谢的地方外， 论文中不包含其他人已经发表或撰写的研究成果，也不包含为获得大连理 工大学或者其他单位的学位或证书所使用过的材料与我一同工作的同志 对本研究所做的贡献均已在论文中做了明确的说明并表示了谢意。 作者签名：三! bj 交日期：筮2 盘，f ： 大连理工大学硕士研究生学位论文 大连理工大学学位论文版权使用授权书 本学位论文作者及指导教师完全了解“大连理工大学硕士、博士学位 论文版权使用规定”，同意大连理工大学保留并向国家有关部门或机构送 交学位论文的复印件和电子版，允许论文被查阅和借阅。本人授权大连理 工大学可以将本学位论文的全部或部分内容编入有关数据库进行检索，也 可采用影印、缩印或扫描等复制手段保存和汇编学位论文。 作者签名 导师签名 址i 壹 起垒 垫! 星年l 月n 大连理工大学硕士学位论文 1绪论 1 1 研究背景及研究目的 1 1 1 图像变形问题的提出 作为一种计算机视觉方面的应用，图像变形问题近年来倍受关注，它的价值正在研 究与实践中不断完善和发展。我们应用图像变形技术可以生成从一幅数字图像到另一幅 数字图像的平滑过度，或者根据在多幅图像之间进行的变换，都可以产生惊人的视觉效 果。图像变形技术应用面很广，在医学影像方面【l 】，图像变形更是一种重要应用，对于 一些手术需要对很多模型进行模拟，以及变形的假设，这种技术对于医学研究有很大的 帮助。它也可以用在影视业中的虚拟角色，角色，娱乐，人脸记忆合成，虚拟现实等， 电影中常见的应用如从某一个脸到另一个脸的变化，或者对于一些给定的图像让它产生 喜，怒，哀，乐等复杂的表情变化。事实上，电影特技效果的制作在大量应用了图像变 换技术基础上，也取得了巨大的成功。这些应用可以使得图像更有生气，使效果更加逼 真。同时我们也可以通过控制物体的形状变化，或者人物动作的变化的连续操作来实现 动画效果。 为了实现控制和动画，最好设计一个计算模型。例如对人脸建模，其基本思想是根 据人类面部特征的位置分布基本上是一样的，因而特定人脸的模型可以通过对一个原始 模型的特征和其他一些网格点的位置进行自动或交互式的调整而得到的。 目前比较流行的是多边形表示人脸的3 d 模型【2 】。第一个物体模型的多边形顶点和 第二个物体模型对应的多边形顶点问颜色和位置属性进行插值运算。这种方法的缺陷是 对物体的几何表示有一定的约束，例如每个模型都要求同样数目的多边形，而且当两物 体的拓扑结构有差异时变形就会产生新的问题，但如果模型的拓扑结构一致，这种直接 用对应顶点插值的技术还是很有效的，可以实现从一张人脸到另一张人脸的变形、多个 简单表情的融合生成复杂的表情以及两张脸的合成等。虽然用3 d 建模的方法可以实现 合成新的图像，但建模过程的复杂性使得这种方法有很大的局限性。因此直接应用2 d 的数字图像来合成新的图像就成为了一种更好的选择。它的优势在于不依赖于场景的具 体复杂度，它只是根据图像的大小来确定算法的规模。 2 d 图像变形技术可以用来产生基于图像的绘制效果。它并不对场景进行模型的分 析，只是依赖一些先验的知识对图像进行处理和生成。因此这种技术更加贴近人们的习 惯，它的实用范围相对而言要广一些。数字图像的变形是指利用图像上有限的特征，并 通过对这些特征的移动来使整幅图像产生几何变化，以达到预期变化效果的一种技术。 图像变形算法的研究及改进 2 d 图像变形是一种有用的工具在各种应用中比如在实时操作以及拓展图形用户接 口。一个好的图形变形系统目的是要通过简单的操作产生可视的令人满意的效果并且给 用户提供交互式的反馈。很多技术被提出为了达到这两个目标的平衡。于是人们专注于 研究图像变形算法期望到达完美的效果，并且获得实时交互的反馈。 1 1 2 图像变形技术的发展状况以及相关技术 以前在2 d 图像变形上的工作主要集中研究不同的控制。主要的方法有基于点或者 线段特征的图像变形技术，但这种技术所设定的线段往往与场景有关，它的开销在某种 程度上仍旧依赖于场景的复杂度。也有人提出了一种基于局部三角形对应的图像变形方 法，将信息完全局部化，真正做到了与场景的复杂度无关，为以后的图像变形系统的实 时化打下了基础。 最著名的变形方法是基于网格的技术即自由形式的变形。自由形式变形( f f d ) 【3 ，5 】 以及基于框架的技术【6 】如今被广泛的应用在商业软件的一些方法。它们运行的速度快。 在f f d 中，一个图形被嵌入一个网格中，通过移动网格的控制点来控制变形。f f d 简单 容易使用，但是不能通过正常的方式来控制图形的性质。比如，具有同样轮廓的动画。 基于框架的变形提供一种直觉的方法来控制一些动画图形的形变。基于框架的算法定义 点的位置作为那些映射到移动坐标结构上的点的加权线性结合，对应的结构通常可以用 手动的具体描述。近似的权值选择是一个比较痛苦的过程。而且，在f f d 中控制许多控 制点是非常费力的事。虽然基于身体的仿真可以达到满意的效果但是非常低的收敛。同 时，这种代表性的方法对应到控制点的线需要矫正，对于用户来说也比较麻烦。 b e i e r 丰1 n e e l y 7 1 等在基于网格技术的基础上提出了一种方法允许用户用一系列线来 描述变形。这个方法基于s h e p a 讪的插值鸭建立平滑变形。但是，作者注意到他们的方 法会产生复杂的扭曲，在变形中会有不必要的折叠。k o b a e 9 】不久后提出了表面变形的技 术。有一些变形需要不同的变形转换。一个例外是基于薄片的方法试图缩小变形的量。 b o o k s t e i n 1 0 提出一种用最简单的变形控制点的变形算法，用基于光线的函数。图1 i l ( 2 ) 给出用这种方法的例子。这种变形和仿射方法非常相似。这两种情况，测试图片受到非 一致性缩放和剪切，在很多应用上这是不需要的。 近来，i g a r a s h i 1 1 1 的文章提出了一个基于点的图像变形技术，主要针对卡通图像的 变换，使变换尽可能刚性。图1 1 是i g a r a s h i 的方法得到的变形，其中左图为原测试图， 中间为用t h i n - p l a t es p l i n e s 函数得到的变形，有点失真，右图为i g a r a s h i 方法产生的变 形，这样的变形缺少平滑性。图1 2 是m l s 方法显得平滑。这个交互式系统允许用户通 过操纵一些点来变形一个2 d 图形。这些图形通过一些三角网格展现并且用户移动网格 大连理工大学硕士学位论文 里的一些向量作为约束控制。系统可以计算出其余自由向量的位置通过最小化每个三角 形的误差。为使问题成为线性的，他们提供了两步的闭式算法：第一步计算旋转第二步 计算比例。这样就把问题分成两个最小平方的最小化问题，可以快速稳定的解决。同时， 这些变形有的性质可以大量的减少局部缩放和剪切。而且作者表示该算法仅仅是应用上 为了到达交互式操作的近似，并且由于它的线性性质可能在某些情况下引起不正常的效 果。 ( 1 ) 原测试图( 2 ) t h i n - p l a t es p l i n e s 函数变形( 3 ) i g a r a s h i 变形 图1 1 变形对比 f i g 1 1c o m p a r i n gi m a g ed e f o r m a t i o n s 为了达到身体上的可能变形，可以应用基于身体的仿真 1 2 , 1 3 , 1 4 j 。在这些方法中，最 流行的是m a s s s p r i n g 模型【l3 1 。但是它收敛的太慢，并且需要仔细地调整不同的参数。 有限元的方法【1 2 】提供了更精确的仿真在针对一些冗长的计算。因此，它们都不适用于交 互式的变形应用。这个a r t d c f o 系纠1 4 】可以交互式进行，但是只限于小部分变形。基于 梯度的 1 5 , 1 6 , 1 7 , 1 i , l g , 1 9 1 映射变形技术也是在一种能量最小化问题。这个能量函数包括一个保 持细节的约束项，以及一个位置约束项。其中保持细节的约束是一个非线性的因为其包 含了局部细节差异和独立位置上的局部变形。对于计算的效率，存在一种技术通过用不 同近似包括转换【1 1 l 的局部线性化把非线性约束转换为线性约束，操作【1 8 1 6 ”】的转换插值 以及旋转和比例计算【l l 】的分解。应用这种最d x - - 乘机制也不能确定到达满意的结果。 如今，比较新的图像变形技术都是以i g a r a s h i 提出的算法为基础，一种基于线性最 小移动二乘m o v i n gl e a s ts q u a r e s 的图像变形算澍2 0 】。构造这种变形来减少大量的局部缩 放和剪切，我们约束转换的类利用最小移动二乘在相似和刚性变换上。通过应用m l s ， 我们避免了对输入图像的三角化，并且可以产生全局平滑的变形。然后，我们得到相似 和刚性变换的封闭形式的规则。这些规则很容易执行并且提供实时变形。这些主要来自 一3 一 图像变形算法的研究及改进 相似变换和刚性变换之间的关系可以缩小最t j 、- - 乘的问题。与i g a r a s h i 的方法相比，我 们的方法不需要一般的线性解决方法。作为我们的基于点的方法的延伸，我们扩展m l s 变形从一系列点到一系列线段，并且再次提供了变形封闭形式的表达。 图1 2 利用m l s 方法的变形 f i g 1 2 d e f o r m a t i o nw i t hm l s 另一种方法即非线性最小二乘规划算法n o n l i n e a rl e a s ts q u a r e so p t i m i z a t i o n 2 1 1 。该算 法输入是一个2 d 图形，边缘是封闭多边形。这些图形可以通过图形向量或者位图形式 表示。对于位图形式，我们可以手动移除背景，并且可以应用根据m a r c h i n gs q u a r e s 算 法的自动轮廓提取边缘多边形。我们的算法在图形的内部区域内自动插入一系列的点并 且通过连接图形的边缘轮廓和内部点这些向量来产生曲线图。用户可以拖动这些点来控 制形变。这个算法的目的是保持两个局部性质：外轮廓的l a p l a c i a n 坐标和图形内部的 局部面积。l a p l a c i a n 坐标表现了图形边缘的局部细节，并且广泛的应用在3 d 网格变形 方法中。而保持l a p l a c i a n 坐标通常可以产生好的形变效果对于3 d 网格，但是对于2 d 变形要想产生视觉满意的效果仅仅这样是不够的( 如图1 4 ) 。因此，我们还要保持图形 内部的局部面积特性。为了达到这个目的，我们建立了一些曲线并且为这些连线引入两 个新的局部性质：内部点与邻居点的位置关系，以及每条边的长度。为了控制形变，用 户要输入一系列点变形后的位置。所有输入的点的变形位置可以通过最小化一个包含 l a p l a c i 赳r i 坐标的保持，内部点位置关系的保持，边缘长度的保持以及位置约束四个部分 的能量函数。 上述两种方法是最新的有关图像变形的算法，但是在不同情况时候，效果也不一定 能到达完美。 4 一 大连理工大学硕士学位论文 1 2 研究图像目的以及关键问题 1 2 1 研究目的 因为图像变形技术的广泛应用，同时我们与软件公司合作的项目需求是实现动画变 形的效果，更进一步来扩充现有图像编辑软件的功能，填加变形的应用。于是展开对图 像变形技术的研究，为了实现更好的变形效果，从基础算法开始研究，直到较新的算法 并且尽量改进，使的改进算法的变形效果能更好的实现项目需求。 1 2 2 图像变形中的关键问题 在图像变形技术发展之前，生成从一幅数字图像到另一幅数字图像的平滑过渡通常 通过一个交叉溶解( c r o s s - d i s s o l v e ) 的过程实现f 2 】。中间图像某一点的灰度值等于两原图 像上相同坐标点灰度值的平均。由于非对齐区域的重影效果，这种简单方法生成图像的 质量很差。而图像变形技术应用2 d 几何变换来保持图像特征点的拓扑关系不变。两幅 图像的变形技术首先建立两图像之间特征点的对应关系，图像的特征可以是网格、直线、 曲线或点。 特征对应是一个很繁琐的过程，从现有的方法来看，对于相差比较大的图像来讲( 指 颜色和形状) 一般都是由人工选定几个特征点作为对应的特征点。也可以借鉴已有的关 键点匹配算法，由于三维空间物体的边缘或角点等在分别向两个摄像机作投影时，会产 生二维图像中灰度剧烈变化的点，这些点由于在二维图像中位置比较特殊，周围灰度变 化也十分剧烈，因此比较容易找到对应的点，由于这些点能够被匹配得比较准确，因此 称之为关键点，寻找关键点之间的对应也就相应的称为关键点匹配。与原有的方法相比， 这是一种半自动化的方法，有时需要人工剔出错误的匹配点。所以本文中的匹配点选取 会采用手动的情况，认为规定对应点的位置，从而控制形变，这样做也是为了能够按照 用户的意愿进行图像变形。 在图像变形中，为了实现变形我们提出了很多操作来控制变形。这些控制可以通过 点的形式也可以通过线段，甚至是多边形网格，这些都是图像本身的特征，用户可以修 改位置以及这些操作的方向，图像应该在直觉发生变形。我们可以用点或者线段作为特 征，通过用户输入作为变形为的目标状态，从而控制形变效果。 在特征对应的基础上就可以计算两图像间点的对应关系了，这个对应关系称为变换 函数求变换函数是图像变形技术中的一个关键问题，即找到源图像和目标图像之间的 映射关系，一旦求得两图像间的变换函数就可以进行对应点的插值运算了。变换函数我 们根据图像研究的经验分析，可以使用一些已有的函数。图像变形中另一个重要的问题 是变换控制，如果从一幅图像变换到另一幅图像的过程中，对应点的变换速度在整幅图 图像变形算法的研究及改进 像中不一致，就可以产生更多有意义的动画效果。并且，在不用参数控制的情况，可以 得到不同的效果，也同样可以将参数控制应用在图像变形上，进而丰富动画效果。 1 3 本文主要研究内容 图像变形技术在图形图像应用领域一直是研究的热点问题，它涉及计算机图形学， 图像处理，计算机视觉，计算数学等多个学科等。通过对基础算法的了解，我们着手研 究最新算法基于线性最小移动二乘m o v i n g l e a s ts q u a r e s ( m l s ) 的图像变形算法和非线性 最小二乘规划算法n o n l i n e a rl e a s ts q u a r e so p t i m i z a t i o n 。 m l s 算法中，我们重点讨论通过点控制形变的情形，形变过程依赖变换函数，这 将是我们讨论的重点，根据选取不同变换函数，产生的不同变形结果，我们讨论得到最 合适的变形。通过应用m l s ，我们避免了对输入图像的三角化，并且可以产生全局平 滑的变形。 然后，进一步讨论基于非线性最小二乘规划算法，这种新颖的2 d 变形算法与m l s 算法不同，它在变形的过程中，使得下面几个主要属性保持不变：图形轮廓曲线的 l a p l a c i a n 坐标、内部点位置关系、内部边的长度以及图形的总面积。这些约束条件可以 被封装成为一个带约束的非线性最小二乘问题，进而化成带约束的非线性二次规划问 题。这个算法得到了非常理想的视觉效果，它还保持了图形的总面积，使得带有弹性的 物体的形变更具有真实感。但是它保持内部点位置关系和内部边的长度不变的两个约束 没有足够的强度来保持局部的特性，其网格化方法使得内部图的结构不够稳定，导致在 某些特殊情况下，会产生不理想的效果。 本文对上述算法给出了详细的分析，并对其进行了改进。改进的方向主要为了使问 题简化成无约束的非线性最小二乘问题。充分的理论分析与大量实验证明这样的改动不 仅保证了变形效果，也进一步提高了运算速度。图1 1 为改进的图像变形算法的一个实 例。主要为了简化约束，并且保证变形效果，同时也要进一步提高运算速度。 1 4 本文的组织结构 第一章为绪论，说明研究的背景和研究目的，主要是引出本文将要讨论的问题，概 括介绍主要的研究内容，并对以后各章的后续工作做了简要的说明。 第二章简要介绍了一种比较新的应用最小移动二乘算法的图像变形技术。主要介绍 了该算法的基本原理，在基础算法上做了哪些改进，实现了比较理想的变形效果。此方 法通过尝试不同的变形函数达到不同效果，并且对比这些结果，选取最合适的变换函数 确定变形。 一6 一 大连理工大学硕士学位论文 第三章主要对基于非线性最小二乘规划的图像变形算法进行了详细的分析。首先将 图像网格化，主要采用四方形网格作为初始条件。然后介绍了用来控制形变的四种约束： 图形的局部特性、全局面积、外轮廓曲线与内部点位置关系，保持这四种约束就可以保 持变形的效果，同时给出调节四个约束参数达到的不同效果。 第四章进一步根据上述算法，证明了不同的网格结构对最终的变形结果具有重大的 影响。采用三角形网格作为初始条件，在变形过程中只保持边的长度不变，就足以保持 图形的局部特性、全局面积、外轮廓曲线与内部点位置关系。因此本文对基于非线性最 4 , - - 乘规划的图像变形算法进行改进，去掉了多余约束，使得问题规模得以简化。充分 的理论分析与大量实验证明了改进的算法具有多个优点。除此之外，该算法还具有面部 表情控制、图形面积调节等能力。 接下来，为了把最新变形算法和我们改进的算法做对比，给出了大量实验用例，比 较几种算法的不同效果，更加证明了改进算法在效果和速度上的成就。 第五章是对本论文的工作总结和展望。总结了论文的主要研究内容，以及改进部分 的详细说明，重要的是很好的完成了项目需求，并给出交互变形效果。同时提出未来继 续的研究方向，以及算法的可能改进。 图像变形算法的研究及改进 2 基于线性最, j 、- - 乘m l s 的图像变形 图像变形技术的广泛应用已经被人们所关注，对变形技术的研究也日新月益。以前 在图像变形上的工作主要集中研究不同的控制。比如控制点，线段，或者网格等。近期 i g a r a s h i 的文章突出了一个基于点的图像变形技术，主要针对卡通图像的变换，使变换 尽可能刚性。这些变形有的性质可以大量的减少局部缩放和剪切的效果。 为了产生刚性变换，即更稳定的变换，i g a r a s h i 三角化输入图片【l l 】并且解一个线性 方程，其大小等于三角化中内点的数量。相反的，一种更新的基于最小移动二乘算法的 变形方法被提出，在每个网格上解一个很小的线性方程。因为解的是更小的线性系统， 所以可以产生更快的变形。下面将介绍该种算法。 2 1 概括介绍m l s 图像变形有很多应用，比如在使图像有生气，变体以及医学影像等方面。为了实现 变形我们提出了很多操作来控制变形。这些控制可以通过点的形式也可以通过线，甚至 是多边形网格。m l s 算法想通过用户修改变形位置以及这些操作的方向，使图像在直 觉上产生变形效果。 我们首先观察变形函数厂，该函数用来表示将点从非变形图像映射到变形图像。应 用这个变形函数可以对每个点来构造变形后图像。现在考虑把图像上一些控制点p 由用 户移动到一个新的位置g 。厂若是变形函数它必须满足以下性质： ( 1 ) 插值：控制点p 可以直接映射到q 上。 ( 2 ) 平滑：厂可以产生平滑变形。 ( 3 ) 一致性：如果变形控制p 和g 一样，那么厂就是一个一致性函数。 这些性质和那些应用在离散函数上的插值很相似。开始的两个性质简单陈述函数厂 可以用于插值离散函数并且平滑。这最后一个性质有时会涉及到线性精确近似。它说明 了从线性函数采样得到数据，然后插值产生线性函数。假定这些相似性，毫无疑问可以 借助离散数据插值的方法产生很多变形方法。当，取不同的变换函数时，会有不同的变 换效果，如图2 1 为利用最小移动二乘的图像变形。原始图像用蓝色控制点如图2 1 ( 1 ) ， 最小移动二乘变形应用仿射变换如图2 1 ( 2 ) ，相似变换如图2 1 ( 3 ) ，以及刚性变换如图 2 1 ( 4 ) 。 一8 一 大连理工大学硕士学位论文 2 1 1 n l s 算法的引出 图像变形上的主要工作集中在研究不同的控制方式。但是如果大多数控制不当，可 能会影响效果或者变形的运算速度，而且可能给用户带来麻烦。 ( 1 ) 原图( 2 ) 仿射m l s( 3 ) 相似m l s( 4 ) 刚性m l s 图2 1 利用最小移动二乘的图像变形 f i g 2 1 d e f o r m a t i o nw i t hm l s b e i e r 在基于网格技术的基础上提出了一种方法允许用户用一系列线来描述变形。 这个方法基于s h e p a r d 的插值，建立平滑变形。但是，人们注意到他们的方法会产生复 杂的扭曲，在变形中会有不必要的折叠。k o d a 不久后提出了表面变形的技术。有一些 变形需要不同的变形转换。一个例外是基于薄片的方法试图缩小变形的量。b o o k s t e i n 提出一种用最简单的变形控制点的变形算法，用基于t h i n - p l a t es p l i n e s 的函数( 如图 1 1 ( 2 ) ) 。 本章主要依据一个近期i g a r a s h i 的文章突出了一个基于点的图像变形技术，主要针 对卡通图像的变换，使变换尽可能刚性。这些变形有的性质可以大量的减少局部缩放和 剪切。为了产生刚性稳定的变换。i g a r a s h i 三角化输入图片并且解一个线性方程，其大 小等于三角化中高点的数量。而本章的变形方法解一个很小的线性方程。因为我们解的 是更小的线性系统，我们可以产生更快的变形。当然这种算法的贡献不仅仅是速度上的。 图1 1 ( 3 ) 是i g a r a s h i 方法产生的变形，可能有明显的不连续点，如图1 1 。 在本章中提出的这个基于线性最小移动二乘的图像变形算法。构造这种变形来减少 大量的局部缩放和剪切，我们约束转换的类利用最小移动二乘在相似和刚性变换上。通 过应用m l s ，我们避免了对输入图像的三角化，并且可以产生全局平滑的变形，使得 变形效果更理想。 然后，我们得到相似和刚性变换的封闭形式的规则。这些规则很容易执行并且提供 实时变形。这些主要来自相似变换和刚性变换之间的关系可以缩小最小二乘的问题。与 i g a r a s h i 的方法相比，这里的方法不需要一般的线性解决方法。 图像变形算法的研究及改进 作为基于点的方法的延伸，本章扩展m l s 变形从一系列点到一系列线段，并且再 次提供了变形封闭形式的表达。 2 2 移动最小二乘变形 这里我们考虑的是一种基于搜集用户提供的控制变形点的方法。让p 为一系列控制 点，g 是控制点p 变形以后的位置。我们建立一个变形函数，满足上面所说的m l s 算法中变形函数的的三个性质【捌。在图像给定一个点v ，我们为了解得最优的仿射变换 而最小化下面式( 2 1 ) 所示： z w , l t a p j ) - q , 1 2 ( 2 1 ) 这里只和吼是行向量，并且权值w 有这样的形式：w f2 历j 。汗因为权值w f 在 最小平方问题估计点v 处是独立的，我1 f f 3n q 这个为最小移动二乘的最小化。因此，我们 可以每个v 点得到一个不同的转换从l a x ) 。 现在我们定义一下变形函数，为f ( v ) = l a ；) 。观察当v 接近p i ，以及心接近无 穷，并且函数厂插入新的语句( 厂( 只) = 毋) 。并且，如果吼= p i ，那么对于每个工有 l ( z ) = 石，因此，厂是一个一致性变换f ( v ) = ，最后，这个变形函数，具有使各处 平滑的性质( 除了控制点只当口1 ) 。 现在因为t a x ) 是一个仿射变换，而l ) 由两部分组成：一个线性转换矩阵m 和 一个平移转换r 。 l a x ) = x m + r ( 2 2 ) 事实上，我们从最小化问题中可以去掉r 进一步化简方程，方程( 2 1 ) 是包括，的二次方 程式。因为引出每个与l ( 的自由变量有关的最小值为零。所以我们可以根据矩阵肘直 接解出t 。利用r 中的局部有关变量产生了方程的线性系统。解r 得：t = q o p , m ， 这里毋和a 是权值质心。 肛= 哿吼= 哿ww 利用这样的观察我们把r 带回方程( 2 2 ) 然后重新写l ( 力 大连理工大学硕士学位论文 l a x ) = ( 工一p o ) m + 毋 ( 2 3 ) 基于这样的观察，最小移动二乘问题可以重新写作如下 ；i a m 一引2( 2 4 ) 这里廖= p i a 和玩= 吼- q 。 注意最小移动二乘很普遍其中矩阵m 并不一定完全就是仿射变换。事实上，这种 结构允许我们尝试不同的转换矩阵m 。我们更感兴趣的是m 是刚性变换。但是，我们 首先从最简单的情况开始研究就是肘是仿射变换。然后我们构造一种变形利用相似变 换，并且显示出这些解决方法可以用来找到利用刚性变换解决移动最小二乘变形问题的 封闭形式。 2 2 1 仿射变换 找到一种仿射变换来直接利用正态方程最小化方程( 2 4 ) 得到： m = ( ；扫? w 囊i t l 薯w i 套? i i 虽然这样需要方程的转置，但是这个方程就是2 * 2 的矩阵转置的速度会很快。利用这种 封闭形式解决吖，我们可以重新为变形函数z ( v ) 写一个简单的表达式。 f o ( v ) = ( 1 ，一p ) m = ( 手矗7 心磊) 一号_ 见7 q j + q , ( 2 5 ) 应用这个变形函数对每个点建立一个新的变形的图像。 当用户通过操作点g ，p 点是固定的。应为p 在整个变形过程中不能改变，公式( 2 5 ) 中有一些可以预先计算这样就可以达到非常快速的变形。近一步我们可以重新写方程 ( 2 5 ) 如下形式： 六( 力= ；么，毒，+ 毋 ， 这里彳；是一个单纯标量由下式给出 4 ，= ( v p ) ( 军a 7 w a ) _ 1 毒，7 注意，如果给出一个点v ，都可以通过a ；预先计算出一个简单的，有利的总和。表2 1 为文章中的例子提供计时结果，可以表明我们的例子每秒可以进行5 0 0 次的变形。 如图2 1 中( 2 ) 举出仿射移动最小二乘变形算法应用到我们的测试图片上的结果。不 幸的，这种变形在胳膊的延伸和不完整的部分的变形不能得到另人满意的结果。这样的 图像变形算法的研究及改进 结果主要因为仿射变换包含一些变形比如非一致性的比例缩放和剪切。为了消除这些不 必要的变形，我们引入了线性转换l ( x ) 。特别的，我们修改这类变形通过约束从完全 的线性到相似和刚性变换的转换矩阵膨。 表2 1 各种方法的变形时间 t a b 2 1d e f o r m a t i t i m e sf o rt h ev a r i o u sm e t h o d s 2 2 2 相似变换 当仿射变换包括许多诸如非一致性比例缩放和剪切的效果时，许多物体的变形是不 能接受的。相似变换是仿射变换的一个子集，这种变换只包括平移，旋转和一致性缩放。 转换我们的变形技术只采用相似变换，我们约束矩阵m 这样的性质m 7 m = a 2 i 对 于每个标量旯。如果m 为方块阵的形式则为m = ( m ，膨：) 这里的m 。， 以长度为2 的列 向量。约束肘为一个相似变换需要m 7 m = 如7 如= a 2m i r m 2 = 0 。这种约束暗示着 m 2 = m 。1 这里上是一种在2 d 向量上的操作比如( 算，y ) 1 = ( 一y ，工) 。尽管有这样的限制， 这种来自方程( 2 4 ) 的最小化问题仍然是二次方的，而且可以再修改通过找到列向量m 。 最小化表示为： 莩州善- ) m i 一铲| 2 这个二次函数有个唯一的最小值，产生了最优的转换矩阵m 肚去莩( 善弘铲) ( 2 6 ) 池一p i 大连理工大学硕士学位论文 这里的以= z w , b , b ，7 。 与仿射变换相似，用户操作口点产生变形而p 点固定不变。利用这些我们写出变形 函数z ( 用那种尽可能多的预先计算的形式。z ( v ) 写做 z ( v ) = 军磊( 二4 ) + g 以 这里以和4 依赖于只，v 和可以预先计算的4 4 2 w i ( 毫一七v - - 一p , ) 7 ( 2 7 ) 正如所期望的，相似m l s 变形在原图的基础上保留了角度这点优于仿射m l s 。而 近似角度的保留在很多情况都需要，允许局部比例缩放常常会导致不满意的变形结果。 图2 1 中( 3 ) 给出了一个应用相似m l s 来测试图像的例子。结果变形看起来比图2 1 中 ( 2 ) 要现实一些。但是，这种变形缩放的比例使上面胳膊好像被延伸了。为了去除这种 比例缩放，我们考虑用刚性转换来产生变形。 2 2 3 刚性变换 近来，许多工作 1 5 , 1 1 1 表明对于真实的形状，变形必须尽可能严格，并且变形的空间 必须包括统一的缩放比例。传统上变形方面的研究者很困难的直接接近这个问题，这都 要归功于非线性约束膨7 m = 1 。但是，我们注意到这种封闭式的解决问题的方法来自迭 代最近的点集。h o m 证吲2 3 1 最优的刚性变换可以根据特征值和一个包含p l 和吼协方差 向量的特征向量得到。 定理2 1 ：c 为一个矩阵，最小化下面的相似功能函数 。嚆：，手i a m 一甜 如果c 被写做2 r ，这里月是一个旋转矩阵，而且五是一个缩放比例系数，旋转矩阵r 最 小化这个刚性函数 n l i n ；i a m 一磊1 2 m t m = if 这里我们可以给出上述定理的证明过程，证明： 首先，我们扩展上面两个误差函数通过二次方的形式，表示为： m i n ，。肼，w f ( 五2 a a 7 - 2 1 b i r g l i 7 咆磊7 ) ，( 多。a 7 2 多；嘶，7q 。辱。t m l n r t r = ) l 乙i w p l p i 一2 p i m q ；均| q i1 图像变形算法的研究及改进 这些最小化问题非常相似。我们可以通过区别那些在r 中与自由变量口，有关的矩阵 找到最小化这些误差函数的矩阵。 ，w ( - 2 绝署铲瑚 川之a 署扪= o 现在，除非五= 0 ，意味着一个退化的变形。这些二次方程是等价的，因为c = 五r 这个意味着r 利用刚性变换最小化二次方程。这个负的解决办法对应最大值，正的解 决方法对应最小值。 这个定理在任意维数的情况都成立，但是，应用在2 d 情况时很简单。用这个定理 我们可以找到和方程( 1 6 ) 一样的刚性变换除了我们用一个不变量从来解决肘7 , 1 4 r = ， 这里给出所= ( 莩磊a 7 ) 2 + ( 手心磊磊”) 2 不像相似变换z ( v ) ，对于刚性变换函数，( v ) 我们不能预先计算一些信息。但是， 这些变换的处理仍然很有效，另，( v ) = 磊4 。这里的4 在方程( 2 7 ) 中定义，可以预先 计算。向量，( v ) 是向量v 只的旋转和缩放形式。为了计算，( v ) 我们标准化z 通过v p 的长度来衡量，并且通过玑转换 肛v ) 书叩i 揣怕 ( 2 8 ) l 工【v ) i 这种方法因为标准化所以比相似变形慢，但是这些变形如表2 i 中显示还是很快。 图2 1 中( 2 ) 显示了应用刚性变形的测试图像。与其他方法相反，这个变形非常真实并且 看起来感觉好像用户在操纵真实物体。图2 2 和图2 3 给出了一些刚性变形的其他例子。 在这个图上我们利用蒙那丽莎变形后。得到了轮廓瘦些并且微笑起来的蒙那丽莎。在马 的那幅图上，我们伸长了马的腿和脖子构造出一个