基于DBSCAN聚類算法的激光掃描雷達(dá)可視化障礙物檢測(cè)

張雨晨

北方工業(yè)大學(xué)城市道路交通智能控制技術(shù)北京市重點(diǎn)實(shí)驗(yàn)室，北京 100043

近年，人工智能時(shí)代的逐漸到來(lái)，無(wú)人駕駛技術(shù)高速發(fā)展，無(wú)人駕駛技術(shù)的安全性又一次被推到了風(fēng)口浪尖上，行駛的無(wú)人駕駛汽車具有許多關(guān)鍵性難題，例如，對(duì)周圍環(huán)境的感知、針對(duì)周圍環(huán)境情況做出預(yù)測(cè)等，障礙物檢測(cè)成為確保無(wú)人駕駛技術(shù)安全性的一個(gè)重要問題，只有實(shí)時(shí)并且精準(zhǔn)地完成障礙物的檢測(cè)才能確保無(wú)人駕駛車輛的安全問題。在周圍環(huán)境不明的情況下，有效的信息采集對(duì)無(wú)人駕駛汽車等自動(dòng)行駛機(jī)器人顯得尤為重要，無(wú)人駕駛其中一個(gè)核心的技術(shù)就是采用何種傳感器以及如何從傳感器信號(hào)中獲取有用的環(huán)境信息，并采取有效的信息處理技術(shù)，從而實(shí)現(xiàn)障礙物的檢測(cè)。目前，相關(guān)企業(yè)在障礙物檢測(cè)方面多使用熱成像紅外檢測(cè)、攝像頭檢測(cè)等檢測(cè)方法，這些技術(shù)存在數(shù)據(jù)量小、信息缺失、分辨率不高、抗干擾能力差、檢測(cè)數(shù)據(jù)傳輸?shù)膶?shí)時(shí)性不強(qiáng)等問題，所以提出使用16線激光掃描雷達(dá)來(lái)進(jìn)行障礙物信息檢測(cè)。

1 激光掃描雷達(dá)數(shù)據(jù)采集

障礙物檢測(cè)的難點(diǎn)是如何快速、準(zhǔn)確的找到障礙，系統(tǒng)通過Velodyne公司的VLP-16三維激光雷達(dá)采集數(shù)據(jù)，VLP-16三維激光雷達(dá)如圖1所示。

圖1 VLP-16三維激光雷達(dá)實(shí)物圖

1.1 雷達(dá)簡(jiǎn)介

VLP-16激光雷達(dá)是Velodyne公司生產(chǎn)的規(guī)格最小的雷達(dá)，可隨時(shí)上傳周圍障礙物的反射情況和距離，并且實(shí)現(xiàn)了雷達(dá)的轉(zhuǎn)速可調(diào)節(jié)。VLP-16激光雷達(dá)同時(shí)具有重量輕、易安裝等優(yōu)點(diǎn)，尤其適合安裝在小型智能車、機(jī)器人等小型設(shè)備上面。如表1所示，VLP-16激光雷達(dá)的檢測(cè)精度可達(dá)3cm以內(nèi)，最遠(yuǎn)可達(dá)100m的遠(yuǎn)距離探測(cè)，掃描幀頻最高可達(dá)10Hz，每秒高達(dá)30萬(wàn)個(gè)點(diǎn)數(shù)據(jù)檢測(cè)，水平視角360°全方位掃描，-15～15°的垂直視角可完成低空障礙物檢測(cè)。

表1 VLP-16三維激光雷達(dá)性能指標(biāo)

1.2 數(shù)據(jù)采集并解析

VLP-16三維激光雷達(dá)采集的環(huán)境信息通過UDP（User Datagram Protocol）協(xié)議傳輸?shù)缴衔粰C(jī)平臺(tái)，數(shù)據(jù)包（Data Packet ）結(jié)構(gòu)如圖2所示，激光掃描雷達(dá)每次接收的一個(gè)數(shù)據(jù)包由占42個(gè)字節(jié)的協(xié)議頭（Header）、12個(gè)數(shù)據(jù)塊（Data Block）、時(shí)間戳（Time Stamp）、出廠標(biāo)志（Factory Bytes）組成，VLP-16三維激光雷達(dá)出廠標(biāo)志為固定值22h。

圖2 數(shù)據(jù)包結(jié)構(gòu)

每一個(gè)完整的數(shù)據(jù)包包含12個(gè)數(shù)據(jù)塊，數(shù)據(jù)塊結(jié)構(gòu)如圖3所示，來(lái)自16個(gè)激光發(fā)射器的數(shù)據(jù)信息包含在一個(gè)數(shù)據(jù)塊中，每個(gè)數(shù)據(jù)塊只返回一個(gè)水平方位角信息（Azimuth N），返回16個(gè)垂直方位角信息，將激光掃描雷達(dá)所在點(diǎn)上下的15°分為16個(gè)空間角度。解析數(shù)據(jù)包的旋轉(zhuǎn)角度、測(cè)量距離和報(bào)告校準(zhǔn)反射率，得出水平方位角及垂直方位角。

