来自分享

这是一位公众号关注者经过一段时间的整理与努力发出了一篇论文，在我的追问与交流下，让这位学生写了一篇总结分享给大家，再次感谢吧，同时有觉得对你很受用的话，请点赞支持！

以下就是作者的分享的内容：

最近学习平面检测以及障碍物检测方面的问题，利用点云数据检测平面以及不同形状的物体。我要实现的有两个：

第一、对于只有平面特征的场景，要检测出不同的平面。比如只存在正方形的场景，要检测出正方形的不同平面。

第二对于既有平面又有曲面特征的场景，则要将不同的特征分别检测出来。比如场景中有桌子平面，圆柱体以及正方体，则这三者都要用不同的颜色区分。总之，是一个点云聚类的问题。

针对我提出的问题，现行算法主要分为三大类：RANSAC平面聚类，欧式聚类的方法，以及区域生长。为了找到最适合实时检测的算法并对算法进行改进，我对每一种算法都进行了学习。

首先是RANSAC算法，是一种迭代方法，用于从一组包含异常值的观察数据中估计数学模型的参数，当异常值对估计值无任何影响时。因此，它也可以解释为异常值检测方法。在某种意义上说，它是一种非确定性算法，它只能以一定的概率产生合理的结果，随着更多的迭代被允许，这种概率增加。该算法首先由Fischler和Bolles 于1981年在SRI国际公布。他们使用RANSAC来解决位置确定问题（LDP）一个基本的假设是，数据由“内部值”组成，即其分布可以通过某些模型参数集来解释，尽管可能会受到噪声的影响，也就是数据不符合模型的“异常值”。异常值可以来自于噪声的极值，或来自对数据解释的错误测量或不正确的假设。RANSAC还假设，给定（通常是小的）集合的内在因素，存在可以估计最佳地解释或拟合该数据的模型的参数的过程。但是RANSAC算法存在的最大问题是使用范围受限，最实用于只有平面特征的数据，同时由于是一种迭代的算法，因此算法的准确性依赖迭代的次数。

再者是欧式聚类的方法，聚类方法需要将无组织点云模型 划分为较小的部分，从而大大减少整体处理时间。欧几里德意义上的简单数据聚类方法可以通过使用固定宽度框或更一般地八叉树数据结构的空间的3D网格细分来实现。这种特定的表示非常快速地构建，并且对于需要占用空间的体积表示或者可以用不同结构近似的每个所得到的3D框（或八叉树叶）中的数据的情况是有用的。然而，在更一般的意义上，我们可以利用最近的邻居并实现与洪泛填充算法基本相似的聚类技术。这种方法对于具有复杂特征的场景，分类效果会特别的差。

我重点学习的区域生长的方法，首先这种算法的使用范围很广，在机器人导航以及复杂场景的重建中都有相应的应用，这也展示了这种方法的使用范围。比较早的区域生长算法有基于法线向量的方法，可以分为以下几步：

1.种子周围的点和种子相比

2法线方向是否足够相近

3曲率是否足够小

4如果满足1，2则该点可用做种子

5如果只满足1，则归类而不做种

6从某个种子出发，其“子种子”不再出现则一类聚集完成

7类的规模既不能太大也不能太小

当然在此基础上有了很多改进，比如加入一些控制分割效果的参数，平滑参数等。随着深度相机的普及，也提出了基于彩色信息的区域分割，显而易见，这种点云除了结构信息之外，还存在颜色信息。将物体通过颜色分类，是人类在辨认果实的过程中进化出的能力，颜色信息可以很好的将复杂场景中的特殊物体分割出来。而颜色点云也并不那么遥不可及，Xbox Kinect就可以轻松的捕捉颜色点云。

基于颜色的区域生长分割原理上和基于曲率，法线的分割方法是一致的。只不过比较目标换成了颜色，去掉了点云规模上限的限制。可以认为，同一个颜色且挨得近，是一类的可能性很大，不需要上限来限制。所以这种方式比较适合用于室内场景分割。尤其是复杂室内场景，颜色分割可以轻松的将连续的场景点云变成不同的物体。哪怕是高低不平的地面，没法用采样一致分割器抽掉，颜色分割算法同样能完成分割任务。但是目前为止，这种算法应用的也是比较少。比如一个有图案的杯子，我们的目的是把杯子曲面分割出来，将杯子盖子分割成另一类，但是应用基于颜色的分类方法，很容易把杯子曲面分割成很多不同的类。所以我觉得颜色信息是比较重要的信息但是怎么利用颜色信息是比较重要的。

综合比较，最后我选择是基于法线的区域生长。基于法线的区域生长，最重要的参数是条件收缩参数，选择不同的参数直接会对分割结果产生影响。经过多次的调试，当条件收缩参数选择过大则会减少分割聚类数目，当条件收缩参数选择过小，则会使分割类数过多。因此，目前很多算法是对收缩条件进行了改进。同时，算法在进行法线估计的时候要对每一个点进行k邻近搜索，目前存在的算法有octree,kD-tree,已经octree和KD-tree相结合的方法，从实现的效果上来说，octree 的方法速度上并不占优势，KD-tree和octree和KD-tree结合的方法在不同的场景中使用效果是不同的。