- Olena-patches

3032: Comment, beautify, strengthen n_cmpt5.
by Ugo Jardonnet 12 Dec '08

12 Dec '08

https://svn.lrde.epita.fr/svn/oln/trunk/milena/sandbox Index: ChangeLog from Ugo Jardonnet <jardonnet(a)lrde.epita.fr> Comment, beautify, strengthen n_cmpt5. * jardonnet/n_cmpt/n_cmpt5.hh: Comment. Add assertions. * jardonnet/n_cmpt/Makefile: Fix rules. Makefile | 10 ++++---- n_cmpt5.hh | 72 +++++++++++++++++++++++++++++++++++++------------------------ 2 files changed, 49 insertions(+), 33 deletions(-) Index: jardonnet/n_cmpt/n_cmpt5.hh --- jardonnet/n_cmpt/n_cmpt5.hh (revision 3031) +++ jardonnet/n_cmpt/n_cmpt5.hh (working copy) @@ -46,7 +46,7 @@ { template < typename I > - void n_cmpt3(const I& (((((((ima)))))))); + void n_cmpt5(const I& (((((((ima)))))))); # ifndef MLN_INCLUDE_ONLY @@ -67,17 +67,12 @@ n_cmpt3(const I& ima, const N& nbh, unsigned lambda) { - unsigned label; - std::cout << "/ima/" << std::endl; debug::println(ima); - /* - // get /ima/ regional minima - mln_ch_value(I, unsigned) min = labeling::regional_minima(ima, nbh, label); - std::cout << "/ima/ regional minima" << std::endl; - debug::println(min); -*/ + // compute volume image + //--------------------- + typedef p_array<mln_psite(I)> S; typedef mln_ch_value(I,unsigned) V; typedef accu::volume A; @@ -89,31 +84,41 @@ std::cout << "/volume/" << std::endl; debug::println(volume); + // get /volume/ regional minima + //----------------------------- + + unsigned label; mln_ch_value(I, unsigned) min_v = labeling::regional_minima(volume, nbh, label); std::cout << "/volume/ regional minima" << std::endl; debug::println(min_v); - // tester minima de ima == minima de attr - //mln_assertion(min == min_v); - - mln_ch_value(I, bool) fused; - initialize(fused, volume); - mln::level::fill(fused, false); - // number of minima unsigned cmpts = label; - if (lambda > cmpts) std::cout << "warning : lambda value is to hight." << std::endl; + std::cout << cmpts << std::endl; + + + // two pass algo + //-------------- + + // init fused image + mln_ch_value(I, bool) fused; + initialize(fused, volume); + mln::level::fill(fused, false); + // prepare union find typedef mln_psite(V) P; + //data mln_ch_value(V, accu::volume<V>) data(volume.domain()); + //deja_vu mln_ch_value(V, bool) deja_vu(volume.domain()); mln::level::fill(deja_vu, false); + //parent mln_ch_value(V, P) parent(volume.domain()); { @@ -121,16 +126,14 @@ for_all(p) { parent(p) = p; + + // Mandatory since we propagate fused if (min_v(p) != 0) // p in a reg min of the attribute image fused(p) = true; // ok } } - std::cout << "cmpts | volume_set | " << std::endl; - std::cout << cmpts << " : "; - std::cout << std::endl; - - // union find sur volume + // UNION FIND ON VOLUME mln_fwd_piter(S) p(sp); mln_niter(N) n(nbh, p); for_all(p) @@ -157,14 +160,28 @@ not fused(p)) { parent(r) = p; - // propagate set - fused(p) = true; - //min_v(p) = min_v(r); //FIXME: fusion may happend with a non minima value + // This test is mandatory. Sometimes (--_) points are fused + // tought none of these points belongs to a component (attached + // to a local minima). In this case fused(p) must not be true + // since it can be fused again without removing a component. + // looking if r is fused should be enought. + // This test force minima to be initialized fused. + if (fused(r)) + fused(p) = true; - fused(n) = true; // We cannot mark minima at init ! ... ? + // If I try to fuse with something never fused I am on a plateau. + // not fused(r) => ( volume(r) == volume(p) ) + mln_invariant(fused(r) || volume(r) == volume(p)); + // fused(r) and ( volume(r) == volume(p) ) happen on minima plateau. + + // fused(n) = true; // useless ? probably yes because when we + // want to know that we really fuse component, we look at + // fused(r) not n. + // fused(n) is not an invariant: --_. And it is ok (I think). + // We don't have to retro-propagate fused. - std::cout << "volume " << volume(p) << " - " << cmpts << std::endl; + //std::cout << "volume " << volume(p) << " - " << cmpts << std::endl; debug::println(fused); } } @@ -176,7 +193,6 @@ I iota(ima.domain()); debug::iota(iota); -// step2: std::cout << std::endl; std::cout << "cmpts : " << cmpts << std::endl; Index: jardonnet/n_cmpt/Makefile --- jardonnet/n_cmpt/Makefile (revision 3031) +++ jardonnet/n_cmpt/Makefile (working copy) @@ -25,12 +25,12 @@ debug3: n_cmpt3.hh n_cmpt3.cc g++ -I../../.. -Wall -W -Wextra n_cmpt3.cc -g -g3 -o n_cmpt3 -Debug4: N_cmpt4.hh n_cmpt4.cc - g++ -I../../.. -Wall -W -Wextra n_cmpt4.cc -g -g4 -o n_cmpt4 +Debug4: n_cmpt4.hh n_cmpt4.cc + g++ -I../../.. -Wall -W -Wextra n_cmpt4.cc -g -g3 -o n_cmpt4 -Debug5: N_cmpt5.hh n_cmpt5.cc - g++ -I../../.. -Wall -W -Wextra n_cmpt5.cc -g -g5 -o n_cmpt5 +Debug5: n_cmpt5.hh n_cmpt5.cc + g++ -I../../.. -Wall -W -Wextra n_cmpt5.cc -g -g3 -o n_cmpt5 Debugnwst: nwst.hh nwst.cc - g++ -I../../.. -Wall -W -Wextra nwst.cc -g -g5 -o nwst + g++ -I../../.. -Wall -W -Wextra nwst.cc -g -g3 -o nwst

1 0

3031: Mark bad test in nwst.
by Ugo Jardonnet 11 Dec '08

11 Dec '08

https://svn.lrde.epita.fr/svn/oln/trunk/milena/sandbox Index: ChangeLog from Ugo Jardonnet <ugo.jardonnet(a)lrde.epita.fr> Mark bad test in nwst. * jardonnet/n_cmpt/nwst.hh: Wrong shed test. * jardonnet/n_cmpt/n_cmpt5.hh: Beautify. n_cmpt5.hh | 10 +--------- nwst.hh | 2 +- 2 files changed, 2 insertions(+), 10 deletions(-) Index: jardonnet/n_cmpt/nwst.hh --- jardonnet/n_cmpt/nwst.hh (revision 3030) +++ jardonnet/n_cmpt/nwst.hh (working copy) @@ -157,7 +157,7 @@ } // mark limit point - if (parent(p) != parent(n)) + if (parent(p) != parent(n)) // wrong wst(p) = literal::red; } } Index: jardonnet/n_cmpt/n_cmpt5.hh --- jardonnet/n_cmpt/n_cmpt5.hh (revision 3030) +++ jardonnet/n_cmpt/n_cmpt5.hh (working copy) @@ -186,15 +186,7 @@ mln_bkd_piter(S) p(sp); for_all(p) if (parent(p) == p) // p is root. - { - //FIXME: if minimas have same values. Components are not visible. - //Using min_v instead of ima does not really fix it. - //see propagation of min_v values. - //Maybe this is only a part of the problem: - // n_cmpt4 claims that n components remain, - // which is visually false. - output(p) = iota(p) * 10; //(p[0] + p[1]) * 10; - } + output(p) = iota(p) * 10; else output(p) = output(parent(p)); }

1 0

3030: Update nwst.
by Ugo Jardonnet 11 Dec '08

11 Dec '08

https://svn.lrde.epita.fr/svn/oln/trunk/milena/sandbox Index: ChangeLog from Ugo Jardonnet <jardonnet(a)lrde.epita.fr> Update nwst. * jardonnet/n_cmpt/nwst.hh: Update. Mark local minima. * jardonnet/n_cmpt/wst.cc: New. Add wst ref. nwst.hh | 19 +++++++++++-------- wst.cc | 46 ++++++++++++++++++++++++++++++++++++++++++++++ 2 files changed, 57 insertions(+), 8 deletions(-) Index: jardonnet/n_cmpt/nwst.hh --- jardonnet/n_cmpt/nwst.hh (revision 3029) +++ jardonnet/n_cmpt/nwst.hh (working copy) @@ -81,9 +81,11 @@ // sort ima psites typedef mln_psite(I) P; typedef p_array S; - S sp = level::sort_psites_decreasing(ima); - + S sp = level::sort_psites_increasing(ima); + // init watershed image + mln_ch_value(I, value::rgb8) wst(ima.domain()); + mln::level::fill(wst, literal::black); // number of minima unsigned cmpts = label; @@ -107,7 +109,10 @@ { parent(p) = p; if (min(p) != 0) // p in a reg min of the attribute image + { fused(p) = true; // ok + wst(p) = literal::red; + } } } @@ -115,10 +120,6 @@ std::cout << cmpts << " : "; std::cout << std::endl; - // init watershed image - mln_ch_value(I, value::rgb8) wst(ima.domain()); - mln::level::fill(wst, literal::black); - // union find mln_fwd_piter(S) p(sp); mln_niter(N) n(nbh, p); @@ -138,8 +139,6 @@ if (cmpts >= lambda) // union is still alowed if (fused(p)) // p already belong to a cmpt (fused for an another n) cmpts--; - else - wst(p) = literal::red; if (cmpts >= lambda || ima(r) == ima(p) || @@ -156,6 +155,10 @@ std::cout << "ima " << ima(p) << " - " << cmpts << std::endl; debug::println(fused); } + + // mark limit point + if (parent(p) != parent(n)) + wst(p) = literal::red; } } } Index: jardonnet/n_cmpt/wst.cc --- jardonnet/n_cmpt/wst.cc (revision 0) +++ jardonnet/n_cmpt/wst.cc (revision 0) @@ -0,0 +1,46 @@ + +#include <iostream> + +#include <mln/core/image/image2d.hh> +#include <mln/core/alias/neighb2d.hh> +#include <mln/value/int_u8.hh> + +#include <mln/make/image.hh> +#include <mln/core/alias/neighb1d.hh> + +#include <mln/morpho/meyer_wst.hh> + +#include <mln/io/pgm/load.hh> +#include <mln/io/pgm/save.hh> + +#include "nwst.hh" + +using namespace mln; +using namespace mln::value; + +bool usage(int argc, char ** argv) +{ + if (argc != 3) + { + std::cout << argv[0] << " ima.pgm lambda" << std::endl; + return false; + } + return true; +} + +int main(int argc, char ** argv) +{ + if (not usage(argc,argv)) + return 1; + + image2d<int_u8> ima; + io::pgm::load(ima, argv[1]); + unsigned lambda = atoi(argv[2]); + + ima(point2d(0,3)) = 106; + + int_u8 label; + io::pgm::save(morpho::meyer_wst(ima, c4(), label), + "meyer_wst.ppm"); + std::cout << label << std::endl; +}

1 0

3029: Experimental nwst.
by Ugo Jardonnet 11 Dec '08

11 Dec '08

