,,,

(西南交通大學(xué) 信息科學(xué)與技術(shù)學(xué)院,成都 611756)

0 概述

自主移動(dòng)機(jī)器人在未知環(huán)境中移動(dòng),需要根據(jù)位置估計(jì)和地圖進(jìn)行自身定位,同時(shí)在自身定位的基礎(chǔ)上建造增量式地圖,實(shí)現(xiàn)機(jī)器人自主定位和導(dǎo)航。這一過(guò)程被稱為即時(shí)定位與地圖構(gòu)建(Simultaneous Localization And Mapping,SLAM)。在室內(nèi)通常采用特征地圖,因其需要更少的內(nèi)存,能夠更高效全面地提供關(guān)于環(huán)境的信息。被提取的特征通常是幾何特征,如角和線段,在室內(nèi)這些特征是很豐富的,可以對(duì)障礙物進(jìn)行表示,并用于建圖和定位。因此,特征地圖被廣泛地研究并用在SLAM中。

從激光雷達(dá)掃描室內(nèi)環(huán)境所得數(shù)據(jù)中提取直線特征的算法主要有分裂合并法[1-2]、增量法[3]、直線回歸法[4]、霍夫變換(HT)[5-8]、隨機(jī)抽樣一致性算法(RANSAC)[9-10]、期望最大化算法(EM)等[11-12]。激光雷達(dá)對(duì)環(huán)境的掃描數(shù)據(jù)具有極角的排列順序,而RANSAC、HT和EM等算法由于自身的算法特性,不會(huì)利用掃描數(shù)據(jù)點(diǎn)的排列順序,試圖虛假地跨順序擬合直線,造成擬合所得直線的假陽(yáng)性及算法的時(shí)間復(fù)雜度增高。分裂合并法、直線回歸法和增量法則采用線性回歸方法從掃描數(shù)據(jù)中擬合直線,但是當(dāng)掃描數(shù)據(jù)被大量噪聲干擾時(shí),噪聲點(diǎn)參與直線擬合,造成擬合所得直線的精確性下降。因此,從受到噪聲干擾的大規(guī)模離散數(shù)據(jù)點(diǎn)中剔除噪聲點(diǎn),精準(zhǔn)地提取直線特征,構(gòu)建精確地圖,實(shí)現(xiàn)移動(dòng)機(jī)器人在不同時(shí)刻不同位置對(duì)同一目標(biāo)的觀測(cè)值相對(duì)一致顯得十分重要。文獻(xiàn)[13]討論了在SLAM過(guò)程中建圖噪聲去除問(wèn)題的解決方案。文獻(xiàn)[14]采用無(wú)向圖,使用能量函數(shù)最小化的方法從2D激光掃描數(shù)據(jù)中提取直線特征,對(duì)噪聲的抑制具有較好的效果。文獻(xiàn)[15]使用在運(yùn)動(dòng)連續(xù)性和空間連續(xù)性上的物理約束來(lái)確定噪聲點(diǎn),但在構(gòu)建確定性地圖時(shí),計(jì)算復(fù)雜度較高。文獻(xiàn)[16]運(yùn)用圖像處理方法,把原始激光掃描數(shù)據(jù)轉(zhuǎn)換為二值圖像,每一個(gè)掃描點(diǎn)對(duì)應(yīng)一個(gè)像素點(diǎn),對(duì)圖像進(jìn)行腐蝕運(yùn)算,該算法在移除噪聲點(diǎn)的過(guò)程中會(huì)把真實(shí)點(diǎn)移除,雖采用膨脹算法進(jìn)行補(bǔ)救,但仍會(huì)丟失一些真實(shí)點(diǎn),同時(shí)存在轉(zhuǎn)換誤差,且實(shí)時(shí)性差。文獻(xiàn)[17]提出一種自適應(yīng)的圖像線段檢測(cè)器,該方法不需要參數(shù)調(diào)整,可以獲得較精確的提取結(jié)果,但是其提取直線特征速度較慢,達(dá)不到機(jī)器人實(shí)時(shí)精準(zhǔn)建圖的要求。

