- Olena-patches

1753: Fix the pretty-printer of util::internal::graph_base.
by Roland Levillain 27 Feb '08

27 Feb '08

https://svn.lrde.epita.fr/svn/oln/trunk Index: ChangeLog from Roland Levillain <roland(a)lrde.epita.fr> Fix the pretty-printer of util::internal::graph_base. * milena/mln/util/internal/graph_base.hh (node<void>::edges): Use a std::vector (as in node<T>), not a std::list. (util::internal::graph_base<N, E>::print_debug): Fix the iteration on the edges adjacent to a vertex. * milena/tests/core/graph_image.cc: Exercise util::internal::graph_base<N, E>::print_debug mln/util/internal/graph_base.hh | 7 +++++-- tests/core/graph_image.cc | 1 + 2 files changed, 6 insertions(+), 2 deletions(-) Index: milena/tests/core/graph_image.cc --- milena/tests/core/graph_image.cc (revision 1753) +++ milena/tests/core/graph_image.cc (working copy) @@ -75,6 +75,7 @@ `-------*/ p_graph<point2d> pg(g); + g.print_debug(std::cout); /*-------------. | Graph image. | Index: milena/mln/util/internal/graph_base.hh --- milena/mln/util/internal/graph_base.hh (revision 1753) +++ milena/mln/util/internal/graph_base.hh (working copy) @@ -82,7 +82,7 @@ template<> struct node<void> { - std::list<edge_id> edges; + std::vector<edge_id> edges; }; @@ -386,7 +386,10 @@ n != nodes_.end (); ++n, ++i) { ostr << "node: " <edges.begin(); + /* FIXME: We shouldn't manipulate std::vector<edge_id> + directly, but use a typedef instead. */ + for (typename std::vector<util::edge_id>::const_iterator e = + (*n)->edges.begin(); e != (*n)->edges.end(); ++e) ostr << *e << " "; ostr << std::endl;

1 0

milena r1753: Split fllt.hh in my sanbox
by Matthieu Garrigues 26 Feb '08

26 Feb '08

URL: https://svn.lrde.epita.fr/svn/oln/trunk/milena ChangeLog: 2008-02-26 Matthieu Garrigues <garrigues(a)lrde.epita.fr> Split fllt.hh in my sanbox. * sandbox/garrigues/fllt/compute_level_set.hh: New, compute the level sets. * sandbox/garrigues/fllt/debug.hh: New, debug routines for FLLT. * sandbox/garrigues/fllt/doc.hh: New, some comments from the monasse's paper. * sandbox/garrigues/fllt/lower.hh: New, the struct used to compute the lower level set. * sandbox/garrigues/fllt/upper.hh: New, the struct used to compute the upper level set. * sandbox/garrigues/fllt/types.hh: New, type defined for FLLT. * sandbox/garrigues/fllt/merge.hh: New, routines to merge the lower level set and the upper level set. * sandbox/garrigues/fllt/fllt.hh: Split this file. * sandbox/garrigues/fllt/test_fllt10.cc: Update includes. --- compute_level_set.hh | 410 ++++++++++++++++++++++++++++ debug.hh | 122 ++++++++ doc.hh | 90 ++++++ fllt.hh | 724 --------------------------------------------------- lower.hh | 86 ++++++ merge.hh | 216 +++++++++++++++ test_fllt10.cc | 2 types.hh | 71 +++++ upper.hh | 85 +++++ 9 files changed, 1090 insertions(+), 716 deletions(-) Index: trunk/milena/sandbox/garrigues/fllt/test_fllt10.cc =================================================================== --- trunk/milena/sandbox/garrigues/fllt/test_fllt10.cc (revision 1752) +++ trunk/milena/sandbox/garrigues/fllt/test_fllt10.cc (revision 1753) @@ -1,4 +1,4 @@ -# include "fllt2.hh" +# include "fllt.hh" # include <mln/core/image2d.hh> # include <mln/core/clone.hh> # include <mln/value/int_u8.hh> Index: trunk/milena/sandbox/garrigues/fllt/lower.hh =================================================================== --- trunk/milena/sandbox/garrigues/fllt/lower.hh (revision 0) +++ trunk/milena/sandbox/garrigues/fllt/lower.hh (revision 1753) @@ -0,0 +1,86 @@ +// Copyright (C) 2007, 2008 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 lower.hh + * + * \brief Lower level set for Fast level line transform. + * + */ + +# include <mln/core/neighb2d.hh> +# include <mln/labeling/regional_minima.hh> +# include <mln/accu/min.hh> + +# include "upper.hh" + +namespace mln +{ + namespace fllt + { + + //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 L> + static mln_ch_value(I, L) + regional_extremum(const Image& input, const Neighborhood<N>& nbh, L& nlabels) + { + return labeling::regional_minima(input, nbh, 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/fllt/upper.hh =================================================================== --- trunk/milena/sandbox/garrigues/fllt/upper.hh (revision 0) +++ trunk/milena/sandbox/garrigues/fllt/upper.hh (revision 1753) @@ -0,0 +1,85 @@ +// Copyright (C) 2007, 2008 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 Upper level set for Fast level line transform. + * + */ + +# include <mln/core/neighb2d.hh> +# include <mln/labeling/regional_maxima.hh> +# include <mln/accu/max.hh> + +# include "lower.hh" + +namespace mln +{ + namespace fllt + { + + //Fwd declarations. + template <typename V> struct lower; + + // 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 L> + static mln_ch_value(I, L) + regional_extremum(const Image& input, const Neighborhood<N>& nbh, L& nlabels) + { + return labeling::regional_maxima(input, nbh, 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/fllt/merge.hh =================================================================== --- trunk/milena/sandbox/garrigues/fllt/merge.hh (revision 0) +++ trunk/milena/sandbox/garrigues/fllt/merge.hh (revision 1753) @@ -0,0 +1,216 @@ +// Copyright (C) 2007, 2008 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 merge.hh + * + * \brief Merge for Fast level line transform. + * + */ + +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) + { + // 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 " < + 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(p_set) 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(p_set) 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_ind(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_ind(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; + } + + + } // end of namespace mln::fllt + +} // end of namespace mln + + + +#endif // ! MLN_FIXME_FLLT_MERGE_HH 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 1753) @@ -0,0 +1,71 @@ +// Copyright (C) 2007, 2008 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 types.hh + * + * \brief Types for Fast level line transform. + * + */ + +# include <mln/core/p_set.hh> +# include <mln/util/tree.hh> +# include <mln/util/branch_iter_ind.hh> + +namespace mln +{ + namespace fllt + { + + template <typename P, typename V> + struct fllt_node_elt + { + V value; + p_set points; + p_set 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::tree_node< fllt_node_elt<P, V> > +# define fllt_branch(P, V) util::branch< fllt_node_elt<P, V> > +# define fllt_branch_iter_ind(P, V) util::branch_iter_ind< fllt_node_elt<P, V> > + + // # define fllt_node(P, V) typename fllt_tree(P, V)::node_t + + } // 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 1753) @@ -0,0 +1,90 @@ +// Copyright (C) 2007, 2008 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 doc.hh + * + * \brief Compute Level Set for Fast level line transform. + * + */ + +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/fllt/debug.hh =================================================================== --- trunk/milena/sandbox/garrigues/fllt/debug.hh (revision 0) +++ trunk/milena/sandbox/garrigues/fllt/debug.hh (revision 1753) @@ -0,0 +1,122 @@ +// Copyright (C) 2007, 2008 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_DEBUG_HH +# define MLN_FIXME_FLLT_DEBUG_HH + +/*! \file debug.hh + * + * \brief Debug for Fast level line transform. + * + */ + +# include "types.hh" + +namespace mln +{ + namespace fllt + { + + + template <typename P, typename V> + void + visualize_deepness(image2d<value::int_u8>& output, + fllt_tree(P, V)& tree) + { + fllt_branch_iter_ind(P, V) p(tree.main_branch()); + level::fill(output, 0); + for_all(p) + { + //std::cout << (&*p) << ":" << p.deepness() << std::endl; + mln_piter(p_set<point2d>) q((*p).elt().points); + for_all(q) + { + if (output(q) < p.deepness()) + output(q) = p.deepness(); + } + } + } + + + template <typename P, typename V> + void + visualize_bounds(image2d<value::int_u8>& output, + fllt_tree(P, V)& tree, + unsigned limit) + { + fllt_branch_iter_ind(P, V) p(tree.main_branch()); + level::fill(output, 255); + for_all(p) + { + if ((*p).elt().points.npoints() > limit) + { + mln_piter(p_set<point2d>) q((*p).elt().points); + for_all(q) + { + mln_niter(neighb2d) n(c4(), q); + bool is_border = false; + for_all (n) + if (!((*p).elt().points).has (n)) + is_border = true; + if (is_border) + output(q) = 0; + } + } + } + } + + template <typename P, typename V> + void + draw_tree(const image2d<V>& ima, + fllt_tree(P, V)& tree) + { + fllt_branch_iter_ind(P, V) p(tree.main_branch()); + for_all(p) + { + std::cout << "region mere : " << (*p).parent() << std::endl; + std::cout << " ^" << std::endl; + std::cout << " |" << std::endl; + std::cout << "region : " << &*p + << " value = " << (*p).elt().value << std::endl + << " holes : " + << (*p).elt().holes.npoints() + << (*p).elt().holes + << std::endl; + + debug::println(ima | (*p).elt().points); + std::cout << std::endl; + } + } + + } // end of namespace mln::fllt + +} // end of namespace mln + + + +#endif // ! MLN_FIXME_FLLT_DEBUG_HH Index: trunk/milena/sandbox/garrigues/fllt/fllt.hh =================================================================== --- trunk/milena/sandbox/garrigues/fllt/fllt.hh (revision 1752) +++ trunk/milena/sandbox/garrigues/fllt/fllt.hh (revision 1753) @@ -1,4 +1,4 @@ -// Copyright (C) 2007 EPITA Research and Development Laboratory +// Copyright (C) 2007, 2008 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 @@ -78,725 +78,19 @@ # include <mln/level/compare.hh> # include <mln/io/pgm/save.hh> -namespace mln -{ - namespace fllt - { - - template <typename P, typename V> - struct fllt_node_elt - { - V value; - p_set points; - p_set 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::tree_node< fllt_node_elt<P, V> > -# define fllt_branch(P, V) util::branch< fllt_node_elt<P, V> > -# define fllt_branch_iter_ind(P, V) util::branch_iter_ind< 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 V> - void step1 (const image2d<V>& ima, - point2d p, - V& g, - point2d& x0) - { - //std::cout << "entering step 1" << std::endl; - // x0 <- a not tagged local mininum of ima. - //std::cout << std::endl << "x0 = " < - void step2 (p_set& A, - p_set& R, - p_set& N, - point2d& x0) - { - //std::cout << "entering step 2" << std::endl; - // A <- {x0} - A.clear(); - A.insert(x0); - // R <- {} - R.clear(); - // N <- {} - N.clear(); - //std::cout << "exiting step 2" << std::endl; - } - - - template <typename V, typename P, typename F> - void step3 (const image2d<V>& u, - image2d<bool>& tagged, - p_set& A, - p_set& R, - p_set& N, - V& gn) - { - static bool finished = false; - //std::cout << "entering step 3" << std::endl; - - // Stop the algorithm. - if (finished) - { finished = false; gn -= 2 * F::inc; return; } - - // N <- N union {x neighbor of a pixel in a\R} - mln_piter(p_set) qa(A); - for_all(qa) - { - mln_niter(neighb2d) n(F::reg_nbh(), qa); - for_all (n) - if (!R.has (n)) - 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 ((u | set::inter(N, u.domain())).npoints() > 0) - gn = level::compute< typename F::accu_for_gn >(u | set::inter(N, u.domain())); - else - { - finished = true; - gn += F::inc; - } - //std::cout << std::endl << "gN = " << gn << std::endl; - // R <- R union A - // tag the pixels of A. - - for_all(qa) - { - R.insert(qa); - tagged(qa) = true; - } - //std::cout << "exiting step 3" << std::endl; - } - - - /// IF g < gn. - template <typename V, typename P, typename F> - void step4_1 (image2d<V>& u, - p_set& A, - p_set& R, - p_set& N, - V& g, - V& gn, - fllt_node(P, V)*& current_region, - image2d<fllt_node(P, V)*>& regions - ) - { - //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 ((R.bbox() < u.domain()) || (R.npoints() == u.domain().npoints())) - { - mln_piter(p_set) p(R); - current_region = new fllt_node(P, V)(); - current_region->elt().brighter = F::parent_is_brighter; - current_region->elt().value = g; - for_all(p) - { - current_region->elt().points.insert(p); - - if (regions(p) == 0) - { - //current_region->elt().points.insert(p); - regions(p) = current_region; - } - else - { - if (regions(p)->parent() == 0) - regions(p)->set_parent(current_region); - } - } - - - // Count the number of conected components of the border of R. - static image2d<unsigned> tmp(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(p_set) z(N); - for_all(z) - { - mln_assertion(border_ima.owns_(z)); - border_ima(z) = true; - } - unsigned n; - tmp = labeling::level(border_ima, true, F::bdr_nbh(), 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. - 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 - } - } - - } - g = gn; - // A <- {x belongs to N / u(x) == g} - A.clear(); - A = set::uni(A, set::inter(N, u.domain()) | pw::value(u) == pw::cst(g)); - // N <- N\{x belongs to N / u(x) == g} - N = set::diff(N, set::inter(N, u.domain()) | pw::value(u) == pw::cst(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 (const image2d<V>& u, - p_set& A, - p_set& N, - V& g, - fllt_node(P, V)* current_region, - image2d<fllt_node(P, V)*>& regions - ) - { - //std::cout << "entering step 4_2" << std::endl; - - // A <- {x belongs to N / u(x) == g} - A = set::uni(A, set::inter(N, u.domain()) | pw::value(u) == pw::cst(g)); - // N <- N\{x belongs to N / u(x) == g} - N = set::diff(N, set::inter(N, u.domain()) | pw::value(u) == pw::cst(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 (image2d<V>& u, - const image2d<bool>& tagged, - const p_set& 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(p_set) p(R); - for_all(p) - { - mln_assertion (tagged(p)); - u (p) = g; - } - - //std::cout << "exiting step 4_3" << std::endl; - - } - - - template <typename V, typename F> - fllt_tree(point2d, V)& - compute_level_set(const image2d<V>& ima, - image2d< fllt_node(point2d, V)* >& regions) - { - typedef point2d P; - typedef image2d<V> I; - - // FIXME: not nice. - typedef mln::image_if< - mln::image2d<unsigned>, - mln::fun::greater_p2b_expr_<mln::pw::value_<mln::image2d<unsigned> >, - mln::pw::cst_<int> > - > I_IF; - - // Check - mln_assertion(ima.domain() == regions.domain()); - - // Declarations. - p_set R, N, A; - V g, gn; - point2d x0; - image2d<unsigned> min_locals(ima.domain()); - image2d<V> u = clone(ima); - border::fill(u, 0); - - //std::cout << "image U:" << std::endl; - // debug::println_with_border(u); - image2d<bool> tagged(ima.domain()); - fllt_node(P, V)* current_region; - - // INIT - R.clear(); - N.clear(); - A.clear(); - g= 0; - gn = 0; - current_region = 0; - - level::fill(regions, 0); - level::fill(tagged, false); - - // Get the locals extremums - unsigned nlabels; - min_locals = F::regional_extremum(ima, F::reg_nbh(), 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 (tagged(p)) - continue; - - step1(ima, p, g, x0); - step2(A, R, N, x0); - while (1) - { - //std::cout << "g = " << g << std::endl; - step3<V, P, F>(u, tagged, A, R, N, gn); - /// step4. - if (F::compare(g, gn)) - { - step4_1<V, P, F>(u, A, R, N, g, gn, current_region, regions); - // GO TO 3) - continue; - } - - - if (g == gn) - { - step4_2(u, A, N, g, current_region, regions); - // GO TO 3) - continue; - } - - - if (!F::compare(g, gn)) - { - step4_3(u, tagged, R, g); - // GO TO 1) - break; - } - } - //std::cout << "current_region = " << current_region << std::endl; - } - } // end of Algorithm - - image2d<value::int_u8> output (ima.domain ()); - fllt_tree(P, V)& tree = *new fllt_tree(P, V)(current_region); - util::tree_to_image (tree, output); - - // util::display_tree(ima, tree); - - // debug::println(output); - // std::cout << std::endl; - // debug::println(ima); - - // if (output != ima) - // { - // std::cerr << "BUG!!!" << std::endl; - // abort(); - // } - - // io::pgm::save(output, "out.pgm"); - // std::cout << "out.pgm generate" - // << std::endl; - - - // debug::println(regions); - //debug::println(ima | 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 L> - static mln_ch_value(I, L) - regional_extremum(const Image& input, const Neighborhood<N>& nbh, L& nlabels) - { - return labeling::regional_minima(input, nbh, 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(); } - - }; - - +# include "types.hh" +# include "debug.hh" - // UPPER LEVEL SET : region = c8, border = c4 - template <typename V> - struct upper - { - typedef lower<V> opposite; +# include "lower.hh" +# include "upper.hh" - static bool - compare(const V& u, const V& v) - { - return u > v; - } - - template <typename I, typename N, typename L> - static mln_ch_value(I, L) - regional_extremum(const Image& input, const Neighborhood<N>& nbh, L& nlabels) - { - return labeling::regional_maxima(input, nbh, nlabels); - } +# include "compute_level_set.hh" +# include "merge.hh" - 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 " < - 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(p_set) 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(p_set) 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_ind(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_ind(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) - { - fllt_branch_iter_ind(P, V) p(tree.main_branch()); - level::fill(output, 0); - for_all(p) - { - //std::cout << (&*p) << ":" << p.deepness() << std::endl; - mln_piter(p_set<point2d>) q((*p).elt().points); - for_all(q) - { - if (output(q) < p.deepness()) - output(q) = p.deepness(); - } - } - } - - - template <typename P, typename V> - void - visualize_bounds(image2d<value::int_u8>& output, - fllt_tree(P, V)& tree, - unsigned limit) - { - fllt_branch_iter_ind(P, V) p(tree.main_branch()); - level::fill(output, 255); - for_all(p) - { - if ((*p).elt().points.npoints() > limit) - { - mln_piter(p_set<point2d>) q((*p).elt().points); - for_all(q) - { - mln_niter(neighb2d) n(c4(), q); - bool is_border = false; - for_all (n) - if (!((*p).elt().points).has (n)) - is_border = true; - if (is_border) - output(q) = 0; - } - } - } - } - - template <typename P, typename V> - void - draw_tree(const image2d<V>& ima, - fllt_tree(P, V)& tree) +namespace mln { - fllt_branch_iter_ind(P, V) p(tree.main_branch()); - for_all(p) + namespace fllt { - std::cout << "region mere : " << (*p).parent() << std::endl; - std::cout << " ^" << std::endl; - std::cout << " |" << std::endl; - std::cout << "region : " << &*p - << " value = " << (*p).elt().value << std::endl - << " holes : " - << (*p).elt().holes.npoints() - << (*p).elt().holes - << std::endl; - - debug::println(ima | (*p).elt().points); - std::cout << std::endl; - } - } template <typename V> // Fixme : return type Index: trunk/milena/sandbox/garrigues/fllt/compute_level_set.hh =================================================================== --- trunk/milena/sandbox/garrigues/fllt/compute_level_set.hh (revision 0) +++ trunk/milena/sandbox/garrigues/fllt/compute_level_set.hh (revision 1753) @@ -0,0 +1,410 @@ +// Copyright (C) 2007, 2008 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_COMPUTE_LEVEL_SET_HH +# define MLN_FIXME_FLLT_COMPUTE_LEVEL_SET_HH + +/*! \file compute_level_set.hh + * + * \brief Compute Level Set for Fast level line transform. + * + */ + +namespace mln +{ + namespace fllt + { + + + template <typename V> + void step1 (const image2d<V>& ima, + point2d p, + V& g, + point2d& x0) + { + //std::cout << "entering step 1" << std::endl; + // x0 <- a not tagged local mininum of ima. + //std::cout << std::endl << "x0 = " < + void step2 (p_set& A, + p_set& R, + p_set& N, + point2d& x0) + { + //std::cout << "entering step 2" << std::endl; + // A <- {x0} + A.clear(); + A.insert(x0); + // R <- {} + R.clear(); + // N <- {} + N.clear(); + //std::cout << "exiting step 2" << std::endl; + } + + + template <typename V, typename P, typename F> + void step3 (const image2d<V>& u, + image2d<bool>& tagged, + p_set& A, + p_set& R, + p_set& N, + V& gn) + { + static bool finished = false; + //std::cout << "entering step 3" << std::endl; + + // Stop the algorithm. + if (finished) + { finished = false; gn -= 2 * F::inc; return; } + + // N <- N union {x neighbor of a pixel in a\R} + mln_piter(p_set) qa(A); + for_all(qa) + { + mln_niter(neighb2d) n(F::reg_nbh(), qa); + for_all (n) + if (!R.has (n)) + 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 ((u | set::inter(N, u.domain())).npoints() > 0) + gn = level::compute< typename F::accu_for_gn >(u | set::inter(N, u.domain())); + else + { + finished = true; + gn += F::inc; + } + //std::cout << std::endl << "gN = " << gn << std::endl; + // R <- R union A + // tag the pixels of A. + + for_all(qa) + { + R.insert(qa); + tagged(qa) = true; + } + //std::cout << "exiting step 3" << std::endl; + } + + + /// IF g < gn. + template <typename V, typename P, typename F> + void step4_1 (image2d<V>& u, + p_set& A, + p_set& R, + p_set& N, + V& g, + V& gn, + fllt_node(P, V)*& current_region, + image2d<fllt_node(P, V)*>& regions + ) + { + //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 ((R.bbox() < u.domain()) || (R.npoints() == u.domain().npoints())) + { + mln_piter(p_set) p(R); + current_region = new fllt_node(P, V)(); + current_region->elt().brighter = F::parent_is_brighter; + current_region->elt().value = g; + for_all(p) + { + current_region->elt().points.insert(p); + + if (regions(p) == 0) + { + //current_region->elt().points.insert(p); + regions(p) = current_region; + } + else + { + if (regions(p)->parent() == 0) + regions(p)->set_parent(current_region); + } + } + + + // Count the number of conected components of the border of R. + static image2d<unsigned> tmp(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(p_set) z(N); + for_all(z) + { + mln_assertion(border_ima.owns_(z)); + border_ima(z) = true; + } + unsigned n; + tmp = labeling::level(border_ima, true, F::bdr_nbh(), 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. + 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 + } + } + + } + g = gn; + // A <- {x belongs to N / u(x) == g} + A.clear(); + A = set::uni(A, set::inter(N, u.domain()) | pw::value(u) == pw::cst(g)); + // N <- N\{x belongs to N / u(x) == g} + N = set::diff(N, set::inter(N, u.domain()) | pw::value(u) == pw::cst(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 (const image2d<V>& u, + p_set& A, + p_set& N, + V& g, + fllt_node(P, V)* current_region, + image2d<fllt_node(P, V)*>& regions + ) + { + //std::cout << "entering step 4_2" << std::endl; + + // A <- {x belongs to N / u(x) == g} + A = set::uni(A, set::inter(N, u.domain()) | pw::value(u) == pw::cst(g)); + // N <- N\{x belongs to N / u(x) == g} + N = set::diff(N, set::inter(N, u.domain()) | pw::value(u) == pw::cst(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 (image2d<V>& u, + const image2d<bool>& tagged, + const p_set& 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(p_set) p(R); + for_all(p) + { + mln_assertion (tagged(p)); + u (p) = g; + } + + //std::cout << "exiting step 4_3" << std::endl; + + } + + + template <typename V, typename F> + fllt_tree(point2d, V)& + compute_level_set(const image2d<V>& ima, + image2d< fllt_node(point2d, V)* >& regions) + { + typedef point2d P; + typedef image2d<V> I; + + // FIXME: not nice. + typedef mln::image_if< + mln::image2d<unsigned>, + mln::fun::greater_p2b_expr_<mln::pw::value_<mln::image2d<unsigned> >, + mln::pw::cst_<int> > + > I_IF; + + // Check + mln_assertion(ima.domain() == regions.domain()); + + // Declarations. + p_set R, N, A; + V g, gn; + point2d x0; + image2d<unsigned> min_locals(ima.domain()); + image2d<V> u = clone(ima); + border::fill(u, 0); + + //std::cout << "image U:" << std::endl; + // debug::println_with_border(u); + image2d<bool> tagged(ima.domain()); + fllt_node(P, V)* current_region; + + // INIT + R.clear(); + N.clear(); + A.clear(); + g= 0; + gn = 0; + current_region = 0; + + level::fill(regions, 0); + level::fill(tagged, false); + + // Get the locals extremums + unsigned nlabels; + min_locals = F::regional_extremum(ima, F::reg_nbh(), 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 (tagged(p)) + continue; + + step1(ima, p, g, x0); + step2(A, R, N, x0); + while (1) + { + //std::cout << "g = " << g << std::endl; + step3<V, P, F>(u, tagged, A, R, N, gn); + /// step4. + if (F::compare(g, gn)) + { + step4_1<V, P, F>(u, A, R, N, g, gn, current_region, regions); + // GO TO 3) + continue; + } + + + if (g == gn) + { + step4_2(u, A, N, g, current_region, regions); + // GO TO 3) + continue; + } + + + if (!F::compare(g, gn)) + { + step4_3(u, tagged, R, g); + // GO TO 1) + break; + } + } + //std::cout << "current_region = " << current_region << std::endl; + } + } // end of Algorithm + + image2d<value::int_u8> output (ima.domain ()); + fllt_tree(P, V)& tree = *new fllt_tree(P, V)(current_region); + util::tree_to_image (tree, output); + + // util::display_tree(ima, tree); + + // debug::println(output); + // std::cout << std::endl; + // debug::println(ima); + + // if (output != ima) + // { + // std::cerr << "BUG!!!" << std::endl; + // abort(); + // } + + // io::pgm::save(output, "out.pgm"); + // std::cout << "out.pgm generate" + // << std::endl; + + + // debug::println(regions); + //debug::println(ima | 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 + + } // end of namespace mln::fllt + +} // end of namespace mln + + + +#endif // ! MLN_FIXME_FLLT_COMPUTE_LEVEL_SET_HH

