February 2009 - Olena-patches

milena r3319: Implement fastest versions of labeling
by Fabien Freling 09 Feb '09

09 Feb '09

URL: https://svn.lrde.epita.fr/svn/oln/trunk/milena ChangeLog: 2009-02-09 Fabien Freling <freling(a)lrde.epita.fr> Implement fastest versions of labeling. * mln/canvas/labeling.hh: Change labeling() to labeling_video() and * labeling_sorted(). * mln/labeling/flat_zones.hh: Implement fastest version. * mln/labeling/level.hh: Implement fastest version. * mln/labeling/regional_maxima.hh: Implement fastest version. * mln/labeling/regional_minima.hh: Implement fastest version. --- canvas/labeling.hh | 419 ++++++++++++++++++++++++++++++++++++++++---- labeling/flat_zones.hh | 61 ++---- labeling/level.hh | 102 ++-------- labeling/regional_maxima.hh | 70 ++----- labeling/regional_minima.hh | 76 +++---- 5 files changed, 498 insertions(+), 230 deletions(-) Index: trunk/milena/mln/canvas/labeling.hh =================================================================== --- trunk/milena/mln/canvas/labeling.hh (revision 3318) +++ trunk/milena/mln/canvas/labeling.hh (revision 3319) @@ -1,5 +1,5 @@ -// Copyright (C) 2007, 2008, 2009 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 @@ -39,6 +39,10 @@ # include <mln/data/fill.hh> # include <mln/literal/zero.hh> # include <mln/convert/to_upper_window.hh> +# include <mln/extension/adjust_fill.hh> + +# include <mln/level/sort_psites.hh> +# include <mln/level/sort_offsets.hh> namespace mln @@ -47,11 +51,20 @@ namespace canvas { - // General version. - template <typename I, typename N, typename F, typename L> + template <typename I, typename N, typename L, + typename F> + mln_ch_value(I, L) + labeling_video(const Image& input, const Neighborhood<N>& nbh, L& nlabels, + F& functor); + + + template <typename I, typename N, typename L, + typename F> mln_ch_value(I, L) - labeling(const Image& input, const Neighborhood<N>& nbh, - F& functor, L& nlabels); + labeling_sorted(const Image& input, const Neighborhood<N>& nbh, L& nlabels, + F& functor, bool increasing); + + # ifndef MLN_INCLUDE_ONLY @@ -61,21 +74,22 @@ namespace internal { - template <typename I, typename N, typename F, typename L> + template <typename I, typename N, typename L, + typename F> void - labeling_tests(const Image& input_, const Neighborhood<N>& nbh_, - const F& f, const L& nlabels) + labeling_tests(const Image& input_, const Neighborhood<N>& nbh_, const L& nlabels, + const F& f) { const I& input = exact(input_); const N& nbh = exact(nbh_); mln_precondition(input.is_valid()); - mln_precondition(nbh.is_valid()); + // mln_precondition(nbh.is_valid()); (void) input; (void) nbh; - (void) f; (void) nlabels; + (void) f; } } // end of namespace mln::canvas::internal @@ -101,10 +115,11 @@ return parent(x) = find_root(parent, parent(x)); } - template <typename I, typename N, typename F, typename L> + template <typename I, typename N, typename L, + typename S, typename F> mln_ch_value(I, L) - labeling(const Image& input_, const Neighborhood<N>& nbh_, - F& f, L& nlabels) + labeling(const Image& input_, const Neighborhood<N>& nbh_, L& nlabels, + const S& s, F& f) { trace::entering("canvas::impl::generic::labeling"); @@ -113,8 +128,6 @@ const I& input = exact(input_); const N& nbh = exact(nbh_); - typedef typename F::S S; - // Local type. typedef mln_psite(I) P; @@ -124,6 +137,7 @@ // Output. mln_ch_value(I, L) output; + bool status; // Initialization. { @@ -141,7 +155,7 @@ // First Pass. { - mln_fwd_piter(S) p(f.s); + mln_fwd_piter(S) p(s); mln_niter(N) n(nbh, p); for_all(p) if (f.handles(p)) { @@ -171,7 +185,7 @@ // Second Pass. { - mln_bkd_piter(S) p(f.s); + mln_bkd_piter(S) p(s); for_all(p) if (f.handles(p)) { if (parent(p) == p) // if p is root @@ -180,7 +194,7 @@ { if (nlabels == mln_max(L)) { - trace::warning("labeling aborted!"); + status = false; return output; } output(p) = ++nlabels; @@ -189,6 +203,7 @@ else output(p) = output(parent(p)); } + status = true; } trace::exiting("canvas::impl::generic::labeling"); @@ -197,6 +212,244 @@ } // end of namespace mln::canvas::impl::generic + + + // Fastest video version. + + template <typename I> + static inline + unsigned + find_root_fastest(I& parent, unsigned x) + { + if (parent.element(x) == x) + return x; + else + return parent.element(x) = find_root_fastest(parent, parent.element(x)); + } + + + template <typename I, typename N, typename L, + typename F> + mln_ch_value(I, L) + labeling_video_fastest(const Image& input_, const Neighborhood<N>& nbh_, + L& nlabels, F& f) + { + trace::entering("canvas::impl::labeling_video_fastest"); + + // FIXME: Test?! + + const I& input = exact(input_); + const N& nbh = exact(nbh_); + + extension::adjust(input, nbh); + + // Auxiliary data. + mln_ch_value(I, bool) deja_vu; + mln_ch_value(I, unsigned) parent; + + // Output. + mln_ch_value(I, L) output; + bool status; + + // Initialization. + { + initialize(deja_vu, input); + mln::data::fill(deja_vu, false); + extension::fill(deja_vu, false); // So that the extension is ignored. + + initialize(parent, input); + + initialize(output, input); + mln::data::fill(output, L(literal::zero)); + nlabels = 0; + + f.init_(); // Client initialization. + } + + // First Pass. + { + mln_pixter(const I) px(input); + mln_nixter(const I, N) nx(px, nbh); + for_all(px) + { + unsigned p = px.offset(); + if (! f.handles_(p)) + continue; + + // Make-Set. + parent.element(p) = p; + f.init_attr_(p); + for_all(nx) + { + unsigned n = nx.offset(); + if (deja_vu.element(n)) + { + if (f.equiv_(n, p)) + { + // Do-Union. + unsigned r = find_root_fastest(parent, n); + if (r != p) + { + parent.element(r) = p; + f.merge_attr_(r, p); + } + } + else + f.do_no_union_(n, p); + } + } + + deja_vu.element(p) = true; + } + } + + // Second Pass. + { + mln_bkd_pixter(const I) px(input); + for_all(px) + { + unsigned p = px.offset(); + if (! f.handles_(p)) + continue; + if (parent.element(p) == p) // if p is root + { + if (f.labels_(p)) + { + if (nlabels == mln_max(L)) + { + status = false; + return output; + } + output.element(p) = ++nlabels; + } + } + else + output.element(p) = output.element(parent.element(p)); + } + status = true; + } + + trace::exiting("canvas::impl::labeling_video_fastest"); + return output; + } + + + + // Fastest sorted version + + template <typename I, typename N, typename L, + typename S, typename F> + mln_ch_value(I, L) + labeling_sorted_fastest(const Image& input_, const Neighborhood<N>& nbh_, L& nlabels, + const S& s, F& f) + { + trace::entering("canvas::impl::labeling_sorted_fastest"); + + // FIXME: Test?! + + const I& input = exact(input_); + const N& nbh = exact(nbh_); + + extension::adjust(input, nbh); + + // Local type. + typedef mln_psite(I) P; + + // Auxiliary data. + mln_ch_value(I, bool) deja_vu; + mln_ch_value(I, unsigned) parent; + + // Output. + mln_ch_value(I, L) output; + bool status; + + // Initialization. + { + initialize(deja_vu, input); + mln::data::fill(deja_vu, false); + extension::fill(deja_vu, false); // So that the extension is ignored. + + initialize(parent, input); + + initialize(output, input); + mln::data::fill(output, L(literal::zero)); + nlabels = 0; + + f.init_(); // Client initialization. + } + + util::array<int> dp = offsets_wrt(input, nbh); + const unsigned n_nbhs = dp.nelements(); + + const unsigned n_points = s.nelements(); + + // First Pass. + { + + for (unsigned i = 0; i < n_points; ++i) + { + unsigned p = s[i]; + if (! f.handles_(p)) + continue; + + // Make-Set. + parent.element(p) = p; + f.init_attr_(p); + + for (unsigned j = 0; j < n_nbhs; ++j) + { + unsigned n = p + dp[j]; + if (! deja_vu.element(n)) + continue; + + if (f.equiv_(n, p)) + { + // Do-Union. + unsigned r = find_root_fastest(parent, n); + if (r != p) + { + parent.element(r) = p; + f.merge_attr_(r, p); + } + } + else + f.do_no_union_(n, p); + } + deja_vu.element(p) = true; + + } + } + + // Second Pass. + { + for (int i = n_points - 1; i >=0; --i) + { + unsigned p = s[i]; + if (! f.handles_(p)) + continue; + + if (parent.element(p) == p) // if p is root + { + if (f.labels_(p)) + { + if (nlabels == mln_max(L)) + { + status = false; + return output; + } + output.element(p) = ++nlabels; + } + } + else + output.element(p) = output.element(parent.element(p)); + } + status = true; + } + + trace::exiting("canvas::impl::labeling_sorted_fastest"); + return output; + } + } // end of namespace mln::canvas::impl @@ -206,39 +459,143 @@ namespace internal { - template <typename I, typename N, typename F, typename L> + // Video + + template <typename I, typename N, typename L, + typename F> inline mln_ch_value(I, L) - labeling_dispatch(const Image& input, const Neighborhood<N>& nbh, - F& functor, L& nlabels) + labeling_video(metal::false_, const Image& input, + const Neighborhood<N>& nbh, L& nlabels, F& functor) { - return impl::generic::labeling(input, nbh, functor, nlabels); + return impl::generic::labeling(input, nbh, input.domain(), + nlabels, functor); } + template <typename I, typename N, typename L, + typename F> + inline + mln_ch_value(I, L) + labeling_video(metal::true_, const Image& input, + const Neighborhood<N>& nbh, L& nlabels, F& functor) + { + return impl::labeling_video_fastest(input, nbh, nlabels, functor); + } + + template <typename I, typename N, typename L, + typename F> + inline + mln_ch_value(I, L) + labeling_video_dispatch(const Image& input, const Neighborhood<N>& nbh, + L& nlabels, F& functor) + { + enum { + test = mlc_equal(mln_trait_image_speed(I), + trait::image::speed::fastest)::value + && + mln_is_simple_neighborhood(N)::value + }; + return labeling_video(metal::bool_<test>(), input, + nbh, nlabels, functor); + } + + + // Sorted dispatch. + + template <typename I, typename N, typename L, typename F> + inline + mln_ch_value(I, L) + labeling_sorted_dispatch(metal::false_, + const Image& input, const Neighborhood<N>& nbh, L& nlabels, + F& functor, bool increasing) + { + p_array<mln_psite(I)> s = + increasing ? + level::sort_psites_increasing(input) : + level::sort_psites_decreasing(input); + return impl::generic::labeling(input, nbh, nlabels, + s, functor); + } + + template <typename I, typename N, typename L, typename F> + inline + mln_ch_value(I, L) + labeling_sorted_dispatch(metal::true_, + const Image& input, const Neighborhood<N>& nbh, L& nlabels, + F& functor, bool increasing) + { + util::array<unsigned> s = + increasing ? + level::sort_offsets_increasing(input) : + level::sort_offsets_decreasing(input); + return impl::labeling_sorted_fastest(input, nbh, nlabels, + s, functor); + } + + template <typename I, typename N, typename L, typename F> + inline + mln_ch_value(I, L) + labeling_sorted_dispatch(const Image& input, const Neighborhood<N>& nbh, L& nlabels, + F& functor, bool increasing) + { + enum { + test = mlc_equal(mln_trait_image_speed(I), + trait::image::speed::fastest)::value + && + mln_is_simple_neighborhood(N)::value + }; + return labeling_sorted_dispatch(metal::bool_<test>(), + input, nbh, nlabels, + functor, increasing); + } + + } // end of namespace mln::canvas::internal - // Facade. + // Facades. + - template <typename I, typename N, typename F, typename L> + template <typename I, typename N, typename L, + typename F> inline mln_ch_value(I, L) - labeling(const Image& input, const Neighborhood<N>& nbh, - F& functor, L& nlabels) + labeling_video(const Image& input, const Neighborhood<N>& nbh, L& nlabels, + F& functor) { - trace::entering("canvas::labeling"); + trace::entering("canvas::labeling_video"); - internal::labeling_tests(input, nbh, functor, nlabels); + internal::labeling_tests(input, nbh, nlabels, functor); mln_ch_value(I, L) output; - output = internal::labeling_dispatch(input, nbh, functor, nlabels); + output = internal::labeling_video_dispatch(input, nbh, nlabels, + functor); - trace::exiting("canvas::labeling"); + trace::exiting("canvas::labeling_video"); return output; } + template <typename I, typename N, typename L, + typename F> + inline + mln_ch_value(I, L) + labeling_sorted(const Image& input, const Neighborhood<N>& nbh, L& nlabels, + F& functor, bool increasing) + { + trace::entering("canvas::labeling_sorted"); + + internal::labeling_tests(input, nbh, nlabels, functor); + + mln_ch_value(I, L) output; + output = internal::labeling_sorted_dispatch(input, nbh, nlabels, + functor, increasing); + + trace::exiting("canvas::labeling_sorted"); + return output; + } + # endif // ! MLN_INCLUDE_ONLY } // end of namespace mln::canvas Index: trunk/milena/mln/labeling/flat_zones.hh =================================================================== --- trunk/milena/mln/labeling/flat_zones.hh (revision 3318) +++ trunk/milena/mln/labeling/flat_zones.hh (revision 3319) @@ -64,64 +64,47 @@ // Flat zone functor for the labeling canvas. - template <typename I_, typename N_, typename L_> + template <typename I> struct flat_zones_functor { - typedef mln_psite(I_) P; + typedef mln_psite(I) P; - // requirements from mln::canvas::labeling: + // Requirements from mln::canvas::labeling: - typedef I_ I; - typedef N_ N; - typedef L_ L; typedef mln_pset(I) S; const I& input; - const N& nbh; - const S& s; + // Generic implementation. + + void init() {} bool handles(const P&) const { return true; } bool equiv(const P& n, const P& p) const { return input(n) == input(p); } - - void init() {} bool labels(const P&) const { return true; } void do_no_union(const P&, const P&) {} void init_attr(const P&) {} void merge_attr(const P&, const P&) {} - // end of requirements + // Fastest implementation. + + void init_() {} + bool handles_(unsigned) const { return true; } + bool equiv_(unsigned n, unsigned p) const { return input.element(n) == + input.element(p); } + bool labels_(unsigned) const { return true; } + void do_no_union_(unsigned, unsigned) {} + void init_attr_(unsigned) {} + void merge_attr_(unsigned, unsigned) {} + + // end of requirements. flat_zones_functor(const I& input, const N& nbh) - : input(input), - nbh(nbh), - s(input.domain()) + : input(input) {} }; - // Generic implementation. - - namespace generic - { - - template <typename I, typename N, typename L> - mln_ch_value(I, L) - flat_zones(const Image& input, const Neighborhood<N>& nbh, L& nlabels) - { - trace::entering("labeling::impl::generic::flat_zones"); - - typedef flat_zones_functor<I,N,L> F; - F f(exact(input), exact(nbh)); - mln_ch_value(I, L) output = canvas::labeling(input, nbh, f, nlabels); - - trace::exiting("labeling::impl::generic::flat_zones"); - return output; - } - - } // end of namespace mln::labeling::impl::generic - - } // end of namespace mln::labeling::impl @@ -139,8 +122,10 @@ const N& nbh = exact(nbh_); mln_precondition(input.is_valid()); - // Calls the only (generic) impl. - mln_ch_value(I, L) output = impl::generic::flat_zones(input, nbh, nlabels); + // Calls the only implementation. + typedef flat_zones_functor<I,N,L> F; + F f(exact(input), exact(nbh)); + mln_ch_value(I, L) output = canvas::labeling_video(input, nbh, nlabels, f); trace::exiting("labeling::flat_zones"); return output; Index: trunk/milena/mln/labeling/level.hh =================================================================== --- trunk/milena/mln/labeling/level.hh (revision 3318) +++ trunk/milena/mln/labeling/level.hh (revision 3319) @@ -36,11 +36,10 @@ # include <mln/core/concept/image.hh> # include <mln/core/concept/neighborhood.hh> -# include <mln/canvas/labeling.hh> -# include <mln/data/fill.hh> -// The 'fastest' specialization is in: -# include <mln/labeling/level.spe.hh> +# include "labeling.hh" + +# include <mln/data/fill.hh> @@ -79,7 +78,7 @@ L& nlabels) { mln_precondition(exact(input).is_valid()); - mln_precondition(exact(nbh).is_valid()); + // mln_precondition(exact(nbh).is_valid()); (void) input; (void) val; @@ -91,40 +90,13 @@ - // Generic implementation. - namespace impl { - - struct labeling_functor_base - { - void init() {} - - template <typename P> - bool handles(const P&) const { return true; } - - template <typename L, typename R> - bool equiv(const L&, const R&) const { return false; } - - template <typename P> - bool labels(const P&) const { return true; } - - template <typename L, typename R> - void do_no_union(const L&, const R&) {} - - template <typename P> - void init_attr(const P&) {} - - template <typename L, typename R> - void merge_attr(const L&, const R&) {} - }; - - // Generic functor. template <typename I> - struct level_functor : labeling_functor_base + struct level_functor { typedef mln_psite(I) P; @@ -134,68 +106,39 @@ // Requirements from mln::canvas::labeling. typedef mln_pset(I) S; - const S& s; + + // Generic implementation void init() {} bool handles(const P& p) const { return input(p) == val; } bool equiv(const P& n, const P&) const { return input(n) == val; } bool labels(const P&) const { return true; } + void do_no_union(const P& n, const P& p) {} + void init_attr(const P&) {} + void merge_attr(const P& r, const P& p) {} + + // Fastest implementation + + void init_() {} + bool handles_(unsigned p) const { return input.element(p) == val; } + bool equiv_(unsigned n, unsigned) const { return input.element(n) == val; } + bool labels_(unsigned) const { return true; } + void do_no_union_(unsigned n, unsigned p) {} + void init_attr_(unsigned) {} + void merge_attr_(unsigned r, unsigned p) {} // end of Requirements. level_functor(const Image& input_, const mln_value(I)& val) : input(exact(input_)), - val(val), - s(input.domain()) + val(val) { } }; - - - // Generic implementation. - - namespace generic - { - - template <typename I, typename N, typename L> - mln_ch_value(I, L) - level(const Image& input, const mln_value(I)& val, - const Neighborhood<N>& nbh, - L& nlabels) - { - trace::entering("labeling::impl::generic::level"); - - internal::level_tests(input, val, nbh, nlabels); - - level_functor f(input, val); - mln_ch_value(I, L) output = canvas::labeling(input, nbh, f, nlabels); - - trace::exiting("labeling::impl::generic::level"); - return output; - } - - } // end of namespace mln::labeling::impl::generic - - } // end of namespace mln::labeling::impl - // Dispatch. - - namespace internal - { - - template <typename I, typename N, typename L> - mln_ch_value(I, L) - level_dispatch(const Image& input, const mln_value(I)& val, const Neighborhood<N>& nbh, - L& nlabels) - { - return impl::generic::level(input, val, nbh, nlabels); - } - - } // end of namespace mln::labeling::internal - // Facade. @@ -210,7 +153,8 @@ internal::level_tests(input, val, nbh, nlabels); mln_ch_value(I, L) output; - output = internal::level_dispatch(input, val, nbh, nlabels); + impl::level_functor f(input, val); + output = canvas::labeling_video(input, nbh, nlabels, f); trace::exiting("labeling::level"); return output; Index: trunk/milena/mln/labeling/regional_minima.hh =================================================================== --- trunk/milena/mln/labeling/regional_minima.hh (revision 3318) +++ trunk/milena/mln/labeling/regional_minima.hh (revision 3319) @@ -35,7 +35,9 @@ # include <mln/core/concept/image.hh> # include <mln/core/concept/neighborhood.hh> -# include <mln/canvas/labeling.hh> + +# include "labeling.hh" + # include <mln/data/fill.hh> # include <mln/level/sort_psites.hh> @@ -68,21 +70,16 @@ // Generic functor. - template <typename I_, typename N_, typename L_> + template <typename I> struct regional_minima_functor { - typedef mln_psite(I_) P; + typedef mln_psite(I) P; // requirements from mln::canvas::labeling: - typedef I_ I; - typedef N_ N; - typedef L_ L; - typedef p_array S; - const I& input; - const N& nbh; - S s; + + // Generic implementation void init() { data::fill(attr, true); } bool handles(const P&) const { return true; } @@ -103,43 +100,37 @@ void merge_attr(const P& r, const P& p) { attr(p) = attr(p) && attr(r); } - // end of requirements - - mln_ch_value(I, bool) attr; + // Fastest implementation - regional_minima_functor(const I_& input, const N_& nbh) - : input(input), - nbh(nbh), - s(level::sort_psites_increasing(input)) + void init_() { data::fill(attr, true); } + bool handles_(unsigned p) const { return true; } + bool labels_(unsigned p) const { return attr.element(p); } + bool equiv_(unsigned n, unsigned p) const { return input.element(n) == + input.element(p); } + void do_no_union_(unsigned n, unsigned p) { - initialize(attr, input); + // Avoid a warning about an undefined variable when NDEBUG + // is not defined. + (void)n; + + mln_invariant(input.element(n) < input.element(p)); + attr.element(p) = false; } - }; + void init_attr_(unsigned) {} + void merge_attr_(unsigned r, unsigned p) { attr.element(p) = attr.element(p) && + attr.element(r); } - // Generic implementation. + // end of requirements - namespace generic - { + mln_ch_value(I, bool) attr; - template <typename I, typename N, typename L> - mln_ch_value(I, L) - regional_minima(const I& input, const N& nbh, L& nlabels) + regional_minima_functor(const I& input) + : input(input) { - trace::entering("labeling::impl::generic::regional_minima"); - - // FIXME: abort if L is not wide enough to encode the set of - // minima. - - typedef impl::regional_minima_functor<I,N,L> F; - F f(exact(input), exact(nbh)); - mln_ch_value(I, L) output = canvas::labeling(input, nbh, f, nlabels); - - trace::exiting("labeling::impl::generic::regional_minima"); - return output; + initialize(attr, input); } - - } // end of namespace mln::labeling::impl::generic + }; } // end of namespace mln::labeling::impl @@ -159,8 +150,13 @@ const N& nbh = exact(nbh_); mln_precondition(input.is_valid()); - // Calls the only (generic) impl. - mln_ch_value(I, L) output = impl::generic::regional_minima(input, nbh, nlabels); + // FIXME: abort if L is not wide enough to encode the set of + // minima. + + typedef impl::regional_minima_functor F; + F f(exact(input)); + mln_ch_value(I, L) output = canvas::labeling_sorted(input, nbh, nlabels, + f, true); trace::exiting("labeling::regional_minima"); return output; Index: trunk/milena/mln/labeling/regional_maxima.hh =================================================================== --- trunk/milena/mln/labeling/regional_maxima.hh (revision 3318) +++ trunk/milena/mln/labeling/regional_maxima.hh (revision 3319) @@ -35,7 +35,9 @@ # include <mln/core/concept/image.hh> # include <mln/core/concept/neighborhood.hh> -# include <mln/canvas/labeling.hh> + +# include "labeling.hh" + # include <mln/data/fill.hh> # include <mln/level/sort_psites.hh> @@ -69,21 +71,16 @@ // Generic functor. - template <typename I_, typename N_, typename L_> + template <typename I> struct regional_maxima_functor { - typedef mln_psite(I_) P; + typedef mln_psite(I) P; // requirements from mln::canvas::labeling: - typedef I_ I; - typedef N_ N; - typedef L_ L; - typedef p_array S; - const I& input; - const N& nbh; - S s; + + // Generic implementation void init() { data::fill(attr, true); } bool handles(const P&) const { return true; } @@ -97,50 +94,37 @@ void merge_attr(const P& r, const P& p) { attr(p) = attr(p) && attr(r); } + // Fastest implementation + + void init_() { data::fill(attr, true); } + bool handles_(unsigned p) const { return true; } + bool labels_(unsigned p) const { return attr.element(p); } + bool equiv_(unsigned n, unsigned p) const { return input.element(n) == + input.element(p); } + void do_no_union_(unsigned n, unsigned p) { mln_invariant(input.element(n) > + input.element(p)); + attr.element(p) = false; } + void init_attr_(unsigned) {} + void merge_attr_(unsigned r, unsigned p) { attr.element(p) = attr.element(p) && + attr.element(r); } + // end of requirements mln_ch_value(I, bool) attr; - regional_maxima_functor(const I_& input, const N_& nbh) - : input(input), - nbh(nbh), - s(level::sort_psites_decreasing(input)) + regional_maxima_functor(const I& input) + : input(input) { initialize(attr, input); } }; - // Generic implementation. - - namespace generic - { - - template <typename I, typename N, typename L> - mln_ch_value(I, L) - regional_maxima(const I& input, const N& nbh, - L& nlabels) - { - trace::entering("labeling::impl::generic::regional_maxima"); - - // FIXME: abort if L is not wide enough to encode the set of - // maxima. - - typedef impl::regional_maxima_functor<I,N,L> F; - F f(exact(input), exact(nbh)); - mln_ch_value(I, L) output = canvas::labeling(input, nbh, f, nlabels); - - trace::exiting("labeling::impl::generic::regional_maxima"); - return output; - } - - } // end of namespace mln::labeling::impl::generic - - } // end of namespace mln::labeling::impl + // Facade. template <typename I, typename N, typename L> @@ -154,8 +138,10 @@ const N& nbh = exact(nbh_); mln_precondition(input.is_valid()); - // Calls the only (generic) impl. - mln_ch_value(I, L) output = impl::generic::regional_maxima(input, nbh, nlabels); + typedef impl::regional_maxima_functor F; + F f(exact(input)); + mln_ch_value(I, L) output = canvas::labeling_sorted(input, nbh, nlabels, + f, false); trace::exiting("labeling::regional_maxima"); return output;

