- Olena-patches

3290: Augment Laurent's code.
by Thierry Geraud 05 Feb '09

05 Feb '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 code. * theo/esiee/laurent/ismm09/topo_wst.cc (ls): Rename as... (l_): ...this. * theo/esiee/laurent/ismm09/main.cc: Update. * theo/esiee/laurent/ismm09/pseudo_tree.hh: Augment. * theo/esiee/laurent/ismm09/lca.hh: Update. lca.hh | 2 main.cc | 19 +++--- pseudo_tree.hh | 178 ++++++++++++++++++++++++++++++++++++++++++++++++++++----- topo_wst.cc | 8 +- 4 files changed, 178 insertions(+), 29 deletions(-) Index: theo/esiee/laurent/ismm09/topo_wst.cc --- theo/esiee/laurent/ismm09/topo_wst.cc (revision 3289) +++ theo/esiee/laurent/ismm09/topo_wst.cc (working copy) @@ -81,12 +81,12 @@ a[++l] = f(p); } - util::array<L> ls = sort_by_increasing_attributes(a, l_max); + util::array<L> l_ = sort_by_increasing_attributes(a, l_max); { - std::cout << "ls:" << std::endl; + std::cout << "l_:" << std::endl; for (unsigned i = 1; i <= l_max; ++i) - std::cout << ls[i] << "(" << a[ls[i]] << ") "; + std::cout << l_[i] << "(" << a[l_[i]] << ") "; std::cout << std::endl << std::endl; } @@ -95,5 +95,5 @@ // -> pseudo-tree - compute_pseudo_tree(w_ext, g, ls, a, e_to_l1_l2); + compute_pseudo_tree(w_ext, g, l_, a, e_to_l1_l2); } Index: theo/esiee/laurent/ismm09/main.cc --- theo/esiee/laurent/ismm09/main.cc (revision 3289) +++ theo/esiee/laurent/ismm09/main.cc (working copy) @@ -91,19 +91,20 @@ w, // image of labels l_max); - util::array<L> ls = sort_by_increasing_attributes(a, l_max); + util::array<L> l_ = sort_by_increasing_attributes(a, l_max); -// { -// std::cout << "ls:" << std::endl; -// for (unsigned i = 1; i <= l_max; ++i) -// std::cout << ls[i] << "(" << a[ls[i]] << ") "; -// std::cout << std::endl -// << std::endl; -// } + { + std::cout << "l_:" << std::endl; + for (unsigned i = 1; i <= l_max; ++i) + std::cout << l_[i] << "(" << a[l_[i]] << ") "; + std::cout << std::endl + << std::endl; + } // -> pseudo-tree - compute_pseudo_tree(w, g, ls, a, e_to_l1_l2); + compute_pseudo_tree(w_ext, g, l_, a, e_to_l1_l2); + } Index: theo/esiee/laurent/ismm09/pseudo_tree.hh --- theo/esiee/laurent/ismm09/pseudo_tree.hh (revision 3289) +++ theo/esiee/laurent/ismm09/pseudo_tree.hh (working copy) @@ -1,10 +1,25 @@ #include <mln/core/concept/image.hh> +#include <mln/core/site_set/p_set.hh> #include <mln/core/site_set/p_queue.hh> #include <mln/core/site_set/p_priority.hh> + #include <mln/data/fill.hh> +#include <mln/data/paste.hh> #include <mln/util/array.hh> +#include "lca.hh" + + +// FIXME: Move elsewhere. +#include <mln/core/alias/neighb2d.hh> +#include <mln/morpho/dilation.hh> +#include <mln/core/image/image2d.hh> +#include <mln/value/int_u8.hh> +#include <mln/io/pgm/save.hh> +#include <mln/level/stretch.hh> + + namespace mln @@ -178,20 +193,24 @@ typename F> void compute_pseudo_tree(const W& w, - const G& g, - const util::array<L>& ls, - const A& a, + const G& g, // FIXME: Directly input g_line? + const util::array<L>& l_, + const util::array<A>& a, const F& e_to_l1_l2) { typedef mln_value(G) T; // <--- Type of edge values. typedef mln_psite(G) E; // <--- Type of edges. - const L l_max = ls.nelements() - 1; + const L l_max = l_.nelements() - 1; mln_VAR( g_line, g | (pw::value(w) == 0) ); + // Initialization. + // ----------------------------------- + + // Edges -> Priority queue. typedef p_priority< T, p_queue<E> > Q; @@ -212,8 +231,12 @@ - // Initialization. - // ----------------------------------- + + // 'aa' is the resulting attributes on edges. + + mln_ch_value(g_line_t, A) aa; + initialize(aa, g_line); + data::fill(aa, 0); // FIXME: Safety iff 0 is an invalidate attribute value! @@ -274,12 +297,13 @@ for (unsigned i = 1; i < l_max; ++i) { - L l = ls[i]; // Region label. + L l = l_[i]; // Region label. L l1, l2; E e; get_smallest_edge(q, // in-out l, w, lpar, e_to_l1_l2, // in e, l1, l2); // out + aa(e) = a[l]; L l1r = find_root_l(lpar, l1), l2r = find_root_l(lpar, l2); @@ -288,7 +312,7 @@ { if (i > 1) { - L former_l = ls[i-1]; + L former_l = l_[i-1]; mln_invariant(a[l] >= a[former_l]); } mln_invariant(epar(e) == e); // 'e' has not been processed yet. @@ -302,11 +326,6 @@ } - - // aa(e) = a[l]; // FIXME: Re-activate. - - - /* std::cout << "l = " << l << " e = " << e @@ -422,7 +441,11 @@ { - // Display edge tree. + // Display 'aa' over all edges. + + debug::println("aa (on 'passing' edges):", aa); + + // Display "edge tree". mln_ch_value(g_line_t, bool) deja_vu; initialize(deja_vu, g_line); @@ -435,15 +458,140 @@ E e = edge[l]; while (! deja_vu(e)) { - std::cout << e << " -> "; + std::cout << e << " [" << aa(e) << "] -> "; + mln_invariant(aa(e) != 0 && aa(epar(e)) != 0); // aa is valid + mln_invariant(aa(epar(e)) >= aa(e)); // edge parenthood goes with 'aa' increasing deja_vu(e) = true; e = epar(e); } std::cout << e << std::endl; } + std::cout << std::endl; + + // Display "region l -> edge e". + + std::cout << "region:(edge) = "; + for (L l = 1; l <= l_max; ++l) + std::cout << l << ':' << edge[l] << " "; + std::cout << std::endl + << std::endl; + + } // end of Display. + + + + // Testing both that all regions and all "smallest" edges have + // merged (assumption: connected domain!). + + { + L l_1 = l_[1], + l_root = find_root_l(lpar, l_1); + mln_invariant(edge[l_1] != null); + E e_root = find_root_e(z_epar, edge[l_1]); + for (unsigned i = 2; i <= l_max; ++i) + { + L l = l_[i]; + mln_invariant(find_root_l(lpar, l) == l_root); + mln_invariant(edge[l] != null); + mln_invariant(find_root_e(z_epar, edge[l]) == e_root); + } } + + // Finalization. + + A aa_max = mln_min(A); + + { + mln_VAR(aa_ext, aa.unmorph_().unmorph_()); + + + debug::println("aa ext (1):", aa_ext); + + + std::vector<E> roots; + mln_VAR(chl, compute_children(epar, edge, l_max, roots)); + + // Connected domain so: + mln_invariant(roots.size() == 1); + E root = roots[0]; // THE root. + + lca_t<L,chl_t,E> lca(l_max, chl, roots); + + mln_piter(g_line_t) e(g_line.domain()); + for_all(e) + { + L l1, l2; + e_to_l1_l2(e, l1, l2); + mln_invariant(l1 != 0 && l2 > l1); + E e_ = lca(edge[l1],edge[l2]); + + mln_invariant(g_line.has(e_)); // e_ is a valid edge. + mln_invariant(aa(e_) != 0); // aa is valid at e_. + + // The attribute value propagates from the lca to the current edge + // of the line: + aa(e) = aa(e_); + if (aa(e) > aa_max) + aa_max = aa(e); + } + + debug::println("aa:", aa); + + debug::println("aa ext (2):", aa_ext); + + { + mln_VAR( aa_line, aa_ext | (pw::value(w) == 0) ); + + data::paste(morpho::dilation(extend(aa_line | (pw::value(aa_line) == 0), + aa_line), + c4().win()), + aa_line); + } + + debug::println("aa ext (3):", aa_ext); + + + { + using value::int_u8; + if (aa_max < 256) + { + image2d<int_u8> output(aa_ext.domain()); + data::fill(output, 0); + data::paste(aa_ext, output); + io::pgm::save(output, "aa_line.pgm"); + } + else + { + std::cerr << "warning: stretching [0," << aa_max << "] to int_u8" << std::endl; + + image2d<int_u8> output(aa_ext.domain()); + data::fill(output, 0); + data::paste(aa_ext, output); + io::pgm::save(level::stretch(int_u8(), output), + "aa_line.pgm"); } + } + + +// mln_VAR(aa_basins, aa_ext | (pw::value(w) != 0)); +// { +// mln_piter(aa_basins_t) p(aa_basins.domain()); +// for_all(p) +// { +// L l = w(p); +// aa_basins(p) = aa( edge[l] ); // FIXME: was: a[w(p)]; +// } +// } + + +// debug::println("aa ext (4):", aa_ext); + + } + + + } + } // end of namespace mln Index: theo/esiee/laurent/ismm09/lca.hh --- theo/esiee/laurent/ismm09/lca.hh (revision 3289) +++ theo/esiee/laurent/ismm09/lca.hh (working copy) @@ -7,7 +7,7 @@ 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) + compute_children(const I& epar, const util::array<E>& edge, L l_max, std::vector<E>& roots) { typedef std::vector<mln_psite(I)> C; // Children. mln_ch_value(I,C) chl;

1 0

3289: Cleanup Fabien's 1st try.
by Thierry Geraud 05 Feb '09

05 Feb '09

https://svn.lrde.epita.fr/svn/oln/trunk/milena/sandbox Index: ChangeLog from Thierry Geraud <thierry.geraud(a)lrde.epita.fr> Cleanup Fabien's 1st try. * fabien/regional_maxima.hh, * fabien/labeling.hh: Fix paren balancing. Cleanup a bit. labeling.hh | 387 ++++++++++++++++++++++++++++------------------------- regional_maxima.hh | 7 2 files changed, 214 insertions(+), 180 deletions(-) Index: fabien/regional_maxima.hh --- fabien/regional_maxima.hh (revision 3288) +++ fabien/regional_maxima.hh (working copy) @@ -122,12 +122,13 @@ + // Facade. template <typename I, typename N, typename L> mln_ch_value(I, L) regional_maxima(const Image& input_, const Neighborhood<N>& nbh_, - bool increasing, L& nlabels) + L& nlabels) { trace::entering("labeling::regional_maxima"); @@ -137,8 +138,8 @@ typedef impl::regional_maxima_functor F; F f(exact(input)); - mln_ch_value(I, L) output = canvas::labeling_sorted(input, nbh, increasing, - f, nlabels); + mln_ch_value(I, L) output = canvas::labeling_sorted(input, nbh, nlabels, + f, false); trace::exiting("labeling::regional_maxima"); return output; Index: fabien/labeling.hh --- fabien/labeling.hh (revision 3288) +++ fabien/labeling.hh (working copy) @@ -40,6 +40,9 @@ # include <mln/literal/zero.hh> # include <mln/convert/to_upper_window.hh> +# include <mln/level/sort_psites.hh> +# include <mln/level/sort_offsets.hh> + namespace mln { @@ -47,11 +50,20 @@ namespace canvas { - // General version. - template <typename I, typename N, typename F, typename L> + template <typename I, typename N, typename L, + typename F> + mln_ch_value(I, L) + labeling_video(const Image& input, const Neighborhood<N>& nbh, L& nlabels, + F& functor); + + + template <typename I, typename N, typename L, + typename F> mln_ch_value(I, L) - labeling(const Image& input, const Neighborhood<N>& nbh, - F& functor, L& nlabels); + labeling_sorted(const Image& input, const Neighborhood<N>& nbh, L& nlabels, + F& functor, bool increasing); + + # ifndef MLN_INCLUDE_ONLY @@ -61,10 +73,11 @@ namespace internal { - template <typename I, typename N, typename F, typename L> + template <typename I, typename N, typename L, + typename F> void - labeling_tests(const Image& input_, const Neighborhood<N>& nbh_, - const F& f, const L& nlabels) + labeling_tests(const Image& input_, const Neighborhood<N>& nbh_, const L& nlabels, + const F& f) { const I& input = exact(input_); const N& nbh = exact(nbh_); @@ -74,8 +87,8 @@ (void) input; (void) nbh; - (void) f; (void) nlabels; + (void) f; } } // end of namespace mln::canvas::internal @@ -101,10 +114,11 @@ return parent(x) = find_root(parent, parent(x)); } - template <typename I, typename N, typename S, typename F, typename L> + template <typename I, typename N, typename L, + typename S, typename F> mln_ch_value(I, L) - labeling(const Image& input_, const Neighborhood<N>& nbh_, - S& s, F& f, L& nlabels) + labeling(const Image& input_, const Neighborhood<N>& nbh_, L& nlabels, + const S& s, F& f) { trace::entering("canvas::impl::generic::labeling"); @@ -199,7 +213,7 @@ - // Fastest video version + // Fastest video version. template <typename I> static inline @@ -212,110 +226,112 @@ return parent.element(x) = find_root(parent, parent.element(x)); } - // FIXME: Use the same functer for the generic and the fastest versions - - template <typename I, typename N, typename F, typename L> - mln_ch_value(I, L) - labeling_fastest_video(const Image& input_, const Neighborhood<N>& nbh_, - F& f, L& nlabels) - { - trace::entering("canvas::impl::labeling"); - - // FIXME: Test?! - - const I& input = exact(input_); - const N& nbh = exact(nbh_); - - // Local type. - typedef mln_psite(I) P; - - // Auxiliary data. - mln_ch_value(I, bool) deja_vu; - mln_ch_value(I, P) parent; - - // Output. - mln_ch_value(I, L) output; - bool status; - - // Initialization. - { - initialize(deja_vu, input); - mln::data::fill(deja_vu, false); - - initialize(parent, input); - - initialize(output, input); - mln::data::fill(output, L(literal::zero)); - nlabels = 0; - - f.init(); // Client initialization. - } - - // First Pass. - { - mln_pixter(const S) p(f.s); - mln_nixter(const S, N) n(p, nbh); - for_all(p) if (f.handles(p)) - { - // Make-Set. - parent.element(p) = p; - f.init_attr(p); - - for_all(n) - if (input.has(n) && deja_vu(n)) - { - if (f.equiv(n, p)) - { - // Do-Union. - unsigned r = find_root_fastest(parent, n); - if (r != p) - { - parent.element(r) = p; - f.merge_attr(r, p); - } - } - else - f.do_no_union(n, p); - (p) = true; - } - } - - // Second Pass. - { - mln_bkd_pixter(S) p(f.s); - for_all(p) if (f.handles(p)) - { - if (parent.element(p) == p) // if p is root - { - if (f.labels(p)) - { - if (nlabels == mln_max(L)) - { - status = false; - return output; - } - output.element(p) = ++nlabels; - } - } - else - output.element(p) = output(parent.element(p)); - } - status = true; - } +// // FIXME: Use the same functer for the generic and the fastest versions - trace::exiting("canvas::impl::labeling"); - return output; - } +// template <typename I, typename N, typename L, +// typename F> +// mln_ch_value(I, L) +// labeling_fastest_video(const Image& input_, const Neighborhood<N>& nbh_, +// F& f, L& nlabels) +// { +// trace::entering("canvas::impl::labeling"); + +// // FIXME: Test?! + +// const I& input = exact(input_); +// const N& nbh = exact(nbh_); + +// // Local type. +// typedef mln_psite(I) P; + +// // Auxiliary data. +// mln_ch_value(I, bool) deja_vu; +// mln_ch_value(I, P) parent; + +// // Output. +// mln_ch_value(I, L) output; +// bool status; + +// // Initialization. +// { +// initialize(deja_vu, input); +// mln::data::fill(deja_vu, false); + +// initialize(parent, input); + +// initialize(output, input); +// mln::data::fill(output, L(literal::zero)); +// nlabels = 0; + +// f.init(); // Client initialization. +// } + +// // First Pass. +// { +// mln_pixter(const S) p(f.s); +// mln_nixter(const S, N) n(p, nbh); +// for_all(p) if (f.handles(p)) +// { +// // Make-Set. +// parent.element(p) = p; +// f.init_attr(p); + +// for_all(n) +// if (input.has(n) && deja_vu(n)) +// { +// if (f.equiv(n, p)) +// { +// // Do-Union. +// unsigned r = find_root_fastest(parent, n); +// if (r != p) +// { +// parent.element(r) = p; +// f.merge_attr(r, p); +// } +// } +// else +// f.do_no_union(n, p); +// (p) = true; +// } +// } +// } + +// // Second Pass. +// { +// mln_bkd_pixter(S) p(f.s); +// for_all(p) if (f.handles(p)) +// { +// if (parent.element(p) == p) // if p is root +// { +// if (f.labels(p)) +// { +// if (nlabels == mln_max(L)) +// { +// status = false; +// return output; +// } +// output.element(p) = ++nlabels; +// } +// } +// else +// output.element(p) = output(parent.element(p)); +// } +// status = true; +// } + +// trace::exiting("canvas::impl::labeling"); +// return output; +// } // Fastest sorted version - template <typename I, typename N, typename S, typename F, typename L> + template <typename I, typename N, typename L, + typename S, typename F> mln_ch_value(I, L) - labeling_fastest_sorted(const Image& input_, - const Neighborhood<N>& nbh_, - S& s, F& f, L& nlabels) + labeling_sorted_fastest(const Image& input_, const Neighborhood<N>& nbh_, L& nlabels, + const S& s, F& f) { trace::entering("canvas::impl::labeling"); @@ -324,8 +340,6 @@ const I& input = exact(input_); const N& nbh = exact(nbh_); - typedef typename F::S S; - // Local type. typedef mln_psite(I) P; @@ -391,6 +405,7 @@ deja_vu.element(p) = true; } + } // Second Pass. { @@ -431,71 +446,84 @@ namespace internal { - // Video +// // Video - template <typename I, typename N, typename F, typename L> - inline - mln_ch_value(I, L) - labeling_video(metal::false_, const Image& input, - const Neighborhood<N>& nbh, F& functor, L& nlabels) - { - return impl::generic::labeling(input, nbh, input.domain(), - functor, nlabels); - } +// template <typename I, typename N, typename L, +// typename F> +// inline +// mln_ch_value(I, L) +// labeling_video(metal::false_, const Image& input, +// const Neighborhood<N>& nbh, L& nlabels, F& functor) +// { +// return impl::generic::labeling(input, nbh, input.domain(), +// nlabels, functor); +// } + +// template <typename I, typename N, typename L, +// typename F> +// inline +// mln_ch_value(I, L) +// labeling_video(metal::true_, const Image& input, +// const Neighborhood<N>& nbh, L& nlabels, F& functor) +// { +// return impl::labeling_fastest_video(input, nbh, nlabels, functor); +// } + +// template <typename I, typename N, typename L, +// typename F> +// inline +// mln_ch_value(I, L) +// labeling_video_dispatch(const Image& input, const Neighborhood<N>& nbh, +// L& nlabels, F& functor) +// { +// enum { +// test = mlc_equal(mln_trait_image_speed(I), +// trait::image::speed::fastest)::value +// && +// mln_is_simple_neighborhood(N)::value +// }; +// return impl::generic::labeling_video(metal::bool_<test>(), input, +// nbh, nlabels, functor); +// } - template <typename I, typename N, typename F, typename L> - inline - mln_ch_value(I, L) - labeling_video(metal::true_, const Image& input, - const Neighborhood<N>& nbh, F& functor, L& nlabels) - { - return impl::labeling_fastest_video(input, nbh, functor, nlabels); - } - - template <typename I, typename N, typename F, typename L> - inline - mln_ch_value(I, L) - labeling_video_dispatch(const Image& input, const Neighborhood<N>& nbh, - F& functor, L& nlabels) - { - enum { - test = mlc_equal(mln_trait_image_speed(I), - trait::image::speed::fastest)::value - && - mln_is_simple_neighborhood(N)::value - }; - return impl::generic::labeling_video(metal::bool_<test>(), input, - nbh, functor, nlabels); - } + // Sorted dispatch. - // Sorted - - template <typename I, typename N, typename S, typename F, typename L> + template <typename I, typename N, typename L, typename F> inline mln_ch_value(I, L) - labeling_sorted(metal::false_, const Image& input, - const Neighborhood<N>& nbh, F& functor, L& nlabels) - { - return impl::generic::labeling(input, nbh, s, functor, nlabels); + labeling_sorted_dispatch(metal::false_, + const Image& input, const Neighborhood<N>& nbh, L& nlabels, + F& functor, bool increasing) + { + p_array<mln_psite(I)> s = + increasing ? + level::sort_psites_increasing(input) : + level::sort_psites_decreasing(input); + return impl::generic::labeling(input, nbh, nlabels, + s, functor); } - template <typename I, typename N, typename S, typename F, typename L> + template <typename I, typename N, typename L, typename F> inline mln_ch_value(I, L) - labeling_sorted(metal::true_, const Image& input, - const Neighborhood<N>& nbh, F& functor, L& nlabels) - { - return impl::labeling_fastest_sorted(input, nbh, s, - functor, nlabels); + labeling_sorted_dispatch(metal::true_, + const Image& input, const Neighborhood<N>& nbh, L& nlabels, + F& functor, bool increasing) + { + util::array<unsigned> s = + increasing ? + level::sort_offsets_increasing(input) : + level::sort_offsets_decreasing(input); + return impl::labeling_sorted_fastest(input, nbh, nlabels, + s, functor); } - template <typename I, typename N, typename S, typename F, typename L> + template <typename I, typename N, typename L, typename F> inline mln_ch_value(I, L) - labeling_sorted_dispatch(const Image& input, - const Neighborhood<N>& nbh, - F& functor, L& nlabels) + labeling_sorted_dispatch(const Image& input, const Neighborhood<N>& nbh, L& nlabels, + F& functor, bool increasing) { enum { test = mlc_equal(mln_trait_image_speed(I), @@ -503,8 +531,9 @@ && mln_is_simple_neighborhood(N)::value }; - return impl::generic::labeling_sorted(metal::bool_<test>(), input, - nbh, s, functor, nlabels); + return labeling_sorted_dispatch(metal::bool_<test>(), + input, nbh, nlabels, + functor, increasing); } @@ -512,39 +541,43 @@ - // Facade. + // Facades. + - template <typename I, typename N, typename F, typename L> + template <typename I, typename N, typename L, + typename F> inline mln_ch_value(I, L) - labeling_video(const Image& input, const Neighborhood<N>& nbh, - F& functor, L& nlabels) + labeling_video(const Image& input, const Neighborhood<N>& nbh, L& nlabels, + F& functor) { trace::entering("canvas::labeling_video"); - internal::labeling_tests(input, nbh, functor, nlabels); + internal::labeling_tests(input, nbh, nlabels, functor); mln_ch_value(I, L) output; - output = internal::labeling_video_dispatch(input, nbh, - functor, nlabels); + output = internal::labeling_video_dispatch(input, nbh, nlabels, + functor); trace::exiting("canvas::labeling_video"); return output; } - template <typename I, typename N, typename F, typename L> + + template <typename I, typename N, typename L, + typename F> inline mln_ch_value(I, L) - labeling_sorted(const Image& input, const Neighborhood<N>& nbh, - bool increasing, F& functor, L& nlabels) + labeling_sorted(const Image& input, const Neighborhood<N>& nbh, L& nlabels, + F& functor, bool increasing) { trace::entering("canvas::labeling_sorted"); - internal::labeling_tests(input, nbh, functor, nlabels); + internal::labeling_tests(input, nbh, nlabels, functor); mln_ch_value(I, L) output; - output = internal::labeling_sorted_dispatch(input, nbh, s, - functor, nlabels); + output = internal::labeling_sorted_dispatch(input, nbh, nlabels, + functor, increasing); trace::exiting("canvas::labeling_sorted"); return output;

