Research progress of point clouds segmentation algorithms based on geometric features

3维图像是一种特殊的信息表达形式，包含了所观测场景的完整几何信息。相较于平面2维图像，深度信息的获取使得3维图像可以轻易地实现不同距离场景的分离，并对不同测量设备和不同视角保持良好的统一性。近些年来，随着3维成像技术的快速发展，出现了越来越多高精度、低成本的3维图像传感器，如激光雷达(light detection and ranging, LiDAR)^[1]、深度相机^[2]等，大幅降低了3维信息获取的难度与成本。作为一种特殊格式的3维数据，点云^[3]已经成为当前3维图像的主要信息表达方式。相较于其它的3维数据格式，点云数据无需存储各离散点之间的拓扑结构，有着更为简单、灵活和强大的表示能力，在处理时可以表现出更好的性能。因此，点云成为了机器视觉、遥感测绘等领域的首选数据格式，在目标识别^[4]、模型构建^[5]等场景中得到了广泛的应用。

点云分割是点云数据处理过程中的重要步骤，其目的在于将初始点云划分成若干具有相似属性的子集^[6]，为后续进一步应用做准备。由传感器所获得的原始点云数据往往较为复杂，包含着大量冗余信息，难以直接获取所需信息, 故需要先对初始点云进行分割，再从中分离出感兴趣的部分。在点云处理过程中，点云分割的结果将作为后续步骤的输入数据，对算法的运行结果产生直接影响，因此，点云分割算法一直受到3维信息处理领域的广泛关注。近年来，深度学习给点云数据处理提供了新的思路^[7]，但相关算法结构复杂、运行速度慢、结果稳定性差，距离广泛的实际应用还有一定距离。与之相比，基于3维图像几何特征的点云分割算法结构更加简洁、响应速度快、结果稳定性好，并且易于针对不同场景进行快速调整，在实际应用中仍占有主要地位。

尽管基本理论框架已经基本完善，但随着硬件设备的不断更新，3维图像特征的获取方式更加多样化，许多优秀的分割算法仍旧不断涌现。本文中对近年来出现的点云分割算法进行了梳理，并依照其所应用的特征进行了分类，分析了其优缺点。期望为相关研究和应用提供一定参考。

与2维图像分割相似，3维点云分割指将整个点云场景分解为不同子集的过程，所得子集之间互不交叉，且每个子集满足特定属性的一致性。将2维图像分割的数学定义拓展至3维图形，点云分割的数学定义可以表述为：令点集I表示整个点云场景，R_i(i=1, 2, …, n)表示点云分割所得子集，描述符号H(A)表示集合A内各元素具有相同属性，则R_i应满足以下条件：(1) $\mathop \cup \limits_{i = 1}^N {R_i} = I, {R_i} \cap {R_j} = \emptyset , \forall i, j, i \ne j, $即分割所得子集应覆盖整个场景，且相互不重叠; (2)∀i, i=1, 2, …, n, H(R_i)=ture，子集内部所有元素点应具有相同属性; (3)∀i, j, i≠j, H(R_i∪R_j)=false，不同子集所具有属性之间具有明显差异，不同子集不能合并。

边缘描述了物体的形状特征，在图像中常常表现为方向不连续、或者某属性发生突变的点。根据RABBANI等人^[8]的定义，此类分割算法主要分为两步：(1)边缘的检测与提取；(2)对边缘内的点云进行聚类。边缘检测算法大体上可分为直接检测与间接检测两类^[9]：直接检测即利用边缘的特殊性质对其进行检测，间接检测则通过将3维点云与2维图像建立对应关系来进行，通过对2维图像进行边缘检测将所得边缘投影至3维点云。由于3维点云转换到2维图像的过程中有可能会丢失部分特征，在实践中有诸多困难难以克服，应用较少，本文中只对直接检测方法进行讨论。

2017年，美国俄勒冈州立大学的CHE等人^[10-11]提出了法向量变化分析(normal variation analysis，NORVANA)算法。该算法利用地面激光扫描(terrestrial laser scan，TLS)的网格扫描模式构建局部三角网络，并由每条共享边的法向梯度确定共享边是否位于边缘上。2019年，CHE等人将NORVANA算法拓展至车载激光雷达点云数据(mobile laser scan，MLS)处理中，称作Mo-NORVANA^[12]，其流程图如图 1所示。车载激光雷达点云无法利用网格模式确定近邻，故基于车载激光雷达点云由线性扫描所得这一事实，选取相邻两条扫描线上的点作为最近邻以构建网格，分析其法向差异，并应用NORVANA算法实现边缘检测。

