基于改进栅格图的道路和障碍物检测算法研究*

岳元琛 王东生

（南京理工大学计算机科学与工程学院 南京 210094）

1 引言

近年来，传感器和人工智能相关技术高速发展，无人驾驶技术作为人工智能的一个重要应用也成为了热门的研究内容。其中，高精度实时的环境感知是无人车进行有效路径规划和控制的重要前提。多线激光雷达作为一种重要的车载设备，是无人车进行环境感知任务中最重要传感器之一，可以直接得到周围环境的三维点云信息，同时可以很好地适应夜间、雨天等较复杂条件下的行驶任务。因此，多线激光雷达点云数据相关的研究工作具有重要的研究价值和应用前景。

点云数据最常见的处理方法主要分为直接对无序点云的处理［1～3］、体素化处理［4］、多视角图像［5～6］、栅格化［7～12］。栅格化处理是将原始点云数据投影到一个鸟瞰视角下2D栅格图中，简单而高效，在无人驾驶系统中应用广泛。基于高度差的栅格图［9］存在很多问题，无法正确区分悬浮障碍物和正障碍物，同时极易受到噪声点的影响。针对这一问题，本文提出一种改进的栅格图构建方法，通过统计栅格内点云高度分布的方法进行栅格分类，有效区分噪声点、悬浮障碍物点、正障碍点和地面点，同时通过膨胀处理得到紧密相连的占据栅格。

道路检测过程中，通常采用先确定地面点再进行道边点检测。地面点提取过程中使用线段分割的方法进行提取，线段分割方法主要有PDBS［13］、SEF［14］、LT［15］和IEPF［16］等。这些方法直接对原始点云进行处理，阈值控制比较困难，并且计算量较大难以满足实时性需求。针对这些问题，本文采用直接从栅格图中搜索候选道边的方法，使用自适应半圆弧搜索进行道边候选点的搜索，同时采用改进RANSAC算法进行道边拟合，得到最终的道路检测结果。算法简单高效，提高了检测精度并满足实时性需求。

2 基于改进栅格图的障碍物检测

2.1 点云数据栅格化

原始点云数据具有海量性、稀疏性、无序性等特点，在实际使用的过程中会存在很多困难。常见的Velodyne32线激光雷达每一帧数据量可以达到50K，在处理和数据传输的过程中有很大的时间和内存开销；点云数据具有稀疏性，不同于图像中紧密连接的像素点，点云数据散落在三维空间中，并没有固定的分布区域并且密度也不相同；点云数据具有无序性，一般的图像都可以表示为一个C×W×H的3维矩阵，但是点云数据无法直接使用一个结构化矩阵来表示。

栅格法是一种针对点云数据进行障碍物检测的一种应用广泛的算法，它可以将3D空间内散乱分布的点云数据结构化到一个鸟瞰视角下的2D栅格地图。该方法主要问题是栅格化处理会损失一定的空间信息，同时栅格大小的选择也将对实验精度产生较大的影响，因此需要设置恰当的统计量来有效描述栅格内点云的空间信息，同时应设置恰当的栅格大小。

本文改进了经典的基于高程差的栅格图［8～9］，使用了一种新颖的栅格化处理方法。如图1所示，首先设置一个大小为W×H的栅格地图，栅格大小为g×g，将该栅格图看作一个二维空间内的哈希表，Δy代表坐标偏移量，点云坐标(x,y)与栅格坐标(w,h)的映射关系满足哈希函数：

图1 点云栅格化过程示意图

映射过程中，栅格图范围外的点将去除掉不用于检测任务中。设置每个栅格内最少点个数阈值Tmin，当栅格内点的个数Ng，Ng＜Tmin时认为栅格是一个未被占据的栅格，设置最小点阈值可以有效避免一些空间内孤立的噪声点对实验结果的影响，Ng≥Tmin认为是一个占据的栅格。由于三维空间内点云分布不均匀，同时栅格内所有的点是无序的，不需要进行随机读取，因此使用链表来记录同一个栅格内点的信息，这样可以极大提高存储效率。

2.2 基于点云高度分布的栅格分类