1 0

r3318: Implement fastest versions of labeling
by Fabien Freling 09 Feb '09

09 Feb '09

URL: https://svn.lrde.epita.fr/svn/oln/trunk/milena/sandbox ChangeLog: 2009-02-09 Fabien Freling <freling(a)lrde.epita.fr> Implement fastest versions of labeling. * fabien/flat_zones.hh: Implement fastest version. * fabien/level.hh: Fix. --- flat_zones.hh | 141 ++++++++++++++++++++++++++++++++++++++++++++++++++++++++++ level.hh | 2 2 files changed, 141 insertions(+), 2 deletions(-) Index: trunk/milena/sandbox/fabien/flat_zones.hh =================================================================== --- trunk/milena/sandbox/fabien/flat_zones.hh (revision 0) +++ trunk/milena/sandbox/fabien/flat_zones.hh (revision 3318) @@ -0,0 +1,141 @@ +// 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 +// of the GNU General Public License version 2 as published by the +// Free Software Foundation. +// +// This library is distributed in the hope that it will be useful, +// but WITHOUT ANY WARRANTY; without even the implied warranty of +// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU +// General Public License for more details. +// +// You should have received a copy of the GNU General Public License +// along with this library; see the file COPYING. If not, write to +// the Free Software Foundation, 51 Franklin Street, Fifth Floor, +// Boston, MA 02111-1307, USA. +// +// As a special exception, you may use this file as part of a free +// software library without restriction. Specifically, if other files +// instantiate templates or use macros or inline functions from this +// file, or you compile this file and link it with other files to +// produce an executable, this file does not by itself cause the +// resulting executable to be covered by the GNU General Public +// License. This exception does not however invalidate any other +// reasons why the executable file might be covered by the GNU General +// Public License. + +#ifndef MLN_LABELING_FLAT_ZONES_HH +# define MLN_LABELING_FLAT_ZONES_HH + +/// \file mln/labeling/flat_zones.hh +/// +/// Connected component labeling of the flat zones of an image. + +# include <mln/core/concept/image.hh> +# include <mln/core/concept/neighborhood.hh> +# include <mln/canvas/labeling.hh> + + +namespace mln +{ + + namespace labeling + { + + /// Connected component labeling of the flat zones of an image. + /// + /// \param[in] input The input image. + /// \param[in] nbh The connexity of the flat zones. + /// \param[out] nlabels The number of labels. + /// \return The label image. + /// + template <typename I, typename N, typename L> + mln_ch_value(I, L) + flat_zones(const Image& input, const Neighborhood<N>& nbh, L& nlabels); + + + +# ifndef MLN_INCLUDE_ONLY + + namespace impl + { + + // Flat zone functor for the labeling canvas. + + template <typename I> + struct flat_zones_functor + { + typedef mln_psite(I) P; + + // Requirements from mln::canvas::labeling: + + typedef mln_pset(I) S; + + const I& input; + + // Generic implementation. + + void init() {} + bool handles(const P&) const { return true; } + bool equiv(const P& n, const P& p) const { return input(n) == + input(p); } + bool labels(const P&) const { return true; } + void do_no_union(const P&, const P&) {} + void init_attr(const P&) {} + void merge_attr(const P&, const P&) {} + + // Fastest implementation. + + void init_() {} + bool handles_(unsigned) const { return true; } + bool equiv_(unsigned n, unsigned p) const { return input.element(n) == + input.element(p); } + bool labels_(unsigned) const { return true; } + void do_no_union_(unsigned, unsigned) {} + void init_attr_(unsigned) {} + void merge_attr_(unsigned, unsigned) {} + + // end of requirements. + + flat_zones_functor(const I& input, const N& nbh) + : input(input) + {} + }; + + + } // end of namespace mln::labeling::impl + + + + // Facade. + + template <typename I, typename N, typename L> + mln_ch_value(I, L) + flat_zones(const Image& input_, const Neighborhood<N>& nbh_, + L& nlabels) + { + trace::entering("labeling::flat_zones"); + + const I& input = exact(input_); + const N& nbh = exact(nbh_); + mln_precondition(input.is_valid()); + + // Calls the only implementation. + typedef flat_zones_functor<I,N,L> F; + F f(exact(input), exact(nbh)); + mln_ch_value(I, L) output = canvas::labeling_video(input, nbh, nlabels, f); + + trace::exiting("labeling::flat_zones"); + return output; + } + +# endif // ! MLN_INCLUDE_ONLY + + } // end of namespace mln::labeling + +} // end of namespace mln + + +#endif // ! MLN_LABELING_FLAT_ZONES_HH Index: trunk/milena/sandbox/fabien/level.hh =================================================================== --- trunk/milena/sandbox/fabien/level.hh (revision 3317) +++ trunk/milena/sandbox/fabien/level.hh (revision 3318) @@ -90,8 +90,6 @@ - // Generic implementation. - namespace impl {