文獻(xiàn)[18]提出相似三角形法則(STCSM)對(duì)每條真實(shí)直線上的噪聲點(diǎn)服從的隨機(jī)特性進(jìn)行量化。然后利用統(tǒng)計(jì)方法尋找出真實(shí)直線的最優(yōu)方向,以最大程度剔除噪聲點(diǎn)。該方法結(jié)合分裂算法,能快速檢測(cè)線段,滿足機(jī)器人實(shí)時(shí)建圖。但在確定真實(shí)直線最優(yōu)方向的過(guò)程中會(huì)誤剔除數(shù)據(jù)點(diǎn),導(dǎo)致數(shù)據(jù)點(diǎn)信息利用率不高造成直線提取精度不穩(wěn)定。本文針對(duì)上述問(wèn)題提出改進(jìn)型相似三角形去噪算法。通過(guò)雷達(dá)在不同位置對(duì)障礙物環(huán)境進(jìn)行掃描,從獲得的掃描數(shù)據(jù)中提取直線特征。

1 直線特征提取算法

本文直線特征提取算法分為下面的5個(gè)步驟:數(shù)據(jù)預(yù)處理,數(shù)據(jù)分裂[2],改進(jìn)相似三角形法則去噪,去噪數(shù)據(jù)再次分裂,最小二乘直線擬合。激光掃描數(shù)據(jù)點(diǎn)在激光雷達(dá)自身的掃描坐標(biāo)系表示為為極坐標(biāo)形式P(α,r)。數(shù)據(jù)預(yù)處理時(shí)計(jì)算第i個(gè)點(diǎn)Pi(i=2,3,…,m-1,其中m為激光數(shù)據(jù)點(diǎn)的總數(shù))與前后相鄰點(diǎn)Pi-1和Pi+1之間的極徑差值分別為k1和k2。若k1和k2符號(hào)同號(hào),并且其絕對(duì)值均大于閾值dc,則該點(diǎn)作為噪聲點(diǎn)。然后對(duì)預(yù)處理后的數(shù)據(jù)進(jìn)行分裂,得到分裂點(diǎn)集,對(duì)每2個(gè)相鄰分裂點(diǎn)之間的所有數(shù)據(jù)點(diǎn)采用改進(jìn)相似三角形算法去噪。最后對(duì)去噪后的數(shù)據(jù)點(diǎn)重新進(jìn)行分裂,并進(jìn)行最小二乘直線擬合,計(jì)算直線參數(shù)和擬合誤差。

算法直線特征提取算法

輸入原始激光掃描數(shù)據(jù),參數(shù)dc、dth、dr、bin、ε、ds

輸出所有線段所在直線的參數(shù)列表S

1.數(shù)據(jù)預(yù)處理(dc),輸出數(shù)據(jù)集Data1

2.數(shù)據(jù)分裂(dth,Data1),輸出分裂點(diǎn)集合M1

3.foreach M1中每?jī)上噜彿至腰c(diǎn)間的數(shù)據(jù)點(diǎn) do

4.改進(jìn)型相似三角形法則去噪(dr,bin,ε)

5.end

6.輸出數(shù)據(jù)集Data2

7.數(shù)據(jù)分裂(dth,Data2),輸出分裂點(diǎn)集合M2

8.foreach M2中每?jī)上噜彿至腰c(diǎn)間的數(shù)據(jù)點(diǎn)do

9.最小二乘直線擬合(ds)

10.end

11.輸出直線參數(shù)列表S

1.1 相似三角形法則去噪

