URL: https://svn.lrde.epita.fr/svn/oln/trunk/milena ChangeLog: 2007-10-23 Matthieu Garrigues <garrigues@lrde.epita.fr> Update fllt. * mln/core/a_point_of.hh: New, give a point of an image * mln/util/abr.hh: (abr::set_parent) New, (abr::get_parent) New, (abr::content) New. * sandbox/garrigues/fllt.hh: Update fllt. * sandbox/garrigues/test_fllt.cc: Update. --- mln/core/a_point_of.hh | 63 +++++++++++++++++++++++ mln/util/abr.hh | 40 +++++++++++++- sandbox/garrigues/fllt.hh | 110 ++++++++++++++++++++++++++++++++++++----- sandbox/garrigues/test_fllt.cc | 8 +- 4 files changed, 201 insertions(+), 20 deletions(-) Index: trunk/milena/mln/core/a_point_of.hh =================================================================== --- trunk/milena/mln/core/a_point_of.hh (revision 0) +++ trunk/milena/mln/core/a_point_of.hh (revision 1380) @@ -0,0 +1,63 @@ +// 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_CORE_A_POINT_OF_HH +# define MLN_CORE_A_POINT_OF_HH + +/*! \file mln/core/a_point_oft.hh + * + * \brief Give a point of an image. + */ + +# include <mln/core/concept/image.hh> +# include <mln/core/exact.hh> + +namespace mln +{ + + /// Give a point of an image. + template <typename I> + mln_point(I) a_point_of(const Image<I>& ima); + + +# ifndef MLN_INCLUDE_ONLY + + template <typename I> + mln_point(I) a_point_of(const Image<I>& ima_) + { + const I& ima = exact(ima_); + mln_piter(I) p(ima.domain()); + p.start(); + return p; + } + +# endif // ! MLN_INCLUDE_ONLY + +} // end of namespace mln + + +#endif // ! MLN_CORE_A_POINT_OF_HH Index: trunk/milena/mln/util/abr.hh =================================================================== --- trunk/milena/mln/util/abr.hh (revision 1379) +++ trunk/milena/mln/util/abr.hh (revision 1380) @@ -49,13 +49,17 @@ abr(); abr(T& elt); + T& content(); + const T& content() const; void add_child(T& elt); + void set_parent(abr<T>* parent); + abr<T>* get_parent(); void print_rec(int n) const; void print(void) const; int search_rec(abr<T>** res, T& elt); abr<T>* search(T& elt); - T& elt_; + T elt_; abr<T>* parent_; std::vector< abr<T>* > child_; }; @@ -65,8 +69,7 @@ template <typename T> abr<T>::abr() - : elt_ (0), - parent_ (0) + : parent_ (0) { } @@ -78,6 +81,20 @@ } template <typename T> + const T& + abr<T>::content() const + { + return elt_; + } + + template <typename T> + T& + abr<T>::content() + { + return elt_; + } + + template <typename T> void abr<T>::add_child(T& elt) { @@ -88,6 +105,23 @@ } template <typename T> + void + abr<T>::set_parent(abr<T>* parent) + { + mln_assertion(parent != 0); + parent_ = parent; + parent->child_.push_back(this); + } + + + template <typename T> + abr<T>* + abr<T>::get_parent() + { + return parent_; + } + + template <typename T> int abr<T>::search_rec(abr<T>** res, T& elt) { Index: trunk/milena/sandbox/garrigues/fllt.hh =================================================================== --- trunk/milena/sandbox/garrigues/fllt.hh (revision 1379) +++ trunk/milena/sandbox/garrigues/fllt.hh (revision 1380) @@ -44,6 +44,7 @@ # 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/convert/to_image.hh> @@ -56,6 +57,8 @@ # include <mln/set/diff.hh> # include <mln/set/inter.hh> +# include <mln/util/abr.hh> + # include <mln/labeling/regional_minima.hh> # include <mln/labeling/level.hh> @@ -65,6 +68,19 @@ namespace mln { + namespace fllt + { + + template <typename P> + struct fllt_node + { + set_p<P> points; + set_p<P> holes; + }; + + # define fllt_node(P) util::abr< fllt_node<P> > + + // LOWER LEVEL SET : region = c4, border = c8 // UPPER LEVEL SET : region = c8, border = c4 @@ -145,7 +161,13 @@ set_p<P>& N, V& gn) { + static bool finished = false; std::cout << "entering step 3" << std::endl; + + // Stop the algorithm. + if (finished) + { gn = 0; return; } + // N <- N union {x neighbor of a pixel in a\R} mln_piter(set_p<P>) qa(A); for_all(qa) @@ -167,8 +189,13 @@ debug::println(u | R); // gn <- min u(x) x belongs to N. + if ((u | set::inter(N, u.domain())).npoints() > 0) gn = level::compute<accu::min>(u | set::inter(N, u.domain())); - + else + { + finished = true; + gn++; + } std::cout << std::endl << "gN = " << gn << std::endl; // R <- R union A // tag the pixels of A. @@ -186,12 +213,36 @@ template <typename V, typename P> void step4_1 (image2d<V>& u, set_p<P>& A, -// set_p<P>& R, + set_p<P>& R, set_p<P>& N, V& g, - V& gn) + V& gn, + fllt_node(P)* current_region, + image2d<fllt_node(P)*>& regions + ) { std::cout << "entering step 4_1" << std::endl; + + // Create a new conected component. + // FIXME : we can make it faster. + //mln_piter(S) p(set::inter(N, u.domain()) | pw::value(u) == pw::cst(g)); + mln_piter(set_p<P>) p(R); + current_region = new fllt_node(P)(); + for_all(p) + { + if (regions(p) == 0) + { + current_region->content().points.insert(p); + regions(p) = current_region; + } + else + { + if (regions(p)->get_parent() == 0) + regions(p)->set_parent(current_region); + } + } + + // Count the number of conected components of the border of R. image2d<int> tmp(u.domain().to_larger(1)); image2d<bool> border_ima(u.domain().to_larger(1)); @@ -208,13 +259,18 @@ { // 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. -// Remove from N border of holes???. + // WARNING : We trust labeling::level to label the exterior border with 1. + current_region->content().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} @@ -239,7 +295,10 @@ void step4_2 (const image2d<V>& u, set_p<P>& A, set_p<P>& N, - V& g) + V& g, + fllt_node(P)* current_region, + image2d<fllt_node(P)*>& regions + ) { std::cout << "entering step 4_2" << std::endl; @@ -248,6 +307,21 @@ // N <- N\{x belongs to N / u(x) == g} N = set::diff(N, N | pw::value(u) == pw::cst(g)); +// // FIXME +// typedef mln::pset_if< +// mln::set_p<mln::point_<mln::grid::square, int> >, +// mln::fun::eq_p2b_expr_<mln::pw::value_<mln::image2d<int> >, +// mln::pw::cst_<int> > > S; + +// // Update the current region +// //mln_piter(S) p(set::inter(N, u.domain()) | pw::value(u) == pw::cst(g)); +// mln_piter(set_p<P>) p(A); +// for_all(p) +// { +// if (regions(p) == 0) +// regions(p) = current_region; +// } + std::cout << "A :" << std::endl; if (A.npoints()) debug::println(u | A); @@ -280,14 +354,12 @@ } - - - template <typename V> void compute_level_set(const image2d<V>& ima) { typedef point2d P; typedef image2d<V> I; + // FIXME typedef mln::image_if< mln::image2d<V>, mln::fun::greater_p2b_expr_<mln::pw::value_<mln::image2d<V> >, @@ -302,6 +374,10 @@ image2d<V> u = clone(ima); image2d<bool> tagged(ima.domain()); + fllt_node(P)* current_region; + image2d<fllt_node(P)*> regions(ima.domain()); + level::fill(regions, 0); + unsigned nlabels; labeling::regional_minima(ima, c4(), min_locals, nlabels); @@ -329,7 +405,7 @@ /// step4. if (g < gn) { - step4_1(u, A, N, g, gn); + step4_1(u, A, R, N, g, gn, current_region, regions); // GO TO 3) continue; } @@ -337,7 +413,7 @@ if (g == gn) { - step4_2(u, A, N, g); + step4_2(u, A, N, g, current_region, regions); // GO TO 3) continue; } @@ -351,8 +427,16 @@ } } } - } - } + } // end of Algorithm + std::cout << "END OF ALGORITHM" << std::endl; + + + debug::println(regions); + debug::println(ima | regions(make::point2d(-4,-1))->content().points); + + } // end of compute_level_set + + } // end of namespace mln::fllt } // end of namespace mln Index: trunk/milena/sandbox/garrigues/test_fllt.cc =================================================================== --- trunk/milena/sandbox/garrigues/test_fllt.cc (revision 1379) +++ trunk/milena/sandbox/garrigues/test_fllt.cc (revision 1380) @@ -14,9 +14,9 @@ 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,4,2,3,2,1,1, - 1,3,3,4,2,3,2,1,1, + 1,2,4,2,1,2,1,9,1, + 1,3,3,4,2,3,2,9,1, + 1,3,3,4,2,3,2,9,1, 1,3,3,4,2,3,2,1,1, 1,3,3,4,2,3,2,1,1}; @@ -25,5 +25,5 @@ image2d<int> ima = convert::to_image(w_win); debug::println(ima); - compute_level_set(ima); + fllt::compute_level_set(ima); }