1 0

r3317: Add untake and setvalue property to card accu
by Edwin Carlinet 09 Feb '09

09 Feb '09

URL: https://svn.lrde.epita.fr/svn/oln/trunk/milena/sandbox ChangeLog: 2009-02-09 Edwin Carlinet <carlinet(a)lrde.epita.fr> Add untake and setvalue property to card accu. * edwin/accu_trait.hh: Add properties untake, stop, setvalue. * edwin/card.hh: Add untake/setvalue method. --- accu_trait.hh | 69 +++++++++++++++++++++++++++++++++++++++++++++++++++------- card.hh | 2 + 2 files changed, 63 insertions(+), 8 deletions(-) Index: trunk/milena/sandbox/edwin/card.hh =================================================================== --- trunk/milena/sandbox/edwin/card.hh (revision 3316) +++ trunk/milena/sandbox/edwin/card.hh (revision 3317) @@ -18,6 +18,8 @@ void init () { c_ = 0; }; void take (const card<T>& accu) { c_ += accu.c_; }; void take (const T& elt) { ++c_; }; + void untake (const T& elt) { --c_; }; + void setvalue (const unsigned v) { c_ = v; }; unsigned to_result() const { return c_; }; bool is_valid () const { return true; }; Index: trunk/milena/sandbox/edwin/accu_trait.hh =================================================================== --- trunk/milena/sandbox/edwin/accu_trait.hh (revision 3316) +++ trunk/milena/sandbox/edwin/accu_trait.hh (revision 3317) @@ -3,7 +3,18 @@ # include <mln/trait/undef.hh> -# define mln_trait_accu_when_pix(A) typename trait::accu::accu_traits<A>::when_pix +/// Shortcut to the accumulator property about untake method disponibility +# define mln_trait_accu_has_untake(A) typename mln::trait::accu::accu_traits< A >::has_untake + +/// Shortcut to the accumulator property about setvalue method disponibility +# define mln_trait_accu_has_setvalue(A) typename mln::trait::accu::accu_traits< A >::has_setvalue + +/// Shortcut to the accumulator property about stop method disponibility +# define mln_trait_accu_has_stop(A) typename mln::trait::accu::accu_traits< A >::has_stop + +/// Shortcut to the accumulator property about behavior when pixel is given as take() value +/// Used for instance in mln::canvas::morpho::leveling +# define mln_trait_accu_when_pix(A) typename mln::trait::accu::accu_traits< A >::when_pix namespace mln @@ -21,18 +32,57 @@ namespace accu { + // Basic accumulators properties + + struct has_untake + { + struct any { protected: any() {}; }; + + struct no : any { std::string name() const { return "has_untake::no"; } }; + + struct yes : any { std::string name() const { return "has_untake::yes"; } }; + }; + + struct has_stop + { + struct any { protected: any() {}; }; + + struct no : any { std::string name() const { return "has_setvalue::no"; } }; + + struct yes : any { std::string name() const { return "has_stop::yes"; } }; + }; + + struct has_setvalue + { + struct any { protected: any() {}; }; + + struct no : any { std::string name() const { return "has_setvalue::no"; } }; + + struct yes : any { std::string name() const { return "has_setvalue::yes"; } }; + }; + + // Morphological accumulators properties struct when_pix { - struct use_v {}; - struct use_p {}; - struct use_pix {}; - struct use_whatever {}; - struct not_ok {}; + struct any { protected: any() {}; }; + + struct use_v : any { std::string name() const { return "when_pix::use_v"; } }; + + struct use_p : any { std::string name() const { return "when_pix::use_p"; } }; + + struct use_pix : any { std::string name() const { return "when_pix::use_pix"; } }; + + struct use_whatever { std::string name() const { return "when_pix::use_whatever"; } }; + + struct not_ok : any { std::string name() const { return "when_pix::not_ok"; } }; }; template <typename A> struct accu_traits { + typedef undef has_untake; + typedef undef has_stop; + typedef undef has_setvalue; typedef undef when_pix; }; @@ -40,11 +90,14 @@ template <typename T> struct accu_traits< mln::morpho::accu::card <T> > { + typedef has_stop::no has_stop; + typedef has_untake::yes has_untake; + typedef has_setvalue::yes has_setvalue; typedef when_pix::use_p when_pix; }; - } //accu + } //mln::accu - }//trait + } //mln::trait } //mln #endif /* !ACCU_TRAIT_HH_ */

