Probabilistic Models for
3D Urban Scene Understanding
from Movable Platforms
Dissertation
Dipl.-Inform. Andreas Geiger

Dissertation, Karlsruher Institut für Technologie
Fakultät für Maschinenbau
Hauptreferent: Prof. Dr. Christoph Stiller
Korreferent: Prof. Dr. Raquel Urtasun
Tag der mündlichen Prüfung: 19. April 2013

Impressum
Karlsruher Institut für Technologie (KIT)KIT Scientific Publishing
Straße am Forum 2
D-76131 Karlsruhe
KIT – Universität des Landes Baden-Württemberg und nationales
Forschungszentrum in der Helmholtz-Gemeinschaft
www.ksp.kit.edu

Diese Veröffentlichung ist im Internet unter folgender Creative Commons-Lizenz
publiziert: http://creativecommons.org/licenses/by-nc-nd/3.0/de/

KIT Scientific Publishing 2013
Print on Demand
ISSN: XXXX-XXXX
ISBN: 978-3-86644-XXX-X

Probabilistic Models for 3D Urban Scene
Understanding from Movable Platforms

Zur Erlangung des akademischen Grades
Doktor der Ingenieurwissenschaften
der Fakultät für Maschinenbau
des Karlsruher Instituts für Technologie (KIT)
genehmigte
Dissertation
von
D IPL .-I NFORM . A NDREAS G EIGER
aus Karlsruhe

Tag der mündlichen Prüfung: 19. April 2013
Hauptreferent:
Prof. Dr. Christoph Stiller
Korreferent:
Prof. Dr. Raquel Urtasun

Für meine Frau Anja undmeine Eltern Walburga und Günter

Vorwort
Die vorliegende Arbeit entstand während meiner Tätigkeit als wissenschaftlicher
Mitarbeiter am Institut für Mess- und Regelungstechnik am Karlsruher Institut fürTechnologie (KIT) unter Prof. Christoph Stiller.
Zunächst möchte ich mich herzlich bei Herrn Prof. Christoph Stiller für die Anregung zu dieser Arbeit, die wissenschaftliche Förderung und für die Übernahme desHauptreferates bedanken. In gleichem Maße gilt mein Dank meiner Korreferentin
Prof. Raquel Urtasun, welche mich seit meiner Diplomarbeit wissenschaftlich betreut, gefördert und zu neuen Ideen inspiriert hat. Gerne erinnere ich mich zurück
an unsere gemeinsame Zeit in Lausanne, Boston und Chicago. Prof. Marc Pollefeys
danke ich für die Möglichkeit drei Monate an der ETH Zürich zu forschen und neue
Einblicke in die Welt der 3D Rekonstruktionen zu gewinnen. Dr. Martin Lauer danke
ich für die Entführung in die Zauberwelt der Samplingverfahren. Zudem bedanke ich
mich bei allen Mitarbeitern des Institutes für Mess- und Regelungstechnik sowie bei
Alexander Schwing und Roland Angst für die wissenschaftlichen Diskussionen, dieentstandenen Freundschaften und die fröhlichen Momente bei Geburtstagen, Einstandsfeiern, Sommerseminaren, Sportveranstaltungen und Skiausflügen. Des Weiteren bedanke ich mich bei unserem Systemadministrator Werner Paal, der Werkstatt
und dem Sekretariat des MRT für die stets unbürokratische und freundliche Bearbeitung von Auf- und Anträgen. Den Herren Shaban und Käptn Peng gebührt mein
Dank für die musikalisch-philosophische Unterstützung und für den Kreis. Für die
finanzielle Unterstützung danke ich der Deutschen Forschungsgemeinschaft (DFG),
der Karlsruhe School of Optics and Photonics (KSOP) und dem Karlsruhe House of Young Scientists (KHYS), welche mir unabhängige Forschungsprojekte und
Auslandsaufenthalte ermöglicht haben.
Zum Schluss möchte ich mich bei meinen Eltern bedanken, die mich in jeder
Hinsicht förderten, mir ein sorgenfreies Studium ermöglicht haben und jederzeit fürmich da waren. Aus tiefstem Herzen danke ich meiner Frau Anja für ihre Geduld
während arbeitsintensiven Phasen ("Deadlines"), ihr Verständnis und die Motivation, ohne die diese Arbeit nicht möglich gewesen wäre.

Karlsruhe, 2013

Andreas Geigeriii

Zusammenfassung
Visuelles 3D Szenenverständnis stellt eine wichtige Komponente für automatisiertes Fahren und die Navigation von Robotern dar. Innerstädtische Kreuzungsszenarien sind hierbei in gleichem Maße interessant wie auch anspruchsvoll: Straßenkreuzungen können komplexe Geometrien annehmen und oft werden wichtige Hinweise
auf die Geometrie, wie zum Beispiel Fahrbahnmarkierungen oder andere Verkehrsteilnehmer, durch Objekte im Sichtfeld verdeckt. Während autonomes Fahren auf
Schnellstraßen (Dickmanns et al. [51]) sowie das Überqueren einfacher annotierter Kreuzungen (DARPA Urban Challenge [31]) bereits erfolgreich gezeigt wurde,
bleibt die Behandlung des allgemeinen innerstädtischen Falls mit geringem Vorwissen auch weiterhin ein ungelöstes Problem. Diese Arbeit stellt einen Beitrag zum
Verständnis von Verkehrsszenen basierend auf Videosequenzen dar. Ein auf dem
Dach des Versuchträger AnnieWay [106] angebrachtes Kamerasystem liefert die
dafür benötigten Sensorinformationen. Vorgestellt wird ein probabilistisches generatives Modell, welches die 3D Szenengeometrie sowie die Position und Orientierung von Objekten in der Szene schätzt. Insbesondere werden die Topologie, Geometrie sowie Aktivitäten der Verkehrsteilnehmer aus kurzen Videosequenzen bestimmt. Das Verfahren zieht dabei monokulare Informationen wie Objekte, Fluchtpunkte sowie eine semantische Bildsegmentierung als Merkmale heran. Zusätzlich
wird der Einfluss stereoskopischer Merkmale wie Szenenfluss und Belegungsgitter
untersucht. Motiviert durch die beeindruckende Fähigkeit des Menschen wird kein
weiteres Wissen wie beispielsweise GPS-, Lidar-, Radar- oder Karteninformationen
vorausgesetzt. Die auf 113 repräsentativ ausgewählten Sequenzen durchgeführten
Experimente zeigen dass der vorgestellte Ansatz für eine Vielzahl von Szenarien geeignet ist. Eine umfangreiche Auswertung und Analyse gibt Aufschluss über die Relevanz der einzelnen Merkmale. Des Weiteren wird aufgezeigt, wie durch das vorgeschlagene Verfahren eine verbesserte Objektdetektion und -orientierungsschätzung
erreicht werden kann.

v

Abstract
Visual 3D scene understanding is an important component in autonomous driving
and robot navigation. Intelligent vehicles for example often base their decisions
on observations obtained from video cameras as they are cheap and easy to employ.
Inner-city intersections represent an interesting but also very challenging scenario in
this context: The road layout may be very complex and observations are often noisy
or even missing due to heavy occlusions. While Highway navigation (e.g., Dickmanns et al. [51]) and autonomous driving on simple and annotated intersections(e.g., DARPA Urban Challenge [31]) have already been demonstrated successfully,
understanding and navigating general inner-city crossings with little prior knowledge remains an unsolved problem. This thesis is a contribution to understanding
multi-object traffic scenes from video sequences. All data is provided by a camera
system which is mounted on top of the autonomous driving platform AnnieWAY[106]. The proposed probabilistic generative model reasons jointly about the 3D
scene layout as well as the 3D location and orientation of objects in the scene. In
particular, the scene topology, geometry as well as traffic activities are inferred fromshort video sequences. The model takes advantage of monocular information in theform of vehicle tracklets, vanishing lines and semantic labels. Additionally, the benefit of stereo features such as 3D scene flow and occupancy grids is investigated.
Motivated by the impressive driving capabilities of humans, no further informationsuch as GPS, lidar, radar or map knowledge is required. Experiments conducted
on 113 representative intersection sequences show that the developed approach successfully infers the correct layout in a variety of difficult scenarios. To evaluate theimportance of each feature cue, experiments with different feature combinations are
conducted. Additionally, the proposed method is shown to improve object detection
and object orientation estimation performance.

vii

Contents

Notation and Symbols

1

1 Introduction
1.1 Problem Statement . . . . . . . . . . . . . . . . . . . . . . . . .
1.2 Applications . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
1.3 Contributions . . . . . . . . . . . . . . . . . . . . . . . . . . . .
1.4 Thesis Outline . . . . . . . . . . . . . . . . . . . . . . . . . . . .

5
5
6
7
8

2 Related Work
2.1 Autonomous Driving . . . . . . . . . . . . . . . . . . . . . . . .
2.1.1 The DARPA Urban Challenge . . . . . . . . . . . . . . .
2.1.2 The Google Driverless Car . . . . . . . . . . . . . . . . .
2.2 Environment Perception . . . . . . . . . . . . . . . . . . . . . . .
2.2.1 Lane Detection . . . . . . . . . . . . . . . . . . . . . . .
2.2.2 Road Detection . . . . . . . . . . . . . . . . . . . . . . .
2.2.3 Intersection Recognition . . . . . . . . . . . . . . . . . .
2.2.4 Semantic Image Segmentation . . . . . . . . . . . . . . .
2.2.5 3D Indoor Scene Understanding . . . . . . . . . . . . . .
2.2.6 3D Outdoor Scene Understanding . . . . . . . . . . . . .
2.2.7 Object Tracking and Activity Recognition . . . . . . . . .

11
11
11
12
12
12
14
15
16
16
17
17

3 Urban Scene Understanding
3.1 Geometric Model . . . . . . . . . . . . . . . . . . . . . . . . . .
3.2 Image Evidence . . . . . . . . . . . . . . . . . . . . . . . . . . .
3.3 Probabilistic Model . . . . . . . . . . . . . . . . . . . . . . . . .
3.3.1 Prior . . . . . . . . . . . . . . . . . . . . . . . . . . . .
3.3.2 Vehicle Tracklets . . . . . . . . . . . . . . . . . . . . . .
3.3.3 Vanishing Points . . . . . . . . . . . . . . . . . . . . . .
3.3.4 Semantic Scene Labels . . . . . . . . . . . . . . . . . . .
3.3.5 Scene Flow . . . . . . . . . . . . . . . . . . . . . . . . .
3.3.6 Occupancy Grid . . . . . . . . . . . . . . . . . . . . . .
3.4 Inference . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

19
19
22
23
23
25
27
28
29
29
30

viii

3.4.1 Inferring the Road Layout . . . . . . . . . . . . . . . . . .
3.4.2 Inferring the Location of Objects . . . . . . . . . . . . . .
Learning . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
3.5.1 Learning the Model Parameters . . . . . . . . . . . . . . .
3.5.2 Energy Potentials and Derivatives . . . . . . . . . . . . .

31
33
34
34
37

4 Image Evidence
4.1 Vehicle Tracklets . . . . . . . . . . . . . . . . . . . . . . . . . .
4.1.1 Detection . . . . . . . . . . . . . . . . . . . . . . . . . .
4.1.2 Tracking . . . . . . . . . . . . . . . . . . . . . . . . . .
4.1.3 Projection into 3D . . . . . . . . . . . . . . . . . . . . .
4.1.4 Temporal Integration . . . . . . . . . . . . . . . . . . . .
4.2 Vanishing Points . . . . . . . . . . . . . . . . . . . . . . . . . . .
4.3 Semantic Scene Labels . . . . . . . . . . . . . . . . . . . . . . .
4.4 Scene Flow . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
4.5 Occupancy Grid . . . . . . . . . . . . . . . . . . . . . . . . . . .

43
43
44
45
47
54
55
57
58
62

5 Experimental Evaluation
5.1 System Setup . . . . . . . . . . . . . . . . . . . . . . . . . . . .
5.2 Sensor Calibration . . . . . . . . . . . . . . . . . . . . . . . . . .
5.2.1 Synchronization . . . . . . . . . . . . . . . . . . . . . . .
5.2.2 Camera Calibration . . . . . . . . . . . . . . . . . . . . .
5.2.3 Velodyne and IMU Calibration . . . . . . . . . . . . . . .
5.3 Data Collection and Annotation . . . . . . . . . . . . . . . . . . .
5.4 Experimental Results . . . . . . . . . . . . . . . . . . . . . . . .
5.4.1 Learning the Model Parameters . . . . . . . . . . . . . . .
5.4.2 Expressive Power and Generality . . . . . . . . . . . . . .
5.4.3 Sampling from the Road Layout Prior . . . . . . . . . . .
5.4.4 Topology and Geometry . . . . . . . . . . . . . . . . . .
5.4.5 Tracklet Associations and Semantic Activities . . . . . . .
5.4.6 Object Orientation Estimation . . . . . . . . . . . . . . .
5.4.7 Object Detection . . . . . . . . . . . . . . . . . . . . . .
5.4.8 Runtime . . . . . . . . . . . . . . . . . . . . . . . . . . .
5.4.9 Qualitative Results . . . . . . . . . . . . . . . . . . . . .

65
65
66
67
67
68
70
71
72
72
77
77
82
82
83
85
86

6 Conclusions and Future Directions

91

A Sampling Techniques
A.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
A.2 Basic Sampling Strategies . . . . . . . . . . . . . . . . . . . . . .
A.2.1 Inverse Transform Sampling . . . . . . . . . . . . . . . .
A.2.2 Rejection Sampling . . . . . . . . . . . . . . . . . . . . .
A.3 Markov Chains . . . . . . . . . . . . . . . . . . . . . . . . . . .

93
93
94
94
95
98

3.5

A.3.1 Definition of Markov Chains . . . . . . . . . . . . . . . . 99
A.3.2 Properties of Markov Chains . . . . . . . . . . . . . . . . 102
A.3.3 Combining Kernels . . . . . . . . . . . . . . . . . . . . . 104
A.4 Markov Chain Monte Carlo . . . . . . . . . . . . . . . . . . . . . 107
A.4.1 Metropolis-Hastings Sampling . . . . . . . . . . . . . . . 107
A.4.2 Gibbs Sampling . . . . . . . . . . . . . . . . . . . . . . . 111
B Bibliography

115

Notation and Symbols
This chapter introduces the notation and symbols which are used in this thesis. In
cases where a symbol has more than one meaning, the context (or a specific statement) resolves the ambiguity.
General Notation
Scalars
Vectors
Matrices
Sets
Distributions
Numbers

Regular (greek) lower case
Bold (greek) lower case
Bold upper case
Calligraphic upper case
Calligraphic upper caseBlackboard/greek upper casea, b, c, σ, λa, b, c, σ, λA, B, C, Σ, Λ
A, B, C
U(·), N (·), Cat(·)
N, Z, R, ∆Indexing
i
j
ai
Ai,j
[a1 , a2 ]First-order index i ∈ {1, . . . , N }Second-order index j ∈ {1, . . . , M }i’th element of vector a(i, j)’th element of matrix A
Matrix A = [a1 , a2 ] is composed of columns a1 and a2

NumbersN
Z
R∆N

Natural numbers
Integer numbers
Real numbers
N-simplex

Geometry
R
κ
c
w
r
α
l

Intersection parameters R = {κ, c, w, r, α}Intersection topology κ ∈ {1, . . . , 7}Center of intersection c ∈ R2
Road width w ∈ R+
Road layout orientation r ∈ [− π4 , + π4 ]Crossing street angle α ∈ [− π4 , + π4 ]Lane index
1

s
K
L

Spline index
Number of intersection arms K ∈ {2, 3, 4}
Number of lanes/parking spots

Image Evidence
E
T
t
d
fd
md , Sd
od
V
v
S
s
F
f
O
ρ

Image evidence E = {T , V, S, F, O}
Tracklets T = {t1 , . . . , tNt }Tracklet t = {d1 , . . . , dMd }Detection d = (fd , md , Sd , od )Frame number of object detection fd ∈ N
Object location distribution N (md ∈ R2 , Sd ∈ R2×2 )Object orientation distribution od ∈ ∆7
Vanishing points V = {v1 , . . . , vNv }Vanishing point/line angle v ∈ [0, π)
Scene labels S = {s1 , . . . , sNs }Scene label s ∈ ∆2
Scene flow F = {f1 , . . . , fNf }Scene flow vector f = (pf , qf ), pf ∈ R2 , qf ∈ R2
Occupancy grid O = {o1 , . . . , oNo }Occupancy grid cell ρ ∈ {−1, 0, +1}

Projection(x, y, z)T(u, v)T
π(·)
K
P
R, r
T, t
I
D

World coordinates
Image coordinates
Projection onto the image plane
Camera calibration matrix K ∈ R3×3 (intrinsics)
Camera projection matrix P ∈ R3×4 (intrinsics, extrinsics)
Rotation matrix, rotation vector
Translation matrix, translation vector
Image
Disparity map

Probabilistic Model
Θ
E, R
p(·)
log p(·)
φ(·), ϕ(·)ψ(·), Ψ(·)
ζ, λ
σout
2

Model parameters
Training set (E = {E1 , .., ED }, R = {R1 , .., RD })Probability
Log-probability
Image likelihood helper functions
Potential functions
Image likelihood outlier and importance variables
Standard deviation of outlier distributionq(·)
pM H (·)U(·)
N (·)
Cat(·)µ, µ
σ2 , Σ
λ, Λh·ip(·)[·]

Metropolis-Hastings proposal distribution
Metropolis-Hastings acceptance probability
Uniform distribution (discrete or continuous)
Gaussian distribution
Categorical distribution
Mean
Variance, covariance matrix
Precision λ = σ −2 , precision matrix Λ = Σ−1
Expectation with respect to p(·)
Iverson bracket (1 if true, 0 otherwise)

Notation of Probability Distributions
This thesis follows the common notation of probability distributions and uses p(x) =D(x|θ) and x ∼ D(θ) interchangeably, where x is a random variable, D denotes
some probability distribution and θ are the parameters of the distribution.

31. Introduction
Recent progress in self-driving vehicles makes us believe that only a few decades
from now drivers can be replaced by autonomous systems that excel humans in termsof perception (e.g., omni-directional sensors), availability and the ability to respond.
Improved safety and time for work and leisure activities while traveling are the consequence. While vehicle control and trajectory planning algorithms have alreadybeen demonstrated successfully, robust environment perception is still a challenging
unsolved problem. This thesis presents a method to extend the vehicle’s field of viewto the challenging scenario of cluttered real-world intersections while relying solely
on close-to-production stereo image sensors.
1.1. Problem Statement
Given a short traffic video sequence of 5 to 30 seconds in length captured from a
movable platform we are interested in extracting information about the scene layout
and the dynamic objects, e.g., vehicles, present in the scene. In particular, we tackle
traffic scenarios with complex interactions. They pose an interesting problem andare challenging due to the heavy occlusions and the clutter present in these scenes.
Additional difficulties are caused by the low camera viewpoint leading to noisy depth
estimates and the limited camera field of view. In particular, the proposed method
tries to answer the following questions:• Where are the streets and the center of the intersection located?
• What is the width and the orientation of the streets?
• Where are the vehicles located and how are they oriented?
• Which car is driving? On which street?
• Which cars are parked at the side of the road?
• What is the current traffic situation?
• Does object detection benefit from the extracted road layout?
We try to answer the aforementioned questions from visual measurements alone,which are easy and cheap to acquire, never get outdated (as maps do) and mimic thehuman perception process. All sequences used for evaluation end when the observeris required to take a decision, i.e., when the traffic light turns green or the ego-vehicle5

1. Introduction

Figure 1.1.: Intersection from a Lane Detector’s Point of View. This figure shows a typicaltraffic scene with all non-road pixels masked. Note how difficult it is to correctly assess theintersection geometry using this information alone. To see the full picture, please turn over toFig. 1.2 on page 8.

enters the crossing. This requires predicting into the future and makes the task very
challenging. Much like for human drivers no additional information such as 3D point
clouds from a laser scanner, radar or maps is used.
While the problem of lane detection has been tackled intensely over the last
decades [4, 44, 51, 137, 173, 185], the detection and recognition of lane markings inisolation is not sufficient to infer the scene layout in complex situations. Consider for
example the scene illustrated in Fig. 1.1, where all non-road pixels of the image havebeen whitened. Even for a human being it is almost impossible to judge the situation
using lane markings as the only source of information. In contrast, Fig. 1.2 reveals
the full picture and shows that a variety of feature cues are important to understandthe scene in context [179]. Amongst them are: Other traffic participants, buildings,
vegetation, vanishing points and the sky region. Drawing from these observations,this thesis combines a variety of features in a probabilistic framework to tackle theproblem as illustrated in Fig. 1.3(b).
1.2. Applications
We highlight three important applications of traffic scene understanding.
While the total number of fatal traffic accidents has beenslightly decreasing over the last couple of years, in 2010 still more than 12, 000
fatalities have been reported in the US1 and more than 3, 500 cases have been registered in Germany2 . The ultimate goal of autonomous driving is to substitute thehuman driver with an intelligent system which is able to process the incoming sensor information and react appropriately in order to maneuver the vehicle from A
Autonomous Driving:

1
2

6

National Highway Traffic Safety Administration Facts Sheet 2010
Statistisches Jahrbuch 2011

1.3. Contributions

to B. However, autonomous driving has the potential to significantly reduce traffic accidents [138] and vehicle emissions [187] at the same time, for example byincreasing roadway capacity and reducing traffic jams [146]. As a side effect, passengers gain additional time which can be utilized for work or leisure activities. So
far, autonomous driving has been successfully demonstrated on highways with little
or no traffic. Busy inner-city navigation, however, is still an open challenge.
While autonomous driving at large scale
might still be decades away, many research findings have already made their way into
commercial driver assistance systems such as lane departure warning [127], automatic parking or collision avoidance [189]. Visual scene analysis at intersections can
add to these functionalities by warning the driver of overlooked traffic participants
or when entering the wrong lane. Furthermore, navigation systems will benefit fromthe extracted 3D information by enhancing their visual experience and simplifying
the interaction with the user.
Advanced Driver Assistance Systems:

Traffic scene understanding is of high importance forblind people as well, for example the situation must be assessed correctly before to
crossing the street [1]. Today’s assistance is typically provided by short-range whitecanes or guide dogs which both can only be employed for navigating known terrain[52]. Computer-based scene analysis in combination with visualization techniquessuch as acoustic auralization [182] has the potential to increase the range of perception, contribute to a higher quality of life and increase safety.

Visually Impaired People:

1.3. Contributions
The contributions of this thesis are as follows:• A novel intersection model is proposed which, in contrast to existing lane orroad detection methods, is flexible in the number of intersecting streets andthe location, orientation and width of the intersection arms.
• Compared to existing approaches, no static camera, bird’s eye view or information from maps is required.
• In contrast to previous approaches, the proposed model combines static features (e.g., building facades or vanishing points) with dynamic features (e.g.,traffic participants) for improved performance and robustness.
• Efficient learning and inference algorithms based on Markov Chain Monte
Carlo sampling and belief propagation are developed to infer the scene layout
and the location of objects within the scene.

7

1. Introduction

Figure 1.2.: Intersection from a Human’s Point of View. To interpret complex scenes as
the one from Fig. 1.1 on page 6, humans make use of a variety of different cues such as infrastructure (e.g., buildings or vegetation), vanishing points, objects and dynamic information.
The presented approach builds on this observation and integrates the different complementaryfeatures into a probabilistic model for analyzing traffic scenes.

• Extensive evaluations on 113 real-world sequences demonstrate the applicability of the method and confirm that context helps in scene estimation as well
as object recognition. The importance of each of the proposed feature cues
for the problem of 3D scene understanding is evaluated and discussed.
1.4. Thesis Outline
This thesis is structured as follows: Chapter 2 surveys the current state-of-the-art andcontrasts the proposed approach with respect to previous work. Chapter 3 presents
the proposed geometric and probabilistic intersection model and the parameter learning and model inference techniques that are employed. Chapter 4 gives details about
the image evidence and the computation of the features used by the model. Finally,
Chapter 5 describes the autonomous platform, the data collection process and theexperiments that have been carried out. Conclusions are drawn in Chapter 6. A
brief tutorial on the sampling techniques that we use for learning and inference isgiven in Appendix A.

8

1.4. Thesis Outline

Vehicle Tracklets

Vanishing Points

Scene Labels
Scene Flow

Occupancy Grid(a) Video-based Image Cues are the Input to the Proposed Model(b) Inference Result: Scene Layout and Objects(c) Experimental Platform AnnieWAY

Figure 1.3.: 3D Intersection Understanding. (a) Image cues. (b) Inferred scene layout andobjects, active lanes are shown in red. (c) Autonomous vehicle AnnieWAY which has beenused for capturing the evaluation sequences.

92. Related Work
This chapter discusses the state-of-the-art in autonomous driving systems and scene
understanding, and positions the contributions of this thesis with respect to the existing literature, summarized in Fig. 2.1. We start with an overview of the developmentof autonomous driving systems, survey their capabilities and current challenges.
2.1. Autonomous Driving
In 1939 General Motors invited the industrial designer Bel Geddes to submit a proposal for an exhibit at the New York’s World Fair ’Building The World of Tomorrow’. The exhibit, called ’Futurama’, envisioned a world 20 years into the futurefeaturing automated highways as a solution to traffic congestion of the day. Electriccars were powered by circuits embedded in the roadway and controlled by radio,much like modern production lines work today. In 1986, supported by the rapid
development of computers, a team of engineers around Ernst Dickmanns in collaboration with Daimler equipped a Mercedes-Benz van with cameras and successfully
demonstrated the first self-driving car on well-marked streets without traffic [51].
Subsequently, the European Commission began funding the EUREKA Prometheus
Project on autonomous vehicles (1987–1995). In 1995 the team demonstrated semiautonomous driving in real traffic from Munich in Germany to Odense in Denmarkat speeds up to 175 km/h, with human intervention for about 5% of the distance. At
the same time, the CMU Navlab project achieved 98.2% autonomous driving withmanual longitudinal control using the RALPH (Rapidly Adapting Lateral Position
Handler) computer program [152]. Similar efforts have been undertaken in 1996
and 2010 by the research group of Alberto Broggi [28], amongst others. In 2011, theGrand Cooperative Driving Challenge has benchmarked the state-of-the-art in autonomous platooning systems with Christoph Stiller’s Team AnnieWAY from KIT
taking the lead [68].
All aforementioned projects are targeted at tasks like highway driving, lanekeeping/-following or overtaking. In contrast, this thesis deals with the more challenging task of understanding traffic situations at intersection, which are much more
flexible in terms of topology, geometry and vehicle constellation.
2.1.1. The DARPA Urban Challenge
Motivated by the success of the Grand Challenges in 2004 and 2005 [30], the American Defense Advanced Research Projects Agency initiated the DARPA Urban Chal11

2. Related Worklenge [31, 106, 139, 100] in 2007 to benchmark the state-of-the-art in autonomous
inner-city driving on a 96 km test course at an abandoned Air Force Base. As for theprevious challenges and in contrast to the early approaches mentioned above, 100%
autonomous driving was required throughout the course.
While the Urban Challenge endeavor came closer to urban traffic situations, thestreets were wider than usual, the field of view was unobstructed and only a very
limited number of traffic participants were present. Furthermore, sub-meter precise
manually annotated maps were required and all teams made use of expensive 3D
laser scanner equipment for localization and collision avoidance. In contrast, theapproach presented in this thesis aims at analyzing complex and cluttered scenes in
the absence of maps or 3D point clouds.
2.1.2. The Google Driverless Car
Under the guidance of Sebastian Thrun, Google gathered a team of engineers,amongst them Chris Urmson (the current team lead), Mike Montemerlo and Anthony Levandowski who had experienced the DARPA Grand [30] and Urban [31]
Challenges, to equip a Toyota Prius with self-driving capabilities [188]. In August2012 Google announced that they have completed over 300,000 miles without accident.
Similarly to the participants of the DARPA Urban Challenge, the Google driverless car is equipped with a Velodyne 3D laser scanner for perception and requires
manually annotated maps at lane-level accuracy for path planning. Furthermore,
its precise localization system is based on registering depth and reflectance measurements with respect to a 3D map, which is recorded a-priori. In contrast, thisthesis targets scene understanding in the more general and challenging case where
no a-priori location-specific information is required.
2.2. Environment Perception
One major challenge for intelligent autonomous driving systems is the requirement
to perceive and interpret their environment. We focus on cheap and easy-to-employ
video-based perception and this section surveys the current state-of-the-art in thisfield. The spectrum of the referenced works ranges from very task-specific methods(e.g., lane detection) to more general scene understanding approaches (e.g., scene
segmentation and 3D interpretation).
2.2.1. Lane Detection
The pioneering works of Dickmanns et al. [51] made use of an extended Kalman
Filter [105] to recursively estimate lane parameters such as the steering angle, slip
angle, lateral offset from the road center, heading relative to the road tangent and12

2.2. Environment Perception

Futurama (Geddes, 1939)

Blocks World (Roberts, 1963)

VaMP Car (Dickmanns, 1994)

Intersection (Rasmussen, 2003)

Geom. Context (Hoiem, 2005)

Urban Challenge (Boss, 2007)

Lane Detection (Aly, 2008)

Segmentation (Ess, 2009)

Road Detect. (Alvarez, 2010)

VIAC Challenge (Broggi, 2010)

Activity Recogn. (Wang, 2009)

Driverless Car (Google, 2011)

Figure 2.1.: Related Work in autonomous driving/environment perception.
13

