Changed the date.

[mtp.git] / README.txt

diff --git a/README.txt b/README.txt
index afc2388..807f567 100644 (file)
--- a/README.txt
+++ b/README.txt
@@ -1,6 +1,6 @@
 
 

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

 
 * INTRODUCTION
 
 
 * INTRODUCTION
 


@@ -14,7 +14,25 @@ in
   2011.
 
 This implementation is not the reference implementation used for the
   2011.
 
 This implementation is not the reference implementation used for the

-experiments presented in this article.
+experiments presented in this article. It does not require any
+library, and uses a Dijkstra with a Binary Heap for the min-queue,
+instead of a Fibonacci heap.
+
+This software package includes three commands:
+
+ - mtp is the generic command to use in practice. It takes tracking
+   parameters as input, and prints the tracked trajectories as
+   output. The format for these parameters is given at the bottom of
+   this documentation.
+
+ - mtp_example creates a tracking toy example, and runs the tracking
+   algorithm on it. It gives an example of how to use MTPTracker on a
+   configuration produced dynamically, and produces a test input file
+   for the mtp command.
+
+ - mtp_stress_test creates a larger problem with a lot of noise and
+   multiple trajectories, to check the behavior of the code under
+   slightly more complex situations.

 
 * INSTALLATION
 
 
 * INSTALLATION
 


@@ -29,7 +47,7 @@ tracker.dat, and print the optimal detected trajectories.
 
 If you now execute
 
 
 If you now execute
 

-  ./mtp tracker.dat
+  ./mtp --verbose --trajectory-file result.trj --graph-file graph.dot tracker.dat

 
 It will load the file tracker.dat saved by the previous command, run
 the detection, save the detected trajectories in result.trj, and the
 
 It will load the file tracker.dat saved by the previous command, run
 the detection, save the detected trajectories in result.trj, and the


@@ -55,11 +73,11 @@ 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.
 
 family it computes eventually is globally optimal, even if the
 computation is iterative.
 

-The MTPTracker is defined by
+The MTPTracker takes as input

 
 

- (1) a spatial topology composed of
+ (1) a number of locations and a number of time steps

 
 

-     - a number of locations
+ (2) a spatial topology composed of

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


@@ -68,32 +86,32 @@ The MTPTracker is defined by
 
      - the exits (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) a detection score for every location and time, which stands for
  (3) a detection score for every location and time, which stands for

-     log(P(Y = 1 | X)/P(Y = 0 | X)) where Y is the said location
-     occupancy and X the available observations.
-
-From this setting, MTPTracker has methods to compute 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). If no trajectory of total
-positive detection score exists, this optimal set of trajectories will
-be empty.

 
 

-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
+             log( P(Y(l,t) = 1 | X) / P(Y(l,t) = 0 | X) )
+
+     where Y is the occupancy of location l at time t and X is the
+     available observation. Hence, this score is negative on locations
+     where the probability that the location is occupied is close to
+     0, and positive when it is close to 1.
+
+From this parameters, the MTPTracker can compute the best set of
+disjoint trajectories consistent with the defined topology, which
+maximizes the overall detection score (i.e. the sum of the detection
+scores of the nodes visited by the trajectories). In particular, if no
+trajectory of total positive detection score exists, this optimal set
+of trajectories is empty.
+
+An MTPTracker is a wrapper around an MTPGraph. 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. 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. This structure ensures that the trajectories computed by the

 MTPTracker will be node-disjoint, since the trajectories computed by
 the MTPGraph are edge-disjoint.
 
 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 file mtp_example.cc gives a very simple usage example of the
 MTPTracker class by setting the tracker parameters dynamically, and
 running the tracking.


@@ -101,7 +119,7 @@ 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:
 
 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 -------------------------------
+---------------------------- snip snip -------------------------------

   int:L int:T
 
   bool:allowed_motion_from_1_to_1 ... bool:allowed_motion_from_1_to_L
   int:L int:T
 
   bool:allowed_motion_from_1_to_1 ... bool:allowed_motion_from_1_to_L


@@ -119,16 +137,16 @@ where L is the number of locations and T is the number of time steps:
   float:detection_score_1_1 ... float:detection_score_1_L
   ...
   float:detection_score_T_1 ... float:detection_score_T_L
   float:detection_score_1_1 ... float:detection_score_1_L
   ...
   float:detection_score_T_1 ... float:detection_score_T_L

-  ---------------------------- snip snip -------------------------------
+---------------------------- snip snip -------------------------------

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

-  ---------------------------- snip snip -------------------------------
+---------------------------- snip snip -------------------------------

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

-  ---------------------------- snip snip -------------------------------
+---------------------------- snip snip -------------------------------

 
 --
 François Fleuret
 
 --
 François Fleuret

-September 2012
+January 2013