基于深度投影的三維點(diǎn)云目標(biāo)分割和碰撞檢測(cè)

王張飛，劉春陽，2*，隋 新，楊 芳，馬喜強(qiáng)，陳立海，2

(1.河南科技大學(xué) 機(jī)電工程學(xué)院，河南 洛陽 471003；2.機(jī)械裝備先進(jìn)制造河南省協(xié)同創(chuàng)新中心，河南 洛陽 471003；3.河南省機(jī)械設(shè)計(jì)及傳動(dòng)系統(tǒng)重點(diǎn)實(shí)驗(yàn)室，河南 洛陽 471003)

1 引 言

隨著無人駕駛技術(shù)的興起，三維激光雷達(dá)憑借其測(cè)距精度高、抗干擾能力強(qiáng)、全方位掃描等優(yōu)點(diǎn)，越來越廣泛的應(yīng)用在無人駕駛車輛中，成為無人駕駛車輛地形測(cè)繪、環(huán)境感知、三維目標(biāo)識(shí)別、防碰撞檢測(cè)的重要傳感器[1-3]。

激光雷達(dá)采集的三維點(diǎn)云具有無序性和稀疏性特點(diǎn)[4]，對(duì)三維點(diǎn)云進(jìn)行聚類分割是后續(xù)碰撞檢測(cè)的關(guān)鍵。目前常用的基于特征對(duì)點(diǎn)云分割的方法，通常在三維空間中構(gòu)建復(fù)雜的幾何特征，然后根據(jù)聚類算法對(duì)點(diǎn)云進(jìn)行分割，這類方法雖然可以取得較好的分割效果，但是計(jì)算時(shí)間過長，往往不能滿足點(diǎn)云分割的實(shí)時(shí)性要求[5-6]。DBSCAN(Density-Based Spatial Clustering of Applications with Noise)算法是經(jīng)典的基于密度的聚類方法，通過指定鄰域半徑和最小數(shù)據(jù)點(diǎn)閾值對(duì)點(diǎn)云進(jìn)行聚類，但在密度不均勻集上的聚類質(zhì)量不高。為了提升點(diǎn)云目標(biāo)分割的準(zhǔn)確性，秦佳睿等[7]提出一種自適應(yīng)選擇局部半徑的密度聚類算法，通過確定密度峰值點(diǎn)，自適應(yīng)選擇聚類的局部鄰域半徑；Bogoslavskyi等[8]利用深度圖像角度值進(jìn)行點(diǎn)云目標(biāo)分割，通過掃描線中的角度差判斷是否為同一物體；劉志青等[9]提出信息向量機(jī)對(duì)LiDAR點(diǎn)云數(shù)據(jù)分類的方法，點(diǎn)云目標(biāo)分割的準(zhǔn)確度較高，但分割時(shí)間效率仍有提升空間。

在無人駕駛汽車的目標(biāo)檢測(cè)中，對(duì)物體間的碰撞檢測(cè)是一項(xiàng)重要任務(wù)，其中，包圍盒算法是一種較為常用的方法，用體積較大而幾何特征簡單的包圍盒近似描述復(fù)雜的幾何對(duì)象，只需對(duì)包圍盒重疊的對(duì)象進(jìn)行進(jìn)一步碰撞檢測(cè)，該方法在滿足測(cè)量精度要求的前提下，大大減少了運(yùn)算時(shí)間[10]。目前主要研究的三維點(diǎn)云包圍盒包括軸對(duì)齊包圍盒 (Axis-Aligned Bounding Box， AABB)和有向包圍盒 (Oriented Bounding Box， OBB)等，然而這些包圍盒在碰撞檢測(cè)速度和精度上往往相互矛盾。

