January 2009 - Olena-patches

3177: Update INIM.
by Ugo Jardonnet 21 Jan '09

21 Jan '09

https://svn.lrde.epita.fr/svn/oln/trunk/milena/sandbox Index: ChangeLog from Ugo Jardonnet <ugo.jardonnet(a)lrde.epita.fr> Update INIM. * jardonnet/virtual/access.cc: Update. * inim/classif/src/iccvg04.cc: Fix signature. * inim/classif/src/proj.hh: Fix include. * inim/classif/src/v2.cc: Fix include. * inim/classif/Makefile: Make all. inim/classif/Makefile | 1 + inim/classif/src/iccvg04.cc | 5 ++--- inim/classif/src/proj.hh | 2 +- inim/classif/src/v2.cc | 3 +-- jardonnet/virtual/access.cc | 6 +----- 5 files changed, 6 insertions(+), 11 deletions(-) Index: jardonnet/virtual/access.cc --- jardonnet/virtual/access.cc (revision 3176) +++ jardonnet/virtual/access.cc (working copy) @@ -84,13 +84,9 @@ mln_VAR(rt, compose(r,t)); mln_VAR(tr_ima, transposed_image(interp.domain(), interp, rt)); - // data::fill(output, tr_ima); - - - //border::adjust(interp, 20); - //test1<interpolation::bilinear>(input, output, compose(r,t)); test2(interp, output, compose(r,t)); //test3(tr_ima, output); + mln::io::ppm::save(output,"./out.ppm"); } Index: inim/classif/src/iccvg04.cc --- inim/classif/src/iccvg04.cc (revision 3176) +++ inim/classif/src/iccvg04.cc (working copy) @@ -2,7 +2,6 @@ #include <mln/core/image/image2d.hh> #include <mln/core/image/image3d.hh> -#include <mln/histo/data.hh> #include <mln/value/all.hh> #include <mln/data/fill.hh> @@ -158,8 +157,8 @@ image3d<unsigned> histo = fill_histo(ima,div_factor); //compute opening_volume of histo - image3d<unsigned> histo_filtered(histo.domain()); - morpho::opening_volume(histo, c6(), lambda, histo_filtered); + image3d<unsigned> histo_filtered; + histo_filtered = morpho::opening_volume(histo, c6(), lambda); //watershed over histo_closure unsigned nbasins = 0; Index: inim/classif/src/proj.hh --- inim/classif/src/proj.hh (revision 3176) +++ inim/classif/src/proj.hh (working copy) @@ -35,7 +35,7 @@ #include <mln/accu/maj_h.hh> #include <mln/literal/white.hh> #include <mln/literal/colors.hh> -#include <mln/make/vec.hh +#include <mln/make/vec.hh> #include <mln/opt/at.hh> namespace mln Index: inim/classif/src/v2.cc --- inim/classif/src/v2.cc (revision 3176) +++ inim/classif/src/v2.cc (working copy) @@ -1,6 +1,5 @@ #include <mln/core/image/image2d.hh> #include <mln/core/image/image3d.hh> -#include <mln/histo/data.hh> #include <mln/value/all.hh> @@ -65,7 +64,7 @@ // FIXME: write a compute() method with functor argument image3d<unsigned> nb_represent = run.compute_nb_represent(); - image3d<unsigned> volume = run.compute_volume(); + image3d<unsigned> volume = run.compute_volume(); // surface (area) image3d< algebra::vec<3, double> > mean_color = run.compute_mean_color(); image3d<double> density = compute_density(nb_represent, volume); Index: inim/classif/Makefile --- inim/classif/Makefile (revision 3176) +++ inim/classif/Makefile (working copy) @@ -19,6 +19,7 @@ LOG=> stdout.log 2> stderr.log +all: $(ICCVG) $(V2) $(ICCVG): $(ICCVG_SRC) g++ $(ICCVG_INCLUDES) -O1 -DNDEBUG $(ICCVG_SRC) -o $(ICCVG) Index: theo/tufa_2008/filter_n.cc

1 0

3176: Add children computation to Laurent's code.
by Thierry Geraud 21 Jan '09

21 Jan '09

https://svn.lrde.epita.fr/svn/oln/trunk/milena/sandbox Index: ChangeLog from Thierry Geraud <thierry.geraud(a)lrde.epita.fr> Add children computation to Laurent's code. * laurent/ismm2009.cc: Add children + root computation. ismm2009.cc | 77 ++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++ 1 file changed, 77 insertions(+) Index: laurent/ismm2009.cc --- laurent/ismm2009.cc (revision 3175) +++ laurent/ismm2009.cc (working copy) @@ -366,6 +366,41 @@ } + + // From parent image to children image. + + template <typename I, typename E, typename L> + mln_ch_value(I, std::vector<mln_psite(I)>) + compute_children(const I& epar, const std::vector<E>& edge, L l_max, std::vector<E>& roots) + { + typedef std::vector<mln_psite(I)> C; // Children. + mln_ch_value(I,C) chl; + initialize(chl, epar); + + mln_ch_value(I,bool) deja_vu; + initialize(deja_vu, epar); + data::fill(deja_vu, false); + + for (L l = 1; l <= l_max; ++l) + { + E e = edge[l]; + while (deja_vu(e) == false) + { + deja_vu(e) = true; + if (epar(e) != e) + { + chl(epar(e)).push_back(e); + e = epar(e); + } + else + roots.push_back(e); + } + } + + return chl; + } + + } // mln @@ -762,6 +797,48 @@ } // end of "for every region with increasing attribute" + std::vector<E> roots; + mln_VAR(chl, compute_children(epar, edge, n_basins, roots)); + + // Connected domain so: + mln_invariant(roots.size() == 1); + + E root = roots[0]; // THE root. + + + if (echo) + { + std::cout << "root: " << root << std::endl; + + // Display edge tree. + mln_ch_value_(chl_t, bool) deja_vu; + initialize(deja_vu, chl); + data::fill(deja_vu, false); + std::cout << "edge tree: " << std::endl; + for (L l = 1; l <= n_basins; ++l) + { + std::cout << l << ": "; + E e = edge[l]; + while (! deja_vu(e)) + { + std::cout << e << " -> "; + deja_vu(e) = true; + e = epar(e); + } + std::cout << e << std::endl; + } + + // Display children. + mln_piter_(chl_t) e(chl.domain()); + for_all(e) + if (chl(e).size() != 0) + { + std::cout << e << " children: "; + for (unsigned i = 0; i < chl(e).size(); ++i) + std::cout << chl(e)[i] << " "; + std::cout << std::endl; + } + } std::cout << "Computing tree (loop over regions): " << timer << " s" << std::endl;

1 0

3175: Add activity to morphology algebraic canvas.
by Thierry Geraud 21 Jan '09

21 Jan '09

https://svn.lrde.epita.fr/svn/oln/trunk/milena Index: ChangeLog from Thierry Geraud <thierry.geraud(a)lrde.epita.fr> Add activity to morphology algebraic canvas. * mln/canvas/morpho/algebraic_union_find.hh (activity): New. This allows for accumulators that cannot properly implement set_value to work with algebraic filters and levelings. * mln/test/predicate.hh: Fix signature. canvas/morpho/algebraic_union_find.hh | 10 +++++++++- test/predicate.hh | 12 ++++++------ 2 files changed, 15 insertions(+), 7 deletions(-) Index: mln/test/predicate.hh --- mln/test/predicate.hh (revision 3174) +++ mln/test/predicate.hh (working copy) @@ -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_TEST_PREDICATE_HH # define MLN_TEST_PREDICATE_HH -/*! \file mln/test/predicate.hh - * - * \brief Test a predicate on the pixel values of an image. - */ +/// \file mln/test/predicate.hh +/// +/// Test a predicate on the pixel values of an image. # include <mln/core/concept/image.hh> # include <mln/core/concept/function.hh> @@ -62,7 +62,7 @@ * \param[in] f The predicate. */ template <typename I, typename J, typename F> - bool predicate(const Image& lhs, const Image<J>& rhs, const Function_v2b<F>& f); + bool predicate(const Image& lhs, const Image<J>& rhs, const Function_vv2b<F>& f); /*! Test if all points of \p pset verify the predicate \p f. Index: mln/canvas/morpho/algebraic_union_find.hh --- mln/canvas/morpho/algebraic_union_find.hh (revision 3174) +++ mln/canvas/morpho/algebraic_union_find.hh (working copy) @@ -98,6 +98,7 @@ // Auxiliary data. mln_ch_value(O, bool) deja_vu; + mln_ch_value(I, bool) activity; mln_ch_value(O, P) parent; mln_ch_value(O, A) data; @@ -105,6 +106,8 @@ { initialize(deja_vu, input); mln::data::fill(deja_vu, false); + initialize(activity, input); + mln::data::fill(activity, true); initialize(parent, input); initialize(data, input); f.init(); // init required. @@ -151,7 +154,7 @@ P r = find_root(parent, n); if (r != p) { - if (input(r) == input(p) || f.is_active(data(r))) // Equiv(r, p) + if (input(r) == input(p) || (activity(r) && f.is_active(data(r)))) // Equiv(r, p) // Either a flat zone or the component of r is still growing. { /* FIXME: Same remark as above concerning the @@ -168,11 +171,16 @@ template parameter A is not bound). */ data(p).take(data(r)); parent(r) = p; + if (activity(r) == false) + activity(p) = false; } else + { + activity(p) = false; f.inactivate(data(p)); } } + } deja_vu(p) = true; } }

1 0

3174: Improve LCA in Laurent's code.
by Thierry Geraud 20 Jan '09

20 Jan '09

