[Olena-patches] [PATCH 29/31] 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. --- milena/ChangeLog | 21 ++ milena/mln/morpho/all.hh | 9 +- milena/mln/morpho/reconstruction/all.hh | 57 ++++ .../mln/morpho/reconstruction/by_dilation/all.hh | 59 ++++ .../reconstruction/by_dilation/union_find.hh | 286 ++++++++++++++++++++ milena/tests/morpho/Makefile.am | 1 + milena/tests/morpho/reconstruction/Makefile.am | 11 + .../morpho/reconstruction/by_dilation/Makefile.am | 15 + .../reconstruction/by_dilation/union_find.cc | 64 +++++ 9 files changed, 519 insertions(+), 4 deletions(-) create mode 100644 milena/mln/morpho/reconstruction/all.hh create mode 100644 milena/mln/morpho/reconstruction/by_dilation/all.hh create mode 100644 milena/mln/morpho/reconstruction/by_dilation/union_find.hh create mode 100644 milena/tests/morpho/reconstruction/Makefile.am create mode 100644 milena/tests/morpho/reconstruction/by_dilation/Makefile.am create mode 100644 milena/tests/morpho/reconstruction/by_dilation/union_find.cc diff --git a/milena/ChangeLog b/milena/ChangeLog index b26865f..34bb8a0 100644 --- a/milena/ChangeLog +++ b/milena/ChangeLog @@ -1,3 +1,24 @@ +2009-05-14 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. + 2009-05-12 Thierry Geraud &lt;thierry.geraud(a)lrde.epita.fr&gt; De-activate hsl stuff in value rgb. diff --git a/milena/mln/morpho/all.hh b/milena/mln/morpho/all.hh index d420dd1..8d7425a 100644 --- a/milena/mln/morpho/all.hh +++ b/milena/mln/morpho/all.hh @@ -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 @@ namespace mln # 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> diff --git a/milena/mln/morpho/reconstruction/all.hh b/milena/mln/morpho/reconstruction/all.hh new file mode 100644 index 0000000..4b7db9e --- /dev/null +++ b/milena/mln/morpho/reconstruction/all.hh @@ -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 diff --git a/milena/mln/morpho/reconstruction/by_dilation/all.hh b/milena/mln/morpho/reconstruction/by_dilation/all.hh new file mode 100644 index 0000000..d88213d --- /dev/null +++ b/milena/mln/morpho/reconstruction/by_dilation/all.hh @@ -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 diff --git a/milena/mln/morpho/reconstruction/by_dilation/union_find.hh b/milena/mln/morpho/reconstruction/by_dilation/union_find.hh new file mode 100644 index 0000000..4a7dec0 --- /dev/null +++ b/milena/mln/morpho/reconstruction/by_dilation/union_find.hh @@ -0,0 +1,286 @@ +// 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 +// 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_UNION_FIND_HH +# define MLN_MORPHO_RECONSTRUCTION_BY_DILATION_UNION_FIND_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 +{ + + namespace morpho + { + + 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 + + + // Tests. + + namespace internal + { + + 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; + } + + + +// 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, P) parent; + mln_concrete(I) output; + + // Initialization. + { + initialize(output, f); + data::paste(f, output); + initialize(parent, f); + initialize(deja_vu, f); + data::fill(deja_vu, false); + + s = level::sort_psites_decreasing(g); + } + + // First pass. + { + 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.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.nsites() - 1; i >= 0; --i) + { + P p = s[i]; + if (parent(p) == p) + { + if (output(p) == mln_max(V)) + output(p) = g(p); + } + else + output(p) = output(parent(p)); + } + } + + mln_postcondition(output >= f); + mln_postcondition(output <= g); + + trace::exiting("morpho::reconstruction::by_dilation::impl::generic::union_find"); + return output; + } + + + } // end of namespace mln::morpho::reconstruction::by_dilation::impl::generic + + } // end of namespace mln::morpho::reconstruction::by_dilation::impl + + + // Dispatch. + + namespace internal + { + + 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) + { + // FIXME: Not yet implemented. + } + + 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) + { + return impl::generic::union_find(f, g, nbh); + } + + 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) + { + return union_find_dispatch(mln_trait_image_kind(I)(), + f, g, nbh); + } + + } // end of namespace mln::morpho::reconstruction::by_dilation::internal + + + // 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) + { + 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::reconstruction + + } // end of namespace mln::morpho + +} // end of namespace mln + + +#endif // ! MLN_MORPHO_RECONSTRUCTION_BY_DILATION_UNION_FIND_HH diff --git a/milena/tests/morpho/Makefile.am b/milena/tests/morpho/Makefile.am index a4b7c6b..f66924d 100644 --- a/milena/tests/morpho/Makefile.am +++ b/milena/tests/morpho/Makefile.am @@ -8,6 +8,7 @@ SUBDIRS = \ closing \ elementary \ opening \ + reconstruction \ tree \ watershed diff --git a/milena/tests/morpho/reconstruction/Makefile.am b/milena/tests/morpho/reconstruction/Makefile.am new file mode 100644 index 0000000..1cfac92 --- /dev/null +++ b/milena/tests/morpho/reconstruction/Makefile.am @@ -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) + + diff --git a/milena/tests/morpho/reconstruction/by_dilation/Makefile.am b/milena/tests/morpho/reconstruction/by_dilation/Makefile.am new file mode 100644 index 0000000..fd83a0b --- /dev/null +++ b/milena/tests/morpho/reconstruction/by_dilation/Makefile.am @@ -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) + + diff --git a/milena/tests/morpho/reconstruction/by_dilation/union_find.cc b/milena/tests/morpho/reconstruction/by_dilation/union_find.cc new file mode 100644 index 0000000..46631f0 --- /dev/null +++ b/milena/tests/morpho/reconstruction/by_dilation/union_find.cc @@ -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()); + } +} -- 1.6.1.2