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

hierarchical_clustering.hxx |

1 /************************************************************************/
2 /* */
3 /* Copyright 2011 by Ullrich Koethe */
4 /* */
5 /* This file is part of the VIGRA computer vision library. */
6 /* The VIGRA Website is */
7 /* http://hci.iwr.uni-heidelberg.de/vigra/ */
8 /* Please direct questions, bug reports, and contributions to */
9 /* ullrich.koethe@iwr.uni-heidelberg.de or */
10 /* vigra@informatik.uni-hamburg.de */
11 /* */
12 /* Permission is hereby granted, free of charge, to any person */
13 /* obtaining a copy of this software and associated documentation */
14 /* files (the "Software"), to deal in the Software without */
15 /* restriction, including without limitation the rights to use, */
16 /* copy, modify, merge, publish, distribute, sublicense, and/or */
17 /* sell copies of the Software, and to permit persons to whom the */
18 /* Software is furnished to do so, subject to the following */
19 /* conditions: */
20 /* */
21 /* The above copyright notice and this permission notice shall be */
22 /* included in all copies or substantial portions of the */
23 /* Software. */
24 /* */
25 /* THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND */
26 /* EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES */
27 /* OF MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND */
28 /* NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT */
29 /* HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, */
30 /* WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING */
31 /* FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR */
32 /* OTHER DEALINGS IN THE SOFTWARE. */
33 /* */
34 /************************************************************************/
35
36
37
38 #ifndef VIGRA_HIERARCHICAL_CLUSTERING_HXX
39 #define VIGRA_HIERARCHICAL_CLUSTERING_HXX
40
41
42
43 /*std*/
44 #include <queue>
45 #include <iomanip>
46
47 /*vigra*/
48 #include "priority_queue.hxx"
49 #include "metrics.hxx"
50
51 namespace vigra{
52
53 namespace cluster_operators{
54
55 template<
56 class MERGE_GRAPH,
57 class EDGE_INDICATOR_MAP,
58 class EDGE_SIZE_MAP,
59 class NODE_SIZE_MAP,
60 class MIN_WEIGHT_MAP
61 >
62 class EdgeWeightedUcm
63 {
64 typedef EdgeWeightedUcm<
65 MERGE_GRAPH,
66 EDGE_INDICATOR_MAP,
67 EDGE_SIZE_MAP,
68 NODE_SIZE_MAP,
69 MIN_WEIGHT_MAP
70 > SelfType;
71
72 public:
73
74 typedef typename EDGE_INDICATOR_MAP::Value ValueType;
75 typedef ValueType WeightType;
76 typedef MERGE_GRAPH MergeGraph;
77 typedef typename MergeGraph::Graph Graph;
78 typedef typename Graph::Edge BaseGraphEdge;
79 typedef typename Graph::Node BaseGraphNode;
80 typedef typename MergeGraph::Edge Edge;
81 typedef typename MergeGraph::Node Node;
82 typedef typename MergeGraph::EdgeIt EdgeIt;
83 typedef typename MergeGraph::NodeIt NodeIt;
84 typedef typename MergeGraph::IncEdgeIt IncEdgeIt;
85 typedef typename MergeGraph::index_type index_type;
86 typedef MergeGraphItemHelper<MergeGraph,Edge> EdgeHelper;
87 typedef MergeGraphItemHelper<MergeGraph,Node> NodeHelper;
88
89 typedef typename MergeGraph::MergeNodeCallBackType MergeNodeCallBackType;
90 typedef typename MergeGraph::MergeEdgeCallBackType MergeEdgeCallBackType;
91 typedef typename MergeGraph::EraseEdgeCallBackType EraseEdgeCallBackType;
92
93 typedef typename EDGE_INDICATOR_MAP::Reference EdgeIndicatorReference;
94 /// \brief construct cluster operator
95 EdgeWeightedUcm(
96 MergeGraph & mergeGraph,
97 EDGE_INDICATOR_MAP edgeIndicatorMap,
98 EDGE_SIZE_MAP edgeSizeMap,
99 NODE_SIZE_MAP nodeSizeMap,
100 MIN_WEIGHT_MAP minWeightEdgeMap,
101 const ValueType wardness=1.0
102 )
103 : mergeGraph_(mergeGraph),
104 edgeIndicatorMap_(edgeIndicatorMap),
105 edgeSizeMap_(edgeSizeMap),
106 nodeSizeMap_(nodeSizeMap),
107 minWeightEdgeMap_(minWeightEdgeMap),
108 pq_(mergeGraph.maxEdgeId()+1),
109 wardness_(wardness)
110 {
111 MergeNodeCallBackType cbMn(MergeNodeCallBackType:: template from_method<SelfType,&SelfType::mergeNodes>(this));
112 MergeEdgeCallBackType cbMe(MergeEdgeCallBackType:: template from_method<SelfType,&SelfType::mergeEdges>(this));
113 EraseEdgeCallBackType cbEe(EraseEdgeCallBackType:: template from_method<SelfType,&SelfType::eraseEdge>(this));
114
115 mergeGraph_.registerMergeNodeCallBack(cbMn);
116 mergeGraph_.registerMergeEdgeCallBack(cbMe);
117 mergeGraph_.registerEraseEdgeCallBack(cbEe);
118
119 for(EdgeIt e(mergeGraph_);e!=lemon::INVALID;++e){
120 const Edge edge = *e;
121 const BaseGraphEdge graphEdge=EdgeHelper::itemToGraphItem(mergeGraph_,edge);
122 const index_type edgeId = mergeGraph_.id(edge);
123 const ValueType currentWeight = this->getEdgeWeight(edge);
124 pq_.push(edgeId,currentWeight);
125 minWeightEdgeMap_[graphEdge]=currentWeight;
126 }
127 }
128
129 void setWardness(const float w){
130 wardness_ = w;
131 }
132
133 void resetMgAndPq(){
134 mergeGraph_.reset();
135
136 MergeNodeCallBackType cbMn(MergeNodeCallBackType:: template from_method<SelfType,&SelfType::mergeNodes>(this));
137 MergeEdgeCallBackType cbMe(MergeEdgeCallBackType:: template from_method<SelfType,&SelfType::mergeEdges>(this));
138 EraseEdgeCallBackType cbEe(EraseEdgeCallBackType:: template from_method<SelfType,&SelfType::eraseEdge>(this));
139
140 mergeGraph_.registerMergeNodeCallBack(cbMn);
141 mergeGraph_.registerMergeEdgeCallBack(cbMe);
142 mergeGraph_.registerEraseEdgeCallBack(cbEe);
143
144 pq_.reset();
145 for(EdgeIt e(mergeGraph_);e!=lemon::INVALID;++e){
146 const Edge edge = *e;
147 const BaseGraphEdge graphEdge=EdgeHelper::itemToGraphItem(mergeGraph_,edge);
148 const index_type edgeId = mergeGraph_.id(edge);
149 const ValueType currentWeight = this->getEdgeWeight(edge);
150 pq_.push(edgeId,currentWeight);
151 minWeightEdgeMap_[graphEdge]=currentWeight;
152 }
153 }
154
155 /// \brief will be called via callbacks from mergegraph
156 void mergeEdges(const Edge & a,const Edge & b){
157 // update features / weigts etc
158 const BaseGraphEdge aa=EdgeHelper::itemToGraphItem(mergeGraph_,a);
159 const BaseGraphEdge bb=EdgeHelper::itemToGraphItem(mergeGraph_,b);
160 EdgeIndicatorReference va=edgeIndicatorMap_[aa];
161 EdgeIndicatorReference vb=edgeIndicatorMap_[bb];
162 va*=edgeSizeMap_[aa];
163 vb*=edgeSizeMap_[bb];
164
165 va+=vb;
166 edgeSizeMap_[aa]+=edgeSizeMap_[bb];
167 va/=(edgeSizeMap_[aa]);
168 vb/=edgeSizeMap_[bb];
169 // delete b from pq
170 pq_.deleteItem(b.id());
171 }
172
173 /// \brief will be called via callbacks from mergegraph
174 void mergeNodes(const Node & a,const Node & b){
175 const BaseGraphNode aa=NodeHelper::itemToGraphItem(mergeGraph_,a);
176 const BaseGraphNode bb=NodeHelper::itemToGraphItem(mergeGraph_,b);
177 nodeSizeMap_[aa]+=nodeSizeMap_[bb];
178 }
179
180 /// \brief will be called via callbacks from mergegraph
181 void eraseEdge(const Edge & edge){
182
183 //std::cout<<"start to erase edge "<<mergeGraph_.id(edge)<<"\n";
184 // delete edge from pq
185 pq_.deleteItem(edge.id());
186 // get the new region the edge is in
187 // (since the edge is no any more an active edge)
188 //std::cout<<"get the new node \n";
189 const Node newNode = mergeGraph_.inactiveEdgesNode(edge);
190 //std::cout<<"new node "<<mergeGraph_.id(newNode)<<"\n";
191
192 // iterate over all edges of this node
193 for (IncEdgeIt e(mergeGraph_,newNode);e!=lemon::INVALID;++e)
194 {
195 //std::cout<<"get inc edge\n";
196 const Edge incEdge(*e);
197
198 //std::cout<<"get inc graph edge\n";
199 const BaseGraphEdge incGraphEdge = EdgeHelper::itemToGraphItem(mergeGraph_,incEdge);
200
201 //std::cout<<"get inc edge weight"<<counter<<"\n";
202 // compute the new weight for this edge
203 // (this should involve region differences)
204 const ValueType newWeight = getEdgeWeight(incEdge);
205
206 // change the weight in pq by repushing
207 pq_.push(incEdge.id(),newWeight);
208 minWeightEdgeMap_[incGraphEdge]=newWeight;
209
210 }
211 //std::cout<<"done\n";
212 }
213
214 /// \brief get the edge which should be contracted next
215 Edge contractionEdge(){
216 index_type minLabel = pq_.top();
217 while(mergeGraph_.hasEdgeId(minLabel)==false){
218 eraseEdge(Edge(minLabel));
219 minLabel = pq_.top();
220 }
221 return Edge(minLabel);
222 }
223
224 /// \brief get the edge weight of the edge which should be contracted next
225 WeightType contractionWeight(){
226 index_type minLabel = pq_.top();
227 while(mergeGraph_.hasEdgeId(minLabel)==false){
228 eraseEdge(Edge(minLabel));
229 minLabel = pq_.top();
230 }
231 return pq_.topPriority();
232
233 }
234
235
236 /// \brief get a reference to the merge
237 MergeGraph & mergeGraph(){
238 return mergeGraph_;
239 }
240
241 bool done(){
242
243 index_type minLabel = pq_.top();
244 while(mergeGraph_.hasEdgeId(minLabel)==false){
245 eraseEdge(Edge(minLabel));
246 minLabel = pq_.top();
247 }
248 return mergeGraph_.edgeNum()==0 || mergeGraph_.nodeNum()==1;
249 }
250
251 private:
252 ValueType getEdgeWeight(const Edge & e){
253
254 const Node u = mergeGraph_.u(e);
255 const Node v = mergeGraph_.v(e);
256
257 const size_t dU = mergeGraph_.degree(u);
258 const size_t dV = mergeGraph_.degree(u);
259 const BaseGraphEdge ee=EdgeHelper::itemToGraphItem(mergeGraph_,e);
260 const BaseGraphNode uu=NodeHelper::itemToGraphItem(mergeGraph_,u);
261 const BaseGraphNode vv=NodeHelper::itemToGraphItem(mergeGraph_,v);
262
263 const float sizeU = nodeSizeMap_[uu] ;
264 const float sizeV = nodeSizeMap_[vv] ;
265
266 const ValueType wardFac = 2.0 / ( 1.0/std::pow(sizeU,wardness_) + 1/std::pow(sizeV,wardness_) );
267 //const ValueType wardFac = (wardFacRaw*wardness_) + (1.0-wardness_);
268
269 const ValueType fromEdgeIndicator = edgeIndicatorMap_[ee];
270 const ValueType totalWeight = fromEdgeIndicator*wardFac;
271 return totalWeight;
272 }
273
274
275 MergeGraph & mergeGraph_;
276 EDGE_INDICATOR_MAP edgeIndicatorMap_;
277 EDGE_SIZE_MAP edgeSizeMap_;
278 NODE_SIZE_MAP nodeSizeMap_;
279 MIN_WEIGHT_MAP minWeightEdgeMap_;
280 vigra::ChangeablePriorityQueue< ValueType > pq_;
281 ValueType wardness_;;
282 };
283
284 /// \brief This Cluster Operator is a MONSTER.
285 /// It can really do a lot.
286 ///
287 /// Each edge has a single scalar weight w_e.
288 /// Each node has a feature vector f_n.
289 /// (all f_n's have the same length).
290 /// Edges and nodes have a length / size
291 ///
292 /// The total edge weight is computed via a complicated formula
293 ///
294 /// The main idea is the following.
295 /// Use a mixture between the edge weights w_e,
296 /// and node based edge weights which are computed
297 /// via a metric which measures the 'difference' between
298 /// the u/v feature vectors f_n.
299 ///
300 /// Furthermore a 'Ward'-like regularization can be applied.
301 /// This is useful if one have clusters with sizes
302 /// in the same magnitude (or 'similar' sizes).
303 /// The amount of 'ward'-regularization is controlled
304 /// with the 'wardness' parameter.
305 ///
306 /// Also labels (in the sense of seeds) can be attached to get a 'watershed-ish'
307 /// behavior (nodes with different labels will never be merged)
308 /// The '0'-Label is used to indicate that there is no label at all.
309 /// If certain connected regions share the same seed/label
310 /// it is not guaranteed that they will merge. But a certain prior / multiplier
311 /// must be specified. The total weight of an edge where the u/v node have
312 /// the same label is multiplied with this very multiplier.
313 template<
314 class MERGE_GRAPH,
315 class EDGE_INDICATOR_MAP,
316 class EDGE_SIZE_MAP,
317 class NODE_FEATURE_MAP,
318 class NODE_SIZE_MAP,
319 class MIN_WEIGHT_MAP,
320 class NODE_LABEL_MAP
321 >
322 class EdgeWeightNodeFeatures{
323
324 typedef EdgeWeightNodeFeatures<
325 MERGE_GRAPH,
326 EDGE_INDICATOR_MAP,
327 EDGE_SIZE_MAP,
328 NODE_FEATURE_MAP,
329 NODE_SIZE_MAP,
330 MIN_WEIGHT_MAP,
331 NODE_LABEL_MAP
332 > SelfType;
333 public:
334
335
336 typedef typename EDGE_INDICATOR_MAP::Value ValueType;
337 typedef ValueType WeightType;
338 typedef MERGE_GRAPH MergeGraph;
339 typedef typename MergeGraph::Graph Graph;
340 typedef typename Graph::Edge BaseGraphEdge;
341 typedef typename Graph::Node BaseGraphNode;
342 typedef typename MergeGraph::Edge Edge;
343 typedef typename MergeGraph::Node Node;
344 typedef typename MergeGraph::EdgeIt EdgeIt;
345 typedef typename MergeGraph::NodeIt NodeIt;
346 typedef typename MergeGraph::IncEdgeIt IncEdgeIt;
347 typedef typename MergeGraph::index_type index_type;
348 typedef MergeGraphItemHelper<MergeGraph,Edge> EdgeHelper;
349 typedef MergeGraphItemHelper<MergeGraph,Node> NodeHelper;
350
351
352 typedef typename EDGE_INDICATOR_MAP::Reference EdgeIndicatorReference;
353 typedef typename NODE_FEATURE_MAP::Reference NodeFeatureReference;
354 /// \brief construct cluster operator
355 EdgeWeightNodeFeatures(
356 MergeGraph & mergeGraph,
357 EDGE_INDICATOR_MAP edgeIndicatorMap,
358 EDGE_SIZE_MAP edgeSizeMap,
359 NODE_FEATURE_MAP nodeFeatureMap,
360 NODE_SIZE_MAP nodeSizeMap,
361 MIN_WEIGHT_MAP minWeightEdgeMap,
362 NODE_LABEL_MAP nodeLabelMap,
363 const ValueType beta,
364 const metrics::MetricType metricType,
365 const ValueType wardness=1.0,
366 const ValueType gamma = 10000000.0,
367 const ValueType sameLabelMultiplier = 0.8
368 )
369 : mergeGraph_(mergeGraph),
370 edgeIndicatorMap_(edgeIndicatorMap),
371 edgeSizeMap_(edgeSizeMap),
372 nodeFeatureMap_(nodeFeatureMap),
373 nodeSizeMap_(nodeSizeMap),
374 minWeightEdgeMap_(minWeightEdgeMap),
375 nodeLabelMap_(nodeLabelMap),
376 pq_(mergeGraph.maxEdgeId()+1),
377 beta_(beta),
378 wardness_(wardness),
379 gamma_(gamma),
380 sameLabelMultiplier_(sameLabelMultiplier),
381 metric_(metricType)
382 {
383 typedef typename MergeGraph::MergeNodeCallBackType MergeNodeCallBackType;
384 typedef typename MergeGraph::MergeEdgeCallBackType MergeEdgeCallBackType;
385 typedef typename MergeGraph::EraseEdgeCallBackType EraseEdgeCallBackType;
386
387
388 MergeNodeCallBackType cbMn(MergeNodeCallBackType:: template from_method<SelfType,&SelfType::mergeNodes>(this));
389 MergeEdgeCallBackType cbMe(MergeEdgeCallBackType:: template from_method<SelfType,&SelfType::mergeEdges>(this));
390 EraseEdgeCallBackType cbEe(EraseEdgeCallBackType:: template from_method<SelfType,&SelfType::eraseEdge>(this));
391
392 mergeGraph_.registerMergeNodeCallBack(cbMn);
393 mergeGraph_.registerMergeEdgeCallBack(cbMe);
394 mergeGraph_.registerEraseEdgeCallBack(cbEe);
395
396
397
398 for(EdgeIt e(mergeGraph);e!=lemon::INVALID;++e){
399 const Edge edge = *e;
400 const BaseGraphEdge graphEdge=EdgeHelper::itemToGraphItem(mergeGraph_,edge);
401 const index_type edgeId = mergeGraph_.id(edge);
402 const ValueType currentWeight = this->getEdgeWeight(edge);
403 pq_.push(edgeId,currentWeight);
404 minWeightEdgeMap_[graphEdge]=currentWeight;
405 }
406
407 }
408
409 /// \brief will be called via callbacks from mergegraph
410 void mergeEdges(const Edge & a,const Edge & b){
411 // update features / weigts etc
412 const BaseGraphEdge aa=EdgeHelper::itemToGraphItem(mergeGraph_,a);
413 const BaseGraphEdge bb=EdgeHelper::itemToGraphItem(mergeGraph_,b);
414 EdgeIndicatorReference va=edgeIndicatorMap_[aa];
415 EdgeIndicatorReference vb=edgeIndicatorMap_[bb];
416 va*=edgeSizeMap_[aa];
417 vb*=edgeSizeMap_[bb];
418
419
420 va+=vb;
421 edgeSizeMap_[aa]+=edgeSizeMap_[bb];
422 va/=(edgeSizeMap_[aa]);
423 vb/=edgeSizeMap_[bb];
424 // delete b from pq
425 pq_.deleteItem(b.id());
426 }
427
428 /// \brief will be called via callbacks from mergegraph
429 void mergeNodes(const Node & a,const Node & b){
430 const BaseGraphNode aa=NodeHelper::itemToGraphItem(mergeGraph_,a);
431 const BaseGraphNode bb=NodeHelper::itemToGraphItem(mergeGraph_,b);
432 NodeFeatureReference va=nodeFeatureMap_[aa];
433 NodeFeatureReference vb=nodeFeatureMap_[bb];
434 va*=nodeSizeMap_[aa];
435 vb*=nodeSizeMap_[bb];
436 va+=vb;
437 nodeSizeMap_[aa]+=nodeSizeMap_[bb];
438 va/=(nodeSizeMap_[aa]);
439 vb/=nodeSizeMap_[bb];
440
441
442 // update labels
443 const UInt32 labelA = nodeLabelMap_[aa];
444 const UInt32 labelB = nodeLabelMap_[bb];
445
446 if(labelA!=0 && labelB!=0 && labelA!=labelB){
447 throw std::runtime_error("both nodes have labels");
448 }
449 else{
450 const UInt32 newLabel = std::max(labelA, labelB);
451 nodeLabelMap_[aa] = newLabel;
452 }
453 }
454
455 /// \brief will be called via callbacks from mergegraph
456 void eraseEdge(const Edge & edge){
457
458 //std::cout<<"start to erase edge "<<mergeGraph_.id(edge)<<"\n";
459 // delete edge from pq
460 pq_.deleteItem(edge.id());
461 // get the new region the edge is in
462 // (since the edge is no any more an active edge)
463 //std::cout<<"get the new node \n";
464 const Node newNode = mergeGraph_.inactiveEdgesNode(edge);
465 //std::cout<<"new node "<<mergeGraph_.id(newNode)<<"\n";
466
467
468 // iterate over all edges of this node
469 for (IncEdgeIt e(mergeGraph_,newNode);e!=lemon::INVALID;++e){
470
471 //std::cout<<"get inc edge\n";
472 const Edge incEdge(*e);
473
474 //std::cout<<"get inc graph edge\n";
475 const BaseGraphEdge incGraphEdge = EdgeHelper::itemToGraphItem(mergeGraph_,incEdge);
476
477 //std::cout<<"get inc edge weight"<<counter<<"\n";
478 // compute the new weight for this edge
479 // (this should involve region differences)
480 const ValueType newWeight = getEdgeWeight(incEdge);
481
482
483 // change the weight in pq by repushing
484
485 //std::cout<<"push\n";
486 pq_.push(incEdge.id(),newWeight);
487 minWeightEdgeMap_[incGraphEdge]=newWeight;
488
489 }
490 //std::cout<<"done\n";
491 }
492
493 /// \brief get the edge which should be contracted next
494 Edge contractionEdge(){
495 index_type minLabel = pq_.top();
496 while(mergeGraph_.hasEdgeId(minLabel)==false){
497 pq_.deleteItem(minLabel);
498 minLabel = pq_.top();
499 }
500 return Edge(minLabel);
501 }
502
503 /// \brief get the edge weight of the edge which should be contracted next
504 WeightType contractionWeight(){
505 index_type minLabel = pq_.top();
506 while(mergeGraph_.hasEdgeId(minLabel)==false){
507 pq_.deleteItem(minLabel);
508 minLabel = pq_.top();
509 }
510 return pq_.topPriority();
511
512 }
513
514
515 /// \brief get a reference to the merge
516 MergeGraph & mergeGraph(){
517 return mergeGraph_;
518 }
519
520 bool done(){
521
522 index_type minLabel = pq_.top();
523 while(mergeGraph_.hasEdgeId(minLabel)==false){
524 pq_.deleteItem(minLabel);
525 minLabel = pq_.top();
526 }
527 const ValueType p = pq_.topPriority();
528
529 return p>= gamma_;
530 }
531
532 private:
533 ValueType getEdgeWeight(const Edge & e){
534
535 const Node u = mergeGraph_.u(e);
536 const Node v = mergeGraph_.v(e);
537
538 const size_t dU = mergeGraph_.degree(u);
539 const size_t dV = mergeGraph_.degree(u);
540 const BaseGraphEdge ee=EdgeHelper::itemToGraphItem(mergeGraph_,e);
541 const BaseGraphNode uu=NodeHelper::itemToGraphItem(mergeGraph_,u);
542 const BaseGraphNode vv=NodeHelper::itemToGraphItem(mergeGraph_,v);
543
544 const float sizeU = nodeSizeMap_[uu];
545 const float sizeV = nodeSizeMap_[vv];
546
547
548 const ValueType wardFac = 2.0 / ( 1.0/std::pow(sizeU,wardness_) + 1/std::pow(sizeV,wardness_) );
549
550 const ValueType fromEdgeIndicator = edgeIndicatorMap_[ee];
551 ValueType fromNodeDist = metric_(nodeFeatureMap_[uu],nodeFeatureMap_[vv]);
552 ValueType totalWeight = ((1.0-beta_)*fromEdgeIndicator + beta_*fromNodeDist)*wardFac;
553
554
555 const UInt32 labelA = nodeLabelMap_[uu];
556 const UInt32 labelB = nodeLabelMap_[vv];
557
558 if(labelA!=0 && labelB!=0){
559 if(labelA == labelB){
560 totalWeight*=sameLabelMultiplier_;
561 }
562 else{
563 totalWeight += gamma_;
564 }
565 }
566 return totalWeight;
567 }
568
569
570 MergeGraph & mergeGraph_;
571 EDGE_INDICATOR_MAP edgeIndicatorMap_;
572 EDGE_SIZE_MAP edgeSizeMap_;
573 NODE_FEATURE_MAP nodeFeatureMap_;
574 NODE_SIZE_MAP nodeSizeMap_;
575 MIN_WEIGHT_MAP minWeightEdgeMap_;
576 NODE_LABEL_MAP nodeLabelMap_;
577 vigra::ChangeablePriorityQueue< ValueType > pq_;
578 ValueType beta_;
579 ValueType wardness_;
580 ValueType gamma_;
581 ValueType sameLabelMultiplier_;
582 metrics::Metric<float> metric_;
583 };
584
585
586
587 } // end namespace cluster_operators
588
589
590
591 /// \brief do hierarchical clustering with a given cluster operator
592 template< class CLUSTER_OPERATOR>
593 class HierarchicalClustering{
594
595 public:
596 typedef CLUSTER_OPERATOR ClusterOperator;
597 typedef typename ClusterOperator::MergeGraph MergeGraph;
598 typedef typename MergeGraph::Graph Graph;
599 typedef typename Graph::Edge BaseGraphEdge;
600 typedef typename Graph::Node BaseGraphNode;
601 typedef typename MergeGraph::Edge Edge;
602 typedef typename MergeGraph::Node Node;
603 typedef typename CLUSTER_OPERATOR::WeightType ValueType;
604 typedef typename MergeGraph::index_type MergeGraphIndexType;
605
606 struct Parameter{
607 Parameter(
608 const size_t nodeNumStopCond = 1,
609 const bool buildMergeTree = true,
610 const bool verbose = false
611 )
612 : nodeNumStopCond_ (nodeNumStopCond),
613 buildMergeTreeEncoding_(buildMergeTree),
614 verbose_(verbose){
615 }
616 size_t nodeNumStopCond_;
617 bool buildMergeTreeEncoding_;
618 bool verbose_;
619 };
620
621 struct MergeItem{
622 MergeItem(
623 const MergeGraphIndexType a,
624 const MergeGraphIndexType b,
625 const MergeGraphIndexType r,
626 const ValueType w
627 ):
628 a_(a),b_(b),r_(r),w_(w){
629 }
630 MergeGraphIndexType a_;
631 MergeGraphIndexType b_;
632 MergeGraphIndexType r_;
633 ValueType w_;
634 };
635
636 typedef std::vector<MergeItem> MergeTreeEncoding;
637
638 /// \brief construct HierarchicalClustering from clusterOperator and an optional parameter object
639 HierarchicalClustering(
640 ClusterOperator & clusterOperator,
641 const Parameter & parameter = Parameter()
642 )
643 :
644 clusterOperator_(clusterOperator),
645 param_(parameter),
646 mergeGraph_(clusterOperator_.mergeGraph()),
647 graph_(mergeGraph_.graph()),
648 timestamp_(graph_.maxNodeId()+1),
649 toTimeStamp_(),
650 timeStampIndexToMergeIndex_(),
651 mergeTreeEndcoding_()
652 {
653 if(param_.buildMergeTreeEncoding_){
654 // this can be be made smater since user can pass
655 // stoping condition based on nodeNum
656 mergeTreeEndcoding_.reserve(graph_.nodeNum()*2);
657 toTimeStamp_.resize(graph_.maxNodeId()+1);
658 timeStampIndexToMergeIndex_.resize(graph_.maxNodeId()+1);
659 for(MergeGraphIndexType nodeId=0;nodeId<=mergeGraph_.maxNodeId();++nodeId){
660 toTimeStamp_[nodeId]=nodeId;
661 }
662 }
663
664
665
666 }
667
668 /// \brief start the clustering
669 void cluster(){
670 if(param_.verbose_)
671 std::cout<<"\n";
672 while(mergeGraph_.nodeNum()>param_.nodeNumStopCond_ && mergeGraph_.edgeNum()>0 && !clusterOperator_.done()){
673
674 const Edge edgeToRemove = clusterOperator_.contractionEdge();
675 if(param_.buildMergeTreeEncoding_){
676 const MergeGraphIndexType uid = mergeGraph_.id(mergeGraph_.u(edgeToRemove));
677 const MergeGraphIndexType vid = mergeGraph_.id(mergeGraph_.v(edgeToRemove));
678 const ValueType w = clusterOperator_.contractionWeight();
679 // do the merge
680 mergeGraph_.contractEdge( edgeToRemove);
681 const MergeGraphIndexType aliveNodeId = mergeGraph_.hasNodeId(uid) ? uid : vid;
682 const MergeGraphIndexType deadNodeId = aliveNodeId==vid ? uid : vid;
683 timeStampIndexToMergeIndex_[timeStampToIndex(timestamp_)]=mergeTreeEndcoding_.size();
684 mergeTreeEndcoding_.push_back(MergeItem( toTimeStamp_[aliveNodeId],toTimeStamp_[deadNodeId],timestamp_,w));
685 toTimeStamp_[aliveNodeId]=timestamp_;
686 timestamp_+=1;
687 }
688 else{
689 //std::cout<<"constract\n";
690 // do the merge
691 mergeGraph_.contractEdge( edgeToRemove );
692 }
693 if(param_.verbose_ && mergeGraph_.nodeNum()%1==0){
694 std::cout<<"\rNodes: "<<std::setw(10)<<mergeGraph_.nodeNum()<<std::flush;
695 }
696
697 }
698 if(param_.verbose_)
699 std::cout<<"\n";
700 }
701
702 /// \brief get the encoding of the merge tree
703 const MergeTreeEncoding & mergeTreeEndcoding()const{
704 return mergeTreeEndcoding_;
705 }
706
707 template<class EDGE_MAP>
708 void ucmTransform(EDGE_MAP & edgeMap)const{
709 typedef typename Graph::EdgeIt BaseGraphEdgeIt;
710
711 for(BaseGraphEdgeIt iter(graph()); iter!=lemon::INVALID; ++iter ){
712 const BaseGraphEdge edge=*iter;
713 edgeMap[edge] = edgeMap[mergeGraph().reprGraphEdge(edge)];
714 }
715 }
716
717 /// \brief get the node id's which are the leafes of a treeNodeId
718 template<class OUT_ITER>
719 size_t leafNodeIds(const MergeGraphIndexType treeNodeId, OUT_ITER begin)const{
720 if(treeNodeId<=graph_.maxNodeId()){
721 *begin=treeNodeId;
722 ++begin;
723 return 1;
724 }
725 else{
726 size_t leafNum=0;
727 std::queue<MergeGraphIndexType> queue;
728 queue.push(treeNodeId);
729
730 while(!queue.empty()){
731
732 const MergeGraphIndexType id = queue.front();
733 queue.pop();
734 const MergeGraphIndexType mergeIndex = timeStampToMergeIndex(id);
735 const MergeGraphIndexType ab[]= { mergeTreeEndcoding_[mergeIndex].a_, mergeTreeEndcoding_[mergeIndex].b_};
736
737 for(size_t i=0;i<2;++i){
738 if(ab[i]<=graph_.maxNodeId()){
739 *begin=ab[i];
740 ++begin;
741 ++leafNum;
742 }
743 else{
744 queue.push(ab[i]);
745 }
746 }
747 }
748 return leafNum;
749 }
750 }
751
752 /// \brief get the graph the merge graph is based on
753 const Graph & graph()const{
754 return graph_;
755 }
756
757 /// \brief get the merge graph
758 const MergeGraph & mergeGraph()const{
759 return mergeGraph_;
760 }
761
762 /// \brief get the representative node id
763 const MergeGraphIndexType reprNodeId(const MergeGraphIndexType id)const{
764 return mergeGraph_.reprNodeId(id);
765 }
766 private:
767
768 MergeGraphIndexType timeStampToIndex(const MergeGraphIndexType timestamp)const{
769 return timestamp- graph_.maxNodeId();
770 }
771
772
773 MergeGraphIndexType timeStampToMergeIndex(const MergeGraphIndexType timestamp)const{
774 return timeStampIndexToMergeIndex_[timeStampToIndex(timestamp)];
775 }
776
777 ClusterOperator & clusterOperator_;
778 Parameter param_;
779 MergeGraph & mergeGraph_;
780 const Graph & graph_;
781 // parameter object
782
783
784 // timestamp
785 MergeGraphIndexType timestamp_;
786 std::vector<MergeGraphIndexType> toTimeStamp_;
787 std::vector<MergeGraphIndexType> timeStampIndexToMergeIndex_;
788 // data which can reconstruct the merge tree
789 MergeTreeEncoding mergeTreeEndcoding_;
790
791
792 };
793
794
795 }
796
797 #endif // VIGRA_HIERARCHICAL_CLUSTERING_HXX
vigra::HierarchicalClustering::mergeTreeEndcoding
const MergeTreeEncoding & mergeTreeEndcoding() const
get the encoding of the merge tree
Definition: hierarchical_clustering.hxx:703
vigra::HierarchicalClustering::mergeGraph
const MergeGraph & mergeGraph() const
get the merge graph
Definition: hierarchical_clustering.hxx:758
vigra::cluster_operators::EdgeWeightNodeFeatures
This Cluster Operator is a MONSTER. It can really do a lot.
Definition: hierarchical_clustering.hxx:322
vigra::cluster_operators::EdgeWeightNodeFeatures::mergeGraph
MergeGraph & mergeGraph()
get a reference to the merge
Definition: hierarchical_clustering.hxx:516
vigra::HierarchicalClustering::reprNodeId
const MergeGraphIndexType reprNodeId(const MergeGraphIndexType id) const
get the representative node id
Definition: hierarchical_clustering.hxx:763
vigra::HierarchicalClustering::leafNodeIds
size_t leafNodeIds(const MergeGraphIndexType treeNodeId, OUT_ITER begin) const
get the node id&#39;s which are the leafes of a treeNodeId
Definition: hierarchical_clustering.hxx:719
vigra
Definition: accessor.hxx:43
vigra::ChangeablePriorityQueue< ValueType >
vigra::cluster_operators::EdgeWeightNodeFeatures::EdgeWeightNodeFeatures
EdgeWeightNodeFeatures(MergeGraph &mergeGraph, EDGE_INDICATOR_MAP edgeIndicatorMap, EDGE_SIZE_MAP edgeSizeMap, NODE_FEATURE_MAP nodeFeatureMap, NODE_SIZE_MAP nodeSizeMap, MIN_WEIGHT_MAP minWeightEdgeMap, NODE_LABEL_MAP nodeLabelMap, const ValueType beta, const metrics::MetricType metricType, const ValueType wardness=1.0, const ValueType gamma=10000000.0, const ValueType sameLabelMultiplier=0.8)
construct cluster operator
Definition: hierarchical_clustering.hxx:355
vigra::HierarchicalClustering::graph
const Graph & graph() const
get the graph the merge graph is based on
Definition: hierarchical_clustering.hxx:753
vigra::cluster_operators::EdgeWeightNodeFeatures::contractionWeight
WeightType contractionWeight()
get the edge weight of the edge which should be contracted next
Definition: hierarchical_clustering.hxx:504
vigra::cluster_operators::EdgeWeightNodeFeatures::mergeEdges
void mergeEdges(const Edge &a, const Edge &b)
will be called via callbacks from mergegraph
Definition: hierarchical_clustering.hxx:410
vigra::cluster_operators::EdgeWeightNodeFeatures::eraseEdge
void eraseEdge(const Edge &edge)
will be called via callbacks from mergegraph
Definition: hierarchical_clustering.hxx:456
vigra::HierarchicalClustering::HierarchicalClustering
HierarchicalClustering(ClusterOperator &clusterOperator, const Parameter &parameter=Parameter())
construct HierarchicalClustering from clusterOperator and an optional parameter object ...
Definition: hierarchical_clustering.hxx:639
vigra::gamma
double gamma(double x)
The gamma function.
Definition: mathutil.hxx:1570
vigra::boost_graph::edge
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
vigra::cluster_operators::EdgeWeightNodeFeatures::mergeNodes
void mergeNodes(const Node &a, const Node &b)
will be called via callbacks from mergegraph
Definition: hierarchical_clustering.hxx:429
vigra::HierarchicalClustering
do hierarchical clustering with a given cluster operator
Definition: hierarchical_clustering.hxx:593
vigra::UInt32
detail::SelectIntegerType< 32, detail::UnsignedIntTypes >::type UInt32
32-bit unsigned int
Definition: sized_int.hxx:183
vigra::HierarchicalClustering::cluster
void cluster()
start the clustering
Definition: hierarchical_clustering.hxx:669
vigra::cluster_operators::EdgeWeightNodeFeatures::contractionEdge
Edge contractionEdge()
get the edge which should be contracted next
Definition: hierarchical_clustering.hxx:494

© 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