應用于無人駕駛車輛的點云聚類算法研究進展*

王子洋 李瓊瓊 張子蘊 王 康 楊家富

（南京林業(yè)大學機械電子工程學院，南京210037）

隨著近年來人工智能的快速發(fā)展，無人駕駛汽車的出現(xiàn)引發(fā)了各界人士的大量關注，這將對傳統(tǒng)汽車行業(yè)形成巨大的沖擊。無人駕駛車輛通過多種車載傳感器來識別車輛所處的周邊環(huán)境和狀態(tài)，并根據所獲得的環(huán)境信息自主做出分析和判斷，從而自主地控制車輛運動，最終實現(xiàn)無人駕駛。其中，環(huán)境感知[1]、導航定位、路徑規(guī)劃[2，3]、決策控制[4]是無人駕駛汽車的四大核心技術[5]。環(huán)境感知是用來獲取周圍環(huán)境信息的，是實現(xiàn)無人駕駛的基礎[6]。目前主流的有以谷歌為代表采用激光雷達的方案和以特斯拉為代表采用視覺的方案。點云聚類是環(huán)境感知重要部分之一，其利用激光雷達對點云進行聚類分割，同時也為點云分類奠定了重要基礎。點云聚類算法是人工智能和無人駕駛領域中新型的算法，該算法不僅是研究熱點還得到了廣泛的推廣。經典的點云聚類算法也包括 K-means算法[7]、DBSCAN算法[8]等。

無人駕駛汽車通過激光雷達發(fā)射出的激光束對周圍環(huán)境進行旋轉掃描形成的點云圖，每個點都會有相應的坐標位置信息，點云聚類的任務就是將點云圖中的各個點云聚類成若干個整體，具有相似程度的對象構成一組，降低后續(xù)計算的計算量，也有利于后續(xù)的聚類。目前在無人駕駛汽車的研發(fā)中，點云聚類主要應用于對障礙物、道路、行人等方面檢測。其中絕大多數是研究在結構化道路上的檢測問題，而非結構化道路上的檢測問題還有待進一步深入研究。本文簡要闡述了點云聚類的基本概念，分析了應用于無人駕駛車輛中點云聚類的六類聚類方法，并將這六類聚類方法在點云聚類應用中的性能進行了對比，最后提出了無人駕駛車輛點云聚類的未來研究方向。

1 點云聚類

所謂的點云聚類就是將沒有任何結構的原始點云按照某些特征分割成一系列的點云簇，同一類的點云簇具有相似或相似度較高的特征，不同類點云簇間的點云具有不相似或相似度較低的特征，聚類階段如圖1所示。近年來在無人車的感知層中點云聚類開始得到了廣泛的應用，其中主要的點云聚類方法如表1所示。

圖1 聚類階段[9]Fig．1 Clustering Stage[9]

表1 應用于無人車感知層的點云聚類算法分類Tab．1 Classification of Point Cloud Clustering Algorithm Applied to Perception Layer of Unmanned Vehicle

1.1 基于劃分的聚類算法

基于劃分的聚類算法的基本思想是預先指定聚類數目和聚類中心，計算每個點與其他點的距離，對于每個數據點都有n－1個距離值，對這些距離值進行排序，找出最接近的數據點，算出這些距離的和值。并進行下次迭代，這時數據中心點位置改變，繼續(xù)按照上方的步驟，逐步降低目標函數的誤差值，直到目標函數值收斂時，得到最終聚類的結果。代表算法有K-means算法。

1.1.1 K-means算法

K-means算法思想能夠追溯到1957年的Hugo Steinhaus，術語“k-means”于 1967年才被James MacQueen[10]首次使用。K-means算法是基于劃分的聚類算法[11]，其思想是以k為參數，把n個對象分成k個簇，使簇內具有較高的相似度，而簇間的相似度較低。該算法是研究得最多的分區(qū)聚類算法[12]，同時由于其簡單性該算法也被大量學者廣泛使用。

