[Olena-patches] 937: Draft union_find using canvas (two_pass).

Index: ChangeLog from Ugo Jardonnet &lt;ugo.jardonnet(a)lrde.epita.fr&gt; Draft union_find using canvas (two_pass). * oln/morpho/reconstruction.hh: Fix. * oln/morpho/cc_tarjan.hh: Fix. * oln/morpho/union_find.hh: New. * oln/canvas: New. * oln/canvas/two_pass.hh: New. canvas/two_pass.hh | 52 ++++++++++++++++ morpho/cc_tarjan.hh | 3 morpho/reconstruction.hh | 10 +-- morpho/union_find.hh | 144 +++++++++++++++++++++++++++++++++++++++++++++++ 4 files changed, 202 insertions(+), 7 deletions(-) Index: oln/morpho/reconstruction.hh --- oln/morpho/reconstruction.hh (revision 936) +++ oln/morpho/reconstruction.hh (working copy) @@ -63,7 +63,7 @@ template <typename I> oln_plain(I) - reconstruction_loop(const Image_with_Nbh<I>& marker, + reconstruction_loop(Image_with_Nbh<I>& marker, const Binary_Image<I>& mask) { oln_plain(I) output; @@ -86,10 +86,10 @@ template <typename I , typename J> void // FIXME : Slow impl. - reconstruction_(const Image_with_Nbh<I>& marker, + reconstruction_(Image_with_Nbh<I>& marker, const Binary_Image<J>& mask) { - image2d<int> tmp = level::clone(exact(marker).image()); + I tmp = level::clone(marker); while ( not stability(marker, tmp) ) { @@ -104,10 +104,10 @@ template <typename I , typename J> void - reconstruction(const Image_with_Nbh<I>& marker, + reconstruction(Image_with_Nbh<I>& marker, const Binary_Image<J>& mask) { - impl::reconstruction_(exact(marker), exact(mask)); + impl::reconstruction_(marker, exact(mask)); } # endif // ! OLN_INCLUDE_ONLY Index: oln/morpho/cc_tarjan.hh --- oln/morpho/cc_tarjan.hh (revision 936) +++ oln/morpho/cc_tarjan.hh (working copy) @@ -118,8 +118,7 @@ oln_plain(I) is_processed; prepare(is_processed, with, input); - oln_piter(I) p1(input.points()); - for_all(p1) + oln_piter(I) p1(is_processed.points()); is_processed(p1) = false; // FIXME : built with ?. first_pass(input, parent, is_processed); Index: oln/morpho/union_find.hh --- oln/morpho/union_find.hh (revision 0) +++ oln/morpho/union_find.hh (revision 0) @@ -0,0 +1,144 @@ +// 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 receiv 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 OLN_MORPHO_UNION_FIND_HH +# define OLN_MORPHO_UNION_FIND_HH + +# include <oln/core/concept/image.hh> + +# include <oln/canvas/two_pass.hh> + +namespace oln +{ + + namespace morpho + { + + template <typename I> + oln_plain_value(I, unsigned) + union_find(const Binary_Image<I>& input); + +# ifndef OLN_INCLUDE_ONLY + + namespace impl + { + template <typename I> + struct union_find_ + { + const I& input; + oln_plain(I) output; + + oln_plain(I) is_processed; + oln_plain_value(I, oln_point(I)) parent; + + union_find_(const I& in) + : input(in) + { + prepare(is_processed, oln::with, input); + prepare(output, oln::with, input); + prepare(parent, oln::with, input); + } + + oln_point(I) find_root(I& ima, + const oln_point(I)& x, + oln_plain_value(I, oln_point(I))& parent) + { + if (parent(x) != x) + { + parent(x) = find_root(ima, parent(x), parent); + return parent(x); + } + return x; + } + + void do_union(I& ima, + const oln_point(I)& n, + const oln_point(I)& p, + oln_plain_value(I, oln_point(I))& parent) + { + oln_point(I) r = find_root(ima, n, parent); + if (r != p) + parent(r) = p; + } + + void init() + { + oln::level::fill(is_processed, false); + } + + void first_pass_body(const oln_point(I)& p) + { + parent(p) = p; + if ( input(p) ) + { + oln_niter(I) n(p, input); + for_all(n) + { + if ( input(n) == true and is_processed(n) ) + do_union(input, n, p, parent); + } + is_processed(p) = true; + } + + } + + void second_pass_body(const oln_point(I)& p) + { + unsigned current_label = 0; + if ( input(p) == true and parent(p) == p ) + output(p) = ++current_label; + else + output(p) = output(parent(p)); + } + + void final() + { + } + + }; + + } // end of namespace oln::morpho::impl + +// Facades. + + template <typename I> + oln_plain_value(I, unsigned) + union_find(const Binary_Image<I>& input) + { + union_find_<I> f(input); + canvas::two_pass(f); + return f.output; + } + +# endif // ! OLN_INCLUDE_ONLY + + } // end of namespace oln::morpho + +} // end of namespace oln + + +#endif // ! OLN_MORPHO_UNION_FIND_HH Index: oln/canvas/two_pass.hh --- oln/canvas/two_pass.hh (revision 0) +++ oln/canvas/two_pass.hh (revision 0) @@ -0,0 +1,52 @@ +// 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 receiv 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 OLN_CANVAS_TWO_PASS_HH +# define OLN_CANVAS_TWO_PASS_HH + +namespace canvas +{ + + template <typename F, typename I> + void two_pass(F f, I input) + { + f.init(); + + oln_piter(I) p1(f.input.points()); + for_all(p1) + f.first_pass_body(p1); + + oln_bkd_piter(I) p2(f.input.points()); + for_all(p2) + f.second_pass_body(p2); + + f.final(); + } + +} + +#endif // ! OLN_CANVAS_TWO_PASS_HH