由于在相鄰2個(gè)分裂點(diǎn)之間的大部分離散點(diǎn)在誤差允許范圍內(nèi)屬于目標(biāo)直線,同時(shí)離散點(diǎn)相對(duì)于真實(shí)目標(biāo)直線左右波動(dòng)的距離關(guān)系可以認(rèn)為服從零均值的正態(tài)分布,因此假設(shè)目標(biāo)直線已知,構(gòu)建一條與目標(biāo)直線相交于點(diǎn)O的參考直線lr,同時(shí)2條直線之間的夾角為γ。令某2個(gè)相鄰分裂點(diǎn)間的m個(gè)離散點(diǎn)構(gòu)成集合{Pi|i=1, 2,…,m},則離散點(diǎn)Pi與Oi、O構(gòu)成RtΔPiOiO,其中Oi是Pi到直線lr的垂線的垂足。此時(shí)所有離散點(diǎn)到目標(biāo)直線距離關(guān)系可被間接量化為某一分布X～M(μ,σ2),且該分布的眾數(shù)為γ,其中X={Xi|Xi=∠PiOOi}。理論上所有屬于目標(biāo)直線的離散點(diǎn)Pi,其對(duì)應(yīng)的Xi會(huì)集中分布于X的眾數(shù)γ。相似三角形去噪算法的執(zhí)行步驟如下[18]:

步驟1在點(diǎn)集U={Pi|i=1,2,…,m;i≠m}中,以離散點(diǎn)Pi作為基準(zhǔn)參考點(diǎn),以點(diǎn)Pi和點(diǎn)Pm兩點(diǎn)擬合直線li′,并以離散點(diǎn)Pi為旋轉(zhuǎn)中心,把直線li′順時(shí)針旋轉(zhuǎn)角度θ(即γ=θ,5°<θ<10°)得到參考直線li,如圖1所示。

圖1 相似三角形法則去噪示意圖

步驟2對(duì)集合W={Pj|j=1,2,…,m-1;j≠i}中的點(diǎn)進(jìn)行遍歷。計(jì)算每一個(gè)點(diǎn)Pj與參考點(diǎn)Pi的距離dj1以及點(diǎn)Pj與參考直線li的距離dj2,求比值cij=dj2/dj1。當(dāng)遍歷完W中所有點(diǎn)后,得到數(shù)據(jù)集Q={cij|j=1,2,…,m-1;j≠i}。

步驟3求數(shù)據(jù)集Q的眾數(shù)。在數(shù)據(jù)集Q的最大值和最小值之間進(jìn)行S等分,得到S個(gè)區(qū)間間隔。統(tǒng)計(jì)在S個(gè)區(qū)間中的最大頻數(shù)ni-max以及該頻數(shù)對(duì)應(yīng)的區(qū)間平均值ci-max。如果ni-max>nmax,那么令nmax=ni-max、cmax=ci-max、num=i,進(jìn)入步驟4;否則,直接進(jìn)入步驟4。其中,眾數(shù)nmax表示對(duì)集合U中每一個(gè)點(diǎn)Pi執(zhí)行算法步驟1～步驟4后經(jīng)比較保存的最大區(qū)間頻數(shù),cmax表示nmax對(duì)應(yīng)區(qū)間的平均正弦比例值,num表示nmax對(duì)應(yīng)的基準(zhǔn)參考點(diǎn)Pi在原始數(shù)據(jù)點(diǎn)中的排列序號(hào)。

步驟4當(dāng)點(diǎn)集U中所有點(diǎn)都作為參考點(diǎn),并執(zhí)行算法步驟1～步驟3后,進(jìn)入步驟5;否則把下一個(gè)離散點(diǎn)Pi+1代替Pi作為基準(zhǔn)參考點(diǎn)并跳轉(zhuǎn)至步驟1。

步驟6計(jì)算Pk(k=1,2,…,m)到直線l′的距離θi,若dk大于閾值dr,則把點(diǎn)Pk記為噪聲點(diǎn)。算法結(jié)束。

相似三角形去噪算法的時(shí)間復(fù)雜度為O(m2),算法可以歸納為尋求函數(shù)J最優(yōu)的過(guò)程:

(1)

其中:

(2)

其中,δ為ci-max對(duì)應(yīng)區(qū)間的長(zhǎng)度。

