* 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 <thierry.geraud(a)lrde.epita.fr>
+
+ 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 <thierry.geraud(a)lrde.epita.fr>
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
