2D激光雷达扫描数据的异常值检测

刘延彬,姜媛媛

(1.安徽理工大学力学与光电物理学院,安徽 淮南,232001；2.安徽理工大学电气与信息工程学院,安徽 淮南,232001)

1 引 言

2D激光雷达在移动机器人方面具有广泛的应用(包括障碍物检测、同时定位与制图，SLAM等)[1-3]。近年来,随着移动机器人在工业或日常生活中的普及(例如,清洁机器人、仓储物流机器人等),大量的低成本2D激光雷达被应用到移动机器人导航系统。然而,低成本带来的是低精度的测量数据,致使2D激光雷达扫描数据中总会包含一些异常值。异常值会对后续的障碍物检测、SLAM及机器人决策产生影响。激光雷达的测量值由角度和距离数据组成,其对单点测距分为以下情况[3]:

(1)测量正确,测量值具有随机噪声,且受到雷达精度及灵敏度影响；

(2)检测到意外的对象；

(3)测量失败,例如照射到镜面或阳光影响等；

(4)测量到随机值。

其中,情况(1)为正常测量数据,需要滤波处理；情况(2)、(3)、(4)为雷达扫描数据的异常值,需要单独处理。

几十年来,国内外众多研究人员在阵列及3D雷达扫描数据的异常值抑制方面取得了大量的研究成果。Shapiro 等[4]人采用极大似然比迭代算法分析了噪声的概率密度函数,基于数学期望最大算法对距离像进行了估计。Thomas J等[5]采用小窗口中值滤波器抑制距离像中的非线性噪声。Seongjoon 等[6]假设目标表面至少有两个邻近的像素点,且目标表面像素点的距离值是相似的,提出了一种具有高离群值比率的点云异常值区分方法。沈严等[7]基于距离像的统计直方图提出分层滤波算法,对距离像做分层分割、分别滤波及重新整合。李自勤[8]等使用局部直方图判断距离反常像素,研究了距离反常噪声抑制算法。陈晓清[9]等基于排序差分和自适应中值滤波的距离反常抑制算法来处理距离像反常噪声。宋昭等[10]对激光雷达距离像噪声抑制方法进行了研究,提出了一种基于包围准则的自适应中值滤波算法。于加其等[11]提出改进环圈滤波算法对激光阵列雷达距离像距离反常噪声的噪声抑制。

由于2D激光雷达具有特殊性,其扫描方式为单点扫描,扫描数据相对稀疏,上述各种去除异常值算法很难直接应用于2D激光雷达扫描数据的异常值处理。随着SLAM技术的发展,2D激光雷达在机器人行业应用越来越广泛[12-14],Santos等[15]对常用的SLAM算法进行评估,指出激光雷达噪声引起的栅格地图扫描匹配误差导致试验结果差于仿真结果。综上所述,2D激光雷达扫描数据的异常值处理亦成为了不得不面对的问题。本文采用最邻近距离-局部异常因子检测算法对2D激光雷达扫描数据的异常值进行检测,研究结果表明该方法具有较大的实用价值。

2 异常数据检测基本原理

2.1 2D激光雷达扫描数据异常值分析

激光雷达扫描数据的异常值主要由以下情况产生[16]:

1) 雷达发射的激光脉冲没有回波。激光脉冲传播路径上没有物体反射表面(例如空旷场地等),或者物体表面反射的激光回波没有到达雷达,接收机不能接收到激光回波。

2) 回波的强度低于雷达接收机的检测门限。

3) 回波时间超出接收时间窗口。激光雷达只能接收某段距离范围内的激光回波,该时间就是激光雷达接收时间窗口。接收时间窗口与激光雷达测距的最大距离和最小距离相对应。

在以上3种情况中,2D雷达接收机探测不到激光回波,相应的雷达扫描数据形成异常值。如图1所示,点A、B、C及区域S中所包围的点均属于此类异常值。且2D雷达扫描数据的异常值分为两种情况:①孤立异常点,如点A、B、C；②聚集异常点,如区域S所包围的点。本文将采用最邻近距离及局部异常因子分别对两种情况进行检测。

