README.txt

   1
   2                      Multi-Tracked Paths (MTP)
   3                      -------------------------
   4
   5 * INTRODUCTION
   6
   7 This is a very simple implementation of a variant of KSP applied to
   8 multi-target, as described in
   9
  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,
  13   2011.
  14
  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.
  18
  19 * INSTALLATION
  20
  21 This source code 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 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:
  37
  38   dot < graph.dot -T pdf -o graph.pdf
  39
  40 * IMPLEMENTATION
  41
  42 The two main classes are MTPGraph and MTPTracker.
  43
  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.
  47
  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.
  53
  54 The MTPTracker class allows
  55
  56  (1) to define a spatial topology composed of
  57
  58      - a number of locations
  59      - the allowed motions between them (i.e. a Boolean flag for each
  60        pair of locations)
  61      - the entrances (a Boolean flag for each location)
  62      - the exits (a Boolean flag for each location)
  63
  64  (2) to define a number of time steps
  65
  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.
  69
  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
  73 the trajectories)
  74
  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.
  80
  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.
  84
  85 The file mtp_example.cc gives a very simple usage example of the
  86 MTPTracker class by setting the tracker parameters dynamically, and
  87 running the tracking.
  88
  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:
  91
  92 ---------------------------- snip snip -------------------------------
  93 int:L int:T
  94
  95 bool:allowed_motion_from_1_to_1 ... bool:allowed_motion_from_1_to_L
  96 ...
  97 bool:allowed_motion_from_L_to_1 ... bool:allowed_motion_from_L_to_L
  98
  99 bool:is_an_entrance_1 ... bool:is_an_entrance_L
 100
 101 bool:is_an_exit_1 ... bool:is_an_exit_L
 102
 103 float:detection_score_1_1 ... float:detection_score_1_L
 104 ...
 105 float:detection_score_T_1 ... float:detection_score_T_L
 106 ---------------------------- snip snip -------------------------------
 107
 108 The method MTPTracker::write_trajectories writes first the number of
 109 trajectories, followed by one line per trajectory with the following
 110 structure
 111
 112 ---------------------------- snip snip -------------------------------
 113 int:traj_number int:entrance_time int:duration float:score int:location_1 ... int:location_duration
 114 ---------------------------- snip snip -------------------------------
 115
 116 --
 117 François Fleuret
 118 August 2012