一种激光雷达可通行区域提取算法

袁夏，赵春霞

(南京理工大学 计算机学院，江苏 南京210094)

0 引言

地面自主移动机器人［1］是一种能够连续自主运动的车辆，其发展对国防、社会经济和科学技术具有重大的影响，已成为各国高科技领域的战略性研究目标。自主导航是地面自主移动机器人的一个基本功能，室外自主导航目前依然是一个极具挑战性的课题。可通行区域检测主要针对局部环境，是环境理解的重要研究内容之一。可通行区域信息结合车辆自身固有的性能参数，可以保护机器人安全移动，防止侧翻、碰撞等危险状况发生［2］。

激光雷达不受纹理和光照的影响，可以检测道路边界的跳变，因此比较适合在较复杂的环境中检测和跟踪可通行区域［3］，使用基于几何结构特征的方法，激光雷达可以采样到路边的几何结构并用于检测和跟踪路边信息［4-7］，而直接对可通行区域进行检测［8］可以进一步提高检测的稳定性。这些方法主要是针对单条激光雷达扫描线数据的。单独分析1 条扫描线数据虽然可以获得路边、障碍等信息，但是由于这种分析方法忽略了环境固有的时空关联特性，因而损失了很多原始采样数据包含的信息，使算法的准确性受到影响。本文的研究主要针对如何在分析单条扫描线的基础上，结合扫描线间的时空关联特性进一步优化可通行区域提取结果。

本文提出可通行区域提取算法主要包含单条激光扫描线数据聚类、初始可通行区域提取、时空关联分析3 个主要过程。利用相邻扫描线间的时间和空间关联性，可以得到比分析单条扫面线更准确的可通行区域提取结果。

1 数据聚类

算法首先使用基于最大熵的模糊预测模型将单条扫描线数据点聚类。这里单条扫描线指单线激光雷达的1 帧数据或者多线激光雷达1 个发射单元旋转1 周得到的数据。假设算法预测误差阈值为δ，某点的测量位置是(xi，yi，zi)，利用模糊模型计算的预测位置为，预测误差定义为

如果ei＞δ，则认为该采样点是下一段数据的开始，上一段数据的结束。

大部分激光雷达是等角度间隔采样的，由于目标距离是变化的，以及被采样表面法线方向和激光发射夹角的不同，这个采样过程其实是一种不均匀采样，因此δ 不能设为常量，其取值与当前采样点到目标的距离和激光雷达水平采样精度有关，用下式计算δ

式中:参数a 为与激光雷达噪声有关的缩放因子;θ为单个发射单元水平扫描精度的1/2，x 和y 为一个采样点在直角坐标系中的坐标;i 为当前点在一条扫描线中的序号。

假设一个发射单元的一条扫描线数据有N 个点，这N 个点可以用N 维空间的k 个聚类中心描述:C1，C2，…，Ck，每一个聚类中心Ci由m 个测量点构成的向量表示。取实际测量的前p 个向量作为模糊规则的输入，后m-p 个向量作为规则的输出，即可构成一组模糊规则中心。为了减少误差积累的影响，算法中把预测误差也加入模糊规则，和测量值同时参与预测，然后在新的预测值中减掉积累误差

聚类过程可以看作一个最优化问题，构造代价函数如式(3)，μi为隶属度，X 为模糊规则的输入，Xi为第i 个待预测的数据的采样值。式(3)的计算方法请参考文献［8］.

这种聚类算法的优点是可以跟踪数据点的发展趋势，将发展趋势一致的点聚类成为一个数据点段，分段结果保留了较多的原有特征，而非常散乱的区域将被分的较零散，不会参与特征提取，同时该方法不涉及迭代和学习过程，随着数据的增加计算量基本呈线性增长。

2 直线特征分析

城市环境中的可通行区域主要指道路区域，这些区域一般是经过修筑的，相对而言比较平坦。在一条扫描线数据中，这种平坦的路面区域表现为一段呈直线分布的点集。算法先把聚类后一条扫描线上呈直线分布的数据段提取出来，然后在直线分布数据段中根据设定的路面特征搜索初始可通行路面。为了加快计算速度，直线特征分析在二维空间进行，将三维空间点分别投影到如图1所示的XOY、XOZ 和YOZ 平面搜索直线。

一般情况下，通过设定点集中各点到拟合直线距离的均值μ 与方差σ 的阈值，可以提取直线分段。但是由于城市环境复杂多变，激光雷达在不同距离的采样点分布特性也不同，因此μ 与σ 的阈值很难选取。

鉴于此，本文采用多次加权最小二乘拟合算法寻找呈直线分布的点集，共进行三次直线拟合。第一次直线拟合，把一条扫描线上数据分段后得到的各段数据点直接做最小二乘直线拟合，得到初始拟合直线L1.

