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 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.
  19
  20 * INSTALLATION
  21
  22 This software should compile with any C++ compiler. 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 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.
  37
  38 You can produce a pdf from the latter with the dot command from
  39 graphviz:
  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 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
  50 lengths.
  51
  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.
  57
  58 The MTPTracker class allows
  59
  60  (1) to define 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)
  68
  69      - the exits (a Boolean flag for each location)
  70
  71  (2) to define a number of time steps
  72
  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.
  76
  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
  80 the trajectories)
  81
  82 The MTPTracker is a wrapper around the MTPGraph class.
  83
  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.
  89
  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
  93 detection scores.
  94
  95 The file mtp_example.cc gives a very simple usage example of the
  96 MTPTracker class by setting the tracker parameters dynamically, and
  97 running the tracking.
  98
  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:
 101
 102 ---------------------------- snip snip -------------------------------
 103 int:L int:T
 104
 105 bool:allowed_motion_from_1_to_1 ... bool:allowed_motion_from_1_to_L
 106 ...
 107 bool:allowed_motion_from_L_to_1 ... bool:allowed_motion_from_L_to_L
 108
 109 bool:is_an_entrance_1 ... bool:is_an_entrance_L
 110
 111 bool:is_an_exit_1 ... bool:is_an_exit_L
 112
 113 float:detection_score_1_1 ... float:detection_score_1_L
 114 ...
 115 float:detection_score_T_1 ... float:detection_score_T_L
 116 ---------------------------- snip snip -------------------------------
 117
 118 The method MTPTracker::write_trajectories writes first the number of
 119 trajectories, followed by one line per trajectory with the following
 120 structure
 121
 122 ---------------------------- snip snip -------------------------------
 123 int:traj_number int:entrance_time int:duration float:score int:location_1 ... int:location_duration
 124 ---------------------------- snip snip -------------------------------
 125
 126 --
 127 François Fleuret
 128 September 2012