[Olena-patches] milena r3319: Implement fastest versions of labeling

URL: https://svn.lrde.epita.fr/svn/oln/trunk/milena ChangeLog: 2009-02-09 Fabien Freling &lt;freling(a)lrde.epita.fr&gt; Implement fastest versions of labeling. * mln/canvas/labeling.hh: Change labeling() to labeling_video() and * labeling_sorted(). * mln/labeling/flat_zones.hh: Implement fastest version. * mln/labeling/level.hh: Implement fastest version. * mln/labeling/regional_maxima.hh: Implement fastest version. * mln/labeling/regional_minima.hh: Implement fastest version. --- canvas/labeling.hh | 419 ++++++++++++++++++++++++++++++++++++++++---- labeling/flat_zones.hh | 61 ++---- labeling/level.hh | 102 ++-------- labeling/regional_maxima.hh | 70 ++----- labeling/regional_minima.hh | 76 +++---- 5 files changed, 498 insertions(+), 230 deletions(-) Index: trunk/milena/mln/canvas/labeling.hh =================================================================== --- trunk/milena/mln/canvas/labeling.hh (revision 3318) +++ trunk/milena/mln/canvas/labeling.hh (revision 3319) @@ -1,5 +1,5 @@ -// Copyright (C) 2007, 2008, 2009 EPITA Research and Development -// Laboratory (LRDE) +// Copyright (C) 2007, 2008 EPITA Research and Development Laboratory +// (LRDE) // // This file is part of the Olena Library. This library is free // software; you can redistribute it and/or modify it under the terms @@ -39,6 +39,10 @@ # include <mln/data/fill.hh> # include <mln/literal/zero.hh> # include <mln/convert/to_upper_window.hh> +# include <mln/extension/adjust_fill.hh> + +# include <mln/level/sort_psites.hh> +# include <mln/level/sort_offsets.hh> namespace mln @@ -47,11 +51,20 @@ namespace canvas { - // General version. - template <typename I, typename N, typename F, typename L> + template <typename I, typename N, typename L, + typename F> + mln_ch_value(I, L) + labeling_video(const Image<I>& input, const Neighborhood<N>& nbh, L& nlabels, + F& functor); + + + template <typename I, typename N, typename L, + typename F> mln_ch_value(I, L) - labeling(const Image<I>& input, const Neighborhood<N>& nbh, - F& functor, L& nlabels); + labeling_sorted(const Image<I>& input, const Neighborhood<N>& nbh, L& nlabels, + F& functor, bool increasing); + + # ifndef MLN_INCLUDE_ONLY @@ -61,21 +74,22 @@ namespace internal { - template <typename I, typename N, typename F, typename L> + template <typename I, typename N, typename L, + typename F> void - labeling_tests(const Image<I>& input_, const Neighborhood<N>& nbh_, - const F& f, const L& nlabels) + labeling_tests(const Image<I>& input_, const Neighborhood<N>& nbh_, const L& nlabels, + const F& f) { const I& input = exact(input_); const N& nbh = exact(nbh_); mln_precondition(input.is_valid()); - mln_precondition(nbh.is_valid()); + // mln_precondition(nbh.is_valid()); (void) input; (void) nbh; - (void) f; (void) nlabels; + (void) f; } } // end of namespace mln::canvas::internal @@ -101,10 +115,11 @@ return parent(x) = find_root(parent, parent(x)); } - template <typename I, typename N, typename F, typename L> + template <typename I, typename N, typename L, + typename S, typename F> mln_ch_value(I, L) - labeling(const Image<I>& input_, const Neighborhood<N>& nbh_, - F& f, L& nlabels) + labeling(const Image<I>& input_, const Neighborhood<N>& nbh_, L& nlabels, + const S& s, F& f) { trace::entering("canvas::impl::generic::labeling"); @@ -113,8 +128,6 @@ const I& input = exact(input_); const N& nbh = exact(nbh_); - typedef typename F::S S; - // Local type. typedef mln_psite(I) P; @@ -124,6 +137,7 @@ // Output. mln_ch_value(I, L) output; + bool status; // Initialization. { @@ -141,7 +155,7 @@ // First Pass. { - mln_fwd_piter(S) p(f.s); + mln_fwd_piter(S) p(s); mln_niter(N) n(nbh, p); for_all(p) if (f.handles(p)) { @@ -171,7 +185,7 @@ // Second Pass. { - mln_bkd_piter(S) p(f.s); + mln_bkd_piter(S) p(s); for_all(p) if (f.handles(p)) { if (parent(p) == p) // if p is root @@ -180,7 +194,7 @@ { if (nlabels == mln_max(L)) { - trace::warning("labeling aborted!"); + status = false; return output; } output(p) = ++nlabels; @@ -189,6 +203,7 @@ else output(p) = output(parent(p)); } + status = true; } trace::exiting("canvas::impl::generic::labeling"); @@ -197,6 +212,244 @@ } // end of namespace mln::canvas::impl::generic + + + // Fastest video version. + + template <typename I> + static inline + unsigned + find_root_fastest(I& parent, unsigned x) + { + if (parent.element(x) == x) + return x; + else + return parent.element(x) = find_root_fastest(parent, parent.element(x)); + } + + + template <typename I, typename N, typename L, + typename F> + mln_ch_value(I, L) + labeling_video_fastest(const Image<I>& input_, const Neighborhood<N>& nbh_, + L& nlabels, F& f) + { + trace::entering("canvas::impl::labeling_video_fastest"); + + // FIXME: Test?! + + const I& input = exact(input_); + const N& nbh = exact(nbh_); + + extension::adjust(input, nbh); + + // Auxiliary data. + mln_ch_value(I, bool) deja_vu; + mln_ch_value(I, unsigned) parent; + + // Output. + mln_ch_value(I, L) output; + bool status; + + // Initialization. + { + initialize(deja_vu, input); + mln::data::fill(deja_vu, false); + extension::fill(deja_vu, false); // So that the extension is ignored. + + initialize(parent, input); + + initialize(output, input); + mln::data::fill(output, L(literal::zero)); + nlabels = 0; + + f.init_(); // Client initialization. + } + + // First Pass. + { + mln_pixter(const I) px(input); + mln_nixter(const I, N) nx(px, nbh); + for_all(px) + { + unsigned p = px.offset(); + if (! f.handles_(p)) + continue; + + // Make-Set. + parent.element(p) = p; + f.init_attr_(p); + for_all(nx) + { + unsigned n = nx.offset(); + if (deja_vu.element(n)) + { + if (f.equiv_(n, p)) + { + // Do-Union. + unsigned r = find_root_fastest(parent, n); + if (r != p) + { + parent.element(r) = p; + f.merge_attr_(r, p); + } + } + else + f.do_no_union_(n, p); + } + } + + deja_vu.element(p) = true; + } + } + + // Second Pass. + { + mln_bkd_pixter(const I) px(input); + for_all(px) + { + unsigned p = px.offset(); + if (! f.handles_(p)) + continue; + if (parent.element(p) == p) // if p is root + { + if (f.labels_(p)) + { + if (nlabels == mln_max(L)) + { + status = false; + return output; + } + output.element(p) = ++nlabels; + } + } + else + output.element(p) = output.element(parent.element(p)); + } + status = true; + } + + trace::exiting("canvas::impl::labeling_video_fastest"); + return output; + } + + + + // Fastest sorted version + + template <typename I, typename N, typename L, + typename S, typename F> + mln_ch_value(I, L) + labeling_sorted_fastest(const Image<I>& input_, const Neighborhood<N>& nbh_, L& nlabels, + const S& s, F& f) + { + trace::entering("canvas::impl::labeling_sorted_fastest"); + + // FIXME: Test?! + + const I& input = exact(input_); + const N& nbh = exact(nbh_); + + extension::adjust(input, nbh); + + // Local type. + typedef mln_psite(I) P; + + // Auxiliary data. + mln_ch_value(I, bool) deja_vu; + mln_ch_value(I, unsigned) parent; + + // Output. + mln_ch_value(I, L) output; + bool status; + + // Initialization. + { + initialize(deja_vu, input); + mln::data::fill(deja_vu, false); + extension::fill(deja_vu, false); // So that the extension is ignored. + + initialize(parent, input); + + initialize(output, input); + mln::data::fill(output, L(literal::zero)); + nlabels = 0; + + f.init_(); // Client initialization. + } + + util::array<int> dp = offsets_wrt(input, nbh); + const unsigned n_nbhs = dp.nelements(); + + const unsigned n_points = s.nelements(); + + // First Pass. + { + + for (unsigned i = 0; i < n_points; ++i) + { + unsigned p = s[i]; + if (! f.handles_(p)) + continue; + + // Make-Set. + parent.element(p) = p; + f.init_attr_(p); + + for (unsigned j = 0; j < n_nbhs; ++j) + { + unsigned n = p + dp[j]; + if (! deja_vu.element(n)) + continue; + + if (f.equiv_(n, p)) + { + // Do-Union. + unsigned r = find_root_fastest(parent, n); + if (r != p) + { + parent.element(r) = p; + f.merge_attr_(r, p); + } + } + else + f.do_no_union_(n, p); + } + deja_vu.element(p) = true; + + } + } + + // Second Pass. + { + for (int i = n_points - 1; i >=0; --i) + { + unsigned p = s[i]; + if (! f.handles_(p)) + continue; + + if (parent.element(p) == p) // if p is root + { + if (f.labels_(p)) + { + if (nlabels == mln_max(L)) + { + status = false; + return output; + } + output.element(p) = ++nlabels; + } + } + else + output.element(p) = output.element(parent.element(p)); + } + status = true; + } + + trace::exiting("canvas::impl::labeling_sorted_fastest"); + return output; + } + } // end of namespace mln::canvas::impl @@ -206,39 +459,143 @@ namespace internal { - template <typename I, typename N, typename F, typename L> + // Video + + template <typename I, typename N, typename L, + typename F> inline mln_ch_value(I, L) - labeling_dispatch(const Image<I>& input, const Neighborhood<N>& nbh, - F& functor, L& nlabels) + labeling_video(metal::false_, const Image<I>& input, + const Neighborhood<N>& nbh, L& nlabels, F& functor) { - return impl::generic::labeling(input, nbh, functor, nlabels); + return impl::generic::labeling(input, nbh, input.domain(), + nlabels, functor); } + template <typename I, typename N, typename L, + typename F> + inline + mln_ch_value(I, L) + labeling_video(metal::true_, const Image<I>& input, + const Neighborhood<N>& nbh, L& nlabels, F& functor) + { + return impl::labeling_video_fastest(input, nbh, nlabels, functor); + } + + template <typename I, typename N, typename L, + typename F> + inline + mln_ch_value(I, L) + labeling_video_dispatch(const Image<I>& input, const Neighborhood<N>& nbh, + L& nlabels, F& functor) + { + enum { + test = mlc_equal(mln_trait_image_speed(I), + trait::image::speed::fastest)::value + && + mln_is_simple_neighborhood(N)::value + }; + return labeling_video(metal::bool_<test>(), input, + nbh, nlabels, functor); + } + + + // Sorted dispatch. + + template <typename I, typename N, typename L, typename F> + inline + mln_ch_value(I, L) + labeling_sorted_dispatch(metal::false_, + const Image<I>& input, const Neighborhood<N>& nbh, L& nlabels, + F& functor, bool increasing) + { + p_array<mln_psite(I)> s = + increasing ? + level::sort_psites_increasing(input) : + level::sort_psites_decreasing(input); + return impl::generic::labeling(input, nbh, nlabels, + s, functor); + } + + template <typename I, typename N, typename L, typename F> + inline + mln_ch_value(I, L) + labeling_sorted_dispatch(metal::true_, + const Image<I>& input, const Neighborhood<N>& nbh, L& nlabels, + F& functor, bool increasing) + { + util::array<unsigned> s = + increasing ? + level::sort_offsets_increasing(input) : + level::sort_offsets_decreasing(input); + return impl::labeling_sorted_fastest(input, nbh, nlabels, + s, functor); + } + + template <typename I, typename N, typename L, typename F> + inline + mln_ch_value(I, L) + labeling_sorted_dispatch(const Image<I>& input, const Neighborhood<N>& nbh, L& nlabels, + F& functor, bool increasing) + { + enum { + test = mlc_equal(mln_trait_image_speed(I), + trait::image::speed::fastest)::value + && + mln_is_simple_neighborhood(N)::value + }; + return labeling_sorted_dispatch(metal::bool_<test>(), + input, nbh, nlabels, + functor, increasing); + } + + } // end of namespace mln::canvas::internal - // Facade. + // Facades. + - template <typename I, typename N, typename F, typename L> + template <typename I, typename N, typename L, + typename F> inline mln_ch_value(I, L) - labeling(const Image<I>& input, const Neighborhood<N>& nbh, - F& functor, L& nlabels) + labeling_video(const Image<I>& input, const Neighborhood<N>& nbh, L& nlabels, + F& functor) { - trace::entering("canvas::labeling"); + trace::entering("canvas::labeling_video"); - internal::labeling_tests(input, nbh, functor, nlabels); + internal::labeling_tests(input, nbh, nlabels, functor); mln_ch_value(I, L) output; - output = internal::labeling_dispatch(input, nbh, functor, nlabels); + output = internal::labeling_video_dispatch(input, nbh, nlabels, + functor); - trace::exiting("canvas::labeling"); + trace::exiting("canvas::labeling_video"); return output; } + template <typename I, typename N, typename L, + typename F> + inline + mln_ch_value(I, L) + labeling_sorted(const Image<I>& input, const Neighborhood<N>& nbh, L& nlabels, + F& functor, bool increasing) + { + trace::entering("canvas::labeling_sorted"); + + internal::labeling_tests(input, nbh, nlabels, functor); + + mln_ch_value(I, L) output; + output = internal::labeling_sorted_dispatch(input, nbh, nlabels, + functor, increasing); + + trace::exiting("canvas::labeling_sorted"); + return output; + } + # endif // ! MLN_INCLUDE_ONLY } // end of namespace mln::canvas Index: trunk/milena/mln/labeling/flat_zones.hh =================================================================== --- trunk/milena/mln/labeling/flat_zones.hh (revision 3318) +++ trunk/milena/mln/labeling/flat_zones.hh (revision 3319) @@ -64,64 +64,47 @@ // Flat zone functor for the labeling canvas. - template <typename I_, typename N_, typename L_> + template <typename I> struct flat_zones_functor { - typedef mln_psite(I_) P; + typedef mln_psite(I) P; - // requirements from mln::canvas::labeling: + // Requirements from mln::canvas::labeling: - typedef I_ I; - typedef N_ N; - typedef L_ L; typedef mln_pset(I) S; const I& input; - const N& nbh; - const S& s; + // Generic implementation. + + void init() {} bool handles(const P&) const { return true; } bool equiv(const P& n, const P& p) const { return input(n) == input(p); } - - void init() {} bool labels(const P&) const { return true; } void do_no_union(const P&, const P&) {} void init_attr(const P&) {} void merge_attr(const P&, const P&) {} - // end of requirements + // Fastest implementation. + + void init_() {} + bool handles_(unsigned) const { return true; } + bool equiv_(unsigned n, unsigned p) const { return input.element(n) == + input.element(p); } + bool labels_(unsigned) const { return true; } + void do_no_union_(unsigned, unsigned) {} + void init_attr_(unsigned) {} + void merge_attr_(unsigned, unsigned) {} + + // end of requirements. flat_zones_functor(const I& input, const N& nbh) - : input(input), - nbh(nbh), - s(input.domain()) + : input(input) {} }; - // Generic implementation. - - namespace generic - { - - template <typename I, typename N, typename L> - mln_ch_value(I, L) - flat_zones(const Image<I>& input, const Neighborhood<N>& nbh, L& nlabels) - { - trace::entering("labeling::impl::generic::flat_zones"); - - typedef flat_zones_functor<I,N,L> F; - F f(exact(input), exact(nbh)); - mln_ch_value(I, L) output = canvas::labeling(input, nbh, f, nlabels); - - trace::exiting("labeling::impl::generic::flat_zones"); - return output; - } - - } // end of namespace mln::labeling::impl::generic - - } // end of namespace mln::labeling::impl @@ -139,8 +122,10 @@ const N& nbh = exact(nbh_); mln_precondition(input.is_valid()); - // Calls the only (generic) impl. - mln_ch_value(I, L) output = impl::generic::flat_zones(input, nbh, nlabels); + // Calls the only implementation. + typedef flat_zones_functor<I,N,L> F; + F f(exact(input), exact(nbh)); + mln_ch_value(I, L) output = canvas::labeling_video(input, nbh, nlabels, f); trace::exiting("labeling::flat_zones"); return output; Index: trunk/milena/mln/labeling/level.hh =================================================================== --- trunk/milena/mln/labeling/level.hh (revision 3318) +++ trunk/milena/mln/labeling/level.hh (revision 3319) @@ -36,11 +36,10 @@ # include <mln/core/concept/image.hh> # include <mln/core/concept/neighborhood.hh> -# include <mln/canvas/labeling.hh> -# include <mln/data/fill.hh> -// The 'fastest' specialization is in: -# include <mln/labeling/level.spe.hh> +# include "labeling.hh" + +# include <mln/data/fill.hh> @@ -79,7 +78,7 @@ L& nlabels) { mln_precondition(exact(input).is_valid()); - mln_precondition(exact(nbh).is_valid()); + // mln_precondition(exact(nbh).is_valid()); (void) input; (void) val; @@ -91,40 +90,13 @@ - // Generic implementation. - namespace impl { - - struct labeling_functor_base - { - void init() {} - - template <typename P> - bool handles(const P&) const { return true; } - - template <typename L, typename R> - bool equiv(const L&, const R&) const { return false; } - - template <typename P> - bool labels(const P&) const { return true; } - - template <typename L, typename R> - void do_no_union(const L&, const R&) {} - - template <typename P> - void init_attr(const P&) {} - - template <typename L, typename R> - void merge_attr(const L&, const R&) {} - }; - - // Generic functor. template <typename I> - struct level_functor : labeling_functor_base + struct level_functor { typedef mln_psite(I) P; @@ -134,68 +106,39 @@ // Requirements from mln::canvas::labeling. typedef mln_pset(I) S; - const S& s; + + // Generic implementation void init() {} bool handles(const P& p) const { return input(p) == val; } bool equiv(const P& n, const P&) const { return input(n) == val; } bool labels(const P&) const { return true; } + void do_no_union(const P& n, const P& p) {} + void init_attr(const P&) {} + void merge_attr(const P& r, const P& p) {} + + // Fastest implementation + + void init_() {} + bool handles_(unsigned p) const { return input.element(p) == val; } + bool equiv_(unsigned n, unsigned) const { return input.element(n) == val; } + bool labels_(unsigned) const { return true; } + void do_no_union_(unsigned n, unsigned p) {} + void init_attr_(unsigned) {} + void merge_attr_(unsigned r, unsigned p) {} // end of Requirements. level_functor(const Image<I>& input_, const mln_value(I)& val) : input(exact(input_)), - val(val), - s(input.domain()) + val(val) { } }; - - - // Generic implementation. - - namespace generic - { - - template <typename I, typename N, typename L> - mln_ch_value(I, L) - level(const Image<I>& input, const mln_value(I)& val, - const Neighborhood<N>& nbh, - L& nlabels) - { - trace::entering("labeling::impl::generic::level"); - - internal::level_tests(input, val, nbh, nlabels); - - level_functor<I> f(input, val); - mln_ch_value(I, L) output = canvas::labeling(input, nbh, f, nlabels); - - trace::exiting("labeling::impl::generic::level"); - return output; - } - - } // end of namespace mln::labeling::impl::generic - - } // end of namespace mln::labeling::impl - // Dispatch. - - namespace internal - { - - template <typename I, typename N, typename L> - mln_ch_value(I, L) - level_dispatch(const Image<I>& input, const mln_value(I)& val, const Neighborhood<N>& nbh, - L& nlabels) - { - return impl::generic::level(input, val, nbh, nlabels); - } - - } // end of namespace mln::labeling::internal - // Facade. @@ -210,7 +153,8 @@ internal::level_tests(input, val, nbh, nlabels); mln_ch_value(I, L) output; - output = internal::level_dispatch(input, val, nbh, nlabels); + impl::level_functor<I> f(input, val); + output = canvas::labeling_video(input, nbh, nlabels, f); trace::exiting("labeling::level"); return output; Index: trunk/milena/mln/labeling/regional_minima.hh =================================================================== --- trunk/milena/mln/labeling/regional_minima.hh (revision 3318) +++ trunk/milena/mln/labeling/regional_minima.hh (revision 3319) @@ -35,7 +35,9 @@ # include <mln/core/concept/image.hh> # include <mln/core/concept/neighborhood.hh> -# include <mln/canvas/labeling.hh> + +# include "labeling.hh" + # include <mln/data/fill.hh> # include <mln/level/sort_psites.hh> @@ -68,21 +70,16 @@ // Generic functor. - template <typename I_, typename N_, typename L_> + template <typename I> struct regional_minima_functor { - typedef mln_psite(I_) P; + typedef mln_psite(I) P; // requirements from mln::canvas::labeling: - typedef I_ I; - typedef N_ N; - typedef L_ L; - typedef p_array<P> S; - const I& input; - const N& nbh; - S s; + + // Generic implementation void init() { data::fill(attr, true); } bool handles(const P&) const { return true; } @@ -103,43 +100,37 @@ void merge_attr(const P& r, const P& p) { attr(p) = attr(p) && attr(r); } - // end of requirements - - mln_ch_value(I, bool) attr; + // Fastest implementation - regional_minima_functor(const I_& input, const N_& nbh) - : input(input), - nbh(nbh), - s(level::sort_psites_increasing(input)) + void init_() { data::fill(attr, true); } + bool handles_(unsigned p) const { return true; } + bool labels_(unsigned p) const { return attr.element(p); } + bool equiv_(unsigned n, unsigned p) const { return input.element(n) == + input.element(p); } + void do_no_union_(unsigned n, unsigned p) { - initialize(attr, input); + // Avoid a warning about an undefined variable when NDEBUG + // is not defined. + (void)n; + + mln_invariant(input.element(n) < input.element(p)); + attr.element(p) = false; } - }; + void init_attr_(unsigned) {} + void merge_attr_(unsigned r, unsigned p) { attr.element(p) = attr.element(p) && + attr.element(r); } - // Generic implementation. + // end of requirements - namespace generic - { + mln_ch_value(I, bool) attr; - template <typename I, typename N, typename L> - mln_ch_value(I, L) - regional_minima(const I& input, const N& nbh, L& nlabels) + regional_minima_functor(const I& input) + : input(input) { - trace::entering("labeling::impl::generic::regional_minima"); - - // FIXME: abort if L is not wide enough to encode the set of - // minima. - - typedef impl::regional_minima_functor<I,N,L> F; - F f(exact(input), exact(nbh)); - mln_ch_value(I, L) output = canvas::labeling(input, nbh, f, nlabels); - - trace::exiting("labeling::impl::generic::regional_minima"); - return output; + initialize(attr, input); } - - } // end of namespace mln::labeling::impl::generic + }; } // end of namespace mln::labeling::impl @@ -159,8 +150,13 @@ const N& nbh = exact(nbh_); mln_precondition(input.is_valid()); - // Calls the only (generic) impl. - mln_ch_value(I, L) output = impl::generic::regional_minima(input, nbh, nlabels); + // FIXME: abort if L is not wide enough to encode the set of + // minima. + + typedef impl::regional_minima_functor<I> F; + F f(exact(input)); + mln_ch_value(I, L) output = canvas::labeling_sorted(input, nbh, nlabels, + f, true); trace::exiting("labeling::regional_minima"); return output; Index: trunk/milena/mln/labeling/regional_maxima.hh =================================================================== --- trunk/milena/mln/labeling/regional_maxima.hh (revision 3318) +++ trunk/milena/mln/labeling/regional_maxima.hh (revision 3319) @@ -35,7 +35,9 @@ # include <mln/core/concept/image.hh> # include <mln/core/concept/neighborhood.hh> -# include <mln/canvas/labeling.hh> + +# include "labeling.hh" + # include <mln/data/fill.hh> # include <mln/level/sort_psites.hh> @@ -69,21 +71,16 @@ // Generic functor. - template <typename I_, typename N_, typename L_> + template <typename I> struct regional_maxima_functor { - typedef mln_psite(I_) P; + typedef mln_psite(I) P; // requirements from mln::canvas::labeling: - typedef I_ I; - typedef N_ N; - typedef L_ L; - typedef p_array<P> S; - const I& input; - const N& nbh; - S s; + + // Generic implementation void init() { data::fill(attr, true); } bool handles(const P&) const { return true; } @@ -97,50 +94,37 @@ void merge_attr(const P& r, const P& p) { attr(p) = attr(p) && attr(r); } + // Fastest implementation + + void init_() { data::fill(attr, true); } + bool handles_(unsigned p) const { return true; } + bool labels_(unsigned p) const { return attr.element(p); } + bool equiv_(unsigned n, unsigned p) const { return input.element(n) == + input.element(p); } + void do_no_union_(unsigned n, unsigned p) { mln_invariant(input.element(n) > + input.element(p)); + attr.element(p) = false; } + void init_attr_(unsigned) {} + void merge_attr_(unsigned r, unsigned p) { attr.element(p) = attr.element(p) && + attr.element(r); } + // end of requirements mln_ch_value(I, bool) attr; - regional_maxima_functor(const I_& input, const N_& nbh) - : input(input), - nbh(nbh), - s(level::sort_psites_decreasing(input)) + regional_maxima_functor(const I& input) + : input(input) { initialize(attr, input); } }; - // Generic implementation. - - namespace generic - { - - template <typename I, typename N, typename L> - mln_ch_value(I, L) - regional_maxima(const I& input, const N& nbh, - L& nlabels) - { - trace::entering("labeling::impl::generic::regional_maxima"); - - // FIXME: abort if L is not wide enough to encode the set of - // maxima. - - typedef impl::regional_maxima_functor<I,N,L> F; - F f(exact(input), exact(nbh)); - mln_ch_value(I, L) output = canvas::labeling(input, nbh, f, nlabels); - - trace::exiting("labeling::impl::generic::regional_maxima"); - return output; - } - - } // end of namespace mln::labeling::impl::generic - - } // end of namespace mln::labeling::impl + // Facade. template <typename I, typename N, typename L> @@ -154,8 +138,10 @@ const N& nbh = exact(nbh_); mln_precondition(input.is_valid()); - // Calls the only (generic) impl. - mln_ch_value(I, L) output = impl::generic::regional_maxima(input, nbh, nlabels); + typedef impl::regional_maxima_functor<I> F; + F f(exact(input)); + mln_ch_value(I, L) output = canvas::labeling_sorted(input, nbh, nlabels, + f, false); trace::exiting("labeling::regional_maxima"); return output;