[Olena-patches] r3013: Reconstruction canvas using union-find

URL: https://svn.lrde.epita.fr/svn/oln/trunk/milena/sandbox ChangeLog: 2008-12-09 Matthieu Garrigues &lt;garrigues(a)lrde.epita.fr&gt; The canvas * garrigues/union_find/canvas/reconstruction.hh: New. * garrigues/union_find/canvas: New. Differents implementations of reconstruction. * garrigues/union_find: New. * garrigues/union_find/reconstructions.cc: New. * garrigues/union_find/reconstructions.hh: New. Some small test images. * garrigues/union_find/images/marker.pbm: New. * garrigues/union_find/images/marker_to_dilate.pbm: New. * garrigues/union_find/images/mask.pbm: New. * garrigues/union_find/images: New. --- canvas/reconstruction.hh | 149 +++++++++++++++++++++++++++++ images/marker_to_dilate.pbm | 4 images/mask.pbm | 5 + reconstructions.cc | 57 +++++++++++ reconstructions.hh | 220 ++++++++++++++++++++++++++++++++++++++++++++ 5 files changed, 435 insertions(+) Index: trunk/milena/sandbox/garrigues/union_find/reconstructions.hh =================================================================== --- trunk/milena/sandbox/garrigues/union_find/reconstructions.hh (revision 0) +++ trunk/milena/sandbox/garrigues/union_find/reconstructions.hh (revision 3013) @@ -0,0 +1,220 @@ +// Copyright (C) 2007, 2008 EPITA Research and Development Laboratory +// (LRDE) +// +// This file is part of the Olena Library. This library is free +// software; you can redistribute it and/or modify it under the terms +// of the GNU General Public License version 2 as published by the +// Free Software Foundation. +// +// This library is distributed in the hope that it will be useful, +// but WITHOUT ANY WARRANTY; without even the implied warranty of +// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU +// General Public License for more details. +// +// You should have received a copy of the GNU General Public License +// along with this library; see the file COPYING. If not, write to +// the Free Software Foundation, 51 Franklin Street, Fifth Floor, +// Boston, MA 02111-1307, USA. +// +// As a special exception, you may use this file as part of a free +// software library without restriction. Specifically, if other files +// instantiate templates or use macros or inline functions from this +// file, or you compile this file and link it with other files to +// produce an executable, this file does not by itself cause the +// resulting executable to be covered by the GNU General Public +// License. This exception does not however invalidate any other +// reasons why the executable file might be covered by the GNU General +// Public License. + +#ifndef MLN_RECONSTRUCTIONS_HH +# define MLN_RECONSTRUCTIONS_HH + +# include <mln/core/image/image2d.hh> +# include <mln/core/alias/neighb2d.hh> +# include <mln/level/fill.hh> +# include <mln/level/paste.hh> + +# include "canvas/reconstruction.hh" + +namespace mln +{ + + namespace impl + { + + struct reconstruction_by_dilation_t + { + typedef image2d<bool> I; + typedef mln_site_(I) P; + + reconstruction_by_dilation_t (const I& marker, const I& mask, I& output) + : marker(marker), mask(mask), output(output) + {} + + bool is_in_D(P p) { return mask(p); } + void set_default_output() { level::fill(output, false); } + void init(P p) { output(p) = marker(p); } + void merge(P r, P p) { output(p) = output(p) || output(r); } + void visit_ext_border(P n, P p) { (void) n; (void) p; } + + const I& marker; // F + const I& mask; // G + I& output; // O + }; + + + struct reconstruction_by_dilation_alt_t + { + typedef image2d<bool> I; + typedef mln_site_(I) P; + + reconstruction_by_dilation_alt_t (const I& marker, const I& mask, I& output) + : marker(marker), mask(mask), output(output) + {} + + bool is_in_D(P p) { return mask(p) && !marker(p); } + void set_default_output() { level::paste(marker, output); } + void init(P p) { output(p) = false; } + void merge(P r, P p) { output(p) = output(p) || output(r); } + void visit_ext_border(P n, P p) { if (marker(n)) output(p) = true; } + + const I& marker; // F + const I& mask; // G + I& output; // O + }; + + + struct reconstruction_by_erosion_t + { + typedef image2d<bool> I; + typedef mln_site_(I) P; + + reconstruction_by_erosion_t (const I& marker, const I& mask, I& output) + : marker(marker), mask(mask), output(output) + {} + + bool is_in_D(P p) { return !mask(p); } + void set_default_output() { level::fill(output, true); } + void init(P p) { output(p) = marker(p); } + void merge(P r, P p) { output(p) = output(p) && output(r); } + void visit_ext_border(P n, P p) { (void) n; (void) p; } + + const I& marker; // F + const I& mask; // G + I& output; // O + }; + + struct reconstruction_by_erosion_alt_t + { + typedef image2d<bool> I; + typedef mln_site_(I) P; + + reconstruction_by_erosion_alt_t (const I& marker, const I& mask, I& output) + : marker(marker), mask(mask), output(output) + {} + + bool is_in_D(P p) { return !mask(p) && marker(p); } + void set_default_output() { level::paste(mask, output); } + void init(P p) { output(p) = true; } + void merge(P r, P p) { output(p) = output(p) && output(r); } + void visit_ext_border(P n, P p) { if (!marker(n)) output(p) = false; } + + const I& marker; // F + const I& mask; // G + I& output; // O + }; + + } // end of namespace mln::impl + + + image2d<bool> + reconstruction_by_dilation(const image2d<bool>& marker, + const image2d<bool>& mask, + const neighb2d& nbh) + { + trace::entering("morpho::reconstruction_by_dilation"); + + mln_precondition(exact(marker).has_data()); + mln_precondition(exact(mask).has_data()); + + image2d<bool> output; + initialize(output, marker); + + typedef impl::reconstruction_by_dilation_t F; + F f(marker, mask, output); + canvas::morpho::reconstruction(mask, nbh, f, output); + + trace::exiting("morpho::reconstruction_by_dilation"); + return output; + } + + + image2d<bool> + reconstruction_by_dilation_alt(const image2d<bool>& marker, + const image2d<bool>& mask, + const neighb2d& nbh) + { + trace::entering("morpho::reconstruction_by_dilation_alt"); + + mln_precondition(exact(marker).has_data()); + mln_precondition(exact(mask).has_data()); + + image2d<bool> output; + initialize(output, marker); + + typedef impl::reconstruction_by_dilation_alt_t F; + F f(marker, mask, output); + canvas::morpho::reconstruction(mask, nbh, f, output); + + trace::exiting("morpho::reconstruction_by_dilation_alt"); + return output; + } + + + image2d<bool> + reconstruction_by_erosion(const image2d<bool>& marker, + const image2d<bool>& mask, + const neighb2d& nbh) + { + trace::entering("morpho::reconstruction_by_erosion"); + + mln_precondition(exact(marker).has_data()); + mln_precondition(exact(mask).has_data()); + + image2d<bool> output; + initialize(output, marker); + + typedef impl::reconstruction_by_erosion_t F; + F f(marker, mask, output); + canvas::morpho::reconstruction(mask, nbh, f, output); + + trace::exiting("morpho::reconstruction_by_erosion"); + return output; + } + + + image2d<bool> + reconstruction_by_erosion_alt(const image2d<bool>& marker, + const image2d<bool>& mask, + const neighb2d& nbh) + { + trace::entering("morpho::reconstruction_by_erosion_alt"); + + mln_precondition(exact(marker).has_data()); + mln_precondition(exact(mask).has_data()); + + image2d<bool> output; + initialize(output, marker); + + typedef impl::reconstruction_by_erosion_alt_t F; + F f(marker, mask, output); + canvas::morpho::reconstruction(mask, nbh, f, output); + + trace::exiting("morpho::reconstruction_by_erosion_alt"); + return output; + } + +} // end of namespace mln. + + +#endif // ! MLN_RECONSTRUCTIONS_HH Index: trunk/milena/sandbox/garrigues/union_find/images/marker_to_dilate.pbm =================================================================== --- trunk/milena/sandbox/garrigues/union_find/images/marker_to_dilate.pbm (revision 0) +++ trunk/milena/sandbox/garrigues/union_find/images/marker_to_dilate.pbm (revision 3013) @@ -0,0 +1,4 @@ +P4 +# CREATOR: GIMP PNM Filter Version 1.1 +30 30 +ÿÿÿìÿÿÿÄÿÿÿÄÿÿÿìÿÿÿüÿÿÿüÿÿÿüÿÿÿüÿÿÿüÿÿÿüÿþÿüÿüÿüÿüüÿüüÿÿÿüÿÿÿüÿÿÿüÿÿÿüÿÿÿüÿÿÿüÿÿÿüÿÿÿüÿÿÿüÿÿÿüÏÿÿü‡ÿÿüÿÿüÿÿüßÿÿüÿÿÿü \ No newline at end of file Index: trunk/milena/sandbox/garrigues/union_find/images/mask.pbm =================================================================== --- trunk/milena/sandbox/garrigues/union_find/images/mask.pbm (revision 0) +++ trunk/milena/sandbox/garrigues/union_find/images/mask.pbm (revision 3013) @@ -0,0 +1,5 @@ +P4 +# CREATOR: XV version 3.10a-jumboFix+Enh of 20050501 +# CREATOR: GIMP PNM Filter Version 1.1 +30 30 +ÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÀ?ÿÿÀ?ÿÿÌ?ÿÿÌ?ÿÿÌ?ÿÿÀ?ÿÿÀ?ÿÿÏÿÿÿÏÿÿÿÏÿÿÿÏÿÿÿÀ?ÿÿÀ?ÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿ \ No newline at end of file Index: trunk/milena/sandbox/garrigues/union_find/images/marker.pbm =================================================================== Cannot display: file marked as a binary type. svn:mime-type = application/octet-stream Property changes on: trunk/milena/sandbox/garrigues/union_find/images/marker.pbm ___________________________________________________________________ Name: svn:mime-type + application/octet-stream Index: trunk/milena/sandbox/garrigues/union_find/reconstructions.cc =================================================================== --- trunk/milena/sandbox/garrigues/union_find/reconstructions.cc (revision 0) +++ trunk/milena/sandbox/garrigues/union_find/reconstructions.cc (revision 3013) @@ -0,0 +1,57 @@ +// Copyright (C) 2007, 2008 EPITA Research and Development Laboratory +// (LRDE) +// +// This file is part of the Olena Library. This library is free +// software; you can redistribute it and/or modify it under the terms +// of the GNU General Public License version 2 as published by the +// Free Software Foundation. +// +// This library is distributed in the hope that it will be useful, +// but WITHOUT ANY WARRANTY; without even the implied warranty of +// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU +// General Public License for more details. +// +// You should have received a copy of the GNU General Public License +// along with this library; see the file COPYING. If not, write to +// the Free Software Foundation, 51 Franklin Street, Fifth Floor, +// Boston, MA 02111-1307, USA. +// +// As a special exception, you may use this file as part of a free +// software library without restriction. Specifically, if other files +// instantiate templates or use macros or inline functions from this +// file, or you compile this file and link it with other files to +// produce an executable, this file does not by itself cause the +// resulting executable to be covered by the GNU General Public +// License. This exception does not however invalidate any other +// reasons why the executable file might be covered by the GNU General +// Public License. + +# include "reconstructions.hh" +# include <mln/core/alias/neighb2d.hh> +# include <mln/core/image/image2d.hh> +# include <mln/io/pbm/load.hh> +# include <mln/io/pbm/save.hh> + +int main(int argc, char** argv) +{ + using namespace mln; + typedef image2d<bool> I; + + image2d<bool> marker; + image2d<bool> mask; + image2d<bool> output; + + if (argc < 2) + { + std::cerr << "Usage: " << argv[0] << " marker.pbm mask.pbm" << std::endl; + return 1; + } + + io::pbm::load(marker, argv[1]); + io::pbm::load(mask, argv[2]); + + io::pbm::save(reconstruction_by_dilation (marker, mask, c4()), "r1.pbm"); + io::pbm::save(reconstruction_by_dilation_alt(marker, mask, c4()), "r2.pbm"); + io::pbm::save(reconstruction_by_erosion (marker, mask, c4()), "r3.pbm"); + io::pbm::save(reconstruction_by_erosion_alt (marker, mask, c4()), "r4.pbm"); +} Index: trunk/milena/sandbox/garrigues/union_find/canvas/reconstruction.hh =================================================================== --- trunk/milena/sandbox/garrigues/union_find/canvas/reconstruction.hh (revision 0) +++ trunk/milena/sandbox/garrigues/union_find/canvas/reconstruction.hh (revision 3013) @@ -0,0 +1,149 @@ +// Copyright (C) 2007, 2008 EPITA Research and Development Laboratory +// (LRDE) +// +// This file is part of the Olena Library. This library is free +// software; you can redistribute it and/or modify it under the terms +// of the GNU General Public License version 2 as published by the +// Free Software Foundation. +// +// This library is distributed in the hope that it will be useful, +// but WITHOUT ANY WARRANTY; without even the implied warranty of +// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU +// General Public License for more details. +// +// You should have received a copy of the GNU General Public License +// along with this library; see the file COPYING. If not, write to +// the Free Software Foundation, 51 Franklin Street, Fifth Floor, +// Boston, MA 02111-1307, USA. +// +// As a special exception, you may use this file as part of a free +// software library without restriction. Specifically, if other files +// instantiate templates or use macros or inline functions from this +// file, or you compile this file and link it with other files to +// produce an executable, this file does not by itself cause the +// resulting executable to be covered by the GNU General Public +// License. This exception does not however invalidate any other +// reasons why the executable file might be covered by the GNU General +// Public License. + +#ifndef MLN_CANVAS_ON_SET_HH +# define MLN_CANVAS_ON_SET_HH + +# include <mln/core/image/image2d.hh> +# include <mln/level/fill.hh> +# include <mln/literal/zero.hh> +# include <mln/convert/to_upper_window.hh> +# include <mln/accu/count.hh> +# include <mln/util/pix.hh> + +# include <mln/core/alias/neighb2d.hh> + +# include <mln/io/pbm/save.hh> +# include <mln/io/pbm/load.hh> + +namespace mln +{ + + + namespace canvas + { + + namespace morpho + { + + template <typename I> + static inline + mln_psite(I) + find_root(I& parent, + const mln_psite(I)& x) + { + if (parent(x) == x) + return x; + else + return parent(x) = find_root(parent, parent(x)); + } + + template <typename N, typename F, typename I, typename O> + void + reconstruction(const Image<I>& mask_, + const Neighborhood<N>& nbh_, + F& f, + O& output) + { + trace::entering("canvas::morpho::reconstruction"); + + const N& nbh = exact(nbh_); + const I& mask = exact(mask_); + + mln_precondition(mask.domain() == output.domain()); + + // Local type. + typedef typename F::P P; + + // Auxiliary data. + mln_ch_value(O, bool) deja_vu; + mln_ch_value(O, P) parent; + + // init + { + initialize(deja_vu, mask); + initialize(parent, mask); + + mln::level::fill(deja_vu, false); + f.set_default_output(); // Client initialization. + } + + // first pass + { + mln_fwd_piter(I) p(mask.domain()); + mln_niter(N) n(nbh, p); + for_all(p) + { + if (f.is_in_D(p)) + { + // Make set. + parent(p) = p; + f.init(p); + + for_all(n) if (mask.domain().has(n)) + { + if (deja_vu(n) && f.is_in_D(n)) + { + //do_union(n, p); + P r = find_root(parent, n); + if (r != p) + { + f.merge(r, p); + parent(r) = p; + } + } + else + // Visit boundaries of D. + f.visit_ext_border(n, p); + } + deja_vu(p) = true; + } + + } + } + + // second pass + { + mln_bkd_piter(I) p(mask.domain()); + for_all(p) + if (f.is_in_D(p)) + if (parent(p) != p) // if p is not a root. + output(p) = output(parent(p)); + } + + trace::exiting("canvas::morpho::reconstruction"); + } + + + } // end of namespace mln::canvas::morpho + + } // end of namespace mln::canvas + +} // end of namespace mln. + +#endif // ! MLN_CANVAS_ON_SET_HH