基于迭代近点算法的地图拼接方法研究

基于迭代近点算法的地图拼接基于迭代最近点算法的地图拼接方法研究毕业设计（论文）原创性声明和使用授权说明原创性声明而使用过的材料。对本研究提供过帮助和做出过贡献的个人或集体，使用授权说明本人完全了解大学关于收集、保存、使用毕业设计（论本学位论文作者完全了解学校有关保留、使用学位论文的规定，同意学校保留并向国家有关部门或机构送交论文的复印件和电子版，允许论文被查阅和借阅。本人授权大学可以将本学位2、学生掌握专业知识、技能的扎实程度4、研究方法的科学性；技术线路的可行性；设计方案的合理性二、论文（设计）质量三、论文（设计）水平1、论文（设计）的理论意义或对解决实际问题的指导意义年二、论文（设计）水平1、论文（设计）的理论意义或对解决实际问题的指导意义教研室（或答辩小组）及教学系意见2、对答辩问题的反应、理解、表达情况二、论文（设计）质量）？三、论文（设计）水平1、论文（设计）的理论意义或对解决实际问题的指导意义：（2刚体迭代最近点算法2.2迭代最近点算法2.3实验结果与分析2.4本章小结3基于迭代最近点的部分配准算法3.1刚体部分配准问题3.2部分对应的迭代最近点算法3.3实验结果与分析3.4本章小结4基于迭代最近点的地图拼接方法4.1地图拼接问题4.3实验结果与分析5结论与展望二十世纪以来，图像配准已逐渐成为图像处因此图像点集配准是一项基础且非常重要的研1.1研究背景和意义所谓图像配准就是将不同传感器不同时间、配就是在一幅比较大的图像中搜寻与目标图像法。目前，在最为传统的ICP算法的基础上已经发展出了许多处理各种不同种类数据和问题的像之间具有较为明显的错位。为了配准这类图像，可以采用空域的方法来去除这些差别.域中产生细微差别，例如透视变形.或者其他景物的变化而引起的.第二类和第三类图像之间差别并不是能够直接特征空间指的是从图像中提取出来的用来匹度测量则决定了每一个配准测试中的相关特性.间以及搜索策略等的选择都会影响到最后配准的各种各样的配准方法的特点以及其之间的关在较为简单二维图像配准过程中，图像特征算法策略来计算这些几何特征（通常是两个点问题归根到底可归结到二维点集配准这个更为将多个深度图像数据配准后建立三维的几何模型并进行后期处理已经成为当前一由上，图像配准技术在二维或者三维图像处图像配准的应用领域概括起来主要有如下4个方CT,MRI,PET图像结构信息融合，数字剪辑血管（3）模式识别：目标物运动跟踪，序列图像图像配准技术在很多领域都有着广泛的应1.2国内外研究现状点集配准问题最初产生于计算机视觉，计算配准问题则是其他非刚体配准问题研究的基础图像点集刚体配准技术最早出现在上世纪70终科学家们在潘兴2式中程导弹及战斧式巡航导导弹命中率上至高的一个飞跃。进入八十年代研究深入到了更为广大的领域，如遥感图像处而更为抽象统一的图像点集配准技术理论并未计算互相关相似度量进行图像检测技算的图像的互相关技术进行了全面的研究；M.Svedlow等对图像配准的相似性度量和预处理方法进行了动态程序设计方法用于几何畸变较大的图像配在二十世纪八十年代初期，当时图像配准问题的研究方向主要为最基本的全局刚体配准算集特征而直接进行配准的图像配准方法被广泛一种不需要提取图像特征就可以完成三维曲线复杂的曲面上图像（如地形数据或者人脸数据直到二十世纪九十年代初，图像配准领域中大名鼎鼎的刚体迭代最近点算，英文Iterative它理所当然的成为了众多领域为人所熟知的图大量学者从收敛速度和收敛性方面对ICP算法对更为复杂现实情景中图像配准的变种ICP算法被提出。这其中的例子数不胜数，例如，Fitzgibbon采用Levenberg-Marquardt算法加快析了ICP算法的收敛速度问题，证明了刚体配准部分对应点集的配准问题还是一个难点热点问相对国外，在国内图像配准技术起步相对较一种将遗传算法（GeneticAlgorithm,简称GA）但实际上它是一种使用互相关函数作为相似性遗传算法和最小二乘算法结合用于图像的子像在部分对应点集配准问题被提出后很长一段分配准算法大多数都是以经典的ICP算法为基础，然后通过引入现代科学的优化策略来实现声干扰下产生了较大量的离群点，不稳定几何所谓几何方法，是指采用几何约束条件来排除点集配准中的噪声点和大量无信息点对的方性的点集提取方法，从而提高ICP算法的几何稳YonghuaiLiu通过分析刚体移动的特性，引入几何约束条件来去除ICP算法中错误的匹配刚体移动的几何规律与点集最邻近约束条件相结合，通过选择正确的匹配点对，再次提CP通过建立概率模型来约束配准过程，进而提高算法的鲁棒性也是一类常见的方法。Zinßer准方差，迭代过程中排除距离大于该方差的点HaitaoZhang通过提取深度图像信息，运用矩阵同时考虑到传感器噪音和待匹配目标位置率的方法配准含形状噪声的点集具有较强的鲁采用阈值度量方法在迭代过程中排除异常点的干扰，从而提高点集匹配的精度。EmanueleTrucco在ICP算法中引入线性回归的和中值最另外一些学者采用由粗到精的策略来提高缺匹配，然后进一步细化，完成精匹配。在上面介绍到的所有用于解决点集刚体部分1.3本文研究内容及组织结构点集刚体配准作为图像配准的一项基础而关百分比为基础的刚体部分配准算法应用到了二2）给出基于迭代最近点的部分配准算法在地体部分迭代最尽点算法刚好可以应用这个问题像点集配准的研究背景和意义，然后对点集配准问题进行描述并且分析其难点，接着介绍点集配准的研究现状，最本章首先给出了点集配准的概念，然后在此概念上阐述了刚体变换和相似性度量，接着给出了刚体配准的数学模型和流程框图。在此基础上，本章详细的阐最近点算法，并给出了该算法流程和每进行了细微详尽的分析。本章最后还展示了应用刚体迭代最近点算法，在matlab上配准两幅简单线条的黑白图片的实验结果，并对实验结果进行了初配准算法。本章首先提出了具有部分数据丢失的点集部分配准问题，然后建立本章详细的阐述了一种采用重叠百分比决点集部分配准问题。阐述过程中并给出了该算法的简要流程和具体步骤，以及每一步中要求解的数学表达式，更深一步的本文还对算法进行了理论上层次较高的算法分析。最后实验结果和分析是在二维刚体情景中进行的，对不同图像情景在配准算法参数和循环次数已经配准时间上进行了列表展示和分析比对全文进行总结，并对下一步的工作进2刚体迭代最近点算法刚体配准是图像配准问题中一类最为基础和刚体配准问题的理解在本文后面的工作中至关处理的各个领域中抽象出来的一类重要的基础个图像点集中的每个点与另一个图像点集中的就是要确定如何来度量或者说Euclidean距离，本文后面仅简要阐述了一下给定Rm维空间中的形状点集S和模型点集M，假设存在任意两点xS和yM，那么刚体变换的数点到点的距离又称为2范数距离，它表示Rmii来定义空间中点对的距离。以点到点的S--形状点集M--模型点集优的空间变换T和确定形状点集到模型点集的2.2迭代最近点算法算法最早是由Besl和McKay于1992年提出来的模型点集中的点能够在Euclidean欧式距离空间采用了上述阐述到的最小平方（LeastSquare，2R,t,cic(i)TR刚体配准问题实际上是求使满足上式的R，t和从图2-2可以看出，经典的ICP算法首先由人值要求应当粗略正确。然后ICP算法正如它的名关系最终以求达到最优的配准效果。那ICP算法是如何改进每步迭代中的变换量和对应量的形状点集和模型点集间每个点的对应关系2k3）更新第k步的变换R和t：*t止迭代而退出呢？这就涉及到如何判定图像点式是总体上形状点集中点和模型点集中对应点kk可能性是不可能使配准误差ε达到它理论上的最取均方误差达到设定范围下限和迭代步骤达到代。当ICP算法循环退出后，那么返回得到最2.2.2算法求解法则更适合于低维点集的点搜索。鉴于简单起见，本文采用的是Delaunay三角化。对第二步求解，有SVD(奇异值分解，SingularValue如何把一个散点集合剖分成不均匀的三角形维)空间中任意分布的散乱点用直线段连接起角形(四面体)集，每个三角形(四面体)的顶点即认的具有最好几何拓扑性质的剖分就是符合Delaunay满足两个基本准则，其一是空圆特性，即在性，即在散点集可能形成的三角剖分中，大。局部变换法和Watson算法是离散点集kkM进行略找到形状点集S在模型点集M中的对应点。该搜索策略大幅度提高了点集对应关系求解的速定理（1给定任意两个m维对应点集{q}N和{n}NΣn-1Σiii=1NiNikkNc(i)NiiiNiic(i)Nc(i)iiiiii2.2.4实验结果nTRqiii=1图a-1模型图像a-1模型图像图b-1模型图像图b-2待配准图像图上面所示的实验结果图中，因为为了简单起见均采用的是黑白图，而且仅仅是提取了图片中图像物体的外部轮廓线条特征来作配准的标准。其中模型图像和待配准图像之间仅仅是一个旋转和平移的效果，并涉及其它复杂的图像变换，这也正是刚体变换所需要的前提。在配准结果图中，需要说明的是红色线是待配2.4本章小结本章首先提出了图像点集配准问题的概念，了在众多的刚体配准研究中最为瞩目的由Besl和Mckay提出的ICP算法，并且详尽地论述了3基于迭代最近点的部分配准算法了它的数学模型，且给出求解ICP刚体配准问在假设两个待配准点集中所有点都是有其相对器噪声等因素所造成的点集部分数据丢失或存相对传统的ICP算法新增了重叠百分比这个变3.1刚体部分配准问题在模型点集M中找到与之相对应的点，即假定了点集P中仅有部分点能够在点集M找到相对应的且很可能P中能找到对应点的点集是非常小的一部分。在这种情况下，传统的ICP算法就无法如果按照点集对应关系来分类，则通常认为点集中部分数据丢失或点集中含有大量离群点不同，或者两次采集图像时障碍物遮挡情况不一，再或者是采集设备自身缺陷等原因而造成且这些非对应点存在方式跟外界环境和对象物于外界环境的干扰和采集设备本身的限制产生部分配准在本文中将不会再被提及和探讨。绿色和天蓝色分别表示两个点集中多余或者缺形状点集中的绿色部分在模型点集中无法找到如何解决上述具有部分数据缺失的点集配准问题呢？大家都会想到的很简单的考虑是先要但具体到如何有效排除点集中的非对应点集部文绪论中范范而谈了几种处理部分对应点集的而我们面对的情况是未知待配准点集图像形状和未知噪声概率分布函数这一更为严峻的情景，3.1.2模型建立r如何确定两个点集之间重叠百分比是建立具r有部分数据缺失的点集刚体部分配准数学模型rrrrrr点集中能够建立对应关系的点个数此时极少故r优的值，所谓最优的重叠百分比，是指在该百r中那部分能够建立对应的点集能够最佳的与模型点集中相对应的部分点集能够在几何空间上r缺失数据点集配准误差与重叠百分比关系缺失数据点集配准误差与重叠百分比关系20864200.550.60.650.70.750.80.850.90.951重叠百分比差0.5配准算法相比较，因为传统ICP配准算法假设了形状点集和模型点集间具有完该百分比ג能尽可能多地包括两个点集中能够相2）重叠百分比很大。点集之间能够作对应点个r用的点集信息很大。但是如果重叠百分比取值r应的点的问题，而这些异常点会提供错误的信综上述，最优的重叠百分比r应该是两矛盾r使得点集配准在误差取得极小值的情况下又尽也达到最佳，而不是前面分析的在误差突变时设表示两个点集的重叠百分比，r表示形状点r2λrλic(i)2TRλe[λ,λ],re[0.5,1]rr点集配准均方误差:2ic(i)2ir惩罚函数:sirλrλMSE(r)MSE(r)最小值点所对应得到的重叠百分比就是要求解864200.50.550.60.650.70.750.80.850.90.951重叠百分比误差惩罚函数差误该算法在每步迭代中除了要计算求解点集的对r。算法开始的第一步，假设形状点集和模型点集是完全重叠的，即令r=1，调控参数λ=λ。然后以后每步迭代中调控参数λ从λ递减到于第n步的λ,在迭代过程中最ma小x化目标min函数 (r,λ)，计算出该步最优的刚体变换R和t，然后赋值传递给第n+1步。算法的内循环迭代流程类似1)根据(k1)步的刚体变换(R,t)，计算点集S和M2)求目标函数(r,λ)2sje{1,2,,N}s的最小值的过程中确定第步kkirmkckλrλ)(i)2Ns{m}NskkSS4)通过求关于子集第k步的空间变换krkrrirmkck(i)2S度量函数的最小化值计算krk2RTR=I,det(R)=1,tseS5）更新R和t:*R*t配准过程中，只有当取值能够搜索出最优λ的裁剪度时，才能计算出准确的刚体变换，这r(r,λ)会随着λ的减小而增大。配准循环结束后，算法让λ从λ开始往递增方向搜索，因为在稳定min状态（配准结果正确）下(r,λ)是递减的，因此第一个使目标函数(r,λ)递增的λ*就是待求的最优参数。该点对应的Ψ(r,λ*)是最优的目标函数，而其对应的裁剪度r*和刚体变换也是最优的配准结3.3实验结果分析为了验证带重叠百分比的点集部分配准算法配准的实验误差采用的是均方根（RootMeanSquare，RMS）误差度量。本文中所有的代码百分比的点集部分配准算法对于这类简单的黑针对具有部分数据缺失这一类点集部分配准问题，本章在传统经典的ICP算法基础上，提出了一种在目标函数中引入重叠百分比r和惩罚函数两个量的作用而产生的一种新ICP变种处理具有缺失数据点集配准问题的可行性。然点集配准实验进一步验证了算法的正确性和精5总结与展望题分别进行了描述和提出了一种高效的变种ICP虽然本文对图像点集配准算法做了一些研究山一角。还有更多的图像配准问题并没有涉及1）详尽阐述了ICP算法的基本思想和原理，这因为本文提出的算法正是基于经典ICP算法的2）提出了用于解决因部分数据丢失情况下刚体ICP算法。该算法目前是最好的用于解决此类配3）将算法成功的应用到地图拼接中，并获得的虽然本文刚体配准的一般模型，经典ICP算法和带重叠百分比的部分点ICP算法进行探讨，1）本文提出的目标函数及算法都采用的是基于2）目前，本文提出带重叠百分比的部分点ICP附：论文翻译在当被称为相对姿态的初始估计是知道的情况型的几何对准.阶段从点的选择和匹配方面着手以求达到最小出了它们按照正确路径收敛的速度.inscribedsugaces，我们引入一个新的基于均我们最终提出一种结合了其它变种ICP算法而具有高收敛速度的算法.我们将展示一个能够在几十毫秒范围内配准两好的.典型是那种一次只能从一个方向扫描物体的扫位置，识别和索引表面特征[Faugeras86，斯图像”表面签名[约翰逊97A]，计算主轴扫描全方位定位问题[Bergevin96，斯图达特96，1.在一幅或两幅网格图像中选择其中部分点4.排斥某些点对，在单独寻找每对点对或考虑在本文中,我们将着眼于这六类中的每个变种，这种实时ICP算法的可用性可能使大量的新应用在基于模型的跟踪和三维扫描方面产生。将作为我们基准选择的算法是实质上是[普莉来源有一个正常的其他网正常。在生产环境已得到广泛使用Levoy00]，对含有％；2％.所有我们使用的网格都是简单视角范围内的“最近点”和“投影点”变种之间的比较（见曲面的法线计算只是基于四个近邻范围内的选择会影响quantitative，而不是定性的，我“切平面”现场（图IC由在一个“X”形状虽然这些场面肯定不涵盖所有可能的扫描对象例如，数字米开朗基罗项目[Levoy00]涉及表面扫描含有低频特性（例如，线条流畅雕像分我们使用综合数据进行比较的动机是使我们知用度量是两个网格中对应点的实际距离的最小虽然一个单一的运行结果显然不能被视为一个了典型的捕捉了在各种场景中具有显着性能差变种，并在我们的测试场景中比较了他们的性我们首先通过检查点对的选择对ICP的收敛性始终使用所有可用点[Besl92]。可用点均匀子采样[TurkS94]。随机抽样（每步迭代中选择不同的点样本）在使用颜色或强度以帮助配准的变种算法中,选择具有高强度梯度的点[Weik97]。上述方案中的每个都可以选择只从一幅网格中选择点，也可以选择从两个网格中选择源点这一战略动机为了是观察某些类型的场景下的程中尽可能是均匀样品.普通空间采样是一个用表面特性配准的非常简统基于特征的方法具有较低的鲁棒性[Faugeras86，Stein92,Johnson97a]。的六个部分之中的三个起到作用（一个平面内的两个translations，一个旋转）完全（图6尤其是在迭代阶段早期当两个网格仍我们将研究ICP的下一阶段是如何寻找点与点查找从源点出发朝向具有目标表面的源点法距离度量标准[Benjemaa97]，点到线的距离[Dorai98]，或强度相容性[Weik97]或颜色和法线间角度[Pulli99]的相容性指标已被探），首先，让我们先来看看对“fract