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

struct	RebindGm

struct	RebindGmAndAcc

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

Detailed Description

template<class GM, class ACC>
class opengm::AStar< GM, ACC >

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.

Examples:: one_to_one_matching.cxx.

Definition at line 64 of file astar.hxx.

Member Typedef Documentation

§ AccumulationType

template<class GM, class ACC>

typedef ACC opengm::AStar< GM, ACC >::AccumulationType

accumulation type

Definition at line 70 of file astar.hxx.

§ ConfVec

template<class GM, class ACC>

typedef std::vector<LabelType> opengm::AStar< GM, ACC >::ConfVec

configuration vector type

Definition at line 73 of file astar.hxx.

§ ConfVecIt

template<class GM, class ACC>

typedef ConfVec::iterator opengm::AStar< GM, ACC >::ConfVecIt

configuration iterator

Definition at line 75 of file astar.hxx.

§ EmptyVisitorType

template<class GM, class ACC>

typedef opengm::visitors::EmptyVisitor<AStar<GM, ACC> > opengm::AStar< GM, ACC >::EmptyVisitorType

Definition at line 79 of file astar.hxx.

§ GraphicalModelType

template<class GM, class ACC>

typedef GM opengm::AStar< GM, ACC >::GraphicalModelType

graphical model type

Definition at line 68 of file astar.hxx.

§ TimingVisitorType

template<class GM, class ACC>

typedef opengm::visitors::TimingVisitor<AStar<GM, ACC> > opengm::AStar< GM, ACC >::TimingVisitorType

Definition at line 78 of file astar.hxx.

§ VerboseVisitorType

template<class GM, class ACC>

typedef opengm::visitors::VerboseVisitor<AStar<GM, ACC> > opengm::AStar< GM, ACC >::VerboseVisitorType

visitor

Definition at line 77 of file astar.hxx.

Member Enumeration Documentation

§ Heuristic

template<class GM, class ACC>

enum opengm::AStar::Heuristic

Enumerator
DEFAULT_HEURISTIC
FAST_HEURISTIC
STANDARD_HEURISTIC

Definition at line 93 of file astar.hxx.

Constructor & Destructor Documentation

§ AStar()

template<class GM , class ACC >

opengm::AStar< GM, ACC >::AStar	(	const GM &	gm,
		Parameter	para = `Parameter()`
	)

constructor

Parameters

gm	graphical model
para	AStar parameter

Definition at line 193 of file astar.hxx.

Here is the caller graph for this function:

Member Function Documentation

§ arg()

template<class GM, class ACC>

InferenceTermination opengm::AStar< GM, ACC >::arg	(	std::vector< LabelType > &	arg,
		const size_t	argIndex = `1`
	)		const

virtual

output a solution

Parameters

[out]	arg	labeling
	argIndex	solution index (1=best, 2=second best, etc.)

Reimplemented from opengm::Inference< GM, ACC >.

Definition at line 360 of file astar.hxx.

Here is the call graph for this function:

Here is the caller graph for this function:

§ args()

template<class GM, class ACC>

InferenceTermination opengm::AStar< GM, ACC >::args ( std::vector< std::vector< LabelType > > & v ) const

virtual

args

Parameters

[out]

Reimplemented from opengm::Inference< GM, ACC >.

Definition at line 377 of file astar.hxx.

Here is the caller graph for this function:

§ bound()

template<class GM, class ACC>

ValueType opengm::AStar< GM, ACC >::bound ( ) const

inlinevirtual

return a bound on the solution

Reimplemented from opengm::Inference< GM, ACC >.

Definition at line 150 of file astar.hxx.

§ factorMarginal()

template<class GM, class ACC>

virtual InferenceTermination opengm::AStar< GM, ACC >::factorMarginal	(	const size_t	factorIndex,
		IndependentFactorType &	out
	)		const

inlinevirtual

output a solution for a marginal for all variables connected to a factor

Parameters

	factorIndex	index of the factor
[out]	out	the marginal

Reimplemented from opengm::Inference< GM, ACC >.

Definition at line 153 of file astar.hxx.

Here is the call graph for this function:

§ graphicalModel()

template<class GM , class ACC >

const AStar< GM, ACC >::GraphicalModelType & opengm::AStar< GM, ACC >::graphicalModel ( ) const

inlinevirtual

Implements opengm::Inference< GM, ACC >.

Definition at line 710 of file astar.hxx.

§ infer() [1/2]

template<class GM , class ACC >

InferenceTermination opengm::AStar< GM, ACC >::infer ( )

virtual

Implements opengm::Inference< GM, ACC >.

Definition at line 300 of file astar.hxx.

Here is the call graph for this function:

§ infer() [2/2]

template<class GM , class ACC >

template<class VisitorType >

InferenceTermination opengm::AStar< GM, ACC >::infer ( VisitorType & visitor )

inference with visitor

Parameters

visitor visitor

Definition at line 310 of file astar.hxx.

§ marginal()

template<class GM, class ACC>

virtual InferenceTermination opengm::AStar< GM, ACC >::marginal	(	const size_t	variableIndex,
		IndependentFactorType &	out
	)		const

inlinevirtual

output a solution for a marginal for a specific variable

Parameters

	variableIndex	index of the variable
[out]	out	the marginal

Reimplemented from opengm::Inference< GM, ACC >.

Definition at line 152 of file astar.hxx.

§ name()

template<class GM, class ACC>

virtual std::string opengm::AStar< GM, ACC >::name ( ) const

inlinevirtual

Implements opengm::Inference< GM, ACC >.

Definition at line 145 of file astar.hxx.

Here is the call graph for this function:

§ reset()

template<class GM , class ACC >

void opengm::AStar< GM, ACC >::reset ( )

virtual

reset

Warning: reset assumes that the structure of the graphical model has not changed

TODO

todo

Definition at line 293 of file astar.hxx.

§ value()

template<class GM , class ACC >

GM::ValueType opengm::AStar< GM, ACC >::value ( ) const

virtual

return the solution (value)

Reimplemented from opengm::Inference< GM, ACC >.

Definition at line 348 of file astar.hxx.

Here is the call graph for this function:

Member Data Documentation

§ OPENGM_GM_TYPE_TYPEDEFS

template<class GM, class ACC>

opengm::AStar< GM, ACC >::OPENGM_GM_TYPE_TYPEDEFS

Definition at line 71 of file astar.hxx.

Classes

Public Types

Public Member Functions

Public Attributes

Detailed Description

template<class GM, class ACC> class opengm::AStar< GM, ACC >

Member Typedef Documentation

§ AccumulationType

§ ConfVec

§ ConfVecIt

§ EmptyVisitorType

§ GraphicalModelType

§ TimingVisitorType

§ VerboseVisitorType

Member Enumeration Documentation

§ Heuristic

Constructor & Destructor Documentation

§ AStar()

Member Function Documentation

§ arg()

§ args()

§ bound()

§ factorMarginal()

§ graphicalModel()

§ infer() [1/2]

§ infer() [2/2]

§ marginal()

§ name()

§ reset()

§ value()

Member Data Documentation

§ OPENGM_GM_TYPE_TYPEDEFS

template<class GM, class ACC>
class opengm::AStar< GM, ACC >