2. Related Workthe horizontal and vertical road curvature parameters. The road was represented using a clothoid (or Euler spiral) which is commonly employed in road planning andconstruction. As features, edge elements were extracted by correlating the image
with filter templates. Besides modeling the road shape with clothoids [51, 45, 176],
splines [4, 16, 45, 36] have been proposed to more accurately represent road segments that do not obey a clothoidal shape. Apart from edge features, other cues suchas color, lane width [8, 44] and adaptive binarization techniques [55, 27] have been
investigated. In order to remove the effect of distortions introduced by the perspective projection, the inverse perspective mapping has been proposed [27, 4, 66], constructing a virtual bird’s eye view of the road area ahead of the vehicle by means of
the homography between the road and the image plane. Due to the increase in computing power over the last decades, the extended Kalman filter has been replaced by
the more powerful particle filter [44, 173, 185] for tracking the road parameters overtime. In contrast to the extended Kalman filter no linearization is required and multimodal distributions can be represented more accurately, given a sufficient number ofparticles – or equivalently – computation time. To distinguish lane markings fromclutter such as cast shadows and damages in the road surface, robust methods havebeen developed [4, 8, 185]. Furthermore, the use of stereo information has beenreported to additionally boost performance [16, 45, 44, 111, 177, 186] as it enables
distinguishing edge information on the road from edges located on objects and infrastructure. While early stereo-based approaches applied the idea of Helmholtz shear[111] for computational reasons, recent progress in dense real-time stereo matching[113, 64, 93, 133, 73] allows to directly estimate the free space and segment roadfrom objects and infrastructure [10, 12, 11] in an online fashion. Paetzold et al.
[147] have cast lane recognition as an optimal control problem where the vehicle
trajectory is directly optimized to avoid obstacles and maximize comfort at the sametime. The use of maps has been investigated bei Heimes, Huang et al. [90, 100].
They map line segments into the image using GPS as initialization to improve localization accuracy [90]. Furthermore, map information in combination with a precise
GPS system have been key to successful navigation during the DARPA Urban Challenge [100]. For a more complete survey on recent developments in lane detection,
the reader is referred to [107, 137].
While all of the methods mentioned above focus on the detection of one to threeadjacent lanes, this thesis is concerned with the intersection scenario and handles
lane detection as a subset of intersection understanding.
2.2.2. Road Detection
While lane detection approaches try to fit parametric models to the lane boundaries,
methods for road detection are non-parametric in the sense that they directly produce
a segmentation of the image into road and non-road pixels. This is useful in cases ofless structured roads, for example when driving on dirt roads as required during the14

2.2. Environment Perception

DARPA Grand Challenge [30]. Early approaches directly classify each pixel using
the gray value structure tensor as feature [199]. To increase robustness, different
cues such as color, vanishing points and the 3D scene layout have been proposed
and integrated over time [3]. Online learning approaches [2, 42] inspect a small road
patch in front of the vehicle, e.g., identified by lidar [42], to learn a statistical modelof the road ahead and classify image regions further away. According to Dahlkamp
et al. [42], such a mechanism turned out to be key for increasing the range of visionin order to drive fast enough to win the 2005 DARPA Grand Challenge.
All state-of-the-art road detection methods focus on recognizing a single road andwork well in unstructured terrain where texture and color are discriminative enoughto distinguish road from vegetation or background. As will be shown in this thesis,
texture based classification alone, which is one of the features in our framework,
is insufficient for extracting higher-level information about intersections such as the
topology or geometry.
2.2.3. Intersection Recognition
Back in the early 1990’s the problem of intersection understanding has been recognized as a difficult one [41, 56, 77]. In the case of unstructured terrain, patternrecognition techniques have been employed to partition the image into road and nonroad pixels and classify the shape of the road using template matching [41] or classification [154, 58]. To increase the field of view, active camera vision systems havebeen proposed [104, 136]. For well marked roads, Enkelmann et al. [56] aim at recovering gaps between road markings as indications of intersections. Gengenbach[77], Heimes [89, 90] and Mueck [140] project intersection models, which have been
manually annotated or obtained from maps [29] in a semi-supervised fashion, into
the image in order to localize the vehicle when the approximate location is known
up to a couple of meters. Richer prior knowledge has been incorporated into thesemethods using description logic. In [102, 103], for example, a description logic basefor arbitrary road and intersection geometries has been developed. Based on map information, logically stated geometric constraints and road building regulations are
employed in a deductive inference scheme to answer questions like ’is this lane aright turn lane?’ or ’which lane is the vehicle on?’.
All existing methods deal with very simple scenarios, neglecting clutter and occlusions, or require an immense amount of labor intense prior knowledge. This
prevents them from being employed to real-world urban traffic situations. We argue
that road and lane features by themselves are insufficient to robustly infer the roadlayout. Instead a more diverse set of feature cues such as the scene flow fields induced by other participants [67], infrastructure elements [69], vanishing points andscene labels [74] need to be considered in order to accomplish the task.

15

2. Related Work2.2.4. Semantic Image Segmentation
While the approaches described so far are largely rooted in the domain of robotics
and intelligent vehicles, the perceptual side of scene understanding has received a
lot of attention in the computer vision and machine learning communities as well.
In the following, we introduce the most important developments in these fields andrelate the material presented in this thesis with respect to them.
The goal of semantic image segmentation [118, 117, 58, 174, 9, 203, 54, 21, 63,
81, 83, 83, 120, 170, 170, 181, 191] is to partition the input image into disjoint
regions and assign a unique class label (e.g., car, building, vegetation or sky) toeach of them. Contextual information is typically integrated by means of a Markov
random field model.
While these models reason directly at the pixel-level, they provide useful cues
which are exploited as features in the proposed approach. We aim to infer the full 3D
layout of traffic intersections from a monocular view including the accurate positionof buildings, the street and all vehicles.
2.2.5. 3D Indoor Scene Understanding
Several decades after Roberts first attempts [155] in 1963, the problem of 3D scene
understanding has witnessed novel interest thanks to the developments in object detection, semantic segmentation and image classification, amongst others. A wide
variety of approaches have been proposed to recover the 3D layout of indoor scenes
in the form of 3D cuboids from a single image [126, 87, 183, 125, 168]. These methods mainly build on edges and image segments as features, and most of them relyon the Manhattan world assumption [114, 157], i.e., edges in the image can be associated with vanishing points which are orthogonal to each other. With a moderate
degree of clutter, accurate geometry estimation has been shown for this scenario. To
improve performance, several methods have tried to explicitly model the room clutter using 3D occupancy grids [87] or cuboids [88, 149, 125, 195]. Recently, depth
information from the Kinect sensor has been explored towards the goal of estimating support relationships between objects [171]. Context from observing people andtheir interaction with the environment has been investigated by Breitenstein, Delaitre
et al. [25, 49] and a vertical structure prior has been proposed by Zeisl et al. [198].
Unfortunately, these approaches can only cope with limited amounts of clutter(e.g., beds), and rely on the fact that indoor scenes closely satisfy the Manhattan
world assumption, i.e., walls (and objects) are aligned with the three dominant vanishing points. In contrast, outdoor scenes as considered in this thesis are often more
cluttered, 3D lines are not necessarily orthogonal [166, 15], and objects might notalways agree with the dominant orientations.

16

2.2. Environment Perception

2.2.6. 3D Outdoor Scene Understanding
Apart from the efforts towards geometric multi-view reconstruction [128, 40, 151]
for urban scenes, a large body of work has focused on estimating 3D popups fromsingle images captured outdoors [96, 94, 97, 98, 163, 161, 162, 164, 91, 142]. Often a Manhattan world [15, 114, 157] is assumed to infer vanishing points fromline segments. Reminiscent to the Blocksworld model, physical constraints between
objects such as ’object A supports object B’ are imposed in [84]. Large datasets
such as LabelMe [160] allow for similarity-based scene understanding [159], where
ground truth labels are transferred from the most similar scenes in the database.
Several methods have tried to infer the 3D locations of objects in outdoor scenarios [95, 14, 50]. In order to estimate 3D object locations, tree-structured models have been proposed [95, 14] which also reason about the camera tilt. Murphy et al. [141] exploit object co-occurrence statistics to improve object detection,
while Sudderth at al. [175] make use of hierarchical Dirichlet processes to modelvisual scenes. The most successful approaches use tracklets to prune spurious detections by linking consistent evidence in successive frames [108, 101, 65]. However,these models are either designed for static camera setups in surveillance applications[101] or do not provide a rich scene description [108, 65]. Notable exceptions are[37, 57, 190, 192, 193], which jointly infer the camera pose with respect to a single ground plane and the location of objects in the scene. Unfortunately, most urban
scenes violate the Manhattan world assumption and several approaches have focusedon estimating vanishing points in this more adversarial setting [166]. For example,
Barinova et al. [15] proposed to jointly perform line detection as well as vanishingpoint, azimuth and zenith estimation.
Unfortunately, most of the existing 3D scene layout estimation techniques aremainly qualitative, do not model object dynamics, suffer from clutter and lack thelevel of accuracy necessary for real-world applications such as autonomous driving
or robot navigation. Existing methods that take objects into account usually model
the scene in terms of a simple ground plane and thus are not able to draw conclusions
from the complex interplay of the objects with the larger scene layout. In contrast,
we propose a method that is able to extract accurate geometric information by reasoning jointly about static and dynamic elements as well as their interplay. Towards
this goal we develop a rich image likelihood model that takes advantage of vehicle
tracklets, vanishing points, segmentations, scene flow and occupancy grids.
2.2.7. Object Tracking and Activity Recognition
For a long time dynamic objects have been considered either in isolation [153, 65,
20, 6, 7, 13, 43, 112, 131] or jointly using simple motion models [101, 24, 32, 57,
109, 129, 130, 167, 172, 194, 200, 197, 202]. Only very recently, social interaction between individuals has been taken into account [196, 38, 37, 124]. Choi et al.
[38] introduce a hierarchy of activities, modeling the behavior of groups and Pelle17

2. Related Workgrini et al. [148] explicitly account for collisions. Methods for unsupervised activity
recognition and abnormality detection [115, 184] are able to recover spatio-temporaldependencies from a static camera mounted on top of a building.
While promising results have been shown, the interplay of objects with their environment is neglected and the focus is put on surveillance scenarios with a fixedcamera viewpoint, limiting applicability. In contrast, the method developed in thisthesis infers semantics at a higher level such as multi-object traffic patterns at intersections, in order to improve the layout and object estimation processes. Importantly,
we do inference over intersections that we have never seen before and our viewpoint
is substantially lower compared to the surveillance scenario, which renders the problem very challenging.

18

3. Urban Scene Understanding
This thesis tackles the problem of estimating complex 3D traffic scenes (e.g., intersections) from video sequences. The sequences have been captured from a moving
vehicle as illustrated in Fig. 1.3(c). Here, 2D refers to observations in the image planeand 3D refers to coordinates in bird’s eye perspective. We assume a flat road surface
and model the scene layout and all objects in the road coordinate system. The roadcoordinate system is located directly below the left camera in the last frame using thesame yaw angle and coordinate axis definition (x = right, y = down, z = forward).
All points on the road satisfy y = 0. An illustration of the road coordinate systemwith respect to the camera is given in Fig. 3.1(b) and Fig. 4.3.
3.1. Geometric Model
The proposed model is based on our observation of typical traffic scenes: We assume that the global layout of the scene is dominated by two, three or four roads
intersecting at a single point, the center of the intersection. All vehicles are either
parked at designated parking areas at the side of the road or they drive on lanes andadhere to some basic traffic rules such as right-hand driving. Lanes are modeledusing B-splines and connect every inbound street with every outbound street. Road
boundaries determine the border between drivable regions and areas that are likely
to contain buildings and infrastructure. We model seven different scene topologies
and use the following parameters to describe the intersection:• Topology. The discrete topology variable κ distinguishes between the scene
topologies ’straight’, ’turn’, ’T-intersection’ and ’X-intersection’ as illustrated
in Fig. 3.1(a). κ ∈ {1, . . . , 7}.
• Center of intersection. The intersection center c defines the point where allroads join and is specified in terms of the road coordinate system, depicted inFig. 3.1(b). c = (x, z)T ∈ R2 .
• Street width. As our depth measurements are very noisy and the size of the
opposing streets are often not observable, we assume that all streets sharethe same width w. The consequences of this assumption are analyzed in our
experimental evaluation. w ∈ R+ .
• Rotation. The rotation r accounts for the observer’s yaw orientation withrespect to the incoming street. r ∈ [− π4 , + π4 ].
19

3. Urban Scene Understanding

1

2

3

4

5

6

7

(a) Topology Model κ ∈ {1, . . . , 7}(b) Geometry Model (for κ = 4)

Figure 3.1.: Road Topology and Geometry. (a) shows the 7 different topologies κ we consider: Straights (1), turns (2,3), T-intersections (4-6) and X-intersections (7). The gray shaded
areas illustrate the flexibility of the crossing street. (b) shows the geometric parameters of themodel for κ = 4. All modeling is done in bird’s eye perspective (road plane coordinates).

• Crossing angle. The crossing angle α refers to the relative orientation of thecrossing street. Alternate intersection arms are forced to be collinear, which
is a reasonable assumption. α ∈ [− π4 , + π4 ].
All variables are illustrated in Fig. 3.1. In the following they will be subsumed using
the road layout variable R = {κ, c, w, r, α}.
An important contribution of the proposed model is to account for
the interplay of dynamic objects (i.e., vehicles) with their environment (e.g., streetsor buildings). This is realized by assuming that, given the road layout, all traffic
participants can be explained as either driving on designated lanes, which we modelwith the help of B-splines, or being parked at a parking area at the side of the road.
For simplicity, we restrict our focus to two lanes per street, one incoming and one
outgoing lane for each intersection arm. Streets with multiple lanes can be represented in our model by means of a larger street width w. As vehicles are allowed
to cross the intersection in any possible direction, we have K(K − 1) lanes for a
K-armed intersection. For each street we model two parking areas at the side of
the road, one at the left side and one at the right side, yielding 2K parking areas intotal. Two (out of six) lanes of a 3-armed intersection as well as one parking area
are illustrated in Fig. 3.2(a).
Lane centerlines are modeled using quadratic B-splines [48] governed by five control points {q1 , . . . , q5 } which are located at the center of the lane as illustrated in
Lane Model:

203.1. Geometric Model

2
1.5
1
0.5
0
−0.5
−1
−1.5
−2
0

(a) Lanes and Parking Lots(b) B-Spline Control Points

12(c) B-Splines

Figure 3.2.: Lane Model. This figure illustrates the location of the lane centerlines with respect
to the road layout using B-splines. (a) shows 2 out of 6 lanes and 1 out of 6 parking areas fora 3-armed intersection. All lanes and parking areas are discretized at 1m intervals to facilitate
inference. The placement of the 5 control points that define a lane spline is depicted in (b). A
set of quadratic B-splines with knot vector t is illustrated in Fig. 3.2(c).

Fig. 3.2(b), with q3 the intersection center. Using de Boor’s recursion formula [48],a spline can be recursively expressed ass(t) =

5
X

bi,2 (t)qii=1

t − titi+j+1 − tbi,j−1 (t) +bi+1,j−1 (t)ti+j − titi+j+1 − ti+1
bi,0 (t) = [ti ≤ t < ti+1 ]bi,j (t) =(3.1)

where t ∈ [0..1] is the curve parameter, ti is the i’th entry of the knot vector t,b(t) are the basis B-splines, qi ∈ R2 is the i’th control point as illustrated in Fig.
3.2(b), and [·] denotes the Iverson bracket. The knot vector, controlling the shape of
the B-spline through Eq. 3.1, is chosen as t = (0 0 0 0.1 0.9 1 1 1)T which forces
the spline to interpolate all but the central control point. Empirically this resulted
in realistic curvatures as illustrated in Fig. 3.2(c). We refer the reader to [48] fordetails.
Given all lane splines and all parking areas, we equidistantly define discrete vehicle locations (s) at 1m intervals as illustrated in Fig. 3.2(a). This makes inferencevery efficient as dynamic programming algorithms can be employed for calculating
marginals and MAP estimates. At inference, the vehicle locations are obtained byassigning all detected objects to one of these locations. Note that this assignment
links the object detections with the static elements in the scene (e.g., road, buildings,
vanishing points).

21

3. Urban Scene Understanding

3.2. Image Evidence
Besides the geometric model, which is entirely determined by the road parameters
R = {κ, c, w, r, α}, we define a probabilistic model to explain the evidence E in
the image. The observations are collected from a set of monocular and stereo featurecues which we introduce in the following.
First, we detect objects and track them over time, yielding vehicle tracklets, which
we denote by T . They provide us with information about where the lanes and theparking areas might be located, which are central in our geometric model describedin Section 3.1. Furthermore, vanishing points V give useful hints about the directionof the streets since many scene elements such as road markings or building facades
are often aligned with the principal axes of the scene. Segmenting the image into semantic categories S such as road, background or sky, provides valuable information
about the extend of the roads and urban canyons.
In addition to the monocular feature cues described so far, we also leverage lowlevel stereo features. For instance, 3D scene flow F is extracted as a cue for moving
objects in the scene and an occupancy grid O provides complementary hints at thelocation of buildings and infrastructure alongside the road.
We summarize all feature cues as image evidence E = {T , V, S, F, O}, which
we will define in the following. For details on the feature extraction pipeline, we
refer the reader to Chapter 4.
Vehicle Tracklets: Let T denote the set of vehicle tracklets T = {t1 , . . . , tNt }that have been detected in the sequence. A vehicle tracklet t is defined as a sequenceof object detections projected into bird’s eye perspective t = {d1 , . . . , dMd } withd = (fd , md , Sd , od ). Here, fd ∈ N is the frame number and md ∈ R2 , Sd ∈R2×2 are the mean and covariance of the Gaussian distribution N (m, S) describing
the object location in road coordinates. od ∈ ∆7 are the parameters of a categorical
distribution over eight possible viewpoints (estimated by the object detector) withthe unit N -simplex ∆N defined by
(
)
N
+1
X
N
N +1
∆ = x∈R
xi = 1 ∧ ∀ i : xi ≥ 0
(3.2)
i=1

Furthermore, we detect up to two (Nv ∈ {0, 1, 2}) dominantvanishing points V = {v1 , . . . , vNv } and represent them by a single rotation angle around the yaw axis of the road coordinate system vi ∈ [0, π). The verticalvanishing point is non-informative for our task and not considered here.

Vanishing Points:

We define the set of semantic labels S = {s1 , . . . , sNs }by subdividing the image into Ns patches (or ’superpixels’) of size ns × ns pixels.

Semantic Scene Labels:

22

3.3. Probabilistic Model

For each patch, si ∈ ∆2 denotes the discrete probability distribution over the semantic categories road, background and sky. This feature is computed for the last
frame in each sequence as this gives us the best possible view at the scene.
The scene flow F = {f1 , . . . , fNf } features capture the 3D motion in the scene, compensated for the observer’s egomotion. Each flow vector
f = (pf , qf ) is defined by its location pf ∈ R2 and velocity qf ∈ R2 on theroad plane. All velocity vectors are normalized to kqf k2 = 1 as our scene flow
model does not explicitly reason about vehicle velocities.
Scene Flow:

The occupancy grid O = {ρ1 , . . . , ρNo } is represented by No
cells of size no × no meters. Each cell ρi ∈ {−1, 0, +1} can be either free (−1),
occupied (+1) or unobserved (0).

Occupancy Grid:

3.3. Probabilistic Model
By assuming all observations E = {T , V, S, F, O} to be conditionally independent
given the road layout R, the joint distribution over the image evidence E and the roadparameters R factorizes as#"NtYp(E, R|Θ) = p(R|Θ)
p(ti |R, Θ)
i=1| {z } |
Prior

×

Nv
Y

{z

Vehicle Tracklets
NsYp(vi |R, Θ)

i=1

|
×

{z

} |

p(fi |R, Θ){zScene Labels

No
Y

}

p(ρi |R, Θ)

(3.3)

i=1

i=1

|

p(si |R, Θ)

i=1

Vanishing Points

Nf
Y

}

{z

Scene Flow

} |

{z

Occupancy Grid}

where Θ denotes the set of all parameters in our model. This is also illustrated in
the graphical model shown in Fig. 3.3.
3.3.1. Prior
The prior on road parameters R factorizes asp(R|Θ) = p(κ|Θ)p(c, r, w|κ, Θ)p(α|κ, Θ)

(3.4)

23

3. Urban Scene Understanding

Figure 3.3.: Directed Graphical Model. This figure shows the factorization of the joint probability distribution in Eq. 3.3 using a directed graph. Random variables are depicted with circles, observed variables are filled and dependencies between random variables are highlighted
using directed arrows. The plate notation is adopted to denote copies.

withκ ∼ Cat(ξp )−1(c, r, log w)T |κ ∼ N µp(κ) , Λ(κ)
pα|κ ∼ fκ (α, σα )

λp

(3.5)
(3.6)
(3.7)

where Cat(·) denotes the categorical distributionp(κ|Θ) = Cat(κ|ξp ) = ξp,κ

with

7
X

ξp,i = 1

(3.8)

i=1

and c, r and w are modeled jointly to capture correlations between the variables. w
is modeled using a log-Normal distribution due to its positivity constraint. Empirically we found α to be highly multi-modal and model it using kernel density estimation fκ (α, σα ) with kernel bandwidth σα . All parameters ξp , µp , Λp , λp ∈ Θare learned from training data using real-world intersections labeled in GoogleMaps
aerial imagery as described in Section 5.3. Note that the symmetric positive definite
precision matrix Λp has to be parameterized appropriately. For details on the parameterization and the learning procedure the reader is referred to Section 3.5. The
likelihood terms in Eq. 3.3 are described in the following.

24

3.3. Probabilistic Model

3.3.2. Vehicle Tracklets
Recall that a vehicle tracklet t is defined as a sequence of object detections projected into bird’s eye perspective t = {d1 , . . . , dMd } with object detections d =(fd , md , Sd , od ), where fd ∈ N is the frame number, md ∈ R2 , Sd ∈ R2×2 describe the object location in road coordinates and od ∈ ∆7 is the discrete object
orientation distribution. Let l be an additional latent variable representing either
the lane or the parking area where tracklet t has been observed as illustrated in Fig.
3.2(a). Assuming a uniform prior on all K(K − 1) lanes and all 2K parking areasl ∼ U ({1, . . . , K(K − 1) + 2K})

(3.9)

the tracklet likelihood is defined as the marginal distributionLX

p(t, l|R)(3.10)

p(t, l|R) = p(l|R)p(t|l, R) ∝ p(t|l, R)(3.11)

p(t|R, Θ) =l=1

where the tracklet index i and the dependency on the parameters Θ have been
dropped for clarity of notation. In order to keep inference tractable, we marginalize
over l when estimating the road model parameters R. When estimating the locationof individual objects in the scene, the posterior over l becomes important and is explicitly computed. The tracklet distribution conditioned on the lane and road layout
is given bypl (t|l, R) if l ≤ K(K − 1)(lane)
p(t|l, R) =(3.12)
pp (t|l, R) if K(K − 1) < l ≤ 2K (parking)where pl (t|l, R) and pp (t|l, R) denote the likelihood terms for the lanes and parking areas, respectively.
In order to evaluate the tracklet posterior for lanes pl (t|l, R), all object detectionst = {d1 , . . . , dMd } must be associated to locations on the spline of lane l. As thissubroutine is called very often during inference (i.e., once per sample and observed
tracklet) and for maintaining efficiency, we discretize the lane spline at 1m intervals
and augment the observation model with an additional discrete latent variable s per
object detection d which indexes the location on the lane as illustrated in Fig. 3.2(a).
Note that a 1m discretization interval is sufficient as for most viewpoints the observation noise will be larger than 1m. As dynamical model we employ a left-to-right25

3. Urban Scene Understanding

Hidden Markov Model. Marginalizing over all hidden states {s1 , . . . , sMd } yields
X
pl (t|l, R) =pl (t, s1 , . . . , sMd |l, R)
s1 ,...,sM

d

X

=

s1 ,...,sM

×

Md
Y

p(s1 )pl (d1 |s1 , l, R)dp(sj |sj−1 )pl (dj |sj , l, R)(3.13)

j=2

where Md denotes the number of object detections in the tracklet and tracklets are allowed to start anywhere on the lane with equal probability, i.e., s1 ∼ U ({1, . . . , Ml }),with Ml the number of spline points on lane l. Our motion model is simple, yet effective: By constraining all tracklets to move forward with uniform probability1
if sj ≥ sj−1
Ml −sj−1 +1p(sj |sj−1 ) =(3.14)
0otherwise
the model is able to distinguish the lane of a crossing street purely based on thevehicle’s motion. This is of importance as distance measurements of far objects arenoisy to an extend which is preventing the distinction from the object location alone.
The emission probability for lanes pl (d|s, l, R) is factorized into the probability
over object location md , Sd and object orientation odpl (d|s, l, R) = p(md |s, l, R, Sd ) p(od |s, l, R)(3.15)For clarity of notation the detection index j has been dropped. The 3D object location in Eq. 3.15 is modeled as a Gaussian mixturep(md |s, l, R, Sd ) = (1 − ζt ) pin (md |s, l, R, Sd )+ ζt pout (md |s, l, R)(3.16)

with inlier and outlier distributions defined by1pin (md |s, l, R, Sd ) ∝ exp − (φt − md )T S−1
d (φt − md )2

1
(3.17)
pout (md |s, l, R) ∝ exp − 2 mTd md ,2σout
respectively. Here, φt (s, l, R) ∈ R2 denotes the 2D location of spline point s
on lane l according to the B-spline model presented in Section 3.1, ζt ∈ Θ is theoutlier probability and σout ∈ Θ is a parameter controlling the ’spread’ of the outlier
distribution.

26

3.3. Probabilistic Model

For the object orientation likelihood, we impose a categorical distribution over
object orientations odp(od |s, l, R) = Cat(ϕt (s, l, R)|od ) = od,ϕt (s,l,R)(3.18)

where ϕt (s, l, R) ∈ {1, . . . , 8} selects the orientation bin that represents the relative direction the object would be viewed by the observer when it was driving into
the direction of the lane. Intuitively, Eq. 3.18 encourages lane associations such thatthe estimated vehicle orientation and the direction of the lane coincide. The relative
viewing direction is computed from the tangent of lane l at spline point s.
For parking areas, all cars are assumed to be static. Thus, no dynamics needs to
be incorporated into the observation model and the tracklet’s parking area likelihood
reduces toX
pp (t|l, R) =pp (t, s|l, R)
s

=

Md
XY
s

p(s) pp (dj |s, l, R)(3.19)

j=1

assuming a uniform prior p(s) on the location s within parking area l. Furthermore,
for parked cars we do not make any assumption about the orientation. Thus, theemission probability becomespp (d|s, l, R) =1
p(md |s, l, R, Sd )8

(3.20)

with p(md |s, l, R, Sd ) as in Eq. 3.16.
3.3.3. Vanishing Points
Assuming all Nv ∈ {0, 1, 2} vanishing points V = {v1 , . . . , vNv }, represented bytheir orientations on the ground plane vi ∈ [0, π), to be independent given the roadlayout R, we definep(v|R, Θ) ∝ ζv + (1 − ζv ) exp (−λv φv (v, R, Θ))(3.21)

with orientation error
φv (v, R, Θ) = 1 − cos(2v − 2ϕv (R))

(3.22)

where ζv ∈ Θ is a small constant capturing outlier detections. The last term in
Eq. 3.21 correspond to the cyclic von Mises distribution [22] up to a normalizing
factor that depends on the zeroth-order Bessel function of the first kind. ϕv (R) is
the orientation of the closest street, based on the current road model configuration
R, and λv ∈ Θ is a precision parameter and controls the importance of this term.
27

3. Urban Scene Understanding

Figure 3.4.: Illustration of Scene Label Likelihood. This figure shows the semantic segmentation returned by a joint boosting classifier (top) and the ’virtual’ image segmentation
corresponding to the current road layout configuration R (bottom). The semantic scene label
likelihood in Eq. 3.23 encourages a large overlap between the virtual segmentation and theclassification result.

As lines belonging to a vanishing point are undirected, i.e., v ∈ [0, π) instead ofv ∈ [0, 2π), a factor of 2 is added in Eq. 3.22 to accommodate this fact.
3.3.4. Semantic Scene Labels
Let s ∈ S represent the (discrete) distribution over the three different semantic
classes ’road’, ’background’ and ’sky’ for a particular image patch. The semanticlabel likelihood for that patch is modeled as
λsp(s|R, Θ) ∝ exp
ws,φs (R) sφs (R)(3.23)
Ns
where λs ∈ Θ is a parameter controlling the importance of the semantic label cue,φs (R) ∈ {1, 2, 3} picks the class label corresponding to the same pixel in a ’virtual’segmentation of the scene according to the current road model configuration R andws ∈ R3 is a weight vector. We assume that the background (i.e., buildings, trees)
starts directly behind the curb of the road and buildings reach a height of four stories on average, thereby defining the background area which separates the sky fromthe road region. Facades adjacent to the observer’s own street are not considered.
Despite the fact that this approximation seems quite crude, many inner-city scenes
in our dataset follow this scheme closely. Fig. 3.4 illustrates the scene labeling re28

3.3. Probabilistic Model

turned by our boosting classifier described in Section 4.3 (left) as well as the labeling
generated from the re-projection of our model (right). A large overlap corresponds
to a large likelihood in Eq. 3.23.
3.3.5. Scene Flow
Compared to the tracklet observations, the 3D scene flow likelihood directly explains
all moving objects in the scene with the road model described by R. However, incontrast to vehicle tracklets, objects that do not fit the appearance model of the car
detector (e.g., trucks, tractors, quad bikes, motorbikes) and hence have been missed
at detection time are considered here as well, unless they do not move.
Recall that each 3D flow vector f = (pf , qf ) is defined by its location pf andnormalized velocity qf on the road plane. The probability of a scene flow vector
depends on its proximity to the closest lane and on how well its velocity vector aligns
with the tangent of the respective B-spline at the corresponding foot point1

p(f |R, Θ) ∝ φf (f , R, Θ) Nf(3.24)

where




kpf k2φf (f , R, Θ) = ζf exp − 2 2 + (1 − ζf ) exp −φ̃f (f , R, Θ)
2σout(3.25)andφ̃f (f , R, Θ) = −λf 1 kpf − ϕf (pf , R)k22 − λf 2 (1 − qTf ϕ̃f (pf , R))(3.26)