1 0

3288: Add a topological wst following Laurent's ISMM09 scheme.
by Thierry Geraud 05 Feb '09

05 Feb '09

https://svn.lrde.epita.fr/svn/oln/trunk/milena/sandbox Index: ChangeLog from Thierry Geraud <thierry.geraud(a)lrde.epita.fr> Add a topological wst following Laurent's ISMM09 scheme. * theo/esiee/laurent/ismm09/main.cc: Copy to... * theo/esiee/laurent/ismm09/topo_wst.cc: ...this new file. Update. * theo/esiee/laurent/ismm09/main.cc (T, E): Remove useless typedefs. main.cc | 4 --- topo_wst.cc | 76 ++++++++++++++++++++++++------------------------------------ 2 files changed, 31 insertions(+), 49 deletions(-) Index: theo/esiee/laurent/ismm09/topo_wst.cc --- theo/esiee/laurent/ismm09/topo_wst.cc (revision 3286) +++ theo/esiee/laurent/ismm09/topo_wst.cc (working copy) @@ -7,9 +7,7 @@ #include <mln/io/pgm/save.hh> #include <mln/debug/println.hh> -#include <mln/morpho/meyer_wst.hh> -#include <mln/labeling/compute.hh> -#include <mln/accu/count.hh> +#include <mln/debug/iota.hh> #include "pseudo_tree.hh" #include "cplx2d.hh" @@ -20,7 +18,7 @@ void usage(char* argv[]) { std::cerr << "usage: " << argv[0] << " input.pgm" << std::endl; - std::cerr << "Laurent ISMM 2009 scheme." << std::endl; + std::cerr << "Laurent topological watershed transform thru ISMM 2009 scheme." << std::endl; abort(); } @@ -40,6 +38,7 @@ image2d<int_u8> f; io::pgm::load(f, argv[1]); + debug::println("f:", f); // g: weights on edges. @@ -47,67 +46,54 @@ mln_VAR(g, cplx2d::f_to_g(f) ); debug::println("g:", g); - typedef mln_value_(g_t) T; // <--- Type of edge values. - typedef mln_psite_(g_t) E; // <--- Type of edges. + // r: one pixel is one region. - // w: watershed labeling on edges. + typedef label_16 L; + L l_max = f.nsites(); - typedef label_16 L; // <--- Type of labels. - L l_max; - mln_VAR( w, morpho::meyer_wst(g, cplx2d::e2e(), l_max) ); - debug::println("w:", w); - - - mln_VAR( is_w_line, pw::value(w) == pw::cst(0) ); - mln_VAR( g_line, g | is_w_line ); - debug::println("g | line:", g_line); - - mln_VAR(w_ext, cplx2d::extend_w_edges_to_all_faces(w)); + image2d<L> w_ext(2 * f.nrows() - 1, 2 * f.ncols() - 1); + data::fill(w_ext, 0); // Useless but for display! + mln_VAR( w_pixel, w_ext | cplx2d::is_pixel ); + { + mln_fwd_piter_(w_pixel_t) p(w_pixel.domain()); + unsigned l = 0; + for_all(p) + w_pixel(p) = ++l; + } debug::println("w_ext:", w_ext); // e -> (l1, l2) mln_VAR( e_to_l1_l2, function_e_to_l1_l2(w_ext, cplx2d::e2p()) ); -// { -// // Test adjacency "e -> (l1, l2)". -// L l1, l2; -// mln_piter_(g_t) e(g.domain()); -// for_all(e) -// if (w(e) == 0) -// { -// e_to_l1_l2(e, l1, l2); -// std::cout << e << "=" << l1 << '|' << l2 << " "; -// } -// std::cout << std::endl; -// } - // a: array "label -> attribute". - typedef unsigned A; // <--- Type of attributes. + typedef int_u8 A; // <--- Type of attributes. - util::array<A> a = labeling::compute(accu::meta::count(), - g, // image of values - w, // image of labels - l_max); + util::array<A> a(l_max.next()); + { + mln_fwd_piter_(box2d) p(f.domain()); + unsigned l = 0; + for_all(p) + a[++l] = f(p); + } util::array<L> ls = sort_by_increasing_attributes(a, l_max); -// { -// std::cout << "ls:" << std::endl; -// for (unsigned i = 1; i <= l_max; ++i) -// std::cout << ls[i] << "(" << a[ls[i]] << ") "; -// std::cout << std::endl -// << std::endl; -// } + { + std::cout << "ls:" << std::endl; + for (unsigned i = 1; i <= l_max; ++i) + std::cout << ls[i] << "(" << a[ls[i]] << ") "; + std::cout << std::endl + << std::endl; + } // -> pseudo-tree - compute_pseudo_tree(w, g, ls, a, e_to_l1_l2); - + compute_pseudo_tree(w_ext, g, ls, a, e_to_l1_l2); } Property changes on: theo/esiee/laurent/ismm09/topo_wst.cc ___________________________________________________________________ Added: svn:mergeinfo Index: theo/esiee/laurent/ismm09/main.cc --- theo/esiee/laurent/ismm09/main.cc (revision 3287) +++ theo/esiee/laurent/ismm09/main.cc (working copy) @@ -47,9 +47,6 @@ mln_VAR(g, cplx2d::f_to_g(f) ); debug::println("g:", g); - typedef mln_value_(g_t) T; // <--- Type of edge values. - typedef mln_psite_(g_t) E; // <--- Type of edges. - // w: watershed labeling on edges. @@ -109,5 +106,4 @@ // -> pseudo-tree compute_pseudo_tree(w, g, ls, a, e_to_l1_l2); - }

1 0

r3287: Handle fastest version of functor
by Fabien Freling 05 Feb '09

05 Feb '09

URL: https://svn.lrde.epita.fr/svn/oln/trunk/milena/sandbox ChangeLog: 2009-02-05 Fabien Freling <freling(a)lrde.epita.fr> Handle fastest version of functor. * fabien/labeling.hh: . * fabien/regional_maxima.hh: Fastest version of functor --- labeling.hh | 44 ++++++++++++++-------------- regional_maxima.hh | 81 ++++++++++++++++++++--------------------------------- 2 files changed, 54 insertions(+), 71 deletions(-) Index: trunk/milena/sandbox/fabien/regional_maxima.hh =================================================================== --- trunk/milena/sandbox/fabien/regional_maxima.hh (revision 3286) +++ trunk/milena/sandbox/fabien/regional_maxima.hh (revision 3287) @@ -69,74 +69,55 @@ // Generic functor. - template <typename I_, typename N_, typename L_> + template <typename I> struct regional_maxima_functor { - typedef mln_psite(I_) P; + typedef mln_psite(I) P; // requirements from mln::canvas::labeling: - typedef I_ I; - typedef N_ N; - typedef L_ L; - typedef p_array S; - const I& input; - const N& nbh; - S s; + + // Generic implementation void init() { data::fill(attr, true); } bool handles(const P&) const { return true; } - bool labels(const P& p) const { return attr(p); } - bool equiv(const P& n, const P& p) const { return input(n) == - input(p); } - void do_no_union(const P& n, const P& p) { mln_invariant(input(n) > - input(p)); - attr(p) = false; } + bool labels(const P& p) const { return attr.element(p); } + bool equiv(const P& n, const P& p) const { return input.element(n) == + input.element(p); } + void do_no_union(const P& n, const P& p) { mln_invariant(input.element(n) > + input.element(p)); + attr.element(p) = false; } void init_attr(const P&) {} - void merge_attr(const P& r, const P& p) { attr(p) = attr(p) && - attr(r); } + void merge_attr(const P& r, const P& p) { attr.element(p) = attr.element(p) && + attr.element(r); } + + // Fastest implementation + + void init_() { data::fill(attr, true); } + bool handles_(unsigned p) const { return true; } + bool labels_(unsigned p) const { return attr.element(p); } + bool equiv_(unsigned n, unsigned p) const { return input.element(n) == + input.element(p); } + void do_no_union_(unsigned n, unsigned p) { mln_invariant(input.element(n) > + input.element(p)); + attr.element(p) = false; } + void init_attr_(const P&) {} + void merge_attr_(unsigned r, unsigned p) { attr.element(p) = attr.element(p) && + attr.element(r); } // end of requirements mln_ch_value(I, bool) attr; regional_maxima_functor(const I_& input, const N_& nbh) - : input(input), - nbh(nbh), - s(level::sort_psites_decreasing(input)) + : input(input) { initialize(attr, input); } }; - // Generic implementation. - - namespace generic - { - - template <typename I, typename N, typename L> - mln_ch_value(I, L) - regional_maxima(const I& input, const N& nbh, - L& nlabels) - { - trace::entering("labeling::impl::generic::regional_maxima"); - - // FIXME: abort if L is not wide enough to encode the set of - // maxima. - - typedef impl::regional_maxima_functor<I,N,L> F; - F f(exact(input), exact(nbh)); - mln_ch_value(I, L) output = canvas::labeling(input, nbh, f, nlabels); - - trace::exiting("labeling::impl::generic::regional_maxima"); - return output; - } - - } // end of namespace mln::labeling::impl::generic - - } // end of namespace mln::labeling::impl @@ -146,7 +127,7 @@ template <typename I, typename N, typename L> mln_ch_value(I, L) regional_maxima(const Image& input_, const Neighborhood<N>& nbh_, - L& nlabels) + bool increasing, L& nlabels) { trace::entering("labeling::regional_maxima"); @@ -154,8 +135,10 @@ const N& nbh = exact(nbh_); mln_precondition(input.is_valid()); - // Calls the only (generic) impl. - mln_ch_value(I, L) output = impl::generic::regional_maxima(input, nbh, nlabels); + typedef impl::regional_maxima_functor F; + F f(exact(input)); + mln_ch_value(I, L) output = canvas::labeling_sorted(input, nbh, increasing, + f, nlabels); trace::exiting("labeling::regional_maxima"); return output; Index: trunk/milena/sandbox/fabien/labeling.hh =================================================================== --- trunk/milena/sandbox/fabien/labeling.hh (revision 3286) +++ trunk/milena/sandbox/fabien/labeling.hh (revision 3287) @@ -101,10 +101,10 @@ return parent(x) = find_root(parent, parent(x)); } - template <typename I, typename N, typename F, typename L> + template <typename I, typename N, typename S, typename F, typename L> mln_ch_value(I, L) labeling(const Image& input_, const Neighborhood<N>& nbh_, - F& f, L& nlabels) + S& s, F& f, L& nlabels) { trace::entering("canvas::impl::generic::labeling"); @@ -113,8 +113,6 @@ const I& input = exact(input_); const N& nbh = exact(nbh_); - typedef typename F::S S; - // Local type. typedef mln_psite(I) P; @@ -228,8 +226,6 @@ const I& input = exact(input_); const N& nbh = exact(nbh_); - typedef typename F::S S; - // Local type. typedef mln_psite(I) P; @@ -315,7 +311,7 @@ // Fastest sorted version - template <typename I, typename N, typename F, typename L> + template <typename I, typename N, typename S, typename F, typename L> mln_ch_value(I, L) labeling_fastest_sorted(const Image& input_, const Neighborhood<N>& nbh_, @@ -443,8 +439,8 @@ labeling_video(metal::false_, const Image& input, const Neighborhood<N>& nbh, F& functor, L& nlabels) { - // FIXME:s = input.domain() - return impl::generic::labeling(input, nbh, functor, nlabels); + return impl::generic::labeling(input, nbh, input.domain(), + functor, nlabels); } template <typename I, typename N, typename F, typename L> @@ -468,35 +464,37 @@ && mln_is_simple_neighborhood(N)::value }; - return impl::generic::labeling_video(metal::bool_<test>(), input, nbh, - functor, nlabels); + return impl::generic::labeling_video(metal::bool_<test>(), input, + nbh, functor, nlabels); } // Sorted - template <typename I, typename N, typename F, typename L> + template <typename I, typename N, typename S, typename F, typename L> inline mln_ch_value(I, L) labeling_sorted(metal::false_, const Image& input, const Neighborhood<N>& nbh, F& functor, L& nlabels) { - return impl::generic::labeling(input, nbh, functor, nlabels); + return impl::generic::labeling(input, nbh, s, functor, nlabels); } - template <typename I, typename N, typename F, typename L> + template <typename I, typename N, typename S, typename F, typename L> inline mln_ch_value(I, L) labeling_sorted(metal::true_, const Image& input, const Neighborhood<N>& nbh, F& functor, L& nlabels) { - return impl::labeling_fastest_sorted(input, nbh, functor, nlabels); + return impl::labeling_fastest_sorted(input, nbh, s, + functor, nlabels); } - template <typename I, typename N, typename F, typename L> + template <typename I, typename N, typename S, typename F, typename L> inline mln_ch_value(I, L) - labeling_sorted_dispatch(const Image& input, const Neighborhood<N>& nbh, + labeling_sorted_dispatch(const Image& input, + const Neighborhood<N>& nbh, F& functor, L& nlabels) { enum { @@ -505,8 +503,8 @@ && mln_is_simple_neighborhood(N)::value }; - return impl::generic::labeling_video(metal::bool_<test>(), input, nbh, - functor, nlabels); + return impl::generic::labeling_sorted(metal::bool_<test>(), input, + nbh, s, functor, nlabels); } @@ -527,7 +525,8 @@ internal::labeling_tests(input, nbh, functor, nlabels); mln_ch_value(I, L) output; - output = internal::labeling_dispatch(input, nbh, functor, nlabels); + output = internal::labeling_video_dispatch(input, nbh, + functor, nlabels); trace::exiting("canvas::labeling_video"); return output; @@ -537,14 +536,15 @@ inline mln_ch_value(I, L) labeling_sorted(const Image& input, const Neighborhood<N>& nbh, - F& functor, L& nlabels) + bool increasing, F& functor, L& nlabels) { trace::entering("canvas::labeling_sorted"); internal::labeling_tests(input, nbh, functor, nlabels); mln_ch_value(I, L) output; - output = internal::labeling_dispatch(input, nbh, functor, nlabels); + output = internal::labeling_sorted_dispatch(input, nbh, s, + functor, nlabels); trace::exiting("canvas::labeling_sorted"); return output;

