[Olena-patches] 1068: Add labeling routines.

https://svn.lrde.epita.fr/svn/oln/trunk/milena Index: ChangeLog from Thierry Geraud &lt;thierry.geraud(a)lrde.epita.fr&gt; Add labeling routines. * tests/sort_points.cc: Rename as... * tests/level_sort_points.cc: ...this. Augment. * tests/labeling.cc: Rename as... * tests/labeling_foreground.cc: ...this. Update. * tests/labeling_regional_maxima.cc: New. * mln/convert/to_vec_p.hh: New. * mln/pw/image.hh (change_value): Use fixme. * mln/core/vec_p.hh (reserve, hook_): New. * mln/core/vec_p_piter.hh (vec_p_bkd_piter_): Code. * mln/level/sort_points.hh (sort_points): Rename as... (sort_points_increasing): ...this. (sort_points_decreasing): New. * mln/level/fill.hh: Add & to the C function arg; that fixes the behavior of icpc when calling fill with the literal 0. * mln/level/labeling.hh: Remove; obsolete because of labeling::level. * mln/linear/sobel.hh: Add FIXME. * mln/canvas/labeling.hh: New. * mln/labeling/flat_zones.hh: New. * mln/labeling/+foreground.hh: Remove. * mln/labeling/level.hh: New. * mln/labeling/foreground.hh: New. * mln/labeling/regional_minima.hh: New. * mln/labeling/base.hh: New. * mln/labeling/regional_maxima.hh: New. * mln/labeling/background.hh: New. mln/canvas/labeling.hh | 157 ++++++++++++++++++++++++++++++++++++++ mln/convert/to_vec_p.hh | 71 +++++++++++++++++ mln/core/vec_p.hh | 20 ++++ mln/core/vec_p_piter.hh | 121 ++++++++++++++++++++++++++++- mln/labeling/background.hh | 79 +++++++++++++++++++ mln/labeling/base.hh | 94 ++++++++++++++++++++++ mln/labeling/flat_zones.hh | 111 ++++++++++++++++++++++++++ mln/labeling/foreground.hh | 79 +++++++++++++++++++ mln/labeling/level.hh | 118 ++++++++++++++++++++++++++++ mln/labeling/regional_maxima.hh | 120 +++++++++++++++++++++++++++++ mln/labeling/regional_minima.hh | 120 +++++++++++++++++++++++++++++ mln/level/fill.hh | 5 - mln/level/sort_points.hh | 110 ++++++++++++++++++++------ mln/linear/sobel.hh | 2 mln/pw/image.hh | 2 tests/labeling_foreground.cc | 45 ++-------- tests/labeling_regional_maxima.cc | 57 +++++++++++++ tests/level_sort_points.cc | 15 ++- 18 files changed, 1254 insertions(+), 72 deletions(-) Index: tests/level_sort_points.cc --- tests/level_sort_points.cc (revision 1067) +++ tests/level_sort_points.cc (working copy) @@ -47,10 +47,13 @@ image2d_b<int_u8> ima(3, 3); debug::iota(ima); - std::vector<point2d> vec = level::sort_points(ima); - - std::copy(vec.begin(), vec.end(), - std::ostream_iterator<point2d>(std::cout, " ")); - std::cout << std::endl; - + vec_p<point2d> vec; + { + vec = level::sort_points_increasing(ima); + std::cout << vec << std::endl; + } + { + vec = level::sort_points_decreasing(ima); + std::cout << vec << std::endl; + } } Index: tests/labeling_foreground.cc --- tests/labeling_foreground.cc (revision 1067) +++ tests/labeling_foreground.cc (working copy) @@ -25,54 +25,33 @@ // reasons why the executable file might be covered by the GNU General // Public License. -/*! \file tests/labeling.cc +/*! \file tests/labeling_foreground.cc * - * \brief Tests on mln::level::labeling. + * \brief Test on mln::labeling::foreground. */ #include <mln/core/image2d_b.hh> #include <mln/core/neighb2d.hh> - #include <mln/value/int_u8.hh> -#include <mln/value/label.hh> - -#include <mln/pw/value.hh> -#include <mln/pw/cst.hh> -#include <mln/fun/ops.hh> +#include <mln/pw/all.hh> #include <mln/io/load_pgm.hh> #include <mln/io/save_pgm.hh> - -#include <mln/level/fill.hh> -#include <mln/level/labeling.hh> -#include <mln/level/to_enc.hh> - +#include <mln/labeling/foreground.hh> int main() { using namespace mln; using value::int_u8; - using value::label; - image2d_b<int_u8> lena = io::load_pgm("../img/lena.pgm"); - - image2d_b<bool> bin(lena.domain()); - level::fill(bin, pw::value(lena) > pw::cst(127)); - - { - image2d_b<int_u8> lab(lena.domain()); - level::labeling(bin, c4(), lab); - io::save_pgm(lab, "lab.pgm"); - } - - { - image2d_b< label<8> > lab(lena.domain()); - level::labeling(bin, c4(), lab); - - image2d_b< int_u8 > out(lena.domain()); - level::to_enc(lab, out); + image2d_b<int_u8> + lena = io::load_pgm("../img/tiny.pgm"), + out(lena.domain()); + + unsigned n; + labeling::foreground((pw::value(lena) > pw::cst(127)) | lena.domain(), + c4(), out, n); io::save_pgm(out, "out.pgm"); - } - + mln_assertion(n = 14); } Index: tests/labeling_regional_maxima.cc --- tests/labeling_regional_maxima.cc (revision 0) +++ tests/labeling_regional_maxima.cc (revision 0) @@ -0,0 +1,57 @@ +// Copyright (C) 2007 EPITA Research and Development Laboratory +// +// 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_regional_maxima.cc + * + * \brief Test on mln::labeling::regional_maxima. + */ + +#include <mln/core/image2d_b.hh> +#include <mln/core/neighb2d.hh> +#include <mln/value/int_u8.hh> + +#include <mln/io/load_pgm.hh> +#include <mln/io/save_pgm.hh> + +#include <mln/labeling/regional_maxima.hh> + + +int main() +{ + using namespace mln; + using value::int_u8; + + image2d_b<int_u8> + lena = io::load_pgm("../img/lena.pgm"), + out(lena.domain()); + + unsigned n; + labeling::regional_maxima(lena, c4(), out, n); + mln_assertion(n = 255); + + io::save_pgm(out, "out.pgm"); +} Index: mln/convert/to_vec_p.hh --- mln/convert/to_vec_p.hh (revision 0) +++ mln/convert/to_vec_p.hh (revision 0) @@ -0,0 +1,71 @@ +// Copyright (C) 2007 EPITA Research and Development Laboratory +// +// 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_CONVERT_TO_VEC_P_HH +# define MLN_CONVERT_TO_VEC_P_HH + +/*! \file mln/convert/to_vec_p.hh + * + * \brief Conversions to mln::vec_p. + */ + +# include <mln/core/vec_p.hh> + + +namespace mln +{ + + namespace convert + { + + /// Convert a point set \p pset into a vec_p (point set vector). + template <typename S> + vec_p<mln_point(S)> to_vec_p(const Point_Set<S>& pset); + + +# ifndef MLN_INCLUDE_ONLY + + template <typename S> + vec_p<mln_point(S)> to_vec_p(const Point_Set<S>& pset_) + { + const S& pset = exact(pset_); + vec_p<mln_point(S)> v; + v.reserve(pset.npoints()); + mln_fwd_piter(S) p(pset); + for_all(p) + v.append(p); + return v; + } + +# endif // ! MLN_INCLUDE_ONLY + + } // end of namespace mln::convert + +} // end of namespace mln + + +#endif // ! MLN_CONVERT_TO_VEC_P_HH Index: mln/pw/image.hh --- mln/pw/image.hh (revision 1067) +++ mln/pw/image.hh (working copy) @@ -109,7 +109,7 @@ template <typename U> struct change_value { - typedef void ret; + typedef internal::fixme ret; }; protected: Index: mln/core/vec_p.hh --- mln/core/vec_p.hh (revision 1067) +++ mln/core/vec_p.hh (working copy) @@ -79,6 +79,9 @@ /// Constructor from a vector \p vect. vec_p(const std::vector<P>& vect); + /// Reserve \p n cells. + void reserve(std::size_t n); + /// Test is \p p belongs to this point set. bool has(const P& p) const; @@ -100,6 +103,9 @@ /// Return the \p i-th point. const P& operator[](unsigned i) const; + /// Hook to data. + std::vector<P>& hook_(); + protected: std::vector<P> vect_; @@ -129,6 +135,20 @@ template <typename P> void + vec_p<P>::reserve(std::size_t n) + { + vect_.reserve(n); + } + + template <typename P> + std::vector<P>& + vec_p<P>::hook_() + { + return vect_; + } + + template <typename P> + void vec_p<P>::update_bb_() const { bb_.init(); Index: mln/core/vec_p_piter.hh --- mln/core/vec_p_piter.hh (revision 1067) +++ mln/core/vec_p_piter.hh (working copy) @@ -92,15 +92,63 @@ - // FIXME: + /*! \brief Backward iterator on points of a vec_p<P>. + * + */ template <typename P> - struct vec_p_bkd_piter_ : internal::fixme - {}; + struct vec_p_bkd_piter_ : public Point_Iterator< vec_p_bkd_piter_<P> > + { + enum { dim = P::dim }; + + /// Point_Site associated type. + typedef P psite; + + /// Point associated type. + typedef P point; + + /// Dpoint associated type. + typedef mln_dpoint(P) dpoint; + + /// Coordinate associated type. + typedef mln_coord(P) coord; + + /// Coordinate associated type. + template <typename S> + vec_p_bkd_piter_(const Point_Set<S>& s); + + /// Give a hook to the point address. + const P* pointer_() const; + + /// Read-only access to the \p i-th coordinate. + coord operator[](unsigned i) const; + + /// Test if the iterator is valid. + bool is_valid() const; + + /// Invalidate the iterator. + void invalidate(); + + /// Start an iteration. + void start(); + + /// Go to the next point. + void next_(); + + /// Convert the iterator into a point. + operator P() const; + + protected: + const std::vector<P>& vect_; + int i_; + P p_; + }; # ifndef MLN_INCLUDE_ONLY + // vec_p_fwd_piter_<P> + template <typename P> template <typename S> vec_p_fwd_piter_<P>::vec_p_fwd_piter_(const Point_Set<S>& s) @@ -153,6 +201,7 @@ vec_p_fwd_piter_<P>::next_() { ++i_; + if (is_valid()) p_ = vect_[i_]; } @@ -163,6 +212,72 @@ return p_; } + + // vec_p_bkd_piter_<P> + + template <typename P> + template <typename S> + vec_p_bkd_piter_<P>::vec_p_bkd_piter_(const Point_Set<S>& s) + : vect_(exact(s).vect()) + { + invalidate(); + } + + template <typename P> + const P* + vec_p_bkd_piter_<P>::pointer_() const + { + return & p_; + } + + template <typename P> + mln_coord(P) + vec_p_bkd_piter_<P>::operator[](unsigned i) const + { + mln_precondition(i < dim); + mln_precondition(is_valid()); + return p_[i]; + } + + template <typename P> + bool + vec_p_bkd_piter_<P>::is_valid() const + { + return i_ >= 0; + } + + template <typename P> + void + vec_p_bkd_piter_<P>::invalidate() + { + i_ = -1; + } + + template <typename P> + void + vec_p_bkd_piter_<P>::start() + { + i_ = vect_.size() - 1; + if (is_valid()) + p_ = vect_[i_]; + } + + template <typename P> + void + vec_p_bkd_piter_<P>::next_() + { + --i_; + if (is_valid()) + p_ = vect_[i_]; + } + + template <typename P> + vec_p_bkd_piter_<P>::operator P() const + { + mln_precondition(is_valid()); + return p_; + } + # endif // ! MLN_INCLUDE_ONLY } // end of namespace mln Index: mln/level/sort_points.hh --- mln/level/sort_points.hh (revision 1067) +++ mln/level/sort_points.hh (working copy) @@ -31,13 +31,14 @@ /*! \file mln/level/sort_points.hh * * \brief Sort_Points the contents of an image into another one. + * + * \todo Factor code + optimize. */ -# include <vector> -# include <utility> # include <algorithm> # include <mln/core/concept/image.hh> +# include <mln/convert/to_vec_p.hh> # include <mln/histo/compute.hh> @@ -55,7 +56,7 @@ * \pre \p input.has_data */ template <typename I> - std::vector<mln_point(I)> sort_points(const Image<I>& input); + vec_p<mln_point(I)> sort_points_increasing(const Image<I>& input); # ifndef MLN_INCLUDE_ONLY @@ -63,6 +64,8 @@ namespace impl { + // utility + template <typename I> struct value_point_less_ { @@ -82,31 +85,40 @@ }; template <typename I> - std::vector<mln_point(I)> - sort_points(metal::false_, // general case - const Image<I>& input_) + struct value_point_greater_ { - const I& input = exact(input_); + const I& ima_; - std::vector<mln_point(I)> vec; - vec.reserve(input.npoints()); + value_point_greater_(const I& ima) + : ima_(ima) + { + } - mln_fwd_piter(I) p(input.domain()); - for_all(p) - vec.push_back(p); + bool operator()(const mln_point(I)& lhs, + const mln_point(I)& rhs) const + { + return ima_(lhs) > ima_(rhs) || (ima_(lhs) = ima_(rhs) + && lhs > rhs); + } + }; - std::sort(vec.begin(), vec.end(), + + // increasing + + template <typename I> + vec_p<mln_point(I)> + sort_points_increasing_(metal::false_, const I& input) // general case + { + vec_p<mln_point(I)> v = convert::to_vec_p(input.domain()); + std::sort(v.hook_().begin(), v.hook_().end(), value_point_less_<I>(input)); - return vec; + return v; } template <typename I> - std::vector<mln_point(I)> - sort_points(metal::true_, // low quantization - const Image<I>& input_) + vec_p<mln_point(I)> + sort_points_increasing_(metal::true_, const I& input) // low quantization { - const I& input = exact(input_); - typedef mln_vset(I) S; const S& vset = input.values(); const unsigned n = vset.nvalues(); @@ -120,12 +132,46 @@ for (unsigned i = 1; i != n; ++i) loc[i] = loc[i-1] + h[i-1]; - /* - MEMO. Decreasing case is: + // computing output data + std::vector<mln_point(I)> vec(input.npoints()); + mln_fwd_piter(I) p(input.domain()); + for_all(p) + vec[loc[vset.index_of(input(p))]++] = p; + + vec_p<mln_point(I)> v; + v.hook_() = vec; + return v; + } + + + // decreasing + + template <typename I> + vec_p<mln_point(I)> + sort_points_decreasing_(metal::false_, const I& input) // general case + { + vec_p<mln_point(I)> v = convert::to_vec_p(input.domain()); + std::sort(v.hook_().begin(), v.hook_().end(), + value_point_greater_<I>(input)); + return v; + } + + template <typename I> + vec_p<mln_point(I)> + sort_points_decreasing_(metal::true_, const I& input) // low quantization + { + typedef mln_vset(I) S; + const S& vset = input.values(); + const unsigned n = vset.nvalues(); + + // h + histo::data<S> h = histo::compute(input); + + // preparing output data + std::vector<unsigned> loc(vset.nvalues()); loc[n-1] = 0; for (unsigned i = n - 2; i != 0; --i) loc[i] = loc[i+1] + h[i+1]; - */ // computing output data std::vector<mln_point(I)> vec(input.npoints()); @@ -133,20 +179,32 @@ for_all(p) vec[loc[vset.index_of(input(p))]++] = p; - return vec; + vec_p<mln_point(I)> v; + v.hook_() = vec; + return v; } + } // end of namespace mln::level::impl + // Facades. + template <typename I> - std::vector<mln_point(I)> - sort_points(const Image<I>& input) + vec_p<mln_point(I)> + sort_points_increasing(const Image<I>& input) { mln_precondition(exact(input).has_data()); - return impl::sort_points(mln_is_value_lowq(I)(), exact(input)); + return impl::sort_points_increasing_(mln_is_value_lowq(I)(), exact(input)); } + template <typename I> + vec_p<mln_point(I)> + sort_points_decreasing(const Image<I>& input) + { + mln_precondition(exact(input).has_data()); + return impl::sort_points_decreasing_(mln_is_value_lowq(I)(), exact(input)); + } # endif // ! MLN_INCLUDE_ONLY Index: mln/level/fill.hh --- mln/level/fill.hh (revision 1067) +++ mln/level/fill.hh (working copy) @@ -86,7 +86,7 @@ * \todo Take benefit from quantization when possible. */ template <typename I> - void fill(Image<I>& ima, mln_value(I) (*f)(const mln_point(I)& p)); + void fill(Image<I>& ima, mln_value(I) (*(&f))(const mln_point(I)& p)); /*! Fill the image \p ima with the values given by the array \p arr. @@ -191,8 +191,9 @@ template <typename I> void fill(Image<I>& ima_, - mln_value(I) (*f)(const mln_point(I)& p)) + mln_value(I) (*(&f))(const mln_point(I)& p)) { + mln_precondition(f != 0); I& ima = exact(ima_); mln_precondition(ima.has_data()); mln_piter(I) p(ima.domain()); Index: mln/linear/sobel.hh --- mln/linear/sobel.hh (revision 1067) +++ mln/linear/sobel.hh (working copy) @@ -102,7 +102,7 @@ O temp(exact(input).domain()); sobel_v(input, temp); // output - arith::plus_inplace(output, temp); + arith::plus_inplace(output, temp); // FIXME: abs before plus!!! level::abs_inplace(output); } Index: mln/canvas/labeling.hh --- mln/canvas/labeling.hh (revision 0) +++ mln/canvas/labeling.hh (revision 0) @@ -0,0 +1,157 @@ +// Copyright (C) 2007 EPITA Research and Development Laboratory +// +// 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_CANVAS_LABELING_HH +# define MLN_CANVAS_LABELING_HH + +/*! \file mln/canvas/labeling.hh + * + * \brief Connected component labeling of the object part in a binary + * image. + */ + +# include <mln/level/fill.hh> +# include <mln/level/sort_points.hh> + + +namespace mln +{ + + namespace canvas + { + + template <typename F> + struct labeling + { + F& f; + + typedef typename F::I I; + typedef typename F::N N; + typedef typename F::O O; + typedef typename F::S S; + typedef mln_point(I) point; + + // aux: + mln_ch_value(O, bool) deja_vu; + mln_ch_value(O, point) parent; + + labeling(F& f) + : f(f), + deja_vu(f.output.domain()), + parent(f.output.domain()) + { + run(); + } + + void run() + { + // init + { + f.nlabels = 0; + mln::level::fill(deja_vu, false); + f.init(); + } + // first pass + { + mln_fwd_piter(S) p(f.s); + mln_niter(N) n(f.nbh, p); + for_all(p) if (f.handles(p)) + { + make_set(p); + for_all(n) + if (f.input.has(n) && deja_vu(n)) + if (f.equiv(n, p)) + do_union(n, p); + else + f.do_no_union(n, p); + deja_vu(p) = true; + } + } + + // second pass + { + mln_bkd_piter(S) p(f.s); + mln_niter(N) n(f.nbh, p); + for_all(p) if (f.handles(p)) + { + if (is_root(p)) + { + if (f.labels(p)) + { + if (f.nlabels = mln_max(mln_value(O))) + { + f.status = false; + return; + } + f.output(p) = ++f.nlabels; + } + } + else + f.output(p) = f.output(parent(p)); + } + f.status = true; + } + + } // end of run() + + void make_set(const point& p) + { + parent(p) = p; + f.init_attr(p); + } + + bool is_root(const point& p) const + { + return parent(p) = p; + } + + point find_root(const point& x) + { + if (parent(x) = x) + return x; + else + return parent(x) = find_root(parent(x)); + } + + void do_union(const point& n, const point& p) + { + point r = find_root(n); + if (r != p) + { + parent(r) = p; + f.merge_attr(r, p); + } + } + + }; + + } // end of namespace mln::canvas + +} // end of namespace mln + + +#endif // ! MLN_CANVAS_LABELING_HH Index: mln/labeling/flat_zones.hh --- mln/labeling/flat_zones.hh (revision 0) +++ mln/labeling/flat_zones.hh (revision 0) @@ -0,0 +1,111 @@ +// Copyright (C) 2007 EPITA Research and Development Laboratory +// +// 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 + * + * \brief Connected component labeling of the flat zones of an image. + */ + +# include <mln/labeling/base.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 neighborhood to consider. + * \param[out] output The label image. + * \param[out] nlabels The number of labels. + * + * \return The number of labels. + */ + template <typename I, typename N, typename O> + bool flat_zones(const Image<I>& input, const Neighborhood<N>& nbh, + Image<O>& output, + unsigned& nlabels); + + +# ifndef MLN_INCLUDE_ONLY + + namespace impl + { + + template <typename I_, typename N_, typename O_> + struct flat_zones_ : base_<I_,N_,O_> + { + typedef mln_point(I_) P; + + // requirements from mln::canvas::labeling: + + typedef mln_pset(I_) S; + const S& s; + mln_value(O) nlabels; + bool status; + + bool equiv(const P& n, const P&) const { return input(n) = input(p); } + + // end of requirements + + flat_zones_(const I_& input, const N_& nbh, O_& output) + : base_<I_,N_,O_>(input, nbh, output), + s(input.domain()) + {} + }; + + } // end of namespace mln::labeling::impl + + + // Facade. + + template <typename I, typename N, typename O> + bool flat_zones(const Image<I>& input, const Neighborhood<N>& nbh, + Image<O>& output, + unsigned& nlabels) + { + typedef impl::flat_zones_<I,N,O> F; + F f(exact(input), exact(nbh), exact(output)); + canvas::labeling<F> run(f); + nlabels = f.nlabels; + return f.status; + } + +# endif // ! MLN_INCLUDE_ONLY + + } // end of namespace mln::labeling + +} // end of namespace mln + + +#endif // ! MLN_LABELING_FLAT_ZONES_HH Index: mln/labeling/level.hh --- mln/labeling/level.hh (revision 0) +++ mln/labeling/level.hh (revision 0) @@ -0,0 +1,118 @@ +// Copyright (C) 2007 EPITA Research and Development Laboratory +// +// 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_LEVEL_HH +# define MLN_LABELING_LEVEL_HH + +/*! \file mln/labeling/level.hh + * + * \brief Connected component labeling of the image objects at a given + * level. + */ + +# include <mln/labeling/base.hh> +# include <mln/level/fill.hh> + + +namespace mln +{ + + namespace labeling + { + + /*! Connected component labeling of the image objects at a given + * level. + * + * \param[in] input The input image. + * \param[in] val The level to consider for the labeling. + * \param[in] nbh The neighborhood. + * \param[out] output The label image. + * \param[out] nlabels The number of labels. + * + * \return Succeed or not. + */ + template <typename I, typename N, typename O> + bool level(const Image<I>& input, const mln_value(I)& val, const Neighborhood<N>& nbh, + Image<O>& output, unsigned& nlabels); + + + +# ifndef MLN_INCLUDE_ONLY + + namespace impl + { + + template <typename I_, typename N_, typename O_> + struct level_ : base_<I_,N_,O_> + { + typedef mln_point(I_) P; + + // requirements from mln::canvas::labeling: + + typedef mln_pset(I_) S; + const S& s; + + void init() { mln::level::fill(this->output, 0); } + bool handles(const P& p) const { return input(p) = val; } + bool equiv(const P& n, const P&) const { return input(n) = val; } + + // end of requirements + + const mln_value(I_)& val; + + level_(const I_& input, const mln_value(I_)& val, const N_& nbh, O_& output) + : base_<I_,N_,O_>(input, nbh, output), + s(input.domain()), + val(val) + {} + }; + + } // end of namespace mln::labeling::impl + + + // Facade. + + template <typename I, typename N, typename O> + bool level(const Image<I>& input, const mln_value(I)& val, const Neighborhood<N>& nbh, + Image<O>& output, unsigned& nlabels) + { + mln_precondition(exact(output).domain() = exact(input).domain()); + typedef impl::level_<I,N,O> F; + F f(exact(input), val, exact(nbh), exact(output)); + canvas::labeling<F> run(f); + nlabels = f.nlabels; + return f.status; + } + +# endif // ! MLN_INCLUDE_ONLY + + } // end of namespace mln::labeling + +} // end of namespace mln + + +#endif // ! MLN_LABELING_LEVEL_HH Index: mln/labeling/foreground.hh --- mln/labeling/foreground.hh (revision 0) +++ mln/labeling/foreground.hh (revision 0) @@ -0,0 +1,79 @@ +// Copyright (C) 2007 EPITA Research and Development Laboratory +// +// 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_FOREGROUND_HH +# define MLN_LABELING_FOREGROUND_HH + +/*! \file mln/labeling/foreground.hh + * + * \brief Connected component labeling of the object part in a binary + * image. + */ + +# include <mln/labeling/level.hh> + + +namespace mln +{ + + namespace labeling + { + + /*! Connected component labeling of the object part in a binary + * image. + * + * \param[in] input The input image. + * \param[in] nbh The neighborhood to consider. + * \param[out] output The label image. + * \param[out] nlabels The number of labels. + * + * \return The number of labels. + */ + template <typename I, typename N, typename O> + bool foreground(const Image<I>& input, const Neighborhood<N>& nbh, + Image<O>& output, + unsigned& nlabels); + + +# ifndef MLN_INCLUDE_ONLY + + template <typename I, typename N, typename O> + bool foreground(const Image<I>& input, const Neighborhood<N>& nbh, + Image<O>& output, + unsigned& nlabels) + { + return labeling::level(input, true, nbh, output, nlabels); + } + +# endif // ! MLN_INCLUDE_ONLY + + } // end of namespace mln::labeling + +} // end of namespace mln + + +#endif // ! MLN_LABELING_FOREGROUND_HH Index: mln/labeling/regional_minima.hh --- mln/labeling/regional_minima.hh (revision 0) +++ mln/labeling/regional_minima.hh (revision 0) @@ -0,0 +1,120 @@ +// Copyright (C) 2007 EPITA Research and Development Laboratory +// +// 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_MINIMA_HH +# define MLN_LABELING_REGIONAL_MINIMA_HH + +/*! \file mln/labeling/regional_minima.hh + * + * \brief Connected component labeling of the regional minima of an + * image. + */ + +# include <mln/labeling/base.hh> +# include <mln/level/sort_points.hh> + + +namespace mln +{ + + namespace labeling + { + + /*! Connected component labeling of the regional minima of an + * image. + * + * \param[in] input The input image. + * \param[in] nbh The neighborhood to consider. + * \param[out] output The label image. + * + * \return The number of labels. + */ + template <typename I, typename N, typename O> + bool regional_minima(const Image<I>& input, const Neighborhood<N>& nbh, + Image<O>& output, unsigned& nlabels); + + + +# ifndef MLN_INCLUDE_ONLY + + namespace impl + { + + template <typename I_, typename N_, typename O_> + struct regional_minima_ : base_<I_,N_,O_> + { + typedef mln_point(I_) P; + + // requirements from mln::canvas::labeling: + + typedef vec_p<P> S; + S s; + + void init() { mln::level::fill(this->output, 0); + level::fill(attr, 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 merge_attr(const P& r, const P& p) { attr(p) = attr(p) && attr(r); } + + // end of requirements + + mln_ch_value(O_, bool) attr; + + regional_minima_(const I_& input, const N_& nbh, O_& output) + : base_<I_,N_,O_>(input, nbh, output), + s(level::sort_points_increasing(input)), + attr(output.domain()) + { + } + }; + + } // end of namespace mln::labeling::impl + + + // Facade. + + template <typename I, typename N, typename O> + bool regional_minima(const Image<I>& input, const Neighborhood<N>& nbh, + Image<O>& output, unsigned& nlabels) + { + typedef impl::regional_minima_<I,N,O> F; + F f(exact(input), exact(nbh), exact(output)); + canvas::labeling<F> run(f); + nlabels = f.nlabels; + return f.status; + } + +# endif // ! MLN_INCLUDE_ONLY + + } // end of namespace mln::labeling + +} // end of namespace mln + + +#endif // ! MLN_LABELING_REGIONAL_MINIMA_HH Index: mln/labeling/base.hh --- mln/labeling/base.hh (revision 0) +++ mln/labeling/base.hh (revision 0) @@ -0,0 +1,94 @@ +// Copyright (C) 2007 EPITA Research and Development Laboratory +// +// 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_BASE_HH +# define MLN_LABELING_BASE_HH + +/*! \file mln/labeling/base.hh + * + * \brief Base class for labeling functors. + */ + +# include <mln/core/concept/image.hh> +# include <mln/core/concept/neighborhood.hh> +# include <mln/canvas/labeling.hh> + + +namespace mln +{ + + namespace labeling + { + +# ifndef MLN_INCLUDE_ONLY + + namespace impl + { + + /// Base class for labeling functors. + template <typename I_, typename N_, typename O_> + struct base_ + { + typedef I_ I; + typedef N_ N; + typedef O_ O; + typedef mln_point(I_) P; + + const I& input; + const N& nbh; + O& output; + + mln_value(O_) nlabels; + bool status; + + base_(const I_& input, const N_& nbh, O_& output) + : input(input), + nbh(nbh), + output(output) + { + } + + // Defaults. + + bool handles(const P&) const { return true; } + bool labels(const P&) const { return true; } + void init() {} + void do_no_union(const P&, const P&) {} + void init_attr(const P&) {} + void merge_attr(const P&, const P&) {} + }; + + } // end of namespace mln::labeling::impl + +# endif // ! MLN_INCLUDE_ONLY + + } // end of namespace mln::labeling + +} // end of namespace mln + + +#endif // ! MLN_LABELING_BASE_HH Index: mln/labeling/regional_maxima.hh --- mln/labeling/regional_maxima.hh (revision 0) +++ mln/labeling/regional_maxima.hh (revision 0) @@ -0,0 +1,120 @@ +// Copyright (C) 2007 EPITA Research and Development Laboratory +// +// 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 + * + * \brief Connected component labeling of the regional maxima of an + * image. + */ + +# include <mln/labeling/base.hh> +# include <mln/level/sort_points.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 neighborhood to consider. + * \param[out] output The label image. + * + * \return The number of labels. + */ + template <typename I, typename N, typename O> + bool regional_maxima(const Image<I>& input, const Neighborhood<N>& nbh, + Image<O>& output, unsigned& nlabels); + + + +# ifndef MLN_INCLUDE_ONLY + + namespace impl + { + + template <typename I_, typename N_, typename O_> + struct regional_maxima_ : base_<I_,N_,O_> + { + typedef mln_point(I_) P; + + // requirements from mln::canvas::labeling: + + typedef vec_p<P> S; + S s; + + void init() { mln::level::fill(this->output, 0); + level::fill(attr, 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 merge_attr(const P& r, const P& p) { attr(p) = attr(p) && attr(r); } + + // end of requirements + + mln_ch_value(O_, bool) attr; + + regional_maxima_(const I_& input, const N_& nbh, O_& output) + : base_<I_,N_,O_>(input, nbh, output), + s(level::sort_points_decreasing(input)), + attr(output.domain()) + { + } + }; + + } // end of namespace mln::labeling::impl + + + // Facade. + + template <typename I, typename N, typename O> + bool regional_maxima(const Image<I>& input, const Neighborhood<N>& nbh, + Image<O>& output, unsigned& nlabels) + { + typedef impl::regional_maxima_<I,N,O> F; + F f(exact(input), exact(nbh), exact(output)); + canvas::labeling<F> run(f); + nlabels = f.nlabels; + return f.status; + } + +# endif // ! MLN_INCLUDE_ONLY + + } // end of namespace mln::labeling + +} // end of namespace mln + + +#endif // ! MLN_LABELING_REGIONAL_MAXIMA_HH Index: mln/labeling/background.hh --- mln/labeling/background.hh (revision 0) +++ mln/labeling/background.hh (revision 0) @@ -0,0 +1,79 @@ +// Copyright (C) 2007 EPITA Research and Development Laboratory +// +// 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_BACKGROUND_HH +# define MLN_LABELING_BACKGROUND_HH + +/*! \file mln/labeling/background.hh + * + * \brief Connected component labeling of the background in a binary + * image. + */ + +# include <mln/labeling/level.hh> + + +namespace mln +{ + + namespace labeling + { + + /*! Connected component labeling of the background in a binary + * image. + * + * \param[in] input The input image. + * \param[in] nbh The neighborhood to consider. + * \param[out] output The label image. + * \param[out] nlabels The number of labels. + * + * \return The number of labels. + */ + template <typename I, typename N, typename O> + bool background(const Image<I>& input, const Neighborhood<N>& nbh, + Image<O>& output, + unsigned& nlabels); + + +# ifndef MLN_INCLUDE_ONLY + + template <typename I, typename N, typename O> + bool background(const Image<I>& input, const Neighborhood<N>& nbh, + Image<O>& output, + unsigned& nlabels) + { + return labeling::level(input, false, nbh, output, nlabels); + } + +# endif // ! MLN_INCLUDE_ONLY + + } // end of namespace mln::labeling + +} // end of namespace mln + + +#endif // ! MLN_LABELING_BACKGROUND_HH