龔亮等[13]采用K-means算法利用機載激光雷達點云數據的強度信息對道路進行提取，可以分離道路輪廓。Diaz-Vilarino等[14]使用 K-means算法對石頭和瀝青兩種不同路段進行聚類，較好地分辨出兩種不同的路段，但僅限于瀝青和石頭兩種特定的材料。Xia等[15]將強度信息作為特征進行聚類以區(qū)分同距離的不同目標，再利用閾值限定聚類中心間的最小距離，其聚類準確率達到90%以上，較好地解決了同一距離不同目標的激光雷達點云聚類問題，但還存在對輸入參數預先選取問題。

然而K-means算法在處理點云數據過程中，常會受到k值和初始聚類中心的選取等相關因素的影響，導致其聚類的準確率較低。為了解決k值難以選取的問題，Li等[16]開始嘗試利用熵代價函數來確定合適的聚類數目，但未解決選取聚類中心問題。Khan等[17]為了解決在聚類開始前對初始聚類中心難以選取的問題，提出了一種計算k均值聚類初始聚類中心的算法，但還存在對k值選取問題。在上述問題的基礎上，Limwattanapibool等[18]采用了基于密度的思想自動找到K-means的合適k值和初始聚類中心。而Li等[19]利用局部最大密度區(qū)域的個數來確定k值的選取，再根據數據點的坐標值計算出各個局部最大密度區(qū)域的重心，將初始聚類中心選取為距離重心最近的點，有效地解決了k值和初始聚類中心兩個初始參數的選取問題，提升了聚類結果，但降低了聚類速度。

K-means算法簡單實用，對高維或低維點云數據聚類的效率較好。但不能夠對任意形狀的簇進行聚類，同時由于依賴k值、聚類中心點的選取，參數的選取直接會影響到聚類結果的好壞，因此該算法的聚類準確率不穩(wěn)定。

1.1.2 模糊c-均值聚類算法

模糊 c-均值聚類算法[20]（Fuzzy C-Means Algorithm，F(xiàn)CM）由美國的Bezdek教授最早提出，是基于劃分的聚類算法。FCM算法是對目標函數進行優(yōu)化的聚類算法，主要是根據各個對象之間的相似性來完成目標對象的聚類，算法的主要思想是確定好聚類數和聚類中心初值去計算每個點與聚類中心的距離，構建模糊[21]分類矩陣以及重新計算聚類中心，最終直到相鄰兩次的聚類中心小于規(guī)定值時聚類結束，得到聚類結果。

FCM算法較為簡單，運算速度快并且算法容易實現(xiàn)。但FCM算法也存在著自身的不足，受參數的影響較大，在聚類之前要先確定聚類數目和初始聚類中心的值，并且聚類數目與初始聚類中心的值會直接影響到聚類的結果，在FCM算法逐步優(yōu)化的過程中，也會容易陷入到局部最優(yōu)解，也可能會使得最后得到的結果與預想的差別很大。

針對以上FCM算法存在的一些缺陷，Chiu等[22]提出了一種自適應模糊c-均值聚類算法，該算法可事先根據輸入樣本點的數據來確定和劃分聚類數目和初始聚類中心的值，簡化了算法的計算難度并且優(yōu)化了聚類的結果，但未解決易陷入局部最小值問題。于是Wang等[23，24]采用了改進的粒子群算法和FCM相結合的算法，通過利用改進的粒子群算法解決了傳統(tǒng)FCM易陷入局部最小值問題，通過實驗驗證該算法具有更快的收斂速度和更少的迭代次數，點云聚類效果更加準確，但還存在對輸入參數敏感問題。Fu等[25]采用遺傳算法確定FCM的聚類數目，很好地克服了輸入參數敏感問題，但還存在計算時間長，聚類效果較差的問題。而Chen等[26]在Fu等的基礎上提出了一種改進的遺傳FCM聚類算法，通過改進了遺傳算法的交叉、選擇和變異來提高全局搜索能力，降低了設置遺傳參數的難度，很好地提高了收斂速度與聚類結果。

