[Olena-patches] 3321: Optimize the video labeling canvas.

https://svn.lrde.epita.fr/svn/oln/trunk/milena Index: ChangeLog from Thierry Geraud &lt;thierry.geraud(a)lrde.epita.fr&gt; Optimize the video labeling canvas. * mln/core/concept/neighborhood.hh (negative_offsets_wrt): New. * mln/core/concept/window.hh: Likewise. * mln/canvas/labeling.hh (labeling): Strenghten 's' type. Use negative_offsets_wrt. * mln/labeling/flat_zones.hh (flat_zones_functor): Remove useless typedef S. Fix ctor. (flat_zones): Fix. * tests/labeling/flat_zones.cc: Upgrade file doc style. Add commented bench. Add consistency test wrt both implementations. mln/canvas/labeling.hh | 48 +++++++++++++++++++++------------------ mln/core/concept/neighborhood.hh | 18 ++++++++++++++ mln/core/concept/window.hh | 30 ++++++++++++++++++++++++ mln/labeling/flat_zones.hh | 16 ++++--------- tests/labeling/flat_zones.cc | 47 ++++++++++++++++++++++++++++++++++---- 5 files changed, 122 insertions(+), 37 deletions(-) Index: mln/core/concept/neighborhood.hh --- mln/core/concept/neighborhood.hh (revision 3320) +++ mln/core/concept/neighborhood.hh (working copy) @@ -102,6 +102,10 @@ util::array<int> offsets_wrt(const Image<I>& ima, const Neighborhood<N>& nbh); + template <typename I, typename N> + util::array<int> + negative_offsets_wrt(const Image<I>& ima, const Neighborhood<N>& nbh); + # ifndef MLN_INCLUDE_ONLY @@ -160,6 +164,20 @@ return offsets_wrt(ima, nbh.win()); } + template <typename I, typename N> + util::array<int> + negative_offsets_wrt(const Image<I>& ima_, const Neighborhood<N>& nbh_) + { + mln_is_simple_neighborhood(N)::check(); + + const I& ima = exact(ima_); + const N& nbh = exact(nbh_); + mln_precondition(ima.is_valid()); + mln_precondition(nbh.is_valid()); + + return negative_offsets_wrt(ima, nbh.win()); + } + # endif // ! MLN_INCLUDE_ONLY } // end of namespace mln Index: mln/core/concept/window.hh --- mln/core/concept/window.hh (revision 3320) +++ mln/core/concept/window.hh (working copy) @@ -119,6 +119,10 @@ util::array<int> offsets_wrt(const Image<I>& ima, const Window<W>& win); + template <typename I, typename W> + util::array<int> + negative_offsets_wrt(const Image<I>& ima, const Window<W>& win); + namespace convert @@ -339,6 +343,32 @@ } + template <typename I, typename W> + inline + util::array<int> + negative_offsets_wrt(const Image<I>& ima_, const Window<W>& win_) + { + mln_is_simple_window(W)::check(); + + const I& ima = exact(ima_); + const W& win = exact(win_); + mln_precondition(ima.is_valid()); + mln_precondition(win.is_valid()); + + util::array<int> arr; + unsigned n = win.size(); + + for (unsigned i = 0; i < n; ++i) + { + int offset = ima.delta_index(win.dp(i)); + if (offset < 0) + arr.append(offset); + } + + return arr; + } + + namespace convert { Index: mln/canvas/labeling.hh --- mln/canvas/labeling.hh (revision 3320) +++ mln/canvas/labeling.hh (working copy) @@ -119,7 +119,7 @@ typename S, typename F> mln_ch_value(I, L) labeling(const Image<I>& input_, const Neighborhood<N>& nbh_, L& nlabels, - const S& s, F& f) + const Site_Set<S>& s_, F& f) { trace::entering("canvas::impl::generic::labeling"); @@ -127,6 +127,7 @@ const I& input = exact(input_); const N& nbh = exact(nbh_); + const S& s = exact(s_); // Local type. typedef mln_psite(I) P; @@ -254,7 +255,7 @@ // Initialization. { initialize(deja_vu, input); - mln::data::fill(deja_vu, false); + mln::data::fill(deja_vu, true); extension::fill(deja_vu, false); // So that the extension is ignored. initialize(parent, input); @@ -268,8 +269,10 @@ // First Pass. { + util::array<int> dp = negative_offsets_wrt(input, nbh); + const unsigned n_nbhs = dp.nelements(); + mln_pixter(const I) px(input); - mln_nixter(const I, N) nx(px, nbh); for_all(px) { unsigned p = px.offset(); @@ -279,10 +282,10 @@ // Make-Set. parent.element(p) = p; f.init_attr_(p); - for_all(nx) + for (unsigned i = 0; i < n_nbhs; ++i) { - unsigned n = nx.offset(); - if (deja_vu.element(n)) + unsigned n = p + dp[i]; + if (deja_vu.element(n)) // Only false in the external border. { if (f.equiv_(n, p)) { @@ -298,8 +301,6 @@ f.do_no_union_(n, p); } } - - deja_vu.element(p) = true; } } @@ -465,19 +466,21 @@ typename F> inline mln_ch_value(I, L) - labeling_video(metal::false_, const Image<I>& input, - const Neighborhood<N>& nbh, L& nlabels, F& functor) + labeling_video_dispatch(metal::false_, + const Image<I>& input, const Neighborhood<N>& nbh, L& nlabels, + F& functor) { - return impl::generic::labeling(input, nbh, input.domain(), - nlabels, functor); + return impl::generic::labeling(input, nbh, input.domain(), nlabels, + functor); } template <typename I, typename N, typename L, typename F> inline mln_ch_value(I, L) - labeling_video(metal::true_, const Image<I>& input, - const Neighborhood<N>& nbh, L& nlabels, F& functor) + labeling_video_dispatch(metal::true_, + const Image<I>& input, const Neighborhood<N>& nbh, L& nlabels, + F& functor) { return impl::labeling_video_fastest(input, nbh, nlabels, functor); } @@ -486,8 +489,8 @@ typename F> inline mln_ch_value(I, L) - labeling_video_dispatch(const Image<I>& input, const Neighborhood<N>& nbh, - L& nlabels, F& functor) + labeling_video_dispatch(const Image<I>& input, const Neighborhood<N>& nbh, L& nlabels, + F& functor) { enum { test = mlc_equal(mln_trait_image_speed(I), @@ -495,8 +498,9 @@ && mln_is_simple_neighborhood(N)::value }; - return labeling_video(metal::bool_<test>(), input, - nbh, nlabels, functor); + return labeling_video_dispatch(metal::bool_<test>(), + input, nbh, nlabels, + functor); } @@ -513,8 +517,8 @@ increasing ? level::sort_psites_increasing(input) : level::sort_psites_decreasing(input); - return impl::generic::labeling(input, nbh, nlabels, - s, functor); + return impl::generic::labeling(input, nbh, nlabels, s, + functor); } template <typename I, typename N, typename L, typename F> @@ -528,8 +532,8 @@ increasing ? level::sort_offsets_increasing(input) : level::sort_offsets_decreasing(input); - return impl::labeling_sorted_fastest(input, nbh, nlabels, - s, functor); + return impl::labeling_sorted_fastest(input, nbh, nlabels, s, + functor); } template <typename I, typename N, typename L, typename F> Index: mln/labeling/flat_zones.hh --- mln/labeling/flat_zones.hh (revision 3320) +++ mln/labeling/flat_zones.hh (working copy) @@ -67,16 +67,12 @@ template <typename I> struct flat_zones_functor { - typedef mln_psite(I) P; - - // Requirements from mln::canvas::labeling: - - typedef mln_pset(I) S; - const I& input; // Generic implementation. + typedef mln_psite(I) P; + void init() {} bool handles(const P&) const { return true; } bool equiv(const P& n, const P& p) const { return input(n) == @@ -99,7 +95,7 @@ // end of requirements. - flat_zones_functor(const I& input, const N& nbh) + flat_zones_functor(const I& input) : input(input) {} }; @@ -122,9 +118,9 @@ const N& nbh = exact(nbh_); mln_precondition(input.is_valid()); - // Calls the only implementation. - typedef flat_zones_functor<I,N,L> F; - F f(exact(input), exact(nbh)); + // Call the labeling canvas. + typedef impl::flat_zones_functor<I> F; + F f(input); mln_ch_value(I, L) output = canvas::labeling_video(input, nbh, nlabels, f); trace::exiting("labeling::flat_zones"); Index: tests/labeling/flat_zones.cc --- tests/labeling/flat_zones.cc (revision 3320) +++ tests/labeling/flat_zones.cc (working copy) @@ -1,4 +1,5 @@ -// Copyright (C) 2007, 2008 EPITA Research and Development Laboratory (LRDE) +// Copyright (C) 2007, 2008, 2009 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 @@ -25,10 +26,11 @@ // reasons why the executable file might be covered by the GNU General // Public License. -/*! \file tests/labeling/flat_zones.cc - * - * \brief Test on mln::labeling::flat_zones. - */ +/// \file tests/labeling/flat_zones.cc +/// +/// Test on mln::labeling::flat_zones. +/// +/// \todo Move commented bench to the 'bench' directory. #include <mln/core/image/image2d.hh> #include <mln/value/int_u8.hh> @@ -38,6 +40,7 @@ #include <mln/labeling/blobs.hh> #include <mln/pw/all.hh> +#include <mln/level/compare.hh> #include "tests/data.hh" @@ -49,11 +52,44 @@ image2d<int_u8> lena = io::pgm::load<int_u8>(MLN_IMG_DIR "/tiny.pgm"); + + // Bench code: + +// for (unsigned i = 0; i < 10; ++i) +// { +// typedef image2d<int_u8> I; +// labeling::impl::flat_zones_functor<I> f(lena); +// unsigned n; +// canvas::impl::labeling_video_fastest(lena, +// c4(), +// n, +// f); +// } + + unsigned n; image2d<unsigned> labels = labeling::flat_zones(lena, c4(), n); mln_assertion(n == 247); { + typedef image2d<int_u8> I; + labeling::impl::flat_zones_functor<I> f(lena); + + unsigned nlabels_generic, nlabels_fastest; + mln_assertion(canvas::impl::generic::labeling(lena, + c4(), + nlabels_generic, + lena.domain(), + f) + == + canvas::impl::labeling_video_fastest(lena, + c4(), + nlabels_fastest, + f)); + mln_assertion(nlabels_generic == nlabels_fastest); + } + + { unsigned n_ = 0; for (unsigned i = 0; i <= 255; ++i) { @@ -64,4 +100,5 @@ } mln_assertion(n_ == n); } + }