1 0

milena r1752: Chamfer DT visual tests (beautiful images inside !)
by Etienne FOLIO 26 Feb '08

26 Feb '08

URL: https://svn.lrde.epita.fr/svn/oln/trunk/milena ChangeLog: 2008-02-26 Etienne FOLIO <folio(a)lrde.epita.fr> Chamfer DT visual tests (beautiful images inside !). * sandbox/folio/chamfer_dt.cc: New visual tests inside (Beware! There's a picasso painting here !). --- chamfer_dt.cc | 36 +++++++++++++++++++++++++++++++----- 1 file changed, 31 insertions(+), 5 deletions(-) Index: trunk/milena/sandbox/folio/chamfer_dt.cc =================================================================== --- trunk/milena/sandbox/folio/chamfer_dt.cc (revision 1751) +++ trunk/milena/sandbox/folio/chamfer_dt.cc (revision 1752) @@ -29,7 +29,6 @@ #include <mln/core/image2d.hh> #include <mln/level/fill.hh> -#include <mln/debug/println.hh> #include <mln/make/win_chamfer.hh> #include <mln/accu/min.hh> @@ -40,13 +39,13 @@ { template<typename I> inline - mln_ch_value(I, float) + mln_ch_value(I, int) chamfer_dt(const Image& input_) { const I& input = exact(input_); mln_precondition(input.has_data()); - mln_ch_value(I, float) output; + mln_ch_value(I, int) output; initialize(output, input); accu::min_<int> min; @@ -98,10 +97,18 @@ #endif /* ! CHAMFER_DT_HH */ +#include <mln/debug/println.hh> +#include <mln/level/stretch.hh> +#include <mln/value/int_u8.hh> +#include <mln/io/pgm/save.hh> +#include <mln/io/pgm/load.hh> +#include <tests/data.hh> + int main() { using namespace mln; + { image2d<bool> ima(5,5); bool vals[] = { 1, 1, 1, 0, 0, 0, 0, 1, 0, 0, @@ -110,7 +117,26 @@ 0, 0, 0, 0, 0 }; level::fill(ima, vals); - debug::println(ima); - debug::println(chamfer_dt(ima)); + + image2d<int> out = chamfer_dt(ima); + debug::println(out); + + image2d<value::int_u8> out2; + initialize(out2, out); + level::stretch(out, out2); + io::pgm::save(out2, "./out.pgm"); + } + + { + image2d<value::int_u8> ima; + io::pgm::load(ima, MLN_IMG_DIR "/picasso.pgm"); + + image2d<int> out = chamfer_dt(ima); + + image2d<value::int_u8> out2; + initialize(out2, out); + level::stretch(out, out2); + io::pgm::save(out2, "./out2.pgm"); + } }

1 0

milena r1749: Rename util::node (of util::tree) as util::tree_node
by Matthieu Garrigues 26 Feb '08

26 Feb '08

