Supplemental Material forLost! Leveraging the Crowd for Probabilistic Visual Self-Localization
Marcus A. Brubaker
TTI Chicagombrubake@cs.toronto.edu

Andreas Geiger
KIT & MPI Tübingengeiger@kit.edu

Raquel Urtasun
TTI Chicago
rurtasun@ttic.edu

1. Overview
This document includes supplementary material to Lost! Leveraging the Crowd for Probabilistic Visual SelfLocalization. Included are detailed versions of the algorithms and other results.

2. Additional Results
Included in this document are additional results which could not fit in the main paper. See Figure 1 for frames fromthe remaining training sequences and Figures 2 and 3 for frames from the test sequences where ground truth data is
not availble.

3. GMM Simplification
PAs described
P in the appendix of the main paper, given a Gaussian mixture model f (x) = a πa N (x|µa , Σa ) weseek g(x) = b ωb N (x|µb , Σb ) with the least number of components such that D(f kg) <  where D(f kg) is the KL
divergence. We begin with g(x) = f (x) and successively remove the lowest weight component of g(x) and updatethe remaining components to better fit f (x) so long as the KL divergence (or its upper bound) is below the threshold
. As explained in the paper, experimentation found an optimal value of this parameter to be  = 10−2 nats for ourproblem.
The upper bound [1] used isX
φa,bD̂(φ, ψ, f, g) =φa,b log+ D(fa kgb )(1)
ψa,ba,bwhere φa,b and ψa,b are variational parameters andD(fa kgb ) =1T −1log |Σb | − log |Σa | + T r(Σ−1b Σa ) − d + (µa − µb ) Σb (µa − µb )2(2)is the KL divergence between the Gaussian mixture components fa and gb . To minimize this objective (and improvethe fit of a given approximation) we note that the global optima can be found for each set of parameters individually.

1

Figure 1. Selected Frames: Inference results for the remaining training sequences. The left most column shows the full map
region for each sequence, followed by zoomed in sections of the map showing the posterior distribution over time. The black lineis the GPS trajectory and the concentric circles indicate the current GPS position. Grid lines are every 500m.

That is, by setting the derivatives of (1) equal to zero and solving, one can find!−1XXµb =φa,bφa,b µaaa!−1Σb=X

φa,ba

ωb=

X

X

φa,b Σa + (µa − µb )(µa − µb )T



a

φa,ba

φa,b0a0 φa ,b
ψa,b exp (−D(fa kgb ))φa,b = πa P
00b0 ψa,b exp (−D(fa kgb ))PPPNote that it is necessary to enforce the constraints b ωb = 1, b φa,b = πa and a ψa,b = ωb through the use ofLagrange multipliers. This procedure is summarized in Algorithm 1.
ψa,b= ωb P

Algorithm 1 GMM Simplification
P
Input: f (x) = a πa N (x|µa , Σa )Initialize g = f , φ ← diag(π), ψ ← diag(π)
loopSelect a component to remove b̂ = arg minb0 ωb0for b 6= b̂ doRemove b̂ from the variational parametersωb̂ωb0 ← ωb + |g|−1µ0b ← µbΣ0b ← Σbφa,b0∀a: φ0a,b ← φa,b + |g|−1φ00∀a: ψa,b← ωb0 P 0a,bφ0a0 |baend forwhile D̂(φ0 , ψ 0 , f, g 0 ) ≥  and not converged doMinimize D̂(φ0 , ψ 0 , f, g 0 ) w.r.t. φ0 , ψ 0 , ω 0 , µ0 , Σ0 .
P
∀b 6= b̂: ωb0 ← a φ0a,b
φ00∀a, b 6= b̂: ψa,b
← ωb0 P 0a,b
φ 0aa ,bψ 0 exp(−D(fa kgb0 ))∀a, b 6= b̂: φ0a,b ← πa P a,b00 exp(−D(fa kg ))0 ψb∀b 6= b̂: µ0b ←P0a φa,ba,b
−1Pb00a φa,b µaP
−1 P
0000 T∀b 6= b̂: Σ0b ←a φa,ba φa,b Σa + (µa − µb )(µa − µb )end whileif D̂(φ0 , ψ 0 , f, g 0 ) ≥  thenReturn: gelseg ← g0
end ifend loop

