CGraphCut Class Reference

Detailed Description

Graph cuts inference for fatcor graph using V. Kolmogorov's max-flow/min-cut algorithm

Please refer to the paper for more details:

"An Experimental Comparison of Min-Cut/Max-Flow Algorithms for Energy Minimization in Vision." Yuri Boykov and Vladimir Kolmogorov. In IEEE Transactions on Pattern Analysis and Machine Intelligence (PAMI), 2004.

Currently, only binary lablel is supported, factor order <= 3

Definition at line 106 of file GraphCut.h.

Inheritance diagram for CGraphCut:

Public Member Functions
	CGraphCut ()
	CGraphCut (CFactorGraph *fg)
	CGraphCut (int32_t num_nodes, int32_t num_edges)
virtual	~CGraphCut ()
virtual const char *	get_name () const
virtual float64_t	inference (SGVector< int32_t > assignment)
float64_t	get_flow ()
void	build_st_graph (int32_t num_nodes, int32_t num_edges)
void	add_edge (int32_t i, int32_t j, float64_t capacity, float64_t reverse_capacity)
void	add_tweights (int32_t i, float64_t cap_source, float64_t cap_sink)
void	init_maxflow ()
float64_t	compute_maxflow ()
ETerminalType	get_assignment (int32_t i, ETerminalType default_terminal=SOURCE)
void	print_graph ()
void	print_assignment ()
virtual CSGObject *	shallow_copy () const
virtual CSGObject *	deep_copy () const
virtual bool	is_generic (EPrimitiveType *generic) const
template<class T >
void	set_generic ()
template<>
void	set_generic ()
template<>
void	set_generic ()
template<>
void	set_generic ()
template<>
void	set_generic ()
template<>
void	set_generic ()
template<>
void	set_generic ()
template<>
void	set_generic ()
template<>
void	set_generic ()
template<>
void	set_generic ()
template<>
void	set_generic ()
template<>
void	set_generic ()
template<>
void	set_generic ()
template<>
void	set_generic ()
template<>
void	set_generic ()
template<>
void	set_generic ()
void	unset_generic ()
virtual void	print_serializable (const char *prefix="")
virtual bool	save_serializable (CSerializableFile *file, const char *prefix="")
virtual bool	load_serializable (CSerializableFile *file, const char *prefix="")
void	set_global_io (SGIO *io)
SGIO *	get_global_io ()
void	set_global_parallel (Parallel *parallel)
Parallel *	get_global_parallel ()
void	set_global_version (Version *version)
Version *	get_global_version ()
SGStringList< char >	get_modelsel_names ()
void	print_modsel_params ()
char *	get_modsel_param_descr (const char *param_name)
index_t	get_modsel_param_index (const char *param_name)
void	build_gradient_parameter_dictionary (CMap< TParameter *, CSGObject * > *dict)
bool	has (const std::string &name) const
template<typename T >
bool	has (const Tag< T > &tag) const
template<typename T , typename U = void>
bool	has (const std::string &name) const
template<typename T >
void	set (const Tag< T > &_tag, const T &value)
template<typename T , typename U = void>
void	set (const std::string &name, const T &value)
template<typename T >
T	get (const Tag< T > &_tag) const
template<typename T , typename U = void>
T	get (const std::string &name) const
virtual void	update_parameter_hash ()
virtual bool	parameter_hash_changed ()
virtual bool	equals (CSGObject *other, float64_t accuracy=0.0, bool tolerant=false)
virtual CSGObject *	clone ()

Public Attributes
SGIO *	io
Parallel *	parallel
Version *	version
Parameter *	m_parameters
Parameter *	m_model_selection_parameters
Parameter *	m_gradient_parameters
uint32_t	m_hash

Protected Member Functions
virtual void	load_serializable_pre () throw (ShogunException)
virtual void	load_serializable_post () throw (ShogunException)
virtual void	save_serializable_pre () throw (ShogunException)
virtual void	save_serializable_post () throw (ShogunException)
template<typename T >
void	register_param (Tag< T > &_tag, const T &value)
template<typename T >
void	register_param (const std::string &name, const T &value)

Protected Attributes
float64_t	m_map_energy
CFactorGraph *	m_fg

Constructor & Destructor Documentation

