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

With the success of object detection came also the success of tracking-by-detection approaches [2, 10, 11, 32, 35,
43, 46] which track an unknown number of objects overtime. The idea is to first detect objects independently ineach frame, followed by an association step linking individual detections to form trajectories. The association problem is difficult due to the presence of occlusions, noisy
detections as well as false negatives. The simplest approach is to independently establish associations between
all pairs of consecutive frames, a problem which can besolved optimally in polynomial time using the Hungarian
method. However, in challenging situations ambiguities are
hard to resolve using local information alone and early errors cannot be corrected at later frames leading to globallyinconsistent tracks. More recently, sophisticated discretecontinuous optimization schemes have been proposed [2],which alternate between optimizing trajectories and performing data association over the whole sequence by assigning detections to the set of trajectory hypotheses. Unfortunately, the resulting problems are highly non-convex,
hard to optimize and provide no guarantees of optimality.
In their seminal work, Zhang et al. [46] showed how
multi-frame data association can be cast as a network flow
problem. The optimal solution can be found by a min-cost
flow algorithm, solving simultaneously for the number ofobjects and their trajectories according to a cost-function
which incorporates the likelihood of a detection as well as
pairwise relationships between detections for all consecutive frames. Recent extensions [3, 6, 11, 35] demonstrate
speedups by using more elaborate graph solvers, and showhow higher-order motion models can be incorporated into
the formulation at the cost of giving up global optimality.
In this paper we are interested in making min-cost flow
solutions applicable to real-world scenarios such as autonomous driving. Towards this goal two main problems
need to be addressed: (i) current approaches assume a batch
setting, where all detections must be available a priori, and(ii) their memory and computation requirements grow unbounded with the size of the input video. As a consequence existing min-cost flow techniques cannot be em-

One of the most popular approaches to multi-target
tracking is tracking-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 each of these issues, resulting in a computationally and memory-bounded solution. First, we introduce a
dynamic version of the successive shortest-path algorithm
which solves the data association problem optimally whilereusing computation, resulting in faster inference than standard solvers. Second, we address the optimal solution to thedata association problem when dealing with an incoming
stream of data (i.e., online setting). Finally, we present our
main contribution which is an approximate online solution
with bounded memory and computation which is capable ofhandling videos of arbitrary length while performing tracking in real time. We demonstrate the effectiveness of ouralgorithms on the KITTI and PETS2009 benchmarks andshow state-of-the-art performance, while being significantly
faster than existing solvers.

1. Introduction
In recent years the performance of object detectors has
improved substantially, reaching levels which nowadays
make them applicable to real-world problems. A notable
example is face recognition where algorithms that employ
deep learning features have attained human performance[39]. Many aspects have been key for the success of object recognition. The creation of benchmarks such as PASCAL [18] and ImageNet [36] made experimentation more
rigorous and stimulated the development of key algorithms
such as the deformable part-based model (DPM) [19] andmore recently deep learning approaches based on convolutional nets such as [26] and R-CNN [23].
1ployed in robotics applications where tracking algorithms
are required to run non-stop in an online setting while competing with other processes for a limited computation andmemory budget. In this paper we develop practical tracking
by detection solutions that• perform computations only when necessary,• handle an online stream of data, and• are bounded in memory and computation.
In particular, we show that the first two properties can beachieved while maintaining optimality, and an approximate
solution is possible for the latter which still performs very
well in practice. We demonstrate the effectiveness of the
proposed solvers on the KITTI [22] and PETS 2009 [20]tracking benchmarks. As evidenced by our experiments,
our approach is significantly more efficient than existing
min-cost flow algorithms. Furthermore, a near-optimal solution is retrieved when bounding the memory and computation to as little as 20kB and 10ms. We make our code,
dataset and supplementary material available on our project
website1 .

2. Related WorkMulti-target tracking approaches can be divided into
two main categories: filtering-based approaches and batch
methods. Filtering-based methods [10, 17, 33, 34] are basedon the Markov assumption, i.e., the current state depends
only on the previous states. While they are fast and applicable in real-time applications, they typically suffer from theirinability to recover from early errors.
Recent efforts focus primarily on batch methods, where
object hypothesis are typically obtained using an object detector (tracking-by-detection) and tracking is formulated as
an optimization problem over the whole sequence. This
mitigates the aforementioned problems and allows for the
integration of higher-level cues such as social group behavior in the case of pedestrian tracking [25, 27, 37]. Discretecontinuous optimization techniques have been proposed[2, 32], where discrete (data association) and continuous(trajectory fitting) optimization problems are solved in analternating way until converging to a hopefully better local minimum. In [9, 13, 14, 44], approximate Markov chain
Monte Carlo techniques are employed for solving the dataassociation problem. In order to increase the discriminative
power of appearance and dynamical models, online learning
approaches have been suggested [28, 29, 43, 45]. In [5, 6],
the problem is cast as optimization on a grid using a linear
program while assuming that the observing camera is static.
The problem of tracking through occlusions has been tackled in [4,12,16,30] by using context from outside the object
region or by building strong statistical motion models.
1 http://www.cs.toronto.edu/∼boundTracking

