CN116051841A - 基于车载LiDAR点云的路边地上物多阶段聚类分割算法 - Google Patents

Abstract

本发明公开基于车载LiDAR点云的路边地上物多阶段聚类分割算法：步骤(1)、车载LiDAR点云数据预处理，得到路边地上物点云数据；步骤(2)、对路边地上物点云数据依次进行三维格网化和广度优先搜索，实现路边地上物点云数据的粗聚类分割；粗聚类分割得到单独地物点云和相连地物点云，单独地物点云作为路边地上物聚类结果输出；步骤(3)、将相连地物点云进行欧氏聚类，分割为边界完整的粗聚类点云集；步骤(4)、利用多段式近邻搜索聚合粗聚类点云集的所有聚类对象；自适应调整聚类阈值，至所有聚类对象的点云聚合速度相近，输出相连地物聚类结果。本发明解决了车载LiDAR点云分割存在人工干预多、分割效果不稳定等问题。

Description

基于车载LiDAR点云的路边地上物多阶段聚类分割算法

技术领域

本发明涉及地上物聚类分割技术领域。具体地说是基于车载LiDAR点云的路边地上物多阶段聚类分割算法。

背景技术

车载LiDAR技术作为当今前沿空间信息获取技术，在车辆行驶过程中能快速获取道路两侧地物详尽的三维空间信息。行道树、路灯、指示牌等路边地上物作为该数据源中的常见要素，为构建智慧城市、数字道路及自动驾驶技术等提供数据支持。由于车载LiDAR无差别地记录了建筑物、汽车、行人、路面、路边地上物等空间信息，从海量点云中获取地物时，点云聚类分割是其重要步骤，分割结果对三维重建、目标识别、特征提取等后续处理有直接影响。

当前针对路边地上物点云的聚类算法主要分为以下4类：

1)基于几何距离，如K-Means聚类、欧氏聚类等。该类算法的聚类结果与初始簇心位置、距离阈值有关，因道路场景中常有多种路边地上物，需频繁调整这些值以达到理想效果，其算法的参数复用性较差且易出现过分割/欠分割现象。

2)基于点云密度，如DBSCAN聚类、OPTICS聚类。该类方法以点云分布的紧密程度作为聚类依据，聚类时随机选择一个核心对象作为种子，输出这个核心对象密度可达的所有样本集合，重复该操作直到所有核心对象聚类完成。同类地物因点云密度相近而具有较好的提取效果，但近邻的地物易被提取为单个聚类，且车载LiDAR数据存在随扫描距离增大而点云密度下降的问题，需考虑局部密度变化对聚类效果的影响。

3)区域生长聚类，如自适应区域增长准则算法。该类算法先根据曲率值对点云排序并选择初始种子点，比较种子点与邻域点间的法向量夹角，将属性相似的点归为一类并继续向外生长，直至没有满足条件的点为止。算法适合已确定种子点数量及位置的聚类情况，但在处理相连点云时，单一的生长判定准则和停止条件易产生过分割/欠分割现象。

4)基于模型拟合，有Hough变换、RANSAC分割等。该类方法根据地物的形态骨架特征预设模型参数，通过计算全局点到模型的距离，输出满足置信度及距离阈值的点作为聚类结果。对噪声和异常值的鲁棒性较高，但难以提取非预设模型的地物，在处理大场景点云时，还需对数据做精确的分块处理。

综上，当前基于车载LiDAR的路边地上物聚类算法主要有以下问题：1)需预设多种参数以提高聚类精度，人工干预多且参数复用性差；2)单一算法对相连地物的聚类分割效果不稳定。

发明内容

为此，本发明所要解决的技术问题在于提供一种基于车载LiDAR点云的路边地上物多阶段聚类分割算法，以解决车载LiDAR点云分割存在人工干预多、分割效果不稳定等问题。

为解决上述技术问题，本发明提供如下技术方案：

基于车载LiDAR点云的路边地上物多阶段聚类分割算法，包括如下步骤：

步骤(1)、对车载LiDAR点云数据进行数据预处理，得到路边地上物点云数据；

步骤(2)、对路边地上物点云数据依次进行三维格网化和广度优先搜索，实现路边地上物点云数据的粗聚类分割；粗聚类分割得到单独地物点云和相连地物点云，单独地物点云直接作为路边地上物聚类结果输出；

步骤(3)、将相连地物点云进行欧氏聚类，分割为边界完整的粗聚类点云集；

步骤(4)、预设地物类型并进行地物分类，根据地物分类情况给定聚类阈值初值，利用多段式近邻搜索逐步聚合粗聚类点云集的所有聚类对象；评估各点云的聚合速度，并自适应调整聚类阈值，直至所有聚类对象的点云聚合速度相近，输出相连地物聚类结果，从而完成对路边地上物的聚类分割。

上述基于车载LiDAR点云的路边地上物多阶段聚类分割算法，步骤(2)中，三维格网化时，用体素将路边地上物点云数据进行空间划分，得到分块点云；对分块点云建立三维格网索引I(r,c,l)，以确定其空间拓扑关系。

