4 This is a very simple implementation of a variant of KSP applied to
5 multi-target tracking dubbed "Multi-Tracked Paths" (MTP).
7 It works with negative edge length and stops when it can not find any
8 path of negative total length, instead of fixing the total number of
13 This source code should compile with any C++ compiler. Just execute
18 It will create a synthetic dummy example, save its description in
19 tracker.dat, and print the optimal detected trajectories.
25 It will load the tracker.dat example, run the detection, save the
26 detected trajectories in result.trj, and the underlying graph with
27 occupied edges in graph.dot. You can produce a pdf from the latter
28 with the dot command from graphviz:
30 dot < graph.dot -T pdf -o graph.pdf
34 The two main classes are MTPGraph and Tracker.
36 The MTPGraph class stores a directed acyclic graph (DAG), with a
37 length for each edge -- which can be negative -- and can compute the
38 family of paths in this graph that minimizes the sum of edge lengths.
40 This means that it will iteratively add paths as long as it can find
41 some with negative length. If there are no such path, it will compute
42 no path at all. Note that the solution it finds is globally
43 optimal. Note that the procedure is similar to that of KSP, in the
44 sense that the family it computes eventually is globally optimal, even
45 if the procedure is iterative.
47 The Tracker class allows
49 (1) to define a spatial topology composed of
51 - a number of locations
52 - the allowed motions between them (i.e. a Boolean flag for each
54 - the entrances (a Boolean flag for each location)
55 - the exits (a Boolean flag for each location)
57 (2) to define a number of time steps
59 (3) to set for every location and time a detection score, which
60 should be equal to log(P(Y = 1 | X)/P(Y = 0 | X)) where Y stands for
61 the location occupancy and X for the observations.
63 From this setting, it computes the best set of disjoint trajectories
64 consistent with the topology, which maximizes the overall detection
65 score (i.e. the sum of the detection scores of the nodes visited by
68 The Tracker class uses the MTPGraph. From the definition of the
69 spatial topology, it builds a graph with one source, one sink, and two
70 nodes per location and time. This structure ensures the trajectories
71 computed by the tracker to be node-disjoint by forcing the paths
72 computed by the MTPGraph to be edge-disjoint. The edges from the
73 source or to the sink, or between these pairs, are of length zero, and
74 the edge between the two nodes of such a pair has a length equal to
75 the opposite of the detection score.
77 The file mtp.cc gives a very simple usage example of the Tracker