[Olena-patches] 4381: Add blobs_and_compute.

* mln/canvas/labeling/blobs.hh: New. Make labeling blobs a canvas. * mln/labeling/blobs.hh: Use the brand new canvas. * mln/labeling/blobs_and_compute.hh: New routine. --- milena/ChangeLog | 13 ++ milena/mln/canvas/labeling/blobs.hh | 179 ++++++++++++++++++++++++++++ milena/mln/labeling/blobs.hh | 88 ++++---------- milena/mln/labeling/blobs_and_compute.hh | 169 ++++++++++++++++++++++++++ milena/tests/labeling/Makefile.am | 2 + milena/tests/labeling/blobs_and_compute.cc | 56 +++++++++ 6 files changed, 441 insertions(+), 66 deletions(-) create mode 100644 milena/mln/canvas/labeling/blobs.hh create mode 100644 milena/mln/labeling/blobs_and_compute.hh create mode 100644 milena/tests/labeling/blobs_and_compute.cc diff --git a/milena/ChangeLog b/milena/ChangeLog index 896aad1..31f5d3d 100644 --- a/milena/ChangeLog +++ b/milena/ChangeLog @@ -1,5 +1,18 @@ 2009-08-21 Guillaume Lazzara &lt;lazzara(a)lrde.epita.fr&gt; + Add blobs_and_compute. + + * mln/canvas/labeling/blobs.hh: New. Make labeling blobs a canvas. + + * mln/labeling/blobs.hh: Use the brand new canvas. + + * mln/labeling/blobs_and_compute.hh: New routine. + + * milena/tests/labeling/Makefile.am, + * milena/tests/labeling/blobs_and_compute.cc: New test. + +2009-08-21 Guillaume Lazzara &lt;lazzara(a)lrde.epita.fr&gt; + Split canvas/labeling.hh into separate files. * mln/canvas/labeling/all.hh, diff --git a/milena/mln/canvas/labeling/blobs.hh b/milena/mln/canvas/labeling/blobs.hh new file mode 100644 index 0000000..8f85541 --- /dev/null +++ b/milena/mln/canvas/labeling/blobs.hh @@ -0,0 +1,179 @@ +// Copyright (C) 2009 EPITA Research and Development Laboratory (LRDE) +// +// This file is part of Olena. +// +// Olena is free software: you can redistribute it and/or modify it under +// the terms of the GNU General Public License as published by the Free +// Software Foundation, version 2 of the License. +// +// Olena 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 Olena. If not, see <http://www.gnu.org/licenses/>. +// +// As a special exception, you may use this file as part of a free +// software project 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_CANVAS_LABELING_BLOBS_HH +# define MLN_CANVAS_LABELING_BLOBS_HH + +/// \file +/// +/// Canvas for connected component labeling of the binary objects of a +/// binary image using a queue-based algorithm. + + +# include <mln/util/pix.hh> + +namespace mln +{ + + namespace canvas + { + + namespace labeling + { + + /*! \brief Canvas for connected component labeling of the binary + objects of a binary image using a queue-based algorithm. + + \param[in] input The input image. + \param[in] nbh The connexity of the objects. + \param[out] nlabels The Number of labels. Its value is set in + the algorithms. + \param[in,out] functor A functor computing data while labeling. + + \return The label image. + + \pre The input image has to be binary (checked at compile-time). + + A fast queue is used so that the algorithm is not recursive and + can handle large binary objects (blobs). + */ + template <typename I, typename N, typename L, typename F> + mln_ch_value(I, L) + blobs(const Image<I>& input_, const Neighborhood<N>& nbh_, + L& nlabels, F& functor); + + + +# ifndef MLN_INCLUDE_ONLY + + + // Implementations. + + namespace impl + { + + // Generic implementation. + + namespace generic + { + + template <typename I, typename N, typename L, typename F> + mln_ch_value(I, L) + blobs(const I& input, const N& nbh, L& nlabels, F& functor) + { + typedef mln_psite(I) P; + + P cur; + mln_niter(N) n(nbh, cur); + p_queue_fast<P> qu; + const L zero = literal::zero; + + // Initialization. + nlabels = literal::zero; + typedef mln_ch_value(I, L) out_t; + out_t output; + initialize(output, input); + data::fill(output, zero); + functor.init(); // <-- functor.init() + + // Loop. + mln_piter(I) p(input.domain()); + for_all(p) + if (input(p) && output(p) == zero) // Object point, not labeled yet. + { + // Label this point component. + if (nlabels == mln_max(L)) + { + trace::warning("labeling aborted! Too many labels \ +for this label type: nlabels > max(label_type)."); + + return output; + } + ++nlabels; + functor.new_label(nlabels); // <-- functor.new_label() + mln_invariant(qu.is_empty()); + qu.push(p); + output(p) = nlabels; + functor.process_p(util::pix<out_t>(output, p)); // <-- functor.process_p() + do + { + cur = qu.front(); + qu.pop(); + for_all(n) if (input.has(n)) + if (input(n) && output(n) == zero) + { + mln_invariant(! qu.compute_has(n)); + qu.push(n); + output(n) = nlabels; + functor.process_n(util::pix<out_t>(output, n)); // <-- functor.process_n() + } + } + while (! qu.is_empty()); + } + + functor.finalize(); // <-- functor.finalize() + return output; + } + + } // end of namespace mln::labeling::impl::generic + + } // end of namespace mln::labeling::impl + + + + // Facade. + + template <typename I, typename N, typename L, typename F> + inline + mln_ch_value(I, L) + blobs(const Image<I>& input_, const Neighborhood<N>& nbh_, + L& nlabels, F& functor) + { + trace::entering("labeling::blobs"); + mlc_equal(mln_trait_image_kind(I), + mln::trait::image::kind::binary)::check(); + const I& input = exact(input_); + const N& nbh = exact(nbh_); + mln_precondition(input.is_valid()); + + // The only implementation is the generic one. + mln_ch_value(I, L) + output = impl::generic::blobs(input, nbh, nlabels, functor); + + trace::exiting("labeling::blobs"); + return output; + } + + +# endif // ! MLN_INCLUDE_ONLY + + } // end of namespace mln::canvas::labeling + + } // end of namespace mln::canvas + +} // end of namespace mln + + +#endif // ! MLN_CANVAS_LABELING_BLOBS_HH diff --git a/milena/mln/labeling/blobs.hh b/milena/mln/labeling/blobs.hh index bfb7b4c..f63430f 100644 --- a/milena/mln/labeling/blobs.hh +++ b/milena/mln/labeling/blobs.hh @@ -41,6 +41,7 @@ # include <mln/data/fill.hh> # include <mln/core/site_set/p_queue_fast.hh> +# include <mln/canvas/labeling/blobs.hh> namespace mln @@ -71,76 +72,28 @@ namespace mln # ifndef MLN_INCLUDE_ONLY - namespace impl + + namespace internal { - namespace generic + /// Functor not computing anything. To be passed to the labeling + /// blobs canvas. + template <typename L> + struct dummy_functor { + void init() {} - template <typename I, typename N, typename L> - mln_ch_value(I, L) - blobs_(const I& input, const N& nbh, L& nlabels) - { - typedef mln_psite(I) P; - - P cur; - mln_niter(N) n(nbh, cur); - p_queue_fast<P> qu; - const L zero = literal::zero; - - // Initialization. - nlabels = literal::zero; - mln_ch_value(I, L) output; - initialize(output, input); - data::fill(output, zero); - - // Loop. - mln_piter(I) p(input.domain()); - for_all(p) - if (input(p) && output(p) == zero) // Object point, not labeled yet. - { - // Label this point component. - if (nlabels == mln_max(L)) - { - trace::warning("labeling aborted! Too many labels \ -for this label type: nlabels > max(label_type)."); - - return output; - } - ++nlabels; - mln_invariant(qu.is_empty()); - qu.push(p); - output(p) = nlabels; - do - { - cur = qu.front(); - qu.pop(); - for_all(n) if (input.has(n)) - if (input(n) && output(n) == zero) - { - mln_invariant(! qu.compute_has(n)); - qu.push(n); - output(n) = nlabels; - } - } - while (! qu.is_empty()); - } - - return output; - } - - } // end of namespace mln::labeling::impl::generic - - - template <typename I, typename N, typename L> - mln_ch_value(I, L) - blobs_(const I& input, const N& nbh, L& nlabels) - { - // The only implementation is the generic one. - return generic::blobs_(input, nbh, nlabels); - } + void new_label(const mln_value(L)&) {} + + void process_p(const util::pix<L>&) {} + + void process_n(const util::pix<L>&) {} + + void finalize() {} + }; + + } // end of namespace mln::labeling::internal - } // end of namespace mln::labeling::impl // Facade. @@ -158,7 +111,10 @@ for this label type: nlabels > max(label_type)."); const N& nbh = exact(nbh_); mln_precondition(input.is_valid()); - mln_ch_value(I, L) output = impl::blobs_(input, nbh, nlabels); + typedef mln_ch_value(I,L) out_t; + internal::dummy_functor<out_t> functor; + out_t + output = canvas::labeling::blobs(input, nbh, nlabels, functor); trace::exiting("labeling::blobs"); return output; diff --git a/milena/mln/labeling/blobs_and_compute.hh b/milena/mln/labeling/blobs_and_compute.hh new file mode 100644 index 0000000..4d5d5d8 --- /dev/null +++ b/milena/mln/labeling/blobs_and_compute.hh @@ -0,0 +1,169 @@ +// Copyright (C) 2009 EPITA Research and Development Laboratory (LRDE) +// +// This file is part of Olena. +// +// Olena is free software: you can redistribute it and/or modify it under +// the terms of the GNU General Public License as published by the Free +// Software Foundation, version 2 of the License. +// +// Olena 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 Olena. If not, see <http://www.gnu.org/licenses/>. +// +// As a special exception, you may use this file as part of a free +// software project 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_BLOBS_AND_COMPUTE_HH +# define MLN_LABELING_BLOBS_AND_COMPUTE_HH + +/// \file +/// +/// Label an image and compute given accumulators. + + +# include <mln/core/concept/image.hh> +# include <mln/core/concept/neighborhood.hh> + +# include <mln/labeling/blobs.hh> +# include <mln/labeling/compute.hh> + + +namespace mln +{ + + namespace labeling + { + + /*! Label an image and compute given accumulators. + + \param[in] input A binary image. + \param[in] nbh A neighborhood used for labeling. + \param[in,out] nlabels The number of labels found. + \param[in] accu An accumulator to be computed while labeling. + + */ + template <typename I, typename N, typename L, typename A> + util::couple<mln_ch_value(I, L), util::array<mln_result(A)> > + blobs_and_compute(const Image<I>& input, const Neighborhood<N>& nbh, + L& nlabels, const Accumulator<A>& accu); + + + +# ifndef MLN_INCLUDE_ONLY + + + namespace internal + { + + /// Functor not computing anything. To be passed to the labeling + /// blobs canvas. + template <typename L, typename A> + struct compute_functor + { + typedef mln_result(A) accu_result; + typedef mln_argument(A) accu_argument; + typedef util::array<accu_result> result; + + void init() + { + // FIXME: arbitrary value... + accus_.reserve(static_cast<unsigned>(mln_max(mln_value(L))) / 2); + accus_.append(A()); + } + + void new_label(const mln_value(L)& l) + { + current_lbl_ = l; + accus_.append(A()); + } + + void process_p(const util::pix<L>& pix) + { + process_(accu_argument(), pix); + } + + void process_n(const util::pix<L>& pix) + { + process_(accu_argument(), pix); + } + + void finalize() + { + convert::from_to(accus_, result_); + } + + + private: + void process_(const mln_psite(L)&, const util::pix<L>& pix) + { + accus_[current_lbl_].take(pix.p()); + } + + void process_(const mln_value(L)&, const util::pix<L>& pix) + { + accus_[current_lbl_].take(pix.v()); + } + + void process_(const util::pix<L>&, const util::pix<L>& pix) + { + accus_[current_lbl_].take(pix); + } + + public: + util::array<mln_result(A)> result_; + util::array<A> accus_; + mln_value(L) current_lbl_; + }; + + } // end of namespace mln::labeling::internal + + + + // Facade. + + + template <typename I, typename N, typename L, typename A> + util::couple<mln_ch_value(I,L), util::array<mln_result(A)> > + blobs_and_compute(const Image<I>& input, const Neighborhood<N>& nbh, + L& nlabels, const Accumulator<A>& accu) + { + trace::entering("labeling::blobs_and_compute"); + + (void) accu; + mlc_equal(mln_trait_image_kind(I), + mln::trait::image::kind::binary)::check(); + mln_precondition(exact(input).is_valid()); + + typedef mln_ch_value(I,L) out_t; + typedef internal::compute_functor<out_t,A> func_t; + func_t functor; + out_t + output = canvas::labeling::blobs(input, nbh, nlabels, functor); + + util::couple<out_t, typename func_t::result> + result = make::couple(output, functor.result_); + + trace::exiting("labeling::blobs_and_compute"); + return result; + } + + +# endif // ! MLN_INCLUDE_ONLY + + + } // end of namespace mln::labeling + +} // end of namespace mln + + +#endif // ! MLN_LABELING_BLOBS_AND_COMPUTE_HH diff --git a/milena/tests/labeling/Makefile.am b/milena/tests/labeling/Makefile.am index 8ec17c4..1509d72 100644 --- a/milena/tests/labeling/Makefile.am +++ b/milena/tests/labeling/Makefile.am @@ -22,6 +22,7 @@ include $(top_srcdir)/milena/tests/tests.mk check_PROGRAMS = \ background \ blobs \ + blobs_and_compute \ colorize \ compute \ fill_holes \ @@ -38,6 +39,7 @@ check_PROGRAMS = \ background_SOURCES = background.cc blobs_SOURCES = blobs.cc +blobs_and_compute_SOURCES = blobs_and_compute.cc colorize_SOURCES = colorize.cc compute_SOURCES = compute.cc fill_holes_SOURCES = fill_holes.cc diff --git a/milena/tests/labeling/blobs_and_compute.cc b/milena/tests/labeling/blobs_and_compute.cc new file mode 100644 index 0000000..8516bba --- /dev/null +++ b/milena/tests/labeling/blobs_and_compute.cc @@ -0,0 +1,56 @@ +// Copyright (C) 2009 EPITA Research and Development Laboratory (LRDE) +// +// This file is part of Olena. +// +// Olena is free software: you can redistribute it and/or modify it under +// the terms of the GNU General Public License as published by the Free +// Software Foundation, version 2 of the License. +// +// Olena 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 Olena. If not, see <http://www.gnu.org/licenses/>. +// +// As a special exception, you may use this file as part of a free +// software project 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. + +#include <mln/core/image/image2d.hh> +#include <mln/io/pbm/load.hh> +#include <mln/core/alias/neighb2d.hh> +#include <mln/accu/center.hh> +#include <mln/labeling/blobs_and_compute.hh> +#include <mln/util/array.hh> +#include <mln/util/couple.hh> +#include <mln/value/label_8.hh> + +#include "tests/data.hh" + + +int main() +{ + using namespace mln; + + image2d<bool> pic = io::pbm::load(MLN_IMG_DIR "/picasso.pbm"); + value::label_8 n; + + + typedef image2d<value::label_8> L; + typedef util::array<point2d> arr_t; + typedef util::couple<L,arr_t> res_t; + res_t result = labeling::blobs_and_compute(pic, c4(), n, + accu::center<point2d,point2d>()); + + mln_assertion(result.second().size() == 34); + mln_assertion(result.second()[1] == point2d(10,30)); + mln_assertion(result.second()[33] == point2d(310,66)); + mln_assertion(n == 33); +} -- 1.5.6.5