上述基于车载LiDAR点云的路边地上物多阶段聚类分割算法，对任意一个三维点(x_i,y_i,z_i)，其三维格网索引I(r,c,l)的计算公式为：

式(1)至(3)中，math.floor为向下取整函数，L为体素边长，r、c、l分别为点所在格网的行、列、层号，x_min、y_min、z_min为点云在X、Y、Z方向上的最小值。

上述基于车载LiDAR点云的路边地上物多阶段聚类分割算法，步骤(2)中，利用三维格网化后的起始格网为依据，对三维格网索引进行广度优先搜索；广度优先搜索的算法包括如下步骤：

步骤(2-1)、对每个起始格网做XOY平面上的四邻域搜索，移除搜索到的其他起始格网，使每个起始格网互不连通；

步骤(2-2)、创建开启队列和关闭队列，将一个起始格网压入开启队列；

步骤(2-3)、对开启队列中的首个元素进行六邻域搜索，获取其上下左右前后6个方向上的近邻格网；对每个近邻格网，若存在三维格网索引，未在关闭队列且未在开启队列，则将该格网压入开启队列；所有近邻格网处理完毕后，将开启队列中的首个元素移入关闭队列中；

步骤(2-4)、重复步骤(2-3)，直到开启队列为空，此时关闭队列表示为一块由三维格网索引组成的连通空间，该空间中的点云视为一个聚类对象；

步骤(2-5)、重复步骤(2-2)至步骤(2-4)，即可将点云数据粗分割为两个或两个以上的聚类对象；遍历每个对象的三维格网索引，对于仅存在单个起始格网的对象，输出格网对应的点云作为单独地物聚类结果；若起始格网数大于或等于2，则视为相连地物点云。

上述基于车载LiDAR点云的路边地上物多阶段聚类分割算法，步骤(3)中，欧氏聚类的算法过程如下：

步骤(3-1)、标记相连地物点云中的某点P；利用KD-Tree结构近邻查询离P最近的n个点，将距离小于搜索阈值T_E的点标记并存储到类Q中；

步骤(3-2)、从类Q中选取未用于搜索的某点作为新的点P，利用KD-Tree结构近邻查询离P最近的n个点，将距离小于搜索阈值T_E的点标记并存储到类Q中；

步骤(3-3)、重复步骤(3-2)，直至类Q不再有新点加入，则完成一个聚类；

步骤(3-4)、重复步骤(3-1)至步骤(3-3)，直至相连地物点云中的所有点被标记，即完成欧氏聚类。

上述基于车载LiDAR点云的路边地上物多阶段聚类分割算法，以相连地物点云中点间平均距离

的两倍作为欧氏聚类搜索阈值T_E；点间平均距离

的计算公式为：

式(4)中，函数math.dis计算两点间的欧氏距离，函数math.min返回数列中的最小值。使用同一个激光扫描仪采集含多种地物的点云数据，大部分点的点间最小距离d_i处在

附近，设T_E为两倍的

能保证T_E大于各类地物点云内点的d_i，使欧氏聚类的过程中不产生散点；车载扫描仪采集的数据点云密度高，相连地物中不同地物间的距离往往大于

值，因此参考

生成的粗聚类点云不易有欠分割现象。

上述基于车载LiDAR点云的路边地上物多阶段聚类分割算法，步骤(4)的具体算法如下：

步骤(4-1)、由起始格网得到各地物近似的底部中心，选取最近的粗聚类点云为起始聚类点云；

步骤(4-2)、根据起始聚类点数和地物高度进行地物分类；

步骤(4-3)、进行相连地物点云近邻搜索；

步骤(4-4)、评估各相连地物点云的聚合速度；若各相连地物点云的聚合速度相近，则输出相连地物聚类结果，否则进行自适应调整主体阈值T_main和最远聚合阈值T_max，并再次进行近邻搜索，直至各相连地物点云的聚合速度相近，输出相连地物聚类结果。

上述基于车载LiDAR点云的路边地上物多阶段聚类分割算法，步骤(4-1)中，起始聚类点云的计算方法为：从相连地物点云中选取n个起始格网对应的点云，各自计算出其质心；将质心作为聚类分割后每个独立地物近似的底部中心O_i(x_i,y_i,z_i)(i＝1,2,…,n)；计算O_i到相连地物点云中每个点的欧氏距离D，D值最小的点所对应的粗聚类点云作为起始聚类点云。

上述基于车载LiDAR点云的路边地上物多阶段聚类分割算法，步骤(4-2)中，地物分类的方法为：起始聚类点数量多且地物高度低的起始聚类为灌木类地物；起始聚类点数少且地物高度高的起始聚类为乔木类地物；起始聚类点数多且地物高度高的起始聚类为路灯或指示牌。

上述基于车载LiDAR点云的路边地上物多阶段聚类分割算法，步骤(4-3)中，相连地物点云近邻搜索的算法流程如下：

