ISSN 1000-1239 CN 11-1777/TP

计算机研究与发展 ›› 2019, Vol. 56 ›› Issue (2): 338-348.doi: 10.7544/issn1000-1239.2019.20180092

• 人工智能 • 上一篇    下一篇



  1. 1(计算机科学国家重点实验室(中国科学院软件研究所) 北京 100190); 2(中国科学院大学 北京 100190); 3(中国科学院软件研究所 北京 100190) (
  • 出版日期: 2019-02-01
  • 基金资助: 

SegGraph: An Algorithm for Loop-Closure Detection in Outdoor Scenes Using 3D Point Clouds

Liao Ruijie1,2, Yang Shaofa1, Meng Wenxia2,3, Dong Chunmei1,2   

  1. 1(State Key Laboratory of Computer Science (Institute of Software, Chinese Academy of Sciences), Beijing 100190); 2(University of Chinese Academy of Sciences, Beijing 100190); 3(Institute of Software, Chinese Academy of Sciences, Beijing 100190)
  • Online: 2019-02-01

摘要: 提出适用于配有三维激光雷达的自主移动机器人在室外场景进行同时定位与地图创建(simul-taneous localization and mapping, SLAM)的一种闭环检测算法,命名为SegGraph.作为SLAM的关键模块,闭环检测的任务是判断机器人当前位置是否与已到过的某一位置邻近.SegGraph包含3步:1)对在不同时刻得到的2组点云分别移除大地平面后采用区域增长方法分割为若干个点云簇;2)以点云簇为顶点,以点云簇图心间距离为边权值,分别构建带权值的完全图;3)判定所得的2个完全图是否含有足够大的公共子图.SegGraph的主要创新点是在寻找公共子图时以边权值(即点云簇间距离)为主要匹配依据.这是因为点云数据中的噪声会导致在邻近地点获得的不同点云经分割后得出差别很大的点云簇集,不同点云中相应的点云簇也便无法匹配.然而相应点云簇间距离却受分割过程影响不大.主要贡献包括研发高效的判定2个点云簇图是否有足够大的公共子图的近似算法,实现完整的SegGraph算法,及以被广泛使用的公开数据集KITTI(Karlsruhe Institute of Technology and Toyota Technological Institute)评估SegGraph的准确度及运行效率.实验结果显示SegGraph具有良好的准确度及运行效率.

关键词: 同时定位与地图创建, 闭环检测, 公共子图, 3D点云, KITTI数据集

Abstract: We present SegGraph, a new algorithm for loop-closure detection (LCD) for autonomous robots equipped with three-dimensional laser scanners in outdoor scenes such as urban streets. LCD is to check whether the robot has passed a place near where it visited at some point before, and is a key component of a robot’s simultaneous localization and mapping system. Our SegGraph algorithm consists of three steps: 1) partition each of the two input point clouds into point clusters corre-sponding to smooth surfaces, while discarding the ground planes; 2) construct complete weighted graphs from the cluster sets where weights correspond to distances between surface centroids; 3) check if these two graphs contain a sufficiently large common subgraph. The key novelty of SegGraph is that in matching common subgraphs, we mainly compare the distances between corresponding pairs of surface clusters. The rationale is that, due to noise in point cloud data and imperfection of segmentation techniques, different point clouds obtained from nearby places may often be partitioned into drastically different surface segments. However, distances between centroids of these segments tend to be stable across different point clouds. We develope an efficient heuristic randomized algorithm for finding common subgraphs, implement a full LCD algorithm and evaluate it on the publicly available KITTI dataset, which is one of the most widely used. Experimental results demonstrate that our LCD algorithm achieves good accuracy and efficiency.

Key words: simultaneous localization and mapping (SLAM), loop-closure detection, common subgraphs, 3D point cloud, KITTI dataset