https://svn.lrde.epita.fr/svn/oln/trunk/milena/sandbox Index: ChangeLog from Ugo Jardonnet <ugo.jardonnet(a)lrde.epita.fr> Experimental nwst. * jardonnet/n_cmpt/nwst.hh, * jardonnet/n_cmpt/nwst.cc: Test N-watershed. * jardonnet/n_cmpt/n_cmpt4.cc, * jardonnet/n_cmpt/n_cmpt4.hh: Minor fix. * jardonnet/n_cmpt/Makefile: Add nwst rules. Makefile | 6 + n_cmpt4.cc | 2 n_cmpt4.hh | 2 nwst.cc | 48 ++++++++++++++ nwst.hh | 197 +++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++ 5 files changed, 253 insertions(+), 2 deletions(-) Index: jardonnet/n_cmpt/nwst.cc --- jardonnet/n_cmpt/nwst.cc (revision 0) +++ jardonnet/n_cmpt/nwst.cc (revision 0) @@ -0,0 +1,48 @@ + +#include <iostream> + +#include <mln/core/image/image2d.hh> +#include <mln/core/alias/neighb2d.hh> +#include <mln/value/int_u8.hh> + +#include <mln/make/image.hh> +#include <mln/core/alias/neighb1d.hh> + +#include <mln/io/pgm/load.hh> +#include <mln/io/pgm/save.hh> + +#include "nwst.hh" + +using namespace mln; +using namespace mln::value; + +bool usage(int argc, char ** argv) +{ + if (argc != 3) + { + std::cout << argv[0] << " ima.pgm lambda" << std::endl; + return false; + } + return true; +} + +int main(int argc, char ** argv) +{ + if (not usage(argc,argv)) + return 1; + + image2d<int_u8> ima; + io::pgm::load(ima, argv[1]); + unsigned lambda = atoi(argv[2]); + + ima(point2d(0,3)) = 106; + + int_u8 tab[] = {2,3,1,0,2,3,4,5,1,1,0,5,6,8,7,1,1,2,3,4}; + image1d<int_u8> ima1= make::image(tab); + + // std::cout << "/output/" << std::endl; + // debug::println(n_cmpt::n_cmpt3(ima1, c2(), lambda)); + + io::pgm::save(n_cmpt::n_cmpt3(ima, c4(), lambda), + "out.pgm"); +} Index: jardonnet/n_cmpt/n_cmpt4.cc --- jardonnet/n_cmpt/n_cmpt4.cc (revision 3028) +++ jardonnet/n_cmpt/n_cmpt4.cc (working copy) @@ -43,6 +43,6 @@ // std::cout << "/output/" << std::endl; // debug::println(n_cmpt::n_cmpt3(ima1, c2(), lambda)); - io::pgm::save(n_cmpt::n_cmpt3(ima, c4(), lambda), + io::pgm::save(n_cmpt::n_cmpt4(ima, c4(), lambda), "out.pgm"); } Index: jardonnet/n_cmpt/nwst.hh --- jardonnet/n_cmpt/nwst.hh (revision 0) +++ jardonnet/n_cmpt/nwst.hh (revision 0) @@ -0,0 +1,197 @@ +// Copyright (C) 2008 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 MLN_N_CMPT3_HH +# define MLN_N_CMPT3_HH + +# include <mln/labeling/regional_minima.hh> +# include <mln/core/alias/neighb2d.hh> +# include <mln/util/set.hh> + +# include <mln/debug/println.hh> +# include <mln/debug/iota.hh> + +# include <mln/literal/colors.hh> +# include <mln/io/ppm/save.hh> + +# include <mln/accu/volume.hh> +# include <mln/morpho/tree/data.hh> +# include <mln/morpho/tree/compute_attribute_image.hh> + +namespace mln +{ + + namespace n_cmpt + { + + template < typename I > + void n_cmpt3(const I& (((((((ima)))))))); + +# ifndef MLN_INCLUDE_ONLY + + template <typename I> + 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 I, typename N> + I + n_cmpt3(const I& ima, const N& nbh, + unsigned lambda) + { + unsigned label; + + std::cout << "/ima/" << std::endl; + debug::println(ima); + + // get /ima/ regional minima + mln_ch_value(I, unsigned) min = labeling::regional_minima(ima, nbh, label); + + // sort ima psites + typedef mln_psite(I) P; + typedef p_array S; + S sp = level::sort_psites_decreasing(ima); + + + + // number of minima + unsigned cmpts = label; + + if (lambda > cmpts) + std::cout << "warning : lambda value is to hight." << std::endl; + + //// prepare union find + // fused + mln_ch_value(I, bool) fused; + initialize(fused, ima); + mln::level::fill(fused, false); + // deja_vu + mln_ch_value(I, bool) deja_vu(ima.domain()); + mln::level::fill(deja_vu, false); + //parent + mln_ch_value(I, P) parent(ima.domain()); + { + mln_fwd_piter(S) p(sp); + for_all(p) + { + parent(p) = p; + if (min(p) != 0) // p in a reg min of the attribute image + fused(p) = true; // ok + } + } + + std::cout << "cmpts | volume_set | " << std::endl; + std::cout << cmpts << " : "; + std::cout << std::endl; + + // init watershed image + mln_ch_value(I, value::rgb8) wst(ima.domain()); + mln::level::fill(wst, literal::black); + + // union find + mln_fwd_piter(S) p(sp); + mln_niter(N) n(nbh, p); + for_all(p) + { + std::cout << p << std::endl; + for_all(n) + { + if (ima.domain().has(n) && deja_vu(n)) + { + //do_union(n, p); + P r = find_root(parent, n); + if (r != p) + { + // One cmpt less if + if (ima(r) != ima(p)) // r and p have differerent volumes + if (cmpts >= lambda) // union is still alowed + if (fused(p)) // p already belong to a cmpt (fused for an another n) + cmpts--; + else + wst(p) = literal::red; + + if (cmpts >= lambda || + ima(r) == ima(p) || + not fused(p)) + { + parent(r) = p; + // propagate set + fused(p) = true; + + //min_v(p) = min_v(r); //FIXME: fusion may happend with a non minima value + + fused(n) = true; // We cannot mark minima at init ! ... ? + + std::cout << "ima " << ima(p) << " - " << cmpts << std::endl; + debug::println(fused); + } + } + } + } + deja_vu(p) = true; + } + + I iota(ima.domain()); + debug::iota(iota); + + io::ppm::save(wst, "wst.ppm"); + +// step2: + std::cout << std::endl; + std::cout << "cmpts : " << cmpts << std::endl; + + // second pass + I output(ima.domain()); + { + mln_bkd_piter(S) p(sp); + for_all(p) + if (parent(p) == p) // p is root. + { + output(p) = iota(p) * 10; + } + else + output(p) = output(parent(p)); + } + + return output; + } + + } // end of namespace n_cmpt + +# endif // ! MLN_INCLUDE_ONLY + +} // end of namespace mln + +#endif /* MLN_N_CMPT3_HH */ + Index: jardonnet/n_cmpt/n_cmpt4.hh --- jardonnet/n_cmpt/n_cmpt4.hh (revision 3028) +++ jardonnet/n_cmpt/n_cmpt4.hh (working copy) @@ -63,7 +63,7 @@ template < typename I, typename N> I - n_cmpt3(const I& ima, const N& nbh, + n_cmpt4(const I& ima, const N& nbh, unsigned lambda) { unsigned label; Index: jardonnet/n_cmpt/Makefile --- jardonnet/n_cmpt/Makefile (revision 3028) +++ jardonnet/n_cmpt/Makefile (working copy) @@ -13,6 +13,9 @@ n_cmpt5: n_cmpt5.hh n_cmpt5.cc g++ -I../../.. -Wall -W -Wextra n_cmpt5.cc -DNDEBUG -O1 -o n_cmpt5 +nwst: nwst.hh nwst.cc + g++ -I../../.. -Wall -W -Wextra nwst.cc -DNDEBUG -O1 -o nwst + debug: n_cmpt.hh n_cmpt.cc g++ -I../../.. -Wall -W -Wextra n_cmpt.cc -g -g3 -o n_cmpt @@ -28,3 +31,6 @@ Debug5: N_cmpt5.hh n_cmpt5.cc g++ -I../../.. -Wall -W -Wextra n_cmpt5.cc -g -g5 -o n_cmpt5 +Debugnwst: nwst.hh nwst.cc + g++ -I../../.. -Wall -W -Wextra nwst.cc -g -g5 -o nwst +

1 0

3028: Work around different class but same parent(p) value.
by Ugo Jardonnet 11 Dec '08

11 Dec '08

https://svn.lrde.epita.fr/svn/oln/trunk/milena/sandbox Index: ChangeLog from Ugo Jardonnet <ugo.jardonnet(a)lrde.epita.fr> Work around different class but same parent(p) value. * jardonnet/n_cmpt/n_cmpt5.cc: Same as v4. * jardonnet/n_cmpt/n_cmpt5.hh: Same as v4. Use iota image. * jardonnet/n_cmpt/Makefile: Add n_cmpt5 rules. * jardonnet/TODO: Cleanup. TODO | 27 ------ n_cmpt/Makefile | 8 +- n_cmpt/n_cmpt5.cc | 48 ++++++++++++ n_cmpt/n_cmpt5.hh | 212 ++++++++++++++++++++++++++++++++++++++++++++++++++++++ 4 files changed, 267 insertions(+), 28 deletions(-) Index: jardonnet/n_cmpt/n_cmpt5.cc --- jardonnet/n_cmpt/n_cmpt5.cc (revision 0) +++ jardonnet/n_cmpt/n_cmpt5.cc (revision 0) @@ -0,0 +1,48 @@ + +#include <iostream> + +#include <mln/core/image/image2d.hh> +#include <mln/core/alias/neighb2d.hh> +#include <mln/value/int_u8.hh> + +#include <mln/make/image.hh> +#include <mln/core/alias/neighb1d.hh> + +#include <mln/io/pgm/load.hh> +#include <mln/io/pgm/save.hh> + +#include "n_cmpt5.hh" + +using namespace mln; +using namespace mln::value; + +bool usage(int argc, char ** argv) +{ + if (argc != 3) + { + std::cout << argv[0] << " ima.pgm lambda" << std::endl; + return false; + } + return true; +} + +int main(int argc, char ** argv) +{ + if (not usage(argc,argv)) + return 1; + + image2d<int_u8> ima; + io::pgm::load(ima, argv[1]); + unsigned lambda = atoi(argv[2]); + + ima(point2d(0,3)) = 106; + + int_u8 tab[] = {2,3,1,0,2,3,4,5,1,1,0,5,6,8,7,1,1,2,3,4}; + image1d<int_u8> ima1= make::image(tab); + + // std::cout << "/output/" << std::endl; + // debug::println(n_cmpt::n_cmpt3(ima1, c2(), lambda)); + + io::pgm::save(n_cmpt::n_cmpt3(ima, c4(), lambda), + "out.pgm"); +} Index: jardonnet/n_cmpt/n_cmpt5.hh --- jardonnet/n_cmpt/n_cmpt5.hh (revision 0) +++ jardonnet/n_cmpt/n_cmpt5.hh (revision 0) @@ -0,0 +1,212 @@ +// Copyright (C) 2008 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 MLN_N_CMPT3_HH +# define MLN_N_CMPT3_HH + +# include <mln/labeling/regional_minima.hh> +# include <mln/core/alias/neighb2d.hh> +# include <mln/util/set.hh> + +# include <mln/debug/println.hh> +# include <mln/debug/iota.hh> + +# include <mln/accu/volume.hh> +# include <mln/morpho/tree/data.hh> +# include <mln/morpho/tree/compute_attribute_image.hh> + +namespace mln +{ + + namespace n_cmpt + { + + template < typename I > + void n_cmpt3(const I& (((((((ima)))))))); + +# ifndef MLN_INCLUDE_ONLY + + template <typename I> + 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 I, typename N> + I + n_cmpt3(const I& ima, const N& nbh, + unsigned lambda) + { + unsigned label; + + std::cout << "/ima/" << std::endl; + debug::println(ima); + /* + // get /ima/ regional minima + mln_ch_value(I, unsigned) min = labeling::regional_minima(ima, nbh, label); + std::cout << "/ima/ regional minima" << std::endl; + debug::println(min); +*/ + // compute volume image + typedef p_array<mln_psite(I)> S; + typedef mln_ch_value(I,unsigned) V; + typedef accu::volume A; + + S sp = level::sort_psites_decreasing(ima); + morpho::tree::data<I,S> t(ima, sp, nbh); + V volume = morpho::tree::compute_attribute_image(A(), t); + sp = level::sort_psites_increasing(volume); + std::cout << "/volume/" << std::endl; + debug::println(volume); + + // get /volume/ regional minima + mln_ch_value(I, unsigned) min_v = labeling::regional_minima(volume, nbh, label); + std::cout << "/volume/ regional minima" << std::endl; + debug::println(min_v); + + // tester minima de ima == minima de attr + //mln_assertion(min == min_v); + + mln_ch_value(I, bool) fused; + initialize(fused, volume); + mln::level::fill(fused, false); + + // number of minima + unsigned cmpts = label; + + if (lambda > cmpts) + std::cout << "warning : lambda value is to hight." << std::endl; + + // prepare union find + typedef mln_psite(V) P; + //data + mln_ch_value(V, accu::volume<V>) data(volume.domain()); + //deja_vu + mln_ch_value(V, bool) deja_vu(volume.domain()); + mln::level::fill(deja_vu, false); + //parent + mln_ch_value(V, P) parent(volume.domain()); + { + mln_fwd_piter(S) p(sp); + for_all(p) + { + parent(p) = p; + if (min_v(p) != 0) // p in a reg min of the attribute image + fused(p) = true; // ok + } + } + + std::cout << "cmpts | volume_set | " << std::endl; + std::cout << cmpts << " : "; + std::cout << std::endl; + + // union find sur volume + mln_fwd_piter(S) p(sp); + mln_niter(N) n(nbh, p); + for_all(p) + { + std::cout < lambda) + // goto step2; + for_all(n) + { + if (volume.domain().has(n) && deja_vu(n)) + { + //do_union(n, p); + P r = find_root(parent, n); + if (r != p) + { + // One cmpt less if + if (volume(r) != volume(p)) // r and p have differerent volumes + if (fused(p)) // p already belong to a cmpt (fused for an another n) + if (cmpts >= lambda) // union is still alowed + cmpts--; + + if (cmpts >= lambda || + volume(r) == volume(p) || + not fused(p)) + { + parent(r) = p; + // propagate set + fused(p) = true; + + //min_v(p) = min_v(r); //FIXME: fusion may happend with a non minima value + + fused(n) = true; // We cannot mark minima at init ! ... ? + + std::cout << "volume " << volume(p) << " - " << cmpts << std::endl; + debug::println(fused); + } + } + } + } + deja_vu(p) = true; + } + + I iota(ima.domain()); + debug::iota(iota); + +// step2: + std::cout << std::endl; + std::cout << "cmpts : " << cmpts << std::endl; + + // second pass + I output(ima.domain()); + { + mln_bkd_piter(S) p(sp); + for_all(p) + if (parent(p) == p) // p is root. + { + //FIXME: if minimas have same values. Components are not visible. + //Using min_v instead of ima does not really fix it. + //see propagation of min_v values. + //Maybe this is only a part of the problem: + // n_cmpt4 claims that n components remain, + // which is visually false. + output(p) = iota(p) * 10; //(p[0] + p[1]) * 10; + } + else + output(p) = output(parent(p)); + } + + return output; + } + + } // end of namespace n_cmpt + +# endif // ! MLN_INCLUDE_ONLY + +} // end of namespace mln + +#endif /* MLN_N_CMPT3_HH */ + Index: jardonnet/n_cmpt/Makefile --- jardonnet/n_cmpt/Makefile (revision 3027) +++ jardonnet/n_cmpt/Makefile (working copy) @@ -10,6 +10,9 @@ n_cmpt4: n_cmpt4.hh n_cmpt4.cc g++ -I../../.. -Wall -W -Wextra n_cmpt4.cc -DNDEBUG -O1 -o n_cmpt4 +n_cmpt5: n_cmpt5.hh n_cmpt5.cc + g++ -I../../.. -Wall -W -Wextra n_cmpt5.cc -DNDEBUG -O1 -o n_cmpt5 + debug: n_cmpt.hh n_cmpt.cc g++ -I../../.. -Wall -W -Wextra n_cmpt.cc -g -g3 -o n_cmpt @@ -19,6 +22,9 @@ debug3: n_cmpt3.hh n_cmpt3.cc g++ -I../../.. -Wall -W -Wextra n_cmpt3.cc -g -g3 -o n_cmpt3 -debug4: n_cmpt4.hh n_cmpt4.cc +Debug4: N_cmpt4.hh n_cmpt4.cc g++ -I../../.. -Wall -W -Wextra n_cmpt4.cc -g -g4 -o n_cmpt4 +Debug5: N_cmpt5.hh n_cmpt5.cc + g++ -I../../.. -Wall -W -Wextra n_cmpt5.cc -g -g5 -o n_cmpt5 + Index: jardonnet/TODO --- jardonnet/TODO (revision 3027) +++ jardonnet/TODO (working copy) @@ -4,30 +4,3 @@ - gaussian.cc: In function 'int main(int, char*)': gaussian.cc:22: error: no match for 'operator==' in 'img == out' -- - -Check gaussian - -- - - -adapt test for threshold (old thresholding) -- - - -- - -write -trans : vec --> quat - v |-> m = trans(t) - -- - -io/all.hh cass� - -- - -Mettre au clair center, mean ... - -- - - -algebra::to_point ne devrait pas etre dans algebra puisqu'il - est utile pour passer d'un point<int> vers point<float> -move it in convert - -- - -ecrire cov.hh. quoi en argument (p_array, std::set, std::vector?) \ No newline at end of file

1 0

3027: Fix missing lowq test for morpho general with any elt.
by Thierry Geraud 10 Dec '08

10 Dec '08

