《電子技術(shù)應(yīng)用》
您所在的位置：首頁 > 嵌入式技術(shù) > 設(shè)計應(yīng)用 > 基于多層激光雷達的可行駛區(qū)域信息提取算法
基于多層激光雷達的可行駛區(qū)域信息提取算法
2017年電子技術(shù)應(yīng)用第10期
段建民，王昶人，任 璐，劉 丹
北京工業(yè)大學 信息學部，北京100124
摘要： 為了提取無人駕駛車前方可行駛區(qū)域信息，提出了一種基于多層激光雷達可行駛區(qū)域信息提取算法。首先，根據(jù)雷達返回數(shù)據(jù)的特征結(jié)合數(shù)據(jù)區(qū)間密度分布獲得路沿點集，并利用基于加權(quán)歐氏距離KNN改進的OPTICS算法對得到的路沿點聚類。然后，使用最小二乘法擬合出兩側(cè)路沿。最后，通過改進的OPTICS算法將路面上的障礙物點云進行聚類，并通過計算得到障礙物的位置、距離、尺寸等信息。利用數(shù)據(jù)區(qū)間密度分布法提取路沿點不受障礙物以及路面點的影響，而改進的OPTICS算法則不再受Eps的約束，并且可以準確分辨出噪點，解決了障礙物信息由于噪點而提取不準確的問題。實車實驗證明了算法的有效性和實時性。
中圖分類號： TN958.98
文獻標識碼： A
DOI：10.16157/j.issn.0258-7998.170392
中文引用格式： 段建民，王昶人，任璐，等. 基于多層激光雷達的可行駛區(qū)域信息提取算法[J].電子技術(shù)應(yīng)用，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.
Algorithm of driving area information extraction based on multi-layer lidar
Duan Jianmin，Wang Changren，Ren Lu，Liu Dan
Department of Information Science，Beijing University of Technology，Beijing 100124，China
Abstract： In order to extract the driving area information of the unmanned vehicle, an algorithm of driving area information extraction of the multi-layer lidar is proposed. First, the curb point set is obtained by combining the feature of the radar return data with the data interval density distribution and the resulting road-point clustering is achieved by using KNN-OPTICS algorithm based on weighted Euclidean distance KNN. Then, both sides of the curb are fitted using the least square method. Finally，the improved OPTICS algorithm is used to cluster the obstacle points on the road surface, and the position, distance and size of the obstacle are calculated. Using the method of data interval density distribution, the curb points will not be affected by the obstacle and the road surface. The improved OPTICS algorithm is no longer bound by Eps and can distinguish the noise accurately. It solves the problem that the obstacle information is inaccurate due to noise. Experimental results show that the algorithm is accurate and effective.
Key words : unmanned vehicle；multi-layer lidar；driving area；data density distribution；OPTICS algorithm

0 引言

    隨著社會的不斷發(fā)展，世界各國越來越多的學者開始對無人駕駛進行研究[1-2]，其中雷達技術(shù)更得到廣泛關(guān)注。文獻[3]利用路沿點數(shù)據(jù)斜率一致特性對路沿點進行提取，但該算法容易受路面點和障礙物點的影響并且要分層處理，所以準確性和實時性都不能達到要求。文獻[4]利用激光雷達返回高度數(shù)據(jù)的跳變提取路沿點，這種方法受障礙物影響很不穩(wěn)定。而對于聚類算法，由于激光雷達數(shù)據(jù)主要是成簇出現(xiàn)的，所以基于密度的聚類方法適合于激光雷達數(shù)據(jù)，其中OPTICS算法是典型的基于密度的聚類方法。文獻[5]利用結(jié)果序列重組織策略對OPTICS算法進行改進，但是在實際應(yīng)用中，對于激光雷達數(shù)據(jù)點突然出現(xiàn)的噪點無法區(qū)分，導(dǎo)致障礙物提取效果不準確。

    本文首先利用數(shù)據(jù)區(qū)間密度分布提取路沿點并通過最小二乘法擬合出路沿區(qū)分可行駛區(qū)域，然后在可行駛區(qū)域中利用改進的OPTICS算法對返回數(shù)據(jù)進行實時聚類。最后通過實車實驗驗證提出算法的有效性與實時性。

1 激光雷達數(shù)據(jù)預(yù)處理

1.1 激光雷達數(shù)據(jù)分析

    本文應(yīng)用德國IBEO公司生產(chǎn)的IBEO LUX 2010型四線激光雷達，該型號的雷達較單線激光雷達具有數(shù)據(jù)量大、檢測精度高、探測距離遠等優(yōu)勢[6]。其主要參數(shù)如表1所示。