CGraphCut

(

)

Constructor

Definition at line 16 of file GraphCut.cpp.

CGraphCut

(

CFactorGraph *

fg

)

Constructor

Parameters

fg	factor graph

Definition at line 24 of file GraphCut.cpp.

CGraphCut	(	int32_t	num_nodes,
		int32_t	num_edges
	)

Constructor This constructor is used for general s-t graph, the next steps to compute the max flow are:

1. use add_tweight and add_edges to add nodes and edges to the s-t graph
2. init_maxflow()
3. compute_maxflow()

Parameters

num_nodes	number of nodes in the s-t graph (SOURCE and SINK nodes are not included)
num_edges	number of edges in the s-t graph (the edges connecting to the SOURCE and SINK are not included)

Definition at line 32 of file GraphCut.cpp.

~CGraphCut ( )

virtual

Destructor

Definition at line 42 of file GraphCut.cpp.

Member Function Documentation

void add_edge	(	int32_t	i,
		int32_t	j,
		float64_t	capacity,
		float64_t	reverse_capacity
	)

Adds a bidirectional edge between 'i' and 'j' with the weights 'cap' and 'rev_cap'.

Parameters

i	node id i
j	node id j
capacity	edge capacity
reverse_capacity	reverse edge capacity

Definition at line 451 of file GraphCut.cpp.

void add_tweights	(	int32_t	i,
		float64_t	cap_source,
		float64_t	cap_sink
	)

Adds new edges 'SOURCE->i' and 'i->SINK' with corresponding weights. Can be called multiple times for each node. Weights can be negative. NOTE: the number of such edges is not counted in edge_num_max. No internal memory is allocated by this call.

Parameters

i	node id i
cap_source	SOURCE->i capacity
cap_sink	i->SINK capacity

Definition at line 431 of file GraphCut.cpp.

void build_gradient_parameter_dictionary ( CMap< TParameter *, CSGObject * > *  dict )

inherited

Builds a dictionary of all parameters in SGObject as well of those of SGObjects that are parameters of this object. Dictionary maps parameters to the objects that own them.

Parameters

dict	dictionary of parameters to be built.

Definition at line 630 of file SGObject.cpp.

void build_st_graph	(	int32_t	num_nodes,
		int32_t	num_edges
	)

Build s-t graph

Parameters

num_nodes	number of nodes in the s-t graph (SOURCE and SINK nodes are not included)
num_edges	number of edges in the s-t graph (the edges connecting to the SOURCE and SINK are not included)

Definition at line 122 of file GraphCut.cpp.

CSGObject * clone ( )

virtualinherited

Creates a clone of the current object. This is done via recursively traversing all parameters, which corresponds to a deep copy. Calling equals on the cloned object always returns true although none of the memory of both objects overlaps.

Returns

an identical copy of the given object, which is disjoint in memory. NULL if the clone fails. Note that the returned object is SG_REF'ed

Definition at line 747 of file SGObject.cpp.

float64_t compute_maxflow

(

)

Compute the maxflow

The algorithm builds up two search trees, a source-tree and a sink-tree. In the beginning of the algorithm only the source and the sink nodes and all other nodes are free nodes. The algorithm consists of three phases:

grow-phase: In this phase active nodes aquire new children from a set of free nodes. The grow phase terminates if there are no more active nodes left or a node discovers a node from the other search tree through an unsaturated edge. In this case a path from source to sink is found.

augmentation-pahse: the input for this stage is a path P from s to t found at the growth stage. Some nodes may become "orphans" because their parents are no longer valid as they are on the augmented path and saturated.

adoption-phase: the adoption stage tries to find a new valid parent for each orphan. A parent should be in the same set (SOURCE or SINK), as the orphan and connected through a non-saturated edge. The stage terminates when no orphans are left and the search tree of SOURCE and SINK are restored.

After the adoption stage is completed, the algorithm returns to the growth stage. The algorithm terminates when the search tree cannot grow (no active nodes) and the trees are seperated by saturated edges. This implies that a maximum flow is achieved.

Returns

the total flow after computing max flow

Definition at line 540 of file GraphCut.cpp.

CSGObject * deep_copy ( ) const

virtualinherited

A deep copy. All the instance variables will also be copied.