1 0

3316: Update IRM segmentation.
by Thierry Geraud 09 Feb '09

09 Feb '09

https://svn.lrde.epita.fr/svn/oln/trunk/milena/sandbox Index: ChangeLog from Thierry Geraud <thierry.geraud(a)lrde.epita.fr> Update IRM segmentation. * theo/igr/dump_cut.cc: New. * theo/igr/irm_anat_segm.cc: Update. dump_cut.cc | 47 +++++++++++++++++++++++++++++++++++++++++++++++ irm_anat_segm.cc | 14 ++++++++------ 2 files changed, 55 insertions(+), 6 deletions(-) Index: theo/igr/dump_cut.cc --- theo/igr/dump_cut.cc (revision 0) +++ theo/igr/dump_cut.cc (revision 0) @@ -0,0 +1,47 @@ + +#include <mln/make/image3d.hh> +#include <mln/data/fill.hh> +#include <mln/value/int_u8.hh> +#include <mln/io/dump/load.hh> +#include <mln/io/dump/save.hh> + + + +void usage(char* argv[]) +{ + std::cerr << "usage: " << argv[0] << " input.dump s_min r_min c_min s_max r_max c_max output.dump" << std::endl; + abort(); +} + + + +int main(int argc, char* argv[]) +{ + using namespace mln; + using value::int_u8; + + if (argc != 9) + usage(argv); + + image3d<int_u8> vol; + io::dump::load(vol, argv[1]); + + int + s_min = atoi(argv[2]), + r_min = atoi(argv[3]), + c_min = atoi(argv[4]), + + s_max = atoi(argv[5]), + r_max = atoi(argv[6]), + c_max = atoi(argv[7]); + + // FIXME: Test! + + box3d b = make::box3d(s_min, r_min, c_min, s_max, r_max, c_max); + + // IRM.dump => 0, 180, 50, 14, 340, 400 + + image3d<int_u8> ima(b); + data::fill(ima, vol); + io::dump::save(ima, argv[8]); +} Index: theo/igr/irm_anat_segm.cc --- theo/igr/irm_anat_segm.cc (revision 3315) +++ theo/igr/irm_anat_segm.cc (working copy) @@ -7,7 +7,7 @@ #include <mln/io/dump/save.hh> #include <mln/morpho/elementary/gradient.hh> -#include <mln/morpho/closing_volume.hh> +#include <mln/morpho/closing_height.hh> #include <mln/morpho/watershed/flooding.hh> #include <mln/accu/mean.hh> @@ -19,7 +19,8 @@ void usage(char* argv[]) { - std::cerr << "usage: " << argv[0] << " input.dump output.dump" << std::endl; + std::cerr << "usage: " << argv[0] << " input.dump lambda output.dump" << std::endl + << " It relies on height closing; e.g., take lambda = 20" << std::endl; abort(); } @@ -30,7 +31,7 @@ using namespace mln; using value::int_u8; - if (argc != 3) + if (argc != 4) usage(argv); trace::quiet = false; @@ -40,8 +41,10 @@ image3d<int_u8> vol, grad, clo; io::dump::load(vol, argv[1]); + unsigned lambda = atoi(argv[2]); + grad = morpho::elementary::gradient(vol, c6()); - clo = morpho::closing_volume(grad, c6(), 666); + clo = morpho::closing_height(grad, c6(), lambda); typedef value::label_16 L; L n_basins; @@ -60,8 +63,7 @@ convert::from_to(a, f); image3d<int_u8> out = level::transform(wst, f); - io::dump::save(out, argv[2]); - + io::dump::save(out, argv[3]); trace::exiting("main"); }

1 0

3315: Fix missing update from 'raw' to 'dump'.
by Thierry Geraud 08 Feb '09

08 Feb '09

https://svn.lrde.epita.fr/svn/oln/trunk/milena/sandbox Index: ChangeLog from Thierry Geraud <thierry.geraud(a)lrde.epita.fr> Fix missing update from 'raw' to 'dump'. * theo/igr/raw2pgm.cc: Rename as... * theo/igr/dump2pgm.cc: ...this. (include, usage): Fix missing update. * theo/igr/pgms2raw.cc: Rename as... * theo/igr/pgms2dump.cc: ...this. (usage): Fix missing update. (main): Fix io save. * theo/igr/irm_anat_segm.cc: Update. * theo/igr/irm_anat_segm__2D_ONLY.cc: Update. * theo/irm.cc: Rename as... * theo/igr/irm_seg_with_mm_and_rag.cc: ...this. dump2pgm.cc | 4 ++-- irm_anat_segm.cc | 15 ++++++++++----- irm_anat_segm__2D_ONLY.cc | 2 -- pgms2dump.cc | 6 +++--- 4 files changed, 15 insertions(+), 12 deletions(-) Index: theo/igr/dump2pgm.cc --- theo/igr/dump2pgm.cc (revision 3314) +++ theo/igr/dump2pgm.cc (working copy) @@ -4,14 +4,14 @@ #include <mln/debug/slices_2d.hh> #include <mln/value/int_u8.hh> -#include <mln/io/raw/load.hh> +#include <mln/io/dump/load.hh> #include <mln/io/pgm/save.hh> void usage(char* argv[]) { - std::cerr << "usage: " << argv[0] << " input.raw output.pgm" << std::endl; + std::cerr << "usage: " << argv[0] << " input.dump output.pgm" << std::endl; abort(); } Index: theo/igr/pgms2dump.cc --- theo/igr/pgms2dump.cc (revision 3314) +++ theo/igr/pgms2dump.cc (working copy) @@ -4,13 +4,13 @@ #include <mln/value/int_u8.hh> #include <mln/io/pgm/load.hh> -#include <mln/io/raw/save.hh> +#include <mln/io/dump/save.hh> void usage(char* argv[]) { - std::cerr << "usage: " << argv[0] << " output.raw input1.pgm .. inputn.pgm" << std::endl; + std::cerr << "usage: " << argv[0] << " output.dump input1.pgm .. inputn.pgm" << std::endl; abort(); } @@ -34,5 +34,5 @@ arr.append(ima); } image3d<int_u8> vol = make::image3d(arr); - io::save(vol, argv[1]); + io::dump::save(vol, argv[1]); } Index: theo/igr/irm_anat_segm.cc --- theo/igr/irm_anat_segm.cc (revision 3314) +++ theo/igr/irm_anat_segm.cc (working copy) @@ -3,12 +3,12 @@ #include <mln/core/alias/neighb3d.hh> #include <mln/value/int_u8.hh> -#include <mln/io/raw/load.hh> -#include <mln/io/raw/save.hh> +#include <mln/io/dump/load.hh> +#include <mln/io/dump/save.hh> #include <mln/morpho/elementary/gradient.hh> #include <mln/morpho/closing_volume.hh> -#include <mln/morpho/meyer_wst.hh> +#include <mln/morpho/watershed/flooding.hh> #include <mln/accu/mean.hh> #include <mln/labeling/compute.hh> @@ -19,7 +19,7 @@ void usage(char* argv[]) { - std::cerr << "usage: " << argv[0] << " input.raw output.raw" << std::endl; + std::cerr << "usage: " << argv[0] << " input.dump output.dump" << std::endl; abort(); } @@ -35,6 +35,8 @@ trace::quiet = false; + trace::entering("main"); + image3d<int_u8> vol, grad, clo; io::dump::load(vol, argv[1]); @@ -43,7 +45,7 @@ typedef value::label_16 L; L n_basins; - image3d<L> wst = morpho::meyer_wst(clo, c6(), n_basins); + image3d<L> wst = morpho::watershed::flooding(clo, c6(), n_basins); std::cout << n_basins << std::endl; @@ -59,4 +61,7 @@ image3d<int_u8> out = level::transform(wst, f); io::dump::save(out, argv[2]); + + + trace::exiting("main"); } Index: theo/igr/irm_anat_segm__2D_ONLY.cc --- theo/igr/irm_anat_segm__2D_ONLY.cc (revision 3314) +++ theo/igr/irm_anat_segm__2D_ONLY.cc (working copy) @@ -32,8 +32,6 @@ if (argc != 3) usage(argv); - trace::quiet = false; - image2d<int_u8> vol, grad, clo; io::pgm::load(vol, argv[1]);

1 0

3314: Add a color segmentation on pixels (not on edges).
by Thierry Geraud 08 Feb '09

08 Feb '09

