王東生

（南京理工大學(xué)計(jì)算機(jī)科學(xué)與工程學(xué)院 南京 210094）

1 引言

無人駕駛系統(tǒng)中的核心任務(wù)之一是障礙物檢測(cè)，激光雷達(dá)作為一種高精度距離傳感器，具有探測(cè)范圍廣，受光照等環(huán)境因素影響小等優(yōu)點(diǎn)［1］，被廣泛應(yīng)用于障礙物檢測(cè)中。激光雷達(dá)獲取的數(shù)據(jù)稱為點(diǎn)云，基于點(diǎn)云進(jìn)行障礙物檢測(cè)是無人駕駛系統(tǒng)中的關(guān)鍵技術(shù)之一。

聚類算法能夠?qū)⑻卣飨嘟臄?shù)據(jù)聚為一類，可以用于從點(diǎn)云數(shù)據(jù)中提取障礙物。常見的聚類算法可以分為基于劃分的聚類算法、基于網(wǎng)格的聚類算法、基于密度的聚類算法。K-Means算法是劃分聚類算法的代表，該算法實(shí)現(xiàn)簡單，運(yùn)行速度快，但是需要預(yù)先給定聚類個(gè)數(shù)，且受噪聲數(shù)據(jù)影響較大［2～4］?；诰W(wǎng)格的聚類算法將數(shù)據(jù)空間劃分為網(wǎng)格單元結(jié)構(gòu)，再對(duì)網(wǎng)格進(jìn)行計(jì)算和聚類，該類方法受網(wǎng)格劃分精度影響較大，且需要進(jìn)行特殊的邊緣 處 理［5～8］。DBSCAN（Density-Based Spatial Clustering of Applications with Noise）算法是經(jīng)典的基于密度的聚類算法，該方法不需要預(yù)先給出聚類個(gè)數(shù)，可以檢測(cè)出任何形狀的類別，同時(shí)可以檢測(cè)出噪聲數(shù)據(jù)［9～11］。

本文針對(duì)無人駕駛車輛行駛在結(jié)構(gòu)化道路的場景，結(jié)合多線激光雷達(dá)的特點(diǎn)，提出了一種基于數(shù)據(jù)分布密度的加權(quán)RANSAC（Random Sample Consensus）直線檢測(cè)算法以及一種基于動(dòng)態(tài)閾值的DBSCAN（Dynamic Threshold Density-Based Spatial Clustering of Applications with Noise，DT-DBSCAN）聚類算法。實(shí)驗(yàn)表明，本文方法可以滿足無人駕駛系統(tǒng)實(shí)時(shí)性的要求，經(jīng)過改進(jìn)后提高了檢測(cè)的魯棒性和準(zhǔn)確率。

2 感興趣區(qū)域提取

在結(jié)構(gòu)化道路場景中，無人駕駛車輛行駛的感興趣區(qū)域（Region of Interest，ROI）為道路區(qū)域，雖然激光雷達(dá)可以感知到道路區(qū)域以外的環(huán)境信息，但該信息對(duì)于無人駕駛系統(tǒng)意義不大。因此提取出感興趣區(qū)域可以減少噪聲的干擾，同時(shí)可以提升障礙物檢測(cè)的速度。

2.1 多線激光雷達(dá)的數(shù)據(jù)分布

多線激光雷達(dá)在工作時(shí)向外界發(fā)射一簇具有固定垂直角分辨率的激光束，反射回來的激光經(jīng)過處理即可獲得外界環(huán)境信息。激光雷達(dá)的工作原理決定了點(diǎn)云數(shù)據(jù)的“近密遠(yuǎn)疏”性質(zhì)，即同樣大小的障礙物，在近處可以得到密集的點(diǎn)云數(shù)據(jù)，而在遠(yuǎn)處只能得到稀疏的點(diǎn)云數(shù)據(jù)。另一方面由于激光不具有穿透性，當(dāng)近處的物體擋住了激光后，相同方向更遠(yuǎn)處的障礙物將不能被感知到，這也加劇了點(diǎn)云數(shù)據(jù)的“近密遠(yuǎn)疏”性質(zhì)。

圖1 點(diǎn)云數(shù)據(jù)的近密遠(yuǎn)疏性質(zhì)

