一種結構化道路環境的障礙物檢測方法*

王東生

（南京理工大學計算機科學與工程學院 南京 210094）

1 引言

無人駕駛系統中的核心任務之一是障礙物檢測，激光雷達作為一種高精度距離傳感器，具有探測范圍廣，受光照等環境因素影響小等優點［1］，被廣泛應用于障礙物檢測中。激光雷達獲取的數據稱為點云，基于點云進行障礙物檢測是無人駕駛系統中的關鍵技術之一。

聚類算法能夠將特征相近的數據聚為一類，可以用于從點云數據中提取障礙物。常見的聚類算法可以分為基于劃分的聚類算法、基于網格的聚類算法、基于密度的聚類算法。K-Means算法是劃分聚類算法的代表，該算法實現簡單，運行速度快，但是需要預先給定聚類個數，且受噪聲數據影響較大［2～4］?；诰W格的聚類算法將數據空間劃分為網格單元結構，再對網格進行計算和聚類，該類方法受網格劃分精度影響較大，且需要進行特殊的邊緣 處 理［5～8］。DBSCAN（Density-Based Spatial Clustering of Applications with Noise）算法是經典的基于密度的聚類算法，該方法不需要預先給出聚類個數，可以檢測出任何形狀的類別，同時可以檢測出噪聲數據［9～11］。

本文針對無人駕駛車輛行駛在結構化道路的場景，結合多線激光雷達的特點，提出了一種基于數據分布密度的加權RANSAC（Random Sample Consensus）直線檢測算法以及一種基于動態閾值的DBSCAN（Dynamic Threshold Density-Based Spatial Clustering of Applications with Noise，DT-DBSCAN）聚類算法。實驗表明，本文方法可以滿足無人駕駛系統實時性的要求，經過改進后提高了檢測的魯棒性和準確率。

2 感興趣區域提取

在結構化道路場景中，無人駕駛車輛行駛的感興趣區域（Region of Interest，ROI）為道路區域，雖然激光雷達可以感知到道路區域以外的環境信息，但該信息對于無人駕駛系統意義不大。因此提取出感興趣區域可以減少噪聲的干擾，同時可以提升障礙物檢測的速度。

2.1 多線激光雷達的數據分布

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

圖1 點云數據的近密遠疏性質

2.2 加權RANSAC直線檢測算法

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

結構化道路的道路邊界具有重要意義，它限制了無人駕駛系統的可通行區域。本文結合激光雷達點云數據的分布特點，提出了改進的加權RANSAC直線檢測算法。算法具體流程如下：

1）輸入當前點云數據；

2）任意選取兩個不同的點并確定一條直線L；計算與直線L距離小于D的點的個數N；

3）記錄并更新N的最大值Nmax及對應的直線參數P；

4）Repeat；

5）輸出最優的直線方程。

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

其中L為當前擬合的直線，D為判斷點在直線上的閾值，pi代表點的坐標，F定義如下：

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

上述計算方法中，沒有考慮到數據分布不均的特性，近處的點和遠處的點被同等對待，很有可能因為近處的點過于密集從而造成誤判。改進的思路是利用數據分布的特性，密集區域內的數據對最終計數結果貢獻應該稍低，而稀疏區域內的數據對最終計數結果貢獻應該稍高，改進后的F定義如下：

其中O表示坐標原點，L為當前擬合的直線，D為判斷點在直線上的閾值，pi代表點的坐標，dis(O,pi)表示兩點之間的距離，W表示權重系數。

改進后的計算方法充分考慮了激光雷達點云數據分布不均的特性，在進行計數時，所有的點的計數貢獻最大為1，最小為0，且密集區域內的數據貢獻更小，稀疏區域內的數據貢獻更大。

2.3 ROI提取

根據上述方法檢測出道邊后，可以從數據中提取出感興趣區域。假設道邊的直線方程為

則感興趣區域內的點pi(xi,yi,zi)滿足：

根據上式可以提取出感興趣區域。

3 基于動態閾值的DBSCAN 障礙物檢測方法

3.1 DBSCAN聚類方法

DBSCAN 是經典的聚類方法，該方法以密度為標準將數據劃分為核心點、噪聲點，再將距離較近的核心點聚集為一簇，同時將距離某一簇較近的噪聲點加入該簇，作為該簇的邊界點。該方法的優勢在于不需要預先確定聚類的個數，同時可以發現任何形狀的類，缺點是參數受實際場景影響較大。DBSCAN算法流程如下：

