基于多區(qū)域RANSAC的地面點(diǎn)云提取算法

管郡智 潘衛(wèi)清

（1.浙江科技學(xué)院機(jī)械與能源工程學(xué)院 浙江省杭州市 310000 2.浙江科技學(xué)院理學(xué)院 浙江省杭州市 310000）

1 前言

隨著科技的發(fā)展，高精地圖在無(wú)人車應(yīng)用越來(lái)越廣泛，也是無(wú)人車普及的關(guān)鍵一步[2]。而激光雷達(dá)又是高精地圖的重要的傳感器，點(diǎn)云算法的研究也成為感知技術(shù)的重要的一環(huán)?，F(xiàn)在的大多數(shù)無(wú)人車都是在水平的地面上行駛，因此，在平面上檢測(cè)障礙物、測(cè)定相機(jī)相對(duì)于地面的姿態(tài)等等都成為非常有用的技術(shù)。目前已經(jīng)發(fā)展出幾種地面點(diǎn)云的提取方法，文獻(xiàn)[3-4]提出最小二乘法、特征值法等從三維點(diǎn)云中擬合地面，其原理是基于給定的目標(biāo)方程，最大程度地估算和優(yōu)化模型參數(shù)以給定的點(diǎn)云數(shù)據(jù)。由于最小二乘法和特征值法算法本身的局限性，并不能有效地抵制異常數(shù)據(jù)的干擾。這種情況下，文獻(xiàn)[5-7]提出先用隨機(jī)樣本一致性（random sample consensus, RANSAC）算法剔除大量的異常數(shù)據(jù)，再用最小二乘法擬合平面。雖然取得一定的效果，但是應(yīng)用于KITTI 數(shù)據(jù)集上，其地面點(diǎn)云提取的穩(wěn)定性依然沒(méi)有有效解決。本文提出在將點(diǎn)云數(shù)據(jù)分割為多區(qū)域的情況下，結(jié)合RANSAC 和最小二乘法提取地面點(diǎn)云，并用KITTI 的點(diǎn)云數(shù)據(jù)進(jìn)行驗(yàn)證，實(shí)驗(yàn)表明本文的方法可以有效提高地面點(diǎn)云提取的穩(wěn)定性。

2 基于多區(qū)域RANSAC地面點(diǎn)云提取算法

2.1 點(diǎn)云數(shù)據(jù)柵格化處理

將點(diǎn)云數(shù)據(jù)看作是一個(gè)整塊，用最小的長(zhǎng)方體將其包圍，然后根據(jù)點(diǎn)云的實(shí)際尺寸分別設(shè)定長(zhǎng)方體的最小邊長(zhǎng)，再將長(zhǎng)方體劃分為三維的網(wǎng)格，即將點(diǎn)云進(jìn)行柵格化，形成點(diǎn)云數(shù)據(jù)的多區(qū)域分割[8]。

（1）計(jì)算點(diǎn)集合{P1,P2,…,PN}(其中Pi=[xi,yi,zi]T,i=1,2,…,N) XYZ三個(gè)坐標(biāo)軸的最大值和最小值：

（2）確定柵格化邊長(zhǎng)。柵格化的邊長(zhǎng)R 確定了每個(gè)網(wǎng)格里面點(diǎn)的個(gè)數(shù)以及計(jì)算效率。柵格化邊長(zhǎng)R 越小，網(wǎng)格數(shù)量越多，占用的計(jì)算機(jī)資源越多，運(yùn)行速度越低，效率低下。柵格化邊長(zhǎng)R 越大，那地面點(diǎn)云的擬合穩(wěn)定性就越低，就失去柵格化的作用。所以，會(huì)根據(jù)實(shí)驗(yàn)的效果來(lái)確定柵格化的邊長(zhǎng)R。確定了柵格化邊長(zhǎng)之后，就可以計(jì)算點(diǎn)云網(wǎng)格的維度：

（3）計(jì)算柵格化之后每個(gè)點(diǎn)的索引。對(duì)柵格化之后的點(diǎn)云進(jìn)行編碼，確定每個(gè)點(diǎn)所在的網(wǎng)格的編號(hào)。每個(gè)點(diǎn)在網(wǎng)格中的索引h：

表1：不同算法提取地面點(diǎn)云數(shù)量比較

2.2 RANSAC算法

隨機(jī)樣本一致性( random sample consensus, RANSAC)是一種用迭代的方式擬合出數(shù)學(xué)模型參數(shù)的算法，該算法的優(yōu)點(diǎn)是對(duì)包含異常值的數(shù)據(jù)有較好的魯棒性[9-11]。將RANSAC 算法應(yīng)用到地面點(diǎn)云的提取中，除地面點(diǎn)云外，都屬于異常值點(diǎn)云數(shù)據(jù)，具體實(shí)現(xiàn)步驟：

（1）在點(diǎn)云中隨機(jī)選取三個(gè)點(diǎn)并向量的叉乘計(jì)算三個(gè)點(diǎn)所在平面的法向量：

其中，P1=(x1,y1,z1), P2=(x2,y2,z2),P3=(x3,y3,z3)。

（2）計(jì)算點(diǎn)云中任意一點(diǎn)到這個(gè)平面的距離：

其中，Pi為點(diǎn)云中任意一點(diǎn)，i=4,5,…,N。

