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 It works with negative edge lengths and stops computing new path when
17 it can not find one of negative total length, instead of fixing the
18 total number of paths to a constant K.
22 This software should compile with any C++ compiler. Just execute
27 It will create a synthetic dummy example, save its description in
28 tracker.dat, and print the optimal detected trajectories.
34 It will load the tracker.dat saved by the previous command, run the
35 detection, save the detected trajectories in result.trj, and the
36 underlying graph with occupied edges in graph.dot.
38 You can produce a pdf from the latter with the dot command from
41 dot < graph.dot -T pdf -o graph.pdf
45 The two main classes are MTPGraph and MTPTracker.
47 The MTPGraph class stores a directed acyclic graph (DAG), with a
48 length for each edge -- which can be negative -- and can compute the
49 family of paths in this graph that globally minimizes the sum of edge
52 This means that it will iteratively add paths as long as it can find
53 some with negative length. If there are no such path, it will compute
54 no path at all. Note that the procedure is similar to that of KSP, in
55 the sense that the family it computes eventually is globally optimal,
56 even if the computation is iterative.
58 The MTPTracker class allows
60 (1) to define a spatial topology composed of
62 - a number of locations
64 - the allowed motions between them (a Boolean flag for each pair
67 - the entrances (a Boolean flag for each location)
69 - the exits (a Boolean flag for each location)
71 (2) to define a number of time steps
73 (3) to set for every location and time a detection score, which
74 should stand for log(P(Y = 1 | X)/P(Y = 0 | X)) where Y is for
75 the location occupancy and X the available observations.
77 From this setting, it computes the best set of disjoint trajectories
78 consistent with the topology, which maximizes the overall detection
79 score (i.e. the sum of the detection scores of the nodes visited by
82 The MTPTracker is a wrapper around the MTPGraph class.
84 From the defined the spatial topology and number of time steps, it
85 builds a graph with one source, one sink, and two nodes per location
86 and time. This structure ensures that the trajectories computed by the
87 MTPTracker will be node-disjoint, since the trajectories computed by
88 the MTPGraph are edge-disjoint.
90 The edges from the source or to the sink, or between these pairs of
91 nodes, are of length zero, and the edges between the two nodes of such
92 a pair have lengths equal to the opposite of the corresponding
95 The file mtp_example.cc gives a very simple usage example of the
96 MTPTracker class by setting the tracker parameters dynamically, and
99 The tracker data file for MTPTracker::read has the following format,
100 where L is the number of locations and T is the number of time steps:
102 ---------------------------- snip snip -------------------------------
105 bool:allowed_motion_from_1_to_1 ... bool:allowed_motion_from_1_to_L
107 bool:allowed_motion_from_L_to_1 ... bool:allowed_motion_from_L_to_L
109 bool:force_empty_first_frame bool:force_empty_last_frame
111 bool:is_an_entrance_1 ... bool:is_an_entrance_L
113 bool:is_an_exit_1 ... bool:is_an_exit_L
115 float:detection_score_1_1 ... float:detection_score_1_L
117 float:detection_score_T_1 ... float:detection_score_T_L
118 ---------------------------- snip snip -------------------------------
120 The method MTPTracker::write_trajectories writes first the number of
121 trajectories, followed by one line per trajectory with the following
124 ---------------------------- snip snip -------------------------------
125 int:traj_number int:entrance_time int:duration float:score int:location_1 ... int:location_duration
126 ---------------------------- snip snip -------------------------------