李佳佳，李永強(qiáng)，楊亞倫

(河南理工大學(xué) 測繪與國土信息工程學(xué)院，河南 焦作 454003)

車載LiDAR作為近年來一種新興的空間信息獲取手段，能快速獲取高精度的城市地理信息數(shù)據(jù)并應(yīng)用于諸多領(lǐng)域[1-2]。車載LiDAR采集的城市三維信息包括行人、建筑物、汽車、桿狀地物、地面等點(diǎn)云數(shù)據(jù)，其中地面點(diǎn)云均勻分布在整個(gè)道路場景中，是連接其他地物的主要樞紐。在特定的應(yīng)用研究中，需要將地面點(diǎn)濾除以獲取非地面點(diǎn)云數(shù)據(jù)。

目前地面點(diǎn)提取算法主要分為4類：①基于數(shù)學(xué)形態(tài)學(xué)的算法[3-6]。該方法首先對(duì)點(diǎn)云數(shù)據(jù)進(jìn)行網(wǎng)格化，以任意一點(diǎn)為中心開w×w的窗口，通過腐蝕膨脹窗口內(nèi)各點(diǎn)高程提取地面點(diǎn)云數(shù)據(jù)，但該算法針對(duì)起伏地形提取效果較差，自動(dòng)化程度及對(duì)低矮地物的濾除效果欠佳。②基于坡度變化的算法[7-10]。該方法的核心思想為地面點(diǎn)與非地面點(diǎn)的坡度大于地面點(diǎn)間的坡度，計(jì)算各點(diǎn)與鄰域點(diǎn)之間的坡度值和設(shè)定閾值進(jìn)行對(duì)比，判定其是地面點(diǎn)還是非地面點(diǎn)。該算法具有較強(qiáng)的實(shí)用性，但需要人工輸入多個(gè)閾值參數(shù)，閾值選擇不當(dāng)會(huì)影響提取精度，并且計(jì)算復(fù)雜度較高。③基于不規(guī)則三角網(wǎng)的算法[11-14]。該方法將點(diǎn)云空間劃分為規(guī)則格網(wǎng)，選擇格網(wǎng)中的最低點(diǎn)作為地面點(diǎn)并構(gòu)建三角網(wǎng)，通過判斷非地面點(diǎn)與所在三角形的距離和角度是否滿足所設(shè)閾值進(jìn)而提取地面點(diǎn)。該算法能有效提取地面點(diǎn)云，但針對(duì)密度較大的數(shù)據(jù)，三角網(wǎng)的構(gòu)建過程較復(fù)雜，地面點(diǎn)提取效率低。④RANSAC算法[15-16]。該算法從點(diǎn)云數(shù)據(jù)中隨機(jī)選取3個(gè)點(diǎn)，用這3個(gè)點(diǎn)擬合出一個(gè)平面模型，判斷剩余點(diǎn)到擬合平面的距離與閾值的大小關(guān)系，采用迭代的方式直至擬合出一個(gè)最優(yōu)平面模型，從而提取地面點(diǎn)，但算法存在提取結(jié)果穩(wěn)定性差、精度低等問題。針對(duì)RANSAC算法的缺點(diǎn)，本研究對(duì)其進(jìn)行改進(jìn)，首先使用KD-Tree構(gòu)建點(diǎn)云拓?fù)潢P(guān)系，計(jì)算點(diǎn)云法向量，根據(jù)法向量對(duì)地面點(diǎn)進(jìn)行粗提取，然后利用高程閾值去除非地面點(diǎn)，最后用FPS算法獲取種子點(diǎn)擬合平面實(shí)現(xiàn)地面點(diǎn)的精確提取。經(jīng)實(shí)驗(yàn)驗(yàn)證，改進(jìn)后的RANSAC算法提取結(jié)果更穩(wěn)定、精度更高。

1 研究方法

