王凱歌 馮 輝 徐海祥 胡 勇

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

0 引 言

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

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

1 地面點(diǎn)云與非面地點(diǎn)云分割

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

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

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

圖1 地面點(diǎn)與非地面點(diǎn)分割

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

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

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

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

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

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

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

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

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

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

圖5 邊緣點(diǎn)搜索到的點(diǎn)

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

(1)

(2)

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

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

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

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

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

(3)

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

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

(4)

根據(jù)圖7其截?cái)鄼?quán)值由式(4)計(jì)算得2.9，則點(diǎn)1～6被剔除，最終圖4c)中類A的邊緣點(diǎn)搜索到的點(diǎn)集中不再包含類B和類C中的點(diǎn)，搜索不會(huì)再?gòu)念怉延伸到其他類.

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

(5)

(6)

(7)

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

(8)

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

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

4 實(shí)驗(yàn)結(jié)果及分析

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

圖9 聚類前的點(diǎn)云圖像

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

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

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

由圖10～12可知，當(dāng)多個(gè)目標(biāo)相距較近時(shí)，距離閾值選取較大會(huì)出現(xiàn)很多欠分割的目標(biāo)，隨著距離閾值的增大欠分割的現(xiàn)象更加嚴(yán)重.相較于傳統(tǒng)的歐式聚類算法，改進(jìn)后的算法在0.5～1 m的距離閾值范圍內(nèi)都可以較好地分割距離較近的多個(gè)目標(biāo)，在一定程度上解決了傳統(tǒng)歐式聚類對(duì)距離閾值敏感的問題，降低了距離閾值選取的難度.實(shí)驗(yàn)中對(duì)傳統(tǒng)的歐式聚類算法和改進(jìn)之后的歐式聚類算法進(jìn)行了連續(xù)幀點(diǎn)云的目標(biāo)檢測(cè)，其平均結(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時(shí)改進(jìn)后的歐式聚類較傳統(tǒng)的歐式聚類其正確率分別提升6.5%，13%，26.5%且正確率都較高，而欠分割率有較大的下降，其欠分割率分別下降9%，17%，31%.同時(shí)改進(jìn)后的歐式聚類在0.5～1 m的距離閾值區(qū)間內(nèi)過分割率和丟失率都較低.表4為單幀點(diǎn)云聚類的平均耗時(shí)，從平均耗時(shí)來看改進(jìn)后的歐式聚類較傳統(tǒng)的歐式聚類耗時(shí)有所增加，但耗時(shí)增加幅度不大，依舊可以滿足實(shí)時(shí)的目標(biāo)檢測(cè).綜合聚類效果和耗時(shí)來看，改進(jìn)后的歐式聚類算法較傳統(tǒng)的歐式聚類算法在一個(gè)距離閾值區(qū)間內(nèi)都有較好的聚類效果，降低了傳統(tǒng)歐式聚類距離閾值選取的難度.

表4 單幀點(diǎn)云聚類的平均耗時(shí)

5 結(jié) 束 語

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