https://svn.lrde.epita.fr/svn/oln/trunk/milena Index: ChangeLog from Thierry Geraud <thierry.geraud@lrde.epita.fr> Fix accu::bbox and new fllt try in sandbox. * mln/core/p_array.hh (append): New overload for p_array. * mln/accu/bbox.hh (take): Fix. The "else if" was wrong; is_valid_ was not updated. * sandbox/geraud/fllt.svg.1.cc: New. * sandbox/geraud/fllt.cc: New. mln/accu/bbox.hh | 10 + mln/core/p_array.hh | 15 ++ sandbox/geraud/fllt.cc | 301 +++++++++++++++++++++++++++++++++++++++++++ sandbox/geraud/fllt.svg.1.cc | 222 +++++++++++++++++++++++++++++++ 4 files changed, 546 insertions(+), 2 deletions(-) Index: mln/core/p_array.hh --- mln/core/p_array.hh (revision 1873) +++ mln/core/p_array.hh (working copy) @@ -93,6 +93,9 @@ /// Append a point \p p. p_array<P>& append(const P& p); + /// Append an array \p other of points. + p_array<P>& append(const p_array<P>& other); + /// Clear this set. void clear(); @@ -204,6 +207,18 @@ template <typename P> inline + p_array<P>& + p_array<P>::append(const p_array<P>& other) + { + vect_.insert(vect_.end(), + other.vect().begin(), other.vect().end()); + if (! bb_needs_update_) + bb_needs_update_ = true; + return *this; + } + + template <typename P> + inline void p_array<P>::clear() { Index: mln/accu/bbox.hh --- mln/accu/bbox.hh (revision 1873) +++ mln/accu/bbox.hh (working copy) @@ -134,16 +134,19 @@ { // 'other' makes '*this' valid *this = other; + is_valid_ = true; return; } // both are valids so: const box_<P>& o_b = other.b_; for (unsigned i = 0; i < P::dim; ++i) + { if (o_b.pmin()[i] < b_.pmin()[i]) b_.pmin()[i] = o_b.pmin()[i]; - else if (o_b.pmax()[i] > b_.pmax()[i]) + if (o_b.pmax()[i] > b_.pmax()[i]) b_.pmax()[i] = o_b.pmax()[i]; } + } template <typename P> inline @@ -158,15 +161,18 @@ if (! this->is_valid_) { b_ = other; + is_valid_ = true; return; } // both are valids so: for (unsigned i = 0; i < P::dim; ++i) + { if (other.pmin()[i] < b_.pmin()[i]) b_.pmin()[i] = other.pmin()[i]; - else if (other.pmax()[i] > b_.pmax()[i]) + if (other.pmax()[i] > b_.pmax()[i]) b_.pmax()[i] = other.pmax()[i]; } + } template <typename P> inline Index: sandbox/geraud/fllt.svg.1.cc --- sandbox/geraud/fllt.svg.1.cc (revision 0) +++ sandbox/geraud/fllt.svg.1.cc (revision 0) @@ -0,0 +1,222 @@ +// Copyright (C) 2008 EPITA Research and Development Laboratory +// +// This file is part of the Olena Library. This library is free +// software; you can redistribute it and/or modify it under the terms +// of the GNU General Public License version 2 as published by the +// Free Software Foundation. +// +// This library is distributed in the hope that it will be useful, +// but WITHOUT ANY WARRANTY; without even the implied warranty of +// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU +// General Public License for more details. +// +// You should have received a copy of the GNU General Public License +// along with this library; see the file COPYING. If not, write to +// the Free Software Foundation, 51 Franklin Street, Fifth Floor, +// Boston, MA 02111-1307, USA. +// +// As a special exception, you may use this file as part of a free +// software library without restriction. Specifically, if other files +// instantiate templates or use macros or inline functions from this +// file, or you compile this file and link it with other files to +// produce an executable, this file does not by itself cause the +// resulting executable to be covered by the GNU General Public +// License. This exception does not however invalidate any other +// reasons why the executable file might be covered by the GNU General +// Public License. + +#include <mln/core/image2d.hh> +#include <mln/core/neighb2d.hh> +#include <mln/core/p_array.hh> +#include <mln/core/clone.hh> + +#include <mln/value/int_u8.hh> +# include <mln/value/rgb8.hh> + +#include <mln/io/pgm/load.hh> +#include <mln/io/pgm/save.hh> +#include <mln/io/ppm/save.hh> + +#include <mln/level/fill.hh> +#include <mln/debug/println.hh> +#include <mln/labeling/regional_minima.hh> +#include <mln/accu/bbox.hh> + +#include <mln/literal/black.hh> +#include <mln/literal/white.hh> +#include <mln/literal/colors.hh> + +#include <sstream> + + +namespace mln +{ + + namespace my + { + + template <typename N_t> + unsigned compute_gN(const N_t& N) + { + for (unsigned i = 0; i < 256; ++i) + if (N[i].npoints() != 0) + return i; + mln_invariant(0); + return 0; + } + + + template <typename I, typename A_t> + void save(const I& is, const A_t& A) + { + static unsigned counter = 0; + using value::rgb8; + + image2d<rgb8> temp(is.domain()); + level::fill(temp, literal::black); + + mln_piter(I) p(is.domain()); + for_all(p) + switch (is(p)) { + case 1: // R + temp(p) = literal::red; + break; + case 2: // N + temp(p) = literal::green; + break; + } + + mln_piter(A_t) a(A); + for_all(a) // A + temp(a) = literal::blue; + + std::stringstream filename; + filename << "./temp_" << ++counter << ".ppm"; + io::ppm::save(temp, filename.str()); + } + + + template <typename I, typename Nbh> + void fllt(const Image<I>& input_, const Neighborhood<Nbh>& nbh_) + { + const I& input = exact(input_); + const Nbh& nbh = exact(nbh_); + + unsigned l = 0, l_max; + mln_ch_value(I, unsigned) reg_min = labeling::regional_minima(input, nbh, l_max); + + // Variables. + I u = mln::clone(input); + mln_point(I) x0; + mln_value(I) g, gN; + image2d<unsigned char> is(input.domain()); + const unsigned in_R = 1, in_N = 2, in_O = 0; + + typedef p_array<mln_point(I)> arr_t; + arr_t A; + arr_t N[256]; + + accu::bbox<mln_point(I)> R_box; + + + // Step 1. + step_1: + { + if (l == l_max) + return; + l += 1; + mln_piter(I) p(input.domain()); + for_all(p) + if (reg_min(p) == l) + break; + x0 = p; + g = input(x0); + } + + // Step 2. + step_2: + { + R_box.init(); + level::fill(is, in_O); + A.append(x0); + } + + // Step 3. + step_3: + { + mln_piter(arr_t) a(A); + mln_niter(Nbh) x(nbh, a); + + my::save(is, A); + + // R <- R U A + for_all(a) + is(a) = in_R; + R_box.take(A.bbox()); + + // N <- N U { x in nbh of A and not in R } + for_all(a) + for_all(x) + if (u.has(x) && is(x) == in_O) + { + N[u(x)].append(x); + is(x) = in_N; + } + // gN = min u(x) for all x in N + gN = compute_gN(N); + + // FIXME: update the number of CC of the border of R + } + + // Step 4. + step_4: + { + // a) + if (g < gN) + { + // FIXME: DO the hole thing. + A = N[g]; + N[g].clear(); + g = gN; + gN = compute_gN(N); + goto step_3; + } + // b) + else if (g == gN) + { + A = N[g]; + N[g].clear(); + g = gN; + gN = compute_gN(N); + goto step_3; + } + // c) + else + { + mln_piter(box_<mln_point(I)>) p(R_box); + for_all(p) + if (is(p) == in_R) + u(p) = g; + goto step_1; + } + } + + } + + } // end of namespace mln::my + +} // end of namespace mln + + +int main() +{ + using namespace mln; + using value::int_u8; + + image2d<int_u8> lena; + io::pgm::load(lena, "../../img/tiny.pgm"); + + my::fllt(lena, c4()); + io::pgm::save(lena, "./out.pgm"); + +} Index: sandbox/geraud/fllt.cc --- sandbox/geraud/fllt.cc (revision 0) +++ sandbox/geraud/fllt.cc (revision 0) @@ -0,0 +1,301 @@ +// Copyright (C) 2008 EPITA Research and Development Laboratory +// +// This file is part of the Olena Library. This library is free +// software; you can redistribute it and/or modify it under the terms +// of the GNU General Public License version 2 as published by the +// Free Software Foundation. +// +// This library is distributed in the hope that it will be useful, +// but WITHOUT ANY WARRANTY; without even the implied warranty of +// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU +// General Public License for more details. +// +// You should have received a copy of the GNU General Public License +// along with this library; see the file COPYING. If not, write to +// the Free Software Foundation, 51 Franklin Street, Fifth Floor, +// Boston, MA 02111-1307, USA. +// +// As a special exception, you may use this file as part of a free +// software library without restriction. Specifically, if other files +// instantiate templates or use macros or inline functions from this +// file, or you compile this file and link it with other files to +// produce an executable, this file does not by itself cause the +// resulting executable to be covered by the GNU General Public +// License. This exception does not however invalidate any other +// reasons why the executable file might be covered by the GNU General +// Public License. + +#include <mln/core/image2d.hh> +#include <mln/core/neighb2d.hh> +#include <mln/core/p_array.hh> +#include <mln/core/clone.hh> +#include <mln/core/image_if_value.hh> + +#include <mln/value/int_u8.hh> +# include <mln/value/rgb8.hh> + +#include <mln/io/pgm/load.hh> +#include <mln/io/pgm/save.hh> +#include <mln/io/ppm/save.hh> + +#include <mln/level/fill.hh> +#include <mln/debug/println.hh> +#include <mln/labeling/regional_minima.hh> +#include <mln/accu/bbox.hh> +#include <mln/geom/bbox.hh> + +#include <mln/literal/black.hh> +#include <mln/literal/white.hh> +#include <mln/literal/colors.hh> + +#include <sstream> + + +namespace mln +{ + + namespace my + { + + template <typename N_t, typename G> + void update_gN(const N_t& N, G& gN) + { + for (unsigned g = 0; g < 256; ++g) + if (N[g].npoints() != 0) + { + gN = g; + return; + } + // if N is empty, gN is the max value. + gN = 255; + } + + + template <typename N_t> + void print_N(const N_t& N) + { + for (unsigned i = 0; i < 256; ++i) + { + if (N[i].npoints() == 0) + continue; + std::cout << i << ": " << N[i] << std::endl; + } + } + + template <typename N_t> + void clear_N(N_t& N) + { + for (unsigned i = 0; i < 256; ++i) + N[i].clear(); + } + + + + template <typename T> + image2d<T> enlarge(const image2d<T>& input, unsigned coef) + { + unsigned + nrows_ = coef * geom::nrows(input), + ncols_ = coef * geom::ncols(input); + image2d<T> output(nrows_, ncols_); + for (int row = 0; row < nrows_; ++row) + for (int col = 0; col < ncols_; ++col) + output.at(row, col) = input.at(row / coef, col / coef); + return output; + } + + + template <typename I> + void save(const I& is, const std::string& name = "") + { + static unsigned counter = 0; + using value::rgb8; + + image2d<rgb8> temp(is.domain()); + level::fill(temp, literal::black); + + mln_piter(I) p(is.domain()); + for_all(p) + switch (is(p)) { + case 1: // R + temp(p) = literal::red; + break; + case 2: // N + temp(p) = literal::green; + break; + case 3: // A + temp(p) = literal::blue; + break; + } + + if (name == "") + { + std::stringstream filename; + filename << "./temp_" << ++counter << ".ppm"; + io::ppm::save(my::enlarge(temp, 10), filename.str()); + } + else + io::ppm::save(temp, name); + } + + + template <typename I, typename Nbh> + void fllt(const Image<I>& input_, const Neighborhood<Nbh>& nbh_) + { + const I& input = exact(input_); + const Nbh& nbh = exact(nbh_); + + unsigned l = 0, l_max; + mln_ch_value(I, unsigned) reg_min = labeling::regional_minima(input, nbh, l_max); + + // Variables. + I u = mln::clone(input); + mln_point(I) x0; + mln_value(I) g, gN; + image2d<unsigned char> is(input.domain()); + const unsigned in_R = 1, in_N = 2, in_A = 3, in_O = 0; + + typedef p_array<mln_point(I)> arr_t; + arr_t A, R; + R.reserve(input.npoints()); + arr_t N[256]; + + accu::bbox<mln_point(I)> R_box; + + unsigned n_step_1 = 0, n_step_3 = 0; + + // Step 1. + step_1: + { + if (l == l_max) + goto the_end; + + ++n_step_1; + + l += 1; + mln_piter(I) p(input.domain()); + for_all(p) + if (reg_min(p) == l) + break; + x0 = p; + g = input(x0); + } + + // Step 2. + step_2: + { + level::fill(is, in_O); + // R <- 0 + R_box.init(); + R.clear(); + // A <- { x0 } + A.clear(); + A.append(x0); + is(x0) = in_A; + // N <- 0 + clear_N(N); + } + + // Step 3. + step_3: + { + ++n_step_3; + + mln_piter(arr_t) a(A); + mln_niter(Nbh) x(nbh, a); + + + my::save(is); + + + // R <- R U A + if (A.npoints() == 0) + goto the_end; + + R.append(A); + for_all(a) + { + mln_invariant(is(a) == in_A); + is(a) = in_R; + } + mln_invariant(R.npoints() == (is | in_R).npoints()); + R_box.take(A.bbox()); + + // N <- N U { x in nbh of A and not in R } + for_all(a) + for_all(x) + if (u.has(x) && is(x) == in_O) + { + N[u(x)].append(x); + is(x) = in_N; + } + // gN = min u(x) for all x in N + update_gN(N, gN); + + // FIXME: update the number of CC of the border of R + } + + // Step 4. + step_4: + { + // a) + if (g < gN) + { + g = gN; + // FIXME: DO the hole thing. + A = N[g]; + mln_piter(arr_t) a(A); + for_all(a) + { + mln_invariant(is(a) == in_N); + is(a) = in_A; + } + N[g].clear(); + goto step_3; + } + // b) + else if (g == gN) + { + A = N[g]; + mln_piter(arr_t) a(A); + for_all(a) + { + mln_invariant(is(a) == in_N); + is(a) = in_A; + } + N[g].clear(); + goto step_3; + } + // c) + else + { + mln_invariant(R_box.to_result() == geom::bbox(is | in_R)); + mln_piter(arr_t) r(R); + for_all(r) + u(r) = g; + goto step_1; + } + } + + the_end: + std::cout << n_step_1 << ' ' << n_step_3 << std::endl; + + } + + } // end of namespace mln::my + +} // end of namespace mln + + +int main() +{ + using namespace mln; + using value::int_u8; + + image2d<int_u8> lena; + io::pgm::load(lena, "../../img/tiny.pgm"); + + my::fllt(lena, c4()); + io::pgm::save(lena, "./out.pgm"); + +}