ISSN 1000-1239 CN 11-1777/TP

Journal of Computer Research and Development ›› 2019, Vol. 56 ›› Issue (2): 338-348.doi: 10.7544/issn1000-1239.2019.20180092

Previous Articles     Next Articles

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

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

CLC Number: