楊忠炯，王臣臣，周立強，易圣先

（中南大學(xué)，長沙 410000）

0 引言

同時定位與建圖是近些年來機器人領(lǐng)域研究的熱門話題，是實現(xiàn)機器人在未知環(huán)境自主導(dǎo)航的關(guān)鍵技術(shù)。SLAM技術(shù)是指機器人能夠在未知環(huán)境中，通過自身攜帶的傳感器來獲取外界信息和自身位姿，以此建立起環(huán)境地圖和完成自身定位，并在運動中完成地圖與自身位姿的更新。

機器人攜帶的傳感器包括激光傳感器，相機，毫米波雷達等，其中激光傳感器由于其具有同時精確測量距離和方位角的能力，并且受環(huán)境影響較小的特點，被廣泛應(yīng)用于各類機器人導(dǎo)航與定位系統(tǒng)。特征地圖因其占用內(nèi)存小，能夠高效，全面地表示環(huán)境信息，因而被廣泛應(yīng)用在室內(nèi)移動機器人定位中。而構(gòu)造特征地圖的首要任務(wù)就是環(huán)境特征的提取，常見的環(huán)境特征通常是指幾何環(huán)境特征，比如線段、角、圓等。而在實際環(huán)境中，最常見的特征之一就是線段特征。由激光傳感器掃描環(huán)境所得的數(shù)據(jù)中提取線段特征的算法目前主要有霍夫變換，回歸法，增量法，分裂合并法等。文中提出一種基于密度聚類的線段特征提取方法。

1 聚類

聚類是一種應(yīng)用廣泛的數(shù)據(jù)挖掘技術(shù)，很多領(lǐng)域都應(yīng)用到了聚類算法，包括機器學(xué)習(xí)，圖像處理等。聚類將數(shù)據(jù)按照其相似程度不一的特性講其劃分為不同的簇，同一簇內(nèi)數(shù)據(jù)相似程度高，不同簇內(nèi)數(shù)據(jù)相似程度較低。聚類算法得到了廣泛的研究，許多學(xué)者提出了不同類型的聚類算法，包括原型聚類，密度聚類，層次聚類等。對于從激光傳感器獲取的數(shù)據(jù)，可以用距離來表征數(shù)據(jù)之間的相似性。距離計算可以采用5種方式：歐式距離，馬氏距離，夾角余弦距離，二值特征的夾角余弦測度，二值特征的Tanimoto測度。鑒于向量間歐式距離計算簡便，且基于歐式距離的分類方法使用效果好，因此文中采用歐式距離聚類方法。

相鄰兩點xj和xj+1之間的歐式距離為記為disted（xj,xj+1）, 設(shè)xj，xj+1的特征向量分別為：

2 基于密度聚類的線段特征提取方法

機器人在室內(nèi)運動時，遇到線段特征的概率是非常大的，比如桌子，窗戶，房梁等，因此對線段特征進行提取就非常有必要。對線段特征進去提取就是要從激光傳感器掃描的數(shù)據(jù)點進行分析，處理，識別出其中的線段特征。

由于激光傳感器采集數(shù)據(jù)是一個實時的過程，所以采集到的數(shù)據(jù)就不可避免地存在噪聲，這些噪聲會嚴(yán)重干擾地圖的創(chuàng)建，因此在正式的環(huán)境特征提取之前，必須對原始數(shù)據(jù)進行去噪處理，即對數(shù)據(jù)進行預(yù)處理。此外，激光傳感器采集的原始數(shù)據(jù)是完全混合在一起的，為了能夠更好地提取環(huán)境特征，需要對數(shù)據(jù)進行區(qū)域分割，使其準(zhǔn)確地劃分為各個路標(biāo)的數(shù)據(jù)集。

由此，文中基于激光傳感器數(shù)據(jù)的線段環(huán)境特征提取算法由激光傳感器數(shù)據(jù)預(yù)處理，基于聚類的區(qū)域分割和參數(shù)擬合三部分組成。

2.1 數(shù)據(jù)預(yù)處理

在分析激光傳感器數(shù)據(jù)和特征提取的過程中發(fā)現(xiàn)，激光傳感器數(shù)據(jù)仍然存在一些不可忽視的問題，這些問題會對特征提取算法的魯棒性，精度以及時效性帶來不良影響，這些問題主要包括：

1）噪聲。傳感器受其使用環(huán)境和自身精度影響都不可避免地會產(chǎn)生噪聲，激光傳感器也不例外。噪聲干擾會導(dǎo)致數(shù)據(jù)中出現(xiàn)一些孤立的點，但是這并不是真實的觀測數(shù)據(jù)，反而會干擾算法結(jié)果，所以預(yù)先予以濾除。

2）數(shù)據(jù)離散化誤差。激光傳感器數(shù)據(jù)是高度離散化的，當(dāng)目標(biāo)與激光傳感器距離較遠時，其離散化誤差也就越大，因此需要對距離較遠的數(shù)據(jù)濾除，以防干擾算法結(jié)果。

為了減小上述因素對特征提取的影響，需要對原始數(shù)據(jù)進行濾波處理，常用的濾波算法有中值濾波，高斯濾波和均值濾波等算法。文中采用中值濾波方法對激光數(shù)據(jù)平滑處理。

中值濾波是一種非線段性平滑技術(shù)，把數(shù)據(jù)集中一點的值用其領(lǐng)域內(nèi)各個點的中值代替，從而減小數(shù)據(jù)的離散性，使其更加接近真實值。中值濾波算法主要取決于窗口N。

計算公式如下：