URL: https://svn.lrde.epita.fr/svn/oln/trunk/milena ChangeLog: 2008-02-26 Matthieu Garrigues <garrigues(a)lrde.epita.fr> Rename util::node (of util::tree) as util::tree_node. * mln/util/branch_iter.hh, * mln/util/branch_iter_ind.hh, * mln/util/tree.hh, * mln/util/tree_to_image.hh: Update. --- branch_iter.hh | 14 +-- branch_iter_ind.hh | 16 ++-- tree.hh | 190 ++++++++++++++++++++++++++--------------------------- tree_to_image.hh | 38 +++++----- 4 files changed, 129 insertions(+), 129 deletions(-) Index: trunk/milena/mln/util/tree.hh =================================================================== --- trunk/milena/mln/util/tree.hh (revision 1748) +++ trunk/milena/mln/util/tree.hh (revision 1749) @@ -48,100 +48,100 @@ { /// Fwd declarations. - template <typename T> class node; + template <typename T> class tree_node; template <typename T> class tree; template <typename T> class branch; - /*! \brief Class of generic node for tree. + /*! \brief Class of generic tree_node for tree. * */ template <typename T> - class node + class tree_node { public: - typedef std::vector< node<T>* > children_t; + typedef std::vector< tree_node<T>* > children_t; /*! \brief Constructor. * */ - node(); + tree_node(); /*! \brief Constructor. * - * \param[in] elt The element of node. + * \param[in] elt The element of tree_node. */ - node(T elt); + tree_node(T elt); /*! \brief The getter of the element. * - * \return The element of the node. + * \return The element of the tree_node. */ T& elt(); /*! \brief The const getter of the element. * - * \return The element of the node in const. + * \return The element of the tree_node in const. */ const T& elt() const; /*! \brief The getter of the children. * - * \return The children of the node. + * \return The children of the tree_node. */ children_t& children(); /*! \brief The getter of the children. * - * \return The children of the node in const. + * \return The children of the tree_node in const. */ const children_t& children() const; /*! \brief The getter of the parent. * - * \return The parent of the node. + * \return The parent of the tree_node. */ - node<T>* parent(); + tree_node<T>* parent(); - /*! \brief Create a node with \p elt which become the child of - * the current node. + /*! \brief Create a tree_node with \p elt which become the child of + * the current tree_node. * * \param[in] elt The element of the new child to add. * - * \return The new node created. + * \return The new tree_node created. */ - node<T>* add_child(T elt); + tree_node<T>* add_child(T elt); - /*! \brief Bind \p node to the current node and become its + /*! \brief Bind \p tree_node to the current tree_node and become its * child. * - * \param[in] node The new child node. + * \param[in] tree_node The new child tree_node. * - * \return The child node. + * \return The child tree_node. */ - node<T>* add_child(node<T>* node); + tree_node<T>* add_child(tree_node<T>* tree_node); - /*! \brief Bind \p node to the current node and become its + /*! \brief Bind \p tree_node to the current tree_node and become its * parent. * - * \param[in] parent The new parent node. + * \param[in] parent The new parent tree_node. * */ - void set_parent(node<T>* parent); + void set_parent(tree_node<T>* parent); - /*! \brief Delete the current node. + /*! \brief Delete the current tree_node. * */ - node<T>* delete_node(); + tree_node<T>* delete_tree_node(); /*! \brief Print on \p ostr the arborescence with the current - * node as root. + * tree_node as root. * * \param[in] ostr The output stream. * \param[in] level The deep level @@ -149,35 +149,35 @@ */ void print(std::ostream& ostr, int level = 0); - /*! \brief Check the consistency of the node. + /*! \brief Check the consistency of the tree_node. * * \return true if no error, else false. */ bool check_consistency(); - /*! \brief Search the node with value \p elt in the arborescence - * of the current node. + /*! \brief Search the tree_node with value \p elt in the arborescence + * of the current tree_node. * - * \param[in] elt The value of the searched node. + * \param[in] elt The value of the searched tree_node. * - * \return If not found 0 else the node with \p elt value. + * \return If not found 0 else the tree_node with \p elt value. */ - node<T>* search(T& elt); + tree_node<T>* search(T& elt); /// The using method for method search. - int search_rec(node<T>** res, T& elt); + int search_rec(tree_node<T>** res, T& elt); private: /// The value. T elt_; - /// The node parent. - node<T>* parent_; + /// The tree_node parent. + tree_node<T>* parent_; /// The children. - std::vector< node<T>* > child_; + std::vector< tree_node<T>* > child_; }; @@ -190,7 +190,7 @@ { public: - typedef node<T> node_t; + typedef tree_node<T> tree_node_t; /*! \brief Constructor. * @@ -201,18 +201,18 @@ * * \param[in] root The root of the tree. */ - tree(node<T>* root); + tree(tree_node<T>* root); /*! \brief The getter of the root. * - * \return The root's node of the the current tree. + * \return The root's tree_node of the the current tree. */ - node<T>* root(); + tree_node<T>* root(); /*! \brief Convert the tree into brach. * - * \return The root's node of the the current tree. + * \return The root's tree_node of the the current tree. */ branch<T> main_branch(); @@ -225,22 +225,22 @@ /*! \brief Bind a new tree upper the current. * - * \param[in] elt The new value of the new node of the new tree + * \param[in] elt The new value of the new tree_node of the new tree * add upper the current. */ void add_tree_up (T& elt); /*! \brief Bind a new tree downer the current. * - * \param[in] elt The new value of the new node of the new tree + * \param[in] elt The new value of the new tree_node of the new tree * add downer the current. */ void add_tree_down (T& elt); private: - /// The root's node. - node<T>* root_; + /// The root's tree_node. + tree_node<T>* root_; }; @@ -257,13 +257,13 @@ * \param[in] tree The tree of the branch. * \param[in] apex The apex of the branch. */ - branch(tree<T>& tree, node<T>& apex); + branch(tree<T>& tree, tree_node<T>& apex); /*! \brief The getter of the appex. * - * \return The node appex of the current branch. + * \return The tree_node appex of the current branch. */ - node<T>& apex(); + tree_node<T>& apex(); /*! \brief The getter of the tree. * @@ -275,8 +275,8 @@ /// The tree of this branch. util::tree<T>& tree_; - /// The node apex of this branch. - node<T>& apex_; + /// The tree_node apex of this branch. + tree_node<T>& apex_; }; @@ -291,7 +291,7 @@ template <typename T> inline - tree<T>::tree(node<T>* root) + tree<T>::tree(tree_node<T>* root) : root_ (root) { mln_assertion (root != 0); @@ -299,7 +299,7 @@ template <typename T> inline - node<T>* + tree_node<T>* tree<T>::root() { return root_; @@ -318,7 +318,7 @@ void tree<T>::add_tree_up(T& elt) { - node<T>* n = new node<T> (elt); + tree_node<T>* n = new tree_node<T> (elt); root_->set_parent(n); n->children().push_back (root_); root_ = n; @@ -329,7 +329,7 @@ void tree<T>::add_tree_down(T& elt) { - node<T>* n = new node<T> (elt); + tree_node<T>* n = new tree_node<T> (elt); root_->child_.push_back (n); } @@ -344,14 +344,14 @@ template <typename T> inline - node<T>::node() + tree_node<T>::tree_node() : parent_ (0) { } template <typename T> inline - node<T>::node(T elt) + tree_node<T>::tree_node(T elt) : elt_ (elt), parent_ (0) { @@ -360,7 +360,7 @@ template <typename T> inline const T& - node<T>::elt() const + tree_node<T>::elt() const { return elt_; } @@ -368,7 +368,7 @@ template <typename T> inline T& - node<T>::elt() + tree_node<T>::elt() { return elt_; } @@ -376,26 +376,26 @@ template <typename T> inline - std::vector< node<T>* >& - node<T>::children() + std::vector< tree_node<T>* >& + tree_node<T>::children() { return child_; } template <typename T> inline - const std::vector< node<T>* >& - node<T>::children() const + const std::vector< tree_node<T>* >& + tree_node<T>::children() const { return child_; } template <typename T> inline - node<T>* - node<T>::add_child(T elt) + tree_node<T>* + tree_node<T>::add_child(T elt) { - node<T>* s = new node<T>(elt); + tree_node<T>* s = new tree_node<T>(elt); s->parent_ = this; this->child_.push_back(s); @@ -405,33 +405,33 @@ template <typename T> inline - node<T>* - node<T>::add_child(node<T>* node) + tree_node<T>* + tree_node<T>::add_child(tree_node<T>* tree_node) { - if (node->parent_) + if (tree_node->parent_) { - for (typename std::vector<util::node<T>* >::iterator it = node->parent()->children().begin(); - it != node->parent()->children().end(); ++it) - if ((*it) == node) + for (typename std::vector<util::tree_node<T>* >::iterator it = tree_node->parent()->children().begin(); + it != tree_node->parent()->children().end(); ++it) + if ((*it) == tree_node) { - node->parent()->children().erase(it); + tree_node->parent()->children().erase(it); break; } } - node->parent_ = this; - this->children().push_back(node); - return node; + tree_node->parent_ = this; + this->children().push_back(tree_node); + return tree_node; } template <typename T> inline - node<T>* - node<T>::delete_node() + tree_node<T>* + tree_node<T>::delete_tree_node() { mln_assertion(parent_ != 0); - node<T>* res = parent_; + tree_node<T>* res = parent_; - typename std::vector<node<T>* >::iterator it = parent_->children().begin(); + typename std::vector<tree_node<T>* >::iterator it = parent_->children().begin(); for (; it < parent_->children().end(); ++it) if ((*it) == this) { @@ -439,7 +439,7 @@ break; } - for (typename std::vector<node<T>* >::iterator it = this->child_.begin(); + for (typename std::vector<tree_node<T>* >::iterator it = this->child_.begin(); it != this->child_.end(); ++it) parent_->add_child(*it); return (res); @@ -448,14 +448,14 @@ template <typename T> inline void - node<T>::print(std::ostream& ostr, int level) + tree_node<T>::print(std::ostream& ostr, int level) { ostr << level << std::endl; ostr << " elt " << this->elt() << std::endl; - for (typename std::vector<node<T>* >::iterator it = this->child_.begin(); + for (typename std::vector<tree_node<T>* >::iterator it = this->child_.begin(); it != this->child_.end(); ++it) { (*it)->print(level + 1); @@ -466,7 +466,7 @@ template <typename T> inline void - node<T>::set_parent(node<T>* parent) + tree_node<T>::set_parent(tree_node<T>* parent) { mln_assertion(parent != 0); parent_ = parent; @@ -475,8 +475,8 @@ template <typename T> inline - node<T>* - node<T>::parent() + tree_node<T>* + tree_node<T>::parent() { return parent_; } @@ -484,7 +484,7 @@ template <typename T> inline int - node<T>::search_rec(node<T>** res, T& elt) + tree_node<T>::search_rec(tree_node<T>** res, T& elt) { if (elt == this->elt_) { @@ -493,7 +493,7 @@ } else { - for (typename std::vector<node<T>* >::iterator it = this->child_.begin(); + for (typename std::vector<tree_node<T>* >::iterator it = this->child_.begin(); it != this->child_.end(); ++it) { if ((**it).search_rec(res, elt)) @@ -505,10 +505,10 @@ template <typename T> inline - node<T>* - node<T>::search(T& elt) + tree_node<T>* + tree_node<T>::search(T& elt) { - node<T>* res = 0; + tree_node<T>* res = 0; if (search_rec(&res, elt)) return res; @@ -518,9 +518,9 @@ template <typename T> inline bool - node<T>::check_consistency() + tree_node<T>::check_consistency() { - for (typename std::vector<node<T>* >::iterator it = this->child_.begin(); + for (typename std::vector<tree_node<T>* >::iterator it = this->child_.begin(); it != this->child_.end(); ++it) { if ((**it).parent() != this) @@ -537,7 +537,7 @@ template <typename T> inline branch<T>::branch(util::tree<T>& tree, - util::node<T>& apex) + util::tree_node<T>& apex) : tree_(tree), apex_(apex) { @@ -546,7 +546,7 @@ template <typename T> inline - util::node<T>& + util::tree_node<T>& branch<T>::apex() { return apex_; Index: trunk/milena/mln/util/tree_to_image.hh =================================================================== --- trunk/milena/mln/util/tree_to_image.hh (revision 1748) +++ trunk/milena/mln/util/tree_to_image.hh (revision 1749) @@ -68,15 +68,15 @@ display_tree(const Image<J>& ima_, tree& tree); - /*! Display an arborescence from \p node. + /*! Display an arborescence from \p tree_node. * * \param[in] ima_ The domain of output image. - * \param[in] node The root node to display. + * \param[in] tree_node The root tree_node to display. * */ template <typename I, typename J> void - display_branch(const Image<J>& ima_, node* node); + display_branch(const Image<J>& ima_, tree_node* tree_node); # ifndef MLN_INCLUDE_ONLY @@ -86,21 +86,21 @@ template <typename T, typename I> inline void - tree_to_image_rec(node<T>* node, Image& output_) + tree_to_image_rec(tree_node<T>* tree_node, Image& output_) { trace::entering("util::impl::tree_to_image_rec"); I& output = exact(output_); - mln_piter(p_set<point2d>) p(node->elt().points); + mln_piter(p_set<point2d>) p(tree_node->elt().points); for_all(p) - output(p) = node->elt().value; + output(p) = tree_node->elt().value; - typename std::vector< util::node<T>* >::const_iterator it = node->children().begin(); + typename std::vector< util::tree_node<T>* >::const_iterator it = tree_node->children().begin(); for (int i = 0; - it != node->children().end(); + it != tree_node->children().end(); ++it, ++i) { if (*it) @@ -112,15 +112,15 @@ template <typename T, typename J> inline void - display_tree_rec(const Image<J>& ima_, node<T>* node, int level) + display_tree_rec(const Image<J>& ima_, tree_node<T>* tree_node, int level) { trace::entering("util::impl::display_tree_rec"); const J& ima = exact(ima_); - display_set(ima, node->elt().points); - typename mln::util::node<T>::children_t::iterator it = node->children().begin(); + display_set(ima, tree_node->elt().points); + typename mln::util::tree_node<T>::children_t::iterator it = tree_node->children().begin(); for (; - it != node->children().end(); ++it) + it != tree_node->children().end(); ++it) display_tree_rec(ima, (*it), level + 1); trace::exiting("util::impl::display_tree_rec"); @@ -130,19 +130,19 @@ template <typename T, typename J, typename K> inline void - display_branch_rec(const Image<J>& ima_, node<T>* node, Image<K>& output_) + display_branch_rec(const Image<J>& ima_, tree_node<T>* tree_node, Image<K>& output_) { trace::entering("util::impl::display_branch_rec"); K& output = exact(output_); const J& ima = exact(ima_); - mln_piter(p_set<point2d>) p(node->elt().points); + mln_piter(p_set<point2d>) p(tree_node->elt().points); for_all (p) output(p) = true; - typename mln::util::node<T>::children_t::iterator it = node->children().begin(); + typename mln::util::tree_node<T>::children_t::iterator it = tree_node->children().begin(); for (; - it != node->children().end(); ++it) + it != tree_node->children().end(); ++it) display_branch_rec(ima, (*it), output); trace::exiting("util::impl::display_branch_rec"); @@ -207,17 +207,17 @@ template <typename I, typename J> inline void - display_branch(const Image<J>& ima_, node* node) + display_branch(const Image<J>& ima_, tree_node* tree_node) { trace::entering("util::display_branch"); - mln_assertion(node); + mln_assertion(tree_node); const J& ima = exact(ima_); image2d<bool> output (ima.domain ()); level::fill(output, false); - impl::display_branch_rec(ima, node, output); + impl::display_branch_rec(ima, tree_node, output); trace::exiting("util::display_branch"); } Index: trunk/milena/mln/util/branch_iter_ind.hh =================================================================== --- trunk/milena/mln/util/branch_iter_ind.hh (revision 1748) +++ trunk/milena/mln/util/branch_iter_ind.hh (revision 1749) @@ -46,7 +46,7 @@ template<typename T> struct bi_elt { - typedef std::vector< util::node<T>* > child_list; + typedef std::vector< util::tree_node<T>* > child_list; bi_elt(child_list* list) : list_(list), @@ -54,7 +54,7 @@ pos_(-1) {} child_list* list_; - util::node<T>* previous_; + util::tree_node<T>* previous_; int pos_; }; @@ -71,8 +71,8 @@ branch_iter_ind(branch<T> branch); /// Convertion to node. - operator util::node<T>&() const; - util::node<T>& operator *(); + operator util::tree_node<T>&() const; + util::tree_node<T>& operator *(); /// Test the iterator validity. bool is_valid() const; @@ -96,7 +96,7 @@ /// Store child().begin() and child().end(). std::stack< bi_elt<T> > s_; - util::node<T>* n_; + util::tree_node<T>* n_; }; # ifndef MLN_INCLUDE_ONLY @@ -112,7 +112,7 @@ template <typename T> inline - branch_iter_ind<T>::operator node<T>&() const + branch_iter_ind<T>::operator tree_node<T>&() const { mln_assertion(n_); return *n_; @@ -120,7 +120,7 @@ template <typename T> inline - util::node<T>& + util::tree_node<T>& branch_iter_ind<T>::operator*() { mln_assertion(n_); @@ -134,7 +134,7 @@ { mln_assertion(is_valid()); unsigned i = 0; - node<T>* p = n_; + tree_node<T>* p = n_; while (p) { p = p->parent(); Index: trunk/milena/mln/util/branch_iter.hh =================================================================== --- trunk/milena/mln/util/branch_iter.hh (revision 1748) +++ trunk/milena/mln/util/branch_iter.hh (revision 1749) @@ -57,8 +57,8 @@ branch_iter(branch<T> branch); /// Convertion to node. - operator util::node<T>&() const; - util::node<T>& operator *(); + operator util::tree_node<T>&() const; + util::tree_node<T>& operator *(); /// Test the iterator validity. bool is_valid() const; @@ -78,12 +78,12 @@ /// The branch to iter. util::branch<T> branch_; - typedef typename std::vector< util::node<T>* >::iterator child_iter; + typedef typename std::vector< util::tree_node<T>* >::iterator child_iter; typedef std::pair<child_iter, child_iter> iter_pair; /// Store child().begin() and child().end(). std::stack< iter_pair > s_; - util::node<T>* n_; + util::tree_node<T>* n_; }; @@ -100,7 +100,7 @@ template <typename T> inline - branch_iter<T>::operator node<T>&() const + branch_iter<T>::operator tree_node<T>&() const { mln_assertion(n_); return *n_; @@ -108,7 +108,7 @@ template <typename T> inline - util::node<T>& + util::tree_node<T>& branch_iter<T>::operator*() { mln_assertion(n_); @@ -122,7 +122,7 @@ { mln_assertion(is_valid()); unsigned i = 0; - node<T>* p = n_; + tree_node<T>* p = n_; while (p) { p = p->parent();