https://svn.lrde.epita.fr/svn/oln/trunk/milena/sandbox Index: ChangeLog from Thierry Geraud <thierry.geraud(a)lrde.epita.fr> Add a color segmentation on pixels (not on edges). * theo/color/segment.hh: Update. * theo/color/segment_rgb_pixels.cc: New. * theo/color/segment_rgb_edges.cc: Update. * theo/color/mean_rgb_pix.hh: New. * theo/color/change_attributes.hh: Update. change_attributes.hh | 55 +++++++++++++++-- mean_rgb_pix.hh | 105 ++++++++++++++------------------ segment.hh | 88 ++++++++++++++++++++++++++- segment_rgb_edges.cc | 24 +------ segment_rgb_pixels.cc | 160 ++++++++++++++++++++++++++++++++++++-------------- 5 files changed, 305 insertions(+), 127 deletions(-) Index: theo/color/segment.hh --- theo/color/segment.hh (revision 3313) +++ theo/color/segment.hh (working copy) @@ -8,6 +8,9 @@ #include <mln/make/pix.hh> #include <mln/debug/println.hh> +#include <mln/value/rgb8.hh> +#include <mln/math/diff_abs.hh> + #include <mln/level/sort_psites.hh> #include <mln/labeling/regional_minima.hh> #include <mln/pw/all.hh> @@ -23,6 +26,31 @@ { + // Distance between 2 rgb8 colors. + + value::int_u8 dist(const value::rgb8& c1, const value::rgb8& c2) + { + unsigned d = 0; + d += (math::diff_abs(c1.red(), c2.red()) + 2) / 3; + d += (math::diff_abs(c1.green(), c2.green()) + 2) / 3; + d += (math::diff_abs(c1.blue(), c2.blue()) + 2) / 3; + if (d > 255) + d = 255; + return d; + } + + value::int_u8 dist_(const value::rgb8& c1, const value::rgb8& c2) + { + unsigned d = 0; + d += math::diff_abs(c1.red(), c2.red()); + d += math::diff_abs(c1.green(), c2.green()); + d += math::diff_abs(c1.blue(), c2.blue()); + if (d > 255) + d = 255; + return d; + } + + // Sorting. @@ -118,6 +146,58 @@ + + + // Tree -> attributes on every pixel. + // Warning : it is not an attribute per flat zone! + // ----------------------------------------------- + + template <typename A, typename T> + inline + mln_ch_value(typename T::function, mln_result(A)) + compute_attribute_on_pixels__not_on_flat_zones(const A& a, const T& t) + { + typedef typename T::function I; + + mln_ch_value(I, A) acc; + mln_ch_value(I, mln_result(A)) attr; + + // Initialization of 'acc'. + { + initialize(acc, t.f()); + data::fill(acc, a); // Transfer "dynamic data" (state) of 'a'. + } + + // Initialize every attribute with the corresponding pixel. + { + mln_piter(I) p(t.f().domain()); + for_all(p) + acc(p).take_as_init(make::pix(t.f(), p)); + } + + // Propagate attribute from a site to its parent. + { + mln_fwd_piter(T) p(t.domain()); + for_all(p) + if (! t.is_root(p)) + acc(t.parent(p)).take(acc(p)); + } + + + // Change accumulator into its result. + { + initialize(attr, acc); + mln_piter(I) p(t.f().domain()); // The main difference is here! + for_all(p) + attr(p) = acc(p).to_result(); + } + + return attr; + } + + + + // Tree -> nchildren (on nodes). // ----------------------------- @@ -228,7 +308,7 @@ if (echo) { - back_propagate(filtered, t); + back_propagate(t, filtered); debug::println("filtered =", filtered); debug::println("a < lambda = ", (pw::value(a) < pw::cst(lambda)) | a.domain()); } @@ -344,7 +424,7 @@ tree_t t(f, s, nbh); mln_VAR(a, compute_attribute_on_nodes(a_, t)); - back_propagate(a, t); + back_propagate(t, a); if (echo) { @@ -363,7 +443,7 @@ break; case 2: std::cout << "fuse up attributes" << std::endl; - fuse_down_attributes(t, a, echo); + fuse_up_attributes(t, a, echo); break; } @@ -409,7 +489,7 @@ T t(f, s, nbh); mln_VAR(a, compute_attribute_on_nodes(a_, t)); - back_propagate(a, t); + back_propagate(t, a); unsigned n_regmins_f; // This value can be obtained while computing the attributes! Index: theo/color/segment_rgb_pixels.cc --- theo/color/segment_rgb_pixels.cc (revision 3313) +++ theo/color/segment_rgb_pixels.cc (working copy) @@ -4,34 +4,101 @@ #include <mln/core/alias/neighb2d.hh> #include <mln/value/int_u8.hh> -#include <mln/value/label_8.hh> +#include <mln/value/label_16.hh> #include <mln/value/rgb8.hh> #include <mln/literal/colors.hh> -#include <mln/io/pgm/load.hh> +#include <mln/io/ppm/load.hh> #include <mln/io/ppm/save.hh> #include <mln/io/pgm/save.hh> - +#include <mln/io/pbm/save.hh> #include <mln/level/convert.hh> -#include <mln/morpho/elementary/gradient.hh> #include <mln/morpho/meyer_wst.hh> -#include <mln/accu/height.hh> - +#include "mean_rgb_pix.hh" #include "segment.hh" +namespace mln +{ + + + // Distance, stored on pixels, of neighboring colors. + + template <typename N> + image2d<value::int_u8> + dist_on_pixels(const image2d<value::rgb8>& input, const N& nbh) + { + using value::int_u8; + image2d<int_u8> output(input.domain()); + + mln_piter(box2d) p(input.domain()); + mln_niter(N) n(nbh, p); + for_all(p) + { + int_u8 d = 0u; + for_all(n) if (input.domain().has(n)) + { + int_u8 d_ = dist(input(p), input(n)); + if (d_ > d) + d = d_; + } + output(p) = d; + } + + io::pgm::save(output, "temp_dist.pgm"); + + return output; + } + + + + + + // From 'mean color' attributes to 'mean difference p/par(p)'. + // ----------------------------------------------------------- + + + template <typename T, typename A> + inline + mln_ch_value(A, value::int_u8) + dists_from_means(const T& t, const A& a, bool echo = false) + { + if (echo) + { + std::cout << "means:" << std::endl; + display_tree_attributes(t, a); + } + + mln_ch_value(A, value::int_u8) d; + initialize(d, a); + + typedef typename T::nodes_t N; + mln_fwd_piter(N) n(t.nodes()); + for_all(n) + d(n) = dist(a(n), a(t.parent(n))); + + if (echo) + { + std::cout << "dists:" << std::endl; + display_tree_attributes(t, d); + } + + return d; + } + + +} // mln + void usage(char* argv[]) { - std::cerr << "usage: " << argv[0] << " input.pgm n change extinction echo output.ppm" << std::endl; - std::cerr << "gray-level version on pixels (without edges)" << std::endl; + std::cerr << "usage: " << argv[0] << " input.ppm n echo output.ppm" << std::endl; + std::cerr << "color version on pixels (without edges)" << std::endl; std::cerr << " n >= 2" << std::endl; - std::cerr << " change = 0 (none), 1 (move-down), or 2 (fuse)" << std::endl; - std::cerr << " extinction = 0 (none) or 1 (effective)" << std::endl; std::cerr << " echo = 0 (mute) or 1 (verbose)" << std::endl; abort(); } @@ -46,30 +113,22 @@ using value::rgb8; - if (argc != 7) + if (argc != 5) usage(argv); - // Gray-level debase version. - // -------------------------- + // Color debase (on pixels, not edges) version. + // -------------------------------------------- - typedef image2d<int_u8> I; + typedef image2d<rgb8> I; I input; - io::pgm::load(input, argv[1]); + io::ppm::load(input, argv[1]); unsigned n_objects = atoi(argv[2]); - int change_kind = atoi(argv[3]); - if (change_kind < 0 || change_kind > 2) - usage(argv); - - int do_extinction = atoi(argv[4]); - if (do_extinction != 0 && do_extinction != 1) - usage(argv); - - bool echo = atoi(argv[5]); + bool echo = atoi(argv[3]); // Neighborhood. @@ -78,40 +137,55 @@ // Changing input into 'f'. - I f = morpho::elementary::gradient(input, c4()); + typedef image2d<int_u8> F; + F f = dist_on_pixels(input, c4()); + + + typedef p_array<mln_psite_(F)> S; + S s = level::sort_psites_decreasing(f); + typedef morpho::tree::data<F,S> tree_t; + tree_t t(f, s, c4()); - // // granulometry: - // gran_filter(f, c4(), a_); + accu::rgb_image_ = input; + accu::mean_rgb_pix< util::pix<F> > a_; + mln_VAR(a, compute_attribute_on_nodes(a_, t)); + mln_VAR(d, dists_from_means(t, a, echo)); + make_attribute_grow(t, d); + if (echo) + { + std::cout << "dists growing:" << std::endl; + display_tree_attributes(t, d); + } - // accu::count< util::pix > a_; - // accu::sum_pix< util::pix > a_; - // accu::volume a_; - accu::height a_; - // It seems that both extinction and changing attributes only - // properly works for the 'height' attribute. + // BAD: extinct_attributes(t, d, echo); - I g = filter(f, c4(), - a_, - change_kind, do_extinction, - n_objects, + + int_u8 lambda; + unsigned less; + image2d<int_u8> g = run_filter(d, t, c4(), n_objects, // input + less, lambda, // output echo); - if (echo) - debug::println("activity (g != f) = ", (pw::value(g) != pw::value(f)) | f.domain()); + io::pbm::save( (pw::value(g) != pw::value(f)) | f.domain(), + "temp_activity.pbm" ); + +// if (echo) +// debug::println("activity (g != f) = ", (pw::value(g) != pw::value(f)) | f.domain()); // Watershed transform. - typedef value::label_8 L; + typedef value::label_16 L; L nbasins; mln_ch_value_(I, L) w = morpho::meyer_wst(g, c4(), nbasins); + std::cout << "n basins = " << nbasins << std::endl; - image2d<rgb8> output = level::convert(rgb8(), input); - data::fill((output | (pw::value(w) == 0)).rw(), literal::red); + image2d<rgb8> output = duplicate(input); + data::fill((output | (pw::value(w) == 0)).rw(), literal::black); - io::ppm::save(output, argv[6]); + io::ppm::save(output, argv[4]); } Index: theo/color/segment_rgb_edges.cc --- theo/color/segment_rgb_edges.cc (revision 3313) +++ theo/color/segment_rgb_edges.cc (working copy) @@ -17,8 +17,6 @@ #include <mln/io/ppm/load.hh> #include <mln/io/ppm/save.hh> -#include <mln/math/diff_abs.hh> - #include <mln/morpho/dilation.hh> #include <mln/morpho/erosion.hh> #include <mln/morpho/meyer_wst.hh> @@ -29,11 +27,10 @@ #include <mln/accu/mean.hh> #include "sum_pix.hh" - - #include "segment.hh" + namespace mln { @@ -192,22 +189,11 @@ - // Distance. - - value::int_u8 dist(const value::rgb8& c1, const value::rgb8& c2) - { - unsigned d = 0; - d += (math::diff_abs(c1.red(), c2.red()) + 2) / 3; - d += (math::diff_abs(c1.green(), c2.green()) + 2) / 3; - d += (math::diff_abs(c1.blue(), c2.blue()) + 2) / 3; - if (d > 255) - d = 255; - return d; - } + // Distance, stored on edges, of a couple of colors. template <typename I, typename N> image2d<value::int_u8> - dist(const I& input, const N& nbh) + dist_on_edges(const I& input, const N& nbh) { image2d<value::int_u8> output; initialize(output, input); @@ -224,6 +210,8 @@ output(p) = dist(c1, c2); } + io::pgm::save(output, "temp_dist.pgm"); + return output; } @@ -288,7 +276,7 @@ image2d<int_u8> f_; image2d<rgb8> input_ = image2full(input); { - f_ = dist(extend(input_ | is_edge, pw::value(input_)), + f_ = dist_on_edges(extend(input_ | is_edge, pw::value(input_)), e2c()); } mln_VAR(f, f_ | is_edge); Index: theo/color/mean_rgb_pix.hh --- theo/color/mean_rgb_pix.hh (revision 3313) +++ theo/color/mean_rgb_pix.hh (working copy) @@ -26,57 +26,57 @@ // reasons why the executable file might be covered by the GNU General // Public License. -#ifndef MLN_ACCU_SUM_PIX_HH -# define MLN_ACCU_SUM_PIX_HH +#ifndef MLN_ACCU_MEAN_RGB_PIX_HH +# define MLN_ACCU_MEAN_RGB_PIX_HH -/// \file mln/accu/sum_pix.hh +/// \file mln/accu/mean_rgb_pix.hh /// -/// Define an accumulator that computes a sum. +/// Define an accumulator that computes an rgb8 mean. # include <mln/core/concept/meta_accumulator.hh> # include <mln/accu/internal/base.hh> -# include <mln/util/pix.hh> // To prevent accu::sum_pix to work on pixels (ambiguous). +# include <mln/value/rgb8.hh> +# include <mln/algebra/vec.hh> -# include <mln/trait/value_.hh> // For mln_sum_pix. -# include <mln/value/builtin/all.hh> // In the case of summing builtin values. -# include <mln/literal/zero.hh> // For initialization. +# include <mln/util/pix.hh> +# include <mln/core/image/image2d.hh> namespace mln { + namespace accu { - /// Generic sum_pix accumulator class. - /*! - * Parameter \c T is the type of values that we sum. Parameter \c - * S is the type to store the value sum; the default type of - * \c S is the summation type (property) of \c T. - */ - template <typename P, typename S = mln_sum(mln_value(P))> - struct sum_pix : public mln::accu::internal::base< const S&, sum_pix<P,S> > + image2d<value::rgb8> rgb_image_; + + + /// Generic mean_rgb_pix accumulator class. + /// + template <typename Pix> + struct mean_rgb_pix : public mln::accu::internal::base< value::rgb8, mean_rgb_pix<Pix> > { - typedef P argument; + typedef Pix argument; - sum_pix(); + mean_rgb_pix(); /// Manipulators. /// \{ void init(); void take(const argument& t); - void take(const sum_pix<P,S>& other); + void take(const mean_rgb_pix<Pix>& other); /// \} - void set_value(S v) - { - s_ = v; - } +// void set_value(S v) +// { +// s_ = v; +// } /// Get the value of the accumulator. - const S& to_result() const; + value::rgb8 to_result() const; /// Check whether this accu is able to return a result. /// Always true here. @@ -84,70 +84,59 @@ protected: - S s_; + typedef algebra::vec<3,float> vec_t; + vec_t s_; + unsigned n_; }; - namespace meta - { - - /// Meta accumulator for sum_pix. - struct sum_pix : public Meta_Accumulator< sum_pix > - { - template <typename P, typename S = mln_sum(mln_value(P))> - struct with - { - typedef accu::sum_pix<P, S> ret; - }; - }; - - } // end of namespace mln::accu::meta - - # ifndef MLN_INCLUDE_ONLY - template <typename P, typename S> + template <typename Pix> inline - sum_pix<P,S>::sum_pix() + mean_rgb_pix<Pix>::mean_rgb_pix() { init(); } - template <typename P, typename S> + template <typename Pix> inline void - sum_pix<P,S>::init() + mean_rgb_pix<Pix>::init() { - s_ = literal::zero; + s_ = vec_t::zero; + n_ = 0; } - template <typename P, typename S> + template <typename Pix> inline - void sum_pix<P,S>::take(const argument& p) + void mean_rgb_pix<Pix>::take(const argument& px) { - s_ += /* 1 + */ p.v(); + s_ += vec_t(rgb_image_(px.p())); + ++n_; } - template <typename P, typename S> + template <typename Pix> inline void - sum_pix<P,S>::take(const sum_pix<P,S>& other) + mean_rgb_pix<Pix>::take(const mean_rgb_pix<Pix>& other) { s_ += other.s_; + n_ += other.n_; } - template <typename P, typename S> + template <typename Pix> inline - const S& - sum_pix<P,S>::to_result() const + value::rgb8 + mean_rgb_pix<Pix>::to_result() const { - return s_; + return algebra::vec<3, unsigned>(s_ / n_); } - template <typename P, typename S> + template <typename Pix> inline bool - sum_pix<P,S>::is_valid() const + mean_rgb_pix<Pix>::is_valid() const { return true; } @@ -159,4 +148,4 @@ } // end of namespace mln -#endif // ! MLN_ACCU_SUM_PIX_HH +#endif // ! MLN_ACCU_MEAN_RGB_PIX_HH Index: theo/color/change_attributes.hh --- theo/color/change_attributes.hh (revision 3313) +++ theo/color/change_attributes.hh (working copy) @@ -38,12 +38,58 @@ + // Test attribute growing property. + // -------------------------------- + + template <typename T, typename A> + inline + bool + test_attribute_growing_property(const T& t, const A& a) + { + typedef typename T::nodes_t N; + mln_fwd_piter(N) n(t.nodes()); + for_all(n) + if (a(t.parent(n)) < a(n)) + return false; + return true; + } + + template <typename T, typename A> + inline + void + invariant__attribute_growing_property(const T& t, const A& a) + { + mln_invariant(test_attribute_growing_property(t, a)); + } + + + + + // Make attributes grow. + // -------------------------------- + + template <typename T, typename A> + inline + void + make_attribute_grow(const T& t, A& a) + { + typedef typename T::nodes_t N; + mln_fwd_piter(N) n(t.nodes()); + for_all(n) + if (a(t.parent(n)) < a(n)) + a(t.parent(n)) = a(n); + + mln_postcondition(test_attribute_growing_property(t, a)); + } + + + // Back-propagate values from nodes to component sites. // ---------------------------------------------------- - template <typename A, typename T> + template <typename T, typename A> void - back_propagate(A& a, const T& t) + back_propagate(const T& t, A& a) { mln_fwd_piter(T) p(t.domain()); for_all(p) @@ -243,13 +289,13 @@ - // Fuse down. + // Fuse up. // ---------- template <typename T, typename A> inline void - fuse_down_attributes(const T& t, A& a, bool echo = false) + fuse_up_attributes(const T& t, A& a, bool echo = false) { if (echo) { @@ -273,6 +319,7 @@ + // Rand. // -----

