基于假設(shè)檢驗的室內(nèi)環(huán)境多特征檢測方法

霍光磊，趙立軍，李瑞峰，呂明睿

（哈爾濱工業(yè)大學(xué)機器人技術(shù)與系統(tǒng)國家重點實驗室，黑龍江哈爾濱150001）

基于假設(shè)檢驗的室內(nèi)環(huán)境多特征檢測方法

霍光磊，趙立軍，李瑞峰，呂明睿

（哈爾濱工業(yè)大學(xué)機器人技術(shù)與系統(tǒng)國家重點實驗室，黑龍江哈爾濱150001）

為解決移動機器人室內(nèi)環(huán)境特征提取適應(yīng)性問題，提出了基于假設(shè)檢驗的室內(nèi)多特征檢測方法。該方法首先構(gòu)建多維數(shù)據(jù)空間。通過定義距離概率函數(shù)，結(jié)合χ2假設(shè)檢驗理論，在估計采樣點的特征區(qū)域基礎(chǔ)上，通過極值法進行角點檢測，然后采用約束最小二乘法提取線段與圓弧特征。最后，實驗驗證了該方法可以提取較穩(wěn)定的角點、線段以及圓弧特征，同時特征的識別率達到94%以上。

室內(nèi)環(huán)境；假設(shè)檢驗；特征；機器人；多特征檢測；最小二乘法

采用激光測距傳感器的SLAM技術(shù)已成為移動機器人感知未知環(huán)境的基本能力，而環(huán)境地圖構(gòu)建產(chǎn)生的大量數(shù)據(jù)和高維數(shù)據(jù)空間問題，限制了機器人的應(yīng)用。近年來用于解決該問題的特征提取方法取得一定成果。相關(guān)的匹配方法主要有［2］：點到點［3］、點到特征［4］與特征到特征［5］。

室內(nèi)環(huán)境主要特征包括角點特征，線段特征與圓弧特征［6］。Weber提出了一種新的算法—錨點提取算法（anchor point relation，APR）［7］，以錨點信息為路標(biāo)，引導(dǎo)機器人定位，然而錨點不能反映路標(biāo)幾何外觀，影響環(huán)境特征精確描述。Yan等［8］采用角點特征匹配，獲得機器人定位信息，但是這種方法需要其他特征支持。線段特征提取方法有Split?Merge算法［9］，采用遞歸原理，其計算量與拐點個數(shù)成正比。Noyer等［10］利用激光傳感器的性質(zhì)與極坐標(biāo)系下掃描點的幾何不變性結(jié)合提取線段特征；Su?Yong等［11］利用線段特征為路標(biāo)，通過Rao?Blackwellized粒子濾波器實現(xiàn)機器人的室內(nèi)SLAM，減少了地圖存儲數(shù)據(jù)量；以上方法適用于單特征環(huán)境。Syed Riaz等［12］通過匹配角點與線段兩種特征表示環(huán)境，實現(xiàn)機器人定位，但該方法不適合帶有曲線的環(huán)境。

針對曲線特性，F(xiàn)eng等［13］使用無跡卡爾曼濾波器方法估計曲線特征，但在復(fù)雜環(huán)境中運算開銷大；Liu等［14］采用局部曲率尺度方法提取角點、線段以及圓弧特征，無法區(qū)分圓弧的類線段特征。

綜上所述，激光傳感器提取特征有如下問題：1）傳統(tǒng)方法關(guān)注于單一特征，忽略多特征及耦合問題；2）在特征過渡條件下，特征區(qū)分難度大。本文將統(tǒng)計學(xué)和優(yōu)化方法結(jié)合，提出一種綜合角點、線段與圓弧多特征識別方法，解決環(huán)境多特征檢測問題。

1 特征初分類

激光傳感器掃描數(shù)據(jù)的極坐標(biāo)表示為：sk＝（ρk，θk），k＝1，2，…，N，其中N為掃描數(shù)據(jù)個數(shù)，sk為帶噪聲數(shù)據(jù)，（ρk，θk）服從高斯白噪聲分布且相互獨立，即ρk～N（μρk，σρ2），θk～N（μθk，σθ2）。

室內(nèi)環(huán)境中，大多數(shù)物體是相互分開的，環(huán)境聚類是為了將激光傳感器可能掃描到同一物體的掃描點分為一類［15］。在聚類的環(huán)境基礎(chǔ)上對每一段采樣點采用一維高斯核對掃描點做卷積（斷點除外），然后對采樣點做降采樣處理，構(gòu)建多維數(shù)據(jù)空間。

在降維后的數(shù)據(jù)空間下，描述環(huán)境的每個數(shù)據(jù)點與其左右鄰域的若干點的關(guān)聯(lián)性，需要檢測每個采樣點及其鄰域內(nèi)的點。采用假設(shè)檢驗的方法，先估計采樣點鄰域的特征，然后確定采樣點自身特征。

