基于改進RANSAC算法的車載LiDAR地面點云提取

李佳佳，李永強，楊亞倫

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

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

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

1 研究方法

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

(1)

P=1-(1-wn)k。

(2)

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

(3)

(4)

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

(5)

1.1 RANSAC算法改進

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

圖1 算法流程

1.2 點云法向量求解

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

(6)

(7)

(8)

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

1.3 高程濾波

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

1.4 最遠點采樣

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

圖2 最遠點采樣

2 實驗與分析

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

圖3 實驗區(qū)

2.1 實驗結果

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

圖4 提取結果

2.2 精度分析

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

表1 濾波誤差

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

表2 精度評價結果

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

2.3 穩(wěn)定性分析

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

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

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

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

圖6 RANSAC算法提取結果

圖7 改進后的RANSAC算法提取結果

3 結論

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