1）初始化參數掃描半徑Eps，類別包含的最小點數MinPts；

2）以Eps為半徑掃描點p的鄰居點，根據鄰居點的個數判斷p為核心點還是邊界點；

3）若p是核心點，記錄p的鄰居節點（距離小于Eps），稱p和這些點直接密度可達；

4）重復2）、3）直到所有點被遍歷；

5）對于每一個核心點，將該核心點和其直接密度可達的核心點聚為一類；

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

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

8）輸出所有的聚類結果。

3.2 DT-DBSCAN聚類方法

DBSCAN 算法中，Eps和MinPts的選取至關重要，原始的DBSCAN算法常根據實際應用場景選擇固定的參數，該方法在數據分布較為均勻的情況下效果較好。當數據分布不均時，單一的參數無法作用于全局數據，在某些區域可以獲得較好的檢測效果，然而在另外一些區域檢測效果往往較差。激光雷達點云數據正是分布不均勻的，如果使用單一的參數，難以同時保證遠處、近處的檢測效果。

針對該問題，本文結合激光雷達點云數據分布不均的特性，提出了基于動態閾值的DBSCAN的算法。該方法考慮了數據分布不均的情況，可以同時兼顧所有區域的檢測效果。點pi(xi,yi,zi)處的參數取值為

其中pi(xi,yi,zi)表示當前點的坐標，WEps,WMinPts表示權重系數。

4 實驗結果及分析

本節通過實驗及分析，驗證了改進后的RANSAC 直線檢測算法的準確率優勢和DT-DBSCAN算法在分布不均勻的數據中的優勢。本文先在KITTI［18］道路數據集上進行實驗，對多個場景進行感興趣區域提取和障礙物檢測，對比和分析了改進前后的檢測性能與結果。然后還使用實際場景數據驗證和評估算法性能。實驗環境為Intel i5-9300H@2.4GHz，8G內存，Windows10操作系統。

4.1 KITTI數據集評估

KITTI數據集由德國卡爾斯魯厄理工學院和豐田美國技術研究院聯合主辦，是經典的自動駕駛場景下的計算機算法評估數據集。該數據集包含市區、鄉村和高速公路等場景采集的真實圖像數據，可滿足不同的測試要求。本文選取了不同場景下的數據進行直線檢測與障礙物檢測，并對比了改進前后的檢測結果。

圖2 給出了KITTI 數據集456 號場景下的直線檢測結果，其中灰色線段代表改進前的原始RANSAC 直線檢測算法結果，白色線段代表改進后的加權RANSAC 直線檢測算法結果。該場景下感興趣區域內障礙物較少，故激光雷達感知的道路邊界信息較為完整。對比檢測結果可以發現，原始的RANSAC 直線檢測算法與實際道邊位置偏差較大，加權RANSAC 直線檢測算法得到結果更符合實際道邊位置，誤差更小。這是因為原始的RANSAC直線檢測算法沒有考慮點云數據分布不均的特性，近處的數據較多因此算法結果受近處數據影響較大，在遠處出現偏差。改進后的加權RANSAC 直線檢測算法考慮了數據分布不均的特性，取得了更好的檢測結果，在遠處的偏差更小。

圖2 KITTI456直線檢測結果對比

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

圖3 KITTI2345直線檢測結果對比

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

圖4 KITTI456改進前障礙物檢測結果

圖5 KITTI456改進后障礙物檢測結果

4.2 實際場景數據評估

在實際公路場景中采集數據，以評估本文提出的障礙物檢測方法。

由圖6 可以看出，本文提出的方法在直線檢測結果和障礙物檢測結果中均優于改進前的算法，其中灰色直線和灰色框代表改進之前的檢測結果，白色直線和白色框代表改進之后的檢測結果，最近的障礙物距離為50m 遠，最遠的障礙物距離為180m遠，因距離較遠故圖中顯示的點云數據較為稀疏。改進之后的加權RANSAC 算法檢測出的直線誤差更??；改進之后的DT-DBSCAN 算法除了能夠檢測出近處的障礙物，甚至能夠檢測出了180m 外超遠距離的障礙物。實驗隨機選取了多幀場景并統計了檢測結果的誤差，如表1、表2所示。

圖6 實際場景檢測結果對比

表1 改進前后的直線檢測算法比較

表2 改進前后的障礙物檢測算法比較

4.3 結果分析

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

5 結語

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