40 #ifndef VIGRA_GRAPH_ALGORITHMS_HXX 41 #define VIGRA_GRAPH_ALGORITHMS_HXX 52 #include "graph_generalization.hxx" 53 #include "multi_gridgraph.hxx" 54 #include "priority_queue.hxx" 55 #include "union_find.hxx" 56 #include "adjacency_list_graph.hxx" 57 #include "graph_maps.hxx" 63 #include "functorexpression.hxx" 64 #include "array_vector.hxx" 72 namespace detail_graph_algorithms{
73 template <
class GRAPH_MAP,
class COMPERATOR>
74 struct GraphItemCompare
77 GraphItemCompare(
const GRAPH_MAP & map,
const COMPERATOR & comperator)
79 comperator_(comperator){
84 bool operator()(
const KEY & a,
const KEY & b)
const{
85 return comperator_(map_[a],map_[b]);
88 const GRAPH_MAP & map_;
89 const COMPERATOR & comperator_;
97 template<
class GRAPH,
class WEIGHTS,
class COMPERATOR>
100 const WEIGHTS & weights,
101 const COMPERATOR & comperator,
102 std::vector<typename GRAPH::Edge> & sortedEdges
104 sortedEdges.resize(g.edgeNum());
106 for(
typename GRAPH::EdgeIt e(g);e!=lemon::INVALID;++e){
110 detail_graph_algorithms::GraphItemCompare<WEIGHTS,COMPERATOR> edgeComperator(weights,comperator);
111 std::sort(sortedEdges.begin(),sortedEdges.end(),edgeComperator);
116 template<
class G,
class A,
class B>
118 typename G::NodeIt iter(g);
119 while(iter!=lemon::INVALID){
126 template<
class G,
class A,
class B>
128 typename G::EdgeIt iter(g);
129 while(iter!=lemon::INVALID){
135 template<
class G,
class A,
class T>
137 typename G::NodeIt iter(g);
138 while(iter!=lemon::INVALID){
144 template<
class G,
class A,
class T>
146 typename G::EdgeIt iter(g);
147 while(iter!=lemon::INVALID){
163 class GRAPH_IN_NODE_LABEL_MAP
167 GRAPH_IN_NODE_LABEL_MAP labels,
169 typename AdjacencyListGraph:: template EdgeMap< std::vector<typename GRAPH_IN::Edge> > & affiliatedEdges,
170 const Int64 ignoreLabel=-1
173 typedef typename GraphMapTypeTraits<GRAPH_IN_NODE_LABEL_MAP>::Value LabelType;
174 typedef GRAPH_IN GraphIn;
177 typedef typename GraphIn::Edge EdgeGraphIn;
178 typedef typename GraphIn::NodeIt NodeItGraphIn;
179 typedef typename GraphIn::EdgeIt EdgeItGraphIn;
180 typedef typename GraphOut::Edge EdgeGraphOut;
183 for(NodeItGraphIn iter(graphIn);iter!=lemon::INVALID;++iter){
184 const LabelType l=labels[*iter];
185 if(ignoreLabel==-1 || static_cast<Int64>(l)!=ignoreLabel)
189 for(EdgeItGraphIn e(graphIn);e!=lemon::INVALID;++e){
190 const EdgeGraphIn
edge(*e);
191 const LabelType lu = labels[graphIn.u(edge)];
192 const LabelType lv = labels[graphIn.v(edge)];
193 if( lu!=lv && ( ignoreLabel==-1 || (static_cast<Int64>(lu)!=ignoreLabel && static_cast<Int64>(lv)!=ignoreLabel) ) ){
200 affiliatedEdges.assign(rag);
201 for(EdgeItGraphIn e(graphIn);e!=lemon::INVALID;++e){
202 const EdgeGraphIn
edge(*e);
203 const LabelType lu = labels[graphIn.u(edge)];
204 const LabelType lv = labels[graphIn.v(edge)];
206 if( lu!=lv && ( ignoreLabel==-1 || (static_cast<Int64>(lu)!=ignoreLabel && static_cast<Int64>(lv)!=ignoreLabel) ) ){
210 affiliatedEdges[ragEdge].push_back(edge);
216 template<
unsigned int DIM,
class DTAG,
class AFF_EDGES>
217 size_t affiliatedEdgesSerializationSize(
220 const AFF_EDGES & affEdges
227 for(EdgeIt iter(rag); iter!=lemon::INVALID; ++iter){
230 size+=affEdges[e].size()*(DIM+1);
235 template<
class OUT_ITER,
unsigned int DIM,
class DTAG,
class AFF_EDGES>
236 void serializeAffiliatedEdges(
239 const AFF_EDGES & affEdges,
247 for(EdgeIt iter(rag); iter!=lemon::INVALID; ++iter){
249 const Edge
edge = *iter;
250 const size_t numAffEdge = affEdges[
edge].size();
251 *outIter = numAffEdge; ++outIter;
253 for(
size_t i=0; i<numAffEdge; ++i){
254 const GEdge gEdge = affEdges[
edge][i];
255 for(
size_t d=0; d<DIM+1; ++d){
256 *outIter = gEdge[d]; ++outIter;
262 template<
class IN_ITER,
unsigned int DIM,
class DTAG,
class AFF_EDGES>
263 void deserializeAffiliatedEdges(
266 AFF_EDGES & affEdges,
275 affEdges.assign(rag);
277 for(EdgeIt iter(rag); iter!=lemon::INVALID; ++iter){
279 const Edge
edge = *iter;
280 const size_t numAffEdge = *begin; ++begin;
282 for(
size_t i=0; i<numAffEdge; ++i){
284 for(
size_t d=0; d<DIM+1; ++d){
285 gEdge[d]=*begin; ++begin;
287 affEdges[
edge].push_back(gEdge);
296 template<
class GRAPH,
class WEIGHT_TYPE>
301 typedef typename Graph::Node Node;
302 typedef typename Graph::NodeIt NodeIt;
303 typedef typename Graph::Edge Edge;
304 typedef typename Graph::OutArcIt OutArcIt;
306 typedef WEIGHT_TYPE WeightType;
308 typedef typename Graph:: template NodeMap<Node> PredecessorsMap;
309 typedef typename Graph:: template NodeMap<WeightType> DistanceMap;
315 pq_(g.maxNodeId()+1),
333 template<
class WEIGHTS>
335 const Node &
target = lemon::INVALID,
336 WeightType maxDistance=NumericTraits<WeightType>::max())
338 this->initializeMaps(source);
339 runImpl(weights,
target, maxDistance);
355 template<
class WEIGHTS>
356 void run(Node
const & start, Node
const & stop,
357 const WEIGHTS & weights,
const Node & source,
358 const Node &
target = lemon::INVALID,
359 WeightType maxDistance=NumericTraits<WeightType>::max())
362 "ShortestPathDijkstra::run(): source is not within ROI");
363 vigra_precondition(
target == lemon::INVALID ||
365 "ShortestPathDijkstra::run(): target is not within ROI");
366 this->initializeMaps(source, start, stop);
367 runImpl(weights,
target, maxDistance);
376 template<
class WEIGHTS>
377 void reRun(
const WEIGHTS & weights,
const Node & source,
378 const Node &
target = lemon::INVALID,
379 WeightType maxDistance=NumericTraits<WeightType>::max())
381 this->reInitializeMaps(source);
382 runImpl(weights,
target, maxDistance);
389 template<
class WEIGHTS,
class ITER>
392 const Node &
target = lemon::INVALID,
393 WeightType maxDistance=NumericTraits<WeightType>::max())
395 this->initializeMapsMultiSource(source_begin, source_end);
396 runImpl(weights,
target, maxDistance);
404 template<
class EFGE_WEIGHTS,
class NODE_WEIGHTS,
class ITER>
407 const EFGE_WEIGHTS & edgeWeights,
408 const NODE_WEIGHTS & nodeWeights,
411 const Node &
target = lemon::INVALID,
412 WeightType maxDistance = NumericTraits<WeightType>::max())
414 this->initializeMapsMultiSource(source_begin, source_end);
415 runImplWithNodeWeights(edgeWeights, nodeWeights,
target, maxDistance);
433 return target_!=lemon::INVALID;
438 return discoveryOrder_;
459 template<
class WEIGHTS>
460 void runImpl(
const WEIGHTS & weights,
461 const Node &
target = lemon::INVALID,
462 WeightType maxDistance=NumericTraits<WeightType>::max())
464 ZeroNodeMap<Graph, WEIGHT_TYPE> zeroNodeMap;
465 this->runImplWithNodeWeights(weights,zeroNodeMap,
target, maxDistance);
469 template<
class EDGE_WEIGHTS,
class NODE_WEIGHTS>
470 void runImplWithNodeWeights(
471 const EDGE_WEIGHTS & edgeWeights,
472 const NODE_WEIGHTS & nodeWeights,
473 const Node &
target = lemon::INVALID,
474 WeightType maxDistance=NumericTraits<WeightType>::max())
476 target_ = lemon::INVALID;
477 while(!pq_.empty() ){
478 const Node topNode(graph_.nodeFromId(pq_.top()));
479 if(distMap_[topNode] > maxDistance)
482 discoveryOrder_.push_back(topNode);
486 for(OutArcIt outArcIt(graph_,topNode);outArcIt!=lemon::INVALID;++outArcIt){
487 const Node otherNode = graph_.target(*outArcIt);
488 const size_t otherNodeId = graph_.id(otherNode);
489 const WeightType otherNodeWeight = nodeWeights[otherNode];
490 if(pq_.contains(otherNodeId)){
491 const Edge
edge(*outArcIt);
492 const WeightType currentDist = distMap_[otherNode];
493 const WeightType alternativeDist = distMap_[topNode]+edgeWeights[
edge]+otherNodeWeight;
494 if(alternativeDist<currentDist){
495 pq_.push(otherNodeId,alternativeDist);
496 distMap_[otherNode]=alternativeDist;
497 predMap_[otherNode]=topNode;
500 else if(predMap_[otherNode]==lemon::INVALID){
501 const Edge
edge(*outArcIt);
502 const WeightType initialDist = distMap_[topNode]+edgeWeights[
edge]+otherNodeWeight;
503 if(initialDist<=maxDistance)
505 pq_.push(otherNodeId,initialDist);
506 distMap_[otherNode]=initialDist;
507 predMap_[otherNode]=topNode;
512 while(!pq_.empty() ){
513 const Node topNode(graph_.nodeFromId(pq_.top()));
514 predMap_[topNode]=lemon::INVALID;
517 if(
target == lemon::INVALID || discoveryOrder_.back() ==
target)
518 target_ = discoveryOrder_.back();
522 void initializeMaps(Node
const & source){
523 for(NodeIt n(graph_); n!=lemon::INVALID; ++n){
525 predMap_[node]=lemon::INVALID;
527 distMap_[
source]=
static_cast<WeightType
>(0.0);
529 discoveryOrder_.clear();
530 pq_.push(graph_.id(source),0.0);
534 void initializeMaps(Node
const & source,
535 Node
const & start, Node
const & stop)
537 Node left_border = min(start, Node(1)),
538 right_border = min(predMap_.shape()-stop, Node(1)),
539 DONT_TOUCH = Node(lemon::INVALID) - Node(1);
542 left_border, right_border, DONT_TOUCH);
543 predMap_.subarray(start, stop) = lemon::INVALID;
546 distMap_[
source]=
static_cast<WeightType
>(0.0);
547 discoveryOrder_.clear();
548 pq_.push(graph_.id(source),0.0);
552 template <
class ITER>
553 void initializeMapsMultiSource(ITER source, ITER source_end){
554 for(NodeIt n(graph_); n!=lemon::INVALID; ++n){
556 predMap_[node]=lemon::INVALID;
558 discoveryOrder_.clear();
559 for( ; source != source_end; ++
source)
561 distMap_[*
source]=
static_cast<WeightType
>(0.0);
563 pq_.push(graph_.id(*source),0.0);
565 source_=lemon::INVALID;
568 void reInitializeMaps(Node
const & source){
569 for(
unsigned int n=0; n<discoveryOrder_.size(); ++n){
570 predMap_[discoveryOrder_[n]]=lemon::INVALID;
572 distMap_[
source]=
static_cast<WeightType
>(0.0);
574 discoveryOrder_.clear();
575 pq_.push(graph_.id(source),0.0);
579 const Graph & graph_;
581 PredecessorsMap predMap_;
582 DistanceMap distMap_;
583 DiscoveryOrder discoveryOrder_;
590 template<
class NODE,
class PREDECESSORS>
594 const PREDECESSORS & predecessors
596 if(predecessors[target]==lemon::INVALID)
599 NODE currentNode =
target;
601 while(currentNode!=source){
602 currentNode=predecessors[currentNode];
610 template<
class GRAPH,
class WEIGHTS,
class PREDECESSORS,
class DISTANCE,
class HEURSTIC>
613 const typename GRAPH::Node & source,
614 const typename GRAPH::Node &
target,
615 const WEIGHTS & weights,
616 PREDECESSORS & predecessors,
618 const HEURSTIC & heuristic
622 typedef typename Graph::Edge Edge;
623 typedef typename Graph::Node Node;
624 typedef typename Graph::NodeIt NodeIt;
625 typedef typename Graph::OutArcIt OutArcIt;
626 typedef typename DISTANCE::value_type DistanceType;
628 typename GRAPH:: template NodeMap<bool> closedSet(graph);
631 for(NodeIt n(graph);n!=lemon::INVALID;++n){
633 closedSet[node]=
false;
634 distance[node]=std::numeric_limits<DistanceType>::infinity();
635 predecessors[node]=lemon::INVALID;
638 distance[
source]=
static_cast<DistanceType
>(0.0);
639 estimatedDistanceOpenSet.push(graph.id(source),heuristic(source,target));
642 while(!estimatedDistanceOpenSet.empty()){
645 const Node current = graph.nodeFromId(estimatedDistanceOpenSet.top());
653 estimatedDistanceOpenSet.pop();
654 closedSet[current]=
true;
657 for(OutArcIt outArcIt(graph,current);outArcIt!=lemon::INVALID;++outArcIt){
660 const Node neighbour = graph.target(*outArcIt);
661 const size_t neighbourId = graph.id(neighbour);
664 if(!closedSet[neighbour]){
667 const Edge
edge(*outArcIt);
670 const DistanceType tenativeScore = distance[current] + weights[
edge];
673 if(!estimatedDistanceOpenSet.contains(neighbourId) || tenativeScore < distance[neighbour] ){
675 predecessors[neighbour]=current;
676 distance[neighbour]=tenativeScore;
680 estimatedDistanceOpenSet.push(neighbourId,distance[neighbour]+heuristic(neighbour,target));
695 void shortestPathSegmentation(
697 const EDGE_WEIGHTS & edgeWeights,
698 const NODE_WEIGHTS & nodeWeights,
699 SEED_NODE_MAP & seeds
703 typedef typename Graph::Node Node;
704 typedef typename Graph::NodeIt NodeIt;
705 typedef WEIGHT_TYPE WeightType;
708 std::vector<Node> seededNodes;
709 for(NodeIt n(graph);n!=lemon::INVALID;++n){
713 seededNodes.push_back(node);
719 typedef typename Sp::PredecessorsMap PredecessorsMap;
721 sp.runMultiSource(edgeWeights, nodeWeights, seededNodes.begin(), seededNodes.end());
722 const PredecessorsMap & predMap = sp.predecessors();
724 for(NodeIt n(graph);n!=lemon::INVALID;++n){
728 Node pred=predMap[node];
729 while(seeds[pred]==0){
732 seeds[node]=seeds[pred];
737 namespace detail_watersheds_segmentation{
739 struct RawPriorityFunctor{
740 template<
class L,
class T>
741 T operator()(
const L label,
const T priority)
const{
748 template<
class PRIORITY_TYPE,
class LABEL_TYPE>
749 struct CarvingFunctor{
750 CarvingFunctor(
const LABEL_TYPE backgroundLabel,
751 const PRIORITY_TYPE & factor,
752 const PRIORITY_TYPE & noPriorBelow
754 : backgroundLabel_(backgroundLabel),
756 noPriorBelow_(noPriorBelow){
758 PRIORITY_TYPE operator()(
const LABEL_TYPE label,
const PRIORITY_TYPE priority)
const{
759 if(priority>=noPriorBelow_)
760 return (label==backgroundLabel_ ? priority*factor_ : priority);
765 LABEL_TYPE backgroundLabel_;
766 PRIORITY_TYPE factor_;
767 PRIORITY_TYPE noPriorBelow_;
775 class PRIORITY_MANIP_FUNCTOR,
778 void edgeWeightedWatershedsSegmentationImpl(
780 const EDGE_WEIGHTS & edgeWeights,
782 PRIORITY_MANIP_FUNCTOR & priorManipFunctor,
786 typedef typename Graph::Edge Edge;
787 typedef typename Graph::Node Node;
788 typedef typename Graph::NodeIt NodeIt;
789 typedef typename Graph::OutArcIt OutArcIt;
791 typedef typename EDGE_WEIGHTS::Value WeightType;
792 typedef typename LABELS::Value LabelType;
803 for(NodeIt n(g);n!=lemon::INVALID;++n){
805 if(labels[node]!=static_cast<LabelType>(0)){
806 for(OutArcIt a(g,node);a!=lemon::INVALID;++a){
808 const Node neigbour=g.target(*a);
810 if(labels[neigbour]==static_cast<LabelType>(0)){
811 const WeightType priority = priorManipFunctor(labels[node],edgeWeights[edge]);
812 pq.push(edge,priority);
822 const Edge
edge = pq.top();
825 const Node u = g.u(edge);
826 const Node v = g.v(edge);
827 const LabelType lU = labels[u];
828 const LabelType lV = labels[v];
832 throw std::runtime_error(
"both have no labels");
834 else if(lU!=0 && lV!=0){
839 const Node unlabeledNode = lU==0 ? u : v;
840 const LabelType label = lU==0 ? lV : lU;
843 labels[unlabeledNode] = label;
846 for(OutArcIt a(g,unlabeledNode);a!=lemon::INVALID;++a){
847 const Edge otherEdge(*a);
848 const Node targetNode=g.target(*a);
849 if(labels[targetNode] == 0){
851 const WeightType priority = priorManipFunctor(label,edgeWeights[otherEdge]);
852 pq.push(otherEdge,priority);
871 template<
class GRAPH,
class EDGE_WEIGHTS,
class SEEDS,
class LABELS>
874 const EDGE_WEIGHTS & edgeWeights,
878 detail_watersheds_segmentation::RawPriorityFunctor fPriority;
879 detail_watersheds_segmentation::edgeWeightedWatershedsSegmentationImpl(g,edgeWeights,seeds,fPriority,labels);
892 template<
class GRAPH,
class EDGE_WEIGHTS,
class SEEDS,
class LABELS>
895 const EDGE_WEIGHTS & edgeWeights,
897 const typename LABELS::Value backgroundLabel,
898 const typename EDGE_WEIGHTS::Value backgroundBias,
899 const typename EDGE_WEIGHTS::Value noPriorBelow,
902 typedef typename EDGE_WEIGHTS::Value WeightType;
903 typedef typename LABELS::Value LabelType;
904 detail_watersheds_segmentation::CarvingFunctor<WeightType,LabelType> fPriority(backgroundLabel,backgroundBias, noPriorBelow);
905 detail_watersheds_segmentation::edgeWeightedWatershedsSegmentationImpl(g,edgeWeights,seeds,fPriority,labels);
916 template<
class GRAPH ,
class EDGE_WEIGHTS,
class NODE_SIZE,
class NODE_LABEL_MAP>
919 const EDGE_WEIGHTS & edgeWeights,
920 const NODE_SIZE & nodeSizes,
922 NODE_LABEL_MAP & nodeLabeling,
923 const int nodeNumStopCond = -1
926 typedef typename Graph::Edge Edge;
927 typedef typename Graph::Node Node;
929 typedef typename EDGE_WEIGHTS::Value WeightType;
930 typedef typename EDGE_WEIGHTS::Value NodeSizeType;
931 typedef typename Graph:: template NodeMap<WeightType> NodeIntDiffMap;
932 typedef typename Graph:: template NodeMap<NodeSizeType> NodeSizeAccMap;
935 NodeIntDiffMap internalDiff(graph);
936 NodeSizeAccMap nodeSizeAcc(graph);
938 fillNodeMap(graph,internalDiff,static_cast<WeightType>(0.0));
945 std::vector<Edge> sortedEdges;
946 std::less<WeightType> comperator;
947 edgeSort(graph,edgeWeights,comperator,sortedEdges);
950 UnionFindArray<UInt64> ufdArray(graph.maxNodeId()+1);
953 size_t nodeNum = graph.nodeNum();
958 for(
size_t i=0;i<sortedEdges.size();++i){
959 const Edge e = sortedEdges[i];
960 const size_t rui = ufdArray.findIndex(graph.id(graph.u(e)));
961 const size_t rvi = ufdArray.findIndex(graph.id(graph.v(e)));
962 const Node ru = graph.nodeFromId(rui);
963 const Node rv = graph.nodeFromId(rvi);
967 const WeightType w = edgeWeights[e];
968 const NodeSizeType sizeRu = nodeSizeAcc[ru];
969 const NodeSizeType sizeRv = nodeSizeAcc[rv];
970 const WeightType tauRu =
static_cast<WeightType
>(k)/static_cast<WeightType>(sizeRu);
971 const WeightType tauRv =
static_cast<WeightType
>(k)/static_cast<WeightType>(sizeRv);
972 const WeightType minIntDiff = std::min(internalDiff[ru]+tauRu,internalDiff[rv]+tauRv);
975 ufdArray.makeUnion(rui,rvi);
978 const size_t newRepId = ufdArray.findIndex(rui);
979 const Node newRepNode = graph.nodeFromId(newRepId);
980 internalDiff[newRepNode]=w;
981 nodeSizeAcc[newRepNode] = sizeRu+sizeRv;
984 if(nodeNum==nodeNumStopCond){
988 if(nodeNumStopCond==-1){
992 if(nodeNum>nodeNumStopCond){
1000 ufdArray.makeContiguous();
1001 for(
typename GRAPH::NodeIt n(graph);n!=lemon::INVALID;++n){
1002 const Node node(*n);
1003 nodeLabeling[node]=ufdArray.findLabel(graph.id(node));
1010 namespace detail_graph_smoothing{
1014 class NODE_FEATURES_IN,
1016 class WEIGHTS_TO_SMOOTH_FACTOR,
1017 class NODE_FEATURES_OUT
1019 void graphSmoothingImpl(
1021 const NODE_FEATURES_IN & nodeFeaturesIn,
1022 const EDGE_WEIGHTS & edgeWeights,
1023 WEIGHTS_TO_SMOOTH_FACTOR & weightsToSmoothFactor,
1024 NODE_FEATURES_OUT & nodeFeaturesOut
1027 typedef GRAPH Graph;
1028 typedef typename Graph::Edge Edge;
1029 typedef typename Graph::Node Node;
1030 typedef typename Graph::NodeIt NodeIt;
1031 typedef typename Graph::OutArcIt OutArcIt;
1033 typedef typename NODE_FEATURES_IN::Value NodeFeatureInValue;
1034 typedef typename NODE_FEATURES_OUT::Reference NodeFeatureOutRef;
1035 typedef typename EDGE_WEIGHTS::ConstReference SmoothFactorType;
1040 for(NodeIt n(g);n!=lemon::INVALID;++n){
1042 const Node node(*n);
1044 NodeFeatureInValue featIn = nodeFeaturesIn[node];
1045 NodeFeatureOutRef featOut = nodeFeaturesOut[node];
1048 float weightSum = 0.0;
1050 for(OutArcIt a(g,node);a!=lemon::INVALID;++a){
1051 const Edge
edge(*a);
1052 const Node neigbour(g.target(*a));
1053 SmoothFactorType smoothFactor= weightsToSmoothFactor(edgeWeights[edge]);
1055 NodeFeatureInValue neighbourFeat = nodeFeaturesIn[neigbour];
1056 neighbourFeat*=smoothFactor;
1058 featOut = neighbourFeat;
1060 featOut += neighbourFeat;
1061 weightSum+=smoothFactor;
1065 featIn*=
static_cast<float>(
degree);
1066 weightSum+=
static_cast<float>(
degree);
1073 struct ExpSmoothFactor{
1074 ExpSmoothFactor(
const T lambda,
const T edgeThreshold,
const T scale)
1076 edgeThreshold_(edgeThreshold),
1079 T operator()(
const T weight){
1080 return weight> edgeThreshold_ ? 0 :
std::exp(-1.0*lambda_*weight)*scale_;
1099 template<
class GRAPH,
class NODE_FEATURES_IN,
class EDGE_INDICATOR,
class NODE_FEATURES_OUT>
1102 const NODE_FEATURES_IN & nodeFeaturesIn,
1103 const EDGE_INDICATOR & edgeIndicator,
1105 const float edgeThreshold,
1107 NODE_FEATURES_OUT & nodeFeaturesOut
1109 detail_graph_smoothing::ExpSmoothFactor<float> functor(lambda,edgeThreshold,scale);
1110 detail_graph_smoothing::graphSmoothingImpl(g,nodeFeaturesIn,edgeIndicator,functor,nodeFeaturesOut);
1124 template<
class GRAPH,
class NODE_FEATURES_IN,
class EDGE_INDICATOR,
class NODE_FEATURES_OUT>
1127 const NODE_FEATURES_IN & nodeFeaturesIn,
1128 const EDGE_INDICATOR & edgeIndicator,
1130 const float edgeThreshold,
1133 NODE_FEATURES_OUT & nodeFeaturesBuffer,
1134 NODE_FEATURES_OUT & nodeFeaturesOut
1137 iterations = std::max(
size_t(1),iterations);
1139 graphSmoothing(g,nodeFeaturesIn,edgeIndicator,lambda,edgeThreshold,scale,nodeFeaturesOut);
1143 for(
size_t i=0;i<iterations;++i){
1145 graphSmoothing(g,nodeFeaturesOut,edgeIndicator,lambda,edgeThreshold,scale,nodeFeaturesBuffer);
1149 graphSmoothing(g,nodeFeaturesBuffer,edgeIndicator,lambda,edgeThreshold,scale,nodeFeaturesOut);
1154 copyNodeMap(g,nodeFeaturesBuffer,nodeFeaturesOut);
1159 template<
class GRAPH,
class NODE_MAP,
class EDGE_MAP>
1160 void nodeGtToEdgeGt(
1162 const NODE_MAP & nodeGt,
1163 const Int64 ignoreLabel,
1166 typedef typename GRAPH::Node Node;
1167 typedef typename GRAPH::EdgeIt EdgeIt;
1168 typedef typename GRAPH::Edge Edge;
1170 for(EdgeIt edgeIt(g); edgeIt!=lemon::INVALID; ++edgeIt){
1171 const Edge
edge(*edgeIt);
1172 const Node u = g.u(edge);
1173 const Node v = g.v(edge);
1175 const Int64 lU =
static_cast<Int64>(nodeGt[u]);
1176 const Int64 lV =
static_cast<Int64>(nodeGt[v]);
1178 if(ignoreLabel==-1 || (lU!=ignoreLabel || lV!=ignoreLabel)){
1179 edgeGt[
edge] = lU == lV ? 0 : 1;
1197 template<
class RAG,
class BASE_GRAPH,
class BASE_GRAPH_RAG_LABELS,
1198 class BASE_GRAPH_GT,
class RAG_GT,
class RAG_GT_QT>
1201 const BASE_GRAPH & baseGraph,
1202 const BASE_GRAPH_RAG_LABELS & baseGraphRagLabels,
1203 const BASE_GRAPH_GT & baseGraphGt,
1207 typedef typename BASE_GRAPH::Node BaseGraphNode;
1208 typedef typename BASE_GRAPH::NodeIt BaseGraphNodeIt;
1209 typedef typename RAG::NodeIt RagNodeIt;
1210 typedef typename RAG::Node RagNode;
1211 typedef typename BASE_GRAPH_RAG_LABELS::Value BaseRagLabelType;
1212 typedef typename BASE_GRAPH_GT::Value GtLabelType;
1213 typedef typename RAG_GT::Value RagGtLabelType;
1216 typedef std::map<GtLabelType,UInt32> MapType;
1217 typedef typename MapType::const_iterator MapIter;
1218 typedef typename RAG:: template NodeMap<MapType> Overlap;
1219 Overlap overlap(rag);
1223 for(BaseGraphNodeIt baseNodeIter(baseGraph); baseNodeIter!=lemon::INVALID; ++baseNodeIter , ++i ){
1229 const BaseGraphNode baseNode = *baseNodeIter;
1232 const GtLabelType gtLabel = baseGraphGt[baseNode];
1236 const BaseRagLabelType bgRagLabel = baseGraphRagLabels[baseNode];
1237 const RagNode ragNode = rag.nodeFromId(bgRagLabel);
1240 overlap[ragNode][gtLabel]+=1;
1244 for(RagNodeIt ragNodeIter(rag); ragNodeIter!=lemon::INVALID; ++ragNodeIter ){
1245 const RagNode ragNode = *ragNodeIter;
1246 const MapType olMap = overlap[ragNode];
1248 RagGtLabelType bestLabel = 0;
1249 for(MapIter olIter = olMap.begin(); olIter!=olMap.end(); ++olIter ){
1250 if(olIter->second > olSize){
1251 olSize = olIter->second;
1252 bestLabel = olIter->first;
1255 ragGt[ragNode]=bestLabel;
1268 template<
class RAGGRAPH,
class GRAPH,
class RAGEDGES,
unsigned int N,
class T>
1270 const RAGGRAPH & rag,
1271 const GRAPH & graph,
1272 const RAGEDGES & affiliatedEdges,
1274 const typename RAGGRAPH::Node & node
1276 typedef typename GRAPH::Node Node;
1277 typedef typename GRAPH::Edge Edge;
1278 typedef typename RAGGRAPH::OutArcIt RagOutArcIt;
1279 typedef typename RAGGRAPH::Edge RagEdge;
1280 typedef typename GraphDescriptorToMultiArrayIndex<GRAPH>::IntrinsicNodeMapShape NodeCoordinate;
1282 T nodeLabel = rag.id(node);
1285 std::set< NodeCoordinate > edgeCoordinates;
1286 for (RagOutArcIt iter(rag, node); iter != lemon::INVALID; ++iter)
1288 const RagEdge ragEdge(*iter);
1289 const std::vector<Edge> & affEdges = affiliatedEdges[ragEdge];
1290 for (
int i=0; i<affEdges.size(); ++i)
1292 Node u = graph.u(affEdges[i]);
1293 Node v = graph.v(affEdges[i]);
1294 T uLabel = labelsArray[u];
1295 T vLabel = labelsArray[v];
1297 NodeCoordinate coords;
1298 if (uLabel == nodeLabel)
1300 coords = GraphDescriptorToMultiArrayIndex<GRAPH>::intrinsicNodeCoordinate(graph, u);
1302 else if (vLabel == nodeLabel)
1304 coords = GraphDescriptorToMultiArrayIndex<GRAPH>::intrinsicNodeCoordinate(graph, v);
1308 vigra_precondition(
false,
"You should not come to this part of the code.");
1310 edgeCoordinates.insert(coords);
1318 typedef typename std::set< NodeCoordinate >::iterator setIter;
1319 for (setIter iter = edgeCoordinates.begin(); iter!=edgeCoordinates.end(); ++iter)
1321 NodeCoordinate coords = *iter;
1322 for (
int k=0; k<coords.size(); ++k)
1324 edgePoints(next, k) = coords[k];
1339 template<
unsigned int N,
class DirectedTag,
1340 class NODEMAP,
class EDGEMAP,
class FUNCTOR>
1344 const NODEMAP & nodeWeights,
1345 EDGEMAP & edgeWeights,
1347 FUNCTOR
const & func)
1350 typedef typename Graph::Edge Edge;
1351 typedef typename Graph::EdgeIt EdgeIt;
1354 vigra_precondition(nodeWeights.shape() == g.shape(),
1355 "edgeWeightsFromNodeWeights(): shape mismatch between graph and nodeWeights.");
1357 for (EdgeIt iter(g); iter!=lemon::INVALID; ++iter)
1359 const Edge
edge(*iter);
1360 const CoordType uCoord(g.
u(edge));
1361 const CoordType vCoord(g.
v(edge));
1364 edgeWeights[
edge] =
norm(uCoord-vCoord) * func(nodeWeights[uCoord], nodeWeights[vCoord]);
1368 edgeWeights[
edge] = func(nodeWeights[uCoord], nodeWeights[vCoord]);
1373 template<
unsigned int N,
class DirectedTag,
1374 class NODEMAP,
class EDGEMAP>
1378 const NODEMAP & nodeWeights,
1379 EDGEMAP & edgeWeights,
1380 bool euclidean=
false)
1397 template<
unsigned int N,
class DirectedTag,
1398 class T,
class EDGEMAP>
1403 EDGEMAP & edgeWeights,
1404 bool euclidean =
false)
1407 typedef typename Graph::Edge Edge;
1408 typedef typename Graph::EdgeIt EdgeIt;
1411 vigra_precondition(interpolatedImage.
shape() == 2*g.shape()-CoordType(1),
1412 "edgeWeightsFromInterpolatedImage(): interpolated shape must be shape*2-1");
1414 for (EdgeIt iter(g); iter!=lemon::INVALID; ++iter)
1416 const Edge
edge(*iter);
1417 const CoordType uCoord(g.
u(edge));
1418 const CoordType vCoord(g.
v(edge));
1421 edgeWeights[
edge] =
norm(uCoord-vCoord) * interpolatedImage[uCoord+vCoord];
1425 edgeWeights[
edge] = interpolatedImage[uCoord+vCoord];
1430 template<
class GRAPH>
1433 typedef typename GRAPH::Node Node;
1435 ThreeCycle(
const Node & a,
const Node & b,
const Node c){
1439 std::sort(nodes_, nodes_+3);
1441 bool operator < (
const ThreeCycle & other)
const{
1442 if(nodes_[0] < other.nodes_[0]){
1445 else if(nodes_[0] == other.nodes_[0]){
1446 if(nodes_[1] < other.nodes_[1]){
1449 else if(nodes_[1] == other.nodes_[1]){
1450 if(nodes_[2] < other.nodes_[2]){
1472 template<
class GRAPH>
1477 typedef typename GRAPH::Node Node;
1478 typedef typename GRAPH::Edge Edge;
1479 typedef typename GRAPH::EdgeIt EdgeIt;
1480 typedef typename GRAPH::OutArcIt OutArcIt;
1482 typedef ThreeCycle<GRAPH> Cycle;
1484 std::set< Cycle > cycles;
1485 typedef typename std::set<Cycle>::const_iterator SetIter;
1486 for (EdgeIt iter(g); iter!=lemon::INVALID; ++iter){
1487 const Edge
edge(*iter);
1488 const Node u = g.u(edge);
1489 const Node v = g.v(edge);
1492 for(OutArcIt outArcIt(g,u); outArcIt!=lemon::INVALID;++outArcIt){
1493 const Node w = g.target(*outArcIt);
1495 const Edge e = g.findEdge(w,v);
1496 if(e != lemon::INVALID){
1498 cycles.insert(Cycle(u, v, w));
1505 for(SetIter iter=cycles.begin(); iter!=cycles.end(); ++iter){
1507 const Cycle & c = *iter;
1508 for(
size_t j=0;j<3; ++j){
1509 cyclesArray(i)[j] = g.id(c.nodes_[j]);
1515 template<
class GRAPH>
1516 void find3CyclesEdges(
1520 typedef typename GRAPH::Node Node;
1521 typedef typename GRAPH::Edge Edge;
1522 typedef typename GRAPH::EdgeIt EdgeIt;
1523 typedef typename GRAPH::OutArcIt OutArcIt;
1525 typedef ThreeCycle<GRAPH> Cycle;
1527 std::set< Cycle > cycles;
1528 typedef typename std::set<Cycle>::const_iterator SetIter;
1529 for (EdgeIt iter(g); iter!=lemon::INVALID; ++iter){
1530 const Edge
edge(*iter);
1531 const Node u = g.u(edge);
1532 const Node v = g.v(edge);
1535 for(OutArcIt outArcIt(g,u); outArcIt!=lemon::INVALID;++outArcIt){
1536 const Node w = g.target(*outArcIt);
1538 const Edge e = g.findEdge(w,v);
1539 if(e != lemon::INVALID){
1541 cycles.insert(Cycle(u, v, w));
1548 for(SetIter iter=cycles.begin(); iter!=cycles.end(); ++iter){
1550 const Cycle & c = *iter;
1551 const Node u = c.nodes_[0];
1552 const Node v = c.nodes_[1];
1553 const Node w = c.nodes_[2];
1555 cyclesArray(i)[0] = g.id(g.findEdge(u, v));
1556 cyclesArray(i)[1] = g.id(g.findEdge(u, w));
1557 cyclesArray(i)[2] = g.id(g.findEdge(v, w));
1566 #endif // VIGRA_GRAPH_ALGORITHMS_HXX vigra::GridGraph< N, DirectedTag >::degree_size_type degree(typename vigra::GridGraph< N, DirectedTag >::vertex_descriptor const &v, vigra::GridGraph< N, DirectedTag > const &g)
Return total number of edges (incoming and outgoing) of vertex v (API: boost).
Definition: multi_gridgraph.hxx:2828
Define a grid graph in arbitrary dimensions.
Definition: multi_fwd.hxx:217
const PredecessorsMap & predecessors() const
get the predecessors node map (after a call of run)
Definition: graph_algorithms.hxx:442
void initMultiArrayBorder(...)
Write values to the specified border values in the array.
vigra::GridGraph< N, DirectedTag >::vertex_descriptor target(typename vigra::GridGraph< N, DirectedTag >::edge_descriptor const &e, vigra::GridGraph< N, DirectedTag > const &g)
Get a vertex descriptor for the end vertex of edge e in graph g (API: boost).
Definition: multi_gridgraph.hxx:2954
void run(Node const &start, Node const &stop, const WEIGHTS &weights, const Node &source, const Node &target=lemon::INVALID, WeightType maxDistance=NumericTraits< WeightType >::max())
run shortest path in a region of interest of a GridGraph.
Definition: graph_algorithms.hxx:356
void fillNodeMap(const G &g, A &a, const T &value)
fill a lemon node map
Definition: graph_algorithms.hxx:136
WeightType distance(const Node &target) const
get the distance to a rarget node (after a call of run)
Definition: graph_algorithms.hxx:452
linalg::TemporaryMatrix< T > exp(MultiArrayView< 2, T, C > const &v)
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.
Definition: graph_algorithms.hxx:1269
Heap-based priority queue compatible to BucketQueue.
Definition: priority_queue.hxx:290
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.
Definition: graph_algorithms.hxx:611
detail::GenericEdge< index_type > Edge
edge descriptor
Definition: adjacency_list_graph.hxx:249
Main MultiArray class containing the memory management.
Definition: multi_array.hxx:2422
const DistanceMap & distances() const
get the distances node map (after a call of run)
Definition: graph_algorithms.hxx:447
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
Definition: graph_algorithms.hxx:917
void edgeWeightsFromNodeWeights(const GridGraph< N, DirectedTag > &g, const NODEMAP &nodeWeights, EDGEMAP &edgeWeights, bool euclidean, FUNCTOR const &func)
create edge weights from node weights
Definition: graph_algorithms.hxx:1342
bool allLess(TinyVectorBase< V1, SIZE, D1, D2 > const &l, TinyVectorBase< V2, SIZE, D3, D4 > const &r)
pointwise less-than
Definition: tinyvector.hxx:1375
undirected adjacency list graph in the LEMON API
Definition: adjacency_list_graph.hxx:227
Definition: accessor.hxx:43
Node nodeFromId(const index_type id) const
Get node descriptor for given node ID i (API: LEMON). Return Node(lemon::INVALID) when the ID does no...
detail::SelectIntegerType< 64, detail::SignedIntTypes >::type Int64
64-bit signed int
Definition: sized_int.hxx:177
const DiscoveryOrder & discoveryOrder() const
get an array with all visited nodes, sorted by distance from source
Definition: graph_algorithms.hxx:437
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
Definition: graph_algorithms.hxx:1125
FFTWComplex< R >::NormType norm(const FFTWComplex< R > &a)
norm (= magnitude)
Definition: fftw3.hxx:1037
const Node & source() const
get the source node
Definition: graph_algorithms.hxx:423
shortest path computer
Definition: graph_algorithms.hxx:297
const Graph & graph() const
get the graph
Definition: graph_algorithms.hxx:419
Definition: inspectimage.hxx:255
void copyNodeMap(const G &g, const A &a, B &b)
copy a lemon node map
Definition: graph_algorithms.hxx:117
const difference_type & shape() const
Definition: multi_array.hxx:1596
MultiArray & init(const U &init)
Definition: multi_array.hxx:2799
void edgeWeightsFromInterpolatedImage(const GridGraph< N, DirectedTag > &g, const MultiArrayView< N, T > &interpolatedImage, EDGEMAP &edgeWeights, bool euclidean=false)
create edge weights from an interpolated image
Definition: graph_algorithms.hxx:1400
Edge findEdge(const Node &a, const Node &b) const
Get a descriptor for the edge connecting vertices u and v, or lemon::INVALID if no such edge exists (...
vigra::GridGraph< N, DirectedTag >::vertex_descriptor source(typename vigra::GridGraph< N, DirectedTag >::edge_descriptor const &e, vigra::GridGraph< N, DirectedTag > const &g)
Get a vertex descriptor for the start vertex of edge e in graph g (API: boost).
Definition: multi_gridgraph.hxx:2943
const Node & target() const
get the target node
Definition: graph_algorithms.hxx:427
void runMultiSource(const WEIGHTS &weights, ITER source_begin, ITER source_end, const Node &target=lemon::INVALID, WeightType maxDistance=NumericTraits< WeightType >::max())
run shortest path with given edge weights from multiple sources.
Definition: graph_algorithms.hxx:391
void copyEdgeMap(const G &g, const A &a, B &b)
copy a lemon edge map
Definition: graph_algorithms.hxx:127
size_t pathLength(const NODE source, const NODE target, const PREDECESSORS &predecessors)
get the length in node units of a path
Definition: graph_algorithms.hxx:591
Class for fixed size vectors.This class contains an array of size SIZE of the specified VALUETYPE...
Definition: accessor.hxx:940
void fillEdgeMap(const G &g, A &a, const T &value)
fill a lemon edge map
Definition: graph_algorithms.hxx:145
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
Definition: graph_algorithms.hxx:165
void edgeSort(const GRAPH &g, const WEIGHTS &weights, const COMPERATOR &comperator, std::vector< typename GRAPH::Edge > &sortedEdges)
get a vector of Edge descriptors
Definition: graph_algorithms.hxx:98
std::pair< typename vigra::GridGraph< N, DirectedTag >::edge_descriptor, bool > edge(typename vigra::GridGraph< N, DirectedTag >::vertex_descriptor const &u, typename vigra::GridGraph< N, DirectedTag >::vertex_descriptor const &v, vigra::GridGraph< N, DirectedTag > const &g)
Return the pair (edge_descriptor, true) when an edge between vertices u and v exists, or (lemon::INVALID, false) otherwise (API: boost).
Definition: multi_gridgraph.hxx:2990
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)
Definition: graph_algorithms.hxx:1199
MultiArrayShape< 2 >::type Shape2
shape type for MultiArray<2, T>
Definition: multi_shape.hxx:254
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
Definition: graph_algorithms.hxx:893
bool operator<(FixedPoint< IntBits1, FracBits1 > l, FixedPoint< IntBits2, FracBits2 > r)
less than
Definition: fixedpoint.hxx:512
void edgeWeightedWatershedsSegmentation(const GRAPH &g, const EDGE_WEIGHTS &edgeWeights, const SEEDS &seeds, LABELS &labels)
edge weighted watersheds Segmentataion
Definition: graph_algorithms.hxx:872
void runMultiSource(const EFGE_WEIGHTS &edgeWeights, const NODE_WEIGHTS &nodeWeights, ITER source_begin, ITER source_end, const Node &target=lemon::INVALID, WeightType maxDistance=NumericTraits< WeightType >::max())
run shortest path with given edge weights from multiple sources.
Definition: graph_algorithms.hxx:406
detail::SelectIntegerType< 32, detail::UnsignedIntTypes >::type UInt32
32-bit unsigned int
Definition: sized_int.hxx:183
Base class for, and view to, vigra::MultiArray.
Definition: multi_array.hxx:652
Node v(Edge const &e) const
Get the end node of the given edge e (API: LEMON, the boost::graph API provides the free function bo...
Definition: multi_gridgraph.hxx:2390
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
Definition: graph_algorithms.hxx:1100
bool allLessEqual(TinyVectorBase< V1, SIZE, D1, D2 > const &l, TinyVectorBase< V2, SIZE, D3, D4 > const &r)
pointwise less-equal
Definition: tinyvector.hxx:1399
void run(const WEIGHTS &weights, const Node &source, const Node &target=lemon::INVALID, WeightType maxDistance=NumericTraits< WeightType >::max())
run shortest path given edge weights
Definition: graph_algorithms.hxx:334
Node u(Edge const &e) const
Get the start node of the given edge e (API: LEMON, the boost::graph API provides the free function ...
Definition: multi_gridgraph.hxx:2382
void reRun(const WEIGHTS &weights, const Node &source, const Node &target=lemon::INVALID, WeightType maxDistance=NumericTraits< WeightType >::max())
run shortest path again with given edge weights
Definition: graph_algorithms.hxx:377
detail_adjacency_list_graph::ItemIter< GraphType, Edge > EdgeIt
edge iterator
Definition: adjacency_list_graph.hxx:253
ShortestPathDijkstra(const Graph &g)
\ brief constructor from graph
Definition: graph_algorithms.hxx:313
bool hasTarget() const
check if explicit target is given
Definition: graph_algorithms.hxx:432