车载激光扫描数据的结构化道路要素自动提取方法

韩 旭，梁新美

(中国地质大学(武汉),湖北 武汉 430074)

随着近年来无人驾驶、机器导航的出现和发展，对道路识别的研究日益受到重视，从原先基于单目影像的二维视觉逐步开始侧重立体视觉方面[1]，三维激光点云数据的处理及基于点云数据提取道路要素的研究变得更加重要[2]。而车载点云数据作为道路两侧三维数据获取的重要来源[3]，是道路提取的重点研究数据,从车载激光点云中准确提取道路结构，是三维建模领域需要首要解决的重要问题之一[4]。虽然在机载激光扫描点云数据中相关研究已经较为深入，但由于扫描方式、点云密度、几何特征等不同，机载激光点云数据的处理方式并不完全适用于移动激光扫描点云数据[5]，相比前者，从后者提取道路更为艰难[6]。本文研究在不同层次对象提取不同特征的方法，在满足一定精度的基础上尽可能地提高效率。

1 点云预处理

常见的道路结构类型一般由车道、人行道及二者的连接结构路坎组成[7]。

车载扫描系统扫描轨迹线通常沿道路延伸方向获取道路及其周边的点云数据，且通常包含扫描角度信息[8]。另外，由于特征提取极为耗时[9]，因此可以通过扫描角度约束将点云分割，获得感兴趣区域，缩小处理范围。约束公式为

SI={Pi|-45°≤θ(Pi)≤45°,Pi∈Spart}

(1)

式中，SI为扫描角度约束后的点集；Spart为车载扫描点云片段点集；θ(Pi)为点Pi的扫描角度。

2 基于局部特征约束的点云分割

点云的局部特征可以用来反映点云在极小范围内扫描值的变化规律，从而对点云进行标识和分类。本文利用高程梯度约束方法将点云标记为道路点和路坎点两类，然后进行点云的初步分割。

2.1 高程梯度定义

高程梯度可以用来反映点云局部高程变化的快慢，可区分立面点云和水平面点云。各点在局部的高程变化信息可用于区分道路和路坎。目前点云梯度并没有明确的定义[10]，大多数点云梯度计算是投影到二维平面进行梯度计算，如Yang等[11]、Huang等[12]、Xia等[13]按各点值在坐标轴方向变化的最大值来分析变量变化的特征，Xu等[10]则是将二维Robert算子的定义从二维像素拓展到三维格网求梯度，直接将基于像素的图像处理方法使用于基于格网的三维点云计算。本文采用图像梯度及数学中函数梯度的定义和思想，对三维离散点直接计算梯度大小。

(1) 梯度定义中将点值变化量分别在x、y、z轴投影，得到3个方向的局部投影变化量Fx、Fy、Fz，再将投影变化量除以变化“距离”，得到局部投影变化率为

(2)

(2) 对所有邻域点的投影变化率求和为

(3)

(3) 将结果除以点数，以得到投影变化率的平均值，得到梯度大小为

(4)

2.2 局部特征约束

依照本文对高程梯度大小的定义，在水平结构中高程变化接近0，位于立面结构的点云计算出的高程梯度值一般较大。结合实际经验，选取不同的梯度阈值按式(5)和式(6)将点云分割为两类，从而区分立面点云和水平点云。

