一种依据点云法向量相似度的结构化道路提取方法

安瑶军，陈晓轩，隋立春,3，周荣荣

(1. 长安大学地质工程与测绘学院，陕西 西安 710054； 2. 陕西省交通规划设计研究院，陕西 西安 710065； 3. 地理国情监测国家测绘地理信息局工程技术研究中心，陕西 西安 710064)

高精度、准确、现势性强的道路三维信息对于道路维护、交通管理、城市规划等具有重要作用[1]。近年来，以车辆为搭载平台，集成GPS、INS、激光扫描仪、CCD相机等多种传感器，在传感器同步控制的基础上，能够获取城市街道、建筑物立面的几何数据和纹理信息，为道路信息快速获取、更新及三维道路环境自动提取开辟了新的途径[2]。

目前，国内外从车载点云数据中提取道路信息的研究方法主要可以归纳为从点云投影的特征图像中间接提取和从离散点云直接提取两类。

在点云投影的特征图像中提取方面，主要依据城市环境中路面与邻域之间的高程或密度差异，将原始点云数据转换成特征图像[3-6],再结合图像处理的相关算法进行道路信息的提取。此类算法需要将离散点云转换成格网，降低了原始数据的精度和分辨率。

在离散点云数据直接提取方面，闫利等[7]分析了道路点云法向量的分布特征，结合模糊聚类算法对道路面点云进行滤波；方莉娜等[2]提出了一种结构化道路自动提取方法，适合道路边缘点较为突出的道路；Yuan[8]按扫描线进行模糊聚类的方法提取近似水平的长直线作为路面，但当路面有遮挡时算法的准确性不高；Smadja等[9]基于随机抽样一致性算法(RANSAC)提取路面点云；Zhan等[10]通过解算每个点的法向量、法向量残差、离散度等特征，利用支持向量机(SVM)的方法将点云数据分为地面、斜坡及树木等。

本文结合道路面的点云法向量分布特征，提出一种依据点云法向量相似度的结构化道路提取方法。

1 车载点云的道路提取方法

1.1 非地面点滤波

城镇道路环境通常比较复杂，原始车载点云中包括道路两侧大量的树木、路灯、电线杆及路面上的汽车等非路面目标，这些非地面点会对点云局部法向量的准确计算和道路提取的效率、准确度带来干扰，因此需要对原始点云滤波剔除非地面点。

本文采用Zhang[11]提出的基于布料模拟的滤波算法(CSF)，该地形滤波算法稳健性较强，参数较少且速度快，适用于车载点云滤波。布料模拟滤波算法的滤波过程类似于一种简单的物理过程模拟。假如地形表面正上方有块虚拟布料，在重力作用下覆盖在地形表面上，如果布料足够柔软，则布料的最终形状就是数字表面模型(DSM)。同理可得，如果把原始地形翻转过来，同时布料具有一定的硬度,则在同样的重力作用下布料最终的形状就是数字高程模型(DEM)。布料模拟的原理如图1所示。

图1 CSF算法模拟示意图

1.2 法向量及曲率估算原理

1.2.1 基于KD-tree的k邻域搜索

点云数据缺乏离散点间的几何拓扑信息，为了实现基于邻域关系的快速近邻查找，要建立原始点云离散点间的拓扑关系。KD-tree由Bentley[12]于1975年首先提出，是一种分割k维数据空间的数据结构，其本质是带有约束条件的二分查找树，主要应用于多维空间数据中的近邻搜索(KNN)和范围搜索(FDN)。KD-tree在三维空间的结构如图2所示。

图2 三维KD-tree空间分割

1.2.2 基于PCA的法向量估算

离散点云中每个激光点的法向量可以采用局部邻域拟合的切平面的法向量近似表示。Hoppe等采用局部切平面拟合方法来估算某点的局部法向量[13]，原理如图3所示。

对点云数据中每个点pi={xi,yi,zi}，通过邻域查找获得k个邻域点，然后根据距离最小二乘准则计算出该点的局部拟合平面P，平面P可以用如下数学方程表示

(1)

式中，n为平面P的法向量；d为P到坐标原点的距离；argmin为目标函数取最小值时的变量值。

通过计算可知，k个近邻点的三维质心位于平面P上，且法向量n为单位向量，满足nTn=1。运用主成分分析方法(principal component analysis, PCA)，将求解点云法向量的问题转化成k个近邻点构建的协方差矩阵C特征值分解的问题。协方差矩阵C最小特征值对应的特征向量即为需要求解的法向量。

(2)

C·vi=λi·vi,j∈{0,1,2}

(3)

