基于改進DBSCAN算法的激光雷達水面目標檢測

葉 晟 徐海祥 馮 輝

(高性能船舶技術教育重點實驗室1) 武漢 430063) (武漢理工大學船海與能源動力工程學院2) 武漢 430063)

0 引 言

激光雷達具有測量精度高、響應速度快、抗干擾能力強、對環境全向感知，可以得到障礙目標的深度信息等優點，因此被廣泛應用于無人系統的感知領域，比如，無人機的道路勘測、地圖繪制，無人車領域的道路檢測、行人檢測、車輛檢測，無人艇自主靠離泊過程中對港口泊位的檢測等[1].激光雷達目標檢測可分為傳統方法的目標檢測和基于機器學習方法的目標檢測，其關鍵就是激光雷達點云的聚類.常用的聚類方法主要有基于劃分的方法，如K-Means算法[2-3]、基于(坡度、相似程度、曲率、曲面法向量等)區域增長的聚類算法[4-6]、基于空間距離遠近的歐式聚類算法[7-9]、具有噪聲的基于密度的聚類算法(density-based spatial clustering of applications with noise, DBSCAN)等.DBSCAN算法聚類時主要依靠數據的疏密程度對數據進行劃分，可以發現不同形狀的點云集合，對噪聲點不敏感，無需事先確定障礙物個數，因此被廣泛應用于激光雷達點云目標的檢測.

夏魯寧等[10]在DBSCAN的基礎上提出了SA-DBSCAN聚類算法，通過k-dist圖來選取鄰域值ε，通過繪圖求得噪聲值曲線與坐標軸第一象限平分線的交點橫坐標作為密度閾值Minpts.王光等[11]采用核密度估計確定鄰域值ε和密度閾值Minpts的合理區間，通過分析數據局部密度特點確定簇數，然后根據合理區間內的參數值進行聚類.蔡懷宇等[12]利用在地面上反射的激光雷達掃描線的分布特點，將激光雷達高度視為單位1，從而建立了一個ε表對點云進行聚類.宮銘錢等[13]根據三維激光雷達對立體物體的相鄰兩次掃描結果，計算掃描線的間隔乘以Minpts從而建立ε表，對激光雷達目標檢測.

文中提出了一種自適應參數的改進DBSCAN算法，在一定的密度閾值Minpts下，對每一個點云采取隨距離自適應增大的鄰域值ε，并設定一個合適的鄰域下限，這樣既保留了傳統的DBSCAN在近距離點云聚類時的優點，又能對遠距離的點云正確地聚類.通過實驗對比了傳統的DBSCAN算法和改進之后的DBSCAN算法對無人艇采集的障礙物點云數據聚類的性能.實驗結果表明，改進之后的DBSCAN聚類算法，能夠自適應地選取鄰域值ε和密度閾值Minpts兩個重要參數，對于無人艇采集的障礙物點云數據能夠實現較好的聚類效果.

1 傳統DBSCAN聚類算法

DBSCAN聚類算法針對的是點云的密度對點云進行聚類，其核心思想是根據點云的疏密程度，將點云密度超過密度閾值的點聚成類，將其他的低于密度閾值的點歸類成噪聲點.其主要步驟如下.

步驟1根據數據集特點選取合適的鄰域值ε和密度閾值Minpts，把所有數據點標記為未處理.

步驟2隨機的選擇一個點Pi，對Pi的ε鄰域內的點數進行統計.如果大于或等于Minpts，把Pi標記為核心點，并新建一個類別.以Pi為起點，尋找與Pi密度相連的點，找到密度相連點的最大集合.如果小于Minpts，把Pi標記為噪聲點.

步驟3選擇數據集中的另一個點，重復步驟2，直到所有的點標記為已處理.

傳統的DBSCAN算法在應用于激光雷達水面目標檢測時，有以下優缺點.