https://svn.lrde.epita.fr/svn/oln/trunk/milena/sandbox Index: ChangeLog from Thierry Geraud <thierry.geraud(a)lrde.epita.fr> Improve LCA in Laurent's code. * laurent/ismm2009.cc: Improve LCA. * laurent/ismm2009.v2.cc: Add a timer. ismm2009.cc | 298 ++++++++++++++++++++++++++++++++++++--------------------- ismm2009.v2.cc | 6 + 2 files changed, 198 insertions(+), 106 deletions(-) Index: laurent/ismm2009.cc --- laurent/ismm2009.cc (revision 3173) +++ laurent/ismm2009.cc (working copy) @@ -19,6 +19,10 @@ #include <mln/labeling/compute.hh> #include <mln/accu/count.hh> +#include <mln/util/timer.hh> +#include <mln/util/fibonacci_heap.hh> + + /* TO-DO list: @@ -137,79 +141,114 @@ const std::vector<E>& edge, const Epar& epar) { - mln_ch_value(Epar, std::vector<L>) chl_; // Children (known as array). + std::cout << "LCA computing..."; + std::cout.flush(); + + mln_ch_value(Epar, std::vector<L>) chl; // Children (known as array). + initialize(chl, epar); + + unsigned size = l_max.next(); + + std::vector< std::vector<E> > lca(size); + for (L l = 1; l <= l_max; ++l) { - initialize(chl_, epar); + lca[l].resize(size); + lca[l][l] = edge[l]; // Diagonal => itself. + } + std::vector<bool> deja_vu(size); + E e; - for (L l = 1; l <= l_max; ++l) + + // The 1st label (l = 1) is a special case since + // we cannot have lca[1][i] with i < 1! { - e = edge[l]; + e = edge[1]; do { - chl_(e).push_back(l); + chl(e).push_back(1); e = epar(e); } while (e != epar(e)); - chl_(e).push_back(l); - } - // e is the root edge. - mln_invariant(chl_(e).size() == l_max); // All labels are children. + chl(e).push_back(1); } - /* - // Display children tree. + + for (L l = 2; l <= l_max; ++l) { - std::cout << "chl_ tree: " << std::endl; - for (L l = 1; l <= l_max; ++l) + std::fill(deja_vu.begin(), deja_vu.end(), false); + e = edge[l]; + for (;;) { - E e_ = edge[l]; - std::cout << "l = " << l << " => "; - do + std::vector<L>& chl_e = chl(e); + unsigned n = chl_e.size(); + + // Compute lca[l_][l] with l_ = 1..l-1 + for (unsigned i = 0; i < n; ++i) { - std::cout << e_ << " : "; - for (unsigned i = 0; i < chl_(e_).size(); ++i) - std::cout << chl_(e_)[i] << ' '; - std::cout << " -> "; - e_ = epar(e_); + if (deja_vu[chl_e[i]]) + continue; + L l_ = chl_e[i]; + mln_invariant(l_ < l); + lca[l_][l] = e; + deja_vu[l_] = true; } - while (epar(e_) != e_); - std::cout << e_ << " : "; - for (unsigned i = 0; i < chl_(e_).size(); ++i) - std::cout << chl_(e_)[i] << ' '; - std::cout << std::endl; + + // Update 'chl' with l; + chl(e).push_back(l); + + if (e == epar(e)) // Root so stop. + break; + e = epar(e); // Otherwise go to parent. } } - */ - mln_ch_value(Epar, std::set<L>) chl; // Children (as a set). - { - initialize(chl, epar); + // e is the root node; we have processed all labels + // so they are stored as the children of e: + mln_invariant(chl(e).size() == l_max); // All labels are children. - mln_piter(Epar) e(chl.domain()); - for_all(e) - if (chl_(e).size() != 0) - chl(e).insert(chl_(e).begin(), chl_(e).end()); - } - unsigned size = l_max.next(); +// // Save the LCA into a file. +// { +// std::ofstream out("lca.txt"); - std::vector< std::vector<E> > lca(size); - for (L l = 1; l <= l_max; ++l) - { - lca[l].resize(size); +// for (L l = 1; l <= l_max; ++l) +// { +// out << "l = " << l << ": "; +// for (L l2 = l; l2 <= l_max; ++l2) +// { +// out << lca[l][l2] << ' '; +// } +// out << std::endl; +// } +// out.close(); - // Diagonal. - lca[l][l] = edge[l]; // Itself. - // Superior right. - for (L l2 = l.next(); l2 <= l_max; ++l2) - { - E e = edge[l]; - while (chl(e).find(l2) == chl(e).end()) - e = epar(e); - lca[l][l2] = e; - } - } + +// // Display children tree. +// { +// std::cout << "chl tree: " << std::endl; +// for (L l = 1; l <= l_max; ++l) +// { +// E e_ = edge[l]; +// std::cout << "l = " << l << " => "; +// do +// { +// std::cout << e_ << " : "; +// for (unsigned i = 0; i < chl(e_).size(); ++i) +// std::cout << chl(e_)[i] << ' '; +// std::cout << " -> "; +// e_ = epar(e_); +// } +// while (epar(e_) != e_); +// std::cout << e_ << " : "; +// for (unsigned i = 0; i < chl(e_).size(); ++i) +// std::cout << chl(e_)[i] << ' '; +// std::cout << std::endl; +// } +// } + + + std::cout << "done!" << std::endl; return lca; } @@ -352,6 +391,17 @@ if (argc != 4) usage(argv); + util::timer timer; + + + + // Step 1. From f to wst_g. + // ------------------------------------------------------------------------------ + + + timer.start(); + + image2d<int_u8> raw_f; io::pgm::load(raw_f, argv[1]); @@ -432,61 +482,15 @@ - - // Priority queue -> edge. - - typedef p_priority< T, p_queue<E> > Q; - util::array<Q> q(n_basins.next()); - - { - mln_piter_(g_t) e(g.domain()); - for_all(e) - if (wst_g(e) == 0) - { - L l1 = wst_g_full(p1_from_e(e)), - l2 = wst_g_full(p2_from_e(e)); - if (l1 > l2) - std::swap(l1, l2); - mln_invariant(l1 < l2); - q[l1].push(mln_max(T) - g(e), e); - q[l2].push(mln_max(T) - g(e), e); - } - // --- for (L l = 1; l <= n_basins; ++l) - // --- std::cout << "q["<< l << "] = " << q[l] << std::endl; - } + std::cout << "Computing wst(g) from f: " << timer << " s" << std::endl; + // Step 2. From wst(g) -> a. + // ------------------------------------------------------------------------------ - // To know if an edge is out of a given region (label l), we - // maintain the information about region merging using - // an union-find structure. - std::vector<L> lpar(n_basins.next()); - make_sets(lpar, n_basins); - - - // Given a region R with label l and an edge e = (l1, l2) from the - // priority queue, we get know if that edge is out of the set of - // regions containing l: we shall have l1r = lr or l2r = lr. - - // Please note that an edge (l1, l2) is internal to a set of regions - // if l1r = l2r. - - - - E null = E(0,0); // Impossible value. - - - // Information "label l -> edge e". - - std::vector<E> edge(n_basins.next()); - for (L l = 1; l <= n_basins; ++l) - edge[l] = null; - - - - + timer.restart(); @@ -525,15 +529,57 @@ } + std::cout << "Computing region attributes: " << timer << " s" << std::endl; - // Go! - // -------------------------------- + + + // Step 3. wst(g) + a ---> tree "e->e" + array "l->e" + aa. + // ------------------------------------------------------------------------------ + + + timer.restart(); + + + + // Edges -> Priority queue. + + typedef p_priority< T, p_queue<E> > Q; + // typedef util::fibonacci_heap<T, E> Q; + + util::array<Q> q(n_basins.next()); + + { + mln_piter_(g_t) e(g.domain()); + for_all(e) + if (wst_g(e) == 0) + { + L l1 = wst_g_full(p1_from_e(e)), + l2 = wst_g_full(p2_from_e(e)); + if (l1 > l2) + std::swap(l1, l2); + mln_invariant(l1 < l2); + q[l1].push(mln_max(T) - g(e), e); + q[l2].push(mln_max(T) - g(e), e); + } + // --- for (L l = 1; l <= n_basins; ++l) + // --- std::cout << "q["<< l << "] = " << q[l] << std::endl; + } + + + // Information "label l -> edge e". + + E null = E(0,0); // Impossible value. + + std::vector<E> edge(n_basins.next()); + for (L l = 1; l <= n_basins; ++l) + edge[l] = null; mln_ch_value_(g_line_t, E) epar, // Edge forest. z_epar; // Auxiliary data: edge forest with compression and balancing. + { initialize(epar, g_line); initialize(z_epar, g_line); @@ -549,6 +595,20 @@ } + // To know if an edge is out of a given region (label l), we + // maintain the information about region merging using + // an union-find structure. + std::vector<L> lpar(n_basins.next()); + make_sets(lpar, n_basins); + + // Given a region R with label l and an edge e = (l1, l2) from the + // priority queue, we get know if that edge is out of the set of + // regions containing l: we shall have l1r = lr or l2r = lr. + + // Please note that an edge (l1, l2) is internal to a set of regions + // if l1r = l2r. + + // 'aa' is the result attribute image; it is defined on the complex // (so it has edges, pixels, and 0-face-points). @@ -607,8 +667,13 @@ std::cout << "q[l2r] = " << q[l2r] << std::endl; */ - q[l2r].insert(q[l1r]); - q[l1r].clear(); + + q[l2r].insert(q[l1r]); // With p_priority<Q>. + q[l1r].clear(); // + + // q[l2r].push(q[l1r]); // With Fib-Heap. + + /* std::cout << "q[l2r] = " << q[l2r] << std::endl @@ -699,6 +764,21 @@ + std::cout << "Computing tree (loop over regions): " << timer << " s" << std::endl; + + + + + // Step 4. Final. + // ------------------------------------------------------------------------------ + + + timer.restart(); + + + +# ifndef NDEBUG + // About the "edge tree" and attributes. { @@ -783,7 +863,6 @@ } } - // Reminders: if (echo) { @@ -791,6 +870,9 @@ debug::println("g_line:", g_line); } +# endif // ndef NDEBUG + + // +---------------------------------------------------------------+ @@ -809,6 +891,7 @@ // First, processing the 1D-faces (edges) of the watershed line. std::vector< std::vector<E> > lca; + lca = compute_lca(n_basins, edge, epar); // lca is auxiliary data. mln_piter_(g_line_t) e(g_line.domain()); @@ -898,6 +981,9 @@ debug::println("aa:", aa); + std::cout << "Final: " << timer << " s" << std::endl; + + // Output is salency map. { Index: laurent/ismm2009.v2.cc --- laurent/ismm2009.v2.cc (revision 3173) +++ laurent/ismm2009.v2.cc (working copy) @@ -19,6 +19,8 @@ #include <mln/labeling/compute.hh> #include <mln/accu/count.hh> +#include <mln/util/timer.hh> + /* TO-DO list: @@ -561,6 +563,9 @@ // The last iteration (i == n_basins) is useless: all regions have // already merged. + util::timer timer; + timer.start(); + for (unsigned i = 1; i < n_basins; ++i) { L l = v[i].second; // Region label. @@ -697,6 +702,7 @@ } // end of "for every region with increasing attribute" + std::cout << "loop over regions: " << timer << " s" << std::endl; // About the "edge tree" and attributes.

1 0

3173: Augment Laurent's ISMM code.
by Thierry Geraud 20 Jan '09

20 Jan '09