步骤(4-31)、选取某一粗聚类点云，计算其质心到某起始聚类中n个点的欧氏距离D_i(i＝1,2,…,n)；若粗聚类点云的质心到起始聚类质心的距离大于主体阈值T_main，则舍弃该欧氏距离D_i；

步骤(4-32)、重复步骤(4-31)，直到遍历所有的起始聚类，将满足要求的欧氏距离D_i值中最小的记为D_min，并记录对应的起始聚类，当D_min小于近邻阈值T_near时，将该点云压入类Q；

步骤(4-33)、重复步骤(4-32)，直到遍历所有粗聚类点云，当类Q中没有点云，增大近邻阈值T_near；当类Q中存在点云，将其存入对应的起始聚类，并将近邻阈值T_near设为初值；

步骤(4-34)、重复步骤(4-33)，直到所有粗聚类点云都被存入起始聚类，若近邻阈值T_near大于20倍初值，结束运行。

步骤(4-35)、修改步骤(4-31)的内容为：选取某一粗聚类点云，计算其质心到某起始聚类中n个点的欧氏距离D_i(i＝1,2,…,n)；若D_i大于最远聚合阈值T_max，则舍弃该欧氏距离D_i；

步骤(4-36)、重复步骤(4-34)，即完成相连地物点云近邻搜索。

上述基于车载LiDAR点云的路边地上物多阶段聚类分割算法，为确定各类地物的主体阈值T_main和最远聚合阈值T_max，从单独地物的聚类结果中选取同类地物外包络立方体体积最小的点云，计算其在XOY平面上的点间最远距离D_max，并按比例取D_max值作为该类地物的T_main与T_max值；具体计算公式为：

式(5)中，函数math.max返回数列中的最大值；函数math.disXY将两点投影至XOY平面，计算两投影点间的欧氏距离；对在水平面上的点云投影，D_max表征为其最小覆盖圆的直径。路边地上物点云在水平面上的投影，其最小覆盖圆可反映该类地物大小。较小的同心圆覆盖区域可视为同类地物的聚类主体范围，故以最小覆盖圆的直径作为各类地物T_main与T_max的设置依据。

上述基于车载LiDAR点云的路边地上物多阶段聚类分割算法，步骤(4-4)中，自适应调整阈值T_main、T_max的算法流程如下：

步骤(4-41)、执行多段式近邻搜索；对同一相连地物的n个聚类对象，计算其聚类主体的外包络立方体体积V_m与聚类结果的外包络立方体体积V_r，并记录V_m与V_r的比值R；

步骤(4-42)、取R的最大值为R_max；若有：

R_i∈[R_max - σ,R_max] ,i＝1,…,n (6)；

输出聚类结果并结束程序，式中σ为任意正数；否则，执行步骤(4-43)；

步骤(4-43)、记上一轮中V_m与V_r的比值为R'，若本次为第一轮则R'值为零；

①选取未满足式(6)的对象，若R≥R'，则其聚类主体仍需增大以提高聚合速度，增大该对象的主体阈值T_main；

②选取未满足式(6)的对象，若R＜R'，则其聚类结果出现较大增幅，表明该地物先一步聚合了其他地物的点云，减小该对象的主体阈值T_main和最远聚合阈值T_max；

③若存在未被聚合的粗聚类点云，增大所有聚类对象的最远聚合阈值T_max；

步骤(4-44)、清空本轮的聚类结果，重复步骤(4-41)和步骤(4-42)。

本发明的技术方案取得了如下有益的技术效果：

1、本发明基于车载LiDAR点云的路边地上物多阶段聚类分割算法以点云的三维坐标为依据，先使用三维格网和广度优先搜索算法对点云粗分割，再对相连地物进行欧氏聚类生成若干边界完整的粗聚类点云，使用多段式近邻搜索逐步得到聚类结果，最后根据聚类主体和结果的体积比值评估聚合速度，以此自适应调整聚类阈值或输出结果，实现对道路场景中各类路边地上物的聚类分割。

2、本发明基于车载LiDAR点云的路边地上物多阶段聚类分割算法中设计了自适应调整阈值的算法，引入主体阈值T_main和最远聚合阈值T_max执行两次近邻搜索，先使起始聚类生成聚类主体，再由聚类主体得到聚类分割对象；这种方法能够可避免点云稀疏地物的边缘点云被错分给近邻的地物，从而有效避免过分割现象。本发明通过阈值T_main和T_max的自适应调整，能够有效降低人工干预，提高分割正确率。

3、本发明对行道树的正确提取率为87.0％，对路灯、指示牌的正确提取率为91.9％，均实现有效提取，且过分割/欠分割现象较少；相连地物的聚类结果保有完整的边缘轮廓。

附图说明

图1本发明实施例中车载LiDAR点云多阶段聚类分割技术路线图；

图2本发明实施例中车载LiDAR点云三维格网化效果图；

图3本发明实施例中六邻域判断示意图；

图4a本发明实施例中T_near范围内没有新点时的情况示意图；

图4b本发明实施例中增大T_near，发现新点时的情况示意图；