本文提出一種基于深度投影的點(diǎn)云目標(biāo)實(shí)時(shí)分割方法，首先對(duì)原始點(diǎn)云進(jìn)行預(yù)處理，去除噪聲點(diǎn)和地面點(diǎn)，然后進(jìn)行深度投影，采用廣度優(yōu)先搜索法搜索臨近點(diǎn)，根據(jù)激光雷達(dá)和不同點(diǎn)云之間的角度對(duì)目標(biāo)進(jìn)行分割，利用自適應(yīng)角度閾值的方法，根據(jù)不同的激光雷達(dá)掃描范圍設(shè)定不同的角度閾值，提高點(diǎn)云目標(biāo)分割的準(zhǔn)確性和實(shí)時(shí)性。最后使用混合層次包圍盒算法對(duì)分割后的點(diǎn)云目標(biāo)進(jìn)行碰撞檢測(cè)，采用AABB包圍盒算法快速濾除相距較遠(yuǎn)且不可能碰撞的對(duì)象，對(duì)于AABB包圍盒存在相交的對(duì)象，則進(jìn)一步采用緊密性較好的OBB包圍盒檢測(cè)碰撞狀態(tài)，大大提高了碰撞檢測(cè)的精度和效率。

2 點(diǎn)云處理方法

2.1 點(diǎn)云處理流程

圖1為激光雷達(dá)點(diǎn)云目標(biāo)分割和碰撞檢測(cè)總體流程圖。首先用激光雷達(dá)采集點(diǎn)云數(shù)據(jù)，然后使用體素化濾波去除外點(diǎn)和噪聲點(diǎn)，采用漸進(jìn)式形態(tài)學(xué)濾波方法對(duì)地面點(diǎn)進(jìn)行移除，建立非地面點(diǎn)云與深度投影圖像的映射關(guān)系，利用深度投影圖像的自適應(yīng)角度閾值的方法對(duì)非地面點(diǎn)云進(jìn)行目標(biāo)分割，最后使用混合層次包圍盒算法進(jìn)行碰撞檢測(cè)。

圖1 激光雷達(dá)數(shù)據(jù)處理流程圖Fig.1 Flowchart of LiDAR data processing

2.2 點(diǎn)云濾波

在無人駕駛車輛行駛過程中，激光雷達(dá)采集的三維點(diǎn)云通常是密度非均勻、非結(jié)構(gòu)化分布、包含有噪聲和外點(diǎn)的無序點(diǎn)云。使用體素化濾波方法，不僅可以減少點(diǎn)云數(shù)量，而且可以保持點(diǎn)云數(shù)據(jù)的形狀特征[11]。進(jìn)行體素化濾波首先需要確定點(diǎn)云數(shù)據(jù)的范圍，求出點(diǎn)云數(shù)據(jù)集的最小三維長方體包圍盒，將點(diǎn)云數(shù)據(jù)劃分到三維體素柵格中[12]，用體素內(nèi)所有點(diǎn)集pI的坐標(biāo)平均值替換當(dāng)前體素內(nèi)所有點(diǎn)集的坐標(biāo)值。假設(shè)體素大小為a，則點(diǎn)云在三個(gè)坐標(biāo)軸方向上的體素個(gè)數(shù)為：

(1)

式中：floor函數(shù)為返回?cái)?shù)字的下舍整數(shù)，xmax，ymax，zmax和xmin，ymin，zmin分別表示點(diǎn)云在激光雷達(dá)坐標(biāo)系中三個(gè)坐標(biāo)軸方向掃描的最遠(yuǎn)和最近距離。

此外，無人駕駛車輛采集的點(diǎn)云數(shù)據(jù)需要對(duì)地面點(diǎn)和非地面點(diǎn)進(jìn)行分類，采用漸進(jìn)式形態(tài)學(xué)濾波方法可以有效去除地面點(diǎn)[13-14]，避免后續(xù)非地面點(diǎn)云目標(biāo)分割和包圍盒碰撞檢測(cè)時(shí)發(fā)生干涉。

2.3 深度投影圖像建立

點(diǎn)云數(shù)據(jù)進(jìn)行體素化濾波和地面點(diǎn)去除后，根據(jù)非地面點(diǎn)云的空間幾何特征，基于深度投影圖像的自適應(yīng)角度閾值進(jìn)行點(diǎn)云目標(biāo)分割。首先將三維點(diǎn)云數(shù)據(jù)通過深度投影轉(zhuǎn)化為深度投影圖像[15]，通過激光雷達(dá)采集的點(diǎn)云數(shù)據(jù)可計(jì)算出每個(gè)激光束到目標(biāo)的距離值，然后將三維點(diǎn)云進(jìn)行深度投影，其中，深度投影圖像的每個(gè)像素點(diǎn)存儲(chǔ)了激光雷達(dá)與掃描對(duì)象之間的空間距離值，深度投影圖像的行數(shù)Rr取決于垂直方向上激光器的數(shù)目，深度投影圖像的列數(shù)Rc取決于激光雷達(dá)水平角度的分辨率[8]。三維點(diǎn)云與深度投影圖像之間的映射關(guān)系如圖2所示。

