图像变形的移动最小二乘问题（开题报告） 1
图像变形的移动最小二乘问题
信计071（10070814）张英杰
摘要：在几何造型和计算机动画领域，变形技术已经成为一种越来越重要的工具。曲面变形是计算机辅助几何设计中的一个重要研究课题。通过变形技术可以模拟传统造型和计算机动画技术难以实现的变形效果。这项技术应用于计算机动画，可以减轻美工师的手工劳动；也应用于产品造型设计，可把不同造型特征相互交融，产生新的系列造型。本文将通过使用VC和OpenGL来实现变形算法，并给出相关的例子和比较。 关键词：图像变形，网格，变形算法
1研究背景
1.1 计算机辅助几何设计概述
经典微分几何研究的是曲线曲面的局部性质和几何不变性。计算机的诞生标志着复杂曲线曲面能的计算可以在计算机上实现。而计算机显示技术的发展又使曲线曲面能在屏幕上显示真正面目。20世纪60年代末和70年代初，法国雷诺汽车公司的工程师Bezier和美国麻省理工学院的Conns教授开展的曲线曲面设计工作开创了一个新的学科—计算机辅助几何设计。
计算机辅助几何设计主要研究曲线曲面的计算机表示、逼近和计算。在工程领域，曲线曲面应用十分广泛，大到汽车外形设计，飞机机身设计，船舶船体设计，小到电话机座的设计等；从实质上看他们都是曲线曲面的设计。传统的方法大都是靠手工放样来实现，效率低、精度差，且修改困难，不能适应现代化工业发展的需要。如果借助于计算机来辅助曲线设计，不但速度快、精度高，而且还能在屏幕上显示出来，通过人机交互的方式，曲线曲面的修改十分方便。因此，用计算机辅助设计可以大大缩短设计周期，提高设计精度，加快产品的更新换代。
1.2 曲线曲面造型技术
曲线曲面造型是CAD／CAM／CAE (Computer-Aided Design／Manufacture／Engineering，计算机辅助设计／制造／工程)、CG(Computer Graphics，计算机图形学)、CAGD(Computer Aided Geometric Design，计算机辅助几何设计)等领域的重要研究内容，它涉及数值逼近、计算几何、计算机动画、科学计算与可视化、计算机视觉、图像处理等领域，有着广阔的应用背景．曲线曲面造型主要研究在计算机的环境下曲线曲面的表示、设计、显示和分析等．自Coons、Bezier等大师于上世纪六十年代奠定理论基础以来．已经取得了长足的发展．
图像变形的移动最小二乘问题（开题报告） 2
传统的曲线曲面造型技术起源于飞机、汽车等的外形设计。有着较长的发展历史．早在1963年，美国波音公司的Ferguson首先提出将曲线曲面表示为参数的矢函数方法，并引入参数三次曲线，从此曲线曲面的参数化形式成为形状数学描述的标准形式．1964年麻省理工学院的Coons提出一种具有一般性的曲面描述方法．用给定围成封闭曲线的四条边界定义一块曲面，这是一种超限插值方法．1971年法国雷诺汽车公司的Bezier提出一种由控制多边形设计曲线的新方法。这种方法不仅简单易用，而且很好的解决了形状控制问题．为曲线曲面造型的进一步发展奠定了坚实的基础．随后Forrest和Gordon等人对Bezier方法做了深入的研究．使Bezier方法具有更坚实的理论基础．并最终发展成一套自由型曲线曲面设计系统，UNISURF．但是Bezier方法存在连接问题和局部修改问题．1972年de Boor给出了关于B样条的一套标准算法．1974年Gordon和Riesenfeld把B样条理论应用于形状描述，最终提出了B样条方法，这种方法继承了Bezier方法的优点．同时又解决了局部控制问题，而且在参数连续性的意义下解决了光滑拼接问题．从而使得自由型曲线曲面形状的描述问题得到很好的解决．B样条方法在设计自由曲线曲面时显示了强大的威力．但是经典的B样条表示方法有一个缺陷是不能精确表示球面等常用的初等二次曲面．为了满足工业界的要求，1975年美国Syracuse大学的VerspriUe首次提出了有理B样条方法．后来由于Piegl和Tiller等人的研究．终于使NURBS (Non-Uniform Rational B-Spline，非均匀有理B样条)成为现代曲线曲面造型中广泛使用的技术并成为工业标准． 许多年来，人们不断地探索方便、灵活、实用的曲线曲面构造方法。从提出样条函数至今的50余年间，曲线曲面造型经历了参数样条方法、Coons曲面、Bezier曲线曲面和B样条方法，已取得了辉煌的成果。但人们不满足于现状，仍在继续探索新的造型方法。80年代中期以来，相继出现了自由型变形造型、偏微分方程造型和能量法造型等新技术，并取得了很多研究成果。
1.3 图像变形技术的应用广泛性
图像变形(image morphing)是一种图像处理技术，即在图像间进行二维的形状和颜色插值，产生从起始图像到终止图像的平滑过渡的期间图像，使得起始图像逐渐地变化到终止图像。该技术利用两图像间的对应特征关系，求得相应的几何变换函数，根据变换函数来实现图像的变形。
图像变形技术是近几年来图像处理领域崛起的一个新分支，它主要研究图像中点与点之间的空间映射问题。作为一种计算机视觉方面的应用，它的价值正在研究与实践中不断完善和发展。我们应用图像变形技术在多幅图像之间进行的变换，可以产生惊人的视觉效果。图像变形技术在影视动画，医学成像，虚拟现实等诸多领域中有着广泛的应用。
电影中常见的应用如从某一个脸到另一个脸的变化，或者对于一些给定的图像让它产生喜，怒，哀，乐等复杂的表情变化。这些应用可以使得图像更有生气，使效果更加
图像变形的移动最小二乘问题（开题报告） 3
逼真。同时也可以通过控制物体的形状变化，或者人物动作变化的连续操作来实现动画效果。
在医学成像中，CT和MRI的扫描片可以在一固定薄片间的分辨率水平线上获得。虽然中间薄片可由传统的线性的、立方的或更多次数的插值函数计算得到，但这种传统的方法没有考虑被成像的组织的基本构成结构。通过在扫描片的连续对之间建立特征的对应关系可以获得更加好的结果。计算得到的变形图像构成了中间图像，它们符合由用户提供的几何对应关系。
在卫星图像、超声图像的处理中，它用于校正由于工具或方法的内在限制而产生的图像扭曲;在医学图像处理和三维重建中，变形用于定位、匹配等技术中去;在图像编辑和艺术设计中，利用变形可达到某些特殊效果。在教育领域，变形技术用来作为一种新的形象生动的教学工具。在气象预报中，对气象卫星传送的气象云图应用变形技术可以生成连续的卫星云图，以便描述云图的运动状态。在地理信息系统中，变形技术应用于数字地形模型的生成中，把一幅二维遥感图像叠加到一个三维的地形图上。在刑侦系统中，变形技术用来描述人物脸部特征，构造人脸模型。图像变形也是当今许多新技术的基础，如图像调配技术和基于图像的绘制技术。前者在计算机动画中帮助实现关键帧的平滑过渡;后者帮助产生虚拟现实。
图像变形技术通过改变控制句柄的方向和位置, 采用有效的变形映射算法和优化约束控制, 使图像产生连续、光滑、逼真的变形。随着图像变形技术应用的不断扩展，它的算法也越来越成熟而且具有效率。
2 文献综述
对图像变形方法的研究最早可以追溯到20世纪60年代，生成从一幅数字图像到另一幅数字图像的平滑过渡通常通过一个交叉溶解的过程实现。这是图像变形方法家族中最简单的一种方法，通过线性插值实现一幅图像到另一幅图像的逐渐变化，其视觉效果乏味，不能令人满意。其实从严格的意义上来说，交叉分解方法还不能算是一种图像变形方法，通常只能把它看成是一种图像转变，而且，那时候人们没有对图像变形方法的研究引起足够的重视，这种简单方法生成图像的质量很差。直到20世纪80年代末，Douglas Smythe在电影Willow的制作过程中提出了网格扭曲的变形方法，这种情况才有所改变。在过去的十几年中，图像变形技术的研究取得了突破性的进展。
对于一般变形，在变形效果上，一般不希望出现变形折叠，也不希望出现变形过程中起始图像信息的大量丢失现象。如果随着变形的进行，起始图像信息会大量的损失，则图像可继续变形路径的“长度\就会缩短，限制了变形的范围，使图像失去可持续变形、可持续利用的机会；在变形控制上，即使一种变形技术能够产生很好的变形效果，但如果其变形控制复杂、种类不丰富、难以操作，则仍然不能称之为一个优秀的图像变
图像变形的移动最小二乘问题（开题报告） 4
形技术。高质量的变形效果配合强有力的控制手段，才能发挥出该技术应有的效率。因此图像变形中一个重要的问题是变换控制。为了实现变形利用控制句柄来操作变形。这些控制句柄可以通过点的形式也可以通过线段，甚至是多边形网格，这些都是图像本身的特征，通过改变控制句柄(网格、特征线或特征点等)的方向和位置对图像进行操纵，使图像产生连续、光滑、逼真的变形。因此根据控制句柄的不同，可以将图像变形分为基于网格的图像变形、基于域的图像变形以及基于点的图像变形。 (1) 基于网格的图像变形技术
网格变形算法首先在图像中选择若干特征控制点，建立图像的特征网格模型，通过改变图像上有限的控制点，使图像的其余部分在某种规则的约束下自动调整，同时保证控制点的位置仅影响该点附近的一个小区域的图像。DouglaS Smythe提出的网格变形技术首先用网格来控制图像扭曲，然后再采用溶解技术获得中间图像。Wolberg的书在这方面做了深入研究和精辟论述，涵盖了数字图像变形的基础内容，高水平的介绍了二维样条的网格变形技术，该技术具有快速、直观和高效的优点。
最著名的变形方法是基于网格的自由形式的变形技术(Free Form Deformation，FFD)，如今被广泛的应用在商业软件的一些方法，它们运行的速度快。在FFD中，一个图形被嵌入一个网格中，通过移动网格的控制点来控制变形。FFD简单容易使用，利用二维三次曲线参数化图像，生成C2连续变形函数。但是这种方法需要将网格线和参数化曲线的控制点对齐，不方便操作。而且，在FFD中操纵许多控制点是非常费力的事，对于用户来说比较麻烦。
传统的多边形网格变形方法都注重于变形的准确控制，用户操作时不直观而且麻烦。Kho和Garlandt提出了一种非规则多边形网格的变形技术，用户通过在图像平面上勾画曲线就可以定义变形区域。通过移动该曲线，用户可以直接控制整个图像的变形。同时该曲线提供包括扭曲和缩放在内的变形参数。该技术可以对各种非规则多边形网格模型进行变形，具有易于操作、直观等特点。
Blanco和Oliveira提出了基于特征曲线操作的快速网格变形技术。用描述网格模型的直线集生成参数曲线，控制该曲线可以实现变形。参数曲线可以从图像轮廓中自动提取。该技术不需要对变形图像进行预处理，因此对于使用者的技术要求不高，可以实现具有真实感、快速的变形效果。 (2) 基于域的图像变形技术
域变形算法最早是由Thaddeus Beier和Shawn Neely提出的，利用起始图像和终止图像中有代表性的线段对来定义两幅图像间的特征坐标映射，其它的点通过到线段的距离来确定对准关系。在这种变形方法中，特征对是直线或者是线段，这种方法给了用户很大的自由选择的权力，在变形之前，首先由用户在人机界面上的源图像和目标图像上选择线段，根据所选择的线对建立特征对应关系，也就是根据在不同图像上的线段来建立特征一一对应关系，根据这个特征对应关系建立映射函数。这个映射函数是指一组线对
图像变形的移动最小二乘问题（开题报告） 5
的两个直线是一一对应的，直线以外的点根据它们到直线的距离以及它们在直线上的投影点的位置来确定其对应处的位置。映射函数建立好以后，通常用逆向映射来估计图像变形，依次扫描目标图像的每一个像素，根据映射函数在原始图像中找出对应像素，这样目标图像的每一个像素都会有适当的填充，所有的像素点都映射到其对应的位置后也就完成了图像变形。这种方法比网格法更赋有表现力而且更加容易表达用户的设计思想。操作中只需要在起始图像和终止图像中的关键特征点处标定特征线对，不必对非特征点进行标定，即可产生相当不错的流畅渐变效果。但同时它的运算复杂度也是非常高， 特别是随着特征线段的增多，其运算时间会急剧上升。王建宁等人提出了一种基于三角形特征对应的域变形方法，该方法在离散的特征对应点的基础之上构造了一系列三角形之间的对应关系，然后通过三角形内部的线性关系求得图像间各点的对应关系。这种做法使得插值的区域缩小了，加强了局部的信息向导，在速度上取得了优势。同时由于本算法的开销与场景复杂度无关，而只与图像大小有关，所以容易取得快速、逼真的变形效果。
于学春等人提出了一种基于扫描线的域变形技术，在得到所需变形图像的边界约束后，采用给出的扫描线填充算法，将原始图像中的颜色完整地赋给变换图像，从而实现了图像的精确变形，保证了变形后的图像颜色与原始图像变化趋势相同。 (3) 基于点的图像变形技术
点变形算法的变形函数完全建立在对离散特征点插值的基础上。通常图像对于特征的描述可归纳为点、线段或者曲线的集合。另一方面，由于线段和曲线都是由点组成的，所以所有对于特征的描述可以完全统一为一个点集合。基于点的变形算法比基于域的变形算法更好，其原因有以下几点，首先，域变形以线段为特征，而每组线段是两个点的连线，也就是说要建立映射关系，其控制点的个数必须是偶数，其次用点作为特征来建立映射函数比用线段作为特征更为自然，另外，域变形算法中线段是不能交叉的，而以点作为特征却没有这样的限制。
Igarashi等人提出的基于点的图像变形技术，将输入的图像进行三角剖分，对未知变量个数等于三角形顶点之和的线性方程组进行求解，最大程度的减少了图像变形后的撕裂和扭曲，同时使图像的变形尽可能的刚性。
Hart等人提出了一种基于样条曲线的自由形状变形技术。该算法可以自动提取出样条曲线上的点，并传递施加在沿法线方向的相应顶点处的外力限制。通过对每一个顶点加入一个影响因子使这些限制只作用在局部区域。该技术可以精确地控制图像的形状变形。
利用径向基函数来进行图像变形的方法就是在源图像和目标图像上选点，这些点就是特征，根据这些点对的对应关系，用径向基函数来建立映射函数，然后目标图像中的每个像素点都会根据这个映射函数找到它在源图像中对应的像素点。
李旭东等人提出了提出了一种基于非对称径向基函数的图像变形算法，该算法克大连理
图形变换开题报告