1 0

milena r1748: Create FLLT directory in my sandbox
by Matthieu Garrigues 25 Feb '08

25 Feb '08

URL: https://svn.lrde.epita.fr/svn/oln/trunk/milena ChangeLog: 2008-02-25 Matthieu Garrigues <garrigues(a)lrde.epita.fr> Create FLLT directory in my sandbox and move fllt related files into it. * sandbox/garrigues/fllt: New. * sandbox/garrigues/fllt.hh: Remove. * sandbox/garrigues/fllt/fllt.hh: New. * sandbox/garrigues/fllt/fllt2.hh: New. * sandbox/garrigues/fllt/fllt_doc.hh: New. * sandbox/garrigues/fllt/fllt_merge.hh: New. * sandbox/garrigues/fllt/fllt_optimized.hh: New. * sandbox/garrigues/fllt/fllt_types.hh: New. * sandbox/garrigues/fllt/test_fllt.cc: New. * sandbox/garrigues/fllt/test_fllt10.cc: New. * sandbox/garrigues/fllt/test_fllt10_inv.cc: New. * sandbox/garrigues/fllt/test_fllt12.cc: New. * sandbox/garrigues/fllt/test_fllt13.cc: New. * sandbox/garrigues/fllt/test_fllt15.cc: New. * sandbox/garrigues/fllt/test_fllt2.cc: New. * sandbox/garrigues/fllt/test_fllt3.cc: New. * sandbox/garrigues/fllt/test_fllt3_inv.cc: New. * sandbox/garrigues/fllt/test_fllt4.cc: New. * sandbox/garrigues/fllt/test_fllt5.cc: New. * sandbox/garrigues/fllt/test_fllt6.cc: New. * sandbox/garrigues/fllt/test_fllt7.cc: New. * sandbox/garrigues/fllt/test_fllt7_inv.cc: New. * sandbox/garrigues/fllt/test_fllt8.cc: New. * sandbox/garrigues/fllt/test_fllt9.cc: New. * sandbox/garrigues/fllt/test_fllt_lena.cc: New. * sandbox/garrigues/fllt/test_fllt_lena_tiles.cc: New. * sandbox/garrigues/fllt/test_fllt_tiny.cc: New. * sandbox/garrigues/fllt/test_flltb.cc: New. * sandbox/garrigues/fllt2.hh: Remove. * sandbox/garrigues/fllt_doc.hh: Remove. * sandbox/garrigues/fllt_merge.hh: Remove. * sandbox/garrigues/fllt_optimized.hh: Remove. * sandbox/garrigues/fllt_types.hh: Remove. * sandbox/garrigues/test_fllt.cc: Remove. * sandbox/garrigues/test_fllt10.cc: Remove. * sandbox/garrigues/test_fllt10_inv.cc: Remove. * sandbox/garrigues/test_fllt12.cc: Remove. * sandbox/garrigues/test_fllt13.cc: Remove. * sandbox/garrigues/test_fllt15.cc: Remove. * sandbox/garrigues/test_fllt2.cc: Remove. * sandbox/garrigues/test_fllt3.cc: Remove. * sandbox/garrigues/test_fllt3_inv.cc: Remove. * sandbox/garrigues/test_fllt4.cc: Remove. * sandbox/garrigues/test_fllt5.cc: Remove. * sandbox/garrigues/test_fllt6.cc: Remove. * sandbox/garrigues/test_fllt7.cc: Remove. * sandbox/garrigues/test_fllt7_inv.cc: Remove. * sandbox/garrigues/test_fllt8.cc: Remove. * sandbox/garrigues/test_fllt9.cc: Remove. * sandbox/garrigues/test_fllt_lena.cc: Remove. * sandbox/garrigues/test_fllt_lena_tiles.cc: Remove. * sandbox/garrigues/test_fllt_tiny.cc: Remove. * sandbox/garrigues/test_flltb.cc: Remove. --- fllt.hh | 760 ++++++++++++++++++++++++++++++++++++++++ fllt2.hh | 893 ++++++++++++++++++++++++++++++++++++++++++++++++ fllt_doc.hh | 86 ++++ fllt_merge.hh | 200 ++++++++++ fllt_optimized.hh | 193 ++++++++++ fllt_types.hh | 71 +++ test_fllt.cc | 34 + test_fllt10.cc | 31 + test_fllt10_inv.cc | 31 + test_fllt12.cc | 29 + test_fllt13.cc | 30 + test_fllt15.cc | 43 ++ test_fllt2.cc | 33 + test_fllt3.cc | 31 + test_fllt3_inv.cc | 45 ++ test_fllt4.cc | 40 ++ test_fllt5.cc | 40 ++ test_fllt6.cc | 28 + test_fllt7.cc | 44 ++ test_fllt7_inv.cc | 31 + test_fllt8.cc | 33 + test_fllt9.cc | 41 ++ test_fllt_lena.cc | 24 + test_fllt_lena_tiles.cc | 32 + test_fllt_tiny.cc | 19 + test_flltb.cc | 40 ++ 26 files changed, 2882 insertions(+) Index: trunk/milena/sandbox/garrigues/test_fllt_lena_tiles.cc (deleted) =================================================================== Index: trunk/milena/sandbox/garrigues/test_fllt10.cc (deleted) =================================================================== Index: trunk/milena/sandbox/garrigues/test_fllt12.cc (deleted) =================================================================== Index: trunk/milena/sandbox/garrigues/test_fllt_tiny.cc (deleted) =================================================================== Index: trunk/milena/sandbox/garrigues/test_fllt10_inv.cc (deleted) =================================================================== Index: trunk/milena/sandbox/garrigues/test_fllt3.cc (deleted) =================================================================== Index: trunk/milena/sandbox/garrigues/test_fllt5.cc (deleted) =================================================================== Index: trunk/milena/sandbox/garrigues/test_fllt7.cc (deleted) =================================================================== Index: trunk/milena/sandbox/garrigues/test_fllt9.cc (deleted) =================================================================== Index: trunk/milena/sandbox/garrigues/fllt_merge.hh (deleted) =================================================================== Index: trunk/milena/sandbox/garrigues/fllt2.hh (deleted) =================================================================== Index: trunk/milena/sandbox/garrigues/test_fllt_lena.cc (deleted) =================================================================== Index: trunk/milena/sandbox/garrigues/fllt_optimized.hh (deleted) =================================================================== Index: trunk/milena/sandbox/garrigues/test_fllt3_inv.cc (deleted) =================================================================== Index: trunk/milena/sandbox/garrigues/fllt_types.hh (deleted) =================================================================== Index: trunk/milena/sandbox/garrigues/fllt_doc.hh (deleted) =================================================================== Index: trunk/milena/sandbox/garrigues/test_fllt.cc (deleted) =================================================================== Index: trunk/milena/sandbox/garrigues/test_flltb.cc (deleted) =================================================================== Index: trunk/milena/sandbox/garrigues/test_fllt7_inv.cc (deleted) =================================================================== Index: trunk/milena/sandbox/garrigues/test_fllt13.cc (deleted) =================================================================== Index: trunk/milena/sandbox/garrigues/test_fllt15.cc (deleted) =================================================================== Index: trunk/milena/sandbox/garrigues/fllt.hh (deleted) =================================================================== Index: trunk/milena/sandbox/garrigues/test_fllt2.cc (deleted) =================================================================== Index: trunk/milena/sandbox/garrigues/test_fllt4.cc (deleted) =================================================================== Index: trunk/milena/sandbox/garrigues/test_fllt6.cc (deleted) =================================================================== Index: trunk/milena/sandbox/garrigues/test_fllt8.cc (deleted) =================================================================== Index: trunk/milena/sandbox/garrigues/fllt/fllt2.hh =================================================================== --- trunk/milena/sandbox/garrigues/fllt/fllt2.hh (revision 0) +++ trunk/milena/sandbox/garrigues/fllt/fllt2.hh (revision 1748) @@ -0,0 +1,893 @@ +// 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_HH +# define MLN_FIXME_FLLT_HH + +/*! \file fllt.hh + * + * \brief Fast level line transform of an image. + * + */ + +# include <mln/core/image2d.hh> +# include <mln/core/p_set.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 <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 fllt_node_elt + { + V value; + p_set points; + p_set 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_ind(P, V) util::branch_iter_ind< 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 V> + void step1 (const image2d<V>& ima, + point2d p, + V& g, + point2d& x0) + { + //std::cout << "entering step 1" << std::endl; + // x0 <- a not tagged local mininum of ima. + //std::cout << std::endl << "x0 = " < + void step2 (p_set& A, + p_set& R, + p_set& N, + point2d& x0) + { + //std::cout << "entering step 2" << std::endl; + // A <- {x0} + A.clear(); + A.insert(x0); + // R <- {} + R.clear(); + // N <- {} + N.clear(); + //std::cout << "exiting step 2" << std::endl; + } + + + template <typename V, typename P, typename F> + void step3 (const image2d<V>& u, + image2d<bool>& tagged, + p_set& A, + p_set& R, + p_set& N, + V& gn) + { + static bool finished = false; + //std::cout << "entering step 3" << std::endl; + + // Stop the algorithm. + if (finished) + { finished = false; gn -= 2 * F::inc; return; } + + // N <- N union {x neighbor of a pixel in a\R} + mln_piter(p_set) qa(A); + for_all(qa) + { + mln_niter(neighb2d) n(F::reg_nbh(), qa); + for_all (n) + if (!R.has (n)) + 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 ((u | set::inter(N, u.domain())).npoints() > 0) + gn = level::compute< typename F::accu_for_gn >(u | set::inter(N, u.domain())); + else + { + finished = true; + gn += F::inc; + } + //std::cout << std::endl << "gN = " << gn << std::endl; + // R <- R union A + // tag the pixels of A. + + for_all(qa) + { + R.insert(qa); + tagged(qa) = true; + } + //std::cout << "exiting step 3" << std::endl; + } + + + /// IF g < gn. + template <typename V, typename P, typename F> + void step4_1 (image2d<V>& u, + p_set& A, + p_set& R, + p_set& N, + V& g, + V& gn, + fllt_node(P, V)*& current_region, + image2d<fllt_node(P, V)*>& regions + ) + { + //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 ((R.bbox() < u.domain()) || (R.npoints() == u.domain().npoints())) + { + mln_piter(p_set) p(R); + current_region = new fllt_node(P, V)(); + current_region->elt().brighter = F::parent_is_brighter; + current_region->elt().value = g; + for_all(p) + { + current_region->elt().points.insert(p); + + if (regions(p) == 0) + { + //current_region->elt().points.insert(p); + regions(p) = current_region; + } + else + { + if (regions(p)->parent() == 0) + regions(p)->set_parent(current_region); + } + } + + + // Count the number of conected components of the border of R. + static image2d<int> tmp(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(p_set) z(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); + + // 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. + 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 + } + } + + } + g = gn; + // A <- {x belongs to N / u(x) == g} + A.clear(); + A = set::uni(A, set::inter(N, u.domain()) | pw::value(u) == pw::cst(g)); + // N <- N\{x belongs to N / u(x) == g} + N = set::diff(N, set::inter(N, u.domain()) | pw::value(u) == pw::cst(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 (const image2d<V>& u, + p_set& A, + p_set& N, + V& g, + fllt_node(P, V)* current_region, + image2d<fllt_node(P, V)*>& regions + ) + { + //std::cout << "entering step 4_2" << std::endl; + + // A <- {x belongs to N / u(x) == g} + A = set::uni(A, set::inter(N, u.domain()) | pw::value(u) == pw::cst(g)); + // N <- N\{x belongs to N / u(x) == g} + N = set::diff(N, set::inter(N, u.domain()) | pw::value(u) == pw::cst(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 (image2d<V>& u, + const image2d<bool>& tagged, + const p_set& 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(p_set) p(R); + for_all(p) + { + mln_assertion (tagged(p)); + u (p) = g; + } + + //std::cout << "exiting step 4_3" << std::endl; + + } + + + template <typename V, typename F> + fllt_tree(point2d, V)& + compute_level_set(const image2d<V>& ima, + 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(ima.domain() == regions.domain()); + + // Declarations. + p_set R, N, A; + V g, gn; + point2d x0; + image2d<V> min_locals(ima.domain()); + image2d<V> u = clone(ima); + border::fill(u, 0); + + //std::cout << "image U:" << std::endl; + // debug::println_with_border(u); + image2d<bool> tagged(ima.domain()); + fllt_node(P, V)* current_region; + + // INIT + R.clear(); + N.clear(); + A.clear(); + g= 0; + gn = 0; + current_region = 0; + + level::fill(regions, 0); + level::fill(tagged, false); + + // Get the locals extremums + unsigned nlabels; + F::regional_extremum(ima, 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 (tagged(p)) + continue; + + step1(ima, p, g, x0); + step2(A, R, N, x0); + while (1) + { + //std::cout << "g = " << g << std::endl; + step3<V, P, F>(u, tagged, A, R, N, gn); + /// step4. + if (F::compare(g, gn)) + { + step4_1<V, P, F>(u, A, R, N, g, gn, current_region, regions); + // GO TO 3) + continue; + } + + + if (g == gn) + { + step4_2(u, A, N, g, current_region, regions); + // GO TO 3) + continue; + } + + + if (!F::compare(g, gn)) + { + step4_3(u, tagged, R, g); + // GO TO 1) + break; + } + } + //std::cout << "current_region = " << current_region << std::endl; + } + } // end of Algorithm + + image2d<value::int_u8> output (ima.domain ()); + fllt_tree(P, V)& tree = *new fllt_tree(P, V)(current_region); + util::tree_to_image (tree, output); + + // util::display_tree(ima, tree); + + // debug::println(output); + // std::cout << std::endl; + // debug::println(ima); + + // if (output != ima) + // { + // std::cerr << "BUG!!!" << std::endl; + // abort(); + // } + + // io::pgm::save(output, "out.pgm"); + // std::cout << "out.pgm generate" + // << std::endl; + + + // debug::println(regions); + //debug::println(ima | 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& 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& 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 " < + 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(p_set) 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(p_set) 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_ind(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_ind(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) + { + fllt_branch_iter_ind(P, V) p(tree.main_branch()); + level::fill(output, 0); + for_all(p) + { + //std::cout << (&*p) << ":" << p.deepness() << std::endl; + mln_piter(p_set<point2d>) q((*p).elt().points); + for_all(q) + { + if (output(q) < p.deepness()) + output(q) = p.deepness(); + } + } + } + + + template <typename P, typename V> + void + visualize_bounds(image2d<value::int_u8>& output, + fllt_tree(P, V)& tree, + unsigned limit) + { + fllt_branch_iter_ind(P, V) p(tree.main_branch()); + level::fill(output, 255); + for_all(p) + { + if ((*p).elt().points.npoints() > limit) + { + mln_piter(p_set<point2d>) q((*p).elt().points); + for_all(q) + { + mln_niter(neighb2d) n(c4(), q); + bool is_border = false; + for_all (n) + if (!((*p).elt().points).has (n)) + is_border = true; + if (is_border) + output(q) = 0; + } + } + } + } + + template <typename P, typename V> + void + draw_tree(const image2d<V>& ima, + fllt_tree(P, V)& tree) + { + fllt_branch_iter_ind(P, V) p(tree.main_branch()); + for_all(p) + { + std::cout << "region mere : " << (*p).parent() << std::endl; + std::cout << " ^" << std::endl; + std::cout << " |" << std::endl; + std::cout << "region : " << &*p + << " value = " << (*p).elt().value << std::endl + << " holes : " + << (*p).elt().holes.npoints() + << (*p).elt().holes + << std::endl; + + debug::println(ima | (*p).elt().points); + std::cout << std::endl; + } + } + + template <typename V> + // Fixme : return type + void + fllt(const image2d<V>& ima) + { + typedef point2d P; + + fllt_tree(P, V) upper_tree; + fllt_tree(P, V) lower_tree; + image2d<fllt_node(P, V)*> low_reg(ima.domain()); + image2d<fllt_node(P, V)*> upp_reg(ima.domain()); + + 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"); + + } + + } // end of namespace mln::fllt + +} // end of namespace mln + + + +#endif // ! MLN_FIXME_FLLT_HH Index: trunk/milena/sandbox/garrigues/fllt/test_fllt_lena.cc =================================================================== --- trunk/milena/sandbox/garrigues/fllt/test_fllt_lena.cc (revision 0) +++ trunk/milena/sandbox/garrigues/fllt/test_fllt_lena.cc (revision 1748) @@ -0,0 +1,24 @@ +# include "fllt.hh" +# include <mln/core/image2d.hh> +# include <mln/core/clone.hh> +# include <mln/value/int_u8.hh> +# include <mln/debug/println.hh> +# include <mln/convert/to_w_window.hh> +# include <mln/core/w_window2d_int.hh> +# include <mln/convert/to_image.hh> +# include <mln/level/fill.hh> +# include <mln/io/pgm/load.hh> +# include <mln/io/pbm/load.hh> + +int main() +{ + + using namespace mln; + + image2d<value::int_u8> ima = io::pgm::load("../../img/lena.pgm"); + + image2d<int> ima_int(ima.domain()); + + level::fill(ima_int, ima); + fllt::fllt(ima_int); +} Index: trunk/milena/sandbox/garrigues/fllt/fllt_types.hh =================================================================== --- trunk/milena/sandbox/garrigues/fllt/fllt_types.hh (revision 0) +++ trunk/milena/sandbox/garrigues/fllt/fllt_types.hh (revision 1748) @@ -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 points; + p_set 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/test_fllt3_inv.cc =================================================================== --- trunk/milena/sandbox/garrigues/fllt/test_fllt3_inv.cc (revision 0) +++ trunk/milena/sandbox/garrigues/fllt/test_fllt3_inv.cc (revision 1748) @@ -0,0 +1,45 @@ +# include "fllt2.hh" +# include <mln/core/image2d.hh> +# include <mln/core/clone.hh> +# include <mln/value/int_u8.hh> +# include <mln/debug/println.hh> +# include <mln/convert/to_w_window.hh> +# include <mln/core/w_window2d_int.hh> +# include <mln/convert/to_image.hh> +# include <mln/level/fill.hh> +# include <mln/io/pgm/load.hh> +# include <mln/io/pbm/load.hh> + +int main() +{ + + 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}; + +// w_window2d_int w_win = make::w_window2d(ws); +// image2d<int> ima = convert::to_image(w_win); +// fllt::fllt(ima); + + int vs[9][9] = { {0,0,0,0,0,0,0,0,0}, + {0,0,0,0,0,0,0,0,0}, + {0,1,1,1,1,1,1,1,0}, + {0,1,0,0,1,2,2,1,0}, + {0,1,0,0,1,2,2,1,0}, + {0,1,0,0,1,2,2,1,0}, + {0,1,1,1,1,1,1,1,0}, + {0,1,1,1,1,1,1,1,0}, + {0,0,0,0,0,0,0,0,0} }; + + image2d<int> ima(make::image2d(vs)); + fllt::fllt(ima); + +} Index: trunk/milena/sandbox/garrigues/fllt/fllt_optimized.hh =================================================================== --- trunk/milena/sandbox/garrigues/fllt/fllt_optimized.hh (revision 0) +++ trunk/milena/sandbox/garrigues/fllt/fllt_optimized.hh (revision 1748) @@ -0,0 +1,193 @@ +// 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_HH +# define MLN_FIXME_FLLT_HH + +/*! \file fllt.hh + * + * \brief Fast level line transform of an image. + * + */ + + +# 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> +# 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> + void + visualize_deepness(image2d<value::int_u8>& output, + fllt_tree(P, V)& tree) + { + fllt_branch_iter(P, V) p(tree.main_branch()); + level::fill(output, 0); + for_all(p) + { + //std::cout << (&*p) << ":" << p.deepness() << std::endl; + mln_piter(p_set<point2d>) q((*p).elt().points); + for_all(q) + { + if (output(q) < p.deepness()) + output(q) = p.deepness(); + } + } + } + + + template <typename P, typename V> + void + visualize_bounds(image2d<value::int_u8>& output, + fllt_tree(P, V)& tree, + unsigned limit) + { + fllt_branch_iter(P, V) p(tree.main_branch()); + level::fill(output, 255); + for_all(p) + { + if ((*p).elt().points.npoints() > limit) + { + mln_piter(p_set<point2d>) q((*p).elt().points); + for_all(q) + { + mln_niter(neighb2d) n(c4(), q); + bool is_border = false; + for_all (n) + if (!((*p).elt().points).has (n)) + is_border = true; + if (is_border) + output(q) = 0; + } + } + } + } + + template <typename P, typename V> + void + draw_tree(const image2d<V>& ima, + fllt_tree(P, V)& tree) + { + fllt_branch_iter(P, V) p(tree.main_branch()); + for_all(p) + { + std::cout << "region mere : " << (*p).parent() << std::endl; + std::cout << " ^" << std::endl; + std::cout << " |" << std::endl; + std::cout << "region : " << &*p + << " value = " << (*p).elt().value << std::endl + << " holes : " + << (*p).elt().holes.npoints() + << (*p).elt().holes + << std::endl; + + debug::println(ima | (*p).elt().points); + std::cout << std::endl; + } + } + + 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; + + fllt_tree(P, V) upper_tree; + fllt_tree(P, V) lower_tree; + image2d<fllt_node(P, V)*> low_reg(ima.domain()); + image2d<fllt_node(P, V)*> upp_reg(ima.domain()); + + std::cout << "1/ Compute the lower level set." << std::endl; + lower_tree = compute_level_set<V, lower<V> >(ima, low_reg); + std::cout << "2/ Compute the upper level set." << std::endl; + upper_tree = compute_level_set<V, upper<V> >(ima, upp_reg); + + std::cout << "3/ Merge the two trees." << std::endl; + fllt_tree(P, V) result_tree = merge_trees(lower_tree, upper_tree, low_reg, upp_reg, ima); + + return result_tree; + } + + } // end of namespace mln::fllt + +} // end of namespace mln + + + +#endif // ! MLN_FIXME_FLLT_HH Index: trunk/milena/sandbox/garrigues/fllt/test_fllt_lena_tiles.cc =================================================================== --- trunk/milena/sandbox/garrigues/fllt/test_fllt_lena_tiles.cc (revision 0) +++ trunk/milena/sandbox/garrigues/fllt/test_fllt_lena_tiles.cc (revision 1748) @@ -0,0 +1,32 @@ +# include "fllt_optimized.hh" +# include <mln/core/image2d.hh> +# include <mln/core/clone.hh> +# include <mln/value/int_u8.hh> +# include <mln/debug/println.hh> +# include <mln/convert/to_w_window.hh> +# include <mln/core/w_window2d_int.hh> +# include <mln/convert/to_image.hh> +# include <mln/level/fill.hh> +# include <mln/io/pgm/load.hh> +# include <mln/io/pbm/load.hh> +# include <sstream> + + +int main() +{ + + using namespace mln; + + for (int i = 0; i < 16; ++i) + for (int j = 0; j < 16; ++j) + { + std::stringstream path; + path << "/lrde/tegucigalpa/theo/pub/mln_docs/lena_tiles/lena_" < ima = io::pgm::load(path.str()); + image2d<int> ima_int(ima.domain()); + level::fill(ima_int, ima); + fllt::fllt(ima_int); + } +} + Index: trunk/milena/sandbox/garrigues/fllt/test_fllt.cc =================================================================== --- trunk/milena/sandbox/garrigues/fllt/test_fllt.cc (revision 0) +++ trunk/milena/sandbox/garrigues/fllt/test_fllt.cc (revision 1748) @@ -0,0 +1,34 @@ +# include "fllt2.hh" +# include <mln/core/image2d.hh> +# include <mln/core/clone.hh> +# include <mln/value/int_u8.hh> +# include <mln/debug/println.hh> +# include <mln/convert/to_w_window.hh> +# include <mln/core/w_window2d_int.hh> +# include <mln/convert/to_image.hh> +# include <mln/level/fill.hh> +# include <mln/io/pgm/load.hh> +# include <mln/io/pbm/load.hh> +# include <sstream> + + +int main() +{ + + using namespace mln; + + int ws[81] = {3,2,3,3,5,5,5,5,5, + 2,1,3,4,4,4,4,5,5, + 2,3,4,2,3,3,2,4,4, + 1,4,2,1,1,2,1,2,2, + 1,2,4,2,1,2,1,1,1, + 1,3,3,3,4,3,2,5,1, + 1,3,4,3,4,3,2,5,1, + 1,3,3,3,4,3,2,5,1, + 1,3,3,4,2,3,2,1,1}; + + w_window2d_int w_win = make::w_window2d(ws); + image2d<int> ima = convert::to_image(w_win); + fllt::fllt(ima); + +} Index: trunk/milena/sandbox/garrigues/fllt/fllt_doc.hh =================================================================== --- trunk/milena/sandbox/garrigues/fllt/fllt_doc.hh (revision 0) +++ trunk/milena/sandbox/garrigues/fllt/fllt_doc.hh (revision 1748) @@ -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/fllt/test_fllt10.cc =================================================================== --- trunk/milena/sandbox/garrigues/fllt/test_fllt10.cc (revision 0) +++ trunk/milena/sandbox/garrigues/fllt/test_fllt10.cc (revision 1748) @@ -0,0 +1,31 @@ +# include "fllt2.hh" +# include <mln/core/image2d.hh> +# include <mln/core/clone.hh> +# include <mln/value/int_u8.hh> +# include <mln/debug/println.hh> +# include <mln/convert/to_w_window.hh> +# include <mln/core/w_window2d_int.hh> +# include <mln/convert/to_image.hh> +# include <mln/level/fill.hh> +# include <mln/io/pgm/load.hh> +# include <mln/io/pgm/save.hh> +# include <mln/io/pbm/load.hh> +# include <sstream> + + +int main() +{ + + using namespace mln; + using typename value::int_u8; + + int vs[5][10] = { {3, 3, 3, 3, 3, 4, 4, 4, 4, 4}, + {3, 4, 4, 4, 3, 4, 3, 3, 3, 4}, + {3, 4, 0, 4, 3, 4, 3, 5, 3, 4}, + {3, 4, 4, 4, 3, 4, 3, 3, 3, 4}, + {3, 3, 3, 3, 3, 4, 4, 4, 4, 4} }; + + image2d<int> ima(make::image2d(vs)); + fllt::fllt(ima); + +} Index: trunk/milena/sandbox/garrigues/fllt/test_flltb.cc =================================================================== --- trunk/milena/sandbox/garrigues/fllt/test_flltb.cc (revision 0) +++ trunk/milena/sandbox/garrigues/fllt/test_flltb.cc (revision 1748) @@ -0,0 +1,40 @@ +# include "fllt2.hh" +# include <mln/core/image2d.hh> +# include <mln/core/clone.hh> +# include <mln/value/int_u8.hh> +# include <mln/debug/println.hh> +# include <mln/convert/to_w_window.hh> +# include <mln/core/w_window2d_int.hh> +# include <mln/convert/to_image.hh> +# include <mln/level/fill.hh> +# include <mln/io/pgm/load.hh> +# include <mln/io/pgm/save.hh> +# include <mln/io/pbm/load.hh> +# include <sstream> + + +int main() +{ + + 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][4] = { {3, 3, 3, 4}, + {3, 2, 3, 2}, + {4, 3, 3, 2}, + {2, 2, 2, 2} }; + + + + image2d<int> ima(make::image2d(vs)); + image2d<int_u8> out(ima.domain()); + + level::fill(out, ima); + io::pgm::save(out, "ima.pgm "); + fllt::fllt(ima); + +} Index: trunk/milena/sandbox/garrigues/fllt/test_fllt_tiny.cc =================================================================== --- trunk/milena/sandbox/garrigues/fllt/test_fllt_tiny.cc (revision 0) +++ trunk/milena/sandbox/garrigues/fllt/test_fllt_tiny.cc (revision 1748) @@ -0,0 +1,19 @@ +# include "fllt2.hh" +# include <mln/core/image2d.hh> +# include <mln/core/clone.hh> +# include <mln/value/int_u8.hh> +# include <mln/level/fill.hh> +# include <mln/io/pgm/load.hh> + +int main() +{ + + using namespace mln; + + image2d<value::int_u8> ima = io::pgm::load("../../img/tiny.pgm"); + + image2d<int> ima_int(ima.domain()); + + level::fill(ima_int, ima); + fllt::fllt(ima_int); +} Index: trunk/milena/sandbox/garrigues/fllt/test_fllt7_inv.cc =================================================================== --- trunk/milena/sandbox/garrigues/fllt/test_fllt7_inv.cc (revision 0) +++ trunk/milena/sandbox/garrigues/fllt/test_fllt7_inv.cc (revision 1748) @@ -0,0 +1,31 @@ +# include "fllt2.hh" +# include <mln/core/image2d.hh> +# include <mln/core/clone.hh> +# include <mln/value/int_u8.hh> +# include <mln/debug/println.hh> +# include <mln/convert/to_w_window.hh> +# include <mln/core/w_window2d_int.hh> +# include <mln/convert/to_image.hh> +# include <mln/level/fill.hh> +# include <mln/io/pgm/load.hh> +# include <mln/io/pgm/save.hh> +# include <mln/io/pbm/load.hh> +# include <sstream> + + +int main() +{ + + using namespace mln; + using typename value::int_u8; + + int vs[5][5] = { {200, 100, 100, 100, 200}, + {200, 100, 0 , 100, 200}, + {200, 100, 100, 100, 200}, + {200, 100, 0 , 100, 200}, + {200, 100, 100, 100, 200} }; + + image2d<int> ima(make::image2d(vs)); + fllt::fllt(ima); + +} Index: trunk/milena/sandbox/garrigues/fllt/test_fllt12.cc =================================================================== --- trunk/milena/sandbox/garrigues/fllt/test_fllt12.cc (revision 0) +++ trunk/milena/sandbox/garrigues/fllt/test_fllt12.cc (revision 1748) @@ -0,0 +1,29 @@ +# include "fllt2.hh" +# include <mln/core/image2d.hh> +# include <mln/core/clone.hh> +# include <mln/value/int_u8.hh> +# include <mln/debug/println.hh> +# include <mln/convert/to_w_window.hh> +# include <mln/core/w_window2d_int.hh> +# include <mln/convert/to_image.hh> +# include <mln/level/fill.hh> +# include <mln/io/pgm/load.hh> +# include <mln/io/pgm/save.hh> +# include <mln/io/pbm/load.hh> +# include <sstream> + + +int main() +{ + + using namespace mln; + using typename value::int_u8; + + 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)); + fllt::fllt(ima); +} Index: trunk/milena/sandbox/garrigues/fllt/test_fllt13.cc =================================================================== --- trunk/milena/sandbox/garrigues/fllt/test_fllt13.cc (revision 0) +++ trunk/milena/sandbox/garrigues/fllt/test_fllt13.cc (revision 1748) @@ -0,0 +1,30 @@ +# include "fllt2.hh" +# include <mln/core/image2d.hh> +# include <mln/core/clone.hh> +# include <mln/value/int_u8.hh> +# include <mln/debug/println.hh> +# include <mln/convert/to_w_window.hh> +# include <mln/core/w_window2d_int.hh> +# include <mln/convert/to_image.hh> +# include <mln/level/fill.hh> +# include <mln/io/pgm/load.hh> +# include <mln/io/pgm/save.hh> +# include <mln/io/pbm/load.hh> +# include <sstream> + + +int main() +{ + + using namespace mln; + using typename value::int_u8; + + 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)); + fllt::fllt(ima); +} Index: trunk/milena/sandbox/garrigues/fllt/test_fllt15.cc =================================================================== --- trunk/milena/sandbox/garrigues/fllt/test_fllt15.cc (revision 0) +++ trunk/milena/sandbox/garrigues/fllt/test_fllt15.cc (revision 1748) @@ -0,0 +1,43 @@ +# include "fllt2.hh" +# include <mln/core/image2d.hh> +# include <mln/core/clone.hh> +# include <mln/value/int_u8.hh> +# include <mln/debug/println.hh> +# include <mln/convert/to_w_window.hh> +# include <mln/core/w_window2d_int.hh> +# include <mln/convert/to_image.hh> +# include <mln/level/fill.hh> +# include <mln/io/pgm/load.hh> +# include <mln/io/pgm/save.hh> +# include <mln/io/pbm/load.hh> +# include <sstream> + + +int main() +{ + + 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[6][5] = { + +{ 3, 3, 4, 4, 4 }, +{ 2, 1, 1, 1, 1 }, +{ 1, 4, 4, 4, 1 }, +{ 1, 4, 3, 4, 1 }, +{ 1, 4, 5, 3, 1 }, +{ 1, 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/fllt/fllt.hh =================================================================== --- trunk/milena/sandbox/garrigues/fllt/fllt.hh (revision 0) +++ trunk/milena/sandbox/garrigues/fllt/fllt.hh (revision 1748) @@ -0,0 +1,760 @@ +// 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_HH +# define MLN_FIXME_FLLT_HH + +/*! \file fllt.hh + * + * \brief Fast level line transform of an image. + * + */ + +# 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.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 fllt_node_elt + { + V value; + set_p points; + set_p holes; + }; + +# 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 V> + void step1 (const image2d<V>& ima, + point2d p, + V& g, + point2d& x0) + { + //std::cout << "entering step 1" << std::endl; + // x0 <- a not tagged local mininum of ima. + //std::cout << std::endl << "x0 = " < + void step2 (set_p& A, + set_p& R, + set_p& N, + point2d& x0) + { + //std::cout << "entering step 2" << std::endl; + // A <- {x0} + A.clear(); + A.insert(x0); + // R <- {} + R.clear(); + // N <- {} + N.clear(); + //std::cout << "exiting step 2" << std::endl; + } + + + template <typename V, typename P, typename F> + void step3 (const image2d<V>& u, + image2d<bool>& tagged, + set_p& A, + set_p& R, + set_p& N, + V& gn) + { + static bool finished = false; + //std::cout << "entering step 3" << std::endl; + + // Stop the algorithm. + if (finished) + { finished = false; gn -= 2 * F::inc; return; } + + // N <- N union {x neighbor of a pixel in a\R} + mln_piter(set_p) qa(A); + for_all(qa) + { + mln_niter(neighb2d) n(F::reg_nbh(), qa); + for_all (n) + if (!R.has (n)) + 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 ((u | set::inter(N, u.domain())).npoints() > 0) + gn = level::compute< typename F::accu_for_gn >(u | set::inter(N, u.domain())); + else + { + finished = true; + gn += F::inc; + } + //std::cout << std::endl << "gN = " << gn << std::endl; + // R <- R union A + // tag the pixels of A. + + for_all(qa) + { + R.insert(qa); + tagged(qa) = true; + } + //std::cout << "exiting step 3" << std::endl; + } + + + /// IF g < gn. + template <typename V, typename P, typename F> + void step4_1 (image2d<V>& u, + set_p& A, + set_p& R, + set_p& N, + V& g, + V& gn, + fllt_node(P, V)*& current_region, + image2d<fllt_node(P, V)*>& regions + ) + { + //std::cout << "entering step 4_1" << std::endl; + + // Create a new conected component. + // FIXME : we can make it faster. + mln_piter(set_p) p(R); + current_region = new fllt_node(P, V)(); + current_region->elt().value = g; + for_all(p) + { + current_region->elt().points.insert(p); + if (regions(p) == 0) + regions(p) = current_region; + else + { + if (regions(p)->parent() == 0) + regions(p)->set_parent(current_region); + } + } + + + // Count the number of conected components of the border of R. + static image2d<int> tmp(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) z(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); + + // 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. + current_region->elt().holes.insert(a_point_of(tmp | pw::value(tmp) == pw::cst(n))); + + // FIXME : [optimisation] 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} + A.clear(); + A = set::uni(A, set::inter(N, u.domain()) | pw::value(u) == pw::cst(g)); + // N <- N\{x belongs to N / u(x) == g} + N = set::diff(N, set::inter(N, u.domain()) | pw::value(u) == pw::cst(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 (const image2d<V>& u, + set_p& A, + set_p& N, + V& g, + fllt_node(P, V)* current_region, + image2d<fllt_node(P, V)*>& regions + ) + { + //std::cout << "entering step 4_2" << std::endl; + + // A <- {x belongs to N / u(x) == g} + A = set::uni(A, set::inter(N, u.domain()) | pw::value(u) == pw::cst(g)); + // N <- N\{x belongs to N / u(x) == g} + N = set::diff(N, set::inter(N, u.domain()) | pw::value(u) == pw::cst(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 (image2d<V>& u, + const image2d<bool>& tagged, + const 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(R); + for_all(p) + { + mln_assertion (tagged(p)); + u (p) = g; + } + + //std::cout << "exiting step 4_3" << std::endl; + + } + + + template <typename V, typename F> + fllt_tree(point2d, V)& + compute_level_set(const image2d<V>& ima, + 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(ima.domain() == regions.domain()); + + // Declarations. + set_p R, N, A; + V g, gn; + point2d x0; + image2d<V> min_locals(ima.domain()); + image2d<V> u = clone(ima); + border::fill(u, 0); + + //std::cout << "image U:" << std::endl; + // debug::println_with_border(u); + image2d<bool> tagged(ima.domain()); + fllt_node(P, V)* current_region; + + // INIT + R.clear(); + N.clear(); + A.clear(); + g= 0; + gn = 0; + current_region = 0; + + level::fill(regions, 0); + level::fill(tagged, false); + + // Get the locals extremums + unsigned nlabels; + F::regional_extremum(ima, 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 (tagged(p)) + continue; + + step1(ima, p, g, x0); + step2(A, R, N, x0); + while (1) + { + //std::cout << "g = " << g << std::endl; + step3<V, P, F>(u, tagged, A, R, N, gn); + /// step4. + if (F::compare(g, gn)) + { + step4_1<V, P, F>(u, A, R, N, g, gn, current_region, regions); + // GO TO 3) + continue; + } + + + if (g == gn) + { + step4_2(u, A, N, g, current_region, regions); + // GO TO 3) + continue; + } + + + if (!F::compare(g, gn)) + { + step4_3(u, tagged, R, g); + // GO TO 1) + break; + } + } + //std::cout << "current_region = " << current_region << std::endl; + } + } // end of Algorithm + std::cout << "END OF ALGORITHM" << std::endl; + + image2d<value::int_u8> output (ima.domain ()); + fllt_tree(P, V)& tree = *new fllt_tree(P, V)(current_region); + util::tree_to_image (tree, output); + + util::display_tree(ima, tree); + +// debug::println(output); +// std::cout << std::endl; +// debug::println(ima); + + if (output != ima) + { + std::cerr << "BUG!!!" << std::endl; + abort(); + } + + io::pgm::save(output, "out.pgm"); + std::cout << "out.pgm generate" + << std::endl; + + + // debug::println(regions); + //debug::println(ima | 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 + + // LOWER LEVEL SET : region = c4, border = c8 + template <typename V> + struct lower + { + 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& input, const Neighborhood<N>& nbh, + Image<O>& output, unsigned& nlabels) + { + return labeling::regional_minima(input, nbh, + output, nlabels); + } + + static const int inc = 1; + + 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 + { + 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& input, const Neighborhood<N>& nbh, + Image<O>& output, unsigned& nlabels) + { + return labeling::regional_maxima(input, nbh, + output, nlabels); + } + + static const int inc = -1; + typedef accu::max accu_for_gn; + + static const neighb2d& bdr_nbh() { return c4(); } + static const neighb2d& reg_nbh() { return c8(); } + }; + + template <typename P, typename V> + void + move_shape(fllt_node(P, V)& node, + fllt_node(P, V)& hole, + fllt_tree(P, V)& tree, + const image2d<fllt_node(P, V)*>& other_reg) + { + fill_a_shape(hole, tree, other_reg); + node.elt().points = set::uni(hole.elt().points, node.elt().points); + node.add_child(&hole); + } + + template <typename P, typename V> + 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() && (s->parent()->elt().value < node.elt().value)) + { + mln_assertion(s); + s = s->parent(); + mln_assertion(s); + } + return s; + } + + template <typename P, typename V> + void + fill_a_shape(fllt_node(P, V)& node, + fllt_tree(P, V)& tree, + const image2d<fllt_node(P, V)*>& other_reg) + { + mln_piter(set_p) p(node.elt().holes); + for_all(p) + { + std::cout << "OK start loop" << std::endl; + bool h = true; + fllt_node(P, V)* hole = find_the_hole(node, point2d(p), other_reg); + typename fllt_node(P, V)::children_t::iterator it; + for (it = node.children().begin(); + it != node.children().end(); + it++) + { + if (set::is_subset_of(hole->elt().points, + (*it)->elt().points)) + { + h = false; + break; + } + } + if (h) + { + move_shape(node, *hole, tree, other_reg); + std::cout << "OK" << std::endl; + } + + } + } + + template <typename P, typename V> + void + merge_trees(fllt_tree(P, V)& lower, + fllt_tree(P, V)& upper, + const image2d<fllt_node(P, V)*>& low_reg, + const image2d<fllt_node(P, V)*>& upp_reg) + { + + // 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.main_branch()); + for_all(p) + { + fllt_node(P, V)& n(p); + fill_a_shape(n, lower, upp_reg); + mln_assertion(n.check_consistency()); + } + // fllt_branch_iter(P, V) q(upper.main_branch()); + // for_all(q) + // { + // fllt_node(P, V)& n(p); + // fill_a_shape(n, upper, low_reg); + // } + } + + + template <typename P, typename V> + void + visualize_deepness(image2d<value::int_u8>& output, + fllt_tree(P, V)& tree) + { + fllt_branch_iter(P, V) p(tree.main_branch()); + level::fill(output, 0); + for_all(p) + { + //std::cout << (&*p) << ":" << p.deepness() << std::endl; + mln_piter(set_p<point2d>) q((*p).elt().points); + for_all(q) + { + if (output(q) < p.deepness()) + output(q) = p.deepness(); + } + } + } + + + template <typename P, typename V> + void + visualize_bounds(image2d<value::int_u8>& output, + fllt_tree(P, V)& tree, + unsigned limit) + { + fllt_branch_iter(P, V) p(tree.main_branch()); + level::fill(output, 255); + for_all(p) + { + if ((*p).elt().points.npoints() > limit) + { + mln_piter(set_p<point2d>) q((*p).elt().points); + for_all(q) + { + mln_niter(neighb2d) n(c4(), q); + bool is_border = false; + for_all (n) + if (!((*p).elt().points).has (n)) + is_border = true; + if (is_border) + output(q) = 0; + } + } + } + } + + template <typename V> + // Fixme : return type + void + fllt(const image2d<V>& ima) + { + typedef point2d P; + + fllt_tree(P, V) upper_tree; + fllt_tree(P, V) lower_tree; + image2d<fllt_node(P, V)*> low_reg(ima.domain()); + image2d<fllt_node(P, V)*> upp_reg(ima.domain()); + + std::cout << "1/ Compute the lower level set." << std::endl; + lower_tree = compute_level_set<V, lower<V> >(ima, low_reg); + std::cout << "2/ Compute the upper level set." << std::endl; + upper_tree = compute_level_set<V, upper<V> >(ima, upp_reg); + + std::cout << "3/ Merge the two trees." << std::endl; + merge_trees(lower_tree, upper_tree, low_reg, upp_reg); + + + std::cout << "4/ Generate outputs." << std::endl; + + image2d<value::int_u8> output (ima.domain ()); + util::tree_to_image (lower_tree, output); + + if (output != ima) + { + std::cerr << "BUG!!!" << std::endl; + abort(); + } + + +// io::pgm::save(output, "out_final.pgm"); +// std::cout << "out_final.pgm generate" +// << std::endl; + + +// fllt_branch_iter(P, V) p(lower_tree.main_branch()); +// for_all(p) +// { +// std::cout << "region mere : " << (*p).parent() << std::endl; +// std::cout << " ^" << std::endl; +// std::cout << " |" << std::endl; +// std::cout << "region : " << &*p << std::endl; + +// debug::println(ima | (*p).elt().points); +// std::cout << std::endl; +// } + +// 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, lower_tree, 2000); +// debug::println(viz); +// io::pgm::save(viz, "fllt_bounds.pgm"); + } + + } // end of namespace mln::fllt + +} // end of namespace mln + + + +#endif // ! MLN_FIXME_FLLT_HH Index: trunk/milena/sandbox/garrigues/fllt/test_fllt10_inv.cc =================================================================== --- trunk/milena/sandbox/garrigues/fllt/test_fllt10_inv.cc (revision 0) +++ trunk/milena/sandbox/garrigues/fllt/test_fllt10_inv.cc (revision 1748) @@ -0,0 +1,31 @@ +# include "fllt2.hh" +# include <mln/core/image2d.hh> +# include <mln/core/clone.hh> +# include <mln/value/int_u8.hh> +# include <mln/debug/println.hh> +# include <mln/convert/to_w_window.hh> +# include <mln/core/w_window2d_int.hh> +# include <mln/convert/to_image.hh> +# include <mln/level/fill.hh> +# include <mln/io/pgm/load.hh> +# include <mln/io/pgm/save.hh> +# include <mln/io/pbm/load.hh> +# include <sstream> + + +int main() +{ + + using namespace mln; + using typename value::int_u8; + + int vs[5][10] = { {0, 0, 0, 0, 0, 1, 1, 1, 1, 1}, + {0, 1, 1, 1, 0, 1, 0, 0, 0, 1}, + {0, 1, 0, 1, 0, 1, 0, 1, 0, 1}, + {0, 1, 1, 1, 0, 1, 0, 0, 0, 1}, + {0, 0, 0, 0, 0, 1, 1, 1, 1, 1} }; + + image2d<int> ima(make::image2d(vs)); + fllt::fllt(ima); + +} Index: trunk/milena/sandbox/garrigues/fllt/test_fllt2.cc =================================================================== --- trunk/milena/sandbox/garrigues/fllt/test_fllt2.cc (revision 0) +++ trunk/milena/sandbox/garrigues/fllt/test_fllt2.cc (revision 1748) @@ -0,0 +1,33 @@ +# include "fllt_optimized.hh" +# include <mln/core/image2d.hh> +# include <mln/core/clone.hh> +# include <mln/value/int_u8.hh> +# include <mln/debug/println.hh> +# include <mln/convert/to_w_window.hh> +# include <mln/core/w_window2d_int.hh> +# include <mln/convert/to_image.hh> +# include <mln/level/fill.hh> +# include <mln/io/pgm/load.hh> +# include <mln/io/pbm/load.hh> + +int main() +{ + + using namespace mln; + + int ws[81] = {5,5,5,5,5,5,5,5,5, + 5,5,5,5,5,5,5,5,5, + 5,5,5,5,5,5,8,8,5, + 5,5,1,1,1,5,8,8,5, + 5,5,1,1,1,5,8,8,5, + 5,5,1,1,1,5,8,8,5, + 5,5,5,5,5,5,8,8,5, + 5,5,5,5,5,5,5,5,5, + 5,5,5,5,5,5,5,5,5}; + + w_window2d_int w_win = make::w_window2d(ws); + image2d<int> ima = convert::to_image(w_win); + + fllt_tree(point2d, int) t = fllt::fllt(ima); + fllt::debug(ima, t); +} Index: trunk/milena/sandbox/garrigues/fllt/test_fllt3.cc =================================================================== --- trunk/milena/sandbox/garrigues/fllt/test_fllt3.cc (revision 0) +++ trunk/milena/sandbox/garrigues/fllt/test_fllt3.cc (revision 1748) @@ -0,0 +1,31 @@ +# include "fllt2.hh" +# include <mln/core/image2d.hh> +# include <mln/core/clone.hh> +# include <mln/value/int_u8.hh> +# include <mln/debug/println.hh> +# include <mln/convert/to_w_window.hh> +# include <mln/core/w_window2d_int.hh> +# include <mln/convert/to_image.hh> +# include <mln/level/fill.hh> +# include <mln/io/pgm/load.hh> +# include <mln/io/pbm/load.hh> + +int main() +{ + + using namespace mln; + + 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} }; + + image2d<int> ima(make::image2d(vs)); + fllt::fllt(ima); + +} Index: trunk/milena/sandbox/garrigues/fllt/test_fllt4.cc =================================================================== --- trunk/milena/sandbox/garrigues/fllt/test_fllt4.cc (revision 0) +++ trunk/milena/sandbox/garrigues/fllt/test_fllt4.cc (revision 1748) @@ -0,0 +1,40 @@ +# include "fllt2.hh" +# include <mln/core/image2d.hh> +# include <mln/core/clone.hh> +# include <mln/value/int_u8.hh> +# include <mln/debug/println.hh> +# include <mln/convert/to_w_window.hh> +# include <mln/core/w_window2d_int.hh> +# include <mln/convert/to_image.hh> +# include <mln/level/fill.hh> +# include <mln/io/pgm/load.hh> +# include <mln/io/pbm/load.hh> + +int main() +{ + + using namespace mln; + + int ws[81] = {5,5,5,5,5,1,1,1,1, + 5,5,5,5,5,1,1,1,1, + 5,5,5,5,5,1,1,1,1, + 5,5,5,5,5,1,1,1,1, + 5,5,5,5,5,1,1,1,1, + 5,5,5,5,5,1,1,1,1, + 5,5,5,5,5,1,1,1,1, + 5,5,5,5,5,1,1,1,1, + 5,5,5,5,5,1,1,1,1}; + + 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); +} Index: trunk/milena/sandbox/garrigues/fllt/test_fllt5.cc =================================================================== --- trunk/milena/sandbox/garrigues/fllt/test_fllt5.cc (revision 0) +++ trunk/milena/sandbox/garrigues/fllt/test_fllt5.cc (revision 1748) @@ -0,0 +1,40 @@ +# include "fllt2.hh" +# include <mln/core/image2d.hh> +# include <mln/core/clone.hh> +# include <mln/value/int_u8.hh> +# include <mln/debug/println.hh> +# include <mln/convert/to_w_window.hh> +# include <mln/core/w_window2d_int.hh> +# include <mln/convert/to_image.hh> +# include <mln/level/fill.hh> +# include <mln/io/pgm/load.hh> +# include <mln/io/pbm/load.hh> + +int main() +{ + + using namespace mln; + + int ws[81] = {5,5,5,2,2,2,1,1,1, + 5,5,5,2,2,2,1,1,1, + 5,5,5,2,2,2,1,1,1, + 5,5,5,2,2,2,1,1,1, + 5,5,5,2,2,2,1,1,1, + 5,5,5,2,2,2,1,1,1, + 5,5,5,2,2,2,1,1,1, + 5,5,5,2,2,2,1,1,1, + 5,5,5,2,2,2,1,1,1}; + + 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); +} Index: trunk/milena/sandbox/garrigues/fllt/test_fllt6.cc =================================================================== --- trunk/milena/sandbox/garrigues/fllt/test_fllt6.cc (revision 0) +++ trunk/milena/sandbox/garrigues/fllt/test_fllt6.cc (revision 1748) @@ -0,0 +1,28 @@ +# include "fllt.hh" +# include <mln/core/image2d.hh> +# include <mln/core/clone.hh> +# include <mln/value/int_u8.hh> +# include <mln/debug/println.hh> +# include <mln/convert/to_w_window.hh> +# include <mln/core/w_window2d_int.hh> +# include <mln/convert/to_image.hh> +# include <mln/level/fill.hh> +# include <mln/io/pgm/load.hh> +# include <mln/io/pbm/load.hh> +# include <sstream> + + +int main() +{ + + using namespace mln; + + int ws[25] = {1,1,1, 1,1, + 1,255,1, 1, 1, + 1,1,1,1, 1, + 1,1,1, 255, 1, + 1,1,1, 1, 1}; + w_window2d_int w_win = make::w_window2d(ws); + image2d<int> ima = convert::to_image(w_win); + fllt::fllt(ima); +} Index: trunk/milena/sandbox/garrigues/fllt/test_fllt7.cc =================================================================== --- trunk/milena/sandbox/garrigues/fllt/test_fllt7.cc (revision 0) +++ trunk/milena/sandbox/garrigues/fllt/test_fllt7.cc (revision 1748) @@ -0,0 +1,44 @@ +# include "fllt2.hh" +# include <mln/core/image2d.hh> +# include <mln/core/clone.hh> +# include <mln/value/int_u8.hh> +# include <mln/debug/println.hh> +# include <mln/convert/to_w_window.hh> +# include <mln/core/w_window2d_int.hh> +# include <mln/convert/to_image.hh> +# include <mln/level/fill.hh> +# include <mln/io/pgm/load.hh> +# include <mln/io/pgm/save.hh> +# include <mln/io/pbm/load.hh> +# include <sstream> + + +int main() +{ + + using namespace mln; + using typename value::int_u8; + + int ws[49] = {101, 101, 101, 191, 204, 255, 191, + 101, 101, 191, 204, 204, 204, 204, + 101, 191, 191, 204, 255, 204, 191, + 204, 204, 204, 191, 191, 191, 76, + 191, 191, 204, 191, 101, 101, 76, + 204, 204, 191, 204, 101, 76, 76, + 191, 191, 191, 101, 76, 101, 0}; + + + int vs[5][5] = { {100, 200, 200, 200, 100}, + {100, 200, 255, 200, 100}, + {100, 200, 200, 200, 100}, + {100, 200, 255, 200, 100}, + {100, 200, 200, 200, 100} }; + + image2d<int> ima(make::image2d(vs)); + image2d<int_u8> out(ima.domain()); + + level::fill(out, ima); + io::pgm::save(out, "ima.pgm "); + fllt::fllt(ima); + +} Index: trunk/milena/sandbox/garrigues/fllt/test_fllt8.cc =================================================================== --- trunk/milena/sandbox/garrigues/fllt/test_fllt8.cc (revision 0) +++ trunk/milena/sandbox/garrigues/fllt/test_fllt8.cc (revision 1748) @@ -0,0 +1,33 @@ +# include "fllt2.hh" +# include <mln/core/image2d.hh> +# include <mln/core/clone.hh> +# include <mln/value/int_u8.hh> +# include <mln/debug/println.hh> +# include <mln/convert/to_w_window.hh> +# include <mln/core/w_window2d_int.hh> +# include <mln/convert/to_image.hh> +# include <mln/level/fill.hh> +# include <mln/io/pgm/load.hh> +# include <mln/io/pgm/save.hh> +# include <mln/io/pbm/load.hh> +# include <sstream> + + +int main() +{ + + 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} }; + + image2d<int> ima(make::image2d(vs)); + image2d<int_u8> out(ima.domain()); + + level::fill(out, ima); + io::pgm::save(out, "ima.pgm "); + fllt::fllt(ima); + +} Index: trunk/milena/sandbox/garrigues/fllt/test_fllt9.cc =================================================================== --- trunk/milena/sandbox/garrigues/fllt/test_fllt9.cc (revision 0) +++ trunk/milena/sandbox/garrigues/fllt/test_fllt9.cc (revision 1748) @@ -0,0 +1,41 @@ +# include "fllt2.hh" +# include <mln/core/image2d.hh> +# include <mln/core/clone.hh> +# include <mln/value/int_u8.hh> +# include <mln/debug/println.hh> +# include <mln/convert/to_w_window.hh> +# include <mln/core/w_window2d_int.hh> +# include <mln/convert/to_image.hh> +# include <mln/level/fill.hh> +# include <mln/io/pgm/load.hh> +# include <mln/io/pgm/save.hh> +# include <mln/io/pbm/load.hh> +# include <sstream> + + +int main() +{ + + using namespace mln; + using typename value::int_u8; + + int vs[5][5] = { {100, 100, 100, 100, 100}, + {100, 200, 255, 200, 100}, + {100, 200, 200, 200, 100}, + {100, 200, 255, 200, 100}, + {100, 100, 100, 100, 100} }; + + int vs_inv[5][5] = { {255, 255, 255, 255, 255}, + {255, 200, 100, 200, 255}, + {255, 200, 200, 200, 255}, + {255, 200, 100, 200, 255}, + {255, 255, 255, 255, 255} }; + + image2d<int> ima(make::image2d(vs)); + image2d<int_u8> out(ima.domain()); + + level::fill(out, ima); + io::pgm::save(out, "ima.pgm "); + fllt::fllt(ima); + +} Index: trunk/milena/sandbox/garrigues/fllt/fllt_merge.hh =================================================================== --- trunk/milena/sandbox/garrigues/fllt/fllt_merge.hh (revision 0) +++ trunk/milena/sandbox/garrigues/fllt/fllt_merge.hh (revision 1748) @@ -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(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) 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