2.2 加權(quán)RANSAC直線檢測(cè)算法

Hough 變換常用于檢測(cè)二維圖像中的直線，它將圖像空間中的直線映射到參數(shù)空間，然后在參數(shù)空間檢測(cè)直線，該方法的檢測(cè)精度和檢測(cè)速率受限于參數(shù)空間中角度的分辨率［12］，但難以應(yīng)用于三維數(shù)據(jù)。RANSAC［13］（隨機(jī)抽樣一致性算法，Random Sampling Consensus）廣泛應(yīng)用于特征匹配、矩陣估計(jì)等計(jì)算機(jī)視覺領(lǐng)域［14］，具有極強(qiáng)的魯棒性［15］，可用于直線檢測(cè)［16］、平面檢測(cè)［17］等。

結(jié)構(gòu)化道路的道路邊界具有重要意義，它限制了無人駕駛系統(tǒng)的可通行區(qū)域。本文結(jié)合激光雷達(dá)點(diǎn)云數(shù)據(jù)的分布特點(diǎn)，提出了改進(jìn)的加權(quán)RANSAC直線檢測(cè)算法。算法具體流程如下：

1）輸入當(dāng)前點(diǎn)云數(shù)據(jù)；

2）任意選取兩個(gè)不同的點(diǎn)并確定一條直線L；計(jì)算與直線L距離小于D的點(diǎn)的個(gè)數(shù)N；

3）記錄并更新N的最大值Nmax及對(duì)應(yīng)的直線參數(shù)P；

4）Repeat；

5）輸出最優(yōu)的直線方程。

根據(jù)激光雷達(dá)點(diǎn)云數(shù)據(jù)的特性可知，近處的道路邊界反射回來的點(diǎn)數(shù)量較多，遠(yuǎn)處的道路邊界反射回來的點(diǎn)數(shù)量較少，數(shù)據(jù)分布不均勻。為了解決這個(gè)問題，本文改進(jìn)了RANSAC直線檢測(cè)算法中直線上的點(diǎn)的計(jì)算方法。原始的計(jì)算方法如下：

其中L為當(dāng)前擬合的直線，D為判斷點(diǎn)在直線上的閾值，pi代表點(diǎn)的坐標(biāo)，F(xiàn)定義如下：

其中dis(L,pi)表示點(diǎn)到直線的距離。

上述計(jì)算方法中，沒有考慮到數(shù)據(jù)分布不均的特性，近處的點(diǎn)和遠(yuǎn)處的點(diǎn)被同等對(duì)待，很有可能因?yàn)榻幍狞c(diǎn)過于密集從而造成誤判。改進(jìn)的思路是利用數(shù)據(jù)分布的特性，密集區(qū)域內(nèi)的數(shù)據(jù)對(duì)最終計(jì)數(shù)結(jié)果貢獻(xiàn)應(yīng)該稍低，而稀疏區(qū)域內(nèi)的數(shù)據(jù)對(duì)最終計(jì)數(shù)結(jié)果貢獻(xiàn)應(yīng)該稍高，改進(jìn)后的F定義如下：

其中O表示坐標(biāo)原點(diǎn)，L為當(dāng)前擬合的直線，D為判斷點(diǎn)在直線上的閾值，pi代表點(diǎn)的坐標(biāo)，dis(O,pi)表示兩點(diǎn)之間的距離，W表示權(quán)重系數(shù)。

改進(jìn)后的計(jì)算方法充分考慮了激光雷達(dá)點(diǎn)云數(shù)據(jù)分布不均的特性，在進(jìn)行計(jì)數(shù)時(shí)，所有的點(diǎn)的計(jì)數(shù)貢獻(xiàn)最大為1，最小為0，且密集區(qū)域內(nèi)的數(shù)據(jù)貢獻(xiàn)更小，稀疏區(qū)域內(nèi)的數(shù)據(jù)貢獻(xiàn)更大。

2.3 ROI提取

根據(jù)上述方法檢測(cè)出道邊后，可以從數(shù)據(jù)中提取出感興趣區(qū)域。假設(shè)道邊的直線方程為

則感興趣區(qū)域內(nèi)的點(diǎn)pi(xi,yi,zi)滿足：

根據(jù)上式可以提取出感興趣區(qū)域。

