基于空间相似聚类的点云数据分割方法研究与实验

马进全，李玉忠，穆文龙

(1. 青海省测绘产品质量监督检验站，青海 西宁 810001；2. 青海省第二测绘院，青海 西宁 810001)

0 引 言

三维点云数据是指通过激光雷达(LiDAR，Light Detecting And Ranging)扫描获取的包含目标表面三维坐标、反射强度等信息的海量点数据，具有无损、高效、精准、海量数据等特点[1]。点云信息除了目标物体表面的离散点的空间坐标信息外，还包含海量点云的子集所描述的曲面信息以及发射的激光脉冲经过与目标作用后反射的不同强度的回波信号。在对物体进行测量的过程中，三维扫描仪可快速高效地对目标物体进行量测，获取物体表面三维坐标。由于点云数据的密度大并且不直接与地物表面接触，被广泛应用在室外场景的处理中，以实现地物提取、物体识别、场景分析等工作。而这些应用的输入数据则是通过点云分割将具有相同属性的点聚类为同质区域的结果数据，且点云分割结果的优劣直接影响到后续的应用分析，故点云分割具有重要的研究价值，也得到了国内外许多研究者的广泛关注，并提出了许多点云分割算法。

1 国内外研究现状

三维点云分割就是从原始杂乱无章的点云中确定具有相同属性的区域，赋予相同标志的过程，其相同几何属性区域主要包含：线状区域、面状区域、球状区域等；相同语义属性区域是指环境中的地物，如道路、树木、路灯、交通标志牌、建筑物等。目前三维点云的分割方法多种多样，按照分割方法的不同分为如下几类：基于区域边界的分割方法、基于聚类的分割方法、基于区域增长的分割方法、基于图的分割方法、基于模型匹配的分割方法以及基于机器学习的分割方法等。

1.1 基于边界的分割方法

通过计算每个点的几何特性，估算出点的法向量或曲率，将突变处的三维点定义为特征点，将所有的特征点连接形成一个封闭的区域，得出分割结果。Fan等采用逐点计算点局部曲率的方法，依据曲率变化情况判断是否为边界点，该方法计算量较大[2]；Sappa等采用两步边界查找法，在边界优化过程中对曲面拟合的初始迭代参数精度要求高，实用性不强[3]。基于边界的分割方法对噪声比较敏感，要求点云数据比较完整，对平面物体该方法能取得很好的效果，但对室外场景中比较散乱的点云应用效果则不理想。

1.2 基于区域增长的分割方法

该方法将相同几何特征的点云归类到同一区域当中，依靠区域扩张形成一个迭代的过程,主要分自上而下、自下而上的两种迭代形式。通过选择点云中的种子片面或者种子点，以该种子为中心，向四周以法向量、坡度或者曲率差异等临近准则进行增长,直到满足条件为止。Wang和Tseng提出基于体元的分裂与合并算法，运用到共面体元合并的计算过程中，在这过程中体元大小以及合并准则对分割结果影响很大[4]。而且该算法需要依据准则对分割过程进行不断的干预，计算过程比较耗时[5]。

1.3 基于图的分割方法

该方法包括正则化图割、最小割等。主要通过K邻近阈值建立一个三维图，图中的节点为空间划分体元或者三维点，除了这些节点外还有两个终端节点S与T，S表示前景节点，T表示背景节点，连接节点的边上的权重一般是欧几里得距离的函数，如图1所示。正则化图割是一种全局最优的分割方法，通过不断迭代直至达到最优条件：分割块内部的差异最小同时分割块之间的差异最大[6]。除此之外还有基于欧氏距离和图割的聚类方法及过分割和层次化合并的方法等，先将点云分割成超级体素，再根据超级体素之间的相似性对超级体素进行层次化合并[7]。

图1 图割示意图Fig.1 Schematic diagram of drawing

1.4 基于特征聚类的分割方法

该方法是一种多元统计分析方法，重点是识别点云聚类模式。史文中等提出了基于投影点密度的车载激光扫描距离图像分割方法，根据投影密度的差异区分不同地物，以达到对原始点云语义分割的目的[8]；张雨禾等提出基于密度空间聚类的散乱点云特征提取方法,对相关概念进行重定义并建立新的特征识别准则,对潜在曲面形状差异较大的模型表现出了较强的优越性[9]。

1.5 基于模型匹配的分割方法