2018年，英国斯特拉斯克莱德大学的SUMMAN等人提出了利用邻域点特征来提取边界点的方法^[13], 该算法依据邻域点的分布将点云划分为内点、凸面边界点和凹面边界点3类，并利用“3点定圆”的思想来标记边缘点，其示意图如图 2所示。其中点C为内点，点A和点B为凹面边界点，点D和点E为凸面边界点。对于未分类的点，步骤一：计算该点及任意两个邻域点所确定的所有圆的半径; 若有任意一个圆的半径大于其局部分辨率，且所求圆的对应球体中不包含任一其它点，则此点标记为边界点；否则进行步骤二：将点P及其邻域投影至最佳拟合平面上，并以P为原点建立极坐标系，尝试建立一个可以包围原点并通过所有邻域点的路径，若此路径不存在则将P标记为边界点。

对点云而言，是否为边界点是一个由其邻域所确定的固有属性^[14]，故边缘检测算法很容易受到离群点和噪声的影响，在应用此类方法之前应先对点云做降噪处理。同样，若点云密度过低或分布不均匀，则无法明确点云的局部特征，导致边缘缺失，影响算法运行的结果。

区域生长算法(region growing，RG)^[15]是在2维图像分割领域中得到广泛应用的经典算法，因其出色的分割效果被拓展至3维点云数据中。算法流程为：首先指定种子点，随后对邻域点的某些特征进行比对，若小于预定阈值则将邻域点作为新的种子点继续生长，若周边邻域点没有符合条件的点则跳出算法。

种子点的选取策略与生长与否的判断依据是对区域生长算法效果影响最大的两个因素。1988年，美国密歇根大学安娜堡分校的BESL等人提出选择曲率最小的点作为种子点^[16]。此准则简单有效，是目前采用最多的方法^[17-18]。此外，将点云预分割以提升种子点选择质量也是常见的方法^[19]。在生长判断准则方面，阈值分类思想仍旧占据主流，平滑度^[8]、RGB颜色^[20]、法向量^[18]、平面拟合残差^[21]等点特征作为生长判据被广泛应用于区域生长算法之中。

2019年，华中师范大学的WU等人将多尺度张量投票算法(multiscale tensor voting method, MSTVM)引入区域生长算法以确定种子点^[22]，其流程图如图 3所示。张量投票算法最早由德国波恩大学摄影测量研究所的SCHUSTER引入点云数据之中^[23]，通过点云协方差矩阵的特征值和特征向量表述该点的局部几何特征。对于张量投票算法而言，投票的数目，即尺度，对算法的效果有着至关重要的影响。因此，作者提出了MSTVM, 通过指数化半变异函数确定合适的尺度区间，在区间内多次计算投票值以求得相对投票值，选择相对投票值较高的点作为种子点。相较于应用主成分分析(principle component analysis，PCA)和张量投票算法的区域生长算法，MSTVM有着更高的分割精度，对噪声有着更高的鲁棒性。

2020年，巴西坎皮纳斯大学的PAIVA等人结合了分水岭算法与区域生长算法，实现了对RGB点云建筑模型的分割^[24], 算法流程图如图 4所示。对于所得初始点云，该算法首先通过灰度变换将其转化为灰度图，并利用八叉树明确点云各点之间的连接关系。连接图构建完成后，平滑点云灰度值，以此获取梯度作为分水岭算法的输入。随后选定各区域内的曲率最小点作为种子点应用区域生长算法。

尽管区域生长算法已经在点云分割领域得到广泛应用，但它的缺点仍旧不容忽视。种子点可以大幅影响算法效率，但是其选择的依据并没有一个统一的最优解，目前应用最为广泛的方法是选择曲率最小的点作为种子点，但在小部分情况下这依然无法取得较好的效果，这使得算法的稳定性大打折扣。此外，区域生长算法要求点云集有足够的连续性，若点云密度不均匀则难以获得精确的结果。与基于边缘的分割算法类似，区域生长同样基于局部特征，故对噪声、离群点十分敏感，在分割之前需要对点云进行去噪、平顺等预处理。

