URL: https://svn.lrde.epita.fr/svn/oln/branches/cleanup-2008/milena ChangeLog: 2008-10-08 Matthieu Garrigues <garrigues@lrde.epita.fr> Work on erosion and browsing canvas. Todo: Add a n-dimensional browsing canvas which follows diagonal directions, to accelerate erosion on diagonal lines. * mln/morpho/erosion.spe.hh: * tests/morpho/erosion.cc: More tests and benches on rectangles, hline2d, vline2d and octogone. * mln/canvas/browsing/directional.hh: Improve this canvas in order to use it in erosion, to improve performance on erosion with lines. * tests/timer.hh: New. Tool to bench tests. --- mln/canvas/browsing/directional.hh | 13 + mln/morpho/erosion.spe.hh | 380 ++++++++++++++++++++++++++++++++----- tests/morpho/erosion.cc | 179 +++++++++++++---- tests/timer.hh | 62 ++++++ 4 files changed, 542 insertions(+), 92 deletions(-) Index: branches/cleanup-2008/milena/tests/morpho/erosion.cc =================================================================== --- branches/cleanup-2008/milena/tests/morpho/erosion.cc (revision 2531) +++ branches/cleanup-2008/milena/tests/morpho/erosion.cc (revision 2532) @@ -33,25 +33,17 @@ #include <mln/core/image/image2d.hh> #include <mln/win/rectangle2d.hh> #include <mln/win/octagon2d.hh> -#include <mln/win/diag2d.hh> -#include <mln/win/backdiag2d.hh> -#include <mln/core/alias/window2d.hh> + +#include <mln/debug/iota.hh> #include <mln/io/pgm/load.hh> #include <mln/io/pgm/save.hh> #include <mln/value/int_u8.hh> -#include <mln/level/fill.hh> #include <mln/morpho/erosion.hh> -#include <mln/pw/value.hh> -#include <mln/pw/cst.hh> -#include <mln/fun/ops.hh> - -#include <mln/convert/to_p_array.hh> -#include <mln/convert/to_window.hh> - #include "tests/data.hh" +#include "tests/timer.hh" int main() @@ -76,43 +68,150 @@ // 11 29 1 // 25 66 15 + border::thickness = 20; image2d<int_u8> lena; io::pgm::load(lena, MLN_IMG_DIR "/lena.pgm"); + win::rectangle2d rec(21, 21); + win::hline2d hline(31); + win::vline2d vline(31); + win::octagon2d oct(15); + image2d<int_u8> out; + image2d<int_u8> ref; // trace::quiet = false; + timer t; + + + // Rectangle + std::cout << "-------------------------- Rectangle: " << std::endl; { - win::rectangle2d rec(L_rec, L_rec); - io::pgm::save(morpho::erosion(lena, rec), - "out1.pgm"); + t.start(); + ref = morpho::impl::generic::erosion_on_function(lena, rec); + std::cout << "generic on rectangle2d: " << t << std::endl; } { - win::octagon2d oct(L_oct); - io::pgm::save(morpho::erosion(lena, oct), - "out2.pgm"); - } - -// { -// p_array<point2d> vec = convert::to_p_array(rec, point2d::zero); -// window2d win = convert::to_window(vec); - -// image2d<int_u8> out(lena.domain()); -// level::ero(lena, win, out); -// morpho::erosion(lena, win, out); -// io::pgm::save(out, "out.pgm"); -// } - -// { -// image2d<bool> bin(lena.domain()), out(lena.domain()); -// level::fill(bin, pw::value(lena) > pw::cst(127)); -// morpho::erosion(bin, rec, out); - -// image2d<int_u8> test(lena.domain()); -// image2d<int_u8>::fwd_piter p(lena.domain()); -// for_all(p) -// test(p) = out(p) ? 255 : 0; -// io::pgm::save(test, "test.pgm"); -// } + t.start(); + out = morpho::erosion(lena, rec); + std::cout << "dispach on rectangle2d: " << t << std::endl; + bool test = out == ref; + mln_assertion(test); + std::cout << " " << (test ? "OK" : "KO!!!") << std::endl; + } + + { + t.start(); + out = morpho::impl::erosion_arbitrary_2d_fastest(lena, rec); + std::cout << "erosion_arbitrary_2d_fastest on rectangle2d: " << t << std::endl; + bool test = out == ref; + mln_assertion(test); + std::cout << " " << (test ? "OK" : "KO!!!") << std::endl; + } + + { + t.start(); + out = morpho::impl::erosion_arbitrary_2d(lena, rec); + std::cout << "erosion_arbitrary_2d on rectangle2d: " << t << std::endl; + bool test = out == ref; + mln_assertion(test); + std::cout << " " << (test ? "OK" : "KO!!!") << std::endl; + } + + //Hline + + std::cout << "-------------------------- Hline2d: " << std::endl; + + { + t.start(); + ref = morpho::impl::generic::erosion_on_function(lena, hline); + std::cout << "generic on hline2d: " << t << std::endl; + } + + { + t.start(); + out = morpho::erosion(lena, hline); + std::cout << "dispach on hline2d : " << t << std::endl; + bool test = out == ref; + mln_assertion(test); + std::cout << " " << (test ? "OK" : "KO!!!") << std::endl; + } + + { + t.start(); + out = morpho::impl::erosion_arbitrary_2d_fastest(lena, hline); + std::cout << "erosion_arbitrary_2d_fastest on hline2d: " << t << std::endl; + bool test = out == ref; + mln_assertion(test); + std::cout << " " << (test ? "OK" : "KO!!!") << std::endl; + } + + + { + t.start(); + out = morpho::impl::erosion_arbitrary_2d(lena, hline); + std::cout << "erosion_arbitrary_2d on hline2d: " << t << std::endl; + bool test = out == ref; + mln_assertion(test); + std::cout << " " << (test ? "OK" : "KO!!!") << std::endl; + } + + std::cout << "-------------------------- Vline2d: "<< std::endl; + + //Vline + { + t.start(); + ref = morpho::impl::generic::erosion_on_function(lena, vline); + std::cout << "generic on vline2d: " << t << std::endl; + } + + { + t.start(); + out = morpho::erosion(lena, vline); + std::cout << "dispach on vline2d : " << t << std::endl; + bool test = out == ref; + mln_assertion(test); + std::cout << " " << (test ? "OK" : "KO!!!") << std::endl; + } + + + { + t.start(); + out = morpho::impl::erosion_arbitrary_2d_fastest(lena, vline); + std::cout << "erosion_arbitrary_2d_fastest on vline2d: " << t << std::endl; + bool test = out == ref; + mln_assertion(test); + std::cout << " " << (test ? "OK" : "KO!!!") << std::endl; + } + + + { + t.start(); + out = morpho::impl::erosion_arbitrary_2d(lena, vline); + std::cout << "erosion_arbitrary_2d on vline2d: " << t << std::endl; + bool test = out == ref; + mln_assertion(test); + std::cout << " " << (test ? "OK" : "KO!!!") << std::endl; + } + + std::cout << "-------------------------- Octogone: " << std::endl; + + //Octogone + { + t.start(); + ref = morpho::impl::generic::erosion_on_function(lena, oct); + std::cout << "generic on octogone: " << t << std::endl; + io::pgm::save(ref, "out_oct_ref.pgm"); + } + + { + t.start(); + out = morpho::erosion(lena, oct); + std::cout << "dispach on octogone: " << t << std::endl; + bool test = out == ref; + mln_assertion(test); + std::cout << " " << (test ? "OK" : "KO!!!") << std::endl; + io::pgm::save(out, "out_oct.pgm"); + } } Index: branches/cleanup-2008/milena/tests/timer.hh =================================================================== --- branches/cleanup-2008/milena/tests/timer.hh (revision 0) +++ branches/cleanup-2008/milena/tests/timer.hh (revision 2532) @@ -0,0 +1,62 @@ +// Copyright (C) 2007, 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/morpho/erosion.cc + * + * \brief Timer to bench tests. + */ + +class timer +{ +public: + void start() + { + start_ = clock(); + } + + void stop() + { + end_ = clock(); + len = float(end_ - start_) / CLOCKS_PER_SEC; + } + + float lenght() + { + return float(clock() - start_) / CLOCKS_PER_SEC; + } + +private: + clock_t start_; + clock_t end_; + float len; +}; + + +std::ostream& operator<<(std::ostream& ostr, timer t) +{ + return ostr << t.lenght() << "s"; +} Index: branches/cleanup-2008/milena/mln/morpho/erosion.spe.hh =================================================================== --- branches/cleanup-2008/milena/mln/morpho/erosion.spe.hh (revision 2531) +++ branches/cleanup-2008/milena/mln/morpho/erosion.spe.hh (revision 2532) @@ -41,6 +41,8 @@ # include <mln/accu/min_h.hh> # include <mln/canvas/browsing/snake_fwd.hh> +# include <mln/canvas/browsing/snake_generic.hh> +# include <mln/canvas/browsing/directional.hh> /*! \file mln/morpho/erosion.spe.hh @@ -258,6 +260,10 @@ template <typename I, typename W> struct erosion_arbitrary_2d_fastest_functor { + typedef erosion_arbitrary_2d_fastest_functor<I,W> self; + typedef void (self::*move_fun)(); + typedef mln_deduce(I, psite, delta) dpsite; + const I& input; const W& win; mln_concrete(I) output; @@ -266,30 +272,50 @@ mln_psite(I) p; window2d - win_left, - win_right, + win_left_fwd, + win_right_fwd, + win_left_bkd, + win_right_bkd, win_bot, win_top; mln_qixter(const I, window2d) - q_l, - q_r, + q_l_fwd, + q_r_fwd, + q_l_bkd, + q_r_bkd, q_top, q_bot; + std::vector<move_fun> moves; + std::vector<dpsite> dps; + erosion_arbitrary_2d_fastest_functor(const I& input, const W& win) : input(input), win(win), min(), - win_left(win::shift(win, left) - win), - win_right(win - win::shift(win, left)), + win_left_fwd(win::shift(win, left) - win), + win_right_fwd(win - win::shift(win, left)), + win_left_bkd(win::shift(win_left_fwd, right)), + win_right_bkd(win::shift(win_right_fwd, right)), win_bot(win - win::shift(win, up)), win_top(win::shift(win, up) - win), - q_l(input, win_left, p), - q_r(input, win_right, p), + q_l_fwd(input, win_left_fwd, p), + q_r_fwd(input, win_right_fwd, p), + q_l_bkd(input, win_left_bkd, p), + q_r_bkd(input, win_right_bkd, p), q_top(input, win_top, p), - q_bot(input, win_bot, p) - { } + q_bot(input, win_bot, p), + moves(3), + dps(3) + { + dps[0] = dpsite(1, 0); + dps[1] = dpsite(0, 1); + dps[2] = dpsite(0, -1); + moves[0] = &self::down; + moves[1] = &self::fwd; + moves[2] = &self::bkd; + } void init() { @@ -301,31 +327,29 @@ mln_qixter(const I, W) q(input, win, p); for_all(q) min.take(q.val()); + p = input.domain().pmin(); } void fwd() { - ++p.col(); - for_all(q_l) - min.untake(q_l.val()); - for_all(q_r) - min.take(q_r.val()); + for_all(q_l_fwd) + min.untake(q_l_fwd.val()); + for_all(q_r_fwd) + min.take(q_r_fwd.val()); output(p) = min; } void bkd() { - --p.col(); - for_all(q_r) - min.untake(q_r.val()); - for_all(q_l) - min.take(q_l.val()); + for_all(q_r_bkd) + min.untake(q_r_bkd.val()); + for_all(q_l_bkd) + min.take(q_l_bkd.val()); output(p) = min; } void down() { - ++p.row(); for_all(q_top) min.untake(q_top.val()); for_all(q_bot) @@ -344,7 +368,7 @@ typedef erosion_arbitrary_2d_fastest_functor<I, W> F; F f(exact(input), exact(win)); - canvas::browsing::snake_fwd(f); + canvas::browsing::snake_generic(f); trace::exiting("morpho::impl:erosion_arbitrary_2d_fastest"); @@ -355,6 +379,10 @@ template <typename I, typename W> struct erosion_arbitrary_2d_functor { + typedef erosion_arbitrary_2d_functor<I,W> self; + typedef void (self::*move_fun)(); + typedef mln_deduce(I, psite, delta) dpsite; + const I& input; const W& win; mln_concrete(I) output; @@ -363,30 +391,50 @@ mln_psite(I) p; window2d - win_left, - win_right, + win_left_fwd, + win_right_fwd, + win_left_bkd, + win_right_bkd, win_bot, win_top; mln_qiter(window2d) - q_l, - q_r, + q_l_fwd, + q_r_fwd, + q_l_bkd, + q_r_bkd, q_top, q_bot; + std::vector<move_fun> moves; + std::vector<dpsite> dps; + erosion_arbitrary_2d_functor(const I& input, const W& win) : input(input), win(win), min(), - win_left(win::shift(win, left) - win), - win_right(win - win::shift(win, left)), + win_left_fwd(win::shift(win, left) - win), + win_right_fwd(win - win::shift(win, left)), + win_left_bkd(win::shift(win_left_fwd, right)), + win_right_bkd(win::shift(win_right_fwd, right)), win_bot(win - win::shift(win, up)), win_top(win::shift(win, up) - win), - q_l(win_left, p), - q_r(win_right, p), + q_l_fwd(win_left_fwd, p), + q_r_fwd(win_right_fwd, p), + q_l_bkd(win_left_bkd, p), + q_r_bkd(win_right_bkd, p), q_top(win_top, p), - q_bot(win_bot, p) - { } + q_bot(win_bot, p), + moves(3), + dps(3) + { + dps[0] = dpsite(1, 0); + dps[1] = dpsite(0, 1); + dps[2] = dpsite(0, -1); + moves[0] = &self::down; + moves[1] = &self::fwd; + moves[2] = &self::bkd; + } void init() { @@ -398,31 +446,29 @@ mln_qiter(W) q(win, p); for_all(q) min.take(input(q)); + p = input.domain().pmin(); } void fwd() { - ++p.col(); - for_all(q_l) - min.untake(input(q_l)); - for_all(q_r) - min.take(input(q_r)); + for_all(q_l_fwd) + min.untake(input(q_l_fwd)); + for_all(q_r_fwd) + min.take(input(q_r_fwd)); output(p) = min; } void bkd() { - --p.col(); - for_all(q_r) - min.untake(input(q_r)); - for_all(q_l) - min.take(input(q_l)); + for_all(q_r_bkd) + min.untake(input(q_r_bkd)); + for_all(q_l_bkd) + min.take(input(q_l_bkd)); output(p) = min; } void down() { - ++p.row(); for_all(q_top) min.untake(input(q_top)); for_all(q_bot) @@ -441,13 +487,192 @@ typedef erosion_arbitrary_2d_functor<I, W> F; F f(exact(input), exact(win)); - canvas::browsing::snake_fwd(f); + canvas::browsing::snake_generic(f); trace::exiting("morpho::impl:erosion_arbitrary_2d"); return f.output; } + + template <typename Dp> + Dp dp_directional(int dir) + { + Dp dp = literal::zero; + dp[dir] = 1; + return dp; + } + + template <typename I_, typename W> + struct erosion_directional_nd_functor + { + typedef I_ I; + typedef mln_deduce(I, psite, delta) dpsite; + + const I& input; + const W& win; + mln_concrete(I) output; + accu::min_h<mln_value(I)> min; + enum { dim = I::site::dim }; + + mln_psite(I) p; + unsigned dir; + + window2d + win_left, + win_right; + + mln_qiter(window2d) + q_l, + q_r; + + erosion_directional_nd_functor(const I& input, const W& win, int dir) + : input(input), + win(win), + min(), + dir(dir), + win_left(win::shift(win, -dp_directional<dpsite>(dir)) - win), + win_right(win - win::shift(win, -dp_directional<dpsite>(dir))), + q_l(win_left, p), + q_r(win_right, p) + { + + } + + void init() + { + // FIXME: border::adjust(input, win.delta()); + extension::fill(input, mln_max(mln_value(I))); + initialize(output, input); + } + + + void init_run() + { + min.init(); + p[dir]--; + mln_qiter(W) q(win, p); + for_all(q) + min.take(input(q)); + p[dir]++; + } + + void next() + { + for_all(q_l) + min.untake(input(q_l)); + for_all(q_r) + min.take(input(q_r)); + output(p) = min; + } + + void final() + { + } + + }; + + template <typename I, typename W> + inline + mln_concrete(I) + erosion_directional_nd(const Image<I>& input, const Window<W>& win, unsigned dir) + { + trace::entering("morpho::impl:erosion_directional_nd"); + + typedef erosion_directional_nd_functor<I, W> F; + F f(exact(input), exact(win), dir); + canvas::browsing::directional(f); + + trace::exiting("morpho::impl:erosion_directional_nd"); + + return f.output; + } + + + template <typename I_, typename W> + struct erosion_directional_nd_fastest_functor + { + typedef I_ I; + typedef mln_deduce(I, psite, delta) dpsite; + + const I& input; + const W& win; + mln_concrete(I) output; + accu::min_h<mln_value(I)> min; + + mln_psite(I) p; + enum { dim = I::site::dim }; + unsigned dir; + + window2d + win_left, + win_right; + + mln_qixter(const I, window2d) + q_l, + q_r; + + erosion_directional_nd_fastest_functor(const I& input, const W& win, unsigned dir) + : input(input), + win(win), + min(), + dir(dir), + win_left(win::shift(win, -dp_directional<dpsite>(dir)) - win), + win_right(win - win::shift(win, -dp_directional<dpsite>(dir))), + q_l(input, win_left, p), + q_r(input, win_right, p) + { + } + + void init() + { + // FIXME: border::adjust(input, win.delta()); + extension::fill(input, mln_max(mln_value(I))); + initialize(output, input); + } + + void next() + { + for_all(q_l) + min.untake(q_l.val()); + for_all(q_r) + min.take(q_r.val()); + output(p) = min; + } + + + void init_run() + { + min.init(); + p[dir]--; + mln_qixter(const I, W) q(input, win, p); + for_all(q) + min.take(q.val()); + p[dir]++; + } + + void final() + { + } + + }; + + template <typename I, typename W> + inline + mln_concrete(I) + erosion_directional_nd_fastest(const Image<I>& input, const Window<W>& win, unsigned dir) + { + trace::entering("morpho::impl:erosion_directional_nd_fastest"); + + typedef erosion_directional_nd_fastest_functor<I, W> F; + F f(exact(input), exact(win), dir); + canvas::browsing::directional(f); + + trace::exiting("morpho::impl:erosion_directional_nd_fastest"); + + return f.output; + } + } // end of namespace mln::morpho::impl @@ -505,9 +730,11 @@ mln_concrete(I) erosion_dispatch_for_generic(const I& input, const W& win) // Entry point. { + trace::entering("morpho::erosion_dispatch_for_generic"); return erosion_dispatch_for_generic(mln_trait_image_kind(I)(), mln_trait_image_speed(I)(), input, win); + trace::entering("morpho::erosion_dispatch_for_generic"); } @@ -518,7 +745,7 @@ erosion_chooses_arbitrary(const I& input, const W& win) { return - win.size() >= 25 // size is not too small + win.size() >= 10 // size is not too small && // 2d case only mlc_equal(mln_trait_image_dimension(I), @@ -553,8 +780,40 @@ mln_concrete(I) erosion_dispatch_for_arbitrary(const I& input, const W& win) { + trace::entering("morpho::erosion_dispatch_for_arbitrary"); return erosion_dispatch_for_arbitrary(mln_trait_image_speed(I)(), input, win); + trace::exiting("morpho::erosion_dispatch_for_arbitrary"); + } + + + + // dispatch for directional_nd w.r.t. speed + + template <typename I, typename W> + mln_concrete(I) + erosion_dispatch_for_directional(trait::image::speed::fastest, + const I& input, const W& win, unsigned dir) + { + return impl::erosion_directional_nd_fastest(input, win, dir); + } + + template <typename I, typename W> + mln_concrete(I) + erosion_dispatch_for_directional(trait::image::speed::any, + const I& input, const W& win, unsigned dir) + { + return impl::erosion_directional_nd(input, win, dir); + } + + template <typename I, typename W> + mln_concrete(I) + erosion_dispatch_for_directional(const I& input, const W& win, unsigned dir) + { + trace::entering("morpho::erosion_dispatch_for_directional"); + return erosion_dispatch_for_directional(mln_trait_image_speed(I)(), + input, win, dir); + trace::exiting("morpho::erosion_dispatch_for_directional"); } // dispatch w.r.t. win @@ -567,9 +826,9 @@ // win::shift does not work. We have to introduce // props from windows, then re-write win::shift. -// if (erosion_chooses_arbitrary(input, win)) -// return erosion_dispatch_for_arbitrary(input, win); -// else + if (erosion_chooses_arbitrary(input, win)) + return erosion_dispatch_for_arbitrary(input, win); + else return erosion_dispatch_for_generic(input, win); } @@ -587,13 +846,34 @@ mln_concrete(I) erosion_dispatch_wrt_win(const I& input, const win::octagon2d& win) { - if (win.size() <= 9) // FIXME: Hard-coded! - return erosion_dispatch_for_generic(input, win); + if (win.length() < 5) + return erosion_dispatch_for_arbitrary(input, win); else return impl::erosion_octagon2d(input, win); } + template <typename I> + mln_concrete(I) + erosion_dispatch_wrt_win(const I& input, const win::hline2d& win) + { + if (win.size() <= 3) + return erosion_dispatch_for_generic(input, win); + else + return erosion_dispatch_for_directional(input, win, 1); + } + + template <typename I> + mln_concrete(I) + erosion_dispatch_wrt_win(const I& input, const win::vline2d& win) + { + if (win.size() <= 3) + return erosion_dispatch_for_generic(input, win); + else + return erosion_dispatch_for_directional(input, win, 0); + } + + // The dispatch entry point. template <typename I, typename W> Index: branches/cleanup-2008/milena/mln/canvas/browsing/directional.hh =================================================================== --- branches/cleanup-2008/milena/mln/canvas/browsing/directional.hh (revision 2531) +++ branches/cleanup-2008/milena/mln/canvas/browsing/directional.hh (revision 2532) @@ -121,10 +121,18 @@ do { - trace::entering("canvas::browsing::directional::next"); + + // Browse the run + f.init_run(); + while (f.p[f.dir] <= pmax[f.dir]) + { f.next(); - trace::exiting("canvas::browsing::directional::next"); + ++f.p[f.dir]; + } + f.p[f.dir] = pmin[f.dir]; + + // Select the next run start for (int c = F::dim - 1; c >= 0; --c) { if (c == int(f.dir)) @@ -136,6 +144,7 @@ } f.p[c] = pmin[c]; } + } while (f.p != pmin); trace::entering("canvas::browsing::directional::final");