2006-08-04 Thierry GERAUD <theo(a)tegucigalpa.lrde.epita.fr>
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