Sliding window estimation is widely used for online simultaneous localization and mapping. While increasing the sliding window size generally yields improved accuracy, it also comes at an increase in computational cost. In order to reduce this cost, we propose smarter non-uniform sampling of the trajectory representation over the sliding window. This non-uniform temporal resolution is possible with continuous-time representations that allow freely adjustable knots location. Four strategies for selecting the knots location are presented and evaluated based on a real data laser-odometry SLAM problem. The results clearly show that non-uniform distributions of knots can be superior to uniform distribution in terms of accuracy per computation time.

Robust, scalable place recognition is a core competency for many robotic applications. However, when revisiting places over and over, many state-of-the-art approaches exhibit reduced performance in terms of computation and memory complexity and in terms of accuracy. For successful deployment of robots over long time scales, we must develop algorithms that get better with repeated visits to the same environment, while still working within a fixed computational budget. This paper presents and evaluates an algorithm that alternates between online place recognition and offline map maintenance with the goal of producing the best performance with a fixed map size. At the core of the algorithm is the concept of a Summary Map, a reduced map representation that includes only the landmarks that are deemed most useful for place recognition. To assign landmarks to the map, we use a scoring function that ranks the utility of each landmark and a sampling policy that selects the landmarks for each place. The Summary Map can then be used by any descriptor-based inference method for constant-complexity online place recognition. We evaluate a number of scoring functions and sampling policies and show that it is possible to build and maintain maps of a constant size and that place-recognition performance improves over multiple visits.

Robust, scalable localization unlocks path-planning, obstacle avoidance as well as manipulation and thus is a core competency for many robotic applications. However, as we leave the lab and move out in the world, models of the environment no longer span distances of meters but kilometers in length. Now, gigabytes instead of megabytes of memory are required to hold the model of the environment required for localization. Discarding data and keeping the map representation compact is thus essential for any meaningful application. This paper presents and evaluates a map compression algorithm that approaches this data-reduction as an constrained optimization problem. At the core of the algorithm is the concept of a Summary Map, a reduced map representation that includes only the landmarks that are deemed most useful for place recognition. To assign landmarks to the map we have to satisfy the conflicting goals of map coverage and localizability as well as our tight memory budget. While using an optimization approach for compression is not novel, in this paper we propose adaptations to drastically reduce the computational requirements. Our approach improves scalability from trajectories of a few tens of meters manageable by the state of the art to virtually unlimited dataset sizes in our system. We evaluate the performance of various compression levels as well as several methods for selecting the best localization landmarks from outdoor datasets.

Place recognition is a core competency for any visual simultaneous localization and mapping system. Identifying previously visited places enables the creation of globally accurate maps, robust relocalization, and multi-user mapping. To match one place to another, most state-of-the-art approaches must decide a priori what constitutes a place, often in terms of how many consecutive views should overlap, or how many consecutive images should be considered together. Unfortunately, depending on thresholds such as these, limits their generality to different types of scenes. In this paper, we present a placeless place recognition algorithm using a novel vote-density estimation technique that avoids heuristically discretizing the space. Instead, our approach considers place recognition as a problem of continuous matching between image streams, automatically discovering regions of high vote density that represent overlapping trajectory segments. The resulting algorithm has a single free parameter and all remaining thresholds are set automatically using well-studied statistical tests. We demonstrate the efficiency and accuracy of our methodology on three outdoor sequences: A comprehensive evaluation against ground-truth from publicly available datasets shows that our approach outperforms several state-of-the-art algorithms for place recognition.

In developing autonomous solutions for mapping and localization, one problem that often needs to be dealt with is determining when an area is revisited despite having poor or no prior information on the relative alignment error. There are well-formulated approaches for recognizing such matches using the rich information in camera data; however, it is a much more challenging problem using lidar sensors alone. Most existing approaches employ a pairwise place comparison of place descriptors and thus finding matches requires linear time per place. We instead propose the use of a keypoint voting approach to achieve sub-linear matching times. A constant number of nearest neighbor votes per keypoint are queried from a database of local descriptors and aggregated to determine likely place matches. It becomes critical to analyze the distributions of vote scores such that a suitable threshold for matching scores can be determined a priori, so that the system is not overwhelmed by false positives nor starved for true matches. We have empirically determined that the vote scores follow a log-normal distribution, and we are able to fit a parametric model of its hyper-parameters based on the number of neighbors, the number of keypoints in a place, and the total number of keypoints in the database. We demonstrate the performance of our system in a variety of large scale 3D lidar datasets using data collected from a continually scanning handheld lidar sensor, and also on two publicly available lidar datasets.

