Main Page   Namespace List   Class Hierarchy   Compound List   File List   Namespace Members   Compound Members   File Members  

Graph_cut::PushRelabel_non_linear_grid_3D< Real > Class Template Reference

#include <pushrelabel_non_linear_grid_3D.h>

List of all members.

[NOHEADER]

typedef char direction_type
 Direction used to name an edge by the pair (node,direction).

const direction_type X_MIN_DIR = 1
 Direction used to name an edge by the pair (node,direction).

const direction_type X_MAX_DIR = 2
 Direction used to name an edge by the pair (node,direction).

const direction_type Y_MIN_DIR = 3
 Direction used to name an edge by the pair (node,direction).

const direction_type Y_MAX_DIR = 4
 Direction used to name an edge by the pair (node,direction).

const direction_type Z_MIN_x_min_DIR = 5
 Direction used to name an edge by the pair (node,direction).

const direction_type Z_MIN_x_max_DIR = 6
 Direction used to name an edge by the pair (node,direction).

const direction_type Z_MIN_y_min_DIR = 7
 Direction used to name an edge by the pair (node,direction).

const direction_type Z_MIN_y_max_DIR = 8
 Direction used to name an edge by the pair (node,direction).

const direction_type Z_MAX_x_min_DIR = 9
 Direction used to name an edge by the pair (node,direction).

const direction_type Z_MAX_x_max_DIR = 10
 Direction used to name an edge by the pair (node,direction).

const direction_type Z_MAX_y_min_DIR = 11
 Direction used to name an edge by the pair (node,direction).

const direction_type Z_MAX_y_max_DIR = 12
 Direction used to name an edge by the pair (node,direction).


[NOHEADER]

typedef char location_type
 Position to name a node of coordinate (x;y).

const location_type CENTER_NODE = 100
 Position to name a node of coordinate (x;y).

const location_type Z_MAX_x_min_NODE = 101
 Position to name a node of coordinate (x;y).

const location_type Z_MAX_x_max_NODE = 102
 Position to name a node of coordinate (x;y).

const location_type Z_MAX_y_min_NODE = 103
 Position to name a node of coordinate (x;y).

const location_type Z_MAX_y_max_NODE = 104
 Position to name a node of coordinate (x;y).


Public Types

typedef Real real_type
 Useful typedef.

typedef Array_3D< bool
>::size_type 		size_type
 Useful typedef.

typedef Geometry::Vec3< unsigned
int > 		position_type
 Useful typedef.

typedef unsigned int index_type
 Useful typedef.

typedef unsigned int label_type
 Useful typedef.


Public Methods

 PushRelabel_non_linear_grid_3D (const Array_3D< real_type > &cost_edge_cap, const Array_3D< bool > &dom, const Array_2D< real_type > &x_derivative_edge_cap, const Array_2D< real_type > &y_derivative_edge_cap, const real_type eps=1e-3)
 Constructor.

real_type max_flow ()
 Compute the maximum flow on the graph.

void min_cut (Array_2D< size_type > *const cut) const
 Compute the minimum cut once the maximum flow is known.

void to_index (const node_type &p, size_type *const i) const
 Compute an index for all the 3 coordinates to spare space.

void from_index (node_type *const p, const size_type i) const
 Reverse transformation of to_index().

void neighbors (const node_type &node, node_type *const result, size_type *const n_res) const
 Gives all the neighbors.

void adjacent_nodes (const node_type &node, node_type *const result, size_type *const n_res) const
 Gives the adjacent nodes that are reachable through a non saturated edge.

real_type edge_capacity (const node_type &from, const direction_type dir) const
 Gives the max capacity of an edge named by (node,direction).

real_type edge_flow (const node_type &from, const direction_type dir) const
 Gives the flow in an edge named by (node,direction).

real_type edge_residual (const node_type &from, const direction_type dir) const
 Gives the residual capacity of an edge named by (node,direction).

real_type node_excess (const node_type &node) const
 Gives excess water in a node.

void add_flow (const node_type &from, const direction_type dir, const real_type flow)
 Adds flow to an edge.

direction_type direction (const node_type &from, const node_type &to) const
 Gives the direction of an edge named by (source,target).

label_type relabel (const node_type &node)
 relabel step of the algorithm.

