From 15ad4100d5f4d7e3e15ea807c9bef8002fa9c177 Mon Sep 17 00:00:00 2001 From: Francois Fleuret Date: Thu, 23 Aug 2012 17:27:02 -0700 Subject: [PATCH] Update. --- README.txt | 33 ++++++++++++++++++++++++++------- 1 file changed, 26 insertions(+), 7 deletions(-) diff --git a/README.txt b/README.txt index 8c38d68..5975edf 100644 --- a/README.txt +++ b/README.txt @@ -1,14 +1,22 @@ + This is a very simple implementation of the KSP applied to -multi-target tracking. It is dubbed Multi-Tracked Path. +multi-target tracking. It is dubbed Multi-Tracked Path since it +differs a bit from the standard KSP. It works with negative edge +length and stops when it can not find path of negative length anymore +instead of fixing the total number of paths to a constant. The two main classes are MTPGraph and Tracker. -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. +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. + +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 solution it finds is globally optimal. -Tracker allows +The Tracker class allows (1) to define a spatial topology composed of @@ -27,7 +35,18 @@ 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 file mtp.cc gives a very simple example. +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. 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 file mtp.cc gives a very simple usage example of the Tracker +class. +-- François Fleuret August 2012 -- 2.39.5