* mln/morpho/skeleton_constrained.hh: cleanup. * mln/topo/skeleton/crest.hh, * mln/topo/skeleton/is_simple_point.hh: new routines. * tests/topo/Makefile.am, * tests/topo/skeleton/Makefile.am, * tests/topo/skeleton/crest.cc, * tests/topo/skeleton/is_simple_point: new tests. --- milena/ChangeLog | 14 ++ milena/mln/morpho/skeleton_constrained.hh | 29 ++-- milena/mln/topo/skeleton/crest.hh | 123 +++++++++++ milena/mln/topo/skeleton/is_simple_point.hh | 287 +++++++++++++++++++++++++ milena/tests/topo/Makefile.am | 2 + milena/tests/topo/skeleton/Makefile.am | 12 + milena/tests/topo/skeleton/crest.cc | 85 ++++++++ milena/tests/topo/skeleton/is_simple_point.cc | 53 +++++ 8 files changed, 592 insertions(+), 13 deletions(-) create mode 100644 milena/mln/topo/skeleton/crest.hh create mode 100644 milena/mln/topo/skeleton/is_simple_point.hh create mode 100644 milena/tests/topo/skeleton/Makefile.am create mode 100644 milena/tests/topo/skeleton/crest.cc create mode 100644 milena/tests/topo/skeleton/is_simple_point.cc diff --git a/milena/ChangeLog b/milena/ChangeLog index d4ff83d..6938aa3 100644 --- a/milena/ChangeLog +++ b/milena/ChangeLog @@ -1,5 +1,19 @@ 2009-05-15 Guillaume Lazzara <lazzara@lrde.epita.fr> + Add new routines related to constrained skeletons. + + * mln/morpho/skeleton_constrained.hh: cleanup. + + * mln/topo/skeleton/crest.hh, + * mln/topo/skeleton/is_simple_point.hh: new routines. + + * tests/topo/Makefile.am, + * tests/topo/skeleton/Makefile.am, + * tests/topo/skeleton/crest.cc, + * tests/topo/skeleton/is_simple_point: new tests. + +2009-05-15 Guillaume Lazzara <lazzara@lrde.epita.fr> + Add transformation::rotation. * mln/transformation/all.hh, diff --git a/milena/mln/morpho/skeleton_constrained.hh b/milena/mln/morpho/skeleton_constrained.hh index 273a259..0b4e00c 100644 --- a/milena/mln/morpho/skeleton_constrained.hh +++ b/milena/mln/morpho/skeleton_constrained.hh @@ -1,4 +1,5 @@ -// Copyright (C) 2008 EPITA Research and Development Laboratory (LRDE) +// Copyright (C) 2008, 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 @@ -69,11 +70,18 @@ namespace mln const Neighborhood<N>& nbh_, const F& is_simple, const Image<K>& constraint_, const Image<R>& priority_) { + trace::entering("morpho::skeleton_constrained"); + const I& input = exact(input_); const N& nbh = exact(nbh_); const K& constraint = exact(constraint_); const R& priority = exact(priority_); + mln_precondition(input.is_valid()); + mln_precondition(nbh.is_valid()); + mln_precondition(constraint.is_valid()); + mln_precondition(priority.is_valid()); + extension::adjust_duplicate(input, nbh); // FIXME: Tests! @@ -92,17 +100,13 @@ namespace mln mln_piter(I) p(input.domain()); for_all(p) - if ( input(p) == false && - is_simple(input, nbh, p) ) // p is a simple point of the background. + if (input(p) == false && + is_simple(input, nbh, p)) // p is a simple point of the background. { q.push(priority(p), p); - // std::cout << p << " "; } - std::cout << std::endl; } - // std::cout << std::endl << "propagation..." << std::endl; - // Propagation. { P p; @@ -111,19 +115,18 @@ namespace mln { p = q.pop_front(); for_all(n) - if ( output.has(n) && - output(n) == true && - constraint(n) == false && - is_simple(output, nbh, n) ) + if (output.has(n) && + output(n) == true && + constraint(n) == false && + is_simple(output, nbh, n)) { output(n) = false; // Remove n from object. q.push(priority(n), n); - // std::cout << n << " "; } } - std::cout << std::endl; } + trace::exiting("morpho::skeleton_constrained"); return output; } diff --git a/milena/mln/topo/skeleton/crest.hh b/milena/mln/topo/skeleton/crest.hh new file mode 100644 index 0000000..432b57c --- /dev/null +++ b/milena/mln/topo/skeleton/crest.hh @@ -0,0 +1,123 @@ +// 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_TOPO_SKELETON_CREST_HH +# define MLN_TOPO_SKELETON_CREST_HH + +/// \file mln/topo/skeleton/crest.hh +/// +/// Compute skeletization constraints. + + +namespace mln +{ + + namespace topo + { + + namespace skeleton + { + + + /// Compute skeletization constraints. + /// + /// \param[in] input_ A binary image. + /// \param[in] dist_map_ A distance map of \p input. Contains the + /// inner object distance map. + /// \param[in] nbh_ A neighborhood. + /// + /// \result A binary image. + // + template <typename I, typename D, typename N> + mln_concrete(I) + crest(const Image<I>& input_, const Image<D>& dist_map_, + const Neighborhood<N>& nbh_); + + + +# ifndef MLN_INCLUDE_ONLY + + + template <typename I, typename D, typename N> + mln_concrete(I) + crest(const Image<I>& input_, const Image<D>& dist_map_, + const Neighborhood<N>& nbh_) + { + trace::entering("topo::skeleton::crest"); + const I& input = exact(input_); + const D& dist_map = exact(dist_map_); + const N& nbh = exact(nbh_); + + mlc_equal(mln_value(I), bool)::check(); + mln_precondition(input.is_valid()); + mln_precondition(dist_map.is_valid()); + mln_precondition(nbh.is_valid()); + + mln_concrete(I) is_crest; + initialize(is_crest, input); + data::fill(is_crest, false); + + mln_piter(I) p(input.domain()); + mln_niter(N) n(nbh, p); + for_all(p) + { + if (!input(p) || dist_map(p) < 0) + continue; + + unsigned nb_eq = 0; + unsigned nb_gt = 0; + unsigned nb_lt = 0; + for_all(n) + if (input.domain().has(n)) + { + if (dist_map(n) == dist_map(p)) + ++nb_eq; + else if (dist_map(n) > dist_map(p)) + ++nb_gt; + else + ++nb_lt; + } + + if ((nb_lt + nb_eq) > 5) // Pixel Superiority index + is_crest(p) = true; + } + + trace::exiting("topo::skeleton::crest"); + return is_crest; + } + + +# endif // ! MLN_INCLUDE_ONLY + + + } // end of namespace mln::topo::skeleton + + } // end of namespace mln::topo + +} // end of namespace mln + +#endif // ! MLN_TOPO_SKELETON_CREST_HH diff --git a/milena/mln/topo/skeleton/is_simple_point.hh b/milena/mln/topo/skeleton/is_simple_point.hh new file mode 100644 index 0000000..4d31dfc --- /dev/null +++ b/milena/mln/topo/skeleton/is_simple_point.hh @@ -0,0 +1,287 @@ +// 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_TOPO_SKELETON_IS_SIMPLE_POINT_HH +# define MLN_TOPO_SKELETON_IS_SIMPLE_POINT_HH + +/// \file mln/topo/skeleton/is_simple_point.hh +/// +/// is_simple_point tells if a point is simple or not. +/// For more information refer to bertrand.07.chap. + +# include <mln/core/concept/image.hh> +# include <mln/core/alias/point2d.hh> +# include <mln/core/alias/neighb2d.hh> + +namespace mln +{ + + namespace topo + { + + namespace skeleton + { + + /*! Tell if a point is simple or not. A point of an object is simple + * if in its c8 neiborhood, there is exactly one connected component of the + * object, and only one connected component of the background + * Examples : ( | == object, - = background) + * \verbatim + + - - | + | P | Here p is simple in the c4 and c8 case. + | | | + + - | - + | P | Here p is never simple. + | | | + + \endverbatim + */ + template <typename I, typename N> + bool + is_simple_point(const Image<I>& ima, + const Neighborhood<N>& nbh, + const mln_site(I)& p); + + +# ifndef MLN_INCLUDE_ONLY + + + namespace internal + { + + + static const unsigned char nb_connexity_c8[256] = + { + 0, 1, 1, 1, 1, 2, 1, 1, 1, 1, 1, 1, 2, 2, 1, 1, + 1, 2, 1, 1, 1, 2, 1, 1, 2, 2, 1, 1, 2, 2, 1, 1, + 1, 2, 2, 2, 2, 3, 2, 2, 1, 1, 1, 1, 2, 2, 1, 1, + 2, 3, 2, 2, 2, 3, 2, 2, 2, 2, 1, 1, 2, 2, 1, 1, + + 1, 2, 2, 2, 2, 3, 2, 2, 1, 1, 1, 1, 2, 2, 1, 1, + 1, 2, 1, 1, 1, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, + 1, 2, 2, 2, 2, 3, 2, 2, 1, 1, 1, 1, 2, 2, 1, 1, + 1, 2, 1, 1, 1, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, + + 1, 2, 2, 2, 2, 3, 2, 2, 2, 2, 2, 2, 3, 3, 2, 2, + 1, 2, 1, 1, 1, 2, 1, 1, 2, 2, 1, 1, 2, 2, 1, 1, + 2, 3, 3, 3, 3, 4, 3, 3, 2, 2, 2, 2, 3, 3, 2, 2, + 2, 3, 2, 2, 2, 3, 2, 2, 2, 2, 1, 1, 2, 2, 1, 1, + + 1, 2, 2, 2, 2, 3, 2, 2, 1, 1, 1, 1, 2, 2, 1, 1, + 1, 2, 1, 1, 1, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, + 1, 2, 2, 2, 2, 3, 2, 2, 1, 1, 1, 1, 2, 2, 1, 1, + 1, 2, 1, 1, 1, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1 + }; + + static const unsigned char nb_connexity_c4[256] = + { + 0, 0, 1, 1, 0, 0, 1, 1, 1, 1, 2, 1, 1, 1, 2, 1, + 1, 1, 2, 2, 1, 1, 1, 1, 2, 2, 3, 2, 2, 2, 2, 1, + 0, 0, 1, 1, 0, 0, 1, 1, 1, 1, 2, 1, 1, 1, 2, 1, + 1, 1, 2, 2, 1, 1, 1, 1, 2, 2, 3, 2, 2, 2, 2, 1, + + 1, 1, 2, 2, 1, 1, 2, 2, 2, 2, 3, 2, 2, 2, 3, 2, + 2, 2, 3, 3, 2, 2, 2, 2, 3, 3, 4, 3, 3, 3, 3, 2, + 1, 1, 2, 2, 1, 1, 2, 2, 1, 1, 2, 1, 1, 1, 2, 1, + 2, 2, 3, 3, 2, 2, 2, 2, 2, 2, 3, 2, 2, 2, 2, 1, + + 0, 0, 1, 1, 0, 0, 1, 1, 1, 1, 2, 1, 1, 1, 2, 1, + 1, 1, 2, 2, 1, 1, 1, 1, 2, 2, 3, 2, 2, 2, 2, 1, + 0, 0, 1, 1, 0, 0, 1, 1, 1, 1, 2, 1, 1, 1, 2, 1, + 1, 1, 2, 2, 1, 1, 1, 1, 2, 2, 3, 2, 2, 2, 2, 1, + + 1, 1, 2, 2, 1, 1, 2, 2, 2, 2, 3, 2, 2, 2, 3, 2, + 1, 1, 2, 2, 1, 1, 1, 1, 2, 2, 3, 2, 2, 2, 2, 1, + 1, 1, 2, 2, 1, 1, 2, 2, 1, 1, 2, 1, 1, 1, 2, 1, + 1, 1, 2, 2, 1, 1, 1, 1, 1, 1, 2, 1, 1, 1, 1, 1 + }; + + + + template <typename I, typename N> + inline + unsigned + nb_connexity2d(const I& ima, + const N& nbh, + const mln_site(I)& p, + bool object) + { + unsigned res = 0; + + mln_bkd_niter(N) n(c8(), p); + for_all(n) + { + res = (res << 1); + if (ima.domain().has(n) && ima(n) == object) + res = res | 1; + } + + if (nbh == c8()) + return nb_connexity_c8[res]; + else + { + mln_assertion(nbh == c4()); + return nb_connexity_c4[res]; + } + } + + + template <typename N> + neighb2d + complement2d(const Neighborhood<N>& nbh_) + { + const N& nbh = exact(nbh_); + mln_precondition(nbh.is_valid()); + mln_precondition(nbh == c4() || nbh == c8()); + + if (nbh == c4()) + return c8(); + else + return c4(); + } + + + // Tests. + + template <typename I, typename N> + inline + void + is_simple_point_tests(const Image<I>& ima_, + const Neighborhood<N>& nbh_, + const mln_site(I)& p) + { + const I& ima = exact(ima_); + const N& nbh = exact(nbh_); + + mln_assertion(nbh == c4() || nbh == c8()); + mln_precondition(ima.is_valid()); + mln_precondition(nbh.is_valid()); + + (void) ima; + (void) nbh; + (void) p; + } + + } // end of namespace mln::topo::skeleton::internal + + + + // Implementations + + namespace impl + { + + template <typename I, typename N> + inline + bool + is_simple_point2d(const Image<I>& ima_, + const Neighborhood<N>& nbh_, + const point2d& p) + { + const I& ima = exact(ima_); + const N& nbh = exact(nbh_); + + internal::is_simple_point_tests(ima, nbh, p); + + bool b = (internal::nb_connexity2d(ima, nbh, p, true) == 1) + && (internal::nb_connexity2d(ima, internal::complement2d(nbh), + p, false) == 1); + + trace::exiting("topo::skeleton::is_simple_point2d"); + return b; + } + + } // end of namespace mln::topo::skeleton::impl + + + + + // Dispatch + + namespace internal + { + + template <typename I, typename N> + inline + bool + is_simple_point_dispatch(const Image<I>& ima, + const Neighborhood<N>& nbh, + const point2d& p) + { + return impl::is_simple_point2d(ima, nbh, p); + } + + + template <typename I, typename N> + inline + bool + is_simple_point_dispatch(const Image<I>& ima, + const Neighborhood<N>& nbh, + const mln_site(I)& p) + { + /// Not implemented for that site type yet. + mlc_abort(I)::check(); + return false; + } + + } // end of namespace mln::topo::skeleton::internal + + + + + + // Facade + + template <typename I, typename N> + inline + bool + is_simple_point(const Image<I>& ima, + const Neighborhood<N>& nbh, + const mln_site(I)& p) + { + trace::entering("topo::skeleton::is_simple_point2d"); + + internal::is_simple_point_tests(ima, nbh, p); + + bool b = internal::is_simple_point_dispatch(ima, nbh, p); + + trace::exiting("topo::skeleton::is_simple_point2d"); + return b; + } + + +# endif // MLN_TOPO_SKELETON_INCLUDE_ONLY + + } // end of namespace mln::topo::skeleton + + } // end of namespace mln::topo + +} // end of namespace mln + +#endif // ! MLN_TOPO_SKELETON_IS_SIMPLE_POINT_HH diff --git a/milena/tests/topo/Makefile.am b/milena/tests/topo/Makefile.am index b955229..b9b3982 100644 --- a/milena/tests/topo/Makefile.am +++ b/milena/tests/topo/Makefile.am @@ -2,6 +2,8 @@ include $(top_srcdir)/milena/tests/tests.mk +SUBDIRS = skeleton + check_PROGRAMS = \ complex diff --git a/milena/tests/topo/skeleton/Makefile.am b/milena/tests/topo/skeleton/Makefile.am new file mode 100644 index 0000000..ff96b31 --- /dev/null +++ b/milena/tests/topo/skeleton/Makefile.am @@ -0,0 +1,12 @@ +## Process this file through Automake to create Makefile.in -*- Makefile -*- + +include $(top_srcdir)/milena/tests/tests.mk + +check_PROGRAMS = \ + crest \ + is_simple_point + +crest_SOURCES = crest.cc +is_simple_point_SOURCES = is_simple_point.cc + +TESTS = $(check_PROGRAMS) diff --git a/milena/tests/topo/skeleton/crest.cc b/milena/tests/topo/skeleton/crest.cc new file mode 100644 index 0000000..ba2c500 --- /dev/null +++ b/milena/tests/topo/skeleton/crest.cc @@ -0,0 +1,85 @@ +// 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/topo/skeleton/crest.cc +/// +/// Test of mln::topo::skeleton::crest. + +# include <mln/core/alias/neighb2d.hh> +# include <mln/core/image/image2d.hh> + +# include <mln/level/compare.hh> + +# include <mln/logical/not.hh> + +# include <mln/make/image.hh> +# include <mln/make/w_window2d_int.hh> + +# include <mln/topo/skeleton/crest.hh> + +# include <mln/transform/distance_front.hh> + +# include <mln/value/int_u8.hh> + + +int main() +{ + using namespace mln; + + bool ref_dat[][9] = { { 0, 0, 0, 0, 0, 0, 0, 0, 0 }, + { 0, 0, 0, 0, 0, 1, 0, 0, 0 }, + { 0, 0, 0, 0, 1, 1, 0, 1, 0 }, + { 0, 1, 1, 1, 1, 1, 0, 1, 0 }, + { 0, 0, 0, 0, 1, 0, 0, 0, 0 }, + { 0, 0, 0, 0, 1, 0, 1, 0, 0 }, + { 0, 0, 0, 0, 0, 0, 0, 0, 0 } }; + + bool in_dat[][9] = { { 0, 0, 0, 0, 1, 1, 1, 0, 0 }, + { 0, 0, 0, 1, 1, 1, 1, 0, 0 }, + { 0, 0, 1, 1, 1, 1, 1, 1, 1 }, + { 0, 1, 1, 1, 1, 1, 1, 1, 1 }, + { 0, 0, 1, 1, 1, 1, 1, 0, 0 }, + { 0, 0, 0, 1, 1, 1, 1, 0, 0 }, + { 0, 0, 0, 0, 1, 0, 0, 0, 0 } }; + + int vals[] = { 0, 9, 0, 9, 0, + 9, 6, 4, 6, 9, + 0, 4, 0, 4, 0, // Values of distances. + 9, 6, 4, 6, 9, + 0, 9, 0, 9, 0 }; + + image2d<bool> input = make::image(in_dat); + image2d<bool> crest_ref = make::image(ref_dat); + + image2d<value::int_u8> + dist_map = transform::distance_front(logical::not_(input), c8(), + make::w_window2d_int(vals), + mln_max(value::int_u8)); + image2d<bool> crest_ima = topo::skeleton::crest(input, dist_map, c8()); + + mln_assertion(crest_ima == crest_ref); +} diff --git a/milena/tests/topo/skeleton/is_simple_point.cc b/milena/tests/topo/skeleton/is_simple_point.cc new file mode 100644 index 0000000..23cb97c --- /dev/null +++ b/milena/tests/topo/skeleton/is_simple_point.cc @@ -0,0 +1,53 @@ +// 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/topo/skeleton/is_simple_point.cc +/// +/// Test mln::topo::skeleton::is_simple_point. + +#include <mln/make/image2d.hh> +#include <mln/topo/skeleton/is_simple_point.hh> +#include <mln/make/image.hh> + +#include <mln/debug/println.hh> + +static const unsigned ref[] = { 1, 0, 1, 1, 1, 0, 0, 0, 0, 1, 1, 0 }; + +int main() +{ + using namespace mln; + + bool vals[][6] = { { 0, 1, 0, 0, 1, 1 }, + { 0, 0, 0, 0, 1, 1 } }; + + image2d<bool> ima = make::image(vals); + + unsigned i = 0; + mln_piter_(image2d<bool>) p(ima.domain()); + for_all(p) + mln_assertion(ref[i++] == topo::skeleton::is_simple_point(ima, c8(), p)); +} -- 1.5.6.5