Definition at line 231 of file SGObject.cpp.

bool equals ( CSGObject *  other, float64_t  accuracy = 0.0, bool  tolerant = false  )

virtualinherited

Recursively compares the current SGObject to another one. Compares all registered numerical parameters, recursion upon complex (SGObject) parameters. Does not compare pointers!

May be overwritten but please do with care! Should not be necessary in most cases.

Parameters

other	object to compare with
accuracy	accuracy to use for comparison (optional)
tolerant	allows linient check on float equality (within accuracy)

Returns

true if all parameters were equal, false if not

Definition at line 651 of file SGObject.cpp.

T get ( const Tag< T > &  _tag ) const

inherited

Getter for a class parameter, identified by a Tag. Throws an exception if the class does not have such a parameter.

Parameters

_tag	name and type information of parameter

Returns

value of the parameter identified by the input tag

Definition at line 367 of file SGObject.h.

T get ( const std::string &  name ) const

inherited

Getter for a class parameter, identified by a name. Throws an exception if the class does not have such a parameter.

Parameters

name	name of the parameter

Returns

value of the parameter corresponding to the input name and type

Definition at line 388 of file SGObject.h.

ETerminalType get_assignment	(	int32_t	i,
		ETerminalType	default_terminal = SOURCE
	)

After the maxflow is computed, this function returns to which terminal the node 'i' belongs (ETerminalType::SOURCE or ETerminalType::SINK).

Occasionally there may be several minimum cuts. If a node can be assigned to both the source and the sink, then default_terminal is returned.

Parameters

i	node id
default_terminal	default terminal

Returns

terminal that the node belongs to

Definition at line 944 of file GraphCut.cpp.

float64_t get_flow

(

)

Returns

the total flow in the s-t graph

Definition at line 146 of file GraphCut.h.

SGIO * get_global_io ( )

inherited

get the io object

Returns

io object

Definition at line 268 of file SGObject.cpp.

Parallel * get_global_parallel ( )

inherited

get the parallel object

Returns

parallel object

Definition at line 310 of file SGObject.cpp.

Version * get_global_version ( )

inherited

get the version object

Returns

version object

Definition at line 323 of file SGObject.cpp.

SGStringList< char > get_modelsel_names ( )

inherited

Returns

vector of names of all parameters which are registered for model selection

Definition at line 531 of file SGObject.cpp.

char * get_modsel_param_descr ( const char *  param_name )

inherited

Returns description of a given parameter string, if it exists. SG_ERROR otherwise

Parameters

param_name

name of the parameter

Returns

description of the parameter

Definition at line 555 of file SGObject.cpp.

index_t get_modsel_param_index ( const char *  param_name )

inherited

Returns index of model selection parameter with provided index

Parameters

param_name

name of model selection parameter

Returns

index of model selection parameter with provided name, -1 if there is no such

Definition at line 568 of file SGObject.cpp.

virtual const char* get_name ( ) const

virtual

Returns

class name

Reimplemented from CMAPInferImpl.

Definition at line 133 of file GraphCut.h.

bool has ( const std::string &  name ) const

inherited

Checks if object has a class parameter identified by a name.

Parameters

name	name of the parameter

Returns

true if the parameter exists with the input name

Definition at line 289 of file SGObject.h.

bool has ( const Tag< T > &  tag ) const

inherited

Checks if object has a class parameter identified by a Tag.

Parameters

tag	tag of the parameter containing name and type information

Returns

true if the parameter exists with the input tag

Definition at line 301 of file SGObject.h.

bool has ( const std::string &  name ) const

inherited

Checks if a type exists for a class parameter identified by a name.

Parameters

name	name of the parameter

Returns

true if the parameter exists with the input name and type

Definition at line 312 of file SGObject.h.

float64_t inference ( SGVector< int32_t >  assignment )

virtual

Inference

Parameters

assignment

the assignment

Returns

the total energy after doing inference

Implements CMAPInferImpl.

Definition at line 193 of file GraphCut.cpp.

void init_maxflow

(

)

Initialize max flow, call this function after adding nodes and edges

Definition at line 151 of file GraphCut.cpp.

bool is_generic ( EPrimitiveType *  generic ) const

virtualinherited

