[Olena-patches] milena r1234: Add labeling_fast in mln

URL: https://svn.lrde.epita.fr/svn/oln/trunk/milena ChangeLog: 2007-10-03 Guillaume Duhamel &lt;guillaume.duhamel(a)lrde.epita.fr&gt; Add labeling_fast in mln. * canvas/labeling.hh: New canvas for labeling fast. * convert/to_window.hh: New function to_upper_window. * labeling/level.hh: Add level_fast. --- canvas/labeling.hh | 107 ++++++++++++++++++++++++++++++++++++++++++++++++++- convert/to_window.hh | 20 ++++++++- labeling/level.hh | 47 ++++++++++++++++++++++ 3 files changed, 171 insertions(+), 3 deletions(-) Index: trunk/milena/mln/convert/to_window.hh =================================================================== --- trunk/milena/mln/convert/to_window.hh (revision 1233) +++ trunk/milena/mln/convert/to_window.hh (revision 1234) @@ -53,6 +53,10 @@ template <typename N> window<mln_dpoint(N)> to_window(const Neighborhood<N>& nbh); + /// Convert a neighborhood \p nbh into an upper window. + template <typename N> + window<mln_dpoint(N)> to_upper_window(const Neighborhood<N>& nbh); + /// Convert a binary image \p ima into a window. template <typename I> window<mln_dpoint(I)> to_window(const Image<I>& ima); @@ -77,8 +81,20 @@ window<D> win; mln_niter(N) n(nbh, P::zero); for_all(n) -// FIXME: pour Guillaume -// if (n < P::zero) + win.insert(n - P::zero); + return win; + } + + template <typename N> + window<mln_dpoint(N)> to_upper_window(const Neighborhood<N>& nbh_) + { + const N& nbh = exact(nbh_); + typedef mln_dpoint(N) D; + typedef mln_point(D) P; + window<D> win; + mln_niter(N) n(nbh, P::zero); + for_all(n) + if (n > P::zero) win.insert(n - P::zero); return win; } Index: trunk/milena/mln/canvas/labeling.hh =================================================================== --- trunk/milena/mln/canvas/labeling.hh (revision 1233) +++ trunk/milena/mln/canvas/labeling.hh (revision 1234) @@ -36,7 +36,7 @@ # include <mln/level/fill.hh> # include <mln/level/sort_points.hh> - +# include <mln/convert/to_window.hh> namespace mln { @@ -154,6 +154,111 @@ // FIXME: Fast version. + template <typename F> + struct labeling_fast + { + F& f; + + typedef typename F::I I; + typedef typename F::N N; + typedef typename F::O O; + + // aux: + mln_ch_value(O, unsigned) parent; + + labeling_fast(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); + + typedef window<mln_dpoint(I)> W; + W win = mln::convert::to_upper_window(f.nbh); + mln_qixter(const I, W) n(p, win); + + for_all(p) if (f.handles(p)) + { + make_set(p); + for_all(n) + 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; + } + + } // end of run() + + 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); + } + } + + }; + + } // end of namespace mln::canvas } // end of namespace mln Index: trunk/milena/mln/labeling/level.hh =================================================================== --- trunk/milena/mln/labeling/level.hh (revision 1233) +++ trunk/milena/mln/labeling/level.hh (revision 1234) @@ -34,10 +34,12 @@ * level. */ +# include <mln/core/concept/fast_image.hh> # include <mln/labeling/base.hh> # include <mln/level/fill.hh> + namespace mln { @@ -59,6 +61,9 @@ bool level(const Image<I>& input, const mln_value(I)& val, const Neighborhood<N>& nbh, Image<O>& output, unsigned& nlabels); + template <typename I, typename N, typename O> + bool level_fast(const Fast_Image<I>& input, const mln_value(I)& val, const Neighborhood<N>& nbh, + Fast_Image<O>& output, unsigned& nlabels); # ifndef MLN_INCLUDE_ONLY @@ -108,6 +113,40 @@ // FIXME: Add fast versions. + template <typename I_, typename N_, typename O_> + struct level_fast_t : labeling::impl::base_fast_<I_,N_,O_> + { + typedef mln_point(I_) P; + + // typedef mln_pset(I_) S; + // const S& s; + + void init() { level::fill(this->output, 0); } + bool handles(unsigned p) const { return this->input[p] == val; } + bool equiv(unsigned n, unsigned) const { return this->input[n] == val; } + + const mln_value(I_)& val; + + level_fast_t(const I_& input, const mln_value(I_)& val, const N_& nbh, O_& output) + : labeling::impl::base_fast_<I_,N_,O_>(input, nbh, output), + // s(input.domain()), + val(val) + {} + }; + + + template <typename I, typename N, typename O> + bool level_fast_(const Fast_Image<I>& input, const mln_value(I)& val, const Neighborhood<N>& nbh, + Fast_Image<O>& output, unsigned& nlabels) + { + typedef level_fast_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 of namespace mln::labeling::impl @@ -121,6 +160,14 @@ return impl::level_(exact(input), val, nbh, output, nlabels); } + template <typename I, typename N, typename O> + bool level_fast(const Fast_Image<I>& input, const mln_value(I)& val, const Neighborhood<N>& nbh, + Fast_Image<O>& output, unsigned& nlabels) + { + mln_precondition(exact(output).domain() == exact(input).domain()); + return impl::level_fast_(exact(input), val, nbh, output, nlabels); + } + # endif // ! MLN_INCLUDE_ONLY } // end of namespace mln::labeling