RANSAC算法由 Fischler和Bolles于1981年最先提出，該算法通過迭代方式從一組包含異常點(diǎn)的數(shù)據(jù)中尋找最優(yōu)的數(shù)學(xué)模型。利用該算法提取地面點(diǎn)時(shí)，隨機(jī)選取3個(gè)點(diǎn)計(jì)算得到初始平面模型，計(jì)算點(diǎn)云中的點(diǎn)到初始平面模型的距離，小于閾值的判定為“內(nèi)點(diǎn)”，大于閾值的判定為“外點(diǎn)”，計(jì)算“內(nèi)點(diǎn)”在點(diǎn)云數(shù)據(jù)中的占比w(公式1)。此外，要保證k次迭代計(jì)算模型每次至少采樣到一個(gè)“外點(diǎn)”去計(jì)算模型的概率P(公式2)。公式如下：

(1)

P=1-(1-wn)k。

(2)

迭代次數(shù)過少會(huì)造成擬合的平面模型不理想，導(dǎo)致提取的地面點(diǎn)不完整且精度較低，故可以設(shè)置最小迭代次數(shù)k(公式3)。為得到更可信的平面模型參數(shù)，在k值的基礎(chǔ)上再加上其標(biāo)準(zhǔn)偏差S(k)(公式4)，得到最終的迭代次數(shù)E(k)(公式5)。通過不斷迭代的方式，取w最大的模型為最優(yōu)平面模型，利用該模型提取地面點(diǎn)云。公式如下：

(3)

(4)

E(k)=k+S(k)。

(5)

1.1 RANSAC算法改進(jìn)

改進(jìn)后的RANSAC算法首先計(jì)算點(diǎn)云法向量，根據(jù)法向量對(duì)地面點(diǎn)進(jìn)行粗提取。遍歷粗提取的地面點(diǎn)云求平均高程，將其作為閾值濾除較高的地物點(diǎn)得到地面點(diǎn)集。然后，從地面點(diǎn)集中隨機(jī)選取1個(gè)點(diǎn)作為種子點(diǎn)，利用最遠(yuǎn)點(diǎn)采樣(farthest point sampling，F(xiàn)PS)算法選取剩余2個(gè)種子點(diǎn)并擬合平面模型。遍歷點(diǎn)云數(shù)據(jù)(除去隨機(jī)采樣的3個(gè)點(diǎn))求每個(gè)點(diǎn)到擬合平面的距離d，將求出的距離d與預(yù)先設(shè)定的數(shù)據(jù)和平面模型間可接受的最大差值α進(jìn)行比較。若點(diǎn)云到平面的距離大于α則判定該點(diǎn)為非平面點(diǎn)，若點(diǎn)云到平面的距離小于α則判定該點(diǎn)為平面點(diǎn)。遍歷完所有點(diǎn)云數(shù)據(jù)之后，統(tǒng)計(jì)平面點(diǎn)的數(shù)量n，與預(yù)先設(shè)定的平面點(diǎn)閾值β進(jìn)行對(duì)比。若n>β，則擬合出的平面模型為最優(yōu)平面模型，可利用最優(yōu)平面模型精確提取地面點(diǎn)。改進(jìn)后的算法流程如圖1所示。

圖1 算法流程

1.2 點(diǎn)云法向量求解

首先求解點(diǎn)云法向量，根據(jù)法向量對(duì)地面點(diǎn)進(jìn)行粗提取，使用KD-Tree將點(diǎn)云空間劃分成不同區(qū)域，根據(jù)設(shè)置的鄰域半徑獲取鄰域點(diǎn)集P{(x1,y1,z1),(x2,y2,z2),…,(xn,yn,zn)}。利用公式(6)計(jì)算點(diǎn)集樣本均值,之后計(jì)算點(diǎn)集協(xié)方差矩陣C，最后計(jì)算協(xié)方差矩陣C的特征值與特征向量，所求最小特征值對(duì)應(yīng)的特征向量即該鄰域點(diǎn)集的局部法向量，見公式(7)和(8)：

