基于改進歐式聚類的激光雷達目標檢測

王凱歌 馮 輝 徐海祥 胡 勇

(高性能船舶技術教育部重點實驗室1) 武漢 430063) (武漢理工大學船海與能源動力工程學院2) 武漢 430063)(上海交大海洋水下工程科學研究院有限公司3) 上海 200231)

0 引 言

激光雷達由于測量精度高、響應速度快、抗干擾能力強、可以很好的表征外部環境等優點而被廣泛地應用于無人系統領域，其在無人機、無人車、無人船上的使用已經得到了較好的發展.激光雷達目標檢測的核心是點云的聚類，點云聚類的算法一般分為傳統的聚類算法和基于模型的機器學習聚類算法兩類.傳統的點云聚類方法主要包括基于密度的DBSCAN聚類算法[1-3]、基于劃分的K-Means聚類算法[4-5]、區域增長法[6]、基于空間距離遠近的歐式聚類算法等.其中，DBSCAN聚類算法可以發現任意形狀的點云簇，對噪聲點不敏感，但數據量大時聚類所需的時間較長.文獻[3]針對密度不均的點云數據，通過建立參數列表使得參數隨著距離的增加而合理地增大，改善了密度聚類的效果.K-means聚類算法原理簡單、聚類速度快，但需要人為的指定聚類簇數，對噪聲點較為敏感且只能發現球狀簇.區域增長法可以依據不同的屬性，例如，曲率、法向量、幾何特性等對點云進行聚類，但當數據包含噪聲或點云屬性分布不均時會大幅影響分割效果.李仁忠等[7-8]通過估算點云數據的曲率大小, 將曲率最小點設置為種子節點，從點云數據最平坦的區域開始生長，解決了傳統區域生長法分割不穩定的問題.歐式聚類算法在距離閾值設定合理的前提下有較好的聚類效果，聚類速度較快，適用于實時的點云目標檢測，但對距離閾值的選取較為敏感，聚類時需要選取正確的距離閾值，過大或過小的距離閾值都會影響聚類效果.吳燕雄等[9]在傳統歐式聚類算法中加入了平滑閾值的約束來防止欠分割和過分割的現象.田青華等[10]以模板物體的點云分布情況作為聚類標準，提出了一種距離閾值自適應的歐式聚類算法并應用于工件的點云聚類.劉暢等[11]按測量距離將點云劃分到不同的區域，在不同的區域內設定了不同的距離閾值，并在路面目標的檢測上進行了算法驗證.

文中以無人車的三維點云數據為例，針對傳統歐式聚類距離閾值較難選取，選取不當時會產生聚類目標過分割或欠分割，造成目標分割不準確的問題，對傳統的歐式聚類進行了改進.選取了范圍較大的距離閾值區間，區間內的距離閾值較大以避免產生過分割現象；在傳統的歐式聚類搜索過程中，對聚類目標和干擾目標的激光點設定不同的激光點權值，然后去除搜索過程中干擾目標的激光點，較好地解決了大距離閾值時產生的欠分割現象；對比了傳統的歐式聚類和改進之后的歐式聚類在聚類效果和速度方面的差異.盡管該方法采用的數據是無人車三維點云數據，但是該方法可以擴展到機器人、無人船等領域.實驗結果表明，改進之后的歐式聚類算法在選取的距離閾值區間內都有較好的聚類效果，降低了距離閾值選取的難度.

1 地面點云與非面地點云分割

由于地面點云對非地面點云聚類的影響較大，會干擾非地面點云聚類的效果，因此在進行聚類之前將地面點云去除.同一區域的地面點云其曲率一般不會有不規則的突兀的變化，因此將地面近似為平面選用RANSAC平面擬合算法來去除地面點云.

RANSAC平面擬合算法的核心是隨機抽樣性和假設性.其算法思路如下:①在一幀裁剪后的點云圖像的點云集合G={Pi=(x,y,z)|i=1,2,3,…,n}中隨機的選取三個點，利用這三個點的空間坐標確定三個點所在的平面，并設定一個距離閾值Dthres；②計算點云集合G中剩余的點到上述確定平面的距離di，將集合G中到上述確定平面的距離小于距離閾值(diDthres)的點作為非地面點.③重復上述的過程若干次選取數量最多的一組地面點云作為最終的地面點云將其去除，將對應的非地面點云保留用于聚類.

