#include <mmn_dp_solver.h>
Minimises F() = sum node_costs + sum pair_costs
Assumes graph defining relationships can be fully decomposed by repeatedly removing any nodes with two or fewer neighbours. Global optimum is found using a series of sequential exhaustive optimisations.
Definition at line 22 of file mmn_dp_solver.h.
Public Member Functions | |
| mmn_dp_solver () | |
| Default constructor. | |
| unsigned | root () const |
| Index of root node. | |
| void | set_dependancies (const vcl_vector< mmn_dependancy > &deps, unsigned n_nodes, unsigned max_n_arcs) |
| Define dependencies. | |
| double | solve (const vcl_vector< vnl_vector< double > > &node_cost, const vcl_vector< vnl_matrix< double > > &pair_cost, vcl_vector< unsigned > &x) |
| Find values for each node with minimise the total cost. | |
| double | solve (const vcl_vector< vnl_vector< double > > &node_cost, const vcl_vector< vnl_matrix< double > > &pair_cost, const vcl_vector< vil_image_view< double > > &tri_cost, vcl_vector< unsigned > &x) |
| Find values for each node with minimise the total cost. | |
| void | backtrace (unsigned root_value, vcl_vector< unsigned > &x) |
| Compute optimal values for x[i] given that root node is root_value. | |
| const vnl_vector< double > & | root_cost () const |
| root_cost()[i] is cost of selecting value i for the root node. | |
Private Member Functions | |
| void | process_dep1 (const mmn_dependancy &dep) |
| Compute optimal choice for node dep.v0 for each possible v1. | |
| void | process_dep2 (const mmn_dependancy &dep) |
| Compute optimal choice for dep.v0 given v1 and v2. | |
| void | process_dep2t (const mmn_dependancy &dep, const vil_image_view< double > &tri_cost) |
| Compute optimal choice for dep.v0 given v1 and v2. | |
Private Attributes | |
| vcl_vector< vnl_vector< double > > | nc_ |
| Workspace for incremental costs of each node. | |
| vcl_vector< vnl_matrix< double > > | pc_ |
| Workspace for incremental costs of each arc. | |
| vcl_vector< vcl_vector< unsigned > > | index1_ |
| index1[i][j] = optimal choice for i if other node is j. | |
| vcl_vector< vnl_matrix< int > > | index2_ |
| index2[i](j,k) = optimal choice of i if two other nodes are (j,k). | |
| vcl_vector< mmn_dependancy > | deps_ |
| Dependencies. | |
| mmn_dp_solver::mmn_dp_solver | ( | ) |
| void mmn_dp_solver::process_dep1 | ( | const mmn_dependancy & | dep | ) | [private] |
Compute optimal choice for node dep.v0 for each possible v1.
Uses pair costs for v0-v1 (in pc_) and the node cost nc_(v0)
Definition at line 33 of file mmn_dp_solver.cxx.
| void mmn_dp_solver::process_dep2 | ( | const mmn_dependancy & | dep | ) | [private] |
Compute optimal choice for dep.v0 given v1 and v2.
Uses only pairwise and node costs (in nc_ and pc_)
Definition at line 82 of file mmn_dp_solver.cxx.
| void mmn_dp_solver::process_dep2t | ( | const mmn_dependancy & | dep, | |
| const vil_image_view< double > & | tri_cost | |||
| ) | [private] |
Compute optimal choice for dep.v0 given v1 and v2.
Includes cost depending on (v0,v1,v2) as well as pairwise and node costs. tri_cost(i,j,k) is cost of associating smallest node index with i, next with j and largest node index with k.
Definition at line 142 of file mmn_dp_solver.cxx.
| unsigned mmn_dp_solver::root | ( | ) | const |
| void mmn_dp_solver::set_dependancies | ( | const vcl_vector< mmn_dependancy > & | deps, | |
| unsigned | n_nodes, | |||
| unsigned | max_n_arcs | |||
| ) |
| double mmn_dp_solver::solve | ( | const vcl_vector< vnl_vector< double > > & | node_cost, | |
| const vcl_vector< vnl_matrix< double > > & | pair_cost, | |||
| vcl_vector< unsigned > & | x | |||
| ) |
Find values for each node with minimise the total cost.
| node_cost,: | node_cost[i][j] is cost of selecting value j for node i | |
| pair_cost,: | pair_cost[a](i,j) is cost of selecting values (i,j) for nodes at end of arc a. | |
| x,: | On exit, x[i] gives choice for node i NOTE: If arc a connects nodes v1,v2, the associated pair_cost is ordered with the node with the lowest index being the first parameter. Thus if v1 has value i1, v2 has value i2, then the cost of this choice is (v1<v2?pair_cost(i1,i2):pair_cost(i2,i1)) Returns the minimum cost |
Definition at line 207 of file mmn_dp_solver.cxx.
| double mmn_dp_solver::solve | ( | const vcl_vector< vnl_vector< double > > & | node_cost, | |
| const vcl_vector< vnl_matrix< double > > & | pair_cost, | |||
| const vcl_vector< vil_image_view< double > > & | tri_cost, | |||
| vcl_vector< unsigned > & | x | |||
| ) |
Find values for each node with minimise the total cost.
As solve(node_cost,pair_cost,x), but allows inclusion of costs for triplets (ie when v0 depends on v1 and v2). tri_cost(i,j,k) gives cost of node min(v0,v1,v2) being value i, node mid(v0,v1,v2) being value j and node max(v0,v1,v2) being value k.
Definition at line 240 of file mmn_dp_solver.cxx.
| void mmn_dp_solver::backtrace | ( | unsigned | root_value, | |
| vcl_vector< unsigned > & | x | |||
| ) |
Compute optimal values for x[i] given that root node is root_value.
Assumes that solve() has been already called.
Definition at line 286 of file mmn_dp_solver.cxx.
| const vnl_vector<double>& mmn_dp_solver::root_cost | ( | ) | const [inline] |
root_cost()[i] is cost of selecting value i for the root node.
Definition at line 96 of file mmn_dp_solver.h.
vcl_vector<vnl_vector<double> > mmn_dp_solver::nc_ [private] |
vcl_vector<vnl_matrix<double> > mmn_dp_solver::pc_ [private] |
vcl_vector<vcl_vector<unsigned> > mmn_dp_solver::index1_ [private] |
index1[i][j] = optimal choice for i if other node is j.
Definition at line 32 of file mmn_dp_solver.h.
vcl_vector<vnl_matrix<int> > mmn_dp_solver::index2_ [private] |
index2[i](j,k) = optimal choice of i if two other nodes are (j,k).
Definition at line 35 of file mmn_dp_solver.h.
vcl_vector<mmn_dependancy> mmn_dp_solver::deps_ [private] |
1.5.1