[Olena-patches] r3285: Implement fastest versions of canvas::labeling

URL: https://svn.lrde.epita.fr/svn/oln/trunk/milena/sandbox ChangeLog: 2009-02-04 Fabien Freling &lt;freling(a)lrde.epita.fr&gt; Implement fastest versions of canvas::labeling. * fabien/regional_maxima.hh: New. --- labeling.hh | 199 +++++++++++++++++++++++++++++++++++++++++++++++++---- regional_maxima.hh | 171 +++++++++++++++++++++++++++++++++++++++++++++ 2 files changed, 357 insertions(+), 13 deletions(-) Index: trunk/milena/sandbox/fabien/regional_maxima.hh =================================================================== --- trunk/milena/sandbox/fabien/regional_maxima.hh (revision 0) +++ trunk/milena/sandbox/fabien/regional_maxima.hh (revision 3285) @@ -0,0 +1,171 @@ +// 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_REGIONAL_MAXIMA_HH +# define MLN_LABELING_REGIONAL_MAXIMA_HH + +/// \file mln/labeling/regional_maxima.hh +/// +/// Connected component labeling of the regional maxima of an image. + +# include <mln/core/concept/image.hh> +# include <mln/core/concept/neighborhood.hh> +# include <mln/canvas/labeling.hh> +# include <mln/data/fill.hh> +# include <mln/level/sort_psites.hh> + + +namespace mln +{ + + namespace labeling + { + + /*! Connected component labeling of the regional maxima of an + * image. + * + * \param[in] input The input image. + * \param[in] nbh The connexity of the regional maxima. + * \param[out] nlabels The number of labeled regions. + * \return The label image. + * + */ + template <typename I, typename N, typename L> + mln_ch_value(I, L) + regional_maxima(const Image<I>& input, const Neighborhood<N>& nbh, + L& nlabels); + + + +# ifndef MLN_INCLUDE_ONLY + + namespace impl + { + + // Generic functor. + + template <typename I_, typename N_, typename L_> + struct regional_maxima_functor + { + typedef mln_psite(I_) P; + + // requirements from mln::canvas::labeling: + + typedef I_ I; + typedef N_ N; + typedef L_ L; + typedef p_array<P> S; + + const I& input; + const N& nbh; + S s; + + void init() { data::fill(attr, true); } + bool handles(const P&) const { return true; } + bool labels(const P& p) const { return attr(p); } + bool equiv(const P& n, const P& p) const { return input(n) == + input(p); } + void do_no_union(const P& n, const P& p) { mln_invariant(input(n) > + input(p)); + attr(p) = false; } + void init_attr(const P&) {} + void merge_attr(const P& r, const P& p) { attr(p) = attr(p) && + attr(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)) + { + 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> + mln_ch_value(I, L) + regional_maxima(const Image<I>& input_, const Neighborhood<N>& nbh_, + L& nlabels) + { + trace::entering("labeling::regional_maxima"); + + const I& input = exact(input_); + 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); + + trace::exiting("labeling::regional_maxima"); + return output; + } + +# endif // ! MLN_INCLUDE_ONLY + + } // end of namespace mln::labeling + +} // end of namespace mln + + +#endif // ! MLN_LABELING_REGIONAL_MAXIMA_HH Index: trunk/milena/sandbox/fabien/labeling.hh =================================================================== --- trunk/milena/sandbox/fabien/labeling.hh (revision 3284) +++ trunk/milena/sandbox/fabien/labeling.hh (revision 3285) @@ -201,7 +201,7 @@ - // Fastest version + // Fastest video version template <typename I> static inline @@ -214,9 +214,11 @@ return parent.element(x) = find_root(parent, parent.element(x)); } + // FIXME: Use the same functer for the generic and the fastest versions + template <typename I, typename N, typename F, typename L> mln_ch_value(I, L) - labeling_fastest(const Image<I>& input_, const Neighborhood<N>& nbh_, + labeling_fastest_video(const Image<I>& input_, const Neighborhood<N>& nbh_, F& f, L& nlabels) { trace::entering("canvas::impl::labeling"); @@ -269,7 +271,7 @@ if (f.equiv(n, p)) { // Do-Union. - P r = find_root(parent, n); + unsigned r = find_root_fastest(parent, n); if (r != p) { parent.element(r) = p; @@ -278,8 +280,7 @@ } else f.do_no_union(n, p); - } - deja_vu(p) = true; + (p) = true; } } @@ -310,6 +311,121 @@ return output; } + + + // Fastest sorted version + + template <typename I, typename N, typename F, typename L> + mln_ch_value(I, L) + labeling_fastest_sorted(const Image<I>& input_, + const Neighborhood<N>& nbh_, + S& s, F& f, L& nlabels) + { + trace::entering("canvas::impl::labeling"); + + // FIXME: Test?! + + const I& input = exact(input_); + const N& nbh = exact(nbh_); + + typedef typename F::S S; + + // Local type. + typedef mln_psite(I) P; + + // Auxiliary data. + mln_ch_value(I, bool) deja_vu; + mln_ch_value(I, P) parent; + + // Output. + mln_ch_value(I, L) output; + bool status; + + // Initialization. + { + initialize(deja_vu, input); + mln::data::fill(deja_vu, false); + + initialize(parent, input); + + initialize(output, input); + mln::data::fill(output, L(literal::zero)); + nlabels = 0; + + f.init(); // Client initialization. + } + + util::array<int> dp = offsers_wrt(input, nbh); + const unsigned n_nbhs = dp.nelements(); + + const unsigned n_points = s.elements(); + + // 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[n]) + continue; + + if (f.equiv(n, p)) + { + // Do-Union. + unsigned r = find_root_fastest(parent, n); + if (input.element(r) != input.element(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(parent.element(p)); + } + status = true; + } + + trace::exiting("canvas::impl::labeling"); + return output; + } + } // end of namespace mln::canvas::impl @@ -319,10 +435,50 @@ namespace internal { + // Video + + template <typename I, typename N, typename F, typename L> + inline + mln_ch_value(I, L) + labeling_video(metal::false_, const Image<I>& input, + const Neighborhood<N>& nbh, F& functor, L& nlabels) + { + // FIXME:s = input.domain() + return impl::generic::labeling(input, nbh, functor, nlabels); + } + + template <typename I, typename N, typename F, typename L> + inline + mln_ch_value(I, L) + labeling_video(metal::true_, const Image<I>& input, + const Neighborhood<N>& nbh, F& functor, L& nlabels) + { + return impl::labeling_fastest_video(input, nbh, functor, nlabels); + } + template <typename I, typename N, typename F, typename L> inline mln_ch_value(I, L) - labeling(metal::false_, const Image<I>& input, + labeling_video_dispatch(const Image<I>& input, const Neighborhood<N>& nbh, + F& functor, L& nlabels) + { + enum { + test = mlc_equal(mln_trait_image_speed(I), + trait::image::speed::fastest)::value + && + mln_is_simple_neighborhood(N)::value + }; + return impl::generic::labeling_video(metal::bool_<test>(), input, nbh, + functor, nlabels); + } + + + // Sorted + + template <typename I, typename N, typename F, typename L> + inline + mln_ch_value(I, L) + labeling_sorted(metal::false_, const Image<I>& input, const Neighborhood<N>& nbh, F& functor, L& nlabels) { return impl::generic::labeling(input, nbh, functor, nlabels); @@ -331,16 +487,16 @@ template <typename I, typename N, typename F, typename L> inline mln_ch_value(I, L) - labeling(metal::true_, const Image<I>& input, + labeling_sorted(metal::true_, const Image<I>& input, const Neighborhood<N>& nbh, F& functor, L& nlabels) { - return impl::labeling_fastest(input, nbh, functor, nlabels); + return impl::labeling_fastest_sorted(input, nbh, functor, nlabels); } template <typename I, typename N, typename F, typename L> inline mln_ch_value(I, L) - labeling_dispatch(const Image<I>& input, const Neighborhood<N>& nbh, + labeling_sorted_dispatch(const Image<I>& input, const Neighborhood<N>& nbh, F& functor, L& nlabels) { enum { @@ -349,10 +505,11 @@ && mln_is_simple_neighborhood(N)::value }; - return impl::generic::labeling(metal::bool_<test>(), input, nbh, + return impl::generic::labeling_video(metal::bool_<test>(), input, nbh, functor, nlabels); } + } // end of namespace mln::canvas::internal @@ -362,20 +519,36 @@ template <typename I, typename N, typename F, typename L> inline mln_ch_value(I, L) - labeling(const Image<I>& input, const Neighborhood<N>& nbh, + labeling_video(const Image<I>& input, const Neighborhood<N>& nbh, F& functor, L& nlabels) { - trace::entering("canvas::labeling"); + trace::entering("canvas::labeling_video"); internal::labeling_tests(input, nbh, functor, nlabels); mln_ch_value(I, L) output; output = internal::labeling_dispatch(input, nbh, functor, nlabels); - trace::exiting("canvas::labeling"); + trace::exiting("canvas::labeling_video"); return output; } + template <typename I, typename N, typename F, typename L> + inline + mln_ch_value(I, L) + labeling_sorted(const Image<I>& input, const Neighborhood<N>& nbh, + F& functor, L& nlabels) + { + trace::entering("canvas::labeling_sorted"); + + internal::labeling_tests(input, nbh, functor, nlabels); + + mln_ch_value(I, L) output; + output = internal::labeling_dispatch(input, nbh, functor, nlabels); + + trace::exiting("canvas::labeling_sorted"); + return output; + } # endif // ! MLN_INCLUDE_ONLY