README.txt

   1
   2 This is a very simple implementation of the KSP applied to
   3 multi-target tracking. It is dubbed Multi-Tracked Path since it
   4 differs a bit from the standard KSP. It works with negative edge
   5 length and stops when it can not find path of negative length anymore
   6 instead of fixing the total number of paths to a constant.
   7
   8 The two main classes are MTPGraph and Tracker.
   9
  10 The MTPGraph class stores a directed acyclic graph (DAG), with a
  11 length for each edge (which can be negative), and can compute the
  12 family of paths in this graph that minimizes the sum of edge
  13 lengths.
  14
  15 This means that it will iteratively add paths as long as it can find
  16 some with negative length. If there are no such path, it will compute
  17 no path at all. Note that the solution it finds is globally optimal.
  18
  19 The Tracker class allows
  20
  21  (1) to define a spatial topology composed of
  22
  23      - a number of locations
  24      - the allowed motions between them (i.e. a Boolean flag for each
  25        pair of locations)
  26      - the entrances (a Boolean flag for each location)
  27      - the exits (a Boolean flag for each location)
  28
  29  (2) to define a number of time steps
  30
  31  (3) to set for every location and time a detection score
  32
  33 From this input, it computes the best set of disjoint trajectories
  34 consistent with the topology, which maximizes the overall detection
  35 score (i.e. the sum of the detection scores of the nodes visited by
  36 the trajectories)
  37
  38 The Tracker class uses the MTPGraph. From the definition of the
  39 spatial topology, it builds a graph with one source, one sink, and two
  40 nodes per location and time. This structure ensures the trajectories
  41 computed by the tracker to be node-disjoint by forcing the paths
  42 computed by the MTPGraph to be edge-disjoint. The edges from the
  43 source or to the sink, or between these pairs, are of length zero, and
  44 the edge between the two nodes of such a pair has a length equal to
  45 the opposite of the detection score.
  46
  47 The file mtp.cc gives a very simple usage example of the Tracker
  48 class.
  49
  50 --
  51 François Fleuret
  52 August 2012