void global_relabel ()
 Global update of the labels.

bool discharge (const node_type &node)
 discharge step of the algorithm.

void add_active_node (const node_type &node)
 Adds an active node.

void get_next_node (node_type *const node, bool *const no_more_node)
 Gets the next node to handle.

bool is_active (const node_type &node) const
 Algorithm defined test.

bool is_admissible (const node_type &from, const node_type &to) const
 Algorithm defined test.

const label_type & label (const node_type &node) const
 Manage the labels.

label_type & label (const node_type &node)
 Manage the labels.


Public Attributes

bool DBG_LOGGING
const real_type epsilon
 Threshold to test zero equality.

size_type nb_nodes
 Number of nodes in the graph.

size_type nb_relabel
 Number of consecutive relabel steps.

Array_3D< real_type > cost_edge_capacity
 Max capacity of the cost edges.

const Array_3D< bool > & domain
Array_2D< size_type > min_bound
 Bottom boundary the optimization domain.

Array_2D< size_type > max_bound
 Top boundary of the optimization domain.

std::deque< index_type > active_node_index
 List of the active nodes.

const node_type source
 Source node.

const node_type target
 Think node.

Array_2D< real_type > x_major_derivative_edge_capacity
 Max capacity of the derivative penalty edges.

Array_2D< real_type > x_minor_derivative_edge_capacity
 Max capacity of the derivative penalty edges.

Array_2D< real_type > y_major_derivative_edge_capacity
 Max capacity of the derivative penalty edges.

Array_2D< real_type > y_minor_derivative_edge_capacity
 Max capacity of the derivative penalty edges.

Array_3D< index_type > label_CENTER
 Node labels.

Array_3D< index_type > label_Z_MAX_x_min
 Node labels.

Array_3D< index_type > label_Z_MAX_x_max
 Node labels.

Array_3D< index_type > label_Z_MAX_y_min
 Node labels.

Array_3D< index_type > label_Z_MAX_y_max
 Node labels.

Array_3D< real_type > cost_edge_Z_MAX_x_min_flow
 Flow in the cost edges.

Array_3D< real_type > cost_edge_Z_MAX_x_max_flow
 Flow in the cost edges.

Array_3D< real_type > cost_edge_Z_MAX_y_min_flow
 Flow in the cost edges.

Array_3D< real_type > cost_edge_Z_MAX_y_max_flow
 Flow in the cost edges.

Array_3D< real_type > cost_edge_Z_MAX_MAX_x_min_flow
 Flow in the cost edges.

Array_3D< real_type > cost_edge_Z_MAX_MAX_x_max_flow
 Flow in the cost edges.

Array_3D< real_type > cost_edge_Z_MAX_MAX_y_min_flow
 Flow in the cost edges.

Array_3D< real_type > cost_edge_Z_MAX_MAX_y_max_flow
 Flow in the cost edges.

Array_3D< real_type > x_major_derivative_edge_flow
 Flow in the penalty edges.

Array_3D< real_type > y_major_derivative_edge_flow
 Flow in the penalty edges.

Array_3D< real_type > x_minor_derivative_edge_flow
 Flow in the penalty edges.

Array_3D< real_type > y_minor_derivative_edge_flow
 Flow in the penalty edges.

const size_type x_size
 Max size of the optimization domain.

const size_type y_size
 Max size of the optimization domain.

const size_type z_size
 Max size of the optimization domain.

Detailed Description

template<typename Real>
class Graph_cut::PushRelabel_non_linear_grid_3D< Real >

Optimized so as to use as few memory as possible : combinatorial information (adjacency) are compute on the fly at each request.

Member Typedef Documentation

template<typename Real>
typedef char Graph_cut::PushRelabel_non_linear_grid_3D< Real >::direction_type
 

Direction used to name an edge by the pair (node,direction).

template<typename Real>
typedef unsigned int Graph_cut::PushRelabel_non_linear_grid_3D< Real >::index_type
 

Useful typedef.

template<typename Real>
typedef unsigned int Graph_cut::PushRelabel_non_linear_grid_3D< Real >::label_type
 

Useful typedef.

template<typename Real>
typedef char Graph_cut::PushRelabel_non_linear_grid_3D< Real >::location_type
 