ck3-b1.gif

    四線雷達返回的信息主要包含序號、掃描層數(shù)、距離以及位置坐標信息。其特性分析如下：

    (1)激光雷達是自左向右掃描的，每一幀返回的數(shù)據(jù)量基本相近；

    (2)激光雷達返回的數(shù)據(jù)是根據(jù)前方場景的變化而變化的，每個障礙物的掃描點的數(shù)目及形狀不一；

    (3)當激光雷達掃描到路沿時返回的數(shù)據(jù)特點是x軸坐標稀疏，y軸坐標緊密排列。

1.2 數(shù)據(jù)預(yù)處理

    為了檢測車輛前方的可行駛區(qū)域以及障礙物的信息，將激光雷達安放在車輛前方正中間的位置，根據(jù)以往經(jīng)驗，雷達的安裝高度設(shè)定為0.846 m。安裝位置示意圖如圖1所示。

ck3-t1.gif

ck3-gs1.gif

2 激光雷達數(shù)據(jù)處理方法

2.1 一維數(shù)據(jù)區(qū)間密度分布

    假設(shè)(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ū)間[ω，ξ]的密度，其公式為：

    ck3-gs2.gif

式中，ω和ξ為某個區(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)

    假設(shè)點P包含m個鄰近的最小半徑為min-distance(P)，那么P點的核心距離就可以定義為：

     ck3-gs3.gif

    定義2 可達距離(reach-distance，RD)

    假設(shè)P是點o鄰近點之一，那么P與o相關(guān)的可達距離定義式為：

    ck3-gs4.gif

    傳統(tǒng)的OPTICS聚類方法實現(xiàn)步驟如圖2所示，OPTICS算法的優(yōu)點是對輸入?yún)?shù)不敏感，但是輸入Eps與實際Eps差距較大時，聚類效果依然被影響，而且該算法對于噪點也不能區(qū)分。

ck3-t2.gif

2.3 基于加權(quán)歐氏距離的KNN圖

ck3-gs5-6.gif

    在實際的雷達數(shù)據(jù)中對雷達數(shù)據(jù)進行數(shù)據(jù)密度分布計算后提取各個峰值區(qū)域的點集，計算其橫、縱坐標的方差值，就可以計算出數(shù)據(jù)點間的加權(quán)歐氏距離。

    KNN即將實際雷達掃描到的數(shù)據(jù)點按照加權(quán)歐氏距離求取其距離矩陣Distk*k，然后將Distk*k中每一維按照升序排列形成sort(Distk*k)，最后將sort(Distk*k)中的每一維數(shù)據(jù)繪制成KNN圖。

2.4 最小二乘法擬合

    本文根據(jù)實驗道路特性，由于實驗道路兩側(cè)路沿點多呈線性分布，因此，使用最小二乘法對道路兩側(cè)提取的路沿點進行線性擬合。最小二乘法[12-14]是一種數(shù)學優(yōu)化方法，它通過最小化誤差的平方和尋找數(shù)據(jù)的最佳函數(shù)匹配。其針對線性擬合常用的表達式為y=kx+h，以下則是參數(shù)k和h的求解公式：

     ck3-gs7.gif

式中，n表示待擬合的點的個數(shù)，(xi，yi)為待擬合點的坐標值，k為斜率，h為截距。

3 可行駛區(qū)域信息提取方法

3.1 基于加權(quán)歐氏距離改進的OPTICS算法

    傳統(tǒng)的OPTICS算法雖然能克服其他傳統(tǒng)聚類算法的一些問題[15]，但其自身仍然有一些不足之處，如OPTICS在實際的篩選核心點的過程中是通過選取合適的Eps來確定核心點的位置，而由于Eps選取不當引入噪點，這樣大大降低了算法對噪點的敏感程度，使得聚類不準確。另外，如果盲目選擇Eps的范圍，同樣影響聚類效果。 

    為了改進OPTICS的不足之處，本文提出了基于加權(quán)歐氏距離KNN改進的OPTICS算法，此算法不需要輸入?yún)?shù)Eps，而是通過數(shù)據(jù)點間加權(quán)歐氏距離升序排序形成一個k-最近鄰圖(KNN)來確定聚類結(jié)果以及區(qū)分噪點。具體步驟如圖3所示。

