A generative model for 3D urban scene understanding from movable platforms
Supplementary Material
Andreas Geiger and Martin Lauer
Department of Measurement and Control
Karlsruhe Institute of TechnologyRaquel Urtasun
Toyota Technological Institute at Chicago
rurtasun@ttic.edu{geiger,martin.lauer}@kit.edu

In this supplementary material we first present a review on sampling methods and details on the bijection we employ forlearning a non-parametric prior over the orientations. We then show inference results for all the sequences in our dataset.

1. A Review on Sampling Methods
Bayesian inference often requires the calculation of posterior distributions. Unfortunately, only in special cases (e. g.,conjugate priors) it is possible to compute analytically the posterior. Typical approximations to this computation are Laplaceapproximations and sampling. In sampling-based approaches the integral is approximated numerically. Markov chain Monte
Carlo methods (MCMC) can be used to generate samples from a complex graphical model efficiently. The basic idea is tocreate an artificial ergodic Markov chain so that the posterior distribution of interest becomes a stationary distribution of theMarkov chain. Hence, after a burn-in period sampling from the Markov chain yields samples from the posterior distribution[1].
The main challenge in MCMC methods is to create an adequate transition kernel for the Markov chain. Two major
strategies have been developed, Metropolis-Hastings and Gibbs sampling. Metropolis-Hastings [4] uses an arbitrary proposal
distribution q(x0 |x) to sample a new candidate state x0 from the current state x of the Markov chain. x0 is accepted as thenew state of the Markov chain with a certain probability A(x, x0 ), otherwise the current state x is replicated. The acceptanceprobability A(x, x0 ) is designed in such a way that the stochastic transition kernel T (·|x) defined by this procedure meets thedetailed balance condition for Markov chains, i. e.,
T (x0 |x) · p(x) = T (x|x0 ) · p(x0 )where p(·) denotes the posterior distribution of interest. The detailed balance condition ensures that p is a stationary distribution of the transition kernel T .
Gibbs sampling [2] is an alternative way to implement transition kernels, where the proposal distributions are the conditional distributions p(xi |x1 , · · · , xi−1 , xi+1 , · · · , xN ) for all i1 . Several transition kernels with the same stationary distribution can be combined by applying them in sequential order or by randomly selecting one of them in each step. Note that forthese type of transition kernel, the acceptance probability is always one.
More than just allowing stochastic inference on models of fixed size, MCMC methods are able to sample over modelsof varying size and varying topology. This is important to us since in our model the number of parameters varies with thenumber of arms in the intersection. Green [3] proposed an extension of Metropolis-Hastings, named reversible jumps, thatallows transdimensional jumps between models of different size and topology. Again, meeting the detailed balance condition
ensures that the resulting reversible jump sampler converges in distribution to the posterior distribution of interest.
For simplicity, lets consider an example where we are interested in two different model topologies with states X1 and X2
respectively. Let p1 and p2 be the posterior distribution of interest, and let π1 , π2 = 1 − π1 be priors to control the amount ofsamples from each topology. Unfortunately a direct comparison of the densities is misleading since the probability measureson X1 and X2 might be different. To overcome this problem, reversible jumps introduce additional states U1 and U2 to havea one to one mapping between the augmented state spaces τ : X1 × U1 → X2 × U2 . Using a proposal distribution of the1 here we assume x to be a vector x = (x , . . . , x )1N1form q1 (u1 |x1 ), we can create a vector (x1 , u1 ), transform it into (x2 , u2 ) applying the mapping τ and neglect u2 to obtaina candidate for x2 . The acceptance probability of a jump from x1 to x2 becomesA(x1 , x2 ) = min{1,π2 · p2 (x2 ) · q2 (u2 |x2 ) · |det(Jτ (x1 , u1 ))|}
π1 · p1 (x1 ) · q1 (u1 |x1 )where det(Jτ (x1 , u1 )) denotes the determinant of the Jacobian of τ . Analogously, we can switch from X2 to X1 using a
proposal distribution q2 (u2 |x2 ) and compute the corresponding acceptance probability. Note that it is important to implement
forward and backward steps together to meet the detailed balance condition.
When using reversible jumps, it is important to combine transition kernels that perform transitions within the present
subspace and those that jump between subspaces. Typically, one of the kernels is selected randomly in every step. Notethat if the selection probabilities are different for a transdimensional jump and its inverse jump, the ratio of the selection
probabilities has to be considered in the acceptance probability A(x1 , x2 ).

2. Non-parametric Models of Distributions on a Simplex
This section elaborates in more details on the bijection we employ to obtain a non-parametric distribution estimate over
the orientation vector o. First, lets illustrate the behavior of o for k = 3. The following figure shows different orientation
configurations. Note that for the sake of this illustration, a Mixture-of-Dirichlet distribution has been specified manually,
while in our approach we learn a multimodal prior distribution from labeled data. We will come back to the learning later inthe supplementary material (section 2.3).

