[Olena-patches] milena r1113: labeling and level for fast image in sandboy but need to fix.

URL: https://svn.lrde.epita.fr/svn/oln/trunk/milena ChangeLog: 2007-09-14 Guillaume Duhamel &lt;guillaume.duhamel(a)lrde.epita.fr&gt; labeling and level for fast image in sandboy but need to fix. * fill.hh: . * labeling.hh: New. * labeling_cpy_from_mln.hh: New. * labeling_level_fast.cc: New. * level.hh: New. * level_cpy_from_mln.hh: New. * main.cc: . * paste.hh: . --- fill.hh | 4 labeling.hh | 138 +++++++++++++++++++++++ labeling_cpy_from_mln.hh | 276 +++++++++++++++++++++++++++++++++++++++++++++++ labeling_level_fast.cc | 78 +++++++++++++ level.hh | 117 +++++++++++++++++++ level_cpy_from_mln.hh | 147 +++++++++++++++++++++++++ main.cc | 34 ++++- paste.hh | 3 8 files changed, 789 insertions(+), 8 deletions(-) Index: trunk/milena/sandbox/duhamel/labeling_cpy_from_mln.hh =================================================================== --- trunk/milena/sandbox/duhamel/labeling_cpy_from_mln.hh (revision 0) +++ trunk/milena/sandbox/duhamel/labeling_cpy_from_mln.hh (revision 1113) @@ -0,0 +1,276 @@ +// 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_CANVAS_LABELING_HH +# define MLN_CANVAS_LABELING_HH + +/*! \file mln/canvas/labeling.hh + * + * \brief Connected component labeling of the object part in a binary + * image. + */ + +# include <mln/level/fill.hh> +# include <mln/level/sort_points.hh> + +# include <mln/convert/to_window.hh> + +namespace mln +{ + + namespace canvas + { + + // General version. + + template <typename F> + struct labeling + { + F& f; + + typedef typename F::I I; + typedef typename F::N N; + typedef typename F::O O; + typedef typename F::S S; + typedef mln_point(I) point; + + // aux: + mln_ch_value(O, bool) deja_vu; + mln_ch_value(O, point) parent; + + labeling(F& f) + : f(f), + deja_vu(f.output.domain()), + parent(f.output.domain()) + { + run(); + } + + void run() + { + // init + { + f.nlabels = 0; + mln::level::fill(deja_vu, false); + f.init(); + } + // first pass + { + mln_fwd_piter(S) p(f.s); + mln_niter(N) n(f.nbh, p); + for_all(p) if (f.handles(p)) + { + make_set(p); + for_all(n) + if (f.input.has(n) && deja_vu(n)) + if (f.equiv(n, p)) + do_union(n, p); + else + f.do_no_union(n, p); + deja_vu(p) = true; + } + } + + // second pass + { + mln_bkd_piter(S) p(f.s); + for_all(p) if (f.handles(p)) + { + if (is_root(p)) + { + if (f.labels(p)) + { + if (f.nlabels == mln_max(mln_value(O))) + { + f.status = false; + return; + } + f.output(p) = ++f.nlabels; + } + } + else + f.output(p) = f.output(parent(p)); + } + f.status = true; + } + + } // end of run() + + void make_set(const point& p) + { + parent(p) = p; + f.init_attr(p); + } + + bool is_root(const point& p) const + { + return parent(p) == p; + } + + point find_root(const point& x) + { + if (parent(x) == x) + return x; + else + return parent(x) = find_root(parent(x)); + } + + void do_union(const point& n, const point& p) + { + point r = find_root(n); + if (r != p) + { + parent(r) = p; + f.merge_attr(r, p); + } + } + + }; + + + // FIXME: Fast version. + + // FIXME (ADD) + // + template <typename F> + struct labeling_fast + { + F& f; + + typedef typename F::I I; + typedef typename F::N N; + typedef typename F::O O; + typedef typename F::S S; + typedef mln_point(I) point; + + labeling_fast(F& f) + : f(f) + { + run(); + } + + void run() + { + // init + { + f.nlabels = 0; + f.init(); + } + // first pass + { + typedef mln_dpoint(N) DP; + typedef mln_point(N) P; + typedef window<DP> W; + + mln_fwd_pixter(const I) pix_input(f.input); + W win = convert::to_window(f.nbh); + + mln_qiter(W) q_input(win, P::zero); + + for_all(pix_input) + { +// if (f.handles(pix_input)) + { + // FIXME convert pix_input into point p +// make_set(p); +// for_all(q_input) +// { +// // FIXME convert q_input into point q +// point q; +// if (f.equiv(q, p)) +// do_union(q, p); +// else +// f.do_no_union(q, p); +// } + } + } + } + +// // second pass +// { +// mln_bkd_piter(S) p(f.s); +// for_all(p) if (f.handles(p)) +// { +// if (is_root(p)) +// { +// if (f.labels(p)) +// { +// if (f.nlabels == mln_max(mln_value(O))) +// { +// f.status = false; +// return; +// } +// f.output(p) = ++f.nlabels; +// } +// } +// else +// f.output(p) = f.output(parent(p)); +// } +// f.status = true; +// } + + } // end of run() + + void make_set(const point& p) + { + parent(p) = p; + f.init_attr(p); + } + +// bool is_root(const point& p) const +// { +// return parent(p) == p; +// } + +// point find_root(const point& x) +// { +// if (parent(x) == x) +// return x; +// else +// return parent(x) = find_root(parent(x)); +// } + +// void do_union(const point& n, const point& p) +// { +// point r = find_root(n); +// if (r != p) +// { +// parent(r) = p; +// f.merge_attr(r, p); +// } +// } + }; + // + // END FIXME (ADD) + + + } // end of namespace mln::canvas + +} // end of namespace mln + + +#endif // ! MLN_CANVAS_LABELING_HH Index: trunk/milena/sandbox/duhamel/fill.hh =================================================================== --- trunk/milena/sandbox/duhamel/fill.hh (revision 1112) +++ trunk/milena/sandbox/duhamel/fill.hh (revision 1113) @@ -1,3 +1,6 @@ +#ifndef FILL_HH +# define FILL_HH + # include <cstring> # include <mln/core/concept/image.hh> @@ -125,3 +128,4 @@ } } } +#endif Index: trunk/milena/sandbox/duhamel/labeling_level_fast.cc =================================================================== --- trunk/milena/sandbox/duhamel/labeling_level_fast.cc (revision 0) +++ trunk/milena/sandbox/duhamel/labeling_level_fast.cc (revision 1113) @@ -0,0 +1,78 @@ +// 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. + +/*! \file tests/labeling_foreground.cc + * + * \brief Test on mln::labeling::foreground. + */ + +#include <mln/core/image2d_b.hh> +#include <mln/core/neighb2d.hh> +#include <mln/value/int_u8.hh> +#include <mln/pw/all.hh> + +#include <mln/io/pgm/load.hh> +#include <mln/io/pgm/save.hh> +#include <mln/labeling/foreground.hh> +#include <mln/debug/println_with_border.hh> + +#include "paste.hh" +#include "fill.hh" + + +int main() +{ + using namespace mln; + using value::int_u8; + + image2d_b<value::int_u8> i1(3, 3); + image2d_b<value::int_u8> out (i1.domain ()); + + level::fill_opt2(i1, 8); + + for (int i = 0; i < 81; ++i) + i1[i] = (i * 4452) % 255; + debug::println_with_border(i1); + + unsigned n; + labeling::level(i1, true, c4(), out, n); + printf ("\nn=%u\n", n); + +// image2d_b<int_u8> +// lena = io::pgm::load("../../img/tiny.pgm"), +// out(lena.domain()); + +// debug::println_with_border(out); + +// labeling::foreground((pw::value(lena) > pw::cst(127)) | lena.domain(), +// c4(), out, n); + + // debug::println_with_border(out); + +// io::pgm::save(out, "out.pgm"); +// mln_assertion(n == 14); +} Index: trunk/milena/sandbox/duhamel/level.hh =================================================================== --- trunk/milena/sandbox/duhamel/level.hh (revision 0) +++ trunk/milena/sandbox/duhamel/level.hh (revision 1113) @@ -0,0 +1,117 @@ + +#ifndef LEVEL_HH +# define LEVEL_HH + +/*! \file mln/labeling/level.hh + * + * \brief Connected component labeling of the image objects at a given + * level. + */ + +# include <mln/labeling/base.hh> +# include <mln/level/fill.hh> +# include "labeling.hh" + +namespace mln +{ + + namespace labeling + { + + /*! Connected component labeling of the image objects at a given + * level. + * + * \param[in] input The input image. + * \param[in] val The level to consider for the labeling. + * \param[in] nbh The neighborhood. + * \param[out] output The label image. + * \param[out] nlabels The number of labels. + * + * \return Succeed or not. + */ + template <typename I, typename N, typename O> + bool level(const Image<I>& input, const mln_value(I)& val, const Neighborhood<N>& nbh, + Image<O>& output, unsigned& nlabels); + + + +# ifndef MLN_INCLUDE_ONLY + + namespace impl + { + + // Functors. + + template <typename I_, typename N_, typename O_> + struct level_t : base_<I_,N_,O_> + { + typedef mln_point(I_) P; + + // requirements from mln::canvas::labeling: + + typedef mln_pset(I_) S; + const S& s; + + void init() { mln::level::fill(this->output, 0); } + bool handles(const P& p) const { return input(p) == val; } + bool equiv(const P& n, const P&) const { return input(n) == val; } + + // end of requirements + + const mln_value(I_)& val; + + level_t(const I_& input, const mln_value(I_)& val, const N_& nbh, O_& output) + : base_<I_,N_,O_>(input, nbh, output), + s(input.domain()), + val(val) + {} + }; + + // Routines. + + template <typename I, typename N, typename O> + bool level_(const Image<I>& input, const mln_value(I)& val, const Neighborhood<N>& nbh, + Image<O>& output, unsigned& nlabels) + { + typedef impl::level_t<I,N,O> F; + F f(exact(input), val, exact(nbh), exact(output)); + canvas::labeling<F> run(f); + nlabels = f.nlabels; + return f.status; + } + + // FIXME: Add fast versions. + + template <typename I, typename N, typename O> + bool level_(const Fast_Image<I>& input, const mln_value(I)& val, const Neighborhood<N>& nbh, + Fast_Image<O>& output, unsigned& nlabels) + { + typedef impl::level_t<I,N,O> F; + F f(exact(input), val, exact(nbh), exact(output)); + canvas::labeling_fast<F> run(f); + nlabels = f.nlabels; + return f.status; + } + + // END FIX + } // end of namespace mln::labeling::impl + + + // Facade. + + template <typename I, typename N, typename O> + bool level(const Image<I>& input, const mln_value(I)& val, const Neighborhood<N>& nbh, + Image<O>& output, unsigned& nlabels) + { + mln_precondition(exact(output).domain() == exact(input).domain()); + return impl::level_(exact(input), val, nbh, output, nlabels); + } + +# endif // ! MLN_INCLUDE_ONLY + + } // end of namespace mln::labeling + +} // end of namespace mln + + +#endif // ! LEVEL_HH Index: trunk/milena/sandbox/duhamel/main.cc =================================================================== --- trunk/milena/sandbox/duhamel/main.cc (revision 1112) +++ trunk/milena/sandbox/duhamel/main.cc (revision 1113) @@ -13,20 +13,40 @@ #include "paste.hh" #include "fill.hh" +//#include "level.hh" +//#include "labeling.hh" + +#include <mln/core/image2d_b.hh> +#include <mln/core/neighb2d.hh> +#include <mln/value/int_u8.hh> +#include <mln/pw/all.hh> + +#include <mln/io/pgm/load.hh> +#include <mln/io/pgm/save.hh> +#include <mln/labeling/foreground.hh> +#include <mln/debug/println_with_border.hh> + + using namespace mln; int main (void) { - image2d_b<int> i1(3, 3); - image2d_b<int> i2(3, 3); - mln::sparse_image<mln::point2d, int> sparse; - mln::sparse_image<mln::point2d, int> sparse2; - mln::rle_image<mln::point2d, int> rle1; - mln::rle_image<mln::point2d, int> rle2; + image2d_b<value::int_u8> i1(3, 3); +// Neighborhood<value::int_u8> nbh; + +// labeling::level (i1, 3, nbh,2); +// image2d_b<int> i2(3, 3); +// mln::sparse_image<mln::point2d, int> sparse; +// mln::sparse_image<mln::point2d, int> sparse2; +// mln::rle_image<mln::point2d, int> rle1; +// mln::rle_image<mln::point2d, int> rle2; + // level::fill_opt2(i1, 8); + // debug::println_with_border(i1); - level::paste(rle1, rle2); + +// level::paste(rle1, rle2); // level::fill(sparse, 42); // debug::println_with_border(i2); Index: trunk/milena/sandbox/duhamel/level_cpy_from_mln.hh =================================================================== --- trunk/milena/sandbox/duhamel/level_cpy_from_mln.hh (revision 0) +++ trunk/milena/sandbox/duhamel/level_cpy_from_mln.hh (revision 1113) @@ -0,0 +1,147 @@ +// 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_LABELING_LEVEL_HH +# define MLN_LABELING_LEVEL_HH + +/*! \file mln/labeling/level.hh + * + * \brief Connected component labeling of the image objects at a given + * level. + */ + +# include <mln/labeling/base.hh> +# include <mln/level/fill.hh> + + +namespace mln +{ + + namespace labeling + { + + /*! Connected component labeling of the image objects at a given + * level. + * + * \param[in] input The input image. + * \param[in] val The level to consider for the labeling. + * \param[in] nbh The neighborhood. + * \param[out] output The label image. + * \param[out] nlabels The number of labels. + * + * \return Succeed or not. + */ + template <typename I, typename N, typename O> + bool level(const Image<I>& input, const mln_value(I)& val, const Neighborhood<N>& nbh, + Image<O>& output, unsigned& nlabels); + + + +# ifndef MLN_INCLUDE_ONLY + + namespace impl + { + + // Functors. + + template <typename I_, typename N_, typename O_> + struct level_t : base_<I_,N_,O_> + { + typedef mln_point(I_) P; + + // requirements from mln::canvas::labeling: + + typedef mln_pset(I_) S; + const S& s; + + void init() { mln::level::fill(this->output, 0); } + bool handles(const P& p) const { return input(p) == val; } + bool equiv(const P& n, const P&) const { return input(n) == val; } + + // end of requirements + + const mln_value(I_)& val; + + level_t(const I_& input, const mln_value(I_)& val, const N_& nbh, O_& output) + : base_<I_,N_,O_>(input, nbh, output), + s(input.domain()), + val(val) + {} + }; + + // Routines. + + template <typename I, typename N, typename O> + bool level_(const Image<I>& input, const mln_value(I)& val, const Neighborhood<N>& nbh, + Image<O>& output, unsigned& nlabels) + { + typedef impl::level_t<I,N,O> F; + F f(exact(input), val, exact(nbh), exact(output)); + canvas::labeling<F> run(f); + nlabels = f.nlabels; + return f.status; + } + + // FIXME: Add fast versions. + + // FIXME (ADD) + // + template <typename I, typename N, typename O> + bool level_(const Fast_Image<I>& input, const mln_value(I)& val, const Neighborhood<N>& nbh, + Image<O>& output, unsigned& nlabels) + { + typedef impl::level_t<I,N,O> F; + F f(exact(input), val, exact(nbh), exact(output)); + canvas::labeling_fast<F> run(f); + nlabels = f.nlabels; + return f.status; + } + + // + //END FIXME (ADD) + + } // end of namespace mln::labeling::impl + + + // Facade. + + template <typename I, typename N, typename O> + bool level(const Image<I>& input, const mln_value(I)& val, const Neighborhood<N>& nbh, + Image<O>& output, unsigned& nlabels) + { + mln_precondition(exact(output).domain() == exact(input).domain()); + return impl::level_(exact(input), val, nbh, output, nlabels); + } + +# endif // ! MLN_INCLUDE_ONLY + + } // end of namespace mln::labeling + +} // end of namespace mln + + +#endif // ! MLN_LABELING_LEVEL_HH Index: trunk/milena/sandbox/duhamel/paste.hh =================================================================== --- trunk/milena/sandbox/duhamel/paste.hh (revision 1112) +++ trunk/milena/sandbox/duhamel/paste.hh (revision 1113) @@ -27,7 +27,8 @@ template <typename I, typename J> void paste(const rle_image<I, J>& data_, rle_image<I, J>& destination_) { - imacpy_ (destination_, data_, data_.size ()); + // TO FIX + imacpy_ (destination_, data_, 42); } Index: trunk/milena/sandbox/duhamel/labeling.hh =================================================================== --- trunk/milena/sandbox/duhamel/labeling.hh (revision 0) +++ trunk/milena/sandbox/duhamel/labeling.hh (revision 1113) @@ -0,0 +1,138 @@ +#ifndef LABELING_HH +# define LABELING_HH + +/*! \file mln/canvas/labeling.hh + * + * \brief Connected component labeling of the object part in a binary + * image. + */ + +# include <mln/level/fill.hh> +# include "fill.hh" +# include <mln/level/sort_points.hh> + + +namespace mln +{ + + namespace canvas + { + + // General version. + + // In mln/canvas/labeling.hh + + + // FIXME: Fast version. + template <typename F> + struct labeling_fast + { + F& f; + + typedef typename F::I I; + typedef typename F::N N; + typedef typename F::O O; + typedef typename F::S S; + typedef mln_point(I) point; + +// // aux: +// mln_ch_value(O, bool) deja_vu; +// mln_ch_value(O, point) parent; + + labeling_fast(F& f) + : f(f)// , +// deja_vu(f.output.domain()), +// parent(f.output.domain()) + { + run(); + } + + void run() + { + // init + { + f.nlabels = 0; +// fill_opt2 (deja_vu, false); +// mln::level::fill(deja_vu, false); + f.init(); + } + // first pass + { + mln_fwd_pixter(S) p(f.s); + mln_qiter(N) q(f.nbh, p); + for_all(p) if (f.handles(p)) + { + make_set(p); + for_all(q) +// if (f.input.has(n) && deja_vu(n)) + if (f.equiv(q, p)) + do_union(q, p); + else + f.do_no_union(q, p); +// deja_vu(p) = true; + } + } + + // second pass + { + mln_bkd_piter(S) p(f.s); + for_all(p) if (f.handles(p)) + { + if (is_root(p)) + { + if (f.labels(p)) + { + if (f.nlabels == mln_max(mln_value(O))) + { + f.status = false; + return; + } + f.output(p) = ++f.nlabels; + } + } + else + f.output(p) = f.output(parent(p)); + } + f.status = true; + } + + } // end of run() + + void make_set(const point& p) + { + parent(p) = p; + f.init_attr(p); + } + + bool is_root(const point& p) const + { + return parent(p) == p; + } + + point find_root(const point& x) + { + if (parent(x) == x) + return x; + else + return parent(x) = find_root(parent(x)); + } + + void do_union(const point& n, const point& p) + { + point r = find_root(n); + if (r != p) + { + parent(r) = p; + f.merge_attr(r, p); + } + } + + }; + // END FIX + + } // end of namespace mln::canvas + +} // end of namespace mln + + +#endif // ! LABELING_HH