Point Cloud Library (PCL) 1.12.0
|
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 | |
virtual | ~BoykovKolmogorov () |
destructor | |
std::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 | |
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 | |
using | edge_pair = std::pair<capacitated_edge::iterator, capacitated_edge::iterator> |
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 | |
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.
|
protected |
capacitated edge
Definition at line 121 of file grabcut_segmentation.h.
Definition at line 67 of file grabcut_segmentation.h.
|
protected |
edge pair
Definition at line 123 of file grabcut_segmentation.h.
Definition at line 66 of file grabcut_segmentation.h.
pcl::segmentation::grabcut::BoykovKolmogorov::BoykovKolmogorov | ( | std::size_t | max_nodes = 0 | ) |
construct a maxflow/mincut problem with estimated max_nodes
|
inlinevirtual |
destructor
Definition at line 72 of file grabcut_segmentation.h.
add constant flow to graph
Definition at line 87 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)
add edge from s to nodeId
add edge from nodeId to t
|
protected |
adopt orphaned subtrees
|
protected |
augment the path found by expandTrees; return orphaned subtrees
void pcl::segmentation::grabcut::BoykovKolmogorov::clear | ( | ) |
clear the graph and internal datastructures
|
protected |
clear active set
expand trees until a path is found (or no path (-1, -1))
|
protected |
initialize trees from source and target
return true if u
is in the t-set after calling solve
Definition at line 106 of file grabcut_segmentation.h.
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().
active if head or previous node is not the terminal
Definition at line 146 of file grabcut_segmentation.h.
|
inlineprotected |
Definition at line 143 of file grabcut_segmentation.h.
mark vertex as active
mark vertex as inactive
|
inline |
get number of nodes in the graph
Definition at line 75 of file grabcut_segmentation.h.
returns the residual capacity for an edge (use -1 for terminal (-1,-1) is the current flow
|
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
identifies which side of the cut a node falls
Definition at line 162 of file grabcut_segmentation.h.
|
protected |
current flow value (includes constant)
Definition at line 160 of file grabcut_segmentation.h.
|
protected |
nodes and their outgoing internal edges
Definition at line 158 of file grabcut_segmentation.h.
|
protected |
edges leaving the source
Definition at line 154 of file grabcut_segmentation.h.
|
protected |
edges entering the target
Definition at line 156 of file grabcut_segmentation.h.