- Multi-Tracked Paths (MTP)
- -------------------------
+ Multi-Tracked Paths (MTP)
+ -------------------------
* INTRODUCTION
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
-This software should compile with any C++ compiler. Just execute
+This software should compile with any C++ compiler. Under a unix-like
+environment, just execute
make
./mtp_example
If you now execute
- ./mtp tracker.dat
+ ./mtp --verbose --trajectory-file result.trj --graph-file graph.dot 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
+It will load the file 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:
+If you do have the graphviz set of tools installed, you can produce a
+pdf from the latter with the dot command:
dot < graph.dot -T pdf -o graph.pdf
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.
+The MTPGraph class contains a directed acyclic graph (DAG), with a
+length for each edge -- which can be negative -- and has methods to
+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.
+If there are no path of negative length, this optimal family will be
+empty, since the minimum total length you can achieve is zero. 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 class allows
+The MTPTracker takes as input
- (1) to define 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 exits (a Boolean flag for each location and time step)
- (2) to define a number of time steps
-
- (3) to set 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 the 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
+ (3) a detection score for every location and time, which stands for
+
+ 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.
-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 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.
where L is the number of locations and T is the number of time steps:
---------------------------- snip snip -------------------------------
-int:L int:T
+ 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: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: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
+ 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
+ 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
structure
---------------------------- 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 -------------------------------
--
François Fleuret
-September 2012
+January 2013
projects / mtp.git / blobdiff