大盘点！汇总点云分割算法，涉及RANSAC、欧式聚类、区域增长等

窝窝乡村长

点云分割的目标是将点云数据中的点分成不同的组或类别，使每个组中的点都属于同一种物体或区域。根据空间，几何和纹理等特征对点云进行划分，使同一划分内的点云拥有相似的特征。点云分割的目的是分块，从而便于单独处理。分割过程有助于从各个方面分析场景，例如定位和识别对象、分类和特征提取。
作者：PCIPG-zzl | 来源：计算机视觉工坊
，备注：3D点云，拉你入群。文末附行业细分群。
点云的有效分割是许多应用的前提：

• 工业测量/逆向工程：对零件表面提前进行分割，再进行后续重建、计算特征等操作。
  
• 遥感领域：对地物进行提前分割，再进行分类识别等工作
  

点云分类（Point Cloud Classification）：点云分类是将点云中的每个点分配到预定义的类别或标签中的任务。点云分类可用于识别点云中的不同物体或地物，例如识别建筑物、树木、汽车等。为每个点分配一个语义标记。点云的分类是将点云分类到不同的点云集。同一个点云集具有相似或相同的属性，例如地面、树木、人等。点云分类也叫做点云语义分割。实例分割（Instance Segmentation）：实例分割是一种更高级的任务，它不仅要求识别点云中的不同物体或类别，还需要为每个物体中的每个点分配一个唯一的标识符，以区分不同实例。这使得实例分割能够精确地区分出多个相同类别的物体，例如在一个点云场景中区分出多辆汽车或多棵树。点云语义分割是指把一个大规模场景下的点云按照不同的类别给每个点云一个语义标签，比如城市高速公路，所有的路灯会有一个相同的语义标签，所有的路面会有 一个相同的语义标签，所有的树木会有同一个语义标签。点云实例分割是在语义分割的基础之上，把所有的路灯再一个一个分开，区别出来每一个路灯。这里也推荐「3D视觉工坊」新课程《三维点云处理：算法与实战汇总》。
（Random Sample Consensus）随机采样一致性算法，采用迭代的方式从一组包含离群的被观测数据中估算出数学模型的参数。RANSAC算法假设数据中包含正确数据和异常数据（或称为噪声），正确数据记为内点（inliers），异常数据记为外点（outliers）

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

• 要得到一个直线模型，需要两个点唯一确定一个直线方程。所以第一 步随机选择两个点。
  
• 通过这两个点，可以计算出这两个点所表示的模型方程y=ax+b。
  

• 将所有的数据点套到这个模型中计算误差。
  
• 找到所有满足误差阈值的点。
  

• 然后我们再重复1~4这个过程，直到达到一定迭代次数后，选出那个被 支持的最多的模型，作为问题的解。
  

RANSAC算法与最小二乘法区别RANSAC 算法：适用性：RANSAC主要用于处理包含噪音和异常值的数据集。它通过随机采样和迭代的方式来找到最佳拟合模型，忽略了外点的影响，因此在数据中含有大量噪音或少量异常值的情况下表现较好。步骤：RANSAC通过随机选择内点样本进行模型拟合，并通过计算内点和模型之间的误差来判断外点。它迭代地选择具有最大内点数的模型作为最终拟合模型。优点：鲁棒性较强，能够在存在噪音和异常值的情况下仍然得到合理的模型估计。最小二乘法：适用性：最小二乘法假设数据中的噪音较小，且异常值较少。它通过最小化数据点与模型之间的误差平方和来得到最佳拟合模型，适用于数据比较干净的情况。求解：最小二乘法可以直接求解或优化模型参数的解析解，对于线性问题尤其有效。然而，在存在较多噪音或异常值时，最小二乘法容易受到这些数据点的影响，导致估计结果不准确。优点：在数据相对干净，噪音较小的情况下，最小二乘法能够得到精确的模型估计。RANSAC算法被广泛应用在计算机视觉领域和数学领域，例如直线拟合、平面拟合、计算图像或点云间的变换矩阵、计算基础矩阵等方面，使用的非常多。总之，RANSAC和最小二乘法适用于不同类型的数据情况。RANSAC适用于含有噪音和异常值的数据，能够通过迭代的方式找到鲁棒性较强的模型。最小二乘法适用于相对干净的数据，能够得到精确的模型估计，但容易受到噪音和异常值的影响。在实际应用中，根据数据的特点选择合适的方法以获得准确的模型估计。
pcl::ModelCoefficients::Ptr coefficients(new pcl::ModelCoefficients);pcl::PointIndices::Ptr inliers(new pcl::PointIndices); //inliers用来存储直线上点的索引pcl::SACSegmentation seg;//创建一个分割器seg.setOptimizeCoefficients(true); //可选择配置，设置模型系数需要优化seg.setModelType(pcl::SACMODEL_LINE); //设置目标几何形状seg.setMethodType(pcl::SAC_RANSAC); //拟合方法：随机采样法seg.setDistanceThreshold(0.05); //设置误差容忍范围，也就是阈值seg.setMaxIterations(500); //最大迭代次数，不设置的话默认迭代50次seg.setInputCloud(cloud); //输入点云seg.segment(*inliers, *coefficients); //拟合点云欧式聚类算法（Euclidean Clustering）是一种将点云数据分割成不同聚类（簇）的算法。它是点云分割中的一种常用方法，旨在将距离比较近的点分为同一簇，从而识别出不同的物体或结构。这个算法主要适用于包含较小噪音和具有一定距离差异的点云数据。基本思想：