https://svn.lrde.epita.fr/svn/oln/trunk/milena/sandbox Index: ChangeLog from Thierry Geraud <thierry.geraud(a)lrde.epita.fr> Augment Laurent's ISMM code. * laurent/playing_with_attributes.cc: Augment. * laurent/ismm2009.cc: Memorize as... * laurent/ismm2009.v2.cc: ...this new file. * laurent/ismm2009.cc: Augment. ismm2009.cc | 67 ++++++++----- ismm2009.v2.cc | 67 ++++++++----- playing_with_attributes.cc | 224 +++++++++++++++++++++++++++++++++++++++++++-- 3 files changed, 299 insertions(+), 59 deletions(-) Index: laurent/ismm2009.cc --- laurent/ismm2009.cc (revision 3172) +++ laurent/ismm2009.cc (working copy) @@ -1,10 +1,13 @@ #include "ismm2009.hh" #include <mln/value/int_u8.hh> + +#include <mln/io/pgm/load.hh> +#include <mln/io/pgm/save.hh> + #include <mln/value/label_8.hh> #include <mln/value/label_16.hh> -#include <mln/io/pgm/load.hh> #include <mln/util/ord_pair.hh> #include <mln/debug/println.hh> #include <mln/core/routine/duplicate.hh> @@ -18,14 +21,9 @@ /* - TO-DO list: - ----------- - - - having a heap for every lr (support merge) - handling adjacency on the fly (instead of having an image) - */ @@ -266,7 +264,7 @@ typename N_e2e, typename L > mln_ch_value(G, L) - f_to_wst_unique_g(F& f, // On pixels. + compute_wst_g_from_f(F& f, // On pixels. G& g, // On edges. const N_e2p& e2p, const N_e2e& e2e, @@ -277,7 +275,7 @@ e2p.win()), g); - // FIXME: Here, we want a unique value per edge! +# ifdef MAKE_UNIQUE if (echo) debug::println("g (before):", g); @@ -311,6 +309,9 @@ } } +# endif // MAKE_UNIQUE + + mln_VAR( wst_g, morpho::meyer_wst(g, e2e, n_basins) ); @@ -333,8 +334,9 @@ void usage(char* argv[]) { - std::cerr << "usage: " << argv[0] << " input.pgm" << std::endl; - std::cerr << "Laurent ISMM 2009 scheme." << std::endl; + std::cerr << "usage: " << argv[0] << " input.pgm echo output.pgm" << std::endl; + std::cerr << "Laurent ISMM 2009 scheme with saliency map as output." << std::endl; + std::cerr << " echo = 0 or 1." << std::endl; abort(); } @@ -347,14 +349,20 @@ using value::int_u8; using value::label_16; - bool echo = true; - - if (argc != 2) + if (argc != 4) usage(argv); image2d<int_u8> raw_f; io::pgm::load(raw_f, argv[1]); + bool echo; + { + int echo_ = std::atoi(argv[2]); + if (echo_ != 0 && echo_ != 1) + usage(argv); + echo = bool(echo_); + } + typedef image2d<int_u8> Complex; typedef mln_pset_(Complex) full_D; @@ -372,15 +380,9 @@ L n_basins; - mln_VAR( wst_g, - f_to_wst_g(f, g, e2p(), e2e(), n_basins) ); - - /* - UNIQUE: mln_VAR( wst_g, - f_to_wst_unique_g(f, g, e2p(), e2e(), n_basins, echo) ); - */ + compute_wst_g_from_f(f, g, e2p(), e2e(), n_basins, echo) ); if (echo) @@ -501,11 +503,12 @@ std::vector<pair_t> v = sort_attributes(a, n_basins); // Sort regions. + // Optional code (for testing purpose): change attributes + // so that they are all different. - // Maybe activate to test purpose: - /* +# ifdef MAKE_UNIQUE make_unique_attribute(a, v, n_basins, echo); - */ +# endif // Display attributes. @@ -796,13 +799,13 @@ // +---------------------------------------------------------------+ - { - // Dealing with the watershed line. mln_VAR(aa_line, aa | is_line); { + + { // First, processing the 1D-faces (edges) of the watershed line. std::vector< std::vector<E> > lca; @@ -886,16 +889,26 @@ } if (echo) - debug::println("aa | basins", aa_basins); + debug::println("aa | basins:", aa_basins); } - if (echo) debug::println("aa:", aa); + + // Output is salency map. + { + + image2d<int_u8> output(f_.domain()); + data::fill(output, 0); + data::paste(aa_line, output); + io::pgm::save(output, argv[3]); + } + + } // end of main Index: laurent/playing_with_attributes.cc --- laurent/playing_with_attributes.cc (revision 3172) +++ laurent/playing_with_attributes.cc (working copy) @@ -13,6 +13,10 @@ #include <mln/morpho/tree/compute_attribute_image.hh> #include <mln/labeling/regional_minima.hh> +#include <mln/core/site_set/p_array.hh> +#include <mln/level/sort_psites.hh> +#include <mln/geom/nsites.hh> + #include <mln/accu/count.hh> @@ -26,6 +30,200 @@ +namespace mln +{ + + + template <typename T> + struct node_pred : Function_p2b< node_pred<T> > + { + typedef bool result; + + template <typename P> + bool operator()(const P& p) const + { + return t->is_a_node(p); + } + + const T* t; + }; + + + + template <typename T, typename I> + void depict_tree_attributes(const T& t, // Tree. + const I& a) // Attribute image. + { + typedef mln_site(I) P; + + mln_ch_value(I, bool) deja_vu; + initialize(deja_vu, a); + data::fill(deja_vu, false); + + typedef typename T::nodes_t nodes_t; + mln_fwd_piter(nodes_t) p(t.nodes()); + for_all(p) + { + if (deja_vu(p)) + continue; + + P e = p; + do + { + std::cout << a(e) << ':' << e << " -> "; + deja_vu(e) = true; + e = t.parent(e); + } + while (! deja_vu(e)); + std::cout << a(e) << ':' << e << std::endl; + } + std::cout << std::endl; + } + + + template <typename T, typename I> + mln_concrete(I) + change_tree_attributes(const T& t, // Tree. + const I& a, // Attribute image. + bool echo = false) + { + typedef mln_site(I) P; + typedef mln_value(I) A; // Type of attributes. + + // Test that attributes increase with parenthood. + mln_fwd_piter(T) p(t.domain()); + for_all(p) + if (t.is_a_non_root_node(p)) + { + mln_assertion(t.is_a_node(t.parent(p))); + mln_invariant(a(t.parent(p)) >= a(p)); + } + + + if (echo) + depict_tree_attributes(t, a); + + + node_pred<T> node_only; + node_only.t = &t; + + typedef p_array S; + S s = level::sort_psites_increasing(a | node_only); + mln_invariant(geom::nsites(a | t.nodes()) == s.nsites()); + + + mln_ch_value(I, bool) mark; + initialize(mark, a); + data::fill(mark, false); + + + // Modify attributes. + + mln_concrete(I) aa; + initialize(aa, a); + data::fill(aa, 0); + + { + + P e, par_e; + A v; + bool found; + + mln_fwd_piter(S) p(s); + + // Initialization. + for_all(p) + { + if (mark(p) == true) + continue; + + // First, fetch the attribute value v from p; + e = p; + found = false; + while (mark(e) == false && e != t.parent(e)) + { + par_e = t.parent(e); + if (mark(par_e) == true) + { + v = a(e); + found = true; + break; + } + e = par_e; + }; + + if (! found && e == t.parent(e)) + { + // e is a root node; we get its value: + v = a(e); + + if (echo) + std::cout << "from p = " << p + << " to root e = " << e + << " v = " << v + << std::endl; + + // we set aa from p to the root node + e = p; + do + { + aa(e) = v; + mln_invariant(mark(e) == false); + mark(e) = true; + e = t.parent(e); + } + while (e != t.parent(e)); + // handle the root node 'e': + aa(e) = v; + mln_invariant(mark(e) == false); + mark(e) = true; + mln_invariant(a(e) == v); + } + else if (found) + { + e = p; + + P last_e = P(0,0); + + while (mark(e) == false) + { + aa(e) = v; + mark(e) = true; + last_e = e; + e = t.parent(e); + }; + + if (echo) + { + if (last_e == p) + std::cout << "p = " << p + << " par(e) = " << par_e + << " so keep v = " << v + << std::endl; + else + std::cout << "from p = " << p + << " to e = " << last_e + << " with par(e) = " << par_e + << " v = " << v + << std::endl; + } + } + } + + if (echo) + depict_tree_attributes(t, aa); + + } // end of Modify attributes. + + return aa; + } + + + +} // mln + + + template <typename I, typename N, typename L> void do_it(const I& g, const N& nbh, L& n_labels) { @@ -34,7 +232,7 @@ // regional minima mln_ch_value(I,L) regmin = labeling::regional_minima(g, nbh, n_labels); - debug::println("regmin(g):", regmin); + // debug::println("regmin(g):", regmin); // watershed @@ -42,7 +240,7 @@ L n_basins; mln_ch_value(I,L) w = morpho::meyer_wst(g, nbh, n_basins); mln_invariant(n_basins == n_labels); - debug::println("w(g):", w); + // debug::println("w(g):", w); { @@ -55,12 +253,28 @@ accu::count< util::pix > a_; // Kind of attribute. mln_ch_value(I,unsigned) a = morpho::tree::compute_attribute_image(a_, t); - debug::println("a:", a); + debug::println("a | nodes:", a | t.nodes()); + + mln_ch_value(I,unsigned) aa = change_tree_attributes(t, a); + debug::println("aa | nodes:", aa | t.nodes()); + + // Back-propagation from nodes to components. + { + mln_fwd_piter(tree_t) p(t.domain()); + for_all(p) + if (! t.is_a_node(p)) + { + mln_assertion(t.is_a_node(t.parent(p))); + aa(p) = aa(t.parent(p)); + } + } debug::println("a | w line:", a | (pw::value(w) == pw::cst(0))); - debug::println("a | w basins:", a | (pw::value(w) != pw::cst(0))); + debug::println("aa | w line:", aa | (pw::value(w) == pw::cst(0))); + +// debug::println("a | w basins:", a | (pw::value(w) != pw::cst(0))); +// debug::println("a | regmin:", a | (pw::value(regmin) != pw::cst(0))); - debug::println("a | regmin:", a | (pw::value(regmin) != pw::cst(0))); } } // end of do_it Index: laurent/ismm2009.v2.cc --- laurent/ismm2009.v2.cc (revision 3172) +++ laurent/ismm2009.v2.cc (working copy) @@ -1,10 +1,13 @@ #include "ismm2009.hh" #include <mln/value/int_u8.hh> + +#include <mln/io/pgm/load.hh> +#include <mln/io/pgm/save.hh> + #include <mln/value/label_8.hh> #include <mln/value/label_16.hh> -#include <mln/io/pgm/load.hh> #include <mln/util/ord_pair.hh> #include <mln/debug/println.hh> #include <mln/core/routine/duplicate.hh> @@ -18,14 +21,9 @@ /* - TO-DO list: - ----------- - - - having a heap for every lr (support merge) - handling adjacency on the fly (instead of having an image) - */ @@ -266,7 +264,7 @@ typename N_e2e, typename L > mln_ch_value(G, L) - f_to_wst_unique_g(F& f, // On pixels. + compute_wst_g_from_f(F& f, // On pixels. G& g, // On edges. const N_e2p& e2p, const N_e2e& e2e, @@ -277,7 +275,7 @@ e2p.win()), g); - // FIXME: Here, we want a unique value per edge! +# ifdef MAKE_UNIQUE if (echo) debug::println("g (before):", g); @@ -311,6 +309,9 @@ } } +# endif // MAKE_UNIQUE + + mln_VAR( wst_g, morpho::meyer_wst(g, e2e, n_basins) ); @@ -333,8 +334,9 @@ void usage(char* argv[]) { - std::cerr << "usage: " << argv[0] << " input.pgm" << std::endl; - std::cerr << "Laurent ISMM 2009 scheme." << std::endl; + std::cerr << "usage: " << argv[0] << " input.pgm echo output.pgm" << std::endl; + std::cerr << "Laurent ISMM 2009 scheme with saliency map as output." << std::endl; + std::cerr << " echo = 0 or 1." << std::endl; abort(); } @@ -347,14 +349,20 @@ using value::int_u8; using value::label_16; - bool echo = true; - - if (argc != 2) + if (argc != 4) usage(argv); image2d<int_u8> raw_f; io::pgm::load(raw_f, argv[1]); + bool echo; + { + int echo_ = std::atoi(argv[2]); + if (echo_ != 0 && echo_ != 1) + usage(argv); + echo = bool(echo_); + } + typedef image2d<int_u8> Complex; typedef mln_pset_(Complex) full_D; @@ -372,15 +380,9 @@ L n_basins; - mln_VAR( wst_g, - f_to_wst_g(f, g, e2p(), e2e(), n_basins) ); - - /* - UNIQUE: mln_VAR( wst_g, - f_to_wst_unique_g(f, g, e2p(), e2e(), n_basins, echo) ); - */ + compute_wst_g_from_f(f, g, e2p(), e2e(), n_basins, echo) ); if (echo) @@ -501,11 +503,12 @@ std::vector<pair_t> v = sort_attributes(a, n_basins); // Sort regions. + // Optional code (for testing purpose): change attributes + // so that they are all different. - // Maybe activate to test purpose: - /* +# ifdef MAKE_UNIQUE make_unique_attribute(a, v, n_basins, echo); - */ +# endif // Display attributes. @@ -796,13 +799,13 @@ // +---------------------------------------------------------------+ - { - // Dealing with the watershed line. mln_VAR(aa_line, aa | is_line); { + + { // First, processing the 1D-faces (edges) of the watershed line. std::vector< std::vector<E> > lca; @@ -886,16 +889,26 @@ } if (echo) - debug::println("aa | basins", aa_basins); + debug::println("aa | basins:", aa_basins); } - if (echo) debug::println("aa:", aa); + + // Output is salency map. + { + + image2d<int_u8> output(f_.domain()); + data::fill(output, 0); + data::paste(aa_line, output); + io::pgm::save(output, argv[3]); + } + + } // end of main

1 0

3172: Introduce debug::quiet.
by Guillaume Lazzara 20 Jan '09

20 Jan '09

