+ Multi-Tracked Paths (MTP)
+ -------------------------
+
* INTRODUCTION
-This is a very simple implementation of a variant of KSP applied to
-multi-target tracking dubbed "Multi-Tracked Paths" (MTP).
+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.
-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.
+This implementation is not the reference implementation used for the
+experiments presented in this article.
* INSTALLATION
-This source code 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
./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:
+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.
+
+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 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 is defined by
- (1) to define a spatial topology composed of
+ (1) a spatial topology composed of
- a number of locations
- - the allowed motions between them (i.e. a Boolean flag for each
- pair of locations)
- - the entrances (a Boolean flag for each location)
- - the exits (a Boolean flag for each location)
- (2) to define a number of time steps
+ - 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) 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.
- (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.
+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.
-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 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 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 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 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 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 file mtp.cc gives a very simple usage example of the MTPTracker
-class.
+ ---------------------------- snip snip -------------------------------
+ int:L int:T
-The tracker data file one can read with MTPTracker::read has the
-following format (with L the number of locations and T the number of
-time steps):
+ 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
----------------------------- snip snip -------------------------------
-L T
+ bool:entrance_1_1 ... bool:entrance_1_L
+ ...
+ bool:entrance_T_1 ... bool:entrance_T_L
-allowed_motion_from_1_to_1 ... allowed_motion_from_1_to_L
-...
-allowed_motion_from_L_to_1 ... allowed_motion_from_L_to_L
+ bool:exit_1_1 ... bool:exit_1_L
+ ...
+ bool:exit_T_1 ... bool:exit_T_L
-is_an_entrance_1 ... is_an_entrance_L
+ float:detection_score_1_1 ... float:detection_score_1_L
+ ...
+ float:detection_score_T_1 ... float:detection_score_T_L
+ ---------------------------- snip snip -------------------------------
-is_an_exit_1 ... is_an_exit_L
+The method MTPTracker::write_trajectories writes first the number of
+trajectories, followed by one line per trajectory with the following
+structure
-detection_score_1_1 ... detection_score_1_L
-...
-detection_score_T_1 ... detection_score_T_L
----------------------------- snip snip -------------------------------
+ ---------------------------- snip snip -------------------------------
+ int:traj_number int:entrance_time int:duration float:score int:location_1 ... int:location_duration
+ ---------------------------- snip snip -------------------------------
--
François Fleuret
-August 2012
+September 2012
projects / mtp.git / blobdiff