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