式中N表示窗口大小，pmid代表中值，mid是取中值的函數(shù)，pi表示原始數(shù)據(jù)。

算法：中值濾波算法；

輸入：激光傳感器數(shù)據(jù)；

輸出：去除噪聲后的中值數(shù)據(jù)；

1）選擇一個窗口大小N；

2）帶入數(shù)據(jù)p1-pN；

3）把p1-pN排序，并計算出中位數(shù)pmid；

4）窗口中數(shù)據(jù)的中間數(shù)替換為pmid；

5）窗口數(shù)據(jù)前移一位，并重復(fù)3），4）步驟；

6）窗口到達右端終點，中值濾波完成。

經(jīng)過以上的數(shù)據(jù)處理，能夠有效地減小離散化誤差，部分偏離線段的數(shù)據(jù)點向線段集中，所保留下來的數(shù)據(jù)都盡量接近真實值，為后面的算法順利實現(xiàn)做出了保障。

2.2 基于密度聚類的區(qū)域分割算法

區(qū)域分割是根據(jù)數(shù)據(jù)點的位置分布，劃分可能屬于同一個特征的數(shù)據(jù)點集。理論上，每個點集對應(yīng)一個線段特征。SLAM研究的是未知環(huán)境，對于環(huán)境是沒有任何先驗知識的，因此對當(dāng)前數(shù)據(jù)應(yīng)該分割成多少個子集是完全不知道的，這恰恰和機器學(xué)習(xí)中的聚類分析相一致。文中采用基于密度聚類的算法對激光數(shù)據(jù)進行區(qū)域分割。

DBSCAN是一種著名的密度聚類算法，它把具有足夠高密度的數(shù)據(jù)劃分為一簇，并能夠在噪聲的干擾下發(fā)現(xiàn)任意形狀的簇。DBSCAN基于一組“鄰域”參數(shù)

來判斷數(shù)據(jù)的緊密程度，對于某數(shù)據(jù)集D（x1，x2，…，xm），有以下五個定義：

1）鄰域：空間內(nèi)任意一點xi的鄰域是以該點為圓心，半徑為ρ的圓形區(qū)域內(nèi)的點的集合。記為Nρ（xi）={xj∈D│dist（xi，xj）≤ρ}，dist（xi，xj）表示xi和xj之間的距離。

2）核心對象：若xi的的鄰域內(nèi)至少包含MinPts個樣本，則xi是一個核心對象。

3）密度直達：若xj在xi的鄰域內(nèi)，且xi是核心對象，則xj由xi密度直達。

4）密度可達：若存在α1，α2，…，αn，其中α1=xi，αn=xj，且αi+1由αi密度直達，則xj由xi密度可達。

5）密度相連：若xk使得xj和xi均由xk密度可達，則xj和xi密度相連。

圖1 DBSCAN基本概念圖

如圖1所示，紅色線段大圓表示其鄰域，x1是核心對象，x2由x1密度直達，x3由x1密度可達，x3與x4密度相連?；谏鲜龆x，DBSCAN將簇定義為：由密度可達關(guān)系導(dǎo)出的密度相連樣本集合。文中用歐式距離來表征數(shù)據(jù)點之間的相似性，其DBSCAN算法的具體步驟如下：

1）確定樣本鄰域ρ，MinPts，設(shè)區(qū)域分割之前的數(shù)據(jù)集B（x1，x2，…，xn），

2）從數(shù)據(jù)集中任意選取一個點x1，判斷|Nρ（xi）|≥MinPts是否成立，若成立，則xi為核心對象，加入核心對象集合B中。

3）從集合B中隨機選擇一個核心對象xj，尋找由它密度可達的所有點，將其加入一個新的集合C1，形成第一個聚類簇，并將C1中包含的核心對象從B中去除。

4）繼續(xù)訪問數(shù)據(jù)集中的下一個點，重復(fù)以上過程，直到處理完數(shù)據(jù)集中所有的點，得到m個聚類簇Cm。

5）將沒有包含在聚類簇中的數(shù)據(jù)視為噪聲干擾，予以刪除。

2.3 參數(shù)擬合

經(jīng)過上述對數(shù)據(jù)的處理后，下面就要對聚類得到的集合ci中的數(shù)據(jù)點進行線段特征擬合。文中采用最小二乘法進行參數(shù)擬合。

圖2 線段特征在坐標(biāo)系下的表示

如圖2所示，線段表達為：

ρ為極點到線段的距離，α為極點和線段的垂線段和x軸的夾角。最小二乘法原理：當(dāng)所有的點到線段的距離（Δρ）的平方之和最小時，此線段可以被認(rèn)為是對所有點的最好的線段擬合，即：

上述的（xm，ym）是第m個數(shù)據(jù)點在坐標(biāo)系下的坐標(biāo)，上面的公式分別對α和ρ求偏導(dǎo)等于0得：

可得線段參數(shù)：

綜上所述，所求得使式(6)成立的α，ρ代入式(5)，所得即為線段特征。

3 結(jié)束語

文中針對基于激光傳感器的線段特征提取，引入密度聚類的方法，其基本技術(shù)路線圖如圖3所示。

圖3 基本技術(shù)路線圖

本方法通過引入密度聚類的思想對激光傳感器數(shù)據(jù)進行區(qū)域分割，提出了一種新的線段特征提取方法。首先對原始數(shù)據(jù)進行濾波處理，去除噪聲，然后基于密度聚類進行區(qū)域分割，并去除不合理特征點，最后采用最小二乘法進行參數(shù)擬合，完成線段特征提取。對slam算法中的特征提取的準(zhǔn)確性和魯棒性的提升有借鑒意義。