[Olena-patches] 1095: Add fast histogram-based erosion and color skeleton.

https://svn.lrde.epita.fr/svn/oln/trunk/milena Index: ChangeLog from Thierry Geraud &lt;thierry.geraud(a)lrde.epita.fr&gt; Add fast histogram-based erosion and color skeleton. * tests/morpho_erosion_min_h.cc: New. * tests/value_rgb8.cc: New. * mln/level/ero.hh: New; temporary, rename it! * mln/accu/min_h.hh: New. * mln/core/vec_p.hh (dpoint): New. * mln/core/window.hh (operator<<): New. * mln/value/rgb8.hh: New. * tests/morpho_erosion.cc: Update. * mln/convert/to_window.hh: Fix sig. * mln/morpho/dilation.hh: Add todo. * mln/morpho/erosion.hh: Add todo. * mln/level/approx/median.hh: Add todo. * mln/value/props.hh: Fix missing include. mln/accu/min_h.hh | 243 ++++++++++++++++++++++++++++++++++++++++++ mln/convert/to_window.hh | 4 mln/core/vec_p.hh | 3 mln/core/window.hh | 10 + mln/level/approx/median.hh | 7 + mln/level/ero.hh | 188 ++++++++++++++++++++++++++++++++ mln/morpho/dilation.hh | 5 mln/morpho/erosion.hh | 11 + mln/value/props.hh | 1 mln/value/rgb8.hh | 114 +++++++++++++++++++ tests/morpho_erosion.cc | 35 ++++-- tests/morpho_erosion_min_h.cc | 65 +++++++++++ tests/value_rgb8.cc | 46 +++++++ 13 files changed, 719 insertions(+), 13 deletions(-) Index: tests/morpho_erosion.cc --- tests/morpho_erosion.cc (revision 1094) +++ tests/morpho_erosion.cc (working copy) @@ -32,6 +32,7 @@ #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> @@ -44,6 +45,8 @@ #include <mln/pw/cst.hh> #include <mln/fun/ops.hh> +#include <mln/convert/to_vec_p.hh> +#include <mln/convert/to_window.hh> int main() @@ -62,16 +65,26 @@ io::pgm::save(out, "out.pgm"); } - { - image2d_b<bool> bin(lena.domain()), out(lena.domain()); - level::fill(bin, pw::value(lena) > pw::cst(127)); - morpho::erosion(bin, rec, out); - - image2d_b<int_u8> test(lena.domain()); - image2d_b<int_u8>::fwd_piter p(lena.domain()); - for_all(p) - test(p) = out(p) ? 255 : 0; - io::pgm::save(test, "test.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()); +// level::ero(lena, win, out); +// morpho::erosion(lena, win, out); +// io::pgm::save(out, "out.pgm"); +// } + +// { +// image2d_b<bool> bin(lena.domain()), out(lena.domain()); +// level::fill(bin, pw::value(lena) > pw::cst(127)); +// morpho::erosion(bin, rec, out); + +// image2d_b<int_u8> test(lena.domain()); +// image2d_b<int_u8>::fwd_piter p(lena.domain()); +// for_all(p) +// test(p) = out(p) ? 255 : 0; +// io::pgm::save(test, "test.pgm"); +// } } Index: tests/morpho_erosion_min_h.cc --- tests/morpho_erosion_min_h.cc (revision 0) +++ tests/morpho_erosion_min_h.cc (revision 0) @@ -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/level/ero.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()); + level::ero(lena, win, out); + io::pgm::save(out, "out.pgm"); + } +} Index: tests/value_rgb8.cc --- tests/value_rgb8.cc (revision 0) +++ tests/value_rgb8.cc (revision 0) @@ -0,0 +1,46 @@ +// 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/value_rgb8.cc + * + * \brief Tests on mln::value::rgb8. + */ + +#include <mln/value/rgb8.hh> + + + +int main() +{ + using namespace mln; + using value::rgb8; + + { + rgb8 c; + // todo matthieu + } +} Index: mln/convert/to_window.hh --- mln/convert/to_window.hh (revision 1094) +++ mln/convert/to_window.hh (working copy) @@ -58,7 +58,7 @@ window<mln_dpoint(I)> to_window(const Image<I>& ima); /// Convert a point set \p pset into a window. - template <typename S, typename F> + template <typename S> window<mln_dpoint(S)> to_window(const Point_Set<S>& pset); /// Convert an std::set \p s of delta-points into a window. @@ -97,7 +97,7 @@ return win; } - template <typename S, typename F> + template <typename S> window<mln_dpoint(S)> to_window(const Point_Set<S>& pset) { return to_window(pw::cst(true) | pset); Index: mln/core/window.hh --- mln/core/window.hh (revision 1094) +++ mln/core/window.hh (working copy) @@ -97,6 +97,16 @@ }; + // FIXME: Move code at EOF + doc. + template <typename D> + std::ostream& operator<<(std::ostream& ostr, const window<D>& win) + { + // FIXME + for (unsigned i = 0; i < win.ndpoints(); ++i) + ostr << win.dp(i); + return ostr; + } + # ifndef MLN_INCLUDE_ONLY Index: mln/core/vec_p.hh --- mln/core/vec_p.hh (revision 1094) +++ mln/core/vec_p.hh (working copy) @@ -64,6 +64,9 @@ /// Point associated type. typedef P point; + /// Dpoint associated type. + typedef mln_dpoint(P) dpoint; + /// Point_Site associated type. typedef P psite; Index: mln/morpho/dilation.hh --- mln/morpho/dilation.hh (revision 1094) +++ mln/morpho/dilation.hh (working copy) @@ -38,6 +38,11 @@ # include <mln/morpho/includes.hh> + +// todo simon +// this file should be like erosion + + namespace mln { Index: mln/morpho/erosion.hh --- mln/morpho/erosion.hh (revision 1094) +++ mln/morpho/erosion.hh (working copy) @@ -148,6 +148,17 @@ # endif // MLN_CORE_WIN_RECTANGLE2D_HH + +// ifdef MLN_CORE_WIN_RECTANGLE2D_HH + +// template <typename I, typename O> +// void erosion_wrt_win(const Image<I>& input, const win::octagon2d& win, Image<O>& output) +// { +// todo simon +// } + +// endif MLN_CORE_WIN_RECTANGLE2D_HH + // ^ // | // end of stage1 (dispatch w.r.t. the window type) Index: mln/level/ero.hh --- mln/level/ero.hh (revision 0) +++ mln/level/ero.hh (revision 0) @@ -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_LEVEL_ERO_HH +# define MLN_LEVEL_ERO_HH + +/*! \file mln/level/ero.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 level + { + + /*! 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 ero(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 ero_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 + + ero_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 ero_t + + + template <typename I, typename W, typename O> + void ero_(const Image<I>& input, const Window<W>& win, O& output) + { + // FIXME: resize border! + ero_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 ero(const Image<I>& input, const Window<W>& win, + Image<O>& output) + { + mln_assertion(exact(output).domain() = exact(input).domain()); + impl::ero_(exact(input), exact(win), exact(output)); + } + +# endif // ! MLN_INCLUDE_ONLY + + } // end of namespace mln::level + +} // end of namespace mln + + +#endif // ! MLN_LEVEL_ERO_HH Index: mln/level/approx/median.hh --- mln/level/approx/median.hh (revision 1094) +++ mln/level/approx/median.hh (working copy) @@ -78,6 +78,13 @@ level::median(tmp, win::vline2d(win.height()), output); } +// template <typename I, typename O> +// void median(const Image<I>& input_, const win::disk2d& win, +// Image<O>& output_) +// { +// // todo simon +// } + # endif // ! MLN_INCLUDE_ONLY } // end of namespace mln::level::approx Index: mln/accu/min_h.hh --- mln/accu/min_h.hh (revision 0) +++ mln/accu/min_h.hh (revision 0) @@ -0,0 +1,243 @@ +// 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_MIN_H_HH +# define MLN_ACCU_MIN_H_HH + +/*! \file mln/accu/min_h.hh + * + * \brief Define a generic min accumulator class based on histogram. + */ + +# include <mln/core/concept/accumulator.hh> +# include <mln/accu/histo.hh> + + +namespace mln +{ + + namespace accu + { + + + /*! Generic min function based on histogram over a value set with + * type \c S. + */ + template <typename S> + struct min_h : public Accumulator< min_h<S> > + { + typedef mln_value(S) value; + + min_h(const Value_Set<S>& s); + min_h(); + + void init(); + void take(const value& v); + void take_as_init(const value& v); + void take(const min_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 min index + mutable value v_; // the min value + + // Auxiliary methods + void update_() const; + void go_minus_() const; + void go_plus_() const; + }; + + +# ifndef MLN_INCLUDE_ONLY + + template <typename S> + min_h<S>::min_h(const Value_Set<S>& s) + : h_(s), + s_(h_.vset()) + { + init(); + } + + template <typename S> + min_h<S>::min_h() + : h_(), + s_(h_.vset()) + { + init(); + } + + template <typename S> + void + min_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 + min_h<S>::take(const min_h<S>& other) + { + // h_ + h_.take(other.h_); + for (unsigned i = 0; i < i_; ++i) + sum_ += other.h_[i]; + valid_ = false; + // FIXME: Optimize. + } + + template <typename S> + void + min_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 + min_h<S>::update_() const + { + if (sum_ != 0) + go_minus_(); + else + if (h_[i_] = 0) + go_plus_(); + valid_ = true; + } + + template <typename S> + void + min_h<S>::go_minus_() const + { + do + { + --i_; + if (h_[i_] != 0) + sum_ -= h_[i_]; + } + while (sum_ != 0); + v_ = s_[i_]; + } + + template <typename S> + void + min_h<S>::go_plus_() const + { + do + ++i_; + while (h_[i_] = 0); + v_ = s_[i_]; + } + + template <typename S> + void + min_h<S>::init() + { + h_.init(); + sum_ = 0; + i_ = mln_max(value); + v_ = s_[i_]; + valid_ = true; + } + + template <typename S> + void + min_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 min_h<S>::value + min_h<S>::to_value() const + { + if (! valid_) + update_(); + return v_; + } + + template <typename S> + const accu::histo<S>& + min_h<S>::histo() const + { + return h_; + } + + template <typename S> + std::ostream& operator<<(std::ostream& ostr, const min_h<S>& m) + { + return ostr << m.to_value(); + } + +# endif // ! MLN_INCLUDE_ONLY + + } // end of namespace mln::accu + +} // end of namespace mln + + +#endif // ! MLN_ACCU_MIN_H_HH Index: mln/value/rgb8.hh --- mln/value/rgb8.hh (revision 0) +++ mln/value/rgb8.hh (revision 0) @@ -0,0 +1,114 @@ +// 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_VALUE_RGB8_HH +# define MLN_VALUE_RGB8_HH + +/*! \file mln/value/rgb8.hh + * + * \brief Color class for red-green-blue where every component is + * 8-bit encoded. + */ + +# include <mln/core/concept/value.hh> +# include <mln/value/int_u8.hh> + + +namespace mln +{ + + namespace value + { + + + typedef int_u8 int_u8_x3_t[3]; + typedef unsigned char uchar_x3_t[3]; + typedef float float_x3_t[3]; + + + /*! \brief Color class for red-green-blue where every component is + * 8-bit encoded. + */ + class rgb8 : public Value< rgb8 > + { + public: + + /// Encoding associated type. + typedef int_u8_x3_t enc; + + /// Equivalent associated type. + typedef int_u8_x3_t equiv; + + int_u8 red() const { return c_[0]; } + int_u8& red() { return c_[0]; } + + int_u8 green() const { return c_[1]; } + int_u8& green() { return c_[1]; } + + int_u8 blue() const { return c_[2]; } + int_u8& blue() { return c_[2]; } + + // todo matthieu + + private: + int_u8_x3_t c_; + }; + + + struct props< rgb8 > + { + static const unsigned nbits = 24; + static const std::size_t card_ = metal::pow<2, nbits>::value; + typedef color_kind kind; + typedef float_x3_t sum; + typedef uchar_x3_t interop; + }; + + + + /*! \brief Print an rgb8 \p c into the output stream \p ostr. + * + * \param[in,out] ostr An output stream. + * \param[in] c An rgb8. + * + * \return The modified output stream \p ostr. + */ + std::ostream& operator<<(std::ostream& ostr, const rgb8& c); + + +# ifndef MLN_INCLUDE_ONLY + + // todo matthieu + +# endif // ! MLN_INCLUDE_ONLY + + } // end of namespace mln::value + +} // end of namespace mln + + +#endif // ! MLN_VALUE_RGB8_HH Index: mln/value/props.hh --- mln/value/props.hh (revision 1094) +++ mln/value/props.hh (working copy) @@ -34,6 +34,7 @@ * FIXME : add interop typedef in each props */ +# include <cstddef> # include <climits> # include <cfloat>