Typo.
[mtp.git] / README.txt
1
2                        Multi-Tracked Paths (MTP)
3                        -------------------------
4
5 * INTRODUCTION
6
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
9 in
10
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,
14   2011.
15
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.
19
20 This software package includes three commands:
21
22  - mtp is the generic command to use in practice. It takes tracking
23    parameters as input, and prints the tracked trajectories as
24    output. The format for these parameters is given at the bottom of
25    this documentation.
26
27  - mtp_example creates a tracking toy example, and runs the tracking
28    algorithm on it. It gives an example of how to use MTPTracker on a
29    configuration produced dynamically, and produce a test input file
30    for the mtp command.
31
32  - mtp_stress_test creates a larger problem with a lot of noise and
33    multiple trajectories, to check the behavior of the code under
34    slightly more complex situations.
35
36 * INSTALLATION
37
38 This software should compile with any C++ compiler. Under a unix-like
39 environment, just execute
40
41   make
42   ./mtp_example
43
44 It will create a synthetic dummy example, save its description in
45 tracker.dat, and print the optimal detected trajectories.
46
47 If you now execute
48
49   ./mtp --verbose --trajectory-file result.trj --graph-file graph.dot tracker.dat
50
51 It will load the file tracker.dat saved by the previous command, run
52 the detection, save the detected trajectories in result.trj, and the
53 underlying graph with occupied edges in graph.dot.
54
55 If you do have the graphviz set of tools installed, you can produce a
56 pdf from the latter with the dot command:
57
58   dot < graph.dot -T pdf -o graph.pdf
59
60 * IMPLEMENTATION
61
62 The two main classes are MTPGraph and MTPTracker.
63
64 The MTPGraph class contains a directed acyclic graph (DAG), with a
65 length for each edge -- which can be negative -- and has methods to
66 compute the family of paths in this graph that globally minimizes the
67 sum of edge lengths.
68
69 If there are no path of negative length, this optimal family will be
70 empty, since the minimum total length you can achieve is zero. Note
71 that the procedure is similar to that of KSP, in the sense that the
72 family it computes eventually is globally optimal, even if the
73 computation is iterative.
74
75 The MTPTracker takes as input
76
77  (1) a spatial topology composed of
78
79      - a number of locations
80
81      - the allowed motions between them (a Boolean flag for each pair
82        of locations from/to)
83
84      - the entrances (a Boolean flag for each location and time step)
85
86      - the exits (a Boolean flag for each location and time step)
87
88  (2) a number of time steps
89
90  (3) a detection score for every location and time, which stands for
91
92              log( P(Y(l,t) = 1 | X) / P(Y(l,t) = 0 | X) )
93
94      where Y is the occupancy of location l at time t and X is the
95      available observation. Hence, this score is negative on locations
96      where the probability that the location is occupied is close to
97      0, and positive when it is close to 1.
98
99 From this parameters, an MTPTracker can compute the best set of
100 disjoint trajectories consistent with the defined topology, which
101 maximizes the overall detection score (i.e. the sum of the detection
102 scores of the nodes visited by the trajectories). In particular, if no
103 trajectory of total positive detection score exists, this optimal set
104 of trajectories is empty.
105
106 An MTPTracker is a wrapper around an MTPGraph. From the defined
107 spatial topology and number of time steps, it builds a graph with one
108 source, one sink, and two nodes per location and time. The edges from
109 the source or to the sink, or between these pairs of nodes, are of
110 length zero, and the edges between the two nodes of such a pair have
111 negative lengths, equal to the opposite of the corresponding detection
112 scores. This structure ensures that the trajectories computed by the
113 MTPTracker will be node-disjoint, since the trajectories computed by
114 the MTPGraph are edge-disjoint.
115
116 The file mtp_example.cc gives a very simple usage example of the
117 MTPTracker class by setting the tracker parameters dynamically, and
118 running the tracking.
119
120 The tracker data file for MTPTracker::read has the following format,
121 where L is the number of locations and T is the number of time steps:
122
123 ---------------------------- snip snip -------------------------------
124   int:L int:T
125
126   bool:allowed_motion_from_1_to_1 ... bool:allowed_motion_from_1_to_L
127   ...
128   bool:allowed_motion_from_L_to_1 ... bool:allowed_motion_from_L_to_L
129
130   bool:entrance_1_1 ... bool:entrance_1_L
131   ...
132   bool:entrance_T_1 ... bool:entrance_T_L
133
134   bool:exit_1_1 ... bool:exit_1_L
135   ...
136   bool:exit_T_1 ... bool:exit_T_L
137
138   float:detection_score_1_1 ... float:detection_score_1_L
139   ...
140   float:detection_score_T_1 ... float:detection_score_T_L
141 ---------------------------- snip snip -------------------------------
142
143 The method MTPTracker::write_trajectories writes first the number of
144 trajectories, followed by one line per trajectory with the following
145 structure
146
147 ---------------------------- snip snip -------------------------------
148   int:traj_number int:entrance_time int:duration float:score int:location_1 ... int:location_duration
149 ---------------------------- snip snip -------------------------------
150
151 --
152 François Fleuret
153 December 2012