[Olena-patches] 3226: Prepare to fastest the morpho canvas of algebraic union find.

https://svn.lrde.epita.fr/svn/oln/trunk/milena Index: ChangeLog from Thierry Geraud &lt;thierry.geraud(a)lrde.epita.fr&gt; Prepare to fastest the morpho canvas of algebraic union find. * mln/canvas/morpho/algebraic_union_find.hh (opening_attribute_functor_base): Remove; useless. (impl): New sub-namespace. (find_root, algebraic_union_find): Move into impl. (dispatch): New sub-namespace. (algebraic_union_find_dispatch): New. (algebraic_union_find): New facade. * mln/morpho/closing_attribute.hh (closing_attribute_t_f, closing_attribute_f): Remove dead code. (closing_attribute): Update. * mln/morpho/opening_attribute.hh (opening_attribute_t_f, opening_attribute_f): Remove dead code. (opening_attribute): Update. * tests/convert/impl/Makefile.am: New. * tests/convert/Makefile.am: Update. mln/canvas/morpho/algebraic_union_find.hh | 199 +++++------------------------- mln/morpho/closing_attribute.hh | 94 -------------- mln/morpho/opening_attribute.hh | 91 ------------- tests/convert/Makefile.am | 2 tests/convert/impl/Makefile.am | 10 + 5 files changed, 58 insertions(+), 338 deletions(-) Index: mln/morpho/closing_attribute.hh --- mln/morpho/closing_attribute.hh (revision 3225) +++ mln/morpho/closing_attribute.hh (working copy) @@ -100,6 +100,9 @@ } // end of namespace mln::morpho::impl + + // Facade. + template <typename A, typename I, typename N> inline mln_concrete(I) @@ -110,12 +113,9 @@ mln_precondition(exact(input).is_valid()); - mln_concrete(I) output; - initialize(output, input); - typedef impl::closing_attribute_t<I, A> F; F f(input, lambda); - canvas::morpho::algebraic_union_find(input, nbh, f, output); + mln_concrete(I) output = canvas::morpho::algebraic_union_find(input, nbh, f); mln_postcondition(output >= input); @@ -124,92 +124,6 @@ } - /* ----------------------------------------------------------- - - Old code below. - - namespace impl - { - - template <typename A_, - typename I_, typename N_, typename O_> - struct closing_attribute_t_f - { - typedef mln_psite(I_) P; - - // requirements from mln::canvas::morpho::algebraic_union_find - - typedef A_ A; - typedef I_ I; - typedef N_ N; - typedef O_ O; - typedef p_array<P> S; - typedef util::pix<I> pix_t; - - const I& input; - const N& nbh; - mln_result(A) lambda; - O& output; - - const S s; - - inline - void init() - { - // FIXME: border::fill(input, mln_max(mln_value(I))); - // FIXME: Shouldn't it be - // border::fill(input, mln_max(mln_value(I))) - // instead? - } - - inline - bool is_active(const A& attr) const - { - return attr.to_result() < lambda; - } - - inline - void inactivate(A& attr) - { - attr.set_value(lambda); - } - - // end of requirements - - inline - closing_attribute_t_f(const I_& input, const N_& nbh, - mln_result(A) lambda, O_& output) - : input(input), nbh(nbh), lambda(lambda), output(output), - s(level::sort_psites_increasing(input)) - { - } - - }; - - } // end of namespace mln::morpho::impl - - - template <typename A, - typename I, typename N, typename O> - inline - void closing_attribute_f(const Image<I>& input_, - const Neighborhood<N>& nbh_, mln_result(A) lambda, - Image<O>& output_) - { - const I& input = exact(input_); - const N& nbh = exact(nbh_); - O& output = exact(output_); - mln_precondition(output.domain() == input.domain()); - - typedef impl::closing_attribute_t_f<A,I,N,O> F; - F f(input, nbh, lambda, output); - canvas::morpho::algebraic_union_find_f<F> run(f); - - mln_postcondition(output >= input); - } - - */ - # endif // ! MLN_INCLUDE_ONLY } // end of namespace mln::morpho Index: mln/morpho/opening_attribute.hh --- mln/morpho/opening_attribute.hh (revision 3225) +++ mln/morpho/opening_attribute.hh (working copy) @@ -102,6 +102,8 @@ } // end of namespace mln::morpho::impl + // Facade. + template <typename A, typename I, typename N> inline mln_concrete(I) @@ -112,101 +114,16 @@ mln_precondition(exact(input).is_valid()); - mln_concrete(I) output; - initialize(output, input); - typedef impl::opening_attribute_t<I, A> F; F f(input, lambda); - canvas::morpho::algebraic_union_find(input, nbh, f, output); + mln_concrete(I) output = canvas::morpho::algebraic_union_find(input, nbh, f); mln_postcondition(output <= input); + trace::exiting("morpho::opening_attribute"); return output; } - - // ----------------------------------------------------------- - // Old code below. - - - namespace impl - { - - template <typename A_, - typename I_, typename N_, typename O_> - struct opening_attribute_t_f - { - typedef mln_psite(I_) P; - - // requirements from mln::canvas::morpho::algebraic_union_find - - typedef A_ A; - typedef I_ I; - typedef N_ N; - typedef O_ O; - typedef p_array<P> S; - typedef util::pix<I> pix_t; - - const I& input; - const N& nbh; - mln_result(A) lambda; - O& output; - - const S s; - - inline - void init() - { - // FIXME: border::fill(input, mln_max(mln_value(I))); - } - - inline - bool is_active(const A& attr) const - { - return attr.to_result() < lambda; - } - - inline - void inactivate(A& attr) - { - attr.set_value(lambda); - } - - // end of requirements - - inline - opening_attribute_t_f(const I_& input, const N_& nbh, - mln_result(A) lambda, O_& output) - : input(input), nbh(nbh), lambda(lambda), output(output), - s(level::sort_psites_decreasing(input)) - { - } - - }; - - } // end of namespace mln::morpho::impl - - - template <typename A, - typename I, typename N, typename O> - inline - void opening_attribute_f(const Image<I>& input_, - const Neighborhood<N>& nbh_, mln_result(A) lambda, - Image<O>& output_) - { - const I& input = exact(input_); - const N& nbh = exact(nbh_); - O& output = exact(output_); - mln_precondition(output.domain() == input.domain()); - - typedef impl::opening_attribute_t_f<A,I,N,O> F; - F f(input, nbh, lambda, output); - canvas::morpho::algebraic_union_find_f<F> run(f); - - mln_postcondition(output <= input); - } - - # endif // ! MLN_INCLUDE_ONLY } // end of namespace mln::morpho Index: mln/canvas/morpho/algebraic_union_find.hh --- mln/canvas/morpho/algebraic_union_find.hh (revision 3225) +++ mln/canvas/morpho/algebraic_union_find.hh (working copy) @@ -48,24 +48,13 @@ namespace morpho { - // FIXME: Is it really needed? - struct opening_attribute_functor_base + namespace impl { - inline void init() {} - - template <typename A> - inline bool is_active(const A&) const { return false; } - - template <typename A> - inline void inactivate(A&) {} - }; - template <typename I> - static inline + inline mln_psite(I) - find_root(I& parent, - const mln_psite(I)& x) + find_root(I& parent, const mln_psite(I)& x) { if (parent(x) == x) return x; @@ -73,12 +62,12 @@ return parent(x) = find_root(parent, parent(x)); } - template <typename I, typename N, typename F, typename O> - void + template <typename I, typename N, typename F> + inline + mln_concrete(I) algebraic_union_find(const Image<I>& input_, const Neighborhood<N>& nbh_, - F& f, - Image<O>& output_) + F& f) { trace::entering("canvas::morpho::algebraic_union_find"); @@ -89,20 +78,20 @@ const I& input = exact(input_); const N& nbh = exact(nbh_); - O& output = exact(output_); - mln_precondition(output.domain() == input.domain()); + mln_concrete(I) output; + initialize(output, input); // Local type. typedef mln_psite(I) P; // Auxiliary data. - mln_ch_value(O, bool) deja_vu; + mln_ch_value(I, bool) deja_vu; mln_ch_value(I, bool) activity; - mln_ch_value(O, P) parent; - mln_ch_value(O, A) data; + mln_ch_value(I, P) parent; + mln_ch_value(I, A) data; - // init + // Initialization. { initialize(deja_vu, input); mln::data::fill(deja_vu, false); @@ -113,7 +102,7 @@ f.init(); // init required. } - // first pass + // First pass. { mln_fwd_piter(S) p(f.s); // s required. mln_niter(N) n(nbh, p); @@ -185,7 +174,7 @@ } } - // second pass + // Second pass. { mln_bkd_piter(S) p(f.s); for_all(p) @@ -202,159 +191,47 @@ mln::data::fill(output, input); */ trace::exiting("canvas::morpho::algebraic_union_find"); - } - - - // ----------------------------------------------------------- - // Old code below. - - // General version. - - template <typename F> - struct algebraic_union_find_f - { - F& f; - - typedef typename F::I I; - typedef typename F::N N; - typedef typename F::O O; - typedef typename F::S S; - typedef typename F::A A; - typedef mln_psite(I) psite; - // aux: - mln_ch_value(O, bool) deja_vu; - mln_ch_value(O, psite) parent; - mln_ch_value(O, A) data; - - algebraic_union_find_f(F& f) - : f(f) - { - run(); + return output; } - void run() - { - // init - { - initialize(deja_vu, f.input); - mln::data::fill(deja_vu, false); - initialize(parent, f.input); - initialize(data, f.input); - f.init(); - } - - // first pass - { - mln_fwd_piter(S) p(f.s); - mln_niter(N) n(f.nbh, p); - for_all(p) - { - make_set(p); - for_all(n) - if (f.input.domain().has(n) && deja_vu(n)) - do_union(n, p); - deja_vu(p) = true; - } - } - - // second pass - { - mln_bkd_piter(S) p(f.s); - for_all(p) - if (is_root(p)) - f.output(p) = f.input(p); - else - f.output(p) = f.output(parent(p)); - } - - /* - Change 2nd pass into: - for_all(p) if (not is_root(p)) f.output(p) = f.output(parent(p)); - and add in init: - mln::data::fill(f.output, f.input); - */ - - } // end of run() - - void make_set(const psite& p) - { - parent(p) = p; - /* FIXME: What if the value_type of DATA (i.e., A) were not - based on a accu::count<mln::pix>? Currently, nothing - enforces this, but the code below expects this line to be - valid: - - data(p).take_as_init(make::pix(f.input, p)) - - which probably restricts the kind of input images. + } // end of namespace mln::canvas::morpho::impl - If we want to be more generic, the initialization should - read something like: - init_data(p); - i.e., the functor for the initialization of data should - be passed as an argument to the canvas' ctor. + // Dispatch. - Of course, we might want to restrict attributes to the - accumulator accu::count<mln::pix> (which is perfectly - acceptable), but then this class should statically check - the conformance of the template parameter A to this - constraint. */ - data(p).take_as_init(make::pix(f.input, p)); // FIXME: algebraic so p! - } - - bool is_root(const psite& p) const + namespace internal { - return parent(p) == p; - } - psite find_root(const psite& x) + template <typename I, typename N, typename F> + inline + mln_concrete(I) + algebraic_union_find_dispatch(trait::image::speed::any, + const Image<I>& input, + const Neighborhood<N>& nbh, + F& f) { - if (parent(x) == x) - return x; - else - return parent(x) = find_root(parent(x)); + return impl::algebraic_union_find(input, nbh, f); } - bool equiv(const psite& r, const psite& p) - { - // Either a flat zone or the component of r is still growing. - return f.input(r) == f.input(p) || f.is_active(data(r)); - } + } // end of namespace mln::canvas::morpho::internal - void do_union(const psite& n, const psite& p) - { - psite r = find_root(n); - if (r != p) - { - if (equiv(r, p)) - { - /* FIXME: Same remark as above concerning the - initialization of data(p); instead of - data(p).take(data(r)); - we should (or could) have + // Facade. - unite_data(p, r); - - so as to keep the generic aspect of this canvas - (as long as the set of acceptable types for the - template parameter A is not bound). */ - data(p).take(data(r)); - parent(r) = p; - } - else - f.inactivate(data(p)); - } + template <typename I, typename N, typename F> + inline + mln_concrete(I) + algebraic_union_find(const Image<I>& input, + const Neighborhood<N>& nbh, + F& f) + { + return internal::algebraic_union_find_dispatch(mln_trait_image_speed(I)(), + input, nbh, f); } - }; - - // FIXME: Fast version. - } // end of namespace mln::canvas::morpho Index: tests/convert/impl/Makefile.am --- tests/convert/impl/Makefile.am (revision 0) +++ tests/convert/impl/Makefile.am (revision 0) @@ -0,0 +1,10 @@ +## Process this file through Automake to create Makefile.in -*- Makefile -*- + +include $(top_srcdir)/milena/tests/tests.mk + +check_PROGRAMS = \ + from_site_set_to_image + +from_site_set_to_image_SOURCES = from_site_set_to_image.cc + +TESTS = $(check_PROGRAMS) Index: tests/convert/Makefile.am --- tests/convert/Makefile.am (revision 3225) +++ tests/convert/Makefile.am (working copy) @@ -2,6 +2,8 @@ include $(top_srcdir)/milena/tests/tests.mk +SUBDIRS = impl + ##FIXME: re-enable all tests check_PROGRAMS = \ to_hsl \