点云分割涉及将点云数据分组成不同的部分，这些部分具有相似的特征如空间、几何和纹理属性。点云语义分割进一步为每个点分配语义标签，使得同一分类的点云具有相同或相似属性。有效的点云分割是许多应用的前提，例如工业测量和逆向工程。经典点云分割方法包括随机采样一致方法（RANSAC）、欧式聚类分割、条件欧式聚类分割、基于区域生长的分割等。

点云分割与点云语义分割

简单来说，点云分割只是单纯地把一些部分分为一类，但是没有实际分类的意义，而点云语义分割则是给每个点云指定了标签。

点云分割：根据空间，几何和纹理等特征点进行划分，是同一划分内的点云拥有相似的特征。 点云分割的目的是分块，从而便于单独处理。

点云语义分割：为每个点分配一个语义标记。点云的分类是将点云分类到不同的点云集，同一个点云集具有相似或相同的属性，例如地面，树木，人等。也叫做点云语义分割。

点云的有效分割是许多应用的前提，例如在工业测量/逆向工程领域，对零件表面提前进行分割，再进行后续重建、计算特征等操作。

经典点云分割方法

• 随机采样一致方法（RANSAC）
• 欧式聚类分割方法
• 条件欧式聚类分割
• 基于区域生长的分割
• 基于颜色的区域生长分割
• 最小图割的分割
• 基于法线微分的分割
• 基于超体素的分割

随机采样一致方法（RANSAC）

采用迭代的方式从一组包含离群的被观测数据中估算出数学模型的参数。RANSAC算法假设数据中包含正确数据和异常数据（或称为噪声）。

该算法核心思想就是随机性和假设性，随机性是根据正确数据出现概率去随机选取抽样数据，根据大数定律，随机性模拟可以近似得到正确结果。假设性是假设选取出的抽样数据都是正确数据，然后用这些正确数据通过问题满足的模型，去计算其他点 ，然后对这次结果进行一个评分。

算法的流程如下：

1. 要得到一个直线模型，需要两个点唯一确定一个直线方程。所以第一步随机选择两个点。
2. 通过这两个点，可以计算出这两个点所表示的模型方程y=ax+b。
3. 将所有的数据点套到这个模型中计算误差。
4. 找到所有满足误差阈值的点。
5. 然后我们再重复1~4这个过程，直到达到一定迭代次数后，选出那个被支持的最多的模型，作为问题的解。

最小二乘法尽量去适应包括局外点在内的所有点。相反，RANSAC能得出一个仅仅用局内点计算出模型，并且概率还足够高。

但是，RANSAC并不能保证结果一定正确，为了保证算法有足够高的合理概率，必须小心的选择算法的参数（参数配置）。

经实验验证，对于包含80%误差的数据集，RANSAC的效果远优于直接的最小二乘法。

PCL中的RANSAC模块

PCL中的 Sample_consensus库实现了随机采样一致性及其泛化估计算法，以及例如平面、柱面等各种常见几何模型，用不同的估计算法和不同的几何模型自由结合估算点云中隐含的具体几何模型的系数，实现点云中所处的几何模型的分割。

优点：避免噪声点对拟合结果的干扰。

缺点：由于计算结果的不确定性，迭代次数可能过高，对于密集点云来讲，计算时间过长，需要进行预处理后再进行拟合过程，但同样会损失时间。

PCL中支持的几何模型（来源于网络，没仔细推敲《机器视觉PCL学习笔记》）：

欧式聚类

主要用于分割离群点。

欧式聚类的原理非常简单，就是以一个点开始，设置一个距离，小于这个距离的，则认为是同一个类型，大于这个距离的则不是同一个目标，找到附近的点之后再重复上述步骤，直到找不到最近的点为止，这样就得到了一个簇，依次类推，迭代点云中其它的点，最后点云就会分割成一个个的簇。

欧式聚类需要注意2点。

1. 在聚类之前需要去除平面，自动驾驶中大部分情况下需要去除地面，不然会把所有的点云都连起来。
2. 建立索引，为了加快查找最近的点，需要在查找之前就根据点云建立KD-Tree，用于提高效率。

参考资料：点云聚类算法一（欧式聚类）

条件欧式聚类

与其他分割方法不同的是该方法的聚类约束条件（欧式距离、平滑度、RGB颜色等）可以由用户自己定义，即当搜索到一个近邻点时，用户可以自定义该邻域点是否合并到当前聚类的条件。

区域生长算法

区域生长算法是一种常用于点云数据处理中的分割算法，它的基本原理是从一组种子点出发，逐步将邻近的点加入到相应的区域中去，直到满足某种停止条件。这个过程中通常需要考虑点云的几何特性，比如点之间的距离、表面法向量的一致性等。

区域生长算法的关键步骤如下：

1. 选择种子点：首先在点云中选择一个或多个初始点作为种子点。这些种子点可以是随机选择的，也可以基于某些特定的属性，比如点的密度、曲率等。
2. 邻域搜索：对于每个种子点，搜索其周围的邻近点。这个搜索可以基于点之间的距离（比如在一定的半径内），也可以基于k近邻算法。
3. 增长条件：对于找到的邻近点，根据一定的准则判断它们是否应该加入到当前区域中。这些准则可能包括点之间的距离、表面法向量的差异、颜色差异等。
4. 合并邻近点：满足增长条件的邻近点被加入到当前区域，并成为新的种子点，用于下一轮邻域搜索。
5. 重复步骤：重复步骤2到4，直到没有更多的点可以被加入到区域中，或者达到了预设的停止条件（比如区域的大小或点的数量）。
6. 处理所有点：一旦一个区域停止增长，选择新的种子点开始新一轮的区域生长，直到所有的点都被分配到某个区域中。

