Supplementary Material for
FollowMe: Efficient Online Min-Cost Flow Tracking
with Bounded Memory and Computation
Philip Lenz
Karlsruhe Institute of Technology

Andreas Geiger
MPI Tübingen

Raquel Urtasun
University of Toronto

lenz@kit.edu

andreas.geiger@tue.mpg.deurtasun@cs.toronto.edu

Abstract
In this supplementary material we specify further technical details and show additional results. We first provide links tothe supplementary videos showing the performance of our optimal and approximate solvers on several challenging sequencesfrom the KITTI tracking dataset. Secondly, we specify all necessary details of the association features we employ as pairwise
constraints and illustrate the logistic functions we have learned. Furthermore, we give additional results in terms of runtime
and provide an analysis of the sensitivity of the proposed model against variation of the parameters. We also show additional
quantitative and qualitative results comparing the optimal batch solution to the proposed memory and computationallybounded online variant. We conclude with a review of related algorithms for finding successive shortest paths (SSP) in a
network in order to help understanding our technical contributions.

1. Videos
We encourage the reviewers to have a look at the supplementary videos:• Qualitative Results for Cars
• Additional Qualitative Results for Cars, Pedestrians, and Cyclists.
The videos may be started by clicking on the items above .

2. Association Features
This section explains the features we use for associating detections. We start with the two appearance-based features we use:
• Color Histogram Similarity sc computes a measure of how well the histograms of both detections match:P(H1 (i) − H̄1 )(H2 (i) − H̄2 )qsc (H1 , H2 ) = P iP22i (H1 (i) − H̄1 )i (H2 (i) − H̄2 )
where
H̄k =

(1)

1 X
Hk (j)
np j

