README.txt

   1
   2 * INTRODUCTION
   3
   4 This is a very simple implementation of a variant of KSP applied to
   5 multi-target tracking dubbed "Multi-Tracked Paths" (MTP).
   6
   7 It works with negative edge length and stops when it can not find any
   8 path of negative total length, instead of fixing the total number of
   9 paths to a constant K.
  10
  11 * INSTALLATION
  12
  13 This source code should compile with any C++ compiler. Just execute
  14
  15   make
  16   ./mtp_example
  17
  18 It will create a synthetic dummy example, save its description in
  19 tracker.dat, and print the optimal detected trajectories.
  20
  21 If you now execute
  22
  23   ./mtp tracker.dat
  24
  25 It will load the tracker.dat example, run the detection, save the
  26 detected trajectories in result.trj, and the underlying graph with
  27 occupied edges in graph.dot. You can produce a pdf from the latter
  28 with the dot command from graphviz:
  29
  30   dot < graph.dot -T pdf -o graph.pdf
  31
  32 * IMPLEMENTATION
  33
  34 The two main classes are MTPGraph and MTPTracker.
  35
  36 The MTPGraph class stores a directed acyclic graph (DAG), with a
  37 length for each edge -- which can be negative -- and can compute the
  38 family of paths in this graph that minimizes the sum of edge lengths.
  39
  40 This means that it will iteratively add paths as long as it can find
  41 some with negative length. If there are no such path, it will compute
  42 no path at all. Note that the procedure is similar to that of KSP, in
  43 the sense that the family it computes eventually is globally optimal,
  44 even if the computation is iterative.
  45
  46 The MTPTracker class allows
  47
  48  (1) to define a spatial topology composed of
  49
  50      - a number of locations
  51      - the allowed motions between them (i.e. a Boolean flag for each
  52        pair of locations)
  53      - the entrances (a Boolean flag for each location)
  54      - the exits (a Boolean flag for each location)
  55
  56  (2) to define a number of time steps
  57
  58  (3) to set for every location and time a detection score, which
  59      should be equal to log(P(Y = 1 | X)/P(Y = 0 | X)) where Y stands
  60      for the location occupancy and X for the observations.
  61
  62 From this setting, it computes the best set of disjoint trajectories
  63 consistent with the topology, which maximizes the overall detection
  64 score (i.e. the sum of the detection scores of the nodes visited by
  65 the trajectories)
  66
  67 The MTPTracker class uses the MTPGraph. From the definition of the
  68 spatial topology, it builds a graph with one source, one sink, and two
  69 nodes per location and time. This structure ensures the trajectories
  70 computed by the tracker to be node-disjoint by forcing the paths
  71 computed by the MTPGraph to be edge-disjoint.
  72
  73 The edges from the source or to the sink, or between these pairs, are
  74 of length zero, and the edge between the two nodes of such a pair has
  75 a length equal to the opposite of the detection score.
  76
  77 The file mtp_example.cc gives a very simple usage example of the
  78 MTPTracker class by setting the tracker parameters dynamically, and
  79 running the tracking.
  80
  81 The tracker data file for MTPTracker::read has the following format,
  82 where L is the number of locations and T is the number of time steps:
  83
  84 ---------------------------- snip snip -------------------------------
  85 int:L int:T
  86
  87 bool:allowed_motion_from_1_to_1 ... bool:allowed_motion_from_1_to_L
  88 ...
  89 bool:allowed_motion_from_L_to_1 ... bool:allowed_motion_from_L_to_L
  90
  91 bool:is_an_entrance_1 ... bool:is_an_entrance_L
  92
  93 bool:is_an_exit_1 ... bool:is_an_exit_L
  94
  95 float:detection_score_1_1 ... float:detection_score_1_L
  96 ...
  97 float:detection_score_T_1 ... float:detection_score_T_L
  98 ---------------------------- snip snip -------------------------------
  99
 100 The method MTPTracker::write_trajectories writes first the number of
 101 trajectories, followed by one line per trajectory with the following
 102 structure
 103
 104 ---------------------------- snip snip -------------------------------
 105 int:traj_number int:entrance_time int:duration float:score int:location_1 ... int:location_duration
 106 ---------------------------- snip snip -------------------------------
 107
 108 --
 109 François Fleuret
 110 August 2012