1 0

milena r1747: Chamfer DT algorithm
by Etienne FOLIO 21 Feb '08

21 Feb '08

URL: https://svn.lrde.epita.fr/svn/oln/trunk/milena ChangeLog: 2008-02-21 Etienne FOLIO <folio(a)lrde.epita.fr> Chamfer DT algorithm. * sandbox/folio/chamfer_dt.cc: Chamfer DT algorithm (with test). * sandbox/folio/dmap.cc: Unsignificative modification. --- chamfer_dt.cc | 116 ++++++++++++++++++++++++++++++++++++++++++++++++++++++++++ dmap.cc | 1 2 files changed, 116 insertions(+), 1 deletion(-) Index: trunk/milena/sandbox/folio/chamfer_dt.cc =================================================================== --- trunk/milena/sandbox/folio/chamfer_dt.cc (revision 0) +++ trunk/milena/sandbox/folio/chamfer_dt.cc (revision 1747) @@ -0,0 +1,116 @@ +// 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. + +#include <iostream> + +#include <mln/core/image2d.hh> +#include <mln/level/fill.hh> +#include <mln/debug/println.hh> +#include <mln/make/win_chamfer.hh> +#include <mln/accu/min.hh> + +#ifndef CHAMFER_DT_HH +# define CHAMFER_DT_HH + +namespace mln +{ + template<typename I> + inline + mln_ch_value(I, float) + chamfer_dt(const Image& input_) + { + const I& input = exact(input_); + mln_precondition(input.has_data()); + + mln_ch_value(I, float) output; + initialize(output, input); + + accu::min_<int> min; + w_window2d_int chamferTop = make::mk_chamfer_3x3_int<3, 4>(); + + // initialization + { + mln_fwd_piter(I) p(input.domain()); + for_all(p) + output(p) = input(p) ? 0 : mln_max(int); + } + + // First pass. + { + mln_fwd_piter(I) p(input.domain()); + mln_qiter(w_window2d_int) q(chamferTop, p); + for_all(p) + { + min.init(); + for_all(q) + if (input.has(q) && output(q) != mln_max(int)) + min.take(output(q) + q.w()); + if (output(p) != mln_max(int)) + min.take(output(p)); + output(p) = min.to_result(); + } + } + + // Second pass. + { + w_window2d_int chamferBottom = chamferTop.sym(); + mln_bkd_piter(I) p(input.domain()); + mln_qiter(w_window2d_int) q(chamferBottom, p); + for_all(p) + { + min.init(); + for_all(q) + if (input.has(q) && output(q) != mln_max(int)) + min.take(output(q) + q.w()); + if (output(p) != mln_max(int)) + min.take(output(p)); + output(p) = min.to_result(); + } + } + + return output; + } +} + +#endif /* ! CHAMFER_DT_HH */ + +int main() +{ + using namespace mln; + + image2d<bool> ima(5,5); + bool vals[] = { 1, 1, 1, 0, 0, + 0, 0, 1, 0, 0, + 0, 0, 1, 0, 0, + 0, 0, 0, 0, 0, + 0, 0, 0, 0, 0 }; + + level::fill(ima, vals); + + debug::println(ima); + debug::println(chamfer_dt(ima)); +} Index: trunk/milena/sandbox/folio/dmap.cc =================================================================== --- trunk/milena/sandbox/folio/dmap.cc (revision 1746) +++ trunk/milena/sandbox/folio/dmap.cc (revision 1747) @@ -4,7 +4,6 @@ #include <mln/debug/println.hh> #include <mln/accu/min.hh> #include <mln/norm/l2.hh> -// #include <mln/literal/zero.hh> namespace mln {

