README.md

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