3 基于動(dòng)態(tài)閾值的DBSCAN 障礙物檢測(cè)方法

3.1 DBSCAN聚類方法

DBSCAN 是經(jīng)典的聚類方法，該方法以密度為標(biāo)準(zhǔn)將數(shù)據(jù)劃分為核心點(diǎn)、噪聲點(diǎn)，再將距離較近的核心點(diǎn)聚集為一簇，同時(shí)將距離某一簇較近的噪聲點(diǎn)加入該簇，作為該簇的邊界點(diǎn)。該方法的優(yōu)勢(shì)在于不需要預(yù)先確定聚類的個(gè)數(shù)，同時(shí)可以發(fā)現(xiàn)任何形狀的類，缺點(diǎn)是參數(shù)受實(shí)際場景影響較大。DBSCAN算法流程如下：

1）初始化參數(shù)掃描半徑Eps，類別包含的最小點(diǎn)數(shù)MinPts；

2）以Eps為半徑掃描點(diǎn)p的鄰居點(diǎn)，根據(jù)鄰居點(diǎn)的個(gè)數(shù)判斷p為核心點(diǎn)還是邊界點(diǎn)；

3）若p是核心點(diǎn)，記錄p的鄰居節(jié)點(diǎn)（距離小于Eps），稱p和這些點(diǎn)直接密度可達(dá)；

4）重復(fù)2）、3）直到所有點(diǎn)被遍歷；

5）對(duì)于每一個(gè)核心點(diǎn)，將該核心點(diǎn)和其直接密度可達(dá)的核心點(diǎn)聚為一類；

6）將距離小于Eps的類進(jìn)行合并，直到所有的類都不能繼續(xù)合并，即找到了所有的最大密度相連點(diǎn)集合；

7）將距離某一類距離小于Eps的噪聲點(diǎn)加入該類，稱為邊界點(diǎn)；

8）輸出所有的聚類結(jié)果。

3.2 DT-DBSCAN聚類方法

DBSCAN 算法中，Eps和MinPts的選取至關(guān)重要，原始的DBSCAN算法常根據(jù)實(shí)際應(yīng)用場景選擇固定的參數(shù)，該方法在數(shù)據(jù)分布較為均勻的情況下效果較好。當(dāng)數(shù)據(jù)分布不均時(shí)，單一的參數(shù)無法作用于全局?jǐn)?shù)據(jù)，在某些區(qū)域可以獲得較好的檢測(cè)效果，然而在另外一些區(qū)域檢測(cè)效果往往較差。激光雷達(dá)點(diǎn)云數(shù)據(jù)正是分布不均勻的，如果使用單一的參數(shù)，難以同時(shí)保證遠(yuǎn)處、近處的檢測(cè)效果。

針對(duì)該問題，本文結(jié)合激光雷達(dá)點(diǎn)云數(shù)據(jù)分布不均的特性，提出了基于動(dòng)態(tài)閾值的DBSCAN的算法。該方法考慮了數(shù)據(jù)分布不均的情況，可以同時(shí)兼顧所有區(qū)域的檢測(cè)效果。點(diǎn)pi(xi,yi,zi)處的參數(shù)取值為

其中pi(xi,yi,zi)表示當(dāng)前點(diǎn)的坐標(biāo)，WEps,WMinPts表示權(quán)重系數(shù)。

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

本節(jié)通過實(shí)驗(yàn)及分析，驗(yàn)證了改進(jìn)后的RANSAC 直線檢測(cè)算法的準(zhǔn)確率優(yōu)勢(shì)和DT-DBSCAN算法在分布不均勻的數(shù)據(jù)中的優(yōu)勢(shì)。本文先在KITTI［18］道路數(shù)據(jù)集上進(jìn)行實(shí)驗(yàn)，對(duì)多個(gè)場景進(jìn)行感興趣區(qū)域提取和障礙物檢測(cè)，對(duì)比和分析了改進(jìn)前后的檢測(cè)性能與結(jié)果。然后還使用實(shí)際場景數(shù)據(jù)驗(yàn)證和評(píng)估算法性能。實(shí)驗(yàn)環(huán)境為Intel i5-9300H@2.4GHz，8G內(nèi)存，Windows10操作系統(tǒng)。

4.1 KITTI數(shù)據(jù)集評(píng)估