Creating rich representations of environments requires integration of multiple sensing modalities with complementary characteristics such as range and imaging sensors. To precisely combine multisensory information, the rigid transformation between different sensor coordinate systems (i.e., extrinsic parameters) must be estimated. The majority of existing extrinsic calibration techniques require one or multiple planar calibration patterns (such as checkerboards) to be observed simultaneously from the range and imaging sensors. The main limitation of these approaches is that they require modifying the scene with artificial targets. In this paper, we present a novel algorithm for extrinsically calibrating a range sensor with respect to an image sensor with no requirement of external artificial targets. The proposed method exploits natural linear features in the scene to precisely determine the rigid transformation between the coordinate frames. First, a set of 3D lines (plane intersection and boundary line segments) are extracted from the point cloud, and a set of 2D line segments are extracted from the image. Correspondences between the 3D and 2D line segments are used as inputs to an optimization problem which requires jointly estimating the relative translation and rotation between the coordinate frames. The proposed method is not limited to any particular types or configurations of sensors. To demonstrate robustness, efficiency and generality of the presented algorithm, we include results using various sensor configurations.

The building sector is the dominant consumer of energy and therefore a major contributor to anthropomorphic climate change. The rapid generation of photorealistic, 3D environment models with incorporated surface temperature data has the potential to improve thermographic monitoring of building energy efficiency. In pursuit of this goal, we propose a system which combines a range sensor with a thermal-infrared camera. Our proposed system can generate dense 3D models of environments with both appearance and temperature information, and is the first such system to be developed using a low-cost RGB-D camera. The proposed pipeline processes depth maps successively, forming an ongoing pose estimate of the depth camera and optimizing a voxel occupancy map. Voxels are assigned 4 channels representing estimates of their true RGB and thermal-infrared intensity values. Poses corresponding to each RGB and thermal-infrared image are estimated through a combination of timestamp-based interpolation and a predetermined knowledge of the extrinsic calibration of the system. Raycasting is then used to color the voxels to represent both visual appearance using RGB, and an estimate of the surface temperature. The output of the system is a dense 3D model which can simultaneously represent both RGB and thermal-infrared data using one of two alternative representation schemes. Experimental results demonstrate that the system is capable of accurately mapping difficult environments, even in complete darkness.

Three-dimensional perception is a key technology for many robotics applications, including obstacle detection, mapping, and localization. There exist a number of sensors and techniques for acquiring 3-D data, many of which have particular utility for various robotic tasks. We introduce a new design for a 3-D sensor system, constructed from a 2-D range scanner coupled with a passive linkage mechanism, such as a spring. By mounting the other end of the passive linkage mechanism to a moving body, disturbances resulting from accelerations and vibrations of the body propel the 2-D scanner in an irregular fashion, thereby extending the device's field of view outside of its standard scanning plane. The proposed 3-D sensor system is advantageous due to its mechanical simplicity, mobility, low weight, and relatively low cost. We analyze a particular implementation of the proposed device, which we call Zebedee, consisting of a 2-D time-of-flight laser range scanner rigidly coupled to an inertial measurement unit and mounted on a spring. The unique configuration of the sensor system motivates unconventional and specialized algorithms to be developed for data processing. As an example application, we describe a novel 3-D simultaneous localization and mapping solution in which Zebedee is mounted on a moving platform. Using a motion capture system, we have verified the positional accuracy of the sensor trajectory. The results demonstrate that the six-degree-of-freedom trajectory of a passive spring-mounted range sensor can be accurately estimated from laser range data and industrial-grade inertial measurements in real time and that a quality 3-D point cloud map can be generated concurrently using the same data.

