一種基于目標點云分布特性的動態聚類算法

摘 要：激光雷達在自動駕駛系統的目標檢測任務中發揮著重要作用，但其掃描機理會使得點云分布不均勻，常規聚類算法由于參數固定會導致較多的錯誤聚類。為解決該問題，該文以橢圓形狀作為鄰域空間，設計基于采樣點位置的鄰域自適應調整策略，提出一種基于目標點云分布特性的動態聚類算法。通過正確聚類、過聚類等綜合結果評估算法的性能，在KITTI數據集上進行了數值分析得到算法參數，并在校園環境中進行了實車對比實驗。結果表明：所提算法能減少基于密度的噪聲應用空間聚類（DBSCAN）中固定鄰域所造成的70.60%過聚類、49.76%欠聚類等錯誤結果，從而有效提高算法的綜合聚類性能。

關鍵詞： 智能汽車；目標檢測； 激光雷達； 點云聚類；KITTI 數據集；基于密度的噪聲應用空間聚類（DBSCAN）

中圖分類號： U 471 文獻標識碼： A DOI： 10.3969/j.issn.1674-8484.2024.02. 015

自動駕駛汽車（autonomous vehicles，AVs） 能有效避免疲勞駕駛等因素導致的安全問題[1]，改善交通擁堵提高駕駛效率。目標檢測是AVs 實現平穩自主駕駛的基礎[2]。相較于相機，激光雷達具有較高的測量精度和空間分辨率，且對光照等擾動具有強穩健性[3-4]，被廣泛應用于目標檢測。激光雷達目標檢測通過結構特征先將點云聚類到不同簇中，再根據幾何特征獲取目標位置和角度等信息[5-6]，其中，聚類質量將直接影響目標檢測性能。

根據點云聚類的實現原理可將其分為深度學習和聚類算法。早期基于深度學習的方法中，MVCNN [7]、PointPillars [8]、Voxel RCNN [9] 等算法將無序點云轉換為規則數據后，再利用卷積神經網絡處理，既生成了大量無效網格又模糊了目標幾何特征。Second 網絡[10]引入稀疏卷積算子以保持點云稀疏性和特征空間不變性，而以PointGNN [11] 和GraphRCNN [12] 為代表的圖卷積網絡能夠獲取更精確的目標信息。為充分利用點云空間結構，SE-SSD [13]、PointDistiller [14] 等算法以PointNet [15] 為基礎，直接根據3D 點云進行目標檢測。盡管已存在多個公開訓練數據集，但仍無法覆蓋所有交通場景和激光雷達傳感器特性[16]。此外，網絡模型輸入輸出的映射關系不明朗，聚類失效時難以定位并解決問題。

以K 均值、歐氏距離、基于密度的噪聲應用空間聚類（density-based spatial clustering of applicationswith noise，DBSCAN） 等為代表的聚類算法，具有清晰的內在關系，更適合于工程應用。K 均值方法隨機分配K個聚類中心后，迭代遍歷所有采樣點，并根據點與中心距離最近原則對點進行分配[17]。由于參數設置會影響聚類效果，LI Xinggang [18] 和ZHANGZhenyu [19] 等依據局部點密度設計參數，但無法根據場景中點的分布自適應調整。均值漂移聚類能夠根據點云分布自動發現類，并通過滑動窗口將聚類中心向數據密集方向移動[20]，但迭代優化會增加計算成本。此外，上述方法通常用于規則物體的聚類，無法處理復雜形狀的點云聚類。DBSCAN 根據密度將點聚集在簇中并遍歷鄰域點實現聚類[21]，對噪聲不敏感并適用于各種形狀的點云。面向自動駕駛應用場景，地面濾波后的目標點云具有較高的密度特征，因與DBSCAN 實現原理高度一致，而被廣泛應用于目標檢測。但是，該方法通過固定閾值處理全局數據，易造成點云的過分割、欠分割等錯誤聚類，降低目標檢測精度。

