[Olena-patches] r3291: Compile fastest versions of labeling

URL: https://svn.lrde.epita.fr/svn/oln/trunk/milena/sandbox ChangeLog: 2009-02-05 Fabien Freling &lt;freling(a)lrde.epita.fr&gt; Compile fastest versions of labeling. * fabien/labeling.hh: Compile fastest versions. * fabien/regional_maxima.cc: Simple test file. * fabien/regional_maxima.hh: Functor in fastest implementation. --- labeling.hh | 293 ++++++++++++++++++++++++++--------------------------- regional_maxima.cc | 53 +++++++++ regional_maxima.hh | 8 - 3 files changed, 204 insertions(+), 150 deletions(-) Index: trunk/milena/sandbox/fabien/regional_maxima.cc =================================================================== --- trunk/milena/sandbox/fabien/regional_maxima.cc (revision 0) +++ trunk/milena/sandbox/fabien/regional_maxima.cc (revision 3291) @@ -0,0 +1,53 @@ +// 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. + +/*! \file tests/labeling/regional_maxima.cc + * + * \brief Test on mln::labeling::regional_maxima. + */ + +#include <mln/core/image/image2d.hh> +#include <mln/value/int_u8.hh> +#include <mln/core/alias/neighb2d.hh> +#include <mln/io/pgm/load.hh> + +#include "regional_maxima.hh" + +#include <tests/data.hh> + + +int main() +{ + using namespace mln; + using value::int_u8; + + image2d<int_u8> lena = io::pgm::load<int_u8>(MLN_IMG_DIR "/tiny.pgm"); + + unsigned n; + labeling::regional_maxima(lena, c4(), n); + mln_assertion(n == 25); +} Index: trunk/milena/sandbox/fabien/regional_maxima.hh =================================================================== --- trunk/milena/sandbox/fabien/regional_maxima.hh (revision 3290) +++ trunk/milena/sandbox/fabien/regional_maxima.hh (revision 3291) @@ -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> @@ -102,7 +104,7 @@ void do_no_union_(unsigned n, unsigned p) { mln_invariant(input.element(n) > input.element(p)); attr.element(p) = false; } - void init_attr_(const P&) {} + void init_attr_(unsigned) {} void merge_attr_(unsigned r, unsigned p) { attr.element(p) = attr.element(p) && attr.element(r); } @@ -110,7 +112,7 @@ mln_ch_value(I, bool) attr; - regional_maxima_functor(const I_& input, const N_& nbh) + regional_maxima_functor(const I& input) : input(input) { initialize(attr, input); Index: trunk/milena/sandbox/fabien/labeling.hh =================================================================== --- trunk/milena/sandbox/fabien/labeling.hh (revision 3290) +++ trunk/milena/sandbox/fabien/labeling.hh (revision 3291) @@ -223,105 +223,104 @@ 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)); } -// // FIXME: Use the same functer for the generic and the fastest versions -// template <typename I, typename N, typename L, -// typename F> -// mln_ch_value(I, L) -// labeling_fastest_video(const Image<I>& input_, const Neighborhood<N>& nbh_, -// F& f, L& nlabels) -// { -// trace::entering("canvas::impl::labeling"); - -// // FIXME: Test?! - -// const I& input = exact(input_); -// const N& nbh = exact(nbh_); - -// // Local type. -// typedef mln_psite(I) P; - -// // Auxiliary data. -// mln_ch_value(I, bool) deja_vu; -// mln_ch_value(I, P) parent; - -// // Output. -// mln_ch_value(I, L) output; -// bool status; - -// // Initialization. -// { -// initialize(deja_vu, input); -// mln::data::fill(deja_vu, false); - -// initialize(parent, input); - -// initialize(output, input); -// mln::data::fill(output, L(literal::zero)); -// nlabels = 0; - -// f.init(); // Client initialization. -// } - -// // First Pass. -// { -// mln_pixter(const S) p(f.s); -// mln_nixter(const S, N) n(p, nbh); -// for_all(p) if (f.handles(p)) -// { -// // Make-Set. -// parent.element(p) = p; -// f.init_attr(p); - -// for_all(n) -// if (input.has(n) && deja_vu(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); -// (p) = true; -// } -// } -// } - -// // Second Pass. -// { -// mln_bkd_pixter(S) p(f.s); -// for_all(p) if (f.handles(p)) -// { -// 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(parent.element(p)); -// } -// status = true; -// } - -// trace::exiting("canvas::impl::labeling"); -// return output; -// } + 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_, + F& f, L& nlabels) + { + trace::entering("canvas::impl::labeling"); + + // FIXME: Test?! + + const I& input = exact(input_); + const N& nbh = exact(nbh_); + + // Local type. + typedef mln_psite(I) P; + + // Auxiliary data. + mln_ch_value(I, bool) deja_vu; + mln_ch_value(I, P) parent; + + // Output. + mln_ch_value(I, L) output; + bool status; + + // Initialization. + { + initialize(deja_vu, input); + mln::data::fill(deja_vu, false); + + 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) p(input); + mln_nixter(const I, N) n(p, nbh); + for_all(p) if (f.handles_(p)) + { + // Make-Set. + parent.element(p) = p; + f.init_attr(p); + + for_all(n) + if (input.has(n) && deja_vu(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); + (p) = true; + } + } + } + + // Second Pass. + { + mln_bkd_pixter(I) p(input); + for_all(p) if (f.handles_(p)) + { + 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(parent.element(p)); + } + status = true; + } + + trace::exiting("canvas::impl::labeling"); + return output; + } @@ -345,7 +344,7 @@ // Auxiliary data. mln_ch_value(I, bool) deja_vu; - mln_ch_value(I, P) parent; + mln_ch_value(I, unsigned) parent; // Output. mln_ch_value(I, L) output; @@ -362,13 +361,13 @@ mln::data::fill(output, L(literal::zero)); nlabels = 0; - f.init(); // Client initialization. + f.init_(); // Client initialization. } - util::array<int> dp = offsers_wrt(input, nbh); + util::array<int> dp = offsets_wrt(input, nbh); const unsigned n_nbhs = dp.nelements(); - const unsigned n_points = s.elements(); + const unsigned n_points = s.nelements(); // First Pass. { @@ -376,31 +375,31 @@ for (unsigned i = 0; i < n_points; ++i) { unsigned p = s[i]; - if (!f.handles(p)) + if (!f.handles_(p)) continue; // Make-Set. parent.element(p) = p; - f.init_attr(p); + f.init_attr_(p); for (unsigned j = 0; j < n_nbhs; ++j) { unsigned n = p + dp[j]; - if (!deja_vu[n]) + if (!deja_vu.element(n)) continue; - if (f.equiv(n, p)) + if (f.equiv_(n, p)) { // Do-Union. unsigned r = find_root_fastest(parent, n); if (input.element(r) != input.element(p)) { parent.element(r) = p; - f.merge_attr(r, p); + f.merge_attr_(r, p); } } else - f.do_no_union(n, p); + f.do_no_union_(n, p); } deja_vu.element(p) = true; @@ -412,12 +411,12 @@ for (int i = n_points - 1; i >=0; --i) { unsigned p = s[i]; - if (!f.handles(p)) + if (!f.handles_(p)) continue; if (parent.element(p) == p) // if p is root { - if (f.labels(p)) + if (f.labels_(p)) { if (nlabels == mln_max(L)) { @@ -428,7 +427,7 @@ } } else - output.element(p) = output(parent.element(p)); + output.element(p) = output.element(parent.element(p)); } status = true; } @@ -446,45 +445,45 @@ namespace internal { -// // Video + // Video -// template <typename I, typename N, typename L, -// typename F> -// inline -// mln_ch_value(I, L) -// labeling_video(metal::false_, const Image<I>& input, -// const Neighborhood<N>& nbh, L& nlabels, F& functor) -// { -// 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_fastest_video(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 impl::generic::labeling_video(metal::bool_<test>(), input, -// nbh, nlabels, functor); -// } + template <typename I, typename N, typename L, + typename F> + inline + mln_ch_value(I, L) + labeling_video(metal::false_, const Image<I>& input, + const Neighborhood<N>& nbh, L& nlabels, F& functor) + { + 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 impl::generic::labeling(metal::bool_<test>(), input, + nbh, nlabels, functor); + } // Sorted dispatch.