基于自适应阈值的距离图像线段特征提取

满增光，叶文华，楼佩煌，钱晓明

南京航空航天大学机电学院，南京210016

环境地图广泛用于移动机器人导航系统，机器人借此完成基于地图的定位或全局路径规划等任务.当机器人工作于地面时，一个2D环境地图足以为其提供必要信息.对于室内环境，通常采用栅格地图［1］和几何地图［2-3］.栅格地图的缺点在于地图的存储占用量大;而几何地图因其环境表示紧凑，可以很好地克服这个缺点.几何地图采用几何图元表示环境，例如，线段、圆弧和直角等.由于室内环境具有结构化的特点，这些几何图元可以从2D激光雷达扫描的环境数据中提取.在室内环境中，墙壁、门等环境的轮廓都是直线形式，因此，线段是一类最常用作室内环境建模的几何图元.相应地，从2D激光雷达扫描数据中提取线段的技术也得到深入研究.

目前，线段提取技术可以分为序惯方法和递归方法两类.序惯方法有PDBS(point distance based methods)算法、SEF(successive edge following)算法和LT(line tracking)算法.递归方法有IEPF(iterative end point fit)算法和Split-Merge算法.除此以外，还有不依赖于局部信息的HT(Hough transform)方法.

PDBS算法直接利用激光雷达探测的距离信息提取线段［4］.该算法在分割线段时依据两相邻扫描点的直线距离.SEF算法对PDBS算法进行简化［5］.这两种算法的缺点是对相交线段的分割失效，且由于同一线段上的扫描点空间分布不均，使阈值选取困难.LT算法依据第n+1个点到前n个点所拟合直线的距离分割线段，其对阈值敏感［5-6］.IEPF算法包括递归分割和递归合并两个过程［4，6-8］.Split-Merge算法和IEPF算法类似，区别在于分割阶段所采用的直线拟合方法不同［5，7-9］.这两种方法对阈值也比较敏感，容易引起过分割或过合并问题.HT算法具有简单及好的抗噪性能［7，10-11］，但由于没有利用数据点采集序列的顺序信息，计算量大，且其采用投票的方式确定直线，提取的线段严重依赖于扫描点的空间密集程度.

由于2D激光雷达获得的距离图像在同一线段上的扫描点分布不均，测量误差随探测距离的增加而增大.通常，固定阈值无法满足从该距离图像中提取线段的要求.鉴于线段特征提取算法存在阈值选取困难，易引起线段的过分割和过合并的问题，本研究提出一种基于自适应阈值的分割-合并算法，尝试解决线段提取中过分割和过合并弊病.

1 2D激光雷达

激光雷达发射极短的脉冲激光束 (红外激光束)，其基本原理是通过测量从发射激光束到接收反射光的时间间隔 (time-of-flight，TOF)来确定目标的距离.TOF与被测距离成正比.当激光束遇到物体表面时，部分光线被反射回来，由接收单元接收并计算出TOF.电机带动旋转镜面间断地将激光束偏转使其通过整个视场，最终得到一个全视场的距离扫描数据.

2 算法描述

将激光雷达扫描180°视场的N个扫描点作为一个有序序列，按该序列返回扫描的距离数据.首先，对返回的距离数据进行预处理，即把在极坐标系中表示的激光雷达距离图像转换到直角坐标系中，得到的点集为

本研究算法分为分割和合并两个阶段.

2.1 分割

分割阶段将不在同一条直线上的点集进行分割.最有效的线段分割算法有IEPF算法和LT算法.IEPF分割原理如图1.通过点集P的起点P0和终点Pn确定直线l，在该点集中搜索到该直线距离最大的点Pj，若该点到该直线的距离dj大于设定的阈值dthd，则以该点为断点，将该点集分割为P'和P″两个点集.IEPF分割是一种递归算法，因此对每一个经分割得到的点集如P'和P″，仍要执行相同的分割过程，直到所有点集都满足验证准则［4］.

图1 IEPF算法分割原理Fig.1 Segmentation principle of IEPF algorithm

LT分割算法原理如图2.初始化点集P，包含n个点，并对P进行直线拟合，得到直线l.若第n+1个点Pn+1到直线l的距离dn+1小于设定阈值dthd，则将该点加入点集P;否则，以该点为起点，初始化下一个点集.LT分割算法具有较好的直线跟踪能力，但由于LT算法没有合并阶段，因此线段的分割完全取决于阈值dthd.IEPF算法包含合并阶段，但该算法在分割时没有考虑共有端点的情况，即分割点只属于其中一个子点集，因而对线段端点的确定不够准确.

图2 LT算法分割原理Fig.2 Segmentation principle of LT algorithm

本研究利用IEPF和LT算法各自的优点，提出以下分割算法:

步骤1:对于点集Pi，根据IEPF分割原理，Pi中探测可能的分割点，相应的距离为dthd，以点为分割点将点集Pi分割为两个点集Pi'和Pi″，更新所有点集的集合P.分割点的分配由准则1确定.

补充说明:步骤1是一个递归过程，直到P中的所有点集都不满足分割条件，算法终止.转至步骤2.

步骤2:去掉P中所有重复出现、由单个点构成的点集，更新P.

步骤3:去掉P中所有已包含在相邻点集中、由单个点构成的点集，更新P.

步骤4:利用LT分割算法的思想，判定在所有相邻点集Pi和Pi+1中，Pi+1的起点是否可作为Pi的新终点.若是，将Pi+1的起点添加到Pi中，更新P.判定方法依据准则2.

步骤5:利用LT分割算法的思想，判定在所有相邻点集Pi和Pi+1中，Pi的终点是否可作为Pi+1的新起点.若是，则将Pi的终点添加到Pi+1中，更新P.判定方法依据准则2.

