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

* mln/topo/is_simple_cell.hh: Make this functor more generic. * mln/topo/detach_cell.hh (detach): Turn this function into 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 | 15 +++ milena/mln/make/attachment.hh | 48 +++++---- milena/mln/make/detachment.hh | 41 +++++--- milena/mln/topo/detach_cell.hh | 107 ++++++++++++++++--- milena/mln/topo/is_simple_cell.hh | 81 ++++++++------- milena/mln/topo/skeleton/breadth_first_thinning.hh | 18 +++- 6 files changed, 213 insertions(+), 97 deletions(-) diff --git a/milena/ChangeLog b/milena/ChangeLog index c0a7088..bff25d3 100644 --- a/milena/ChangeLog +++ b/milena/ChangeLog @@ -1,5 +1,20 @@ 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_cell.hh (detach): Turn this function into 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/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_cell.hh b/milena/mln/topo/detach_cell.hh index dfc4fb5..9e2a489 100644 --- a/milena/mln/topo/detach_cell.hh +++ b/milena/mln/topo/detach_cell.hh @@ -27,7 +27,7 @@ # define MLN_TOPO_DETACH_CELL_HH /// \file -/// \brief Detaching a cell from a binary complex-based image. +/// \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> @@ -40,38 +40,111 @@ namespace mln namespace topo { - /** Detach the cell corresponding to \a f from \a ima. + /** A functor detaching a cell from a binary (probably + complex-based) image. - \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_cell(const complex_psite<D, G>& f, complex_image<D, G, bool>& ima); + \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 <unsigned D, typename G> + 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(const complex_psite<D, G>& f, complex_image<D, G, bool>& ima) + detach_cell<I, N>::operator()(const mln_psite(I)& f) { + mln_precondition(ima_); mln_precondition(topo::is_facet(f)); - typedef complex_psite<D, G> psite; - typedef p_set<psite> faces_t; + typedef p_set<mln_psite(I)> faces_t; - // Compute the detachment of P from IMA. - faces_t detach = make::detachment(f, ima); - // Detach all its faces from IMA. + // 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); + data::fill(*ima_ | detach, false); # endif mln_piter(faces_t) p(detach); for_all(p) - ima(p) = false; + (*ima_)(p) = false; } # endif // MLN_INCLUDE_ONLY 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 7401bae..121c159 100644 --- a/milena/mln/topo/skeleton/breadth_first_thinning.hh +++ b/milena/mln/topo/skeleton/breadth_first_thinning.hh @@ -61,9 +61,13 @@ namespace mln (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>. \param constraint A constraint on point (site); if it returns \c false for a point, this point - will not be removed. */ + 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, @@ -83,8 +87,11 @@ namespace mln \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 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, @@ -112,8 +119,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_queue_fast<psite> queue_t; @@ -131,7 +139,7 @@ namespace mln psite p = queue.pop_front(); if (output(p) && constraint(p) && is_simple(p)) { - detach(p, output); + detach(p); mln_niter(N) n(nbh, p); for_all(n) { -- 1.5.6.5