[Olena-patches] 3230: Make the fastest version for the algebraic morpho canvas work.

https://svn.lrde.epita.fr/svn/oln/trunk/milena Index: ChangeLog from Thierry Geraud &lt;thierry.geraud(a)lrde.epita.fr&gt; Make the fastest version for the algebraic morpho canvas work. * mln/level/sort_offsets.hh: New. * mln/level/all.hh: Update. * mln/morpho/closing_attribute.hh (closing_attribute_fastest_functor_t): Update. * mln/canvas/morpho/algebraic_union_find.hh (algebraic_union_find_fastest): Update. canvas/morpho/algebraic_union_find.hh | 71 +++---- level/all.hh | 1 level/sort_offsets.hh | 337 ++++++++++++++++++++++++++++++++++ morpho/closing_attribute.hh | 5 4 files changed, 377 insertions(+), 37 deletions(-) Index: mln/level/all.hh --- mln/level/all.hh (revision 3229) +++ mln/level/all.hh (working copy) @@ -66,6 +66,7 @@ # include <mln/level/replace.hh> # include <mln/level/saturate.hh> # include <mln/level/sort_psites.hh> +# include <mln/level/sort_offsets.hh> # include <mln/level/stretch.hh> # include <mln/level/to_enc.hh> # include <mln/level/transform.hh> Index: mln/level/sort_offsets.hh --- mln/level/sort_offsets.hh (revision 0) +++ mln/level/sort_offsets.hh (revision 0) @@ -0,0 +1,337 @@ +// 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 +// of the GNU General Public License version 2 as published by the +// Free Software Foundation. +// +// This library is distributed in the hope that it will be useful, +// but WITHOUT ANY WARRANTY; without even the implied warranty of +// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU +// General Public License for more details. +// +// You should have received a copy of the GNU General Public License +// along with this library; see the file COPYING. If not, write to +// the Free Software Foundation, 51 Franklin Street, Fifth Floor, +// Boston, MA 02111-1307, USA. +// +// As a special exception, you may use this file as part of a free +// software library without restriction. Specifically, if other files +// instantiate templates or use macros or inline functions from this +// file, or you compile this file and link it with other files to +// produce an executable, this file does not by itself cause the +// resulting executable to be covered by the GNU General Public +// License. This exception does not however invalidate any other +// reasons why the executable file might be covered by the GNU General +// Public License. + +#ifndef MLN_LEVEL_SORT_OFFSETS_HH +# define MLN_LEVEL_SORT_OFFSETS_HH + +/// \file mln/level/sort_offsets.hh +/// \brief Sort_Offsets the contents of an image into another one. +/// +/// \todo Factor code + optimize. + +# include <algorithm> + +# include <mln/core/concept/image.hh> +# include <mln/histo/compute.hh> +# include <mln/util/array.hh> +# include <mln/util/ord.hh> +# include <mln/geom/nsites.hh> + + +namespace mln +{ + + namespace level + { + + /// Sort pixel offsets of the image \p input wrt increasing pixel + /// values. + /// + template <typename I> + util::array<unsigned> + sort_offsets_increasing(const Image<I>& input); + + + // /// Sort pixel offsets of the image \p input wrt decreasing pixel + // /// values. + // /// + // template <typename I> + // util::array<unsigned> + // sort_offsets_decreasing(const Image<I>& input); + + + +# ifndef MLN_INCLUDE_ONLY + + namespace impl + { + + namespace generic + { + + // increasing + + template <typename I> + struct value_offset_less_ + { + const I& ima_; + inline value_offset_less_(const I& ima) : ima_(ima) {} + inline bool operator()(unsigned lhs, unsigned rhs) const + { + return util::ord_strict(ima_.element(lhs), ima_.element(rhs)) + || (ima_.element(lhs) == ima_.element(rhs) + && + lhs < rhs); + } + }; + + template <typename I> + inline + util::array<unsigned> + sort_offsets_increasing(const Image<I>& input_) + { + trace::entering("level::impl::generic::sort_offsets_increasing"); + + const I& input = exact(input_); + + util::array<unsigned> v; + v.reserve(input.nelements()); + mln_fwd_pixter(const I) pxl(input); + for_all(pxl) + v.append(pxl.offset()); + std::sort(v.hook_std_vector_().begin(), v.hook_std_vector_().end(), + value_offset_less_<I>(input)); + + trace::exiting("level::impl::generic::sort_offsets_increasing"); + return v; + } + + + // decreasing + + template <typename I> + struct value_offset_greater_ + { + const I& ima_; + inline value_offset_greater_(const I& ima) : ima_(ima) {} + inline bool operator()(unsigned lhs, unsigned rhs) const + { + return util::ord_strict(ima_.element(rhs), ima_.element(lhs)) + || (ima_.element(lhs) == ima_.element(rhs) + && + lhs > rhs); + } + }; + + template <typename I> + inline + util::array<unsigned> + sort_offsets_decreasing(const Image<I>& input_) + { + trace::entering("level::impl::generic::sort_offsets_decreasing"); + + const I& input = exact(input_); + + util::array<unsigned> v; + v.reserve(input.nelements()); + mln_fwd_pixter(const I) pxl(input); + for_all(pxl) + v.append(pxl.offset()); + std::sort(v.hook_std_vector_().begin(), v.hook_std_vector_().end(), + value_offset_greater_<I>(input)); + + trace::exiting("level::impl::generic::sort_offsets_decreasing"); + return v; + } + + + } // end of namespace mln::level::impl::generic + + + + // increasing + + template <typename I> + inline + util::array<unsigned> + sort_offsets_increasing_radix(const Image<I>& input_) + { + trace::entering("level::impl::sort_offsets_increasing_radix"); + + const I& input = exact(input_); + + typedef mln_vset(I) S; + const S& vset = input.values_eligible(); + const unsigned n = vset.nvalues(); + + // h + histo::array<mln_value(I)> h = histo::compute(input); + + // preparing output data + std::vector<unsigned> loc(vset.nvalues()); + loc[0] = 0; + for (unsigned i = 1; i != n; ++i) + loc[i] = loc[i-1] + h[i-1]; + + // computing output data + util::array<unsigned> vec(geom::nsites(input)); + mln_fwd_pixter(const I) pxl(input); + for_all(pxl) + vec[loc[vset.index_of(pxl.val())]++] = pxl.offset(); + + trace::exiting("level::impl::sort_offsets_increasing_radix"); + return vec; + } + + + // decreasing + + template <typename I> + inline + util::array<unsigned> + sort_offsets_decreasing_radix(const Image<I>& input_) + { + trace::entering("level::impl::sort_offsets_decreasing_radix"); + + const I& input = exact(input_); + + typedef mln_vset(I) S; + const S& vset = input.values_eligible(); + const unsigned n = vset.nvalues(); + + // h + histo::array<mln_value(I)> h = histo::compute(input); + + // preparing output data + std::vector<unsigned> loc(vset.nvalues()); + loc[n-1] = 0; + for (int i = n - 2; i >= 0; --i) + loc[i] = loc[i+1] + h[i+1]; + + // computing output data + util::array<unsigned> vec(geom::nsites(input)); + mln_fwd_pixter(const I) pxl(input); + for_all(pxl) + vec[loc[vset.index_of(pxl.val())]++] = pxl.offset(); + + trace::exiting("level::impl::sort_offsets_decreasing_radix"); + return vec; + } + + + } // end of namespace mln::level::impl + + + + namespace internal + { + + // increasing + + template <typename I> + inline + util::array<unsigned> + sort_offsets_increasing_dispatch(trait::image::quant::any, + const Image<I>& input) + { + return impl::generic::sort_offsets_increasing(input); + } + + template <typename I> + inline + util::array<unsigned> + sort_offsets_increasing_dispatch(trait::image::quant::low, + const Image<I>& input) + { + return impl::sort_offsets_increasing_radix(input); + } + + template <typename I> + inline + util::array<unsigned> + sort_offsets_increasing_dispatch(const Image<I>& input) + { + return sort_offsets_increasing_dispatch(mln_trait_image_quant(I)(), + input); + } + + // decreasing + + template <typename I> + inline + util::array<unsigned> + sort_offsets_decreasing_dispatch(trait::image::quant::any, + const Image<I>& input) + { + return impl::generic::sort_offsets_decreasing(input); + } + + template <typename I> + inline + util::array<unsigned> + sort_offsets_decreasing_dispatch(trait::image::quant::low, + const Image<I>& input) + { + return impl::sort_offsets_decreasing_radix(input); + } + + template <typename I> + inline + util::array<unsigned> + sort_offsets_decreasing_dispatch(const Image<I>& input) + { + return sort_offsets_decreasing_dispatch(mln_trait_image_quant(I)(), + input); + } + + } // end of namespace mln::level::internal + + + + // Facades. + + template <typename I> + inline + util::array<unsigned> + sort_offsets_increasing(const Image<I>& input) + { + trace::entering("level::sort_offsets_increasing"); + mlc_is(mln_trait_image_speed(I), + trait::image::speed::fastest)::check(); + + mln_precondition(exact(input).is_valid()); + util::array<unsigned> output = internal::sort_offsets_increasing_dispatch(input); + + trace::exiting("level::sort_offsets_increasing"); + return output; + } + + template <typename I> + inline + util::array<unsigned> + sort_offsets_decreasing(const Image<I>& input) + { + trace::entering("level::sort_offsets_decreasing"); + mlc_is(mln_trait_image_speed(I), + trait::image::speed::fastest)::check(); + + mln_precondition(exact(input).is_valid()); + util::array<unsigned> output = internal::sort_offsets_decreasing_dispatch(input); + + trace::exiting("level::sort_offsets_decreasing"); + return output; + } + +# endif // ! MLN_INCLUDE_ONLY + + } // end of namespace mln::level + +} // end of namespace mln + + +#endif // ! MLN_LEVEL_SORT_OFFSETS_HH Index: mln/morpho/closing_attribute.hh --- mln/morpho/closing_attribute.hh (revision 3229) +++ mln/morpho/closing_attribute.hh (working copy) @@ -40,6 +40,7 @@ # include <mln/morpho/includes.hh> # include <mln/canvas/morpho/algebraic_union_find.hh> # include <mln/level/sort_psites.hh> +# include <mln/level/sort_offsets.hh> # include <mln/util/pix.hh> @@ -144,7 +145,7 @@ typedef A_ A; typedef mln_psite(I) P; - typedef p_array<P> S; + typedef util::array<unsigned> S; mln_result(A) lambda; const S s; @@ -168,7 +169,7 @@ closing_attribute_fastest_functor_t(const Image<I>& input, mln_result(A) lambda) : lambda(lambda), - s(level::sort_psites_increasing(exact(input))) + s(level::sort_offsets_increasing(exact(input))) { } Index: mln/canvas/morpho/algebraic_union_find.hh --- mln/canvas/morpho/algebraic_union_find.hh (revision 3229) +++ mln/canvas/morpho/algebraic_union_find.hh (working copy) @@ -214,7 +214,7 @@ if (parent.element(x) == x) return x; else - return parent.element(x) = find_root(parent, parent.element(x)); + return parent.element(x) = find_root_fastest(parent, parent.element(x)); } @@ -260,63 +260,64 @@ } util::array<int> dp = offsets_wrt(input, nbh); - for (unsigned i = 0; i < dp.nelements(); ++i) - std::cout << dp[i] << ' '; - std::cout << std::endl; + const unsigned n_nbhs = dp.nelements(); - /* + const util::array<unsigned>& s = f.s; + const unsigned n_points = s.nelements(); // First pass. { - for (unsigned p = 0; p < f.s.size(); ++p) - mln_niter(N) n(nbh, p); - for_all(p) + + for (unsigned i = 0; i < n_points; ++i) { + unsigned p = s[i]; // An offset. + // Make set. - { - parent(p) = p; - data(p).take_as_init(make::pix(input, p)); // FIXME: algebraic so p! - } + parent.element(p) = p; + data.element(p).take_as_init( input.element(p) ); // FIXME: Very bad!!! - for_all(n) - if (input.domain().has(n) && deja_vu(n)) + for (unsigned j = 0; j < n_nbhs; ++j) { - P r = find_root(parent, n); + unsigned n = p + dp[j]; + if (! deja_vu.element(n)) + continue; + + unsigned r = find_root_fastest(parent, n); if (r != p) { - if (input(r) == input(p) || (activity(r) && f.is_active(data(r)))) - { - data(p).take(data(r)); - parent(r) = p; - if (activity(r) == false) - activity(p) = false; + if (input.element(r) == input.element(p) + || (activity.element(r) + && f.is_active(data.element(r)))) + { + data.element(p).take(data.element(r)); + parent.element(r) = p; + if (activity.element(r) == false) + activity.element(p) = false; } else { - activity(p) = false; - f.inactivate(data(p)); - } + activity.element(p) = false; + f.inactivate(data.element(p)); } } - deja_vu(p) = true; - } } - */ + deja_vu.element(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); + for (int i = n_points - 1; i >= 0 ; --i) + { + unsigned p = s[i]; + if (parent.element(p) == p) // p is root. + output.element(p) = input.element(p); else - output(p) = output(parent(p)); + output.element(p) = output.element(parent.element(p)); + } } - - */ trace::exiting("canvas::morpho::impl::algebraic_union_find_fastest"); return output;