為防止地面目標較多時擬合出非地面點云部分的平面，同時減少地面點和非地面點分割所用的時間，在進行RANSAC平面擬合算法之前先提取一定高度以下的點云，將提取后的點云進行RANSAC平面擬合算法分離出地面部分的點云，見圖1.

圖1 地面點與非地面點分割

2 傳統歐式聚類方法

歐式聚類是一種區域增長式的聚類方式，基于點與點的空間距離，將空間距離比較近的點歸為一類.其原理如下：①依據待分割的點云數據建立對應的KD-tree，KD-tree是一種高緯索引的樹形數據結構，常用于大規模高維數據的K鄰近查找，可加快歐式聚類的速度，減少聚類所需的時間；②設定距離閾值Dthres，在待分割的點云中隨機地選取一個初始點Pstart，創建一個點云集合Ri，將Pstart加入Ri中.依據KD-tree在待分割的點云中搜索初始點Pstart距離閾值Dthres范圍內的點集Q={P1,P2,…,Pn}，將其加入Ri中并標記點Pstart.再從Ri中抽取未標記的點P，依據KD-tree在待分割的點云中搜索點P距離閾值Dthres范圍內的點集Q={P1,P2,…,Pn}，將其加入Ri中，標記剛才的點P，繼續從Ri中抽取未標記的點P重復剛才的步驟直至Ri中不再有新的點加入，此時將Ri作為一個分割完成的目標；③在待分割的點云中再抽取一個未標記的點作為初始點Pstart，重復上述步驟直至待分割的三維點云中的點全部被標記，歐式聚類完成得到相應的聚類目標.

由歐式聚類的原理可知：歐式聚類的效果取決于距離閾值的選取，傳統的歐式聚類算法對于距離閾值的選取較為敏感.距離閾值選取過小，可能將同一個目標分割成很多個目標，造成過分割的現象.距離閾值選取過大，如果幾個目標的空間位置相距較近，那么有可能將幾個不同的目標合并為同一個目標，造成欠分割的現象.上述問題使得在實際的應用中往往很難確定準確的距離閾值.圖2為過分割的點云圖像，框區域為過分割的目標.圖3為欠分割的點云圖像，框區域為欠分割的目標.

圖2 點云過分割(距離閾值：0.2 m)

圖3 點云欠分割(距離閾值：1 m)

3 改進歐式聚類方法

針對傳統歐式聚類算法對距離閾值敏感的問題，本文希望通過改進使得歐式聚類算法在一個范圍較大的距離閾值區間內都可以有較好的分割效果，從而降低距離閾值選取的難度.以無人車應用為例，歐式聚類距離閾值的可行范圍一般在0～1 m，由于激光雷達的分辨率較高，在較小的空間范圍內也分布著較多的激光點，在此距離閾值范圍內可以滿足對相互關聯的激光點的搜索.當距離閾值超過1 m時，歐式聚類只能檢測空間距離間隔較大的目標，對于空間距離間隔較小的多個目標極易造成目標欠分割的現象.但在0～1 m的可行范圍內由于不同目標的尺寸和距激光雷達的距離、角度有所不同，使得獲得的點云的稀疏程度也有所不同，以某一選定的距離閾值進行目標聚類時仍然存在某個單目標過分割和幾個目標被聚類為同一目標的現象，使得距離閾值的合理選取較為困難.在可行的距離閾值范圍內，距離閾值的選取其目的是避免過分割和欠分割的現象，如選取距離閾值較小的一個區間，范圍為0～0.5 m，可以避免欠分割的現象，但需要解決將過分割的目標聚合成正確目標的問題.如果選取距離閾值較大的一個區間，范圍為0.5～1 m，可以避免過分割的現象，但需要解決欠分割的目標正確分割的問題.由于僅依據空間的距離關系很難準確地將過分割的目標重新聚合，因此本文選取距離閾值較大的區間，即0.5～1 m.同時，在傳統的歐式聚類搜索過程中，對聚類目標和干擾目標的激光點設定不同的激光點權值，然后去除搜索過程中干擾目標的激光點，較好地解決了傳統歐式聚類在此距離閾值區間內欠分割目標的分割問題.本文首先以一組二維點為例，闡述改進歐式聚類方法的主要思想.

