[ VIGRA Homepage | Function Index | Class Index | Namespaces | File List | Main Page ]

| Graph Data Structures and Algorithms |

## Classes

class | AdjacencyListGraph
| undirected adjacency list graph in the LEMON API More...
class | GridGraph< N, DirectedTag >
| Define a grid graph in arbitrary dimensions. More...
class | ShortestPathDijkstra< GRAPH, WEIGHT_TYPE >
| shortest path computer More...

## Functions

template<class GRAPH , class EDGE_WEIGHTS , class SEEDS , class LABELS >
void | carvingSegmentation (const GRAPH &g, const EDGE_WEIGHTS &edgeWeights, const SEEDS &seeds, const typename LABELS::Value backgroundLabel, const typename EDGE_WEIGHTS::Value backgroundBias, const typename EDGE_WEIGHTS::Value noPriorBelow, LABELS &labels)
| edge weighted watersheds Segmentataion More...
template<class G , class A , class B >
void | copyEdgeMap (const G &g, const A &a, B &b)
| copy a lemon edge map
template<class G , class A , class B >
void | copyNodeMap (const G &g, const A &a, B &b)
| copy a lemon node map
template<class GRAPH , class WEIGHTS , class COMPERATOR >
void | edgeSort (const GRAPH &g, const WEIGHTS &weights, const COMPERATOR &comperator, std::vector< typename GRAPH::Edge > &sortedEdges)
| get a vector of Edge descriptors More...
template<class GRAPH , class EDGE_WEIGHTS , class SEEDS , class LABELS >
void | edgeWeightedWatershedsSegmentation (const GRAPH &g, const EDGE_WEIGHTS &edgeWeights, const SEEDS &seeds, LABELS &labels)
| edge weighted watersheds Segmentataion More...
template<unsigned int N, class DirectedTag , class T , class EDGEMAP >
void | edgeWeightsFromInterpolatedImage (const GridGraph< N, DirectedTag > &g, const MultiArrayView< N, T > &interpolatedImage, EDGEMAP &edgeWeights, bool euclidean=false)
| create edge weights from an interpolated image More...
template<unsigned int N, class DirectedTag , class NODEMAP , class EDGEMAP , class FUNCTOR >
void | edgeWeightsFromNodeWeights (const GridGraph< N, DirectedTag > &g, const NODEMAP &nodeWeights, EDGEMAP &edgeWeights, bool euclidean, FUNCTOR const &func)
| create edge weights from node weights More...
template<class GRAPH , class EDGE_WEIGHTS , class NODE_SIZE , class NODE_LABEL_MAP >
void | felzenszwalbSegmentation (const GRAPH &graph, const EDGE_WEIGHTS &edgeWeights, const NODE_SIZE &nodeSizes, float k, NODE_LABEL_MAP &nodeLabeling, const int nodeNumStopCond=-1)
| edge weighted watersheds Segmentataion More...
template<class G , class A , class T >
void | fillEdgeMap (const G &g, A &a, const T &value)
| fill a lemon edge map
template<class G , class A , class T >
void | fillNodeMap (const G &g, A &a, const T &value)
| fill a lemon node map
template<class GRAPH , class NODE_FEATURES_IN , class EDGE_INDICATOR , class NODE_FEATURES_OUT >
void | graphSmoothing (const GRAPH &g, const NODE_FEATURES_IN &nodeFeaturesIn, const EDGE_INDICATOR &edgeIndicator, const float lambda, const float edgeThreshold, const float scale, NODE_FEATURES_OUT &nodeFeaturesOut)
| smooth node features of a graph More...
template<class GRAPH_IN , class GRAPH_IN_NODE_LABEL_MAP >
void | makeRegionAdjacencyGraph (GRAPH_IN graphIn, GRAPH_IN_NODE_LABEL_MAP labels, AdjacencyListGraph &rag, typename AdjacencyListGraph::template EdgeMap< std::vector< typename GRAPH_IN::Edge > > &affiliatedEdges, const Int64 ignoreLabel=-1)
| make a region adjacency graph from a graph and labels w.r.t. that graph More...
template<class NODE , class PREDECESSORS >
size_t | pathLength (const NODE source, const NODE target, const PREDECESSORS &predecessors)
| get the length in node units of a path
template<class RAG , class BASE_GRAPH , class BASE_GRAPH_RAG_LABELS , class BASE_GRAPH_GT , class RAG_GT , class RAG_GT_QT >
void | projectGroundTruth (const RAG &rag, const BASE_GRAPH &baseGraph, const BASE_GRAPH_RAG_LABELS &baseGraphRagLabels, const BASE_GRAPH_GT &baseGraphGt, RAG_GT &ragGt, RAG_GT_QT &ragGtQt)
template<class RAGGRAPH , class GRAPH , class RAGEDGES , unsigned int N, class T >
MultiArray< 2, MultiArrayIndex > | ragFindEdges (const RAGGRAPH &rag, const GRAPH &graph, const RAGEDGES &affiliatedEdges, MultiArrayView< N, T > labelsArray, const typename RAGGRAPH::Node &node)
| Find indices of points on the edges. More...
template<class GRAPH , class NODE_FEATURES_IN , class EDGE_INDICATOR , class NODE_FEATURES_OUT >
void | recursiveGraphSmoothing (const GRAPH &g, const NODE_FEATURES_IN &nodeFeaturesIn, const EDGE_INDICATOR &edgeIndicator, const float lambda, const float edgeThreshold, const float scale, size_t iterations, NODE_FEATURES_OUT &nodeFeaturesBuffer, NODE_FEATURES_OUT &nodeFeaturesOut)
| smooth node features of a graph More...
template<class GRAPH , class WEIGHTS , class PREDECESSORS , class DISTANCE , class HEURSTIC >
void | shortestPathAStar (const GRAPH &graph, const typename GRAPH::Node &source, const typename GRAPH::Node &target, const WEIGHTS &weights, PREDECESSORS &predecessors, DISTANCE &distance, const HEURSTIC &heuristic)
| Astar Shortest path search.