K-means算法與FCM算法很相似，兩者都是基于劃分的聚類方法，并且在聚類之前都要事先確定好聚類數目和聚類中心值，兩個算法都較為簡單，容易實現(xiàn)，但在實際使用中使用K-means算法的人相對較多一些。

1.2 基于層次的聚類算法

基于層次的聚類算法的主要思想是把每個對象都看成是一個類，去計算任意兩個子類的相似度并根據相似度的大小進行排序，把相似度最大的兩個子類合并或者把相似度大于一定閾值的若干個子類合并去得到新的類，再重新計算類與類之間的相似度再進行排序，直到滿足終止條件才完成聚類。該算法通?？山忉屝院?、能產生較好的聚類，與K-means算法相比較可解決非球形簇的問題，但也存在時間復雜度高等缺點。目前在處理點云聚類問題中，層次聚類常被作為其他聚類算法的輔助算法使用。

部分學者也對傳統(tǒng)的基于層次的聚類算法做了一些改進，張名芳[27]提出了一種在線學習合并閾值的層次聚類算法，通過確定聚類數搜索范圍上界和初始聚類中心的待選點集，利用距離乘積最大化方法對待選點集進行初始化排序，結合點云的空間密度分布從而提高運算速度并較好的改善了聚類結果。而Zhao等[28]提出了一種基于表面特征描述的基于層次聚類算法，該算法不需要先驗知識和特定的閾值，可以快速簡化密集點云，同時還保留特征點，減少了聚類時間，也使得點云精度損失較小。

基于層次的聚類算法與基于劃分的聚類方法相比，在點云聚類方面應用相對較少，該算法可以去識別形狀復雜、大小不一的類，并且孤立點以及噪聲點也可被濾除。但兩者也存在相似之處，在聚類之前都需要預先知道子類的數目。

1.3 基于密度的聚類算法

大多數的聚類方法是以數據集在空間分布上的距離作為依據進行聚類，而基于密度的聚類方法是以數據集在空間分布上的稠密度為依據進行聚類，無需預先設定簇的數量，因此特別適合對未知內容的數據集進行聚類。此外，該方法不僅可以發(fā)現(xiàn)任意形狀的簇，還可有效去除噪聲點。

1.3.1 DBSCAN算法

DBSCAN算法是在1996年被 Martin Ester、Hans-Peter Kriegel等[29]率先提出的，該算法是基于密度的聚類算法中最常用的一種聚類方法[30，31]，該算法通過引入密度的概念，即要求聚類空間中的一定區(qū)域內所包含對象的數據不小于某一給定閾值。該方法能夠在具有噪聲的空間數據庫中發(fā)現(xiàn)任意形狀的簇，可將密度足夠大的相鄰區(qū)域連接，能夠有效的處理異常數據，主要用于對空間數據的聚類。

DBSCAN算法是點云聚類算法中較為常用的算法，楊思遠等[32]采用DBSCAN算法去除噪聲點云實現(xiàn)車輛點云聚類，Liu等[33]利用DBSCAN算法對非結構化環(huán)境中的障礙物點云進行聚類。

為了提高算法的聚類速度，Guan等[34]通過設置掃描點搜索角領域來改變搜索擴展域范圍并結合自適應DBSCAN算法，大大減少了聚類搜索時間實現(xiàn)點云快速聚類，Zhao等[35]提出了 VGDBSCAN算法，將三維點云進行體素柵格劃分，大幅減少了搜索范圍，通過實驗驗證該算法可實現(xiàn)點云的快速聚類，而Li等[36]將區(qū)域生長算法與自適應DBSCAN算法相結合，對預處理后的點云數據進行兩階段聚類，實現(xiàn)對障礙物的快速檢測，該方法不僅加快了聚類速度，還具有較好的魯棒性。