KITTI數(shù)據(jù)集由德國卡爾斯魯厄理工學(xué)院和豐田美國技術(shù)研究院聯(lián)合主辦，是經(jīng)典的自動(dòng)駕駛場景下的計(jì)算機(jī)算法評(píng)估數(shù)據(jù)集。該數(shù)據(jù)集包含市區(qū)、鄉(xiāng)村和高速公路等場景采集的真實(shí)圖像數(shù)據(jù)，可滿足不同的測(cè)試要求。本文選取了不同場景下的數(shù)據(jù)進(jìn)行直線檢測(cè)與障礙物檢測(cè)，并對(duì)比了改進(jìn)前后的檢測(cè)結(jié)果。

圖2 給出了KITTI 數(shù)據(jù)集456 號(hào)場景下的直線檢測(cè)結(jié)果，其中灰色線段代表改進(jìn)前的原始RANSAC 直線檢測(cè)算法結(jié)果，白色線段代表改進(jìn)后的加權(quán)RANSAC 直線檢測(cè)算法結(jié)果。該場景下感興趣區(qū)域內(nèi)障礙物較少，故激光雷達(dá)感知的道路邊界信息較為完整。對(duì)比檢測(cè)結(jié)果可以發(fā)現(xiàn)，原始的RANSAC 直線檢測(cè)算法與實(shí)際道邊位置偏差較大，加權(quán)RANSAC 直線檢測(cè)算法得到結(jié)果更符合實(shí)際道邊位置，誤差更小。這是因?yàn)樵嫉腞ANSAC直線檢測(cè)算法沒有考慮點(diǎn)云數(shù)據(jù)分布不均的特性，近處的數(shù)據(jù)較多因此算法結(jié)果受近處數(shù)據(jù)影響較大，在遠(yuǎn)處出現(xiàn)偏差。改進(jìn)后的加權(quán)RANSAC 直線檢測(cè)算法考慮了數(shù)據(jù)分布不均的特性，取得了更好的檢測(cè)結(jié)果，在遠(yuǎn)處的偏差更小。

圖2 KITTI456直線檢測(cè)結(jié)果對(duì)比

圖3 給出了KITTI 數(shù)據(jù)集2345 號(hào)場景下的直線檢測(cè)結(jié)果。其中灰色線段代表改進(jìn)前的原始RANSAC 直線檢測(cè)算法結(jié)果，白色線段代表改進(jìn)后的加權(quán)RANSAC 直線檢測(cè)算法結(jié)果。該場景下感興趣區(qū)域內(nèi)障礙物較多，故激光雷達(dá)感知的道路邊界信息不完整，點(diǎn)云數(shù)據(jù)中表示道邊的數(shù)據(jù)整體上更少。該場景中遠(yuǎn)處的數(shù)據(jù)更少，因此改進(jìn)前后的算法檢測(cè)結(jié)果相近。這表明了加權(quán)RANSAC 直線檢測(cè)算法保留了RANSAC 直線檢測(cè)算法的中心思想，在數(shù)據(jù)分布相對(duì)均勻的時(shí)候可以獲得相近的結(jié)果，在數(shù)據(jù)分布不均的時(shí)候也可以獲得更好的結(jié)果。

圖3 KITTI2345直線檢測(cè)結(jié)果對(duì)比

圖4 和圖5 分別給出了DBSCAN 算法和DT-DBSCAN 算法的檢測(cè)結(jié)果，檢測(cè)得到的障礙物由白色包圍框給出定位。從圖中可以看出，改進(jìn)前后的算法在近處場景的檢測(cè)結(jié)果相近，DBSCAN 算法沒能檢測(cè)出較遠(yuǎn)的障礙物，而DT-DBSCAN 算法檢測(cè)出了遠(yuǎn)方的障礙物。在該場景中，道路左半部分有兩輛車，右半部分有四棵樹，它們均是感興趣區(qū)域中的障礙物，無人駕駛車輛在行駛時(shí)需要避開。由于激光雷達(dá)點(diǎn)云數(shù)據(jù)分布的不均勻性，單一閾值無法很好地作用于整體數(shù)據(jù)，如果為了檢測(cè)出遠(yuǎn)方的障礙物而放寬閾值限制，那么近處的單個(gè)障礙物可能會(huì)被分割為多個(gè)，近處的噪聲也可能被誤檢測(cè)為障礙物，如果使用嚴(yán)格的閾值，遠(yuǎn)處的障礙物由于數(shù)據(jù)較少很可能無法被檢測(cè)到。改進(jìn)后的DT-DBSCAN 算法解決了上述問題，檢測(cè)出了近處和遠(yuǎn)處的障礙物，效果優(yōu)于DBSCAN算法。

