点云分割方法综述_对于密度不均匀的点云分割算法

参考：PCL中各种点云分割方法

粗配准、精配准-算法概述

 基于传统方法点云分割以及PCL中分割模块

点云各种分割方法--pcl分割的模块汇总

点云数据集：

链接：百度网盘 请输入提取码
提取码：h121

• 在图像分割中常常用到前景与背景的分割处理，而在点云处理中，对于给定点云数据，分割的目标是将具有相似特征的点聚类成均匀区域，根据分割结果应用于各个方面的场景分析，一般的方法是根据输入点云的网格构建图形，使用边界线的法线，平滑度或者是凹凸性等信息进行聚类分割。
• 分割的方法（可应用于2D图像和3D点云数据）：凹凸性分割，分水岭分析，层次聚类，区域增长以及频谱聚类
• 基于传统的方法：Graph Cuts，包含了Normalized Cuts和Min Cuts 

点云分割的六类方法：

①基于**属性**的分割算法：使用点云属性作为**聚类阈值**得到分割结果，过于依赖点云密度且相当耗时；

②基于**图**的分割算法：利用点云的数据结构构造图，用权值表示点之间的相似性，利用权值进行点云分割，分割精确度高，但是分割效率低；

③ 基于**模型**的分割算法：将点云拟合成球、圆柱等数学模型，分割范围有限，对于复杂场景点云分割效果欠佳；

④基于**边缘检测**的方法：通过计算梯度、检测表面上单位法向量方向的变化来拟合线段等方法检测点云区域的**边界**来获取分割区域，分割速度快，但是分割准确率低，且易受噪声干扰；

⑤ 基于**机器学习**的分割算法：利用机器学习算法分割，需离线训练，而且需要足够的训练集；

⑥ 基于**区域生长**的分割算法：通过选取种子点，以**法向量夹角**或**曲率**作为阈值**进行区域生长**，能够保持良好的边界性与区域连通性，分割效率高，但算法性能**依赖于种子选取**。

分为：种子区域方法（自下而上）和非种子区域方法（自上而下）

种子区域：选多个种子作为起始点，添加种子邻域点然后逐渐形成点云区域。包含：每个点的曲率识别种子点－》标准(点的相似度和点云表面相似度)来生长种子点。特点：高度依赖选定的种子点。 Pcl提出基于欧式聚类的区域增长方式。欧式聚类的缺点：没有初始化种子系统，没有欠分割和过分割的控制，效率低。

非种子区域：所有点都分为一个区域，然后细分为更小的区域。存在的困难：决定细分的位置和方式。它们需要大量先验知识例如对象模型、区域数量等，而这些先验知识在复杂场景中通常是未知的。

一、点云分割算法应具有的属性

1. 当点云数据的特征数量↑，应具有鲁棒性
2. 分割要能够根据相邻信息推断出稀疏点云中，点的属性或判定出这些点云属于哪个标签
3. 分割算法适用于不同扫描器。不同场景下不同扫描仪应具不同属性、不同点云质量、不同稀疏性

二、点云分割的挑战

• 点云数据虽然可以确定3D对象的形状，大小和一些其他属性，但是3D点云通常由于传感器的限制，数据是嘈杂稀疏且无序的，比如激光雷达线性和角速率的变化，点的采集密度也是不均匀的，此外点云数据的表面形状可以是任意的，是没有数据统计分布呈现出来的。所以这就给点云的分割带来一系列的问题。        ／／三维点云分割是将同属性的点云物体分割出来，以便于单独对该点云物体处理，但是由于点云数据是一种高冗余度，且不均匀的数据结构，所以点云分割具有一定挑战性。

三、传统点云分割算法

• 基于边缘的方法，基于区域的方法，基于属性的方法，基于模型的方法和基于图优化的方法。
  

1.基于边缘

边缘是描述点云物体形状的基本特征，这种方法检测点云一些区域的边界来获取分割区域，这些方法的原理是定位出边缘点的强度变化。

有些论文提出的方法：
01.通过计算梯度，检测表面上单位法向量方向的变化来拟合线段。
02.基于扫描线的分组进行快速分割。

总结：基于边缘的方法虽然分割速度比较快但是准确度不能保证，因为边缘对于噪声和不均匀的或稀疏的点云非常敏感。

2.基于区域

基于区域的方法是使用邻域信息来将具有相似属性的附近点归类，以获得到分割区域，并区分出不同区域之间的差异性。这种方法比基于边缘的更准确，但存在过分割和欠分割和区域边界不确定的问题。研究者们将基于区域的方法分为两类：种子区域（或自下而上）方法和非种子区域（或自上而下）方法。

3.基于属性

该方法是基于点云数据的属性的一种鲁棒性较好的分割方法，这种方法一般包括了两个单独的步骤：（1）第一步，基于属性的计算；（2）第二步，将根据计算点的属性进行聚类。