图1 加权直线拟合权重计算原理Fig.1 Theory of weight least squire linear fitting

第二次直线拟合在第一次初拟合的基础上做加权直线拟合。设直线方程为

则其一元线性回归的加权最小二乘离差平方和为

可以证明［9］(β0，β1)的加权最小二乘估计为

算法用以下方法计算某点的权重，假设某一分段第一次拟合得到直线L1，段内两相邻点为Pi和Pi+1，则Pi的权重等于在L1上的投影(如图1)。对于一帧内的点我们还将进行权重的归一化，某点的归一化权重为

其中，direction(L1)为第一次拟合直线L1的方向，长度为1.计算出一段内各点的权重后，做加权直线拟合，得到L2.

第三次直线拟合，在第二次加权拟合直线L2的基础上，再次计算该点段内各点与其近邻点连线在L2上投影得到的权重，取权重最大的80%的点，再做加权直线拟合，得到L3.

这种加权最小二乘直线拟合算法考虑了各点与其下一个近邻点的连线与拟合直线方向之间的关系。连线与拟合方向一致性越高，则direction(L)的值越大，那么该点的权重越高，表明该点符合该段数据主要发展方向的程度高，拟合得到的直线更能代表数据的主要分布方向。

实验表明，越是符合直线分布的分段，L1和L3的方向越接近。而一些程不规则分布，或者拐角分布的分段，L1与L3方向夹角相对较大。根据这个原理，我们设定一个阈值θline，把第一次和第三次拟合直线的夹角小于θline的点段作为符合直线分布的直线特征分段，而其余点段作为非直线分布区域。

3 可通行区域提取

3.1 初始可通行区域提取

用上一节的方法得到的呈直线分布的点段显然包含大量的非路面区域，例如比较规则物体表面的采样点也呈直线分布。算法通过设定一系列的可通行区域约束条件首先在单条扫描线提取初始的可通行区域。用如下结构来描述根据一个聚类分段拟合的直线段:

假设借助惯导系统获得了机器人(等同于激光雷达)的航向角、方位角与姿态角，那么首先用式(8)进行坐标转换，将点云变换到机器人呈水平位置的一个临时坐标系OR中。

图2 机器人坐标系Fig.2 The robot coordinate system

为了提高系统的效率，在对一条扫描线数据聚类分段后，取包含采样点个数n 满足n ＞D 的分段才是有效分段，D 为有效分段需要包含的最少点的个数，一般根据激光雷达设定的角分辨率选取合适的值。这样做的主要目的是删除一些散乱点所在的分段，例如位于灌木丛的采样点，其每一个分段可能只包含一两个点，这些分段对于路面提取是没有意义的，在聚类后直接删除。

结合可通行区域的特点，设定如下可通行区域约束条件来判断某拟合线段Li是否属于可通行区域:

1)处于平坦区域的激光采样点拟合的线段Li应该具有一定的长度，设它的长度至少为q，则q 的取值必须满足宽度大于机器人的可通行宽度W，即

2)在OR坐标系中分析时，可通行区域相对于机器人的斜率应该小于能使机器人发生侧滑的地面斜率，即Li的斜率应该满足式(10)，式中Δk 为允许的最大倾斜程度。为了提高计算效率，算法不在三维空间中做直线拟合以及斜率判断，而是把采样点投影到XOZ 或者YOZ 平面再进行分析。)

3)在一个局部的范围内，可通行区域具有一定的连续性，因此其高度变化也应该在一定范围内，设当前机器人所处位置高度为H，由于地面起伏造成的局部高度差极值为ΔH，则激光雷达采样到的前方可通行区域高度应满足

以上可通行区域特征是针对单条激光雷达扫描线数据的，根据这些特征在一条扫描线数据中提取的可通行区域将作为初始值，再根据时空关联模型进一步优化。

3.2 时空关联分析

由于激光雷达的分辨率不高，在复杂的环境中，不同分段之间提取的特征可能出现相似度很高的情况，因此单条雷达扫描线中提取的符合可通行区域条件的数据段中可能会包含不可通行区域，独立分析一条扫描线时这种错误是很难避免的。机器人在移动过程中激光雷达连续捕获采样数据，这些数据在时间和空间上是有关联的，引入数据之间的时空关联特性有利于提取得更准确的可通行区域。假设Yi是某条扫描线某个分段的真实属性，Xi是观测值，即根据激光雷达数据提取的特征，那么可以用一个无向图来描述不同扫描线分段之间的时空关联，如图3为一个链状时空关联模型［10］。图中i -1，i 和i+1 既可以代表相邻时刻，也可以代表空间近邻关系。

