[Olena-patches] 196: Add (queue-based) level and extrema components computation

Ce code est sans doute redondant avec ce qu'offriront les canevas sur l'Union-Find, mais : 1. je vais en avoir besoin pour écrire des variantes du watershed ; 2. je ne voulais pas marcher sur les plates-bandes de Christophe et Nicolas ; d'où l'idée d'écrire les calculs des extrema locaux avec une variante à base de FIFO. (C'est très certainement (très) sub-optimal.) https://svn.lrde.epita.fr/svn/oln/prototypes/proto-1.0 ChangeLog | 13 +++ oln/level/extrema_components.hh | 124 +++++++++++++++++++++++++++++++++++ oln/level/level_components.hh | 83 +++++++++++++++++++++++ oln/morpho/lower_completion.hh | 5 - tests/level/tests/extrema_components | 42 +++++++++++ tests/morpho/tests/lower_completion | 1 6 files changed, 265 insertions(+), 3 deletions(-) Index: olena/ChangeLog from Roland Levillain &lt;roland(a)lrde.epita.fr&gt; Add (queue-based) level and extrema components computation. * oln/level/level_components.hh, oln/level/extrema_components.hh: New files. * tests/level/tests/extrema_components: New test. * oln/morpho/lower_completion.hh: Check that the input is a scalar image. * tests/morpho/tests/lower_completion: Don't include useless headers. Index: olena/tests/morpho/tests/lower_completion --- olena/tests/morpho/tests/lower_completion (revision 195) +++ olena/tests/morpho/tests/lower_completion (working copy) @@ -4,7 +4,6 @@ #include "oln/core/2d/image2d.hh" #include "oln/core/gen/image_with_nbh.hh" #include "oln/io/read_image.hh" -#include "oln/io/write_image.hh" #include "oln/morpho/lower_completion.hh" #include "oln/ops/cmp.hh" Index: olena/tests/level/tests/extrema_components --- olena/tests/level/tests/extrema_components (revision 0) +++ olena/tests/level/tests/extrema_components (revision 0) @@ -0,0 +1,42 @@ + // -*- C++ -*- +#include "data.hh" +#include "ntg/int.hh" +#include "oln/core/2d/image2d.hh" +#include "oln/core/gen/image_with_nbh.hh" +#include "oln/io/read_image.hh" +#include "oln/io/write_image.hh" +#include "oln/level/extrema_components.hh" +#include "oln/ops/cmp.hh" +#include "oln/utils/md5.hh" + +using namespace oln; + +bool check() +{ + image2d<ntg::int_u8> raw_input; + raw_input = io::read(rdata("16x16.pgm")); + typedef image_with_nbh<image2d<ntg::int_u8>, neighborhood2d> image_type; + image_type input = join(raw_input, neighb_c4()); + + // MD5 sum of the minima. + utils::key::value_type minima_data_key[16] = + { 0x72, 0xad, 0x21, 0xcc, 0xd9, 0x6a, 0x6a, 0x82, + 0xb8, 0xea, 0x60, 0x1f, 0xcf, 0x76, 0x45, 0x13 }; + utils::key minima_key(minima_data_key); + + image_type minima = level::minima_components<ntg::int_u8>(input); + if (utils::md5(minima) != minima_key) + return true; + + // MD5 sum of the maxima. + utils::key::value_type maxima_data_key[16] = + { 0x6e, 0x71, 0x74, 0x7c, 0xf8, 0xb, 0xfe, 0xa, + 0xa9, 0xd2, 0x84, 0x26, 0xa5, 0x3e, 0xfd, 0xba }; + utils::key maxima_key(maxima_data_key); + + image_type maxima = level::maxima_components<ntg::int_u8>(input); + if (utils::md5(maxima) != maxima_key) + return true; + + return false; +} Index: olena/oln/morpho/lower_completion.hh --- olena/oln/morpho/lower_completion.hh (revision 195) +++ olena/oln/morpho/lower_completion.hh (working copy) @@ -36,11 +36,12 @@ namespace morpho { - // FIXME: INPUT should be a scalar image. template <typename DestValue, typename I> typename ch_value_type<I, DestValue>::ret lower_completion(const abstract::image_with_nbh<I>& input) { + mlc_is_a(I, abstract::scalar_valued_image)::ensure(); + typedef oln_type_of(I, point) point_type; /*------------------------------------------. @@ -55,7 +56,7 @@ typename ch_value_type<I, unsigned>::ret distance(input.size()); unsigned cur_dist = 1; - oln_type_of(I, fwd_piter) p(input.size()); + oln_type_of(I, piter) p(input.size()); for_all_p (p) { distance[p] = 0; Index: olena/oln/level/extrema_components.hh --- olena/oln/level/extrema_components.hh (revision 0) +++ olena/oln/level/extrema_components.hh (revision 0) @@ -0,0 +1,124 @@ +// Copyright (C) 2005 EPITA Research and Development Laboratory +// +// 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, 59 Temple Place - Suite 330, 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 OLENA_MORPHO_EXTREMA_COMPONENTS_HH +# define OLENA_MORPHO_EXTREMA_COMPONENTS_HH + +# include <map> +# include <queue> +# include <functional> + +# include "oln/level/level_components.hh" + +namespace oln { + + namespace level { + + namespace internal { + + /// 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) + { + mlc_is_a(I, abstract::scalar_valued_image)::ensure(); + Cmp cmp; + + // Compute level components. + typename ch_value_type<I, DestValue>::ret comps = + level_components<DestValue>(input); + std::set<DestValue> extrema; + std::set<DestValue> non_extrema; + + // Search extrema components. + oln_type_of(I, piter) p(input.size()); + for_all_p (p) + { + DestValue 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) && cmp(input[n], input[p])) + { + extrema.erase(comp); + non_extrema.insert(comp); + } + } + } + + // Re-label the extrema. label_map hold the assigned labels. + std::map<DestValue, DestValue> label_map; + { + DestValue cur_label = ntg_min_val(DestValue) + 1; + for (typename std::set<DestValue>::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()); + level::fill (output, ntg_min_val(DestValue)); + for_all_p (p) + { + DestValue comp = comps[p]; + if (label_map.find(comp) != label_map.end()) + output[p] = label_map[comp]; + } + return output; + } + + } // end of namespace oln::level::internal. + + + /// 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) + { + mlc_is_a(I, abstract::scalar_valued_image)::ensure(); + return internal::extrema_components< DestValue, + std::less<DestValue> >(input); + } + + /// 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) + { + mlc_is_a(I, abstract::scalar_valued_image)::ensure(); + return internal::extrema_components< DestValue, + std::greater<DestValue> >(input); + } + + } // end of namespace oln::level. + +} // end of namespace oln. + +#endif // ! OLENA_MORPHO_EXTREMA_COMPONENTS_HH Index: olena/oln/level/level_components.hh --- olena/oln/level/level_components.hh (revision 0) +++ olena/oln/level/level_components.hh (revision 0) @@ -0,0 +1,83 @@ +// Copyright (C) 2005 EPITA Research and Development Laboratory +// +// 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, 59 Temple Place - Suite 330, 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 OLENA_MORPHO_LEVEL_COMPONENTS_HH +# define OLENA_MORPHO_LEVEL_COMPONENTS_HH + +# include <queue> + +# include "oln/level/fill.hh" + +namespace oln { + + namespace level { + + /// Compute the level components of \a input. + template <typename DestValue, typename I> + typename ch_value_type<I, DestValue>::ret + level_components(const abstract::image_with_nbh<I>& input) + { + mlc_is_a(I, abstract::scalar_valued_image)::ensure(); + + typename ch_value_type<I, DestValue>::ret labels(input.size()); + typename ch_value_type<I, bool>::ret processed(input.size()); + level::fill (processed, false); + + DestValue cur_label = ntg_min_val(DestValue); + + typedef oln_type_of(I, point) point_type; + std::queue<point_type> q; + + oln_type_of(I, piter) p(input.size()); + for_all_p (p) + if (!processed[p]) + { + labels[p] = cur_label; + q.push(p); + while (!q.empty()) + { + point_type s = q.front(); + q.pop(); + oln_type_of(I, niter) n(input); + for_all_n_of_p (n, s) + if (input.hold(n) && input[n] == input[s] && !processed[n]) + { + labels[n] = cur_label; + processed[n] = true; + q.push(n); + } + } + ++cur_label; + } + return labels; + } + + } // end of namespace oln::level + +} // end of namespace oln + +#endif // ! OLENA_MORPHO_LEVEL_COMPONENTS_HH