(a)原始點(diǎn)云(a)Original point cloud(b)深度投影圖像(b)Depth projection image

(c)場(chǎng)景圖(c)Scene map圖2 三維點(diǎn)云投影到深度圖Fig.2 3D point cloud projection to depth map

三維點(diǎn)云空間直角坐標(biāo)點(diǎn)(x，y，z)可通過坐標(biāo)變換轉(zhuǎn)化為深度投影圖像二維坐標(biāo)點(diǎn)(R，C)，轉(zhuǎn)化公式為：

(2)

2.4 非地面點(diǎn)云目標(biāo)分割

三維點(diǎn)云轉(zhuǎn)化為深度投影圖像后，根據(jù)深度投影圖像計(jì)算激光雷達(dá)與不同點(diǎn)云之間的角度值。圖3(a)為激光雷達(dá)掃描線與不同點(diǎn)云之間的角度示意圖，假設(shè)激光雷達(dá)位于O點(diǎn)，掃描線OA，OB表示激光束與物體相交于A，B兩點(diǎn)，OA和AB之間的夾角為β，點(diǎn)A和點(diǎn)B之間的連線可估計(jì)掃描對(duì)象的表面[16]。如圖3(b)所示，兩個(gè)相鄰物體已被標(biāo)注為不同的顏色(彩圖見期刊電子版)，當(dāng)三維激光雷達(dá)掃描周圍環(huán)境時(shí)，在同一物體上點(diǎn)云分布較為密集，兩個(gè)相鄰點(diǎn)A和B到激光雷達(dá)的距離差值較小，所以β角度較大，而相鄰物體之間，由于存在間隔，兩個(gè)相鄰點(diǎn)A和B(點(diǎn)A和B分別取自兩個(gè)相鄰物體)到激光雷達(dá)的距離差值較大，所以β角度較小。因此，基于激光雷達(dá)與不同點(diǎn)云之間的角度值β可以判斷是否為同一物體。OA和AB之間夾角β的計(jì)算公式為：

β=arctan(|BH|/|HA|)= arctan((d2sinα)/(d1-d2cosα))，

(3)

式中：α為掃描線OA和OB之間的夾角，d2和d1分別為OA和OB的距離。

(a)點(diǎn)云之間的角度(a)Angle between point clouds

(b)相鄰點(diǎn)云目標(biāo)分割(b)Adjacent point cloud object segmentation圖3 點(diǎn)云之間的角度和點(diǎn)云目標(biāo)分割示意圖Fig.3 Angle between point clouds and point cloud object segmentation

設(shè)定角度閾值為θ，當(dāng)夾角β>θ時(shí)，認(rèn)為兩點(diǎn)代表同一物體，根據(jù)不同的應(yīng)用場(chǎng)景選擇不同的角度閾值θ，可以起到較好的分割效果。本文主要針對(duì)城市道路環(huán)境進(jìn)行測(cè)試，使用激光雷達(dá)采集多組城市道路環(huán)境的點(diǎn)云數(shù)據(jù)，通過實(shí)驗(yàn)發(fā)現(xiàn)，設(shè)定最小角度閾值θmin=0.114 rad時(shí)具有較好的點(diǎn)云分割效果。為了進(jìn)一步提高點(diǎn)云目標(biāo)分割的準(zhǔn)確度，降低噪聲點(diǎn)的干擾，在點(diǎn)云目標(biāo)分割算法中設(shè)置最大和最小點(diǎn)云數(shù)量閾值，去除不滿足數(shù)量要求的點(diǎn)云目標(biāo)。

由于激光雷達(dá)點(diǎn)云數(shù)據(jù)的密度會(huì)隨著掃描距離的變化而變化，掃描距離近的點(diǎn)云密度較高，掃描距離遠(yuǎn)的點(diǎn)云密度較低，所以在同一應(yīng)用場(chǎng)景下，角度閾值θ不應(yīng)是固定值，而應(yīng)是隨著掃描距離而變化的自適應(yīng)參數(shù)。本文根據(jù)激光雷達(dá)掃描距離進(jìn)行分段，如圖4所示，根據(jù)不同的掃描距離設(shè)定不同的角度閾值，最終利用回歸分析掃描距離和角度閾值的關(guān)系建立回歸方程。通過回歸方程，自適應(yīng)角度閾值θ為：