圖3 數(shù)據(jù)塊格式

如圖4所示，采集出障礙物距離激光掃描雷達(dá)的距離信息后，在三維空間中建立立體模型，數(shù)據(jù)點(diǎn)距原點(diǎn)的距離為R，垂直夾角為W，水平夾角為a，數(shù)據(jù)點(diǎn)在三維立體空間模型中的X、Y、Z坐標(biāo)由公式（1）、（2）、（3）可計(jì)算得出。在得出障礙點(diǎn)在三維空間模型中的X坐標(biāo)、Y坐標(biāo)、Z坐標(biāo)后，數(shù)據(jù)采集完成。

圖4 三維空間建模

1.3 空間環(huán)境搭建

在空間中搭建一個(gè)10m×10m×2m立體空間，如圖5所示，該空間由100×100×20個(gè)小立方體組成，小立方體的長(zhǎng)寬高分別為10cm，即激光掃描雷達(dá)的檢測(cè)精度為10cm，符合實(shí)際障礙物檢測(cè)情況。以該三維立體空間的質(zhì)心為原點(diǎn)，若檢測(cè)到某小立方體處有障礙物，則填“1”，否則填“0”。至此，三維空間環(huán)境搭建完成，并且將所有采集到的障礙物信息填充到該三維空間模型中。

圖5 三維立體空間搭建

2 雷達(dá)數(shù)據(jù)可視化上位機(jī)軟件搭建

數(shù)據(jù)可視化，即以數(shù)據(jù)為視角看待世界，清晰有效地傳達(dá)與溝通信息，直觀清晰地看出障礙物的大小，障礙物數(shù)據(jù)可視化主要使用dbscan算法和python編程語(yǔ)言中的matplotlib庫(kù)實(shí)現(xiàn)，通過Pyqt創(chuàng)建一個(gè)GUI（圖形用戶界面）應(yīng)用程序。

2.1 dbscan算法

基于密度的空間聚類算法（Density-basedspatial clustering of application with noise， DBSCAN）——在數(shù)據(jù)空間中將簇看作是被低密度區(qū)域分隔開的高密度對(duì)象區(qū)域。

2.1.1 DBSCAN算法思想

DBSCAN基本概念如下：

??-鄰域：N?(xi)N?(x→i)={xj∈D|distance(xi,xj)x→j∈D|distance(x→i,x→j)≤?≤?}，N?(xi)N?(x→i)包含了樣本集DD中與xi(x→i)距離不大于??的所有樣本。

核心對(duì)象core object：若|N?(xi)N∈(x→i)|≥MinPts≥MinPts，則稱xi(x→i)是一個(gè)核心對(duì)象。即：若xi(x→i)的∈∈-鄰域中至少包含MinPtsMinPts個(gè)樣本，則稱xi(x→i)是一個(gè)核心對(duì)象。

密度直達(dá)directly density-reachable：若xi(x→i)是一個(gè)核心對(duì)象，且xj∈x→j∈N∈(xi)N∈(x→i)，則稱xj(x→j)由xi(x→i)密度直達(dá)，記作xi(x→i)-＞xj(x→j)。

密度可達(dá)density-reachable：對(duì)于xi(x→i)和xj(x→j)，若存在樣本序列（p0, p1, p2, ..., pm, pm+1, p→0, p→1, p→2, ..., p→m，p→m+1）， 其 中p0(p→0)=xi(x→i)，pm+1(p→m+1)=xj(x→j)，ps∈D, s=1, 2, ..., m, p→s∈D, s=1, 2, ..., m。如果ps+1(p→s+1)由ps, s=1, 2, ..., m, p→s, s=1, 2, ..., m密度直達(dá)，則稱xj(x→j)由xi(x→i)密度可達(dá)，記作xi(x→i)～＞xj(x→j)。

密度相連density-connected：對(duì)于xi(x→i)和xj(x→j)，若存在xk(x→k)，使得xi(x→i)和xj(x→j)均由xk(x→k)密度可達(dá)，則稱xj(x→j)由xi(x→i)密度相連，記作xi(x→i)～xj(x→j)。

DBSCAN聚類思想如圖6所示，??用一個(gè)相應(yīng)的半徑表示，設(shè)MinPts=3，請(qǐng)分析Q，M，P，S，O，R這5個(gè)樣本點(diǎn)之間的關(guān)系。根據(jù)以上概念知道：由于有標(biāo)記的各點(diǎn)M、P、O和R的Eps近鄰均包含3個(gè)以上的點(diǎn)，因此它們都是核對(duì)象；M是從P“直接密度可達(dá)”；而Q則是從M“直接密度可達(dá)”；基于上述結(jié)果，Q是從P“密度可達(dá)”；但P從Q無(wú)法“密度可達(dá)”(非對(duì)稱)。類似地，S和R從O是“密度可達(dá)”的；O、R和S均是“密度相連”的。顯然，DBSCAN聚類算法的目的是找到密度相連對(duì)象的最大集合。

