首页 >> 生活百科 >>

ICP算法

生活百科 2023-01-26 08:57生活百科www.aizhengw.cn

ICP算法

三维空间R3存在两组含有n个坐标点的点集，分别为 PL和PR。三维空间点集PL中各点经过三维空间变换后与点集PR中点一一对应，其单点变换关係式为

(0-1)

上式中，R为三维旋转矩阵，t为平移向量。

在ICP配準方法中，空间变换参数向量X可表示为[9] 。参数向量中四元数参数满足约束条件为

(0-2)

根据叠代的初值X0，由式(0-1)计算新点集Pi为

(0-3)

式中，P表示原始未修改过的点集，Pi的下标i表示叠代次数，参数向量X的初始值X0为 。

根据以上数据处理方法，ICP配準算法可以概括为以下七个步骤

1） 根据点集Plk中的点坐标，在曲面S上搜寻相应就近点点集Prk；

2） 计算两个点集的重心位置坐标，并进行点集中心化生成新的点集；

3） 由新的点集计算正定矩阵N，并计算N的最大特徵值及其最大特徵向量；

4） 由于最大特徵向量等价于残差平方和最小时的旋转四元数，将四元数转换为旋转矩阵R；

5） 在旋转矩阵R被确定后，由平移向量t仅仅是两个点集的重心差异，可以通过两个坐标系中的重心点和旋转矩阵确定；

6） 根据式(0-3)，由点集Plk计算旋转后的点集P’lk。通过Plk与P’lk计算距离平方和值为fk+1。以连续两次距离平方和之差绝对值 作为叠代判断数值；

7） 当 时，ICP配準算法就停止叠代，否则重複1至6步，直到满足条件 后停止叠代

基本介绍

  • 中文名ICP算法
  • 外文名Iterative Closest Point
  • 搜寻方法最近点搜寻法
  • 变换关係式(0-1)
  • 算法步骤7步
  • 主要用于解决基于自由形态曲面
  • 属性算法

叠代就近点算法

在20世纪80年代中期，很多学者开始对点集数据的配準进行了大量研究。1987年，Horn[1]、Arun[2]等人用四元数法提出点集对点集配準方法。这种点集与点集坐标系匹配算法通过实践证明是一个解决複杂配準问题的关键方法。1992年，计算机视觉研究者Besl和Mckay[3]介绍了一种高层次的基于自由形态曲面的配準方法，也称为叠代就近点法ICP（Iterative Closest Point）。以点集对点集（PSTPS）配準方法为基础，他们阐述了一种曲面拟合算法，该算法是基于四元数的点集到点集配準方法。从测量点集中确定其对应的就近点点集后，运用Faugera和Hebert提出的方法计算新的就近点点集。用该方法进行叠代计算，直到残差平方和所构成的目标函式值不变，结束叠代过程。ICP配準法主要用于解决基于自由形态曲面的配準问题。
叠代就近点法ICP就近点法经过十几年的发展，不断地得到了完善和补充。Chen和Medioni[4]及Bergevin等人[5]提出了point-to-plane搜寻就近点的精确配準方法。Rusinkiewicz和Levoy提出了point-to-p rojection搜寻就近点的快速配準方法。Soon-Yong和Murali提出了Contractive-projection-point搜寻就近点的配準方法。，Andrew和Sing[6]提取了基于彩色三维扫描数据点纹理信息的数据配準方法，主要在ICP算法中考虑三维扫描点的纹理色彩信息进行搜寻就近点。Natasha等人[7]分析了ICP算法中的点云数据配準质量问题。
基本原理
三维空间R3存在两组含有n个坐标点的点集，分别为 PL和PR。三维空间点集PL中各点经过三维空间变换后与点集PR中点一一对应，其单点变换关係式为
(0-1)
上式中，R为三维旋转矩阵，t为平移向量。
在ICP配準方法中，空间变换参数向量X可表示为[9] 。参数向量中四元数参数满足约束条件为
(0-2)
根据叠代的初值X0，由式(0-1)计算新点集Pi为
(0-3)
式中，P表示原始未修改过的点集，Pi的下标i表示叠代次数，参数向量X的初始值X0为 。
根据以上数据处理方法，ICP配準算法可以概括为以下七个步骤
1） 根据点集Plk中的点坐标，在曲面S上搜寻相应就近点点集Prk；
2） 计算两个点集的重心位置坐标，并进行点集中心化生成新的点集；
3） 由新的点集计算正定矩阵N，并计算N的最大特徵值及其最大特徵向量；
4） 由于最大特徵向量等价于残差平方和最小时的旋转四元数，将四元数转换为旋转矩阵R；
5） 在旋转矩阵R被确定后，由平移向量t仅仅是两个点集的重心差异，可以通过两个坐标系中的重心点和旋转矩阵确定；
6） 根据式(0-3)，由点集Plk计算旋转后的点集P’lk。通过Plk与P’lk计算距离平方和值为fk+1。以连续两次距离平方和之差绝对值 作为叠代判断数值；
7） 当 时，ICP配準算法就停止叠代，否则重複1至6步，直到满足条件 后停止叠代。

