From 2b42f849b86f2517e7e0fbaf498e307c1d48dd2a Mon Sep 17 00:00:00 2001 From: Francois Fleuret Date: Mon, 3 Sep 2012 08:52:14 +0200 Subject: [PATCH] Update. --- README.txt | 58 ++++++++++++++++++++++++++++++++---------------------- 1 file changed, 34 insertions(+), 24 deletions(-) diff --git a/README.txt b/README.txt index 53ef33f..742dde3 100644 --- a/README.txt +++ b/README.txt @@ -4,21 +4,22 @@ * INTRODUCTION -This is a very simple implementation of a variant of KSP applied to -multi-target, as described in +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. +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. * INSTALLATION -This source code should compile with any C++ compiler. Just execute +This software should compile with any C++ compiler. Just execute make ./mtp_example @@ -30,10 +31,12 @@ 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 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: dot < graph.dot -T pdf -o graph.pdf @@ -43,7 +46,8 @@ 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. +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 @@ -56,31 +60,37 @@ The MTPTracker class allows (1) to define 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 allowed motions between them (a Boolean flag for each pair + of locations from/to) + - the entrances (a Boolean flag for each location) + - the exits (a Boolean flag for each location) (2) to define 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. + should stand for log(P(Y = 1 | X)/P(Y = 0 | X)) where Y is for + the 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) -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 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 +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, 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 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. The file mtp_example.cc gives a very simple usage example of the MTPTracker class by setting the tracker parameters dynamically, and @@ -115,4 +125,4 @@ int:traj_number int:entrance_time int:duration float:score int:location_1 ... in -- François Fleuret -August 2012 +September 2012 -- 2.39.5