While a large amount of work exists in the literature relating to place/location recognition, very few of these provide a robust way of dealing with large amounts of lighting changes in locations of interest. In this paper, we address the problem under the additional constraint that a pose estimate from the current location of the camera to the reference location is to be estimated. This requires robust feature matching to estimate corresponding points, and not just image-level matching, as is often done in the literature. We present a method to learn a matching function from training data that is representative of the lighting variations to be modeled, under weak assumptions. Lighting variation in the image descriptors is modeled using a probability distribution on the discretized descriptor space. Results are presented on a live visual SLAM system in outdoor environments and in an indoor simulated environment, which demonstrate the efficacy of the proposed method.

Traditional vision-based localization methods such as visual SLAM suffer from practical problems in outdoor environments such as unstable feature detection and inability to perform location recognition under lighting, perspective, weather and appearance change. Additionally map construction on a large scale in these systems presents its own challenges. In this work, we present a novel method for precisely localizing vehicles on the road using signs marked on the road (road markings), which have the advantage of being distinct and easy to detect, their detection being robust under changes in lighting and weather. Our method uses corners detected on road markings to perform localization in global coordinates. The method consists of two phases - a mapping phase when a high-quality GPS device is used to automatically survey road marks and add them to a light-weight “map” or database, and a localization phase where road mark detection and look-up in the map, combined with visual odometry, produces precise localization. We present experiments using a real-time implementation operating in a car that demonstrates the improved localization robustness and accuracy of our system even when using road marks alone. However, in this case the trajectory between road marks has to be filled-in by visual odometry, which contributes drift. Hence, we also present a mechanism for combining road-mark-based maps with sparse feature-based maps that results in greater accuracy still. We see our use of road marks as a significant step in the general trend of using higher-level features for improved localization performance irrespective of environment conditions.

Reliable lane-level localization is a requirement for many driver-assistance methods as well as for autonomous driving. Localization using cameras is desirable due to ubiquity and cheapness of sensors but is hard to achieve reliably. We propose a method towards reliable visual localization using traffic signs painted on the road such as arrows, pedestrian crossings, and speed limits. These road markings are relatively easily detected since they are designed to be highly conspicuous. Our method automatically recognizes road markings and uses features detected within them to compute the location of the vehicle. This provides an absolute global localization if the road markings have been surveyed before hand, and relative positioning information otherwise. We demonstrate using experiments and with groundtruth data that our method provides accurate lane-level visual localization under various lighting conditions and using various types of road markings.

We present a system for detecting and recognizing road markings from video input obtained from an in-car camera. Our system learns feature-based templates of road markings from training data and matches these templates to detected features in the test images during runtime. We use MSER features and perform the template matching in an efficient manner so that our system can detect multiple road markings in a single image. Our system also scales well with the number of categories of road markings to be detected. For evaluating our system, we present an extensive dataset (available from www.ananth.in/RoadMarkingDetection.html) of road markings with ground truth labels, which we hope will be useful as a benchmark dataset for future researchers in this area.

We present a method to reconstruct indoor environments from stereo image pairs, suitable for the navigation of robots. To enable a robot to navigate solely using visual cues it receives from a stereo camera, the depth information needs to be extracted from the image pairs and combined into a common representation. The initially determined raw depthmaps are fused into a two level heightmap representation which contains a floor and a ceiling height level. To reduce the noise in the height maps we employ a total variation regularized energy functional.With this 2.5D representation of the scene the computational complexity of the energy optimization is reduced by one dimension in contrast to other fusion techniques that work on the full 3D space such as volumetric fusion. While we show only results for indoor environments the approach can be extended to generate heightmaps for outdoor environments.

Categorizing areas such as rooms and corridors using a discrete set of labels has been of long-standing interest to the robotics community. A map with labels such as kitchen, lab, copy room etc provides a basic amount of semantic information that can enable a robot to perform a number of tasks specified in human-centric terms rather than just map coordinates. In this work, we propose a method to label areas in a pre-built map using information from camera images. In contrast to most existing approaches, our method labels the area that is viewed in the camera image rather than just the current robot location. Place labels are generated from the image input using the PLISS system [14]. The label information on the viewed areas is integrated in a Conditional Random Field (CRF) that also considers higher level semantics such as adjacency and place boundaries. We demonstrate our technique on maps built using from laser and visual SLAM systems. We obtain the correct place categorization of a very high percentage of the map areas even when the place categorization system is trained using images only from the internet.

