* mln/topo/skeleton/priority_driven_thinning.hh: New. * headers.mk: Regen. --- milena/ChangeLog | 7 + milena/headers.mk | 1 + ...rst_thinning.hh => priority_driven_thinning.hh} | 144 ++++++++++---------- 3 files changed, 81 insertions(+), 71 deletions(-) copy milena/mln/topo/skeleton/{breadth_first_thinning.hh => priority_driven_thinning.hh} (54%) diff --git a/milena/ChangeLog b/milena/ChangeLog index f0bb818..b41024f 100644 --- a/milena/ChangeLog +++ b/milena/ChangeLog @@ -1,5 +1,12 @@ 2010-09-15 Roland Levillain <roland@lrde.epita.fr> + New skeletonization algorithm: priority-driven thinning. + + * mln/topo/skeleton/priority_driven_thinning.hh: New. + * headers.mk: Regen. + +2010-09-15 Roland Levillain <roland@lrde.epita.fr> + Add helpers to compute skeletons by thinning on regular 2D images. * mln/topo/is_simple_point2d.hh, diff --git a/milena/headers.mk b/milena/headers.mk index a4314f5..fd6169c 100644 --- a/milena/headers.mk +++ b/milena/headers.mk @@ -1016,6 +1016,7 @@ mln/topo/n_faces_set.hh \ mln/topo/skeleton/breadth_first_thinning.hh \ mln/topo/skeleton/crest.hh \ mln/topo/skeleton/is_simple_point.hh \ +mln/topo/skeleton/priority_driven_thinning.hh \ mln/topo/static_n_face_iter.hh \ mln/trace/all.hh \ mln/trace/entering.hh \ diff --git a/milena/mln/topo/skeleton/breadth_first_thinning.hh b/milena/mln/topo/skeleton/priority_driven_thinning.hh similarity index 54% copy from milena/mln/topo/skeleton/breadth_first_thinning.hh copy to milena/mln/topo/skeleton/priority_driven_thinning.hh index 3be9539..f074b6a 100644 --- a/milena/mln/topo/skeleton/breadth_first_thinning.hh +++ b/milena/mln/topo/skeleton/priority_driven_thinning.hh @@ -23,11 +23,11 @@ // 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 +#ifndef MLN_TOPO_SKELETON_PRIORITY_DRIVEN_THINNING_HH +# define MLN_TOPO_SKELETON_PRIORITY_DRIVEN_THINNING_HH /// \file -/// \brief Computing a skeleton by using breadth-first thinning on a +/// \brief Computing a skeleton by using priority-driven thinning on a /// binary image. # include <algorithm> @@ -37,7 +37,8 @@ # include <mln/core/concept/image.hh> # include <mln/core/concept/neighborhood.hh> -# include <mln/core/site_set/p_set.hh> +# include <mln/core/site_set/p_queue_fast.hh> +# include <mln/core/site_set/p_priority.hh> # include <mln/fun/p2b/tautology.hh> @@ -50,10 +51,10 @@ namespace mln namespace skeleton { - /** \brief Skeleton by Breadth-First Thinning. + /** \brief Skeleton by Priority-Driven Thinning. A generic implementation of the computation of a skeleton - using a breadth-first thinning on a binary image. + using a priority-driven thinning on a binary image. \param input The input image. \param nbh The adjacency relation between triangles. @@ -61,22 +62,25 @@ 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. + \param priority A priority function expressed as an image. \param constraint A constraint on point (site); if it returns \c false for a point, this point will not be removed. */ - template <typename I, typename N, typename F, typename G, typename H> + template <typename I, typename N, typename F, typename G, typename J, + typename H> mln_concrete(I) - breadth_first_thinning(const Image<I>& input, - const Neighborhood<N>& nbh, - Function_v2b<F>& is_simple, - G detach, - const Function_v2b<H>& constraint); + priority_driven_thinning(const Image<I>& input, + const Neighborhood<N>& nbh, + Function_v2b<F>& is_simple, + G detach, + const Image<J>& priority, + const Function_v2b<H>& constraint); - /** \brief Skeleton by Breadth-First Thinning with no constraint. + /** \brief Skeleton by Priority-Driven Thinning with no constraint. A generic implementation of the computation of a skeleton - using a breadth-first thinning on a binary image. + using a priority-driven thinning on a binary image. \param input The input image. \param nbh The adjacency relation between triangles. @@ -84,31 +88,36 @@ 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. */ - template <typename I, typename N, typename F, typename G> + \a input. + \param priority A priority function expressed as an image. */ + template <typename I, typename N, typename F, typename G, typename J> mln_concrete(I) - breadth_first_thinning(const Image<I>& input, - const Neighborhood<N>& nbh, - Function_v2b<F>& is_simple, - G detach); + priority_driven_thinning(const Image<I>& input, + const Neighborhood<N>& nbh, + Function_v2b<F>& is_simple, + G detach, + const Image<J>& priority); # ifndef MLN_INCLUDE_ONLY - template <typename I, typename N, typename F, typename G, typename H> + template <typename I, typename N, typename F, typename G, typename J, + typename H> inline mln_concrete(I) - breadth_first_thinning(const Image<I>& input_, - const Neighborhood<N>& nbh_, - Function_v2b<F>& is_simple_, - G detach, - const Function_v2b<H>& constraint_) + priority_driven_thinning(const Image<I>& input_, + const Neighborhood<N>& nbh_, + Function_v2b<F>& is_simple_, + G detach, + const Image<J>& priority_, + const Function_v2b<H>& constraint_) { - trace::entering("topo::skeleton::breadth_first_thinning"); + trace::entering("topo::skeleton::priority_driven_thinning"); const I& input = exact(input_); const N& nbh = exact(nbh_); F& is_simple = exact(is_simple_); + const J& priority = exact(priority_); const H& constraint = exact(constraint_); mln_concrete(I) output = duplicate(input); @@ -116,9 +125,10 @@ namespace mln is_simple.set_image(output); typedef mln_psite(I) psite; - typedef p_set<psite> set_t; - set_t set; - // Populate SET with candidate simple points. + typedef p_queue_fast<psite> queue_t; + typedef p_priority<mln_value(J), queue_t> p_queue_t; + p_queue_t p_queue; + // Populate P_QUEUE with candidate simple points. mln_piter(I) p_(output.domain()); for_all(p_) { @@ -129,60 +139,52 @@ namespace mln the compiler and pass an actual, explicit psite. */ psite p = p_; if (output(p) && constraint(p) && is_simple(p)) - set.insert(p); + p_queue.push(priority(p), p); } - while (!set.is_empty()) + while (!p_queue.is_empty()) { - set_t next_set; - - mln_piter(set_t) ps(set); - for_all(ps) - { - // Same remark as above. - psite p = ps; - - /* FIXME: We compute the cell and attachment of P twice: - during the call to is_simple() and within detach(). - How could we reuse this elegantly, without breaking - the genericity of the skeleton algorithm? - Also, keep in mind that functors can maintain an - internal state and make side effects, meaning that - e.g. constraint(p) might not be constant for a - given p during the thinning. */ - if (output(p) && constraint(p) && is_simple(p)) + psite p = p_queue.pop_front(); + + /* FIXME: We compute the cell and attachment of P twice: + during the call to is_simple() and within detach(). + How could we reuse this elegantly, without breaking + the genericity of the skeleton algorithm? + Also, keep in mind that functors can maintain an + internal state and make side effects, meaning that + e.g. constraint(p) might not be constant for a + given p during the thinning. */ + if (output(p) && constraint(p) && is_simple(p)) + { + detach(p, output); + mln_niter(N) n_(nbh, p); + for_all(n_) { - detach(p, output); - mln_niter(N) n_(nbh, p); - for_all(n_) - { - // Same remark as above regarding P and P_. - psite n = n_; - if (output.domain().has(n) - && output(n) && constraint(n) && is_simple(n)) - next_set.insert(n); - } + // Same remark as above regarding P and P_. + psite n = n_; + if (output.domain().has(n) + && output(n) && constraint(n) && is_simple(n)) + p_queue.push(priority(n), n); } - } - set.clear(); - std::swap(set, next_set); + } } - trace::exiting("topo::skeleton::breadth_first_thinning"); + trace::exiting("topo::skeleton::priority_driven_thinning"); return output; } - template <typename I, typename N, typename F, typename G> + template <typename I, typename N, typename F, typename G, typename J> inline mln_concrete(I) - breadth_first_thinning(const Image<I>& input, - const Neighborhood<N>& nbh, - Function_v2b<F>& is_simple, - G detach) + priority_driven_thinning(const Image<I>& input, + const Neighborhood<N>& nbh, + Function_v2b<F>& is_simple, + G detach, + const Image<J>& priority) { - return breadth_first_thinning(input, nbh, is_simple, detach, - fun::p2b::tautology()); + return priority_driven_thinning(input, nbh, is_simple, detach, + priority, fun::p2b::tautology()); } # endif // MLN_INCLUDE_ONLY @@ -193,4 +195,4 @@ namespace mln } // end of namespace mln -#endif // ! MLN_TOPO_SKELETON_BREADTH_FIRST_THINNING_HH +#endif // ! MLN_TOPO_SKELETON_PRIORITY_DRIVEN_THINNING_HH -- 1.5.6.5