图3 链状时空关联模型Fig.3 A chain model of space-time association

如果用一个概率模型来描述这种时空关联，那么某个分段属于可通行区域的条件概率可以描述为

式中，sk(yi，x，i)为可通行区域特征函数，k 为选取的可通行区域特征个数，tj(yi-1，yi，x，i)为可通行区域状态转移特征函数，代表时空关联性，j 为选取的可通行区域状态转移特征个数，Z(x)是一个归一化因子，μ 和λj是特征函数权重。sk(yi，x，i)和tj(yi-1，yi，x，i)可以取为二值函数，即:

可通行区域状态转移特征函数tj(yi-1，yi，x，i)中，yi-1既可以代表时间关联，也可以代表空间关联，即某条扫描线数据既与前一时刻的数据有关，也与当前时刻其近邻扫描线数据有关。从时间关联上分析，激光雷达每一时刻采样得到一条扫描线，可通行区域相邻时刻采样数据的高度分布应该具有一定的连续性，因此计算相邻时刻的前方地面高度差可以判断后一时刻的数据是否仍然可通行，如图4所示。

图4 t-1 和t 时刻地面高度差计算原理Fig.4 Theory of computing the difference of height between time t-1 and t

假设激光雷达扫描角度间隔为1°，激光雷达与机器人水平面的安装夹角为α，t -1 时刻机器人本体的俯仰角为βt-1，航向角为γt-1;t 时刻的本体俯仰角为βt，航向角为γt，激光雷达水平第m 条激光束的采样点极坐标为(ρm，θm)，那么第t -1 时刻激光雷达的第m 条水平扫描激光束和t 时刻激光激光的第［m +(γt-γt-1)］条水平扫描激光束探测到的地面高度差为

当Δh 大于给定阈值T 时，考察t +1 帧激光数据的第m 条扫描线与第t 帧激光数据的第［m +(γt-γt-1)］条扫描线探测到的地面高度差，如果仍然大于T，即认为前方m(°)方向不满足时间关联可通行条件。

多线激光雷达可以同时采样得到多条扫描线数据，可以从空间相邻的初始可通行区域分段中根据空间关联进一步分析可通行性。首先，高度差计算原理显然也适用于空间关联中，将分析t-1 时刻和t 时刻地面高度差变为分析相邻扫描线之间的高度差即可。其次，如图5，如果将多条扫描线映射到OR坐标系的XOY 平面上，那么属于可通行区域的条拟合直线段Li一般是不重合的，并且相邻的属于同一块可通行区域的分段是近似平行的。设某条扫描线的某个分段在其近邻的n 条扫描线中有m 个近邻分段，其中与其满足近似平行的有m1条，则m和m1应满足

图5 可通行区域空间关联示意图Fig.5 Space association of traversable area

式中:m0和m10为2 个阈值。

4 实验结果及分析

实验使用的激光雷达有SICK LMS291 和DHL64，前者为单线激光雷达，有效探测距离80 m，角分辨率设定为1°，后者为64 线激光雷达，有效探测距离为120 m，垂直视角为26.8°，发射体旋转速度设定为10 Hz，即每秒获得10 帧水平360°扫描数据。

图6为对机器人运动进行航迹推算后，将115帧单线激光雷达数据拼接形成前方一个区域的数据以后进行可通行区域提取的结果。图6(b)是对每帧数据聚类时得到的预测误差。图6(c)显示了对连续115 帧数据的可通行区域提取结果，中灰色区域为可通行区域，本文方法在每条扫描线中能够比较准确地找到可通行区域的右边界，即成功区分了高度相似，但是地形不同的区域，从图6(b)也可以看到，植被部分的预测误差明显大于可通行区域。图6(c)中基于单条扫描线分析提取的可通行区域包含下陷的井盖区域，这是由于该部分区域表面特性和可通行路面一致，且高度和路面相差不大，而式(11)中设定的ΔH 一般相对较大，难以分辨这种高度差。在图6(c)提取结果的基础上，加入时间关联分析，对前后帧数据进行路面相对高度差分析后，得到了图6(d)所示的结果。可以看到优化后的可通行区域成功的把井盖部分删除了，利用本文算法通过对前后帧数据的关联分析，得到了比单独分析一条扫描线更准确的结果。

图6 单线激光雷达实验结果Fig.6 Experiment result of range finder