(6)

(7)

(8)

根據(jù)法向量提取地面點(diǎn)的具體步驟如下:①利用KD-Tree劃分點(diǎn)云空間，設(shè)置鄰域半徑獲取鄰域點(diǎn)集；②計(jì)算點(diǎn)集樣本均值；③計(jì)算點(diǎn)集協(xié)方差矩陣；④計(jì)算特征值與特征向量，獲取點(diǎn)集法向量；⑤計(jì)算鄰域點(diǎn)集法向量與豎直方向的夾角，與所設(shè)閾值對(duì)比，若夾角小于5°則判定為非地面點(diǎn)。重復(fù)②～⑤，直至遍歷所有點(diǎn)。

1.3 高程濾波

由于利用法向量獲取的地面點(diǎn)云中仍包含部分非地面點(diǎn)，故利用點(diǎn)云高程信息對(duì)地面點(diǎn)云進(jìn)行二次提取。遍歷點(diǎn)云數(shù)據(jù)獲取每個(gè)點(diǎn)的高程值并將其存放在一個(gè)空列表中，求出點(diǎn)云數(shù)據(jù)的平均高程h,并將h作為第一次濾波的閾值。再次遍歷所有點(diǎn)云數(shù)據(jù)，對(duì)比每個(gè)點(diǎn)的高程與閾值h的關(guān)系，若某點(diǎn)的高程大于h，則判定該點(diǎn)為非地面點(diǎn)，若小于h，則判定該點(diǎn)為地面點(diǎn)。通過點(diǎn)云的平均高程無法將非地面點(diǎn)完全濾除，故需要擬合出最優(yōu)平面模型來提取更加精確的地面點(diǎn)云。

1.4 最遠(yuǎn)點(diǎn)采樣

從點(diǎn)云中隨機(jī)選取1個(gè)點(diǎn)作為種子點(diǎn)，利用FPS算法選取剩余2個(gè)種子點(diǎn)，過程如圖2所示。假設(shè)數(shù)據(jù)集S={p1,p2,…,pn}中共有n個(gè)點(diǎn)，在S中隨機(jī)選取1個(gè)點(diǎn)pi(圖2中的白色點(diǎn))作為第1個(gè)種子點(diǎn)；計(jì)算剩余n-1個(gè)點(diǎn)(圖2中的黑色點(diǎn))與白色點(diǎn)的距離，選擇離pi最遠(yuǎn)的點(diǎn)pj作為第2個(gè)種子點(diǎn)，將pi與pj寫入點(diǎn)集S1={pi,pj}；選取剩余n-2個(gè)點(diǎn)計(jì)算其與點(diǎn)集S1中每個(gè)點(diǎn)的距離, 將最短距離作為該點(diǎn)到點(diǎn)集的距離,可得到n-2個(gè)到點(diǎn)集的距離，選取最遠(yuǎn)的點(diǎn)pk作為第3個(gè)種子點(diǎn)寫入點(diǎn)集S1,此時(shí)S1={pi,pj,pk}；利用點(diǎn)集S1中的種子點(diǎn)擬合平面模型，通過迭代的方式擬合出最優(yōu)平面模型，從而精確提取地面點(diǎn)云數(shù)據(jù)。

圖2 最遠(yuǎn)點(diǎn)采樣

2 實(shí)驗(yàn)與分析

