|
OpenGM
2.3.x
Discrete Graphical Model Library
|
A star search algorithm. More...
#include <astar.hxx>
Inheritance diagram for opengm::AStar< GM, ACC >: Collaboration diagram for opengm::AStar< GM, ACC >:Classes | |
| struct | Parameter |
Public Types | |
| enum | Heuristic { DEFAULT_HEURISTIC = 0, FAST_HEURISTIC = 1, STANDARD_HEURISTIC = 2 } |
| typedef GM | GraphicalModelType |
| graphical model type More... | |
| typedef ACC | AccumulationType |
| accumulation type More... | |
| typedef std::vector< LabelType > | ConfVec |
| configuration vector type More... | |
| typedef ConfVec::iterator | ConfVecIt |
| configuration iterator More... | |
| typedef opengm::visitors::VerboseVisitor< AStar< GM, ACC > > | VerboseVisitorType |
| visitor More... | |
| typedef opengm::visitors::TimingVisitor< AStar< GM, ACC > > | TimingVisitorType |
| typedef opengm::visitors::EmptyVisitor< AStar< GM, ACC > > | EmptyVisitorType |
| Public Types inherited from opengm::Inference< GM, ACC > | |
| typedef GM | GraphicalModelType |
| typedef ACC | AccumulationType |
| typedef GraphicalModelType::LabelType | LabelType |
| typedef GraphicalModelType::IndexType | IndexType |
| typedef GraphicalModelType::ValueType | ValueType |
| typedef GraphicalModelType::OperatorType | OperatorType |
| typedef GraphicalModelType::FactorType | FactorType |
| typedef GraphicalModelType::IndependentFactorType | IndependentFactorType |
| typedef GraphicalModelType::FunctionIdentifier | FunctionIdentifier |
Public Member Functions | |
| AStar (const GM &gm, Parameter para=Parameter()) | |
| constructor More... | |
| virtual std::string | name () const |
| const GraphicalModelType & | graphicalModel () const |
| virtual InferenceTermination | infer () |
| virtual void | reset () |
| reset More... | |
| template<class VisitorType > | |
| InferenceTermination | infer (VisitorType &vistitor) |
| inference with visitor More... | |
| ValueType | bound () const |
| return a bound on the solution More... | |
| ValueType | value () const |
| return the solution (value) More... | |
| virtual InferenceTermination | marginal (const size_t, IndependentFactorType &out) const |
| output a solution for a marginal for a specific variable More... | |
| virtual InferenceTermination | factorMarginal (const size_t, IndependentFactorType &out) const |
| output a solution for a marginal for all variables connected to a factor More... | |
| virtual InferenceTermination | arg (std::vector< LabelType > &v, const size_t=1) const |
| output a solution More... | |
| virtual InferenceTermination | args (std::vector< std::vector< LabelType > > &v) const |
| args More... | |
| Public Member Functions inherited from opengm::Inference< GM, ACC > | |
| virtual | ~Inference () |
| virtual void | setStartingPoint (typename std::vector< LabelType >::const_iterator) |
| set initial labeling More... | |
| InferenceTermination | constrainedOptimum (std::vector< IndexType > &, std::vector< LabelType > &, std::vector< LabelType > &) const |
| InferenceTermination | modeFromMarginal (std::vector< LabelType > &) const |
| InferenceTermination | modeFromFactorMarginal (std::vector< LabelType > &) const |
Public Attributes | |
| OPENGM_GM_TYPE_TYPEDEFS | |
A star search algorithm.
Kappes, J. H. "Inference on Highly-Connected Discrete Graphical Models with Applications to Visual Object Recognition". Ph.D. Thesis 2011 Bergtholdt, M. & Kappes, J. H. & Schnoerr, C.: "Learning of Graphical Models and Efficient Inference for Object Class Recognition", DAGM 2006 Bergtholdt, M. & Kappes, J. H. & Schmidt, S. & Schnoerr, C.: "A Study of Parts-Based Object Class Detection Using Complete Graphs" IJCV 2010
Within this implementation of the AStar-Algo the user has to set the the node order and a acyclic graph for the calculation of the heuristic. A good choice for both is critical for good performance! A heuristic which select these parameters automatically will be added in the next version
The AStar-Algo transform the problem into a shortest path problem in an exponentially large graph. Due to the problem structure, this graph can be represented implicitly! To find the shortest path we perform a best first search and use a admissable tree-based heuristic to underestimate the cost to a goal node. This lower bound allows us to reduce the search to an manageable subspace of the exponentially large search-space.
| typedef ACC opengm::AStar< GM, ACC >::AccumulationType |
| typedef std::vector<LabelType> opengm::AStar< GM, ACC >::ConfVec |
| typedef ConfVec::iterator opengm::AStar< GM, ACC >::ConfVecIt |
| typedef opengm::visitors::EmptyVisitor<AStar<GM, ACC> > opengm::AStar< GM, ACC >::EmptyVisitorType |
| typedef GM opengm::AStar< GM, ACC >::GraphicalModelType |
| typedef opengm::visitors::TimingVisitor<AStar<GM, ACC> > opengm::AStar< GM, ACC >::TimingVisitorType |
| typedef opengm::visitors::VerboseVisitor<AStar<GM, ACC> > opengm::AStar< GM, ACC >::VerboseVisitorType |
| opengm::AStar< GM, ACC >::AStar | ( | const GM & | gm, |
| Parameter | para = Parameter() |
||
| ) |
|
virtual |
output a solution
| [out] | arg | labeling |
| argIndex | solution index (1=best, 2=second best, etc.) |
Reimplemented from opengm::Inference< GM, ACC >.
|
virtual |
|
inlinevirtual |
return a bound on the solution
Reimplemented from opengm::Inference< GM, ACC >.
|
inlinevirtual |
output a solution for a marginal for all variables connected to a factor
| factorIndex | index of the factor | |
| [out] | out | the marginal |
Reimplemented from opengm::Inference< GM, ACC >.
|
inlinevirtual |
Implements opengm::Inference< GM, ACC >.
|
virtual |
Implements opengm::Inference< GM, ACC >.
| InferenceTermination opengm::AStar< GM, ACC >::infer | ( | VisitorType & | visitor | ) |
|
inlinevirtual |
output a solution for a marginal for a specific variable
| variableIndex | index of the variable | |
| [out] | out | the marginal |
Reimplemented from opengm::Inference< GM, ACC >.
|
inlinevirtual |
Implements opengm::Inference< GM, ACC >.
|
virtual |
|
virtual |
return the solution (value)
Reimplemented from opengm::Inference< GM, ACC >.
| opengm::AStar< GM, ACC >::OPENGM_GM_TYPE_TYPEDEFS |
1.8.9.1