1 0

3286: Clean-up Laurent's code.
by Thierry Geraud 05 Feb '09

05 Feb '09

https://svn.lrde.epita.fr/svn/oln/trunk/milena/sandbox Index: ChangeLog from Thierry Geraud <thierry.geraud(a)lrde.epita.fr> Clean-up Laurent's code. * theo/esiee/laurent/ismm09/main.cc (p1_from, p2_from, e_to_labels_t): Move... * theo/esiee/laurent/ismm09/trash.hh: ...here. * theo/esiee/laurent/ismm09/main.cc (data__paste_values, cplx2d): Move... * theo/esiee/laurent/ismm09/cplx2d.hh: ...in this new file. * theo/esiee/laurent/ismm09/main.cc (compute_pseudo_tree): Move... * theo/esiee/laurent/ismm09/pseudo_tree.hh: ...in this new file. * theo/esiee/laurent/ismm09/main.cc (include): Dispatch... * theo/esiee/laurent/ismm09/util.hh, * theo/esiee/laurent/ismm09/cplx2d.hh, * theo/esiee/laurent/ismm09/pseudo_tree.hh: ...in those files. * theo/color/change_attributes.hh (extinct_rec__, extinct_attributes__): New. color/change_attributes.hh | 62 +++ esiee/laurent/ismm09/cplx2d.hh | 148 +++++++ esiee/laurent/ismm09/main.cc | 671 +----------------------------------- esiee/laurent/ismm09/pseudo_tree.hh | 449 ++++++++++++++++++++++++ esiee/laurent/ismm09/trash.hh | 44 ++ esiee/laurent/ismm09/util.hh | 10 6 files changed, 745 insertions(+), 639 deletions(-) Index: theo/esiee/laurent/ismm09/trash.hh --- theo/esiee/laurent/ismm09/trash.hh (revision 3285) +++ theo/esiee/laurent/ismm09/trash.hh (working copy) @@ -36,6 +36,50 @@ } + inline + point2d p1_from_e(const point2d& e) + { + return e + (is_row_odd(e) ? up : left); + } + + inline + point2d p2_from_e(const point2d& e) + { + return e + (is_row_odd(e) ? down : right); + } + + + + struct e_to_labels_t + { + template <typename W, typename L> + inline + void + operator()(const W& w, const point2d& e, L& l1, L& l2) const + { + mln_precondition(w(e) == 0); + l1 = 0; + l2 = 0; + mln_niter(dbl_neighb2d) n(e2e(), e); + for_all(n) + if (w.has(n) && w(n) != 0) + { + if (l1 == 0) // First label to be stored. + l1 = w(n); + else + if (w(n) != l1 && l2 == 0) // Second label to be stored. + l2 = w(n); + else + mln_invariant(w(n) == l1 || w(n) == l2); + } + mln_invariant(l1 != 0 && l2 != 0); + if (l1 > l2) + std::swap(l1, l2); + mln_postcondition(l2 >= l1); + } + }; + + } // end of namespace mln Index: theo/esiee/laurent/ismm09/main.cc --- theo/esiee/laurent/ismm09/main.cc (revision 3285) +++ theo/esiee/laurent/ismm09/main.cc (working copy) @@ -1,620 +1,20 @@ #include <mln/core/var.hh> -#include <mln/core/image/image2d.hh> -#include <mln/core/alias/neighb2d.hh> -#include <mln/make/double_neighb2d.hh> - -#include <mln/core/image/image_if.hh> -#include <mln/core/routine/extend.hh> - #include <mln/value/label_16.hh> #include <mln/value/int_u8.hh> #include <mln/io/pgm/load.hh> #include <mln/io/pgm/save.hh> #include <mln/debug/println.hh> -#include <mln/data/fill.hh> -#include <mln/data/paste.hh> -#include <mln/labeling/compute.hh> -#include <mln/level/sort_psites.hh> - -#include <mln/core/site_set/p_queue.hh> -#include <mln/core/site_set/p_priority.hh> - -#include <mln/morpho/gradient.hh> #include <mln/morpho/meyer_wst.hh> -#include <mln/morpho/tree/data.hh> -#include <mln/morpho/tree/compute_attribute_image.hh> - +#include <mln/labeling/compute.hh> #include <mln/accu/count.hh> +#include "pseudo_tree.hh" +#include "cplx2d.hh" -namespace mln -{ - - - - template <typename I, typename J> - void data__paste_values(const Image& input_, Image<J>& output_) - { - const I& input = exact(input_); - J& output = exact(output_); - - mln_fwd_piter(I) pi(input.domain()); - mln_fwd_piter(J) po(output.domain()); - for_all_2(pi, po) - output(po) = input(pi); - } - - - - namespace cplx2d - { - - // Neighborhoods. - - typedef neighb< win::multiple<window2d, bool(*)(const point2d&)> > dbl_neighb2d; - - inline - bool is_row_odd(const point2d& p) - { - return p.row() % 2; - } - - // Edge to (the couple of) pixels. - const dbl_neighb2d& e2p() - { - static bool e2p_h[] = { 0, 1, 0, - 0, 0, 0, - 0, 1, 0 }; - static bool e2p_v[] = { 0, 0, 0, - 1, 0, 1, - 0, 0, 0 }; - static dbl_neighb2d nbh = make::double_neighb2d(is_row_odd, e2p_h, e2p_v); - return nbh; - } - - - // Edge to neighboring edges. - const dbl_neighb2d& e2e() - { - static bool e2e_h[] = { 0, 0, 1, 0, 0, - 0, 1, 0, 1, 0, - 0, 0, 0, 0, 0, - 0, 1, 0, 1, 0, - 0, 0, 1, 0, 0 }; - static bool e2e_v[] = { 0, 0, 0, 0, 0, - 0, 1, 0, 1, 0, - 1, 0, 0, 0, 1, - 0, 1, 0, 1, 0, - 0, 0, 0, 0, 0 }; - static dbl_neighb2d nbh = make::double_neighb2d(is_row_odd, e2e_h, e2e_v); - return nbh; - } - - - // Predicates. - - typedef fun::C<bool (*)(const mln::point2d&)> predicate_t; - - inline - bool is_pixel(const point2d& p) - { - // Original pixels. - return p.row() % 2 == 0 && p.col() % 2 == 0; - } - - inline - bool is_edge(const point2d& p) - { - // Edges between pixels. - return p.row() % 2 + p.col() % 2 == 1; - } - - inline - bool is_point(const point2d& p) - { - // Points in-between pixels. - return p.row() % 2 && p.col() % 2; - } - - - - image_if< image2d<value::int_u8>, predicate_t > - f_to_g(const image2d<value::int_u8>& f) - { - - image2d<value::int_u8> f_(2 * f.nrows() - 1, 2 * f.ncols() - 1); - data::fill(f_, 0); // Useless but for display! - - data__paste_values(f, (f_ | is_pixel).rw()); - - mln_VAR(g, f_ | is_edge); - data::paste(morpho::gradient(extend(g, f_), - e2p().win()), - g); - - return g; - } - - - template <typename W> - image2d<mln_value(W)> - extend_w_edges_to_all_faces(W& w) - { - mln_VAR(w_ext, w.unmorph_()); - - // edges (1D-faces) -> pixels (2D-faces) - data::paste(morpho::dilation(extend(w_ext | is_pixel, - pw::value(w_ext)), - c4().win()), - w_ext); - - // edges (1D-faces) -> points (0D-faces) - data::paste(morpho::erosion(extend(w_ext | is_point, - pw::value(w_ext)), - c4().win()), - w_ext); - - return w_ext; - } - - - inline - point2d p1_from_e(const point2d& e) - { - return e + (is_row_odd(e) ? up : left); - } - - inline - point2d p2_from_e(const point2d& e) - { - return e + (is_row_odd(e) ? down : right); - } - - - // Function-Object "e -> (l1, l2)". - - struct e_to_labels_t - { - template <typename W, typename L> - inline - void - operator()(const W& w, const point2d& e, L& l1, L& l2) const - { - mln_precondition(w(e) == 0); - l1 = 0; - l2 = 0; - mln_niter(dbl_neighb2d) n(e2e(), e); - for_all(n) - if (w.has(n) && w(n) != 0) - { - if (l1 == 0) // First label to be stored. - l1 = w(n); - else - if (w(n) != l1 && l2 == 0) // Second label to be stored. - l2 = w(n); - else - mln_invariant(w(n) == l1 || w(n) == l2); - } - mln_invariant(l1 != 0 && l2 != 0); - if (l1 > l2) - std::swap(l1, l2); - mln_postcondition(l2 >= l1); - } - }; - - - } // end of namespace mln::cplx2d - - - - template <typename A, typename L> - util::array<L> - sort_by_increasing_attributes(const util::array<A>& a, L l_max) - { - typedef std::pair<A,L> pair_t; - std::vector<pair_t> v; - v.reserve(l_max.next()); - - v.push_back(pair_t(mln_min(A), 0)); // First elt, even after sorting. - for (L l = 1; l <= l_max; ++l) - v.push_back(pair_t(a[l], l)); - - std::sort(v.begin(), v.end()); - - util::array<L> ls(l_max.next()); - for (unsigned i = 1; i <= l_max; ++i) - ls[i] = v[i].second; - - return ls; - } - - - - // Find-Root for a region labeled with 'l'. - - template <typename L> - inline - L find_root_l(util::array<L>& lpar, L l) - { - if (lpar[l] == l) - return l; - else - return lpar[l] = find_root_l(lpar, lpar[l]); - } - - - - template <typename I> - inline - mln_psite(I) - find_root_e(I& z_epar, mln_psite(I) e) - { - if (z_epar(e) == e) - return e; - else - return z_epar(e) = find_root_e(z_epar, z_epar(e)); - } - - - - // Test emptiness of the queue of a set of regions. - - template <typename Qs, typename L> - bool test_q_emptiness(const Qs& qs, L l, util::array<L>& lpar) - { - L l_ = l; - while (lpar[l_] != l_) - { - if (! qs[l_].is_empty()) - return false; - l_ = lpar[l_]; - } - return true; - } - - - // Get smallest edge. - - template <typename Q_, - typename W, typename L, typename F, - typename E> - void - get_smallest_edge(Q_& q_, // in-out - L l, const W& w, util::array<L>& lpar, const F& e_to_labels, // in - E& e) // out - { - typedef mln_element(Q_) Q; // q_ 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(q_, l, lpar)); - - L lr = find_root_l(lpar, l); - Q& q = q_[lr]; - - while (! q.is_empty()) - { - e = q.pop_front(); - - L l1, l2; - e_to_labels(w, e, // input - l1, l2); // output - - mln_invariant(l1 != l2); - - L l1r = find_root_l(lpar, l1), - l2r = find_root_l(lpar, l2); - - mln_invariant(l1r == lr || l2r == lr); - - if (l1r == l2r) - // 'e' is an internal edge => forget it. - continue; - - // Otherwise 'e' has been found. - return; - } - - mln_invariant(0); // We should not be here! - } - - - - - // ################################################################### - // ################################################################### - // ################################################################### - // ################################################################### - // ################################################################### - - - - template <typename W, - typename G, - typename L, typename A, - typename F> - void - compute_pseudo_tree(const W& w, - const G& g, - const util::array<L>& ls, - const A& a, - const F& e_to_labels) - { - - typedef mln_value(G) T; // <--- Type of edge values. - typedef mln_psite(G) E; // <--- Type of edges. - - const L l_max = ls.nelements() - 1; - - mln_VAR( g_line, g | (pw::value(w) == 0) ); - - - // Edges -> Priority queue. - - typedef p_priority< T, p_queue<E> > Q; - util::array<Q> q(l_max.next()); - - { - L l1, l2; - - mln_piter(g_line_t) e(g_line.domain()); - for_all(e) - { - mln_invariant(w(e) == 0); - e_to_labels(w, e, // input - l1, l2); // output - q[l1].push(mln_max(T) - g(e), e); - q[l2].push(mln_max(T) - g(e), e); - } - } - - - - // Initialization. - // ----------------------------------- - - - - // Information "label l -> edge e". - - E null = E(0,0); // Impossible value. FIXME: lack of genericity. - - - util::array<E> edge(l_max.next()); - for (L l = 0; l <= l_max; ++l) - edge[l] = null; - - - util::array<L> lpar(l_max.next()); - for (L l = 0; l <= l_max; ++l) - lpar[l] = l; // Make-Set. - - - // 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 named "lpar". - // - // In the following "lpar[l]" is shortly denoted by lr, meaning - // l-root. - - - // 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. - - - - - 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); - mln_piter(g_line_t) e(g_line.domain()); - for_all(e) - { - // Make-Set. - epar(e) = e; - z_epar(e) = e; - } - debug::println("epar (init):", epar); // epar(e) == e so we depict the edges! - } - - - - // GO GO GO !!! - - - for (unsigned i = 1; i < l_max; ++i) - { - L l = ls[i]; // Region label. - E e; - get_smallest_edge(q, // in-out - l, w, lpar, e_to_labels, // in - e); // out - // FIXME: the call below is performed above!!! - L l1, l2; - e_to_labels(w, e, l1, l2); - - L l1r = find_root_l(lpar, l1), - l2r = find_root_l(lpar, l2); - - // Consistency tests. - { - if (i > 1) - { - L former_l = ls[i-1]; - mln_invariant(a[l] >= a[former_l]); - } - mln_invariant(epar(e) == e); // 'e' has not been processed yet. - mln_invariant(l1 != l2); // It is a valid edge, i.e., between 2 different regions... - mln_invariant(l1r != l2r); // ...that are not already merged. - - L lr = find_root_l(lpar, l); - mln_invariant(lr == l // Either l is not deja-vu - || ((lr == l1r && lr != l2r) || // or l belongs to l1r xor l2r. - (lr == l2r && lr != l1r))); - } - - - - // aa(e) = a[l]; // FIXME: Re-activate. - - - - /* - std::cout << "l = " << l - << " e = " << e - << " (l1, l2) = (" << l1 << ", " << l2 << ") => " - << " merging R" << l1r << " and R" << l2r - << std::endl; - */ - - - // Merging both regions. - { - if (l2r < l1r) - std::swap(l1r, l2r); - mln_invariant(l2r > l1r); - lpar[l1r] = l2r; - - /* - std::cout << "q[l1r] = " << q[l1r] << std::endl; - std::cout << "q[l2r] = " << q[l2r] << std::endl; - */ - - - q[l2r].insert(q[l1r]); - q[l1r].clear(); - - - /* - std::cout << "q[l2r] = " << q[l2r] << std::endl - << std::endl; - */ - - - /* - // Displaying lpar. - { - std::cout << "lpar = "; - for (unsigned i = 1; i <= l_max; ++i) - { - L l = v[i].second; - std::cout << l << "->" << lpar[l] << " "; - } - std::cout << std::endl; - } - */ - } - - E e1 = edge[l1], - e2 = edge[l2]; - - if (e1 == null && e2 == null) - { - // New edge-component (singleton) - // Put differently: new edge-node! - edge[l1] = e; - edge[l2] = e; - // after: - // e - // / \ - // l1 l2 - } - else if (e1 != null && e2 != null) - { - // Two trees shall merge. - E e1r = find_root_e(z_epar, e1), - e2r = find_root_e(z_epar, e2); - mln_invariant(e1r != e2r); // Otherwise, there's a bug! - // before: - // e1r e2r - // |... |... - // e1 e2 - // / \ / \ - // l1 . l2 . - epar(e1r) = e; z_epar(e1r) = e; - epar(e2r) = e; z_epar(e2r) = e; - // after: - // e - // / \ - // e1r e2r - // |... |... - // e1 e2 - // / \ / \ - // l1 . l2 . - } - else if (e1 != null && e2 == null) - { - E e1r = find_root_e(z_epar, e1); - // before: - // e1r - // |... - // e1 null - // / \ / - // l1 . l2 - epar(e1r) = e; z_epar(e1r) = e; - edge[l2] = e; - // after: - // e - // / \ - // e1r l2 - // |... - // e1 - // / \ - // l1 . - } - else - { - mln_invariant(e1 == null && e2 != null); - E e2r = find_root_e(z_epar, e2); - epar(e2r) = e; z_epar(e2r) = e; - edge[l1] = e; - } - - } // end of "for every region with increasing attribute" - - - { - // Display edge tree. - - mln_ch_value(g_line_t, bool) deja_vu; - initialize(deja_vu, g_line); - data::fill(deja_vu, false); - - std::cout << "edge tree: " << std::endl; - for (L l = 1; l <= l_max; ++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; - } - } - - - - } - - - -} // end of namespace mln - void usage(char* argv[]) @@ -642,8 +42,6 @@ io::pgm::load(f, argv[1]); - cplx2d::e_to_labels_t e_to_labels; - // g: weights on edges. mln_VAR(g, cplx2d::f_to_g(f) ); @@ -653,30 +51,37 @@ typedef mln_psite_(g_t) E; // <--- Type of edges. - mln_VAR(nbh_g, cplx2d::e2e()); // Neighborhood between edges. - - // w: watershed labeling on edges. typedef label_16 L; // <--- Type of labels. L l_max; - mln_VAR( w, morpho::meyer_wst(g, nbh_g, l_max) ); + mln_VAR( w, morpho::meyer_wst(g, cplx2d::e2e(), l_max) ); debug::println("w:", w); - mln_VAR( w_line, pw::value(w) == pw::cst(0) ); - mln_VAR( g_line, g | w_line ); + mln_VAR( is_w_line, pw::value(w) == pw::cst(0) ); + mln_VAR( g_line, g | is_w_line ); debug::println("g | line:", g_line); - - { - /* - // debug::println("w | line:", w | w_line); mln_VAR(w_ext, cplx2d::extend_w_edges_to_all_faces(w)); debug::println("w_ext:", w_ext); - // debug::println("w_ext | line:", w_ext | (pw::value(w_ext) == pw::cst(0))); - */ - } + + + // e -> (l1, l2) + mln_VAR( e_to_l1_l2, function_e_to_l1_l2(w_ext, cplx2d::e2p()) ); + +// { +// // Test adjacency "e -> (l1, l2)". +// L l1, l2; +// mln_piter_(g_t) e(g.domain()); +// for_all(e) +// if (w(e) == 0) +// { +// e_to_l1_l2(e, l1, l2); +// std::cout << e << "=" << l1 << '|' << l2 << " "; +// } +// std::cout << std::endl; +// } @@ -691,30 +96,18 @@ util::array<L> ls = sort_by_increasing_attributes(a, l_max); - - { - std::cout << "ls:" << std::endl; - for (unsigned i = 1; i <= l_max; ++i) - std::cout << ls[i] << "(" << a[ls[i]] << ") "; - std::cout << std::endl - << std::endl; - } - - - // { - // // Test adjacency "e -> (l1, l2)". - // L l1, l2; - // mln_piter_(g_t) e(g.domain()); - // for_all(e) - // if (w(e) == 0) // { - // e_to_labels(w, e, l1, l2); - // std::cout << e << ':' << l1 << ',' << l2 << std::endl; - // } +// std::cout << "ls:" << std::endl; +// for (unsigned i = 1; i <= l_max; ++i) +// std::cout << ls[i] << "(" << a[ls[i]] << ") "; +// std::cout << std::endl +// << std::endl; // } - compute_pseudo_tree(w, g, ls, a, - e_to_labels); + + // -> pseudo-tree + + compute_pseudo_tree(w, g, ls, a, e_to_l1_l2); } Index: theo/esiee/laurent/ismm09/cplx2d.hh --- theo/esiee/laurent/ismm09/cplx2d.hh (revision 0) +++ theo/esiee/laurent/ismm09/cplx2d.hh (revision 0) @@ -0,0 +1,148 @@ + +#include <mln/core/image/image2d.hh> +#include <mln/core/alias/neighb2d.hh> +#include <mln/make/double_neighb2d.hh> + +#include <mln/pw/all.hh> +#include <mln/core/image/image_if.hh> +#include <mln/core/routine/extend.hh> + +#include <mln/data/paste.hh> + +#include <mln/morpho/gradient.hh> + + +namespace mln +{ + + + + template <typename I, typename J> + void data__paste_values(const Image& input_, Image<J>& output_) + { + const I& input = exact(input_); + J& output = exact(output_); + + mln_fwd_piter(I) pi(input.domain()); + mln_fwd_piter(J) po(output.domain()); + for_all_2(pi, po) + output(po) = input(pi); + } + + + + namespace cplx2d + { + + // Neighborhoods. + + typedef neighb< win::multiple<window2d, bool(*)(const point2d&)> > dbl_neighb2d; + + inline + bool is_row_odd(const point2d& p) + { + return p.row() % 2; + } + + // Edge to (the couple of) pixels. + const dbl_neighb2d& e2p() + { + static bool e2p_h[] = { 0, 1, 0, + 0, 0, 0, + 0, 1, 0 }; + static bool e2p_v[] = { 0, 0, 0, + 1, 0, 1, + 0, 0, 0 }; + static dbl_neighb2d nbh = make::double_neighb2d(is_row_odd, e2p_h, e2p_v); + return nbh; + } + + + // Edge to neighboring edges. + const dbl_neighb2d& e2e() + { + static bool e2e_h[] = { 0, 0, 1, 0, 0, + 0, 1, 0, 1, 0, + 0, 0, 0, 0, 0, + 0, 1, 0, 1, 0, + 0, 0, 1, 0, 0 }; + static bool e2e_v[] = { 0, 0, 0, 0, 0, + 0, 1, 0, 1, 0, + 1, 0, 0, 0, 1, + 0, 1, 0, 1, 0, + 0, 0, 0, 0, 0 }; + static dbl_neighb2d nbh = make::double_neighb2d(is_row_odd, e2e_h, e2e_v); + return nbh; + } + + + // Predicates. + + typedef fun::C<bool (*)(const mln::point2d&)> predicate_t; + + inline + bool is_pixel(const point2d& p) + { + // Original pixels. + return p.row() % 2 == 0 && p.col() % 2 == 0; + } + + inline + bool is_edge(const point2d& p) + { + // Edges between pixels. + return p.row() % 2 + p.col() % 2 == 1; + } + + inline + bool is_point(const point2d& p) + { + // Points in-between pixels. + return p.row() % 2 && p.col() % 2; + } + + + + image_if< image2d<value::int_u8>, predicate_t > + f_to_g(const image2d<value::int_u8>& f) + { + image2d<value::int_u8> f_(2 * f.nrows() - 1, 2 * f.ncols() - 1); + data::fill(f_, 0); // Useless but for display! + + data__paste_values(f, (f_ | is_pixel).rw()); + + mln_VAR(g, f_ | is_edge); + data::paste(morpho::gradient(extend(g, f_), + e2p().win()), + g); + + return g; + } + + + template <typename W> + image2d<mln_value(W)> + extend_w_edges_to_all_faces(W& w) + { + mln_VAR(w_ext, w.unmorph_()); + + // edges (1D-faces) -> pixels (2D-faces) + data::paste(morpho::dilation(extend(w_ext | is_pixel, + pw::value(w_ext)), + c4().win()), + w_ext); + + // edges (1D-faces) -> points (0D-faces) + data::paste(morpho::erosion(extend(w_ext | is_point, + pw::value(w_ext)), + c4().win()), + w_ext); + + return w_ext; + } + + + + } // end of namespace mln::cplx2d + +} // end of namespace mln Index: theo/esiee/laurent/ismm09/util.hh --- theo/esiee/laurent/ismm09/util.hh (revision 3285) +++ theo/esiee/laurent/ismm09/util.hh (working copy) @@ -1,4 +1,14 @@ +#include <mln/core/concept/function.hh> +#include <mln/core/site_set/p_array.hh> + +#include <mln/level/sort_psites.hh> + +#include <mln/morpho/tree/data.hh> +#include <mln/morpho/tree/compute_attribute_image.hh> + + + namespace mln { Index: theo/esiee/laurent/ismm09/pseudo_tree.hh --- theo/esiee/laurent/ismm09/pseudo_tree.hh (revision 0) +++ theo/esiee/laurent/ismm09/pseudo_tree.hh (revision 0) @@ -0,0 +1,449 @@ + +#include <mln/core/concept/image.hh> +#include <mln/core/site_set/p_queue.hh> +#include <mln/core/site_set/p_priority.hh> +#include <mln/data/fill.hh> +#include <mln/util/array.hh> + + + +namespace mln +{ + + + // Function-Object "e -> (l1, l2)". + + template <typename W, typename N> + struct e_to_l1_l2_t + { + const W& w; + const N& nbh; + typedef mln_value(W) L; + + e_to_l1_l2_t(const W& w, const N& nbh) + : w(w), nbh(nbh) + { + } + + template <typename E> + void operator()(const E& e, // in + L& l1, // out + L& l2 // out + ) const + { + mln_niter(N) n(nbh, e); + n.start(); + l1 = w(n); + n.next(); + l2 = w(n); + mln_invariant(l2 != l1); + if (l1 > l2) + std::swap(l1, l2); + } + }; + + template <typename W, typename N> + e_to_l1_l2_t<W, N> + function_e_to_l1_l2(const W& w, const N& nbh) + { + e_to_l1_l2_t<W, N> tmp(w, nbh); + return tmp; + } + + + + template <typename A, typename L> + util::array<L> + sort_by_increasing_attributes(const util::array<A>& a, L l_max) + { + typedef std::pair<A,L> pair_t; + std::vector<pair_t> v; + v.reserve(l_max.next()); + + v.push_back(pair_t(mln_min(A), 0)); // First elt, even after sorting. + for (L l = 1; l <= l_max; ++l) + v.push_back(pair_t(a[l], l)); + + std::sort(v.begin(), v.end()); + + util::array<L> ls(l_max.next()); + for (unsigned i = 1; i <= l_max; ++i) + ls[i] = v[i].second; + + return ls; + } + + + + // Find-Root for a region labeled with 'l'. + + template <typename L> + inline + L find_root_l(util::array<L>& lpar, L l) + { + if (lpar[l] == l) + return l; + else + return lpar[l] = find_root_l(lpar, lpar[l]); + } + + + + template <typename I> + inline + mln_psite(I) + find_root_e(I& z_epar, mln_psite(I) e) + { + if (z_epar(e) == e) + return e; + else + return z_epar(e) = find_root_e(z_epar, z_epar(e)); + } + + + + // Test emptiness of the queue of a set of regions. + + template <typename Qs, typename L> + bool test_q_emptiness(const Qs& qs, L l, util::array<L>& lpar) + { + L l_ = l; + while (lpar[l_] != l_) + { + if (! qs[l_].is_empty()) + return false; + l_ = lpar[l_]; + } + return true; + } + + + // Get smallest edge. + + template <typename Q_, + typename W, typename L, typename F, + typename E> + void + get_smallest_edge(Q_& q_, // in-out + L l, const W& w, util::array<L>& lpar, const F& e_to_l1_l2, // in + E& e, L& l1, L& l2) // out + { + typedef mln_element(Q_) Q; // q_ 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(q_, l, lpar)); + + L lr = find_root_l(lpar, l); + Q& q = q_[lr]; + + while (! q.is_empty()) + { + e = q.pop_front(); + + e_to_l1_l2(e, l1, l2); + + mln_invariant(l1 != l2); + + L l1r = find_root_l(lpar, l1), + l2r = find_root_l(lpar, l2); + + mln_invariant(l1r == lr || l2r == lr); + + if (l1r == l2r) + // 'e' is an internal edge => forget it. + continue; + + // Otherwise 'e' has been found. + return; + } + + mln_invariant(0); // We should not be here! + } + + + + + // ################################################################### + // ################################################################### + // ################################################################### + // ################################################################### + // ################################################################### + + + + template <typename W, + typename G, + typename L, typename A, + typename F> + void + compute_pseudo_tree(const W& w, + const G& g, + const util::array<L>& ls, + const A& a, + const F& e_to_l1_l2) + { + + typedef mln_value(G) T; // <--- Type of edge values. + typedef mln_psite(G) E; // <--- Type of edges. + + const L l_max = ls.nelements() - 1; + + mln_VAR( g_line, g | (pw::value(w) == 0) ); + + + // Edges -> Priority queue. + + typedef p_priority< T, p_queue<E> > Q; + util::array<Q> q(l_max.next()); + + { + L l1, l2; + + mln_piter(g_line_t) e(g_line.domain()); + for_all(e) + { + mln_invariant(w(e) == 0); + e_to_l1_l2(e, l1, l2); + q[l1].push(mln_max(T) - g(e), e); + q[l2].push(mln_max(T) - g(e), e); + } + } + + + + // Initialization. + // ----------------------------------- + + + + // Information "label l -> edge e". + + E null = E(0,0); // Impossible value. FIXME: lack of genericity. + + + util::array<E> edge(l_max.next()); + for (L l = 0; l <= l_max; ++l) + edge[l] = null; + + + util::array<L> lpar(l_max.next()); + for (L l = 0; l <= l_max; ++l) + lpar[l] = l; // Make-Set. + + + // 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 named "lpar". + // + // In the following "lpar[l]" is shortly denoted by lr, meaning + // l-root. + + + // 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. + + + + + 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); + mln_piter(g_line_t) e(g_line.domain()); + for_all(e) + { + // Make-Set. + epar(e) = e; + z_epar(e) = e; + } + debug::println("epar (init):", epar); // epar(e) == e so we depict the edges! + } + + + + // GO GO GO !!! + + + for (unsigned i = 1; i < l_max; ++i) + { + L l = ls[i]; // Region label. + L l1, l2; + E e; + get_smallest_edge(q, // in-out + l, w, lpar, e_to_l1_l2, // in + e, l1, l2); // out + + L l1r = find_root_l(lpar, l1), + l2r = find_root_l(lpar, l2); + + // Consistency tests. + { + if (i > 1) + { + L former_l = ls[i-1]; + mln_invariant(a[l] >= a[former_l]); + } + mln_invariant(epar(e) == e); // 'e' has not been processed yet. + mln_invariant(l1 != l2); // It is a valid edge, i.e., between 2 different regions... + mln_invariant(l1r != l2r); // ...that are not already merged. + + L lr = find_root_l(lpar, l); + mln_invariant(lr == l // Either l is not deja-vu + || ((lr == l1r && lr != l2r) || // or l belongs to l1r xor l2r. + (lr == l2r && lr != l1r))); + } + + + + // aa(e) = a[l]; // FIXME: Re-activate. + + + + /* + std::cout << "l = " << l + << " e = " << e + << " (l1, l2) = (" << l1 << ", " << l2 << ") => " + << " merging R" << l1r << " and R" << l2r + << std::endl; + */ + + + // Merging both regions. + { + if (l2r < l1r) + std::swap(l1r, l2r); + mln_invariant(l2r > l1r); + lpar[l1r] = l2r; + + /* + std::cout << "q[l1r] = " << q[l1r] << std::endl; + std::cout << "q[l2r] = " << q[l2r] << std::endl; + */ + + + q[l2r].insert(q[l1r]); + q[l1r].clear(); + + + /* + std::cout << "q[l2r] = " << q[l2r] << std::endl + << std::endl; + */ + + + /* + // Displaying lpar. + { + std::cout << "lpar = "; + for (unsigned i = 1; i <= l_max; ++i) + { + L l = v[i].second; + std::cout << l << "->" << lpar[l] << " "; + } + std::cout << std::endl; + } + */ + } + + E e1 = edge[l1], + e2 = edge[l2]; + + if (e1 == null && e2 == null) + { + // New edge-component (singleton) + // Put differently: new edge-node! + edge[l1] = e; + edge[l2] = e; + // after: + // e + // / \ + // l1 l2 + } + else if (e1 != null && e2 != null) + { + // Two trees shall merge. + E e1r = find_root_e(z_epar, e1), + e2r = find_root_e(z_epar, e2); + mln_invariant(e1r != e2r); // Otherwise, there's a bug! + // before: + // e1r e2r + // |... |... + // e1 e2 + // / \ / \ + // l1 . l2 . + epar(e1r) = e; z_epar(e1r) = e; + epar(e2r) = e; z_epar(e2r) = e; + // after: + // e + // / \ + // e1r e2r + // |... |... + // e1 e2 + // / \ / \ + // l1 . l2 . + } + else if (e1 != null && e2 == null) + { + E e1r = find_root_e(z_epar, e1); + // before: + // e1r + // |... + // e1 null + // / \ / + // l1 . l2 + epar(e1r) = e; z_epar(e1r) = e; + edge[l2] = e; + // after: + // e + // / \ + // e1r l2 + // |... + // e1 + // / \ + // l1 . + } + else + { + mln_invariant(e1 == null && e2 != null); + E e2r = find_root_e(z_epar, e2); + epar(e2r) = e; z_epar(e2r) = e; + edge[l1] = e; + } + + } // end of "for every region with increasing attribute" + + + { + // Display edge tree. + + mln_ch_value(g_line_t, bool) deja_vu; + initialize(deja_vu, g_line); + data::fill(deja_vu, false); + + std::cout << "edge tree: " << std::endl; + for (L l = 1; l <= l_max; ++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; + } + } + + } + +} // end of namespace mln + Index: theo/color/change_attributes.hh --- theo/color/change_attributes.hh (revision 3285) +++ theo/color/change_attributes.hh (working copy) @@ -77,6 +77,9 @@ const T* t; }; + + // Vachier's version. + template <typename T, typename I, typename M> inline mln_value(I) @@ -92,9 +95,30 @@ return a(p) = extinct_rec(t, a, mark, t.parent(p)); } + + // Modified version. + + template <typename T, typename I, typename M> + inline + mln_value(I) + extinct_rec__(const T& t, // tree + const I& a, // original attribute image + I& ea, // extincted attribute image + M& mark, + const mln_psite(I)& p) + { + mln_invariant(mark(p) == false); + mark(p) = true; + if (t.parent(p) == p || mark(t.parent(p)) == true) // Stop. + return a(t.parent(p)); // The parent attribute! + return ea(p) = extinct_rec__(t, a, ea, mark, t.parent(p)); + } + + } // end of internal + // Vachier's version. template <typename T, typename I> void @@ -128,6 +152,44 @@ + // Modified version. + + template <typename T, typename I> + void + extinct_attributes__(const T& t, // Tree. + I& a) // Attribute image. + { + typedef mln_site(I) P; + typedef mln_value(I) A; // Type of attributes. + + mln_ch_value(I, bool) mark; + initialize(mark, a); + data::fill(mark, false); + + mln_concrete(I) ea = duplicate(a); + + internal::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_fwd_piter(S) p(s); + for_all(p) + { + if (mark(p) == true) + continue; + internal::extinct_rec__(t, a, ea, mark, p); + } + + data::fill(a, ea); + + // debug::println(mark | t.nodes()); + } + + + // Move down. // ----------

