2 Multi-Tracked Paths (MTP)
3 -------------------------
7 This is a very simple implementation of a variant of the k-shortest
8 paths algorithm (KSP) applied to multi-target tracking, as described
11 J. Berclaz, E. Turetken, F. Fleuret, and P. Fua. Multiple Object
12 Tracking using K-Shortest Paths Optimization. IEEE Transactions on
13 Pattern Analysis and Machine Intelligence (TPAMI), 33(9):1806-1819,
16 This implementation is not the reference implementation used for the
17 experiments presented in this article. It does not require any
18 library, and uses a Dijkstra with a Binary Heap for the min-queue,
19 instead of a Fibonacci heap.
21 This software package includes three commands:
23 - mtp is the generic command to use in practice. It takes tracking
24 parameters as input, and prints the tracked trajectories as
25 output. The format for these parameters is given at the bottom of
28 - mtp_example creates a tracking toy example, and runs the tracking
29 algorithm on it. It gives an example of how to use MTPTracker on a
30 configuration produced dynamically, and produces a test input file
31 for the mtp command. If you pass it the "stress" argument, it
32 generates a larger and noisier problem.
36 This software should compile with any C++ compiler. Under a unix-like
37 environment, just execute
42 It will create a synthetic dummy example, save its description in
43 tracker.dat, and print the optimal detected trajectories.
47 ./mtp --verbose --trajectory-file result.trj --graph-file graph.dot tracker.dat
49 It will load the file tracker.dat saved by the previous command, run
50 the detection, save the detected trajectories in result.trj, and the
51 underlying graph with occupied edges in graph.dot.
53 If you do have the graphviz set of tools installed, you can produce a
54 pdf from the latter with the dot command:
56 dot < graph.dot -T pdf -o graph.pdf
60 The two main classes are MTPGraph and MTPTracker.
62 The MTPGraph class contains a directed acyclic graph (DAG), with a
63 length for each edge -- which can be negative -- and has methods to
64 compute the family of paths in this graph that globally minimizes the
67 If there are no path of negative length, this optimal family will be
68 empty, since the minimum total length you can achieve is zero. Note
69 that the procedure is similar to that of KSP, in the sense that the
70 family it computes eventually is globally optimal, even if the
71 computation is iterative.
73 The MTPTracker takes as input
75 (1) a number of locations and a number of time steps
77 (2) a spatial topology composed of
79 - the allowed motions between locations (a Boolean flag for each
80 pair of locations from/to)
82 - the entrances (a Boolean flag for each location and time step)
84 - the exits (a Boolean flag for each location and time step)
86 (3) a detection score for every location and time, which stands for
88 log( P(Y(l,t) = 1 | X) / P(Y(l,t) = 0 | X) )
90 where Y is the occupancy of location l at time t and X is the
91 available observation. In particular, this score is negative on
92 locations where the probability that the location is occupied is
93 close to 0, and positive when it is close to 1.
95 From this parameters, the MTPTracker can compute the best set of
96 disjoint trajectories consistent with the defined topology, which
97 maximizes the overall detection score (i.e. the sum of the detection
98 scores of the nodes visited by the trajectories). In particular, if no
99 trajectory of total positive detection score exists, this optimal set
100 of trajectories is empty.
102 An MTPTracker is a wrapper around an MTPGraph. From the defined
103 spatial topology and number of time steps, it builds a graph with one
104 source, one sink, and two nodes per location and time. The edges from
105 the source or to the sink, or between these pairs of nodes, are of
106 length zero, and the edges between the two nodes of such a pair have
107 negative lengths, equal to the opposite of the corresponding detection
108 scores. This structure ensures that the trajectories computed by the
109 MTPTracker will be node-disjoint, since the trajectories computed by
110 the MTPGraph are edge-disjoint.
112 The file mtp_example.cc gives a very simple usage example of the
113 MTPTracker class by setting the tracker parameters dynamically, and
114 running the tracking.
116 The tracker data file for MTPTracker::read has the following format,
117 where L is the number of locations and T is the number of time steps:
119 ---------------------------- snip snip -------------------------------
122 bool:allowed_motion_from_1_to_1 ... bool:allowed_motion_from_1_to_L
124 bool:allowed_motion_from_L_to_1 ... bool:allowed_motion_from_L_to_L
126 bool:entrance_1_1 ... bool:entrance_1_L
128 bool:entrance_T_1 ... bool:entrance_T_L
130 bool:exit_1_1 ... bool:exit_1_L
132 bool:exit_T_1 ... bool:exit_T_L
134 float:detection_score_1_1 ... float:detection_score_1_L
136 float:detection_score_T_1 ... float:detection_score_T_L
137 ---------------------------- snip snip -------------------------------
139 The method MTPTracker::write_trajectories writes first the number of
140 trajectories, followed by one line per trajectory with the following
143 ---------------------------- snip snip -------------------------------
144 int:traj_number int:entrance_time int:duration float:score int:location_1 ... int:location_duration
145 ---------------------------- snip snip -------------------------------