图1 2D激光雷达扫描数据Fig.1 2D lidar scanning data

2.2 最邻近距离

在2D激光雷达工作环境中,物体表面一般为连续变化的,只有极少数物体的表面会存在过深的孔洞等影响扫描结果的因素。此外,本文不考虑雷达只能单次扫描到的微小物体。故做如下假设:

(1)被扫描物体的表面是连续、光滑的,即物体表面不存在过深的孔洞等非光滑因素。

(2)物体空间尺度远大于激光雷达扫描间隔,且对于同一物体,激光雷达至少会扫描到两点。

(3)测量值的相对误差很小。

当满足以上假设时,点Pi到其最近邻近点的距离必然要小于某个确定的阈值。记单线激光雷达扫描数据集的n个点为P={P1P2…Pn}。Pi与点Pj之间的欧式距离记为d(Pi,Pj),本文据此定义最邻近距离及孤立点。即:

对于不同型号的激光雷达、不同的测试环境及不同的被扫描物体,不可能给出统一的γ值,可以采用3δ法则确定γ值。

2.3 局部异常因子

2000年,Breunig 等提出基于局部离群因子(local outlier factor,LOF)的离群点检测方法[17],该方法使用数据点与周围紧邻点的相对密度度量其离群程度。目前,LOF算法被广泛的应用到离群点检测[18-20]。LOF算法中的相关定义为:

K-邻近距离(K-distance):在点Pi的邻近点集中,第K个邻近点跟点Pi之间的距离称为点Pi的K-邻近距离,记为K-distance(Pi)。点Pi的第K距离,就是距离Pi第K远的点到Pi的距离(不包括Pi本身)。

K距离领域(K-distance neighborhood)点Pi的K距离领域是以点Pi为圆心,以K距离为半径的圆内所包含的点集合(包括圆上的点)。Pi的第K距离领域内点的个数至少是K。

可达距离(rechability distance):可达距离的定义跟K-邻近距离是相关的,给定参数k,数据点Pi到数据点Pj的可达距离reach-dist(Pi,Pj)为数据点Pj的K-邻近距离及数据点Pi与点Pj之间的直接距离的最大值。即:

reach_distK(Pi,Pj)=max{K-distance(Pj),d(Pi,Pj)}

(1)

局部可达密度(local reachability density):与点Pi的距离小于等于K-distance(Pi)的数据点集合称为点Pi的K-nearest-neighbor,记为NK(Pi),点Pi的局部可达密度是其与邻近数据点集合平均可达距离的倒数,即:

(2)

局部异常因子(local outlier factor):点Pi的局部异常因子(局部相对密度)是点Pi邻近点的平均局部可达密度与点Pi的局部可达密度的比值,即:

(3)

由局部异常因子定义可知,如果某个数据点相对于其邻近数据点比较疏远,它的局部可达密度就小。LOF算法衡量数据点的异常程度,并不是看它的绝对局部密度,而是看它相对邻近数据点集合的密度。该方法允许数据点分布不均匀、密度不同。

2.4 最邻近距离-局部异常因子检测算法

LOF定义表明:如果数据点Pi的 LOF值在1附近,数据点Pi的局部密度跟其邻域内的其余点差不多；点Pi的 LOF的值小于1,点Pi的局部密度就高于其邻域点密度；点Pi的 LOF值大于1,点Pi密度小于其邻域点密度,很有可能是异常点。2D激光雷达扫描数据为点扫描数据,数据点比较稀疏,大于1的LOF值较多。如果取LOF的阈值为1,则大部分扫描数据点会被判别为异常点,故本文采用3δ准则确定LOF的阈值。基于最邻近距离-局部异常因子的2D激光雷达扫描数据的异常数据点检测步骤如下:

Step 2:计算邻近距离集合D的均值、方差,确定阈值γ.

Step 3:确定2D雷达扫描数据集合的孤立点,并剔除.

Step 4:计算2D雷达扫描数据集合的LOF值集合。

Step 5:计算LOF值集合的均值、方差,确定LOF阈值.

