[Olena-patches] 973: Canvas : Add union-find, two_pass version. Fix reconstruction.

Index: ChangeLog from Ugo Jardonnet &lt;ugo.jardonnet(a)lrde.epita.fr&gt; Canvas : Add union-find, two_pass version. Fix reconstruction. * oln/core/internal/point_impl.hh: Whitespaces. * oln/morpho/binary_reconstruction_v0.hh: Procedure version. * oln/morpho/fast_binary_reconstruction.hh: Fast hybrid version. * oln/morpho/reconstruction.hh: removed. * oln/morpho/binary_reconstruction.hh: Removed. * oln/morpho/binary_reconstruction_v1.hh: Canvas version. * oln/level/local_sup.hh: Fixed. * oln/level/local_inf.hh: Fixed. * oln/canvas/union_find.hh: New. * oln/canvas/two_pass.hh: New version (v4) with inheritens. canvas/two_pass.hh | 40 ++++++------ canvas/union_find.hh | 76 ++++++++++++++++++++++ level/local_inf.hh | 6 - level/local_sup.hh | 6 - morpho/binary_reconstruction_v0.hh | 123 +++++++++++++++++++++++++++++++++++++ morpho/binary_reconstruction_v1.hh | 122 ++++++++++++++++++++++++++++++++++++ morpho/cc_tarjan_v1.hh | 5 - 7 files changed, 353 insertions(+), 25 deletions(-) Index: oln/core/internal/point_impl.hh Index: oln/morpho/binary_reconstruction_v0.hh --- oln/morpho/binary_reconstruction_v0.hh (revision 0) +++ oln/morpho/binary_reconstruction_v0.hh (revision 0) @@ -0,0 +1,123 @@ +// Copyright (C) 2007 EPITA Research and Development Laboratory +// 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 OLN_MORPHO_BINARY_RECONSTRUCTION_HH +# define OLN_MORPHO_BINARY_RECONSTRUCTION_HH + +# include <oln/core/concept/image.hh> +# include <oln/accumulator/max.hh> +# include <oln/level/clone.hh> +# include <oln/level/fill.hh> +# include <oln/level/local_inf.hh> +# include <oln/level/local_sup.hh> + +namespace oln +{ + + namespace morpho + { + + template <typename I , typename J> + void + binary_reconstruction(const Binary_Image<I>& marker, + const Binary_Image<J>& mask); + +# ifndef OLN_INCLUDE_ONLY + + namespace impl + { + + template <typename I> + bool + stability(const Image_with_Nbh<I>& marker, + oln_plain(I)& tmp) + { + oln_piter(I) p(marker.points()); + for_all(p) + if (marker(p) != tmp(p)) + return false; + return true; + } + + template <typename I, typename J> + oln_plain(I) + binary_reconstruction_loop(const Image_with_Nbh<I>& marker, + const Binary_Image<J>& mask) + { + oln_plain(I) output; + prepare(output, with, marker); + + accumulator::max_<oln_value(I)> max; + + // first pass + oln_fwd_piter(I) p(marker.points()); + for_all(p) + output(p) = level::local_sup(max, marker, p) and mask(p); + + // second pass + oln_bkd_piter(I) p2(marker.points()); + for_all(p2) + output(p2) = level::local_inf(max, marker, p2) and mask(p2); + + return output; + } + + template <typename I , typename J> + void // FIXME : Slow impl. + binary_reconstruction_(const Image_with_Nbh<I>& marker, + const Binary_Image<J>& mask) + { + oln_plain(I) tmp = level::clone(marker); + + while ( not stability(marker, tmp) ) + { + level::fill(inplace(exact(marker).image()), tmp); + tmp = binary_reconstruction_loop(marker, mask); + } + + level::fill(inplace(exact(marker).image()), tmp); + } + + } // end of namespace oln::morpho::impl + + template <typename I , typename J> + void + binary_reconstruction(Binary_Image<I>& marker, + const Binary_Image<J>& mask) + { + impl::binary_reconstruction_(marker + c4, mask); + } + +# endif // ! OLN_INCLUDE_ONLY + + } // end of namespace oln::morpho + +} // end of namespace oln + + +#endif // ! OLN_MORPHO_BINARY_RECONSTRUCTION_HH Index: oln/morpho/fast_binary_reconstruction.hh Index: oln/morpho/cc_tarjan_v1.hh --- oln/morpho/cc_tarjan_v1.hh (revision 972) +++ oln/morpho/cc_tarjan_v1.hh (working copy) @@ -54,7 +54,8 @@ namespace impl { - template <typename I> + template <typename I> // FIXME : template< op_<I, extended_by, N>, + // typename I, Typename N> ? struct cc_tarjan_ { typedef oln_point(I) point; @@ -128,7 +129,7 @@ { point r = find_root(n); if (r != p) - parent(r) = p; + parent(r) = p5A5A; } }; Index: oln/morpho/binary_reconstruction_v1.hh --- oln/morpho/binary_reconstruction_v1.hh (revision 0) +++ oln/morpho/binary_reconstruction_v1.hh (revision 0) @@ -0,0 +1,122 @@ +// 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 OLN_MORPHO_BINARY_RECONSTRUCTION_HH +# define OLN_MORPHO_BINARY_RECONSTRUCTION_HH + +# include <oln/core/concept/image.hh> +# include <oln/accumulator/max.hh> +# include <oln/level/clone.hh> +# include <oln/level/fill.hh> +# include <oln/level/local_inf.hh> +# include <oln/level/local_sup.hh> + +namespace oln +{ + + namespace morpho + { + + template <typename I , typename J> + void + binary_reconstruction(const Binary_Image<I>& marker, + const Binary_Image<J>& mask); + +# ifndef OLN_INCLUDE_ONLY + + namespace impl + { + + template <typename I> + bool + stability(const Image_with_Nbh<I>& marker, + oln_plain(I)& tmp) + { + oln_piter(I) p(marker.points()); + for_all(p) + if (marker(p) != tmp(p)) + return false; + return true; + } + + template <typename I, typename J> + oln_plain(I) + binary_reconstruction_loop(const Image_with_Nbh<I>& marker, + const Binary_Image<J>& mask) + { + oln_plain(I) output; + prepare(output, with, marker); + + accumulator::max_<oln_value(I)> max; + + // first pass + oln_fwd_piter(I) p(marker.points()); + for_all(p) + output(p) = level::local_sup(max, marker, p) and mask(p); + + // second pass + oln_bkd_piter(I) p2(marker.points()); + for_all(p2) + output(p2) = level::local_inf(max, marker, p2) and mask(p2); + + return output; + } + + template <typename I , typename J> + void // FIXME : Slow impl. + binary_reconstruction_(const Image_with_Nbh<I>& marker, + const Binary_Image<J>& mask) + { + oln_plain(I) tmp = level::clone(marker); + + while ( not stability(marker, tmp) ) + { + level::fill(inplace(exact(marker).image()), tmp); + tmp = binary_reconstruction_loop(marker, mask); + } + + level::fill(inplace(exact(marker).image()), tmp); + } + + } // end of namespace oln::morpho::impl + + template <typename I , typename J> + void + binary_reconstruction(Binary_Image<I>& marker, + const Binary_Image<J>& mask) + { + impl::binary_reconstruction_(marker + c4, mask); + } + +# endif // ! OLN_INCLUDE_ONLY + + } // end of namespace oln::morpho + +} // end of namespace oln + + +#endif // ! OLN_MORPHO_BINARY_RECONSTRUCTION_HH Index: oln/level/local_sup.hh --- oln/level/local_sup.hh (revision 972) +++ oln/level/local_sup.hh (working copy) @@ -68,7 +68,7 @@ const oln_point(I)& p) { f.init_with(input(p)); - oln_niter(I) n(p, input); + oln_niter(I) n(input, p); for_all(n) if (n > p) f(input(n)); @@ -86,7 +86,7 @@ f.init_with(input(p)); if (f.value() == true) return true; - oln_niter(I) n(p, input); + oln_niter(I) n(input, p); for_all(n) if (n > p) { @@ -106,7 +106,7 @@ const oln_point(I)& p) { f.init_with(input(p)); - oln_niter(I) n(p, input); + oln_niter(I) n(input, p); for_all(n) if (n > p) { Index: oln/level/local_inf.hh --- oln/level/local_inf.hh (revision 972) +++ oln/level/local_inf.hh (working copy) @@ -68,7 +68,7 @@ const oln_point(I)& p) { f.init_with(input(p)); - oln_niter(I) n(p, input); + oln_niter(I) n(input, p); for_all(n) if (n < p) f(input(n)); @@ -86,7 +86,7 @@ f.init_with(input(p)); if (f.value() == true) return true; - oln_niter(I) n(p, input); + oln_niter(I) n(input, p); for_all(n) if (n < p) { @@ -106,7 +106,7 @@ const oln_point(I)& p) { f.init_with(input(p)); - oln_niter(I) n(p, input); + oln_niter(I) n(input, p); for_all(n) if (n < p) { Index: oln/canvas/union_find.hh --- oln/canvas/union_find.hh (revision 0) +++ oln/canvas/union_find.hh (revision 0) @@ -0,0 +1,76 @@ +// 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. + +#include <oln/core/concept/image.hh> + +#ifndef OLN_CANVAS_UNION_FIND_HH +# define OLN_CANVAS_UNION_FIND_HH + +namespace canvas +{ + + template <template <class> class F, + typename I> + void union_find(F<I> fun) + { + fun.init(); + + // first pass + oln_bkd_piter(I) p1(fun.f.points()); + for_all(p1) + { + fun.parent(p1) = p1; + if (fun.f(p) == true) + { + oln_niter(I) n(f, p); + for_all(n) + { + if (is_processed(n)) + if (f.condition_bck(p1, n)) + fun.first_pass_body(p1); + } + } + } + + // second pass + oln_fwd_piter(I) p2(fun.f.points()); + for_all(p2) + { + if (fun.f(p2) == true) + if (fun.condition_fwd(p2)) + { + fun.second_pass_body(p2); + } + } + + fun.final(); + } + +} + + +#endif // ! OLN_CANVAS_UNION_FIND_HH Index: oln/canvas/two_pass.hh --- oln/canvas/two_pass.hh (revision 972) +++ oln/canvas/two_pass.hh (working copy) @@ -5,8 +5,8 @@ // 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 +// 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. // @@ -60,7 +60,7 @@ namespace v2 // Data owned by f but not input. { template <typename F, typename I> - void two_pass(F fun, I f) + void two_pass(F& fun, I f) { // mlc::assert_< mlc_is_a(I, Image) >::check(); @@ -83,7 +83,7 @@ namespace v3 // Auxiliar data given as argument. { template <typename F, typename I, typename A> - void two_pass(F fun, I f, A aux) + void two_pass(F fun, I f, A& aux) { // mlc::assert_< mlc_is_a(I, Image) >::check(); @@ -107,38 +107,44 @@ namespace v4 // Via Inheritance. { - template <typename I> + template <typename Exact> struct two_pass { + void init() + { + this->exact().impl_init(); + } - const I& f; - - - - void init(); - - void final(); + void final() + { + this->exact().impl_final(); + } - void first_pass_body(const oln_point(I)& p); + void first_pass_body(const oln_point(I)& p) + { + this->exact().impl_first_pass_body(p); + } - void second_pass_body(const oln_point(I)& p); + void second_pass_body(const oln_point(I)& p) + { + this->exact().impl_second_pass_body(p); + } void run() { init(f); // first pass - oln_bkd_piter(I) p1(f.points()); + oln_bkd_piter(typename Exact::I) p1(f.points()); for_all(p1) first_pass_body(p1); // second pass - oln_fwd_piter(I) p2(f.points()); + oln_fwd_piter(typename Exact::I) p2(f.points()); for_all(p2) second_pass_body(p2); final(f); - } };