由于DBSCAN算法嚴重依賴半徑（Eps）和閾值（MinPts）兩個參數的選取，所以參數的選取往往會直接影響到最終的聚類結果，雖然部分學者將DBSCAN算法改進成自適應的DBSCAN算法，但僅實現(xiàn)了半徑的自適應，還存在閾值自適應的問題有待解決，所以希望以后會有更多的研究人員嘗試解決閾值的選取，實現(xiàn)兩個參數的自適應，從而達到最佳的聚類效果。

1.3.2 OPTICS算法

OPTICS算法也是一種基于密度的聚類算法，可以說是對DBSCAN算法的擴展。與DBSCAN算法不同的是，OPTICS算法可以獲得不同密度的聚類，其實就是通過OPTICS算法的處理，理論上應該可以獲得任意密度的聚類。OPTICS算法思想與DBSCAN算法較相似，OPTICS和DBSCAN的輸入參數一樣是半徑（Eps）和閾值（MinPts），但該算法對 Eps輸入不敏感，先通過固定的MinPts和無窮大的Eps去得到有序列表，然后再得到決策圖，最后通過決策圖可知Eps取特定值時數據的聚類情況。

OPTICS算法不需要去提前確定簇個數就可以去發(fā)現(xiàn)任意形狀的簇，同時還對輸入的參數不敏感，但不同的Eps也會影響算法最終的聚類效果，并且傳統(tǒng)算法還存在不會對噪點區(qū)分問題。針對傳統(tǒng) OPTICS算法存在的一些缺陷，F(xiàn)eng等[40]提出了一種與OPTICS算法相結合并利用網格優(yōu)化的DBSCAN算法，該算法首先將DBSCAN中的核心點轉換為網格中心點進行處理，然后以柵格為最小處理對象，最后減少了耗時，提高了運算效率。而Moosmann等[41]提出了一種基于加權歐氏距離的改進算法，解決了傳統(tǒng)OPTICS算法受參數約束問題，改善了點云聚類效果，同時也增強了目標提取的準確性，但對提取出的目標類別有限。

OPTICS算法與DBSCAN算法都是基于密度的聚類算法，兩者的輸入參數一樣均為半徑（Eps）和閾值（MinPts）。但DBSCAN算法對輸入的參數過于敏感，選擇不同的參數會導致千差萬別的聚類結果，而OPTICS算法的提出可以說就是為了改善DBSCAN算法，幫助其選擇合適的參數，從而降低對輸入參數的敏感度。但目前使用DBSCAN算法的較多，而采用OPTICS算法很少，希望以后會有更多的學者將OPTICS算法運用到無人駕駛點云聚類方面。

1.4 基于網格的聚類算法

先把對象空間量化為有限數目的單元，這些單元形成了網絡結構，所有的聚類操作都在該結構上進行。這種方法的優(yōu)勢在于運算速度快，其處理的時間獨立于數據對象數，而僅依賴于量化空間中每一維的單元數。

基于網格的聚類算法主要思想是首先對網格進行劃分，然后使用網格單元內數據的統(tǒng)計信息對數據進行壓縮表達，再根據這些統(tǒng)計信息去判斷出高密度網格單元，最后將相連的高密度網格單元識別成簇。

由于傳統(tǒng)的網格聚類自身存在局限性，所以一些研究人員在傳統(tǒng)算法的基礎上加以了適當的改進，Huang等[42]提出了一種基于最小聚類單元的新算法，通過結合K-means與網格聚類的優(yōu)缺點，解決了定值k和網格聚類中數據密集的難點。Qiu等[43]提出了一種相交的網格劃分與密度估計相結合的方法，通過分區(qū)可以大大減少高維點云數據中的網格數量，并且使得領域搜索變得簡單，該算法不僅可以去發(fā)現(xiàn)任意形狀的簇，還可以加快聚類速度，但還需要輸入一個初始參數。而Lou等[44]提出了一種基于動態(tài)距離閾值的網格聚類算法，通過實驗表明，改進后的動態(tài)閾值與傳統(tǒng)的固定閾值相比，能夠解決處理激光雷達點云近密遠疏的問題，同時還能夠更好地對障礙物進行正確聚類。

