URL: https://svn.lrde.epita.fr/svn/oln/trunk/milena ChangeLog: 2009-05-25 Edwin Carlinet <carlinet@lrde.epita.fr> Reconstruction by erosion. * mln/morpho/reconstruction/by_erosion/all.hh, * mln/morpho/reconstruction/by_erosion/union_find.hh, * mln/morpho/reconstruction/by_erosion: Reconstruction by erosion. * tests/morpho/reconstruction/Makefile.am, * tests/morpho/reconstruction/by_erosion/union_find.cc, * tests/morpho/reconstruction/by_erosion, * tests/unit_test/unit-tests.mk: Reconstruction by erosion test files. --- mln/morpho/reconstruction/by_erosion/all.hh | 59 ++++ mln/morpho/reconstruction/by_erosion/union_find.hh | 280 +++++++++++++++++++ tests/morpho/reconstruction/Makefile.am | 3 tests/morpho/reconstruction/by_erosion/Makefile.am | 15 + tests/morpho/reconstruction/by_erosion/union_find.cc | 64 ++++ tests/unit_test/unit-tests.mk | 20 + 6 files changed, 438 insertions(+), 3 deletions(-) Index: trunk/milena/tests/morpho/reconstruction/by_erosion/Makefile.am =================================================================== --- trunk/milena/tests/morpho/reconstruction/by_erosion/Makefile.am (revision 0) +++ trunk/milena/tests/morpho/reconstruction/by_erosion/Makefile.am (revision 3869) @@ -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: trunk/milena/tests/morpho/reconstruction/by_erosion/union_find.cc =================================================================== --- trunk/milena/tests/morpho/reconstruction/by_erosion/union_find.cc (revision 0) +++ trunk/milena/tests/morpho/reconstruction/by_erosion/union_find.cc (revision 3869) @@ -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_erosion/union_find.cc +/// +/// Test on mln::morpho::reconstruction::by_erosion::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_erosion/union_find.hh> + +#include "tests/data.hh" + + + +int main() +{ + using namespace mln; + using namespace morpho::reconstruction::by_erosion; + + 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()); + } +} Property changes on: trunk/milena/tests/morpho/reconstruction/by_erosion ___________________________________________________________________ Added: svn:mergeinfo Index: trunk/milena/tests/morpho/reconstruction/Makefile.am =================================================================== --- trunk/milena/tests/morpho/reconstruction/Makefile.am (revision 3868) +++ trunk/milena/tests/morpho/reconstruction/Makefile.am (revision 3869) @@ -3,7 +3,8 @@ include $(top_srcdir)/milena/tests/tests.mk SUBDIRS = \ - by_dilation + by_dilation \ + by_erosion TESTS = $(check_PROGRAMS) Index: trunk/milena/tests/unit_test/unit-tests.mk =================================================================== --- trunk/milena/tests/unit_test/unit-tests.mk (revision 3868) +++ trunk/milena/tests/unit_test/unit-tests.mk (revision 3869) @@ -239,6 +239,8 @@ mln_core_image_complex_window_piter \ mln_core_image_complex_windows \ mln_core_image_decorated_image \ +mln_core_image_dmorph_all \ +mln_core_image_dmorph_transformed_image \ mln_core_image_edge_image \ mln_core_image_essential \ mln_core_image_extended \ @@ -376,6 +378,8 @@ mln_core_site_set_p_run_piter \ mln_core_site_set_p_set \ mln_core_site_set_p_set_of \ +mln_core_site_set_p_transformed \ +mln_core_site_set_p_transformed_piter \ mln_core_site_set_p_vaccess \ mln_core_site_set_p_vertices \ mln_core_site_set_p_vertices_psite \ @@ -635,6 +639,8 @@ mln_io_pgm_all \ mln_io_pgm_load \ mln_io_pgm_save \ +mln_io_plot_all \ +mln_io_plot_load \ mln_io_plot_save \ mln_io_pnm_all \ mln_io_pnm_load_header \ @@ -648,7 +654,6 @@ mln_io_ppm_save \ mln_io_tiff_all \ mln_io_tiff_load \ -mln_io_tiff_save \ mln_io_txt_all \ mln_io_txt_save \ mln_labeling_all \ @@ -900,6 +905,8 @@ mln_morpho_reconstruction_all \ mln_morpho_reconstruction_by_dilation_all \ mln_morpho_reconstruction_by_dilation_union_find \ +mln_morpho_reconstruction_by_erosion_all \ +mln_morpho_reconstruction_by_erosion_union_find \ mln_morpho_skeleton_constrained \ mln_morpho_thickening \ mln_morpho_thick_miss \ @@ -1211,6 +1218,7 @@ mln_value_stack \ mln_value_super_value \ mln_value_viter \ +mln_version \ mln_win_all \ mln_win_backdiag2d \ mln_win_ball \ @@ -1490,6 +1498,8 @@ mln_core_image_complex_window_piter_SOURCES = mln_core_image_complex_window_piter.cc mln_core_image_complex_windows_SOURCES = mln_core_image_complex_windows.cc mln_core_image_decorated_image_SOURCES = mln_core_image_decorated_image.cc +mln_core_image_dmorph_all_SOURCES = mln_core_image_dmorph_all.cc +mln_core_image_dmorph_transformed_image_SOURCES = mln_core_image_dmorph_transformed_image.cc mln_core_image_edge_image_SOURCES = mln_core_image_edge_image.cc mln_core_image_essential_SOURCES = mln_core_image_essential.cc mln_core_image_extended_SOURCES = mln_core_image_extended.cc @@ -1627,6 +1637,8 @@ mln_core_site_set_p_run_piter_SOURCES = mln_core_site_set_p_run_piter.cc mln_core_site_set_p_set_SOURCES = mln_core_site_set_p_set.cc mln_core_site_set_p_set_of_SOURCES = mln_core_site_set_p_set_of.cc +mln_core_site_set_p_transformed_SOURCES = mln_core_site_set_p_transformed.cc +mln_core_site_set_p_transformed_piter_SOURCES = mln_core_site_set_p_transformed_piter.cc mln_core_site_set_p_vaccess_SOURCES = mln_core_site_set_p_vaccess.cc mln_core_site_set_p_vertices_SOURCES = mln_core_site_set_p_vertices.cc mln_core_site_set_p_vertices_psite_SOURCES = mln_core_site_set_p_vertices_psite.cc @@ -1886,6 +1898,8 @@ mln_io_pgm_all_SOURCES = mln_io_pgm_all.cc mln_io_pgm_load_SOURCES = mln_io_pgm_load.cc mln_io_pgm_save_SOURCES = mln_io_pgm_save.cc +mln_io_plot_all_SOURCES = mln_io_plot_all.cc +mln_io_plot_load_SOURCES = mln_io_plot_load.cc mln_io_plot_save_SOURCES = mln_io_plot_save.cc mln_io_pnm_all_SOURCES = mln_io_pnm_all.cc mln_io_pnm_load_header_SOURCES = mln_io_pnm_load_header.cc @@ -1899,7 +1913,6 @@ mln_io_ppm_save_SOURCES = mln_io_ppm_save.cc mln_io_tiff_all_SOURCES = mln_io_tiff_all.cc mln_io_tiff_load_SOURCES = mln_io_tiff_load.cc -mln_io_tiff_save_SOURCES = mln_io_tiff_save.cc mln_io_txt_all_SOURCES = mln_io_txt_all.cc mln_io_txt_save_SOURCES = mln_io_txt_save.cc mln_labeling_all_SOURCES = mln_labeling_all.cc @@ -2151,6 +2164,8 @@ mln_morpho_reconstruction_all_SOURCES = mln_morpho_reconstruction_all.cc mln_morpho_reconstruction_by_dilation_all_SOURCES = mln_morpho_reconstruction_by_dilation_all.cc mln_morpho_reconstruction_by_dilation_union_find_SOURCES = mln_morpho_reconstruction_by_dilation_union_find.cc +mln_morpho_reconstruction_by_erosion_all_SOURCES = mln_morpho_reconstruction_by_erosion_all.cc +mln_morpho_reconstruction_by_erosion_union_find_SOURCES = mln_morpho_reconstruction_by_erosion_union_find.cc mln_morpho_skeleton_constrained_SOURCES = mln_morpho_skeleton_constrained.cc mln_morpho_thickening_SOURCES = mln_morpho_thickening.cc mln_morpho_thick_miss_SOURCES = mln_morpho_thick_miss.cc @@ -2462,6 +2477,7 @@ mln_value_stack_SOURCES = mln_value_stack.cc mln_value_super_value_SOURCES = mln_value_super_value.cc mln_value_viter_SOURCES = mln_value_viter.cc +mln_version_SOURCES = mln_version.cc mln_win_all_SOURCES = mln_win_all.cc mln_win_backdiag2d_SOURCES = mln_win_backdiag2d.cc mln_win_ball_SOURCES = mln_win_ball.cc Index: trunk/milena/mln/morpho/reconstruction/by_erosion/all.hh =================================================================== --- trunk/milena/mln/morpho/reconstruction/by_erosion/all.hh (revision 0) +++ trunk/milena/mln/morpho/reconstruction/by_erosion/all.hh (revision 3869) @@ -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_EROSION_ALL_HH +# define MLN_MORPHO_RECONSTRUCTION_BY_EROSION_ALL_HH + + +/// \file mln/morpho/reconstruction by erosion/all.hh +/// +/// File that includes all morphological reconstruction by erosion routines. + + +namespace mln +{ + + namespace morpho + { + + namespace reconstruction + { + + /// Namespace of morphological reconstruction by erosion routines. + namespace by_erosion + {} + + } + } +} + + +# include <mln/morpho/reconstruction/by_erosion/union_find.hh> +// ... + + +#endif // ! MLN_MORPHO_RECONSTRUCTION_BY_EROSION_ALL_HH Property changes on: trunk/milena/mln/morpho/reconstruction/by_erosion/all.hh ___________________________________________________________________ Added: svn:mergeinfo Index: trunk/milena/mln/morpho/reconstruction/by_erosion/union_find.hh =================================================================== --- trunk/milena/mln/morpho/reconstruction/by_erosion/union_find.hh (revision 0) +++ trunk/milena/mln/morpho/reconstruction/by_erosion/union_find.hh (revision 3869) @@ -0,0 +1,280 @@ +// 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_EROSION_UNION_FIND_HH +# define MLN_MORPHO_RECONSTRUCTION_BY_EROSION_UNION_FIND_HH + +# include <vector> +# include <mln/core/concept/image.hh> +# include <mln/core/concept/neighborhood.hh> +# include <mln/data/fill.hh> +# include <mln/level/compare.hh> +# include <mln/level/sort_psites.hh> + + +namespace mln +{ + + namespace morpho + { + + namespace reconstruction + { + + namespace by_erosion + { + + + 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 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_erosion::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_erosion::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::fill(output, f); + initialize(parent, f); + initialize(deja_vu, f); + data::fill(deja_vu, false); + + s = level::sort_psites_increasing(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) +// == +// (g(n) > g(p) || (g(n) == g(p) +// && util::ord_strict(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_min(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_min(V)) + output(p) = g(p); + } + else + output(p) = output(parent(p)); + } + } + + mln_postcondition(output >= f); + mln_postcondition(output >= g); + + trace::exiting("morpho::reconstruction::by_erosion::impl::generic::union_find"); + return output; + } + + } // end of namespace mln::morpho::reconstruction::by_erosion::impl::generic + + } // end of namespace mln::morpho::reconstruction::by_erosion::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_erosion::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_erosion::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_erosion::union_find"); + return output; + } + +# endif // ! MLN_INCLUDE_ONLY + + } // end of namespace mln::morpho::reconstruction::by_erosion + + } // end of namespace mln::morpho::reconstruction + + } // end of namespace mln::morpho + +} // end of namespace mln + + +#endif // ! MLN_MORPHO_RECONSTRUCTION_BY_EROSION_UNION_FIND_HH Property changes on: trunk/milena/mln/morpho/reconstruction/by_erosion/union_find.hh ___________________________________________________________________ Added: svn:mergeinfo