这种聚类方法一般能适应空间关系和点云的各种属性，最终将不同的属性的点云分割出来。但是这种方法局限性在于他们高度依赖派生属性的质量，所以要求第一步能够精确的计算点云数据的属性，这样才会在第二步中根据属性的类别分割出最佳的效果。

有些论文提出的方法：
01.提出了一种基于特征空间聚类分析方法，使用一种自适应斜率的邻域系统导出法向量，使用点云数据的属性，例如距离、点密度、点在水平或者垂直方向的分布，来定义测量点之间的领域，然后将每个方向上的法向量的斜率和点邻域的数据之差作为聚类的属性，这种方法可以消除异常值和噪声的影响。

总结：将点云分割相同属性区域的高效、灵活准确。但依赖于点之间邻域的定义和点云数据的点密度。当输入点的多维属性时比较耗时。

4.基于模型

该方法是基于几何的形状比如球形、圆锥、平面和圆柱形来对点云进行分组，那么根据这些形状，具有相同的数学表示的点将会被分割为同一组点。

有些论文提出的方法：
01.ANSAC是强大的模型，用于检测直线、圆等数学特征。这种应用极为广泛且可以认为是模型拟合的最先进技术，在3D点云的分割中需要改进的方法都是继承了这种方法。

总结：这种方法在点云库中已经实现了基于线、平面、圆等各种模型。但在处理不同点云时具有不准确性。

5.基于图优化

在机器的应用中十分流行。FH算法、条件随机场CRF等。

总结：在复杂的城市环境中成功地分割点云，具有接近实时的性能。实时性不太好。

6、基于临近信息的点云分割

      分割给人最直观的影响大概就是邻居和我不一样。通过对比某点和其最近一点的某些特征，来实现点云的分割。图像所能提供的分割信息仅是灰度或RGB向量，而三维点云却能够提供更多的信息。故点云在分割上的优势是图像所无法比拟的。

        由于分割工作需要对点云的邻近点进行操作，不断对比和访问某个点的邻居，所以决定点云的相邻关系是非常重要的。对于Scan来说，邻居关系是天然的。但对于很多杂乱点云或者滤波，分割后的点云来说，邻居关系就已经被破坏了。确定一个点云之间的相邻关系可以通过“树”来完成，目前比较主流的方法包括：kdTree和OcTree，这两种方法各有特点。

6.1 kdTree---一种递归的邻近搜索策略

　　kdTree实际上包括两个部分：1.建立kdTree，2.在kdTree中查找。

        建立kdTree实际上是一个不断划分的过程，首先选择最sparse（稀疏、稀少）的维度，然后找到该维度上的中间点，垂直该维度做第一次划分。此时k维超平面被一分为二，在两个子平面中再找最sparse的维度，依次类推知道最后一个点也被划分。那么就形了一个不断二分的树。如图所示。 

        一般情况下，一个点的邻近点只需要在其父节点和子节点中搜索即可，大大缩小了邻近点的搜索规模。并且kdtree可以有效的对插入点进行判断其最近点在哪个位置。在很多情况下需要给出某个点，再查k临近点的编号，或者差某半径范围内的点。【点云是疏散的，分布很广泛，且没什么规律（如lidar测得的点云或双目视觉捕捉的点云）kdTree能更好的划分】

6.2 OcTree——

　　对于一个空间，如果某个角落里有个盒子我们却不知道在哪儿。显而易见的方法就是把空间化成8个卦限，然后询问在哪个卦限内。再将存在的卦限继续化成8个。意思大概就是太极生两仪，两仪生四象，四象生八卦，就这么一直划分下去，最后一定会确定一个非常小的空间。对于点云而言，只要将点云的立方体凸包用octree生成很多很多小的卦限，那么在相邻卦限里的点则为相邻点。【如果点云分布非常规整，是某个特定物体的点云模型，则应该使用ocTree，因为很容易求解凸包并且点与点之间相对距离无需再次比对父节点和子节点，更加明晰】

四、方法总结

• -以上将分割方法分为五类。但是，一般来说，有两种基本方法。
• -第一种方法是用纯数学模型和几何推理技术，如：区域增长或模型拟合，将线性和非线性模型拟合到点云数据。这种方法允许快速运行时间能实现良好的结果。这种方法的局限性在于在拟合物体时难以选择模型的大小，对噪声敏感并且在复杂场景中不能很好地工作。
• -第二种方法是用特征描述子的方法。从点云数据中提取3D特征，并使用机器学习技术来学习不同类别的对象类型，然后使用结果模型对所获取的数据进行分类。在复杂场景中，机器学习技术将优于纯粹基于几何推理的技术。原因是由于噪声、密度不均匀、点云数据中的遮挡，很难找到并将复杂的几何图元拟合到物体上。虽然机器学习技术可以提供更好的结果，但它们通常很慢并且依赖于特征提取过程的结果。