传统方法的点云分割以及PCL中分割模块
有兴趣的小伙伴可以查阅历史文章，同时也欢迎小伙伴们积极分享与公众号主题相关的文章。在公众号的菜单栏开放了企业招聘。有需要的可以按要求发布招聘信息，你也可以把身边的HR推荐给群主，参与进来。
摘要
三维点云分割是将同属性的点云物体分割出来，以便于单独对该点云物体处理，但是由于点云数据是一种高冗余度，且不均匀的数据结构，所以点云分割具有一定挑战性。
点云库于（PCL）2011年推出以来，得到行业广泛的应用，该库包含了最先进的3D感知算法，并包含了LIDAR和三维扫描仪的接口，这使得点云库PCL在机器人领域持续不断的发展壮大起来。至今为止已经更新到了1.9.1版本。在图像分割中常常用到前景与背景的分割处理，而在点云处理中，对于给定点云数据，分割的目标是将具有相似特征的点聚类成均匀区域，根据分割结果应用于各个方面的场景分析，一般的方法时根据输入点云的网格构建图形，使用边界线的法线，平滑度或者是凹凸性等信息进行聚类分割，在文章【1】中调查了分割的方法有：凹凸性分割，分水岭分析，层次聚类，区域增长以及频谱聚类。这些方法不仅是应用图像，也广泛的应用于点云数据的分割。
在计算机视觉中，2D图像的分割是一个很经典的问题，并且已经有着十几年的研究历史，其中基于传统的方法比较流行有Graph Cuts[2],包含了Normalized Cuts和Min Cuts 这些方法的思想同样适应于3D点云的分割，并且这部分内容在PCL中都已经开源。
1.点云分割算法的属性
（1）鲁棒性，比如树木是具有与汽车相区别的特征的，当点云数据的特征数量增加时，分割算法应该具有一定的鲁棒性，能够学习如何自动的区分它们。
（2）其次分割应该能够根据其相邻的信息推断出稀疏点云中这些点的属性或者判定出属于哪个标签。
（3）分割算法应该能适用于不同的扫描器，即便是相同的场景在不同的扫描仪生成出的点云也是具有不同的属性的，并且产生点云的质量以及稀疏性的也是不一样的。
2.点云分割的挑战
点云数据虽然可以确定3D对象的形状，大小和一些其他属性，但是3D点云通常由于传感器的限制，数据是嘈杂稀疏且无序的，比如激光雷达线性和角速率的变化，点的采集密度也是不均匀的，此外点云数据的表面形状可以是任意的，是没有数据统计分布呈现出来的。所以这就给点云的分割带来一系列的问题。
3.数据集介绍：
Example scenes of (a) Cornell RGBD dataset, (b) VMR-Oakland dataset, © KITTI dataset, and (d) Robotic 3D Scan Repository
如图1 这些数据可分为两类：Kinect捕获的室内数据集，以及由激光扫描仪（比如lidar）捕获的室外数据集，将分割算法应用于这些公共数据集使研究者们更加的了解分割算法的优缺点。
（1）Cornell RGBD数据集： 该数据集具有52个标签的具有RGB值的点云的室内场（24个标记为办公场景和28个标记的家庭场景）。使用RGBDSLAM [45]从原始RGB-D图像创建点云数据。该数据集由大约550个视图组成，具有2495个标签对应着27个种类的物体。
（2）VMR-Oakland数据集： 该数据集是通过移动平台从CMU园区收集的带有标记点云数据。使用激光扫描仪收集点云并以文本格式保存，每行中写入三个实值坐标。并且提供训练集，和测试集。
（3） KITTI数据集：该数据集包括由360°Velodyne激光扫描仪捕获的大量无组织点云数据。它是具有手动标记真值框的，如汽车，行人，电车，卡车和自行车等户外的真值边界框，用于训练集。
（4）Robotic 3D Scan Repository： 该数据集为室内和室外环境提供3D点云数据集的集合。一些数据集包括热量和颜色信息。这是3D点云数据的巨大集合，不仅可用于分割，还可用于不同其他算法使用。但是，这些数据集尚未标记，在将它们用作分割算法的输入之前，可能是需要预处理步骤。
4.点云分割算法介绍
接下里将介绍五种传统的分割算法：基于边缘的方法，基于区域的方法，基于属性的方法，基于模型的方法和基于图优化的方法。
01
基于边缘的方法：边缘是描述点云物体形状的基本特征，这种方法检测点云一些区域的边界来获取分割区域，这些方法的原理是定位出边缘点的强度变化，论文【2】提出了一种边缘检测技术，通过计算梯度，检测表面上单位法向量方向的变化来拟合线段。论文【3】是基于扫描线的分组进行快速分割，基于边缘的方法虽然分割速度比较快但是准确度不能保证，因为边缘对于噪声和不均匀的或稀疏的点云非常敏感。
02
基于区域分割方法：基于区域的方法使用邻域信息来将具有相似属性的附近点归类，以获得到分割区域，并区分出不同区域之间的差异性。 基于区域的方法比基于边缘的方法更准确。 但是他们在分割过度或不足以及在如何准确确定区域边界方面存在问题。 研究者们将基于区域的方法分为两类：种子区域（或自下而上）方法和非种子区域（或自上而下）方法。
种子区域方法： 基于种子的区域分割通过选择多个种子点来开始做分割，从这些种子点为起始点，通过添加种子的邻域点的方式逐渐形成点云区域，最初的算法是有论文【4】提出来，该算法主要包含了两个步骤：
（1）基于每个点的曲率识别种子点，
（2）根据预定标准，该标准可以是点的相似度和点云的表面的相似度来生长种子点。
这种方法对噪声点也非常敏感，并且耗时。但后续有很多基于这种方法的改进，比如对于激光雷达数据的区域增长的方法，提出了基于种子点的法向量和与生长平面的距离来生长种子点。种子区域方法高度依赖于选定的种子点。不准确选择种子点会影响分割过程，并可能导致分割不足或过度。选择种子点以及控制生长过程是耗时的。分割结果可能对所选的兼容性阈值敏感。另一个困难是决定是否在给定区域中添加点，因为这种方法对点云的噪声也很敏感。
非种子区域方法： 这种方法时基于自上而下的方法。首先，所有点都分为一个区域。然后细分过程开始将其划分为更小的区域。论文【5】使用这种方法指导聚类平面区域的过程，以重建建筑物的完整几何形状。该工作引入了基于局部区域的置信率为平面的分割方法。这种方法的局限性在于它也会可能过度分割，并且在分割其他对象（例如树）时它不能很好地执行。非种子区域方法的主要困难是决定细分的位置和方式。这些方法的另一个限制是它们需要大量的先验知识（例如，对象模型，区域数量等），然后这些未知的先验知识在复杂场景中通常是未知的。
03
基于属性的方法：该方法是基于点云数据的属性的一种鲁棒性较好的分割方法，这种方法一般包括了两个单独的步骤：
第一步，基于属性的计算。
第二步，将根据计算点的属性进行聚类，这种聚类方法一般能适应空间关系和点云的各种属性，最终将不同的属性的点云分割出来，但是这种方法局限性在于他们高度依赖派生属性的质量所以要求第一步能够精确的计算点云数据的属性，这样才会在第二步中根据属性的类别分割出最佳的效果。
论文【6】则是这种方法实现的，提出了一种基于特征空间聚类分析方法，在该方法中，使用一种自适应斜率的邻域系统导出法向量，使用点云数据的属性，例如距离，点密度，点在水平或者垂直方向的分布，来定义测量点之间的领域，然后将每个方向上的法向量的斜率和点邻域的数据之差作为聚类的属性，这种方法可以消除异常值和噪声的影响，基于属性的方法是将点云分割相同属性区域的高效方法，并且分割的结果灵活而准确。 然而，这些方法依赖于点之间邻域的定义和点云数据的点密度。 当处理大量输入点的多维属性时，这种方法的另一个限制是比较耗时。
04
基于模型的方法：该方法时基于几何的形状比如球形，圆锥，平面和圆柱形来对点云进行分组，那么根据这些几个形状，具有相同的数学表示的点将会被分割为同一组点，论文【7】中引入了一种众所周知的算法RANSAC（RANdom SAmple Consensus）,RANSAC是强大的模型，用于检测直线，圆等数学特征，这种应用极为广泛且可以认为是模型拟合的最先进技术，在3D点云的分割中需要改进的方法都是继承了这种方法。基于模型的方法具有纯粹的数学原理，快速且强大，具有异值性，这种方法的主要局限性在于处理不同点云是的不准确性。这种方法在点云库中已经实现了基于线，平面，圆等各种模型。
05
基于图优化的方法：图优化的方法在机器人的应用中十分流行，众所周知的方法是FH算法【7】，该方法简单且高效，并且像Kruskal算法一样用于在图中查找最小生成树。许多基于图的方法的工作被投入到概率推理模型中，例如条件随机场（CRF），使用CRF标记具有不同几何表面基元的点的方法。基于图优化的方法在复杂的城市环境中成功地分割点云，具有接近实时的性能。为了与其他方法进行比较，基于图形的方法可以对点云数据中的复杂场景进但是，这些方法通常无法实时运行。其中一些可能需要离线训练等步骤
5.总结
以上将分割方法分为五类。但是，一般来说，有两种基本方法。
第一种方法使用纯数学模型和几何推理技术，如区域增长或模型拟合，将线性和非线性模型拟合到点云数据。这种方法允许快速运行时间能实现良好的结果。这种方法的局限性在于在拟合物体时难以选择模型的大小，对噪声敏感并且在复杂场景中不能很好地工作。
第二种方法使用特征描述子的方法从点云数据中提取3D特征，并使用机器学习技术来学习不同类别的对象类型，然后使用结果模型对所获取的数据进行分类。在复杂场景中，机器学习技术将优于纯粹基于几何推理的技术。原因是由于噪声，密度不均匀，点云数据中的遮挡，很难找到并将复杂的几何图元拟合到物体上。虽然机器学习技术可以提供更好的结果，但它们通常很慢并且依赖于特征提取过程的结果。
以上的这些算法在PCL的都已经实现且都有现成的demo可以查看效果。
6.PCL点云中的分割模块
该模块是在以上基本模块的基础上进行的研究，比如如何将点云数据构造成kdtree或者Octree结构使用FLANN（最近邻搜索）的方式寻找点与周围见之间的关系。
在PCL常用的聚类分割的类有以下几种：
class pcl::ConditionalEuclideanClustering< PointT >
该类实现了用于设定的条件的欧式聚类的分类算法。
class pcl::CPCSegmentation< PointT >
对超体素图进行分割的分割算法。 它使用局部凹度引起的平面切割进行递归分割。使用局部约束的有向RANSAC进行分割。
CPC分割与LCCP分割是继承的关系 ，具体论文【9】。
class pcl::EuclideanClusterExtraction< PointT >
欧几里得聚类提取是欧几里得意义上的聚类获取分割的点云类。
class pcl::LabeledEuclideanClusterExtraction< PointT >
labeledeuclidenclusterextraction表示一个分段类，用于欧几里得意义上的带有标签信息的聚类提取，
class pcl::ExtractPolygonalPrismData< PointT >
ExtractPolygonalPrismData使用一组表示平面模型的点索引，并与给定的高度一起生成三维多边形棱柱。然后使用多边形棱柱分割位于其内部的所有点。
class pcl::GrabCut< PointT >
实现了GrabCut分割。
class pcl::segmentation::detail::RandomWalker< Graph, EdgeWeightMap, VertexColorMap >
实现随机行走的优化的分割方法，论文【10】
class pcl::LCCPSegmentation< PointT >
一种简单的分割算法，将一个超体素图分割成由凹边界分隔的局部凸连接超体素组，论文【11】
class pcl::SACSegmentationFromNormals< PointT, PointNT >
结合点云的数据表面的法向量使用RANSAC方法的分割。
class pcl::SupervoxelClustering< PointT >
实现基于体素结构、法线和RGB值的超体素算法。论文【12】。
【1】A. Shamir, Segmentation and shape extraction of 3D boundary meshes (state of the art report), in Eurographics, 2006
【2】 B. Bhanu, S. Lee,C. Ho, and T. Henderson, Range data processing:Representation of surfaces by edges. In proc.int. Pattern recognition conf, 1896
【3】X.Y. Jiang, H. Bunke, and U. Meier, Fast range image segmentation using high level segmentation primitives, In 3rd IEEE Workshop on Applications of Compute Vision, USA, 1996
【4】P.J. Besl, R.C. Jain, Segmentation through variable order surface fitting, IEEE Transaction on Pattern Analysis and Machine Intelligence 10, 1988.
【5】J. Chen, B.Chen, Architectural modeling from sparsely scanned range data. Int. J. Comput. Vision 78, 2008.
【6】S. Filin, N. Pfeifer, Segmentation of airborne data using a slope adaptive filter, ISPRS J. Photogramm. Remote Sens., vol. 60, pp. 71- 80, 2006.
【7】M. Fischler, R. Bolles, Random sample consensus: a paradigm for model fitting with applications to image analysis and automated cartography Communications of the ACM
【8】P.F. Felzenszwalb, D.P. Huttenlocher, Efficient Graph-Based Image Segmentation, International Journal of Computer Vision, 59(2), 2004.
【9】M. Schoeler, J. Papon, F. Woergoetter Constrained Planar Cuts - Object Partitioning for Point Clouds In Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition (CVPR) 2015
【10】Random Walks for Image Segmentation
【11】S. C. Stein, M. Schoeler, J. Papon, F. Woergoetter Object Partitioning using Local Convexity In Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition (CVPR) 2014
【12】Voxel Cloud Connectivity Segmentation - Supervoxels from PointClouds In Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition (CVPR) 2013
注意