36 #ifndef VIGRA_WATERSHEDS_HXX
37 #define VIGRA_WATERSHEDS_HXX
40 #include "mathutil.hxx"
41 #include "stdimage.hxx"
42 #include "pixelneighborhood.hxx"
43 #include "union_find.hxx"
47 template <
class SrcIterator,
class SrcAccessor,
48 class DestIterator,
class DestAccessor,
50 unsigned int watershedLabeling(SrcIterator upperlefts,
51 SrcIterator lowerrights, SrcAccessor sa,
52 DestIterator upperleftd, DestAccessor da,
55 typedef typename DestAccessor::value_type LabelType;
57 int w = lowerrights.x - upperlefts.x;
58 int h = lowerrights.y - upperlefts.y;
61 SrcIterator ys(upperlefts);
63 DestIterator yd(upperleftd);
67 detail::UnionFindArray<LabelType> labels;
70 NeighborOffsetCirculator<Neighborhood> ncstart(Neighborhood::CausalFirst);
71 NeighborOffsetCirculator<Neighborhood> ncstartBorder(Neighborhood::North);
72 NeighborOffsetCirculator<Neighborhood> ncend(Neighborhood::CausalLast);
74 NeighborOffsetCirculator<Neighborhood> ncendBorder(Neighborhood::North);
90 da.set(labels.finalizeLabel(labels.nextFreeLabel()), xd);
94 for(x = 1; x != w; ++x, ++xs.x, ++xd.x)
96 if((sa(xs) & Neighborhood::directionBit(Neighborhood::West)) ||
97 (sa(xs, Neighborhood::west()) & Neighborhood::directionBit(Neighborhood::East)))
99 da.set(da(xd, Neighborhood::west()), xd);
103 da.set(labels.finalizeLabel(labels.nextFreeLabel()), xd);
109 for(y = 1; y != h; ++y, ++ys.y, ++yd.y)
114 for(x = 0; x != w; ++x, ++xs.x, ++xd.x)
116 NeighborOffsetCirculator<Neighborhood> nc(x == w-1
119 NeighborOffsetCirculator<Neighborhood> nce(x == 0
122 LabelType currentLabel = labels.nextFreeLabel();
123 for(; nc != nce; ++nc)
125 if((sa(xs) & nc.directionBit()) || (sa(xs, *nc) & nc.oppositeDirectionBit()))
127 currentLabel = labels.makeUnion(da(xd,*nc), currentLabel);
130 da.set(labels.finalizeLabel(currentLabel), xd);
134 unsigned int count = labels.makeContiguous();
139 for(y=0; y != h; ++y, ++yd.y)
142 for(x = 0; x != w; ++x, ++xd.x)
144 da.set(labels[da(xd)], xd);
150 template <
class SrcIterator,
class SrcAccessor,
151 class DestIterator,
class DestAccessor,
153 unsigned int watershedLabeling(triple<SrcIterator, SrcIterator, SrcAccessor> src,
154 pair<DestIterator, DestAccessor> dest,
155 Neighborhood neighborhood)
157 return watershedLabeling(src.first, src.second, src.third,
158 dest.first, dest.second, neighborhood);
162 template <
class SrcIterator,
class SrcAccessor,
163 class DestIterator,
class DestAccessor>
164 void prepareWatersheds(SrcIterator upperlefts, SrcIterator lowerrights, SrcAccessor sa,
165 DestIterator upperleftd, DestAccessor da,
168 int w = lowerrights.x - upperlefts.x;
169 int h = lowerrights.y - upperlefts.y;
172 SrcIterator ys(upperlefts);
175 DestIterator yd = upperleftd;
177 for(y = 0; y != h; ++y, ++ys.y, ++yd.y)
180 DestIterator xd = yd;
182 for(x = 0; x != w; ++x, ++xs.x, ++xd.x)
185 typename SrcAccessor::value_type v = sa(xs);
192 NeighborhoodCirculator<SrcIterator, FourNeighborCode> c(xs), cend(c);
197 o = c.directionBit();
204 RestrictedNeighborhoodCirculator<SrcIterator, FourNeighborCode> c(xs, atBorder), cend(c);
209 o = c.directionBit();
219 template <
class SrcIterator,
class SrcAccessor,
220 class DestIterator,
class DestAccessor>
221 void prepareWatersheds(SrcIterator upperlefts, SrcIterator lowerrights, SrcAccessor sa,
222 DestIterator upperleftd, DestAccessor da,
225 int w = lowerrights.x - upperlefts.x;
226 int h = lowerrights.y - upperlefts.y;
229 SrcIterator ys(upperlefts);
232 DestIterator yd = upperleftd;
234 for(y = 0; y != h; ++y, ++ys.y, ++yd.y)
237 DestIterator xd = yd;
239 for(x = 0; x != w; ++x, ++xs.x, ++xd.x)
242 typename SrcAccessor::value_type v = sa(xs);
252 NeighborhoodCirculator<SrcIterator, EightNeighborCode>
254 for(
int i = 0; i < 4; ++i, c += 2)
259 o = c.directionBit();
263 for(
int i = 0; i < 4; ++i, c += 2)
268 o = c.directionBit();
274 RestrictedNeighborhoodCirculator<SrcIterator, EightNeighborCode>
275 c(xs, atBorder), cend(c);
283 o = c.directionBit();
294 o = c.directionBit();
405 template <
class SrcIterator,
class SrcAccessor,
406 class DestIterator,
class DestAccessor,
409 watersheds(SrcIterator upperlefts, SrcIterator lowerrights, SrcAccessor sa,
410 DestIterator upperleftd, DestAccessor da, Neighborhood neighborhood)
412 SImage orientationImage(lowerrights - upperlefts);
415 prepareWatersheds(upperlefts, lowerrights, sa,
416 orientationImage.upperLeft(), orientationImage.accessor(), neighborhood);
417 return watershedLabeling(orientationImage.upperLeft(), orientationImage.lowerRight(), orientationImage.accessor(),
418 upperleftd, da, neighborhood);
421 template <
class SrcIterator,
class SrcAccessor,
422 class DestIterator,
class DestAccessor>
424 watersheds(SrcIterator upperlefts, SrcIterator lowerrights, SrcAccessor sa,
425 DestIterator upperleftd, DestAccessor da)
430 template <
class SrcIterator,
class SrcAccessor,
431 class DestIterator,
class DestAccessor,
434 watersheds(triple<SrcIterator, SrcIterator, SrcAccessor> src,
435 pair<DestIterator, DestAccessor> dest, Neighborhood neighborhood)
437 return watersheds(src.first, src.second, src.third, dest.first, dest.second, neighborhood);
440 template <
class SrcIterator,
class SrcAccessor,
441 class DestIterator,
class DestAccessor>
443 watersheds(triple<SrcIterator, SrcIterator, SrcAccessor> src,
444 pair<DestIterator, DestAccessor> dest)
446 return watersheds(src.first, src.second, src.third, dest.first, dest.second);
453 #endif // VIGRA_WATERSHEDS_HXX