點云分布具有緊密遠疏性，故有學者從激光雷達發射角度或點云分布特性入手，以改善固定閾值帶來的不良影響。ZHAO Junxuan 等[22] 手動將檢測范圍分為具有重疊區域的3 個圓環，每個環形中DBSCAN 的閾值不同，提高了聚類精度，但參數的有效設定問題仍有待解決。CHIANG Yenhung 等[23] 通過相鄰點角度快速搜索鄰域角度，并根據點位置自動調節聚類半徑。JIANG Wuhua 等[24] 則根據采樣點的俯仰角與激光雷達角分辨率自動調整聚類半徑。CHEN Jingrong 等[25]根據激光雷達發射線角度計算點間距并構造鄰域，然后通過鄰域空間確定最小聚類個數。CHEN Xiao 等[26]提出兩步聚類法，在粗分類中根據特征的明顯程度選擇較優的多個鄰域，而在細聚類中根據k-dist [27] 曲線分析得到最優鄰域。這些方法在一定程度上改善了固定閾值導致的聚類錯誤，但同時計算多個聚類算法或復雜變量嚴重消耗了計算資源，制約了它們在車載資源上的產業應用。

鳥瞰視角（bird’s eye view，BEV） 能以較少數據直觀表征周圍場景信息，故參照文獻[28-29] 將原始點云投影到二維BEV 柵格地圖上進行后續操作。本文根據目標典型的外形特征構建點間距模型，并以此為基礎分析目標點云的空間分布規律，從而設計橢圓鄰域以適應其在不同方向和位置的密度特性。參考DBSCAN 提出動態聚類算法，并采用數值方法設計關鍵參數。并在校園環境下進行實車對比測試，驗證所提方法能否有效改善傳統固定參數的DBSCAN 導致的過聚類和欠聚類等問題，以提高目標識別性能。

1 動態聚類算法

基于典型目標外形特征在對其點云的空間分布進行分析基礎上，提出了一種動態聚類算法，以實現目標點云快速準確地聚類。

1.1 目標點云的空間分布特性分析

為實現快速準確的點云聚類，點云聚類器不僅要適應目標的形狀特點，還要結合點云本身的分布特點，即需關注相鄰點在不同位置的變化規律。考慮智能汽車感知對象的外形特點，其點云形狀主要由“｜”和“—”構成，由于聚類階段難以明確物體形狀、尺寸及其相對車輛的位置關系，故以典型的目標點云形狀分布為研究對象，聚焦于點間距沿自車行駛方向和垂直方向的變化。假設目標與車輛平行，自車行駛方向和垂直方向上相鄰點間距如圖1所示。圖中激光雷達傳感器位于坐標原點，激光雷達坐標軸方向與車輛坐標保持一致。

圖中，點A、B、C 是激光雷達檢測到該目標的相鄰3 個點，X 軸和Y 軸方向上的點間距計算式為：

dx = |y| [cot（θ - ρ）-cot θ]，dy = |x| [tan（θ + ρ）-tan θ].（1）

其中： ρ 是激光雷達在水平視場的角分辨率（ 產品出廠前已設定，具體數值請查閱產品的用戶手冊），（x， y） 是A點的坐標位置， θ 是點A處激光束與光軸中心的夾角，其計式為

由于不同生產廠商、掃描技術和產品型號之間存在差異，Lidar 掃描范圍與水平角分辨等數據會有所不同。由于車輛行駛過程中，其前方與相鄰車道內目標的運動狀態會直接影響車輛駕駛行為，且激光雷達掃描區域具有左右對稱性，故選擇前方1～80 m 和側邊0～5.6 m 區域為目標檢測的感興趣范圍，以分析目標點云的分布情況。為了使數據更貼近于真實值并具有一定的普適性，在此區域內模擬Lidar 掃描生成一系列點云數據，并以常見商用Lidar 系統的平均值0.1° 作為水平角分辨率。通過式（1） 可以計算出它們在X 軸和Y 軸上的點間距，分布情況如圖2 所示。

從圖2 中可以得出以下規律：1） 點間距dx 和dy 均隨采樣點與激光雷達距離的增大而增加，但變化速率相差巨大；2） dx 沿X 和Y 軸方向均呈非線性變化，但變化率不同；3） 相對而言，dy 的變化更加平緩，且沿X軸近似線性增長，沿Y 軸方向幾乎保持不變；4） dy 在區域內的最大值為0.175 4 m，相較于待測目標尺寸可忽略不計。

1.2 動態聚類算法

