Efficient Visual Search in Appearance-based SLAM

• Author / Creator

  Hajebi, Kiana

• Simultaneous localization and mapping (SLAM) in an unknown environment is a prerequisite to have a truly autonomous mobile robot. In this thesis, we focus on appearance-based visual SLAM, for which we develop a graph-based nearest-neighbor search algorithm to speed up bag-of-words (BoW) image retrieval. In appearance-based SLAM, the robot uses the visual appearance of the locations taken along its route to build the map of the environment and localizes itself within this map by recognizing places it has visited before. To solve the challenging problem of appearance-based place recognition (a.k.a. loop closure detection in the context of SLAM) in large-scale environments, we employ the bag-of-words model, because of its efficiency in image representation and retrieval. Moreover, because the complexity of BoW does not grow with the size of the dataset, as much as that of other search techniques (e.g. direct feature matching) do, it can be employed for large-scale image search applications. Although BoW provides an efficient search technique, its vector-quantization (VQ) step can be computationally expensive in order to provide sufficient discriminating power for image matching. In order to speed up the VQ process, we propose a graph-based nearest neighbor search method (GNNS) that builds a k-NN graph index, and is efficiently integrated into the SLAM system. The k-NN graph is constructed over the visual words of the vocabulary. At search time, the standard GNNS algorithm starts from a randomly sampled node in the graph and performs hill-climbing until reaching a local minimum which is then an approximate nearest neighbor of the queried feature. We modify the GNNS algorithm to be initialized judiciously by exploiting the following properties of SLAM and BoW model: (1) the sequential property of images acquired in appearance-based SLAM, (2) the perceptual aliasing problem inherent to BoW. This smart initialization of GNNS improves the speedup of the vector-quantization considerably. We experimentally show that our search method outperforms the popular KD-trees and hierarchical k-means algorithms. Furthermore, we develop a SLAM system by integrating the BoW’s loop closure detection in a Bayesian filtering framework. This probabilistic framework then discards false loop closures by enforcing the temporal coherency of estimation. We run our SLAM system on different datasets to test our loop closure detection in challenging environments. The system successfully detects loop closures with 100% precision and high recall rates in real-time.

• Subjects / Keywords

  • Robotics
  • Image Retrieval
  • Appearance-based SLAM
  • Graph Nearest Neighbor Search

• Graduation date

  Fall 2015

• Type of Item

  Thesis

• Degree

  Doctor of Philosophy

• DOI

  https://doi.org/10.7939/R3RF5KP8X

• License

  This thesis is made available by the University of Alberta Libraries with permission of the copyright owner solely for non-commercial purposes. This thesis, or any portion thereof, may not otherwise be copied or reproduced without the written consent of the copyright owner, except to the extent permitted by Canadian copyright law.