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

© 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 (Tue Dec 31 2013)