图7(a)和图7(b)是HDL-64E 分别在2 个丁字路口采集的2 帧数据的俯视图，其中图7(a)的路口相对图7(b)更加开阔，而图7(b)附近还有小路口，地面环境比7(a)复杂。从图7(c)和7(d)看，由于环境复杂度比图7高，因此根据单条扫描线提取的初始可通行区域除了包含真正的可通行区域外，还包含路边上的人行道等其它和可通行区域结构类似的区域。图7(e)和图7(f)是时空关联分析后得到的可通行区域结果，大部分人行道已经被滤除，激光雷达周围半径20 m 以内的提取结果更加准确，距离越远提取结果准确度开始下降，这有很大原因是激光雷达在40 m 以外的采样精度比较低，测量误差也开始增加，对算法的判断产生一定的影响。表1反应了分析单条扫描线得到的初始可通行分段数量与时空关联分析后得到的可通行分段数量间的对比，可以看到加入对多条扫描线的关联分析后，有效滤除了一些单条扫描线分析中得到的错误区域，提高了可通行区域提取结果的准确性。

图7 64 线激光雷达实验结果Fig.7 Experiment result of HDL64E

表1 单条扫描线分析与时空关联分析后的可通行分段数量对比Tab.1 Comparing of number of traversable segments extracted by single scan analyze and time-space associating analyze

图(6)和图(7)的实验表明，无论是分析单线激光雷达数据还是64 线激光雷达数据，加入时空关联分析后都得到了比分析单条扫描线更准确的可通行区域。

5 结论

本文结合模糊模型和时空关联分析，出了一种在激光雷达获得的数据中提取可通行区域的方法。该方法利用基于最大熵的模糊预测模型将单条扫描线数据聚类分段，然后从各条扫描线中提取初始可通行区域，最后结合多条扫描线数据之间的时间和空间关联特性，进一步优化可通行区域提取结果，提高了可通行区域提取的准确性。计算过程中通过不同方向三维到二维的映射避免了三维空间中计算量大的缺陷，同时又较好的使用了三维数据包含的信息，不涉及迭代计算和在线机器学习过程。

实验表明在分析单条扫描线数据的基础上，加入时空关联分析有助于提高可通行区域提取的准确性，算法在城市环境中获得了较好的结果。下一步研究工作将关注如何分析颠簸路面的路面特征，增强算法对越野环境的适应性。

References)

［1］Meyrowitz A L，Blidberg D R，Michelson R C.Autonomous vehicles［J］.Proceedings of IEEE，1996，84(8):1147 -1164.

［2］Helmick D，Angelova A，Livianu M，et al.Terrain adaptive navigation for mars rovers［C］∥IEEE Aerospace Conference.Big Sky，2007:1 -11.

［3］Cremean L B，Murray R M.Model-based estimation of off-highway road geometry using single-axis ladar and inertial sensing［C］∥Proceedings of IEEE International Conference on Robotics and Automation.Orlando，2006:1661 -1666.

［4］Hong T，Chang T，Rasmussen C，et al.Road detection and tracking for autonomous mobile robots［C］∥Proceedings of SPIE Aerosense Conference.Orlando，2002:311 -319.

［5］Wijesoma W S，Kodagoda K R S，Balasuriya A P.Road boundary detection and tracking using ladar sensing［J］.IEEE Transactions on Robotics and Automation，2004，20(3):456 -464.

［6］陈得宝，赵春霞，张浩峰，等.基于2 维激光测距仪的快速路边检测［J］.中国图象图形学，2007，12(9):1604 -1609.CHEN De-bao，ZHAO Chun-xia，ZHANG Hao-feng，et al.Quick road-boundary detection based on 2D laser rangerfinder［J］.Journal of Image and Graphics，2007，12(9):1604 -1609.(in Chinese)

［7］Peterson K，Ziglar J，Rybski P.Fast feature detection and stochastic parameter estimation of road shape using multiple LIDAR［C］∥IEEE/RSJ 2008 International Conference on Intelligent Robots and Systems.Nice，2008:612 -619.

［8］袁夏，赵春霞，陈得宝，等.一种基于激光雷达的路面提取算法［J］.中国图象图形学报，2009，14(10):2035 -2041.YUAN Xia，ZHAO Chun-xia，CHEN De-bao，et al.Road-surface dectction based on lidar sensing［J］.Journal of Image and Graphics，2009，14(10):2035 -2041.(in Chinese)

［9］何晓群，刘文卿.应用回归分析［M］.北京:中国人民大学出版社，2001.HE Xiao-qun，LIU Wen-qing.Application regression analysis［M］.Beijing:China Renmin University Press，2001.(in Chinese)

［10］Lafferty J，McCallum A，Pereira F.Conditional random fields:probabilistic models for segmenting and labeling sequence data［C］∥Proceedings of the 18th International Conference on Machine Learning，Morgan Kaufmann.Williamstown，2001:282 -289.