September 2013 - Olena-patches

olena: branch maxtree-integration created: olena-2.0-791-g3193cca
by git＠lrde.epita.fr 05 Sep '13

05 Sep '13

This is an automated email from the git hooks/post-receive script. It was generated because a ref change was pushed to the repository containing the project "Olena, a generic and efficient image processing platform". The branch maxtree-integration has been created at 3193cca84ee8ff98f1f406fd255313aabdfb23fb (commit) - Log ----------------------------------------------------------------- 3193cca Fix some shortcomings in binary subsampling. This function used to memory leak and makes an unnecessary heap memory allocation. Moreover, it makes some unnecessary assumptions about the domain of the image (only worked for 2D images with a domain starting at (0,0)). e3bd054 Fix issues with loading ascii ppm. 5b8491a Minor updates to make things compile. a7536eb Add MLN_WO_GLOBAL_VARS directive that prevents globals vars to be included. 366258c Tree debug tools. 9d7b9fa Tree build algorithms and tree management routines ab86054 Unified structure for simple/dual input min/max tree. ----------------------------------------------------------------------- hooks/post-receive -- Olena, a generic and efficient image processing platform

1 0

olena: olena-2.0-791-g3193cca Fix some shortcomings in binary subsampling. This function used to memoryleak and makes an unnecessary heap memory allocation. Moreover, it makes someunnecessary assumptions about the domain of the image (only worked for 2D images with a domainstarting at (0,0)).
by Edwin Carlinet 05 Sep '13

05 Sep '13

* milena/mln/world/binary_2d/subsample.hh: Many fixes. Conflicts: milena/ChangeLog milena/mln/world/binary_2d/subsample.hh --- milena/ChangeLog | 12 +++++++- milena/mln/world/binary_2d/subsample.hh | 51 ++++++++++++++++++++++--------- 2 files changed, 47 insertions(+), 16 deletions(-) diff --git a/milena/ChangeLog b/milena/ChangeLog index 9572039..22bee5f 100644 --- a/milena/ChangeLog +++ b/milena/ChangeLog @@ -1,4 +1,3 @@ -<<<<<<< HEAD 2013-09-02 Roland Levillain <roland(a)lrde.epita.fr> Add parentheses around complex operands of operator `|'. @@ -4770,6 +4769,17 @@ * mln/geom/crop.hh, * mln/geom/crop_without_localization.hh: New. +2013-09-05 Edwin Carlinet <carlinet(a)lrde.epita.fr> + + Fix some shortcomings in binary subsampling. This function used to + memory leak and makes an unnecessary heap memory + allocation. Moreover, it makes some unnecessary assumptions about + the domain of the image (only worked for 2D images with a domain + starting at (0,0)). + + * milena/mln/world/binary_2d/subsample.hh: Many fixes. + + 2012-06-05 Edwin Carlinet <carlinet(a)lrde.epita.fr> Fix issues with loading ascii ppm. diff --git a/milena/mln/world/binary_2d/subsample.hh b/milena/mln/world/binary_2d/subsample.hh index 3ea041a..f6baf6c 100644 --- a/milena/mln/world/binary_2d/subsample.hh +++ b/milena/mln/world/binary_2d/subsample.hh @@ -50,7 +50,18 @@ namespace mln namespace binary_2d { - /// Subsample a Boolean image. + /// \brief Subsample a Boolean image. + /// + /// Subsample a binary image by a factor \p n and return a gray + /// level image by averaging. + /// + /// \[ + /// out(p) = \frac{1}{n^2} \sum_{\epsilon=1}^n input(n.(p+pmin) + + /// \langle \epsilon, 1\rangle ) + /// \] + /// + /// Note that even if the input image does not have its origin + /// at (0,0), the output image does so. /// /// \param[in] input A binary image. /// \param[in] n Linear subsampling coefficient. @@ -75,31 +86,41 @@ namespace mln if (n == 0) return data::convert(int_u8(), input); - const bool** ptr = new const bool*[n]; + const unsigned nrows = input.nrows() / n; const unsigned ncols = input.ncols() / n; - image2d<int_u8> output(nrows, ncols); - - const unsigned delta_row = input.delta_offset(down); - for (unsigned row = 0; row < nrows; ++row) + algebra::vec<2, unsigned int> vmin; + algebra::vec<2, unsigned int> vmax; + vmin[0] = 0; + vmin[1] = 0; + vmax[0] = nrows - 1; + vmax[1] = ncols - 1; + point2d pmin(vmin); + point2d pmax(vmax); + + image2d<int_u8> output(box<point2d>(pmin, pmax)); + dpoint2d dp_row(1, 0); + const unsigned delta_row = input.delta_index(dp_row); + + const bool* origin = &input(input.domain().pmin()); + const bool* line_ptr = origin; + for (unsigned row = 0; row < nrows; ++row, line_ptr += delta_row * n) { - ptr[0] = & input(point2d(n * row, 0)); - for (unsigned i = 1; i < n; ++i) - ptr[i] = ptr[i - 1] + delta_row; - for (unsigned col = 0; col < ncols; ++col) + const bool* ptr = line_ptr; + for (unsigned col = 0; col < ncols; ++col, ptr += n) { unsigned count = 0; for (unsigned i = 0; i < n; ++i) - for (unsigned j = 0; j < n; ++j, ++(ptr[i])) - if (*(ptr[i])) + for (unsigned j = 0; j < n; ++j) + { + if (ptr[delta_row * i + j]) ++count; - output(point2d(row, col)) = count * mln_max(int_u8) / n / n; + } + output.at_(row, col) = count * 255 / n / n; } } - delete[] ptr; - return output; } -- 1.7.10.4

1 0

olena: olena-2.0-790-ge3bd054 Fix issues with loading ascii ppm.
by Edwin Carlinet 05 Sep '13

05 Sep '13

* io/pnm/load.hh: add specials cases to handle vectorial type when loading from ascii ppms. Conflicts: milena/ChangeLog --- milena/ChangeLog | 13 ++++++++----- milena/mln/io/pnm/load.hh | 43 +++++++++++++++++++++++++++++++++++++++---- 2 files changed, 47 insertions(+), 9 deletions(-) diff --git a/milena/ChangeLog b/milena/ChangeLog index af4f536..9572039 100644 --- a/milena/ChangeLog +++ b/milena/ChangeLog @@ -1,3 +1,4 @@ +<<<<<<< HEAD 2013-09-02 Roland Levillain <roland(a)lrde.epita.fr> Add parentheses around complex operands of operator `|'. @@ -4769,6 +4770,13 @@ * mln/geom/crop.hh, * mln/geom/crop_without_localization.hh: New. +2012-06-05 Edwin Carlinet <carlinet(a)lrde.epita.fr> + + Fix issues with loading ascii ppm. + + * io/pnm/load.hh: add specials cases to handle vectorial type when + loading from ascii ppms. + 2011-10-14 Guillaume Lazzara <z(a)lrde.epita.fr> * mln/value/builtin/floatings.hh: Fix string name for builtin @@ -6840,11 +6848,6 @@ (make::edge_image(const vertex_image<P,V,G>&, const Function_v2b<F>&)): Actually use the predicate passed as second argument. Remove debug code. -======= - * mln/trait/ch_value.hh, - * mln/util/ctree/node.hh, - * mln/value/sign.hh : Add MLN_WO_GLOBAL_VARS define. ->>>>>>> Add MLN_WO_GLOBAL_VARS directive that prevents globals vars to be 2010-05-04 edwin carlinet <carlinet(a)lrde.epita.fr> diff --git a/milena/mln/io/pnm/load.hh b/milena/mln/io/pnm/load.hh index ee77e5e..acd9400 100644 --- a/milena/mln/io/pnm/load.hh +++ b/milena/mln/io/pnm/load.hh @@ -44,7 +44,9 @@ # include <mln/io/pnm/max_component.hh> # include <mln/io/pnm/macros.hh> +# include <mln/trait/value_.hh> # include <mln/metal/is_a.hh> +# include <mln/metal/bool.hh> namespace mln { @@ -59,7 +61,13 @@ namespace mln # ifndef MLN_INCLUDE_ONLY template <typename I> - void load_ascii_value(std::ifstream& file, I& ima); + void + load_ascii_value(std::ifstream& file, I& ima, metal::true_ is_scalar); + + template <typename I> + void + load_ascii_value(std::ifstream& file, I& ima, metal::false_ is_scalar); + template <typename I> void load_ascii_builtin(std::ifstream& file, I& ima); @@ -73,7 +81,7 @@ namespace mln void load_ascii_dispatch(std::ifstream& file, I& ima, const metal::bool_<true>&) { - load_ascii_value(file, ima); + load_ascii_value(file, ima, mlc_bool( mln_dim(mln_value(I)) == 1 ) () ); } template <typename I> @@ -158,20 +166,47 @@ namespace mln file.read((char*)(&ima(p)), len); } - /// load_ascii for Milena value types. + /// load_ascii for Vectorial Milena value types. template <typename I> inline - void load_ascii_value(std::ifstream& file, I& ima) + void + load_ascii_value(std::ifstream& file, I& ima, metal::false_) + { + enum { dim = mln_dim(mln_value(I)) }; + typedef mln_equiv(mln_value_(I)) E; + typedef mln_equiv(trait::value_<E>::comp) T; + E v; + T x; + + mln_fwd_piter(I) p(ima.domain()); + for_all(p) + { + for (int i = 0; i<dim; ++i) { + file >> x; + v[i] = x; + } + ima(p) = v; + } + } + + /// load_ascii for Scalar Milena value types + template <typename I> + inline + void + load_ascii_value(std::ifstream& file, I& ima, metal::true_) { mln_equiv(mln_value_(I)) c; + mln_fwd_piter(I) p(ima.domain()); for_all(p) { file >> c; + std::cout << c << std::endl; ima(p) = c; } } + /// load_ascii for builtin value types. template <typename I> inline -- 1.7.10.4

1 0

olena: olena-2.0-789-g5b8491a Minor updates to make things compile.
by Edwin Carlinet 05 Sep '13

05 Sep '13

* milena/mln/core/image/attribute_image.hh: add explicit constructor. * milena/mln/morpho/tree/leaf_last.hh: energy minimization instead of maximization. * milena/mln/util/ctree/ctree.hh: bug fix.Minor --- milena/ChangeLog | 10 ++++++++++ milena/mln/core/image/attribute_image.hh | 2 +- milena/mln/morpho/tree/leaf_last.hh | 4 +++- milena/mln/util/ctree/ctree.hh | 8 +++++++- 4 files changed, 21 insertions(+), 3 deletions(-) diff --git a/milena/ChangeLog b/milena/ChangeLog index c50015e..af4f536 100644 --- a/milena/ChangeLog +++ b/milena/ChangeLog @@ -5384,6 +5384,16 @@ * mln/convert/impl/from_unsigned_to_value.hh, * mln/value/label.hh: Here. +2011-03-02 edwin carlinet <carlinet(a)lrde.epita.fr> + Minor updates to make things compile. + + * milena/mln/core/image/attribute_image.hh: add explicit + constructor. + * milena/mln/morpho/tree/leaf_last.hh: energy minimization instead + of maximization. + * milena/mln/util/ctree/ctree.hh: Copy the domain instead of + taking a reference that can be dangling. + 2011-03-01 Guillaume Lazzara <z(a)lrde.epita.fr> * mln/labeling/fill_holes.hh: Improve speed. diff --git a/milena/mln/core/image/attribute_image.hh b/milena/mln/core/image/attribute_image.hh index 1331a6f..cc2d760 100644 --- a/milena/mln/core/image/attribute_image.hh +++ b/milena/mln/core/image/attribute_image.hh @@ -160,7 +160,7 @@ namespace mln /// Constructor without argument. attribute_image(); /// Allocate an attribute image respecting the size of the tree. - attribute_image(const Tree<T>& tree); + explicit attribute_image(const Tree<T>& tree); /// \} /// Initialize an empty image. diff --git a/milena/mln/morpho/tree/leaf_last.hh b/milena/mln/morpho/tree/leaf_last.hh index 2f283d5..07ad8a1 100644 --- a/milena/mln/morpho/tree/leaf_last.hh +++ b/milena/mln/morpho/tree/leaf_last.hh @@ -61,7 +61,7 @@ namespace mln bool operator() (const node_t& lhs, const node_t& rhs) { - return f_(lhs) > f_(rhs); + return f_(lhs) < f_(rhs); } private: @@ -77,6 +77,8 @@ namespace mln typedef typename T::node_t node_t; p_array<node_t> sorted_sites = convert::to_p_array(ima); + mln_invariant(sorted_sites.nsites() == ima.nsites()); + std::vector<node_t>& hook = sorted_sites.hook_std_vector_(); std::sort(hook.begin(), hook.end(), internal::less_<T, V> (ima)); diff --git a/milena/mln/util/ctree/ctree.hh b/milena/mln/util/ctree/ctree.hh index e1c7148..39e7170 100644 --- a/milena/mln/util/ctree/ctree.hh +++ b/milena/mln/util/ctree/ctree.hh @@ -39,9 +39,11 @@ # include <mln/core/concept/site_set.hh> # include <mln/util/ctree/internal/tree_base.hh> # include <mln/util/array.hh> +# include <mln/data/fill.hh> # include <mln/core/image/attribute_image.hh> # include <algorithm> + # define mln_node(T) typename T::node_t namespace mln @@ -101,7 +103,7 @@ namespace mln std::vector<unsigned> length_; std::vector<mln_value(I)> values_; - const mln_domain(I)& domain_; + mln_domain(I) domain_; int nnodes; }; @@ -244,10 +246,13 @@ namespace mln /// Equivalent to desc(tree.node_at(i)).nsites(). unsigned length_at_(index_t i) const; unsigned& length_at_(index_t i); + rvalue f_at_(index_t i) const; lvalue f_at_(index_t i); + index_t parent_at_(index_t i) const; index_t& parent_at_(index_t i); + index_t node_at_(const psite& p) const; index_t& node_at_(const psite& p); /// \} @@ -342,6 +347,7 @@ namespace mln this->data_ = new mln::internal::data< ctree >(f); initialize(this->data_->map_, f); + this->data_->domain_ = f.domain(); this->data_->parent_.resize(nnodes); this->data_->length_.resize(nnodes); this->data_->values_.resize(nnodes); -- 1.7.10.4

1 0

olena: olena-2.0-788-ga7536eb Add MLN_WO_GLOBAL_VARS directive that prevents globals vars to be included.
by Edwin Carlinet 05 Sep '13

05 Sep '13