https://svn.lrde.epita.fr/svn/oln/trunk/milena Index: ChangeLog from Thierry Geraud <thierry.geraud(a)lrde.epita.fr> Fix missing lowq test for morpho general with any elt. * mln/morpho/general.spe.hh (general_dispatch_wrt_win): Fix missing test about lowq. * mln/labeling/flat_zones.hh: Upgrade doc style. * mln/util/set.hh: Likewise. labeling/flat_zones.hh | 14 +-- morpho/general.spe.hh | 3 util/set.hh | 193 ++++++++++++++++++++++++------------------------- 3 files changed, 105 insertions(+), 105 deletions(-) Index: mln/morpho/general.spe.hh --- mln/morpho/general.spe.hh (revision 3026) +++ mln/morpho/general.spe.hh (working copy) @@ -350,6 +350,9 @@ && mln_is_simple_window(W)::value && + mlc_equal(mln_trait_image_quant(I), + trait::image::quant::low)::value + && mlc_not_equal(mln_trait_image_value_storage(I), trait::image::value_storage::disrupted)::value }; return general_dispatch_wrt_arbitrary_win(metal::bool_<test>(), Index: mln/labeling/flat_zones.hh --- mln/labeling/flat_zones.hh (revision 3026) +++ mln/labeling/flat_zones.hh (working copy) @@ -44,13 +44,13 @@ namespace labeling { - /*! Connected component labeling of the flat zones of an image. - * - * \param[in] input The input image. - * \param[in] nbh The connexity of the flat zones. - * \param[out] nlabels The number of labels. - * \return The label image. - */ + /// Connected component labeling of the flat zones of an image. + /// + /// \param[in] input The input image. + /// \param[in] nbh The connexity of the flat zones. + /// \param[out] nlabels The number of labels. + /// \return The label image. + /// template <typename I, typename N, typename L> mln_ch_value(I, L) flat_zones(const Image& input, const Neighborhood<N>& nbh, L& nlabels); Index: mln/util/set.hh --- mln/util/set.hh (revision 3026) +++ mln/util/set.hh (working copy) @@ -1,4 +1,5 @@ // 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 @@ -28,14 +29,13 @@ #ifndef MLN_UTIL_SET_HH # define MLN_UTIL_SET_HH -/*! \file mln/util/set.hh - * - * \brief Definition of mln::util::set. - * - * \todo Clean code and test! - * - * \todo Zed: Group methods into 2 categories: when frozen, when not. - */ +/// \file mln/util/set.hh +/// +/// Definition of mln::util::set. +/// +/// \todo Clean code and test! +/// +/// \todo Zed: Group methods into 2 categories: when frozen, when not. # include <vector> # include <set> @@ -58,27 +58,24 @@ template <typename T> class set_bkd_iter; - /*! \brief An "efficient" mathematical set class. - * - * - * - * This set class is designed to store a mathematical set and to - * present it to the user as a linear array (std::vector). - * - * Elements are stored by copy. Implementation is lazy. - * - * The set has two states: frozen or not. There is an automatic - * switch of state when the user modifies its contents (insert, - * remove, or clear) or access to its contents (op[i]). - * - * The parameter \c T is the element type, which shall not be - * const-qualified. - * - * The unicity of set elements is handled by the mln::util::ord - * mechanism. - * - * \see mln::util::ord - */ + /// \brief An "efficient" mathematical set class. + /// + /// This set class is designed to store a mathematical set and to + /// present it to the user as a linear array (std::vector). + /// + /// Elements are stored by copy. Implementation is lazy. + /// + /// The set has two states: frozen or not. There is an automatic + /// switch of state when the user modifies its contents (insert, + /// remove, or clear) or access to its contents (op[i]). + /// + /// The parameter \c T is the element type, which shall not be + /// const-qualified. + /// + /// The unicity of set elements is handled by the mln::util::ord + /// mechanism. + /// + /// \see mln::util::ord template <typename T> class set : public Object< mln::util::set<T> > { @@ -98,67 +95,67 @@ typedef fwd_eiter eiter; - /*! \brief Insert an element \p elt into the set. - * - * \param[in] elt The element to be inserted. - * - * If \p elt is already in the set, this method is a no-op. - * - * \return The set itself after insertion. - */ + /// \brief Insert an element \p elt into the set. + /// + /// \param[in] elt The element to be inserted. + /// + /// If \p elt is already in the set, this method is a no-op. + /// + /// \return The set itself after insertion. + /// set<T>& insert(const T& elt); - /*! \brief Insert the elements of \p other into the set. - * - * \param[in] other The set containing the elements to be inserted. - * - * \return The set itself after insertion. - */ + /// \brief Insert the elements of \p other into the set. + /// + /// \param[in] other The set containing the elements to be inserted. + /// + /// \return The set itself after insertion. + /// template <typename U> set<T>& insert(const set& other); - /*! \brief Remove an element \p elt into the set. - * - * \param[in] elt The element to be inserted. - * - * If \p elt is already in the set, this method is a no-op. - * - * \return The set itself after suppression. - */ + /// \brief Remove an element \p elt into the set. + /// + /// \param[in] elt The element to be inserted. + /// + /// If \p elt is already in the set, this method is a no-op. + /// + /// \return The set itself after suppression. + /// set<T>& remove(const T& elt); - /*! \brief Empty the set. - * - * All elements contained in the set are destroyed so the set is - * emptied. - * - * \post is_empty() == true - */ + /// \brief Empty the set. + /// + /// All elements contained in the set are destroyed so the set is + /// emptied. + /// + /// \post is_empty() == true + /// void clear(); - /*! \brief Return the number of elements of the set. - */ + /// \brief Return the number of elements of the set. + /// unsigned nelements() const; - /*! \brief Test if the set is empty. - */ + /// \brief Test if the set is empty. + /// bool is_empty() const; - /*! \brief Return the i-th element of the set. - * - * \param[in] i Index of the element to retrieve. - * - * \pre i < nelements() - * - * The element is returned by reference and is constant. - */ + /// \brief Return the i-th element of the set. + /// + /// \param[in] i Index of the element to retrieve. + /// + /// \pre i < nelements() + /// + /// The element is returned by reference and is constant. + /// const T& operator[](unsigned i) const; /// Return the first element of the set. @@ -170,23 +167,23 @@ const T last_element() const; - /*! \brief Test if the object \p elt belongs to the set. - * - * \param[in] elt A possible element of the set. - * - * \return True is \p elt is in the set. - */ + /// \brief Test if the object \p elt belongs to the set. + /// + /// \param[in] elt A possible element of the set. + /// + /// \return True is \p elt is in the set. + /// bool has(const T& elt) const; - /*! \brief Give access to the set elements. - * - * The complexity of this method is O(1). - * - * \post The set is frozen. - * - * \return An array (std::vector) of elements. - */ + /// \brief Give access to the set elements. + /// + /// The complexity of this method is O(1). + /// + /// \post The set is frozen. + /// + /// \return An array (std::vector) of elements. + /// const std::vector<T>& std_vector() const; @@ -202,27 +199,27 @@ private: - /*! \brief Array of elements. - * - * This structure is only updated (if required) when elements - * are accessed. - */ + /// \brief Array of elements. + /// + /// This structure is only updated (if required) when elements + /// are accessed. + /// mutable std::vector<T> v_; - /*! \brief Set of elements. - * - * This structure is always up-to-date w.r.t. the set contents. - */ + /// \brief Set of elements. + /// + /// This structure is always up-to-date w.r.t. the set contents. + /// mutable std::set< T, util::ord<T> > s_; - /*! \brief Freeze the contents of the set (update \a v_ from \a - * s_, then clear s_). - */ + /// \brief Freeze the contents of the set (update \a v_ from \a + /// s_, then clear s_). + /// void freeze_() const; - /*! \brief Unfreeze the contents of the set. - */ + /// \brief Unfreeze the contents of the set. + /// void unfreeze_() const; /// Tell if the set is frozen.

1 0

3026: Add some experimental code about TUFA and regional minima.
by Thierry Geraud 10 Dec '08

10 Dec '08