## Detailed Description

Graph algorithms and the underlying graph data structures (e.g. GridGraph and AdjacencyListGraph) implementing the APIs of the boost::graph and LEMON libraries.

See also the GridGraph additions to namespace `boost`.

## Function Documentation

## ◆ edgeSort()

void vigra::edgeSort | ( | const GRAPH & | g,
|  | const WEIGHTS & | weights,
|  | const COMPERATOR & | comperator,
|  | std::vector< typename GRAPH::Edge > & | sortedEdges
| ) |  |

get a vector of Edge descriptors

Sort the Edge descriptors given weights and a comperator

## ◆ makeRegionAdjacencyGraph()

void vigra::makeRegionAdjacencyGraph | ( | GRAPH_IN | graphIn,
|  | GRAPH_IN_NODE_LABEL_MAP | labels,
|  | AdjacencyListGraph & | rag,
|  | typename AdjacencyListGraph::template EdgeMap< std::vector< typename GRAPH_IN::Edge > > & | affiliatedEdges,
|  | const Int64 | ignoreLabel = `-1`
| ) |  |

make a region adjacency graph from a graph and labels w.r.t. that graph

Parameters

  | graphIn | : input graph
  | labels | : labels w.r.t. graphIn
  [out] | rag | : region adjacency graph
  [out] | affiliatedEdges | : a vector of edges of graphIn for each edge in rag
  | ignoreLabel | : optional label to ignore (default: -1 means no label will be ignored)

## ◆ edgeWeightedWatershedsSegmentation()

void vigra::edgeWeightedWatershedsSegmentation | ( | const GRAPH & | g,
|  | const EDGE_WEIGHTS & | edgeWeights,
|  | const SEEDS & | seeds,
|  | LABELS & | labels
| ) |  |

edge weighted watersheds Segmentataion

Parameters

  | g | input graph
  | edgeWeights | : edge weights / edge indicator
  | seeds | : seed must be non empty!
  [out] | labels | : resulting nodeLabeling (not necessarily dense)

## ◆ carvingSegmentation()

void vigra::carvingSegmentation | ( | const GRAPH & | g,
|  | const EDGE_WEIGHTS & | edgeWeights,
|  | const SEEDS & | seeds,
|  | const typename LABELS::Value | backgroundLabel,
|  | const typename EDGE_WEIGHTS::Value | backgroundBias,
|  | const typename EDGE_WEIGHTS::Value | noPriorBelow,
|  | LABELS & | labels
| ) |  |

edge weighted watersheds Segmentataion

Parameters

  | g | input graph
  | edgeWeights | : edge weights / edge indicator
  | seeds | : seed must be non empty!
  | backgroundLabel | : which label is background
  | backgroundBias | : bias for background
  | noPriorBelow | : don't bias the background if edge indicator is below this value
  [out] | labels | : resulting nodeLabeling (not necessarily dense)

## ◆ felzenszwalbSegmentation()

void vigra::felzenszwalbSegmentation | ( | const GRAPH & | graph,
|  | const EDGE_WEIGHTS & | edgeWeights,
|  | const NODE_SIZE & | nodeSizes,
|  | float | k,
|  | NODE_LABEL_MAP & | nodeLabeling,
|  | const int | nodeNumStopCond = `-1`
| ) |  |

edge weighted watersheds Segmentataion

Parameters

  | graph | input graph
  | edgeWeights | : edge weights / edge indicator
  | nodeSizes | : size of each node
  | k | : free parameter of felzenszwalb algorithm
  [out] | nodeLabeling | : nodeLabeling (not necessarily dense)
  | nodeNumStopCond | : optional stopping condition