步骤6:去掉P中已包含在相邻点集中、由单个点构成的点集，更新P.

准则1:分割点分配准则如图3.其中，D1为分割点到其前一点的距离;D2为分割点到其后一点的距离;c为一预先设定的常数，通过实验确定，其值在0～1之间.

图3 分割点分配准则Fig.3 Allocation criteria of split points

准则2:采用 TLS(total least square)方法［9］对点集pi进行直线拟合，计算某点到该直线的距离，如果该距离小于设定的阈值，则点属于该点集.

2.2 基于自适应阈值的合并

合并阶段将满足一定条件的相邻点集合并，从而最大程度上提取出最小数量的线段.传统的合并方法采用直线拟合误差E2［9］与固定阈值Ethd比较.固定阈值的缺点是容易引起线段特征提取的过合并或过分割问题.鉴于此，本研究提出一种基于自适应阈值的合并算法.该算法根据两个相邻点集所包含的点数将合并过程分为两种情况进行考虑.核心算法描述如下:

3 实验分析

实验数据由Sick LMS 200激光雷达获取，其角度分辨率设为1°，算法在Matlab平台下实现.分析对比LT算法、IEPF算法及本算法实验结果，相关参数为:① 在 LT算法中，dthd=33 mm;② 在IEPF算法中，dthd=33 mm，Ethd=5 000 mm2;③在本算法中，

图4与图5为部分实验结果，分别来自不同激光雷达的测量数据.图4(b)～(d)分别是对原始图像图4(a)中方框处特征提取结果.可见，在图4(b)中，采用LT算法提取的线段1和线段2都出现过合并.图4(c)中，采用IEPF算法提取的线段2出现过合并.而图4(d)中，采用本研究算法提取的线段1、2和3都没有出现过合并问题.

图5(b)～(d)分别是采用3种算法对原始图像图5(a)进行特征提取的结果.可见，在图5(b)中，采用LT算法提取的线段3和4在椭圆处被过分割.图5(c)中，采用IEPF算法提取的线段3和4在椭圆处被过分割，线段5和6在另一椭圆处被过分割.在图5(d)中，采用本研究算法提取的特征没有出现过分割问题.另外，在图5(b)和 (c)中的矩形处也看到，LT算法和IEPF算法对提取线段的端点确定不够准确.而从图5(d)和图4(d)中的矩形处可以看出，本研究算法对端点的确定比其他两种方法更加准确.

图4 线段特征提取过合并对比Fig.4 A comparison of over-merging produced by feature extraction

图5 线段特征提取过分割对比Fig.5 A comparison of over-spliting produced by feature extraction

结 语

本研究提出一种基于自适应阈值的线段提取新方法，该算法由分割和合并两阶段组成:① 在分割阶段，采用IEPF分割算法对输入点集进行递归分割，利用LT分割算法思想对已分割点集的端点进行重新分配.由于考虑了公共端点的情况，对线段端点的表示比其他算法更加准确;② 在合并阶段，根据两个相邻点集包含的点数将合并过程分为两种情况考虑.针对两种不同情况分别采用不同的自适应阈值合并算法对两点集进行合并.采用自适应阈值改善了其他算法在线段特征提取中存在的过分割和过合并缺点.

［1］Schroeter C，Gross H.传感器无关的RBPF SLAM方法——应用于视觉建图的地图匹配SLAM［C］//2008 IEEE/RSJ智能机器人和系统国际会议论文集.皮斯卡塔韦 (美国):IEEE出版社，2008:2078-2083.(英文版)

［2］Andrea G，Antonio G，Andrea R，等.基于直线特征环境模型的移动机器SLAM［C］//第44届IEEE设计和控制会议与欧洲控制会议论文集.皮斯卡塔韦 (美国):IEEE计算机协会，2005:2041-2046.(英文版)［3］庄 严，王 伟，王 珂，等.移动机器人基于激光测距和单目视觉的室内同时定位和地图构建［J］.自动化学报，2005，31(6):925-933.

［4］Borges G A，Aldon M J.用于移动机器人的2D距离图像直线提取［J］.智能与机器人系统，2004，40(3):267-297.(英文版)

［5］Borges G A，Aldon M J.从2D距离图像中提取直线的split-merge分割方法［C］//第15届模式识别国际会议论文集.洛斯阿拉米托斯 (美国):IEEE计算机协会，2000:441-444.(英文版)

［6］Vandorpe J，Brussel H V，Xu H.利用2D测距传感器得到的几何图元移动机器人精确动态建图［C］//机器人与自动化国际会议论文集.纽约 (美国):IEEE出版社，1996:901-908.(英文版)

［7］Viet N，Stefan G，Agostino M，等.用于室内移动机器人从2D距离数据中提取直线的算法比较［J］.自主机器人，2007，23(2):97-111.(英文版)

［8］Choi Y，Lee T，Oh S.面向移动机器人利用低级测距传感器使用几何约束和主动探测的基于直线特征的SLAM［J］.自主机器人，2008，24(1):13-27.(英文版)

［9］Pavlidis T，Horowitz S L.平面曲线分割［J］.IEEE计算机汇刊，1974，23(8):860-870.(英文版)

［10］Lorenzo J M P，Vázquez R，Núñez P，等.基于 Hough变换的室内环境中并发建图与定位［C］//2004 IEEE机器人、自动化和机电一体化国际会议论文集.皮斯卡塔韦 (美国):IEEE出版社，2005:840-845.(英文版)

［11］Stefan G，Viet N，Roland S.用于服务机器人的距离图像分割结果［C］//IEEE第4届计算机视觉国际会议论文集.纽约 (美国):IEEE计算机协会，2006:53-60.(英文版)