除区域生长算法以外，各种聚类算法也被用于进行点云分割，如经典的k均值算法^[25-26]、均值漂移算法^[27-28]、高斯混合模型^[29]等。对于聚类算法而言，其选用特征的可靠性和质量对算法的分割效果有着较大的影响。常用于点云分割的特征有点的空间位置信息^[30-31]、法向量、点的局部密度等。以点特征构建特征向量^[32]可以提高算法的鲁棒性，也是常见的特征构建方法。也有少部分算法采用局部算子作为特征，如快速点特征直方图(fast point feature histogram, FPFH)^[33]、视点特征直方图(viewpoint feature histogram，VFH)^[34]等。

2018年，美国德克萨斯大学奥斯汀分校的CZERNIAWSKI等人^[35]将基于密度的噪声应用空间聚类(density-based spatial clustering of applications with noise, DBSCAN)算法^[36]应用于点云分割。算法将点云映射至高斯球上以提取法向信息，并与3维坐标相结合，构建6维特征空间{x, y, z, n_x, n_y, n_z}以进行DBSCAN聚类。分割结果如图 5所示。

2019年，浙江工业大学的HUANG等人提出了基于密度的聚类算法(density-based clustering，DBCS)^[37]。该算法由DBSCAN算法发展而来，并通过将点云划分为不同子集平行处理提高算法效率，其流程图如图 6所示。对于大规模点云场景，算法先求其边界盒，若其中子集数量大于预设值，则对矩形边界盒进一步进行划分，直至边界盒内点云数量达到阈值。

2020年，韩国首尔国立大学的PARK等人提出了弯曲体素的概念，并以此为基础利用聚类算法完成了对点云数据的分割, 称作弯曲体素聚类算法^[38]，流程图如图 7所示。弯曲体素是体素在球坐标系下的拓展，与体素类似，定义为球坐标系内的独立单元，以确定的分辨率划分整个球坐标系。算法首先将初始点云自3维笛卡尔坐标系转换至球坐标系中，随后创建哈希表，将各点映射至包含其的弯曲体素中，并滤除其中的无用弯曲体素，保留含有点的体素。最后在哈希表中搜寻相邻的体素，将其划分为同一个聚类，完成分割。

与区域生长算法类似，利用聚类算法来完成点云分割同样也是基于点云及其相邻点的局部特征来对散乱点进行分类的。此类算法与区域生长算法最大的区别就在于聚类算法无需定义种子点，这使得聚类算法的适用性比区域生长算法略高，但其判断准则仍旧对算法效果有较大影响。

图是一种强大的数学工具，已在计算机视觉、目标探测等方面得到广泛的应用。点云离散的特性也使得其与图有着良好的相性，图论中众多的分割方法在点云数据处理中都有着广泛的应用潜力。图论分割的主要思想即是确保不同片段之间的相似度最小，而相同片段中各点的相似性最大，点云中各点可天然视作图中的顶点，因此，如何确定构建连接图，确定边的权重，成为了此类方法的研究重点。

2017年，慕尼黑工业大学的XU等人^[39]提出了基于体素与图论方法的点云分割(voxel-graph based segmentation, VGS)方法。算法首先将点云体素化，以所得体素作为图的顶点，并利用八叉树构建全连接图。图中各边的权重则由顶点的空间相似度、几何相似度与曲率变化确认。2020年，XU等人对VGS算法进行了进一步的优化^[40]，其算法流程图如图 8所示。新的算法利用几何中心与内部各点的法向量对体素进行表示，以此为基准，仅保留内部点分布平面化的体素，滤除内部点云呈不规则分布或曲面分布的冗余体素，提升了平面拟合效果；各边的权重则由相邻节点V_n, V_m之间的法向量角度差D_nm^α和空间距离D_nm^p得到：

式中, δ_α和δ_p为权重参数。分割完成后，应用RANSAC算法进行平面提取。

以图论作为理论基础有着较好的可解释性，在复杂场景下基于图论的点云分割可以取得很好的效果，但此类算法仍旧有着很高的时间复杂度，难以实现实时应用。