為驗(yàn)證本研究所提算法的有效性，利用SSW車載激光掃描系統(tǒng)采集道路場景點(diǎn)云數(shù)據(jù)。采集數(shù)據(jù)時(shí)，設(shè)置激光掃描系統(tǒng)點(diǎn)頻為500 kHz，轉(zhuǎn)速為100 r/s，點(diǎn)云掃描間隔為0.02 m。實(shí)驗(yàn)區(qū)為2019年10月12日于河南焦作采集的某道路場景，如圖3所示。車載LiDAR掃描系統(tǒng)在獲取點(diǎn)云數(shù)據(jù)時(shí)，受采集環(huán)境和設(shè)備自身的影響，獲取的數(shù)據(jù)不可避免地包含噪聲點(diǎn)和離群點(diǎn)，會(huì)影響后續(xù)點(diǎn)云處理，故需要將噪聲點(diǎn)去除。去噪后實(shí)驗(yàn)區(qū)共有1 918 601個(gè)數(shù)據(jù)，主要包括路燈、行道樹、低矮灌木、車輛、地面等。

圖3 實(shí)驗(yàn)區(qū)

2.1 實(shí)驗(yàn)結(jié)果

本算法通過Python語言進(jìn)行編程，利用Open3D對(duì)提取的地面點(diǎn)云進(jìn)行可視化。利用KD-Tree組織點(diǎn)云數(shù)據(jù)，設(shè)鄰域半徑為0.1 m，鄰域搜索最小數(shù)量為32，計(jì)算點(diǎn)云法向量。根據(jù)法向量提取地面點(diǎn)，計(jì)算點(diǎn)云平均高程，濾除部分非地面點(diǎn)，設(shè)模型概率P為0.99、最大迭代次數(shù)為500，擬合最優(yōu)平面模型，精確提取地面點(diǎn)，提取結(jié)果如圖4所示。圖4(a)為RANSAC算法的提取結(jié)果，提取的地面點(diǎn)數(shù)量為1 313 679；圖4(b)為改進(jìn)后RANSAC算法的提取結(jié)果，提取的地面點(diǎn)數(shù)量為1 314 063。兩種算法提取的地面點(diǎn)相差不多，但改進(jìn)后的RANSAC算法提取的地面更加完整。

圖4 提取結(jié)果

2.2 精度分析

提取地面點(diǎn)云的實(shí)驗(yàn)結(jié)果表明，改進(jìn)后的RANSAC算法能夠有效提取城市中道路場景地面點(diǎn)云數(shù)據(jù)，絕大部分行道樹、路燈、汽車、低矮灌木被濾除干凈，同時(shí)大部分地面細(xì)節(jié)特征被保留。為定量分析實(shí)驗(yàn)結(jié)果，本研究使用濾波誤差評(píng)判提取的地面點(diǎn)云數(shù)據(jù)。濾波誤差分為3種，包括一類誤差、二類誤差、總誤差，這3種誤差是國際攝影測量與遙感學(xué)會(huì)(ISPRS)建立的濾波效果評(píng)價(jià)體系。一類誤差又稱拒真誤差，是指將地面點(diǎn)錯(cuò)分成地物點(diǎn)的誤差；二類誤差又稱納偽誤差，是指將地物點(diǎn)錯(cuò)分成地面點(diǎn)的誤差；總誤差是將上述兩種誤差進(jìn)行加權(quán)求和得到的誤差。濾波誤差如表1所示，其中a為地面點(diǎn)正確提取的數(shù)量，b為將地面點(diǎn)錯(cuò)分成地物點(diǎn)的數(shù)量，c為將地物點(diǎn)錯(cuò)分為地面點(diǎn)的數(shù)量，d為地物點(diǎn)分類正確的數(shù)量。

表1 濾波誤差

本研究將實(shí)驗(yàn)區(qū)人工判讀的分類結(jié)果作為準(zhǔn)確值，其中地面點(diǎn)數(shù)量為1 313 498，地物點(diǎn)數(shù)量為605 103。本研究所提算法的精度評(píng)價(jià)結(jié)果如表2所示。

表2 精度評(píng)價(jià)結(jié)果

