* mln/canvas/distance_geodesic.hh: Remove useless traces.
* mln/transform/influence_zone_geodesic.hh: Add a specific fastest version and move some code...
* mln/transform/influence_zone_geodesic_saturated.hh: ... here.
* tests/transform/influence_zone_geodesic.cc: Update test according to the new interface.
* tests/transform/Makefile.am, * tests/transform/influence_zone_geodesic_saturated.cc: New test.
--- milena/ChangeLog | 17 ++ milena/mln/canvas/distance_geodesic.hh | 56 +++--- milena/mln/transform/influence_zone_geodesic.hh | 194 ++++++++++++++++---- ...sic.hh => influence_zone_geodesic_saturated.hh} | 52 ++--- milena/tests/transform/Makefile.am | 6 +- milena/tests/transform/influence_zone_geodesic.cc | 4 +- ...sic.cc => influence_zone_geodesic_saturated.cc} | 6 +- 7 files changed, 232 insertions(+), 103 deletions(-) copy milena/mln/transform/{influence_zone_geodesic.hh => influence_zone_geodesic_saturated.hh} (65%) copy milena/tests/transform/{influence_zone_geodesic.cc => influence_zone_geodesic_saturated.cc} (90%)
diff --git a/milena/ChangeLog b/milena/ChangeLog index f835a42..1e97d05 100644 --- a/milena/ChangeLog +++ b/milena/ChangeLog @@ -1,3 +1,20 @@ +2009-11-18 Guillaume Lazzara z@lrde.epita.fr + + Improve influence zone geodesic. + + * mln/canvas/distance_geodesic.hh: Remove useless traces. + + * mln/transform/influence_zone_geodesic.hh: Add a specific fastest + version and move some code... + + * mln/transform/influence_zone_geodesic_saturated.hh: ... here. + + * tests/transform/influence_zone_geodesic.cc: Update test + according to the new interface. + + * tests/transform/Makefile.am, + * tests/transform/influence_zone_geodesic_saturated.cc: New test. + 2009-11-09 Guillaume Lazzara z@lrde.epita.fr
Add box_runend_piter. diff --git a/milena/mln/canvas/distance_geodesic.hh b/milena/mln/canvas/distance_geodesic.hh index 813e8fc..e833f08 100644 --- a/milena/mln/canvas/distance_geodesic.hh +++ b/milena/mln/canvas/distance_geodesic.hh @@ -1,4 +1,5 @@ -// Copyright (C) 2008, 2009 EPITA Research and Development Laboratory (LRDE) +// Copyright (C) 2008, 2009 EPITA Research and Development Laboratory +// (LRDE) // // This file is part of Olena. // @@ -51,8 +52,8 @@ namespace mln template <typename I, typename N, typename D, typename F> mln_ch_value(I, D) - distance_geodesic(const Image<I>& input, const Neighborhood<N>& nbh, D max, - F& functor); + distance_geodesic(const Image<I>& input, const Neighborhood<N>& nbh, + D max, F& functor);
@@ -67,7 +68,8 @@ namespace mln template <typename I, typename N, typename D, typename F> void - distance_geodesic_tests(const Image<I>& input_, const Neighborhood<N>& nbh_, D max, + distance_geodesic_tests(const Image<I>& input_, + const Neighborhood<N>& nbh_, D max, F& functor) { const I& input = exact(input_); @@ -98,8 +100,8 @@ namespace mln template <typename I, typename N, typename D, typename F> mln_ch_value(I, D) - distance_geodesic(const Image<I>& input_, const Neighborhood<N>& nbh_, D max, - F& functor) + distance_geodesic(const Image<I>& input_, const Neighborhood<N>& nbh_, + D max, F& functor) { trace::entering("canvas::impl::generic::distance_geodesic");
@@ -119,8 +121,6 @@ namespace mln
// Initialization. { - trace::entering("initialization"); - functor.init(input); // <-- init data::fill(dmap, max);
@@ -139,12 +139,10 @@ namespace mln break; } } - trace::exiting("initialization"); }
// Propagation. { - trace::entering("propagation"); P p; mln_niter(N) n(nbh, p); while (! q.is_empty()) @@ -164,7 +162,6 @@ namespace mln q.push(n); } } - trace::exiting("propagation"); }
trace::exiting("canvas::impl::generic::distance_geodesic"); @@ -180,8 +177,10 @@ namespace mln template <typename I, typename N, typename D, typename F> mln_ch_value(I, D) - distance_geodesic_fastest(const Image<I>& input_, const Neighborhood<N>& nbh_, D max, - F& functor) + distance_geodesic_fastest(const Image<I>& input_, + const Neighborhood<N>& nbh_, + D max, + F& functor) { trace::entering("canvas::impl::distance_geodesic_fastest");
@@ -199,8 +198,6 @@ namespace mln
// Initialization. { - trace::entering("initialization"); - functor.init_(input); // <-- init data::fill(dmap, max); // For the extension to be ignored: @@ -221,13 +218,10 @@ namespace mln break; } } - - trace::exiting("initialization"); }
// Propagation. { - trace::entering("propagation"); unsigned p;
util::array<int> dp = offsets_wrt(input, nbh); @@ -251,9 +245,8 @@ namespace mln } } } - trace::exiting("propagation"); } - + trace::exiting("canvas::impl::distance_geodesic_fastest"); return dmap; } @@ -272,9 +265,10 @@ namespace mln typename F> inline mln_ch_value(I, D) - distance_geodesic_dispatch(metal::false_, - const Image<I>& input, const Neighborhood<N>& nbh, D max, - F& functor) + distance_geodesic_dispatch(metal::false_, + const Image<I>& input, + const Neighborhood<N>& nbh, D max, + F& functor) { return impl::generic::distance_geodesic(input, nbh, max, functor); @@ -284,9 +278,10 @@ namespace mln typename F> inline mln_ch_value(I, D) - distance_geodesic_dispatch(metal::true_, - const Image<I>& input, const Neighborhood<N>& nbh, D max, - F& functor) + distance_geodesic_dispatch(metal::true_, + const Image<I>& input, + const Neighborhood<N>& nbh, D max, + F& functor) { return impl::distance_geodesic_fastest(input, nbh, max, functor); // return impl::generic::distance_geodesic(input, nbh, max, @@ -297,8 +292,9 @@ namespace mln typename F> inline mln_ch_value(I, D) - distance_geodesic_dispatch(const Image<I>& input, const Neighborhood<N>& nbh, D max, - F& functor) + distance_geodesic_dispatch(const Image<I>& input, + const Neighborhood<N>& nbh, D max, + F& functor) { enum { test = mlc_equal(mln_trait_image_speed(I), @@ -322,8 +318,8 @@ namespace mln typename F> inline mln_ch_value(I, D) - distance_geodesic(const Image<I>& input, const Neighborhood<N>& nbh, D max, - F& functor) + distance_geodesic(const Image<I>& input, const Neighborhood<N>& nbh, + D max, F& functor) { trace::entering("canvas::distance_geodesic");
diff --git a/milena/mln/transform/influence_zone_geodesic.hh b/milena/mln/transform/influence_zone_geodesic.hh index f500bcf..4d7255a 100644 --- a/milena/mln/transform/influence_zone_geodesic.hh +++ b/milena/mln/transform/influence_zone_geodesic.hh @@ -30,6 +30,7 @@ /// /// Geodesic influence zone transform.
+# include <mln/extension/adjust.hh> # include <mln/canvas/distance_geodesic.hh> # include <mln/transform/internal/influence_zone_functor.hh>
@@ -44,26 +45,9 @@ namespace mln /// /// \param[in] input An image. /// \param[in] nbh A neighborhood. - /// \param[in] max The maximum influence zone distance. - /// \param[in] background_value The value used as background (i.e. - /// not propagated). /// /// \return An image of influence zone. // - template <typename I, typename N, typename D> - mln_concrete(I) - influence_zone_geodesic(const Image<I>& input, - const Neighborhood<N>& nbh, - const D& max, const mln_value(I)& background_value); - - /// \overload - template <typename I, typename N, typename D> - mln_concrete(I) - influence_zone_geodesic(const Image<I>& input, - const Neighborhood<N>& nbh, const D& max); - - - /// \overload template <typename I, typename N> mln_concrete(I) influence_zone_geodesic(const Image<I>& input, const Neighborhood<N>& nbh); @@ -73,38 +57,176 @@ namespace mln # ifndef MLN_INCLUDE_ONLY
- template <typename I, typename N, typename D> - mln_concrete(I) - influence_zone_geodesic(const Image<I>& input, const Neighborhood<N>& nbh, - const D& max, const mln_value(I)& background_value) + namespace internal { - trace::entering("transform::influence_zone_geodesic");
- mln_precondition(exact(input).is_valid()); - mln_precondition(exact(nbh).is_valid()); + template <typename I, typename N> + void + influence_zone_geodesic_tests(const Image<I>& input, + const Neighborhood<N>& nbh) + { + mln_precondition(exact(input).is_valid()); + mln_precondition(exact(nbh).is_valid());
- internal::influence_zone_functor<I> f(background_value); - (void) mln::canvas::distance_geodesic(input, nbh, max, f); + (void) input; + (void) nbh; + }
- trace::exiting("transform::influence_zone_geodesic"); - return f.output; - } + } // end of namespace mln::transform::internal
- template <typename I, typename N, typename D> - mln_concrete(I) - influence_zone_geodesic(const Image<I>& input, const Neighborhood<N>& nbh, - const D& max) + namespace impl + { + + namespace generic + { + + template <typename I, typename N> + mln_concrete(I) + influence_zone_geodesic(const Image<I>& input, + const Neighborhood<N>& nbh) + { + // FIXME: To be written... + mlc_abort(I)::check(); + } + + } // end of namespace mln::transform::impl::generic + + + template <typename I, typename N> + mln_concrete(I) + influence_zone_geodesic_fastest(const Image<I>& input_, + const Neighborhood<N>& nbh_) + { + trace::entering("transform::impl::influence_zone_geodesic_fastest"); + + const I& input = exact(input_); + const N& nbh = exact(nbh_); + + internal::influence_zone_geodesic_tests(input, nbh); + mln_precondition(input.domain().pmin() == literal::origin); + + std::queue<mln_value(I)*> q; + mln_concrete(I) output; + + util::array<int> dp = offsets_wrt(input, nbh); + const unsigned n_nbhs = dp.nelements(); + const unsigned + ncols = input.ncols(), + first_offset = input.border() * (ncols + 2 * input.border() + 1); + + // Initialization. + { + extension::adjust(input, nbh); + output = duplicate(input); + // For the extension to be ignored: + extension::fill(input, 0); // in initialization + extension::fill(output, 1); // in propagation + + const unsigned nelts = input.nelements(); + const mln_value(I)* p_i = & input.at_(0, 0); + mln_value(I)* p_o = & output.at_(0, 0); + for (unsigned i = first_offset; i < nelts; ++i, ++p_i, ++p_o) + { + if (*p_i == 0) + continue; + for (unsigned j = 0; j < n_nbhs; ++j) + { + const mln_value(I)* n_i = p_i + dp[j]; + if (*n_i == 0) + { + q.push(p_o); + break; + } + } + } + + } + + // Propagation. + { + mln_value(I)* ptr; + + while (! q.empty()) + { + ptr = q.front(); + q.pop(); + mln_invariant(*ptr != 0); + for (unsigned j = 0; j < n_nbhs; ++j) + { + mln_value(I)* ntr = ptr + dp[j]; + if (*ntr == 0) + { + *ntr = *ptr; + q.push(ntr); + } + } + } + } + + trace::exiting("transform::impl::influence_zone_geodesic_fastest"); + return output; + } + + + } // end of namespace mln::transform::impl + + + namespace internal { - return influence_zone_geodesic(input, nbh, max, literal::zero); - } + + template <typename I, typename N> + mln_concrete(I) + influence_zone_geodesic_dispatch(trait::image::value_alignment::any, + trait::image::value_storage::any, + trait::image::value_access::any, + const I& input, + const N& nbh) + { + return impl::generic::influence_zone_geodesic(input, nbh); + } + + + template <typename I, typename N> + mln_concrete(I) + influence_zone_geodesic_dispatch(trait::image::value_alignment::with_grid, + trait::image::value_storage::one_block, + trait::image::value_access::direct, + const I& input, + const N& nbh) + { + return impl::influence_zone_geodesic_fastest(input, nbh); + } + + + template <typename I, typename N> + mln_concrete(I) + influence_zone_geodesic_dispatch(const Image<I>& input, + const Neighborhood<N>& nbh) + { + return + influence_zone_geodesic_dispatch(mln_trait_image_value_alignment(I)(), + mln_trait_image_value_storage(I)(), + mln_trait_image_value_access(I)(), + exact(input), exact(nbh)); + } + + } // end of namespace mln::transform::internal
template <typename I, typename N> mln_concrete(I) influence_zone_geodesic(const Image<I>& input, const Neighborhood<N>& nbh) { - return influence_zone_geodesic(input, nbh, mln_max(unsigned)); + trace::entering("transform::influence_zone_geodesic"); + + internal::influence_zone_geodesic_tests(input, nbh); + + mln_concrete(I) + output = internal::influence_zone_geodesic_dispatch(input, nbh); + + trace::exiting("transform::influence_zone_geodesic"); + return output; }
# endif // ! MLN_INCLUDE_ONLY diff --git a/milena/mln/transform/influence_zone_geodesic.hh b/milena/mln/transform/influence_zone_geodesic_saturated.hh similarity index 65% copy from milena/mln/transform/influence_zone_geodesic.hh copy to milena/mln/transform/influence_zone_geodesic_saturated.hh index f500bcf..5a29858 100644 --- a/milena/mln/transform/influence_zone_geodesic.hh +++ b/milena/mln/transform/influence_zone_geodesic_saturated.hh @@ -1,4 +1,4 @@ -// Copyright (C) 2008, 2009 EPITA Research and Development Laboratory (LRDE) +// Copyright (C) 2009 EPITA Research and Development Laboratory (LRDE) // // This file is part of Olena. // @@ -23,8 +23,8 @@ // exception does not however invalidate any other reasons why the // executable file might be covered by the GNU General Public License.
-#ifndef MLN_TRANSFORM_INFLUENCE_ZONE_GEODESIC_HH -# define MLN_TRANSFORM_INFLUENCE_ZONE_GEODESIC_HH +#ifndef MLN_TRANSFORM_INFLUENCE_ZONE_GEODESIC_SATURATED_HH +# define MLN_TRANSFORM_INFLUENCE_ZONE_GEODESIC_SATURATED_HH
/// \file /// @@ -52,22 +52,17 @@ namespace mln // template <typename I, typename N, typename D> mln_concrete(I) - influence_zone_geodesic(const Image<I>& input, - const Neighborhood<N>& nbh, - const D& max, const mln_value(I)& background_value); + influence_zone_geodesic_saturated(const Image<I>& input, + const Neighborhood<N>& nbh, + const D& max, + const mln_value(I)& background_value);
/// \overload template <typename I, typename N, typename D> mln_concrete(I) - influence_zone_geodesic(const Image<I>& input, - const Neighborhood<N>& nbh, const D& max); - - - /// \overload - template <typename I, typename N> - mln_concrete(I) - influence_zone_geodesic(const Image<I>& input, const Neighborhood<N>& nbh); - + influence_zone_geodesic_saturated(const Image<I>& input, + const Neighborhood<N>& nbh, + const D& max);
# ifndef MLN_INCLUDE_ONLY @@ -75,10 +70,12 @@ namespace mln
template <typename I, typename N, typename D> mln_concrete(I) - influence_zone_geodesic(const Image<I>& input, const Neighborhood<N>& nbh, - const D& max, const mln_value(I)& background_value) + influence_zone_geodesic_saturated(const Image<I>& input, + const Neighborhood<N>& nbh, + const D& max, + const mln_value(I)& background_value) { - trace::entering("transform::influence_zone_geodesic"); + trace::entering("transform::influence_zone_geodesic_saturated");
mln_precondition(exact(input).is_valid()); mln_precondition(exact(nbh).is_valid()); @@ -86,25 +83,18 @@ namespace mln internal::influence_zone_functor<I> f(background_value); (void) mln::canvas::distance_geodesic(input, nbh, max, f);
- trace::exiting("transform::influence_zone_geodesic"); + trace::exiting("transform::influence_zone_geodesic_saturated"); return f.output; }
template <typename I, typename N, typename D> mln_concrete(I) - influence_zone_geodesic(const Image<I>& input, const Neighborhood<N>& nbh, - const D& max) - { - return influence_zone_geodesic(input, nbh, max, literal::zero); - } - - - template <typename I, typename N> - mln_concrete(I) - influence_zone_geodesic(const Image<I>& input, const Neighborhood<N>& nbh) + influence_zone_geodesic_saturated(const Image<I>& input, + const Neighborhood<N>& nbh, + const D& max) { - return influence_zone_geodesic(input, nbh, mln_max(unsigned)); + return influence_zone_geodesic_saturated(input, nbh, max, literal::zero); }
# endif // ! MLN_INCLUDE_ONLY @@ -114,4 +104,4 @@ namespace mln } // end of namespace mln
-#endif // ! MLN_TRANSFORM_INFLUENCE_ZONE_GEODESIC_HH +#endif // ! MLN_TRANSFORM_INFLUENCE_ZONE_GEODESIC_SATURATED_HH diff --git a/milena/tests/transform/Makefile.am b/milena/tests/transform/Makefile.am index 3cc36e8..07feb9b 100644 --- a/milena/tests/transform/Makefile.am +++ b/milena/tests/transform/Makefile.am @@ -25,15 +25,19 @@ check_PROGRAMS = \ distance_front \ distance_geodesic \ hough \ + kht \ influence_zone_front \ - influence_zone_geodesic + influence_zone_geodesic \ + influence_zone_geodesic_saturated
bench_closest_point_geodesic_SOURCES = bench_closest_point_geodesic.cc distance_and_closest_point_geodesic_SOURCES = distance_and_closest_point_geodesic.cc distance_front_SOURCES = distance_front.cc distance_geodesic_SOURCES = distance_geodesic.cc hough_SOURCES = hough.cc +kht_SOURCES = kht.cc influence_zone_front_SOURCES = influence_zone_front.cc influence_zone_geodesic_SOURCES = influence_zone_geodesic.cc +influence_zone_geodesic_saturated_SOURCES = influence_zone_geodesic_saturated.cc
TESTS = $(check_PROGRAMS) diff --git a/milena/tests/transform/influence_zone_geodesic.cc b/milena/tests/transform/influence_zone_geodesic.cc index 56a4461..682c1e1 100644 --- a/milena/tests/transform/influence_zone_geodesic.cc +++ b/milena/tests/transform/influence_zone_geodesic.cc @@ -39,7 +39,7 @@ int main()
int_u8 vals[] = { 1, 1, 0, 0, 0, 0, 3, - 1, 1, 1, 0, 0, 0, 0, + 1, 1, 1, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 2, 0, @@ -47,6 +47,6 @@ int main() 0, 0, 0, 0, 0, 0, 0 }; image2d<int_u8> input = make::image2d(vals);
- image2d<int_u8> output = transform::influence_zone_geodesic(input, c4(), int_u8(2)); + image2d<int_u8> output = transform::influence_zone_geodesic(input, c4()); debug::println(output); } diff --git a/milena/tests/transform/influence_zone_geodesic.cc b/milena/tests/transform/influence_zone_geodesic_saturated.cc similarity index 90% copy from milena/tests/transform/influence_zone_geodesic.cc copy to milena/tests/transform/influence_zone_geodesic_saturated.cc index 56a4461..e925b59 100644 --- a/milena/tests/transform/influence_zone_geodesic.cc +++ b/milena/tests/transform/influence_zone_geodesic_saturated.cc @@ -29,7 +29,7 @@ #include <mln/make/image2d.hh> #include <mln/debug/println.hh>
-#include <mln/transform/influence_zone_geodesic.hh> +#include <mln/transform/influence_zone_geodesic_saturated.hh>
int main() @@ -39,7 +39,7 @@ int main()
int_u8 vals[] = { 1, 1, 0, 0, 0, 0, 3, - 1, 1, 1, 0, 0, 0, 0, + 1, 1, 1, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 2, 0, @@ -47,6 +47,6 @@ int main() 0, 0, 0, 0, 0, 0, 0 }; image2d<int_u8> input = make::image2d(vals);
- image2d<int_u8> output = transform::influence_zone_geodesic(input, c4(), int_u8(2)); + image2d<int_u8> output = transform::influence_zone_geodesic_saturated(input, c4(), int_u8(2)); debug::println(output); }
-
Guillaume Lazzara