While most of the aforementioned formulations resort
to approximate optimization without optimality guarantees,
Zhang et al. [46] showed how data association with pairwise energies can be formulated as a network flow problem
such that standard graph 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. To reducethe computational complexity of min-cost flow algorithms,[6, 35] proposed to use the successive shortest-path (SSP)
algorithm as solver. Further speed-ups have been achievedin [35] using a greedy dynamic programming (DP) approximation. The min-cost flow idea has been extended in [3,11]
to include higher-order terms at the price of loosing optimality. More recently, Wang et al. [41] proposed to jointly
model the appearance of interacting objects by integrating
linear flow constraints into the framework.
While all of the existing min-cost flow formulations assume a batch setting, in this paper we propose a computationally and memory-bounded version of this algorithm,
which is able to process video sequences frame-by-frame
while reusing computation via efficient caching strategies.
Furthermore, our scheduling strategy performs computations only when neccessary which also speeds up traditional
batch solvers.

3. Review on Optimal Tracking-by-Detection
One of the most popular approaches to multi-target
tracking is tracking-by-detection, where a set of detections
are computed for each frame and trajectories are formedby linking these detections. In this section, we briefly review the necessary preliminaries to our contributions in
Section 4. In particular, we review how to formulate multitarget tracking as a min-cost flow problem and how to solve
it using the successive shortest path algorithm.

3.1. Tracking as Min-Cost Flow
Following the tracking-by-detection paradigm, we assume that a set of detections X = {xi } is available as input. Let xi = (xi , ti , si , ai , di ) denote a detection, with xi
the position of the bounding box, ti the time step (frame
index), si the size of the bounding box, ai the appearance, and di the detector score. We define a trajectory
as a sequence of observations Tk = (o1 , o2 , . . . , olk ) witho ∈ {1, . . . , |X |} the detection index of temporally adjacentdetections toi+1 = toi + 1.
The full association hypothesis is then given by a set of
trajectories T = {Tk }, and the data association problem
can be formulated as a Markov random field (MRF). Morespecifically, we aim at maximizing the posterior probability

of trajectories:p(T |X ) = p(T )Y

p(xi |T )(1)i

The observation model is given byPi
if ∃ Tk ∈ T ∧ i ∈ Tk
p(xi |T ) =1 − Pi otherwise(2)

where Pi denotes the probability of xi being a true detection. The prior over trajectories decomposes into a productof unary and pairwise factors
YYp(T ) ∝
Ψ(T )[T ∩ T 0 = ∅]
(3)
T ∈T

T,T 0 ∈T

where the pairwise term ensures that trajectories are disjoint. The unary factors are given byΨ(T ) = Ψen (xo1 )Ψex (xol )l−1YΨli (xoi , xoi+1 )

(4)

i=1

where Ψen (xo1 ), Ψex (xol ) and Ψli (xoi , xoi+1 ) model thelikelihood of entering a trajectory, exiting a trajectory andlinking temporally adjacent detections within a trajectory.
Taking the negative logarithm of (Eq. 1), the maximization can be transformed into an equivalent minimization
problem over flow variables [46] as follows
X
X
Cien fien +Ciex fiexf ∗ = argmin
f

i

+

X

s.t. fien +

X

i,j

j

i
li li
Ci,j
fi,j +

X

Cidet fidet

i
li
fj,i
= fidet = fiex +

X

li
fi,j

Figure 1: The original problem (top) is mapped into a mincost flow network (bottom). Ground truth trajectories areshown in black. Colored nodes encode detections and correspond to two nodes in the min-cost flow network G. For
clarity of illustration, edges from the source and to the sink
have been ommitted.

∀i (5)jwhere Cien = − log Ψen (xi ) is the cost of creating a new
trajectory at xi and Ciex = − log Ψex (xi ) is the cost of exiting a trajectory at xi . The cost of linking two consecutivelidetections xi and xj is denoted Ci,j= − log Ψli (xi , xj )det
and Ci encodes the cost of xi being a true detection ora false positive (data term). Furthermore, the binary flow
variables fien or fiex take value 1 if the solution contains a
trajectory such that xi is the first frame or last frame, respectively. fidet = 1 encodes the fact that xi is part of ali
trajectory and fi,j
= 1 if a tracklet exists which contains
both detections xi and xj in two consecutive frames.
In their seminal work, Zhang and Nevatia [46] showed
how to map the problem in Eq. 5 into a min-cost flow network problem. Fig. 1 illustrates one such network graph,
where for each observation two nodes ui and vi are created(summarized as one node for clarity of illustration) with anedge between them with cost c(ui , vi ) = Cidet and flowf (ui , vi ) = fidet . For entering, edges are introduced between the source s and the first node of each detection withcost c(s, ui ) = Cien and flow fien . For exiting, edges are
introduced between the last node of each detection and thesink with cost c(vi , t) = Ciex and flow fiex . Finally, edges
between consecutive detections (vi , uj ) encode pairwise aslilisociation scores with cost c(vi , uj ) = Ci,jand flow fi,j.
While we assume that only detections in consecutive frames
can be linked, this can be easily generalized by allowing
transitions between detections in non-consecutive frames
resulting in additional edges.
To find the optimal solution, Zhang et al. [46] start withflow zero, and augment the flow one unit at a time, applying
the push relabeling algorithm [24] to retrieve the shortest
path at each iteration. The algorithm terminates if the costof the currently retrieved shortest path is greater or equal tozero. For efficiency, the bisection method can be applied on
the number of flow units, reducing time complexity fromlinear to logarithmic with respect to the number of trajectories. The total complexity is then O((mn2 log2 (n))), withn the number of nodes and m the number of edges.

