Point Cloud Library (PCL)  1.7.0
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 conext. More...

#include <pcl/segmentation/grabcut.h>

List of all members.

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_edgenodes_
 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 <stephen.gould@anu.edu.au> 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.

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.

Definition at line 64 of file grabcut.h.


Member Enumeration Documentation

tree states

Enumerator:
FREE 
SOURCE 
TARGET 

Definition at line 111 of file grabcut.h.


Constructor & Destructor Documentation

construct a maxflow/mincut problem with estimated max_nodes

destructor

Definition at line 70 of file grabcut.h.


Member Function Documentation

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)

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

add edge from s to nodeId

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

clear the graph and internal datastructures

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

initialize trees from source and target

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

Definition at line 104 of file grabcut.h.

References cut_, and TARGET.

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 [inline, protected]

active if head or previous node is not the terminal

Definition at line 138 of file grabcut.h.

Returns:
true if active set is empty

Definition at line 135 of file grabcut.h.

mark vertex as active

mark vertex as inactive

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

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

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

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

current flow value (includes constant)

Definition at line 152 of file grabcut.h.

Referenced by addConstant().

nodes and their outgoing internal edges

Definition at line 150 of file grabcut.h.

Referenced by numNodes().

edges leaving the source

Definition at line 146 of file grabcut.h.

edges entering the target

Definition at line 148 of file grabcut.h.


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