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
33 - mtp_stress_test creates a larger problem with a lot of noise and
34 multiple trajectories, to check the behavior of the code under
35 slightly more complex situations.
39 This software should compile with any C++ compiler. Under a unix-like
40 environment, just execute
45 It will create a synthetic dummy example, save its description in
46 tracker.dat, and print the optimal detected trajectories.
50 ./mtp --verbose --trajectory-file result.trj --graph-file graph.dot tracker.dat
52 It will load the file tracker.dat saved by the previous command, run
53 the detection, save the detected trajectories in result.trj, and the
54 underlying graph with occupied edges in graph.dot.
56 If you do have the graphviz set of tools installed, you can produce a
57 pdf from the latter with the dot command:
59 dot < graph.dot -T pdf -o graph.pdf
63 The two main classes are MTPGraph and MTPTracker.
65 The MTPGraph class contains a directed acyclic graph (DAG), with a
66 length for each edge -- which can be negative -- and has methods to
67 compute the family of paths in this graph that globally minimizes the
70 If there are no path of negative length, this optimal family will be
71 empty, since the minimum total length you can achieve is zero. Note
72 that the procedure is similar to that of KSP, in the sense that the
73 family it computes eventually is globally optimal, even if the
74 computation is iterative.
76 The MTPTracker takes as input
78 (1) a spatial topology composed of
80 - a number of locations
82 - the allowed motions between them (a Boolean flag for each pair
85 - the entrances (a Boolean flag for each location and time step)
87 - the exits (a Boolean flag for each location and time step)
89 (2) a number of time steps
91 (3) a detection score for every location and time, which stands for
93 log( P(Y(l,t) = 1 | X) / P(Y(l,t) = 0 | X) )
95 where Y is the occupancy of location l at time t and X is the
96 available observation. Hence, this score is negative on locations
97 where the probability that the location is occupied is close to
98 0, and positive when it is close to 1.
100 From this parameters, an MTPTracker can compute the best set of
101 disjoint trajectories consistent with the defined topology, which
102 maximizes the overall detection score (i.e. the sum of the detection
103 scores of the nodes visited by the trajectories). In particular, if no
104 trajectory of total positive detection score exists, this optimal set
105 of trajectories is empty.
107 An MTPTracker is a wrapper around an MTPGraph. From the defined
108 spatial topology and number of time steps, it builds a graph with one
109 source, one sink, and two nodes per location and time. The edges from
110 the source or to the sink, or between these pairs of nodes, are of
111 length zero, and the edges between the two nodes of such a pair have
112 negative lengths, equal to the opposite of the corresponding detection
113 scores. This structure ensures that the trajectories computed by the
114 MTPTracker will be node-disjoint, since the trajectories computed by
115 the MTPGraph are edge-disjoint.
117 The file mtp_example.cc gives a very simple usage example of the
118 MTPTracker class by setting the tracker parameters dynamically, and
119 running the tracking.
121 The tracker data file for MTPTracker::read has the following format,
122 where L is the number of locations and T is the number of time steps:
124 ---------------------------- snip snip -------------------------------
127 bool:allowed_motion_from_1_to_1 ... bool:allowed_motion_from_1_to_L
129 bool:allowed_motion_from_L_to_1 ... bool:allowed_motion_from_L_to_L
131 bool:entrance_1_1 ... bool:entrance_1_L
133 bool:entrance_T_1 ... bool:entrance_T_L
135 bool:exit_1_1 ... bool:exit_1_L
137 bool:exit_T_1 ... bool:exit_T_L
139 float:detection_score_1_1 ... float:detection_score_1_L
141 float:detection_score_T_1 ... float:detection_score_T_L
142 ---------------------------- snip snip -------------------------------
144 The method MTPTracker::write_trajectories writes first the number of
145 trajectories, followed by one line per trajectory with the following
148 ---------------------------- snip snip -------------------------------
149 int:traj_number int:entrance_time int:duration float:score int:location_1 ... int:location_duration
150 ---------------------------- snip snip -------------------------------