1 0

1746: Have graph_image<P, V> work with V = bool as well.
by Roland Levillain 21 Feb '08

21 Feb '08

https://svn.lrde.epita.fr/svn/oln/trunk/milena Index: ChangeLog from Roland Levillain <roland(a)lrde.epita.fr> Have graph_image<P,V> work with V = bool as well. * mln/core/graph_image.hh (graph_image<P,V>::lvalue, graph_image<P,V>::rvalue): Redefine using std::vector's associated types `reference' and `const_reference', so as to be able to form references on the elements of the image when its value type is `bool'. Use these associated types as return types for... (graph_image<P,V>::operator()(const graph_psite&)) (graph_image<P,V>::operator()(const graph_psite&) const): ...these operators. graph_image.hh | 17 +++++++++++------ 1 file changed, 11 insertions(+), 6 deletions(-) Index: mln/core/graph_image.hh --- mln/core/graph_image.hh (revision 1745) +++ mln/core/graph_image.hh (working copy) @@ -104,10 +104,15 @@ typedef V value; /// Return type of read-write access. - typedef V& lvalue; + /// + /// We use the associated type \c reference instead of a plain + /// reference on th value type (\v V), because it's the only way + /// to safely form a reference on the element in the case of a + /// std::vector<bool>. + typedef typename std::vector<V>::reference lvalue; /// Return type of read-only access. - typedef const V& rvalue; + typedef typename std::vector<V>::const_reference rvalue; /// Value set associated type. typedef mln::value::set<value> vset; @@ -127,10 +132,10 @@ void init_(const p_graph& g, const std::vector<V>& val); /// Read-only access of pixel value at point site \p p. - const V& operator()(const graph_psite& p) const; + rvalue operator()(const graph_psite& p) const; /// Read-write access of pixel value at point site \p p. - V& operator()(const graph_psite& p); + lvalue operator()(const graph_psite& p); /// Accessors. /// \{ @@ -234,7 +239,7 @@ template <typename P, typename V> inline - const V& + typename graph_image<P, V>::rvalue graph_image<P, V>::operator()(const graph_psite& p) const { mln_precondition(&p.pg() == &this->data_->pg_); @@ -244,7 +249,7 @@ template <typename P, typename V> inline - V& + typename graph_image<P, V>::lvalue graph_image<P, V>::operator()(const graph_psite& p) { mln_precondition(&p.pg() == &this->data_->pg_);