We present a new Gaussian process (GP) inference algorithm, called online sparse matrix Gaussian processes (OSMGP), and demonstrate its merits by applying it to the problems of head pose estimation and visual tracking. The OSMGP is based upon the observation that for kernels with local support, the Gram matrix is typically sparse. Maintaining and updating the sparse Cholesky factor of the Gram matrix can be done efficiently using Givens rotations. This leads to an exact, online algorithm whose update time scales linearly with the size of the Gram matrix. Further, we provide a method for constant time operation of the OSMGP using matrix downdates. The downdates maintain the Cholesky factor at a constant size by removing certain rows and columns corresponding to discarded training examples. We demonstrate that, using these matrix downdates, online hyperparameter estimation can be included at cost linear in the number of total training examples. We describe a robust appearance-based head pose estimation system based upon the OSMGP. Numerous experiments and comparisons with existing methods using a large dataset system demonstrate the efficiency and accuracy of our system. Further, to showcase the applicability of OSMGP to a wide variety of problems, we also describe a regression-based visual tracking method. Experiments show that our OSMGP algorithm generalizes well using online learning.

We describe a system for generating coherent movies from a collection of unedited videos. The generation process is guided by one or more input keyframes, which determine the content of the generated video. The basic mechanism involves similarity analysis using the histogram intersection function. The function is applied to spatial pyramid histograms computed on the video frames in the collection using Dense SIFT features. A two-directional greedy path finding algorithm is used to select and arrange frames from the collection while maintaining visual similarity, coherence, and continuity. Our system demonstrates promising results on large video collections and is a first step towards increased automation in non-linear video editing.

Automatic detection of landmarks, usually special places in the environment such as gateways, for topological mapping has proven to be a difficult task. We present the use of Bayesian surprise, introduced in computer vision, for landmark detection. Further, we provide a novel hierarchical, graphical model for the appearance of a place and use this model to perform surprise-based landmark detection. Our scheme is agnostic to the sensor type, and we demonstrate this by implementing a simple laser model for computing surprise. We evaluate our landmark detector using appearance and laser measurements in the context of a topological mapping algorithm, thus demonstrating the practical applicability of the detector.

Pose estimation of outdoor robots presents some distinct challenges due to the various uncertainties in the robot sensing and action. In particular, global positioning sensors of outdoor robots do not always work perfectly, causing large drift in the location estimate of the robot. To overcome this common problem, we propose a new approach for global localization using place recognition. First, we learn the location of some arbitrary key places using odometry measurements and GPS measurements only at the start and the end of the robot trajectory. In subsequent runs, when the robot perceives a key place, our fixed-lag smoother fuses odometry measurements with the relative location to the key place to improve its pose estimate. Outdoor mobile robot experiments show that place recognition measurements significantly improve the estimate of the smoother in the absence of GPS measurements.

In this paper, we present incremental smoothing and mapping (iSAM), which is a novel approach to the simultaneous localization and mapping problem that is based on fast incremental matrix factorization. iSAM provides an efficient and exact solution by updating a QR factorization of the naturally sparse smoothing information matrix, thereby recalculating only those matrix entries that actually change. iSAM is efficient even for robot trajectories with many loops as it avoids unnecessary fill-in in the factor matrix by periodic variable reordering. Also, to enable data association in real time, we provide efficient algorithms to access the estimation uncertainties of interest based on the factored information matrix. We systematically evaluate the different components of iSAM as well as the overall algorithm using various simulated and real-world datasets for both landmark and pose-only settings.

We introduce incremental smoothing and mapping (iSAM), a novel approach to the problem of simultaneous localization and mapping (SLAM) that addresses the data association problem and allows real-time application in large-scale environments. We employ smoothing to obtain the complete trajectory and map without the need for any approximations, exploiting the natural sparsity of the smoothing information matrix. A QR-factorization of this information matrix is at the heart of our approach. It provides efficient access to the exact covariances as well as to conservative estimates that are used for online data association. It also allows recovery of the exact trajectory and map at any given time by back-substitution. Instead of refactoring in each step, we update the QR-factorization whenever a new measurement arrives. We analyze the effect of loops, and show how our approach extends to the non-linear case. Finally, we provide experimental validation of the overall non-linear algorithm based on the standard Victoria Park data set with unknown correspondences.