图4c本发明实施例中新点压入对应聚类，重置T_near时的情况示意图；

图5本发明实施例中实验区点云示意图；

图6本发明实施例中实验数据示意图；

图7a本发明实施例中点云粗分割为单个地物和相连地物的示意图；

图7b本发明实施例中相连地物的起始聚类的示意图；

图7c本发明实施例中聚类主体示意图；

图7d本发明实施例中聚类结果示意图；

图8a本发明实施例中K-Means聚类结果示意图；

图8b本发明实施例中DBSCAN聚类结果示意图；

图8c本发明实施例中MCSA聚类结果示意图；

图9a本发明实施例中K-Means算法的过分割现象示意图(左图为算法的聚类结果，右图为分割真值)；

图9b本发明实施例中DBSCAN算法的过分割现象示意图(左图为算法的聚类结果，右图为分割真值)；

图9c本发明实施例中MCSA算法的过分割现象示意图(左图为算法的聚类结果，右图为分割真值)。

具体实施方式

本实施例中基于车载LiDAR点云的路边地上物多阶段聚类分割算法是一种融合欧氏聚类与近邻搜索的多阶段聚类分割算法(Multi-stage Clustering SegmentationAlgorithm，MCSA)，该算法的特点在于：

1)使用三维格网和广度优先搜索算法实现数据分块，分离单独地物与相连地物；

2)基于区域生长思想，采用迭代近邻搜索渐进聚合点云，聚类结果的边缘轮廓完整，过分割/欠分割现象较少；

3)根据聚类主体与聚类结果的体积比值评估点云聚合速度，自适应调整聚类阈值，减少人工干预。

1算法原理

本实施例的MCSA算法先使用三维格网和广度优先搜索算法对点云进行粗分割，分离出单独地物和相连地物；再将相连地物进行欧氏聚类，分割为若干边界完整的粗聚类点云；然后预设地物类型以给定聚类阈值初值，使用多段式近邻搜索逐步聚合所有对象；最后以聚类主体与聚类结果的体积比值评估点云聚合速度，并自适应调整聚类阈值，直至若干聚类对象的点云聚合速度基本一致时输出结果，实现对路边地上物的聚类分割。算法分为粗分割、欧氏聚类和迭代近邻搜索3个阶段，技术路线如图1所示。

1.1粗聚类分割

1.1.1三维格网化

用体素将点云数据进行空间划分，对分块点云建立三维格网索引I(r,c,l)，以确定其空间拓扑关系。对任意一个三维点(x_i,y_i,z_i)，其三维格网索引计算公式为：

式(1)至(3)中，math.floor为向下取整函数，L为体素边长，r、c、l分别为点所在格网的行、列、层号，x_min、y_min、z_min为点云在X、Y、Z方向上的最小值；本实施例中三维格网化效果见图2。

1.1.2广度优先搜索

三维格网记录了点云的高程范围，其中高程值最小的格网包含了地物底部的点云，称该格网为起始格网。本实施例以起始格网为依据，对三维格网索引使用六邻域的广度优先搜索，以分离出单个地物和相连地物，其算法流程如下：

1)对每个起始格网做XOY平面上的四邻域搜索，移除搜索到的其他起始格网，使每个起始格网互不连通；

2)创建开启队列和关闭队列，将一个起始格网压入开启队列；

3)对开启队列中的首个元素进行六邻域搜索，获取其上下左右前后这6个方向上近邻的格网，对每个近邻格网，若存在三维格网索引、未在关闭队列且未在开启队列，将该格网压入开启队列，所有近邻格网处理完毕后，将开启队列中的首个元素移入关闭队列中；

4)重复步骤3，直到开启队列为空，此时关闭队列表示为一块由若干三维格网索引组成的连通空间，该空间中的点云视为一个聚类对象；

5)重复步骤2-4，可将点云数据粗分割为若干聚类对象。遍历每个对象的三维格网索引，对于仅存在单个起始格网的对象，输出格网对应的点云作为聚类结果；若起始格网数不小于2，则视为相连地物，保留对应点云供后续处理。

1.2欧氏聚类

欧氏聚类是一种基于欧氏距离的聚类算法，适用于不规则区域的分割。欧氏聚类是根据距离值生成聚类的算法，近邻点到P的距离小于搜索阈值，则该近邻点与P同属于一个聚类。算法过程如表1所示，具体为：标记点云中的某点P，利用KD-Tree结构近邻查询离P最近的n个点，将距离小于搜索阈值(即聚类半径阈值)T_E的点标记并存储到类Q中，再从Q中选取未用于搜索的某点作为新的点P，重复这一过程，直至类Q没有新点加入，则完成一个聚类。重复前述过程，直至点云中的所有点被标记，此时点云完成欧氏聚类。

表1欧氏聚类伪代码

使用同一个激光扫描仪采集含多种地物的点云数据，大部分点的点间最小距离处在点间平均距离

附近。为保证欧氏聚类的结果中不含散点，取

的两倍作为欧氏聚类的搜索阈值T_E。

的计算公式为：