1 0

3313: Update segmentation code.
by Thierry Geraud 08 Feb '09

08 Feb '09

https://svn.lrde.epita.fr/svn/oln/trunk/milena/sandbox Index: ChangeLog from Thierry Geraud <thierry.geraud(a)lrde.epita.fr> Update segmentation code. * theo/color/segment.cc: Rename as... * theo/color/segment_rgb_edges.cc: ...this. Update. * theo/color/segment_debase.cc: Rename as... * theo/color/segment_gl_pixels.cc: ...this. Update. * theo/color/segment.hh (filter): Add change_kind. * theo/color/change_attributes.hh (extinct_attributes, move_down_attributes): Use echo. (fuse_down_attributes): Use echo. change_attributes.hh | 94 +++++++++++++++++++++++++++++++++++++-------------- segment.hh | 27 +++++++++++++- segment_gl_pixels.cc | 32 ++++++++++++----- segment_rgb_edges.cc | 66 ++++++++++++++++++++--------------- 4 files changed, 154 insertions(+), 65 deletions(-) Index: theo/color/segment.hh --- theo/color/segment.hh (revision 3312) +++ theo/color/segment.hh (working copy) @@ -329,8 +329,11 @@ mln_concrete(F) filter(const F& f, // a "gradient" of color image const N& nbh, + const A& a_, // an attribute + unsigned change_kind, bool do_extinction, + unsigned n_objects, bool echo = false) { @@ -350,8 +353,25 @@ debug::println("a = ", a); } + switch (change_kind) + { + case 0: + break; + case 1: + std::cout << "move down attributes" << std::endl; + move_down_attributes(t, a, echo); + break; + case 2: + std::cout << "fuse up attributes" << std::endl; + fuse_down_attributes(t, a, echo); + break; + } + if (do_extinction) - extinct_attributes(t, a); + { + std::cout << "do extinction" << std::endl; + extinct_attributes(t, a, echo); + } if (echo) debug::println("a' =", a | t.nodes()); @@ -362,10 +382,13 @@ less, lambda, // output echo); - if (do_extinction == false) + if (do_extinction == false && change_kind == 0) + { + std::cout << "testing filter result v. classical method" << std::endl; test_filter(a_, lambda, f, g, nbh, n_objects, less, echo); + } return g; } Index: theo/color/segment_rgb_edges.cc --- theo/color/segment_rgb_edges.cc (revision 3312) +++ theo/color/segment_rgb_edges.cc (working copy) @@ -22,10 +22,11 @@ #include <mln/morpho/dilation.hh> #include <mln/morpho/erosion.hh> #include <mln/morpho/meyer_wst.hh> - +#include <mln/labeling/compute.hh> #include <mln/accu/count.hh> #include <mln/accu/volume.hh> +#include <mln/accu/mean.hh> #include "sum_pix.hh" @@ -241,8 +242,9 @@ void usage(char* argv[]) { - std::cerr << "usage: " << argv[0] << " input.ppm n extinction output.ppm echo" << std::endl; + std::cerr << "usage: " << argv[0] << " input.ppm n change extinction echo output.ppm" << std::endl; std::cerr << " n >= 2" << std::endl; + std::cerr << " change = 0 (none), 1 (move-down), or 2 (fuse-up)" << std::endl; std::cerr << " extinction = 0 (none) or 1 (effective)" << std::endl; std::cerr << " echo = 0 (mute) or 1 (verbose)" << std::endl; abort(); @@ -256,12 +258,10 @@ using value::int_u8; using value::rgb8; - if (argc != 6) + if (argc != 7) usage(argv); - { - // Color version. // -------------- @@ -269,9 +269,17 @@ image2d<rgb8> input; io::ppm::load(input, argv[1]); + unsigned n_objects = atoi(argv[2]); - bool do_extinction = atoi(argv[3]); + int change_kind = atoi(argv[3]); + if (change_kind < 0 || change_kind > 2) + usage(argv); + + int do_extinction = atoi(argv[4]); + if (do_extinction != 0 && do_extinction != 1) + usage(argv); + bool echo = atoi(argv[5]); @@ -295,7 +303,8 @@ accu::blen_pix a_; f_t g = filter(f, e2e(), - a_, do_extinction, + a_, + change_kind, do_extinction, n_objects, echo); @@ -324,7 +333,7 @@ } image2d<L> w_all = w.unmorph_(); - { + // edges -> squares mln_VAR(w_squares, w_all | is_square); data::paste(morpho::dilation(extend(w_squares, pw::value(w_all)), @@ -335,38 +344,37 @@ data::paste(morpho::erosion(extend(w_points, pw::value(w_all)), c4().win()), w_all); - } - io::pgm::save( level::transform(w_all, convert::to_fun(L_to_int_u8)), - "temp_w_all.pgm" ); - } -// { -// // Gray-level version. + // Outputing. + // ---------- -// image2d<int_u8> f_; -// io::pgm::load(f_, argv[1]); -// unsigned n_objects = atoi(argv[2]); + typedef algebra::vec<3,float> vec3f; -// mln_VAR(f, f_ | is_edge); -// typedef f_t I; + util::array<vec3f> m_3f = labeling::compute(accu::mean<rgb8>(), + input, + full2image(w_all), + nbasins); + m_3f[0] = vec3f::zero; -// typedef p_array<point2d> S; -// S s = level::sort_psites_decreasing(f); + util::array<rgb8> m; + convert::from_to(m_3f, m); -// typedef morpho::tree::data<I,S> tree_t; -// tree_t t(f, s, e2e()); + io::ppm::save( level::transform(w_all, + convert::to< fun::i2v::array<rgb8> >(m) ), + argv[6] ); -// accu::count< util::pix > a_; -// mln_VAR(a, compute_attribute_on_nodes(a_, t)); -// f_t g = filter(a, t, e2e(), n_objects); +// debug::println("input_", input_); +// debug::println("w_squares", w_squares); -// unsigned nbasins; -// debug::println("wst =", morpho::meyer_wst(g, e2e(), nbasins)); -// } +// FIXME: The code below does not work! +// util::array<vec3f> m_3f = labeling::compute(accu::mean<rgb8>(), +// input_, +// w_squares, +// nbasins); } Index: theo/color/change_attributes.hh --- theo/color/change_attributes.hh (revision 3312) +++ theo/color/change_attributes.hh (working copy) @@ -96,25 +96,6 @@ } - // Modified version. - - template <typename T, typename I, typename M> - inline - mln_value(I) - extinct_rec__(const T& t, // tree - const I& a, // original attribute image - I& ea, // extincted attribute image - M& mark, - const mln_psite(I)& p) - { - mln_invariant(mark(p) == false); - mark(p) = true; - if (t.parent(p) == p || mark(t.parent(p)) == true) // Stop. - return a(t.parent(p)); // The parent attribute! - return ea(p) = extinct_rec__(t, a, ea, mark, t.parent(p)); - } - - } // end of internal @@ -123,8 +104,15 @@ template <typename T, typename I> void extinct_attributes(const T& t, // Tree. - I& a) // Attribute image. + I& a, // Attribute image. + bool echo = false) + { + if (echo) { + std::cout << "before:" << std::endl; + display_tree_attributes(t, a); + } + typedef mln_site(I) P; typedef mln_value(I) A; // Type of attributes. @@ -148,15 +136,47 @@ } // debug::println(mark | t.nodes()); + + if (echo) + { + std::cout << "after:" << std::endl; + display_tree_attributes(t, a); + } } + /* // Modified version. + // + // The extinction moves down the parent attribute. With the 1st + // experiments, that does not work. Yet, it is better to first modify + // the attributes (move down the parent values) the classically extinct. + + namespace internal + { + + template <typename T, typename I, typename M> + inline + mln_value(I) + extinct_rec__(const T& t, // tree + const I& a, // original attribute image + I& ea, // extincted attribute image + M& mark, + const mln_psite(I)& p) + { + mln_invariant(mark(p) == false); + mark(p) = true; + if (t.parent(p) == p || mark(t.parent(p)) == true) // Stop. + return a(t.parent(p)); // The parent attribute! + return ea(p) = extinct_rec__(t, a, ea, mark, t.parent(p)); + } + + } // end of internal template <typename T, typename I> void - extinct_attributes__(const T& t, // Tree. + extinct_attributes_new(const T& t, // Tree. I& a) // Attribute image. { typedef mln_site(I) P; @@ -188,23 +208,36 @@ // debug::println(mark | t.nodes()); } + */ // Move down. // ---------- - template <typename A, typename T> + template <typename T, typename A> inline void - move_down_attributes(A& a, const T& t) + move_down_attributes(const T& t, A& a, bool echo = false) + { + if (echo) { + std::cout << "before:" << std::endl; + display_tree_attributes(t, a); + } typedef typename T::nodes_t N; mln_fwd_piter(N) n(t.nodes()); for_all(n) a(n) = a(t.parent(n)); + // Test. for_all(n) mln_invariant(a(n) <= a(t.parent(n))); + + if (echo) + { + std::cout << "after:" << std::endl; + display_tree_attributes(t, a); + } } @@ -213,11 +246,16 @@ // Fuse down. // ---------- - template <typename A, typename T> + template <typename T, typename A> inline void - fuse_down_attributes(A& a, const T& t) + fuse_down_attributes(const T& t, A& a, bool echo = false) { + if (echo) + { + std::cout << "before:" << std::endl; + display_tree_attributes(t, a); + } typedef typename T::nodes_t N; mln_fwd_piter(N) n(t.nodes()); for_all(n) @@ -225,6 +263,12 @@ for_all(n) mln_invariant(a(n) <= a(t.parent(n))); + + if (echo) + { + std::cout << "after:" << std::endl; + display_tree_attributes(t, a); + } } Index: theo/color/segment_gl_pixels.cc --- theo/color/segment_gl_pixels.cc (revision 3312) +++ theo/color/segment_gl_pixels.cc (working copy) @@ -17,8 +17,7 @@ #include <mln/morpho/elementary/gradient.hh> #include <mln/morpho/meyer_wst.hh> -#include <mln/accu/volume.hh> -#include "sum_pix.hh" +#include <mln/accu/height.hh> #include "segment.hh" @@ -28,8 +27,10 @@ void usage(char* argv[]) { - std::cerr << "usage: " << argv[0] << " input.pgm n extinction output.ppm echo" << std::endl; + std::cerr << "usage: " << argv[0] << " input.pgm n change extinction echo output.ppm" << std::endl; + std::cerr << "gray-level version on pixels (without edges)" << std::endl; std::cerr << " n >= 2" << std::endl; + std::cerr << " change = 0 (none), 1 (move-down), or 2 (fuse)" << std::endl; std::cerr << " extinction = 0 (none) or 1 (effective)" << std::endl; std::cerr << " echo = 0 (mute) or 1 (verbose)" << std::endl; abort(); @@ -45,20 +46,29 @@ using value::rgb8; - if (argc != 6) + if (argc != 7) usage(argv); // Gray-level debase version. // -------------------------- + typedef image2d<int_u8> I; I input; io::pgm::load(input, argv[1]); unsigned n_objects = atoi(argv[2]); - bool do_extinction = atoi(argv[3]); + + int change_kind = atoi(argv[3]); + if (change_kind < 0 || change_kind > 2) + usage(argv); + + int do_extinction = atoi(argv[4]); + if (do_extinction != 0 && do_extinction != 1) + usage(argv); + bool echo = atoi(argv[5]); @@ -69,7 +79,6 @@ // Changing input into 'f'. I f = morpho::elementary::gradient(input, c4()); - io::pgm::save(f, "temp_f.pgm"); // // granulometry: @@ -79,10 +88,15 @@ // accu::count< util::pix > a_; // accu::sum_pix< util::pix > a_; - accu::volume a_; + // accu::volume a_; + accu::height a_; + + // It seems that both extinction and changing attributes only + // properly works for the 'height' attribute. I g = filter(f, c4(), - a_, do_extinction, + a_, + change_kind, do_extinction, n_objects, echo); @@ -99,5 +113,5 @@ image2d<rgb8> output = level::convert(rgb8(), input); data::fill((output | (pw::value(w) == 0)).rw(), literal::red); - io::ppm::save(output, argv[4]); + io::ppm::save(output, argv[6]); }