1.1 左右鄰域特征處理

在極坐標(biāo)下，線段方程為非線性方程，角分線函數(shù)為

式中：ρi為當(dāng)前采樣點的極徑，ρ?i±j為鄰域內(nèi)相對采樣點i的第j個采樣點極徑的估計值，Δθ為激光傳感器的角度分辨率，±號分別表示左右鄰域，ρi±2j為相對采樣點i的第2j個采樣點的極徑。

在線段環(huán)境下，ρ?i±j是ρi±j的無偏估計，且ρi是相互獨立的。根據(jù)假設(shè)檢驗有

接受域H0：當(dāng)前采樣點的鄰域為線段；拒絕域H1：當(dāng)前采樣點的鄰域為圓弧、角點或者其他特征。

在采樣點i的鄰域內(nèi)，其他采樣點j相對i的距離與特征信息緊密程度相關(guān)，越近相關(guān)性越緊密，但冗余信息越多，反之，則相反。定義相對采樣點的緊密程度概率密度函數(shù)pi±j為

式中：di±j為采樣點j到當(dāng)前采樣點i的距離；μd為最緊密距離；σd為對分布的影響，μd、σd需人為給定。樣本方差為

在樣本空間內(nèi)，已知采樣方差，選擇統(tǒng)計量為

采樣點滿足式（8）的鄰域可能為線段特征。在拒絕域H1上滿足：

滿足式（9）的采樣點鄰域為非線段特征。

1.2 當(dāng)前采樣點特征

估計當(dāng)前采樣點特征的方法仍采用χ2假設(shè)檢驗方法。特征估計采用左右鄰域采樣點向當(dāng)前采樣點投影的方法，投影函數(shù)如下

式中：ρi+j表示當(dāng)前采樣點i左鄰域內(nèi)的采樣點j的極徑，ρi-j表示當(dāng)前采樣點i右鄰域內(nèi)的采樣點j的極徑，表示左右鄰域內(nèi)采樣點j對當(dāng)前采樣點極徑的估計。

接受域H0：當(dāng)前采樣點i為線段、圓弧或其他特征，拒絕域H1：當(dāng)前采樣點i為角點特征。

拒絕域H1上滿足：

滿足式（12）的采樣點為角點，否則為非角點特征。

上述方法給出采樣點及其鄰域特征初步判斷結(jié)果，對于環(huán)境中的具體特征需要進一步確定。

2 多特征檢測

特征初分類之后需要對每種特征進行特征提取，確定角點、線段以及圓弧的特征信息。

2.1 角點特征

在極坐標(biāo)系內(nèi)，角點特征表示為P＝［ρP，θP］T，其中ρP、θP分別為角點的極徑和極角。角點分為2類：一類為凸角點，即角點為其鄰域內(nèi)的最小值；另一類為凹角點，即角點為其鄰域內(nèi)的最大值。定義凹凸性函數(shù)EC：

如果EC＞0，則角點所在的區(qū)域為凹區(qū)域，否則為凸區(qū)域。

激光傳感器掃描數(shù)據(jù)點如圖1所示。

圖1 角點估計示意圖Fig.1 Corner points estimation schematic

圖1以凸角點區(qū)域為例，拋物線上3點P-1、P0、P1分別為角點及其左右相鄰的點。Δθ為傳感器角分辨率。假設(shè)3點滿足拋物線方程為ρ＝at2+bt+c，可求解該方程參數(shù)，則可求得角點位置Pmin。

2.2 線段特征

線段特征表示為L＝［d，φ，Ps，Pe］T、其中：d為激光傳感器在笛卡爾坐標(biāo)系原點到線段的距離，φ為線段的傾角，Ps為線段的起點，Pe為線段的終點。線段在笛卡爾坐標(biāo)系下的方程為

其中：d＞0，-π＜φ＜π，xi＝ρicos θi，yi＝ρisin θi。

在1節(jié)中，將待識別數(shù)據(jù)進行初步特征劃分，為準(zhǔn)確提取線段特征，采用帶權(quán)值的約束最小二乘法對可能存在線段特征進行特征提取，將式（14）轉(zhuǎn)換為最小二乘形式：

由于sin2φ+cos2φ＝1，引入拉格朗日乘子λ，得

解上式的廣義特征值與廣義特征向量，S為一個正定矩陣，待求特征向量J一定對應(yīng)最小的特征值λ，可得線段特征φ與d。

2.3 圓弧特征

圓弧特征向量為R＝［θC，ρC，r］T，極坐標(biāo)下為

式中：θC為圓心極角；ρC為圓心極徑；r為圓的半徑，r～N（μr，σr2）。