相鄰分裂點(diǎn)間的所有離散點(diǎn)到目標(biāo)直線的距離關(guān)系可被間接地量化為某一分布X～M(μ,σ2),當(dāng)進(jìn)行正弦函數(shù)映射后,Y=sin(X),Y與X的分布不再一致,在步驟3中求出的ci-max所對(duì)應(yīng)的角度arcsin(ci-max)與X的眾數(shù)值不嚴(yán)格相等。當(dāng)X較小時(shí),Y=sin(X)≈X,此時(shí)Y的分布可以近似為X的分布,角度arcsin(ci-max)則可作為X的眾數(shù)值。由圖1可知,集合{Pj|j=1,2, …,m-1;j≠i}中的任意點(diǎn)Pj,其對(duì)應(yīng)的arcsin(d2/d1)在θ附近波動(dòng),即arcsin(d2/d1)≈θ,而arcsin(d2/d1)正是隨機(jī)變量X的一個(gè)樣本點(diǎn)。所以,取5°<θ<10°,就能使Y的分布與X的分布近似一致。

參數(shù)S的取值將影響γ的精確性,S由式(3)給出:

S=[max(cij)-min(cij)]/bin

(3)

其中,cij∈Q,bin是各區(qū)間間隔值,其實(shí)際取值視需要的精度而定,通常較小。

1.2 改進(jìn)相似三角形去噪法則

當(dāng)集合U={Pi|i=1,2,…,m;i≠m}中的點(diǎn)Pi作為參考點(diǎn)時(shí)構(gòu)建參考直線,并且相似三角形去噪算法步驟3被執(zhí)行完成后,可以得到數(shù)據(jù)Q={cij|j=1,2,…,m-1;j≠i}。假設(shè)cij的分布直方圖對(duì)應(yīng)的輪廓線如圖2所示。

圖2 cij分布直方圖輪廓線

在圖2中,ci-max表示當(dāng)以Pi作為參考點(diǎn)時(shí),數(shù)據(jù)集Q的眾數(shù),ni-max表示ci-max對(duì)應(yīng)的頻數(shù),cih對(duì)應(yīng)圖3中的Ph點(diǎn)。

圖3 參考點(diǎn)Pi鄰域內(nèi)的離散點(diǎn)分布

假設(shè)圖3中直線li′是目標(biāo)直線,左右兩邊的虛線與li′的距離均為dr。由相似三角形去噪算法步驟6可知,離散點(diǎn)到目標(biāo)直線的距離是否大于閾值dr決定該點(diǎn)是否是噪聲點(diǎn)。因此,圖3中2條虛線間區(qū)域內(nèi)的點(diǎn)都不該視為噪聲點(diǎn),在此區(qū)域內(nèi)離散點(diǎn)的位置信息需被利用起來(lái)確定最終的真實(shí)目標(biāo)直線。圖3中點(diǎn)Ph與參考點(diǎn)Pi的距離dh1很小,Ph對(duì)應(yīng)正弦值cih?sinθ。據(jù)相似三角形去噪法則原理,cih不會(huì)被包含在用于確定目標(biāo)直線的離散數(shù)據(jù)點(diǎn)集合;但Ph處于閾值區(qū)域內(nèi),應(yīng)為確定目標(biāo)直線做出貢獻(xiàn)。由上述分析可知,在參考點(diǎn)Pi的某一空間鄰域內(nèi)會(huì)出現(xiàn)較多屬于閾值區(qū)域內(nèi)的Ph點(diǎn),忽略這些點(diǎn)的信息將導(dǎo)致求得的目標(biāo)直線參數(shù)不準(zhǔn)確。本文針對(duì)這一問(wèn)題提出改進(jìn)算法,在相似三角形去噪法則的步驟3之后對(duì)ni-max進(jìn)行更新。

算法ni-max更新

輸入基準(zhǔn)參考點(diǎn)Pi,及對(duì)應(yīng)的分裂區(qū)間點(diǎn)集U、參考直線li、數(shù)據(jù)集Q、ci-max和ni-max