根據上一小節分析的點云空間分布規律可知，若應用DBSCAN 算法中圓形鄰域進行點云聚類可能會存在以下問題：1） 點云靠近激光雷達處密度更大，而遠離激光雷達位置的密度會更加稀疏。若使用固定的圓形鄰域進行聚類，在近距離區域內容易發生過聚類而在遠距離區域更易出現欠聚類。2） 點云密度在X 軸和Y 軸方向上具有不同的分布特點，使用圓作為鄰域形狀無法滿足該特性，在點云聚類時會出現錯誤的聚類結果。

為解決上述問題，考慮1.1 節的點云空間分布規律，設計如下的橢圓鄰域：

其中： （x， y） 是采樣點坐標位置，（xp， yp） 是鄰域中心點，Ex 和Ey 分別是半長軸和半短軸。在設計半長軸和半短軸參數時考慮：a） 檢測區域內，dy 的最大值與BEV 柵格單元具有同等數量級，且小于待測目標尺寸，故可將Ey 設置為常數；b） 雖然隨采樣點與激光雷達距離的增加dx 呈非線性增長，但為便于應用將Ex 設置為dx 的線性函數；c） 實際應用中，采樣點靠近激光雷達時，dx會小于BEV 柵格單元。此時若Ex 隨dx 減小，一方面會與不同高度的點混淆而影響聚類，另一方面也會增加計算成本；d） 典型目標尺寸存在上限，即Ex 不能隨dx無限增大。

根據上述考慮，針對（3） 式所示的橢圓鄰域，設計如下的參數調節策略：

其中： w是柵格尺寸， β 是膨脹系數， C和D是設計參數。

參考DBSCAN 構建圖3 所示的動態聚類流程。它與傳統DBSCAN 的最主要區別在于：a） 原先圓形固定鄰域被替換為式（3） 所示的橢圓動態鄰域；b） 鄰域尺寸隨采樣點位置而自適應調整。

2 聚類參數設計

除DBSCAN 中聚類密度閾值MinPts，本方法還涉及參數β，C，D。根據上節介紹的動態聚類算法，C由待測目標的最大尺寸所決定。具有真值標簽的公開數據集能夠作為聚類結果的評價標準，考慮到KITTI數據集[30] 的應用廣泛度與普遍認可度，本節將利用此數據集進行參數設計。由于自動駕駛汽車具有場景復雜性、行車安全性及現實可靠性等因素，本文將評估聚類算法在正確聚類、過聚類、欠聚類及漏聚類上[31]的整體性能表現。

2.1 MinPts 與β 的設計

根據圖3 所示的聚類流程，鄰域內點云是否合并主要由其密度MinPts 決定，而該值與橢圓鄰域尺寸相關。由式（3） 和（4） 可知，最小鄰域尺寸取決于βw，故MinPts 與β 呈正相關關系。圖4 給出了鄰域MinPts 最小情況的示例。

若鄰域內所有點均分布在長軸上，則可得到兩者之間的關系為

其中· 是向下取整函數。由于物體遮擋等因素影響可能會導致目標點不連續，需適當放大β以實現正確聚類。但過大取值意味著覆蓋更多鄰域范圍，一旦超過所需最小點密度則會導致欠聚類。綜合考慮上述因素，β由下式確定：

理論上，隨著MinPts 增加，鄰域面積變大。對于點數較少的小目標和遠處稀疏點云，難以形成有效簇而被認為是噪點，導致漏聚類或過聚類。同時，鄰域面積的增加有利于避免漏檢，但卻不利于欠聚類的分割。MinPts 對性能的影響比較復雜，為此本文在KITTI 數據集上綜合考慮正確聚類、過聚類、欠聚類和漏聚類等多種性能，采用數值方法確定MinPts 的取值[32]。數值實驗時，D 設置為0.2 m，MinPts 取值范圍設置為3～8 [33] 以尋找最優聚類效果，聚類結果如圖5 所示。

從圖5 可知，漏聚類的比例隨MinPts 的增加呈近似線性增長。這是因為MinPts 變大意味著更多點才能實現有效聚類。路人、騎行人等相對較小的目標距離激光雷達較遠時，其點數變得稀少而易被處理為噪點。此外，較大的MinPts 會擴展鄰域，對于位置相近的多個目標易被誤識別為同一物體，會增加欠聚類的比例，降低過聚類的數量。