2.1. A bijection between the simplex ∆k−1 and Rk−1We now show how we express a multimodal distribution over the simplex ∆k−1 via a multimodal distribution over Rk−1 .
Let o = (o1 , ..., ok )T be an orientation vector as described in the paper submission, with()
kX
k−1
ko∈∆
= R | ∀i : oi ≥ 0 ∧oi = 1(1)i=1This vector can be interpreted as a multinomial distribution and samples can be drawn from the Dirichlet distributionkY
i=1 Γ(αi )i −1oα,PkiΓ( i=1 αi ) i=1QkDir(o|α) =hence the Dirichlet distribution qualifies as a prior for o. However, since the Dirichlet distribution can not handle multiple
distinct modes for αi ≥ 1, learning a mixture of Dirichlet distributions will be neccessary to truthfully capture the datastatistics. Unfortunately, the conjugate prior of the Dirichlet distribtion has no standard form and thus it is hard to employ
in practice. Instead, we use a commonly used trick in the statistics community and assume a softmax model for o, which
implies that the preimage õ (of o) lives in Rk−1 , while o lives in ∆k−1 . This allows for the use of mixture distributions on
Rk−1 , e.g., Gaussian mixture, which has analytic solutions to all relevant quantities. In the following we give a bijectionτ (õ) : Rk−1 → ∆k−1 which provides a unique mapping between the two spaces. Using the softmax, we have for all i thattheeiexp(õi )= Pk(2)τ (õ)i = oi = Pk
j=1 exp(õj )j=1 ejwith ei = exp(õi ). The inverse mapping is more complicated. Rewriting the above equation, gives   0e1o1 − 1o1···o1 o2
eo−
1···o22   20
= .

 ..
.
..
.
.
..
..   ..   ..  .
.
0ekokok· · · ok − 1{z}
|

(3)

=O

Note that O is of rank k − 1, giving rise to infinitly many solutions e. In order to make the inverse mapping τ −1 unique wetherefor introduce an additional constraint, ek = 1, resulting in 
o1 − 1o1···o1e1−o1 o2 o2 − 1 · · ·o2   e2   −o2 = . (4)
 ..


..
.
.
.
..
..
 .
  ..   .. .
ok−1
ok−1 · · · ok−1 − 1
ek−1
−ok−1
Thus, with e the solution to Eq. 4, the inverse mapping τ −1 is given byτ −1 (o)i = õi = log ei(5)

The following plots show samples from a Dirichlet distribution in ∆2 (left) and the transformed samples in R2 :
R28R2

8

Simplex Space

Simplex Space

0.7

6

0.7

6

0.6

4

0.6

4

0.5

0.5

20.4

20.4

000.3

0.3

−20.2
0.1−40.1

0−6

0

0

0.2

0.4

0.6

0.8

−20.2

1−4
−60−8

−58

0R2

0.2

0.4

0.6

0.8

1−85−50R2

5−50R2

5−50

58Simplex Space

Simplex Space

0.7
0.6
0.5

6

0.7

64

0.6

4

0.5

2

0.4

2

0.4

00

0.3

0.3

−2

0.2

0.2

0.1

−4

0.1

0−6

00

0.2

0.4

0.6

0.8

−2

1−4
−6
0−8

−58

0R2

0.2

0.4

0.6

0.8

1−858

Simplex Space

Simplex Space

0.7

6

0.7

6

0.6

4

0.6

40.50.520.4

2

0.4
00

0.3

0.3
−20.2
0.1

−40.1

0−6000.2

0.4

0.6

0.8−20.2

1−4−60−8−5050.2

0.4

0.6

0.8

1−8

2.2. Change of Variables
Mapping probability density functions into each other is also possible by change of variables. Again, we haveexp(õi )exp(õi )= Pk−1τ (õ)i = oi = Pkexp(õ)
jj=1j=1 exp(õj ) + 1
and the Jacobian of τ (õ) is given byexp(õ1 ) − exp(2õ1 )ō · · · − exp(õ2 + õ1 )ō···dτJτ == ō · ..
..
dõ
.
.
− exp(õk−1 + õ1 )ō · · ·with ō =hP

k−1
j=1 exp(õj ) + 1

i−1− exp(õ1 + õk−1 )ō− exp(õ2 + õk−1 )ō
..
.




exp(õk−1 ) − exp(2õk−1 )ō. Lets assume now that there exists a probability density f on õ, for instance f (õ) =N (õ|µ, Σ), and also a probability density g on o. Then, by laws of change of variables these two densities are related via
g(o) =f (õ)| det(Jτ )|The following example shows how a 2-dimensional Gaussian density translates into a non-standard density in ∆2 :

2.3. Sampling a Gaussian Mixture in Rk−1 for data from ∆k−1
For each k, we use the derived bijection in order to map o to õ for each data point and learn a non-parametric multimodal
distribution on õ using a Dirichlet Process Mixture model via a transformed Gaussian Mixture Model. The following figure
illustrates, for k = 3, a sample from the posterior over õ in both Rk−1 and ∆k−1 :3. Inference Results on all 113 Video Sequences
In this section, we depict the inference results of our approach on all 113 video sequences from the experimental evaluationof the paper. All sequences, for which k is estimated correctly are marked with a green frame, while the other ones aredepicted in red. Note that in most of the latter cases, the estimated geometry is still plausible, given the observed features andthe limited angular aperture.

References[1] C. Andrieu, N. de Freitas, A. Doucet, and M. I. Jordan. An introduction to MCMC for machine learning. Machine Learning, 50(12):5–43, 2003. 1[2] S. Geman and D. Geman. Stochastic relaxation, Gibbs distributions and the Bayesian restauration of images. IEEE Transactions in
Pattern Analysis and Machine Intelligence, 6:721–741, 1984. 1[3] P. J. Green. Reversible jump Markov chain Monte Carlo computation and Bayesian model determination. Biometrika, 82:711–732,
1995. 1[4] W. K. Hastings. Monte Carlo sampling methods using Markov chains and their applications. Biometrika, 57:97–109, 1970. 1