https://svn.lrde.epita.fr/svn/oln/trunk/milena/sandbox Index: ChangeLog from Thierry Geraud <thierry.geraud(a)lrde.epita.fr> Add some experimental code about TUFA and regional minima. * geraud/tufa_2008: New directory. * geraud/tufa_2008/steps.0.cc: New. * geraud/tufa_2008/compute_a.cc: New. * geraud/tufa_2008/steps.1.cc: New. * geraud/tufa_2008/steps.2.cc: New. * geraud/tufa_2008/closing.cc: New. * geraud/tufa_2008/steps.3.cc: New. * geraud/tufa_2008/opening.cc: New. * geraud/tufa_2008/experiment.cc: New. * geraud/tufa_2008/steps.2b.cc: New. * geraud/tufa_2008/filter.cc: New. * geraud/tufa_2008/wst_f_equal_wst_a.cc: New. * geraud/tufa_2008/closed_gradient.cc: New. * geraud/tufa_2008/fz_count.cc: New. * geraud/tufa_2008/regmin_count.cc: New. closed_gradient.cc | 64 +++++++ closing.cc | 64 +++++++ compute_a.cc | 411 +++++++++++++++++++++++++++++++++++++++++++++++++++ experiment.cc | 138 +++++++++++++++++ filter.cc | 169 ++++++++++++++++++++ fz_count.cc | 159 +++++++++++++++++++ opening.cc | 63 +++++++ regmin_count.cc | 173 +++++++++++++++++++++ steps.0.cc | 170 +++++++++++++++++++++ steps.1.cc | 273 +++++++++++++++++++++++++++++++++ steps.2.cc | 184 ++++++++++++++++++++++ steps.2b.cc | 184 ++++++++++++++++++++++ steps.3.cc | 184 ++++++++++++++++++++++ wst_f_equal_wst_a.cc | 140 +++++++++++++++++ 14 files changed, 2376 insertions(+) Index: geraud/tufa_2008/steps.0.cc --- geraud/tufa_2008/steps.0.cc (revision 0) +++ geraud/tufa_2008/steps.0.cc (revision 0) @@ -0,0 +1,170 @@ +// 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 sandbox/geraud/tufa/steps.cc + +#include <mln/core/image/image2d.hh> +#include <mln/value/int_u8.hh> +#include <mln/io/pgm/load.hh> +#include <mln/debug/println.hh> + +#include <mln/core/site_set/p_array.hh> +#include <mln/level/sort_psites.hh> +#include <mln/core/alias/neighb2d.hh> +#include <mln/morpho/tree/data.hh> + +#include <mln/accu/count.hh> + +#include <mln/morpho/tree/compute_attribute_image.hh> +#include <mln/morpho/closing_area.hh> +#include <mln/level/fill.hh> + + +namespace mln +{ + + template <typename I> + void println_par(const I& par) + { + int nr = par.nrows(), nc = par.ncols(); + for (int r = 0; r < nr; ++r) + { + for (int c = 0; c < nc; ++c) + if (par.at(r,c) == point2d(r,c)) + std::cout << "( ) "; + else + std::cout << par.at(r,c) << ' '; + std::cout << std::endl; + } + } + + template <typename P> + inline + mln_value(P) find_root__(P& par, const mln_value(P)& x) + { + if (par(x) == x) + return x; + else + return par(x) = find_root__(par, par(x)); + } + + + template <typename I, typename A, typename N> + mln_concrete(I) filtering(const I& f, const A& a, const N& nbh, mln_value(A) lambda) + { + typedef p_array<mln_psite(I)> S; + S s = level::sort_psites_increasing(a); + + // s maps increasing attributes. + + mln_concrete(I) out; + initialize(out, f); + + mln_ch_value(I, mln_site(I)) par; + mln_ch_value(I, bool) deja_vu; + { + initialize(par, f); + mln_piter(A) p(par.domain()); + for_all(p) + par(p) = p; + initialize(deja_vu, f); + level::fill(deja_vu, false); + } + + // First pass. + { + mln_site(I) r; + mln_fwd_piter(S) p(s); + mln_niter(N) n(nbh, p); + for_all(p) + { + for_all(n) + if (a.domain().has(n) && deja_vu(n)) + { + r = find_root__(par, n); + if (r != p) + if (f(r) == f(p) || a(r) < lambda) + par(r) = p; // Union. + } + deja_vu(p) = true; + } + } + + // Second pass. + { + mln_bkd_piter(S) p(s); + for_all(p) + if (par(p) == p) + out(p) = f(p); + else + out(p) = out(par(p)); + } + return out; + } + + +} // mln + + + + +int main() +{ + using namespace mln; + using value::int_u8; + + int_u8 n; + + typedef image2d<int_u8> I; + I f; + io::pgm::load(f, "../../../img/fly.pgm"); + debug::println("f =", f); + + debug::println("ref =", morpho::closing_area(f, c4(), 10)); + + typedef p_array<point2d> S; + S s = level::sort_psites_decreasing(f); + + // Children go towards lower levels so leafs are regional minima. + // We get a min-tree so that we can perform morphological closings. + + morpho::tree::data<I,S> t(f, s, c4()); + accu::count< util::pix > attr; + + image2d<unsigned> a = morpho::tree::compute_attribute_image(attr, t); + I g = filtering(f, a, c4(), 10); + debug::println("g =", g); + + { + S s = level::sort_psites_decreasing(g); + morpho::tree::data<I,S> t(g, s, c4()); + image2d<unsigned> a_g = morpho::tree::compute_attribute_image(attr, t); + debug::println("a(f) =", a); + debug::println("a(g) =", a_g); + } + +} Index: geraud/tufa_2008/compute_a.cc --- geraud/tufa_2008/compute_a.cc (revision 0) +++ geraud/tufa_2008/compute_a.cc (revision 0) @@ -0,0 +1,411 @@ +// 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 sandbox/geraud/tufa/compute_a.cc + +#include <mln/core/image/image2d.hh> +#include <mln/core/image/image_if.hh> +#include <mln/pw/all.hh> +#include <mln/core/alias/neighb2d.hh> +#include <mln/value/int_u8.hh> +#include <mln/io/pgm/load.hh> +#include <mln/debug/println.hh> + +#include <mln/core/site_set/p_array.hh> +#include <mln/level/sort_psites.hh> +#include <mln/level/fill.hh> +#include <mln/level/paste.hh> +#include <mln/level/compare.hh> + +#include <mln/morpho/tree/data.hh> +#include <mln/morpho/tree/compute_attribute_image.hh> +#include <mln/labeling/regional_minima.hh> + +#include <mln/accu/count.hh> + + + +namespace mln +{ + + template <typename I> + void println_par(const I& par) + { + int nr = par.nrows(), nc = par.ncols(); + for (int r = 0; r < nr; ++r) + { + for (int c = 0; c < nc; ++c) + if (par.at(r,c) == point2d(r,c)) + std::cout << "( ) "; + else + std::cout << par.at(r,c) << ' '; + std::cout << std::endl; + } + } + + + template <typename P> + inline + mln_value(P) find_root__(P& par, const mln_value(P)& x) + { + if (par(x) == x) + return x; + else + return par(x) = find_root__(par, par(x)); + } + + + + //------------------------------- compute_a + + + + template <typename I, typename N, typename A> + mln_ch_value(I, mln_result(A)) + compute_a(const I& f, const N& nbh, A, unsigned& n_regmins) + { + typedef p_array<mln_psite(I)> S; + S s = level::sort_psites_increasing(f); + // s maps increasing attributes. + + mln_ch_value(I, mln_site(I)) par; + mln_ch_value(I, mln_site(I)) zpar; + mln_ch_value(I, bool) deja_vu, flag; + mln_ch_value(I, A) attr; + + n_regmins = f.domain().nsites(); + + + // Initialization. + { + // parent + initialize(par, f); + initialize(zpar, f); + + // deja_vu + initialize(deja_vu, f); + level::fill(deja_vu, false); + + // flag + initialize(flag, f); + level::fill(flag, true); + + // attr + initialize(attr, f); + } + + + // First Pass. + { + mln_site(I) r; + mln_fwd_piter(S) p(s); + mln_niter(N) n(nbh, p); + for_all(p) + { + // Make-Set. + par(p) = p; + zpar(p) = p; + attr(p).take_as_init(p); + + for_all(n) + if (f.domain().has(n) && deja_vu(n)) + { + r = find_root__(zpar, n); + if (r != p) + { + // Fully compressed union. + zpar(r) = p; + attr(p).take(attr(r)); + + if (f(r) == f(p)) + { + // Weak-Union; only for flat zones. + par(r) = p; + + if (flag(p) == false && flag(r) == false) + { + // Two non-reg-min components merge (same flat + // zone) so we had an extra invalidation. + ++n_regmins; + } + flag(p) = flag(p) && flag(r); + --n_regmins; // So we get the number of flat zones + // minus the non-reg-min flat zones. + } + else + { + mln_invariant(f(r) < f(p)); + if (flag(p) == true) + --n_regmins; // Invalidation. + flag(p) = false; + } + } + } + deja_vu(p) = true; + } + } // end of First Pass. + + + std::cout << "n reg min = " << n_regmins << std::endl; + + + { + unsigned n = 0; + mln_fwd_piter(S) p(s); + for_all(p) + if (par(p) == p && flag(p)) + ++n; + mln_assertion(n == n_regmins); + } + + + // The attr image is not correct on flat zones since there is + // no back-propagation of the attribute value of the component + // root. For instance with f="v v v" we get attr="1 2 3" + // instead of "3 3 3". So a finalization is required. + + mln_ch_value(I, mln_result(A)) a; + initialize(a, f); + level::paste(attr, a); + + // Finalization. + { + mln_bkd_piter(S) p(s); // Reverse. + + unsigned n_non_compressed_par = 0; + for_all(p) + { + a(p) = a(par(p)); + if (par(par(p)) != par(p)) + ++ n_non_compressed_par; + } + std::cout << "n_non_compressed_par = " << n_non_compressed_par << std::endl; + } + + // TODO: compress at least the reg minima! + + + { + image2d<unsigned> regmin; + initialize(regmin, f); + { + unsigned i_regmin = 0; + mln_bkd_piter(S) p(s); + for_all(p) + { + if (par(p) == p) + { + if (flag(p)) + regmin(p) = ++i_regmin; + else + regmin(p) = 0; + } + else + regmin(p) = regmin(par(p)); + } + } + + debug::println("f", f); + + debug::println("flag", flag); + // We can see that some point are at true for components that + // are not reg min; flag is a candidate to be compressed... + + debug::println("regmin", regmin); + + + + // TODO: + + // On veut tester ici dans quel ordre on voit les + // reg min lorsque a croit. Pour tous les points d'un reg min, + // est-ce que le root est vu en premier ? + + + + image2d<bool> seen; + initialize(seen, f); + level::fill(seen, false); + + s = level::sort_psites_increasing(a); + mln_bkd_piter(S) p(s); + for_all(p) + { + if (regmin(p) == 0) + continue; + // p is in a regional minimum. + if (par(p) != p) // A non-root point. + { + mln_assertion(regmin(par(p)) != 0); // Root in a regional minimum. + mln_assertion(regmin(par(p)) == regmin(p)); // and the same as p. + mln_assertion(seen(par(p))); + } + seen(p) = true; + } + debug::println(seen); + +// if (flag(p)) +// std::cout << a(p) << ' ' < +// mln_concrete(I) filtering(const I& f, const A& a, const N& nbh, +// unsigned n_regmins, unsigned n_wanted) +// { +// typedef p_array<mln_psite(I)> S; +// S s = level::sort_psites_increasing(a); + +// // s maps increasing attributes. + +// mln_concrete(I) out; +// initialize(out, f); + +// mln_ch_value(I, mln_site(I)) par; +// mln_ch_value(I, bool) deja_vu, flag; + +// // Initialization. +// { +// initialize(par, f); +// mln_piter(A) p(par.domain()); +// for_all(p) +// par(p) = p; +// initialize(deja_vu, f); +// level::fill(deja_vu, false); + +// // flag +// initialize(flag, f); +// level::fill(flag, true); +// } + + +// int counter = 0; +// // We are trying to count the number of merges of regional minima... + + +// // First Pass. +// { +// mln_site(I) r; +// mln_fwd_piter(S) p(s); +// mln_niter(N) n(nbh, p); +// for_all(p) +// { +// for_all(n) +// if (a.domain().has(n) && deja_vu(n)) +// { +// r = find_root__(par, n); +// if (r != p) +// if (a(r) == a(p)) +// { +// par(r) = p; // Union. +// if (flag(r) == true && flag(p) == true) +// --counter; +// flag(p) = flag(p) && flag(r); +// } +// else // a(r) != a(p) +// { +// if (flag(r) == true && flag(p) == true) +// ++counter; +// mln_invariant(a(p) > a(r)); +// flag(p) = false; +// } +// } +// deja_vu(p) = true; +// } +// std::cout << counter << std::endl; +// } + +// // // Second Pass. +// // { +// // mln_bkd_piter(S) p(s); +// // for_all(p) +// // if (par(p) == p) +// // out(p) = f(p); +// // else +// // out(p) = out(par(p)); +// // } + +// return out; +// } + + + + +} // mln + + + + +int main(int, char* argv[]) +{ + using namespace mln; + using value::int_u8; + + typedef image2d<int_u8> I; + I f; + io::pgm::load(f, argv[1]); + // debug::println(f); + + accu::count<point2d> area; + unsigned n_regmins; + image2d<unsigned> a = compute_a(f, c4(), area, n_regmins); + // debug::println(a); + +// { +// // Test of 'n_regmins'. +// unsigned ref; +// labeling::regional_minima(f, c4(), ref); +// mln_assertion(n_regmins == ref); +// } + +// { +// // Test of 'a'. +// typedef p_array<point2d> S; +// S s = level::sort_psites_decreasing(f); +// morpho::tree::data<I,S> t(f, s, c4()); +// accu::count< util::pix > area; +// image2d<unsigned> ref = morpho::tree::compute_attribute_image(area, t); +// mln_assertion(a == ref); +// } + + + + + +// unsigned n_wanted = 10; +// I g = filtering(f, a, c4(), n_regmins, n_wanted); + +} Index: geraud/tufa_2008/steps.1.cc --- geraud/tufa_2008/steps.1.cc (revision 0) +++ geraud/tufa_2008/steps.1.cc (revision 0) @@ -0,0 +1,273 @@ +// 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 sandbox/geraud/tufa/steps.cc + +#include <mln/core/image/image2d.hh> +#include <mln/value/int_u8.hh> +#include <mln/io/pgm/load.hh> +#include <mln/debug/println.hh> + +#include <mln/core/site_set/p_array.hh> +#include <mln/level/sort_psites.hh> +#include <mln/core/alias/neighb2d.hh> +#include <mln/morpho/tree/data.hh> + +#include <mln/accu/count.hh> +#include <mln/util/set.hh> + +#include <mln/labeling/regional_minima.hh> +#include <mln/morpho/tree/compute_attribute_image.hh> +#include <mln/morpho/closing_area.hh> +#include <mln/level/fill.hh> + + +namespace mln +{ + + template <typename I> + void println_par(const I& par) + { + int nr = par.nrows(), nc = par.ncols(); + for (int r = 0; r < nr; ++r) + { + for (int c = 0; c < nc; ++c) + if (par.at(r,c) == point2d(r,c)) + std::cout << "( ) "; + else + std::cout << par.at(r,c) << ' '; + std::cout << std::endl; + } + } + + template <typename P> + inline + mln_value(P) find_root__(P& par, const mln_value(P)& x) + { + if (par(x) == x) + return x; + else + return par(x) = find_root__(par, par(x)); + } + + + template <typename I, typename A, typename N> + void run_run(const I& f, const A& a, const N& nbh) + { + typedef p_array<mln_psite(I)> S; + S s = level::sort_psites_increasing(a); + // s maps increasing attributes. + + mln_ch_value(I, mln_site(I)) par; + mln_ch_value(I, bool) deja_vu; + mln_ch_value(I, util::set<unsigned>) labels; + unsigned nbassins, current_n; + + + // Initialization. + { + mln_piter(A) p(f.domain()); + + // parent + initialize(par, f); + for_all(p) + par(p) = p; + + // deja_vu + initialize(deja_vu, f); + level::fill(deja_vu, false); + + // labels + mln_ch_value(I, unsigned) regmin = labeling::regional_minima(a, nbh, + nbassins); + debug::println(regmin); + initialize(labels, f); + for_all(p) + if (regmin(p) != 0) // p in a reg min of the attribute image + labels(p).insert(regmin(p)); + } + + current_n = nbassins; + + // First pass. + { + mln_site(I) r; + mln_fwd_piter(S) p(s); + mln_niter(N) n(nbh, p); + for_all(p) + { + for_all(n) + if (a.domain().has(n) && deja_vu(n)) + { + r = find_root__(par, n); + if (r != p) + { + par(r) = p; // Union. + + // logging the different cases + if (labels(p).is_empty() && labels(r).is_empty()) + { + std::cout << "x"; + + // It can happen with: + // M M m + // (m a min, M a flat zone) + // During the pass: + // M M {m} + // then the 1st point is processed + // {} M {m} + // and when processing the 2nd point + // r={} p={} {m} + // the (left) neighbor of p has an empty set such as p. + +// // Extra log. +// std::cout << std::endl +// << "p = " << p << " " +// << "r = " << r << std::endl; +// debug::println(labels); + } + else + if (labels(p).is_empty() || labels(r).is_empty()) + { + std::cout << (labels(p).is_empty() ? 'p' : 'r'); + } + else + if (labels(p) == labels(r)) + { + std::cout << "="; +// // Extra log. +// std::cout << std::endl +// << "p = " << p << " " +// << "r = " << r << std::endl; +// debug::println(labels); + } + else + std::cout << "."; + // end of log + + // The invariants below are erroneous. +// mln_invariant(! (labels(p).is_empty() && labels(r).is_empty())); +// mln_invariant(labels(p) != labels(r)); + + // Either: + // one of the two label sets is empty (and the other is not) + // or: + // both label sets are not empty then they differ. + + // More restrictively: +// mln_invariant(! labels(r).is_empty()); + + if (labels(p).is_empty()) + { + labels(p).insert(labels(r)); + } + else + { + +// std::cout << std::endl +// << "at " << p << std::endl +// << "before:" << std::endl; +// debug::println(labels); + + unsigned + np = labels(p).nelements(), + nr = labels(r).nelements(); + labels(p).insert(labels(r)); + unsigned + n = labels(p).nelements(), + dnp = n - np, + dnr = n - nr, + delta_n = std::min(dnp, dnr); + + // The invariant below is erroneous. +// mln_invariant(delta_n != 0); + + +// std::cout << "delta = " << delta_n << std::endl +// << "after: " << std::endl; +// debug::println(labels); + + + // We can have the three cases below: + if (dnr > dnp) + std::cout << '>'; + else + if (dnr < dnp) + std::cout << '<'; + else + std::cout << '~'; + std::cout << '(' << delta_n << ')'; + } + } + } + deja_vu(p) = true; + } + } + + std::cout << std::endl; +// debug::println(labels); + } + + +} // mln + + + + +int main() +{ + using namespace mln; + using value::int_u8; + + int_u8 n; + + typedef image2d<int_u8> I; + I f; + io::pgm::load(f, "../../../img/tiny.pgm"); +// debug::println("f =", f); + + typedef p_array<point2d> S; + S s = level::sort_psites_decreasing(f); + + // Children go towards lower levels so leafs are regional minima. + // We get a min-tree so that we can perform morphological closings. + + morpho::tree::data<I,S> t(f, s, c4()); + accu::count< util::pix > attr; + + image2d<unsigned> a = morpho::tree::compute_attribute_image(attr, t); + run_run(f, a, c4()); + +// { +// S s = level::sort_psites_decreasing(g); +// morpho::tree::data<I,S> t(g, s, c4()); +// image2d<unsigned> a_g = morpho::tree::compute_attribute_image(attr, t); +// debug::println("a(f) =", a); +// debug::println("a(g) =", a_g); +// } + +} Index: geraud/tufa_2008/steps.2.cc --- geraud/tufa_2008/steps.2.cc (revision 0) +++ geraud/tufa_2008/steps.2.cc (revision 0) @@ -0,0 +1,184 @@ +// 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 sandbox/geraud/tufa/steps.cc + +#include <mln/core/image/image2d.hh> +#include <mln/value/int_u8.hh> +#include <mln/io/pgm/load.hh> +#include <mln/debug/println.hh> + +#include <mln/core/site_set/p_array.hh> +#include <mln/level/sort_psites.hh> +#include <mln/core/alias/neighb2d.hh> +#include <mln/morpho/tree/data.hh> + +#include <mln/accu/count.hh> +#include <mln/util/set.hh> + +#include <mln/labeling/regional_minima.hh> +#include <mln/morpho/tree/compute_attribute_image.hh> +#include <mln/morpho/closing_area.hh> +#include <mln/level/fill.hh> + + +namespace mln +{ + + template <typename I> + void println_par(const I& par) + { + int nr = par.nrows(), nc = par.ncols(); + for (int r = 0; r < nr; ++r) + { + for (int c = 0; c < nc; ++c) + if (par.at(r,c) == point2d(r,c)) + std::cout << "( ) "; + else + std::cout << par.at(r,c) << ' '; + std::cout << std::endl; + } + } + + template <typename P> + inline + mln_value(P) find_root__(P& par, const mln_value(P)& x) + { + if (par(x) == x) + return x; + else + return par(x) = find_root__(par, par(x)); + } + + + template <typename I, typename A, typename N> + void run_run(const I& f, const A& a, const N& nbh) + { + typedef p_array<mln_psite(I)> S; + S s = level::sort_psites_increasing(a); + // s maps increasing attributes. + + mln_ch_value(I, mln_site(I)) par; + mln_ch_value(I, bool) deja_vu; + mln_ch_value(I, util::set<unsigned>) labels; + unsigned nbassins, current_n; + + + // Initialization. + { + mln_piter(A) p(f.domain()); + + // parent + initialize(par, f); + for_all(p) + par(p) = p; + + // deja_vu + initialize(deja_vu, f); + level::fill(deja_vu, false); + + // labels + mln_ch_value(I, unsigned) regmin = labeling::regional_minima(a, nbh, + nbassins); + initialize(labels, f); + for_all(p) + if (regmin(p) != 0) // p in a reg min of the attribute image + labels(p).insert(regmin(p)); + } + + current_n = nbassins; + + // First pass. + { + mln_site(I) r; + mln_fwd_piter(S) p(s); + mln_niter(N) n(nbh, p); + for_all(p) + { + for_all(n) + if (a.domain().has(n) && deja_vu(n)) + { + r = find_root__(par, n); + if (r != p) + { + par(r) = p; // Union. + + if (labels(r).is_empty()) + // No-op. + ; + else + if (labels(p).is_empty()) + labels(p) = labels(r); + else + if (labels(p) == labels(r)) + // No-op. + ; + else + { + labels(p).insert(labels(r)); + --current_n; + } + } + } + deja_vu(p) = true; + } + } + + std::cout << std::endl; + std::cout << "end = " << current_n << std::endl; + } + + +} // mln + + + + +int main(int, char* argv[]) +{ + using namespace mln; + using value::int_u8; + + int_u8 n; + + typedef image2d<int_u8> I; + I f; + io::pgm::load(f, argv[1]); + + typedef p_array<point2d> S; + S s = level::sort_psites_decreasing(f); + + // Children go towards lower levels so leafs are regional minima. + // We get a min-tree so that we can perform morphological closings. + + morpho::tree::data<I,S> t(f, s, c4()); + accu::count< util::pix > attr; + + image2d<unsigned> a = morpho::tree::compute_attribute_image(attr, t); + run_run(f, a, c4()); + +} Index: geraud/tufa_2008/closing.cc --- geraud/tufa_2008/closing.cc (revision 0) +++ geraud/tufa_2008/closing.cc (revision 0) @@ -0,0 +1,64 @@ +// 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 sandbox/geraud/tufa/closing.cc + +#include <mln/core/image/image2d.hh> +#include <mln/value/int_u8.hh> +#include <mln/value/rgb8.hh> +#include <mln/io/pgm/load.hh> +#include <mln/io/pgm/save.hh> +#include <mln/core/alias/neighb2d.hh> + +#include <mln/morpho/elementary/gradient.hh> +#include <mln/morpho/closing_volume.hh> + + + +void usage(char* argv[]) +{ + std::cerr << "usage: " << argv[0] << " input.pgm lambda output.pgm" << std::endl; + std::abort(); +} + + +int main(int argc, char* argv[]) +{ + using namespace mln; + using value::int_u8; + + if (argc != 4) + usage(argv); + + image2d<int_u8> f; + io::pgm::load(f, argv[1]); + unsigned lambda = std::atoi(argv[2]); + io::pgm::save(morpho::closing_volume(f, + c4(), + lambda), + argv[3]); +} Index: geraud/tufa_2008/steps.3.cc --- geraud/tufa_2008/steps.3.cc (revision 0) +++ geraud/tufa_2008/steps.3.cc (revision 0) @@ -0,0 +1,184 @@ +// 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 sandbox/geraud/tufa/steps.cc + +#include <mln/core/image/image2d.hh> +#include <mln/value/int_u8.hh> +#include <mln/io/pgm/load.hh> +#include <mln/debug/println.hh> + +#include <mln/core/site_set/p_array.hh> +#include <mln/level/sort_psites.hh> +#include <mln/core/alias/neighb2d.hh> +#include <mln/morpho/tree/data.hh> + +#include <mln/accu/count.hh> +#include <mln/util/set.hh> + +#include <mln/labeling/regional_minima.hh> +#include <mln/morpho/tree/compute_attribute_image.hh> +#include <mln/morpho/closing_area.hh> +#include <mln/level/fill.hh> + + +namespace mln +{ + + template <typename I> + void println_par(const I& par) + { + int nr = par.nrows(), nc = par.ncols(); + for (int r = 0; r < nr; ++r) + { + for (int c = 0; c < nc; ++c) + if (par.at(r,c) == point2d(r,c)) + std::cout << "( ) "; + else + std::cout << par.at(r,c) << ' '; + std::cout << std::endl; + } + } + + template <typename P> + inline + mln_value(P) find_root__(P& par, const mln_value(P)& x) + { + if (par(x) == x) + return x; + else + return par(x) = find_root__(par, par(x)); + } + + + template <typename I, typename A, typename N> + void run_run(const I& f, const A& a, const N& nbh) + { + typedef p_array<mln_psite(I)> S; + S s = level::sort_psites_increasing(a); + // s maps increasing attributes. + + mln_ch_value(I, mln_site(I)) par; + mln_ch_value(I, bool) deja_vu; + mln_ch_value(I, util::set<unsigned>) labels; + unsigned nbassins, current_n; + + + // Initialization. + { + mln_piter(A) p(f.domain()); + + // parent + initialize(par, f); + for_all(p) + par(p) = p; + + // deja_vu + initialize(deja_vu, f); + level::fill(deja_vu, false); + + // labels + mln_ch_value(I, unsigned) regmin = labeling::regional_minima(a, nbh, + nbassins); + initialize(labels, f); + for_all(p) + if (regmin(p) != 0) // p in a reg min of the attribute image + labels(p).insert(regmin(p)); + } + + current_n = nbassins; + + // First pass. + { + mln_site(I) r; + mln_fwd_piter(S) p(s); + mln_niter(N) n(nbh, p); + for_all(p) + { + for_all(n) + if (a.domain().has(n) && deja_vu(n)) + { + r = find_root__(par, n); + if (r != p) + { + par(r) = p; // Union. + + if (labels(r).is_empty()) + // No-op. + ; + else + if (labels(p).is_empty()) + labels(p) = labels(r); + else + if (labels(p) == labels(r)) + // No-op. + ; + else + { + labels(p).insert(labels(r)); + --current_n; + } + } + } + deja_vu(p) = true; + } + } + + std::cout << std::endl; + std::cout << "end = " << current_n << std::endl; + } + + +} // mln + + + + +int main(int, char* argv[]) +{ + using namespace mln; + using value::int_u8; + + int_u8 n; + + typedef image2d<int_u8> I; + I f; + io::pgm::load(f, argv[1]); + + typedef p_array<point2d> S; + S s = level::sort_psites_decreasing(f); + + // Children go towards lower levels so leafs are regional minima. + // We get a min-tree so that we can perform morphological closings. + + morpho::tree::data<I,S> t(f, s, c4()); + accu::count< util::pix > attr; + + image2d<unsigned> a = morpho::tree::compute_attribute_image(attr, t); + run_run(f, a, c4()); + +} Index: geraud/tufa_2008/opening.cc --- geraud/tufa_2008/opening.cc (revision 0) +++ geraud/tufa_2008/opening.cc (revision 0) @@ -0,0 +1,63 @@ +// 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 sandbox/geraud/tufa/opening.cc + +#include <mln/core/image/image2d.hh> +#include <mln/value/int_u8.hh> +#include <mln/value/rgb8.hh> +#include <mln/io/pgm/load.hh> +#include <mln/io/pgm/save.hh> +#include <mln/core/alias/neighb2d.hh> + +#include <mln/morpho/opening_volume.hh> + + + +void usage(char* argv[]) +{ + std::cerr << "usage: " << argv[0] << " input.pgm lambda output.pgm" << std::endl; + std::abort(); +} + + +int main(int argc, char* argv[]) +{ + using namespace mln; + using value::int_u8; + + if (argc != 4) + usage(argv); + + image2d<int_u8> f, g; + io::pgm::load(f, argv[1]); + unsigned lambda = std::atoi(argv[2]); + initialize(g, f); + morpho::opening_volume(f, c4(), lambda, g); + io::pgm::save(g, + argv[3]); +} Index: geraud/tufa_2008/experiment.cc --- geraud/tufa_2008/experiment.cc (revision 0) +++ geraud/tufa_2008/experiment.cc (revision 0) @@ -0,0 +1,138 @@ +// 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 sandbox/geraud/tufa/experiment.cc + +#include <mln/core/image/image2d.hh> +#include <mln/value/int_u8.hh> +#include <mln/value/rgb8.hh> +#include <mln/literal/black.hh> + +#include <mln/io/pgm/load.hh> +#include <mln/io/pgm/save.hh> +#include <mln/io/ppm/save.hh> +#include <mln/debug/println.hh> + +#include <mln/core/site_set/p_array.hh> +#include <mln/level/sort_psites.hh> +#include <mln/core/alias/neighb2d.hh> +#include <mln/morpho/tree/data.hh> + +#include <mln/accu/volume.hh> +#include <mln/win/disk2d.hh> + +#include <mln/morpho/tree/compute_attribute_image.hh> +#include <mln/morpho/meyer_wst.hh> +#include <mln/morpho/opening.hh> +#include <mln/morpho/closing_area.hh> + +#include <mln/level/fill.hh> + +#include <mln/level/transform.hh> +#include <mln/level/stretch.hh> + + + +namespace mln +{ + + struct colorize : Function_v2v< colorize > + { + typedef value::rgb8 result; + colorize(unsigned max) + : lut(max + 1) + { + lut[0] = literal::black; + for (unsigned i = 1; i <= max; ++i) + lut[i] = result(100 + std::rand() % 150, + 100 + std::rand() % 150, + 100 + std::rand() % 150); + } + result operator()(unsigned i) const + { + return lut[i]; + } + std::vector<result> lut; + }; + +} // mln + + + + +void usage(char* argv[]) +{ + std::cerr << "usage: " << argv[0] << " input.pgm" << std::endl; + std::abort(); +} + + + +int main(int argc, char* argv[]) +{ + using namespace mln; + using value::int_u8; + + if (argc != 2) + usage(argv); + + + typedef image2d<int_u8> I; + I f; + io::pgm::load(f, argv[1]); + + typedef p_array<point2d> S; + S s = level::sort_psites_decreasing(f); + + // Children go towards lower levels so leafs are regional minima. + // We get a min-tree so that we can perform morphological closings. + + morpho::tree::data<I,S> t(f, s, c4()); + accu::volume attr; + + image2d<unsigned> a = morpho::tree::compute_attribute_image(attr, t); + io::pgm::save(level::stretch(int_u8(), a), + "a.pgm"); + + unsigned n; + image2d<unsigned> wst_a = morpho::meyer_wst(a, c4(), n); + io::ppm::save(level::transform(wst_a, colorize(n)), + "wst_a.ppm"); + std::cout << "n(a) = " << n << std::endl; + + // FIXME: ça n'a pas de sens de faire ce qui est dessous... :-( + + + image2d<unsigned> aa = morpho::closing_area(a, c4(), 100); + io::pgm::save(level::stretch(int_u8(), aa), + "aa.pgm"); + + image2d<unsigned> wst_aa = morpho::meyer_wst(aa, c4(), n); + io::ppm::save(level::transform(wst_aa, colorize(n)), + "wst_aa.ppm"); + std::cout << "n(aa) = " << n << std::endl; +} Index: geraud/tufa_2008/steps.2b.cc --- geraud/tufa_2008/steps.2b.cc (revision 0) +++ geraud/tufa_2008/steps.2b.cc (revision 0) @@ -0,0 +1,184 @@ +// 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 sandbox/geraud/tufa/steps.cc + +#include <mln/core/image/image2d.hh> +#include <mln/value/int_u8.hh> +#include <mln/io/pgm/load.hh> +#include <mln/debug/println.hh> + +#include <mln/core/site_set/p_array.hh> +#include <mln/level/sort_psites.hh> +#include <mln/core/alias/neighb2d.hh> +#include <mln/morpho/tree/data.hh> + +#include <mln/accu/count.hh> +#include <set> + +#include <mln/labeling/regional_minima.hh> +#include <mln/morpho/tree/compute_attribute_image.hh> +#include <mln/morpho/closing_area.hh> +#include <mln/level/fill.hh> + + +namespace mln +{ + + template <typename I> + void println_par(const I& par) + { + int nr = par.nrows(), nc = par.ncols(); + for (int r = 0; r < nr; ++r) + { + for (int c = 0; c < nc; ++c) + if (par.at(r,c) == point2d(r,c)) + std::cout << "( ) "; + else + std::cout << par.at(r,c) << ' '; + std::cout << std::endl; + } + } + + template <typename P> + inline + mln_value(P) find_root__(P& par, const mln_value(P)& x) + { + if (par(x) == x) + return x; + else + return par(x) = find_root__(par, par(x)); + } + + + template <typename I, typename A, typename N> + void run_run(const I& f, const A& a, const N& nbh) + { + typedef p_array<mln_psite(I)> S; + S s = level::sort_psites_increasing(a); + // s maps increasing attributes. + + mln_ch_value(I, mln_site(I)) par; + mln_ch_value(I, bool) deja_vu; + mln_ch_value(I, std::set<unsigned>) labels; + unsigned nbassins, current_n; + + + // Initialization. + { + mln_piter(A) p(f.domain()); + + // parent + initialize(par, f); + for_all(p) + par(p) = p; + + // deja_vu + initialize(deja_vu, f); + level::fill(deja_vu, false); + + // labels + mln_ch_value(I, unsigned) regmin = labeling::regional_minima(a, nbh, + nbassins); + initialize(labels, f); + for_all(p) + if (regmin(p) != 0) // p in a reg min of the attribute image + labels(p).insert(regmin(p)); + } + + current_n = nbassins; + + // First pass. + { + mln_site(I) r; + mln_fwd_piter(S) p(s); + mln_niter(N) n(nbh, p); + for_all(p) + { + for_all(n) + if (a.domain().has(n) && deja_vu(n)) + { + r = find_root__(par, n); + if (r != p) + { + par(r) = p; // Union. + + if (labels(r).empty()) + // No-op. + ; + else + if (labels(p).empty()) + labels(p) = labels(r); + else + if (labels(p) == labels(r)) + // No-op. + ; + else + { + labels(p).insert(labels(r).begin(), labels(r).end()); + --current_n; + } + } + } + deja_vu(p) = true; + } + } + + std::cout << std::endl; + std::cout << "end = " << current_n << std::endl; + } + + +} // mln + + + + +int main(int, char* argv[]) +{ + using namespace mln; + using value::int_u8; + + int_u8 n; + + typedef image2d<int_u8> I; + I f; + io::pgm::load(f, argv[1]); + + typedef p_array<point2d> S; + S s = level::sort_psites_decreasing(f); + + // Children go towards lower levels so leafs are regional minima. + // We get a min-tree so that we can perform morphological closings. + + morpho::tree::data<I,S> t(f, s, c4()); + accu::count< util::pix > attr; + + image2d<unsigned> a = morpho::tree::compute_attribute_image(attr, t); + run_run(f, a, c4()); + +} Index: geraud/tufa_2008/filter.cc --- geraud/tufa_2008/filter.cc (revision 0) +++ geraud/tufa_2008/filter.cc (revision 0) @@ -0,0 +1,169 @@ +// 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 sandbox/geraud/tufa/filter.cc + +#include <mln/core/image/image2d.hh> +#include <mln/value/int_u8.hh> +#include <mln/value/rgb8.hh> +#include <mln/literal/black.hh> + +#include <mln/io/pgm/load.hh> +#include <mln/io/pgm/save.hh> +#include <mln/io/ppm/save.hh> +#include <mln/debug/println.hh> + +#include <mln/core/site_set/p_array.hh> +#include <mln/core/alias/neighb2d.hh> +#include <mln/level/sort_psites.hh> +#include <mln/level/fill.hh> + +#include <mln/morpho/tree/data.hh> +#include <mln/morpho/tree/compute_attribute_image.hh> +#include <mln/morpho/closing_volume.hh> + + + +namespace mln +{ + + template <typename P> + inline + mln_value(P) find_root__(P& par, const mln_value(P)& x) + { + if (par(x) == x) + return x; + else + return par(x) = find_root__(par, par(x)); + } + + + template <typename I, typename A, typename N> + mln_concrete(I) filtering(const I& f, const A& a, const N& nbh, mln_value(A) lambda) + { + typedef p_array<mln_psite(I)> S; + S s = level::sort_psites_increasing(a); + + // s maps increasing attributes. + + mln_concrete(I) out; + initialize(out, f); + + mln_ch_value(I, mln_site(I)) par; + mln_ch_value(I, bool) deja_vu; + { + initialize(par, f); + mln_piter(A) p(par.domain()); + for_all(p) + par(p) = p; + initialize(deja_vu, f); + level::fill(deja_vu, false); + } + + // First pass. + { + mln_site(I) r; + mln_fwd_piter(S) p(s); + mln_niter(N) n(nbh, p); + for_all(p) + { + for_all(n) + if (a.domain().has(n) && deja_vu(n)) + { + r = find_root__(par, n); + if (r != p) + if (f(r) == f(p) || a(r) < lambda) + par(r) = p; // Union. + } + deja_vu(p) = true; + } + } + + // Second pass. + { + mln_bkd_piter(S) p(s); + for_all(p) + if (par(p) == p) + out(p) = f(p); + else + out(p) = out(par(p)); + } + return out; + } + + +} // mln + + + +void usage(char* argv[]) +{ + std::cerr << "usage: " << argv[0] << " input.pgm lambda output.pgm" << std::endl; + std::abort(); +} + + + +int main(int argc, char* argv[]) +{ + using namespace mln; + using value::int_u8; + + if (argc != 4) + usage(argv); + + + typedef image2d<int_u8> I; + I f; + io::pgm::load(f, argv[1]); + + unsigned lambda = std::atoi(argv[2]); + + typedef p_array<point2d> S; + S s = level::sort_psites_decreasing(f); + + // Children go towards lower levels so leafs are regional minima. + // We get a min-tree so that we can perform morphological closings. + + morpho::tree::data<I,S> t(f, s, c4()); + accu::volume attr; + + image2d<unsigned> a = morpho::tree::compute_attribute_image(attr, t); + + I g = filtering(f, a, c4(), lambda); + + { + I ref = morpho::closing_volume(f, c4(), lambda); + if (g != ref) + { + io::pgm::save(ref, "ref.pgm"); + std::cerr << "oops!" << std::endl; + } + } + + io::pgm::save(g, argv[3]); +} Index: geraud/tufa_2008/wst_f_equal_wst_a.cc --- geraud/tufa_2008/wst_f_equal_wst_a.cc (revision 0) +++ geraud/tufa_2008/wst_f_equal_wst_a.cc (revision 0) @@ -0,0 +1,140 @@ +// 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 sandbox/geraud/tufa/steps.cc + +#include <mln/core/image/image2d.hh> +#include <mln/pw/all.hh> +#include <mln/value/int_u8.hh> +#include <mln/value/rgb8.hh> +#include <mln/io/pgm/load.hh> +#include <mln/io/ppm/save.hh> +#include <mln/io/pbm/save.hh> +#include <mln/literal/black.hh> + +#include <mln/core/site_set/p_array.hh> +#include <mln/level/sort_psites.hh> +#include <mln/level/transform.hh> +#include <mln/core/alias/neighb2d.hh> +#include <mln/morpho/tree/data.hh> + +#include <mln/accu/volume.hh> +#include <mln/morpho/tree/compute_attribute_image.hh> +#include <mln/morpho/meyer_wst.hh> + +#include <mln/labeling/regional_minima.hh> + +#include <mln/core/var.hh> + + +namespace mln +{ + + struct colorize : Function_v2v< colorize > + { + typedef value::rgb8 result; + colorize(unsigned max) + : lut(max + 1) + { + lut[0] = literal::black; + for (unsigned i = 1; i <= max; ++i) + lut[i] = result(100 + std::rand() % 150, + 100 + std::rand() % 150, + 100 + std::rand() % 150); + } + result operator()(unsigned i) const + { + return lut[i]; + } + std::vector<result> lut; + }; + +} // mln + + + +void usage(char* argv[]) +{ + std::cerr << "usage: " << argv[0] << " input.pgm" << std::endl; + std::abort(); +} + + + +int main(int argc, char* argv[]) +{ + using namespace mln; + using value::int_u8; + + if (argc != 2) + usage(argv); + + unsigned nref, n; + + typedef image2d<int_u8> I; + I f; + io::pgm::load(f, argv[1]); + + labeling::regional_minima(f, c4(), nref); + std::cout << nref << std::endl; + + + image2d<unsigned> wst_f = morpho::meyer_wst(f, c4(), n); + mln_assertion(n == nref); + + io::ppm::save(level::transform(wst_f, colorize(n)), + "wst_f.ppm"); + mln_VAR(WST_f, (pw::value(wst_f) == pw::cst(0u)) | f.domain()); + io::pbm::save(WST_f, "wst_f.pbm"); + + + typedef p_array<point2d> S; + S s = level::sort_psites_decreasing(f); + + // Children go towards lower levels so leafs are regional minima. + // We get a min-tree so that we can perform morphological closings. + + morpho::tree::data<I,S> t(f, s, c4()); + accu::volume vol; + image2d<unsigned> a = morpho::tree::compute_attribute_image(vol, t); + + labeling::regional_minima(a, c4(), n); + mln_assertion(n == nref); + + + image2d<unsigned> wst_a = morpho::meyer_wst(a, c4(), n); + mln_assertion(n == nref); + + io::ppm::save(level::transform(wst_a, colorize(n)), + "wst_a.ppm"); + mln_VAR(WST_a, (pw::value(wst_a) == pw::cst(0u)) | f.domain()); + io::pbm::save(WST_a, "wst_a.pbm"); + + + io::pbm::save((pw::value(WST_a) != pw::value(WST_f)) | f.domain(), + "diff.pbm"); +} Index: geraud/tufa_2008/closed_gradient.cc --- geraud/tufa_2008/closed_gradient.cc (revision 0) +++ geraud/tufa_2008/closed_gradient.cc (revision 0) @@ -0,0 +1,64 @@ +// 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 sandbox/geraud/tufa/closed_gradient.cc + +#include <mln/core/image/image2d.hh> +#include <mln/value/int_u8.hh> +#include <mln/value/rgb8.hh> +#include <mln/io/pgm/load.hh> +#include <mln/io/pgm/save.hh> +#include <mln/core/alias/neighb2d.hh> + +#include <mln/morpho/elementary/gradient.hh> +#include <mln/morpho/closing_volume.hh> + + + +void usage(char* argv[]) +{ + std::cerr << "usage: " << argv[0] << " input.pgm lambda output.pgm" << std::endl; + std::abort(); +} + + +int main(int argc, char* argv[]) +{ + using namespace mln; + using value::int_u8; + + if (argc != 4) + usage(argv); + + image2d<int_u8> f; + io::pgm::load(f, argv[1]); + unsigned lambda = std::atoi(argv[2]); + io::pgm::save(morpho::closing_volume(morpho::elementary::gradient(f, c4()), + c4(), + lambda), + argv[3]); +} Index: geraud/tufa_2008/fz_count.cc --- geraud/tufa_2008/fz_count.cc (revision 0) +++ geraud/tufa_2008/fz_count.cc (revision 0) @@ -0,0 +1,159 @@ +// 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 sandbox/geraud/tufa/fz_count.cc + +#include <mln/core/image/image2d.hh> +#include <mln/value/int_u8.hh> +#include <mln/io/pgm/load.hh> +#include <mln/debug/println.hh> + +#include <mln/core/site_set/p_array.hh> +#include <mln/level/sort_psites.hh> +#include <mln/core/alias/neighb2d.hh> + +#include <mln/labeling/regional_minima.hh> +#include <mln/labeling/flat_zones.hh> +#include <mln/level/fill.hh> + + +namespace mln +{ + + template <typename I> + void println_par(const I& par) + { + int nr = par.nrows(), nc = par.ncols(); + for (int r = 0; r < nr; ++r) + { + for (int c = 0; c < nc; ++c) + if (par.at(r,c) == point2d(r,c)) + std::cout << "( ) "; + else + std::cout << par.at(r,c) << ' '; + std::cout << std::endl; + } + } + + template <typename P> + inline + mln_value(P) find_root__(P& par, const mln_value(P)& x) + { + if (par(x) == x) + return x; + else + return par(x) = find_root__(par, par(x)); + } + + + template <typename I, typename N> + unsigned fz_count(const I& f, const N& nbh) + { + typedef p_array<mln_psite(I)> S; + S s = level::sort_psites_increasing(f); + // s maps increasing attributes. + + mln_ch_value(I, mln_site(I)) par; + mln_ch_value(I, bool) deja_vu; + + unsigned counter = f.domain().nsites(); + + // Initialization. + { + mln_piter(I) p(f.domain()); + + // parent + initialize(par, f); + for_all(p) + par(p) = p; + + // deja_vu + initialize(deja_vu, f); + level::fill(deja_vu, false); + } + + // First pass. + { + mln_site(I) r; + mln_fwd_piter(S) p(s); + mln_niter(N) n(nbh, p); + for_all(p) + { + for_all(n) + if (f.domain().has(n) && deja_vu(n)) + { + r = find_root__(par, n); + if (r != p) // not already merged + { + if (f(r) == f(p)) + { + + // Moving the line below out of this test + // (either before the test or after the block) + // makes the algorithm fail. + // The erroneous result is less than the ref + // result => we want this current block too many + // times. Since we merge (thru "par(r) = p") + // whatever "f(r) == f(p)" is true or not, we + // have more often "f(r) == f(p)" than expected. + par(r) = p; + + --counter; + } + } + } + + deja_vu(p) = true; + } + } + + return counter; + } + + +} // mln + + + + +int main(int, char* argv[]) +{ + using namespace mln; + using value::int_u8; + + typedef image2d<int_u8> I; + I f; + io::pgm::load(f, argv[1]); + + unsigned ref, n = fz_count(f, c4()); + labeling::flat_zones(f, c4(), ref); + + if (n == ref) + std::cout << "success: n flat zones = " << n << std::endl; + else + std::cout << "FAILURE: found = " << n << " v. ref = " << ref << std::endl; +} Index: geraud/tufa_2008/regmin_count.cc --- geraud/tufa_2008/regmin_count.cc (revision 0) +++ geraud/tufa_2008/regmin_count.cc (revision 0) @@ -0,0 +1,173 @@ +// 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 sandbox/geraud/tufa/regmin_count.cc + +#include <mln/core/image/image2d.hh> +#include <mln/value/int_u8.hh> +#include <mln/io/pgm/load.hh> +#include <mln/debug/println.hh> + +#include <mln/core/site_set/p_array.hh> +#include <mln/level/sort_psites.hh> +#include <mln/core/alias/neighb2d.hh> + +#include <mln/labeling/regional_minima.hh> +#include <mln/labeling/flat_zones.hh> +#include <mln/level/fill.hh> + + +namespace mln +{ + + template <typename I> + void println_par(const I& par) + { + int nr = par.nrows(), nc = par.ncols(); + for (int r = 0; r < nr; ++r) + { + for (int c = 0; c < nc; ++c) + if (par.at(r,c) == point2d(r,c)) + std::cout << "( ) "; + else + std::cout << par.at(r,c) << ' '; + std::cout << std::endl; + } + } + + template <typename P> + inline + mln_value(P) find_root__(P& par, const mln_value(P)& x) + { + if (par(x) == x) + return x; + else + return par(x) = find_root__(par, par(x)); + } + + + template <typename I, typename N> + unsigned regmin_count(const I& f, const N& nbh) + { + typedef p_array<mln_psite(I)> S; + S s = level::sort_psites_increasing(f); + // s maps increasing attributes. + + mln_ch_value(I, mln_site(I)) par; + mln_ch_value(I, bool) deja_vu, flag; + + unsigned counter = f.domain().nsites(); + + + // Initialization. + { + mln_piter(I) p(f.domain()); + + // parent + initialize(par, f); + for_all(p) + par(p) = p; + + // flag + initialize(flag, f); + level::fill(flag, true); + + // deja_vu + initialize(deja_vu, f); + level::fill(deja_vu, false); + } + + // First pass. + { + mln_site(I) r; + mln_fwd_piter(S) p(s); + mln_niter(N) n(nbh, p); + for_all(p) + { + unsigned loc = 0; + for_all(n) + if (f.domain().has(n) && deja_vu(n)) + { + r = find_root__(par, n); + if (r != p) + { + if (f(r) == f(p)) + { + par(r) = p; // Union. + if (flag(p) == false && flag(r) == false) + { + // Two non-reg-min components merge (same flat + // zone) so we had an extra invalidation. + ++counter; + } + flag(p) = flag(p) && flag(r); + --counter; // So we get the number of flat zones + // minus the non-reg-min flat zones. + } + else + { + mln_invariant(f(r) < f(p)); + if (flag(p) == true) + { + ++loc; + --counter; // Invalidation. + } + flag(p) = false; + } + } + } + mln_invariant(loc == 0 || loc == 1); + deja_vu(p) = true; + } + } + + return counter; + } + + +} // mln + + + + +int main(int, char* argv[]) +{ + using namespace mln; + using value::int_u8; + + typedef image2d<int_u8> I; + I f; + io::pgm::load(f, argv[1]); + + unsigned ref, n = regmin_count(f, c4()); + labeling::regional_minima(f, c4(), ref); + + if (n == ref) + std::cout << "success: n regional minima = " << n << std::endl; + else + std::cout << "FAILURE: found = " << n << " v. ref = " << ref << std::endl; +}

