October 2012 - Olena-patches

olena-2.0-27-g925e576 More efficient lpde inpainting method implementation
by Coddy Levi 30 Oct '12

30 Oct '12

--- milena/mln/inpainting/inpaint.hh | 11 ++- milena/mln/inpainting/lpde.hh | 201 +++++++++++++++++++++++---------- milena/mln/inpainting/metric/psnr.hh | 12 ++- 3 files changed, 158 insertions(+), 66 deletions(-) diff --git a/milena/mln/inpainting/inpaint.hh b/milena/mln/inpainting/inpaint.hh index 44f20a8..86398e5 100644 --- a/milena/mln/inpainting/inpaint.hh +++ b/milena/mln/inpainting/inpaint.hh @@ -15,6 +15,8 @@ #include <mln/util/timer.hh> +#include <mln/inpainting/metric/psnr.hh> + namespace mln { namespace inpainting @@ -73,13 +75,20 @@ namespace mln I<bool> new_mask(roi); data::paste(inpaint_mask | roi, new_mask); + data::fill((new_src | pw::value(new_mask)).rw(), literal::zero); + mln::util::timer t; t.start(); inpaint_method(new_src, new_mask); t.stop(); - std::cout << "inpaint time = " << t << std::endl; + + double psnr = metric::psnr(inpaint_src | pw::value(inpaint_mask), + new_src | pw::value(new_mask)); + + std::cout << "inpaint time = " << t << "; " + << "psnr = " << psnr << std::endl; I<T> output(inpaint_src); { // paste new_src to output diff --git a/milena/mln/inpainting/lpde.hh b/milena/mln/inpainting/lpde.hh index 1f754d8..04a903a 100644 --- a/milena/mln/inpainting/lpde.hh +++ b/milena/mln/inpainting/lpde.hh @@ -1,5 +1,6 @@ #include <algorithm> #include <vector> +#include <limits> #include <mln/core/image/dmorph/image_if.hh> @@ -11,6 +12,8 @@ #include <mln/linear/gaussian.hh> #include <mln/core/alias/w_window2d_float.hh> +#include <mln/core/alias/neighb2d.hh> + #include <mln/pw/value.hh> #include <mln/value/int_u.hh> @@ -20,6 +23,17 @@ #include <mln/core/alias/vec2d.hh> +#include <mln/inpainting/derivative_kernels.hh> + +#include <mln/core/concept/accumulator.hh> + +#include <mln/trait/value_.hh> + +#include <mln/extension/adjust_duplicate.hh> + +#include <mln/norm/l2.hh> +#include <mln/value/int_u8.hh> + namespace mln { namespace inpainting @@ -49,92 +63,157 @@ namespace mln this->t_f = t_f; } - template <typename I> - void compute_diff_invariants(const I& u, - std::vector& invs, - const std::vector<float>& w) + template <typename T> + inline + T components_product(trait::value::nature::scalar, + T a, + T b) { - const float sigma = 0.8; + return a * b; + } + + template <typename T> + T components_product(trait::value::nature::vectorial, + T a, + T b) + { + T c; + // static loop unrolling ? + for (unsigned i = 0; i < mln_dim(T); ++i) + c[i] = a[i] * b[i]; + + return c; + } + + template <typename T> + inline + T components_product(T a, + T b) + { + return components_product(mln_trait_value_nature(T)(), a, b); + } + + template <typename I, typename M> + float diffuse(I& u, + const I& f, + const std::vector<float>& w, + const M& mask) + { + typedef mln_value(I) T; + + const float activation_threshold = 0.001; + + const unsigned derivative_kernels_size = 5; + const float* derivative_kernel[derivative_kernels_size]; + + derivative_kernel[0] = make_dx_kernel(); + derivative_kernel[1] = make_dy_kernel(); + derivative_kernel[2] = make_dxx_kernel(); + derivative_kernel[3] = make_dyy_kernel(); + derivative_kernel[4] = make_dxy_kernel(); - invs[0] = linear::gaussian_1st_derivative(u, sigma, 1); - invs[1] = linear::gaussian_1st_derivative(u, sigma, 0); - invs[2] = linear::gaussian_2nd_derivative(u, sigma, 1); - invs[3] = linear::gaussian_2nd_derivative(u, sigma, 0); - invs[4] = linear::gaussian_2nd_derivative(u, sigma); + static window2d full3x3; + static const bool vals[] = { 1, 1, 1, + 1, 1, 1, + 1, 1, 1 }; - { // TV regularization term div ( \nabla u / | \nabla u | ) + convert::from_to(vals, full3x3); - I u_xnx( invs[5].domain() ); - I u_yny( invs[5].domain() ); + mln_pixter(I) p(u); + //mln_pixter(const I) p_f(f); + mln_pixter(const M) p_m(mask); + mln_qixter(const I, window2d) q(p, full3x3); - { - mln_piter(I) p( invs[5].domain() ); + float sse = 0; - for_all(p) + unsigned car = 0; + for_all_2 (p, p_m) + { + //if (p_m.val()) { - for (unsigned i = 0; i < mln_dim(mln_value(I)); ++i) - { - float norm; - { - vec2d_f v; - - v[0] = invs[0](p)[i]; - v[1] = invs[1](p)[i]; - - norm = norm::l2(v); - } + T old = p.val(); - u_xnx(p)[i] = invs[0](p)[i] / norm; - u_yny(p)[i] = invs[1](p)[i] / norm; - } - } - } + if (fabs(w[1]) > activation_threshold) + p.val() *= w[1]; - u_xnx = linear::gaussian_1st_derivative(u_xnx, sigma, 1); - u_yny = linear::gaussian_1st_derivative(u_yny, sigma, 0); + // if (fabs(w[0]) > activation_threshold) + // p.val() += w[0] * p_f.val(); - mln_piter(I) p( invs[5].domain() ); - for_all(p) - { - invs[5](p) = u_xnx(p) + u_yny(p); - } + T p_derivative[derivative_kernels_size]; + + for (unsigned i = 0; i < derivative_kernels_size; ++i) + p_derivative[i] = literal::zero; + + unsigned k = 0; + for_all (q) + { + for (unsigned i = 0; i < derivative_kernels_size; ++i) + { + p_derivative[i] += q.val() * derivative_kernel[i][k]; + } + ++k; + } + + const T& p_x = p_derivative[0]; + const T& p_y = p_derivative[1]; + const T& p_xx = p_derivative[2]; + const T& p_yy = p_derivative[3]; + const T& p_xy = p_derivative[4]; + + const T p_x2 = components_product(p_x, p_x); + const T p_y2 = components_product(p_y, p_y); + const T p_xx2 = components_product(p_xx, p_xx); + const T p_yy2 = components_product(p_yy, p_yy); + const T p_xy2 = components_product(p_xy, p_xy); + + //||∇u||^2 + if (fabs(w[2]) > activation_threshold) + p.val() += w[2] * (p_x2 + p_y2); + + // laplacian + if (fabs(w[3]) > activation_threshold) + p.val() += w[3] * (p_xx + p_yy); + + // tr(H^2(u)) + if (fabs(w[4]) > activation_threshold) + p.val() += w[4] * (p_xx2 + 2 * p_xy2 + p_yy2); + + // (∇u)^T H_u (∇u) + if (fabs(w[5]) > activation_threshold) + p.val() += w[5] * (components_product(p_x2, p_xx) + + 2 * components_product(components_product(p_x, p_y), p_xy) + + components_product(p_y2, p_yy)); + + sse += norm::l2(old - p.val()); + } } + + return sse; } template <template <typename> class I, typename T> void lpde::operator()(I<T>& src, I<bool>& mask) { + extension::adjust_duplicate(src, 1); - data::fill((src | pw::value(mask)).rw(), literal::zero); + const I<T> f(src); - std::vector<I<T> > invs(w.size(), src.domain()); + I<T>& u = src; - I<T>& u_t = src; + float sse = std::numeric_limits<float>::max(); - float r = this->dt / (this->dx * this->dx); - - for (float t = 0; t < this->t_f; t += dt) + float t = 0; + while (t < this->t_f && sse > 0.01 && !std::isnan(sse)) { - compute_diff_invariants(u_t, invs, this->w); + sse = diffuse(u, f, w, mask); - mln_piter(I<T>) p(u_t.domain()); + std::cout << "sse = " << sse << std::endl; - for_all(p) - { - if (mask(p)) - { - T contribution = literal::zero; - - for (unsigned k = 0; k < w.size(); ++k) - { - contribution += this->w[k] * invs[k](p); - } - - u_t(p) += r * contribution; - } - } + t += this->dt; } + + std::cout << "Number of iterations: " << t << std::endl; } void lpde::set(const std::vector<float>& w) diff --git a/milena/mln/inpainting/metric/psnr.hh b/milena/mln/inpainting/metric/psnr.hh index 4998b4a..5dd8fdd 100644 --- a/milena/mln/inpainting/metric/psnr.hh +++ b/milena/mln/inpainting/metric/psnr.hh @@ -14,12 +14,12 @@ namespace mln { namespace metric { - template <typename I> + template <typename I, typename I2> double psnr(const Image& original_, - const Image& altered_) + const Image<I2>& altered_) { const I& original = exact(original_); - const I& altered = exact(altered_); + const I2& altered = exact(altered_); mln_piter(I) p( altered.domain() ); @@ -27,6 +27,8 @@ namespace mln const unsigned dim = mln_dim(mln_value(I)); + unsigned nelements = 0; + for_all(p) { const mln_sum(mln_value(I)) diff = original(p) - altered(p); @@ -36,9 +38,11 @@ namespace mln else for (unsigned i = 0; i < dim; ++i) mse += diff[i] * diff[i]; + + ++nelements; } - mse /= ( altered.ncols() * altered.nrows() * dim); + mse /= ( nelements * dim); const unsigned max = pow(2, mln_nbits(mln_value(I)) / dim) - 1; -- 1.7.2.5