(4)

式中：l為激光雷達(dá)掃描距離，由于激光雷達(dá)掃描距離有效范圍為0～100 m，所以，0

圖4 激光雷達(dá)掃描距離和角度閾值Fig.4 Lidar scan distances and angle thresholds

2.5 激光雷達(dá)和無人駕駛車輛的位置標(biāo)定

激光雷達(dá)與無人駕駛車輛位置的標(biāo)定過程，實(shí)際上是求解激光雷達(dá)坐標(biāo)系與車輛坐標(biāo)系之間的坐標(biāo)變換矩陣[17-18]，本文將激光雷達(dá)安裝在車輛的頂部位置，并標(biāo)定激光雷達(dá)與車輛坐標(biāo)系方向相一致，如圖5所示，激光雷達(dá)的坐標(biāo)系的x軸指向車頭，z軸垂直車身向上，y軸與x，z軸相互垂直。因此，無人駕駛車輛只需要構(gòu)建AABB包圍盒。為起到預(yù)防碰撞的效果，可將無人駕駛汽車包圍盒按一定比例進(jìn)行放大，生成體積較大的包圍盒。

圖5 激光雷達(dá)與無人駕駛車輛位置標(biāo)定Fig.5 Lidar and unmanned vehicle position calibration

3 點(diǎn)云數(shù)據(jù)混合層次包圍盒算法描述

3.1 混合層次包圍盒算法流程概述

在預(yù)處理階段，采用自頂向下的方法為幾何對(duì)象構(gòu)建包圍盒層次二叉樹[19]，具體分為兩層，分別是X層的AABB包圍盒和Y層的OBB包圍盒，三維激光雷達(dá)和無人駕駛車輛標(biāo)定在同一坐標(biāo)系下，且坐標(biāo)軸方向相同，所以無人駕駛車輛只需構(gòu)建AABB包圍盒，對(duì)檢測(cè)對(duì)象分別構(gòu)建AABB和OBB包圍盒。本文所采用的混合層次包圍盒算法，在碰撞檢測(cè)階段，對(duì)同一物體最多進(jìn)行兩次包圍盒檢測(cè)：AABB與AABB包圍盒碰撞檢測(cè)、AABB與OBB包圍盒碰撞檢測(cè)。

3.2 AABB與AABB包圍盒碰撞檢測(cè)

AABB包圍盒的各軸方向與坐標(biāo)軸的方向平行，所以AABB碰撞檢測(cè)只需要判斷包圍盒在三個(gè)坐標(biāo)軸上投影是否相交，若三個(gè)軸上的投影都相交，則認(rèn)為發(fā)生碰撞[20]。否則，認(rèn)為不發(fā)生碰撞，最多需要判斷3次。碰撞檢測(cè)效果如圖6所示。

圖6 AABB與AABB包圍盒碰撞檢測(cè)Fig.6 AABB and AABB bounding box collision detection

3.3 AABB與OBB包圍盒碰撞檢測(cè)

AABB和OBB包圍盒采用分離軸定理進(jìn)行碰撞檢測(cè)[21]，假設(shè)存在包圍盒A和B，其中，Ai，Bi(i=1，2，3)分別是A，B兩個(gè)包圍盒長、寬、高的一半，Ci，Di(i=1，2，3)分別是包圍盒A，B長、寬、高的單位向量，T是兩包圍盒中心的方向向量，L是分離軸的方向向量[22]。φA和φB分別是包圍盒A和B長、寬、高的一半在L上投影距離相加的和。A，B兩個(gè)包圍盒在分離軸上的投影距離為|T·L|。則有：

(5)

(6)

3.4 包圍盒碰撞檢測(cè)方法對(duì)比分析

