36#ifndef VIGRA_WATERSHEDS_HXX
37#define VIGRA_WATERSHEDS_HXX
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"
52template <
class SrcIterator,
class SrcAccessor,
53 class DestIterator,
class DestAccessor,
55unsigned int watershedLabeling(SrcIterator upperlefts,
56 SrcIterator lowerrights, SrcAccessor sa,
57 DestIterator upperleftd, DestAccessor da,
60 typedef typename DestAccessor::value_type LabelType;
62 int w = lowerrights.x - upperlefts.x;
63 int h = lowerrights.y - upperlefts.y;
66 SrcIterator ys(upperlefts);
68 DestIterator yd(upperleftd);
72 UnionFindArray<LabelType> labels;
75 NeighborOffsetCirculator<Neighborhood> ncstart(Neighborhood::CausalFirst);
76 NeighborOffsetCirculator<Neighborhood> ncstartBorder(Neighborhood::North);
77 NeighborOffsetCirculator<Neighborhood> ncend(Neighborhood::CausalLast);
79 NeighborOffsetCirculator<Neighborhood> ncendBorder(Neighborhood::North);
95 da.set(labels.finalizeIndex(labels.nextFreeIndex()), xd);
99 for(x = 1; x != w; ++x, ++xs.x, ++xd.x)
101 if((sa(xs) & Neighborhood::directionBit(Neighborhood::West)) ||
102 (sa(xs, Neighborhood::west()) & Neighborhood::directionBit(Neighborhood::East)))
104 da.set(da(xd, Neighborhood::west()), xd);
108 da.set(labels.finalizeIndex(labels.nextFreeIndex()), xd);
114 for(y = 1; y != h; ++y, ++ys.y, ++yd.y)
119 for(x = 0; x != w; ++x, ++xs.x, ++xd.x)
121 NeighborOffsetCirculator<Neighborhood> nc(x == w-1
124 NeighborOffsetCirculator<Neighborhood> nce(x == 0
127 LabelType currentIndex = labels.nextFreeIndex();
128 for(; nc != nce; ++nc)
130 if((sa(xs) & nc.directionBit()) || (sa(xs, *nc) & nc.oppositeDirectionBit()))
132 currentIndex = labels.makeUnion(da(xd,*nc), currentIndex);
135 da.set(labels.finalizeIndex(currentIndex), xd);
139 unsigned int count = labels.makeContiguous();
144 for(y=0; y != h; ++y, ++yd.y)
147 for(x = 0; x != w; ++x, ++xd.x)
149 da.set(labels.findLabel(da(xd)), xd);
155template <
class SrcIterator,
class SrcAccessor,
156 class DestIterator,
class DestAccessor,
158unsigned int watershedLabeling(triple<SrcIterator, SrcIterator, SrcAccessor> src,
159 pair<DestIterator, DestAccessor> dest,
160 Neighborhood neighborhood)
162 return watershedLabeling(src.first, src.second, src.third,
163 dest.first, dest.second, neighborhood);
167template <
class SrcIterator,
class SrcAccessor,
168 class DestIterator,
class DestAccessor>
169void prepareWatersheds(SrcIterator upperlefts, SrcIterator lowerrights, SrcAccessor sa,
170 DestIterator upperleftd, DestAccessor da,
173 int w = lowerrights.x - upperlefts.x;
174 int h = lowerrights.y - upperlefts.y;
177 SrcIterator ys(upperlefts);
180 DestIterator yd = upperleftd;
182 for(y = 0; y != h; ++y, ++ys.y, ++yd.y)
185 DestIterator xd = yd;
187 for(x = 0; x != w; ++x, ++xs.x, ++xd.x)
190 typename SrcAccessor::value_type v = sa(xs);
197 NeighborhoodCirculator<SrcIterator, FourNeighborCode> c(xs), cend(c);
202 o = c.directionBit();
209 RestrictedNeighborhoodCirculator<SrcIterator, FourNeighborCode> c(xs, atBorder), cend(c);
214 o = c.directionBit();
224template <
class SrcIterator,
class SrcAccessor,
225 class DestIterator,
class DestAccessor>
226void prepareWatersheds(SrcIterator upperlefts, SrcIterator lowerrights, SrcAccessor sa,
227 DestIterator upperleftd, DestAccessor da,
230 int w = lowerrights.x - upperlefts.x;
231 int h = lowerrights.y - upperlefts.y;
234 SrcIterator ys(upperlefts);
237 DestIterator yd = upperleftd;
239 for(y = 0; y != h; ++y, ++ys.y, ++yd.y)
242 DestIterator xd = yd;
244 for(x = 0; x != w; ++x, ++xs.x, ++xd.x)
247 typename SrcAccessor::value_type v = sa(xs);
257 NeighborhoodCirculator<SrcIterator, EightNeighborCode>
259 for(
int i = 0; i < 4; ++i, c += 2)
264 o = c.directionBit();
268 for(
int i = 0; i < 4; ++i, c += 2)
273 o = c.directionBit();
279 RestrictedNeighborhoodCirculator<SrcIterator, EightNeighborCode>
280 c(xs, atBorder), cend(c);
288 o = c.directionBit();
299 o = c.directionBit();
332 enum DetectMinima { LevelSets, Minima, ExtendedMinima, Unspecified };
342 : thresh(NumericTraits<double>::max()),
362 mini = ExtendedMinima;
403 bool thresholdIsValid()
const
405 return thresh < double(NumericTraits<T>::max());
492template <
class SrcIterator,
class SrcAccessor,
493 class DestIterator,
class DestAccessor,
496generateWatershedSeeds(SrcIterator upperlefts, SrcIterator lowerrights, SrcAccessor sa,
497 DestIterator upperleftd, DestAccessor da,
501 using namespace functor;
502 typedef typename SrcAccessor::value_type SrcType;
504 vigra_precondition(options.mini != SeedOptions::LevelSets ||
505 options.thresholdIsValid<SrcType>(),
506 "generateWatershedSeeds(): SeedOptions.levelSets() must be specified with threshold.");
508 Diff2D shape = lowerrights - upperlefts;
511 if(options.mini == SeedOptions::LevelSets)
515 ifThenElse(Arg1() <= Param(options.thresh), Param(1), Param(0)));
524 if(options.thresholdIsValid<SrcType>())
527 localMinima(srcIterRange(upperlefts, lowerrights, sa), destImage(seeds),
532 Neighborhood::DirectionCount == 8, 0);
535template <
class SrcIterator,
class SrcAccessor,
536 class DestIterator,
class DestAccessor>
538generateWatershedSeeds(SrcIterator upperlefts, SrcIterator lowerrights, SrcAccessor sa,
539 DestIterator upperleftd, DestAccessor da,
540 SeedOptions
const & options = SeedOptions())
542 return generateWatershedSeeds(upperlefts, lowerrights, sa, upperleftd, da,
546template <
class SrcIterator,
class SrcAccessor,
547 class DestIterator,
class DestAccessor,
550generateWatershedSeeds(triple<SrcIterator, SrcIterator, SrcAccessor> src,
551 pair<DestIterator, DestAccessor> dest,
552 Neighborhood neighborhood,
553 SeedOptions
const & options = SeedOptions())
555 return generateWatershedSeeds(src.first, src.second, src.third,
556 dest.first, dest.second,
557 neighborhood, options);
560template <
class SrcIterator,
class SrcAccessor,
561 class DestIterator,
class DestAccessor>
563generateWatershedSeeds(triple<SrcIterator, SrcIterator, SrcAccessor> src,
564 pair<DestIterator, DestAccessor> dest,
565 SeedOptions
const & options = SeedOptions())
567 return generateWatershedSeeds(src.first, src.second, src.third,
568 dest.first, dest.second,
699template <
class SrcIterator,
class SrcAccessor,
700 class DestIterator,
class DestAccessor,
704 DestIterator upperleftd, DestAccessor da,
705 Neighborhood neighborhood)
707 SImage orientationImage(lowerrights - upperlefts);
709 prepareWatersheds(upperlefts, lowerrights, sa,
712 upperleftd, da, neighborhood);
715template <
class SrcIterator,
class SrcAccessor,
716 class DestIterator,
class DestAccessor>
719 DestIterator upperleftd, DestAccessor da)
724template <
class SrcIterator,
class SrcAccessor,
725 class DestIterator,
class DestAccessor,
729 pair<DestIterator, DestAccessor> dest, Neighborhood neighborhood)
732 dest.first, dest.second, neighborhood);
735template <
class SrcIterator,
class SrcAccessor,
736 class DestIterator,
class DestAccessor>
739 pair<DestIterator, DestAccessor> dest)
742 dest.first, dest.second);
745template <
class T1,
class S1,
750 MultiArrayView<2, T2, S2> dest, Neighborhood neighborhood)
753 destImage(dest), neighborhood);
756template <
class T1,
class S1,
760 MultiArrayView<2, T2, S2> dest)
762 vigra_precondition(src.shape() == dest.shape(),
763 "watershedsUnionFind(): shape mismatch between input and output.");
777 enum Method { RegionGrowing, UnionFind };
779 double max_cost, bias;
782 unsigned int biased_label, bucket_count;
796 terminate(CompleteGrow),
797 method(RegionGrowing),
812 terminate =
SRGType(CompleteGrow | (terminate & StopAtThreshold));
824 terminate =
SRGType(KeepContours | (terminate & StopAtThreshold));
846 terminate =
SRGType(terminate | StopAtThreshold);
847 max_cost = threshold;
864 this->bucket_count = bucket_count;
865 method = RegionGrowing;
896 biased_label = label;
911 this->method = method;
924 method = RegionGrowing;
944template <
class CostType,
class LabelType>
945class WatershedStatistics
949 typedef SeedRgDirectValueFunctor<CostType> value_type;
950 typedef value_type & reference;
951 typedef value_type
const & const_reference;
953 typedef CostType first_argument_type;
954 typedef LabelType second_argument_type;
955 typedef LabelType argument_type;
957 WatershedStatistics()
960 void resize(
unsigned int)
968 template <
class T1,
class T2>
969 void operator()(first_argument_type
const &, second_argument_type
const &)
974 LabelType maxRegionLabel()
const
975 {
return size() - 1; }
979 LabelType size()
const
980 {
return NumericTraits<LabelType>::max(); }
984 const_reference operator[](argument_type)
const
989 reference operator[](argument_type)
995template <
class Value>
996class SeedRgBiasedValueFunctor
1003 typedef Value argument_type;
1008 typedef Value result_type;
1012 typedef Value cost_type;
1014 SeedRgBiasedValueFunctor(
double b = 1.0)
1020 void operator()(argument_type
const &)
const {}
1024 cost_type cost(argument_type
const & v)
const
1026 return cost_type(bias*v);
1030template <
class CostType,
class LabelType>
1031class BiasedWatershedStatistics
1035 typedef SeedRgBiasedValueFunctor<CostType> value_type;
1036 typedef value_type & reference;
1037 typedef value_type
const & const_reference;
1039 typedef CostType first_argument_type;
1040 typedef LabelType second_argument_type;
1041 typedef LabelType argument_type;
1043 BiasedWatershedStatistics(LabelType biasedLabel,
double bias)
1044 : biased_label(biasedLabel),
1048 void resize(
unsigned int)
1056 template <
class T1,
class T2>
1057 void operator()(first_argument_type
const &, second_argument_type
const &)
1062 LabelType maxRegionLabel()
const
1063 {
return size() - 1; }
1067 LabelType size()
const
1068 {
return NumericTraits<LabelType>::max(); }
1072 const_reference operator[](argument_type label)
const
1074 return (label == biased_label)
1081 reference operator[](argument_type label)
1083 return (label == biased_label)
1088 LabelType biased_label;
1089 value_type stats, biased_stats;
1353template <
class SrcIterator,
class SrcAccessor,
1354 class DestIterator,
class DestAccessor,
1358 DestIterator upperleftd, DestAccessor da,
1359 Neighborhood neighborhood,
1362 typedef typename SrcAccessor::value_type ValueType;
1363 typedef typename DestAccessor::value_type LabelType;
1365 unsigned int max_region_label = 0;
1367 if(options.seed_options.mini != SeedOptions::Unspecified)
1371 generateWatershedSeeds(srcIterRange(upperlefts, lowerrights, sa),
1372 destIter(upperleftd, da),
1373 neighborhood, options.seed_options);
1376 if(options.biased_label != 0)
1379 detail::BiasedWatershedStatistics<ValueType, LabelType>
1380 regionstats(options.biased_label, options.bias);
1383 if(options.bucket_count == 0)
1387 srcIter(upperleftd, da),
1388 destIter(upperleftd, da),
1389 regionstats, options.terminate, neighborhood, options.max_cost);
1394 fastSeededRegionGrowing(srcIterRange(upperlefts, lowerrights, sa),
1395 destIter(upperleftd, da),
1396 regionstats, options.terminate,
1397 neighborhood, options.max_cost, options.bucket_count);
1403 detail::WatershedStatistics<ValueType, LabelType> regionstats;
1406 if(options.bucket_count == 0)
1410 srcIter(upperleftd, da),
1411 destIter(upperleftd, da),
1412 regionstats, options.terminate, neighborhood, options.max_cost);
1417 fastSeededRegionGrowing(srcIterRange(upperlefts, lowerrights, sa),
1418 destIter(upperleftd, da),
1419 regionstats, options.terminate,
1420 neighborhood, options.max_cost, options.bucket_count);
1424 return max_region_label;
1427template <
class SrcIterator,
class SrcAccessor,
1428 class DestIterator,
class DestAccessor>
1431 DestIterator upperleftd, DestAccessor da,
1432 WatershedOptions
const & options = WatershedOptions())
1438template <
class SrcIterator,
class SrcAccessor,
1439 class DestIterator,
class DestAccessor,
1443 pair<DestIterator, DestAccessor> dest,
1444 Neighborhood neighborhood,
1445 WatershedOptions
const & options = WatershedOptions())
1448 dest.first, dest.second,
1449 neighborhood, options);
1452template <
class SrcIterator,
class SrcAccessor,
1453 class DestIterator,
class DestAccessor>
1456 pair<DestIterator, DestAccessor> dest,
1457 WatershedOptions
const & options = WatershedOptions())
1460 dest.first, dest.second,
1464template <
class T1,
class S1,
1469 MultiArrayView<2, T2, S2> dest,
1470 Neighborhood neighborhood,
1471 WatershedOptions
const & options = WatershedOptions())
1473 vigra_precondition(src.shape() == dest.shape(),
1474 "watershedsRegionGrowing(): shape mismatch between input and output.");
1477 neighborhood, options);
1480template <
class T1,
class S1,
1484 MultiArrayView<2, T2, S2> dest,
1485 WatershedOptions
const & options = WatershedOptions())
1487 vigra_precondition(src.shape() == dest.shape(),
1488 "watershedsRegionGrowing(): shape mismatch between input and output.");
Fundamental class template for images.
Definition: basicimage.hxx:476
Accessor accessor()
Definition: basicimage.hxx:1066
traverser lowerRight()
Definition: basicimage.hxx:936
traverser upperLeft()
Definition: basicimage.hxx:925
Two dimensional difference vector.
Definition: diff2d.hxx:186
@ NorthEast
 
