Global localization and relative positioning based on scale-invariant keypoints

The localization capability of a mobile robot is central to basic navigation and map building tasks. We describe a probabilistic environment model which facilitates global localization scheme by means of location recognition. In the exploration stage the environment is partitioned into locations, each characterized by a set of scale-invariant keypoints. The descriptors associated with these keypoints can be robustly matched despite changes in contrast, scale and viewpoint. We demonstrate the efficacy of these features for location recognition, where given a new view the most likely location from which this view came from is determined. The misclassifications due to dynamic changes in the environment or inherent appearance ambiguities are overcome by exploiting location neighborhood relationships captured by a Hidden Markov Model. We report the recognition performance of this approach in an indoor environment consisting of eighteen locations and discuss the suitability of this approach for a more general class of recognition problems. Once the most likely location has been determined we demonstrate how to robustly compute the relative pose between the representative view and the current view. (C) 2005 Elsevier B.V. All rights reserved.