圓弧可能存在區(qū)域由凹凸性函數(shù)（13）給出，條件為相鄰區(qū)凹凸性一致。當(dāng)EC＞0時為凸圓弧區(qū)域，EC＜0為凹圓弧區(qū)域。

為獲得最小二乘形式，則等式（19）變?yōu)?/p>

其中，i∈［m，n］。上式可簡化為

其中：x＝［xi，yi］T，a＝1，b＝［-2ρCcos θC，-2ρCsin θC］T，c＝ρC2-r2。等式（21）整理為矩陣形式：

其中：H＝［1，b（1，1），b（2，1），c］T。b2（1，1）+b2（2，1）-4c＝4r2，引入拉格朗日乘子λ，得

式中：Q為一個正定矩陣，絕對值最小特征值λ的特征向量為H，則圓弧特征：

3 實驗結(jié)果

本文提出的算法由VC++編寫程序代碼，并在服務(wù)機器人上實驗，使用的激光傳感器為UTM?30LX激光傳感器。其中，σρ為1 cm，σθ為0.1°，μd為12 cm，σd為6 cm，σφ為0.1°，σr為2 cm。

圖1為實驗室特征地圖，其中角點特征為實驗臺的棱邊，墻角等；線段特征主要為墻體，實驗臺側(cè)面，門等；圓弧特征主要為桶等其他圓柱形的物體。服務(wù)機器人在圖示的位置沿直線做往返運動，將獲取的特征加入到環(huán)境地圖中。圖中已提取的特征：分別由小寫字母a～h為角點、數(shù)字1～17為線段和羅馬數(shù)字Ⅰ～Ⅶ為圓弧，大寫字母表示提取錯誤的特征。

圖2 實驗室環(huán)境地圖Fig.2 Map of laboratory

室內(nèi)環(huán)境共有12處角點特征。表1給出了角點特征θP與ρP的均值與方差。θP方差的最大值為0.12°，ρP方差的最大值為1.98 cm，盡管右側(cè)墻壁存在許多孤立的點，但沒有影響本文方法提取角點。

表1 角點特征統(tǒng)計Table1 Statistics of corner features

室內(nèi)環(huán)境共有17處線段特征。表2給出了線段特征φ與d的均值與方差。φ方差的最大值為1.51°，d方差的最大值為4.63 cm。

表2 線段特征統(tǒng)計Table2 Statistics of segment features

圖1中，室內(nèi)環(huán)境共有7處圓弧特征。表3給出了圓弧特征θC、ρC與r的均值與方差。實驗數(shù)據(jù)中θC的最大方差為0.5°，ρC的最大方差為2.83 cm，r的最大方差為2.28 cm。

表4為圓弧半徑估計均值與真實值對比。從表4中可以看出圓弧半徑估計最大誤差為1.84 cm，最小誤差為0.24 cm，相對誤差為1.41 cm。

表5給出了本文特征識別算法實驗的全部統(tǒng)計數(shù)據(jù)（含重復(fù)提取數(shù)據(jù)），錯誤提取的環(huán)境特征為圖1中大寫英文字母的位置。本文算法提取特征的成功率在94%以上，具有較好的多特征提取穩(wěn)定性。

表3 圓弧特征統(tǒng)計Table3 Statistics of circle features

表4 結(jié)果對比Table4 Results comparison

表5 實驗結(jié)果統(tǒng)計Table5 Statistics of experimental results

4 結(jié)論

本文采用二維激光傳感器進行室內(nèi)環(huán)境多種特征提取研究，提出了基于假設(shè)檢驗及最小二乘法綜合的新型特征提取方法。通過實驗驗證本文方法具有以下特點：

1）多特征，可同時識別角點、線段以及圓弧特征；

2）高精度，均值和方差數(shù)據(jù)表明特征提取的位置誤差均小于5 cm，可滿足基于特征的機器人定位和地圖構(gòu)建需要。

實際環(huán)境的特征識別實驗驗證了本算法具有較好的適應(yīng)性和穩(wěn)定性，提高了移動機器人對環(huán)境的理解能力。

［1］LEONARD J，HOW J，TELLER S，et a1.A perception?driv?en autonomous urban vehicle［J］.Journal of Field Robotics，2008，25（10）：727?774.

［2］楊明，王宏.基于激光雷達的移動機器人位姿估計方法綜述［J］.機器人，2002，24（2）：177?183.YANG Ming，WANG Hong.Overview of laser radar based pose estimation for mobile robots［J］.Robot，2002，24（2）：177?183.

［3］MINGUEZ J，MONTESANO L，LAMIRAUX F.Metric?based iterative closest point scan matching for sensor dis?placement estimation［J］.IEEE Transactions on Robotics，2006，22（5）：1047?1054.

