40 #ifndef VIGRA_GRAPH_ALGORITHMS_HXX
41 #define VIGRA_GRAPH_ALGORITHMS_HXX
51 #include "graph_generalization.hxx"
52 #include "multi_gridgraph.hxx"
53 #include "priority_queue.hxx"
54 #include "union_find.hxx"
55 #include "adjacency_list_graph.hxx"
56 #include "graph_maps.hxx"
57 #include "functorexpression.hxx"
58 #include "array_vector.hxx"
66 namespace detail_graph_algorithms{
67 template <
class GRAPH_MAP,
class COMPERATOR>
68 struct GraphItemCompare
71 GraphItemCompare(
const GRAPH_MAP & map,
const COMPERATOR & comperator)
73 comperator_(comperator){
78 bool operator()(
const KEY & a,
const KEY & b)
const{
79 return comperator_(map_[a],map_[b]);
82 const GRAPH_MAP & map_;
83 const COMPERATOR & comperator_;
91 template<
class GRAPH,
class WEIGHTS,
class COMPERATOR>
94 const WEIGHTS & weights,
95 const COMPERATOR & comperator,
96 std::vector<typename GRAPH::Edge> & sortedEdges
98 sortedEdges.resize(g.edgeNum());
100 for(
typename GRAPH::EdgeIt e(g);e!=lemon::INVALID;++e){
104 detail_graph_algorithms::GraphItemCompare<WEIGHTS,COMPERATOR> edgeComperator(weights,comperator);
105 std::sort(sortedEdges.begin(),sortedEdges.end(),edgeComperator);
110 template<
class G,
class A,
class B>
112 typename G::NodeIt iter(g);
113 while(iter!=lemon::INVALID){
120 template<
class G,
class A,
class B>
122 typename G::EdgeIt iter(g);
123 while(iter!=lemon::INVALID){
129 template<
class G,
class A,
class T>
131 typename G::NodeIt iter(g);
132 while(iter!=lemon::INVALID){
138 template<
class G,
class A,
class T>
140 typename G::EdgeIt iter(g);
141 while(iter!=lemon::INVALID){
157 class GRAPH_IN_NODE_LABEL_MAP
161 GRAPH_IN_NODE_LABEL_MAP labels,
163 typename AdjacencyListGraph:: template EdgeMap< std::vector<typename GRAPH_IN::Edge> > & affiliatedEdges,
164 const Int64 ignoreLabel=-1
167 typedef typename GraphMapTypeTraits<GRAPH_IN_NODE_LABEL_MAP>::Value LabelType;
168 typedef GRAPH_IN GraphIn;
171 typedef typename GraphIn::Edge EdgeGraphIn;
172 typedef typename GraphIn::NodeIt NodeItGraphIn;
173 typedef typename GraphIn::EdgeIt EdgeItGraphIn;
175 typedef typename GraphOut::Edge EdgeGraphOut;
176 for(NodeItGraphIn iter(graphIn);iter!=lemon::INVALID;++iter){
177 const LabelType l=labels[*iter];
178 if(ignoreLabel==-1 || static_cast<Int64>(l)!=ignoreLabel)
183 for(EdgeItGraphIn e(graphIn);e!=lemon::INVALID;++e){
184 const EdgeGraphIn
edge(*e);
185 const LabelType lu = labels[graphIn.u(edge)];
186 const LabelType lv = labels[graphIn.v(edge)];
187 if( lu!=lv && ( ignoreLabel==-1 || (static_cast<Int64>(lu)!=ignoreLabel && static_cast<Int64>(lv)!=ignoreLabel) ) ){
193 affiliatedEdges.assign(rag);
195 for(EdgeItGraphIn e(graphIn);e!=lemon::INVALID;++e){
196 const EdgeGraphIn
edge(*e);
197 const LabelType lu = labels[graphIn.u(edge)];
198 const LabelType lv = labels[graphIn.v(edge)];
200 if( lu!=lv && ( ignoreLabel==-1 || (static_cast<Int64>(lu)!=ignoreLabel && static_cast<Int64>(lv)!=ignoreLabel) ) ){
204 affiliatedEdges[ragEdge].push_back(edge);
211 template<
class GRAPH,
class WEIGHT_TYPE>
216 typedef typename Graph::Node Node;
217 typedef typename Graph::NodeIt NodeIt;
218 typedef typename Graph::Edge Edge;
219 typedef typename Graph::OutArcIt OutArcIt;
221 typedef WEIGHT_TYPE WeightType;
223 typedef typename Graph:: template NodeMap<Node> PredecessorsMap;
224 typedef typename Graph:: template NodeMap<WeightType> DistanceMap;
230 pq_(g.maxNodeId()+1),
248 template<
class WEIGHTS>
250 const Node &
target = lemon::INVALID,
251 WeightType maxDistance=NumericTraits<WeightType>::max())
253 this->initializeMaps(source);
254 runImpl(weights,
target, maxDistance);
270 template<
class WEIGHTS>
271 void run(Node
const & start, Node
const & stop,
272 const WEIGHTS & weights,
const Node & source,
273 const Node &
target = lemon::INVALID,
274 WeightType maxDistance=NumericTraits<WeightType>::max())
277 "ShortestPathDijkstra::run(): source is not within ROI");
278 vigra_precondition(
target == lemon::INVALID ||
280 "ShortestPathDijkstra::run(): target is not within ROI");
281 this->initializeMaps(source, start, stop);
282 runImpl(weights,
target, maxDistance);
291 template<
class WEIGHTS>
292 void reRun(
const WEIGHTS & weights,
const Node & source,
293 const Node &
target = lemon::INVALID,
294 WeightType maxDistance=NumericTraits<WeightType>::max())
296 this->reInitializeMaps(source);
297 runImpl(weights,
target, maxDistance);
304 template<
class WEIGHTS,
class ITER>
307 const Node &
target = lemon::INVALID,
308 WeightType maxDistance=NumericTraits<WeightType>::max())
310 this->initializeMapsMultiSource(source_begin, source_end);
311 runImpl(weights,
target, maxDistance);
329 return target_!=lemon::INVALID;
334 return discoveryOrder_;
355 template<
class WEIGHTS>
356 void runImpl(
const WEIGHTS & weights,
357 const Node &
target = lemon::INVALID,
358 WeightType maxDistance=NumericTraits<WeightType>::max())
360 target_ = lemon::INVALID;
361 while(!pq_.
empty() ){
362 const Node topNode(graph_.nodeFromId(pq_.
top()));
363 if(distMap_[topNode] > maxDistance)
366 discoveryOrder_.push_back(topNode);
370 for(OutArcIt outArcIt(graph_,topNode);outArcIt!=lemon::INVALID;++outArcIt){
371 const Node otherNode = graph_.target(*outArcIt);
372 const size_t otherNodeId = graph_.id(otherNode);
375 const Edge
edge(*outArcIt);
376 const WeightType currentDist = distMap_[otherNode];
377 const WeightType alternativeDist = distMap_[topNode]+weights[
edge];
378 if(alternativeDist<currentDist){
379 pq_.
push(otherNodeId,alternativeDist);
380 distMap_[otherNode]=alternativeDist;
381 predMap_[otherNode]=topNode;
384 else if(predMap_[otherNode]==lemon::INVALID){
385 const Edge
edge(*outArcIt);
386 const WeightType initialDist = distMap_[topNode]+weights[
edge];
387 if(initialDist<=maxDistance)
389 pq_.
push(otherNodeId,initialDist);
390 distMap_[otherNode]=initialDist;
391 predMap_[otherNode]=topNode;
396 while(!pq_.
empty() ){
397 const Node topNode(graph_.nodeFromId(pq_.
top()));
398 predMap_[topNode]=lemon::INVALID;
402 target_ = discoveryOrder_.
back();
406 void initializeMaps(Node
const & source){
407 for(NodeIt n(graph_); n!=lemon::INVALID; ++n){
409 predMap_[node]=lemon::INVALID;
411 distMap_[
source]=
static_cast<WeightType
>(0.0);
413 discoveryOrder_.clear();
414 pq_.
push(graph_.id(source),0.0);
418 void initializeMaps(Node
const & source,
419 Node
const & start, Node
const & stop)
421 Node left_border = min(start, Node(1)),
422 right_border = min(predMap_.shape()-stop, Node(1)),
423 DONT_TOUCH = Node(lemon::INVALID) - Node(1);
426 left_border, right_border, DONT_TOUCH);
427 predMap_.subarray(start, stop) = lemon::INVALID;
430 distMap_[
source]=
static_cast<WeightType
>(0.0);
431 discoveryOrder_.clear();
432 pq_.
push(graph_.id(source),0.0);
436 template <
class ITER>
437 void initializeMapsMultiSource(ITER source, ITER source_end){
438 for(NodeIt n(graph_); n!=lemon::INVALID; ++n){
440 predMap_[node]=lemon::INVALID;
442 discoveryOrder_.clear();
443 for( ; source != source_end; ++
source)
445 distMap_[*
source]=
static_cast<WeightType
>(0.0);
447 pq_.
push(graph_.id(*source),0.0);
449 source_=lemon::INVALID;
452 void reInitializeMaps(Node
const & source){
453 for(
unsigned int n=0; n<discoveryOrder_.
size(); ++n){
454 predMap_[discoveryOrder_[n]]=lemon::INVALID;
456 distMap_[
source]=
static_cast<WeightType
>(0.0);
458 discoveryOrder_.clear();
459 pq_.
push(graph_.id(source),0.0);
463 const Graph & graph_;
465 PredecessorsMap predMap_;
466 DistanceMap distMap_;
467 DiscoveryOrder discoveryOrder_;
474 template<
class NODE,
class PREDECESSORS>
478 const PREDECESSORS & predecessors
480 if(predecessors[target]==lemon::INVALID)
483 NODE currentNode = target;
485 while(currentNode!=source){
486 currentNode=predecessors[currentNode];
496 template<
class GRAPH,
class WEIGHTS,
class PREDECESSORS,
class DISTANCE,
class HEURSTIC>
499 const typename GRAPH::Node & source,
500 const typename GRAPH::Node & target,
501 const WEIGHTS & weights,
502 PREDECESSORS & predecessors,
504 const HEURSTIC & heuristic
508 typedef typename Graph::Edge Edge;
509 typedef typename Graph::Node Node;
510 typedef typename Graph::NodeIt NodeIt;
511 typedef typename Graph::OutArcIt OutArcIt;
512 typedef typename DISTANCE::value_type DistanceType;
514 typename GRAPH:: template NodeMap<bool> closedSet(graph);
517 for(NodeIt n(graph);n!=lemon::INVALID;++n){
519 closedSet[node]=
false;
520 distance[node]=std::numeric_limits<DistanceType>::infinity();
521 predecessors[node]=lemon::INVALID;
524 distance[source]=
static_cast<DistanceType
>(0.0);
525 estimatedDistanceOpenSet.push(graph.id(source),heuristic(source,target));
528 while(!estimatedDistanceOpenSet.empty()){
531 const Node current = graph.nodeFromId(estimatedDistanceOpenSet.top());
539 estimatedDistanceOpenSet.pop();
540 closedSet[current]=
true;
543 for(OutArcIt outArcIt(graph,current);outArcIt!=lemon::INVALID;++outArcIt){
546 const Node neighbour = graph.target(*outArcIt);
547 const size_t neighbourId = graph.id(neighbour);
550 if(!closedSet[neighbour]){
553 const Edge
edge(*outArcIt);
556 const DistanceType tenativeScore = distance[current] + weights[
edge];
559 if(!estimatedDistanceOpenSet.contains(neighbourId) || tenativeScore < distance[neighbour] ){
561 predecessors[neighbour]=current;
562 distance[neighbour]=tenativeScore;
566 estimatedDistanceOpenSet.push(neighbourId,distance[neighbour]+heuristic(neighbour,target));
574 namespace detail_watersheds_segmentation{
576 struct RawPriorityFunctor{
577 template<
class L,
class T>
578 T operator()(
const L label,
const T priority)
const{
583 template<
class PRIORITY_TYPE,
class LABEL_TYPE>
584 struct CarvingFunctor{
585 CarvingFunctor(
const LABEL_TYPE backgroundLabel,
const PRIORITY_TYPE & factor)
586 : backgroundLabel_(backgroundLabel),
589 PRIORITY_TYPE operator()(
const LABEL_TYPE label,
const PRIORITY_TYPE priority)
const{
590 return (label==backgroundLabel_ ? priority*factor_ : priority);
592 LABEL_TYPE backgroundLabel_;
593 PRIORITY_TYPE factor_;
597 template<
class GRAPH,
class EDGE_WEIGHTS,
class SEEDS,
class PRIORITY_MANIP_FUNCTOR,
class LABELS>
598 void edgeWeightedWatershedsSegmentationImpl(
600 const EDGE_WEIGHTS & edgeWeights,
602 PRIORITY_MANIP_FUNCTOR & priorManipFunctor,
606 typedef typename Graph::Edge Edge;
607 typedef typename Graph::Node Node;
608 typedef typename Graph::NodeIt NodeIt;
609 typedef typename Graph::OutArcIt OutArcIt;
611 typedef typename EDGE_WEIGHTS::Value WeightType;
612 typedef typename LABELS::Value LabelType;
613 typedef typename Graph:: template NodeMap<bool> NodeBoolMap;
614 typedef PriorityQueue<Node,WeightType,true> PQ;
622 for(NodeIt n(g);n!=lemon::INVALID;++n){
624 if(labels[node]!=static_cast<LabelType>(0)){
626 for(OutArcIt a(g,node);a!=lemon::INVALID;++a){
628 const Node neigbour=g.target(*a);
630 if(labels[neigbour]==static_cast<LabelType>(0) && !inPQ[neigbour]){
631 const WeightType priority = priorManipFunctor(labels[node],edgeWeights[
edge]);
632 pq.push(neigbour,priority);
643 const Node node = pq.top();
644 const LabelType label = labels[node];
647 throw std::runtime_error(
"seems like there are no seeds at all");
651 bool moreThanOneLabel =
false;
652 LabelType labelFound = 0 ;
653 for(OutArcIt a(g,node);a!=lemon::INVALID;++a){
655 const Node neigbour=g.target(*a);
656 if(labels[neigbour]!=static_cast<LabelType>(0)){
658 labelFound=labels[neigbour];
661 moreThanOneLabel=
true;
666 if(labelFound!=0 && !moreThanOneLabel ){
667 labels[node]=labelFound;
668 for(OutArcIt a(g,node);a!=lemon::INVALID;++a){
670 const Node neigbour=g.target(*a);
671 if(labels[neigbour]==static_cast<LabelType>(0)){
673 const WeightType priority = priorManipFunctor(labelFound,edgeWeights[
edge]);
674 pq.push(neigbour,edgeWeights[
edge]);
683 for(NodeIt n(g);n!=lemon::INVALID;++n){
685 if(labels[node]==static_cast<LabelType>(0)){
687 WeightType minWeight = std::numeric_limits<WeightType>::infinity();
688 LabelType minWeightLabel =
static_cast<LabelType
>(0);
689 for(OutArcIt a(g,node);a!=lemon::INVALID;++a){
691 const Node neigbour=g.target(*a);
692 const WeightType priority = priorManipFunctor(labels[neigbour],edgeWeights[
edge]);
693 if(labels[neigbour]!=0 && priority<minWeight){
695 minWeightLabel=labels[neigbour];
698 labels[node]=minWeightLabel;
713 template<
class GRAPH,
class EDGE_WEIGHTS,
class SEEDS,
class LABELS>
716 const EDGE_WEIGHTS & edgeWeights,
720 detail_watersheds_segmentation::RawPriorityFunctor f;
721 detail_watersheds_segmentation::edgeWeightedWatershedsSegmentationImpl(g,edgeWeights,seeds,f,labels);
732 template<
class GRAPH,
class EDGE_WEIGHTS,
class SEEDS,
class LABELS>
735 const EDGE_WEIGHTS & edgeWeights,
737 const typename LABELS::Value backgroundLabel,
738 const typename EDGE_WEIGHTS::Value backgroundBias,
741 typedef typename EDGE_WEIGHTS::Value WeightType;
742 typedef typename LABELS::Value LabelType;
743 detail_watersheds_segmentation::CarvingFunctor<WeightType,LabelType> f(backgroundLabel,backgroundBias);
744 detail_watersheds_segmentation::edgeWeightedWatershedsSegmentationImpl(g,edgeWeights,seeds,f,labels);
756 template<
class GRAPH ,
class EDGE_WEIGHTS,
class NODE_SIZE,
class NODE_LABEL_MAP>
759 const EDGE_WEIGHTS & edgeWeights,
760 const NODE_SIZE & nodeSizes,
762 NODE_LABEL_MAP & nodeLabeling,
763 const int nodeNumStopCond = -1
766 typedef typename Graph::Edge Edge;
767 typedef typename Graph::Node Node;
769 typedef typename EDGE_WEIGHTS::Value WeightType;
770 typedef typename EDGE_WEIGHTS::Value NodeSizeType;
771 typedef typename Graph:: template NodeMap<WeightType> NodeIntDiffMap;
772 typedef typename Graph:: template NodeMap<NodeSizeType> NodeSizeAccMap;
775 NodeIntDiffMap internalDiff(graph);
776 NodeSizeAccMap nodeSizeAcc(graph);
778 fillNodeMap(graph,internalDiff,static_cast<WeightType>(0.0));
785 std::vector<Edge> sortedEdges;
786 std::less<WeightType> comperator;
787 edgeSort(graph,edgeWeights,comperator,sortedEdges);
790 UnionFindArray<UInt64> ufdArray(graph.maxNodeId()+1);
793 size_t nodeNum = graph.nodeNum();
798 for(
size_t i=0;i<sortedEdges.size();++i){
799 const Edge e = sortedEdges[i];
800 const size_t rui = ufdArray.findIndex(graph.id(graph.u(e)));
801 const size_t rvi = ufdArray.findIndex(graph.id(graph.v(e)));
802 const Node ru = graph.nodeFromId(rui);
803 const Node rv = graph.nodeFromId(rvi);
807 const WeightType w = edgeWeights[e];
808 const NodeSizeType sizeRu = nodeSizeAcc[ru];
809 const NodeSizeType sizeRv = nodeSizeAcc[rv];
810 const WeightType tauRu =
static_cast<WeightType
>(k)/static_cast<WeightType>(sizeRu);
811 const WeightType tauRv =
static_cast<WeightType
>(k)/static_cast<WeightType>(sizeRv);
812 const WeightType minIntDiff = std::min(internalDiff[ru]+tauRu,internalDiff[rv]+tauRv);
815 ufdArray.makeUnion(rui,rvi);
818 const size_t newRepId = ufdArray.findIndex(rui);
819 const Node newRepNode = graph.nodeFromId(newRepId);
820 internalDiff[newRepNode]=w;
821 nodeSizeAcc[newRepNode] = sizeRu+sizeRv;
824 if(nodeNum==nodeNumStopCond){
828 if(nodeNumStopCond==-1){
832 if(nodeNum>nodeNumStopCond){
840 ufdArray.makeContiguous();
841 for(
typename GRAPH::NodeIt n(graph);n!=lemon::INVALID;++n){
843 nodeLabeling[node]=ufdArray.findLabel(graph.id(node));
850 namespace detail_graph_smoothing{
854 class NODE_FEATURES_IN,
856 class WEIGHTS_TO_SMOOTH_FACTOR,
857 class NODE_FEATURES_OUT
859 void graphSmoothingImpl(
861 const NODE_FEATURES_IN & nodeFeaturesIn,
862 const EDGE_WEIGHTS & edgeWeights,
863 WEIGHTS_TO_SMOOTH_FACTOR & weightsToSmoothFactor,
864 NODE_FEATURES_OUT & nodeFeaturesOut
868 typedef typename Graph::Edge Edge;
869 typedef typename Graph::Node Node;
870 typedef typename Graph::NodeIt NodeIt;
871 typedef typename Graph::OutArcIt OutArcIt;
873 typedef typename NODE_FEATURES_IN::Value NodeFeatureInValue;
874 typedef typename NODE_FEATURES_OUT::Reference NodeFeatureOutRef;
875 typedef typename EDGE_WEIGHTS::ConstReference SmoothFactorType;
880 for(NodeIt n(g);n!=lemon::INVALID;++n){
884 NodeFeatureInValue featIn = nodeFeaturesIn[node];
885 NodeFeatureOutRef featOut = nodeFeaturesOut[node];
888 float weightSum = 0.0;
890 for(OutArcIt a(g,node);a!=lemon::INVALID;++a){
892 const Node neigbour(g.target(*a));
893 SmoothFactorType smoothFactor= weightsToSmoothFactor(edgeWeights[
edge]);
895 NodeFeatureInValue neighbourFeat = nodeFeaturesIn[neigbour];
896 neighbourFeat*=smoothFactor;
898 featOut = neighbourFeat;
900 featOut += neighbourFeat;
901 weightSum+=smoothFactor;
905 featIn*=
static_cast<float>(degree);
906 weightSum+=
static_cast<float>(degree);
913 struct ExpSmoothFactor{
914 ExpSmoothFactor(
const T lambda,
const T edgeThreshold,
const T scale)
916 edgeThreshold_(edgeThreshold),
919 T operator()(
const T weight){
920 return weight> edgeThreshold_ ? 0 :
std::exp(-1.0*lambda_*weight)*scale_;
939 template<
class GRAPH,
class NODE_FEATURES_IN,
class EDGE_INDICATOR,
class NODE_FEATURES_OUT>
942 const NODE_FEATURES_IN & nodeFeaturesIn,
943 const EDGE_INDICATOR & edgeIndicator,
945 const float edgeThreshold,
947 NODE_FEATURES_OUT & nodeFeaturesOut
949 detail_graph_smoothing::ExpSmoothFactor<float> functor(lambda,edgeThreshold,scale);
950 detail_graph_smoothing::graphSmoothingImpl(g,nodeFeaturesIn,edgeIndicator,functor,nodeFeaturesOut);
964 template<
class GRAPH,
class NODE_FEATURES_IN,
class EDGE_INDICATOR,
class NODE_FEATURES_OUT>
967 const NODE_FEATURES_IN & nodeFeaturesIn,
968 const EDGE_INDICATOR & edgeIndicator,
970 const float edgeThreshold,
973 NODE_FEATURES_OUT & nodeFeaturesBuffer,
974 NODE_FEATURES_OUT & nodeFeaturesOut
977 iterations = std::max(
size_t(1),iterations);
979 graphSmoothing(g,nodeFeaturesIn,edgeIndicator,lambda,edgeThreshold,scale,nodeFeaturesOut);
983 for(
size_t i=0;i<iterations;++i){
985 graphSmoothing(g,nodeFeaturesOut,edgeIndicator,lambda,edgeThreshold,scale,nodeFeaturesBuffer);
989 graphSmoothing(g,nodeFeaturesBuffer,edgeIndicator,lambda,edgeThreshold,scale,nodeFeaturesOut);
1003 template<
class RAG,
class BASE_GRAPH,
class BASE_GRAPH_RAG_LABELS,
1004 class BASE_GRAPH_GT,
class RAG_GT,
class RAG_GT_QT>
1007 const BASE_GRAPH & baseGraph,
1008 const BASE_GRAPH_RAG_LABELS & baseGraphRagLabels,
1009 const BASE_GRAPH_GT & baseGraphGt,
1013 typedef typename BASE_GRAPH::Node BaseGraphNode;
1014 typedef typename BASE_GRAPH::NodeIt BaseGraphNodeIt;
1015 typedef typename RAG::NodeIt RagNodeIt;
1016 typedef typename RAG::Node RagNode;
1017 typedef typename BASE_GRAPH_RAG_LABELS::Value BaseRagLabelType;
1018 typedef typename BASE_GRAPH_GT::Value GtLabelType;
1019 typedef typename RAG_GT::Value RagGtLabelType;
1022 typedef std::map<GtLabelType,UInt32> MapType;
1023 typedef typename MapType::const_iterator MapIter;
1024 typedef typename RAG:: template NodeMap<MapType> Overlap;
1025 Overlap overlap(rag);
1027 for(BaseGraphNodeIt baseNodeIter(baseGraph); baseNodeIter!=lemon::INVALID; ++baseNodeIter ){
1029 const BaseGraphNode baseNode = *baseNodeIter;
1032 const GtLabelType gtLabel = baseGraphGt[baseNode];
1036 const BaseRagLabelType bgRagLabel = baseGraphRagLabels[baseNode];
1037 const RagNode ragNode = rag.nodeFromId(bgRagLabel);
1040 overlap[ragNode][gtLabel]+=1;
1044 for(RagNodeIt ragNodeIter(rag); ragNodeIter!=lemon::INVALID; ++ragNodeIter ){
1045 const RagNode ragNode = *ragNodeIter;
1046 const MapType olMap = overlap[ragNode];
1048 RagGtLabelType bestLabel = 0;
1049 for(MapIter olIter = olMap.begin(); olIter!=olMap.end(); ++olIter ){
1050 if(olIter->second > olSize){
1051 olSize = olIter->second;
1052 bestLabel = olIter->first;
1055 ragGt[ragNode]=bestLabel;
1068 template<
unsigned int N,
class DirectedTag,
1069 class NODEMAP,
class EDGEMAP,
class FUNCTOR>
1073 const NODEMAP & nodeWeights,
1074 EDGEMAP & edgeWeights,
1076 FUNCTOR
const & func)
1079 typedef typename Graph::Edge Edge;
1080 typedef typename Graph::EdgeIt EdgeIt;
1083 vigra_precondition(nodeWeights.shape() == g.shape(),
1084 "edgeWeightsFromNodeWeights(): shape mismatch between graph and nodeWeights.");
1086 for (EdgeIt iter(g); iter!=lemon::INVALID; ++iter)
1088 const Edge
edge(*iter);
1089 const CoordType uCoord(g.
u(edge));
1090 const CoordType vCoord(g.
v(edge));
1093 edgeWeights[
edge] =
norm(uCoord-vCoord) * func(nodeWeights[uCoord], nodeWeights[vCoord]);
1097 edgeWeights[
edge] = func(nodeWeights[uCoord], nodeWeights[vCoord]);
1102 template<
unsigned int N,
class DirectedTag,
1103 class NODEMAP,
class EDGEMAP>
1106 const GridGraph<N, DirectedTag> & g,
1107 const NODEMAP & nodeWeights,
1108 EDGEMAP & edgeWeights,
1109 bool euclidean=
false)
1111 using namespace vigra::functor;
1126 template<
unsigned int N,
class DirectedTag,
1127 class T,
class EDGEMAP>
1132 EDGEMAP & edgeWeights,
1133 bool euclidean =
false)
1136 typedef typename Graph::Edge Edge;
1137 typedef typename Graph::EdgeIt EdgeIt;
1140 vigra_precondition(interpolatedImage.
shape() == 2*g.shape()-CoordType(1),
1141 "edgeWeightsFromInterpolatedImage(): interpolated shape must be shape*2-1");
1143 for (EdgeIt iter(g); iter!=lemon::INVALID; ++iter)
1145 const Edge
edge(*iter);
1146 const CoordType uCoord(g.
u(edge));
1147 const CoordType vCoord(g.
v(edge));
1150 edgeWeights[
edge] =
norm(uCoord-vCoord) * interpolatedImage[uCoord+vCoord];
1154 edgeWeights[
edge] = interpolatedImage[uCoord+vCoord];
1163 #endif // VIGRA_GRAPH_ALGORITHMS_HXX