1 0

1745: Add a missing line in the last ChangeLog entry.
by Roland Levillain 21 Feb '08

21 Feb '08

Git'll probably be useful for those cases... :P URL : https://svn.lrde.epita.fr/svn/oln/trunk/milena Index: ChangeLog =================================================================== --- ChangeLog (revision 1744) +++ ChangeLog (revision 1745) @@ -11,6 +11,7 @@ (line_graph_image<P,V>::operator()(const line_graph_psite&)) (line_graph_image<P,V>::operator()(const line_graph_psite&) const): ...these operators. + Suggested by Alexandre Duret-Lutz. * mln/morpho/level_components.hh (morpho::level_components): Remove the kludge: actually use an image of `bool' instead of an image of `int' to tick the processed points.

1 0

1744: Have line_graph_image<P, V> work with V = bool.
by Roland Levillain 21 Feb '08

21 Feb '08

https://svn.lrde.epita.fr/svn/oln/trunk/milena Index: ChangeLog from Roland Levillain <roland(a)lrde.epita.fr> Have line_graph_image<P,V> work with V = bool. * mln/core/line_graph_image.hh (line_graph_image<P,V>::lvalue, line_graph_image<P,V>::rvalue): Redefine using std::vector's associated types `reference' and `const_reference', so as to be able to form references on the elements of the image when its value type is `bool'. Use these associated types as return types for... (line_graph_image<P,V>::operator()(const line_graph_psite&)) (line_graph_image<P,V>::operator()(const line_graph_psite&) const): ...these operators. * mln/morpho/level_components.hh (morpho::level_components): Remove the kludge: actually use an image of `bool' instead of an image of `int' to tick the processed points. core/line_graph_image.hh | 17 +++++++++++------ morpho/level_components.hh | 12 +----------- 2 files changed, 12 insertions(+), 17 deletions(-) Index: mln/core/line_graph_image.hh --- mln/core/line_graph_image.hh (revision 1743) +++ mln/core/line_graph_image.hh (working copy) @@ -122,10 +122,15 @@ typedef V value; /// Return type of read-write access. - typedef V& lvalue; + /// + /// We use the associated type \c reference instead of a plain + /// reference on th value type (\v V), because it's the only way + /// to safely form a reference on the element in the case of a + /// std::vector<bool>. + typedef typename std::vector<V>::reference lvalue; /// Return type of read-only access. - typedef const V& rvalue; + typedef typename std::vector<V>::const_reference rvalue; /// Value set associated type. typedef mln::value::set<value> vset; @@ -149,10 +154,10 @@ const std::vector<V>& edge_val); /// Read-only access of pixel value at point site \p p. - const V& operator()(const line_graph_psite& p) const; + rvalue operator()(const line_graph_psite& p) const; /// Read-write access of pixel value at point site \p p. - V& operator()(const line_graph_psite& p); + lvalue operator()(const line_graph_psite& p); /// Accessors. /// \{ @@ -271,7 +276,7 @@ template <typename P, typename V> inline - const V& + typename line_graph_image<P, V>::rvalue line_graph_image<P, V>::operator()(const line_graph_psite& p) const { mln_precondition(&p.plg() == &this->data_->plg_); @@ -281,7 +286,7 @@ template <typename P, typename V> inline - V& + typename line_graph_image<P, V>::lvalue line_graph_image<P, V>::operator()(const line_graph_psite& p) { mln_precondition(&p.plg() == &this->data_->plg_); Index: mln/morpho/level_components.hh --- mln/morpho/level_components.hh (revision 1743) +++ mln/morpho/level_components.hh (working copy) @@ -99,17 +99,7 @@ const W& win = exact(win_); mln_ch_value(I, DestValue) labels(input.domain()); - /* FIXME: Yet another KLUDGE, this time required by the - specialization std::vector<bool>, which prevents forming - (mutable) reference to any of its elements. This creates - errors later with images using std::vector<bool> to store - their data (e.g., line_graph_image<P, V>). - - Alas, we cannot prevent the compiler to use this - specialization. Our workaround is simply... to use integers - instead of booleans. */ -// mln_ch_value(I, bool) processed(input.domain()); - mln_ch_value(I, int) processed(input.domain()); + mln_ch_value(I, bool) processed(input.domain()); level::fill (processed, false); DestValue cur_label = mln_min(DestValue);