If the SGSerializable is a class template then TRUE will be returned and GENERIC is set to the type of the generic.

Parameters

generic

set to the type of the generic if returning TRUE

Returns

TRUE if a class template.

Definition at line 329 of file SGObject.cpp.

bool load_serializable ( CSerializableFile *  file, const char *  prefix = ""  )

virtualinherited

Load this object from file. If it will fail (returning FALSE) then this object will contain inconsistent data and should not be used!

Parameters

file	where to load from
prefix	prefix for members

Returns

TRUE if done, otherwise FALSE

Definition at line 402 of file SGObject.cpp.

void load_serializable_post ( ) throw ( ShogunException )

protectedvirtualinherited

Can (optionally) be overridden to post-initialize some member variables which are not PARAMETER::ADD'ed. Make sure that at first the overridden method BASE_CLASS::LOAD_SERIALIZABLE_POST is called.

Exceptions

ShogunException

will be thrown if an error occurs.

Reimplemented in CKernel, CWeightedDegreePositionStringKernel, CList, CAlphabet, CLinearHMM, CGaussianKernel, CInverseMultiQuadricKernel, CCircularKernel, and CExponentialKernel.

Definition at line 459 of file SGObject.cpp.

void load_serializable_pre ( ) throw ( ShogunException )

protectedvirtualinherited

Can (optionally) be overridden to pre-initialize some member variables which are not PARAMETER::ADD'ed. Make sure that at first the overridden method BASE_CLASS::LOAD_SERIALIZABLE_PRE is called.

Exceptions

ShogunException

will be thrown if an error occurs.

Reimplemented in CDynamicArray< T >, CDynamicArray< float64_t >, CDynamicArray< float32_t >, CDynamicArray< int32_t >, CDynamicArray< char >, CDynamicArray< bool >, and CDynamicObjectArray.

Definition at line 454 of file SGObject.cpp.

bool parameter_hash_changed ( )

virtualinherited

Returns

whether parameter combination has changed since last update

Definition at line 295 of file SGObject.cpp.

void print_assignment

(

)

Print assignment

Definition at line 984 of file GraphCut.cpp.

void print_graph

(

)

Print the s-t graph

Definition at line 956 of file GraphCut.cpp.

void print_modsel_params ( )

inherited

prints all parameter registered for model selection and their type

Definition at line 507 of file SGObject.cpp.

void print_serializable ( const char *  prefix = "" )

virtualinherited

prints registered parameters out

Parameters

prefix

prefix for members

Definition at line 341 of file SGObject.cpp.

void register_param ( Tag< T > &  _tag, const T &  value  )

protectedinherited

Registers a class parameter which is identified by a tag. This enables the parameter to be modified by set() and retrieved by get(). Parameters can be registered in the constructor of the class.

Parameters

_tag	name and type information of parameter
value	value of the parameter

Definition at line 439 of file SGObject.h.

void register_param ( const std::string &  name, const T &  value  )

protectedinherited

Registers a class parameter which is identified by a name. This enables the parameter to be modified by set() and retrieved by get(). Parameters can be registered in the constructor of the class.

Parameters

name	name of the parameter
value	value of the parameter along with type information

Definition at line 452 of file SGObject.h.

bool save_serializable ( CSerializableFile *  file, const char *  prefix = ""  )

virtualinherited

Save this object to file.

Parameters

file	where to save the object; will be closed during returning if PREFIX is an empty string.
prefix	prefix for members

Returns

TRUE if done, otherwise FALSE

Definition at line 347 of file SGObject.cpp.

void save_serializable_post ( ) throw ( ShogunException )

protectedvirtualinherited

Can (optionally) be overridden to post-initialize some member variables which are not PARAMETER::ADD'ed. Make sure that at first the overridden method BASE_CLASS::SAVE_SERIALIZABLE_POST is called.

Exceptions

ShogunException

will be thrown if an error occurs.

Reimplemented in CKernel.

Definition at line 469 of file SGObject.cpp.

void save_serializable_pre ( ) throw ( ShogunException )

protectedvirtualinherited

Can (optionally) be overridden to pre-initialize some member variables which are not PARAMETER::ADD'ed. Make sure that at first the overridden method BASE_CLASS::SAVE_SERIALIZABLE_PRE is called.