The generation of accurate, watertight, three-dimensional models of environments are often crucial for the purposes of scientific study and infrastructure management. Most commonly, such models are acquired by using range sensors producing point clouds, and further processing steps are required for the construction of a surface model. We used a mobile lidar to map several kilometers of a natural cave system in order to obtain 3D volumetric models for use in scientific research studying the local palaeo-climatic record. For unstructured and GPS-denied environments, such as cave systems, the process of acquiring a complete map is difficult and further complicated by limited mobility within the cave. During the mapping process, many unwanted measurements occur due to occlusions from moving objects such as other people present in the cave. Most common point cloud surface reconstruction techniques are not designed to deal these occlusions; i.e., they require manual cleanup of the data set or are not capable of generating watertight surfaces. The large scale of the environments introduces the additional challenge of dealing with memory limitations. We propose a new volume-based approach to reconstruct a watertight surface from range measurements of enclosed environments without limitation on the scale of the collected data. Our approach carves all unoccupied voxels from the sensor to a triangulated and rasterized surface between successive scans, which is intended to fill in the missing data between the scan rays. The surface is then constructed from the isosurface between unoccupied and unknown cells. By decomposing the space, we are able to handle large-scale data without exceeding the memory limitation of a standard PC, at the cost of some additional computation time. The algorithm has been evaluated across several datasets within a variety of environments and observed to build more complete volumetric models than a simple space carving approach. We have mapped several kilometers of cave networks and, with the described method, produced watertight reconstructions suitable for further scientific analysis.

Reliable real-time localization is a key component of autonomous industrial vehicle systems. We consider the problem of using on-board vision to determine a vehicle's pose in a known, but non-static, environment. While feasible technologies exist for vehicle localization, many are not suited for industrial settings where the vehicle must operate dependably both indoors and outdoors and in a range of lighting conditions. We extend the capabilities of an existing vision-based localization system, in a continued effort to improve the robustness, reliability and utility of an automated industrial vehicle system. The vehicle pose is estimated by comparing an edge-filtered version of a video stream to an available 3D edge map of the site. We enhance the previous system by additionally filtering the camera input for straight lines using a Hough transform, observing that the 3D environment map contains only linear features. In addition, we present an automated approach for generating 3D edge maps from laser point clouds, removing the need for manual map surveying and also reducing the time for map generation down from days to minutes. We present extensive localization results in multiple lighting conditions comparing the system with and without the proposed enhancements.

Scan-matching is a technique that can be used for building accurate maps and estimating vehicle motion by comparing a sequence of point cloud measurements of the environment taken from a moving sensor. One challenge that arises in mapping applications where the sensor motion is fast relative to the measurement time is that scans become locally distorted and difficult to align. This problem is common when using 3D laser range sensors, which typically require more scanning time than their 2D counterparts. Existing 3D mapping solutions either eliminate sensor motion by taking a “stop-and-scan” approach, or attempt to correct the motion in an open-loop fashion using odometric or inertial sensors. We propose a solution to 3D scan-matching in which a continuous 6DOF sensor trajectory is recovered to correct the point cloud alignments, producing locally accurate maps and allowing for a reliable estimate of the vehicle motion. Our method is applied to data collected from a 3D spinning lidar sensor mounted on a skid-steer loader vehicle to produce quality maps of outdoor scenes and estimates of the vehicle trajectory during the mapping sequences.

We present a technique for high-dynamic range stereo for outdoor mobile robot applications. Stereo pairs are captured at a number of different exposures (exposure bracketing), and combined by projecting the 3D points into a common coordinate frame, and building a 3D occupancy map. We present experimental results for static scenes with constant and dynamic lighting as well as outdoor operation with variable and high contrast lighting conditions.

A coverage algorithm is an algorithm that deploys a strategy as to how to cover all points in terms of a given area using some set of sensors. In the past decades a lot of research has gone into development of coverage algorithms. Initially, the focus was coverage of structured and semi-structured indoor areas, but with time and development of better sensors and introduction of GPS, the focus has turned to outdoor coverage. Due to the unstructured nature of an outdoor environment, covering an outdoor area with all its obstacles and simultaneously performing reliable localization is a difficult task. In this paper, two path planning algorithms suitable for solving outdoor coverage tasks are introduced. The algorithms take into account the kinematic constraints of an under-actuated car-like vehicle, minimize trajectory curvatures, and dynamically avoid detected obstacles in the vicinity, all in real-time. We demonstrate the performance of the coverage algorithm in the field by achieving 95% coverage using an autonomous tractor mower without the aid of any absolute localization system or constraints on the physical boundaries of the area.

