README.txt

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