基于改進(jìn)歐式聚類的激光雷達(dá)目標(biāo)檢測

王凱歌 馮 輝 徐海祥 胡 勇

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

0 引 言

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

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

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

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

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

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

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

2 傳統(tǒng)歐式聚類方法

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

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

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

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

3 改進(jìn)歐式聚類方法

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

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

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

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

圖5 邊緣點搜索到的點

依據(jù)圖5中搜索到的點的坐標(biāo)計算此次搜索的“類別點”C，其坐標(biāo)的計算公式為

(1)

(2)

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

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

圖6 “類別點”位置及坐標(biāo)

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

圖7 距離閾值范圍內(nèi)各點權(quán)值圖

(3)

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

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

(4)

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

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

(5)

(6)

(7)

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

(8)

改進(jìn)之后歐式聚類算法流程見圖8.

圖8 改進(jìn)后的歐式聚類算法流程圖

4 實驗結(jié)果及分析

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

圖9 聚類前的點云圖像

圖10 距離閾值為0.5 m的聚類結(jié)果

圖11 距離閾值為0.7 m的聚類結(jié)果

圖12 距離閾值為1 m的聚類結(jié)果

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

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

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

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

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

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

5 結(jié) 束 語

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