[Olena-patches] 2938: Add a morpho tree computation.

https://svn.lrde.epita.fr/svn/oln/trunk/milena Index: ChangeLog from Thierry Geraud &lt;thierry.geraud(a)lrde.epita.fr&gt; Add a morpho tree computation. * mln/morpho/tree: New directory. * mln/morpho/tree/compute_parent.hh: New; revamp of... * sandbox/geraud/max_tree_nnodes.cc: ...this file. * tests/morpho/tree: New directory. * tests/morpho/tree/compute_parent.cc: * tests/morpho/tree/Makefile.am: New. * tests/morpho/Makefile.am: Update. * mln/canvas/morpho/all.hh: Upgrade doc style. mln/canvas/morpho/all.hh | 16 +- mln/morpho/tree/compute_parent.hh | 273 +++++++++++++++++++++++------------- tests/morpho/Makefile.am | 4 tests/morpho/tree/Makefile.am | 11 + tests/morpho/tree/compute_parent.cc | 80 ++++++++++ 5 files changed, 284 insertions(+), 100 deletions(-) Index: tests/morpho/tree/compute_parent.cc --- tests/morpho/tree/compute_parent.cc (revision 0) +++ tests/morpho/tree/compute_parent.cc (revision 0) @@ -0,0 +1,80 @@ +// 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/morpho/tree/compute_parent.cc +/// +/// Tests on mln::morpho::tree::compute_parent. + +#include <mln/core/image/image2d.hh> +#include <mln/core/alias/neighb2d.hh> + +#include <mln/debug/println.hh> +#include <mln/debug/iota.hh> + +#include <mln/core/var.hh> +#include <mln/core/image/image_if.hh> +#include <mln/pw/value.hh> + +#include <mln/morpho/tree/compute_parent.hh> + + +int main() +{ + using namespace mln; + + { + bool vals[] = { 1, 1, 1, + 0, 1, 0, + 0, 0, 1 }; + image2d<bool> ima = make::image2d(vals); + mln_VAR(sub, ima | pw::value(ima)); + debug::println(sub); + + mln_VAR(par, morpho::tree::compute_parent(sub, c4(), sub.domain())); + debug::println(par); + } + +/* + { + image2d<unsigned> ima(3, 3); + debug::iota(ima); + debug::println(ima); + + debug::println( morpho::tree::compute_parent(ima, c4(), ima.domain()) ); + } + + + { + image2d<unsigned> ima(3, 3); + level::fill(ima, 0); + debug::println(ima); + + debug::println( morpho::tree::compute_parent(ima, c4(), ima.domain()) ); + } +*/ + +} Index: tests/morpho/tree/Makefile.am --- tests/morpho/tree/Makefile.am (revision 0) +++ tests/morpho/tree/Makefile.am (revision 0) @@ -0,0 +1,11 @@ +## Process this file through Automake to create Makefile.in -*- Makefile -*- + +include $(top_srcdir)/milena/tests/tests.mk + +check_PROGRAMS = \ + compute_tree + + +compute_tree_SOURCES = compute_tree_.cc + +TESTS = $(check_PROGRAMS) Index: tests/morpho/Makefile.am --- tests/morpho/Makefile.am (revision 2937) +++ tests/morpho/Makefile.am (working copy) @@ -2,7 +2,9 @@ include $(top_srcdir)/milena/tests/tests.mk -SUBDIRS = elementary +SUBDIRS = \ + elementary \ + tree check_PROGRAMS = \ artificial_line_graph_image_wst \ Index: mln/morpho/tree/compute_parent.hh --- mln/morpho/tree/compute_parent.hh (revision 0) +++ mln/morpho/tree/compute_parent.hh (working copy) @@ -1,151 +1,240 @@ +// 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_MORPHO_TREE_COMPUTE_PARENT_HH +# define MLN_MORPHO_TREE_COMPUTE_PARENT_HH + +/// \file mln/morpho/tree/compute_parent.hh +/// +/// Compute a canonized tree from an image. +/// +/// \todo Specialize for low quant (and try fastest). # include <mln/core/concept/image.hh> # include <mln/core/concept/neighborhood.hh> # include <mln/level/fill.hh> -# include <mln/util/pix.hh> -# include <mln/morpho/includes.hh> -# include <mln/level/sort_psites.hh> - -# include <mln/core/image/image2d.hh> -# include <mln/core/alias/neighb2d.hh> -# include <mln/value/int_u8.hh> -# include <mln/io/pgm/load.hh> namespace mln { - template <typename I, typename N> - struct max_tree_ + namespace morpho { - typedef mln_site(I) point; - typedef p_array<point> S; - // in: - const I& f; - const N& nbh; + namespace tree + { - // aux: - S s; - mln_ch_value(I, bool) deja_vu; - mln_ch_value(I, point) parent; - mln_ch_value(I, point) zpar; + // Remember: + // p is root iff parent(p) == p + // p is node iff either p is root or f(parent(p)) != f(p) + + template <typename I, typename N, typename S> + mln_ch_value(I, mln_psite(I)) + compute_parent(const Image<I>& f, const Neighborhood<N>& nbh, + const Site_Set<S>& s); + + + +# ifndef MLN_INCLUDE_ONLY + + + // Tests. + + + namespace internal + { - max_tree_(const I& f, const N& nbh) - : f(f), - nbh(nbh) + template <typename I, typename N, typename S> + void + compute_parent_tests(const Image<I>& f_, + const Neighborhood<N>& nbh_, + const Site_Set<S>& s_) { - run(); + const I& f = exact(f_); + const N& nbh = exact(nbh_); + const S& s = exact(s_); + + mln_precondition(f.has_data()); + // mln_precondition(nbh.is_valid()); + mln_precondition(s == f.domain()); + + (void) f; + (void) nbh; + (void) s; } - void run() + + } // end of namespace mln::morpho::tree::internal + + + + // Implementations. + + + namespace impl + { + + namespace generic { - // init + + // Z-Find-Root. + + template <typename T> + inline + mln_psite(T) zfind_root(T& zpar, const mln_psite(T)& x) { + mlc_equal(mln_value(T), mln_psite(T))::check(); + if (zpar(x) == x) + return x; + else + return zpar(x) = zfind_root(zpar, zpar(x)); + } + + // Compute-Parent. + + template <typename I, typename N, typename S> + inline + mln_ch_value(I, mln_psite(I)) + compute_parent(const Image<I>& f_, + const Neighborhood<N>& nbh_, + const Site_Set<S>& s_) + { + trace::entering("morpho::tree::impl::generic::compute_parent"); + + typedef mln_psite(I) P; + + const I& f = exact(f_); + const N& nbh = exact(nbh_); + const S& s = exact(s_); + + // Tests. + internal::compute_parent_tests(f, nbh, s); + + // Auxiliary data. + mln_ch_value(I, bool) deja_vu; + mln_ch_value(I, P) parent; + mln_ch_value(I, P) zpar; + initialize(deja_vu, f); - mln::level::fill(deja_vu, false); initialize(parent, f); initialize(zpar, f); - s = level::sort_psites_decreasing(f); - } - // first pass - { - mln_fwd_piter(S) p(s); + // Initialization. + level::fill(deja_vu, false); + + // Body. + mln_bkd_piter(S) p(s); mln_niter(N) n(nbh, p); for_all(p) { - make_set(p); + // Make-Set. + parent(p) = p; + zpar(p) = p; + for_all(n) - if (f.has(n) && deja_vu(n)) - do_union(n, p); - deja_vu(p) = true; + if (f.domain().has(n) && deja_vu(n)) + { + // Do-Union. + P r = zfind_root(zpar, n); + if (r != p) + { + parent(r) = p; + zpar(r) = p; } } + deja_vu(p) = true; + } - // second pass: canonization + // Canonization. { - mln_bkd_piter(S) p(s); + mln_fwd_piter(S) p(s); for_all(p) { - point q = parent(p); + P q = parent(p); if (f(parent(q)) == f(q)) parent(p) = parent(q); } } - } // end of run() - - void make_set(const point& p) - { - parent(p) = p; - zpar(p) = p; + trace::exiting("morpho::tree::impl::generic::compute_parent"); + return parent; } - bool is_root(const point& p) const - { - return parent(p) == p; - } + } // end of namespace mln::morpho::tree::impl::generic + + } // end of namespace mln::morpho::tree::impl - bool is_node(const point& p) const - { - return is_root(p) || f(parent(p)) != f(p); - } - point find_root(const point& x) - { - if (zpar(x) == x) - return x; - else - return zpar(x) = find_root(zpar(x)); - } - void do_union(const point& n, const point& p) + // Dispatch. + + namespace internal { - point r = find_root(n); - if (r != p) + + template <typename I, typename N, typename S> + inline + mln_ch_value(I, mln_psite(I)) + compute_parent_dispatch(const Image<I>& f, + const Neighborhood<N>& nbh, + const Site_Set<S>& s) { - parent(r) = p; - zpar(r) = p; + return impl::generic::compute_parent(f, nbh, s); } - } - - }; + } // end of namespace mln::morpho::tree::internal + // Facade. - template <typename I, typename N> - unsigned max_tree(const I& f, const N& nbh) + template <typename I, typename N, typename S> + inline + mln_ch_value(I, mln_psite(I)) + compute_parent(const Image<I>& f, const Neighborhood<N>& nbh, + const Site_Set<S>& s) { - max_tree_<I,N> run(f, nbh); + trace::entering("morpho::tree::compute_parent"); - mln_piter(I) p(f.domain()); - unsigned nnodes = 0; - for_all(p) - if (run.is_node(p)) - ++nnodes; - return nnodes; - } + internal::compute_parent_tests(f, nbh, s); + + mln_ch_value(I, mln_psite(I)) output; + output = internal::compute_parent_dispatch(f, nbh, s); -} // end of mln + trace::exiting("morpho::tree::compute_parent"); + return output; + } +# endif // ! MLN_INCLUDE_ONLY + } // end of namespace mln::morpho::tree -int main(int argc, char* argv[]) -{ - if (argc != 2) - { - std::cerr << "usage: " << argv[0] << " filename" << std::endl; - return 1; - } + } // end of namespace mln::morpho - using namespace mln; - using value::int_u8; +} // end of namespace mln - image2d<int_u8> f; - io::pgm::load(f, argv[1]); - std::cout << "n nodes = " << mln::max_tree(f, c8()) << std::endl; -} +#endif // ! MLN_MORPHO_TREE_COMPUTE_PARENT_HH Index: mln/canvas/morpho/all.hh --- mln/canvas/morpho/all.hh (revision 2937) +++ mln/canvas/morpho/all.hh (working copy) @@ -1,4 +1,5 @@ -// Copyright (C) 2007 EPITA Research and Development Laboratory +// 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 @@ -28,23 +29,24 @@ #ifndef MLN_CANVAS_MORPHO_ALL_HH # define MLN_CANVAS_MORPHO_ALL_HH -/*! \file mln/canvas/morpho/all.hh - * - * \brief File that includes morphological canvas-related routines. - */ +/// \file mln/canvas/morpho/all.hh +/// +/// File that includes morphological canvas-related routines. namespace mln { - namespace canvas { + /// Namespace of morphological canvas. namespace morpho {} - } } +} + # include <mln/canvas/morpho/algebraic_union_find.hh> + #endif // ! MLN_CANVAS_MORPHO_ALL_HH