基于假設檢驗的室內環境多特征檢測方法

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

（哈爾濱工業大學機器人技術與系統國家重點實驗室，黑龍江哈爾濱150001）

基于假設檢驗的室內環境多特征檢測方法

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

（哈爾濱工業大學機器人技術與系統國家重點實驗室，黑龍江哈爾濱150001）

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

室內環境；假設檢驗；特征；機器人；多特征檢測；最小二乘法

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

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

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

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

1 特征初分類

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

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

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

1.1 左右鄰域特征處理

在極坐標下，線段方程為非線性方程，角分線函數為

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

在線段環境下，ρ?i±j是ρi±j的無偏估計，且ρi是相互獨立的。根據假設檢驗有

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

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

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

在樣本空間內，已知采樣方差，選擇統計量為

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

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

1.2 當前采樣點特征

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

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

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

拒絕域H1上滿足：

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

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

2 多特征檢測

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

2.1 角點特征

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

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

激光傳感器掃描數據點如圖1所示。

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

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

2.2 線段特征

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

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

在1節中，將待識別數據進行初步特征劃分，為準確提取線段特征，采用帶權值的約束最小二乘法對可能存在線段特征進行特征提取，將式（14）轉換為最小二乘形式：

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

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

2.3 圓弧特征

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

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

圓弧可能存在區域由凹凸性函數（13）給出，條件為相鄰區凹凸性一致。當EC＞0時為凸圓弧區域，EC＜0為凹圓弧區域。

為獲得最小二乘形式，則等式（19）變為

其中，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 實驗結果

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

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

圖2 實驗室環境地圖Fig.2 Map of laboratory

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

表1 角點特征統計Table1 Statistics of corner features

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

表2 線段特征統計Table2 Statistics of segment features

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

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

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

表3 圓弧特征統計Table3 Statistics of circle features

表4 結果對比Table4 Results comparison

表5 實驗結果統計Table5 Statistics of experimental results

4 結論

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

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

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

實際環境的特征識別實驗驗證了本算法具有較好的適應性和穩定性，提高了移動機器人對環境的理解能力。

［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，FORTIN 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.網絡出版時間：2015?01?09.

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

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

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