[Olena-patches] milena r2926: Put algebraic_union_find into a routine

URL: https://svn.lrde.epita.fr/svn/oln/trunk/milena ChangeLog: 2008-11-19 Matthieu Garrigues &lt;garrigues(a)lrde.epita.fr&gt; Put algebraic_union_find into a routine. * mln/canvas/morpho/algebraic_union_find.hh: algebraic_union_find is now a routine. The old version (functor) is renamed as algebraic_union_find_f. * mln/morpho/closing_attribute.hh, * mln/morpho/opening_attribute.hh: Update to use algebraic_union_find as a routine instead of a functor. --- canvas/morpho/algebraic_union_find.hh | 157 +++++++++++++++++++++++++++++++++- morpho/closing_attribute.hh | 74 ++++++++++++++-- morpho/opening_attribute.hh | 77 +++++++++++++++- 3 files changed, 295 insertions(+), 13 deletions(-) Index: trunk/milena/mln/morpho/closing_attribute.hh =================================================================== --- trunk/milena/mln/morpho/closing_attribute.hh (revision 2925) +++ trunk/milena/mln/morpho/closing_attribute.hh (revision 2926) @@ -56,9 +56,73 @@ namespace impl { + template <typename I, typename A_> + struct closing_attribute_t + { + // requirements from mln::canvas::morpho::algebraic_union_find + + typedef A_ A; + typedef mln_psite(I) P; + typedef p_array<P> S; + + mln_result(A) lambda; + 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 + closing_attribute_t(const Image<I>& input, mln_result(A) lambda) + : lambda(lambda), + s(level::sort_psites_increasing(exact(input))) + { + } + + }; + + } // end of namespace mln::morpho::impl + + + template <typename A, + typename I, typename N, typename O> + inline + void closing_attribute(const Image<I>& input, + const Neighborhood<N>& nbh, mln_result(A) lambda, + Image<O>& output) + { + typedef impl::closing_attribute_t<I, A> F; + F f(input, lambda); + canvas::morpho::algebraic_union_find(input, nbh, f, output); + + mln_postcondition(output >= input); + } + + // ----------------------------------------------------------- + // Old code below. + + namespace impl + { + template <typename A_, typename I_, typename N_, typename O_> - struct closing_attribute_t + struct closing_attribute_t_f { typedef mln_psite(I_) P; @@ -104,7 +168,7 @@ // end of requirements inline - closing_attribute_t(const I_& input, const N_& nbh, + 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)) @@ -119,7 +183,7 @@ template <typename A, typename I, typename N, typename O> inline - void closing_attribute(const Image<I>& input_, + void closing_attribute_f(const Image<I>& input_, const Neighborhood<N>& nbh_, mln_result(A) lambda, Image<O>& output_) { @@ -128,9 +192,9 @@ O& output = exact(output_); mln_precondition(output.domain() == input.domain()); - typedef impl::closing_attribute_t<A,I,N,O> F; + typedef impl::closing_attribute_t_f<A,I,N,O> F; F f(input, nbh, lambda, output); - canvas::morpho::algebraic_union_find<F> run(f); + canvas::morpho::algebraic_union_find_f<F> run(f); mln_postcondition(output >= input); } Index: trunk/milena/mln/morpho/opening_attribute.hh =================================================================== --- trunk/milena/mln/morpho/opening_attribute.hh (revision 2925) +++ trunk/milena/mln/morpho/opening_attribute.hh (revision 2926) @@ -56,9 +56,75 @@ namespace impl { + template <typename I, typename A_> + struct opening_attribute_t + { + // requirements from mln::canvas::morpho::algebraic_union_find + + typedef A_ A; + typedef mln_psite(I) P; + typedef p_array<P> S; + + mln_result(A) lambda; + 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(const Image<I>& input, mln_result(A) lambda) + : lambda(lambda), + s(level::sort_psites_decreasing(exact(input))) + { + } + + }; + + } // end of namespace mln::morpho::impl + + + template <typename A, + typename I, typename N, typename O> + inline + void opening_attribute(const Image<I>& input, + const Neighborhood<N>& nbh, mln_result(A) lambda, + Image<O>& output) + { + typedef impl::opening_attribute_t<I, A> F; + F f(input, lambda); + canvas::morpho::algebraic_union_find(input, nbh, f, output); + + mln_postcondition(output <= input); + } + + + // ----------------------------------------------------------- + // Old code below. + + + namespace impl + { + template <typename A_, typename I_, typename N_, typename O_> - struct opening_attribute_t + struct opening_attribute_t_f { typedef mln_psite(I_) P; @@ -99,7 +165,7 @@ // end of requirements inline - opening_attribute_t(const I_& input, const N_& nbh, + 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)) @@ -114,7 +180,7 @@ template <typename A, typename I, typename N, typename O> inline - void opening_attribute(const Image<I>& input_, + void opening_attribute_f(const Image<I>& input_, const Neighborhood<N>& nbh_, mln_result(A) lambda, Image<O>& output_) { @@ -123,13 +189,14 @@ O& output = exact(output_); mln_precondition(output.domain() == input.domain()); - typedef impl::opening_attribute_t<A,I,N,O> F; + typedef impl::opening_attribute_t_f<A,I,N,O> F; F f(input, nbh, lambda, output); - canvas::morpho::algebraic_union_find<F> run(f); + canvas::morpho::algebraic_union_find_f<F> run(f); mln_postcondition(output <= input); } + # endif // ! MLN_INCLUDE_ONLY } // end of namespace mln::morpho Index: trunk/milena/mln/canvas/morpho/algebraic_union_find.hh =================================================================== --- trunk/milena/mln/canvas/morpho/algebraic_union_find.hh (revision 2925) +++ trunk/milena/mln/canvas/morpho/algebraic_union_find.hh (revision 2926) @@ -49,10 +49,162 @@ namespace morpho { + // FIXME: Is it really needed? + struct opening_attribute_functor_base + { + 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 + mln_psite(I) + find_root(I& parent, + const mln_psite(I)& x) + { + if (parent(x) == x) + return x; + else + return parent(x) = find_root(parent, parent(x)); + } + + template <typename I, typename N, typename F, typename O> + void + algebraic_union_find(const Image<I>& input_, + const Neighborhood<N>& nbh_, + F& f, + Image<O>& output_) + { + trace::entering("canvas::morpho::algebraic_union_find"); + + // FIXME: Tests? + + typedef typename F::S S; + typedef typename F::A A; + + const I& input = exact(input_); + const N& nbh = exact(nbh_); + O& output = exact(output_); + + mln_precondition(output.domain() == input.domain()); + + // Local type. + typedef mln_psite(I) P; + + // Auxiliary data. + mln_ch_value(O, bool) deja_vu; + mln_ch_value(O, P) parent; + mln_ch_value(O, A) data; + + // init + { + initialize(deja_vu, input); + mln::level::fill(deja_vu, false); + initialize(parent, input); + initialize(data, input); + f.init(); // init required. + } + + // first pass + { + mln_fwd_piter(S) p(f.s); // s required. + mln_niter(N) n(nbh, p); + for_all(p) + { + // Make set. + { + 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. + + 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. + + 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(input, p)); // FIXME: algebraic so p! + } + + for_all(n) + if (input.domain().has(n) && deja_vu(n)) + { + //do_union(n, p); + P r = find_root(parent, n); + if (r != p) + { + if (input(r) == input(p) || f.is_active(data(r))) // Equiv(r, p) + // Either a flat zone or the component of r is still growing. + { + /* FIXME: Same remark as above concerning the + initialization of data(p); instead of + + data(p).take(data(r)); + + we should (or could) have + + 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)); + } + } + deja_vu(p) = true; + } + } + + // second pass + { + mln_bkd_piter(S) p(f.s); + for_all(p) + if (parent(p) == p) // p is root. + output(p) = input(p); + else + output(p) = output(parent(p)); + } + + /* + Change 2nd pass into: + for_all(p) if (not is_root(p)) output(p) = output(parent(p)); + and add in init: + mln::level::assign(output, input); + */ + trace::exiting("canvas::morpho::algebraic_union_find"); + } + + + // ----------------------------------------------------------- + // Old code below. + // General version. template <typename F> - struct algebraic_union_find + struct algebraic_union_find_f { F& f; @@ -68,7 +220,7 @@ mln_ch_value(O, psite) parent; mln_ch_value(O, A) data; - algebraic_union_find(F& f) + algebraic_union_find_f(F& f) : f(f) { run(); @@ -194,7 +346,6 @@ }; - // FIXME: Fast version.