URL: https://svn.lrde.epita.fr/svn/oln/trunk/milena/sandbox ChangeLog: 2009-03-13 Etienne FOLIO &lt;folio(a)lrde.epita.fr&gt; Sandbox reorganization. Moved again many old things... * folio/dt/canvas_dt.hh: Remove. * folio/dt/chamfer.hh: Remove. * folio/dt/cp.hh: Remove. * folio/dt/dmap.hh: Remove. * folio/dt/path.hh: Remove. * folio/dt/raw_cp_fast.hh: Remove. * folio/dt/raw_cp_slow.hh: Remove. * folio/dt/raw_dmap_fast.hh: Remove. * folio/dt/raw_dmap_slow.hh: Remove. * folio/dt/raw_path_fast.hh: Remove. * folio/dt/raw_path_slow.hh: Remove. * folio/dt: Remove. * folio/dt_old/canevas_dt.hh: Remove. * folio/dt_old/chamfer.cc: Remove. * folio/dt_old/distance_front.cc: Remove. * folio/dt_old/distance_front_new.hh: Remove. * folio/dt_old/dt.cc: Remove. * folio/dt_old/dt.hh: Remove. * folio/dt_old/dt.spe.hh: Remove. * folio/dt_old/naive.cc: Remove. * folio/dt_old/psn.cc: Remove. * folio/dt_old/psn_log.cc: Remove. * folio/dt_old: Remove. * folio/mln/dt/dt_old: New. * folio/mln/dt: New. --- canvas_dt.hh | 178 ++++++++++++++++++ chamfer.hh | 156 +++++++++++++++ cp.hh | 121 ++++++++++++ dmap.hh | 119 ++++++++++++ dt_old/canevas_dt.hh | 231 +++++++++++++++++++++++ dt_old/chamfer.cc | 206 +++++++++++++++++++++ dt_old/distance_front.cc | 88 +++++++++ dt_old/distance_front_new.hh | 420 +++++++++++++++++++++++++++++++++++++++++++ dt_old/dt.cc | 59 ++++++ dt_old/dt.hh | 101 ++++++++++ dt_old/dt.spe.hh | 123 ++++++++++++ dt_old/naive.cc | 142 ++++++++++++++ dt_old/psn.cc | 203 ++++++++++++++++++++ dt_old/psn_log.cc | 290 +++++++++++++++++++++++++++++ path.hh | 121 ++++++++++++ raw_cp_fast.hh | 173 +++++++++++++++++ raw_cp_slow.hh | 155 +++++++++++++++ raw_dmap_fast.hh | 164 ++++++++++++++++ raw_dmap_slow.hh | 149 +++++++++++++++ raw_path_fast.hh | 173 +++++++++++++++++ raw_path_slow.hh | 155 +++++++++++++++ 21 files changed, 3527 insertions(+) Index: trunk/milena/sandbox/folio/mln/dt/dmap.hh =================================================================== --- trunk/milena/sandbox/folio/mln/dt/dmap.hh (revision 0) +++ trunk/milena/sandbox/folio/mln/dt/dmap.hh (revision 3524) @@ -0,0 +1,119 @@ +// Copyright (C) 2007 EPITA Research and Development Laboratory +// +// This file is part of the Olena Library. This library is free +// software; you can redistribute it and/or modify it under the terms +// of the GNU General Public License version 2 as published by the +// Free Software Foundation. +// +// This library 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 this library; see the file COPYING. If not, write to +// the Free Software Foundation, 51 Franklin Street, Fifth Floor, +// Boston, MA 02111-1307, USA. +// +// As a special exception, you may use this file as part of a free +// software library 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_DT_DMAP_HH +# define MLN_DT_DMAP_HH + +# include "canvas_dt.hh" + +namespace mln +{ + + namespace dt + { + + /*! Propagation using a single neighborhood (PSN). + * + * \param[in] input_ The input image. + * \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) + dmap(const Image<I>& input_, const N& nbh, unsigned max); + + +# ifndef MLN_INCLUDE_ONLY + + namespace impl + { + + // Generic functor. + + template <typename I_, typename N_> + struct dmap_functor + { + typedef I_ I; + typedef N_ N; + + const I& input; + const N& nbh; + unsigned max; + + dmap_functor(const I& input, const N& nbh, unsigned max) + : input(input), + nbh(nbh), + max(max) + {} + + void init() + { + } + + void init_in_for(const mln_point(I)& p) + { + (void) p; + } + + void run_in_for(const mln_point(I)& p, const mln_point(I)& n) + { + (void) p; + (void) n; + } + }; + + } // end of namespace mln::dt::impl + + + // Facade. + + template<typename I, typename N> + inline + mln_ch_value(I, unsigned) + dmap(const Image<I>& input, const N& nbh, unsigned max) + { + trace::entering("dt::dmap"); + mln_precondition(exact(input).is_valid()); + + typedef impl::dmap_functor<I, N> F; + F f(exact(input), nbh, max); + mln::canvas::dt<F> call(f); + + trace::exiting("dt::dmap"); + return call.distance; + } + +# endif // ! MLN_INCLUDE_ONLY + + } // end of namespace mln::dt + +} // end of namespace mln + +#endif // ! MLN_DT_DMAP_HH Index: trunk/milena/sandbox/folio/mln/dt/canvas_dt.hh =================================================================== --- trunk/milena/sandbox/folio/mln/dt/canvas_dt.hh (revision 0) +++ trunk/milena/sandbox/folio/mln/dt/canvas_dt.hh (revision 3524) @@ -0,0 +1,178 @@ +// Copyright (C) 2007, 2008 EPITA Research and Development Laboratory +// +// This file is part of the Olena Library. This library is free +// software; you can redistribute it and/or modify it under the terms +// of the GNU General Public License version 2 as published by the +// Free Software Foundation. +// +// This library 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 this library; see the file COPYING. If not, write to +// the Free Software Foundation, 51 Franklin Street, Fifth Floor, +// Boston, MA 02111-1307, USA. +// +// As a special exception, you may use this file as part of a free +// software library 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_DT_CANVAS_HH +# define MLN_DT_CANVAS_HH + +# include <vector> + +namespace mln +{ + + namespace canvas + { + + // General version. + + template <typename F> + class dt + { + public: + + // Ctor. + dt(F& f); + + typedef typename F::I I; + typedef typename F::N N; + typedef mln_point(I) point; + + mln_ch_value(I, unsigned) distance; + + private: + + // Functor. + F& f; + + void init(); + void run(); + + std::vector< std::vector<point> > bucket; + unsigned bucket_size; + unsigned mod; + }; + + +# ifndef MLN_INCLUDE_ONLY + + /*-------------. + | canvas::dt. | + `-------------*/ + + template <typename F> + dt<F>::dt(F& f) + : f(f), + bucket_size(0) + { + trace::entering("canvas::dt"); + + this->init(); + this->run(); + + trace::exiting("canvas::dt"); + } + + template <typename F> + void + dt<F>::init() + { + // Preconditions. + mln_precondition(f.input.is_valid()); + + f.init(); //< f call. + + initialize(distance, f.input); + + // Mod determination. + mln::accu::max<unsigned> accu; + mln_fwd_piter(I) p(f.input.domain()); + mln_qiter(N) n(f.nbh, p); + for_all(n) + accu.take(n.w()); + mod = accu.to_result() + 1; + + bucket.resize(mod); + + // Initialization + for_all(p) + { + f.init_in_for(p); //< f call. + if (f.input(p)) + { + distance(p) = literal::zero; + for_all(n) + if (f.input.has(n) && ! f.input(n)) + { + bucket[0].push_back(p); + ++bucket_size; + break; + } + } + else + distance(p) = f.max; + } + } + + template <typename F> + void + dt<F>::run() + { + point p; + mln_qiter(N) n(f.nbh, p); + + for (unsigned d = 0; bucket_size != 0; ++d) + { + std::vector<point>& bucket_d = bucket[d % mod]; + for (unsigned i = 0; i < bucket_d.size(); ++i) + { + p = bucket_d[i]; + + /* |00| |00| insert "a" in bucket 1 |00| + |ab| -> |12| -> insert "b" in bucket 1 -> |11| -> then in bucket 2. + when d = 2, "b" has already been processed when d = 1. */ + if (distance(p) < d) + continue; + + for_all(n) + if (distance.has(n) && distance(n) > d) + { + unsigned newDist = d + n.w(); + + if (newDist < distance(n)) + { + f.run_in_for(p, n); //< f call. + distance(n) = newDist; + bucket[newDist % mod].push_back(n); + ++bucket_size; + } + } + } + bucket_size -= bucket_d.size(); + bucket_d.clear(); + } + + } // end of method dt::run() + + +# endif // ! MLN_INCLUDE_ONLY + + + } // end of namespace mln::canvas + +} // end of namespace mln + + +#endif // ! MLN_DT_CANVAS_HH Index: trunk/milena/sandbox/folio/mln/dt/cp.hh =================================================================== --- trunk/milena/sandbox/folio/mln/dt/cp.hh (revision 0) +++ trunk/milena/sandbox/folio/mln/dt/cp.hh (revision 3524) @@ -0,0 +1,121 @@ +// Copyright (C) 2007 EPITA Research and Development Laboratory +// +// This file is part of the Olena Library. This library is free +// software; you can redistribute it and/or modify it under the terms +// of the GNU General Public License version 2 as published by the +// Free Software Foundation. +// +// This library 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 this library; see the file COPYING. If not, write to +// the Free Software Foundation, 51 Franklin Street, Fifth Floor, +// Boston, MA 02111-1307, USA. +// +// As a special exception, you may use this file as part of a free +// software library 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_DT_CP_HH +# define MLN_DT_CP_HH + +# include "canvas_dt.hh" + +namespace mln +{ + + namespace dt + { + + /*! Propagation using a single neighborhood (PSN). + * + * \param[in] input_ The input image. + * \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, mln_point(I)) + cp(const Image<I>& input_, const N& nbh, unsigned max); + + +# ifndef MLN_INCLUDE_ONLY + + namespace impl + { + + // Generic functor. + + template <typename I_, typename N_> + struct cp_functor + { + typedef I_ I; + typedef N_ N; + + const I& input; + const N& nbh; + unsigned max; + + cp_functor(const I& input, const N& nbh, unsigned max) + : input(input), + nbh(nbh), + max(max) + {} + + mln_ch_value(I, mln_point(I)) output; + + void init() + { + initialize(output, input); + } + + void init_in_for(const mln_point(I)& p) + { + output(p) = p; + } + + void run_in_for(const mln_point(I)& p, const mln_point(I)& n) + { + output(n) = p; + } + }; + + } // end of namespace mln::dt::impl + + + // Facade. + + template<typename I, typename N> + inline + mln_ch_value(I, mln_point(I)) + cp(const Image<I>& input, const N& nbh, unsigned max) + { + trace::entering("dt::cp"); + mln_precondition(exact(input).is_valid()); + + typedef impl::cp_functor<I, N> F; + F f(exact(input), nbh, max); + mln::canvas::dt<F> call(f); + + trace::exiting("dt::cp"); + return f.output; + } + +# endif // ! MLN_INCLUDE_ONLY + + } // end of namespace mln::dt + +} // end of namespace mln + +#endif // ! MLN_DT_CP_HH Index: trunk/milena/sandbox/folio/mln/dt/raw_path_fast.hh =================================================================== --- trunk/milena/sandbox/folio/mln/dt/raw_path_fast.hh (revision 0) +++ trunk/milena/sandbox/folio/mln/dt/raw_path_fast.hh (revision 3524) @@ -0,0 +1,173 @@ +// Copyright (C) 2007 EPITA Research and Development Laboratory +// +// This file is part of the Olena Library. This library is free +// software; you can redistribute it and/or modify it under the terms +// of the GNU General Public License version 2 as published by the +// Free Software Foundation. +// +// This library 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 this library; see the file COPYING. If not, write to +// the Free Software Foundation, 51 Franklin Street, Fifth Floor, +// Boston, MA 02111-1307, USA. +// +// As a special exception, you may use this file as part of a free +// software library 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_DT_RAW_PATH_FAST_HH +# define MLN_DT_RAW_PATH_FAST_HH + +# include <queue> +# include <map> +# 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 <mln/accu/max.hh> + +# include <iostream> + +namespace mln +{ + + namespace dt + { + + /*! Propagation using a single neighborhood (PSN). + * + * \param[in] input_ The input image. + * \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, mln_point(I)) + raw_path_fast(const Image<I>& input_, const N& nbh, unsigned max); + + +# ifndef MLN_INCLUDE_ONLY + + + namespace impl + { + } // end of namespace mln::dt::impl + + + + // Facade. + + template<typename I, typename N> + inline + mln_ch_value(I, mln_point(I)) + raw_path_fast(const Image<I>& input_, const N& nbh, unsigned max) + { + // Preconditions. + const I& input = exact(input_); + mln_precondition(input.is_valid()); + + // Types. + typedef mln_point(I) point; + + // Initialization of distance. + mln_ch_value(I, unsigned) distance; + initialize(distance, input); + + // Initialization of output. + mln_ch_value(I, mln_point(I)) output; + initialize(output, input); + + // Mod determination. + mln_accu_with_(accu::max, unsigned) accu; + mln_fwd_piter(I) p(input.domain()); + mln_qiter(N) n(nbh, p); + for_all(n) + accu.take(n.w()); + unsigned mod = accu.to_result() + 1; + + // Aux data. + std::vector< std::vector<point> > bucket(mod); + unsigned bucket_size = 0; + + // Initialization. + { + for_all(p) + { + output(p) = p; + if (input(p)) + { + distance(p) = literal::zero; + for_all(n) + if (input.has(n) && ! input(n)) + { + bucket[0].push_back(p); + ++bucket_size; + break; + } + } + else + distance(p) = max; + } + } + + // Propagation. + { + point p; + mln_qiter(N) n(nbh, p); + + for (unsigned d = 0; bucket_size != 0; ++d) + { + std::vector<point>& bucket_d = bucket[d % mod]; + for (unsigned i = 0; i < bucket_d.size(); ++i) + { + p = bucket_d[i]; + + // FIXME: Draw... + if (distance(p) < d) + // p has already been processed, having a distance less than d. + continue; + + for_all(n) + if (distance.has(n) && distance(n) > d) + { + unsigned newDist = d + n.w(); + + if (newDist < distance(n)) + { + output(n) = output(p); + distance(n) = newDist; + bucket[newDist % mod].push_back(n); + ++bucket_size; + } + } + } + bucket_size -= bucket_d.size(); + bucket_d.clear(); + } + + } // end of propagation. + + return output; + } + +# endif // ! MLN_INCLUDE_ONLY + + } // end of namespace mln::dt + +} // end of namespace mln + +#endif // ! MLN_DT_RAW_PATH_FAST_HH Index: trunk/milena/sandbox/folio/mln/dt/chamfer.hh =================================================================== --- trunk/milena/sandbox/folio/mln/dt/chamfer.hh (revision 0) +++ trunk/milena/sandbox/folio/mln/dt/chamfer.hh (revision 3524) @@ -0,0 +1,156 @@ +// Copyright (C) 2007 EPITA Research and Development Laboratory +// +// This file is part of the Olena Library. This library is free +// software; you can redistribute it and/or modify it under the terms +// of the GNU General Public License version 2 as published by the +// Free Software Foundation. +// +// This library 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 this library; see the file COPYING. If not, write to +// the Free Software Foundation, 51 Franklin Street, Fifth Floor, +// Boston, MA 02111-1307, USA. +// +// As a special exception, you may use this file as part of a free +// software library 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_DT_CHAMFER_HH +# define MLN_DT_CHAMFER_HH + +# include <mln/core/concept/image.hh> +# include <mln/make/w_window.hh> + +namespace mln +{ + + namespace dt + { + + /*! Distance tranform by chamfer application. + * + * \param[in] input_ The input image. + * \param[in] chamfer The chamfer window to use for distance calcul. + * \return A pair (distance map, nearest point map). + * + * \pre \p img has to be initialized. + */ + template<typename I, typename T> + std::pair<mln_ch_value(I, T), mln_ch_value(I, mln_point(I))> + chamfer(const Image<I>& input_, + w_window<mln_dpoint(I), T> chamfer); + + +# ifndef MLN_INCLUDE_ONLY + + namespace impl + { + + /*! Computes a pass of the chamfer DT algorithm. + * + * \param[in] p Iterator on the input image to use. + * \param[in] chamfer The chamfer window to use for distance calcul. + * \param[in] input The input image. + * \param[out] outputDistance The distance map updated. + * \param[out] outputnearest The nearest points map updated. + */ + template<typename Q, typename I, typename T> + inline + void + chamfer_pass(const w_window<mln_dpoint(I), T> chamfer, + const I& input, + mln_ch_value(I, T)& outputDistance, + mln_ch_value(I, mln_point(I))& outputNearest) + { + typedef w_window<mln_dpoint(I), T> W; + + Q p(input.domain()); + mln_qiter(W) q(chamfer, p); + for_all(p) + { + std::pair<T, mln_point(I)> min(mln_max(T), p); + + for_all(q) + if (input.has(q) && outputDistance(q) != mln_max(T)) + { + T v = outputDistance(q) + q.w(); + + if (v < min.first) + { + min.first = v; + min.second = outputNearest(q); + } + } + + if (min.first < outputDistance(p)) + { + outputDistance(p) = min.first; + outputNearest(p) = min.second; + } + } + } + + } // end of namespace mln::dt::impl + + + + // Facade. + + template<typename I, typename T> + inline + std::pair<mln_ch_value(I, T), mln_ch_value(I, mln_point(I))> + chamfer(const Image<I>& input_, + w_window<mln_dpoint(I), T> chamfer) + { + typedef w_window<mln_dpoint(I), T> W; + + const I& input = exact(input_); + mln_precondition(input.is_valid()); + + mln_ch_value(I, T) outputDistance; + initialize(outputDistance, input); + + mln_ch_value(I, mln_point(I)) outputNearest; + initialize(outputNearest, input); + + // Initialization. + { + mln_fwd_piter(I) p(input.domain()); + for_all(p) + { + outputDistance(p) = input(p) ? literal::zero : mln_max(T); + outputNearest(p) = p; + } + } + + // First pass. + impl::chamfer_pass<mln_fwd_piter(I)> + (chamfer, input, outputDistance, outputNearest); + + chamfer.sym(); + + // Second pass. + impl::chamfer_pass<mln_bkd_piter(I)> + (chamfer, input, outputDistance, outputNearest); + + return std::pair<mln_ch_value(I, T), mln_ch_value(I, mln_point(I))> + (outputDistance, outputNearest); + } + +# endif // ! MLN_INCLUDE_ONLY + + } // end of namespace mln::dt + +} // end of namespace mln + +#endif // ! MLN_DT_CHAMFER_HH Index: trunk/milena/sandbox/folio/mln/dt/dt_old/psn.cc =================================================================== --- trunk/milena/sandbox/folio/mln/dt/dt_old/psn.cc (revision 0) +++ trunk/milena/sandbox/folio/mln/dt/dt_old/psn.cc (revision 3524) @@ -0,0 +1,203 @@ +// Copyright (C) 2007 EPITA Research and Development Laboratory +// +// This file is part of the Olena Library. This library is free +// software; you can redistribute it and/or modify it under the terms +// of the GNU General Public License version 2 as published by the +// Free Software Foundation. +// +// This library 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 this library; see the file COPYING. If not, write to +// the Free Software Foundation, 51 Franklin Street, Fifth Floor, +// Boston, MA 02111-1307, USA. +// +// As a special exception, you may use this file as part of a free +// software library 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_DT_CHAMFER_HH +# define MLN_DT_CHAMFER_HH + +# include <queue> +# include <map> +# 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 +{ + + namespace dt + { + + /*! Propagation using a single neighborhood (PSN). + * + * \param[in] input_ The input image. + * \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, unsigned max); + + +# ifndef MLN_INCLUDE_ONLY + + + namespace impl + { + } // end of namespace mln::dt::impl + + + + // Facade. + + template<typename I, typename N> + inline + mln_ch_value(I, unsigned) + psn(const Image<I>& input_, const N& nbh, unsigned max) + { + // Preconditions. + const I& input = exact(input_); + mln_precondition(input.is_valid()); + + // Types. + typedef mln_point(I) point; + + // Initialization of output. + mln_ch_value(I, unsigned) output; + initialize(output, input); + + // Initialization. + // { + + std::map<unsigned, std::queue<point> > bucket; + unsigned bucket_size = 0; + + mln_fwd_piter(I) p(input.domain()); + for_all(p) + if (input(p)) + { + output(p) = literal::zero; + bucket[0].push(p); + ++bucket_size; + } + else + output(p) = max; + + unsigned d = 0; + + // } + + while (bucket_size != 0) + { + std::queue<point> bucket_d = bucket[d]; + while (! bucket_d.empty()) + { + point p = bucket_d.front(); + bucket_d.pop(); + --bucket_size; + + if (output(p) == d) + { + mln_qiter(N) n(nbh, p); + + for_all(n) + if (output.has(n)) + { + unsigned newOut = output(p) + n.w(); + + if (newOut < output(n)) + { + output(n) = newOut; + bucket[newOut].push(n); + ++bucket_size; + } + } + } + } + bucket.erase(d); + ++d; + } + + return output; + } + +# endif // ! MLN_INCLUDE_ONLY + + } // end of namespace mln::dt + +} // end of namespace mln + +#endif // ! MLN_DT_CHAMFER_HH + +#include <iostream> +#include <mln/core/image/image2d.hh> +#include <mln/debug/println.hh> +#include <mln/make/win_chamfer.hh> +#include <mln/data/fill.hh> +#include <mln/core/alias/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/image/sub_image.hh> +#include <mln/core/image/image_if.hh> +#include <mln/pw/value.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}; + data::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}; + data::fill(msk, rest); + + int ws[] = { 2, 1, 2, + 1, 0, 1, + 2, 1, 2 }; + image2d<unsigned> out; + out = dt::psn(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/mln/dt/dt_old/canevas_dt.hh =================================================================== --- trunk/milena/sandbox/folio/mln/dt/dt_old/canevas_dt.hh (revision 0) +++ trunk/milena/sandbox/folio/mln/dt/dt_old/canevas_dt.hh (revision 3524) @@ -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_psite(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_psite(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/mln/dt/dt_old/dt.hh =================================================================== --- trunk/milena/sandbox/folio/mln/dt/dt_old/dt.hh (revision 0) +++ trunk/milena/sandbox/folio/mln/dt/dt_old/dt.hh (revision 3524) @@ -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).is_valid()); + + 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/mln/dt/dt_old/psn_log.cc =================================================================== --- trunk/milena/sandbox/folio/mln/dt/dt_old/psn_log.cc (revision 0) +++ trunk/milena/sandbox/folio/mln/dt/dt_old/psn_log.cc (revision 3524) @@ -0,0 +1,290 @@ + +// Copyright (C) 2007 EPITA Research and Development Laboratory +// +// This file is part of the Olena Library. This library is free +// software; you can redistribute it and/or modify it under the terms +// of the GNU General Public License version 2 as published by the +// Free Software Foundation. +// +// This library 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 this library; see the file COPYING. If not, write to +// the Free Software Foundation, 51 Franklin Street, Fifth Floor, +// Boston, MA 02111-1307, USA. +// +// As a special exception, you may use this file as part of a free +// software library 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_DT_CHAMFER_HH +# define MLN_DT_CHAMFER_HH + +# include <vector> +# include <queue> +# include <map> +# include <cmath> + +# include <mln/core/concept/image.hh> +# include <mln/core/concept/neighborhood.hh> +# include <mln/literal/zero.hh> + +#include <mln/core/image/image2d.hh> +# include <mln/debug/println.hh> + +namespace mln +{ + + namespace dt + { + + /*! 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>. + * + * \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); + + +# ifndef MLN_INCLUDE_ONLY + + + 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; + } + + template <typename BP> + unsigned + size(const std::map<unsigned, std::queue<BP> >& bucket, + int d) + { + unsigned s = 0; + typename std::map<unsigned, std::queue<BP> >::const_iterator i; + for (i = bucket.begin(); i != bucket.end(); ++i) + if (i->first >= d) + s += i->second.size(); + return s; + } + + template <typename BP> + unsigned + size(const std::map<unsigned, std::queue<BP> >& bucket) + { + unsigned s = 0; + typename std::map<unsigned, std::queue<BP> >::const_iterator i; + for (i = bucket.begin(); i != bucket.end(); ++i) + s += i->second.size(); + return s; + } + + template <typename BP> + void + print(const std::map<unsigned, std::queue<BP> >& bucket) + { + typename std::map<unsigned, std::queue<BP> >::const_iterator i; + int d = -1; + for (i = bucket.begin(); i != bucket.end(); ++i) + { + if (i->first != d) + { + d = i->first; + std::cout << std::endl << d << ": "; + } + std::queue<BP> qu = i->second; // copy + std::vector<BP> v; + v.push_back(qu.front()); qu.pop(); + typename std::vector<BP>::const_iterator j; + for (j = v.begin(); j != v.end(); ++j) + std::cout << j->first << " "; // point + } + std::cout << std::endl; + } + + } // end of namespace mln::dt::impl + + + + // Facade. + + template<typename I, typename N> + inline + mln_ch_value(I, unsigned) + psn(const Image<I>& input_, const N& nbh) + { + const I& input = exact(input_); + mln_precondition(input.is_valid()); + + mln_ch_value(I, unsigned) D; + initialize(D, input); + + static const unsigned M = 666; // FIXME + + // Initialization. + typedef mln_point(I) point; + typedef mln_dpoint(I) dpoint; + typedef std::pair<point, dpoint> BP; + + std::map<unsigned, std::queue<BP> > 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)); + ++bucket_size; + } + else + D(p) = M; + + debug::println(input); + debug::println(D); + impl::print(bucket); + + unsigned d = 0; + + while (impl::size(bucket, d) != 0) + { + + mln_invariant(impl::size(bucket) == bucket_size); + + std::cout << "PROCESSING d = " << d << std::endl; + + std::queue<BP>& bucket_d = bucket[d]; + + while (! bucket_d.empty()) + { + point p = bucket_d.front().first; + dpoint dp = bucket_d.front().second; + + bucket_d.pop(); + --bucket_size; + + std::cout << "pop " << p << " at D=" << D(p) << std::endl; + + if (D(p) == d) + { + mln_niter(N) n_(nbh, p); + + for_all(n_) + if (D.has(n_)) + { + dpoint n = n_ - p; + unsigned newD = impl::sq(dp + n); + + std::cout << " n=" << n_ << " at D=" << D(n_) + << " and newD=" << newD + << (newD < D(p + n) ? " push" : "") + << std::endl; + + if (newD < D(p + n)) // p + n = p + n_ - p = n_ + { + D(n_) = newD; + bucket[newD].push(BP(p + n, dp + n)); + ++bucket_size; + } + } + } + } + ++d; + } + + return D; + } + +# endif // ! MLN_INCLUDE_ONLY + + } // end of namespace mln::dt + +} // end of namespace mln + +#endif // ! MLN_DT_CHAMFER_HH + +#include <iostream> +#include <mln/debug/println.hh> +#include <mln/make/win_chamfer.hh> +#include <mln/data/fill.hh> +#include <mln/core/alias/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/image/sub_image.hh> +#include <mln/core/image/image_if.hh> +#include <mln/pw/value.hh> + +int main() +{ + 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}; + data::fill(ima, vals); + + image2d<bool> msk(3,3); + bool rest[] = { 1, 0, 1, + 1, 0, 1, + 1, 1, 1}; + data::fill(msk, rest); + + image2d<unsigned> out; + out = dt::psn(ima | pw::value(msk), c4()); + + 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/mln/dt/dt_old/distance_front.cc =================================================================== --- trunk/milena/sandbox/folio/mln/dt/dt_old/distance_front.cc (revision 0) +++ trunk/milena/sandbox/folio/mln/dt/dt_old/distance_front.cc (revision 3524) @@ -0,0 +1,88 @@ +// Copyright (C) 2008, 2009 EPITA Research and Development Laboratory +// (LRDE) +// +// This file is part of the Olena Library. This library is free +// software; you can redistribute it and/or modify it under the terms +// of the GNU General Public License version 2 as published by the +// Free Software Foundation. +// +// This library 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 this library; see the file COPYING. If not, write to +// the Free Software Foundation, 51 Franklin Street, Fifth Floor, +// Boston, MA 02111-1307, USA. +// +// As a special exception, you may use this file as part of a free +// software library 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. + +/// \file tests/transform/distance_front.cc +/// +/// Test on mln::transform::distance_front. + +#include <mln/core/var.hh> +#include <mln/core/image/image2d.hh> +#include <mln/core/alias/neighb2d.hh> +#include <mln/make/w_window2d_int.hh> +#include <mln/value/int_u8.hh> +#include <mln/data/fill.hh> +#include <mln/debug/println.hh> +#include <mln/opt/at.hh> +#include <mln/level/compare.hh> + +#include <mln/transform/internal/distance_functor.hh> +#include "distance_front_new.hh" + + +int main() +{ + using namespace mln; + using value::int_u8; + + typedef image2d<bool> I; + + I input(9, 9); + data::fill(input, false); + opt::at(input, 4, 4) = true; + + + int_u8 dmax = 18; + mln_VAR(nbh, c4()); + + int ws[] = { 0, 9, 0, 9, 0, + 9, 6, 4, 6, 9, + 0, 4, 0, 4, 0, + 9, 6, 4, 6, 9, + 0, 9, 0, 9, 0 }; + mln_VAR(w_win, make::w_window2d_int(ws)); + + + transform::internal::distance_functor<I> f; + image2d<int_u8> ref, output; + + ref = canvas::impl::generic::distance_front(input, + nbh, + w_win, + dmax, + f); + // debug::println("ref", ref); + + output = canvas::impl::distance_front_fastest(input, + nbh, + w_win, + dmax, + f); + // debug::println("output", output); + + mln_invariant(output == ref); +} Property changes on: trunk/milena/sandbox/folio/mln/dt/dt_old/distance_front.cc ___________________________________________________________________ Name: svn:mergeinfo + Index: trunk/milena/sandbox/folio/mln/dt/dt_old/naive.cc =================================================================== --- trunk/milena/sandbox/folio/mln/dt/dt_old/naive.cc (revision 0) +++ trunk/milena/sandbox/folio/mln/dt/dt_old/naive.cc (revision 3524) @@ -0,0 +1,142 @@ +// Copyright (C) 2007, 2008 EPITA Research and Development Laboratory (LRDE) +// +// This file is part of the Olena Library. This library is free +// software; you can redistribute it and/or modify it under the terms +// of the GNU General Public License version 2 as published by the +// Free Software Foundation. +// +// This library 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 this library; see the file COPYING. If not, write to +// the Free Software Foundation, 51 Franklin Street, Fifth Floor, +// Boston, MA 02111-1307, USA. +// +// As a special exception, you may use this file as part of a free +// software library 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. + +/*! \file TODO + * + * \brief Defines a function that creates a distance map corresponding to a + * given image. + */ + +#ifndef MLN_DT_NAIVE_HH +# define MLN_DT_NAIVE_HH + +# include <mln/core/concept/image.hh> +# include <mln/core/concept/function.hh> +# include <mln/literal/zero.hh> +# include <mln/accu/min.hh> + +namespace mln +{ + + namespace dt + { + + /*! Calculates the distance map corresponding to a given image + * + * \param[in] input_ The binary reference image. + * \param[in] fun_ The function used for distance aclculus. + * \return New distance map image. + * + * \pre \p input_ has to be initialized. + * + * \fixme Use instead of R the result type of F::operator(). + */ + template <typename I, typename F> + inline + mln_ch_value(I, mln_result(F)) + naive(const Image<I>& input_, const Function_v2v<F>& fun_); + + +# ifndef MLN_INCLUDE_ONLY + + // Facade. + + template <typename I, typename F> + inline + mln_ch_value(I, mln_result(F)) + naive(const Image<I>& input_, const Function_v2v<F>& fun_) + { + const I& input = exact(input_); + const F& fun = exact(fun_); + mln_precondition(input.is_valid()); + + mln_ch_value(I, mln_result(F)) output; + initialize(output, input); + + mln_piter(I) p(input.domain()); + for_all(p) + { + if (input(p)) + output(p) = literal::zero; + else + { + // p is in the background so the distance has to be computed. + accu::min_<mln_result(F)> min; + min.init(); + + mln_piter(I) q(input.domain()); + for_all(q) + if (input(q)) + { + // q is in the object. +// metal::vec<2, int> vp = p.to_point(), vq = q.to_point(); +// min.take(fun_(vp, vq)); + min.take(fun(p - q)); + } + output(p) = min; + } + } + + return output; + } + +# endif // ! MLN_INCLUDE_ONLY + + } // end of namespace mln::dt + +} // end of namespace mln + +#endif // ! MLN_DT_NAIVE_HH + +#include <iostream> +#include <mln/debug/println.hh> +#include <mln/core/image/image2d.hh> +#include <mln/data/fill.hh> +#include <mln/fun/v2v/norm.hh> + +int main() +{ + 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 }; + + data::fill(ima, vals); + debug::println(ima); + + typedef fun::v2v::l2_norm< algebra::vec<2,float>, float > L2; + image2d<float> out = dt::naive(ima, L2()); + + std::cerr << "Distance:" << std::endl; + debug::println(out); + } +} Index: trunk/milena/sandbox/folio/mln/dt/dt_old/chamfer.cc =================================================================== --- trunk/milena/sandbox/folio/mln/dt/dt_old/chamfer.cc (revision 0) +++ trunk/milena/sandbox/folio/mln/dt/dt_old/chamfer.cc (revision 3524) @@ -0,0 +1,206 @@ +// Copyright (C) 2007 EPITA Research and Development Laboratory +// +// This file is part of the Olena Library. This library is free +// software; you can redistribute it and/or modify it under the terms +// of the GNU General Public License version 2 as published by the +// Free Software Foundation. +// +// This library 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 this library; see the file COPYING. If not, write to +// the Free Software Foundation, 51 Franklin Street, Fifth Floor, +// Boston, MA 02111-1307, USA. +// +// As a special exception, you may use this file as part of a free +// software library 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_DT_CHAMFER_HH +# define MLN_DT_CHAMFER_HH + +# include <mln/core/concept/image.hh> +# include <mln/make/w_window.hh> + +namespace mln +{ + + namespace dt + { + + /*! Distance tranform by chamfer application. + * + * \param[in] input_ The input image. + * \param[in] chamfer The chamfer window to use for distance calcul. + * \return A pair (distance map, nearest point map). + * + * \pre \p img has to be initialized. + */ + template<typename I, typename T> + std::pair<mln_ch_value(I, T), mln_ch_value(I, mln_point(I))> + chamfer(const Image<I>& input_, + w_window<mln_dpoint(I), T> chamfer); + + +# ifndef MLN_INCLUDE_ONLY + + namespace impl + { + + /*! Computes a pass of the chamfer DT algorithm. + * + * \param[in] p Iterator on the input image to use. + * \param[in] chamfer The chamfer window to use for distance calcul. + * \param[in] input The input image. + * \param[out] outputDistance The distance map updated. + * \param[out] outputnearest The nearest points map updated. + */ + template<typename Q, typename I, typename T> + inline + void + chamfer_pass(const w_window<mln_dpoint(I), T> chamfer, + const I& input, + mln_ch_value(I, T)& outputDistance, + mln_ch_value(I, mln_point(I))& outputNearest) + { + typedef w_window<mln_dpoint(I), T> W; + + Q p(input.domain()); + mln_qiter(W) q(chamfer, p); + for_all(p) + { + std::pair<T, mln_point(I)> min(mln_max(T), p); + + for_all(q) + if (input.has(q) && outputDistance(q) != mln_max(T)) + { + T v = outputDistance(q) + q.w(); + + if (v < min.first) + { + min.first = v; + min.second = outputNearest(q); + } + } + + if (min.first < outputDistance(p)) + { + outputDistance(p) = min.first; + outputNearest(p) = min.second; + } + } + } + + } // end of namespace mln::dt::impl + + + + // Facade. + + template<typename I, typename T> + inline + std::pair<mln_ch_value(I, T), mln_ch_value(I, mln_point(I))> + chamfer(const Image<I>& input_, + w_window<mln_dpoint(I), T> chamfer) + { + typedef w_window<mln_dpoint(I), T> W; + + const I& input = exact(input_); + mln_precondition(input.is_valid()); + + mln_ch_value(I, T) outputDistance; + initialize(outputDistance, input); + + mln_ch_value(I, mln_point(I)) outputNearest; + initialize(outputNearest, input); + + // Initialization. + { + mln_fwd_piter(I) p(input.domain()); + for_all(p) + { + outputDistance(p) = input(p) ? literal::zero : mln_max(T); + outputNearest(p) = p; + } + } + + // First pass. + impl::chamfer_pass<mln_fwd_piter(I)> + (chamfer, input, outputDistance, outputNearest); + + chamfer.sym(); + + // Second pass. + impl::chamfer_pass<mln_bkd_piter(I)> + (chamfer, input, outputDistance, outputNearest); + + return std::pair<mln_ch_value(I, T), mln_ch_value(I, mln_point(I))> + (outputDistance, outputNearest); + } + +# endif // ! MLN_INCLUDE_ONLY + + } // end of namespace mln::dt + +} // end of namespace mln + +#endif // ! MLN_DT_CHAMFER_HH + +#include <iostream> +#include <mln/core/image/image2d.hh> +#include <mln/debug/println.hh> +#include <mln/make/win_chamfer.hh> +#include <mln/data/fill.hh> + +#include <mln/io/pbm/load.hh> +#include <mln/io/pgm/save.hh> +#include <mln/level/stretch.hh> +#include <mln/value/int_u8.hh> + +int main() +{ + using namespace mln; + + w_window2d_int chamfer = make::mk_chamfer_3x3_int<1, 2>(); + + { +// 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 }; + +// data::fill(ima, vals); +// debug::println(ima); + +// std::pair<image2d<int>, image2d<mln_point_(image2d<bool>)> > out; +// for (int i = 0; i < 999; ++i) +// out = dt::chamfer(ima, chamfer); + +// std::cerr << "Distance:" << std::endl; +// debug::println(out.first); +// std::cerr << "PPP:" << std::endl; +// debug::println(out.second); + + image2d<bool> ima = io::pbm::load("../../img/c01.pbm"); + + std::pair<image2d<int>, image2d<mln_point_(image2d<bool>)> > out; + out = dt::chamfer(ima, chamfer); + + image2d<value::int_u8> out2(out.first.domain()); + level::stretch(out.first, out2); + + io::pgm::save(out2, "out.pgm"); + + } +} Index: trunk/milena/sandbox/folio/mln/dt/dt_old/distance_front_new.hh =================================================================== --- trunk/milena/sandbox/folio/mln/dt/dt_old/distance_front_new.hh (revision 0) +++ trunk/milena/sandbox/folio/mln/dt/dt_old/distance_front_new.hh (revision 3524) @@ -0,0 +1,420 @@ +// Copyright (C) 2008 EPITA Research and Development Laboratory (LRDE) +// +// This file is part of the Olena Library. This library is free +// software; you can redistribute it and/or modify it under the terms +// of the GNU General Public License version 2 as published by the +// Free Software Foundation. +// +// This library 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 this library; see the file COPYING. If not, write to +// the Free Software Foundation, 51 Franklin Street, Fifth Floor, +// Boston, MA 02111-1307, USA. +// +// As a special exception, you may use this file as part of a free +// software library 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_CANVAS_DISTANCE_FRONT_HH +# define MLN_CANVAS_DISTANCE_FRONT_HH + +/// \file mln/canvas/distance_front.hh +/// +/// Discrete distance canvas by front propagation. + +# include <vector> +# include <mln/core/concept/image.hh> +# include <mln/core/concept/neighborhood.hh> +# include <mln/core/concept/weighted_window.hh> +# include <mln/data/fill.hh> +# include <mln/accu/max.hh> +# include <mln/extension/adjust_fill.hh> + + +namespace mln +{ + + namespace canvas + { + + /// Discrete front distance canvas. + template <typename I, + typename N, typename W, typename D, + typename F> + mln_ch_value(I, D) + distance_front(const Image<I>& input, + const Neighborhood<N>& nbh, const Weighted_Window<W>& w_win, D max, + F& functor); + + + +# ifndef MLN_INCLUDE_ONLY + + + // Tests. + + namespace internal + { + + template <typename I, + typename N, typename W, typename D, + typename F> + void + distance_front_tests(const Image<I>& input_, + const Neighborhood<N>& nbh_, + const Weighted_Window<W>& w_win_, + D max, + F& functor) + { + const I& input = exact(input_); + const N& nbh = exact(nbh_); + const W& w_win = exact(w_win_); + + mln_precondition(input.is_valid()); + mln_precondition(nbh.is_valid()); + + (void) input; + (void) nbh; + (void) max; + (void) functor; + } + + + } // of namespace mln::canvas::internal + + + + // Implementations. + + namespace impl + { + + namespace generic + { + + template <typename I, + typename N, typename W, typename D, + typename F> + mln_ch_value(I, D) + distance_front(const Image<I>& input_, + const Neighborhood<N>& nbh_, + const Weighted_Window<W>& w_win_, + D max, + F& functor) + { + trace::entering("canvas::impl::generic::distance_front"); + + const I& input = exact(input_); + const N& nbh = exact(nbh_); + const W& w_win = exact(w_win_); + + mln_precondition(input.is_valid()); + mln_precondition(w_win.is_valid()); + + typedef mln_site(I) P; + typedef std::vector<P> bucket_t; + + // Distance map. + mln_ch_value(I, D) dmap; + initialize(dmap, input); + data::fill(dmap, max); + + // Mod determination. + unsigned mod; + { + accu::max<unsigned> m; + for (unsigned i = 0; i < w_win.size(); ++i) + m.take(w_win.w(i)); + mod = unsigned(m) + 1; + } + + // Aux data. + std::vector<bucket_t> bucket(mod); + unsigned bucket_size = 0; + + // Initialization. + { + functor.init(input); // <-- init + mln_piter(I) p(input.domain()); + mln_niter(N) n(nbh, p); + for_all(p) + if (functor.inqueue_p_wrt_input_p(input(p))) // <-- inqueue_p_wrt_input_p + { + dmap(p) = 0; + for_all(n) + if (input.domain().has(n) && + functor.inqueue_p_wrt_input_n(input(n))) // <-- inqueue_p_wrt_input_n + { + bucket[0].push_back(p); + ++bucket_size; + break; + } + } + } // end of Initialization. + + // Propagation. + { + P p; + mln_qiter(W) q(w_win, p); + for (unsigned d = 0; bucket_size != 0; ++d) + { + bucket_t& bucket_d = bucket[d % mod]; + for (unsigned i = 0; i < bucket_d.size(); ++i) + { + p = bucket_d[i]; + + if (dmap(p) == max) + { + // Saturation so stop. + bucket_size = bucket_d.size(); // So at end bucket_size == 0. + break; + } + + if (dmap(p) < d) + // p has already been processed, having a distance less than d. + continue; + + for_all(q) + if (dmap.domain().has(q) && dmap(q) > d) + { + unsigned d_ = d + q.w(); + if (d_ < dmap(q)) + { + dmap(q) = d_; + functor.process(p, q); // <- process + bucket[d_ % mod].push_back(q); + ++bucket_size; + } + } + } + bucket_size -= bucket_d.size(); + bucket_d.clear(); + } + } // end of Propagation. + + trace::exiting("canvas::impl::generic::distance_front"); + return dmap; + } + + } // of namespace mln::canvas::impl::generic + + + + // Fastest version. + + template <typename I, + typename N, typename W, typename D, + typename F> + mln_ch_value(I, D) + distance_front_fastest(const Image<I>& input_, + const Neighborhood<N>& nbh_, + const Weighted_Window<W>& w_win_, + D max, F& functor) + { + trace::entering("canvas::impl::distance_front_fastest"); + + const I& input = exact(input_); + const N& nbh = exact(nbh_); + const W& w_win = exact(w_win_); + + mln_precondition(input.is_valid()); + mln_precondition(w_win.is_valid()); + + // Handling w_win. + extension::adjust(input, w_win); + const unsigned n_ws = w_win.size(); + util::array<int> dp = offsets_wrt(input, w_win.win()); + mln_invariant(dp.nelements() == n_ws); + + // Distance map. + mln_ch_value(I, D) dmap; + initialize(dmap, input); + data::fill(dmap, max); + + // Mod determination. + unsigned mod; + { + accu::max<unsigned> m; + for (unsigned i = 0; i < w_win.size(); ++i) + m.take(w_win.w(i)); + mod = unsigned(m) + 1; + } + + // Aux data. + typedef std::vector<unsigned> bucket_t; + std::vector<bucket_t> bucket(mod); + unsigned bucket_size = 0; + + // Initialization. + { + functor.init_(input); // <-- init + + // For the extension to be ignored: + extension::fill(input, true); + extension::fill(dmap, D(0)); + + mln_pixter(const I) p(input); + mln_nixter(const I, N) n(p, nbh); + for_all(p) + if (functor.inqueue_p_wrt_input_p_(p.val())) // <-- inqueue_p_wrt_input_p + { + dmap.element(p.offset()) = 0; + for_all(n) + if (functor.inqueue_p_wrt_input_n_(n.val())) // <-- inqueue_p_wrt_input_n + { + bucket[0].push_back(p.offset()); + ++bucket_size; + break; + } + } + } // end of Initialization. + + // Propagation. + { + unsigned p; + + for (unsigned d = 0; bucket_size != 0; ++d) + { + bucket_t& bucket_d = bucket[d % mod]; + for (unsigned i = 0; i < bucket_d.size(); ++i) + { + p = bucket_d[i]; + + if (dmap.element(p) == max) + { + // Saturation so stop. + bucket_size = bucket_d.size(); // So at end bucket_size == 0. + break; + } + + if (dmap.element(p) < d) + // p has already been processed, having a distance less than d. + continue; + + for (unsigned i = 0; i < n_ws; ++i) + { + unsigned q = p + dp[i]; + if (dmap.element(q) > d) + { + unsigned d_ = d + w_win.w(i); + if (d_ < dmap.element(q)) + { + dmap.element(q) = d_; + functor.process_(p, q); // <- process + bucket[d_ % mod].push_back(q); + ++bucket_size; + } + } + } + } + bucket_size -= bucket_d.size(); + bucket_d.clear(); + } + } // end of Propagation. + + trace::exiting("canvas::impl::distance_front_fastest"); + return dmap; + } + + + } // of namespace mln::canvas::impl + + + + // Dispatch. + + namespace internal + { + + template <typename I, + typename N, typename W, typename D, + typename F> + inline + mln_ch_value(I, D) + distance_front_dispatch(metal::false_, + const Image<I>& input, + const Neighborhood<N>& nbh, const Weighted_Window<W>& w_win, + D max, F& functor) + { + return impl::generic::distance_front(input, nbh, max, w_win, functor); + } + + template <typename I, + typename N, typename W, typename D, + typename F> + inline + mln_ch_value(I, D) + distance_front_dispatch(metal::true_, + const Image<I>& input, + const Neighborhood<N>& nbh, const Weighted_Window<W>& w_win, + D max, F& functor) + { + return impl::distance_front_fastest(input, nbh, w_win, max, functor); + // return impl::generic::distance_front(input, nbh, w_win, max, functor); + } + + template <typename I, + typename N, typename W, typename D, + typename F> + inline + mln_ch_value(I, D) + distance_front_dispatch(const Image<I>& input, + const Neighborhood<N>& nbh, const Weighted_Window<W>& w_win, + D max, F& functor) + { + enum { + test = mlc_equal(mln_trait_image_speed(I), + trait::image::speed::fastest)::value + && + mln_is_simple_neighborhood(N)::value + }; + return distance_front_dispatch(metal::bool_<test>(), + input, nbh, w_win, max, functor); + } + + + } // of namespace mln::canvas::internal + + + + // Facade. + + template <typename I, + typename N, typename W, typename D, + typename F> + inline + mln_ch_value(I, D) + distance_front(const Image<I>& input, + const Neighborhood<N>& nbh, const Weighted_Window<W>& w_win, + D max, F& functor) + { + trace::entering("canvas::distance_front"); + + internal::distance_front_tests(input, nbh, w_win, max, functor); + + mln_ch_value(I,D) output; + output = internal::distance_front_dispatch(input, nbh, w_win, max, functor); + + trace::exiting("canvas::distance_front"); + return output; + } + + +# endif // ! MLN_INCLUDE_ONLY + + } // end of namespace mln::canvas + +} // end of namespace mln + + +#endif // ! MLN_CANVAS_DISTANCE_FRONT_HH Index: trunk/milena/sandbox/folio/mln/dt/dt_old/dt.cc =================================================================== --- trunk/milena/sandbox/folio/mln/dt/dt_old/dt.cc (revision 0) +++ trunk/milena/sandbox/folio/mln/dt/dt_old/dt.cc (revision 3524) @@ -0,0 +1,59 @@ +/*! + * \file dt.cc + * \author ornthalas &lt;ornthalas(a)gmail.com&gt; + */ + +#include <iostream> +#include <mln/core/image/image2d.hh> +#include <mln/debug/println.hh> +#include <mln/make/win_chamfer.hh> +#include <mln/data/fill.hh> +#include <mln/core/alias/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/image/sub_image.hh> +#include <mln/core/image/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}; + data::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}; + data::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/mln/dt/dt_old/dt.spe.hh =================================================================== --- trunk/milena/sandbox/folio/mln/dt/dt_old/dt.spe.hh (revision 0) +++ trunk/milena/sandbox/folio/mln/dt/dt_old/dt.spe.hh (revision 3524) @@ -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 Index: trunk/milena/sandbox/folio/mln/dt/raw_dmap_fast.hh =================================================================== --- trunk/milena/sandbox/folio/mln/dt/raw_dmap_fast.hh (revision 0) +++ trunk/milena/sandbox/folio/mln/dt/raw_dmap_fast.hh (revision 3524) @@ -0,0 +1,164 @@ +// Copyright (C) 2007 EPITA Research and Development Laboratory +// +// This file is part of the Olena Library. This library is free +// software; you can redistribute it and/or modify it under the terms +// of the GNU General Public License version 2 as published by the +// Free Software Foundation. +// +// This library 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 this library; see the file COPYING. If not, write to +// the Free Software Foundation, 51 Franklin Street, Fifth Floor, +// Boston, MA 02111-1307, USA. +// +// As a special exception, you may use this file as part of a free +// software library 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_DT_RAW_DMAP_FAST_HH +# define MLN_DT_RAW_DMAP_FAST_HH + +# include <queue> +# include <map> +# 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 +{ + + namespace dt + { + + /*! Propagation using a single neighborhood (PSN). + * + * \param[in] input_ The input image. + * \param[in] nbh The chamfer window to use for distance calcul. + * \param[in] max Max value of the distance image. + * \return A distance map. + * + * \pre \p img has to be initialized. + */ + template<typename I, typename N> + mln_ch_value(I, unsigned) + raw_dmap_fast(const Image<I>& input_, const N& nbh, unsigned max); + + +# ifndef MLN_INCLUDE_ONLY + + + namespace impl + { + } // end of namespace mln::dt::impl + + + + // Facade. + + template<typename I, typename N> + inline + mln_ch_value(I, unsigned) + raw_dmap_fast(const Image<I>& input_, const N& nbh, unsigned max) + { + // Preconditions. + const I& input = exact(input_); + mln_precondition(input.is_valid()); + + // Types. + typedef mln_point(I) point; + + // Initialization of distance. + mln_ch_value(I, unsigned) distance; + initialize(distance, input); + + // Mod determination. + mln_accu_with_(accu::max, unsigned) accu; + mln_fwd_piter(I) p(input.domain()); + mln_qiter(N) n(nbh, p); + for_all(n) + accu.take(n.w()); + unsigned mod = accu.to_result() + 1; + + // Aux data. + std::vector< std::vector<point> > bucket(mod); + unsigned bucket_size = 0; + + // Initialization. + { + for_all(p) + if (input(p)) + { + distance(p) = literal::zero; + for_all(n) + if (input.has(n) && ! input(n)) + { + bucket[0].push_back(p); + ++bucket_size; + break; + } + } + else + distance(p) = max; + } + + // Propagation. + { + point p; + mln_qiter(N) n(nbh, p); + + for (unsigned d = 0; bucket_size != 0; ++d) + { + std::vector<point>& bucket_d = bucket[d % mod]; + for (unsigned i = 0; i < bucket_d.size(); ++i) + { + p = bucket_d[i]; + + // FIXME: Draw... + if (distance(p) < d) + // p has already been processed, having a distance less than d. + continue; + + for_all(n) + if (distance.has(n) && distance(n) > d) + { + unsigned newDist = d + n.w(); + + if (newDist < distance(n)) + { + distance(n) = newDist; + bucket[newDist % mod].push_back(n); + ++bucket_size; + } + } + } + bucket_size -= bucket_d.size(); + bucket_d.clear(); + } + + } // end of propagation. + + return distance; + } + +# endif // ! MLN_INCLUDE_ONLY + + } // end of namespace mln::dt + +} // end of namespace mln + +#endif // ! MLN_DT_RAW_DMAP_FAST_HH Index: trunk/milena/sandbox/folio/mln/dt/raw_cp_fast.hh =================================================================== --- trunk/milena/sandbox/folio/mln/dt/raw_cp_fast.hh (revision 0) +++ trunk/milena/sandbox/folio/mln/dt/raw_cp_fast.hh (revision 3524) @@ -0,0 +1,173 @@ +// Copyright (C) 2007 EPITA Research and Development Laboratory +// +// This file is part of the Olena Library. This library is free +// software; you can redistribute it and/or modify it under the terms +// of the GNU General Public License version 2 as published by the +// Free Software Foundation. +// +// This library 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 this library; see the file COPYING. If not, write to +// the Free Software Foundation, 51 Franklin Street, Fifth Floor, +// Boston, MA 02111-1307, USA. +// +// As a special exception, you may use this file as part of a free +// software library 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_DT_RAW_CP_FAST_HH +# define MLN_DT_RAW_CP_FAST_HH + +# include <queue> +# include <map> +# 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 <mln/accu/max.hh> + +# include <iostream> + +namespace mln +{ + + namespace dt + { + + /*! Propagation using a single neighborhood (PSN). + * + * \param[in] input_ The input image. + * \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 initialcped. + */ + template<typename I, typename N> + mln_ch_value(I, mln_point(I)) + raw_cp_fast(const Image<I>& input_, const N& nbh, unsigned max); + + +# ifndef MLN_INCLUDE_ONLY + + + namespace impl + { + } // end of namespace mln::dt::impl + + + + // Facade. + + template<typename I, typename N> + inline + mln_ch_value(I, mln_point(I)) + raw_cp_fast(const Image<I>& input_, const N& nbh, unsigned max) + { + // Preconditions. + const I& input = exact(input_); + mln_precondition(input.is_valid()); + + // Types. + typedef mln_point(I) point; + + // Initialcpation of distance. + mln_ch_value(I, unsigned) distance; + initialize(distance, input); + + // Initialcpation of output. + mln_ch_value(I, mln_point(I)) output; + initialize(output, input); + + // Mod determination. + mln_accu_with_(accu::max, unsigned) accu; + mln_fwd_piter(I) p(input.domain()); + mln_qiter(N) n(nbh, p); + for_all(n) + accu.take(n.w()); + unsigned mod = accu.to_result() + 1; + + // Aux data. + std::vector< std::vector<point> > bucket(mod); + unsigned bucket_size = 0; + + // Initialcpation. + { + for_all(p) + { + output(p) = p; + if (input(p)) + { + distance(p) = literal::zero; + for_all(n) + if (input.has(n) && ! input(n)) + { + bucket[0].push_back(p); + ++bucket_size; + break; + } + } + else + distance(p) = max; + } + } + + // Propagation. + { + point p; + mln_qiter(N) n(nbh, p); + + for (unsigned d = 0; bucket_size != 0; ++d) + { + std::vector<point>& bucket_d = bucket[d % mod]; + for (unsigned i = 0; i < bucket_d.size(); ++i) + { + p = bucket_d[i]; + + // FIXME: Draw... + if (distance(p) < d) + // p has already been processed, having a distance less than d. + continue; + + for_all(n) + if (distance.has(n) && distance(n) > d) + { + unsigned newDist = d + n.w(); + + if (newDist < distance(n)) + { + output(n) = p; + distance(n) = newDist; + bucket[newDist % mod].push_back(n); + ++bucket_size; + } + } + } + bucket_size -= bucket_d.size(); + bucket_d.clear(); + } + + } // end of propagation. + + return output; + } + +# endif // ! MLN_INCLUDE_ONLY + + } // end of namespace mln::dt + +} // end of namespace mln + +#endif // ! MLN_DT_RAW_CP_FAST_HH Index: trunk/milena/sandbox/folio/mln/dt/raw_path_slow.hh =================================================================== --- trunk/milena/sandbox/folio/mln/dt/raw_path_slow.hh (revision 0) +++ trunk/milena/sandbox/folio/mln/dt/raw_path_slow.hh (revision 3524) @@ -0,0 +1,155 @@ +// Copyright (C) 2007 EPITA Research and Development unsignedaboratory +// +// This file is part of the Olena unsignedibrary. This library is free +// software; you can redistribute it and/or modify it under the terms +// of the GNU General Public unsignedicense version 2 as published by the +// Free Software Foundation. +// +// This library 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 unsignedicense for more details. +// +// You should have received a copy of the GNU General Public unsignedicense +// along with this library; see the file COPYING. If not, write to +// the Free Software Foundation, 51 Franklin Street, Fifth Floor, +// Boston, MA 02111-1307, USA. +// +// As a special exception, you may use this file as part of a free +// software library 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 +// unsignedicense. This exception does not however invalidate any other +// reasons why the executable file might be covered by the GNU General +// Public unsignedicense. + +#ifndef MLN_DT_RAW_PATH_SLOW_HH +# define MLN_DT_RAW_PATH_SLOW_HH + +# include <queue> +# include <map> +# 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 +{ + + namespace dt + { + + /*! Propagation using a single neighborhood (PSN). + * + * \param[in] input_ The input image. + * \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, mln_point(I)) + raw_path_slow(const Image<I>& input_, const N& nbh, unsigned max); + + +# ifndef MLN_INCLUDE_ONLY + + + namespace impl + { + } // end of namespace mln::dt::impl + + + + // Facade. + + template<typename I, typename N> + inline + mln_ch_value(I, mln_point(I)) + raw_path_slow(const Image<I>& input_, const N& nbh, unsigned max) + { + // Preconditions. + const I& input = exact(input_); + mln_precondition(input.is_valid()); + + // Types. + typedef mln_point(I) point; + + // Initialization of distance. + mln_ch_value(I, unsigned) distance; + initialize(distance, input); + + // Initialization of output. + mln_ch_value(I, mln_point(I)) output; + initialize(output, input); + + // Initialization. + // { + + std::map< unsigned, std::queue<point> > bucket; + unsigned bucket_size = 0; + + mln_fwd_piter(I) p(input.domain()); + for_all(p) + { + output(p) = p; + if (input(p)) + { + distance(p) = literal::zero; + bucket[0].push(p); + ++bucket_size; + } + else + distance(p) = max; + } + + // } + + for (unsigned d = 0; bucket_size != 0; ++d) + { + std::queue<point> bucket_d = bucket[d]; + while (! bucket_d.empty()) + { + point p = bucket_d.front(); + bucket_d.pop(); + --bucket_size; + + if (distance(p) == d) + { + mln_qiter(N) n(nbh, p); + + for_all(n) + if (distance.has(n)) + { + unsigned newDist = d + n.w(); + + if (newDist < distance(n)) + { + distance(n) = newDist; + output(n) = output(p); + bucket[newDist].push(n); + ++bucket_size; + } + } + } + } + bucket.erase(d); + } + + return output; + } + +# endif // ! MLN_INCLUDE_ONLY + + } // end of namespace mln::dt + +} // end of namespace mln + +#endif // ! MLN_DT_RAW_PATH_SLOW_HH Index: trunk/milena/sandbox/folio/mln/dt/path.hh =================================================================== --- trunk/milena/sandbox/folio/mln/dt/path.hh (revision 0) +++ trunk/milena/sandbox/folio/mln/dt/path.hh (revision 3524) @@ -0,0 +1,121 @@ +// Copyright (C) 2007 EPITA Research and Development Laboratory +// +// This file is part of the Olena Library. This library is free +// software; you can redistribute it and/or modify it under the terms +// of the GNU General Public License version 2 as published by the +// Free Software Foundation. +// +// This library 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 this library; see the file COPYING. If not, write to +// the Free Software Foundation, 51 Franklin Street, Fifth Floor, +// Boston, MA 02111-1307, USA. +// +// As a special exception, you may use this file as part of a free +// software library 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_DT_PATH_HH +# define MLN_DT_PATH_HH + +# include "canvas_dt.hh" + +namespace mln +{ + + namespace dt + { + + /*! Propagation using a single neighborhood (PSN). + * + * \param[in] input_ The input image. + * \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, mln_point(I)) + path(const Image<I>& input_, const N& nbh, unsigned max); + + +# ifndef MLN_INCLUDE_ONLY + + namespace impl + { + + // Generic functor. + + template <typename I_, typename N_> + struct path_functor + { + typedef I_ I; + typedef N_ N; + + const I& input; + const N& nbh; + unsigned max; + + path_functor(const I& input, const N& nbh, unsigned max) + : input(input), + nbh(nbh), + max(max) + {} + + mln_ch_value(I, mln_point(I)) output; + + void init() + { + initialize(output, input); + } + + void init_in_for(const mln_point(I)& p) + { + output(p) = p; + } + + void run_in_for(const mln_point(I)& p, const mln_point(I)& n) + { + output(n) = output(p); + } + }; + + } // end of namespace mln::dt::impl + + + // Facade. + + template<typename I, typename N> + inline + mln_ch_value(I, mln_point(I)) + path(const Image<I>& input, const N& nbh, unsigned max) + { + trace::entering("dt::path"); + mln_precondition(exact(input).is_valid()); + + typedef impl::path_functor<I, N> F; + F f(exact(input), nbh, max); + mln::canvas::dt<F> call(f); + + trace::exiting("dt::path"); + return f.output; + } + +# endif // ! MLN_INCLUDE_ONLY + + } // end of namespace mln::dt + +} // end of namespace mln + +#endif // ! MLN_DT_PATH_HH Index: trunk/milena/sandbox/folio/mln/dt/raw_dmap_slow.hh =================================================================== --- trunk/milena/sandbox/folio/mln/dt/raw_dmap_slow.hh (revision 0) +++ trunk/milena/sandbox/folio/mln/dt/raw_dmap_slow.hh (revision 3524) @@ -0,0 +1,149 @@ +// Copyright (C) 2007 EPITA Research and Development unsignedaboratory +// +// This file is part of the Olena unsignedibrary. This library is free +// software; you can redistribute it and/or modify it under the terms +// of the GNU General Public unsignedicense version 2 as published by the +// Free Software Foundation. +// +// This library 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 unsignedicense for more details. +// +// You should have received a copy of the GNU General Public unsignedicense +// along with this library; see the file COPYING. If not, write to +// the Free Software Foundation, 51 Franklin Street, Fifth Floor, +// Boston, MA 02111-1307, USA. +// +// As a special exception, you may use this file as part of a free +// software library 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 +// unsignedicense. This exception does not however invalidate any other +// reasons why the executable file might be covered by the GNU General +// Public unsignedicense. + +#ifndef MLN_DT_RAW_DMAP_SLOW_HH +# define MLN_DT_RAW_DMAP_SLOW_HH + +# include <queue> +# include <map> +# 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 +{ + + namespace dt + { + + /*! Propagation using a single neighborhood (PSN). + * + * \param[in] input_ The input image. + * \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) + raw_dmap_slow(const Image<I>& input_, const N& nbh, unsigned max); + + +# ifndef MLN_INCLUDE_ONLY + + + namespace impl + { + } // end of namespace mln::dt::impl + + + + // Facade. + + template<typename I, typename N> + inline + mln_ch_value(I, unsigned) + raw_dmap_slow(const Image<I>& input_, const N& nbh, unsigned max) + { + // Preconditions. + const I& input = exact(input_); + mln_precondition(input.is_valid()); + + // Types. + typedef mln_point(I) point; + + // Initialization of distance. + mln_ch_value(I, unsigned) distance; + initialize(distance, input); + + // Initialization. + // { + + std::map< unsigned, std::queue<point> > bucket; + unsigned bucket_size = 0; + + mln_fwd_piter(I) p(input.domain()); + for_all(p) + { + if (input(p)) + { + distance(p) = literal::zero; + bucket[0].push(p); + ++bucket_size; + } + else + distance(p) = max; + } + + // } + + for (unsigned d = 0; bucket_size != 0; ++d) + { + std::queue<point> bucket_d = bucket[d]; + while (! bucket_d.empty()) + { + point p = bucket_d.front(); + bucket_d.pop(); + --bucket_size; + + if (distance(p) == d) + { + mln_qiter(N) n(nbh, p); + + for_all(n) + if (distance.has(n)) + { + unsigned newDist = d + n.w(); + + if (newDist < distance(n)) + { + distance(n) = newDist; + bucket[newDist].push(n); + ++bucket_size; + } + } + } + } + bucket.erase(d); + } + + return distance; + } + +# endif // ! MLN_INCLUDE_ONLY + + } // end of namespace mln::dt + +} // end of namespace mln + +#endif // ! MLN_DT_RAW_DMAP_SLOW_HH Index: trunk/milena/sandbox/folio/mln/dt/raw_cp_slow.hh =================================================================== --- trunk/milena/sandbox/folio/mln/dt/raw_cp_slow.hh (revision 0) +++ trunk/milena/sandbox/folio/mln/dt/raw_cp_slow.hh (revision 3524) @@ -0,0 +1,155 @@ +// Copyright (C) 2007 EPITA Research and Development unsignedaboratory +// +// This file is part of the Olena unsignedibrary. This library is free +// software; you can redistribute it and/or modify it under the terms +// of the GNU General Public unsignedicense version 2 as published by the +// Free Software Foundation. +// +// This library 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 unsignedicense for more details. +// +// You should have received a copy of the GNU General Public unsignedicense +// along with this library; see the file COPYING. If not, write to +// the Free Software Foundation, 51 Franklin Street, Fifth Floor, +// Boston, MA 02111-1307, USA. +// +// As a special exception, you may use this file as part of a free +// software library 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 +// unsignedicense. This exception does not however invalidate any other +// reasons why the executable file might be covered by the GNU General +// Public unsignedicense. + +#ifndef MLN_DT_RAW_CP_SLOW_HH +# define MLN_DT_RAW_CP_SLOW_HH + +# include <queue> +# include <map> +# 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 +{ + + namespace dt + { + + /*! Propagation using a single neighborhood (PSN). + * + * \param[in] input_ The input image. + * \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 initialcped. + */ + template<typename I, typename N> + mln_ch_value(I, mln_point(I)) + raw_cp_slow(const Image<I>& input_, const N& nbh, unsigned max); + + +# ifndef MLN_INCLUDE_ONLY + + + namespace impl + { + } // end of namespace mln::dt::impl + + + + // Facade. + + template<typename I, typename N> + inline + mln_ch_value(I, mln_point(I)) + raw_cp_slow(const Image<I>& input_, const N& nbh, unsigned max) + { + // Preconditions. + const I& input = exact(input_); + mln_precondition(input.is_valid()); + + // Types. + typedef mln_point(I) point; + + // Initialcpation of distance. + mln_ch_value(I, unsigned) distance; + initialize(distance, input); + + // Initialcpation of output. + mln_ch_value(I, mln_point(I)) output; + initialize(output, input); + + // Initialcpation. + // { + + std::map< unsigned, std::queue<point> > bucket; + unsigned bucket_size = 0; + + mln_fwd_piter(I) p(input.domain()); + for_all(p) + { + output(p) = p; + if (input(p)) + { + distance(p) = literal::zero; + bucket[0].push(p); + ++bucket_size; + } + else + distance(p) = max; + } + + // } + + for (unsigned d = 0; bucket_size != 0; ++d) + { + std::queue<point> bucket_d = bucket[d]; + while (! bucket_d.empty()) + { + point p = bucket_d.front(); + bucket_d.pop(); + --bucket_size; + + if (distance(p) == d) + { + mln_qiter(N) n(nbh, p); + + for_all(n) + if (distance.has(n)) + { + unsigned newDist = d + n.w(); + + if (newDist < distance(n)) + { + distance(n) = newDist; + output(n) = p; + bucket[newDist].push(n); + ++bucket_size; + } + } + } + } + bucket.erase(d); + } + + return output; + } + +# endif // ! MLN_INCLUDE_ONLY + + } // end of namespace mln::dt + +} // end of namespace mln + +#endif // ! MLN_DT_RAW_CP_SLOW_HH