- 1 -
中国科技论文在线
基于移动最小二乘法的图像变形及 GPU实
现
邱文杰，陈坤斌，刘琼，李学明**
作者简介：邱文杰（1988-），男，硕士研究生，主要研究方向：多媒体通信、图像处理
通信联系人：李学明（1969-），男，教授，博士生导师，主要研究方向：多媒体通信、图像处理
（北京邮电大学信息与通信工程学院，北京 100876） 5
摘要：图像变形是一种基于变形控制特征，根据一定的变形函数生成平滑、具有真实感的变
形效果的图像处理技术。本文对基于移动最小二乘法的图像变形的三种变换方式：仿射变换、
相似变换和刚性变换进行比较；然后在 iOS平台上实现变形算法并运用 OpenGL ES技术进
行并行运算实现算法加速，实现应用通过手工交互设置控制点集，移动控制点集的位置使图
像产生变形，生成图像的相似变换和刚性变换。最后通过实验，表明该方法可以使图像产生10
平滑、真实的变形,获得满意的效果。以及通过对算法加速前后的对比测试得到加速数据和
结论。
关键词：移动最小二乘法; 图像变形；着色器编程
中图分类号：TP37
15
Image Deformation Using MLS and implementation with
GPU
QIU Wenjie, CHEN Kunbin, LIU Qiong, LI Xueming
(School of Information and Communication Engineering, Beijing University of Posts and
Telecommunications, Beijing 100876) 20
Abstract: Image deformation is a image process technique,which create smooth and realistic
deformation effect through deformation function which define by moving control characters. In this
paper, we compare three type transformations of image deformation using Moving Least Square: affine,
similarity and rigid transformations. Then We present a way to use OpenGL ES technique to optimize
the algorithm by concurrent computing and a image deformation application on iOS platform,in which 25
user can set up control points and move them to create deformation on image. Experiments show that
image deformation speed up at least one order of magnitude by the measure in this paper.
Key words: Moving Least Squares (MLS); image deformation; shader programming
0 引言 30
随着信息时代的到来，多媒体技术不断发展。而作为多媒体的一个重要组成部分，图像
在人们的日常生活中的应用也越来越广泛，人们对于图像处理的需求也愈发强烈。图像处理
技术在许多应用领域受到广泛的重视并取得了重大的开拓型成就，使图像处理成为一门引人
注目、前景远大的新学科。
作为图像处理中的一个重要分支，图像变形是一种基于变形控制特征 根据一定的变形35
函数生成平滑、具有真实感的变形效果的图像处理技术。
常见的图像变形算法包括网格变形算法、域变形算法和点变形算法等等，通过改变控制
句柄（网格、特征线、特征点等）的方向和位置对图像进行操纵，采用有效的变形映射算法
和优化约束控制，使图像产生连续、光滑、自然的变形。
- 2 -
中国科技论文在线
图像变形广泛应用于影视动画、图像融合、医学图像处理和虚拟现实等领域。在动漫产40
业方面，通过关键帧的绘制和图像变形的结合，可以大幅度的减少工作量，加快卡通动画的
制作周期。在医学工程方面，实施医学影像中的器官分离时，通过对样板图像进行变形操作，
使其能在最大程度上接近于目标图像，来实现对目标图像的分割。在影视工业方面，需要影
视作品的特效处理及后期制作处理都需要大量的图像变形原始图像技术的支持。在通信工程
方面，图像变形可以将大数据量的图像传输转化为相应的运动数据传输，节省带宽的占用率 45
并大幅度减少传输的数据量。
本文的最终目的是研究图像变形技术，并在移动终端 iOS 平台实现基于移动最小二乘法
的图像变形算法，以及运用 GPU 加速进行优化。
1 图像变形技术
对于一般变形，在变形效果上，一般不希望出现变形折叠，也不希望出现变形过程中原50
始图像信息的大量丢失现象[1]。如果随着变形的进行，起始图像信息会大量的损失，则图像
可继续变形路径的“长度”就会缩短，限制了变形的范围，使图像失去可持续变形、可持续利
用的机会；在变形控制上，即使一种变形技术能够产生很好的变形效果，但如果其变形控制
复杂、种类不丰富、难以操作，则仍然不能称之为一个优秀的图像变形技术。高质量的变形
效果配合强有力的控制手段，才能发挥出该技术应有的效率。 55
因此图像变形中一个重要的问题是变换控制。为了实现变形利用控制句柄来操作变形。
这些控制句柄可以通过点的形式也可以通过线段，甚至是多边形网格，这些都是图像本身的
特征，通过改变控制句柄（网格、特征线或特征点等）的方向和位置对图像进行操纵，使图
像产生连续、光滑、逼真的变形。因此根据控制句柄的不同，可以将图像变形分为基于网格
的图像变形、基于域的图像变形以及基于点的图像变形。而在基于点的图像变形中，近年来60
发展迅速的技术之一是基于移动最小二乘法的图像变形技术，该方法利用线性函数的变换类
包括仿射，相似和刚性变换。这种实在的变换将会给用户一种操纵真实世界物体的感觉。
2 基于点的移动最小二乘法的图像变形算法
移动最小二乘法的图像变形算法(Image Deformation Using Moving Least Square)是
Schaefer 等[2]提出的，通过控制一些控制点或控制线来修改这些点的位置，根据变形函数来65
改变周围像素点位置而使得图像产生变形效果。
我们假设同样以用户操作控制点的方式来实现图像变形。我们分别设定两个点集p 和
q ，p 代表原始图片中的控制点位置的集合，q 代表变形后的图片中控制点位置的集合。存
在这么一个函数f ：对图片中任意一点x ， ( )xf 是点 x 经过变形以后所在的位置。为了使
得变形最优化，我们引入最小二乘法的概念，通过p 和q 两组控制点控制变形的效果，使70
得下式在全局取得最小值，从而解得函数f 。
( )∑ − iivi qplw (2-1)
其中， ip 和 iq 分别为行向量， iw 为权值常量。
α2/1 vpw ii −=
由上式可以看出，权值函数只与运算的像素点和控制点之间的距离有关，因此我们称之75
为移动最小二乘法。对于每一个像素点v ，权值 iw 会导致变换 vl 不同，从而变换关系会随
- 3 -
中国科技论文在线
着像素点移动而变化。
一般地，变形函数 可以分为线性变换项和平移变换项，分别用M 和T 表示，则有：
( ) TxMxf += (2-2)
将(2-2)式带入(2-1)式，并求最小值，即对f 的变量求导数且令其为 0，得出T 的值，则80
变形函数f 的一般形式为：
( ) ∑
∑
∑
∑ +⎟⎟⎠
⎞
⎜⎜⎝
⎛ −=
i i
i ii
i i
i ii
w
qwMw
pwxxf (2-3)
注意，在移动最小二乘法这个框架中，矩阵M 可以视为一般化的仿射变换，包含了缩
放、错切、旋转等变换成分[3]。可以对这些成分进行组合分析，获得仿射变换(错切、非均
匀缩放和平移)、相似变换(同比例旋转、缩放和平移)以及刚性变换(旋转、平移和非均匀缩85
放)情况的变形函数f 。
仿射变换
我们把(2-3)带入(2-1)式，并对结果求偏导，使结果等于为零，可以求出仿射变换变形函
数 ( )xf 的最终表达式：
( ) ( ) ∑ ∑∑∑∑∑ +⎟⎟⎠⎞⎜⎜⎝⎛ −= − j i ii iijTjji iiii ii ii wqwqpwpwpwpwxxf ˆˆˆˆ 1T (2-4) 90
根据公式(2-4)，我们代入图像中任意一个像素点 的坐标，都可以计算出变形后的新坐
标 ( )xf 。 ( )xf 是一个 21 × 的矩阵。
相似变换
由于仿射变换中存在着不均匀比例缩放和错切，这使得图像变形的真实感较弱。相似变
换是仿射变换的特殊形式，只包括平移、旋转和同比例缩放。为了使得变换矩阵只采用相似95
变换，限制M 具有如下性质：
对于特定值λ有 IMM 2T λ= 。将M 写成块矩阵的形式 ( )21MMM = ， 1M 和 2M 都是
长度为 2 的列向量，而且 0, 2122211 === MMMMMM TTT λ 。推出 ⊥= 12 MM ，⊥是一
个二维向量操作符，( ) ( )⊥−= xyx ,y, 。虽然被限制，求解公式(2-1)最小值的问题可以转
换为找到 1M 使得下式取得最小值，于是我们可以解出相似变换的变形函数 ( )xsf ： 100
( ) ∑ ∑
∑+⎟⎟⎠
⎞
⎜⎜⎝
⎛=
i i i
i ii
i
s
is w
qwAkqxf
1ˆ
其中：
T
i i
i ii
i i
i ii
i
i
ii
w
pwx
w
pwx
p
pwA
⎟⎟
⎟⎟
⎟⎟
⎠
⎞
⎜⎜
⎜⎜
⎜⎜
⎝
⎛
⎟⎟⎠
⎞
⎜⎜⎝
⎛ −−
−
⎟⎟⎠
⎞
⎜⎜⎝
⎛
−= ⊥⊥
∑
∑
∑
∑
ˆ
ˆ
(2-5)
∑=
i
T
iiis ppw ˆˆk
- 4 -
中国科技论文在线
与仿射变换类似，对原始图像中的任意像素点x， ( )xfs 是变形后的像素点坐标。由此105
我们可以生成变形后的新图像。
刚性变换
相似变换在保持原始图像角度关系上的效果要优于仿射变换（这种严格保持角度关系的
变换叫做等角变换），但是同比例缩放在某些局部位置经常会有不理想的效果。对于真实感
的形状，变形应该尽可能的刚性，意味着变形的空间必须保持着统一的缩放比例。Horn[4]1987110
年的重复最近点集一文中指出：在包含 ip 和 iq 的协方差矩阵的特征值和特征向量中能够找
到最理想的刚性变化。
在这里我们引入了一个新的常量 rk ，使得 IM =TM ：
( ) ( )∑ ∑ ⊥+= i i TiiiTiiir qpwqpwk 22 ˆˆˆˆ (2-6)
由此推导出刚性变换函数 ( )vrf ： 115
( ) ( )( ) **rf qvf
vfpvv
r
r +−= G
G
(2-7)
其中上式中的：
( ) ∑= ir ,ˆf iii AAqvG 见公式(2-5)
同前面两种方法相比，这种变形方法具有很强的真实感，能够使得用户有操纵真实物体
的感觉。 120
三种变换的比较
利用我们上面推导出来的变形函数 ，可以计算出图像上任意一个像素点v 变形后的新
位置，将每个原始图像像素的颜色值依次复制到目标图像上的指定位置，就可以生成新的变
形图像。下面图 1 为对图像进行仿射、相似和刚性变换的结果对比图：
125
图 2-1 基于移动最小二乘法的图像变形效果图 a 和 b
- 5 -
中国科技论文在线
图 2-2 基于移动最小二乘法的图像变形效果图 c 和 d
上图中，a 为原图。原图上用户交互生成了 7 个控制点。我们移动其中的若干个控制点
生成变形图像，b、c、d 分别为变换函数是仿射、相似和刚性变换的结果图。可以看到变形130
区域主要集中在图中小猫的手附近，利用仿射变换得到的 b 图中，卡通人物错切严重，而且
有非均匀的缩放。c 图中在保持原图像角度关系上的效果优于 b，但是同比例缩放在某些局
部位置经常产生不理想的效果。比如上图中手的比例有些失真，爪子部分比较明显。而 d
图和 b、c 图对比，效果相对更逼真，能够让用户有操纵真实物体的感觉。
3 基于 OpenGL ES的图像变形加速算法 135
OpenGL(Open Graphics Library)是个定义了一个跨编程语言，跨平台的程序接口的规格，
它用于生成二维、三维图像。这个接口由接近三百五十个不同的函数调用组成[5]，用来从简
单的图像比特绘制复杂的三维景象。常用于 CAD、虚拟实境、科学可视化程序和电子游戏
开发。
OpenGL ES(OpenGL for Embedded Systems)是 OpenGL 三维图形 API 的子集，是从140
OpenGL 裁剪定制的为嵌入式设备而设计的版本。而 OpenGL ES 是参照 OpenGL 的
规范定义的，这个版本引入了对可编程管线的支持。固定管线（固定功能 API）必须随着所
支持的操作、功能的增长而变得愈发复杂。而可编程 API 能够以更直接的方式（由开发人
员编程定制）实现需求。开发人员无需搜索所有可能的模式，只要学习计算机体系结构并制
定想要执行的算法就可以了。 145
基于 MLS 的图像变形算法是简明的且很容易使用标准编程语言来描述。概括来说，对
一个给定图像限制以 m 个控制点进行图像变形，则需要对图像的每个像素点进行 0(m)复杂
度的操作。假设给定图像有 n 个像素点，那么算法的时间复杂度为 0(m*n)。而我们发现，
在变形算法中，给定图像的各个像素点能同时、独立地进行变形，并不依赖其他像素点。这
一特性表明该算法是适宜运用并行计算来进行处理的。 150
之前的研究表明[6]，对 GPU 恰当的使用能使可并行计算的算法表现提升不止一个数量
级。
为了提高图像处理效率，本文采用 OpenGL ES 技术将图像处理工作交予 GPU 进行。图
形系统采用特有的管道几只来运算处理图像数据，对像素点的处理为并行进行，大大提升效
率。OpenGL ES 允许提供编程来控制管道中一些重要的工序，其中包括 shader 着色器。155
着色器包含了允许在顶点上进行一般操作的顶点着色器，以及允许在片段上进行一般操作的
片段着色器。本文利用着色器这一环节来编写 shader 程序运用图像处理算法来处理图像数
- 6 -
中国科技论文在线
据，并将结果输出，达到提高运算速度，提高图像处理效率的效果。
着色器编程[7]，是移植一般算法到 GPU 的最常用技术。在 iOS 平台上，强大的 OpenGL
ES 图形库允许用户对着色器(shaders)进行编程。在图形管道的处理中，按照着色器在流水160
线中的位置来区分，可以把着色器分为顶点着色器(Vertex Shader)以及片段着色器(Frame
Shader)等。本文主要使用 GLSL 语言(OpenGL Shading Language)，把代码片段实现于片段着
色器中。
片段着色器负责输出每个呈现的三角形像素的最终像素颜色。片段着色器以输入的形式
收到顶点着色器通过管道传递的所有这些片段。算法实现中，输入和输出都被储存在纹理内165
存中，变形前，从输入纹理片段中提取出待处理的像素点，经过计算后，变形后的像素点会
按一定的顺序，储存在输出纹理相应的片段里。
顶点着色器
在我们的编程实现中，顶点着色器的实现是很简单的，由于输入的点集是和一般流程类
似的展示网格上的点，所以我们可以用通常的方式或者固定管线来实现顶点着色器。这个着170
色器中几乎没有做任何计算变形新位置的操作，而是主要把变量信息等传递给流水线上的下
一个环节（片段着色器）。
片段着色器
片段着色器的实现中，我们把 GPU 当做是一个通用的并行计算处理单元。输入和输出
都存放在纹理中。每一个变形点都和纹理中的一个片段（fragment、pixel）相对应。当变形175
函数计算结束的时候，变形点就会被储存在我们的变形输出纹理中的相应片段中。
4 系统实现
本文具体实现了一个 iOS 平台上的图像变形应用，并且使用上一章节所说的定制着色器
方法来进行算法加速。
着色器编程是 OpenGL ES 里，从资源耗费来说，比较昂贵的操作。其主要的思想是：180
在程序初始化的时候，编译、链接和验证开发者编写的.vsh 和.fsh 文件。
在 iOS 平台上，我们为了完成上述的构架着色器环境主要用到这么几个接口：
glCreateShader()是用于为指定着色器生成句柄。
glAttachShader()是用于把程序和着色器联系起来。
glCompileShader()，glLinkProgram()，glValidateProgram()这几个函数顾名思义是用来编185
译、链接和验证着色器的。
完成这些关联程序和着色器的操作之后，开发者就可以开始着手用 GLSL 语言编写.vsh
和.fsh。根据我们的算法，并不需要在顶点着色器里做太多事情，我们这次主要工作是编写
片段着色器。要注意的是，由于图形流水线的流程，程序传递到着色器的常量和全局变量需
要传递到顶点着色器中，片段着色器的数据只能从顶点着色器中获取，传递数据（给着色器190
中的全局变量即 uniform 变量）会用到 glUniform 等一些函数。另外，GPUImage[8]，一个第
三方开源框架，封装了关于 iOS 关联程序和着色器的操作。
如 中所说的，我们把变形前后的图片都放在 GPU 的纹理（texture）中，片段着色器
的主要工作是在拥有原始图像纹理的条件下，生成变形后的纹理。本文把移动最小二乘法的
图像变形算法移植成 GLSL 语言并写在片段着色器上。 195
本文最后的工作是在 iOS 平台用 Cocoa Touch 框架实现可交互的图像变形应用。涉及的
- 7 -
中国科技论文在线
技术主要是 Cocoa Touch 的 UIKit 层。感兴趣的读者可以去阅读苹果公司详细的说明文档。
5 实验验证
下面我们用经典的达芬奇名作《蒙娜丽莎的微笑》做测试图像，进行图像变形效果展示
以及针对图像做 GPU 加速前后的性能测试。 200
图 4-1 为原始图像，图 4-2、图 4-3 为根据不同目的变形后的图像。
图 4-1 原始图像
图 4-2 变形后悲伤和开心的蒙娜丽莎 205
- 8 -
中国科技论文在线
图 4-3 变形后变瘦和变胖的蒙娜丽莎
可以看到，基于移动最小二乘法的图像变形随着控制点的移动产生相应的变形，交互友
好，让用户具有操纵图像的感觉。变形效果逼真、平滑、自然。
下表中测试时间为 1000 次的测试结果的均值。保留 6 位有效数字。 210
表 使用定制着色器加速变形前后性能比较
Performance comparison of between using shader and not
加速前(s) 加速后(s)
3 个控制点 图像尺寸 256*256
6 个控制点 图像尺寸 256*256
3 个控制点 图像尺寸 600*1107
6 个控制点 图像尺寸 600*1107
测试环境如下：
用作实验的设备是 16GB 的 iPhone4 手机。 215
系统：iOS
CPU：800MHz
GPU：Imagination PowerVR SGX535
内存：512M
语言：Objective-C、C++、GLSL 220
编译器：Apple LLVM compiler
从上表数据我们可以看到：
算法时间与控制点数 m 以及像素点总数 n 成正比，即 O(m*n)，与算法原理吻合。此外，
使用 GPU 并行计算以后，图像尺寸是 256*256 时，计算时间是加速前的 1/6。图像尺寸为
600*1107 时，计算时间是加速前的 1/9。当图像尺寸越大，加速效果越明显。 225
6 结论
本文对基于移动最小二乘法的图像变形算法的思想和仿射、相似和刚性变换三种变换方
式进行了介绍，然后实现了 iOS 平台上的变形应用，并用 OpenGL ES 技术实现并行运算的
算法加速。
根据本文进行的图像变形效果展示，可以看出基于移动最小二乘法的图像变形效果逼230
真、自然、平滑。
本文开发了一个 iOS 平台的图像变形应用，应用交互友好，能给用户真实操纵物体变形
- 9 -
中国科技论文在线
的感受，有不错的变形效果。
运用 OpenGL ES 技术定制传统的着色器实现加速，加速效果与图片尺寸大小成正比，
与加速前的算法相比，平均减少一个数量级的运行时间。 235
[参考文献] (References)
[1] 孙家广,杨长贵.计算机图形学[M].北京：清华大学出版社，1995.
[2] Schaefer S, McPhail T, Warren J. Image Deformation Using Moving Least Squares[C]. In Proceedings of
ACM SIGGRAPH, Boston, 2006, 533-540. 240
[3] Lee S, Chwa K Y. Image morphing using deformation techniques[J], 1996, 7(1):3-23.
[4] Horn B, Closed-form Solution of Absolute Orientation Using unit Quaternions[J]. Journal of the Optical
Society of America, 1987 4(4): 629-642
[5] 维基百科. OpenGL[OL].
[6] Papakipos. The peakstream platform: High productivity software development for GPUs[M]. In Proceedings of 245
LCI Conference on High-Performance Clustered Computing, 2007
[7] (美)MasonWoo 等著,吴斌等译.OpenGL 编程权威指南[M].北京：中国电力出版社，2001.
[8] BradLarson, GPUImage an open source iOS framework for GPU-based image and video processing[OL].
250
