URL: https://svn.lrde.epita.fr/svn/oln/branches/cleanup-2008/milena ChangeLog: 2008-11-18 Matthieu Garrigues <garrigues@lrde.epita.fr> Convert the labeling canvas into a routine. * mln/canvas/labeling.hh: . * mln/labeling/level.hh: Update to use the routine. --- canvas/labeling.hh | 226 ++++++++++++++++++++--------------------------------- labeling/level.hh | 8 - 2 files changed, 92 insertions(+), 142 deletions(-) Index: branches/cleanup-2008/milena/mln/canvas/labeling.hh =================================================================== --- branches/cleanup-2008/milena/mln/canvas/labeling.hh (revision 2891) +++ branches/cleanup-2008/milena/mln/canvas/labeling.hh (revision 2892) @@ -48,15 +48,34 @@ { // General version. + template <typename I, typename N, typename F> + mln_ch_value(I, typename F::L) + labeling(const Image<I>& input, const Neighborhood<N>& nbh, + F& functor, typename F::L& nlabels); - template <typename F> - struct labeling + +# ifndef MLN_INCLUDE_ONLY + + + template <typename I> + static inline + mln_psite(I) + find_root(I& parent, + const mln_psite(I)& x) { - // Functor. - F& f; + if (parent(x) == x) + return x; + else + return parent(x) = find_root(parent, parent(x)); + } + + template <typename I, typename N, typename F> + mln_ch_value(I, typename F::L) + labeling(const Image<I>& input, const Neighborhood<N>& nbh, + F& functor, typename F::L& nlabels) + { + trace::entering("canvas::labeling"); - typedef typename F::I I; - typedef typename F::N N; typedef typename F::L L; typedef typename F::S S; @@ -69,31 +88,78 @@ // Output. mln_ch_value(I, L) output; - L nlabels; bool status; - // Ctor. - labeling(F& f); - - void init(); - - void pass_1(); - - void pass_2(); - - - // Auxiliary methods. + // Initialization. init(); + { + initialize(deja_vu, functor.input); + mln::level::fill(deja_vu, false); + initialize(parent, functor.input); + initialize(output, functor.input); + mln::level::fill(output, L(literal::zero)); + nlabels = 0; + functor.init(); // Client initialization. + } - void make_set(const psite& p); + // First Pass. pass_1(); + { + mln_fwd_piter(S) p(functor.s); + mln_niter(N) n(functor.nbh, p); + for_all(p) if (functor.handles(p)) + { + // Make the set with p as root. make_set(p). + parent(p) = p; + functor.init_attr(p); - bool is_root(const psite& p) const; + for_all(n) + if (functor.input.domain().has(n) && deja_vu(n)) + { + if (functor.equiv(n, p)) + { + // Put p as root. do_union(n, p); + psite r = find_root(parent, n); + if (r != p) + { + parent(r) = p; + functor.merge_attr(r, p); + } + } + else + functor.do_no_union(n, p); + } + deja_vu(p) = true; + } + } - psite find_root(const psite& x); + // Second Pass. pass_2(); + { + mln_bkd_piter(S) p(functor.s); + for_all(p) if (functor.handles(p)) + { + if (parent(p) == p) // if p is root + { + if (functor.labels(p)) + { + if (nlabels == mln_max(L)) + { + status = false; + return output; + } + output(p) = ++nlabels; + } + } + else + output(p) = output(parent(p)); + } + status = true; - void do_union(const psite& n, const psite& p); + } - }; + trace::exiting("canvas::labeling"); + return output; + } +# endif // ! MLN_INCLUDE_ONLY // Fastest version. @@ -136,120 +202,6 @@ # ifndef MLN_INCLUDE_ONLY - /*-------------------. - | canvas::labeling. | - `-------------------*/ - - template <typename F> - labeling<F>::labeling(F& f) - : f(f) - { - trace::entering("canvas::labeling"); - - init(); - f.init(); // Client initialization. - pass_1(); - pass_2(); - - trace::exiting("canvas::labeling"); - } - - template <typename F> - void - labeling<F>::init() - { - initialize(deja_vu, f.input); - mln::level::fill(deja_vu, false); - initialize(parent, f.input); - initialize(output, f.input); - mln::level::fill(output, L(literal::zero)); - nlabels = 0; - } - - template <typename F> - void - labeling<F>::pass_1() - { - mln_fwd_piter(S) p(f.s); - mln_niter(N) n(f.nbh, p); - for_all(p) if (f.handles(p)) - { - make_set(p); - for_all(n) - if (f.input.domain().has(n) && deja_vu(n)) - { - if (f.equiv(n, p)) - do_union(n, p); - else - f.do_no_union(n, p); - } - deja_vu(p) = true; - } - } - - template <typename F> - void - labeling<F>::pass_2() - { - mln_bkd_piter(S) p(f.s); - for_all(p) if (f.handles(p)) - { - if (is_root(p)) - { - if (f.labels(p)) - { - if (nlabels == mln_max(L)) - { - status = false; - return; - } - output(p) = ++nlabels; - } - } - else - output(p) = output(parent(p)); - } - status = true; - } - - template <typename F> - void - labeling<F>::make_set(const psite& p) - { - parent(p) = p; - f.init_attr(p); - } - - template <typename F> - bool - labeling<F>::is_root(const psite& p) const - { - return parent(p) == p; - } - - template <typename F> - typename labeling<F>::psite - labeling<F>::find_root(const psite& x) - { - if (parent(x) == x) - return x; - else - return parent(x) = find_root(parent(x)); - } - - template <typename F> - void - labeling<F>::do_union(const psite& n, const psite& p) - { - psite r = find_root(n); - if (r != p) - { - parent(r) = p; - f.merge_attr(r, p); - } - } - - /*---------------------------. | canvas::labeling_fastest. | `---------------------------*/ Index: branches/cleanup-2008/milena/mln/labeling/level.hh =================================================================== --- branches/cleanup-2008/milena/mln/labeling/level.hh (revision 2891) +++ branches/cleanup-2008/milena/mln/labeling/level.hh (revision 2892) @@ -153,13 +153,11 @@ typedef level_functor<I,N,L> F; F f(exact(input), val, exact(nbh)); - canvas::labeling<F> run(f); - - nlabels = run.nlabels; - // FIXME: Handle run.status + mln_ch_value(I, L) output = canvas::labeling(input, nbh, f, nlabels); + // FIXME: Handle canvas status. trace::exiting("labeling::impl::generic::level"); - return run.output; + return output; } } // end of namespace mln::labeling::impl::generic