https://svn.lrde.epita.fr/svn/oln/trunk/milena Index: ChangeLog from Thierry Geraud <thierry.geraud@lrde.epita.fr> Fix repeated loops with pixel iterators. * mln/core/image/image2d.hh (todo): New. * mln/core/pixter2d.hh (start_): New. Upgrade file doc style. Layout. * mln/core/pixter3d.hh: Likewise. * mln/core/dpoints_pixter.hh (todo): New. * mln/core/internal/pixel_iterator_base.hh: Upgrade file doc style. (start_): New; default impl is no-op. (start): Call start_. * mln/core/internal/pixel_impl.hh (todo): New. (pixel_impl_base_): New. (image_, value_ptr_): Move from pixel_impl_ to pixel_impl_base_. * mln/core/pixel.hh: Upgrade file doc style. (todo): New. * mln/util/pix.hh (todo): New. Misc. * mln/core/concept/window.hh (offsets_wrt): New. * mln/core/concept/neighborhood.hh: Likewise. * mln/morpho/closing_attribute.hh: Update. * mln/morpho/opening_attribute.hh: Update. * mln/canvas/morpho/algebraic_union_find.hh: Update. canvas/morpho/algebraic_union_find.hh | 159 ++++++++++++++++++++++++++++++++-- core/concept/neighborhood.hh | 32 ++++++ core/concept/window.hh | 32 ++++++ core/dpoints_pixter.hh | 2 core/image/image2d.hh | 3 core/internal/pixel_impl.hh | 115 +++++++++++++++++++++--- core/internal/pixel_iterator_base.hh | 24 ++++- core/pixel.hh | 14 +- core/pixter2d.hh | 40 +++++++- core/pixter3d.hh | 73 ++++++++++++--- morpho/closing_attribute.hh | 149 ++++++++++++++++++++++++++++++- morpho/opening_attribute.hh | 2 util/pix.hh | 7 + 13 files changed, 598 insertions(+), 54 deletions(-) Index: mln/core/image/image2d.hh --- mln/core/image/image2d.hh (revision 3228) +++ mln/core/image/image2d.hh (working copy) @@ -33,6 +33,9 @@ /// Definition of the basic mln::image2d class. /// /// \todo Re-activate include at EOF when make::image2d is up again. +/// +/// \todo Rename delta_index and point_at_index as offset and +/// point_at_offset. # include <mln/core/internal/image_primary.hh> # include <mln/core/internal/fixme.hh> Index: mln/core/pixter2d.hh --- mln/core/pixter2d.hh (revision 3228) +++ mln/core/pixter2d.hh (working copy) @@ -30,7 +30,8 @@ # define MLN_CORE_PIXTER2D_HH /// \file mln/core/pixter2d.hh -/// \brief Pixel iterators on a 2-D image with border. +/// +/// Pixel iterators on a 2D image with border. # include <mln/core/internal/pixel_iterator_base.hh> # include <mln/core/alias/point2d.hh> @@ -62,13 +63,21 @@ /// Go to the next pixel. void next_(); + /// Extra code for start(). + void start_(); + private: + /// Twice the size of the image border. unsigned border_x2_; + /// Row offset. unsigned row_offset_; + /// End of the current row. mln_qlf_value(I)* eor_; + + using super_::image_; }; @@ -94,14 +103,21 @@ /// Go to the next pixel. void next_(); + /// Extra code for start(). + void start_(); + private: /// Twice the size of the image border. unsigned border_x2_; + /// Row offset. unsigned row_offset_; + /// Beginning of the current row. mln_qlf_value(I)* bor_; + + using super_::image_; }; @@ -117,8 +133,7 @@ fwd_pixter2d<I>::fwd_pixter2d(I& image) : super_(image), border_x2_(2 * image.border()), - row_offset_(image.bbox().ncols() + border_x2_), - eor_(& opt::at(image, geom::min_row(image), geom::max_col(image)) + 1) + row_offset_(image.bbox().ncols() + border_x2_) { mln_precondition(image.is_valid()); } @@ -136,6 +151,14 @@ } } + template <typename I> + inline + void + fwd_pixter2d<I>::start_() + { + eor_ = & opt::at(image_, geom::min_row(image_), geom::max_col(image_)) + 1; + } + /*------------------. | fwd_pixter2d<I>. | @@ -146,8 +169,7 @@ bkd_pixter2d<I>::bkd_pixter2d(I& image) : super_(image), border_x2_(2 * image.border()), - row_offset_(image.bbox().ncols() + border_x2_), - bor_(& opt::at(image, geom::max_row(image), geom::min_col(image)) - 1) + row_offset_(image.bbox().ncols() + border_x2_) { mln_precondition(image.is_valid()); } @@ -165,6 +187,14 @@ } } + template <typename I> + inline + void + bkd_pixter2d<I>::start_() + { + bor_ = & opt::at(image_, geom::max_row(image_), geom::min_col(image_)) - 1; + } + #endif // ! MLN_INCLUDE_ONLY } // end of namespace mln Index: mln/core/pixter3d.hh --- mln/core/pixter3d.hh (revision 3228) +++ mln/core/pixter3d.hh (working copy) @@ -30,13 +30,15 @@ # define MLN_CORE_PIXTER3D_HH /// \file mln/core/pixter3d.hh -/// \brief Pixel iterators on a 3-D image with border. +/// +/// Pixel iterators on a 3D image with border. # include <mln/core/internal/pixel_iterator_base.hh> # include <mln/core/alias/point3d.hh> # include <mln/geom/size3d.hh> # include <mln/opt/at.hh> + namespace mln { @@ -62,22 +64,33 @@ /// Go to the next pixel. void next_(); + /// Extra code for start(). + void start_(); + private: + /// Twice the size of the image border. const unsigned border_x2_; + /// Row offset. const unsigned row_offset_; + /// End of the current row. mln_qlf_value(I)* eor_; /// Next slice offset. const unsigned next_sli_offset_; + /// Next slice offset for row. const unsigned next_srow_offset_; + /// Slice offset. const unsigned sli_offset_; + /// End of the current slice. mln_qlf_value(I)* eos_; + + using super_::image_; }; @@ -103,22 +116,33 @@ /// Go to the next pixel. void next_(); + /// Extra code for start(). + void start_(); + private: + /// Twice the size of the image border. const unsigned border_x2_; + /// Row offset. const unsigned row_offset_; + /// Beginning of the current row. mln_qlf_value(I)* bor_; /// Next slice offset. const unsigned next_sli_offset_; + /// Next slice offset for row. const unsigned next_srow_offset_; + /// Slice offset. const unsigned sli_offset_; + /// Beginning of the current slice. mln_qlf_value(I)* bos_; + + using super_::image_; }; @@ -134,16 +158,10 @@ : super_(image), border_x2_(2 * image.border()), row_offset_(image.bbox().ncols() + border_x2_), - eor_(& opt::at(image, geom::min_sli(image), - geom::min_row(image), - geom::max_col(image)) + 1), next_sli_offset_(row_offset_ * border_x2_ + border_x2_), next_srow_offset_(next_sli_offset_ + image.bbox().ncols()), sli_offset_((image.bbox().ncols() + border_x2_) * - (image.bbox().nrows() + border_x2_)), - eos_(& opt::at(image, geom::min_sli(image), - geom::max_row(image), - geom::max_col(image)) + 1) + (image.bbox().nrows() + border_x2_)) { mln_precondition(image.is_valid()); } @@ -151,6 +169,21 @@ template <typename I> inline void + fwd_pixter3d<I>::start_() + { + eor_ = & opt::at(image_, + geom::min_sli(image_), + geom::min_row(image_), + geom::max_col(image_)) + 1; + eos_ = & opt::at(image_, + geom::min_sli(image_), + geom::max_row(image_), + geom::max_col(image_)) + 1; + } + + template <typename I> + inline + void fwd_pixter3d<I>::next_() { ++this->value_ptr_; @@ -178,16 +211,10 @@ : super_(image), border_x2_(2 * image.border()), row_offset_(image.bbox().ncols() + border_x2_), - bor_(& opt::at(image, geom::max_sli(image), - geom::max_row(image), - geom::min_col(image)) - 1), next_sli_offset_(row_offset_ * border_x2_ + border_x2_), next_srow_offset_(next_sli_offset_ + image.bbox().ncols()), sli_offset_((image.bbox().ncols() + border_x2_) * - (image.bbox().nrows() + border_x2_)), - bos_(& opt::at(image, geom::max_sli(image), - geom::min_row(image), - geom::min_col(image)) - 1) + (image.bbox().nrows() + border_x2_)) { mln_precondition(image.is_valid()); } @@ -195,6 +222,21 @@ template <typename I> inline void + bkd_pixter3d<I>::start_() + { + bor_ = & opt::at(image_, + geom::max_sli(image_), + geom::max_row(image_), + geom::min_col(image_)) - 1; + bos_ = & opt::at(image_, + geom::max_sli(image_), + geom::min_row(image_), + geom::min_col(image_)) - 1; + } + + template <typename I> + inline + void bkd_pixter3d<I>::next_() { --this->value_ptr_; @@ -215,4 +257,5 @@ } // end of namespace mln + #endif // ! MLN_CORE_PIXTER3D_HH Index: mln/core/dpoints_pixter.hh --- mln/core/dpoints_pixter.hh (revision 3228) +++ mln/core/dpoints_pixter.hh (working copy) @@ -33,6 +33,8 @@ /// /// \brief Definition of forward and backward mln::dpoint-based /// iterators for pixels iterations. +/// +/// \todo In ::init_ use offsets_wrt (defined in concept/window.hh). # include <cassert> # include <vector> Index: mln/core/internal/pixel_iterator_base.hh --- mln/core/internal/pixel_iterator_base.hh (revision 3228) +++ mln/core/internal/pixel_iterator_base.hh (working copy) @@ -30,12 +30,14 @@ # define MLN_CORE_INTERNAL_PIXEL_ITERATOR_BASE_HH /// \file mln/core/internal/pixel_iterator_base.hh -/// \brief Base classes factoring code for pixel iterator classes. +/// +/// Base classes factoring code for pixel iterator classes. # include <mln/core/concept/pixel_iterator.hh> # include <mln/core/internal/pixel_impl.hh> # include <mln/core/trait/qlf_value.hh> + namespace mln { @@ -58,10 +60,15 @@ pixel_iterator_base_(I& image); protected: + /// Beginning of the image. mln_qlf_value(I)* boi_; + /// End of the image (past-the-end). mln_qlf_value(I)* eoi_; + + /// Default impl is no-op. + void start_(); }; @@ -76,6 +83,7 @@ typedef pixel_iterator_base_<I, E> super_; public: + /// Manipulation /// \{ /// Start an iteration. @@ -87,6 +95,7 @@ /// \} protected: + /// Constructor. forward_pixel_iterator_base_(I& image); }; @@ -114,13 +123,16 @@ /// \} protected: + /// Constructor. backward_pixel_iterator_base_(I& image); }; + #ifndef MLN_INCLUDE_ONLY + /*---------------------------------------. | internal::pixel_iterator_base_<I, E>. | `---------------------------------------*/ @@ -137,6 +149,14 @@ exact(*this).invalidate(); } + template <typename I, typename E> + inline + void + pixel_iterator_base_<I, E>::start_() + { + // Default impl is no-op. + } + /*-----------------------------------------------. | internal::forward_pixel_iterator_base_<I, E>. | @@ -155,6 +175,7 @@ forward_pixel_iterator_base_<I, E>::start() { this->value_ptr_ = this->boi_ + 1; + exact(this)->start_(); } template <typename I, typename E> @@ -191,6 +212,7 @@ backward_pixel_iterator_base_<I, E>::start() { this->value_ptr_ = this->eoi_ - 1; + exact(this)->start_(); } template <typename I, typename E> Index: mln/core/internal/pixel_impl.hh --- mln/core/internal/pixel_impl.hh (revision 3228) +++ mln/core/internal/pixel_impl.hh (working copy) @@ -1,4 +1,5 @@ -// Copyright (C) 2007, 2008 EPITA Research and Development Laboratory (LRDE) +// Copyright (C) 2007, 2008 EPITA Research and Development Laboratory +// (LRDE) // // This file is part of the Olena Library. This library is free // software; you can redistribute it and/or modify it under the terms @@ -32,9 +33,13 @@ /// /// Define a couple of implementation classes to provide methods /// to classes of generalized pixels. +/// +/// \todo Clean-up code. # include <mln/core/concept/image.hh> # include <mln/core/internal/force_exact.hh> +# include <mln/util/pix.hh> + namespace mln @@ -43,11 +48,83 @@ namespace internal { + // We indeed have to handle the couple of cases when I is fastest + // or is not. Justification: mln::pixel derives from pixel_impl_ + // and is a general purpose pixel class; it can be used on any + // image whatever it is a fastest one or not. + + template <bool is_fastest, typename I, typename E> + class pixel_impl_base_; + + + template <typename I, typename E> + struct pixel_impl_base_< false, I, E > // I is not fastest. + { + typedef mlc_if(mlc_is_const(I), const mln_value(I), mln_value(I)) value_ptr_t; + + pixel_impl_base_(I& image, value_ptr_t* value_ptr) + : image_(image), + value_ptr_(value_ptr) + { + } + + protected: + + /// Image associated to the iterator + I& image_; + + /// Current pixel / value + value_ptr_t* value_ptr_; + }; + + + template <typename I, typename E> + struct pixel_impl_base_< true, I, E > // I is fastest => extra interface. + { + typedef mlc_if(mlc_is_const(I), const mln_value(I), mln_value(I)) value_ptr_t; + typedef mlc_unconst(I) unconst_image_t; + + pixel_impl_base_(I& image, value_ptr_t* value_ptr) + : image_(image), + value_ptr_(value_ptr) + { + } + + unsigned offset() const + { + return value_ptr_ - image_.buffer(); + } + + operator util::pix<unconst_image_t>() const + { + util::pix<unconst_image_t> tmp(image_, image_.point_at_index(offset())); + return tmp; + } + + protected: + + /// Image associated to the iterator. + I& image_; + + /// Current pixel / value. + value_ptr_t* value_ptr_; + }; + + /// Implementation class to equip generalized pixel /// classes based on mutable images. + /// template <typename I, typename E> class pixel_impl_ - { + + : public pixel_impl_base_< mlc_is(mln_trait_image_speed(I), + trait::image::speed::fastest)::value, + I, E > + { + typedef pixel_impl_base_< mlc_is(mln_trait_image_speed(I), + trait::image::speed::fastest)::value, + I, E > super_; + public: /// Image type. @@ -79,11 +156,11 @@ protected: - /// Image associated to the iterator - I& image_; + /// Image associated to the iterator. + using super_::image_; - /// Current pixel / value - value* value_ptr_; + /// Current pixel / value. + using super_::value_ptr_; /// Constructor pixel_impl_(I& image); @@ -95,9 +172,18 @@ /// Implementation class to equip generalized pixel /// classes based on constant images. + /// template <typename I, typename E> class pixel_impl_< const I, E > - { + + : public pixel_impl_base_< mlc_is(mln_trait_image_speed(I), + trait::image::speed::fastest)::value, + const I, E > + { + typedef pixel_impl_base_< mlc_is(mln_trait_image_speed(I), + trait::image::speed::fastest)::value, + const I, E > super_; + public: /// Image type. @@ -121,13 +207,14 @@ /// Address of the current iterator value/pixel. const value** address_() const; + protected: - /// Image associated to the iterator - const I& image_; + /// Image associated to the iterator. + using super_::image_; - /// Current pixel / value - const value* value_ptr_; + /// Current pixel / value. + using super_::value_ptr_; /// Constructor pixel_impl_(const I& image); @@ -152,8 +239,7 @@ template <typename I, typename E> inline pixel_impl_<I, E>::pixel_impl_(I& image) : - image_(image), - value_ptr_(0) + super_(image, 0) { } @@ -206,8 +292,7 @@ template <typename I, typename E> inline pixel_impl_<const I, E>::pixel_impl_(const I& image) : - image_(image), - value_ptr_(0) + super_(image, 0) { } Index: mln/core/pixel.hh --- mln/core/pixel.hh (revision 3228) +++ mln/core/pixel.hh (working copy) @@ -1,4 +1,5 @@ -// Copyright (C) 2007 EPITA Research and Development Laboratory +// Copyright (C) 2007, 2008 EPITA Research and Development Laboratory +// (LRDE) // // This file is part of the Olena Library. This library is free // software; you can redistribute it and/or modify it under the terms @@ -28,10 +29,13 @@ #ifndef MLN_CORE_PIXEL_HH # define MLN_CORE_PIXEL_HH -/*! \file mln/core/pixel.hh - * - * \brief Definition of the generic pixel class mln::pixel. - */ +/// \file mln/core/pixel.hh +/// +/// Definition of the generic pixel class mln::pixel. +/// +/// \todo Answer these questions: +/// - why do we have 2 classes (mln::pixel and mln::util::pix)? +/// - what about keeping only one of both? # include <mln/core/concept/generalized_pixel.hh> # include <mln/core/internal/pixel_impl.hh> Index: mln/core/concept/window.hh --- mln/core/concept/window.hh (revision 3228) +++ mln/core/concept/window.hh (working copy) @@ -46,6 +46,7 @@ # include <mln/core/site_set/p_array.hh> # include <mln/core/internal/geom_bbox.hh> // For use in convert::from_to. # include <mln/convert/from_to.hxx> +# include <mln/util/array.hh> @@ -70,8 +71,9 @@ namespace mln { - // Forward declaration. + // Forward declarations. template <typename E> struct Window; + template <typename E> struct Image; // Window category flag type. @@ -114,6 +116,12 @@ std::ostream& operator<<(std::ostream& ostr, const Window<W>& win); + // FIXME: Move as a method of Image? + template <typename I, typename W> + util::array<int> + offsets_wrt(const Image<I>& ima, const Window<W>& win); + + namespace convert { @@ -309,6 +317,28 @@ } + template <typename I, typename W> + inline + util::array<int> + offsets_wrt(const Image<I>& ima_, const Window<W>& win_) + { + mln_is_simple_window(W)::check(); + + const I& ima = exact(ima_); + const W& win = exact(win_); + mln_precondition(ima.is_valid()); + // mln_precondition(win.is_valid()); + + util::array<int> arr; + unsigned n = win.size(); + + for (unsigned i = 0; i < n; ++i) + arr.append(ima.delta_index(win.dp(i))); + + return arr; + } + + namespace convert { Index: mln/core/concept/neighborhood.hh --- mln/core/concept/neighborhood.hh (revision 3228) +++ mln/core/concept/neighborhood.hh (working copy) @@ -33,14 +33,21 @@ /// /// Definition of the concept of mln::Neighborhood. -# include <mln/core/concept/object.hh> +# include <mln/core/concept/window.hh> # include <mln/trait/windows.hh> + +# define mln_is_simple_neighborhood(N) mln_is_simple_window(mln_window(N)) + + + + namespace mln { - // Fwd decl. + + // Forward declaration. template <typename E> struct Neighborhood; @@ -90,6 +97,12 @@ operator<<(std::ostream&ostr, const Neighborhood<N>& nbh); + // FIXME: Move as a method of Image? + template <typename I, typename N> + util::array<int> + offsets_wrt(const Image<I>& ima, const Neighborhood<N>& nbh); + + # ifndef MLN_INCLUDE_ONLY @@ -129,6 +142,21 @@ return ostr << exact(nbh).win(); } + template <typename I, typename N> + inline + util::array<int> + offsets_wrt(const Image<I>& ima_, const Neighborhood<N>& nbh_) + { + mln_is_simple_neighborhood(N)::check(); + + const I& ima = exact(ima_); + const N& nbh = exact(nbh_); + mln_precondition(ima.is_valid()); + // mln_precondition(nbh.is_valid()); + + return offsets_wrt(ima, nbh.win()); + } + # endif // ! MLN_INCLUDE_ONLY } // end of namespace mln Index: mln/morpho/closing_attribute.hh --- mln/morpho/closing_attribute.hh (revision 3228) +++ mln/morpho/closing_attribute.hh (working copy) @@ -34,6 +34,8 @@ /// Morphological attribute closing. /// /// \todo How to pass dynamic data (e.g., k of accu::rank) to the routine? +/// +/// \todo Add extension::adjust_fill. # include <mln/morpho/includes.hh> # include <mln/canvas/morpho/algebraic_union_find.hh> @@ -57,11 +59,20 @@ # ifndef MLN_INCLUDE_ONLY + + // Implementations. + namespace impl { + + // Generic version. + + namespace generic + { + template <typename I, typename A_> - struct closing_attribute_t + struct closing_attribute_functor_t { // requirements from mln::canvas::morpho::algebraic_union_find @@ -89,7 +100,7 @@ // end of requirements - closing_attribute_t(const Image<I>& input, mln_result(A) lambda) + closing_attribute_functor_t(const Image<I>& input, mln_result(A) lambda) : lambda(lambda), s(level::sort_psites_increasing(exact(input))) { @@ -97,10 +108,137 @@ }; + + template <typename A, typename I, typename N> + inline + mln_concrete(I) + closing_attribute(const Image<I>& input, const Neighborhood<N>& nbh, + mln_result(A) lambda) + { + trace::entering("morpho::impl::generic::closing_attribute"); + + mln_precondition(exact(input).is_valid()); + + typedef closing_attribute_functor_t<I, A> F; + F f(input, lambda); + mln_concrete(I) output = canvas::morpho::impl::generic::algebraic_union_find(input, nbh, f); + + mln_postcondition(output >= input); + + trace::exiting("morpho::impl::generic::closing_attribute"); + return output; + } + + + } // end of namespace mln::morpho::impl::generic + + + + // "Fastest" version. + + + template <typename I, typename A_> + struct closing_attribute_fastest_functor_t + { + // requirements from mln::canvas::morpho::algebraic_union_find + + typedef A_ A; + typedef mln_psite(I) P; + typedef p_array<P> S; + + mln_result(A) lambda; + const S s; + + void init() + { + // FIXME: border::fill(input, mln_max(mln_value(I))); + } + + bool is_active(const A& attr) const + { + return attr.to_result() < lambda; + } + + void inactivate(A& attr) + { + attr.set_value(lambda); + } + + // end of requirements + + closing_attribute_fastest_functor_t(const Image<I>& input, mln_result(A) lambda) + : lambda(lambda), + s(level::sort_psites_increasing(exact(input))) + { + } + + }; + + + template <typename A, typename I, typename N> + inline + mln_concrete(I) + closing_attribute_fastest(const Image<I>& input, const Neighborhood<N>& nbh, + mln_result(A) lambda) + { + trace::entering("morpho::impl::closing_attribute_fastest"); + + mln_precondition(exact(input).is_valid()); + + typedef impl::closing_attribute_fastest_functor_t<I, A> F; + F f(input, lambda); + mln_concrete(I) output = canvas::morpho::impl::algebraic_union_find_fastest(input, nbh, f); + + mln_postcondition(output >= input); + + trace::exiting("morpho::impl::closing_attribute_fastest"); + return output; + } + + } // end of namespace mln::morpho::impl + // Dispatch. + + namespace internal + { + + template <typename A, typename I, typename N> + inline + mln_concrete(I) + closing_attribute_dispatch(trait::image::speed::any, + const Image<I>& input, const Neighborhood<N>& nbh, + mln_result(A) lambda) + { + return impl::generic::closing_attribute<A>(input, nbh, lambda); + } + +// template <typename A, typename I, typename N> +// inline +// mln_concrete(I) +// closing_attribute_dispatch(trait::image::speed::fastest, +// const Image<I>& input, const Neighborhood<N>& nbh, +// mln_result(A) lambda) +// { +// return impl::closing_attribute_fastest<A>(input, nbh, lambda); +// } + + template <typename A, typename I, typename N> + inline + mln_concrete(I) + closing_attribute_dispatch(const Image<I>& input, const Neighborhood<N>& nbh, + mln_result(A) lambda) + { + return closing_attribute_dispatch<A>(mln_trait_image_speed(I)(), + input, nbh, lambda); + } + + } // end of namespace internal + + + // Facade. template <typename A, typename I, typename N> @@ -113,9 +251,7 @@ mln_precondition(exact(input).is_valid()); - typedef impl::closing_attribute_t<I, A> F; - F f(input, lambda); - mln_concrete(I) output = canvas::morpho::algebraic_union_find(input, nbh, f); + mln_concrete(I) output = internal::closing_attribute_dispatch<A>(input, nbh, lambda); mln_postcondition(output >= input); @@ -124,6 +260,9 @@ } + // Facade. + + # endif // ! MLN_INCLUDE_ONLY } // end of namespace mln::morpho Index: mln/morpho/opening_attribute.hh --- mln/morpho/opening_attribute.hh (revision 3228) +++ mln/morpho/opening_attribute.hh (working copy) @@ -32,6 +32,8 @@ /// \file mln/morpho/opening_attribute.hh /// /// Morphological attribute opening. +/// +/// \todo Add extension::adjust_fill. # include <mln/morpho/includes.hh> # include <mln/canvas/morpho/algebraic_union_find.hh> Index: mln/canvas/morpho/algebraic_union_find.hh --- mln/canvas/morpho/algebraic_union_find.hh (revision 3228) +++ mln/canvas/morpho/algebraic_union_find.hh (working copy) @@ -51,6 +51,11 @@ namespace impl { + // Generic version. + + namespace generic + { + template <typename I> inline mln_psite(I) @@ -69,7 +74,7 @@ const Neighborhood<N>& nbh_, F& f) { - trace::entering("canvas::morpho::algebraic_union_find"); + trace::entering("canvas::morpho::impl::generic::algebraic_union_find"); // FIXME: Tests? @@ -190,11 +195,134 @@ and add in init: mln::data::fill(output, input); */ - trace::exiting("canvas::morpho::algebraic_union_find"); + trace::exiting("canvas::morpho::impl::generic::algebraic_union_find"); + + return output; + } + + } // end of namespace mln::canvas::morpho::impl::generic + + + + // Fastest version. + + template <typename I> + inline + unsigned + find_root_fastest(I& parent, unsigned x) + { + if (parent.element(x) == x) + return x; + else + return parent.element(x) = find_root(parent, parent.element(x)); + } + + + template <typename I, typename N, typename F> + inline + mln_concrete(I) + algebraic_union_find_fastest(const Image<I>& input_, + const Neighborhood<N>& nbh_, + F& f) + { + trace::entering("canvas::morpho::impl::algebraic_union_find_fastest"); + + // FIXME: Tests? + + typedef typename F::S S; + typedef typename F::A A; + + const I& input = exact(input_); + const N& nbh = exact(nbh_); + + mln_concrete(I) output; + initialize(output, input); + + // Local type. + typedef mln_psite(I) P; + + // Auxiliary data. + mln_ch_value(I, bool) deja_vu; + mln_ch_value(I, bool) activity; + mln_ch_value(I, unsigned) parent; + mln_ch_value(I, A) data; + + // Initialization. + { + initialize(deja_vu, input); + mln::data::fill(deja_vu, false); + initialize(activity, input); + mln::data::fill(activity, true); + initialize(parent, input); + mln::data::fill(parent, 0); + initialize(data, input); + f.init(); // init required. + } + + util::array<int> dp = offsets_wrt(input, nbh); + for (unsigned i = 0; i < dp.nelements(); ++i) + std::cout << dp[i] << ' '; + std::cout << std::endl; + + /* + + // First pass. + { + for (unsigned p = 0; p < f.s.size(); ++p) + mln_niter(N) n(nbh, p); + for_all(p) + { + // Make set. + { + parent(p) = p; + data(p).take_as_init(make::pix(input, p)); // FIXME: algebraic so p! + } + + for_all(n) + if (input.domain().has(n) && deja_vu(n)) + { + P r = find_root(parent, n); + if (r != p) + { + if (input(r) == input(p) || (activity(r) && f.is_active(data(r)))) + { + data(p).take(data(r)); + parent(r) = p; + if (activity(r) == false) + activity(p) = false; + } + else + { + activity(p) = false; + f.inactivate(data(p)); + } + } + } + deja_vu(p) = true; + } + } + + */ + + /* + + // Second pass. + { + mln_bkd_piter(S) p(f.s); + for_all(p) + if (parent(p) == p) // p is root. + output(p) = input(p); + else + output(p) = output(parent(p)); + } + + */ + trace::exiting("canvas::morpho::impl::algebraic_union_find_fastest"); return output; } + } // end of namespace mln::canvas::morpho::impl @@ -212,7 +340,29 @@ const Neighborhood<N>& nbh, F& f) { - return impl::algebraic_union_find(input, nbh, f); + return impl::generic::algebraic_union_find(input, nbh, f); + } + +// template <typename I, typename N, typename F> +// inline +// mln_concrete(I) +// algebraic_union_find_dispatch(trait::image::speed::fastest, +// const Image<I>& input, +// const Neighborhood<N>& nbh, +// F& f) +// { +// return impl::algebraic_union_find_fastest(input, nbh, f); +// } + + template <typename I, typename N, typename F> + inline + mln_concrete(I) + algebraic_union_find_dispatch(const Image<I>& input, + const Neighborhood<N>& nbh, + F& f) + { + return algebraic_union_find_dispatch(mln_trait_image_speed(I)(), + input, nbh, f); } } // end of namespace mln::canvas::morpho::internal @@ -228,8 +378,7 @@ const Neighborhood<N>& nbh, F& f) { - return internal::algebraic_union_find_dispatch(mln_trait_image_speed(I)(), - input, nbh, f); + return internal::algebraic_union_find_dispatch(input, nbh, f); } Index: mln/util/pix.hh --- mln/util/pix.hh (revision 3228) +++ mln/util/pix.hh (working copy) @@ -32,6 +32,13 @@ /// \file mln/util/pix.hh /// /// Definition of an instant pix. +/// +/// \todo Rename as util::pixel. +/// +/// \todo Think about separating this class between +/// util::pixel<"mutable" I> and util::pixel<const I>. +/// +/// \todo Look at the todo entry of mln/core/pixel.hh. # include <mln/core/concept/image.hh>