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

watersheds.hxx VIGRA

1 /************************************************************************/
2 /* */
3 /* Copyright 1998-2005 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 #ifndef VIGRA_WATERSHEDS_HXX
37 #define VIGRA_WATERSHEDS_HXX
38 
39 #include <functional>
40 #include "mathutil.hxx"
41 #include "stdimage.hxx"
42 #include "pixelneighborhood.hxx"
43 #include "localminmax.hxx"
44 #include "labelimage.hxx"
45 #include "seededregiongrowing.hxx"
46 #include "functorexpression.hxx"
47 #include "union_find.hxx"
48 #include "multi_shape.hxx"
49 
50 namespace vigra {
51 
52 template <class SrcIterator, class SrcAccessor,
53  class DestIterator, class DestAccessor,
54  class Neighborhood>
55 unsigned int watershedLabeling(SrcIterator upperlefts,
56  SrcIterator lowerrights, SrcAccessor sa,
57  DestIterator upperleftd, DestAccessor da,
58  Neighborhood)
59 {
60  typedef typename DestAccessor::value_type LabelType;
61 
62  int w = lowerrights.x - upperlefts.x;
63  int h = lowerrights.y - upperlefts.y;
64  int x,y;
65 
66  SrcIterator ys(upperlefts);
67  SrcIterator xs(ys);
68  DestIterator yd(upperleftd);
69  DestIterator xd(yd);
70 
71  // temporary image to store region labels
72  UnionFindArray<LabelType> labels;
73 
74  // initialize the neighborhood circulators
75  NeighborOffsetCirculator<Neighborhood> ncstart(Neighborhood::CausalFirst);
76  NeighborOffsetCirculator<Neighborhood> ncstartBorder(Neighborhood::North);
77  NeighborOffsetCirculator<Neighborhood> ncend(Neighborhood::CausalLast);
78  ++ncend;
79  NeighborOffsetCirculator<Neighborhood> ncendBorder(Neighborhood::North);
80  ++ncendBorder;
81 
82  // pass 1: scan image from upper left to lower right
83  // to find connected components
84 
85  // Each component will be represented by a tree of pixels. Each
86  // pixel contains the scan order address of its parent in the
87  // tree. In order for pass 2 to work correctly, the parent must
88  // always have a smaller scan order address than the child.
89  // Therefore, we can merge trees only at their roots, because the
90  // root of the combined tree must have the smallest scan order
91  // address among all the tree's pixels/ nodes. The root of each
92  // tree is distinguished by pointing to itself (it contains its
93  // own scan order address). This condition is enforced whenever a
94  // new region is found or two regions are merged
95  da.set(labels.finalizeIndex(labels.nextFreeIndex()), xd);
96 
97  ++xs.x;
98  ++xd.x;
99  for(x = 1; x != w; ++x, ++xs.x, ++xd.x)
100  {
101  if((sa(xs) & Neighborhood::directionBit(Neighborhood::West)) ||
102  (sa(xs, Neighborhood::west()) & Neighborhood::directionBit(Neighborhood::East)))
103  {
104  da.set(da(xd, Neighborhood::west()), xd);
105  }
106  else
107  {
108  da.set(labels.finalizeIndex(labels.nextFreeIndex()), xd);
109  }
110  }
111 
112  ++ys.y;
113  ++yd.y;
114  for(y = 1; y != h; ++y, ++ys.y, ++yd.y)
115  {
116  xs = ys;
117  xd = yd;
118 
119  for(x = 0; x != w; ++x, ++xs.x, ++xd.x)
120  {
121  NeighborOffsetCirculator<Neighborhood> nc(x == w-1
122  ? ncstartBorder
123  : ncstart);
124  NeighborOffsetCirculator<Neighborhood> nce(x == 0
125  ? ncendBorder
126  : ncend);
127  LabelType currentIndex = labels.nextFreeIndex();
128  for(; nc != nce; ++nc)
129  {
130  if((sa(xs) & nc.directionBit()) || (sa(xs, *nc) & nc.oppositeDirectionBit()))
131  {
132  currentIndex = labels.makeUnion(da(xd,*nc), currentIndex);
133  }
134  }
135  da.set(labels.finalizeIndex(currentIndex), xd);
136  }
137  }
138 
139  unsigned int count = labels.makeContiguous();
140 
141  // pass 2: assign one label to each region (tree)
142  // so that labels form a consecutive sequence 1, 2, ...
143  yd = upperleftd;
144  for(y=0; y != h; ++y, ++yd.y)
145  {
146  DestIterator xd(yd);
147  for(x = 0; x != w; ++x, ++xd.x)
148  {
149  da.set(labels.findLabel(da(xd)), xd);
150  }
151  }
152  return count;
153 }
154 
155 template <class SrcIterator, class SrcAccessor,
156  class DestIterator, class DestAccessor,
157  class Neighborhood>
158 unsigned int watershedLabeling(triple<SrcIterator, SrcIterator, SrcAccessor> src,
159  pair<DestIterator, DestAccessor> dest,
160  Neighborhood neighborhood)
161 {
162  return watershedLabeling(src.first, src.second, src.third,
163  dest.first, dest.second, neighborhood);
164 }
165 
166 
167 template <class SrcIterator, class SrcAccessor,
168  class DestIterator, class DestAccessor>
169 void prepareWatersheds(SrcIterator upperlefts, SrcIterator lowerrights, SrcAccessor sa,
170  DestIterator upperleftd, DestAccessor da,
172 {
173  int w = lowerrights.x - upperlefts.x;
174  int h = lowerrights.y - upperlefts.y;
175  int x,y;
176 
177  SrcIterator ys(upperlefts);
178  SrcIterator xs(ys);
179 
180  DestIterator yd = upperleftd;
181 
182  for(y = 0; y != h; ++y, ++ys.y, ++yd.y)
183  {
184  xs = ys;
185  DestIterator xd = yd;
186 
187  for(x = 0; x != w; ++x, ++xs.x, ++xd.x)
188  {
189  AtImageBorder atBorder = isAtImageBorder(x,y,w,h);
190  typename SrcAccessor::value_type v = sa(xs);
191  // the following choice causes minima to point
192  // to their lowest neighbor -- would this be better???
193  // typename SrcAccessor::value_type v = NumericTraits<typename SrcAccessor::value_type>::max();
194  int o = 0; // means center is minimum
195  if(atBorder == NotAtBorder)
196  {
197  NeighborhoodCirculator<SrcIterator, FourNeighborCode> c(xs), cend(c);
198  do {
199  if(sa(c) <= v)
200  {
201  v = sa(c);
202  o = c.directionBit();
203  }
204  }
205  while(++c != cend);
206  }
207  else
208  {
209  RestrictedNeighborhoodCirculator<SrcIterator, FourNeighborCode> c(xs, atBorder), cend(c);
210  do {
211  if(sa(c) <= v)
212  {
213  v = sa(c);
214  o = c.directionBit();
215  }
216  }
217  while(++c != cend);
218  }
219  da.set(o, xd);
220  }
221  }
222 }
223 
224 template <class SrcIterator, class SrcAccessor,
225  class DestIterator, class DestAccessor>
226 void prepareWatersheds(SrcIterator upperlefts, SrcIterator lowerrights, SrcAccessor sa,
227  DestIterator upperleftd, DestAccessor da,
229 {
230  int w = lowerrights.x - upperlefts.x;
231  int h = lowerrights.y - upperlefts.y;
232  int x,y;
233 
234  SrcIterator ys(upperlefts);
235  SrcIterator xs(ys);
236 
237  DestIterator yd = upperleftd;
238 
239  for(y = 0; y != h; ++y, ++ys.y, ++yd.y)
240  {
241  xs = ys;
242  DestIterator xd = yd;
243 
244  for(x = 0; x != w; ++x, ++xs.x, ++xd.x)
245  {
246  AtImageBorder atBorder = isAtImageBorder(x,y,w,h);
247  typename SrcAccessor::value_type v = sa(xs);
248  // the following choice causes minima to point
249  // to their lowest neighbor -- would this be better???
250  // typename SrcAccessor::value_type v = NumericTraits<typename SrcAccessor::value_type>::max();
251  int o = 0; // means center is minimum
252  if(atBorder == NotAtBorder)
253  {
254  // handle diagonal and principal neighbors separately
255  // so that principal neighbors are preferred when there are
256  // candidates with equal strength
257  NeighborhoodCirculator<SrcIterator, EightNeighborCode>
259  for(int i = 0; i < 4; ++i, c += 2)
260  {
261  if(sa(c) <= v)
262  {
263  v = sa(c);
264  o = c.directionBit();
265  }
266  }
267  --c;
268  for(int i = 0; i < 4; ++i, c += 2)
269  {
270  if(sa(c) <= v)
271  {
272  v = sa(c);
273  o = c.directionBit();
274  }
275  }
276  }
277  else
278  {
279  RestrictedNeighborhoodCirculator<SrcIterator, EightNeighborCode>
280  c(xs, atBorder), cend(c);
281  do
282  {
283  if(!c.isDiagonal())
284  continue;
285  if(sa(c) <= v)
286  {
287  v = sa(c);
288  o = c.directionBit();
289  }
290  }
291  while(++c != cend);
292  do
293  {
294  if(c.isDiagonal())
295  continue;
296  if(sa(c) <= v)
297  {
298  v = sa(c);
299  o = c.directionBit();
300  }
301  }
302  while(++c != cend);
303  }
304  da.set(o, xd);
305  }
306  }
307 }
308 
309 /** \addtogroup Superpixels
310 */
311 //@{
312 
313  /**\brief Options object for generateWatershedSeeds().
314  *
315  <b> Usage:</b>
316 
317  <b>\#include</b> <vigra/watersheds.hxx><br>
318  Namespace: vigra
319 
320  \code
321  MultiArray<2, float> boundary_indicator(w, h);
322  MultiArray<2, int> seeds(boundary_indicator.shape());
323 
324  // detect all minima in 'boundary_indicator' that are below gray level 22
325  generateWatershedSeeds(boundary_indicator, seeds,
326  SeedOptions().minima().threshold(22.0));
327  \endcode
328  */
330 {
331 public:
332  enum DetectMinima { LevelSets, Minima, ExtendedMinima, Unspecified };
333 
334  double thresh;
335  DetectMinima mini;
336 
337  /**\brief Construct default options object.
338  *
339  Defaults are: detect minima without thresholding (i.e. all minima).
340  */
342  : thresh(NumericTraits<double>::max()),
343  mini(Minima)
344  {}
345 
346  /** Generate seeds at minima.
347 
348  Default: true
349  */
351  {
352  mini = Minima;
353  return *this;
354  }
355 
356  /** Generate seeds at minima and minimal plateaus.
357 
358  Default: false
359  */
361  {
362  mini = ExtendedMinima;
363  return *this;
364  }
365 
366  /** Generate seeds as level sets.
367 
368  Note that you must also set a threshold to define which level set is to be used.<br>
369  Default: false
370  */
372  {
373  mini = LevelSets;
374  return *this;
375  }
376 
377  /** Generate seeds as level sets at given threshold.
378 
379  Equivalent to <tt>SeedOptions().levelSet().threshold(threshold)</tt><br>
380  Default: false
381  */
383  {
384  mini = LevelSets;
385  thresh = threshold;
386  return *this;
387  }
388 
389  /** Set threshold.
390 
391  The threshold will be used by both the minima and level set variants
392  of seed generation.<br>
393  Default: no thresholding
394  */
396  {
397  thresh = threshold;
398  return *this;
399  }
400 
401  // check whether the threshold has been set for the target type T
402  template <class T>
403  bool thresholdIsValid() const
404  {
405  return thresh < double(NumericTraits<T>::max());
406  }
407 
408  // indicate that this option object is invalid (for internal use in watersheds)
409  SeedOptions & unspecified()
410  {
411  mini = Unspecified;
412  return *this;
413  }
414 };
415 
416 /** \brief Generate seeds for watershed computation and seeded region growing.
417 
418  The source image is a boundary indicator such as the gradient magnitude
419  or the trace of the \ref boundaryTensor(). Seeds are generally generated
420  at locations where the boundaryness (i.e. the likelihood of the point being on the
421  boundary) is very small. In particular, seeds can be placed by either
422  looking for local minima (possibly including minimal plateaus) of the boundaryness,
423  of by looking at level sets (i.e. regions where the boundaryness is below a threshold).
424  Both methods can also be combined, so that only minima below a threshold are returned.
425  The particular seeding strategy is specified by the <tt>options</tt> object
426  (see \ref SeedOptions).
427 
428  The pixel type of the input image must be <tt>LessThanComparable</tt>.
429  The pixel type of the output image must be large enough to hold the labels for all seeds.
430  (typically, you will use <tt>UInt32</tt>). The function will label seeds by consecutive integers
431  (starting from 1) and returns the largest label it used.
432 
433  Pass \ref vigra::NeighborhoodType "IndirectNeighborhood" or \ref vigra::NeighborhoodType "DirectNeighborhood"
434  (first form of the function)
435  or \ref vigra::EightNeighborCode or \ref vigra::FourNeighborCode (second and third forms) to determine the
436  neighborhood where pixel values are compared.
437 
438  <b> Declarations:</b>
439 
440  use arbitrary-dimensional arrays:
441  \code
442  namespace vigra {
443  template <unsigned int N, class T, class S1,
444  class Label, class S2>
445  Label
446  generateWatershedSeeds(MultiArrayView<N, T, S1> const & data,
447  MultiArrayView<N, Label, S2> seeds,
448  NeighborhoodType neighborhood = IndirectNeighborhood,
449  SeedOptions const & options = SeedOptions());
450  }
451  \endcode
452 
453  \deprecatedAPI{generateWatershedSeeds}
454  pass \ref ImageIterators and \ref DataAccessors :
455  \code
456  namespace vigra {
457  template <class SrcIterator, class SrcAccessor,
458  class DestIterator, class DestAccessor,
459  class Neighborhood = EightNeighborCode>
460  unsigned int
461  generateWatershedSeeds(SrcIterator upperlefts, SrcIterator lowerrights, SrcAccessor sa,
462  DestIterator upperleftd, DestAccessor da,
463  Neighborhood neighborhood = EightNeighborCode(),
464  SeedOptions const & options = SeedOptions());
465  }
466  \endcode
467  use argument objects in conjunction with \ref ArgumentObjectFactories :
468  \code
469  namespace vigra {
470  template <class SrcIterator, class SrcAccessor,
471  class DestIterator, class DestAccessor,
472  class Neighborhood = EightNeighborCode>
473  unsigned int
474  generateWatershedSeeds(triple<SrcIterator, SrcIterator, SrcAccessor> src,
475  pair<DestIterator, DestAccessor> dest,
476  Neighborhood neighborhood = EightNeighborCode(),
477  SeedOptions const & options = SeedOptions());
478  }
479  \endcode
480  \deprecatedEnd
481 
482  <b> Usage:</b>
483 
484  <b>\#include</b> <vigra/multi_watersheds.hxx> (MultiArray variant)<br>
485  <b>\#include</b> <vigra/watersheds.hxx> (deprecated variants)<br>
486  Namespace: vigra
487 
488  For detailed examples see \ref watershedsMultiArray() and \ref watershedsRegionGrowing().
489 */
490 doxygen_overloaded_function(template <...> unsigned int generateWatershedSeeds)
491 
492 template <class SrcIterator, class SrcAccessor,
493  class DestIterator, class DestAccessor,
494  class Neighborhood>
495 unsigned int
496 generateWatershedSeeds(SrcIterator upperlefts, SrcIterator lowerrights, SrcAccessor sa,
497  DestIterator upperleftd, DestAccessor da,
498  Neighborhood,
499  SeedOptions const & options = SeedOptions())
500 {
501  using namespace functor;
502  typedef typename SrcAccessor::value_type SrcType;
503 
504  vigra_precondition(options.mini != SeedOptions::LevelSets ||
505  options.thresholdIsValid<SrcType>(),
506  "generateWatershedSeeds(): SeedOptions.levelSets() must be specified with threshold.");
507 
508  Diff2D shape = lowerrights - upperlefts;
509  BImage seeds(shape);
510 
511  if(options.mini == SeedOptions::LevelSets)
512  {
513  transformImage(srcIterRange(upperlefts, lowerrights, sa),
514  destImage(seeds),
515  ifThenElse(Arg1() <= Param(options.thresh), Param(1), Param(0)));
516  }
517  else
518  {
519  LocalMinmaxOptions lm_options;
520  lm_options.neighborhood(Neighborhood::DirectionCount)
521  .markWith(1.0)
522  .allowAtBorder()
523  .allowPlateaus(options.mini == SeedOptions::ExtendedMinima);
524  if(options.thresholdIsValid<SrcType>())
525  lm_options.threshold(options.thresh);
526 
527  localMinima(srcIterRange(upperlefts, lowerrights, sa), destImage(seeds),
528  lm_options);
529  }
530 
531  return labelImageWithBackground(srcImageRange(seeds), destIter(upperleftd, da),
532  Neighborhood::DirectionCount == 8, 0);
533 }
534 
535 template <class SrcIterator, class SrcAccessor,
536  class DestIterator, class DestAccessor>
537 inline unsigned int
538 generateWatershedSeeds(SrcIterator upperlefts, SrcIterator lowerrights, SrcAccessor sa,
539  DestIterator upperleftd, DestAccessor da,
540  SeedOptions const & options = SeedOptions())
541 {
542  return generateWatershedSeeds(upperlefts, lowerrights, sa, upperleftd, da,
543  EightNeighborCode(), options);
544 }
545 
546 template <class SrcIterator, class SrcAccessor,
547  class DestIterator, class DestAccessor,
548  class Neighborhood>
549 inline unsigned int
550 generateWatershedSeeds(triple<SrcIterator, SrcIterator, SrcAccessor> src,
551  pair<DestIterator, DestAccessor> dest,
552  Neighborhood neighborhood,
553  SeedOptions const & options = SeedOptions())
554 {
555  return generateWatershedSeeds(src.first, src.second, src.third,
556  dest.first, dest.second,
557  neighborhood, options);
558 }
559 
560 template <class SrcIterator, class SrcAccessor,
561  class DestIterator, class DestAccessor>
562 inline unsigned int
563 generateWatershedSeeds(triple<SrcIterator, SrcIterator, SrcAccessor> src,
564  pair<DestIterator, DestAccessor> dest,
565  SeedOptions const & options = SeedOptions())
566 {
567  return generateWatershedSeeds(src.first, src.second, src.third,
568  dest.first, dest.second,
569  EightNeighborCode(), options);
570 }
571 
572 /********************************************************/
573 /* */
574 /* watershedsUnionFind */
575 /* */
576 /********************************************************/
577 
578 /** \brief Region segmentation by means of the union-find watershed algorithm.
579 
580  Note: This function is largely obsolete, \ref watershedsMultiArray() should be
581  preferred unless top speed is required.
582 
583  This function implements the union-find version of the watershed algorithms
584  described as algorithm 4.7 in
585 
586  J. Roerdink, R. Meijster: <em>"The watershed transform: definitions, algorithms,
587  and parallelization strategies"</em>, Fundamenta Informaticae, 41:187-228, 2000
588 
589  The source image is a boundary indicator such as the gaussianGradientMagnitude()
590  or the trace of the \ref boundaryTensor(). Local minima of the boundary indicator
591  are used as region seeds, and all other pixels are recursively assigned to the same
592  region as their lowest neighbor. Pass \ref vigra::EightNeighborCode or
593  \ref vigra::FourNeighborCode to determine the neighborhood where pixel values
594  are compared. The pixel type of the input image must be <tt>LessThanComparable</tt>.
595  The function uses accessors.
596 
597  Note that VIGRA provides an alternative implementation of the watershed transform via
598  \ref watershedsRegionGrowing(). It is slower, but offers many more configuration options.
599 
600  <b> Declarations:</b>
601 
602  pass 2D array views:
603  \code
604  namespace vigra {
605  template <class T1, class S1,
606  class T2, class S2,
607  class Neighborhood>
608  unsigned int
609  watershedsUnionFind(MultiArrayView<2, T1, S1> const & src,
610  MultiArrayView<2, T2, S2> dest,
611  Neighborhood neighborhood = EightNeighborCode());
612  }
613  \endcode
614 
615  \deprecatedAPI{watershedsUnionFind}
616  pass \ref ImageIterators and \ref DataAccessors :
617  \code
618  namespace vigra {
619  template <class SrcIterator, class SrcAccessor,
620  class DestIterator, class DestAccessor,
621  class Neighborhood = EightNeighborCode>
622  unsigned int
623  watershedsUnionFind(SrcIterator upperlefts, SrcIterator lowerrights, SrcAccessor sa,
624  DestIterator upperleftd, DestAccessor da,
625  Neighborhood neighborhood = EightNeighborCode())
626  }
627  \endcode
628  use argument objects in conjunction with \ref ArgumentObjectFactories :
629  \code
630  namespace vigra {
631  template <class SrcIterator, class SrcAccessor,
632  class DestIterator, class DestAccessor,
633  class Neighborhood = EightNeighborCode>
634  unsigned int
635  watershedsUnionFind(triple<SrcIterator, SrcIterator, SrcAccessor> src,
636  pair<DestIterator, DestAccessor> dest,
637  Neighborhood neighborhood = EightNeighborCode())
638  }
639  \endcode
640  \deprecatedEnd
641 
642  <b> Usage:</b>
643 
644  <b>\#include</b> <vigra/watersheds.hxx><br>
645  Namespace: vigra
646 
647  Example: watersheds of the gradient magnitude.
648 
649  \code
650  MultiArray<2, float> in(w,h);
651  ... // read input data
652 
653  // compute gradient magnitude as boundary indicator
654  MultiArray<2, float> gradMag(w, h);
655  gaussianGradientMagnitude(src, gradMag, 3.0);
656 
657  // the pixel type of the destination image must be large enough to hold
658  // numbers up to 'max_region_label' to prevent overflow
659  MultiArray<2, unsigned int> labeling(w,h);
660  unsigned int max_region_label = watershedsUnionFind(gradMag, labeling);
661  \endcode
662 
663  \deprecatedUsage{watershedsUnionFind}
664  Example: watersheds of the gradient magnitude.
665 
666  \code
667  vigra::BImage in(w,h);
668  ... // read input data
669 
670  // compute gradient magnitude as boundary indicator
671  vigra::FImage gradMag(w, h);
672  gaussianGradientMagnitude(srcImageRange(src), destImage(gradMag), 3.0);
673 
674  // the pixel type of the destination image must be large enough to hold
675  // numbers up to 'max_region_label' to prevent overflow
676  vigra::IImage labeling(w,h);
677  int max_region_label = watershedsUnionFind(srcImageRange(gradMag), destImage(labeling));
678 
679  \endcode
680  <b> Required Interface:</b>
681  \code
682  SrcIterator src_upperleft, src_lowerright;
683  DestIterator dest_upperleft;
684 
685  SrcAccessor src_accessor;
686  DestAccessor dest_accessor;
687 
688  // compare src values
689  src_accessor(src_upperleft) <= src_accessor(src_upperleft)
690 
691  // set result
692  int label;
693  dest_accessor.set(label, dest_upperleft);
694  \endcode
695  \deprecatedEnd
696 */
697 doxygen_overloaded_function(template <...> unsigned int watershedsUnionFind)
698 
699 template <class SrcIterator, class SrcAccessor,
700  class DestIterator, class DestAccessor,
701  class Neighborhood>
702 unsigned int
703 watershedsUnionFind(SrcIterator upperlefts, SrcIterator lowerrights, SrcAccessor sa,
704  DestIterator upperleftd, DestAccessor da,
705  Neighborhood neighborhood)
706 {
707  SImage orientationImage(lowerrights - upperlefts);
708 
709  prepareWatersheds(upperlefts, lowerrights, sa,
710  orientationImage.upperLeft(), orientationImage.accessor(), neighborhood);
711  return watershedLabeling(orientationImage.upperLeft(), orientationImage.lowerRight(), orientationImage.accessor(),
712  upperleftd, da, neighborhood);
713 }
714 
715 template <class SrcIterator, class SrcAccessor,
716  class DestIterator, class DestAccessor>
717 inline unsigned int
718 watershedsUnionFind(SrcIterator upperlefts, SrcIterator lowerrights, SrcAccessor sa,
719  DestIterator upperleftd, DestAccessor da)
720 {
721  return watershedsUnionFind(upperlefts, lowerrights, sa, upperleftd, da, EightNeighborCode());
722 }
723 
724 template <class SrcIterator, class SrcAccessor,
725  class DestIterator, class DestAccessor,
726  class Neighborhood>
727 inline unsigned int
728 watershedsUnionFind(triple<SrcIterator, SrcIterator, SrcAccessor> src,
729  pair<DestIterator, DestAccessor> dest, Neighborhood neighborhood)
730 {
731  return watershedsUnionFind(src.first, src.second, src.third,
732  dest.first, dest.second, neighborhood);
733 }
734 
735 template <class SrcIterator, class SrcAccessor,
736  class DestIterator, class DestAccessor>
737 inline unsigned int
738 watershedsUnionFind(triple<SrcIterator, SrcIterator, SrcAccessor> src,
739  pair<DestIterator, DestAccessor> dest)
740 {
741  return watershedsUnionFind(src.first, src.second, src.third,
742  dest.first, dest.second);
743 }
744 
745 template <class T1, class S1,
746  class T2, class S2,
747  class Neighborhood>
748 inline unsigned int
749 watershedsUnionFind(MultiArrayView<2, T1, S1> const & src,
750  MultiArrayView<2, T2, S2> dest, Neighborhood neighborhood)
751 {
752  return watershedsUnionFind(srcImageRange(src),
753  destImage(dest), neighborhood);
754 }
755 
756 template <class T1, class S1,
757  class T2, class S2>
758 inline unsigned int
759 watershedsUnionFind(MultiArrayView<2, T1, S1> const & src,
760  MultiArrayView<2, T2, S2> dest)
761 {
762  vigra_precondition(src.shape() == dest.shape(),
763  "watershedsUnionFind(): shape mismatch between input and output.");
764  return watershedsUnionFind(srcImageRange(src),
765  destImage(dest));
766 }
767 
768 /** \brief Options object for watershed algorithms.
769 
770  <b> Usage:</b>
771 
772  see \ref watershedsMultiArray() and watershedsRegionGrowing() for detailed examples.
773 */
775 {
776  public:
777  enum Method { RegionGrowing, UnionFind };
778 
779  double max_cost, bias;
780  SRGType terminate;
781  Method method;
782  unsigned int biased_label, bucket_count;
783  SeedOptions seed_options;
784 
785 
786 
787  /** \brief Create options object with default settings.
788 
789  Defaults are: perform complete grow (all pixels are assigned to regions),
790  use standard algorithm, assume that the destination image already contains
791  region seeds.
792  */
794  : max_cost(0.0),
795  bias(1.0),
796  terminate(CompleteGrow),
797  method(RegionGrowing),
798  biased_label(0),
799  bucket_count(0),
800  seed_options(SeedOptions().unspecified())
801  {}
802 
803  /** \brief Perform complete grow.
804 
805  That is, all pixels are assigned to regions, without explicit contours
806  in between.
807 
808  Default: true
809  */
811  {
812  terminate = SRGType(CompleteGrow | (terminate & StopAtThreshold));
813  return *this;
814  }
815 
816  /** \brief Keep one-pixel wide contour between regions.
817 
818  Note that this option is unsupported by the turbo algorithm.
819 
820  Default: false
821  */
823  {
824  terminate = SRGType(KeepContours | (terminate & StopAtThreshold));
825  return *this;
826  }
827 
828  /** \brief Set \ref SRGType explicitly.
829 
830  Default: CompleteGrow
831  */
833  {
834  terminate = type;
835  return *this;
836  }
837 
838  /** \brief Stop region growing when the boundaryness exceeds the threshold.
839 
840  This option may be combined with completeGrow() and keepContours().
841 
842  Default: no early stopping
843  */
844  WatershedOptions & stopAtThreshold(double threshold)
845  {
846  terminate = SRGType(terminate | StopAtThreshold);
847  max_cost = threshold;
848  return *this;
849  }
850 
851  /** \brief Use a simpler, but faster region growing algorithm.
852 
853  The algorithm internally uses a \ref BucketQueue to determine
854  the processing order of the pixels. This is only useful,
855  when the input boundary indicator image contains integers
856  in the range <tt>[0, ..., bucket_count-1]</tt>. Since
857  these boundary indicators are typically represented as
858  UInt8 images, the default <tt>bucket_count</tt> is 256.
859 
860  Default: don't use the turbo algorithm
861  */
862  WatershedOptions & turboAlgorithm(unsigned int bucket_count = 256)
863  {
864  this->bucket_count = bucket_count;
865  method = RegionGrowing;
866  return *this;
867  }
868 
869  /** \brief Specify seed options.
870 
871  In this case, watershedsRegionGrowing() assumes that the destination
872  image does not yet contain seeds. It will therefore call
873  generateWatershedSeeds() and pass on the seed options.
874 
875  Default: don't compute seeds (i.e. assume that destination image already
876  contains seeds).
877  */
879  {
880  seed_options = s;
881  return *this;
882  }
883 
884  /** \brief Bias the cost of the specified region by the given factor.
885 
886  In certain applications, one region (typically the background) should
887  be preferred in region growing. This is most easily achieved
888  by adjusting the assignment cost for that region as <tt>factor*cost</tt>,
889  with a factor slightly below 1.
890 
891  Default: don't bias any region.
892  */
893  WatershedOptions & biasLabel(unsigned int label, double factor)
894  {
895  biased_label = label;
896  bias = factor;
897  return *this;
898  }
899 
900  /** \brief Specify the algorithm to be used.
901 
902  Possible values are <tt>WatershedOptions::RegionGrowing</tt> and
903  <tt>WatershedOptions::UnionFind</tt>. The latter algorithm is fastest
904  but doesn't support seeds and any of the other options.
905 
906  Default: RegionGrowing.
907  */
908  WatershedOptions & useMethod(Method method)
909  {
910  this->method = method;
911  return *this;
912  }
913 
914  /** \brief Use region-growing watershed.
915 
916  Use this method when you want to specify seeds explicitly (seeded watersheds)
917  or use any of the other options.
918 
919  Default: true.
920  */
922  {
923  method = RegionGrowing;
924  return *this;
925  }
926 
927  /** \brief Use union-find watershed.
928 
929  This is the fasted method, but it doesn't support seeds and any of the other
930  options (they will be silently ignored).
931 
932  Default: false.
933  */
935  {
936  method = UnionFind;
937  return *this;
938  }
939 };
940 
941 namespace detail {
942 
943 template <class CostType, class LabelType>
944 class WatershedStatistics
945 {
946  public:
947 
948  typedef SeedRgDirectValueFunctor<CostType> value_type;
949  typedef value_type & reference;
950  typedef value_type const & const_reference;
951 
952  typedef CostType first_argument_type;
953  typedef LabelType second_argument_type;
954  typedef LabelType argument_type;
955 
956  WatershedStatistics()
957  {}
958 
959  void resize(unsigned int)
960  {}
961 
962  void reset()
963  {}
964 
965  /** update regions statistics (do nothing in the watershed algorithm)
966  */
967  template <class T1, class T2>
968  void operator()(first_argument_type const &, second_argument_type const &)
969  {}
970 
971  /** ask for maximal index (label) allowed
972  */
973  LabelType maxRegionLabel() const
974  { return size() - 1; }
975 
976  /** ask for array size (i.e. maxRegionLabel() + 1)
977  */
978  LabelType size() const
979  { return NumericTraits<LabelType>::max(); }
980 
981  /** read the statistics functor for a region via its label
982  */
983  const_reference operator[](argument_type) const
984  { return stats; }
985 
986  /** access the statistics functor for a region via its label
987  */
988  reference operator[](argument_type)
989  { return stats; }
990 
991  value_type stats;
992 };
993 
994 template <class Value>
995 class SeedRgBiasedValueFunctor
996 {
997  public:
998  double bias;
999 
1000  /* the functor's argument type
1001  */
1002  typedef Value argument_type;
1003 
1004  /* the functor's result type (unused, only necessary for
1005  use of SeedRgDirectValueFunctor in \ref vigra::ArrayOfRegionStatistics
1006  */
1007  typedef Value result_type;
1008 
1009  /* the return type of the cost() function
1010  */
1011  typedef Value cost_type;
1012 
1013  SeedRgBiasedValueFunctor(double b = 1.0)
1014  : bias(b)
1015  {}
1016 
1017  /* Do nothing (since we need not update region statistics).
1018  */
1019  void operator()(argument_type const &) const {}
1020 
1021  /* Return scaled argument
1022  */
1023  cost_type cost(argument_type const & v) const
1024  {
1025  return cost_type(bias*v);
1026  }
1027 };
1028 
1029 template <class CostType, class LabelType>
1030 class BiasedWatershedStatistics
1031 {
1032  public:
1033 
1034  typedef SeedRgBiasedValueFunctor<CostType> value_type;
1035  typedef value_type & reference;
1036  typedef value_type const & const_reference;
1037 
1038  typedef CostType first_argument_type;
1039  typedef LabelType second_argument_type;
1040  typedef LabelType argument_type;
1041 
1042  BiasedWatershedStatistics(LabelType biasedLabel, double bias)
1043  : biased_label(biasedLabel),
1044  biased_stats(bias)
1045  {}
1046 
1047  void resize(unsigned int)
1048  {}
1049 
1050  void reset()
1051  {}
1052 
1053  /** update regions statistics (do nothing in the watershed algorithm)
1054  */
1055  template <class T1, class T2>
1056  void operator()(first_argument_type const &, second_argument_type const &)
1057  {}
1058 
1059  /** ask for maximal index (label) allowed
1060  */
1061  LabelType maxRegionLabel() const
1062  { return size() - 1; }
1063 
1064  /** ask for array size (i.e. maxRegionLabel() + 1)
1065  */
1066  LabelType size() const
1067  { return NumericTraits<LabelType>::max(); }
1068 
1069  /** read the statistics functor for a region via its label
1070  */
1071  const_reference operator[](argument_type label) const
1072  {
1073  return (label == biased_label)
1074  ? biased_stats
1075  : stats;
1076  }
1077 
1078  /** access the statistics functor for a region via its label
1079  */
1080  reference operator[](argument_type label)
1081  {
1082  return (label == biased_label)
1083  ? biased_stats
1084  : stats;
1085  }
1086 
1087  LabelType biased_label;
1088  value_type stats, biased_stats;
1089 };
1090 
1091 } // namespace detail
1092 
1093 /** \brief Region segmentation by means of a flooding-based watershed algorithm.
1094 
1095  Note: This function is largely obsolete, \ref watershedsMultiArray() should be
1096  preferred unless top speed is required.
1097 
1098  This function implements variants of the watershed algorithm
1099  described in
1100 
1101  L. Vincent and P. Soille: <em>"Watersheds in digital spaces: An efficient algorithm
1102  based on immersion simulations"</em>, IEEE Trans. Patt. Analysis Mach. Intell. 13(6):583-598, 1991
1103 
1104  The source image is a boundary indicator such as the gaussianGradientMagnitude()
1105  or the trace of the \ref boundaryTensor(), and the destination is a label image
1106  designating membership of each point in one of the regions. Plateaus in the boundary
1107  indicator (i.e. regions of constant gray value) are handled via a Euclidean distance
1108  transform by default.
1109 
1110  By default, the destination image is assumed to hold seeds for a seeded watershed
1111  transform. Seeds may, for example, be created by means of generateWatershedSeeds().
1112  Note that the seeds will be overridden with the final watershed segmentation.
1113 
1114  Alternatively, you may provide \ref SeedOptions in order to instruct
1115  watershedsRegionGrowing() to generate its own seeds (it will call generateWatershedSeeds()
1116  internally). In that case, the destination image should be zero-initialized.
1117 
1118  You can specify the neighborhood system to be used by passing \ref FourNeighborCode
1119  or \ref EightNeighborCode (default).
1120 
1121  Further options to be specified via \ref WatershedOptions are:
1122 
1123  <ul>
1124  <li> Whether to keep a 1-pixel-wide contour (with label 0) between regions or
1125  perform complete grow (i.e. all pixels are assigned to a region).
1126  <li> Whether to stop growing when the boundaryness exceeds a threshold (remaining
1127  pixels keep label 0).
1128  <li> Whether to use a faster, but less powerful algorithm ("turbo algorithm"). It
1129  is faster because it orders pixels by means of a \ref BucketQueue (therefore,
1130  the boundary indicator must contain integers in the range
1131  <tt>[0, ..., bucket_count-1]</tt>, where <tt>bucket_count</tt> is specified in
1132  the options object), it only supports complete growing (no contour between regions
1133  is possible), and it handles plateaus in a simplistic way. It also saves some
1134  memory because it allocates less temporary storage.
1135  <li> Whether one region (label) is to be preferred or discouraged by biasing its cost
1136  with a given factor (smaller than 1 for preference, larger than 1 for discouragement).
1137  </ul>
1138 
1139  Note that VIGRA provides an alternative implementation of the watershed transform via
1140  \ref watershedsUnionFind().
1141 
1142  <b> Declarations:</b>
1143 
1144  pass 2D array views:
1145  \code
1146  namespace vigra {
1147  template <class T1, class S1,
1148  class T2, class S2,
1149  class Neighborhood = EightNeighborCode>
1150  unsigned int
1151  watershedsRegionGrowing(MultiArrayView<2, T1, S1> const & src,
1152  MultiArrayView<2, T2, S2> dest,
1153  Neighborhood neighborhood = EightNeighborCode(),
1154  WatershedOptions const & options = WatershedOptions());
1155 
1156  template <class T1, class S1,
1157  class T2, class S2>
1158  unsigned int
1159  watershedsRegionGrowing(MultiArrayView<2, T1, S1> const & src,
1160  MultiArrayView<2, T2, S2> dest,
1161  WatershedOptions const & options = WatershedOptions());
1162  }
1163  \endcode
1164 
1165  \deprecatedAPI{watershedsRegionGrowing}
1166  pass \ref ImageIterators and \ref DataAccessors :
1167  \code
1168  namespace vigra {
1169  template <class SrcIterator, class SrcAccessor,
1170  class DestIterator, class DestAccessor,
1171  class Neighborhood = EightNeighborCode>
1172  unsigned int
1173  watershedsRegionGrowing(SrcIterator upperlefts, SrcIterator lowerrights, SrcAccessor sa,
1174  DestIterator upperleftd, DestAccessor da,
1175  Neighborhood neighborhood = EightNeighborCode(),
1176  WatershedOptions const & options = WatershedOptions());
1177 
1178  template <class SrcIterator, class SrcAccessor,
1179  class DestIterator, class DestAccessor>
1180  unsigned int
1181  watershedsRegionGrowing(SrcIterator upperlefts, SrcIterator lowerrights, SrcAccessor sa,
1182  DestIterator upperleftd, DestAccessor da,
1183  WatershedOptions const & options = WatershedOptions());
1184  }
1185  \endcode
1186  use argument objects in conjunction with \ref ArgumentObjectFactories :
1187  \code
1188  namespace vigra {
1189  template <class SrcIterator, class SrcAccessor,
1190  class DestIterator, class DestAccessor,
1191  class Neighborhood = EightNeighborCode>
1192  unsigned int
1193  watershedsRegionGrowing(triple<SrcIterator, SrcIterator, SrcAccessor> src,
1194  pair<DestIterator, DestAccessor> dest,
1195  Neighborhood neighborhood = EightNeighborCode(),
1196  WatershedOptions const & options = WatershedOptions());
1197 
1198  template <class SrcIterator, class SrcAccessor,
1199  class DestIterator, class DestAccessor>
1200  unsigned int
1201  watershedsRegionGrowing(triple<SrcIterator, SrcIterator, SrcAccessor> src,
1202  pair<DestIterator, DestAccessor> dest,
1203  WatershedOptions const & options = WatershedOptions());
1204  }
1205  \endcode
1206  \deprecatedEnd
1207 
1208  <b> Usage:</b>
1209 
1210  <b>\#include</b> <vigra/watersheds.hxx><br>
1211  Namespace: vigra
1212 
1213  Example: watersheds of the gradient magnitude.
1214 
1215  \code
1216  MultiArray<2, float> src(w, h);
1217  ... // read input data
1218 
1219  // compute gradient magnitude at scale 1.0 as a boundary indicator
1220  MultiArray<2, float> gradMag(w, h);
1221  gaussianGradientMagnitude(src, gradMag, 1.0);
1222 
1223  // example 1
1224  {
1225  // the pixel type of the destination image must be large enough to hold
1226  // numbers up to 'max_region_label' to prevent overflow
1227  MultiArray<2, unsigned int> labeling(w, h);
1228 
1229  // call watershed algorithm for 4-neighborhood, leave a 1-pixel boundary between regions,
1230  // and autogenerate seeds from all gradient minima where the magnitude is below 2.0
1231  unsigned int max_region_label =
1232  watershedsRegionGrowing(gradMag, labeling,
1233  FourNeighborCode(),
1234  WatershedOptions().keepContours()
1235  .seedOptions(SeedOptions().minima().threshold(2.0)));
1236  }
1237 
1238  // example 2
1239  {
1240  MultiArray<2, unsigned int> labeling(w, h);
1241 
1242  // compute seeds beforehand (use connected components of all pixels
1243  // where the gradient is below 4.0)
1244  unsigned int max_region_label =
1245  generateWatershedSeeds(gradMag, labeling,
1246  SeedOptions().levelSets(4.0));
1247 
1248  // quantize the gradient image to 256 gray levels
1249  MultiArray<2, unsigned char> gradMag256(w, h);
1250  FindMinMax<float> minmax;
1251  inspectImage(gradMag, minmax); // find original range
1252  transformImage(gradMag, gradMag256,
1253  linearRangeMapping(minmax, 0, 255));
1254 
1255  // call the turbo algorithm with 256 bins, using 8-neighborhood
1256  watershedsRegionGrowing(gradMag256, labeling,
1257  WatershedOptions().turboAlgorithm(256));
1258  }
1259 
1260  // example 3
1261  {
1262  MultiArray<2, unsigned int> labeling(w, h);
1263 
1264  .. // get seeds from somewhere, e.g. an interactive labeling program,
1265  // make sure that label 1 corresponds to the background
1266 
1267  // bias the watershed algorithm so that the background is preferred
1268  // by reducing the cost for label 1 to 90%
1269  watershedsRegionGrowing(gradMag, labeling,
1270  WatershedOptions().biasLabel(1, 0.9));
1271  }
1272  \endcode
1273 
1274  \deprecatedUsage{watershedsRegionGrowing}
1275  \code
1276  vigra::BImage src(w, h);
1277  ... // read input data
1278 
1279  // compute gradient magnitude at scale 1.0 as a boundary indicator
1280  vigra::FImage gradMag(w, h);
1281  gaussianGradientMagnitude(srcImageRange(src), destImage(gradMag), 1.0);
1282 
1283  // example 1
1284  {
1285  // the pixel type of the destination image must be large enough to hold
1286  // numbers up to 'max_region_label' to prevent overflow
1287  vigra::IImage labeling(w, h);
1288 
1289  // call watershed algorithm for 4-neighborhood, leave a 1-pixel boundary between regions,
1290  // and autogenerate seeds from all gradient minima where the magnitude is below 2.0
1291  unsigned int max_region_label =
1292  watershedsRegionGrowing(srcImageRange(gradMag), destImage(labeling),
1293  FourNeighborCode(),
1294  WatershedOptions().keepContours()
1295  .seedOptions(SeedOptions().minima().threshold(2.0)));
1296  }
1297 
1298  // example 2
1299  {
1300  vigra::IImage labeling(w, h);
1301 
1302  // compute seeds beforehand (use connected components of all pixels
1303  // where the gradient is below 4.0)
1304  unsigned int max_region_label =
1305  generateWatershedSeeds(srcImageRange(gradMag), destImage(labeling),
1306  SeedOptions().levelSets(4.0));
1307 
1308  // quantize the gradient image to 256 gray levels
1309  vigra::BImage gradMag256(w, h);
1310  vigra::FindMinMax<float> minmax;
1311  inspectImage(srcImageRange(gradMag), minmax); // find original range
1312  transformImage(srcImageRange(gradMag), destImage(gradMag256),
1313  linearRangeMapping(minmax, 0, 255));
1314 
1315  // call the turbo algorithm with 256 bins, using 8-neighborhood
1316  watershedsRegionGrowing(srcImageRange(gradMag256), destImage(labeling),
1317  WatershedOptions().turboAlgorithm(256));
1318  }
1319 
1320  // example 3
1321  {
1322  vigra::IImage labeling(w, h);
1323 
1324  .. // get seeds from somewhere, e.g. an interactive labeling program,
1325  // make sure that label 1 corresponds to the background
1326 
1327  // bias the watershed algorithm so that the background is preferred
1328  // by reducing the cost for label 1 to 90%
1329  watershedsRegionGrowing(srcImageRange(gradMag), destImage(labeling),
1330  WatershedOptions().biasLabel(1, 0.9));
1331  }
1332  \endcode
1333  <b> Required Interface:</b>
1334  \code
1335  SrcIterator src_upperleft, src_lowerright;
1336  DestIterator dest_upperleft;
1337 
1338  SrcAccessor src_accessor;
1339  DestAccessor dest_accessor;
1340 
1341  // compare src values
1342  src_accessor(src_upperleft) <= src_accessor(src_upperleft)
1343 
1344  // set result
1345  int label;
1346  dest_accessor.set(label, dest_upperleft);
1347  \endcode
1348  \deprecatedEnd
1349 */
1350 doxygen_overloaded_function(template <...> unsigned int watershedsRegionGrowing)
1351 
1352 template <class SrcIterator, class SrcAccessor,
1353  class DestIterator, class DestAccessor,
1354  class Neighborhood>
1355 unsigned int
1356 watershedsRegionGrowing(SrcIterator upperlefts, SrcIterator lowerrights, SrcAccessor sa,
1357  DestIterator upperleftd, DestAccessor da,
1358  Neighborhood neighborhood,
1359  WatershedOptions const & options = WatershedOptions())
1360 {
1361  typedef typename SrcAccessor::value_type ValueType;
1362  typedef typename DestAccessor::value_type LabelType;
1363 
1364  unsigned int max_region_label = 0;
1365 
1366  if(options.seed_options.mini != SeedOptions::Unspecified)
1367  {
1368  // we are supposed to compute seeds
1369  max_region_label =
1370  generateWatershedSeeds(srcIterRange(upperlefts, lowerrights, sa),
1371  destIter(upperleftd, da),
1372  neighborhood, options.seed_options);
1373  }
1374 
1375  if(options.biased_label != 0)
1376  {
1377  // create a statistics functor for biased region growing
1378  detail::BiasedWatershedStatistics<ValueType, LabelType>
1379  regionstats(options.biased_label, options.bias);
1380 
1381  // perform region growing, starting from the seeds computed above
1382  if(options.bucket_count == 0)
1383  {
1384  max_region_label =
1385  seededRegionGrowing(srcIterRange(upperlefts, lowerrights, sa),
1386  srcIter(upperleftd, da),
1387  destIter(upperleftd, da),
1388  regionstats, options.terminate, neighborhood, options.max_cost);
1389  }
1390  else
1391  {
1392  max_region_label =
1393  fastSeededRegionGrowing(srcIterRange(upperlefts, lowerrights, sa),
1394  destIter(upperleftd, da),
1395  regionstats, options.terminate,
1396  neighborhood, options.max_cost, options.bucket_count);
1397  }
1398  }
1399  else
1400  {
1401  // create a statistics functor for region growing
1402  detail::WatershedStatistics<ValueType, LabelType> regionstats;
1403 
1404  // perform region growing, starting from the seeds computed above
1405  if(options.bucket_count == 0)
1406  {
1407  max_region_label =
1408  seededRegionGrowing(srcIterRange(upperlefts, lowerrights, sa),
1409  srcIter(upperleftd, da),
1410  destIter(upperleftd, da),
1411  regionstats, options.terminate, neighborhood, options.max_cost);
1412  }
1413  else
1414  {
1415  max_region_label =
1416  fastSeededRegionGrowing(srcIterRange(upperlefts, lowerrights, sa),
1417  destIter(upperleftd, da),
1418  regionstats, options.terminate,
1419  neighborhood, options.max_cost, options.bucket_count);
1420  }
1421  }
1422 
1423  return max_region_label;
1424 }
1425 
1426 template <class SrcIterator, class SrcAccessor,
1427  class DestIterator, class DestAccessor>
1428 inline unsigned int
1429 watershedsRegionGrowing(SrcIterator upperlefts, SrcIterator lowerrights, SrcAccessor sa,
1430  DestIterator upperleftd, DestAccessor da,
1431  WatershedOptions const & options = WatershedOptions())
1432 {
1433  return watershedsRegionGrowing(upperlefts, lowerrights, sa, upperleftd, da,
1434  EightNeighborCode(), options);
1435 }
1436 
1437 template <class SrcIterator, class SrcAccessor,
1438  class DestIterator, class DestAccessor,
1439  class Neighborhood>
1440 inline unsigned int
1441 watershedsRegionGrowing(triple<SrcIterator, SrcIterator, SrcAccessor> src,
1442  pair<DestIterator, DestAccessor> dest,
1443  Neighborhood neighborhood,
1444  WatershedOptions const & options = WatershedOptions())
1445 {
1446  return watershedsRegionGrowing(src.first, src.second, src.third,
1447  dest.first, dest.second,
1448  neighborhood, options);
1449 }
1450 
1451 template <class SrcIterator, class SrcAccessor,
1452  class DestIterator, class DestAccessor>
1453 inline unsigned int
1454 watershedsRegionGrowing(triple<SrcIterator, SrcIterator, SrcAccessor> src,
1455  pair<DestIterator, DestAccessor> dest,
1456  WatershedOptions const & options = WatershedOptions())
1457 {
1458  return watershedsRegionGrowing(src.first, src.second, src.third,
1459  dest.first, dest.second,
1460  EightNeighborCode(), options);
1461 }
1462 
1463 template <class T1, class S1,
1464  class T2, class S2,
1465  class Neighborhood>
1466 inline unsigned int
1467 watershedsRegionGrowing(MultiArrayView<2, T1, S1> const & src,
1468  MultiArrayView<2, T2, S2> dest,
1469  Neighborhood neighborhood,
1470  WatershedOptions const & options = WatershedOptions())
1471 {
1472  vigra_precondition(src.shape() == dest.shape(),
1473  "watershedsRegionGrowing(): shape mismatch between input and output.");
1474  return watershedsRegionGrowing(srcImageRange(src),
1475  destImage(dest),
1476  neighborhood, options);
1477 }
1478 
1479 template <class T1, class S1,
1480  class T2, class S2>
1481 inline unsigned int
1482 watershedsRegionGrowing(MultiArrayView<2, T1, S1> const & src,
1483  MultiArrayView<2, T2, S2> dest,
1484  WatershedOptions const & options = WatershedOptions())
1485 {
1486  vigra_precondition(src.shape() == dest.shape(),
1487  "watershedsRegionGrowing(): shape mismatch between input and output.");
1488  return watershedsRegionGrowing(srcImageRange(src),
1489  destImage(dest),
1490  EightNeighborCode(), options);
1491 }
1492 
1493 //@}
1494 
1495 } // namespace vigra
1496 
1497 #endif // VIGRA_WATERSHEDS_HXX
SeedOptions & threshold(double threshold)
Definition: watersheds.hxx:395
WatershedOptions & completeGrow()
Perform complete grow.
Definition: watersheds.hxx:810
SRGType
Definition: seededregiongrowing.hxx:176
 
