00001
00002
00003
00004
00005
00006
00007
00008
00009
00010
00011
00012
00013
00014
00015
00016
00017
00018
00019
00020
00021
00022
00023
00024
00025
00026 #ifndef MLN_MORPHO_WATERSHED_FLOODING_HH
00027 # define MLN_MORPHO_WATERSHED_FLOODING_HH
00028
00040
00041 # include <mln/trait/ch_value.hh>
00042
00043 # include <mln/morpho/includes.hh>
00044 # include <mln/literal/zero.hh>
00045 # include <mln/labeling/regional_minima.hh>
00046
00047 # include <mln/core/site_set/p_queue_fast.hh>
00048 # include <mln/core/site_set/p_priority.hh>
00049
00050 # include <mln/extension/adjust_fill.hh>
00051
00052
00053 namespace mln
00054 {
00055
00056 namespace morpho
00057 {
00058
00059 namespace watershed
00060 {
00061
00073
00074 template <typename L, typename I, typename N>
00075 mln_ch_value(I, L)
00076 flooding(const Image<I>& input, const Neighborhood<N>& nbh,
00077 L& n_basins);
00078
00095 template <typename L, typename I, typename N>
00096 mln_ch_value(I, L)
00097 flooding(const Image<I>& input, const Neighborhood<N>& nbh);
00098
00099
00100
00101 # ifndef MLN_INCLUDE_ONLY
00102
00103
00104
00105
00106 namespace impl
00107 {
00108
00109 namespace generic
00110 {
00111
00112 template <typename L, typename I, typename N>
00113 mln_ch_value(I, L)
00114 flooding(const Image<I>& input_, const Neighborhood<N>& nbh_,
00115 L& n_basins)
00116 {
00117 trace::entering("morpho::watershed::impl::generic::flooding");
00118
00119
00120 const I input = exact(input_);
00121 const N nbh = exact(nbh_);
00122
00123 typedef L marker;
00124 const marker unmarked = literal::zero;
00125
00126 typedef mln_value(I) V;
00127 const V max = mln_max(V);
00128
00129
00130 mln_ch_value(I, marker) output =
00131 labeling::regional_minima (input, nbh, n_basins);
00132
00133 typedef mln_psite(I) psite;
00134
00135
00136 typedef p_queue_fast<psite> Q;
00137 p_priority<V, Q> queue;
00138
00139
00140 mln_ch_value(I, bool) in_queue;
00141 initialize(in_queue, input);
00142 data::fill(in_queue, false);
00143
00144
00145
00146
00147 mln_piter(I) p(output.domain());
00148 mln_niter(N) n(nbh, p);
00149 for_all(p)
00150 if (output(p) == unmarked)
00151 for_all(n)
00152 if (output.domain().has(n) && output(n) != unmarked)
00153 {
00154 queue.push(max - input(p), p);
00155 in_queue(p) = true;
00156 break;
00157 }
00158
00159
00160
00161
00162 while (! queue.is_empty())
00163 {
00164 psite p = queue.front();
00165 queue.pop();
00166
00167
00168 marker adjacent_marker = unmarked;
00169
00170 bool single_adjacent_marker_p = true;
00171 mln_niter(N) n(nbh, p);
00172 for_all(n)
00173 if (output.domain().has(n) && output(n) != unmarked)
00174 {
00175 if (adjacent_marker == unmarked)
00176 {
00177 adjacent_marker = output(n);
00178 single_adjacent_marker_p = true;
00179 }
00180 else
00181 if (adjacent_marker != output(n))
00182 {
00183 single_adjacent_marker_p = false;
00184 break;
00185 }
00186 }
00187
00188
00189
00190
00191 if (single_adjacent_marker_p)
00192 {
00193 output(p) = adjacent_marker;
00194 for_all(n)
00195 if (output.domain().has(n) && output(n) == unmarked
00196 && ! in_queue(n))
00197 {
00198 queue.push(max - input(n), n);
00199 in_queue(n) = true;
00200 }
00201 }
00202 }
00203
00204 trace::exiting("morpho::watershed::impl::generic::flooding");
00205 return output;
00206 }
00207
00208 }
00209
00210
00211
00212
00213
00214 template <typename I, typename N, typename L>
00215 mln_ch_value(I, L)
00216 flooding_fastest(const Image<I>& input_, const Neighborhood<N>& nbh_,
00217 L& n_basins)
00218 {
00219 trace::entering("morpho::watershed::impl::flooding_fastest");
00220
00221
00222 const I input = exact(input_);
00223 const N nbh = exact(nbh_);
00224
00225 typedef L marker;
00226 const marker unmarked = literal::zero;
00227
00228 typedef mln_value(I) V;
00229 const V max = mln_max(V);
00230
00231 extension::adjust_fill(input, nbh, max);
00232
00233
00234 typedef mln_ch_value(I, L) O;
00235 O output = labeling::regional_minima(input, nbh, n_basins);
00236 extension::fill(output, unmarked);
00237
00238
00239 typedef p_queue_fast<unsigned> Q;
00240 p_priority<V, Q> queue;
00241
00242
00243
00244
00245
00246
00247 mln_ch_value(I, bool) in_queue;
00248 initialize(in_queue, input);
00249 data::fill(in_queue, false);
00250 extension::fill(in_queue, true);
00251
00252
00253
00254
00255 mln_pixter(const O) p_out(output);
00256 mln_nixter(const O, N) n_out(p_out, nbh);
00257 for_all(p_out)
00258 if (p_out.val() == unmarked)
00259 for_all(n_out)
00260 if (n_out.val() != unmarked)
00261 {
00262 unsigned po = p_out.offset();
00263 queue.push(max - input.element(po), po);
00264 in_queue.element(po) = true;
00265 break;
00266 }
00267
00268
00269
00270
00271 util::array<int> dp = offsets_wrt(input, nbh);
00272 const unsigned n_nbhs = dp.nelements();
00273 while (! queue.is_empty())
00274 {
00275 unsigned p = queue.front();
00276 queue.pop();
00277
00278
00279 marker adjacent_marker = unmarked;
00280
00281 bool single_adjacent_marker_p = true;
00282 for (unsigned i = 0; i < n_nbhs; ++i)
00283 {
00284 unsigned n = p + dp[i];
00285
00286 if (output.element(n) != unmarked)
00287 {
00288 if (adjacent_marker == unmarked)
00289 {
00290 adjacent_marker = output.element(n);
00291 single_adjacent_marker_p = true;
00292 }
00293 else
00294 if (adjacent_marker != output.element(n))
00295 {
00296 single_adjacent_marker_p = false;
00297 break;
00298 }
00299 }
00300 }
00301
00302
00303
00304
00305 if (single_adjacent_marker_p)
00306 {
00307 output.element(p) = adjacent_marker;
00308 for (unsigned i = 0; i < n_nbhs; ++i)
00309 {
00310 unsigned n = p + dp[i];
00311 if (output.element(n) == unmarked
00312
00313 && ! in_queue.element(n))
00314 {
00315 queue.push(max - input.element(n), n);
00316 in_queue.element(n) = true;
00317 }
00318 }
00319 }
00320 }
00321
00322 trace::exiting("morpho::watershed::impl::flooding_fastest");
00323 return output;
00324 }
00325
00326
00327 }
00328
00329
00330
00331
00332
00333 namespace internal
00334 {
00335
00336 template <typename I, typename N, typename L>
00337 inline
00338 mln_ch_value(I, L)
00339 flooding_dispatch(metal::false_,
00340 const Image<I>& input, const Neighborhood<N>& nbh,
00341 L& n_basins)
00342 {
00343 return impl::generic::flooding(input, nbh, n_basins);
00344 }
00345
00346
00347 template <typename I, typename N, typename L>
00348 inline
00349 mln_ch_value(I, L)
00350 flooding_dispatch(metal::true_,
00351 const Image<I>& input, const Neighborhood<N>& nbh,
00352 L& n_basins)
00353 {
00354 return impl::flooding_fastest(input, nbh, n_basins);
00355 }
00356
00357 template <typename I, typename N, typename L>
00358 inline
00359 mln_ch_value(I, L)
00360 flooding_dispatch(const Image<I>& input, const Neighborhood<N>& nbh,
00361 L& n_basins)
00362 {
00363 enum {
00364 test = mlc_equal(mln_trait_image_speed(I),
00365 trait::image::speed::fastest)::value
00366 &&
00367 mln_is_simple_neighborhood(N)::value
00368 };
00369 return flooding_dispatch(metal::bool_<test>(),
00370 input, nbh, n_basins);
00371 }
00372
00373 }
00374
00375
00376
00377
00378 template <typename L, typename I, typename N>
00379 inline
00380 mln_ch_value(I, L)
00381 flooding(const Image<I>& input, const Neighborhood<N>& nbh, L& n_basins)
00382 {
00383 trace::entering("morpho::watershed::flooding");
00384
00385
00386
00387 mln_ch_value(I, L) output =
00388 internal::flooding_dispatch(input, nbh, n_basins);
00389
00390 trace::exiting("morpho::watershed::flooding");
00391 return output;
00392 }
00393
00394 template <typename L, typename I, typename N>
00395 mln_ch_value(I, L)
00396 flooding(const Image<I>& input, const Neighborhood<N>& nbh)
00397 {
00398 L nbasins;
00399 return flooding<L>(input, nbh, nbasins);
00400 }
00401
00402 # endif // ! MLN_INCLUDE_ONLY
00403
00404 }
00405
00406 }
00407
00408 }
00409
00410
00411 #endif // ! MLN_MORPHO_WATERSHED_FLOODING_HH