with parameters ζf , λf 1 , λf 2 , σout ∈ Θ. Here, ζf accounts for outliers and λf 1 andλf 2 control the importance of the location and the orientation term, respectively.
Similar to the vehicle tracklet model from Section 3.3.2, σout denotes the width ofthe outlier distribution. The functions ϕf (pf , R) ∈ R2 and ϕ̃f (pf , R) ∈ R2
return the spline foot point and tangent vector at the location closest to pf , respectively. This is illustrated in Fig. 3.5(a). The dependencies are modeled as a hard
mixture, i.e. for each flow vector we select the spline l that maximizes Eq. 3.24.
3.3.6. Occupancy Grid
Free space information is incorporated by means of a 2D occupancy grid O ={ρ1 , . . . , ρNo }, modeled in road coordinates (y = 0), with No the number of cells in
the grid. Here, our assumption is that the road area should coincide with free space
while non-road areas may be covered by buildings or vegetation. Each cell ρ in the29

3. Urban Scene Understanding(a) Scene Flow Likelihood(b) Occupancy Grid Likelihood

Figure 3.5.: Scene Flow and Occupancy Grid Observation Model. (a) The proposed scene
flow likelihood encourages flow vectors to agree with the lane geometry. (b) The geometricprior, a ’template’ of freespace and occupied areas, determines the occupancy grid likelihood.

grid takes one of three values ρ ∈ {−1, 0, +1} representing free space, unobserved
areas and obstacles. The occupancy likelihood of cell ρ is defined asλop(ρ|R, Θ) ∝ exp
ρ · φo (R)(3.27)
No
where φo (R) ∈ {wo,1 , wo,2 , wo,3 } is a mapping that for any cell ρ returns the value(or weight) of a model-dependent geometric prior expressing the belief on the location of free space (i.e., road) and buildings alongside the road. The geometric prior
is illustrated in Fig. 3.5(b) for the case of a right turn. Intuitively, it encourages freespace where the road is located and obstacles elsewhere, with a preference towards
the roadside region. λo ∈ Θ controls the strength of this term.
3.4. Inference
Given the image evidence E, we are interested in determining the underlying roadlayout R and the location of cars C = {(l, s)} in the scene
R̂, Cˆ = argmax p(R, C|E, Θ)(3.28)

R,C

where l denotes the lane index and s contains the spline points of all detections in a
tracklet. Unfortunately, the posteriors involved in this computation have no analytical solution and can’t be solved in closed form. Thus we approximate them using
Metropolis-Hastings sampling [5, 78, 86, 123, 79]. A short review on the samplingtechniques employed in this thesis is given in Appendix A. To keep computations30

3.4. Inference

Local Metropolis Proposals (33%)
1. Vary center of crossroads c (σc )2. Vary width of all roads w (σw )3. Vary angle of crossing street α (σα )4. Vary overall orientation r (σr )5. Vary center c and width w jointly
6. Vary center c, width w, angle α and rotation r jointlyInter-Topology Metropolis Proposals (33%)
7. Re-sample κ uniformly
Global Metropolis-Hastings Proposals (33%)
8. Re-sample all parameters R = {κ, c, w, r, α} from the prior
Table 3.1.: Metropolis-Hastings Proposals for Inference. We randomly propose one of theabove moves with probability given in brackets and accept the move according to the acceptanceprobability in Eq. 3.33.

tractable, the problem is split into two sub-problems: First, we estimate R whilemarginalizing C
X
p(R, C|E, Θ)(3.29)
R̂ = argmax p(R|E, Θ) = argmax
R

R

C

Given an estimate of R, the object locations C can be inferred as
Cˆ = argmax p(C|E, R, Θ)(3.30)C

Both steps are detailed in the following two subsections. Throughout inference, thecalibration parameters, the camera poses and the ground plane are assumed to be
known, i.e., estimated with sufficient accuracy, and fixed.
3.4.1. Inferring the Road Layout
Our first goal is to estimate the road layout R given the image evidence E
R̂ = argmax p(R|E, Θ)(3.31)

R

where
p(R|E, Θ) ∝ p(E, R|Θ)(3.32)as p(E) is constant. For computing the maximum a-posteriori estimate in Eq. 3.31
we run a Markov chain for ninf er iterations and pick the sample with the highest
probability. As the normalization constant p(E) does not depend on R, it cancels in31

3. Urban Scene Understanding

Algorithm 1 Tracklet Marginals (Forward Algorithm)
Input: E = [e1 , . . . , eMd ], Ej,s ∝ pl (dj |s, l, R)
Output: log pl (t|l, R)
α1 ← M1s e1
P s
1
β← M
k=1 α1,k , α1 ← β α1 , log pl ← log β
for j ← 2, . . . , Md dofor k ← 1, . . . , Ms P
doαj,k ← Ej,k k1 kk0 =1 αj−1,k0P
β ← k αj,k , αj ← β1 αj , log pl ← log pl + log β
return log plthe sampler’s acceptance ratiop(R0 |E, Θ)q(R|R0 , Θ)
pM H (R0 |R) = min 1,
p(R|E, Θ)q(R0 |R, Θ)p(E, R0 |Θ)q(R|R0 , Θ)
= min 1,p(E, R|Θ)q(R0 |R, Θ)(3.33)

Here, q(R0 |R, Θ) denotes the proposal distribution and R0 is the proposed statecomputed from the old state R using one of the moves in Table 3.1. A short tutorial
on sampling techniques and Metropolis-Hastings can be found in Appendix A.
We exploit a combination of local, inter-topology and global moves to obtain awell-mixing Markov chain. While local moves modify R slightly, global moves
sample R directly from the prior. This ensures a quick traversal of the search space,
while still exploring local modes. For local moves we choose symmetric proposals
in the form of Gaussians centered on the previous state such that the proposal ratio
in Eq. 3.33 cancels. To avoid trans-dimensional jumps [82], we do not alter the
existence of the variable α. Instead, we include α in all models, also when κ = 1.
Table 3.1 gives an overview of the move categories picked at random. Note that while
the local and inter-topology moves are symmetric and thus purely ’Metropolis’, theglobal moves result in a proposal distribution ratio q(R|R0 , Θ)/q(R0 |R, Θ) 6= 1.
Each sample requires the evaluation of p(R|E, Θ) up to a normalizing constant.
The marginalization in Eq. 3.13 can be carried out efficiently using the forward
algorithm [22] for hidden Markov models, which for the dynamical model in Eq.
3.14 is given in Algorithm 1. Numerical instabilities due to limitations in the floating
point arithmetic precision are mitigated through proper re-normalization in each stepof the algorithm.

32

3.4. Inference

Algorithm 2 Vehicle Locations (Viterbi Decoding)Input: E = [e1 , . . . , eMd ], Ej,s ∝ pl (dj |s, l, R)
Output: {s1 , . . . , sMd } = argmaxs1 ,...,sM pl (s1 , . . . , sMd |t, l, R)δ 1 ← M1s e1for j ← 2, . . . , Md dofor k ← 1, . . . , Ms do
δj,k ← Ej,k maxk0 =1,...,k δj−1,k0
ψj,k ← argmaxk0 =1,...,k δj−1,k0dsMd ← ψMd ,Ms
for j ← Md − 1, . . . , 1 dosj ← ψj+1,sj+1
return {s1 , . . . , sMd }3.4.2. Inferring the Location of Objects
Given the road model R, we are interested in recovering the location of cars C ={(l1 , s1 ), . . . , (lNt , sNt )}, where li denotes the lane index and si are the spline indices of all detections in tracklet iCˆ = argmax p(C|E, R, Θ)(3.34)

C

Conditioned on R, all tracklets become independent such that the inference problem
decomposes into sub-problems. Neglecting the tracklet index i and the dependencyon Θ for notational clarity and observing that p(t) is constant, l can be inferred bymarginalizing over the object locations {s1 , . . . , sMd } on the lane splineˆl = argmax p(l|t, R) = argmax p(t, l|R)l

(3.35)

lwith p(t, l|R) defined by Eq. 3.11. Given l, the object locations on the lane splineŝ1 , . . . , ŝMd = argmax pl (s1 , . . . , sMd |t, l, R)
s1 ,...,sMd= argmax pl (t, s1 , . . . , sMd |l, R)
s1 ,...,sM(3.36)dare easily inferred using Viterbi decoding for hidden Markov models. The procedure is sketched in Algorithm 2, assuming uniform forward motion probability as
discussed in Section 3.3.2.

33

3. Urban Scene Understanding

3.5. Learning
A principled way to estimate the parameters Θ of our model is to learn them fromtraining data using maximum likelihood. Let us assume we are given a training set(E, R) of cardinality D, with E = {E1 , . . . , ED } denoting the image evidence andR = {R1 , . . . , RD } the annotated road layouts for each sequence, respectively. We
perform ten-fold cross-validation. As we have 113 annotated sequences in total thisleads to D ≈ 113 − 11 = 102 training sequences per fold. For the ease of indexing,
let us further assume that all model parameters are absorbed into the parameter set
Θ = {θ1 , . . . , θMΘ }, with θi denoting a single parameter (e.g., λt , λv , . . . ) andMΘ is the total number of parameters.
3.5.1. Learning the Model Parameters
Given a training fold (E, R), our goal is to find the parameter set Θ̂ that maximizes
the likelihood of the dataΘ̂ = argmax p(E, R|Θ)(3.37)

Θwithp(E, R|Θ) =D
Yp(Ed , Rd |Θ)(3.38)

d=1

Unfortunately, maximizing Eq. 3.38 directly for Θ is intractable due to the integral
over R that appears in the partition function
Z
Z(Θ) = p(E, R|Θ)dR(3.39)
Instead, let us define a Gibbs random field by re-writing p(Ed , Rd |Θ) asp(Ed , Rd |Θ) =1
exp (−Ψ(Ed , Rd , Θ))
Zd (Θ)(3.40)

where Ψ(Ed , Rd , Θ) is the sum of a set of potential functions {ψi }. Details on the
shape of the individual potentials, corresponding to the prior and the likelihoods
from Section 3.3 will be given in Section 3.5.2 and the resulting factor graph is
depicted in Fig. 3.6. Zd (Θ) is the partition function corresponding to data point dZ
Zd (Θ) = exp(−Ψ(Ed , R, Θ))dR(3.41)
necessary for turning p(Ed , Rd |Θ) into a proper distribution. Note that in Eq. 3.41
and in the following we abuse the integral over R to express integration and sum-34

3.5. Learning

mation in order to avoid clutter in the notation. Substituting Eq. 3.40 into Eq. 3.38,
we obtain1p(E, R|Θ) =exp (−Ψ(E, R, Θ))(3.42)Z(Θ)
with
Ψ(E, R, Θ) =DX

Ψ(Ed , Rd , Θ)(3.43)

Zd (Θ)(3.44)

d=1

Z(Θ) =

and

D
Y
d=1

The partition functions in Eq. 3.41 and Eq. 3.44, required for evaluating Eq. 3.38,
are still intractable to compute. However, it is possible to approximate the gradientsof the log-likelihood function
L(E, R, Θ) =DX

log p(Ed , Rd |Θ)

d=1

= −

D
X

(Ψ(Ed , Rd |Θ) + log Zd (Θ))(3.45)

d=1

which can be optimized as surrogate for Eq. 3.38. Taking the partial derivative ofL(E, R, Θ) with respect to parameter θi , we obtain
D

X∂
L(E, R, Θ) = −
∂θi
d=1




∂
∂
Ψ(Ed , Rd , Θ) +log Zd (Θ)∂θi∂θi(3.46)

While the first term in this sum can be evaluated easily as it only depends on thepotential functions themselves, the second term seems intractable at first glance as
it involves derivatives of the log-partition function. By re-arranging the terms, how-35

3. Urban Scene Understanding

ever, we obtain∂log Zd (Θ)
∂θi
1
∂
=
Zd (Θ)
Zd (Θ) ∂θiZ1∂=
exp(−Ψ(Ed , R, Θ))dR
Zd (Θ)
∂θi
Z
1
∂
= −
exp(−Ψ(Ed , R, Θ))Ψ(Ed , R, Θ)dR
Zd (Θ)∂θiZ∂
Ψ(Ed , R, Θ)dR
= − p(Ed , R|Θ)
∂θi


∂
= −
Ψ(Ed , R, Θ)∂θip(Ed ,R|Θ)(3.47)

Here, the derivative with respect to θi and the integral operator can be swapped because the partial derivative of the integrand is continuous and the limits of integration
do not depend on θi (Leibniz integral rule). Thus, the derivative of the log-partition
function can be expressed as the expectation of the potential derivatives with respect to the model distribution p(Ed , R|Θ). In contrast to [92, 156] the potentials
Ψ additionally depend on Ed in our case. While it is impossible to evaluate this expression exactly, it can be approximated by drawing samples using Markov Chain
Monte Carlo as described in Section 3.4. Sampling exhaustively from the model
distribution is computationally prohibitive. However, it has been shown [92] thatwhen starting from the data distribution, a couple of sampling iterations, say nlearn
iterations, are sufficient to draw the samples closer to the (current) model distribution. This change is sufficient to approximate the gradients well enough. Given theapproximation to the gradient, we take niter steps into its direction
!


D
ηi X
∂
∂
δθi = −
Ψ(Ed , Rd , Θ) +Ψ(Ed , R, Θ)(3.48)D∂θi∂θip(Ed ,R|Θ)d=1

where ηi is the learning rate controlling the speed of convergence. The choice of
ηi is subtle: When ηi is chosen too small, the parameters converge very slowly. On
contrary, values that are too large can easily cause parameter divergence. Furthermore, choosing a single η for all parameter dimensions i will inherently lead to slow
convergence rates as η has to be chosen small enough such that convergence for allparameters is guaranteed.
Thus, we employ a simple optimization heuristic: We initialize all ηi small enough(ηi = 10−6 ) and analyze the normalized second derivative of each parameter, which
is an indicator for the smoothness of the learning curves, in a time interval of 10
iterations. For all smooth curves we multiply ηi by a factor of 10 while we divide all36

3.5. Learning

Figure 3.6.: Factor Graph. This figure shows the factor graph representation of the directed
graphical model in Fig. 3.3 corresponding to the distribution in Eq. 3.49. Dependencies between random variables are expressed using factor nodes (black squares) and the latent tracklet
variables s and l have been marginalized for clarity of presentation.

ηi ’s by 10 in case the curves become noisy. In practice, this algorithm led to quick
and stable convergence. We also observed the procedure to be largely independentof the initialization, which has been empirically chosen for all parameters.
3.5.2. Energy Potentials and Derivatives
For applying the learning procedure described in Section 3.5.1, all potential functions1 need to be properly defined and their derivatives with respect to the model
parameters Θ must be calculated. The joint potential Ψ(E, R, Θ) from Eq. 3.40
decomposes asΨ(E, R, Θ) = ψp (R, Θ) + ψt (T , R, Θ)+ ψv (V, R, Θ) + ψs (S, R, Θ)+ ψf (F, R, Θ) + ψo (O, R, Θ)(3.49)

using the same subscript notation as in Eq. 3.3. The corresponding factor graph is
illustrated in Fig. 3.6. In the following, we derive each potential in Eq. 3.49.

1Note that throughout this section we call ’ψ(·)’ a potential function for clarity of notation, even though(strictly speaking) ’−ψ(·)’ is the actual energy potential.

373. Urban Scene Understanding

By taking the negative logarithm of Eq. 3.4 and absorbing all constant terms
into the partition function, we obtain the prior potential

Prior:

ψp (R, Θ) = − log ξp,κ − λp log fκ (α)
1+ φp (R, µp(κ) )T Λp(κ) φp (R, µ(κ)
p )2(3.50)

withφp (R, µp(κ) ) = (c, r, log w)T − µ(κ)
p(3.51)

4and ξp , λp ∈ Θ. While µp ∈ R can be parameterized element-wise, i.e. µp ∈Θ, Λp ∈ R4×4 has to fulfill the properties of a precision matrix, i.e. it must be
symmetric positive definite. These properties can be enforced by considering theCholesky decomposition of Λ,Λ = LT L(3.52)
into a lower triangular matrix LT and an upper triangular matrix L, omitting all
indices for clarity of notation. Clearly, Λ is symmetric positive definite and L canbe parameterized asL1,1 L1,2 L1,3 L1,4
 0 L2,2 L2,3 L2,4 (3.53)
L= 0
0 L3,3 L3,4 
00
0 L4,4
with ∀i≤j : Li,j ∈ Θ. The required derivatives with respect to ξp,i , µ, Li,j and λp
are readily given by∂ψp (R, Θ)∂ξp,i∂ψp (R, Θ)∂µ∂ψp (R, Θ)∂Li,j∂ψp (R, Θ)
∂λp

= −

[κ = i]ξp,i= −Λ φp (R, µ)


1
∂LT
∂L
= φp (R, µ)T
L + LTφp (R, µ)
2
∂Li,j
∂Li,j
= − log fκ (α)(3.54)

In practice, one can directly optimize for log ξp,i instead of ξp,i for stability.
The potential corresponding to the vehicle tracklet likelihoodand its derivative are obtained by taking the logarithm of Eq. 3.10 and differentiating
Vehicle Tracklets:38

3.5. Learning

it:
!
Nt
L
X
λt X
log
p(ti , l|R)ψt (T , R, Θ) = −Nt i=1l=1!
NtLX∂ψt (T , R, Θ)
1 X
logp(ti , l|R)= −∂λt
Nt i=1(3.55)(3.56)

l=1

Here, λt ∈ Θ is a parameter controlling the strength of the feature cue and thetracklet probability p(t, l|R) is defined by Eq. 3.10. We have added an additional
degree of freedom λt to the tracklet potential ψt , which accommodates for violationsof the naïve Bayesian observation model and controls the relative strength of the
tracklet feature with respect to the prior and all other features.
Similarly, the vanishing point potential and its derivative are
obtained from Eq. 3.21 as
Vanishing Points:

ψv (V, R, Θ) = −NvXlog (ζv + (1 − ζv ) exp (−λv φv (vi , R, Θ))) (3.57)

i=1
Nv
X
∂ψv (V, R, Θ)
1 − exp (−λv φv (vi , R, Θ))
= −
∂ζv
ζ
v + (1 − ζv ) exp (−λv φv (vi , R, Θ))i=1
Nv
X∂ψv (V, R, Θ)(ζv − 1) exp (−λv φv (vi , R, Θ)) φv (vi , R, Θ)= −∂λv
ζv + (1 − ζv ) exp (−λv φv (vi , R, Θ))i=1

with φv (v, R, Θ) measuring the error with respect to the orientation of the closest
street as defined in Eq. 3.22.
Semantic Scene Labels: The semantic scene label potential is given by taking thelogarithm of Eq. 3.23 and differentiating with respect to λs
Ns
λs X
ws,φs (R) si,φs (R)Ns i=1(3.58)Ns∂ψs (S, R, Θ)
1 X= −ws,φs (R) si,φs (R)∂λs
Ns i=1(3.59)

ψs (S, R, Θ) = −where φs (R) ∈ {1, 2, 3} selects the class label according to the segmentation of thescene induced by the current road layout R. For further details, we refer the reader
to Section 3.3.4 and the illustration in Fig. 3.4.

39

3. Urban Scene Understanding
Scene Flow: The scene flow potential is obtained by taking the logarithm of Eq.
3.24 and differentiating with respect to the outlier constant ζf and the importanceweights λf 1 (location) and λf 2 (orientation):Nfψf (F, R, Θ) = −1 X
log φf (fi , R, Θ)(3.60)
Nf i=1




kp
k2
Nf
2
exp − 2σf,i− exp −φ̃f (fi , R, Θ)X
2∂ψf (F, R, Θ)
= −
∂ζf
i=1

out

Nf φf (fi , R, Θ)Nf(ζf − 1) exp −φ̃f (fi , R, Θ) ∂ φ̃ (f , R, Θ)X∂ψf (F, R, Θ)
= −
∂λf 1
i=1

f

i

Nf φf (fi , R, Θ)
∂λf 1


Nf
(ζf − 1) exp −φ̃f (fi , R, Θ) ∂ φ̃ (f , R, Θ)X∂ψf (F, R, Θ)
= −
∂λf 1
i=1

f

Nf φf (fi , R, Θ)

i

∂λf 2

with the unnormalized probability of a single scene flow vector given by
kpf k2φf (f , R, Θ) = ζf exp − 2 2 + (1 − ζf ) exp −φ̃f (f , R, Θ)
2σout(3.61)andφ̃f (f , R, Θ) = −λf 1 kpf − ϕf (pf , R)k22 − λf 2 (1 − qTf ϕ̃f (pf , R))(3.62)The partial derivatives with respect to λ are given by∂ φ̃f (f , R, Θ)= −kpf − ϕf (pf , R)k22∂λf 1(3.63)∂ φ̃f (f , R, Θ)= qTf ϕ̃f (pf , R) − 1∂λf 2(3.64)

with ϕf (pf , R) and ϕ̃f (pf , R) returning the foot point and tangent of the closest
lane spline as in Eq. 3.26 and illustrated in Fig. 3.5(a).

403.5. Learning
Occupancy Grid: Taking the logarithm of Eq. 3.27 and its derivative, the occupancy grid potential readsNoλo X
ρi · φo (R)No i=1(3.65)No∂ψo (O, R, Θ)
1 X
ρi · φo (R)= −∂λoNo i=1(3.66)ψo (O, R, Θ) = −where φo (R) ∈ {wo,1 , wo,2 , wo,3 } is a mapping that for any cell ρ returns the valueof the model-dependent geometric prior expressing the belief on the location of freespace (i.e. road) and buildings alongside the road. For more details the reader isreferred to Section 3.27 and the illustration in Fig. 3.5(b).

414. Image EvidenceThis chapter describes the feature cues used by our probabilistic model describedin Section 3.3. They can be categorized into monocular cues (i.e., vehicle tracklets,
vanishing points and semantic scene labels) for which one camera is sufficient andstereo cues (i.e., 3D scene flow and occupancy grids) which require a stereo camera
setup. We represent all features in the reference coordinate system which as described in Chapter 3 is located below the left camera coordinate system in the last
frame of each sequence as illustrated in Fig. 4.3. The required ego-motion falls off
as a by-product when computing the scene flow features as described in Section 4.4.
4.1. Vehicle Tracklets
Vehicle tracklets are sets of vehicle detections which are associated over time andrepresent one of the strongest cues in our framework. This is because the observationof moving objects tells us a lot about the structure of the scene as well as where thelanes are located and which vehicles are allowed to move given the current traffic
light situation. Empirically, we found that pedestrians occur much more rarely in ourdatasets and are thus less important in this context. While it would be straightforward
to extend our model to include pedestrians, we focus on vehicles (i.e., cars) here. As
we are interested in reasoning about the scene in bird’s eye perspective, we also
propose a way to extract 3D location estimates from the 2D object detections.
As mentioned earlier, we define a tracklet as a set of object detections, projected
into bird’s eye perspective t = {d1 , . . . , dMd } with d = (fd , md , Sd , od ). Here,fd ∈ N is the frame number and md ∈ R2 , Sd ∈ R2×2 are the mean and covarianceof the Gaussian distribution N (m, S) describing the object location in road coordinates. od ∈ ∆7 is a discrete orientation distribution over 8 possible points of view.
The goal of the tracking stage is to associate object detections to tracklets and project
them into 3D using cues such as the object size or the bounding box ground contact
point in combination with the height and the pitch angle of the camera. Association of detections to tracklets is performed in image-scale space to better account for
uncertainties of the object detector.

43

4. Image Evidence(a) Bounding Box b = (u, v, w, h)(b) Orientation o ∈ R8

Figure 4.1.: Illustration of Vehicle Detections. We detect objects in adjacent frames, estimate
their orientation and associate them over time.

4.1.1. Detection
First, let us define a 2D object detection as d̃ = (f, b, o)1 , with frame index f ∈ N
and 2D object bounding box b = (u, v, w, h) ∈ R4 , where (u, v)T is the bottomcenter and (w, h)T are the width and height of the bounding box. In contrast to mosttraditional object detectors, we also estimate a (discrete) distribution over 8 possible
points of view, o ∈ ∆7 , giving us a sense of orientation of the object. All involved
variables are illustrated in Fig. 4.1.
In order to detect objects {(f, b, o)} in an image, we train the part-based object
detector2 of [60] on a large set of manually annotated images. The object detection system described in [60] is based on mixtures of multi-scale deformable partmodels, can represent highly variable object classes and achieves state-of-the-art
performance in difficult scenarios such as the ones presented in the PASCAL object
detection challenge [59]. For training object models we employ a latent SVM [60]where the location of the individual parts of an object are assumed to be unknown attraining time and maximized over. The model parameters are found using stochastic gradient descent, embedded into an alternating scheme which also estimates thehidden variables at the same time.
In contrast to the original model of [60], our annotations do not only comprisethe bounding boxes b, but also the relative object orientations o, discretized into
8 viewpoints as illustrated in Fig. 4.1(b). We use one component per viewpointand fix the latent variables such that they correspond to the components according
to the ground truth orientations relative to the observer. By introducing this additional degree of supervision we are able to recover a distribution over possible object
orientations o ∈ ∆7 at test time for each detected object. Algorithm 3 illustrates
the non-maximum-suppression mechanism which computes a small number of nonmaximum suppressed detections with discrete orientation distributions from all raw
detections with associated orientation and score. In order to obtain a proper distribu1
2

We use a tilde for distinguishing 2D object detections d̃ (or vehicle tracklets t̃) from 3D detections d (orvehicle tracklets t)
Source code available at: http://people.cs.uchicago.edu/~rbg/latent/

44

4.1. Vehicle Tracklets

Algorithm 3 Multi-Class Non-Maximum-Suppression
Input: L-SVM detections with orientation and score {(b, o, s)}
Output: NMS detections with orientation distribution {(b, o)}A ← {(b, o, s)}B←∅while A 6= ∅ do// Get all detections that overlap with the highest scoring onea ← argmaxx∈A score(x)nobox(x) ∩ box(a)Aa ← x | x ∈ A ∧ box(x)> τd∪ box(a)// For each orientation, get highest score within Aa
for i ← 1, . . . , 8 do
Ai ← {x | x ∈ Aa ∧ orientation(x) = i}oi ← maxx∈Ai score(x)// Apply
Psoftmax normalization
Z ← i exp(oi )for i ← 1, . . . , 8 dooi ← Z1 exp(oi )// Add detection to B and remove Aa from A
B ← B ∪ (box(a), o)A ← A \ Aareturn B
Ption o ∈ ∆7 with i oi = 1, the softmax transformation is applied to the maximumof all detections scores over all orientation bins. Fig. 4.2 illustrates the quality of the
MAP orientation estimate in terms of the confusion matrix over orientation classes.
4.1.2. Tracking
The association of 2D object detections {d̃} to 2D object tracks t̃ = {d̃1 , . . . , d̃T }with d̃ = (f, b, o) is solved using a two-stage process which utilizes the Hungarianalgorithm [116] for global frame-to-frame data association. As all measurements
are made in the image domain, it is natural to associate objects directly in the image
rather than in 3D to better account for uncertainties.
First, individual frames are associated frame-byframe in a tracking-by-detection framework. For all frames of a sequence, we associate all object detections above a certain detection score to the existing tracklets
using the Hungarian algorithm [116]. If a detection has not been assigned to anyof the existing tracklets, a new tracklet is spawned. The affinity matrix is computed
using both geometry and appearance cues of the object. Experimentally we foundthat combining both cues yields the best association results possible. As geometry
Frame-to-Frame Association:45

true heading

4. Image Evidence

1 369 23

1

0

69 14

0

1

2 30 106

1

0

3

28

6

0

3 2

1

799 17

4

7

1

0

4 0

1

9 247

3

3

2

0

5 5

1

11

0

372 3

0

6

6 1

0

0

7

3 146

0

0

7 2

6

6

1

0 131 321

0

8 1

0

0

2

7

0

0

41

1

2

3
4
5
6
estimated heading

7

8

5

1

3
7

2

6

4

8

Figure 4.2.: Confusion Matrix of the orientation estimates by the part-based object detector
presented in [60], trained in a semi-supervised fashion.

cue we employ the bounding box intersection over union score. The appearance cue
is computed by correlating the bounding box region in the previous frame with thebounding box region in the current frame, using a small margin (20%) to account for
the localization uncertainty of the object detector. Let d̃i and d̃j denote two object
detections in consecutive frames. Then, the (i, j)’th entry of the affinity matrix A
is given byΓ(d̃i , d̃j ) if Γ(d̃i , d̃j ) < τt1
Ai,j =(4.1)∞
otherwise box(d̃i ) ∩ box(d̃j )× 1 − xcorr(d̃i , d̃j )Γ(d̃i , d̃j ) = 1 −box(d̃i ) ∪ box(d̃j )where box(·) returns the bounding box b that belongs to a detected object, xcorr(·, ·)returns the maximum of the normalized cross-correlation of two detections, and τt1
is the gating threshold of stage one. The optimal assignment given the affinity matrix Aij can be efficiently computed in polynomial time using the Kuhn-Munkres
algorithm [116], yielding a set of initial tracklets.
So far, only adjacent object detections havebeen considered. In practice, however, it occurs quite frequently that object detections are missing for a couple of frames. This may be caused by imperfectionsof the object detector, or simply by the fact that other objects like cars, pedestrians
or traffic signs occlude the target of interest. Yet, longer tracklets provide more information to our model than short tracklets. Thus we employ a second association
stage where we associate tracklets with each other which may be occluded for up to

Tracklet-to-Tracklet Association:46

4.1. Vehicle Tracklets

