2D激光雷達(dá)掃描數(shù)據(jù)的異常值檢測

劉延彬,姜媛媛

(1.安徽理工大學(xué)力學(xué)與光電物理學(xué)院,安徽 淮南,232001；2.安徽理工大學(xué)電氣與信息工程學(xué)院,安徽 淮南,232001)

1 引 言

2D激光雷達(dá)在移動機(jī)器人方面具有廣泛的應(yīng)用(包括障礙物檢測、同時(shí)定位與制圖，SLAM等)[1-3]。近年來,隨著移動機(jī)器人在工業(yè)或日常生活中的普及(例如,清潔機(jī)器人、倉儲物流機(jī)器人等),大量的低成本2D激光雷達(dá)被應(yīng)用到移動機(jī)器人導(dǎo)航系統(tǒng)。然而,低成本帶來的是低精度的測量數(shù)據(jù),致使2D激光雷達(dá)掃描數(shù)據(jù)中總會包含一些異常值。異常值會對后續(xù)的障礙物檢測、SLAM及機(jī)器人決策產(chǎn)生影響。激光雷達(dá)的測量值由角度和距離數(shù)據(jù)組成,其對單點(diǎn)測距分為以下情況[3]:

(1)測量正確,測量值具有隨機(jī)噪聲,且受到雷達(dá)精度及靈敏度影響；

(2)檢測到意外的對象；

(3)測量失敗,例如照射到鏡面或陽光影響等；

(4)測量到隨機(jī)值。

其中,情況(1)為正常測量數(shù)據(jù),需要濾波處理；情況(2)、(3)、(4)為雷達(dá)掃描數(shù)據(jù)的異常值,需要單獨(dú)處理。

幾十年來,國內(nèi)外眾多研究人員在陣列及3D雷達(dá)掃描數(shù)據(jù)的異常值抑制方面取得了大量的研究成果。Shapiro 等[4]人采用極大似然比迭代算法分析了噪聲的概率密度函數(shù),基于數(shù)學(xué)期望最大算法對距離像進(jìn)行了估計(jì)。Thomas J等[5]采用小窗口中值濾波器抑制距離像中的非線性噪聲。Seongjoon 等[6]假設(shè)目標(biāo)表面至少有兩個(gè)鄰近的像素點(diǎn),且目標(biāo)表面像素點(diǎn)的距離值是相似的,提出了一種具有高離群值比率的點(diǎn)云異常值區(qū)分方法。沈嚴(yán)等[7]基于距離像的統(tǒng)計(jì)直方圖提出分層濾波算法,對距離像做分層分割、分別濾波及重新整合。李自勤[8]等使用局部直方圖判斷距離反常像素,研究了距離反常噪聲抑制算法。陳曉清[9]等基于排序差分和自適應(yīng)中值濾波的距離反常抑制算法來處理距離像反常噪聲。宋昭等[10]對激光雷達(dá)距離像噪聲抑制方法進(jìn)行了研究,提出了一種基于包圍準(zhǔn)則的自適應(yīng)中值濾波算法。于加其等[11]提出改進(jìn)環(huán)圈濾波算法對激光陣列雷達(dá)距離像距離反常噪聲的噪聲抑制。

由于2D激光雷達(dá)具有特殊性,其掃描方式為單點(diǎn)掃描,掃描數(shù)據(jù)相對稀疏,上述各種去除異常值算法很難直接應(yīng)用于2D激光雷達(dá)掃描數(shù)據(jù)的異常值處理。隨著SLAM技術(shù)的發(fā)展,2D激光雷達(dá)在機(jī)器人行業(yè)應(yīng)用越來越廣泛[12-14],Santos等[15]對常用的SLAM算法進(jìn)行評估,指出激光雷達(dá)噪聲引起的柵格地圖掃描匹配誤差導(dǎo)致試驗(yàn)結(jié)果差于仿真結(jié)果。綜上所述,2D激光雷達(dá)掃描數(shù)據(jù)的異常值處理亦成為了不得不面對的問題。本文采用最鄰近距離-局部異常因子檢測算法對2D激光雷達(dá)掃描數(shù)據(jù)的異常值進(jìn)行檢測,研究結(jié)果表明該方法具有較大的實(shí)用價(jià)值。

2 異常數(shù)據(jù)檢測基本原理

2.1 2D激光雷達(dá)掃描數(shù)據(jù)異常值分析

