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 () |
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_ |
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 in DARWIN under BSD does the trick however solwer than original implementation. en.g ould@ anu. edu.a u
Definition at line 63 of file grabcut_segmentation.h.
Member Typedef Documentation
capacitated_edge
|
protected |
capacitated edge
Definition at line 121 of file grabcut_segmentation.h.
edge_capacity_type
Definition at line 67 of file grabcut_segmentation.h.
edge_pair
|
protected |
edge pair
Definition at line 123 of file grabcut_segmentation.h.
vertex_descriptor
Definition at line 66 of file grabcut_segmentation.h.
Member Enumeration Documentation
nodestate
|
protected |
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()
|
inlinevirtual |
destructor
Definition at line 72 of file grabcut_segmentation.h.
Member Function Documentation
addConstant()
|
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()
|
protected |
adopt orphaned subtrees
augmentPath()
|
protected |
augment the path found by expandTrees; return orphaned subtrees
clear()
void pcl::segmentation::grabcut::BoykovKolmogorov::clear | ( | ) |
clear the graph and internal datastructures
clearActive()
|
protected |
clear active set
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()
|
protected |
initialize trees from source and target
inSinkTree()
|
inline |
return true if u
is in the t-set after calling solve
Definition at line 106 of file grabcut_segmentation.h.
inSourceTree()
|
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()
|
inlineprotected |
active if head or previous node is not the terminal
Definition at line 146 of file grabcut_segmentation.h.
isActiveSetEmpty()
|
inlineprotected |
- Returns
- true if active set is empty
Definition at line 143 of file grabcut_segmentation.h.
markActive()
|
protected |
mark vertex as active
markInactive()
|
protected |
mark vertex as inactive
numNodes()
|
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()
|
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_
|
protected |
identifies which side of the cut a node falls
Definition at line 162 of file grabcut_segmentation.h.
flow_value_
|
protected |
current flow value (includes constant)
Definition at line 160 of file grabcut_segmentation.h.
nodes_
|
protected |
nodes and their outgoing internal edges
Definition at line 158 of file grabcut_segmentation.h.
source_edges_
|
protected |
edges leaving the source
Definition at line 154 of file grabcut_segmentation.h.
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
© 2009–2012, Willow Garage, Inc.
© 2012–, Open Perception, Inc.
Licensed under the BSD License.
https://pointclouds.org/documentation/classpcl_1_1segmentation_1_1grabcut_1_1_boykov_kolmogorov.html