该方法有时也指基于参数的方法，常采用Hough Transform和RANSAC算法。霍夫变换的主要过程是检测平面、圆柱、球体等基本形状。RANSAC算法通过用最少的点构建基元形状，构建形状的点通过与点云数据集中所有的点进行对比检核以确定当前形状即是正确最优的形状集合。虽然这两种算法有较强的稳定性与鲁棒性，RANSAC算法在有较多噪声和异常值的数据集中表现良好，但参数模型的缺点在于分割结果依赖于点云密度、位置精度等，且不适用于数据量较大、基本几何形状较复杂的点云数据[5]。

1.6 基于机器学习的分割方法

机器学习是目前比较热门的一个研究方向，它通过对大量的样本进行机器学习，得出样本的一些特征知识，然后运用先验知识对目标数据处理，得到分割结果。该方法需要先获取大量的样本，再通过神经网络算法进行大量运算，对于处理数据量较大的点云还是有一定困难。

2 原理及方法

本文在前人研究的基础上，提出一种基于空间相似性聚类的语义分割方法。其基本原理是：在空间距离聚类分割不足的基础上，对分割不足的分割块中具有相同几何属性的点集进行精细化分割，再根据环境中地物语义属性进行组合分割，以提高语义分割识别的精确度，减少方法的计算量，提高方法的性能。其中，对于三维点云的语义分割目的在于：将属于同一目标物体表面的激光扫描点聚类到同一分割块中，在对具有相似属性的点云进行聚类分割时，需要有一定的相似性测度，而点云之间的相似度有多种判定方法，最基本的是基于欧式距离聚类的方法。

本方法的思路是：先对点云数据进行地面点、非地面点分离，然后对非地面点实施欧式聚类，再对欧式聚类分割块中的点逐点计算其空间分布属性，根据空间分布属性再次进行条件距离聚类分割得到最终的分割结果。其主要流程如图2所示。

图2 空间相似性分割算法流程图Fig.2 Flowchart of spatial similarity segmentation algorithm

2.1 地面点与非地面点分离

据统计，车载或者地面站激光扫描仪获取的点云数据中70%的数据属于地面点。虽然地面点在点云数据中所占比例较大，但其地物种类比较单一，主要是道路及两侧的人行道或者道路旁侧的草坪绿地等。而城区环境中的其他种类繁多、形态各异、数量较多的目标主要位于非地面点中，若直接对原始点云数据分割，不仅会造成冗余计算，降低生产应用效率，而且在很多情况下会引起分割错误等不良后果。如若直接对原始点云进行欧式聚类，则无法有效地将环境中相离的两个路灯分开，因为两个路灯均与地面相连，在欧式聚类时，它们最终会根据相邻点距离聚类到同一分割区域中。

由上所述，在对点云进行分割前需进行地面点与非地面点分离处理。首先对原始点云数据进行水平方向上格网化处理，并统计每个格网中的最小高程值；然后遍历所有格网，对每个格网逐点比较其高程与当前格网最小高程值的差异，若差异小于阈值则判定为地面点，若差异大于阈值则判定为非地面点；据此分离点云数据中的地面点与非地面点，为后续的非地面点的分割做准备。

2.2 距离聚类

空间中同一地物的表面是连续表面，在点云数据中即为距离较近的点集。点云中的欧式聚类是指将点云中距离小于阈值的点聚类为同一集合。按照此原理，基于欧式聚类的点云分割会导致分割不足。实验时先对地面点与非地面点分离结果中的非地面点进行欧式聚类，初步认为空间中距离较近的点为某一同质区域内的内部点，将非地面点中相离的点云分别聚类为不同的分割块。

2.3 空间相似性分割

如前所述，将非地面点中的点云分别根据欧式距离聚类为不同的分割块后，对于相互在空间上有粘连的地物而言，如电线杆与电线杆之间的电线，两者在形态上存在很大差异，但是由于两者在空间上粘连，故上一步的欧式聚类结果中两者被聚类为同一分割块，即分割不足现象。因此还需将分割不足的结果作为输入，对每一块分割不足的分割块内的点云进行空间相似性分割。相似性分割测度为点云逐点分类的属性，将属性相同且距离小于阈值的点分割为同一分割块；将距离小于阈值而属性不同的点划分到不同的分割块中。

