[Olena-patches] 1694: Add a computation of the extrema level components.

https://svn.lrde.epita.fr/svn/oln/trunk/milena (Same remark as my previous patch.) Index: ChangeLog from Roland Levillain &lt;roland(a)lrde.epita.fr&gt; Add a computation of the extrema level components. * mln/morpho/extrema_components.hh: New. Imported from Olena proto-1.0. * tests/morpho/extrema_components.cc: New test. * tests/morpho/Makefile.am (check_PROGRAMS): Add extrema_components. (extrema_components_SOURCES): New. * img/squares.pgm, img/squares-lc.pgm: New images. mln/morpho/extrema_components.hh | 229 ++++++++++++++++++++++++++++--------- tests/morpho/Makefile.am | 2 tests/morpho/extrema_components.cc | 69 +++++++++++ 3 files changed, 247 insertions(+), 53 deletions(-) Index: mln/morpho/extrema_components.hh --- mln/morpho/extrema_components.hh (revision 1680) +++ mln/morpho/extrema_components.hh (working copy) @@ -1,4 +1,4 @@ -// Copyright (C) 2005 EPITA Research and Development Laboratory +// Copyright (C) 2005, 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 @@ -25,51 +25,152 @@ // reasons why the executable file might be covered by the GNU General // Public License. -#ifndef OLENA_MORPHO_EXTREMA_COMPONENTS_HH -# define OLENA_MORPHO_EXTREMA_COMPONENTS_HH +#ifndef MLN_MORPHO_EXTREMA_COMPONENTS_HH +# define MLN_MORPHO_EXTREMA_COMPONENTS_HH + +// FIXME: This file seems to contain the same algorithm as +// mln/labeling/regional_minima.hh and +// mln/labeling/regional_maxima.hh. Merge or remove to avoid +// duplication. + +// FIXME: Provide neighborhood-aware versions of these algorithms. # include <map> # include <queue> # include <functional> -# include "oln/level/level_components.hh" +# include <mln/trait/ch_value.hh> + +# include <mln/level/fill.hh> + +# include <mln/morpho/includes.hh> +# include <mln/morpho/level_components.hh> + + +namespace mln { + + namespace morpho { + + /*--------------------------. + | Minima level components. | + `--------------------------*/ + + /** \brief Compute the minima level components of \a input. + + \p DestValue is the value type of the output. + + The result is an image where each minima is given a value + between \c mln_value(DestValue) + 1 and \c nminima (the number + of minima level components). Points which do not belong to a + minimum are gien the value mln_value(DestValue). + + \param[in] input The image whose minima are computed. + \param[in] win The window describing the connexity of \a input. + \param[out] nminima The number of minima found by the algorithm. + \return The image of minima. + + \pre \p DestValue is large enough to hold a number of values + equal to \c nminima + 1, so as to tag all the minima points + plus the non-minima points. */ + template <typename DestValue, typename I, typename W> + mln_ch_value(I, DestValue) + minima_components(const Image<I>& input, const Window<W>& win, + unsigned& nminima); + + /// \brief Like the 3-argument version of mln::moprho::minima_components, + /// without the out argument \c nminima. + template <typename DestValue, typename I, typename W> + mln_ch_value(I, DestValue) + minima_components(const Image<I>& input, const Window<W>& win); + + + /*--------------------------. + | Maxima level components. | + `--------------------------*/ + + /** \brief Compute the maxima level components of \a input. + + \p DestValue is the value type of the output. + + The result is an image where each maxima is given a value + between \c mln_value(DestValue) + 1 and \c nmaxima (the number + of maxima level components). Points which do not belong to a + maximum are gien the value mln_value(DestValue). + + \param[in] input The image whose maxima are computed. + \param[in] win The window describing the connexity of \a input. + \param[out] nmaxima The number of maxima found by the algorithm. + \return The image of maxima. -namespace oln { + \pre \p DestValue is large enough to hold a number of values + equal to \c nmaxima + 1, so as to tag all the maxima points + plus the non-maxima points. */ + template <typename DestValue, typename I, typename W> + mln_ch_value(I, DestValue) + maxima_components(const Image<I>& input, const Window<W>& win, + unsigned& nmaxima); - namespace level { + /// \brief Like the 3-argument version of mln::moprho::maxima_components, + /// without the out argument \c nmaxima. + template <typename DestValue, typename I, typename W> + mln_ch_value(I, DestValue) + maxima_components(const Image<I>& input, const Window<W>& win); - namespace internal { + +# ifndef MLN_INCLUDE_ONLY + + namespace impl { /// Find the extrema level components of \a input, using \param /// Cmp as comparison function. - template <typename DestValue, typename Cmp, typename I> - typename ch_value_type<I, DestValue>::ret - extrema_components(const abstract::image_with_nbh<I>& input) + template <typename DestValue, typename Cmp, typename I, typename W> + mln_ch_value(I, DestValue) + extrema_components(const Image<I>& input_, const Window<W>& win_, + unsigned& nextrema) { - mlc_is_a(I, abstract::scalar_valued_image)::ensure(); + + /* FIXME: Errors due to a too small DestValue type should be + reported more explicitely. Currently, we abort with messages + akin to this one: + + Assertion failed: + (unsigned(i) <= mln::trait::value_< enc_ >::max()), + function operator=, file ../../../../milena/mln/value/int_u.hh, + line 243. + + This is not user-friendly at all! */ + + const I& input = exact(input_); + const W& win = exact(win_); + + // Instantiate a comparison functor. Cmp cmp; // Compute level components. - typedef ntg_cumul_type(DestValue) cumul_type; + /* FIXME: Should we deduce cumul_type from DestValue? Or + stick to unsigned? */ + typedef unsigned cumul_type; typedef cumul_type comp_type; - typename ch_value_type<I, comp_type>::ret comps = - level_components<comp_type>(input); + mln_ch_value(I, comp_type) comps = + level_components<comp_type>(input, win); + /* FIXME: Does Milena provide better data structures to + store this information? */ std::set<comp_type> extrema; std::set<comp_type> non_extrema; // Search extrema components. - oln_type_of(I, piter) p(input.size()); - for_all_p (p) + mln_piter(I) p(input.domain()); + for_all(p) { - comp_type comp = comps[p]; + comp_type comp = comps(p); if (non_extrema.find(comp) == non_extrema.end()) { // A new level is a (potential) extrema by default. extrema.insert(comp); - oln_type_of(I, niter) n(input); - for_all_n_of_p (n, p) - if (input.hold(n) and cmp(input[n], input[p])) + mln_qiter(W) q(win, p); + for_all(q) + if (input.has(q) and cmp(input(q), input(p))) { extrema.erase(comp); non_extrema.insert(comp); @@ -78,57 +179,79 @@ } } + // Update nextrema. + nextrema = extrema.size(); + // Re-label the extrema. label_map hold the assigned labels. std::map<comp_type, DestValue> label_map; { - DestValue cur_label = ntg_min_val(DestValue) + 1; - for (typename std::set<comp_type>::const_iterator i = - extrema.begin(); i != extrema.end(); ++i, ++cur_label) - { + DestValue cur_label = mln_min(DestValue) + 1; + for (typename std::set<comp_type>::const_iterator i = extrema.begin(); + i != extrema.end(); + ++i, ++cur_label) label_map[*i] = cur_label; } - } - typename ch_value_type<I, DestValue>::ret output (input.size(), - input.nbh_get()); - level::fill (output, ntg_min_val(DestValue)); - for_all_p (p) + mln_ch_value(I, DestValue) output (input.domain()); + level::fill (output, mln_min(DestValue)); + for_all(p) { - comp_type comp = comps[p]; + comp_type comp = comps(p); if (label_map.find(comp) != label_map.end()) - output[p] = label_map[comp]; + output(p) = label_map[comp]; } return output; } - } // end of namespace oln::level::internal. + } // end of namespace mln::morpho::impl. - /// Find the minima level components of \a input. - template <typename DestValue, typename I> - typename ch_value_type<I, DestValue>::ret - minima_components(const abstract::image_with_nbh<I>& input) + /*----------. + | Facades. | + `----------*/ + + template <typename DestValue, typename I, typename W> + mln_ch_value(I, DestValue) + minima_components(const Image<I>& input, const Window<W>& win, + unsigned& nminima) { - mlc_is_a(I, abstract::scalar_valued_image)::ensure(); - typedef oln_type_of(I, value) input_value_type; - return - internal::extrema_components< DestValue, - std::less<input_value_type> >(input); + /* FIXME: Ensure the input image has scalar values. */ + typedef std::less< mln_value(I) > cmp_t; + return impl::extrema_components<DestValue, cmp_t>(input, win, nminima); } - /// Find the maxima level components of \a input. - template <typename DestValue, typename I> - typename ch_value_type<I, DestValue>::ret - maxima_components(const abstract::image_with_nbh<I>& input) + template <typename DestValue, typename I, typename W> + mln_ch_value(I, DestValue) + minima_components(const Image<I>& input, const Window<W>& win) + { + // Dummy value. + unsigned nminima; + return minima_components<DestValue>(input, win, nminima); + } + + + template <typename DestValue, typename I, typename W> + mln_ch_value(I, DestValue) + maxima_components(const Image<I>& input, const Window<W>& win, + unsigned& nmaxima) { - mlc_is_a(I, abstract::scalar_valued_image)::ensure(); - typedef oln_type_of(I, value) input_value_type; - return - internal::extrema_components< DestValue, - std::greater<input_value_type> >(input); + /* FIXME: Ensure the input image has scalar values. */ + typedef std::greater< mln_value(I) > cmp_t; + return impl::extrema_components<DestValue, cmp_t>(input, win, nmaxima); } - } // end of namespace oln::level. + template <typename DestValue, typename I, typename W> + mln_ch_value(I, DestValue) + maxima_components(const Image<I>& input, const Window<W>& win) + { + // Dummy value. + unsigned nmaxima; + return maxima_components<DestValue>(input, win, nmaxima); + } + +# endif // ! MLN_INCLUDE_ONLY + + } // end of namespace mln::morpho. -} // end of namespace oln. +} // end of namespace mln. -#endif // ! OLENA_MORPHO_EXTREMA_COMPONENTS_HH +#endif // ! MLN_MORPHO_EXTREMA_COMPONENTS_HH Index: tests/morpho/extrema_components.cc --- tests/morpho/extrema_components.cc (revision 0) +++ tests/morpho/extrema_components.cc (revision 0) @@ -0,0 +1,69 @@ +// Copyright (C) 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/morpho/extrema_components.cc +// /\brief Test on mln::morpho::extrema_components + +#include <iostream> + +#include <mln/core/image2d.hh> +#include <mln/core/window2d.hh> +#include <mln/core/neighb2d.hh> + +#include <mln/convert/to_window.hh> + +#include <mln/value/int_u8.hh> + +#include <mln/morpho/extrema_components.hh> + +#include <mln/io/pgm/load.hh> +#include <mln/io/pgm/save.hh> + +#include "tests/data.hh" + + +int main() +{ + using namespace mln; + using value::int_u8; + + image2d<int_u8> input; + io::pgm::load(input, MLN_IMG_DIR "/squares.pgm"); + + unsigned nminima; + // FIXME: Do we really need to use a neighborood to express a 4-c window? + image2d<int_u8> minima = + morpho::minima_components<int_u8>(input, convert::to_window(c4()), nminima); + std::cout << "nminima = " << nminima << std::endl; + io::pgm::save(minima, "minima.pgm"); + + unsigned nmaxima; + image2d<int_u8> maxima = + morpho::maxima_components<int_u8>(input, convert::to_window(c4()), nmaxima); + std::cout << "nmaxima = " << nmaxima << std::endl; + io::pgm::save(maxima, "maxima.pgm"); +} Index: tests/morpho/Makefile.am --- tests/morpho/Makefile.am (revision 1693) +++ tests/morpho/Makefile.am (working copy) @@ -8,6 +8,7 @@ dilation_max_h \ erosion \ erosion_min_h \ + extrema_components \ gradient \ hit_or_miss \ laplacian \ @@ -20,6 +21,7 @@ dilation_max_h_SOURCES = dilation_max_h.cc erosion_SOURCES = erosion.cc erosion_min_h_SOURCES = erosion_min_h.cc +extrema_components_SOURCES = extrema_components.cc gradient_SOURCES = gradient.cc hit_or_miss_SOURCES = hit_or_miss.cc laplacian_SOURCES = laplacian.cc