We present a new method for the robust detection and matching of multiple planes in pairs of images. Such planes can serve as stable landmarks for vision-based urban navigation. Our approach starts from SIFT matches and generates multiple local homography hypotheses using the recent J-linkage technique by Toldo and Fusiello, a robust randomized multi-model estimation algorithm. These hypotheses are then globally merged, spatially analyzed, robustly fitted, and checked for stability. When tested on more than 30,000 image pairs taken from panoramic views of a college campus, our method yields no false positives and recovers 72% of the matchable building walls identified by a human, despite significant occlusions and viewpoint changes.

This paper presents a new method for navigation and localization of a mobile robot equipped with an omnidirectional camera. We represent the environment using a collection of one-dimensional panoramic images formed by averaging the center scanlines of a cylindrical view. Such 1D images can be stored and processed with few resources, allowing a fairly dense sampling of the environment. Image matching proceeds in real time using dynamic programming on scale-invariant features extracted from each circular view. By analyzing the shape of the matching curve, the relative orientation of pairs of views can be recovered and utilized for navigation. When navigating, the robot continually matches its current view against stored reference views taken from known locations, and determines its location and heading from the properties of the matching results. Experiments show that our method is robust to occlusion, repeating patterns, and lighting variations

We propose a new system for vision-based mobile robot navigation in an unmodeled environment. Simple, unobtrusive artificial landmarks are used as navigation and localization aids. The landmark patterns are designed so that they can be reliably detected in real-time in images taken with the robot's camera over a wide range of viewing configurations. The code for the recognition algorithm is available in the web site.

An offset-polygon annulus region is defined in terms of a polygon P and a distance δ > 0 (offset of P). In this paper we solve several containment problems for polygon annulus regions with respect to an input point set. Optimization criteria include both maximizing the number of points contained in a fixed size annulus and minimizing the size of the annulus needed to contain all points. We address the following variants of the problem: placement of an annulus of a convex polygon as well as of a simple polygon; placement by translation only, or by translation and rotation; off-line and on-line versions of the corresponding decision problems; and decision as well as optimization versions of the problems. We present efficient algorithms in each case.

No abstract available.

We consider the problem of planning the configuration of a sensor within the context of a robotic task. In this paper, we focus on geometrically specified tasks in the plane, and give algorithms for computing the regions from which an idealized point-and-shoot sensor can detect a polygonal robot. Our main algorithm allows sensor configurations from which the robot may be partially obstructed, and computes the regions from which the robot can be detected as it translates through the goal at a known orientation. This algorithm runs in time O(kmn/sup 3/(n+m)) for an environment of complexity n, a robot of complexity m, and a goal of complexity k. The regions constructed can be used by an active sensing system to configure sensors that are guaranteed to observe the robot as it enters the goal.>

Uncertainty in the execution of robot motion plans must be accounted for in the geometric computations from which plans are obtained, especially in the case where position sensing is inaccurate. We give an Ο(n2 log n) algorithm to find a single commanded motion direction which will guarantee a successful motion in the plane from a specified start to a specified goal whenever such a one-step motion is possible. The plans account for uncertainty in the start position and in robot control, and anticipate that the robot may stick on or slide along obstacle surfaces with which it comes in contact. This bound improves on the best previous bound by a quadratic factor, and is achieved in part by a new analysis of the geometric complexity of the backprojection of the goal as a function of commanded motion direction.