1 0

3025: [Scribo] Make use of depth first search canvas.
by Guillaume Lazzara 10 Dec '08

10 Dec '08

* sandbox/scribo/demat.hh: use depth first search canvas. * sandbox/scribo/photo.cc, * sandbox/scribo/table.cc: Use a dedicated routine. --- milena/sandbox/ChangeLog | 9 ++ milena/sandbox/scribo/demat.hh | 296 ++++++++++++++++++---------------------- milena/sandbox/scribo/photo.cc | 2 +- milena/sandbox/scribo/table.cc | 2 +- 4 files changed, 143 insertions(+), 166 deletions(-) diff --git a/milena/sandbox/ChangeLog b/milena/sandbox/ChangeLog index cc1d17d..020324f 100644 --- a/milena/sandbox/ChangeLog +++ b/milena/sandbox/ChangeLog @@ -1,3 +1,12 @@ +2008-12-10 Guillaume Lazzara <z(a)lrde.epita.fr> + + [Scribo] Make use of depth first search canvas. + + * sandbox/scribo/demat.hh: use depth first search canvas. + + * sandbox/scribo/photo.cc, + * sandbox/scribo/table.cc: Use a dedicated routine. + 2008-12-10 Matthieu Garrigues <garrigues(a)lrde.epita.fr> [Markov] Speed up the algorithm. diff --git a/milena/sandbox/scribo/demat.hh b/milena/sandbox/scribo/demat.hh index ff059d2..609e4c8 100644 --- a/milena/sandbox/scribo/demat.hh +++ b/milena/sandbox/scribo/demat.hh @@ -51,7 +51,9 @@ # include <mln/util/graph.hh> # include <mln/util/line_graph.hh> -#include <tesseract/baseapi.h> +# include <mln/canvas/browsing/depth_first_search.hh> + +# include <tesseract/baseapi.h> namespace scribo { @@ -206,7 +208,7 @@ namespace scribo { image2d<bool> b(tboxes[i], 0); level::fill(b, false); - level::fill(b, in | (tboxes[i] | (pw::value(lbl) == pw::cst(i)))); + level::fill((b | (pw::value(lbl) == pw::cst(i))).rw(), true); char* s = TessBaseAPI::TesseractRect( (unsigned char*) b.buffer(), @@ -526,39 +528,6 @@ namespace scribo //-*************************************** /// \{ - fun::l2l::relabel<label_16> - make_relabel_fun(const util::graph& g) - { - fun::l2l::relabel<label_16> fun(g.v_nmax(), mln_max(label_16)); - - // The first vertex (id 0) IS the background (component 0). - unsigned ncomp = 0; - mln_vertex_iter_(util::graph) v(g); - for_all(v) - if (fun(v.id()) == mln_max(label_16)) - { - std::queue<unsigned> queue; - queue.push(v.id()); - fun(v.id()) = ncomp; - while (!queue.empty()) - { - util::vertex<util::graph> current_v = g.vertex(queue.front()); - queue.pop(); - for (unsigned nv = 0; nv < current_v.nmax_nbh_vertices(); ++nv) - if (fun(current_v.ith_nbh_vertex(nv)) == mln_max(label_16)) - { - fun(current_v.ith_nbh_vertex(nv)) = ncomp; - queue.push(current_v.ith_nbh_vertex(nv)); - } - } - ++ncomp; - } - - return fun; - } - - - template <typename R> struct remove_small_comps : Function_l2b< remove_small_comps<R> > @@ -630,22 +599,88 @@ namespace scribo } } + struct make_relabel_fun_t + { + template <typename G> + void init(const Graph<G>& g) + { + l2l.resize(exact(g).v_nmax(), mln_max(label_16)); + ncomp = 0; + } + + void final() + {} + + void next() + { ++ncomp; } + + void update_treated(unsigned id) + { l2l(id) = ncomp; } + + void update_queued(unsigned id) + { update_treated(id); } + + bool to_be_treated(unsigned id) + { return l2l(id) == mln_max(label_16); } + + bool to_be_queued(unsigned id) + { return to_be_treated(id); } + + unsigned ncomp; + fun::l2l::relabel<label_16> l2l; + }; + + struct comp_size_t + { + template <typename G> + void init(const Graph<G>& g) + { + treated.resize(exact(g).v_nmax(), mln_max(label_16)); + } + + void final() + {} + + void next() + { + unsigned compsize = comp_vertices.nelements(); + for (unsigned i = 0; i < comp_vertices.nelements(); ++i) + treated[comp_vertices[i]] = compsize; + comp_vertices.clear(); + } + void update_treated(unsigned id) + { comp_vertices.insert(id); } + + void update_queued(unsigned id) + { update_treated(id); } + + bool to_be_treated(unsigned id) + { return treated[id] == mln_max(label_16); } + + bool to_be_queued(unsigned id) + { return comp_vertices.has(id); } + + util::set<unsigned> comp_vertices; + util::array<unsigned> treated; + }; /// Merge bboxes according to their left box neighbor. - util::array< box2d > + util::array<box2d> group_bboxes(const util::graph& g, image2d<label_16>& lbl, util::array<box2d>& cboxes, label_16& nlabels) { - fun::l2l::relabel<label_16> relabel_fun = make_relabel_fun(g); + // Build relabel function. + make_relabel_fun_t f; + canvas::browsing::depth_first_search(g, f); util::array< accu::bbox<point2d> > tboxes; tboxes.resize(nlabels.next()); for_all_ncomponents(i, nlabels) - tboxes[relabel_fun(i)].take(cboxes[i]); + tboxes[f.l2l(i)].take(cboxes[i]); //Update labels - labeling::relabel_inplace(lbl, nlabels, relabel_fun); + labeling::relabel_inplace(lbl, nlabels, f.l2l); #ifndef NOUT save_lbl_image(lbl, nlabels, "lbl-grouped-boxes.pgm"); @@ -656,39 +691,18 @@ namespace scribo if (tboxes[i].is_valid()) result.append(tboxes[i].to_result()); + mln_assertion(result.nelements() == f.ncomp); nlabels = result.nelements(); + #ifndef NOUT image2d<label_16> lbl2 = clone(lbl); - util::array<unsigned> treated(g.v_nmax(), mln_max(unsigned)); - util::set<unsigned> comp_vertices; - mln_vertex_iter_(util::graph) v(g); - for_all(v) - if (treated[v.id()] == mln_max(unsigned)) - { - std::queue<unsigned> queue; - queue.push(v.id()); - comp_vertices.insert(v.id()); - while (!queue.empty()) - { - util::vertex<util::graph> current_v = g.vertex(queue.front()); - queue.pop(); - for (unsigned nv = 0; nv < current_v.nmax_nbh_vertices(); ++nv) - if (!comp_vertices.has(current_v.ith_nbh_vertex(nv))) - { - comp_vertices.insert(current_v.ith_nbh_vertex(nv)); - queue.push(current_v.ith_nbh_vertex(nv)); - } - } - unsigned compsize = comp_vertices.nelements(); - for (unsigned i = 0; i < comp_vertices.nelements(); ++i) - treated[comp_vertices[i]] = compsize; - comp_vertices.clear(); - } + comp_size_t comp_size; + canvas::browsing::depth_first_search(g, comp_size); for_all_ncomponents(i, nlabels) if (tboxes[i].is_valid()) - if (treated[i] < 3) + if (comp_size.treated[i] < 3) level::fill((lbl2 | (tboxes[i].to_result() | (pw::value(lbl2) == pw::cst(i)))).rw(), 0u); save_lbl_image(lbl2, nlabels, "lbl-grouped-boxes-cleaned.ppm"); #endif @@ -769,72 +783,8 @@ namespace scribo return tboxes; } - - - struct gcolor_t : public mln::Function< gcolor_t > - { - typedef mln::value::rgb8 result; - - template <typename G> - mln::value::rgb8 - operator()(const mln::util::vertex<G>&) const - { - return mln::literal::cyan; - } - - template <typename G> - mln::value::rgb8 - operator()(const mln::util::edge<G>&) const - { - return mln::literal::magenta; - } - - }; - - struct gcolorarr_t : public mln::Function< gcolorarr_t > - { - typedef mln::value::rgb8 result; - - gcolorarr_t(unsigned n, const mln::value::rgb8& val) - : v_(n, val) - { - } - - template <typename G> - const mln::value::rgb8& - operator()(const mln::util::vertex<G>& v) const - { - return v_[v.id()]; - } - - template <typename G> - const mln::value::rgb8& - operator()(const mln::util::edge<G>& e) const - { - return v_[e.id()]; - } - - template <typename G> - mln::value::rgb8& - operator()(const mln::util::vertex<G>& v) - { - return v_[v.id()]; - } - - template <typename G> - mln::value::rgb8& - operator()(const mln::util::edge<G>& e) - { - return v_[e.id()]; - } - - std::vector<mln::value::rgb8> v_; - }; - - - template <typename P> - struct lg_vertex_values : public mln::Function_p2v< lg_vertex_values > + struct lg_vertex_values : public mln::Function_p2v< lg_vertex_values > { typedef float result; @@ -895,7 +845,7 @@ namespace scribo typedef fun::i2v::array<point2d> fv2p_t; fv2p_t fv2p(nlabels.next()); - for_all_elements(i, tboxes) + for_all_components(i, tboxes) fv2p(i) = tboxes[i].center(); // util::array<point2d> centers = labeling::compute(accu::center<point2d>(), iz, nlabels); // fv2p_t fv2p = convert::to<fv2p_t>(centers); @@ -924,16 +874,16 @@ namespace scribo mln_VAR(lg_ima, lgv2v | pvlg); - gcolorarr_t ecolor(pvlg.nsites(), literal::olive); + fun::i2v::array<value::rgb8> ecolor(pvlg.nsites(), literal::olive); mln_piter_(lg_ima_t) p(lg_ima.domain()); for_all (p) if ((lg_ima(p) > settings.max_cos) || (lg_ima(p) < - settings.max_cos)) - ecolor(p.element()) = literal::cyan; + ecolor(p) = literal::cyan; #ifndef NOUT image2d<rgb8> output = level::convert(rgb8(), in); internal::draw_component_boxes(output, tboxes); - debug::draw_graph(output, pvlg, gcolor_t(), ecolor); + debug::draw_graph(output, pvlg, pw::cst(literal::cyan), ecolor); io::ppm::save(output, internal::output_file("aligned-bboxes-merged.ppm")); #endif @@ -955,19 +905,13 @@ namespace scribo // Facade - void demat(char *argv[], bool treat_tables) + void demat_table(char *argv[]) { using namespace mln; using value::rgb8; using value::label_16; - - //Useful debug variables - border::thickness = 3; - trace::quiet = true; - - - internal::settings.treat_tables = treat_tables; + internal::settings.treat_tables = true; internal::input_file = basename(argv[1]); //Load image @@ -981,40 +925,64 @@ namespace scribo internal::settings.max_comp_size = in.ncols() * in.nrows() * 0.05; - //Label and remove small components. + std::pair<util::array<box2d>, + util::array<box2d> > tblboxes = internal::extract_tables(in); + image2d<bool> table = internal::rebuild_table(in, tblboxes); + + /// relabel since the table has been removed. label_16 nlabels; image2d<label_16> lbl = labeling::blobs(in, c8(), nlabels); + internal::cleanup_components(lbl, nlabels); - /// Do we really want to cleanup before removing tables? - if (!treat_tables) - internal::cleanup_components(lbl, nlabels); +#ifndef NOUT + internal::save_lbl_image(lbl, nlabels, "lbl-small-comps-removed.pgm"); +#endif - std::pair<util::array<box2d>, - util::array<box2d> > tblboxes; + util::array<box2d> tboxes = internal::extract_text(in, lbl, nlabels); - image2d<bool> table; - if (treat_tables) - { - tblboxes = internal::extract_tables(in); - table = internal::rebuild_table(in, tblboxes); + internal::merge_aligned_text_boxes(in, tboxes, lbl, nlabels); - /// relabel since the table has been removed. - lbl = labeling::blobs(in, c8(), nlabels); - /// Do we really want to cleanup again? - internal::cleanup_components(lbl, nlabels); + internal::maptext_to_cells(in, table, tboxes); #ifndef NOUT - internal::save_lbl_image(lbl, nlabels, "lbl-small-comps-removed.pgm"); + std::cout << "Saving output" << std::endl; + image2d<rgb8> output = level::convert(rgb8(), in_bak); + internal::draw_component_boxes(output, tboxes); + io::ppm::save(output, internal::output_file("out.ppm")); #endif - } - util::array<box2d> tboxes = - internal::extract_text(in, lbl, nlabels); + internal::text_recognition(in, lbl, tboxes); + } - internal::merge_aligned_text_boxes(in, tboxes, lbl, nlabels); - if (treat_tables) - internal::maptext_to_cells(in, table, tboxes); + void demat_photo(char *argv[]) + { + using namespace mln; + using value::rgb8; + using value::label_16; + + internal::settings.treat_tables = false; + internal::input_file = basename(argv[1]); + + //Load image + image2d<bool> in; + io::pbm::load(in, argv[1]); + logical::not_inplace(in); + +#ifndef NOUT + image2d<bool> in_bak = clone(in); +#endif + + internal::settings.max_comp_size = in.ncols() * in.nrows() * 0.05; + + //Label and remove small components. + label_16 nlabels; + image2d<label_16> lbl = labeling::blobs(in, c8(), nlabels); + + internal::cleanup_components(lbl, nlabels); + + util::array<box2d> tboxes = internal::extract_text(in, lbl, nlabels); + internal::merge_aligned_text_boxes(in, tboxes, lbl, nlabels); #ifndef NOUT std::cout << "Saving output" << std::endl; diff --git a/milena/sandbox/scribo/photo.cc b/milena/sandbox/scribo/photo.cc index 4e358ab..a173750 100644 --- a/milena/sandbox/scribo/photo.cc +++ b/milena/sandbox/scribo/photo.cc @@ -58,7 +58,7 @@ int main(int argc, char*argv[]) return 1; } - scribo::demat(argv, false); + scribo::demat_photo(argv); return 0; } diff --git a/milena/sandbox/scribo/table.cc b/milena/sandbox/scribo/table.cc index 3c28540..3472599 100644 --- a/milena/sandbox/scribo/table.cc +++ b/milena/sandbox/scribo/table.cc @@ -60,7 +60,7 @@ int main(int argc, char*argv[]) return 1; } - scribo::demat(argv, true); + scribo::demat_table(argv); return 0; } -- 1.5.6.5