1 0

r3285: Implement fastest versions of canvas::labeling
by Fabien Freling 04 Feb '09

04 Feb '09

URL: https://svn.lrde.epita.fr/svn/oln/trunk/milena/sandbox ChangeLog: 2009-02-04 Fabien Freling <freling(a)lrde.epita.fr> Implement fastest versions of canvas::labeling. * fabien/regional_maxima.hh: New. --- labeling.hh | 199 +++++++++++++++++++++++++++++++++++++++++++++++++---- regional_maxima.hh | 171 +++++++++++++++++++++++++++++++++++++++++++++ 2 files changed, 357 insertions(+), 13 deletions(-) Index: trunk/milena/sandbox/fabien/regional_maxima.hh =================================================================== --- trunk/milena/sandbox/fabien/regional_maxima.hh (revision 0) +++ trunk/milena/sandbox/fabien/regional_maxima.hh (revision 3285) @@ -0,0 +1,171 @@ +// 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 +// 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_LABELING_REGIONAL_MAXIMA_HH +# define MLN_LABELING_REGIONAL_MAXIMA_HH + +/// \file mln/labeling/regional_maxima.hh +/// +/// Connected component labeling of the regional maxima of an image. + +# include <mln/core/concept/image.hh> +# include <mln/core/concept/neighborhood.hh> +# include <mln/canvas/labeling.hh> +# include <mln/data/fill.hh> +# include <mln/level/sort_psites.hh> + + +namespace mln +{ + + namespace labeling + { + + /*! Connected component labeling of the regional maxima of an + * image. + * + * \param[in] input The input image. + * \param[in] nbh The connexity of the regional maxima. + * \param[out] nlabels The number of labeled regions. + * \return The label image. + * + */ + template <typename I, typename N, typename L> + mln_ch_value(I, L) + regional_maxima(const Image& input, const Neighborhood<N>& nbh, + L& nlabels); + + + +# ifndef MLN_INCLUDE_ONLY + + namespace impl + { + + // Generic functor. + + template <typename I_, typename N_, typename L_> + struct regional_maxima_functor + { + typedef mln_psite(I_) P; + + // requirements from mln::canvas::labeling: + + typedef I_ I; + typedef N_ N; + typedef L_ L; + typedef p_array S; + + const I& input; + const N& nbh; + S s; + + void init() { data::fill(attr, true); } + bool handles(const P&) const { return true; } + bool labels(const P& p) const { return attr(p); } + bool equiv(const P& n, const P& p) const { return input(n) == + input(p); } + void do_no_union(const P& n, const P& p) { mln_invariant(input(n) > + input(p)); + attr(p) = false; } + void init_attr(const P&) {} + void merge_attr(const P& r, const P& p) { attr(p) = attr(p) && + attr(r); } + + // end of requirements + + mln_ch_value(I, bool) attr; + + regional_maxima_functor(const I_& input, const N_& nbh) + : input(input), + nbh(nbh), + s(level::sort_psites_decreasing(input)) + { + initialize(attr, input); + } + }; + + + // Generic implementation. + + namespace generic + { + + template <typename I, typename N, typename L> + mln_ch_value(I, L) + regional_maxima(const I& input, const N& nbh, + L& nlabels) + { + trace::entering("labeling::impl::generic::regional_maxima"); + + // FIXME: abort if L is not wide enough to encode the set of + // maxima. + + typedef impl::regional_maxima_functor<I,N,L> F; + F f(exact(input), exact(nbh)); + mln_ch_value(I, L) output = canvas::labeling(input, nbh, f, nlabels); + + trace::exiting("labeling::impl::generic::regional_maxima"); + return output; + } + + } // end of namespace mln::labeling::impl::generic + + + } // end of namespace mln::labeling::impl + + + + // Facade. + + template <typename I, typename N, typename L> + mln_ch_value(I, L) + regional_maxima(const Image& input_, const Neighborhood<N>& nbh_, + L& nlabels) + { + trace::entering("labeling::regional_maxima"); + + const I& input = exact(input_); + const N& nbh = exact(nbh_); + mln_precondition(input.is_valid()); + + // Calls the only (generic) impl. + mln_ch_value(I, L) output = impl::generic::regional_maxima(input, nbh, nlabels); + + trace::exiting("labeling::regional_maxima"); + return output; + } + +# endif // ! MLN_INCLUDE_ONLY + + } // end of namespace mln::labeling + +} // end of namespace mln + + +#endif // ! MLN_LABELING_REGIONAL_MAXIMA_HH Index: trunk/milena/sandbox/fabien/labeling.hh =================================================================== --- trunk/milena/sandbox/fabien/labeling.hh (revision 3284) +++ trunk/milena/sandbox/fabien/labeling.hh (revision 3285) @@ -201,7 +201,7 @@ - // Fastest version + // Fastest video version template <typename I> static inline @@ -214,9 +214,11 @@ return parent.element(x) = find_root(parent, parent.element(x)); } + // FIXME: Use the same functer for the generic and the fastest versions + template <typename I, typename N, typename F, typename L> mln_ch_value(I, L) - labeling_fastest(const Image& input_, const Neighborhood<N>& nbh_, + labeling_fastest_video(const Image& input_, const Neighborhood<N>& nbh_, F& f, L& nlabels) { trace::entering("canvas::impl::labeling"); @@ -269,7 +271,7 @@ if (f.equiv(n, p)) { // Do-Union. - P r = find_root(parent, n); + unsigned r = find_root_fastest(parent, n); if (r != p) { parent.element(r) = p; @@ -278,8 +280,7 @@ } else f.do_no_union(n, p); - } - deja_vu(p) = true; + (p) = true; } } @@ -310,6 +311,121 @@ return output; } + + + // Fastest sorted version + + template <typename I, typename N, typename F, typename L> + mln_ch_value(I, L) + labeling_fastest_sorted(const Image& input_, + const Neighborhood<N>& nbh_, + S& s, F& f, L& nlabels) + { + trace::entering("canvas::impl::labeling"); + + // FIXME: Test?! + + const I& input = exact(input_); + const N& nbh = exact(nbh_); + + typedef typename F::S S; + + // Local type. + typedef mln_psite(I) P; + + // Auxiliary data. + mln_ch_value(I, bool) deja_vu; + mln_ch_value(I, P) parent; + + // Output. + mln_ch_value(I, L) output; + bool status; + + // Initialization. + { + initialize(deja_vu, input); + mln::data::fill(deja_vu, false); + + initialize(parent, input); + + initialize(output, input); + mln::data::fill(output, L(literal::zero)); + nlabels = 0; + + f.init(); // Client initialization. + } + + util::array<int> dp = offsers_wrt(input, nbh); + const unsigned n_nbhs = dp.nelements(); + + const unsigned n_points = s.elements(); + + // First Pass. + { + + for (unsigned i = 0; i < n_points; ++i) + { + unsigned p = s[i]; + if (!f.handles(p)) + continue; + + // Make-Set. + parent.element(p) = p; + f.init_attr(p); + + for (unsigned j = 0; j < n_nbhs; ++j) + { + unsigned n = p + dp[j]; + if (!deja_vu[n]) + continue; + + if (f.equiv(n, p)) + { + // Do-Union. + unsigned r = find_root_fastest(parent, n); + if (input.element(r) != input.element(p)) + { + parent.element(r) = p; + f.merge_attr(r, p); + } + } + else + f.do_no_union(n, p); + } + deja_vu.element(p) = true; + + } + + // Second Pass. + { + for (int i = n_points - 1; i >=0; --i) + { + unsigned p = s[i]; + if (!f.handles(p)) + continue; + + if (parent.element(p) == p) // if p is root + { + if (f.labels(p)) + { + if (nlabels == mln_max(L)) + { + status = false; + return output; + } + output.element(p) = ++nlabels; + } + } + else + output.element(p) = output(parent.element(p)); + } + status = true; + } + + trace::exiting("canvas::impl::labeling"); + return output; + } + } // end of namespace mln::canvas::impl @@ -319,10 +435,50 @@ namespace internal { + // Video + + template <typename I, typename N, typename F, typename L> + inline + mln_ch_value(I, L) + labeling_video(metal::false_, const Image& input, + const Neighborhood<N>& nbh, F& functor, L& nlabels) + { + // FIXME:s = input.domain() + return impl::generic::labeling(input, nbh, functor, nlabels); + } + + template <typename I, typename N, typename F, typename L> + inline + mln_ch_value(I, L) + labeling_video(metal::true_, const Image& input, + const Neighborhood<N>& nbh, F& functor, L& nlabels) + { + return impl::labeling_fastest_video(input, nbh, functor, nlabels); + } + template <typename I, typename N, typename F, typename L> inline mln_ch_value(I, L) - labeling(metal::false_, const Image& input, + labeling_video_dispatch(const Image& input, const Neighborhood<N>& nbh, + F& functor, L& nlabels) + { + enum { + test = mlc_equal(mln_trait_image_speed(I), + trait::image::speed::fastest)::value + && + mln_is_simple_neighborhood(N)::value + }; + return impl::generic::labeling_video(metal::bool_<test>(), input, nbh, + functor, nlabels); + } + + + // Sorted + + template <typename I, typename N, typename F, typename L> + inline + mln_ch_value(I, L) + labeling_sorted(metal::false_, const Image& input, const Neighborhood<N>& nbh, F& functor, L& nlabels) { return impl::generic::labeling(input, nbh, functor, nlabels); @@ -331,16 +487,16 @@ template <typename I, typename N, typename F, typename L> inline mln_ch_value(I, L) - labeling(metal::true_, const Image& input, + labeling_sorted(metal::true_, const Image& input, const Neighborhood<N>& nbh, F& functor, L& nlabels) { - return impl::labeling_fastest(input, nbh, functor, nlabels); + return impl::labeling_fastest_sorted(input, nbh, functor, nlabels); } template <typename I, typename N, typename F, typename L> inline mln_ch_value(I, L) - labeling_dispatch(const Image& input, const Neighborhood<N>& nbh, + labeling_sorted_dispatch(const Image& input, const Neighborhood<N>& nbh, F& functor, L& nlabels) { enum { @@ -349,10 +505,11 @@ && mln_is_simple_neighborhood(N)::value }; - return impl::generic::labeling(metal::bool_<test>(), input, nbh, + return impl::generic::labeling_video(metal::bool_<test>(), input, nbh, functor, nlabels); } + } // end of namespace mln::canvas::internal @@ -362,20 +519,36 @@ template <typename I, typename N, typename F, typename L> inline mln_ch_value(I, L) - labeling(const Image& input, const Neighborhood<N>& nbh, + labeling_video(const Image& input, const Neighborhood<N>& nbh, F& functor, L& nlabels) { - trace::entering("canvas::labeling"); + trace::entering("canvas::labeling_video"); internal::labeling_tests(input, nbh, functor, nlabels); mln_ch_value(I, L) output; output = internal::labeling_dispatch(input, nbh, functor, nlabels); - trace::exiting("canvas::labeling"); + trace::exiting("canvas::labeling_video"); return output; } + template <typename I, typename N, typename F, typename L> + inline + mln_ch_value(I, L) + labeling_sorted(const Image& input, const Neighborhood<N>& nbh, + F& functor, L& nlabels) + { + trace::entering("canvas::labeling_sorted"); + + internal::labeling_tests(input, nbh, functor, nlabels); + + mln_ch_value(I, L) output; + output = internal::labeling_dispatch(input, nbh, functor, nlabels); + + trace::exiting("canvas::labeling_sorted"); + return output; + } # endif // ! MLN_INCLUDE_ONLY

