[Olena-patches] cleanup-2008 2739: Add a generic discrete distance transform.

https://svn.lrde.epita.fr/svn/oln/branches/cleanup-2008 Index: ChangeLog from Thierry Geraud &lt;thierry.geraud(a)lrde.epita.fr&gt; Add a generic discrete distance transform. * milena/mln/transform: New. * milena/mln/transform/distance.hh: New. * milena/tests/transform: New directory. * milena/tests/transform/Makefile.am: New. * milena/tests/transform/distance.cc: New. * milena/sandbox/geraud/skel.cc: Layout. * milena/sandbox/geraud/dmap.cc: Update. Slight change in w_window. * milena/mln/core/w_window.hh (from_to): Prepare new overload. For that, add some new meta-code: * milena/mln/metal/math/root.hh: New. * milena/mln/metal/math/all.hh: Update. * milena/mln/metal/math/sqrt.hh (todo): New. * milena/tests/metal/math/root.cc: New. * milena/tests/metal/math/pow.cc: Remove echo. * milena/tests/metal/math/Makefile.am: Update. * milena/tests/morpho/Makefile.am (SUBDIRS): Fix missing. mln/core/w_window.hh | 17 +++ mln/metal/math/all.hh | 3 mln/metal/math/root.hh | 71 +++++---------- mln/metal/math/sqrt.hh | 2 mln/transform/distance.hh | 197 +++++++++++++++++++++++++++++++++++++++++++ sandbox/geraud/dmap.cc | 33 +++---- sandbox/geraud/skel.cc | 4 tests/metal/math/Makefile.am | 4 tests/metal/math/pow.cc | 5 - tests/metal/math/root.cc | 15 +-- tests/morpho/Makefile.am | 2 tests/transform/Makefile.am | 10 ++ tests/transform/distance.cc | 61 +++++++++++++ 13 files changed, 349 insertions(+), 75 deletions(-) Index: milena/tests/metal/math/root.cc --- milena/tests/metal/math/root.cc (revision 2732) +++ milena/tests/metal/math/root.cc (working copy) @@ -1,4 +1,4 @@ -// Copyright (C) 2007 EPITA Research and Development Laboratory +// 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 @@ -25,23 +25,20 @@ // reasons why the executable file might be covered by the GNU General // Public License. -/*! \file tests/metal/math/pow.cc +/*! \file tests/metal/math/root.cc * - * \brief Test on mln::metal::math::pow. + * \brief Test on mln::metal::math::root. */ #include <iostream> #include <mln/core/contract.hh> -#include <mln/metal/math/pow.hh> +#include <mln/metal/math/root.hh> int main() { using namespace mln; - using namespace mln::metal; - int res = metal::math::pow_int<2,3>::value; - mln_assertion(res == 8); - - std::cout << metal::math::pow< int_<2>, int_<3> >::ret().name() << std::endl; + int res = metal::math::root<3,8>::value; + mln_assertion(res == 2); } Index: milena/tests/metal/math/pow.cc --- milena/tests/metal/math/pow.cc (revision 2738) +++ milena/tests/metal/math/pow.cc (working copy) @@ -1,4 +1,4 @@ -// Copyright (C) 2007 EPITA Research and Development Laboratory +// 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 @@ -43,5 +43,6 @@ int res = metal::math::pow_int<2,3>::value; mln_assertion(res == 8); - std::cout << metal::math::pow< int_<2>, int_<3> >::ret().name() << std::endl; + std::string s = metal::math::pow< int_<2>, int_<3> >::ret().name(); + mln_assertion(s == "metal::int_<8>"); } Index: milena/tests/metal/math/Makefile.am --- milena/tests/metal/math/Makefile.am (revision 2738) +++ milena/tests/metal/math/Makefile.am (working copy) @@ -3,8 +3,10 @@ include $(top_srcdir)/milena/tests/tests.mk check_PROGRAMS = \ - pow + pow \ + root pow_SOURCES = pow.cc +root_SOURCES = root.cc TESTS = $(check_PROGRAMS) Index: milena/tests/transform/Makefile.am --- milena/tests/transform/Makefile.am (revision 0) +++ milena/tests/transform/Makefile.am (revision 0) @@ -0,0 +1,10 @@ +## Process this file through Automake to create Makefile.in -*- Makefile -*- + +include $(top_srcdir)/milena/tests/tests.mk + +check_PROGRAMS = \ + distance + +distance_SOURCES = distance.cc + +TESTS = $(check_PROGRAMS) Index: milena/tests/transform/distance.cc --- milena/tests/transform/distance.cc (revision 0) +++ milena/tests/transform/distance.cc (revision 0) @@ -0,0 +1,61 @@ +// 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/transform/distance.cc + * + * \brief Test on mln::transform::distance. + */ + +#include <mln/core/image/image2d.hh> +#include <mln/core/alias/neighb2d.hh> +#include <mln/make/w_window2d_int.hh> +#include <mln/value/int_u8.hh> +#include <mln/level/fill.hh> +#include <mln/debug/println.hh> + +#include <mln/transform/distance.hh> + + +int main() +{ + using namespace mln; + using value::int_u8; + + image2d<bool> input(9, 9); + level::fill(input, false); + input.at(4, 4) = true; + + int vals[] = { 0, 9, 0, 9, 0, + 9, 6, 4, 6, 9, + 0, 4, 0, 4, 0, + 9, 6, 4, 6, 9, + 0, 9, 0, 9, 0 }; + + image2d<int_u8> output = transform::distance(int_u8(), input, + c4(), make::w_window2d_int(vals)); + debug::println(output); +} Index: milena/tests/morpho/Makefile.am --- milena/tests/morpho/Makefile.am (revision 2738) +++ milena/tests/morpho/Makefile.am (working copy) @@ -2,6 +2,8 @@ include $(top_srcdir)/milena/tests/tests.mk +SUBDIRS = elementary + check_PROGRAMS = \ artificial_line_graph_image_wst \ closing_area \ Index: milena/mln/core/w_window.hh --- milena/mln/core/w_window.hh (revision 2738) +++ milena/mln/core/w_window.hh (working copy) @@ -148,6 +148,10 @@ void from_to(const Image<I>& from, w_window<D,W>& to); + template <typename V, unsigned S, typename D, typename W> + void + from_to(const V (&values)[S], w_window<D,W>& to); + } // end of namespace mln::convert @@ -339,6 +343,19 @@ to.insert(ima(p), convert::to<D>(p)); } +// template <typename V, unsigned S, typename D, typename W> +// void +// from_to(const V (&values)[S], w_window<D,W>& to) +// { +// enum { d = D::dim, +// s = mlc_root(d,S)::value / 2 }; +// metal::bool_<(mlc_pow_int(2 * s + 1, d) == S)>::check(); +// to.clear(); +// D dp; +// dp.set_all(-s); +// FIXME +// } + } // end of namespace mln::convert Index: milena/mln/metal/math/root.hh --- milena/mln/metal/math/root.hh (revision 2732) +++ milena/mln/metal/math/root.hh (working copy) @@ -25,19 +25,20 @@ // reasons why the executable file might be covered by the GNU General // Public License. -#ifndef MLN_METAL_MATH_SQRT_HH -# define MLN_METAL_MATH_SQRT_HH +#ifndef MLN_METAL_MATH_ROOT_HH +# define MLN_METAL_MATH_ROOT_HH -/*! \file mln/metal/math/sqrt.hh +/*! \file mln/metal/math/root.hh * - * \brief Definition of the 'sqrt' static function. + * \brief Definition of the 'nth-root' static function. + * + * \todo Have consistent writing of math meta-routines. */ -# include <mln/metal/bool.hh> -# include <mln/metal/int.hh> +# include <mln/metal/math/pow.hh> -# define mlc_sqrt_int(N) mln::metal::math::sqrt_int<( N )>::value +# define mlc_root(N,X) mln::metal::math::root<( N ),( X )> namespace mln @@ -49,63 +50,43 @@ namespace math { - // sqrt_int<x> - namespace impl { - template <int n, int lo = 1, int hi = n> - struct sqrt_int_ + template <unsigned n, unsigned x, + unsigned lo = 1, unsigned hi = x> + struct root { enum { mid = (lo + hi + 1) / 2, - val_lo = sqrt_int_<n, lo, mid-1>::value, - val_hi = sqrt_int_<n, mid, hi>::value + val_lo = root<n, x, lo, mid-1>::value, + val_hi = root<n, x, mid, hi>::value }; - enum { value = n < mid * mid ? val_lo : val_hi }; + enum { value = x < mlc_pow_int(mid, n) ? val_lo : val_hi }; }; - template<int n, int m> - struct sqrt_int_<n, m, m> - { - enum { value = m }; - }; - - // Entry. - - template <int n, bool b> - struct sqrt_int_if_ : sqrt_int_<n> - { - enum { value_ = sqrt_int_<n>::value, - reminder_ = n - value_ * value_ }; - // FIXME: Check that reminder_ == 0. - }; - - template <int n> - struct sqrt_int_if_< n, false > + template<unsigned n, unsigned x, unsigned m> + struct root<n, x, m, m> { + enum { value = m }; // Found. }; } // end of namespace mln::metal::math::impl - template <int n> - struct sqrt_int : impl::sqrt_int_if_< n, (n >= 0) > + template <unsigned n, unsigned x> + struct root : bool_<(n != 0)>::check_t { + enum { value = impl::root<n,x>::value, + reminder = x - mlc_pow_int(value, n) }; }; - - // sqrt<N> - - template <typename N> - struct sqrt; - - template <int n> - struct sqrt< int_<n> > + template <unsigned n> + struct root<n, 0> : bool_<(n != 0)>::check_t { - typedef int_< sqrt_int<n>::value > ret; + enum { value = 0, + reminder = 0}; }; - } // end of namespace mln::metal::math } // end of namespace mln::metal @@ -113,4 +94,4 @@ } // end of namespace mln -#endif // ! MLN_METAL_MATH_SQRT_HH +#endif // ! MLN_METAL_MATH_ROOT_HH Index: milena/mln/metal/math/all.hh --- milena/mln/metal/math/all.hh (revision 2738) +++ milena/mln/metal/math/all.hh (working copy) @@ -1,4 +1,4 @@ -// Copyright (C) 2007 EPITA Research and Development Laboratory +// 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 @@ -54,6 +54,7 @@ # include <mln/metal/math/pow.hh> +# include <mln/metal/math/root.hh> # include <mln/metal/math/sqrt.hh> # include <mln/metal/math/max.hh> // ... Index: milena/mln/metal/math/sqrt.hh --- milena/mln/metal/math/sqrt.hh (revision 2738) +++ milena/mln/metal/math/sqrt.hh (working copy) @@ -31,6 +31,8 @@ /*! \file mln/metal/math/sqrt.hh * * \brief Definition of the 'sqrt' static function. + * + * \todo Rely on nth-root. */ # include <mln/metal/bool.hh> Index: milena/mln/transform/distance.hh --- milena/mln/transform/distance.hh (revision 0) +++ milena/mln/transform/distance.hh (revision 0) @@ -0,0 +1,197 @@ +// 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. + +#ifndef MLN_TRANSFORM_DISTANCE_HH +# define MLN_TRANSFORM_DISTANCE_HH + +/*! \file mln/transform/distance.hh + * + * \brief Discrete distance transform. + */ + +# include <vector> +# include <mln/core/concept/image.hh> +# include <mln/core/concept/neighborhood.hh> +# include <mln/core/concept/weighted_window.hh> +# include <mln/level/fill.hh> +# include <mln/accu/max.hh> + + + +namespace mln +{ + + namespace transform + { + + /*! Discrete distance transform. + * + * FIXME: doc. + */ + template <typename D, typename I, typename N, typename W> + mln_ch_value(I, D) + distance(D, const Image<I>& input, + const Neighborhood<N>& nbh, const Weighted_Window<W>& w_win); + + +# ifndef MLN_INCLUDE_ONLY + + namespace impl + { + + namespace generic + { + + template <typename D, typename I, typename N, typename W> + mln_ch_value(I, D) + distance(D, const Image<I>& input_, + const Neighborhood<N>& nbh_, const Weighted_Window<W>& w_win_) + { + trace::entering("transform::impl::generic::distance"); + + const I& input = exact(input_); + const N& nbh = exact(nbh_); + const W& w_win = exact(w_win_); + + mln_precondition(input.has_data()); + + const D Max = mln_max(D); + + typedef mln_site(I) P; + typedef std::vector<P> bucket_t; + + mln_ch_value(I, D) output; + initialize(output, input); + level::fill(output, Max); + + // Modulus determination. + unsigned mod; + { + mln::accu::max<unsigned> accu; + P p; + mln_qiter(W) q(w_win, p); + for_all(q) + accu.take(q.w()); + mod = accu.to_result() + 1; + } + + std::vector<bucket_t> bucket; + bucket.resize(mod); + unsigned bucket_size = 0; + + // Initialization. + { + mln_piter(I) p(input.domain()); + mln_niter(N) n(nbh, p); + for_all(p) + if (input(p) == true) + { + output(p) = literal::zero; + for_all(n) + if (input.domain().has(n) && input(n) == false) + { + bucket[0].push_back(p); + ++bucket_size; + break; + } + } + } + + // Propagation. + { + P p; + mln_qiter(W) q(w_win, p); + + for (unsigned d = 0; bucket_size != 0; ++d) + { + bucket_t& bucket_d = bucket[d % mod]; + for (unsigned i = 0; i < bucket_d.size(); ++i) + { + p = bucket_d[i]; + if (output(p) < d) + continue; + + for_all(q) + if (output.domain().has(q) && output(q) > d) + { + if (unsigned(Max - q.w()) < d) // Saturation => Stop! + { + // trace::warning... + trace::exiting("transform::impl::generic::distance"); + return output; + } + unsigned d_ = d + q.w(); + + if (d_ < output(q)) + { + output(q) = d_; + bucket[d_ % mod].push_back(q); + ++bucket_size; + } + } + } + bucket_size -= bucket_d.size(); + bucket_d.clear(); + } + } + + trace::exiting("transform::impl::generic::distance"); + return output; + + } + + } // end of namespace mln::transform::impl::generic + + } // end of namespace mln::transform::impl + + + // Facade. + + template <typename D, typename I, typename N, typename W> + inline + mln_ch_value(I, D) + distance(D, const Image<I>& input, + const Neighborhood<N>& nbh, const Weighted_Window<W>& w_win) + { + trace::entering("transform::distance"); + + // FIXME: tests. + mln_ch_value(I, D) output = impl::generic::distance(D(), input, + nbh, w_win); + + trace::exiting("transform::distance"); + return output; + } + +# endif // ! MLN_INCLUDE_ONLY + + } // end of namespace mln::transform + +} // end of namespace mln + + +#endif // ! MLN_TRANSFORM_DISTANCE_HH Index: milena/sandbox/geraud/skel.cc --- milena/sandbox/geraud/skel.cc (revision 2738) +++ milena/sandbox/geraud/skel.cc (working copy) @@ -12,7 +12,6 @@ # include <mln/debug/println.hh> - namespace mln { @@ -75,6 +74,9 @@ return output; } +*/ + + } // mln Index: milena/sandbox/geraud/dmap.cc --- milena/sandbox/geraud/dmap.cc (revision 2738) +++ milena/sandbox/geraud/dmap.cc (working copy) @@ -21,14 +21,14 @@ const W& win = exact(win_); mln_precondition(input.has_data()); - typedef std::vector<mln_point(I)> bucket_t; + typedef std::vector<mln_site(I)> bucket_t; // Initialization of distance. mln_ch_value(I, unsigned) distance; initialize(distance, input); // Mod determination. - mln_accu_with_(accu::max, unsigned) max; + accu::max<unsigned> max; for (unsigned i = 0; i < win.size(); ++i) max.take(win.w(i)); unsigned mod = unsigned(max) + 1; @@ -59,7 +59,7 @@ // Propagation. { - mln_point(I) p; + mln_site(I) p; mln_qiter(W) q(win, p); for (unsigned d = 0; bucket_size != 0; ++d) @@ -104,26 +104,27 @@ using namespace mln; using value::int_u8; - const unsigned n = 256; + const unsigned n = 9; image2d<bool> ima(n, n); level::fill(ima, false); ima.at(n / 2, n / 2) = true; - int ws[] = { 3, 2, 3, - 2, 0, 2, - 3, 2, 3 }; - -// int ws[] = { 0, 9, 0, 9, 0, -// 9, 6, 4, 6, 9, -// 0, 4, 0, 4, 0, -// 9, 6, 4, 6, 9, -// 0, 9, 0, 9, 0 }; // coef = 4.1203 +// int ws[] = { 3, 2, 3, +// 2, 0, 2, +// 3, 2, 3 }; + + int ws[] = { 0, 9, 0, 9, 0, + 9, 6, 4, 6, 9, + 0, 4, 0, 4, 0, + 9, 6, 4, 6, 9, + 0, 9, 0, 9, 0 }; // coef = 4.1203 w_window2d_int win = make::w_window2d(ws); image2d<unsigned> d = dmap(ima, win); + debug::println(d); - image2d<int_u8> out(d.domain()); - level::stretch(d, out); - io::pgm::save(out, "out.pgm"); +// image2d<int_u8> out; +// level::stretch(d, out); +// io::pgm::save(out, "out.pgm"); }