輸出ni-max的更新值

1. 求φ=arcsin(ci-max)

2. 根據(jù)φ、li求出直線lm

3. foreach Pj∈U do

4. if cij?Q

5. 計(jì)算Pj到直線lm的距離dj-m

6. if dj-m>dr

7. ni-max++

8. end

9. end

10. end

11. 輸出ni-max

閾值dr的大小隨著原始探測(cè)數(shù)據(jù)的線性一致性增大而減小。當(dāng)環(huán)境中障礙物表面粗糙程度差異較大時(shí),可對(duì)U中的點(diǎn)進(jìn)行二維PCA處理,dr可自適應(yīng)取值為在次分量方向上數(shù)據(jù)投影的方差;否則可取dr為定值。

1.3 直線擬合及特征提取

當(dāng)所有相鄰分裂點(diǎn)構(gòu)成的線段區(qū)間上的離散點(diǎn)經(jīng)過(guò)相似三角形法則去噪后,對(duì)去噪后的所有點(diǎn)重新執(zhí)行分裂算法,得到精確的分裂點(diǎn)集。按照分裂點(diǎn)的順序,對(duì)相鄰2個(gè)分裂點(diǎn)之間所有非噪聲點(diǎn)的數(shù)目進(jìn)行統(tǒng)計(jì),若點(diǎn)數(shù)小于閾值ds,則舍棄該線段區(qū)間,否則利用最小二乘法擬合直線。擬合所得直線l表示為:

d=rcos(α-θ)

(4)

其中,d為原點(diǎn)到直線l的垂線長(zhǎng),θ為垂線與極軸的逆時(shí)針?lè)较虻膴A角,(α,r)為直線l上的點(diǎn)P(α,r)。

θ和d由式(5)、式(6)給出:

(5)

(6)

(7)

F=

(8)

(9)

其中,N為參與擬合直線l的離散點(diǎn)個(gè)數(shù),F為Jacobian矩陣,C為參與擬合直線l的N個(gè)激光測(cè)距點(diǎn)參數(shù)的協(xié)方差矩陣。

2 實(shí)驗(yàn)結(jié)果與分析

本文使用RPLIDAR360°激光測(cè)距儀對(duì)12 m×6 m的實(shí)驗(yàn)環(huán)境進(jìn)行掃描。雷達(dá)有效測(cè)距半徑為6 m,設(shè)置其掃描間隔為0.25°,得到693個(gè)掃描點(diǎn)。分裂算法的分裂閾值dth為70 mm,相似三角形去噪過(guò)程中的統(tǒng)計(jì)區(qū)間間隔設(shè)為sin 0.5°,距離閾值dr為定值5 mm,再次分裂并擬合直線步驟中的點(diǎn)數(shù)閾值ds為5。測(cè)量極角的方差忽略不計(jì),測(cè)量距離的方差與測(cè)量距離的關(guān)系如圖4所示。

圖4 測(cè)量距離方差與測(cè)量距離的關(guān)系

2.1 算法精度