and np is the total number of histogram bins. Note that a normalization is performed by subtracting the mean H̄k in the
numerator and computing the standard deviation σH in the denominator. When we use color images, we compute thesc separately for each channel and average their values. In particular, we use the Lab color space which was designed
to approximate visual human perception and does not suffer as heavily as, e.g. the RGB color space from illumination
changes.
• Normalized Cross-Correlation: We also employed the normalized cross-correlation sx between the two boundingboxes. Changes in the scale of the object are considered by computing the correlation for a range of scales and taking
the maximum value. To handle uncertainties in the bounding box position, the template is cropped to 80% of its
original size.
1Positional-based image cues are primarily suitable for comparing objects in consecutive frames. Bounding box overlap, size,and position in the image plane are subject to perspective changes for non-adjacent frames and moving objects, considerablychanging for a longer time period. In particular, we use four positional-based cues defined as follows:• Bounding Box Overlap so is a thresholdded intersection over union (IoU) between the bounding boxes of both objects(
IoU if IoU > 0.5(2)so (b1 , b2 ) =0otherwisewith IoU =b1 ∩ b2
b1 ∪ b2• Bounding Box Size Similarity ss is the normalized sum of the absolute width and height difference1|w1 − w2 ||h1 − h2 |ss (s1 , s2 ) = 1 −+2 max(w1 , w2 ) max(h1 , h2 )(3)

• Location Similarity sp is the sum of absolute differences for the bounding box position normalized by the image
dimensions.

1 |u2 − u1 | |v2 − v1 |+(4)
sp (u1 , u2 ) = 1 −
2
wimg
himg
• Orientation Similarity sα is the normalized cosine similarity of the absolute angular differencesα (α1 , α2 ) =cos(|α1 − α2 |) + 1
2(5)

signal #1 signal #2

x-corr(a) Color Histogram Similarity(b) Cross Correlation(c) Bounding Box Overlap(d) Optical Flow Overlap(e) Positional and Size Similarity(f) Orientation Similarity

Figure 1: Association Features. Image-based ((a), (b)) and positional-based ((c), (d), (e), (f)) features used as input for
association costs within the network flow formulation.

3. Runtime

103

103

102

102

101

101

100

100

runtime [s]runtime [s]We used the training sequences of the KITTI tracking benchmark and show the mean run time and its variance to computeresults up to a particular frame, where we average across sequences. In addition to Dijkstra’s algorithm, we state the runtime
for Bellman-Ford (“BF”) as shortest path solver, which can handle the arbitrary costs of the original DAG and therefore
avoids cost conversion. For Dijkstra and Bellman-Ford, we implemented the algorithms described in [6]. As shown in Fig. 2,
our approach outperforms Dijkstra’s algorithm by factor 2. For the online approach we noticed a slight overhead but speedups up to one order of magnitude were observed. Note that the worst case complexity cannot be reduced as in the worst
case the whole predecessor map needs to be computed. However, this bound is loose, and the average case is much morefavorable and the typical scenario when considering multi-target tracking.More importantly, our memory-bounded algorithm
has a complexity independent of the sequence length and outperforms significantly in terms of runtime the algorithm of [12](see Fig. 2(c)). Furthermore, detailed run times of the modules that composed the batch solvers are given in Fig. 3. Note thatdDijkstra is called dSSP in the paper.

10−1
10−2
10−3

10−1
10−2
10−3

10−4

10−4
SSP – Bellmann-Ford

SSP – Dijkstra

SSP – odDijkstra

10−5

SSP – dDijkstra

10−5
0

100

200

300

400

500

600

700

800

900

0

100

200

300

# frames

400

500

600

700

800

900

# frames(a) Existing Baselines(b) Proposed Optimal Solvers
103
102

runtime [s]

101
100
10−1
10−2
10−3
10−4
SSP – DPSSP – mbodDijkstra

10−5
0

100

200

300

400

500

600

700

800

900

# frames(c) Approximate Solutions

Figure 2: Comparing Run Time: Batch solvers are shown as a function of the sequence length in the first two figures. As
shown in the last figure, our approach outperforms significantly [12], named SSP-DP in terms of runtime. We use a window
size of τ = 10 for mbodSSP and evaluate all methods on a the original network without pruning any edges.

0.011s - Extract SP
0.131s - Residual Graph
640.233s - Bellman-Ford
640.376s - SSP-Bellmann-Ford (total)

0.000s - Cost Conversion
0.012s - Extract SP
0.107s - Residual Graph
0.591s - DAG-SP
10.041s - Graph Conversion
23.453s - Dijkstra
34.204s - SSP-Dijkstra (total)

0.000s - Cost Conversion
0.010s - Extract SP
0.591s - DAG-SP
7.393s - dDijkstra
11.785s - dDijkstra Update
19.780s - dDijkstra (total)

Figure 3: Run Time Analysis of the Different Batch Solvers: SSP with Bellman-Ford (top left), Dijkstra (top right),
dDijkstra (dSSP in the paper) (bottom) as shortest path solver. The Bellman-Ford algorithm does not need to convert thegraph and therefore spends all resources relaxing edges. Our dynamic algorithm (dDijkstra) decreases the run time necessary
to find the shortest path by factor 3 when comparing to the standard Dijkstra algorithm. Note that there is also a slightoverhead for creating the residual graph (Graph Conversion/Update).

4. Sensitivity to the Parameters
Fig. 4 depicts the logistic functions learned for the different features. As shown in Fig. 5 and Fig. 6 the performancedoes not depend too much on the specific value of the parameters. The learned values for computing the final edge costs are
depicted in Table 1. Fig. 7 shows the performance of our memory bounded algorithm mbodSSP as a function of the window
size τ (i.e., history length). Note that the curves are very flat, and good performance is achieved with a small window. The
results for an infinite history length (i.e., batch method) are shown on the right hand side.
orientation
cross-correlation
color histogram
location

optical flowbounding box overlap
bounding box size

similarity feature sl

1.0
0.8
0.6
0.4
0.2
0.0
0.0

0.2

0.4

0.6

0.8

1.0

normalized similarity
Figure 4: Similarity Features. Logistic functions learned that transform each raw feature l (e.g., bounding box IOU) into
an association score sl (similarity). We learn all logistic functions via logistic regression on the KITTI training set using the
ground truth associations.

FEATURE

wl
ol

en

ex

det

α

over

5.0 5.0 21.5 1.5 5.0
0.0 0.0 -0.5 1.0 -0.75

flow βsize color x-corr

loc

1.0
0.0

1.25 8.0 8.4
0.625 -0.4 0.0

9.25
-0.8

6.5
-0.01

Table 1: Model parameters. This table shows the weight wl and offset ol of the logistic function for each feature l which
we kept fixed during all our experiments. The robustness of each feature l against variation of its weight value wl is shownin Fig. 5 and Fig. 6 for different values of wl .

F1

MT

precision

1.0

1.0

0.8

0.8

0.6

0.6

0.4

0.4

0.2

0.2

0.0

recall

MOTA

0.0
0

5

10 15 20 25 30 35 40 45

05weight wl

weight wl(b) Detection(c) Bbox Overlap

1.0

1.0

0.8

0.8

0.6

0.6

0.4

0.4

0.2

0.2

0.0

10 15 20 25 30 35 40 45

0.0
0

5

10 15 20 25 30 35 40 45

05

10 15 20 25 30 35 40 45

weight wl

weight wl(d) Bbox Size(e) Location

1.0

1.0

0.8

0.8

0.6

0.6

0.4

0.4

0.2

0.2
0.0

0.0
0

5

10 15 20 25 30 35 40 45

weight wl(f) Orientation

0

5

10 15 20 25 30 35 40 45

weight wl(g) Flow Overlap

Figure 5: Robustness of Detection and Positional Features against Variation of Parameters. This figure shows the performance for different weight values on the KITTI training set using dSSP. While varying one parameter, all other parameters
are kept fixed (c.f. Table 1).

F1

MT

precision

recall

1.0

1.0

0.8

0.8

0.6

0.6

0.4

0.4

0.2

0.2

0.0

MOTA

0.0
0

5

10 15 20 25 30 35 40 45

05

10 15 20 25 30 35 40 45

weight wl

weight wl(b) Color Histogram(c) Cross-Correlation

F1
FAR

MT
ML

Id-Switches
Fragmentations

1.0

750

0.8

600

0.6

450

0.4

300

0.2

150

0.0
100

101

102

τ

(a) KITTI (car)

0
103

MOTA
MOTP

recallprecision

F1
FAR

MT
ML

Id-Switches
Fragmentations

1.0

750

0.8

600

0.6

450

0.4

300

0.2

150

0.0
100

101

102

Id-Switches/Fragmentations

recallprecision

MOTA/MOTP/recall/precision/F1/FAR/MT/ML

MOTA
MOTP

Id-Switches/Fragmentations

MOTA/MOTP/recall/precision/F1/FAR/MT/ML

Figure 6: Robustness of Appearance-based Features against Variation of Parameters. This figure shows the performancedSSP for different weight values on the KITTI training set. While varying one parameter, all other parameters are kept fixed(c.f. Table 1).

0
103

τ

(b) PETS (pedestrian)Figure 7: Performance for Different History Lengths. We evaluated the performance of mbodSSP for different values of
its history length τ on the whole KITTI training set and PETS S2.L1. Result for τ → ∞ are given on the very right of theplot.

5. Additional Quantitative Results
In this section we provide the full result tables with all metrics employed in the literature [5, 10] for both our methods
and the baselines on KITTI (Table 2 + 3) as well as PETS 2009 (5) dataset. Note that our approach performs better thancompeting approaches in almost all metrics.

MOTA
MOTP
MODA
MODP
Recall
Prec.
F1
FAR
MT
PT
ML
TP
FP
Misses
IDS
Frag.

HM

[3]

[11]

[12]

[8]

mbodSSP

SSP

mbodSSP*

SSP*

0.42
0.78
0.42
0.53
0.43
0.97
0.60
0.048
0.077
0.50
0.42
15293
535
20121
12
578

0.35
0.75
0.36
0.54
0.50
0.77
0.61
0.46
0.11
0.56
0.34
17734
5161
17733
223
624

0.48
0.77
0.48
0.58
0.54
0.90
0.67
0.18
0.14
0.52
0.34
19057
2045
16401
125
401

0.44
0.78
0.52
0.54
0.46
0.96
0.62
0.053
0.11
0.49
0.39
16113
588
19287
2738
3241

0.52
0.78
0.52
0.58
0.54
0.95
0.69
0.083
0.14
0.52
0.35
19308
923
16139
33
540

0.52
0.78
0.52
0.59
0.56
0.93
0.70
0.14
0.15
0.55
0.30
19909
1588
15506
0
708

0.54
0.78
0.54
0.59
0.58
0.94
0.71
0.11
0.21
0.51
0.27
20447
1279
15034
7
717

0.67
0.79
0.67
0.66
0.78
0.88
0.83
0.34
0.34
0.55
0.10
28623
3765
8022
117
894

0.67
0.79
0.67
0.67
0.80
0.87
0.83
0.40
0.41
0.51
0.090
29714
4500
7279
194
977

Table 2: Comparison of the proposed methods to four state of the art methods and a HM baseline implementation on KITTI(car) [9] using DPM detections. An asterisk in the method name indicates usage of Regionlet detections.

MOTA
MOTP
MODA
MODP
RecallPrecision
F1
FAR
MT
PT
ML
TP
FP
MissesIDS
Fragmentations[11]

mbodSSP

SSP

0.36
0.75
0.37
0.76
0.47
0.82
0.60
0.56
0.080
0.39
0.53
27568
6221
31185
221
1011

0.13
0.67
0.13
0.16
0.33
0.62
0.43
0.42
0.024
0.44
0.54
7641
4620
15653
4
929

0.16
0.67
0.16
0.17
0.37
0.64
0.46
0.43
0.048
0.50
0.45
8513
4830
14791
111
1134

Table 3: Comparison of the proposed methods one state of the art method on KITTI (pedestrian) [9] using DPM detections.

MOTA
MOTP
MODA
MODP
Recall
Prec.
F1
FAR
MT
PT
ML
TP
FP
Misses
IDS
Frag.

[2]

[3]

EKF [11][11]

mbodSSP

SSP

0.81
0.76
n/a
n/a
n/a
n/a
n/a
n/a
0.83
0.17
0.0
n/a
n/a
n/a
15
21

0.96
0.79
n/a
n/a
n/a
n/a
n/a
n/a
0.96
0.04
0.0
n/a
n/a
n/a
10
8

0.68
0.77
n/a
n/a
0.70
0.98
0.82
0.08
0.39
0.57
0.04
n/a
65
1173
25
30

0.91
0.80
n/a
n/a
0.92
0.98
0.95
0.07
0.91
0.05
0.04
n/a
59
302
11
6

0.89
0.87
0.89
0.87
0.90
0.99
0.94
0.057
0.89
0.11
0.0
4153
45
461
7
100

0.91
0.87
0.91
0.87
0.92
0.99
0.95
0.067
0.89
0.11
0.0
4247
53
367
23
100

Table 4: Comparison of the proposed method to three baselines on PETS 2009 [7].

τ
MOTA
MOTP
F1
FAR
MT
ML
IDS
Frag.

5
0.50
0.78
0.69
0.15
0.14
0.30
2
703

10
0.52
0.78
0.70
0.14
0.15
0.30
0
708

15
0.48
0.78
0.68
0.14
0.16
0.34
0
690

20
0.49
0.78
0.69
0.14
0.17
0.33
0
701

50
0.51
0.78
0.70
0.14
0.18
0.30
4
710

100
0.52
0.78
0.71
0.14
0.15
0.26
5
712

Table 5: Comparison for different values for the approximation parameter τ .

6. Additional Qualitative Results
In this section, we show additional qualitative results for several sequences from the KITTI tracking benchmark (Fig. 8– 13). Additionally, we show how our method performs when tracking cars, pedestrians as well as cyclist in challenging
crowded scenarios (Fig. 14+15). For further details, we encourage the reviewers to have a look at the supplementary videos:• Qualitative Results for Cars
• Additional Qualitative Results for Cars, Pedestrians, and Cyclists.
The videos may be started by clicking on the items above or any of the respective images in the related figures.
All figures show results for the optimal solution (left) and our approximate memory-bounded approach (right). We startby discussing notably good results (Fig. 8 – 10) and review differences between the optimal and approximate solution as well
as some failure cases (Fig. 11 – 13). All examples are discussed in the caption of the respective figure.

Figure 8: Qualitative Results for the Optimal (left) and our Approximate Solution (right). Far away objects are welltracked. Track 13/11 is followed for 3.7s and not confused with several parking cars.

Figure 9: Qualitative Results for the Optimal (left) and our Approximate Solution (right). Objects are tracked despite
sharp turns. Significantly changing bounding box sizes and appearance do not lead to track interruption. (track 3/0)

Figure 10: Qualitative Results for the Optimal (left) and our Approximate Solution (right). Preceding objects in crowded
scenes are well tracked. Track 3/1 is followed for 9.5s

Figure 11: Qualitative Results for the Optimal (left) and our Approximate Solution (right). Changes in illumination
and resulting ambiguous detections (middle) may lead the approximate solution to terminate a track due to missing futureevidence. In contrast, the optimal solution tracks the preceding car for 37.2s.

Figure 12: Qualitative Results for the Optimal (left) and our Approximate Solution (right). Challenging intersection
scenarios lead to qualitatively good results. The limited optimization window for the approximate solution may also preventchanges for parts of trajectory outside of this window. Due to this approximation, track 9/12 is not fragmented for mbodSSP.

Figure 13: Qualitative Results for the Optimal (left) and our Approximate Solution (right). Missing future evidence forthe approximate solution may lead to tracks that start later when compared to the optimal solution (track 76/4). This happens
primarily for detections with a low score for the early part of the trajectory.

Figure 14: Qualitative Results for the Optimal (left) and our Approximate Solution (right). For crowded inner-city
scenes, objects of different classes (cars, pedestrians, cyclists) are tracked robustly.

Figure 15: Qualitative Results for the Optimal (left) and our Approximate Solution (right). For groups of interacting pedestrians, tracks are correct even for partly occluded objects. Very high occlusions for several frames may lead tointerrupted tracks.

7. A review on Network Algorithms for Shortest Paths Computation
In this section, we discuss shortest path solvers for graphs with arbitrary costs and no negative cycles (Algo. 1), positive
costs only (Algo. 2) as well as algorithms for finding successive shortest paths in both cases (SSP Algo. 3 for arbitrary costs,
KSP Algo. 4 for positive costs only).
Graphs with Arbitrary Costs We start our discussion by describing the Bellman-Ford (BF) algorithm (Algo. 1), which
is typically called at each SSP iteration for computing the shortest path on the residual graph Gr (f ). BF is based on theprinciple of relaxation, in which an upper bound of the correct distance to the source for each node is gradually replaced bytighter bounds (by computing the predecessor and its distance) until the optimal solution is reached. To achieve optimality
the BF algorithm relaxes all edges in the graph for |V | − 1 iterations, where |V | denotes the number of vertices in the graph.
In each of these repetitions, the number of vertices with correctly calculated distances grows, from which it follows thateventually all vertices will have their correct distances, even before the |V | − 1’th repetition. In contrast to the originallyproposed BF algorithm, current implementations consider this behavior by terminating the algorithm early when no changes
between two iterations are detected anymore.
Algorithm 1: Bellman-Ford [6, p.651ff.]
Input: Graph G, Costs C, Source s
Output: Predecessor Map π, Distance Map d// set π(u) = Unkown, d(u) = ∞, u ∈ |V | \ s
1 π, d ← InitializeSingleSource(G,s)
2 for i ← 1, . . . , |V | − 1 do
3foreach edge (u, v) ∈ G do
4π(v) ← Relax(π(v), (u, v), c(u, v))// check for negative cycles
5 foreach edge (u, v) ∈ G do
6
if d(v) > d(u) + c(u, v) then// a negative cycle was detected
7
RaiseError(“negative cycle”)
8 return π, dWhile the BF algorithm is able to compute a single trajectory with lowest cost, in multi-target tracking we are interested
in recovering the optimal set of trajectories. In the following, we review how to compute the optimal set of trajectories bymeans of SSP (see Algo. 3) for a given example. Let us consider the directed acyclic graph (DAG) in Fig. 16(a) which
specifies an instance of the network flow problem for four frames and three detections per frame. First, we relax all edges by
traversing the graph from left-to-right, which is illustrated in Fig. 16 (b)+(c) for the first and second time step. This allows
to recover the first optimal trajectory depicted in green in Fig. 16(d). We refer to this algorithm as DAG-SP as stated in [6, p.
655]. An alternative at this point is to remove all edges from this trajectory and run the algorithm again [12]. However, thisgreedy version of the algorithm does not guarantee optimality, as shown in Fig. 16(e) where some of the edges are absent in(k)
the graph. Instead, we introduce a residual graph Gr (Fig. 16(f)) by inverting the edges of the previously found optimal
trajectory. The resulting graph is, however, not a DAG anymore. A slight improvement of the approximate greedy solution
can be achieved by considering backward-pointing edges once by traversing through the graph against the direction of theinitial DAG [12]. In the following, we refer to this heuristic approximation as dynamic programming (DP). Instead, the SSP
algorithm applies BF again on the residual graph (Fig. 16(g)) yielding the second shortest path and preserving optimality.
The process finishes when a newly found shortest path has positive costs, i.e., it can not further reduce the total cost. The final
trajectories shown in Fig. 16(i) are recovered by extracting all backward edges from the most recent residual graph, starting
the back-tracking procedure at the target node.
Graphs with Positive Costs After stating the SSP algorithm for graphs with arbitrary edge weights, we continue our
exposition with the KSP algorithm [4, 13, 14] for a graph with positive costs only. Since the original tracking problem
contains negative edge weights, an initial conversion of the graph is required. This can be done after initially running theDAG-SP algorithm for the topologically ordered graph, resulting in a predecessor map containing the shortest path to every

Algorithm 2: Dijkstra’s Algorithm [6, p. 658ff.]
Input: Graph G, Source s, Costs c
Output: Predecessor Map π, Distance Map d// set π(u) = Unkown, d(u) = ∞, u ∈ |V | \ s
1 π, d ← InitializeSingleSource(G,s)
2 S ←∅
3 Q ← edges(G)4 while ¬ empty(Q) do
5u ← NodeWithMinDistance(Q)6S ← S ∪ {u}7foreach node v ∈ Neighbors(G,u) do// Check if u is a better predecessor for v
8π(v) ← Relax(u,v,c)9
if d(v) > d(u) + c(u, v) then10d(v) ← d(u) + c(u, v)
11 return π,dAlgorithm 3: Successive shortest-path (SSP) [1]
Input: Detections X = {xi }, Source s, Target t
Output: Set of trajectory hypotheses T = {Tk }// construct graph from observations
1 G(V, E, C, f ) ← X
2 f (G) ← 0
3 Gr (f ) ← G(f )// find k-th shortest path
4 while C(γk ) < 0 do// using any SP solver
5γk ← FindShortestPath(Gr (f ), s, t)// Revert edges for Gr (f ) along γk
6
Gr (f ) ← RevertEdges(Gr (f ),γk )7 return T// invariant nodes// min-priority queue// initialize flow to 0// initialize Gr (f ) as a DAG

0node of the graph. Exploiting this predecessor map, arbitrary edge weights Ci,j ∈ R can be converted to weights Ci,j
∈ R+
0
by
0
Ci,j
= Ci,j + d(i) − d(j) ∀ei,j ∈ E(6)with d(i) the distance on the shortest path from the source to node i. This results in a graph with only positive costs (Fig. 17).
0
Edges on a shortest path of this converted graph have a weight Ci,j= 0 describing an arborescence Γ [15, p. 126ff.]. An
example of this conversion is depicted in Fig. 18. Reducing costs in this way must be performed for every residual graph.
However, the runtime for this step is negligible compared to computing the shortest path.
We continue by reviewing KSP and start with Dijkstra’s algorithm for finding shortest paths as stated in Algo. 2. In each(k)
KSP iteration, Dijkstra is initially called on the residual graph Gr . As BF, Dijkstra is based on the principle of relaxation.
0
Since the minimum cost of an edge is guaranteed to be Ci,j = 0, the algorithm exploits this property as a lower bound forthe best shortest path. Starting at the source node, a priority queue is maintained and in every iteration all edges from themost promising node u to its successors v are relaxed. For every node u taken from the queue, the final shortest path was
determined. Consequently, while establishing a particular s-t path, the algorithm may terminate early after taking the target
node from the queue. However, within the KSP algorithm the shortest path to every node must be computed as mentioned
above, whereas an early termination may leave the predecessor map in an incomplete state.
(k)After detecting a shortest path on Gr , an iteration of the KSP algorithm is continued by converting again the edge costs

Algorithm 4: K-Shortest Paths (KSP) [4, 13]
Input: Detections X = {xi }, Source s, Target t
Output: Set of trajectory hypotheses T = {Tk }1 G(V, E, C, f ) ← ConstructGraph(X , s, t)
2 f (G) ← 0
3
45// DAG// initialize flow to 0(0)

Gr (f ) ← G(f )(0)π (0) ← DAG-SP(Gr (f ))// encode arborescence in residual graph(0)// shortest path in DAG(0)

Gr (f ) ← ConvertEdgeCost(Gr (f ), π (0) )// Revert edges along shortest path
(1)

(0)

Gr (f ) ← ComputeResidualGraph(Gr (f ), π (0) )// find k-th shortest path
7 k ←08 while 1 do
9k ←k+1
6

10
11
12

(k)

γ (k) , π (k) ← Dijkstra(Gr (f ))// shortest path(k)(k)
Gr (f ) ← ConvertEdgeCost(Gr (f ), π (k) )
(k)
(k+1)
(f ) ← ComputeResidualGraph(Gr (f ), γ (k) )Gr// evaluate converted costs
Pk13
if i=1 cost(γ (i) ) > | cost(γ (0) )| then14
break
15 return T(k)of Gr according to Eq. 6 resulting in a graph containing the arborescence0Γ = G(k)r \ {E | Ci,j 6= 0}.
(k+1)

(7)

Finally, the subsequent residual graph Gr
is computed according to [13] by reverting the direction of edges along theshortest path γ (k) . While for the original graph the SSP algorithm terminated after finding a path with positive costs, the KSP
Pk
algorithm for the converted problem finishes if the sum of the total costs i=1 cost(γ (i) ) are higher compared to the first
iteration | cost(γ (0) |. The KSP algorithm is summarized as Algo. 4.
Comparing the time complexity of both SSP and KSP, the differences come from the time complexities of the shortest
path solver, which must be repeated nK + 1 times for nK objects present in the scene. The total complexity of the BF
algorithm is O(|V ||E|), where |V | is the number of vertices and |E| is the number of edges. Basically, BF relaxes all edges
as many times as vertices exist in the graph to guarantee the shortest path to every node. This is typically too expensive forreal-world applications. In contrast, the lower bound and the priority queue used in Dijkstra’s algorithm reduce the worstcase complexity, depending on the complexity for queue operations. Using an efficient Fibonacci heap for this task results
in a time complexity of O(|E| + |V | log(|V |)) resulting in KSP (O(nK (|E||V | log(|V |))) being more efficient than SSP(O(nK |V ||E|)). The non-optimal DP algorithm [12] still saves log(|V |) operations over using KSP.

(a) Original Graph(b) DAG-SP (I)(c) DAG-SP (II)(d) Shortest Path(e) Non-optimal(f) Residual Graph(g) Dijkstra(h) Back Tracking(i) Optimal Solution

Figure 16: Illustration of the SSP Algorithm. The original problem is depicted in (a). Dynamic programming relaxes the
red edges in (b) and (c) yielding the shortest path in the DAG, depicted in green in (d). Simply removing this path and rerunning the algorithm violates optimality as shown in (e). Instead, a SSP strategy on the residual graph (f) allows for finding
the optimal solution (g+h). Backward pointing edges in the residual graph (h) encode trajectories for the original problem (i).

(a) Original Costs(b) Converted Costs0
Figure 17: Cost Conversion. For an edge between the nodes u and v, costs Cu,v ∈ R can be converted into Cu,v=+Cu,v + d(u) − d(v) ∈ R0 . Therefore, the distance on the shortest path d(·) from the source to both nodes u and v must
known.

(a) Original Graph(b) Shortest Path(c) Converted Graph

Figure 18: Cost Conversion Example. For the graph in (a) with negative costs, the shortest s-t path is computed (blue edgesin (b)). Numbers in the nodes state the distance on the shortest path for this particular node. The graph is converted intoa graph without negative costs according to Eq. 6. The resulting graph in (c) contains the arborescence Γ in blue which is
identical with the shortest s-t path in this case.

References[1] R. K. Ahuja, T. L. Magnanti, and J. B. Orlin. Network Flows. Prentice Hall, 1993. 15[2] A. Andriyenko and K. Schindler. Multi-target tracking by continuous energy minimization. In Proc. IEEE Conf. on
Computer Vision and Pattern Recognition (CVPR), 2011. 9[3] A. Andriyenko, K. Schindler, and S. Roth. Discrete-continuous optimization for multi-target tracking. In Proc. IEEE
Conf. on Computer Vision and Pattern Recognition (CVPR), 2012. 8, 9[4] J. Berclaz, F. Fleuret, E. Turetken, and P. Fua. Multiple object tracking using k-shortest paths optimization. IEEE Trans.
on Pattern Analysis and Machine Intelligence (PAMI), 33(9):1806–1819, 2011. 14, 16[5] K. Bernardin and R. Stiefelhagen. Evaluating multiple object tracking performance: The clear mot metrics. Journal on
Image and Video Processing (JIVP), 1:1–10, 2008. 8[6] T. H. Cormen, C. Stein, R. L. Rivest, and C. E. Leiserson. Introduction to Algorithms. McGraw-Hill Higher Education,
2001. 3, 14, 15[7] A. Ellis and J. M. Ferryman. PETS 2010 and PETS 2009 evaluation of results using individual ground truthed single
views. 2010. 9[8] A. Geiger, M. Lauer, C. Wojek, C. Stiller, and R. Urtasun. 3D traffic scene understanding from movable platforms.
IEEE Trans. on Pattern Analysis and Machine Intelligence (PAMI), 36(5):1012–1025, 2014. 8[9] 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. 8[10] Y. Li, C. Huang, and R. Nevatia. Learning to associate: HybridBoosted multi-target tracker for crowded scene. In Proc.
IEEE Conf. on Computer Vision and Pattern Recognition (CVPR), 2009. 8[11] A. Milan, S. Roth, and K. Schindler. Continuous energy minimization for multitarget tracking. IEEE Trans. on PatternAnalysis and Machine Intelligence (PAMI), 36(1):58–72, 2014. 8, 9[12] H. Pirsiavash, D. Ramanan, and C. C. Fowlkes. Globally-optimal greedy algorithms for tracking a variable number ofobjects. In Proc. IEEE Conf. on Computer Vision and Pattern Recognition (CVPR), 2011. 3, 8, 14, 16[13] J. W. Suurballe. Disjoint paths in a network. Networks, 4(2):125–145, 1974. 14, 16[14] J. W. Suurballe and R. E. Tarjan. A quick method for finding shortest pairs of disjoint paths. Networks, 14(2):325–336,
1984. 14[15] W. Tutte. Graph Theory. Cambridge Mathematical Library. Cambridge University Press, 2001. 15