* headers.mk: add new header to distribution. * mln/debug/all.hh, * mln/debug/essential.hh: include quiet.hh * mln/debug/println.hh: use debug::quiet. Println prints nothing if debug::quiet is set to true. * mln/debug/quiet.hh: the new global variable. * tests/unit_test/Makefile.am, * tests/unit_test/mln_debug_quiet.cc: new unit test. --- milena/ChangeLog | 17 +++++++++++++ milena/headers.mk | 1 + milena/mln/debug/all.hh | 2 +- milena/mln/debug/essential.hh | 3 +- milena/mln/debug/println.hh | 14 ++++++++--- milena/mln/debug/{essential.hh => quiet.hh} | 34 +++++++++++++++++++++----- milena/tests/unit_test/Makefile.am | 2 + milena/tests/unit_test/mln_debug_quiet.cc | 11 ++++++++ 8 files changed, 71 insertions(+), 13 deletions(-) copy milena/mln/debug/{essential.hh => quiet.hh} (73%) create mode 100644 milena/tests/unit_test/mln_debug_quiet.cc diff --git a/milena/ChangeLog b/milena/ChangeLog index e9ca068..b4040f1 100644 --- a/milena/ChangeLog +++ b/milena/ChangeLog @@ -1,5 +1,22 @@ 2009-01-20 Guillaume Lazzara <z(a)lrde.epita.fr> + Introduce debug::quiet. + + * headers.mk: add new header to distribution. + + * mln/debug/all.hh, + * mln/debug/essential.hh: include quiet.hh + + * mln/debug/println.hh: use debug::quiet. Println prints nothing if + debug::quiet is set to true. + + * mln/debug/quiet.hh: the new global variable. + + * tests/unit_test/Makefile.am, + * tests/unit_test/mln_debug_quiet.cc: new unit test. + +2009-01-20 Guillaume Lazzara <z(a)lrde.epita.fr> + Make the use of pw::cst() optional in predicates. * mln/pw/cst.hh: add the proper traits. diff --git a/milena/headers.mk b/milena/headers.mk index a730437..04c0a73 100644 --- a/milena/headers.mk +++ b/milena/headers.mk @@ -1019,6 +1019,7 @@ mln/debug/println.spe.hh \ mln/debug/colorize.hh \ mln/debug/draw_graph.hh \ mln/debug/put_word.hh \ +mln/debug/quiet.hh \ mln/debug/println_with_border.spe.hh \ mln/debug/format.hh \ mln/debug/println.hh \ diff --git a/milena/mln/debug/all.hh b/milena/mln/debug/all.hh index a0a27c6..97f12e9 100644 --- a/milena/mln/debug/all.hh +++ b/milena/mln/debug/all.hh @@ -53,6 +53,6 @@ namespace mln # include <mln/debug/println.hh> # include <mln/debug/println_with_border.hh> # include <mln/debug/put_word.hh> - +# include <mln/debug/quiet.hh> #endif // ! MLN_DEBUG_ALL_HH diff --git a/milena/mln/debug/essential.hh b/milena/mln/debug/essential.hh index a28563b..1851c7a 100644 --- a/milena/mln/debug/essential.hh +++ b/milena/mln/debug/essential.hh @@ -1,4 +1,5 @@ -// Copyright (C) 2008 EPITA Research and Development Laboratory (LRDE) +// Copyright (C) 2008, 2009 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 diff --git a/milena/mln/debug/println.hh b/milena/mln/debug/println.hh index 29ff7bd..1e3371d 100644 --- a/milena/mln/debug/println.hh +++ b/milena/mln/debug/println.hh @@ -38,6 +38,7 @@ # include <mln/core/concept/image.hh> # include <mln/core/concept/window.hh> # include <mln/geom/bbox.hh> +# include <mln/debug/quiet.hh> # include <mln/debug/format.hh> // Specializations are in: @@ -89,16 +90,21 @@ namespace mln println(const Image& input) { trace::entering("debug::println"); - impl::println(geom::bbox(exact(input).domain()), - exact(input)); + + if (!quiet) + impl::println(geom::bbox(exact(input).domain()), + exact(input)); trace::exiting("debug::println"); } template <typename I> void println(const std::string& msg, const Image& input) { - std::cout << msg << std::endl; - println(input); + if (!quiet) + { + std::cout << msg << std::endl; + println(input); + } } # endif // ! MLN_INCLUDE_ONLY diff --git a/milena/mln/debug/essential.hh b/milena/mln/debug/quiet.hh similarity index 73% copy from milena/mln/debug/essential.hh copy to milena/mln/debug/quiet.hh index a28563b..ab54a48 100644 --- a/milena/mln/debug/essential.hh +++ b/milena/mln/debug/quiet.hh @@ -1,4 +1,4 @@ -// Copyright (C) 2008 EPITA Research and Development Laboratory (LRDE) +// Copyright (C) 2009 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 @@ -25,13 +25,33 @@ // reasons why the executable file might be covered by the GNU General // Public License. -#ifndef MLN_DEBUG_ESSENTIAL_HH -# define MLN_DEBUG_ESSENTIAL_HH +#ifndef MLN_DEBUG_QUIET_HH +# define MLN_DEBUG_QUIET_HH -/// \file mln/debug/essential.hh +/// \file mln/debug/quiet.hh /// -/// File that includes essential debug-related routines. +/// global variable telling whether the debug should be printed or not. -# include <mln/debug/all.hh> -#endif // ! MLN_DEBUG_ESSENTIAL_HH +namespace mln +{ + + namespace debug + { + + extern bool quiet; + + + +# ifndef MLN_INCLUDE_ONLY + + bool quiet = false; + +# endif // ! MLN_INCLUDE_ONLY + + + } // end of namespace mln::debug + +} // end of namespace mln + +#endif // ! MLN_DEBUG_QUIET_HH diff --git a/milena/tests/unit_test/Makefile.am b/milena/tests/unit_test/Makefile.am index b5dd047..f7886cd 100644 --- a/milena/tests/unit_test/Makefile.am +++ b/milena/tests/unit_test/Makefile.am @@ -983,6 +983,7 @@ mln_debug_println_with_border \ mln_debug_colorize \ mln_debug_draw_graph \ mln_debug_put_word \ +mln_debug_quiet \ mln_debug_format \ mln_debug_println \ mln_debug_essential \ @@ -1998,6 +1999,7 @@ mln_debug_println_with_border_SOURCES = mln_debug_println_with_border.cc mln_debug_colorize_SOURCES = mln_debug_colorize.cc mln_debug_draw_graph_SOURCES = mln_debug_draw_graph.cc mln_debug_put_word_SOURCES = mln_debug_put_word.cc +mln_debug_quiet_SOURCES = mln_debug_quiet.cc mln_debug_format_SOURCES = mln_debug_format.cc mln_debug_println_SOURCES = mln_debug_println.cc mln_debug_essential_SOURCES = mln_debug_essential.cc diff --git a/milena/tests/unit_test/mln_debug_quiet.cc b/milena/tests/unit_test/mln_debug_quiet.cc new file mode 100644 index 0000000..baa5c09 --- /dev/null +++ b/milena/tests/unit_test/mln_debug_quiet.cc @@ -0,0 +1,11 @@ +// Unit test for mln/debug/quiet.hh. +// Generated by ./build_unit_test.sh, do not modify. + +// Include the file twice, so we detect missing inclusion guards. +#include <mln/debug/quiet.hh> +#include <mln/debug/quiet.hh> + +int main() +{ + // Nothing. +} -- 1.5.6.5

1 0

3171: Make the use of pw::cst() optional in predicates.
by Guillaume Lazzara 20 Jan '09

20 Jan '09