经典的基于高程差的栅格化处理方法存在很多的问题，只统计栅格内点的最大高度和最小高度，会忽略很多空间分布信息，无法实现栅格的有效分类；少量具有较大高度的噪声点会影响高程差的统计，造成栅格的误标记，因而鲁棒性不够高；无法有效区分悬浮障碍物和普通正障碍物，基于高程差的栅格图会将悬浮障碍物当作普通障碍物，在一些城市道路的场景中，伸入路面的树枝等悬浮物会被误检为障碍物导致道路可通行区域被封死，影响无人车的行驶。

针对这些问题，本文提出一种统计栅格内点云高度分布的方法进行栅格分类。常见的栅格类型可以分为正障碍栅格、悬浮障碍栅格、地面栅格、噪声栅格等。去除噪声栅格，并将栅格图中每一个障碍物的“占据”栅格标记为对应类别，非障碍物的“占据”栅格标记为地面。

栅格内点云的高度分布满足一定的分布规律。将点云根据高度信息进行聚类后，噪声点簇满足点簇中点的个数少；地面点簇满足点簇内高程差很小并且高度均值小于一定阈值；悬浮障碍点簇满足点数大于一定阈值，并且最低高度要高于安全高度阈值；正障碍点簇满足点的个数大一定的阈值，并且高程差也大于一定的阈值。

根据高度分布的规律，考虑可能的两种解决方法，K-means算法和双指针法。K-means算法是一种经典的聚类算法，应用在此场景下可以有效实现指定数量点云簇的聚类，进而将悬浮点、正障碍点、地面点等区分开，但是由于栅格类型的多样性，每个栅格内的点的数量以及高度分布情况不同，很难选择适合的K值，同时在计算过程中需要进行多次迭代过程，将产生较大的时间开销；双指针法实现原理简单，时间开销较小，不需要设置K值，可以很好适应此场景下多种类型栅格的点云分布情况，同时也可以很好应对不同栅格内点云数量差距太大的情况。

本文使用双指针法进行处理，有效地将悬浮障碍点、地面点、正障碍点区分，并去除噪声点。图2所示在不同栅格类型的条件下运用双指针法的结果，算法执行流程如下：

图2 栅格内点云高度分布规律

1）输入栅格内的按照高度排序后的点云集P，初始化高指针ptr1为点云最大高度，低指针ptr2为点云最小高度，并设置聚类阈值T1，最小间隔阈值T2，点簇最少点个数阈值N1，间隔内最大点个数N2，障碍物高程差阈值Th。

2）高指针ptr1与相邻点高度差小于T1时，指针下移；低指针ptr2与相邻点高度差小于T1时，指针上移。直到满足终止条件，ptr1与ptr2相遇时或者两个指针与相邻的点高度差大于T1，无法继续移动。其中一个点簇中点的个数小于N1，如图2（a）所示，则将这个点簇视作噪声点簇，去除该点簇内的点，重新执行2）。

3）双指针终止移动后，可能的结果如图2所示，根据高低指针的位置，各种情况处理方法如下：

（1）如图2（b）所示，终止条件下ptr1与ptr2之间点个数小于N2，ptr1超过了安全高度，且ptr2对应点簇高程差Δh小于Th，此时标记栅格为悬浮障碍栅格。

（2）如图2（c）所示，终止条件下ptr1与ptr2之间点个数小于N2，ptr1超过了安全高度，且ptr2对应点簇高程差Δh大于Th，此时标记栅格为正障碍栅格。

（3）如图2（d）所示，终止条件下，ptr1与ptr2中间点个数大于N2，且中间的点在安全高度之下，合并中间的点簇和ptr2对应点簇，计算对应的高程差Δh，并标记栅格为正障碍栅格。

（4）如图2（e）所示，如果ptr1与ptr2相遇，则栅格内的点视作一个整体，高程差Δh大于Th标记栅格为正障碍栅格，如图2（f）所示，高程差Δh小于Th标记为地面栅格。

4）重复1）～3）的过程，直到所有的栅格都被成功标记结束算法流程。

