高春艷，申紫銘，張明路，田 穎

一種基于RANSAC的點(diǎn)云柱狀化軸線特征表示法

高春艷，申紫銘，張明路，田 穎

(河北工業(yè)大學(xué)機(jī)械工程學(xué)院，天津 300130)

現(xiàn)有的三維地圖構(gòu)建算法多強(qiáng)調(diào)對地圖構(gòu)建的精確性，導(dǎo)致成圖效率低、成本高。為了提高建立地圖的效率，提出了一種對地標(biāo)性物體進(jìn)行圓柱體識別與提取并以其軸線特征作為地標(biāo)構(gòu)建簡化地圖的改進(jìn)算法。基于隨機(jī)采樣一致算法（RANSAC）對點(diǎn)云模型中的待提取主體模型生成待估計(jì)圓柱模型并進(jìn)行匹配，通過對單應(yīng)性矩陣及其誤差函數(shù)的計(jì)算得到迭代過程中的最佳閾值，以得到最佳匹配圓柱模型并提高提取效率，然后用所提取的圓柱軸線描述地標(biāo)的空間位置，圓柱半徑描述地標(biāo)的空間幾何信息。通過與傳統(tǒng)RANSAC方法的仿真實(shí)驗(yàn)對比，證明該方法可以有效的精簡地圖，為后續(xù)識別地標(biāo)路徑規(guī)劃奠定基礎(chǔ)。

點(diǎn)云；三維地圖；特征提?。籖ANSAC

目前三維點(diǎn)云地圖常采用改進(jìn)的ICP算法進(jìn)行創(chuàng)建[1]，生成的三維地圖精度較高，對環(huán)境的細(xì)節(jié)描述精細(xì)，所以存在著成本高、效率低、實(shí)時(shí)性差等問題。但在多路徑規(guī)劃與導(dǎo)航設(shè)計(jì)時(shí)并不要求地圖過度精確，而是追求地圖的實(shí)用性和快速響應(yīng)，因此，需要對地圖進(jìn)行盡可能的簡化，簡化的三維地圖構(gòu)建的基礎(chǔ)通常是點(diǎn)云特征提取的結(jié)果[2]?？臻g特征提取算法主要分為2大類[3]：①基于邊界的算法，主要通過計(jì)算獲得點(diǎn)云表面的法矢、曲率等微分幾何變量的突變特性來提取特征，缺點(diǎn)是對噪聲較為敏感，魯棒性較低。②基于面域的算法，通過提取點(diǎn)云數(shù)據(jù)中具有共同屬性的點(diǎn)集構(gòu)造出穩(wěn)定的生長區(qū)域進(jìn)行生長，然后實(shí)現(xiàn)特征提取，主要有隨機(jī)采樣一致算法(random sample consensus，RANSAC)、最小中值算法和霍夫變換等[4]，雖然該類方法在提取特征時(shí)可以有效避免噪聲的影響，但其實(shí)時(shí)性較差。平面特征提取的方法還有最小二乘法、特征值法等[5-8]，但其不能有效抵御異常值的影響且只能擬合平面，對空間形狀的擬合效果較差。

為解決三維地圖構(gòu)建過程中實(shí)時(shí)性差，效率低等問題，本文提出了一種地標(biāo)物體柱狀化的方法，針對圓柱特征的提取在RANSAC算法[9]的基礎(chǔ)上進(jìn)行了改進(jìn)，首先基于RANSAC算法在點(diǎn)云中隨機(jī)生成一個(gè)圓，然后將圓形拉伸形成圓柱與點(diǎn)云模型進(jìn)行匹配，當(dāng)點(diǎn)云數(shù)據(jù)中的點(diǎn)到軸線的距離與半徑符合條件的數(shù)量達(dá)到所設(shè)定的閾值時(shí)得到最終的匹配圓柱模型，為了減少匹配過程中的迭代計(jì)算次數(shù)，通過實(shí)驗(yàn)篩選出最佳閾值檢測去除異常值并限定搜索區(qū)域。

1 基于RANSAC的物體柱狀化軸線提取

1.1 基于RANSAC的物體柱狀化處理