Definition: pixelneighborhood.hxx:437
Options object for localMinima() and localMaxima().
Definition: localminmax.hxx:494
LocalMinmaxOptions & allowAtBorder(bool f=true)
Detect extrema at the image border.
Definition: localminmax.hxx:565
LocalMinmaxOptions & threshold(double t)
Threshold the extrema.
Definition: localminmax.hxx:554
LocalMinmaxOptions & markWith(double m)
Mark extrema in the destination image with the given value.
Definition: localminmax.hxx:541
LocalMinmaxOptions & neighborhood(unsigned int n)
Use the given neighborhood.
Definition: localminmax.hxx:525
LocalMinmaxOptions & allowPlateaus(bool f=true)
Allow extremal plateaus.
Definition: localminmax.hxx:578
Options object for generateWatershedSeeds().
Definition: watersheds.hxx:330
SeedOptions & levelSets()
Definition: watersheds.hxx:371
SeedOptions & extendedMinima()
Definition: watersheds.hxx:360
SeedOptions()
Construct default options object.
Definition: watersheds.hxx:341
SeedOptions & minima()
Definition: watersheds.hxx:350
SeedOptions & levelSets(double threshold)
Definition: watersheds.hxx:382
SeedOptions & threshold(double threshold)
Definition: watersheds.hxx:395
Options object for watershed algorithms.
Definition: watersheds.hxx:775
WatershedOptions & unionFind()
Use union-find watershed.
Definition: watersheds.hxx:935
WatershedOptions & useMethod(Method method)
Specify the algorithm to be used.
Definition: watersheds.hxx:909
WatershedOptions & srgType(SRGType type)
Set SRGType explicitly.
Definition: watersheds.hxx:832
WatershedOptions & biasLabel(unsigned int label, double factor)
Bias the cost of the specified region by the given factor.
Definition: watersheds.hxx:894
WatershedOptions & completeGrow()
Perform complete grow.
Definition: watersheds.hxx:810
WatershedOptions & regionGrowing()
Use region-growing watershed.
Definition: watersheds.hxx:922
WatershedOptions & turboAlgorithm(unsigned int bucket_count=256)
Use a simpler, but faster region growing algorithm.
Definition: watersheds.hxx:862
WatershedOptions()
Create options object with default settings.
Definition: watersheds.hxx:793
WatershedOptions & stopAtThreshold(double threshold)
Stop region growing when the boundaryness exceeds the threshold.
Definition: watersheds.hxx:844
WatershedOptions & seedOptions(SeedOptions const &s)
Specify seed options.
Definition: watersheds.hxx:878
WatershedOptions & keepContours()
Keep one-pixel wide contour between regions.
Definition: watersheds.hxx:822
SRGType
Definition: seededregiongrowing.hxx:176
void seededRegionGrowing(...)
Region Segmentation by means of Seeded Region Growing.
EightNeighborhood::NeighborCode EightNeighborCode
Definition: pixelneighborhood.hxx:687
unsigned int labelImageWithBackground(...)
Find the connected components of a segmented image, excluding the background from labeling.
unsigned int watershedsUnionFind(...)
Region segmentation by means of the union-find watershed algorithm.
FourNeighborhood::NeighborCode FourNeighborCode
Definition: pixelneighborhood.hxx:379
AtImageBorder
Encode whether a point is near the image border.
Definition: pixelneighborhood.hxx:69
@ NotAtBorder
 
Definition: pixelneighborhood.hxx:70
doxygen_overloaded_function(template<... > void separableConvolveBlockwise) template< unsigned int N
Separated convolution on ChunkedArrays.
void localMinima(...)
Find local minima in an image or multi-dimensional array.
unsigned int watershedsRegionGrowing(...)
Region segmentation by means of a flooding-based watershed algorithm.
AtImageBorder isAtImageBorder(int x, int y, int width, int height)
Find out whether a point is at the image border.
Definition: pixelneighborhood.hxx:111