https://svn.lrde.epita.fr/svn/oln/trunk/milena/sandbox Index: ChangeLog from Ugo Jardonnet &lt;ugo.jardonnet(a)lrde.epita.fr&gt; Add n_cmpt4 : version without util::set. * jardonnet/n_cmpt/n_cmpt3.hh: Minor fix for test. * jardonnet/n_cmpt/n_cmpt3.cc: Add 1d test. * jardonnet/n_cmpt/n_cmpt4.hh: New version without util::set. * jardonnet/n_cmpt/n_cmpt4.cc: New main. * jardonnet/n_cmpt/Makefile: Add n_cmpt4 rules. * jardonnet/n_cmpt/tiny_seg15.pgm: New. * jardonnet/n_cmpt/seg15.pgm: New. Makefile | 7 + n_cmpt3.cc | 8 +- n_cmpt3.hh | 37 ++++++---- n_cmpt4.cc | 48 +++++++++++++ n_cmpt4.hh | 208 +++++++++++++++++++++++++++++++++++++++++++++++++++++++++ seg15.pgm | 5 + tiny_seg15.pgm | 5 + 7 files changed, 304 insertions(+), 14 deletions(-) Index: jardonnet/n_cmpt/n_cmpt3.hh --- jardonnet/n_cmpt/n_cmpt3.hh (revision 3002) +++ jardonnet/n_cmpt/n_cmpt3.hh (working copy) @@ -100,9 +100,10 @@ initialize(volume_set, min_v); // number of minima - int cmpts = label; + unsigned cmpts = label; - std::cout << "Nb of regionnal minima : " << cmpts << std::endl; + if (lambda > cmpts) + std::cout << "warning : lambda value is to hight." << std::endl; // prepare union find typedef mln_psite(V) P; @@ -122,13 +123,18 @@ volume_set(p).insert(min_v(p)); } } + + std::cout << "cmpts | volume_set | " << std::endl; + std::cout << cmpts << " : "; debug::println(volume_set); + 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 << p << std::endl; //if (volume(p) > lambda) // goto step2; for_all(n) @@ -141,18 +147,29 @@ { // One cmpt less if if (volume(r) != volume(p)) // r and p have differerent volumes - if (not volume_set(p).is_empty()) // r already belong to a cmpt + if (not volume_set(p).is_empty()) // p already belong to a cmpt if (volume_set(p) != volume_set(r)) // cmpt r and p are different - if (cmpts > lambda) // union is still alowed + { + if (cmpts >= lambda) // unions still allowed cmpts--; + } + else + { + // should not happen since we test that (r != p) + std::cout << "IT HAPPEND !!!!!!!!!!!!!!!!!!!" << std::endl; + exit(42); + } - if (cmpts > lambda || + if (cmpts >= lambda || volume(r) == volume(p) || volume_set(p).is_empty()) { parent(r) = p; // propagate set volume_set(p).insert(volume_set(r)); + + std::cout << "volume " << volume(p) << " - " << cmpts << " : " << std::endl; + debug::println(volume_set); } } } @@ -160,9 +177,9 @@ deja_vu(p) = true; } - step2: - debug::println(volume_set); - std::cout << "Nb cmpts after processing : " << cmpts << std::endl; +// step2: + std::cout << std::endl; + std::cout << "cmpts : " << cmpts << std::endl; // second pass I output(ima.domain()); @@ -175,10 +192,6 @@ output(p) = output(parent(p)); } - std::cout << "/output/" << std::endl; - debug::println(output); - assert(output != input); - return output; } Index: jardonnet/n_cmpt/n_cmpt4.hh --- jardonnet/n_cmpt/n_cmpt4.hh (revision 0) +++ jardonnet/n_cmpt/n_cmpt4.hh (revision 0) @@ -0,0 +1,208 @@ +// 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/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<I> 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 << p << std::endl; + //if (volume(p) > 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; + } + +// 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) = ima(p); //(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/seg15.pgm --- jardonnet/n_cmpt/seg15.pgm (revision 0) +++ jardonnet/n_cmpt/seg15.pgm (revision 0) @@ -0,0 +1,5 @@ +P5 +# CREATOR: GIMP PNM Filter Version 1.1 +16 16 +255 +������������Ȯ��������������Ȯ��������������Ȯ��������������Ȯ��������������Ȯ������������Ȯ�����������������������������������җ��������������җ��������������җ�dd�����������җ�dd�����������Ǘ�ggg�������������ggg�������������gggg������������gggg���������� \ No newline at end of file Index: jardonnet/n_cmpt/n_cmpt3.cc --- jardonnet/n_cmpt/n_cmpt3.cc (revision 3002) +++ jardonnet/n_cmpt/n_cmpt3.cc (working copy) @@ -6,6 +6,7 @@ #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> @@ -34,9 +35,12 @@ io::pgm::load(ima, argv[1]); unsigned lambda = atoi(argv[2]); - int_u8 tab[] = {2,3,1,0,2,3,2,2,1}; + 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); - io::pgm::save(n_cmpt::n_cmpt3(ima1, c4(), lambda), + 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 0) +++ jardonnet/n_cmpt/n_cmpt4.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_cmpt4.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/tiny_seg15.pgm --- jardonnet/n_cmpt/tiny_seg15.pgm (revision 0) +++ jardonnet/n_cmpt/tiny_seg15.pgm (revision 0) @@ -0,0 +1,5 @@ +P5 +# CREATOR: GIMP PNM Filter Version 1.1 +16 16 +255 +�����������Ȱ�n��{�����������u=Uhx�����׸����EZIgv������ټ��\S�Mmv����������V��Opv����]a����e��Opv��U<:o�v?$����pz�W60az�j-)��Z�q��@1IsFiA,8��ft��E5?OjqmH.Hj��u�dRGKV���71bf��o�\SXXAp�O%7fc���RKgW=d�yH:RU�m��I;WhIx��VY|�[��H6LFX����k�jV��D@JAp�����flUO \ No newline at end of file Index: jardonnet/n_cmpt/Makefile --- jardonnet/n_cmpt/Makefile (revision 3002) +++ jardonnet/n_cmpt/Makefile (working copy) @@ -7,6 +7,9 @@ n_cmpt3: n_cmpt3.hh n_cmpt3.cc g++ -I../../.. -Wall -W -Wextra n_cmpt3.cc -DNDEBUG -O1 -o n_cmpt3 +n_cmpt4: n_cmpt4.hh n_cmpt4.cc + g++ -I../../.. -Wall -W -Wextra n_cmpt4.cc -DNDEBUG -O1 -o n_cmpt4 + debug: n_cmpt.hh n_cmpt.cc g++ -I../../.. -Wall -W -Wextra n_cmpt.cc -g -g3 -o n_cmpt @@ -15,3 +18,7 @@ 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 + Index: jardonnet/n_cmpt/check/test.pgm Cannot display: file marked as a binary type. svn:mime-type = application/octet-stream