* mln/border/thickness.hh, * mln/core/alias/dpoint1d.hh, * mln/core/alias/dpoint2d.hh, * mln/core/alias/dpoint3d.hh, * mln/fun/v2v/hsl_to_rgb.hh, * mln/literal/black.hh, * mln/literal/colors.hh, * mln/literal/identity.hh, * mln/literal/one.hh, * mln/literal/origin.hh, * mln/literal/white.hh, * mln/literal/zero.hh, * mln/tag/init.hh, * mln/trace/entering.hh, * mln/trace/quiet.hh, * mln/trait/ch_value.hh, * mln/util/ctree/node.hh, * mln/value/sign.hh : Add MLN_WO_GLOBAL_VARS define. Conflicts: milena/ChangeLog --- milena/ChangeLog | 16 +++++----------- milena/mln/trait/ch_value.hh | 8 ++++++++ milena/mln/util/ctree/node.hh | 14 ++++++++++++++ 3 files changed, 27 insertions(+), 11 deletions(-) diff --git a/milena/ChangeLog b/milena/ChangeLog index 31cef75..c50015e 100644 --- a/milena/ChangeLog +++ b/milena/ChangeLog @@ -6111,17 +6111,6 @@ * mln/fun/x2x/translation.hh: Introduce data_t typedef passed to x2x_linear_impl. -2010-04-30 Guillaume Lazzara <z(a)lrde.epita.fr> - - Add some code in my sandbox. - - * sandbox/lazzara/scribo/binarization_naive/main.cc, - * sandbox/lazzara/scribo/binarization_naive/toto.cc, - * sandbox/lazzara/scribo/fill_holes/main.cc, - * sandbox/lazzara/scribo/separateurs_materialises/lines_pattern.cc, - * sandbox/lazzara/scribo/skeleton_crest/main.cc, - * sandbox/lazzara/skeleton_crest/main.cc: New. - 2010-05-21 edwin carlinet <carlinet(a)lrde.epita.fr> Add MLN_WO_GLOBAL_VARS directive that prevents globals vars to be @@ -6841,6 +6830,11 @@ (make::edge_image(const vertex_image<P,V,G>&, const Function_v2b<F>&)): Actually use the predicate passed as second argument. Remove debug code. +======= + * mln/trait/ch_value.hh, + * mln/util/ctree/node.hh, + * mln/value/sign.hh : Add MLN_WO_GLOBAL_VARS define. +>>>>>>> Add MLN_WO_GLOBAL_VARS directive that prevents globals vars to be 2010-05-04 edwin carlinet <carlinet(a)lrde.epita.fr> diff --git a/milena/mln/trait/ch_value.hh b/milena/mln/trait/ch_value.hh index 87afc0a..f543579 100644 --- a/milena/mln/trait/ch_value.hh +++ b/milena/mln/trait/ch_value.hh @@ -59,6 +59,7 @@ namespace mln template <typename G, typename F> class p_vertices; template <typename P, typename V, typename G> class vertex_image; template <typename P, typename V, typename G> class edge_image; + template <typename T, typename V> class attribute_image; template <typename I> class labeled_image; namespace pw { template <typename F, typename S> class image; } @@ -205,6 +206,13 @@ namespace mln typedef mln_ch_value(I,V) ret; }; + // Attribute image. + template <typename T, typename V1, typename V2> + struct ch_value_< attribute_image< tag::tree_<T>, tag::value_<V1> >, V2 > + { + typedef attribute_image<T, V2> ret; + }; + template < template <class, class> class M, typename T, typename S, typename V > diff --git a/milena/mln/util/ctree/node.hh b/milena/mln/util/ctree/node.hh index d22c48e..ebdc955 100644 --- a/milena/mln/util/ctree/node.hh +++ b/milena/mln/util/ctree/node.hh @@ -130,6 +130,12 @@ namespace mln bool operator!= (const node<T>& n1, const node<T>& n2); + /// Test if the node \p n1 is a descendant of \p n2 + /// + template <typename T> + bool + operator< (const node<T>& n1, const node<T>& n2); + } // end of namespace mln::util::ctree } // end of namespace mln::util @@ -273,6 +279,14 @@ namespace mln return n1.index() != n2.index(); } + template <typename T> + inline + bool + operator< (const node<T>& n1, const node<T>& n2) + { + return n1.index() > n2.index(); + } + } // end of namespace mln::util::ctree } // end of namespace mln::util -- 1.7.10.4

1 0

[Olena] #280: Get rid of trash directories
by Olena Trac 05 Sep '13

05 Sep '13

#280: Get rid of trash directories ----------------------+------------------------ Reporter: levill_r | Owner: Olena Team Type: task | Status: new Priority: minor | Milestone: Olena 2.1 Component: Milena | Version: 2.0 Keywords: cleanup | ----------------------+------------------------ I.e.: * source:milena/doc/examples/trash * source:milena/trash Rationale: if their content is not distributed, they should not be part of `master`. We can style reintegrate them later from the repository's history if needed. -- Ticket URL: <https://trac.lrde.epita.fr/olena/ticket/280> Olena <http://olena.lrde.epita.fr> Olena, a software platform dedicated to image processing.

1 0

olena: olena-2.0-786-g9d7b9fa Tree build algorithms and tree management routines
by Edwin Carlinet 05 Sep '13

05 Sep '13

