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.
  18
  19 * INSTALLATION
  20
  21 This software should compile with any C++ compiler. Under a unix-like
  22 environment, just execute
  23
  24   make
  25   ./mtp_example
  26
  27 It will create a synthetic dummy example, save its description in
  28 tracker.dat, and print the optimal detected trajectories.
  29
  30 If you now execute
  31
  32   ./mtp tracker.dat
  33
  34 It will load the file tracker.dat saved by the previous command, run
  35 the detection, save the detected trajectories in result.trj, and the
  36 underlying graph with occupied edges in graph.dot.
  37
  38 If you do have the graphviz set of tools installed, you can produce a
  39 pdf from the latter with the dot command:
  40
  41   dot < graph.dot -T pdf -o graph.pdf
  42
  43 * IMPLEMENTATION
  44
  45 The two main classes are MTPGraph and MTPTracker.
  46
  47 The MTPGraph class contains a directed acyclic graph (DAG), with a
  48 length for each edge -- which can be negative -- and has methods to
  49 compute the family of paths in this graph that globally minimizes the
  50 sum of edge lengths.
  51
  52 If there are no path of negative length, this optimal family will be
  53 empty, since the minimum total length you can achieve is zero. Note
  54 that the procedure is similar to that of KSP, in the sense that the
  55 family it computes eventually is globally optimal, even if the
  56 computation is iterative.
  57
  58 The MTPTracker is defined by
  59
  60  (1) a spatial topology composed of
  61
  62      - a number of locations
  63
  64      - the allowed motions between them (a Boolean flag for each pair
  65        of locations from/to)
  66
  67      - the entrances (a Boolean flag for each location and time step)
  68
  69      - the exits (a Boolean flag for each location and time step)
  70
  71  (2) a number of time steps
  72
  73  (3) a detection score for every location and time, which stands for
  74      log(P(Y = 1 | X)/P(Y = 0 | X)) where Y is the said location
  75      occupancy and X the available observations.
  76
  77 From this setting, MTPTracker has methods to compute the best set of
  78 disjoint trajectories consistent with the topology, which maximizes
  79 the overall detection score (i.e. the sum of the detection scores of
  80 the nodes visited by the trajectories). If no trajectory of total
  81 positive detection score exists, this optimal set of trajectories will
  82 be empty.
  83
  84 The MTPTracker is a wrapper around the MTPGraph class.
  85
  86 From the defined spatial topology and number of time steps, it builds
  87 a graph with one source, one sink, and two nodes per location and
  88 time. This structure ensures that the trajectories computed by the
  89 MTPTracker will be node-disjoint, since the trajectories computed by
  90 the MTPGraph are edge-disjoint.
  91
  92 The edges from the source or to the sink, or between these pairs of
  93 nodes, are of length zero, and the edges between the two nodes of such
  94 a pair have negative lengths, equal to the opposite of the
  95 corresponding detection scores.
  96
  97 The file mtp_example.cc gives a very simple usage example of the
  98 MTPTracker class by setting the tracker parameters dynamically, and
  99 running the tracking.
 100
 101 The tracker data file for MTPTracker::read has the following format,
 102 where L is the number of locations and T is the number of time steps:
 103
 104   ---------------------------- snip snip -------------------------------
 105   int:L int:T
 106
 107   bool:allowed_motion_from_1_to_1 ... bool:allowed_motion_from_1_to_L
 108   ...
 109   bool:allowed_motion_from_L_to_1 ... bool:allowed_motion_from_L_to_L
 110
 111   bool:entrance_1_1 ... bool:entrance_1_L
 112   ...
 113   bool:entrance_T_1 ... bool:entrance_T_L
 114
 115   bool:exit_1_1 ... bool:exit_1_L
 116   ...
 117   bool:exit_T_1 ... bool:exit_T_L
 118
 119   float:detection_score_1_1 ... float:detection_score_1_L
 120   ...
 121   float:detection_score_T_1 ... float:detection_score_T_L
 122   ---------------------------- snip snip -------------------------------
 123
 124 The method MTPTracker::write_trajectories writes first the number of
 125 trajectories, followed by one line per trajectory with the following
 126 structure
 127
 128   ---------------------------- snip snip -------------------------------
 129   int:traj_number int:entrance_time int:duration float:score int:location_1 ... int:location_duration
 130   ---------------------------- snip snip -------------------------------
 131
 132 --
 133 François Fleuret
 134 September 2012