[Olena-patches] last-svn-commit-203-g876aaf5 More generic breadth-first-thinning-based skeleton transformations.

* mln/topo/is_simple_cell.hh: Make this functor more generic. * mln/topo/detach: Rename as... * mln/topo/detach_cell.hh: ...this. (detach): Turn this function into... (detach_cell): ...a more generic functor. * mln/make/attachment.hh (mln::make::attachment) * mln/make/detachment.hh (mln::make::detachment): Make these routines more generic. * mln/topo/skeleton/breadth_first_thinning.hh (mln::topo::skeleton::breadth_first_thinning): Adjust. * headers.mk: Regen. --- milena/ChangeLog | 17 ++ milena/headers.mk | 2 +- milena/mln/make/attachment.hh | 48 ++++--- milena/mln/make/detachment.hh | 41 +++-- milena/mln/topo/detach.hh | 83 ---------- milena/mln/topo/detach_cell.hh | 157 ++++++++++++++++++++ milena/mln/topo/is_simple_cell.hh | 81 ++++++----- milena/mln/topo/skeleton/breadth_first_thinning.hh | 42 +++-- 8 files changed, 295 insertions(+), 176 deletions(-) delete mode 100644 milena/mln/topo/detach.hh create mode 100644 milena/mln/topo/detach_cell.hh diff --git a/milena/ChangeLog b/milena/ChangeLog index b95813a..b15ba2a 100644 --- a/milena/ChangeLog +++ b/milena/ChangeLog @@ -1,5 +1,22 @@ 2010-09-09 Roland Levillain &lt;roland(a)lrde.epita.fr&gt; + More generic breadth-first-thinning-based skeleton transformations. + + * mln/topo/is_simple_cell.hh: Make this functor more generic. + * mln/topo/detach: Rename as... + * mln/topo/detach_cell.hh: ...this. + (detach): Turn this function into... + (detach_cell): ...a more generic functor. + * mln/make/attachment.hh (mln::make::attachment) + * mln/make/detachment.hh (mln::make::detachment): + Make these routines more generic. + * mln/topo/skeleton/breadth_first_thinning.hh + (mln::topo::skeleton::breadth_first_thinning): + Adjust. + * headers.mk: Regen. + +2010-09-09 Roland Levillain &lt;roland(a)lrde.epita.fr&gt; + Introduce a helper to build an mln::mutable_extension_ima. * mln/core/routine/mutable_extend.hh: New. diff --git a/milena/headers.mk b/milena/headers.mk index 9a33d4e..c3aedc4 100644 --- a/milena/headers.mk +++ b/milena/headers.mk @@ -996,7 +996,7 @@ mln/topo/center_only_iter.hh \ mln/topo/centered_iter_adapter.hh \ mln/topo/complex.hh \ mln/topo/complex_iterators.hh \ -mln/topo/detach.hh \ +mln/topo/detach_cell.hh \ mln/topo/essential.hh \ mln/topo/face.hh \ mln/topo/face_data.hh \ diff --git a/milena/mln/make/attachment.hh b/milena/mln/make/attachment.hh index 088f9df..3af5332 100644 --- a/milena/mln/make/attachment.hh +++ b/milena/mln/make/attachment.hh @@ -1,4 +1,4 @@ -// Copyright (C) 2009 EPITA Research and Development Laboratory (LRDE) +// Copyright (C) 2009, 2010 EPITA Research and Development Laboratory (LRDE) // // This file is part of Olena. // @@ -43,52 +43,58 @@ namespace mln /** \brief Compute the attachment of the cell corresponding to the facet \a f to the image \a ima. + \param ima The input image to which the facet is attached. + \param f The psite corresponding to the attached facet. + \param nbh An adjacency relationship between faces + (should return the set of (n-1)- and (n+1)-faces + adjacent to an n-face). + + \return A set of faces containing the attachment. + + \pre ima is an image of Boolean values. \pre \a f is a facet (it does not belong to any face of higher dimension). - \pre ima is an image of Boolean values. - - \return a set of faces containing the attachment. We do not use the fomal definition of the attachment here (see couprie.08.pami). We use the following (equivalent) definition: an N-face F in CELL is in the attachment of CELL to IMA if it is adjacent to at least an (N-1)-face or an (N+1)-face that does not belong to CELL. */ - template <unsigned D, typename G, typename V> - p_set< complex_psite<D, G> > - attachment(const complex_psite<D, G>& f, - const complex_image<D, G, V>& ima); + template <typename I, typename N> + p_set<mln_psite(I)> + attachment(const Image<I>& ima, const mln_psite(I)& f, + const Neighborhood<N>& nbh); # ifndef MLN_INCLUDE_ONLY - template <unsigned D, typename G, typename V> + template <typename I, typename N> inline - p_set< complex_psite<D, G> > - attachment(const complex_psite<D, G>& f, - const complex_image<D, G, V>& ima) + p_set<mln_psite(I)> + attachment(const Image<I>& ima_, const mln_psite(I)& f, + const Neighborhood<N>& nbh_) { mln_precondition(topo::is_facet(f)); - mlc_equal(V, bool)::check(); + mlc_equal(mln_value(I), bool)::check(); + + I ima = exact(ima_); + N nbh = exact(nbh_); - typedef complex_psite<D, G> psite; - typedef p_set<psite> faces_t; + typedef p_set<mln_psite(I)> faces_t; faces_t f_hat = make::cell(f); - faces_t att_f; + faces_t attach_f; - typedef complex_lower_higher_neighborhood<D, G> adj_nbh_t; - adj_nbh_t adj_nbh; mln_piter(faces_t) g(f_hat); - mln_niter(adj_nbh_t) n(adj_nbh, g); + mln_niter(N) n(nbh, g); for_all(g) for_all(n) if (ima(n) && !f_hat.has(n)) { - att_f.insert(g); + attach_f.insert(g); break; } - return att_f; + return attach_f; } # endif // MLN_INCLUDE_ONLY diff --git a/milena/mln/make/detachment.hh b/milena/mln/make/detachment.hh index 16a8c92..6cd01ba 100644 --- a/milena/mln/make/detachment.hh +++ b/milena/mln/make/detachment.hh @@ -1,4 +1,4 @@ -// Copyright (C) 2009 EPITA Research and Development Laboratory (LRDE) +// Copyright (C) 2009, 2010 EPITA Research and Development Laboratory (LRDE) // // This file is part of Olena. // @@ -43,12 +43,19 @@ namespace mln /** \brief Compute the detachment of the cell corresponding to the facet \a f from the image \a ima. + \param ima The input image from which the facet is to be + detached. + \param f The psite corresponding to the facet to detach. + \param nbh An adjacency relationship between faces + (should return the set of (n-1)- and (n+1)-faces + adjacent to an n-face). + + \return A set of faces containing the detachment. + \pre \a f is a facet (it does not belong to any face of higher dimension). \pre \a ima is an image of Boolean values. - \return a set of faces containing the detachment. - We do not use the fomal definition of the detachment here (see couprie.08.pami). We use the following (equivalent) definition: an N-face F in CELL is not in the detachment of CELL from IMA if @@ -60,34 +67,34 @@ namespace mln the part that is removed, i.e., the detached part CELL - ATTACHMENT. It would be wise to rename this routine to something else. */ - template <unsigned D, typename G, typename V> - p_set< complex_psite<D, G> > - detachment(const complex_psite<D, G>& f, - const complex_image<D, G, V>& ima); + template <typename I, typename N> + p_set<mln_psite(I)> + detachment(const Image<I>& ima, const mln_psite(I)& f, + const Neighborhood<N>& nbh); # ifndef MLN_INCLUDE_ONLY - template <unsigned D, typename G, typename V> + template <typename I, typename N> inline - p_set< complex_psite<D, G> > - detachment(const complex_psite<D, G>& f, - const complex_image<D, G, V>& ima) + p_set<mln_psite(I)> + detachment(const Image<I>& ima_, const mln_psite(I)& f, + const Neighborhood<N>& nbh_) { mln_precondition(topo::is_facet(f)); - mlc_equal(V, bool)::check(); + mlc_equal(mln_value(I), bool)::check(); + + I ima = exact(ima_); + N nbh = exact(nbh_); - typedef complex_psite<D, G> psite; - typedef p_set<psite> faces_t; + typedef p_set<mln_psite(I)> faces_t; faces_t f_hat = make::cell(f); // Initialize DETACH_F to F_HAT. faces_t detach_f = f_hat; - typedef complex_lower_higher_neighborhood<D, G> adj_nbh_t; - adj_nbh_t adj_nbh; mln_piter(faces_t) g(f_hat); - mln_niter(adj_nbh_t) n(adj_nbh, g); + mln_niter(N) n(nbh, g); for_all(g) for_all(n) if (ima(n) && !f_hat.has(n)) diff --git a/milena/mln/topo/detach.hh b/milena/mln/topo/detach.hh deleted file mode 100644 index 6218739..0000000 --- a/milena/mln/topo/detach.hh +++ /dev/null @@ -1,83 +0,0 @@ -// Copyright (C) 2009 EPITA Research and Development Laboratory (LRDE) -// -// This file is part of Olena. -// -// Olena is free software: you can redistribute it and/or modify it under -// the terms of the GNU General Public License as published by the Free -// Software Foundation, version 2 of the License. -// -// Olena 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 Olena. If not, see <http://www.gnu.org/licenses/>. -// -// As a special exception, you may use this file as part of a free -// software project 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_DETACH_HH -# define MLN_TOPO_DETACH_HH - -/// \file -/// \brief Detaching a cell from a binary complex-based image. - -# include <mln/core/site_set/p_set.hh> -# include <mln/core/image/complex_image.hh> -# include <mln/make/detachment.hh> -# include <mln/topo/is_facet.hh> - -namespace mln -{ - - namespace topo - { - - /** Detach the cell corresponding to \a f from \a ima. - - \pre \a f is a facet (it does not belong to any face of higher - dimension). - \pre \a ima is an image of Boolean values. */ - template <unsigned D, typename G> - void - detach(const complex_psite<D, G>& f, complex_image<D, G, bool>& ima); - - -# ifndef MLN_INCLUDE_ONLY - - template <unsigned D, typename G> - inline - void - detach(const complex_psite<D, G>& f, complex_image<D, G, bool>& ima) - { - mln_precondition(topo::is_facet(f)); - - typedef complex_psite<D, G> psite; - typedef p_set<psite> faces_t; - - // Compute the detachment of P from IMA. - faces_t detach = make::detachment(f, ima); - // Detach all its faces from IMA. -# if 0 - // FIXME: Does not work yet? Check again. - data::fill(ima | detach, false); -# endif - mln_piter(faces_t) p(detach); - for_all(p) - ima(p) = false; - } - -# endif // MLN_INCLUDE_ONLY - - } // end of namespace mln::topo - -} // end of namespace mln - -#endif // ! MLN_TOPO_DETACH_HH diff --git a/milena/mln/topo/detach_cell.hh b/milena/mln/topo/detach_cell.hh new file mode 100644 index 0000000..8a828e4 --- /dev/null +++ b/milena/mln/topo/detach_cell.hh @@ -0,0 +1,157 @@ +// Copyright (C) 2009, 2010 EPITA Research and Development Laboratory (LRDE) +// +// This file is part of Olena. +// +// Olena is free software: you can redistribute it and/or modify it under +// the terms of the GNU General Public License as published by the Free +// Software Foundation, version 2 of the License. +// +// Olena 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 Olena. If not, see <http://www.gnu.org/licenses/>. +// +// As a special exception, you may use this file as part of a free +// software project 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_DETACH_CELL_HH +# define MLN_TOPO_DETACH_CELL_HH + +/// \file +/// \brief Detaching a cell from a binary (probably complex-based) image. + +# include <mln/core/site_set/p_set.hh> +# include <mln/core/image/complex_image.hh> +# include <mln/make/detachment.hh> +# include <mln/topo/is_facet.hh> + +namespace mln +{ + + namespace topo + { + + /** A functor detaching a cell from a binary (probably + complex-based) image. + + \tparam I The type of the image. + \tparam N An neighborhood type corresponding to (directly) + adjacent faces (should return the set of (n-1)- and + (n+1)-faces adjacent to an n-face). */ + template <typename I, typename N> + class detach_cell + { + public: + /// Constructors. + /// \{ + /** Construct an mln::topo::detach_cell from a neighborhood. + + \param nbh An adjacency relationship between faces + (should return the set of (n-1)- and (n+1)-faces + adjacent to an n-face). */ + detach_cell(const Neighborhood<N>& nbh); + + /** Construct an mln::topo::detach_cell from an image and a + neighborhood. + + \pre \a ima is an image of Boolean values. + + \param ima The input image from which the facet is to be + detached. + \param nbh An adjacency relationship between faces + (should return the set of (n-1)- and (n+1)-faces + adjacent to an n-face). */ + detach_cell(mln::Image<I>& ima, const Neighborhood<N>& nbh); + /// \} + + /* FIXME: Rename as init() or something like this? See how other + functors are written. */ + /** Set the underlying image. + + \pre \a ima is an image of Boolean values. */ + void set_image(mln::Image<I>& ima); + + /** Detach the cell corresponding to \a f from \a ima. + + \pre \a f is a facet (it does not belong to any face of + higher dimension). + + \param f The psite corresponding to the facet to detach. + \param nbh An adjacency relationship between faces + (should return the set of (n-1)- and (n+1)-faces + adjacent to an n-face). */ + void + operator()(const mln_psite(I)& f); + + private: + I* ima_; + const N& nbh_; + }; + + + +# ifndef MLN_INCLUDE_ONLY + + template <typename I, typename N> + inline + detach_cell<I, N>::detach_cell(const Neighborhood<N>& nbh) + : ima_(0), nbh_(exact(nbh)) + { + } + + template <typename I, typename N> + inline + detach_cell<I, N>::detach_cell(mln::Image<I>& ima, + const Neighborhood<N>& nbh) + : ima_(exact(&ima)), nbh_(exact(nbh)) + { + mlc_equal(mln_value(I), bool)::check(); + } + + template <typename I, typename N> + inline + void + detach_cell<I, N>::set_image(mln::Image<I>& ima) + { + mlc_equal(mln_value(I), bool)::check(); + ima_ = exact(&ima); + } + + template <typename I, typename N> + inline + void + detach_cell<I, N>::operator()(const mln_psite(I)& f) + { + mln_precondition(ima_); + mln_precondition(topo::is_facet(f)); + + typedef p_set<mln_psite(I)> faces_t; + + // Compute the detachment of P from *IMA_. + faces_t detach = make::detachment(*ima_, f, nbh_); + // Detach all its faces from *IMA_. +# if 0 + // FIXME: Does not work yet? Check again. + data::fill(*ima_ | detach, false); +# endif + mln_piter(faces_t) p(detach); + for_all(p) + (*ima_)(p) = false; + } + +# endif // MLN_INCLUDE_ONLY + + } // end of namespace mln::topo + +} // end of namespace mln + +#endif // ! MLN_TOPO_DETACH_CELL_HH diff --git a/milena/mln/topo/is_simple_cell.hh b/milena/mln/topo/is_simple_cell.hh index a86a8fa..bf60c3d 100644 --- a/milena/mln/topo/is_simple_cell.hh +++ b/milena/mln/topo/is_simple_cell.hh @@ -1,4 +1,4 @@ -// Copyright (C) 2009 EPITA Research and Development Laboratory (LRDE) +// Copyright (C) 2009, 2010 EPITA Research and Development Laboratory (LRDE) // // This file is part of Olena. // @@ -27,7 +27,6 @@ # define MLN_TOPO_IS_SIMPLE_CELL_HH /// \file -/// /// \brief Testing whether a facet is a simple cell. # include <mln/core/concept/function.hh> @@ -48,22 +47,29 @@ namespace mln namespace topo { + /* FIXME: Maybe we could add traits to deduce N from NL and NH (or + the converse). Anyway, the part of the code where neighborhood + are used should be moved into another functor + (`is_collapsible', see below), thus pushing away this + issue. */ + /** \brief A predicate for the simplicity of a point based on the collapse property of the attachment. The functor does not actually take a cell as input, but a face - that is expected to be a D-facet. */ - template <typename I> - class is_simple_cell : public mln::Function_v2b< is_simple_cell<I> > + that is expected to be a D-facet. + + \tparam I The type of the image. + \tparam N The neighborhood type returning the set of + (n-1)- and (n+1)-faces adjacent to a an n-face. + \tparam NL The neighborhood type returning the set of + (n-1)-faces adjacent to a an n-face. + \tparam NH The neighborhood type returning the set of + (n+1)-faces adjacent to a an n-face. */ + template <typename I, typename N, typename NL, typename NH> + class is_simple_cell : public mln::Function_v2b< is_simple_cell<I, N, NL, NH> > { public: - /// Dimension of the image (and therefore of the complex). - static const unsigned D = I::dim; - /// Geometry of the image. - typedef mln_geom(I) G; - /// Psite type. - typedef mln::complex_psite<D, G> psite; - /// Result type of the functor. typedef bool result; @@ -76,8 +82,11 @@ namespace mln void set_image(const mln::Image<I>& ima); /// Based on the algorithm A2 from couprie.08.pami. - bool operator()(const mln::complex_psite<I::dim,mln_geom(I)>& p) const; - // Tech note: The argument type above is explicit to help g++-3.3. + /* FIXME: We probably broke the compatiblity with g++ 3.3, as it + seems this compiler does not like an indirect type like the + one of the following operator's argument. Check and possibly + improve this. */ + bool operator()(const mln_psite(I)& p) const; private: const I* ima_; @@ -87,44 +96,44 @@ namespace mln # ifndef MLN_INCLUDE_ONLY - template <typename I> + template <typename I, typename N, typename NL, typename NH> inline - is_simple_cell<I>::is_simple_cell() + is_simple_cell<I, N, NL, NH>::is_simple_cell() : ima_(0) { } - template <typename I> + template <typename I, typename N, typename NL, typename NH> inline - is_simple_cell<I>::is_simple_cell(const mln::Image<I>& ima) - : ima_(mln::exact(&ima)) + is_simple_cell<I, N, NL, NH>::is_simple_cell(const mln::Image<I>& ima) + : ima_(exact(&ima)) { } - template <typename I> + template <typename I, typename N, typename NL, typename NH> inline void - is_simple_cell<I>::set_image(const mln::Image<I>& ima) + is_simple_cell<I, N, NL, NH>::set_image(const mln::Image<I>& ima) { - ima_ = mln::exact(&ima); + ima_ = exact(&ima); } - template <typename I> + template <typename I, typename N, typename NL, typename NH> inline bool - is_simple_cell<I>::operator()(const mln::complex_psite<I::dim,mln_geom(I)>& p) const - // Tech note: The argument type above is explicit to help g++-3.3. + is_simple_cell<I, N, NL, NH>::operator()(const mln_psite(I)& p) const { mln_precondition(ima_); - typedef p_set<psite> faces_t; + typedef p_set<mln_psite(I)> faces_t; - // Compute the attachment of the cell corresponding to P to he + // Compute the attachment of the cell corresponding to P to the // domain of *IMA_. - faces_t att = make::attachment(p, *ima_); + N adj_nbh; + faces_t att = make::attachment(*ima_, p, adj_nbh); // A cell with an empty attachment is not simple. - /* FIXME: Why does p_set not provide an empty() predicate? */ + /* FIXME: Why p_set does not provide an empty() predicate? */ if (att.nsites() == 0) return false; @@ -134,10 +143,8 @@ namespace mln routine. */ // Try to collapse the attachment (to a single point). { - typedef complex_lower_neighborhood<D, G> lower_adj_nbh_t; - typedef complex_higher_neighborhood<D, G> higher_adj_nbh_t; - lower_adj_nbh_t lower_adj_nbh; - higher_adj_nbh_t higher_adj_nbh; + NL lower_adj_nbh; + NH higher_adj_nbh; while (att.nsites() > 1) { @@ -149,11 +156,11 @@ namespace mln for_all(g) /* G cannot have dimension 0, since we later look for an adjacent face H of lower dimension. */ - if (static_cast<psite>(g).n() > 0) + if (static_cast<mln_psite(I)>(g).n() > 0) { // Check whether G is a facet within ATT. bool g_is_facet = true; - mln_niter(higher_adj_nbh_t) f(higher_adj_nbh, g); + mln_niter(NH) f(higher_adj_nbh, g); for_all(f) if (att.has(f)) { @@ -165,13 +172,13 @@ namespace mln // Look for a face H stricly included in G. bool gh_is_simple_pair = false; - mln_niter(lower_adj_nbh_t) h(lower_adj_nbh, g); + mln_niter(NL) h(lower_adj_nbh, g); for_all(h) { bool h_strictly_in_g = true; if (att.has(h)) { - mln_niter(higher_adj_nbh_t) i(higher_adj_nbh, h); + mln_niter(NH) i(higher_adj_nbh, h); for_all(i) if (i != g && att.has(i)) { diff --git a/milena/mln/topo/skeleton/breadth_first_thinning.hh b/milena/mln/topo/skeleton/breadth_first_thinning.hh index f405166..eb1c212 100644 --- a/milena/mln/topo/skeleton/breadth_first_thinning.hh +++ b/milena/mln/topo/skeleton/breadth_first_thinning.hh @@ -55,15 +55,19 @@ namespace mln A generic implementation of the computation of a skeleton using a breadth-first thinning on a binary. - \param input The input image. - \param nbh The adjacency relation between triangles. - \param is_simple The predicate on the simplicity of points - (sites). This functor must provide a method - <tt>void set_image(const Image<I>&)</tt>. + \param input The input image. + \param nbh The adjacency relation between triangles. + \param is_simple The predicate on the simplicity of points + (sites). This functor must provide a method + <tt>void set_image(const Image<I>&)</tt>. \param detach A function used to detach a cell from \a input. - \param constraint A constraint on point (site); if it - returns \c false for a point, this point - will not be removed. */ + This functor must provide a method + <tt>void set_image(const Image<I>&)</tt>. + \param constraint A constraint on point (site); if it + returns \c false for a point, this point + will not be removed. + + Keywords: skeletons, simple points. */ template <typename I, typename N, typename F, typename G, typename H> mln_concrete(I) breadth_first_thinning(const Image<I>& input, @@ -78,13 +82,16 @@ namespace mln A generic implementation of the computation of a skeleton using a breadth-first thinning on a binary. - \param input The input image. - \param nbh The adjacency relation between triangles. - \param is_simple The predicate on the simplicity of points - (sites). This functor must provide a method - <tt>void set_image(const Image<I>&)</tt>. - \param detach A function used to detach a cell from - \a input. */ + \param input The input image. + \param nbh The adjacency relation between triangles. + \param is_simple The predicate on the simplicity of points + (sites). This functor must provide a method + <tt>void set_image(const Image<I>&)</tt>. + \param detach A function used to detach a cell from \a input. + This functor must provide a method + <tt>void set_image(const Image<I>&)</tt>. + + Keywords: skeletons, simple points. */ template <typename I, typename N, typename F, typename G> mln_concrete(I) breadth_first_thinning(const Image<I>& input, @@ -110,8 +117,9 @@ namespace mln const H& constraint = exact(constraint_); mln_concrete(I) output = duplicate(input); - // Attach the work image to IS_SIMPLE. + // Attach the work image to IS_SIMPLE and DETACH. is_simple.set_image(output); + detach.set_image(output); typedef mln_psite(I) psite; typedef p_set<psite> set_t; @@ -150,7 +158,7 @@ namespace mln given p during the thinning. */ if (constraint(p) && is_simple(p)) { - detach(p, output); + detach(p); mln_niter(N) n_(nbh, p); for_all(n_) { -- 1.5.6.5