* mln/core/image/all.hh: Update. * mln/morpho/tree/all.hh: Update. * mln/tag/skeleton.hh: Update. * mln/morpho/tree/component_tree.hh: Routines to build component trees. * mln/morpho/tree/compute_attribute_image.hh: Routines to compute attribute images. * mln/morpho/tree/dual_input_tree.hh: Routines to build dual-input trees. * mln/morpho/tree/filter/direct.hh, * mln/morpho/tree/filter/max.hh, * mln/morpho/tree/filter/min.hh, * mln/morpho/tree/filter/subtractive.hh: Filtering routines. * mln/morpho/tree/impl/hqueue.hh, * mln/morpho/tree/impl/hqueue_fast.hh, * mln/morpho/tree/impl/union_find.hh, * mln/morpho/tree/impl/union_find_fast.hh: Tree computation algorithms. * mln/morpho/tree/leaf_last.hh, * mln/morpho/tree/propagate_node.hh: Tree management routines. Conflicts: milena/mln/morpho/tree/compute_attribute_image.hh milena/mln/morpho/tree/dual_input_tree.hh milena/mln/morpho/tree/filter/direct.hh milena/mln/morpho/tree/filter/max.hh milena/mln/morpho/tree/filter/min.hh milena/mln/morpho/tree/filter/subtractive.hh milena/mln/morpho/tree/impl/dual_hqueue.hh milena/mln/morpho/tree/propagate_node.hh --- milena/mln/core/image/all.hh | 1 + milena/mln/morpho/tree/all.hh | 16 +- milena/mln/morpho/tree/component_tree.hh | 86 ++- milena/mln/morpho/tree/compute_attribute_image.hh | 278 ++++------ milena/mln/morpho/tree/dual_input_tree.hh | 78 +-- milena/mln/morpho/tree/filter/direct.hh | 35 +- milena/mln/morpho/tree/filter/max.hh | 62 ++- milena/mln/morpho/tree/filter/min.hh | 57 +- milena/mln/morpho/tree/filter/subtractive.hh | 49 +- milena/mln/morpho/tree/impl/dual_hqueue.hh | 585 ++++++++++++--------- milena/mln/morpho/tree/impl/hqueue.hh | 428 +++++++++++++++ milena/mln/morpho/tree/impl/hqueue_fast.hh | 391 ++++++++++++++ milena/mln/morpho/tree/impl/union_find.hh | 174 ++++++ milena/mln/morpho/tree/impl/union_find_fast.hh | 396 ++++++++++++++ milena/mln/morpho/tree/leaf_last.hh | 111 ++++ milena/mln/morpho/tree/propagate_node.hh | 190 +++---- milena/mln/tag/skeleton.hh | 1 + milena/mln/util/hqueues.hh | 32 +- 18 files changed, 2220 insertions(+), 750 deletions(-) create mode 100644 milena/mln/morpho/tree/impl/hqueue.hh create mode 100644 milena/mln/morpho/tree/impl/hqueue_fast.hh create mode 100644 milena/mln/morpho/tree/impl/union_find.hh create mode 100644 milena/mln/morpho/tree/impl/union_find_fast.hh create mode 100644 milena/mln/morpho/tree/leaf_last.hh diff --git a/milena/mln/core/image/all.hh b/milena/mln/core/image/all.hh index ee6a15e..1cd2773 100644 --- a/milena/mln/core/image/all.hh +++ b/milena/mln/core/image/all.hh @@ -40,6 +40,7 @@ // Files. +# include <mln/core/image/attribute_image.hh> # include <mln/core/image/ch_piter.hh> # include <mln/core/image/complex_image.hh> # include <mln/core/image/complex_neighborhood_piter.hh> diff --git a/milena/mln/morpho/tree/all.hh b/milena/mln/morpho/tree/all.hh index d088ea0..c6d93ee 100644 --- a/milena/mln/morpho/tree/all.hh +++ b/milena/mln/morpho/tree/all.hh @@ -30,7 +30,6 @@ /// /// File that includes all morphological tree-related routines. - namespace mln { @@ -46,11 +45,14 @@ namespace mln } // end of namespace mln -# include <mln/morpho/tree/compute_attribute_image.hh> -# include <mln/morpho/tree/compute_parent.hh> # include <mln/morpho/tree/dual_input_tree.hh> -# include <mln/morpho/tree/data.hh> -# include <mln/morpho/tree/max.hh> -# include <mln/morpho/tree/utils.hh> +# include <mln/morpho/tree/component_tree.hh> +# include <mln/morpho/tree/compute_parent.hh +# include <mln/morpho/tree/compute_attribute_image.hh> +# include <mln/morpho/tree/leaf_last.hh> +# include <mln/morpho/tree/propagate_node.hh> + +# include <mln/morpho/tree/filter/all.hh> + -#endif // ! MLN_MORPHO_TREE_ALL_HH +#endif // !MLN_MORPHO_TREE_ALL_HH diff --git a/milena/mln/morpho/tree/component_tree.hh b/milena/mln/morpho/tree/component_tree.hh index d628e98..1fd272b 100644 --- a/milena/mln/morpho/tree/component_tree.hh +++ b/milena/mln/morpho/tree/component_tree.hh @@ -32,8 +32,10 @@ #ifndef MLN_MORPHO_TREE_COMPONENT_TREE_HH # define MLN_MORPHO_TREE_COMPONENT_TREE_HH -# include <mln/data/sort_psites.hh> -# include <mln/morpho/tree/data.hh> +# include <mln/tag/tree.hh> +# include <mln/util/ctree/ctree.hh> +# include <mln/morpho/tree/impl/union_find_fast.hh> +# include <mln/morpho/tree/impl/hqueue_fast.hh> namespace mln { @@ -53,7 +55,7 @@ namespace mln /// template <typename I, typename N> inline - data< I, p_array<mln_psite(I)> > + util::ctree::ctree min_tree(const Image& f, const Neighborhood<N>& nbh); /// Compute a canonized max-tree. @@ -65,15 +67,73 @@ namespace mln /// template <typename I, typename N> inline - data< I, p_array<mln_psite(I)> > + util::ctree::ctree max_tree(const Image& f, const Neighborhood<N>& nbh); # ifndef MLN_INCLUDE_ONLY + namespace internal + { + + template <typename I, typename N> + inline + util::ctree::ctree + max_tree_dispatch(trait::image::quant::any, + const I& f, + const N& nbh) + { + util::ctree::ctree tree = + morpho::tree::impl::generic::union_find_fast(tag::tree::max, f, nbh); + + return tree; + } + + template <typename I, typename N> + inline + util::ctree::ctree + min_tree_dispatch(trait::image::quant::any, + const I& f, + const N& nbh) + { + util::ctree::ctree tree = + morpho::tree::impl::generic::union_find_fast(tag::tree::min, f, nbh); + + return tree; + } + + + template <typename I, typename N> + inline + util::ctree::ctree + max_tree_dispatch(trait::image::quant::low, + const I& f, + const N& nbh) + { + util::ctree::ctree tree = + morpho::tree::impl::hqueue_fast(tag::tree::max, f, nbh); + + return tree; + } + + template <typename I, typename N> + inline + util::ctree::ctree + min_tree_dispatch(trait::image::quant::low, + const I& f, + const N& nbh) + { + util::ctree::ctree tree = + morpho::tree::impl::hqueue_fast(tag::tree::min, f, nbh); + + return tree; + } + + } + template <typename I, typename N> inline - data< I, p_array<mln_psite(I)> > + util::ctree::ctree min_tree(const Image& f_, const Neighborhood<N>& nbh_) { mln_trace("morpho::tree::min_tree"); @@ -84,18 +144,15 @@ namespace mln mln_precondition(f.is_valid()); mln_precondition(nbh.is_valid()); - typedef p_array<mln_psite(I)> S; - typedef data<I,S> tree_t; - - S s = mln::data::sort_psites_decreasing(f); - tree_t tree(f, s, nbh); + util::ctree::ctree tree = + internal::min_tree_dispatch(mln_trait_image_quant(I)(), f, nbh); return tree; } template <typename I, typename N> inline - data< I, p_array<mln_psite(I)> > + util::ctree::ctree max_tree(const Image& f_, const Neighborhood<N>& nbh_) { mln_trace("morpho::tree::max_tree"); @@ -106,11 +163,8 @@ namespace mln mln_precondition(f.is_valid()); mln_precondition(nbh.is_valid()); - typedef p_array<mln_psite(I)> S; - typedef data<I,S> tree_t; - - S s = mln::data::sort_psites_increasing(f); - tree_t tree(f, s, nbh); + util::ctree::ctree tree = + internal::max_tree_dispatch(mln_trait_image_quant(I)(), f, nbh); return tree; } diff --git a/milena/mln/morpho/tree/compute_attribute_image.hh b/milena/mln/morpho/tree/compute_attribute_image.hh index 308a0e2..d27e314 100644 --- a/milena/mln/morpho/tree/compute_attribute_image.hh +++ b/milena/mln/morpho/tree/compute_attribute_image.hh @@ -24,22 +24,20 @@ // 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_ATTRIBUTE_IMAGE_HH -# define MLN_MORPHO_TREE_COMPUTE_ATTRIBUTE_IMAGE_HH - -/// \file +#ifndef COMPUTE_ATTRIBUTE_IMAGE_HH +# define COMPUTE_ATTRIBUTE_IMAGE_HH +/// +/// +/// \brief Compute an attribute on a morphological tree. /// -/// Compute a canonized tree from an image. +/// \todo Specialize for fast image. /// -/// \todo Specialize for low quant (and try fastest). -# include <mln/core/routine/duplicate.hh> -# include <mln/core/concept/image.hh> -# include <mln/morpho/tree/data.hh> -# include <mln/trait/accumulators.hh> -# include <mln/util/pix.hh> -# include <mln/data/fill.hh> +# include <mln/core/concept/tree.hh> +# include <mln/core/concept/accumulator.hh> +# include <mln/core/image/attribute_image.hh> +# include <mln/data/fill.hh> namespace mln { @@ -51,210 +49,140 @@ namespace mln { /** - ** Compute an attribute image using tree with a parent - ** relationship between sites. In the attribute image, the - ** resulting value at a node is the 'sum' of its sub-components - ** value + the attribute value at this node. - ** - ** Warning: \p s translates the ordering related to the - ** "natural" childhood relationship. The parenthood is thus - ** inverted w.r.t. to \p s. + ** Compute an attribute over a tree. ** - ** It is very convenient since all processing upon the parent - ** tree are performed following \p s (in the default "forward" - ** way). ** - ** FIXME: Put it more clearly... + ** \param[in] tree A morphological tree (typically a min or max tree) + ** \param[in] accu An accumulator ** - ** The parent result image verifies: \n - ** - p is root iff parent(p) == p \n - ** - p is a node iff either p is root or f(parent(p)) != f(p). - ** - ** \param[in] a Attribute. - ** \param[in] t Component tree. - ** \param[out] accu_image Optional argument used to store image - ** of attribute accumulator. - ** - ** \return The attribute image. */ - template <typename A, typename T> - mln_ch_value(typename T::function, mln_result(A)) - compute_attribute_image(const Accumulator<A>& a, - const T& t, - mln_ch_value(typename T::function, A)* accu_image = 0); - - - - /** The same as compute_attribute_image but uses the values - ** stored by \p values image instead. - ** - ** \param[in] a Attribute. - ** \param[in] t Component tree. - ** \param[in] values Value image. - ** \param[out] accu_image Optional argument used to store image. - ** - ** \return - */ - template <typename A, typename T, typename V> - mln_ch_value(typename T::function, mln_result(A)) - compute_attribute_image_from(const Accumulator<A>& a, - const T& t, - const Image<V>& values, - mln_ch_value(typename T::function, A)* accu_image = 0); + template <typename T, typename A> + attribute_image<T, mln_result(A)> + compute_attribute_image(const Tree<T>& tree, + const Accumulator<A>& accu); # ifndef MLN_INCLUDE_ONLY - // Take_as_init specialization namespace internal { - template <typename A, typename I, typename P> - void take_as_init (trait::accumulator::when_pix::use_none, A& accu, - const I& input, const P& p) - { - (void)input; - (void)p; - accu.take_as_init(); - } - template <typename A, typename I, typename P> - void take_as_init (trait::accumulator::when_pix::use_pix, A& accu, - const I& input, const P& p) + template <typename T, typename A> + inline + void + take_as_init(trait::accumulator::when_pix::use_none, + const T&, A& accu, + const mln_psite(T)&) { - accu.take_as_init(make::pix(input, p)); + accu.take(); } - template <typename A, typename I, typename P> - void take_as_init (trait::accumulator::when_pix::use_v, A& accu, - const I& input, const P& p) + template <typename T, typename A> + inline + void + take_as_init(trait::accumulator::when_pix::use_pix, + const T& tree, A& accu, + const mln_psite(T)& p) { - accu.take_as_init(input(p)); + accu.take(make::pix(p, tree.f(p))); } - template <typename A, typename I, typename P> - void take_as_init (trait::accumulator::when_pix::use_p, A& accu, - const I& input, const P& p) + + template <typename T, typename A> + inline + void + take_as_init(trait::accumulator::when_pix::use_v, + const T& tree, A& accu, + const mln_psite(T)& p) { - (void) input; - accu.take_as_init(p); + accu.take(tree.f(p)); } - - template <typename A, typename I, typename P> - void take_as_init (A& accu, const I& input, const P& p) + template <typename T, typename A> + inline + void + take_as_init(trait::accumulator::when_pix::use_p, + const T&, A& accu, + const mln_psite(T)& p) { - take_as_init (mln_trait_accumulator_when_pix(A)(), accu, input, p); + accu.take(p); } - - template <typename A, typename T, typename V> - inline - mln_ch_value(typename T::function, mln_result(A)) - compute_attribute_image(const A& a, - const T& t, - const V& values, - mln_ch_value(typename T::function, A)* accu_image = 0) + template <typename T, typename A> + void + take_as_init(const T& tree, A& a, const mln_psite(T)& p) { + take_as_init(mln_trait_accumulator_when_pix(A)(), tree, a, p); + } - typedef typename T::function I; - mln_ch_value(I, A) acc; - initialize(acc, t.f()); + } // end of namespace namespace mln::morpho::tree::internal - { - // Transmit "dynamic data" (state) of 'a' to every values of - // 'acc'. It is usually a no-op (so useless) except for a - // few accumulators, e.g., for accu::stat::rank which has the 'k' - // attribute. - mln::data::fill(acc, a); - } + namespace impl + { - { - // Initialize every attribute with the corresponding pixel. - mln_site_piter(T) p(t); - for_all(p) - take_as_init(acc(p), values, p); - } + namespace generic + { + template <typename T, typename A> + attribute_image<T, mln_result(A)> + compute_attribute_image(const T& tree, const A& accu, attribute_image<T, A>* accu_img = 0) { - mln_up_site_piter(T) p(t); - // Propagate attribute from a site to its parent. - for_all(p) - if (! t.is_root(p)) - acc(t.parent(p)).take(acc(p)); - - // Back-propagate attribute from a node to sites of its - // component. Below, p is a non-node component site and - // parent(p) is a node, that is, the site representative of - // the component p belongs to. - for_all(p) - if (! t.is_a_node(p)) - { - mln_assertion(t.is_a_node(t.parent(p))); - acc(p) = acc(t.parent(p)); - } + typedef attribute_image<T, A> I; + attribute_image<T, A> a(tree); + (void) accu_img; + + // Transmit dynamic data of accumulator (ex: rank filter). + data::fill(a, accu); + + // Initialize. Each node takes its content. + { + mln_fwd_piter(T::domain_t) p(tree.domain()); + for_all(p) + internal::take_as_init(tree, a.element(tree.node_at_(p)), p); + } + + // Transmit to parent. + for (unsigned i = tree.n_nodes() - 1; i > 0; --i) + { + unsigned q = tree.parent_at_(i); + if (q != i) // The current node is not a root. + a.element(q).take(a.element(i)); + } + + attribute_image<T, mln_result(A)> out(tree); + for (int i = 0; i < tree.n_nodes(); i++) + out.element(i) = a.element(i).to_result(); + + return out; } + } // end of namespace mln::morpho::tree::impl::generic - // Store accumulator image. - if (accu_image) - *accu_image = duplicate(acc); - - typedef typename T::function I; - mln_ch_value(I, mln_result(A)) output; - initialize(output, acc); - mln::data::fill(output, acc); - - return output; - } - } + } // end of namespace mln::morpho::tree::impl - // Facade. - - template <typename A, typename T> - inline - mln_ch_value(typename T::function, mln_result(A)) - compute_attribute_image(const Accumulator<A>& a_, - const T& t, - mln_ch_value(typename T::function, A)* accu_image) + // Facades + template <typename T, typename A> + attribute_image<T, mln_result(A)> + compute_attribute_image(const Tree<T>& tree_, const Accumulator<A>& acc) { - mln_trace("morpho::tree::compute_attribute_image"); + trace::entering("mln::morpho::tree::compute_attribute_image"); + const T& tree = exact(tree_); + const A& accu = exact(acc); - mln_ch_value(typename T::function, mln_result(A)) output; - output = internal::compute_attribute_image(exact(a_), t, t.f(), - accu_image); + mln_precondition(tree.is_valid()); - return (output); + attribute_image<T, mln_result(A)> out = impl::generic::compute_attribute_image(tree, accu); + trace::exiting("mln::morpho::tree::compute_attribute_image"); + return out; } - template <typename A, typename T, typename V> - inline - mln_ch_value(typename T::function, mln_result(A)) - compute_attribute_image_from(const Accumulator<A>& a_, - const T& t, - const Image<V>& values, - mln_ch_value(typename T::function, A)* accu_image) - { - mln_trace("morpho::tree::compute_attribute_image_from"); - - - mln_ch_value(typename T::function, mln_result(A)) output; - output = internal::compute_attribute_image(exact(a_), t, exact(values), - accu_image); - - return output; - } - - - - # endif // ! MLN_INCLUDE_ONLY - } // end of namespace mln::morpho::tree - - } // end of namespace mln::morpho + } // end of namespace mln::morpho::tree -} // end of namespace mln + } // end of namespace mln::morpho +} // end of namespace mln -#endif // ! MLN_MORPHO_TREE_COMPUTE_ATTRIBUTE_IMAGE_HH +#endif // !COMPUTE_ATTRIBUTE_IMAGE_HH diff --git a/milena/mln/morpho/tree/dual_input_tree.hh b/milena/mln/morpho/tree/dual_input_tree.hh index 9692a75..50297a9 100644 --- a/milena/mln/morpho/tree/dual_input_tree.hh +++ b/milena/mln/morpho/tree/dual_input_tree.hh @@ -23,17 +23,12 @@ // exception does not however invalidate any other reasons why the // executable file might be covered by the GNU General Public License. -/// \file -/// -/// Compute a canonized component tree from a dual input. - #ifndef MLN_MORPHO_TREE_DUAL_INPUT_TREE_HH # define MLN_MORPHO_TREE_DUAL_INPUT_TREE_HH -# include <mln/data/sort_psites.hh> - -# include <mln/morpho/tree/data.hh> -# include <mln/morpho/tree/impl/dual_union_find.hh> +# include <mln/tag/tree.hh> +# include <mln/util/ctree/ctree.hh> +# include <mln/morpho/tree/impl/union_find_fast.hh> # include <mln/morpho/tree/impl/dual_hqueue.hh> namespace mln @@ -45,67 +40,26 @@ namespace mln namespace tree { - /// Compute the dual input max tree using mask-based connectivity. + /// Compute the dual input max-tree using mask-based connectivity. /// - /// \param[in] f The original image. - /// \param[in] m The connectivity mask. - /// \param[in] nbh The neighborhood of the mask. + /// \param[in] f The input image. + /// \param[in] m The mask image. + /// \param[in] nbh The neighborhood. /// - /// \return The computed tree. + /// \return The corresponding tree structure. /// template <typename I, typename N> inline - data< I, p_array<mln_psite(I)> > + util::ctree::ctree dual_input_max_tree(const Image& f, const Image& m, const Neighborhood<N>& nbh); - # ifndef MLN_INCLUDE_ONLY - namespace internal - { - - template <typename I, typename N> - inline - data< I, p_array<mln_psite(I)> > - dual_input_max_tree_dispatch(trait::image::quant::any, - const I& f, - const I& m, - const N& nbh) - { - typedef p_array<mln_psite(I)> S; - typedef data<I,S> tree_t; - - S s_f = mln::data::sort_psites_increasing(f); - S s_m = mln::data::sort_psites_increasing(m); - - tree_t tree = impl::generic::dual_union_find(f, m, s_f, s_m, nbh); - return tree; - } - - template <typename I, typename N> - inline - data< I, p_array<mln_psite(I)> > - dual_input_max_tree_dispatch(trait::image::quant::low, - const I& f, - const I& m, - const N& nbh) - { - typedef p_array<mln_psite(I)> S; - typedef data<I,S> tree_t; - - tree_t tree = impl::dual_hqueue(f, m, nbh); - return tree; - } - - } // end of namespace mln::morpho::tree::internal - - - // Facades. template <typename I, typename N> inline - morpho::tree::data< I, p_array<mln_psite(I)> > + util::ctree::ctree dual_input_max_tree(const Image& f_, const Image& m_, const Neighborhood<N>& nbh_) @@ -117,22 +71,17 @@ namespace mln const N& nbh = exact(nbh_); mln_precondition(f.is_valid()); - mln_precondition(m.is_valid()); mln_precondition(nbh.is_valid()); - mln_precondition(f.domain() == m.domain()); - typedef p_array<mln_psite(I)> S; - typedef data<I,S> tree_t; + util::ctree::ctree tree = + morpho::tree::impl::dual_hqueue(tag::tree::max, f, m, nbh); tree_t tree = internal::dual_input_max_tree_dispatch(mln_trait_image_quant(I)(), f, m, nbh); - + trace::exiting("morpho::tree::dual_input_max_tree"); return tree; } - - - # endif // ! MLN_INCLUDE_ONLY } // end of namespace mln::morpho::tree @@ -141,5 +90,4 @@ namespace mln } // end of namespace mln - #endif // !MLN_MORPHO_TREE_DUAL_INPUT_TREE_HH diff --git a/milena/mln/morpho/tree/filter/direct.hh b/milena/mln/morpho/tree/filter/direct.hh index 953a06c..4c4833f 100644 --- a/milena/mln/morpho/tree/filter/direct.hh +++ b/milena/mln/morpho/tree/filter/direct.hh @@ -27,7 +27,9 @@ # define MLN_MORPHO_TREE_FILTER_DIRECT_HH # include <mln/core/concept/function.hh> -# include <mln/morpho/tree/data.hh> +# include <mln/core/image/attribute_image.hh> +# include <mln/morpho/tree/propagate_node.hh> + /** ** \file mln/morpho/tree/filter/direct.hh @@ -51,36 +53,39 @@ namespace mln /** ** Direct non-pruning strategy. A node is removed if it does - ** not verify the predicate. The sub-components remain intact. + ** not verify the predicate. Its pixels are lowered in gray + ** level to the highest ancestor which meets the criterion, + ** and while its descendants are unaffected. ** - ** \param[in] tree Component tree. - ** \param[out] f_ Image to filter. + ** \param[in,out] attr The attribute image. ** \param[in] pred_ Filtering criterion. */ - template <typename T, typename F, typename P> + template <typename T, typename V, typename P> inline void - direct(const T& tree, Image<F>& f_, const Function_v2b& pred_); + direct(attribute_image<T,V>& attr, const Function_v2b& pred_); # ifndef MLN_INCLUDE_ONLY - template <typename T, typename F, typename P> + template <typename T, typename V, typename F> inline void - direct(const T& tree, Image<F>& f_, const Function_v2b& pred_) + direct(attribute_image<T,V>& attr, const Function_v2b<F>& pred_) { - F& f = exact(f_); - const P& pred = exact(pred_); - mln_trace("mln::morpho::tree::filter::direct"); - mln_dn_node_piter(T) n(tree); - for_all(n) - if (!pred(n)) - f(n) = f(tree.parent(n)); + typedef attribute_image<T,V> A; + + const F& pred = exact(pred_); + const T& tree = attr.tree(); + + mln_fwd_piter(A) node(attr.domain()); + for_all(node) + if (!pred(node)) + attr(node) = attr(tree.parent(node)); } diff --git a/milena/mln/morpho/tree/filter/max.hh b/milena/mln/morpho/tree/filter/max.hh index 7feed02..b6b6002 100644 --- a/milena/mln/morpho/tree/filter/max.hh +++ b/milena/mln/morpho/tree/filter/max.hh @@ -27,14 +27,16 @@ # define MLN_MORPHO_TREE_FILTER_MAX_HH # include <mln/core/concept/function.hh> -# include <mln/morpho/tree/data.hh> +# include <mln/core/image/attribute_image.hh> +# include <mln/morpho/tree/propagate_node.hh> /** ** \file mln/morpho/tree/filter/max.hh ** ** \brief Filtering with max strategy. ** -** +** See comments in min filter documentation. +** FIXME: it is possible to make it in one pass ! */ namespace mln @@ -54,51 +56,59 @@ namespace mln ** children are removed or if it does not verify the predicate ** \p pred_. ** - ** \param[in] tree Component tree. - ** \param[out] f_ Image to filter. + ** \param[in,out] attr The attribute image. ** \param[in] pred_ Filtering criterion. */ - template <typename T, typename F, typename P> + template <typename T, typename V, typename P> inline void - max(const T& tree, Image<F>& f_, const Function_v2b& pred_); - + max(attribute_image<T,V>& attr, const Function_v2b& pred_); # ifndef MLN_INCLUDE_ONLY - template <typename T, typename F, typename P> + template <typename T, typename V, typename P> inline void - max(const T& tree, Image<F>& f_, const Function_v2b& pred_) + max(attribute_image<T,V>& attr, const Function_v2b& pred_) { - F& f = exact(f_); - const P& pred = exact(pred_); - mln_trace("mln::morpho::tree::filter::max"); - mln_ch_value(F, bool) mark; - initialize(mark, f); - mln::data::fill(mark, true); + typedef attribute_image<T,V> A; + const P& pred = exact(pred_); + const T& tree = attr.tree(); + + typedef mln_ch_value(A, char) M; + M marker; + initialize(marker, attr); + mln::data::fill(marker, true); + // 1st pass up. { - mln_up_node_piter(T) n(tree); - for_all(n) - if (!mark(n)) - mark(tree.parent(n)) = false; - else if (pred(n)) + mln_bkd_piter(M) node(marker.domain()); + for_all(node) + if (!marker(node)) + marker(tree.parent(node)) = false; + else if (pred(node)) { - mark(tree.parent(n)) = false; - mark(n) = false; + marker(tree.parent(node)) = false; + marker(node) = false; } } + // 2nd pass down: propagation. { - mln_dn_node_piter(T) n(tree); - for_all(n) - if (mark(n)) - f(n) = f(tree.parent(n)); + for (int i = 0; i < tree.n_nodes(); ++i) + { + mln_invariant(tree.has_index(i)); + mln_psite(A) n(tree, i); + if (marker(n)) + { + attr(n) = attr(tree.parent(n)); + i += propagate_node_to_descendants(attr, n, attr(n)); + } + } } } diff --git a/milena/mln/morpho/tree/filter/min.hh b/milena/mln/morpho/tree/filter/min.hh index 14e7ee1..fa11f6f 100644 --- a/milena/mln/morpho/tree/filter/min.hh +++ b/milena/mln/morpho/tree/filter/min.hh @@ -27,7 +27,8 @@ # define MLN_MORPHO_TREE_FILTER_MIN_HH # include <mln/core/concept/function.hh> -# include <mln/morpho/tree/data.hh> +# include <mln/core/image/attribute_image.hh> +# include <mln/morpho/tree/propagate_node.hh> /** @@ -52,45 +53,55 @@ namespace mln /** - ** Min pruning strategy. A node is removed iif its parent is + ** Min pruning strategy. A node is removed iff its parent is ** removed or if it does not verify the predicate \p pred_. ** - ** \param[in] tree Component tree. - ** \param[out] f_ Image to filter. + ** \param[in,out] attr The attribute image. ** \param[in] pred_ Filtering criterion. */ - template <typename T, typename F, typename P> + template <typename T, typename V, typename F> inline void - min(const T& tree, Image<F>& f_, const Function_v2b& pred_); + min(attribute_image<T,V>& attr, const Function_v2b<F>& pred); # ifndef MLN_INCLUDE_ONLY - template <typename T, typename F, typename P> + template <typename T, typename V, typename F> inline void - min(const T& tree, Image<F>& f_, const Function_v2b& pred_) + min(attribute_image<T,V>& attr, const Function_v2b<F>& pred_) { - F& f = exact(f_); - const P& pred = exact(pred_); - mln_trace("mln::morpho::tree::filter::min"); - mln_ch_value(F, bool) mark; - initialize(mark, f); - mln::data::fill(mark, false); - - mln_dn_node_piter(T) n(tree); - for_all(n) - if (mark(tree.parent(n)) || !pred(n)) - { - f(n) = f(tree.parent(n)); - mark(n) = true; - } - + typedef attribute_image<T,V> A; + + const F& pred = exact(pred_); + const T& tree = attr.tree(); + + // Ce qui devrait être ! + // mln_fwd_piter(A) n(attr); + // for_all(n) + // if (!pred(n)) + // { + // data::fill_with_value(attr | tree.desc(n), attr(n)); + // n.go_to_brother(); + // } + + // En attendant que le morpher subimage soit spécialisé, + // on joue avec les indexes. + for (int i = 0; i < tree.n_nodes(); ++i) + { + mln_invariant(tree.has_index(i)); + mln_psite(A) n(tree, i); + if (!pred(n)) + { + attr(n) = attr(tree.parent(n)); + i += propagate_node_to_descendants(attr, n, attr(n)); + } + } } # endif // ! MLN_INCLUDE_ONLY diff --git a/milena/mln/morpho/tree/filter/subtractive.hh b/milena/mln/morpho/tree/filter/subtractive.hh index 8ab2eb8..acda41f 100644 --- a/milena/mln/morpho/tree/filter/subtractive.hh +++ b/milena/mln/morpho/tree/filter/subtractive.hh @@ -27,10 +27,8 @@ # define MLN_MORPHO_TREE_FILTER_SUBTRACTIVE_HH # include <mln/core/concept/function.hh> -# include <mln/fun/ops.hh> - -# include <mln/morpho/tree/data.hh> -# include <mln/morpho/tree/propagate_if.hh> +# include <mln/core/image/attribute_image.hh> +# include <mln/morpho/tree/propagate_node.hh> /** ** \file mln/morpho/tree/filter/subtractive.hh @@ -57,44 +55,57 @@ namespace mln ** does not verify the predicate. The sub-components values ** are set to the value of the removed component. ** - ** \param[in] tree Component tree. - ** \param[out] f_ Image to filter. + ** \param[in] ori The values as an attribute image. ** \param[in] pred_ Filtering criterion. + ** \return A copy of \p ori filtered with the subtractive strategy. */ - template <typename T, typename F, typename P> + template <typename T, typename V, typename P> inline - void - subtractive(const T& tree, Image<F>& f_, const Function_v2b& pred_); - - + attribute_image<T, V> + subtractive(const attribute_image<T,V>& ori, const Function_v2b& pred_); # ifndef MLN_INCLUDE_ONLY - template <typename T, typename F, typename P> + template <typename T, typename V, typename F> inline - void - subtractive(const T& tree, Image<F>& f_, const Function_v2b& pred_) + attribute_image<T, V> + subtractive(const attribute_image<T,V>& ori, const Function_v2b<F>& pred_) { - F& f = exact(f_); - const P& pred = exact(pred_); - mln_trace("mln::morpho::tree::filter::subtractive"); + typedef attribute_image<T,V> A; + + const F& pred = exact(pred_); + const T& tree = ori.tree(); - morpho::tree::propagate_if(tree, f, morpho::tree::desc_propagation (), !pred); + mln_precondition(ori.is_valid()); - mln_up_node_piter(T) n(tree); + A f; + initialize(f, ori); + + // Fixme: introduce mln_root_piter... + // and traverse all roots, not just the first one. + mln_psite(A) root = util::ctree::node<T>(tree, 0); + f(root) = ori(root); + + mln_piter(A) n(ori.domain()); for_all(n) if (!pred(n)) f(n) = f(tree.parent(n)); + else + f(n) = f(tree.parent(n)) + ori(n) - ori(tree.parent(n)); + return f; } # endif // ! MLN_INCLUDE_ONLY } // end of namespace mln::morpho::tree::filter + } // end of namespace mln::morpho::tree + } // end of namespace mln::morpho + } // end of namespace mln #endif // ! MLN_MORPHO_TREE_FILTER_SUBTRACTIVE_HH diff --git a/milena/mln/morpho/tree/impl/dual_hqueue.hh b/milena/mln/morpho/tree/impl/dual_hqueue.hh index bd892eb..91f1c43 100644 --- a/milena/mln/morpho/tree/impl/dual_hqueue.hh +++ b/milena/mln/morpho/tree/impl/dual_hqueue.hh @@ -1,4 +1,4 @@ -// Copyright (C) 2008, 2009, 2013 EPITA Research and Development +man // Copyright (C) 2008, 2009, 2013 EPITA Research and Development // Laboratory (LRDE). // // This file is part of Olena. @@ -33,31 +33,19 @@ /// This implementation is based on P. Salembier algorithm using /// hierachical queues. This implies a low-quantized input image so /// that the number of queues is limited. -/// -/// TODO: Think about how to extend f domain in a more -/// generic way. The actual implementation doubles the size of the -/// first dimension. It implies a boxed domain. -/// -/// TODO: Use the less functor. The actual implementation is for max-tree. -/// -/// TODO: During the canonization pass, we build the tree site set -/// from the sorted site set of f, so that we compute twice f -/// histogram (can be avoided). -# include <mln/data/sort_psites.hh> +# include <mln/util/ctree/ctree.hh> # include <mln/data/fill.hh> +# include <mln/extension/fill.hh> +# include <mln/extension/adjust.hh> # include <mln/geom/nsites.hh> -# include <mln/geom/translate.hh> -# include <mln/morpho/tree/data.hh> # include <mln/util/hqueues.hh> -# include <mln/util/ord.hh> # include <mln/value/value_array.hh> # include <mln/value/set.hh> - # include <mln/util/timer.hh> namespace mln @@ -80,317 +68,404 @@ namespace mln /// /// \return The tree structure. /// - template <typename I, typename N> - inline - data<I, p_array<mln_psite(I)> > - dual_hqueue(const Image& f, + template <typename T, typename I, typename N> + util::ctree::ctree + dual_hqueue(const tag::tree::tree_t<T>&, + const Image& f, const Image& m, const Neighborhood<N>& nbh); + } // end of namespace mln::morpho::tree::impl # ifndef MLN_INCLUDE_ONLY - namespace internal + namespace impl { - template <typename I, typename N, class E> - struct shared_flood_args + + template <typename I, typename N, typename E> + struct flooder_base_ : Object<E> { - typedef mln_psite(I) P; + typedef unsigned P; typedef mln_value(I) V; - typedef p_array S; + // Constructor. + flooder_base_(const I& f_, const I& m_, const N& nbh_); + + // Returned values. + mln_ch_value(I, unsigned) map; + std::vector location; + std::vector<V> values; + std::vector parent; + std::vector<unsigned> area; + unsigned nnode; + + + protected: + enum { + nvalues = mln_card(mln_value(I)) + }; + + + // Recursive function that floods. Canevas function. + int flood(int h_idx); + + // HLevel comparaison. To be specialized for min/max tree. + bool hlevel_less(int h_idx1, int h_idx2); + + // Parent attachment function. To be specialized for min/max tree. + int attach_parent(int h_idx); + + // Data. + // \{ const I& f; const I& m; const N& nbh; - mln_ch_value(I, P)& parent; - // Aux data - util::hqueues<P, V>& hqueues; - const E& extend; // site -> site functor. + // Auxiliary data. + util::hqueues<unsigned, V> hqueues; + value::set<V> vset; + util::array<int> dp; + unsigned n_nbhs; + + mln_ch_value(I, bool) deja_vu; value::value_array<V, bool> is_node_at_level; value::value_array<V, P> node_at_level; - mln_ch_value(I, bool) deja_vu; - const value::set<V>& vset; - - shared_flood_args(const I& f_, - const I& m_, - const N& neigb_, - mln_ch_value(I, P)& parent_, - util::hqueues<mln_psite(I), V>& hqueues_, - const E& extend_) - : f (f_), - m (m_), - nbh (neigb_), - parent (parent_), - hqueues (hqueues_), - extend (extend_), - is_node_at_level (false), - vset (hqueues.vset()) - { - initialize(deja_vu, f); - mln::data::fill(deja_vu, false); - } + unsigned loc; + // \} }; - template <typename I> - inline - histo::array<mln_value(I)> - compute_histo(const I& f, const I& m, mln_value(I)& hmin, mln_psite(I)& pmin) - { - histo::array<mln_value(I)> hm = histo::compute(m); - const histo::array<mln_value(I)> hf = histo::compute(f); - - { // Retrieve hmin. - unsigned i = 0; - while (hm[i] == 0) - ++i; - hmin = hm.vset()[i]; - } + template <typename T, typename I, typename N> + struct flooder; - // Merge histograms. - for (unsigned i = 0; i < hm.nvalues(); ++i) - hm[i] += hf[i]; + template <typename I, typename N> + struct flooder<tag::tree::max_t, I, N> : + flooder_base_< I, N, flooder<tag::tree::max_t, I, N> > + { + typedef mln_value(I) V; + typedef flooder_base_< I, N, flooder<tag::tree::max_t, I, N> > super_; - // Retrieve pmin. - mln_piter(I) p(m.domain()); - for (p.start(); m(p) != hmin; p.next()) - ; - mln_assertion(p.is_valid()); - pmin = p; + // Constructor. + flooder(const I& f, const I& m, const N& nbh); - return hm; - } + // HLevel comparaison. + bool hlevel_less_(int h_idx1, int h_idx2); - // Site -> site functor: give for all p in Domain(f), its - // equivalence in the extended domain. - // TODO: make it generic. It works only on boxed domain. - template <typename I> - struct extend - { - extend(const mln_psite(I)::delta& dp) - : dp_ (dp) - { - } + // Parent attachment function. + int attach_parent_(int h_idx); - mln_psite(I) operator() (const mln_psite(I)& p) const - { - return p + dp_; - } + public: + using super_::parent; + using super_::area; + using super_::location; - private: - const mln_psite(I)::delta dp_; + protected: + using super_::is_node_at_level; + using super_::node_at_level; + using super_::vset; + using super_::loc; + using super_::hqueues; }; - } // end of namespace mln::morpho::tree::internal + template <typename I, typename N> + struct flooder<tag::tree::min_t, I, N> : + flooder_base_< I, N, flooder<tag::tree::min_t, I, N> > + { + typedef mln_value(I) V; + typedef flooder_base_< I, N, flooder<tag::tree::min_t, I, N> > super_; - namespace impl - { + // Constructor. + flooder(const I& f, const I& m, const N& nbh); - template <typename I, typename N, typename E> - unsigned - flood(internal::shared_flood_args<I, N, E>& args, const unsigned h_idx) - { - mln_assertion(args.is_node_at_level[h_idx]); + // HLevel comparaison. + bool hlevel_less_(int h_idx1, int h_idx2); - while (!args.hqueues[h_idx].empty()) - { - mln_psite(I) p = args.hqueues[h_idx].pop_front(); - unsigned p_idx = args.vset.index_of(args.f(p)); - - if (p_idx != h_idx) - { // Intensity mismatch: irregular case. - mln_psite(I) pext = args.extend(p); - args.parent(pext) = args.node_at_level[h_idx]; - - if (p_idx > h_idx) // Singleton with parent at h. - args.parent(p) = args.node_at_level[h_idx]; - else - { - if (!args.is_node_at_level[p_idx]) - { - args.is_node_at_level[p_idx] = true; - args.node_at_level[p_idx] = p; - } - } - } + // Parent attachment function. + unsigned attach_parent_(int h_idx); - if (p_idx <= h_idx) - { - if (!args.f.domain().has(args.node_at_level[p_idx]) || - util::ord_strict(p, args.node_at_level[p_idx])) - { // Regular case but a representative provided by the extension. - args.parent(args.node_at_level[p_idx]) = p; - args.node_at_level[p_idx] = p; - //args.parent(p) = p; - } - args.parent(p) = args.node_at_level[p_idx]; - } + public: + using super_::parent; + using super_::area; + using super_::location; + protected: + using super_::is_node_at_level; + using super_::node_at_level; + using super_::vset; + using super_::loc; + using super_::hqueues; + }; - // Process the neighbors - mln_niter(N) n(args.nbh, p); - for_all(n) - if (args.f.domain().has(n) && !args.deja_vu(n)) - { - unsigned mn = args.vset.index_of(args.m(n)); - unsigned fn = args.vset.index_of(args.f(n)); - args.hqueues[mn].push(n); - args.deja_vu(n) = true; - - mln_psite(I) ext = args.extend(n); - // Create a node at c. - { - mln_psite(I) node = (fn == mn) ? n : ext; - if (!args.is_node_at_level[mn]) - { - args.is_node_at_level[mn] = true; - args.node_at_level[mn] = node; - } - } - - while (mn > h_idx) - mn = flood(args, mn); - } - } - // Retrieve dad. - args.is_node_at_level[h_idx] = false; - unsigned c = h_idx; - while (c > 0 && !args.is_node_at_level[c]) - --c; + template <typename I, typename N, typename E> + inline + bool + flooder_base_<I, N, E>::hlevel_less(int h_idx1, int h_idx2) + { + E& obj = exact(*this); + return obj.hlevel_less_(h_idx1, h_idx2); + } - mln_psite(I) x = args.node_at_level[h_idx]; - if (c > 0) - args.parent(x) = args.node_at_level[c]; - else - args.parent(x) = x; + template <typename I, typename N, typename E> + inline + int + flooder_base_<I, N, E>::attach_parent(int h_idx) + { + E& obj = exact(*this); + return obj.attach_parent_(h_idx); + } - return c; + template <typename I, typename N> + inline + flooder<tag::tree::max_t, I, N>::flooder(const I& f_, const I& m_, const N& nbh_) + : flooder_base_<I, N, flooder<tag::tree::max_t, I, N> >(f_, m_, nbh_) + { } template <typename I, typename N> inline - data< I, p_array<mln_psite(I)> > - dual_hqueue(const Image& f_, - const Image& m_, - const Neighborhood<N>& neibh_) + flooder<tag::tree::min_t, I, N>::flooder(const I& f_, const I& m_, const N& nbh_) + : flooder_base_<I, N, flooder<tag::tree::min_t, I, N> >(f_, m_, nbh_) { - mln_trace("mln::morpho::tree::impl::dual_hqueue"); + } - const I& f = exact(f_); - const I& m = exact(m_); - const N& nbh = exact(neibh_); + template <typename I, typename N> + inline + bool + flooder<tag::tree::max_t, I, N>::hlevel_less_(int h_idx1, int h_idx2) + { + return h_idx1 < h_idx2; + } - typedef mln_psite(I) P; - typedef p_array<mln_psite(I)> S; + template <typename I, typename N> + inline + bool + flooder<tag::tree::min_t, I, N>::hlevel_less_(int h_idx1, int h_idx2) + { + return h_idx2 < h_idx1; + } - util::timer tm; - tm.start(); + template <typename I, typename N> + inline + int + flooder<tag::tree::max_t, I, N>::attach_parent_(int h_idx) + { + mln_assertion(h_idx >= 0); + mln_assertion(is_node_at_level[h_idx]); - // Histo. - mln_psite(I) pmin; - mln_value(I) hmin; - const histo::array<mln_value(I)> histo = internal::compute_histo(f, m, hmin, pmin); - util::hqueues<P, mln_value(I)> hqueues(histo); - mln_psite(I)::delta dp(literal::zero); - mln_domain(I) d_ext = f.domain(); - mln_domain(I) d = f.domain(); + unsigned x = node_at_level[h_idx]; + int c = h_idx - 1; - // Extend the domain. - dp[0] = d.pmax()[0] - d.pmin()[0] + 1; - d.pmax() += dp; - d_ext.pmin() += dp; - d_ext.pmax() += dp; + is_node_at_level[h_idx] = false; + while (c >= 0 && !is_node_at_level[c]) + --c; - // Data. - mln_concrete(I) fext; - mln_ch_value(I, P) parent; - p_array<mln_psite(I)> s; - - // Initialization. - fext = geom::translate(m, dp.to_vec(), f, d); - initialize(parent, fext); - s.reserve(geom::nsites(fext)); - - // Process. - internal::extend extend(dp); - internal::shared_flood_args< I, N, internal::extend > - args(f, m, nbh, parent, hqueues, extend); - - unsigned r = args.vset.index_of(hmin); - args.deja_vu(pmin) = true; - args.hqueues[r].push(pmin); - args.node_at_level[r] = (f(pmin) == hmin) ? pmin : extend(pmin); - args.is_node_at_level[r] = true; - flood(args, r); - - // Attach the nodes under hmin. - unsigned i = r; - do + if (c >= 0) { - if (args.is_node_at_level[i]) - { - parent(args.node_at_level[r]) = args.node_at_level[i]; - r = i; - } + unsigned p = node_at_level[c]; + parent[x] = p; + area[p] += area[x] + 1; } - while (i-- > 0); - parent(args.node_at_level[r]) = args.node_at_level[r]; //root + else // root case. + parent[x] = x; - // Canonization and make tree site set. - { - mln_ch_value(I, bool) deja_vu(d_ext); - mln::data::fill(deja_vu, false); + location[x] = loc++; + return c; + } - p_array<mln_psite(I)> s_f = mln::data::sort_psites_increasing(f); - mln_fwd_piter(S) p(s_f); // Forward. - for_all(p) + template <typename I, typename N, typename E> + flooder_base_<I, N, E>::flooder_base_(const I& f_, const I& m_, const N& nbh_) + : f (f_), m(m_), nbh (nbh_), is_node_at_level (false) + { + typedef mln_value(I) V; + + unsigned pmin_offset; + V vmin; + + // Allocate hierarchical queues and retrieve the starting point + { + util::array< unsigned > h(nvalues, 0); + + pmin_offset = m.index_of_point(m.domain().pmin()); + vmin = m.element(pmin_offset); + + mln_fwd_pixter(const I) pxl(m); + for_all(pxl) + { + ++h[pxl.val()]; + if (hlevel_less(pxl.val(), vmin)) + { + vmin = pxl.val(); + pmin_offset = pxl.offset(); + } + } + + for (unsigned i = 0; i < nvalues; ++i) + hqueues[i].reserve(h[i]); + } + + // Initialize aux data + { + dp = offsets_wrt(f, nbh); + n_nbhs = dp.nelements(); + vset = value::set<V>::the(); + + extension::adjust(f, nbh); + extension::adjust(m, nbh); + + initialize(deja_vu, f); + initialize(map, f); + data::fill(deja_vu, false); + extension::fill(deja_vu, true); + + unsigned nsites = geom::nsites(f); + parent.resize(2 * nsites); + location.resize(2 * nsites); + area.resize(2 * nsites, 0); + values.resize(2 * nsites); + + nnode = 0; + loc = 0; + } + + // Start flooding + unsigned hmin = vset.index_of(vmin); + unsigned fmin = vset.index_of(f.element(pmin_offset)); + std::cout << vmin << std::endl; + hqueues[hmin].push(pmin_offset); + deja_vu.element(pmin_offset) = true; + values[nnode] = vmin; + node_at_level[fmin] = nnode++; + is_node_at_level[fmin] = true; + if (hmin != fmin) + { + values[nnode] = f.element(pmin_offset); + node_at_level[hmin] = nnode++; + is_node_at_level[hmin] = true; + } + int c = flood(hmin); + while (c != -1) // There still are nodes under minimal mask level. + c = attach_parent(c); + mln_assertion(c == -1); + } + + template <typename I, typename N, typename E> + int + flooder_base_<I, N, E>::flood(int h_idx) + { + mln_assertion(h_idx >= 0); + mln_assertion(is_node_at_level[h_idx]); + + while (!hqueues[h_idx].empty()) { - P x = p; - P q = parent(p); + unsigned p = hqueues[h_idx].pop_front(); + int p_idx = vset.index_of(f.element(p)); + mln_assertion(vset.index_of(m.element(p)) == (unsigned)h_idx); + //mln_assertion(is_node_at_level[p_idx]); - // Case: l: m <---- m <---- f - // Or - // Case l1: m <----- f impossible. - // | - // l2: m - mln_assertion(!(d_ext.has(q) && fext(p) == fext(q) && d_ext.has(parent(q)) && q != parent(q))); - while (d_ext.has(q) && !deja_vu(q) && (fext(q) != fext(parent(q)) || q == parent(q))) + if (h_idx < p_idx) // FIXME: max tree only { - s.append(q); - deja_vu(q) = true; - x = q; - q = parent(q); + // Singleton + int par_i = node_at_level[h_idx]; + int self_i = nnode++; // Create the node. + map.element(p) = self_i; + values[self_i] = m.element(p); + area[self_i] = 1; + parent[self_i] = par_i; + location[self_i] = loc++; + area[par_i]++; } + else + map.element(p) = node_at_level[p_idx]; - if (d_ext.has(q) && fext(q) == fext(parent(q)) && q != parent(q)) + // Process the neighbors + for (unsigned j = 0; j < n_nbhs; ++j) { - q = (parent(x) = parent(q)); - mln_assertion(f.domain().has(q)); + unsigned n = p + dp[j]; + + if (!deja_vu.element(n)) + { + unsigned n_hidx = vset.index_of(m.element(n)); + unsigned n_fidx = vset.index_of(f.element(n)); + hqueues[n_hidx].push(n); + deja_vu.element(n) = true; + + if (!is_node_at_level[n_hidx]) + { + values[nnode] = (m.element(n)); + node_at_level[n_hidx] = nnode++; + is_node_at_level[n_hidx] = true; + } + if (!is_node_at_level[n_fidx] && n_fidx < n_hidx) + { + values[nnode] = (f.element(n)); + node_at_level[n_fidx] = nnode++; + is_node_at_level[n_fidx] = true; + } + + while (hlevel_less(h_idx, n_hidx)) + n_hidx = flood(n_hidx); + } } + } - if (fext(q) == fext(parent(q))) - parent(x) = parent(q); + return attach_parent(h_idx); + } - s.append(p); + template <typename T, typename I, typename N> + inline + util::ctree::ctree + dual_hqueue(const tag::tree::tree_t<T>&, + const Image& f_, + const Image& m_, + const Neighborhood<N>& nbh_) + { + trace::entering("mln::morpho::tree::impl::hqueue"); + const I& f = exact(f_); + const I& m = exact(m_); + const N& nbh = exact(nbh_); - mln_assertion((q = parent(p)) == parent(q) || fext(q) != fext(parent(q))); - } + mln_precondition(f.is_valid()); + mln_precondition(m.is_valid()); + mln_precondition(nbh.is_valid()); - } + // Process + impl::flooder<T, I, N> args(f, m, nbh); - data<I, S> tree(fext, parent, s); + // Reserve + util::ctree::ctree tree; + tree.reserve(f, args.nnode); + // Set values + { + mln_piter(I) p(f.domain()); + for_all(p) + { + unsigned idx = args.map(p); + unsigned loc = args.nnode - args.location[idx] - 1; + tree.node_at_(p) = loc; + } + + for (int idx = 0; idx < args.nnode; ++idx) + { + unsigned loc = args.nnode - args.location[idx] - 1; + + tree.parent_at_(loc) = args.nnode - args.location[args.parent[idx]] - 1; + tree.f_at_(loc) = args.values[idx]; + tree.length_at_(loc) = args.area[idx]; + } + } + trace::exiting("mln::morpho::tree::impl::hqueue"); return tree; } - } // end of namespace mln::morpho::tree::impl + } // end of namespace mln::morpho::tree::impl + # endif // ! MLN_INCLUDE_ONLY diff --git a/milena/mln/morpho/tree/impl/hqueue.hh b/milena/mln/morpho/tree/impl/hqueue.hh new file mode 100644 index 0000000..cfe0f4b --- /dev/null +++ b/milena/mln/morpho/tree/impl/hqueue.hh @@ -0,0 +1,428 @@ +// Copyright (C) 2008, 2009 EPITA Research and Development Laboratory (LRDE) +// +// This file is part of Olena. +// +// Olena is free software: you can redistribute it and/or modify it under +// the terms of the GNU General Public License as published by the Free +// Software Foundation, version 2 of the License. +// +// Olena 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 Olena. If not, see <http://www.gnu.org/licenses/>. +// +// As a special exception, you may use this file as part of a free +// software project 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_IMPL_HQUEUE_HH +# define MLN_MORPHO_TREE_IMPL_HQUEUE_HH + +# include <mln/util/ctree/ctree.hh> +# include <mln/util/hqueues.hh> +# include <mln/value/value_array.hh> +# include <mln/geom/nsites.hh> + +# include <mln/histo/array.hh> +# include <mln/histo/compute.hh> +# include <mln/data/fill.hh> + +namespace mln +{ + + namespace morpho + { + + namespace tree + { + + namespace impl + { + + template <typename T, typename I, typename N> + inline + util::ctree::ctree + hqueue(const tag::tree::tree_t<T>&, const Image& f, const Neighborhood<N>& nbh); + + } // end of namespace mln::morpho::tree::impl + +# ifndef MLN_INCLUDE_ONLY + + namespace internal + { + + template <typename T, typename I> + struct op_psite_less; + + template <typename I> + struct op_psite_less< tag::tree::max_t, I> + { + op_psite_less(const I& f) : f_(f) {} + + bool operator() (const mln_psite(I)& lhs, const mln_psite(I)& rhs) const + { + return util::ord_strict(f_(lhs), f_(rhs)); + } + + private: + const I& f_; + }; + + template <typename I> + struct op_psite_less< tag::tree::min_t, I> + { + op_psite_less(const I& f) : f_(f) {} + + bool operator() (const mln_psite(I)& lhs, const mln_psite(I)& rhs) const + { + return util::ord_strict(f_(rhs), f_(lhs)); + } + + private: + const I& f_; + }; + + } + + + namespace impl + { + + + template <typename I, typename N, typename E> + struct flooder_base_ : Object<E> + { + typedef unsigned P; + typedef mln_value(I) V; + + // Constructor. + flooder_base_(const I& f_, const N& nbh_); + + // Returned values. + mln_ch_value(I, unsigned) map; + std::vector location; + std::vector parent; + std::vector<unsigned> area; + unsigned n_node; + + + protected: + // Recursive function that floods. Canevas function. + unsigned flood(const unsigned h_idx); + + // HLevel comparaison. To be specialized for min/max tree. + bool hlevel_less(unsigned h_idx1, unsigned h_idx2); + + // Parent attachment function. To be specialized for min/max tree. + unsigned attach_parent(unsigned h_idx); + + // Data. + // \{ + const I& f; + const N& nbh; + + // Auxiliary data. + util::hqueues<mln_psite(I), V> hqueues; + value::set<V> vset; + + mln_ch_value(I, bool) deja_vu; + value::value_array<V, bool> is_node_at_level; + value::value_array<V, P> node_at_level; + unsigned loc; + // \} + }; + + template <typename T, typename I, typename N> + struct flooder; + + template <typename I, typename N> + struct flooder<tag::tree::max_t, I, N> : + flooder_base_< I, N, flooder<tag::tree::max_t, I, N> > + { + typedef mln_value(I) V; + typedef flooder_base_< I, N, flooder<tag::tree::max_t, I, N> > super_; + + // Constructor. + flooder(const I& f_, const N& nbh_); + + // HLevel comparaison. + bool hlevel_less_(unsigned h_idx1, unsigned h_idx2); + + // Parent attachment function. + unsigned attach_parent_(unsigned h_idx); + + public: + using super_::parent; + using super_::area; + using super_::location; + + protected: + using super_::is_node_at_level; + using super_::node_at_level; + using super_::vset; + using super_::loc; + }; + + template <typename I, typename N> + struct flooder<tag::tree::min_t, I, N> : + flooder_base_< I, N, flooder<tag::tree::min_t, I, N> > + { + typedef mln_value(I) V; + typedef flooder_base_< I, N, flooder<tag::tree::min_t, I, N> > super_; + + // Constructor. + flooder(const I& f_, const N& nbh_); + + // HLevel comparaison. + bool hlevel_less_(unsigned h_idx1, unsigned h_idx2); + + // Parent attachment function. + unsigned attach_parent_(unsigned h_idx); + + public: + using super_::parent; + using super_::area; + using super_::location; + + protected: + using super_::is_node_at_level; + using super_::node_at_level; + using super_::vset; + using super_::loc; + }; + + + template <typename I, typename N, typename E> + inline + bool + flooder_base_<I, N, E>::hlevel_less(unsigned h_idx1, unsigned h_idx2) + { + E& obj = exact(*this); + return obj.hlevel_less_(h_idx1, h_idx2); + } + + template <typename I, typename N, typename E> + inline + unsigned + flooder_base_<I, N, E>::attach_parent(unsigned h_idx) + { + E& obj = exact(*this); + return obj.attach_parent_(h_idx); + } + + template <typename I, typename N> + inline + flooder<tag::tree::max_t, I, N>::flooder(const I& f_, const N& nbh_, + const histo::array< mln_value(I) >& histo_) + : flooder_base_<I, N, flooder<tag::tree::max_t, I, N> >(f_, nbh_, histo_) + { + } + + template <typename I, typename N> + inline + flooder<tag::tree::min_t, I, N>::flooder(const I& f_, const N& nbh_, + const histo::array<mln_value(I)>& histo_) + : flooder_base_<I, N, flooder<tag::tree::min_t, I, N> >(f_, nbh_, histo_) + { + } + + template <typename I, typename N> + inline + bool + flooder<tag::tree::max_t, I, N>::hlevel_less_(unsigned h_idx1, unsigned h_idx2) + { + return h_idx1 < h_idx2; + } + + template <typename I, typename N> + inline + bool + flooder<tag::tree::min_t, I, N>::hlevel_less_(unsigned h_idx1, unsigned h_idx2) + { + return h_idx2 < h_idx1; + } + + template <typename I, typename N> + inline + unsigned + flooder<tag::tree::max_t, I, N>::attach_parent_(unsigned h_idx) + { + unsigned c = h_idx; + while (c > 0 && !is_node_at_level[c]) + --c; + + unsigned x = node_at_level[h_idx]; + if (is_node_at_level[c]) // || c > 0 + { + unsigned p = node_at_level[c]; + parent[x] = p; + area[p] += area[x] + 1; + } + else + parent[x] = x; + + location[x] = loc++; + return c; + } + + template <typename I, typename N> + inline + unsigned + flooder<tag::tree::min_t, I, N>::attach_parent_(unsigned h_idx) + { + unsigned nv = vset.nvalues() - 1; + unsigned c = h_idx; + + while (c < nv && !is_node_at_level[c]) + ++c; + + unsigned x = node_at_level[h_idx]; + if (is_node_at_level[c]) // || c < nv + { + unsigned p = node_at_level[c]; + parent[x] = p; + area[p] += area[x] + 1; + } + else + parent[x] = x; + + location[x] = loc++; + return c; + } + + + template <typename I, typename N, typename E> + flooder_base_<I, N, E>::flooder_base_(const I& f_, const N& nbh_, + const histo::array< mln_value(I) >& histo_) + : f (f_), nbh (nbh_), is_node_at_level (false) + { + // Initialization + { + unsigned nsites = geom::nsites(f); + initialize(map, f); + initialize(deja_vu, f); + + parent.resize(nsites); + location.resize(nsites); + area.resize(nsites, 0); + data::fill(deja_vu, false); + + vset = value::set< mln_value(I) >::the(); + + n_node = 0; + loc = 0; + } + + // Get start value + mln_psite(I) pstart = f.domain().pmin(); + mln_value(I) hstart = f(pstart); + { + mln_piter(I) p(f.domain()); + for_all(p) + { + mln_value(I) v = f(p); + ++h[v]; + if (hlevel_less(v, hstart)) + { + hstart = v; + pstart = p; + } + } + + for (unsigned i = 0; i < nvalues; ++i) + hqueues[i].reserve(h[i]); + } + + // Start flooding + unsigned r = vset.index_of(hstart); + deja_vu(pstart) = true; + hqueues[r].push(pstart); + node_at_level[r] = n_node++; + is_node_at_level[r] = true; + + flood(r); + } + + template <typename I, typename N, typename E> + unsigned + flooder_base_<I, N, E>::flood(const unsigned h_idx) + { + mln_assertion(is_node_at_level[h_idx]); + + while (!hqueues[h_idx].empty()) + { + mln_psite(I) p = hqueues[h_idx].pop_front(); + mln_assertion(vset.index_of(f(p)) == h_idx); + + map(p) = node_at_level[h_idx]; + + // Process the neighbors + mln_niter(N) n(nbh, p); + for_all(n) + if (f.domain().has(n) && !deja_vu(n)) + { + unsigned n_idx = vset.index_of(f(n)); + hqueues[n_idx].push(n); + deja_vu(n) = true; + + if (!is_node_at_level[n_idx]) + { + node_at_level[n_idx] = n_node++; + is_node_at_level[n_idx] = true; + } + + while (hlevel_less(h_idx, n_idx)) + n_idx = flood(n_idx); + } + } + + is_node_at_level[h_idx] = false; + return attach_parent(h_idx); + } + + template <typename T, typename I, typename N> + inline + util::ctree::ctree + hqueue(const tag::tree::tree_t<T>&, const Image& f_, const Neighborhood<N>& nbh_) + { + trace::entering("mln::morpho::tree::impl::hqueue"); + const I& f = exact(f_); + const N& nbh = exact(nbh_); + + mln_precondition(f.is_valid()); + mln_precondition(nbh.is_valid()); + + // Process + impl::flooder<T, I, N> args(f, nbh); + // \todo handles here discontinous domains: so multi-roots trees. + + args.parent.resize(args.n_node); + args.area.resize(args.n_node); + args.location.resize(args.n_node); + + util::ctree::ctree tree(f, args.map, args.location, args.parent, + args.area); + + trace::exiting("mln::morpho::tree::impl::hqueue"); + return tree; + } + + } // end of namespace mln::morpho::tree::impl + +# endif // ! MLN_INCLUDE_ONLY + + } // end of namespace mln::morpho::tree + + } // end of namespace mln::morpho + +} // end of namespace mln + +#endif // !MLN_MORPHO_TREE_IMPL_HQUEUE_HH diff --git a/milena/mln/morpho/tree/impl/hqueue_fast.hh b/milena/mln/morpho/tree/impl/hqueue_fast.hh new file mode 100644 index 0000000..645bbc4 --- /dev/null +++ b/milena/mln/morpho/tree/impl/hqueue_fast.hh @@ -0,0 +1,391 @@ +#ifndef MLN_MORPHO_TREE_IMPL_HQUEUE_FASTHH +# define MLN_MORPHO_TREE_IMPL_HQUEUE_FASTHH + +# include <mln/extension/adjust.hh> +# include <mln/extension/fill.hh> +# include <mln/util/ctree/ctree.hh> +# include <mln/util/hqueues.hh> +# include <mln/value/value_array.hh> +# include <mln/geom/nsites.hh> +# include <mln/data/fill.hh> + +namespace mln +{ + + namespace morpho + { + + namespace tree + { + + namespace impl + { + + template <typename T, typename I, typename N> + util::ctree::ctree + hqueue_fast(const tag::tree::tree_t<T>&, const Image& f, const Neighborhood<N>& nbh); + + } // end of namespace mln::morpho::tree::impl + +# ifndef MLN_INCLUDE_ONLY + + namespace impl + { + + template <typename I, typename N, typename E> + struct flooder_base_ : Object<E> + { + typedef unsigned P; + typedef mln_value(I) V; + + // Constructor. + flooder_base_(const I& f_, const N& nbh_); + + mln_ch_value(I, unsigned) map; + std::vector location; + std::vector parent; + std::vector<unsigned> area; + unsigned n_node; + + protected: + enum { + nvalues = mln_card(mln_value(I)) + }; + + // Recursive function that floods. Canevas function. + unsigned flood(const unsigned h_idx); + + // HLevel comparaison. To be specialized for min/max tree. + bool hlevel_less(unsigned h_idx1, unsigned h_idx2); + + // Parent attachment function. To be specialized for min/max tree. + unsigned attach_parent(unsigned h_idx); + + + // Data. + // \{ + const I& f; + const N& nbh; + + // Auxiliary data. + util::hqueues<unsigned, V> hqueues; + value::set<V> vset; + util::array<int> dp; + unsigned n_nbhs; + + mln_ch_value(I, bool) deja_vu; + value::value_array<V, bool> is_node_at_level; + value::value_array<V, P> node_at_level; + unsigned loc; + // \} + }; + + template <typename T, typename I, typename N> + struct flooder; + + template <typename I, typename N> + struct flooder<tag::tree::max_t, I, N> : + flooder_base_< I, N, flooder<tag::tree::max_t, I, N> > + { + typedef mln_value(I) V; + typedef flooder_base_< I, N, flooder<tag::tree::max_t, I, N> > super_; + + // Constructor. + flooder(const I& f_, const N& nbh_); + + // HLevel comparaison. + bool hlevel_less_(unsigned h_idx1, unsigned h_idx2); + + // Parent attachment function. + unsigned attach_parent_(unsigned h_idx); + + public: + using super_::parent; + using super_::area; + using super_::location; + + protected: + using super_::is_node_at_level; + using super_::node_at_level; + using super_::vset; + using super_::loc; + }; + + template <typename I, typename N> + struct flooder<tag::tree::min_t, I, N> : + flooder_base_< I, N, flooder<tag::tree::min_t, I, N> > + { + typedef mln_value(I) V; + typedef flooder_base_< I, N, flooder<tag::tree::min_t, I, N> > super_; + + // Constructor. + flooder(const I& f_, const N& nbh_); + + // HLevel comparaison. + bool hlevel_less_(unsigned h_idx1, unsigned h_idx2); + + // Parent attachment function. + unsigned attach_parent_(unsigned h_idx); + + public: + using super_::parent; + using super_::area; + using super_::location; + + protected: + using super_::is_node_at_level; + using super_::node_at_level; + using super_::vset; + using super_::loc; + }; + + template <typename I, typename N, typename E> + inline + bool + flooder_base_<I, N, E>::hlevel_less(unsigned h_idx1, unsigned h_idx2) + { + E& obj = exact(*this); + return obj.hlevel_less_(h_idx1, h_idx2); + } + + template <typename I, typename N, typename E> + inline + unsigned + flooder_base_<I, N, E>::attach_parent(unsigned h_idx) + { + E& obj = exact(*this); + return obj.attach_parent_(h_idx); + } + + template <typename I, typename N> + inline + flooder<tag::tree::max_t, I, N>::flooder(const I& f_, const N& nbh_) + : flooder_base_<I, N, flooder<tag::tree::max_t, I, N> >(f_, nbh_) + { + } + + template <typename I, typename N> + inline + flooder<tag::tree::min_t, I, N>::flooder(const I& f_, const N& nbh_) + : flooder_base_<I, N, flooder<tag::tree::min_t, I, N> >(f_, nbh_) + { + } + + template <typename I, typename N> + inline + bool + flooder<tag::tree::max_t, I, N>::hlevel_less_(unsigned h_idx1, unsigned h_idx2) + { + return h_idx1 < h_idx2; + } + + template <typename I, typename N> + inline + bool + flooder<tag::tree::min_t, I, N>::hlevel_less_(unsigned h_idx1, unsigned h_idx2) + { + return h_idx2 < h_idx1; + } + + template <typename I, typename N> + inline + unsigned + flooder<tag::tree::max_t, I, N>::attach_parent_(unsigned h_idx) + { + unsigned c = h_idx; + while (c > 0 && !is_node_at_level[c]) + --c; + + unsigned x = node_at_level[h_idx]; + if (is_node_at_level[c]) // || c > 0 + { + unsigned p = node_at_level[c]; + parent[x] = p; + area[p] += area[x] + 1; + } + else + parent[x] = x; + + location[x] = loc++; + return c; + } + + template <typename I, typename N> + inline + unsigned + flooder<tag::tree::min_t, I, N>::attach_parent_(unsigned h_idx) + { + unsigned nv = vset.nvalues() - 1; + unsigned c = h_idx; + + while (c < nv && !is_node_at_level[c]) + ++c; + + unsigned x = node_at_level[h_idx]; + if (is_node_at_level[c]) // || c < nv + { + unsigned p = node_at_level[c]; + parent[x] = p; + area[p] += area[x] + 1; + } + else + parent[x] = x; + + location[x] = loc++; + return c; + } + + + template <typename I, typename N, typename E> + flooder_base_<I, N, E>::flooder_base_(const I& f_, const N& nbh_) + : f (f_), nbh (nbh_), is_node_at_level(false) + { + // Prepare hierarchical queues and retrieve start point. + unsigned pmin; + mln_value(I) vmin; + { + util::array< unsigned > h(nvalues, 0); + + pmin = f.index_of_point(f.domain().pmin()); + vmin = f.element(pmin); + + mln_fwd_pixter(const I) pxl(f); + for_all(pxl) + { + ++h[pxl.val()]; + if (hlevel_less(pxl.val(), vmin)) + { + vmin = pxl.val(); + pmin = pxl.offset(); + } + } + + for (unsigned i = 0; i < nvalues; ++i) + hqueues[i].reserve(h[i]); + } + + // Initialize aux data + { + dp = offsets_wrt(f, nbh); + n_nbhs = dp.nelements(); + vset = value::set< mln_value(I) >::the(); + + extension::adjust(f, nbh); + + initialize(deja_vu, f); + initialize(map, f); + data::fill(deja_vu, false); + extension::fill(deja_vu, true); + + unsigned nsites = geom::nsites(f); + parent.resize(nsites); + location.resize(nsites); + area.resize(nsites, 0); + + n_node = 0; + loc = 0; + } + + // Start flooding + unsigned hmin = vset.index_of(vmin); + deja_vu.element(pmin) = true; + hqueues[hmin].push(pmin); + node_at_level[hmin] = n_node++; + is_node_at_level[hmin] = true; + + flood(hmin); + } + + template <typename I, typename N, typename E> + unsigned + flooder_base_<I, N, E>::flood(const unsigned h_idx) + { + mln_assertion(is_node_at_level[h_idx]); + + while (!hqueues[h_idx].empty()) + { + unsigned p = hqueues[h_idx].pop_front(); + mln_assertion(vset.index_of(f.element(p)) == h_idx); + + map.element(p) = node_at_level[h_idx]; + + // Process the neighbors + for (unsigned j = 0; j < n_nbhs; ++j) + { + unsigned n = p + dp[j]; + + if (!deja_vu.element(n)) + { + unsigned n_idx = vset.index_of(f.element(n)); + hqueues[n_idx].push(n); + deja_vu.element(n) = true; + + if (!is_node_at_level[n_idx]) + { + node_at_level[n_idx] = n_node++; + is_node_at_level[n_idx] = true; + } + + while (hlevel_less(h_idx, n_idx)) + n_idx = flood(n_idx); + } + } + } + + is_node_at_level[h_idx] = false; + return attach_parent(h_idx); + } + + template <typename T, typename I, typename N> + inline + util::ctree::ctree + hqueue_fast(const tag::tree::tree_t<T>&, const Image& f_, const Neighborhood<N>& nbh_) + { + trace::entering("mln::morpho::tree::impl::hqueue_fast"); + const I& f = exact(f_); + const N& nbh = exact(nbh_); + + mln_precondition(f.is_valid()); + mln_precondition(nbh.is_valid()); + + // Process + impl::flooder<T, I, N> args(f, nbh); + // \todo handles here discontinous domains: so multi-roots trees. + + // Create tree and fill it. + util::ctree::ctree tree; + { + tree.reserve(f, args.n_node); + + mln_pixter(const I) pix(f); + for_all(pix) + { + int idx = args.map.element(pix.offset()); + int loc = args.n_node - args.location[idx] - 1; + tree.data_->map_.element(pix.offset()) = loc; + tree.data_->values_[loc] = pix.val(); + } + + for (unsigned idx = 0; idx < args.n_node; ++idx) + { + int loc = args.n_node - args.location[idx] - 1; + tree.data_->parent_[loc] = args.n_node - args.location[args.parent[idx]] - 1; + tree.data_->length_[loc] = args.area[idx]; + } + } + + trace::exiting("mln::morpho::tree::impl::hqueue_fast"); + return tree; + } + + } // end of namespace mln::morpho::tree::impl + +# endif // ! MLN_INCLUDE_ONLY + + } // end of namespace mln::morpho::tree + + } // end of namespace mln::morpho + +} // end of namespace mln + +#endif // !MLN_MORPHO_TREE_IMPL_HQUEUE_FAST_HH diff --git a/milena/mln/morpho/tree/impl/union_find.hh b/milena/mln/morpho/tree/impl/union_find.hh new file mode 100644 index 0000000..8485727 --- /dev/null +++ b/milena/mln/morpho/tree/impl/union_find.hh @@ -0,0 +1,174 @@ +// Copyright (C) 2008, 2009 EPITA Research and Development Laboratory (LRDE) +// +// This file is part of Olena. +// +// Olena is free software: you can redistribute it and/or modify it under +// the terms of the GNU General Public License as published by the Free +// Software Foundation, version 2 of the License. +// +// Olena 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 Olena. If not, see <http://www.gnu.org/licenses/>. +// +// As a special exception, you may use this file as part of a free +// software project 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_IMPL_UNION_FIND_HH +# define MLN_MORPHO_TREE_IMPL_UNION_FIND_HH + +# include <mln/data/sort_psites.hh> +# include <mln/util/ctree/ctree.hh> + +namespace mln +{ + + namespace morpho + { + + namespace tree + { + + namespace impl + { + + template <typename T, typename I, typename N> + util::ctree::ctree + union_find(const tag::tree::tree_t<T>&, + const Image& f, + const Neighborhood<N>& nbh); + } + + +# ifndef MLN_INCLUDE_ONLY + + namespace internal + { + + template <typename I> + p_array<mln_psite(I)> + inline + sort_sites_set(const tag::tree::max_t&, const I& f) + { + p_array<mln_psite(I)> data = + data::sort_psites_increasing(f); + return data; + } + + template <typename I> + p_array<mln_psite(I)> + inline + sort_sites_set(const tag::tree::min_t&, const I& f) + { + p_array<mln_psite(I)> data = + data::sort_psites_decreasing(f); + return data; + } + + 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)); + } + + } + + + namespace impl + { + + namespace generic + { + + template <typename T, typename I, typename N> + util::ctree::ctree + union_find(const tag::tree::tree_t<T>&, + const Image& f_, + const Neighborhood<N>& nbh_) + { + trace::entering("morpho::tree::impl::generic::union_find"); + + typedef mln_psite(I) P; + typedef p_array<mln_psite(I)> S; + + const I& f = exact(f_); + const N& nbh = exact(nbh_); + S s = internal::sort_sites_set(T (), f); + + // Auxiliary data. + mln_ch_value(I, bool) deja_vu; + mln_ch_value(I, P) parent; + mln_ch_value(I, unsigned) area; + mln_ch_value(I, P) zpar; + unsigned nb_nodes = s.nsites(); + + initialize(deja_vu, f); + initialize(parent, f); + initialize(area, f); + initialize(zpar, f); + + // Initialization. + data::fill(deja_vu, false); + data::fill(area, 0); + + // Body. + mln_bkd_piter(S) p(s); // Backward. + mln_niter(N) n(nbh, p); + for_all(p) + { + // Make-Set. + parent(p) = p; + zpar(p) = p; + + for_all(n) + if (f.domain().has(n) && deja_vu(n)) + { + // Do-Union. + P r = internal::zfind_root(zpar, n); + if (r != p) + { + parent(r) = p; + zpar(r) = p; + area(p) += area(r); + if (f(r) != f(p)) + ++area(p); + else + --nb_nodes; + } + } + deja_vu(p) = true; + } + + util::ctree::ctree tree(f, s, parent, area, nb_nodes); + + trace::exiting("morpho::tree::impl::generic::union_find"); + return tree; + } + + } + + } + +# endif // ! MLN_INCLUDE_ONLY + + } + + } + +} +#endif // !MLN_MORPHO_TREE_IMPL_UNION_FIND_HH diff --git a/milena/mln/morpho/tree/impl/union_find_fast.hh b/milena/mln/morpho/tree/impl/union_find_fast.hh new file mode 100644 index 0000000..80a521d --- /dev/null +++ b/milena/mln/morpho/tree/impl/union_find_fast.hh @@ -0,0 +1,396 @@ +// Copyright (C) 2008, 2009 EPITA Research and Development Laboratory (LRDE) +// +// This file is part of Olena. +// +// Olena is free software: you can redistribute it and/or modify it under +// the terms of the GNU General Public License as published by the Free +// Software Foundation, version 2 of the License. +// +// Olena 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 Olena. If not, see <http://www.gnu.org/licenses/>. +// +// As a special exception, you may use this file as part of a free +// software project 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_IMPL_UNION_FIND_FAST_HH +# define MLN_MORPHO_TREE_IMPL_UNION_FIND_FAST_HH + +/// +/// + + +namespace mln +{ + + namespace morpho + { + + namespace tree + { + + namespace impl + { + + namespace generic + { + + /// The fast version of union-find algorithm. + /// \pre The image \p f must be fastest + /// + /// \param tree_tag The type of tree to build (min or max-tree). + /// \param f Source image used to build the component tree. + /// \param nbh Neighborhood used to build the component tree. + /// + /// \return A component tree object. + /// + template <typename T, typename I, typename N> + util::ctree::ctree + union_find_fast(const tag::tree::tree_t<T>& tree_tag, + const Image& f, + const Neighborhood<N>& nbh); + } + + } + +# ifndef MLN_INCLUDE_ONLY + + namespace internal + { + + template <typename I> + inline + void + sort_sites_set_radix(const tag::tree::max_t&, const I& f, util::array<unsigned>& s, util::array<unsigned>& levels) + { + typedef mln_value(I) V; + static const value::set<V>& vset = value::set<V>::the(); + static const int n = mln_card(V); + + util::array<unsigned> h(n, 0); + s.resize(f.domain().nsites()); + levels.resize(n + 1); + + mln_fwd_pixter(const I) pxl(f); + for_all(pxl) + ++h[vset.index_of(pxl.val())]; + + for (int i = 1; i <= n; ++i) + { + levels[i] = levels[i - 1] + h[i - 1]; + h[i - 1] = levels[i - 1]; + } + + // computing output data + for_all(pxl) + { + int i = vset.index_of(pxl.val()); + s[h[i]++] = pxl.offset(); + } + } + + template <typename I> + static inline + void + sort_sites_set_radix(const tag::tree::min_t&, const I& f, util::array<unsigned>& s, util::array<unsigned>& levels) + { + typedef mln_value(I) V; + static const value::set<V>& vset = value::set<V>::the(); + static const int n = mln_card(V); + + util::array<unsigned> h(n, 0); + s.resize(f.domain().nsites()); + levels.resize(n + 1); + + mln_fwd_pixter(const I) pxl(f); + for_all(pxl) + ++h[n - 1 - vset.index_of(pxl.val())]; + + for (int i = 1; i <= n; ++i) + { + levels[i] = levels[i - 1] + h[i - 1]; + h[i - 1] = levels[i - 1]; + } + + // computing output data + for_all(pxl) + { + int i = vset.index_of(pxl.val()); + s[h[n - 1 - i]++] = pxl.offset(); + } + } + + template <typename T, typename I> + struct sort_op_less_; + + template <typename I> + struct sort_op_less_<tag::tree::max_t, I> + { + sort_op_less_ (const I& f_) : f(f_) {} + + bool operator() (unsigned e1, unsigned e2) + { + return f.element(e1) < f.element(e2) || (f.element(e1) == f.element(e2) && e1 < e2); + } + + private: + const I& f; + }; + + template <typename I> + struct sort_op_less_<tag::tree::min_t, I> + { + sort_op_less_ (const I& f_) : f(f_) {} + + bool operator() (unsigned e1, unsigned e2) + { + return f.element(e2) < f.element(e1) || (f.element(e1) == f.element(e2) && e2 < e1); + } + + private: + const I& f; + }; + + template <typename T, typename I> + inline + void + sort_sites_set_std(const T&, const I& f, util::array<unsigned>& s) + { + s.reserve(f.domain().nsites()); + + mln_pixter(const I) pix(f); + for_all(pix) + s.append(pix.offset()); + + std::vector<unsigned>& v = s.hook_std_vector_(); + std::sort(v.begin(), v.end(), sort_op_less_<T, I>(f)); + } + + template <typename T, typename I> + static inline + void + sort_sites_set_dispatch(const mln::trait::value::quant::low&, const T& tree_, const I& f, util::array<unsigned>& s, util::array<unsigned>& levels) + { + trace::entering("morpho::tree::internal::sort_sites_set_radix"); + sort_sites_set_radix(tree_, f, s, levels); + trace::exiting("morpho::tree::internal::sort_sites_set_radix"); + } + + template <typename T, typename I> + static inline + void + sort_sites_set_dispatch(const mln::trait::value::quant::any&, const T& tree_, const I& f, util::array<unsigned>& s, util::array<unsigned>& levels) + { + (void) levels; + trace::entering("morpho::tree::internal::sort_sites_set_std"); + sort_sites_set_std(tree_, f, s); + trace::exiting("morpho::tree::internal::sort_sites_set_std"); + } + + + template <typename T, typename I> + static inline + void + sort_sites_set(const T& tree_, const I& f, util::array<unsigned>& s, util::array<unsigned>& levels) + { + sort_sites_set_dispatch(mln_trait_value_quant(mln_value(I)) (), tree_, f, s, levels); + } + + template <typename T> + static inline + unsigned + zfind_root(T& zpar, unsigned x) + { + mlc_equal(mln_value(T), unsigned)::check(); + if (zpar.element(x) == x) + return x; + else + return zpar.element(x) = zfind_root(zpar, zpar.element(x)); + } + + + } // end of namespace mln::morpho::tree::internal + + namespace impl + { + + namespace generic + { + + template <typename I, typename F> + static inline + void + union_find_fast_process2_(const I& f, const util::array<int>& dp, + F& parent, F& area, F& zpar, + unsigned& nnodes, unsigned p) + { + // Make set. + const unsigned n_nbhs = dp.nelements(); + + parent.element(p) = p; + zpar.element(p) = p; + + for (unsigned j = 0; j < n_nbhs; ++j) + { + unsigned n = p + dp[j]; + + if (zpar.element(n) == 0) // not deja-vu + continue; + + unsigned r = internal::zfind_root(zpar, n); + if (r != p) + { + parent.element(r) = p; + zpar.element(r) = p; + area.element(p) += area.element(r); + if (f.element(r) != f.element(p)) + ++area.element(p); + else + --nnodes; + } + } + } + + + template <typename I, typename F> + static inline + unsigned + union_find_fast_process(const mln::trait::value::quant::low&, const I& f, const util::array<int>& dp, + F& parent, F& area, F& zpar, + const util::array<unsigned>& s, const util::array<unsigned>& levels) + { + trace::entering("morpho::tree::impl::union_find_fast_process_low"); + static const unsigned nvalues = mln_card(mln_value(I)); + + unsigned nnodes = f.domain().nsites(); + + for (int v = nvalues - 1; v >= 0; --v) // Reverse + { + for (int i = levels[v + 1] - 1; i >= (int)levels[v]; --i) // Reverse + union_find_fast_process2_(f, dp, parent, area, zpar, nnodes, s[i]); + + // Fast root compression + for (unsigned i = levels[v]; i < levels[v + 1]; ++i) // Direct + { + unsigned p = s[i]; + zpar.element(p) = zpar.element(zpar.element(p)); + } + } + + trace::exiting("morpho::tree::impl::union_find_fast_process_low"); + return nnodes; + } + + template <typename I, typename F> + static inline + unsigned + union_find_fast_process(const trait::value::quant::any&, const I& f, const util::array<int>& dp, + F& parent, F& area, F& zpar, + const util::array<unsigned>& s, const util::array<unsigned>&) + { + trace::entering("morpho::tree::impl::union_find_fast_process_any"); + + unsigned nnodes = f.domain().nsites(); + for (int i = s.size() - 1; i >= 0; --i) // Reverse + union_find_fast_process2_(f, dp, parent, area, zpar, nnodes, s[i]); + + trace::exiting("morpho::tree::impl::union_find_fast_process_any"); + return nnodes; + } + + + template <typename T, typename I, typename N> + util::ctree::ctree + union_find_fast(const tag::tree::tree_t<T>&, + const Image& f_, + const Neighborhood<N>& nbh_) + { + trace::entering("morpho::tree::impl::generic::union_find_fast"); + + typedef p_array<mln_psite(I)> S; + typedef mln_value(I) V; + + const I& f = exact(f_); + const N& nbh = exact(nbh_); + util::array< unsigned > s; + util::array< unsigned > levels; + internal::sort_sites_set(T (), f, s, levels); + + util::array<int> dp = offsets_wrt(f, nbh); + + // Auxiliary data. + mln_ch_value(I, unsigned) parent; + mln_ch_value(I, unsigned) area; + mln_ch_value(I, unsigned) zpar; + + initialize(parent, f); + initialize(area, f); + initialize(zpar, f); + + // Initialization. + data::fill(zpar, 0); + data::fill(area, 0); + + unsigned nnodes = + union_find_fast_process(mln_trait_value_quant(V) (), f, dp, parent, area, zpar, s, levels); + + util::ctree::ctree tree; + tree.reserve(f, nnodes); + + unsigned root_offset = 0; + for (unsigned i = 0; i < s.size(); ++i) // Forward + { + unsigned p = s[i]; + unsigned q = parent.element(p); + + if (f.element(parent.element(q)) == f.element(q)) // Canonization + q = (parent.element(p) = parent.element(q)); + + if (f.element(p) == f.element(q) && p != q) // Not a node. + { + mln_assertion(q == parent.element(p)); + tree.data_->map_.element(p) = + tree.data_->map_.element(q); + } + else + { + unsigned& offset = (p == q) ? root_offset : area.element(q); + + // Insert Node. + mln_assertion(offset < nnodes); + tree.data_->map_.element(p) = offset; + tree.data_->parent_[offset] = tree.data_->map_.element(q); + tree.data_->values_[offset] = f.element(p); + tree.data_->length_[offset] = area.element(p); + area.element(p) = offset + 1; + offset += tree.data_->length_[offset] + 1; + } + } + + trace::exiting("morpho::tree::impl::generic::union_find_fast"); + return tree; + } + + } // end of namespace mln::morpho::tree::impl::generic + + } // end of namespace mln::morpho::tree::impl + +# endif // ! MLN_INCLUDE_ONLY + + } // end of namespace mln::morpho::tree + + } // end of namespace mln::morpho + +} // end of namespace mln + +#endif // !MLN_MORPHO_TREE_IMPL_UNION_FIND_FAST_HH diff --git a/milena/mln/morpho/tree/leaf_last.hh b/milena/mln/morpho/tree/leaf_last.hh new file mode 100644 index 0000000..2f283d5 --- /dev/null +++ b/milena/mln/morpho/tree/leaf_last.hh @@ -0,0 +1,111 @@ +// Copyright (C) 2008, 2009 EPITA Research and Development Laboratory (LRDE) +// +// This file is part of Olena. +// +// Olena is free software: you can redistribute it and/or modify it under +// the terms of the GNU General Public License as published by the Free +// Software Foundation, version 2 of the License. +// +// Olena 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 Olena. If not, see <http://www.gnu.org/licenses/>. +// +// As a special exception, you may use this file as part of a free +// software project 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_LEAF_LAST_HH +# define MLN_MORPHO_TREE_LEAF_LAST_HH + +# include <mln/accu/stat/max.hh> +# include <mln/util/ctree/ctree.hh> +# include <mln/morpho/tree/propagate_node.hh> +# include <mln/convert/to_p_array.hh> + +namespace mln +{ + + namespace morpho + { + + namespace tree + { + + template <typename T, typename V> + util::array<typename T::node_t> + leaf_last(const attribute_image<T, V>& ima); + +# ifndef MLN_INCLUDE_ONLY + + namespace internal + { + + template <typename T, typename V> + struct less_ + { + typedef typename T::node_t node_t; + + less_(const attribute_image<T, V>& img) : + f_ (img) + { + } + + bool operator() (const node_t& lhs, const node_t& rhs) + { + return f_(lhs) > f_(rhs); + } + + private: + const attribute_image<T, V>& f_; + }; + } + + template <typename T, typename V> + util::array<typename T::node_t> + leaf_last(const attribute_image<T, V>& ima) + { + typedef attribute_image<T, V> A; + typedef typename T::node_t node_t; + + p_array<node_t> sorted_sites = convert::to_p_array(ima); + std::vector<node_t>& hook = sorted_sites.hook_std_vector_(); + std::sort(hook.begin(), hook.end(), internal::less_<T, V> (ima)); + + mln_ch_value(A, char) deja_vu; + initialize(deja_vu, ima); + data::fill(deja_vu, 0); + + util::array<node_t> result; + + mln_piter(p_array<node_t>) n(sorted_sites); + for_all(n) + { + if (deja_vu(n)) + continue; + result.append(n); + deja_vu(n) = true; // useless + propagate_node_to_descendants<T, char>(deja_vu, n, 1); + propagate_node_to_ancestors<T, char>(deja_vu, n, 1); + } + + return result; + } + +# endif // ! MLN_INCLUDE_ONLY + + } // end of namespace mln::morpho::tree + + } // end of namespace mln::morpho + +} // end of namespace mln + +#endif // !MLN_MORPHO_TREE_LEAF_LAST_HH diff --git a/milena/mln/morpho/tree/propagate_node.hh b/milena/mln/morpho/tree/propagate_node.hh index 33c06c2..c2fc15e 100644 --- a/milena/mln/morpho/tree/propagate_node.hh +++ b/milena/mln/morpho/tree/propagate_node.hh @@ -26,14 +26,27 @@ #ifndef MLN_MORPHO_TREE_PROPAGATE_NODE_HH # define MLN_MORPHO_TREE_PROPAGATE_NODE_HH -# include <mln/core/concept/image.hh> -# include <mln/core/macros.hh> -# include <mln/morpho/tree/data.hh> - /// \file /// /// Functions to propagate node in the tree. +/// +/// \todo: The new implementation permits: + to propagate toward +/// subcomponents very fast (data::fill)\ + to propagate toward +/// supernodes as fast as the previous component\ + the attribute +/// image is still valid without the use of propagate_representative +/// that does not make sense any more. +/// +/// We are able in both cases to do something like: +/// + data::fill(attr_img | asc(n), v) +/// + data::fill(attr_img | desc(n), v) +/// +/// However the subimage morpher is not specialized for fast image and +/// does not take benefits in the fact that: +/// + desc(n) is a p_run (so can be memseted) +/// + attr_img can accessed by indexed (element() method for fast-image) +# include <mln/core/image/attribute_image.hh> +# include <algorithm> namespace mln { @@ -47,162 +60,85 @@ namespace mln /*! ** Propagate a value \p v from a node \p n to its descendants. ** - ** \param[in] n Node to propagate. - ** \param[in] t Component tree used for propagation. - ** \param[in] a_ Attribute image where values are propagated. - ** \param[in] v Value to propagate. - ** \param[out] nb_leaves Optional. Store the number of leaves in - ** the component. - */ - template <typename T, typename A> - void - propagate_node_to_descendants(mln_psite(A) n, - const T& t, - Image<A>& a_, - const mln_value(A)& v, - unsigned* nb_leaves = 0); - - /*! - ** Propagate the node's value to its descendants. + ** \param[in] a Attribute image + ** \param[in] n Node from which we should start propagating + ** \param[in] value Value to propagate ** - ** \param[in] n Node to propagate. - ** \param[in] t Component tree used for propagation. - ** \param[in] a_ Attribute image where values are propagated. - ** \param[out] nb_leaves Optional. Store the number of leaves in - ** the component. + ** \return The number of nodes set. */ - template <typename T, typename A> + template <typename T, typename V> inline - void - propagate_node_to_descendants(mln_psite(A)& n, - const T& t, - Image<A>& a_, - unsigned* nb_leaves = 0); + unsigned + propagate_node_to_descendants(attribute_image<T, V>& a, + const typename T::node_t& n, + const V& value); /*! ** Propagate a value \p v from a node \p n to its ancestors. ** - ** \param[in] n Node to propagate. - ** \param[in] t Component tree used for propagation. - ** \param[in] a_ Attribute image where values are propagated. - ** \param[in] v Value to propagate. - */ - template <typename T, typename A> - void - propagate_node_to_ancestors(mln_psite(A) n, - const T& t, - Image<A>& a_, - const mln_value(A)& v); - - /*! - ** Propagate the node's value to its ancestors. + ** \param[in] a Attribute image + ** \param[in] n Node from which we should start propagating + ** \param[in] value Value to propagate ** - ** \param[in] n Node to propagate. - ** \param[in] t Component tree used for propagation. - ** \param[in,out] a_ Attribute image where values are propagated. + ** \return The number of nodes set. */ - template <typename T, typename A> + template <typename T, typename V> inline - void - propagate_node_to_ancestors(mln_psite(A) n, - const T& t, - Image<A>& a_); - + unsigned + propagate_node_to_ancestors(attribute_image<T, V>& a, + typename T::node_t n, + const V& v); # ifndef MLN_INCLUDE_ONLY - /* Descendants propagation */ - - template <typename T, typename A> + template <typename T, typename V> inline - void - propagate_node_to_descendants(mln_psite(A) n, - const T& t, - Image<A>& a_, - const mln_value(A)& v, - unsigned* nb_leaves) + unsigned + propagate_node_to_descendants(attribute_image<T, V>& a, + const typename T::node_t& n, + const V& value) { - A& a = exact(a_); + typedef typename T::nodes_t desc_t; mln_precondition(a.is_valid()); - mln_precondition(a.domain() == t.f().domain()); - mln_precondition(a.domain().has(n)); - - - if (!t.is_a_node(n)) // Get the representant. - n = t.parent(n); - mln_assertion(t.is_a_node(n)); + mln_precondition(a.has(n)); - typename T::depth1st_piter pp(t, n); + // (n € desc(n)) but we don't set its value. + unsigned i = a.tree().desc(n).nsites(); - pp.start(); // We don't set n to v. - - if (nb_leaves) - *nb_leaves += t.is_a_leaf(pp); - - for (pp.next(); pp.is_valid(); pp.next()) + if (i > 1) { - a(pp) = v; - if (nb_leaves && t.is_a_leaf(pp)) - ++(*nb_leaves); + mln_assertion(a.tree().has_index(n.index() + i)); + V* v = a.buffer() + n.index(); + std::fill(v + 1, v + i, value); } + return i - 1; } - - template <typename T, typename A> + template <typename T, typename V> inline - void - propagate_node_to_descendants(mln_psite(A) n, - const T& t, - Image<A>& a_, - unsigned* nb_leaves = 0) - - { - A& a = exact(a_); - propagate_node_to_descendants(n, t, a, a(n), nb_leaves); - } - - - /* Ancestors propagation */ - - template <typename T, typename A> - void - propagate_node_to_ancestors(mln_psite(A) n, - const T& t, - Image<A>& a_, - const mln_value(A)& v) + unsigned + propagate_node_to_ancestors(attribute_image<T, V>& a, + typename T::node_t n, + const V& v) { - A& a = exact(a_); mln_precondition(a.is_valid()); - mln_precondition(a.domain() == t.f().domain()); - mln_precondition(a.domain().has(n)); + mln_precondition(a.has(n)); - if (!t.is_a_node(n)) // Get the representant. - n = t.parent(n); - mln_assertion(t.is_a_node(n)); - - if (t.is_root(n)) - return; + if (a.tree().is_a_root(n)) + return 0; + unsigned i = 0; do { - n = t.parent(n); + n = a.tree().parent(n); a(n) = v; - } while (!t.is_root(n)); + ++i; + } while (!a.tree().is_a_root(n)); + return i; } - template <typename T, typename A> - inline - void - propagate_node_to_ancestors(mln_psite(A) n, - const T& t, - Image<A>& a_) - { - A& a = exact(a_); - propagate_node_to_ancestors(n, t, a, a(n)); - } - -# endif // ! MLN_INCLUDE_ONLY +# endif } // end of namespace mln::morpho::tree diff --git a/milena/mln/tag/skeleton.hh b/milena/mln/tag/skeleton.hh index f446317..bca9b4f 100644 --- a/milena/mln/tag/skeleton.hh +++ b/milena/mln/tag/skeleton.hh @@ -44,6 +44,7 @@ namespace mln template <typename F> struct function_ { typedef F param; }; template <typename G> struct graph_ { typedef G param; }; template <typename I> struct image_ { typedef I param; }; + template <typename T> struct tree_ { typedef T param; }; template <typename N> struct neighb_ { typedef N param; }; template <typename P> struct psite_ { typedef P param; }; template <typename S> struct domain_ { typedef S param; }; diff --git a/milena/mln/util/hqueues.hh b/milena/mln/util/hqueues.hh index 151c71c..35c7a50 100644 --- a/milena/mln/util/hqueues.hh +++ b/milena/mln/util/hqueues.hh @@ -55,6 +55,7 @@ namespace mln nvalues = mln_card(T) }; + hqueues(); hqueues(const histo::array<T>& h); const p_queue_fast& operator[](unsigned i) const; @@ -66,38 +67,29 @@ namespace mln const mln::value::set<T>& vset() const; protected: - void pre_allocate_(unsigned i); - - const histo::array<T>& h_; const mln::value::set<T>& s_; - std::vector<bool> allocated_; std::vector< p_queue_fast >queues_; }; # ifndef MLN_INCLUDE_ONLY - template <typename P, typename T> inline - hqueues<P,T>::hqueues(const histo::array<T>& h) - : h_ (h), - s_ (mln::value::set<T>::the()), - allocated_ (nvalues, false), - queues_ (nvalues) + hqueues<P,T>::hqueues() + : s_ (mln::value::set<T>::the()) { + queues_.resize(nvalues); } + template <typename P, typename T> inline - void - hqueues<P,T>::pre_allocate_(unsigned i) + hqueues<P,T>::hqueues(const histo::array<T>& h) + : s_ (mln::value::set<T>::the()) { - mln_precondition(i < nvalues); - if (!allocated_[i]) - { - queues_[i].reserve(h_[i]); - allocated_[i] = true; - } + queues_.resize(nvalues); + for (unsigned i = 0; i < nvalues; ++i) + queues_[i].reserve(h[i]); } @@ -107,7 +99,6 @@ namespace mln hqueues<P,T>::operator[](unsigned i) const { mln_precondition(i < nvalues); - pre_allocate_(i); return queues_[i]; } @@ -117,7 +108,6 @@ namespace mln hqueues<P,T>::operator[](unsigned i) { mln_precondition(i < nvalues); - pre_allocate_(i); return queues_[i]; } @@ -127,7 +117,6 @@ namespace mln hqueues<P,T>::operator()(const T& v) const { unsigned i = s_.index_of(v); - pre_allocate_(i); return queues_[i]; } @@ -137,7 +126,6 @@ namespace mln hqueues<P,T>::operator()(const T& v) { unsigned i = s_.index_of(v); - pre_allocate_(i); return queues_[i]; } -- 1.7.10.4

