A Generalized Successive Shortest Paths Solver for Tracking Dividing Targets
Tracking-by-detection methods are prevailing in many tracking scenarios. One attractive property is that in the absence of additional constraints they can be solved optimally in polynomial time, e.g. by min-cost flow solvers. But when potentially dividing
- PDF / 1,048,914 Bytes
- 17 Pages / 439.37 x 666.142 pts Page_size
- 58 Downloads / 202 Views
bstract. Tracking-by-detection methods are prevailing in many tracking scenarios. One attractive property is that in the absence of additional constraints they can be solved optimally in polynomial time, e.g. by min-cost flow solvers. But when potentially dividing targets need to be tracked – as is the case for biological tasks like cell tracking – finding the solution to a global tracking-by-detection model is NP-hard. In this work, we present a flow-based approximate solution to a common cell tracking model that allows for objects to merge and split or divide. We build on the successive shortest path min-cost flow algorithm but alter the residual graph such that the flow through the graph obeys division constraints and always represents a feasible tracking solution. By conditioning the residual arc capacities on the flow along logically associated arcs we obtain a polynomial time heuristic that achieves close-to-optimal tracking results while exhibiting a good anytime performance. We also show that our method is a generalization of an approximate dynamic programming cell tracking solver by Magnusson et al. that stood out in the ISBI Cell Tracking Challenges.
1
Introduction
Tracking proliferating cells is a task that arises e.g. in developmental biology and high-throughput screening for drug development. Tracking-by-detection methods are often the tool of choice because they allow for fine tuned detection algorithms, give room for a lot of modeling decisions, and do not require that the number of targets is known beforehand. One common ingredient in all tracking models for divisible targets is the constraint that a division can only occur in the presence of a parent. These constraints require the formulation of the objective as an integer linear program (ILP) [1–3]. Such ILPs can be solved to optimality up to a certain size, in spite of their NP-hardness; but they do not scale to the huge coupled problems that arise from long video. Recently, min-cost flow solvers have become a popular choice to tracking multiple targets like pedestrians, cars, and other non-dividing objects [4–7]. These methods provide a polynomial runtime guarantee and are very efficient in practice, while solving the problem to global optimality. Unfortunately, min-cost flow solvers are not directly applicable to tracking problems with additional c Springer International Publishing AG 2016 B. Leibe et al. (Eds.): ECCV 2016, Part VII, LNCS 9911, pp. 566–582, 2016. DOI: 10.1007/978-3-319-46478-7 35
A Generalized Successive Shortest Paths Solver f(ai,ao)
0/0 2-f(bi,bo)
f(s,ao)
s ai
ao f(ai,ao) -f(s,ao)
a)
bo
bi
i o ,b )
2-f(a
2-f(ai,ao)
i o ,b )
f(a 2-f(a o ,c i) f(a o,c i )
ai
0/2
0/0
co
ci
b)
f(ci,co)
0/0
0/2
ai
bo
ao
ai
ao
1/1
0/1
c)
1/1
0/1
co
ci
0/0
0/0
1/2
0/0
co
ci
d)
0/0
bo
bi
0/2 1/1
1/2
0/0
0/2
0/0
s
0/0
0/0
0/1
1/1
1/0 1/2
0/0 1/1
ai
bo
bi
1/2
1/1
ao
ai
1/1
ao
1/1
0/0
e)
1/1
0/1
co
ci
0/1 0/1
1/1
0/1
co
ci
f)
0/1
bo
bi
1/1
0/0 0/0
0/1
1/1
0/1
s
0/1
0/0
Ca
Data Loading...