從表2中可以看出，兩種算法的一類誤差分別為4.04%、2.16%，改進(jìn)后的算法比原算法低1.88個(gè)百分點(diǎn)，表明改進(jìn)后的RANSAC算法(本算法)提取的地面點(diǎn)云更為準(zhǔn)確；兩種算法的二類誤差分別為8.80%、4.79%，改進(jìn)后的算法比原算法低4.01個(gè)百分點(diǎn)，表明本算法將地物點(diǎn)誤判成地面點(diǎn)的數(shù)量更少。兩種算法的總誤差分別為5.54%、2.99%，改進(jìn)后的算法比原算法低2.55個(gè)百分點(diǎn)，表明本算法提取的地面點(diǎn)云精度更高，提取結(jié)果更可靠。由此可知,改進(jìn)后的算法一類誤差、二類誤差和總誤差均低于原算法，表明本算法對(duì)道路場景中地面點(diǎn)云的提取具有較強(qiáng)的適用性。

2.3 穩(wěn)定性分析

利用RANSAC算法提取地面點(diǎn)云，種子點(diǎn)選取具有隨機(jī)性，使得提取結(jié)果不穩(wěn)定，需要多次提取才能獲得較為完整的地面點(diǎn)云。為驗(yàn)證改進(jìn)后的RANSAC算法是否具有更強(qiáng)的穩(wěn)定性，進(jìn)行多次地面點(diǎn)提取實(shí)驗(yàn)并分析改進(jìn)后算法的穩(wěn)定性。共進(jìn)行7次實(shí)驗(yàn)，每次設(shè)置相同的實(shí)驗(yàn)參數(shù)，以提取出的點(diǎn)云數(shù)量作為穩(wěn)定性分析的評(píng)判依據(jù)，穩(wěn)定性分析結(jié)果如表3所示。

表3 穩(wěn)定性分析結(jié)果

為了更直觀地對(duì)比兩種算法的穩(wěn)定性，用表3中兩種算法提取的點(diǎn)云數(shù)量繪制折線圖(圖5)。RANSAC算法隨機(jī)選取3個(gè)種子點(diǎn)擬合平面模型，提取的地面點(diǎn)云數(shù)量起伏較大，精度不穩(wěn)定。改進(jìn)后的RANSAC算法利用點(diǎn)云法向量和高程閾值對(duì)地面點(diǎn)粗提取，通過FPS算法增加了初始種子點(diǎn)為地面點(diǎn)的概率，提取的地面點(diǎn)云數(shù)量變化不大，同時(shí)精度穩(wěn)定在98%，證明改進(jìn)后的算法使得地面點(diǎn)提取結(jié)果更穩(wěn)定。選取其中3組地面點(diǎn)提取結(jié)果并可視化，結(jié)果如圖6與圖7所示。圖6為RANSAC算法提取結(jié)果，從(a)中可以看出提取的地面并不完整；(b)中提取的地面較為完整，同時(shí)大部分地面細(xì)節(jié)特征被保留下來，但存在較多的非地面點(diǎn)；(c)中提取的地面數(shù)據(jù)相對(duì)完整，地物點(diǎn)也較少。圖7為改進(jìn)后的RANSAC算法提取結(jié)果，可以看出提取的地面完整且穩(wěn)定性更強(qiáng)。

圖5 穩(wěn)定性分析

圖6 RANSAC算法提取結(jié)果

圖7 改進(jìn)后的RANSAC算法提取結(jié)果

3 結(jié)論

本研究以車載LiDAR采集的城市道路場景為研究對(duì)象，利用改進(jìn)的RANSAC算法提取地面點(diǎn)云，實(shí)驗(yàn)結(jié)果表明改進(jìn)后算法的一類誤差為2.16%、二類誤差為4.79%、總誤差為2.99%，比原算法的誤差低且精度更高。為驗(yàn)證改進(jìn)后算法的穩(wěn)定性，進(jìn)行了7次地面提取實(shí)驗(yàn)，結(jié)果表明改進(jìn)后算法的穩(wěn)定性更強(qiáng)。