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
00027 #ifndef MLN_CANVAS_MORPHO_ATTRIBUTE_FILTER_HH
00028 # define MLN_CANVAS_MORPHO_ATTRIBUTE_FILTER_HH
00029
00033
00034
00035 # include <mln/core/concept/image.hh>
00036 # include <mln/core/concept/neighborhood.hh>
00037 # include <mln/core/concept/accumulator.hh>
00038
00039 # include <mln/data/sort_offsets.hh>
00040 # include <mln/trait/accumulators.hh>
00041 # include <mln/util/pix.hh>
00042
00043 # include <mln/border/get.hh>
00044 # include <mln/data/fill.hh>
00045 # include <mln/extension/adjust_fill.hh>
00046 # include <mln/data/sort_psites.hh>
00047
00048 namespace mln
00049 {
00050
00051 namespace canvas
00052 {
00053
00054 namespace morpho
00055 {
00056
00057
00058
00059 template <typename I, typename N, typename A>
00060 mln_concrete(I)
00061 attribute_filter(const Image<I>& input, const Neighborhood<N>& nbh,
00062 const Accumulator<A>& a, const mln_result(A)& lambda,
00063 bool increasing);
00064
00065
00066
00067 # ifndef MLN_INCLUDE_ONLY
00068
00069 namespace impl
00070 {
00071
00072 template <typename A, typename I>
00073 void take_as_init_fastest(trait::accumulator::when_pix::use_none, A& accu,
00074 const I& input, const unsigned p)
00075 {
00076 (void)input;
00077 (void)p;
00078 accu.take_as_init();
00079 }
00080
00081 template <typename A, typename I, typename P>
00082 void take_as_init(trait::accumulator::when_pix::use_p, A& accu,
00083 const I& input, const P& p)
00084 {
00085 (void)input;
00086 accu.take_as_init(p);
00087 }
00088
00089 template <typename A, typename I, typename P>
00090 void take_as_init(trait::accumulator::when_pix::use_none, A& accu,
00091 const I& input, const P& p)
00092 {
00093 (void)input;
00094 (void)p;
00095 accu.take_as_init();
00096 }
00097
00098 template <typename A, typename I, typename P>
00099 void take_as_init(trait::accumulator::when_pix::use_pix, A& accu,
00100 const I& input, const P& p)
00101 {
00102 accu.take_as_init(make::pix(input, p));
00103 }
00104
00105 template <typename A, typename I, typename P>
00106 void take_as_init(trait::accumulator::when_pix::use_v, A& accu,
00107 const I& input, const P& p)
00108 {
00109 accu.take_as_init(input(p));
00110 }
00111
00112 template <typename A, typename I>
00113 void take_as_init_fastest(trait::accumulator::when_pix::use_v, A& accu,
00114 const I& input, const unsigned p)
00115 {
00116 accu.take_as_init(input.element(p));
00117 }
00118
00119
00120 template <typename A, typename I, typename P>
00121 void take_as_init(A& accu, const I& input, const P& p)
00122 {
00123 take_as_init(mln_trait_accumulator_when_pix(A)(), accu, input, p);
00124 }
00125
00126 template <typename A, typename I, typename P>
00127 void take_as_init_fastest(A& accu, const I& input, const P& p)
00128 {
00129 take_as_init_fastest(mln_trait_accumulator_when_pix(A)(), accu, input, p);
00130 }
00131
00132
00133
00134 namespace generic
00135 {
00136
00140
00141
00142 template <typename I>
00143 static inline
00144 mln_psite(I)
00145 find_root(I& parent, const mln_psite(I) & x)
00146 {
00147 if (parent(x) == x)
00148 return x;
00149 else
00150 return parent(x) = find_root(parent, parent(x));
00151 }
00152
00153 template <typename I, typename N, typename S, typename A>
00154 mln_concrete(I)
00155 attribute_filter(const Image<I>& input_,
00156 const Neighborhood<N>& nbh_,
00157 const Site_Set<S>& s_,
00158 const Accumulator<A>& a_,
00159 const mln_result(A)& lambda)
00160 {
00161 trace::entering("canvas::morpho::impl::generic::attribute_filter");
00162
00163
00164 const I& input = exact(input_);
00165 const N& nbh = exact(nbh_);
00166 const S& s = exact(s_);
00167 (void)a_;
00168
00169 mln_concrete(I) output;
00170 initialize(output, input);
00171
00172
00173 typedef mln_psite(I) P;
00174
00175
00176
00177 mln_ch_value(I, bool) deja_vu;
00178 mln_ch_value(I, bool) activity;
00179 mln_ch_value(I, P) parent;
00180 mln_ch_value(I, A) data;
00181
00182
00183 {
00184 initialize(deja_vu, input);
00185 data::fill(deja_vu, false);
00186 initialize(activity, input);
00187 data::fill(activity, true);
00188 initialize(parent, input);
00189 initialize(data, input);
00190
00191 }
00192
00193
00194 {
00195 mln_fwd_piter(S) p(s);
00196 mln_niter(N) n(nbh, p);
00197
00198 for_all(p)
00199 {
00200
00201 {
00202 parent(p) = p;
00203
00204
00205 take_as_init(data(p), input, p);
00206 }
00207
00208 for_all(n)
00209 if (input.domain().has(n) && deja_vu(n))
00210 {
00211
00212 P r = find_root(parent, n);
00213 if (r != p)
00214 {
00215 if (input(r) == input(p) || (activity(r) && (data(r) < lambda)))
00216
00217 {
00218
00219
00220
00221
00222
00223
00224
00225
00226
00227
00228
00229
00230
00231 data(p).take(data(r));
00232 parent(r) = p;
00233 if (activity(r) == false)
00234 activity(p) = false;
00235 }
00236 else
00237 {
00238 activity(p) = false;
00239 }
00240 }
00241 }
00242 deja_vu(p) = true;
00243 }
00244 }
00245
00246
00247 {
00248 mln_bkd_piter(S) p(s);
00249 for_all(p)
00250 if (parent(p) == p)
00251 output(p) = input(p);
00252 else
00253 output(p) = output(parent(p));
00254 }
00255
00256 trace::exiting("canvas::morpho::impl::generic::attribute_filter");
00257 return output;
00258 }
00259
00260 }
00261
00262
00266
00267 template <typename I>
00268 inline
00269 unsigned
00270 find_root_fastest(I& parent, unsigned x)
00271 {
00272 if (parent.element(x) == x)
00273 return x;
00274 else
00275 return parent.element(x) = find_root_fastest(parent, parent.element(x));
00276 }
00277
00278 template <typename I, typename N, typename A>
00279 mln_concrete(I)
00280 attribute_filter_fastest(const Image<I>& input_,
00281 const Neighborhood<N>& nbh_,
00282 const util::array<unsigned>& s,
00283 const Accumulator<A>& a_,
00284 const mln_result(A)& lambda)
00285 {
00286 trace::entering("canvas::morpho::impl::attribute_filter_fastest");
00287
00288
00289 const I& input = exact(input_);
00290 const N& nbh = exact(nbh_);
00291 (void)a_;
00292
00293
00294
00295 mln_precondition(border::get(input) >= nbh.delta());
00296
00297 mln_concrete(I) output;
00298 initialize(output, input);
00299
00300
00301 typedef mln_psite(I) P;
00302
00303
00304 mln_ch_value(I, bool) deja_vu;
00305 mln_ch_value(I, bool) activity;
00306 mln_ch_value(I, unsigned) parent;
00307 mln_ch_value(I, A) data;
00308
00309
00310 {
00311 initialize(deja_vu, input);
00312 data::fill(deja_vu, false);
00313 extension::fill(deja_vu, false);
00314
00315 initialize(activity, input);
00316 data::fill(activity, true);
00317 initialize(parent, input);
00318 data::fill(parent, 0);
00319 initialize(data, input);
00320 }
00321
00322 util::array<int> dp = offsets_wrt(input, nbh);
00323 const unsigned n_nbhs = dp.nelements();
00324 const unsigned n_points = s.nelements();
00325
00326
00327 {
00328 for (unsigned i = 0; i < n_points; ++i)
00329 {
00330 unsigned p = s[i];
00331
00332
00333 parent.element(p) = p;
00334
00335
00336 take_as_init_fastest(data.element(p), input, p);
00337
00338 for (unsigned j = 0; j < n_nbhs; ++j)
00339 {
00340 unsigned n = p + dp[j];
00341 if (! deja_vu.element(n))
00342 continue;
00343
00344 unsigned r = find_root_fastest(parent, n);
00345 if (r != p)
00346 {
00347 if (input.element(r) == input.element(p)
00348 || (activity.element(r)
00349 && (data.element(r) < lambda)))
00350 {
00351 data.element(p).take(data.element(r));
00352 parent.element(r) = p;
00353 if (activity.element(r) == false)
00354 activity.element(p) = false;
00355 }
00356 else
00357 activity.element(p) = false;
00358 }
00359 }
00360
00361 deja_vu.element(p) = true;
00362 }
00363 }
00364
00365
00366
00367 {
00368 for (int i = n_points - 1; i >= 0 ; --i)
00369 {
00370 unsigned p = s[i];
00371 if (parent.element(p) == p)
00372 output.element(p) = input.element(p);
00373 else
00374 output.element(p) = output.element(parent.element(p));
00375 }
00376 }
00377
00378 trace::exiting("canvas::morpho::impl::attribute_filter_fastest");
00379 return output;
00380 }
00381
00382 }
00383
00384
00385
00386
00387
00388
00389
00390 namespace internal
00391 {
00392
00393
00394
00395 template <typename I, typename N, typename A>
00396 inline
00397 mln_concrete(I)
00398 attribute_filter_dispatch(metal::false_,
00399 const Image<I>& input,
00400 const Neighborhood<N>& nbh,
00401 const Accumulator<A>& a,
00402 const mln_result(A)& lambda,
00403 bool increasing)
00404 {
00405 p_array<mln_psite(I)> s = increasing ?
00406 data::sort_psites_increasing(input) :
00407 data::sort_psites_decreasing(input);
00408
00409 return impl::generic::attribute_filter(input, nbh, s, a, lambda);
00410 }
00411
00412
00413
00414
00415 template <typename I, typename N, typename A>
00416 inline
00417 mln_concrete(I)
00418 attribute_filter_dispatch(metal::true_,
00419 const Image<I>& input,
00420 const Neighborhood<N>& nbh,
00421 const Accumulator<A>& a,
00422 const mln_result(A)& lambda,
00423 bool increasing)
00424 {
00425 extension::adjust(input, nbh);
00426
00427 util::array<unsigned> s =
00428 increasing ?
00429 data::sort_offsets_increasing(input) :
00430 data::sort_offsets_decreasing(input);
00431
00432 return impl::attribute_filter_fastest(input, nbh, s, a, lambda);
00433 }
00434
00435
00436
00437 template <typename I, typename N, typename A>
00438 inline
00439 mln_concrete(I)
00440 attribute_filter_dispatch(const Image<I>& input,
00441 const Neighborhood<N>& nbh,
00442 const Accumulator<A>& a,
00443 const mln_result(A)& lambda,
00444 bool increasing)
00445 {
00446 enum {
00447 test = (mlc_equal(mln_trait_image_speed(I),
00448 trait::image::speed::fastest)::value &&
00449 mln_is_simple_neighborhood(N)::value &&
00450 (mlc_equal(mln_trait_accumulator_when_pix(A),
00451 trait::accumulator::when_pix::use_none)::value ||
00452 mlc_equal(mln_trait_accumulator_when_pix(A),
00453 trait::accumulator::when_pix::use_v)::value))
00454 };
00455 return attribute_filter_dispatch(metal::bool_<test>(), input, nbh, a, lambda, increasing);
00456 }
00457
00458 }
00459
00460
00461
00462
00463
00464 template <typename I, typename N, typename A>
00465 inline
00466 mln_concrete(I)
00467 attribute_filter(const Image<I>& input,
00468 const Neighborhood<N>& nbh,
00469 const Accumulator<A>& a,
00470 const mln_result(A)& lambda,
00471 bool increasing)
00472 {
00473 return internal::attribute_filter_dispatch(input, nbh, a, lambda, increasing);
00474 }
00475
00476
00477 # endif // ! MLN_INCLUDE_ONLY
00478
00479 }
00480
00481 }
00482
00483 }
00484
00485
00486 #endif // ! MLN_CANVAS_MORPHO_ATTRIBUTE_FILTER_HH