基于假设检验的室内环境多特征检测方法

霍光磊，赵立军，李瑞峰，吕明睿

（哈尔滨工业大学机器人技术与系统国家重点实验室，黑龙江哈尔滨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.