1)優點 ①可以對任意形狀點集聚類，發現不同形狀的目標 相較于K-means算法只能對凸數據集聚類、需要事先確定聚類目標個數的局限性，DBSCAN算法具有能夠對不同形狀的數據集聚類、無需事先確定障礙物個數的優點；②可以有效剔除數據集中的異常點，降低數據預處理的難度 在無人車應用中，在點云預處理時通常需要進行地面點云分割，以排除地面點云對目標檢測的干擾.而水面點云反射較少，使用DBSCAN算法聚類時，可以將少量的水面點云視為噪聲點進行剔除，不會對聚類結果造成影響，所以應用DBSCAN算法對水面激光雷達點云聚類時，無需進行水面點云分割，省去了復雜的點云預處理步驟；③近距離點云聚類效果好 激光雷達點云是一種密度隨著距離逐漸減小的不均勻數據集.而近距離部分的點云數據比較稠密，點云分布相對均勻，使用傳統DBSCAN算法聚類時，聚類效果好.

2)缺點 ①參數選擇困難 鄰域值ε和密度閾值Minpts的選取會相互影響，需要對其聯合調參，不同的參數組合對最后的聚類結果有較大的影響；②近距離的相鄰目標容易被欠分割 傳統DBSCAN算法選擇固定不變的鄰域值ε和密度閾值Minpts，在物體距離很近時，容易將它們聚類成同一物體，出現欠分割；③遠距離目標容易被漏檢 傳統的DBSCAN算法中，選取了一個固定的鄰域值ε和密度閾值Minpts，對于離激光雷達較遠的點云，這些點云明顯更為稀疏，其密度小于密度閾值Minpts，不滿足核心點的判定，因而容易被漏檢.

2 改進DBSCAN聚類算法

針對傳統DBSCAN算法在應用于激光雷達水面目標檢測時的缺點，提出一種自適應參數的改進DBSCAN算法.其核心思想如下：在一定的Minpts下，對于激光雷達的每一個點云選擇隨距離自適應增大的鄰域值ε，使得點云稀疏區域采用較大的鄰域值ε，從而保證對遠距離的點云完成聚類.設置一個鄰域值下限，相當于對近距離點云使用傳統DBSCAN算法聚類，這樣保留了傳統DBSCAN算法在近距離點云聚類上的優勢.

圖1為VLP-16激光雷達掃描線掃描示意圖，激光雷達掃面線掃描到擋板上時，相鄰的兩根掃描線的距離并不是相同的，相鄰兩根掃描線的間距與掃描線ID密切相關.而且，在同一掃描線上時，距離激光雷達越遠，點云越稀疏.因此，通過相鄰掃描線間距以及點云到激光雷達的距離計算點云的鄰域值ε.

圖1 VLP-16激光雷達掃描線掃描示意圖

為了計算每個點云的鄰域ε，首先計算相鄰掃描線的間距ε*，建立ε*列表：

以VLP-16激光雷達為例，設定激光雷達到擋板距離為單位1.已知VLP-16激光雷達水平放置時，每一條掃描線俯仰角從大到小排列為15°,13°,…,1°,-1°,…,-13°,-15°，見表1.

表1 掃描線ID與俯仰角對應關系

掃描線俯仰角與ID關系為

βi=17-2*i

(1)

式中：βi為掃描線俯仰角；i為掃描線ID.

相鄰掃描線間隔ε*等于掃描線在擋板上的反射點高度的差值，計算公式為

(2)

對于激光雷達點云中的任意一點P(x,y,z)，其鄰域值ε為

(3)

(4)

式中：λ為修正系數；ε*為相鄰掃描線間隔；k為點P的掃描線ID；ε0為鄰域值下限.