4. Filtering Algorithm
Due to space constraints, the equations necessary to implement the filtering algorithm could not be included. Instead, they are presented here in Algorithm 2.
The function used to determine whether to use a Monte Carlo approximation or an analytic approximation is:Zg(µ, Σ) = p(ut |ut−1 , st−1 )N (st−1 |µ, Σ)dst−1(3)In the model we have thatZ `ut−1

p(ut |ut−1 , st−1 ) = ξut ,ut−1`ut−1+`uN (x|aTd st−1 , aTd Σxut−1 ad )dx(4)where ξut ,ut−1 is a constant. Substituting this in we haveZ Z `ug(µ, Σ)=t−1+`uN (x|aTd st−1 , aTd Σxut−1 ad )N (st−1 |µ, Σ)dxdst−1

ξut ,ut−1`ut−1Z `ut−1+`u Z= ξut ,ut−1`ut−1Z `ut−1=

ξut ,ut−1`ut−1=N (x|aTd st−1 , aTd Σxut−1 ad )N (st−1 |µ, Σ)dst−1 dx+`uN (x|aTd µ, aTd (Σxut−1 + Σ)ad )dxξut ,ut−1 Φ(`ut−1 + `u |m, s2 ) − Φ(`ut−1 |m, s2 )where m = aTd µ, s2 = aTd (Σxut−1 + Σ)ad and Φ(x|m, s2 ) is the CDF of a univariate normal distribution with meanm and variance s2 evaluated at x.

References[1] J. Hershey and P. Olsen. Approximating the Kullback-Leibler Divergence Between Gaussian Mixture Models. In ICASSP,
volume 4, pages 317–320, 2007. 1

Algorithm 2 Filter
Input: Posterior at t − 1, {Put−1 , Mt−1u }, and observation at t, yt
Initialize mixtures, Mtu ← ∅, for all u
for all streets ut−1 dofor all streets ut reachable from ut−1 do
M0 ← ∅for all (ω, µ, Σ) ∈ Mt−1
ut−1 dodif k dµ g(µ, Σ)k < η thenAnalytically approximate cpred N (µpred , Σpred )cpred ← p(ut |ut−1 , st−1 = µ)µpred ← Aut ,ut−1 µ + but ,ut−1
Σpred ← Σxut + Aut ,ut−1 ΣATut ,ut−1else
Sample to compute cpred N (µpred , Σpred )for j = 1, . . . , M do(j)st−1 ∼ N (µ, Σ)(j)(j)
st ← Aut ,ut−1 st−1 + but ,ut−1end forPM(j)cpred ← M −1 j=1 p(ut |ut−1 , st−1 )
P(j)
(j)
M
µpred ← (M cpred )−1 j=1 p(ut |ut−1 , st−1 )st(j)PM p(ut |ut−1 ,st−1 ) (j)(j)(st − µpred )(st − µpred )TΣpred ← Σxut + j=1
M cpredend ifIncorporate yt to compute cupd N (µupd , Σupd )−1−1
Σupd ← MTut Σyut −1 Mut + Σpred−1µupd ← Σupd MTut Σyut yt + Σ−1
pred µpredωcpred |Σupd |0.5
12cupd ← |Σpred−ky−Mµkyy 0.5 exp
tupred
T0.5t
2
Σut +Mut Σpred Mut| |Σut |if ut 6= ut−1 thenAdd (cupd , µupd , Σupd ) to M0else
Add (cupd , µupd , Σupd ) to Mtut
end ifend forCompute (c, µ, Σ) to approximate components of M0 and add to Mtut
end forend forfor all streets u do
Set Put to the sum of the weights of mixture Mtu
Normalize the weights of mixture Mtu`uif |Mt | < 10 meters thenu
Simplify Mtu with Algorithm 1
end ifend forP
Normalize Put so that u Put = 1.
For all u, if Put < 10−50 set Put ← 0 and Mtu ← ∅Return: Posterior at t, {Put , Mtu }Figure 2. Selected Frames of Test Sequences: Inference results for the testing sequences. The left most column shows the fullmap region for each sequence, followed by zoomed in sections of the map showing the posterior distribution over time. GPS data
is unavailable for these sequences. Zooming is done based on a smoothed bounding box of the dominant modes of the posterior.
Grid lines are every 500m.

Figure 3. Selected Frames of Test Sequences: Inference results for the testing sequences. The left most column shows the fullmap region for each sequence, followed by zoomed in sections of the map showing the posterior distribution over time. GPS data
is unavailable for these sequences. Zooming is done based on a smoothed bounding box of the dominant modes of the posterior.
Grid lines are every 500m.