（3）設(shè)定閾值di<τ 以提取出正常的點(diǎn)云數(shù)據(jù)，將符合條件的點(diǎn)云保存下來(lái)，并記錄點(diǎn)的數(shù)量。

（4）重復(fù)步驟 1) ～ 3) T 次，然后將點(diǎn)數(shù)量最多的點(diǎn)云保存下來(lái)，再用最小二乘法微調(diào)地面點(diǎn)云以擬合出準(zhǔn)確的平面參數(shù)。

在RANSAC 算法中，超參數(shù)τ 和 T 的設(shè)定也非常重要。迭代次數(shù)T 對(duì)模型的影響很大，T 設(shè)置過(guò)大，會(huì)增加運(yùn)行時(shí)間，影響運(yùn)行速度，而運(yùn)行過(guò)小也會(huì)導(dǎo)致擬合不出的平面，不過(guò)可以從理論推導(dǎo)的角度選擇合適迭代次數(shù)T：

其中，e：點(diǎn)云數(shù)據(jù)中異常點(diǎn)的比率；

s：每次迭代選取點(diǎn)的數(shù)量；

T：RANSAC 最大迭代次數(shù)；

p：至少一次選取到正常點(diǎn)的概率。

而τ 選小了則會(huì)漏掉地面點(diǎn)云，選大了會(huì)將異常點(diǎn)云當(dāng)作地面點(diǎn)云，本文以實(shí)驗(yàn)可視化來(lái)確定閾值τ 的大小。這里使用所有點(diǎn)到平面距離的標(biāo)準(zhǔn)差σ 作為閾值：

取τ=2σ, 當(dāng) di>τ=2σ 時(shí)，此點(diǎn)被認(rèn)為是異常值點(diǎn)，不當(dāng)作地面點(diǎn)云提??；反之，為有效值點(diǎn)，被當(dāng)作地面點(diǎn)云提取出來(lái)。

圖1

2.3 最小二乘法

經(jīng)過(guò)RANSAC 初步擬合出地面之后，再用最小二乘法進(jìn)行微調(diào)。由于 RANSAC 擬合帶有隨機(jī)性，且當(dāng)異常值點(diǎn)云的比率e 設(shè)置不正確的情況時(shí)，即使在最大迭代次數(shù)之內(nèi)，也沒(méi)有提取到準(zhǔn)確的地面點(diǎn)云。那就沒(méi)有必要執(zhí)行N 次迭代，設(shè)定一個(gè)期望正常值比率E：

當(dāng)RANSAC 提取的地面點(diǎn)云比上點(diǎn)云總數(shù)大于E 時(shí)，就終止迭代，然后再將提取到的點(diǎn)云用最小二乘再一次擬合，計(jì)算得出的地面模型參數(shù)：

A 為RANSAC 提取的點(diǎn)云組成的矩陣, A=[P1…PS]T且 S

最后，根據(jù)擬合出來(lái)的平面模型參數(shù)，在每個(gè)網(wǎng)格點(diǎn)云中提取出地面點(diǎn)云。

2.4 地面點(diǎn)云提取流程

（1）對(duì)原始點(diǎn)云進(jìn)行柵格化處理，并且對(duì)每一個(gè)網(wǎng)格進(jìn)行編碼；

（2）對(duì)網(wǎng)格里的點(diǎn)云做隨機(jī)樣本一致性，達(dá)到期望正常值比率E 就停止RANSAC 迭代；

（3）根據(jù)（2）步得到的點(diǎn)云，用最小二乘法重新擬合出地面模型的參數(shù)，根據(jù)參數(shù)提取網(wǎng)格中的地面點(diǎn)云；

（4）遍歷所有網(wǎng)格，重復(fù)第（2）步和第（3）步的操作，直到所有網(wǎng)格都提取到地面點(diǎn)云。

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

3.1 實(shí)驗(yàn)數(shù)據(jù)

實(shí)驗(yàn)用到的數(shù)據(jù)選自KITTI 的點(diǎn)云數(shù)據(jù)集，使用python 對(duì)所有算法進(jìn)行仿真，點(diǎn)云數(shù)據(jù)不做任何預(yù)處理，用原始數(shù)據(jù)來(lái)驗(yàn)證本文提出的算法的穩(wěn)定性。

3.2 算法比較

本次實(shí)驗(yàn)挑選的KITTI 某一個(gè)點(diǎn)云數(shù)據(jù)來(lái)比較算法提取地面點(diǎn)云的數(shù)量以及可視化，其中柵格化的尺寸是20 米。由表1 可以看出,提取地面點(diǎn)書最多的是本文提出的算法，從圖1(a)也可以看出，本文算法能夠很穩(wěn)定地將地面點(diǎn)云提取出來(lái)，同時(shí)RANSAC 和最小二乘法的結(jié)合也比純粹的RANSAC 算法效果好很多。

4 結(jié)語(yǔ)

傳統(tǒng)的算法，如隨機(jī)樣本一種性算法和最小二乘法都不能從點(diǎn)云數(shù)據(jù)中穩(wěn)定地提取地面，而地面點(diǎn)云的提取又是眾多工程應(yīng)用的重要環(huán)節(jié)之一。本文提出了在多區(qū)域的情況下，結(jié)合隨機(jī)樣本一致性算法和最小二乘法來(lái)提取激光雷達(dá)掃描到的地面點(diǎn)云，從實(shí)驗(yàn)可以看出算法的穩(wěn)定性。