得到的原始栅格图存在一定的孤立性，由于多线激光雷达本身具有一定稀疏性，并且检测出来的障碍物栅格也会存在一定漏检或者断裂的情况，很多的栅格可能没有成为一个连贯的整体，这将不利于后续的处理过程。此时，考虑对栅格进行膨胀处理，选用四近邻膨胀模板。注意不可重复膨胀。在膨胀过程中，出于安全性的考虑，设置优先级依次为正障碍栅格、悬浮障碍栅格、地面栅格，在膨胀过程中，首先将所有的正障碍栅格进行膨胀，膨胀过程中如果高优先级栅格近邻存在低优先级的栅格，即膨胀过程中近邻遇到悬浮障碍栅格和地面栅格，将使用正障碍栅格替换对应栅格。紧接着分别膨胀悬浮障碍栅格和地面栅格，得到最终的栅格图。

3 基于改进栅格图的道路检测

3.1 候选道边点搜索

道路边界点提取主要可以分为两大类方法：使用雷达扫描线上的点进行线段分割，进而区分路面点和候选道路边界点；直接从栅格图中搜索出候选道边点。

本文采用一种新颖的自适应半圆弧搜索法，可以直接运用之前得到的改进栅格图来搜索候选道标，不用保留多余的雷达扫描线信息。如图3所示，算法流程如下：

图3 自适应半圆弧搜索过程

1）以栅格图底部中心位置（对应车体坐标系的原点）为圆心起点，作半径为r的半圆弧，其中左搜索使用左半圆弧，右搜索使用右半圆弧。

2）右搜索过程中，从90°～-90°间隔为Δθ依次进行检验圆弧所在栅格的占据情况，如果所在栅格为正障碍栅格，则记录下圆心位置并将此栅格作为右道边候选栅格，结束本次行搜索过程；如果直到-90°位置仍没有搜索到正障碍栅格，那么将圆心向右平移Δw的距离再重新进行搜索；如果一直到栅格图边界仍没有搜索到，认为本次行搜索没有发现候选道边点，圆心点重置为起始点，并结束本次行搜索过程。

3）行搜索结束后，根据上一次搜索的圆心位置，向上平移Δh的距离，并结合右道边点的横向变化趋势做一次横向偏移，进而确定新的圆心起始位置，再次执行2）中的行搜索过程。

4）重复执行2）、3）直到搜索点到搜索起始点的纵向距离超过阈值H，停止搜索过程，此时得到了完整的右候选道边点。

5）重复执行以上过程，确定左候选道边的点。

3.2 基于最小二乘法的直线拟合

最小二乘法是一种经典的数学拟合算法，可以通过最小化误差的平方和来得到数据的最佳函数匹配。在进行道路边界拟合的过程中，期望的目标函数是一条直线，这里选择使用左右候选道边点进行左右道边拟合。

设右候选道边点集为PR，左候选道边点集为PL，其中点的坐标为车体坐标系下的坐标。分别进行左右道边的拟合，期望的直线方程为

根据左（右）候选道边点的坐标和期望直线方程，可以得到矩阵形式的超定方程组：

推导的最小二乘解公式，得到方程组的最小二乘解为

在实际算法执行过程中，以左（右）候选道边点作为输入，分别带入到上述矩阵方程中，得到左（右）道边模型的各个参数值。同时注意到，为了满足超定方程组的前置条件，用于拟合的候选道边点个数应该大于3，点的个数过少将停止拟合过程。

3.3 基于改进RANSAC算法的道边拟合

RANSAC即随机抽样一致性算法，是一种能够从一组包含一定量异常样本的样本集中计算出数学模型参数的方法，可以有效解决异常数据对模型的影响。RANSAC算法假设数据集中既有正确的样本集，称作内点集，也有异常的样本的样本集，称作外点集。内点集中的样本数据与拟合模型偏差较小，可以被模型有效描述；外点集中的样本数据与拟合模型偏差较大。同时RANSAC算法还假设，给定一组正确的数据，存在一种模型构建方法可以有效描述这组数据。基本的RANSAC算法流程为