We present an algorithm for pose estimation using fixed-lag smoothing. We show that fixed-lag smoothing enables inclusion of measurements from multiple asynchronous measurement sources in an optimal manner. Since robots usually have a plurality of uncoordinated sensors, our algorithm has an advantage over filtering-based estimation algorithms, which cannot incorporate delayed measurements optimally. We provide an implementation of the general fixed-lag smoothing algorithm using square root smoothing, a technique that has become prominent. Square root smoothing uses fast sparse matrix factorization and enables our fixed-lag pose estimation algorithm to run at upwards of 20 Hz. Our algorithm has been extensively tested over hundreds of hours of operation on a robot operating in outdoor environments. We present results based on these tests that verify our claims using wheel encoders, visual odometry, and GPS as sensors.

We present a particle filtering algorithm to construct topological maps of an uninstrument environment. The algorithm presented here constructs the posterior on the space of all possible topologies given measurements, and is based on our previous work on a Bayesian inference framework for topological maps (A. Ranganathan and F. Dellaert, 2004). Constructing the posterior solves the perceptual aliasing problem in a general, robust manner. The use of a Rao-Blackwellized particle filter (RBPF) for this purpose makes the inference in the space of topologies incremental and run in real-time. The RBPF maintains the joint posterior on topological maps and locations of landmarks. We demonstrate that, using the landmark locations thus obtained, the global metric map can be obtained from the topological map generated by our algorithm through a simple post-processing step. A data-driven proposal is provided to overcome the degeneracy problem inherent in particle filters. The use of a Dirichlet process prior on landmark labels is also a novel aspect of this work. We use laser range scan and odometry measurements to present experimental results on a robot

While probabilistic techniques have previously been investigated extensively for performing inference over the space of metric maps, no corresponding general-purpose methods exist for topological maps. We present the concept of probabilistic topological maps (PTMs), a sample-based representation that approximates the posterior distribution over topologies, given available sensor measurements. We show that the space of topologies is equivalent to the intractably large space of set partitions on the set of available measurements. The combinatorial nature of the problem is overcome by computing an approximate, sample-based representation of the posterior. The PTM is obtained by performing Bayesian inference over the space of all possible topologies, and provides a systematic solution to the problem of perceptual aliasing in the domain of topological mapping. In this paper, we describe a general framework for modeling measurements, and the use of a Markov-chain Monte Carlo algorithm that uses specific instances of these models for odometry and appearance measurements to estimate the posterior distribution. We present experimental results that validate our technique and generate good maps when using odometry and appearance, derived from panoramic images, as sensor measurements.

While probabilistic techniques have been considered extensively in the context of metric maps, no general purpose probabilistic methods exist for topological maps. We present the concept of probabilistic topological maps (PTMs), a sample-based representation that approximates the posterior distribution over topologies given the available sensor measurements. The PTM is obtained through the use of MCMC-based Bayesian inference over the space of all possible topologies. It is shown that the space of all topologies is equivalent to the space of set partitions of all available measurements. While the space of possible topologies is intractably large, our use of Markov chain Monte Carlo sampling to infer the approximate histograms overcomes the combinatorial nature of this space and provides a general solution to the correspondence problem in the context of topological mapping. We present experimental results that validate our technique and generate good maps even when using only odometry as the sensor measurements.

Motion-planning problems can be solved by discretizing the continuous configuration space, for example with graph-based or cell-based techniques. We study rapidly exploring random trees (RRTs) as an example of graph-based techniques and the parti-game method as an example of cell-based techniques. We then propose parti-game directed RRTs (PDRRTs) as a novel technique that combines them. PDRRTs are based on the parti-game method but use RRTs as local controllers rather than the simplistic controllers used by the parti-game method. Our experimental results show that PDRRTs plan faster and solve more motion-planning problems than RRTs and plan faster and with less memory than the parti-game method.

In this paper, we describe a reactive robot architecture that uses fast replanning methods to avoid the shortcomings of reactive navigation, such as getting stuck in box canyons or in front of small openings. Our robot architecture differs from other robot architectures in that it gives planning progressively greater control of the robot if reactive navigation continues to fail, until planning controls the robot directly. Our first experiments on a Nomad robot and in simulation demonstrate that our robot architecture promises to simplify the programming of reactive robot architectures and results in robust navigation, smooth trajectories, and reasonably good navigation performance.