2006-08-04 Thierry GERAUD &lt;theo(a)tegucigalpa.lrde.epita.fr&gt; Factor some code in oln/lrde/ufmt/; add video raster scan algorithms and some versions with points as indices. * olena/oln/lrde/ufmt/README: New. * olena/oln/lrde/ufmt/basic_maxtree.hh: Move some parts into... * olena/oln/lrde/ufmt/ap_maxtree.hh: ...this new file. * olena/oln/lrde/ufmt/sp_maxtree.hh: New. * olena/oln/lrde/ufmt/ai_maxtree.hh: New. * olena/oln/lrde/ufmt/si_maxtree.hh: New. * olena/oln/lrde/ufmt/rup_maxtree.hh: New. * olena/oln/lrde/ufmt/bin/sp_maxtree.cc: New. * olena/oln/lrde/ufmt/bin/si_maxtree.cc: New. * olena/oln/lrde/ufmt/bin/rup_maxtree.cc: New. * olena/oln/lrde/ufmt/bin/r1_maxtree.cc: New. Index: 10.245/oln.prj --- 10.245/oln.prj +++ 10.245(w)/oln.prj @@ -1548,6 +1548,39 @@ (doc/ref/exdoc.mk (oln/x/9_exdoc.mk 1.1 644)) (doc/ref/doxygen.config (oln/x/10_doxygen.co 1.1 644)) (doc/ref/out/exdoc.config (oln/x/11_exdoc.conf 1.1 644)) + +;; Files added by populate at Fri, 04 Aug 2006 18:38:31 +0200, +;; to version 10.245(w), by theo: + + (olena/oln/lrde/ufmt/ai_maxtree.hh ()) + (olena/oln/lrde/ufmt/si_maxtree.hh ()) + (olena/oln/lrde/ufmt/rup_maxtree.hh ()) + (olena/oln/lrde/ufmt/sp_maxtree.hh ()) + (olena/oln/lrde/ufmt/ap_maxtree.hh ()) + (olena/oln/lrde/ufmt/r1_maxtree.hh ()) + (olena/oln/lrde/ufmt/bin/rup_maxtree.cc ()) + (olena/oln/lrde/ufmt/bin/si_maxtree.cc ()) + (olena/oln/lrde/ufmt/bin/sp_maxtree.cc ()) + (olena/oln/lrde/ufmt/bin/r1_maxtree.cc ()) + + + + + + + (olena/oln/lrde/ufmt/README ()) + +;; Files deleted by depopulate at Fri, 04 Aug 2006 18:41:16 +0200, +;; from version 10.245(w), by theo: + + ; (olena/oln/lrde/ufmt/bin/exe/si_maxtree () :no-keywords) + ; (olena/oln/lrde/ufmt/bin/exe/rup2_maxtree () :no-keywords) + ; (olena/oln/lrde/ufmt/bin/exe/sp_maxtree () :no-keywords) + ; (olena/oln/lrde/ufmt/bin/exe/rup_maxtree () :no-keywords) + ; (olena/oln/lrde/ufmt/bin/exe/basic_salembier () :no-keywords) + ; (olena/oln/lrde/ufmt/bin/exe/basic_maxtree () :no-keywords) ) (Merge-Parents) -(New-Merge-Parents) +(New-Merge-Parents + (10.245 complete) +) Index: 10.245/olena/oln/lrde/ufmt/bin/basic_maxtree.cc --- 10.245/olena/oln/lrde/ufmt/bin/basic_maxtree.cc Thu, 03 Aug 2006 16:06:43 +0200 theo (oln/x/0_basic_maxt 1.1 644) +++ 10.245(w)/olena/oln/lrde/ufmt/bin/basic_maxtree.cc Fri, 04 Aug 2006 10:26:17 +0200 theo (oln/x/0_basic_maxt 1.1 644) @@ -36,5 +36,6 @@ algorithm_t run(input, c == 4 ? neighb_c4() : neighb_c8()); run.go(); + std::cout << "n level roots = " << n_level_roots(run) << std::endl; } Index: 10.245/olena/oln/lrde/ufmt/basic_maxtree.hh --- 10.245/olena/oln/lrde/ufmt/basic_maxtree.hh Thu, 03 Aug 2006 16:06:43 +0200 theo (oln/x/4_basic_maxt 1.1 644) +++ 10.245(w)/olena/oln/lrde/ufmt/basic_maxtree.hh Fri, 04 Aug 2006 11:53:39 +0200 theo (oln/x/4_basic_maxt 1.1 644) @@ -30,6 +30,7 @@ # include <oln/level/fill.hh> # include <oln/lrde/ufmt/utils.hh> +# include <oln/lrde/ufmt/ap_maxtree.hh> @@ -46,20 +47,16 @@ // FIXME: doc. template <class I> - struct basic_maxtree + struct basic_maxtree : public ap_maxtree<I> { - typedef I image; - typedef oln_point_type(I) point; - typedef oln_value_type(I) value; - typedef oln_neighborhood_type(I) Nbh; - typedef oln_iter_type(Nbh) niter; - - // input - const I& f; - const Nbh& nbh; + typedef ap_maxtree<I> super; + using super::f; + using super::nbh; + using super::par; + oln_lrde_ufmt_import_ap_maxtree_typedefs; + // aux data - typename mute<I, point>::ret par; typename mute<I, bool>::ret isproc; std::vector<point> S; @@ -69,10 +66,7 @@ basic_maxtree(const abstract::image<I>& f, const oln_neighborhood_type(I)& nbh) : - f(f.exact()), - nbh(nbh), - // FIXME: par and isproc should NOT be initialized here! (but in "init()") - par(f.size()), + super(f, nbh), isproc(f.size()) { } @@ -110,67 +104,21 @@ // FIXME: TODO } - void make_set(const point& x) - { - par[x] = x; - } - void do_union(const point& n, const point& p) { - point r = find_tree_root(n); + point r = find_root(n); if (r != p) par[r] = p; } - bool is_tree_root(const point& x) const - { - return par[x] == x; - } - - bool is_level_root(const point& x) const - { - return is_tree_root(x) or f[par[x]] < f[x]; - } - - point find_level_root(const point& x) - { - if (is_level_root(x)) - return x; - else - return par[x] = find_level_root(par[x]); - } - - point find_tree_root(point x) + point find_root(point x) { - while (not is_tree_root(x)) + while (not is_root(x)) x = find_level_root(par[x]); return x; } - - // uniformized interface - - const point& parent_(const point& p) const { - return par[p]; - } - const value& f_(const point& p) const { - return f[p]; - } - const I& f_() const { - return f; - } - bool is_tree_root_(const point& p) const { - return is_tree_root(p); - } - bool is_level_root_(const point& p) const { - return is_level_root(p); - } - - // end of uniformized interface - - - }; // end of class basic_maxtree Index: 10.245/olena/oln/lrde/ufmt/utils.hh --- 10.245/olena/oln/lrde/ufmt/utils.hh Thu, 03 Aug 2006 16:06:43 +0200 theo (oln/x/8_utils.hh 1.1 644) +++ 10.245(w)/olena/oln/lrde/ufmt/utils.hh Fri, 04 Aug 2006 16:00:07 +0200 theo (oln/x/8_utils.hh 1.1 644) @@ -32,6 +32,14 @@ # include <vector> + + + +# define oln_neighborhood_type(I) \ +typename oln::lrde::ufmt::internal::neighborhood<I>::ret + + + namespace oln { @@ -138,6 +146,7 @@ } + template <class I> std::vector<oln_point_type(I)> histogram_reverse_sort_p(const abstract::image<I>& input, @@ -166,6 +175,56 @@ } + // _i + + template <class I> + std::vector<int> + histogram_reverse_sort_i(const abstract::image<I>& input, + size_t N, + std::vector<size_t>& H) + { + H = histogram(input, N); + + // preparing output data + + unsigned nvalues = uint_nvalues(input); + std::vector<int> loc(nvalues); + loc[nvalues - 1] = 0; + for (int l = int(nvalues) - 2; l >= 0; --l) + loc[l] = loc[l+1] + H[l+1]; + + std::vector<int> vec(N); + + // storing output data + + typedef oln_value_type(I) value_t; + typedef oln_point_type(I) point_t; + + I& input_ = const_cast<I&>(input.exact()); + value_t* orig = &(input_[point_t()]); + oln_iter_type(I) p(input); + size_t count = 0; + for_all(p) + { + vec[loc[input[p]]++] = int(&(input_[p]) - orig); + if (++count == N) + return vec; + } + + return vec; + } + + + template <class I> + std::vector<int> + histogram_reverse_sort_i(const abstract::image<I>& input, + std::vector<size_t>& H) + { + return histogram_reverse_sort_i(input, input.npoints(), H); + } + + + // Extra traits to get the classical neighborhood types from // classical image types. @@ -185,6 +244,59 @@ + template <class I> + unsigned pre(const oln_neighborhood_type(I)& nbh, + std::vector<oln_dpoint_type(I)>& pre) + { + for (unsigned i = 0; i < nbh.card(); ++i) + { + unsigned d; + for (d = 0; d < I::dim; ++d) + if (nbh.dp(i).nth(d) < 0) { + pre.push_back(nbh.dp(i)); + break; + } + else if (nbh.dp(i).nth(d) > 0) + break; + } + assert(pre.size() == (nbh.card() / 2)); + return pre.size(); + } + + + template <class I> + unsigned split(const oln_neighborhood_type(I)& nbh, + std::vector<oln_dpoint_type(I)>& pre, + std::vector<oln_dpoint_type(I)>& post) + { + for (unsigned i = 0; i < nbh.card(); ++i) + { + unsigned d; + bool is_post = true; + for (d = 0; d < I::dim; ++d) + if (nbh.dp(i).nth(d) < 0) { + pre.push_back(nbh.dp(i)); + is_post = false; + break; + } + else if (nbh.dp(i).nth(d) > 0) + break; + if (is_post) + post.push_back(nbh.dp(i)); + } + if (not ((pre.size() + post.size()) == nbh.card()) + or not (pre.size() == post.size())) + { + std::cerr << "pb in oln::lrde::ufmt::split (utils.hh) so abort!" << std::endl; + abort(); + } + assert((pre.size() + post.size()) == nbh.card()); + assert(pre.size() == post.size()); + return pre.size(); + } + + + } // end of namespace oln::lrde::ufmt } // end of namespace oln::lrde @@ -193,9 +305,5 @@ -# define oln_neighborhood_type(I) \ -typename oln::lrde::ufmt::internal::neighborhood<I>::ret - - #endif // ! OLENA_LRDE_UFMT_UTILS_HH Only in 10.245(w): olena/oln/lrde/ufmt/ai_maxtree.hh Only in 10.245(w): olena/oln/lrde/ufmt/si_maxtree.hh Only in 10.245(w): olena/oln/lrde/ufmt/rup_maxtree.hh Only in 10.245(w): olena/oln/lrde/ufmt/sp_maxtree.hh Only in 10.245(w): olena/oln/lrde/ufmt/ap_maxtree.hh Only in 10.245(w): olena/oln/lrde/ufmt/r1_maxtree.hh Only in 10.245(w): olena/oln/lrde/ufmt/bin/rup_maxtree.cc Only in 10.245(w): olena/oln/lrde/ufmt/bin/si_maxtree.cc Only in 10.245(w): olena/oln/lrde/ufmt/bin/sp_maxtree.cc Only in 10.245(w): olena/oln/lrde/ufmt/bin/r1_maxtree.cc Only in 10.245(w): olena/oln/lrde/ufmt/README