此类算法通过将所得点云与预设模型进行拟合来实现点云分割，其所使用的形状基元在参考文献[41]中有着详细的介绍，在此不多赘述；而其中使用最为广泛、效果最为出色的算法是3-D霍夫变换(3-D Hough transform，3DHT)^[42]、随机采样一致(random sample consensus，RANSAC)^[43]，以及它们的一系列衍生算法。

霍夫变换是一种纯数学的参数空间转换方法，由HOUGH在1960年提出^[44]。通过改变点的数学表现形式，将点从3维空间映射至参数空间完成投票，对各种可参数化的形状有良好的探测效果。霍夫变换由3步构成^[45]：(1)构建参数空间；(2)由输入数据累计投票；(3)在参数空间中识别模型。对于3维笛卡尔空间中的平面，其方程为：

可写为：

式中, s_x和s_y为平面对z轴的斜率，D为平面在z轴的截距。由此可定义一个三变量空间，即霍夫空间。霍夫空间中的点与3维坐标系中的平面一一对应，利用这样的对应关系即可以通过投票算法完成拟合。

2019年，荷兰代尔夫特大学的WIDYANINGRUM等人提出了基于有序点表(ordered points lists，OPL)辅助的霍夫变换算法，并实现了对空载激光雷达建筑物点云边界线的提取^[46]，算法流程图及分割结果如图 9所示。OPL由霍夫矩阵变换而来，与霍夫矩阵有着相同的维度与参数。两者的区别在于：霍夫矩阵仅保存行内直线的投票点的数量，而OPL保存了这些点的有序表。通过设定间隔空隙，算法对包含点不连续的直线进行了分割，解决了传统霍夫变换对方向相同但属于不同分割片段的直线误判断问题，大幅提高了建筑物边界提取的质量。

同年，北方工业大学的SONG等人与澳门大学的TIAN利用3DHT实现了大规模MLS云的地面提取^[47]。算法同时利用了中央处理器(central processing unit, CPU)与图形处理器(graphics processing unit, GPU)，并将3-D霍夫空间体素化，实现了利用GPU的并行计算，大幅提升了算法效率。GPU-CPU混合地面提取算法框架如图 10所示。

2020年，TIAN等人通过构建标志图对算法进行了进一步优化^[48]。

标志图与霍夫空间维度相同，主要用于实现对3-D霍夫空间内体素的一对一标记，对有效体素则通过霍夫空间内的坐标计算标志值：

式中, i, j, k分别为标志图的3维坐标，h(i, j, k)为霍夫空间内相应坐标的投票值，I_H，J_H和K_H分别为霍夫空间内各3维方向上的体素数量。

在此基础上，算法将相连的体素聚类为同一集团，并取集团内的最小标志值代表集团。此时，同一集团内标志值相同，不同集团之间标志值相异，遍历所有集团即可完成峰值搜索。算法流程如图 11所示。

RANSAC算法基于对模型的假设与选择，通过随机选取点云中的若干子集对模型进行多次拟合，从中选取拟合效果最佳的模型作为拟合结果。RANSAC算法简单且强大，2007年，法国国立应用科学学院的TARSHA-KURDI等人^[49]将3-D霍夫变换与RANSAC算法进行了比较，实验证明，RANSAC算法有着更高的效率与精准度。

2017年，武汉大学LI等人将RANSAC算法与正态分布变换单元(normal distribution transformation cells，NDT Cells)相结合，用于点云数据的平面分割^[50]。NDT与体素类似，为小尺寸立方体，包含若干点云，其内部点云视为正态分布。在完成对初始点云的划分后，求各单元内点云的协方差矩阵，其特征值与特征向量作为单元特征表述各单元的几何特性，并以此为依据提取平面分布的正态分布单元。最终，对平面分布的正态分布单元内应用RANSAC算法，实现平面分割，并以迭代加权最小二乘法计算法向量，进行平面拟合，完成平面融合。其算法运行结果如图 12所示。