Position to name a node of coordinate (x;y).

template<typename Real>
typedef Geometry::Vec3<unsigned int> Graph_cut::PushRelabel_non_linear_grid_3D< Real >::position_type
 

Useful typedef.

template<typename Real>
typedef Real Graph_cut::PushRelabel_non_linear_grid_3D< Real >::real_type
 

Useful typedef.

template<typename Real>
typedef Array_3D<bool>::size_type Graph_cut::PushRelabel_non_linear_grid_3D< Real >::size_type
 

Useful typedef.

Constructor & Destructor Documentation

template<typename Real>
Graph_cut::PushRelabel_non_linear_grid_3D< Real >::PushRelabel_non_linear_grid_3D (  const Array_3D< real_type > &    cost_edge_cap,
const Array_3D< bool > &    dom,
const Array_2D< real_type > &    x_derivative_edge_cap,
const Array_2D< real_type > &    y_derivative_edge_cap,
const real_type    eps = 1e-3
) 
 

Constructor.

You have to provide the consistency value for each voxel in cost_edge_cap which is a 3D array (remember the final cut is parameterized as z = h(x,y)). dom is a 3D array with boolean values indacting if the (x,y,z)-voxel is part of optimization domain. x_derivative_edge_cap is 2D array containing the smoothing value between (x,y)-column and (x+1,y)-column. y_derivative_edge_cap is the equivalent part for (x,y) and (x,y+1). eps is a value such that any value smallest than eps is considered to be zero.

Member Function Documentation

template<typename Real>
void Graph_cut::PushRelabel_non_linear_grid_3D< Real >::add_active_node (  const node_type &    node )  [inline]
 

Adds an active node.

template<typename Real>
void Graph_cut::PushRelabel_non_linear_grid_3D< Real >::add_flow (  const node_type &    from,
const direction_type    dir,
const real_type    flow
)  [inline]
 

Adds flow to an edge.

No domain check.

template<typename Real>
void Graph_cut::PushRelabel_non_linear_grid_3D< Real >::adjacent_nodes (  const node_type &    node,
node_type *const    result,
size_type *const    n_res
)  const [inline]
 

Gives the adjacent nodes that are reachable through a non saturated edge.

No domain check.

template<typename Real>
PushRelabel_non_linear_grid_3D< Real >::direction_type Graph_cut::PushRelabel_non_linear_grid_3D< Real >::direction (  const node_type &    from,
const node_type &    to
)  const [inline]
 

Gives the direction of an edge named by (source,target).

template<typename Real>
bool Graph_cut::PushRelabel_non_linear_grid_3D< Real >::discharge (  const node_type &    node )  [inline]
 

discharge step of the algorithm.

true if the operation have been done.

template<typename Real>
PushRelabel_non_linear_grid_3D< Real >::real_type Graph_cut::PushRelabel_non_linear_grid_3D< Real >::edge_capacity (  const node_type &    from,
const direction_type    dir
)  const [inline]
 

Gives the max capacity of an edge named by (node,direction).

Pas de vérification pour les bords.

template<typename Real>
PushRelabel_non_linear_grid_3D< Real >::real_type Graph_cut::PushRelabel_non_linear_grid_3D< Real >::edge_flow (  const node_type &    from,
const direction_type    dir
)  const [inline]
 

Gives the flow in an edge named by (node,direction).

template<typename Real>
PushRelabel_non_linear_grid_3D< Real >::real_type Graph_cut::PushRelabel_non_linear_grid_3D< Real >::edge_residual (  const node_type &    from,
const direction_type    dir
)  const [inline]
 

Gives the residual capacity of an edge named by (node,direction).

template<typename Real>
void Graph_cut::PushRelabel_non_linear_grid_3D< Real >::from_index (  node_type *const    p,
const size_type    i
)  const [inline]
 

Reverse transformation of to_index().

template<typename Real>
void Graph_cut::PushRelabel_non_linear_grid_3D< Real >::get_next_node (  node_type *const    node,
bool *const    no_more_node
)  [inline]
 

Gets the next node to handle.

template<typename Real>
void Graph_cut::PushRelabel_non_linear_grid_3D< Real >::global_relabel (    ) 
 

