X-Git-Url: https://fleuret.org/cgi-bin/gitweb/gitweb.cgi?p=mtp.git;a=blobdiff_plain;f=README.txt;h=a20e23d50b30aec77c682079bcc7f39472fff5d7;hp=eb8a26f5ab481d90a49fd618849cfce4a02479ef;hb=14e3b33cbe1e0d7deb0b4aa697f6c8b5d43e2963;hpb=53da5d9421597dfc056b5727dbe7898afd30bdc9 diff --git a/README.txt b/README.txt index eb8a26f..a20e23d 100644 --- a/README.txt +++ b/README.txt @@ -1,16 +1,26 @@ + 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. It uses a Dijkstra with a +Binary Heap for the min-queue, and not the optimal Fibonacci heap. * 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 @@ -22,81 +32,104 @@ 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: +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 * IMPLEMENTATION -The two main classes are MTPGraph and Tracker. +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 Tracker 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) 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. + (3) a detection score for every location and time, which stands for -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) + log( P(Y(l,t) = 1 | X) / P(Y(l,t) = 0 | X) ) -The Tracker 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. + where Y is the occupancy of location l at time t and X is the + available observation. -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. +From this setting, MTPTracker has methods to 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). If no trajectory of +total positive detection score exists, this optimal set of +trajectories will be empty. -The file mtp.cc gives a very simple usage example of the Tracker -class. +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. 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 also ensures that the trajectories +computed by the MTPTracker will be node-disjoint, since the +trajectories computed by the MTPGraph are edge-disjoint. -The tracker data file one can read with Tracker::read has the -following format (with L the number of locations and T the number of -time steps): +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 ------------------------------- -L 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 -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:entrance_1_1 ... bool:entrance_1_L + ... + bool:entrance_T_1 ... bool:entrance_T_L -is_an_entrance_1 ... is_an_entrance_L + bool:exit_1_1 ... bool:exit_1_L + ... + bool:exit_T_1 ... bool:exit_T_L -is_an_exit_1 ... 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 ------------------------------- -detection_score_1_1 ... detection_score_1_L -... -detection_score_T_1 ... detection_score_T_L +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 -August 2012 +December 2012