圖4a)為一組二維點，其中有三個目標：類A、類B、類C，依據上述的歐式聚類原理，隨機的選取這組點中的一個點作為起始點，假設為類A中的某一點，然后開始搜索其距離閾值內的點，再依據搜索到的點搜索距離閾值Dthres內未被搜索過的點，見圖4b).當搜索到類A的邊緣點時，如果距離閾值過大將會搜索到類B、類C中的點，見圖4c)中的點1～6.此時如果再依據點1～6進行搜索，見圖4d)，則搜索將會從類A延伸到類B和類C，最終將類A、類B、類C歸為同一個目標出現欠分割的情況，見圖4e).

圖4 歐式聚類中的欠分割問題

上述的欠分割問題是因為在類A的邊緣點處進行搜索時，由于距離閾值過大搜索到了其他類中的點.為解決此問題希望去除在類A的邊緣點處搜索到的其他類中的點，即依據圖4c)中的邊緣點進行搜索后，去除搜索到的點集中的點1～6，不再以其他類中的點繼續搜索，阻止搜索從類A延伸到類B和類C.對上述方式單獨討論圖4c)中邊緣點的搜索和對點1～6的去除，圖5為圖4c)中邊緣點搜索到的點集及點的坐標，其中搜索中心為圖4c)中的邊緣點.

圖5 邊緣點搜索到的點

依據圖5中搜索到的點的坐標計算此次搜索的“類別點”C，其坐標的計算公式為

(1)

(2)

式中：C.x，C.y為“類別點”C的坐標值；n為距離閾值范圍內搜索到的點的數量；p0.x、p0.y為搜索中心的坐標值；pi.x，pi.y為距離閾值范圍內搜索到的點的坐標值；D(pi,p0)為距離閾值范圍內搜索到的點到搜索中心的距離.

計算類別點的目的在于確定邊緣點處進行的搜索更傾向于哪個目標，由式(1)和(2)可知，搜索中心附近的點在計算“類別點”C的坐標時所占的比重較大.由于搜索從類A開始，所以搜索中心附近的點以類A中的點居多，其他類中的點距搜索中心較遠且數量較少.根據式(1)和(2)計算的 “類別點”的坐標和位置見圖6.由圖6可知，距離閾值范圍內類A中的點距“類別點”的距離比較小且比較均勻，而其他類中的點1～6與“類別點”的距離較遠.后續依據距離閾值范圍內的點和“類別點”的關系對類A中的點和其他類中的點1～6進行區分.

圖6 “類別點”位置及坐標

計算出“類別點”后，將圖6中除搜索中心以外的點與搜索中心相連，給每條邊賦予一個權值Q，見圖7，權值的計算公式為

圖7 距離閾值范圍內各點權值圖

(3)

式中:D(pi,p0)為距離閾值范圍內搜索到的點到搜索中心的距離；D(pi,C)為距離閾值范圍內搜索到的點到"類別點"的距離；D(p0,C)為搜索中心到類別點的距離；Dthres為距離閾值.

由圖7可知，搜索中心附近的點其權值較大，且類A中與搜索中心距離較遠的點其權值大于其他類中距搜索中心較遠點的權值.根據計算得到的權值，其他類中的點1～6被區分了出來，此時依據式(4)計算出截斷權值，即權值的均值，然后將大于截斷權值的點保留，將小于截斷權值的點剔除.

(4)

根據圖7其截斷權值由式(4)計算得2.9，則點1～6被剔除，最終圖4c)中類A的邊緣點搜索到的點集中不再包含類B和類C中的點，搜索不會再從類A延伸到其他類.

