2 Multi-Tracked Paths (MTP)
3 -------------------------
7 This is a very simple implementation of a variant of KSP applied to
8 multi-target, as described in
10 J. Berclaz, E. Turetken, F. Fleuret, and P. Fua. Multiple Object
11 Tracking using K-Shortest Paths Optimization. IEEE Transactions on
12 Pattern Analysis and Machine Intelligence (TPAMI), 33(9):1806-1819,
15 It works with negative edge length and stops when it can not find any
16 path of negative total length, instead of fixing the total number of
17 paths to a constant K.
21 This source code 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 example, run the detection, save the
34 detected trajectories in result.trj, and the underlying graph with
35 occupied edges in graph.dot. You can produce a pdf from the latter
36 with the dot command from graphviz:
38 dot < graph.dot -T pdf -o graph.pdf
42 The two main classes are MTPGraph and MTPTracker.
44 The MTPGraph class stores a directed acyclic graph (DAG), with a
45 length for each edge -- which can be negative -- and can compute the
46 family of paths in this graph that minimizes the sum of edge lengths.
48 This means that it will iteratively add paths as long as it can find
49 some with negative length. If there are no such path, it will compute
50 no path at all. Note that the procedure is similar to that of KSP, in
51 the sense that the family it computes eventually is globally optimal,
52 even if the computation is iterative.
54 The MTPTracker class allows
56 (1) to define a spatial topology composed of
58 - a number of locations
59 - the allowed motions between them (i.e. a Boolean flag for each
61 - the entrances (a Boolean flag for each location)
62 - the exits (a Boolean flag for each location)
64 (2) to define a number of time steps
66 (3) to set for every location and time a detection score, which
67 should be equal to log(P(Y = 1 | X)/P(Y = 0 | X)) where Y stands
68 for the location occupancy and X for the observations.
70 From this setting, it computes the best set of disjoint trajectories
71 consistent with the topology, which maximizes the overall detection
72 score (i.e. the sum of the detection scores of the nodes visited by
75 The MTPTracker class uses the MTPGraph. From the definition of the
76 spatial topology, it builds a graph with one source, one sink, and two
77 nodes per location and time. This structure ensures the trajectories
78 computed by the tracker to be node-disjoint by forcing the paths
79 computed by the MTPGraph to be edge-disjoint.
81 The edges from the source or to the sink, or between these pairs, are
82 of length zero, and the edge between the two nodes of such a pair has
83 a length equal to the opposite of the detection score.
85 The file mtp_example.cc gives a very simple usage example of the
86 MTPTracker class by setting the tracker parameters dynamically, and
89 The tracker data file for MTPTracker::read has the following format,
90 where L is the number of locations and T is the number of time steps:
92 ---------------------------- snip snip -------------------------------
95 bool:allowed_motion_from_1_to_1 ... bool:allowed_motion_from_1_to_L
97 bool:allowed_motion_from_L_to_1 ... bool:allowed_motion_from_L_to_L
99 bool:is_an_entrance_1 ... bool:is_an_entrance_L
101 bool:is_an_exit_1 ... bool:is_an_exit_L
103 float:detection_score_1_1 ... float:detection_score_1_L
105 float:detection_score_T_1 ... float:detection_score_T_L
106 ---------------------------- snip snip -------------------------------
108 The method MTPTracker::write_trajectories writes first the number of
109 trajectories, followed by one line per trajectory with the following
112 ---------------------------- snip snip -------------------------------
113 int:traj_number int:entrance_time int:duration float:score int:location_1 ... int:location_duration
114 ---------------------------- snip snip -------------------------------