2.2 D 的設計

理想情況下根據式（1） 可得到如圖2 所示的點間距分布圖。然而實際環境下存在目標被遮擋、方向與自車不平行、表面不光滑等異常情況。并不能直接根據1.1節的分析結果確定D。此外，待處理目標點云經BEV投影后也無法真實反應物體的幾何特征。因此，本節根據KITTI 數據集通過實驗分析來確定D。根據2.1節結果，MinPts 設置為5，D 設置為w 的1～5 倍，數值實驗結果如圖6 所示。

與圖5 結果相比，D幾乎不影響漏聚類。鄰域面積隨D 增加而變大，利于聚集同一目標點云，降低過聚類比例。然而，對于位置相近的目標點，則易將它們錯誤地識別為同一目標，導致欠聚類數量增加。綜合考慮，D 設計為0.6 m。

3 實驗驗證與分析

為驗證所提動態聚類算法的性能，在校園環境下開展實車測試。實驗車配備1 個120° 廣角視野的攝像頭以描述場景，3 個110° 水平視場角的IBEO LUX8L-8激光雷達來采集數據，其中IBEO 自帶融合器可實現多Lidar 在時間和空間上的同步，融合后可得到寬視角的掃描范圍，攝像頭作為場景描述傳感器通過幀率調節實現與Lidar 的同頻數據采集。此外，本實驗采用實時多傳感器應用程序的圖形化軟件RTMaps [34]，以保證數據的同步采集與實時存儲。所選定的實驗路線包括擁擠人群、陡坡、狹窄道路等場景，能夠充分反映城市交通中物體位置與形態。實驗平臺與典型場景如圖7所示。

為更好地驗證本算法性能，以文獻[22] 的聚類算法為參照（3-Sub DBSCAN）。該算法將檢測區域劃分為3 個具有重疊區域的矩形，具體參數設置見表1。

由于路人、騎行人和車輛具有隨機性，實驗車沿著設定軌跡行駛多次，統計結果如圖8 所示。相較于固定圓形鄰域，通過引入橢圓鄰域與自適應參數，所提算法的聚類性能都得到了明顯改善。正確聚類、欠聚類、過聚類和漏聚類的改善比例分別提高了14.26%，49.76%，70.60% 和1.2%。其中，過聚類和欠聚類的改善效果尤為明顯。聚類后的幾何信息是確定目標類型、尺寸等關鍵依據，對提升激光雷達目標識別性能具有重要意義。此外，引入自適應橢圓域后算法計算量略有增加，但仍能滿足自動駕駛的實時性要求。

圖9 為典型場景的聚類效果圖。該場景中，2 個路人行走在停滿車輛的道路上：左側路人靠近白色車輛并遮擋了部分車身；而右側路人與靜止的灰色車輛保持一定的距離。從BEV 柵格圖可看出：左側路人與白色車輛距離過近，它們的點云已經融合在一起，導致它們無法被正確識別；左側路人遮擋了白色車輛的一部分，使得該車輛點云的分布不再連續；右側路人行走過程中，手臂不斷靠近灰色車輛，縮短了它們BEV點云的距離。

根據對比結果發現：3-Sub DBSCAN 以固定圓形為搜索鄰域，其半徑無法適應障礙物點云的點間距，導致其無法將被截斷的車輛點云聚集在一起（ 如圖9c 中障礙物1 和障礙物3），也不能分割出路人和車輛的點云（ 如圖9c 中障礙物2）。相較之下，本文所提算法不僅考慮了點間距在不同方向上的差異，還能根據采樣點位置自適應調整鄰域范圍；因此，能夠正確識別被部分遮擋的車輛（ 如圖9d 中障礙物1），并且準確區分距離較近的路人和車輛（ 如圖9d 中障礙物2 和障礙物3）。

4 結 論

本文提出了一個新的動態聚類算法，通過引入自適應橢圓鄰域來應對點云在不同位置和方向上分布的不均勻性，以獲取更好的聚類性能。通過理論分析與對比實驗可得到以下結論：

1） 點云聚類算法設計過程中，不能忽略點云在距離和方向上分布不均勻的特性；

