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

hierarchical_clustering.hxx VIGRA

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_;
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  >
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
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
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_;
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>
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
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
This Cluster Operator is a MONSTER. It can really do a lot.
Definition: hierarchical_clustering.hxx:322
MergeGraph & mergeGraph()
get a reference to the merge
Definition: hierarchical_clustering.hxx:516
const MergeGraphIndexType reprNodeId(const MergeGraphIndexType id) const
get the representative node id
Definition: hierarchical_clustering.hxx:763
const MergeGraph & mergeGraph() const
get the merge graph
Definition: hierarchical_clustering.hxx:758
Definition: accessor.hxx:43
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
WeightType contractionWeight()
get the edge weight of the edge which should be contracted next
Definition: hierarchical_clustering.hxx:504
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
void mergeEdges(const Edge &a, const Edge &b)
will be called via callbacks from mergegraph
Definition: hierarchical_clustering.hxx:410
void eraseEdge(const Edge &edge)
will be called via callbacks from mergegraph
Definition: hierarchical_clustering.hxx:456
HierarchicalClustering(ClusterOperator &clusterOperator, const Parameter &parameter=Parameter())
construct HierarchicalClustering from clusterOperator and an optional parameter object ...
Definition: hierarchical_clustering.hxx:639
double gamma(double x)
The gamma function.
Definition: mathutil.hxx:1570
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 mergeNodes(const Node &a, const Node &b)
will be called via callbacks from mergegraph
Definition: hierarchical_clustering.hxx:429
do hierarchical clustering with a given cluster operator
Definition: hierarchical_clustering.hxx:593
detail::SelectIntegerType< 32, detail::UnsignedIntTypes >::type UInt32
32-bit unsigned int
Definition: sized_int.hxx:183
void cluster()
start the clustering
Definition: hierarchical_clustering.hxx:669
const MergeTreeEncoding & mergeTreeEndcoding() const
get the encoding of the merge tree
Definition: hierarchical_clustering.hxx:703
Edge contractionEdge()
get the edge which should be contracted next
Definition: hierarchical_clustering.hxx:494
const Graph & graph() const
get the graph the merge graph is based on
Definition: hierarchical_clustering.hxx:753

© 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.10.0