FollowMe: Efficient Online Min-Cost Flow Tracking
with Bounded Memory and Computation
Philip Lenz , Andreas Geiger , Raquel Urtasun
1Karlsruhe Institute of Technology
lenz@kit.edu

Abstract

3

MPI for Intelligent Systems, Tübingen
andreas.geiger@tue.mpg.de

Problem Statement
frame with xi = (frame, position, size, appearance, detector score)• Find the set of optimal trajectories T = {Tk } by maximizingQ
the posterior probability p(T |X ) = p(T ) i(xi|T )Graph Construction

Qualitative Results

Quantitative Results

Contribution

Pair-wise prior over trajectories
Yp(T ) ∝Ψ(T )T ∈T

2D Bounding Boxes as Input Detections [2]Unary factors

HM [1] [4] [5] [3] mbodSSP SSP mbodSSP* SSP*
MOTA 0.42 0.35 0.48 0.44 0.52 0.52 0.54
0.67
0.67
0.79
0.79
MOTP 0.78 0.75 0.77 0.78 0.78 0.78 0.78
F10.60 0.61 0.67 0.62 0.69 0.70 0.71
0.83
0.83
0.34
0.40
FAR 0.048 0.46 0.18 0.053 0.083 0.14 0.11
MT0.077 0.11 0.14 0.11 0.14 0.15 0.21
0.34
0.41
ML0.42 0.34 0.34 0.39 0.35 0.30 0.270.10 0.090
07117
194IDS
12 223 125 2738 33Frag. 578 624 401 3241 540
708
717
894
977

can be formulated as a network flow problem.
• Standard solvers can be leveraged to retrieve the global optimum.
• Their formulation solves for the globally optimal trajectories including
their number, and hence implicitly solves the model selection problem.

Dynamic Successive Shortest Path Algorithm

Piif ∃ Tk ∈ T ∧ i ∈ Tk
1 − Pi otherwisep(xi|T ) =• Solves the data association problem optimally, reuses computation.

http://www.cs.toronto.edu/~boundTracking• Given a set of detections X = {xi} (car, pedestrian, and cyclist) per • Zhang et al. [7] showed how data association with pairwise energies

Observation model(• Dynamic version of the successive shortest-path algorithm.

University of Toronto
urtasun@cs.toronto.edu
3[T ∩ T 0 = ∅]YT,T 0∈TΨ(T ) = Ψen(xo1 )Ψex(xol )l−1
YQuantitative Results on the KITTI-Car Dataset. Comparison of our proposed methods to four state of the art methods and a HM baseline implementation.
Detections: DPM [2] reference detections and Regionlets [6] (marked with a star).

• Dynamic algorithm. Performs computations only when necessary.
• Nodes are held in a priority queue.
• The most promising node is relaxed in each iteration.
• The queue is dynamically updated depending on previous updates.

103

Ψli(xoi , xoi+1 )i=1• Optimal data association for an online setting.

Input Detections xi in Time Domain

Final World Association

100

online solver

Online Memory-bounded SSP

Online SSP

106
105

10−2

104

10−3101

103
100

102

103

104

105

106

• Only trajectories that were optimal are retained.

Possible Trajectories as Graph Representation

Optimal Association as Shortest Paths

Association Features

101102103

104106τ
5
10 15 20 50 100
MOTA 0.50 0.52 0.48 0.49 0.51 0.52
MOTP 0.78 0.78 0.78 0.78 0.78 0.78
F1 0.69 0.70 0.68 0.69 0.70 0.71
FAR 0.15 0.14 0.14 0.14 0.14 0.14
MT 0.14 0.15 0.16 0.17 0.18 0.15
ML 0.30 0.30 0.34 0.33 0.30 0.26
IDS
200045Frag. 703 708 690 701 710 712

10−1

previous computations.
• In order to “remember” known paths, costs of clipped trajectories
are summed up and new entry edges added to the graph.

10−210−3

τ=5
τ = 10τ = 25
τ = 50τ = 100
τ = 150
τ = 250

10−40 100 200 300 400 500 600 700 800 900# frames

Online Approximation Performance. Impact of different values for the history
length τ .

Real-time SSP

References[1] Anton Andriyenko, Konrad Schindler, and Stefan Roth. Discrete-continuousoptimization for multi-target tracking. In CVPR, 2012.
Bounding Box Overlap

Positional and Size Similarity[2] P. Felzenszwalb, R. Girshick, D. McAllester, and D. Ramanan. Object
detection with discriminatively trained part based models. PAMI,
32:1627–1645, 2010.

Orientation Similarity

signal #1 signal #2[3] Andreas Geiger, Martin Lauer, Christian Wojek, Christoph Stiller, and Raquel
Urtasun. 3D traffic scene understanding from movable platforms. PAMI,
36(5):1012–1025, 2014.

Ground Truth: KITTI Tracking Dataset[4] A. Milan, S. Roth, and K. Schindler. Continuous energy minimization for
multitarget tracking. PAMI, 36(1):58–72, 2014.

• 3D Ground Truthx-corr

Results on KITTI Tracking Benchmark. State-of-the-art performance for significantly faster inference than standard solvers.

105# frames100• Simply deleting edges from the graph is suboptimal and discards

optimalsolution

107

Run Time and Memory Comparison. Computational performance of allsolvers using one long sequence. From left to right: Mean runtime and idealized
memory consumption for every solver.

• Most of the past can be neglected for a tight approximation.

Standard SSP

Greedy SSP

101

odSSP/dSSP/SSP/DP
mbodSSP108# frames

runtime [s]with bounded memory and computation.
• Capable of handling videos of arbitrary in real time.
• State-of-the-art results on KITTI and PETS2009 benchmarks.

approximativesolution

102

109

10−1

• Approximate online solution

Dynamic SSP

DPSSPdSSP
mbodSSP

104• Faster inference than standard solvers.

batch solver

1010

105

runtime [s]One of the most popular approaches to multi-target tracking istracking-by-detection. Current min-cost flow algorithms which solve
the data association problem optimally have three main drawbacks:
they are computationally expensive, they assume that the whole video
is given as a batch, and they scale badly in memory and computation
with the length of the video sequence. In this paper, we address eachof these issues, resulting in a computationally and memory-boundedsolution.

Project Page with Codememory [byte]

122

Flow Overlap

Color Histogram Similarity

Template MatchingTracklets• 1249 Car Tracklets• 459 Pedestrian
Tracklets[5] Hamed Pirsiavash, Deva Ramanan, and Charless C. Fowlkes. Globally-optimal
greedy algorithms for tracking a variable number of objects. In CVPR, 2011.
[6] Xiaoyu Wang, Ming Yang, Shenghuo Zhu, and Yuanqing Lin. Regionlets forgeneric object detection. In ICCV, 2013.

KITTI-Tracking Benchmark. Stable and consistent results for long-term andcomplex scenes including challenging illumination or partial occlusions.

[7] L. Zhang, Y. Li, and R. Nevatia. Global data association for multi-object
tracking using network flows. In CVPR, 2008.