測(cè)試環(huán)境如圖5(a)所示,實(shí)驗(yàn)中激光雷達(dá)的測(cè)量中心所在位置為原點(diǎn)O,沿其測(cè)量極坐標(biāo)系的極軸方向建立x軸,相應(yīng)建立y軸。采用改進(jìn)相似三角形去噪算法,最終擬合直線的結(jié)果如圖5(b)所示,得到7條直線,與真實(shí)障礙物環(huán)境中的直線相吻合。由于改進(jìn)相似三角形去噪法則能最大程度剔除噪聲點(diǎn)及利用有效點(diǎn)確定真實(shí)直線所在方向,因此沒(méi)有線段合并的過(guò)程。各條擬合所得直線的參數(shù)如表1所示。表1中皮爾遜系數(shù)表示根據(jù)如圖5(b)所示的離散點(diǎn)擬合所得各直線的線性程度。點(diǎn)數(shù)比例表示去噪后參與擬合各條直線的離散點(diǎn)數(shù)在線段區(qū)間上的原始數(shù)據(jù)點(diǎn)數(shù)中所占比例。擬合所得各線段的點(diǎn)數(shù)比例最低為45.07%,平均比例為52.25%。由相似三角形去噪算法改進(jìn)原理可知,算法去噪建立在噪聲點(diǎn)服從正態(tài)分布的隨機(jī)特性基礎(chǔ)上,能避免大量的局部大面積去噪。因此,去噪后的數(shù)據(jù)點(diǎn)能準(zhǔn)確描述真實(shí)直線的信息。相關(guān)系數(shù)最小值為0.999 972,擬合各條直線的離散點(diǎn)線性相關(guān)性均趨近1。由此表明本文算法保證在不丟失原始數(shù)據(jù)絕大部分信息的前提下,利用線性程度較高的數(shù)據(jù)點(diǎn)擬合得到直線參數(shù)。同時(shí),實(shí)驗(yàn)所得直線參數(shù)精度也較高,直線li參數(shù)di的方差的最高數(shù)量級(jí)為10-1mm2,參數(shù)θi的方差的最高數(shù)量級(jí)為10-5rad2,針對(duì)該激光掃描器的特性而言,算法滿足對(duì)環(huán)境的精確建模。

圖5 采用改進(jìn)相似三角形法則提取的環(huán)境直線

直線θ/radd/mmσ2d/mm2σdθ/(mm·rad-1)σ2θ/rad2皮爾遜系數(shù)點(diǎn)數(shù)比例/%L10.276444.96705′1031.20427′10-11.91303′10-44.37536′10-60.99999445.07L20.593222.80229′1039.93612′10-31.58685′10-45.65798′10-60.99999155.38L30.276394.96759′1031.27231′10-12.07484′10-35.67538′10-50.99999251.78L41.930532.88392′1035.24792′10-35.83036′10-51.80895′10-60.99999954.43L50.816253.53996′1031.38402′10-2-1.26114′10-41.80798′10-60.99999854.00L61.928335.00153′1035.40386′10-2-1.48725′10-57.78181′10-80.99997355.06L72.912284.65371′1034.33849′10-23.25620′10-52.02008′10-80.99997250.00

2.2 算法準(zhǔn)確性

把激光雷達(dá)的測(cè)量中心分別平移到如圖6(a)所示標(biāo)號(hào)的位置(xj,yj)處對(duì)環(huán)境進(jìn)行掃描,j=1,2,…,14。雷達(dá)在(x1,y1)處的測(cè)量坐標(biāo)系作為全局不變坐標(biāo)系。因此,直線li(θi,di),i=1,2…,7,在平移前后的雷達(dá)極坐標(biāo)系中的參數(shù)(θi1,di1)、(θij,dij)滿足下式:

Δθi=|θij-θi1|

(10)

(11)

其中,Δθi稱為平移不變性參數(shù),理論上Δθi=0。由于直線li的準(zhǔn)確參數(shù)(θi,di)無(wú)法預(yù)知,因此無(wú)法對(duì)激光雷達(dá)平移前后的直線參數(shù)進(jìn)行式(11)的檢驗(yàn)。但由式(5)、式(6)可知,參數(shù)di的準(zhǔn)確性依賴于θi,直線極角的準(zhǔn)確性在一定程度上能保證極徑的準(zhǔn)確性。因此,對(duì)平移前后的直線參數(shù)進(jìn)行式(10)的檢驗(yàn)即可評(píng)價(jià)算法的準(zhǔn)確性。

