2.2.1.1 Feature-Based Localization

A commonly used approach is feature-based localization, as illustrated in Figure 2.7. Figure 2.7a shows one frame of an image sequence recorded in a mapping run. Figure 2.7b has been acquired during an autonomous test drive from a rear-facing camera. Clearly, both images have been obtained from approximately the same position and angle, yet at a different time of year. The two images are registered spatially by means of a descriptor-based point feature association: salient features of the map sequence (so-called landmarks shown in blue in Figure 2.7) are associated with detected features (red) in the current image of the vehicle's rear-facing camera. Given that the 3D positions of these landmarks have been computed beforehand, for example, by bundle adjustment, it is possible to compute a 6D rigid-body transformation between both camera poses that would bring associated features in agreement. By fusing this transformation with the global reference pose of the map image and the motion information from wheel encoders and yaw rate sensors available in the vehicle, an accurate global position estimate can be recovered. More details on this feature-based localization can be found in Ziegler et al. (2014b).

2.2.1.2 Marking-Based Localization

In feature-rich environments such as urban areas, the feature-based localization method yields excellent map-relative localization results, achieving centimeter accuracy in many cases. However, this approach has two main problems: first, in suburban and rural areas, the required landmark density may drop below a required reliability level. Secondly, there is currently no feature descriptor that is robust with respect to illumination and time of year (see Valgren and Lilienthal (2010)). This is still an open problem.

Using lane markings for localization is a natural alternative. Figure 2.8 illustrates the principle presented in Schreiber et al. (2013).

Let us assume that a precise map containing all visible markings, stop lines, and curbs is available. If one projects these features onto the image, it is easy to estimate the vehicle's pose relative to the map. In practice, the matching can be done with a nearest neighbor search on the sampled map and the resulting residuals can be used to drive a Kalman filter. In suburban areas, the boundary lines of the road are often substituted with curbs. In this case, it is beneficial to support the measurements with a curb classifier. Such a system is described in Enzweiler et al. (2013) for example.

2.2.1.3 Discussion

Precise digital maps have to be gathered, processed, stored, and continuously updated. All these steps can be managed within an experiment like the Bertha drive, but cause problems for a commercial system. According to official statistics, the total length of the street network in Germany is about 650 000km and 6.5 Mio km in the United States.

Lategahn (2013) points out that the feature-based localization scheme sketched earlier leads to an average storage size of almost 1 GB/km. This still ignores the mentioned sensitivity of descriptors to changing illumination and time of the year. Even if this amount of data could be significantly reduced by optimization, storing the 3D map for an entire country would still be a challenge. This problem does not exist if only small areas need to be mapped, for example, for autonomous parking.

A second challenge is keeping the up-to-date maps. This requires the online detection of changes and a continuous update of the maps by the provider. Such a tool chain does not exist and requires further research.

The mentioned problems raise the question whether the approach of (extremely) precise maps used by numerous teams today scales to larger areas. Since humans are able to find their way safely using only simple and geometrically inaccurate maps, one might argue for more sophisticated solutions for Autonomous Driving with less precise maps and no need for a precise localization. Obviously, this would require a more powerful environment perception. For example, Zhang et al. (2013) show that the outline of an intersection can be determined from various vision cues only. The future will reveal the best compromise between map quality and image analysis effort.

2.2.2.1 Depth Estimation

The stereo camera systems used in Mercedes-Benz serial cars today have two high dynamic range color imagers with field-of-view lenses and a baseline of . The depth information is computed for a field of . Color is necessary for various tasks such as adaptive high beam (intelligent headlight control), traffic sign recognition, and construction site recognition.

Since we decided not to change the standard safety systems of our test vehicle, we were free to add and optimize a second stereo camera system just for the Autonomous Driving task. In order to get the best stereo performance possible with available FPGA hardware and imagers, we abstained from using color (no de-Bayering necessary) and enlarged the baseline to .

