* 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(a)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(a)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