boost implementation of Boykov and Kolmogorov's maxflow algorithm doesn't support negative flows which makes it inappropriate for this conext. More...

#include <pcl/segmentation/grabcut.h>

Public Types
typedef int	vertex_descriptor
typedef double	edge_capacity_type

Public Member Functions
	BoykovKolmogorov (std::size_t max_nodes=0)
	construct a maxflow/mincut problem with estimated max_nodes
virtual	~BoykovKolmogorov ()
	destructor
size_t	numNodes () const
	get number of nodes in the graph
void	reset ()
	reset all edge capacities to zero (but don't free the graph)
void	clear ()
	clear the graph and internal datastructures
int	addNodes (std::size_t n=1)
	add nodes to the graph (returns the id of the first node added)
void	addConstant (double c)
	add constant flow to graph
void	addSourceEdge (int u, double cap)
	add edge from s to nodeId
void	addTargetEdge (int u, double cap)
	add edge from nodeId to t
void	addEdge (int u, int v, double cap_uv, double cap_vu=0.0)
	add edge from u to v and edge from v to u (requires cap_uv + cap_vu >= 0)
double	solve ()
	solve the max-flow problem and return the flow
bool	inSourceTree (int u) const
	return true if `u` is in the s-set after calling solve.
bool	inSinkTree (int u) const
	return true if `u` is in the t-set after calling solve
double	operator() (int u, int v) const
	returns the residual capacity for an edge (use -1 for terminal (-1,-1) is the current flow

Protected Types
enum	nodestate { FREE = 0x00, SOURCE = 0x01, TARGET = 0x02 }
	tree states More...
typedef std::map< int, double >	capacitated_edge
	capacitated edge
typedef std::pair < capacitated_edge::iterator, capacitated_edge::iterator >	edge_pair
	edge pair

Protected Member Functions
void	preAugmentPaths ()
	pre-augment s-u-t and s-u-v-t paths
void	initializeTrees ()
	initialize trees from source and target
std::pair< int, int >	expandTrees ()
	expand trees until a path is found (or no path (-1, -1))
void	augmentPath (const std::pair< int, int > &path, std::deque< int > &orphans)
	augment the path found by expandTrees; return orphaned subtrees
void	adoptOrphans (std::deque< int > &orphans)
	adopt orphaned subtrees
void	clearActive ()
	clear active set
bool	isActiveSetEmpty () const
bool	isActive (int u) const
	active if head or previous node is not the terminal
void	markActive (int u)
	mark vertex as active
void	markInactive (int u)
	mark vertex as inactive

Protected Attributes
std::vector< double >	source_edges_
	edges leaving the source
std::vector< double >	target_edges_
	edges entering the target
std::vector< capacitated_edge >	nodes_
	nodes and their outgoing internal edges
double	flow_value_
	current flow value (includes constant)
std::vector< unsigned char >	cut_
	identifies which side of the cut a node falls

Detailed Description

boost implementation of Boykov and Kolmogorov's maxflow algorithm doesn't support negative flows which makes it inappropriate for this conext.

This implementation of Boykov and Kolmogorov's maxflow algorithm by Stephen Gould steph.nosp@m.en.g.nosp@m.ould@.nosp@m.anu..nosp@m.edu.a.nosp@m.u in DARWIN under BSD does the trick however solwer than original implementation.

Definition at line 61 of file grabcut.h.

Member Typedef Documentation

typedef std::map<int, double> pcl::segmentation::grabcut::BoykovKolmogorov::capacitated_edge

protected

capacitated edge

Definition at line 113 of file grabcut.h.

typedef double pcl::segmentation::grabcut::BoykovKolmogorov::edge_capacity_type

Definition at line 65 of file grabcut.h.

typedef std::pair<capacitated_edge::iterator, capacitated_edge::iterator> pcl::segmentation::grabcut::BoykovKolmogorov::edge_pair

protected

edge pair

Definition at line 115 of file grabcut.h.

typedef int pcl::segmentation::grabcut::BoykovKolmogorov::vertex_descriptor

Definition at line 64 of file grabcut.h.

Member Enumeration Documentation

enum pcl::segmentation::grabcut::BoykovKolmogorov::nodestate

protected

tree states

Enumerator:

FREE
SOURCE
TARGET

Definition at line 111 of file grabcut.h.

Constructor & Destructor Documentation

pcl::segmentation::grabcut::BoykovKolmogorov::BoykovKolmogorov ( std::size_t max_nodes = 0 )

construct a maxflow/mincut problem with estimated max_nodes

virtual pcl::segmentation::grabcut::BoykovKolmogorov::~BoykovKolmogorov ( )

inlinevirtual

destructor

Definition at line 70 of file grabcut.h.

Member Function Documentation

void pcl::segmentation::grabcut::BoykovKolmogorov::addConstant ( double c )

inline

add constant flow to graph

Definition at line 85 of file grabcut.h.

References flow_value_.

void pcl::segmentation::grabcut::BoykovKolmogorov::addEdge	(	int	u,
		int	v,
		double	cap_uv,
		double	cap_vu = `0.0`
	)

add edge from u to v and edge from v to u (requires cap_uv + cap_vu >= 0)

int pcl::segmentation::grabcut::BoykovKolmogorov::addNodes ( std::size_t n = 1 )

add nodes to the graph (returns the id of the first node added)

void pcl::segmentation::grabcut::BoykovKolmogorov::addSourceEdge	(	int	u,
		double	cap
	)

add edge from s to nodeId

void pcl::segmentation::grabcut::BoykovKolmogorov::addTargetEdge	(	int	u,
		double	cap
	)

add edge from nodeId to t

void pcl::segmentation::grabcut::BoykovKolmogorov::adoptOrphans ( std::deque< int > & orphans )

protected

adopt orphaned subtrees

void pcl::segmentation::grabcut::BoykovKolmogorov::augmentPath	(	const std::pair< int, int > &	path,
		std::deque< int > &	orphans
	)

protected

augment the path found by expandTrees; return orphaned subtrees

void pcl::segmentation::grabcut::BoykovKolmogorov::clear ( )

clear the graph and internal datastructures

void pcl::segmentation::grabcut::BoykovKolmogorov::clearActive ( )

protected

clear active set

std::pair<int, int> pcl::segmentation::grabcut::BoykovKolmogorov::expandTrees ( )

protected

expand trees until a path is found (or no path (-1, -1))

void pcl::segmentation::grabcut::BoykovKolmogorov::initializeTrees ( )

protected

initialize trees from source and target

bool pcl::segmentation::grabcut::BoykovKolmogorov::inSinkTree ( int u ) const

inline

return true if u is in the t-set after calling solve

Definition at line 104 of file grabcut.h.

References cut_, and TARGET.

bool pcl::segmentation::grabcut::BoykovKolmogorov::inSourceTree ( int u ) const

inline

return true if u is in the s-set after calling solve.

Definition at line 101 of file grabcut.h.

References cut_, and SOURCE.

Referenced by pcl::GrabCut< PointT >::isSource().

bool pcl::segmentation::grabcut::BoykovKolmogorov::isActive ( int u ) const

inlineprotected

active if head or previous node is not the terminal

Definition at line 138 of file grabcut.h.

bool pcl::segmentation::grabcut::BoykovKolmogorov::isActiveSetEmpty ( ) const

inlineprotected

Returns: true if active set is empty

Definition at line 135 of file grabcut.h.

void pcl::segmentation::grabcut::BoykovKolmogorov::markActive ( int u )

protected

mark vertex as active

void pcl::segmentation::grabcut::BoykovKolmogorov::markInactive ( int u )

protected

mark vertex as inactive

size_t pcl::segmentation::grabcut::BoykovKolmogorov::numNodes ( ) const

inline

get number of nodes in the graph

Definition at line 73 of file grabcut.h.

References nodes_.

double pcl::segmentation::grabcut::BoykovKolmogorov::operator()	(	int	u,
		int	v
	)		const

returns the residual capacity for an edge (use -1 for terminal (-1,-1) is the current flow

void pcl::segmentation::grabcut::BoykovKolmogorov::preAugmentPaths ( )

protected

pre-augment s-u-t and s-u-v-t paths

void pcl::segmentation::grabcut::BoykovKolmogorov::reset ( )

reset all edge capacities to zero (but don't free the graph)

double pcl::segmentation::grabcut::BoykovKolmogorov::solve ( )

solve the max-flow problem and return the flow

Member Data Documentation

std::vector<unsigned char> pcl::segmentation::grabcut::BoykovKolmogorov::cut_

protected

identifies which side of the cut a node falls

Definition at line 154 of file grabcut.h.

Referenced by inSinkTree(), and inSourceTree().

double pcl::segmentation::grabcut::BoykovKolmogorov::flow_value_

protected

current flow value (includes constant)

Definition at line 152 of file grabcut.h.

Referenced by addConstant().

std::vector<capacitated_edge> pcl::segmentation::grabcut::BoykovKolmogorov::nodes_

protected

nodes and their outgoing internal edges

Definition at line 150 of file grabcut.h.

Referenced by numNodes().

std::vector<double> pcl::segmentation::grabcut::BoykovKolmogorov::source_edges_

protected

edges leaving the source

Definition at line 146 of file grabcut.h.

std::vector<double> pcl::segmentation::grabcut::BoykovKolmogorov::target_edges_

protected

edges entering the target

Definition at line 148 of file grabcut.h.

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

/tmp/buildd/pcl-1.7-1.7.0/segmentation/include/pcl/segmentation/grabcut.h

Public Types

Public Member Functions

Protected Types

Protected Member Functions

Protected Attributes

Detailed Description

Member Typedef Documentation

Member Enumeration Documentation

Constructor & Destructor Documentation

Member Function Documentation

Member Data Documentation