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 execute
  14
  15   make
  16   ./mtp_example
  17
  18 It will create a synthetic dummy example, save its description in
  19 tracker.dat, and print the optimal detected trajectories.
  20
  21 If you now execute
  22
  23   ./mtp tracker.dat
  24
  25 It will load the tracker.dat example, run the detection, save the
  26 detected trajectories in result.trj, and the underlying graph with
  27 occupied edges in graph.dot. You can produce a pdf from the latter
  28 with the dot command from graphviz:
  29
  30   dot < graph.dot -T pdf -o graph.pdf
  31
  32 * IMPLEMENTATION
  33
  34 The two main classes are MTPGraph and Tracker.
  35
  36 The MTPGraph class stores a directed acyclic graph (DAG), with a
  37 length for each edge -- which can be negative -- and can compute the
  38 family of paths in this graph that minimizes the sum of edge lengths.
  39
  40 This means that it will iteratively add paths as long as it can find
  41 some with negative length. If there are no such path, it will compute
  42 no path at all. Note that the solution it finds is globally
  43 optimal. Note that the procedure is similar to that of KSP, in the
  44 sense that the family it computes eventually is globally optimal, even
  45 if the procedure is iterative.
  46
  47 The Tracker class allows
  48
  49  (1) to define a spatial topology composed of
  50
  51      - a number of locations
  52      - the allowed motions between them (i.e. a Boolean flag for each
  53        pair of locations)
  54      - the entrances (a Boolean flag for each location)
  55      - the exits (a Boolean flag for each location)
  56
  57  (2) to define a number of time steps
  58
  59  (3) to set for every location and time a detection score, which
  60  should be equal to log(P(Y = 1 | X)/P(Y = 0 | X)) where Y stands for
  61  the location occupancy and X for the observations.
  62
  63 From this setting, it computes the best set of disjoint trajectories
  64 consistent with the topology, which maximizes the overall detection
  65 score (i.e. the sum of the detection scores of the nodes visited by
  66 the trajectories)
  67
  68 The Tracker class uses the MTPGraph. From the definition of the
  69 spatial topology, it builds a graph with one source, one sink, and two
  70 nodes per location and time. This structure ensures the trajectories
  71 computed by the tracker to be node-disjoint by forcing the paths
  72 computed by the MTPGraph to be edge-disjoint. The edges from the
  73 source or to the sink, or between these pairs, are of length zero, and
  74 the edge between the two nodes of such a pair has a length equal to
  75 the opposite of the detection score.
  76
  77 The file mtp.cc gives a very simple usage example of the Tracker
  78 class.
  79
  80 --
  81 François Fleuret
  82 August 2012