https://svn.lrde.epita.fr/svn/oln/trunk Index: ChangeLog from Thierry Geraud &lt;thierry.geraud(a)lrde.epita.fr&gt; Update milena. * olena/oln/morpho/Rd/union_find.hh: Update. * milena/test/main.cc: Use Rd. * milena/morpho/Rd.hh: New. * milena/level/fill.hh: Add assertions. * milena/level/compare.hh: New. * milena/level/paste.hh: New. * milena/core/macros.hh (mln_ch_value): New. * milena/core/concept/image.hh: Update. * milena/core/image2d.hh: Update. milena/core/concept/image.hh | 8 + milena/core/image2d.hh | 6 + milena/core/macros.hh | 4 milena/level/compare.hh | 63 +++++++++++++ milena/level/fill.hh | 20 ++++ milena/level/paste.hh | 38 +++++++ milena/morpho/Rd.hh | 181 ++++++++++++++++++++++++++++++++++++++ milena/test/main.cc | 83 +++++++++-------- olena/oln/morpho/Rd/union_find.hh | 51 +++++----- 9 files changed, 393 insertions(+), 61 deletions(-) Index: olena/oln/morpho/Rd/union_find.hh --- olena/oln/morpho/Rd/union_find.hh (revision 986) +++ olena/oln/morpho/Rd/union_find.hh (working copy) @@ -29,6 +29,7 @@ # define OLN_MORPHO_RD_UNION_FIND_HH # include <oln/morpho/Rd/utils.hh> +# include <oln/core/internal/max_value.hh> namespace oln @@ -45,6 +46,7 @@ struct union_find_t { typedef oln_point(I) point; + typedef oln_value(I) value; // in: I f, g; @@ -55,8 +57,8 @@ // aux: std::vector<point> S; - I data; - oln_plain_value(I, bool) is_proc; + // was: I data; + oln_plain_value(I, bool) isproc; oln_plain_value(I, point) parent; union_find_t(const I& f, const I& g, const N& nbh) @@ -64,14 +66,15 @@ { prepare(o, with, f); prepare(parent, with, f); - prepare(is_proc, with, f); - prepare(data, with, f); + prepare(isproc, with, f); + // was: prepare(data, with, f); // init std::cout << "0 "; - level::fill(inplace(is_proc), false); + level::fill(inplace(isproc), false); S = histo_reverse_sort(g); + level::paste(f, inplace(o)); // new: replace make_set(p) { data(p) = f(p) } // first pass @@ -83,35 +86,40 @@ make_set(p); oln_niter(N) n(nbh, p); for_all(n) - if (f.has(n) and is_proc(n)) + { + if (f.has(n)) + assert(isproc(n) = is_proc(n, p)); + if (f.has(n) and isproc(n)) do_union(n, p); - is_proc(p) = true; + } + isproc(p) = true; } // second pass std::cout << "2 "; - level::fill(inplace(is_proc), false); for (int i = S.size() - 1; i >= 0; --i) { point p = S[i]; - assert(is_proc(p) = false); if (parent(p) = p) - o(p) = data(p) = 255 ? g(p) : data(p); + if (o(p) = oln_max(value)) + o(p) = g(p); else - { - assert(is_proc(parent(p)) = true); o(p) = o(parent(p)); } - is_proc(p) = true; + } + bool is_proc(const point& n, const point& p) const + { + return g(n) > g(p) or (g(n) = g(p) and n < p); } void make_set(const point& p) { parent(p) = p; - data(p) = f(p); + // was: data(p) = f(p); + // now: in "initialization" } point find_root(const point& x) @@ -122,24 +130,21 @@ return parent(x) = find_root(parent(x)); } - bool equiv(const point& r, const point& p) - { - return g(r) = g(p) or g(p) >= data(r); - } - void do_union(const point& n, const point& p) { point r = find_root(n); if (r != p) { - if (equiv(r, p)) + // NEW: o replaces data + + if (g(r) = g(p) or g(p) >= o(r)) // equiv test { parent(r) = p; - if (data(r) > data(p)) - data(p) = data(r); // increasing criterion + if (o(r) > o(p)) + o(p) = o(r); // increasing criterion } else - data(p) = 255; + o(p) = oln_max(value); } } Index: milena/test/main.cc --- milena/test/main.cc (revision 986) +++ milena/test/main.cc (working copy) @@ -10,11 +10,15 @@ #include <core/neighb2d.hh> #include <morpho/erosion.hh> +#include <morpho/Rd.hh> -int cos_sin(const mln::point2d& p) +typedef unsigned char int_u8; + + +int_u8 cos_sin(const mln::point2d& p) { - return int(255 * std::cos(float(p.row())) * std::sin(float(p.col()))); + return (int_u8)(255 * std::cos(float(p.row())) * std::sin(float(p.col()))); } @@ -22,43 +26,46 @@ { using namespace mln; - box2d b = mk_box2d(/* row = */ 1, 3, - /* col = */ 4, 6); - std::cout << b << std::endl; - - bool w[] - { 0, 1, 0, - 0, 1, 0, - 1, 0, 0 }; - window2d win = mk_window2d(w); - std::cout << win << std::endl; - std::cout << c8() << std::endl; - - /* - { - image2d<int> ima(b); - level::fill(ima, 51); - debug::println(ima); - - std::cout << win << std::endl; - - morpho::erosion(ima, win); - - rectangle2d rec(1, 2); - std::cout << rec << std::endl; + const unsigned size = 1000; + image2d<int_u8> f(size, size); + morpho::Rd(f, f, c8()); } - */ - - - { - image2d<int> ima(b); - level::fill(ima, cos_sin); - debug::println(ima); - std::cout << std::endl; - image2d<int> ima2 = morpho::erosion(ima, win); - debug::println(ima2); - } -} +// box2d b = mk_box2d(/* row = */ 1, 3, +// /* col = */ 4, 6); +// std::cout << b << std::endl; + +// bool w[] +// { 0, 1, 0, +// 0, 1, 0, +// 1, 0, 0 }; +// window2d win = mk_window2d(w); +// std::cout << win << std::endl; +// std::cout << c8() << std::endl; + +// { +// image2d<int> ima(b); +// level::fill(ima, 51); +// debug::println(ima); + +// std::cout << win << std::endl; + +// morpho::erosion(ima, win); + +// rectangle2d rec(1, 2); +// std::cout << rec << std::endl; +// } + + +// { +// image2d<int> ima(b); +// level::fill(ima, cos_sin); +// debug::println(ima); + +// std::cout << std::endl; + +// image2d<int> ima2 = morpho::erosion(ima, win); +// debug::println(ima2); +// } Index: milena/morpho/Rd.hh --- milena/morpho/Rd.hh (revision 0) +++ milena/morpho/Rd.hh (revision 0) @@ -0,0 +1,181 @@ +#ifndef MLN_MORPHO_RD_HH +# define MLN_MORPHO_RD_HH + +# include <vector> + +# include <core/concept/image.hh> +# include <core/concept/neighborhood.hh> + +# include <value/props.hh> + +# include <level/fill.hh> +# include <level/compare.hh> + + + +namespace mln +{ + + namespace morpho + { + + template <typename I, typename N> + I Rd(const Image<I>& f, const Image<I>& g, const Neighborhood<N>& nbh); + + +# ifndef MLN_INCLUDE_ONLY + + namespace impl + { + + template <typename I> + std::vector<unsigned> compute_histo(const I& ima) + { + std::vector<unsigned> h(256, 0); + mln_piter(I) p(ima.domain()); + for_all(p) + ++h[ima(p)]; + return h; + } + + template <typename I> + std::vector<mln_point(I)> histo_reverse_sort(const I& ima) + { + std::vector<unsigned> h = compute_histo(ima); + // preparing output data + std::vector<int> loc(256); + loc[255] = 0; + for (int l = 254; l >= 0; --l) + loc[l] = loc[l+1] + h[l+1]; + std::vector<mln_point(I)> vec(ima.domain().npoints()); + // storing output data + mln_piter(I) p(ima.domain()); + for_all(p) + vec[loc[ima(p)]++] = p; + return vec; + } + + + template <typename I, typename N> + struct Rd + { + typedef mln_point(I) point; + typedef mln_value(I) value; + + // in: + const I& f; + const I& g; + const N& nbh; + + // out: + I o; + + // aux: + mln_ch_value(I, bool) is_proc; + mln_ch_value(I, point) parent; + std::vector<point> S; + + Rd(const I& f, const I& g, const N& nbh) + : f(f), g(g), nbh(nbh), + o(f.domain()), + is_proc(f.domain()), + parent(f.domain()) + { + // init + level::fill(o, f); + S = histo_reverse_sort(g); + level::fill(is_proc, false); // FIXME: rm + + // first pass + for (unsigned i = 0; i < S.size(); ++i) + { + point p = S[i]; + + make_set(p); + mln_niter(N) n(nbh, p); + for_all(n) + { + if (f.has(n)) + assert(is_proc(n) = is_proc__(n, p)); + if (f.has(n) and is_proc(n)) + do_union(n, p); + } + is_proc(p) = true; + } + + // second pass + for (int i = S.size() - 1; i >= 0; --i) + { + point p = S[i]; + if (parent(p) = p) + if (o(p) = mln_max(value)) + o(p) = g(p); + else + o(p) = o(parent(p)); + is_proc(p) = true; + } + + } + + bool is_proc__(const point& n, const point& p) const + { + return g(n) > g(p) or (g(n) = g(p) and n < p); + } + + void make_set(const point& p) + { + parent(p) = p; + } + + point find_root(const point& x) + { + if (parent(x) = x) + return x; + else + return parent(x) = find_root(parent(x)); + } + + bool equiv(const point& r, const point& p) + { + return g(r) = g(p) or g(p) >= o(r); + } + + void do_union(const point& n, const point& p) + { + point r = find_root(n); + if (r != p) + { + if (equiv(r, p)) + { + parent(r) = p; + if (o(r) > o(p)) + o(p) = o(r); // increasing criterion + } + else + o(p) = mln_max(value); + } + } + + }; + + } // end of namespace mln::morpho::impl + + + // facade + + template <typename I, typename N> + I Rd(const Image<I>& f, const Image<I>& g, const Neighborhood<N>& nbh) + { + assert(f <= g); + impl::Rd<I,N> run(exact(f), exact(g), exact(nbh)); + return run.o; + } + +# endif // ! MLN_INCLUDE_ONLY + + } // end of namespace mln::morpho + +} // end of namespace mln + + +#endif // ! MLN_MORPHO_RD_HH Index: milena/level/fill.hh --- milena/level/fill.hh (revision 986) +++ milena/level/fill.hh (working copy) @@ -22,6 +22,10 @@ void fill(Image<I>& ima_, const mln_value(I) array[]); + template <typename I, typename J> + void fill(Image<I>& ima_, + const Image<J>& data); + # ifndef MLN_INCLUDE_ONLY @@ -30,6 +34,7 @@ const mln_value(I)& value) { I& ima = exact(ima_); + assert(ima.has_data()); mln_piter(I) p(ima.domain()); for_all(p) ima(p) = value; @@ -40,6 +45,7 @@ mln_value(I) (*f)(const mln_point(I)& p)) { I& ima = exact(ima_); + assert(ima.has_data()); mln_piter(I) p(ima.domain()); for_all(p) ima(p) = f(p); @@ -50,12 +56,26 @@ const mln_value(I) array[]) { I& ima = exact(ima_); + assert(ima.has_data()); mln_piter(I) p(ima.domain()); unsigned i = 0; for_all(p) ima(p) = array[i++]; } + template <typename I, typename J> + void fill(Image<I>& ima_, + const Image<J>& data_) + { + I& ima = exact(ima_); + const J& data = exact(data_); + assert(ima.has_data() and data.has_data()); + + mln_piter(I) p(ima.domain()); + for_all(p) + ima(p) = data(p); + } + # endif // ! MLN_INCLUDE_ONLY } // end of namespace mln::level Index: milena/level/compare.hh --- milena/level/compare.hh (revision 0) +++ milena/level/compare.hh (revision 0) @@ -0,0 +1,63 @@ +#ifndef MLN_LEVEL_COMPARE_HH +# define MLN_LEVEL_COMPARE_HH + +# include <core/concept/image.hh> + + +namespace mln +{ + + template <typename L, typename R> + bool operator = (const Image<L>& lhs, const Image<R>& rhs); + + template <typename L, typename R> + bool operator < (const Image<L>& lhs, const Image<R>& rhs); + + template <typename L, typename R> // required! + bool operator <= (const Image<L>& lhs, const Image<R>& rhs); + + +# ifndef MLN_INCLUDE_ONLY + + template <typename L, typename R> + bool operator = (const Image<L>& lhs_, const Image<R>& rhs_) + { + const L& lhs = exact(lhs_); + const R& rhs = exact(rhs_); + mln_piter(L) p(lhs.domain()); + for_all(p) + if (not (lhs(p) = rhs(p))) + return false; + return true; + } + + template <typename L, typename R> + bool operator < (const Image<L>& lhs_, const Image<R>& rhs_) + { + const L& lhs = exact(lhs_); + const R& rhs = exact(rhs_); + mln_piter(L) p(lhs.domain()); + for_all(p) + if (not (lhs(p) < rhs(p))) + return false; + return true; + } + + template <typename L, typename R> // required! + bool operator <= (const Image<L>& lhs_, const Image<R>& rhs_) + { + const L& lhs = exact(lhs_); + const R& rhs = exact(rhs_); + mln_piter(L) p(lhs.domain()); + for_all(p) + if (not (lhs(p) <= rhs(p))) + return false; + return true; + } + +# endif // ! MLN_INCLUDE_ONLY + +} // end of namespace mln + + +#endif // ! MLN_LEVEL_COMPARE_HH Index: milena/level/paste.hh --- milena/level/paste.hh (revision 0) +++ milena/level/paste.hh (revision 0) @@ -0,0 +1,38 @@ +#ifndef MLN_LEVEL_PASTE_HH +# define MLN_LEVEL_PASTE_HH + +# include <core/concept/image.hh> + + +namespace mln +{ + + namespace level + { + + template <typename I, typename J> + void paste(const Image<I>& data, Image<J>& destination); + + +# ifndef MLN_INCLUDE_ONLY + + template <typename I, typename J> + void paste(const Image<I>& data_, Image<J>& destination_) + { + const I& data = exact(data_); + I& destination = exact(destination_); + assert(ima.has_data() and destination.has_data()); + + mln_piter(I) p(data.domain()); + for_all(p) + destination(p) = data(p); + } + +# endif // ! MLN_INCLUDE_ONLY + + } // end of namespace mln::level + +} // end of namespace mln + + +#endif // ! MLN_LEVEL_PASTE_HH Index: milena/core/macros.hh --- milena/core/macros.hh (revision 986) +++ milena/core/macros.hh (working copy) @@ -25,4 +25,8 @@ # define mln_rvalue(T) typename T::rvalue # define mln_lvalue(T) typename T::lvalue + +# define mln_ch_value(I, T) typename I::template change_value<T>::ret + + #endif // ! MLN_CORE_MACROS_HH Index: milena/core/concept/image.hh --- milena/core/concept/image.hh (revision 986) +++ milena/core/concept/image.hh (working copy) @@ -25,6 +25,12 @@ rvalue operator()(const psite& p) const; lvalue operator()(const psite& p); + template <typename T> + struct change_value + { + typedef ret; + }; + // provided by internal::image_base_: @@ -71,6 +77,8 @@ typedef mln_rvalue(E) rvalue; typedef mln_lvalue(E) lvalue; + typedef mln_ch_value(E, value) change; + bool (E::*m3)() const = & E::has_data; m3 = 0; bool (E::*m4)(const psite& p) const = & E::owns_; Index: milena/core/image2d.hh --- milena/core/image2d.hh (revision 986) +++ milena/core/image2d.hh (working copy) @@ -15,6 +15,12 @@ typedef const T& rvalue; typedef T& lvalue; + template <typename U> + struct change_value + { + typedef image2d<U> ret; + }; + image2d(); image2d(int nrows, int ncols); image2d(const box2d& b);