前言

点云分割算法广泛应用于激光遥感、无人驾驶、工业自动化领域，其原理是根据空间、几何和纹理等特征对点云进行划分，使同一划分内的点云拥有类似的特征。

一、点云分割算法简介

点云分割算法经过长时间的发展，目前大致可以分为基于随机采样一致的分割算法、基于聚类的分割算法和基于点云深度学习模型的算法。

1.1 基于RANSAC的点云分割

RANSAC算法是一种非常经典的点云拟合算法，同时可以根据拟合结果实现点云分割，常用于规则点云的分割，例如直线、平面、圆球等。
其基本原理前面写过，是通过把点云随机一个初始模型，把所有点分为内点和外点，并设定阈值，符合阈值的为内点，不符合的为外点，不断迭代，最终满足迭代条件从而实现点云分割的。

1.2 基于聚类的点云分割

聚类是机器学习中非常重要的概念，属于无监督学习任务。
目前聚类的方法有很多，但算法基本原理都是类似的，即不需要标签，仅依靠数据的特征把数据分为不同的类或者簇，使类内的元素的相似性尽可能的大，类间元素相似性则尽可能小。
二维图像聚类个人比较熟悉K-均值和高斯混合聚类。
点云聚类分割最简单的则是欧式聚类分割，除了该算法，还有基于区域生长、图割法、超体素分割等方法。

1.2.1 欧式聚类分割

欧式聚类分割和K-均值聚类算法的思路很相似：
1：首先设定初始点p，用Kd-tree进行半径为r的点云搜索，得到初始点集合Q。
2：在Q中选择新的种子点，进行步骤1，若Q不再新增加点，且聚类总点数在设定的点云数量范围内，则Q聚类完成，否则重新开始1。
3：在剩余点云中继续选点执行上述步骤。

1.3 基于深度学习的点云分割

目前基于深度学习的点云分割模型的工作已有很多，流行的包括PointNet、PointNet++、RandLA-Net、PointConv、PCT和PointCNN等，一篇综述介绍的比较好。
基于深度学习的三维点云分割综述
目前该领域的研究主要应用于无人驾驶领域。

二、算法示例

2.1 基于RANSAC的平面分割

pcl::PointCloud<pcl::PointXYZ> cloud;
	//填充点云数据
	cloud.width = 1000;
	cloud.height = 1;
	cloud.points.resize(cloud.width * cloud.height);
	for (size_t i = 0; i < cloud.points.size(); ++i)
	{
		cloud.points[i].x = 1024 * rand() / (RAND_MAX + 1.0f);
		cloud.points[i].y = 1024 * rand() / (RAND_MAX + 1.0f);
		cloud.points[i].z = 1.0;
	}
	//设置局外点
	cloud.points[23].z = 20;
	cloud.points[203].z = -120.0;
	cloud.points[106].z = -60;
	cloud.points[400].z = 5;
	cloud.points[921].z = 3;
	cloud.points[8].z = 120.0;
	cloud.points[103].z = -220.0;
	cloud.points[206].z = -310;
	cloud.points[300].z = 602;
	cloud.points[821].z = 405;

	pcl::ModelCoefficients::Ptr coefficients(new pcl::ModelCoefficients);
	pcl::PointIndices::Ptr inliers(new pcl::PointIndices);
	//创建分割对象
	pcl::SACSegmentation<pcl::PointXYZ> seg;
	seg.setOptimizeCoefficients(true);
	//设置参数
	seg.setModelType(pcl::SACMODEL_PLANE);
	seg.setMethodType(pcl::SAC_RANSAC);
	seg.setDistanceThreshold(0.01);
	seg.setInputCloud(cloud.makeShared());
	seg.segment(*inliers, *coefficients);
	if (inliers->indices.size() == 0)
	{
		PCL_ERROR("Could not estimate a planar model for the given dataset.");
	}
	//输出平面模型的系数
	std::cout << "Model coefficients: " << coefficients->values[0] << " "
		<< coefficients->values[1] << " "
		<< coefficients->values[2] << " "
		<< coefficients->values[3] << std::endl;
	std::cout << "Model inliers: " << inliers->indices.size() << std::endl;

2.2 欧式聚类

    pcl::search::KdTree<pcl::PointXYZ>::Ptr tree(new pcl::search::KdTree<pcl::PointXYZ>);
	tree->setInputCloud(cloud_filtered);//设置输入点云

	std::vector<pcl::PointIndices> cluster_indices;
	pcl::EuclideanClusterExtraction<pcl::PointXYZ> ecluster;//创建一个聚类对象
	ecluster.setClusterTolerance(0.02); //设置近邻搜索的搜索半径为2cm
	ecluster.setMinClusterSize(100);    //设置一个聚类需要的最少点数目为100
	ecluster.setMaxClusterSize(2000);  //设置一个聚类需要的最大点数目为2000
	ecluster.setSearchMethod(tree);     //设置点云的搜索机制
	ecluster.setInputCloud(cloud_filtered); //设置原始点云 
	ecluster.extract(cluster_indices);  //从点云中提取聚类

    int j = 0;
	for (std::vector<pcl::PointIndices>::const_iterator it = cluster_indices.begin(); it != cluster_indices.end(); ++it)
	{
		pcl::PointCloud<pcl::PointXYZ>::Ptr cloud_cluster(new pcl::PointCloud<pcl::PointXYZ>);
		for (std::vector<int>::const_iterator pit = it->indices.begin(); pit != it->indices.end(); pit++)
			cloud_cluster->points.push_back(cloud_filtered->points[*pit]); //*

		cloud_cluster->width = cloud_cluster->points.size();
		cloud_cluster->height = 1;
		cloud_cluster->is_dense = true;

		std::cout << "当前聚类 " << j << " 包含的点云数量: " << cloud_cluster->points.size() << " data points." << std::endl;
		std::stringstream ss;
		ss << "cloud_cluster_" << j << ".pcd";
		writer.write<pcl::PointXYZ>(ss.str(), *cloud_cluster, false); //*
		j++;
		viewer->addPointCloud(cloud_cluster, cluster_color, ss.str(), v2);
	}

2.3 基于PointNet++的点云分割

待续。。

总结