基于DBSCAN聚類算法的激光掃描雷達可視化障礙物檢測

張雨晨

北方工業大學城市道路交通智能控制技術北京市重點實驗室，北京 100043

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

1 激光掃描雷達數據采集

障礙物檢測的難點是如何快速、準確的找到障礙，系統通過Velodyne公司的VLP-16三維激光雷達采集數據，VLP-16三維激光雷達如圖1所示。

圖1 VLP-16三維激光雷達實物圖

1.1 雷達簡介

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

表1 VLP-16三維激光雷達性能指標

1.2 數據采集并解析

VLP-16三維激光雷達采集的環境信息通過UDP（User Datagram Protocol）協議傳輸到上位機平臺，數據包（Data Packet ）結構如圖2所示，激光掃描雷達每次接收的一個數據包由占42個字節的協議頭（Header）、12個數據塊（Data Block）、時間戳（Time Stamp）、出廠標志（Factory Bytes）組成，VLP-16三維激光雷達出廠標志為固定值22h。

圖2 數據包結構

每一個完整的數據包包含12個數據塊，數據塊結構如圖3所示，來自16個激光發射器的數據信息包含在一個數據塊中，每個數據塊只返回一個水平方位角信息（Azimuth N），返回16個垂直方位角信息，將激光掃描雷達所在點上下的15°分為16個空間角度。解析數據包的旋轉角度、測量距離和報告校準反射率，得出水平方位角及垂直方位角。

圖3 數據塊格式

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

圖4 三維空間建模

1.3 空間環境搭建

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

圖5 三維立體空間搭建

2 雷達數據可視化上位機軟件搭建

數據可視化，即以數據為視角看待世界，清晰有效地傳達與溝通信息，直觀清晰地看出障礙物的大小，障礙物數據可視化主要使用dbscan算法和python編程語言中的matplotlib庫實現，通過Pyqt創建一個GUI（圖形用戶界面）應用程序。

2.1 dbscan算法

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

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)距離不大于??的所有樣本。

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

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

密度可達density-reachable：對于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密度直達，則稱xj(x→j)由xi(x→i)密度可達，記作xi(x→i)～＞xj(x→j)。

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

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

圖6 DBSCAN聚類算法示意圖

2.1.2 dbscan算法聚類過程

DBSCAN聚類算法聚類過程如圖7所示，首先初始化數據集和搜索集，然后依次遍歷數據集中未歸類的節點，檢查數據集是否遍歷完畢，若遍歷完畢則聚類完成；若數據集未完成遍歷，則判斷未歸類節點是否為核心對象，若為核心對象，則將未歸類節點的鄰域對象放入搜索集，接下來遍歷搜索集中未歸類的點，遍歷完成后判斷該點是否為核心對象，若為核心對象，則把該點的鄰域對象放入搜索集中，將此兩點視為同一類，繼續進入下一個聚類過程，直到數據集遍歷完成，結束聚類。

圖7 DBSCAN聚類算法執行流程圖

2.2 上位機軟件搭建

使用pyqt5對上位機進行頁面布局，設計障礙物可視化區以及障礙物距離顯示區，對VLP-16三維激光雷達前后5m，上下1m的空間進行障礙物掃描檢測。實際設計的圖形界面如圖8所示，橫坐標為水平位置顯示，單位長度為2m，縱坐標為豎直位置顯示，單位長度為0.25m。

圖8 上位機圖形界面示意圖

3 實際檢測障礙物實驗并分析結果

本文根據實際情況搭建系統測試環境，驗證VLP-16三維激光雷達采集數據并實現可視化的運行效果。在實驗VLP-16三維激光雷達前方放置兩塊相同的目標木板，上位機顯示如圖9所示，該雷達可以精準的掃描區分出不同障礙物，并實時顯示其大小和位置，周圍的障礙物點為實驗場空間中的其余障礙物，更可以證明VLP-16三維激光雷達的準確性。

圖9 上位機障礙物顯示

多次改變其周圍環境，觀測上位機的障礙物顯示情況，如表2所示。在周圍環境復雜度不同的情況下進行障礙物檢測，分別對比障礙物距離精度、聚類程度、顯示實時性等特性。實驗結果表明，即使在高度復雜的環境中，該設計也能很好地完成障礙物檢測，達到高精度、實時顯示的目的。

表2 不同環境下障礙物檢測結果

4 結語

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