基于深度投影的三維點云目標分割和碰撞檢測

王張飛，劉春陽，2*，隋 新，楊 芳，馬喜強，陳立海，2

(1.河南科技大學 機電工程學院，河南 洛陽 471003；2.機械裝備先進制造河南省協同創新中心，河南 洛陽 471003；3.河南省機械設計及傳動系統重點實驗室，河南 洛陽 471003)

1 引 言

隨著無人駕駛技術的興起，三維激光雷達憑借其測距精度高、抗干擾能力強、全方位掃描等優點，越來越廣泛的應用在無人駕駛車輛中，成為無人駕駛車輛地形測繪、環境感知、三維目標識別、防碰撞檢測的重要傳感器[1-3]。

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

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

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

2 點云處理方法

2.1 點云處理流程

圖1為激光雷達點云目標分割和碰撞檢測總體流程圖。首先用激光雷達采集點云數據，然后使用體素化濾波去除外點和噪聲點，采用漸進式形態學濾波方法對地面點進行移除，建立非地面點云與深度投影圖像的映射關系，利用深度投影圖像的自適應角度閾值的方法對非地面點云進行目標分割，最后使用混合層次包圍盒算法進行碰撞檢測。

圖1 激光雷達數據處理流程圖Fig.1 Flowchart of LiDAR data processing

2.2 點云濾波

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

(1)

式中：floor函數為返回數字的下舍整數，xmax，ymax，zmax和xmin，ymin，zmin分別表示點云在激光雷達坐標系中三個坐標軸方向掃描的最遠和最近距離。

此外，無人駕駛車輛采集的點云數據需要對地面點和非地面點進行分類，采用漸進式形態學濾波方法可以有效去除地面點[13-14]，避免后續非地面點云目標分割和包圍盒碰撞檢測時發生干涉。

2.3 深度投影圖像建立

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

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

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

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

(2)

2.4 非地面點云目標分割

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

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

(3)

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

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

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

設定角度閾值為θ，當夾角β>θ時，認為兩點代表同一物體，根據不同的應用場景選擇不同的角度閾值θ，可以起到較好的分割效果。本文主要針對城市道路環境進行測試，使用激光雷達采集多組城市道路環境的點云數據，通過實驗發現，設定最小角度閾值θmin=0.114 rad時具有較好的點云分割效果。為了進一步提高點云目標分割的準確度，降低噪聲點的干擾，在點云目標分割算法中設置最大和最小點云數量閾值，去除不滿足數量要求的點云目標。

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

(4)

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

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

2.5 激光雷達和無人駕駛車輛的位置標定

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

圖5 激光雷達與無人駕駛車輛位置標定Fig.5 Lidar and unmanned vehicle position calibration

3 點云數據混合層次包圍盒算法描述

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

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

3.2 AABB與AABB包圍盒碰撞檢測

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

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

3.3 AABB與OBB包圍盒碰撞檢測

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

(5)

(6)

3.4 包圍盒碰撞檢測方法對比分析

如圖7所示，A表示無人駕駛車輛的AABB包圍盒，B表示道路轉彎處物體的OBB包圍盒，C表示道路轉彎處物體的AABB包圍盒，D表示無人駕駛車輛的運動軌跡。當包圍盒A與包圍盒C發生碰撞時，檢測包圍盒A與包圍盒B是否碰撞，如果包圍盒A與包圍盒B未發生碰撞，則該區域是安全的。反之，兩者發生碰撞。

4 實驗與分析

實驗環節使用的運算平臺為Jetson TX2，搭載NVIDIA的Tegra處理器和8 GB內存，算法采用Python編程實現，并使用OpenGL進行顯示。

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

(a)AABB and AABB

(b)AABB and OBB

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

(a)原始點云(a)Original point cloud

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

目標分割中常用的區域增長算法是通過判斷點云的法向量和曲率對點云進行聚類，歐式聚類算法是根據不同點云間的空間歐幾里得距離對點云聚類。圖9為區域增長算法、歐式聚類算法和本文所提出的基于深度投影圖像的自適應角度閾值的點云目標分割方法進行檢測的對比圖。

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

選取區域增長算法、歐式聚類算法和本文所提出的算法對點云目標進行分割，并通過混合層次包圍盒算法對分割后的點云目標進行碰撞檢測，在實驗數據中并未出現碰撞情況。

(a)區域增長點云目標分割算法(a)Region growing point cloud object segmentation algorithm

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

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

圖10為歐式聚類算法、區域增長算法和本文提出的方法點云數據處理時間的對比圖，歐式聚類算法和區域增長算法的平均運行時間分別為992 ms和1 734 ms。本文所提出的基于深度投影圖像的自適應角度閾值的點云目標分割方法平均運行時間為73 ms，時間效率上約為區域增長算法的23倍，并且相對歐式聚類算法和區域增長算法，該方法處理單幀點云數據的時間效率穩定，可滿足點云數據處理的實時性和穩定性要求。

圖10 分割算法的時間效率對比Fig.10 Time efficiency comparison of segmentation algorithms

為了分析點云目標分割算法的準確度，實驗中通過對激光雷達點云數據隨機選取442個目標進行人為手動標記，以P作為目標分割的準確率，通過點云目標分割算法準確分割點云目標的數量Sa占總目標數量的比例為：

(7)

對點云數據分別采用三種目標分割算法進行處理，計算每種算法正確分割的目標數量Sa，最后分別計算三種算法目標分割的準確率。本文所提算法的準確率為78.82%，歐式聚類算法的準確率為72.62%，區域增長聚類算法的準確率為75.11%，所提算法相對歐式聚類算法的準確率提高了約6%，相對區域增長算法的準確率提高了約4%，能夠更準確地對點云目標進行分割，取得了較好的效果。

5 結 論

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

點云目標分割研究主要根據點云空間幾何特征進行目標分割，絕大多數算法都是針對特定場景提出的，提高算法的自適應性將是未來研究的關鍵。