On the delivered images, dense disparity images are reconstructed using semi-global matching (SGM) (see Hirschmüller (2005)). The Census metric is used because it yields better results than classical scores such as the correlation coefficient, especially under adverse weather conditions and in the presence of calibration deficiencies. Due to its robustness and efficiency, SGM has been commercially used in Mercedes-Benz cars since 2013. Gehrig et al. (2009) show how to run this powerful scheme on energy-efficient, cheap FPGA hardware, allowing to compute dense high-quality depth maps in real time.

As stated in Chapter 1, SGM outperforms all known local disparity estimation schemes. A current ranking of stereo algorithms on the Middlebury data set can be consulted at Scharstein and Szeliski (2002). The KITTI Benchmark, published in 2012, contains data from real traffic scenes and has triggered new research on disparity estimation for this specific field (see Geiger (n.d.) and Geiger et al. (2012)).

The large measurement range and the high measurement accuracy necessary for DAS make sub-pixel estimation indispensable. For the used Census metric, the so-called equiangular fit has proven to be superior to the classical polynomial fit. Unfortunately, the achievable precision is limited by its preference of integer disparities (see Shimizu and Okutomi (2001)). This “pixel-locking effect” can lead to deviations of up to 0.3 px in global stereo methods. Although solutions have been proposed, this problem has not yet been resolved. As sub-pixel accuracy is not demanded in current stereo benchmarks, only little attention is devoted to this problem by academia.

As previously mentioned in Section 2.1, precise depth estimation requires a careful camera calibration. In practice, an online calibration is indispensable. While the change of internal parameters may be neglected, the external parameters need to be estimated continuously. For example, in the area of horizontal structures, uncorrected pitch errors of 0.2 px only can result in completely wrong estimates. If the relative speed of two approaching vehicles is determined fromsubsequent disparity measurements, squint angle errors are critical, especially if the object distance is equivalent to only a few disparities. Driving at urban speeds, a calibration error of just 1 px is sufficient to observe trucks approaching with 130 km/h. Therefore, special care needs to be put on the online estimation of the squint angle. Best results are achieved when objects whose depth is known from other sensors, for example, leading vehicles tracked by an active sensor, are used for this task.

2.2.2.2 The Stixel World

In order to cope with the large amount of data (the FPGA delivers roughly 400,000 points in 3D at 25Hz) and reduce the computational burden of subsequent vision tasks (Badino et al. 2009) introduced the Stixel representation. Related to modern super-pixels, the so-called Stixel World is a versatile and extremely compact 3D medium-level representation. As shown in Figure 2.9, the complete 3D information is represented by only a few hundreds of small rectangular sticks of certain width, height, and position in the world. All areas of the image that are not covered with Stixels are implicitly understood as free, and thus, in intersection with the map of the route, as potentially drivable space.

The Stixel approximation exploits the fact that cities like all man-made environments are dominated by either horizontal or vertical planar surfaces. Horizontal surfaces typically correspond to the ground and exhibit a linearly decreasing disparity from the bottom of the image to the horizon. The vertical parts relate to objects, such as solid infrastructure, pedestrians, or cars and show (nearly) constant disparities. In the sense of a super-pixel, each Stixel approximates a certain part of an upright oriented object together with its distance and height.

Pfeiffer and Franke (2011) have presented a probabilistic approach to compute the Stixel World for a stereo image pair in a global optimization scheme. They treat the problem of Stixel extraction as a classical maximum a-posteriori (MAP) estimation problem, this way ensuring to obtain the best segmentation result for the current stereo disparity input.

Hence, it allows the support of the segmentation with a certain set of physically motivated world assumptions such as the following:

• Bayesian information criterion: The number of objects captured along every column is small. Dispensable cuts should be avoided.
• Gravity constraint: Flying objects are unlikely. The ground-adjacent object segment usually stands on the ground surface.
• Ordering constraint: The upper of two adjacent object segments has agreater depth. Reconstructing otherwise (e.g., for traffic lights, signs, or trees) is still possible if sufficiently supported by the input data.

Dynamic programming is used to infer the optimal solution in real time (see Bellman (1957)).

