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>
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_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 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.
typedef std::map<int, double> pcl::segmentation::grabcut::BoykovKolmogorov::capacitated_edge [protected] |
typedef std::pair<capacitated_edge::iterator, capacitated_edge::iterator> pcl::segmentation::grabcut::BoykovKolmogorov::edge_pair [protected] |
enum pcl::segmentation::grabcut::BoykovKolmogorov::nodestate [protected] |
| 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 | ( | ) | [inline, virtual] |
| void pcl::segmentation::grabcut::BoykovKolmogorov::addConstant | ( | double | c | ) | [inline] |
| 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)
Referenced by pcl::GrabCut< PointT >::addEdge().
| int pcl::segmentation::grabcut::BoykovKolmogorov::addNodes | ( | std::size_t | n = 1 |
) |
add nodes to the graph (returns the id of the first node added)
Referenced by pcl::GrabCut< PointT >::initGraph().
| void pcl::segmentation::grabcut::BoykovKolmogorov::addSourceEdge | ( | int | u, | |
| double | cap | |||
| ) |
add edge from s to nodeId
Referenced by pcl::GrabCut< PointT >::setTerminalWeights().
| void pcl::segmentation::grabcut::BoykovKolmogorov::addTargetEdge | ( | int | u, | |
| double | cap | |||
| ) |
add edge from nodeId to t
Referenced by pcl::GrabCut< PointT >::setTerminalWeights().
| 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
Referenced by pcl::GrabCut< PointT >::initGraph().
| 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))
| void pcl::segmentation::grabcut::BoykovKolmogorov::initializeTrees | ( | ) | [protected] |
initialize trees from source and target
| bool pcl::segmentation::grabcut::BoykovKolmogorov::inSinkTree | ( | int | u | ) | const [inline] |
| bool pcl::segmentation::grabcut::BoykovKolmogorov::inSourceTree | ( | int | u | ) | const [inline] |
| bool pcl::segmentation::grabcut::BoykovKolmogorov::isActive | ( | int | u | ) | const [inline, protected] |
| bool pcl::segmentation::grabcut::BoykovKolmogorov::isActiveSetEmpty | ( | ) | const [inline, protected] |
| 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] |
| 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
Referenced by pcl::GrabCut< PointT >::refineOnce().
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().
double pcl::segmentation::grabcut::BoykovKolmogorov::flow_value_ [protected] |
current flow value (includes constant)
Definition at line 152 of file grabcut.h.
Referenced by addConstant().
std::vector<capacitated_edge> pcl::segmentation::grabcut::BoykovKolmogorov::nodes_ [protected] |
nodes and their outgoing internal edges
Definition at line 150 of file grabcut.h.
Referenced by numNodes().
std::vector<double> pcl::segmentation::grabcut::BoykovKolmogorov::source_edges_ [protected] |
std::vector<double> pcl::segmentation::grabcut::BoykovKolmogorov::target_edges_ [protected] |
