-This is a very simple implementation of the KSP applied to
-multi-target tracking. It is dubbed Multi-Tracked Paths since it
-differs a bit from the standard KSP. It works with negative edge
-length and stops when it can not find any path of negative length,
-instead of fixing the total number of paths to a constant K.
+* INTRODUCTION
-The two main classes are MTPGraph and Tracker.
+This is a very simple implementation of a variant of KSP applied to
+multi-target tracking dubbed "Multi-Tracked Paths" (MTP).
+
+It works with negative edge length and stops when it can not find any
+path of negative total length, instead of fixing the total number of
+paths to a constant K.
+
+* INSTALLATION
+
+This source code 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 example, 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
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 solution it finds is globally
-optimal. 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 procedure is iterative.
+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 Tracker class allows
+The MTPTracker class allows
(1) to define a spatial topology composed of
(2) to define a number of time steps
(3) to set for every location and time a detection score, which
- should be equal to log(P(Y = 1 | X)/P(Y = 0 | X)) where Y stands for
- the location occupancy and X for the observations.
+ should be equal to log(P(Y = 1 | X)/P(Y = 0 | X)) where Y stands
+ for the location occupancy and X for the 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 Tracker class uses the MTPGraph. From the definition of the
+The MTPTracker class uses the MTPGraph. From the definition of the
spatial topology, it builds a graph with one source, one sink, and two
nodes per location and time. This structure ensures the trajectories
computed by the tracker to be node-disjoint by forcing the paths
-computed by the MTPGraph to be edge-disjoint. The edges from the
-source or to the sink, or between these pairs, are of length zero, and
-the edge between the two nodes of such a pair has a length equal to
-the opposite of the detection score.
+computed by the MTPGraph to be edge-disjoint.
+
+The edges from the source or to the sink, or between these pairs, are
+of length zero, and the edge between the two nodes of such a pair has
+a length equal to the opposite of the detection score.
+
+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:is_an_entrance_1 ... bool:is_an_entrance_L
+
+bool:is_an_exit_1 ... bool:is_an_exit_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
-The file mtp.cc gives a very simple usage example of the Tracker
-class.
+---------------------------- snip snip -------------------------------
+int:traj_number int:entrance_time int:duration float:score int:location_1 ... int:location_duration
+---------------------------- snip snip -------------------------------
--
François Fleuret
projects / mtp.git / blobdiff