式(4)中，函数math.dis计算两点间的欧氏距离，函数math.min返回数列中的最小值。对相连地物点云进行欧氏聚类，得到若干形状完整的粗聚类点云。

1.3多段式近邻搜索

1.3.1起始聚类及地物分类

点云质心是所有点趋向集中的一个假想点，其坐标值为所有点坐标的平均值。从相连地物点云中选取n个起始格网对应的点云，各自计算出其质心，作为聚类分割后每个独立地物近似的底部中心O_i(x_i,y_i,z_i)(i＝1,2,…,n)。计算O_i到相连地物点云中每个点的欧氏距离D，D值最小的点所对应的粗聚类点云作为起始聚类点云。

实验显示，道路两侧常有相连现象的路边地上物为行道树、路灯、指示牌。根据地物的起始聚类点数和地物高度两参数，预设起始聚类的地物类型。其中，灌木类地物的起始聚类点数量较多；乔木类地物高度较高，但因枝叶遮挡，其起始聚类的点数量较少；路灯、指示牌的起始聚类点数量较多且高度较高。此外，受车载LiDAR采集环境所限，地物顶部可能缺失数据。本实施例将原始点云投影到XOY平面上，并沿着数据采集方向，标记起始质心附近范围内的所有点，以高程最大的点作为地物的近似高度。

1.3.2近邻搜索

判断两点云近邻，一种方法是计算点云A中一点P_Ai(i＝1,2,…,n)到点云B的点P_Bj(j＝1,2,…,m)的欧氏距离D_ij，若D_ij值小于近邻阈值T_near，可判断点云A近邻点云B，两者可合并为同一点云。基于这一思想，设计近邻搜索算法流程如下：

1)选取某一粗聚类点云，计算其质心到某起始聚类中n个点的欧氏距离D_i(i＝1,2,…,n)；

2)重复步骤1，直到遍历所有的起始聚类，欧氏距离D_i值最小的为D_min，并记录对应的起始聚类，当D_min小于阈值T_near时，将该点云压入类Q；

3)重复步骤2，直到遍历所有粗聚类点云，当类Q中没有点云，增大阈值T_near(图4a、图4b)；当类Q中存在点云，将其存入对应的起始聚类，并将T_near设为初值(图4b、图4c)；

4)重复步骤3，直到所有粗聚类点云都被存入起始聚类，若T_near过大(大于20倍初值)，结束运行。

1.3.3自适应阈值设置

近邻搜索算法能保证起始聚类点云渐进式地聚合粗聚类点云，但若某个地物的起始聚类近邻不存在点云，直接使用近邻搜索算法会使该地物的聚类结果仅包含起始聚类，而其他地物出现过分割现象。为避免该现象，引入主体阈值T_main和最远聚合阈值T_max以执行两次近邻搜索，先使起始聚类生成聚类主体，再由聚类主体得到聚类分割对象。T_main促使起始聚类只聚合一定范围内的粗聚类点云，让每个聚类主体的外包络立方体体积与理想聚类结果的比值大致相同；T_max表现为聚类主体聚合近邻点云的最远距离，在聚合过程中，稀疏地物的边缘点云可能会被近邻的稠密地物先一步聚合，依据地物类型设置不同的T_max能影响聚类结果的大小，有效避免这类过分割现象。为确定各类地物的T_main与T_max值，从单独地物的聚类结果中选取同类地物外包络立方体体积最小的点云，计算其在XOY平面上的点间最远距离D_max，并按比例取D_max值作为该类地物的T_main与T_max值。

式(5)中，函数math.max返回数列中的最大值；函数math.disXY将两点投影至XOY平面，计算两投影点间的欧氏距离；对在水平面上的点云投影，D_max表征为其最小覆盖圆的直径。

加入上述两种阈值为判断条件，对粗聚类点云先后执行两次附以不同条件的近邻搜索。在第一次近邻搜索中，执行1.3.2的步骤1后，若粗聚类点云的质心到起始质心的距离大于T_main，舍弃D_i，以限制聚类主体的大小。在第二次近邻搜索中，执行1.3.2的步骤1后，若D_i大于T_max，舍弃D_i。该条件可避免点云稀疏地物的边缘点云被错分给近邻的地物。执行上述的多段式近邻搜索，可将相连地物聚类分割为多个独立地物。

相连地物的各项理想阈值往往存在差异，为减少阈值设置的人工干预，设计如下算法，使阈值T_main、T_max在设置初值后，对各类地物具有自适应性：

(1)执行多段式近邻搜索。对同一相连地物的n个聚类对象，计算其聚类主体的外包络立方体体积V_m与聚类结果的外包络立方体体积V_r，并记录V_m与V_r的比值R。

(2)取R的最大值为R_max。若有

R_i∈[R_max - σ,R_max] ,i＝1,…,n (6)

输出聚类结果并结束程序，式中σ为任意正数。否则，执行步骤3。