Definition: pixelneighborhood.hxx:437
SeedOptions & minima()
Definition: watersheds.hxx:350
unsigned int watershedsUnionFind(...)
Region segmentation by means of the union-find watershed algorithm.
WatershedOptions()
Create options object with default settings.
Definition: watersheds.hxx:793
WatershedOptions & regionGrowing()
Use region-growing watershed.
Definition: watersheds.hxx:921
void transformImage(...)
Apply unary point transformation to each pixel.
WatershedOptions & unionFind()
Use union-find watershed.
Definition: watersheds.hxx:934
SeedOptions & levelSets(double threshold)
Definition: watersheds.hxx:382
void localMinima(...)
Find local minima in an image or multi-dimensional array.
AtImageBorder
Encode whether a point is near the image border.
Definition: pixelneighborhood.hxx:68
AtImageBorder isAtImageBorder(int x, int y, int width, int height)
Find out whether a point is at the image border.
Definition: pixelneighborhood.hxx:111
WatershedOptions & useMethod(Method method)
Specify the algorithm to be used.
Definition: watersheds.hxx:908
WatershedOptions & seedOptions(SeedOptions const &s)
Specify seed options.
Definition: watersheds.hxx:878
unsigned int labelImageWithBackground(...)
Find the connected components of a segmented image, excluding the background from labeling...
BasicImage< UInt8 > BImage
Definition: stdimage.hxx:62
WatershedOptions & turboAlgorithm(unsigned int bucket_count=256)
Use a simpler, but faster region growing algorithm.
Definition: watersheds.hxx:862
WatershedOptions & keepContours()
Keep one-pixel wide contour between regions.
Definition: watersheds.hxx:822
BasicImage< Int16 > SImage
Definition: stdimage.hxx:89
Options object for watershed algorithms.
Definition: watersheds.hxx:774
SeedOptions()
Construct default options object.
Definition: watersheds.hxx:341
WatershedOptions & srgType(SRGType type)
Set SRGType explicitly.
Definition: watersheds.hxx:832
doxygen_overloaded_function(template<...> void separableConvolveBlockwise) template< unsigned int N
Separated convolution on ChunkedArrays.
void seededRegionGrowing(...)
Region Segmentation by means of Seeded Region Growing.
WatershedOptions & biasLabel(unsigned int label, double factor)
Bias the cost of the specified region by the given factor.
Definition: watersheds.hxx:893
WatershedOptions & stopAtThreshold(double threshold)
Stop region growing when the boundaryness exceeds the threshold.
Definition: watersheds.hxx:844
SeedOptions & levelSets()
Definition: watersheds.hxx:371
FourNeighborhood::NeighborCode FourNeighborCode
Definition: pixelneighborhood.hxx:379
Options object for generateWatershedSeeds().
Definition: watersheds.hxx:329
unsigned int watershedsRegionGrowing(...)
Region segmentation by means of a flooding-based watershed algorithm.
 
Definition: pixelneighborhood.hxx:70
EightNeighborhood::NeighborCode EightNeighborCode
Definition: pixelneighborhood.hxx:687
SeedOptions & extendedMinima()
Definition: watersheds.hxx:360

© 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 (Thu Mar 17 2016)