由于特征值λ0<λ1<λ2分别代表了点在3个主方向上的变化程度，因此点pi的曲率Ki可以用下式近似估算

(4)

1.3 改进的区域生长算法

结构化道路路面区域点云的法向量分布较为集中，总体呈竖直方向，且在道路边缘处与路缘石等地物的法向量方向存在显著性差异。因此利用路面点云的法向量方向相似性作为约束条件，采用区域生长[14-15]的算法分割出道路面点云。

针对传统区域生长法通常随机选取种子点，容易导致过分分割且效率低下的问题，结合路面提取目标，对种子点的选取准则进行改进。结构化道路的空间特征如图4所示，表现为局部比较平坦，同时路面点高程一般略低于周围人行横道等其他地物。因此，本文首先对原始点云按高程进行升序排列，再选择其中曲率最小的点作为道路种子点。算法具体流程如下：

(1) 对输入的原始点云按高程进行升序排列，计算各点的法向量ni与曲率Ki，再对曲率Ki进行排序，将曲率最小的点确定为种子点。

(2) 对当前种子点搜索其邻域点(KNN或FDN)，并计算邻域点的法向量与当前种子点的法向量夹角Si及各邻域点的曲率值Ki。

(3) 若法向量夹角Si

(4) 当前种子点出队，若种子点队列不为空，选出新种子点，回到步骤(2)。

上述分割过程结束后，聚类结果除路面区域外可能还有一些近似平面点群区域。道路路面所在区域一般为最大连通区域，且区域平均高程较小。因此可以设置阈值参数剔除非路面区域而得到道路面点云。

图4 道路空间特征分布示意图

2 试验与分析

2.1 试验数据

试验采用某车载移动测量系统获取的两组不同城镇环境下比较典型的点云数据。数据1为城市高架，共包含3 689 279个激光点，长度约为300 m，道路宽度比较规则，路面呈坡状，主要为弯曲道路，如图5(a)所示；数据2为街区主干道，共包含1 519 065个激光点，长度约为120 m，道路宽度在局部不一致，路面整体比较平坦，如图5(b)所示。两组数据中均包含道路、行道树、路灯、电力设施及汽车等地物。

图5 原始车载点云数据

2.2 试验结果与分析

首先，使用开源点云数据处理软件CloudCompare中的布料模拟滤波算法对两组原始车载点云进行滤波。数据1整体为坡度地形，因此硬度参数设为2、大格网分辨率为1.5 m、距离阈值为0.5 m、迭代次数为150次，同时选中坡度拟合因子进行边坡后处理。数据2整体比较平坦，因此硬度参数设为1，其余参数保持不变。两组数据使用布料模拟滤波后的结果如图6所示，滤波后的点云数据主要包括道路和道路两旁的人行道区域，其中出现的空洞是车辆被滤波去除后所致。

图6 滤波后地面点

然后，对滤波后点云数据使用C++语言，在VS2013环境下编程实现本文提出的道路面提取方法。其中，法向量计算时点云邻域查找方式为KNN，查找点数量参数设置为30；区域生长时邻域搜索参数也设置为30，两组数据曲率阈值Kt均为0.04，数据1法向量夹角阈值Sθ为8°，数据2为5°。最后，两组数据的道路面提取结果如图7、图8所示。

图7 数据1路面提取结果

图8 数据2路面提取结果

准确性p、完整性r和检测质量q是用于评估道路提取精度广泛使用的定量指标[16]。为了对试验结果进行客观分析与评价，笔者通过手工从原始点云中选取出路面点云作为参考数据，并结合试验提取的非路面点计算上述3个评价指标，公式定义如下

p=TP/(TP+FP)

(5)

r=TP/(TP+FN)

(6)

q=TP/(TP+FP+FN)

(7)

式中，TP为试验中正确提取的路面点数量；FP为提取的非路面点数量；FN为未提取的道路点数量。

对试验提取的路面点统计分析结果见表1，两组数据进行道路提取的准确性p、完整性r和检测质量q均在93%以上。其中，两组数据提取的路面在局部边缘处存在少量缺失，是由路面车辆等障碍物的遮挡所致。试验结果表明，本文方法可以在复杂的城市环境下进行结构化道路面的提取，并且受道路宽度及形状的影响不大。

表1 试验结果分析 (%)

3 结 语

本文充分利用结构化道路点云的法向量分布特征，提出了一种基于点云法向量相似度的道路面提取方法。通过对试验提取的道路面点云进行目视评价及定量分析，结果表明该方法适用于城镇环境下的结构化道路面提取。对车辆和行人等遮挡造成的路面局部边缘的缺失进行修补，以及进一步精细化提取道路标线和标志是下一步的主要研究工作。