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