1 0

3024: Add depth first search canvas for graphes.
by Guillaume Lazzara 10 Dec '08

10 Dec '08

* mln/canvas/browsing/depth_first_search.hh: new canvas. * mln/util/array.hh, * mln/fun/internal/array_base.hh: add new resize() overload. * mln/fun/x2x/rotation.hh: update doc. * tests/fun/x2x/rotation.cc: fix wrong namespace. * milena/tests/unit_test/Makefile.am, * milena/tests/unit_test/mln_canvas_browsing_depth_first_search.cc: add a new unit test. * milena/headers.mk: update distributed headers. --- milena/ChangeLog | 19 +++ milena/headers.mk | 2 +- milena/mln/canvas/browsing/depth_first_search.hh | 134 ++++++++++++++++++++ milena/mln/fun/internal/array_base.hh | 9 ++ milena/mln/fun/x2x/rotation.hh | 14 +-- milena/mln/util/array.hh | 11 ++ milena/tests/fun/x2x/rotation.cc | 4 +- milena/tests/unit_test/Makefile.am | 2 + .../mln_canvas_browsing_depth_first_search.cc | 8 ++ 9 files changed, 192 insertions(+), 11 deletions(-) create mode 100644 milena/mln/canvas/browsing/depth_first_search.hh create mode 100644 milena/tests/unit_test/mln_canvas_browsing_depth_first_search.cc diff --git a/milena/ChangeLog b/milena/ChangeLog index 2fd50e0..64c3fd7 100644 --- a/milena/ChangeLog +++ b/milena/ChangeLog @@ -1,3 +1,22 @@ +2008-12-10 Guillaume Lazzara <z(a)lrde.epita.fr> + + Add depth first search canvas for graphes. + + * mln/canvas/browsing/depth_first_search.hh: new canvas. + + * mln/util/array.hh, + * mln/fun/internal/array_base.hh: add new resize() overload. + + * mln/fun/x2x/rotation.hh: update doc. + + * tests/fun/x2x/rotation.cc: fix wrong namespace. + + * milena/tests/unit_test/Makefile.am, + * milena/tests/unit_test/mln_canvas_browsing_depth_first_search.cc: + add a new unit test. + + * milena/headers.mk: update distributed headers. + 2008-12-10 Thierry Geraud <thierry.geraud(a)lrde.epita.fr> Fix 'implies' test and doc tutorial examples. diff --git a/milena/headers.mk b/milena/headers.mk index f88845e..25f239c 100644 --- a/milena/headers.mk +++ b/milena/headers.mk @@ -237,7 +237,6 @@ mln/convert/to_p_array.hh \ mln/convert/from_to.hxx \ mln/convert/to_rgb.hh \ mln/convert/essential.hh \ -mln/value/label.hh.bak \ mln/value/float01_f.hh \ mln/value/float01_16.hh \ mln/value/lut_vec.hh \ @@ -464,6 +463,7 @@ mln/canvas/browsing/all.hh \ mln/canvas/browsing/diagonal2d.hh \ mln/canvas/browsing/fwd.hh \ mln/canvas/browsing/dir_struct_elt_incr_update.hh \ +mln/canvas/browsing/depth_first_search.hh \ mln/canvas/browsing/directional.hh \ mln/canvas/browsing/essential.hh \ mln/canvas/chamfer.hh \ diff --git a/milena/mln/canvas/browsing/depth_first_search.hh b/milena/mln/canvas/browsing/depth_first_search.hh new file mode 100644 index 0000000..716be86 --- /dev/null +++ b/milena/mln/canvas/browsing/depth_first_search.hh @@ -0,0 +1,134 @@ +// 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_CANVAS_BROWSING_DEPTH_FIRST_SEARCH_HH +# define MLN_CANVAS_BROWSING_DEPTH_FIRST_SEARCH_HH + +/// \file mln/canvas/browsing/depth_first_search.hh +/// +/// Depth-limited search algorithm for graph. +/// Browse over all vertices for each component. + +/*! +** The functor should provide the following methods: +** +** - template <typename G> void init(const Graph<G>& g) +** Will be called at the beginning. +** +** - void next() +** Will be called after all vertices from a component have been treated. +** +** - void update_treated(unsigned id) +** will be called for the first vertex encountered for each component. +** +** - void update_queued(unsigned id) +** Will be called for every vertex encountered in each component, except +** the first one. +** +** - bool to_be_treated(unsigned id) +** Return whether this vertex has already been marked or if it may be a +** a component representative. +** +** - bool to_be_queued(unsigned id) +** Return whether this vertex has already been marked or if it can be added +** to the current component. +** +** - void final() +** Will be called at the end; +** +*/ + +# include <mln/core/concept/graph.hh> + +namespace mln +{ + + namespace canvas + { + + namespace browsing + { + + struct depth_first_search_t : public Browsing< depth_first_search_t > + { + template <typename G, typename F> + void operator()(const Graph<G>&, F& f) const; + }; + + extern const depth_first_search_t depth_first_search; + +# ifndef MLN_INCLUDE_ONLY + + const depth_first_search_t depth_first_search; + + template <typename G, typename F> + inline + void + depth_first_search_t::operator()(const Graph<G>& g_, F& f) const + { + trace::entering("canvas::browsing::depth_first_search"); + + const G& g = exact(g_); + + f.init(g); + + mln_vertex_iter(util::graph) v(g); + for_all(v) + if (f.to_be_treated(v.id())) + { + std::queue<unsigned> queue; + queue.push(v.id()); + f.update_treated(v.id()); + while (!queue.empty()) + { + util::vertex<util::graph> current_v = g.vertex(queue.front()); + queue.pop(); + for (unsigned nv = 0; nv < current_v.nmax_nbh_vertices(); ++nv) + if (f.to_be_queued(current_v.ith_nbh_vertex(nv))) + { + f.update_queued(current_v.ith_nbh_vertex(nv)); + queue.push(current_v.ith_nbh_vertex(nv)); + } + } + f.next(); + } + + f.final(); + + trace::exiting("canvas::browsing::depth_first_search"); + } + +# endif // ! MLN_INCLUDE_ONLY + + } // end of namespace mln::canvas::browsing + + } // end of namespace mln::canvas + +} // end of namespace mln + + +#endif // ! MLN_CANVAS_BROWSING_DEPTH_FIRST_SEARCH_HH diff --git a/milena/mln/fun/internal/array_base.hh b/milena/mln/fun/internal/array_base.hh index 32abb8a..62486fb 100644 --- a/milena/mln/fun/internal/array_base.hh +++ b/milena/mln/fun/internal/array_base.hh @@ -55,6 +55,7 @@ namespace mln typedef T result; void resize(unsigned n); + void resize(unsigned n, const T& val); unsigned size() const; const T& operator()(unsigned i) const; @@ -150,6 +151,14 @@ namespace mln template <typename T> inline + void + array_base<T>::resize(unsigned n, const T& val) + { + v_.resize(n, val); + } + + template <typename T> + inline unsigned array_base<T>::size() const { diff --git a/milena/mln/fun/x2x/rotation.hh b/milena/mln/fun/x2x/rotation.hh index 9364cda..6ebe9b2 100644 --- a/milena/mln/fun/x2x/rotation.hh +++ b/milena/mln/fun/x2x/rotation.hh @@ -1,4 +1,5 @@ -// Copyright (C) 2007 EPITA Research and Development Laboratory +// 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 @@ -28,10 +29,9 @@ #ifndef MLN_FUN_X2X_ROTATION_HH # define MLN_FUN_X2X_ROTATION_HH -/*! \file mln/fun/x2x/rotation.hh - * - * \brief Define a rotation function. - */ +/// \file mln/fun/x2x/rotation.hh +/// +/// Define a rotation function. # include <mln/core/concept/function.hh> # include <mln/fun/internal/x2x_linear_impl.hh> @@ -116,9 +116,7 @@ namespace mln } // end of namespace internal - /*! \brief Represent a rotation function. - * - */ + /// Represent a rotation function. template <unsigned n, typename C> struct rotation : fun::internal::x2x_linear_impl_< algebra::vec<n,C>, rotation<n,C> > diff --git a/milena/mln/util/array.hh b/milena/mln/util/array.hh index b5e2534..822a513 100644 --- a/milena/mln/util/array.hh +++ b/milena/mln/util/array.hh @@ -118,6 +118,9 @@ namespace mln /// Resize this array to \p n elements. void resize(unsigned n); + /// Resize this array to \p n elements with \p value as value. + void resize(unsigned n, const T& value); + /// Add the element \p elt at the end of this array. array<T>& append(const T& elt); @@ -329,6 +332,14 @@ namespace mln template <typename T> inline + void + array<T>::resize(unsigned n, const T& value) + { + v_.resize(n, value); + } + + template <typename T> + inline array<T>& array<T>::append(const T& elt) { diff --git a/milena/tests/fun/x2x/rotation.cc b/milena/tests/fun/x2x/rotation.cc index 85b9619..bce3137 100644 --- a/milena/tests/fun/x2x/rotation.cc +++ b/milena/tests/fun/x2x/rotation.cc @@ -31,7 +31,7 @@ /// #include <iostream> -#include <mln/fun/x2x/rotation.hh> +#include <mln/fun/x2v/rotation.hh> #include <mln/core/image/image2d.hh> #include <mln/value/int_u8.hh> #include <mln/io/pgm/load.hh> @@ -56,7 +56,7 @@ int main() io::pgm::load(lena, MLN_IMG_DIR "/lena.pgm"); image2d<int_u8> out(lena.domain()); - interpolated<image2d<int_u8>, fun::x2x::bilinear> inter(lena); + interpolated<image2d<int_u8>, fun::x2v::bilinear> inter(lena); fun::x2x::rotation<2,float> rot1(0.1, axis); diff --git a/milena/tests/unit_test/Makefile.am b/milena/tests/unit_test/Makefile.am index 893238e..953077f 100644 --- a/milena/tests/unit_test/Makefile.am +++ b/milena/tests/unit_test/Makefile.am @@ -459,6 +459,7 @@ mln_canvas_browsing_all \ mln_canvas_browsing_diagonal2d \ mln_canvas_browsing_fwd \ mln_canvas_browsing_dir_struct_elt_incr_update \ +mln_canvas_browsing_depth_first_search \ mln_canvas_browsing_directional \ mln_canvas_browsing_essential \ mln_canvas_chamfer \ @@ -1454,6 +1455,7 @@ mln_canvas_browsing_all_SOURCES = mln_canvas_browsing_all.cc mln_canvas_browsing_diagonal2d_SOURCES = mln_canvas_browsing_diagonal2d.cc mln_canvas_browsing_fwd_SOURCES = mln_canvas_browsing_fwd.cc mln_canvas_browsing_dir_struct_elt_incr_update_SOURCES = mln_canvas_browsing_dir_struct_elt_incr_update.cc +mln_canvas_browsing_depth_first_search_SOURCES = mln_canvas_browsing_depth_first_search.cc mln_canvas_browsing_directional_SOURCES = mln_canvas_browsing_directional.cc mln_canvas_browsing_essential_SOURCES = mln_canvas_browsing_essential.cc mln_canvas_chamfer_SOURCES = mln_canvas_chamfer.cc diff --git a/milena/tests/unit_test/mln_canvas_browsing_depth_first_search.cc b/milena/tests/unit_test/mln_canvas_browsing_depth_first_search.cc new file mode 100644 index 0000000..5073125 --- /dev/null +++ b/milena/tests/unit_test/mln_canvas_browsing_depth_first_search.cc @@ -0,0 +1,8 @@ +// Unit test for mln/canvas/browsing/depth_first_search.hh. +// Generated file, do not modify. +#include <mln/canvas/browsing/depth_first_search.hh> + +int main() +{ + // Nothing. +} -- 1.5.6.5