Global update of the labels.

template<typename Real>
bool Graph_cut::PushRelabel_non_linear_grid_3D< Real >::is_active (  const node_type &    node )  const [inline]
 

Algorithm defined test.

template<typename Real>
bool Graph_cut::PushRelabel_non_linear_grid_3D< Real >::is_admissible (  const node_type &    from,
const node_type &    to
)  const [inline]
 

Algorithm defined test.

template<typename Real>
PushRelabel_non_linear_grid_3D< Real >::label_type & Graph_cut::PushRelabel_non_linear_grid_3D< Real >::label (  const node_type &    node )  [inline]
 

Manage the labels.

template<typename Real>
const PushRelabel_non_linear_grid_3D< Real >::label_type & Graph_cut::PushRelabel_non_linear_grid_3D< Real >::label (  const node_type &    node )  const [inline]
 

Manage the labels.

template<typename Real>
PushRelabel_non_linear_grid_3D< Real >::real_type Graph_cut::PushRelabel_non_linear_grid_3D< Real >::max_flow (    ) 
 

Compute the maximum flow on the graph.

template<typename Real>
void Graph_cut::PushRelabel_non_linear_grid_3D< Real >::min_cut (  Array_2D< size_type > *const    cut )  const
 

Compute the minimum cut once the maximum flow is known.

template<typename Real>
void Graph_cut::PushRelabel_non_linear_grid_3D< Real >::neighbors (  const node_type &    node,
node_type *const    result,
size_type *const    n_res
)  const [inline]
 

Gives all the neighbors.

No domain check.

template<typename Real>
PushRelabel_non_linear_grid_3D< Real >::real_type Graph_cut::PushRelabel_non_linear_grid_3D< Real >::node_excess (  const node_type &    node )  const [inline]
 

Gives excess water in a node.

template<typename Real>
PushRelabel_non_linear_grid_3D< Real >::label_type Graph_cut::PushRelabel_non_linear_grid_3D< Real >::relabel (  const node_type &    node )  [inline]
 

relabel step of the algorithm.

template<typename Real>
void Graph_cut::PushRelabel_non_linear_grid_3D< Real >::to_index (  const node_type &    p,
size_type *const    i
)  const [inline]
 

Compute an index for all the 3 coordinates to spare space.

Member Data Documentation

template<typename Real>
std::deque<index_type> Graph_cut::PushRelabel_non_linear_grid_3D< Real >::active_node_index
 

List of the active nodes.

template<typename Real>
const location_type Graph_cut::PushRelabel_non_linear_grid_3D< Real >::CENTER_NODE = 100 [static]
 

Position to name a node of coordinate (x;y).

template<typename Real>
Array_3D<real_type> Graph_cut::PushRelabel_non_linear_grid_3D< Real >::cost_edge_capacity
 

Max capacity of the cost edges.

template<typename Real>
Array_3D<real_type> Graph_cut::PushRelabel_non_linear_grid_3D< Real >::cost_edge_Z_MAX_MAX_x_max_flow
 

Flow in the cost edges.

Sign refers to the flow direction.

template<typename Real>
Array_3D<real_type> Graph_cut::PushRelabel_non_linear_grid_3D< Real >::cost_edge_Z_MAX_MAX_x_min_flow
 

Flow in the cost edges.

Sign refers to the flow direction.

template<typename Real>
Array_3D<real_type> Graph_cut::PushRelabel_non_linear_grid_3D< Real >::cost_edge_Z_MAX_MAX_y_max_flow
 

Flow in the cost edges.

Sign refers to the flow direction.

template<typename Real>
Array_3D<real_type> Graph_cut::PushRelabel_non_linear_grid_3D< Real >::cost_edge_Z_MAX_MAX_y_min_flow
 

Flow in the cost edges.

Sign refers to the flow direction.

template<typename Real>
Array_3D<real_type> Graph_cut::PushRelabel_non_linear_grid_3D< Real >::cost_edge_Z_MAX_x_max_flow
 

Flow in the cost edges.

Sign refers to the flow direction.

template<typename Real>
Array_3D<real_type> Graph_cut::PushRelabel_non_linear_grid_3D< Real >::cost_edge_Z_MAX_x_min_flow
 