(3)记上一轮中V_m与V_r的比值为R'，若本次为第一轮该值为零。分3种情况执行：①选取未满足式(6)的对象，若R≥R'，则其聚类主体仍需增大以提高聚合速度，增大该对象T_main；②选取未满足式(6)的对象，若R＜R'，则其聚类结果出现较大增幅，表明该地物先一步聚合了其他地物的点云，减小该对象T_main和T_max；③若存在未被聚合的粗聚类点云，增大所有聚类对象的T_max。

(4)清空本轮的聚类结果，重复步骤1、2。

2实验分析

2.1实验数据及环境

为验证本实施例算法的有效性，使用VC++语言实现该算法，利用SSW-3型车载激光扫描系统采集的道路场景点云数据进行实验验证。采集设置点频为500kHz，转速为100r/s，扫描间隔为0.02m，扫描距离为150m，沿道路两侧往返扫描。实验区如图5所示，该区域点云数据采集时间为2019-12-30，实验区位于河南省焦作市河南理工大学南门附近的凯旋路部分路段，全长562m，场景中主要包括建筑物、路灯、行道树、低矮灌木、车辆、电线杆、道路交通指示牌等地物。

2.2数据预处理

聚类分割的对象是道路两侧一定宽度内的路灯、行道树、指示牌等路边地上物，不包含对地面点云及建筑物的分割，利用CloudCompare软件保留实验主区域，再使用布料模拟滤波算法滤除地面点，生成的实验数据高程跨度11.88m，点数为2 094 941个，点间平均距离为0.059m，其结果如图6所示。将数据集投影至XOY平面并进行单位格网划分，通过统计投影点的外包络格网数，近似得到数据的扫描面积为3786m²，点云密度为553个/m²。

2.3实验结果

原始点云预处理完成后，对点云进行三维格网化，按式(1)至(3)将体素边长L值设为1m，构建行、列、层数为546*125*24的三维格网索引；以起始格网为依据，通过广度优先搜索算法，将输入点云粗分割为单个地物和相连地物(图7a)；然后对相连地物的点云执行欧氏聚类，搜索阈值T_E设为0.12m，分割得到若干轮廓完整的粗聚类点云。由起始格网得到各地物近似的底部中心，选取最近的粗聚类点云为起始聚类(图7b)；根据起始聚类点数和地物高度进行地物分类，按点云近邻参考值及式(5)给定聚类阈值初值(表2)，设σ值为0.2；进行第一次近邻搜索，生成聚类主体(图7c)；执行第二次近邻搜索，渐进式地聚合余下的粗聚类点云，若生成的聚类结果未满足式(6)，自适应调整阈值T_main和T_max并重新执行多段式近邻搜索，直至得到最终聚类结果(图7d)。

表2各地物聚类阈值初值

2.4精度分析

为验证MCSA算法的有效性，选取当前有代表性的K-Means聚类算法、DBSCAN算法与本实施例的算法进行对比分析，以正确提取率(Right Draw Ratio,RDP)对三种算法的聚类结果进行定量评价，RDP定义见式(7)。三种算法的聚类结果如图8a至图8c所示。

式(7)中：u为正确分割数，v为错误分割数。

汇总各算法的聚类数据至表3，MCSA算法对行道树的RDP为87.0％，对路灯和指示牌地物的RDP为91.9％，综合分割精度优于K-Means算法与DBSCAN算法。三种算法的聚类结果中都存在过分割现象(图9a至图9c)。柳树因树冠疏散、枝叶层叠，其树干部分的点云较完整，但树冠数据集中在地物的外缘及远离采集路径一侧，其内部数据常有缺失。在使用K-Means算法处理该类地物时，因柳树冠幅较大，同一地物可能有多个初始聚类簇心，从而输出多个分割对象；DBSCAN算法随机选取种子点，将与其密度可达的所有点输出为聚类，导致聚类结果中有许多欠分割的相连树，一些悬空的致密离散点也被输出为分割对象。相较之下，MCSA算法在粗分割阶段以地物底部点云的质心作为聚类种子点，避免了对同一地物多次分割，也保证了地物边缘的离散点可被近邻搜索聚合进附近的点云中。

表3分割精度评价

MCSA算法的聚类结果仍有少量过分割和欠分割现象，原因有：

1)对灌木类地物与乔木类地物的部分重叠区域，低矮植株因整体连通性强，由聚类主体到分割对象的聚合过程更快，往往会先一步聚合乔木类地物的边缘点云，通过提高乔木类地物的主体阈值T_main初值，使两类地物的聚合速度一致，减少该类过分割现象；

2)在进行广度优先搜索时，两地物底部因近邻而引起起始格网合并，导致在聚类过程中只使用一个种子点进行聚类(图7d右下角，两个邻近路灯聚类为同一地物)，可使用边长L更小的体素进行三维格网化来减少该类欠分割现象；

3)在近邻搜索中，因乔木类地物的树冠中部缺少点云，原属于该地物的边缘、悬空点云被灌木类地物聚合，可通过调低灌木类地物的最远聚合阈值T_max初值，减少该类过分割现象。

