[文章]

机器视觉之ICP算法和RANSAC算法

2019-6-19 08:00:00

3193 机器视觉算法

临时研究了下机器视觉两个基本算法的算法原理，可能有理解错误的地方，希望发现了告诉我一下
主要是了解思想，就不写具体的计算公式之类的了
（一） ICP算法（Iterative Closest Point迭代最近点）
ICP（Iterative Closest Point迭代最近点）算法是一种点集对点集配准方法，如下图1
如下图，假设PR（红色块）和RB（蓝色块）是两个点集，该算法就是计算怎么把PB平移旋转，使PB和PR尽量重叠，建立模型的

（图1）
ICP是改进自对应点集配准算法的
对应点集配准算法是假设一个理想状况，将一个模型点云数据X（如上图的PB）利用四元数

旋转，并平移

得到点云P（类似于上图的PR）。而对应点集配准算法主要就是怎么计算出qR和qT的，知道这两个就可以匹配点云了。
但是对应点集配准算法的前提条件是计算中的点云数据PB和PR的元素一一对应，这个条件在现实里因误差等问题，不太可能实线，所以就有了ICP算法

ICP算法是从源点云上的（PB）每个点先计算出目标点云（PR）的每个点的距离，使每个点和目标云的最近点匹配，（记得这种映射方式叫满射吧）
这样满足了对应点集配准算法的前提条件、每个点都有了对应的映射点，则可以按照对应点集配准算法计算，但因为这个是假设，所以需要重复迭代运行上述过程，直到均方差误差小于某个阀值。

也就是说每次迭代，整个模型是靠近一点，每次都重新找最近点，然后再根据对应点集批准算法算一次，比较均方差误差，如果不满足就继续迭代

（二）RANSAC算法（RANdom SAmple Consensus随机抽样一致）
它可以从一组包含“局外点”的观测数据集中，通过迭代方式估计数学模型的参数。它是一种不确定的算法——它有一定的概率得出一个合理的结果；为了提高概率必须提高迭代次数。该算法最早由Fischler和Bolles于1981年提出。
光看文字还是太抽象了，我们再用图描述
RANSAC的基本假设是：
（1）数据由“局内点”组成，例如：数据的分布可以用一些模型参数来解释；
（2）“局外点”是不能适应该模型的数据；
（3）除此之外的数据属于噪声。
而下图二里面、蓝色部分为局内点，而红色部分就是局外点，而这个算法要算出的就是蓝色部分那个模型的参数

（图二）
RANSAC算法的输入是一组观测数据，一个可以解释或者适应于观测数据的参数化模型，一些可信的参数。
在上图二中  左半部分灰色的点为观测数据，一个可以解释或者适应于观测数据的参数化模型我们可以在这个图定义为一条直线，如y=kx + b；
一些可信的参数指的就是指定的局内点范围。而k，和b就是我们需要用RANSAC算法求出来的
RANSAC通过反复选择数据中的一组随机子集来达成目标。被选取的子集被假设为局内点，并用下述方法进行验证：
　　1.有一个模型适应于假设的局内点，即所有的未知参数都能从假设的局内点计算得出。
　　2.用1中得到的模型去测试所有的其它数据，如果某个点适用于估计的模型，认为它也是局内点。
   3.如果有足够多的点被归类为假设的局内点，那么估计的模型就足够合理。
   4.然后，用所有假设的局内点去重新估计模型，因为它仅仅被初始的假设局内点估计过。
   5.最后，通过估计局内点与模型的错误率来评估模型。
这个过程被重复执行固定的次数，每次产生的模型要么因为局内点太少而被舍弃，要么因为比现有的模型更好而被选用。
这个算法用图二的例子说明就是先随机找到内点，计算k1和b1，再用这个模型算其他内点是不是也满足y=k1x+b2，评估模型
再跟后面的两个随机的内点算出来的k2和b2比较模型评估值，不停迭代最后找到最优点

我再用图一的模型说明一下RANSAC算法

（图1）
RANSAC算法的输入是一组观测数据，一个可以解释或者适应于观测数据的参数化模型，一些可信的参数。
模型对应的是空间中一个点云数据到另外一个点云数据的旋转以及平移。
第一步随机得到的是一个点云中的点对作，利用其不变特征（两点距离，两点法向量夹角）作为哈希表的索引值搜索另一个点云中的一对对应点对，然后计算得到旋转及平移的参数值。
然后适用变换，找到其他局内点，并在找到局内点之后重新计算旋转及平移为下一个状态。
然后迭代上述过程，找到最终的位置
其中观测数据就是PB，一个可以解释或者适应于观测数据的参数化模型是四元数

旋转，并平移

可信的参数是两个点对的不变特征（两点距离，两点法向量夹角）

也就是说用RANSAC算法是从PB找一个随机的点对计算不变特征，找目标点云PR里特征最像的来匹配，计算qR和qT

RANSAC算法成立的条件里主要是先要有一个模型和确定的特征，用确定的特征计算模型的具体参数
RANSAC算法貌似可以应用很多地方，这个相比ICP算法，更接近于一种算法思想吧