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. Just execute
  22
  23   make
  24   ./mtp_example
  25
  26 It will create a synthetic dummy example, save its description in
  27 tracker.dat, and print the optimal detected trajectories.
  28
  29 If you now execute
  30
  31   ./mtp tracker.dat
  32
  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.
  36
  37 You can produce a pdf from the latter with the dot command from
  38 graphviz:
  39
  40   dot < graph.dot -T pdf -o graph.pdf
  41
  42 * IMPLEMENTATION
  43
  44 The two main classes are MTPGraph and MTPTracker.
  45
  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
  49 lengths.
  50
  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.
  56
  57 The MTPTracker class allows
  58
  59  (1) to define a spatial topology composed of
  60
  61      - a number of locations
  62
  63      - the allowed motions between them (a Boolean flag for each pair
  64        of locations from/to)
  65
  66      - the entrances (a Boolean flag for each location and time step)
  67
  68      - the exits (a Boolean flag for each location and time step)
  69
  70  (2) to define a number of time steps
  71
  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.
  75
  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
  79 the trajectories)
  80
  81 The MTPTracker is a wrapper around the MTPGraph class.
  82
  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.
  88
  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
  92 detection scores.
  93
  94 The file mtp_example.cc gives a very simple usage example of the
  95 MTPTracker class by setting the tracker parameters dynamically, and
  96 running the tracking.
  97
  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:
 100
 101 ---------------------------- snip snip -------------------------------
 102 int:L int:T
 103
 104 bool:allowed_motion_from_1_to_1 ... bool:allowed_motion_from_1_to_L
 105 ...
 106 bool:allowed_motion_from_L_to_1 ... bool:allowed_motion_from_L_to_L
 107
 108 bool:entrance_1_1 ... bool:entrance_1_L
 109 ...
 110 bool:entrance_T_1 ... bool:entrance_T_L
 111
 112 bool:exit_1_1 ... bool:exit_1_L
 113 ...
 114 bool:exit_T_1 ... bool:exit_T_L
 115
 116 float:detection_score_1_1 ... float:detection_score_1_L
 117 ...
 118 float:detection_score_T_1 ... float:detection_score_T_L
 119 ---------------------------- snip snip -------------------------------
 120
 121 The method MTPTracker::write_trajectories writes first the number of
 122 trajectories, followed by one line per trajectory with the following
 123 structure
 124
 125 ---------------------------- snip snip -------------------------------
 126 int:traj_number int:entrance_time int:duration float:score int:location_1 ... int:location_duration
 127 ---------------------------- snip snip -------------------------------
 128
 129 --
 130 François Fleuret
 131 September 2012