文獻標識碼： A
DOI：10.16157/j.issn.0258-7998.170392
中文引用格式： 段建民，王昶人，任璐，等. 基于多層激光雷達的可行駛區(qū)域信息提取算法[J].電子技術應用，2017，43(10)：78-82.
英文引用格式： Duan Jianmin，Wang Changren，Ren Lu，et al. Algorithm of driving area information extraction based on multi-layer lidar[J].Application of Electronic Technique，2017，43(10)：78-82.
0 引言
隨著社會的不斷發(fā)展，世界各國越來越多的學者開始對無人駕駛進行研究[1-2]，其中雷達技術更得到廣泛關注。文獻[3]利用路沿點數(shù)據(jù)斜率一致特性對路沿點進行提取，但該算法容易受路面點和障礙物點的影響并且要分層處理，所以準確性和實時性都不能達到要求。文獻[4]利用激光雷達返回高度數(shù)據(jù)的跳變提取路沿點，這種方法受障礙物影響很不穩(wěn)定。而對于聚類算法，由于激光雷達數(shù)據(jù)主要是成簇出現(xiàn)的，所以基于密度的聚類方法適合于激光雷達數(shù)據(jù)，其中OPTICS算法是典型的基于密度的聚類方法。文獻[5]利用結果序列重組織策略對OPTICS算法進行改進，但是在實際應用中，對于激光雷達數(shù)據(jù)點突然出現(xiàn)的噪點無法區(qū)分，導致障礙物提取效果不準確。
本文首先利用數(shù)據(jù)區(qū)間密度分布提取路沿點并通過最小二乘法擬合出路沿區(qū)分可行駛區(qū)域，然后在可行駛區(qū)域中利用改進的OPTICS算法對返回數(shù)據(jù)進行實時聚類。最后通過實車實驗驗證提出算法的有效性與實時性。
1 激光雷達數(shù)據(jù)預處理
1.1 激光雷達數(shù)據(jù)分析
本文應用德國IBEO公司生產(chǎn)的IBEO LUX 2010型四線激光雷達，該型號的雷達較單線激光雷達具有數(shù)據(jù)量大、檢測精度高、探測距離遠等優(yōu)勢[6]。其主要參數(shù)如表1所示。
四線雷達返回的信息主要包含序號、掃描層數(shù)、距離以及位置坐標信息。其特性分析如下：
(1)激光雷達是自左向右掃描的，每一幀返回的數(shù)據(jù)量基本相近；
(2)激光雷達返回的數(shù)據(jù)是根據(jù)前方場景的變化而變化的，每個障礙物的掃描點的數(shù)目及形狀不一；
(3)當激光雷達掃描到路沿時返回的數(shù)據(jù)特點是x軸坐標稀疏，y軸坐標緊密排列。
1.2 數(shù)據(jù)預處理
為了檢測車輛前方的可行駛區(qū)域以及障礙物的信息，將激光雷達安放在車輛前方正中間的位置，根據(jù)以往經(jīng)驗，雷達的安裝高度設定為0.846 m。安裝位置示意圖如圖1所示。
2 激光雷達數(shù)據(jù)處理方法
2.1 一維數(shù)據(jù)區(qū)間密度分布
假設(x1，y1)，(x2，y2)，(x3，y3)，…，(xn，yn)，n∈R為雷達返回路沿點數(shù)據(jù)，根據(jù)其特性，其中某一維數(shù)據(jù)D={y1，y2，y3，…，yn}，n∈R是基本相近的，數(shù)據(jù)區(qū)間概率密度分布即雷達返回的數(shù)據(jù)落在某個區(qū)間[ω，ξ]的密度，其公式為：
式中，ω和ξ為某個區(qū)間的兩個端點，num(yi)為落在某個區(qū)間數(shù)據(jù)的個數(shù)，分母為數(shù)據(jù)個數(shù)之和；P為在某個區(qū)間數(shù)據(jù)個數(shù)占總體的概率。若將整體的數(shù)據(jù)分為j個區(qū)間，則其概率的總和為1。
2.2 OPTICS算法
OPTICS[7-9](Order Point to Identify the Cluster Structure)算法是一種基于密度的聚類算法。此算法是DBSCAN算法的擴展，對數(shù)據(jù)對象集中的數(shù)據(jù)進行排序，輸出一個有序的對象列表(cluster-ordering)，在這個列表中包含了用來提取聚類的所有信息，即對數(shù)據(jù)對象進行分類。以下是OPTICS算法中引入的兩個定義[10]：
定義1 核心距離(core-distance)
假設點P包含m個鄰近的最小半徑為min-distance(P)，那么P點的核心距離就可以定義為：
定義2 可達距離(reach-distance，RD)
假設P是點o鄰近點之一，那么P與o相關的可達距離定義式為：
傳統(tǒng)的OPTICS聚類方法實現(xiàn)步驟如圖2所示，OPTICS算法的優(yōu)點是對輸入?yún)?shù)不敏感，但是輸入Eps與實際Eps差距較大時，聚類效果依然被影響，而且該算法對于噪點也不能區(qū)分。
2.3 基于加權歐氏距離的KNN圖
在實際的雷達數(shù)據(jù)中對雷達數(shù)據(jù)進行數(shù)據(jù)密度分布計算后提取各個峰值區(qū)域的點集，計算其橫、縱坐標的方差值，就可以計算出數(shù)據(jù)點間的加權歐氏距離。
KNN即將實際雷達掃描到的數(shù)據(jù)點按照加權歐氏距離求取其距離矩陣Distk*k，然后將Distk*k中每一維按照升序排列形成sort(Distk*k)，最后將sort(Distk*k)中的每一維數(shù)據(jù)繪制成KNN圖。
2.4 最小二乘法擬合
本文根據(jù)實驗道路特性，由于實驗道路兩側路沿點多呈線性分布，因此，使用最小二乘法對道路兩側提取的路沿點進行線性擬合。最小二乘法[12-14]是一種數(shù)學優(yōu)化方法，它通過最小化誤差的平方和尋找數(shù)據(jù)的最佳函數(shù)匹配。其針對線性擬合常用的表達式為y=kx+h，以下則是參數(shù)k和h的求解公式：
式中，n表示待擬合的點的個數(shù)，(xi，yi)為待擬合點的坐標值，k為斜率，h為截距。
3 可行駛區(qū)域信息提取方法
3.1 基于加權歐氏距離改進的OPTICS算法
傳統(tǒng)的OPTICS算法雖然能克服其他傳統(tǒng)聚類算法的一些問題[15]，但其自身仍然有一些不足之處，如OPTICS在實際的篩選核心點的過程中是通過選取合適的Eps來確定核心點的位置，而由于Eps選取不當引入噪點，這樣大大降低了算法對噪點的敏感程度，使得聚類不準確。另外，如果盲目選擇Eps的范圍，同樣影響聚類效果。
為了改進OPTICS的不足之處，本文提出了基于加權歐氏距離KNN改進的OPTICS算法，此算法不需要輸入?yún)?shù)Eps，而是通過數(shù)據(jù)點間加權歐氏距離升序排序形成一個k-最近鄰圖(KNN)來確定聚類結果以及區(qū)分噪點。具體步驟如圖3所示。
根據(jù)圖3所示，改進的OPTICS算法不需要選取Eps就可以直接進行聚類。在流程圖中基于加權歐氏距離KNN分離噪點的具體步驟如下：
(1)求取每類數(shù)據(jù)點中每個點之間的加權歐式距離，形成距離矩陣Distk*k；
(2)將距離矩陣中各維度距離按照升序排序，形成sort(Distk*k)；
(3)由于噪點與其他點的距離大于一個閾值，所以就要判定這個點與其他點之間距離最小距離是否大于threshold，若大于，則該點為噪點。
3.2 基于一維數(shù)據(jù)區(qū)間密度分布的路沿提取算法
通過對激光雷達返回的點云數(shù)據(jù)分析可知，在點云中包含有路面點、兩側路沿點、周圍花草景物點以及障礙物點。設定k個等距區(qū)間[ω，ξ]，在此區(qū)間中利用式(2)求取雷達數(shù)據(jù)點在每個區(qū)間的密度。以橫軸零為分界點，提取出兩側密度最大值及次大值所在區(qū)間。由經(jīng)驗知，路面點與路沿點高度差大約為20 cm，根據(jù)此高度差可消除路面點。得到路沿點后，將路沿點使用改進的OPTICS算法進行聚類，最后利用最小二乘法擬合得到路沿，并計算得到路沿信息。
3.3 可行駛區(qū)域內障礙物信息提取
通過得到的路沿信息，可判定出路面的路寬度。若假設左右路沿點的范圍分別為[a，b]和[c，d]，則根據(jù)橫向定界及式(8)得到可行駛區(qū)域的范圍：
式中，Croad為可行駛區(qū)域，Cnoise為周圍環(huán)境。
根據(jù)無人駕駛車輛寬度信息和提取出可行駛區(qū)域的寬度信息結合，其表達式為：
提取出可行駛區(qū)域后，剩下的點為障礙物以及噪點。障礙物點主要有：行人、機動車、自行車等。障礙物的主要屬性信息表示為距離、角度、中心點等。利用改進的OPTICS算法將可行駛區(qū)域內的障礙物進行聚類，并提取出每類障礙物的距離、角度以及障礙物中心點x、y、z坐標值。通過類內計算得到障礙物的長度、寬度、距離、角度以及速度等信息。
4 實車實驗結果
4.1 實驗條件及平臺
本文實驗平臺為BJUT-IV(Beijing University of Technology Intelligent Vehicle)自主研發(fā)的無人駕駛車，在車輛的前端正中的位置安裝IBEO-LUX四線激光雷達來采集實驗數(shù)據(jù)。雷達安裝高度為0.846 m。實驗的場景為校園內道路，如圖4所示。
4.2 可行駛區(qū)域路沿提取實驗結果
可行駛區(qū)域路沿提取實驗結果如圖5所示。
圖4左側為實驗場景1，道路條件為無車輛通過。圖5(b)為原始數(shù)據(jù)點，原始數(shù)據(jù)點中包含路沿點、路面點，及周圍的樹木、鐵網(wǎng)。圖中雷達數(shù)據(jù)點分為4層，由圖中箭頭所指的點表示。圖5(a)為雷達返回數(shù)據(jù)坐標y值的數(shù)據(jù)密度分布直方圖，其中以零為分界點，4個范圍中靠近零的兩個區(qū)間為路沿點區(qū)間，而另外兩個區(qū)間為球場邊界。根據(jù)密度直方圖可以清晰地分析出左側路沿點所在范圍[-3.92，-3.7]，右側路沿點范圍為[6.4，6.8]。通過對區(qū)間密度的選取，就得到了如圖5(c)所示的情況，圖中的兩列點則為通過基于一維數(shù)據(jù)區(qū)間密度提取出的結果。圖5(d)是將提取出的路沿點通過基于加權歐式距離的KNN改進的OPTICS算法進行聚類，圖中橢圓形框是為了清楚表示兩類的聚類結果。最后通過最小二乘法將兩側提取出的路沿點進行線性擬合，結果如圖5(e)所示。提取出的路沿結果顯示，道路的寬度為10.48 m，車輛左側與路沿距離為6.64 m，車輛右側與路沿距離為3.83 m。在實際的實驗場景中通過測量得到實際的道路寬度約為10.5 m，提取結果與實際寬度僅差0.02 m，路面寬度信息檢測率為99.8％，符合實際應用需要。
4.3 可行駛區(qū)域障礙物提取實驗結果
可行駛區(qū)域障礙物提取結果如圖6所示，圖4右側為實驗場景2，場景中有行人和汽車。圖6(a)為第47幀加權歐氏距離KNN圖，圖中稀疏部分為文中提到的噪點，其他部分為聚類效果。圖6(b)為車輛行駛過程中第47幀數(shù)據(jù)利用傳統(tǒng)OPTICS算法檢測出路面的障礙物的情況。從圖中可以看出，由于在雷達掃描過程中第3層數(shù)據(jù)出現(xiàn)噪點，所以影響了聚類效果，導致聚類準確性降低。而圖6(c)為第47幀數(shù)據(jù)利用基于加權歐氏距離的KNN改進OPTICS算法的效果，算法可以避免路面噪點的影響，而且可以對障礙物準確的聚類，并且通過計算可以得到障礙物的主要屬性，檢測到行人的長度length=0.1 m，寬度為width=0.3 m，檢測到車輛的長度為length=3.3 m，寬度為width=1.7 m，包括雷達距離前方障礙物的距離，檢測結果與實際測量尺寸基本相符，滿足了檢測要求。
圖6(d)為第45幀傳統(tǒng)OPTICS算法檢測結果，圖中將路面噪點當作障礙物，影響了聚類準確性。圖6(e)為第45幀數(shù)據(jù)利用改進OPTICS算法，效果良好。通過以上實驗結果可以證明，本文提出的可行駛區(qū)域提取算法的有效性與實時性都得到提高。
5 結束語
本文提出的可行駛區(qū)域信息提取算法包括可行駛區(qū)域路沿提取和障礙物提取，在路沿提取中，利用一維數(shù)據(jù)區(qū)間密度分布對雷達數(shù)據(jù)進行界定，并通過界定范圍提取路沿點，這種方法根據(jù)數(shù)據(jù)密度提取路沿點排除了路面障礙物對路沿點提取的影響，并且對多層數(shù)據(jù)同時處理，減少了復雜度。通過基于加權歐氏距離的KNN改進OPTICS算法將路面上的障礙物點云進行聚類，并通過計算得到障礙物的位置、距離、尺寸等信息。改進的OPTICS算法則不再受Eps的約束，而且可以準確分辨出噪點，增加了障礙物提取的準確性。提出的算法可以有效感知無人駕駛車輛前方可行駛區(qū)域的信息，為無人駕駛決策層提供有效信息，同時也提高了無人駕駛車的安全性。
參考文獻
[1] DAHLKAMP H，KAEHLER A，BRADSKI G.Self-supervised monocular road detection in desert terrain[C].Proceedings of Robotics：Science and Systems.Philadelphia：MIT Press，2006：115-121.
[2] 王欣，李高，朱萬力，等.并聯(lián)混合動力汽車能量管理建模及優(yōu)化研究[J].控制工程，2014(3)：357-360.
[3] 楊象軍.基于四線激光雷達的道路檢測與跟蹤[D].杭州：浙江大學，2013．
[4] 劉梓，唐振民，任明武.基于3D激光雷達的實時道路邊界檢測算法[J].華中科技大學學報(自然科版)，2011(S2)：351-354.
[5] 曾依靈，許洪波，白碩.改進的OPTICS算法及其在文本聚類中的應用[J].中文信息學報，2008(1)：51-55，60.
[6] 莊秀華.基于單線激光雷達的障礙物檢測與跟蹤研究[D].長沙：湖南大學，2014.
[7] 黨秋月，陸月明.基于OPTICS可達圖的自動識別簇方法[J].計算機應用，2012(S2)：19-21，47.
[8] 王品，黃焱.改進的OPTICS算法在調制識別中的應用[J].計算機工程與應用，2011(16)：141-143.
[9] 孫天宇，孫煒，薛敏.OPTICS聚類與目標區(qū)域概率模型的多運動目標跟蹤[J].中國圖像圖形學報，2015(11)：1492-1499.
[10] 陳燕俐，洪龍，金達文，等.一種簡單有效的基于密度的聚類分析算法[J].南京郵電學院學報，2005(4)：24-29.
[11] 段建民，李龍杰，鄭凱華.基于車載4線激光雷達的前方道路可行駛區(qū)域檢測[J].汽車技術，2016(2)：55-62.
[12] 鄒樂強.最小二乘法原理及其簡單應用[J].科技信息，2010(23)：282-283.
[13] 丁克良，沈云中，歐吉坤.整體最小二乘法直線擬合[J].遼寧工程技術大學學報(自然科學版)，2010(1)：44-47.
[14] 程玉民.移動最小二乘法研究進展與述評[J].計算機輔助工程，2009(2)：5-11，20.
[15] 段建民，鄭凱華，李龍杰，等.基于多層激光雷達的道路信息提取算法[J].控制工程，2016(4)：468-473.
作者信息：
段建民，王昶人，任 璐，劉 丹
（北京工業(yè)大學 信息學部，北京100124）