2.2.2.3 Stixel Tracking

In a static world, the Stixel representation is sufficient to compute a safe trajectory. In real traffic, moving objects have to be detected and their motion state must be determined.

A unique feature of images is that pixels with sufficient contrast can easily be tracked from frame to frame. If the camera is static, moving objects can be directly detected in the optical flow field. However, if the observer is also moving, things are more complicated, since the apparent flow depends on the observer's motion as well as on the depth of the considered pixel. In practice, neither the motion nor the depth is known exactly. Especially at larger distances when disparity uncertainties may not be ignored, a naive motion estimation will give unreliable and highly noisy results.

Much better results can be achieved by an optimal fusion of depth and optical flow measurements, as proposed in Franke et al. (2005). In their scheme, pixels are tracked over time and image positions as well as disparities are measured at each time step. Assuming a constant motion of the tracked features and a known motion of the observer, a Kalman filter uses the measured pixel positions and disparities together with the measurement covariances to simultaneously estimate -position and -motion for each tracked feature. Thus, the approach has become known as “6D-Vision”. Figure 2.10 shows on the left side the obtained result applying this algorithm to a sequence of a turning bicyclist. The arrows point to the expected positions ahead.

The motion of the observer comes as a by-product. As the complete motion is determined for thousands of points, it is straightforward to select good static features and use those for ego-motion calculation following the approach of Badino (2004).

This “6D-Vision” principle can also be applied to Stixels in order to precisely estimate their motion states. Given that objects of interest are expected to move earthbound, the estimated state vector can be reduced to , which represents the position and velocity of the Stixel. The dynamic Stixel results for the cyclist scenario are illustrated in Figure 2.10b. As a by-product of this simplification, the estimation puts fewer requirements on the ego-motion estimation. In practice, the vehicle's inertial sensors are sufficient to compensate for its own motion state. Thanks to the temporal integration, the motion vectors are highly parallel although the estimation is done independently.

2.2.2.4 Stixel Grouping

So far, Stixels are a compact representation of the local three-dimensional environment, but they do not provide any explicit knowledge about which Stixels belong together and which do not. This is achieved in the last step of the processing pipeline, when tracked Stixels are grouped into the motion classes “right headed,” “left headed,” “with us,” and “oncoming” as well as “static background.” The result of the scheme published in Erbs and Franke (2012) is illustrated in Figure 2.9 showing the motion segmentation result for the considered scenario. Further results are shown in Figure 2.11.

The authors approach this task as a MAP estimation problem as well. Given the dynamic Stixel World, the goal is to label each Stixel with one of the previously mentioned motion classes, depending on which class conforms best with the prior knowledge about the current local environment.

Apart from assuming rigid motion and striving for spatial smoothness of the segmentation, they use statistics obtained from annotated training data to express where in the scene which type of motion is likely to appear. For this purpose, Erbs and Franke (2012) model this problem using a conditional Markov random field, thus considering direct neighbor relationships (see Boykov et al. (1999)). The best labeling is extracted using the popular -expansion graph cut (see Kolmogorov and Rother (2007)). Since the image is represented by a few hundreds of Stixels only, the optimal solution can be computed in less than a millisecond on a single I7 core.

Each resulting cluster is represented by its geometric form and a weighted average motion vector. If the object has been classified as vehicle (see Chapter 3), a special tracker is applied that exploits the kinematic limitations of cars. The vehicle tracker proposed in Barth et al. (2009) implements a bicycle model and thus allows the observation of the complete motion state including the yaw rate of oncoming vehicles, which is important for intention recognition at intersections.

2.2.2.5 Discussion

The sketched vision architecture has been systematically optimized within the Bertha project and has proven its reliability in daily traffic. Each step from pixels via Stixels to objects is based on (semi-)global optimization in order to achieve both best performance and robustness. In particular, real-time SGM is used to compute dense stereo depth maps from rectified image pairs. The Stixel World is computed from stereo also in a semi-global optimal manner, just ignoring the lateral dependencies of Stixel columns in order to achieve a real-time implementation. The motion estimation is based on the 6D-Vision principle, taking into account the temporal history of the tracked Stixel. Finally, graph-cut-based optimization is used to find the optimum segmentation of the dynamic Stixel World.