此步骤中，首先将分割不足的分割块中的点云进行逐点分类，赋予每个点一个属性值，遍历计算所有点后，对点云中具有相同属性的点进行距离聚类，即可以得到初始的语义分割结果，然后通过一定的优化准则对分割结果进行优化。

对于非地面点先逐点计算特征，将其分类为：杆状点、面状点、球类点以及未分类的点，逐点计算特征的方法如下:

（其中，M3+3为邻域点集坐标的协方差矩阵，为邻域内每个点的坐标列向量，为邻域内所有点的坐标平均值，即邻域的中心〈重心〉点的坐标，N为邻域内点的数量）。

由公式（1）中的协方差矩阵计算特征值λ1，λ2，λ3，其中λ1＞λ2＞λ3＞0；

对每个点分别计算以上α1D，α2D，α3D3个值中最大的值所对应的生长要素的类型即为当前点的空间形态类型；再对基础分类后的点进一步地语义分类，将杆状点分为水平、竖直杆，将平面类的点分为水平面、立面。

精细分类的方法：

对于杆状物，判断其主方向的方位，主方向为该点邻域点的协方差矩阵最大特征值对应的特征向量，主方向与天顶方向的夹角大于阈值，则为水平杆；主方向若与天顶方向的夹角小于阈值，则为立杆；

对于面状物，判断其法向的方向，法方向为该点邻域点的协方差矩阵最小特征值对应的特征向量，若其法向与天顶方向的夹角小于阈值，则为水平面；若其法向与天顶方向的夹角大于某阈值，则为立面；

由以上步骤已初步得到每个点的空间形态特征，再以空间形态特征为判断准则对分割不足的分割块中的点云进行空间相似性分割，若距离小于阈值而空间形态不一致则分割为不同区域块，由此解决前文中出现的分割不足问题。

经过相似性分割处理后，对每个独立的分割块根据地物语义信息分类：大面积立面组成的地物为建筑物，球状体与临近竖直线状地物为树木，竖直线状地物与邻接的水平线状地物为电线杆等。

3 实验结果及分析

按照上述技术方法对某地一块十字路口的点云数据进行分割实验，原始数据如图3所示。实验时设定平面格网长度和宽度为1 m，欧式聚类阈值设为0.2 m，则地面点与非地面点分离后结果如图4所示，其中蓝色部分为地面点，绿色部分为非地面点，由图可得，本文的方法可有效分离地面点与非地面点。

图3 原始点云数据Fig.3 Original point cloud data

图4 地面点与非地面点分离结果Fig.4 Separation result of ground point and non-ground points

图5为对非地面点逐点计算空间形态特征的结果，其中，红色部分表示空间垂直，主要为建筑物墙面表面点；橘黄色为水平面，主要为建筑物阳台部分的表面点云；蓝色为空间竖直线状地物，主要为电线杆及路灯灯杆表面点；绿色为水平线状地物，主要为电线表面点。除此之外，由图可见，直接通过逐点计算空间形态的方法对空间杂乱点云进行分类有很多错分的结果，而且同一地物表面点的属性计算结果不一致，主要由于计算空间形态时，点邻域大小选择对属性计算结果的影响，故直接通过此方法进行分割结果不佳。

图6所示为根据本文提出的方法对该数据进行分割及优化后的结果，对比图6及图5可知：图6的分割结果在正确性、一致性方面均优于直接分类的结果。其中，蓝色为地面，青色为建筑物，绿色为树木，灰色为未分类目标，黄色为电线杆，橙色为路灯，灰色为归类目标。但是依然存在一些问题：如图6目视判别的所示电线杆的分割结果存在一定的问题，将电线杆分割成两部分，需要后续优化改进。

图5 非地面点逐点分类结果Fig.5 Point by point classif i cation results of non-ground point

图6 语义分割结果Fig.6 Semantic segmentation results

4 结束语

本文主要探讨了点云分割的方法，并通过具体实验介绍了基于空间相似性的语义分割流程，将数据量巨大的点云数据由多到少，由粗到细进行逐步分割优化，分割结果较直接欧式聚类与直接逐点分类结果的正确性、一致性等方面均有较大进步。实验表明，采用该方法可以取得良好的分割效果，但还存在一定的缺点（如路灯的分割等），后续需增加更多的分割约束准则，使得分割结果更优；而且，在时间效率方面，后续研究及应用中也需进一步强化。