Flow in the cost edges.

Sign refers to the flow direction.

template<typename Real>
Array_3D<real_type> Graph_cut::PushRelabel_non_linear_grid_3D< Real >::cost_edge_Z_MAX_y_max_flow
 

Flow in the cost edges.

Sign refers to the flow direction.

template<typename Real>
Array_3D<real_type> Graph_cut::PushRelabel_non_linear_grid_3D< Real >::cost_edge_Z_MAX_y_min_flow
 

Flow in the cost edges.

Sign refers to the flow direction.

template<typename Real>
bool Graph_cut::PushRelabel_non_linear_grid_3D< Real >::DBG_LOGGING
 

template<typename Real>
const Array_3D<bool>& Graph_cut::PushRelabel_non_linear_grid_3D< Real >::domain
 

Definition of the optimization domain. Graph is only defined on this domain.

template<typename Real>
const real_type Graph_cut::PushRelabel_non_linear_grid_3D< Real >::epsilon
 

Threshold to test zero equality.

template<typename Real>
Array_3D<index_type> Graph_cut::PushRelabel_non_linear_grid_3D< Real >::label_CENTER
 

Node labels.

template<typename Real>
Array_3D<index_type> Graph_cut::PushRelabel_non_linear_grid_3D< Real >::label_Z_MAX_x_max
 

Node labels.

template<typename Real>
Array_3D<index_type> Graph_cut::PushRelabel_non_linear_grid_3D< Real >::label_Z_MAX_x_min
 

Node labels.

template<typename Real>
Array_3D<index_type> Graph_cut::PushRelabel_non_linear_grid_3D< Real >::label_Z_MAX_y_max
 

Node labels.

template<typename Real>
Array_3D<index_type> Graph_cut::PushRelabel_non_linear_grid_3D< Real >::label_Z_MAX_y_min
 

Node labels.

template<typename Real>
Array_2D<size_type> Graph_cut::PushRelabel_non_linear_grid_3D< Real >::max_bound
 

Top boundary of the optimization domain.

template<typename Real>
Array_2D<size_type> Graph_cut::PushRelabel_non_linear_grid_3D< Real >::min_bound
 

Bottom boundary the optimization domain.

template<typename Real>
size_type Graph_cut::PushRelabel_non_linear_grid_3D< Real >::nb_nodes
 

Number of nodes in the graph.

template<typename Real>
size_type Graph_cut::PushRelabel_non_linear_grid_3D< Real >::nb_relabel
 

Number of consecutive relabel steps.

template<typename Real>
const node_type Graph_cut::PushRelabel_non_linear_grid_3D< Real >::source
 

Source node.

template<typename Real>
const node_type Graph_cut::PushRelabel_non_linear_grid_3D< Real >::target
 

Think node.

template<typename Real>
Array_2D<real_type> Graph_cut::PushRelabel_non_linear_grid_3D< Real >::x_major_derivative_edge_capacity
 

Max capacity of the derivative penalty edges.

template<typename Real>
Array_3D<real_type> Graph_cut::PushRelabel_non_linear_grid_3D< Real >::x_major_derivative_edge_flow
 

Flow in the penalty edges.

Sign refers to the flow direction.

template<typename Real>
const direction_type Graph_cut::PushRelabel_non_linear_grid_3D< Real >::X_MAX_DIR = 2 [static]
 

Direction used to name an edge by the pair (node,direction).

template<typename Real>
const direction_type Graph_cut::PushRelabel_non_linear_grid_3D< Real >::X_MIN_DIR = 1 [static]
 

Direction used to name an edge by the pair (node,direction).

template<typename Real>
Array_2D<real_type> Graph_cut::PushRelabel_non_linear_grid_3D< Real >::x_minor_derivative_edge_capacity
 

Max capacity of the derivative penalty edges.

template<typename Real>
Array_3D<real_type> Graph_cut::PushRelabel_non_linear_grid_3D< Real >::x_minor_derivative_edge_flow
 

Flow in the penalty edges.

Sign refers to the flow direction.

template<typename Real>
const size_type Graph_cut::PushRelabel_non_linear_grid_3D< Real >::x_size
 

Max size of the optimization domain.