［4］ELFES A.Sonar?based real?world mapping and navigation［J］.IEEE Journal of Robotics＆Automation，1987（6）：249?265.

［5］LINGEMANN K，SURMANN H，NUCHTER A，et al.In?door and outdoor location for fast mobile robots［C］／／Pro?ceedings of IEEE／RSJ International Conference on Intelli?gent Robots and Systems（IROS'04）.Sendai，Japan，2004：2185?2190.

［6］KNIERIEMEN T，Von PUTTKAMER E，ROTH J.Extrac?ting lines，circular segments and clusters from radar pictures in real time for an autonomous mobile robot［C］／／IEEE Workshop on Real Time Systems.Piscataway，USA，1991：127?135.

［7］WEBER J，J?RG K W，PUTTKAMER E.APR?global scan matching using anchor point relationships［C］／／6th Int Conf Intelligent Autonomous Systems.Venice，Italy，2000：471?478.

［8］YAN R，WU J，WANG W，et al.Natural corners extraction algorithm in 2D unknown indoor environment with laser sen?sor［C］／／2012 12th International Conference on Control，Automation and Systems（ICCAS）.JeJu，Island，2012：983?987.

［9］BORGES G A，ALDON M J.A split?and?merge segmentation algorithm for line extraction in 2D range images［C］／／Rro?ceedings of 15th International Conference on Pattern Recog? nition.Los Alamitos：IEEE Computer Society，2000：441?444.

［10］NOYER J C，LHERBIER R，F(xiàn)ORTIN B.Automatic fea?ture extraction in laser rangefinder data using geometric in?variance［C］／／2010 Conference Record of the Forty Fourth Asilomar Conference on Signals，Systems and Computers（ASILOMAR）.Pacific Grove，CA，2010：199?203.

［11］AN S Y，KANG J G，LEE L K，et al.SLAM with salient line feature extraction in indoor environments［C］／／2010 11th International Conference on Control Automation Robot?ics＆Vision（ICARCV）.Singapore，2010：410?416.

［12］JAFRI S R U N，ZHAO L，CHANDIO A A，et al.Laser only feature based multi robot SLAM［C］／／2012 12th In?ternational Conference on Control Automation Robotics＆Vision（ICARCV）.Guangzhou，2012：1012?1017.

［13］FENG X，GUO S，LI X，et al.Robust mobile robot locali?zation by tracking natural landmarks［C］／／International Conference on Artificial Intelligence and Computational In?telligence.Berlin：Springer，2009：278?287.

［14］LIU M，LEI X，ZHANG S，et al.Natural landmark extrac?tion in 2D laser data based on local curvature scale for mo?bile robot navigation［C］／／2010 IEEE International Con?ference on Robotics and Biomimetics（ROBIO）.Tianjin，2010：525?530.

［15］DIOSI A，KLEEMAN L.Laser scan matching in polar coor?dinates with application to SLAM［C］／／Proceedings of 2005 IEEE／RSJ International Conference on Intelligent Ro?bots and Systems.Edmonton，Canada，2005：3317?3322.

An indoor environmental multi?feature identification method based on the hypothesis testing

HUO Guanglei，ZHAO Lijun，LI Ruifeng，LYU Mingrui
（State Key Laboratory of Robotics and System，Harbin Institute of Technology，Harbin 150001，China）

In order to solve the adaptability of indoor environmental feature extraction of mobile robots，this paper proposed a hypothesis?testing?based indoor multi?feature identification method.Firstly，the multi?dimensional space is built before processing features.Then，the distance probability function is defined，and by combination with the χ2hypothesis test theory the feature regions of the sampled points are estimated and segmented.Further，the corner features are recognized by the extreme value method while the features of line segments and arcs are obtained by u?sing the constrained least square method.Finally，the results of experiments verify that the proposed method can ex?tract the corner feature，the line segment feature and the arc feature steadily，and the feature recognition rate is o?ver 94%.

indoor environment；hypothesis testing；features；robot；multi?feature identification；least square method

10.3969／j.issn.1006?7043.201310040

http：／／www.cnki.net／kcms／detail／23.1390.U.20150109.1513.008.html

TP242.6

A

1006?7043（2015）03?0348?05

2013?10?15.網(wǎng)絡(luò)出版時間：2015?01?09.

國家自然科學(xué)基金資助項目（61473103，61273339）；機器人技術(shù)與系統(tǒng)國家重點實驗室自主課題資助項目（SKLRS201405B，SKLRS201411B）.

霍光磊（1982?），男，博士研究生；趙立軍（1972?），男，高級工程師，博士；李瑞峰（1965?），男，教授，博士生導(dǎo)師.

趙立軍，E?mail：zhaoings＠163.com.