README.txt

   1
   2 * INTRODUCTION
   3
   4 This is a very simple implementation of a variant of KSP applied to
   5 multi-target tracking dubbed "Multi-Tracked Paths" (MTP).
   6
   7 It works with negative edge length and stops when it can not find any
   8 path of negative total length, instead of fixing the total number of
   9 paths to a constant K.
  10
  11 * INSTALLATION
  12
  13 This source code should compile with any C++ compiler. Just run "make"
  14 and execute the mtp executable. It should print the optimal detected
  15 trajectories, and save into graph.dot the result graph and
  16 trajectories in the dot syntax. You can produce a pdf from the latter
  17 with
  18
  19   dot < graph.dot -T pdf -o graph.pdf
  20
  21 * DESCRIPTION
  22
  23 The two main classes are MTPGraph and Tracker.
  24
  25 The MTPGraph class stores a directed acyclic graph (DAG), with a
  26 length for each edge -- which can be negative -- and can compute the
  27 family of paths in this graph that minimizes the sum of edge lengths.
  28
  29 This means that it will iteratively add paths as long as it can find
  30 some with negative length. If there are no such path, it will compute
  31 no path at all. Note that the solution it finds is globally
  32 optimal. Note that the procedure is similar to that of KSP, in the
  33 sense that the family it computes eventually is globally optimal, even
  34 if the procedure is iterative.
  35
  36 The Tracker class allows
  37
  38  (1) to define a spatial topology composed of
  39
  40      - a number of locations
  41      - the allowed motions between them (i.e. a Boolean flag for each
  42        pair of locations)
  43      - the entrances (a Boolean flag for each location)
  44      - the exits (a Boolean flag for each location)
  45
  46  (2) to define a number of time steps
  47
  48  (3) to set for every location and time a detection score, which
  49  should be equal to log(P(Y = 1 | X)/P(Y = 0 | X)) where Y stands for
  50  the location occupancy and X for the observations.
  51
  52 From this setting, it computes the best set of disjoint trajectories
  53 consistent with the topology, which maximizes the overall detection
  54 score (i.e. the sum of the detection scores of the nodes visited by
  55 the trajectories)
  56
  57 The Tracker class uses the MTPGraph. From the definition of the
  58 spatial topology, it builds a graph with one source, one sink, and two
  59 nodes per location and time. This structure ensures the trajectories
  60 computed by the tracker to be node-disjoint by forcing the paths
  61 computed by the MTPGraph to be edge-disjoint. The edges from the
  62 source or to the sink, or between these pairs, are of length zero, and
  63 the edge between the two nodes of such a pair has a length equal to
  64 the opposite of the detection score.
  65
  66 The file mtp.cc gives a very simple usage example of the Tracker
  67 class.
  68
  69 --
  70 François Fleuret
  71 August 2012