k可以通過求出點P與水平面夾角，查表1獲得.λ為修正系數，與激光雷達類型有關，文中使用雷達為VLP-16激光雷達，取λ=1.3.ε0為鄰域值下限，是一個固定的數值，其大小與激光雷達類型有關，可以通過統計近距離出現過分割或視為噪聲的目標點云，計算其鄰域值ε的最大值獲得，取ε0=0.23.ε0的設置主要為了防止距離激光雷達較近的點云的鄰域值過小，而導致點云被過分割或者被檢測為噪聲的情況.

統計數據集中每一個點ε鄰域內包含點的數量，并用其期望作為密度閾值Minpts.

(5)

式中：Pi為點i的ε鄰域內包含的點的個數；n為點云的總數.

改進的DBSCAN算法的流程圖見圖2.

圖2 改進DBSCAN算法流程圖

3 實驗結果與分析

為了驗證上述改進DBSCAN算法的有效性，使用無人艇采集的水面障礙物點云數據集為研究對象.以16 GB內存、i7-9750處理器、2.6 GHz主頻的計算機作為實驗平臺，并在Matlab2019a上編程實現.通過兩個不同場景，采用傳統DBSCAN算法和改進DBSCAN算法分別對點云聚類，并分析比較實驗結果.

圖3為原始點云和提取感興趣區域后的待處理點云，圖4a)為取ε=1，Minpts=40的傳統DBSCAN聚類結果，圖4b)為未設置鄰域值下限ε0的改進DBSACN聚類結果，圖4c)為設置鄰域值下限ε0的改進DBSCAN聚類結果.

圖3 原始點云和提取感興趣區域后的待處理點云

圖4 傳統和改進DBSCAN聚類結果

在該實驗場景下，包含有6個離激光雷達較近的障礙物，分別為：(-6,4,:)附近的障礙物1，(-2,4,:)附近的皮劃艇和劃皮劃艇的人作為障礙物2和3，在點(1,5,:)附近的障礙物4，在(2,5,:)附近的兩個距離接近的障礙物5和6.

由圖4a)可知:傳統的DBSCAN聚類算法，檢測了4個目標，將相鄰的障礙物2和障礙物3聚成了同一個類，將相鄰的障礙物5和障礙物6聚成了同一個類.主要是因為DBSCAN算法選擇固定不變的鄰域值ε和密度閾值Minpts，在物體距離很近時，容易聚類成同一物體，出現欠分割.

由圖4b)可知:未加入鄰域值下限的改進DBSCAN算法在對距離激光雷達很近的相鄰目標2,3的檢測中，將目標2,3中的大部分點云檢測為噪聲.這是因為離激光雷達很近的點的鄰域值選取得過小，使得其鄰域內點數明顯少于密度閾值Minpts，因此被檢測為噪聲.

由圖4c)可知:加入鄰域值下限后的改進DBSCAN算法，檢測了6個目標，把距離激光雷達較近的相鄰障礙物2，3以及距離激光雷達較近的相鄰障礙物5，6明顯地分割開來.這是因為改進的DBSCAN算法，每一個點的鄰域值ε是獨立的，近距離點云的鄰域值ε選取相對較小，所以能夠區分距離激光雷達較近的相鄰目標.

實驗表明，設置一個良好的鄰域值下限后的改進DBSCAN算法，可以減少距離激光雷達較近的目標被檢測為噪聲的情況.改進的DBSCAN算法相較于傳統的DBSCAN算法，在距離激光雷達較近的目標檢測中有分割優勢，減少了相鄰的目標欠分割的情況.

圖5為原始和提取感興趣區域后的待處理點云，圖6a)為取ε=1，Minpts=40的傳統DBSCAN聚類結果，圖6b)為未設置鄰域值下限ε0的改進DBSACN聚類結果，圖6c)為設置鄰域值下限ε0的改進DBSCAN聚類結果.

圖5 原始點云和提取感興趣區域后的待處理點云

圖6 傳統和改進DBSCAN聚類結果