Global optimization has become the key for high-performance vision algorithms as it forces us to clearly define what we expect from the “best” solution. If we are not happy with what we get from optimization, we have to reformulate our goal function.

Disparity estimation is a good example. SGM puts a small penalty on disparity changes of one pixel and a higher penalty on large chances. This regularization leads to a robust scheme, but one can do better. The currently best performing algorithms for road scenes (according to the KITTI benchmark) assume that the world is composed of small planes with constant surface normals and restricted border conditions (see Yamaguchi et al. (2014)). This regularization is much stronger and leads to significantly better results. Unfortunately, these algorithms are computationally expensive and not (yet) suited for real-time applications.

Alternatively, one can search for stronger data terms, which means that we incorporate more information in the optimization. For example, Sanberg et al. (2014) use color to improve the Stixel estimation. Attempts to improve the disparity estimation by color have not been proven useful when contrasted with the additional computation effort. On the contrary, using color information leads to worse results when color constancy is not perfectly fulfilled (see Bleyer and Chambon (2010)).

Another cue that has been successfully used is motion, as we expect the world to consist of a limited number of moving objects. Early Scene Flow estimation schemes that just enforce local smoothness of the 3D flow field deliver noisy results compared to 6D-Vision (as shown in Rabe et al. (2010)), while powerful approaches that simultaneously generate a super-pixel representation, where each patch has a constant surface normal and 3D motion vector, deliver excellent results but are out of reach for commercial applications (see Vogel et al. (2013)).

Nevertheless, the latter scheme clearly indicates the way we will go in future. The optimization takes into account spatial and temporal information and has a strongregularization. Furthermore, it performs disparity estimation and super-pixel computation jointly. As there is no interface between these two major building blocks any longer, there is no risk that relevant information is suppressed by the disparity estimation module that usually generates just one disparity estimate per pixel.

Future vision systems will also benefit from better imagers. In the past, the step from 8-bit images to 12-bit images with increased dynamics significantly improved the performance. Next, higher resolution will help to push the limits of stereo vision and allow detection of objects at larger distances, as it increases the depth sensitivity and the size of the observed objects at the same time. However, this does not come for free.

First, the computational load for disparity estimation increases. Secondly, and even more importantly, the sensor sensitivity decreases if the imager size is kept fixed for cost reasons. This results in more noise, stronger motion blur, and a reduced night performance. In addition, an improvement by a certain factor does not necessarily lead to an increase in the measurement range by the same factor. The reason is that one has to decide whether points with noisy depth are more likely to belong to the ground surface or an obstacle that stays on it. The commonly used planar world assumption does not hold at larger distances, and small errors in the tilt angle estimated from depth data in front of the car linearly increase with distance. Attempts to estimate the 3D height profile from depth data exist but suffer from the high depth noise at larger distances and the fact that glare and reflections make stable stereo ground correspondences increasingly difficult at large distances.

The above discussion reveals ways to improve the performance of the stereo analysis. The practical success will depend on their robustness with respect to adverse weather and illumination conditions as well as on their cost/performance relation. As long as FPGAs are the only way to get high computational power at low power dissipation, noniterative algorithms will be the preferred solution.

2.2.3.1 ROI Generation

Naturally, the more one knows about the current environment, the less effort must be spent on extracting the objects of interest.

For a monocular approach, there are no prior clues to exploit except a rough planar road assumption of the environment. Thus, one is forced to test lots of hypotheses spread across the image, covering all possible scales that the objects of interest might have. Approximately 50,000 hypotheses have to be tested per image to obtain reasonable results.

If depth data are available, it can be used to easily sort out unlikely hypotheses in advance, for example, by considering the correlation of depth and scale as suggested in Keller et al. (2011). This strategy allows reduction of the hypotheses set by an order of magnitude, such that about 5000 remaining hypotheses have to be classified (see Figure 2.12 for illustration).

