基于迭代最近点算法的地图拼接方法研究毕业论文(编辑修改稿)

基于迭代最近点算法的地图拼接方法研究毕业论文(编辑修改稿)内容摘要：

idean距离，本文后面仅简要阐述了一下 Euclieadn距离度量。 刚体 (Rigid body)。 在任何力的作用下，体积和形状都不发生改变的物体叫做刚体。 以上是物理学上对刚体所下的定义，那顾名思义刚体配准就是刚性图像间的配准，它主要包括旋转和平移变换。 所以本文中所涉及的变换 T 仅限于旋转和平移，而不包括其他变换，如相似变换、伸缩变换、仿射变换、投影变换和弹性变换等。 在数学上建立刚体变换的模型相当简单： 给定 Rm 维 空间中的 形状点集 S 和 模型点集 M，假设 存在任意两点 xS和 yM ，那么刚体变换 的数学表达式 为： y R x t X —— 原始点集 Y —— 变换后点集 R —— m x m 维的旋转矩阵， R 满足 如下约束 ： t —— m 维的平移向量 图像点集配准中一个重要的量 —— 相似性度量 J。 点到点的距离又称为 2 范数距离，它表示 Rm空间中两个点 x{x1 ,x2 ,..,xi ,... } 和y{ y1 ,y2 ,..,yi ,... }之间的真实距离： 由于 Euclidean计算 比较简单，因而它是最为常见和常用的距离，大多数点集配准问题都采用它来定义空间中点对的距离。 以点到点的 Euclidean 距离为基础作相似性度量，最为常见的是两个集合之间的最小平方（ Least Square， LS）准则。 对于两组点集，进行配准的 LS准则函数为： 综上述，刚体配准是图像配准中的一种，它最终目的是通过寻找一个空间变换 T，即 R和 t,使得经过该空间变换后两幅图像间相似性度量 J 最小，这也就达到了两幅图像中的点 在空间几何上的一致。 图 错误 !文档中没有指定样式的文字。 1 点集配 准示意图 给定 R 空间中的两个点集： S形状点集 M模型点集 故配准问题实际上是解决上述两个未知量，即最优的空间变换 T 和确定形状点集到模型点集的对应关系 C。 现阶段刚体配准问题的研究工作中，最为典型的是 ICP 算法，它有效地解决了点集的刚体配准问题，更为非刚体配准算法研究奠定了理论基础。 ICP 算法 ICP (Iterative Closest Point) 算法最早是由 Besl 和 McKay于 1992 年提出来的一个配准算法，它用于解决两个点集之间的刚体配准问题。 ICP算法 的目标是寻找一个刚体变换， 即旋转矩阵 R 和平移向量 t ，使得 给定形状点集和模型点集中的点能够在 Euclidean欧式距离空间上对应起来。 在经典的 ICP算法中，相似性度量 J 采用了上述阐述到的最小平方（ Least Square， LS）距离。 对于刚体变换，空间变换 Τ 仅包括旋转变换 R 和平移变换 t ，因此刚体配准问题可表示为： 2( ) 21m in || || . . , de t( ) 1PNi c ic iTstR,t, R s t mR R I R C(i) 形状点集和模型点集间的对应关系。 Np 形状点集中点的个数。 刚体配准问题实际上是求使满足上式的 R， t 和 C(i)，即变换和对应关系。 ICP配准算法通过交替迭代的方式来分别求解这两个未知变量，算法流程如 图 错误 !文档中没有指定样式的文字。 1所示： 图 错误 !文档中没有指定样式的文字。 1 ICP 算法流程 从 图 错误 !文档中没有指定样式的文字。 1可以看出， 经典的 ICP算法首先由人为估计给定 一个初始的 空间变换 ，并且这个初始值要求应当粗略正确。 然后 ICP算法 正如它的名字一样 通过反复迭代 ，不断改进空间变换和对应关系最终以求达到最优的配准效果。 那 ICP算法是如何改进每步迭代中的变换量和对应量的呢。 下面给出具体的数 学表达式，来阐述 原理 ： 1） 根据 1k 步的刚体变换 11( , )kkRt 来 确定形状点集和模型点集间每个点的对应关系 21 1 2( ) a r g m i n ( | | ( ) | | ) , 1 , 2 , . . . ,k k i k j sc i i N   R s t m 2） 计算两个点集 1 1 1{( )} sNk i k i  R s t 和 ( ) 1{}sk Nc i im之间新的刚体变换： T2** 1 1 ( )2, d e t ( ) 1 , 1( , ) a r g m i n ( ( ) )pksNk i k c ii     R R I R tR t R R s t t m 3） 更新第 k 步的变换 kR 和 kt ： * * *11 , k k k k  R R R t R t t ICP 算法是一个迭代过程，那么算法在何处停止迭代而退出呢。 这就涉及到如何判定图像点集配准所达到的效果程度，很简单明了的一种方式是总体上形状点集中点和模型点集中对应点的 2 维范数以达到最小。 这就是所谓的两个点集 间的均方误差（ Mean Square Error，MSE） ，数学表达式为 2( ) 21 || ( ) ||skNk k i k c ii    R s t m。 当 k 达到 我们设定的某个范围值下 限时，我们就可以让 ICP 算法停止迭代退出了。 当然实际配准中，我们很大的可能性是不可能使配准误差 k 达到它理论上的最小值，因为这可能需要难以忍受的等待时间或者根本就不存在这样一个最小值。 所以我们往往采取均方误差达到设定范围下限和 迭代步骤达到指定的循环次数 这两个指标，来决定是否停止迭代。 当 ICP 算法 循环 退出后， 那么返回 得到最终的刚体变换 和点集对应关系，通过这两个量我们就可以把两幅刚性图像配准了。 算法求解 对第一步求解，有 kd 树、基于 Delaunay(德劳内 )三角化的最近点搜索算法等。 很多研究和实验结果 一致表明 ， kd 树适合于高维点集的点搜索，而基于 Delaunay 三角化的最近点搜索算法 则 更适 合于低维点集的点搜索。 鉴于简单起见， 本 文 采用的是 Delaunay 三角化。 对第二步求解，有 SVD(奇异值分解， Singular Value Deposition)、四元组、正交矩阵、双四元祖方法，本 文 采用的是 SVD 1） Delaunay 三角化 求解 点集 对应关系 如何把一个散点集合剖分成不均匀的三角 形网格，这就是散点集的三角剖分问题。 将二维 (三维 )空间中任意分布的散乱点用直线段连接起来，形成的空间上既不重叠又无间隙的紧邻的三角形 (四面体 )集，每个三角形 (四面体 )的顶点即为原始散乱点。 也就是说，在二维情况下得到的是三角形网格，在三维情况下得到的是四面体网格。 在已有的 多种三角剖分的优化规则 中 ，目前公认的具有最好几何拓扑性质的剖分就是符合 Delaunay 规则的三角剖分。 Delaunay 剖分必须满足两个基本准则，其一是 空圆特性 ，即在 Delaunay 三角形网中任一 个 三角形的外接圆范围内不会有其它点存在。 其二是 最大化最小角特性 ，即 在散点集可能形成的三角剖分中， Delaunay 三角剖分所形成的三角形的最小角最大。 局部变换法和 Watson 算法是离散点集 Delaunay 三角剖分的常用算法，算法过程中逐点添加、局部优化是三角网格生成速度的重要影响因素。 根据 Delaunay 三角剖分原理 ，可以构造出各种适合该网格形状的搜索策略。 对于 ICP 算法中式的求解，首先将模型点集 M进行 Delaunay 三角剖分，然后采用三角划分搜索策略找到形状点集 S 在模型点集 M 中的对应点。 该搜索策略大幅度提高了点集对应关系求解的速度和精度。 2） SVD 方法 求解 刚体变换 SVD 方法 相当比较 简单，而且具有较好的扩展性，所以 本文采用 奇异值分解 Singular Value Deposition 的方法解决第二步中刚体变换求解。 定理（ 1） ： 给定任意两个 m 维对应点集 1{}Niiq 和 1{}Niin ，当1111NNiiiiNNt n q时，目标函数 221( ) || ||NiiiF   t q t n取得最小值。 设 39。 11i k i ks R s t ， 那么式最小化目标函数为： 39。 2( ) 21( , ) || ||kNi c iiF   R t R s t m 要使目标函数最小， 则 ： ()1111sskNNc i iiippNNt m R s 令11 sNi i iipN  q s s，( ) ( )11skkNi c i c iisN  n m m， 化简目标函数得： 1 1 1( , ) 2s s sN N NT T Ti i i i i ii i iF       R t q q n R q n n 最小化目标函数，即最小化1sN Tiiin Rq 实验结果 图 a1 模型图像 图 a2 待配准图像 图 a3 配准结果 图 b1 模型图像 图 b2 待配准图像 图 b3 配准结果 上面所示的实验结果图中，因为为了简单起见均采用的是黑白图，而且仅仅是提取了图片中图像物体的外部轮廓 线条特征来作配准的标准。 其中模型图像和待配准图像之间仅仅是一个旋转和平移的效果，并涉及其它复杂的图像变换，这也正是刚体变换所需要的前提。 在配准结果图中，需要说明的是 红色 线是待配准图像的轮廓， 绿色 线 是 模型图像的轮廓，程序结果并没有很好的展示配准后两者相重叠的轮廓部分。 从上面的配准结果来看， IPC 算法的配准效果还蛮不错的。 本章小结 本章 首先提出了图像点集配准问题的概念，接着在数学上 建立点集配准 的 模型 ，随后又阐述了 在众多的刚体配准研究 中最为瞩目的由 Besl 和 Mckay 提出的 ICP 算法 ，并且详尽地论 述了算法运作流程和算法每步中问题的解决方法。 本章 最后 给出 了利用 ICP 算法在matlab 上所做的简单图像配准实验结果。 3 基于迭代最近点的部分配准算法 前面 第二章 描述了 ICP 刚体配准 问题并建立了它的数学 模型 ， 且给出 求解 ICP 刚体配准问题的 具体 方法和原理 ， 接下来 本章 将 在 上面的 基础上进一步研究基于 ICP（即迭代最近点） 的刚体 部分 配准问题。 因为 传统的 ICP 算法 是建立在 假设两个待配准点集 中所有点都是有其相对应关系的前提下的 ， 它 并未 考虑到实际中存在的复杂情况，如障碍物 遮挡，拍摄角度 狭窄 及传感器噪声等 因素所造成的点集 部分 数据 丢失或存在大量离群点情况下图像点集的配准。 所以本章针对这一问题，会在传统 ICP 算法基础上，将引入重叠百分比的概念，然后建立关于空间变换的新目标函数，因而与前面 ICP 算法不同的是在 配准过程中 ，将 同时更新 三个未知量，即 点集重叠百分比 ， 空间变换 和点间对应关系。 很明显相对传统的 ICP算法新增了重叠百分比这个变量，所以算法也相应变得更为复杂，更具挑战性。 在内容安排方面，本章首先给出 点集刚体 部分配准 问题 的 描述及解决方案，接着 提出本文的第一个 创新点， 一种能够自动计算点集重叠百分比的快速鲁棒的刚体配准算法 ， 然后详尽 阐述 算法 的基本 思想 原理和算法解决问题的步骤流程， 最后 就是给出 实验结果 ，并根据结果一些数学品质考察此算法的性能。 刚体部分配准问题 问题描述 传统 ICP 算法假设形状点集 P 中每一点都能在模型点集 M 中找到与之 相 对应的点，即 假定了 两个待配准点集之间存在 完整的对应 关系。 然而在 现实环境中图像配准问题中，由于 摄 相机拍摄角度 ， 障碍物遮挡， 传感器噪声以及图像处理过程噪声等因素的影响， 因而存在这样一种情况： 点集 P 中 仅有部分点能够在点集 M 找到相对应的点 ， 即 两个点 集之间仅存在部分对应的关系 ，而且很可能 P 中能找到对应点的点集是非常小的一部分。 在这种情况下，传统的 ICP 算法就无法保证配准结果的鲁棒性， 无法得到较为精确的配准结果，而且非匹配点集 所占比例越大则往往得到错误配准 结果 的几率更大。 如果按照 点集对应关系 来分类，则通常认为 点集部分 配准问题可以分为两大类：一类是具有 点集中部分 数据 丢失或点集中含有大量 离群点的点集配准，而另一类是具有形状噪声的点集配准问题。 第一类 往往是由于 摄像机两次 拍 摄角度不同，或者两次采集图像时障碍物遮挡情况不一，再或者是采集设备自身缺陷等原因而造成的。 它 主要表现为两个点集之间 仅有一部分点集是能够对应起来的，而其他部分则完全相异 ， 并。