在該實驗場景下，包含有6個障礙物.分別為4個近距離障礙物：(0,0,:)附近的障礙物1，(-2,0,:)附近的障礙物2，(-2,5,:)附近的障礙物3，在點(-8,3,:)附近的障礙物4.以及2個遠距離障礙物：在(10,20,:)附近的大障礙物5，在(8,20,:)附近的小障礙物6.

由圖6a)可知，傳統的DBSCAN算法檢測了離激光雷達較近的障礙物1、2、3、4，將距離激光雷達較遠的大障礙物5的大部分點云檢測為噪聲，將距離激光雷達較遠的小障礙物6的全部點云檢測為噪聲.這是因為在傳統的DBSCAN算法中，選取了一個固定的鄰域值ε和密度閾值Minpts，當它滿足近距離的激光雷達目標檢測時，對于離激光雷達較遠的點云，這些點云明顯更為稀疏，其密度小于密度閾值Minpts，不滿足核心點的判定，因而無法被檢測，所以結果距離激光雷達較遠大障礙物5上的大量點云被檢測為噪聲，距離激光雷達較遠的小障礙物6的全部點云都被檢測為噪聲.

由圖6b)可知，未設置鄰域值下限ε0的改進算法，將距離激光雷達很近的障礙物1檢測為噪聲，其他障礙物的檢測結果與設置鄰域值下限ε0后的改進之后的DBSCAN算法一致.

由圖6c)可知，設置鄰域值下限ε0后的改進之后的DBSCAN算法，既檢測了離激光雷達較近的障礙物1、2、3、4，又檢測了離激光雷達較遠的兩個障礙物5,6.這是因為改進的鄰域值ε選取是隨著距離自適應增大的，在一定的密度閾值Minpts下，遠距離目標采用更大的鄰域值ε，在點的ε范圍內可以包含更多的點數，使得遠距離障礙物點云滿足核心點的判定，從而被算法檢測到.

實驗表明，設置一個合適的鄰域值下限后的改進DBSCAN算法，可以減少距離激光雷達較近的目標的點云被檢測為噪聲的情況.改進的DBSCAN算法相較于傳統的DBSCAN算法，在距離激光雷達較遠的目標檢測中有很大優勢，減少了距離激光雷達較遠的目標被漏檢的情況.

實驗中，對無人艇采集的連續幀的障礙物點云數據進行了聚類，其平均結果見表2.

表2 傳統DBSCAN與改進DBSCAN各項指標對比

雖然平均耗時對比傳統DBSCAN有所增加，但是增幅不大，可以滿足在工程上的應用.對比于傳統DBSCAN聚類算法，改進DBSCAN算法的正確率明顯大于傳統的DBSCAN聚類算法，提高了21.21%，丟失率下降了9.09%，這說明改進DBSCAN算法比傳統DBSCAN算法分割更為準確.改進DBSCAN算法錯誤分割率降低了12.12%，這說明改進DBSCAN算法相較于傳統DBSCAN算法分割更為精細.

綜上所述，改進的DBSCAN算法較傳統DBSCAN聚類算法，在近距離的目標檢測中，可以減少檢測目標被欠分割的情況，在遠距離的目標檢測中，可以減少檢測目標被漏檢的情況.在激光雷達水面目標檢測中，改進的DBSCAN算法相比于傳統的DBSCAN算法檢測效果更好.

4 結 束 語

文中以無人艇采集的水面障礙物點云數據為研究對象，針對傳統DBSCAN算法對鄰域ε、密度閾值Minpts兩個參數選取困難的問題，以及采用固定的鄰域值ε和密度閾值Minpts難以對全部數據實現良好聚類的問題，提出了一種自適應參數的改進DBSCAN算法，對每一個點云采取獨立的ε進行聚類.改進的方法降低了參數選擇的難度，可以減少近距離目標目標被欠分割的情況，可以防止遠距離目標被漏檢的情況.通過傳統DBSCAN算法與改進DBSCAN算法的對比，驗證了改進DBSCAN算法的有效性.