Exceptions

ShogunException

will be thrown if an error occurs.

Reimplemented in CKernel, CDynamicArray< T >, CDynamicArray< float64_t >, CDynamicArray< float32_t >, CDynamicArray< int32_t >, CDynamicArray< char >, CDynamicArray< bool >, and CDynamicObjectArray.

Definition at line 464 of file SGObject.cpp.

void set ( const Tag< T > &  _tag, const T &  value  )

inherited

Setter for a class parameter, identified by a Tag. Throws an exception if the class does not have such a parameter.

Parameters

_tag	name and type information of parameter
value	value of the parameter

Definition at line 328 of file SGObject.h.

void set ( const std::string &  name, const T &  value  )

inherited

Setter for a class parameter, identified by a name. Throws an exception if the class does not have such a parameter.

Parameters

name	name of the parameter
value	value of the parameter along with type information

Definition at line 354 of file SGObject.h.

void set_generic ( )

inherited

Definition at line 74 of file SGObject.cpp.

void set_generic ( )

inherited

Definition at line 79 of file SGObject.cpp.

void set_generic ( )

inherited

Definition at line 84 of file SGObject.cpp.

void set_generic ( )

inherited

Definition at line 89 of file SGObject.cpp.

void set_generic ( )

inherited

Definition at line 94 of file SGObject.cpp.

void set_generic ( )

inherited

Definition at line 99 of file SGObject.cpp.

void set_generic ( )

inherited

Definition at line 104 of file SGObject.cpp.

void set_generic ( )

inherited

Definition at line 109 of file SGObject.cpp.

void set_generic ( )

inherited

Definition at line 114 of file SGObject.cpp.

void set_generic ( )

inherited

Definition at line 119 of file SGObject.cpp.

void set_generic ( )

inherited

Definition at line 124 of file SGObject.cpp.

void set_generic ( )

inherited

Definition at line 129 of file SGObject.cpp.

void set_generic ( )

inherited

Definition at line 134 of file SGObject.cpp.

void set_generic ( )

inherited

Definition at line 139 of file SGObject.cpp.

void set_generic ( )

inherited

Definition at line 144 of file SGObject.cpp.

void set_generic ( )

inherited

set generic type to T

void set_global_io ( SGIO *  io )

inherited

set the io object

Parameters

io	io object to use

Definition at line 261 of file SGObject.cpp.

void set_global_parallel ( Parallel *  parallel )

inherited

set the parallel object

Parameters

parallel

parallel object to use

Definition at line 274 of file SGObject.cpp.

void set_global_version ( Version *  version )

inherited

set the version object

Parameters

version

version object to use

Definition at line 316 of file SGObject.cpp.

CSGObject * shallow_copy ( ) const

virtualinherited

A shallow copy. All the SGObject instance variables will be simply assigned and SG_REF-ed.

Reimplemented in CGaussianKernel.

Definition at line 225 of file SGObject.cpp.

void unset_generic ( )

inherited

unset generic type

this has to be called in classes specializing a template class

Definition at line 336 of file SGObject.cpp.

void update_parameter_hash ( )

virtualinherited

Updates the hash of current parameter combination

Definition at line 281 of file SGObject.cpp.

Member Data Documentation

SGIO* io

inherited

io

Definition at line 537 of file SGObject.h.

CFactorGraph* m_fg

protectedinherited

pointer of factor graph

Definition at line 128 of file MAPInference.h.

Parameter* m_gradient_parameters

inherited

parameters wrt which we can compute gradients

Definition at line 552 of file SGObject.h.

uint32_t m_hash

inherited

Hash of parameter values

Definition at line 555 of file SGObject.h.

float64_t m_map_energy

protected

the total energy of the factor graph

Definition at line 307 of file GraphCut.h.

Parameter* m_model_selection_parameters

inherited

model selection parameters

Definition at line 549 of file SGObject.h.

Parameter* m_parameters

inherited

parameters

Definition at line 546 of file SGObject.h.

Parallel* parallel

inherited

parallel

Definition at line 540 of file SGObject.h.

Version* version

inherited

version

Definition at line 543 of file SGObject.h.

---

The documentation for this class was generated from the following files:

• GraphCut.h
• GraphCut.cpp