## ◆ graphSmoothing()

void vigra::graphSmoothing | ( | const GRAPH & | g,
|  | const NODE_FEATURES_IN & | nodeFeaturesIn,
|  | const EDGE_INDICATOR & | edgeIndicator,
|  | const float | lambda,
|  | const float | edgeThreshold,
|  | const float | scale,
|  | NODE_FEATURES_OUT & | nodeFeaturesOut
| ) |  |

smooth node features of a graph

Parameters

  | g | : input graph
  | nodeFeaturesIn | : input node features which should be smoothed
  | edgeIndicator | : edge indicator to indicate over which edges one should smooth
  | lambda | : scale edge indicator by lambda before taking negative exponent
  | edgeThreshold | : edge threshold
  | scale | : how much smoothing should be applied
  [out] | nodeFeaturesOut | : smoothed node features

## ◆ recursiveGraphSmoothing()

void vigra::recursiveGraphSmoothing | ( | const GRAPH & | g,
|  | const NODE_FEATURES_IN & | nodeFeaturesIn,
|  | const EDGE_INDICATOR & | edgeIndicator,
|  | const float | lambda,
|  | const float | edgeThreshold,
|  | const float | scale,
|  | size_t | iterations,
|  | NODE_FEATURES_OUT & | nodeFeaturesBuffer,
|  | NODE_FEATURES_OUT & | nodeFeaturesOut
| ) |  |

smooth node features of a graph

Parameters

  | g | : input graph
  | nodeFeaturesIn | : input node features which should be smoothed
  | edgeIndicator | : edge indicator to indicate over which edges one should smooth
  | lambda | : scale edge indicator by lambda before taking negative exponent
  | edgeThreshold | : edge threshold
  | scale | : how much smoothing should be applied
  | iterations | : how often should this algorithm be called recursively
  [out] | nodeFeaturesBuffer | : preallocated(!) buffer to store node features temp.
  [out] | nodeFeaturesOut | : smoothed node features

## ◆ projectGroundTruth()

void vigra::projectGroundTruth | ( | const RAG & | rag,
|  | const BASE_GRAPH & | baseGraph,
|  | const BASE_GRAPH_RAG_LABELS & | baseGraphRagLabels,
|  | const BASE_GRAPH_GT & | baseGraphGt,
|  | RAG_GT & | ragGt,
|  | RAG_GT_QT & | ragGtQt
| ) |  |

project ground truth from a base graph, to a region adjacency graph.

## ◆ ragFindEdges()

MultiArray<2, MultiArrayIndex> vigra::ragFindEdges | ( | const RAGGRAPH & | rag,
|  | const GRAPH & | graph,
|  | const RAGEDGES & | affiliatedEdges,
|  | MultiArrayView< N, T > | labelsArray,
|  | const typename RAGGRAPH::Node & | node
| ) |  |

Find indices of points on the edges.

Parameters

  rag | : Region adjacency graph of the labels array
  graph | : Graph of labels array
  affiliatedEdges | : The affiliated edges of the region adjacency graph
  labelsArray | : The label image
  node | : The node (of the region adjacency graph), whose edges shall be found

## ◆ edgeWeightsFromNodeWeights()

void vigra::edgeWeightsFromNodeWeights | ( | const GridGraph< N, DirectedTag > & | g,
|  | const NODEMAP & | nodeWeights,
|  | EDGEMAP & | edgeWeights,
|  | bool | euclidean,
|  | FUNCTOR const & | func
| ) |  |

create edge weights from node weights

Parameters

  | g | : input graph
  | nodeWeights | : node property map holding node weights
  [out] | edgeWeights | : resulting edge weights
  | euclidean | : if 'true', multiply the computed weights with the Euclidean distance between the edge's end nodes (default: 'false')
  | func | : binary function that computes the edge weight from the weights of the edge's end nodes (default: take the average)

## ◆ edgeWeightsFromInterpolatedImage()

void vigra::edgeWeightsFromInterpolatedImage | ( | const GridGraph< N, DirectedTag > & | g,
|  | const MultiArrayView< N, T > & | interpolatedImage,
|  | EDGEMAP & | edgeWeights,
|  | bool | euclidean = `false`
| ) |  |

create edge weights from an interpolated image

Parameters

  | g | : input graph
  | interpolatedImage | : interpolated image
  [out] | edgeWeights | : edge weights
  | euclidean | : if 'true', multiply the weights with the Euclidean distance between the edge's end nodes (default: 'false')

For each edge, the function reads the weight from `interpolatedImage[u+v]`, where `u` and `v` are the coordinates of the edge's end points.

© Ullrich Köthe (ullrich.koethe@iwr.uni-heidelberg.de) Heidelberg Collaboratory for Image Processing, University of Heidelberg, Germany | html generated using doxygen and Python vigra 1.11.0