1 0

3023: Fix 'implies' test and doc tutorial examples.
by Thierry Geraud 10 Dec '08

10 Dec '08

https://svn.lrde.epita.fr/svn/oln/trunk/milena Index: ChangeLog from Thierry Geraud <thierry.geraud(a)lrde.epita.fr> Fix 'implies' test and doc tutorial examples. * doc/tutorial/examples/image_if.cc, * doc/tutorial/examples/image2d.cc, * doc/tutorial/examples/sub_image_if.cc, * doc/tutorial/examples/for_Z.cc, * doc/tutorial/examples/p_run.cc, * doc/tutorial/examples/p_mutable_array_of.cc: Fix missing updates. * mln/core/site_set/p_array.hh: Upgrade doc style. (p_indexed_psite, change_index, dec_index, inc_index): Use update_. (subj_): Do not update_; instead, test that update is effective. * mln/core/contract.hh (implies): Fix. doc/tutorial/examples/for_Z.cc | 2 - doc/tutorial/examples/image2d.cc | 4 +- doc/tutorial/examples/image_if.cc | 4 +- doc/tutorial/examples/p_mutable_array_of.cc | 2 - doc/tutorial/examples/p_run.cc | 2 - doc/tutorial/examples/sub_image_if.cc | 2 - mln/core/contract.hh | 10 +++---- mln/core/site_set/p_array.hh | 40 ++++++++++++++-------------- 8 files changed, 33 insertions(+), 33 deletions(-) Index: doc/tutorial/examples/image_if.cc --- doc/tutorial/examples/image_if.cc (revision 3022) +++ doc/tutorial/examples/image_if.cc (working copy) @@ -72,7 +72,7 @@ // FIXME: border::fill(ima, 0); debug::iota(ima); - mln_VAR(ima_, ima | fun::p2b::chess); + mln_VAR(ima_, ima | fun::p2b::chess()); debug::println(ima); debug::println(ima_); @@ -80,7 +80,7 @@ trait::image::print(ima_); std::cout << std::endl; - typedef p_if<box2d, fun::p2b::chess_t> S; + typedef p_if<box2d, fun::p2b::chess> S; ch_target(mln_fwd_piter_(S)(), ima_.domain()); // mln_VAR(ima_e, extend(ima_, pw::value(ima))); Index: doc/tutorial/examples/image2d.cc --- doc/tutorial/examples/image2d.cc (revision 3022) +++ doc/tutorial/examples/image2d.cc (working copy) @@ -6,7 +6,7 @@ # include <mln/debug/println.hh> # include <mln/core/alias/neighb2d.hh> -# include <mln/estim/nsites.hh> +# include <mln/geom/nsites.hh> template <typename I, typename W, typename P> @@ -45,7 +45,7 @@ debug::iota(ima); debug::println(ima); mln_assertion(ima.nsites() == 6); - mln_assertion(estim::nsites(ima) == ima.nsites()); + mln_assertion(geom::nsites(ima) == ima.nsites()); window2d win; win Index: doc/tutorial/examples/sub_image_if.cc --- doc/tutorial/examples/sub_image_if.cc (revision 3022) +++ doc/tutorial/examples/sub_image_if.cc (working copy) @@ -68,7 +68,7 @@ {1, 0, 1, 1, 1}, {1, 0, 0, 0, 0} }; - image2d<bool> ima = make::image2d(vals); + image2d<bool> ima = make::image(vals); debug::println(ima); int_u8 nlabels; Index: doc/tutorial/examples/for_Z.cc --- doc/tutorial/examples/for_Z.cc (revision 3022) +++ doc/tutorial/examples/for_Z.cc (working copy) @@ -135,7 +135,7 @@ {1, 0, 1, 1, 1}, {1, 0, 0, 0, 0} }; - image2d<bool> ima = make::image2d(vals); + image2d<bool> ima = make::image(vals); debug::println(ima); int_u8 nlabels; Index: doc/tutorial/examples/p_run.cc --- doc/tutorial/examples/p_run.cc (revision 3022) +++ doc/tutorial/examples/p_run.cc (working copy) @@ -32,7 +32,7 @@ {0, 0, 1, 1, 1}, {1, 1, 1, 0, 0} }; - image2d<bool> ima = make::image2d(vals); + image2d<bool> ima = make::image(vals); debug::println(ima); Runs rs; Index: doc/tutorial/examples/p_mutable_array_of.cc --- doc/tutorial/examples/p_mutable_array_of.cc (revision 3022) +++ doc/tutorial/examples/p_mutable_array_of.cc (working copy) @@ -35,7 +35,7 @@ {0, 0, 1, 1, 1}, {1, 1, 1, 0, 0} }; - image2d<bool> ima = make::image2d(vals); + image2d<bool> ima = make::image(vals); debug::println(ima); typedef p_mutable_array_of< p_run<point2d> > Runs; Index: mln/core/site_set/p_array.hh --- mln/core/site_set/p_array.hh (revision 3022) +++ mln/core/site_set/p_array.hh (working copy) @@ -28,15 +28,14 @@ #ifndef MLN_CORE_SITE_SET_P_ARRAY_HH # define MLN_CORE_SITE_SET_P_ARRAY_HH -/*! \file mln/core/site_set/p_array.hh - * - * \brief Definition of a point set class based on std::vector. - * - * \todo Add a facade to index_of_in so that it dispatches when - * calling it with Object<p_array_site>. - * - * \todo Use util::index (instead of int) as many times as possible. - */ +/// \file mln/core/site_set/p_array.hh +/// +/// Definition of a point set class based on std::vector. +/// +/// \todo Add a facade to index_of_in so that it dispatches when +/// calling it with Object<p_array_site>. +/// +/// \todo Use util::index (instead of int) as many times as possible. # include <vector> @@ -74,10 +73,10 @@ - /*! \brief Site set class based on std::vector. - * - * This is a multi-set of sites. - */ + /// Site set class based on std::vector. + /// + /// This is a multi-set of sites. + /// template <typename P> class p_array : public internal::site_set_base_< P, p_array > { @@ -172,8 +171,8 @@ - // p_indexed_psite - + /// Psite class for indexed site sets such as p_array. + /// template <typename S> class p_indexed_psite : public internal::pseudo_site_base_< const mln_element(S)&, p_indexed_psite<S> > @@ -498,6 +497,7 @@ : s_(& s), i_(i) { + update_(); } template <typename S> @@ -514,6 +514,7 @@ p_indexed_psite<S>::change_index(int i) { i_ = i; + update_(); } template <typename S> @@ -522,6 +523,7 @@ p_indexed_psite<S>::dec_index() { --i_; + update_(); } template <typename S> @@ -530,6 +532,7 @@ p_indexed_psite<S>::inc_index() { ++i_; + update_(); } template <typename S> @@ -562,7 +565,8 @@ const mln_element(S)& p_indexed_psite<S>::subj_() { - update_(); // In case of... + if (is_valid()) + mln_invariant(p_ == (*s_)[i_]); return p_; } @@ -621,7 +625,6 @@ p_indexed_fwd_piter<S>::start_() { p_.change_index(0); - p_.update_(); } template <typename S> @@ -630,7 +633,6 @@ p_indexed_fwd_piter<S>::next_() { p_.inc_index(); - p_.update_(); } template <typename S> @@ -680,7 +682,6 @@ p_indexed_bkd_piter<S>::start_() { p_.change_index(s_->nsites() - 1); - p_.update_(); } template <typename S> @@ -689,7 +690,6 @@ p_indexed_bkd_piter<S>::next_() { p_.dec_index(); - p_.update_(); } template <typename S> Index: mln/core/contract.hh --- mln/core/contract.hh (revision 3022) +++ mln/core/contract.hh (working copy) @@ -1,4 +1,5 @@ // 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 @@ -28,10 +29,9 @@ #ifndef MLN_CORE_CONTRACT_HH # define MLN_CORE_CONTRACT_HH -/*! \file mln/core/contract.hh - * - * \brief Definition of the set of contracts. - */ +/// \file mln/core/contract.hh +/// +/// Definition of the set of contracts. # include <cassert> @@ -70,7 +70,7 @@ inline bool implies(bool lexpr, bool rexpr) { - return ! (rexpr) || (lexpr); + return (! lexpr) || rexpr; } # endif // ! MLN_INCLUDE_ONLY

1 0