Since Stixels inherently encode where in the scene, at which distance, and at which scale objects are to be expected, it is straightforward to directly use this prior knowledge for the hypotheses' generation step. Enzweiler et al. (2012) prove that it is possible to further reduce the number of required hypotheses by a whole magnitude, resulting in a total number of merely about 500. It also allows reduction in the number of false alarms by almost one order of magnitude, while the detection rate remains constant. The potential of this procedure has also been the focus of the work in Benenson et al. (2011).

2.2.3.2 Pedestrian Classification

Classification in the near range will be explained on the basis of pedestrian recognition. Each ROI from the previous system stage is classified by powerful multi-cue pedestrian classifiers. It is beneficial to use a Mixture-of-Experts scheme that operates on a diverse set of image features and modalities as inspired by Enzweiler and Gavrila (2011). In particular, they suggest to couple gradient-based features such as histograms of oriented gradients (HoG) (see Dalal and Triggs (2005)) with texture-based features such as local binary patterns (LBP) or local receptive fields (LRF) (see Wöhler and Anlauf (1999)). Furthermore, all features operate on both gray-level intensity and dense disparity images to fully exploit the orthogonal characteristics of both modalities, as shown in Figure 2.13. Classification is done using linear support vector machines. Multiple classifier responses at similar locations and scales are fused to a single detection by applying mean-shift-based nonmaximum suppression to the individual detections. For classifier training, the Daimler Multi-Cue Pedestrian Classification Benchmark has been made publicly available (see Enzweiler et al. (2010)).

The ROC curves shown in Figure 2.14 reveal that the additional depth cue leads to a reduction of the false-positive rate by a factor of five or an improvement of the detection rate up to 10%.

What is the best operating point? How many pedestrians can be recognized by the classifier? Interestingly, the answers to these questions depend on whether you want to realize a driver assistance system or an Autonomous Vehicle. For an autonomous emergency braking system, you might probably select an operating point far on the left of the ROC curve such that your system will nearly never show a false reaction but still has the potential of saving many lives. For an Autonomous Car, you must ensure that it will never hit a person that it could detect. So you have to accept much more false positives in order to reach the highest possible detection rate. Hopefully, the fusion module as well as the behavior control will be able to manage the problem of many false-positive detections.

The sketched system is highly efficient and powerful at the same time. However, the limited field of view of the used stereo system prohibits the recognition of pedestrians while turning at urban intersections. We used the wide-angled camera installed for traffic light recognition to check for pedestrians in those situations. Traffic light recognition was switched off and an unconstrained pedestrian search process was performed in those situations.

2.2.3.3 Vehicle Detection

For vision-based vehicle detection in the near range, a similar system concept as outlined earlier for pedestrian recognition including Stixel-based ROI generation can be used. However, the high relative velocities of approaching vehicles require a much larger operating range of the vehicle detection module than what is needed for pedestrian recognition. For Autonomous Driving in cities, it is desirable to detect and track oncoming vehicles at distances larger than 120m (equivalent to 4 seconds look ahead in city traffic) (see Figure 2.15). For highway applications, one aims at distances of 200m to complement active sensors over their entire measurement range.

Since one cannot apply stereo-based ROI generation for the long range, it has to be replaced by a fast monocular vehicle detector, that is, a Viola–Jones cascade detector (see Viola and Jones (2001b)). Since its main purpose is to create regions of interest for a subsequent strong classifier described earlier, one can easily tolerate the inferior detection performance of the Viola–Jones cascade framework compared to the state of the art and exploit its unrivaled speed.

Precise distance and velocity estimation of detected vehicles throughout the full distance range pose extreme demands on the accuracy of stereo matching as well as on camera calibration. In order to obtain optimal disparity estimates, one can perform an additional careful correlation analysis on the detected object. Pinggera et al. (2013) show that an EM-based multi-cue segmentation framework is able to give a sub-pixel accuracy of 0.1 px and allows precise tracking of vehicles 200m in front.

