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<P> points;
+ p_set<P> holes;
+ /// Tell if his parent if brighter or not. Nb : if the parent
+ /// if brighter, the node come from the lower level set
+ bool brighter;
+ };
+
+# 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 = " << p <<
std::endl;
+ x0 = p;
+ // g <- u(x0)
+ g = ima(x0);
+ //std::cout << "g = " << g << std::endl;
+ //std::cout << "exiting step 1" << std::endl;
+ }
+
+ template <typename P>
+ void step2 (p_set<P>& A,
+ p_set<P>& R,
+ p_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,
+ p_set<P>& A,
+ p_set<P>& R,
+ p_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(p_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,
+ p_set<P>& A,
+ p_set<P>& R,
+ p_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;
+
+ // 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>) 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<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(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<P>& A,
+ p_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 p_set<P>& R,
+ const V& g)
+ {
+ //std::cout << "entering step 4_3" << std::endl;
+
+ // set the gray-level of the pixels of R to g.
+ mln_piter(p_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.
+ p_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
+
+ 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<I>& input, const Neighborhood<N>&
nbh,
+ Image<O>& output, unsigned& nlabels)
+ {
+ return labeling::regional_minima(input, nbh,
+ output, nlabels);
+ }
+
+ static const int inc = 1;
+ static const bool parent_is_brighter = true;
+ typedef accu::min accu_for_gn;
+
+ static const neighb2d& bdr_nbh() { return c8(); }
+ static const neighb2d& reg_nbh() { return c4(); }
+
+ };
+
+
+
+ // UPPER LEVEL SET : region = c8, border = c4
+ template <typename V>
+ struct upper
+ {
+ typedef lower<V> opposite;
+
+ static bool
+ compare(const V& u, const V& v)
+ {
+ return u > v;
+ }
+
+ template <typename I, typename N, typename O>
+ static bool
+ regional_extremum(const Image<I>& input, const Neighborhood<N>&
nbh,
+ Image<O>& output, unsigned& nlabels)
+ {
+ return labeling::regional_maxima(input, nbh,
+ output, nlabels);
+ }
+
+ static const int inc = -1;
+ static const bool parent_is_brighter = false;
+ typedef accu::max accu_for_gn;
+
+ static const neighb2d& bdr_nbh() { return c4(); }
+ static const neighb2d& reg_nbh() { return c8(); }
+ };
+
+ // Fwd declarations.
+ template <typename P, typename V, typename F>
+ void
+ fill_a_shape(fllt_node(P, V)& node,
+ fllt_tree(P, V)& tree,
+ const image2d<fllt_node(P, V)*>& node_reg,
+ const image2d<fllt_node(P, V)*>& hole_reg);
+
+ template <typename P, typename V, typename F>
+ void
+ move_shape(fllt_node(P, V)& node,
+ fllt_node(P, V)& hole,
+ fllt_tree(P, V)& tree,
+ const image2d<fllt_node(P, V)*>& hole_reg,
+ const image2d<fllt_node(P, V)*>& other_reg)
+ {
+ // FIXME : debug to remove.
+ // std::cout << " [move_shape] "<< &hole
<< " as son of "<< &node << std::endl;
+ //node.elt().points = set::uni(hole.elt().points, node.elt().points);
+ node.add_child(&hole);
+ fill_a_shape<P,V,typename F::opposite>(hole, tree, hole_reg, other_reg);
+ }
+
+ template <typename P, typename V, typename F>
+ fllt_node(P, V)*
+ find_the_hole(fllt_node(P, V)& node,
+ const P p,
+ const image2d<fllt_node(P, V)*>& other_reg)
+ {
+ fllt_node(P, V)* s = other_reg(p);
+ mln_assertion(s);
+ while (s->parent() &&
F::opposite::compare(s->parent()->elt().value, node.elt().value))
+ //FIXME : Was while (s->parent() && (s->parent()->elt().value <
node.elt().value))
+ {
+ mln_assertion(s);
+ s = s->parent();
+ mln_assertion(s);
+ }
+// std::cout << " [Find the hole] of " << p
+// << " from " << &node
+// << " return " << s
+// << std::endl;
+ return s;
+ }
+
+ template <typename P, typename V, typename F>
+ void
+ fill_a_shape(fllt_node(P, V)& node,
+ fllt_tree(P, V)& tree,
+ const image2d<fllt_node(P, V)*>& node_reg,
+ const image2d<fllt_node(P, V)*>& hole_reg)
+ {
+// std::cout << "[Start fill_a_shape] " << &node <<
" "
+// << node.elt().holes.npoints()
+// << " holes." << std::endl;
+
+ if (node.elt().holes.npoints() == 0)
+ {
+ // std::cout << "[End fill_a_shape]" << std::endl;
+ return;
+ }
+ mln_piter(p_set<P>) p(node.elt().holes);
+ for_all(p)
+ {
+ bool h = true;
+
+ fllt_node(P, V)* hole;
+ if (node.elt().brighter == F::parent_is_brighter)
+ hole = find_the_hole<P,V,F>(node, point2d(p), hole_reg);
+ else
+ hole = find_the_hole<P,V,typename F::opposite>(node, point2d(p), node_reg);
+
+ mln_assertion(hole);
+
+ typename fllt_node(P, V)::children_t::iterator it;
+ for (it = node.children().begin();
+ it != node.children().end();
+ it++)
+ {
+ // Browse the hole of each child.
+ mln_piter(p_set<P>) q((*it)->elt().holes);
+ for_all(q)
+ {
+ fllt_node(P, V)* child_hole = find_the_hole<P,V,F>((**it), point2d(q),
hole_reg);
+ if (set::is_subset_of(hole->elt().points,
+ child_hole->elt().points))
+
+// 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<P> points;
+ p_set<P> holes;
+ /// Tell if his parent if brighter or not. Nb : if the parent
+ /// if brighter, the node come from the lower level set
+ bool brighter;
+ };
+
+ } // end of namespace mln::fllt
+
+} // end of namespace mln
+
+
+
+#endif // ! MLN_FIXME_FLLT_TYPES_HH
Index: trunk/milena/sandbox/garrigues/fllt/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_"
<< i << "_" << j << ".pgm";
+ std::cout << path.str () << std::endl;
+ image2d<value::int_u8> 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<P> points;
+ set_p<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 = " << p <<
std::endl;
+ x0 = p;
+ // g <- u(x0)
+ g = ima(x0);
+ //std::cout << "g = " << g << std::endl;
+ //std::cout << "exiting step 1" << std::endl;
+ }
+
+ template <typename P>
+ void step2 (set_p<P>& A,
+ set_p<P>& R,
+ set_p<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<P>& A,
+ set_p<P>& R,
+ set_p<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<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<P>& A,
+ set_p<P>& R,
+ set_p<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>) 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<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<P>& A,
+ set_p<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<P>& R,
+ const V& g)
+ {
+ //std::cout << "entering step 4_3" << std::endl;
+
+ // set the gray-level of the pixels of R to g.
+ mln_piter(set_p<P>) p(R);
+ 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<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<I>& 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<I>& 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>) 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>) p(node.elt().holes);
+ for_all(p)
+ {
+ bool h = true;
+
+ fllt_node(P, V)* hole;
+ if (node.elt().brighter == F::parent_is_brighter)
+ hole = find_the_hole<P,V,F>(node, point2d(p), hole_reg);
+ else
+ hole = find_the_hole<P,V,typename F::opposite>(node, point2d(p), node_reg);
+
+ mln_assertion(hole);
+
+ typename fllt_node(P, V)::children_t::iterator it;
+ for (it = node.children().begin();
+ it != node.children().end();
+ it++)
+ {
+ // Browse the holes of each child.
+ mln_piter(p_set<P>) q((*it)->elt().holes);
+ for_all(q)
+ {
+ fllt_node(P, V)* child_hole = find_the_hole<P,V,F>((**it), point2d(q),
hole_reg);
+ if (set::is_subset_of(hole->elt().points,
+ child_hole->elt().points))
+ {
+ h = false;
+ break;
+ }
+
+ }
+ if (!h)
+ break;
+ }
+ if (h)
+ move_shape<P,V,F>(node, *hole, tree, hole_reg, node_reg);
+ }
+
+ node.elt().holes.clear();
+ }
+
+ template <typename P, typename V>
+ fllt_tree(P, V)
+ merge_trees(fllt_tree(P, V)& lower_tree,
+ fllt_tree(P, V)& upper_tree,
+ const image2d<fllt_node(P, V)*>& low_reg,
+ const image2d<fllt_node(P, V)*>& upp_reg,
+ const image2d<V>& ima)
+ {
+
+ // In order to merge the trees, we only have to find for each shape S
+ // with a hole H in it whether one of its children has a hole HŽ
+ // containing H. If it is the case, we do nothing. Otherwise, we
+ // put the shape of the hole H (and all its descendants) as child of
+ // the shape .
+ {
+ fllt_branch_iter(P, V) p(lower_tree.main_branch());
+ for_all(p)
+ {
+ fllt_node(P, V)& n(p);
+ fill_a_shape< P, V, lower<V> >(n, lower_tree, low_reg, upp_reg);
+ mln_assertion(lower_tree.check_consistency());
+ mln_assertion(upper_tree.check_consistency());
+ }
+
+ }
+
+ {
+ fllt_branch_iter(P, V) p(upper_tree.main_branch());
+ for_all(p)
+ {
+ fllt_node(P, V)& n(p);
+ fill_a_shape< P, V, upper<V> >(n, upper_tree, upp_reg, low_reg);
+ mln_assertion(lower_tree.check_consistency());
+ mln_assertion(upper_tree.check_consistency());
+ }
+ }
+
+ // FIXME : this is a wrong way to choose the root of the result
+ // tree. lower and upper root doesn't have the same level, we
+ // want the right level for the background.
+ fllt_tree(P, V)* main_tree = &lower_tree;
+ fllt_tree(P, V)* other_tree = &upper_tree;
+
+ if (lower_tree.root()->elt().points.npoints() >= ima.domain().npoints())
+ {
+ main_tree = &upper_tree;
+ other_tree = &lower_tree;
+ }
+
+ typename fllt_node(P, V)::children_t::iterator it;
+ for (it = other_tree->root()->children().begin();
+ it != other_tree->root()->children().end(); )
+ {
+ main_tree->root()->add_child(*it);
+ }
+ mln_assertion(main_tree->check_consistency());
+ return *main_tree;
+ }
+
+ } // end of namespace mln::fllt
+
+} // end of namespace mln
+
+#endif // ! MLN_FIXME_FLLT_MERGE_HH