Landmark selection for vision-based navigation

Recent work in the object recognition community has yielded a class of interest point-based features that are stable under significant changes in scale, viewpoint, and illumination, making them ideally suited to landmark-based navigation. Although many such features may be visible in a given view of the robot's environment, only a few such features are necessary to estimate the robot's position and orientation. In this paper, we address the problem of automatically selecting, from the entire set of features visible in the robot's environment, the minimum (optimal) set by which the robot can navigate its environment. Specifically, we decompose the world into a small number of maximally sized regions such that at each position in a given region, the same small set of features is visible. We introduce a novel graph theoretic formulation of the problem and prove that it is NP-complete. Next, we introduce a number of approximation algorithms and evaluate them on both synthetic and real data.

Authors

• Pablo Sala
• Robert Sim
• Ali Shokoufandeh
• Sven J. Dickinson

Keywords

• Navigation
• Robotics and automation
• Robots
• Object recognition
• Lighting
• Image databases
• Spatial databases
• Computer vision
• Runtime environment
• Tiles
• Vision-based Navigation
• Feature Classification
• Estimation Algorithm
• Scale Changes
• Illumination Changes
• Viewpoint Changes
• Small Set Of Features
• Perimeter
• Visual Features
• Grid Points
• Set Of Covariates
• Visual Areas
• Minimum Set
• Current Image
• Visual Perspective
• Pose Estimation
• Mixture Distribution
• Circular Area
• Problem Instances
• Scale-invariant Feature Transform
• Number Of Poses
• Set Cover Problem
• Feature Database
• Robot Localization
• Robot Pose
• Robot Navigation