RANSAC算法是從一組數(shù)據(jù)集中通過迭代的方式匹配已給出的數(shù)學(xué)模型參數(shù)，最后通過估計(jì)局內(nèi)點(diǎn)與模型的錯(cuò)誤率來評估模型的精度[10]，因此傳統(tǒng)的RANSAC算法具有一定的不確定性，其有一定的概率得到一個(gè)高精度的估計(jì)模型，但為了提高概率又必須提高迭代次數(shù)，影響計(jì)算效率，而迭代次數(shù)過低又很可能會因抽樣不充分導(dǎo)出錯(cuò)誤的估計(jì)模型[11]。

本文采用限制迭代次數(shù)上限的方法對圓柱體進(jìn)行識別匹配。即先基于RANSAC給出匹配圓柱模型，通過閾值檢測去除異常值以及限定搜索區(qū)域減小迭代次數(shù)，提高模型的精度。設(shè)為最少必要模型點(diǎn)個(gè)數(shù)，個(gè)點(diǎn)為局內(nèi)點(diǎn)的概率為，點(diǎn)集的總數(shù)為，所有局外點(diǎn)數(shù)為N，隨機(jī)選取一個(gè)點(diǎn)為局外點(diǎn)的概率為，則=N/。個(gè)點(diǎn)全部為局內(nèi)點(diǎn)的概率為(1–), 1–(1–)表示個(gè)點(diǎn)中至少有一個(gè)為局外點(diǎn)的概率，則(1–(1–))表示個(gè)點(diǎn)恒不可能全部為局內(nèi)點(diǎn)的概率，其應(yīng)與1–相等[12-14]，即1–(1–(1–))，等式兩邊取對數(shù)得

其中，k為算法的迭代次數(shù)(抽樣次數(shù))，迭代時(shí)n取大于k的值。k與N的關(guān)系如圖1所示。

由圖1可看出，在與確定的情況下，局外點(diǎn)率越大，迭代次數(shù)也就越大，為減少迭代次數(shù)，提高算法效率，在點(diǎn)的選取時(shí)應(yīng)進(jìn)行對搜索區(qū)域限定的自適應(yīng)調(diào)整，降低局外點(diǎn)所占的比例。

改進(jìn)的RANSAC算法提取圓柱的步驟如下：

步驟1.給定搜索區(qū)域，在該區(qū)域內(nèi)選定一組待處理的點(diǎn)云集{1,2,···,P}，不共線的3個(gè)點(diǎn)確定一個(gè)圓，設(shè)圓所在平面為，隨機(jī)選取其中的3個(gè)點(diǎn){P,P,P|,,[1，]且≠≠}，如圖2所示。

圖2 圓與軸線的選擇原理圖

步驟2.計(jì)算3個(gè)點(diǎn)構(gòu)成的圓的圓心坐標(biāo)及半徑(0，0，)，如圖3所示，在圓心坐標(biāo)處建立與圓所在平面垂直的軸線，生成與圓半徑相等的圓柱體，計(jì)算點(diǎn)云集中的各點(diǎn)到軸線的距離l。

步驟3.設(shè)置符合條件的點(diǎn)的閾值，記錄滿足l∈[–,+]的點(diǎn)云集{1,2,···,Q}，當(dāng)=/≥時(shí)，停止迭代。

步驟4.檢驗(yàn)所得模型是否達(dá)到預(yù)期要求，若是，則進(jìn)入下一步，否則回到步驟1。

步驟5.將得到的若干組數(shù)據(jù)進(jìn)行比較，選出最符合預(yù)期要求的模型。

流程圖如圖4所示。

圖3 點(diǎn)到軸線距離原理圖

圖4 圓柱模型提取流程圖

1.2 柱狀化軸線的提取

設(shè)在平面得到的3個(gè)點(diǎn)的空間坐標(biāo)為1(1,1,1),2(2,2,2),3(3,3,3),圓心坐標(biāo)為(0,0,0)，半徑為。若得到軸線方程，需先求3個(gè)點(diǎn)所確定的空間圓的圓心坐標(biāo)和半徑，分析可得約束條件：

(1)1,2,3∈；

(2) |1|=|2|=|3|。

可得空間3點(diǎn)確定的平面方程為

求解行列式得