最大似然估计采样一致算法(maximum likelihood estimation sample consensus，MLESAC)由微软研究院的TORR与牛津大学的ZISSERMAN^[51]提出，以模型的似然度代替内点数量对模型拟合效果进行评估。2020年，武汉大学ZHAO等人^[52]将MLESAC算法进行优化，提出Prior-MLESAC算法，并应用于室内点云数据分割，其示意图如图 13所示。Prior-MLESAC算法在进行模型拟合值前，先基于迭代高斯映射对点云进行粗分割。理论上，所有位于平行平面上的点映射至高斯球上后应为同一个点，由此可通过对点云进行高斯映射，并对所得高斯球进行DBSCAN算法完成平行平面提取。在此基础上，以剩余的点云作为输入，逐渐调整DBSCAN算法的参数，迭代地对点云进行提取，实现对点云的粗分割。粗分割完成后，由PCA算法定义曲率特征：

式中, λ_i(i=1, 2, 3)为PCA所得张量的特征值，描述局部区域弯曲度的概率：

作为各点的先验特征，以此引导点云的采样，对属于不同模型的点应用不同的采样策略。

同年，南方科技大学的WU等人利用RANSAC算法实现了点云数据中成对正交平面(pairwise orthogonal planes，POP)的提取^[53]。对于成对正交平面，作者将其视为一个由4个两面角构成的整体模型，由平面的法向量与相交线定义两面角，实现了对成对正交平面模型的表述。在此基础上，算法基于八叉树结构将点云结构化，先在位于同一节点内的子集中生成候补模型，随后将其扩张至整个点云，实现RANSAC算法, 其算法结果如图 14所示。实验证明，相较于传统的平面拟合，成对平面拟合有着更高的效率，对正交的微小平面也有足够的处理能力。

相较于3-D霍夫变换算法，RANSAC算法有着更快的运行速度，对噪声有更强的鲁棒性，有着更广泛的应用场景，但其仍旧有着较高的时间复杂度，难以投入到大型场景的实际应用中；此外，算法自定义参数较少，对参数的选择十分敏感，这对算法在不同场景下的适配程度有所影响；最后，此类算法对点云的质量有着较高的要求，处理低精度、大场景的点云需要额外的措施对点云进行优化。因此，此类算法现多用于对其它算法所得的粗分割结果进行优化。

表 1中总结了各算法的性能参数，并统计了其主要应用场景。由于面向不同场景的算法侧重点有所不同，其评估方法也有所差异，故部分参数缺省。由表 1可见，对于MLS和TLS点云而言，若应用于大场景户外点云，基于边缘探测的NORVANA与Mo-NORVANA算法在保证高精准度的同时有着最高的算法效率，相较于其它算法有着3~4个数量级上的提升；而对于室内场景，其点云密度较高且分布更为均匀，模型也更加规则，因此模型拟合类算法可以获得优秀的分割结果。基于表面特征的算法原理简单、容易实现、效率良好、准确度也较高，但其精确度与召回率较低，因此易产生过分割与欠分割问题。由MSTVM算法可见，种子点的选取质量对区域生长算法的分割效果有着较大影响，但若选择算法过于复杂，则算法效率大打折扣，故需要针对不同需求分别应用；对于机载激光扫描(airborne laser scanning, ALS)点云而言，由于其点云密度较低且不稳定，对算法性能提出了较大挑战，仅有模型拟合类算法有着较好的运行结果，其余算法则不甚理想。

在过去几年中，研究者们在点云分割领域中完成了大量的工作，许多不同的算法被开发，但由于点云数据仍存在一些限制，导致目前在实际工程中难以实现实时应用。本节中总结了对算法效率产生影响的主要因素，对其进行了简要的分析。

基于局部特征的算法中，相似度的表征与所选用的特征直接相关，在模型拟合类算法中，其所选择的拟合基元也可视作特征。点云分割算法中所使用的特征对算法的效率与精确度有着至关重要的影响，现今，大多数算法所使用的特征为点特征，如法向量、RGB颜色、返回激光的强度、空间位置，以及在法向量的基础上进一步计算得到的若干高阶特征，如曲率、梯度等。除点特征外也有部分诸如FPFH、半径表面描述子(radius-based surface descriptor，RSD)等高阶算子被应用于点云分割算法之中，此类高阶算子可以提供更高的精度，但其计算需要较高算力，对算法效率有所影响，故尚未得到广泛应用。在点云的法向量估计方法中，占据主要的是以PCA为代表的局部平面拟合类算法，此类算法简单有效，因此应用得最为广泛，但其对邻域大小和点云噪声较为敏感，且对尖锐特征的表述有所欠缺，容易影响特征估算的精度。