1 0

[Olena] #265: Merge fix/iterator-preconditions-t256 into next
by Olena Trac 05 Sep '13

05 Sep '13

#265: Merge fix/iterator-preconditions-t256 into next --------------------------+------------------------------------------------- Reporter: lazzara | Owner: levill_r Type: pull-request | Status: new Priority: critical | Milestone: Olena 2.1 Component: Milena | Version: 2.0 Keywords: | --------------------------+------------------------------------------------- This branch includes a patch related to ticket #256. -- Ticket URL: <https://trac.lrde.org/olena/ticket/265> Olena <http://olena.lrde.epita.fr> Olena, a software platform dedicated to image processing.

1 1

[Olena] #221: Post-Olena 1.0 cleanup
by Olena Trac 05 Sep '13

05 Sep '13

#221: Post-Olena 1.0 cleanup ----------------------+----------------------------------------------------- Reporter: levill_r | Owner: Olena Team Type: defect | Status: new Priority: major | Milestone: Olena 1.1 Component: Milena | Version: 1.0 Keywords: | ----------------------+----------------------------------------------------- As a memo, an unordered list of miscellaneous tasks (split/reorder if needed): * Rename directories `{milena,scribo}/tests/unit_test` as `{milena,scribo}/tests/unit-tests`. * Move `milena/tests/tools/*` into `build-aux/`. * Write a developer Manual (see Vaucanson's). * All LaTeX-based documents (including the tutorial) should be compiled with `texi2dvi`. * The test `tests/io/pgm/pgm.cc` is too long (edit: check that again); simplify it? * More generally, we should time tests to see which ones are the most time-consuming, both at compile- (if applicable) and run-time. -- Ticket URL: <https://trac.lrde.org/olena/ticket/221> Olena <http://olena.lrde.epita.fr> Olena, a generic and efficient C++ image processing library.

