Application of locality sensitive hashing to feature matching and loop closure detection

• Author / Creator

  Shahbazi, Hossein

• My thesis focuses on automatic parameter selection for euclidean distance version of Locality Sensitive Hashing (LSH) and solving visual loop closure detection by using LSH. LSH is a class of functions for probabilistic nearest neighbor search. Although some work has been done for parameter selection of LSH, having three parameters and lack of guarantees on the running time, restricts the usage of LSH. We propose a method for finding optimal LSH parameters when data distribution meets certain properties.

  Loop closure detection is the problem of deciding whether a robot has visited its current location before. This problem arises in both metric and visual SLAM (Simultaneous Localization and Mapping) applications and it is crucial for creating consistent maps. In our approach, we use hashing to efficiently find similar visual features. This enables us to detect loop closures in real-time without the need to pre-process the data as is the case with the Bag-of-Words (BOW) approach.

  We evaluate our parameter selection and loop closure detection methods by running experiments on real world and synthetic data. To show the effectiveness of our loop closure detection approach, we compare the running time and precision-recalls for our method and the BOW approach coupled with direct feature matching. Our approach has higher recall for the same precision in both sets of our experiments. The running time of our LSH system is comparable to the time that is required for extracting SIFT (Scale Invariant Feature Transform) features and is suitable for real-time applications.

• Subjects / Keywords

  • Parameter selection
  • Nearest neighbor search
  • Locality sensitive hashing
  • Visual slam
  • Loop closure detection

• Graduation date

  Spring 2012

• Type of Item

  Thesis

• Degree

  Master of Science

• DOI

  https://doi.org/10.7939/R3DH0R

• 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.