激光雷達(dá)在位置(xi,yi)處掃描環(huán)境獲得一幀數(shù)據(jù)時(shí),分別采用傳統(tǒng)分裂合并法、STCSM算法和本文改進(jìn)算法進(jìn)行直線提取。當(dāng)雷達(dá)在所有標(biāo)號(hào)位置處對(duì)環(huán)境掃描結(jié)束,采用每一種算法提取完成直線后,均可得直線極角的集合R={θij|j=1,2,…,14},分別對(duì)3種方法所得集合R的元素進(jìn)行方差分析,結(jié)果如圖6(b)～圖6(h)所示。從圖6(b)～圖6(h)可以看出,采用本文改進(jìn)算法在不同測(cè)量位置提取的各條直線參數(shù)的方差最小,最大數(shù)量級(jí)為10-6rad2,即在機(jī)器人移動(dòng)過(guò)程中保持的直線平移不變性要優(yōu)于采用傳統(tǒng)分裂合并法和STCSM算法。隨著雷達(dá)平移,障礙物輪廓線L1、L2和L3被激光掃描得到的點(diǎn)逐漸減少,同時(shí)激光雷達(dá)在位置11～位置14處時(shí),線段L1不在雷達(dá)0°～180°的視野內(nèi),因此圖6(b)～圖6(d)中所示直線極角參數(shù)的方差相較于其余直線參數(shù)偏大。圖6(e)～圖6(h)表明,在不同位置提取的線段L4～L7角度參數(shù)的波動(dòng)幅度很小,平移不變性參數(shù)Δθi≈0。

西格沃特等[2]的研究結(jié)果表明:就正確性而言,增量法表現(xiàn)最好,其假陽(yáng)性約6%;分裂合并法其次,其假陽(yáng)性約10%;同時(shí)分裂合并法的執(zhí)行速度是所有算法里最快的,但是該算法的精度卻不是最高的。RANSAC、HT、EM算法較于分裂合并法其提取直線的速度非常慢,假陽(yáng)性較高,但是它們能夠產(chǎn)生比其他算法更精確的直線,其原因在于它們有能力去除異常點(diǎn)和噪聲大的有效點(diǎn)。綜上分析,本文提出的基于改進(jìn)相似三角形去噪算法有能力去除異常點(diǎn)或噪聲大的有效點(diǎn)有效提高了提取直線的精度。

圖6 雷達(dá)在不同位置對(duì)環(huán)境掃描并采用不同方法提取直線結(jié)果及對(duì)比

3 結(jié)束語(yǔ)

在相似三角形去噪法則剔除噪聲點(diǎn)過(guò)程中,噪聲點(diǎn)相對(duì)于真實(shí)直線的空間位置所呈現(xiàn)的分布進(jìn)行量化存在非線性量化誤差,進(jìn)而會(huì)剔除部分有效點(diǎn)。本文提出的改進(jìn)相似三角形去噪算法降低了誤剔除有效點(diǎn)的數(shù)量。在12 m×6 m的障礙物環(huán)境中進(jìn)行實(shí)驗(yàn),得到在0°～180°的掃描范圍內(nèi)693個(gè)點(diǎn)。直線參數(shù)極徑di的方差數(shù)量級(jí)在10-1mm2以下,極角θi方差的數(shù)量級(jí)最高為10-5rad2。激光雷達(dá)在不同位置對(duì)環(huán)境掃描并提取直線的角度參數(shù)的方差數(shù)量級(jí)最大為10-6rad2。實(shí)驗(yàn)結(jié)果表明,本文提出的改進(jìn)算法在直線提取的準(zhǔn)確性和精度方面都優(yōu)于傳統(tǒng)分裂合并法、增量法、直線回歸法、RANSAC、HT和EM算法,對(duì)室內(nèi)機(jī)器人精準(zhǔn)魯棒地實(shí)時(shí)地圖構(gòu)建、路徑規(guī)劃、全局定位具有重要意義。

[1] PAVLIDIS T,HOROWITZ S L.Segmentation of Plane Curves[J].IEEE Transactions on Computers,1974,23(8):860-870.

[2] NGUYEN V,MARTINELLI A,TOMATIS N,et al.A Comparison of Line Extraction Algorithms Using 2D Laser Rangefinder for Indoor Mobile Robotics[C]//Proceedings of IEEE/RSJ International Conference on Intelligent Robots and Systems.Washington D.C.,USA:IEEE Press,2005:1929-1934.

