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