如圖7所示，A表示無人駕駛車輛的AABB包圍盒，B表示道路轉(zhuǎn)彎處物體的OBB包圍盒，C表示道路轉(zhuǎn)彎處物體的AABB包圍盒，D表示無人駕駛車輛的運(yùn)動(dòng)軌跡。當(dāng)包圍盒A與包圍盒C發(fā)生碰撞時(shí)，檢測(cè)包圍盒A與包圍盒B是否碰撞，如果包圍盒A與包圍盒B未發(fā)生碰撞，則該區(qū)域是安全的。反之，兩者發(fā)生碰撞。

4 實(shí)驗(yàn)與分析

實(shí)驗(yàn)環(huán)節(jié)使用的運(yùn)算平臺(tái)為Jetson TX2，搭載NVIDIA的Tegra處理器和8 GB內(nèi)存，算法采用Python編程實(shí)現(xiàn)，并使用OpenGL進(jìn)行顯示。

為驗(yàn)證本文所提出的點(diǎn)云目標(biāo)分割和碰撞檢測(cè)算法的準(zhǔn)確性和實(shí)時(shí)性，實(shí)驗(yàn)中使用KITTI公開的Velodyne-64線激光雷達(dá)數(shù)據(jù)集作為算法測(cè)試樣本，從數(shù)據(jù)集中隨機(jī)抽取210幀點(diǎn)云數(shù)據(jù)進(jìn)行試驗(yàn)，獲取的原始點(diǎn)云數(shù)據(jù)如圖8(a)所示。對(duì)點(diǎn)云數(shù)據(jù)進(jìn)行預(yù)處理，去除噪聲點(diǎn)和地面點(diǎn)的效果如圖8(b)所示，地面點(diǎn)去除效果比較明顯。

(a)AABB and AABB

(b)AABB and OBB

(c)Proposed algorithm圖7 包圍盒碰撞檢測(cè)對(duì)比分析Fig.7 Contrast analysis of bounding box collision detection

(a)原始點(diǎn)云(a)Original point cloud

(b)去除地面點(diǎn)和噪聲點(diǎn)(b)Ground point and noise point extraction圖8 點(diǎn)云數(shù)據(jù)預(yù)處理Fig.8 Point cloud data preprocessing

目標(biāo)分割中常用的區(qū)域增長算法是通過判斷點(diǎn)云的法向量和曲率對(duì)點(diǎn)云進(jìn)行聚類，歐式聚類算法是根據(jù)不同點(diǎn)云間的空間歐幾里得距離對(duì)點(diǎn)云聚類。圖9為區(qū)域增長算法、歐式聚類算法和本文所提出的基于深度投影圖像的自適應(yīng)角度閾值的點(diǎn)云目標(biāo)分割方法進(jìn)行檢測(cè)的對(duì)比圖。

在點(diǎn)云目標(biāo)分割過程中，區(qū)域增長算法和歐式聚類算法較為依賴參數(shù)值的設(shè)定，圖9(a)中將激光雷達(dá)附近的汽車分割成多個(gè)目標(biāo)，出現(xiàn)過分割問題，如①所框選的目標(biāo)所示；圖9(b)中將距離激光雷達(dá)較遠(yuǎn)的汽車分割成多個(gè)目標(biāo)，并出現(xiàn)多處過分割問題，如①、②和③處所框選的目標(biāo)所示；而本文所提出的方法較好地分割了周圍點(diǎn)云目標(biāo)，如圖9(c)所示，其中①為柱子、②為無人駕駛汽車包圍盒、③為汽車。

選取區(qū)域增長算法、歐式聚類算法和本文所提出的算法對(duì)點(diǎn)云目標(biāo)進(jìn)行分割，并通過混合層次包圍盒算法對(duì)分割后的點(diǎn)云目標(biāo)進(jìn)行碰撞檢測(cè)，在實(shí)驗(yàn)數(shù)據(jù)中并未出現(xiàn)碰撞情況。

(a)區(qū)域增長點(diǎn)云目標(biāo)分割算法(a)Region growing point cloud object segmentation algorithm

(b)歐式聚類算法(b)European clustering algorithm

(c)本文所提點(diǎn)云目標(biāo)分割算法(c)Point cloud object segmentation algorithm圖9 點(diǎn)云目標(biāo)分割和碰撞檢測(cè)效果Fig.9 Point cloud target segmentation and collision detection effects

