图像变形方法比较 23页

'图像变形方法比较指导老师:刘利刚学号:PB10007211姓名:吕永亮 中国科学技术大学本科生毕业论文致谢历时将近两个月的时间终于将这篇论文写完，在论文的写作过程中遇到了无数的困难和障碍，都在同学和老师的帮助下度过了。尤其要强烈感谢我的论文指导老师—刘利刚老师，他对我进行了无私的指导和帮助，不厌其烦地帮助进行论文的修改和改进。另外，在校图书馆查找资料的时候，图书馆的老师也给我提供了很多方面的支持与帮助。在此向帮助和指导过我的各位老师表示最衷心的感谢！感谢这篇论文所涉及到的各位学者。本文引用了数位学者的研究文献，如果没有各位学者的研究成果的帮助和启发，我将很难完成本篇论文的写作。感谢我的同学和朋友，在我写论文的过程中给予了我很多你的素材，还在论文的撰写和排版灯过程中提供热情的帮助。由于我的学术水平有限，所写论文难免有不足之处，恳请各位老师和学友批评和指正！2 中国科学技术大学本科生毕业论文目录中文内容摘要.............................................................................................................................1Abstract.......................................................................................................................................2第一章绪论...............................................................................................................................3§1引言..............................................................................................................................3§2数字图像处理的常用方法..........................................................................................4§3数字图像处理的应用..................................................................................................5§4本章小结......................................................................................................................7第二章图像变形技术介绍......................................................................................................8§1图像变形问题的提出..................................................................................................8§2图像变形发展概况......................................................................................................8§3图像变形的技术........................................................................................................10§4保持图像内容的图像变形技术................................................................................13§5本章小结....................................................................................................................14第三章图像变形方法分析比较............................................................................................15§1反距离加权插值法(IDW)分析..................................................................................15§2径向基函数法(RBF)分析............................................................................................16§3两种方法的比较........................................................................................................16§4本章小结....................................................................................................................17第四章结论与展望.................................................................................................................18参考文献...................................................................................................................................19 中国科学技术大学本科生毕业论文中文内容摘要图像变形既是把任一图像转化成任意形状。为了满足审美需求，开发一种既美观又方便客户使用的图像扭曲技术一直是数字图像处理领域中的一个研究重点。此过程可以分为两步：（1）计算图像所有像素合理的位移，（2）重新取样图像创建输出图像。本文主要研究前者。图像变形技术可分为如下两种：(1)直接在像素级进行散乱点数字插值的方法，（2）基于网格变形的纹理图像映射。在基于网格变形的纹理图像映射上，主要包括基于三角形网格和基于四边形网格的技术。而在直接在像素级进行散乱点数字插值的方法中主要包括：反距离加权插值法（IDW），径向基函数法（RBF）,移动最小二乘（MLS）等。按用户交互方式上，则包括点交互，线交互，制定目标图像边界形状以及自适应的边界形变等多种方式。本文主要针对在散乱点数字插值的方法进行探究和实现。最后我们还将系统地比较几种方法，尤其在时间复杂度上对它们进行详细的分析。关键词：图像变形，插值，时间复杂度1 中国科学技术大学本科生毕业论文AbstractTheterm“ImageWarping”describesmethodsfordeformingimagestoarbitraryshapes.Developinganeasy-to-useimagewarpingtechniqueandgeneratingvisualpleasingresultshavelongbeenahotresearchtopicintheimageprocessingfield,whichisvaluableinbothanimationandimagemadelingfield.Theprocessofwarpinganimagecanbedividedintotwosteps:1.Computethedesireddisplacementsofallpixelsinthesourceimage.2.Resampletheimagetocreatetheoutputimage.Thepapermainlystudiestheformer.Theexistingimagewarpingalgorithmscanbecategorizedintopixel-basedimagewarpingbasedonscattereddata-pointinterpolationmethodsandmesh-basedtexturemappingbasedongeometricaltransformations.Intheaspectofscattereddata-pointinterpolation,severalalgorithmsarereviewedinthispapersuchasIDW,RBF,MLS.Ontheotherhand,severalalgorithmsbasedontriangularmeshandquadrilateralmesharealsoreviewed.Intheaspectofuserinteractionapproach,thosealgorithmscanbecategorizedintopointcontrolling,curvecontrollingandtargetboundaryspecifyingapproaches.Atlast,wewillcomparethesemethods,especiallytheirtimecomplexity.Keywords:imagewarping,interpolation,timecomplexity2 中国科学技术大学本科生毕业论文第一章绪论§1引言相比于文字而言，图像所包含的信息更直观，信息量也更大。通常意义下的图像都是连续的图像，产生的也是模拟信号，由于模拟信号处理自身的原因，现在研究对象已从模拟领域延伸到数字领域，这就产生了数字图像[1]。数字图像是二维图像用有限数字数值像素的表示。由数组或矩阵表示，其光照位置和强度都是离散的。数字图像是由模拟图像数字化得到的、以像素为基本元素的、可以用数字计算机或数字电路存储和处理的图像。数字图像处理在空间方面比较早的应用是在20世纪60年代早期，美国加利福尼亚的喷气推进实验室人们对“旅行者7号”卫星传送的月球图像进行处理。在20世纪60年代末70年代初数字图像处理技术也应用在医学图像，地球遥感监测等领域。在20世纪70年代计算机轴向断层技术的发明是图像处理在医学诊断领域最重要的应用之一。至此，图像处理得到了蓬勃的发展。随着图像处理技术的深入发展，从70年代中期开始，随着计算机技术和人工智能、思维科学研究的迅速发展，数字图像处理向更高、更深层次发展。人们已开始研究如何用计算机系统解释图像，实现类似人类视觉系统理解外部世界，这被称为图像理解或计算机视觉。很多国家，特别是发达国家投入更多的人力、物力到这项研究，取得了不少重要的研究成果。其中代表性的成果是70年代末MIT的Marr提出的视觉计算理论，这个理论成为计算机视觉领域其后十多年的主导思想。图像理解虽然在理论方法研究上已取得不小的进展，但它本身是一个比较难的研究领域，存在不少困难，因人类本身对自己的视觉过程还了解甚少，因此计算机视觉是一个有待人们进一步探索的新领域。数字图像处理包含很多方面，包括对图像进行去除噪声，增强，复原，分割，提取特征等。具体如下：图像增强和图像复原是为了提高图像的质量。图像增强突出图像中所感兴趣的部分。图像复原技术则是以图像退化的数学或者概论模型为基础，再采用某种滤波方式，恢复或重建原来的图像。而图像压缩所涉及的技术是减少图像的储存量，或者在传输图像时降低频带。图像分割则是将一副图像划分为组成部分或者目标物。图像识别则是图像经过某种预处理后，进行图像分割和特征提取，从而进行判决分类。除此之外，数字图像处理还包括形态学处理，图像显示等方面。总而言之。他是包含多种技术和方法的一门学科。随着互联网的发展和计算机的普及，图像又是人类获取和交换信息的主要来源，因此数字图像处理的应用必然涉及到人类生活和工作的方方面面，数字图像处理也将有更广阔的的前景。3 中国科学技术大学本科生毕业论文§2数字图像处理的常用方法数字图像处理常用方法有以下几个方面：1）图像变换：由于图像阵列很大，直接在空间域中进行处理，涉及计算量很大。因此，往往采用各种图像变换的方法，如傅立叶变换、沃尔什变换、离散余弦变换等间接处理技术，将空间域的处理转换为变换域处理[13]，不仅可减少计算量，而且可获得更有效的处理（如傅立叶变换可在频域中进行数字滤波处理）。新兴研究的小波变换在时域和频域中都具有良好的局部化特性，它在图像处理中也有着广泛而有效的应用。2）图像编码压缩：图像编码压缩技术可减少描述图像的数据量（即比特数），以便节省图像传输、处理时间和减少所占用的存储器容量。压缩可以在不失真的前提下获得，也可以在允许的失真条件下进行。编码是压缩技术中最重要的方法，它在图像处理技术中是发展最早且比较成熟的技术。3）图像增强和复原：图像增强和复原的目的是为了提高图像的质量，如去除噪声，提高图像的清晰度等。图像增强不考虑图像降质的原因，突出图像中所感兴趣的部分。如强化图像高频分量，可使图像中物体轮廓清晰，细节明显；如强化低频分量可减少图像中噪声影响。图像复原要求对图像降质的原因有一定的了解，一般讲应根据降质过程建立“降质模型”[14]，再采用某种滤波方法，恢复或重建原来的图像。4）图像分割：图像分割是数字图像处理中的关键技术之一。图像分割是将图像中有意义的特征部分提取出来，其有意义的特征有图像中的边缘、区域等，这是进一步进行图像识别、分析和理解的基础。虽然已研究出不少边缘提取、区域分割的方法，但还没有一种普遍适用于各种图像的有效方法[15]。因此，对图像分割的研究还在不断深入之中，是图像处理中研究的热点之一。5）图像描述：图像描述是图像识别和理解的必要前提。作为最简单的二值图像可采用其几何特性描述物体的特性，一般图像的描述方法采用二维形状描述，它有边界描述和区域描述两类方法。对于特殊的纹理图像可采用二维纹理特征描述。随着图像处理研究的深入发展，已经开始进行三维物体描述的研究，提出了体积描述、表面描述、广义圆柱体描述等方法[16]。6）图像分类（识别）：图像分类（识别）属于模式识别的范畴，其主要内容是图像经过某些预处理（增强、复原、压缩）后，进行图像分割和特征提取，从而进行判决分类。图像分类常采用经典的模式识别方法，有统计模式分类和句法（结构）模式分类，近年来新发展起来的模糊模式识别和人工神经模式模式分类在图像识别中也越来越受到重视。7）数字图像变形技术：数字图像变形技术是近年来图像处理领域的一个新分支，它主要研究数字图像的几何变换，即图像中点与点之间的空间映射关系。4 中国科学技术大学本科生毕业论文该项技术最早起源于对遥感图像的几何校正问题的研究，后来被引入到医学成像及计算机视觉领域。近年来，随着多媒体技术的普及，数字图像变形技术有了很大发展，并在电影，电视和媒体广告中有很多非常成功的应用。数字图像变形技术以空间变换，重采样和反走样技术作为理论基础。§3数字图像处理的应用图像是人类获取和交换信息的主要来源，因此，图像处理的应用领域必然涉及到人类生活和工作的方方面面。随着人类活动范围的不断扩大，图像处理的应用领域也将随之不断扩大。1）航天和航空方面航天和航空技术方面的应用数字图像处理技术在航天和航空技术方面的应用，除了JPL对月球、火星照片的处理之外，另一方面的应用是在飞机遥感和卫星遥感技术中。许多国家每天派出很多侦察飞机对地球上有兴趣的地区进行大量的空中摄影。对由此得来的照片进行处理分析，以前需要雇用几千人，而现在改用配备有高级计算机的图像处理系统来判读分析，既节省人力，又加快了速度，还可以从照片中提取人工所不能发现的大量有用情报。从60年代末以来，美国及一些国际组织发射了资源遥感卫星（如LANDSAT系列）和天空实验室（如SKYLAB）[17]，由于成像条件受飞行器位置、姿态、环境条件等影响，图像质量总不是很高。因此，以如此昂贵的代价进行简单直观的判读来获取图像是不合算的，而必须采用数字图像处理技术。如LANDSAT系列陆地卫星，采用多波段扫描器（MSS），在900km高空对地球每一个地区以18天为一周期进行扫描成像，其图像分辨率大致相当于地面上十几米或100米左右（如1983年发射的LANDSAT-4，分辨率为30m）[18]。这些图像在空中先处理（数字化，编码）成数字信号存入磁带中，在卫星经过地面站上空时，再高速传送下来，然后由处理中心分析判读。这些图像无论是在成像、存储、传输过程中，还是在判读分析中，都必须采用很多数字图像处理方法。现在世界各国都在利用陆地卫星所获取的图像进行资源调查（如森林调查、海洋泥沙和渔业调查、水资源调查等），灾害检测（如病虫害检测、水火检测、环境污染检测等），资源勘察（如石油勘查、矿产量探测、大型工程地理位置勘探分析等），农业规划（如土壤营养、水份和农作物生长、产量的估算等），城市规划（如地质结构、水源及环境分析等）。中国也陆续开展了以上诸方面的一些实际应用，并获得了良好的效果。在气象预报和对太空其它星球研究方面，数字图像处理技术也发挥了相当大的作用。2）生物医学工程方面数字图像处理在生物医学工程方面的应用十分广泛，而且很有成效。除了上面介绍的CT技术之外，还有一类是对医用显微图像的处理分析，如红细胞、白细胞分类，染色体分析，癌细胞识别等。此外，在X光肺部图像增晰、超声波图5 中国科学技术大学本科生毕业论文像处理、心电图分析、立体定向放射治疗等医学诊断方面都广泛地应用图像处理技术。3）通信工程方面当前通信的主要发展方向是声音、文字、图像和数据结合的多媒体通信。具体地讲是将电话、电视和计算机以三网合一的方式在数字通信网上传输。其中以图像通信最为复杂和困难，因图像的数据量十分巨大，如传送彩色电视信号的速率达100Mbit/s以上[19]。要将这样高速率的数据实时传送出去，必须采用编码技术来压缩信息的比特量。在一定意义上讲，编码压缩是这些技术成败的关键。除了已应用较广泛的熵编码、变换编码外，国内外正在大力开发研究新的编码方法，如分行编码、自适应网格编码、小波变换图像压缩编码等[20]。4）工业和工程方面在工业和工程领域中图像处理技术有着广泛的应用，如自动装配线中检测零件的质量、并对零件进行分类，印刷电路板疵病检查，弹性力学照片的应力分析，流体力学图片的阻力和升力分析，邮政信件的自动分拣，在一些有毒、放射性环境内识别工件及物体的形状和排列状态，先进的设计和制造技术中采用工业视觉等等。其中值得一提的是研制具备视觉、听觉和触觉功能的智能机器人，将会给工农业生产带来新的激励，目前已在工业生产中的喷漆、焊接、装配中得到有效的利用。5）军事公安方面在军事方面图像处理和识别主要用于导弹的精确末制导，各种侦察照片的判读，具有图像传输、存储和显示的军事自动化指挥系统，飞机、坦克和军舰模拟训练系统等；公安业务图片的判读分析，指纹识别，人脸鉴别，不完整图片的复原，以及交通监控、事故分析等。目前已投入运行的高速公路不停车自动收费系统中的车辆和车牌的自动识别都是图像处理技术成功应用的例子。6）文化艺术方面目前这类应用有电视画面的数字编辑，动画的制作，电子图像游戏，纺织工艺品设计，服装设计与制作，发型设计，文物资料照片的复制和修复，运动员动作分析和评分等等，现在已逐渐形成一门新的艺术--计算机美术[21]。7）机器人视觉机器视觉作为智能机器人的重要感觉器官，主要进行三维景物理解和识别，是目前处于研究之中的开放课题。机器视觉主要用于军事侦察、危险环境的自主机器人，邮政、医院和家庭服务的智能机器人，装配线工件识别、定位，太空机器人的自动操作等。6 中国科学技术大学本科生毕业论文8）视频和多媒体系统目前，电视制作系统广泛使用的图像处理、变换、合成，多媒体系统中静止图像和动态图像的采集、压缩、处理、存贮和传输等。9）科学可视化图像处理和图形学紧密结合，形成了科学研究各个领域新型的研究工具。10）电子商务在当前呼声甚高的电子商务中，图像处理技术也大有可为，如身份认证、产品防伪、水印技术等。总之，图像处理技术应用领域相当广泛，已在国家安全、经济发展、日常生活中充当越来越重要的角色，对国计民生的作用不可低估。§4本章小结如前所诉，数字图像变形技术室图像处理的一大重要分支。在微观图像的增强处理，考古学及历史学研究中模糊，变质图像的恢复处理方面，数字处理技术都是迅速有效地。这些将有助于丰富我们的生活，提高人类自身的文明程度。本文将着重于图像变形技术的研究，及方法比较。7 中国科学技术大学本科生毕业论文第二章图像变形技术介绍图像变形技术一般应用在图像设计，建模以及动画制作上。用户可以选择一系列操作来达到变形的目的。这些操作可以采取点，线，甚至多边形网格的形式。当用户更改这些操作时，图像会以一种直觉的方式变形。本章主要介绍几种变形的方法。§1图像变形问题的提出数字图像是二维图像用有限数字数值像素的表示。基于点对交互的图像变形问题其实就是在图像上指定一系列点对：起点和终点，变形后的图像起点要移动到终点位置。这些点对就叫做控制点。这些点对的位移会对整个图像产生怎样的效果呢？显然控制点的位移会导致其相邻点的位移，因此这个问题的本质是散乱点的差值问题。§2图像变形发展概况对图像变形方法的研究最早可以追溯到20世纪60年代，最初只是交叉分解变形方法，这种方法的视觉效果是一幅图像慢慢地变成另外一副图像，但其视觉效果乏味，不能令人满意，这是由于在错匹配区域的明显双重曝光造成的，其实从严格的意义上来说，交叉分解方法还不能算是一种图像变形方法，通常只能把它看做是一种图像转变，而且，那时候人们没有对图像变形方法的研究引起足够的重视，知道20世纪80年代末，D.Smythe在电影《Willow》的制作过程中提出了网格扭曲的变形方法[6]，这种情况才有所改变。在过去的十几年中，图像变形技术的研究取得了突破性的进展。对图像变形方法的研究从几个方面展开：网格扭曲，线对变形方法，径向基函数变形方法，能量最小化方法，多层次自由变形方法，工作量最小化方法等。其中线对变形方法和径向基函数变形方法都是比较典型的方法。他们都是基于特征的变形方法，也就是在变形之前先要在图像上选择特征，根据这些特征建立他们的对应关系，然后根据对应关系建立映射函数，最后图像上每个像素都根据这个映射函数进行变换。2.1交叉分解交叉分解就是用一个线性插值函数对两个不同图像的同一个位置上的像素的灰度值进行差值计算，其计算结果就是当前图像的对应位置的像素的灰度值。8 中国科学技术大学本科生毕业论文插值公式如下：s(t)kimage(t)(1k)image2(t)其中s(t)表示当前位置的变形图像的像素的灰度值，k是介于0和1之间的值，t表示当前的位置。交叉分解仅仅涉及到灰度值的插值，并没有用到位置信息以及几何变换。2.2网格扭曲网格扭曲最早是由D.Smythe在1988年的电影《Willow》中利用ILM提出的，它已经成功地用于运动中的图像。但此方法不能保证扭曲一一对应，当一个网格扭曲应用到一幅图像上时，变形图像有可能从自身折叠回来。2.3能量最小化方法针对网格扭曲的缺点，Lee等人提出了一种能量最小化方法[7]从而保证一对一的变形算法，也避免了折叠的产生，本方法允许用各种基元作为特征对，比如：点，线段，曲线等，这些基元被归类到一个集合中，然后根据这个集合产生1映射函数，这可以看做是一个直角平板的二维变形，这种方法同时也是C连续的，在这个变形方法中变形是受到能量的限制的，也就是要在能量最小的条件下进行，当能量最小时，其变形效果是很光滑的，但是由于其计算量太大，本方法没有得到足够的重视。2.4多层次自由变换方法[8]多层次自由变换方法(MFFD)同样由Lee提出，它比能量最小化方法简单，更2快，它穿过一个层次控制网格来产生一对一的而且是C连续的映射函数，在某些特殊情况下，多层次自由变形是用到了双立方B样条张量积的自由变形的延伸[9]，从位置限制中导出变形。2.5工作量最小化方法假如有两幅非常相似的图像，Brown给出了一种能自动在源图像和目标图像上建立像素点对应关系的图像配准方法[10]，例如光流常常被用于在压缩和数字视频处理中跟踪视频帧的帧对帧的运动[11]，这种方法只能适用于具有相同场景但成像上有微小位移并仅仅要恢复少量位移的情况，但是对于图像变形情况就完全不同了，因为参与图像变形的图像可能完全不同，虽然如此Cao和Sederberg还是提出了一种在相似图像中自动确定特征对的方法[12]，它很少或不需要人的干预，这种方法在指定特征对应关系上与朝最小量用户干预的趋势是一致的，这个方法是基于工作最小的趋势，这个趋势直接从图像米芾而不是用户指定的限度来产生工作量。被Wolberg为解决多边形形状混合问题而做的相关工作所激励，Serberg尝试将变形和重新着色的工作量最小化，利用双线性B样条区域格子，它们应用了层次变形并将功耗函数与之联系，即使在变形之后，强度和与着色相关联的功耗函数都会不同，这种方法所产生的变形本质上就是在所有可能的变形9 中国科学技术大学本科生毕业论文中选择能使功耗函数达到最小的变形，其实Wolberg已经提出了一种虽然不能保证功耗函数达到全局最小但比这个方法更简单，更快的变形算法。工作量最小化方法的前提是：大多数视觉愉悦的变形是与满足最小工作量限制条件的那些图像相关联，但是在很多情况下这个前提是得不到满足的，因此，在特征选择和初始化变形方面，少量的用户干预还是很有必要的。总之，这种方法的基本原理就是利用工作量最小化的限制，使用户的干预大大减少。这方面的工作虽然还处于早期研究阶段，但是对相似图像的变形所取得的效果还是比较令人满意的。下面我们将详细介绍几种常用的算法。§3图像变形的技术除了第一节介绍的散乱点插值，还有基于网格的变形算法。本文将着重介绍前者。对散乱点差值的变形方法，可以用数学的形式描述。我们可以把变形看成一个映射f，这个映射把原图的点映射到变形后的图上。对所有点应用这个映射就得到变形后的图像。此变形由控制点对引导，所以必须满足以下条件：（1）插值性：f(pi)=qi（2）光滑性：f能产生光滑的变形因此我们可以把这个图像变形问题看做数据的输入和输出：2输入：n对控制点(pi,qi),pi,qi∈R,i=1,2,………,n22输出：一个至少是连续的函数f:R→R,满足：f(pi)=qi,i=1,2,………,n下面将介绍三种常用的方法，来解决散乱点插值问题。3.1反距离加权插值法（IDW）对每个数i，有一个局部的插值被定义：f2i(p):R→R,满足：fi(pi)=yi，i=1,2,………,n插值函数是这些局部插值的加权平均[2]：nf(p)wi(pi)fi(pi)（1）i1w2i(pi):R→R,是权值函数其满足条件：nwi(p)1,wi(pi)1i1w(p)0,i1,2,,ni这些条件满足了插值的性质，Sheperd[3]提出了如下的权值函数：10 中国科学技术大学本科生毕业论文(p)iw(p)ini(p)i11(p)id(p,p)i此处d(p,pi)表示距离。插值的光滑性是由指数u决定的。u>1保证了导数的连续性，并且使得一阶导数在数据点为0.我们一般选择u=2.为了定义局部插值，利用所有别的控制点，加一个系数wij来削弱远距离点的影响。相应的误差方程为：n2Ei(f)wij(fj(pj)yj)j1,ji通过极小化Ei(f)就能得到局部插值，让wij=j(p)。上诉方法应用在图像变形中可得到：nf(p)wi(p)fi(p),fi(pi)qii1改写为：f(p)qD(pp)iiii满足：D22i(0)=0,Di:R→R作为一个线性变换，可由形式为（di，kl），k，l=1,2,2*2的矩阵表示，相应于一个线性变换D的误差方程如下：n2Ei(D)wij(qiDj(pjpi)qj)j1,ji极小化误差方程就能得到局部插值函数fi。此处介绍另外一种权值函数：(Rd(p,p))iii(p)Rd(p,p)ii此权值函数是由Franke和Nleson[4]提出的，此处x+=max（x，0），Ri是使用者自己确定的参数。正确地选取Ri的值，可以灵活地改变每个控制点对结果所造成的影响，此权值函数是对之前的权值函数的优化，但由于Ri的选取过于困难，本编文章主要采用第一个权值函数所产生的结果。3.2径向基函数法（RBF）另一种常见的方法是用一系列线性的基方程来构造插值函数，然后再决定这些基函数的系数：11 中国科学技术大学本科生毕业论文nf(p)aifi(d)pm(p)i1基函数fi的值只由数据点到控制点之间的距离决定，因此被称作径向基函数。pm(p)是一个次数为m的多项式，这样保证了多项式某一确定次数为m的精度。而系数ai的值则通过我们把数据值代回原方程解得。因此，插值函数的可微性直接依赖于基函数的可微性。介绍几种常用的基函数：2·细盘函数：fdlog(d),它一般用来拟合具有两个参数的平滑函数。22·高斯函数：fexp(d/c),它主要用于精神网格。1·超二次曲面函数：f(d2c2)2,这个基函数可以应用于多个方面，尤其适合于拟合地形学数据。对于含有三个残数的拟合函数，有以下两种基函数可以选择：·双调和样条+线性多项式。·立方调和样条+二次多项式。我们将主要应用超二次曲面函数来进行我们的实验。用径向基函数对离散数据插值本质上是要找到径向基函数中基函数前面的权值以及m阶多项式每一项前面的系数，如果用c=（cT1，……,cm）表示多项式的系数，a=（aT1,……,an）表示基函数系数，那么RBF的公式可以用矩阵的形式表示：APaf=TP0c0解线性系数方程就可以得到参数a和c，也就得到了具体的径向基函数表达式。上面这些多项式样条将指定的能量范数最小化，因此是最平滑的插值方法。3.3移动最小二乘法（MLS）用移动的最小二乘法来构造一个函数[5],满足插值特征。给图像中的一个点v，求得最好的仿射变换lv（x），使函数：n2wi(lv(pi)qi)i1得到最小化。权重wi形式为：1wi2a(pv)i因为在这最小二乘问题中，权重wi依赖于v的值，所以把它叫做移动中的最小12 中国科学技术大学本科生毕业论文二乘法，因此对每一个v有一个不同的变换lv（x）。lv（x）是仿射变换，那么它就有两个部分组成一个线性的变换矩阵M和一个平移矩阵T形如：l(x)xMTv矩阵M可以分为仿射变换，相似变换和刚性变换。§4保持图像内容的图像变形技术大多数图像处理技术都相同的对待全图内容，比如简单的一种变形：图像的缩放，所有的图像特征被扭曲，这对比较突出的几何物体等有很难看的效果。在最近几年中，保持图像内容的算法得到了较多的关注并得到较大的发展，介绍几种算法如下：4.1基于图像裁剪保特征算法保持图像的内容最为重要的是保持住图像中重要区域的特征。一个思路就是找出图像中的显著区域，对显著区域外的部分进行裁剪，这样就能在保持住图像显著性的同时完成图像缩放。这样就必须采用一定的方法来检测图像的重要区域。通常采用的方法有两种：一种是采用Voila等提出的人脸检测器的方法来寻找图像中的重要区域，另外一种方法是Itti等提出的构建图像显著图来实现图像重要区域的探测。Suh等利用上面方法来获取图像中的显著区域，提出了一种为图像创建缩略图的方法。Santella等则是根据人眼聚焦的位置利用前面提到的技术能够智能裁剪图像，得到用户想要的裁剪结果。这两种方法要依赖原有的图像裁剪技术。Liu和Gleiche利用Suh等文中的方法找到感兴趣区域，提出了一个非线性的鱼眼变形函数来保持住感兴趣区域，同时这个函数对图像的其他部分变形程度也不是十分严重。这样当用户指定缩放后要得到的图像的尺寸就可以用上诉方法实现。但是图像中感兴趣的区域若是多于一个，算法结果不是很稳定。Wolf等综合了Voila和Jones提出的人脸探测和图像梯度的信息去检测图像中的重要区域，其方法对于重要区域的变形较小而其余区域的变形较大。4.2特征相关的变形Gal等提出一个保持特征的算法，对由一个特征标注图引导的非均匀二维纹理映射提出一个方法，这个方法保护图形的一些区域，比如一个前景物体，或别的突出部分，这种方法能通过约束它的相似变换扭曲一个图像而保持它的特征的形状。这个纹理映射方法是基于网格的，它根据用户的指定变形一个图像同时又保护标注的区域。特征标注图由用户简单选择。这样图像变形的结果就是标注的地方单独经历一个相似变换，而图像别的区域变形更多作为代价。这个工作同Balmelli等和Sander等的纹理最优技术有关。13 中国科学技术大学本科生毕业论文4.3图像缩放的保特征算法现在图像的便携式显示设备越来越流行，比如手机，便携式电脑等等。这些显示设备的纵宽比是不一致的，如何让图像在不同设备上显示，并且显示的效果好，这变得越来越重要，也引得人们的关注和研究，主要有以下几种算法：基于线裁剪的保持图像内容缩放方法，图像缩放优化方法。下图为基于线裁剪的保持图像内容缩放方法的一个例子。图4.3保特征算法所得图片在图4.3中我们可以观察到，小孩与花在图像缩放中被完整地保持了下来。§5本章小结本章从图像变形问题的提出，再谈及图像变形问题的发展，最后论述到其本质——散乱点的插值问题，介绍了几种图像变形方法，反距离加权插值法，径向基函数法和移动最小二乘变形方法。在本章后部分，介绍了几种保持图像特征的变形方法。接下来我们将应用这几种变形方法，根据其结果更加深入地理解这几种算法，以找到优化它们的方法。14 中国科学技术大学本科生毕业论文第三章图像变形方法分析比较§1反距离加权插值法(IDW)分析图1.1是待变形图像，我们的预期是让图像中的人物嘴角上扬。首先我们先选取四个固定点，固定图像位置，然后我们图1.1原图图1.2IDW法所得图像把两个嘴角向上拉。运行程序之后得到图1.2，虽然大体上满足我们的要求，但仍能找出一些不足。首先图像上出现白斑，这是由于像素点均为整值，所以当我们对计算所得到的结果进行取整时，有很多像素点没有得到赋值造成的，既此映射非一一映射。此外，我们可以发现图像的一些边界并不是十分光滑，比如脸的轮廓，变形很大，而且有一些棱角存在。通过分析算法，我们可以发现，这主要是由各控制点之间过渡地不均匀造成的，从而产生了很多节点，这在脸的边界上十分明显，从而导致脸的轮廓不光滑，尤其在控制点集中地下巴处。想解决这个问题我们就需要改变权函数，既由Franke和Nleson提出的：(Rd(p,p))iii(p)Rd(p,p)ii此权函数可以根据控制点与像素点之间的距离灵活调整权值大小，从而得到令我们满意的效果。另一个制约IDW方法发展的是其时间复杂度O(nN)，这导致其运行起来非常缓慢。15 中国科学技术大学本科生毕业论文§2径向基函数法(RBF)分析图2.1RBF法所得图像与之前想法相同，我们还是选取四个固定点，两个变化点。图2.1为应用RBF算法后的图像。但同样对于每一个点的变化RBF方法需要把所有的控制点考虑进来。因此，其复杂度也是O(nN)。§3两种方法的比较3.1图像边界问题除了上面已经提及的一些不同，这两种方法在图像边界上也存在着显著的区别。我们再来看一组图片：图2.2图2.3图2.4原图IDW法所得图像RBF法所得图像图2.2为原图，图2.3为运行IDW方法得到的图片，图2.4为运行RBF方法得到的图片。从这三张图中我们可以清晰地发现：IDW方法会使图像边界发生明显变化，产生许多我们不想要的扭曲，而这在RBF方法中是不存在的。问题产生16 中国科学技术大学本科生毕业论文的原因显然与我们上面论述的一致，此处不再详细说明。3.2时间复杂度的比较在上面论述中我们已经知道，无论是反距离加权插值法，还是径向基函数法，其时间复杂度均为O(nN)。但在实际运行中，两种方法在运行时间上却存在着显著的差异。我们通过对比试验来比较两者在运行时间上的不同。本次试验我们采用的是一张256*256的图像，既图2.2。分别选取1对到5对控制点（均为变化点），所得结果如下。时间IDWRBF1对78622对1241093对1721254对1871405对234187表1通过表1我们可以发现，RBF法所需时间在整体上小于IDW，而且随着点对的增加，这种差距在逐渐变大。其原因主要在于，IDW法需要计算方根，既d(p,p2i)。而RBF法计算的是d，所以不需要计算方根，从而节约了时间。根据以上的分析我们可以得出一些加快运算速度的方法。一种方法就是通过删除一些节点，然后通过双线性法生成这些节点，以达到减少节点数目来加快运算时间。另外我们可以通过优化某些细节来加快运行速度。比如我们用扫描线算法来计算位移，那么对于所有像素点进行的操作将相同，从而减少运行时间。§4本章小结在本章中，我们具体地实现了反距离加权插值法以及径向基函数法。并对其结果进行了分析与比较。针对其产生的问题进行了分析，并得到了解决办法。然后我们详细地比较了它们在运行时间上的不同，我们发现RBF法在此方面具有优势。最后我们根据问题产生的原因，给出了几个加快运行速度的方案。17 中国科学技术大学本科生毕业论文第四章结论与展望在计算机动画和一些想得到特别的图像效果方面，图像变形有着广泛的应用。为了得到较好的视觉效果，近年来各种图像变形方法引起了大家的注意。本文总结了当前的一些变形方法，并对其做了分析比较，本文主要的工作总结如下：1.概述了图像处理的主要内容以及图像处理的应用范围。由图像变形问题的提出，再到其发展，综述了几种变形方法。从离散数学插值方法的函数特征，得到图像变形问题的公式化，介绍了几种常见方法，反距离加权插值法，径向基函数法和移动最小二乘法。研究了几种保持图像特征的算法思想，有线裁剪算法，以及在其基础上的一些改进算法，并对其进行了展示。2.针对反距离加权插值法和径向基函数法做了详细的分析，对其出现的一些的问题，比如：白斑的产生，边界的不光滑性，做了详细地阐述，系统地分析了这些问题产生的原因。然后对这两种方法进行了比较，着重比较了它们在时间复杂度上的不同，由于IDW法需要计算方根，这使其在运算时间上明显长于RBF法。最后针对产生的问题，提出了几种改良的办法。本文的研究工作得到了一定的效果，但仍然存在不足。对于反距离加权插法，其权值的确定应该是个性化的，但由于经验不足，我们无法给出最理想化的权值函数。因此需要进一步探索，从而得到更好的图像效果。18 中国科学技术大学本科生毕业论文参考文献[1]R.C.GonzalezandR.E.Woods，Imagewarping,2003[2]D.RuprechtandH.Muller,Imagewarpingwithscattereddatainterpolationmethods,IEEEComputerGraphicsandApplication,March1995,15(2):37-43[3]D.Shepard,“ATwo-DimensionalInterpolationFunctionforIrregularSpacedData”,1968,ACMPress,NewYork,pp,517-524[4]R.FrankeandG.Nieson,“SmoothInterpolationofLargeSetsofScatteredData”,1980[5]S.Schaefer,T.Mcphail,andJ.Warren,Imagedeformationusingmovingleastsquares,ACMTransactiononGraphics,2006,25(3):533-540[6]SmytheDB,Atwo-passmeshwarpingalgorithmforobjectgransformationandimageinterpolation,Technicalreport1030,ILMComputerGraphicsDepartment,Lucasfilm,SanRafael,Calif[7]LeeS,ChwaK-Y,ShinSY,WolbergG(1995),Imagemetamorphosisusingsnakeandfree-formdeformations,ComputGraph,pp439-448[8]LeeS,ChwaK-Y,HahnJ,ShinSY(1996),Imagemorphingusingdeformationtechniques,VisualizationComputAnim7:3-23[9]SederbergTW,PartySR(1986),Free-formdeformationofsolidgeometricmodels,ComputGraph20:151-160[10]BrownLG(1992),Asurveyofimageregistrationtechniques,ACMComputsurveys24:325-376[11]TekalpAM(1995),Digitalvideoprocessing,PrenticeHallPTR,UpperSaddleRiver,NJ[12]Gaop,SederbergTW(1998),Aworkminimizationapproachtoimagemorphing,VisualComput[13]L.Wolf,M.Guttmann,andD.Cohen-Or,Non-homogeneouscontent-drivenvideo-retargeting,ProceedingsoftheEleventhIEEEInternationalConferfnceonComputerVision,2007[14]P.ViolaandM.Jones,Rapidobjectdetectionusingaboostedcascadeofsimplefeatures,IEEEComputerSocietyConferenceonComputerVisionandPatternRecognition,2001,1:511-518.[15]L.Itti,C.Koch,andE.Neibur,Amodelofsaliency-basedvisualattentionforrapidsceneAnalysis,IEEETransactionsPatternAnalysisandMachineIntelligence,1998,20(11):1254-1259.[16]B.Suh,H.Ling,andB.Benjamin,Automaticthumbnailcroppinganditseffectiveness,Proceedingsofthe16thAnnualACWSymposiumonUserInterfaceSoftwareandTechnology,2003,95-104.[17]A.Santella,M.Agrawala,andD.DeCarlo,Gaze-basedinteractionforsemi-automaticphotocropping,InACMHumanFactorsinComputingSystems(CHI),2006,771-780.[18]F.LiuandM.Gleicher,Automaticimageretargetingwithfisheye-viewwarping,InACMUIST,2005,153-162.19 中国科学技术大学本科生毕业论文[19]S.Cho,H.Choi,Y.Matsushita,andS.Lee,Imageretargetingusingimportancediffusion,IEEEInternationalConferenceonImageProcessing(ICIP),2009,977-980.[20]R.Gal,O.Sorkine,andD.Cohen-Or,Feature-awaretexturing,EurographiceSymposiumonRendering,June2006,297-303.[21]L.Balmelli,G.Taubin,andF.Bernardini,Space-optimizedtexturemaps,ComputerGraphicsForum,2002,21(3):411-420.20'