Solve restricted class of Markov problems (trees and tri-trees). More...
#include <mmn_dp_solver.h>
Public Member Functions | |
| mmn_dp_solver () | |
| Default constructor. | |
| unsigned | root () const |
| Index of root node. | |
| virtual void | set_arcs (unsigned num_nodes, const vcl_vector< mmn_arc > &arcs) |
| Input the arcs that define the graph. | |
| void | set_dependancies (const vcl_vector< mmn_dependancy > &deps, unsigned n_nodes, unsigned max_n_arcs) |
| Define dependencies. | |
| const vcl_vector < mmn_dependancy > & | deps () const |
| Read access to dependencies. | |
| virtual 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. | |
| virtual bool | set_from_stream (vcl_istream &is) |
| Initialise from a text stream. | |
| short | version_no () const |
| Version number for I/O. | |
| virtual vcl_string | is_a () const |
| Name of the class. | |
| virtual mmn_solver * | clone () const |
| Create a copy on the heap and return base class pointer. | |
| virtual void | print_summary (vcl_ostream &os) const |
| Print class to os. | |
| virtual void | b_write (vsl_b_ostream &bfs) const |
| Save class to binary file stream. | |
| virtual void | b_read (vsl_b_istream &bfs) |
| Load class from binary file stream. | |
Static Public Member Functions | |
| static vcl_auto_ptr< mmn_solver > | create_from_stream (vcl_istream &is) |
| Create a concrete region_model-derived object, from a text specification. | |
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. | |
Detailed Description
Solve restricted class of Markov problems (trees and tri-trees).
Find choice of values at each node which minimises Markov problem. 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 25 of file mmn_dp_solver.h.
Constructor & Destructor Documentation
| mmn_dp_solver::mmn_dp_solver | ( | ) |
Default constructor.
Definition at line 17 of file mmn_dp_solver.cxx.
Member Function Documentation
| void mmn_dp_solver::b_read | ( | vsl_b_istream & | bfs | ) | [virtual] |
Load class from binary file stream.
Implements mmn_solver.
Definition at line 416 of file mmn_dp_solver.cxx.
| void mmn_dp_solver::b_write | ( | vsl_b_ostream & | bfs | ) | const [virtual] |
Save class to binary file stream.
Implements mmn_solver.
Definition at line 404 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 328 of file mmn_dp_solver.cxx.
| mmn_solver * mmn_dp_solver::clone | ( | ) | const [virtual] |
Create a copy on the heap and return base class pointer.
Implements mmn_solver.
Definition at line 387 of file mmn_dp_solver.cxx.
| vcl_auto_ptr< mmn_solver > mmn_solver::create_from_stream | ( | vcl_istream & | is | ) | [static, inherited] |
Create a concrete region_model-derived object, from a text specification.
Definition at line 76 of file mmn_solver.cxx.
| const vcl_vector<mmn_dependancy>& mmn_dp_solver::deps | ( | ) | const [inline] |
Read access to dependencies.
Definition at line 75 of file mmn_dp_solver.h.
| vcl_string mmn_dp_solver::is_a | ( | ) | const [virtual] |
| void mmn_dp_solver::print_summary | ( | vcl_ostream & | os | ) | const [virtual] |
| 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 69 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 125 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 184 of file mmn_dp_solver.cxx.
| unsigned mmn_dp_solver::root | ( | ) | const |
Index of root node.
Definition at line 52 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 106 of file mmn_dp_solver.h.
| void mmn_dp_solver::set_arcs | ( | unsigned | num_nodes, |
| const vcl_vector< mmn_arc > & | arcs | ||
| ) | [virtual] |
Input the arcs that define the graph.
Implements mmn_solver.
Definition at line 22 of file mmn_dp_solver.cxx.
| void mmn_dp_solver::set_dependancies | ( | const vcl_vector< mmn_dependancy > & | deps, |
| unsigned | n_nodes, | ||
| unsigned | max_n_arcs | ||
| ) |
Define dependencies.
Definition at line 59 of file mmn_dp_solver.cxx.
| bool mmn_dp_solver::set_from_stream | ( | vcl_istream & | is | ) | [virtual] |
Initialise from a text stream.
Initialise from a string stream.
Reimplemented from mmn_solver.
Definition at line 352 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, | ||
| vcl_vector< unsigned > & | x | ||
| ) | [virtual] |
Find values for each node with minimise the total cost.
- Parameters:
-
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
Implements mmn_solver.
Definition at line 249 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 282 of file mmn_dp_solver.cxx.
| short mmn_dp_solver::version_no | ( | ) | const |
Version number for I/O.
Reimplemented from mmn_solver.
Definition at line 372 of file mmn_dp_solver.cxx.
Member Data Documentation
vcl_vector<mmn_dependancy> mmn_dp_solver::deps_ [private] |
Dependencies.
Definition at line 41 of file mmn_dp_solver.h.
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 35 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 38 of file mmn_dp_solver.h.
vcl_vector<vnl_vector<double> > mmn_dp_solver::nc_ [private] |
Workspace for incremental costs of each node.
Definition at line 29 of file mmn_dp_solver.h.
vcl_vector<vnl_matrix<double> > mmn_dp_solver::pc_ [private] |
Workspace for incremental costs of each arc.
Definition at line 32 of file mmn_dp_solver.h.
The documentation for this class was generated from the following files:
- contrib/mul/mmn/mmn_dp_solver.h
- contrib/mul/mmn/mmn_dp_solver.cxx