1 3

[Olena] #279: Write a developer manual
by Olena Trac 05 Sep '13

05 Sep '13

#279: Write a developer manual ----------------------+----------------------- Reporter: levill_r | Owner: levill_r Type: task | Status: new Priority: major | Milestone: Olena 2.1 Component: Olena | Version: 2.0 Keywords: | ----------------------+----------------------- Task extracted from #221. We should try to get some inspiration from Vaucanson, SPOT and maybe TC here. I (Roland) think `HACKING` is the right place to host this manual, as it is the case for SPOT's (see http://git.lrde.epita.fr/?p=spot.git;a=blob;f=HACKING) This manual should document maintenance and development procedures, a coding style, help on tools, good practice advice, etc. Do not hesitate to add more ideas to this list and/or to contact me (Roland) about this. See also: * these tickets: #202, #203 and #258; * these messages: * https://lists.lrde.epita.fr/private/olena- core/2008-September/000034.html, * https://lists.lrde.epita.fr/private/olena- core/2008-September/000041.html, * https://lists.lrde.epita.fr/private/olena- core/2009-December/000253.html, * http://lists.lrde.epita.fr/pipermail/olena/2013-September/000545.html. -- Ticket URL: <https://trac.lrde.epita.fr/olena/ticket/279> Olena <http://olena.lrde.epita.fr> Olena, a software platform dedicated to image processing.

1 0