URL: https://svn.lrde.epita.fr/svn/oln/trunk/milena ChangeLog: 2007-09-11 Simon Nivault <simon.nivault@lrde.epita.fr> Move fast erosion and add fast dilation with max accu * mln/accu/max_h.hh: New. Max Accu. * mln/level/ero.hh: Rename as... * mln/morpho/erosion_fast.hh: ...this. * mln/morpho/dilation_fast.hh: Fast dilation. * tests/morpho_dilation_max_h.cc: New. * tests/morpho_erosion_min_h.cc: Update. --- mln/accu/max_h.hh | 241 +++++++++++++++++++++++++++++++++++++++++ mln/morpho/dilation_fast.hh | 188 +++++++++++++++++++++++++++++++ mln/morpho/erosion_fast.hh | 188 +++++++++++++++++++++++++++++++ tests/morpho_dilation_max_h.cc | 65 +++++++++++ tests/morpho_erosion_min_h.cc | 4 5 files changed, 684 insertions(+), 2 deletions(-) Index: trunk/milena/tests/morpho_dilation_max_h.cc =================================================================== --- trunk/milena/tests/morpho_dilation_max_h.cc (revision 0) +++ trunk/milena/tests/morpho_dilation_max_h.cc (revision 1099) @@ -0,0 +1,65 @@ +// 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/morpho_erosion.cc + * + * \brief Test on mln::morpho::erosion. + */ + +#include <mln/core/image2d_b.hh> +#include <mln/core/win/rectangle2d.hh> +#include <mln/core/window2d.hh> + +#include <mln/io/pgm/load.hh> +#include <mln/io/pgm/save.hh> + +#include <mln/value/int_u8.hh> +#include <mln/morpho/dilation_fast.hh> + +#include <mln/convert/to_vec_p.hh> +#include <mln/convert/to_window.hh> + + +int main() +{ + using namespace mln; + using value::int_u8; + + win::rectangle2d rec(21, 21); + border::thickness = 66; + + image2d_b<int_u8> lena = io::pgm::load("../img/lena.pgm"); + + { + vec_p<point2d> vec = convert::to_vec_p(rec, point2d::zero); + window2d win = convert::to_window(vec); + + image2d_b<int_u8> out(lena.domain()); + morpho::dilation_fast(lena, win, out); + io::pgm::save(out, "out.pgm"); + } +} Index: trunk/milena/tests/morpho_erosion_min_h.cc =================================================================== --- trunk/milena/tests/morpho_erosion_min_h.cc (revision 1098) +++ trunk/milena/tests/morpho_erosion_min_h.cc (revision 1099) @@ -38,7 +38,7 @@ #include <mln/io/pgm/save.hh> #include <mln/value/int_u8.hh> -#include <mln/level/ero.hh> +#include <mln/morpho/erosion_fast.hh> #include <mln/convert/to_vec_p.hh> #include <mln/convert/to_window.hh> @@ -59,7 +59,7 @@ window2d win = convert::to_window(vec); image2d_b<int_u8> out(lena.domain()); - level::ero(lena, win, out); + morpho::erosion_fast(lena, win, out); io::pgm::save(out, "out.pgm"); } } Index: trunk/milena/mln/morpho/erosion_fast.hh =================================================================== --- trunk/milena/mln/morpho/erosion_fast.hh (revision 0) +++ trunk/milena/mln/morpho/erosion_fast.hh (revision 1099) @@ -0,0 +1,188 @@ +// 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_MORPHO_EROSION_FAST_HH +# define MLN_MORPHO_EROSION_FAST_HH + +/*! \file mln/morpho/erosion_fast.hh + * + * \brief Ero filtering of an image. + * + * \todo Add Fast_Image versions. + */ + +# include <mln/core/concept/image.hh> +# include <mln/core/window.hh> +# include <mln/geom/shift.hh> +# include <mln/set/diff.hh> + +# include <mln/canvas/browsing/snake_fwd.hh> +# include <mln/accu/min_h.hh> + + +namespace mln +{ + + namespace morpho + { + + /*! Compute in \p output the ero filter of image \p input by + * the window \p win. + * + * \param[in] input The image to be filtered. + * \param[in] win The window. + * \param[out] output The output image. + * + * \pre \p input and \p output have to be initialized. + */ + template <typename I, typename W, typename O> + void erosion_fast(const Image<I>& input, const Window<W>& win, + Image<O>& output); + + + + +# ifndef MLN_INCLUDE_ONLY + + namespace impl + { + + + // Functors. + + + template <typename I, typename W, typename O> + struct erosion_fast_t + { + typedef mln_point(I) P; + typedef mln_dpoint(I) D; + + // i/o + + const I& input; + const W& win; + O& output; + + // aux data + + accu::min_h<mln_vset(I)> min; + P p; + window<D> win_fp, win_fm, win_bp, win_bm, win_dp, win_dm; + mln_qiter(W) q_fp, q_fm, q_bp, q_bm, q_dp, q_dm; + + // ctor + + erosion_fast_t(const I& input_, const W& win_, O& output_) + : + // i/o + input(exact(input_)), + win(exact(win_)), + output(exact(output_)), + // aux data + min(input.values()), + p(), + win_fp(set::diff(win, geom::shift(win, left))), + win_fm(set::diff(geom::shift(win, left), win)), + win_bp(set::diff(win, geom::shift(win, right))), + win_bm(set::diff(geom::shift(win, right), win)), + win_dp(set::diff(win, geom::shift(win, up))), + win_dm(set::diff(geom::shift(win, up), win)), + q_fp(win_fp, p), q_fm(win_fm, p), + q_bp(win_bp, p), q_bm(win_bm, p), + q_dp(win_dp, p), q_dm(win_dm, p) + { + } + + // parts + + void init() + { + min.init(); + mln_qiter(W) q(win, p); + for_all(q) if (input.has(q)) + min.take(input(q)); + } + + void down() + { + for_all(q_dm) if (input.has(q_dm)) + min.untake(input(q_dm)); + for_all(q_dp) if (input.has(q_dp)) + min.take(input(q_dp)); + output(p) = min.to_value(); + } + + void fwd() + { + for_all(q_fm) if (input.has(q_fm)) + min.untake(input(q_fm)); + for_all(q_fp) if (input.has(q_fp)) + min.take(input(q_fp)); + output(p) = min.to_value(); + } + + void bkd() + { + for_all(q_bm) if (input.has(q_bm)) + min.untake(input(q_bm)); + for_all(q_bp) if (input.has(q_bp)) + min.take(input(q_bp)); + output(p) = min.to_value(); + } + + }; // end of erosion_fast_t + + + template <typename I, typename W, typename O> + void erosion_fast_(const Image<I>& input, const Window<W>& win, O& output) + { + // FIXME: resize border! + erosion_fast_t<I,W,O> f(exact(input), exact(win), output); + canvas::browsing::snake_fwd(f); + } + + } // end of namespace mln::morpho::impl + + + // Facades. + + template <typename I, typename W, typename O> + void erosion_fast(const Image<I>& input, const Window<W>& win, + Image<O>& output) + { + mln_assertion(exact(output).domain() == exact(input).domain()); + impl::erosion_fast_(exact(input), exact(win), exact(output)); + } + +# endif // ! MLN_INCLUDE_ONLY + + } // end of namespace mln::morpho + +} // end of namespace mln + + +#endif // ! MLN_MORPHO_EROSION_FAST_HH Index: trunk/milena/mln/morpho/dilation_fast.hh =================================================================== --- trunk/milena/mln/morpho/dilation_fast.hh (revision 0) +++ trunk/milena/mln/morpho/dilation_fast.hh (revision 1099) @@ -0,0 +1,188 @@ +// 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_MORPHO_DILATION_FAST_HH +# define MLN_MORPHO_DILATION_FAST_HH + +/*! \file mln/morpho/dilation_fast.hh + * + * \brief Ero filtering of an image. + * + * \todo Add Fast_Image versions. + */ + +# include <mln/core/concept/image.hh> +# include <mln/core/window.hh> +# include <mln/geom/shift.hh> +# include <mln/set/diff.hh> + +# include <mln/canvas/browsing/snake_fwd.hh> +# include <mln/accu/max_h.hh> + + +namespace mln +{ + + namespace morpho + { + + /*! Compute in \p output the dilation filter of image \p input by + * the window \p win. + * + * \param[in] input The image to be filtered. + * \param[in] win The window. + * \param[out] output The output image. + * + * \pre \p input and \p output have to be initialized. + */ + template <typename I, typename W, typename O> + void dilation_fast(const Image<I>& input, const Window<W>& win, + Image<O>& output); + + + + +# ifndef MLN_INCLUDE_ONLY + + namespace impl + { + + + // Functors. + + + template <typename I, typename W, typename O> + struct dilation_fast_t + { + typedef mln_point(I) P; + typedef mln_dpoint(I) D; + + // i/o + + const I& input; + const W& win; + O& output; + + // aux data + + accu::max_h<mln_vset(I)> max; + P p; + window<D> win_fp, win_fm, win_bp, win_bm, win_dp, win_dm; + mln_qiter(W) q_fp, q_fm, q_bp, q_bm, q_dp, q_dm; + + // ctor + + dilation_fast_t(const I& input_, const W& win_, O& output_) + : + // i/o + input(exact(input_)), + win(exact(win_)), + output(exact(output_)), + // aux data + max(input.values()), + p(), + win_fp(set::diff(win, geom::shift(win, left))), + win_fm(set::diff(geom::shift(win, left), win)), + win_bp(set::diff(win, geom::shift(win, right))), + win_bm(set::diff(geom::shift(win, right), win)), + win_dp(set::diff(win, geom::shift(win, up))), + win_dm(set::diff(geom::shift(win, up), win)), + q_fp(win_fp, p), q_fm(win_fm, p), + q_bp(win_bp, p), q_bm(win_bm, p), + q_dp(win_dp, p), q_dm(win_dm, p) + { + } + + // parts + + void init() + { + max.init(); + mln_qiter(W) q(win, p); + for_all(q) if (input.has(q)) + max.take(input(q)); + } + + void down() + { + for_all(q_dm) if (input.has(q_dm)) + max.untake(input(q_dm)); + for_all(q_dp) if (input.has(q_dp)) + max.take(input(q_dp)); + output(p) = max.to_value(); + } + + void fwd() + { + for_all(q_fm) if (input.has(q_fm)) + max.untake(input(q_fm)); + for_all(q_fp) if (input.has(q_fp)) + max.take(input(q_fp)); + output(p) = max.to_value(); + } + + void bkd() + { + for_all(q_bm) if (input.has(q_bm)) + max.untake(input(q_bm)); + for_all(q_bp) if (input.has(q_bp)) + max.take(input(q_bp)); + output(p) = max.to_value(); + } + + }; // end of dilation_fast_t + + + template <typename I, typename W, typename O> + void dilation_fast_(const Image<I>& input, const Window<W>& win, O& output) + { + // FIXME: resize border! + dilation_fast_t<I,W,O> f(exact(input), exact(win), output); + canvas::browsing::snake_fwd(f); + } + + } // end of namespace mln::level::impl + + + // Facades. + + template <typename I, typename W, typename O> + void dilation_fast(const Image<I>& input, const Window<W>& win, + Image<O>& output) + { + mln_assertion(exact(output).domain() == exact(input).domain()); + impl::dilation_fast_(exact(input), exact(win), exact(output)); + } + +# endif // ! MLN_INCLUDE_ONLY + + } // end of namespace mln::morpho + +} // end of namespace mln + + +#endif // ! MLN_MORPHO_DILATION_FAST_HH Index: trunk/milena/mln/level/ero.hh (deleted) =================================================================== Index: trunk/milena/mln/accu/max_h.hh =================================================================== --- trunk/milena/mln/accu/max_h.hh (revision 0) +++ trunk/milena/mln/accu/max_h.hh (revision 1099) @@ -0,0 +1,241 @@ +// 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_ACCU_MAX_H_HH +# define MLN_ACCU_MAX_H_HH + +/*! \file mln/accu/max_h.hh + * + * \brief Define a generic max accumulator class based on histogram. + */ + +# include <mln/core/concept/accumulator.hh> +# include <mln/accu/histo.hh> + + +namespace mln +{ + + namespace accu + { + + + /*! Generic max function based on histogram over a value set with + * type \c S. + */ + template <typename S> + struct max_h : public Accumulator< max_h<S> > + { + typedef mln_value(S) value; + + max_h(const Value_Set<S>& s); + max_h(); + + void init(); + void take(const value& v); + void take_as_init(const value& v); + void take(const max_h<S>& other); + void untake(const value& v); + + unsigned card() const { return h_.sum(); } + + value to_value() const; + + const accu::histo<S>& histo() const; + + protected: + + mutable accu::histo<S> h_; + const S& s_; // derived from h_ + + mutable std::size_t sum_; + mutable bool valid_; + mutable std::size_t i_; // the max index + mutable value v_; // the max value + + // Auxiliary methods + void update_() const; + void go_minus_() const; + void go_plus_() const; + }; + + +# ifndef MLN_INCLUDE_ONLY + + template <typename S> + max_h<S>::max_h(const Value_Set<S>& s) + : h_(s), + s_(h_.vset()) + { + init(); + } + + template <typename S> + max_h<S>::max_h() + : h_(), + s_(h_.vset()) + { + init(); + } + + template <typename S> + void + max_h<S>::take(const value& v) + { + h_.take(v); + if (h_.sum() == 1) + { + this->take_as_init(v); + return; + } + if (v > v_) + { + ++sum_; + valid_ = false; + } + } + + template <typename S> + void + max_h<S>::take(const max_h<S>& other) + { + // h_ + h_.take(other.h_); + for (unsigned i = this->card() - 1; i > i_; --i) + sum_ += other.h_[i]; + valid_ = false; + // FIXME: Optimize. + } + + template <typename S> + void + max_h<S>::untake(const value& v) + { + mln_precondition(h_(v) != 0); + h_.untake(v); + if (h_.sum() == 0) + { + init(); + return; + } + if (v > v_) + { + mln_invariant(sum_ >= 1); + --sum_; + valid_ = false; + } + else + if (v == v_ && h_[i_] == 0) + valid_ = false; + } + + template <typename S> + void + max_h<S>::update_() const + { + if (sum_ != 0) + go_plus_(); + else + if (h_[i_] == 0) + go_minus_(); + valid_ = true; + } + + template <typename S> + void + max_h<S>::go_minus_() const + { + do + --i_; + while (h_[i_] == 0); + } + + template <typename S> + void + max_h<S>::go_plus_() const + { + do + { + ++i_; + if (h_[i_] != 0) + sum_ -= h_[i_]; + } while (sum_ != 0); + v_ = s_[i_]; + } + + template <typename S> + void + max_h<S>::init() + { + h_.init(); + sum_ = 0; + i_ = mln_min(value); + v_ = s_[i_]; + valid_ = true; + } + + template <typename S> + void + max_h<S>::take_as_init(const value& v) + { + h_.take(v); + sum_ = 0; + i_ = s_.index_of(v); + v_ = v; + valid_ = true; + } + + template <typename S> + typename max_h<S>::value + max_h<S>::to_value() const + { + if (! valid_) + update_(); + return v_; + } + + template <typename S> + const accu::histo<S>& + max_h<S>::histo() const + { + return h_; + } + + template <typename S> + std::ostream& operator<<(std::ostream& ostr, const max_h<S>& m) + { + return ostr << m.to_value(); + } + +# endif // ! MLN_INCLUDE_ONLY + + } // end of namespace mln::accu + +} // end of namespace mln + + +#endif // ! MLN_ACCU_MAX_H_HH