ck3-t3.gif

    根據(jù)圖3所示，改進的OPTICS算法不需要選取Eps就可以直接進行聚類。在流程圖中基于加權(quán)歐氏距離KNN分離噪點的具體步驟如下：

    (1)求取每類數(shù)據(jù)點中每個點之間的加權(quán)歐式距離，形成距離矩陣Distk*k；

    (2)將距離矩陣中各維度距離按照升序排序，形成sort(Distk*k)；

    (3)由于噪點與其他點的距離大于一個閾值，所以就要判定這個點與其他點之間距離最小距離是否大于threshold，若大于，則該點為噪點。

3.2 基于一維數(shù)據(jù)區(qū)間密度分布的路沿提取算法

    通過對激光雷達返回的點云數(shù)據(jù)分析可知，在點云中包含有路面點、兩側(cè)路沿點、周圍花草景物點以及障礙物點。設(shè)定k個等距區(qū)間[ω，ξ]，在此區(qū)間中利用式(2)求取雷達數(shù)據(jù)點在每個區(qū)間的密度。以橫軸零為分界點，提取出兩側(cè)密度最大值及次大值所在區(qū)間。由經(jīng)驗知，路面點與路沿點高度差大約為20 cm，根據(jù)此高度差可消除路面點。得到路沿點后，將路沿點使用改進的OPTICS算法進行聚類，最后利用最小二乘法擬合得到路沿，并計算得到路沿信息。

3.3 可行駛區(qū)域內(nèi)障礙物信息提取

    通過得到的路沿信息，可判定出路面的路寬度。若假設(shè)左右路沿點的范圍分別為[a，b]和[c，d]，則根據(jù)橫向定界及式(8)得到可行駛區(qū)域的范圍：

     ck3-gs8.gif

式中，Croad為可行駛區(qū)域，Cnoise為周圍環(huán)境。

    根據(jù)無人駕駛車輛寬度信息和提取出可行駛區(qū)域的寬度信息結(jié)合，其表達式為：

ck3-gs9.gif

    提取出可行駛區(qū)域后，剩下的點為障礙物以及噪點。障礙物點主要有：行人、機動車、自行車等。障礙物的主要屬性信息表示為距離、角度、中心點等。利用改進的OPTICS算法將可行駛區(qū)域內(nèi)的障礙物進行聚類，并提取出每類障礙物的距離、角度以及障礙物中心點x、y、z坐標值。通過類內(nèi)計算得到障礙物的長度、寬度、距離、角度以及速度等信息。

4 實車實驗結(jié)果

4.1 實驗條件及平臺

    本文實驗平臺為BJUT-IV(Beijing University of Technology Intelligent Vehicle)自主研發(fā)的無人駕駛車，在車輛的前端正中的位置安裝IBEO-LUX四線激光雷達來采集實驗數(shù)據(jù)。雷達安裝高度為0.846 m。實驗的場景為校園內(nèi)道路，如圖4所示。

ck3-t4.gif

4.2 可行駛區(qū)域路沿提取實驗結(jié)果

    可行駛區(qū)域路沿提取實驗結(jié)果如圖5所示。

ck3-t5.gif

    圖4左側(cè)為實驗場景1，道路條件為無車輛通過。圖5(b)為原始數(shù)據(jù)點，原始數(shù)據(jù)點中包含路沿點、路面點，及周圍的樹木、鐵網(wǎng)。圖中雷達數(shù)據(jù)點分為4層，由圖中箭頭所指的點表示。圖5(a)為雷達返回數(shù)據(jù)坐標y值的數(shù)據(jù)密度分布直方圖，其中以零為分界點，4個范圍中靠近零的兩個區(qū)間為路沿點區(qū)間，而另外兩個區(qū)間為球場邊界。根據(jù)密度直方圖可以清晰地分析出左側(cè)路沿點所在范圍[-3.92，-3.7]，右側(cè)路沿點范圍為[6.4，6.8]。通過對區(qū)間密度的選取，就得到了如圖5(c)所示的情況，圖中的兩列點則為通過基于一維數(shù)據(jù)區(qū)間密度提取出的結(jié)果。圖5(d)是將提取出的路沿點通過基于加權(quán)歐式距離的KNN改進的OPTICS算法進行聚類，圖中橢圓形框是為了清楚表示兩類的聚類結(jié)果。最后通過最小二乘法將兩側(cè)提取出的路沿點進行線性擬合，結(jié)果如圖5(e)所示。提取出的路沿結(jié)果顯示，道路的寬度為10.48 m，車輛左側(cè)與路沿距離為6.64 m，車輛右側(cè)與路沿距離為3.83 m。在實際的實驗場景中通過測量得到實際的道路寬度約為10.5 m，提取結(jié)果與實際寬度僅差0.02 m，路面寬度信息檢測率為99.8％，符合實際應(yīng)用需要。