• 选择一个种子点（Seed Point）作为当前簇的起始点。
  
• 遍历所有未分类的点，计算它们与种子点的距离。如果距离小于设定的阈值，将其归为同一簇。
  
• 对于同一簇中的点，重复步骤2，将与当前簇内任一点距离小于阈值的点加入簇。
  
• 切换到下一个未分类的点，作为新的种子点，继续重复步骤2和3。
  
• 当所有点都被分类为某个簇，聚类过程结束。
  

pcl::search::KdTree::Ptr tree (new pcl::search::KdTree);tree->setInputCloud (cloud_filtered);std::vector cluster_indices;pcl::EuclideanClusterExtraction ec;ec.setClusterTolerance (0.02); // 2cmec.setMinClusterSize (100);ec.setMaxClusterSize (25000);ec.setSearchMethod (tree);ec.setInputCloud (cloud_filtered);ec.extract (cluster_indices);一个桌子的场景图经过欧式聚类算法效果如下图所示。

区域生长算法（Region Growing）是一种用于图像处理和分割的算法，主要用于将点云中的点分成不同的区域，从而识别出具有相似特性的区域。区域生长算法基于相似性原则，将相似度高的点聚集在一起，形成连续的区域。算法步骤：1.初始化：选择一个种子点，并将其标记为“已访问”。2.根据设定的相似性准则，计算当前点与种子的相似度。3.如果当前点与种子相似度超过设定阈值，则将其标记为当前区域的一部分，并将其加入当前区域。4.遍历当前点的邻居（相邻点），对每个邻居执行以下步骤：如果邻居未被访问过且与当前区域的相似度超过设定阈值，则将其标记为“已访问”并添加到当前区域。递归地对邻居的邻居进行相似性判断，将相似的像素或点添加到当前区域。5.重复步骤4，直到当前区域不能再生长为止。6.如果还存在未访问的点，选择一个未访问的点作为新的种子，重复上述步骤。7.当所有点都被分配到区域后，分割过程结束。这里也推荐「3D视觉工坊」新课程《三维点云处理：算法与实战汇总》。
pcl::RegionGrowing reg;reg.setMinClusterSize (50);reg.setMaxClusterSize (1000000);reg.setSearchMethod (tree);reg.setNumberOfNeighbours (30);reg.setInputCloud (cloud);reg.setIndices (indices);reg.setInputNormals (normals);reg.setSmoothnessThreshold (3.0 / 180.0 * M_PI);reg.setCurvatureThreshold (1.0);算法是针对小曲率变化面设计的，尤其适合对连续阶梯平面进行分割
https://blog.csdn.net/luolaihua2018/article/details/120113848https://pcl.readthedocs.io/projects/tutorials/en/master/index.html#sample-consensus

来源：http://www.yidianzixun.com/article/0qezs3j6
免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！