Step 6:确定LOF数据集合的异常值,并剔除.

3 实验验证及结果分析

本文采用MALTAB中SLAM开源数据集验证上述算法。该数据是移动机器人在室内环境中所采集的激光雷达扫描数据集,激光雷达最大有效测距距离8 m,每两次扫描之间的平均位移约为0.6 m,共72组。室内移动机器人的雷达扫描环境及近似轨迹如图1所示。

图2 激光雷达扫描环境及近似轨迹Fig.2 Scanning environment and approximate trajectory of lidar

在LOF值计算中,K-邻近距离的K值(决定邻域的范围)会影响异常数据检测的准确率,此外,随着K值的增加,计算开销也急剧增大,文献[17]推荐K的取值范围是10～20,本文选用K=20。选用2D激光雷达扫描数据集中的第1、5、10及第20组数据验证最邻近距离-局部异常因子异常数据检测算法。最小邻近距离及局部异常因子的计算结果如图3、5、7、9、11所示；2D雷达扫描数据的异常数据检测结果如图4、6、8、10、12所示；误报率及计算时间如表1所示。误报率计算公式为:

图3 第1组扫描数据最邻近距离与局部异常因子Fig.3 The nearest neighbor distance and local anomalyfactor of the 1st scanning data

图4 第1组雷达扫描数据的异常检测结果Fig.4 Abnormal detection results of the 1st scanning data

(4)

在(4)式中,FP为误报率;NFP为误报的数据点数量;N为数据集合中数据点的数量。

图5 第5组雷达扫描数据最邻近距离与局部异常因子Fig.5 The nearest neighbor distance and local anomaly factorof the 5th scanning data

图6 第5组雷达扫描数据的异常检测结果Fig.6 Abnormal detection results of the 5th scanning data

图7 第10组雷达扫描数据最邻近距离与局部异常因子Fig.7 The nearest neighbor distance and local anomalyfactor of the 10th scanning data

图8 第10组雷达扫描数据的异常检测结果Fig.8 Abnormal detection results of the 10th scanning data

图9 第15组雷达扫描数据最邻近距离与局部异常因子Fig.9 The nearest neighbor distance and local anomalyfactor of the 15th scanning data

图10 第15组雷达扫描数据的异常检测结果Fig.10 Abnormal detection results of the 15th scanning data

图11 第20组扫描数据最邻近距与局部异常因子Fig.11 The nearest neighbor distance and localanomaly factor of the 20th scanning data

图12 第20组雷达扫描数据的异常检测结果Fig.12 Abnormal detection results of the 20th scanning data

从图3、5、7、9、11可看出,最邻近距离及局部异常因子的数值均相对集中,只有极少部分异常数据,故可以将最小邻近距离及局部异常因子用于2D激光雷达扫描数据的异常值检测。从图4、6、10、12可以看出,最邻近距离只能检测出部分激光脉冲无回波所产生的随机异常数据,局部异常因子可以检测出剩余随机异常数据,最邻近距离-局部异常因子算法无漏检现象。从图4、6、8、10、12可看出,最邻近距离-局部异常因子算法会将极少的离群正常数据误判为异常数据。表1中表明:最邻近距离-局部异常因子算法平均误报率为1.228 %,最大误报率2.47 %,最小误报率为0.87 %,算法可以满足实际需要,且算法的运行时间较短,平均运行时间为0.842 s。综上所述,最邻近距离-局部异常因子算法能够较好的适用于2D激光雷达扫描数据的异常值处理。

表1 误报率及计算时间Tab.1 False alarm rate and calculation time

4 结 论

本文基于最邻近距离-局部异常因子检测算法对2D激光雷达扫描数据进行检测,并采用5组2D激光雷达扫描的实测数据对算法进行测试。测试结果表明:

1) 最邻近距离-局部异常因子检测算法能够很好的检测出2D激光雷达扫描数据的异常值。

2) 最邻近距离-局部异常因子算法会将极少量的离群正常点误判断为异常点,测试结果表明该算法的误报率很低。

3) 最邻近距离-局部异常因子检测算法计算时间较少,可满足实际需求。