logo资料库

ICP迭代最近点算法综述.pdf

发布时间：2022-06-13 发布人：admin 分类：说明书 资料大小：0.41M 资料格式：pdf 举报 版权申诉
第1页 / 共10页
第2页 / 共10页
第3页 / 共10页
第4页 / 共10页
第5页 / 共10页
第6页 / 共10页
第7页 / 共10页
第8页 / 共10页
资料共10页，剩余部分请下载后查看
    1 引言
    2 ICP算法原理
    2.1 ICP算法原理
    2.2 ICP算法特性分析
    3 配准元素的选择
    4 配准策略的确定
    4.1 特征度量的选取
    4.1.1 点到点的距离
    4.1.2 点到平面的距离
    4.1.3 豪斯多夫(Hausdorff)距离
    4.1.4 几何特征
    4.2 搜索策略
    5 误差函数求解
    5.1 基于奇异值分解的方法
    5.2 四元数方法
    6 总结
    参考文献
    迭代最近点算法综述 摘要：三维点集配准问题是计算机技术中的一个极其重要的问题，作为解决三维点集配准问题的一个应用 较为广泛的算法，ICP 算法得到了研究者的关注，本文以一种全新的思路从配准元素的选择、配准策 略的确定和误差函数的求解等 3 个方面对三维点集配准的 ICP 算法的各种改进和优化进行了分类和总 结。 关键词：三维点集；迭代最近点；配准 1 引言 在计算机应用领域，三维点集配准是一个非常重要的中间步骤，它在表面重建、三维物 体识别、相机定位等问题中有着极其重要的应用[1]。对于三维点集配准问题，研究者提出了 很多解决方案，如点标记法、自旋图像、主曲率方法、遗传算法、随机采样一致性算法等等， 这些算法各有特色，在许多特定的情况下能够解决配准的问题。但是应用最广泛的，影响最 大的还是由 Besl 和 Mckay 在 1992 年提出的迭代最近点算法[2]（Iterative Closest Point，ICP）， 它是基于纯粹几何模型的三维物体对准算法，由于它的强大功能以及高的精确度，很快就成 为了曲面配准中的主流算法。 随着 ICP 算法的广泛应用，许多研究者对 ICP 算法做了详细的研究，分析了该算法的 缺陷和特点，提出了许多有价值的改进，推动了这一重要算法的发展。本文着眼于 ICP 算 法的发展历程，详细介绍了 ICP 算法的基本原理，总结其发展和改进的过程，对于该算法 的各个阶段的发展和变化做了简单的论述。 2 ICP算法原理 2.1 ICP算法原理 ICP 算法主要用于三维物体的配准问题，可以理解为：给定两个来至不同坐标系的三维 数据点集，找出两个点集的空间变换，以便它们能进行空间匹配。假定用{ } 表示空间第一个点集，第二个点集的对齐匹配变换为使下式的目标函数最小[3]。 ICP 算法的实质是基于最小二乘法的最优匹配算法，它重复进行“确定对应关系点集— 计算最优刚体变换”的过程，直到某个表示正确匹配的收敛准则得到满足。ICP 算法的母的 是找到目标点集与参考点之间的旋转 R 和平移 T 变换，使得两匹配数据中间满足某种程度 度量准则下的最优匹配。假设目标点集 P 的坐标为{ }及参考点集 Q 的坐标为
    { } ， 在 第 k 次 迭 代 中 计 算 与 点 集 P 的 坐 标 相 对 应 的 对 应 点 坐 标 为 ，计算 P 与 之间的变换矩阵并对原变换进行更新，直到数据间平均距 离小于给定值τ，即满足式（1）最小。具体步骤[4]： （1） 在目标点集 P 中取点集 ； （2） 计算参考点集 Q 中对应点 ，使 ； （3） 计算旋转矩阵 与平移向量 ，使得 ； （4） 计算 （5） 计算 ； ； （6） 如果 不小于给定的τ返回到（2），直到 或迭代次数大于预设的最 大的迭代次数为止。 对于 ICP 的每次迭代，最小化对应点的均方差使得点集 更接近 ，而 是 在 的 最近点。这样，每一次迭代就使得 更接近于 。基于这样的思想，Besl 等人证明了 ICP 算 法的收敛性。 2.2 ICP算法特性分析 在三维点集配准的各种应用中，ICP 算法的使用非常广泛，这是由于 ICP 算法有以下优 点：  可以获得非常精确的配准效果；  可以处理三维点集、参数曲面等多种形式表达的曲面，也就是说该算法对曲面表示 方法独立[5]；  不必对待处理的点集进行分割和特征提取；  在较好的初值情况下，可以得到很好的算法收敛性[6]。 虽然其得到了广泛的应用，但是对于最初的 ICP 算法，存在很多的不足之处，主要表 现在：  算法假设其中一个点集是另一个点集的子集，也就是说，一个点集必须含在另一个 点集中，这一要求在很多时候难以满足；  该算法在搜索对应点的过程中，计算代价非常的大；  在基本的 ICP 算法中，在寻找对应点的时候，认为欧氏距离最近的点就是对应点， 这种假设是比较武断的，它会产生一定数量的错误对应点[7]。 针对上面的一些问题，许多研究者提出了 ICP 算法的各种改进版本。为了说明 ICP 算 法的不同改进版本，有必要将 ICP 算法分成几个阶段来讨论，在各个阶段的划分，国内外 的研究学者也提出了自己的看法。主要的划分方法有，在 Rusinkiewicz[8]的文章中，将 ICP 2
    算法的进行分成了六个阶段，分别为：点集的选择、对应点对的配准、点对的权重确定、特 定点对的剔除、误差矩阵的建立、误差矩阵最小化的求解；伍毅[9]则将其分为四个阶段：重 采样、空间查找及距离度量、目标度量函数最小化和算法的迭代；Nishino[10]认为，不同的 改进方法的差异不过体现在三个方面：配准策略、配准元素和误差度量。 通过比较国内外学者提出的各种 ICP 算法的改进算法，可以知道，Nishino 的划分方法 可以很好的反应算法所做改变的各个阶段。所以，在本文中将围绕 ICP 算法配准元素的选 择、配准策略的确定和误差函数的求解等三个方面做的改进来展开。 3 配准元素的选择 在标准 ICP 算法中，选用点集中的所有点来计算对应的点，但是通常用于配准的点集 元素数量都是非常巨大的，通过这些点集来计算，所消耗的时间也是很长的。所以在后来的 研究当中，提出了各种各样的方法来选择配准元素，这些算法的主要目的无一例外的是为了 减小点集元素的数目，即对匹配点集进行采样。 既然涉及到采样，就有多种采样方法被尝试使用。Turk 使用了一致采样方法 [11]， Masuda[12]使用的式随机采样方法，而且在每一的迭代过程中都要进行随机采样获取不同的 采样点进行计算。 也有一些学者提出了一些新的采样方法，这些方法主要特点是会利用点集的特征信息来 减少点的数目，运用一些具有明显特征的点集来进行配准。比如，Weik[13]在文献中提到的， 利用图像的梯度信息来选择符合要求的点，再用这些点来完成配准。Sappa[14]则是采用了另 外一种策略，直接选取边缘点作为配准的选择点，这样就可以大大的减小配准点的数目。 通过上面的分析可以发现，配准元素的选择的改进，主要集中在如何减小配准点的数目 方面，即如何用最少的点来表征原始点集的全部特征信息。 4 配准策略的确定 上面介绍了 ICP 算法在配准元素选择方面做得一些改进，而更多的改进集中在配准策 略方面。具体的配准策略包括特征度量的选取和搜索策略的选取方面。 4.1 特征度量的选取 要寻找对应点对，就必须寻找场景数据点和模型数据点的特征差异，这就需要对特征进 行度量。在利用特征度量获得对应点以后，还需要利用特征度量建立迭代优化的目标函数， 为误差函数的求解奠定基础[15]。 ICP 算法被提出来时，采用的是欧氏距离作为特征度量，所以在这一阶段的改进方面， 主要是围绕距离展开，很多研究者在这方面提出了自己的改进想法，当然有一些也并没有采 用距离作为特征度量，在下面会做详细的介绍。 4.1.1 点到点的距离 在标准 ICP 算法中，Besl 和 McKay 直接采用的是点到点的欧氏距离。首先利用点到点 的最小欧氏距离得到点到集合的距离，从而寻找到对应点，再对这些对应点到集合的距离进 行求和得到求解刚体变换的目标函数，如(1)式所示。简而言之，标准 ICP 算法使用的是点 到点（point-to-point）的距离。 4.1.2 点到平面的距离 Chen[16]利用的是场景点集中的点的法线与模型点集合的交点来确定对应点，得到对应 点后，目标函数则采用的是点到面(point-to-plane)的距离，点到面的距离是指，场景数据集 3
    中的点到模型数据集合中的经过对应点的切平面的距离，如图 l 所示。场景点 P 中的点 ， 它的法线与模型点集 X 的交点 就被选择为 的对应点。在建立目标函数时，使用的并不是 到 的距离，而是 到模型点集 X 过 的切平面的距离。 图 1 点到平面的距离 点到平面的距离减少了迭代次数，能够以更快的速度收敛到给定的阈值。Pulli 对点到 点的方法和点到面的方法进行了对比讨论[17]，他们指出与点到点的 ICP 算法相比，运用点 到平面的距离的方法大大减少了计算量以及迭代次数，但是该方法的鲁棒性并不是太好。 与上面的度量标准相类似的还有点到三角形的距离，它运用点与点之间的邻接信息，将 三维点集三角化，以点到三角形表面的距离作为特征度量，与点到面的距离有一些相似，主 要由张鸿宾和谢丰在文献中提出[18]。 4.1.3 豪斯多夫(Hausdorff)距离 Hausdorff 距离[19]作为一种距离测度，常用于衡量两个点集之间的相似程度。由于使用 Hausdorff 距离作为距离测度时无需考虑两个点集中的点与点之间的对应关系，因此可以有 效解决当图像中存在噪声和目标被部分遮挡时的识别问题。Ezra[20]研究了使用 Hausdorff 距 离在 ICP 中的一些理论结果，还没有进行配准的实际应用。 4.1.4 几何特征 严格的说，距离也是一种几何特征，这里指的几何特征是指除距离以外的几何特征。主 要有法相量[21]、曲率等特征。 加入几何特征更多的是为了在确定点对时加入限制条件，尽量减小误差点的数目。Pulli 在文献中就加入了给定点对的限制条件，其中一个是每个点对对应的法向矢量差不能超过 45 度，而 Godin[22]则是通过曲率来构造候选兼容点集。图 2 就是通过原始 ICP 算法和加入 法相限制条件后获取的点对情况，其中空心箭头表示法相矢量方向，黑色箭头表示找到的对 应点对。 4
    （a） （b） 图 2 对应点对（a）通过传统 ICP 方法获得（b）中加入了法矢限制条件 通过加入几何特征的限制条件，可以进一步的降低找到错误点对的概率，同时加入几何 特征后，可以非常迅速的确定候选点集，可以大大的提高搜索速度。 4.2 搜索策略 在对应点的选取，也就是构造各对应点的过程中，需要进行大量的搜索过程，这是传统 ICP 算法的瓶颈，为了提高 ICP 算法的效率，提高搜索速度是很有必要的，所以如何改进搜 索策略也是 ICP 算法研究的热点。 Zhang 在其论文中采用了多维二元搜索树[23]（K-D Tree），该算法可以自动的踢出异常 值，可以处理非完全对应的点集合。Greenspan 分析了该树的特性，提出了近似多维二元搜 索树[24]（AK-D Tree），达到了近似的效果，并提高了效率。 另一种方法是依靠金字塔原理提出来的分级收缩算法[25]，大大加快了搜索速度。该方法 通过评估目标区域距离值的方差和均匀拓扑映射来选择区域，在点集中进行逐级的收缩，先 进行粗略定位，最后获取准确地对应点，对于搜索效率有很大的提高。 投影的方法也被应用到 ICP 算法中来，Blais 和 Neugbeuaer 采用反向定标[26]（Reverse Calibration）技术，就是使用的投影搜索算法。Benjemaa[27]则采用了具有多个投影平面的 Z-buffer 方法进行投影搜索。 5 误差函数求解 误差函数的求解，也就是目标函数的最小化，是 ICP 算法的最后一个阶段。在求得目 标函数后应该采用什么样的方法来求解目标函数，使其值能最快最准的的收敛到最小，也是 一个比较重要的问题。传统的 ICP 算法的目标函数是通过点对点的距离建立的，其求解方 法有基于奇异值分解的方法、四元数方法、正交矩阵法[28]和双四元数方法[29]。 Eggert[30]评估了上述四种方法的精确性和稳定性，并且说明了这些方法存在的差 异。由于基于奇异值分解的方法和四元数方法应用的更加广泛，所以，在下面将 对这两种方法的实现方式做具体的介绍。 5.1 基于奇异值分解的方法 用奇异值分解法（SVD 方法）来求解 ICP 算法过程中的几何参数最初是由 ARUN[31]等 提出来的，其并没有建立目标函数等式，而是通过矩阵变换的相关性质，直接求解出最优的 参数解。该方法实现起来比较简单，而且计算结果也比较准确，下面就对相关原理进行论述。 在运用 SVD 方法之前，我们默认已经通过了点对的搜索环节，而且已经准确的找了各 个对应点对。我们认为有两组点，模型点和采集到的点，模型点定义为 ,N 为点的数目。假设要求的旋转矩阵是 R，平移矩阵是 T，理想情况下通过 变换得到的对应 点位 ，有下面的等式： R 变换的旋转角度值； T 变换的平移值； 5
    Ni 噪声。 对于这 N 个点，现在我们已经找到每个点对，对于每个点在变换前后的值都可以非常 清楚地知道，根据式（1），可以得到下面的欧氏距离和。 由 ICP 算法的原理可知，欧氏距离最小的点就是采集点在模型中的对应的点，所以基 本 ICP 算法就是求解上面的代数式，使代数式的值最小的 R 和 T 就是要求的旋转角度和平 移值。而对上面的欧氏距离和，我们可以进行化简。 先计算模板点和数据点的重心 显然有 令 ， ，代入式（2），则有 对于（3）式右边进行分解，可以得到下式。 通过上面的等式，我们可以发现，要使 的值达到最大，等价于使下式最大。 F = = =Trace(RH) 其中， 什么样的情况下 Trace（RH）才能最大呢？这是接下来要讨论的问题。 假设 是一个正定矩阵，B 为正交矩阵， 是 A 中的第 i 列，则有 6
    由施瓦茨不等式可以得到， 所以有， 在求取 F 的最大值时，我们可以效仿上面的定理，先对 H 进行 SVD 分解，可以得到。 其中 U 和 V 为正交矩阵， 为非负的对角矩阵。 我们可以令 ，当然，X 也为正交矩阵，则有 XH 是一个对称正定矩阵，而由上面的证明，我们可以知道，对于任意的正交矩阵 B， 有 通过上式，我们可以发现，当 R 取 XH 时，F 将达到最大值。所以可以求出 R。则 SVD 方法进行的步骤可以归纳如下。 1、 通过 , 计算 ， 以及 和 。 2、 计算矩阵 H，通过式 3、 对 H 进行 SVD 分解。 4、 求解旋转矩阵。 5、 计算平移矩阵 T。 该算法不适合运用于线性的和有奇异点的数据集。 7
    5.2 四元数方法 Horn 等[32]提出了基于单位四元数的计算运动参数的方法。旋转矩阵 R 用一个单位四元 数 q 来表示：R=R(q),其中设单位四元数 ,其中 ,而且 ,则有这个单位四元数产生的旋转矩阵为[33]： （5） 定义平移向量为 ，并由 和 组成一个配准状态向量 。 点集的重心分别为 p 和 ，则两点集的协方差如下： （6） 根据 得出一个反对称矩阵 A，其元素为 ，由 A 的三个循 环元素又组成了一个列向量 。最后，由以上矩阵和向量组成对称矩阵 （7） 其中 为 3X3 单位矩阵。求解对称矩阵 的特征值和特征向量，所得最大特征 值所对应的特征向量即为旋转四元数 。计算平移向量 ， 最终生成一个配准向量 。 6 总结 本文从配准元素的选择、配准策略的确定和误差函数的求解等三个方面对 ICP 算法的 各种改进和优化进行了分类和总结。通过文中的分析可以发现，ICP 在这些年的发展过程中， 将各种技术吸收进来，这一方面说明了 ICP 算法以其本身的优势获得了研究者的关注，另 一方面也说明研究者在对 ICP 算法改进上付出了不懈的努力 但是 ICP 算法的研究还没有停止，因为这种算法还不能解决所有的配准问题，也将还 会有人继续对这种算法展开研究，让其变得更加完美。 8
    分享到：
    赞 收藏

    相关推荐

    资料库

    课程资源

    共收录17145份资料，累计13个分类，关注成员有19位，主要包括：PHP,网络管理,网页制作,Java,.Net,数据库,3G/移动开发,C/C++,游戏开发,嵌入式,讲义,软件测试,专业指导

    热门标签

    PHP 网络管理 网页制作 Java .Net 数据库 3G/移动开发 C/C++ 游戏开发 嵌入式 讲义 软件测试 专业指导

    最新资料