分类：
版权声明：本文为博主原创文章，未经博主允许不得转载。
最近在做点云匹配，需要用c++实现ICP算法，下面是简单理解，期待高手指正。
ICP算法能够使不同的坐标下的点云数据合并到同一个坐标系统中，首先是找到一个可用的变换，配准操作实际是要找到从坐标系1到坐标系2的一个刚性变换。
ICP算法本质上是基于最小二乘法的最优配准方法。该算法重复进行选择对应关系点对， 计算最优刚体变换，直到满足正确配准的收敛精度要求。
ICP 算法的目的是要找到待配准点云数据与参考云数据之间的旋转参数R和平移参数 T，使得两点数据之间满足某种度量准则下的最优匹配。
假设给两个三维点集 X1 和 X2，ICP方法的配准步骤如下：
第一步，计算X2中的每一个点在X1 点集中的对应近点；
第二步，求得使上述对应点对平均距离最小的刚体变换，求得平移参数和旋转参数；
第三步，对X2使用上一步求得的平移和旋转参数，得到新的变换点集；
第四步， 如果新的变换点集与参考点集满足两点集的平均距离小于某一给定阈值，则停止迭代计算，否则新的变换点集作为新的X2继续迭代，直到达到目标函数的要求。
最近点对查找：对应点的计算是整个配准过程中耗费时间最长的步骤，查找最近点，利用 k－d tree提高查找速度 K－d tree 法建立点的拓扑关系是基于二叉树的坐标轴分割，构造 k－d tree 的过程就是按照二叉树法则生成，首先按 X 轴寻找分割线，即计算所有点的x值的平均值，以最接近这个平均值的点的x值将空间分成两部分，然后在分成的子空间中按 Y 轴寻找分割线，将其各分成两部分，分割好的子空间在按X轴分割……依此类推，最后直到分割的区域内只有一个点。这样的分割过程就对应于一个二叉树，二叉树的分节点就对应一条分割线，而二叉树的每个叶子节点就对应一个点。这样点的拓扑关系就建立了。
******************
作者：hao_09
时间：2015/12/1
文章地址：http://blog.csdn.net/lsh_2013/article/details/50135045
===================================================
研究生课程系列文章参见索引《在信科的那些课》
基本原理
假定已给两个数据集P、Q， 
，给出两个点集的空间变换f使他们能进行空间匹配。这里的问题是，f为一未知函数，而且两点集中的点数不一定相同。解决这个问题使用的最多的方法是迭代最近点法（Iterative Closest Points Algorithm）。
基本思想是：根据某种几何特性对数据进行匹配，并设这些匹配点为假想的对应点，然后根据这种对应关系求解运动参数。再利用这些运动参数对数据进行变换。并利用同一几何特征，确定新的对应关系，重复上述过程。
迭代最近点法目标函数
，他们的欧式距离表示为：
，
