[Olena-patches] proto-1.0 262: Add parallel morphological reconstruction

Index: ChangeLog from Damien Thivolle &lt;damien(a)lrde.epita.fr&gt; * tests/morpho/tests/reconstruction: Add parallel reconstruction tests. * oln/morpho/reconstruction_by_dilation.hh: Add `by dilation' version of the parallel reconstruction. * oln/morpho/reconstruction_by_erosion.hh: Add `by erosion' version of the parallel reconstruction.. * oln/canvas/reconstruction.hh: Add parallel reconstruction canvas. * oln/canvas/forth.hh: New. Forward loop canvas. Both with and without convergence versions. * oln/canvas/backandforth.hh: back_and_force_until_convergence now inherits from until_convergence. * oln/canvas/until_convergence.hh: New. `until convergence' canvas. oln/canvas/backandforth.hh | 55 ++--------- oln/canvas/forth.hh | 144 +++++++++++++++++++++++++++++++ oln/canvas/reconstruction.hh | 85 +++++++++++++++++- oln/canvas/until_convergence.hh | 122 ++++++++++++++++++++++++++ oln/morpho/reconstruction_by_dilation.hh | 128 +++++++++++++++++++-------- oln/morpho/reconstruction_by_erosion.hh | 122 ++++++++++++++++++-------- tests/morpho/tests/reconstruction | 19 ++++ 7 files changed, 558 insertions(+), 117 deletions(-) Index: oln/canvas/backandforth.hh --- oln/canvas/backandforth.hh (revision 261) +++ oln/canvas/backandforth.hh (working copy) @@ -28,8 +28,7 @@ #ifndef OLENA_CANVAS_BACKANDFORTH_HH # define OLENA_CANVAS_BACKANDFORTH_HH -# include <mlc/any.hh> -# include <mlc/contract.hh> +# include <oln/canvas/until_convergence.hh> # include <oln/core/abstract/image.hh> # include <oln/core/abstract/piter.hh> @@ -37,20 +36,14 @@ namespace oln { - namespace canvas - { + namespace canvas { + template <typename I, typename E> - struct back_and_forth_until_convergence : public mlc::any<E> + struct back_and_forth_until_convergence : public until_convergence<E> { // Abstract methods. - // Initialize 'work'. - void init() - { - this->exact().impl_init(); - } - // Do something like 'work -> output'. void bkd_loop_body() { @@ -63,25 +56,10 @@ this->exact().impl_fwd_loop_body(); } - // Check stability from input, output, and work. - bool is_stable() const - { - return this->exact().impl_is_stable(); - } - - // Do something like 'work := output'. - void re_loop() - { - return this->exact().impl_re_loop(); - } - // Concrete method. - void run() - { - bool stability; - init(); - for (;;) + void impl_loop_body() { + // back for_all_p (bkd_p) bkd_loop_body(); @@ -90,14 +68,6 @@ for_all_p (fwd_p) fwd_loop_body(); - // stability check - stability = is_stable(); - if (stability) - return; - - // prepare a new loop iteration - re_loop(); - } } @@ -117,11 +87,8 @@ // Check for impls.. ~back_and_forth_until_convergence() { - mlc_check_method_impl(E, void, init, , ); mlc_check_method_impl(E, void, bkd_loop_body, , ); mlc_check_method_impl(E, void, fwd_loop_body, , ); - mlc_check_method_impl(E, bool, is_stable, , const); - mlc_check_method_impl(E, void, re_loop, , ); } }; Index: oln/canvas/forth.hh --- oln/canvas/forth.hh (revision 0) +++ oln/canvas/forth.hh (revision 0) @@ -0,0 +1,144 @@ +// Copyright (C) 2005 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, 59 Temple Place - Suite 330, 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 OLENA_CANVAS_FORTH_HH +# define OLENA_CANVAS_FORTH_HH + +# include <oln/canvas/until_convergence.hh> +# include <oln/core/abstract/image.hh> +# include <oln/core/abstract/piter.hh> + + +namespace oln { + + + namespace canvas { + + + template <typename I, typename E> + struct forth_until_convergence : public until_convergence<E> + { + // Abstract methods. + + // Do something like 'work -> output'. + void fwd_loop_body() + { + this->exact().impl_fwd_loop_body(); + } + + // Concrete method. + void impl_loop_body() + { + + // back + for_all_p (fwd_p) + fwd_loop_body(); + } + + + protected: + + // Ctor. + forth_until_convergence(const abstract::image<I>& input) : + fwd_p(input.size()) + { + } + + // Attributes. + oln_type_of(I, fwd_piter) fwd_p; + + // Check for impls.. + ~forth_until_convergence() + { + mlc_check_method_impl(E, void, fwd_loop_body, , ); + } + + }; + + + template <typename I, typename E> + struct forth : public mlc::any<E> + { + // Abstract methods. + + void init() + { + this->exact().impl_init(); + } + + void preconditions() + { + this->exact().impl_preconditions(); + } + + // Do something like 'work -> output'. + void fwd_loop_body() + { + this->exact().impl_fwd_loop_body(); + } + + // Concrete method. + void run() + { + preconditions(); + init(); + + // forth + for_all_p (fwd_p) + fwd_loop_body(); + + } + + + protected: + + // Ctor. + forth(const abstract::image<I>& input) : + fwd_p(input.size()) + { + } + + // Attributes. + oln_type_of(I, fwd_piter) fwd_p; + + // Check for impls.. + ~forth() + { + mlc_check_method_impl(E, void, init, , ); + mlc_check_method_impl(E, void, fwd_loop_body, , ); + mlc_check_method_impl(E, void, preconditions, , ); + } + + }; + + } // end of namespace oln::canvas + + +} // end of namespace oln + + +#endif // ! OLENA_CANVAS_FORTH_HH Index: oln/morpho/reconstruction_by_dilation.hh --- oln/morpho/reconstruction_by_dilation.hh (revision 261) +++ oln/morpho/reconstruction_by_dilation.hh (working copy) @@ -55,13 +55,6 @@ using super_type::p; - reconstruction_by_dilation(const abstract::image_with_nbh<I1>& marker, - const abstract::image<I2>& mask) : - super_type(marker, mask) - { - } - - /// Local image "or-value" for dilation on sets /// (based on the point and its backward neighborhood). @@ -107,13 +100,66 @@ output[fwd_p] = f_min_alt(mask[fwd_p].value(), fwd_or()); } - void impl_preconditions() + reconstruction_by_dilation(const abstract::image_with_nbh<I1>& marker, + const abstract::image<I2>& mask) : + super_type(marker, mask) + { + } + + }; + + // Hybrid version + + template<typename I1, typename I2> + struct reconstruction <I1, I2, tag::hybrid_type, tag::by_dilation_type> + : public reconstruction_by_dilation<I1, I2, tag::hybrid_type, + reconstruction<I1, I2, tag::hybrid_type, tag::by_dilation_type> > + { + typedef reconstruction<I1, I2, tag::hybrid_type, + tag::by_dilation_type> self_type; + typedef reconstruction_by_dilation<I1, I2, tag::hybrid_type, + self_type> super_type; + + using super_type::mask; + using super_type::marker; + using super_type::output; + using super_type::bkd_p; + using super_type::n; + using super_type::p; + using super_type::fifo; + + + void impl_preconditions() const { precondition(level::is_greater_or_equal(mask, marker)); } + void impl_fifo_loop_body() + { + if ((output[n] < output[p]) and (mask[n] != output[n])) + { + // FIXME: The calls to value_box<>::value are needed to + // have f_min_alt compile. Try to get rid of it. + output[n] = f_max_alt(output[p].value(), mask[n].value()); + fifo.push(n); + } + } + + bool impl_test_fifo_push() + { + return output[n] < output[bkd_p] and output[n] < mask[n]; + } + + + reconstruction(const abstract::image_with_nbh<I1>& marker, + const abstract::image<I2>& mask) : + super_type(marker, mask) + { + } + }; + // Sequential version template<typename I1, typename I2> @@ -127,58 +173,68 @@ typedef reconstruction_by_dilation<I1, I2, tag::sequential_type, self_type> super_type; + using super_type::mask; + using super_type::marker; + + void impl_preconditions() const + { + precondition(level::is_greater_or_equal(mask, marker)); + } + + reconstruction(const abstract::image_with_nbh<I1>& marker, const abstract::image<I2>& mask) : super_type(marker, mask) { } + }; - // Hybrid version + // Parallel version template<typename I1, typename I2> - struct reconstruction <I1, I2, tag::hybrid_type, tag::by_dilation_type> - : public reconstruction_by_dilation<I1, I2, tag::hybrid_type, - reconstruction<I1, I2, tag::hybrid_type, tag::by_dilation_type> > + struct reconstruction<I1, I2, tag::parallel_type, tag::by_dilation_type> + : public canvas::reconstruction<I1, I2, tag::parallel_type, + reconstruction<I1, I2, tag::parallel_type, tag::by_dilation_type> > { - typedef reconstruction<I1, I2, tag::hybrid_type, + typedef reconstruction<I1, I2, tag::parallel_type, tag::by_dilation_type> self_type; - typedef reconstruction_by_dilation<I1, I2, tag::hybrid_type, + typedef canvas::reconstruction<I1, I2, tag::parallel_type, self_type> super_type; - reconstruction(const abstract::image_with_nbh<I1>& marker, - const abstract::image<I2>& mask) : - super_type(marker, mask) - { - } - using super_type::mask; + using super_type::marker; + using super_type::save; using super_type::output; - using super_type::bkd_p; - using super_type::n; - using super_type::p; - using super_type::fifo; + using super_type::fwd_p; - void impl_fifo_loop_body() - { - if ((output[n] < output[p]) and (mask[n] != output[n])) + void impl_preconditions() const { - // FIXME: The calls to value_box<>::value are needed to - // have f_min_alt compile. Try to get rid of it. - output[n] = f_max_alt(output[p].value(), mask[n].value()); - fifo.push(n); + precondition(level::is_greater_or_equal(mask, marker)); } + + void impl_fwd_loop_body() + { + // dilation step + if (not output[fwd_p]) + output[fwd_p] = local_or_value(join(save, marker.nbh_get()), + fwd_p); + + // minimum between mask and output + output[fwd_p] = f_min_alt(output[fwd_p].value(), mask[fwd_p].value()); } - bool impl_test_fifo_push() + reconstruction(const abstract::image_with_nbh<I1>& marker, + const abstract::image<I2>& mask) : + super_type(marker, mask) { - return output[n] < output[bkd_p] and output[n] < mask[n]; } }; + } } Index: oln/canvas/until_convergence.hh --- oln/canvas/until_convergence.hh (revision 0) +++ oln/canvas/until_convergence.hh (revision 0) @@ -0,0 +1,122 @@ +// Copyright (C) 2005 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, 59 Temple Place - Suite 330, 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 OLENA_CANVAS_UNTIL_CONVERGENCE_HH +# define OLENA_CANVAS_UNTIL_CONVERGENCE_HH + +# include <mlc/any.hh> +# include <mlc/contract.hh> + +namespace oln { + + + namespace canvas { + + + template <typename E> + struct until_convergence : public mlc::any<E> + { + // Abstract methods. + + // Initialize 'work'. + void init() + { + this->exact().impl_init(); + } + + void preconditions() const + { + this->exact().impl_preconditions(); + } + + // Do something like 'work -> output'. + void loop_body() + { + this->exact().impl_loop_body(); + } + + // Check stability from input, output, and work. + bool is_stable() const + { + return this->exact().impl_is_stable(); + } + + // Do something like 'work := output'. + void re_loop() + { + return this->exact().impl_re_loop(); + } + + // Concrete method. + void run() + { + bool stability; + preconditions(); + init(); + for (;;) + { + loop_body(); + + // stability check + stability = is_stable(); + if (stability) + return; + + // prepare a new loop iteration + re_loop(); + } + } + + + protected: + + // Ctor. + until_convergence() + { + } + + // Check for impls.. + ~until_convergence() + { + mlc_check_method_impl(E, void, init, , ); + mlc_check_method_impl(E, void, preconditions, , const); + mlc_check_method_impl(E, void, loop_body, , ); + mlc_check_method_impl(E, bool, is_stable, , const); + mlc_check_method_impl(E, void, re_loop, , ); + } + + + }; + + + } // end of namespace oln::canvas + + +} // end of namespace oln + + +#endif // ! OLENA_CANVAS_UNTIL_CONVERGENCE_HH Index: tests/morpho/tests/reconstruction --- tests/morpho/tests/reconstruction (revision 261) +++ tests/morpho/tests/reconstruction (working copy) @@ -24,8 +24,10 @@ image2d<ntg::bin> mask; image_with_nbh<image2d<ntg::bin>, neighborhood2d> res_dil_hyb; image_with_nbh<image2d<ntg::bin>, neighborhood2d> res_dil_seq; + image_with_nbh<image2d<ntg::bin>, neighborhood2d> res_dil_par; image_with_nbh<image2d<ntg::bin>, neighborhood2d> res_ero_hyb; image_with_nbh<image2d<ntg::bin>, neighborhood2d> res_ero_seq; + image_with_nbh<image2d<ntg::bin>, neighborhood2d> res_ero_par; utils::key::value_type data_key[16] = { 0xd1, 0x5c, 0x13, 0xd8, 0xe0, 0xa8, 0x58, 0x7d, @@ -46,7 +48,14 @@ morpho::tag::sequential(), morpho::tag::by_dilation()); + res_dil_par = + morpho::reconstruction(join(marker, neighb_c4()), + mask, + morpho::tag::parallel(), + morpho::tag::by_dilation()); + image2d<ntg::bin> marker_c(level::invert(marker)); + res_ero_hyb = morpho::reconstruction(join(marker_c, neighb_c4()), level::invert(mask), @@ -58,6 +67,12 @@ morpho::tag::sequential(), morpho::tag::by_erosion()); + res_ero_par = + morpho::reconstruction(join(marker_c, neighb_c4()), + level::invert(mask), + morpho::tag::parallel(), + morpho::tag::by_erosion()); + if (utils::md5(res_dil_hyb) != key) return true; @@ -68,6 +83,10 @@ return true; if (!level::is_equal(res_dil_hyb, level::invert(res_ero_seq))) return true; + if (!level::is_equal(res_dil_hyb, res_dil_par)) + return true; + if (!level::is_equal(res_ero_hyb, res_ero_par)) + return true; return false; } Index: oln/morpho/reconstruction_by_erosion.hh --- oln/morpho/reconstruction_by_erosion.hh (revision 261) +++ oln/morpho/reconstruction_by_erosion.hh (working copy) @@ -55,13 +55,6 @@ using super_type::p; - reconstruction_by_erosion(const abstract::image_with_nbh<I1>& marker, - const abstract::image<I2>& mask) : - super_type(marker, mask) - { - } - - /// Local image "and-value" for erosion on sets /// (based on the point and its backward neighborhood). @@ -107,13 +100,66 @@ output[fwd_p] = f_max_alt(mask[fwd_p].value(), fwd_and()); } - void impl_preconditions() + reconstruction_by_erosion(const abstract::image_with_nbh<I1>& marker, + const abstract::image<I2>& mask) : + super_type(marker, mask) + { + } + + }; + + + // Hybrid version + + template<typename I1, typename I2> + struct reconstruction <I1, I2, tag::hybrid_type, tag::by_erosion_type> + : public reconstruction_by_erosion<I1, I2, tag::hybrid_type, + reconstruction<I1, I2, tag::hybrid_type, tag::by_erosion_type> > + { + typedef reconstruction<I1, I2, tag::hybrid_type, + tag::by_erosion_type> self_type; + typedef reconstruction_by_erosion<I1, I2, tag::hybrid_type, + self_type> super_type; + + using super_type::mask; + using super_type::marker; + using super_type::output; + using super_type::bkd_p; + using super_type::n; + using super_type::p; + using super_type::fifo; + + + void impl_fifo_loop_body() + { + if ((output[n] > output[p]) and (mask[n] != output[n])) + { + // FIXME: The calls to value_box<>::value are needed to + // have f_min_alt compile. Try to get rid of it. + output[n] = f_min_alt(output[p].value(), mask[n].value()); + fifo.push(n); + } + } + + void impl_preconditions() const { precondition(level::is_greater_or_equal(marker, mask)); } + bool impl_test_fifo_push() + { + return output[n] > output[bkd_p] and output[n] > mask[n]; + } + + reconstruction(const abstract::image_with_nbh<I1>& marker, + const abstract::image<I2>& mask) : + super_type(marker, mask) + { + } + }; + // Sequential version template<typename I1, typename I2> @@ -126,6 +172,13 @@ tag::by_erosion_type> self_type; typedef reconstruction_by_erosion<I1, I2, tag::sequential_type, self_type> super_type; + using super_type::mask; + using super_type::marker; + + void impl_preconditions() const + { + precondition(level::is_greater_or_equal(marker, mask)); + } reconstruction(const abstract::image_with_nbh<I1>& marker, const abstract::image<I2>& mask) : @@ -135,46 +188,45 @@ }; - // Hybrid version + // Parallel version template<typename I1, typename I2> - struct reconstruction <I1, I2, tag::hybrid_type, tag::by_erosion_type> - : public reconstruction_by_erosion<I1, I2, tag::hybrid_type, - reconstruction<I1, I2, tag::hybrid_type, tag::by_erosion_type> > + struct reconstruction<I1, I2, tag::parallel_type, tag::by_erosion_type> + : public canvas::reconstruction<I1, I2, tag::parallel_type, + reconstruction<I1, I2, tag::parallel_type, tag::by_erosion_type> > { - typedef reconstruction<I1, I2, tag::hybrid_type, + typedef reconstruction<I1, I2, tag::parallel_type, tag::by_erosion_type> self_type; - typedef reconstruction_by_erosion<I1, I2, tag::hybrid_type, + typedef canvas::reconstruction<I1, I2, tag::parallel_type, self_type> super_type; - reconstruction(const abstract::image_with_nbh<I1>& marker, - const abstract::image<I2>& mask) : - super_type(marker, mask) - { - } - using super_type::mask; + using super_type::marker; + using super_type::save; using super_type::output; - using super_type::bkd_p; - using super_type::n; - using super_type::p; - using super_type::fifo; + using super_type::fwd_p; - void impl_fifo_loop_body() - { - if ((output[n] > output[p]) and (mask[n] != output[n])) + void impl_preconditions() const { - // FIXME: The calls to value_box<>::value are needed to - // have f_min_alt compile. Try to get rid of it. - output[n] = f_min_alt(output[p].value(), mask[n].value()); - fifo.push(n); + precondition(level::is_greater_or_equal(marker, mask)); } + + void impl_fwd_loop_body() + { + // erosion step + if (output[fwd_p]) + output[fwd_p] = local_and_value(join(save, marker.nbh_get()), + fwd_p); + + // maximum between mask and output + output[fwd_p] = f_max_alt(output[fwd_p].value(), mask[fwd_p].value()); } - bool impl_test_fifo_push() + reconstruction(const abstract::image_with_nbh<I1>& marker, + const abstract::image<I2>& mask) : + super_type(marker, mask) { - return output[n] > output[bkd_p] and output[n] > mask[n]; } }; Index: oln/canvas/reconstruction.hh --- oln/canvas/reconstruction.hh (revision 261) +++ oln/canvas/reconstruction.hh (working copy) @@ -30,6 +30,7 @@ # include <queue> +# include <oln/canvas/forth.hh> # include <oln/canvas/backandforth.hh> # include <oln/level/compare.hh> # include <oln/utils/clone.hh> @@ -65,6 +66,8 @@ typedef oln_nbh_type_of(nbh_type, window) window_type; typedef oln_type_of(I1, concrete) output_type; + // Abstract methods. + bool test_fifo_push() { p = bkd_p; @@ -75,7 +78,8 @@ return false; } - void preconditions() + + void preconditions() const { this->exact().impl_preconditions(); } @@ -95,6 +99,8 @@ this->exact().impl_fifo_loop_body(); } + // Concrete methods. + void init() { // FIXME: We can't use `output = clone(marker)' directly here, @@ -153,6 +159,7 @@ ~reconstruction() { mlc_check_method_impl(E, bool, test_fifo_push, , ); + mlc_check_method_impl(E, void, preconditions, , const); mlc_check_method_impl(E, void, bkd_loop_body, , ); mlc_check_method_impl(E, void, fwd_loop_body, , ); mlc_check_method_impl(E, void, fifo_loop_body, , ); @@ -175,7 +182,6 @@ - template <typename I1, typename I2, typename E> struct reconstruction<I1, I2, morpho::tag::sequential_type, E> : public back_and_forth_until_convergence<I1, E> @@ -185,6 +191,8 @@ typedef oln_nbh_type_of(nbh_type, window) window_type; typedef oln_type_of(I1, concrete) output_type; + // Concrete methods. + void impl_init() { // FIXME: We can't use `output = clone(marker)' directly here, @@ -218,6 +226,8 @@ return output.unbox(); } + protected: + reconstruction(const abstract::image_with_nbh<I1>& marker, const abstract::image<I2>& mask) : super_type(marker), @@ -237,6 +247,77 @@ }; + + template <typename I1, typename I2, typename E> + struct reconstruction<I1, I2, morpho::tag::parallel_type, E> : + public forth_until_convergence<I1, E> + { + typedef forth_until_convergence<I1, E> super_type; + typedef oln_type_of(I1, neighb) nbh_type; + typedef oln_nbh_type_of(nbh_type, window) window_type; + typedef oln_type_of(I1, concrete) output_type; + + // Abstract methods. + + void fwd_loop_body() + { + this->exact().impl_fwd_loop_body(); + } + + // Concrete methods. + + void impl_init() + { + // FIXME: We can't use `output = clone(marker)' directly here, + // because box's op=(const abstract::image<II>& rhs) would be + // called, which is empty (see oln/core/box.hh). + output_type output_tmp(clone(marker)); + output = output_tmp; + // FIXME: We can't use `save = clone(marker)' directly here, + // because box's op=(const abstract::image<II>& rhs) would be + // called, which is empty (see oln/core/box.hh). + output_type save_tmp(clone(marker)); + save = save_tmp; + + } + + + bool impl_is_stable() const + { + return level::is_equal(save, output); + } + + void impl_re_loop() + { + // FIXME: We can't use `save = clone(output)' directly here, + // because box's op=(const abstract::image<II>& rhs) would be + // called, which is empty (see oln/core/box.hh). + save.unbox() = clone(output); + } + + oln_type_of(I1, concrete) get_output() + { + return output.unbox(); + } + + protected: + + reconstruction(const abstract::image_with_nbh<I1>& marker, + const abstract::image<I2>& mask) : + super_type(marker), + marker(marker.exact()), + mask(mask.exact()) + { + } + + box<oln_type_of(I1, concrete)> save; + box<oln_type_of(I1, concrete)> output; + box<const I1> marker; + box<const I2> mask; + + }; + + }