20 contiguous frames. Similar to the problem above we make use of the Hungarianalgorithm for optimal data association, but this time we associate tracklets instead ofdetections and consider the whole sequence at once. Each entry of the association
matrix refers to a pair of tracklets within the whole sequence. The affinity matrix A
is given byΓ(t̃i , t̃j ) if f∆ (t̃i , t̃j ) < N ∧ Γ(t̃i , t̃j ) < τt2
Ai,j =(4.2)∞
otherwiseΓ(t̃i , t̃j ) = min dist(t̃i , t̃j ), dist(t̃j , t̃i ) × 1 − xcorr(t̃i , t̃j )where f∆ (·, ·) returns the frame gap between two tracklets and dist(·, ·) extrapolates
the bounding boxes of each tracklet linearly to predict the bounding boxes of theother tracklet and returns the mean of the normalized prediction errors with respect
to the bounding box location, width and height. Extrapolation is carried out by
linear regression, i.e., we fit lines to the bounding box location, width and height,
where each of these modalities is considered a function of the frame number. We
also experimented with higher-order prediction schemes, but found a decrease inperformance due to the large and correlated noise in our measurements. Similar toabove, xcorr(·, ·) compares object appearances via the normalized cross-correlation
score, but this time maximized over all possible combinations of object detections
within t̃i and t̃j . We found that this procedure to significantly alleviate the effectof semi-occlusions and moderate appearance changes and leads to longer and morestable tracklet associations. The gating threshold of stage two is denoted by τt2 .
4.1.3. Projection into 3D
While the object detection and object tracking stages in Section 4.1.1 and Section
4.1.2 operate directly in the 2D image domain (t̃), the proposed intersection model
reasons about tracklets in 3D (t). In order to extract 3D information, we make thefollowing two observations:• Intersections are typically flat and can be well approximated using a single
ground plane, which is easily and robustly extracted from structure-frommotion point clouds or disparity maps. For an overview on plane-fitting methods, the reader is referred to [39, 169, 201, 62]. As cars are driving on the
ground, the bounding box contact point (bottom of the bounding box) in combination with an estimate of the ground plane can be employed to ’triangulate’the 3D location of the object.
• Given the 2D bounding box and the 3D dimensions of an object, its distancecan be estimated. Hereto, we learn the statistics of cars from bounding boxes
and disparity images using a held-out car dataset and back-propagate the location and its uncertainty into 3D.
47

4. Image Evidence

Figure 4.3.: Projection of 2D Object Detections into 3D. Assuming known calibration parameters K, a rigid 3D ground plane transformation T and knowledge about typical object
dimensions (∆x, ∆y), the 3D location (x, z) can be estimated from the bounding box size
(w, h) and ground contact point (u, v).

Both ideas are illustrated in Fig. 4.3 and detailed in the following. Let ϕ : b →m, S be a mapping which takes an object bounding box b ∈ R4 as input and maps it
to a 3D location (x, z)T ∼ N (m, S) on the road surface, where m is the mean and S
denotes the covariance matrix. Again, 3D refers to the bird’s eye perspective (y = 0
plane in road coordinates) as we are making a ground plane assumption, i.e. weassume that all objects are attached to and move on a common ground plane. Let us
further assume that the mapping is probabilistic. As cues for this mapping we use thelocation of the bounding box ground contact point as well as the bounding box widthand height. The unknown parameters of the mapping are the uncertainty in bounding
box location σu , σv and size σw , σh as well as the real-world object dimensions∆x, ∆y and their uncertainties σ∆x , σ∆y . All parameters are learned from a held
out training dataset with annotated bounding boxes and depth from stereo.
More formally, let (u, v)T denote the image coordinates of the bottom-center pointof the object’s bounding box and let w, h be the width and height of the boundingbox. Let (x, 0, z)T be the 3D location of an object in ground plane coordinates(y = 0) as illustrated in Fig. 4.3. Further, let ∆x, ∆y be the object width and heightin meters, measured via parallel-projection to the plane z = 0, which is coplanar to
the image plane. Finally, let o denote the MAP orientation of the vehicle as returnedby the object detector.
The posterior on the object’s 3D location is factorized asp(x, z|u, v, w, h, ∆x, ∆y, o)∝ p(u, v, w, h|x, z, ∆x, ∆y, o)p(x, z)= p(u, v|x, z, ∆x, ∆y, o) p(w|x, z, ∆x, ∆y, o) p(h|x, z, ∆x, ∆y, o)= p(u, v|x, z) p(w|z, ∆x, o) p(h|z, ∆y)∝ p(x, z|u, v) p(z|w, ∆x, o) p(z|h, ∆y)

48

(4.3)

4.1. Vehicle Tracklets

where we have assumed a uniform prior over x and z. The first term on the righthand side of Eq. 4.3 relates the bounding box ground contact point (u, v)T to theobject’s 3D location (x, 0, z)T . The second and the last term model the relationshipbetween the distance z of the object to the observer and the bounding box width
w and height h, respectively. Note that the term p(z|w, ∆x, o) which models thewidth ∆x in terms of parallel projection to the z = 0 plane depends on the object
orientation o. This is because the width of a vehicle differs from its length, thus welearn a separate set of statistics for each object orientation. However, for clarity ofpresentation the dependency on o will be dropped in the following. Letx, z|u, v ∼ N (µ1 , Λ−1
1 )

(4.4)

z|w, ∆x ∼ N (µ2 , λ−2
2 )

(4.5)

N (µ3 , λ−2
3 )

(4.6)

z|h, ∆y ∼Then, from Eq. 4.3 we have x, z|u, v, w, h, ∆x, ∆y ∼ N (m, S) with
 
 
0
0
+ SΛ3
m = SΛ1 µ1 + SΛ2µ3µ2
S = (Λ1 + Λ2 + Λ3 )−1
where Λ1 has full rank and Λ2 , Λ3 are singular matrices of the form




0 0
0 0
Λ2 =
Λ3 =
0 λ2
0 λ3

(4.7)

(4.8)

The individual feature cues are described in the following.
Let x, z|u, v ∼ N (µ1 , Λ−11 ) and let us assume a standard
pinhole camera model which projects a 3D ground plane point (x, 0, z)T to the point(u, v)T on the image plane. In homogeneous coordinates, this projection can be
written as
 
 
x
u
 
v  = P3×4  0 
(4.9)
z 
1
1
Ground Contact Point:where P = K T R is the product of a calibration matrix K3×3 , the transformationfrom ground plane coordinates to camera coordinates T3×4 (estimated a-priori) andan additional camera pitch error θ, parameterized by the rotation matrix


0 0
0
0
0 cos θ − sin θ 0
R4×4 (θ) = (4.10)
0 sin θ cos θ 0
0 0
0
1
49

4. Image Evidence

Given (u, v)T we obtain µ1 = (x, z)T by solving the linear system
 
x
A
=b
z

(4.11)with
uP31 − P11 u(P33 cos θ − P32 sin θ) − (P13 cos θ − P12 sin θ)
vP31 − P21 v(P33 cos θ − p32 sin θ) − (P23 cos θ − P22 sin θ)
uP31 − P11 uP33 − P13=(4.12)
vP31 − P21 vP33 − P23
P14 − uP34b =P24 − vP34

A =where Pij denotes the ij’th element of P and we have made use of E(θ) = 0 as
R only models the error in pitch. Assuming the covariance of (u, v)T to be known,
the covariance of (x, z)T can be approximated using error propagation. Since thetransformation implied by Eq. 4.11 is non-linear with respect to u, v and θ, we
linearize it by means of a first-order Taylor expansion. Given σu , σv and σθ we have 2
σu 0 0−12
Λ1 = Σ1
Σ1 = J  0 σv 0  JT
(4.13)
0 0 σθ2
where the Jacobian J ∈ R3×3 is given by
J=

∂
A−1 b
∂u

∂
A−1 b
∂v

∂
A−1 b
∂θ



(4.14)

with∂(A−1 b) = ∂A−1 b + A−1 ∂b= −A−1 ∂AA−1 b + A−1 ∂b= A−1 ∂b − ∂AA−1 b
and
=

∂
A
∂v

=

∂
A
∂θ

50



∂
A
∂u



=

P31 P330000
P31 P33



0 P12 − uP32
0 P22 − vP32



∂
b
∂u

=

∂
b
∂v

=

∂
b
∂θ

=

(4.15)



−P34
0





0
−P34
 
0
0


(4.16)

4.1. Vehicle Tracklets

As state above, we assume z|w, ∆x, o ∼ N (µ2 , σ22 ). From thepinhole model we obtain the relationshipObject Width:

w=

f ∆x
z

(4.17)

with f the focal length, or equivalentlyµ2 = z =f ∆xw(4.18)

which is a non-linear function in w. Using the same reasoning as above, we obtainthe variance in z through error propagation as
 2

σ
0
λ2 = σ2−2
σ22 = J w 2 JT
(4.19)
0 σ∆xwith JacobianJ = − fw∆x
2

f
w



(4.20)In order to properly account for the viewing angle represented by a set of discrete
object orientation classes o, we learn a separate set of parameters (µ2 , σ22 ) for eacho as illustrated in Fig. 4.4 and 4.5.
Similarly to the object width term, we assume a Gaussian distribution z|h, ∆y ∼ N (µ3 , σ32 ) for the object height term. We obtain
Object Height:µ3 = z =f ∆yh(4.21)

 2

σh 0
JT
2
0 σ∆y

(4.22)

with variance
λ3 = σ3−2

σ32 = Jand JacobianJ = − fh∆y
2

f
h



(4.23)

Note that the height does not depend on the object heading o.
Learning the Parameters of the 3D Projection Model: The unknown parametersof the proposed projection model σu , σv , σw , σh , ∆x, ∆y, σ∆x and σ∆y are learned
automatically from annotated training data. For this purpose we have collected adataset of 1020 images that capture 3634 vehicles with annotated 2D bounding boxes
and computed the corresponding disparity maps. The labels do not only include thebounding box but also the heading of the vehicles, quantized into 8 orientationso ∈ {1, . . . , 8}. This is important as the object width depends on the orientation of
the vehicle.

51

4. Image Evidence

40

σu

35

σv

30

σΔ v

a
b
σu 0.0400 1.8239
σv 0.0915 -1.3080
σw 0.1474 1.1972
σh 0.1111 -1.2124

σ

Δu

25
20
15
10
5
0
20

40

60

80

100

120

140

(a) Object Orientation o ∈ {1, 2}
40

σu

35

σv

30

σΔ v

σΔ u

a
b
σu 0.1076 3.8502
σv 0.0396 1.9848
σw 0.2107 5.3625
σh 0.0893 1.0360

25
20
15
10
5
0
20

40

60

80

100

120

140

(b) Object Orientation o ∈ {3, 4}
40

σu

35

σv

30

σΔ v

a
b
σu 0.0975 3.1407
σv 0.0635 0.5281
σw 0.1842 5.2666
σh 0.0806 0.8323

σΔ u

25
20
15
10
5
0
20

40

60

80

100

120

140

(c) Object Orientation o ∈ {5, . . . , 8}

Figure 4.4.: Bounding Box Uncertainty. This figure illustrates the linear relationship between
the error of the object detector and the object size (height h) for the 3 object orientation classes.
The dashed lines show the linear least square approximations σx (h) = a h + b.

52

2

2

1.8

1.8

1.6

1.6

1.6

1.4

1.4

1.4

1.4

1.2

1.2

1.2

1.2

1

1

p(∆ y)

2
1.8

1.6

p(∆ x3)2
1.8p(∆ x2)p(∆ x1)4.1. Vehicle Tracklets

1

1

0.8

0.8

0.8

0.8

0.6

0.6

0.6

0.6

0.4

0.4

0.4

0.4

0.2
0
0

0.2
1

2

3

4
5
∆ x [meters]

6

7

8

0
0

µ
σ

∆x1
1.86
0.28

0.2

0.2
1

2

1

3

4
5
∆ x [meters]

6

2

∆x2
4.37
0.64

7

8

0
0

1

2

3

4
5
∆ x [meters]

6

7

8

3

∆x3
2.82
0.63

0
0

1

2

3

4
∆ y [meters]

5

6

7

8

∆y
1.59
0.22

Figure 4.5.: Object Size Statistics. Cars in our dataset are ∼ 1.9m wide and ∼ 4.4m long.
Here, ∆x and ∆y are the width and height of the object after parallel projection onto the z = 0
plane, with z the optical axis.

We first estimate the parameters related to detection accuracy σu , σv , σw and σhby comparing the object detections with the manually labeled 2D bounding boxes.
Due to the characteristics of sliding-window detectors, we expect the noise to be
dependent on the object scale. A good approximation to object scale is the boundingbox height h as in contrast to the bounding box width it is largely invariant withrespect to the viewing angle. Furthermore, it is readily given by the object detector.
Figure 4.4 depicts σu , σv , σw and σh as a function of h. As the noise σ depends
approximately linearly on h it can be well represented via the linear modelσx (h) = ax,o h + bx,o(4.24)

with x ∈ {u, v, w, h}. Here, a and b are obtained using least squares estimation.
The parameters describing the real-world dimensions of the object’s parallel projection to the z = 0 plane are ∆x, ∆y, σ∆x and σ∆y . They are obtained from theannotated data in conjunction with the stereo information. Given a rectified stereo
camera rig, the following relations hold:
∆x =

zw
bw
=
f
d

∆y =

zh
bh
=
f
d

(4.25)

Here, z is the distance of the object to the camera, f denotes the camera’s focal
length, b is the camera baseline and d represents the median disparity within the 2D
bounding box. As noted above, special care has to be taken for ∆x as it depends on
the orientation of the object. We learn a separate ∆x for each of three car orientation classes illustrated in Fig. 4.4. The results are depicted in Fig. 4.5. When viewed
frontally or from behind a typical car is ∼ 1.9 meters wide. It spans ∼ 4.4 meterswhen viewed from the side. The resulting posterior probabilities for 3 tracklet detec53

4. Image Evidence

pos
width
heightcombined

0.15
0.1

40

0.05
0
0

10

20

30

40

50

60

pos
width
heightcombined

0.3
0.2

30

20

0.1
0
0

10

20

30

40

50

60

pos
width
heightcombined

0.3
0.2

10

0.1
0
0

10

20

30

40

50

60

0

Figure 4.6.: Depth Posterior Distribution. This figure depicts the marginal depth distributions
for each feature cue individually (red,green,blue) and the posterior distribution (black) whencombining the results using Eq. 4.3.

tions are illustrated in Fig. 4.6. The colored curves are the individual cues discussed
in the previous sections and the black curves depict the combined posterior results.
4.1.4. Temporal Integration
As the raw 3D location estimates {(m, S)} are noisy due to the low camera viewpoint, the uncertainties in the object detector and the ground plane estimation process, we temporally integrate detections within a tracklet t using a Kalman smoother[105] assuming a constant velocity model. This step finally yields the tracklet observations which are augmented by the frame number fd and the object orientation
distribution od to tracklets t = {d1 , . . . , dMd } with d = (fd , md , Sd , od ) andserve as input to our probabilistic model in Section 3.3.2. An illustration of the estimated 3D tracklets is provided in Fig. 4.7, where the covariance ellipses depict theuncertainty in object location.

54

4.2. Vanishing Points(a) Frame 40(b) Frame 80

Figure 4.7.: Filtered 3D Vehicle Tracklets. This figure shows two frames of a crossing sequence. The top row depicts the input image with the detected objects and the bottom row
shows the 3D tracklets in bird’s eye perspective after smoothing. The covariance ellipsoids areshown for the current frame. The gray trajectory is generated by the moving observer. The
top-right tracklet is caused by outlier detections from the tipper at the right side of the image.

Figure 4.8.: Vanishing Points. For each scene, we detect up to two dominant vanishing points,
one corresponding to the forward-facing street (shown in green with vanishing lines in red) and
one corresponding to the crossing street (vanishing lines in blue, the corresponding vanishingpoint is located outside of the image).

4.2. Vanishing Points
Vanishing points are good street orientation cues as image gradients from road markings or buildings are often aligned with the dominant streets. For example, in Fig.
1.2 the forward facing street is well supported by the curbstones. In many cases, thecrossing street is supported by road markings, windows or building outlines as well.
We detect up to Nv = 2 vanishing points V = {v1 , . . . , vNv }, where a vanishingpoint is defined by a rotation angle around the y-axis in road coordinates, i.e. weassume that all vanishing lines are collinear with the ground plane and vi represents55

4. Image Evidence

their yaw angle. All 3D lines that are collinear with a vanishing line intersect at
the same vanishing point. For typical scenarios, two vanishing points are dominant:
One which is collinear with the forward facing street and one which is collinear withthe crossing street. The vertical vanishing points are not informative.
In order to detect vanishing points we first extract long line segments. Towards
this goal we make use of the method described by Kosecka et al. [114], which detects long lines in the image by Canny edge detection [35] followed by labeling theconnected orientation components and fitting the line parameters using principal
component analysis. Given the line segments, we detect vanishing points similarly
to [114], but taking into account the (known) camera calibration information and restricting the search space such that all vanishing lines are collinear with the groundplane. Additionally, we relax the model to also allow for non-orthogonal vanishingpoints as this is required by the intersection types in our dataset.
Unfortunately, traditional vanishing point detection methods [114, 15] require relatively clean scenarios and tend to fail in the presence of clutter such as cast shadowson a sunny day, railway tracks or defects in the road surface that easily mislead thevanishing point detection process. To tackle this problem, we learn a k-nearestneighbor classifier based on a held-out annotated set of 185 images, in which all
detected line segments have been manually labeled as either structure or clutter.
Here, structure refers to the line segments of interest, which are aligned with the
major orientations of the streets or building facades. The classifier’s confidence on
structure is used as a weight in the vanishing point voting process.
The feature set for classification comprises multiple types of information: As geometric information the position, length and orientation of the line are included. Further, we incorporate context knowledge by counting the number of lines with similar
and perpendicular orientation in a local window around the target pixel. The local
appearance is represented by the mean, standard deviation and entropy of all pixels,
computed over a small margin of 3 pixels at both sides of the line. Finally, we add
texton-like features from a Gabor filter bank as well as the 3 principal componentsof the scene GIST [145].
The benefits of this additional learning step are highlighted in Fig. 4.9(a), whichshows the ROC curve for classifying lines into structure and clutter. The curves havebeen obtained by adjusting k for the k-nn classifier in the learning based method andby varying the inlier threshold for [114]. Fig. 4.9(b) compares the classification
results for a particular scene: While the cast shadows in the lower-left part of theimage causes wrong evidence for traditional vanishing point detectors [114] (top),
the proposed classification step is able to reject most of those line segments (bottom).
Applying the restricted version of [114] to all structured line segments and thresholding yields up to Nv = 2 vanishing points V = {v1 , . . . , vNv } which serve as
input to the vanishing point likelihood in Section 3.3.3.

56

4.3. Semantic Scene Labels

1true positive rate

0.8

0.6

0.4

0.2
Learning based
Kosecka et al.
0
0

0.2

0.4
0.6
false positive rate

0.81(a) ROC curve for classifying line segments into structure andclutter.

(b) Kosecka et al. (top) vs. proposed approach (bottom). Red
corresponds to structure.

Figure 4.9.: Structured Line Segments. As cast shadows and road defects generate a lot ofstructured line segments which can easily confuse the vanishing point estimation process, weclassify each detected line into structural information versus clutter.

Figure 4.10.: Semantic Image Segmentation. We learn a classifier to compute per-pixel likelihoods for the classes sky, background and foreground.

4.3. Semantic Scene Labels
The appearance of objects and what is often referred to as ’stuff’ in the computer vision literature (i.e., objects without extend such as sky road or vegetation) provides
additional cues about the layout of the scene. For example, the texture statistics of57

4. Image Evidenceroad area usually differs from the statistics of building or sky. Furthermore, geometric priors can be taken into account, e.g. buildings are located above the roadand below the sky. We can make use of this information by comparing a semantic
segmentation of the scene to a projection of our model into the image. See Fig. 3.4
and Fig. 4.10 for an illustration.
For extracting semantic information in the form of scene labels we use the joint
boosting framework proposed in [180] to learn a strong classifier. Following Wojek
et al. [191], we divide the last image of each sequence into patches of size ns × ns
pixels and classify them into the categories road, background and sky. In order toavoid hard decisions and to interpret the boosting confidences as probabilities weapply the softmax transformation [119] to the resulting scores. The semantic labelof a single patch is defined as s ∈ ∆2 , where ∆2 is the unit 2-simplex as describedin Section 3.2. We make use of the following features for classification:• Generic texture cues are computed from the first 16 coefficients of the WalshHadamard transform [2], which is a discrete approximation to the cosine transformation and has been shown to perform well in practice [191] on sequences
similar to the ones used in this work.
• As urban scenes contain many man-made structures we include the feature
set for man-made structure detection described by Kumar et al. [118, 117] on
patches of size 16×16, 32×32 and 64×64 pixels.
• Finally, the image location is incorporated by concatenating the pixel coordinates to the feature vector. This enables to encode knowledge such as the sky
being located on top and the road at the bottom of the image.
For training, we use a hold out dataset of 200 hand-labeled images. Fig. 4.10 illustrates the results of the proposed semantic image feature cue on one of the test
images from our database. After softmax normalization we obtain a (discrete) scenelabel distribution s for each image patch s ∈ S, which is used in our semantic scenelabel likelihood described in Section 3.3.4.
4.4. Scene Flow
Due to the low viewpoint of the car-mounted camera depth information is very noisy
when only relying on monocular feature cues. Thus, we also investigate the use of
stereo features, which are described in this and the following section. Note that evenfor stereo features the depth error increases quadratically with the distance. However,
due to the different noise properties a gain in performance can be expected whenproperly combining stereo and monocular cues, which we verify in the experimental
section of this thesis.
The first feature cue we pursue here is the 3D scene flow caused by moving traffic
participants. The observation is that most of the non-background motion in the scene
58

4.4. Scene Flow

35
30
25
20
15
10
−10

0

10

20

Figure 4.11.: Scene Flow. By matching features between the left and right images of a stereo
pair and over time, we obtain 3D flow vectors (left). Color codes disparity from large (red) tosmall (green) values. When compensating the egomotion the dynamic parts of the scene canbe extracted and accumulated in a common coordinate system (right, bird’s eye view).

is caused by vehicles following a street or crossing the intersection. Assuming righthanded traffic and that the majority of traffic participants keep up with the traffic
rules, these flow vectors should be explained by the underlying scene model, i.e. allvehicles are driving on the correct lanes into the right direction.
Towards extracting 3D scene flow vectors f , we first extract feature matches fromthe image sequence. In order to find stable feature locations, we filter the input
images with 5 × 5 blob and corner masks as illustrated in Fig. 4.12(a). Next, we
employ non-maximum- and non-minimum-suppression [143] on the filtered images,
resulting in feature candidates which belong to one of four classes (i.e., blob max,
blob min, corner max, corner min). To reduce computational efforts, only features
within those classes are matched.
In contrast to methods concerned with reconstructions from unordered image collections, here we assume a smooth camera trajectory, superseding computationallyintense rotation and scale invariant feature descriptors like SURF [18, 17], SIFT
[134, 135] or others [34, 33, 158, 132]. We compute a compact 32 byte feature descriptor from the 8 bit quantized horizontal and vertical Sobel responses at the 16
locations shown in Fig. 4.12(b). Since the sum-of-absolute-differences of 16 bytes
can be computed very efficiently using a single SSE instruction we only need two
calls in order to evaluate this error metric.
We match features between the left and right images and between two consecutive
frames. This is achieved by matching features in a ’circle’: Starting from all feature
candidates in the current left image, we find the best match in the previous left image
within a M × M search window, next in the previous right image, the current rightimage and last in the current left image again. A ’circle match’ gets accepted, if thelast feature index coincides with the first feature index. When matching between theleft and right images, we additionally make use of the epipolar constraint using an

59

4. Image Evidence(a) Blob and Corner detector(b) Feature Descriptor

left image(c) Motion Estimationright image

tim

e

Stage
Time
Filter
6.0 ms
12 ms
NMS
Matching 1 2.8 ms
Matching 2 10.7 ms
Refinement 5.1 ms
Total time 36.6 ms(d) Feature Matching(e) Running Time

Figure 4.12.: Feature Matching and Egomotion Estimation. Blob and corner features aredetected with filters (a), described using Sobel filter responses arranged in a star-like shape(b) and matched in two consecutive stereo pairs (d). Egomotion is obtained using the 3-point
algorithm (c). Running times are given in (e).

error tolerance of 1 pixel. For further details3 , the reader is referred to [75].
Given all ’circular’ feature matches from the previous section, we compute thecamera motion by minimizing the sum of re-projection errors using the 3-point algorithm [144, 47, 85]. First, bucketing [110] is applied to reduce the number offeatures (in practice we retain between 200 and 500 features) and spread them uniformly over the image domain. Next, we project the feature points from the previous
frame into 3D via triangulation using the calibration parameters of the stereo camera
rig. Assuming squared pixels and zero skew, the reprojection into the current image
is given by

 

  

 
x
u
f 0 cu s v  =  0 f cv  [R(r), t] y  − 0
(4.26)

z 

1
0 0 1
0
1
with
3

Source code available at: http://www.mrt.kit.edu/software/60

4.4. Scene Flow

• homogeneous image coordinates (u v 1)T• focal length f• principal point (cu , cv )• rotation matrix R(r) = Rx (rx )Ry (ry )Rz (rz )• rotation vector t = (rx ry rz )T• translation vector t = (tx ty tz )T• 3D coordinates x = (x y z)T• and shift s = 0 (left image) or s = baseline (right image)
Let now π l (x; r, t) : R3 → R2 denote the projection implied by Eq. 4.26, whichtakes a 3D point x and maps it onto the left image plane. Similarly, let π r (x; r, t)
be the projection onto the right image plane. Using Gauss-Newton optimization, we
iteratively minimizer̂, t̂ = argmin
r,t

N
X

(l)

yi − π l (xi ; r, t)

2

(r)

+ yi

− π r (xi ; r, t)

(l)

(r)

2

(4.27)

i=1

for the rigid motion parameters r and t. Here, yi and yi denote the feature locations in the current left and right images and xi are the triangulated 3D points fromthe previous frame. The required Jacobians are readily derived from Eq. 4.26. Inpractice, even a simple initialization (r0 = t0 = 0) proved sufficient to converge in
only a couple of iterations (4-8). For robustness with respect to outliers, we wrap
the estimation approach into a RANSAC scheme [62]: We first estimate (r̂, t̂) nf
times independently using 3 randomly drawn correspondences. Afterwards, all inliers of the winning iteration are used for refining the parameters, yielding the final
transformation parameters (r̂, t̂). While more sophisticated methods for structure
and motion estimation could be employed [121, 122], we found the aforementioned
procedure to be simple and accurate enough for our purpose.
The final step is to compensate the 3D scene flow vectors using the egomotion
given by the transformation parameters {(r̂, t̂)} over time. Towards this goal, we
accumulate all vectors in the coordinate system of the last frame of the sequenceand threshold them by their length, i.e., we remove short vectors that are likely tobelong to the static environment. As the 3D scene flow likelihood doesn’t accountfor object velocities, we normalize all flow vectors to unit length and project them
onto the estimated road plane as illustrated in Fig. 4.11 (right), yielding the scene
flow features F = {f1 , . . . , fNf } which are modeled by the scene flow likelihoodin Section 3.3.5.

61

4. Image Evidence

Figure 4.13.: Occupancy Grid. From the input disparity maps of a T-intersection (left), we
compute evidence for static obstacles and free space in bird’s eye view, and accumulate it overtime in a common coordinate system (right, top view). Here, white denotes obstacle, black is
free space and gray represents unobserved areas.

4.5. Occupancy Grid
Buildings represent obstacles in the scene and thus should never coincide with drivable regions (road). This assumption is incorporated into the occupancy grid feature.
We construct a 2D voxel grid in road plane coordinates from disparity measurements.
The grid classifies the area in front of the vehicle into the categories obstacle, freespace and unobserved segments as illustrated in Fig. 4.13.
For stereo matching we propose the efficient large-scale stereo matcher ELAS4[73], that is capable of computing disparity maps at large image resolutions in realtime on the CPU. The method is inspired from the observation that despite thefact that many stereo correspondences are highly ambiguous, some of them canbe robustly matched. Assuming piecewise smooth disparities, such reliable ’support points’ carry valuable prior information for the estimation of the remaining,ambiguous disparities in between. First, the disparities of a sparse set of support
points are computed using the full disparity range. The image coordinates of the
support points are then used to create a 2D mesh via Delaunay triangulation. Fromthe mesh, a piecewise linear prior is computed to disambiguate the matching problem and increasing the efficiency by restricting the search to a plausible subspace.
The algorithm automatically determines the disparity range, can be easily parallelized and has shown impressive performance on the realistic KITTI dataset [71]and on the large-scale Middlebury benchmark [165] while at the same time achieving significant speedups with respect to competing methods. Two matching results
are illustrated in Fig. 4.13 (left). For a more in-depth discussion on the algorithm,
the reader is referred to [73].
Given the disparity maps for all frames of the sequence, we compute a 2D occupancy grid [178] of the environment, representing obstacles and drivable (road)4

Source code available at: http://www.mrt.kit.edu/software/62

4.5. Occupancy Grid

areas. Using the visual odometry approach described in Section 4.4, we represent all
dynamic and static features in the bird’s eye perspective of the last frame’s camera
coordinate system.
More formally, let O = {ρ1 , . . . , ρNo } be the occupancy grid map with ρi denoting if the i’th cell is free (ρi = −1) or occupied (ρi = +1). Let the probability of an occupied grid cell be denoted by p(ρi ) ≡ p(ρi = +1). Further, let
D = {D1 , . . . , DT } denote the set of all disparity maps, with Di the disparity mapof the i’th frame. Assuming the odometry estimates to be known, we are interested
in computing the posterior p(O|D). To make computations tractable the individual
cells are assumed to be independent conditioned on the measurements D, yieldingp(O|D) =NoY

p(ρi |D)(4.28)

i=1

As this is a binary static state estimation problem, the discrete Bayes filter can beapplied to p(ρi |D). For ease of computation and numerical stability, we follow [178]and make use of the log-odds representationp(ρ|D)
p(ρ|D)= logp(¬ρ|D)
1 − p(ρ|D)
exp l(ρ|D)
p(ρ|D) =1 + exp l(ρ|D)
l(ρ|D) = log(4.29)(4.30)