2） 相較于固定尺寸的圓形鄰域，所提出的動態橢圓鄰域能更好地處理點云的不均勻性；

3） 與傳統DBSCAN 相比，所提動態聚類算法能有效提高整體聚類性能，特別是在改善固定圓形鄰域導致的過聚類和欠聚類錯誤結果。對比實驗的結果顯示，所提方法成功糾正了固定圓形鄰域中70.60% 過聚類和49.76% 欠聚類的錯誤聚類。

參考文獻（References）

[1] GAO Feng， HAN Yu， LI Shengbo， et al. Accuratepseudospectral optimization of nonlinear model predictivecontrol for high-performance motion planning [J]. IEEETrans Intel Vehi， 2023， 8（2）： 1034-1045.

[2] Jebamikyous H H， Kashef R. Autonomous vehiclesperception （AVP） using deep learning： modeling，assessment， and challenges [J]. IEEE Access， 2022， 10：10523-10535.

[3] Alaba S Y， Ball J E. A Survey on deep-learning-basedLiDAR 3D object detection for autonomous driving [J].Sensors， 2022， 22（24）： 9577.

[4] LI You， Ibanez-guzman J. Lidar for autonomous driving：The principles， challenges， and trends for automotive lidarand perception systems [J]. IEEE Sign Proc Maga， 2020，37（4）： 50-61.

[5] XIE Yuxing， TIAN Jiaojiao， ZHU Xiaoxiang. Linkingpoints with labels in 3D： A review of point cloud semantic8（4）： 38-59.

[6] SUN Pengpeng， SUN Chenghao， WAN Lingfeng， et al.Objects detection with 3-D roadside LIDAR under snowyweather [J]. IEEE Sens J， 2022， 22（23）： 23051-23063.

[7] SU Hang， Maji S， Kalogerakis E， et al. Multi-viewconvolutional neural networks for 3D shape recognition[C]// 2015 IEEE Int’l Conf Comp Visi （ICCV）. Santiago，Chile. 2015.

[8] Lang A H， Vora S， Caesar H， et al. Pointpillars： Fastencoders for object detection from point clouds [C] // 2019IEEE/CVF Conf Comp Visi Patt Recog （CVPR）. California，USA. 2019.

[9] DENG Jiajun， SHI Shaoshuai， LI Peiwei， et al. VoxelR-CNN： Towards high performance voxel-based 3D objectdetection [J]. Proceed AAAI Conf Artif Intel， 2021， 35（2）：1201-1209.

[10] YAN Yan， MAO Yuxing， LI Bo. SECOND： Sparselyembedded convolutional detection [J]. Sensors， 2018，18（10）： 3337.

[11] SHI Weijing， Ragunathan， Rajkumar. Point-GNN： Graphneural network for 3D object detection in a point cloud[C]// 2020 IEEE/CVF Conf Comp Visi Patt Recog （CVPR）.Washington， USA. 2020.

[12] YANG Honghui， LIU Zili， WU Xiaopei， et al. GraphR-CNN： Towards accurate 3D object detection withsemantic-decorated local graph [C]// Comp Visi–ECCV2022： 17th European Conf. Tel Aviv， Israel. 2022.

[13] ZHENG Wu， TANG Weiliang， JIANG Li， et al. SESSD：Self-ensembling single-stage object detector frompoint cloud [C]// Proceed IEEE/CVF Conf Comp Visi PattRecog. 2021： 14494-14503.

[14] ZHANG Linfeng， DONG Runpei， TAI Hung-Shuo， et al.Pointdistiller： Structured knowledge distillation towardsefficient and compact 3d detection [C]// Proceed IEEE/CVF Conf Comp Visi Patt Recog. Vancouver， BC， Canada，2023.

[15] Qi C R， SU Hao， MO Kaichun， et al. PointNet：Deep learning on point sets for 3D classification andsegmentation [C]// 2017 IEEE Conf Comp Visi Patt Recog（CVPR）， Hawaii， USA. 2017.

[16] Rahman M M， TAN Yanhao， XUE Jian， et al. Notice ofviolation of IEEE publication principles： Recent advancesin 3D object detection in the era of deep neural networks：A survey [J]. IEEE Trans Imag Proce， 2020， 29： 2947-2962.

