X-Git-Url: https://fleuret.org/cgi-bin/gitweb/gitweb.cgi?p=mtp.git;a=blobdiff_plain;f=README.txt;h=807f567f0803072d0e39a42bb3759dd6263ac360;hp=afc2388f86a2424ba86035f237129a094de599a0;hb=22e800d663bb7a6b03ba6735fef54bf12c6cd2b5;hpb=66479314c7f21ddc2f5e194ad6a25874b2bed909 diff --git a/README.txt b/README.txt index afc2388..807f567 100644 --- a/README.txt +++ b/README.txt @@ -1,6 +1,6 @@ - Multi-Tracked Paths (MTP) - ------------------------- + Multi-Tracked Paths (MTP) + ------------------------- * INTRODUCTION @@ -14,7 +14,25 @@ in 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 @@ -29,7 +47,7 @@ tracker.dat, and print the optimal detected trajectories. If you now execute - ./mtp tracker.dat + ./mtp --verbose --trajectory-file result.trj --graph-file graph.dot tracker.dat It will load the file tracker.dat saved by the previous command, run the detection, save the detected trajectories in result.trj, and the @@ -55,11 +73,11 @@ 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 is defined by +The MTPTracker takes as input - (1) 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) @@ -68,32 +86,32 @@ The MTPTracker is defined by - 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. - -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 + 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 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 running the tracking. @@ -101,7 +119,7 @@ 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 ------------------------------- +---------------------------- snip snip ------------------------------- int:L int:T bool:allowed_motion_from_1_to_1 ... bool:allowed_motion_from_1_to_L @@ -119,16 +137,16 @@ where L is the number of locations and T is the number of time steps: float:detection_score_1_1 ... float:detection_score_1_L ... float:detection_score_T_1 ... float:detection_score_T_L - ---------------------------- snip snip ------------------------------- +---------------------------- 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 ------------------------------- +---------------------------- snip snip ------------------------------- int:traj_number int:entrance_time int:duration float:score int:location_1 ... int:location_duration - ---------------------------- snip snip ------------------------------- +---------------------------- snip snip ------------------------------- -- François Fleuret -September 2012 +January 2013