为检验MCSA算法的聚类质量，采用密实度(Compactness，CP)和分离度(Separation，SP)指标对MCSA算法的聚类结果进行评价。

式(8)和(9)中，Ω为簇的点总数，w为簇的聚类中心，x为簇中一点，K为簇总数。由MCSA算法得到的聚类结果CP值为1.798m，SP值为191.696m，从中取20组簇如表4所示。

表4部分聚类质量评价

3结论

欧氏聚类算法能将点云分割为若干轮廓完整的聚类，近邻搜索算法可渐进式地聚合近邻点云。本实施例融合两者的特点，提出一种仅需点云三维坐标的多阶段算法，以完成道路场景点云的聚类分割任务。实验结果表明，算法对行道树的正确提取率为87.0％，对路灯、指示牌的正确提取率为91.9％，均实现有效提取，且过分割/欠分割现象较少；相连地物的聚类结果仍保有完整的边缘轮廓。

Claims (10)

1.基于车载LiDAR点云的路边地上物多阶段聚类分割算法，其特征在于，包括如下步骤：

步骤(1)、对车载LiDAR点云数据进行数据预处理，得到路边地上物点云数据；

步骤(2)、对路边地上物点云数据依次进行三维格网化和广度优先搜索，实现路边地上物点云数据的粗聚类分割；粗聚类分割得到单独地物点云和相连地物点云，单独地物点云直接作为路边地上物聚类结果输出；

步骤(3)、将相连地物点云进行欧氏聚类，分割为边界完整的粗聚类点云集；

步骤(4)、预设地物类型并进行地物分类，根据地物分类情况给定聚类阈值初值，利用多段式近邻搜索逐步聚合粗聚类点云集的所有聚类对象；评估各点云的聚合速度，并自适应调整聚类阈值，直至所有聚类对象的点云聚合速度相近，输出相连地物聚类结果，从而完成对路边地上物的聚类分割。

2.根据权利要求1所述的基于车载LiDAR点云的路边地上物多阶段聚类分割算法，其特征在于，步骤(2)中，三维格网化时，用体素将路边地上物点云数据进行空间划分，得到分块点云；对分块点云建立三维格网索引I(r,c,l)，以确定其空间拓扑关系；

对任意一个三维点(x_i,y_i,z_i)，其三维格网索引I(r,c,l)的计算公式为：

式(1)至(3)中，math.floor为向下取整函数，L为体素边长，r、c、l分别为点所在格网的行、列、层号，x_min、y_min、z_min为点云在X、Y、Z方向上的最小值。

3.根据权利要求1所述的基于车载LiDAR点云的路边地上物多阶段聚类分割算法，其特征在于，步骤(2)中，利用三维格网化后的起始格网为依据，对三维格网索引进行广度优先搜索；广度优先搜索的算法包括如下步骤：

步骤(2-1)、对每个起始格网做XOY平面上的四邻域搜索，移除搜索到的其他起始格网，使每个起始格网互不连通；

步骤(2-2)、创建开启队列和关闭队列，将一个起始格网压入开启队列；

步骤(2-3)、对开启队列中的首个元素进行六邻域搜索，获取其上下左右前后6个方向上的近邻格网；对每个近邻格网，若存在三维格网索引，未在关闭队列且未在开启队列，则将该格网压入开启队列；所有近邻格网处理完毕后，将开启队列中的首个元素移入关闭队列中；

步骤(2-4)、重复步骤(2-3)，直到开启队列为空，此时关闭队列表示为一块由三维格网索引组成的连通空间，该空间中的点云视为一个聚类对象；

步骤(2-5)、重复步骤(2-2)至步骤(2-4)，即可将点云数据粗分割为两个或两个以上的聚类对象；遍历每个对象的三维格网索引，对于仅存在单个起始格网的对象，输出格网对应的点云作为单独地物聚类结果；若起始格网数大于或等于2，则视为相连地物点云。

4.根据权利要求1所述的基于车载LiDAR点云的路边地上物多阶段聚类分割算法，其特征在于，步骤(3)中，欧氏聚类的算法过程如下：

步骤(3-1)、标记相连地物点云中的某点P；利用KD-Tree结构近邻查询离P最近的n个点，将距离小于搜索阈值T_E的点标记并存储到类Q中；

步骤(3-2)、从类Q中选取未用于搜索的某点作为新的点P，利用KD-Tree结构近邻查询离P最近的n个点，将距离小于搜索阈值T_E的点标记并存储到类Q中；

步骤(3-3)、重复步骤(3-2)，直至类Q不再有新点加入，则完成一个聚类；

步骤(3-4)、重复步骤(3-1)至步骤(3-3)，直至相连地物点云中的所有点被标记，即完成欧氏聚类。

5.根据权利要求4所述的基于车载LiDAR点云的路边地上物多阶段聚类分割算法，其特征在于，以相连地物点云中点间平均距离

的两倍作为欧氏聚类搜索阈值T_E；点间平均距离

的计算公式为：

式(4)中，函数math.dis计算两点间的欧氏距离，函数math.min返回数列中的最小值。

