Autonomous robots operating in semi- or unstructured environments, e.g. during search and rescue missions, require methods for online on-board creation of maps to support path planning and obstacle avoidance. Perception based on stereo cameras is well suited for mixed indoor/outdoor environments. The creation of full 3D maps in GPS-denied areas however is still a challenging task for current robot systems, in particular due to depth errors resulting from stereo reconstruction. State-of-the-art 6D SLAM approaches employ graph-based optimization on the relative transformations between keyframes or local submaps. To achieve loop closures, correct data association is crucial, in particular for sensor input received at different points in time. In order to approach this challenge, we propose a novel method for submap matching. It is based on robust keypoints, which we derive from local obstacle classification. By describing geometrical 3D features, we achieve invariance to changing viewpoints and varying light conditions. We performed experiments in indoor, outdoor and mixed environments. In all three scenarios we achieved a final 3D position error of less than 0.23% of the full trajectory. In addition, we compared our approach with a 3D RBPF SLAM from previous work, achieving an improvement of at least 27% in mean 2D localization accuracy in different scenarios.

Teams of mobile robots can be deployed in search and rescue missions to explore previously unknown environments. Methods for joint localization and mapping constitute the basis for (semi-)autonomous cooperative action, in particular when navigating in GPS-denied areas. As communication losses may occur, a decentralized solution is required. With these challenges in mind, we designed a submap-based SLAM system that relies on inertial measurements and stereo-vision to create multi-robot dense 3D maps. For online pose and map estimation, we integrate the results of keyframe-based local reference filters through incremental graph SLAM. To the best of our knowledge, we are the first to combine these two methods to benefit from their particular advantages for 6D multi-robot localization and mapping: Local reference filters on each robot provide real-time, long-term stable state estimates that are required for stabilization, control and fast obstacle avoidance, whereas online graph optimization provides global multi-robot pose and map estimates needed for cooperative planning. We propose a novel graph topology for a decoupled integration of local filter estimates from multiple robots into a SLAM graph according to the filters' uncertainty estimates and independence assumptions and evaluated its benefits on two different robots in indoor, outdoor and mixed scenarios. Further, we performed two extended experiments in a multi-robot setup to evaluate the full SLAM system, including visual robot detections and submap matches as inter-robot loop closure constraints.

Local fusion of disparity maps allows fast parallel 3D modeling of large scenes that do not fit into main memory. While existing methods assume a constant disparity uncertainty, disparity errors typically vary spatially from tenths of pixels to several pixels. In this paper we propose a method that employs a set of Gaussians for different disparity classes, instead of a single error model with only one variance. The set of Gaussians is learned from the difference between generated disparity maps and ground-truth disparities. Pixels are assigned particular disparity classes based on a Total Variation (TV) feature measuring the local oscillation behavior of the 2D disparity map. This feature captures uncertainty caused for instance by lack of texture or fron to-parallel bias of the stereo method. Experimental results on several datasets in varying configurations demonstrate that our method yields improved performance both qualitatively and quantitatively.

The creation of local and global maps is crucial for (semi-)autonomous operation of mobile robots in previously unknown environments, e.g. during search and rescue missions. We developed an on-board stereo-vision based mapping system, thereby introducing local obstacle maps that can directly be used for fast local obstacle avoidance and path planning. In addition, we designed them to constitute a suitable input to a widely-used simultaneous localization and mapping (SLAM) algorithm. We performed experiments in unknown indoor, unstructured outdoor as well as mixed environments and demonstrated the applicability of our method to camera setups with small as well as wide field of view. In all three scenarios, we achieved a final 2D position error of less than 0.08% of the full trajectory.

Real-time environmental depth perception and ego-motion estimation is essential for all mobile robotic systems. We present a system that computes high quality depth images with 0.5 MPixel resolution using Semi-Global Matching (SGM) and estimates the ego-motion by key frame based visual odometry fused with the data of an inertial measurement unit (IMU). The hardware includes a pair of cameras, a small Intel Core2Duo CPU board, a Spartan 6 FPGA board, an OMAP3530 ARM processor board as well as an IMU. The total weight of the experimental setup is 830 g and is, thus, also feasible for hand-held or flying platforms. Experiments show that the vision system runs at 14.6 Hz with a latency of around 250 ms and produces high quality depth images as well as reliable 6D ego-motion estimates. In the fusion algorithm of visual odometry and IMU data, time delays of the vision system are compensated and a system state estimate is available at the full data rate of the IMU which is important for system control. This paper presents the integration of different techniques into a fast, light weight, real-time system and validates its performance by experiments on real data.