圖4 KITTI456改進(jìn)前障礙物檢測(cè)結(jié)果

圖5 KITTI456改進(jìn)后障礙物檢測(cè)結(jié)果

4.2 實(shí)際場景數(shù)據(jù)評(píng)估

在實(shí)際公路場景中采集數(shù)據(jù)，以評(píng)估本文提出的障礙物檢測(cè)方法。

由圖6 可以看出，本文提出的方法在直線檢測(cè)結(jié)果和障礙物檢測(cè)結(jié)果中均優(yōu)于改進(jìn)前的算法，其中灰色直線和灰色框代表改進(jìn)之前的檢測(cè)結(jié)果，白色直線和白色框代表改進(jìn)之后的檢測(cè)結(jié)果，最近的障礙物距離為50m 遠(yuǎn)，最遠(yuǎn)的障礙物距離為180m遠(yuǎn)，因距離較遠(yuǎn)故圖中顯示的點(diǎn)云數(shù)據(jù)較為稀疏。改進(jìn)之后的加權(quán)RANSAC 算法檢測(cè)出的直線誤差更?。桓倪M(jìn)之后的DT-DBSCAN 算法除了能夠檢測(cè)出近處的障礙物，甚至能夠檢測(cè)出了180m 外超遠(yuǎn)距離的障礙物。實(shí)驗(yàn)隨機(jī)選取了多幀場景并統(tǒng)計(jì)了檢測(cè)結(jié)果的誤差，如表1、表2所示。

圖6 實(shí)際場景檢測(cè)結(jié)果對(duì)比

表1 改進(jìn)前后的直線檢測(cè)算法比較

表2 改進(jìn)前后的障礙物檢測(cè)算法比較

4.3 結(jié)果分析

由實(shí)驗(yàn)結(jié)果可知，本文提出的障礙物檢測(cè)算法得到了很好的驗(yàn)證。加權(quán)RANSAC 直線檢測(cè)算法克服了數(shù)據(jù)分布不均帶來的問題，整體誤差較小，而改進(jìn)前的直線檢測(cè)算法受近處數(shù)據(jù)影響較大，部分場景下在遠(yuǎn)處的檢測(cè)結(jié)果誤差很大，由表1 可知改進(jìn)后的算法誤差平均誤差減小了0.27m。DT-DBSCAN 算法同時(shí)保證了近處和遠(yuǎn)處的聚類效果，近處的大目標(biāo)和遠(yuǎn)處的小目標(biāo)都能被檢測(cè)到。經(jīng)過多次實(shí)驗(yàn)驗(yàn)證，本文方法障礙物檢測(cè)成功率86.8%，比改進(jìn)前提高了15.4%，可以滿足實(shí)際場景需求。

5 結(jié)語

針對(duì)結(jié)構(gòu)化道路的無人駕駛場本文提出了一種障礙物檢測(cè)方法，具體包括加權(quán)RANSAC直線檢測(cè)算法與DT-DBSCAN 聚類算法。加權(quán)RANSAC直線檢測(cè)算法在原有算法的基礎(chǔ)上考慮了點(diǎn)云數(shù)據(jù)分布不均的特性，解決了檢測(cè)結(jié)果受局部數(shù)據(jù)影響過大的問題。DT-DBSCAN 算法用于檢測(cè)障礙物，該方法解決了DBSCAN 算法閾值單一的問題，考慮了數(shù)據(jù)的分布不均特性，在近處和遠(yuǎn)處都有較好的檢測(cè)結(jié)果。本文的研究場景為結(jié)構(gòu)化道路場景，場景特征比較明顯，噪聲較少，如何在半結(jié)構(gòu)化道路甚至是非結(jié)構(gòu)化道路中實(shí)現(xiàn)障礙物檢測(cè)還需要進(jìn)一步的研究。