This paper presents an enhanced algorithm for matching laser scan maps using histogram correlations. The histogram representation effectively summarizes a map's salient features such that pairs of maps can be matched efficiently without any prior guess as to their alignment. The histogram matching algorithm has been enhanced in order to work well in outdoor unstructured environments by using entropy metrics, weighted histograms and proper thresholding of quality metrics. Thus our large-scale scan-matching SLAM implementation has a vastly improved ability to close large loops in real-time even when odometry is not available. Our experimental results have demonstrated a successful mapping of the largest area ever mapped to date using only a single laser scanner. We also demonstrate our ability to solve the lost robot problem by localizing a robot to a previously built map without any prior initialization.

This paper describes Atlas, a hybrid metrical/topological approach to SLAM that achieves efficient mapping of large-scale environments. The representation is a graph of coordinate frames, with each vertex in the graph representing a local frame, and each edge representing the transformation between adjacent frames. In each frame, we build a map that captures the local environment and the current robot pose along with the uncertainties of each. Each map's uncertainties are modeled with respect to its own frame. Probabilities of entities with respect to arbitrary frames are generated by following a path formed by the edges between adjacent frames, computed via Dijkstra's shortest path algorithm. Loop closing is achieved via an efficient map matching algorithm. We demonstrate the technique running in real-time in a large indoor structured environment (2.2 km path length) with multiple nested loops using laser or ultrasonic ranging sensors.

This paper presents an algorithm for feature-based exploration of a priori unknown environments. We aim to build a robot that, unsupervised, plans its motion such that it continually increases both the spatial extent and detail of its world model - its map. We present a method by which the planned motion at any instant is motivated by the geometric, spatial and stochastic characteristics of the current map. In particular each feature within the map is responsible for determining nearby unexplored areas that if visited are likely to constitute exploration. We assume that the location of the features is uncertain and represented by a set of probability distribution functions (pdfs). These distributions are used in conjunction with the robot path history to determine a robot trajectory suited to exploration. We show results that demonstrate the algorithm providing real-time exploration of a mobile robot in an unknown environment.

The paper describes a system for structure-from-motion using vanishing points and three-dimensional lines extracted from omnidirectional video sequences. Two novel aspects of this work are its deferred initialization of features using noisy observations from multiple, uncertain vantage points, and its use of dynamic programming for efficient 3D line tracking. We show preliminary results from the system for both indoor and outdoor sequences.

We consider the problem of video stabilization: removing unwanted image perturbations due to unstable camera motions. We approach this problem from an image-based rendering (IBR) standpoint. Given an unstabilized video sequence, the task is to synthesize a new sequence as seen from a stabilized camera trajectory. This task is relatively straightforward if one has a Euclidean reconstruction of the unstabilized camera trajectory and a suitable IBR algorithm. However, it is often not feasible to obtain a Euclidean reconstruction from an arbitrary video sequence. In light of this problem, we describe IBR techniques for non-metric reconstructions, which are often much easier to obtain since they do not require camera calibration. These rendering techniques are well suited to the video stabilization problem. The key idea behind our techniques is that all measurements are specified in the image space, rather than in the non-metric space.

We describe a dataset of several thousand calibrated, geo-referenced, high dynamic range color images, acquired under uncontrolled, variable illumination in an outdoor region spanning hundreds of meters. All image, feature, calibration, and geo-referencing data are available at http://city.lcs.mit.edu/data. Calibrated imagery is of fundamental interest in a wide variety of applications. We have made this data available in the belief that researchers in computer graphics, computer vision, photogrammetry and digital cartography will find it useful in several ways: as a test set for their own algorithms; as a calibrated image set for applications such as image-based rendering, metric 3D reconstruction, and appearance recovery; and as controlled imagery for integration into existing GIS systems and applications. The Web-based interface to the data provides interactive viewing of high-dynamic-range images and mosaics; extracted edge and point features; intrinsic and extrinsic calibration, along with maps of the ground context in which the images were acquired; the spatial adjacency relationships among images; the epipolar geometry relating adjacent images; compass and absolute scale overlays; and quantitative consistency measures for the calibration data.

We describe an image based rendering approach that generalizes many current image based rendering algorithms, including light field rendering and view-dependent texture mapping. In particular, it allows for lumigraph-style rendering from a set of input cameras in arbitrary configurations (i.e., not restricted to a plane or to any specific manifold). In the case of regular and planar input camera positions, our algorithm reduces to a typical lumigraph approach. When presented with fewer cameras and good approximate geometry, our algorithm behaves like view-dependent texture mapping. The algorithm achieves this flexibility because it is designed to meet a set of specific goals that we describe. We demonstrate this flexibility with a variety of examples.