We introduce our new quadrotor platform for realizing autonomous navigation in unknown indoor/outdoor environments. Autonomous waypoint navigation, obstacle avoidance and flight control is implemented on-board. The system does not require a special environment, artificial markers or an external reference system. We developed a monolithic, mechanically damped perception unit which is equipped with a stereo camera pair, an Inertial Measurement Unit (IMU), two processor-and an FPGA board. Stereo images are processed on the FPGA by the Semi-Global Matching algorithm. Keyframe-based stereo odometry is fused with IMU data compensating for time delays that are induced by the vision pipeline. The system state estimate is used for control and on-board 3D mapping. An operator can set waypoints in the map, while the quadrotor autonomously plans its path avoiding obstacles. We show experiments with the quadrotor flying from inside a building to the outside and vice versa, traversing a window and a door respectively. A video of the experiments is part of this work. To the best of our knowledge, this is the first autonomously flying system with complete on-board processing that performs waypoint navigation with obstacle avoidance in geometrically unconstrained, complex indoor/outdoor environments.

For autonomous navigation tasks it is important that the robot always has a good estimate of its current pose with respect to its starting position and - in terms of orientation - with respect to the gravity vector. For this, the robot should make use of all available information and be robust against the failure of single sensors. In this paper a multisensor data fusion algorithm for the six-legged walking robot DLR Crawler is presented. The algorithm is based on an indirect feedback information filter that fuses measurements from an inertial measurement unit (IMU) with relative 3D leg odometry measurements and relative 3D visual odometry measurements from a stereo camera. Errors of the visual odometry are computed and considered in the filtering process in order to achieve accurate pose estimates which are robust against visual odometry failure. The algorithm was successfully tested and results are presented.

Stereo matching commonly requires rectified images that are computed from calibrated cameras. Since all underlying parametric camera models are only approximations, calibration and rectification will never be perfect. Additionally, it is very hard to keep the calibration perfectly stable in application scenarios with large temperature changes and vibrations. We show that even small calibration errors of a quarter of a pixel are severely amplified on certain structures. We discuss a robotics and a driver assistance example where sub-pixel calibration errors cause severe problems. We propose a filter solution based on signal theory that removes critical structures and makes stereo algorithms less sensitive to calibration errors. Our approach does not aim to correct decalibration, but rather to avoid amplifications and mismatches. Experiments on ten stereo pairs with ground truth and simulated decalibrations as well as images from robotics and driver assistance scenarios demonstrate the success and limitations of our solution that can be combined with any stereo method.

A navigation algorithm for mobile robots in unknown rough terrain has been developed. The algorithm is solely based on stereo images and suitable for wheeled and legged robots. The navigation system is able to guide the robot along a short and safe path to a goal specified by the operator and given in coordinates relative to the starting point of the robot. The algorithm uses visual odometry for localization. The terrain is modeled from stereo images and its traversability is estimated. A D* Lite planner is used for efficiently planning a short and safe path by incorporating terrain traversability in the planning process. The robot actively explores its environment as it follows the path to the goal. The algorithm has been tested on a wheel driven mobile robot and on a six-legged walking robot on rough terrain.

Stereo correspondence methods rely on matching costs for computing the similarity of image locations. We evaluate the insensitivity of different costs for passive binocular stereo methods with respect to radiometric variations of the input images. We consider both pixel-based and window-based variants like the absolute difference, the sampling-insensitive absolute difference, and normalized cross correlation, as well as their zero-mean versions. We also consider filters like LoG, mean, and bilateral background subtraction (BilSub) and nonparametric measures like Rank, SoftRank, Census, and Ordinal. Finally, hierarchical mutual information (HMI) is considered as pixelwise cost. Using stereo data sets with ground-truth disparities taken under controlled changes of exposure and lighting, we evaluate the costs with a local, a semiglobal, and a global stereo method. We measure the performance of all costs in the presence of simulated and real radiometric differences, including exposure differences, vignetting, varying lighting, and noise. Overall, the ranking of methods across all data sets and experiments appears to be consistent. Among the best costs are BilSub, which performs consistently very well for low radiometric differences; HMI, which is slightly better as pixelwise matching cost in some cases and for strong image noise; and Census, which showed the best and most robust overall performance.