激光雷達(dá)掃描數(shù)據(jù)的異常值主要由以下情況產(chǎn)生[16]:

1) 雷達(dá)發(fā)射的激光脈沖沒有回波。激光脈沖傳播路徑上沒有物體反射表面(例如空曠場地等),或者物體表面反射的激光回波沒有到達(dá)雷達(dá),接收機(jī)不能接收到激光回波。

2) 回波的強(qiáng)度低于雷達(dá)接收機(jī)的檢測門限。

3) 回波時(shí)間超出接收時(shí)間窗口。激光雷達(dá)只能接收某段距離范圍內(nèi)的激光回波,該時(shí)間就是激光雷達(dá)接收時(shí)間窗口。接收時(shí)間窗口與激光雷達(dá)測距的最大距離和最小距離相對應(yīng)。

在以上3種情況中,2D雷達(dá)接收機(jī)探測不到激光回波,相應(yīng)的雷達(dá)掃描數(shù)據(jù)形成異常值。如圖1所示,點(diǎn)A、B、C及區(qū)域S中所包圍的點(diǎn)均屬于此類異常值。且2D雷達(dá)掃描數(shù)據(jù)的異常值分為兩種情況:①孤立異常點(diǎn),如點(diǎn)A、B、C；②聚集異常點(diǎn),如區(qū)域S所包圍的點(diǎn)。本文將采用最鄰近距離及局部異常因子分別對兩種情況進(jìn)行檢測。

圖1 2D激光雷達(dá)掃描數(shù)據(jù)Fig.1 2D lidar scanning data

2.2 最鄰近距離

在2D激光雷達(dá)工作環(huán)境中,物體表面一般為連續(xù)變化的,只有極少數(shù)物體的表面會存在過深的孔洞等影響掃描結(jié)果的因素。此外,本文不考慮雷達(dá)只能單次掃描到的微小物體。故做如下假設(shè):

(1)被掃描物體的表面是連續(xù)、光滑的,即物體表面不存在過深的孔洞等非光滑因素。

(2)物體空間尺度遠(yuǎn)大于激光雷達(dá)掃描間隔,且對于同一物體,激光雷達(dá)至少會掃描到兩點(diǎn)。

(3)測量值的相對誤差很小。

當(dāng)滿足以上假設(shè)時(shí),點(diǎn)Pi到其最近鄰近點(diǎn)的距離必然要小于某個(gè)確定的閾值。記單線激光雷達(dá)掃描數(shù)據(jù)集的n個(gè)點(diǎn)為P={P1P2…Pn}。Pi與點(diǎn)Pj之間的歐式距離記為d(Pi,Pj),本文據(jù)此定義最鄰近距離及孤立點(diǎn)。即:

對于不同型號的激光雷達(dá)、不同的測試環(huán)境及不同的被掃描物體,不可能給出統(tǒng)一的γ值,可以采用3δ法則確定γ值。

2.3 局部異常因子

2000年,Breunig 等提出基于局部離群因子(local outlier factor,LOF)的離群點(diǎn)檢測方法[17],該方法使用數(shù)據(jù)點(diǎn)與周圍緊鄰點(diǎn)的相對密度度量其離群程度。目前,LOF算法被廣泛的應(yīng)用到離群點(diǎn)檢測[18-20]。LOF算法中的相關(guān)定義為:

K-鄰近距離(K-distance):在點(diǎn)Pi的鄰近點(diǎn)集中,第K個(gè)鄰近點(diǎn)跟點(diǎn)Pi之間的距離稱為點(diǎn)Pi的K-鄰近距離,記為K-distance(Pi)。點(diǎn)Pi的第K距離,就是距離Pi第K遠(yuǎn)的點(diǎn)到Pi的距離(不包括Pi本身)。

K距離領(lǐng)域(K-distance neighborhood)點(diǎn)Pi的K距離領(lǐng)域是以點(diǎn)Pi為圓心,以K距離為半徑的圓內(nèi)所包含的點(diǎn)集合(包括圓上的點(diǎn))。Pi的第K距離領(lǐng)域內(nèi)點(diǎn)的個(gè)數(shù)至少是K。

可達(dá)距離(rechability distance):可達(dá)距離的定義跟K-鄰近距離是相關(guān)的,給定參數(shù)k,數(shù)據(jù)點(diǎn)Pi到數(shù)據(jù)點(diǎn)Pj的可達(dá)距離reach-dist(Pi,Pj)為數(shù)據(jù)點(diǎn)Pj的K-鄰近距離及數(shù)據(jù)點(diǎn)Pi與點(diǎn)Pj之間的直接距離的最大值。即:

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