將上述方法拓展到三維點云的聚類，當在搜索一個目標的過程中搜索到其他干擾目標的激光點時，通過上述方法去除其他目標中的激光點，阻止聚類從一個目標延伸至其他目標，從而較好地解決了在較大距離閾值時產生的三維點云的欠分割現象.類別點坐標的計算擴展到三維空間見式(5)～(7)，各點權值的計算仍為式(3).

(5)

(6)

(7)

由于激光雷達采集到的點云，距離較近處密集，較遠處稀疏，因此對式(4)乘一裕度σ來調節截斷權值，則截斷權值見式(8).在距激光雷達較遠處選取一個小于1的σ來降低截斷權值，使得距激光雷達較遠處的聚類搜索保留更多的點，防止較遠處的目標出現過分割的現象.

(8)

改進之后歐式聚類算法流程見圖8.

圖8 改進后的歐式聚類算法流程圖

4 實驗結果及分析

針對上述改進之后的歐式聚類算法，以無人車實際采集的三維點云數據為研究對象，通過在較大的距離閾值區間選取不同的閾值對傳統的歐式聚類算法和改進之后的歐式聚類算法進行了對比和分析.其中，距離閾值區間設置為0.5～1 m，并分別選取了0.5，0.7，1 m三個距離閾值.圖9為聚類前的點云圖像，圖10～12分別為距離閾值取0.5，0.7，1 m時的點云聚類情況.

圖9 聚類前的點云圖像

圖10 距離閾值為0.5 m的聚類結果

圖11 距離閾值為0.7 m的聚類結果

圖12 距離閾值為1 m的聚類結果

由圖10～12可知，當多個目標相距較近時，距離閾值選取較大會出現很多欠分割的目標，隨著距離閾值的增大欠分割的現象更加嚴重.相較于傳統的歐式聚類算法，改進后的算法在0.5～1 m的距離閾值范圍內都可以較好地分割距離較近的多個目標，在一定程度上解決了傳統歐式聚類對距離閾值敏感的問題，降低了距離閾值選取的難度.實驗中對傳統的歐式聚類算法和改進之后的歐式聚類算法進行了連續幀點云的目標檢測，其平均結果見表1～3.

表1 距離閾值為0.5 m 單位：%

表2 距離閾值為0.7 m 單位：%

表3 距離閾值為1 m 單位：%

由表1～3可知，在0.5～1 m的距離閾值區間內改進后的歐式聚類較傳統的歐式聚類其正確率都有一定提高，在距離閾值選取0.5，0.7，1 m時改進后的歐式聚類較傳統的歐式聚類其正確率分別提升6.5%，13%，26.5%且正確率都較高，而欠分割率有較大的下降，其欠分割率分別下降9%，17%，31%.同時改進后的歐式聚類在0.5～1 m的距離閾值區間內過分割率和丟失率都較低.表4為單幀點云聚類的平均耗時，從平均耗時來看改進后的歐式聚類較傳統的歐式聚類耗時有所增加，但耗時增加幅度不大，依舊可以滿足實時的目標檢測.綜合聚類效果和耗時來看，改進后的歐式聚類算法較傳統的歐式聚類算法在一個距離閾值區間內都有較好的聚類效果，降低了傳統歐式聚類距離閾值選取的難度.

表4 單幀點云聚類的平均耗時

5 結 束 語

文中以無人系統中的三維點云聚類方法為研究對象，針對傳統歐式聚類對距離閾值敏感，易造成聚類目標過分割或欠分割的問題，選取了范圍較大的大距離閾值區間，避免了聚類中的過分割現象.同時，為了去除搜索過程中搜索到的其他目標的激光點，提出了一種改進后的歐式聚類算法，較好地解決了選取大距離閾值時造成的欠分割現象，使得改進之后的歐式聚類在一個較大范圍的區間內都有較好的聚類效果，在選取的可行距離閾值區間內解決了傳統歐式聚類對距離閾值敏感的問題，降低了距離閾值選取的難度.通過與傳統歐式聚類的對比，驗證了改進后算法的有效性和合理性.盡管以無人車點云數據作為研究對象，但是文中的方法可以很容易擴展到機器人、無人船等領域.