This paper describes the Semi-Global Matching (SGM) stereo method. It uses a pixelwise, Mutual Information based matching cost for compensating radiometric differences of input images. Pixelwise matching is supported by a smoothness constraint that is usually expressed as a global cost function. SGM performs a fast approximation by pathwise optimizations from all directions. The discussion also addresses occlusion detection, subpixel refinement and multi-baseline matching. Additionally, postprocessing steps for removing outliers, recovering from specific problems of structured environments and the interpolation of gaps are presented. Finally, strategies for processing almost arbitrarily large images and fusion of disparity images using orthographic projection are proposed.A comparison on standard stereo images shows that SGM is among the currently top-ranked algorithms and is best, if subpixel accuracy is considered. The complexity is linear to the number of pixels and disparity range, which results in a runtime of just 1-2s on typical test images. An in depth evaluation of the Mutual Information based matching cost demonstrates a tolerance against a wide range of radiometric transformations. Finally, examples of reconstructions from huge aerial frame and pushbroom images demonstrate that the presented ideas are working well on practical problems.

Stereo correspondence methods rely on matching costs for computing the similarity of image locations. In this paper we evaluate the insensitivity of different matching costs with respect to radiometric variations of the input images. We consider both pixel-based and window-based variants and measure their performance in the presence of global intensity changes (e.g., due to gain and exposure differences), local intensity changes (e.g., due to vignetting, non-Lambertian surfaces, and varying lighting), and noise. Using existing stereo datasets with ground-truth disparities as well as six new datasets taken under controlled changes of exposure and lighting, we evaluate the different costs with a local, a semi-global, and a global stereo method.

This paper considers the use of stereo vision in structured environments. Sharp discontinuities and large untextured areas must be anticipated, but complex or natural shapes of objects and fine structures should be handled as well. Additionally, radiometric differences of input images often occur in practice. Finally, computation time is an issue for handling large or many images in acceptable time. The Semi-Global Matching method is chosen as it fulfills already many of the requirements. Remaining problems in structured environments are carefully analyzed and two novel extensions suggested. Firstly, intensity consistent disparity selection is proposed for handling untextured areas. Secondly, discontinuity preserving interpolation is suggested for filling holes in the disparity images that are caused by some filters. It is shown that the performance of the new method on test images with ground truth is comparable to the currently best stereo methods, but the complexity and runtime is much lower.

This paper considers the objectives of accurate stereo matching, especially at object boundaries, robustness against recording or illumination changes and efficiency of the calculation. These objectives lead to the proposed semi-global matching method that performs pixelwise matching based on mutual information and the approximation of a global smoothness constraint. Occlusions are detected and disparities determined with sub-pixel accuracy. Additionally, an extension for multi-baseline stereo images is presented. There are two novel contributions. Firstly, a hierarchical calculation of mutual information based matching is shown, which is almost as fast as intensity based matching. Secondly, an approximation of a global cost calculation is proposed that can be performed in a time that is linear to the number of pixels and disparities. The implementation requires just 1 second on typical images.

Camera motion estimation is useful for a range of applications. Usually, feature tracking is performed through the sequence of images to determine correspondences. Furthermore, robust statistical techniques are normally used to handle large number of outliers in correspondences. This paper proposes a new method that avoids both. Motion is calculated between two consecutive stereo images without any pre-knowledge or prediction about feature location or the possibly large camera movement. This permits a lower frame rate and almost arbitrary movements. Euclidean constraints are used to incrementally select inliers from a set of initial correspondences, instead of using robust statistics that has to handle all inliers and outliers together. These constraints are so strong that the set of initial correspondences can contain several times more outliers than inliers. Experiments on a worst-case stereo sequence show that the method is robust, accurate and can be used in real-time.

Object technology is the dominant software engineering paradigm in most undergraduate computer science courses. Two important topics in this area are design patterns and Java programming, and indeed these are increasingly taught side by side. This paper describes a novel form of visualisation that makes use of a combination of virtual reality and hypertext to represent the structure and behaviour of object-oriented design patterns and simple Java programs, with the overall aim of providing tools to enhance learning and understanding of these topics.For patterns, the solution part of a pattern, which consists of a software fragment of interacting objects, is visualised in an animated 3-dimensional virtual environment. The virtual reality view is embedded in a rich inter-linked hyper-textual description.For Java programs, the source code is first transformed into the same simple software description language (SVL, Software Visualisation Language) used for patterns. Also included is a simple textual specification of a run-time scenario defining the creation of objects and their typical interaction, together with explanatory "comments". As with design patterns, the structure and run-time behaviour of the Java program can then be visualised in three dimensions with synchronised hyper-textual commentary.