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 uses a Dijkstra with a
18 Binary Heap for the min-queue, and not the optimal Fibonacci heap.
22 This software should compile with any C++ compiler. Under a unix-like
23 environment, just execute
28 It will create a synthetic dummy example, save its description in
29 tracker.dat, and print the optimal detected trajectories.
33 ./mtp --verbose --trajectory-file result.trj --graph-file graph.dot < tracker.dat
35 It will load the file tracker.dat saved by the previous command, run
36 the detection, save the detected trajectories in result.trj, and the
37 underlying graph with occupied edges in graph.dot.
39 If you do have the graphviz set of tools installed, you can produce a
40 pdf from the latter with the dot command:
42 dot < graph.dot -T pdf -o graph.pdf
46 The two main classes are MTPGraph and MTPTracker.
48 The MTPGraph class contains a directed acyclic graph (DAG), with a
49 length for each edge -- which can be negative -- and has methods to
50 compute the family of paths in this graph that globally minimizes the
53 If there are no path of negative length, this optimal family will be
54 empty, since the minimum total length you can achieve is zero. Note
55 that the procedure is similar to that of KSP, in the sense that the
56 family it computes eventually is globally optimal, even if the
57 computation is iterative.
59 The MTPTracker takes as input
61 (1) a spatial topology composed of
63 - a number of locations
65 - the allowed motions between them (a Boolean flag for each pair
68 - the entrances (a Boolean flag for each location and time step)
70 - the exits (a Boolean flag for each location and time step)
72 (2) a number of time steps
74 (3) a detection score for every location and time, which stands for
76 log( P(Y(l,t) = 1 | X) / P(Y(l,t) = 0 | X) )
78 where Y is the occupancy of location l at time t and X is the
79 available observation. Hence, this score is negative on locations
80 where the probability that the location is occupied is close to
81 0, and positive when it is close to 1.
83 From this parameters, an MTPTracker can compute the best set of
84 disjoint trajectories consistent with the defined topology, which
85 maximizes the overall detection score (i.e. the sum of the detection
86 scores of the nodes visited by the trajectories). In particular, if no
87 trajectory of total positive detection score exists, this optimal set
88 of trajectories is empty.
90 An MTPTracker is a wrapper around an MTPGraph. From the defined
91 spatial topology and number of time steps, it builds a graph with one
92 source, one sink, and two nodes per location and time. The edges from
93 the source or to the sink, or between these pairs of nodes, are of
94 length zero, and the edges between the two nodes of such a pair have
95 negative lengths, equal to the opposite of the corresponding detection
96 scores. This structure ensures that the trajectories computed by the
97 MTPTracker will be node-disjoint, since the trajectories computed by
98 the MTPGraph are edge-disjoint.
100 The file mtp_example.cc gives a very simple usage example of the
101 MTPTracker class by setting the tracker parameters dynamically, and
102 running the tracking.
104 The tracker data file for MTPTracker::read has the following format,
105 where L is the number of locations and T is the number of time steps:
107 ---------------------------- snip snip -------------------------------
110 bool:allowed_motion_from_1_to_1 ... bool:allowed_motion_from_1_to_L
112 bool:allowed_motion_from_L_to_1 ... bool:allowed_motion_from_L_to_L
114 bool:entrance_1_1 ... bool:entrance_1_L
116 bool:entrance_T_1 ... bool:entrance_T_L
118 bool:exit_1_1 ... bool:exit_1_L
120 bool:exit_T_1 ... bool:exit_T_L
122 float:detection_score_1_1 ... float:detection_score_1_L
124 float:detection_score_T_1 ... float:detection_score_T_L
125 ---------------------------- snip snip -------------------------------
127 The method MTPTracker::write_trajectories writes first the number of
128 trajectories, followed by one line per trajectory with the following
131 ---------------------------- snip snip -------------------------------
132 int:traj_number int:entrance_time int:duration float:score int:location_1 ... int:location_duration
133 ---------------------------- snip snip -------------------------------