迭代最近点算法综述
摘要:三维点集配准问题是计算机技术中的一个极其重要的问题,作为解决三维点集配准问题的一个应用
较为广泛的算法,ICP 算法得到了研究者的关注,本文以一种全新的思路从配准元素的选择、配准策
略的确定和误差函数的求解等 3 个方面对三维点集配准的 ICP 算法的各种改进和优化进行了分类和总
结。
关键词:三维点集;迭代最近点;配准
1 引言
在计算机应用领域,三维点集配准是一个非常重要的中间步骤,它在表面重建、三维物
体识别、相机定位等问题中有着极其重要的应用
[1]
。对于三维点集配准问题,研究者提出了
很多解决方案,如点标记法、自旋图像、主曲率方法、遗传算法、随机采样一致性算法等等,
这些算法各有特色,在许多特定的情况下能够解决配准的问题。但是应用最广泛的,影响最
大的还是由 Besl 和 Mckay 在 1992 年提出的迭代最近点算法
[2]
(Iterative Closest Point,
ICP),它是基于纯粹几何模型的三维物体对准算法,由于它的强大功能以及高的精确度,
很快就成为了曲面配准中的主流算法。
随着 ICP 算法的广泛应用,许多研究者对 ICP 算法做了详细的研究,分析了该算法的
缺陷和特点,提出了许多有价值的改进,推动了这一重要算法的发展。本文着眼于 ICP 算
法的发展历程,详细介绍了 ICP 算法的基本原理,总结其发展和改进的过程,对于该算法
的各个阶段的发展和变化做了简单的论述。
2 ICP 算法原理
2.1 ICP 算法原理
ICP 算法主要用于三维物体的配准问题,可以理解为:给定两个来至不同坐标系的三维
数据点集,找出两个点集的空间变换,以便它们能进行空间匹配。假定用{
P
i
,i
=
1,2,…,N
}表
示空间第一个点集,第二个点集的对齐匹配变换为使下式的目标函数最小
[3]
。
f
(
R,t
)
=
N
i
=
1
||
Q
i
―
(R
P
i
+
T)||
2
=
min
(1)
ICP 算法的实质是基于最小二乘法的最优匹配算法,它重复进行“确定对应关系点集—
计算最优刚体变换”的过程,直到某个表示正确匹配的收敛准则得到满足。ICP 算法的母
的是找到目标点集与参考点之间的旋转 R 和平移 T 变换,使得两匹配数据中间满足某种程
度度量准则下的最优匹配。假设目标点集 P 的坐标为{
P
i
,i
=
1,2,…,
N
P
}及参考点集 Q 的坐标
为{
Q
i
,i
=
1,2,…,
N
q
},在第 k 次迭代中计算与点集 P 的坐标相对应的对应点坐标为
{
Q
i
k
,i
=
1,2,…,
N
P
}
,计算 P 与
Q
k
之间的变换矩阵并对原变换进行更新,直到数据间平均距离小于
评论3