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"
51 template <
class SrcIterator,
class SrcAccessor,
52 class DestIterator,
class DestAccessor,
54 unsigned int watershedLabeling(SrcIterator upperlefts,
55 SrcIterator lowerrights, SrcAccessor sa,
56 DestIterator upperleftd, DestAccessor da,
59 typedef typename DestAccessor::value_type LabelType;
61 int w = lowerrights.x - upperlefts.x;
62 int h = lowerrights.y - upperlefts.y;
65 SrcIterator ys(upperlefts);
67 DestIterator yd(upperleftd);
71 detail::UnionFindArray<LabelType> labels;
74 NeighborOffsetCirculator<Neighborhood> ncstart(Neighborhood::CausalFirst);
75 NeighborOffsetCirculator<Neighborhood> ncstartBorder(Neighborhood::North);
76 NeighborOffsetCirculator<Neighborhood> ncend(Neighborhood::CausalLast);
78 NeighborOffsetCirculator<Neighborhood> ncendBorder(Neighborhood::North);
94 da.set(labels.finalizeLabel(labels.nextFreeLabel()), xd);
98 for(x = 1; x != w; ++x, ++xs.x, ++xd.x)
100 if((sa(xs) & Neighborhood::directionBit(Neighborhood::West)) ||
101 (sa(xs, Neighborhood::west()) & Neighborhood::directionBit(Neighborhood::East)))
103 da.set(da(xd, Neighborhood::west()), xd);
107 da.set(labels.finalizeLabel(labels.nextFreeLabel()), xd);
113 for(y = 1; y != h; ++y, ++ys.y, ++yd.y)
118 for(x = 0; x != w; ++x, ++xs.x, ++xd.x)
120 NeighborOffsetCirculator<Neighborhood> nc(x == w-1
123 NeighborOffsetCirculator<Neighborhood> nce(x == 0
126 LabelType currentLabel = labels.nextFreeLabel();
127 for(; nc != nce; ++nc)
129 if((sa(xs) & nc.directionBit()) || (sa(xs, *nc) & nc.oppositeDirectionBit()))
131 currentLabel = labels.makeUnion(da(xd,*nc), currentLabel);
134 da.set(labels.finalizeLabel(currentLabel), xd);
138 unsigned int count = labels.makeContiguous();
143 for(y=0; y != h; ++y, ++yd.y)
146 for(x = 0; x != w; ++x, ++xd.x)
148 da.set(labels[da(xd)], xd);
154 template <
class SrcIterator,
class SrcAccessor,
155 class DestIterator,
class DestAccessor,
157 unsigned int watershedLabeling(triple<SrcIterator, SrcIterator, SrcAccessor> src,
158 pair<DestIterator, DestAccessor> dest,
159 Neighborhood neighborhood)
161 return watershedLabeling(src.first, src.second, src.third,
162 dest.first, dest.second, neighborhood);
166 template <
class SrcIterator,
class SrcAccessor,
167 class DestIterator,
class DestAccessor>
168 void prepareWatersheds(SrcIterator upperlefts, SrcIterator lowerrights, SrcAccessor sa,
169 DestIterator upperleftd, DestAccessor da,
172 int w = lowerrights.x - upperlefts.x;
173 int h = lowerrights.y - upperlefts.y;
176 SrcIterator ys(upperlefts);
179 DestIterator yd = upperleftd;
181 for(y = 0; y != h; ++y, ++ys.y, ++yd.y)
184 DestIterator xd = yd;
186 for(x = 0; x != w; ++x, ++xs.x, ++xd.x)
189 typename SrcAccessor::value_type v = sa(xs);
196 NeighborhoodCirculator<SrcIterator, FourNeighborCode> c(xs), cend(c);
201 o = c.directionBit();
208 RestrictedNeighborhoodCirculator<SrcIterator, FourNeighborCode> c(xs, atBorder), cend(c);
213 o = c.directionBit();
223 template <
class SrcIterator,
class SrcAccessor,
224 class DestIterator,
class DestAccessor>
225 void prepareWatersheds(SrcIterator upperlefts, SrcIterator lowerrights, SrcAccessor sa,
226 DestIterator upperleftd, DestAccessor da,
229 int w = lowerrights.x - upperlefts.x;
230 int h = lowerrights.y - upperlefts.y;
233 SrcIterator ys(upperlefts);
236 DestIterator yd = upperleftd;
238 for(y = 0; y != h; ++y, ++ys.y, ++yd.y)
241 DestIterator xd = yd;
243 for(x = 0; x != w; ++x, ++xs.x, ++xd.x)
246 typename SrcAccessor::value_type v = sa(xs);
256 NeighborhoodCirculator<SrcIterator, EightNeighborCode>
258 for(
int i = 0; i < 4; ++i, c += 2)
263 o = c.directionBit();
267 for(
int i = 0; i < 4; ++i, c += 2)
272 o = c.directionBit();
278 RestrictedNeighborhoodCirculator<SrcIterator, EightNeighborCode>
279 c(xs, atBorder), cend(c);
287 o = c.directionBit();
298 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());
477 template <
class SrcIterator,
class SrcAccessor,
478 class DestIterator,
class DestAccessor,
482 DestIterator upperleftd, DestAccessor da,
483 Neighborhood neighborhood,
484 SeedOptions
const & options = SeedOptions())
486 using namespace functor;
487 typedef typename SrcAccessor::value_type SrcType;
489 vigra_precondition(options.mini != SeedOptions::LevelSets ||
490 options.thresholdIsValid<SrcType>(),
491 "generateWatershedSeeds(): SeedOptions.levelSets() must be specified with threshold.");
493 Diff2D shape = lowerrights - upperlefts;
496 if(options.mini == SeedOptions::LevelSets)
500 ifThenElse(Arg1() <= Param(options.thresh), Param(1), Param(0)));
504 LocalMinmaxOptions lm_options;
505 lm_options.neighborhood(Neighborhood::DirectionCount)
508 .allowPlateaus(options.mini == SeedOptions::ExtendedMinima);
509 if(options.thresholdIsValid<SrcType>())
510 lm_options.threshold(options.thresh);
512 localMinima(srcIterRange(upperlefts, lowerrights, sa), destImage(seeds),
517 Neighborhood::DirectionCount == 8, 0);
520 template <
class SrcIterator,
class SrcAccessor,
521 class DestIterator,
class DestAccessor>
524 DestIterator upperleftd, DestAccessor da,
525 SeedOptions
const & options = SeedOptions())
531 template <
class SrcIterator,
class SrcAccessor,
532 class DestIterator,
class DestAccessor,
536 pair<DestIterator, DestAccessor> dest,
537 Neighborhood neighborhood,
538 SeedOptions
const & options = SeedOptions())
541 dest.first, dest.second,
542 neighborhood, options);
545 template <
class SrcIterator,
class SrcAccessor,
546 class DestIterator,
class DestAccessor>
549 pair<DestIterator, DestAccessor> dest,
550 SeedOptions
const & options = SeedOptions())
553 dest.first, dest.second,
651 template <
class SrcIterator,
class SrcAccessor,
652 class DestIterator,
class DestAccessor,
656 DestIterator upperleftd, DestAccessor da,
657 Neighborhood neighborhood)
659 SImage orientationImage(lowerrights - upperlefts);
661 prepareWatersheds(upperlefts, lowerrights, sa,
662 orientationImage.upperLeft(), orientationImage.accessor(), neighborhood);
663 return watershedLabeling(orientationImage.upperLeft(), orientationImage.lowerRight(), orientationImage.accessor(),
664 upperleftd, da, neighborhood);
667 template <
class SrcIterator,
class SrcAccessor,
668 class DestIterator,
class DestAccessor>
671 DestIterator upperleftd, DestAccessor da)
676 template <
class SrcIterator,
class SrcAccessor,
677 class DestIterator,
class DestAccessor,
681 pair<DestIterator, DestAccessor> dest, Neighborhood neighborhood)
684 dest.first, dest.second, neighborhood);
687 template <
class SrcIterator,
class SrcAccessor,
688 class DestIterator,
class DestAccessor>
691 pair<DestIterator, DestAccessor> dest)
694 dest.first, dest.second);
706 double max_cost, bias;
708 unsigned int biased_label, bucket_count;
720 terminate(CompleteGrow),
735 terminate =
SRGType(CompleteGrow | (terminate & StopAtThreshold));
747 terminate =
SRGType(KeepContours | (terminate & StopAtThreshold));
769 terminate =
SRGType(terminate | StopAtThreshold);
770 max_cost = threshold;
787 this->bucket_count = bucket_count;
817 biased_label = label;
825 template <
class CostType,
class LabelType>
826 class WatershedStatistics
830 typedef SeedRgDirectValueFunctor<CostType> value_type;
831 typedef value_type & reference;
832 typedef value_type
const & const_reference;
834 typedef CostType first_argument_type;
835 typedef LabelType second_argument_type;
836 typedef LabelType argument_type;
838 WatershedStatistics()
841 void resize(
unsigned int)
849 template <
class T1,
class T2>
850 void operator()(first_argument_type
const &, second_argument_type
const &)
855 LabelType maxRegionLabel()
const
856 {
return size() - 1; }
860 LabelType size()
const
861 {
return NumericTraits<LabelType>::max(); }
865 const_reference operator[](argument_type label)
const
870 reference operator[](argument_type label)
876 template <
class Value>
877 class SeedRgBiasedValueFunctor
884 typedef Value argument_type;
889 typedef Value result_type;
893 typedef Value cost_type;
895 SeedRgBiasedValueFunctor(
double b = 1.0)
901 void operator()(argument_type
const &)
const {}
905 cost_type cost(argument_type
const & v)
const
907 return cost_type(bias*v);
911 template <
class CostType,
class LabelType>
912 class BiasedWatershedStatistics
916 typedef SeedRgBiasedValueFunctor<CostType> value_type;
917 typedef value_type & reference;
918 typedef value_type
const & const_reference;
920 typedef CostType first_argument_type;
921 typedef LabelType second_argument_type;
922 typedef LabelType argument_type;
924 BiasedWatershedStatistics(LabelType biasedLabel,
double bias)
925 : biased_label(biasedLabel),
929 void resize(
unsigned int)
937 template <
class T1,
class T2>
938 void operator()(first_argument_type
const &, second_argument_type
const &)
943 LabelType maxRegionLabel()
const
944 {
return size() - 1; }
948 LabelType size()
const
949 {
return NumericTraits<LabelType>::max(); }
953 const_reference operator[](argument_type label)
const
955 return (label == biased_label)
962 reference operator[](argument_type label)
964 return (label == biased_label)
969 LabelType biased_label;
970 value_type stats, biased_stats;
1150 template <
class SrcIterator,
class SrcAccessor,
1151 class DestIterator,
class DestAccessor,
1155 DestIterator upperleftd, DestAccessor da,
1156 Neighborhood neighborhood,
1157 WatershedOptions
const & options = WatershedOptions())
1159 typedef typename SrcAccessor::value_type ValueType;
1160 typedef typename DestAccessor::value_type LabelType;
1162 unsigned int max_region_label = 0;
1164 if(options.seed_options.mini != SeedOptions::Unspecified)
1169 destIter(upperleftd, da),
1170 neighborhood, options.seed_options);
1173 if(options.biased_label != 0)
1176 detail::BiasedWatershedStatistics<ValueType, LabelType>
1177 regionstats(options.biased_label, options.bias);
1180 if(options.bucket_count == 0)
1184 srcIter(upperleftd, da),
1185 destIter(upperleftd, da),
1186 regionstats, options.terminate, neighborhood, options.max_cost);
1191 fastSeededRegionGrowing(srcIterRange(upperlefts, lowerrights, sa),
1192 destIter(upperleftd, da),
1193 regionstats, options.terminate,
1194 neighborhood, options.max_cost, options.bucket_count);
1200 detail::WatershedStatistics<ValueType, LabelType> regionstats;
1203 if(options.bucket_count == 0)
1207 srcIter(upperleftd, da),
1208 destIter(upperleftd, da),
1209 regionstats, options.terminate, neighborhood, options.max_cost);
1214 fastSeededRegionGrowing(srcIterRange(upperlefts, lowerrights, sa),
1215 destIter(upperleftd, da),
1216 regionstats, options.terminate,
1217 neighborhood, options.max_cost, options.bucket_count);
1221 return max_region_label;
1224 template <
class SrcIterator,
class SrcAccessor,
1225 class DestIterator,
class DestAccessor>
1228 DestIterator upperleftd, DestAccessor da,
1229 WatershedOptions
const & options = WatershedOptions())
1235 template <
class SrcIterator,
class SrcAccessor,
1236 class DestIterator,
class DestAccessor,
1240 pair<DestIterator, DestAccessor> dest,
1241 Neighborhood neighborhood,
1242 WatershedOptions
const & options = WatershedOptions())
1245 dest.first, dest.second,
1246 neighborhood, options);
1249 template <
class SrcIterator,
class SrcAccessor,
1250 class DestIterator,
class DestAccessor>
1253 pair<DestIterator, DestAccessor> dest,
1254 WatershedOptions
const & options = WatershedOptions())
1257 dest.first, dest.second,
1266 #endif // VIGRA_WATERSHEDS_HXX
SeedOptions & threshold(double threshold)
Definition: watersheds.hxx:395
WatershedOptions & completeGrow()
Perform complete grow.
Definition: watersheds.hxx:733
Definition: pixelneighborhood.hxx:414
SeedOptions & minima()
Definition: watersheds.hxx:350
void seededRegionGrowing(...)
Region Segmentation by means of Seeded Region Growing.
WatershedOptions()
Create options object with default settings.
Definition: watersheds.hxx:717
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
SRGType
Definition: seededregiongrowing.hxx:176
WatershedOptions & seedOptions(SeedOptions const &s)
Specify seed options.
Definition: watersheds.hxx:800
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:785
WatershedOptions & keepContours()
Keep one-pixel wide contour between regions.
Definition: watersheds.hxx:745
BasicImage< Int16 > SImage
Definition: stdimage.hxx:89
Options object for watershedsRegionGrowing().
Definition: watersheds.hxx:703
SeedOptions()
Construct default options object.
Definition: watersheds.hxx:341
WatershedOptions & srgType(SRGType type)
Set SRGType explicitly.
Definition: watersheds.hxx:755
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:815
WatershedOptions & stopAtThreshold(double threshold)
Stop region growing when the boundaryness exceeds the threshold.
Definition: watersheds.hxx:767
SeedOptions & levelSets()
Definition: watersheds.hxx:371
unsigned int generateWatershedSeeds(...)
Generate seeds for watershed computation and seeded region growing.
FourNeighborhood::NeighborCode FourNeighborCode
Definition: pixelneighborhood.hxx:356
Options object for generateWatershedSeeds().
Definition: watersheds.hxx:329
Definition: pixelneighborhood.hxx:70
EightNeighborhood::NeighborCode EightNeighborCode
Definition: pixelneighborhood.hxx:644
SeedOptions & extendedMinima()
Definition: watersheds.hxx:360