URL:
https://svn.lrde.epita.fr/svn/oln/trunk/milena
ChangeLog:
2007-11-12 Matthieu Garrigues <garrigues(a)lrde.epita.fr>
Clean and optimise FLLT.
* sandbox/garrigues/fllt_doc.hh: New, Notes for FLLT.
* sandbox/garrigues/fllt_merge.hh: New, merge algorithm.
* sandbox/garrigues/fllt_optimized.hh: Update.
* sandbox/garrigues/fllt_types.hh: New, types used in FLLT.
* sandbox/garrigues/level_set.hh: New, compute lower/upper level set
algorithm
* sandbox/garrigues/lower.hh: New, informations about how to compute
the lower level set.
* sandbox/garrigues/upper.hh: New, informations about how to compute
the lower level set.
* sandbox/garrigues/test_fllt12.cc: Cleaning, (fllt2.hh) replaced by...
(fllt_optimized.hh) ...this.
* sandbox/garrigues/test_fllt13.cc: Likewise.
* sandbox/garrigues/test_fllt2.cc: Likewise.
* sandbox/garrigues/test_fllt3.cc: Likewise.
* sandbox/garrigues/test_fllt_lena_tiles.cc: Likewise.
* mln/util/branch_iter_ind.hh: Check if the tree has not
been subject to updates which can invalidate the iterator.
* sandbox/garrigues/fllt2.hh: (set_p) replaced by...
{p_set} ...this.
---
mln/util/branch_iter_ind.hh | 3
sandbox/garrigues/fllt2.hh | 48 -
sandbox/garrigues/fllt_doc.hh | 86 +++
sandbox/garrigues/fllt_merge.hh | 200 +++++++
sandbox/garrigues/fllt_optimized.hh | 800 +-----------------------------
sandbox/garrigues/fllt_types.hh | 71 ++
sandbox/garrigues/level_set.hh | 463 +++++++++++++++++
sandbox/garrigues/lower.hh | 89 +++
sandbox/garrigues/test_fllt12.cc | 11
sandbox/garrigues/test_fllt13.cc | 11
sandbox/garrigues/test_fllt2.cc | 13
sandbox/garrigues/test_fllt3.cc | 29 -
sandbox/garrigues/test_fllt_lena_tiles.cc | 4
sandbox/garrigues/upper.hh | 89 +++
14 files changed, 1090 insertions(+), 827 deletions(-)
Index: trunk/milena/mln/util/branch_iter_ind.hh
===================================================================
--- trunk/milena/mln/util/branch_iter_ind.hh (revision 1463)
+++ trunk/milena/mln/util/branch_iter_ind.hh (revision 1464)
@@ -172,7 +172,7 @@
else
{
s_.top().pos_++;
- if (s_.top().list_->size() <= s_.top().pos_)
+ if (s_.top().list_->size() == s_.top().pos_)
{
s_.pop();
next();
@@ -180,6 +180,7 @@
}
else
{
+ mln_assertion(s_.top().list_->size() > s_.top().pos_);
if (s_.top().previous_ != 0)
mln_assertion(s_.top().previous_ == (*(s_.top().list_))[s_.top().pos_ - 1]);
// if (s_.top().previous_ > 0)
Index: trunk/milena/sandbox/garrigues/test_fllt_lena_tiles.cc
===================================================================
--- trunk/milena/sandbox/garrigues/test_fllt_lena_tiles.cc (revision 1463)
+++ trunk/milena/sandbox/garrigues/test_fllt_lena_tiles.cc (revision 1464)
@@ -1,4 +1,4 @@
-# include "fllt2.hh"
+# include "fllt_optimized.hh"
# include <mln/core/image2d.hh>
# include <mln/core/clone.hh>
# include <mln/value/int_u8.hh>
@@ -26,7 +26,7 @@
image2d<value::int_u8> ima = io::pgm::load(path.str());
image2d<int> ima_int(ima.domain());
level::fill(ima_int, ima);
- debug::println(ima_int);
fllt::fllt(ima_int);
}
}
+
Index: trunk/milena/sandbox/garrigues/lower.hh
===================================================================
--- trunk/milena/sandbox/garrigues/lower.hh (revision 0)
+++ trunk/milena/sandbox/garrigues/lower.hh (revision 1464)
@@ -0,0 +1,89 @@
+// Copyright (C) 2007 EPITA Research and Development Laboratory
+//
+// 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_FIXME_FLLT_LOWER_HH
+# define MLN_FIXME_FLLT_LOWER_HH
+
+/*! \file fllt.hh
+ *
+ * \brief Informations about how to compute the lower level set.
+ *
+ */
+
+# include <mln/core/neighb2d.hh>
+
+# include <mln/accu/min.hh>
+# include <mln/labeling/regional_minima.hh>
+
+# include "fllt_types.hh"
+
+namespace mln
+{
+ namespace fllt
+ {
+
+ //Fwd declaration.
+ template <typename V> struct upper;
+
+ // LOWER LEVEL SET : region = c4, border = c8
+ template <typename V>
+ struct lower
+ {
+ typedef upper<V> opposite;
+ typedef lower_t tag;
+ static bool
+ compare(const V& u, const V& v)
+ {
+ return u < v;
+ }
+
+ template <typename I, typename N, typename O>
+ static bool
+ regional_extremum(const Image<I>& input, const Neighborhood<N>&
nbh,
+ Image<O>& output, unsigned& nlabels)
+ {
+ return labeling::regional_minima(input, nbh,
+ output, nlabels);
+ }
+
+ static const int inc = 1;
+ static const bool parent_is_brighter = true;
+ typedef accu::min accu_for_gn;
+
+ static const neighb2d& bdr_nbh() { return c8(); }
+ static const neighb2d& reg_nbh() { return c4(); }
+
+ };
+
+ } // end of namespace mln::fllt
+
+} // end of namespace mln
+
+
+
+#endif // ! MLN_FIXME_FLLT_LOWER_HH
Index: trunk/milena/sandbox/garrigues/test_fllt12.cc
===================================================================
--- trunk/milena/sandbox/garrigues/test_fllt12.cc (revision 1463)
+++ trunk/milena/sandbox/garrigues/test_fllt12.cc (revision 1464)
@@ -19,20 +19,11 @@
using namespace mln;
using typename value::int_u8;
-// int vs[3][6] = { {0, 0, 0, 1, 1, 1},
-// {0, 1, 0, 1, 0, 1},
-// {0, 0, 0, 1, 1, 1} };
-
-
- int vs[4][5] = {
- { 4, 4, 2, 2, 2},
+ int vs[4][5] = { {4, 4, 2, 2, 2},
{ 4, 3, 1, 2, 2},
{ 4, 1, 1, 4, 2},
{ 4, 1, 1, 1, 2} };
image2d<int> ima(make::image2d(vs));
- image2d<int_u8> out(ima.domain());
-
- level::fill(out, ima);
fllt::fllt(ima);
}
Index: trunk/milena/sandbox/garrigues/upper.hh
===================================================================
--- trunk/milena/sandbox/garrigues/upper.hh (revision 0)
+++ trunk/milena/sandbox/garrigues/upper.hh (revision 1464)
@@ -0,0 +1,89 @@
+// Copyright (C) 2007 EPITA Research and Development Laboratory
+//
+// 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_FIXME_FLLT_UPPER_HH
+# define MLN_FIXME_FLLT_UPPER_HH
+
+/*! \file upper.hh
+ *
+ * \brief Informations about how to compute the upper level set.
+ *
+ */
+
+# include <mln/core/neighb2d.hh>
+
+# include <mln/accu/max.hh>
+# include <mln/labeling/regional_maxima.hh>
+
+# include "fllt_types.hh"
+
+namespace mln
+{
+ namespace fllt
+ {
+
+ //Fwd declaration.
+ template <typename V> struct lower;
+
+ // UPPER LEVEL SET : region = c8, border = c4
+ template <typename V>
+ struct upper
+ {
+ typedef lower<V> opposite;
+ typedef upper_t tag;
+
+ static bool
+ compare(const V& u, const V& v)
+ {
+ return u > v;
+ }
+
+ template <typename I, typename N, typename O>
+ static bool
+ regional_extremum(const Image<I>& input, const Neighborhood<N>&
nbh,
+ Image<O>& output, unsigned& nlabels)
+ {
+ return labeling::regional_maxima(input, nbh,
+ output, nlabels);
+ }
+
+ static const int inc = -1;
+ static const bool parent_is_brighter = false;
+ typedef accu::max accu_for_gn;
+
+ static const neighb2d& bdr_nbh() { return c4(); }
+ static const neighb2d& reg_nbh() { return c8(); }
+ };
+
+ } // end of namespace mln::fllt
+
+} // end of namespace mln
+
+
+
+#endif // ! MLN_FIXME_FLLT_UPPER_HH
Index: trunk/milena/sandbox/garrigues/test_fllt3.cc
===================================================================
--- trunk/milena/sandbox/garrigues/test_fllt3.cc (revision 1463)
+++ trunk/milena/sandbox/garrigues/test_fllt3.cc (revision 1464)
@@ -15,26 +15,17 @@
using namespace mln;
- int ws[81] = {2,2,2,2,2,2,2,2,2,
- 2,2,2,2,2,2,2,2,2,
- 2,1,1,1,1,1,1,1,2,
- 2,1,2,2,1,0,0,1,2,
- 2,1,2,2,1,0,0,1,2,
- 2,1,2,2,1,0,0,1,2,
- 2,1,1,1,1,1,1,1,2,
- 2,1,1,1,1,1,1,1,2,
- 2,2,2,2,2,2,2,2,2};
+ int vs[9][9] = { {2,2,2,2,2,2,2,2,2},
+ {2,2,2,2,2,2,2,2,2},
+ {2,1,1,1,1,1,1,1,2},
+ {2,1,2,2,1,0,0,1,2},
+ {2,1,2,2,1,0,0,1,2},
+ {2,1,2,2,1,0,0,1,2},
+ {2,1,1,1,1,1,1,1,2},
+ {2,1,1,1,1,1,1,1,2},
+ {2,2,2,2,2,2,2,2,2} };
- w_window2d_int w_win = make::w_window2d(ws);
- image2d<int> ima = convert::to_image(w_win);
+ image2d<int> ima(make::image2d(vs));
fllt::fllt(ima);
-
-// image2d<value::int_u8> ima = io::pgm::load("../../img/tiny.pgm");
-
-// image2d<int> ima_int(ima.domain());
-
-// level::fill(ima_int, ima);
-// debug::println(ima);
-// fllt::fllt(ima_int);
}
Index: trunk/milena/sandbox/garrigues/fllt_merge.hh
===================================================================
--- trunk/milena/sandbox/garrigues/fllt_merge.hh (revision 0)
+++ trunk/milena/sandbox/garrigues/fllt_merge.hh (revision 1464)
@@ -0,0 +1,200 @@
+// Copyright (C) 2007 EPITA Research and Development Laboratory
+//
+// 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_FIXME_FLLT_MERGE_HH
+# define MLN_FIXME_FLLT_MERGE_HH
+
+/*! \file fllt_merge.hh
+ *
+ * \brief merge the upper and lower level set.
+ *
+ */
+
+# include <mln/core/image2d.hh>
+
+# include <mln/set/is_subset_of.hh>
+
+# include "fllt_types.hh"
+
+namespace mln
+{
+ namespace fllt
+ {
+ // Fwd declarations.
+ template <typename P, typename V, typename F>
+ void
+ fill_a_shape(fllt_node(P, V)& node,
+ fllt_tree(P, V)& tree,
+ const image2d<fllt_node(P, V)*>& node_reg,
+ const image2d<fllt_node(P, V)*>& hole_reg);
+
+ template <typename P, typename V, typename F>
+ void
+ move_shape(fllt_node(P, V)& node,
+ fllt_node(P, V)& hole,
+ fllt_tree(P, V)& tree,
+ const image2d<fllt_node(P, V)*>& hole_reg,
+ const image2d<fllt_node(P, V)*>& other_reg)
+ {
+ node.add_child(&hole);
+ fill_a_shape<P,V,typename F::opposite>(hole, tree, hole_reg, other_reg);
+ }
+
+ template <typename P, typename V, typename F>
+ fllt_node(P, V)*
+ find_the_hole(fllt_node(P, V)& node,
+ const P p,
+ const image2d<fllt_node(P, V)*>& other_reg)
+ {
+ fllt_node(P, V)* s = other_reg(p);
+ mln_assertion(s);
+ while (s->parent() &&
F::opposite::compare(s->parent()->elt().value, node.elt().value))
+ {
+ mln_assertion(s);
+ s = s->parent();
+ mln_assertion(s);
+ }
+ return s;
+ }
+
+ template <typename P, typename V, typename F>
+ void
+ fill_a_shape(fllt_node(P, V)& node,
+ fllt_tree(P, V)& tree,
+ const image2d<fllt_node(P, V)*>& node_reg,
+ const image2d<fllt_node(P, V)*>& hole_reg)
+ {
+ if (node.elt().holes.npoints() == 0)
+ {
+ return;
+ }
+ mln_piter(p_set<P>) p(node.elt().holes);
+ for_all(p)
+ {
+ bool h = true;
+
+ fllt_node(P, V)* hole;
+ if (node.elt().brighter == F::parent_is_brighter)
+ hole = find_the_hole<P,V,F>(node, point2d(p), hole_reg);
+ else
+ hole = find_the_hole<P,V,typename F::opposite>(node, point2d(p), node_reg);
+
+ mln_assertion(hole);
+
+ typename fllt_node(P, V)::children_t::iterator it;
+ for (it = node.children().begin();
+ it != node.children().end();
+ it++)
+ {
+ // Browse the holes of each child.
+ mln_piter(p_set<P>) q((*it)->elt().holes);
+ for_all(q)
+ {
+ fllt_node(P, V)* child_hole = find_the_hole<P,V,F>((**it), point2d(q),
hole_reg);
+ if (set::is_subset_of(hole->elt().points,
+ child_hole->elt().points))
+ {
+ h = false;
+ break;
+ }
+
+ }
+ if (!h)
+ break;
+ }
+ if (h)
+ move_shape<P,V,F>(node, *hole, tree, hole_reg, node_reg);
+ }
+
+ node.elt().holes.clear();
+ }
+
+ template <typename P, typename V>
+ fllt_tree(P, V)
+ merge_trees(fllt_tree(P, V)& lower_tree,
+ fllt_tree(P, V)& upper_tree,
+ const image2d<fllt_node(P, V)*>& low_reg,
+ const image2d<fllt_node(P, V)*>& upp_reg,
+ const image2d<V>& ima)
+ {
+
+ // In order to merge the trees, we only have to find for each shape S
+ // with a hole H in it whether one of its children has a hole HŽ
+ // containing H. If it is the case, we do nothing. Otherwise, we
+ // put the shape of the hole H (and all its descendants) as child of
+ // the shape .
+ {
+ fllt_branch_iter(P, V) p(lower_tree.main_branch());
+ for_all(p)
+ {
+ fllt_node(P, V)& n(p);
+ fill_a_shape< P, V, lower<V> >(n, lower_tree, low_reg, upp_reg);
+ mln_assertion(lower_tree.check_consistency());
+ mln_assertion(upper_tree.check_consistency());
+ }
+
+ }
+
+ {
+ fllt_branch_iter(P, V) p(upper_tree.main_branch());
+ for_all(p)
+ {
+ fllt_node(P, V)& n(p);
+ fill_a_shape< P, V, upper<V> >(n, upper_tree, upp_reg, low_reg);
+ mln_assertion(lower_tree.check_consistency());
+ mln_assertion(upper_tree.check_consistency());
+ }
+ }
+
+ // FIXME : this is a wrong way to choose the root of the result
+ // tree. lower and upper root doesn't have the same level, we
+ // want the right level for the background.
+ fllt_tree(P, V)* main_tree = &lower_tree;
+ fllt_tree(P, V)* other_tree = &upper_tree;
+
+ if (lower_tree.root()->elt().points.npoints() >= ima.domain().npoints())
+ {
+ main_tree = &upper_tree;
+ other_tree = &lower_tree;
+ }
+
+ typename fllt_node(P, V)::children_t::iterator it;
+ for (it = other_tree->root()->children().begin();
+ it != other_tree->root()->children().end(); )
+ {
+ main_tree->root()->add_child(*it);
+ }
+ mln_assertion(main_tree->check_consistency());
+ return *main_tree;
+ }
+
+ } // end of namespace mln::fllt
+
+} // end of namespace mln
+
+#endif // ! MLN_FIXME_FLLT_MERGE_HH
Index: trunk/milena/sandbox/garrigues/level_set.hh
===================================================================
--- trunk/milena/sandbox/garrigues/level_set.hh (revision 0)
+++ trunk/milena/sandbox/garrigues/level_set.hh (revision 1464)
@@ -0,0 +1,463 @@
+// Copyright (C) 2007 EPITA Research and Development Laboratory
+//
+// 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_FIXME_LEVEL_SET_HH
+# define MLN_FIXME_LEVEL_SET_HH
+
+/*! \file level_set.hh
+ *
+ * \brief Algorithm to compulte the upper or lower level set.
+ *
+ */
+
+# include "fllt_types.hh"
+# include "lower.hh"
+# include "upper.hh"
+
+# include <mln/core/image2d.hh>
+# include <mln/core/point2d.hh>
+
+# include <mln/core/p_set.hh>
+# include <mln/core/inplace.hh>
+# include <mln/core/neighb2d.hh>
+# include <mln/core/clock_neighb2d.hh>
+# include <mln/core/pset_if_piter.hh>
+# include <mln/core/pset_if.hh>
+# include <mln/core/sub_image.hh>
+# include <mln/core/image_if.hh>
+# include <mln/core/clone.hh>
+# include <mln/core/a_point_of.hh>
+
+# include <mln/debug/println.hh>
+# include <mln/debug/println_with_border.hh>
+
+# include <mln/convert/to_image.hh>
+
+# include <mln/border/fill.hh>
+
+# include <mln/level/compute.hh>
+# include <mln/level/fill.hh>
+# include <mln/accu/min.hh>
+# include <mln/accu/max.hh>
+
+# include <mln/set/uni.hh>
+# include <mln/set/diff.hh>
+# include <mln/set/inter.hh>
+# include <mln/set/is_subset_of.hh>
+
+# include <mln/util/tree.hh>
+# include <mln/util/branch_iter_ind.hh>
+
+# include <mln/labeling/regional_minima.hh>
+# include <mln/labeling/regional_maxima.hh>
+# include <mln/labeling/level.hh>
+
+# include <mln/fun/ops.hh>
+# include <mln/pw/value.hh>
+# include <mln/pw/cst.hh>
+
+# include <mln/util/tree_to_image.hh>
+# include <mln/value/int_u8.hh>
+# include <mln/level/stretch.hh>
+# include <mln/level/compare.hh>
+# include <mln/io/pgm/save.hh>
+
+namespace mln
+{
+ namespace fllt
+ {
+
+ template <typename P, typename V>
+ struct ls_env
+ {
+ const image2d<V>& input;
+ image2d<V> u;
+ image2d<bool> tagged;
+ image2d<bool> shape;
+ int n_cc;
+
+ fllt_node(P, V)* current_region;
+ image2d<fllt_node(P, V)*>& regions;
+ p_set<P> A;
+ p_set<P> R;
+ p_set<P> N;
+ V g,gn;
+ point2d x0;
+
+ ls_env(const image2d<V>& input,
+ image2d<fllt_node(P, V)*>& regions_)
+ : input(input),
+ regions(regions_),
+ tagged(input.domain()),
+ shape(input.domain()),
+ g(0),
+ gn(0),
+ n_cc(0),
+ current_region(0)
+ {
+ // INIT
+ R.clear();
+ N.clear();
+ A.clear();
+
+ level::fill(regions, 0);
+ level::fill(tagged, false);
+
+ u = clone(input);
+ border::fill(u, 0);
+ }
+
+ };
+
+ template <typename P, typename V>
+ void update_n_cc(lower_t,
+ ls_env<P, V>& env,
+ point2d p)
+ {
+ // region in c4.
+ bool previous_is_false;
+ unsigned res = 0;
+
+ dpoint2d dp(-1,-1);
+ clock_neighb2d nbh = cc8(dp);
+
+ mln_fwd_niter(clock_neighb2d) n(nbh , p);
+
+ // just to get the last previous_is_false.
+ // FIXME replace it with bkd_niter.
+ for_all(n)
+ previous_is_false = !env.shape(n);
+
+ for_all(n)
+ {
+ //y in c4
+ bool x = env.shape(n);
+ n.next();
+ mln_assertion(n.is_valid());
+ bool y = env.shape(n);
+
+ if (!x && y)
+ ++res;
+ else
+ if (x && y && previous_is_false)
+ ++res;
+
+ previous_is_false = !y;
+
+ }
+ env.n_cc += (res == 0 ? 0 : (res - 1));
+
+ }
+
+ template <typename P, typename V>
+ void update_n_cc(upper_t,
+ ls_env<P, V>& env,
+ point2d p)
+ {
+ // region in c8.
+ bool previous_is_false;
+ unsigned res = 0;
+
+ dpoint2d dp(-1,0);
+ clock_neighb2d nbh = cc8(dp);
+
+ mln_fwd_niter(clock_neighb2d) n(nbh , p);
+
+ // just to get the last previous_is_false.
+ // FIXME optimise it with bkd_niter.
+ for_all(n)
+ {
+ bool x = env.shape(n);
+ n.next();
+ mln_assertion(n.is_valid());
+ bool y = env.shape(n);
+ previous_is_false = !y && !x;
+ }
+
+
+ for_all(n)
+ {
+ //y in c4
+ bool x = env.shape(n);
+ n.next();
+ mln_assertion(n.is_valid());
+ bool y = env.shape(n);
+
+ if (!x && y)
+ ++res;
+ else
+ if (x && previous_is_false)
+ ++res;
+
+ previous_is_false = !y && !x;
+
+ }
+ env.n_cc += (res == 0 ? 0 : (res - 1));
+ }
+
+ template <typename P, typename V>
+ void step1 (ls_env<P, V>& env,
+ point2d p)
+ {
+ // x0 <- a not tagged local mininum of ima.
+ env.x0 = p;
+ // g <- u(x0)
+ env.g = env.input(env.x0);
+ }
+
+ template <typename P, typename V>
+ void step2 (ls_env<P, V>& env)
+ {
+ // A <- {x0}
+ env.A.clear();
+ env.A.insert(env.x0);
+ // R <- {}
+ env.R.clear();
+ // N <- {}
+ env.N.clear();
+ }
+
+
+ template <typename V, typename P, typename F>
+ void step3 (ls_env<P, V>& env)
+ {
+ static bool finished = false;
+
+ // Stop the algorithm.
+ if (finished)
+ { finished = false; env.gn -= 2 * F::inc; return; }
+
+ // N <- N union {x neighbor of a pixel in a\R}
+ mln_piter(p_set<P>) qa(env.A);
+ for_all(qa)
+ {
+ mln_niter(neighb2d) n(F::reg_nbh(), qa);
+ for_all (n)
+ if (!env.R.has (n))
+ env.N.insert (n);
+ }
+
+ // gn <- min u(x) x belongs to N.
+ if ((env.u | set::inter(env.N, env.u.domain())).npoints() > 0)
+ env.gn = level::compute< typename F::accu_for_gn >(env.u | set::inter(env.N,
env.u.domain()));
+ else
+ {
+ finished = true;
+ env.gn += F::inc;
+ }
+
+ // R <- R union A
+ // tag the pixels of A.
+ for_all(qa)
+ {
+ env.R.insert(qa);
+ env.tagged(qa) = true;
+ //Update the number of connected components.
+ update_n_cc(typename F::tag(), env, qa);
+ }
+ }
+
+ /// IF g < gn.
+ template <typename V, typename P, typename F>
+ void step4_1 (ls_env<P, V>& env)
+ {
+ // If the region is bounded
+ // Create a new conected component.
+ // FIXME : we can make it faster.
+
+ if ((env.R.bbox() < env.u.domain()) || (env.R.npoints() ==
env.u.domain().npoints()))
+ {
+ mln_piter(p_set<P>) p(env.R);
+ env.current_region = new fllt_node(P, V)();
+ env.current_region->elt().brighter = F::parent_is_brighter;
+ env.current_region->elt().value = env.g;
+ for_all(p)
+ {
+ env.current_region->elt().points.insert(p);
+
+ if (env.regions(p) == 0)
+ {
+ env.regions(p) = env.current_region;
+ }
+ else
+ {
+ if (env.regions(p)->parent() == 0)
+ env.regions(p)->set_parent(env.current_region);
+ }
+ }
+
+
+ // Count the number of conected components of the border of R.
+ static image2d<int> tmp(env.u.domain().to_larger(1));
+ static image2d<bool> border_ima(tmp.domain());
+ level::fill(border_ima, false);
+
+ mln_piter(p_set<P>) z(env.N);
+ for_all(z)
+ {
+ mln_assertion(border_ima.owns_(z));
+ border_ima(z) = true;
+ }
+ unsigned n;
+ labeling::level(border_ima, true, F::bdr_nbh(), tmp, n);
+
+ if (n > 1)
+ {
+
+ // IF number of conected components of the border > 1
+ for (int i = 2; i <= n; i++)
+ {
+ // follow each border to find which is the exterior border
+ // and which are the holes. Keep one pixel of each holes.
+
+ // WARNING : We trust labeling::level to label the exterior border with 1.
+ env.current_region->elt().holes.insert(a_point_of(tmp | pw::value(tmp) ==
pw::cst(i)));
+
+ // FIXME : [optimisation] Remove from N border of holes???.
+ // Recompute gn <- min u(x) x belongs to A
+ }
+ }
+
+ }
+ env.g = env.gn;
+ // A <- {x belongs to N / u(x) == g}
+ env.A.clear();
+ env.A = set::uni(env.A, set::inter(env.N, env.u.domain()) | pw::value(env.u) ==
pw::cst(env.g));
+ // N <- N\{x belongs to N / u(x) == g}
+ env.N = set::diff(env.N, set::inter(env.N, env.u.domain()) | pw::value(env.u) ==
pw::cst(env.g));
+ }
+
+
+ /// IF g == gn.
+ template <typename V, typename P>
+ void step4_2 (ls_env<P, V>& env)
+ {
+ // A <- {x belongs to N / u(x) == g}
+ env.A = set::uni(env.A, set::inter(env.N, env.u.domain()) | pw::value(env.u) ==
pw::cst(env.g));
+ // N <- N\{x belongs to N / u(x) == g}
+ env.N = set::diff(env.N, set::inter(env.N, env.u.domain()) | pw::value(env.u) ==
pw::cst(env.g));
+ }
+
+ /// IF g > gn.
+ template <typename V, typename P>
+ void step4_3 (ls_env<P, V>& env)
+ {
+ // set the gray-level of the pixels of R to g.
+ mln_piter(p_set<P>) p(env.R);
+ for_all(p)
+ {
+ mln_assertion (env.tagged(p));
+ env.u (p) = env.g;
+ }
+ }
+
+
+ template <typename V, typename F>
+ fllt_tree(point2d, V)&
+ compute_level_set(const image2d<V>& input,
+ image2d< fllt_node(point2d, V)* >& regions)
+ {
+ typedef point2d P;
+ typedef image2d<V> I;
+
+ // FIXME: not nice.
+ typedef mln::image_if<
+ mln::image2d<V>,
+ mln::fun::greater_p2b_expr_<mln::pw::value_<mln::image2d<V> >,
+ mln::pw::cst_<int> >
+ > I_IF;
+
+ // Check
+ mln_assertion(input.domain() == regions.domain());
+
+ // FIXME : rename it.
+ ls_env<P,V> env(input, regions);
+
+ // Declarations.
+ image2d<V> min_locals(input.domain());
+
+
+ // Get the locals extremums
+ unsigned nlabels;
+ F::regional_extremum(input, F::reg_nbh(), min_locals, nlabels);
+
+ /// Algorithm.
+ {
+ // For all locals extremums
+ I_IF min_locals_list(min_locals | (pw::value(min_locals) > pw::cst(0)));
+ mln_piter(I_IF) p(min_locals_list.domain());
+ for_all(p)
+ {
+ if (env.tagged(p))
+ continue;
+
+ step1(env, p);
+ step2(env);
+ while (1)
+ {
+ step3<V, P, F>(env);
+ /// step4.
+ if (F::compare(env.g, env.gn))
+ {
+ step4_1<V, P, F>(env);
+ // GO TO 3)
+ continue;
+ }
+
+
+ if (env.g == env.gn)
+ {
+ step4_2(env);
+ // GO TO 3)
+ continue;
+ }
+
+
+ if (!F::compare(env.g, env.gn))
+ {
+ step4_3(env);
+ // GO TO 1)
+ break;
+ }
+ }
+ }
+ } // end of Algorithm
+
+ image2d<value::int_u8> output (input.domain ());
+ fllt_tree(P, V)& tree = *new fllt_tree(P, V)(env.current_region);
+ util::tree_to_image (tree, output);
+
+ return (tree);
+
+ } // end of compute_level_set
+
+ } // end of namespace mln::fllt
+
+} // end of namespace mln
+
+#endif // ! MLN_FIXME_LEVEL_SET_HH
Index: trunk/milena/sandbox/garrigues/fllt2.hh
===================================================================
--- trunk/milena/sandbox/garrigues/fllt2.hh (revision 1463)
+++ trunk/milena/sandbox/garrigues/fllt2.hh (revision 1464)
@@ -36,7 +36,7 @@
*/
# include <mln/core/image2d.hh>
-# include <mln/core/set_p.hh>
+# include <mln/core/p_set.hh>
# include <mln/core/inplace.hh>
# include <mln/core/neighb2d.hh>
# include <mln/core/pset_if_piter.hh>
@@ -89,8 +89,8 @@
struct fllt_node_elt
{
V value;
- set_p<P> points;
- set_p<P> holes;
+ p_set<P> points;
+ p_set<P> holes;
/// Tell if his parent if brighter or not. Nb : if the parent
/// if brighter, the node come from the lower level set
bool brighter;
@@ -161,9 +161,9 @@
}
template <typename P>
- void step2 (set_p<P>& A,
- set_p<P>& R,
- set_p<P>& N,
+ void step2 (p_set<P>& A,
+ p_set<P>& R,
+ p_set<P>& N,
point2d& x0)
{
//std::cout << "entering step 2" << std::endl;
@@ -181,9 +181,9 @@
template <typename V, typename P, typename F>
void step3 (const image2d<V>& u,
image2d<bool>& tagged,
- set_p<P>& A,
- set_p<P>& R,
- set_p<P>& N,
+ p_set<P>& A,
+ p_set<P>& R,
+ p_set<P>& N,
V& gn)
{
static bool finished = false;
@@ -194,7 +194,7 @@
{ finished = false; gn -= 2 * F::inc; return; }
// N <- N union {x neighbor of a pixel in a\R}
- mln_piter(set_p<P>) qa(A);
+ mln_piter(p_set<P>) qa(A);
for_all(qa)
{
mln_niter(neighb2d) n(F::reg_nbh(), qa);
@@ -239,9 +239,9 @@
/// IF g < gn.
template <typename V, typename P, typename F>
void step4_1 (image2d<V>& u,
- set_p<P>& A,
- set_p<P>& R,
- set_p<P>& N,
+ p_set<P>& A,
+ p_set<P>& R,
+ p_set<P>& N,
V& g,
V& gn,
fllt_node(P, V)*& current_region,
@@ -256,7 +256,7 @@
if ((R.bbox() < u.domain()) || (R.npoints() == u.domain().npoints()))
{
- mln_piter(set_p<P>) p(R);
+ mln_piter(p_set<P>) p(R);
current_region = new fllt_node(P, V)();
current_region->elt().brighter = F::parent_is_brighter;
current_region->elt().value = g;
@@ -285,7 +285,7 @@
// level::fill(inplace(border_ima | N), true);
// std::cout << "tmp border = " << tmp.border () <<
std::endl;
// std::cout << "ima border = " << border_ima.border ()
<< std::endl;
- mln_piter(set_p<P>) z(N);
+ mln_piter(p_set<P>) z(N);
for_all(z)
{
mln_assertion(border_ima.owns_(z));
@@ -336,8 +336,8 @@
/// IF g == gn.
template <typename V, typename P>
void step4_2 (const image2d<V>& u,
- set_p<P>& A,
- set_p<P>& N,
+ p_set<P>& A,
+ p_set<P>& N,
V& g,
fllt_node(P, V)* current_region,
image2d<fllt_node(P, V)*>& regions
@@ -364,13 +364,13 @@
template <typename V, typename P>
void step4_3 (image2d<V>& u,
const image2d<bool>& tagged,
- const set_p<P>& R,
+ const p_set<P>& R,
const V& g)
{
//std::cout << "entering step 4_3" << std::endl;
// set the gray-level of the pixels of R to g.
- mln_piter(set_p<P>) p(R);
+ mln_piter(p_set<P>) p(R);
for_all(p)
{
mln_assertion (tagged(p));
@@ -401,7 +401,7 @@
mln_assertion(ima.domain() == regions.domain());
// Declarations.
- set_p<P> R, N, A;
+ p_set<P> R, N, A;
V g, gn;
point2d x0;
image2d<V> min_locals(ima.domain());
@@ -629,7 +629,7 @@
// std::cout << "[End fill_a_shape]" << std::endl;
return;
}
- mln_piter(set_p<P>) p(node.elt().holes);
+ mln_piter(p_set<P>) p(node.elt().holes);
for_all(p)
{
bool h = true;
@@ -648,7 +648,7 @@
it++)
{
// Browse the hole of each child.
- mln_piter(set_p<P>) q((*it)->elt().holes);
+ mln_piter(p_set<P>) q((*it)->elt().holes);
for_all(q)
{
fllt_node(P, V)* child_hole = find_the_hole<P,V,F>((**it), point2d(q),
hole_reg);
@@ -744,7 +744,7 @@
for_all(p)
{
//std::cout << (&*p) << ":" << p.deepness() <<
std::endl;
- mln_piter(set_p<point2d>) q((*p).elt().points);
+ mln_piter(p_set<point2d>) q((*p).elt().points);
for_all(q)
{
if (output(q) < p.deepness())
@@ -766,7 +766,7 @@
{
if ((*p).elt().points.npoints() > limit)
{
- mln_piter(set_p<point2d>) q((*p).elt().points);
+ mln_piter(p_set<point2d>) q((*p).elt().points);
for_all(q)
{
mln_niter(neighb2d) n(c4(), q);
Index: trunk/milena/sandbox/garrigues/fllt_optimized.hh
===================================================================
--- trunk/milena/sandbox/garrigues/fllt_optimized.hh (revision 1463)
+++ trunk/milena/sandbox/garrigues/fllt_optimized.hh (revision 1464)
@@ -35,44 +35,12 @@
*
*/
-# include <mln/core/image2d.hh>
-# include <mln/core/set_p.hh>
-# include <mln/core/inplace.hh>
-# include <mln/core/neighb2d.hh>
-# include <mln/core/pset_if_piter.hh>
-# include <mln/core/pset_if.hh>
-# include <mln/core/sub_image.hh>
-# include <mln/core/image_if.hh>
-# include <mln/core/clone.hh>
-# include <mln/core/a_point_of.hh>
-
-# include <mln/debug/println.hh>
-# include <mln/debug/println_with_border.hh>
-
-# include <mln/convert/to_image.hh>
-
-# include <mln/border/fill.hh>
-
-# include <mln/level/compute.hh>
-# include <mln/level/fill.hh>
-# include <mln/accu/min.hh>
-# include <mln/accu/max.hh>
-
-# include <mln/set/uni.hh>
-# include <mln/set/diff.hh>
-# include <mln/set/inter.hh>
-# include <mln/set/is_subset_of.hh>
-
-# include <mln/util/tree.hh>
-# include <mln/util/branch_iter_ind.hh>
-
-# include <mln/labeling/regional_minima.hh>
-# include <mln/labeling/regional_maxima.hh>
-# include <mln/labeling/level.hh>
-
-# include <mln/fun/ops.hh>
-# include <mln/pw/value.hh>
-# include <mln/pw/cst.hh>
+
+# include "fllt_types.hh"
+# include "level_set.hh"
+# include "fllt_merge.hh"
+# include "lower.hh"
+# include "upper.hh"
# include <mln/util/tree_to_image.hh>
# include <mln/value/int_u8.hh>
@@ -86,654 +54,6 @@
{
template <typename P, typename V>
- struct fllt_node_elt
- {
- V value;
- set_p<P> points;
- set_p<P> holes;
- /// Tell if his parent if brighter or not. Nb : if the parent
- /// if brighter, the node come from the lower level set
- bool brighter;
- };
-
-# define fllt_tree(P, V) util::tree< fllt_node_elt<P, V> >
-# define fllt_node(P, V) util::node< fllt_node_elt<P, V> >
-# define fllt_branch(P, V) util::branch< fllt_node_elt<P, V> >
-# define fllt_branch_iter(P, V) util::branch_iter< fllt_node_elt<P, V> >
-
- // # define fllt_node(P, V) typename fllt_tree(P, V)::node_t
-
-
-
- // LOWER LEVEL SET : region = c4, border = c8
- // UPPER LEVEL SET : region = c8, border = c4
-
- // 1)
- // x0 <- a not tagged local mininum of ima.
- // g <- u(x0)
-
- // 2)
- // A <- {x0}
- // R <- {}
- // N <- {}
-
- // 3)
- // N <- N union {x neighbor of a pixel in a}
- // gn <- min u(x) x belongs to N.
- // R <- R union A
- // tag the pixels of A.
-
- // 4)
- // IF g < gn
- // IF number of conected components of the border > 1
- // follow each border to find which is the exterior border
- // and which are the holes. Keep one pixel of each holes.
- //
- // Remove from N border of holes.
- // Recompute gn <- min u(x) x belongs to A
- //
- // g <- gn
- // A <- {x belongs to N / u(x) == g}
- // N <- N\{x belongs to N / u(x) == g}
- // GO TO 3)
- // IF g == gn
- // A <- {x belongs to N / u(x) == g}
- // N <- N\{x belongs to N / u(x) == g}
- // GO TO 3)
- // IF g > gn
- // set the gray-level of the pixels of R to g.
- // GO TO 1)
-
- template <typename P, typename V>
- struct fllt_env
- {
- const image2d<V>& input;
- image2d<V> u;
- image2d<bool> tagged;
- fllt_node(P, V)* current_region;
- image2d<fllt_node(P, V)*>& regions;
- set_p<P> A;
- set_p<P> R;
- set_p<P> N;
- V g,gn;
- point2d x0;
-
- fllt_env(const image2d<V>& input,
- image2d<fllt_node(P, V)*>& regions_)
- : input(input),
- regions(regions_),
- tagged(input.domain())
- {
-
- // INIT
- R.clear();
- N.clear();
- A.clear();
- g= 0;
- gn = 0;
- current_region = 0;
-
- level::fill(regions, 0);
- level::fill(tagged, false);
-
- u = clone(input);
- border::fill(u, 0);
- }
-
- };
-
- template <typename P, typename V>
- void step1 (fllt_env<P, V>& env,
- point2d p)
- {
- //std::cout << "entering step 1" << std::endl;
- // x0 <- a not tagged local mininum of ima.
- //std::cout << std::endl << "x0 = " << p <<
std::endl;
- env.x0 = p;
- // g <- u(x0)
- env.g = env.input(env.x0);
- //std::cout << "g = " << g << std::endl;
- //std::cout << "exiting step 1" << std::endl;
- }
-
- template <typename P, typename V>
- void step2 (fllt_env<P, V>& env)
- {
- //std::cout << "entering step 2" << std::endl;
- // A <- {x0}
- env.A.clear();
- env.A.insert(env.x0);
- // R <- {}
- env.R.clear();
- // N <- {}
- env.N.clear();
- //std::cout << "exiting step 2" << std::endl;
- }
-
-
- template <typename V, typename P, typename F>
- void step3 (fllt_env<P, V>& env)
- {
- static bool finished = false;
- //std::cout << "entering step 3" << std::endl;
-
- // Stop the algorithm.
- if (finished)
- { finished = false; env.gn -= 2 * F::inc; return; }
-
- // N <- N union {x neighbor of a pixel in a\R}
- mln_piter(set_p<P>) qa(env.A);
- for_all(qa)
- {
- mln_niter(neighb2d) n(F::reg_nbh(), qa);
- for_all (n)
- if (!env.R.has (n))
- env.N.insert (n);
- }
-
- // debug::println(u);
-
- // //std::cout << "A :" << std::endl;
- // if (A.npoints())
- // //debug::println(u | A);
- // //std::cout << "N :" << std::endl;
- // if (N.npoints())
- // //debug::println(u | N);
- // //std::cout << "R :" << std::endl;
- // if (R.npoints())
- // //debug::println(u | R);
-
- // gn <- min u(x) x belongs to N.
- if ((env.u | set::inter(env.N, env.u.domain())).npoints() > 0)
- env.gn = level::compute< typename F::accu_for_gn >(env.u | set::inter(env.N,
env.u.domain()));
- else
- {
- finished = true;
- env.gn += F::inc;
- }
- //std::cout << std::endl << "gN = " << gn <<
std::endl;
- // R <- R union A
- // tag the pixels of A.
-
- for_all(qa)
- {
- env.R.insert(qa);
- env.tagged(qa) = true;
- //Update the number of connected components.
- }
- //std::cout << "exiting step 3" << std::endl;
- }
-
-
- /// IF g < gn.
- template <typename V, typename P, typename F>
- void step4_1 (fllt_env<P, V>& env)
- {
- //std::cout << "entering step 4_1" << std::endl;
-
- // If the region is bounded
- // Create a new conected component.
- // FIXME : we can make it faster.
-
- if ((env.R.bbox() < env.u.domain()) || (env.R.npoints() ==
env.u.domain().npoints()))
- {
- mln_piter(set_p<P>) p(env.R);
- env.current_region = new fllt_node(P, V)();
- env.current_region->elt().brighter = F::parent_is_brighter;
- env.current_region->elt().value = env.g;
- for_all(p)
- {
- env.current_region->elt().points.insert(p);
-
- if (env.regions(p) == 0)
- {
- //current_region->elt().points.insert(p);
- env.regions(p) = env.current_region;
- }
- else
- {
- if (env.regions(p)->parent() == 0)
- env.regions(p)->set_parent(env.current_region);
- }
- }
-
-
- // Count the number of conected components of the border of R.
- static image2d<int> tmp(env.u.domain().to_larger(1));
- static image2d<bool> border_ima(tmp.domain());
- level::fill(border_ima, false);
-
- // level::fill(inplace(border_ima | N), true);
- // std::cout << "tmp border = " << tmp.border () <<
std::endl;
- // std::cout << "ima border = " << border_ima.border ()
<< std::endl;
- mln_piter(set_p<P>) z(env.N);
- for_all(z)
- {
- mln_assertion(border_ima.owns_(z));
- border_ima(z) = true;
- }
- std::cout << "labeling::level" << std::endl;
- unsigned n;
- labeling::level(border_ima, true, F::bdr_nbh(), tmp, n);
-
- // debug::println(border_ima);
- //std::cout << "nb composantes :" << n << std::endl;
- // debug::println(tmp);
- if (n > 1)
- {
-
- // IF number of conected components of the border > 1
- for (int i = 2; i <= n; i++)
- {
- // follow each border to find which is the exterior border
- // and which are the holes. Keep one pixel of each holes.
-
- // WARNING : We trust labeling::level to label the exterior border with 1.
- env.current_region->elt().holes.insert(a_point_of(tmp | pw::value(tmp) ==
pw::cst(i)));
-
- // FIXME : [optimisation] Remove from N border of holes???.
- // Recompute gn <- min u(x) x belongs to A
- }
- }
-
- }
- env.g = env.gn;
- // A <- {x belongs to N / u(x) == g}
- env.A.clear();
- env.A = set::uni(env.A, set::inter(env.N, env.u.domain()) | pw::value(env.u) ==
pw::cst(env.g));
- // N <- N\{x belongs to N / u(x) == g}
- env.N = set::diff(env.N, set::inter(env.N, env.u.domain()) | pw::value(env.u) ==
pw::cst(env.g));
-
- // std::cout << "A :" << std::endl;
- // if (A.npoints())
- // debug::println(u | A);
- // std::cout << "N :" << std::endl;
- // if (N.npoints())
- // debug::println(u | N);
-
- //std::cout << "exiting step 4_1" << std::endl;
- }
-
-
- /// IF g == gn.
- template <typename V, typename P>
- void step4_2 (fllt_env<P, V>& env)
- {
- //std::cout << "entering step 4_2" << std::endl;
-
- // A <- {x belongs to N / u(x) == g}
- env.A = set::uni(env.A, set::inter(env.N, env.u.domain()) | pw::value(env.u) ==
pw::cst(env.g));
- // N <- N\{x belongs to N / u(x) == g}
- env.N = set::diff(env.N, set::inter(env.N, env.u.domain()) | pw::value(env.u) ==
pw::cst(env.g));
-
- // std::cout << "A :" << std::endl;
- // if (A.npoints())
- // debug::println(u | A);
- // std::cout << "N :" << std::endl;
- // if (N.npoints())
- // debug::println(u | N);
-
- //std::cout << "exiting step 4_2" << std::endl;
- }
-
- /// IF g > gn.
- template <typename V, typename P>
- void step4_3 (fllt_env<P, V>& env)
- {
- //std::cout << "entering step 4_3" << std::endl;
-
- // set the gray-level of the pixels of R to g.
- mln_piter(set_p<P>) p(env.R);
- for_all(p)
- {
- mln_assertion (env.tagged(p));
- env.u (p) = env.g;
- }
-
- //std::cout << "exiting step 4_3" << std::endl;
-
- }
-
-
- template <typename V, typename F>
- fllt_tree(point2d, V)&
- compute_level_set(const image2d<V>& input,
- image2d< fllt_node(point2d, V)* >& regions)
- {
- typedef point2d P;
- typedef image2d<V> I;
-
- // FIXME: not nice.
- typedef mln::image_if<
- mln::image2d<V>,
- mln::fun::greater_p2b_expr_<mln::pw::value_<mln::image2d<V> >,
- mln::pw::cst_<int> >
- > I_IF;
-
- // Check
- mln_assertion(input.domain() == regions.domain());
-
- // FIXME : rename it.
- fllt_env<P,V> env(input, regions);
-
- // Declarations.
-// set_p<P> R, N, A;
-// V g, gn;
-// point2d x0;
- image2d<V> min_locals(input.domain());
-
-
- // Get the locals extremums
- unsigned nlabels;
- F::regional_extremum(input, F::reg_nbh(), min_locals, nlabels);
-
- // debug::println(min_locals);
- // debug::println(min_locals | (pw::value(min_locals) > pw::cst(0)));
-
- /// Algorithm.
- {
- // For all locals extremums
- //void* x = min_locals | (pw::value(min_locals) > pw::cst(0));
- I_IF min_locals_list(min_locals | (pw::value(min_locals) > pw::cst(0)));
- mln_piter(I_IF) p(min_locals_list.domain());
- for_all(p)
- {
- if (env.tagged(p))
- continue;
-
- step1(env, p);
- step2(env);
- while (1)
- {
- //std::cout << "g = " << g << std::endl;
- step3<V, P, F>(env);
- /// step4.
- if (F::compare(env.g, env.gn))
- {
- step4_1<V, P, F>(env);
- // GO TO 3)
- continue;
- }
-
-
- if (env.g == env.gn)
- {
- step4_2(env);
- // GO TO 3)
- continue;
- }
-
-
- if (!F::compare(env.g, env.gn))
- {
- step4_3(env);
- // GO TO 1)
- break;
- }
- }
- //std::cout << "current_region = " << current_region <<
std::endl;
- }
- } // end of Algorithm
-
- image2d<value::int_u8> output (input.domain ());
- fllt_tree(P, V)& tree = *new fllt_tree(P, V)(env.current_region);
- util::tree_to_image (tree, output);
-
- // util::display_tree(input, tree);
-
- // debug::println(output);
- // std::cout << std::endl;
- // debug::println(input);
-
- // if (output != input)
- // {
- // std::cerr << "BUG!!!" << std::endl;
- // abort();
- // }
-
- // io::pgm::save(output, "out.pgm");
- // std::cout << "out.pgm generate"
- // << std::endl;
-
-
- // debug::println(regions);
- //debug::println(input | regions(make:defined reference to
`mln::fllt::lower<mln::value::int_u<8u>
>::inc':point2d(-4,-1))->elt().points);
-
- return (tree);
-
- } // end of compute_level_set
-
- //Fwd declarations.
- template <typename V> struct lower;
- template <typename V> struct upper;
-
- // LOWER LEVEL SET : region = c4, border = c8
- template <typename V>
- struct lower
- {
- typedef upper<V> opposite;
- static bool
- compare(const V& u, const V& v)
- {
- return u < v;
- }
-
- template <typename I, typename N, typename O>
- static bool
- regional_extremum(const Image<I>& input, const Neighborhood<N>&
nbh,
- Image<O>& output, unsigned& nlabels)
- {
- return labeling::regional_minima(input, nbh,
- output, nlabels);
- }
-
- static const int inc = 1;
- static const bool parent_is_brighter = true;
- typedef accu::min accu_for_gn;
-
- static const neighb2d& bdr_nbh() { return c8(); }
- static const neighb2d& reg_nbh() { return c4(); }
-
- };
-
-
-
- // UPPER LEVEL SET : region = c8, border = c4
- template <typename V>
- struct upper
- {
- typedef lower<V> opposite;
-
- static bool
- compare(const V& u, const V& v)
- {
- return u > v;
- }
-
- template <typename I, typename N, typename O>
- static bool
- regional_extremum(const Image<I>& input, const Neighborhood<N>&
nbh,
- Image<O>& output, unsigned& nlabels)
- {
- return labeling::regional_maxima(input, nbh,
- output, nlabels);
- }
-
- static const int inc = -1;
- static const bool parent_is_brighter = false;
- typedef accu::max accu_for_gn;
-
- static const neighb2d& bdr_nbh() { return c4(); }
- static const neighb2d& reg_nbh() { return c8(); }
- };
-
- // Fwd declarations.
- template <typename P, typename V, typename F>
- void
- fill_a_shape(fllt_node(P, V)& node,
- fllt_tree(P, V)& tree,
- const image2d<fllt_node(P, V)*>& node_reg,
- const image2d<fllt_node(P, V)*>& hole_reg);
-
- template <typename P, typename V, typename F>
- void
- move_shape(fllt_node(P, V)& node,
- fllt_node(P, V)& hole,
- fllt_tree(P, V)& tree,
- const image2d<fllt_node(P, V)*>& hole_reg,
- const image2d<fllt_node(P, V)*>& other_reg)
- {
- // FIXME : debug to remove.
- // std::cout << " [move_shape] "<< &hole
<< " as son of "<< &node << std::endl;
- //node.elt().points = set::uni(hole.elt().points, node.elt().points);
- node.add_child(&hole);
- fill_a_shape<P,V,typename F::opposite>(hole, tree, hole_reg, other_reg);
- }
-
- template <typename P, typename V, typename F>
- fllt_node(P, V)*
- find_the_hole(fllt_node(P, V)& node,
- const P p,
- const image2d<fllt_node(P, V)*>& other_reg)
- {
- fllt_node(P, V)* s = other_reg(p);
- mln_assertion(s);
- while (s->parent() &&
F::opposite::compare(s->parent()->elt().value, node.elt().value))
- //FIXME : Was while (s->parent() && (s->parent()->elt().value <
node.elt().value))
- {
- mln_assertion(s);
- s = s->parent();
- mln_assertion(s);
- }
-// std::cout << " [Find the hole] of " << p
-// << " from " << &node
-// << " return " << s
-// << std::endl;
- return s;
- }
-
- template <typename P, typename V, typename F>
- void
- fill_a_shape(fllt_node(P, V)& node,
- fllt_tree(P, V)& tree,
- const image2d<fllt_node(P, V)*>& node_reg,
- const image2d<fllt_node(P, V)*>& hole_reg)
- {
-// std::cout << "[Start fill_a_shape] " << &node <<
" "
-// << node.elt().holes.npoints()
-// << " holes." << std::endl;
-
- if (node.elt().holes.npoints() == 0)
- {
- // std::cout << "[End fill_a_shape]" << std::endl;
- return;
- }
- mln_piter(set_p<P>) p(node.elt().holes);
- for_all(p)
- {
- bool h = true;
-
- fllt_node(P, V)* hole;
- if (node.elt().brighter == F::parent_is_brighter)
- hole = find_the_hole<P,V,F>(node, point2d(p), hole_reg);
- else
- hole = find_the_hole<P,V,typename F::opposite>(node, point2d(p), node_reg);
-
- mln_assertion(hole);
-
- typename fllt_node(P, V)::children_t::iterator it;
- for (it = node.children().begin();
- it != node.children().end();
- it++)
- {
- // Browse the hole of each child.
- mln_piter(set_p<P>) q((*it)->elt().holes);
- for_all(q)
- {
- fllt_node(P, V)* child_hole = find_the_hole<P,V,F>((**it), point2d(q),
hole_reg);
- if (set::is_subset_of(hole->elt().points,
- child_hole->elt().points))
-
-// if (hole->elt().points < child_hole->elt().points)
- {
- h = false;
- break;
- }
-
- }
- if (!h)
- break;
- }
- if (h)
- move_shape<P,V,F>(node, *hole, tree, hole_reg, node_reg);
- }
-
- node.elt().holes.clear();
- // std::cout << "[end fill_a_shape]" << std::endl;
- }
-
- template <typename P, typename V>
- fllt_tree(P, V)
- merge_trees(fllt_tree(P, V)& lower_tree,
- fllt_tree(P, V)& upper_tree,
- const image2d<fllt_node(P, V)*>& low_reg,
- const image2d<fllt_node(P, V)*>& upp_reg,
- const image2d<V>& ima)
- {
-
- // In order to merge the trees, we only have to find for each shape S
- // with a hole H in it whether one of its children has a hole HŽ
- // containing H. If it is the case, we do nothing. Otherwise, we
- // put the shape of the hole H (and all its descendants) as child of
- // the shape .
- {
- std::cout << "[Merge first tree]------------" << std::endl;
-
- fllt_branch_iter(P, V) p(lower_tree.main_branch());
- for_all(p)
- {
- fllt_node(P, V)& n(p);
- fill_a_shape< P, V, lower<V> >(n, lower_tree, low_reg, upp_reg);
- mln_assertion(lower_tree.check_consistency());
- mln_assertion(upper_tree.check_consistency());
- }
-
- }
-
- {
- std::cout << "[Merge second tree]------------" << std::endl;
-
- fllt_branch_iter(P, V) p(upper_tree.main_branch());
- for_all(p)
- {
- fllt_node(P, V)& n(p);
- fill_a_shape< P, V, upper<V> >(n, upper_tree, upp_reg, low_reg);
- mln_assertion(lower_tree.check_consistency());
- mln_assertion(upper_tree.check_consistency());
- }
- }
-
- fllt_tree(P, V)* main_tree = &lower_tree;
- fllt_tree(P, V)* other_tree = &upper_tree;
-
- if (lower_tree.root()->elt().points.npoints() >= ima.domain().npoints())
- {
- main_tree = &upper_tree;
- other_tree = &lower_tree;
- }
-
- typename fllt_node(P, V)::children_t::iterator it;
- for (it = other_tree->root()->children().begin();
- it != other_tree->root()->children().end(); )
- {
- main_tree->root()->add_child(*it);
- }
- mln_assertion(main_tree->check_consistency());
- return *main_tree;
- }
-
-
- template <typename P, typename V>
void
visualize_deepness(image2d<value::int_u8>& output,
fllt_tree(P, V)& tree)
@@ -743,7 +63,7 @@
for_all(p)
{
//std::cout << (&*p) << ":" << p.deepness() <<
std::endl;
- mln_piter(set_p<point2d>) q((*p).elt().points);
+ mln_piter(p_set<point2d>) q((*p).elt().points);
for_all(q)
{
if (output(q) < p.deepness())
@@ -765,7 +85,7 @@
{
if ((*p).elt().points.npoints() > limit)
{
- mln_piter(set_p<point2d>) q((*p).elt().points);
+ mln_piter(p_set<point2d>) q((*p).elt().points);
for_all(q)
{
mln_niter(neighb2d) n(c4(), q);
@@ -803,9 +123,47 @@
}
}
- template <typename V>
- // Fixme : return type
+ template <typename P, typename V>
void
+ debug(const image2d<V>& ima,
+ fllt_tree(P, V)& tree)
+ {
+
+ std::cout << "4/ Generate outputs." << std::endl;
+
+ image2d<value::int_u8> output (ima.domain());
+ util::tree_to_image (tree, output);
+
+ util::display_tree(ima, tree);
+ draw_tree(ima, tree);
+
+ if (output != ima)
+ std::cerr << "Warning: input and output differ." << std::endl;
+
+ image2d<value::int_u8> out(ima.domain());
+ image2d<value::int_u8> out2(ima.domain());
+ visualize_deepness(out, tree);
+ level::stretch(out, out2);
+ io::pgm::save(out2, "fllt_deepnees.pgm");
+
+ visualize_bounds(out, tree, 800);
+ io::pgm::save(out, "fllt_bounds_800.pgm");
+ visualize_bounds(out, tree, 400);
+ io::pgm::save(out, "fllt_bounds_400.pgm");
+ visualize_bounds(out, tree, 200);
+ io::pgm::save(out, "fllt_bounds_200.pgm");
+ visualize_bounds(out, tree, 100);
+ io::pgm::save(out, "fllt_bounds_100.pgm");
+ visualize_bounds(out, tree, 50);
+ io::pgm::save(out, "fllt_bounds_50.pgm");
+ visualize_bounds(out, tree, 20);
+ io::pgm::save(out, "fllt_bounds_20.pgm");
+ visualize_bounds(out, tree, 8);
+ io::pgm::save(out, "fllt_bounds_8.pgm");
+ }
+
+ template <typename V>
+ fllt_tree(mln_point(image2d<V>), V)
fllt(const image2d<V>& ima)
{
typedef point2d P;
@@ -817,73 +175,13 @@
std::cout << "1/ Compute the lower level set." << std::endl;
lower_tree = compute_level_set<V, lower<V> >(ima, low_reg);
- //draw_tree(ima, lower_tree);
std::cout << "2/ Compute the upper level set." << std::endl;
upper_tree = compute_level_set<V, upper<V> >(ima, upp_reg);
- //draw_tree(ima, upper_tree);
-
std::cout << "3/ Merge the two trees." << std::endl;
-
- // FIXME : the algorithm is contrast invariant.
- // -> the both calls have to give the same result
- // -> check it.
- // FIXME : call merge_tree one time will be enough.
- std::cout << "upp_reg = " << &upp_reg <<
std::endl;
- std::cout << "low_reg = " << &low_reg <<
std::endl;
-
- //fllt_tree(P, V) result_tree = merge_trees(upper_tree, lower_tree, upp_reg,
low_reg, ima);
fllt_tree(P, V) result_tree = merge_trees(lower_tree, upper_tree, low_reg, upp_reg,
ima);
-
- std::cout << "4/ Generate outputs." << std::endl;
-
- image2d<value::int_u8> output (ima.domain ());
- util::tree_to_image (result_tree, output);
-
-
- // io::pgm::save(output, "out_final.pgm");
- // std::cout << "out_final.pgm generate"
- // << std::endl;
-
-
- // util::display_tree(ima, lower_tree);
- //draw_tree(ima, result_tree);
-
- // debug::println(ima);
- // debug::println(output);
-
- // if (output != ima)
- // {
- // std::cerr << "BUG!!!" << std::endl;
- // abort();
- // }
-
- image2d<value::int_u8> viz(ima.domain());
- // image2d<value::int_u8> viz2(ima.domain());
-
- // visualize_deepness(viz, lower_tree);
- // level::stretch(viz, viz2);
- // debug::println(viz);
- // debug::println(viz2);
- // io::pgm::save(viz2, "fllt.pgm");
-
- visualize_bounds(viz, result_tree, 200);
- //debug::println(viz);
- io::pgm::save(viz, "fllt_bounds_200.pgm");
-
- visualize_bounds(viz, result_tree, 100);
- io::pgm::save(viz, "fllt_bounds_100.pgm");
-
- visualize_bounds(viz, result_tree, 50);
- io::pgm::save(viz, "fllt_bounds_50.pgm");
-
- visualize_bounds(viz, result_tree, 20);
- io::pgm::save(viz, "fllt_bounds_20.pgm");
-
- visualize_bounds(viz, result_tree, 8);
- io::pgm::save(viz, "fllt_bounds_8.pgm");
-
+ return result_tree;
}
} // end of namespace mln::fllt
Index: trunk/milena/sandbox/garrigues/fllt_types.hh
===================================================================
--- trunk/milena/sandbox/garrigues/fllt_types.hh (revision 0)
+++ trunk/milena/sandbox/garrigues/fllt_types.hh (revision 1464)
@@ -0,0 +1,71 @@
+// Copyright (C) 2007 EPITA Research and Development Laboratory
+//
+// 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_FIXME_FLLT_TYPES_HH
+# define MLN_FIXME_FLLT_TYPES_HH
+
+/*! \file fllt_types.hh
+ *
+ * \brief Data types used in FLLT.
+ *
+ */
+
+# include <mln/util/tree.hh>
+# include <mln/core/p_set.hh>
+
+# define fllt_tree(P, V) util::tree< mln::fllt::fllt_node_elt<P, V> >
+# define fllt_node(P, V) util::node< mln::fllt::fllt_node_elt<P, V> >
+# define fllt_branch(P, V) util::branch< mln::fllt::fllt_node_elt<P, V> >
+# define fllt_branch_iter(P, V) util::branch_iter< mln::fllt::fllt_node_elt<P,
V> >
+
+namespace mln
+{
+ namespace fllt
+ {
+
+ struct lower_t {};
+ struct upper_t {};
+
+ template <typename P, typename V>
+ struct fllt_node_elt
+ {
+ V value;
+ p_set<P> points;
+ p_set<P> holes;
+ /// Tell if his parent if brighter or not. Nb : if the parent
+ /// if brighter, the node come from the lower level set
+ bool brighter;
+ };
+
+ } // end of namespace mln::fllt
+
+} // end of namespace mln
+
+
+
+#endif // ! MLN_FIXME_FLLT_TYPES_HH
Index: trunk/milena/sandbox/garrigues/fllt_doc.hh
===================================================================
--- trunk/milena/sandbox/garrigues/fllt_doc.hh (revision 0)
+++ trunk/milena/sandbox/garrigues/fllt_doc.hh (revision 1464)
@@ -0,0 +1,86 @@
+// Copyright (C) 2007 EPITA Research and Development Laboratory
+//
+// 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_FIXME_FLLT_DOC_HH
+# define MLN_FIXME_FLLT_DOC_HH
+
+/*! \file fllt_doc.hh
+ *
+ * \brief Notes for FLLT.
+ *
+ */
+
+namespace mln
+{
+ namespace fllt
+ {
+
+ // LOWER LEVEL SET : region = c4, border = c8
+ // UPPER LEVEL SET : region = c8, border = c4
+
+ // 1)
+ // x0 <- a not tagged local mininum of ima.
+ // g <- u(x0)
+
+ // 2)
+ // A <- {x0}
+ // R <- {}
+ // N <- {}
+
+ // 3)
+ // N <- N union {x neighbor of a pixel in a}
+ // gn <- min u(x) x belongs to N.
+ // R <- R union A
+ // tag the pixels of A.
+
+ // 4)
+ // IF g < gn
+ // IF number of conected components of the border > 1
+ // follow each border to find which is the exterior border
+ // and which are the holes. Keep one pixel of each holes.
+ //
+ // Remove from N border of holes.
+ // Recompute gn <- min u(x) x belongs to A
+ //
+ // g <- gn
+ // A <- {x belongs to N / u(x) == g}
+ // N <- N\{x belongs to N / u(x) == g}
+ // GO TO 3)
+ // IF g == gn
+ // A <- {x belongs to N / u(x) == g}
+ // N <- N\{x belongs to N / u(x) == g}
+ // GO TO 3)
+ // IF g > gn
+ // set the gray-level of the pixels of R to g.
+ // GO TO 1)
+
+ } // end of namespace mln::fllt
+
+} // end of namespace mln
+
+#endif // ! MLN_FIXME_FLLT_DOC_HH
Index: trunk/milena/sandbox/garrigues/test_fllt13.cc
===================================================================
--- trunk/milena/sandbox/garrigues/test_fllt13.cc (revision 1463)
+++ trunk/milena/sandbox/garrigues/test_fllt13.cc (revision 1464)
@@ -19,21 +19,12 @@
using namespace mln;
using typename value::int_u8;
-// int vs[3][6] = { {0, 0, 0, 1, 1, 1},
-// {0, 1, 0, 1, 0, 1},
-// {0, 0, 0, 1, 1, 1} };
-
-
- int vs[5][8] = {
-{ 1, 1, 1, 1, 1, 1, 1, 4 },
+ int vs[5][8] = { { 1, 1, 1, 1, 1, 1, 1, 4 },
{ 1, 4, 1, 1, 1, 1, 4, 1 },
{ 1, 2, 1, 1, 1, 4, 1, 1 },
{ 1, 3, 1, 1, 4, 1, 1, 1 },
{ 1, 1, 1, 4, 1, 1, 1, 1 } };
image2d<int> ima(make::image2d(vs));
- image2d<int_u8> out(ima.domain());
-
- level::fill(out, ima);
fllt::fllt(ima);
}
Index: trunk/milena/sandbox/garrigues/test_fllt2.cc
===================================================================
--- trunk/milena/sandbox/garrigues/test_fllt2.cc (revision 1463)
+++ trunk/milena/sandbox/garrigues/test_fllt2.cc (revision 1464)
@@ -1,4 +1,4 @@
-# include "fllt2.hh"
+# include "fllt_optimized.hh"
# include <mln/core/image2d.hh>
# include <mln/core/clone.hh>
# include <mln/value/int_u8.hh>
@@ -27,14 +27,7 @@
w_window2d_int w_win = make::w_window2d(ws);
image2d<int> ima = convert::to_image(w_win);
- fllt::fllt(ima);
-
-// image2d<value::int_u8> ima = io::pgm::load("../../img/tiny.pgm");
-
-// image2d<int> ima_int(ima.domain());
-
-// level::fill(ima_int, ima);
-// debug::println(ima);
-// fllt::fllt(ima_int);
+ fllt_tree(point2d, int) t = fllt::fllt(ima);
+ fllt::debug(ima, t);
}