[Olena-patches] 3790: Add morpho reconstruction by_dilation union_find algorithm.

https://svn.lrde.epita.fr/svn/oln/trunk/milena Index: ChangeLog from Thierry Geraud &lt;thierry.geraud(a)lrde.epita.fr&gt; Add morpho reconstruction by_dilation union_find algorithm. * mln/morpho/reconstruction, * mln/morpho/reconstruction/by_dilation, * tests/morpho/reconstruction, * tests/morpho/reconstruction/by_dilation: New directories. * sandbox/theo/Rd/union_find.hh: Copy to... * mln/morpho/reconstruction/by_dilation/union_find.hh: ...this new file. Update. * mln/morpho/all.hh: Fix comments. * mln/morpho/reconstruction/all.hh: New. * mln/morpho/reconstruction/by_dilation/all.hh: New. * tests/morpho/reconstruction/Makefile.am: New. * tests/morpho/reconstruction/by_dilation/Makefile.am: New. * tests/morpho/reconstruction/by_dilation/union_find.cc: New. * tests/morpho/Makefile.am: Update. mln/morpho/all.hh | 9 mln/morpho/reconstruction/all.hh | 57 +++ mln/morpho/reconstruction/by_dilation/all.hh | 59 +++ mln/morpho/reconstruction/by_dilation/union_find.hh | 272 ++++++++++++------ tests/morpho/Makefile.am | 1 tests/morpho/reconstruction/Makefile.am | 11 tests/morpho/reconstruction/by_dilation/Makefile.am | 15 tests/morpho/reconstruction/by_dilation/union_find.cc | 64 ++++ 8 files changed, 408 insertions(+), 80 deletions(-) Index: mln/morpho/all.hh --- mln/morpho/all.hh (revision 3789) +++ mln/morpho/all.hh (working copy) @@ -31,22 +31,22 @@ /// \file mln/morpho/all.hh /// -/// File that includes all morpho-related routines. +/// File that includes all mathematical morphology routines. namespace mln { - /// Namespace of morphological image processing routines. + /// Namespace of mathematical morphology routines. namespace morpho { - /// Namespace of morphological image processing routines + /// Namespace of mathematical morphology routines /// implementations. namespace impl { - /// Namespace of morphological image processing routines + /// Namespace of mathematical morphology routines /// generic implementations. namespace generic {} @@ -85,6 +85,7 @@ # include <mln/morpho/closing/all.hh> # include <mln/morpho/elementary/all.hh> # include <mln/morpho/opening/all.hh> +# include <mln/morpho/reconstruction/all.hh> # include <mln/morpho/tree/all.hh> # include <mln/morpho/watershed/all.hh> Index: mln/morpho/reconstruction/all.hh --- mln/morpho/reconstruction/all.hh (revision 0) +++ mln/morpho/reconstruction/all.hh (revision 0) @@ -0,0 +1,57 @@ +// Copyright (C) 2009 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_MORPHO_RECONSTRUCTION_ALL_HH +# define MLN_MORPHO_RECONSTRUCTION_ALL_HH + + +/// \file mln/morpho/reconstruction/all.hh +/// +/// File that includes all morphological reconstruction routines. + + +namespace mln +{ + + namespace morpho + { + + /// Namespace of morphological reconstruction routines. + namespace reconstruction + {} + + } +} + + +// Sub-directories. + +# include <mln/morpho/reconstruction/by_dilation/all.hh> +// ... + + +#endif // ! MLN_MORPHO_RECONSTRUCTION_ALL_HH Index: mln/morpho/reconstruction/by_dilation/union_find.hh --- mln/morpho/reconstruction/by_dilation/union_find.hh (revision 0) +++ mln/morpho/reconstruction/by_dilation/union_find.hh (working copy) @@ -1,4 +1,5 @@ -// Copyright (C) 2007, 2008 EPITA Research and Development Laboratory +// Copyright (C) 2007, 2008, 2009 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 @@ -25,10 +26,14 @@ // reasons why the executable file might be covered by the GNU General // Public License. -#ifndef MLN_MORPHO_RD_UNION_FIND_HH -# define MLN_MORPHO_RD_UNION_FIND_HH +#ifndef MLN_MORPHO_RECONSTRUCTION_BY_DILATION_UNION_FIND_HH +# define MLN_MORPHO_RECONSTRUCTION_BY_DILATION_UNION_FIND_HH -# include "utils.hh" +# include <vector> +# include <mln/core/concept/image.hh> +# include <mln/core/concept/neighborhood.hh> +# include <mln/level/compare.hh> +# include <mln/level/sort_psites.hh> namespace mln @@ -37,130 +42,245 @@ namespace morpho { - namespace Rd + namespace reconstruction { + namespace by_dilation + { + + + template <typename I, typename J, typename N> + mln_concrete(I) + union_find(const Image<I>& f, const Image<J>& g, + const Neighborhood<N>& nbh); + + +# ifndef MLN_INCLUDE_ONLY - template <typename I, typename N> - struct union_find_t + + // Tests. + + namespace internal { - typedef mln_site(I) point; - typedef mln_value(I) value; - // in: - const I f, g; - N nbh; + template <typename I, typename J, typename N> + inline + void + union_find_tests(const Image<I>& f_, const Image<J>& g_, + const Neighborhood<N>& nbh_) + { + const I& f = exact(f_); + const J& g = exact(g_); + const N& nbh = exact(nbh_); + + mln_precondition(f.is_valid()); + mln_precondition(g.is_valid()); + mln_precondition(nbh.is_valid()); + + mln_precondition(f.domain() == g.domain()); // FIXME: Relax? + mln_precondition(f <= g); + + // mlc_equal(mln_value(I), mln_value(J))::check(); // FIXME: Too strong! + // FIXME: Also check that we have a total ordering for values. + + (void) f; + (void) g; + (void) nbh; + } + - // out: - I o; - // aux: - std::vector<point> S; +// template <typename P> +// inline +// bool is_proc(const P& n, const P& p) const +// { +// return g(n) > g(p) or (g(n) == g(p) && +// util::ord_strict(n, p)); +// } + + template <typename Par> + inline + mln_site(Par) find_root(Par& parent, mln_site(Par) x) + { + if (parent(x) == x) + return x; + else + return parent(x) = find_root(parent, parent(x)); + } + + + } // end of namespace mln::morpho::reconstruction::by_dilation::internal + + + // Implementations. + + namespace impl + { + + namespace generic + { + + template <typename I, typename J, typename N> + inline + mln_concrete(I) + union_find(const Image<I>& f_, const Image<J>& g_, + const Neighborhood<N>& nbh_) + { + trace::entering("morpho::reconstruction::by_dilation::impl::generic::union_find"); + + const I& f = exact(f_); + const J& g = exact(g_); + const N& nbh = exact(nbh_); + + internal::union_find_tests(f, g, nbh); + + + typedef mln_site(I) P; + typedef mln_value(I) V; + + // Auxiliary data. + p_array<P> s; mln_ch_value(I, bool) deja_vu; - mln_ch_value(I, point) parent; + mln_ch_value(I, P) parent; + mln_concrete(I) output; - union_find_t(const I& f, const I& g, const N& nbh) - : f(f), g(g), nbh(nbh) + // Initialization. { - initialize(o, f); + initialize(output, f); + data::paste(f, output); initialize(parent, f); initialize(deja_vu, f); - - // init - data::fill(deja_vu, false); - S = histo_reverse_sort(g); - data::paste(f, o); // Replace: for all p, make_set(p) { data(p) = f(p) } - // first pass + s = level::sort_psites_decreasing(g); + } - for (unsigned i = 0; i < S.size(); ++i) + // First pass. { - point p = S[i]; - make_set(p); + for (unsigned i = 0; i < s.nsites(); ++i) + { + P p = s[i]; + parent(p) = p; // Make-Set. mln_niter(N) n(nbh, p); for_all(n) { - if (f.has(n)) - mln_invariant(deja_vu(n) == is_proc(n, p)); - if (f.has(n) && deja_vu(n)) - do_union(n, p); + // if (f.domain().has(n)) + // mln_invariant(deja_vu(n) == is_proc(n, p)); + if (f.domain().has(n) && deja_vu(n)) + { + // Do-Union. + P r = internal::find_root(parent, n); + if (r != p) + { + if (g(r) == g(p) || g(p) >= output(r)) // Equivalence test. + { + parent(r) = p; + if (output(r) > output(p)) + output(p) = output(r); // Increasing criterion. + } + else + output(p) = mln_max(V); + } + } } deja_vu(p) = true; } + } - // second pass - - for (int i = S.size() - 1; i >= 0; --i) + // Second pass. + { + for (int i = s.nsites() - 1; i >= 0; --i) { - point p = S[i]; + P p = s[i]; if (parent(p) == p) { - if (o(p) == mln_max(value)) - o(p) = g(p); + if (output(p) == mln_max(V)) + output(p) = g(p); } else - o(p) = o(parent(p)); + output(p) = output(parent(p)); } - } - bool is_proc(const point& n, const point& p) const - { - return g(n) > g(p) or (g(n) == g(p) && - util::ord_strict(n, p)); + mln_postcondition(output >= f); + mln_postcondition(output <= g); + + trace::exiting("morpho::reconstruction::by_dilation::impl::generic::union_find"); + return output; } - void make_set(const point& p) + + } // end of namespace mln::morpho::reconstruction::by_dilation::impl::generic + + } // end of namespace mln::morpho::reconstruction::by_dilation::impl + + + // Dispatch. + + namespace internal { - parent(p) = p; - // was: data(p) = f(p); - // now: in "initialization" - } - point find_root(const point& x) + template <typename I, typename J, typename N> + inline + mln_concrete(I) + union_find_dispatch(trait::image::kind::logic, + const Image<I>& f, const Image<J>& g, + const Neighborhood<N>& nbh) { - if (parent(x) == x) - return x; - else - return parent(x) = find_root(parent(x)); + // FIXME: Not yet implemented. } - void do_union(const point& n, const point& p) - { - point r = find_root(n); - if (r != p) + template <typename I, typename J, typename N> + inline + mln_concrete(I) + union_find_dispatch(trait::image::kind::any, + const Image<I>& f, const Image<J>& g, + const Neighborhood<N>& nbh) { - // NEW: o replaces data + return impl::generic::union_find(f, g, nbh); + } - if (g(r) == g(p) or g(p) >= o(r)) // equiv test + template <typename I, typename J, typename N> + inline + mln_concrete(I) + union_find_dispatch(const Image<I>& f, const Image<J>& g, + const Neighborhood<N>& nbh) { - parent(r) = p; - if (o(r) > o(p)) - o(p) = o(r); // increasing criterion - } - else - o(p) = mln_max(value); - } + return union_find_dispatch(mln_trait_image_kind(I)(), + f, g, nbh); } - }; + } // end of namespace mln::morpho::reconstruction::by_dilation::internal - template <typename I, typename N> - I union_find(const I& f, const I& g, const N& nbh) + // Facade. + + template <typename I, typename J, typename N> + inline + mln_concrete(I) + union_find(const Image<I>& f, const Image<J>& g, + const Neighborhood<N>& nbh) { - mln_precondition(f <= g); - union_find_t<I, N> run(f, g, nbh); - return run.o; + trace::entering("morpho::reconstruction::by_dilation::union_find"); + + internal::union_find_tests(f, g, nbh); + + mln_concrete(I) output; + output = internal::union_find_dispatch(f, g, nbh); + + trace::exiting("morpho::reconstruction::by_dilation::union_find"); + return output; } +# endif // ! MLN_INCLUDE_ONLY + + } // end of namespace mln::morpho::reconstruction::by_dilation - } // end of namespace mln::morpho::Rd + } // end of namespace mln::morpho::reconstruction } // end of namespace mln::morpho } // end of namespace mln -#endif // ! MLN_MORPHO_RD_UNION_FIND_HH +#endif // ! MLN_MORPHO_RECONSTRUCTION_BY_DILATION_UNION_FIND_HH Property changes on: mln/morpho/reconstruction/by_dilation/union_find.hh ___________________________________________________________________ Added: svn:mergeinfo Index: mln/morpho/reconstruction/by_dilation/all.hh --- mln/morpho/reconstruction/by_dilation/all.hh (revision 0) +++ mln/morpho/reconstruction/by_dilation/all.hh (revision 0) @@ -0,0 +1,59 @@ +// Copyright (C) 2009 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_MORPHO_RECONSTRUCTION_BY_DILATION_ALL_HH +# define MLN_MORPHO_RECONSTRUCTION_BY_DILATION_ALL_HH + + +/// \file mln/morpho/reconstruction by dilation/all.hh +/// +/// File that includes all morphological reconstruction by dilation routines. + + +namespace mln +{ + + namespace morpho + { + + namespace reconstruction + { + + /// Namespace of morphological reconstruction by dilation routines. + namespace by_dilation + {} + + } + } +} + + +# include <mln/morpho/reconstruction/by_dilation/union_find.hh> +// ... + + +#endif // ! MLN_MORPHO_RECONSTRUCTION_BY_DILATION_ALL_HH Index: tests/morpho/reconstruction/Makefile.am --- tests/morpho/reconstruction/Makefile.am (revision 0) +++ tests/morpho/reconstruction/Makefile.am (revision 0) @@ -0,0 +1,11 @@ +## Process this file through Automake to create Makefile.in -*- Makefile -*- + +include $(top_srcdir)/milena/tests/tests.mk + +SUBDIRS = \ + by_dilation + + +TESTS = $(check_PROGRAMS) + + Index: tests/morpho/reconstruction/by_dilation/Makefile.am --- tests/morpho/reconstruction/by_dilation/Makefile.am (revision 0) +++ tests/morpho/reconstruction/by_dilation/Makefile.am (revision 0) @@ -0,0 +1,15 @@ +## Process this file through Automake to create Makefile.in -*- Makefile -*- + +include $(top_srcdir)/milena/tests/tests.mk + + +check_PROGRAMS = \ + union_find + + +union_find_SOURCES = union_find.cc + + +TESTS = $(check_PROGRAMS) + + Index: tests/morpho/reconstruction/by_dilation/union_find.cc --- tests/morpho/reconstruction/by_dilation/union_find.cc (revision 0) +++ tests/morpho/reconstruction/by_dilation/union_find.cc (revision 0) @@ -0,0 +1,64 @@ +// Copyright (C) 2009 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/reconstruction/by_dilation/union_find.cc +/// +/// Test on mln::morpho::reconstruction::by_dilation::union_find + +#include <mln/core/image/image2d.hh> +#include <mln/core/alias/neighb2d.hh> +#include <mln/pw/all.hh> + +#include <mln/io/pgm/load.hh> +#include <mln/value/int_u8.hh> +#include <mln/level/compare.hh> + +#include <mln/morpho/reconstruction/by_dilation/union_find.hh> + +#include "tests/data.hh" + + + +int main() +{ + using namespace mln; + using namespace morpho::reconstruction::by_dilation; + + image2d<value::int_u8> lena, lena_2, out; + io::pgm::load(lena, MLN_IMG_DIR "/tiny.pgm"); + + { + out = union_find(lena, lena, c4()); + mln_assertion(out == lena); + } + + { + initialize(lena_2, lena); + data::fill(lena_2, lena); + out = union_find(lena_2, lena, c4()); + } +} Index: tests/morpho/Makefile.am --- tests/morpho/Makefile.am (revision 3789) +++ tests/morpho/Makefile.am (working copy) @@ -8,6 +8,7 @@ closing \ elementary \ opening \ + reconstruction \ tree \ watershed