3.2. Successive Shortest-Path (SSP)
Recently, [6, 35] proposed to replace the costly push relabeling algorithm by the successive shortest-path (SSP) algorithm [1, p. 104]. This reduces the computational complexity to O(K(n log(n) + m)) where n is the number ofnodes, m is the number of edges and K denotes the number of trajectories which is upper bounded by the number ofnodes n. This section gives a brief introduction to the SSP
algorithm as it forms the foundation for our contributions.
We refer the reader to the supplementary material for technical details in greater depth and an illustrative example.

The SSP algorithm works as follows: it first computes
the shortest path between source and target (i.e., path withthe lowest negative cost). It then iterates between reversing the edges of the previously found shortest path to form
the residual graph Gr , and computing the shortest path in
this new residual graph. This process is iterated until no
trajectory with negative cost can be found. Finally, trajectories are extracted by backtracking connected, inverted edges
starting at the target node.
In the first iteration the shortest path from the source
to the target is efficiently retrieved using dynamic programming [15, p. 655] as the input graph is directed andacyclic. In the following iterations, Dijkstra’s algorithm canbe leveraged after converting the graph such that all costs
are positive. This conversion is achieved by simply replacing the current cost Cu,v between nodes (u, v) linked by0
a directed edge, with Cu,v= Cu,v + d(u) − d(v), whered(u) and d(v) are the distance on the shortest path from thesource to nodes u and v (c.f . supplementary material). Im0=0
portantly, for u and v on the shortest path we have Cu,vafter conversion. Note that for graphs with positive costs
and unit flow capacity, the SSP algorithm is similar to the
k-shortest paths (“KSP”) algorithm [38].Furthermore, one
could use other algorithms such as Bellman-Ford to replace
Dijkstra and handle negative costs directly. However, thiswould result in worst complexity, i.e., O(K(n2 )) .

4. Dynamic Online and Bounded Tracking
In this section we present new algorithms that have thenecessary properties for tracking-by-detection to be applicable to real-world scenarios: dynamic computation, handling online data, and bounded memory and computation.
We start by proposing a distributed optimal SSP algorithm
which leverages a dynamic priority cue, saving computation when compared to the original SSP algorithm. We thenextend this algorithm to handle an online data stream. Finally, we proposed our main contribution, a memory andcomputation bounded online SSP algorithm.

4.1. Optimal Dynamic Min-Cost Flow (dSSP)
In this section we propose a novel dynamic algorithm
which performs computations only when necessary. Dijkstra’s algorithm is based on the principle of relaxation,in which an upper bound of the correct distance is gradually replaced by tighter bounds (by computing the predecessor and its distance) until the optimal solution is reached.
Nodes are held in a priority queue, guaranteeing that themost promising node is relaxed in each iteration 2 . This priority queue is initialized to hold only the source node, andupon convergence all nodes have been visited.
The key intuition behind our dynamic computation is
2 This is guaranteed as all costs are positive.

that calling Dijkstra at each iteration of the SSP algorithm issuboptimal in terms of runtime as from one iteration to thenext only a small part of the graph has changed (i.e., only
the reversed edges are different). Inspired by the distributed
Bellman-Ford algorithm [8, 40], we propose to reuse computation and only update the predecessors when needed.
This can be easily implemented within Dijkstra by using
a dynamic priority queue, which contains only nodes thathave changed. Initially, this queue comprises the changes
introduced by reducing edges after finding the previous
shortest path in order to handle positive costs as in KSP.
The queue is then dynamically updated depending on which
successors require changes. We refer the reader to Algo. 1
for a summary of our dynamic algorithm.
We illustrate our dynamic algorithm within the computation of a single iteration of SSP in Fig. 2 for an example
containing four frames with three detections each. Given
the shortest path found in the previous iteration, we revert
its edges to form the residual graph in Fig. 2(a). Note thatthe corresponding predecessor maps have to be updated as
the direction of these edges has changed. We start by updating all predecessors for nodes belonging to the most recent trajectory (blue path in Fig. 2(a)) in a forward sweep(relaxed edges are marked in red). Next, all nodes with a
new predecessor propagate their cost along their respective
shortest path to their successors when taken from the priority queue. All successors which receive an update, i.e., forwhich the predecessor has changed, are themselves added tothe priority queue (indicated by the red edges in Fig. 2(b)).
Note that those nodes are not necessarily part of the previous shortest path but can be retrieved efficiently as the successors of the nodes in the current queue. This way, our algorithm recursively updates all required nodes and ensures
global optimality. The algorithm (one iteration of SSP)
terminates when the queue is empty as all shortest paths
have been updated. Note that this dynamic computation
is employed at each iteration of SSP, and SSP terminates
when no new shortest path with negative cost can be found(Fig. 2(c)). The final trajectories are extracted by collecting all backward pointing edges of Gr , starting at the target
node (Fig. 2(d)). In contrast to Dijkstra’s original algorithm,
our dynamic broadcasting scheme relaxes only parts of thegraph for typical tracking networks as illustrated in Fig. 2(e)and demonstrated later in our experimental evaluation.