圖6 DBSCAN聚類算法示意圖

2.1.2 dbscan算法聚類過程

DBSCAN聚類算法聚類過程如圖7所示，首先初始化數(shù)據(jù)集和搜索集，然后依次遍歷數(shù)據(jù)集中未歸類的節(jié)點(diǎn)，檢查數(shù)據(jù)集是否遍歷完畢，若遍歷完畢則聚類完成；若數(shù)據(jù)集未完成遍歷，則判斷未歸類節(jié)點(diǎn)是否為核心對(duì)象，若為核心對(duì)象，則將未歸類節(jié)點(diǎn)的鄰域?qū)ο蠓湃胨阉骷?，接下?lái)遍歷搜索集中未歸類的點(diǎn)，遍歷完成后判斷該點(diǎn)是否為核心對(duì)象，若為核心對(duì)象，則把該點(diǎn)的鄰域?qū)ο蠓湃胨阉骷校瑢⒋藘牲c(diǎn)視為同一類，繼續(xù)進(jìn)入下一個(gè)聚類過程，直到數(shù)據(jù)集遍歷完成，結(jié)束聚類。

圖7 DBSCAN聚類算法執(zhí)行流程圖

2.2 上位機(jī)軟件搭建

使用pyqt5對(duì)上位機(jī)進(jìn)行頁(yè)面布局，設(shè)計(jì)障礙物可視化區(qū)以及障礙物距離顯示區(qū)，對(duì)VLP-16三維激光雷達(dá)前后5m，上下1m的空間進(jìn)行障礙物掃描檢測(cè)。實(shí)際設(shè)計(jì)的圖形界面如圖8所示，橫坐標(biāo)為水平位置顯示，單位長(zhǎng)度為2m，縱坐標(biāo)為豎直位置顯示，單位長(zhǎng)度為0.25m。

圖8 上位機(jī)圖形界面示意圖

3 實(shí)際檢測(cè)障礙物實(shí)驗(yàn)并分析結(jié)果

本文根據(jù)實(shí)際情況搭建系統(tǒng)測(cè)試環(huán)境，驗(yàn)證VLP-16三維激光雷達(dá)采集數(shù)據(jù)并實(shí)現(xiàn)可視化的運(yùn)行效果。在實(shí)驗(yàn)VLP-16三維激光雷達(dá)前方放置兩塊相同的目標(biāo)木板，上位機(jī)顯示如圖9所示，該雷達(dá)可以精準(zhǔn)的掃描區(qū)分出不同障礙物，并實(shí)時(shí)顯示其大小和位置，周圍的障礙物點(diǎn)為實(shí)驗(yàn)場(chǎng)空間中的其余障礙物，更可以證明VLP-16三維激光雷達(dá)的準(zhǔn)確性。

圖9 上位機(jī)障礙物顯示

多次改變其周圍環(huán)境，觀測(cè)上位機(jī)的障礙物顯示情況，如表2所示。在周圍環(huán)境復(fù)雜度不同的情況下進(jìn)行障礙物檢測(cè)，分別對(duì)比障礙物距離精度、聚類程度、顯示實(shí)時(shí)性等特性。實(shí)驗(yàn)結(jié)果表明，即使在高度復(fù)雜的環(huán)境中，該設(shè)計(jì)也能很好地完成障礙物檢測(cè)，達(dá)到高精度、實(shí)時(shí)顯示的目的。

表2 不同環(huán)境下障礙物檢測(cè)結(jié)果

4 結(jié)語(yǔ)

本文提出了一種使用VLP-16三維激光雷達(dá)采集障礙物信息，并且使用圖形界面編程將障礙物信息實(shí)現(xiàn)可視化。主要解決了激光掃描雷達(dá)采集障礙物信息及使用DBSCAN聚類算法聚類的問題，為障礙物檢測(cè)提供了一種行之有效的思路。首先，建立與VLP-16三維激光雷達(dá)的通信，解析數(shù)據(jù)包的旋轉(zhuǎn)角度，測(cè)量距離等參數(shù)，然后由得到參數(shù)計(jì)算障礙物點(diǎn)X坐標(biāo)、Y坐標(biāo)、Z坐標(biāo)，將其位置標(biāo)記在建立的三維立體空間模型中，最后使用DBSCAN聚類算法完成障礙物點(diǎn)的聚類，顯示到搭建的上位機(jī)平臺(tái)。本文所述的障礙物檢測(cè)并顯示的方法具有數(shù)據(jù)采集速度快、分辨率高、抗干擾能力強(qiáng)等優(yōu)點(diǎn)。該障礙物檢測(cè)技術(shù)適合應(yīng)用到小型智能機(jī)器人、無(wú)人駕駛汽車等設(shè)備，卓有成效地推動(dòng)了無(wú)人駕駛技術(shù)的發(fā)展，一定程度地解決了無(wú)人駕駛的安全性問題，為障礙物檢測(cè)識(shí)別等提供了一個(gè)良好的范本。