|
专栏名称: 3DCV
| 关注工业3D视觉、SLAM、自动驾驶技术，更专注3D视觉产业的信息传播和产品价值的创造，深度聚焦于3D视觉传感器、SLAM产品，使行业产品快速连接消费者。 |
目录
相关文章推荐
|
FT中文网 · 英伦传统出版业能否突围经济周期？ · 9 小时前 |
|
商业洞察 · 裁员上万人，又一汽车巨头扛不住了！ · 昨天 |
|
大港微生活 · 太突然！关闭近千家门店！ · 2 天前 |
|
|
大港微生活 · 太突然！关闭近千家门店！ · 2 天前 |
|
21世纪商业评论 · 勇敢的行动者：2024年度商业模式创新公司 · 2 天前 |
|
FT中文网 · iPhone神话在中国破灭 · 2 天前 |
正文
点击下方
卡片
，关注
「3DCV」
公众号
选择
星标
，干货第一时间送达
来源：https://yilingui.xyz/2019/11/20/191120_point_cloud_registration_icp/
编辑：3DCV
扫描下方二维码，加入
「3D视觉从入门到精通」知识星球
(
点开有惊喜
)
，星球内凝聚了众多3D视觉实战问题，以及各个模块的学习资料：
近20门独家秘制视频课程
、
最新顶会论文
、计算机视觉书籍
、
优质3D视觉算法源码
等。想要入门3D视觉、做项目、搞科研，欢迎扫码加入！
1 问题描述
点云配准（Point Cloud Registration）指的是输入两幅点云
点云配准可以分为粗配准（Coarse Registration）和精配准（Fine Registration）两步。粗配准指的是在两幅点云之间的变换完全未知的情况下进行较为粗糙的配准，目的主要是为精配准提供较好的变换初值；精配准则是给定一个初始变换，进一步优化得到更精确的变换。
目前应用最广泛的点云精配准算法是迭代最近点算法（Iterative Closest Point, ICP）及各种变种 ICP 算法。
2 算法描述
对于
R
∗
,
t
∗
=
arg
min
R
,
t
1
|
P
s
|
|
P
s
|
∑
i
=
1
|
|
p
i
t
−
(
R
⋅
p
i
s
+
t
)
|
|
2
这里
ICP 算法的直观想法如下：
-
如果我们知道两幅点云上点的对应关系，那么我们可以用 Least Squares 来求解 R, t 参数；
-
怎么知道点的对应关系呢？如果我们已经知道了一个大概靠谱的 R, t 参数，那么我们可以通过贪心的方式找两幅点云上点的对应关系（直接找距离最近的点作为对应点）。
ICP 算法实际上就是交替进行上述两个步骤，迭代进行计算，直到收敛。
ICP 一般算法流程为：
-
点云预处理
-
滤波、清理数据等
匹配
-
应用上一步求解出的变换，找最近点
加权
-
调整一些对应点对的权重
剔除不合理的对应点对
计算 loss
最小化 loss，求解当前最优变换
回到步骤 2. 进行迭代，直到收敛
整体上来看，ICP 把点云配准问题拆分成了两个子问题：
-
找最近点
-
找最优变换
2.1 找最近对应点（Find Closet Point）
利用初始
如果直接进行比较找最近邻点，需要进行两重循环，计算复杂度为
-
设置距离阈值，当点与点距离小于一定阈值就认为找到了对应点，不用遍历完整个点集；
-
使用 ANN(Approximate Nearest Neighbor) 加速查找，常用的有 KD-tree；KD-tree 建树的计算复杂度为
O(N log(N))，查找通常复杂度为O(log(N))（最坏情况下O(N)）。
2.2 求解最优变换（Find Best Transform）
对于 point-to-point ICP 问题，求最优变换是有闭形式解（closed-form solution）的，可以借助 SVD 分解来计算。
先给出结论，在已知点的对应关系的情况下，设
最优平移为：
下面分别给出证明。
2.2.1 计算最优平移
令
∂
F
∂
t
=
N
∑
i
=
1
2
(
R
⋅
p
i
s
+
t
−
p
i
t
)
=
2
n
t
+
2
R
N
∑
i
=
1
p
i
s
−
2
N
∑
i
=
1
p
i
t
令导数为 0 ，则有：
无论 R 取值如何，根据上式我们都可以求得最优的 t，使得 loss 最小。下面我们来推导最优旋转的计算公式。
2.2.2 计算最优旋转
经过最优平移的推导，我们知道无论旋转如何取值，都可以通过计算点云的质心来得到最优平移，为了下面计算上的简便，我们不妨不考虑平移的影响，先将源点云和目标点云都转换到质心坐标下，这也就是之前令
下面我们用
不考虑平移，则 loss 可以写成：
先化简
|
|
R
⋅
^
p
i
s
−
^
p
i
t
|
|
2
=
(
R
⋅
^
p
i
s
−
^
p
i
t
)
T
(
R
⋅
^
p
i
s
−
^
p
i
t
)
=
(
^
p
i
s
T
R
T
−
^
p
i
t
T
)
(
R
⋅
^
p
i
s
−
^
p
i
t
)
=
^
p
i
s
T
R
T
R
^
p
i
s
−
^
p
i
t
T
R
^
p
i
s
−
^
p
i
s
T
R
T
^
p
i
t
+
^
p
i
t
T
^
p
i
t
=
|
|
^
p
i
s
|
|
2
+
|
|
^
p
i
t
|
|
2
−
^
p
i
t
T
R
^
p
i
s
−
^
p
i
s
T
R
T
^
p
i
t
=
|
|
^
p
i
s
|
|
2
+
|
|
^
p
i
t
|
|
2
−
2
^
p
i
t
T
R
^
p
i
s
这里利用到了
由于点的坐标是确定的(和 R 无关)，所以最小化原 loss 等价于求：
也即为求：
注意到
则问题转化为：
根据 trace 的性质
还记得前面定义的矩阵 H 和其 SVD 分解吗？带入上式得到：
t
r
a
c
e
(
P
T
t
R
P
s
)
=
t
r
a
c
e
(
R
P
s
P
T
t
)
=
t
r
a
c
e
(
R
H
)
=
t
r
a
c
e
(
R
U
Σ
V
T
)
=
t
r
a
c
e
(
Σ
V
T
R
U
)
注意这里
请到「今天看啥」查看全文
推荐文章
|
|
FT中文网 · 英伦传统出版业能否突围经济周期？ 9 小时前 |
|
|
商业洞察 · 裁员上万人，又一汽车巨头扛不住了！ 昨天 |
|
|
大港微生活 · 太突然！关闭近千家门店！ 2 天前 |
|
|
大港微生活 · 太突然！关闭近千家门店！ 2 天前 |
|
|
21世纪商业评论 · 勇敢的行动者：2024年度商业模式创新公司 2 天前 |
|
|
FT中文网 · iPhone神话在中国破灭 2 天前 |
|
TechTarget · 灾难恢复杠杆：DRaaS与成本控制之间的角力 7 年前 |
|
公主岭帮 · 送走冰雹又来暴雨，农村柴火垛像航空母舰一样飘走··· 7 年前 |
|
开智学堂 · 你会编程，他们不会，太酷了 7 年前 |
|
最绘画 · 最具诗意油画家 | 曹力 7 年前 |
|
数盟 · 大数据与AI的融合，对于人类来说究竟是促进发展，还是加速灭亡？ 7 年前 |