基于迭代最近点算法的地图拼接方法研究毕业论文.doc

基于迭代最近点算法的地图拼接方法研究毕业设计（论文）原创性声明和使用授权说明原创性声明本人郑重承诺：所呈交的毕业设计（论文），是我个人在指导教师的指导下进行的研究工作及取得的成果。尽我所知，除文中特别加以标注和致谢的地方外，不包含其他人或组织已经发表或公布过的研究成果，也不包含我为获得 及其它教育机构的学位或学历而使用过的材料。对本研究提供过帮助和做出过贡献的个人或集体，均已在文中作了明确的说明并表示了谢意。作 者 签 名： 日 期： 指导教师签名： 日期： 使用授权说明本人完全了解 大学关于收集、保存、使用毕业设计（论文）的规定，即：按照学校要求提交毕业设计（论文）的印刷本和电子版本；学校有权保存毕业设计（论文）的印刷本和电子版，并提供目录检索与阅览服务；学校可以采用影印、缩印、数字化或其它复制手段保存论文；在不以赢利为目的前提下，学校可以公布论文的部分或全部内容。作者签名： 日 期： 学位论文原创性声明本人郑重声明：所呈交的论文是本人在导师的指导下独立进行研究所取得的研究成果。除了文中特别加以标注引用的内容外，本论文不包含任何其他个人或集体已经发表或撰写的成果作品。对本文的研究做出重要贡献的个人和集体，均已在文中以明确方式标明。本人完全意识到本声明的法律后果由本人承担。作者签名： 日期： 年 月 日学位论文版权使用授权书本学位论文作者完全了解学校有关保留、使用学位论文的规定，同意学校保留并向国家有关部门或机构送交论文的复印件和电子版，允许论文被查阅和借阅。本人授权 大学可以将本学位论文的全部或部分内容编入有关数据库进行检索，可以采用影印、缩印或扫描等复制手段保存和汇编本学位论文。涉密论文按学校规定处理。作者签名：日期： 年 月 日导师签名： 日期： 年 月 日指导教师评阅书指导教师评价：一、撰写（设计）过程1、学生在论文（设计）过程中的治学态度、工作精神 优 良 中 及格 不及格2、学生掌握专业知识、技能的扎实程度 优 良 中 及格 不及格3、学生综合运用所学知识和专业技能分析和解决问题的能力 优 良 中 及格 不及格4、研究方法的科学性；技术线路的可行性；设计方案的合理性 优 良 中 及格 不及格5、完成毕业论文（设计）期间的出勤情况 优 良 中 及格 不及格二、论文（设计）质量1、论文（设计）的整体结构是否符合撰写规范？ 优 良 中 及格 不及格2、是否完成指定的论文（设计）任务（包括装订及附件）？ 优 良 中 及格 不及格三、论文（设计）水平1、论文（设计）的理论意义或对解决实际问题的指导意义 优 良 中 及格 不及格2、论文的观念是否有新意？设计是否有创意？ 优 良 中 及格 不及格3、论文（设计说明书）所体现的整体水平 优 良 中 及格 不及格建议成绩： 优 良 中 及格 不及格（在所选等级前的内画“”）指导教师： （签名） 单位： （盖章）年 月 日评阅教师评阅书评阅教师评价：一、论文（设计）质量1、论文（设计）的整体结构是否符合撰写规范？ 优 良 中 及格 不及格2、是否完成指定的论文（设计）任务（包括装订及附件）？ 优 良 中 及格 不及格二、论文（设计）水平1、论文（设计）的理论意义或对解决实际问题的指导意义 优 良 中 及格 不及格2、论文的观念是否有新意？设计是否有创意？ 优 良 中 及格 不及格3、论文（设计说明书）所体现的整体水平 优 良 中 及格 不及格建议成绩： 优 良 中 及格 不及格（在所选等级前的内画“”）评阅教师： （签名） 单位： （盖章）年 月 日教研室（或答辩小组）及教学系意见教研室（或答辩小组）评价：一、答辩过程1、毕业论文（设计）的基本要点和见解的叙述情况 优 良 中 及格 不及格2、对答辩问题的反应、理解、表达情况 优 良 中 及格 不及格3、学生答辩过程中的精神状态 优 良 中 及格 不及格二、论文（设计）质量1、论文（设计）的整体结构是否符合撰写规范？ 优 良 中 及格 不及格2、是否完成指定的论文（设计）任务（包括装订及附件）？ 优 良 中 及格 不及格三、论文（设计）水平1、论文（设计）的理论意义或对解决实际问题的指导意义 优 良 中 及格 不及格2、论文的观念是否有新意？设计是否有创意？ 优 良 中 及格 不及格3、论文（设计说明书）所体现的整体水平 优 良 中 及格 不及格评定成绩： 优 良 中 及格 不及格（在所选等级前的内画“”）教研室主任（或答辩小组组长）： （签名）年 月 日教学系意见：系主任： （签名）年 月 日1 绪论1.1 研究背景和意义1.2 国内外研究现状1.3本文研究内容及组织结构2 刚体迭代最近点算法2.1 刚体配准问题2.2 迭代最近点算法2.3 实验结果与分析2.4 本章小结3 基于迭代最近点的部分配准算法3.1 刚体部分配准问题3.2 部分对应的迭代最近点算法3.3 实验结果与分析3.4 本章小结4 基于迭代最近点的地图拼接方法4.1 地图拼接问题4.2 基于icp的地图拼接方法4.3 实验结果与分析4.4 本章小结5 结论与展望5.1 结论5.2 展望1 绪论二十世纪以来，图像配准已逐渐成为图像处理，计算机视觉和计算机图形学等领域的研究重点和难点之一。点特征作为图像最为简单和常用的特征形式，被广泛地应用于图像配准过程中，因此图像点集配准是一项基础且非常重要的研究课题。所谓“图像点集配准”，就是寻求两个图像点集之间的一种几何变换，使得变换后的两幅图像点集在空间位置上达到一致。本文从介绍刚体配准问题出发，着重阐述基于迭代最近点算法的刚体部分配准问题，最后将此算法应用到地图拼接实例中。1.1研究背景和意义所谓图像配准就是将不同传感器不同时间、或不同气候、亮度、摄像角度下获取的两幅或多幅网格图像进行匹配，以求达到几何空间上一致的过程。如今，图像配准技术已经被广泛地应用于各个领域，较为常见的领域有：计算机视觉、图像处理、遥感数据分析等。而传统意义上的匹配就是在一幅比较大的图像中搜寻与目标图像相同的部分，在已知该图中具有要找的目标图像的情况下。通过某种算法策略就可以在图中找到目标图像，确定其空间位置。利用较为简单和成熟的模板匹配可以在一幅图像中找到目标图像，例如抓拍到的一张射门的照片，而要在该照片中找到足球的位置，这时就可以采用模板匹配的方法。目前，在最为传统的icp算法的基础上已经发展出了许多处理各种不同种类数据和问题的变种算法，大概上按照图像分类的不同，图像配准问题可分为三类：第一类：获取图像时间和位置不一致，造成图像之间具有较为明显的错位。为了配准这类图像，可以采用空域的方法来去除这些差别.第二类：获取图像环境条件的不同，这主要是由于光照或者天气条件不同而造成的差别，这样图像在亮度或局部上有所区别，但也有可能在空域中产生细微差别，例如透视变形.第三类：图像的差别是由于目标的运动，生长或者其他景物的变化而引起的.第二类和第三类图像之间差别并不是能够直接通过图像配准可以完全消除的，所以这给图像配准带来了极大的挑战。.对于通常意义上图像配准技术，我么可以简单地把它总结为以下4点选择的组合体：特征空间搜索空间搜索策略相似度测量特征空间指的是从图像中提取出来的用来匹配的信息；搜索空间则是指用来校准图像的图像变换集；搜索策略决定如何在这个空间中选择下一个变换，如何测试并搜索出最优的变换；相似度测量则决定了每一个配准测试中的相关特性.在图像配准中，特征空间、相似度测量、搜索空间以及搜索策略等的选择都会影响到最后配准的精确度。所有的图像配准方法都可以认为是这些选择的组合，这个框架对于我们理解现在存在的各种各样的配准方法的特点以及其之间的关系是相当有用的。在较为简单二维图像配准过程中，图像特征一般被表示成点或线等几何特征，然后通过某个算法策略来计算这些几何特征（通常是两个点集）之间最优的空间变换，从而使得图像能在空间几何上对应起来，这就达到了最终的配准。因此，如何提取图像特征和如何匹配这些特征是二维图像中，进行配准的两个关键前提技术。图像特征地提取在过去的几十年已经发展非常成熟，而最常用的特征提取方式是物体的边缘轮廓，角点，曲面交线，曲率不连续点等，在所有这些特征中，点是最为基础的，它同时也是曲线，曲面，立体等复杂特征的表示基础。因此二维图像配准问题归根到底可归结到二维点集配准这个更为简单直接明了的问题了，它是图像处理中最为基础的一个问题。对于三维图像配准问题，现在已经是如火如荼。近年来伴随着逆向工程技术和三维扫描技术的飞速发展，三维图像配准问题已是一个不得不妥善解决的难题。如今的三维扫描技术已经相当发达，它可以深入到任何复杂的现场环境中进行扫描工作，然后直接将扫描得到的各种大型的、复杂的、不规则、非标准实景三维数据完整无误的存入到电脑中，进而快速重构出目标物体的三维模型。与此同时，三维扫描仪所扫描的三维数据或点云数据还可进行各种后期处理，如测绘、计量、分析、仿真、模拟、展示、监测、虚拟现实等。因而，将多个深度图像数据配准后建立三维的几何模型并进行后期处理已经成为当前一个重要的研究课题。由上，图像配准技术在二维或者三维图像处理中的广泛的应用基础，可以看出它重要性和发展前景。而本文将图像配准技术应用于地图拼接问题中，仅仅是一次牛刀小试。但另一方面从应用后结果分析来看，也充分证明了图像配准技术的强大力量和广泛的应用价值。图像配准的应用领域概括起来主要有如下4个方面：（1）医学图像分析：肿瘤检测，白内障检测，ct,mri,pet图像结构信息融合，数字剪辑血管照造影术(dsa)等；（2）遥感数据分析：分类，定位和识别多谱段的场景信息，自然资源监控，核生长监控，市区增长监控等；（3）模式识别：目标物运动跟踪，序列图像分析，特征识别，签名检测等；（4）计算机视觉：目标定位，自动质量检测等。图像配准技术在很多领域都有着广泛的应用，因此，今年来，它已成为图像处理技术研究的重点课题。1.2 国内外研究现状点集配准问题最初产生于计算机视觉，计算机图形学和图像处理领域。点集配准是图像配准问题的基础，因而对点集配准的研究得到了各界学者一致的重视和关注。而本文所阐述到的刚体配准问题则是其他非刚体配准问题研究的基础和前提，所以在过去几十年里，人们对于刚体点集配准做了许多探索，取得了很大成就。1.2.1图像配准的历史和研究现状图像点集刚体配准技术最早出现在上世纪70年代，当时美国正在从事飞行器辅助导航系统，武器投射系统的末制导和寻地等应用研究，从研究这些问题中，一个不得不妥善解决的问题被广大的研究人员提出，它就是现在的图像配准问题的雏形。该问题被提出后得到美国军方大力的支持和赞助，在经过而后长达二十多年的研究，最终科学家们在潘兴2式中程导弹及战斧式巡航导弹上完美的应用了图像配准技术，使弹着点平均圆半径误差达到小于10米左右的精确度，可谓是导弹命中率上至高的一个飞跃。进入八十年代后，随着科学技术的发展，图像点集配准技术的研究深入到了更为广大的领域，如遥感图像处理，模式识别，自动导航，医学诊断，计算机视觉。各个领域所研究的配准技术都针对各自特殊具体的应用环境，并结合自身领域的相关技术，而更为抽象统一的图像点集配准技术理论并未在科学的层次上被提出和理论建立。直到70年代初，p.e.anuta提出了使用fft进行互相关图像检测计算的图像配准技术，以提高配准过程的收敛速度性能；d.lbarnea等提出了利用模板子图像差值相似性度量的图像配准技术，它比使用fft计算互相关相似度量进行图像检测技算的图像配准方法更具高的性能；w.k.pratt对图像配准的互相关技术进行了全面的研究；m.svedlow等对图像配准的相似性度量和预处理方法进行了比较分析；h.maitre等提出了基于自回归模型的动态程序设计方法用于几何畸变较大的图像配准；flussr针对变形图像间的匹配又提出了一个自适应映射方法，自动地对两幅遥感图像进行分割，使得分割后两幅图像中相应子块间的相似性度很大，从这些子块的空间位置关系来对原来的两幅图像进行匹配。在二十世纪八十年代初期，当时图像配准问题的研究方向主要为最基本的全局刚体配准算法，并且往往只针对某些特定形状的点集进行研究工作。随后八十年代末期，对无需提取图像点集特征而直接进行配准的图像配准方法被广泛的提出和运用，但这还是限于某些特殊简单的情景。例如，schwartz和sharir通过弧长抽样完成了曲线图像的配准问题，但是由于该方法受噪声影响很大而往往结果不尽如人意；taubin提出了一种不需要提取图像特征就可以完成三维曲线和曲面的姿态估计的配准算法，但该算法在过于复杂的曲面上图像（如地形数据或者人脸数据等）上无能为力。八十年代的点集刚体配准的算法，总结起来都是集中于对已知对应关系的点集求解最佳刚体变换，并且都是以欧氏空间中的最小平方准则作为相似性度量函数的。直到二十世纪九十年代初，图像配准领域中的一个里程碑式的刚体配准算法被提出，它就是大名鼎鼎的刚体迭代最近点算，英文iterative closet point（简称icp）。它的提出，才标志点集刚体配准问题已成为一个历史。由于icp算法具有不需要提取点集的特征，不需要对数据进行预处理，具有收敛速度快而精度高的优点，因此它理所当然的成为了众多领域为人所熟知的图像配准算法。在icp算法被提出后的二十年内，大量学者从收敛速度和收敛性方面对icp算法做了大量的理论研究和实验论证，因此更多的针对更为复杂现实情景中图像配准的变种icp算法被提出。这其中的例子数不胜数，例如，fitzgibbon采用levenberg-marquardt算法加快icp的收敛速度；jost和hugli用了一种由粗到精的搜索策略加快了icp算法收敛速度；ezra等分析了icp算法的收敛速度问题，证明了刚体配准的时间复杂度与点集中点的个数间的相关性；更多学者研究了icp算法局部收敛性，并倾心于扩大算法收敛域的问题。正是由于对icp算法收敛速度和局部收敛性的研究，解决部分对应点的配准问题的算法被提出了。相对于全局点集的配准研究的比较成熟，解决方法多且较简单，相反，部分对应点集的配准问题还是一个难点热点问题，因此也是本文研究的重点。相对国外，在国内图像配准技术起步相对较晚，但后来获得了很大发展。李智等提出了基于轮廓相似性度量方式的图像配准方法，它适用于轮廓特征比较丰富的图像配准。郭海涛等提出了一种将遗传算法（genetic algorithm,简称ga）用于图像配准的算法。王小睿等提出并实现了一种自动图像配准算法，用于图像的高精度配准，但实际上它是一种使用互相关函数作为相似性度量的半自动图像配准算法；熊兴华等提出了将遗传算法和最小二乘算法结合用于图像的子像素级配准算法1.2.2刚体部分配准问题研究现状在部分对应点集配准问题被提出后很长一段时间内，如何提高算法的精度成为了广大研究者共同以追寻的目标，由此而产生的各种优秀的部分配准算法大多数都是以经典的icp算法为基础，然后通过引入现代科学的优化策略来实现的。点集的部分配准问题主要涉及两类：一是待配准点集和目标点集间存在部分数据丢失，即仅能够作部分点集的对应；另一是在各种各样的噪声干扰下产生了较大量的离群点，不稳定几何点，多余点的情景。现在对部分配准问题的解决方法主要有：1）几何方法所谓几何方法，是指采用几何约束条件来排除点集配准中的噪声点和大量无信息点对的方法。atasha gelfand提出一种保证空间变换稳定性的点集提取方法，从而提高icp算法的几何稳定性。rusinkiewicz和m.levoy通过提取法向量方向均匀分布的点集作为配准点集，保证两个配准点集之间平移误差最小，进一步提高算法的精度。yonghuai liu通过分析刚体移动的特性，引入几何约束条件来去除icp算法中错误的匹配点。为了进一步改进此算法，yonghuai liu又将刚体移动的几何规律与点集最邻近约束条件相结合，通过选择正确的匹配点对，再次提高icp算法的精度和鲁棒性。这类方法的几何约束条件经常需要根据具体的点集形状而定，因此适应性不是很强。2）概率方法通过建立概率模型来约束配准过程，进而提高算法的鲁棒性也是一类常见的方法。ziner将对应点集的距离看做一种概率分布，计算其标准方差，迭代过程中排除距离大于该方差的点对。haitao zhang通过提取深度图像信息，运用基于概率场的icp算法进行深度图像配准。bjom jensen在icp算法中引入概率距离矩阵，该距离矩阵同时考虑到传感器噪音和待匹配目标位置的不确定性，从而可以有效排除异常点。基于概率的方法配准含形状噪声的点集具有较强的鲁棒性，但是却不能有效解决具有大量离群点或者缺失数据的配准问题。3）阈值度量方法针对提高icp算法鲁棒性这一问题，很多学者采用阈值度量方法在迭代过程中排除异常点的干扰，从而提高点集匹配的精度。emanuele trucco在icp算法中引入线性回归的和中值最小化的方法，在求解空间变换的过程中排除离群点的影响，从而得到更鲁棒的空间变化。dalley通过计算schultz距离来设置阈值大小，排除点集中的噪声点。zhang则结合高斯概率分布规律，通过设定阈值来排除噪声点。该类方法的缺点在于阈值或距离度量不好确定，配准算法往往受到点集形状的影响，导致收敛性不好。4）由粗到精的方法另外一些学者采用由粗到精的策略来提高缺失数据点集配准的鲁棒性。chen提出darces方法，该方法通过自动选取控制点的方式完成粗匹配，然后进一步细化，完成精匹配。rodriguez-losada在细匹配之前，过滤掉和粗匹配结果差异过大的点对。尽管这些方法能够一定程度上提高具有异常点的点集配准的鲁棒性，但是往往需要正确的初始化条件，否则在出现大量缺失数据时候，很容易陷入局部极值点，从而导致错误的配准结果。在上面介绍到的所有用于解决点集刚体部分配准问题的方法中，大多数算法都存在对参数过于依赖弊端性，而且通常情况下需要待配准点集提供额外信息。这些算法在实际问题解决中往往会出现配准精度不高，效率低下等缺点，简而言之结果并不尽如人意。1.3本文研究内容及组织结构1.3.1本文的研究内容点集刚体配准作为图像配准的一项基础而关键的技术，它是计算机图形学，机器视觉和图像分析领域的一个关键问题和研究重点。因此，本文对点集刚体配准问题，进一步点集部分刚体配准问题，都进行了概念和算法原理方面的详尽阐述，分析了点集刚体配准普遍存在存在的缺陷和难点。最后一章中，本文将第三章阐述的以重叠百分比为基础的刚体部分配准算法应用到了二维地图拼接实例中，而且从实验结果的良好性充分证明了算法的优越性。本文的具体研究内容如下：1)研究仅有部分区域重叠的刚性图像的配准问题，提出一种快速鲁棒的刚体配准算法。讨论了在有噪音和数据丢失的情况下，部分点集的配准问题。为了解决这个问题，针对部分区域能够重叠情况，我们提出了一个新的目标函数，函数式中引入了重叠百分比r。由此也产生了一种新型的鲁棒迭代最接近点（icp）算法。在此算法中，通过每步不断求解刚体变换，对应关系，重叠百分比，最终解决刚体部分配准问题。这种新的算法使用尽可能多的点对，以求产生两个点集之间更可靠和准确的配准结果。实验结果表明，此算法是比传统的icp和目前国内最先进的算法更为可靠和高效。2）给出基于迭代最近点的部分配准算法在地图拼接方法中的应用。由于摄像机在不同时刻，不同位置角度进行摄像时，大多数情况下得到的地图图像将是不同的，然所谓的不同也不是完全的不同，它们可能存在某部分区域相同的情况。为了从多个相机拍摄得到的地图图像拼接起来以得到一张大的信息量更多的图像，就需要一种技术能够将这些图像拼接起来。而上面研究的刚体部分迭代最尽点算法刚好可以应用这个问题中来，于是本文中应用了这个算法，然后在matlab上写程序实现算法，模拟测试了两张地图的拼接过程和最终结果。本文的组织结构：第一章， 绪论。本章首先介绍图像点集配准的研究背景和意义，然后对点集配准问题进行描述并且分析其难点，接着介绍点集配准的研究现状，最后给出本文的研究内容和组织结构。第二章， 刚体迭代最近点算法。本章首先给出了点集配准的概念，然后在此概念上阐述了刚体变换和相似性度量，接着给出了刚体配准的数学模型和流程框图。在此基础上，本章详细的阐述了传统经典的icp配准算法，即迭代最近点算法，并给出了该算法流程和每步的求解方法，最后对icp算法收敛性进行了细微详尽的分析。本章最后还展示了应用刚体迭代最近点算法，在matlab上配准两幅简单线条的黑白图片的实验结果，并对实验结果进行了初略分析，对结果中的不足提出疑问。第三章， 基于迭代最近点的部分配准算法。本章首先提出了具有部分数据丢失的点集部分配准问题，然后建立基本的数学求解模型。接着在此基础上，本章详细的阐述了一种采用重叠百分比的变种icp配准算法，此算法可完美解决点集部分配准问题。阐述过程中并给出了该算法的简要流程和具体步骤，以及每一步中要求解的数学表达式，更深一步的本文还对算法进行了理论上层次较高的算法分析。最后实验结果和分析是在二维刚体情景中进行的，对不同图像情景在配准算法参数和循环次数已经配准时间上进行了列表展示和分析比较。第四章， 基于迭代最近点的地图拼接方法。第五章， 结论与展望。在该章中对全文进行总结，并对下一步的工作进行展望。2 刚体迭代最近点算法2.1 刚体配准问题刚体配准是图像配准问题中一类最为基础和简单的，很多其他的复杂高级的配准问题的解决之道都是在其基础上研究发展而得到的，所以对刚体配准问题的理解在本文后面的工作中至关重要。谈到何谓刚体配准，首先我们要从点集配准的概念开始，因为点集配准是图像配准的一项关键技术，它是从计算机视觉、模式识别和图像处理的各个领域中抽象出来的一类重要的基础问题。点集配准。所谓点集配准就是寻求两个图像点集之间的一种几何变换，通过变换后能够使得一个图像点集中的每个点与另一个图像点集中的每个对应点能够达到空间上最佳的匹配。对在不同时间、不同视角、不同成像模式等不同条件下获得的两幅图像（包括二维平面图像和三维深度图像）进行配准，就是要确定如何来度量或者说是考察两幅图像在空间上位置的差异，这可以是一个数学函数，在本文中我们姑且称其为相似性度量函数。相似性度量函数目前已有多种，它一般都是某个距离的函数。当前，点集配准中常用的距离度量有euclidean 距离、mahalanobis 距离、hausdorff 距离等。由于本文仅涉及euclidean距离，本文后面仅简要阐述了一下euclieadn距离度量。刚体(rigid body)。在任何力的作用下，体积和形状都不发生改变的物体叫做刚体。以上是物理学上对刚体所下的定义，那顾名思义刚体配准就是刚性图像间的配准，它主要包括旋转和平移变换。所以本文中所涉及的变换t仅限于旋转和平移，而不包括其他变换，如相似变换、伸缩变换、仿射变换、投影变换和弹性变换等。在数学上建立刚体变换的模型相当简单：给定rm维空间中的形状点集s和模型点集m，假设存在任意两点和，那么刚体变换的数学表达式为：x原始点集y变换后点集rm x m维的旋转矩阵，r满足如下约束：tm维的平移向量图像点集配准中一个重要的量相似性度量j。点到点的距离又称为 2 范数距离，它表示rm空间中两个点xx1 ,x2 ,.,xi ,. 和y y1 ,y2 ,.,yi ,. 之间的真实距离： 由于euclidean计算比较简单，因而它是最为常见和常用的距离，大多数点集配准问题都采用它来定义空间中点对的距离。以点到点的euclidean 距离为基础作相似性度量，最为常见的是两个集合之间的最小平方（least square，ls）准则。对于两组点集，进行配准的ls准则函数为： 综上述，刚体配准是图像配准中的一种，它最终目的是通过寻找一个空间变换t，即r和t,使得经过该空间变换后两幅图像间相似性度量j最小，这也就达到了两幅图像中的点在空间几何上的一致。图 error! no text of specified style in document.1 点集配准示意图给定r空间中的两个点集：s-形状点集m-模型点集故配准问题实际上是解决上述两个未知量，即最优的空间变换t和确定形状点集到模型点集的对应关系c。现阶段刚体配准问题的研究工作中，最为典型的是icp算法，它有效地解决了点集的刚体配准问题，更为非刚体配准算法研究奠定了理论基础。2.2迭代最近点算法2.2.1 icp算法icp (iterative closest point)算法最早是由besl 和mckay于1992 年提出来的一个配准算法，它用于解决两个点集之间的刚体配准问题。icp算法的目标是寻找一个刚体变换，即旋转矩阵和平移向量，使得给定形状点集和模型点集中的点能够在euclidean欧式距离空间上对应起来。在经典的icp算法中，相似性度量采用了上述阐述到的最小平方（least square，ls）距离。对于刚体变换，空间变换仅包括旋转变换和平移变换，因此刚体配准问题可表示为：c(i) -形状点集和模型点集间的对应关系。np -形状点集中点的个数。刚体配准问题实际上是求使满足上式的r，t和c(i)，即变换和对应关系。icp配准算法通过交替迭代的方式来分别求解这两个未知变量，算法流程如图 21所示：图 error! no text of specified style in document.1 icp算法流程从图 error! no text of specified style in document.1可以看出，经典的icp算法首先由人为估计给定一个初始的空间变换，并且这个初始值要求应当粗略正确。然后icp算法正如它的名字一样通过反复迭代，不断改进空间变换和对应关系最终以求达到最优的配准效果。那icp算法是如何改进每步迭代中的变换量和对应量的呢？下面给出具体的数学表达式，来阐述原理：1） 根据步的刚体变换来确定形状点集和模型点集间每个点的对应关系 2） 计算两个点集和之间新的刚体变换：3）更新第步的变换和：icp算法是一个迭代过程，那么算法在何处停止迭代而退出呢？这就涉及到如何判定图像点集配准所达到的效果程度，很简单明了的一种方式是总体上形状点集中点和模型点集中对应点的2维范数以达到最小。这就是所谓的两个点集间的均方误差（mean square error，mse），数学表达式为。当达到我们设定的某个范围值下限时，我们就可以让icp算法停止迭代退出了。当然实际配准中，我们很大的可能性是不可能使配准误差达到它理论上的最小值，因为这可能需要难以忍受的等待时间或者根本就不存在这样一个最小值。所以我们往往采取均方误差达到设定范围下限和迭代步骤达到指定的循环次数这两个指标，来决定是否停止迭代。当icp算法循环退出后，那么返回得到最终的刚体变换和点集对应关系，通过这两个量我们就可以把两幅刚性图像配准了。2.2.2 算法求解对第一步求解，有k-d树、基于delaunay(德劳内 )三角化的最近点搜索算法等。很多研究和实验结果一致表明，k-d树适合于高维点集的点搜索，而基于delaunay三角化的最近点搜索算法则更适合于低维点集的点搜索。鉴于简单起见，本文采用的是delaunay三角化。对第二步求解，有svd(奇异值分解，singular value decomposition)、四元组、正交矩阵、双四元祖方法，本文采用的是svd1）delaunay三角化求解点集对应关系如何把一个散点集合剖分成不均匀的三角形网格，这就是散点集的三角剖分问题。将二维(三维)空间中任意分布的散乱点用直线段连接起来，形成的空间上既不重叠又无间隙的紧邻的三角形(四面体)集，每个三角形(四面体)的顶点即为原始散乱点。也就是说，在二维情况下得到的是三角形网格，在三维情况下得到的是四面体网格。在已有的多种三角剖分的优化规则中，目前公认的具有最好几何拓扑性质的剖分就是符合delaunay规则的三角剖分。delaunay剖分必须满足两个基本准则，其一是空圆特性，即在delaunay三角形网中任一个三角形的外接圆范围内不会有其它点存在。其二是最大化最小角特性，即在散点集可能形成的三角剖分中，delaunay三角剖分所形成的三角形的最小角最大。局部变换法和watson算法是离散点集delaunay三角剖分的常用算法，算法过程中逐点添加、局部优化是三角网格生成速度的重要影响因素。根据delaunay三角剖分原理，可以构造出各种适合该网格形状的搜索策略。对于icp算法中式的求解，首先将模型点集进行delaunay三角剖分，然后采用三角划分搜索策略找到形状点集在模型点集中的对应点。该搜索策略大幅度提高了点集对应关系求解的速度和精度。2）svd方法求解刚体变换svd方法相当比较简单，而且具有较好的扩展性，所以本文采用奇异值分解singular value decomposition的方法解决第二步中刚体变换求解。定理（1）：给定任意两个维对应点集和，当时，目标函数取得最小值。设 ， 那么式最小化目标函数为：要使目标函数最小，则：令，化简目标函数得：最小化目标函数，即最小化2.2.4 实验结果 图a-1 模型图像 图a-2 待配准图像 图a-3 配准结果 图b-1 模型图像 图b-2 待配准图像 图b-3 配准结果 上面所示的实验结果图中，因为为了简单起见均采用的是黑白图，而且仅仅是提取了图片中图像物体的外部轮廓线条特征来作配准的标准。其中模型图像和待配准图像之间仅仅是一个旋转和平移的效果，并涉及其它复杂的图像变换，这也正是刚体变换所需要的前提。在配准结果图中，需要说明的是红色线是待配准图像的轮廓，绿色线是模型图像的轮廓，程序结果并没有很好的展示配准后两者相重叠的轮廓部分。 从上面的配准结果来看，ipc算法的配准效果还蛮不错的。2.4 本章小结本章首先提出了图像点集配准问题的概念，接着在数学上建立点集配准的模型，随后又阐述了在众多的刚体配准研究中最为瞩目的由besl和mckay提出的icp算法，并且详尽地论述了算法运作流程和算法每步中问题的解决方法。本章最后给出了利用icp算法在matlab上所做的简单图像配准实验结果。3 基于迭代最近点的部分配准算法前面第二章描述了icp刚体配准问题并建立了它的数学模型，且给出求解icp刚体配准问题的具体方法和原理，接下来本章将在上面的基础上进一步研究基于icp（即迭代最近点）的刚体部分配准问题。因为传统的icp算法是建立在假设两个待配准点集中所有点都是有其相对应关系的前提下的，它并未考虑到实际中存在的复杂情况，如障碍物遮挡，拍摄角度狭窄及传感器噪声等因素所造成的点集部分数据丢失或存在大量离群点情况下图像点集的配准。所以本章针对这一问题，会在传统icp算法基础上，将引入重叠百分比的概念，然后建立关于空间变换的新目标函数，因而与前面icp算法不同的是在配准过程中，将同时更新三个未知量，即点集重叠百分比，空间变换和点间对应关系。很明显相对传统的icp算法新增了重叠百分比这个变量，所以算法也相应变得更为复杂，更具挑战性。在内容安排方面，本章首先给出点集刚体部分配准问题的描述及解决方案，接着提出本文的第一个创新点，一种能够自动计算点集重叠百分比的快速鲁棒的刚体配准算法，然后详尽阐述算法的基本思想原理和算法解决问题的步骤流程，最后就是给出实验结果，并根据结果一些数学品质考察此算法的性能。3.1 刚体部分配准问题3.1.1问题描述传统icp算法假设形状点集p中每一点都能在模型点集中找到与之相对应的点，即假定了两个待配准点集之间存在完整的对应关系。然而在现实环境中图像配准问题中，由于摄相机拍摄角度，障碍物遮挡，传感器噪声以及图像处理过程噪声等因素的影响，因而存在这样一种情况：点集p中仅有部分点能够在点集m找到相对应的点，即两个点集之间仅存在部分对应的关系，而且很可能p中能找到对应点的点集是非常小的一部分。在这种情况下，传统的icp算法就无法保证配准结果的鲁棒性，无法得到较为精确的配准结果，而且非匹配点集所占比例越大则往往得到错误配准结果的几率更大。如果按照点集对应关系来分类，则通常认为点集部分配准问题可以分为两大类：一类是具有点集中部分数据丢失或点集中含有大量离群点的点集配准，而另一类是具有形状噪声的点集配准问题。第一类往往是由于摄像机两次拍摄角度不同，或者两次采集图像时障碍物遮挡情况不一，再或者是采集设备自身缺陷等原因而造成的。它主要表现为两个点集之间仅有一部分点集是能够对应起来的，而其他部分则完全相异，并且这些非对应点存在方式跟外界环境和对象物体形状本身有关，因而无法精确估计非对应点的分布和几何位置。具有形状噪声的点集一般是由于外界环境的干扰和采集设备本身的限制产生的。所谓形状噪声，它是指图像点集位置与真实精确的位置相异但差别却很小，仅仅是一个小小的扰动而已，而且噪声往往服从某些概率分布，如高斯分布。所以对于此类经常采用概率的方法进行建模匹配。本章即后面的地图拼接仅涉及到第一类点集部分配准问题，所以对于第二类点集部分配准在本文中将不会再被提及和探讨。图给出二维情况下缺失数据点集实例。其中红色表示模型点集，蓝色表示形状点集，绿色和天蓝色分别表示两个点集中多余或者缺失的部分。仔细观察3-1中的两幅图可以看出，形状点集中的绿色部分在模型点集中无法找到相对应的部分，而模型点集中天蓝色部分在形状点集中也无法对应起来。这就是本文所涉及的刚体点集部分配准问题。图3-1 缺失数据点集如何解决上述具有部分数据缺失的点集配准问题呢？大家都会想到的很简单的考虑是先要排除待配准点集中彼此多余或者缺失的部分，仅留下能够相对应起来的部分，否则不大可能得到可靠的配准结果。然而宏观的想法是很简单的，但具体到如何有效排除点集中的非对应点集部分则是一个较为复杂难办的问题。所以这是本章要解决的一个艰巨重要的关键问题。在前面，本文绪论中范范而谈了几种处理部分对应点集的配准方法，即阈值方法，概率方法，几何方法等，然而这些方法都依赖于待配准点集的形状，或知道了噪声点服从某个已知出名的概率分布函数，而我们面对的情况是未知待配准点集图像形状和未知噪声概率分布函数这一更为严峻的情景，它往往是具有较大面积数据缺失的情况。所以前面谈到的方法对本文所研究的问题无法适用，我们将采用一个新的方法。分析具有缺失数据的点集配准问题，可以发现两个待配准点集之间的重叠百分比是一个重要的衡量标准。如果能计算两个点集之间的重叠百分比，那么就可以很轻易地排除点集中的非对应点。换而言之，对于具有缺失数据的点集配准问题，不仅要确定两个点集的对应关系和全局的几何变换，而且还要确定点集的重叠百分比。3.1.2 模型建立如何确定两个点集之间重叠百分比r是建立具有部分数据缺失的点集刚体部分配准数学模型的一个至关重要的问题。在本文中，该百分比r的最优值是由配准误差来确定。作为一个直观，图 32给出了在一般大量配准情景中，点集重叠百分比r与均方根误差（root mean square，rms）的关系。从图 32可以看出，配准误差是重叠百分比r的一个简单的单调递增函数，开始重叠百分比r比很小时配准误差几乎为零，因为形状点集中能够建立对应关系的点个数此时极少故几乎不存在任何误差，然而当重叠百分比达到某个值时配准误差开始突增，根据大量实验表明此时的r值在0.7-0.75之间。接下要做的是寻找最优的r值，所谓最优的重叠百分比，是指在该百分比值下能够求得最优的空间变换，即形状点集中那部分能够建立对应的点集能够最佳的与模型点集中相对应的部分点集能够在几何空间上达到一致。理论和实验一致证明了，最优的重叠百分比r并非像大家想像的那样理所当然的对应具有最小配准误差时的值，而是对应配准误差突增时的值，即在0.7-0.75值之间图 error! no text of specified style in document.2 配准误差与重叠百分比与传统icp配准算法相比较，因为传统icp配准算法假设了形状点集和模型点集间具有完整完全的点对应，故当均方误差达到最小时所求得空间变换也是点集配准过程中最优的变换，再经过多次迭代后配准误差更小，空间变换更优，最终配准结果趋于最佳。而对于具有部分数据缺失的点集部分配准问题，最优空间变换的求解要复杂得多，它不像传统icp配准算法那样仅仅取决与一个配准误差量，它还依赖与重叠百分比r。所以说重叠百分比是很重要的，最基本的要求是该百分比能尽可能多地包括两个点集中能够相对应的部分，而且还要尽可能排除所有离群点。从重叠百分比的大小考虑：1）重叠百分比很小。点集之间能够作对应点个数很少，按照配准均方差的度量方式计算误差将会很小，但是此时配准算法所能够利用的点集信息很少，因而导致配准结果并不尽人意，虽然此时配准误差几乎为零。2）重叠百分比很大。点集之间能够作对应点个数很多，按照配准均方差的度量方式计算误差将会比较大，作为补偿的是此时配准算法所能够利用的点集信息很大。但是如果重叠百分比r取值过大，又会产生在匹配过程中引入大量不能作对应的点的问题，而这些异常点会提供错误的信息，错误引导配准的进行方向，其结果是配准不鲁棒。综上述，最优的重叠百分比r应该是两矛盾方面的中庸之道。如何讲呢？最优的重叠百分r一方面要使配准误差相对较小，而另一方面又要尽可能多地利用待配准点集中能够作对应的点，而这两方面又是相互矛盾对立的。最优重叠百分比r使得点集配准在误差取得极小值的情况下又尽量多地利用了待配准点集的信息。为了使下面的算法和传统icp算法相一致，即更为直观的在配准误差达到最小时，配准效果也达到最佳，而不是前面分析的在误差突变时刻，本文借用正则化的思想来解决这个问题。既然配准误差是关于重叠百分比的递增函数，而最优重叠百分比出现在误差突增的时刻。因此可以给该误差除以一个连续递增的惩罚因子，得到一个新的目标函数。如果惩罚因子选择合适，所得新的目标函数就是一个凸函数，而该凸函数的最小值点就是最优重叠百分比对应的取值点。下面给出新目标函数的数学表达：给定rm维空间中的形状点集s和模型点集m，设表示两个点集的重叠百分比，表示形状点集中与模型点集相对应的部分点集。新的目标函数定义为关于重叠百分比和调控参数的函数：点集配准均方误差:惩罚函数:则目标函数又可以表示为：如下图所示，蓝色点线是配准误差函数，绿色点线是惩罚函数，而红色点线则是目标函数。很明显可以看出该目标函数是一个上凸函数，而函数的最小值点的横坐标就是最优重叠百分比r的取值。根据上述分析，目标函数的最小值点所对应得到的重叠百分比就是要求解的最优重叠百分比，此值在下图中为0.7。图 error! no text of specified style in document.3 3.2迭代最近点部分配准算法3.2.1带重叠百分比的部分点icp算法如前面阐述传统icp算法流程一样，这里给出本文中被称作带重叠百分比部分点icp算法的流程图。与前面经典icp算法显著的不同是，该算法在每步迭代中除了要计算求解点集的对应关系和空间变换外，还要计算点集重叠百分比r。简要具体流程如图 34所示：图 error! no text of specified style in document.4 算法流程图算法开始的第一步，假设形状点集和模型点集是完全重叠的，即令，调控参数=。然后以后每步迭代中调控参数从递减到。对于第步的，在迭代过程中最小化目标函数，计算出该步最优的刚体变换和，然后赋值传递给第步。算法的内循环迭代流程类似于传统icp算法，但是循环体