Download the full-sized PDF of Efficient Visual Search in Appearance-based SLAMDownload the full-sized PDF



Permanent link (DOI):


Export to: EndNote  |  Zotero  |  Mendeley


This file is in the following communities:

Graduate Studies and Research, Faculty of


This file is in the following collections:

Theses and Dissertations

Efficient Visual Search in Appearance-based SLAM Open Access


Other title
Graph Nearest Neighbor Search
Image Retrieval
Appearance-based SLAM
Type of item
Degree grantor
University of Alberta
Author or creator
Hajebi, Kiana
Supervisor and department
Zhang, Hong (Computing Science)
Examining committee member and department
Huang, Biao (Chemical and Materials Engineering)
Mueller, Martin (Computing Science)
Jagersand, Martin (Computing Science)
Hu, Huosheng (Computer Science and Electronic Engineering, University of Essex, UK)
Ray, Nilanjan (Computing Science)
Department of Computing Science

Date accepted
Graduation date
Doctor of Philosophy
Degree level
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.
Permission is hereby granted to the University of Alberta Libraries to reproduce single copies of this thesis and to lend or sell such copies for private, scholarly or scientific research purposes only. The author reserves all other publication and other rights in association with the copyright in the thesis and, except as herein before provided, neither the thesis nor any substantial portion thereof may be printed or otherwise reproduced in any material form whatsoever without the author's prior written permission.
Citation for previous publication

File Details

Date Uploaded
Date Modified
Audit Status
Audits have not yet been run on this file.
File format: pdf (PDF/A)
Mime type: application/pdf
File size: 5478477
Last modified: 2016:06:24 17:57:28-06:00
Filename: Hajebi_Kiana_201509_PhD.pdf
Original checksum: fabe8ef653a056abfeac2dc304290b7b
Well formed: true
Valid: true
Page count: 117
Activity of users you follow
User Activity Date