1 0

1743: Enrich the p_graph interface.
by Nicolas Ballas 21 Feb '08

21 Feb '08

https://svn.lrde.epita.fr/svn/oln/trunk/milena Index: ChangeLog from Nicolas Ballas <ballas(a)lrde.epita.fr> Enrich the p_graph interface. * mln/core/p_graph.hh: Improve the p_graph interface. * mln/core/graph_psite.hh, * mln/core/graph_window_piter.hh, * mln/core/graph_image.hh, * mln/core/p_graph_piter.hh, * mln/draw/graph.hh: Remove graph implementation details. core/graph_image.hh | 10 ---- core/graph_psite.hh | 4 - core/graph_window_piter.hh | 37 +++------------ core/p_graph.hh | 106 ++++++++++++++++++++++++++++++++++++++++++++- core/p_graph_piter.hh | 2 draw/graph.hh | 2 6 files changed, 119 insertions(+), 42 deletions(-) Index: mln/core/graph_psite.hh --- mln/core/graph_psite.hh (revision 1742) +++ mln/core/graph_psite.hh (working copy) @@ -130,7 +130,7 @@ inline graph_psite::operator P() const { - return pg_.gr_.node_data(id_); + return pg_.point_from_id(id_); } template<typename P> @@ -138,7 +138,7 @@ const P& graph_psite::to_point() const { - return pg_.gr_.node_data(id_); + return pg_.point_from_id(id_); } template<typename P> Index: mln/core/p_graph.hh --- mln/core/p_graph.hh (revision 1742) +++ mln/core/p_graph.hh (working copy) @@ -72,7 +72,31 @@ bool has(const psite& p) const; - // FIXME: Should be private. + /// Return the graph point (FIXME site?) from an index + const P& point_from_id(const util::node_id& id) const; + P& point_from_id(const util::node_id& id); + + + /// Return the point contained in the first node adjacent + // to the edge id \a e. + const P& node1(const util::edge_id& e) const; + /// Return the point contained in the second node adjacent + /// to the edge id \a e. + const P& node2(const util::edge_id& e) const; + + /// Return true if the psites lhs and rhs are adjacent, or equal. + bool adjacent_or_equal(const psite& lhs, const psite& rhs) const; + + /// Return true if the nodes lhs and rhs are adjacent, or equal + bool adjacent_or_equal(const util::node_id& lhs, + const util::node_id& rhs) const; + + /// Return the graph associated to the p_graph domain: + const graph& to_graph() const; + graph& to_graph(); + + + private: graph gr_; // FIXME: (Roland) Is it really useful/needed? /* 2007-12-19: It seems so, since graph_image must implement a method @@ -134,6 +158,86 @@ (p.id() < gr_.nnodes()); } + template <typename P> + const P& + p_graph::point_from_id(const util::node_id& id) const + { + return this->gr_.node_data(id); + } + + template <typename P> + P& + p_graph::point_from_id(const util::node_id& id) + { + return this->gr_.node_data(id); + } + + template <typename P> + const P& + p_graph::node1(const util::edge_id& e) const + { + util::node_id n1 = this->gr_.edge(e).n1(); + return this->point_from_id(n1); + } + + template <typename P> + const P& + p_graph::node2(const util::edge_id& e) const + { + util::node_id n2 = this->gr_.edge(e).n2(); + return this->point_from_id(n2); + } + + template <typename P> + inline + bool + p_graph::adjacent_or_equal(const psite& lhs, const psite& rhs) const + { + assert (&lhs.pg() == this && rhs.pg() == this); + return adjacent_or_equal(lhs.id(), rhs.id()); + } + + template <typename P> + inline + bool + p_graph::adjacent_or_equal(const util::node_id& lhs, + const util::node_id& rhs) const + { + // FIXME: Likewise, this is inefficient. + + assert (lhs < this->npoints()); + assert (rhs < this->npoints()); + + if (rhs == lhs) + return true; + + // Check whether the iterator is among the neighbors of P_REF_. + typedef std::vector<util::node_id> adjacency_type; + const adjacency_type& lhs_neighbs = gr_.nodes()[lhs]->edges; + + adjacency_type::const_iterator j = + std::find (lhs_neighbs.begin(), lhs_neighbs.end(), rhs); + if (j != lhs_neighbs.end()) + return true; + + return false; + } + + template <typename P> + const typename p_graph::graph& + p_graph::to_graph() const + { + return this->gr_; + } + + template <typename P> + typename p_graph::graph& + p_graph::to_graph() + { + return this->gr_; + } + + # endif // ! MLN_INCLUDE_ONLY } // end of mln Index: mln/core/graph_window_piter.hh --- mln/core/graph_window_piter.hh (revision 1742) +++ mln/core/graph_window_piter.hh (working copy) @@ -94,6 +94,7 @@ void start(); void next_(); + bool adjacent_or_equal_to_p_ref_() const; /// Update the internal data of the iterator. void update_(); @@ -147,10 +148,7 @@ bool graph_window_fwd_piter::is_valid() const { - // FIXME: We depend too much on the implementation of util::graph - // here. The util::graph should provide the service to abstract - // these manipulations. - return id_ < p_ref_.pg().gr_.nnodes(); + return id_ < p_ref_.pg().npoints(); } template <typename P> @@ -158,7 +156,7 @@ void graph_window_fwd_piter::invalidate() { - id_ = p_ref_.pg().gr_.nnodes(); + id_ = p_ref_.pg().npoints(); } template <typename P> @@ -189,40 +187,21 @@ window, which is not the case now! (Currently, next_() behaves as win was always an elementary window.) */ do + { ++id_; + } while (is_valid() && !adjacent_or_equal_to_p_ref_()); if (is_valid()) update_(); } + template <typename P> inline bool graph_window_fwd_piter::adjacent_or_equal_to_p_ref_() const { - // FIXME: Likewise, this is inefficient. - - // Check wether the iterator points to P_REF_. - if (id_ == p_ref_.id()) - return true; - - // Check whether the iterator is among the neighbors of P_REF_. - { - // Paranoid assertion. - assert (p_ref_.id() < p_ref_.pg().gr_.nnodes()); - // FIXME: This is too low-level. Yet another service the graph - // should provide. - typedef std::vector<util::node_id> adjacency_type; - const adjacency_type& p_ref_neighbs = - p_ref_.pg().gr_.nodes()[p_ref_.id()]->edges; - adjacency_type::const_iterator j = - std::find (p_ref_neighbs.begin(), p_ref_neighbs.end(), id_); - if (j != p_ref_neighbs.end()) - return true; - } - - // Otherwise, the iterator is not adjacent to P_REF_. - return false; + return p_ref_.pg().adjacent_or_equal(p_ref_.id(), id_); } template <typename P> @@ -233,7 +212,7 @@ // Update psite_. psite_ = graph_psite(p_ref_.pg(), id_); // Update p_. - p_ = p_ref_.pg().gr_.node_data(id_); + p_ = p_ref_.pg().point_from_id(id_); } template <typename P> Index: mln/core/graph_image.hh --- mln/core/graph_image.hh (revision 1742) +++ mln/core/graph_image.hh (working copy) @@ -282,10 +282,7 @@ const P& graph_image<P, V>::node1(const util::edge_id& e) const { - // FIXME: Improve the interface of graph to avoid these low-level - // manipulations. - util::node_id n1 = this->domain().gr_.edge(e).n1(); - return this->domain().gr_.node_data(n1); + return this->domain().node1(e); } template <typename P, typename V> @@ -293,10 +290,7 @@ const P& graph_image<P, V>::node2(const util::edge_id& e) const { - // FIXME: Improve the interface of graph to avoid these low-level - // manipulations. - util::node_id n2 = this->domain().gr_.edge(e).n2(); - return this->domain().gr_.node_data(n2); + return this->domain().node2(e); } # endif // ! MLN_INCLUDE_ONLY Index: mln/core/p_graph_piter.hh --- mln/core/p_graph_piter.hh (revision 1742) +++ mln/core/p_graph_piter.hh (working copy) @@ -171,7 +171,7 @@ // Update psite_. psite_ = graph_psite(pg_, id_); // Update p_. - p_ = pg_.gr_.node_data(id_); + p_ = pg_.point_from_id(id_); } template<typename P> Index: mln/draw/graph.hh --- mln/draw/graph.hh (revision 1742) +++ mln/draw/graph.hh (working copy) @@ -120,7 +120,7 @@ line (exact(ima), gi.node1(l), gi.node2(l), link_v); // Draw the points (nodes). for (size_t p = 0; p < gi.domain().npoints(); ++p) - exact(ima)(gi.domain().gr_.node_data(p)) = gi.node_values()[p]; + exact(ima)(gi.domain().point_from_id(p)) = gi.node_values()[p]; } # endif // ! MLN_INCLUDE_ONLY

2 1