（机械设计及理论专业论文）移动最小二乘图像变形方法研究.pdf

大连理工大学硕士学位论文 摘要 图像变形是一种基于变形控制特征，根据一定的变形函数生成平滑、具有真实感的 变形效果的图像处理技术。该技术可以被广泛应用在虚拟现实、计算机动画、医学图像 处理以及影视娱乐等各个领域。本文对基于特征曲线及移动最d - - 乘优化方法的图像变 形技术进行了研究。 研究了基于控制点的移动最小二乘图像变形方法。首先分析了基于控制点的移动最 小二乘图像变形方法的数学模型，根据变形需要设置特征控制点。研究了基于点集的仿 射、相似以及刚性变换的变形函数，基于变形函数通过移动控制点生成变形后的新图像。 并对仿射、相似以及刚性变形效果进行了比较。 在基于点集的图像变形方法的基础上，研究了一种基于控制曲线集的移动最小二乘 图像变形方法。根据源图像中的形状信息或变形需要来设置关键点，生成三次样条特征 曲线，然后移动该特征曲线到新的位置根据变型函数实现图像的变形。推导了基于曲线 集的仿射、相似和刚性变形函数，实现图像的真实感变形。 为了保持图像变形的实时性，在曲线集的图像变形方法基础上研究了一种基于 o p e n g l 纹理映射的加速算法。对源图像进行网格划分，利用变形函数计算出网格点变 形后的坐标，在o p e n g l 中生成变形后的网格点框架；将变形前的二维图像转化为纹理 映射到网格点框架上，从而提高了图像变形速度，达到实时性的变形效果。 基于上述图像变形方法的分析研究，开发了一个图像变形处理系统，实现了基于点、 基于曲线和基于网格点的移动最小二乘图像变形，每种变形方法中包括仿射、相似和刚 性变换三种变形效果。该变形系统利用v i s u a lc + + 的m f c 框架实现了可视化操作界面， 用户使用方便。 关键词：图像变形；变性特征；移动最小二乘法；纹理映射 移动最小二乘图像变形方法研究 s t u d y o ni m a g ed e f o r m a t i o nb a s e do nm o v i n gl e a s ts q u a r e s a b s tr a c t i m a g ed e f o r m a t i o ni sa l li m a g ep r o c e s s i n gt e c h n i q u e ，w h i c hc r e a t e ss m o o t ha n dr e a l i s t i c d e f o r m a t i o nr e s u l t sb a s e do nd e f o r m a t i o nc o n t r o lf e a t u r e sa n dd e f i n i t ed e f o r m a t i o nf u n c t i o n s t k st e c h n i q u ei s w i d e l yu s e d i nv i r t u a lr e a l i t y , c o m p u t e ra n i m a t i o n , m e d i c a li m a g e p r o c e s s i n ga n dm o f i e & t vf i e l d a p o i n t - b a s e di m a g ed e f o r m a t i o nm e t h o du s i n gm o v i n gl e a s ts q u a r e s ( m l s ) i ss t u d i e d f i r s t , p o i n t - b a s e dm l s m a t h e m a t i cm o d e li sa n a l y z e da n dt h ef e a t u r ec o n t r o lp o i n t sa r es e t a c c o r d i n gt od e f o r m a t i o nr e q u i r e m e n t 1 1 1 ep o i n t - b a s e dt r a n s f o r m a t i o nf u n c t i o n sa r es t u d i e d t oc o m p u t ea f f i n e ，s i m i l a r i t ya n dr i g i dd e f o r m a t i o n so fi m a g ea n do b t a i ni m a g ed e f o r m a t i o n r e s u l t sb ym o v i n gc o n t r o lp o i n t s t h e nc o m p a r i s o no fa f f i n e ，s i m i l a r i t ya n dr i g i di m a g e d e f o r m a t i o nr e s u l t si sm a d e b a s e do nt h er e s e a r c ha b o v e ，am l s i m a g ed e f o r m a t i o nm e t h o du s i n gc o n t r o lc u r v e si s s t u d i e d a c c o r d i n gt os h a p ei n f o r m a t i o no rd e f o r m a t i o nr e q u i r e m e n t , k e yp o i n t sa r es e tt o c r e a t ec u b i c s p l i n ec u r v e s t h ec u r v e sa r em o v e dt on e wp o s i t i o n st oc o n t r o lt h ed e f o r m a t i o n o fi m a g e t h e nt h et r a n s f o r m a t i o nf u n c t i o n sb a s e do nc o n t r o lc l l r v e sa l ed e d u c e dt oc o m p m e a f f i n e , s i m i l a r i t ya n dr i g i dd e f o r m a t i o n so fi m a g ea n dr e a l i z er e a l i s t i ci m a g ed e f o r m a t i o n r e s u l t s t ok e e pt h er e a lt i m eo fi m a g ed e f o r m a t i o n , a na c c e l e r a t e da l g o r i t h mo fc u r v e - b a s e d i m a g ed e f o r m a t i o ni si m p l e m e n t e db yo p e n g lt e x t u r em a p p i n g 1 1 1 eo r i g i n a li m a g e i s p a r t i t i o n e db yg n da n dt h ed e f o r m e dc o o r d i n a t e so fe v e r y 鲥dv e r t e xa r ec o m p u t e d t h e n d e f o r m e di m a g ef r a m e w o r ki sc r e a t e di no p e n g l ；2 di m a g eb e f o r ed e f o r m a t i o ni st r a n s l a t e d i n t ot e x t u r ea n dm a p p e dt ot h ed e f o r m e di m a g ef r a m e w o r k ，w h i c ha c c e l e r a t e st i m ec o s ta n d r e a l i z e st h er e a lt i m eo fi m a g ed e f o r m a t i o n as y s t e mo fi m a g ed e f o r m a t i o nh a sb e e ne x p l o i t e db a s e do nt h ea b o v e - m e n t i o n e d m e t h o d s i tc a nr e a l i z em l si m a g ed e f o r m a t i o nb a s e do np o i n t s ，c u l v e sa n dg n dv e r t i c e s e v e r yd e f o r m a t i o nm e t h o dc o n c l u d e sa f f i n e s i m i l a r i t ya n dr i g i dd e f o r m a t i o n so fi m a g e t h e e x p e r i m e n t a lr e s u l t ss h o wt h a tt h es y s t e mh a sv i s u a lo p e r a t i o ni n t e r f a c ea n dm a k e st h e o p e r a t i o nc o n v e n i e n tf o r u s e r s k e yw o r d s ：i m a g ed e f o r m a t i o n ；d e f o r m a t i o nf e a t u r e ；m o v i n gl e a s ts q u a r e s ：t e x t u r e m a p p i n g 大连理工大学学位论文独创性声明 作者郑重声明：所呈交的学位论文，是本人在导师的指导下进行研究 工作所取得的成果。尽我所知，除文中已经注明引用内容和致谢的地方外， 本论文不包含其他个人或集体已经发表的研究成果，也不包含其他已申请 学位或其他用途使用过的成果。与我一同工作的同志对本研究所做的贡献 均已在论文中做了明确的说明并表示了谢意。 若有不实之处，本人愿意承担相关法律责任。 学位论文题目：彗蝴幽锺区盈厶进复嘘z 作者签名： 翻睦日期：五必年。芝月红日 大连理工大学硕士研究生学位论文 大连理工大学学位论文版权使用授权书 本人完全了解学校有关学位论文知识产权的规定，在校攻读学位期间 论文工作的知识产权属于大连理工大学，允许论文被查阅和借阅。学校有 权保留论文并向国家有关部门或机构送交论文的复印件和电子版，可以将 本学位论文的全部或部分内容编入有关数据库进行检索，可以采用影印、 缩印、或扫描等复制手段保存和汇编本学位论文。 学位论文题目：超鹫冱当三鑫区蚴刍逋逾整 e l 期：避年上月丛日 日期： 地容年j 量月上l 日 大连理丁大学硕士学位论文 1绪论 1 1图像变形的研究背景及意义 随着信息技术的发展和不断深入，人们越来越多地利用计算机来获取和处理各种信 息。据统计，在人类从外界获得的信息中有6 0 来自于视觉信息，2 0 来自听觉信息， 其他的2 0 来自味觉、触觉等信息【1 1 。由此可见，视觉信息对于人类来说是最有效和最 重要的，而图像正是人类获取视觉信息的主要途径。与其他途径相比，图像有包含信息 量大、表现形式直观等特点，也正因为如此，关于计算机图形图像的研究越来越受到科 研人员的关注，该领域的发展速度越来越快，应用范围也越来越广。计算机图形学是研 究怎样用计算机表示、生成、处理和显示图形的- - l - j 学科【2 】。2 0 世纪5 0 年代初，美国 麻省理工学院开始从事现代计算机辅助设计与制造技术的开拓性研究，这就是关于计算 机图形学研究的雏形。当时的工作只是为了在绘图仪和阴极射线管( c r t ) 屏幕上输出 图形，而随着计算机硬件和算法的发展，计算机图形学已经成为计算机科学与技术中最 为活跃的学科分支之一，并在众多领域( 如：汽车和飞机的设计与制造、机械产品的计 算机辅助设计和制造、电影特技和动画、军事、医学、工程、艺术、教育和培训等等) 得到广泛的应用。 作为一种计算机视觉方面的应用【3 。5 1 ，图像变形问题近年来备受关注，它的价值正 在研究与实践中不断完善和发展。应用图像变形技术可以生成从一幅数字图像到另一幅 数字图像的平滑过度，或者在多幅图像之间进行的变换，都可以产生惊人的视觉效果。 图像变形技术应用面很广，在医学影像方面【6 】，图像变形更是一种重要应用，对于一些 手术需要对很多模型进行模拟，以及变形的假设，这种技术对于医学研究有很大的帮助。 它也可以用在影视业中的虚拟角色，娱乐，人脸记忆合成，虚拟现实【7 j 等，电影中常见 的应用如从某一个脸到另一个脸的变化，或者对于一些给定的图像让它产生喜，怒，哀， 乐等复杂的表情变化。这些应用可以使得图像更有生气，使效果更加逼真。同时也可以 通过控制物体的形状变化，或者人物动作变化的连续操作来实现动画效果。在教育领域， 变形技术用来作为一种新的形象生动的教学工具。在气象预报中，对气象卫星传送的气 象云图应用变形技术可以生成连续的卫星云图，以便描述云图的运动状态。在地理信息 系统中，变形技术应用于数字地形模型的生成中，把一幅二维遥感图像叠加到一个三维 的地形图上。在刑侦系统中，变形技术用来描述人物脸部特征，构造人脸模型。 图像变形技术可以用来产生基于图像的绘制效果。它并不对场景进行模型的分析， 只是依赖一些先验的知识对图像进行处理和生成。因此这种技术更加贴近人们的习惯， 移动最小二乘图像变形方法研究 它的实用范围相对而言要广一些。数字图像的变形是指利用图像上有限的特征，并通过 对这些特征的移动来使整幅图像产生几何变化，以达到预期变化效果的一种技术。图像 变形的研究成果可以被广泛应用在虚拟现实、计算机动画、医学图像处理以及影视娱乐 等各个领域。总之，随着变形技术和其它各门应用科学的发展，变形技术在这些应用领 域的渗透也会越深越广。因此，对图像变形技术的研究不仅具有重要的理论意义，而且， 具有重要的实际应用价值。 1 2 基于图像变形技术的研究现状 对图像变形方法的研究最早可以追溯到2 0 世纪6 0 年代，生成从一幅数字图像到另 一幅数字图像的平滑过渡通常通过一个交叉溶解( c r o s s d i s s o l v e ) 的过程实现【引。这是图像 变形方法家族中最简单的一种方法，通过线性插值实现一幅图像到另一幅图像的逐渐变 化，其视觉效果乏味，不能令人满意。其实从严格的意义上来说，交叉分解方法还不能 算是一种图像变形方法，通常只能把它看成是一种图像转变，而且，那时候人们没有对 图像变形方法的研究引起足够的重视，这种简单方法生成图像的质量很差。 直到2 0 世纪8 0 年代末，d o u g l a ss m y t h e 在电影w i l l o w 的制作过程中提出了网格 扭曲的变形方法【9 1 ，这种情况才有所改变。在过去的十几年中，图像变形技术的研究取 得了突破性的进展。 对于一般变形，在变形效果上，一般不希望出现变形折叠，也不希望出现变形过程 中起始图像信息的大量丢失现象。如果随着变形的进行，起始图像信息会大量的损失， 则图像可继续变形路径的“长度 就会缩短，限制了变形的范围，使图像失去可持续变 形、可持续利用的机会；在变形控制上，即使一种变形技术能够产生很好的变形效果， 但如果其变形控制复杂、种类不丰富、难以操作，则仍然不能称之为一个优秀的图像变 形技术。高质量的变形效果配合强有力的控制手段，才能发挥出该技术应有的效率。 因此图像变形中一个重要的问题是变换控制。为了实现变形利用控制句柄来操作变 形。这些控制句柄可以通过点的形式也可以通过线段，甚至是多边形网格，这些都是图 像本身的特征，通过改变控制句柄( 网格、特征线或特征点等) 的方向和位置对图像进行 操纵，使图像产生连续、光滑、逼真的变形 1 0 - l l 】。因此根据控制句柄的不同，可以将图 像变形分为基于网格的图像变形、基于域的图像变形以及基于点的图像变形。 ( 1 ) 基于网格的图像变形技术 网格变形算法首先在图像中选择若干特征控制点，建立图像的特征网格模型，通过 改变图像上有限的控制点，使图像的其余部分在某种规则的约束下自动调整，同时保证 大连理工大学硕士学位论文 控制点的位置仅影响该点附近的一个小区域的图像。 d o u g l a ss m y t h e 9 】提出的网格变形技术首先用网格来控制图像扭曲，然后再采用溶 解技术获得中间图像。w o l b e r g 的书【1 2 】在这方面做了深入研究和精辟论述，涵盖了数字 图像变形的基础内容，高水平的介绍了二维样条的网格变形技术，该技术具有快速、直 观和高效的优点。 最著名的变形方法是基于网格的自由形式的变形技术( f r e ef o r md e f o r m a t i o n ， f f d ) 1 3 - 1 5 】，如今被广泛的应用在商业软件的一些方法，它们运行的速度快。在f f d 中， 一个图形被嵌入一个网格中，通过移动网格的控制点来控制变形。f f d 简单容易使用， 利用二维三次曲线参数化图像，生成c 2 连续变形函数。但是这种方法需要将网格线和 参数化曲线的控制点对齐，不方便操作。而且，在f f d 中操纵许多控制点是非常费力 的事，对于用户来说比较麻烦。 传统的多边形网格变形方法都注重于变形的准确控制，用户操作时不直观而且麻 烦。k h o 和g a r l a n d t l 6 】提出了一种非规则多边形网格的变形技术，用户通过在图像平面 上勾画曲线就可以定义变形区域。通过移动该曲线，用户可以直接控制整个图像的变形。 同时该曲线提供包括扭曲和缩放在内的变形参数。该技术可以对各种非规则多边形网格 模型进行变形，具有易于操作、直观等特点。 b l a n c o 和o l i v e i r a 1 。7 】提出了基于特征曲线操作的快速网格变形技术。用描述网格模 型的直线集生成参数曲线，控制该曲线可以实现变形。参数曲线可以从图像轮廓中自动 提取。该技术不需要对变形图像进行预处理，因此对于使用者的技术要求不高，可以实 现具有真实感、快速的变形效果。 ( 2 ) 基于域的图像变形技术 域变形算法最早是由t h a d d e u sb e i e r 和s h a w nn e e l y l l 8 】提出的，利用起始图像和终 止图像中有代表性的线段对来定义两幅图像间的特征坐标映射，其它的点通过到线段的 距离来确定对准关系。在这种变形方法中，特征对是直线或者是线段，这种方法给了用 户很大的自由选择的权力，在变形之前，首先由用户在人机界面上的源图像和目标图像 上选择线段，根据所选择的线对建立特征对应关系，也就是根据在不同图像上的线段来 建立特征一一对应关系，根据这个特征对应关系建立映射函数。这个映射函数是指一组 线对的两个直线是一对应的，直线以外的点根据它们到直线的距离以及它们在直线上 的投影点的位置来确定其对应处的位置。映射函数建立好以后，通常用逆向映射来估计 图像变形，依次扫描目标图像的每个像素，根据映射函数在原始图像中找出对应像素， 这样目标图像的每一个像素都会有适当的填充，所有的像素点都映射到其对应的位置后 也就完成了图像变形。这种方法比网格法更赋有表现力而且更加容易表达用户的设计思 移动最小二乘图像变形方法研究 想。操作中只需要在起始图像和终止图像中的关键特征点处标定特征线对，不必对非特 征点进行标定，即可产生相当不错的流畅渐变效果。但同时它的运算复杂度也是非常高， 特别是随着特征线段的增多，其运算时间会急剧上升。 王建宁等人【19 】提出了一种基于三角形特征对应的域变形方法，该方法在离散的特征 对应点的基础之上构造了一系列三角形之间的对应关系，然后通过三角形内部的线性关 系求得图像间各点的对应关系。这种做法使得插值的区域缩小了，加强了局部的信息向 导，在速度上取得了优势。同时由于本算法的开销与场景复杂度无关，而只与图像大小 有关，所以容易取得快速、逼真的变形效果。 于学春【2 0 】等人提出了一种基于扫描线的域变形技术，在得到所需变形图像的边界约 束后，采用给出的扫描线填充算法，将原始图像中的颜色完整地赋给变换图像，从而实 现了图像的精确变形，保证了变形后的图像颜色与原始图像变化趋势相同。 ( 3 ) 基于点的图像变形技术 点变形算法的变形函数完全建立在对离散特征点插值的基础上。通常图像对于特征 的描述可归纳为点、线段或者曲线的集合。另一方面，由于线段和曲线都是由点组成的， 所以所有对于特征的描述可以完全统一为一个点集合。基于点的变形算法比基于域的变 形算法更好，其原因有以下几点，首先，域变形以线段为特征，而每组线段是两个点的 连线，也就是说要建立映射关系，其控制点的个数必须是偶数，其次用点作为特征来建 立映射函数比用线段作为特征更为自然，另外，域变形算法中线段是不能交叉的，而以 点作为特征却没有这样的限制。 i g a r a s h i 2 l 】等人提出的基于点的图像变形技术，将输入的图像进行三角剖分，对未 知变量个数等于三角形顶点之和的线性方程组进行求解，最大程度的减少了图像变形后 的撕裂和扭曲，同时使图像的变形尽可能的刚性。 h a r t 等人【2 2 】提出了一种基于样条曲线的自由形状变形技术。该算法可以自动提取出 样条曲线上的点，并传递施加在沿法线方向的相应顶点处的外力限制。通过对每一个顶 点加入一个影响因子使这些限制只作用在局部区域。该技术可以精确地控制图像的形状 变形。 利用径向基函数来进行图像变形的方法就是在源图像和目标图像上选点，这些点就 是特征，根据这些点对的对应关系，用径向基函数来建立映射函数，然后目标图像中的 每个像素点都会根据这个映射函数找到它在源图像中对应的像素点。 李旭东等人【2 3 】提出了提出了一种基于非对称径向基函数的图像变形算法，该算法克 大连理工大学硕士学位论文 服了基于对称径向基函数算法中由于对称径向基函数的全局性导致的图像边界变形过 大的不合理变形现象。 还有能量最小化方法、多层次自由变形方法以及移动最小二乘等图像变形方法。 由于网格扭曲方法不能保证扭曲一一对应，当一个网格扭曲应用到一幅图像上时， 变形图像有可能从自身折叠回来，针对这一缺点，l e e 等人提出能量最小化方法1 2 铊引， 从而保证一对一的变形算法，也避免了折叠的发生，本方法允许用各种基元作为特征对， 比如：点、线段、曲线等，这些基元被归类到一个集合中，然后根据这个集合产生映射 函数( 变形函数) ，这可以看作是一个直角平板的二维变形，这种方法同时也是c 1 连续的， 在这个变形方法中变形是受到能量的限制的，也就是要在能量最小的条件下进行，当能 量最小时，其变形效果是很平滑的，但是由于其计算量太大，本方法没有得到足够的重 视。 多层次自由变形( m f f d ) 同样是由l e e 提出，它比能量最小化方法更简单，更快， 它穿过一个层次控制网格来产生一对一的而且是c 2 连续的映射函数，在某些特殊情况 下，多层次自由变形是用到了双立方b 样条张量积的自由变形( f f d ) u 4 】的延伸，从位置 限制中导出变形。 l e v i n 等人【2 6 】提出了最小二乘法的理论模型，基于该模型w e n g 等人【2 7 】提出了非线 性最小二乘规划算法( 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 a r c h i n gs q u a r e s 算法自动提取边缘多边形的轮廓。该算 法的目的是保持两个局部性质：外轮廓的拉普拉斯( l a p l a e i a n ) 坐标和图形内部的局部面 积。拉普拉斯坐标表现了图形边缘的局部细节，并且广泛的应用在三维网格变形方法中。 对于三维网格保持拉普拉斯坐标通常可以产生好的形变效果，但是对于二维变形要想产 生视觉满意的效果仅仅这样是不够的。 s c h a e f e r 等人【2 8 】提出了一种基于移动最小二乘法的图像变形方法，该方法利用控制 点或控制直线段对图像进行变形，分别对图像的仿射变换、相似变换和刚性变换进行了 研究分析。但该方法没有考虑图像变形的形状拓扑学关系，当变形图像轮廓不规则时， 很难利用控制点或控制直线去描述轮廓信息。作为一种延伸，控制曲线可以直观地描述 复杂的形状和轮廓变形。虽然直线也可以被认为是近似的曲线，但是这样变形成本较高。 1 3 基于纹理合成技术的研究现状 基于样图的纹理合成是近年来计算机图形学、计算机视觉和图像处理领域的一个研 究热点，它广泛应用于三维真实感显示、虚拟现实、图像修复等方面。该问题可以描述 移动最小二乘图像变形方法研究 为：给定一个有限的纹理样本，生成任意大的与样本视觉上相似但又有一定差别的纹理 图像。早期的纹理合成方法受纹理分析思想的影响，通过匹配样本的统计特征进行纹理 合成【2 9 - 3 1 1 ，但其仅适用于随机纹理。近年来的研究表明，基于m a r k o v 随机场模型的区 域增长方法能对大多数纹理取得比较好的合成效果，根据合成单元的大小，纹理合成方 法可分为逐点合成方法【3 2 3 7 1 和逐块合成方法【3 8 4 5 1 。 逐点合成方法每次合成一个点，合成时在样本中搜索与待合成点邻域最相似的邻 域，将对应点拷贝到合成图中。e f r o s 等【3 2 】首先提出基于无参采样的逐点合成算法； w e i 等【3 3 】在文献3 2 的基础上进行改进，用多分辨率和树形矢量量化方法进行加速； a s h i k h m i n 3 4 】提出了基于相关搜索的合成算法，将邻域匹配搜索限定在由已合成的相邻 点所确定的一个小范围内，提高了合成速度，但该方法仅适用于自然纹理；t o n g 掣3 5 】 拓展了a s h i k h m i n 的算法，提出k c o h e r e n c e 搜索，使得合成质量更高，适用范围更广； l e f e b v r e 等【3 6 3 7 】提出了基于g p u 的逐点合成方法，可实现运行时的实时合成。一般来 说，逐点合成方法由于合成粒度小，容易对合成进行控制；合成每一个点都要进行搜索， 速度较慢；由于合成后面的点需要用到已合成点，容易造成误差的传递和累积。 逐块合成方法每次合成一个图像块，然后用一定方式将各个块融合在一起。x u 等 首先提出了基于随机拼贴块的合成算法，但其仅适用于随机纹理；e f r o s 等【3 9 】提出一 种逐块合成算法，根据待合成块的邻域搜索匹配块，并用最小误差路径法优化相邻块间 的接缝；l i a n g 等【删也提出一种与文献3 9 类似的算法，但采用像素混合的方法优化块 间重叠区域，另外利用优化的k d t r e e 、四叉树金字塔和主元分析使算法的速度达到实 时；k w a tr a 等提出一种基于g r a p h c u t 的合成算法，将整个样本作为一个块，每次 以选定位移放置到合成图中，然后用g r a p h c u t 来决定最终的输出区域，该方法无需设 置块参数。近年来，基于t i l e 的实时纹理合成方法【4 2 书】也得到发展，该类方法预先计算 得到一个t i l e 集合，合成时按照一定规则从中选取t i l e 完成无缝拼贴。韩媛媛掣4 4 j 提出 一种改进的基于样图的块拼贴纹理合成算法。针对拼贴纹理块时产生的局部性边界不匹 配现象，用图的切割算法寻找块重叠区域的最优拼接路径，有效地提高了纹理合成质量。 同时采用多分辨率图像金字塔构建输入纹理图像，并结合螺旋线搜索策略和加速算法提 高纹理合成速度。但是由于文中算法仍然采用固定的纹理块大小，因此合成质量还存在 一定的约束。聂俊岚【4 5 1 分析了块纹理合成方法中纹理块尺寸对合成结果的影响，经过对 大量不同类型纹理图像采样，归纳并验证了纹理相关性特征值与纹理块尺寸之间的关 系，得出纹理相关性特征值自适应调整纹理块尺寸的算法。采用该算法可避免因纹理块 尺寸选取不当而引起的合成时间的增加和合成质量的降低。 大连理工大学硕七学位论文 与逐点合成方法相比，逐块合成方法更加快速，且能完好保留块内特征，但块间容 易出现不一致，尤其是结构特征的不一致。其主要原因是大多数算法都采用像素r g b 值的差的平方和来进行相似性度量，而这种度量不能很好地反映纹理的结构差异。为此， w u 等【4 6 】提出一种基于特征图的纹理合成算法，通过特征匹配和必要时的变形来保持块 间结构特征的连续性，取得了不错的效果；但该算法速度较慢，且过度的变形会影响合 成质量。国内张蓬掣4 7 1 和杨刚等【4 8 】也提出了保持纹理结构的合成算法。 1 4 本文的主要研究内容 本文工作的主要内容包括： ( 1 ) 研究了基于点的移动最d - 乘图像变形方法的数学模型，在交互模式下，可以 在图像上建立、移动和删除控制点，实现图像变形。 ( 2 ) 研究了基于曲线的移动最小二乘图像变形方法的数学模型，在交互模式下，可 以在图像上建立、移动和删除控制曲线，实现图像变形。保证了图像变形的真实性。 ( 3 ) 在o p e n g l 环境下，研究了图像变形的加速算法，对源图像进行网格划分，利 用变形函数计算出网格点变形后的坐标，在o p e n g l 中生成变形后的网格点框架；然后 将变形前的二维图像转化为纹理贴到网格点框架上，从而提高了图像变形速度，达到实 时性的变形效果。从计算效率和效果上保证了图像变形的效果。 ( 4 ) 针对某些图像变形中所出现纹理挤压或拉伸现象，研究了基于逐块纹理合成技 术的细节保持。通过控制曲线方程和法线方程生成候选块，利用像素r g b 值差的平方 和最小的原则进行挑选，最终将合适的候选块纹理合成到变形后图像中对应的待合成块 上。通过整体图像变形与局部细节保持消除了非真实感的纹理挤压或拉伸现象。 基于上述内容，本文各章节的安排如下： 第一章：绪论。阐述了基于图像变形的研究背景和研究意义，并介绍了该技术的研 究现状。 第二章：阐述了图像变形的原理，基于点的移动最小二乘图像变形方法的数学模型、 仿射变换、相似变换和刚性变换等概念。这些内容是基于移动最小二乘图像变形方法的 理论基础。 第三章：建立基于曲线的移动最小二乘图像变形方法的数学模型，并推导了仿射、 相似和刚性变换情况下的变形公式，进行了基于控制曲线集的图像变形研究。同时对基 于点和基于曲线的变形实例进行了比较。利用o p e n g l 纹理映射技术来实现图像的变形 加速。 移动最小二乘图像变形方法研究 第四章：纹理合成。针对某些图像变形过程中所出现的纹理挤压或拉伸现象，研究 了基于纹理合成的细节保持方法。采用逐块纹理合成的方法，在样图中生成候选块，根 据像素r g b 值差的平方和最小的原则进行挑选，最终将合适的纹理块合成到变形后图 像中对应的待合成块上，消除纹理挤压或者拉伸现象。 第五章：系统实现。介绍了图像变形及加速系统的设计原则、编程环境及主要的程 序模块和函数，并展示了系统的界面、实现功能等。 总结：总结本文的主要工作，并对以后的工作做出展望。 一8 一 大连理工大学硕士学位论文 2 基于移动最, j 、- - 乘法的图像变形 2 1图像的表示方法 现实世界中存在着大量的二维图像资源，这些图像一般采用连续和离散两种表示形 式【4 9 1 。当以连续的形式来考察图像时，将图像用连续函数来描述和分析，图像成为其定 义域上的一个场量，处理过程是对该连续函数的一个域变换。当以离散的形式来考察图 像时，将图像看成离散采样点的集合，每个点具有各自的属性，对图像的操作就是对这 些离散单元的操作，处理过程是通过说明如何对每个像素点进行处理来描述的。 连续和离散是客观存在的两种图像表示形式。连续图像经数字化后成为离散的数字 图像，因此离散图像可以有其连续的本原，另一方面，连续的图像可以用离散形式来表 示。论文中涉及的图像均为离散数字图像，其表示方式如下所述： ( 1 ) 图像的离散表示 一般对离散图像采用如下的特征矩阵来表示： l = s 1 1 $ 1 2 s 2 1 $ 2 2 s m ls m 2 s 1 月 s 2 月 s m 式中，是采样点像素值，f 表示像素点位于图像的第f 行上，- ，表示像素点位于图 像的第j 列上。如上，表示图像有m 行和，2 列。 ( 2 ) 图像的内存表示 图像的内存映像直接对应图像的矩阵表示，具体形式如下： 图像在内存中的映像相当于行堆叠法生成的图像向量，这种表示很适合图像操作的 扫描线法。操作时，对图像按照从左至右、从下至上的顺序，依次扫描每个像素点，并 将扫描到的像素颜色值按照上述表示方式保存到内存中，其中，从s ，到s 。依次代表图 像中的每个像素点的颜色值。 2 2 移动最, j , - - 乘图像变形方法的数学模型 可以将图像变形看成在变形函数厂作用下由未变形图像映射到变形图像的过程。以 移动域小一乘幽像变形方浊研究 基于控制点的图像变形为例，图2l ( a ) 为原始图像，设变形前控制点的集合为5 ，罔21 ( b ) 为变形后图像，设变形后控制点的集合为d 对于变形函数r 一定有以下性质： p 令青 ( 。i ) 胤始陶像( b ) 变形后蚓像 ( a ) o i g i n a li m a g e啦) d e f o r m e di m a g e 倒2l 图像变形原理 f i g21p r i n c i p l eo f i m a g e d e r o g a t i o n ( 1 ) 插值性：在，作用下j 点直接映射到d 点( 有公式f ( s 。) = 4 ) 。 ( 2 ) 光滑性：厂应该产生光常的变形。 ( 3 ) 确定性：如果挎制点j 和d 是司一点，r 府该是确定的方程( 有公式 t = 4j f ( v ) = v ) 。 对于冈像中的任。像素点v ，将，作川于未变形| 冬】像r 的每一个像豪点就可以街 到变形后的蹦像。根据移动最小二乘法( m o v 1 9l e a s ts q u a r e s ，m 【s ) 理论模型，必然存 在变形函数，使下式取得最小值： ，( _ ) 一d 2 其中，和一为控制点集中像素点的坐标，用行向量表不，为权重，表边式为 w ，= l k v l h ，口为调节变形效果的参数，变形中取值为1 。由十权重的取值随着 v 在图像中取点的位置不同而变化，因此把这种方法称为移动最小二乘方法。当v 取值 为关键点时，趋近于无穷太，此时可定义f ( s ，) = 矿；若关键点坐标值不变，则定 义f ( s ) = j = d ，。 大连理工大学硕士学位论文 一般地，变形函数f ( v ) 可以分为线性变换项和平移变换项，分别用2 2 的矩阵m 和长度为2 的行阿量丁表示，则有： f ( v ) = v m + t ( 2 2 ) 将公式( 2 2 ) 代入公式( 2 1 ) ，并求最小值，即对的变量求导数且等于零，有： 丁= z ，w , d , 军w ，一l ；w 一；w ，j m ( 2 3 ) l|tt |l， 这样可得变形函数的一般形式： ( v ) = ( 1 ，一文) m + 以( 2 4 ) 和以的表达式为： w 矗= 蕾 么一”f w f 巧厶”f “ 如蕾 ( 2 5 ) ( 2 6 ) 在此基础上，公式( 2 1 ) 可以改写为： w ，pm 一吖 ( 2 7 ) ， 其中：j ，= s ，一s 。，0 ，= 谚一d ，注意到在m l s 这个框架中，矩阵m 可以视为一 般化的仿射变换，包含了缩放、错切、旋转等变换成分。可以对这些成分进行组合分析， 获得仿射变换( 非均匀缩放、错切和平移) 、相似变换( 同比例缩放、旋转和平移) 以及刚 性变换( 非均匀缩放、旋转和平移) 情况的变形函数厂。 2 3 基于点的移动最小二乘图像变形方法 2 3 1 仿射变换变形函数 对公式( 2 7 ) 求偏导使其等于零： 移动最小二乘图像变形方法研究 者= 2 二w 心，mo ) = 。 线性变换矩阵m 可以表示为： ( 2 8 ) m = ( w ，j ，) 一1 w 童；0 ， ( 2 9 ) ， j 由上式，遍历整幅图像像素点v ，经计算即可生成仿射变换变形后的新图像。 将公式( 2 9 ) 带回到公式( 2 4 ) 中，可以推导出仿射变换变形函数无( v ) ： 无( v ) = ( v s ) ( 譬w ，圹1 w ；歹0 + d ( 2 1 0 ) i i 根据公式( 2 1 0 ) ，代入图像中的任一像素点，的坐标，都可以计算出变形函数无( v ) 的表达式。无( v ) 是一个1 x2 的矩阵，表示变形后像素点v 的新位置。 2 3 2 相似变换变形函数 仿射变换存在着不均匀比例的缩放和错切，这使得图像变形的真实感较弱。相似变 换是仿射变换的特殊形式，只包括平移，旋转和同比例缩放。为了使变换矩阵只采用相 似变换，限制m 具有如下性质： 对于特定值名有m7 m = 名，。将m 写成块矩阵的形式m = ( m ，m 2 ) ，m 。和m 2 都是 长度为2 的列向量，且m l r m l = m 2 r m 2 = 名，m l r m 2 = 0 。推出m 2 = m l 上，上是一个 一i 维向量操作符，( x ，y ) = ( 一y ，x ) 上。虽然被限制，求解公式( 2 7 ) 最小值的问题可以转换 为找到m ，使得下式取的最小值： 引( 一仆。啊l 2 亿 这个二次方程有唯一的最小值，因此可以推出最理想的线性变换矩阵m ： m = 古c 莩w f ( 0 小产7 ) 亿2 ， 其中： 大连理t 大学硕士学位论文 k 。= w ，毫 将公式( 2 1 2 ) 带回公式( 2 4 ) 中，可以得到相似变换变形函数z ( 1 ，) ： 肌) ( 军缸 川 其中： 仁嵋瞄上 r ( 2 1 3 ) ( 2 1 4 ) ( 2 1 5 ) 与仿射变换相似，根据公式( 2 1 4 ) ，代入图像中的任一像素点v 的坐标，都可以计 算出相似变形函数f ( v ) 的表达式，生成变形后的新图。 2 3 3 刚性变换变形函数 相似变换在保持原图像角度关系上的效果要优于仿射变换( 称这种严格保持角度关 系的变换为等角变换) ，但是同比例缩放在某些局部位置经常会产生不理想的效果。近 来，a l e x a 5 0 】等人的研究显示，对于真实感的形状，变形应该尽可能的刚性，也就是说 变形的比例不应该一致。传统的研究者在解决这个问题上一般采用非线性约束 m 7 m = ，但是注意到，h o r n 5 1 1 9 8 7 年的重复最近点集一文中指出：在包含点s ，和d ， 的协方差矩阵的特征值和特征向量中能够找到最理想的刚性变化。下面推导出刚性变换 与2 3 2 节中的相似变换相关。 设c 为使相似函数取得最小值的矩阵： m魏，zwii，mmtmo f l 2 ：磐，i ( 2 1 6 ) 其中c = 2 r ，r 是旋转矩阵五是一个标量，则旋转矩阵r 使刚性函数取得最小值： 巾m i n ：，军w p ，m 一乏1 2 证明过程如下。首先，通过二次方的形式扩展上面两个误差函数，表示为： ( 2 1 7 ) 移动最小二来图像变形方法研究 嬲w ( 榔a ，t 一2 石，磁7 + 匆匆7 ) ( 2 1 8 ) 。m 。i n ：，w ，( ；，；，7 一2 ；，r 0 ，7 + c i ，0 。7 ) ( 2 1 9 ) 这类最小化问题非常相似。可以通过对r 求偏导来找到最小化这些误差函数的 矩阵： 硼捌- 争7 ， ( 2 2 0 ) ，w i ( - 2 s i 嚣) ( 2 2 1 ) 除非见= 0 ，这意味着一个退化的变形。否则这两个二次方程是等价的，因为 c = 旯r 意味着利用r 能使刚性变换的二次方程取得最小值。一r 对应方程的最大值， + r 对应方程的最小值。这个推导对于任意变形都是成立的，而且非常方便对二维图像 进行操作。利用这个定理，发现刚性变换中m 的表达式与公式( 2 1 2 ) 基本上相同，不过 在这里引入了一个新的常量k ，使得m7 1 m = ，： ( 2 2 2 ) 推导出刚性变换函数f a y ) ： ，( d ：i v 一i 器+ 巩 ( 2 2 3 ) l ，( 训 z ( v ) ：匆4 ，4 见公式( 2 1 5 ) ( 2 2 4 ) 同前两种方法相比，这种变形方法具有很强的真实感，能够使使用者有操纵真实物 体的感觉。 人连理1 人学碗十学位论文 24 基于点的图像变形实例 241 映射方式 利用22 节推导出的变形幽数，町以计算出图像上任一像素点v 变形后的新位置， 将每个原始图像像紊的颜色值依次复制到目标图像的指定位簧，就生成了新的剀像。h 前，幽像变形土要采用曲种映射方式：正向映射和逆向映射。 正向映射是由原始图像通过变形函数，直接获得目标陶像，。包括采样和蓐建两 步。首先对原始图像采样，即扫描原始图像，的每一个像素：然后苹建，即通过变形函 数，依次计算每个像素对应到目标图像，。中的位置，将每个原始图像像索的颜色值依次 复制到目标图像中的指定位置。在采样时，原始图像像素是用空间整数坐标柬表小但 是，经过变形函数r 映射计算后，所得k 标值一般都是实数。若简荦地对实数默整来获 得整数坐标，以此重建的目标图像，会出现“空洞”和“重叠”等缺陷1 5 “。当埘原始图 像的多个像素采样，重建后映射到目标罔像的同一像素点时，会引起草番现蒙：而原始 罔像的两个相邻像素点映射到目标图像的两个不相邻像素点时，就可能出现空涮现象。 逆向映射足从目标图像，。出发，通过变形函数r 求解目标图