圖10為歐式聚類算法、區(qū)域增長算法和本文提出的方法點(diǎn)云數(shù)據(jù)處理時(shí)間的對(duì)比圖，歐式聚類算法和區(qū)域增長算法的平均運(yùn)行時(shí)間分別為992 ms和1 734 ms。本文所提出的基于深度投影圖像的自適應(yīng)角度閾值的點(diǎn)云目標(biāo)分割方法平均運(yùn)行時(shí)間為73 ms，時(shí)間效率上約為區(qū)域增長算法的23倍，并且相對(duì)歐式聚類算法和區(qū)域增長算法，該方法處理單幀點(diǎn)云數(shù)據(jù)的時(shí)間效率穩(wěn)定，可滿足點(diǎn)云數(shù)據(jù)處理的實(shí)時(shí)性和穩(wěn)定性要求。

圖10 分割算法的時(shí)間效率對(duì)比Fig.10 Time efficiency comparison of segmentation algorithms

為了分析點(diǎn)云目標(biāo)分割算法的準(zhǔn)確度，實(shí)驗(yàn)中通過對(duì)激光雷達(dá)點(diǎn)云數(shù)據(jù)隨機(jī)選取442個(gè)目標(biāo)進(jìn)行人為手動(dòng)標(biāo)記，以P作為目標(biāo)分割的準(zhǔn)確率，通過點(diǎn)云目標(biāo)分割算法準(zhǔn)確分割點(diǎn)云目標(biāo)的數(shù)量Sa占總目標(biāo)數(shù)量的比例為：

(7)

對(duì)點(diǎn)云數(shù)據(jù)分別采用三種目標(biāo)分割算法進(jìn)行處理，計(jì)算每種算法正確分割的目標(biāo)數(shù)量Sa，最后分別計(jì)算三種算法目標(biāo)分割的準(zhǔn)確率。本文所提算法的準(zhǔn)確率為78.82%，歐式聚類算法的準(zhǔn)確率為72.62%，區(qū)域增長聚類算法的準(zhǔn)確率為75.11%，所提算法相對(duì)歐式聚類算法的準(zhǔn)確率提高了約6%，相對(duì)區(qū)域增長算法的準(zhǔn)確率提高了約4%，能夠更準(zhǔn)確地對(duì)點(diǎn)云目標(biāo)進(jìn)行分割，取得了較好的效果。

5 結(jié) 論

本文針對(duì)無人駕駛車載激光雷達(dá)的點(diǎn)云目標(biāo)分割和碰撞檢測(cè)算法進(jìn)行研究，首先將采集的點(diǎn)云數(shù)據(jù)使用體素化濾波方法去除噪聲點(diǎn)，減少點(diǎn)云數(shù)量的同時(shí)，保持點(diǎn)云的形狀特征，再采用點(diǎn)云漸進(jìn)式形態(tài)學(xué)濾波方法去除地面點(diǎn)云，然后使用基于深度投影圖像的自適應(yīng)角度閾值的方法對(duì)點(diǎn)云目標(biāo)進(jìn)行分割，根據(jù)不同的點(diǎn)云掃描距離設(shè)置不同的角度閾值，有效降低了點(diǎn)云目標(biāo)的過分割問題，最后使用混合層次包圍盒算法對(duì)分割之后的點(diǎn)云進(jìn)行碰撞檢測(cè)。通過實(shí)驗(yàn)發(fā)現(xiàn)，本文所提出的點(diǎn)云目標(biāo)分割方法相對(duì)于區(qū)域增長算法，時(shí)間效率上提高了大約23倍，相對(duì)于歐式聚類算法，準(zhǔn)確率提升了約6%。通過混合層次包圍盒算法對(duì)分割后的點(diǎn)云目標(biāo)繪制包圍盒，并進(jìn)行碰撞檢測(cè)，相較于傳統(tǒng)包圍盒算法，混合層次包圍盒算法在滿足準(zhǔn)確度要求的前提下，大大提高了碰撞檢測(cè)時(shí)間效率。

點(diǎn)云目標(biāo)分割研究主要根據(jù)點(diǎn)云空間幾何特征進(jìn)行目標(biāo)分割，絕大多數(shù)算法都是針對(duì)特定場(chǎng)景提出的，提高算法的自適應(yīng)性將是未來研究的關(guān)鍵。