1 0

3312: Have fastest morpho wst flooding, plus several fixes.
by Thierry Geraud 06 Feb '09

06 Feb '09

https://svn.lrde.epita.fr/svn/oln/trunk/milena Index: ChangeLog from Thierry Geraud <thierry.geraud(a)lrde.epita.fr> Have fastest morpho wst flooding, plus several fixes. * mln/morpho/watershed/flooding.hh (flooding_fastest): Finalize it. (flooding_dispatch): Activate the fastest version. * mln/io/pnm/load.hh (io::pnm::load): Fix trace balancing. * sandbox/fabien/labeling.hh (labeling_video_fastest): Make it work. * tests/morpho/watershed/flooding.cc: Augment. mln/io/pnm/load.hh | 2 mln/morpho/watershed/flooding.hh | 82 +++++++++++++++++++++++-------------- sandbox/fabien/labeling.hh | 49 ++++++++++++---------- tests/morpho/watershed/flooding.cc | 42 +++++++++++++++--- 4 files changed, 115 insertions(+), 60 deletions(-) Index: mln/morpho/watershed/flooding.hh --- mln/morpho/watershed/flooding.hh (revision 3311) +++ mln/morpho/watershed/flooding.hh (working copy) @@ -51,6 +51,8 @@ # include <mln/core/site_set/p_queue_fast.hh> # include <mln/core/site_set/p_priority.hh> +# include <mln/extension/adjust_fill.hh> + namespace mln { @@ -157,6 +159,7 @@ { psite p = queue.front(); queue.pop(); + // Last seen marker adjacent to P. marker adjacent_marker = unmarked; // Has P a single adjacent marker? @@ -193,10 +196,14 @@ } } } + trace::exiting("morpho::watershed::impl::generic::flooding"); return output; } + } // end of namespace mln::morpho::watershed::impl::generic + + // Fastest version. @@ -217,86 +224,100 @@ typedef mln_value(I) V; const V max = mln_max(V); - // Initialize the output with the markers (minima components). - mln_ch_value(I, marker) output = - labeling::regional_minima (input, nbh, n_basins); + extension::adjust_fill(input, nbh, max); - typedef mln_psite(I) psite; + // Initialize the output with the markers (minima components). + typedef mln_ch_value(I, L) O; + O output = labeling::regional_minima(input, nbh, n_basins); + extension::fill(output, unmarked); // Ordered queue. - typedef p_queue_fast<psite> Q; + typedef p_queue_fast<unsigned> Q; p_priority<V, Q> queue; + // FIXME: With typedef std::pair<V, unsigned> VU; + // std::priority_queue<VU> queue; + // we do not get the same results!!! + // In_queue structure to avoid processing sites several times. mln_ch_value(I, bool) in_queue; initialize(in_queue, input); data::fill(in_queue, false); + extension::fill(in_queue, true); // Insert every neighbor P of every marked area in a // hierarchical queue, with a priority level corresponding to // the grey level input(P). - mln_piter(I) p(output.domain()); - mln_niter(N) n(nbh, p); - for_all (p) - if (output(p) == unmarked) - for_all(n) - if (output.domain().has(n) && output(n) != unmarked) - { - queue.push(max - input(p), p); - in_queue(p) = true; + mln_pixter(const O) p_out(output); + mln_nixter(const O, N) n_out(p_out, nbh); + for_all(p_out) + if (p_out.val() == unmarked) + for_all(n_out) + if (n_out.val() != unmarked) + { + unsigned po = p_out.offset(); + queue.push(max - input.element(po), po); + in_queue.element(po) = true; break; } /* Until the queue is empty, extract a psite P from the hierarchical queue, at the highest priority level, that is, the lowest level. */ + util::array<int> dp = offsets_wrt(input, nbh); + const unsigned n_nbhs = dp.nelements(); while (! queue.is_empty()) { - psite p = queue.front(); + unsigned p = queue.front(); queue.pop(); + // Last seen marker adjacent to P. marker adjacent_marker = unmarked; // Has P a single adjacent marker? bool single_adjacent_marker_p = true; - mln_niter(N) n(nbh, p); - for_all(n) - if (output.domain().has(n) && output(n) != unmarked) + for (unsigned i = 0; i < n_nbhs; ++i) + { + unsigned n = p + dp[i]; + if (output.element(n) != unmarked) // In the border, output is unmarked so n is ignored. { if (adjacent_marker == unmarked) { - adjacent_marker = output(n); + adjacent_marker = output.element(n); single_adjacent_marker_p = true; } else - if (adjacent_marker != output(n)) + if (adjacent_marker != output.element(n)) { single_adjacent_marker_p = false; break; } } + } /* If the neighborhood of P contains only psites with the same label, then P is marked with this label, and its neighbors that are not yet marked are put into the hierarchical queue. */ if (single_adjacent_marker_p) { - output(p) = adjacent_marker; - for_all(n) - if (output.domain().has(n) && output(n) == unmarked - && ! in_queue(n)) + output.element(p) = adjacent_marker; + for (unsigned i = 0; i < n_nbhs; ++i) { - queue.push(max - input(n), n); - in_queue(n) = true; + unsigned n = p + dp[i]; + if (output.element(n) == unmarked + && ! in_queue.element(n)) // In the border, in_queue is true so n is ignored. + { + queue.push(max - input.element(n), n); + in_queue.element(n) = true; + } } } } + trace::exiting("morpho::watershed::impl::flooding_fastest"); return output; } - } // end of namespace mln::morpho::watershed::impl::generic - } // end of namespace mln::morpho::watershed::impl @@ -322,8 +343,7 @@ flooding_dispatch(metal::true_, const Image& input, const Neighborhood<N>& nbh, L& n_basins) { - return impl::generic::flooding(input, nbh, n_basins); -// return impl::generic::flooding_fastest(input, nbh, n_basins); + return impl::flooding_fastest(input, nbh, n_basins); } template <typename I, typename N, typename L> @@ -341,7 +361,7 @@ input, nbh, n_basins); } - } // end of namespace mln::morpho::watershed::impl + } // end of namespace mln::morpho::watershed::internal // Facade. Index: mln/io/pnm/load.hh --- mln/io/pnm/load.hh (revision 3311) +++ mln/io/pnm/load.hh (working copy) @@ -192,7 +192,7 @@ if (type == (type_ - 3)) pnm::load_ascii(file, ima); - trace::entering("mln::io::pnm::load"); + trace::exiting("mln::io::pnm::load"); return ima; } Index: sandbox/fabien/labeling.hh --- sandbox/fabien/labeling.hh (revision 3311) +++ sandbox/fabien/labeling.hh (working copy) @@ -243,12 +243,9 @@ extension::adjust(input, nbh); - // Local type. - typedef mln_psite(I) P; - // Auxiliary data. mln_ch_value(I, bool) deja_vu; - mln_ch_value(I, P) parent; + mln_ch_value(I, unsigned) parent; // Output. mln_ch_value(I, L) output; @@ -271,42 +268,52 @@ // First Pass. { - mln_pixter(const I) p(input); - mln_nixter(const I, N) n(p, nbh); - for_all(p) if (f.handles_(p.offset())) + mln_pixter(const I) px(input); + mln_nixter(const I, N) nx(px, nbh); + for_all(px) { - // Make-Set. - parent(p).val() = p; - f.init_attr_(p.offset()); + unsigned p = px.offset(); + if (! f.handles_(p)) + continue; - for_all(n) - if (input.has(n) && deja_vu(n)) + // Make-Set. + parent.element(p) = p; + f.init_attr_(p); + for_all(nx) + { + unsigned n = nx.offset(); + if (deja_vu.element(n)) { - if (f.equiv_(n.offset(), p.offset())) + if (f.equiv_(n, p)) { // Do-Union. - unsigned r = find_root_fastest(parent, n.val()); + unsigned r = find_root_fastest(parent, n); if (r != p) { parent.element(r) = p; - f.merge_attr_(r, p.offset()); + f.merge_attr_(r, p); } } else - f.do_no_union_(n.offset(), p.offset()); + f.do_no_union_(n, p); } - deja_vu(p) = true; + } + + deja_vu.element(p) = true; } } // Second Pass. { - mln_bkd_pixter(I) p(input); - for_all(p) if (f.handles_(p)) + mln_bkd_pixter(const I) px(input); + for_all(px) { + unsigned p = px.offset(); + if (! f.handles_(p)) + continue; if (parent.element(p) == p) // if p is root { - if (f.labels_(p.offset())) + if (f.labels_(p)) { if (nlabels == mln_max(L)) { @@ -317,7 +324,7 @@ } } else - output.element(p) = output(parent.element(p)); + output.element(p) = output.element(parent.element(p)); } status = true; } Index: tests/morpho/watershed/flooding.cc --- tests/morpho/watershed/flooding.cc (revision 3311) +++ tests/morpho/watershed/flooding.cc (working copy) @@ -36,26 +36,54 @@ #include <mln/core/alias/neighb2d.hh> #include <mln/value/int_u8.hh> +#include <mln/value/int_u16.hh> #include <mln/morpho/watershed/flooding.hh> +#include <mln/level/transform.hh> #include <mln/io/pgm/load.hh> #include <mln/io/pgm/save.hh> -#include "tests/data.hh" +#include <mln/util/timer.hh> + + +struct f_16_to_8 : mln::Function_v2v< f_16_to_8 > +{ + typedef mln::value::int_u8 result; + result operator()(const mln::value::int_u16& v) const + { + if (v == 0) + return 0; + return 1 + (v - 1) % 255; + } +}; int main() { using namespace mln; using value::int_u8; + using value::int_u16; image2d<int_u8> input; - io::pgm::load(input, MLN_IMG_DIR "/squares.pgm"); + io::pgm::load(input, "/squares.pgm"); - typedef int_u8 L; - L nbasins; - image2d<L> output = morpho::watershed::flooding(input, c4(), nbasins); - - io::pgm::save(output, "out.pgm"); + typedef int_u16 L; + L n_basins; + { + util::timer t; + t.start(); + image2d<L> output = morpho::watershed::impl::generic::flooding(input, c4(), n_basins); + std::cout << "gen: " << t << std::endl; + io::pgm::save(level::transform(output, f_16_to_8()), + "tmp_ref.pgm"); + } + { + util::timer t; + t.start(); + image2d<L> output = morpho::watershed::impl::flooding_fastest(input, c4(), n_basins); + std::cout << "fast: " << t << std::endl; + io::pgm::save(level::transform(output, f_16_to_8()), + "tmp_out.pgm"); + } }

