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) 最鄰近距離-局部異常因子檢測算法計算時間較少,可滿足實際需求。