[Olena-patches] milena r3552: Optimize propagations and add component processing functions

URL: https://svn.lrde.epita.fr/svn/oln/trunk/milena ChangeLog: 2009-03-19 Edwin Carlinet &lt;carlinet(a)lrde.epita.fr&gt; Optimize propagations and add component processing functions. * mln/morpho/tree/data.hh: Add optimization about preorder iterator. * tests/morpho/tree/data.cc: Update test file. * sandbox/edwin/tree/accumulator/arg_max.hh: New accumulator that returns site having the max value. * sandbox/edwin/tree/accumulator/max.hh: Remove. * sandbox/edwin/tree/propagate.hh: Make clean. * sandbox/edwin/tree/propagate_if.hh: Functions performing different propagations on nodes matching a predicate. * sandbox/edwin/tree/propagate_node.hh: Basic ascendant and descendant propagations computation. * sandbox/edwin/tree/propagation.cc: Test file for propagations. * sandbox/edwin/tree/routines.hh: Remove. * sandbox/edwin/tree/run.hh: Methods to apply accumulator on tree nodes, and to perform object component research with a criteria (treshold...). * sandbox/edwin/tree/test.cc: New. --- mln/morpho/tree/data.hh | 134 ++++++++++-- sandbox/edwin/tree/Makefile | 6 sandbox/edwin/tree/accumulator/arg_max.hh | 160 +++++++++++++++ sandbox/edwin/tree/propagate.hh | 102 --------- sandbox/edwin/tree/propagate_if.hh | 320 ++++++++++++++++++++++++++++++ sandbox/edwin/tree/propagate_node.hh | 46 ++-- sandbox/edwin/tree/propagation.cc | 82 ++++--- sandbox/edwin/tree/run.hh | 272 +++++++++++++++++++++++++ sandbox/edwin/tree/test.cc | 98 +++++++++ tests/morpho/tree/data.cc | 14 + 10 files changed, 1052 insertions(+), 182 deletions(-) Index: trunk/milena/tests/morpho/tree/data.cc =================================================================== --- trunk/milena/tests/morpho/tree/data.cc (revision 3551) +++ trunk/milena/tests/morpho/tree/data.cc (revision 3552) @@ -65,11 +65,18 @@ /* Check site and node up order */ tree_t::up_node_piter n(t); tree_t::up_site_piter s(t); + tree_t::up_leaf_piter l(t); n.start(); + l.start(); for_all(s) if (t.is_a_node(s)) { mln_assertion(s == n); + if (t.is_a_leaf(n)) + { + mln_assertion(l == n); + l.next(); + } n.next(); } mln_assertion(!n.is_valid()); @@ -79,11 +86,18 @@ /* Check site and node up order */ tree_t::dn_node_piter n(t); tree_t::dn_site_piter s(t); + tree_t::dn_leaf_piter l(t); n.start(); + l.start(); for_all(s) if (t.is_a_node(s)) { mln_assertion(s == n); + if (t.is_a_leaf(n)) + { + mln_assertion(l == n); + l.next(); + } n.next(); } mln_assertion(!n.is_valid()); Index: trunk/milena/mln/morpho/tree/data.hh =================================================================== --- trunk/milena/mln/morpho/tree/data.hh (revision 3551) +++ trunk/milena/mln/morpho/tree/data.hh (revision 3552) @@ -47,12 +47,16 @@ # define mln_dn_site_piter(T) typename T::dn_site_piter # define mln_up_node_piter(T) typename T::up_node_piter # define mln_dn_node_piter(T) typename T::dn_node_piter +# define mln_up_leaf_piter(T) typename T::up_leaf_piter +# define mln_dn_leaf_piter(T) typename T::dn_leaf_piter # define mln_preorder_piter(T) typename T::preorder_piter # define mln_up_site_piter_(T) T::up_site_piter # define mln_dn_site_piter_(T) T::dn_site_piter # define mln_up_node_piter_(T) T::up_node_piter # define mln_dn_node_piter_(T) T::dn_node_piter +# define mln_up_leaf_piter_(T) T::up_leaf_piter +# define mln_dn_leaf_piter_(T) T::dn_leaf_piter # define mln_preorder_piter_(T) T::preorder_piter namespace mln @@ -78,6 +82,12 @@ /// Iterate on tree's nodes (component representants) from leaves to roots. template <typename T> struct dn_node_piter; + /// Iterate on tree's leaves in the same way of up_node_piter. + template <typename T> struct up_leaf_piter; + + /// Iterate on tree's leaves in the same way of dn_node_piter. + template <typename T> struct dn_leaf_piter; + /// Preorder tree traversal iterator. template <typename T> struct preorder_piter; @@ -101,8 +111,10 @@ typedef mln_site(I) site; /// Site set associated type. typedef S sites_t; - /// Node list associated type. + /// Node set associated type. typedef p_array<mln_psite(I)> nodes_t; + /// Leaf set associated type. + typedef p_array<mln_psite(I)> leaves_t; /// Parent image associated type. typedef mln_ch_value(I, mln_psite(I)) parent_t; @@ -115,6 +127,10 @@ typedef mln::morpho::tree::up_node_piter<self_> up_node_piter; typedef mln::morpho::tree::dn_node_piter<self_> dn_node_piter; + // Iterate on leaves only. + typedef mln::morpho::tree::up_leaf_piter<self_> up_leaf_piter; + typedef mln::morpho::tree::dn_leaf_piter<self_> dn_leaf_piter; + typedef mln::morpho::tree::preorder_piter<self_> preorder_piter; // typedef mln_bkd_piter(S) piter; @@ -123,7 +139,7 @@ /// Constructor. template <typename N> - explicit data(const Image<I>& f, const Site_Set<S>& s, const Neighborhood<N>& nbh); + data(const Image<I>& f, const Site_Set<S>& s, const Neighborhood<N>& nbh); @@ -134,32 +150,46 @@ /// \} + /// \{ Child-related materials. + const p_array<mln_psite(I)>& children(const mln_psite(I)& p) const; const mln_ch_value(I, nodes_t)& children_image() const; - /// \{ Tests. + /// \} - bool is_valid() const; - bool is_root(const mln_psite(I)& p) const; - bool is_a_node(const mln_psite(I)& p) const; - bool is_a_non_root_node(const mln_psite(I)& p) const; - bool is_a_leaf(const mln_psite(I)& p) const; + /// \{ Nodes materials. - /// \} + const p_array<mln_psite(I)>& nodes() const; + /// \} - /// \{ Nodes-related materials. + /// \{ Leaves materials. - const p_array<mln_psite(I)>& nodes() const; + const p_array<mln_psite(I)>& leaves() const; /// \} - /// \{ Sites-related materials. + /// \{ Sites materials. const S& domain() const; /// \} + + + /// \{ Tests. + + bool is_valid() const; + bool is_root(const mln_psite(I)& p) const; + bool is_a_node(const mln_psite(I)& p) const; + bool is_a_non_root_node(const mln_psite(I)& p) const; + bool is_a_leaf(const mln_psite(I)& p) const; + + /// \} + + + + unsigned nroots() const; @@ -175,10 +205,13 @@ mln_ch_value(I, mln_psite(I)) parent_; // Parent image. mln_ch_value(I, nodes_t) children_; // Children image. nodes_t nodes_; + leaves_t leaves_; unsigned nroots_; }; + /* Iterators */ + template <typename T> struct up_site_piter : public mln::internal::piter_identity_< typename T::sites_t::bkd_piter, // Adaptee. @@ -227,7 +260,7 @@ up_node_piter<T> > // Exact. { private: - typedef typename T::sites_t::fwd_piter Pi_; + typedef typename T::nodes_t::fwd_piter Pi_; typedef mln::internal::piter_identity_< Pi_, up_node_piter<T> > super_; public: @@ -248,7 +281,7 @@ dn_node_piter<T> > // Exact. { private: - typedef typename T::sites_t::bkd_piter Pi_; + typedef typename T::nodes_t::bkd_piter Pi_; typedef mln::internal::piter_identity_< Pi_, dn_node_piter<T> > super_; public: @@ -264,6 +297,48 @@ }; template <typename T> + struct up_leaf_piter + : public mln::internal::piter_identity_< typename T::leaves_t::fwd_piter, // Adaptee. + up_leaf_piter<T> > // Exact. + { + private: + typedef typename T::leaves_t::fwd_piter Pi_; + typedef mln::internal::piter_identity_< Pi_, up_leaf_piter<T> > super_; + + public: + up_leaf_piter(const T& t) + { + this->change_target(t.leaves()); + } + + up_leaf_piter(const Pi_& pi) + : super_(pi) + { + } + }; + + template <typename T> + struct dn_leaf_piter + : public mln::internal::piter_identity_< typename T::leaves_t::bkd_piter, // Adaptee. + dn_leaf_piter<T> > // Exact. + { + private: + typedef typename T::leaves_t::bkd_piter Pi_; + typedef mln::internal::piter_identity_< Pi_, dn_leaf_piter<T> > super_; + + public: + dn_leaf_piter(const T& t) + { + this->change_target(t.leaves()); + } + + dn_leaf_piter(const Pi_& pi) + : super_(pi) + { + } + }; + + template <typename T> class preorder_piter : public mln::internal::site_set_iterator_base< T, preorder_piter<T> > { @@ -294,6 +369,9 @@ /// Go to the next point. void next_(); + /// Skip current point children. Next call to next() goes to the brother point. + void skip_children(); + protected: using super_::p_; using super_::s_; @@ -328,11 +406,14 @@ { nodes_.insert(p); children_(parent_(p)).insert(p); + if (is_a_leaf(p)) + leaves_.insert(p); } - else - if (parent_(p) == p) + else if (parent_(p) == p) //it's a root. { nodes_.insert(p); + if (is_a_leaf(p)) // One pixel image... + leaves_.insert(p); ++nroots_; } } @@ -418,6 +499,15 @@ template <typename I, typename S> inline + const p_array<mln_psite(I)>& + data<I,S>::leaves() const + { + mln_precondition(is_valid()); + return leaves_; + } + + template <typename I, typename S> + inline const S& data<I,S>::domain() const { @@ -490,6 +580,7 @@ const mln_psite(T::function)& p) : root_ (&p) { + mln_assertion(t.is_a_node(p)); this->change_target(t); } @@ -522,7 +613,7 @@ else { mln_dn_node_piter(T) n(*s_); - int roots = 0; + unsigned roots = 0; for (n.start(); n.is_valid() && roots < s_->nroots(); n.next()) if (s_->is_root(n)) { @@ -548,6 +639,15 @@ stack_.push_back(child); } + template <typename T> + inline + void + preorder_piter<T>::skip_children() + { + while (stack_.size() != 1 && s_->parent(stack_.back()) == p_) + stack_.pop_back(); + } + # endif // ! MLN_INCLUDE_ONLY Index: trunk/milena/sandbox/edwin/tree/routines.hh (deleted) =================================================================== Index: trunk/milena/sandbox/edwin/tree/accumulator/max.hh (deleted) =================================================================== Index: trunk/milena/sandbox/edwin/tree/accumulator/arg_max.hh =================================================================== --- trunk/milena/sandbox/edwin/tree/accumulator/arg_max.hh (revision 0) +++ trunk/milena/sandbox/edwin/tree/accumulator/arg_max.hh (revision 3552) @@ -0,0 +1,160 @@ +// 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 +// 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_ACCUMULATOR_ARG_MAX_HH_ +# define MLN_MORPHO_TREE_ACCUMULATOR_ARG_MAX_HH_ + +/// \file mln/morpho/tree/accumulator/arg_max.hh +/// +/// Define an accumulator that performs arg max. + + +# include <mln/core/concept/image.hh> +# include <mln/accu/internal/base.hh> +# include <mln/util/pix.hh> + +namespace mln { + namespace accumulator { + + template <typename I> + class arg_max : public mln::accu::internal::base<const mln_psite(I)&, arg_max<I> > + { + typedef mln::accu::internal::base<const mln_psite(I)&, arg_max<I> > super_; + + public: + typedef typename util::pix<I> argument; + + /// Constructor + arg_max(const Image<I>& ima); + /// Destructor + ~arg_max(); + + /// Manipulators. + /// \{ + void init(); + + void take(const argument& pix); + void take(const arg_max<I>& other); + + void take_as_init(const argument& pix); + /// \} + + /// Get the value of the accumulator. + const mln_psite(I)& to_result() const; + + /// Check whether the accumulator is able to give a result. + bool is_valid() const; + + private: + const I& ima_; + mln_psite(I)* p_; + }; + +# ifndef MLN_INCLUDE_ONLY + + template <typename I> + inline + arg_max<I>::arg_max(const Image<I>& ima) : + ima_ (exact(ima)), + p_ (0) + { + } + + template <typename I> + inline + arg_max<I>::~arg_max() + { + delete p_; + } + + + template <typename I> + inline + void + arg_max<I>::init() + { + } + + template <typename I> + inline + void + arg_max<I>::take(const argument& pix) + { + if (!is_valid()) + { + take_as_init(pix); + return; + } + + if (pix.v() > ima_(*p_)) + *p_ = pix.p(); + } + + template <typename I> + inline + void + arg_max<I>::take(const arg_max<I>& other) + { + mln_invariant(other.is_valid()); + + if (other.ima_(*other.p_) > ima_(*p_)) + *p_ = *other.p_; + } + + template <typename I> + inline + void + arg_max<I>::take_as_init(const argument& pix) + { + p_ = new mln_psite(I)(pix.p()); + } + + template <typename I> + inline + const mln_psite(I)& + arg_max<I>::to_result() const + { + mln_invariant(p_ != 0); + return *p_; + } + + template <typename I> + inline + bool + arg_max<I>::is_valid() const + { + return p_ != 0; + } + + +# endif // ! MLN_INCLUDE_ONLY + + } // end of namespace mln::accumulator + } // end of namespace mln + +#endif /* ! MLN_MORPHO_TREE_ACCUMULATOR_ARG_MAX_HH_ */ Index: trunk/milena/sandbox/edwin/tree/propagate.hh =================================================================== --- trunk/milena/sandbox/edwin/tree/propagate.hh (revision 3551) +++ trunk/milena/sandbox/edwin/tree/propagate.hh (revision 3552) @@ -46,7 +46,7 @@ propagate_representant(const T& t, Image<A>& a_) { A a = exact(a_); - mln_fwd_piter(T) p(t.domain()); + mln_up_site_piter(T) p(t); for_all(p) if (! t.is_a_node(p)) { @@ -55,106 +55,6 @@ } } - - - - - /// Dans le cas des images binaires... - /// Propagate a tagged node's value to its subbranches. - template <typename T, typename A> - void - propagate_to_childhood(const T& t, A& a) - { - mln_bkd_piter(T::nodes_t) n(t.nodes()); - for_all(n) - { - if (a(t.parent(n))) - { - mln_assertion(t.is_a_node(t.parent(n))); - a(n) = a(t.parent(n)); - } - } - } - - - /// Propagate a tagged node's value to its direct children. - template <typename T, typename A> - void - propagate_to_children(const T& t, A& a) - { - mln_fwd_piter(T::nodes_t) n(t.nodes()); - for_all(n) - { - if (a(t.parent(n))) - { - mln_assertion(t.is_a_node(t.parent(n))); - a(n) = a(t.parent(n)); - } - } - } - - /// Propagate a tagged node's value to its ancestors. - template <typename T, typename A> - void - propagate_to_ancestors(const T& t, A& a) - { - mln_fwd_piter(T::nodes_t) n(t.nodes()); - for_all(n) - { - if (a(n)) - { - mln_assertion(t.is_a_node(t.parent(n))); - a(t.parent(n)) = a(n); - } - } - } - - /// Propagate a tagged node's value to its direct parents. - template <typename T, typename A> - void - propagate_to_parent(const T& t, A& a) - { - mln_bkd_piter(T::nodes_t) n(t.nodes()); - for_all(n) - { - mln_assertion(t.is_a_node(n)); - if (a(n)) - { - mln_assertion(t.is_a_node(t.parent(n))); - a(t.parent(n)) = a(n); - } - } - } - - /// Propagate a tagged leaf's value to its ancestors. - /// In others words, tag the branch which the tagged leaf belongs to. - /// At the end, the tree should get this property: - /// for all n - /// a(n) is true iff there exits an l in tree's leaves such that - /// n <== l and a(l) is true. - /// TODO: post-condition which checks this property. - - - template <typename T, typename A> - void - propagate_leaf_to_ancestors(const T& t, A& a) - { - - mln_fwd_piter(T::leaves_t) l(t.leaves()); - for_all(l) - a(t.parent(l)) = 0; - - - mln_fwd_piter(T::nodes_t) n(t.nodes()); - for_all(n) - { - mln_assertion(t.is_a_node(t.parent(n))); - a(t.parent(n)) = a(t.parent(n)) || a(n); - } - } - - - } // end of namespace mln::morpho::tree } // end of namespace mln::morpho } // end of namespace mln Index: trunk/milena/sandbox/edwin/tree/run.hh =================================================================== --- trunk/milena/sandbox/edwin/tree/run.hh (revision 0) +++ trunk/milena/sandbox/edwin/tree/run.hh (revision 3552) @@ -0,0 +1,272 @@ +// 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 +// 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_PROPAGATE_RUN_HH_ +# define MLN_MORPHO_TREE_PROPAGATE_RUN_HH_ + +# include <mln/core/concept/accumulator.hh> +# include <mln/core/concept/image.hh> +# include <mln/core/concept/function.hh> + +# include <mln/core/site_set/p_array.hh> +# include <mln/util/pix.hh> + +# include "propagate_node.hh" + +namespace mln { + namespace morpho { + namespace tree { + + + /** + ** Traverse component tree \p tree and provide tree nodes values + ** to accumulator \p accu_. (Alias to "map") + ** + ** @param tree Component tree used to perform accumulation. + ** @param a_ Attributed image. + ** @accu_ Accumulator that will be applied on tree nodes. + ** + ** @return The result of accumulation. + */ + template <typename T, typename A, typename I> + mln_result(A) + run(const T& tree, + const Image<I>& a_, + Accumulator<A>& accu_); + + /** + ** Apply accumulator \accu on tree nodes. If the resulting node of + ** accumulation checks predicate \p pred, the node is inserted + ** into resulting array, then ascendant and descendant zero-fill + ** propagations are performed from the node. These operations + ** are repeated until the node won't check predicate. + ** + ** @param tree Component tree used for propagation. + ** @param a Attributed image where values are propagated. + ** @param accu_ Accumulator to apply on tree. + ** @param pred Predicate that must check the result of + ** accumulator to propagate the node. + ** + ** @return Array of propagated nodes. + */ + template <typename T, typename A, typename ACC, typename P2B> + p_array< mln_psite(A) > + run_while(const T& tree, + Image<A>& a, + Accumulator<ACC>& accu_, + Function_p2b<P2B>& pred); + + + /** + ** Apply accumulator \accu on tree nodes values n times. + ** Each time, the result of accumulator is inserted + ** into the returned array, then ascendant and descendant zero-fill + ** propagations are performed from the node. + ** (This function is a shorcut of run_while with a cardinality predicate). + ** + ** @param tree Component tree used for propagation. + ** @param a Attributed image where values are propagated. + ** @param accu_ Accumulator to apply on tree. + ** @param n The repetition number. + ** + ** @return Array of propagated nodes. + */ + template <typename T, typename A, typename ACC> + inline + p_array< mln_psite(A) > + run_ntimes(const T& tree, + Image<A>& a, + Accumulator<ACC>& acc, + unsigned n); + + /** + ** Apply accumulator \accu on tree nodes value until the value + ** accumulated by \p acc get lesser than the treshold \p n. + ** Each time, the result of accumulator is inserted + ** into the returned array, then ascendant and descendant zero-fill + ** propagations are performed from the node. + ** (This function is a shorcut of run_while with a treshold predicate). + ** + ** @param tree Component tree used for propagation. + ** @param a Attributed image where values are propagated. + ** @param accu_ Accumulator to apply on tree. + ** @param n Treshold. + ** + ** @return Array of propagated nodes. + */ + template <typename T, typename A, typename ACC> + inline + p_array< mln_psite(A) > + run_while_treshold(const T& tree, + Image<A>& a, + Accumulator<ACC>& acc, + mln_value(A) n); + +# ifndef MLN_INCLUDE_ONLY + + namespace internal + { + + template <typename T, typename A, typename ACC, typename P2B> + p_array< mln_psite(A) > + run_while(const T& tree, + A& a, + ACC& accu, + P2B& pred) + { + mln_psite(A) p; + p_array< mln_psite(A) > arr_sites; + util::array< mln_value(A) > arr_values; + + do { + p = morpho::tree::run(tree, a, accu); + if (a(p) == 0) //there's no more objects. + break; + arr_sites.insert(p); + arr_values.append(a(p)); + morpho::tree::propagate_node_to_descendants(p, tree, a, 0); + morpho::tree::propagate_node_to_ancestors(p, tree, a, 0); + a(p) = 0; + } while (pred(accu.to_result())); + for (unsigned i = 0; i < arr_sites.nsites(); i++) + a(arr_sites[i]) = arr_values[i]; + return arr_sites; + } + + struct ncard : Function_p2b< ncard > + { + typedef bool result; + + ncard(unsigned n) + : n_ (n) + { + } + + template <typename P> + bool operator()(const P& p) + { + (void)p; + return (n_-- > 0); + } + + private: + unsigned n_; + }; + + template <typename I> + struct treshold : Function_p2b< treshold<I> > + { + typedef bool result; + + treshold(const Image<I>& ima, + const mln_value(I)& treshold) + : ima_ (exact(ima)), + treshold_ (treshold) + { + } + + bool operator()(const mln_psite(I)& p) const + { + return (ima_(p) > treshold_); + } + + private: + const I& ima_; + const mln_value(I) treshold_; + }; + + + } // end of namespace mln::morpho::tree::internal + + template <typename T, typename A, typename ACC, typename P2B> + inline + p_array< mln_psite(A) > + run_while(const T& tree, + Image<A>& a_, + Accumulator<ACC>& acc, + Function_p2b<P2B>& pred) + { + A& a = exact(a_); + + mln_precondition(tree.f().domain() == a.domain()); + mln_precondition(a.is_valid()); + + return internal::run_while(tree, a, exact(acc), exact(pred)); + } + + template <typename T, typename A, typename ACC> + inline + p_array< mln_psite(A) > + run_ntimes(const T& tree, + Image<A>& a, + Accumulator<ACC>& acc, + unsigned n) + { + internal::ncard predicate(n - 1); + return run_while(tree, a, acc, predicate); + } + + + template <typename T, typename A, typename ACC> + inline + p_array< mln_psite(A) > + run_while_treshold(const T& tree, + Image<A>& a, + Accumulator<ACC>& acc, + mln_value(A) n) + { + internal::treshold<A> predicate(a, n); + return run_while(tree, a, acc, predicate); + } + + template <typename T, typename A, typename I> + mln_result(A) + run(const T& tree, + const Image<I>& a_, + Accumulator<A>& accu_) + { + A& accu = exact(accu_); + const I& a = exact(a_); + + mln_precondition(tree.f().domain() == a.domain()); + mln_precondition(a.is_valid()); + + mln_up_node_piter(T) n(tree); + for_all(n) + accu.take(make::pix(a, n)); + return (accu.to_result()); + } + +# endif // ! MLN_INCLUDE_ONLY + + + } // end of namespace mln::morpho::tree + } // end of namespace mln::morpho +} // end of namespace mln + +#endif /* !MLN_MORPHO_TREE_PROPAGATE_RUN_HH_ */ Index: trunk/milena/sandbox/edwin/tree/test.cc =================================================================== --- trunk/milena/sandbox/edwin/tree/test.cc (revision 0) +++ trunk/milena/sandbox/edwin/tree/test.cc (revision 3552) @@ -0,0 +1,98 @@ +/* mln core */ +#include <mln/core/image/image2d.hh> +#include <mln/core/alias/neighb2d.hh> +#include <mln/core/var.hh> + +/* Site set */ +#include <mln/core/site_set/p_array.hh> +#include <mln/level/sort_psites.hh> + +/* Component trees */ +#include <mln/morpho/tree/data.hh> +#include <mln/morpho/tree/compute_attribute_image.hh> +#include "propagate.hh" +#include "run.hh" +#include "accumulator/arg_max.hh" + +/* Attributes */ +#include <mln/morpho/attribute/sharpness.hh> + +/* io */ +#include <mln/io/pgm/load.hh> +#include <../../theo/color/change_attributes.hh> +#include <iostream> + +/* std */ +#include <string> + +bool mydebug = false; + + +void usage(char** argv) +{ + std::cerr << "usage: " << argv[0] << " input [--debug]" << std::endl; + abort(); +} + +void dsp(const char* str) +{ + std::cout << std::endl + << "*********************" << std::endl + << "** " << str << std::endl + << "*********************" << std::endl; +} + +int main(int argc, char* argv[]) +{ + using namespace mln; + using value::int_u8; + + if (argc < 2) + usage(argv); + + mydebug = (argc >= 3 && std::string(argv[2]) == "--debug"); + + + /* Image loadin' */ + typedef image2d<int_u8> I; + + I input; + io::pgm::load(input, argv[1]); + + /* Component tree creation */ + typedef p_array< mln_site_(I) > S; + typedef morpho::tree::data<I,S> tree_t; + + S sorted_sites = level::sort_psites_decreasing(input); + tree_t tree(input, sorted_sites, c4()); + + /* Compute Attribute On Image */ + typedef morpho::attribute::sharpness<I> accu_t; + typedef mln_ch_value_(tree_t::function, mln_result_(accu_t)) A; + + A a = morpho::tree::compute_attribute_image(accu_t (), tree); + morpho::tree::propagate_representant(tree, a); + + if (mydebug) { + dsp("Image attribute"); display_tree_attributes(tree, a); + } + + /* Run max accumulator, looking for 5 objects */ + accumulator::arg_max<A> argmax(a); + p_array< mln_psite_(A) > obj_array; // Array of object components. + obj_array = morpho::tree::run_ntimes(tree, a, argmax, 5); + + if (mydebug) { + dsp("Run max accumulator, lk 4 5 objs"); display_tree_attributes(tree, a); + } + + /* Print them */ + if (mydebug) { + dsp("Image Filtered Components"); + mln_fwd_piter_(p_array< mln_psite_(I) >) c(obj_array); + for_all(c) + std::cout << c; + } + + +} Index: trunk/milena/sandbox/edwin/tree/propagate_node.hh =================================================================== --- trunk/milena/sandbox/edwin/tree/propagate_node.hh (revision 3551) +++ trunk/milena/sandbox/edwin/tree/propagate_node.hh (revision 3552) @@ -41,41 +41,42 @@ namespace morpho { namespace tree { - /** - ** Propagate a value to a node and its descendants. + ** Propagate a value \v from a node \n to its descendants. ** - ** @param n The root of subtree which value propagates in. - ** @param t The reference to components tree. - ** @param a_ The reference to image. - ** @param v The value to propagate. Default is a_(n). + ** @param n Node to propagate. + ** @param t Component tree used for propagation. + ** @param a_ Attributed image where values are propagated. + ** @param v Value to propagate. */ template <typename T, typename A> void propagate_node_to_descendants(mln_psite(A) n, const T& t, Image<A>& a_, - mln_value(A) v); + const mln_value(A)& v); /** ** Propagate the node's value to its descendants. ** - ** @param n The root of subtree which value propagates in. - ** @param t The reference to components tree. - ** @param a_ The reference to image. + ** @param n Node to propagate. + ** @param t Component tree used for propagation. + ** @param a_ Attributed image where values are propagated. */ template <typename T, typename A> + inline void propagate_node_to_descendants(mln_psite(A)& n, const T& t, Image<A>& a_); + /** - ** Propagate a value from a node to its ancestors. + ** Propagate a value \v from a node \n to its ancestors. ** - ** @param n Forward iterator related to the node. - ** @param t Reference to components tree. - ** @param a_ Reference to image. + ** @param n Node to propagate. + ** @param t Component tree used for propagation. + ** @param a_ Attributed image where values are propagated. ** @param v Value to propagate. */ template <typename T, typename A> @@ -83,23 +84,24 @@ propagate_node_to_ancestors(mln_psite(A) n, const T& t, Image<A>& a_, - mln_value(A) v); + const mln_value(A)& v); /** ** Propagate the node's value to its ancestors. ** - ** @param n Forward iterator related to the node. - ** @param t Reference to components tree. - ** @param a_ Reference to image. + ** @param n Node to propagate. + ** @param t Component tree used for propagation. + ** @param a_ Attributed image where values are propagated. */ template <typename T, typename A> + inline void propagate_node_to_ancestors(mln_psite(A) n, const T& t, Image<A>& a_); -# ifndef MLN_INCLUDE_ONLY + //# ifndef MLN_INCLUDE_ONLY /* Descendants propagation */ @@ -109,7 +111,7 @@ propagate_node_to_descendants(mln_psite(A) n, const T& t, Image<A>& a_, - mln_value(A) v) + const mln_value(A)& v) { A& a = exact(a_); mln_precondition(a.is_valid()); @@ -148,7 +150,7 @@ propagate_node_to_ancestors(mln_psite(A) n, const T& t, Image<A>& a_, - mln_value(A) v) + const mln_value(A)& v) { A& a = exact(a_); mln_precondition(a.is_valid()); @@ -180,7 +182,7 @@ propagate_node_to_ancestors(n, t, a, a(n)); } -# endif // ! MLN_INCLUDE_ONLY + //# endif // ! MLN_INCLUDE_ONLY } // end of namespace mln::morpho::tree } // end of namespace mln::morpho Index: trunk/milena/sandbox/edwin/tree/propagation.cc =================================================================== --- trunk/milena/sandbox/edwin/tree/propagation.cc (revision 3551) +++ trunk/milena/sandbox/edwin/tree/propagation.cc (revision 3552) @@ -1,9 +1,15 @@ #include <iostream> + +#include <mln/accu/max.hh> +#include <mln/util/pix.hh> + #include <mln/core/image/image2d.hh> #include <mln/core/alias/neighb2d.hh> #include <mln/core/alias/point2d.hh> #include <mln/core/routine/duplicate.hh> +#include <mln/core/concept/function.hh> + #include <mln/value/int_u8.hh> #include <mln/io/pgm/load.hh> @@ -12,12 +18,14 @@ #include <mln/level/sort_psites.hh> #include <mln/morpho/tree/data.hh> - #include <../../theo/color/change_attributes.hh> + + + #include "propagate_node.hh" -#include "propagate_value.hh" +#include "propagate_if.hh" +#include "accumulator/arg_max.hh" #include "run.hh" -#include "accumulator/max.hh" void usage(char** argv) { @@ -46,6 +54,9 @@ print(img, it); } +using namespace mln; + + int main(int argc, char* argv[]) { using namespace mln; @@ -90,53 +101,46 @@ dsp("Propagate node to descendants : (point2d(0, 2), tree, dup)"); display_tree_attributes(tree, dup); - // dup = duplicate(input); -// morpho::tree::propagate_value_to_ancestors(117, tree, dup, 0); -// dsp("Propagate value to ancestors : (117, tree, dup, 0)"); -// display_tree_attributes(tree, dup); -// dup = duplicate(input); -// morpho::tree::propagate_value_to_ancestors(117, tree, dup); -// dsp("Propagate value to ancestors : (117, tree, dup)"); -// display_tree_attributes(tree, dup); - -// dup = duplicate(input); -// morpho::tree::propagate_value_to_descendants(117, tree, dup, 0); -// dsp("Propagate value to descendants : (117, tree, dup, 0)"); -// display_tree_attributes(tree, dup); - -// dup = duplicate(input); -// morpho::tree::propagate_value_to_descendants(117, tree, dup); -// dsp("Propagate value to descendants : (117, tree, dup)"); -// display_tree_attributes(tree, dup); + dup = duplicate(input); + morpho::tree::propagate_if_value(tree, dup, morpho::tree::asc_propagation (), 117, 0); + dsp("Propagate value to ancestors : (117, tree, dup, 0)"); + display_tree_attributes(tree, dup); + dup = duplicate(input); + morpho::tree::propagate_if_value(tree, dup, morpho::tree::asc_propagation (), 117); + dsp("Propagate value to ancestors : (117, tree, dup)"); + display_tree_attributes(tree, dup); + dup = duplicate(input); + morpho::tree::propagate_if_value(tree, dup, morpho::tree::desc_propagation (), 117, 0); + dsp("Propagate value to descendants : (117, tree, dup, 0)"); + display_tree_attributes(tree, dup); dup = duplicate(input); + morpho::tree::propagate_if_value(tree, dup, morpho::tree::desc_propagation (), 117); + dsp("Propagate value to descendants : (117, tree, dup)"); + display_tree_attributes(tree, dup); + - typedef morpho::tree::accumulator::max<tree_t, I> A; - A accu(dup); - morpho::tree::run_bkd(tree, accu); + accumulator::arg_max<I> mmax; + p_array< mln_psite_(I) > tabmax; + mln_fwd_piter_(p_array< mln_psite_(I) >) pit(tabmax); - mln_bkd_piter_(tree_t::nodes_t) it_max = accu.to_result(); - morpho::tree::propagate_node_to_descendants(it_max, tree, dup, 69); - dsp("Propagate value to descendants : (it_max, tree, dup, 69)"); + dup = duplicate(input); + tabmax = morpho::tree::run_ntimes(tree, dup, mmax, 5); + for_all(pit) + std::cout << pit << std::endl; + dsp("Run ntimes : (tree, dup, max, 5)"); display_tree_attributes(tree, dup); -// mln_dn_node_piter_(tree_t) n(tree); -// n.start(); -// print(tree.children_image(), n); - std::cout << "\n"; - mln_preorder_piter_(tree_t) pit(tree); - mln_psite_(I) parent; + dup = duplicate(input); + tabmax = morpho::tree::run_while_treshold(tree, dup, mmax, 20); for_all(pit) - { - if (parent != tree.parent(pit)) - std::cout << std::endl; - std::cout << pit << " -> "; - parent = pit; - } + std::cout << pit << std::endl; + dsp("Run with treshold : (tree, dup, max, 20)"); + display_tree_attributes(tree, dup); } Index: trunk/milena/sandbox/edwin/tree/Makefile =================================================================== --- trunk/milena/sandbox/edwin/tree/Makefile (revision 3551) +++ trunk/milena/sandbox/edwin/tree/Makefile (revision 3552) @@ -1,11 +1,11 @@ -TARGET=propagation -SRC=propagation.cc +TARGET=test +SRC=test.cc OBJS=${SRC:.cc=.o} OLENADIR=$(MLN_DIR)/.. MILENADIR=$(OLENADIR)/milena -CXXFLAGS=-I$(MILENADIR) -I./ +CXXFLAGS=-I$(MILENADIR) -I./ -W -Wall CXXFLAGS += -g -ggdb #CXXFLAGS += -DNDEBUG -O1 Index: trunk/milena/sandbox/edwin/tree/propagate_if.hh =================================================================== --- trunk/milena/sandbox/edwin/tree/propagate_if.hh (revision 0) +++ trunk/milena/sandbox/edwin/tree/propagate_if.hh (revision 3552) @@ -0,0 +1,320 @@ +// 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 +// 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_PROPAGATE_IF_HH_ +# define MLN_MORPHO_TREE_PROPAGATE_IF_HH_ + +/** +** @file mln/morpho/tree/propagate_if.hh +** +** @brief Methods to handle propagation startegies +** in component trees. +** +*/ + +# include <mln/morpho/tree/data.hh> +# include "propagate_node.hh" + +namespace mln { + namespace morpho { + namespace tree { + + template <typename WP> + struct way_of_propagation : Object< WP > { protected: way_of_propagation() {}; }; + struct desc_propagation : way_of_propagation <desc_propagation> {}; + struct asc_propagation : way_of_propagation <asc_propagation> {}; + + /** + ** Propagate nodes checking the predicate \p pred in the way + ** defined by \p way_of_propagation. + ** + ** @param tree Component tree used for propagation. + ** @param a_ Attributed image where values are propagated. + ** @param way_of_propagation Propagate node in acsendant or + ** descendant way. + ** @param pred Predicate that node must check to be propagated. + ** @param v Value to be propagated. (By default \v is the value + ** at the node being propagated). + */ + template <typename T, typename A, class P, typename WP> + inline + void + propagate_if(const T& tree, + Image<A>& a_, + const way_of_propagation<WP>&, + const P& pred, + const mln_value(A)& v); + + template <typename T, typename A, class P, typename WP> + inline + void + propagate_if(const T& tree, + Image<A>& a_, + const way_of_propagation<WP>&, + const P& pred); + + /** + ** Propagate nodes having the value v in the way + ** defined by \p way_of_propagation. + ** + ** @param tree Component tree used for propagation. + ** @param a_ Attributed image where values are propagated. + ** @param way_of_propagation Propagate node in acsendant or + ** descendant way. + ** @param v Value that node must have to be propagated. + ** @param v_prop Value to propagate (By default it is the value + ** at the node being propagated). + */ + template <typename T, typename A, class P, typename WP> + inline + void + propagate_if_value(const T& tree, + Image<A>& a_, + const way_of_propagation<WP>&, + const mln_value(A)& v, + const mln_value(A)& v_prop); + + + +# ifndef MLN_INCLUDE_ONLY + + namespace internal + { + + template <typename I> + struct pred_value_eq : public mln::Function_p2b< pred_value_eq<I> > + { + typedef bool result; + + pred_value_eq(const I& a, const mln_value(I)& v) + : a_ (a), + v_ (v) + { + mln_invariant(a_.is_valid()); + } + + bool operator() (const mln_psite(I)& p) const + { + mln_invariant(a_.domain().has(p)); + return (v_ == a_(p)); + } + + private: + const I& a_; + const mln_value(I) v_; + }; + + + template <typename T, typename A> + bool check_propagate_value(const T& t, + const A& a, + const asc_propagation& prop, + const mln_value(A)& v) + { + (void) prop; + mln_up_node_piter(T) n(t); + for_all(n) + if (a(n) == v && a(t.parent(n)) != v) + return false; + return true; + } + + template <typename T, typename A> + bool check_propagate_value(const T& t, + const A& a, + const desc_propagation& prop, + const mln_value(A)& v) + { + (void) prop; + mln_up_node_piter(T) n(t); + for_all(n) + if (a(n) != v && a(t.parent(n)) == v) + return false; + return true; + } + + + template <typename T, typename A, class P> + inline + void + propagate_if(const T& tree, + Image<A>& a_, + const desc_propagation& prop, + const P& pred, + const mln_value(A)& v) + { + const A& a = exact(a_); + (void) prop; + + mln_precondition(a.is_valid()); + mln_precondition(tree.f().domain() == a.domain()); + + mln_preorder_piter(T) n(tree); + for_all(n) + if (pred(n)) + { + propagate_node_to_descendants(n, tree, a_, v); + n.skip_children(); + } + } + + template <typename T, typename A, class P> + inline + void + propagate_if(const T& tree, + Image<A>& a_, + const desc_propagation& prop, + const P& pred) + { + const A& a = exact(a_); + (void) prop; + + mln_precondition(a.is_valid()); + mln_precondition(tree.f().domain() == a.domain()); + + mln_preorder_piter(T) n(tree); + for_all(n) + if (pred(n)) + { + propagate_node_to_descendants(n, tree, a_); + n.skip_children(); + } + } + + template <typename T, typename A, class P> + inline + void + propagate_if(const T& tree, + Image<A>& a_, + const asc_propagation& prop, + const P& pred, + const mln_value(A)& v) + { + const A& a = exact(a_); + (void) prop; + + mln_precondition(a.is_valid()); + mln_precondition(tree.f().domain() == a.domain()); + + mln_up_node_piter(T) n(tree); + for_all(n) + if (pred(n)) + propagate_node_to_ancestors(n, tree, a_, v); + } + + template <typename T, typename A, class P> + inline + void + propagate_if(const T& tree, + Image<A>& a_, + const asc_propagation& prop, + const P& pred) + { + const A& a = exact(a_); + (void) prop; + + mln_precondition(a.is_valid()); + mln_precondition(tree.f().domain() == a.domain()); + + mln_up_node_piter(T) n(tree); + for_all(n) + if (pred(n)) + propagate_node_to_ancestors(n, tree, a_, a(n)); + } + + } // end of namespace mln::morpho::tree::internal + + + /* Facades */ + + template <typename T, typename A, typename WP> + inline + void + propagate_if_value(const T& tree, + Image<A>& a_, + const way_of_propagation<WP>& prop_, + const mln_value(A)& v, + const mln_value(A)& v_prop) + { + A& a = exact(a_); + const WP& prop = exact(prop_); + internal::pred_value_eq<A> pred(a, v); + + internal::propagate_if(tree, a_, prop, pred, v_prop); + } + + + template <typename T, typename A, typename WP> + inline + void + propagate_if_value(const T& tree, + Image<A>& a_, + const way_of_propagation<WP>& prop_, + const mln_value(A)& v) + { + const A& a = exact(a_); + const WP& prop = exact(prop_); + internal::pred_value_eq<A> pred(a, v); + + internal::propagate_if(tree, a_, prop, pred); + mln_postcondition(internal::check_propagate_value(tree, a, prop, v)); + } + + template <typename T, typename A, class P, typename WP> + inline + void + propagate_if(const T& tree, + Image<A>& a_, + const way_of_propagation<WP>& prop_, + const P& pred, + const mln_value(A)& v) + { + const WP& prop = exact(prop_); + internal::propagate_if(tree, a_, prop, pred, v); + } + + template <typename T, typename A, class P, typename WP> + inline + void + propagate_if(const T& tree, + Image<A>& a_, + const way_of_propagation<WP>& prop_, + const P& pred) + { + const WP& prop = exact(prop_); + internal::propagate_if(tree, a_, prop, pred); + } + +#endif /* !MLN_INCLUDE_ONLY */ + + + } // end of namespace mln::morpho::tree + } // end of namespace mln::morpho +} // end of namespace mln + +#endif /* !MLN_MORPHO_TREE_PROPAGATE_IF_HH_ */