1 0

branch exp/khalimsky updated: olena-2.0-165-g4821f6f
by git＠lrde.epita.fr 30 Oct '12

30 Oct '12

This is an automated email from the git hooks/post-receive script. It was generated because a ref change was pushed to the repository containing the project "Olena, a generic and efficient image processing platform". The branch exp/khalimsky has been updated via 4821f6f79b7795c3e30cf1bf20669d6160bec480 (commit) via 5639d3e99a75a6081b44fdd2218bab8f0d44e5bf (commit) from c328f2420eec8c877803b40f81961c5028f2a585 (commit) Those revisions listed above that are new to this repository have not appeared on any other notification email; so we list those revisions in full, below. - Log ----------------------------------------------------------------- 4821f6f mln/world/k1/immerse.hh: Fix call to an overload in kn namespace. 5639d3e Add more conversions in safe_cast. ----------------------------------------------------------------------- Summary of changes: milena/ChangeLog | 14 +++++ milena/mln/world/k1/immerse.hh | 3 +- milena/mln/world/kn/safe_cast.hh | 108 +++++++++++++++++++++++++++++++++-- milena/tests/world/kn/safe_cast.cc | 106 +++++++++++++++++++++++------------ 4 files changed, 187 insertions(+), 44 deletions(-) hooks/post-receive -- Olena, a generic and efficient image processing platform

1 0

olena-2.0-165-g4821f6f mln/world/k1/immerse.hh: Fix call to an overload in kn namespace.
by Guillaume Lazzara 30 Oct '12

30 Oct '12

--- milena/ChangeLog | 5 +++++ milena/mln/world/k1/immerse.hh | 3 +-- 2 files changed, 6 insertions(+), 2 deletions(-) diff --git a/milena/ChangeLog b/milena/ChangeLog index 56b4097..475fb8e 100644 --- a/milena/ChangeLog +++ b/milena/ChangeLog @@ -1,5 +1,10 @@ 2012-10-30 Guillaume Lazzara <z(a)lrde.epita.fr> + * mln/world/k1/immerse.hh: Fix call to an overload in kn + namespace. + +2012-10-30 Guillaume Lazzara <z(a)lrde.epita.fr> + Add more conversions in safe_cast. * mln/world/kn/safe_cast.hh: Add conversions towards/from diff --git a/milena/mln/world/k1/immerse.hh b/milena/mln/world/k1/immerse.hh index 5ae6cfc..f32339a 100644 --- a/milena/mln/world/k1/immerse.hh +++ b/milena/mln/world/k1/immerse.hh @@ -99,8 +99,7 @@ namespace mln mln_concrete(I) immerse(const Image& ima) { - typedef mln_value(I) V; - return immerse(ima, 1); + return kn::immerse(ima, 1); } -- 1.7.2.5

1 0

olena-2.0-164-g5639d3e Add more conversions in safe_cast.
by Guillaume Lazzara 30 Oct '12

30 Oct '12