1）输入一个样本集P，并定义最小抽样集S，S中样本的数目m为模型参数计算所需的最小样本数，样本集P中的样本数应该大于m。设置算法迭代次数K以及误差阈值δ。

2）从样本集P中随机抽取m个样本构成最小抽样集S，并使用S中的样本进行模型参数计算，得到拟合模型M。

3）计算样本集中其他的数据与拟合模型M之间的误差，当样本的误差小于阈值δ的时候，将该样本加入到S中构成新的内点集S*。

4）迭代执行2）、3）过程K次，选择样本数最多的内点集S*所对应的模型M作为最优的模型，并根据内点集S*重新计算模型，得到最终的拟合模型M*。

在道边拟合的使用场景下考虑使用直线模型来描述候选道边点，执行过程如图4所示，图中展示了两次迭代过程的内点和外点分布情况。在迭代过程结束，得到最优拟合结果之后，使用最小二乘法重新计算模型参数，得到最终的模型。

图4 RANSAC算法道边拟合过程

实际运用过程中，通常设定固定大小的m，此时在保持置信概率p一定的情况下，可以适当提高内点率w来降低迭代次数K；通过增加迭代次数K来提高置信概率p。

在道边拟合的使用场景下，对RANSAC算法进行三种优化：

1）在得到最终的拟合模型M*之后，重新计算内点集并进行模型拟合，迭代执行该过程直到达到指定的迭代次数N或者没有新的样本加入内点集的时候停止迭代过程。

2）可以预设内点率阈值w，当一次迭代过程中内点率达到了预设阈值则提前结束迭代过程。

3）在抽取最小抽样集S的过程中，结合一定的先验信息来确定实际的抽取方案，代替完全随机的选择，提高算法效率。实际的道路边界点通常是高度较为一致的点，在执行算法流程之前可以预先将候选道边点按高度进行归类，抽取的过程中优先抽取高度较为一致的道边点作为最小抽样集。

4 实验结果与分析

4.1 主要参数设定

实验过程中选用Velodyne 32线激光雷达在校园内进行实验验证，根据该雷达的属性和实际功能需求，按照表1设定参数。

表1 主要参数设定

4.2 实验结果展示与分析

图5（a）中，无人车直线行驶过程中，伸入路面的树枝被成功检测为悬浮障碍，同时道边检测正常，不会影响车辆的正常行驶。图5（b）中，在行驶过程中道路右侧遇到了一辆车，成功将其检测为正障碍，同时也成功检测出了悬浮障碍物。图5（c）中，道路左侧存在一定的噪声点，成功将噪声滤除，没有影响道边拟合的结果。图5（d）中，在岔路口转弯的过程中，也能够拟合出道边。

图5 校园道路典型场景中障碍物和道路检测结果

实验过程中，总共采集了2000帧的数据，算法运行时间如图6所示，平均算法运行时间为25.3ms，达到了无人驾驶场景下实时性的需求。在实验过程中，在所有的场景下成功检测出来了全部正障碍物并成功消除了噪声点的影响，同时在99.5%的场景下成功检测出了全部悬浮障碍，证明了本算法实现了改进栅格的鲁棒性需求。

图6 算法运行时间分析

在道边拟合过程中，在直线行驶且道边清晰的场景下都可以正确检测出道边，但是在交叉路口以及道边不明显的道路中检测效果不佳。

5 结语

本文针对无人驾驶中多线激光雷达障碍物和道路检测过程中遇到的一些问题，提出的基于改进栅格图的障碍物和道路检测算法。运用基于点云高度分布的栅格分类方法，有效解决了经典的基于高程差的栅格图无法避免噪声点影响以及无法有效区分正障碍物和悬浮障碍物的缺陷，建立了更加鲁棒的栅格图。同时针对道边检测过程中，精度和实时性不足的问题，提出了直接在栅格图内进行候选道边点搜索并运用改进RANSAC算法进行道边拟合的方法，有效提高了道边检测的精度和效率。最终在实验结果中，证明了算法的有效性。在未来的研究过程中，将考虑进一步提高算法的性能，并考虑实现对行人、车辆等目标实现识别。