(1)

局部可達(dá)密度(local reachability density):與點(diǎn)Pi的距離小于等于K-distance(Pi)的數(shù)據(jù)點(diǎn)集合稱為點(diǎn)Pi的K-nearest-neighbor,記為NK(Pi),點(diǎn)Pi的局部可達(dá)密度是其與鄰近數(shù)據(jù)點(diǎn)集合平均可達(dá)距離的倒數(shù),即:

(2)

局部異常因子(local outlier factor):點(diǎn)Pi的局部異常因子(局部相對密度)是點(diǎn)Pi鄰近點(diǎn)的平均局部可達(dá)密度與點(diǎn)Pi的局部可達(dá)密度的比值,即:

(3)

由局部異常因子定義可知,如果某個(gè)數(shù)據(jù)點(diǎn)相對于其鄰近數(shù)據(jù)點(diǎn)比較疏遠(yuǎn),它的局部可達(dá)密度就小。LOF算法衡量數(shù)據(jù)點(diǎn)的異常程度,并不是看它的絕對局部密度,而是看它相對鄰近數(shù)據(jù)點(diǎn)集合的密度。該方法允許數(shù)據(jù)點(diǎn)分布不均勻、密度不同。

2.4 最鄰近距離-局部異常因子檢測算法

LOF定義表明:如果數(shù)據(jù)點(diǎn)Pi的 LOF值在1附近,數(shù)據(jù)點(diǎn)Pi的局部密度跟其鄰域內(nèi)的其余點(diǎn)差不多；點(diǎn)Pi的 LOF的值小于1,點(diǎn)Pi的局部密度就高于其鄰域點(diǎn)密度；點(diǎn)Pi的 LOF值大于1,點(diǎn)Pi密度小于其鄰域點(diǎn)密度,很有可能是異常點(diǎn)。2D激光雷達(dá)掃描數(shù)據(jù)為點(diǎn)掃描數(shù)據(jù),數(shù)據(jù)點(diǎn)比較稀疏,大于1的LOF值較多。如果取LOF的閾值為1,則大部分掃描數(shù)據(jù)點(diǎn)會被判別為異常點(diǎn),故本文采用3δ準(zhǔn)則確定LOF的閾值。基于最鄰近距離-局部異常因子的2D激光雷達(dá)掃描數(shù)據(jù)的異常數(shù)據(jù)點(diǎn)檢測步驟如下:

Step 2:計(jì)算鄰近距離集合D的均值、方差,確定閾值γ.

Step 3:確定2D雷達(dá)掃描數(shù)據(jù)集合的孤立點(diǎn),并剔除.

Step 4:計(jì)算2D雷達(dá)掃描數(shù)據(jù)集合的LOF值集合。

Step 5:計(jì)算LOF值集合的均值、方差,確定LOF閾值.

Step 6:確定LOF數(shù)據(jù)集合的異常值,并剔除.

3 實(shí)驗(yàn)驗(yàn)證及結(jié)果分析

本文采用MALTAB中SLAM開源數(shù)據(jù)集驗(yàn)證上述算法。該數(shù)據(jù)是移動機(jī)器人在室內(nèi)環(huán)境中所采集的激光雷達(dá)掃描數(shù)據(jù)集,激光雷達(dá)最大有效測距距離8 m,每兩次掃描之間的平均位移約為0.6 m,共72組。室內(nèi)移動機(jī)器人的雷達(dá)掃描環(huán)境及近似軌跡如圖1所示。

圖2 激光雷達(dá)掃描環(huán)境及近似軌跡Fig.2 Scanning environment and approximate trajectory of lidar

在LOF值計(jì)算中,K-鄰近距離的K值(決定鄰域的范圍)會影響異常數(shù)據(jù)檢測的準(zhǔn)確率,此外,隨著K值的增加,計(jì)算開銷也急劇增大,文獻(xiàn)[17]推薦K的取值范圍是10～20,本文選用K=20。選用2D激光雷達(dá)掃描數(shù)據(jù)集中的第1、5、10及第20組數(shù)據(jù)驗(yàn)證最鄰近距離-局部異常因子異常數(shù)據(jù)檢測算法。最小鄰近距離及局部異常因子的計(jì)算結(jié)果如圖3、5、7、9、11所示；2D雷達(dá)掃描數(shù)據(jù)的異常數(shù)據(jù)檢測結(jié)果如圖4、6、8、10、12所示；誤報(bào)率及計(jì)算時(shí)間如表1所示。誤報(bào)率計(jì)算公式為:

圖3 第1組掃描數(shù)據(jù)最鄰近距離與局部異常因子Fig.3 The nearest neighbor distance and local anomalyfactor of the 1st scanning data

圖4 第1組雷達(dá)掃描數(shù)據(jù)的異常檢測結(jié)果Fig.4 Abnormal detection results of the 1st scanning data

(4)

在(4)式中,FP為誤報(bào)率;NFP為誤報(bào)的數(shù)據(jù)點(diǎn)數(shù)量;N為數(shù)據(jù)集合中數(shù)據(jù)點(diǎn)的數(shù)量。

圖5 第5組雷達(dá)掃描數(shù)據(jù)最鄰近距離與局部異常因子Fig.5 The nearest neighbor distance and local anomaly factorof the 5th scanning data

圖6 第5組雷達(dá)掃描數(shù)據(jù)的異常檢測結(jié)果Fig.6 Abnormal detection results of the 5th scanning data

圖7 第10組雷達(dá)掃描數(shù)據(jù)最鄰近距離與局部異常因子Fig.7 The nearest neighbor distance and local anomalyfactor of the 10th scanning data

圖8 第10組雷達(dá)掃描數(shù)據(jù)的異常檢測結(jié)果Fig.8 Abnormal detection results of the 10th scanning data

圖9 第15組雷達(dá)掃描數(shù)據(jù)最鄰近距離與局部異常因子Fig.9 The nearest neighbor distance and local anomalyfactor of the 15th scanning data

圖10 第15組雷達(dá)掃描數(shù)據(jù)的異常檢測結(jié)果Fig.10 Abnormal detection results of the 15th scanning data

圖11 第20組掃描數(shù)據(jù)最鄰近距與局部異常因子Fig.11 The nearest neighbor distance and localanomaly factor of the 20th scanning data

圖12 第20組雷達(dá)掃描數(shù)據(jù)的異常檢測結(jié)果Fig.12 Abnormal detection results of the 20th scanning data

從圖3、5、7、9、11可看出,最鄰近距離及局部異常因子的數(shù)值均相對集中,只有極少部分異常數(shù)據(jù),故可以將最小鄰近距離及局部異常因子用于2D激光雷達(dá)掃描數(shù)據(jù)的異常值檢測。從圖4、6、10、12可以看出,最鄰近距離只能檢測出部分激光脈沖無回波所產(chǎn)生的隨機(jī)異常數(shù)據(jù),局部異常因子可以檢測出剩余隨機(jī)異常數(shù)據(jù),最鄰近距離-局部異常因子算法無漏檢現(xiàn)象。從圖4、6、8、10、12可看出,最鄰近距離-局部異常因子算法會將極少的離群正常數(shù)據(jù)誤判為異常數(shù)據(jù)。表1中表明:最鄰近距離-局部異常因子算法平均誤報(bào)率為1.228 %,最大誤報(bào)率2.47 %,最小誤報(bào)率為0.87 %,算法可以滿足實(shí)際需要,且算法的運(yùn)行時(shí)間較短,平均運(yùn)行時(shí)間為0.842 s。綜上所述,最鄰近距離-局部異常因子算法能夠較好的適用于2D激光雷達(dá)掃描數(shù)據(jù)的異常值處理。

表1 誤報(bào)率及計(jì)算時(shí)間Tab.1 False alarm rate and calculation time

4 結(jié) 論

本文基于最鄰近距離-局部異常因子檢測算法對2D激光雷達(dá)掃描數(shù)據(jù)進(jìn)行檢測,并采用5組2D激光雷達(dá)掃描的實(shí)測數(shù)據(jù)對算法進(jìn)行測試。測試結(jié)果表明:

1) 最鄰近距離-局部異常因子檢測算法能夠很好的檢測出2D激光雷達(dá)掃描數(shù)據(jù)的異常值。

2) 最鄰近距離-局部異常因子算法會將極少量的離群正常點(diǎn)誤判斷為異常點(diǎn),測試結(jié)果表明該算法的誤報(bào)率很低。

3) 最鄰近距離-局部異常因子檢測算法計(jì)算時(shí)間較少,可滿足實(shí)際需求。