[17] GUO Ente， CHEN Zhifeng， Rahardja S， et al. 3DDetection and pose estimation of vehicle in cooperativevehicle infrastructure system [J]. IEEE Sens J， 2021，21（19）： 21759-21771.

[18] LI Xinggang， ZHANG Yaping， YANG Yuwei. Outlierdetection for reconstructed point clouds based on image[C]// 2017 First Int’l Conf Elect Instrum Info Syst. Harbin，China. 2017.

[19] ZHANG Zhengyu， JIN Mengdi. AOMC： An adaptivepoint cloud clustering approach for feature extraction [J].Scientific Programming， 2022， 2022： e3744086.

[20] SONG Yanjie， ZHANG Han， LIU Yuanqiang， et al.Background filtering and object detection with a stationaryLiDAR using a layer-based method [J]. IEEE Access，2020， 8： 184426-184436.

[21] WU Jianqing， XU Hao， ZHENG Jianying， et al. Automaticvehicle detection with roadside LiDAR data under rainyand snowy conditions [J]. IEEE Intel Transport SystMaga， 2021， 13（1）： 197-209.

[22] ZHAO Junxuan， XU Hao， LIU Hongchao， et al. Detectionand tracking of pedestrians and vehicles using roadsideLiDAR sensors [J]. Transport Res Part C： Emerg Tech，2019， 100： 68-87.

[23] CHIANG Yenhung， HSU Chihming， Tsai A. Fast multiresolutionspatial clustering for 3D point cloud data [C]//2019 IEEE Int’l Conf Syst， Man Cybe （SMC）. Bari， Italy.2019.

[24] JIANG Wuhua， SONG Chuanzheng， WANG Hai， et al.Obstacle detection by autonomous vehicles： An adaptiveneighborhood search radius clustering approach [J].Machines， 2023， 11（1）： 54.

[25] CHEN Jingrong， XU Hao， WU Jianqing， et al. Deercrossing road detection with roadside LiDAR sensor [J].IEEE Access， 2019， 7： 65944-65954.

[26] CHEN Xiao， CHEN Zhuang， LIU Guoxiang， et al.Railway overhead contact system point cloud classification[J]. Sensors， 2021， 21（15）： 4961.

[27] Athanesious J J， Vasuhi S， Vaidehi V， et al. Adaptivedensity based data mining technique for detection ofabnormalities in traffic video surveillance [J]. J Intel FuzzSyst， 2020， 39（3）： 3737-3747.

[28] LIU Kaiqi， WANG Jianqiang. Fast dynamic vehicledetection in road scenarios based on pose estimation withconvex-Hull model [J]. Sensors， 2019， 19（14）： 3136.

[29] MENG Qinghao， WANG Wenguan， ZHOU Tianfei， etal. Towards a weakly supervised framework for 3D pointcloud object detection and annotation [J]. IEEE TransPatt Anal Mach Intel， 2022， 44（8）： 4454-4468.

[30] Geiger A， Lenz P， Stiller C， et al. Vision meets robotics：The KITTI dataset [J]. Int’l J Robot Res， 2013， 32（11）：1231-1237.

[31] JIN Xianjian， YANG Hang， LIAO Xin， et al. A robustgaussian process-based LiDAR ground segmentationalgorithm for autonomous driving[J]. Machines， 2022，10（7）： 507.

[32] Laghmara H， Laurain T， Cudel C， et al. 2.5D evidentialgrids for dynamic object detection [C]// 2019 22th Int’lConf Info Fusion （FUSION）. Ontario， Canada. 2019.

[33] SONG Weilong， XIONG Guangming， CHEN Huiyan.Intention-aware autonomous driving decision-making inan uncontrolled intersection [J]. Math Prob Engi， 2016，2016： 1-15.

[34] Intempora. RTMaps [/OL]. 2023. [2023-01-03]. https：//intempora.com/products/rtmaps/.

基金項目 / Supported by ： 汽車安全與節能國家重點實驗室開放基金項目（KFY2209）；汽車協同創新中心揭榜掛帥項目（2022CDJDX-004）；重慶市技術創新與應用發展專項（CSTB2022TIAD-KPX0139）。