杨忠炯，王臣臣，周立强，易圣先

（中南大学，长沙 410000）

0 引言

同时定位与建图是近些年来机器人领域研究的热门话题，是实现机器人在未知环境自主导航的关键技术。SLAM技术是指机器人能够在未知环境中，通过自身携带的传感器来获取外界信息和自身位姿，以此建立起环境地图和完成自身定位，并在运动中完成地图与自身位姿的更新。

机器人携带的传感器包括激光传感器，相机，毫米波雷达等，其中激光传感器由于其具有同时精确测量距离和方位角的能力，并且受环境影响较小的特点，被广泛应用于各类机器人导航与定位系统。特征地图因其占用内存小，能够高效，全面地表示环境信息，因而被广泛应用在室内移动机器人定位中。而构造特征地图的首要任务就是环境特征的提取，常见的环境特征通常是指几何环境特征，比如线段、角、圆等。而在实际环境中，最常见的特征之一就是线段特征。由激光传感器扫描环境所得的数据中提取线段特征的算法目前主要有霍夫变换，回归法，增量法，分裂合并法等。文中提出一种基于密度聚类的线段特征提取方法。

1 聚类

聚类是一种应用广泛的数据挖掘技术，很多领域都应用到了聚类算法，包括机器学习，图像处理等。聚类将数据按照其相似程度不一的特性讲其划分为不同的簇，同一簇内数据相似程度高，不同簇内数据相似程度较低。聚类算法得到了广泛的研究，许多学者提出了不同类型的聚类算法，包括原型聚类，密度聚类，层次聚类等。……