Sh,l={Pi|Pi∈SI,Hgra(Pi)

(5)

Sf,l={Pi|Pi∈SI,Hgra(Pi)>Gv}

(6)

式中，Sh,l为近似的局部水平点集；Sf,l为近似的局部立面点集；Hgra(Pi)为点Pi的高程梯度。

3 多尺度聚类点云提取方法

通过局部特征约束分割后的点云仍包含较多的非目标点云，而它与目标点云在局部特征上表现相似，难以在单个点或局部点云中定义其他有效的特征进行分类。

由于经过局部特征约束后得到的道路备选点和路坎备选点在欧氏空间内成“块”状分布，因此进一步分割可先采用聚类算法在欧氏空间将点云分割成“簇”，并按其几何特征提取包含目标点云的簇[14]。

3.1 基于26方向邻域和遍历标记法的连通域聚类分割方法

利用八叉树对点云划分格网可以建立点之间的拓扑关系[15]，因此本文聚类前需先将点云划分格网。本文借鉴二维图像处理中基于遍历标记法的连通域分割算法，将二维像素标记拓展到三维格网标记，将4方向或8方向邻域拓展到26方向邻域。实现方法如下：

(1) 按特定尺度将待处理的已经过局部特征约束标记属性(道路属性、路坎属性)的点云数据划分格网，采用三元组编号，如第i列第j行第k层的格网编号为(i,j,k)，初始标记Label(i,j,k)=0。

(2) 按一定顺序遍历格网，格网(i,j,k)包含点云时，首先判断该格网26个相邻格网的标记类型：如果该格网邻域内不包含任何类别的格网，则将该格网标记Label(i,j,k)加1，表示增加了一个临时聚类类别；如果该格网邻域内存在Label值不为零的格网，邻域内Label集合中超过两个元素，则将该格网Label值取为邻域内最小的非零Label值，即Label(i,j,k)=min{邻域内非零Label值}，且将此时该邻域的所有非零Label值加入到新的集合类型I={邻域内非零Label值}作为一个新的类型子集。

(3) 遍历所有格网，将所有合并的Label集合I中的元素全部赋值为集合中最小的Label值，即Label∈I=min(I)。

3.2 聚类尺度的确定

该聚类算法需要首先将点云划分格网，而格网的大小(尺度)会影响邻接关系和类别的判断，点云所属的格网及其之间的邻接关系也会发生变化，聚类所得到的类别也就不同。一般而言，使用越小的尺度聚类，分割程度越大，得到的簇越多，同一目标被分割成不同簇的可能性越大(过分割)，同时消耗的时间也就越多；反之，尺度越大则不同目标被分割成同一个簇的可能性越大(欠分割)，耗时越少。

综上选择合适的尺度进行聚类是实现聚类分类的关键，可以通过对样本数据(包括了包含弯曲道路片段的点云、包含直线道路片段的点云、包含转角道路片段的点云及道路结构特征不同的点云)在不同尺度下聚类进行分割情况统计获得较好的尺度，用分割比Rseg表示，当Rseg<1时，表示欠分割，当Rseg>1时表示过分割。

(7)

式中，N为目标的理论结构个数(如车道N一般为1，人行道和路坎N一般大于2)；ni为理论个数为1时(单个结构)对应实际分割得到的个数，当簇中包含有非目标点云块时(即聚类块中有明显的非路坎或非道路的点集，且这些点在采用更小的尺度时有较大可能被分割成不同的类别)，ni=0。

该统计结果仅作为尺度选取的参考，在实际处理中由于道路结构的不同、选取道路片段的长度不同，上述值也会有所差异。

4 结构化道路的道路簇和路坎簇提取

城市结构化道路中行车道与人行道类似，具有如下特点：①一般为平面状；②路面坡度一般小于10%，坡面较为平缓，沿水平方向延伸；③道路表面较为平坦，高程变化点少；④路面面积较大，包含的点较多；⑤主干道路包含扫描角度为零的点云。路坎作为连接路面的分割面，与道路类存在拓扑关系，同时路坎具有如下特点：①形状为细长状；②延伸方向接近水平，且沿该方向高程变化平缓；③平均高程与道路相差较小；④路坎与道路邻接，且位于人行道和车道之间；⑤路坎与扫描轨迹线形状相似(切线方向变化规律一致)。基于上述特点，本文将对道路备选点提取形状、尺度、姿态和位置特征，对路坎备选点提取形状和姿态、空间分布特征，通过特征约束实现车道、人行道和路坎点云的提取。

4.1 多尺度聚类的道路簇提取

试验表明，在小尺度下，车道点云一般处于连通域，不会被标记为多个类别，人行道点云在该尺度下位于不同的连通域，易被标记为多个类别；而在大尺度情况下，人行道则易与车道被标记为同一类别。据此，得到车道点集Sdw和人行道点集Ssw为

(8)

式中，Sdw,sml为小尺度下标记的车道点集；Ssw,sml为小尺度下标记的人行道点集；Srd,lg为大尺度下标记的道路点集。

由于被标记为同一个类别的所有格网一定是处于连通域的，因此，为了使得大尺度下人行道和车道被标记为同一类，应该有至少一组相邻的格网同时包含车道点和人行道路点云。

为了更好地提取簇的几何特征，采用随机采样一致性算法(random sample consensus,RANSAC)对平面拟合的思想，利用内点和外点判断一个簇的平面性，从而避免最小二乘法拟合平面时非目标点的影响。具体计算中采用梅森旋转算法采样若干点(如1000个)，首先利用最小二乘法拟合平面，将距离该平面小于阈值(考虑道路面有弧度，本文取0.02 m)的点记为内点，其余记为外点，统计迭代30次内最大的内点数作为该簇最终的内点数，用于定义簇的形状特征。

按照道路的特点，对聚类分割得到的每个簇提取形状、尺度、姿态和位置特征见表1。

表1 道路簇表征参数

4.2 路坎簇提取

路坎的形状、姿态特征可以使用最小外包盒(minimum bounding box,MBB)衡量，最小外包盒的各边平行于坐标轴，图1为几种简化的路坎结构。

图1 不同路坎结构及最小外包盒示意图

定义路坎的形状和姿态描述特征量为

(9)

式中，X、Y、Z为簇内点坐标x、y、z值的最大差值，即最小外包盒的长、宽、高。

由于路坎(片段)在近似水平方向延伸，因此Sh值越小越有可能是路坎，限制Sh的最大阈值，可以去除汽车、树木、行人等呈块状结构的簇和垂直结构的簇。

除此之外，为了去除一些与路坎在几何形态上类似的簇，定义特征量An以描述簇的空间分布特征。

(10)

式中，Ai为簇内点Pi的扫描角度；N为簇内点的数量。

在结构化道路中，路坎在空间分布上的特征应该是位于车道和人行道之间，平均扫描角度一般情况下应在两侧人行道平均扫描角度所构成的区间内，如图2所示。

图2 基于平均扫描角度的簇标记

路坎簇标记和提取公式为

(11)

5 实例验算

试验数据由车载激光扫描系统在武汉大学扫描获取。数据采集共包含约2.1×109个点，试验数据为车载激光扫描在WGS-84坐标系下的原始数据。

为验证本文算法的有效性，在分割的道路片段中选取数据测试。原始数据包含大量散乱树叶及行人、汽车等非目标点云数据，点云分布十分密集。对数据按照本文的方法进行测试。其中局部特征约束的结果如图3所示，聚类标记的结果如图4所示。

图3 局部特征约束目标提取及标记结果

由图3可见，滤除了大量稀疏点，已基本不包含道路上方的枝叶、距离道路较远的散乱独立地物和一些离散的点云数据，但仍存在较多的树干、行人及非道路地面点，该阶段标记的道路备选点云多为在局部水平分布的点云，而标记的路坎备选点云多为局部垂直分布的立面点云。

从最终的提取结果(如图4所示)来看，非目标点云已经滤除，而且提取的目标点云保留较为完整。

图4 目标提取及标记结果

6 结 语

本文提供了一种基于局部特征和多尺度聚类的道路要素点云提取的完整方法。首先对点云提取局部特征和特征约束分割，并逐层计算特征值和滤除点，从而在点层次标记出道路备选点和路坎备选点；然后采用一种基于遍历标记法的连通域聚类算法，分别将道路备选点和路坎备选点分割成不同的簇，在不同尺度上对每个簇提取对于识别目标(人行道、车道、路坎)有效的描述其形状、尺度、姿态等特点的特征量，利用RANSAC算法提取簇的平面特性，结合不同目标的几何特征，在簇层次标记出车道簇、人行道簇和路坎簇。结果表明，该方法效果较好，提取的车道点云、人行道点云和路坎点云具有较高的准确率和召回率，可以用于车载激光扫描数据的结构化道路目标的识别，并为无人驾驶等应用提供服务。