4.3 可行駛區(qū)域障礙物提取實驗結(jié)果

    可行駛區(qū)域障礙物提取結(jié)果如圖6所示，圖4右側(cè)為實驗場景2，場景中有行人和汽車。圖6(a)為第47幀加權(quán)歐氏距離KNN圖，圖中稀疏部分為文中提到的噪點，其他部分為聚類效果。圖6(b)為車輛行駛過程中第47幀數(shù)據(jù)利用傳統(tǒng)OPTICS算法檢測出路面的障礙物的情況。從圖中可以看出，由于在雷達掃描過程中第3層數(shù)據(jù)出現(xiàn)噪點，所以影響了聚類效果，導(dǎo)致聚類準確性降低。而圖6(c)為第47幀數(shù)據(jù)利用基于加權(quán)歐氏距離的KNN改進OPTICS算法的效果，算法可以避免路面噪點的影響，而且可以對障礙物準確的聚類，并且通過計算可以得到障礙物的主要屬性，檢測到行人的長度length=0.1 m，寬度為width=0.3 m，檢測到車輛的長度為length=3.3 m，寬度為width=1.7 m，包括雷達距離前方障礙物的距離，檢測結(jié)果與實際測量尺寸基本相符，滿足了檢測要求。

ck3-t6.gif

    圖6(d)為第45幀傳統(tǒng)OPTICS算法檢測結(jié)果，圖中將路面噪點當作障礙物，影響了聚類準確性。圖6(e)為第45幀數(shù)據(jù)利用改進OPTICS算法，效果良好。通過以上實驗結(jié)果可以證明，本文提出的可行駛區(qū)域提取算法的有效性與實時性都得到提高。

5 結(jié)束語

    本文提出的可行駛區(qū)域信息提取算法包括可行駛區(qū)域路沿提取和障礙物提取，在路沿提取中，利用一維數(shù)據(jù)區(qū)間密度分布對雷達數(shù)據(jù)進行界定，并通過界定范圍提取路沿點，這種方法根據(jù)數(shù)據(jù)密度提取路沿點排除了路面障礙物對路沿點提取的影響，并且對多層數(shù)據(jù)同時處理，減少了復(fù)雜度。通過基于加權(quán)歐氏距離的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算法及其在文本聚類中的應(yīng)用[J].中文信息學報，2008(1)：51-55，60.

[6] 莊秀華.基于單線激光雷達的障礙物檢測與跟蹤研究[D].長沙：湖南大學，2014.

[7] 黨秋月，陸月明.基于OPTICS可達圖的自動識別簇方法[J].計算機應(yīng)用，2012(S2)：19-21，47.

[8] 王品，黃焱.改進的OPTICS算法在調(diào)制識別中的應(yīng)用[J].計算機工程與應(yīng)用，2011(16)：141-143.

[9] 孫天宇，孫煒，薛敏.OPTICS聚類與目標區(qū)域概率模型的多運動目標跟蹤[J].中國圖像圖形學報，2015(11)：1492-1499.

[10] 陳燕俐，洪龍，金達文，等.一種簡單有效的基于密度的聚類分析算法[J].南京郵電學院學報，2005(4)：24-29.

[11] 段建民，李龍杰，鄭凱華.基于車載4線激光雷達的前方道路可行駛區(qū)域檢測[J].汽車技術(shù)，2016(2)：55-62.

[12] 鄒樂強.最小二乘法原理及其簡單應(yīng)用[J].科技信息，2010(23)：282-283.

[13] 丁克良，沈云中，歐吉坤.整體最小二乘法直線擬合[J].遼寧工程技術(shù)大學學報(自然科學版)，2010(1)：44-47.

[14] 程玉民.移動最小二乘法研究進展與述評[J].計算機輔助工程，2009(2)：5-11，20.

[15] 段建民，鄭凱華，李龍杰，等.基于多層激光雷達的道路信息提取算法[J].控制工程，2016(4)：468-473.



作者信息：

段建民，王昶人，任  璐，劉  丹

（北京工業(yè)大學 信息學部，北京100124）

此內(nèi)容為AET網(wǎng)站原創(chuàng)，未經(jīng)授權(quán)禁止轉(zhuǎn)載。