https://svn.lrde.epita.fr/svn/oln/trunk/milena Index: ChangeLog from Thierry Geraud <thierry.geraud@lrde.epita.fr> Prepare to fast the morpho wst by flooding. * mln/morpho/watershed: New directory. * mln/morpho/meyer_wst.hh: Copy to... * mln/morpho/watershed/flooding.hh: ...this new file. (watershed): New namespace. (nbasins): Rename as... (n_basins): ...this. (meyer_wst): Remove overload without n_basins. (meyer_wst): Rename this only remaining routine as... (flooding): ...this. (flooding_dispatch): New. * mln/morpho/watershed/all.hh: New. * mln/morpho/all.hh: Update. * tests/morpho/watershed: New directory. * tests/morpho/watershed/flooding.cc: New. * tests/morpho/watershed/Makefile.am: New. * tests/morpho/Makefile.am: Update. mln/morpho/all.hh | 1 mln/morpho/watershed/all.hh | 65 +++++++++ mln/morpho/watershed/flooding.hh | 266 +++++++++++++++++++++++++++++-------- tests/morpho/Makefile.am | 3 tests/morpho/watershed/Makefile.am | 10 + tests/morpho/watershed/flooding.cc | 61 ++++++++ 6 files changed, 351 insertions(+), 55 deletions(-) Index: mln/morpho/watershed/flooding.hh --- mln/morpho/watershed/flooding.hh (revision 0) +++ mln/morpho/watershed/flooding.hh (working copy) @@ -25,19 +25,20 @@ // reasons why the executable file might be covered by the GNU General // Public License. -#ifndef MLN_MORPHO_MEYER_WST_HH -# define MLN_MORPHO_MEYER_WST_HH +#ifndef MLN_MORPHO_WATERSHED_FLOODING_HH +# define MLN_MORPHO_WATERSHED_FLOODING_HH -/** \file mln/morpho/meyer_wst.hh - \brief Meyer's Watershed Transform (WST) algorithm. - - The Watershed Transform algorithm from Meyer using a hierarchical - queue. - - Reference: - Fernand Meyer. Un algorithme optimal de ligne de partage des - eaux. In: Actes du 8�me Congr�s AFCET, Lyon-Villeurbanne, France - (1991), pages 847--859. */ +/// \file mln/morpho/watershed/flooding.hh +/// +/// Meyer's Watershed Transform (WST) algorithm. +/// +/// The Watershed Transform algorithm from Meyer using a hierarchical +/// queue. +/// +/// Reference: +/// Fernand Meyer. Un algorithme optimal de ligne de partage des +/// eaux. In: Actes du 8�me Congr�s AFCET, Lyon-Villeurbanne, France +/// (1991), pages 847--859. # include <mln/trait/ch_value.hh> @@ -56,59 +57,155 @@ namespace morpho { - /* FIXME: Provide also a version of the algorithm taking an image - of minima as input. */ - /* FIXME: See also the interface of the Shortest-Path Watershed + namespace watershed + { + + /* + FIXME: + Provide also a version of the algorithm taking an image + of minima as input. + + FIXME: + See also the interface of the Shortest-Path Watershed Transform, which proposes to lower-complete the image before processing it. Then, add a reference to - mln/morpho/lower_completion.hh. */ + mln/morpho/lower_completion.hh. + */ - /** \brief Meyer's Watershed Transform (WST) algorithm. + /// Meyer's Watershed Transform (WST) algorithm. + /// + /// \param[in] input The input image. + /// \param[in] nbh The connexity of markers. + /// \param[out] n_basins The number of basins. + /// + /// \li \p L is the type of labels, used to number the watershed + /// itself (with the minimal value), and the basins. + /// \li \p I is the exact type of the input image. + /// \li \p N is the exact type of the neighborhood used to express + /// \a input's connexity. - \param[in] input The input image. - \param[in] nbh The connexity of markers. - \param[out] nbasins The number of basins. - - \li \p L is the type of labels, used to number the watershed - itself (with the minimal value), and the basins. - \li \p I is the exact type of the input image. - \li \p N is the exact type of the neighborhood used to express - \a input's connexity. */ template <typename I, typename N, typename L> mln_ch_value(I, L) - meyer_wst(const Image<I>& input, const Neighborhood<N>& nbh, - L& nbasins); + flooding(const Image<I>& input, const Neighborhood<N>& nbh, + L& n_basins); + - /** \brief Meyer's Watershed Transform (WST) algorithm, with no - count of basins. - \param[in] input The input image. - \param[in] nbh The connexity of markers. +# ifndef MLN_INCLUDE_ONLY + - \li \p L is the type of labels, used to number the watershed - itself (with the minimal value), and the basins. - \li \p I is the exact type of the input image. - \li \p N is the exact type of the neighborhood used to express - \a input's connexity. + // Implementations. - Note that the first parameter, \p L, is not automatically - valued from the type of the actual argument during implicit - instantiation: you have to explicitly pass this parameter at - call sites. */ - template <typename L, typename I, typename N> + namespace impl + { + + namespace generic + { + + template <typename I, typename N, typename L> mln_ch_value(I, L) - meyer_wst(const Image<I>& input, const Neighborhood<N>& nbh); + flooding(const Image<I>& input_, const Neighborhood<N>& nbh_, + L& n_basins) + { + trace::entering("morpho::watershed::impl::generic::flooding"); + /* FIXME: Ensure the input image has scalar values. */ + + const I input = exact(input_); + const N nbh = exact(nbh_); + typedef L marker; + const marker unmarked = literal::zero; -# ifndef MLN_INCLUDE_ONLY + 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); + + typedef mln_psite(I) psite; + + // Ordered queue. + typedef p_queue_fast<psite> Q; + p_priority<V, Q> queue; + + // 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); + + // 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; + break; + } + + /* Until the queue is empty, extract a psite P from the + hierarchical queue, at the highest priority level, that is, + the lowest level. */ + while (! queue.is_empty()) + { + psite 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) + { + if (adjacent_marker == unmarked) + { + adjacent_marker = output(n); + single_adjacent_marker_p = true; + } + else + if (adjacent_marker != output(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)) + { + queue.push(max - input(n), n); + in_queue(n) = true; + } + } + } + trace::exiting("morpho::watershed::impl::generic::flooding"); + return output; + } + + + // Fastest version. template <typename I, typename N, typename L> mln_ch_value(I, L) - meyer_wst(const Image<I>& input_, const Neighborhood<N>& nbh_, - L& nbasins) + flooding_fastest(const Image<I>& input_, const Neighborhood<N>& nbh_, + L& n_basins) { - trace::entering("morpho::meyer_wst"); + trace::entering("morpho::watershed::impl::flooding_fastest"); /* FIXME: Ensure the input image has scalar values. */ const I input = exact(input_); @@ -122,7 +219,7 @@ // Initialize the output with the markers (minima components). mln_ch_value(I, marker) output = - labeling::regional_minima (input, nbh, nbasins); + labeling::regional_minima (input, nbh, n_basins); typedef mln_psite(I) psite; @@ -193,23 +290,84 @@ } } } - trace::exiting("morpho::meyer_wst"); + trace::exiting("morpho::watershed::impl::flooding_fastest"); return output; } - template <typename L, typename I, typename N> + + } // end of namespace mln::morpho::watershed::impl::generic + + } // end of namespace mln::morpho::watershed::impl + + + + // Dispatch. + + namespace internal + { + + template <typename I, typename N, typename L> + inline mln_ch_value(I, L) - meyer_wst(const Image<I>& input, const Neighborhood<N>& nbh) + flooding_dispatch(metal::false_, + const Image<I>& input, const Neighborhood<N>& nbh, L& n_basins) { - L nbasins; - return meyer_wst<L>(input, nbh, nbasins); + return impl::generic::flooding(input, nbh, n_basins); + } + + + template <typename I, typename N, typename L> + inline + mln_ch_value(I, L) + flooding_dispatch(metal::true_, + const Image<I>& 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); + } + + template <typename I, typename N, typename L> + inline + mln_ch_value(I, L) + flooding_dispatch(const Image<I>& input, const Neighborhood<N>& nbh, L& n_basins) + { + enum { + test = mlc_equal(mln_trait_image_speed(I), + trait::image::speed::fastest)::value + && + mln_is_simple_neighborhood(N)::value + }; + return flooding_dispatch(metal::bool_<test>(), + input, nbh, n_basins); + } + + } // end of namespace mln::morpho::watershed::impl + + + // Facade. + + template <typename I, typename N, typename L> + inline + mln_ch_value(I, L) + flooding(const Image<I>& input, const Neighborhood<N>& nbh, L& n_basins) + { + trace::entering("morpho::watershed::flooding"); + + // FIXME: internal::flooding_tests(input, nbh, n_basins); + + mln_ch_value(I, L) output = internal::flooding_dispatch(input, nbh, n_basins); + + trace::exiting("morpho::watershed::flooding"); + return output; } # endif // ! MLN_INCLUDE_ONLY + } // end of namespace mln::morpho::watershed + } // end of namespace mln::morpho } // end of namespace mln -#endif // ! MLN_MORPHO_MEYER_WST_HH +#endif // ! MLN_MORPHO_WATERSHED_FLOODING_HH Property changes on: mln/morpho/watershed/flooding.hh ___________________________________________________________________ Added: svn:mergeinfo Index: mln/morpho/watershed/all.hh --- mln/morpho/watershed/all.hh (revision 0) +++ mln/morpho/watershed/all.hh (revision 0) @@ -0,0 +1,65 @@ +// Copyright (C) 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_MORPHO_WATERSHED_ALL_HH +# define MLN_MORPHO_WATERSHED_ALL_HH + +/// \file mln/morpho/watershed/all.hh +/// +/// File that includes all morphological watershed routines. + + +namespace mln +{ + + namespace morpho + { + + /// Namespace of morphological watershed routines. + namespace watershed + { + + /// Namespace of morphological watershed routines + /// implementations. + namespace watershed + { + + /// Namespace of morphological watershed routines generic + /// implementations. + namespace generic + {} + + } + } + } +} + + +# include <mln/morpho/watershed/flooding.hh> + + +#endif // ! MLN_MORPHO_WATERSHED_ALL_HH Index: mln/morpho/all.hh --- mln/morpho/all.hh (revision 3307) +++ mln/morpho/all.hh (working copy) @@ -86,6 +86,7 @@ # include <mln/morpho/elementary/all.hh> # include <mln/morpho/tree/all.hh> +# include <mln/morpho/watershed/all.hh> Index: tests/morpho/watershed/flooding.cc --- tests/morpho/watershed/flooding.cc (revision 0) +++ tests/morpho/watershed/flooding.cc (revision 0) @@ -0,0 +1,61 @@ +// Copyright (C) 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/morpho/watershed/flooding.cc +/// +/// Test on mln::morpho::watershed::flooding. + +#include <iostream> + +#include <mln/core/image/image2d.hh> +#include <mln/core/alias/window2d.hh> +#include <mln/core/alias/neighb2d.hh> + +#include <mln/value/int_u8.hh> + +#include <mln/morpho/watershed/flooding.hh> + +#include <mln/io/pgm/load.hh> +#include <mln/io/pgm/save.hh> + +#include "tests/data.hh" + + +int main() +{ + using namespace mln; + using value::int_u8; + + image2d<int_u8> input; + io::pgm::load(input, MLN_IMG_DIR "/squares.pgm"); + + typedef int_u8 L; + L nbasins; + image2d<L> output = morpho::watershed::flooding(input, c4(), nbasins); + + io::pgm::save(output, "out.pgm"); +} Index: tests/morpho/watershed/Makefile.am --- tests/morpho/watershed/Makefile.am (revision 0) +++ tests/morpho/watershed/Makefile.am (revision 0) @@ -0,0 +1,10 @@ +## Process this file through Automake to create Makefile.in -*- Makefile -*- + +include $(top_srcdir)/milena/tests/tests.mk + +check_PROGRAMS = \ + flooding + +flooding_SOURCES = flooding.cc + +TESTS = $(check_PROGRAMS) Index: tests/morpho/Makefile.am --- tests/morpho/Makefile.am (revision 3307) +++ tests/morpho/Makefile.am (working copy) @@ -4,7 +4,8 @@ SUBDIRS = \ elementary \ - tree + tree \ + watershed check_PROGRAMS = \ artificial_line_graph_image_wst \