鉬合金薄壁管在高溫加熱、核電、溫控等領域有著廣泛的應用，長期以來，由于工藝技術的原因，鉬合金管主要以厚壁(厚度≥1 mm)管材為主，管材長度不超過2 m，極大限制了其在高端產品上的應用。國內大長徑比的無縫鉬合金薄壁管產品基本處于空白，產品主要依賴于進口。技術中心團隊經過在工藝加工技術方面的不斷努力攻關，成功攻克了大長徑比無縫鉬合金薄壁管制備的關鍵技術，掌握了此類產品的核心加工工藝。項目制備出的鉬合金薄壁管外徑8 mm，壁厚0.6 mm，長度達8 m。經過壓力測試，該產品在50 MPa的壓力下依舊保持完好。

基于網格的聚類算法運算速度很快，但還存在對參數敏感、無法處理不規(guī)則分布的數據等問題。并且該類算法效率的提高是以聚類結果的精準性為代價的，因此通常與基于密度的算法結合使用。

1.5 基于距離的聚類算法

歐式聚類[45]（又稱歐幾里得聚類）通過計算歐氏距離將相近的點云聚類在一起，也是目前最受歡迎的點云聚類算法之一。

劉暢等[46]提出了一種基于點云射線角度約束以及改進的歐式聚類算法，加快了算法運算速度，同時有效解決了傳統(tǒng)歐式聚類面對點云密度不均勻導致聚類效果差問題，最終通過實車實驗驗證該算法可以快速準確地對障礙物進行聚類，但只對一定范圍內的障礙物有效。Zong等[47]對傳統(tǒng)歐式聚類進行了改進，先通過KD-tree對點云數據進行快速搜索，再引入距離的變閾值思想使得閾值距離隨著點云距離的變化而改變。最后經過試車實驗得出改進后的方法能夠更快速準確地識別障礙物，同時還具有較強的抗干擾能力，而Fan等[48]也采用了KD-tree與歐式聚類相結合的思想，先通過體素濾波進行下采樣，再通過KD-tree快速搜索，提高歐式聚類的聚類速度和聚類效果，最終通過實車實驗表明在越野環(huán)境下可以準確識別行人，具有良好的識別率。

歐式聚類簡單易懂，運算速度快、具有良好通用性同時可用于處理高維數據。雖然目前該算法發(fā)展較為成熟，閾值選取問題已被大多研究人員所解決，但還需要結合一些輔助方法（通常是用KD-tree）去達到更好的聚類效果。

1.6 混合聚類算法

近年來，混合聚類算法逐漸吸引國內外研究人員的關注?；趧澐值木垲愃惴?、基于層次的聚類算法、基于密度的聚類算法、基于網格的聚類算法和基于距離的聚類算法雖然在一定程度上可以去實現(xiàn)無人駕駛汽車的點云聚類，但傳統(tǒng)算法都有其各自的優(yōu)缺點。如果單單僅使用一種算法，那將很難去達到聚類結果的準確性以及算法的高效性。故采用多種方法相結合，并利用其各自優(yōu)勢的混合算法將是該領域的研究重點。

在對改善點云聚類效果方面，鄭蘭香等[49]將基于相對距離和密度的聚類算法相融合，不僅校正了點云的偏移量，還有效地對密度不均勻的點云進行聚類，具有較好的魯棒性。Fan等[50]通過結合深度圖和改進的自適應DBSCAN算法對非地面障礙物點云進行聚類，提升了聚類時間效率和聚類的準確度。Mark Junjie Li等[51]提出了一種凝聚模糊K-均值聚類算法，通過在目標函數中引入了懲罰項來確定聚類數，解決了K值選取問題，提高了聚類效果，加快了算法的聚類速度。Yuan等[52]提出了一種DBSCAN和RIC相結合的算法，采用自適應Eps領域選擇方法來代替全局參數，經過實車實驗驗證表明，該方法能夠將點云分布不同但密度相近的連接對象分離出來，從而達到更好的聚類效果。