* mln/pw/cst.hh: add the proper traits. * tests/pw/value.cc: add one more test. --- milena/ChangeLog | 8 ++++++++ milena/mln/pw/cst.hh | 34 ++++++++++++++++++++++++++++++++++ milena/tests/pw/value.cc | 11 ++++++----- 3 files changed, 48 insertions(+), 5 deletions(-) diff --git a/milena/ChangeLog b/milena/ChangeLog index f672bbb..e9ca068 100644 --- a/milena/ChangeLog +++ b/milena/ChangeLog @@ -1,5 +1,13 @@ 2009-01-20 Guillaume Lazzara <z(a)lrde.epita.fr> + Make the use of pw::cst() optional in predicates. + + * mln/pw/cst.hh: add the proper traits. + + * tests/pw/value.cc: add one more test. + +2009-01-20 Guillaume Lazzara <z(a)lrde.epita.fr> + Fix a double free in fibonacci heap and add support for priority. * mln/util/fibonacci_heap.hh: Fix the destructor and add an attribute diff --git a/milena/mln/pw/cst.hh b/milena/mln/pw/cst.hh index bc344ad..91034cd 100644 --- a/milena/mln/pw/cst.hh +++ b/milena/mln/pw/cst.hh @@ -39,6 +39,40 @@ namespace mln { + // Forward declaration + namespace pw + { + + template <typename T> + struct cst_; + + template <typename T> + cst_<T> cst(const T& t); + + } // end of namespace mln::pw + + + namespace trait + { + + template <typename F, typename S> + struct set_binary_< op::eq, mln::Function_v2v, F, mln::value::Scalar, S > + { + typedef mln_trait_op_eq(F, pw::cst_<mln_value_equiv(S)>) ret; + }; + + } // end of namespace mln::trait + + + template <typename F, typename S> + mln_trait_op_eq(F,S) + operator == (const Function_v2v<F>& fun, const value::Scalar<S>& s) + { + return exact(fun) == pw::cst( value::equiv(s) ); + } + + + namespace pw { diff --git a/milena/tests/pw/value.cc b/milena/tests/pw/value.cc index 268ebde..19938db 100644 --- a/milena/tests/pw/value.cc +++ b/milena/tests/pw/value.cc @@ -1,4 +1,5 @@ -// Copyright (C) 2007 EPITA Research and Development Laboratory +// Copyright (C) 2007, 2009 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 @@ -25,10 +26,9 @@ // reasons why the executable file might be covered by the GNU General // Public License. -/*! \file tests/pw/value.cc - * - * \brief Test on mln::pw::value_. - */ +/// \file tests/pw/value.cc +/// +/// Test on mln::pw::value_. #include <mln/core/image/image2d.hh> #include <mln/data/fill.hh> @@ -45,6 +45,7 @@ int main() point2d p(1, 1); ima(p) = 51; mln_assertion( (pw::value(ima) == pw::cst(51))(p) == true ); + mln_assertion( (pw::value(ima) == 51)(p) == true ); // { // image2d<float> imaf(3,3); -- 1.5.6.5

1 0

3170: Fix a double free in fibonacci heap and add support for priority.
by Guillaume Lazzara 20 Jan '09

20 Jan '09

* mln/util/fibonacci_heap.hh: Fix the destructor and add an attribute "priority" to the heap nodes. The fibonacci heap now behaves like a priority queue. * tests/util/fibonacci_heap.cc: add more tests. --- milena/ChangeLog | 10 + milena/mln/util/fibonacci_heap.hh | 490 ++++++++++++++++++++--------------- milena/tests/util/fibonacci_heap.cc | 47 +++- 3 files changed, 321 insertions(+), 226 deletions(-) diff --git a/milena/ChangeLog b/milena/ChangeLog index f059029..f672bbb 100644 --- a/milena/ChangeLog +++ b/milena/ChangeLog @@ -1,3 +1,13 @@ +2009-01-20 Guillaume Lazzara <z(a)lrde.epita.fr> + + Fix a double free in fibonacci heap and add support for priority. + + * mln/util/fibonacci_heap.hh: Fix the destructor and add an attribute + "priority" to the heap nodes. The fibonacci heap now behaves like a + priority queue. + + * tests/util/fibonacci_heap.cc: add more tests. + 2009-01-19 Guillaume Lazzara <z(a)lrde.epita.fr> Rename histo::data as histo::array. diff --git a/milena/mln/util/fibonacci_heap.hh b/milena/mln/util/fibonacci_heap.hh index 8a7ac2c..ef85508 100644 --- a/milena/mln/util/fibonacci_heap.hh +++ b/milena/mln/util/fibonacci_heap.hh @@ -68,7 +68,7 @@ namespace mln | Fibonacci Heap node Class | `--------------------------*/ - template <typename T> + template <typename P, typename T> class fibonacci_heap_node { @@ -77,17 +77,19 @@ namespace mln fibonacci_heap_node(); /// Construct a new node with \p value as value. - fibonacci_heap_node(const T& value); + fibonacci_heap_node(const P& priority, const T& value); ~fibonacci_heap_node(); /// Return the node value. const T& value() const; - fibonacci_heap_node<T> *left() const; - fibonacci_heap_node<T> *right() const; - fibonacci_heap_node<T> *parent() const; - fibonacci_heap_node<T> *child() const; + const P& priority() const; + + fibonacci_heap_node<P,T> *left() const; + fibonacci_heap_node<P,T> *right() const; + fibonacci_heap_node<P,T> *parent() const; + fibonacci_heap_node<P,T> *child() const; short degree() const; @@ -95,30 +97,29 @@ namespace mln void set_value(const T&); - void set_left(fibonacci_heap_node<T> *node); - void set_right(fibonacci_heap_node<T> *node); - void set_parent(fibonacci_heap_node<T> *node); - void set_child(fibonacci_heap_node<T> *node); + void set_left(fibonacci_heap_node<P,T> *node); + void set_right(fibonacci_heap_node<P,T> *node); + void set_parent(fibonacci_heap_node<P,T> *node); + void set_child(fibonacci_heap_node<P,T> *node); void set_degree(short degree); void set_mark(short mark); - void operator=(const T& val); - - void operator=(fibonacci_heap_node<T>& rhs); - int operator==(fibonacci_heap_node<T>& rhs); - int operator<(fibonacci_heap_node<T>& rhs); + void operator=(fibonacci_heap_node<P,T>& rhs); + bool operator==(fibonacci_heap_node<P,T>& rhs); + bool operator<(fibonacci_heap_node<P,T>& rhs); - void print_(); + void print_() const; private: - fibonacci_heap_node<T> *left_; - fibonacci_heap_node<T> *right_; - fibonacci_heap_node<T> *parent_; - fibonacci_heap_node<T> *child_; + fibonacci_heap_node<P,T> *left_; + fibonacci_heap_node<P,T> *right_; + fibonacci_heap_node<P,T> *parent_; + fibonacci_heap_node<P,T> *child_; short degree_; short mark_; + P priority_; T value_; }; @@ -130,23 +131,30 @@ namespace mln | Fibonacci Heap Class | `---------------------*/ - template <typename T> - class fibonacci_heap : public Object< fibonacci_heap<T> > + template <typename P, typename T> + class fibonacci_heap : public Object< fibonacci_heap<P,T> > { public: + typedef T element; + /// Default constructor fibonacci_heap(); + /// Copy constructor + /// Be ware that once this heap is constructed, the argument \p node + /// is cleared and all its elements are part of this new heap. + fibonacci_heap(const fibonacci_heap<P,T>& node); + ~fibonacci_heap(); /// Push a new element in the heap. /// \sa insert - void push(const T& value); + void push(const P& priority, const T& value); /// Take \p other_heap's elements and insert them in this heap. /// After this call \p other_heap is cleared. - void push(fibonacci_heap<T>& other_heap); + void push(fibonacci_heap<P,T>& other_heap); /// Return the minimum value in the heap. const T& front() const; @@ -166,11 +174,18 @@ namespace mln /// Clear all elements in the heap and make the heap empty. void clear(); + /// Assignment operator. + /// Be ware that this operator do *not* copy the data from \p rhs to this heap. + /// It moves all elements which means that afterwards, \p rhs is + /// is cleared and all its elements are part of this new heap. + fibonacci_heap<P,T>& operator=(fibonacci_heap<P,T>& rhs); - void print_(internal::fibonacci_heap_node<T> *tree = 0, - internal::fibonacci_heap_node<T> *parent = 0); + std::ostream& print_(std::ostream& cout, + internal::fibonacci_heap_node<P,T> *tree = 0, + internal::fibonacci_heap_node<P,T> *parent = 0) const; + private: // Internal functions that help to implement the Standard Operations @@ -180,20 +195,21 @@ namespace mln /// FIXME: cannot use that function efficiently except by passing the /// node pointer. Any idea? /// FIXME: may be part of the public interface. - int decrease_key(internal::fibonacci_heap_node<T> *node, - internal::fibonacci_heap_node<T>& key); + int decrease_key(internal::fibonacci_heap_node<P,T> *node, + internal::fibonacci_heap_node<P,T>& key); /// Remove node \p node from the child list of its parent node. /// FIXME: cannot use that function efficiently except by passing the /// node pointer. Any idea? /// FIXME: may be part of the public interface. - int remove(internal::fibonacci_heap_node<T> *node); + int remove(internal::fibonacci_heap_node<P,T> *node); /// Insert a new node \p node in the heap. - void insert(internal::fibonacci_heap_node<T> *node); + void insert(internal::fibonacci_heap_node<P,T> *node); - void exchange(internal::fibonacci_heap_node<T>*&, - internal::fibonacci_heap_node<T>*&); + /// Swap the two given nodes. + void exchange(internal::fibonacci_heap_node<P,T>*& lhs, + internal::fibonacci_heap_node<P,T>*& rhs); /// Internal function that reorganizes heap as part of an pop_front(). /// We must find new minimum in heap, which could be anywhere along the @@ -214,14 +230,14 @@ namespace mln /// The node \p lhs is removed from the root list and becomes a subtree /// of node \p rhs. - void link(internal::fibonacci_heap_node<T> *lhs, - internal::fibonacci_heap_node<T> *rhs); + void link(internal::fibonacci_heap_node<P,T> *lhs, + internal::fibonacci_heap_node<P,T> *rhs); - void add_to_root_list(internal::fibonacci_heap_node<T> *); + void add_to_root_list(internal::fibonacci_heap_node<P,T> *); /// Remove node \p lhs from the child list of its parent node \p rhs. - void cut(internal::fibonacci_heap_node<T> *lhs, - internal::fibonacci_heap_node<T> *rhs); + void cut(internal::fibonacci_heap_node<P,T> *lhs, + internal::fibonacci_heap_node<P,T> *rhs); /// Cuts each node in parent list, putting successive ancestor nodes on /// the root list until we either arrive at the root list or until we @@ -230,19 +246,26 @@ namespace mln /// been lost; if a second subtree is lost later during another /// cascading cut, then we move the node to the root list so that it /// can be re-balanced on the next consolidate. - void cascading_cut(internal::fibonacci_heap_node<T> *); + void cascading_cut(internal::fibonacci_heap_node<P,T> *); /// Clear the heap but do *NOT* delete elements. - void soft_clear(); + void soft_clear_(); - internal::fibonacci_heap_node<T> *min_root; - long num_nodes; - long num_trees; - long num_marked_nodes; + /// FIXME: ugly but we need to be able to soft_clear() the heap in the + /// copy constructor... Any idea how to do without that? + mutable internal::fibonacci_heap_node<P,T> *min_root; + mutable long num_nodes; + mutable long num_trees; + mutable long num_marked_nodes; }; + template <typename P, typename T> + std::ostream& + operator<<(std::ostream& cout, const fibonacci_heap<P,T>& heap); + + # ifndef MLN_INCLUDE_ONLY @@ -251,202 +274,206 @@ namespace mln { - /*---------------\ + /*--------------------\ | fibonacci_heap_node | - `---------------*/ + `--------------------*/ - template <typename T> + template <typename P, typename T> inline - fibonacci_heap_node<T>::fibonacci_heap_node() + fibonacci_heap_node<P,T>::fibonacci_heap_node() : left_(0), right_(0), parent_(0), child_(0), - degree_(0), mark_(0) + degree_(0), mark_(0), priority_(0) + // FIXME: don't we want to initialize priority with literal::zero? { } - template <typename T> + template <typename P, typename T> inline - fibonacci_heap_node<T>::fibonacci_heap_node(const T& new_value) + fibonacci_heap_node<P,T>::fibonacci_heap_node(const P& priority, + const T& new_value) : left_(0), right_(0), parent_(0), child_(0), - degree_(0), mark_(0), value_(new_value) + degree_(0), mark_(0), priority_(priority), value_(new_value) { } - template <typename T> + template <typename P, typename T> inline - fibonacci_heap_node<T>::~fibonacci_heap_node() + fibonacci_heap_node<P,T>::~fibonacci_heap_node() { } - template <typename T> + template <typename P, typename T> inline const T& - fibonacci_heap_node<T>::value() const + fibonacci_heap_node<P,T>::value() const { return value_; } - template <typename T> + template <typename P, typename T> inline - fibonacci_heap_node<T> * - fibonacci_heap_node<T>::left() const + const P& + fibonacci_heap_node<P,T>::priority() const + { + return priority_; + } + + + template <typename P, typename T> + inline + fibonacci_heap_node<P,T> * + fibonacci_heap_node<P,T>::left() const { return left_; } - template <typename T> + template <typename P, typename T> inline - fibonacci_heap_node<T> * - fibonacci_heap_node<T>::right() const + fibonacci_heap_node<P,T> * + fibonacci_heap_node<P,T>::right() const { return right_; } - template <typename T> + template <typename P, typename T> inline - fibonacci_heap_node<T> * - fibonacci_heap_node<T>::parent() const + fibonacci_heap_node<P,T> * + fibonacci_heap_node<P,T>::parent() const { return parent_; } - template <typename T> + template <typename P, typename T> inline - fibonacci_heap_node<T> * - fibonacci_heap_node<T>::child() const + fibonacci_heap_node<P,T> * + fibonacci_heap_node<P,T>::child() const { return child_; } - template <typename T> + template <typename P, typename T> inline short - fibonacci_heap_node<T>::degree() const + fibonacci_heap_node<P,T>::degree() const { return degree_; } - template <typename T> + template <typename P, typename T> inline short - fibonacci_heap_node<T>::mark() const + fibonacci_heap_node<P,T>::mark() const { return mark_; } - template <typename T> + template <typename P, typename T> inline void - fibonacci_heap_node<T>::set_value(const T& value) + fibonacci_heap_node<P,T>::set_value(const T& value) { value_ = value; } - template <typename T> + template <typename P, typename T> inline void - fibonacci_heap_node<T>::set_left(fibonacci_heap_node<T> *node) + fibonacci_heap_node<P,T>::set_left(fibonacci_heap_node<P,T> *node) { left_ = node; } - template <typename T> + template <typename P, typename T> inline void - fibonacci_heap_node<T>::set_right(fibonacci_heap_node<T> *node) + fibonacci_heap_node<P,T>::set_right(fibonacci_heap_node<P,T> *node) { right_ = node; } - template <typename T> + template <typename P, typename T> inline void - fibonacci_heap_node<T>::set_parent(fibonacci_heap_node<T> *node) + fibonacci_heap_node<P,T>::set_parent(fibonacci_heap_node<P,T> *node) { parent_ = node; } - template <typename T> + template <typename P, typename T> inline void - fibonacci_heap_node<T>::set_child(fibonacci_heap_node<T> *node) + fibonacci_heap_node<P,T>::set_child(fibonacci_heap_node<P,T> *node) { child_ = node; } - template <typename T> + template <typename P, typename T> inline void - fibonacci_heap_node<T>::set_degree(short degree) + fibonacci_heap_node<P,T>::set_degree(short degree) { degree_ = degree; } - template <typename T> + template <typename P, typename T> inline void - fibonacci_heap_node<T>::set_mark(short mark) + fibonacci_heap_node<P,T>::set_mark(short mark) { mark_ = mark; } - template <typename T> - inline - void - fibonacci_heap_node<T>::operator=(const T& value) - { - value_ = value; - } - - - template <typename T> + template <typename P, typename T> inline - void fibonacci_heap_node<T>::operator=(fibonacci_heap_node<T>& rhs) + void fibonacci_heap_node<P,T>::operator=(fibonacci_heap_node<P,T>& rhs) { + priority_ = rhs.priority(); value_ = rhs.value(); } - template <typename T> + template <typename P, typename T> inline - int - fibonacci_heap_node<T>::operator==(fibonacci_heap_node<T>& rhs) + bool + fibonacci_heap_node<P,T>::operator==(fibonacci_heap_node<P,T>& rhs) { - return value_ == rhs.value() ? 1 : 0; + return priority_ == rhs.priority() && value_ == rhs.value(); } - template <typename T> + template <typename P, typename T> inline - int - fibonacci_heap_node<T>::operator<(fibonacci_heap_node<T>& rhs) + bool + fibonacci_heap_node<P,T>::operator<(fibonacci_heap_node<P,T>& rhs) { - return util::ord_strict(value_, rhs.value()) ? 1 : 0; + return util::ord_strict(priority_, rhs.priority()) + || (priority_ == rhs.priority() && util::ord_strict(value_, rhs.value())); } - template <typename T> + template <typename P, typename T> inline - void fibonacci_heap_node<T>::print_() + void fibonacci_heap_node<P,T>::print_() const { - std::cout << value_; + std::cout << value_ << " (" << priority_ << ")"; } @@ -454,53 +481,69 @@ namespace mln - /*----------\ + /*---------------\ | fibonacci_heap | - `----------*/ + `---------------*/ - template <typename T> + template <typename P, typename T> inline - fibonacci_heap<T>::fibonacci_heap() + fibonacci_heap<P,T>::fibonacci_heap() { - min_root = 0; - num_nodes = 0; - num_trees = 0; - num_marked_nodes = 0; + soft_clear_(); + } + + + template <typename P, typename T> + inline + fibonacci_heap<P,T>::fibonacci_heap(const fibonacci_heap<P,T>& rhs) + : Object< fibonacci_heap<P,T> >() + { + min_root = rhs.min_root; + num_nodes = rhs.num_nodes; + num_trees = rhs.num_trees; + num_marked_nodes = rhs.num_marked_nodes; + +// rhs is const, we cannot call that method. +// rhs.soft_clear_(); + rhs.min_root = 0; + rhs.num_nodes = 0; + rhs.num_trees = 0; + rhs.num_marked_nodes = 0; } - template <typename T> + template <typename P, typename T> inline - fibonacci_heap<T>::~fibonacci_heap() + fibonacci_heap<P,T>::~fibonacci_heap() { clear(); } - template <typename T> + template <typename P, typename T> inline void - fibonacci_heap<T>::push(const T& value) + fibonacci_heap<P,T>::push(const P& priority, const T& value) { - typedef internal::fibonacci_heap_node<T> node_t; - node_t *new_node = new node_t(value); + typedef internal::fibonacci_heap_node<P,T> node_t; + node_t *new_node = new node_t(priority, value); insert(new_node); } - template <typename T> + template <typename P, typename T> inline void - fibonacci_heap<T>::push(fibonacci_heap<T>& other_heap) + fibonacci_heap<P,T>::push(fibonacci_heap<P,T>& other_heap) { - internal::fibonacci_heap_node<T> *min1, *min2, *next1, *next2; - - if (other_heap.is_empty()) + if (other_heap.is_empty() || &other_heap == this) return; if (min_root != 0) { + internal::fibonacci_heap_node<P,T> *min1, *min2, *next1, *next2; + // We join the two circular lists by cutting each list between its // min node and the node after the min. This code just pulls those // nodes into temporary variables so we don't get lost as changes @@ -522,7 +565,8 @@ namespace mln // Choose the new minimum for the heap if (*min2 < *min1) min_root = min2; - } else + } + else min_root = other_heap.min_root; // Set the amortized analysis statistics and size of the new heap @@ -531,32 +575,31 @@ namespace mln num_trees += other_heap.num_trees; // Complete the union by setting the other heap to emptiness - other_heap.min_root = 0; - other_heap.num_nodes = 0; - other_heap.num_trees = 0; - other_heap.num_marked_nodes = 0; + other_heap.soft_clear_(); + + mln_postcondition(other_heap.is_empty()); } - template <typename T> + template <typename P, typename T> inline const T& - fibonacci_heap<T>::front() const + fibonacci_heap<P,T>::front() const { return min_root->value(); } - template <typename T> + template <typename P, typename T> inline T - fibonacci_heap<T>::pop_front() + fibonacci_heap<P,T>::pop_front() { mln_precondition(is_valid()); mln_precondition(!is_empty()); - internal::fibonacci_heap_node<T> *result = min_root; - fibonacci_heap<T> *child_heap = 0; + internal::fibonacci_heap_node<P,T> *result = min_root; + fibonacci_heap<P,T> *child_heap = 0; // Remove minimum node and set min_root to next node min_root = result->right(); @@ -565,7 +608,7 @@ namespace mln result->set_left(0); result->set_right(0); - num_nodes --; + --num_nodes; if (result->mark()) { --num_marked_nodes; @@ -592,7 +635,7 @@ namespace mln // root list of this heap. else { - child_heap = new fibonacci_heap<T>(); + child_heap = new fibonacci_heap<P,T>(); child_heap->min_root = result->child(); } @@ -623,13 +666,13 @@ namespace mln } - template <typename T> + template <typename P, typename T> inline int - fibonacci_heap<T>::decrease_key(internal::fibonacci_heap_node<T> *node, - internal::fibonacci_heap_node<T>& key) + fibonacci_heap<P,T>::decrease_key(internal::fibonacci_heap_node<P,T> *node, + internal::fibonacci_heap_node<P,T>& key) { - internal::fibonacci_heap_node<T> *parent; + internal::fibonacci_heap_node<P,T> *parent; if (node == 0 || *node < key) return -1; @@ -650,12 +693,12 @@ namespace mln } - template <typename T> + template <typename P, typename T> inline int - fibonacci_heap<T>::remove(internal::fibonacci_heap_node<T> *node) + fibonacci_heap<P,T>::remove(internal::fibonacci_heap_node<P,T> *node) { - internal::fibonacci_heap_node<T> temp; + internal::fibonacci_heap_node<P,T> temp; int result; if (node == 0) @@ -674,46 +717,38 @@ namespace mln } - template <typename T> + template <typename P, typename T> inline bool - fibonacci_heap<T>::is_empty() const + fibonacci_heap<P,T>::is_empty() const { return min_root == 0; } - template <typename T> + template <typename P, typename T> inline bool - fibonacci_heap<T>::is_valid() const + fibonacci_heap<P,T>::is_valid() const { return min_root != 0; } - template <typename T> + template <typename P, typename T> inline void - fibonacci_heap<T>::clear() + fibonacci_heap<P,T>::clear() { - internal::fibonacci_heap_node<T> *temp; - - for (int i = 0; i < num_nodes; ++i) - { - temp = min_root->right(); - delete min_root; - min_root = temp; - } - - soft_clear(); + while (min_root != 0) + pop_front(); } - template <typename T> + template <typename P, typename T> inline void - fibonacci_heap<T>::soft_clear() + fibonacci_heap<P,T>::soft_clear_() { min_root = 0; num_nodes = 0; @@ -722,22 +757,39 @@ namespace mln } - template <typename T> + template <typename P, typename T> inline unsigned - fibonacci_heap<T>::nelements() const + fibonacci_heap<P,T>::nelements() const { return num_nodes; }; - template <typename T> + template <typename P, typename T> inline - void - fibonacci_heap<T>::print_(internal::fibonacci_heap_node<T> *tree, - internal::fibonacci_heap_node<T> *parent) + fibonacci_heap<P,T>& + fibonacci_heap<P,T>::operator=(fibonacci_heap<P,T>& rhs) + { + if (&rhs != this) + { + min_root = rhs.min_root; + num_nodes = rhs.num_nodes; + num_trees = rhs.num_trees; + num_marked_nodes = rhs.num_marked_nodes; + rhs.soft_clear_(); + } + return *this; + } + + + template <typename P, typename T> + std::ostream& + fibonacci_heap<P,T>::print_(std::ostream& cout, + internal::fibonacci_heap_node<P,T> *tree, + internal::fibonacci_heap_node<P,T> *parent) const { - internal::fibonacci_heap_node<T>* temp = 0; + internal::fibonacci_heap_node<P,T>* temp = 0; if (tree == 0) tree = min_root; @@ -747,51 +799,51 @@ namespace mln { do { if (temp->left() == 0) - std::cout << "(left is 0)"; + cout << "(left is 0)"; temp->print_(); if (temp->parent() != parent) - std::cout << "(parent is incorrect)"; + cout << "(parent is incorrect)"; if (temp->right() == 0) - std::cout << "(right is 0)"; + cout << "(right is 0)"; else if (temp->right()->left() != temp) - std::cout << "(Error in left link left) ->"; + cout << "(Error in left link left) ->"; else - std::cout << " <-> "; + cout << " <-> "; temp = temp->right(); } while (temp != 0 && temp != tree); } else - std::cout << " <empty>" << std::endl; - std::cout << std::endl; + cout << " <empty>" << std::endl; + cout << std::endl; temp = tree; if (temp != 0) { do { - std::cout << "children of "; - temp->print_(); - std::cout << ": "; + cout << "children of " << temp->value() << ": "; if (temp->child() == 0) - std::cout << "NONE" << std::endl; - else print_(temp->child(), temp); + cout << "NONE" << std::endl; + else print_(cout, temp->child(), temp); temp = temp->right(); } while (temp!=0 && temp != tree); } + + return cout; } - template <typename T> + template <typename P, typename T> inline - void fibonacci_heap<T>::consolidate() + void fibonacci_heap<P,T>::consolidate() { - internal::fibonacci_heap_node<T> *x, *y, *w; - internal::fibonacci_heap_node<T> *a[1 + 8 * sizeof (long)]; // 1+lg(n) + internal::fibonacci_heap_node<P,T> *x, *y, *w; + internal::fibonacci_heap_node<P,T> *a[1 + 8 * sizeof (long)]; // 1+lg(n) short dn = 1 + 8 * sizeof (long); // Initialize the consolidation detection array - for (int i = 0; i < dn; i++) + for (int i = 0; i < dn; ++i) a[i] = 0; // We need to loop through all elements on root list. @@ -822,7 +874,7 @@ namespace mln if (w == y) w = y->right(); link(y, x); a[d] = 0; - d++; + ++d; } a[d] = x; @@ -833,24 +885,24 @@ namespace mln // count the number of subtrees. min_root = 0; num_trees = 0; - for (int i = 0; i < dn; i++) + for (int i = 0; i < dn; ++i) if (a[i] != 0) add_to_root_list(a[i]); } - template <typename T> + template <typename P, typename T> inline void - fibonacci_heap<T>::link(internal::fibonacci_heap_node<T> *y, - internal::fibonacci_heap_node<T> *x) + fibonacci_heap<P,T>::link(internal::fibonacci_heap_node<P,T> *y, + internal::fibonacci_heap_node<P,T> *x) { // Remove node y from root list if (y->right() != 0) y->right()->set_left(y->left()); if (y->left() != 0) y->left()->set_right(y->right()); - num_trees--; + --num_trees; // Make node y a singleton circular list with a parent of x y->set_left(y); @@ -874,37 +926,38 @@ namespace mln x->set_degree(x->degree() + 1); // node y has just been made a child, so clear its mark - if (y->mark()) num_marked_nodes--; + if (y->mark()) + --num_marked_nodes; y->set_mark(0); } - template <typename T> + template <typename P, typename T> inline void - fibonacci_heap<T>::add_to_root_list(internal::fibonacci_heap_node<T> *x) + fibonacci_heap<P,T>::add_to_root_list(internal::fibonacci_heap_node<P,T> *x) { if (x->mark()) --num_marked_nodes; x->set_mark(0); - num_nodes--; + --num_nodes; insert(x); } - template <typename T> + template <typename P, typename T> inline void - fibonacci_heap<T>::cut(internal::fibonacci_heap_node<T> *x, - internal::fibonacci_heap_node<T> *y) + fibonacci_heap<P,T>::cut(internal::fibonacci_heap_node<P,T> *x, + internal::fibonacci_heap_node<P,T> *y) { if (y->child() == x) y->child() = x->right(); if (y->child() == x) y->child() = 0; - y->degree --; + y->set_degree(y->degree() - 1); x->left()->right() = x->right(); x->right()->left() = x->left(); @@ -913,19 +966,19 @@ namespace mln } - template <typename T> + template <typename P, typename T> inline void - fibonacci_heap<T>::cascading_cut(internal::fibonacci_heap_node<T> *y) + fibonacci_heap<P,T>::cascading_cut(internal::fibonacci_heap_node<P,T> *y) { - internal::fibonacci_heap_node<T> *z = y->parent(); + internal::fibonacci_heap_node<P,T> *z = y->parent(); while (z != 0) { if (y->mark() == 0) { y->mark() = 1; - num_marked_nodes++; + ++num_marked_nodes; z = 0; } else @@ -938,10 +991,10 @@ namespace mln } - template <typename T> + template <typename P, typename T> inline void - fibonacci_heap<T>::insert(internal::fibonacci_heap_node<T> *node) + fibonacci_heap<P,T>::insert(internal::fibonacci_heap_node<P,T> *node) { if (node == 0) return; @@ -972,24 +1025,33 @@ namespace mln } // We have one more node in the heap, and it is a tree on the root list - num_nodes++; - num_trees++; + ++num_nodes; + ++num_trees; node->set_parent(0); } - template <typename T> + template <typename P, typename T> inline - void fibonacci_heap<T>::exchange(internal::fibonacci_heap_node<T>*& n1, - internal::fibonacci_heap_node<T>*& n2) + void + fibonacci_heap<P,T>::exchange(internal::fibonacci_heap_node<P,T>*& n1, + internal::fibonacci_heap_node<P,T>*& n2) { - internal::fibonacci_heap_node<T> *temp; + internal::fibonacci_heap_node<P,T> *temp; temp = n1; n1 = n2; n2 = temp; } + + template <typename P, typename T> + std::ostream& + operator<<(std::ostream& cout, const fibonacci_heap<P,T>& heap) + { + return heap.print_(cout); + } + # endif // ! MLN_INCLUDE_ONLY diff --git a/milena/tests/util/fibonacci_heap.cc b/milena/tests/util/fibonacci_heap.cc index a7ce896..504686e 100644 --- a/milena/tests/util/fibonacci_heap.cc +++ b/milena/tests/util/fibonacci_heap.cc @@ -33,6 +33,7 @@ #include <mln/util/fibonacci_heap.hh> #include <mln/core/alias/point2d.hh> + using mln::point2d; point2d p[] = { point2d(4,5), point2d(3,4), point2d(3,2), @@ -42,10 +43,10 @@ point2d p[] = { point2d(4,5), point2d(3,4), point2d(3,2), point2d res_1[] = { point2d(1,6), point2d(2,3), point2d(2,4) }; -point2d res_2[] = { point2d(1,4), point2d(3,2), point2d(3,4), - point2d(3,5), point2d(4,5), point2d(5,4), - point2d(7,2), point2d(7,3), point2d(9,6), - point2d(53,4) }; +point2d res_2[] = { point2d(53,4), point2d(5,4), point2d(1,4), + point2d(3,2), point2d(3,4), point2d(3,5), + point2d(4,5), point2d(7,2), point2d(7,3), + point2d(9,6) }; int main() @@ -53,14 +54,14 @@ int main() using namespace mln; /// Init heap - util::fibonacci_heap<point2d> heap; + util::fibonacci_heap<int,point2d> heap; for (unsigned i = 0; i < 5; ++i) - heap.push(p[i]); + heap.push(3, p[i]); /// Init heap2 - util::fibonacci_heap<point2d> heap2; + util::fibonacci_heap<int,point2d> heap2; for (unsigned i = 5; i < 10; ++i) - heap2.push(p[i]); + heap2.push(3, p[i]); /*! @@ -79,8 +80,9 @@ int main() /// Heap2 is now empty mln_assertion(heap2.is_empty()); mln_assertion(heap2.nelements() == 0); + /// Check if the front() is correct in heap - mln_assertion(heap.front() == res_1[0]); +// mln_assertion(heap.front() == res_1[0]); /*! @@ -111,9 +113,9 @@ int main() /// Re-insert data after deletion... - heap2.push(point2d(53,4)); - heap2.push(point2d(1,4)); - heap2.push(point2d(5,4)); + heap2.push(1, point2d(53,4)); + heap2.push(3, point2d(1,4)); + heap2.push(2, point2d(5,4)); /// ... and try to extract and delete data again. unsigned i = 0; @@ -126,4 +128,25 @@ int main() /// The heap must be empty. mln_assertion(heap2.is_empty()); mln_assertion(heap2.nelements() == 0); + + + + /// Swap two variables thanks to a temporary. + heap.push(3, point2d(2,4)); + heap2.push(3, point2d(53,4)); + util::fibonacci_heap<int,point2d> tmp = heap; + heap = heap2; + heap2 = tmp; + + mln_assertion(heap2.nelements() == 1); + mln_assertion(heap.nelements() == 1); + mln_assertion(tmp.nelements() == 0); + + + /// Testing copy constructor. + util::fibonacci_heap<int,point2d> tmp2(heap); + + mln_assertion(tmp2.nelements() == 1); + mln_assertion(heap.nelements() == 0); + } -- 1.5.6.5

1 0

3169: Augment code for Laurent.
by Thierry Geraud 19 Jan '09

19 Jan '09

https://svn.lrde.epita.fr/svn/oln/trunk/milena/sandbox Index: ChangeLog from Thierry Geraud <thierry.geraud(a)lrde.epita.fr> Augment code for Laurent. * theo/color/sum_pix.hh (take): Remove useless +1. * theo/color/segment.cc: Add unactivated code. * theo/color/blen_pix.hh (sum_len): New. (take): Use it. * laurent/ismm2009.cc: UPdate. * laurent/ismm2009.v0.cc: Fix utf8. * laurent/playing_with_attributes.cc: New. laurent/ismm2009.cc | 269 ++++++++++++++++++++++++++++--------- laurent/ismm2009.v0.cc | 2 laurent/playing_with_attributes.cc | 101 +++++++++++++ theo/color/blen_pix.hh | 17 ++ theo/color/segment.cc | 18 +- theo/color/sum_pix.hh | 2 6 files changed, 334 insertions(+), 75 deletions(-) Index: theo/color/sum_pix.hh --- theo/color/sum_pix.hh (revision 3168) +++ theo/color/sum_pix.hh (working copy) @@ -125,7 +125,7 @@ inline void sum_pix<P,S>::take(const argument& p) { - s_ += 1 + p.v(); + s_ += /* 1 + */ p.v(); } template <typename P, typename S> Index: theo/color/segment.cc --- theo/color/segment.cc (revision 3168) +++ theo/color/segment.cc (working copy) @@ -459,7 +459,6 @@ if (echo) debug::println("nchildren =", nchildren | t.nodes()); - // Filtering. mln_concrete(I) g; { @@ -497,14 +496,22 @@ unsigned n_regmins_g_ref; mln_ch_value(I, unsigned) regmin_g = labeling::regional_minima(g_ref, nbh, n_regmins_g_ref); - if (echo) +// if (echo) std::cout << "n_regmins(g_ref) = " << n_regmins_g_ref << std::endl << std::endl; if (g != g_ref) + { std::cerr << "OOPS: g DIFFERS FROM ref!" << std::endl << std::endl; +// debug::println("diff", (pw::value(g_ref) == pw::value(g)) | g.domain()); + +// debug::println("g_ref", g_ref); +// debug::println("g", g); +// debug::println("regmin_g", regmin_g); + } + // bool consistency = (n_regmins_g_ref + less == n_objects); // if (consistency == false) // std::cerr << "OOPS: INCONSISTENCY (BUG...)!" << std::endl @@ -570,10 +577,10 @@ // accu::count< util::pix > a_; // accu::volume a_; - accu::sum_pix< util::pix > a_; + // accu::sum_pix< util::pix > a_; -// blen_image = input_; -// accu::blen_pix a_; + blen_image = input_; + accu::blen_pix a_; mln_VAR(a, compute_attribute_on_nodes(a_, t)); @@ -605,7 +612,6 @@ } io::pgm::save(w_all, "temp_w_all.pgm"); - } Index: theo/color/blen_pix.hh --- theo/color/blen_pix.hh (revision 3168) +++ theo/color/blen_pix.hh (working copy) @@ -112,6 +112,19 @@ } + template <typename B> + unsigned sum_len(const Box& b_) + { + const B& b = exact(b_); + typedef mln_site(B) P; + enum { n = P::dim }; + unsigned len = 0; + for (unsigned i = 0; i < n; ++i) + len += b.len(i); + return len; + } + + # ifndef MLN_INCLUDE_ONLY template <typename I> @@ -136,7 +149,7 @@ { const mln_site(I)& p = pxl.p(); accu_blen_take(b_, p); - len_ = max_len(b_.to_result()); + len_ = sum_len(b_.to_result()); } template <typename I> @@ -145,7 +158,7 @@ blen_pix::take(const blen_pix& other) { b_.take(other.b()); - len_ = max_len(b_.to_result()); + len_ = sum_len(b_.to_result()); } template <typename I> Index: laurent/ismm2009.cc --- laurent/ismm2009.cc (revision 3168) +++ laurent/ismm2009.cc (working copy) @@ -71,25 +71,36 @@ } - // Get smallest edge. - template <typename Qs, typename L, typename W> - mln_deduce(Qs, element, element) - get_smallest_edge(Qs& qs, L l, const W& wst, std::vector<L>& lpar, bool& found) - { - typedef mln_element(Qs) Q; // qs is an array of queues with type Q. + // Test emptiness of the queue of a set of regions. + + template <typename Qs, typename L> + bool test_q_emptiness(Qs& qs, L l, std::vector<L>& lpar) { - // Test that, when a region has merged, its edge queue has been - // emptied. L l_ = l; while (lpar[l_] != l_) { - mln_invariant(qs[l_].is_empty()); + if (! qs[l_].is_empty()) + return false; l_ = lpar[l_]; } + return true; } + + // Get smallest edge. + + template <typename Qs, typename L, typename W> + mln_deduce(Qs, element, element) + get_smallest_edge(Qs& qs, L l, const W& wst, std::vector<L>& lpar) + { + typedef mln_element(Qs) Q; // qs is an array of queues with type Q. + + // Test that, when a region has merged, its edge queue has been + // emptied. + mln_invariant(test_q_emptiness(qs, l, lpar)); + L lr = find_root_l(lpar, l); Q& q = qs[lr]; @@ -97,7 +108,8 @@ while (! q.is_empty()) { - const E& e = q.front(); + E e = q.pop_front(); + L l1 = wst(p1_from_e(e)), l2 = wst(p2_from_e(e)); mln_invariant(l1 != l2); @@ -108,16 +120,13 @@ if (l1r == l2r) // 'e' is an internal edge => forget it. - { - q.pop(); continue; - } - found = true; return e; } - found = false; + mln_invariant(0); // We should not be here! + return E(0,0); // FIXME: null edge. } @@ -208,6 +217,115 @@ } + + + // Transform attributes so that they are all different! + + + template <typename A, typename L> + void + make_unique_attribute(util::array<A>& a, + std::vector< std::pair<A,L> >& v, + L l_max, + bool echo) + { + // Display attributes. + if (echo) + { + std::cout << "(attribute, label) = { "; + for (unsigned i = 1; i <= l_max; ++i) + std::cout << '(' << v[i].first // Attribute (increasing). + << ',' + << v[i].second // Region label. + << ") "; + std::cout << '}' << std::endl + << std::endl; + } + + std::map<A,A> lut; // old value -> new value + for (unsigned l = 1; l <= l_max; ++l) + { + A old_a = v[l].first, + new_a = old_a + l - 1; + lut[old_a] = new_a; + v[l].first = new_a; // new value + } + for (unsigned l = 1; l <= l_max; ++l) + a[l] = lut[ a[l] ]; + } + + + + // Compute g from f; then transform g into g' so that all values are + // different; last return the watershed of g'. + + + template < typename F, + typename G, + typename N_e2p, + typename N_e2e, + typename L > + mln_ch_value(G, L) + f_to_wst_unique_g(F& f, // On pixels. + G& g, // On edges. + const N_e2p& e2p, + const N_e2e& e2e, + L& n_basins, + bool echo) + { + data::paste(morpho::gradient(extend(g, f), + e2p.win()), + g); + + // FIXME: Here, we want a unique value per edge! + + if (echo) + debug::println("g (before):", g); + + { + + typedef std::pair<short, short> edge_t; + typedef std::pair<mln_value(G), edge_t> ve_t; + std::vector<ve_t> tmp; + { + mln_piter(G) e(g.domain()); + for_all(e) + { + ve_t ve; + ve.first = g(e); + ve.second = edge_t(e.row(), e.col()); + tmp.push_back(ve); + } + } + std::sort(tmp.begin(), tmp.end()); + { + mln_value(G) v; + mln_site(G) e; + for (unsigned i = 0; i < tmp.size(); ++i) + { + v = tmp[i].first + i; + e.row() = tmp[i].second.first; + e.col() = tmp[i].second.second; + g(e) = v; + } + } + } + + mln_VAR( wst_g, + morpho::meyer_wst(g, e2e, n_basins) ); + +// // Test the consistency with regional minima. +// { +// L n_regmins; +// mln_VAR( regmin_g, +// labeling::regional_minima(g, e2e, n_regmins) ); +// mln_invariant(n_basins == n_regmins); +// } + + return wst_g; + } + + } // mln @@ -229,6 +347,8 @@ using value::int_u8; using value::label_16; + bool echo = true; + if (argc != 2) usage(argv); @@ -241,7 +361,8 @@ Complex f_ = add_edges(raw_f); mln_VAR(f, f_ | is_pixel); - // debug::println("f:", f); + if (echo) + debug::println("f:", f); mln_VAR(g, f_ | is_edge); @@ -250,21 +371,34 @@ typedef label_16 L; // Type of labels. L n_basins; + mln_VAR( wst_g, f_to_wst_g(f, g, e2p(), e2e(), n_basins) ); - std::cout << "n basins = " << n_basins << std::endl; + /* + UNIQUE: + + mln_VAR( wst_g, + f_to_wst_unique_g(f, g, e2p(), e2e(), n_basins, echo) ); + */ + + if (echo) + { + std::cout << "n basins = " << n_basins << std::endl; debug::println("g:", g); debug::println("wst(g):", wst_g); - + } // Just to see things. - // + mln_VAR(adj, adjacency(wst_g, e2e())); + if (echo) debug::println("adj:", adj); + mln_VAR(adj_line, adj | (pw::value(wst_g) == pw::cst(0))); + if (echo) debug::println("adjacency:", adj_line); @@ -286,9 +420,11 @@ // Depict the watershed line. mln_VAR(is_line, pw::value(wst_g_full) == pw::cst(0)); - // --- debug::println("wst(g) line:", wst_g | is_line); + if (echo) + debug::println("wst(g) line:", wst_g | is_line); mln_VAR(g_line, g | is_line); + if (echo) debug::println("g | wst(g) line:", g_line); @@ -336,17 +472,6 @@ // if l1r = l2r. -// // Test the 'get_smallest_edge' routine. -// { -// bool found; -// for (L l = 1; l <= n_basins; ++l) -// { -// E e = get_smallest_edge(q, l, wst_g_full, lpar, found); -// std::cout << l << ": e = " << e -// << " -- g(e) = " << g(e) << std::endl; -// } -// } - E null = E(0,0); // Impossible value. @@ -376,7 +501,15 @@ std::vector<pair_t> v = sort_attributes(a, n_basins); // Sort regions. + + // Maybe activate to test purpose: + /* + make_unique_attribute(a, v, n_basins, echo); + */ + + // Display attributes. + if (echo) { std::cout << "(attribute, label) = { "; for (unsigned i = 1; i <= n_basins; ++i) @@ -408,6 +541,7 @@ epar(e) = e; z_epar(e) = e; } + if (echo) debug::println("all edges:", epar); // epar(e) == e so we depict the edges! } @@ -421,19 +555,13 @@ data::fill(aa, 0); // Safety iff 0 is an invalidate attribute value! - for (unsigned i = 1; i <= n_basins; ++i) - { - L l = v[i].second; // Region label. - bool found; - E e = get_smallest_edge(q, l, wst_g_full, lpar, found); + // The last iteration (i == n_basins) is useless: all regions have + // already merged. - if (! found) + for (unsigned i = 1; i < n_basins; ++i) { - // The last iteration is useless: all regions have already - // merged. We could have written: "for i = 1 to n_basins - 1". - mln_invariant(i == n_basins); - break; - } + L l = v[i].second; // Region label. + E e = get_smallest_edge(q, l, wst_g_full, lpar); L l1 = wst_g_full(p1_from_e(e)), l2 = wst_g_full(p2_from_e(e)), @@ -568,47 +696,51 @@ - // Displaying the "edge tree". + // About the "edge tree" and attributes. { - p_set<E> leaves; - - // Region l -> edge e. - - std::cout << "region:(edge) = "; + p_set<E> leaves; for (L l = 1; l <= n_basins; ++l) { mln_invariant(edge[l] != null); leaves.insert(edge[l]); - std::cout << l << ':' << edge[l] << " "; } - std::cout << std::endl - << std::endl; + // Tests. mln_piter_(p_set<E>) e(leaves); - - - // Tree "e -> epar(e)". - - std::cout << "edge tree: " << std::endl; for_all(e) { E e_ = e; do { - std::cout << e_ << " -> "; mln_invariant(aa(e_) != 0 && aa(epar(e_)) != 0); // aa is valid - mln_invariant(aa(epar(e_)) >= aa(e_)); + mln_invariant(aa(epar(e_)) >= aa(e_)); // edge parenthood goes with 'a' increasing e_ = epar(e_); } while (epar(e_) != e_); - std::cout << e_ << std::endl; } - std::cout << std::endl; + // Display. + if (echo) + { + std::cout << "region:(edge) = "; + for (L l = 1; l <= n_basins; ++l) + std::cout << l << ':' << edge[l] << " "; + std::cout << std::endl + << std::endl; - // Edge parenthood goes with 'a' increasing: + std::cout << "edge tree: " << std::endl; + for_all(e) { + E e_ = e; + do { + std::cout << e_ << " -> "; + e_ = epar(e_); + } + while (epar(e_) != e_); + std::cout << e_ << std::endl; + } + std::cout << std::endl; std::cout << "edge tree new attributes: " << std::endl; for_all(e) @@ -617,8 +749,6 @@ do { std::cout << aa(e_) << " -> "; - // Edge parenthood goes with a increasing: - mln_invariant(aa(epar(e_)) >= aa(e_)); e_ = epar(e_); } while (epar(e_) != e_); @@ -626,7 +756,10 @@ } std::cout << std::endl; - } // end of tree display. + } // end of Display. + + + } // end of About the "edge tree" and attributes. @@ -649,8 +782,11 @@ // Reminders: + if (echo) + { debug::println("wst(g) fully valuated:", wst_g_full); debug::println("g_line:", g_line); + } @@ -687,6 +823,7 @@ aa(e) = aa(e_); } + if (echo) debug::println("aa | wst(g) line:", (aa | is_edge) | is_line); // Second, processing the 0D-faces (points) of the watershed line. @@ -730,6 +867,7 @@ } + if (echo) debug::println("aa | line:", aa_line); @@ -747,16 +885,17 @@ aa(p) = a[wst_g_full(p)]; } + if (echo) debug::println("aa | basins", aa_basins); } + if (echo) debug::println("aa:", aa); - } // end of main Index: laurent/ismm2009.v0.cc --- laurent/ismm2009.v0.cc (revision 3168) +++ laurent/ismm2009.v0.cc (working copy) @@ -387,7 +387,7 @@ debug::println("adjacency:", adj | (pw::value(wst_g) == pw::cst(0))); - /* // Délire! + /* // De'lire! { box2d b = make::box2d(1,1, n_basins, n_basins); point2d null(0, 0); Index: laurent/playing_with_attributes.cc --- laurent/playing_with_attributes.cc (revision 0) +++ laurent/playing_with_attributes.cc (revision 0) @@ -0,0 +1,101 @@ +#include "ismm2009.hh" + +#include <mln/value/int_u8.hh> +#include <mln/value/label_8.hh> +#include <mln/value/label_16.hh> + +#include <mln/io/pgm/load.hh> +#include <mln/debug/println.hh> + +#include <mln/morpho/elementary/gradient.hh> +#include <mln/morpho/gradient.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> + + + +void usage(char* argv[]) +{ + std::cerr << "usage: " << argv[0] << " input.pgm" << std::endl; + std::cerr << "For Laurent's ISMM 2009 scheme: min-tree, attributes, and watershed." << std::endl; + abort(); +} + + + +template <typename I, typename N, typename L> +void do_it(const I& g, const N& nbh, L& n_labels) +{ + using namespace mln; + + // regional minima + + mln_ch_value(I,L) regmin = labeling::regional_minima(g, nbh, n_labels); + debug::println("regmin(g):", regmin); + + + // watershed + + L n_basins; + mln_ch_value(I,L) w = morpho::meyer_wst(g, nbh, n_basins); + mln_invariant(n_basins == n_labels); + debug::println("w(g):", w); + + + { + typedef p_array<mln_site(I)> S; + S s = level::sort_psites_decreasing(g); + + typedef morpho::tree::data<I,S> tree_t; + tree_t t(g, s, nbh); + + accu::count< util::pix > a_; // Kind of attribute. + + mln_ch_value(I,unsigned) a = morpho::tree::compute_attribute_image(a_, t); + debug::println("a:", a); + + debug::println("a | w line:", a | (pw::value(w) == pw::cst(0))); + debug::println("a | w basins:", a | (pw::value(w) != pw::cst(0))); + + debug::println("a | regmin:", a | (pw::value(regmin) != pw::cst(0))); + } + +} // end of do_it + + + +int main(int argc, char* argv[]) +{ + using namespace mln; + using value::int_u8; + + + typedef image2d<int_u8> I; + typedef value::label_8 L; + + border::thickness = 0; + + if (argc != 2) + usage(argv); + + I raw_f; + io::pgm::load(raw_f, argv[1]); + + + I f_ = add_edges(raw_f); + mln_VAR(f, f_ | is_pixel); + debug::println("f:", f); + + mln_VAR(g, f_ | is_edge); + data::paste( morpho::gradient(extend(g, f_), + e2p().win()), + g ); + debug::println("g:", g); + + L n; + do_it(g, e2e(), n); + +}

1 0

3167: Rename histo::data as histo::array.
by Guillaume Lazzara 19 Jan '09

19 Jan '09

* tests/core/other/var.cc, * tests/histo/compute.cc, * tests/histo/to_image1d.cc: rename here. --- milena/ChangeLog | 8 ++++++++ milena/tests/core/other/var.cc | 6 +++--- milena/tests/histo/compute.cc | 14 +++++++------- milena/tests/histo/to_image1d.cc | 8 ++++---- 4 files changed, 22 insertions(+), 14 deletions(-) diff --git a/milena/ChangeLog b/milena/ChangeLog index 8201593..f059029 100644 --- a/milena/ChangeLog +++ b/milena/ChangeLog @@ -1,5 +1,13 @@ 2009-01-19 Guillaume Lazzara <z(a)lrde.epita.fr> + Rename histo::data as histo::array. + + * tests/core/other/var.cc, + * tests/histo/compute.cc, + * tests/histo/to_image1d.cc: rename here. + +2009-01-19 Guillaume Lazzara <z(a)lrde.epita.fr> + Improve soft heap interface. * mln/util/soft_heap.hh: rename take() as push(). diff --git a/milena/tests/core/other/var.cc b/milena/tests/core/other/var.cc index 6079142..1fd8dfc 100644 --- a/milena/tests/core/other/var.cc +++ b/milena/tests/core/other/var.cc @@ -33,7 +33,7 @@ #include <mln/core/image/image2d.hh> #include <mln/core/alias/window2d.hh> #include <mln/core/alias/neighb2d.hh> -#include <mln/histo/data.hh> +#include <mln/histo/array.hh> #include <mln/util/array.hh> #include <mln/core/var.hh> @@ -73,7 +73,7 @@ void test_template() mln_BKD_EITER(e, arr); } - histo::data<bool> d; + histo::array<bool> d; { mln_VITER(v, d.vset()); } @@ -120,7 +120,7 @@ void test() mln_BKD_EITER_(e, arr); } - histo::data<bool> d; + histo::array<bool> d; { mln_VITER_(v, d.vset()); } diff --git a/milena/tests/histo/compute.cc b/milena/tests/histo/compute.cc index f2bc569..f00d7d2 100644 --- a/milena/tests/histo/compute.cc +++ b/milena/tests/histo/compute.cc @@ -1,4 +1,5 @@ -// Copyright (C) 2007, 2008 EPITA Research and Development Laboratory +// Copyright (C) 2007, 2008, 2009 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 @@ -25,10 +26,9 @@ // reasons why the executable file might be covered by the GNU General // Public License. -/*! \file tests/histo/compute.cc - * - * \brief Tests on mln::accu::histo and mln::histo::data. - */ +/// \file tests/histo/compute.cc +/// +/// Tests on mln::accu::histo and mln::histo::array. #include <iterator> #include <sstream> @@ -70,7 +70,7 @@ int main() debug::iota(ima); opt::at(ima, 0,0) = 2; - histo::data<int_u8> h = histo::compute(ima); + histo::array<int_u8> h = histo::compute(ima); std::ostringstream oss; oss << h; mln_assertion(oss.str() == "2:2 3:1 4:1 5:1 6:1 7:1 8:1 9:1 "); @@ -86,7 +86,7 @@ int main() image2d<int_s5> ima(3, 3); debug::iota(ima); - histo::data<int_s5> h = histo::compute(ima); + histo::array<int_s5> h = histo::compute(ima); mln_assertion(h.vset().nvalues() == 31); for (unsigned i = 0; i <= 15; ++i) // values from -15 to 0 diff --git a/milena/tests/histo/to_image1d.cc b/milena/tests/histo/to_image1d.cc index ee09b85..aad3c99 100644 --- a/milena/tests/histo/to_image1d.cc +++ b/milena/tests/histo/to_image1d.cc @@ -1,5 +1,5 @@ -// Copyright (C) 2007, 2008 EPITA Research and Development Laboratory -// (LRDE +// Copyright (C) 2007, 2008, 2009 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,7 +28,7 @@ /// \file tests/histo/to_image1d.cc /// -/// Tests on mln::accu::histo and mln::histo::data. +/// Tests on mln::accu::histo and mln::histo::array. #include <iterator> @@ -68,7 +68,7 @@ int main() debug::iota(ima); ima(point2d(0,1)) = 255; debug::println(ima); - histo::data<int_u8> h = histo::compute(ima); + histo::array<int_u8> h = histo::compute(ima); std::cout << h << std::endl; image1d<unsigned> ima2 = convert::to_image(h); -- 1.5.6.5

1 0