[Olena-patches] r3309: Implement fastest regional_minima

URL: https://svn.lrde.epita.fr/svn/oln/trunk/milena/sandbox ChangeLog: 2009-02-06 Fabien Freling &lt;freling(a)lrde.epita.fr&gt; Implement fastest regional_minima. * fabien/level.hh: New file to implement fastest level. * fabien/regional_maxima.hh: Fix. * fabien/regional_minima.cc: New file to test regional_minima. * fabien/regional_minima.hh: Fastest implementation. --- level.hh | 188 +++++++++++++++++++++++++++++++++++++++++++++++++++++ regional_minima.cc | 57 ++++++++++++++++ regional_minima.hh | 172 ++++++++++++++++++++++++++++++++++++++++++++++++ 3 files changed, 417 insertions(+) Index: trunk/milena/sandbox/fabien/level.hh =================================================================== --- trunk/milena/sandbox/fabien/level.hh (revision 0) +++ trunk/milena/sandbox/fabien/level.hh (revision 3309) @@ -0,0 +1,188 @@ +// 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_LABELING_LEVEL_HH +# define MLN_LABELING_LEVEL_HH + +/// \file mln/labeling/level.hh +/// +/// Connected component labeling of the image objects at a given +/// level. + +# include <mln/core/concept/image.hh> +# include <mln/core/concept/neighborhood.hh> +# include <mln/canvas/labeling.hh> +# include <mln/data/fill.hh> + + + +namespace mln +{ + + namespace labeling + { + + /*! Connected component labeling of the image objects at a given + * level. + * + * \param[in] input The input image. + * \param[in] val The level to consider for the labeling. + * \param[in] nbh The connexity of the level components. + * \param[out] nlabels The number of labels. + * \return The label image. + */ + 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); + + +# ifndef MLN_INCLUDE_ONLY + + + // Tests. + + namespace internal + { + + template <typename I, typename N, typename L> + void + level_tests(const Image<I>& input, const mln_value(I)& val, const Neighborhood<N>& nbh, + L& nlabels) + { + mln_precondition(exact(input).is_valid()); + // mln_precondition(exact(nbh).is_valid()); + + (void) input; + (void) val; + (void) nbh; + (void) nlabels; + } + + } // end of namespace mln::labeling::internal + + + + // 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 + { + typedef mln_psite(I) P; + + const I& input; + const mln_value(I)& val; + + // Requirements from mln::canvas::labeling. + + typedef mln_pset(I) 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; } + + // Fastest implementation + + void init_() {} + bool handles_(const P& p) const { return input.element(p) == val; } + bool equiv_(const P& n, const P&) const { return input.element(n) == val; } + bool labels_(const P&) const { return true; } + + + // end of Requirements. + + level_functor(const Image<I>& input_, const mln_value(I)& val) + : input(exact(input_)), + val(val) + { + } + }; + + + + + // Facade. + + 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::level"); + + internal::level_tests(input, val, nbh, nlabels); + + mln_ch_value(I, L) output; + level_functor<I> f(input, val); + output = canvas::labeling_video(input, nbh, nlabels, f); + + trace::exiting("labeling::level"); + return output; + } + +# endif // ! MLN_INCLUDE_ONLY + + } // end of namespace mln::labeling + +} // end of namespace mln + + +#endif // ! MLN_LABELING_LEVEL_HH Index: trunk/milena/sandbox/fabien/regional_minima.hh =================================================================== --- trunk/milena/sandbox/fabien/regional_minima.hh (revision 0) +++ trunk/milena/sandbox/fabien/regional_minima.hh (revision 3309) @@ -0,0 +1,172 @@ +// 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_LABELING_REGIONAL_MINIMA_HH +# define MLN_LABELING_REGIONAL_MINIMA_HH + +/// \file mln/labeling/regional_minima.hh +/// +/// Connected component labeling of the regional minima of an image. + +# include <mln/core/concept/image.hh> +# include <mln/core/concept/neighborhood.hh> + +# include "labeling.hh" + +# include <mln/data/fill.hh> +# include <mln/level/sort_psites.hh> + + +namespace mln +{ + + namespace labeling + { + + /*! Connected component labeling of the regional minima of an + * image. + * + * \param[in] input The input image. + * \param[in] nbh The connexity of the regional minima. + * \param[out] nlabels The number of labeled regions. + * \return The label image. + * + */ + template <typename I, typename N, typename L> + mln_ch_value(I, L) + regional_minima(const Image<I>& input, const Neighborhood<N>& nbh, + L& nlabels); + + +# ifndef MLN_INCLUDE_ONLY + + namespace impl + { + + // Generic functor. + + template <typename I> + struct regional_minima_functor + { + typedef mln_psite(I) P; + + // requirements from mln::canvas::labeling: + + const I& input; + + // Generic implementation + + void init() { data::fill(attr, true); } + bool handles(const P&) const { return true; } + bool labels(const P& p) const { return attr(p); } + bool equiv(const P& n, const P& p) const { return input(n) == + input(p); } + void do_no_union(const P& n, const P& p) + { + // Avoid a warning about an undefined variable when NDEBUG + // is not defined. + (void)n; + + mln_invariant(input(n) < input(p)); + attr(p) = false; + } + + void init_attr(const P&) {} + 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) + { + // 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); } + + // end of requirements + + mln_ch_value(I, bool) attr; + + regional_minima_functor(const I& input) + : input(input) + { + initialize(attr, input); + } + }; + + + } // end of namespace mln::labeling::impl + + + + // Facade. + + template <typename I, typename N, typename L> + mln_ch_value(I, L) + regional_minima(const Image<I>& input_, const Neighborhood<N>& nbh_, + L& nlabels) + { + trace::entering("labeling::regional_minima"); + + const I& input = exact(input_); + const N& nbh = exact(nbh_); + mln_precondition(input.is_valid()); + + // 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; + } + +# endif // ! MLN_INCLUDE_ONLY + + } // end of namespace mln::labeling + +} // end of namespace mln + + +#endif // ! MLN_LABELING_REGIONAL_MINIMA_HH Index: trunk/milena/sandbox/fabien/regional_maxima.hh =================================================================== Index: trunk/milena/sandbox/fabien/regional_minima.cc =================================================================== --- trunk/milena/sandbox/fabien/regional_minima.cc (revision 0) +++ trunk/milena/sandbox/fabien/regional_minima.cc (revision 3309) @@ -0,0 +1,57 @@ +// 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_minima.cc + * + * \brief Test on mln::labeling::regional_minima. + */ + +#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 <mln/pw/all.hh> + +#include "regional_minima.hh" + +#include <tests/data.hh> +#include <mln/debug/println.hh> + + +int main() +{ + using namespace mln; + using value::int_u8; + + trace::quiet = false; + + image2d<int_u8> lena = io::pgm::load<int_u8>(MLN_IMG_DIR "/tiny.pgm"); + + unsigned n; + labeling::regional_minima((pw::cst(255) - pw::value(lena)) | lena.domain(), + c4(), n); +}