* mln/world/kn/safe_cast.hh: Add conversions towards/from unsigned. * tests/world/kn/safe_cast.cc: Add more tests. --- milena/ChangeLog | 9 +++ milena/mln/world/kn/safe_cast.hh | 108 +++++++++++++++++++++++++++++++++-- milena/tests/world/kn/safe_cast.cc | 106 +++++++++++++++++++++++------------ 3 files changed, 181 insertions(+), 42 deletions(-) diff --git a/milena/ChangeLog b/milena/ChangeLog index 39b1c71..56b4097 100644 --- a/milena/ChangeLog +++ b/milena/ChangeLog @@ -1,3 +1,12 @@ +2012-10-30 Guillaume Lazzara <z(a)lrde.epita.fr> + + Add more conversions in safe_cast. + + * mln/world/kn/safe_cast.hh: Add conversions towards/from + unsigned. + + * tests/world/kn/safe_cast.cc: Add more tests. + 2012-10-29 Guillaume Lazzara <z(a)lrde.epita.fr> Improve hqueue used in compute_tree_of_shapes. diff --git a/milena/mln/world/kn/safe_cast.hh b/milena/mln/world/kn/safe_cast.hh index 39309cd..da60265 100644 --- a/milena/mln/world/kn/safe_cast.hh +++ b/milena/mln/world/kn/safe_cast.hh @@ -62,6 +62,8 @@ namespace mln namespace value { + // From int_u<n> + template <unsigned m, unsigned n> void safe_cast_(const int_u<m>& from, intsub<n>& to) { @@ -92,6 +94,14 @@ namespace mln to = from.to_interop(); } + template <unsigned m> + void safe_cast_(const int_u<m>& from, unsigned& to) + { + to = from.to_interop(); + } + + // From interval<int> + void safe_cast_(const interval<int>& from, int& to) { if (!from.is_degenerated()) @@ -99,6 +109,13 @@ namespace mln to = from.first(); } + void safe_cast_(const interval<int>& from, unsigned& to) + { + if (!from.is_degenerated() || from.first() < 0) + std::abort(); + to = from.first(); + } + template <unsigned m> void safe_cast_(const interval<int>& from, int_u<m>& to) { @@ -115,13 +132,7 @@ namespace mln to = from.first(); } - template <unsigned n, unsigned m> - void safe_cast_(const interval<intsub<n> >& from, int_u<m>& to) - { - if (!from.is_degenerated()) - std::abort(); - to = intsub<n>(from.first()); - } + // From interval< int_u<m> > template <unsigned m> void safe_cast_(const interval<int_u<m> >& from, int_u<m>& to) @@ -147,6 +158,24 @@ namespace mln to = from.first().to_interop(); } + template <unsigned m> + void safe_cast_(const interval<int_u<m> >& from, unsigned& to) + { + if (!from.is_degenerated()) + std::abort(); + to = from.first().to_interop(); + } + + // From interval<intsub<n> > + + template <unsigned n, unsigned m> + void safe_cast_(const interval<intsub<n> >& from, int_u<m>& to) + { + if (!from.is_degenerated()) + std::abort(); + to = intsub<n>(from.first()); + } + template <unsigned n> void safe_cast_(const interval<intsub<n> >& from, int& to) { @@ -156,6 +185,14 @@ namespace mln } template <unsigned n> + void safe_cast_(const interval<intsub<n> >& from, unsigned& to) + { + if (!from.is_degenerated() || from.first() < 0) + std::abort(); + to = from.first(); + } + + template <unsigned n> void safe_cast_(const interval<intsub<n> >& from, intsub<n>& to) { if (!from.is_degenerated()) @@ -163,6 +200,8 @@ namespace mln to = from.first(); } + // From int + template <unsigned n> void safe_cast_(const int& from, interval<intsub<n> >& to) { @@ -174,6 +213,13 @@ namespace mln to = interval<int>(from); } + void safe_cast_(const int& from, unsigned& to) + { + if (from < 0) + std::abort(); + to = from; + } + template <unsigned m> void safe_cast_(const int& from, int_u<m>& to) { @@ -186,6 +232,7 @@ namespace mln to = from; } + // From intsub<n> template <unsigned n> void safe_cast_(const intsub<n>& from, intsub<2*n>& to) @@ -211,6 +258,14 @@ namespace mln to = from; } + template <unsigned n> + void safe_cast_(const intsub<n>& from, unsigned& to) + { + if (from < 0) + std::abort(); + to = from; + } + template <unsigned n, unsigned m> void safe_cast_(const intsub<n>& from, interval<int_u<m> >& to) { @@ -229,6 +284,45 @@ namespace mln to = interval<intsub<n> >(from); } + // From unsigned + + template <unsigned n> + void safe_cast_(const unsigned& from, interval<intsub<n> >& to) + { + // FIXME: check if unsigned value fits in intsub. + to = interval<intsub<n> >((int)from); + } + + void safe_cast_(const unsigned& from, interval<int>& to) + { + if (from > static_cast<unsigned>(mln_max(int))) + std::abort(); + to = interval<int>(from); + } + + void safe_cast_(const unsigned& from, int& to) + { + if (from > static_cast<unsigned>(mln_max(int))) + std::abort(); + to = from; + } + + template <unsigned m> + void safe_cast_(const unsigned& from, int_u<m>& to) + { + if (from > mln_max(int_u<m>)) + std::abort(); + to = from; + } + + template <unsigned n> + void safe_cast_(const unsigned& from, intsub<n>& to) + { + // FIXME: check if unsigned value fits in intsub. + to = (int)from; + } + + } // end of namespace mln::value diff --git a/milena/tests/world/kn/safe_cast.cc b/milena/tests/world/kn/safe_cast.cc index 7c5be20..135fc1a 100644 --- a/milena/tests/world/kn/safe_cast.cc +++ b/milena/tests/world/kn/safe_cast.cc @@ -36,46 +36,53 @@ int main() using namespace mln::value; using namespace mln::world; - // int -> int_u<8> + // unsigned -> int_u<8> { - int i = 2; + unsigned i = 2; int_u<8> j = kn::safe_cast_to<int_u<8> >(i); mln_assertion(j == 2); } - // int -> intsub<2> + // unsigned -> intsub<2> { - int i = 2; + unsigned i = 2; intsub<2> j = kn::safe_cast_to<intsub<2> >(i); mln_assertion(j == 2); } + // unsigned -> interval<int> + { + unsigned i = 2; + interval<int> j = kn::safe_cast_to<interval<int> >(i); + mln_assertion(j.is_degenerated() && j.first() == 2); + } - // int_u<8> -> int + // unsigned -> interval<int_u<8> > { - int_u<8> i = 2; - int j = kn::safe_cast_to<int>(i); - mln_assertion(j == 2); + unsigned i = 2; + interval<int_u<8> > j = kn::safe_cast_to<interval<int_u<8> > >(i); + mln_assertion(j.is_degenerated() && j.first() == 2); } - // int_u<8> -> intsub<2> + // unsigned -> interval<intsub<2> > { - int_u<8> i = 2; - intsub<2> j = kn::safe_cast_to<intsub<2> >(i); - mln_assertion(j == 2); + unsigned i = 2; + interval<intsub<2> > j = kn::safe_cast_to<interval<intsub<2> > >(i); + mln_assertion(j.is_degenerated() && j.first() == 2); } - // intsub<2> -> int + + // int -> int_u<8> { - intsub<2> i = 2; - int j = kn::safe_cast_to<int>(i); + int i = 2; + int_u<8> j = kn::safe_cast_to<int_u<8> >(i); mln_assertion(j == 2); } - // intsub<2> -> int_u<8> + // int -> intsub<2> { - intsub<2> i = 2; - int_u<8> j = kn::safe_cast_to<int_u<8> >(i); + int i = 2; + intsub<2> j = kn::safe_cast_to<intsub<2> >(i); mln_assertion(j == 2); } @@ -86,25 +93,32 @@ int main() mln_assertion(j.is_degenerated() && j.first() == 2); } - // int_u -> interval<int> + // int -> interval<int_u<8> > { - int_u<8> i = 2; - interval<int> j = kn::safe_cast_to<interval<int> >(i); + int i = 2; + interval<int_u<8> > j = kn::safe_cast_to<interval<int_u<8> > >(i); mln_assertion(j.is_degenerated() && j.first() == 2); } - // int_u -> interval<int> + // int -> interval<intsub<2> > { - intsub<2> i = 2; - interval<int> j = kn::safe_cast_to<interval<int> >(i); + int i = 2; + interval<intsub<2> > j = kn::safe_cast_to<interval<intsub<2> > >(i); mln_assertion(j.is_degenerated() && j.first() == 2); } - // int -> interval<int_u<8> > + // int_u<8> -> int { - int i = 2; - interval<int_u<8> > j = kn::safe_cast_to<interval<int_u<8> > >(i); - mln_assertion(j.is_degenerated() && j.first() == 2); + int_u<8> i = 2; + int j = kn::safe_cast_to<int>(i); + mln_assertion(j == 2); + } + + // int_u<8> -> intsub<2> + { + int_u<8> i = 2; + intsub<2> j = kn::safe_cast_to<intsub<2> >(i); + mln_assertion(j == 2); } // int_u<8> -> interval<int_u<8> > @@ -114,18 +128,17 @@ int main() mln_assertion(j.is_degenerated() && j.first() == 2); } - // intsub<2> -> interval<int_u<8> > + // int_u<8> -> interval<int> { - intsub<2> i = 2; - interval<int_u<8> > j = kn::safe_cast_to<interval<int_u<8> > >(i); + int_u<8> i = 2; + interval<int> j = kn::safe_cast_to<interval<int> >(i); mln_assertion(j.is_degenerated() && j.first() == 2); } - - // int -> interval<intsub<2> > + // int_u<8> -> interval<int> { - int i = 2; - interval<intsub<2> > j = kn::safe_cast_to<interval<intsub<2> > >(i); + intsub<2> i = 2; + interval<int> j = kn::safe_cast_to<interval<int> >(i); mln_assertion(j.is_degenerated() && j.first() == 2); } @@ -136,6 +149,27 @@ int main() mln_assertion(j.is_degenerated() && j.first() == 2); } + // intsub<2> -> int + { + intsub<2> i = 2; + int j = kn::safe_cast_to<int>(i); + mln_assertion(j == 2); + } + + // intsub<2> -> int_u<8> + { + intsub<2> i = 2; + int_u<8> j = kn::safe_cast_to<int_u<8> >(i); + mln_assertion(j == 2); + } + + // intsub<2> -> interval<int_u<8> > + { + intsub<2> i = 2; + interval<int_u<8> > j = kn::safe_cast_to<interval<int_u<8> > >(i); + mln_assertion(j.is_degenerated() && j.first() == 2); + } + // intsub<2> -> interval<intsub<2> > { intsub<2> i = 2; @@ -206,4 +240,6 @@ int main() mln_assertion(j == 2); } + + } -- 1.7.2.5

1 0

branch exp/khalimsky updated: olena-2.0-163-gc328f24
by git＠lrde.epita.fr 29 Oct '12

29 Oct '12

This is an automated email from the git hooks/post-receive script. It was generated because a ref change was pushed to the repository containing the project "Olena, a generic and efficient image processing platform". The branch exp/khalimsky has been updated via c328f2420eec8c877803b40f81961c5028f2a585 (commit) from a70e6db18693ace17288af625c7ee52d9f59f580 (commit) Those revisions listed above that are new to this repository have not appeared on any other notification email; so we list those revisions in full, below. - Log ----------------------------------------------------------------- c328f24 Improve hqueue used in compute_tree_of_shapes. ----------------------------------------------------------------------- Summary of changes: milena/ChangeLog | 12 ++ milena/mln/util/hqueue.hh | 163 ------------------- milena/mln/world/kn/compute_tree_of_shapes.hh | 53 ++++--- milena/mln/world/kn/internal/hqueue.hh | 165 ++++++++++++++++++++ .../kn/internal/{domain_from_k0.hh => queue.hh} | 113 +++++++++----- 5 files changed, 277 insertions(+), 229 deletions(-) delete mode 100644 milena/mln/util/hqueue.hh create mode 100644 milena/mln/world/kn/internal/hqueue.hh copy milena/mln/world/kn/internal/{domain_from_k0.hh => queue.hh} (53%) hooks/post-receive -- Olena, a generic and efficient image processing platform

1 0

olena-2.0-163-gc328f24 Improve hqueue used in compute_tree_of_shapes.
by Guillaume Lazzara 29 Oct '12

29 Oct '12

* mln/util/hqueue.hh: Remove. * mln/world/kn/internal/hqueue.hh, * mln/world/kn/internal/queue.hh: New. * mln/world/kn/compute_tree_of_shapes.hh: Update use of hqueue. Set l_inf. --- milena/ChangeLog | 12 ++ milena/mln/util/hqueue.hh | 163 ------------------- milena/mln/world/kn/compute_tree_of_shapes.hh | 53 ++++--- milena/mln/world/kn/internal/hqueue.hh | 165 ++++++++++++++++++++ .../kn/internal/{domain_from_k0.hh => queue.hh} | 113 +++++++++----- 5 files changed, 277 insertions(+), 229 deletions(-) delete mode 100644 milena/mln/util/hqueue.hh create mode 100644 milena/mln/world/kn/internal/hqueue.hh copy milena/mln/world/kn/internal/{domain_from_k0.hh => queue.hh} (53%) diff --git a/milena/ChangeLog b/milena/ChangeLog index e1d6e5f..39b1c71 100644 --- a/milena/ChangeLog +++ b/milena/ChangeLog @@ -1,5 +1,17 @@ 2012-10-29 Guillaume Lazzara <z(a)lrde.epita.fr> + Improve hqueue used in compute_tree_of_shapes. + + * mln/util/hqueue.hh: Remove. + + * mln/world/kn/internal/hqueue.hh, + * mln/world/kn/internal/queue.hh: New. + + * mln/world/kn/compute_tree_of_shapes.hh: Update use of + hqueue. Set l_inf. + +2012-10-29 Guillaume Lazzara <z(a)lrde.epita.fr> + * mln/world/kn/compute_tree_of_shapes.hh: Make p_inf an argument to this routine. diff --git a/milena/mln/util/hqueue.hh b/milena/mln/util/hqueue.hh deleted file mode 100644 index 9485827..0000000 --- a/milena/mln/util/hqueue.hh +++ /dev/null @@ -1,163 +0,0 @@ -// Copyright (C) 2012 EPITA Research and Development Laboratory (LRDE) -// -// This file is part of Olena. -// -// Olena is free software: you can redistribute it and/or modify it under -// the terms of the GNU General Public License as published by the Free -// Software Foundation, version 2 of the License. -// -// Olena 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 Olena. If not, see <http://www.gnu.org/licenses/>. -// -// As a special exception, you may use this file as part of a free -// software project 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_UTIL_HQUEUE_HH -# define MLN_UTIL_HQUEUE_HH - -/// \file -/// \brief Class for hierarchical queues. - - -# include <cstdlib> -# include <iostream> -# include <vector> -# include <queue> - - -namespace mln -{ - - namespace util - { - - /// \brief Class for hierarchical queues. - template <typename T, typename P> - class hqueue - { - public: - hqueue(); - hqueue(const value::interval& inter); - hqueue(const P& first, const P& last); - - unsigned size() const; - - bool is_empty_at(const P& bucket) const; - bool is_not_empty_at(const P& bucket) const; - -// const std::queue<T>& operator[](const P& bucket) const; - - void push(const T& t, const P& bucket); - T pop(const P& bucket); - - private: - std::vector<std::queue<T> > v_; - unsigned head_; - value::interval inter_; - }; - - -# ifndef MLN_INCLUDE_ONLY - - - template <typename T, typename P> - hqueue<T,P>::hqueue() - { - head_ = 0; - } - - template <typename T, typename P> - hqueue<T,P>::hqueue(const value::interval& inter) - { - inter_ = inter; - v_.resize(inter.nelements()); - head_ = 0; - } - - template <typename T, typename P> - hqueue<T,P>::hqueue(const P& first, const P& last) - { - inter_ = value::interval(first, last); - v_.resize(inter_.nelements()); - head_ = 0; - } - - template <typename T, typename P> - unsigned - hqueue<T,P>::size() const - { - mln_precondition(head_ <= v_.size()); - return v_.size() - head_; - } - - template <typename T, typename P> - bool - hqueue<T,P>::is_empty_at(const P& bucket) const - { - return v_[inter_.index_of(bucket)].empty() == 0; - } - - template <typename T, typename P> - bool - hqueue<T,P>::is_not_empty_at(const P& bucket) const - { - return ! is_empty_at(bucket); - } - - // template <typename T, typename P> - // const std::queue<T>& - // hqueue<T,P>::operator[](const P& i) const - // { - // mln_precondition(i < this->size()); - // return v_[head_ + i]; - // } - - template <typename T, typename P> - void - hqueue<T,P>::push(const T& t, const P& bucket) - { - v_[inter_.index_of(bucket)].push(t); - } - - template <typename T, typename P> - T - hqueue<T,P>::pop(const P& bucket) - { - mln_precondition(!is_empty_at(bucket)); - mln_precondition(bucket < v_.size()); - T front = v_[bucket].front(); - v_[bucket].pop(); - return front; - } - - - template <typename T, typename P> - std::ostream& - operator<<(std::ostream& ostr, const hqueue<T,P>& q) - { - unsigned n = q.size(); - ostr << '('; - for (unsigned i = 0; i < n; ++i) - ostr << q.v_[i] << (i + 1 == n ? "" : ", "); - return ostr << ')'; - } - - -# endif // ! MLN_INCLUDE_ONLY - - } // end of namespace mln::util - -} // end of namespace mln - -#endif // ! MLN_UTIL_HQUEUE_HH diff --git a/milena/mln/world/kn/compute_tree_of_shapes.hh b/milena/mln/world/kn/compute_tree_of_shapes.hh index 795eceb..d6a5984 100644 --- a/milena/mln/world/kn/compute_tree_of_shapes.hh +++ b/milena/mln/world/kn/compute_tree_of_shapes.hh @@ -41,7 +41,7 @@ # include <mln/value/interval.hh> # include <mln/value/is_degenerated.hh> -# include <mln/util/hqueue.hh> +# include <mln/world/kn/internal/hqueue.hh> # include <mln/util/tree_of_shapes.hh> # include <mln/world/kn/is_2_face.hh> @@ -70,13 +70,13 @@ namespace mln template <typename I, typename IV> util::tree_of_shapes compute_tree_of_shapes(const Image& F, const value::interval<IV>& inter, - const mln_site(I)& p_inf); + const mln_site(I)& p_infty); /// \overload template <typename I, typename IV, typename U> util::tree_of_shapes compute_tree_of_shapes(const Image& F, const value::interval<IV>& inter, - const mln_site(I)& p_inf, const U& value); + const mln_site(I)& p_infty, const U& value); # ifndef MLN_INCLUDE_ONLY @@ -95,18 +95,18 @@ namespace mln typedef mln_ch_value(I,P) T; typedef mln_ch_value(I,unsigned) U; typedef std::vector Array_P; - typedef util::hqueue<P,EV> q_type; + typedef world::kn::internal::hqueue<P,EV> q_type; compute_tree_of_shapes_t(); util::tree_of_shapes operator()(const I& F_, const value::interval<IV>& inter, - const mln_site(I)& p_inf); + const mln_site(I)& p_infty); template <typename L> util::tree_of_shapes operator()(const I& F_, const value::interval<IV>& inter, - const mln_site(I)& p_inf, + const mln_site(I)& p_infty, const L& l_inf); void do_union(P p_, P r_, T& zpar, U& rank, U& last); @@ -134,7 +134,7 @@ namespace mln mln_equiv(V) lcur; P undef; - P p_inf_; + P p_infty_; unsigned N; box2d D; @@ -254,7 +254,7 @@ namespace mln for (; l_ < inter_.last(); value::inc(l_)) { - if (q.is_not_empty_at(l_)) + if (!q.is_empty_at(l_)) { found = true; return l_; @@ -263,7 +263,7 @@ namespace mln // Avoid overflow on last element. if (l_ == inter_.last()) - if (q.is_not_empty_at(l_)) + if (!q.is_empty_at(l_)) { found = true; return l_; @@ -280,7 +280,7 @@ namespace mln EV l_ = lcur; for (; l_ > inter_.first(); value::dec(l_)) - if (q.is_not_empty_at(l_)) + if (!q.is_empty_at(l_)) { found = true; return l_; @@ -288,7 +288,7 @@ namespace mln // Avoid overflow on first element. if (l_ == inter_.first()) - if (q.is_not_empty_at(l_)) + if (!q.is_empty_at(l_)) { found = true; return l_; @@ -382,9 +382,8 @@ namespace mln // p is in queue if p is 'deja_vu' but not 'done' } unsigned i = 0; - lcur = safe_cast_to<EV>(F(p_inf_)); // the start level is the one of root - priority_push(q, p_inf_, F); // realize push(q[lcur], p_inf_) - deja_vu(p_inf_) = true; + priority_push(q, p_infty_, F); // realize push(q[lcur], p_infty_) + deja_vu(p_infty_) = true; do { P p = priority_pop(q); @@ -479,15 +478,16 @@ namespace mln util::tree_of_shapes compute_tree_of_shapes_t<I,IV>::operator()(const I& F, const value::interval<IV>& inter, - const mln_site(I)& p_inf) + const mln_site(I)& p_infty) { mln_precondition(F.is_valid()); - mln_precondition(value::is_degenerated(F(p_inf))); + mln_precondition(value::is_degenerated(F(p_infty))); N = F.nsites(); D = F.domain(); inter_ = inter; - p_inf_ = p_inf; + p_infty_ = p_infty; + lcur = safe_cast_to<EV>(F(p_infty_)); // the start level is the one of root util::tree_of_shapes t; @@ -506,16 +506,17 @@ namespace mln util::tree_of_shapes compute_tree_of_shapes_t<I,IV>::operator()(const I& F, const value::interval<IV>& inter, - const mln_site(I)& p_inf, + const mln_site(I)& p_infty, const L& l_inf) { mln_precondition(F.is_valid()); - mln_precondition(F(p_inf).has(l_inf)); + mln_precondition(F(p_infty).has(l_inf)); N = F.nsites(); D = F.domain(); inter_ = inter; - p_inf_ = p_inf; + p_infty_ = p_infty; + lcur = safe_cast_to<EV>(l_inf); // the start level is the one of root util::tree_of_shapes t; @@ -535,16 +536,16 @@ namespace mln template <typename I, typename IV> util::tree_of_shapes compute_tree_of_shapes(const Image& F, const value::interval<IV>& inter, - const mln_site(I)& p_inf) + const mln_site(I)& p_infty) { trace::entering("mln::world::kn::compute_tree_of_shapes"); mln_precondition(exact(F).is_valid()); typedef mln_value(I) V; mlc_is_a(V, value::interval)::check(); - mln_precondition(value::is_degenerated(exact(F)(p_inf))); + mln_precondition(value::is_degenerated(exact(F)(p_infty))); util::tree_of_shapes - t = internal::compute_tree_of_shapes_t<I,IV>()(exact(F), inter, p_inf); + t = internal::compute_tree_of_shapes_t<I,IV>()(exact(F), inter, p_infty); trace::exiting("mln::world::kn::compute_tree_of_shapes"); return t; @@ -553,16 +554,16 @@ namespace mln template <typename I, typename IV, typename U> util::tree_of_shapes compute_tree_of_shapes(const Image& F, const value::interval<IV>& inter, - const mln_site(I)& p_inf, const U& l_inf) + const mln_site(I)& p_infty, const U& l_inf) { trace::entering("mln::world::kn::compute_tree_of_shapes"); mln_precondition(exact(F).is_valid()); typedef mln_value(I) V; mlc_is_a(V, value::interval)::check(); - mln_precondition(F(p_inf).has(l_inf)); + mln_precondition(F(p_infty).has(l_inf)); util::tree_of_shapes - t = internal::compute_tree_of_shapes_t<I,IV>()(exact(F), inter, p_inf, l_inf); + t = internal::compute_tree_of_shapes_t<I,IV>()(exact(F), inter, p_infty, l_inf); trace::exiting("mln::world::kn::compute_tree_of_shapes"); return t; diff --git a/milena/mln/world/kn/internal/hqueue.hh b/milena/mln/world/kn/internal/hqueue.hh new file mode 100644 index 0000000..fe29376 --- /dev/null +++ b/milena/mln/world/kn/internal/hqueue.hh @@ -0,0 +1,165 @@ +// Copyright (C) 2012 EPITA Research and Development Laboratory (LRDE) +// +// This file is part of Olena. +// +// Olena is free software: you can redistribute it and/or modify it under +// the terms of the GNU General Public License as published by the Free +// Software Foundation, version 2 of the License. +// +// Olena 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 Olena. If not, see <http://www.gnu.org/licenses/>. +// +// As a special exception, you may use this file as part of a free +// software project 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_WORLD_KN_INTERNAL_HQUEUE_HH +# define MLN_WORLD_KN_INTERNAL_HQUEUE_HH + +/// \file +/// \brief Class for hierarchical queues. + + +# include <iostream> +# include <vector> +# include <mln/world/kn/internal/queue.hh> + +namespace mln +{ + + namespace world + { + + namespace kn + { + + namespace internal + { + + /// \internal + /// \brief Class for hierarchical queues. + template <typename T, typename P> + class hqueue + { + public: + hqueue(); + hqueue(const value::interval& inter); + hqueue(const P& first, const P& last); + + unsigned nelements() const; + + bool is_empty() const; + bool is_empty_at(const P& bucket) const; + + void push(const T& t, const P& bucket); + T pop(const P& bucket); + + // FIXME: add some reserve strategies... + + private: + std::vector< internal::queue_<T> > v_; + value::interval inter_; + unsigned n_; + }; + + +# ifndef MLN_INCLUDE_ONLY + + + template <typename T, typename P> + hqueue<T,P>::hqueue() + { + n_ = 0; + } + + template <typename T, typename P> + hqueue<T,P>::hqueue(const value::interval& inter) + { + v_.resize(inter.nelements()); + inter_ = inter; + n_ = 0; + } + + template <typename T, typename P> + hqueue<T,P>::hqueue(const P& first, const P& last) + { + v_.resize(inter_.nelements()); + inter_ = value::interval(first, last); + n_ = 0; + } + + template <typename T, typename P> + unsigned + hqueue<T,P>::nelements() const + { + return n_; + } + + template <typename T, typename P> + bool + hqueue<T,P>::is_empty_at(const P& bucket) const + { + unsigned i = inter_.index_of(bucket); + mln_precondition(i < v_.size()); + return v_[i].is_empty(); + } + + template <typename T, typename P> + bool + hqueue<T,P>::is_empty() const + { + return n_ == 0; + } + + template <typename T, typename P> + void + hqueue<T,P>::push(const T& t, const P& bucket) + { + unsigned i = inter_.index_of(bucket); + mln_precondition(i < v_.size()); + v_[i].push(t); + } + + template <typename T, typename P> + T + hqueue<T,P>::pop(const P& bucket) + { + mln_precondition(! is_empty_at(bucket)); + unsigned i = inter_.index_of(bucket); + mln_precondition(i < v_.size()); + return v_[i].pop(); + } + + // template <typename T, typename P> + // std::ostream& + // operator<<(std::ostream& ostr, const hqueue<T,P>& q) + // { + // unsigned n = q.size(); + // ostr << '('; + // for (unsigned i = 0; i < n; ++i) + // ostr << q.v_[i] << (i + 1 == n ? "" : ", "); + // return ostr << ')'; + // } + + +# endif // ! MLN_INCLUDE_ONLY + + } // end of namespace mln::world::kn::internal + + } // end of namespace mln::world::kn + + } // end of namespace mln::world + +} // end of namespace mln + +#endif // ! MLN_WORLD_KN_INTERNAL_HQUEUE_HH diff --git a/milena/mln/world/kn/internal/domain_from_k0.hh b/milena/mln/world/kn/internal/queue.hh similarity index 53% copy from milena/mln/world/kn/internal/domain_from_k0.hh copy to milena/mln/world/kn/internal/queue.hh index 1950280..6a3fbe5 100644 --- a/milena/mln/world/kn/internal/domain_from_k0.hh +++ b/milena/mln/world/kn/internal/queue.hh @@ -23,16 +23,16 @@ // exception does not however invalidate any other reasons why the // executable file might be covered by the GNU General Public License. +#ifndef MLN_WORLD_KN_INTERNAL_QUEUE_HH +# define MLN_WORLD_KN_INTERNAL_QUEUE_HH + /// \file -/// -/// \brief Return the equivalent domain in Kn from a domain in -/// K0. +/// \brief Class for hierarchical queues. + + +# include <vector> -#ifndef MLN_WORLD_KN_DOMAIN_FROM_K0_HH -# define MLN_WORLD_KN_DOMAIN_FROM_K0_HH -# include <mln/core/concept/box.hh> -# include <mln/world/kn/internal/immerse_point.hh> namespace mln { @@ -46,51 +46,86 @@ namespace mln namespace internal { - /// \brief Return the equivalent domain in Kn from a domain in - /// K0. - template <typename B> - B - domain_from_k0(const Box& b, const unsigned n, - unsigned inner_border_thickness); + /// \internal + /// \brief Classical queue structure. + template <typename T> + struct queue_ + { + queue_(); + + void reserve(unsigned n); + + unsigned nelements() const; + bool is_empty() const; - /// \overload - /// \p inner_border_thickness is set to 0. - template <typename B> - B - domain_from_k0(const Box& b, const unsigned n); + const T& operator[](unsigned i) const; + + void push(const T& t); + T pop(); + + std::vector<T> v_; + unsigned head_; + }; # ifndef MLN_INCLUDE_ONLY - template <typename B> - B - domain_from_k0(const Box& b_, const unsigned n, - unsigned inner_border_thickness) + template <typename T> + queue_<T>::queue_() + { + head_ = 0; + } + + template <typename T> + void + queue_<T>::reserve(unsigned n) + { + v_.reserve(n); + } + + template <typename T> + unsigned + queue_<T>::nelements() const + { + mln_precondition(head_ >= v_.size()); + return v_.size() - head_; + } + + template <typename T> + bool + queue_<T>::is_empty() const + { + return head_ == v_.size(); + } + + template <typename T> + const T& + queue_<T>::operator[](unsigned i) const { - mln_precondition(exact(b_).is_valid()); - const B& b = exact(b_); - - mln_deduce(B, site, delta) one; - one.set_all(1); - B bout = B(immerse_point(b.pmin(), n, inner_border_thickness) - - (inner_border_thickness * 2 * one) - one, - immerse_point(b.pmax(), n, inner_border_thickness) - + (std::pow(2,n) - 1) * one + (inner_border_thickness * 2 * one)); - return bout; + mln_precondition(head_ + i < v_.size()); + return v_[head_ + i]; } + template <typename T> + void + queue_<T>::push(const T& t) + { + v_.push_back(t); + } - template <typename B> - B - domain_from_k0(const Box& b, const unsigned n) + template <typename T> + T + queue_<T>::pop() { - return domain_from_K0(b, n, 0); + mln_precondition(! is_empty()); + mln_precondition(head_ < v_.size()); + return v_[head_++]; } # endif // ! MLN_INCLUDE_ONLY - } // end of namespace mln::work::kn::internal + } // end of namespace mln::world::kn::internal } // end of namespace mln::world::kn @@ -98,6 +133,4 @@ namespace mln } // end of namespace mln -#endif // ! MLN_WORLD_KN_DOMAIN_FROM_K0_HH - - +#endif // ! MLN_WORLD_KN_INTERNAL_QUEUE_HH -- 1.7.2.5

1 0

branch exp/khalimsky updated: olena-2.0-162-ga70e6db
by git＠lrde.epita.fr 29 Oct '12

29 Oct '12

This is an automated email from the git hooks/post-receive script. It was generated because a ref change was pushed to the repository containing the project "Olena, a generic and efficient image processing platform". The branch exp/khalimsky has been updated via a70e6db18693ace17288af625c7ee52d9f59f580 (commit) from 181e00223e14c9cfe3e3d947617c62256eb1c6f4 (commit) Those revisions listed above that are new to this repository have not appeared on any other notification email; so we list those revisions in full, below. - Log ----------------------------------------------------------------- a70e6db mln/world/kn/compute_tree_of_shapes.hh: Make p_inf an argument to this routine. ----------------------------------------------------------------------- Summary of changes: milena/ChangeLog | 5 + milena/mln/world/kn/compute_tree_of_shapes.hh | 155 +++++++++++++++++-------- 2 files changed, 114 insertions(+), 46 deletions(-) hooks/post-receive -- Olena, a generic and efficient image processing platform

1 0

olena-2.0-162-ga70e6db mln/world/kn/compute_tree_of_shapes.hh: Make p_inf an argument to this routine.
by Guillaume Lazzara 29 Oct '12

29 Oct '12

--- milena/ChangeLog | 5 + milena/mln/world/kn/compute_tree_of_shapes.hh | 155 +++++++++++++++++-------- 2 files changed, 114 insertions(+), 46 deletions(-) diff --git a/milena/ChangeLog b/milena/ChangeLog index b0e2312..e1d6e5f 100644 --- a/milena/ChangeLog +++ b/milena/ChangeLog @@ -1,5 +1,10 @@ 2012-10-29 Guillaume Lazzara <z(a)lrde.epita.fr> + * mln/world/kn/compute_tree_of_shapes.hh: Make p_inf an argument + to this routine. + +2012-10-29 Guillaume Lazzara <z(a)lrde.epita.fr> + Rename methods in world::kn::hqueue. * mln/world/kn/hqueue.hh: Rename is_empty and is_not_empty to diff --git a/milena/mln/world/kn/compute_tree_of_shapes.hh b/milena/mln/world/kn/compute_tree_of_shapes.hh index 1778073..795eceb 100644 --- a/milena/mln/world/kn/compute_tree_of_shapes.hh +++ b/milena/mln/world/kn/compute_tree_of_shapes.hh @@ -39,6 +39,7 @@ # include <mln/value/dec.hh> # include <mln/value/inc.hh> # include <mln/value/interval.hh> +# include <mln/value/is_degenerated.hh> # include <mln/util/hqueue.hh> # include <mln/util/tree_of_shapes.hh> @@ -66,9 +67,16 @@ namespace mln \param[in] inter Interval of the possible values in \p F. */ - template <typename I> + template <typename I, typename IV> util::tree_of_shapes - compute_tree_of_shapes(const Image& F, const mln_value(I)& inter); + compute_tree_of_shapes(const Image& F, const value::interval<IV>& inter, + const mln_site(I)& p_inf); + + /// \overload + template <typename I, typename IV, typename U> + util::tree_of_shapes + compute_tree_of_shapes(const Image& F, const value::interval<IV>& inter, + const mln_site(I)& p_inf, const U& value); # ifndef MLN_INCLUDE_ONLY @@ -76,7 +84,7 @@ namespace mln namespace internal { - template <typename I> + template <typename I, typename IV> struct compute_tree_of_shapes_t { typedef mln_value(I) V; @@ -92,7 +100,14 @@ namespace mln compute_tree_of_shapes_t(); util::tree_of_shapes operator()(const I& F_, - const mln_value(I)& inter); + const value::interval<IV>& inter, + const mln_site(I)& p_inf); + + template <typename L> + util::tree_of_shapes operator()(const I& F_, + const value::interval<IV>& inter, + const mln_site(I)& p_inf, + const L& l_inf); void do_union(P p_, P r_, T& zpar, U& rank, U& last); @@ -119,17 +134,17 @@ namespace mln mln_equiv(V) lcur; P undef; - P p_0; + P p_inf_; unsigned N; box2d D; - mln_value(I) inter_; + value::interval<IV> inter_; }; - template <typename I> + template <typename I, typename IV> void - compute_tree_of_shapes_t::do_union(P p_, P r_, + compute_tree_of_shapes_t<I,IV>::do_union(P p_, P r_, T& zpar, U& rank, U& last) // modify zpar, rank, and last { @@ -152,9 +167,9 @@ namespace mln } - template <typename I> - typename compute_tree_of_shapes_t::P - compute_tree_of_shapes_t::find_root(T& zpar, P x) + template <typename I, typename IV> + typename compute_tree_of_shapes_t<I,IV>::P + compute_tree_of_shapes_t<I,IV>::find_root(T& zpar, P x) // modify zpar { if (zpar(x) == x) @@ -165,9 +180,9 @@ namespace mln } } - template <typename I> - typename compute_tree_of_shapes_t::T - compute_tree_of_shapes_t::union_find(const Array_P& R, + template <typename I, typename IV> + typename compute_tree_of_shapes_t<I,IV>::T + compute_tree_of_shapes_t<I,IV>::union_find(const Array_P& R, display& dsp) // with balancing { @@ -212,9 +227,9 @@ namespace mln } - template <typename I> + template <typename I, typename IV> void - compute_tree_of_shapes_t::priority_push(q_type& q, const P& p, const I& F) + compute_tree_of_shapes_t<I,IV>::priority_push(q_type& q, const P& p, const I& F) // modify q { EV @@ -231,9 +246,9 @@ namespace mln } - template <typename I> - typename compute_tree_of_shapes_t::EV - compute_tree_of_shapes_t::upper_level_next_to_lcur(q_type& q, bool& found) + template <typename I, typename IV> + typename compute_tree_of_shapes_t<I,IV>::EV + compute_tree_of_shapes_t<I,IV>::upper_level_next_to_lcur(q_type& q, bool& found) { EV l_ = lcur; @@ -258,9 +273,9 @@ namespace mln return EV(); } - template <typename I> - typename compute_tree_of_shapes_t::EV - compute_tree_of_shapes_t::lower_level_next_to_lcur(q_type& q, bool& found) + template <typename I, typename IV> + typename compute_tree_of_shapes_t<I,IV>::EV + compute_tree_of_shapes_t<I,IV>::lower_level_next_to_lcur(q_type& q, bool& found) { EV l_ = lcur; @@ -284,9 +299,9 @@ namespace mln } - template <typename I> - typename compute_tree_of_shapes_t::EV - compute_tree_of_shapes_t::level_next_to_lcur(q_type& q) + template <typename I, typename IV> + typename compute_tree_of_shapes_t<I,IV>::EV + compute_tree_of_shapes_t<I,IV>::level_next_to_lcur(q_type& q) { EV l_; bool found; @@ -321,9 +336,9 @@ namespace mln } - template <typename I> - typename compute_tree_of_shapes_t::P - compute_tree_of_shapes_t::priority_pop(q_type& q) + template <typename I, typename IV> + typename compute_tree_of_shapes_t<I,IV>::P + compute_tree_of_shapes_t<I,IV>::priority_pop(q_type& q) // modify q, and sometimes l { if (q.is_empty_at(lcur)) @@ -339,9 +354,9 @@ namespace mln - template <typename I> + template <typename I, typename IV> void - compute_tree_of_shapes_t::sort(const Image& F_, + compute_tree_of_shapes_t<I,IV>::sort(const Image& F_, util::tree_of_shapes& t, display& dsp) { trace::entering("mln::world::kn::sort"); @@ -367,9 +382,9 @@ namespace mln // p is in queue if p is 'deja_vu' but not 'done' } unsigned i = 0; - lcur = safe_cast_to<EV>(F(p_0)); // the start level is the one of root - priority_push(q, p_0, F); // realize push(q[lcur], p_0) - deja_vu(p_0) = true; + lcur = safe_cast_to<EV>(F(p_inf_)); // the start level is the one of root + priority_push(q, p_inf_, F); // realize push(q[lcur], p_inf_) + deja_vu(p_inf_) = true; do { P p = priority_pop(q); @@ -398,9 +413,9 @@ namespace mln } - template <typename I> + template <typename I, typename IV> void - compute_tree_of_shapes_t::canonicalize_tree(util::tree_of_shapes& t) + compute_tree_of_shapes_t<I,IV>::canonicalize_tree(util::tree_of_shapes& t) // modify parent { const I& Fb = t.Fb; @@ -454,23 +469,53 @@ namespace mln } - template <typename I> - compute_tree_of_shapes_t::compute_tree_of_shapes_t() - : undef(-1, -1), p_0(-1, -1) + template <typename I, typename IV> + compute_tree_of_shapes_t<I,IV>::compute_tree_of_shapes_t() + : undef(-1, -1) { } - template <typename I> + template <typename I, typename IV> + util::tree_of_shapes + compute_tree_of_shapes_t<I,IV>::operator()(const I& F, + const value::interval<IV>& inter, + const mln_site(I)& p_inf) + { + mln_precondition(F.is_valid()); + mln_precondition(value::is_degenerated(F(p_inf))); + + N = F.nsites(); + D = F.domain(); + inter_ = inter; + p_inf_ = p_inf; + + util::tree_of_shapes t; + + display_in_K2<util::tree_of_shapes > dsp(t, std::cout); + sort(F, t, dsp); + + t.parent = union_find(t.R, dsp); + canonicalize_tree(t); + + return t; + } + + + template <typename I, typename IV> + template <typename L> util::tree_of_shapes - compute_tree_of_shapes_t::operator()(const I& F, - const mln_value(I)& inter) + compute_tree_of_shapes_t<I,IV>::operator()(const I& F, + const value::interval<IV>& inter, + const mln_site(I)& p_inf, + const L& l_inf) { - trace::entering("mln::world::kn::compute_tree_of_shapes"); mln_precondition(F.is_valid()); + mln_precondition(F(p_inf).has(l_inf)); N = F.nsites(); D = F.domain(); inter_ = inter; + p_inf_ = p_inf; util::tree_of_shapes t; @@ -487,19 +532,37 @@ namespace mln + template <typename I, typename IV> + util::tree_of_shapes + compute_tree_of_shapes(const Image& F, const value::interval<IV>& inter, + const mln_site(I)& p_inf) + { + trace::entering("mln::world::kn::compute_tree_of_shapes"); + mln_precondition(exact(F).is_valid()); + typedef mln_value(I) V; + mlc_is_a(V, value::interval)::check(); + mln_precondition(value::is_degenerated(exact(F)(p_inf))); + + util::tree_of_shapes + t = internal::compute_tree_of_shapes_t<I,IV>()(exact(F), inter, p_inf); + + trace::exiting("mln::world::kn::compute_tree_of_shapes"); + return t; + } - template <typename I> + template <typename I, typename IV, typename U> util::tree_of_shapes - compute_tree_of_shapes(const Image& F, - const mln_value(I)& inter) + compute_tree_of_shapes(const Image& F, const value::interval<IV>& inter, + const mln_site(I)& p_inf, const U& l_inf) { trace::entering("mln::world::kn::compute_tree_of_shapes"); mln_precondition(exact(F).is_valid()); typedef mln_value(I) V; mlc_is_a(V, value::interval)::check(); + mln_precondition(F(p_inf).has(l_inf)); util::tree_of_shapes - t = internal::compute_tree_of_shapes_t()(exact(F), inter); + t = internal::compute_tree_of_shapes_t<I,IV>()(exact(F), inter, p_inf, l_inf); trace::exiting("mln::world::kn::compute_tree_of_shapes"); return t; -- 1.7.2.5

1 0

branch exp/khalimsky updated: olena-2.0-161-g181e002
by git＠lrde.epita.fr 29 Oct '12

29 Oct '12

This is an automated email from the git hooks/post-receive script. It was generated because a ref change was pushed to the repository containing the project "Olena, a generic and efficient image processing platform". The branch exp/khalimsky has been updated via 181e00223e14c9cfe3e3d947617c62256eb1c6f4 (commit) from 20e5ea192b6d35558375dcdd31105040194a0549 (commit) Those revisions listed above that are new to this repository have not appeared on any other notification email; so we list those revisions in full, below. - Log ----------------------------------------------------------------- 181e002 Rename methods in world::kn::hqueue. ----------------------------------------------------------------------- Summary of changes: milena/ChangeLog | 9 +++++++++ milena/mln/util/hqueue.hh | 12 ++++++------ milena/mln/world/kn/compute_tree_of_shapes.hh | 14 +++++++------- 3 files changed, 22 insertions(+), 13 deletions(-) hooks/post-receive -- Olena, a generic and efficient image processing platform

1 0

olena-2.0-161-g181e002 Rename methods in world::kn::hqueue.
by Guillaume Lazzara 29 Oct '12

29 Oct '12

* mln/world/kn/hqueue.hh: Rename is_empty and is_not_empty to is_empty_at and is_not_empty_at. * mln/world/kn/compute_tree_of_shapes.hh: Update usage of hqueue. --- milena/ChangeLog | 9 +++++++++ milena/mln/util/hqueue.hh | 12 ++++++------ milena/mln/world/kn/compute_tree_of_shapes.hh | 14 +++++++------- 3 files changed, 22 insertions(+), 13 deletions(-) diff --git a/milena/ChangeLog b/milena/ChangeLog index 656968b..b0e2312 100644 --- a/milena/ChangeLog +++ b/milena/ChangeLog @@ -1,5 +1,14 @@ 2012-10-29 Guillaume Lazzara <z(a)lrde.epita.fr> + Rename methods in world::kn::hqueue. + + * mln/world/kn/hqueue.hh: Rename is_empty and is_not_empty to + is_empty_at and is_not_empty_at. + + * mln/world/kn/compute_tree_of_shapes.hh: Update usage of hqueue. + +2012-10-29 Guillaume Lazzara <z(a)lrde.epita.fr> + Add value::is_degenerated. * mln/value/is_degenerated.hh, diff --git a/milena/mln/util/hqueue.hh b/milena/mln/util/hqueue.hh index 6d535cf..9485827 100644 --- a/milena/mln/util/hqueue.hh +++ b/milena/mln/util/hqueue.hh @@ -53,8 +53,8 @@ namespace mln unsigned size() const; - bool is_empty(const P& bucket) const; - bool is_not_empty(const P& bucket) const; + bool is_empty_at(const P& bucket) const; + bool is_not_empty_at(const P& bucket) const; // const std::queue<T>& operator[](const P& bucket) const; @@ -103,16 +103,16 @@ namespace mln template <typename T, typename P> bool - hqueue<T,P>::is_empty(const P& bucket) const + hqueue<T,P>::is_empty_at(const P& bucket) const { return v_[inter_.index_of(bucket)].empty() == 0; } template <typename T, typename P> bool - hqueue<T,P>::is_not_empty(const P& bucket) const + hqueue<T,P>::is_not_empty_at(const P& bucket) const { - return ! is_empty(bucket); + return ! is_empty_at(bucket); } // template <typename T, typename P> @@ -134,7 +134,7 @@ namespace mln T hqueue<T,P>::pop(const P& bucket) { - mln_precondition(!is_empty(bucket)); + mln_precondition(!is_empty_at(bucket)); mln_precondition(bucket < v_.size()); T front = v_[bucket].front(); v_[bucket].pop(); diff --git a/milena/mln/world/kn/compute_tree_of_shapes.hh b/milena/mln/world/kn/compute_tree_of_shapes.hh index 1596618..1778073 100644 --- a/milena/mln/world/kn/compute_tree_of_shapes.hh +++ b/milena/mln/world/kn/compute_tree_of_shapes.hh @@ -239,7 +239,7 @@ namespace mln for (; l_ < inter_.last(); value::inc(l_)) { - if (q.is_not_empty(l_)) + if (q.is_not_empty_at(l_)) { found = true; return l_; @@ -248,7 +248,7 @@ namespace mln // Avoid overflow on last element. if (l_ == inter_.last()) - if (q.is_not_empty(l_)) + if (q.is_not_empty_at(l_)) { found = true; return l_; @@ -265,7 +265,7 @@ namespace mln EV l_ = lcur; for (; l_ > inter_.first(); value::dec(l_)) - if (q.is_not_empty(l_)) + if (q.is_not_empty_at(l_)) { found = true; return l_; @@ -273,7 +273,7 @@ namespace mln // Avoid overflow on first element. if (l_ == inter_.first()) - if (q.is_not_empty(l_)) + if (q.is_not_empty_at(l_)) { found = true; return l_; @@ -326,10 +326,10 @@ namespace mln compute_tree_of_shapes_t::priority_pop(q_type& q) // modify q, and sometimes l { - if (q.is_empty(lcur)) + if (q.is_empty_at(lcur)) { EV lcur_ = level_next_to_lcur(q); // such as q[lcur_] is not empty - if (q.is_empty(lcur_)) + if (q.is_empty_at(lcur_)) std::abort(); lcur = lcur_; } @@ -385,7 +385,7 @@ namespace mln i = i + 1; done(p) = true; - if (q.is_empty(lcur)) + if (q.is_empty_at(lcur)) { std::cout << "sort: done with level " << lcur << std::endl; dsp.show(done); -- 1.7.2.5

1 0