4.2. Optimal Online Solution (odSSP)
Next, we extend the dynamic min-cost flow formulation
introduced in the previous section to the online setting. Our
intuition is that every time a new observation arrives (i.e.,
set of detections at time t), we would like to reuse computation from the shortest paths and trajectories computedin the previous time step which involve all detections up to
time t − 1. This is possible as in the online setting, the new

(a) Update Nodes(b) Priority Queue(c) Shortest Path(d) Final Trajectories(e) Dijkstra (SSP)

Figure 2: Dynamic Message Broadcasting (dSSP): For a given residual graph (shortest path in blue), (a) nodes with invalid
predecessors which require an update (red) are detected and queued. (b) The queue is processed by successively taking
nodes from the queue and relaxing their outgoing edges. Successors with updated predecessors (red) are added to the queue.
Exploiting Dijkstra’s algorithm, the priority queue is processed until no nodes are left. The algorithm terminates with thesolution for the current residual graph (c)+(d). Trajectories are encoded by backward pointing edges (green and blue). While
our dynamic broadcasting scheme exploits the intrinsic properties of the tracking problem and updates only deprecatedpredecessor maps (indicated by the red nodes in (a) and (b)), Dijkstra’s original algorithm requires the full predecessor map
and broadcasts messages to all nodes (indicated by the red nodes in (e)).
network contains the previous network and some additionaledges/nodes. It is important to note that a naı̈ve extensionof trajectories would violate optimality if the new evidence(i.e., detections at time t) changes the optimal trajectories
for detections in previous time steps (1, · · · , t − 1).
We illustrate our dynamic online algorithm with an example in Fig. 3. Consider the network specified in Fig. 3(a)where the most recent time step is t = 3 and the optimal setof trajectories and predecessor maps have been computed.
Fig. 3(b) illustrates the shortest paths as well as the two optimal trajectories (in blue and green respectively) computed
at time t = 3. As a new frame arrives, new nodes (depicted in cyan in Fig. 3(c) are added, extending the graph tothe next time step. The first trajectory can be computed byapplying dynamic programing only to the edges involving
the new nodes, as in a DAG the predecessors do not change
from previous time steps. For successive trajectories (nextiterations of the SSP algorithm), the predecessor maps fromthe previous time steps can be reused only if the trajectories under consideration are currently in the same order as
when applying SSP to the previous time frame t − 1 (i.e.,
before we received the new observation). This will not be
the case when we have competing trajectories with similar
costs, as given the new evidence (new frame) the orderingof these trajectories is likely to change. To handle this case,
we utilize a caching strategy which keeps all predecessor
maps for a cache of |C| frames in memory. Similar to theoffline strategy, the online version implements a dynamic
priority queue. Initially, this queue comprises the changes
introduced by the added nodes and edges for the most recent
time step. The queue is then dynamically updated depending on which successors require changes.
Coming back to our example, the optimal solution for
the first iteration of SSP is found in Fig. 3(d). The predecessor maps for the new nodes (orange nodes in Fig. 3(e))

have to be re-estimated only if they were part of the shortest
path. Towards this goal, we employ our dynamic broadcasting strategy where only the node in cyan in Fig. 3(f) is
put into the initial priority queue. As in this example theoptimal trajectories are consistent with the ones from theprevious time instant (see Fig. 3(b) and Fig. 3(g)), the optimal trajectories can be computed very efficiently, resulting
in massive computational gains.

4.3. Memory-Bounded Solution (mbodSSP)
While the odSSP algorithm handles the online setting,it does not scale to very large problems since messages
might broadcast back to very early frames in order to guarantee optimality. Furthermore, memory requirements stillgrow unbounded with the length of the sequence. Thus,
these algorithms are not applicable to autonomous driving
or surveillance scenarios.
In this section we propose a memory and computationally bounded approximation which we call “mbodSSP”.
The key intuition is that given some computation and memory budget, we can safely neglect most of the past, and only
retain the interesting information, i.e., the trajectories thatwere optimal. We refer the reader to Algo. 2 for a depiction of the algorithm, and focus on explaining it throughan example. Consider the case where we assume a budgetof τ = 4 frames, and the solution from the previous time
step is given in Fig. 3(g). Before adding new nodes to thegraph for the next time step t+1, we remove the oldest time
step t − τ from the graph as illustrated in Fig. 3(h) to maintain the memory/computation constraints. Simply deletingedges from the graph is suboptimal as it completely discards
computations from previous time steps (before the new observation arrives). In order to “remember” known paths, foreach trajectory we sum the cost of the predecessor node attime t − τ to the corresponding successor at time t − τ + 1.

(a) Original Network, t = 3(b) Solution, t = 3(c) Nodes added for t = 4(d) Solution in DAG(e) Merge Solution+Cache(f) Broadcast Changes(g) Decoded Trajectories(h) Clip Graph (mbodSSP)

Figure 3: Online (a)-(g) and Memory Bounded (h) Algorithm: Assume that for the original network at t = 3 (a), thesolution (b) is already known (shortest paths in blue and green). A new set of detections (cyan nodes) for t = 4 arrives and isconnected to the graph (c) resulting in a DAG for which the shortest path can be found by applying one step of the DAG-SP
algorithm (d). The predecessor maps from the previous (magenta nodes) and current time step (orange nodes) are merged(e). The queue initially contains nodes with outdated predecessors from the last shortest path (cyan). The priority queue isprocessed until convergence (Fig. 2) and the predecessors are updated (f). In this example, the algorithm terminates after
one iteration and the optimal solution is found (g). For the mbodSSP algorithm, paths which pass through nodes outside thehistory window are merged with the entry costs of the next time step (h).
This strategy allows us to use the cache and remember previously found paths. In the rare event that a trajectory which
is not represented in the current cache is found, we resort to
odSSP on window [t − τ + 1, t + 1], guaranteeing a valid
cache for the current SSP iteration. The cached predecessor
maps are clipped using the same strategy. While optimality is violated as no changes can be applied to paths beyond t − τ + 1, our experiments demonstrate that for manycases of practical interest small windows are sufficient toobtain near-optimal solutions. In particular, our memory
bounded approximation is able to maintain track ids overperiods much longer than the window itself. In contrast,
when splitting the sequence into batches and applying themin-cost flow network algorithm separately to each batch,ad-hoc heuristics are required to resolve this problem.

5. Experimental Evaluation
We evaluate our algorithms on the challenging KITTI[22] and PETS 2009 [20] tracking benchmarks. For PETS
we use the object detections provided by Andriyenko etal. [2]. For KITTI we compare the DPM reference detections [19] provided on the KITTI website3 with the recently
proposed Regionlet detections [42] provided to us by theauthors.
3 http://www.cvlibs.net/datasets/kitti/eval tracking.php

We convert the detection score of each bounding box
di into a unary cost value Ci using logistic regression
Ci = 1/(1 + eβdi ) on the training set. To encode association costs, we use six different pairwise similarity features s = {sl }: bounding box overlap, orientation similarity, color histogram similarity, cross-correlation, location
similarity, and optical flow overlap. Similar to the detection
scores we pass the association features through a logistic
function using logistic regression yielding s ∈ [0, 1]6 . The
detection/association cost for each edge (u, v) is then defined as Cu,v = ((1 − s) + o)> w, where o denotes anoffset and w the scale. Note that the offset is required toallow for negative as well as positive costs. All parameters(o, w) have been obtained using block coordinate descenton the respective training sets and kept fix during all our
experiments. We refer the reader to the supplementary material for further details on the parameter setting, additional
results, and videos.
Comparison to State-of-the-art on KITTI: We firstcompare the proposed dSSP and mbodSSP algorithms
against four state-of-the-art baselines [2, 21, 31, 35] as wellas the pairwise optimal Hungarian method (“HM”) on thechallenging KITTI dataset using the DPM reference detections [19]. The metrics we use are described in [7, 29]. As
shown in Table 1 (left part), the optimal algorithm (“SSP”)
outperforms all other methods. Note that all discussed opti-

Algorithm 1: dSSP

Algorithm 2: mbodSSP

Input: Set of Detections X = {xi }Output: Set of trajectory hypotheses T = {Tk }1 G(V, E, C, f ) ← ConstructGraph(X , s, t)
2 f (G) ← 0// initialize flow to 0
3 γ0 , π0 ← DAG-SP(G(f ))// shortest path in DAG(0)(1)
4 Gr (f ) ← ConvertEdgeCosts(G(f ), γ0 , π0 ) Gr (f ) ←(0)
ComputeResidualGraph(Gr (f ), π (0) )5 q ← ∅// q is maintained for every iteration k
6 while 1 do// find shortest paths for k ≥ 1
7
k ←k+18
π (k) ← π (k−1)
9q ← γ (k−1)// process queue in time direction
10
foreach node u ∈ q do// check predecessor from past11
π (k) ← Update(π (k) , u)12
if updated then(k)
13
q ← AddSuccessors(q, u, Gr (f ))// process queue
14
while ¬ empty(q) do
15u ← NodeWithMinDistance(q)// pop node16
q ←q\u(k)17
foreach node v ∈ Successors(Gr (f ),u) do// Check predecessor of v
18
π (k) (v) ← Relax(u,v,c)19
if d(v) > d(u) + c(u, v) then20d(v) ← d(u) + c(u, v)
21q ← AddNode(q, v)
(k)
(k)
22
Gr (f ) ← ConvertEdgeCost(Gr (f ), π (k) )
(k+1)
(k)
23
Gr
(f ) ← ResidualGraph(Gr (f ), γ (k) )// evaluate converted costs
P
24
if ki=1 cost(γ (i) ) > | cost(γ (0) )| then25
break
26 return T

Input: Current Detections X t = {xt },Graph G(V, E, C, f, s, t), Cache C
Output: Set of trajectory hypotheses T = {Tk }1 if memorybounded then2
foreach node u ∈ [t − τ ] domal batch solvers obtain identical tracking results, but withdifferent run time thus we only state results for SSP. In our
experiments, we made use of a relatively low threshold di =−0.3 for the object detector to avoid early pruning and evaluate each method with respect to outlier rejection performance. Note that our method attains the best performancewith respect to mostly tracked trajectories (“MT”) while
only exhibiting a slightly higher false alarm rate (“FAR”)
than the other methods. The method of [2] struggled withthe presence of outliers and di = 0.0 was used to obtainmeaningful results. Also note the little loss in performance
when running mbodSSP for a window length of τ = 10 asa good trade-off between runtime and performance (Fig. 3).
Compared to the non-optimal DP solution [35], mbodSSP
achieves higher performance, especially in terms of identity
switches and fragmentations. We provide additional quali-//remember predecessor by updating cen,iG(f ) ← UpdateEntryEdge(G(f ), u)
4
G(f ) ← RemoveObservation(G(f ), u)
5 G(f ) ← AddObservations(G(f ), X t )(0) ← C (0) (t − 1)
6 π
3//still a DAG// run DAG-SP for edges (u, v) ∈ [t − 1, t]
7

γ (0) , π (0) ← DAG-SP(Gr (f ), t − 1)

8

Gr (f ) ← ConvertEdgeCosts(G(f ), γ (0) , π (0) , t − 1)

(0)

(1)
(0)
(0) )
9 Gr (f ) ←ComputeResidualGraph(Gr (f ), πq ← ∅, k ← 0
while 1 do
12k ←k+1

10
11

(k−1)

(k−1)

// γt−δi = γt

, δi ∈ {0, . . . , |C|}14

δi ← MostRecentCache(C, γ (l) ∀ l = 0, . . . , k − 1)
π (k) ← C(δi , k)// update predecessor map πk15q ← {γt13(k−1), (u, v) ∈ [t − δi , t]}// Algo. 1, line 10
(k+1)

Gr
17 return T
16(k)(f ), γ (k) ← ProcessQueue(q, π (k) , Gr (f ))HM [2] [31] [35] [21] mbodSSP SSP mbodSSP* SSP*
MOTA 0.42 0.35 0.48 0.44 0.52
0.52
0.54
0.67
0.67
0.78
0.78
0.79
0.79
MOTP 0.78 0.75 0.77 0.78 0.78
F1
0.60 0.61 0.67 0.62 0.69
0.70
0.71
0.83
0.83
FAR
0.048 0.46 0.18 0.053 0.083
0.14
0.11
0.34
0.40
MT
0.077 0.11 0.14 0.11 0.14
0.15
0.21
0.34
0.41
ML
0.42 0.34 0.34 0.39 0.35
0.30
0.27
0.10
0.090
IDS
12 223 125 2738 33
0
7
117
194
Frag.
578 624 401 3241 540
708
717
894
977

Table 1: Comparison of our proposed methods to four stateof the art methods and a HM baseline implementation on
KITTI-Car using the DPM reference detections and Regionlet detections (marked with a star).
MOTA
MOTP
MT
ML
ID-switches
Fragmentations

[2]
0.96
0.79
0.96
0.0
10
8

EKF [31]
0.68
0.77
0.39
0.04
25
30

[31]
0.91
0.80
0.91
0.04
11
6

mbodSSP
0.89
0.87
0.89
0.0
7
100

SSP
0.91
0.87
0.89
0.0
23
100

Table 2: Comparison of our proposed method to three baselines on PETS 2009 sequence “S2.L1”.
tative results in the supplementary material.We also experiment with the detector of [42], which yields better results
particularly for occluded objects. The increasing tracking
performance indicates that with a good enough detector ourapproach could be used in practical applications.
Comparison to State-of-the-art on PETS2009: We additionally evaluate our methods on the commonly used

1010

105

102
101
100
10−1

101

10−1

108
107
106
105

10−2

10−3

104

10−2
10−3

100

odSSP/dSSP/SSP/DP
mbodSSP

109

runtime [s]runtime [s]

103

DP
SSP
dSSP
mbodSSP

memory [byte]

104

102

103

104

105

106

103
100

101

102

103

104

105

106

# frames# frames(a) Run Time(b) Memory Consumption

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

10−40 100 200 300 400 500 600 700 800 900# frames(c) Impact of History Length τ

Figure 4: Run Time and Memory Comparison. We compare computational performance of all solvers using one longsequence without ground truth annotations. This figure shows the mean runtime (a) and idealized memory consumption (b)for every solver. Additionally, we show the impact of different values for the history length τ (c).
τ
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 3: Variation of the approximation parameter τ .
PETS2009 dataset for sequence “S2.L1”. We used the detections and ground truth provided by the authors of [2, 31].
Both, the optimal algorithms and the memory-bounded approximation perform on par with current state-of-the-art. In
particular performance for precision-based measures is notably good. Note that we used the same parameters as forthe results presented on KITTI.
Comparing Min Cost Flow Solutions: We compare our
globally optimal methods (dSSP, odSSP) as well as our approximate mbodSSP algorithm for window size τ = 10
against a regular SSP implementation using Dijkstra’s algorithm (as described in [15]) as well as the non-optimal DP
solution of [35] in terms of run time and memory consumption. For a fair comparison, we implement all our solvers in
Python using the same data structures. Fig. 4 (a)-(b) depict
execution time and memory consumption as a function of
the number of frames for a very long sequence on KITTI.
Note that our globally optimal dynamic solver (dSSP) outperforms the regular Dijkstra implementation (SSP) by afactor of 3 on average. To verify the correctness of our
implementation against the optimal solution, we have usedthousands of random graphs. Importantly, our experiments
validate that the time complexity of mbodSSP is independent of the sequence length. Thus, it outperforms DP [35]in memory, computation as well as accuracy (see Table 1).

A run time evaluation for KITTI including a comparison forthe different training scenarios is discussed in greater depth
in the supplementary material.
Sliding Window Size of mbodSSP: We evaluate thetracking performance of mbodSSP for different values of τ
on KITTI. As shown in Fig. 4(c), for a value of τ = 10, our
non-optimized Python implementation of mbodDijkstra requires less than 10ms which is sufficient for many real-time
online applications.

6. Conclusions
In this paper we have proposed solutions to make the useof min-cost flow tracking by detection possible in real world
scenarios. Towards this goal we have designed algorithms
that are dynamic, can handle an online data stream and arebounded in memory and computation. We have demonstrated the performance of our algorithms in challenging
autonomous driving and surveillance scenarios. In future
work we plan to extend our approach to handle long-term
occlusions and to incorporate additional features, e.g., map
information.

References[1] R. K. Ahuja, T. L. Magnanti, and J. B. Orlin. Network Flows.
Prentice Hall, 1993. 3[2] A. Andriyenko, K. Schindler, and S. Roth. Discretecontinuous optimization for multi-target tracking. In CVPR,
2012. 1, 2, 6, 7, 8
[3] C. Arora and A. Globerson. Higher order matching for consistent multiple target tracking. In ICCV, 2013. 1, 2
[4] S.-H. Bae and K.-J. Yoon. Robust online multi-object tracking based on tracklet confidence and online discriminative
appearance learning. In CVPR, 2014. 2[5] H. Ben Shitrit, J. Berclaz, F. Fleuret, and P. Fua. MultiCommodity Network Flow for Tracking Multiple People.
PAMI, 36(8):1614–1627, 2013. 2

[6] J. Berclaz, F. Fleuret, E. Turetken, and P. Fua. Multiple
object tracking using k-shortest paths optimization. PAMI,
33(9):1806–1819, 2011. 1, 2, 3
[7] K. Bernardin and R. Stiefelhagen. Evaluating multiple object
tracking performance: The clear mot metrics. JIVP, 1:1–10,
2008. 6
[8] D. Bertsekas and R. Gallager. Data networks. Prentice-Hall,
Inc., 1992. 4[9] E. Brau, J. Guan, K. Simek, L. D. Pero, C. R. Dawson, and
K. Barnard. Bayesian 3d tracking from monocular video. In
ICCV, 2013. 2[10] M. D. Breitenstein, F. Reichlin, B. Leibe, E. Koller-Meier,and L. J. V. Gool. Online multiperson tracking-by-detection
from a single, uncalibrated camera. PAMI, 33(9):1820–1833,
2011. 1, 2
[11] A. Butt and R. Collins. Multi-target tracking by lagrangian
relaxation to min-cost network flow. In CVPR, 2013. 1, 2
[12] X. Chen, Z. Qin, L. An, and B. Bhanu. An online learned elementary grouping model for multi-target tracking. In CVPR,
2014. 2[13] W. Choi, C. Pantofaru, and S. Savarese. A general framework
for tracking multiple people from a moving camera. PAMI,
35(7):1577–1591, 2013. 2[14] R. T. Collins and P. Carr. Hybrid stochastic / deterministic
optimization for tracking sports players and pedestrians. In
ECCV, 2014. 2[15] T. H. Cormen, C. Stein, R. L. Rivest, and C. E. Leiserson.
Introduction to Algorithms. McGraw-Hill Higher Education,
2001. 4, 8
[16] C. Dicle, O. I. Camps, and M. Sznaier. The way they move:
Tracking multiple targets with similar appearance. In ICCV,
December 2013. 2[17] A. Ess, B. Leibe, K. Schindler, and L. V. Gool. Robust multiperson tracking from a mobile platform. PAMI, 31:1831–
1846, 2009. 2[18] M. Everingham, L. Van Gool, C. K. I. Williams, J. Winn,
and A. Zisserman. The pascal visual object classes (voc)challenge. IJCV, 88(2):303–338, 2010. 1[19] P. Felzenszwalb, R. Girshick, D. McAllester, and D. Ramanan. Object detection with discriminatively trained partbased models. PAMI, 32:1627–1645, 2010. 1, 6
[20] J. Ferryman and A. Shahrokni. Pets2009: Dataset and challenge. In PETS, pages 1–6, 2009. 2, 6
[21] A. Geiger, M. Lauer, C. Wojek, C. Stiller, and R. Urtasun. 3D
traffic scene understanding from movable platforms. PAMI,
36(5):1012–1025, 2014. 6, 7
[22] A. Geiger, P. Lenz, and R. Urtasun. Are we ready for autonomous driving? The KITTI vision benchmark suite. In
CVPR, 2012. 2, 6
[23] R. Girshick, J. Donahue, T. Darrell, and J. Malik. Rich feature hierarchies for accurate object detection and semantic
segmentation. In CVPR, 2014. 1[24] A. V. Goldberg. An efficient implementation of a scaling
minimum-cost flow algorithm. JA, 22(1):1–29, 1997. 3[25] J. F. P. Kooij, G. Englebienne, and D. M. Gavrila. A nonparametric hierarchical model to discover behavior dynamics
from tracks. In ECCV, 2012. 2[26] A. Krizhevsky, I. Sutskever, and G. E. Hinton. Imagenet
classification with deep convolutional neural networks. In
NIPS, 2012. 1[27] L. Leal-Taixe, M. Fenzi, A. Kuznetsova, B. Rosenhahn, and
S. Savarese. Learning an image-based motion context for
multiple people tracking. In CVPR, 2014. 2[28] L. Leal-Taixe, G. Pons-Moll, and B. Rosenhahn. Branchand-price global optimization for multi-view multi-target
tracking. In CVPR, 2012. 2[29] Y. Li, C. Huang, and R. Nevatia. Learning to associate:
HybridBoosted multi-target tracker for crowded scene. In
CVPR, 2009. 2, 6[30] J. Liu, P. Carr, R. T. Collins, and Y. Liu. Tracking sports
players with context-conditioned motion models. In CVPR,
2013. 2[31] A. Milan, S. Roth, and K. Schindler. Continuous energy minimization for multitarget tracking. PAMI, 36(1):58–72, 2014.
6, 7, 8[32] A. Milan, K. Schindler, and S. Roth. Detection- andtrajectory-level exclusion in multiple object tracking. In
CVPR, 2013. 1, 2
[33] D. Mitzel and B. Leibe. Taking mobile multi-object tracking
to the next level: People, unknown objects, and carried items.
In ECCV, 2012. 2[34] H. Nam, S. Hong, and B. Han. Online graph-based tracking.
In ECCV, 2014. 2[35] H. Pirsiavash, D. Ramanan, and C. C. Fowlkes. Globallyoptimal greedy algorithms for tracking a variable number ofobjects. In CVPR, 2011. 1, 2, 3, 6, 7, 8[36] O. Russakovsky, J. Deng, H. Su, J. Krause, S. Satheesh,
S. Ma, Z. Huang, A. Karpathy, A. Khosla, M. Bernstein,
A. C. Berg, and L. Fei-Fei. Imagenet large scale visual recognition challenge. arXiv.org, 1409.0575, 2014. 1[37] X. Shi, H. Ling, W. Hu, C. Yuan, and J. Xing. Multi-target
tracking with motion context in tensor power iteration. In
CVPR, 2014. 2[38] J. W. Suurballe. Disjoint paths in a network. Networks,
4(2):125–145, 1974. 4[39] Y. Taigman, M. Yang, M. Ranzato, and L. Wolf. Deepface:
Closing the gap to human-level performance in face verification. In CVPR, 2014. 1[40] D. Walden. The bellman-ford algorithm and “distributed
bellman-ford”. Technical report, MIT, 2003. 4[41] X. Wang, E. Turetken, F. Fleuret, and P. Fua. Tracking interacting objects optimally using integer programming. In
ECCV, 2014. 2[42] X. Wang, M. Yang, S. Zhu, and Y. Lin. Regionlets for genericobject detection. In ICCV, 2013. 6, 7
[43] B. Yang and R. Nevatia. An online learned crf model for
multi-target tracking. In CVPR, 2012. 1, 2
[44] M. Yang, Y. Liu, L. Wen, Z. You, and S. Z. Li. A probabilistic
framework for multitarget tracking with mutual occlusions.
In CVPR, 2014. 2[45] S.-I. Yu, Y. Yang, and A. Hauptmann. Harry potter’s marauder’s map: Localizing and tracking multiple persons-ofinterest by nonnegative discretization. In CVPR, 2013. 2[46] L. Zhang, Y. Li, and R. Nevatia. Global data association for
multi-object tracking using network flows. In CVPR, 2008.
1, 2, 3