From 535b8ede7d6646ea17135da10c8a16416524f6e9 Mon Sep 17 00:00:00 2001 From: Francois Fleuret Date: Thu, 23 Aug 2012 18:53:53 -0700 Subject: [PATCH] Simplifying + cosmetics. --- README.txt | 25 ++++++++++++++++---- graph.txt | 23 ------------------ graph2.txt | 23 ------------------ mtp.cc | 10 ++++---- tracker.cc | 68 +++++++++++++++++++----------------------------------- tracker.h | 14 ++++------- 6 files changed, 53 insertions(+), 110 deletions(-) delete mode 100644 graph.txt delete mode 100644 graph2.txt diff --git a/README.txt b/README.txt index 870e369..e814024 100644 --- a/README.txt +++ b/README.txt @@ -1,9 +1,24 @@ -This is a very simple implementation of the KSP applied to -multi-target tracking. It is dubbed Multi-Tracked Paths since it -differs a bit from the standard KSP. It works with negative edge -length and stops when it can not find any path of negative length, -instead of fixing the total number of paths to a constant K. +* INTRODUCTION + +This is a very simple implementation of a variant of KSP applied to +multi-target tracking dubbed "Multi-Tracked Paths" (MTP). + +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. + +* INSTALLATION + +This source code should compile with any C++ compiler. Just run "make" +and execute the mtp executable. It should print the optimal detected +trajectories, and save into graph.dot the result graph and +trajectories in the dot syntax. You can produce a pdf from the latter +with + + dot < graph.dot -T pdf -o graph.pdf + +* DESCRIPTION The two main classes are MTPGraph and Tracker. diff --git a/graph.txt b/graph.txt deleted file mode 100644 index 92a3142..0000000 --- a/graph.txt +++ /dev/null @@ -1,23 +0,0 @@ -11 20 -0 10 - - 0 1 -1.0 - 0 2 1.0 - 0 3 -1.0 - 1 4 -1.0 - 1 5 1.0 - 2 4 1.0 - 2 5 1.0 - 2 6 1.0 - 3 5 1.0 - 3 6 -1.0 - 4 7 -1.0 - 4 8 1.0 - 5 7 1.0 - 5 8 1.0 - 5 9 1.0 - 6 8 1.0 - 6 9 -1.0 - 7 10 -1.0 - 8 10 1.0 - 9 10 -1.0 diff --git a/graph2.txt b/graph2.txt deleted file mode 100644 index ac428e3..0000000 --- a/graph2.txt +++ /dev/null @@ -1,23 +0,0 @@ -11 20 -0 10 - - 0 1 -2.0 - 0 2 1.0 - 0 3 -2.0 - 1 4 -1.0 - 1 5 -2.0 - 2 4 1.0 - 2 5 1.0 - 2 6 1.0 - 3 5 1.0 - 3 6 -1.0 - 4 7 -1.0 - 4 8 1.0 - 5 7 1.0 - 5 8 1.0 - 5 9 -2.0 - 6 8 1.0 - 6 9 -1.0 - 7 10 -2.0 - 8 10 1.0 - 9 10 -2.0 diff --git a/mtp.cc b/mtp.cc index e07a738..979915b 100644 --- a/mtp.cc +++ b/mtp.cc @@ -44,10 +44,10 @@ int main(int argc, char **argv) { for(int l = 0; l < nb_locations; l++) { for(int k = 0; k < nb_locations; k++) { - tracker->set_allowed_motion(l, k, abs(l - k) <= motion_amplitude); + tracker->allowed_motion[l][k] = abs(l - k) <= motion_amplitude; } - tracker->set_as_entrance(0, 1); - tracker->set_as_exit(nb_locations - 1, 1); + tracker->entrances[0] = 1; + tracker->exits[nb_locations - 1] = 1; } tracker->build_graph(); @@ -57,9 +57,9 @@ int main(int argc, char **argv) { for(int t = 0; t < nb_time_steps; t++) { for(int l = 0; l < nb_locations; l++) { - tracker->set_detection_score(t, l, detection_score(-1, 0.95)); + tracker->detection_score[t][l] = detection_score(-1, 0.95); } - tracker->set_detection_score(t, nb_locations/2, detection_score(1, 0.95)); + tracker->detection_score[t][nb_locations/2] = detection_score(1, 0.95); } tracker->track(); diff --git a/tracker.cc b/tracker.cc index 0d1d781..f5dffd8 100644 --- a/tracker.cc +++ b/tracker.cc @@ -26,23 +26,23 @@ Tracker::Tracker(int nb_time_steps, int nb_locations) { _nb_locations = nb_locations; _nb_time_steps = nb_time_steps; - _detection_score = allocate_array(_nb_time_steps, _nb_locations); - _allowed_motion = allocate_array(_nb_locations, _nb_locations); + detection_score = allocate_array(_nb_time_steps, _nb_locations); + allowed_motion = allocate_array(_nb_locations, _nb_locations); - _entrances = new int[_nb_locations]; - _exits = new int[_nb_locations]; + entrances = new int[_nb_locations]; + exits = new int[_nb_locations]; for(int l = 0; l < nb_locations; l++) { - _entrances[l] = 0; - _exits[l] = 0; + entrances[l] = 0; + exits[l] = 0; for(int m = 0; m < nb_locations; m++) { - _allowed_motion[l][m] = 0; + allowed_motion[l][m] = 0; } } for(int t = 0; t < _nb_time_steps; t++) { for(int l = 0; l < _nb_locations; l++) { - _detection_score[t][l] = 0.0; + detection_score[t][l] = 0.0; } } @@ -53,32 +53,10 @@ Tracker::Tracker(int nb_time_steps, int nb_locations) { Tracker::~Tracker() { delete[] _edge_lengths; delete _graph; - deallocate_array(_detection_score); - deallocate_array(_allowed_motion); - delete[] _exits; - delete[] _entrances; -} - -void Tracker::set_allowed_motion(int from_location, int to_location, int v) { - ASSERT(from_location >= 0 && from_location < _nb_locations && - to_location >= 0 && to_location < _nb_locations); - _allowed_motion[from_location][to_location] = v; -} - -void Tracker::set_as_entrance(int location, int v) { - ASSERT(location >= 0 && location < _nb_locations); - _entrances[location] = v; -} - -void Tracker::set_as_exit(int location, int v) { - ASSERT(location >= 0 && location < _nb_locations); - _exits[location] = v; -} - -void Tracker::set_detection_score(int time, int location, scalar_t score) { - ASSERT(time >= 0 && time < _nb_time_steps && - location >= 0 && location < _nb_locations); - _detection_score[time][location] = score; + deallocate_array(detection_score); + deallocate_array(allowed_motion); + delete[] exits; + delete[] entrances; } void Tracker::build_graph() { @@ -89,10 +67,10 @@ void Tracker::build_graph() { int nb_motions = 0, nb_exits = 0, nb_entrances = 0; for(int l = 0; l < _nb_locations; l++) { - if(_exits[l]) nb_exits++; - if(_entrances[l]) nb_entrances++; + if(exits[l]) nb_exits++; + if(entrances[l]) nb_entrances++; for(int m = 0; m < _nb_locations; m++) { - if(_allowed_motion[l][m]) nb_motions++; + if(allowed_motion[l][m]) nb_motions++; } } @@ -103,7 +81,8 @@ void Tracker::build_graph() { // frame to the sink _nb_locations * 2 + // The edges from the source to the entrances and from the exists - // to the sink (in every time frames but the first and last) + // to the sink (in every time frames but the first for the source, + // and last for the exits) (_nb_time_steps - 1) * (nb_exits + nb_entrances) + // The edges for the motions, between every pair of successive // frames @@ -120,7 +99,8 @@ void Tracker::build_graph() { _edge_lengths = new scalar_t[nb_edges]; // We put the in-node edges first, since these are the ones whose - // lengths we will have to change according to the detection score + // lengths we will have to set later, according to the detection + // scores for(int t = 0; t < _nb_time_steps; t++) { for(int l = 0; l < _nb_locations; l++) { @@ -146,7 +126,7 @@ void Tracker::build_graph() { e++; } else { for(int k = 0; k < _nb_locations; k++) { - if(_allowed_motion[l][k]) { + if(allowed_motion[l][k]) { node_from[e] = 1 + (2 * (t + 0) + 1) * _nb_locations + l; node_to[e] = 1 + (2 * (t + 1) + 0) * _nb_locations + k; _edge_lengths[e] = 0.0; @@ -159,13 +139,13 @@ void Tracker::build_graph() { for(int t = 0; t < _nb_time_steps; t++) { for(int l = 0; l < _nb_locations; l++) { - if(t > 0 && _entrances[l]) { + if(t > 0 && entrances[l]) { node_from[e] = source; node_to[e] = 1 + (2 * (t + 0) + 0) * _nb_locations + l; _edge_lengths[e] = 0.0; e++; } - if(t < _nb_time_steps - 1 && _exits[l]) { + if(t < _nb_time_steps - 1 && exits[l]) { node_from[e] = 1 + (2 * (t + 0) + 1) * _nb_locations + l; node_to[e] = sink; _edge_lengths[e] = 0.0; @@ -186,7 +166,7 @@ void Tracker::print_graph_dot(ostream *os) { int e = 0; for(int t = 0; t < _nb_time_steps; t++) { for(int l = 0; l < _nb_locations; l++) { - _edge_lengths[e++] = - _detection_score[t][l]; + _edge_lengths[e++] = - detection_score[t][l]; } } _graph->print_dot(os); @@ -196,7 +176,7 @@ void Tracker::track() { int e = 0; for(int t = 0; t < _nb_time_steps; t++) { for(int l = 0; l < _nb_locations; l++) { - _edge_lengths[e++] = - _detection_score[t][l]; + _edge_lengths[e++] = - detection_score[t][l]; } } diff --git a/tracker.h b/tracker.h index de6931d..de6ac42 100644 --- a/tracker.h +++ b/tracker.h @@ -35,24 +35,18 @@ class Tracker { MTPGraph *_graph; scalar_t *_edge_lengths; public: + scalar_t **detection_score; + int **allowed_motion; + int *entrances, *exits; + Tracker(int nb_time_steps, int nb_locations); ~Tracker(); - // Define the spatial topology - - void set_allowed_motion(int from_location, int to_location, int v); - void set_as_entrance(int location, int v); - void set_as_exit(int location, int v); - // Build or print the graph needed for the tracking per se void build_graph(); void print_graph_dot(ostream *os); - // Define the detection scores - - void set_detection_score(int time, int location, scalar_t score); - // Compute the optimal set of trajectories void track(); -- 2.39.5