X-Git-Url: https://www.fleuret.org/cgi-bin/gitweb/gitweb.cgi?a=blobdiff_plain;f=README.txt;h=afc2388f86a2424ba86035f237129a094de599a0;hb=66479314c7f21ddc2f5e194ad6a25874b2bed909;hp=2ce7e3149d7a3e06b074258ef1b9b5e71f66f120;hpb=c7d5cdf1982dacc5451f79599041b2e95524d3f7;p=mtp.git diff --git a/README.txt b/README.txt index 2ce7e31..afc2388 100644 --- a/README.txt +++ b/README.txt @@ -13,13 +13,13 @@ in Pattern Analysis and Machine Intelligence (TPAMI), 33(9):1806-1819, 2011. -It works with negative edge lengths and stops computing new path when -it can not find one 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 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 @@ -31,12 +31,12 @@ If you now execute ./mtp 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 @@ -44,53 +44,55 @@ graphviz: 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 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 (a Boolean flag for each pair of locations from/to) - - the entrances (a Boolean flag for each location) + - the entrances (a Boolean flag for each location and time step) - - the exits (a Boolean flag for each location) + - the exits (a Boolean flag for each location and time step) - (2) to define a number of time steps + (2) 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. + (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, 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) +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 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 +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. 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. +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 @@ -99,31 +101,33 @@ 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 + ---------------------------- 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: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:force_empty_first_frame bool:force_empty_last_frame + bool:entrance_1_1 ... bool:entrance_1_L + ... + bool:entrance_T_1 ... bool:entrance_T_L -bool:is_an_entrance_1 ... bool:is_an_entrance_L + bool:exit_1_1 ... bool:exit_1_L + ... + bool:exit_T_1 ... bool:exit_T_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 ------------------------------- + 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 ----------------------------- snip snip ------------------------------- -int:traj_number int:entrance_time int:duration float:score int:location_1 ... int:location_duration ----------------------------- 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