1 0

r3311: Implement labeling_video_fastest
by Fabien Freling 06 Feb '09

06 Feb '09

URL: https://svn.lrde.epita.fr/svn/oln/trunk/milena/sandbox ChangeLog: 2009-02-06 Fabien Freling <freling(a)lrde.epita.fr> Implement labeling_video_fastest. * fabien/labeling.hh: Implement video_fastest. * fabien/level.cc: Test file. * fabien/level.hh: Implement fastest implementation. --- labeling.hh | 22 +++++++++---------- level.cc | 69 ++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++ level.hh | 48 +++++++++++++---------------------------- 3 files changed, 96 insertions(+), 43 deletions(-) Index: trunk/milena/sandbox/fabien/level.hh =================================================================== --- trunk/milena/sandbox/fabien/level.hh (revision 3310) +++ trunk/milena/sandbox/fabien/level.hh (revision 3311) @@ -36,7 +36,9 @@ # include <mln/core/concept/image.hh> # include <mln/core/concept/neighborhood.hh> -# include <mln/canvas/labeling.hh> + +# include "labeling.hh" + # include <mln/data/fill.hh> @@ -93,35 +95,10 @@ namespace impl { - - struct labeling_functor_base - { - void init() {} - - template <typename P> - bool handles(const P&) const { return true; } - - template <typename L, typename R> - bool equiv(const L&, const R&) const { return false; } - - template <typename P> - bool labels(const P&) const { return true; } - - template <typename L, typename R> - void do_no_union(const L&, const R&) {} - - template <typename P> - void init_attr(const P&) {} - - template <typename L, typename R> - void merge_attr(const L&, const R&) {} - }; - - // Generic functor. template <typename I> - struct level_functor : labeling_functor_base + struct level_functor { typedef mln_psite(I) P; @@ -138,14 +115,19 @@ bool handles(const P& p) const { return input(p) == val; } bool equiv(const P& n, const P&) const { return input(n) == val; } bool labels(const P&) const { return true; } + void do_no_union(const P& n, const P& p) {} + void init_attr(const P&) {} + void merge_attr(const P& r, const P& p) {} // Fastest implementation void init_() {} - bool handles_(const P& p) const { return input.element(p) == val; } - bool equiv_(const P& n, const P&) const { return input.element(n) == val; } - bool labels_(const P&) const { return true; } - + bool handles_(unsigned p) const { return input.element(p) == val; } + bool equiv_(unsigned n, unsigned) const { return input.element(n) == val; } + bool labels_(unsigned) const { return true; } + void do_no_union_(unsigned n, unsigned p) {} + void init_attr_(unsigned) {} + void merge_attr_(unsigned r, unsigned p) {} // end of Requirements. @@ -156,6 +138,8 @@ } }; + } // end of namespace mln::labeling::impl + @@ -171,7 +155,7 @@ internal::level_tests(input, val, nbh, nlabels); mln_ch_value(I, L) output; - level_functor f(input, val); + impl::level_functor f(input, val); output = canvas::labeling_video(input, nbh, nlabels, f); trace::exiting("labeling::level"); Index: trunk/milena/sandbox/fabien/labeling.hh =================================================================== --- trunk/milena/sandbox/fabien/labeling.hh (revision 3310) +++ trunk/milena/sandbox/fabien/labeling.hh (revision 3311) @@ -232,7 +232,7 @@ typename F> mln_ch_value(I, L) labeling_video_fastest(const Image& input_, const Neighborhood<N>& nbh_, - F& f, L& nlabels) + L& nlabels, F& f) { trace::entering("canvas::impl::labeling_video_fastest"); @@ -273,27 +273,27 @@ { mln_pixter(const I) p(input); mln_nixter(const I, N) n(p, nbh); - for_all(p) if (f.handles_(p)) + for_all(p) if (f.handles_(p.offset())) { // Make-Set. - parent.element(p) = p; - f.init_attr(p); + parent(p).val() = p; + f.init_attr_(p.offset()); for_all(n) - if (input.domain().has(n) && deja_vu(n)) + if (input.has(n) && deja_vu(n)) { - if (f.equiv_(n, p)) + if (f.equiv_(n.offset(), p.offset())) { // Do-Union. - unsigned r = find_root_fastest(parent, n); + unsigned r = find_root_fastest(parent, n.val()); if (r != p) { parent.element(r) = p; - f.merge_attr_(r, p); + f.merge_attr_(r, p.offset()); } } else - f.do_no_union_(n, p); + f.do_no_union_(n.offset(), p.offset()); } deja_vu(p) = true; } @@ -306,7 +306,7 @@ { if (parent.element(p) == p) // if p is root { - if (f.labels_(p)) + if (f.labels_(p.offset())) { if (nlabels == mln_max(L)) { @@ -488,7 +488,7 @@ && mln_is_simple_neighborhood(N)::value }; - return impl::generic::labeling(metal::bool_<test>(), input, + return labeling_video(metal::bool_<test>(), input, nbh, nlabels, functor); } Index: trunk/milena/sandbox/fabien/level.cc =================================================================== --- trunk/milena/sandbox/fabien/level.cc (revision 0) +++ trunk/milena/sandbox/fabien/level.cc (revision 3311) @@ -0,0 +1,69 @@ +// 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 +// of the GNU General Public License version 2 as published by the +// Free Software Foundation. +// +// This library is distributed in the hope that it will be useful, +// but WITHOUT ANY WARRANTY; without even the implied warranty of +// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU +// General Public License for more details. +// +// You should have received a copy of the GNU General Public License +// along with this library; see the file COPYING. If not, write to +// the Free Software Foundation, 51 Franklin Street, Fifth Floor, +// Boston, MA 02111-1307, USA. +// +// As a special exception, you may use this file as part of a free +// software library without restriction. Specifically, if other files +// instantiate templates or use macros or inline functions from this +// file, or you compile this file and link it with other files to +// produce an executable, this file does not by itself cause the +// resulting executable to be covered by the GNU General Public +// License. This exception does not however invalidate any other +// reasons why the executable file might be covered by the GNU General +// Public License. + +/// \file tests/labeling/level.cc +/// +/// Test on mln::labeling::level. + +#include <mln/core/image/image2d.hh> +#include <mln/core/alias/neighb2d.hh> +#include <mln/value/int_u8.hh> +#include <mln/io/pgm/load.hh> + +#include <mln/accu/count.hh> +#include <mln/accu/compute.hh> + +#include "level.hh" + +#include <mln/pw/all.hh> +#include <mln/core/image/image_if.hh> + +#include <mln/debug/println.hh> + +#include <tests/data.hh> + + +int main() +{ + using namespace mln; + using value::int_u8; + + image2d<int_u8> lena = io::pgm::load<int_u8>(MLN_IMG_DIR "/tiny.pgm"); + image2d<bool> lvl(lena.domain()); + + unsigned n, npixels = 0; + for (unsigned l = 0; l <= 255; ++l) + { + image2d<unsigned> labels = labeling::level(lena, l, c4(), n); + unsigned npix = + accu::compute(accu::meta::count(), + labels | (pw::value(labels) != pw::cst(0u))); + npixels += npix; + } + mln_assertion(npixels == lena.nsites()); +}

1 0

3310: configure.ac: Keep the compatibility with Libtool 1.5.
by Roland Levillain 06 Feb '09

06 Feb '09

--- configure.ac | 3 ++- 1 files changed, 2 insertions(+), 1 deletions(-) diff --git a/configure.ac b/configure.ac index 260baaa..da2178a 100644 --- a/configure.ac +++ b/configure.ac @@ -103,7 +103,8 @@ fi ## ------------------ ## # Use Libtool. -LT_INIT +# To be replaced by a call to LT_INIT as soon as Libtool 2.2 is used. +AC_PROG_LIBTOOL # Check for Darwin. AC_CANONICAL_HOST -- 1.6.1.2

1 0