ICP搜寻方法

ICP搜寻就近点的主要方法

Point to Point

1. Point to Point就近点搜寻法
Point to Point就近点搜寻法是ICP算法中最经典的一种方法。如图1a所示, Point to Point法根据源曲面上的一个点p，在目标曲面上找出对应于p点距离最近的q点。在这个方法中通常运用kd-tree的方法实现就近点搜寻。如图1b所示，pi是源曲麵点云数据中的一个点，Vi是生成目标曲面点云数据中距Pi最近的点。根据Vi点搜寻出在曲面上与Vi点相邻的点构成的三角形格网，计算pi点投影到每个三角形平面上的投影点qi的坐标。对于每个三角形来说，当投影点qi位于三角形内部，则距离最近点是搜寻的最近点，当投影点qi位于三角形外部，搜寻的就近点应位于三角形的两条边界上，Vi是该三角形到pi点的就近距离点。将每个三角形确定的就近距离点进行比较可获得一个最近点。

Point to Plane

2. Point to Plane就近点搜寻算法
如图1c所示，Point to Plane法是根据源曲面上的一个点p，在目标曲面上找出对应于p点一个最近的q点。搜寻算法是根据源曲面上p点的切平面的法线，确定发现于目标曲面的交点q’。根据目标曲面上q’点求出的过q’点切平面，然后求源曲面上p点到过q’点切平面的垂线的交点q。

Point to Projection

3. Point to Projection就近点搜寻算法
Point to Projection就近点搜寻法是一种快速的配準方法。如图1-d所示，图中Oq是扫描目标曲面的透视点的位置。Point to Projection法是根据源曲面上的一个点p和透视点Oq，在目标曲面上找出q点作为对应于p点的就近点。通过确定Oq点向p点方向的投影线与目标曲面的交点q，作为搜寻的就近点。

就近点搜寻图

图1 ICP算法就近点搜寻图
[1]Horn B K P. Closed-form solution of absolute orientation using unit quaternions[J]. Journal of the Optical Society of America A, 1987, 4(4):629-642.
[2] K. S. Arun, T. S Huang, S. D. Blostein. Least-squares fitting of two 3-D point sets[J]. IEEE Transactions on Pattern Analysis and Machine Intelligence, 1987. 9(5): 698-700.
[3] Paul J. Besl, Neil D. McKay. A method for registration of 3-D shapes[J]. IEEE Transactions on Pattern Analysis and Machine Intelligence, 1992. 14(2): 239-256.
[4] Y. Chen, G. Medioni. Object Modeling by Registration of Multiple Range Images[J]. Image and Vision Computing, 1992. 10: 145-155.
[5] R. Bergevin, M Soucy, H. Gagnon, et al. Towards a general multi-view registration technique[J]. IEEE Transactions on Pattern Analysis and Machine Intelligence, 1996. 18(5): 540-547.
[6] Andrew Edie Johnson, Sing Bing Kang. Registration and Integration of Textured 3D Data[J]. Image and Vision Computing, 1999. 17: 135-147.
[7] Natasha Gelfand, Leslie Ikemoto, Szymon Rusinkiewicz, et al. Geometrically Stable Sampling for the ICP Algorithm[A]//. Proceedings of Fourth International Conference on 3-D Digital Imaging and Modeling[C]. Stanford University, CA, USA, 2003: 260-267.
[8] 郑德华. ICP算法及其在建筑物扫描点云数据配準中的套用[J].测绘科学, 2007. 32(2).
[9] P.J. Besl, H.D. McKay. A Method for Registration of 3D Shape[J]. IEEE Transactions on Pattern Analysis and Machine Intelligence, 1992. 14(2): 239-256.

三维点云算法

三维雷射扫描技术的快速发展,使其在各个领域得到广泛套用。由于物理上的一些限制,一次三维雷射扫描不能获取扫描物体的全部数据,要对扫描点云进行拼接。,对最常用的ICP算法进行一系列研究,ICP算法的前提条件是具有一个良好的配準初值,文中在配準初值的选取上採用主成分分析法,为后续ICP算法的工作提供一个良好前提条件,增加点集预处理,点对查找上增加各种限制,採用kd-tree加速查找,以此对算法进行改进,并通过实例来验证本算法的有效性及合理性。
上一篇：Passat新领驭 2009款 2.0L MFI 自动尊享型 下一篇：H.贝可勒尔

生活常识

Copyright@2015-2025 www.aizhengw.cn 癌症网版板所有