[3] AHMAD H,NAMERIKAWA T.Robot Localization and Mapping Problem with Unknown Noise Charac-teristics[C]//Proceedings of IEEE International Conference on Control Applications.Washington D.C.,USA:IEEE Press,2010:1275-1280.

[4] ARRAS K O,SIEGWART R Y.Feature Extraction and Scene Interpretation for Map-based Navigation and Map Building[C]//Proceedings of MRXI’97.[S.1.]:SPIE Press,1997:42-53.

[5] WANG C F.Fast Line Extraction Algorithm Based on Improved Hough Transformation[J].Advanced Materials Research,2014(926-930):3612-3615.

[6] XU Zezhong,SHIN B,KLETTE R.Accurate and Robust Line Segment Extraction Using Minimum Entropy with Hough Transform[J].IEEE Transactions on Image Processing,2015,24(3):813-822.

[7] 王競(jìng)雪,朱 慶,張?jiān)粕?等.疊置分區(qū)輔助的相位編組直線提取算法[J].測(cè)繪學(xué)報(bào),2015,44(7):768-774,790.

[8] 張 帆,高云龍,黃先鋒,等.基于球面投影的單站地面激光點(diǎn)云直線段提取方法[J].測(cè)繪學(xué)報(bào),2015,44(6):655-662.

[9] CANAZ S,KARSLI F,GUNEROGLU A,et al.Automatic Boundary Extraction of Inland Water Bodies Using LiDAR Data[J].Ocean and Coastal Management,2014,118(1):158-166.

[10] FISCHLER M A,BOLLES R C.Random Sample Consensus:A Paradigm for Model Fitting with Application to Image Analysis and Automated Cartography[J].Communications of the ACM,1981,24(6):381-395.

[11] NGUYEN V,GACHTER S,MARTINLLI A,et al.A Comparison of Line Extraction Algorithms Using 2D Range Data for Indoor Mobile Robotics[J].Autonomous Robots,2007,23(2):97-111.

[12] PFISTER S,ROUMELIOTIS S L,Burdick J W.Weighted Line Fitting Algorithms for Mobile Robot Map Building and Efficient Data Representation[C]//Proceedings of IEEE International Conference on Robotics and Automation.Washington D.C.,USA:IEEE Press,2003:1304-1311.

[13] RAO A,MULLANE J,WIJERUPAGE W S,et al.SLAM with Adaptive Noise Tuning for the Marine Environment[C]//Proceedings of OCEANS’11.Washington D.C.,USA:IEEE Press,2011:1-6.

[14] LI Xinzhao,LIU Yuehu,NIU Zhenning,et al.A Line Segments Extraction Based Undirected Graph from 2D Laser Scans[C]//Proceedings of the 17th IEEE International Workshop on Multimedia Signal Processing.Washington D.C.,USA:IEEE Press,2015:1-6.

[15] YE Cang,BORENSTEIN J.A Novel Filter for Terrain Mapping with Laser Rangefinders[J].IEEE Transactions on Robotics,2004,20(5):913-921.

[16] RAVANKAR A A,HOSHINO Y,RAVANKAR A,et al.Algorithms and a Frame Work for Indoor Robot Mapping in a Noisy Environment Using Clustering in Spatial and Hough Domains[J].International Journal of Advanced Robotic Systems,2015,12(3):57-62.

[17] GROMPONE V G,RAFAEL,JAKUBOWICZ J,et al.LSD:A Fast Line Segment Detector with a False Detection Control [J].IEEE Transactions on Pattern Analysis and Machine Intelligence,2008,32(4):722-732.

[18] JIAN Ming,ZHANG Cuifang,YAN Fei,Tet al.A Global Line Extraction Algorithm for Indoor Robot Mapping Based on Noise Eliminating via Similar Triangles Rule[C]//Proceedings of the 35th IEEE China Control Conference.Washington D.C.,USA:IEEE Press,2016:6133-6138.