Abstract:
- 3D数据类型（dense or sparse）
- 地面模型（grid based, Gaussian Process based, or mesh based）
- 3D聚类方法
对于不同类型的3D点云数据，适用的分割方法可能不同，于是该文评估了对每种数据类型具有更好分割性能的算法。
首先，作者对密集（dense）和稀疏（sparse）3D数据进行了区分。在固定的离散分辨率下，密集数据通常包含了可以联通的表面区域，而稀疏数据中空的格点增加，导致物体容易被过分割。相应地，密集数据的分割一般采用固定分辨率的网格模型，稀疏数据的分割则采用基于非固定粒度的地面表示和多种插值方法连接数据间的空洞。
密集数据分割
一般方法：体素网格分割（voxel grid based segmentation）
体素通过三维的立方体来处理3D点及计算特征。例如，3D均值、方差和密度等，这类方法具有简单易用的特点，通过显示或数据结构都能简单地进行表示，并且可以通过调整体素的尺寸进行放缩，而确保数据密度可行。
具体方法可分为四种，其中三种为两阶段方法，即首先决定地面划分，然后进行3D聚类，另外一种则直接进行后边的聚类过程。
- 地面划分：基于垂直方向的均值和方差，进行阈值判断。
- 聚类：仅通过邻域进行划分。
- 地基方法：划分voxel是否属于平面，而当不相似的非平面voxel位于平面voxel之下时，两者可以合并，例如汽车的车身和车顶的关系。
- 地面-地基方法：先进行1，再进行3。
稀疏数据分割
存在两种互补的稀疏分割方法：高斯过程增量采样一致性（GP-INSAC，Gaussian Process Incremental Sample Consensus）和网格分割（Mesh based Segmentation）。
GP_INSAC：迭代连续概率地面估计方法，转换为基于模型的离群值筛除形式。增量采样一致性致力于解决模型复杂度增加带来的计算性能问题。通过迭代地外插和内插，GP-INSAC可以逐渐发现模型内点，并排除干扰模型的离群点，直到没有新的内点可以被找到。
完整处理算法：
Compress和Decimate即在固定尺寸的voxel grid中进行降采样。然后，种子点的选取基于高度和半径。
Mesh Based Segmentation：1）构建地形网格，2）基于梯度场提取地面点，3）聚类非地面物体
Mesh不同于grid，其中相邻两点不满足固定分辨率条件。通过基于种子点的区域生长可以从拓扑结构中分割出地面。在Mesh中按方向遍历，由高度差和距离计算出梯度场。地面分割则从最近的raster line到最远的raster line进行生长聚类。另外，地物转换位置可通过地面上连续点的高度buffer进行识别，这个buffer先沿着raster line扫描，后沿着radial line扫描。当相邻节点的梯度和高度满足约束条件时，找出转换位置。进而，通过转换位置使物体分割更加紧凑。
实验与结论
经验性地分析了不同方法的参数选择和实验效果。