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.
21 This software should compile with any C++ compiler. Just execute
26 It will create a synthetic dummy example, save its description in
27 tracker.dat, and print the optimal detected trajectories.
33 It will load the tracker.dat saved by the previous command, run the
34 detection, save the detected trajectories in result.trj, and the
35 underlying graph with occupied edges in graph.dot.
37 You can produce a pdf from the latter with the dot command from
40 dot < graph.dot -T pdf -o graph.pdf
44 The two main classes are MTPGraph and MTPTracker.
46 The MTPGraph class stores a directed acyclic graph (DAG), with a
47 length for each edge -- which can be negative -- and can compute the
48 family of paths in this graph that globally minimizes the sum of edge
51 This means that it will iteratively add paths as long as it can find
52 some with negative length. If there are no such path, it will compute
53 no path at all. Note that the procedure is similar to that of KSP, in
54 the sense that the family it computes eventually is globally optimal,
55 even if the computation is iterative.
57 The MTPTracker class allows
59 (1) to define a spatial topology composed of
61 - a number of locations
63 - the allowed motions between them (a Boolean flag for each pair
66 - the entrances (a Boolean flag for each location and time step)
68 - the exits (a Boolean flag for each location and time step)
70 (2) to define a number of time steps
72 (3) to set for every location and time a detection score, which
73 should stand for log(P(Y = 1 | X)/P(Y = 0 | X)) where Y is for
74 the location occupancy and X the available observations.
76 From this setting, it computes the best set of disjoint trajectories
77 consistent with the topology, which maximizes the overall detection
78 score (i.e. the sum of the detection scores of the nodes visited by
81 The MTPTracker is a wrapper around the MTPGraph class.
83 From the defined the spatial topology and number of time steps, it
84 builds a graph with one source, one sink, and two nodes per location
85 and time. This structure ensures that the trajectories computed by the
86 MTPTracker will be node-disjoint, since the trajectories computed by
87 the MTPGraph are edge-disjoint.
89 The edges from the source or to the sink, or between these pairs of
90 nodes, are of length zero, and the edges between the two nodes of such
91 a pair have lengths equal to the opposite of the corresponding
94 The file mtp_example.cc gives a very simple usage example of the
95 MTPTracker class by setting the tracker parameters dynamically, and
98 The tracker data file for MTPTracker::read has the following format,
99 where L is the number of locations and T is the number of time steps:
101 ---------------------------- snip snip -------------------------------
104 bool:allowed_motion_from_1_to_1 ... bool:allowed_motion_from_1_to_L
106 bool:allowed_motion_from_L_to_1 ... bool:allowed_motion_from_L_to_L
108 bool:entrance_1_1 ... bool:entrance_1_L
110 bool:entrance_T_1 ... bool:entrance_T_L
112 bool:exit_1_1 ... bool:exit_1_L
114 bool:exit_T_1 ... bool:exit_T_L
116 float:detection_score_1_1 ... float:detection_score_1_L
118 float:detection_score_T_1 ... float:detection_score_T_L
119 ---------------------------- snip snip -------------------------------
121 The method MTPTracker::write_trajectories writes first the number of
122 trajectories, followed by one line per trajectory with the following
125 ---------------------------- snip snip -------------------------------
126 int:traj_number int:entrance_time int:duration float:score int:location_1 ... int:location_duration
127 ---------------------------- snip snip -------------------------------