* apps/statues/mesh-complex-skel.cc: Split reusable parts into... * mln/make/attachment.hh, * mln/make/cell.hh, * mln/make/detachment.hh, * mln/topo/detach.hh, * mln/topo/is_facet.hh, * mln/topo/is_n_face.hh, * mln/topo/is_simple_cell.hh, * mln/topo/skeleton/breadth_first_thinning.hh: ...these (new) files. --- milena/ChangeLog | 15 + milena/apps/statues/mesh-complex-skel.cc | 441 +------------------- milena/mln/make/attachment.hh | 102 +++++ milena/mln/make/cell.hh | 97 +++++ milena/mln/make/detachment.hh | 103 +++++ milena/mln/topo/detach.hh | 86 ++++ milena/mln/topo/is_facet.hh | 79 ++++ milena/mln/topo/is_n_face.hh | 75 ++++ milena/mln/topo/is_simple_cell.hh | 220 ++++++++++ milena/mln/topo/skeleton/breadth_first_thinning.hh | 156 +++++++ 10 files changed, 949 insertions(+), 425 deletions(-) create mode 100644 milena/mln/make/attachment.hh create mode 100644 milena/mln/make/cell.hh create mode 100644 milena/mln/make/detachment.hh create mode 100644 milena/mln/topo/detach.hh create mode 100644 milena/mln/topo/is_facet.hh create mode 100644 milena/mln/topo/is_n_face.hh create mode 100644 milena/mln/topo/is_simple_cell.hh create mode 100644 milena/mln/topo/skeleton/breadth_first_thinning.hh diff --git a/milena/ChangeLog b/milena/ChangeLog index ce4316d..8b483cf 100644 --- a/milena/ChangeLog +++ b/milena/ChangeLog @@ -1,5 +1,20 @@ 2009-04-07 Roland Levillain &lt;roland(a)lrde.epita.fr&gt; + Split apps/statues/mesh-complex-skel. + + * apps/statues/mesh-complex-skel.cc: Split reusable parts into... + * mln/make/attachment.hh, + * mln/make/cell.hh, + * mln/make/detachment.hh, + * mln/topo/detach.hh, + * mln/topo/is_facet.hh, + * mln/topo/is_n_face.hh, + * mln/topo/is_simple_cell.hh, + * mln/topo/skeleton/breadth_first_thinning.hh: + ...these (new) files. + +2009-04-07 Roland Levillain &lt;roland(a)lrde.epita.fr&gt; + * apps/statues/mesh-complex-skel.cc: Remove dead code. 2009-04-07 Roland Levillain &lt;roland(a)lrde.epita.fr&gt; diff --git a/milena/apps/statues/mesh-complex-skel.cc b/milena/apps/statues/mesh-complex-skel.cc index 7c103b2..85a1581 100644 --- a/milena/apps/statues/mesh-complex-skel.cc +++ b/milena/apps/statues/mesh-complex-skel.cc @@ -30,11 +30,6 @@ /// (triangle) mesh of a statue (by thinning), using a complex-based /// image. -#include <cstdlib> -#include <cmath> - -#include <algorithm> -#include <utility> #include <iostream> #include <mln/core/image/complex_image.hh> @@ -42,431 +37,23 @@ #include <mln/core/site_set/p_set.hh> -#include <mln/pw/value.hh> -#include <mln/pw/cst.hh> - #include <mln/value/label_16.hh> -#include <mln/literal/white.hh> - -#include <mln/core/routine/duplicate.hh> #include <mln/labeling/regional_minima.hh> -#include <mln/morpho/erosion.hh> #include <mln/morpho/closing/area.hh> -#include <mln/fun/p2b/tautology.hh> +#include <mln/topo/is_n_face.hh> +#include <mln/topo/is_simple_cell.hh> +#include <mln/topo/skeleton/breadth_first_thinning.hh> #include <mln/io/off/load.hh> -#include <mln/io/off/save.hh> /* FIXME: Remove as soon as mln::io::off::save is able to save a morphed mln::complex_image (i.e., seen through image_if). */ #include "save_bin_alt.hh" -// FIXME: This is bad. Remove as soon as all routines have been moved -// to the library. -using namespace mln; - - -// FIXME: Doc. -template <unsigned D, typename G> -bool -is_facet(const mln::complex_psite<D, G>& f) -{ - typedef mln::complex_higher_neighborhood<D, G> higher_adj_nbh_t; - higher_adj_nbh_t higher_adj_nbh; - mln_niter(higher_adj_nbh_t) n(higher_adj_nbh, f); - for_all(n) - // If the neighborhood is not empty, then F is included in a face - // of higher dimension. - return false; - // Otherwise, F is a facet. - return true; -} - - -/** \brief Compute the set of faces of the cell corresponding to the - facet \a f. - - \pre \a f is a facet (it does not belong to any face of higher - dimension) - - \return a set of faces containing the attachment. */ -template <unsigned D, typename G> -mln::p_set< complex_psite<D, G> > -cell(const complex_psite<D, G>& f) -{ - // Ensure the face F is a facet. - mln_precondition(is_facet(f)); - - typedef complex_psite<D, G> psite; - typedef p_set<psite> faces_t; - - // Compute the cell F^HAT. - faces_t f_hat; - /* FIXME: We need a cell-iterator here - (see https://trac.lrde.org/olena/ticket/162). */ - typedef complex_m_face_neighborhood<D, G> m_faces_nbh_t; - m_faces_nbh_t m_faces_nbh; - mln_niter(m_faces_nbh_t) g(m_faces_nbh, f); - for (unsigned m = 0; m < f.n(); ++m) - { - g.iter().set_m(m); - for_all(g) - { - f_hat.insert(g); - } - } - f_hat.insert(f); - return f_hat; -} - - -/** \brief Compute the attachment of the cell corresponding to the - facet \a f to the image \a ima. - - \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> -mln::p_set< complex_psite<D, G> > -attachment(const mln::complex_psite<D, G>& f, - const mln::complex_image<D, G, V>& ima) -{ - mlc_equal(V, bool)::check(); - - typedef complex_psite<D, G> psite; - typedef p_set<psite> faces_t; - - faces_t f_hat = cell(f); - faces_t att_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); - for_all(g) - for_all(n) - if (ima(n) && !f_hat.has(n)) - { - att_f.insert(g); - break; - } - return att_f; -} - - -/** \brief Compute the detachment of the cell corresponding to the - facet \a f to the image \a ima. - - \pre 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 - 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> -mln::p_set< complex_psite<D, G> > -detachment(const mln::complex_psite<D, G>& f, - const mln::complex_image<D, G, V>& ima) -{ - mlc_equal(V, bool)::check(); - - typedef complex_psite<D, G> psite; - typedef p_set<psite> faces_t; - - faces_t f_hat = 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); - for_all(g) - for_all(n) - if (ima(n) && !f_hat.has(n)) - { - detach_f.remove(g); - break; - } - return detach_f; -} - - -/** \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 2-facet. */ -template <typename I> -class is_simple_cell - : public mln::Function_p2b< is_simple_cell<I> > -{ -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; - - is_simple_cell() - : ima_(0) - { - } - - is_simple_cell(const mln::Image<I>& ima) - : ima_(mln::exact(&ima)) - { - } - - /* FIXME: Rename as init() or something like this? See how other - functors are written. */ - /// Set the underlying image. - void set_image(const mln::Image<I>& ima) - { - ima_ = mln::exact(&ima); - } - - // Based on the algorithm A2 from couprie.08.pami. - bool operator()(const psite& p) const - { - mln_precondition(ima_); - - typedef p_set<psite> faces_t; - - // Compute the attachment of the cell corresponding to P to he - // domain of *IMA_. - faces_t att = attachment(p, *ima_); - - // A cell with an empty attachment is not simple. - /* FIXME: Why does p_set not provide an empty() predicate? */ - if (att.nsites() == 0) - return false; - - /* FIXME: This part could be moved to its own function/method - (`is_collapsible'). Moreover, the code could be split: looking - up for a free pair (g, h) could be performed in another - 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; - while (att.nsites() > 1) - { - - bool simple_pair_collapsed = false; - /* FIXME: The selection of G and H is probably suboptimal - (i.e., selecting G has a face of highest avalaible - dimension in CELL is probably smarter). */ - mln_piter(faces_t) g(att); - 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) - { - // Check whether G is a facet within ATT. - bool g_is_facet = true; - mln_niter(higher_adj_nbh_t) f(higher_adj_nbh, g); - for_all(f) - if (att.has(f)) - { - g_is_facet = false; - break; - } - if (!g_is_facet) - break; - - // 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); - for_all(h) - { - bool h_strictly_in_g = true; - if (att.has(h)) - { - mln_niter(higher_adj_nbh_t) i(higher_adj_nbh, h); - for_all(i) - if (i != g && att.has(i)) - { - h_strictly_in_g = false; - break; - } - } - if (h_strictly_in_g) - { - gh_is_simple_pair = true; - att.remove(g); - att.remove(h); - mln_invariant(att.nsites() > 0); - break; - } - } // for_all(h) - - // If a free pair (G, H) has been found and removed, - // restart the free pair look up from the beginning. - if (gh_is_simple_pair) - { - simple_pair_collapsed = true; - break; - } - } // for_all(g) - - if (!simple_pair_collapsed) - // If no free pair (G, H) was found, then the attachment is - // not collapsible. - return false; - - } // while (att.nsites() > 1) - - mln_postcondition(att.nsites() == 1); - mln_postcondition(att[0].n() == 0); - // If the attachment is collapsible to a 0-face, then the cell - // corresponding to the (face) P is simple. - return true; - } - } - -private: - const I* ima_; -}; - - -// FIXME: Doc. -template <unsigned D, typename G, typename V> -void -detach (const mln::complex_psite<D, G>f, mln::complex_image<D, G, V>& ima) -{ - mlc_equal(V, bool)::check(); - - typedef mln::complex_psite<D, G> psite; - typedef p_set<psite> faces_t; - - // Compute the detachment of P from IMA. - faces_t detach = 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; -} - - -// FIXME: Move this elsewhere. -// FIXME: Use a generic `I' instead of `mln::bin_2complex_image3df'. -// FIXME: Update doc. -/* FIXME: Rename `constraint' to a verb or adjective? - (validate_constraint? satisfy_constraint? pass_constraint? - is_satisfying?) */ -/** \brief Breadth-First Thinning. - - A non generic implementation of a binary skeleton on a triangle - surface (mesh). - - \a N is the adjacency relation between triangles, but it probably - does not make sense to use something other than an instance of - mln::complex_lower_dim_connected_n_face_neighborhood if the image type is - hard-coded as mln::bin_2complex_image3df. */ -template <typename N, typename F, typename G> -mln::bin_2complex_image3df -skeleton(const mln::bin_2complex_image3df& input, - const mln::Neighborhood<N>& nbh_, - mln::Function_p2b<F>& is_simple_, - const mln::Function_p2b<G>& constraint_ = mln::fun::p2b::tautology()) -{ - const N& nbh = exact(nbh_); - F& is_simple = exact(is_simple_); - const G& constraint = exact(constraint_); - - typedef mln::bin_2complex_image3df I; - typedef mln_psite(I) psite; - - I output = mln::duplicate(input); - // Attach the work image to IS_SIMPLE. - is_simple.set_image(output); - - typedef mln::p_set<psite> set_t; - set_t set; - - // Populate the set with candiate simple points. - mln_piter(I) p_(output.domain()); - for_all(p_) - { - /* CONSTRAINTS and IS_SIMPLE are site-to-boolean (p2b) predicate - functors; passing an iterator as argument might not be possible - (C++ cannot resolve template routines if an implicit conversion - of the argument is needed). Help the compiler and pass an - actual, explicit psite. */ - psite p = p_; - if (output(p) && constraint(p) && is_simple(p)) - set.insert(p); - } - - while (!set.is_empty()) - { - set_t next_set; - // FIXME: Use a piter on SET instead of this hand-made iteration. - for (unsigned i = 0; i < set.nsites(); ++i) - { - psite p = set[i]; - /* FIXME: We compute the cell and attachment of P twice: - within is_simple and within detach. How could we reuse - this elegantly, without breaking the genericity of the - skeleton algorithm? */ - if (constraint(p) && is_simple(p)) - { - // FIXME: `detach' could be a functor, as is `is_simple'. - detach(p, output); - mln_niter(N) n(nbh, p); - for_all(n) - if (output.domain().has(n) - && output(n) && constraint(p) && is_simple(n)) - next_set.insert(n); - } - } - set.clear(); - std::swap(set, next_set); - } - return output; -} - - -// Fwd. decl. -template <unsigned N> struct is_n_face; - -/// A functor testing wheter a mln::complex_psite is an \N-face. -template <unsigned N> -struct is_n_face : public mln::Function_p2b< is_n_face<N> > -{ - typedef bool result; - - template <unsigned D, typename G> - bool operator()(const mln::complex_psite<D, G>& p) const - { - return p.n() == N; - } -}; - - -int main(int argc, char* argv[]) +int +main(int argc, char* argv[]) { if (argc != 4) { @@ -476,7 +63,6 @@ int main(int argc, char* argv[]) } std::string input_filename = argv[1]; - // FIXME: Use lambda to filter the input. unsigned lambda = atoi(argv[2]); std::string output_filename = argv[3]; @@ -601,14 +187,19 @@ int main(int argc, char* argv[]) | Skeleton. | `-----------*/ - is_simple_cell<bin_ima_t> is_simple_p; + mln::topo::is_simple_cell<bin_ima_t> is_simple_p; /* FIXME: Cheat! We'd like to iterate on cells of highest dimension (2-cells) only, but we cannot constrain the domain of - the input using image_if (yet). As a workaround, we use the - constraint predicate of the skeleton routine to restrict the - iteration to 2-cells. */ - is_n_face<bin_ima_t::dim> constraint; - bin_ima_t skel = skeleton(surface, nbh, is_simple_p, constraint); + the input using image_if (yet) like this + + breadth_first_thinning(surface | is_n_face<2>, nbh, is_simple_p); + + As a workaround, we use the constraint predicate of the + skeleton routine to restrict the iteration to 2-cells. */ + mln::topo::is_n_face<bin_ima_t::dim> constraint_p; + bin_ima_t skel = + mln::topo::skeleton::breadth_first_thinning(surface, nbh, is_simple_p, + constraint_p); /*---------. | Output. | diff --git a/milena/mln/make/attachment.hh b/milena/mln/make/attachment.hh new file mode 100644 index 0000000..6ac056b --- /dev/null +++ b/milena/mln/make/attachment.hh @@ -0,0 +1,102 @@ +// 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_MAKE_ATTACHMENT_HH +# define MLN_MAKE_ATTACHMENT_HH + +/// \file mln/make/attachment.hh +/// \brief Compute the attachment of a cell to a binary +/// complex-based image. + +# include <mln/core/image/complex_image.hh> +# include <mln/make/cell.hh> +# include <mln/topo/is_facet.hh> + +namespace mln +{ + + namespace make + { + + /** \brief Compute the attachment of the cell corresponding to the + facet \a f to the image \a ima. + + \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); + + +# ifndef MLN_INCLUDE_ONLY + + template <unsigned D, typename G, typename V> + inline + p_set< complex_psite<D, G> > + attachment(const complex_psite<D, G>& f, + const complex_image<D, G, V>& ima) + { + mln_precondition(topo::is_facet(f)); + mlc_equal(V, bool)::check(); + + typedef complex_psite<D, G> psite; + typedef p_set<psite> faces_t; + + faces_t f_hat = make::cell(f); + faces_t att_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); + for_all(g) + for_all(n) + if (ima(n) && !f_hat.has(n)) + { + att_f.insert(g); + break; + } + return att_f; + } + +# endif // MLN_INCLUDE_ONLY + + } // end of namespace mln::make + +} // end of namespace mln + +#endif // ! MLN_MAKE_ATTACHMENT_HH diff --git a/milena/mln/make/cell.hh b/milena/mln/make/cell.hh new file mode 100644 index 0000000..2f5a187 --- /dev/null +++ b/milena/mln/make/cell.hh @@ -0,0 +1,97 @@ +// 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_MAKE_CELL_HH +# define MLN_MAKE_CELL_HH + +/// \file mln/topo/is_facet.hh +/// \brief Computing the set of faces of the cell. + +# include <mln/core/site_set/p_set.hh> +# include <mln/core/site_set/complex_psite.hh> +# include <mln/core/image/complex_neighborhoods.hh> +# include <mln/core/image/complex_neighborhood_piter.hh> + +# include <mln/topo/is_facet.hh> + +namespace mln +{ + + namespace make + { + + /** Compute the set of faces of the cell corresponding to the + facet \a f. + + \pre \a f is a facet (it does not belong to any face of higher + dimension). + + \return An mln::p_set of sites (faces) containing the + attachment. */ + template <unsigned D, typename G> + p_set< complex_psite<D, G> > + cell(const complex_psite<D, G>& f); + + +# ifndef MLN_INCLUDE_ONLY + + template <unsigned D, typename G> + inline + p_set< complex_psite<D, G> > + cell(const complex_psite<D, G>& f) + { + mln_precondition(topo::is_facet(f)); + + typedef complex_psite<D, G> psite; + typedef p_set<psite> faces_t; + + // Compute the cell F^HAT. + faces_t f_hat; + /* FIXME: We need a cell-iterator here + (see https://trac.lrde.org/olena/ticket/162). */ + typedef complex_m_face_neighborhood<D, G> m_faces_nbh_t; + m_faces_nbh_t m_faces_nbh; + mln_niter(m_faces_nbh_t) g(m_faces_nbh, f); + for (unsigned m = 0; m < f.n(); ++m) + { + g.iter().set_m(m); + for_all(g) + { + f_hat.insert(g); + } + } + f_hat.insert(f); + return f_hat; + } + +# endif // MLN_INCLUDE_ONLY + + } // end of namespace mln::make + +} // end of namespace mln + +#endif // ! MLN_TOPO_IS_FACET_HH diff --git a/milena/mln/make/detachment.hh b/milena/mln/make/detachment.hh new file mode 100644 index 0000000..c709a06 --- /dev/null +++ b/milena/mln/make/detachment.hh @@ -0,0 +1,103 @@ +// 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_MAKE_DETACHMENT_HH +# define MLN_MAKE_DETACHMENT_HH + +/// \file mln/make/detachment.hh +/// \brief Compute the detachment of a cell w.r.t. from a binary +/// complex-based image. + +# include <mln/core/image/complex_image.hh> +# include <mln/make/cell.hh> +# include <mln/topo/is_facet.hh> + +namespace mln +{ + + namespace make + { + + /** \brief Compute the detachment of the cell corresponding to the + facet \a f to the image \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. + + \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 + 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> > + detachment(const complex_psite<D, G>& f, + const complex_image<D, G, V>& ima); + + +# ifndef MLN_INCLUDE_ONLY + + template <unsigned D, typename G, typename V> + inline + p_set< complex_psite<D, G> > + detachment(const complex_psite<D, G>& f, + const complex_image<D, G, V>& ima) + { + mln_precondition(topo::is_facet(f)); + mlc_equal(V, bool)::check(); + + typedef complex_psite<D, G> psite; + typedef p_set<psite> 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); + for_all(g) + for_all(n) + if (ima(n) && !f_hat.has(n)) + { + detach_f.remove(g); + break; + } + return detach_f; + } + +# endif // MLN_INCLUDE_ONLY + + } // end of namespace mln::make + +} // end of namespace mln + +#endif // ! MLN_MAKE_DETACHMENT_HH diff --git a/milena/mln/topo/detach.hh b/milena/mln/topo/detach.hh new file mode 100644 index 0000000..e80a8a9 --- /dev/null +++ b/milena/mln/topo/detach.hh @@ -0,0 +1,86 @@ +// 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_DETACH_HH +# define MLN_TOPO_DETACH_HH + +/// \file mln/topo/detach.hh +/// \brief Detachin 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, typename V> + void + detach(const complex_psite<D, G>& f, complex_image<D, G, V>& ima); + + +# ifndef MLN_INCLUDE_ONLY + + template <unsigned D, typename G, typename V> + inline + void + detach(const complex_psite<D, G>& f, complex_image<D, G, V>& ima) + { + mln_precondition(topo::is_facet(f)); + mlc_equal(V, bool)::check(); + + 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/is_facet.hh b/milena/mln/topo/is_facet.hh new file mode 100644 index 0000000..8f6f33f --- /dev/null +++ b/milena/mln/topo/is_facet.hh @@ -0,0 +1,79 @@ +// 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_IS_FACET_HH +# define MLN_TOPO_IS_FACET_HH + +/// \file mln/topo/is_facet.hh +/// \brief Testing whether an mln::complex_psite is a facet. + +# include <mln/core/site_set/complex_psite.hh> +# include <mln/core/image/complex_neighborhoods.hh> +# include <mln/core/image/complex_neighborhood_piter.hh> + + +namespace mln +{ + + namespace topo + { + + /* FIXME: Make this routine a method of mln::complex_psite? Or + better, a method of mln::topo::face? */ + + /// Is \a f a facet, i.e., a face not ``included in'' (adjacent + /// to) a face of higher dimension? + template <unsigned D, typename G> + bool + is_facet(const complex_psite<D, G>& f); + + +# ifndef MLN_INCLUDE_ONLY + + template <unsigned D, typename G> + inline + bool + is_facet(const complex_psite<D, G>& f) + { + typedef complex_higher_neighborhood<D, G> higher_adj_nbh_t; + higher_adj_nbh_t higher_adj_nbh; + mln_niter(higher_adj_nbh_t) n(higher_adj_nbh, f); + for_all(n) + // If the neighborhood is not empty, then F is included in a face + // of higher dimension. + return false; + // Otherwise, F is a facet. + return true; + } + +# endif // MLN_INCLUDE_ONLY + + } // end of namespace mln::topo + +} // end of namespace mln + +#endif // ! MLN_TOPO_IS_FACET_HH diff --git a/milena/mln/topo/is_n_face.hh b/milena/mln/topo/is_n_face.hh new file mode 100644 index 0000000..33bce33 --- /dev/null +++ b/milena/mln/topo/is_n_face.hh @@ -0,0 +1,75 @@ +// 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_IS_N_FACE_HH +# define MLN_TOPO_IS_N_FACE_HH + +/// \file mln/topo/is_facet.hh +/// \brief Testing whether an mln::complex_psite is an n-face. + +# include <mln/core/site_set/complex_psite.hh> +# include <mln/core/image/complex_neighborhoods.hh> +# include <mln/core/image/complex_neighborhood_piter.hh> + +namespace mln +{ + + namespace topo + { + + // Forward declaration. + template <unsigned N> struct is_n_face; + + /// A functor testing wheter a mln::complex_psite is an \N-face. + template <unsigned N> + struct is_n_face : public mln::Function_p2b< is_n_face<N> > + { + typedef bool result; + + template <unsigned D, typename G> + bool operator()(const mln::complex_psite<D, G>& p) const; + }; + + +# ifndef MLN_INCLUDE_ONLY + + template <unsigned N> + template <unsigned D, typename G> + inline + bool + is_n_face<N>::operator()(const mln::complex_psite<D, G>& p) const + { + return p.n() == N; + } + +# endif // MLN_INCLUDE_ONLY + + } // end of namespace mln::topo + +} // end of namespace mln + +#endif // ! MLN_TOPO_IS_N_FACE_HH diff --git a/milena/mln/topo/is_simple_cell.hh b/milena/mln/topo/is_simple_cell.hh new file mode 100644 index 0000000..f81b7cc --- /dev/null +++ b/milena/mln/topo/is_simple_cell.hh @@ -0,0 +1,220 @@ +// 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_IS_SIMPLE_CELL_HH +# define MLN_TOPO_IS_SIMPLE_CELL_HH + +/// \file mln/topo/is_simple_cell.hh +/// \brief Testing whether a facet is a simple cell. + +# include <mln/core/concept/function.hh> +# include <mln/core/concept/image.hh> + +# include <mln/core/site_set/p_set.hh> +# include <mln/core/site_set/complex_psite.hh> +# include <mln/core/site_set/p_complex_piter.hh> +# include <mln/core/image/complex_neighborhoods.hh> +# include <mln/core/image/complex_neighborhood_piter.hh> + +# include <mln/make/attachment.hh> + +namespace mln +{ + + namespace topo + { + + /** \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_p2b< is_simple_cell<I> > + { + 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; + + is_simple_cell(); + is_simple_cell(const mln::Image<I>& ima); + + /* FIXME: Rename as init() or something like this? See how other + functors are written. */ + /// Set the underlying image. + void set_image(const mln::Image<I>& ima); + + /// Based on the algorithm A2 from couprie.08.pami. + bool operator()(const psite& p) const; + + private: + const I* ima_; + }; + + + +# ifndef MLN_INCLUDE_ONLY + + template <typename I> + inline + is_simple_cell<I>::is_simple_cell() + : ima_(0) + { + } + + template <typename I> + inline + is_simple_cell<I>::is_simple_cell(const mln::Image<I>& ima) + : ima_(mln::exact(&ima)) + { + } + + template <typename I> + inline + void + is_simple_cell<I>::set_image(const mln::Image<I>& ima) + { + ima_ = mln::exact(&ima); + } + + template <typename I> + inline + bool + is_simple_cell<I>::operator()(const is_simple_cell<I>::psite& p) const + { + mln_precondition(ima_); + + typedef p_set<psite> faces_t; + + // Compute the attachment of the cell corresponding to P to he + // domain of *IMA_. + faces_t att = make::attachment(p, *ima_); + + // A cell with an empty attachment is not simple. + /* FIXME: Why does p_set not provide an empty() predicate? */ + if (att.nsites() == 0) + return false; + + /* FIXME: This part could be moved to its own function/method + (`is_collapsible'). Moreover, the code could be split: looking + up for a free pair (g, h) could be performed in another + 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; + while (att.nsites() > 1) + { + + bool simple_pair_collapsed = false; + /* FIXME: The selection of G and H is probably suboptimal + (i.e., selecting G has a face of highest avalaible + dimension in CELL is probably smarter). */ + mln_piter(faces_t) g(att); + 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) + { + // Check whether G is a facet within ATT. + bool g_is_facet = true; + mln_niter(higher_adj_nbh_t) f(higher_adj_nbh, g); + for_all(f) + if (att.has(f)) + { + g_is_facet = false; + break; + } + if (!g_is_facet) + break; + + // 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); + for_all(h) + { + bool h_strictly_in_g = true; + if (att.has(h)) + { + mln_niter(higher_adj_nbh_t) i(higher_adj_nbh, h); + for_all(i) + if (i != g && att.has(i)) + { + h_strictly_in_g = false; + break; + } + } + if (h_strictly_in_g) + { + gh_is_simple_pair = true; + att.remove(g); + att.remove(h); + mln_invariant(att.nsites() > 0); + break; + } + } // for_all(h) + + // If a free pair (G, H) has been found and removed, + // restart the free pair look up from the beginning. + if (gh_is_simple_pair) + { + simple_pair_collapsed = true; + break; + } + } // for_all(g) + + if (!simple_pair_collapsed) + // If no free pair (G, H) was found, then the attachment is + // not collapsible. + return false; + + } // while (att.nsites() > 1) + + mln_postcondition(att.nsites() == 1); + mln_postcondition(att[0].n() == 0); + // If the attachment is collapsible to a 0-face, then the cell + // corresponding to the (face) P is simple. + return true; + } + } + +# endif // MLN_INCLUDE_ONLY + + } // end of namespace mln::topo + +} // end of namespace mln + +#endif // ! MLN_TOPO_IS_SIMPLE_CELL_HH diff --git a/milena/mln/topo/skeleton/breadth_first_thinning.hh b/milena/mln/topo/skeleton/breadth_first_thinning.hh new file mode 100644 index 0000000..ee4c5f2 --- /dev/null +++ b/milena/mln/topo/skeleton/breadth_first_thinning.hh @@ -0,0 +1,156 @@ +// 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_BREADTH_FIRST_THINNING_HH +# define MLN_TOPO_SKELETON_BREADTH_FIRST_THINNING_HH + +/// \file mln/topo/skeleton/breadth_first_thinning.hh +/// \brief Computing a skeleton by using breadth-first thinning on a +/// binary image. + +# include <algorithm> + +# include <mln/core/routine/duplicate.hh> + +# include <mln/core/site_set/p_set.hh> +# include <mln/core/alias/complex_image.hh> +# include <mln/topo/detach.hh> + +# include <mln/fun/p2b/tautology.hh> + +namespace mln +{ + + namespace topo + { + + namespace skeleton + { + + /* FIXME: Use a generic `I' instead of + `mln::bin_2complex_image3df', and adjust the + documentation. */ + + /* FIXME: Rename `constraint' to a verb or adjective? + (validate_constraint? satisfy_constraint? pass_constraint? + is_satisfying?) */ + + /** \brief Breadth-First Thinning. + + A semi-generic implementation of a binary skeleton on a triangle + surface (mesh). + + \param input The input image. + \param nbh The adjacency relation between triangles. + \param is_simple The predicate on the simplicity of points (sites). + \param constraint A constraint on point (site); if it + returns \c false for a point, this point + will not be removed. */ + template <typename N, typename F, typename G> + bin_2complex_image3df + breadth_first_thinning(const bin_2complex_image3df& input, + const Neighborhood<N>& nbh, + Function_p2b<F>& is_simple, + const Function_p2b<G>& constraint = + fun::p2b::tautology()); + + +# ifndef MLN_INCLUDE_ONLY + + template <typename N, typename F, typename G> + inline + bin_2complex_image3df + breadth_first_thinning(const bin_2complex_image3df& input, + const Neighborhood<N>& nbh_, + Function_p2b<F>& is_simple_, + const Function_p2b<G>& constraint_) + { + const N& nbh = exact(nbh_); + F& is_simple = exact(is_simple_); + const G& constraint = exact(constraint_); + + typedef bin_2complex_image3df I; + typedef mln_psite(I) psite; + + I output = duplicate(input); + // Attach the work image to IS_SIMPLE. + is_simple.set_image(output); + + typedef p_set<psite> set_t; + set_t set; + + // Populate the set with candiate simple points. + mln_piter(I) p_(output.domain()); + for_all(p_) + { + /* CONSTRAINTS and IS_SIMPLE are site-to-boolean (p2b) + predicate functors; passing an iterator as argument might + not be possible (C++ cannot resolve template routines if + an implicit conversion of the argument is needed). Help + the compiler and pass an actual, explicit psite. */ + psite p = p_; + if (output(p) && constraint(p) && is_simple(p)) + set.insert(p); + } + + while (!set.is_empty()) + { + set_t next_set; + // FIXME: Use a piter on SET instead of this hand-made iteration. + for (unsigned i = 0; i < set.nsites(); ++i) + { + psite p = set[i]; + /* FIXME: We compute the cell and attachment of P + twice: within is_simple and within detach. How + could we reuse this elegantly, without breaking the + genericity of the skeleton algorithm? */ + if (constraint(p) && is_simple(p)) + { + // FIXME: `detach' could be a functor, as is `is_simple'. + topo::detach(p, output); + mln_niter(N) n(nbh, p); + for_all(n) + if (output.domain().has(n) + && output(n) && constraint(p) && is_simple(n)) + next_set.insert(n); + } + } + set.clear(); + std::swap(set, next_set); + } + return output; + } + +# endif // MLN_INCLUDE_ONLY + + } // end of namespace mln::topo::skeleton + + } // end of namespace mln::topo + +} // end of namespace mln + +#endif // ! MLN_TOPO_SKELETON_BREADTH_FIRST_THINNING_HH -- 1.6.1.2