区域生长算法在处理大规模点云数据时特别有效，因为它能够在考虑局部结构的同时逐步构建出全局的区域分割。这种方法在处理噪声数据时也比较鲁棒，但需要合理选择增长条件和停止条件，以及处理好种子点的选择策略。

颜色区域生长分割

基于颜色的区域生长分割原理上和基于曲率，法线的分割方法是一致的，只不过比较目标换成了颜色。可以认为，同一个颜色且挨得近，是一类的可能性很大，比较适合用于室内场景分割。尤其是复杂室内场景，颜色分割可以轻松的将连续的场景点云变成不同的物体。哪怕是高低不平的地面，设法用采样一致分割器抽掉平面，颜色分割算法对不同的颜色的物体实现分割。

RGB的距离：

$$ CD(P_1,P_2)=\sqrt{(R_1-R_2)^2+(G_1-G_2)^2+(B_1-B_2)^2} $$

最小图割的分割

最小图割（Min-Cut）算法是一种用于点云分割的图论方法。它将点云分割问题转化为图割问题，即将一个图（在这里可以理解为点云的一个数学模型）划分为两个子图的问题，目的是使得划分的代价（割的大小）最小。这里的“代价”通常是指边的权重，而在点云分割中，这些权重可以代表点之间的相似度。

最小图割算法的基本步骤如下：

1. 建立图模型：首先，将点云中的每个点看作图中的一个节点。然后，在节点之间根据它们的相似度建立边，这些相似度可以基于点之间的距离、颜色、法向量等属性。
2. 定义权重：为图中的每条边分配一个权重，权重较大意味着两个节点（即点云中的点）非常相似，不太应该被分割开。
3. 选择源点和汇点：在图中选择两个特殊的节点，分别称为源点（Source）和汇点（Sink）。这两个点代表了要分割的两个不同区域。
4. 计算最小割：通过某种算法（如Ford-Fulkerson算法）找到一种割的方式，使得从源点到汇点的路径被切断，同时切断的边的总权重（代价）最小。
5. 分割点云：根据最小割的结果，将点云分为两部分：一部分是与源点相连的点，另一部分是与汇点相连的点。

最小图割算法在处理有明显区分特征的点云数据时表现良好，例如在具有不同颜色或明显不同密度的区域之间进行分割。

它的优点是能够考虑全局信息，从而得到较为准确的分割结果。

然而，这种方法的计算复杂度可能比较高，特别是在处理大规模点云数据时。

法线微分分割

主要依赖于点云中点的表面法线信息。表面法线是指垂直于物体表面的单位向量，能够反映出物体表面的方向和形状。在点云数据中，每个点的法线可以通过其邻近点的几何分布计算得出。这种算法的基本原理是检测点云中法线变化较大的区域，因为这些区域通常对应于不同物体表面或物体的边缘。

算法的基本步骤如下：

1. 计算法线：首先，为点云中的每个点计算法线。这通常通过分析每个点周围邻近点的几何分布来完成，比如使用最小二乘法拟合邻近点的平面。
2. 法线微分：接着，计算每个点法线与其邻近点法线之间的差异。这种差异可以用来衡量表面的曲率或者折叠程度。
3. 确定分割阈值：选择一个阈值来确定法线差异的标准，这个阈值决定了何种程度的法线变化会被认为是一个分割点。
4. 分割点云：根据法线差异和设定的阈值，将点云划分为不同的区域。法线差异大于阈值的点被认为是分割边界。
5. 后处理：可能需要进行一些后处理步骤，比如平滑边界、去除噪声点等，以改善分割的效果。

基于法线微分的分割算法在处理具有复杂几何形状或不规则表面的点云时特别有效。它能够识别出因为几何形状变化导致的边界，如物体的棱角或曲面。

基于超体素的分割

"超体素"（supervoxel）是指在点云数据中形成的，较为均匀的、体积小于整个数据集但比单个数据点（如体素或点云中的点）大的聚类。这些超体素通常通过聚类方法生成，它们能够保留物体表面的细节，同时减少数据的规模，这样在后续的分割或识别任务中可以提高效率和精度。

$$ D=\sqrt{w_cD_c^2+\frac{w_sD_s^2}{3R_{seed}^2}+w_nD_n^2} $$

公式描述了一个基于超体素的分割算法的距离度量D，它是由色彩距离$D_c$、空间距离$D_s$和法线距离$D_n$的加权和构成的。这里的权重$w_c$、$w_s$和$w_n$分别对应色彩、空间和法线的重要性。算法通过这个度量来决定是否应该将相邻的体素合并为一个超体素。这个距离度量考虑了颜色、空间接近度和表面法线这三个重要特征，以更好地进行点云数据的聚类。

下图中，底部有一系列的体素，分别被标记为a到p。上面的数字1到9代表搜索和合并的顺序。例如，种子体素（Seed Voxels）首先搜索周围的体素，并根据上面的距离度量D决定是否与其合并。在此图示中，你可以看到超体素的生成过程：首先处理中心的种子体素，然后根据距离度量决定合并周围体素的顺序，这样逐步构建出超体素。图中绿色箭头表示了合并超体素的方向，这显示了超体素是如何通过结合周围相似体素来成长的。