X-Git-Url: https://fleuret.org/cgi-bin/gitweb/gitweb.cgi?p=mtp.git;a=blobdiff_plain;f=README.txt;h=807f567f0803072d0e39a42bb3759dd6263ac360;hp=8c38d6844861d068e351322f54b48eb70eaf8a83;hb=22e800d663bb7a6b03ba6735fef54bf12c6cd2b5;hpb=f2f1701bfeb50ecb468489d58a59741400d1d791 diff --git a/README.txt b/README.txt index 8c38d68..807f567 100644 --- a/README.txt +++ b/README.txt @@ -1,33 +1,152 @@ -This is a very simple implementation of the KSP applied to -multi-target tracking. It is dubbed Multi-Tracked Path. -The two main classes are MTPGraph and Tracker. + Multi-Tracked Paths (MTP) + ------------------------- -MTPGraph allows to define a directed acyclic graph (DAG), to associate -a length to each of its edge (which can be negative), and to compute -the family of paths in this graph that minimize the sum of the length -of their edges. +* INTRODUCTION -Tracker allows +This is a very simple implementation of a variant of the k-shortest +paths algorithm (KSP) applied to multi-target tracking, as described +in - (1) to define a spatial topology composed of + 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. - - 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) +This implementation is not the reference implementation used for the +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. - (2) to define a number of time steps +This software package includes three commands: - (3) to set for every location and time a detection score + - 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. -From this input, 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) + - 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. -The file mtp.cc gives a very simple example. + - 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 + +This software should compile with any C++ compiler. Under a unix-like +environment, 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 --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 +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 MTPTracker. + +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. + +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 takes as input + + (1) a number of locations and a number of time steps + + (2) a spatial topology composed of + + - 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) + + (3) a detection score for every location and time, which stands for + + 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 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:entrance_1_1 ... bool:entrance_1_L + ... + bool:entrance_T_1 ... bool:entrance_T_L + + bool:exit_1_1 ... bool:exit_1_L + ... + bool:exit_T_1 ... bool:exit_T_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 + +---------------------------- 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 +January 2013