where we have dropped the grid cell index i for clarity. Let Dt = {D1 , . . . , Dt }denote the set of disparity observations till time t. The recursive filter update gives
rise top(ρ|Dt )p(Dt |ρ, Dt−1 )p(ρ|Dt−1 )=p(¬ρ|Dt )p(Dt |¬ρ, Dt−1 )p(¬ρ|Dt−1 )p(Dt |ρ)p(ρ|Dt−1 )=×p(Dt |¬ρ)p(¬ρ|Dt−1 )(4.31)or – equivalently – in log-odds representationl(ρ|Dt ) = l(Dt |ρ) + l(ρ|Dt−1 )Here, l(Dt |ρ) takes the form
 +1 if cell ρ is not occluded−1 if cell ρ is occluded for < 5ml(Dt |ρ) =
0 otherwise (> 5m)(4.32)(4.33)

where the occlusion state of a cell ρ at time t is computed by tracing rays from thecamera into the direction of ρ. If an obstacle higher than 2 meters from the ground63

4. Image Evidence

plane is hit before the cell is reached, the cell is called occluded. Note that we only
assign negative log-odds to cells within a 5 meter margin as no information about
the region behind an obstacle is available (gray areas in Fig. 4.13, right). The minimum height requirement alleviates the problem of clutter produced by other traffic
participants which are (typically) of limited height. Ray tracing on the occupancy
grid can be performed efficiently using the Bresenham algorithm [26]. The last steprounds all occupancy grid cells to ρ ∈ {−1, 0, +1}, yielding the final occupancy
grid O = {ρ1 , . . . , ρNo } which is modeled with the occupancy grid likelihood from
Section 3.3.6.

64

5. Experimental Evaluation
The dataset used in the experimental section of this thesis is part of an early versionof the KITTI vision dataset [71, 70], which has been recorded from a VW Passat
station wagon [68, 106] (established in the context of the SFB/Transregio 28 special
research field and illustrated in Fig. 5.1) while driving around Karlsruhe, Germany.
Our setup includes camera images, laser scans, high-precision GPS measurements
and IMU accelerations/angular velocities from a combined GPS/IMU system. The
main purpose of this dataset is to push forward the development of computer visionand robotic algorithms targeted to dynamic inner-city and freeway scenes. From
the recorded data1 we have extracted benchmarks for different tasks such as stereo,
optical flow, visual odometry, SLAM, 3D object detection and 3D tracking [71]. Fora review on related datasets and evaluation efforts, the reader is referred to [71].
5.1. System Setup
Our sensor setup, illustrated in Fig. 5.1, is as follows:• 2 × PointGray Flea2 grayscale cameras (FL2-14S3M-C), 1.4 Megapixels,
1/2" Sony ICX267 CCD, global shutter• 2 × PointGray Flea2 color cameras (FL2-14S3C-C), 1.4 Megapixels, 1/2"
Sony ICX267 CCD, global shutter• 4 × Edmund Optics lenses, 4mm, opening angle ∼ 90◦ , vertical opening
angle of region of interest (ROI) ∼ 35◦• 1 × Velodyne HDL-64E rotating 3D laser scanner, 10 Hz, 64 beams, 0.09
degree angular resolution, 2 cm distance accuracy, collecting ∼ 1.3 million
points/second, field of view: 360◦ horizontal, 26.8◦ vertical, range: 120 m• 1 × OXTS RT3003 inertial and GPS navigation system, 6 axis, 100 Hz, L1/L2
RTK, resolution: 0.02m / 0.1◦
As color cameras are less sensitive to light we use two stereo camera rigs, one forgrayscale and one for color. The baseline of both stereo camera rigs is approximately
54 cm and the calibration between all sensors is known. In the early setup used forthe intersection subset of KITTI, we only had access to a monochrome video camera
1

The dataset can be downloaded from: http://www.mrt.kit.edu/software/datasets.html

65

5. Experimental Evaluation

Velodyne HDL-64E Laserscanner
Point Gray Flea 2
Video Cameras

z
x
y
x
z y

z
y
x OXTSOXTSRTRT 3003GPS
GPS / IMU(a) Karlsruhe, Germany(b) Experimental Vehicle AnnieWAY (MRT/KIT)All heights wrt. road surface
All camera heights: 1.65 m
Cam 1 (gray)Cam 3 (color)

Wheel axis
(height: 0.30m)

0.54 m1.60 m0.06 mCam-to-CamRect& CamRect-to-ImageCam 0 (gray)Cam 2 (color) z

1.68 m0.80 m0.06 mVelodyne laserscanner(height: 1.73 m)

x
x
y

z
y

Velo-to-Cam

0.05 m

IMU-to-Velo

GPS/IMU x(height: 0.93 m)

0.27 m0.81 m0.32 mzy0.48 m2.71 m(c) Sensor Setup (Top View)

Figure 5.1.: Recording Platform. A VW Passat station wagon has been equipped with four
video cameras (two color and two gray scale cameras). A rotating 3D laser scanner and a
GPS/IMU inertial navigation system unit have been installed for obtaining ground truth annotations.

stereo rig and an GPS/IMU system for localization. The trunk of our vehicle houses
a PC with two six-core Intel XEON X5650 processors and a shock-absorbed RAID
5 hard disk system, storing up to 4 terabytes. Our computer runs Ubuntu Linux (64bit) and a database for cognitive automobiles [80] to store the incoming data streams
in real-time.
5.2. Sensor Calibration
We took care that all sensors are carefully synchronized and calibrated [72, 150]. To
avoid drift over time, we calibrated the sensors at each day of our recordings. The
66

5.2. Sensor Calibration

coordinate systems are defined as illustrated in Fig. 5.1, i.e.:• Camera: x = right, y = down, z = forward• Velodyne: x = forward, y = left, z = up
• GPS/IMU: x = forward, y = left, z = up
5.2.1. Synchronization
In order to synchronize the sensors, we use the timestamps of the Velodyne 3D laser
scanner as a reference and consider each spin as a single frame. We mounted a reed
contact at the bottom of the continuously rotating scanner, triggering the cameras
when it is facing forward. This minimizes the differences in range and image observations caused by dynamic objects. Unfortunately, the GPS/IMU system cannot be
synchronized that way. However as it provides updates at 100 Hz, we collect the datawith the closest time stamp to the laser scanner time stamp for a particular frame.
The remaining worst-case time difference of 5 ms can be taken into account by comparing the corresponding timestamps which are provided for each sensor modality.
5.2.2. Camera Calibration
For calibrating the cameras intrinsically and extrinsically, we use the approach proposed in [72], which delivers all calibration and rectification parameters fully automatically after only a couple of minutes processing. While our cameras are fixedwith respect to the vehicle body, flexible arrangements could be dealt with using
self-calibration methods [46]. Note that the focal points of all cameras are alignedon the same x/y−plane. This is important as it allows us to rectify all cameras
jointly. The calibration parameters are:• s(i) ∈ N2 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Original image size (1392 × 512)
• K(i) ∈ R3×3 . . . . . . . . . . . . . . . . . . . . . . . . . . Calibration matrices (unrectified)• d(i) ∈ R5 . . . . . . . . . . . . . . . . . . . . . . . . . . . Distortion coefficients (unrectified)• R(i) ∈ R3×3 . . . . . . . . . . . . . . . . . . . . . . . . Rotation from camera 0 to camera i• t(i) ∈ R1×3 . . . . . . . . . . . . . . . . . . . . . . Translation from camera 0 to camera i(i)• srect ∈ N2 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Image size after rectification(i)• Rrect ∈ R3×3 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Rectifying rotation matrix(i)• Prect ∈ R3×4 . . . . . . . . . . . . . . . . . . . . . . . Projection matrix after rectification
675. Experimental Evaluation

Here, i ∈ {0, 1, 2, 3} is the camera index, where 0 is the left gray scale, 1 the rightgray scale, 2 the left color and 3 the right color camera. The variable definitions
are compliant with the OpenCV library [23], which has been used for warping theimages. After rectification, only the variables with rect-subscripts are relevant. Notethat due to the pincushion distortion effect the images have been cropped such thatthe size of the rectified images is slightly smaller than the original size of 1392×512
Pixels.
The projection of a 3D point in rectified camera coordinates x = (x, y, z, 1)T to
a point y = (u, v, 1)T in the i’th image is given as(i)y = Prect x
with

 (i)
(i) (i) (i)
0 cu −fu bx
fu
(i)
(i)

0 fv cv
0
0
0
1
0

(i)
Prect = 

(5.1)

(5.2)

(i)

the i’th projection matrix. Here, bx denotes the baseline (in meters) with respect toreference camera 0. In order to project a 3D point x in reference camera coordinates
to a point y on the i’th image plane, the rectifying rotation matrix Rrect
cam must be
considered as well:
(i)
(5.3)
y = Prect Rrect
cam x
(0)

rect
with Rrect
cam = Rrect as camera 0 serves as reference. Here, Rcam has been expanded to a 4 × 4 matrix by appending a fourth zero-row and column and setting
Rrect
cam (4, 4) = 1.

5.2.3. Velodyne and IMU Calibration
The Velodyne laser scanner has been registered with respect to the reference camera coordinate system by initializing the rigid body transformation using the method
proposed in [72]. Additionally, we have optimized an error criterion based on the Euclidean distance of 50 manually selected correspondences and a robust measure on
the disparity error with respect to the 3 top performing stereo methods in the KITTI
stereo benchmark [71]. The optimization has been carried out using MetropolisHastings sampling, yielding the rigid body transformation Tcam
velo . A 3D point x in
Velodyne coordinates gets then projected to a point y in the i’th camera image via(i)camy = Prect Rrect
cam Tvelo x(5.4)

where Tcam
velo denotes the rigid transformation between the laser scanner and the reference camera coordinate system.
For registering the IMU/GPS with respect to the Velodyne laser scanner, we drove
an ’∞’-loop and registered the point clouds using the Point-to-Plane ICP algo68

5.2. Sensor Calibration

Figure 5.2.: Illustration of the Dataset. This figure depicts 18 out of the 113 sequences used
for evaluation of the presented method. Note the complexity and diversity in scene layout,
dynamic objects and appearance.
69

5. Experimental Evaluation

Figure 5.3.: Intersection Annotation Utility. The annotation of the 113 sequences withground truth information has been carried out with an OpenGL tool, that displays image sequences, trajectories, GoogleMaps images and labeled intersections in bird’s eye perspective.

rithm. Given two trajectories this problem corresponds to the well-known handeye-calibration problem which can be solved using standard tools [99], yielding therigid body transformation Tvelo
imu . A 3D point x in IMU/GPS coordinates can thenbe projected to y in the i’th image using
(i)

cam
velo
y = Prect Rrect
cam Tvelo Timu x(5.5)

Note that the Velodyne sensor only serves as a reference and is not used in our experiments in Chapter 5. However, we have included it here for completeness.
5.3. Data Collection and Annotation
For the experiments conducted in this thesis 113 realistic video sequences have beenrecorded with a duration of 5 to 30 seconds each, featuring straights, 3-armed and 470

5.4. Experimental Results

armed intersection scenarios. Each sequence captures the moment of approachingan intersection or waiting in front of a red traffic light. All sequences are manually clipped at the moment the intersection is entered as this is the time when an
autonomous system would need to take a decision. Note that this would also be
possible in an automatic manner using approximate maps and state-of-the-art localization techniques [29]. Fig. 5.2 depicts a couple of sequences from our dataset.
Note the large variability in terms of scene layout and dynamic objects present in
the scene.
The annotation of the data has been carried out using GoogleMaps aerial images.
For each intersection in the database we labeled the center of the intersection as wellas the number, orientation and width of the intersecting streets in bird’s eye perspective. A screen shot of our OpenGL annotation tool is shown in Fig. 5.3. Afterwards,
the annotated geometry is mapped into the road coordinate system using the GPS
coordinates of the vehicle, the road plane estimate and the calibration parametersdescribed in the previous section. Fig. 5.6 shows the variability in terms of roadlayouts (red) in our dataset.
Additionally, we annotated all vehicle tracklets that have been detected by theapproach described in Section 4.1 with the index (l) of the corresponding lane orparking area. For vehicles that have been associated to a lane, the tangent at theclosest foot point of lane l is used as object orientation ground truth. Furthermore,
we manually annotate all lanes in each scenario with a binary label indicating if thelane is ’active’ or not, i.e., if moving vehicles on that lane can be observed or not.
5.4. Experimental Results
Our experiments target at evaluating the overall performance as well as the importance of each individual feature cue for the different tasks, which are detailed in thefollowing sections. Let us define the following feature abbreviations
P = Prior (see Section 3.3.1)
T = Tracklets (see Section 3.3.2)
V = Vanishing Lines (see Section 3.3.3)
S = Semantic labels (see Section 3.3.4)
F = Scene Flow (see Section 3.3.5)
O = Occupancy Grid (see Section 3.3.6)
which allow for easy indexing of the prior and the feature cues. To gain insights
into the strengths and weaknesses of each term in the proposed model, we conduct
experiments using the following feature combinations71

5. Experimental Evaluation

P . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Prior only
PT, PV, PS, PF, PO . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Single term
PVSFO, PTSFO, PTVFO, PTVSO, PTVSF . . . . . . . . . . All terms but one
PTVSFO . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Full modeli.e., we evaluate the prior without any image cues, the prior in combination with asingle feature term, all feature terms but one and the full model including all terms
from Section 3.5.2. For each of these settings a separate set of parameters Θ maximizing the respective probability distribution is learned.
5.4.1. Learning the Model Parameters
Due to the relatively small number of sequences in the dataset, we leverage 10-foldcross-validation to evaluate the proposed method: We hold out every 10’th data
point (i.e., sequence) for evaluation when training the model parameters Θ using
the approach described in Section 3.5.2. Fig. 5.4 and Fig. 5.5 depict the learning
curves of the first fold for each feature term combination. For fitting all curves into asingle plot, all values have been normalized to the interval [0, 1]. In contrast to classical gradient ascent methods, our gradients are noisy due to the non-deterministic
nature of the Markov chains that run within the learning procedure. Nevertheless,convergence typically occured after 150-250 gradient ascent steps. During the final iterations of the learning procedure we reduce the learning rate η step-by-step toforce all parameters to settle at their final values.
Note that for the prior parameters we slightly deviate from the derivations in Section 3.5.2 and only optimize a scalar precision parameter that we multiply with the
maximum-likelihood estimate of the precision matrix. Empirically we found thisto perform equally well compared to the full optimization while at the same time
being significantly faster and more stable to optimize. Similarly, the mean vector
is obtained using maximum-likelihood and kept constant during optimization. Furthermore, we exclude ζt , ζv and ζf from the optimization as these parameters are
difficult to optimize and can be easily chosen based on empiric reasoning. All parameters which are not part of Θ and thus not optimized for are summarized in Table
5.1 for reproducibility of the results.
5.4.2. Expressive Power and Generality
To accommodate for the noise in the features and the difficult nature of the estimation problem in general, the proposed geometric model from Section 3.1 is simplified in a sense that it forces opposing streets to be collinear and all streets to sharethe same width. To justify this approximation and demonstrate the applicabilityof the proposed intersection model to real-world scenes, we fit the model parameters R = {κ, c, w, r, α} to the true intersection layouts that have been annotatedusing GoogleMaps images and compare the road area overlap. This leads to an ’oracle’ measure of the maximum performance that can be achieved with our model72

5.4. Experimental Results

1

1

0.5

λp1

λp1

0.5

λp2

λp2

λp3

λp3
λp4

0

λp5

λ

p4

0

λ

p5

λ

p6

λp6
λp7

−0.5
−1

100

200 300
Iteration

400

λ

p7

−0.5
−1

500

λt

100

(a) P

200 300
Iteration

400

500

(b) PT

1

1
λp1

0.5

λ

λp1

0.5

λ

p2

p2

λ

λ

λp4

λp4

p3

0

λp5

p3

0

λp5

λ

λ

p6

p6

λ

λ

p7

−0.5
−1

λv

100

200 300
Iteration

400

p7

−0.5
−1

500

λs

100

(c) PV

200 300
Iteration

400

500

(d) PS

1

1
λp1

0.5

λp2

λp1

0.5

λ

p2

λp3

λ

p3

λp4
λp5

0

λp6

λp4

0

λp5
λ

p6

λp7
λf1

−0.5
−1

λf2

100

200 300
Iteration(e) PF

400

500

λ

p7

−0.5
−1

λo

100

200 300
Iteration

400

500

(f) PO

Figure 5.4.: Learning the Model Parameters. This figure depicts the evolution of the parameters Θ over the number of gradient ascent steps for each of the settings from Section 5.4.

73

5. Experimental Evaluation

1

λp1

1

λp1

λp2
λp3

0.5

λp4

λp2
λp3

0.5

λp4

λp5

λp5

λ

p6

0

λ

p7

λ

p6

0

λ

p7

λ

λ

λ

λ

v

t

s

−0.5

λ

f1

s

−0.5

λ

f1

λ

λ

λ

λ

f2

f2

o

−1

100

200 300
Iteration

400

o

−1

500

100

(a) PVSFO

200 300
Iteration

400

500

(b) PTSFO

1

λ

1

p1

λp1

λp2
λp3

0.5

λ

λp2

0.5

λp3

p4

λp4

λp5
λp6

0

λp7

λp5
λp6

0

λp7

λt

λt

λ

v

−0.5

λf1

λv

−0.5

λ

s

λf2

λo

λo

−1

100

200 300
Iteration

400

−1

500

100

(c) PTVFO

200 300
Iteration

400

500

(d) PTVSO

1

λp1

1

λp1
λp2

λ

p2

λp3

0.5

λ

λp3

0.5

λp4

p4

λp5

λp5
λp6

0

λp7

λp6
λp7

0

λt

λt

λv

λ

v

−0.5

λs

λs

−0.5

λ

f1

λf1

λf2

λf2

−1

100

200 300
Iteration(e) PTVSF

400

500

−1

λo

100

200 300
Iteration

400

500

(f) PTVSFO

Figure 5.5.: Learning the Model Parameters. This figure depicts the evolution of the parameters Θ over the number of gradient ascent steps for each of the settings from Section 5.4.

74

5.4. Experimental Results

Prior: (Section 3.3.1)
σα = 0.1 rad
KDE kernel bandwidth
Vehicle Tracklets: (Section 3.3.2 and Section 4.1)
τd = 0.2
NMS overlap threshold (object detection)
τt1 = 0.5
Gating threshold (tracking stage 1)
τt2 = 0.3
Gating threshold (tracking stage 2)
ζt = 10−20
Outlier threshold
σout = 70 m
Std. deviation of outlier distribution
Vanishing Points: (Section 3.3.3)
ζv = 10−10
Outlier threshold
Semantic Scene Labels: (Section 3.3.4 and Section 4.3)
ns = 4 Px
Image patch (superpixel) size
ws = (1, 1, 4)
Scene label weights
Scene Flow: (Section 3.3.5 and Section 4.4)
nf = 50
Number of RANSAC samples
ζf = 10−15
Outlier threshold
σout = 70 m
Std. deviation of outlier distribution
Occupancy Grid: (Section 3.3.6 and Section 4.5)
no = 1 m
Occupancy grid cell size
wo = (−1, 4, 1)
Weights of geometric prior∆o = (2, 20) m
Margins of geometric prior
Inference and Learning: (Section 3.4 and Section 3.5)
ninf er = 10, 000
Number of samples drawn at inference
nlearn = 10
Number of samples per learning iteration
niter = 500
Number of learning iterations
Sampling: (Table 3.1)
σc ∈ {0.5, 5.0} m
Proposal std. deviation (center)σw ∈ {0.5, 5.0} m Proposal std. deviation (street width)σα ∈ {0.02, 0.2} rad Proposal std. deviation (crossing angle)
σr ∈ {0.01, 0.1} rad Proposal std. deviation (rotation)
Table 5.1.: Constants. This table shows the setting of all constants in our model. All values
have been kept fix throughout all experiments reported in this thesis.

75

5. Experimental Evaluation

99.5 %

99.5 %

99.4 %

99.2 %

99.1 %

99.0 %

99.0 %

98.9 %

98.3 %

98.2 %

98.1 %

98.0 %

97.9 %

97.5 %

97.5 %

97.4 %

96.9 %

96.8 %

96.6 %

96.4 %

96.1 %

95.3 %

94.5 %

93.6 %

93.3 %

93.3 %

93.2 %

92.8 %

92.5 %

92.0 %

90.6 %

90.5 %

90.5 %

90.4 %

87.6 %

87.6 %

87.6 %

87.4 %

85.7 %

85.7 %

85.6 %

85.0 %

84.8 %

83.2 %

98.8 %

98.3 %

97.3 %

97.2 %

94.3 %

93.8 %

93.8 %

92.2 %

92.1 %

92.1 %

92.0 %

90.1 %

89.2 %

88.7 %

88.2 %

88.2 %

86.5 %

86.3 %

86.2 %

86.1 %

86.1 %

86.1 %

85.6 %

85.4 %

85.4 %

85.4 %

85.4 %

85.4 %

85.4 %

84.7 %

84.7 %

84.7 %

84.5 %

84.4 %

84.4 %

83.6 %

83.4 %

83.1 %

82.9 %

82.9 %

81.7 %

78.6 %

77.9 %

77.9 %

77.7 %

77.7 %

77.6 %

77.5 %

77.1 %

77.1 %

77.0 %

77.0 %

77.0 %

76.9 %

76.4 %

76.3 %

76.0 %

76.0 %

75.8 %

72.4 %

72.4 %

71.3 %

70.5 %

70.4 %

69.2 %

69.1 %

68.9 %

67.5 %

67.5 %

Figure 5.6.: Expressive Power of the Geometric Model. This figure illustrates the generalityof the restricted geometric model presented in Section 3.1 (blue) with respect to the groundtruth road layout (red). All 113 intersections from our dataset are shown, sorted by decreasing
overlap. As expected, straight roads can be approximated best, while X-crossings sometimes
appear in more esoteric shapes. Overall, the simplified model provides a good approximation
to the true intersection layout.

76

5.4. Experimental Results

when assuming complete and perfect observations. For each scene, we maximize
the overlapping road area using iterative non-linear optimization on the intersectionover-union criterionR̂ = argmax
Rroad(R, w̄) ∩ road(G, w̄)road(R, w̄) ∪ road(G, w̄)
|
{z
}

(5.6)

overlapping road area

where road(·, d) is a function that returns the road region clipped at distance d fromthe intersection center c, w̄ is the average street width, R is the simplified modeland G denotes the ground truth layout.
Fig. 5.6 shows the results of this optimization, ordered by decreasing overlap.
The ground truth and the simplified intersection layout are shown in red and blue,
respectively. The average overlap on all 113 sequences is 86.9%. Given the fact that
preliminary experiments [69, 74] indicate an expected performance between 45%
and 60%, and that the street width is often hard to observe or not observable at all(e.g., due to the low camera viewpoint and clutter), the geometric approximations
seem justified. For the vast majority of intersection geometries in Fig. 5.6 the simplified model in blue is a good approximation to the full model, illustrated in red, yet
it can be described with a significantly smaller amount of parameters. Note that the
113 scenarios under consideration are chosen at random from real-world test runs
and are representative for the distribution of intersection layouts in Karlsruhe.
5.4.3. Sampling from the Road Layout Prior
To confirm the quality of the learned road layout prior p(R; Θ) we draw 120 random samples from it using the parameter set Θ from training fold one. The resulting
samples are depicted in Fig. 5.7 using the same axis limits for each subplot. As evidenced by this experiment, the synthesized intersections exhibit different topologies,
locations, scales and street orientations. Qualitatively, the samples resemble naturalintersections well. The impact of including this prior knowledge into the inference
process is evaluated quantitatively in Section 5.4.4. Note that simple left or rightturns (κ ∈ {2, 3}) have not been observed in our dataset which is also reflected by
the samples from the prior.
5.4.4. Topology and Geometry
To judge the performance of the proposed model, we evaluate the estimation resultsof each setting against several metrics. First, we measure the accuracy in topology
estimation, which is the percentage of all 113 cases in which the correct topology κ
has been recovered. Furthermore, we propose three geometric metrics: We computethe average Euclidean error in estimating the center of the intersection, the average
street orientation error and the road area overlap.
77

5. Experimental Evaluation

Figure 5.7.: Samples from the Prior. This figure shows 120 random samples from the learned
prior p(R) in road coordinates (y = 0), using the same axis limits in each plot: x ∈ [−75, 75]
and z ∈ [−50, 100]. For clarity, only the left and right road boundaries are shown here.

785.4. Experimental Results

Regarding the street orientation, we assign each street to its (rotationally) closest
counterpart in the ground truth layout in order to decouple the orientation measurefrom the estimated topology κ. More precisely, we take the layout with the smaller
number of streets and assign all streets to their closest counterparts in the layout withthe larger number of streets. Consider for example a three-way intersection that has
been recovered as a four-way intersection or vice versa. If all street orientations havebeen estimated correctly except for the one that does not exist in the other layout theorientation error is not affected as desired. On contrary, a street that is part of thecorrect layout but is estimated badly in terms of orientation increases the error.
Finally, the road area overlap measures how much the estimated road layout overlaps with the ground truth layout by computing the intersection-over-union of bothroad areas. For this evaluation we make use of the measure introduced in Eq. 5.6 in
Section 5.4.2. Note that the accuracy is upper bounded by the oracle results depicted
in Fig. 5.6 due to the simplified geometric model.
All metrics have been evaluated for each setting and the results are depicted inTable 5.2 (row 1 to 4). The corresponding topology confusion matrices are shown in
Fig. 5.8. As evidenced by the experiments, each feature is able to improve the resultscompared to using prior information alone (column 1-6). The strongest cues in ourframework are vehicle tracklets, 3D scene flow and the occupancy grid features. This
indicates that despite its noisy nature, depth information is important for solving
the problem. The smallest gain in performance is observed for the vanishing point
feature. This is because this feature cue only works in combination with other cues as
it only allows for ’fine tuning’ the street orientations but does not directly influence
the existence of a street.
Additional performance gains can be achieved when combining the feature cues.
In terms of topology estimation, the best results have been obtained by making us of
all information. Without the semantic scene label cue, the geometric error measures
can be slightly improved. While these differences are only marginal, our experiments suggest that the semantic scene label cue is the weakest when considered in
combination with all the other cues. In contrast, important information is comingfrom the occupancy grid. Removing this cue significantly impacts the performance,
especially in terms of topology and road area estimation, but also regarding the intersection location and street orientation errors. We believe that this is because occupancy information is most complementary to the other cues, while 3D scene flow
and vehicle tracklets can partly replace each other.
Note that our learning procedure described in Section 3.5.1 has no access to themetrics we employ here. Instead, it directly maximizes the likelihood of the datawith respect to the proposed model. Thus, errors and uncertainties in the groundtruth labeling impact performance and explain the differences between the models.

79

5. Experimental Evaluation

7 Object Orient. Err. (deg, ↓) 53.0 17.7 54.4 45.1 17.5 24.2 14.0 15.1 14.9

6 Lane Accuracy (%, ↑)5 Tracklet Accuracy (%, ↑)4 Road Area Overlap (%, ↑)3 Street Orient. Err. (deg, ↓)2 Location Error (m, ↓)1 Topology Accuracy (%, ↑)77.3 90.3 78.0 80.2 90.5 85.2 89.7 89.4 89.8

28.1 78.7 30.0 35.8 79.2 65.1 80.7 80.3 79.8

33.1 51.0 32.9 41.2 53.6 63.4 69.3 69.7 71.2

8.7

6.8
5.4

5.1
8.7

6.7

7.3

7.9

5.2

4.5

5.1

4.0

3.6

3.0

3.6

2.9

3.6

2.7

15.4

88.3

77.6

68.9

3.6

3.1

73.7

15.1

90.2

81.6

57.5

4.7

4.8

74.0

14.3

89.7

82.0

69.9

3.6

3.0

PVS PTS PTV PTV PTV PTVPPT PV PSPF PO
FO FO FOSO
SF
SFO
19.5 64.6 20.3 55.8 66.4 83.2 91.1 89.4 91.1 90.3 72.6 92.0

Prior
Tracklets
Vanishing Lines
Semantic labels
Scene Flow
Occupancy Grid

74.1
=
=
=
=
=
=

8 Object Detection AP (%, ↑) 73.6 73.7 73.7 73.1 73.6 74.1 74.1 74.1 74.2
P
T
V
S
F
O

Table 5.2.: Quantitative Results. This table shows our inference results quantitatively and compares the different settings described in Section 5.4.
The metrics are displayed in the left column, with the measurement unit and the metric order in brackets. Regarding the order, ↑ means higher isbetter and ↓ means lower is better. All numbers represent averages over all 113 shots used in our evaluation.

80

0

0

0

0

0

0

1 20

0

0

0

0

0

2

1 20

0

0

0

0

0

2

2 0

0

0

0

0

0

0

2 0

0

0

0

0

0

0

2 0

0

0

0

0

0

0

3 0

0

0

0

0

0

0

3 0

0

0

0

0

0

0

3 0

0

0

0

0

0

0

4 13

0

0

0

0

0

0

4 1

0

0

0

0

0

12

4 11

0

0

0

0

0

2

5 6

0

0

0

0

0

0

5 2

0

0

0

0

0

4

5 5

0

0

0

0

0

1

6 1

0

0

0

0

0

0

6 0

0

0

0

0

0

1

6 1

0

0

0

0

0

0

7 71

0

0

0

0

0

0

7 18

0

0

0

0

0

53

7 68

0

0

0

0

0

3

2 3 4 5 6 7
Estimated Topology

1

2 3 4 5 6 7
Estimated Topology

1

1

0

0

0

0

1

1 22

0

0

0

0

0

0

1 22

0

0

0

0

0

0

0

0

0

0

0

0

2 0

0

0

0

0

0

0

2 0

0

0

0

0

0

0

3 0

0

0

0

0

0

0

3 0

0

0

0

0

0

0

3 0

0

0

0

0

0

0

4 5

0

0

0

0

0

8

4 0

0

0

0

0

0

13

4 1

0

0

11

0

0

1

5 3

0

