Multi-Tracked Paths (MTP)
                     -------------------------

* INTRODUCTION

This is a very simple implementation of a variant of the k-shortest
paths algorithm (KSP) applied to multi-target tracking, as described
in

  J. Berclaz, E. Turetken, F. Fleuret, and P. Fua. Multiple Object
  Tracking using K-Shortest Paths Optimization. IEEE Transactions on
  Pattern Analysis and Machine Intelligence (TPAMI), 33(9):1806-1819,
  2011.

This implementation is not the reference implementation used for the
experiments presented in this article.

* INSTALLATION

This software should compile with any C++ compiler. Just execute

  make
  ./mtp_example

It will create a synthetic dummy example, save its description in
tracker.dat, and print the optimal detected trajectories.

If you now execute

  ./mtp tracker.dat

It will load the tracker.dat saved by the previous command, run the
detection, save the detected trajectories in result.trj, and the
underlying graph with occupied edges in graph.dot.

You can produce a pdf from the latter with the dot command from
graphviz:

  dot < graph.dot -T pdf -o graph.pdf

* IMPLEMENTATION

The two main classes are MTPGraph and MTPTracker.

The MTPGraph class stores a directed acyclic graph (DAG), with a
length for each edge -- which can be negative -- and can compute the
family of paths in this graph that globally minimizes the sum of edge
lengths.

This means that it will iteratively add paths as long as it can find
some with negative length. If there are no such path, it will compute
no path at all. Note that the procedure is similar to that of KSP, in
the sense that the family it computes eventually is globally optimal,
even if the computation is iterative.

The MTPTracker is defined by

 (1) a spatial topology composed of

     - a number of locations

     - the allowed motions between them (a Boolean flag for each pair
       of locations from/to)

     - the entrances (a Boolean flag for each location and time step)

     - the exits (a Boolean flag for each location and time step)

 (2) a number of time steps

 (3) for every location and time a detection score, which should stand
     for log(P(Y = 1 | X)/P(Y = 0 | X)) where Y is for the location
     occupancy and X the available observations.

From this setting, it computes the best set of disjoint trajectories
consistent with the topology, which maximizes the overall detection
score (i.e. the sum of the detection scores of the nodes visited by
the trajectories)

The MTPTracker is a wrapper around the MTPGraph class.

From the defined spatial topology and number of time steps, it builds
a graph with one source, one sink, and two nodes per location and
time. This structure ensures that the trajectories computed by the
MTPTracker will be node-disjoint, since the trajectories computed by
the MTPGraph are edge-disjoint.

The edges from the source or to the sink, or between these pairs of
nodes, are of length zero, and the edges between the two nodes of such
a pair have negative lengths, equal to the opposite of the
corresponding detection scores.

The file mtp_example.cc gives a very simple usage example of the
MTPTracker class by setting the tracker parameters dynamically, and
running the tracking.

The tracker data file for MTPTracker::read has the following format,
where L is the number of locations and T is the number of time steps:

  ---------------------------- snip snip -------------------------------
  int:L int:T

  bool:allowed_motion_from_1_to_1 ... bool:allowed_motion_from_1_to_L
  ...
  bool:allowed_motion_from_L_to_1 ... bool:allowed_motion_from_L_to_L

  bool:entrance_1_1 ... bool:entrance_1_L
  ...
  bool:entrance_T_1 ... bool:entrance_T_L

  bool:exit_1_1 ... bool:exit_1_L
  ...
  bool:exit_T_1 ... bool:exit_T_L

  float:detection_score_1_1 ... float:detection_score_1_L
  ...
  float:detection_score_T_1 ... float:detection_score_T_L
  ---------------------------- snip snip -------------------------------

The method MTPTracker::write_trajectories writes first the number of
trajectories, followed by one line per trajectory with the following
structure

  ---------------------------- snip snip -------------------------------
  int:traj_number int:entrance_time int:duration float:score int:location_1 ... int:location_duration
  ---------------------------- snip snip -------------------------------

--
François Fleuret
September 2012