1 0

r3284: Add card accu and some traits
by Edwin Carlinet 04 Feb '09

04 Feb '09

URL: https://svn.lrde.epita.fr/svn/oln/trunk/milena/sandbox ChangeLog: 2009-02-04 Edwin Carlinet <carlinet(a)lrde.epita.fr> Add card accu and some traits. * accu.cc: Add traits and fix bugs. * accu_trait.hh: New. --- accu.cc | 155 ++++++++++++++++++++++++++++++++++++++++++++++------------ accu_trait.hh | 51 +++++++++++++++++++ 2 files changed, 175 insertions(+), 31 deletions(-) Index: trunk/milena/sandbox/edwin/accu.cc =================================================================== --- trunk/milena/sandbox/edwin/accu.cc (revision 3283) +++ trunk/milena/sandbox/edwin/accu.cc (revision 3284) @@ -1,91 +1,184 @@ -template <typename E> -struct Accumulator : public object<E> -{ - typedef mln_vtypes(E, take_with) take_with; +# include <mln/metal/equal.hh> +# include <mln/metal/if.hh> +# include <mln/metal/is_const.hh> +# include <mln/core/concept/image.hh> +# include <mln/accu/all.hh> +# include <mln/util/pix.hh> +# include <mln/make/pix.hh> +# include "accu_trait.hh" -}; +using namespace mln; + +namespace mln +{ + + namespace morpho + { namespace accu { template <typename T> - struct card : public Accumulator< card<T> > + struct card : public mln::accu::internal::base< unsigned, card<T> > { - void take(const T& elt) { ++c_; } + typedef T argument; + void init () { c_ = 0; }; + void take (const card<T>& elt) { ++c_; }; + void take (const T& elt) { ++c_; }; + void take (const mln_value(T)& v) { ++c_; }; + unsigned to_result() const { return c_; }; + operator unsigned () const { return c_; }; + bool is_valid () const { return true; }; + card () { init(); }; + + private: unsigned c_; }; -} + } // accu + } // morpho namespace impl { - template <typename I, template<typename E> class A> + template <typename I, typename A> void algebraic(const Image& input, - const Accumulator< A<point2d> >& acc) + Accumulator<A>& acc) { const I& ima = exact(input); + A& accu = exact (acc); mln_piter(I) p(ima.domain()); for_all(p) - acc.take(p); + accu.take(p); } // fast implementation - template <typename I, template<typename E> class A> + template <typename I, typename A> void - leveling (const Image& input, - const Accumulator< A< pix > >& acc) + leveling_fast (const Image& input, + Accumulator<A>& acc) { const I& ima = exact(input); + A& accu = exact (acc); mln_pixter(const I) px(ima); for_all(px) - acc.take(px); + accu.take (px.val ()); } // generic implementation - template <typename I, template<typename E> class A> + template <typename I, typename A> void leveling (const Image& input, - const Accumulator< A<point2d> >& acc) + Accumulator<A>& acc) { const I& ima = exact(input); + A& accu = exact (acc); mln_piter(I) p(ima.domain()); for_all(p) - acc.take(p); + accu.take (mln::make::pix(ima, p)); } - } // impl namespace internal { template <typename I, typename A> void - leveling_dispatch(const Image& input, - const Accumulator<A>& acc) + leveling_dispatch(metal::false_, + const Image& input, + Accumulator<A>& acc) { + impl::leveling(input, acc); + } - //Si when_pix = use_only - // - - algebraic_dispatch(mlc_equal(mln_trait_image_speed(I), - trait::image::speed::fastest)::value, - input, - acc); + template <typename I, typename A> + inline + void + leveling_dispatch(metal::true_, + const Image& input, + Accumulator<A>& acc) + { + impl::leveling_fast(input, acc); } + template <typename I, typename A> + inline + void + leveling_dispatch(const Image& input, + Accumulator<A>& acc) + { + enum { + test = (mlc_equal(mln_trait_image_speed(I), + trait::image::speed::fastest)::value && + mlc_equal(mln_trait_accu_when_pix(A), + trait::accu::when_pix::use_v)::value) + }; + leveling_dispatch(metal::bool_<test>(), input, acc); } + } // internal + +} //mln + // Facade. -template <typename M, typename I> +template <typename I, typename A> void -algebraic(const Image& input, const Meta_Accumulator<M>& acc) // FIXME: on préfère Meta_Accumulator ! +leveling(const Image& input, + Accumulator<A>& acc) { - internal::algebraic_dispatch(input, acc); + mln::internal::leveling_dispatch(input, acc); } + + +# include <mln/accu/all.hh> +# include <mln/core/image/image2d.hh> + +# include <mln/debug/iota.hh> +# include <mln/debug/println.hh> +# include <mln/core/var.hh> +# include <mln/util/timer.hh> +int main() +{ + using namespace mln; + typedef image2d<int> I; + + I ima(1000, 1000); + mln::morpho::accu::card<util::pix > acc; + + float elapsed; + mln::util::timer chrono; + + debug::iota(ima); + std::cout << "50 mean of a 1000x1000 image2d<int>" << std::endl; + + acc.init(); + chrono.start(); + for (int i = 0; i < 50; i++) + leveling(ima, acc); + elapsed = chrono.stop(); + + std::cout << "(auto) " << elapsed << "s : " << acc.to_result() << std::endl; + + acc.init(); + chrono.start(); + for (int i = 0; i < 50; i++) + mln::impl::leveling(ima, acc); + elapsed = chrono.stop(); + + std::cout << "(generic) " << elapsed << "s : " << acc.to_result() << std::endl; + + acc.init(); + chrono.start(); + for (int i = 0; i < 50; i++) + mln::impl::leveling_fast(ima, acc); + elapsed = chrono.stop(); + + std::cout << "(fast) " << elapsed << "s : " << acc.to_result() << std::endl; +} + Index: trunk/milena/sandbox/edwin/accu_trait.hh =================================================================== --- trunk/milena/sandbox/edwin/accu_trait.hh (revision 0) +++ trunk/milena/sandbox/edwin/accu_trait.hh (revision 3284) @@ -0,0 +1,51 @@ +#ifndef ACCU_TRAIT_HH_ +# define ACCU_TRAIT_HH_ + +# include <mln/trait/undef.hh> + + +# define mln_trait_accu_when_pix(A) typename trait::accu::accu_traits<A>::when_pix + + +namespace mln +{ + namespace morpho { + namespace accu + { + template <typename T> + struct card; + } + } + + namespace trait + { + namespace accu + { + + struct when_pix + { + struct use_v {}; + struct use_p {}; + struct use_pix {}; + struct use_whatever {}; + struct not_ok {}; + }; + + template <typename A> + struct accu_traits + { + typedef undef when_pix; + }; + + template <> + template <typename T> + struct accu_traits< mln::morpho::accu::card <T> > + { + typedef when_pix::use_v when_pix; + }; + } //accu + + }//trait + +} //mln +#endif /* !ACCU_TRAIT_HH_ */