0

0

0

0

3

5 4

0

0

0

0

0

2

5 2

0

0

2

0

0

2

6 0

0

0

0

0

0

1

6 0

0

0

0

0

0

1

6 0

0

0

0

0

0

1

7 29

0

0

0

0

0

42

7 17

0

0

1

0

0

53

7 8

0

0

2

0

0

61

2 3 4 5 6 7
Estimated Topology

1

2 3 4 5 6 7
Estimated Topology

1

True Topology02 0(d) PS

2 3 4 5 6 7
Estimated Topology(e) PF(f) PO

0

0

0

0

1

0

1 22

0

0

0

0

0

0

1 22

0

0

0

0

0

0

2 0

0

0

0

0

0

0

2 0

0

0

0

0

0

0

2 0

0

0

0

0

0

0

3 0

0

0

0

0

0

0

3 0

0

0

0

0

0

0

3 0

0

0

0

0

0

0

4 0

0

0

13

0

0

0

4 0

0

0

11

0

0

2

4 0

0

0

12

0

0

1

5 2

0

0

0

1

0

3

5 1

0

0

1

1

0

3

5 2

0

0

0

1

0

3

6 0

0

0

1

0

0

0

6 0

0

0

0

0

0

1

6 0

0

0

1

0

0

0

7 2

0

0

1

0

0

68

7 2

0

0

1

1

0

67

7 2

0

0

0

1

0

68

2 3 4 5 6 7
Estimated Topology

1

2 3 4 5 6 7
Estimated Topology

11(g) PVSFO

True Topology

1 21

True Topology(h) PTSFO

2 3 4 5 6 7
Estimated Topology(i) PTVFO

0

0

0

0

0

0

1 22

0

0

0

0

0

0

1 22

0

0

0

0

0

0

2 0

0

0

0

0

0

0

2 0

0

0

0

0

0

0

2 0

0

0

0

0

0

0

3 0

0

0

0

0

0

0

3 0

0

0

0

0

0

0

3 0

0

0

0

0

0

0

4 0

0

0

13

0

0

0

4 0

0

0

3

0

0

10

4 0

0

0

13

0

0

0

5 1

0

0

0

2

0

3

5 1

0

0

1

1

0

3

5 1

0

0

0

2

0

3

6 0

0

0

1

0

0

0

6 0

0

0

0

0

0

1

6 0

0

0

1

0

0

0

7 3

0

0

1

2

0

65

7 11

0

0

3

1

0

56

7 2

0

0

1

1

0

67

2 3 4 5 6 7
Estimated Topology

1

2 3 4 5 6 7
Estimated Topology

11(j) PTVSO

True Topology

1 22(k) PTVSF

True Topology

True Topology(c) PV

1 21

1True Topology

2 3 4 5 6 7
Estimated Topology(b) PT

True Topology

True Topology(a) P

True Topology

1 22

True Topology

True Topology

5.4. Experimental Results

2 3 4 5 6 7
Estimated Topology(l) PTVSFO

Figure 5.8.: Topology Confusion Matrices. This figure depicts the confusion matrices foreach setting, with estimated topologies and true topologies at the x- and y-axis, respectively.

81

5. Experimental Evaluation

5.4.5. Tracklet Associations and Semantic Activities
Besides the geometric reasoning discussed so far, an important aspect in real-world
applications is to understand the scene at a higher level. This includes the associationof vehicle tracklets to lanes (’Tracklet Accuracy’ in Table 5.2) as well as the detectionof active lanes (’Lane Accuracy’ in Table 5.2). With active we refer to lanes thathave the right of way, i.e., where the green light is turned on in the case of signalizedintersections. Note that we are able to infer such information merely by looking at
the dynamic objects in the scene. No detection and recognition of traffic lights isrequired and the state of traffic lights facing towards the other streets are recovered
as well.
For evaluating the above mentioned metrics we extract all unique tracklets. We
define a tracklet as unique if it has a minimum tracklet length of 10 meters and if it
has been uniquely assigned to one of the lanes, where uniqueness is measured by the
distance of the most likely lane to the second likely in terms of their log-likelihood
log p(t|l, R) as defined in Eq. 3.12. For all unique tracklets, we evaluate the accuracy in tracklet-to-lane association as well as the accuracy in detecting active lanes.
We define a lane as active if at least one tracklet has been uniquely assigned to it.
Note that we assign the tracklets to the closest lanes in the ground truth layout toaccount for the fact that the model topology κ might have been wrongly estimated.
This is similar to the street orientation evaluation in the previous section and decouples the error metrics from other parameters.
The tracklet and lane accuracies for all settings are depicted in Table 5.2 (rows
5 and 6). As expected, the best results are obtained in all cases where either the
3D scene flow or the vehicle tracklet features are included in the model, with 80%
accuracy in tracklet associations and 90% accuracy in the active lane detection experiment. While the boost in tracklet accuracy performance is dramatic compared
to using prior knowledge alone (28% accuracy), lane accuracy increases from 77%
to 90%. The reason is that most of the lanes are inactive, hence strongly biasing
the dataset. However, note that the improvements by our model still correspond to a
relative error reduction of over 50%.
5.4.6. Object Orientation Estimation
The estimated object orientations that serve as input to our tracklet model in Section
3.3.2 are noisy as evidenced by the confusion matrix in Fig. 4.2. In fact, the averageorientation error made by the object detector described in the previous section is 32.6
degrees. Using our extracted scene topology, geometry and lane association knowledge, however, we are able to re-estimate the orientations of each object assumingthat all vehicles adhere to some basic traffic rules, i.e., right handed traffic. For associating the tracklets to lanes and the detections to lane spline points, we employ
the inference procedure described in Section 3.4.2. Next, we select the tangent angle
at the associated spline’s foot point s on the inferred lane l as our novel orientation
82

5.4. Experimental Results

estimate. Since parked cars are often oriented arbitrarily, our evaluation focuses onmoving vehicles only. Table 5.2 (row 7) shows that we are able to significantly reduce the orientation error from 32.6 degrees, which corresponds to the orientation
error of the raw detections (not depicted in the table), down to 14.0 degrees whenusing our model in combination with vehicle tracklets or 3D scene flow.
5.4.7. Object Detection
As we have shown in Section 5.4.4, objects help in estimating the layout and geometry of the scene. On the other hand, knowledge about the road layout should also
help in improving the performance of object detectors. To verify this hypothesis, we
conduct the following experiment.
We manually annotated all cars in the last frame of each sequence using 2D bounding boxes. This results in 355 labeled car instances in total. Next, we ran our pretrained part-based object detector [60] from Section 4.1.1 on those images and apply
non-maxima-suppression on the detections. Note that these detections are the sameas the ones that serve as input to our tracking model described in Section 3.3.2 andSection 4.1.2. Given the object detections and the inferred road geometry from Section 5.4.4, we re-score each object detection by adding the following term to thescores of [60]
"


 X
#
3
(xi − µi )2∆2l
0.5 max exp − 2 +
exp −
−1
(5.7)
l
2w
2σi2
i=1
Here ∆l is the distance of a car detection to lane spline l, w is the estimated street
width and {µi , σi } are mean and standard deviation of the object width, height andposition, respectively, obtained from a held-out training set using maximum likelihood estimation. Due to the choice of Eq. 5.7, a value between −1 and +1 will be
added to the detector score, depending on the agreement in size and the proximity
to the closest lane.
Fig. 5.9 depicts the precision-recall curves for the L-SVM baseline [60] and ourapproach. As evidenced by this figure, our geometric and topological constraints increase detection performance significantly, improving average precision from 69.9%
to 74.2%. The benefits of including this knowledge into the detection process arealso illustrated in Fig. 5.10. In order to include the partly occluded car to the right
into the detection result, the threshold of the baseline has to be lowered to a value
which produces two false positives (top). In contrast, our re-scored ranking is able
to handle this case (bottom). The average precision for each setting is listed in Table
5.2 (row 8).

83

5. Experimental Evaluation
100

Precision (%)

80
60
40
20
0
0

L−SVM
P
PT
PV
PS
PF
PO
PVSFO
PTSFO
PTVFO
PTVSO
PTVSF
PTVSFO
20

40
60
Recall (%)

80

100

Figure 5.9.: Improving Object Detection. This figure shows the precision-recall curves for theobject detection task using an overlap threshold of 50%. Compared to Felzenszwalb et al. [60]
(L-SVM), context from the proposed model helps to improving object detection performance.

Figure 5.10.: Improving Object Detection. By using context from our model for re-weighting
object hypothesis our algorithm (bottom) is able to eliminate false positives of state-of-the-art
part-based object detectors [60] (top).

84

5.4. Experimental Results

Object Detection (Section 4.1.1)
Object Tracking (Section 4.1.2)
Long Line Detection (Section 4.2)
Vanishing Line Estimation (Section 4.2)
Semantic Scene Labels (Section 4.3)
Scene Flow / Egomotion (Section 4.4)
Road Plane Estimation (Section 4.4)
Stereo Matching (Section 4.5)
Occupancy Grid Estimation (Section 4.5)
Prior (Section 3.3.1)
Tracklets (Section 3.3.2)
Vanishing Points (Section 3.3.3)
Semantic Labels (Section 3.3.4)
Scene Flow (Section 3.3.5)
Occupancy Grid (Section 3.3.6)
Total

Frame
3.88 s
0.46 s0.03 s0.01 s0.01 s0.31 s
0.06 s0.30 s
0.09 s0.12 s1.28 s0.10 s0.60 s0.50 s0.18 s7.92 sSequence314.01 s
37.55 s2.14 s0.70 s1.01 s24.87 s5.13 s23.90 s7.41 s
9.85 s103.54 s
8.19 s48.21 s40.22 s14.41 s641.13 s

Table 5.3.: Running Times per Frame/Sequence on a Intel Core7@2.67 Ghz. This figure
shows the average running times of the individual parts of our algorithm on a single CPU coreusing a mixed MATLAB/C++ implementation. The first part of the table lists the time used
for computing the image evidence (feature extraction) and the second part shows the timings
for evaluating 10, 000 samples. On average, our basic implementation runs at ∼ 8 seconds
per frame.

5.4.8. Runtime
In this section we evaluate the computational complexity of the proposed approach
experimentally. Towards this goal, we measure the running times of our mixed MATLAB/C++ implementation. While parts of the algorithm already run in real-time andothers can be accelerated using instruction- or thread-level parallelism, this was not
the primary goal of this thesis and is left to future work. However, this evaluation
provides a good indication of the bottlenecks and the more efficient stages in our
implementation.
Table 5.3 lists the average running times of the individual stages of our algorithm,
separated into feature extraction (top) and model inference (bottom). Learning times
are in the order of hours, depending on the quality of the gradient approximation,
but not listed here as learning can be performed offline. On average, our method
runs at ∼ 8 seconds per frame, when including the time for feature extraction anddrawing 10, 000 samples from the model. While the time for inference could be
dramatically reduced when using a pure C++ implementation and parallel Markov
chains, the main bottleneck of our method is the feature extraction stage. In particular, the running times are heavily dominated by the time consumed to detect and85

5. Experimental Evaluation

track objects, even though the cascaded version [61] of the part-based object detector [60] has been leveraged, which reduces object detection runtime by a factor of
10, approximately. With the availability of faster object detectors [53, 19] and heavy
multi-processing, a real-time implementation seems within reach.
5.4.9. Qualitative Results
Fig. 5.11-5.13 illustrate our inference results for the setting ’PTVSFO’, with themost likely lanes for each unique tracklet, indicated by an arrow. The ego-vehicle(observer) is depicted in black. For a definition of uniqueness, the reader is referred
to Section 5.4.5.
For most sequences the road layout has been estimated correctly and the vehicles
have been assigned to the correct lanes. Only vehicles that are very far away orvisible only for a couple of frames pose problems in terms of their lane associations.
However, note that this didn’t affect the layout estimation. In Fig. 5.11 (top-left) themoving vehicle in front of the observer and the static vehicles at the side of the roadhave been identified correctly. In Fig. 5.11 (bottom-left) the cyan object has been
observed only for a short period of time, leading to a probability of moving forward
as well as making a right turn. In Fig. 5.11 (bottom-right) the two crossing vehicles
have been identified correctly and distinguished from the vehicles waiting in frontof the traffic light. However, the red car has been assigned to the wrong lane as
the object detector orientation estimate was too uncertain and no motion has been
observed. The same holds true for the red vehicle in Fig. 5.12 (top-left), which has
been detected only for a very short period of time.
Typical failure modes are depicted in Fig. 5.14. In Fig. 5.14 (top-left, top-right,
bottom-right) the wrong intersection layout has been recovered. However, note thatgiven the estimated layout, most of the lane associations are correct. Fig. 5.14
(middle-right) is a difficult case as no moving vehicles were present to support the
hypothesis of a third intersection arm, resulting in a straight road. While the street
width has been wrongly estimated in Fig. 5.14 (bottom-left), the layout is correct
and almost all vehicles have been associated with the right lanes. In summary, theproposed system works well and robustly. Furthermore, even in the rare event of
topology or geometry estimation failures many objects are still correctly inferred.

86

5.4. Experimental Results

Figure 5.11.: Inference Results. For each sequence, the top plot shows the input image withthe bounding boxes of the detected objects. The bottom plot shows the inference result frombird’s eye perspective. Arrows indicate the predicted driving direction(s). See Section 5.4.9
for details.

87

5. Experimental Evaluation

Figure 5.12.: Inference Results. For each sequence, the top plot shows the input image withthe bounding boxes of the detected objects. The bottom plot shows the inference result frombird’s eye perspective. Arrows indicate the predicted driving direction(s). See Section 5.4.9
for details.

885.4. Experimental Results

Figure 5.13.: Inference Results. For each sequence, the top plot shows the input image withthe bounding boxes of the detected objects. The bottom plot shows the inference result frombird’s eye perspective. Arrows indicate the predicted driving direction(s). See Section 5.4.9
for details.

89

5. Experimental Evaluation

Figure 5.14.: Failure Cases. This figure shows some failure modes of our algorithm, where
either the topology, geometry or the tracklet associations are (partly) wrong. Section 5.4.9
gives further details.

90

6. Conclusions and Future Directions
This thesis has proposed a probabilistic generative model, which is able to reason
about complex inner-city traffic scenes using features extracted from short (stereo)
video sequences recorded from a movable platform. The application is autonomous
driving, which currently cannot handle urban environments due to missing or corrupt
GPS information, outdated maps, the complexity of the scenes, the amount of clutter(e.g., shadows, vegetation) as well as the high level of occlusions (e.g., occlusions
caused by cars, buildings, vegetation or infrastructure). Simple extensions of stateof-the-art lane detectors or lane-keeping systems to intersections are doomed to failas lane markings are often missing, damaged or occluded.
To provide an alternative, here we have proposed a probabilistic model and image
likelihoods using five complementary feature cues that consider the scene as a whole:
Vehicle tracklets, vanishing points, semantic labels, 3D scene flow and occupancy
grids. By making use of these cues our model is able to extract information such as
the topology and geometry of the road layout, as well as the lanes on which vehicles
are driving. We have shown that, despite the fact that the partition function of theprobabilistic model is intractable to compute, parameter learning is still possible inour model. We have cast the problem as a Gibbs random field and apply contrastive
divergence in combination with Markov Chain Monte Carlo inference techniques.
The validity of the proposed model has been substantiated by comprehensive experiments, considering individual image cues as well as a large variety of combinations. On a set of 113 realistic real-world intersection sequences we are able toestimate the topology of the scene with an accuracy of up to 90% while at the sametime accurately determining the intersection center and the individual street orientations. Vice-versa, we have shown that context from our model helps in improving
the performance of state-of-the-art object detectors in terms of detecting objects aswell as estimating their orientation. Considering the scene as a whole turned out tobe crucial, especially in the presence of clutter and missing data.
While we have discovered that all features proposed in this work were able toimprove performance individually, occupancy grids as well as vehicle tracklets and
3D scene flow have been identified as the strongest and most important feature cues.
This is comprehensible as human drivers likewise examine other traffic participants
as well as the 3D structure (e.g., buildings, urban canyons) to picture the scene.
Regarding future extensions, models that incorporate typical traffic patterns andtraffic light phases will present an interesting area of research. Presently, noise in
the observations can lead to implausible configurations such as cars colliding witheach other. Including higher-level information such as traffic patterns and traffic light91

6. Conclusions and Future Directions

phases will help to reduce ambiguities and increase robustness. Such information
will also allow for the detection of abnormalities in the traffic flow and to warn thedriver before entering the intersection.
Furthermore, more complex vehicle motion models are required. The presented
model uses a simple forward motion constraint with a B-spline based lane model.
Improved sensor observations and more computing power will allow for more accurate motion models and lane representations. Another interesting direction will
be to integrate information from other traffic participants (e.g., pedestrians) into themodel as well as to make use of further sources of information such as road markings
whenever they are visible and reliable or street maps, e.g., OpenStreetMap. Whilemaps can be noisy or even outdated, they still provide valuable prior information andcan be updated in an online manner as soon as enough vehicles have been equippedwith a scene understanding system like the one proposed in this thesis.

92

A. Sampling TechniquesThis appendix gives an introduction to sampling techniques, in particular Markov
Chain Monte Carlo (MCMC) methods [5, 123], which are adopted for inferencein the scene understanding model presented in this thesis. The robot localization
examples used for illustration are gratefully borrowed from a tutorial presentationof Martin Lauer in 2010 [123].
A.1. Introduction
Many statistical problems of practical relevance lead to problems which include solving an integral that is analytically intractable. In Bayesian inference, for example,
one is typically interested in inferring unknown variables x from observed data y,which leads to the following problems:p(y|x)p(x)• Normalization: p(x|y) = R p(y|x0 )p(x0 )dx0

R
• Marginalization: p(x|y) = p(x, z|y)dz
R• Expectation: Ep (f (x)) = f (x)p(x)dx
Examples for the latter are:R
• The expectation:
xp(x)dx,
2R
x2 p(x)dx −xp(x)dx , orR
• The expected risk:
risk(x)p(x)dx• The variance:R

Unfortunately, these integrals are often analytically intractable and sometimes p can
not even be expressed as a function. An approximation scheme for solving thesetasks is random Monte Carlo simulations, in which the integralZf (x)p(x)dx(A.1)
is approximated by a finite sum
1 X
f (xi )
N i

(A.2)

93

A. Sampling Techniques

sampleapproximate
integral byﬁnite sum

not analyticallytractable

approximate

Figure A.1.: Monte Carlo Approximation of an integral with a finite sum.

where xi are samples drawn from p. The longer we run the Monte Carlo simulation,
the better the approximation of the integral:
N

1 X
N →∞
f (xi ) −−−−→
N i=1

Z
f (x)p(x)dx(A.3)

Thus the estimate is unbiased and will almost surely converge to the right value by thestrong law of large numbers. The Monte Carlo approximation principle is illustrated
in Fig. A.1. Maintaining efficiency is one of the main challenges of Monte Carlo
methods.
A.2. Basic Sampling Strategies
Before moving on to Markov chains [5], we will review a set of basic samplingalgorithms and illustrate them on simple toy cases.
A.2.1. Inverse Transform Sampling
Assuming we are provided with a random number generator, one can draw samples
from distributions for which the cumulative probability distribution is invertible.
When this is not the case, one can still draw samples by approximating the inverted
cumulative probability distribution using interpolation.
More formally, let us consider a one-dimensional random variable x with probability distribution p(x) from which we want to sample. Let us further assume auniformly distributed random variable y ∼ U(0, 1) and a function f (y), such thatx = f (y). Since probability mass in any differential area must be invariant underchange of variables |p(x)dx| = |p(y)dy|, the distribution of x will be governed byp(x) = p(y)

94

dy
dy
=
.
dx
dx

(A.4)

A.2. Basic Sampling Strategies
8
1

f(y)

p(x)
h(x)

7
0.8

6
5

0.6

4
0.4

3
2

0.2

1
0
0

0.2

0.4

0.6

0.8

1

(a) 100 uniform samples from y ∼ U (0, 1)

0
0

2

4

6

8

10

(b) 100 transformed samples from x ∼ p(x)Figure A.2.: Inverse Transform Sampling. This figure illustrates sampling from a distribution
p(x) with invertible CDF by uniformly drawing samples on the interval (0, 1) and transforming
them by the inverse of the CDF.

By integration we obtain the cumulative density function (CDF)
Z xh(x) ≡p(x0 )dx0 = y

(A.5)

−∞