邻域的大小对算法有着较大影响，邻域范围过大会导致算法复杂度较高，过小则会影响特征估算的精度。最为常用的邻域确定方法有k最近邻(k-nearest neighbor，KNN)和固定半径邻域(fixed distance neighbor, FDN)两种。在实践中，FDN需要根据算法的应用场景来调整截断距离，这对使用者的经验提出了要求，限制了FDN的应用范围。与此相对，KNN对点云密度自适应，有着更为广泛的应用场景，但是对噪声和离群点敏感，对点云数据的质量有较高要求。除此之外，将点云结构化以确定邻域也是比较常见的做法，如将点云数据体素化^[54]、网格化^[55]，利用扫描线确定邻域等^[54]。由表 1可见，此类方法可大幅提升算法的运行效率，但其增加了算法的步骤，并对使用场景和数据获取方式提出了要求，因此只有在特定场景下得到应用。

点云分割的对象是复杂多变的，同一个算法在不同的场景下难以得出相同的结果，因此在算法实现过程中仍旧需要人工调整参数，以改善算法的运行结果。但人工干预增加了算法的不可控变量，往往需要多次实验才能得到良好的参数，这增加了算法设计的成本，降低了算法的适应性。

遥感测绘与计算机视觉是点云数据的两大主要应用领域，但是两者有着不同的注重点，导致领域之间算法难以互通，需要根据应用场景对算法进行调整。两者的区别主要有以下几点：

(1) 算法的评估方式。在计算机视觉应用中，点云分割算法的侧重点在于整体的精度，而在遥感测绘领域中，算法往往更为关注对建筑物等特定目标的提取。因此在算法效果的评估方面，两者需要不同的评估方式来选择与实际情况更加契合的算法。

(2) 点云的获取方式。点云数据的主要获取方式有摄影测量、深度相机、激光雷达、逆向工程等。遥感测绘应用需要复杂且具体的大面积点云数据，因此大多是通过激光雷达与摄影测量得到点云。这种方法所获点云密度不恒定，数据量较大，分布不均匀且充满着噪声和离群点，在进行点云分割时有着更多的限制。而计算机视觉更加关注具体的3维细节，因此需要较高的密度和均匀的分布。其主要的获取方式是深度相机与模型逆向工程。由此方法获取的点云密度高，故处理时算法有着更高的时间花费。

(3) 数据格式。点云数据包含着物体表面的3维坐标信息，除此之外，由激光雷达所得的数据还包含着返回激光的强度，由摄影测量与深度相机所得的数据包含着该点的颜色信息。此类信息可以作为特征来提高算法的效果，但也导致算法难以在不同设备获取的数据之间通用。

(4) 对数据的预处理。在计算机视觉领域中，数据的噪点与离群点并不会对算法的效果造成过多影响，这是由其获取方式和算法侧重点所决定的。在高密度的点云中可以较为容易的滤除离群点，且增强了对噪声的鲁棒性。但在遥感测绘领域，传感器带来的噪声难以避免，在点云密度不均匀的情况下加重了对算法的影响。因此，算法需要针对滤波去噪平顺等方面进行大量的预处理，以尽量提高点云质量。

点云相较于其它3维数据，在处理时耗费资源较少，因此成为了计算机视觉、遥感测绘等领域的首选信息表示形式和处理对象。点云分割作为点云数据处理过程中的重要步骤，是实现相关应用的关键技术，其分割结果直接关系到后续算法的效果，故一直以来受到广泛关注，研究热度居高不下。针对本领域中仍旧存在的问题，如特征估计难、自动化程度低等，研究人员正在不断探索，对算法不断进行优化，取得了相当卓越的成绩。3维信息获取设备的不断发展也给点云分割提供了更多的硬件支持和处理路径，随着获取点云的不断丰富，在多传感器协同工作下的特征提取更加便捷。在自动驾驶、智能机器人等需求的牵引下，点云数据处理方法必将迎来新一波的发展热潮。