https://svn.lrde.epita.fr/svn/oln/trunk/milena Index: ChangeLog from Thierry Geraud <thierry.geraud@lrde.epita.fr> Add fast pixel iterators on neighbors. * mln/core/internal/pixel_iterator_base.hh (boi_): Make it before-the-beginning (reverse of past-the-end). (start, is_valid): Update. * mln/core/line_piter.hh: Import super_::dim. * mln/core/box_piter.hh: Likewise. * mln/core/neighb.hh: Change inheritance to dpoints_base_. * mln/core/image2d_b.hh (bkd_pixter): Fix missing. (fwd_nixter, bkd_nixter): Likewise. * mln/core/pixter2d_b.hh (bkd_pixter2d_b): New. * mln/labeling/base.hh (base_fast_): New. * sandbox/duhamel/labeling_level.hh, * sandbox/duhamel/labeling_level_fast.cc, * sandbox/duhamel/canvas_labeling.hh: Update. mln/core/box_piter.hh | 10 + mln/core/image2d_b.hh | 28 ++++ mln/core/internal/pixel_iterator_base.hh | 8 - mln/core/line_piter.hh | 5 mln/core/neighb.hh | 4 mln/core/pixter2d_b.hh | 69 +++++++++++ mln/labeling/base.hh | 35 +++++ sandbox/duhamel/canvas_labeling.hh | 23 ++- sandbox/duhamel/labeling_level.hh | 184 ++++++++++++++++++------------- sandbox/duhamel/labeling_level_fast.cc | 20 +-- 10 files changed, 286 insertions(+), 100 deletions(-) Index: mln/core/internal/pixel_iterator_base.hh --- mln/core/internal/pixel_iterator_base.hh (revision 1126) +++ mln/core/internal/pixel_iterator_base.hh (working copy) @@ -86,16 +86,17 @@ { mln_precondition(image.has_data()); I& ima = this->image_; - boi_ = & ima( ima.domain().pmin() ); + boi_ = & ima( ima.domain().pmin() ) - 1; eoi_ = & ima( ima.domain().pmax() ) + 1; invalidate(); } + // FIXME: Remove cause dangerous when bkd!!! template <typename I, typename E> void pixel_iterator_base_<I, E>::start() { - this->value_ptr_ = boi_; + this->value_ptr_ = boi_ + 1; } template <typename I, typename E> @@ -105,11 +106,12 @@ this->value_ptr_ = eoi_; } + // FIXME: Remove casue not optimal!!! template <typename I, typename E> bool pixel_iterator_base_<I, E>::is_valid() const { - return this->value_ptr_ != eoi_; + return this->value_ptr_ != eoi_ && this->value_ptr_ != boi_; } #endif // ! MLN_INCLUDE_ONLY Index: mln/core/line_piter.hh --- mln/core/line_piter.hh (revision 1126) +++ mln/core/line_piter.hh (working copy) @@ -46,8 +46,13 @@ template <typename P> class line_piter_ : public internal::point_iterator_base_< P, line_piter_<P> > { + typedef line_piter_<P> self_; + typedef internal::point_iterator_base_< P, self_ > super_; public: + // Make definitions from super class available. + enum { dim = super_::dim }; + /*! \brief Constructor. * * \param[in] b A box. Index: mln/core/neighb.hh --- mln/core/neighb.hh (revision 1126) +++ mln/core/neighb.hh (working copy) @@ -34,7 +34,7 @@ */ # include <mln/core/concept/neighborhood.hh> -# include <mln/core/internal/set_of.hh> +# include <mln/core/internal/dpoints_base.hh> # include <mln/core/dpoint.hh> @@ -53,7 +53,7 @@ */ template <typename D> struct neighb_ : public Neighborhood< neighb_<D> >, - public internal::set_of_<D> + public internal::dpoints_base_<D, neighb_<D> > { /// Dpoint associated type. typedef D dpoint; Index: mln/core/image2d_b.hh --- mln/core/image2d_b.hh (revision 1126) +++ mln/core/image2d_b.hh (working copy) @@ -508,7 +508,13 @@ template <typename T> struct bkd_pixter< image2d_b<T> > { - typedef internal::fixme ret; + typedef bkd_pixter2d_b< image2d_b<T> > ret; + }; + + template <typename T> + struct bkd_pixter< const image2d_b<T> > + { + typedef bkd_pixter2d_b< const image2d_b<T> > ret; }; // qixter @@ -531,6 +537,26 @@ typedef internal::fixme ret; }; + // nixter + + template <typename T, typename N> + struct fwd_nixter< image2d_b<T>, N > + { + typedef dpoints_fwd_pixter< image2d_b<T> > ret; + }; + + template <typename T, typename N> + struct fwd_nixter< const image2d_b<T>, N > + { + typedef dpoints_fwd_pixter< const image2d_b<T> > ret; + }; + + template <typename T, typename N> + struct bkd_nixter< image2d_b<T>, N > + { + typedef internal::fixme ret; + }; + } // end of namespace mln::trait } // end of namespace mln Index: mln/core/box_piter.hh --- mln/core/box_piter.hh (revision 1126) +++ mln/core/box_piter.hh (working copy) @@ -49,8 +49,13 @@ template <typename P> class box_fwd_piter_ : public internal::point_iterator_base_< P, box_fwd_piter_<P> > { + typedef box_fwd_piter_<P> self_; + typedef internal::point_iterator_base_< P, self_ > super_; public: + // Make definitions from super class available. + enum { dim = super_::dim }; + /*! \brief Constructor. * * \param[in] b A box. @@ -94,8 +99,13 @@ template <typename P> class box_bkd_piter_ : public internal::point_iterator_base_< P, box_bkd_piter_<P> > { + typedef box_bkd_piter_<P> self_; + typedef internal::point_iterator_base_< P, self_ > super_; public: + // Make definitions from super class available. + enum { dim = super_::dim }; + /*! \brief Constructor. * * \param[in] b A box. Index: mln/core/pixter2d_b.hh --- mln/core/pixter2d_b.hh (revision 1126) +++ mln/core/pixter2d_b.hh (working copy) @@ -74,11 +74,47 @@ }; - // FIXME: bkd_pixter2d_b + + template <typename I> + class bkd_pixter2d_b : public internal::pixel_iterator_base_< I, bkd_pixter2d_b<I> > + { + typedef internal::pixel_iterator_base_< I, bkd_pixter2d_b<I> > super_; + + public: + + /// Image type. + typedef I image; + + /*! \brief Constructor. + * + * \param[in] image Image to iterate over its pixels. + */ + bkd_pixter2d_b(I& image); + + /// Go to the next pixel. + void next_(); + + 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_; + }; + + #ifndef MLN_INCLUDE_ONLY + // Fwd. + template <typename I> fwd_pixter2d_b<I>::fwd_pixter2d_b(I& image) : super_(image) @@ -101,6 +137,37 @@ } } + // Bkd. + + template <typename I> + bkd_pixter2d_b<I>::bkd_pixter2d_b(I& image) : + super_(image) + { + mln_precondition(image.has_data()); + border_x2_ = 2 * image.border(); + row_offset_ = geom::max_col(image) - geom::min_col(image) + 1 + border_x2_; + bor_ = & image.at(geom::max_row(image), geom::min_col(image)) - 1; + } + + template <typename I> + void + bkd_pixter2d_b<I>::next_() + { + --this->value_ptr_; + if (this->value_ptr_ = bor_ && this->value_ptr_ != this->boi_) + { + this->value_ptr_ -= border_x2_; + bor_ -= row_offset_; + } + } + + template <typename I> + void + bkd_pixter2d_b<I>::start() + { + this->value_ptr_ = this->eoi_ - 1; + } + #endif // ! MLN_INCLUDE_ONLY } // end of namespace mln Index: mln/labeling/base.hh --- mln/labeling/base.hh (revision 1126) +++ mln/labeling/base.hh (working copy) @@ -50,6 +50,7 @@ { /// Base class for labeling functors. + template <typename I_, typename N_, typename O_> struct base_ { @@ -82,6 +83,40 @@ void merge_attr(const P&, const P&) {} }; + + /// Base class for labeling functors on fast images. + + template <typename I_, typename N_, typename O_> + struct base_fast_ + { + typedef I_ I; + typedef N_ N; + typedef O_ O; + + const I& input; + const N& nbh; + O& output; + + mln_value(O_) nlabels; + bool status; + + base_fast_(const I_& input, const N_& nbh, O_& output) + : input(input), + nbh(nbh), + output(output) + { + } + + // Defaults. + + bool handles(unsigned) const { return true; } + bool labels(unsigned) const { return true; } + void init() {} + void do_no_union(unsigned, unsigned) {} + void init_attr(unsigned) {} + void merge_attr(unsigned, unsigned) {} + }; + } // end of namespace mln::labeling::impl # endif // ! MLN_INCLUDE_ONLY Index: sandbox/duhamel/labeling_level.hh --- sandbox/duhamel/labeling_level.hh (revision 1126) +++ sandbox/duhamel/labeling_level.hh (working copy) @@ -25,8 +25,8 @@ // reasons why the executable file might be covered by the GNU General // Public License. -#ifndef MLN_LABELING_LEVEL_HH -# define MLN_LABELING_LEVEL_HH +#ifndef SANDBOX_MLN_LABELING_LEVEL_HH +# define SANDBOX_MLN_LABELING_LEVEL_HH /*! \file mln/labeling/level.hh * @@ -35,113 +35,149 @@ */ # include <mln/labeling/base.hh> -# include <mln/level/fill.hh> +# include <mln/debug/println.hh> +# include <mln/core/window2d.hh> +# include <mln/convert/to_window.hh> namespace mln { - namespace labeling + + template <typename F> + struct labeling_fast_try2 { + F& f; - /*! Connected component labeling of the image objects at a given - * level. - * - * \param[in] input The input image. - * \param[in] val The level to consider for the labeling. - * \param[in] nbh The neighborhood. - * \param[out] output The label image. - * \param[out] nlabels The number of labels. - * - * \return Succeed or not. - */ - template <typename I, typename N, typename O> - bool level(const Image<I>& input, const mln_value(I)& val, const Neighborhood<N>& nbh, - Image<O>& output, unsigned& nlabels); + typedef typename F::I I; + typedef typename F::N N; + typedef typename F::O O; + + // aux: + mln_ch_value(O, unsigned) parent; + + labeling_fast_try2(F& f) + : f(f), + parent(f.output.domain(), f.input.border()) + { + run(); + } + + void run() + { + // init + { + f.nlabels = 0; + f.init(); + } + // first pass + { + mln_bkd_pixter(const I) p(f.input); + mln_nixter(const I, N) n(p, f.nbh); + for_all(p) if (f.handles(p)) + { + make_set(p); + for_all(n) if (n > p) + if (f.equiv(n, p)) + do_union(n, p); + else + f.do_no_union(n, p); + } + } + // second pass + { + mln_fwd_pixter(const I) p(f.input); + for_all(p) if (f.handles(p)) + { + if (is_root(p)) + { + if (f.labels(p)) + { + if (f.nlabels = mln_max(mln_value(O))) + { + f.status = false; + return; + } + f.output[p] = ++f.nlabels; + } + } + else + f.output[p] = f.output[parent[p]]; + } + f.status = true; + } -# ifndef MLN_INCLUDE_ONLY + } // end of run() - namespace impl + void make_set(unsigned p) { + parent[p] = p; + f.init_attr(p); + } + + bool is_root(unsigned p) const + { + return parent[p] = p; + } + + unsigned find_root(unsigned x) + { + if (parent[x] = x) + return x; + else + return parent[x] = find_root(parent[x]); + } + + void do_union(unsigned n, unsigned p) + { + unsigned r = find_root(n); + if (r != p) + { + parent[r] = p; + f.merge_attr(r, p); + } + } + + }; + - // Functors. template <typename I_, typename N_, typename O_> - struct level_t : base_<I_,N_,O_> + struct level_fast_t : mln::labeling::impl::base_fast_<I_,N_,O_> { typedef mln_point(I_) P; - // requirements from mln::canvas::labeling: - - typedef mln_pset(I_) S; - const S& s; + // typedef mln_pset(I_) S; + // const S& s; void init() { mln::level::fill(this->output, 0); } - bool handles(const P& p) const { return input(p) = val; } - bool equiv(const P& n, const P&) const { return input(n) = val; } - - // end of requirements + bool handles(unsigned p) const { return input[p] = val; } + bool equiv(unsigned n, unsigned) const { return input[n] = val; } const mln_value(I_)& val; - level_t(const I_& input, const mln_value(I_)& val, const N_& nbh, O_& output) - : base_<I_,N_,O_>(input, nbh, output), - s(input.domain()), + level_fast_t(const I_& input, const mln_value(I_)& val, const N_& nbh, O_& output) + : mln::labeling::impl::base_fast_<I_,N_,O_>(input, nbh, output), + // s(input.domain()), val(val) {} }; - // Routines. template <typename I, typename N, typename O> - bool level_(const Image<I>& input, const mln_value(I)& val, const Neighborhood<N>& nbh, - Image<O>& output, unsigned& nlabels) + bool labeling_level_fast(const Fast_Image<I>& input, const mln_value(I)& val, const Neighborhood<N>& nbh, + Fast_Image<O>& output, unsigned& nlabels) { - typedef impl::level_t<I,N,O> F; + typedef level_fast_t<I,N,O> F; F f(exact(input), val, exact(nbh), exact(output)); - canvas::labeling<F> run(f); + labeling_fast_try2<F> run(f); nlabels = f.nlabels; return f.status; } - // FIXME: Add fast versions. - - // FIXME (ADD) - // - template <typename I, typename N, typename O> - bool level_(const Fast_Image<I>& input, const mln_value(I)& val, const Neighborhood<N>& nbh, - Image<O>& output, unsigned& nlabels) - { - typedef impl::level_t<I,N,O> F; - F f(exact(input), val, exact(nbh), exact(output)); - canvas::labeling_fast<F> run(f); - nlabels = f.nlabels; - return f.status; - } - - // - //END FIXME (ADD) - - } // end of namespace mln::labeling::impl - - - // Facade. - - template <typename I, typename N, typename O> - bool level(const Image<I>& input, const mln_value(I)& val, const Neighborhood<N>& nbh, - Image<O>& output, unsigned& nlabels) - { - mln_precondition(exact(output).domain() = exact(input).domain()); - return impl::level_(exact(input), val, nbh, output, nlabels); - } - -# endif // ! MLN_INCLUDE_ONLY - - } // end of namespace mln::labeling - } // end of namespace mln -#endif // ! MLN_LABELING_LEVEL_HH +#endif // ! SANDBOX_MLN_LABELING_LEVEL_HH Index: sandbox/duhamel/labeling_level_fast.cc --- sandbox/duhamel/labeling_level_fast.cc (revision 1126) +++ sandbox/duhamel/labeling_level_fast.cc (working copy) @@ -37,7 +37,8 @@ #include <mln/io/pgm/load.hh> #include <mln/io/pgm/save.hh> -#include <mln/labeling/foreground.hh> +#include "labeling_level.hh" +#include <mln/debug/iota.hh> #include <mln/debug/println_with_border.hh> #include "paste.hh" @@ -49,18 +50,19 @@ using namespace mln; using value::int_u8; - image2d_b<value::int_u8> i1(3, 3); - image2d_b<value::int_u8> out (i1.domain ()); + unsigned border = 1; - level::fill_opt2(i1, 8); - - for (int i = 0; i < 81; ++i) - i1[i] = (i * 4452) % 255; + image2d_b<value::int_u8> i1(3, 3, border); + debug::iota(i1); + i1[12] = i1[18] = 2; debug::println_with_border(i1); unsigned n; - labeling::level(i1, true, c4(), out, n); - printf ("\nn=%u\n", n); + image2d_b<value::int_u8> out(i1.domain(), border); + labeling_level_fast(i1, 2, c4(), out, n); + + std::cout << "n = " << n << std::endl; + debug::println(out); // image2d_b<int_u8> // lena = io::pgm::load("../../img/tiny.pgm"), Index: sandbox/duhamel/canvas_labeling.hh --- sandbox/duhamel/canvas_labeling.hh (revision 1126) +++ sandbox/duhamel/canvas_labeling.hh (working copy) @@ -78,17 +78,20 @@ { mln_fwd_pixter(const I) p(f.input); // p is a pixel - W win = convert::to_window(f.nbh); - mln_qixter(const I, W) q(f.input, win, p); +// W win = convert::to_window(f.nbh); +// mln_qixter(const I, W) q(f.input, win, p); + +// mln_nixter(const I, N) n(f.input, f.nbh, p); - for_all(p) // if (f.handles(p)) + for_all(p) if (f.handles(p)) { make_set(p); - for_all(q) - if (f.equiv(n, p)) - do_union(n, p); - else - f.do_no_union(n, p); +// for_all(n) +// if (f.deja_vu(n)) +// if (f.equiv(n, p)) +// do_union(n, p); +// else +// f.do_no_union(n, p); } } @@ -128,7 +131,7 @@ return parent[p] = p; } - point find_root(const unsigned& x) + unsigned find_root(const unsigned& x) { if (parent[x] = x) return x; @@ -138,7 +141,7 @@ void do_union(const unsigned& n, const unsigned& p) { - point r = find_root(n); + unsigned r = find_root(n); if (r != p) { parent[r] = p;