1 0

3283: Clean up ChangeLogs.
by Roland Levillain 04 Feb '09

04 Feb '09

--- ChangeLog | 12 +-- milena/ChangeLog | 242 +++++++++++++++++++++++----------------------- milena/sandbox/ChangeLog | 67 +++++++------ 3 files changed, 159 insertions(+), 162 deletions(-) diff --git a/ChangeLog b/ChangeLog index 90a0af3..d4c4716 100644 --- a/ChangeLog +++ b/ChangeLog @@ -22,16 +22,6 @@ * m4/.gitignore: New. * build-aux/.gitignore: Adjust. -2009-02-04 Frederic Bour <bour(a)lrde.epita.fr> - - [sandbox][bour] Backup of accuprops.cc. - * milena/sandbox/fred/accuprops2.cc: New. - -2009-02-04 Frederic Bour <bour(a)lrde.epita.fr> - - [sandbox][fred] Mean morphological accumulator working with. - * milena/sandbox/fred/accuprops.cc: New. - 2009-02-03 Roland Levillain <roland(a)lrde.epita.fr> Typo: s/splitted/split/. @@ -170,7 +160,7 @@ * configure.ac: Update. 2008-12-16 Guillaume Lazzara <z(a)lrde.epita.fr> - + Make use of milena/generate_dist_headers.sh. * bootstrap: update here. diff --git a/milena/ChangeLog b/milena/ChangeLog index 2818ee1..1599b96 100644 --- a/milena/ChangeLog +++ b/milena/ChangeLog @@ -114,7 +114,7 @@ * tests/unit_test/mln_io_raw_load.cc, * tests/unit_test/mln_io_raw_save.cc, * tests/io/raw/raw.cc, - * tests/io/raw/Makefile.am, + * tests/io/raw/Makefile.am, * tests/io/raw/pbm.cc, * mln/io/raw/all.hh, * mln/io/raw/load.hh, @@ -156,7 +156,7 @@ * mln/trace/exiting.hh, * mln/transform/internal/closest_point_functor.hh: add missing includes. - + * mln/debug/slices_2d.hh: remove an unused variable. 2009-02-03 Guillaume Lazzara <z(a)lrde.epita.fr> @@ -186,7 +186,7 @@ * doc/tutorial/tutorial.tex: include the right files. 2009-02-02 Guillaume Lazzara <z(a)lrde.epita.fr> - + Introduce subject_point_impl. * mln/core/point.hh: All Point proxies will inherit from that class @@ -207,7 +207,7 @@ * mln/core/internal/graph_psite_base.hh: remove a useless forward declaration. - + * mln/io/raw/all.hh: Rewrite, completely wrong... * mln/accu/compute.hh, @@ -256,7 +256,7 @@ * mln/transform/internal/closest_point_functor.hh: New. Construct an image of closest point. - + * tests/unit_test/Makefile.am, * tests/unit_test/mln_transform_internal_closest_point_functor.cc: add new unit test. @@ -341,7 +341,7 @@ 2009-02-02 Thierry Geraud <thierry.geraud(a)lrde.epita.fr> Activate fastest version of algebraic union-find. - + * mln/morpho/closing_attribute.hh (closing_attribute_dispatch): Activate for fastest images. * mln/canvas/morpho/algebraic_union_find.hh: Likewise. @@ -579,7 +579,7 @@ * Makefile.am: fix list of distributed images. * doc/tutorial/Makefile.am: include new mk files. - + * doc/tutorial/generate_dist_files.sh: new script to generate the following list of files. @@ -623,7 +623,7 @@ * doc/tutorial/figures/tuto4_genericity_and_algorithms-7.pgm, * doc/tutorial/figures/tuto4_genericity_and_algorithms-8.ppm, * doc/tutorial/figures/tuto4_genericity_and_algorithms-9.ppm: update. - + * doc/tutorial/figures/tuto4_genericity_and_algorithms-10.ppm: delete, not needed anymore. @@ -738,7 +738,7 @@ 2009-01-21 Thierry GERAUD <thierry.geraud(a)lrde.epita.fr> Add some images. - + * img/space_debris.pgm: Remove; unused. * img/small.ppm: Fix file format. * img/fly.ppm, @@ -759,7 +759,7 @@ * headers.mk: remove to_rgb.hh from distribution. * mln/convert/all.hh: remove to_rgb.hh. - + * mln/convert/from_to.hxx: add more predeclarations. * mln/convert/impl/from_value_to_value.hh: if no value concept is @@ -881,7 +881,7 @@ Add implementation of Fibonacci heap. * headers.mk: add a new header to distribution. - + * mln/util/fibonacci_heap.hh: new file. The implementation. * tests/unit_test/Makefile.am, @@ -1038,7 +1038,7 @@ 2009-01-09 Guillaume Lazzara <z(a)lrde.epita.fr> Remove a useless test in level/median. - + * tests/level/Makefile.am, * tests/level/median_.cc: remove this test. It is already tested by level/median/approx/median.cc. @@ -1055,9 +1055,9 @@ * mln/core/dpsites_piter.hh, * mln/core/neighb.hh, * mln/win/multiple_size.hh: remove empty implementation of center_at_(). - + * mln/core/image/complex_neighborhood_piter.hh: add a new line. - + * mln/core/internal/site_relative_iterator_base.hh: add default implementation of center_at_(). @@ -1130,7 +1130,7 @@ * mln/fun/meta/blue.hh, * mln/fun/meta/green.hh: Add new meta functions to use with fun_image. - + * headers.mk: Add new headers to distribution. * tests/unit_test/Makefile.am, @@ -1416,8 +1416,8 @@ * doc/tutorial/outputs/ima2d-3.txt, * doc/tutorial/samples/ima2d-3.cc, * doc/tutorial/tutorial.tex: use opt::at(ima,...) instead of ima.at() - - * doc/tutorial/outputs/ima2d-3-output.txt: remove useless file. + + * doc/tutorial/outputs/ima2d-3-output.txt: remove useless file. 2008-12-31 Guillaume Lazzara <z(a)lrde.epita.fr> @@ -1628,7 +1628,7 @@ * mln/core/image/complex_image.hh: update comments. * mln/core/image/complex_neighborhood_piter.hh: avoid a warning. - + * mln/core/internal/site_relative_iterator_base.hh: call center_at_() earlier. @@ -1735,7 +1735,7 @@ Various small fixes. - * mln/accu/count_adjacent_vertices.hh: add missing is_valid(). + * mln/accu/count_adjacent_vertices.hh: add missing is_valid(). * mln/canvas/labeling.hh: cleanup. @@ -1782,7 +1782,7 @@ * tests/unit_test/Makefile.am, * tests/unit_test/mln_geom_resize.cc: update unit tests. - * mln/accu/count_adjacent_vertices.hh: add missing is_valid(). + * mln/accu/count_adjacent_vertices.hh: add missing is_valid(). 2008-12-31 Guillaume Lazzara <z(a)lrde.epita.fr> @@ -1853,7 +1853,7 @@ 2008-12-30 Guillaume Lazzara <z(a)lrde.epita.fr> Add a call to center_at_() in - site_relative_iterator_base::center_at() (ticket #176). + site_relative_iterator_base::center_at() (ticket #176). * mln/core/dpsites_piter.hh, * mln/core/image/complex_neighborhood_piter.hh, @@ -1865,7 +1865,7 @@ 2008-12-30 Guillaume Lazzara <z(a)lrde.epita.fr> - Fix from_to dispatch. + Fix from_to dispatch. * mln/convert/from_to.hh: dispatch functions where not called at all. @@ -2590,7 +2590,7 @@ * trash/display_color_pretty.cc, * doc/benchmark/canvas.cc, * doc/examples/erosion.cc: fix doxygen warnings. - + * doc/tutorial/samples/Makefile.am: do not install sample programs. * mln/fun/l2l/relabel.hh: fix wrong guards. @@ -2878,7 +2878,7 @@ Add missing concept for bijective functions. - * mln/core/concept/function.hh: + * mln/core/concept/function.hh: Add Function_v2w2v and Function_v2w_w2v. 2008-12-15 Alexandre Abraham <abraham(a)lrde.epita.fr> @@ -2911,10 +2911,10 @@ since they are not update with the new property names. * milena/mln/core/image/bgraph_psite.hh: fix wrong include. - - * milena/mln/core/image/fi_adaptor.hh, - * milena/mln/core/image/graph_image.hh, - * milena/mln/core/image/line_graph_image.hh: move to... + + * milena/mln/core/image/fi_adaptor.hh, + * milena/mln/core/image/graph_image.hh, + * milena/mln/core/image/line_graph_image.hh: move to... * milena/trash/fi_adaptor.hh, * milena/trash/graph_image.hh, @@ -2989,7 +2989,7 @@ * tests/core/image/graph_image.cc, * tests/core/image/line_graph_image.cc: use id() instead of - element().id(). + element().id(). 2008-12-12 Guillaume Lazzara <z(a)lrde.epita.fr> @@ -3054,7 +3054,7 @@ * mln/core/image/hexa_piter.hh: update attribute name. * mln/core/internal/piter_adaptor.hh: update change_target(); - + * mln/debug/iota.spe.hh: cleanup. * mln/debug/println.spe.hh: remove wrong ifndef. @@ -3070,7 +3070,7 @@ * mln/morpho/line_gradient.hh: update with the new graph structure. * mln/subsampling/gaussian_subsampling.hh: add missing coma. - + * mln/topo/face_iter.hh, * mln/topo/internal/complex_set_iterator_base.hh, * mln/topo/internal/complex_relative_iterator_base.hh, @@ -4190,7 +4190,7 @@ Fix various tests. * headers.mk: Update distributed headers list. - + * mln/make/image.hh, * mln/make/image2d.hh, * mln/fun/v2v/convert.hh, @@ -4247,7 +4247,7 @@ * doc/tutorial/samples/fill-subimage-cfun.cc * doc/tutorial/samples/labeling-compute.cc: rename label8 to label_8 and label16 to label_16. - + * doc/tutorial/tutorial.tex: fix wrong include. * mln/core/site_set/p_graph_piter.hh: add a conversion toward the @@ -4272,7 +4272,7 @@ 2008-12-08 Guillaume Lazzara <z(a)lrde.epita.fr> - Fix build system. + Fix build system. * Makefile.am: Split and move data related to headers distribution... * headers.mk: here. @@ -4351,7 +4351,7 @@ Update unit tests. * milena/tests/unit_test/Makefile.am: Update. - + * milena/tests/unit_test/mln_convert_to_tiles.cc, * milena/tests/unit_test/mln_core_image_graph_neighborhood_piter.cc, * milena/tests/unit_test/mln_core_image_line_graph_elt_piter.cc, @@ -4656,7 +4656,7 @@ * mln/util/line_graph.hh: add graph(). - * doc/tutorial/outputs/labeling-compute-1, + * doc/tutorial/outputs/labeling-compute-1, * doc/tutorial/outputs/labeling-compute.txt: update reference output files for tutorial. @@ -4854,7 +4854,7 @@ * mln/util/internal/graph_vertex_impl.hh: rename as... * mln/util/internal/vertex_impl.hh: ... this. - + * tests/morpho/Makefile.am: disable more tests. * tests/unit_test/build_unit_test.sh: do not include mln/core/doc @@ -4933,7 +4933,7 @@ * tests/core/image/Makefile.am, * tests/convert/Makefile.am, * tests/Makefile.am: comment known non working tests. - + * tests/core/image/flat_image.cc, * tests/convert/to_p_array.cc: write test. @@ -4955,7 +4955,7 @@ * doc/examples/tuto_bis.cc (fill, gradient, dilation): Remove dedicated code; instead use - library routines. Their proper arg is nbh.win(). + library routines. Their proper arg is nbh.win(). (ima): Ensure there is no outer border. (include): Update. * mln/core/image/extended.hh: Upgrade doc style. @@ -5021,7 +5021,7 @@ * img/fly.pgm: New. 2008-11-27 Guillaume Lazzara <z(a)lrde.epita.fr> - + Add new examples. * doc/examples/erosion.cc: Apply a vertical and a horizontal erosion @@ -5040,7 +5040,7 @@ * mln/debug/colorize.hh: Pass the color type as arguments instead of passing the return type as template parameter. - + * mln/debug/draw_graph.hh: add a new signature. * mln/literal/colors.hh, @@ -5077,12 +5077,12 @@ Upgrade tutorial. * Doxyfile.in: add new path to included files. - + * tutorial/Makefile.am, * Makefile.am: update target dependencies. - + * doc.mk: add new global variables. - + * tutorial/figures/fill-subdomain-1.pbm, * tutorial/figures/fill-subdomain-2.ppm, * tutorial/figures/fill-subdomain-3.ppm, @@ -5258,7 +5258,7 @@ (zfind_root): Move from impl::generic to internal. 2008-11-27 Guillaume Lazzara <z(a)lrde.epita.fr> - + Add a missing Makefile.am * milena/tests/morpho/elementary/Makefile.am: new. @@ -5332,7 +5332,7 @@ * doc/tutorial/samples/ima2d-decl-2-blobs.cc, * doc/tutorial/samples/labeling-compute-full.cc: Use label8 instead of int_u8. - + * doc/tutorial/samples/graph-data-full.cc: Add new example. 2008-11-25 Thierry Geraud <thierry.geraud(a)lrde.epita.fr> @@ -5434,7 +5434,7 @@ * mln/morpho/tree/compute_parent.hh: New; revamp of... * sandbox/geraud/max_tree_nnodes.cc: ...this file. * tests/morpho/tree: New directory. - * tests/morpho/tree/compute_parent.cc: + * tests/morpho/tree/compute_parent.cc: * tests/morpho/tree/Makefile.am: New. * tests/morpho/Makefile.am: Update. * mln/canvas/morpho/all.hh: Upgrade doc style. @@ -5565,7 +5565,7 @@ 2008-11-20 Guillaume Lazzara <z(a)lrde.epita.fr> - + Add labeling::relabel. * mln/core/concept/function.hh: add Function_l2b and Function_l2l. @@ -5654,7 +5654,7 @@ * mln/fun/i2v/array.hh: add two from_to; - from_to(util::array, fun::i2v::array) - from_to(std::vector, fun::i2v::array) - + * mln/convert/to.hh, * doc/examples/labeling_algo.cc: cleanup. @@ -6074,7 +6074,7 @@ into... (erosion_dispatch_line): ...this new overloaded routine. (erosion_dispatch_diagonal): Remove check on kind::logic cause it - also works on this case. + also works on this case. To be consistent: * mln/accu/snake_2d.hh: Rename as... @@ -6149,7 +6149,7 @@ * tests/core/image/graph_image.cc, * tests/core/image/line_graph_image.cc: fix tests. - * mln/make/all.hh + * mln/make/all.hh * mln/make/essential.hh: uncomment inclusion of voronoi.hh. 2008-11-14 Thierry Geraud <thierry.geraud(a)lrde.epita.fr> @@ -6321,7 +6321,7 @@ * mln/arith/revert.spe.hh, * mln/arith/times.hh, * mln/arith/times.spe.hh: Cleanup comments. - + * mln/morpho/hit_or_miss.hh, * mln/display/save.hh, * mln/canvas/browsing/backdiagonal2d.hh, @@ -6373,7 +6373,7 @@ * tests/border/get.cc, * tests/border/resize_image_if.cc: Fix tests. - + 2008-11-13 Thierry Geraud <thierry.geraud(a)lrde.epita.fr> Specialize accu tranform for fastest images. @@ -7005,14 +7005,14 @@ Update use of level::transform(). - * mln/binarization/binarization.hh, - * mln/level/abs.hh, - * mln/level/saturate.hh, - * mln/level/to_enc.hh, - * tests/io/pgm/pgm16.cc, - * tests/io/pgm/pgm19.cc, - * tests/io/pgm/pgm27.cc, - * tests/value/float01.cc: Update here. + * mln/binarization/binarization.hh, + * mln/level/abs.hh, + * mln/level/saturate.hh, + * mln/level/to_enc.hh, + * tests/io/pgm/pgm16.cc, + * tests/io/pgm/pgm19.cc, + * tests/io/pgm/pgm27.cc, + * tests/value/float01.cc: Update here. * mln/level/transform.hh: Remove useless prototype. @@ -8107,7 +8107,7 @@ * doc/tutorial/samples/mln_var-3.tex: New. Add sample code. - * doc/tutorial/tutorial.tex: rewrite graph section. + * doc/tutorial/tutorial.tex: rewrite graph section. 2008-11-04 Guillaume Lazzara <z(a)lrde.epita.fr> @@ -8116,7 +8116,7 @@ * mln/debug/graph.hh: update in order to support p_vertices. * tests/core/image/graph_image.cc: Add assertions. - + * tests/core/site_set/p_vertices.cc: use fun::i2v::array. 2008-11-04 Guillaume Lazzara <z(a)lrde.epita.fr> @@ -8160,7 +8160,7 @@ * milena/tests/core/other/box_runstart_piter.cc: remove make:: prefix. - + * milena/tests/core/other/point_set_compatibility.cc: update test according last changes in p_vertices. @@ -8356,7 +8356,7 @@ * mln/io/ppm/save.hh: Update copyright. * mln/io/txt/save.hh: save an image<char> to a txt file. - + * mln/io/off/all.hh, * mln/io/txt/all.hh: new missing 'all' headers. @@ -8375,7 +8375,7 @@ * mln/logical/not.spe.hh: Write a dedicated version of not_inplace. 2008-11-03 Guillaume Lazzara <z(a)lrde.epita.fr> - + Add trace::warning. * mln/trace/warning.hh: new file. @@ -8384,7 +8384,7 @@ * mln/trace/resume.hh, * mln/trace/stop.hh: cleanup includes. - + * mln/debug/put_word.hh: use trace::warning. @@ -8873,7 +8873,7 @@ Fix return type of i2v::array::operator(). - * mln/fun/i2v/array.hh (operator() const): Return a reference instead of a copy. + * mln/fun/i2v/array.hh (operator() const): Return a reference instead of a copy. 2008-10-27 Guillaume Lazzara <z(a)lrde.epita.fr> @@ -9326,7 +9326,7 @@ Fix namespace path to update_tests(). - * mln/level/update.hh: specify full namespace path to update_tests(). + * mln/level/update.hh: specify full namespace path to update_tests(). 2008-10-22 Roland Levillain <roland(a)lrde.epita.fr> @@ -9744,11 +9744,11 @@ Add neighborhoods based on lower/higher-dimension connected n-faces. * mln/core/image/complex_neighborhoods.hh - (mln::complex_lower_dim_connected_n_face_neighborhood<D, G>): + (mln::complex_lower_dim_connected_n_face_neighborhood<D, G>): (mln::complex_higher_dim_connected_n_face_neighborhood<D, G>): New neighborhoods. Exercise them... - * tests/core/image/complex_image.cc: ...here. + * tests/core/image/complex_image.cc: ...here. 2008-10-18 Roland Levillain <roland(a)lrde.epita.fr> @@ -9856,7 +9856,7 @@ * mln/core/image/complex_neighborhoods.hh: New. Replace... * mln/core/image/complex_lower_neighborhood.hh, - * mln/core/image/complex_higher_neighborhood.hh, + * mln/core/image/complex_higher_neighborhood.hh, * mln/core/image/complex_lower_higher_neighborhood.hh: ...these files. Remove. @@ -9869,7 +9869,7 @@ * mln/core/image/complex_windows.hh: New. Replace... * mln/core/image/complex_lower_window_p.hh, - * mln/core/image/complex_higher_window_p.hh, + * mln/core/image/complex_higher_window_p.hh, * mln/core/image/complex_lower_higher_window_p.hh: ...these files. Remove. @@ -9882,7 +9882,7 @@ Factor concrete windows of complex image. * mln/core/image/complex_lower_window_p.hh, - * mln/core/image/complex_higher_window_p.hh, + * mln/core/image/complex_higher_window_p.hh, * mln/core/image/complex_lower_higher_window_p.hh: Factor using mln::internal::complex_window_p_base. @@ -9897,7 +9897,7 @@ Factor concrete neighborhoods of complex image. * mln/core/image/complex_lower_neighborhood.hh, - * mln/core/image/complex_higher_neighborhood.hh, + * mln/core/image/complex_higher_neighborhood.hh, * mln/core/image/complex_lower_higher_neighborhood.hh: Factor using mln::internal::complex_neighborhood_base. @@ -10046,10 +10046,10 @@ (mln::topo::edge(const n_face<0, D>&, const n_face<0, D>&)): New function. * mln/topo/face_data.hh - (mln::topo::internal::lower_dim_faces_data_mixin): Make + (mln::topo::internal::lower_dim_faces_data_mixin): Make mln::topo::n_face<N, D>::lower_dim_adj_faces a friend of this class. - (mln::topo::internal::higher_dim_faces_data_mixin): Make + (mln::topo::internal::higher_dim_faces_data_mixin): Make mln::topo::n_face<N, D>::higher_dim_adj_faces a friend of this class. @@ -10348,29 +10348,29 @@ Add is_valid() in the accumulator concept and move meta-accumulators in meta namespace. - - * mln/accu/count.hh, - * mln/accu/height.hh, - * mln/accu/histo.hh, - * mln/accu/max.hh, - * mln/accu/max_h.hh, - * mln/accu/mean.hh, - * mln/accu/median_alt.hh, - * mln/accu/min.hh, - * mln/accu/min_h.hh, - * mln/accu/nil.hh, - * mln/accu/p.hh, - * mln/accu/pair.hh, - * mln/accu/rank.hh, - * mln/accu/rank_bool.hh, - * mln/accu/rank_high_quant.hh, - * mln/accu/sum.hh, - * mln/accu/tuple.hh, - * mln/accu/v.hh, - * mln/accu/volume.hh: + + * mln/accu/count.hh, + * mln/accu/height.hh, + * mln/accu/histo.hh, + * mln/accu/max.hh, + * mln/accu/max_h.hh, + * mln/accu/mean.hh, + * mln/accu/median_alt.hh, + * mln/accu/min.hh, + * mln/accu/min_h.hh, + * mln/accu/nil.hh, + * mln/accu/p.hh, + * mln/accu/pair.hh, + * mln/accu/rank.hh, + * mln/accu/rank_bool.hh, + * mln/accu/rank_high_quant.hh, + * mln/accu/sum.hh, + * mln/accu/tuple.hh, + * mln/accu/v.hh, + * mln/accu/volume.hh: Add is_valid() and move meta-accumulators in meta namespace if needed. - * mln/core/concept/accumulator.hh: + * mln/core/concept/accumulator.hh: Add is_valid() static test. * tests/accu/all_accus.cc, @@ -10579,7 +10579,7 @@ * tests/timer.hh: New. Tool to bench tests. 2008-10-07 Guillaume Lazzara <z(a)lrde.epita.fr> - + Fix most of the doxygen warnings. * mln/arith/min.hh, @@ -10954,17 +10954,17 @@ Various small fixes. * mln/algebra/vec.hh: add missing header. - + * mln/core/image/obased_rle_image.hh, * mln/core/image/rle_image.hh: Use pruns. - + * mln/core/image/obased_rle_image.hh, * mln/core/image/t_image.hh: add missing init_ function. - + * mln/core/image/tr_image.hh, * tests/core/alias/point1d.cc, * tests/core/alias/point2d.cc: cleanup. - + * tests/core/image/Makefile.am: Disable known broken test such as graph related tests. @@ -11106,12 +11106,12 @@ 2008-10-03 Guillaume Lazzara <z(a)lrde.epita.fr> - Add p_edges. - - * mln/core/site_set/p_edges.hh: - The site set p_edges. + Add p_edges. + + * mln/core/site_set/p_edges.hh: + The site set p_edges. - * mln/util/internal/graph_edge_psite.hh: + * mln/util/internal/graph_edge_psite.hh: The associated psite. * tests/core/site_set/Makefile.am, @@ -11119,28 +11119,28 @@ Add a basic test. 2008-10-03 Guillaume Lazzara <z(a)lrde.epita.fr> - + Refactor graph_vertex_psite. * mln/util/internal/graph_vertex_psite.hh: Refactor this class... - * mln/util/internal/graph_psite_base.hh: - ... here. + * mln/util/internal/graph_psite_base.hh: + ... here. 2008-10-03 Guillaume Lazzara <z(a)lrde.epita.fr> - Fix util::graph<G>::is_subgraph_of(). + Fix util::graph<G>::is_subgraph_of(). - * mln/util/graph.hh: here. + * mln/util/graph.hh: here. 2008-10-03 Guillaume Lazzara <z(a)lrde.epita.fr> Add missing methods to vertex and edge. - * mln/util/internal/graph_edge.hh: - Add change_graph(). - * mln/util/internal/graph_vertex.hh: - Add invalidate(). + * mln/util/internal/graph_edge.hh: + Add change_graph(). + * mln/util/internal/graph_vertex.hh: + Add invalidate(). 2008-10-03 Guillaume Lazzara <z(a)lrde.epita.fr> @@ -11149,10 +11149,10 @@ * mln/core/site_set/p_vertices.hh: The site set p_vertices. - + * mln/util/internal/graph_vertex_psite.hh: The psite associated to p_vertices. - + * tests/core/site_set/p_vertices.cc, * tests/core/site_set/Makefile.am: Add a small test. @@ -11170,7 +11170,7 @@ * mln/util/internal/graph_vertex.hh: Remove useless const and a wrong precondition. - + 2008-10-03 Guillaume Lazzara <z(a)lrde.epita.fr> Fix missing methods in graph_base. @@ -11182,7 +11182,7 @@ Update p_graph_piter. - * mln/core/site_set/p_graph_piter.hh: + * mln/core/site_set/p_graph_piter.hh: update in order to make it work with the new graph structure. 2008-10-02 Ugo Jardonnet <ugo.jardonnet(a)lrde.epita.fr> diff --git a/milena/sandbox/ChangeLog b/milena/sandbox/ChangeLog index be9d267..b05c6f3 100644 --- a/milena/sandbox/ChangeLog +++ b/milena/sandbox/ChangeLog @@ -1,8 +1,17 @@ 2009-02-04 Fabien Freling <freling(a)lrde.epita.fr> Add my own sandbox directory to modify labeling.hh. - * .: New. - * labeling.hh: New. + * fabien/labeling.hh: New. + +2009-02-04 Frederic Bour <bour(a)lrde.epita.fr> + + Backup of accuprops.cc. + * fred/accuprops2.cc: New. + +2009-02-04 Frederic Bour <bour(a)lrde.epita.fr> + + Mean morphological accumulator working with. + * fred/accuprops.cc: New. 2009-02-03 Thierry Geraud <thierry.geraud(a)lrde.epita.fr> @@ -15,16 +24,16 @@ 2009-02-03 Edwin Carlinet <carlinet(a)lrde.epita.fr> First tries of accus with specialisation. - * accu.cc: New. - * fredwin.cc: . + * edwin/accu.cc: New. + * edwin/fredwin.cc: . 2009-02-03 Guillaume Lazzara <z(a)lrde.epita.fr> Rename io::raw as io::dump in sandbox. - * sandbox/theo/igr/irm_anat_segm.cc, - * sandbox/theo/igr/pgms2raw.cc, - * sandbox/theo/igr/raw2pgm.cc: rename here. + * theo/igr/irm_anat_segm.cc, + * theo/igr/pgms2raw.cc, + * theo/igr/raw2pgm.cc: rename here. 2009-02-03 Guillaume Lazzara <z(a)lrde.epita.fr> @@ -43,20 +52,18 @@ 2009-02-02 Edwin Carlinet <carlinet(a)lrde.epita.fr> Add dispatch functions for accumulator. - * .: New. * fredwin.cc: New. 2009-02-02 Frederic Bour <bour(a)lrde.epita.fr> - [sandbox] p2p morpher with translation, composition and flip. - * .: New. - * p2p/Makefile: New. - * p2p/compose_p2p.hh: New. - * p2p/p2p_morpher.hh: New. - * p2p/symmetry_p2p.hh: New. - * p2p/test_morph_image.cc: New. - * p2p/translate_p2p.hh: New. - * p2p: New. + p2p morpher with translation, composition and flip. + * fred/p2p/Makefile: New. + * fred/p2p/compose_p2p.hh: New. + * fred/p2p/p2p_morpher.hh: New. + * fred/p2p/symmetry_p2p.hh: New. + * fred/p2p/test_morph_image.cc: New. + * fred/p2p/translate_p2p.hh: New. + * fred/p2p: New. 2009-02-02 Thierry Geraud <thierry.geraud(a)lrde.epita.fr> @@ -211,7 +218,7 @@ 2009-01-21 Guillaume Lazzara <z(a)lrde.epita.fr> Add a new LCA implementation to Laurent's code. - + * laurent/ismm2009.cc: Use the implementation written by Alexandre Abraham for one of its previous seminar (#0821). @@ -293,7 +300,7 @@ Work on reconstruction. * garrigues/union_find/canvas/reconstruction_on_function.hh: Remove - useless escape value. + useless escape value. * garrigues/union_find/canvas/reconstruction_on_set.hh: Optimizations. * garrigues/union_find/canvas/self_dual_reconstruction.hh: . * garrigues/union_find/images/marker_to_dilate.pbm: Fix it. @@ -1791,13 +1798,13 @@ Examples : ( | == object, - = background) - - - | - | P | Here P is simple in the c4 and c8 case. - | | | + - - | + | P | Here P is simple in the c4 and c8 case. + | | | - - | - - | P | Here P is never simple. - | | | + - | - + | P | Here P is never simple. + | | | * garrigues/ocr/simple_point.cc: New. A simple test that shows all the simple points of a binary image. @@ -1961,7 +1968,7 @@ * abraham/mln/core/image/shell.hh: Fix result value. * abraham/mln/core/concept/meta_fun.hh: (mln::meta::impl) : now templated by return type - (necessary to typedef result). + (necessary to typedef result). * abraham/mln/fun/meta/red.hh: . 2008-10-27 Ugo Jardonnet <ugo.jardonnet(a)lrde.epita.fr> @@ -2085,7 +2092,7 @@ Fix an endless loop. - * scribo/demat.hh: Fix a endless loop. + * scribo/demat.hh: Fix a endless loop. 2008-10-22 Maxime van Noppen <yabo(a)lrde.epita.fr> @@ -2105,7 +2112,7 @@ Improve debug output. - * scribo/demat.hh: + * scribo/demat.hh: Use color images for debug output. Improve the way the small components are erased. @@ -2152,7 +2159,7 @@ Extract text bboxes for Scribo. * scribo/main.cc: Change usage message. - + * scribo/demat.hh: - Cleanup. - Remove too small components using level::transform. @@ -2187,7 +2194,7 @@ Get and display character bboxes. - * sandbox/scribo/demat.hh: update. + * sandbox/scribo/demat.hh: update. Does not create text bboxes yet. 2008-10-15 Guillaume Lazzara <z(a)lrde.epita.fr> -- 1.5.6.5

1 0

r3280: Add my own sandbox directory to modify labeling.hh
by Fabien Freling 04 Feb '09

04 Feb '09

URL: https://svn.lrde.epita.fr/svn/oln/trunk/milena/sandbox ChangeLog: 2009-02-04 Fabien Freling <freling(a)lrde.epita.fr> Add my own sandbox directory to modify labeling.hh. * .: New. * labeling.hh: New. --- labeling.hh | 387 ++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++ 1 file changed, 387 insertions(+) Index: trunk/milena/sandbox/fabien/labeling.hh =================================================================== --- trunk/milena/sandbox/fabien/labeling.hh (revision 0) +++ trunk/milena/sandbox/fabien/labeling.hh (revision 3280) @@ -0,0 +1,387 @@ +// 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 +// of the GNU General Public License version 2 as published by the +// Free Software Foundation. +// +// This library is distributed in the hope that it will be useful, +// but WITHOUT ANY WARRANTY; without even the implied warranty of +// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU +// General Public License for more details. +// +// You should have received a copy of the GNU General Public License +// along with this library; see the file COPYING. If not, write to +// the Free Software Foundation, 51 Franklin Street, Fifth Floor, +// Boston, MA 02111-1307, USA. +// +// As a special exception, you may use this file as part of a free +// software library without restriction. Specifically, if other files +// instantiate templates or use macros or inline functions from this +// file, or you compile this file and link it with other files to +// produce an executable, this file does not by itself cause the +// resulting executable to be covered by the GNU General Public +// License. This exception does not however invalidate any other +// reasons why the executable file might be covered by the GNU General +// Public License. + +#ifndef MLN_CANVAS_LABELING_HH +# define MLN_CANVAS_LABELING_HH + +/// \file mln/canvas/labeling.hh +/// +/// Connected component labeling of the object part in a binary image. +/// +/// \todo Make the fastest version work. + +# include <mln/core/concept/image.hh> +# include <mln/data/fill.hh> +# include <mln/literal/zero.hh> +# include <mln/convert/to_upper_window.hh> + + +namespace mln +{ + + namespace canvas + { + + // General version. + template <typename I, typename N, typename F, typename L> + mln_ch_value(I, L) + labeling(const Image& input, const Neighborhood<N>& nbh, + F& functor, L& nlabels); + + +# ifndef MLN_INCLUDE_ONLY + + // Tests. + + namespace internal + { + + template <typename I, typename N, typename F, typename L> + void + labeling_tests(const Image& input_, const Neighborhood<N>& nbh_, + const F& f, const L& nlabels) + { + const I& input = exact(input_); + const N& nbh = exact(nbh_); + + mln_precondition(input.is_valid()); + // mln_precondition(nbh.is_valid()); + + (void) input; + (void) nbh; + (void) f; + (void) nlabels; + } + + } // end of namespace mln::canvas::internal + + + + // Implementations. + + namespace impl + { + + namespace generic + { + + template <typename I> + static 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, typename F, typename L> + mln_ch_value(I, L) + labeling(const Image& input_, const Neighborhood<N>& nbh_, + F& f, L& nlabels) + { + trace::entering("canvas::impl::generic::labeling"); + + // FIXME: Test?! + + const I& input = exact(input_); + const N& nbh = exact(nbh_); + + typedef typename F::S S; + + // Local type. + typedef mln_psite(I) P; + + // Auxiliary data. + mln_ch_value(I, bool) deja_vu; + mln_ch_value(I, P) parent; + + // Output. + mln_ch_value(I, L) output; + bool status; + + // Initialization. + { + initialize(deja_vu, input); + mln::data::fill(deja_vu, false); + + initialize(parent, input); + + initialize(output, input); + mln::data::fill(output, L(literal::zero)); + nlabels = 0; + + f.init(); // Client initialization. + } + + // First Pass. + { + mln_fwd_piter(S) p(f.s); + mln_niter(N) n(nbh, p); + for_all(p) if (f.handles(p)) + { + // Make-Set. + parent(p) = p; + f.init_attr(p); + + for_all(n) + if (input.domain().has(n) && deja_vu(n)) + { + if (f.equiv(n, p)) + { + // Do-Union. + P r = find_root(parent, n); + if (r != p) + { + parent(r) = p; + f.merge_attr(r, p); + } + } + else + f.do_no_union(n, p); + } + deja_vu(p) = true; + } + } + + // Second Pass. + { + mln_bkd_piter(S) p(f.s); + for_all(p) if (f.handles(p)) + { + if (parent(p) == p) // if p is root + { + if (f.labels(p)) + { + if (nlabels == mln_max(L)) + { + status = false; + return output; + } + output(p) = ++nlabels; + } + } + else + output(p) = output(parent(p)); + } + status = true; + } + + trace::exiting("canvas::impl::generic::labeling"); + return output; + } + + } // end of namespace mln::canvas::impl::generic + + + + // Fastest version + + template <typename I> + static inline + unsigned + find_root_fastest(I& parent, unsigned x) + { + if (parent.element(x) == x) + return x; + else + return parent.element(x) = find_root(parent, parent.element(x)); + } + + template <typename I, typename N, typename F, typename L> + mln_ch_value(I, L) + labeling_fastest(const Image& input_, const Neighborhood<N>& nbh_, + F& f, L& nlabels) + { + trace::entering("canvas::impl::labeling"); + + // FIXME: Test?! + + const I& input = exact(input_); + const N& nbh = exact(nbh_); + + typedef typename F::S S; + + // Local type. + typedef mln_psite(I) P; + + // Auxiliary data. + mln_ch_value(I, bool) deja_vu; + mln_ch_value(I, P) parent; + + // Output. + mln_ch_value(I, L) output; + bool status; + + // Initialization. + { + initialize(deja_vu, input); + mln::data::fill(deja_vu, false); + + initialize(parent, input); + + initialize(output, input); + mln::data::fill(output, L(literal::zero)); + nlabels = 0; + + f.init(); // Client initialization. + } + + // First Pass. + { + mln_pixter(const S) p(f.s); + mln_nixter(const S, N) n(p, nbh); + for_all(p) if (f.handles(p)) + { + // Make-Set. + parent.element(p) = p; + f.init_attr(p); + + for_all(n) + if (input.has(n) && deja_vu(n)) + { + if (f.equiv(n, p)) + { + // Do-Union. + P r = find_root(parent, n); + if (r != p) + { + parent.element(r) = p; + f.merge_attr(r, p); + } + } + else + f.do_no_union(n, p); + } + deja_vu(p) = true; + } + } + + // Second Pass. + { + mln_bkd_pixter(S) p(f.s); + for_all(p) if (f.handles(p)) + { + if (parent.element(p) == p) // if p is root + { + if (f.labels(p)) + { + if (nlabels == mln_max(L)) + { + status = false; + return output; + } + output.element(p) = ++nlabels; + } + } + else + output.element(p) = output(parent.element(p)); + } + status = true; + } + + trace::exiting("canvas::impl::labeling"); + return output; + } + + } // end of namespace mln::canvas::impl + + + + // Dispatch. + + namespace internal + { + + template <typename I, typename N, typename F, typename L> + inline + mln_ch_value(I, L) + labeling(metal::false_, const Image& input, + const Neighborhood<N>& nbh, F& functor, L& nlabels) + { + return impl::generic::labeling(input, nbh, functor, nlabels); + } + + template <typename I, typename N, typename F, typename L> + inline + mln_ch_value(I, L) + labeling(metal::true_, const Image& input, + const Neighborhood<N>& nbh, F& functor, L& nlabels) + { + return impl::labeling_fastest(input, nbh, functor, nlabels); + } + + template <typename I, typename N, typename F, typename L> + inline + mln_ch_value(I, L) + labeling_dispatch(const Image& input, const Neighborhood<N>& nbh, + F& functor, L& nlabels) + { + enum { + test = mlc_equal(mln_trait_image_speed(I), + trait::image::speed::fastest)::value + && + mln_is_simple_neighborhood(N)::value + }; + return impl::generic::labeling(metal::bool_<test>(), input, nbh, + functor, nlabels); + } + + } // end of namespace mln::canvas::internal + + + + // Facade. + + template <typename I, typename N, typename F, typename L> + inline + mln_ch_value(I, L) + labeling(const Image& input, const Neighborhood<N>& nbh, + F& functor, L& nlabels) + { + trace::entering("canvas::labeling"); + + internal::labeling_tests(input, nbh, functor, nlabels); + + mln_ch_value(I, L) output; + output = internal::labeling_dispatch(input, nbh, functor, nlabels); + + trace::exiting("canvas::labeling"); + return output; + } + + +# endif // ! MLN_INCLUDE_ONLY + + } // end of namespace mln::canvas + +} // end of namespace mln + + +#endif // ! MLN_CANVAS_LABELING_HH

2 1

r3256: First tries of accus with specialisation
by Edwin Carlinet 04 Feb '09

04 Feb '09

URL: https://svn.lrde.epita.fr/svn/oln/trunk/milena/sandbox ChangeLog: 2009-02-03 Edwin Carlinet <carlinet(a)lrde.epita.fr> First tries of accus with specialisation. * accu.cc: New. * fredwin.cc: . --- accu.cc | 91 +++++++++++++++++++++++++++++++++++++++++++++++++++++++++ fredwin.cc | 96 ++++++++++++++++++++++++++++++++++++------------------------- 2 files changed, 149 insertions(+), 38 deletions(-) Index: trunk/milena/sandbox/edwin/accu.cc =================================================================== --- trunk/milena/sandbox/edwin/accu.cc (revision 0) +++ trunk/milena/sandbox/edwin/accu.cc (revision 3256) @@ -0,0 +1,91 @@ +template <typename E> +struct Accumulator : public object<E> +{ + typedef mln_vtypes(E, take_with) take_with; + + + +}; + +namespace accu +{ + template <typename T> + struct card : public Accumulator< card<T> > + { + void take(const T& elt) { ++c_; } + unsigned c_; + }; +} + + +namespace impl +{ + + template <typename I, template<typename E> class A> + void + algebraic(const Image& input, + const Accumulator< A<point2d> >& acc) + { + const I& ima = exact(input); + + mln_piter(I) p(ima.domain()); + for_all(p) + acc.take(p); + } + + // fast implementation + template <typename I, template<typename E> class A> + void + leveling (const Image& input, + const Accumulator< A< pix > >& acc) + { + const I& ima = exact(input); + + mln_pixter(const I) px(ima); + for_all(px) + acc.take(px); + } + + // generic implementation + template <typename I, template<typename E> class A> + void + leveling (const Image& input, + const Accumulator< A<point2d> >& acc) + { + const I& ima = exact(input); + + mln_piter(I) p(ima.domain()); + for_all(p) + acc.take(p); + } + + +} // impl + +namespace internal +{ + template <typename I, typename A> + void + leveling_dispatch(const Image& input, + const Accumulator<A>& acc) + { + + //Si when_pix = use_only + // + + algebraic_dispatch(mlc_equal(mln_trait_image_speed(I), + trait::image::speed::fastest)::value, + input, + acc); + } + +} + +// Facade. + +template <typename M, typename I> +void +algebraic(const Image& input, const Meta_Accumulator<M>& acc) // FIXME: on prÃ©fÃšre Meta_Accumulator ! +{ + internal::algebraic_dispatch(input, acc); +} Index: trunk/milena/sandbox/edwin/fredwin.cc =================================================================== --- trunk/milena/sandbox/edwin/fredwin.cc (revision 3255) +++ trunk/milena/sandbox/edwin/fredwin.cc (revision 3256) @@ -1,5 +1,7 @@ +// TODO : ajouter un trait when_pix +// when_pix in {use_p template <typename E> struct Accumulator { @@ -46,15 +48,16 @@ + namespace impl { // Leveling // -------- - template <typename I, typename A> + template <typename I, typename PX> void - leveling(const Image& input, const Accumulator<A>& acc) + leveling_generic(const Image& input, const Accumulator<PX>& acc) { const I& ima = exact(input); // algo en resume : @@ -80,29 +83,15 @@ // spécialisation pour les images fastest - // Algebraic - // --------- - - - template <typename I, typename A> - void - generic_algebraic(const Image& input, const Accumulator<A>& acc) - { - // algo en resume : - mln_piter(I) p(ima.domain()); - for_all(p) - acc.take(p); // psite - } - - template <typename I, typename A> - void - algebraic_fastest(const Image& input, const Accumulator<A>& acc) - { - // algo en resume : - mln_pixter(const I) pxl(input); - for_all(pxl) - acc.take(pxl); - } + // template <typename I, typename A> +// void +// algebraic_fastest(const Image& input, const Accumulator<A>& acc) +// { +// // algo en resume : +// mln_pixter(const I) pxl(input); +// for_all(pxl) +// acc.take(pxl); +// } // FIXME: pb: soit on passe du "site", soit du "pixel"... @@ -123,29 +112,60 @@ // FIXME: On veut qqch qui ressemble à : - template <typename I, typename A> +// template <typename I, typename A> +// void +// generic_algebraic_or_leveling(const Image& input, const Accumulator<A>& acc) +// { +// const I& ima = exact(input); +// // algo en resume : +// mln_piter(I) p(ima.domain()); +// for_all(p) +// acc.take( FIXME ); +// } + +// template <typename I, typename A> +// void +// algebraic_or_leveling_fastest(const Image& input, const Accumulator<A>& acc) +// { +// const I& ima = exact(input); +// // algo en resume : +// mln_pixter(const I) pxl(ima); +// for_all(pxl) +// acc.take( FIXME ); +// } + + + // FIXME: Mais ce n'est peut-être pas possible avec des + // Accumulator... + + // Algebraic + // --------- + + + template <typename I, template<typename E> typename A> void - generic_algebraic_or_leveling(const Image& input, const Accumulator<A>& acc) + algebraic(const Image& input, const Accumulator< A<point2d> >& acc) { + const I& ima = exact(input); + // algo en resume : mln_piter(I) p(ima.domain()); for_all(p) - acc.take( FIXME ); + acc.take(p); // psite } - template <typename I, typename A> + + + template <typename I, template<typename E> typename A> void - algebraic_or_leveling_fastest(const Image& input, const Accumulator<A>& acc) + leveling (const Image& input, const Accumulator< A< pix > >& acc) { - // algo en resume : - mln_pixter(const I) pxl(input); - for_all(pxl) - acc.take( FIXME ); - } - + const I& ima = exact(input); - // FIXME: Mais ce n'est peut-être pas possible avec des - // Accumulator... + mln_pixter(const I) px(ima); + for_all(px) + acc.take(px); + } } // impl

2 1