6.根据权利要求1所述的基于车载LiDAR点云的路边地上物多阶段聚类分割算法，其特征在于，步骤(4)的具体算法如下：

步骤(4-1)、由起始格网得到各地物近似的底部中心，选取最近的粗聚类点云为起始聚类点云；

步骤(4-2)、根据起始聚类点数和地物高度进行地物分类；

步骤(4-3)、进行相连地物点云近邻搜索；

步骤(4-4)、评估各相连地物点云的聚合速度；若各相连地物点云的聚合速度相近，则输出相连地物聚类结果，否则进行自适应调整主体阈值T_main和最远聚合阈值T_max，并再次进行近邻搜索，直至各相连地物点云的聚合速度相近，输出相连地物聚类结果。

7.根据权利要求6所述的基于车载LiDAR点云的路边地上物多阶段聚类分割算法，其特征在于，步骤(4-1)中，起始聚类点云的计算方法为：从相连地物点云中选取n个起始格网对应的点云，各自计算出其质心；将质心作为聚类分割后每个独立地物近似的底部中心O_i(x_i,y_i,z_i)(i＝1,2,…,n)；计算O_i到相连地物点云中每个点的欧氏距离D，D值最小的点所对应的粗聚类点云作为起始聚类点云；

步骤(4-2)，地物分类的方法为：起始聚类点数量多且地物高度低的起始聚类为灌木类地物；起始聚类点数少且地物高度高的起始聚类为乔木类地物；起始聚类点数多且地物高度高的起始聚类为路灯或指示牌。

8.根据权利要求6所述的基于车载LiDAR点云的路边地上物多阶段聚类分割算法，其特征在于，步骤(4-3)中相连地物点云近邻搜索的算法流程如下：

步骤(4-31)、选取某一粗聚类点云，计算其质心到某起始聚类中n个点的欧氏距离D_i(i＝1,2,…,n)；若粗聚类点云的质心到起始聚类质心的距离大于主体阈值T_main，则舍弃该欧氏距离D_i；

步骤(4-32)、重复步骤(4-31)，直到遍历所有的起始聚类，将满足要求的欧氏距离D_i值中最小的记为D_min，并记录对应的起始聚类，当D_min小于近邻阈值T_near时，将该点云压入类Q；

步骤(4-33)、重复步骤(4-32)，直到遍历所有粗聚类点云，当类Q中没有点云，增大近邻阈值T_near；当类Q中存在点云，将其存入对应的起始聚类，并将近邻阈值T_near设为初值；

步骤(4-34)、重复步骤(4-33)，直到所有粗聚类点云都被存入起始聚类，若近邻阈值T_near大于20倍初值，结束运行。

步骤(4-35)、修改步骤(4-31)的内容为：选取某一粗聚类点云，计算其质心到某起始聚类中n个点的欧氏距离D_i(i＝1,2,…,n)；若D_i大于最远聚合阈值T_max，则舍弃该欧氏距离D_i；

步骤(4-36)、重复步骤(4-34)，即完成相连地物点云近邻搜索。

9.根据权利要求6所述的基于车载LiDAR点云的路边地上物多阶段聚类分割算法，其特征在于，为确定各类地物的主体阈值T_main和最远聚合阈值T_max，从单独地物的聚类结果中选取同类地物外包络立方体体积最小的点云，计算其在XOY平面上的点间最远距离D_max，并按比例取D_max值作为该类地物的T_main与T_max值；具体计算公式为：

式(5)中，函数math.max返回数列中的最大值；函数math.disXY将两点投影至XOY平面，计算两投影点间的欧氏距离；对在水平面上的点云投影，D_max表征为其最小覆盖圆的直径。

10.根据权利要求6所述的基于车载LiDAR点云的路边地上物多阶段聚类分割算法，其特征在于，步骤(4-4)中自适应调整主体阈值T_main和最远聚合阈值T_max的算法流程如下：

步骤(4-41)、执行多段式近邻搜索；对同一相连地物的n个聚类对象，计算其聚类主体的外包络立方体体积V_m与聚类结果的外包络立方体体积V_r，并记录V_m与V_r的比值R；

步骤(4-42)、取R的最大值为R_max；若有：

R_i∈[R_max-σ,R_max],i＝1,…,n (6)；

输出聚类结果并结束程序，式中σ为任意正数；否则，执行步骤(4-43)；

步骤(4-43)、记上一轮中V_m与V_r的比值为R'，若本次为第一轮则R'值为零；

①选取未满足式(6)的对象，若R≥R'，则其聚类主体仍需增大以提高聚合速度，增大该对象的主体阈值T_main；

②选取未满足式(6)的对象，若R＜R'，则其聚类结果出现较大增幅，表明该地物先一步聚合了其他地物的点云，减小该对象的主体阈值T_main和最远聚合阈值T_max；

③若存在未被聚合的粗聚类点云，增大所有聚类对象的最远聚合阈值T_max；

步骤(4-44)、清空本轮的聚类结果，重复步骤(4-41)和步骤(4-42)。

Images