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
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 localMinima(srcIterRange(upperlefts, lowerrights, sa), destImage(seeds),
505 LocalMinmaxOptions().neighborhood(Neighborhood::DirectionCount)
507 .threshold(options.thresh)
509 .allowPlateaus(options.mini == SeedOptions::ExtendedMinima));
513 Neighborhood::DirectionCount == 8, 0);
516 template <
class SrcIterator,
class SrcAccessor,
517 class DestIterator,
class DestAccessor>
520 DestIterator upperleftd, DestAccessor da,
521 SeedOptions
const & options = SeedOptions())
527 template <
class SrcIterator,
class SrcAccessor,
528 class DestIterator,
class DestAccessor,
532 pair<DestIterator, DestAccessor> dest,
533 Neighborhood neighborhood,
534 SeedOptions
const & options = SeedOptions())
537 dest.first, dest.second,
538 neighborhood, options);
541 template <
class SrcIterator,
class SrcAccessor,
542 class DestIterator,
class DestAccessor>
545 pair<DestIterator, DestAccessor> dest,
546 SeedOptions
const & options = SeedOptions())
549 dest.first, dest.second,
647 template <
class SrcIterator,
class SrcAccessor,
648 class DestIterator,
class DestAccessor,
652 DestIterator upperleftd, DestAccessor da,
653 Neighborhood neighborhood)
655 SImage orientationImage(lowerrights - upperlefts);
658 prepareWatersheds(upperlefts, lowerrights, sa,
659 orientationImage.upperLeft(), orientationImage.accessor(), neighborhood);
660 return watershedLabeling(orientationImage.upperLeft(), orientationImage.lowerRight(), orientationImage.accessor(),
661 upperleftd, da, neighborhood);
664 template <
class SrcIterator,
class SrcAccessor,
665 class DestIterator,
class DestAccessor>
668 DestIterator upperleftd, DestAccessor da)
673 template <
class SrcIterator,
class SrcAccessor,
674 class DestIterator,
class DestAccessor,
678 pair<DestIterator, DestAccessor> dest, Neighborhood neighborhood)
681 dest.first, dest.second, neighborhood);
684 template <
class SrcIterator,
class SrcAccessor,
685 class DestIterator,
class DestAccessor>
688 pair<DestIterator, DestAccessor> dest)
691 dest.first, dest.second);
703 double max_cost, bias;
705 unsigned int biased_label, bucket_count;
717 terminate(CompleteGrow),
732 terminate =
SRGType(CompleteGrow | (terminate & StopAtThreshold));
744 terminate =
SRGType(KeepContours | (terminate & StopAtThreshold));
766 terminate =
SRGType(terminate | StopAtThreshold);
767 max_cost = threshold;
784 this->bucket_count = bucket_count;
814 biased_label = label;
822 template <
class CostType,
class LabelType>
823 class WatershedStatistics
827 typedef SeedRgDirectValueFunctor<CostType> value_type;
828 typedef value_type & reference;
829 typedef value_type
const & const_reference;
831 typedef CostType first_argument_type;
832 typedef LabelType second_argument_type;
833 typedef LabelType argument_type;
835 WatershedStatistics()
838 void resize(
unsigned int)
846 template <
class T1,
class T2>
847 void operator()(first_argument_type
const &, second_argument_type
const &)
852 LabelType maxRegionLabel()
const
853 {
return size() - 1; }
857 LabelType size()
const
862 const_reference operator[](argument_type label)
const
867 reference operator[](argument_type label)
873 template <
class Value>
874 class SeedRgBiasedValueFunctor
881 typedef Value argument_type;
886 typedef Value result_type;
890 typedef Value cost_type;
892 SeedRgBiasedValueFunctor(
double b = 1.0)
898 void operator()(argument_type
const &)
const {}
902 cost_type cost(argument_type
const & v)
const
904 return cost_type(bias*v);
908 template <
class CostType,
class LabelType>
909 class BiasedWatershedStatistics
913 typedef SeedRgBiasedValueFunctor<CostType> value_type;
914 typedef value_type & reference;
915 typedef value_type
const & const_reference;
917 typedef CostType first_argument_type;
918 typedef LabelType second_argument_type;
919 typedef LabelType argument_type;
921 BiasedWatershedStatistics(LabelType biasedLabel,
double bias)
922 : biased_label(biasedLabel),
926 void resize(
unsigned int)
934 template <
class T1,
class T2>
935 void operator()(first_argument_type
const &, second_argument_type
const &)
940 LabelType maxRegionLabel()
const
941 {
return size() - 1; }
945 LabelType size()
const
950 const_reference operator[](argument_type label)
const
952 return (label == biased_label)
959 reference operator[](argument_type label)
961 return (label == biased_label)
966 LabelType biased_label;
967 value_type stats, biased_stats;
1147 template <
class SrcIterator,
class SrcAccessor,
1148 class DestIterator,
class DestAccessor,
1152 DestIterator upperleftd, DestAccessor da,
1153 Neighborhood neighborhood,
1154 WatershedOptions
const & options = WatershedOptions())
1156 typedef typename SrcAccessor::value_type ValueType;
1157 typedef typename DestAccessor::value_type LabelType;
1159 unsigned int max_region_label = 0;
1161 if(options.seed_options.mini != SeedOptions::Unspecified)
1166 destIter(upperleftd, da),
1167 neighborhood, options.seed_options);
1170 if(options.biased_label != 0)
1173 detail::BiasedWatershedStatistics<ValueType, LabelType>
1174 regionstats(options.biased_label, options.bias);
1177 if(options.bucket_count == 0)
1181 srcIter(upperleftd, da),
1182 destIter(upperleftd, da),
1183 regionstats, options.terminate, neighborhood, options.max_cost);
1188 fastSeededRegionGrowing(srcIterRange(upperlefts, lowerrights, sa),
1189 destIter(upperleftd, da),
1190 regionstats, options.terminate,
1191 neighborhood, options.max_cost, options.bucket_count);
1197 detail::WatershedStatistics<ValueType, LabelType> regionstats;
1200 if(options.bucket_count == 0)
1204 srcIter(upperleftd, da),
1205 destIter(upperleftd, da),
1206 regionstats, options.terminate, neighborhood, options.max_cost);
1211 fastSeededRegionGrowing(srcIterRange(upperlefts, lowerrights, sa),
1212 destIter(upperleftd, da),
1213 regionstats, options.terminate,
1214 neighborhood, options.max_cost, options.bucket_count);
1218 return max_region_label;
1221 template <
class SrcIterator,
class SrcAccessor,
1222 class DestIterator,
class DestAccessor>
1225 DestIterator upperleftd, DestAccessor da,
1226 WatershedOptions
const & options = WatershedOptions())
1232 template <
class SrcIterator,
class SrcAccessor,
1233 class DestIterator,
class DestAccessor,
1237 pair<DestIterator, DestAccessor> dest,
1238 Neighborhood neighborhood,
1239 WatershedOptions
const & options = WatershedOptions())
1242 dest.first, dest.second,
1243 neighborhood, options);
1246 template <
class SrcIterator,
class SrcAccessor,
1247 class DestIterator,
class DestAccessor>
1250 pair<DestIterator, DestAccessor> dest,
1251 WatershedOptions
const & options = WatershedOptions())
1254 dest.first, dest.second,
1263 #endif // VIGRA_WATERSHEDS_HXX