[Olena-patches] cleanup-2008 2541: Add accu computation along lines and use it in erosion.

https://svn.lrde.epita.fr/svn/oln/branches/cleanup-2008/milena Index: ChangeLog from Thierry Geraud &lt;thierry.geraud(a)lrde.epita.fr&gt; Add accu computation along lines and use it in erosion. * mln/accu/line.hh: New. * tests/accu/line.cc: New. * tests/accu/Makefile.am: Update. * mln/accu/min_h.hh (min_h): New meta-class. * mln/accu/max_h.hh (max_h): New meta-class. * mln/morpho/erosion.spe.hh (erosion_line_on_function): New impl. (erosion_dispatch_wrt_win): Replace calls to the directional impl by the line impl for windows being lines. mln/accu/line.hh | 399 ++++++++++++++++++++++++++++++++++++++++++++++ mln/accu/max_h.hh | 24 ++ mln/accu/min_h.hh | 24 ++ mln/morpho/erosion.spe.hh | 58 ++++++ tests/accu/Makefile.am | 2 tests/accu/line.cc | 58 ++++++ 6 files changed, 562 insertions(+), 3 deletions(-) Index: tests/accu/Makefile.am --- tests/accu/Makefile.am (revision 2540) +++ tests/accu/Makefile.am (working copy) @@ -8,6 +8,7 @@ compute \ count \ histo \ + line \ max \ max_h \ mean \ @@ -25,6 +26,7 @@ compute_SOURCES = compute.cc count_SOURCES = count.cc histo_SOURCES = histo.cc +line_SOURCES = line.cc max_SOURCES = max.cc max_h_SOURCES = max_h.cc mean_SOURCES = mean.cc Index: tests/accu/line.cc --- tests/accu/line.cc (revision 0) +++ tests/accu/line.cc (revision 0) @@ -0,0 +1,58 @@ +// Copyright (C) 2008 EPITA Research and Development Laboratory (LRDE) +// +// 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/accu/line.cc + * + * \brief Tests on mln::accu::line. + */ + +#include <mln/accu/line.hh> +#include <mln/accu/min_h.hh> + +#include <mln/core/image/image2d.hh> +#include <mln/level/compare.hh> +#include <mln/debug/iota.hh> + + + +int main() +{ + using namespace mln; + using namespace mln::value; + + typedef image2d<unsigned char> I; + I ima(1, 5); + debug::iota(ima); + + I out(ima.domain()); + point2d p_start(0, 0); + accu::line< accu::meta::min_h, 1 >(ima, + p_start, ima.ncols(), + 0, // half_length + out); + mln_assertion(out == ima); +} Index: mln/accu/line.hh --- mln/accu/line.hh (revision 0) +++ mln/accu/line.hh (revision 0) @@ -0,0 +1,399 @@ +// Copyright (C) 2007, 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. + +#ifndef MLN_ACCU_LINE_HH +# define MLN_ACCU_LINE_HH + +/// \file mln/accu/line.hh +/// Run an accumulator on a line of images. +/// +/// \todo Suppress integer manipulations (redundant with ptr arith). + +# include <mln/core/concept/meta_accumulator.hh> +# include <mln/core/concept/image.hh> + + + +namespace mln +{ + + namespace accu + { + + // FIXME: + + /*! Line an accumulator onto the pixel values of the image \p input. + * + * \param[in] input The input image. + * \param[in] a The accumulator. + * \return The accumulator result. + * + * This routine runs: \n + * tmp = \p a \n + * tmp.init() \n + * accu::take(\p input, tmp) \n + * return tmp.to_result() \n + */ + + template <typename Meta_Accu, unsigned Dir, // Free parameters. + typename I, typename O> + void + line(const Image<I>& input, + const mln_site(I)& p_start, unsigned len, + unsigned half_length, + Image<O>& output); + + + +# ifndef MLN_INCLUDE_ONLY + + namespace internal + { + + template <typename Meta_Accu, unsigned Dir, // Free parameters. + typename I, typename O> + void + line_tests(const Image<I>& input_, + const mln_site(I)& p_start, unsigned len, + unsigned half_length, + Image<O>& output_) + { + mlc_is_a(Meta_Accu, Meta_Accumulator)::check(); + + typedef mln_accu_with(Meta_Accu, mln_value(I)) A; + mlc_converts_to(mln_result(A), mln_value(O))::check(); + + typedef mln_site(I) P; + mlc_bool(Dir < P::dim)::check(); + + mlc_is(mln_trait_image_value_io(O), + mln::trait::image::value_io::read_write)::check(); + + const I& input = exact(input_); + O& output = exact(output_); + mln_precondition(input.has_data()); + mln_precondition(output.has_data()); + } + + } // end of namespace mln::accu::internal + + + namespace impl + { + + namespace generic + { + + template <typename Meta_Accu, unsigned Dir, + typename I, typename O> + void + line(const Image<I>& input_, + const mln_site(I)& p_start, unsigned len, + unsigned half_length, + Image<O>& output_) + { + typedef mln_site(I) P; + typedef mln_accu_with(Meta_Accu, mln_value(I)) A; + + const I& input = exact(input_); + O& output = exact(output_); + + // Checks and tests. + internal::line_tests<Meta_Accu, Dir>(input, + p_start, len, + half_length, + output); + + // Initialization. + const def::coord start = p_start[Dir]; + const def::coord last = start + len - 1; + A a; // Accumulator. + a.init(); + P p; // Current point. + + // Start (first line point). + p = p_start; + P q = p; + for (def::coord c = 0; c <= half_length && c < len; ++c) + { + a.take(input(q)); + ++q[Dir]; + } + output(p) = a; + + def::coord& cur = p[Dir]; + if (cur == last) + return; + + // Begin of line. + + P p_plus = p_start; + def::coord& plus = p_plus[Dir]; + plus += half_length; + + while (cur < start + half_length && cur < last) + { + ++cur; + ++plus; + if (plus <= last) + a.take(input(p_plus)); + output(p) = a; + } + + if (cur == last) + return; + + // Middle of line. + + P p_minus = p_start; + def::coord& minus = p_minus[Dir]; + --minus; + + while (cur < last - half_length) + { + ++cur; + ++plus; + ++minus; + mln_invariant(plus >= start && plus <= last); + a.take(input(p_plus)); + mln_invariant(minus >= start && minus <= last); + a.untake(input(p_minus)); + output(p) = a; + } + + if (cur == last) + return; + + // End of line. + + while (cur < last) + { + ++cur; + ++minus; + mln_invariant(minus >= start && minus <= last); + a.untake(input(p_minus)); + output(p) = a; + } + } + + } // end of namespace mln::accu::impl::generic + + + + template <typename Meta_Accu, unsigned Dir, + typename I, typename O> + void + line_fastest(const Image<I>& input_, + const mln_site(I)& p_start, unsigned len, + unsigned half_length, + Image<O>& output_) + { + typedef mln_site(I) P; + typedef mln_value(I) V; + typedef mln_accu_with(Meta_Accu, V) A; + + const I& input = exact(input_); + O& output = exact(output_); + + // Checks and tests. + internal::line_tests<Meta_Accu, Dir>(input, + p_start, len, + half_length, + output); + + // Initialization. + + const def::coord start = p_start[Dir]; + const def::coord last = start + len - 1; + + const V* p_in = & input(p_start); + V* p_out = & output(p_start); + + mln_delta(P) dp = literal::zero; + dp[Dir] = 1; + unsigned offset = input.delta_index(dp); + + A a; // Accumulator. + a.init(); + + // Start (first line point). + + const V* q = p_in; + for (def::coord c = 0; c <= half_length && c < len; ++c) + { + a.take(*q); + q += offset; + } + *p_out = a; + + def::coord cur = p_start[Dir]; + if (cur == last) + return; + + // Begin of line. + + def::coord plus = start + half_length; + const V* p_plus = p_in + half_length * offset; + + while (cur < start + half_length && cur < last) + { + ++cur; + p_in += offset; + ++plus; + p_plus += offset; + if (plus <= last) + a.take(*p_plus); + p_out += offset; + *p_out = a; + } + + if (cur == last) + return; + + // Middle of line. + + def::coord minus = start - 1; + const V* p_minus = p_in - offset; + + while (cur < last - half_length) + { + ++cur; + p_in += offset; + ++plus; + p_plus += offset; + ++minus; + p_minus += offset; + mln_invariant(plus >= start && plus <= last); + a.take(*p_plus); + mln_invariant(minus >= start && minus <= last); + a.untake(*p_minus); + p_out += offset; + *p_out = a; + } + + if (cur == last) + return; + + // End of line. + + while (cur < last) + { + ++cur; + p_in += offset; + ++minus; + p_minus += offset; + mln_invariant(minus >= start && minus <= last); + a.untake(*p_minus); + p_out += offset; + *p_out = a; + } + + } + + + + + } // end of namespace mln::accu::impl + + + namespace internal + { + + template <typename Meta_Accu, unsigned Dir, // Free parameters. + typename I, typename O> + void + line_dispatch(trait::image::speed::any, + const Image<I>& input, + const mln_site(I)& p_start, unsigned len, + unsigned half_length, + Image<O>& output) + { + impl::generic::line<Meta_Accu, Dir>(input, + p_start, len, + half_length, + output); + } + +// template <typename Meta_Accu, unsigned Dir, // Free parameters. +// typename I, typename O> +// void +// line_dispatch(trait::image::speed::fastest, +// const Image<I>& input, +// const mln_site(I)& p_start, unsigned len, +// unsigned half_length, +// Image<O>& output) +// { +// impl::line_fastest<Meta_Accu, Dir>(input, +// p_start, len, +// half_length, +// output); +// } + + template <typename Meta_Accu, unsigned Dir, // Free parameters. + typename I, typename O> + void + line_dispatch(const Image<I>& input, + const mln_site(I)& p_start, unsigned len, + unsigned half_length, + Image<O>& output) + { + line_dispatch<Meta_Accu, Dir>(mln_trait_image_speed(I)(), + input, + p_start, len, + half_length, + output); + } + + } // end of namespace mln::accu::internal + + + template <typename Meta_Accu, unsigned Dir, // Free parameters. + typename I, typename O> + void + line(const Image<I>& input, + const mln_site(I)& p_start, unsigned len, + unsigned half_length, + Image<O>& output) + { + internal::line_tests<Meta_Accu, Dir>(input, + p_start, len, + half_length, + output); + internal::line_dispatch<Meta_Accu, Dir>(input, + p_start, len, + half_length, + output); + } + +# endif // ! MLN_INCLUDE_ONLY + + } // end of namespace mln::accu + +} // end of namespace mln + + +#endif // ! MLN_ACCU_LINE_HH Index: mln/accu/min_h.hh --- mln/accu/min_h.hh (revision 2540) +++ mln/accu/min_h.hh (working copy) @@ -36,6 +36,7 @@ # include <mln/accu/internal/base.hh> # include <mln/accu/histo.hh> # include <mln/value/set.hh> +# include <mln/util/pix.hh> namespace mln @@ -87,6 +88,29 @@ }; + + template <typename I> struct min_h< util::pix<I> >; + + + namespace meta + { + + /*! + * \brief Meta accumulator for min. + */ + struct min_h : public Meta_Accumulator< min_h > + { + template <typename T> + struct with + { + typedef accu::min_h<T> ret; + }; + }; + + } // end of namespace mln::meta + + + # ifndef MLN_INCLUDE_ONLY template <typename V> Index: mln/accu/max_h.hh --- mln/accu/max_h.hh (revision 2540) +++ mln/accu/max_h.hh (working copy) @@ -35,6 +35,7 @@ # include <mln/accu/internal/base.hh> # include <mln/accu/histo.hh> +# include <mln/util/pix.hh> namespace mln @@ -86,6 +87,29 @@ }; + + template <typename I> struct max_h< util::pix<I> >; + + + namespace meta + { + + /*! + * \brief Meta accumulator for max. + */ + struct max_h : public Meta_Accumulator< max_h > + { + template <typename T> + struct with + { + typedef accu::max_h<T> ret; + }; + }; + + } // end of namespace mln::meta + + + # ifndef MLN_INCLUDE_ONLY template <typename V> Index: mln/morpho/erosion.spe.hh --- mln/morpho/erosion.spe.hh (revision 2540) +++ mln/morpho/erosion.spe.hh (working copy) @@ -42,6 +42,8 @@ # include <mln/win/diff.hh> # include <mln/accu/min_h.hh> +# include <mln/accu/line.hh> + # include <mln/canvas/browsing/snake_fwd.hh> # include <mln/canvas/browsing/snake_generic.hh> # include <mln/canvas/browsing/directional.hh> @@ -220,6 +222,55 @@ } + template <typename I, typename G, unsigned Dir, typename C> + inline + mln_concrete(I) + erosion_line_on_function(const Image<I>& input_, const win::line<G,Dir,C>& win) + { + trace::entering("morpho::impl::erosion_line"); + + typedef mln_site(I) P; + enum { dim = P::dim }; + + const I& input = exact(input_); + + mln_concrete(I) output; + initialize(output, input); + + mln_psite(I) + pmin = input.domain().pmin(), + pmax = input.domain().pmax(), + p = pmin; + + const unsigned len = input.domain().len(Dir); + const unsigned win_half_length = win.length() / 2; + + do + { + accu::line< accu::meta::min_h, Dir >(input, + p, len, + win_half_length, + output); + + for (int c = dim - 1; c >= 0; --c) + { + if (c == int(Dir)) + continue; + if (p[c] != pmax[c]) + { + ++p[c]; + break; + } + p[c] = pmin[c]; + } + } + while (p != pmin); + + trace::exiting("morpho::impl::erosion_line"); + return output; + } + + template <typename I> inline mln_concrete(I) @@ -627,7 +678,6 @@ initialize(output, input); } - void init_run() { min.init(); @@ -941,7 +991,8 @@ if (win.size() <= 3) return erosion_dispatch_for_generic(input, win); else - return erosion_dispatch_for_directional(input, win, 1); + return impl::erosion_line_on_function(input, win); +// return erosion_dispatch_for_directional(input, win, 1); } template <typename I> @@ -951,7 +1002,8 @@ if (win.size() <= 3) return erosion_dispatch_for_generic(input, win); else - return erosion_dispatch_for_directional(input, win, 0); + return impl::erosion_line_on_function(input, win); +// return erosion_dispatch_for_directional(input, win, 0); }