URL: https://svn.lrde.epita.fr/svn/oln/trunk/milena ChangeLog: 2008-04-30 Etienne FOLIO &lt;folio(a)lrde.epita.fr&gt; DT in canevas word plus some addons in original psn. * sandbox/folio/canevas_dt.hh: Canevas for DT algorithm. * sandbox/folio/dt.cc: Main test file. * sandbox/folio/dt.hh: DT using canevas (two algorithms currently identical). * sandbox/folio/dt.spe.hh: DT using canevas spe file. * sandbox/folio/psn.cc: Some addons (max value...). --- canevas_dt.hh | 231 ++++++++++++++++++++++++++++++++++++++++++++++++++++++++++ dt.cc | 59 ++++++++++++++ dt.hh | 101 +++++++++++++++++++++++++ dt.spe.hh | 123 ++++++++++++++++++++++++++++++ psn.cc | 119 ++++++++++++----------------- 5 files changed, 563 insertions(+), 70 deletions(-) Index: trunk/milena/sandbox/folio/psn.cc =================================================================== --- trunk/milena/sandbox/folio/psn.cc (revision 1907) +++ trunk/milena/sandbox/folio/psn.cc (revision 1908) @@ -33,9 +33,12 @@ # include <cmath> # include <mln/core/concept/image.hh> +# include <mln/make/w_window.hh> # include <mln/core/concept/neighborhood.hh> # include <mln/literal/zero.hh> +# include <iostream> + namespace mln { @@ -45,14 +48,15 @@ /*! Propagation using a single neighborhood (PSN). * * \param[in] input_ The input image. - * \param[in] chamfer The chamfer window to use for distance calcul. - * \return A pair <distance map, closest point map>. + * \param[in] nbh The chamfer window to use for distance calcul. + * \param[in] max Max value of the output image. + * \return A distance map. * * \pre \p img has to be initialized. */ template<typename I, typename N> mln_ch_value(I, unsigned) - psn(const Image<I>& input_, const N& nbh); + psn(const Image<I>& input_, const N& nbh, unsigned max); # ifndef MLN_INCLUDE_ONLY @@ -60,31 +64,6 @@ namespace impl { - - template <typename BP> - class compare - { - public: - bool - operator()(const BP& lhs, const BP& rhs) const - { - return lhs.second > rhs.second; - } - }; - - template <typename D> - unsigned - sq(const D& dp) - { - unsigned res = 0; - - for (unsigned i = 0; i < D::dim; ++i) - res += std::abs(dp[i]); // FIXME: dp[i] * dp[i]; - - return res; - } - - } // end of namespace mln::dt::impl @@ -94,72 +73,72 @@ template<typename I, typename N> inline mln_ch_value(I, unsigned) - psn(const Image<I>& input_, const N& nbh) + psn(const Image<I>& input_, const N& nbh, unsigned max) { + // Preconditions. const I& input = exact(input_); mln_precondition(input.has_data()); - mln_ch_value(I, unsigned) D; - initialize(D, input); + // Types. + typedef mln_point(I) point; - static const unsigned M = 666; // FIXME + // Initialization of output. + mln_ch_value(I, unsigned) output; + initialize(output, input); // Initialization. - typedef mln_point(I) point; - typedef mln_dpoint(I) dpoint; - typedef std::pair<point, dpoint> BP; + // { - std::map<unsigned, std::queue<BP> > bucket; + std::map<unsigned, std::queue<point> > bucket; unsigned bucket_size = 0; mln_fwd_piter(I) p(input.domain()); for_all(p) if (input(p)) { - D(p) = literal::zero; - bucket[0].push(BP(p, literal::zero)); + output(p) = literal::zero; + bucket[0].push(p); ++bucket_size; } else - D(p) = M; + output(p) = max; unsigned d = 0; + // } + while (bucket_size != 0) { - std::queue<BP>& bucket_d = bucket[d]; - + std::queue<point> bucket_d = bucket[d]; while (! bucket_d.empty()) { - point p = bucket_d.front().first; - dpoint dp = bucket_d.front().second; - + point p = bucket_d.front(); bucket_d.pop(); --bucket_size; - if (D(p) == d) + if (output(p) == d) { - mln_niter(N) n_(nbh, p); + mln_qiter(N) n(nbh, p); - for_all(n_) - if (D.has(n_)) + for_all(n) + if (output.has(n)) { - dpoint n = n_ - p; - unsigned newD = impl::sq(dp + n); + unsigned newOut = output(p) + n.w(); - if (newD < D(p + n)) // p + n = p + n_ - p = n_ + if (newOut < output(n)) { - D(n_) = newD; - bucket[newD].push(BP(p + n, dp + n)); + output(n) = newOut; + bucket[newOut].push(n); ++bucket_size; } } } } + bucket.erase(d); ++d; } - return D; + return output; } # endif // ! MLN_INCLUDE_ONLY @@ -190,27 +169,27 @@ { using namespace mln; -// image2d<bool> ima(5,5); -// bool vals[] = { 1, 1, 1, 0, 0, -// 0, 0, 1, 0, 0, -// 0, 0, 1, 0, 0, -// 0, 0, 0, 0, 0, -// 0, 0, 0, 0, 0 }; - - image2d<bool> ima(3,3); - bool vals[] = { 1, 0, 0, - 0, 0, 0, - 0, 0, 0}; + image2d<bool> ima(5,5); + bool vals[] = { 1, 0, 0, 1, 1, + 0, 0, 0, 0, 0, + 0, 0, 0, 0, 0, + 0, 0, 0, 1, 0, + 0, 0, 0, 0, 0}; level::fill(ima, vals); - image2d<bool> msk(3,3); - bool rest[] = { 1, 0, 1, - 1, 0, 1, - 1, 1, 1}; + image2d<bool> msk(5,5); + bool rest[] = { 1, 0, 1, 1, 1, + 1, 0, 1, 1, 1, + 1, 1, 0, 0, 0, + 1, 1, 0, 1, 1, + 1, 1, 1, 1, 1}; level::fill(msk, rest); + int ws[] = { 2, 1, 2, + 1, 0, 1, + 2, 1, 2 }; image2d<unsigned> out; - out = dt::psn(ima | pw::value(msk), c4()); + out = dt::psn(ima | pw::value(msk), make::w_window2d(ws), 50); debug::println(ima | pw::value(msk)); debug::println(out); Index: trunk/milena/sandbox/folio/dt.hh =================================================================== --- trunk/milena/sandbox/folio/dt.hh (revision 0) +++ trunk/milena/sandbox/folio/dt.hh (revision 1908) @@ -0,0 +1,101 @@ +/*! + * \file psn.cc + * \author ornthalas &lt;ornthalas(a)gmail.com&gt; + */ + +#ifndef DT_HH +# define DT_HH + +// The 'fastest' specialization is in: +# include "dt.spe.hh" + +namespace mln +{ + + namespace dt + { + + template<typename I, typename N, typename L> + inline + mln_ch_value(I, L) + dt(const Image<I>& input_, const N& nbh, unsigned max); + + +# ifndef MLN_INCLUDE_ONLY + + namespace impl + { + + // Generic functor. + + template <typename I_, typename N_, typename L_> + struct dt_functor + { + typedef I_ I; + typedef N_ N; + typedef L_ L; + + const I& input; + const N& nbh; + unsigned max; + + dt_functor(const I_& input, const N_& nbh, const unsigned max) + : input(input), + nbh(nbh), + max(max) + {} + + void init() {} + }; + + + // Generic implementation. + + namespace generic + { + + template<typename I, typename N, typename L> + inline + mln_ch_value(I, L) + dt_(const Image<I>& input, const N& nbh, unsigned max) + { + trace::entering("dt::impl::generic::dt_"); + + typedef dt_functor<I, N, L> F; + F f(input, nbh, max); + canvas::dt<F> run(f); + + trace::exiting("dt::impl::generic::dt_"); + return run.output; + } + + } // end of namespace mln::dt::impl::generic + + } // end of namespace mln::dt::impl + + + // Facade. + + template<typename I, typename N, typename L> + inline + mln_ch_value(I, L) + dt(const Image<I>& input, const N& nbh, unsigned max) + { + trace::entering("dt::dt"); + mln_precondition(exact(input).has_data()); + + mln_ch_value(I, L) output = + impl::dt_(mln_trait_image_speed(I)(), + exact(input), nbh, max); + + trace::exiting("dt::dt"); + return output; + } + +# endif // ! MLN_INCLUDE_ONLY + + } // end of namespace mln::dt + +} // end of namespace mln + +#endif // !DT_HH Index: trunk/milena/sandbox/folio/canevas_dt.hh =================================================================== --- trunk/milena/sandbox/folio/canevas_dt.hh (revision 0) +++ trunk/milena/sandbox/folio/canevas_dt.hh (revision 1908) @@ -0,0 +1,231 @@ +/*! + * \file canevas_dt.hh + * \author ornthalas &lt;ornthalas(a)gmail.com&gt; + */ + +#ifndef CANEVAS_DT_HH +# define CANEVAS_DT_HH + +# include <queue> +# include <map> +# include <mln/core/concept/image.hh> +# include <mln/make/w_window.hh> +# include <mln/literal/zero.hh> + +# include <mln/core/concept/neighborhood.hh> + +namespace mln +{ + + namespace canvas + { + + // General version. + + template <typename F> + struct dt + { + // Functor. + F& f; + + typedef typename F::I I; + typedef typename F::N N; + typedef typename F::L L; + typedef mln_point(I) point; + + mln_ch_value(I, L) output; + + // Ctor. + dt(F& f); + + void init(); + void run(); + + std::map<unsigned, std::queue<point> > bucket; + unsigned bucket_size; + + unsigned current_distance; + }; + + template <typename F> + struct dt_fastest + { + // Functor. + F& f; + + typedef typename F::I I; + typedef typename F::N N; + typedef typename F::L L; + typedef mln_point(I) point; + + mln_ch_value(I, L) output; + + // Ctor. + dt_fastest(F& f); + + void init(); + void run(); + + std::map<unsigned, std::queue<point> > bucket; + unsigned bucket_size; + + unsigned current_distance; + }; + +# ifndef MLN_INCLUDE_ONLY + + /*-------------. + | canvas::dt. | + `-------------*/ + + template <typename F> + dt<F>::dt(F& f) + : f(f), + bucket_size(0), + current_distance(0) + { + trace::entering("canvas::dt"); + + this->init(); + this->run(); + + trace::exiting("canvas::dt"); + } + + template <typename F> + void + dt<F>::init() + { + this->f.init(); + initialize(this->output, this->f.input); + + mln_fwd_piter(I) p(this->f.input.domain()); + for_all(p) + if (this->f.input(p)) + { + this->output(p) = literal::zero; + this->bucket[0].push(p); + ++this->bucket_size; + } + else + this->output(p) = this->max; + } + + template <typename F> + void + dt<F>::run() + { + while (this->bucket_size != 0) + { + std::queue<point> bucket_d = this->bucket[this->current_distance]; + while (! bucket_d.empty()) + { + point p = bucket_d.front(); + bucket_d.pop(); + --bucket_size; + + if (this->output(p) == this->current_distance) + { + mln_qiter(N) n(this->nbh, p); + + for_all(n) + if (this->output.has(n)) + { + unsigned new_out = this->output(p) + n.w(); + + if (new_out < this->output(n)) + { + this->output(n) = new_out; + this->bucket[new_out].push(n); + ++this->bucket_size; + } + } + } + } + this->bucket.erase(this->current_distance); + ++this->current_distance; + } + } + + /*---------------------. + | canvas::dt_fastest. | + `---------------------*/ + template <typename F> + dt_fastest<F>::dt_fastest(F& f) + : f(f), + bucket_size(0), + current_distance(0) + { + trace::entering("canvas::dt"); + + this->init(); + this->run(); + + trace::exiting("canvas::dt"); + } + + template <typename F> + void + dt_fastest<F>::init() + { + this->f.init(); + initialize(this->output, this->f.input); + + mln_fwd_piter(I) p(this->f.input.domain()); + for_all(p) + if (this->f.input(p)) + { + this->output(p) = literal::zero; + this->bucket[0].push(p); + ++this->bucket_size; + } + else + this->output(p) = this->max; + } + + template <typename F> + void + dt_fastest<F>::run() + { + while (this->bucket_size != 0) + { + std::queue<point> bucket_d = this->bucket[this->current_distance]; + while (! bucket_d.empty()) + { + point p = bucket_d.front(); + bucket_d.pop(); + --bucket_size; + + if (this->output(p) == this->current_distance) + { + mln_qiter(N) n(this->nbh, p); + + for_all(n) + if (this->output.has(n)) + { + unsigned new_out = this->output(p) + n.w(); + + if (new_out < this->output(n)) + { + this->output(n) = new_out; + this->bucket[new_out].push(n); + ++this->bucket_size; + } + } + } + } + this->bucket.erase(this->current_distance); + ++this->current_distance; + } + } + + +# endif // ! MLN_INCLUDE_ONLY + + + } // end of namespace mln::canvas + +} // end of namespace mln + + +#endif // ! MLN_CANVAS_DT_HH Index: trunk/milena/sandbox/folio/dt.cc =================================================================== --- trunk/milena/sandbox/folio/dt.cc (revision 0) +++ trunk/milena/sandbox/folio/dt.cc (revision 1908) @@ -0,0 +1,59 @@ +/*! + * \file dt.cc + * \author ornthalas &lt;ornthalas(a)gmail.com&gt; + */ + +#include <iostream> +#include <mln/core/image2d.hh> +#include <mln/debug/println.hh> +#include <mln/make/win_chamfer.hh> +#include <mln/level/fill.hh> +#include <mln/core/neighb2d.hh> + +#include <mln/io/pbm/load.hh> +#include <mln/io/pgm/save.hh> +#include <mln/level/stretch.hh> +#include <mln/value/int_u8.hh> + +#include <mln/core/sub_image.hh> +#include <mln/core/image_if.hh> +#include <mln/pw/value.hh> + +#include "dt.hh" + +int main() +{ + using namespace mln; + + image2d<bool> ima(5,5); + bool vals[] = { 1, 0, 0, 1, 1, + 0, 0, 0, 0, 0, + 0, 0, 0, 0, 0, + 0, 0, 0, 1, 0, + 0, 0, 0, 0, 0}; + level::fill(ima, vals); + + image2d<bool> msk(5,5); + bool rest[] = { 1, 0, 1, 1, 1, + 1, 0, 1, 1, 1, + 1, 1, 0, 0, 0, + 1, 1, 0, 1, 1, + 1, 1, 1, 1, 1}; + level::fill(msk, rest); + + int ws[] = { 2, 1, 2, + 1, 0, 1, + 2, 1, 2 }; + image2d<unsigned> out; + out = dt::dt(ima | pw::value(msk), make::w_window2d(ws), 50); + + debug::println(ima | pw::value(msk)); + debug::println(out); + +// image2d<bool> ima = io::pbm::load("../../img/c01.pbm"); + +// image2d<value::int_u8> out2(out.domain()); +// level::stretch(out, out2); + +// io::pgm::save(out2, "out.pgm"); +} Index: trunk/milena/sandbox/folio/dt.spe.hh =================================================================== --- trunk/milena/sandbox/folio/dt.spe.hh (revision 0) +++ trunk/milena/sandbox/folio/dt.spe.hh (revision 1908) @@ -0,0 +1,123 @@ +/*! + * \file test_psn.spe.hh + * \author ornthalas &lt;ornthalas(a)gmail.com&gt; + */ + +#ifndef DT_SPE_HH +# define DT_SPE_HH + +# ifndef DT_HH +# error "Forbidden inclusion of *.spe.hh" +# endif // ! DT_HH + +# include "canevas_dt.hh" + +namespace mln +{ + + namespace dt + { + + template<typename I, typename N, typename L> + inline + mln_ch_value(I, L) + dt(const Image<I>& input_, const N& nbh, unsigned max); + + +# ifndef MLN_INCLUDE_ONLY + + namespace impl + { + + + // Fwd decl of the Generic version. + + namespace generic + { + + template<typename I, typename N, typename L> + inline + mln_ch_value(I, L) + dt_(const Image<I>& input_, const N& nbh, unsigned max); + + } // end of namespace mln::dt::impl::generic + + + // Fastest functor. + + template <typename I_, typename N_, typename L_> + struct dt_fasfunctor + { + typedef I_ I; + typedef N_ N; + typedef L_ L; + + const I& input; + const N& nbh; + unsigned max; + + dt_fasfunctor(const I_& input, const N_& nbh, const unsigned max) + : input(input), + nbh(nbh), + max(max) + {} + + void init() {} + }; + + + // Fastest implementation. + + namespace fastest + { + + template<typename I, typename N, typename L> + inline + mln_ch_value(I, L) + dt_(const I& input, const N& nbh, unsigned max) + { + trace::entering("dt::impl::dt_fas"); + + typedef dt_fasfunctor<I,N,L> F; + F f(input, nbh, max); + canvas::dt_fastest<F> run(f); + + trace::exiting("dt::impl::dt_fas"); + return run.output; + } + + } // end of namespace mln::dt::impl::fastest + + + // Disjunction between "fastest" and "not fastest". + + template<typename I, typename N, typename L> + inline + mln_ch_value(I, L) + dt_(trait::image::speed::any, + const I& input, const N& nbh, unsigned max) + { + return generic::dt_(input, nbh, max); + } + + template<typename I, typename N, typename L> + inline + mln_ch_value(I, L) + dt_(trait::image::speed::fastest, + const I& input, const N& nbh, unsigned max) + { + return fastest::dt_(input, nbh, max); + } + + + } // end of namespace mln::dt::impl + + +# endif // ! MLN_INCLUDE_ONLY + + } // end of namespace mln::dt + +} // end of namespace mln + + +#endif // !DT_SPE_HH