在對點云聚類算法優(yōu)劣勢互補方面，Duan等[53]提出了一種DBSCAN與K-means相結合的方法，在K-means中加入了密度聚類的思想，較好了克服了k值難以選取和無法分割密度相鄰的障礙物問題。Yuan等[54]將信息聚類和自適應DBSCAN聚類相融合，不僅克服了傳統(tǒng)DBSCAN算法全局參數的缺點，還保留了去噪能力強的特點，同時也改善了聚類結果。李海倫等[55]將遺傳算法和模糊聚類算法相結合提出一種遺傳模糊聚類算法。利用遺傳算法去解決FCM算法可能陷入局部極小值問題，從而避免了陷入局部最小值情況，同時減少了FCM的迭代次數也提高了算法的運算速度，最終實現(xiàn)快速、準確的點云聚類。Zhou等[56]提出了一種基于密度峰值和空間領域信息的改進FCM算法，通過選擇局部密度峰值較大的點為初始中心點，不僅解決了輸入參數敏感問題，還具有更好的抗噪能力和聚類性能。Wang等[57]提出了改進的粒子群優(yōu)化算法與模糊C-均值算法相結合的SPSO-FCM算法。利用粒子群算法具有較強的全局搜索能力特點，可有效避免過早捕獲局部極小值，同時也改善了初始化聚類中心的高靈敏度所帶來的局限性，最終可以尋找到全局的最優(yōu)解，大大提高了算法的效率，也改善了聚類結果。

此外，基于層次的K-means算法、遺傳算法和K-means算法[58]、基于密度和空間分布的點云聚類算法[59]、結合橢球準則與 FCM聚類算法[60]等。這些混合算法都在一定程度上改善了傳統(tǒng)算法的性能，提高了點云聚類的效果。

2 點云聚類算法在點云聚類應用中的性能對比

每種點云聚類算法在對點云聚類時都會存在自身的一些不足之處，綜上所述，總結的結果如表2所示。

表2 各聚類算法在點云聚類中的優(yōu)缺點對比Tab．2 Advantages and Disadvantages of Each Clustering Algorithm in Point Cloud Clustering

由表2分析可以看出基于劃分聚類、基于密度聚類和基于距離聚類，這三種聚類算法都存在需要預先設定參數的問題，并且嚴重依賴參數的選取，往往會因為參數的取值問題而影響到最終的聚類結果?；趧澐志垲?、基于網格聚類和混合聚類都具有運算速度快的優(yōu)勢，同時基于層次聚類、基于距離聚類和混合聚類的聚類效果都不錯。經過綜合對比可以看出混合聚類算法優(yōu)勢更好一些，但由于混合聚類算法種類太多，需要根據聚類問題選取與其相應合適的混合聚類算法，這樣才能更好地發(fā)揮其聚類效果。

3 總結與展望

綜上所述，盡管國內外學者針對點云聚類做了大量的研究，但到目前為止還并沒有一種適用于所有場景的通用算法，伴隨著激光雷達線數的增多，聚類算法在往云數據方向發(fā)展。未來點云聚類算法將在以下幾個方面成為研究熱點：

1）在對點云數據處理方面，傳統(tǒng)聚類算法在處理大規(guī)模點云數據時運算速度慢，難以滿足無人駕駛車輛的實時性，引入邊緣算法將是無人駕駛車輛的發(fā)展趨勢。

2）激光雷達會使得點云近密遠疏、分布不均勻以及會丟失部分云點，采用混合算法，設計出具有更好的魯棒性和準確性的點云聚類算法保證無人駕駛車輛的實時性和安全性。

3）目前點云聚類算法大部分都是采用圍繞K-means、DBSCAN和歐式聚類等算法，使得在處理無人駕駛點云聚類方面的聚類算法過于單一，可以嘗試將灰色聚類、基于模型的聚類、譜聚類和量子聚類等算法運用到無人駕駛點云聚類中，從而進一步為無人駕駛車輛點云聚類方面的發(fā)展提供參考。