迭代最近点算法

迭代最近点算法，几乎总是简称为 ICP，是一套把一团点平移、旋转，直到尽可能端正地落在另一团描述同一事物的点之上的方法。点云不过是空间里的一群点——对机器人来说，就是它的激光或深度传感器打到附近表面的那些位置。当两团这样的点云从略有不同的位置描绘同一个房间时，ICP 会找出那个能让它们彼此基本吻合的移动，而这个移动也正是机器人在两者之间所做的运动。

它之所以叫“迭代”，是因为它不断重复两个简单的步骤。第一步，对于正在移动的那团点里的每一个点，它在另一团点里找出最近的那个点，并姑且把这两个点当作同一处——这是对“哪个点配哪个点”的一个又快又粗的猜测。第二步，它算出那个能把所有这些猜出来的配对一起拉得最近的“平移加旋转”，并施加上去。此时两团点云贴合得更好了，于是“最近点”的猜测也随之改善；它再重复一遍，每跑一轮，两团点云就贴得更紧，直到几乎不再移动——这个稳定下来的位置就是答案。

ICP 是扫描匹配背后的标准引擎，也是激光雷达 SLAM 的支柱，因其只要从一个还不错的初始猜测出发，就既简单又精确而备受推崇。它的难处在于：它始终只把每个点和它当前的最近邻配对，所以如果两团点云一开始就相距很远、或扭得很厉害，它就可能锁定到错误的配对上，并自信地稳定在一个错误的答案里——这个陷阱叫做局部极小值。这也是为什么机器人通常会先喂给 ICP 一个粗略的初始估计（常常来自车轮计数或上一次扫描），再让它去把吻合度打磨好。