Point Cloud Library (PCL)  1.9.1-dev
List of all members | Public Types | Public Member Functions | Protected Types | Protected Member Functions | Protected Attributes
pcl::segmentation::grabcut::BoykovKolmogorov Class Reference

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

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 More...
 
virtual ~BoykovKolmogorov ()
 destructor More...
 
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...
 
typedef std::map< int, double > capacitated_edge
 capacitated edge More...
 
typedef std::pair< capacitated_edge::iterator, capacitated_edge::iterator > edge_pair
 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_edgenodes_
 nodes and their outgoing internal edges More...
 
double flow_value_
 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 60 of file grabcut_segmentation.h.

Member Typedef Documentation

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

capacitated edge

Definition at line 118 of file grabcut_segmentation.h.

Definition at line 64 of file grabcut_segmentation.h.

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

edge pair

Definition at line 120 of file grabcut_segmentation.h.

Definition at line 63 of file grabcut_segmentation.h.

Member Enumeration Documentation

tree states

Enumerator
FREE 
SOURCE 
TARGET 

Definition at line 116 of file grabcut_segmentation.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 69 of file grabcut_segmentation.h.

Member Function Documentation

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

add constant flow to graph

Definition at line 84 of file grabcut_segmentation.h.

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

double pcl::segmentation::grabcut::BoykovKolmogorov::getSourceEdgeCapacity ( int  u) const
double pcl::segmentation::grabcut::BoykovKolmogorov::getTargetEdgeCapacity ( int  u) const
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 103 of file grabcut_segmentation.h.

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

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

active if head or previous node is not the terminal

Definition at line 143 of file grabcut_segmentation.h.

bool pcl::segmentation::grabcut::BoykovKolmogorov::isActiveSetEmpty ( ) const
inlineprotected
Returns
true if active set is empty

Definition at line 140 of file grabcut_segmentation.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 72 of file grabcut_segmentation.h.

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

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

current flow value (includes constant)

Definition at line 157 of file grabcut_segmentation.h.

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

nodes and their outgoing internal edges

Definition at line 155 of file grabcut_segmentation.h.

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

edges leaving the source

Definition at line 151 of file grabcut_segmentation.h.

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

edges entering the target

Definition at line 153 of file grabcut_segmentation.h.


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