with x = f (y) = h−1 (y). This means that to obtain a sample from x we cansample y ∼ U(0, 1) and transform it using the inverse of the integral of the target
distribution p(x). To illustrate this fact we sample from an exponential distribution
by sampling from a uniform distribution using this method. Consider(exp(−x) 0 ≤ x,p(x) =(A.6)
0else
which gives h(x) = 1 − exp(−x). The inverse mapping is given by f (y) =h−1 (y) = − ln(1 − y). This is illustrated in Fig. A.2, which shows 100 samples
drawn from the distribution Eq. A.6.
A.2.2. Rejection Sampling
Unfortunately, for many distributions the inverse transform sampling procedure isimpractical due to their complex form or high dimensionality. An alternative is rejection sampling, which can be applied whenever another proposal distribution q(x)satisfyingp(x) ≤ M q(x) with M < ∞(A.7)
is available from which samples are obtained more easily and p(x) can be evaluatedup to some normalizing constant as illustrated in Fig. A.3. Each sample from the95

A. Sampling Techniques

0.2
p(x)
2q(x)
2q(xi)

0.15

0.1

p(xi)

0.05

0
−10

xi~q(x)
−5

0

5

10

(a) Rejection sampling

Figure A.3.: Rejection Sampling. This figure illustrates the target distribution p and the proposal distribution q, satisfying the requirement p(x) ≤ 2q(x).

rejection sampler involves generating two random numbers and an accept/reject step:• Draw a sample x from p(x).
• Draw a sample u from U(0, M q(x))
If u ≤ p(x) the sample is accepted, otherwise it gets rejected. As all accepted samples (x, u) follow a uniform distribution under the curve of p(x) the corresponding
x-values are distributed according to p(x) as desired:p(x) ∝ q(x)p(x)
M q(x)(A.8)

The procedure is illustrated in Algorithm 4. In practice it is often difficult to boundp(x) by M q(x). If M is chosen too conservatively (too large) the acceptance probability


p(x)
1
Pr(x accepted) = Pr u <≈(A.9)
M q(x)
M
gets too small to accept enough samples within reasonable time. This makes rejection sampling impractical in high dimensions.
Let us now consider a simple example. Given independent samples from a Gaussian distribution N (0, 0.5), we wish to estimate the mean µ and standard deviation
σ using rejection sampling. The graphical model is shown in Fig. A.4(a). We draw

96

A.2. Basic Sampling Strategies

Algorithm 4 Rejection Samplingi←1while i < N dodraw sample xi ∼ q(x)draw sample ui ∼ U (0, 1)i)
if ui < Mp(xthenq(xi )
accept xi
i←i+1

0.8
0.7
0.6

p(x)

0.5
0.4
0.3
0.2
0.1
0
−3

−2

−1

0
x

1

2

3

(b) 50 samples from N (0, 0.5)(a) Graphical Model
0.8

0.8

0.8

0.7

0.7

0.7

0.6

0.6

0.6

0.5

0.5

0.4

0.4

0.3

0.3

0.2
−0.4

−0.2

0

mu

(c) 1000 Samples

0.2

0.4

sigma

sigma

sigma

1000 accepted
21287 rejected

0.2
−0.4

0.5
0.4
0.3

−0.2

0

0.2

mu

(d) Kernel Density Estimate

0.4

0.2
−0.4

−0.2

0

0.2

0.4

mu

(e) True Posterior

Figure A.4.: Rejection Sampling. Given N = 50 independent samples from a Gaussian
distribution N (µ, σ) we infer the posterior over µ and σ.

97

A. Sampling Techniques

50 samples xi from N (µ, σ) and assume µ ∼ U(−0.5, 0.5) and σ ∼ U(0.1, 1.1)
as prior distributions (Fig. A.4(b)). The posterior simplifies top(µ, σ|x1 , ..., xN ) ∝ p(µ, σ)p(x1 , ..., xN |µ, σ)= p(µ)p(σ)

NYp(xi |µ, σ)i=1= [−0.5 ≤ µ ≤ 0.5] × [0.1 ≤ σ ≤ 1.1]
!

N
N
1
1 X
(xi − µ)2
exp − 2× √2σ i=12πσ 2(A.10)
Unfortunately, a tight bound to this density is hard to derive analytically. Hence,
we set q(µ, σ) = p(0, 0.5, |x1 , ..., xN ) to be constant. This highlights the main
problem with rejection sampling: Finding a tight bound to make sampling tractable.
The results of sampling from this posterior are illustrated and compared against thetrue posterior in Fig. A.4(c)-A.4(e).
Let us now consider a second example which is illustrated in Fig. A.5. Assume, wehave a robot which is located in a 2D field of size 1×1 meters, equipped with sensors
that measure its distance di with respect to the four corners ei of the field. We assume
a uniform prior for the robot location x ∼ U([0, 1] × [0, 1]) and the measurements
are given by the robot’s position and Gaussian noise di |x ∼ N (kx − ei k, σ 2 ) Since
all measurements are assumed to be independent, the posterior of the robot’s position
x given the 4 measurements {d1 , ..., d4 } can be written asp(x|d1 , d2 , d3 , d4 ) ∝ p(x)p(d1 |x)p(d2 |x)p(d3 |x)p(d4 |x)∝ [0 ≤ x1 , x2 ≤ 1] × exp −4
X(A.11)!

1[kx − ei k − di ]2
2σ 2 i=1

Since we know that the maximum of the unnormalized posterior is 1, we set q(x) =[0 ≤ x1 , x2 ≤ 1] which tightly bounds Zp(x), where Z is the normalizing constant.
The sampling results are depicted in Fig. A.5(c) and Fig. A.5(d). Note how many
rejected samples are required for accepting 50 samples in total.
A.3. Markov Chains
While the methods discussed so far are simple, they can be only applied to very simple low-dimensional problems. As a step towards the much more powerful Markov
Chain Monte Carlo methods, this section first introduces Markov chains and theirproperties.

98A.3. Markov Chains

R(a) Robot in the Field(b) Graphical Model for Localization

1

1
2699 rejected
50 accepted

6193 rejected
50 accepted

0.8

0.8

0.6

0.6

0.4

0.4

0.2

0.2

0
0

0.2

0.4

0.6

0.8

1

0
0

(c) Samples (x = (0.9, 0.1), σ = 0.1)

0.2

0.4

0.6

0.8

1

(d) Samples (x = (0.5, 0.5), σ = 0.1)

Figure A.5.: Robot Localization using Rejection Sampling. Illustration of the robot localization example: The task is to infer the robot’s location given noisy measurements of its distances
to the field corners. The lower plots show samples drawn using rejection sampling.

A.3.1. Definition of Markov Chains
Let us start with the definition of Markov chains.
Definition 1 (Markov Chain). A Markov chain (named after Andrey Markov) is adiscrete random process with the Markov property.
Definition 2 (Random Process). Let (Ω, F, P ) be a probability space, with sample
space Ω, σ-field F ⊆ 2Ω and probability measure P : F → [0, 1]. Let further(Ψ, X ) be a measurable observation space. A random process is a collection of
Ψ-valued random variables on Ω:
X = {xi : i ∈ {1, ..., N } ∧ xi : Ω → Ψ}
Definition 3 (Markov Property). A random process is said to be Markov, iff theconditional probability distribution of successor states in the process depends only99

A. Sampling Techniques

x0

x2

x1

x3

x4

x5

x6

...

Figure A.6.: Markov chain. Each state depends only on its predecessor.

0.1
2




0 1 0
T =  0 0.1 0.9
0.6 0.4 0

11(a) Stochastic Transition Matrix

0.4

0.9

0.6

3

(b) Stochastic Transition Graph

Figure A.7.: Homogeneous Discrete Markov Chain. This figure shows the stochastic transition matrix and the transition graph of a Markov chain with 3 states. In (a), the ij-th entry ofT denotes the probability of transitioning from i to j. (b) shows the corresponding graph.

upon the present state:
P (xi |xi−1 , ..., x1 ) = P (xi |xi−1 )This simplifies the joint distribution of X to:
P (x1 , ..., xN ) = P (x1 )NY

P (xi |xi−1 )i=2

The Markov property is illustrated in Fig. A.6, where each variable of the process depends only on the previous variable. An example of a Markov process is the random
walk where, at each step, the new position only depends upon the current position.
If dynamics is introduced, for example in form of a continuous velocity assumption,
the process is no longer Markov, since the new position depends on the current andthe previous position. However, increasing the dimensionality of the state to two(position, velocity) restores the Markov property again.
A Markov chain for which the transition operator does not depend on time is called
homogeneous Markov chain. It is convenient to describe homogeneous Markov
chains via stochastic transition matrices and directed graphs. This is illustrated inFig. A.7. Here, transition probabilities are represented as entries in the transition100A.3. Markov Chains

matrix T or labels in the transition graph. Probabilities must be positive and sum toone. The probability distribution for the new state pi is obtained by multiplying theprevious probability vector pi−1 by the transition matrix T:
pTi = pTi−1 T(A.12)

Note that we will use p = (p(x = s1 ), ..., p(x = sm ))T for distributions
P and p for
probabilities, or elements of p. To ensure that probabilities sum to one ( i p̃i = 1),
all rows of T must sum to one. This can be easily verified by rewriting the transitionin terms of sums:Xp̃j =pi Tij(A.13)i

P
P P
PP
Because of j p̃j = 1 we have j i pi Tij = P
i pi
j Tij = 1 and sinceP
i pi = 1, it is sufficient that all rows of T sum to one (j Tij = 1) to ensure valid
distributions. In the following we illustrate some iterations of a Markov process.
Let’s consider the transition matrix
0.5 0 0.5
T = 0.5 0.5 0 (A.14)
0 0.5 0.5
and start with p1 = (1, 0, 0)T , a distribution which has all it’s probability at state 1.
By iterating pTi ← pTi−1 T, we get:pTi
Iteration i
1(1.00, 0.00, 0.00)
2(0.50, 0.00, 0.50)
3(0.25, 0.25, 0.50)
4(0.25, 0.38, 0.38)
5(0.31, 0.38, 0.32)
6(0.34, 0.34, 0.32)
7(0.33, 0.33, 0.33)
..
..
.
.
∞
(0.33, 0.33, 0.33)
This example already exhibits a desired property of Markov chains: After several
iterations the chain stabilizes at a fix point. It is said to be stationary at p∞ =(0.33, 0.33, 0.33)T . For this T, no matter what initial distribution p1 we use, thechain will always converge to the same stationary point. Note that the stationary
point can be computed directly from the stochastic transition matrix T. Since for p∞
we have pT∞ = pT∞ T, p∞ is the left eigenvector of T corresponding to eigenvalue 1.
In the following we will examine sufficient conditions which guarantee convergenceof Markov chains.
101

A. Sampling Techniques

A.3.2. Properties of Markov Chains
Definition 4 (Stationarity). A probability distribution p on a state space of a Markov
chain with transition matrix T is called stationary, if
pT = pT T.
or in, other words, the probability of being in state x0 is invariantXp(x0 ) =p(x)Txx0x

for any possible state x0 . For the continuous case, the matrix T is replaced by atransition kernel T (x0 |x) which models the transition probabilities. Thus stationary
distributions are those, for whichZp(x0 ) = p(x)T (x0 |x)dx
holds.
A stochastic transition matrix T, for which any Markov chain converges to the invariant distribution p(x) is called ergodic. An ergodic Markov chain has exactly one
stationary distribution.
Definition 5 (Ergodicity). Let T∞ = limk→∞ Tk . A Markov chain with transition
matrix T is called ergodic, if• T∞ exists• All entries of T∞ are positive• All rows of T∞ are identical
A Markov chain is ergodic, iff it is irreducible and aperiodic.
Definition 6 (Irreducibility). A Markov chain is called irreducible, if any state x0 of
the chain can be reached by any other state x in a finite number of steps. Moreformally, there must be a sequence of states (x = x1 , ..., xN = x0 ) such thatTxi−1 xi > 0 for all i ∈ {1, ..., N − 1}.
Through proper state assignment or via permutation using an appropriate permutation matrix Q, the transition matrix T of a reducible Markov chain can be partitioned
into the canonic form


C A
T
QTQ =
(A.15)
0 T
with square stochastic matrix C, rectangular non-negative matrix A and square substochastic matrix T. The states of the Markov chain are partitioned into closed states102A.3. Markov Chains

belonging exclusively to C and transient states belonging to T. Once a transition
into a closed state has been performed, transient states are never reachable again.
The eigenvectors of C define the behavior of the Markov chain at equilibrium.
Definition 7 (Aperiodicity). A Markov chain is called aperiodic, if the occurrenceof states is not restricted to periodic events, but any state may occur at any time.
More formally, we define the period of state x as1

dx = gcd n ∈ N | ∃(x = x1 , ..., xn = x) ∧ ∀i∈{2,..,n} : Txi−1 xi > 0
A Markov chain is aperiodic, if all states x have period dx = 1.
If a Markov chain is aperiodic, returns to state x can occur at irregular times.
Definition 8 (Detailed Balance). A Markov chain with transition matrix T fulfills
the detailed balance condition for a distribution p, iff
p(x)Txx0 = p(x0 )Tx0 x
or in the continuous casep(x)T (x0 |x) = p(x0 )T (x|x0 )holds for all x and x0 .
Informally this means that the probability of being in state x and moving to state x0
equals the probability of being in state x0 and moving back to state x. The detailedbalance condition is sufficient to ensure that p(x) is stationary for T (or T ).
Theorem 1 (Detailed Balance). If T (or T) satisfies the detailed balance condition
for distribution p, then p is stationary distribution of T (or T).
Proof.
X

p(x)Txx0 =xXp(x0 )Tx0 x = p(x0 )

x

Z

X

Tx0 x = p(x0 )x0p(x)T (x |x)dx =Z0p(x )T (x|x0 )dx = p(x0 )To illustrate the convergence properties of Markov chains, let us randomly draw 10
points on the probability simplex and perform 30 Markov chain iterations. To provide a more vivid visualization, we interpolate all points using polynomials. We
show convergence results on a unit 2-simplex (dim(p) = 3) in Fig. A.8 and on aunit 3-simplex (dim(p) = 4) in Fig. A.9. A black square marks the final state of1

gcd: greatest common divisor

103

A. Sampling Techniqueseach Markov chain. Stationary distributions are computed from the first eigenvectorof T and depicted as a black circles. For the periodic and reducible case, all chainsconverge to the sub-simplex of the reduced transition matrix (for the 2-simplex thesub-simplex corresponds to a line), but continue oscillating in this space. Thus nostationary distribution can be found. For the periodic and irreducible example, allchains are orbiting around the center of the simplex and never converge. For theaperiodic and reducible case, all Markov chains converge to a common stationary
distribution, but the stationary point is confined to the sub-simplex of the reduced
matrix. When the transition matrix is aperiodic and irreducible, all trajectories converge to a stationary distribution, defined by the first eigenvector of T.
A.3.3. Combining Kernels
Transition kernels of Markov chains have the nice property that they can be combinedby concatenation. This allows for constructing complex moves from simple ones.
Theorem 2 (Kernel Concatenation). LetR T1 and T2 be transition kernels with stationary distribution p. Then T (x0 |x) ≡ T2 (x0 |x̃)T1 (x̃|x)dx̃ is another transtion
kernel with stationary distribution p.
Proof.
Z

T (x0 |x)p(x)dx =Z Z

T2 (x0 |x̃)T1 (x̃|x)dx̃ p(x)dx
ZZ=
T2 (x0 |x̃) T1 (x̃|x)p(x)dx dx̃
Z=
T2 (x0 |x̃)p(x̃)dx̃
= p(x0 )Theorem 3 (Kernel Mixing). Let T1 and T2 be transition kernels with stationary
distribution p and w1 , w2 ≥ 0 with w1 + w2 = 1. Then T (x0 |x) ≡ w1 T1 (x0 |x) +w2 T2 (x0 |x) is another transtion kernel with stationary distribution p.
Proof.
Z

T (x0 |x)p(x)dx =Zw1 T1 (x0 |x) + w2 T2 (x0 |x) p(x)dx= w1 p(x0 ) + w2 p(x0 )= p(x0 )104

A.3. Markov Chains

periodic + reducible
2

2




0.6 0.2 0.2
0 0 1
0 1 0

0.2

0.6

1

1

1

3

0.2

1

3

periodic + irreducible
2

2




0 1 0
0 0 1 
1 0 0

1

1

1

3

1

1

3

aperiodic + reducible
2

0.5


0.6 0.2 0.2
 0 0.5 0.5
0 0.5 0.5

2



0.2

0.6

1

0.5

0.5

3

0.2

0.5

1

3

aperiodic + irreducible (=ergodic)
2

0.1



2



0 1 0
 0 0.1 0.9
0.6 0.4 0

1

1

0.4

0.6

0.9

3

1

3

Figure A.8.: Markov chains on the 2-Simplex. From left to right: Stochastic transition matrix
T, transition graph and 10 runs of the process. Squares denote final states after 30 iterations,circles denote stationary states.

105

A. Sampling Techniques

periodic + reducible4
0.7 0.1 0.1 0.1
0 0 1 0
0 0 0 1
0 1 0 0

1

2

0.1
0.1
0.1

1

3

1

1

3
1

4

0.7

2

periodic + reducible
4

1

2




0 1 0 0
0 0 1 0
0 0 0 1
1 0 0 0

3

3

1

1

1

1

4

1

2

aperiodic + reducible
4
0.25

0.25

0.5


2
3
0.25 0.25 0.25 0.25
0.25 0.25
 0 0.25 0.5 0.25 0.25 0.01
0.01 0.53
0.25
 0 0.25 0.25 0.5 
0.25
41
0 0.01 0.01 0.98 0.25
0.98

1

2

aperiodic + irreducible (=ergodic)
40.1


0.2 0.8 0 0
0.1 0.1 0.6 0.2
0.1 0.1 0.1 0.7
0.6 0.1 0.2 0.1
3

0.2 0.1
0.1
0.2

0.1

0.8

0.1

0.6

2

0.7

3

0.1
1
0.2

0.6

1

4
0.1

2

Figure A.9.: Markov chains on the 3-Simplex. From left to right: Stochastic transition matrix
T, transition graph and 10 runs of the process. Squares denote final states after 30 iterations,circles denote stationary states.

106A.4. Markov Chain Monte Carlo

Algorithm 5 Metropolis-Hastings
x1 ← initial statei←2while i < N dodraw xi ∼ q(xi |xi−1 )draw ui ∼ U (0, 1)p(xi )q(xi−1 |xi )if ui > p(xi−1then)q(xi |xi−1 )xi ← xi−1i←i+1A.4. Markov Chain Monte Carlo
To make use of Markov chains for sampling, we need to construct a chain with stationary distribution p(x). This is called the Markov Chain Monte Carlo approach. In
contrast to the sampling schemes discussed so far, samples from a Markov chain will
be temporally correlated, but for many applications this is not a problem. The firstsamples we draw will be biased towards the user-specified initial state of the Markov
chain and should thus be removed. This stage is often called ’burn-in’ phase.
A.4.1. Metropolis-Hastings SamplingFirst, we consider the popular Metropolis-Hastings (MH) algorithm, which is very
easy to implement and satisfies the detailed balance condition. The idea is to use
a proposal distribution q from which samples can be drawn easily and efficiently.
Given x, a proposed sample x0 ∼ q(x0 |x) is accepted with probability
p(x0 )q(x|x0 )pM H (x0 |x) = min 1,(A.16)
p(x)q(x0 |x)
Informally this means that a proposed state is accepted, if the target density p(x0 ) is
high and it is likely to get back to the old state q(x|x0 ) using the next proposal. If asample x0 is accepted, it is added to the Markov chain, otherwise the old state x is
added. If q is symmetric Eq. A.16 becomesp(x0 )
0pM H (x |x) = min 1,(A.17)p(x)and the resulting algorithm is called Metropolis sampling. The general MetropolisHastings algorithm is summarized in Algorithm 5. To show that p is a stationary
distribution of T , let us write down the transition kernel T in terms of the acceptance107

A. Sampling Techniques

probability Eq. A.16:
T (x0 |x) = q(x0 |x)pM H (x0 |x)Z0+ δ(x − x) q(x̃|x)[1 − pM H (x̃|x)]dx̃

(A.18)

Informally T (x0 |x) is the probability of moving from state x to state x0 times the acceptance probability of state x0 or the probability of staying at state x because either
x was proposed and accepted or any other state has been proposed and rejected.
Theorem 4 (Metropolis-Hastings). p is stationary distribution of T .
Proof.
Z

T (x0 |x)p(x)dx =Z

min{p(x)q(x0 |x), p(x0 )q(x|x0 )}dxZ
+ p(x0 )q(x̃|x0 )[1 − pM H (x̃|x0 )]dx̃Z=
min{p(x)q(x0 |x), p(x0 )q(x|x0 )}dxZ
˜+p(x0 ) q(x̃|x0 )dx
Z− p(x0 )q(x̃|x0 )pM H (x̃|x0 )dx̃Z=
min{p(x)q(x0 |x), p(x0 )q(x|x0 )}dx+p(x0 )Z
− min{p(x0 )q(x̃|x0 ), p(x̃)q(x0 |x̃)}dx̃
= p(x0 )Let us now turn back to our example of sampling the mean µ and variance σ ofa univariate Gaussian. Again, we first sample N = 50 data points from N (µ =0, σ = 0.5). For sampling x = (µ, σ)T , we use the Metropolis algorithm with theproposal distribution
q(x0 |x) ∼ N (x, 0.05 I)(A.19)
Fig. A.10 shows that the Metropolis sampler has a better acceptance rate than therejection sampler from Section A.2.2. Unfortunately this rate depends heavily on theparticular choice of the proposal distribution q and making the right choice is crucial for applying Metropolis-Hastings to problems of practical relevance. A Markov
108A.4. Markov Chain Monte Carlo

0.8
0.7
0.6

p(x)

0.5
0.4
0.3
0.2
0.1
0
−3

−2

sigma

sigma

0.5

0.8

0.8

0.7

0.7

0.6

0.6

0.5

0.4

0.4

0.3

0.3

−0.2

0

mu

(c) 1000 Samples

0.2

0.4

sigma

Markov chain
1000 accepted
782 rejected

0.6

0.2
−0.4

0
x

1

2

3

(b) 50 samples from N (0, 0.5)(a) Graphical Model
0.8
0.7

−1

0.2
−0.4

0.5
0.4
0.3

−0.2

0

0.2

0.4

mu

(d) Kernel Density Estimate

0.2
−0.4

−0.2

0

0.2

0.4

mu

(e) True Posterior

Figure A.10.: Markov Chain Monte Carlo Sampling. Given independent samples from a
Gaussian distribution we infer the posterior over µ and σ using the Metropolis sampling algorithm with q(x0 |x) ∼ N (x, 0.05 I).

chain that traverses the state space efficiently is said to be well mixing. In contrast,a Markov chain that easily gets trapped in small areas of the search space is called
poorly mixing. The first samples of the chain (’burn-in’ samples) are typically rejected from the final estimate.
Let us now reconsider the robot localization problem from Fig. A.5, but this timeusing the Metropolis algorithm and assuming unknown noise in the distance measurements σ as illustrated in Fig. A.11. Since we are also concerned about estimating
the sensor noise σ, we use 16 measurements (instead of only four in the previous example) in order to gain robustness. Again, the prior for the robot’s location x is
assumed to be uniformly distributed on the unit square and we assume a uniform
prior on the interval [0.01, 0.5] for σ, which is now a stochastic variable as well:x ∼ U([0, 1] × [0, 1])(A.20)σ ∼ U(0.01, 0.5)

(A.21)109

A. Sampling TechniquesR(a) Field(b) Graphical Model1

0.42465 rejected
Markov chain
500 accepted

0.8

0.35
0.3

x2

sigma

0.6

0.4

0.25
0.2
0.15

0.2
0.1

0
0

0.2

0.4

x1

0.6

0.8

1

0.05
0

100

200

300

400

500

sample number(c) Position Estimate x(d) Noise Estimate σ

Figure A.11.: Robot Localization using the Metropolis Algorithm. The second row shows
the Markov chain for the robot’s position x and the measurement noise σ. The true parameters
are x = (0.5, 0.5) and σ = 0.1.

The measurements are modeled using a Gaussian distribution
di |x, σ ∼ N (kx − ei k, σ 2 )(A.22)

Since all measurements are assumed independent, the posterior of the robot’s position given the 16 measurements {d1 , ..., d16 } isp(x, σ|d1 , ...d16 ) ∝ p(x)p(σ)p(d1 |x, σ) · · · p(d16 |x, σ)∝ [0 ≤ x1 , x2 ≤ 1] × [0.01 ≤ σ ≤ 0.5]
P2
exp − 2σ1 2 16i=1 [kx − ei k − di ]×(2πσ 2 )8(A.23)

Sampling results with accepted and rejected samples are depicted in Fig. A.11. Aftera small ’burn-in’ period, the mode of the posterior is found in terms of position as
well as in terms of noise, while only rejecting a relatively small number of samples.

110A.4. Markov Chain Monte Carlo

A.4.2. Gibbs Sampling
When dealing with multivariate posterior distributions, it is also possible to update
variables only partly and loop over the updates. One popular and efficient choice ofsuch a cyclic MH kernel is known as Gibbs sampling. The idea in Gibbs sampling is
to introduce knowledge about the distributions into the sampling process by adopting
full conditional distributionsp(xk |x1 , ..., xk−1 , xk+1 , ..., xD )(A.24)

as proposal distributions for each k. Note that in contrast to the previous section,
here xk denotes the k’th dimension of random vector x and dim(x) = D is its
dimensionality. By applying this procedure all samples get accepted, making Gibbs
sampling very efficient in practice. However, the conditional posterior must be easy
to sample, whereas for Metropolis-Hastings the posterior must only be evaluatedup to a multiplicative constant. Note that it is also possible to group variables andsample from grouped conditionals.
In Gibbs sampling, the proposal distribution is chosen asq(x0 |x) = p(xk |x−k ) δ(x0−k − x−k )(A.25)

for k ∈ {1, ..., D}. Here x−k denotes all entries of x without entry k. It is easy toshow that all Gibbs moves are accepted using this proposal distribution.
Theorem 5 (Gibbs). Gibbs moves are accepted with probability 1.
Proof. As x0−k = x−k , the acceptance probability becomesp(x0 )q(x|x0 )pM H (x0 |x) = min 1,
p(x)q(x0 |x)p(x0 )p(xk |x0−k )= min 1,p(x)p(x0k |x−k )p(x0k , x0−k )p(xk |x0−k )= min 1,p(xk , x−k )p(x0k |x−k )p(x0k |x0−k )p(x0−k )p(xk |x0−k )= min 1,p(xk |x−k )p(x−k )p(x0k |x−k )= min {1, 1} = 1

Note that the proposal distribution is reducible, since we are not exploiting the fullstate space. This ’problem’ is addressed by sampling several times from different
components k of x (=different dimensions). After a full cycle the sample is added
to the list. The full algorithm is given in Algorithm 6.
111

A. Sampling Techniques

Algorithm 6 Gibbs samplingx1 ← initial statefor i ← 2 to N do
for k ← 1 to D doD
, xk+1draw sample xki ∼ p(xki |x1i , ..., xk−1ii−1 , ..., xi−1 )

0.8
0.7
0.6

p(x)

0.5
0.4
0.3
0.2
0.1
0
−3

−2

Markov chain
1000 samples

sigma

sigma

0.6

0.8

0.8

0.7

0.7

0.6

0.6

sigma

0.8

0.5

0
x

0.5
0.4

0.4

0.3

0.3

0.3

0.2
−0.4

0.2
−0.4

0

mu

(c) 1000 Samples

0.2

2

3

0.5

0.4

−0.2

1

(b) 50 samples from N (0, 0.5)(a) Graphical Model

0.7

−1

0.4

−0.2

0

0.2

mu

(d) Kernel Density Estimate

0.4

0.2
−0.4

−0.2

0

0.2

0.4

mu

(e) True Posterior

Figure A.12.: Gibbs Sampling. Given 50 independent samples from a Gaussian distribution
the posterior over µ and σ is sampled using Gibbs sampling. Non-informative priors on µ andσ are assumed.

Let us illustrate Gibbs sampling on our previous example of sampling the posterior parameters of a univariate Gaussian. Note that the simple uniform priors we
employed in the other examples cannot be used for Gibbs sampling as they lead tonon-standard conditional posterior distributions. Instead, we focus on posterior distributions with a well-defined analytical form, for which out-of-the-box samplers
can be used. Such posteriors can be obtained by using conjugate priors, which havethe same analytical form as the posterior. The only difference is an update on theparameters. It is well known that the conjugate prior for the mean of the Gaussian
is Gaussian, and the conjugate prior for the precision (inverse variance) is a Gamma
112

A.4. Markov Chain Monte Carlo

distribution. For details on conjugate priors the reader is referred to [76].
Let us now show that the state conjugacy relationships hold indeed, starting with
the Gaussian mean. Instead of working with the variance σ 2 we employ the socalled precision parameter λ = σ −2 for notational simplicity. Assuming that thedata likelihood and the prior for the mean µ and precision λ are given by√λxi |µ, λ ∼ N (µ, λ−1 ) ∝ λ exp − (xi − µ)2(A.26)2n κoµ ∼ N (ξ, κ−1 ) ∝ exp − (µ − ξ)2(A.27)
2−1
α−1
λ ∼ Γ(α, β ) ∝ λ
exp {−λβ}(A.28)
the posterior of µ given λ and the posterior of λ given µ is easily found by completingthe square: P
λ i xi + κξ, (λN + κ)−1
(A.29)µ|x1 , ..., xN , λ ∼ N
λN + κ
!−1 !
N
1X
λ|x1 , ..., xN , µ ∼ Γ α + ,(xi − µ)2 + β(A.30)
2
2 i
The bivariate Gibbs sampler for the posterior of a Gaussian is now readily given byalternately drawing samples from p(λ|x1 , ..., xN , µ) and p(µ|x1 , ..., xN , λ) while
keeping the other variable fixed in turn. This is illustrated in Fig. A.12 using uninformative priors with ξ = κ = α = β = 0.

113

B. Bibliography[1] P. F. Alcantarilla. Vision Based Localization: From Humanoid Robots to Visually Impaired People. PhD thesis, University of Alcala, Alcala de Henares,
Madrid, Spain, October 2011.
[2] Y. Alon, A. Ferencz, and A. Shashua. Off-road path following using region
classification and geometric projection constraints. In Proc. IEEE Conf. on
Computer Vision and Pattern Recognition (CVPR), 2006.
[3] J. M. Alvarez, T. Gevers, and A. M. Lopez. 3d scene priors for road detection.
In Proc. IEEE Conf. on Computer Vision and Pattern Recognition (CVPR),
2010.
[4] M. Aly. Real time detection of lane markers in urban streets. In Proc. IEEE
Intelligent Vehicles Symposium (IV), 2008.
[5] C. Andrieu, N. de Freitas, A. Doucet, and M. I. Jordan. An introduction to
MCMC for machine learning. Machine Learning, 50(1-2):5–43, 2003.
[6] M. Andriluka, S. Roth, and B. Schiele. People-tracking-by-detection andpeople-detection-by-tracking. In Proc. IEEE Conf. on Computer Vision and
Pattern Recognition (CVPR), 2008.
[7] M. Andriluka, S. Roth, and B. Schiele. Monocular 3d pose estimation andtracking by detection. In Proc. IEEE Conf. on Computer Vision and Pattern
Recognition (CVPR), 2010.
[8] N. Apostoloff and A. Zelinsky. Robust vision based lane tracking using multiple cues and particle filtering. In Proc. IEEE Intelligent Vehicles Symposium(IV), 2003.
[9] A. Bachmann and I. Lulcheva. Bayesian scene segmentation incorporating
motion constraints and category-specific information. In Proc. of the Conf.
on Computer Vision Theory and Applications (VISAPP), 2009.
[10] H. Badino, U. Franke, and R. Mester. Free space computation using stochastic
occupancy grids and dynamic programming. In Proc. IEEE International
Conf. on Computer Vision (ICCV) Workshops, 2007.

115

B. Bibliography[11] H. Badino, U. Franke, and D. Pfeiffer. The stixel world - a compact medium
level representation of the 3d-world. In Proc. of the DAGM Symposium on
Pattern Recognition (DAGM), 2009.
[12] H. Badino, R. Mester, T. Vaudrey, and U. Franke. Stereo-based free spacecomputation in complex traffic scenarios. In Proc. IEEE Southwest Symposium on Image Analysis and Interpretation, pages 189–192, March 2008.
[13] M. Bajracharya, B. Moghaddam, A. Howard, S. Brennan, and L. H. Matthies.
A fast stereo-based system for detecting and tracking pedestrians from a moving vehicle. International Journal of Robotics Research (IJRR), 28:1466–
1485, 2009.
[14] S. Bao, M. Sun, and S. Savarese. Toward coherent object detection and scenelayout understanding. In Proc. IEEE Conf. on Computer Vision and Pattern
Recognition (CVPR), 2010.
[15] O. Barinova, V. Lempitsky, E. Tretyak, and P. Kohli. Geometric image parsing
in man-made environments. In Proc. of the European Conf. on Computer
Vision (ECCV), 2010.
[16] E. Baseski and L. Baunegaard. Road interpretation for driver assistance basedon an early cognitive vision system. In Proc. of the Conf. on Computer Vision
Theory and Applications (VISAPP), 2009.
[17] H. Bay, A. Ess, and L. Tuytelaars, Tinne andVan Gool. Speeded-up robust features (surf). Computer Vision and Image Understanding (CVIU), 110(3):346–
359, 2008.
[18] H. Bay, T. Tuytelaars, and L. V. Gool. Surf: Speeded up robust features. In
Proc. of the European Conf. on Computer Vision (ECCV), 2006.
[19] R. Benenson, M. Mathias, R. Timofte, and L. J. V. Gool. Pedestrian detection
at 100 frames per second. In Proc. IEEE Conf. on Computer Vision and
Pattern Recognition (CVPR), 2012.
[20] M. Betke, E. Haritaoglu, and L. S. Davis. Real-time multiple vehicle detection
and tracking from a moving vehicle. Machine Vision and Applications (MVA),
12(2):69–83, 2000.
[21] S. M. Bileschi. StreetScenes: Towards Scene Understanding in Still Images.
PhD thesis, Massachusetts Institute of Technology, 2006.
[22] C. M. Bishop. Pattern Recognition and Machine Learning. Springer, 1st ed.
2006 edition, October 2006.
116

[23] G. Bradski and A. Kaehler. Learning OpenCV: Computer Vision with the
OpenCV Library. O’Reilly, Cambridge, MA, 2008.
[24] M. D. Breitenstein, F. Reichlin, B. Leibe, E. Koller-Meier, and L. Van Gool.
Robust tracking-by-detection using a detector confidence particle filter. In
Proc. IEEE International Conf. on Computer Vision (ICCV), 2009.
[25] M. D. Breitenstein, E. Sommerlade, B. Leibe, L. Van Gool, and I. Reid. Probabilistic parameter selection for learning scene structure from video. In Proc.
of the British Machine Vision Conf. (BMVC), 2008.
[26] J. E. Bresenham. Algorithm for computer control of a digital plotter. IBM,4(1):25–30, 1965.
[27] A. Broggi. A massively parallel approach to real-time vision-based roadmarkings detection. In Proc. IEEE Intelligent Vehicles Symposium (IV), 1995.
[28] A. Broggi, P. Medici, P. Zani, A. Coati, and M. Panciroli. Autonomous vehicles control in the VisLab Intercontinental Autonomous Challenge. Annual
Reviews in Control, 36(1):161–171, 2012.
[29] M. A. Brubaker, A. Geiger, and R. Urtasun. Lost! leveraging the crowd
for probabilistic visual self-localization. In Proc. IEEE Conf. on Computer
Vision and Pattern Recognition (CVPR), 2013.
[30] M. Buehler, K. Iagnemma, and S. Singh. The 2005 darpa grand challenge:
The great robot race, volume 36. Springer, 2007.
[31] M. Buehler, K. Iagnemma, and S. Singh, editors. The DARPA Urban Challenge, volume 56 of Advanced Robotics, 2009.
[32] Y. Cai, N. de Freitas, and J. J. Little. Robust visual tracking for multiple
targets. In Proc. of the European Conf. on Computer Vision (ECCV), 2006.
[33] M. Calonder, V. Lepetit, M. Ozuysal, T. Trzcinski, C. Strecha, and P. Fua.
Brief: Computing a local binary descriptor very fast. IEEE Trans. on PatternAnalysis and Machine Intelligence (PAMI), 34(7):1281–1298, 2012.
[34] M. Calonder, V. Lepetit, C. Strecha, and P. Fua. Brief: Binary robust independent elementary features. In Proc. of the European Conf. on Computer
Vision (ECCV), 2010.
[35] J. Canny. A computational approach to edge detection. IEEE Trans. on
Pattern Analysis and Machine Intelligence (PAMI), 8(6):679–698, November
1986.

117

B. Bibliography[36] M. Cech. Fahrspurschätzung aus monokularen Bildfolgen für innerstädtische
Fahrerassistenzanwendungen. PhD thesis, Karlsruhe Institute of Technology,
2009.
[37] W. Choi and S. Savarese. Multiple target tracking in world coordinate withsingle, minimally calibrated camera. In Proc. of the European Conf. on Computer Vision (ECCV), 2010.
[38] W. Choi and S. Savarese. A unified framework for multi-target tracking andcollective activity recognition. In Proc. of the European Conf. on Computer
Vision (ECCV), 2012.
[39] N. Chumerin and M. Van Hulle. Ground plane estimation based on dense
stereo disparity. In Proc. of the International Conference on Artificial Intelligence and Neural Networks (ICAINN), 2008.
[40] N. Cornelis, B. Leibe, K. Cornelis, and L. J. Van Gool. 3d urban scene modeling integrating recognition and reconstruction. International Journal ofComputer Vision (IJCV), 78(2-3):121–141, July 2008.
[41] J. Crisman and C. Thorpe. Scarf: A color vision system that tracks roads andintersections. IEEE Trans. on Robotics and Automation (TRA), 9(1):49–58,
February 1993.
[42] H. Dahlkamp, A. Kaehler, D. Stavens, S. Thrun, and G. R. Bradski. Selfsupervised monocular road detection in desert terrain. In Proc. Robotics:
Science and Systems (RSS), 2006.
[43] H. Dahlkamp, H.-H. Nagel, A. Ottlik, and P. Reuter. A framework for modelbased tracking experiments in image sequences. International Journal ofComputer Vision (IJCV), 73(2):139–157, 2007.
[44] R. Danescu and S. Nedevschi. Probabilistic lane tracking in difficult road scenarios using stereovision. IEEE Trans. on Intelligent Transportation Systems(TITS), 10(2):272–282, 2009.
[45] R. Danescu, S. Nedevschi, M. M. Meinecke, and T. B. To. Lane geometry
estimation in urban environments using a stereovision system. In Proc. IEEE
Conf. on Intelligent Transportation Systems (ITSC), 2007.
[46] T. Dang, C. Hoffmann, and C. Stiller. Continuous stereo self-calibration
by camera parameter tracking. IEEE Trans. on Image Processing (TIP),
18(7):1536–50, 2009.
[47] A. J. Davison. Real-time simultaneous localization and mapping with a single
camera. In Proc. IEEE International Conf. on Computer Vision (ICCV), 2003.
118

[48] C. De Boor. A Practical Guide to Splines. Number 27 in Applied Mathematical Sciences. Springer-Verlag, 1978.
[49] V. Delaitre, D. Fouhey, I. Laptev, J. Sivic, A. Gupta, and A. Efros. Scene
semantics from long-term observation of people. In Proc. of the European
Conf. on Computer Vision (ECCV), 2012.
[50] C. Desai, D. Ramanan, and C. Fowlkes. Discriminative models for multiclass object layout. In Proc. IEEE International Conf. on Computer Vision(ICCV), 2009.
[51] E. D. Dickmanns and B. D. Mysliwetz. Recursive 3-d road and relative egostate recognition. IEEE Trans. on Pattern Analysis and Machine Intelligence(PAMI), 14(2):199–213, Feb 1992.
[52] A. H. Dodson, G. V. Moon, T. Moore, and D. Jones. Guiding blind pedestrians
with a personal navigation system. Journal of Navigation, 52:330–341, 1999.
[53] P. Dollar, S. Belongie, and P. Perona. The fastest pedestrian detector in thewest. In Proc. of the British Machine Vision Conf. (BMVC), 2010.
[54] B. A. Draper, R. T. Collins, J. Brolio, A. R. Hanson, and E. M. Riseman. The
schema system. International Journal of Computer Vision (IJCV), 2(3):209–
250, 1989.
[55] C. Duchow. A novel, signal model based approach to lane detection for use
in intersection assistance. In Proc. IEEE Conf. on Intelligent Transportation
Systems (ITSC), 2006.
[56] W. Enkelmann, G. Struck, and J. Geisler. Roma - a system for model-based
analysis of road markings. In Proc. IEEE Intelligent Vehicles Symposium (IV),1995.
[57] A. Ess, B. Leibe, K. Schindler, and L. V. Gool. Robust multi-person tracking from a mobile platform. IEEE Trans. on Pattern Analysis and MachineIntelligence (PAMI), 31:1831–1846, 2009.
[58] A. Ess, T. Mueller, H. Grabner, and L. van Gool. Segmentation-based urban
traffic scene understanding. In Proc. of the British Machine Vision Conf.
(BMVC), 2009.
[59] M. Everingham, L. Van Gool, C. K. I. Williams, J. Winn, and A. Zisserman.
The pascal visual object classes (voc) challenge. International Journal ofComputer Vision (IJCV), 88(2):303–338, 2010.

119B. Bibliography[60] P. Felzenszwalb, R. Girshick, D. McAllester, and D. Ramanan. Object detection with discriminatively trained part based models. IEEE Trans. on PatternAnalysis and Machine Intelligence (PAMI), 32:1627–1645, 2010.
[61] P. F. Felzenszwalb, R. B. Girshick, and D. A. McAllester. Cascade object
detection with deformable part models. In Proc. IEEE Conf. on Computer
Vision and Pattern Recognition (CVPR), 2010.
[62] M. A. Fischler and R. C. Bolles. Random sample consensus: a paradigm formodel fitting with applications to image analysis and automated cartography.
Communications of the ACM, 24:381–395, 1981.
[63] G. Floros and B. Leibe. Joint 2d-3d temporally consistent semantic segmentation of street scenes. In Proc. IEEE Conf. on Computer Vision and Pattern
Recognition (CVPR), 2012.
[64] U. Franke and A. Joos. Real-time stereo vision for urban traffic scene understanding. In Proc. IEEE Intelligent Vehicles Symposium (IV), 2000.
[65] D. M. Gavrila and S. Munder. Multi-cue pedestrian detection and tracking
from a moving vehicle. International Journal of Computer Vision (IJCV),
73:41–59, 2007.
[66] A. Geiger. Monocular road mosaicing for urban environments. In Proc. IEEE
Intelligent Vehicles Symposium (IV), 2009.
[67] A. Geiger and B. Kitt. Objectflow: A descriptor for classifying traffic motion.
In Proc. IEEE Intelligent Vehicles Symposium (IV), 2010.
[68] A. Geiger, M. Lauer, F. Moosmann, B. Ranft, H. Rapp, C. Stiller, andJ. Ziegler. Team annieway’s entry to the grand cooperative driving challenge
2011. IEEE Trans. on Intelligent Transportation Systems (TITS), 2012.
[69] A. Geiger, M. Lauer, and R. Urtasun. A generative model for 3d urban scene
understanding from movable platforms. In Proc. IEEE Conf. on Computer
Vision and Pattern Recognition (CVPR), 2011.
[70] A. Geiger, P. Lenz, C. Stiller, and R. Urtasun. Vision meets robotics: The
kitti dataset. International Journal of Robotics Research (IJRR), to appear.
[71] A. Geiger, P. Lenz, and R. Urtasun. Are we ready for autonomous driving?
The KITTI vision benchmark suite. In Proc. IEEE Conf. on Computer Vision
and Pattern Recognition (CVPR), 2012.
[72] A. Geiger, F. Moosmann, O. Car, and B. Schuster. A toolbox for automatic
calibration of range and camera sensors using a single shot. In Proc. IEEE
International Conf. on Robotics and Automation (ICRA), 2012.
120

[73] A. Geiger, M. Roser, and R. Urtasun. Efficient large-scale stereo matching.
In Proc. of the Asian Conf. on Computer Vision (ACCV), 2010.
[74] A. Geiger, C. Wojek, and R. Urtasun. Joint 3d estimation of objects and scenelayout. In Advances in Neural Information Processing Systems (NIPS), 2011.
[75] A. Geiger, J. Ziegler, and C. Stiller. StereoScan: Dense 3d reconstruction in
real-time. In Proc. IEEE Intelligent Vehicles Symposium (IV), 2011.
[76] A. Gelman, J. B. Carlin, H. S. Stern, and D. B. Rubin. Bayesian Data Analysis,
Second Edition (Chapman & Hall/CRC Texts in Statistical Science). Chapman and Hall/CRC, 2 edition, July 2003.
[77] V. Gengenbach, H. H. Nagel, F. Heimes, G. Struck, and H. Kollnig. Modelbased recognition of intersections and lane structures. In Proc. IEEE Intelligent Vehicles Symposium (IV), 1995.
[78] C. J. Geyer. Practical markov chain monte carlo. Statistical Science, 7(4):473–
483, 1992.
[79] W. Gilks and S. Richardson, editors. Markov Chain Monte Carlo in Practice.
Chapman & Hall, 1995.
[80] M. Goebl and G. Faerber. A real-time-capable hard- and software architecture
for joint image and knowledge processing in cognitive automobiles. In Proc.
IEEE Intelligent Vehicles Symposium (IV), 2007.
[81] S. Gould, R. Fulton, and D. Koller. Decomposing a scene into geometricand semantically consistent regions. In Proc. IEEE International Conf. on
Computer Vision (ICCV), 2009.
[82] P. J. Green. Reversible jump markov chain monte carlo computation andbayesian model determination. Biometrika, 82(4):711–732, 1995.
[83] R. Guo and D. Hoiem. Beyond the line of sight: Labeling the underlying
surfaces. In Proc. of the European Conf. on Computer Vision (ECCV), 2012.
[84] A. Gupta, A. A. Efros, and M. Hebert. Blocks world revisited: Image understanding using qualitative geometry and mechanics. In Proc. of the European
Conf. on Computer Vision (ECCV), 2010.
[85] R. I. Hartley and A. Zisserman. Multiple View Geometry in Computer Vision.
Cambridge University Press, second edition, 2004.
[86] W. K. Hastings. Monte carlo sampling methods using markov chains and theirapplications. Biometrika, 57:97–109, 1970.
121

B. Bibliography[87] V. Hedau, D. Hoiem, and D. Forsyth. Recovering the spatial layout of cluttered rooms. In Proc. IEEE International Conf. on Computer Vision (ICCV),
2009.
[88] V. Hedau, D. Hoiem, and D. A. Forsyth. Recovering free space of indoor
scenes from a single image. In Proc. IEEE Conf. on Computer Vision and
Pattern Recognition (CVPR), 2012.
[89] F. Heimes, K. Fleischer, and H. H. Nagel. Automatic generation of intersection models from digital maps for vision-based driving on inner city intersections. In Proc. IEEE Intelligent Vehicles Symposium (IV), 2000.
[90] F. Heimes and H. H. Nagel. Towards active machine-vision-based driver assistance for urban areas. International Journal of Computer Vision (IJCV),
50(1):5–34, 2002.
[91] G. Heitz, S. Gould, A. Saxena, and D. Koller. Cascaded classification models:
Combining models for holistic scene understanding. In Advances in Neural
Information Processing Systems (NIPS), 2008.
[92] G. Hinton. Training products of experts by minimizing contrastive divergence. Neural Computation, 14:2002, 2000.
[93] H. Hirschmueller. Stereo processing by semiglobal matching and mutual information. IEEE Trans. on Pattern Analysis and Machine Intelligence (PAMI),
30(2):328–341, 2008.
[94] D. Hoiem, A. Efros, and M. Hebert. Putting objects in perspective. In Proc.
IEEE Conf. on Computer Vision and Pattern Recognition (CVPR), 2006.
[95] D. Hoiem, A. Efros, and M. Hebert. Putting objects in perspective. International Journal of Computer Vision (IJCV), 80:3–15, 2008.
[96] D. Hoiem, A. A. Efros, and M. Hebert. Geometric context from a single
image. In Proc. IEEE International Conf. on Computer Vision (ICCV), 2005.
[97] D. Hoiem, A. A. Efros, and M. Hebert. Recovering surface layout from animage. International Journal of Computer Vision (IJCV), 75(1):151–172,
October 2007.
[98] D. Hoiem, A. A. Efros, and M. Hebert. Closing the loop on scene interpretation. In Proc. IEEE Conf. on Computer Vision and Pattern Recognition(CVPR), 2008.
[99] R. Horaud and F. Dornaika. Hand-eye calibration. International Journal of
Robotics Research (IJRR), 14(3):195–210, 1995.
122

[100] A. S. Huang, D. Moore, M. Antone, E. Olson, and S. Teller. Finding multiple
lanes in urban road networks with vision and lidar. Autonomous Robots, 26(23):103–122, 2009.
[101] C. Huang, B. Wu, and R. Nevatia. Robust object tracking by hierarchical association of detection responses. In Proc. of the European Conf. on Computer
Vision (ECCV), 2008.
[102] B. Hummel, W. Thiemann, and I. Lulcheva. Description logic for intersection
understanding. In Cognitive Systems with Interactive Sensors (COGIS), 2007.
[103] B. Hummel, Z. Yang, and C. Duchow. Kreuzungsverstehen - Ein wissensbasierter Ansatz. IT, 49(1):5, 2007.
[104] T. M. Jochem, D. A. Pomerleau, and C. E. Thorpe. Vision based intersection
navigation. In Proc. IEEE Intelligent Vehicles Symposium (IV), 1996.
[105] R. E. Kalman. A new approach to linear filtering and prediction problems.
Journal of Basic Engineering (JBE), 1(82):35–45, 1960.
[106] S. Kammel, J. Ziegler, and C. Stiller. Team annieway’s autonomous system for the 2007 darpa urban challenge. Journal of Field Robotics (JFR),
25(9):615–639, September 2008.
[107] V. Kastrinaki. A survey of video processing techniques for traffic applications.
Image and Vision Computing (IVC), 21(4):359, 2003.
[108] R. Kaucic, A. Perera, G. Brooksby, J. Kaufhold, and A. Hoogs. A unified
framework for tracking through occlusions and across sensor gaps. In Proc.
IEEE Conf. on Computer Vision and Pattern Recognition (CVPR), 2005.
[109] Z. Khan, T. Balch, and F. Dellaert. Mcmc-based particle filtering for tracking
a variable number of interacting targets. IEEE Trans. on Pattern Analysis andMachine Intelligence (PAMI), 27(11):1805–1819, 2005.
[110] B. Kitt, A. Geiger, and H. Lategahn. Visual odometry based on stereo image
sequences with ransac-based outlier rejection scheme. In Proc. IEEE Intelligent Vehicles Symposium (IV), 2010.
[111] D. Koller, Q. T. Luong, and J. Malik. Using binocular stereopsis for visionbased vehicle control. In Proc. IEEE Intelligent Vehicles Symposium (IV),1995.
[112] D. Koller, J. Weber, and J. Malik. Towards realtime visual based tracking in
cluttered traffic scenes. In Proc. IEEE Intelligent Vehicles Symposium (IV),
1994.
123

B. Bibliography[113] K. Konolige. Small vision system. hardware and implementation. In Proc. of
the International Symposium on Robotics Research (ISRR), 1997.
[114] J. Kosecka and W. Zhang. Video compass. In Proc. of the European Conf.
on Computer Vision (ECCV), 2002.
[115] D. Kuettel, M. D. Breitenstein, L. V. Gool, and V. Ferrari. What’s going on?:Discovering spatio-temporal dependencies in dynamic scenes. In Proc. IEEE
Conf. on Computer Vision and Pattern Recognition (CVPR), 2010.
[116] H. W. Kuhn. The Hungarian method for the assignment problem. Naval
Research Logistics Quarterly, 2:83–97, 1955.
[117] S. Kumar and M. Hebert. Discriminative random fields: A discriminative
framework for contextual interaction in classification. In Proc. IEEE International Conf. on Computer Vision (ICCV), pages 1150–1157, 2003.
[118] S. Kumar and M. Hebert. Man-made structure detection in natural images
using a causal multiscale random field. In Proc. IEEE Conf. on Computer
Vision and Pattern Recognition (CVPR), 2003.
[119] S. Kumar and M. Hebert. A hierarchical field framework for unified contextbased classification. In Proc. IEEE International Conf. on Computer Vision(ICCV), 2005.
[120] L. Ladicky, P. Sturgess, C. Russell, S. Sengupta, Y. Bastanlar, W. Clocksin,
and P. Torr. Joint optimisation for object class segmentation and dense stereo
reconstruction. In Proc. of the British Machine Vision Conf. (BMVC), 2010.
[121] H. Lategahn, A. Geiger, and B. Kitt. Visual slam for autonomous groundvehicles. In Proc. IEEE International Conf. on Robotics and Automation(ICRA), 2011.
[122] H. Lategahn, A. Geiger, B. Kitt, and C. Stiller. Motion-without-structure:
Real-time multipose optimization for accurate visual odometry. In Proc. IEEE
Intelligent Vehicles Symposium (IV), 2012.
[123] M. Lauer. Entwicklung eines Monte-Carlo-Verfahrens zum selbstaendigenLernen von Gauss-Mischverteilungen. PhD thesis, Universitaet Karlsruhe(TH), 2004.
[124] L. Leal-Taixe, G. Pons-Moll, and B. Rosenhahn. Everybody needs somebody:modeling social and grouping behavior on a linear programming multiple
people tracker. In Proc. IEEE International Conf. on Computer Vision (ICCV)Workshops, 2011.
124

[125] D. Lee, A. Gupta, M. Hebert, and T. Kanade. Estimating spatial layout ofrooms using volumetric reasoning about objects and surfaces. In Advancesin Neural Information Processing Systems (NIPS), 2010.
[126] D. C. Lee, M. Hebert, and T. Kanade. Geometric reasoning for single image
structure recovery. In Proc. IEEE Conf. on Computer Vision and Pattern
Recognition (CVPR), 2009.
[127] J. Lee. A machine vision system for lane-departure detection. Computer
Vision and Image Understanding (CVIU), 86(1):52–78, 2002.
[128] B. Leibe, N. Cornelis, K. Cornelis, and L. Van Gool. Integrating recognition
and reconstruction for cognitive traffic scene analysis from a moving vehicle.
In Proc. of the DAGM Symposium on Pattern Recognition (DAGM), 2006.
[129] B. Leibe, N. Cornelis, K. Cornelis, and L. Van Gool. Dynamic 3d scene
analysis from a moving vehicle. In Proc. IEEE Conf. on Computer Vision
and Pattern Recognition (CVPR), 2007.
[130] B. Leibe, K. Schindler, N. Cornelis, and L. Van Gool. Coupled detection andtracking from static cameras and moving vehicles. IEEE Trans. on PatternAnalysis and Machine Intelligence (PAMI), 30(10):1683–1698, 2008.
[131] P. Lenz, J. Ziegler, A. Geiger, and M. Roser. Sparse scene flow segmentation
for moving object detection in urban environments. In Proc. IEEE Intelligent
Vehicles Symposium (IV), 2011.
[132] S. Leutenegger, M. Chli, and R. Siegwart. Brisk: Binary robust invariant
scalable keypoints. In Proc. IEEE International Conf. on Computer Vision(ICCV), pages 2548–2555, 2011.
[133] C.-K. Liang, C.-C. Cheng, Y.-C. Lai, L.-G. Chen, and H. H. Chen. Hardwareefficient belief propagation. In Proc. IEEE Conf. on Computer Vision and
Pattern Recognition (CVPR), 2009.
[134] D. G. Lowe. Object recognition from local scale-invariant features. In Proc.
IEEE International Conf. on Computer Vision (ICCV), 1999.
[135] D. G. Lowe. Distinctive image features from scale-invariant keypoints. International Journal of Computer Vision (IJCV), 60(2):91–110, 2004.
[136] M. Lutzeler and E. D. Dickmanns. Ems-vision: recognition of intersections
on unmarked road networks. In Proc. IEEE Intelligent Vehicles Symposium(IV), 2000.

125

B. Bibliography[137] J. C. McCall and M. M. Trivedi. Video-based lane estimation and tracking fordriver assistance: survey, system, and evaluation. IEEE Trans. on Intelligent
Transportation Systems (TITS), 7(1):20–37, March 2006.
[138] F. P. McKenna. The human factor in driving accidents an overview of approaches and problems. Ergonomics, 25(10):867–877, 1982.
[139] M. Montemerlo, J. Becker, and S. Thrun. Junior: The stanford entry in theurban challenge. Journal of Field Robotics (JFR), 25(9):569–597, September
2008.
[140] K. Mueck. Rechnergestuetzte Erkennung und Beschreibung innerstaedtischer. Strassenkreuzungen. PhD thesis, Karlsruhe Institute of Technology(KIT), 2000.
[141] K. Murphy, A. Torralba, and W. T. Freeman. Using the forest to see thetrees: A graphical model relating features, objects, and scenes. In Advancesin Neural Information Processing Systems (NIPS), 2003.
[142] V. Nedovic, A. W. M. Smeulders, A. Redert, and J. M. Geusebroek. Stages
as models of scene geometry. IEEE Trans. on Pattern Analysis and MachineIntelligence (PAMI), 32:1673–1687, 2010.
[143] A. Neubeck and L. V. Gool. Efficient non-maximum suppression. In Proc.
of the International Conf. on Pattern Recognition (ICPR), August 2006.
[144] D. Nister, O. Naroditsky, and J. R. Bergen. Visual odometry. In Proc. IEEE
Conf. on Computer Vision and Pattern Recognition (CVPR), 2004.
[145] A. Oliva and A. Torralba. Modeling the shape of the scene: a holistic representation of the spatial envelope. International Journal of Computer Vision(IJCV), 42:145–175, 2001.
[146] R. O’Toole. Gridlock: Why We’re Stuck in Traffic and What to Do About It.
2009.
[147] F. Paetzold, U. Franke, and W. Von Seelen. Lane recognition in urban environment using optimal control theory. In Proc. IEEE Intelligent Vehicles
Symposium (IV), 2000.
[148] S. Pellegrini, A. Ess, K. Schindler, and L. J. V. Gool. You’ll never walkalone: Modeling social behavior for multi-target tracking. In Proc. IEEE
International Conf. on Computer Vision (ICCV), 2009.
[149] L. D. Pero, J. Bowdish, D. Fried, B. Kermgard, E. Hartley, and K. Barnard.
Bayesian geometric modeling of indoor scenes. In Proc. IEEE Conf. on Computer Vision and Pattern Recognition (CVPR), 2012.
126

[150] J. Pilet, A. Geiger, P. Lagger, V. Lepetit, and P. Fua. An all-in-one solution togeometric and photometric calibration. In Proc. of the International Symposium on Mixed and Augmented Reality (ISMAR), 2006.
[151] M. Pollefeys. Detailed real-time urban 3d reconstruction from video. International Journal of Computer Vision (IJCV), 78(2-3):143–167, July 2008.
[152] D. Pomerleau. Ralph: Rapidly adapting lateral position handler. In Proc.
IEEE Intelligent Vehicles Symposium (IV), pages 506–511, 1995.
[153] D. Ramanan and D. Forsyth. Finding and tracking people from the bottom up.
In Proc. IEEE Conf. on Computer Vision and Pattern Recognition (CVPR),
2003.
[154] C. Rasmussen. Road shape classification for detecting and negotiating intersections. In Proc. IEEE Intelligent Vehicles Symposium (IV), 2003.
[155] L. G. Roberts. Machine perception of three-dimensional solids. PhD thesis,
Massachusetts Institute of Technology. Dept. of Electrical Engineering, 1963.
[156] S. Roth. High-Order Markov Random Fields for Low-Level Vision. PhD
thesis, Brown University, 2007.
[157] C. Rother. A new approach for vanishing point detection in architectural environments. In Proc. of the British Machine Vision Conf. (BMVC), 2000.
[158] E. Rublee, V. Rabaud, K. Konolige, and G. Bradski. Orb: an efficient alternative to sift or surf. In Proc. IEEE International Conf. on Computer Vision(ICCV), pages 2564–2571, 2011.
[159] B. Russell, A. Torralba, C. Liu, R. Fergus, and W. Freeman. Object recognition by scene alignment. In Advances in Neural Information Processing
Systems (NIPS), 2008.
[160] B. Russell, A. Torralba, K. Murphy, and W. Freeman. Labelme: A database
and web-based tool for image annotation. International Journal of Computer
Vision (IJCV), 77:157–173, 2008.
[161] A. Saxena, S. H. Chung, and A. Y. Ng. 3-D depth reconstruction from asingle still image. International Journal of Computer Vision (IJCV), 76:53–
69, 2008.
[162] A. Saxena, J. Schulte, and A. Y. Ng. Depth estimation using monocular andstereo cues. In Proc. of the International Joint Conf. on Artificial Intelligence(IJCAI), 2007.

127

B. Bibliography[163] A. Saxena, M. Sun, and A. Y. Ng. Learning 3-d scene structure from a single
still image. In Proc. IEEE International Conf. on Computer Vision (ICCV),
2007.
[164] A. Saxena, M. Sun, and A. Y. Ng. Make3d: Learning 3d scene structure froma single still image. IEEE Trans. on Pattern Analysis and Machine Intelligence(PAMI), 31:824–840, 2009.
[165] D. Scharstein and R. Szeliski. A taxonomy and evaluation of dense two-frame
stereo correspondence algorithms. International Journal of Computer Vision(IJCV), 47:7–42, 2002.
[166] G. Schindler and F. Dellaert. Atlanta world: An expectation maximization
framework for simultaneous low-level edge grouping and camera calibrationin complex man-made environments. In Proc. IEEE Conf. on Computer Vision and Pattern Recognition (CVPR), 2004.
[167] D. Schulz, W. Burgard, D. Fox, and A. Cremers. People tracking with mobile
robots using sample-based joint probabilistic data association filters. International Journal of Robotics Research (IJRR), 22(2):99–116, 2003.
[168] A. Schwing and R. Urtasun. Efficient exact inference for 3d indoor scene
understanding. In Proc. of the European Conf. on Computer Vision (ECCV),
2012.
[169] S. Se and M. Brady. Ground plane estimation, error analysis and applications.
Robotics and Autonomous Systems (RAS), 39(2):59–71, 2002.
[170] J. Shotton, J. Winn, C. Rother, and A. Criminisi. Textonboost for image understanding: Multi-class object recognition and segmentation by jointly modeling texture, layout, and context. International Journal of Computer Vision(IJCV), 81:2–23, 2009.
[171] N. Silberman, D. Hoiem, P. Kohli, and R. Fergus. Indoor segmentation andsupport inference from rgbd images. In Proc. of the European Conf. on Computer Vision (ECCV), 2012.
[172] X. Song, J. Cui, H. Zha, and H. Zhao. Vision-based multiple interacting
targets tracking via on-line supervised learning. In Proc. of the European
Conf. on Computer Vision (ECCV), 2008.
[173] B. Southall and C. J. Taylor. Stochastic road shape estimation. In Proc. IEEE
International Conf. on Computer Vision (ICCV), 2001.

128

[174] P. Sturgess, K. Alahari, L. Ladicky, and P. Torr. Combining appearance andstructure from motion features for road scene understanding. In Proc. of the
British Machine Vision Conf. (BMVC), 2009.
[175] E. B. Sudderth, A. Torralba, W. T. Freeman, and A. S. Willsky. Describing
visual scenes using transformed objects and parts. International Journal ofComputer Vision (IJCV), 77(1-3):291–330, 2008.
[176] A. Takahashi and Y. Ninomiya. Model-based lane recognition. In Proc. IEEE
Intelligent Vehicles Symposium (IV), 1996.
[177] C. J. Taylor, J. Malik, and J. Weber. A real-time approach to stereopsis andlane-finding. In Proc. IEEE Intelligent Vehicles Symposium (IV), 1996.
[178] S. Thrun, W. Burgard, and D. Fox. Probabilistic Robotics. The MIT Press,
2005.
[179] A. Torralba. Contextual priming for object detection. International Journalof Computer Vision (IJCV), 53(2):169–191, 2003.
[180] A. Torralba, K. P. Murphy, and W. T. Freeman. Sharing features: efficient
boosting procedures for multiclass object detection. In Proc. IEEE Conf. on
Computer Vision and Pattern Recognition (CVPR), 2004.
[181] Z. Tu, X. Chen, A. Yuille, and S. Zhu. Image parsing: Unifying segmentation,
detection, and recognition. International Journal of Computer Vision (IJCV),
63(2):113–140, 2005.
[182] M. Vorlander. Auralization: fundamentals of acoustics, modelling, simulation, algorithms and acoustic virtual reality. Springer, 2007.
[183] H. Wang, S. Gould, and D. Koller. Discriminative learning with latent variables for cluttered indoor scene understanding. In Proc. of the European Conf.
on Computer Vision (ECCV), 2010.
[184] X. Wang, X. Ma, and W. Grimson. Unsupervised activity perception incrowded and complicated scenes using hierarchical bayesian models. IEEE
Trans. on Pattern Analysis and Machine Intelligence (PAMI), 31:539–555,
2009.
[185] Y. Wang, L. Bai, and M. Fairhurst. Robust road modeling and tracking using condensation. IEEE Trans. on Intelligent Transportation Systems (TITS),
9(4):570–579, 2008.
[186] J. Weber, D. Koller, Q. T. Luong, and J. Malik. New results in stereo-based
automatic vehicle guidance. In Proc. IEEE Intelligent Vehicles Symposium(IV), 1995.
129

B. Bibliography[187] S. Widodo, T. Hasegawa, and S. Tsugawa. Vehicle fuel consumption andemission estimation in environment-adaptive driving with or without intervehicle communications. In Proc. IEEE Intelligent Vehicles Symposium (IV),2000.
[188] Wikipedia. Google driverless car — Wikipedia, the free encyclopedia, 2012.
[Online; accessed 06-December-2012].
[189] H. Winner, S. Hakuli, and G. Wolf.
Vieweg + Teubner, 2009.

Handbuch Fahrerassistenzsysteme.

[190] C. Wojek, S. Roth, K. Schindler, and B. Schiele. Monocular 3d scene modeling and inference: Understanding multi-object traffic scenes. In Proc. of theEuropean Conf. on Computer Vision (ECCV), 2010.
[191] C. Wojek and B. Schiele. A dynamic conditional random field model forjoint labeling of object and scene classes. In Proc. of the European Conf. on
Computer Vision (ECCV), 2008.
[192] C. Wojek, S. Walk, S. Roth, and B. Schiele. Monocular 3d scene understanding with explicit occlusion reasoning. In Proc. IEEE Conf. on Computer
Vision and Pattern Recognition (CVPR), 2011.
[193] C. Wojek, S. Walk, S. Roth, K. Schindler, and B. Schiele. Monocular visual
scene understanding: Understanding multi-object traffic scenes. IEEE Trans.
on Pattern Analysis and Machine Intelligence (PAMI), 2012.
[194] B. Wu and R. Nevatia. Detection and tracking of multiple, partially occluded
humans by bayesian combination of edgelet part detectors. International
Journal of Computer Vision (IJCV), 75(2):247–266, 2007.
[195] J. Xiao, B. C. Russell, and A. Torralba. Localizing 3d cuboids in singleview images. In Advances in Neural Information Processing Systems (NIPS),
December 2012.
[196] K. Yamaguchi, A. C. Berg, L. E. Ortiz, and T. L. Berg. Who are you with andwhere are you going? In Proc. IEEE Conf. on Computer Vision and Pattern
Recognition (CVPR), 2011.
[197] Q. Yu and G. Medioni. Multiple-target tracking by spatiotemporal montecarlo markov chain data association. IEEE Trans. on Pattern Analysis andMachine Intelligence (PAMI), 31(12):2196–2210, 2009.
[198] B. Zeisl, C. Zach, and M. Pollefeys. Stereo reconstruction of building interiors
with a vertical structure prior. In THREEDIMPVT, 2011.
130

[199] J. Zhang and H. H. Nagel. Texture-based segmentation of road images. In
Proc. IEEE Intelligent Vehicles Symposium (IV), 1994.
[200] L. Zhang, Y. Li, and R. Nevatia. Global data association for multi-object
tracking using network flows. In Proc. IEEE Conf. on Computer Vision and
Pattern Recognition (CVPR), 2008.
[201] J. Zhao, J. Katupitiya, and J. Ward. Global correlation based ground plane
estimation using v-disparity image. In Proc. IEEE International Conf. on
Robotics and Automation (ICRA), 2007.
[202] T. Zhao and R. Nevatia. Tracking multiple humans in crowded environment.
In Proc. IEEE Conf. on Computer Vision and Pattern Recognition (CVPR),
2004.
[203] L. Zhu, Y. Chen, Y. Lin, C. Lin, and A. Yuille. Recursive segmentation andrecognition templates for 2d parsing. In Advances in Neural Information Processing Systems (NIPS), pages 1985–1992, 2009.

131