2.2.3.4 Traffic Light Recognition

Common Stereo Vision systems obey viewing angles within the range of –. However, stopping at a European traffic light requires a viewing angle of up to to see the relevant light signal right in front of the vehicle. At the same time, a comfortable reaction to red traffic lights on rural roads calls for a high image resolution. For example, in case of approaching a traffic light at 70km/h, the car should react at a distance of about 80m, which implies a first detection at about 100m distance. In this case, given a resolution of 20 px/, the illuminated part of the traffic light is about px, which is the absolute minimum for classification. For practical reasons, a 4 MP color imager and a lens with a horizontal viewing angle of approximately were chosen in the experiments presented here as a compromise between performance and computational burden.

Traffic light recognition involves three main tasks: detection, classification, and selection of the relevant light at complex intersections. If the 3D positions of the traffic lights are stored in the map, the region of interest can easily be determined in order to guide the search. Although color information delivered by the sensor helps in this step, it is not sufficient to solve the problem reliably.

The detected regions of interest are cropped and classified by means of a Neural Network classifier. Each classified traffic light is then tracked over time to improve the reliability of the interpretation (see Lindner et al. (2004) for details).

In practice, the classification task turns out to be more complex than one might expect. About of the 155 traffic lights along the route from Mannheim to Pforzheim turned out to be hard to recognize. Some examples are shown in Figure 2.16. Red lights in particular are very challenging due to their low brightness. One reason for this bad visibility is the strong directional characteristic of the lights. Lights above the road are well visible at larger distances while they become invisible when getting closer. Even the lights on the right side, which one should concentrate on when getting closer, can become nearly invisible in case of a direct stop at a red light. In these cases, traffic light change detection monitoring the switching between red and green is more efficient than classification.

2.2.3.5 Discussion

The recognition of geometrically well-behaved objects such as pedestrians or vehicles is a well-investigated topic (see Dollár et al. (2012), Gerónimo et al. (2010), and Sivaraman and Trivedi (2013)). Since most approaches rely on learning-based methods, system performance is largely dominated by two aspects: the training data set and the feature set used.

Regarding training data, an obvious conclusion is that performance scales with the amount of data available. Munder and Gavrila, for instance, have reported that classification errors are reduced by approximately a factor of two, whenever the training set size is doubled (see Munder and Gavrila (2006)). Similar beneficial effects arise from adding modalities other than gray-level imagery to the training set, for example, depth or motion information from dense stereo and dense optical flow (see Enzweiler and Gavrila (2011) and Walk et al. (2010)).

Given the same training data, the recognition quality significantly depends on the feature set used. For some years now, there has been a trend emerging that involves a steady shift from nonadaptive features such as Haar wavelets or HoGs toward learned features that are able to adapt to the data. This shift does not only result in better recognition performance in most cases, but it is also a necessity in order to be able to derive generic models that are not (hand-) tuned to a specific object class, but can represent multiple object classes with a single shared feature set. In this regard, deep convolutional neural networks (CNNs) represent one very promising line of research. The combination of such CNNs with huge data sets involving thousands of different object classes and lots of computational power has demonstrated outstanding multiclass recognition performance, for example, see Krizhevsky et al. (2012). Yet, much more research is necessary in order tofully understand all aspects of such complex neural network models and to realize their full potential.

A remaining problem with most object recognition approaches is that they are very restrictive from a geometric point of view. Objects are typically described using an axis-aligned bounding box of a constant aspect ratio. In sliding-window detectors, for example, the scene content is represented very concisely as a set of individually detected objects. However, the generalization to partial occlusion cases, object groups, or geometrically poorly-defined classes, such as road surfaces or buildings, is difficult. This generalization is an essential step to move from detecting objects in isolation toward gaining a self-contained understanding of the whole scene. Possible solutions to this problem usually involve a relaxation of geometric constraints and overall less object-centric representations, as will be outlined in the next section.