template<typename Real>
Array_2D<real_type> Graph_cut::PushRelabel_non_linear_grid_3D< Real >::y_major_derivative_edge_capacity
 

Max capacity of the derivative penalty edges.

template<typename Real>
Array_3D<real_type> Graph_cut::PushRelabel_non_linear_grid_3D< Real >::y_major_derivative_edge_flow
 

Flow in the penalty edges.

Sign refers to the flow direction.

template<typename Real>
const direction_type Graph_cut::PushRelabel_non_linear_grid_3D< Real >::Y_MAX_DIR = 4 [static]
 

Direction used to name an edge by the pair (node,direction).

template<typename Real>
const direction_type Graph_cut::PushRelabel_non_linear_grid_3D< Real >::Y_MIN_DIR = 3 [static]
 

Direction used to name an edge by the pair (node,direction).

template<typename Real>
Array_2D<real_type> Graph_cut::PushRelabel_non_linear_grid_3D< Real >::y_minor_derivative_edge_capacity
 

Max capacity of the derivative penalty edges.

template<typename Real>
Array_3D<real_type> Graph_cut::PushRelabel_non_linear_grid_3D< Real >::y_minor_derivative_edge_flow
 

Flow in the penalty edges.

Sign refers to the flow direction.

template<typename Real>
const size_type Graph_cut::PushRelabel_non_linear_grid_3D< Real >::y_size
 

Max size of the optimization domain.

template<typename Real>
const direction_type Graph_cut::PushRelabel_non_linear_grid_3D< Real >::Z_MAX_x_max_DIR = 10 [static]
 

Direction used to name an edge by the pair (node,direction).

template<typename Real>
const location_type Graph_cut::PushRelabel_non_linear_grid_3D< Real >::Z_MAX_x_max_NODE = 102 [static]
 

Position to name a node of coordinate (x;y).

template<typename Real>
const direction_type Graph_cut::PushRelabel_non_linear_grid_3D< Real >::Z_MAX_x_min_DIR = 9 [static]
 

Direction used to name an edge by the pair (node,direction).

template<typename Real>
const location_type Graph_cut::PushRelabel_non_linear_grid_3D< Real >::Z_MAX_x_min_NODE = 101 [static]
 

Position to name a node of coordinate (x;y).

template<typename Real>
const direction_type Graph_cut::PushRelabel_non_linear_grid_3D< Real >::Z_MAX_y_max_DIR = 12 [static]
 

Direction used to name an edge by the pair (node,direction).

template<typename Real>
const location_type Graph_cut::PushRelabel_non_linear_grid_3D< Real >::Z_MAX_y_max_NODE = 104 [static]
 

Position to name a node of coordinate (x;y).

template<typename Real>
const direction_type Graph_cut::PushRelabel_non_linear_grid_3D< Real >::Z_MAX_y_min_DIR = 11 [static]
 

Direction used to name an edge by the pair (node,direction).

template<typename Real>
const location_type Graph_cut::PushRelabel_non_linear_grid_3D< Real >::Z_MAX_y_min_NODE = 103 [static]
 

Position to name a node of coordinate (x;y).

template<typename Real>
const direction_type Graph_cut::PushRelabel_non_linear_grid_3D< Real >::Z_MIN_x_max_DIR = 6 [static]
 

Direction used to name an edge by the pair (node,direction).

template<typename Real>
const direction_type Graph_cut::PushRelabel_non_linear_grid_3D< Real >::Z_MIN_x_min_DIR = 5 [static]
 

Direction used to name an edge by the pair (node,direction).

template<typename Real>
const direction_type Graph_cut::PushRelabel_non_linear_grid_3D< Real >::Z_MIN_y_max_DIR = 8 [static]
 

Direction used to name an edge by the pair (node,direction).

template<typename Real>
const direction_type Graph_cut::PushRelabel_non_linear_grid_3D< Real >::Z_MIN_y_min_DIR = 7 [static]
 

Direction used to name an edge by the pair (node,direction).

template<typename Real>
const size_type Graph_cut::PushRelabel_non_linear_grid_3D< Real >::z_size
 

Max size of the optimization domain.

The documentation for this class was generated from the following file:
Generated on Tue Mar 2 18:12:46 2004 for Graph-cut code by doxygen1.2.18