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

#include <pcl/segmentation/grabcut_segmentation.h>

Public Types
using	vertex_descriptor = int

using	edge_capacity_type = double

Public Member Functions
	BoykovKolmogorov (std::size_t max_nodes=0)
	construct a maxflow/mincut problem with estimated max_nodes More...

virtual	~BoykovKolmogorov ()=default
	destructor More...

std::size_t	numNodes () const
	get number of nodes in the graph More...

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

void	clear ()
	clear the graph and internal datastructures More...

int	addNodes (std::size_t n=1)
	add nodes to the graph (returns the id of the first node added) More...

void	addConstant (double c)
	add constant flow to graph More...

void	addSourceEdge (int u, double cap)
	add edge from s to nodeId More...

void	addTargetEdge (int u, double cap)
	add edge from nodeId to t More...

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) More...

double	solve ()
	solve the max-flow problem and return the flow More...

bool	inSourceTree (int u) const
	return true if `u` is in the s-set after calling solve. More...

bool	inSinkTree (int u) const
	return true if `u` is in the t-set after calling solve More...

double	operator() (int u, int v) const
	returns the residual capacity for an edge (use -1 for terminal (-1,-1) is the current flow More...

double	getSourceEdgeCapacity (int u) const

double	getTargetEdgeCapacity (int u) const

Protected Types
enum	nodestate { FREE = 0x00 , SOURCE = 0x01 , TARGET = 0x02 }
	tree states More...

using	capacitated_edge = std::map< int, double >
	capacitated edge More...

using	edge_pair = std::pair< capacitated_edge::iterator, capacitated_edge::iterator >
	edge pair More...

Protected Member Functions
void	preAugmentPaths ()
	pre-augment s-u-t and s-u-v-t paths More...

void	initializeTrees ()
	initialize trees from source and target More...

std::pair< int, int >	expandTrees ()
	expand trees until a path is found (or no path (-1, -1)) More...

void	augmentPath (const std::pair< int, int > &path, std::deque< int > &orphans)
	augment the path found by expandTrees; return orphaned subtrees More...

void	adoptOrphans (std::deque< int > &orphans)
	adopt orphaned subtrees More...

void	clearActive ()
	clear active set More...

bool	isActiveSetEmpty () const

bool	isActive (int u) const
	active if head or previous node is not the terminal More...

void	markActive (int u)
	mark vertex as active More...

void	markInactive (int u)
	mark vertex as inactive More...

Protected Attributes
std::vector< double >	source_edges_
	edges leaving the source More...

std::vector< double >	target_edges_
	edges entering the target More...

std::vector< capacitated_edge >	nodes_
	nodes and their outgoing internal edges More...

double	flow_value_ {0.0}
	current flow value (includes constant) More...

std::vector< unsigned char >	cut_
	identifies which side of the cut a node falls More...

Detailed Description

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

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 63 of file grabcut_segmentation.h.

Member Typedef Documentation

◆ capacitated_edge

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

protected

capacitated edge

Definition at line 121 of file grabcut_segmentation.h.

◆ edge_capacity_type

using pcl::segmentation::grabcut::BoykovKolmogorov::edge_capacity_type = double

Definition at line 67 of file grabcut_segmentation.h.

◆ edge_pair

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

protected

edge pair

Definition at line 123 of file grabcut_segmentation.h.

◆ vertex_descriptor

using pcl::segmentation::grabcut::BoykovKolmogorov::vertex_descriptor = int

Definition at line 66 of file grabcut_segmentation.h.

Member Enumeration Documentation

◆ nodestate

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

protected

tree states

Enumerator
FREE
SOURCE
TARGET

Definition at line 119 of file grabcut_segmentation.h.

Constructor & Destructor Documentation

◆ BoykovKolmogorov()

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

construct a maxflow/mincut problem with estimated max_nodes

◆ ~BoykovKolmogorov()

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

virtualdefault

destructor

Member Function Documentation

◆ addConstant()

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

inline

add constant flow to graph

Definition at line 87 of file grabcut_segmentation.h.

◆ addEdge()

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)

◆ addNodes()

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

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

◆ addSourceEdge()

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

add edge from s to nodeId

◆ addTargetEdge()

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

add edge from nodeId to t

◆ adoptOrphans()

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

protected

adopt orphaned subtrees

◆ augmentPath()

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

◆ clear()

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

clear the graph and internal datastructures

◆ clearActive()

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

protected

clear active set

◆ expandTrees()

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

protected

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

◆ getSourceEdgeCapacity()

double pcl::segmentation::grabcut::BoykovKolmogorov::getSourceEdgeCapacity ( int u ) const

◆ getTargetEdgeCapacity()

double pcl::segmentation::grabcut::BoykovKolmogorov::getTargetEdgeCapacity ( int u ) const

◆ initializeTrees()

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

protected

initialize trees from source and target

◆ inSinkTree()

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 106 of file grabcut_segmentation.h.

◆ inSourceTree()

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 103 of file grabcut_segmentation.h.

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

◆ isActive()

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

inlineprotected

active if head or previous node is not the terminal

Definition at line 146 of file grabcut_segmentation.h.

◆ isActiveSetEmpty()

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

inlineprotected

Returns: true if active set is empty

Definition at line 143 of file grabcut_segmentation.h.

◆ markActive()

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

protected

mark vertex as active

◆ markInactive()

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

protected

mark vertex as inactive

◆ numNodes()

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

inline

get number of nodes in the graph

Definition at line 75 of file grabcut_segmentation.h.

◆ operator()()

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

◆ preAugmentPaths()

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

protected

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

◆ reset()

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

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

◆ solve()

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

solve the max-flow problem and return the flow

Member Data Documentation

◆ cut_

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

protected

identifies which side of the cut a node falls

Definition at line 162 of file grabcut_segmentation.h.

◆ flow_value_

double pcl::segmentation::grabcut::BoykovKolmogorov::flow_value_ {0.0}

protected

current flow value (includes constant)

Definition at line 160 of file grabcut_segmentation.h.

◆ nodes_

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

protected

nodes and their outgoing internal edges

Definition at line 158 of file grabcut_segmentation.h.

◆ source_edges_

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

protected

edges leaving the source

Definition at line 154 of file grabcut_segmentation.h.

◆ target_edges_

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

protected

edges entering the target

Definition at line 156 of file grabcut_segmentation.h.

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

pcl/segmentation/grabcut_segmentation.h

Public Types

Public Member Functions

Protected Types

Protected Member Functions

Protected Attributes

Detailed Description

Member Typedef Documentation

◆ capacitated_edge

◆ edge_capacity_type

◆ edge_pair

◆ vertex_descriptor

Member Enumeration Documentation

◆ nodestate

Constructor & Destructor Documentation

◆ BoykovKolmogorov()

◆ ~BoykovKolmogorov()

Member Function Documentation

◆ addConstant()

◆ addEdge()

◆ addNodes()

◆ addSourceEdge()

◆ addTargetEdge()

◆ adoptOrphans()

◆ augmentPath()

◆ clear()

◆ clearActive()

◆ expandTrees()

◆ getSourceEdgeCapacity()

◆ getTargetEdgeCapacity()

◆ initializeTrees()

◆ inSinkTree()

◆ inSourceTree()

◆ isActive()

◆ isActiveSetEmpty()

◆ markActive()

◆ markInactive()

◆ numNodes()

◆ operator()()

◆ preAugmentPaths()

◆ reset()

◆ solve()

Member Data Documentation

◆ cut_

◆ flow_value_

◆ nodes_

◆ source_edges_

◆ target_edges_