https://svn.lrde.epita.fr/svn/oln/trunk/milena Index: ChangeLog from Thierry Geraud <thierry.geraud@lrde.epita.fr> Have fastest morpho wst flooding, plus several fixes. * mln/morpho/watershed/flooding.hh (flooding_fastest): Finalize it. (flooding_dispatch): Activate the fastest version. * mln/io/pnm/load.hh (io::pnm::load): Fix trace balancing. * sandbox/fabien/labeling.hh (labeling_video_fastest): Make it work. * tests/morpho/watershed/flooding.cc: Augment. mln/io/pnm/load.hh | 2 mln/morpho/watershed/flooding.hh | 82 +++++++++++++++++++++++-------------- sandbox/fabien/labeling.hh | 49 ++++++++++++---------- tests/morpho/watershed/flooding.cc | 42 +++++++++++++++--- 4 files changed, 115 insertions(+), 60 deletions(-) Index: mln/morpho/watershed/flooding.hh --- mln/morpho/watershed/flooding.hh (revision 3311) +++ mln/morpho/watershed/flooding.hh (working copy) @@ -51,6 +51,8 @@ # include <mln/core/site_set/p_queue_fast.hh> # include <mln/core/site_set/p_priority.hh> +# include <mln/extension/adjust_fill.hh> + namespace mln { @@ -157,6 +159,7 @@ { psite p = queue.front(); queue.pop(); + // Last seen marker adjacent to P. marker adjacent_marker = unmarked; // Has P a single adjacent marker? @@ -193,10 +196,14 @@ } } } + trace::exiting("morpho::watershed::impl::generic::flooding"); return output; } + } // end of namespace mln::morpho::watershed::impl::generic + + // Fastest version. @@ -217,86 +224,100 @@ typedef mln_value(I) V; const V max = mln_max(V); - // Initialize the output with the markers (minima components). - mln_ch_value(I, marker) output = - labeling::regional_minima (input, nbh, n_basins); + extension::adjust_fill(input, nbh, max); - typedef mln_psite(I) psite; + // Initialize the output with the markers (minima components). + typedef mln_ch_value(I, L) O; + O output = labeling::regional_minima(input, nbh, n_basins); + extension::fill(output, unmarked); // Ordered queue. - typedef p_queue_fast<psite> Q; + typedef p_queue_fast<unsigned> Q; p_priority<V, Q> queue; + // FIXME: With typedef std::pair<V, unsigned> VU; + // std::priority_queue<VU> queue; + // we do not get the same results!!! + // In_queue structure to avoid processing sites several times. mln_ch_value(I, bool) in_queue; initialize(in_queue, input); data::fill(in_queue, false); + extension::fill(in_queue, true); // Insert every neighbor P of every marked area in a // hierarchical queue, with a priority level corresponding to // the grey level input(P). - mln_piter(I) p(output.domain()); - mln_niter(N) n(nbh, p); - for_all (p) - if (output(p) == unmarked) - for_all(n) - if (output.domain().has(n) && output(n) != unmarked) - { - queue.push(max - input(p), p); - in_queue(p) = true; + mln_pixter(const O) p_out(output); + mln_nixter(const O, N) n_out(p_out, nbh); + for_all(p_out) + if (p_out.val() == unmarked) + for_all(n_out) + if (n_out.val() != unmarked) + { + unsigned po = p_out.offset(); + queue.push(max - input.element(po), po); + in_queue.element(po) = true; break; } /* Until the queue is empty, extract a psite P from the hierarchical queue, at the highest priority level, that is, the lowest level. */ + util::array<int> dp = offsets_wrt(input, nbh); + const unsigned n_nbhs = dp.nelements(); while (! queue.is_empty()) { - psite p = queue.front(); + unsigned p = queue.front(); queue.pop(); + // Last seen marker adjacent to P. marker adjacent_marker = unmarked; // Has P a single adjacent marker? bool single_adjacent_marker_p = true; - mln_niter(N) n(nbh, p); - for_all(n) - if (output.domain().has(n) && output(n) != unmarked) + for (unsigned i = 0; i < n_nbhs; ++i) + { + unsigned n = p + dp[i]; + if (output.element(n) != unmarked) // In the border, output is unmarked so n is ignored. { if (adjacent_marker == unmarked) { - adjacent_marker = output(n); + adjacent_marker = output.element(n); single_adjacent_marker_p = true; } else - if (adjacent_marker != output(n)) + if (adjacent_marker != output.element(n)) { single_adjacent_marker_p = false; break; } } + } /* If the neighborhood of P contains only psites with the same label, then P is marked with this label, and its neighbors that are not yet marked are put into the hierarchical queue. */ if (single_adjacent_marker_p) { - output(p) = adjacent_marker; - for_all(n) - if (output.domain().has(n) && output(n) == unmarked - && ! in_queue(n)) + output.element(p) = adjacent_marker; + for (unsigned i = 0; i < n_nbhs; ++i) { - queue.push(max - input(n), n); - in_queue(n) = true; + unsigned n = p + dp[i]; + if (output.element(n) == unmarked + && ! in_queue.element(n)) // In the border, in_queue is true so n is ignored. + { + queue.push(max - input.element(n), n); + in_queue.element(n) = true; + } } } } + trace::exiting("morpho::watershed::impl::flooding_fastest"); return output; } - } // end of namespace mln::morpho::watershed::impl::generic - } // end of namespace mln::morpho::watershed::impl @@ -322,8 +343,7 @@ flooding_dispatch(metal::true_, const Image<I>& input, const Neighborhood<N>& nbh, L& n_basins) { - return impl::generic::flooding(input, nbh, n_basins); -// return impl::generic::flooding_fastest(input, nbh, n_basins); + return impl::flooding_fastest(input, nbh, n_basins); } template <typename I, typename N, typename L> @@ -341,7 +361,7 @@ input, nbh, n_basins); } - } // end of namespace mln::morpho::watershed::impl + } // end of namespace mln::morpho::watershed::internal // Facade. Index: mln/io/pnm/load.hh --- mln/io/pnm/load.hh (revision 3311) +++ mln/io/pnm/load.hh (working copy) @@ -192,7 +192,7 @@ if (type == (type_ - 3)) pnm::load_ascii(file, ima); - trace::entering("mln::io::pnm::load"); + trace::exiting("mln::io::pnm::load"); return ima; } Index: sandbox/fabien/labeling.hh --- sandbox/fabien/labeling.hh (revision 3311) +++ sandbox/fabien/labeling.hh (working copy) @@ -243,12 +243,9 @@ extension::adjust(input, nbh); - // Local type. - typedef mln_psite(I) P; - // Auxiliary data. mln_ch_value(I, bool) deja_vu; - mln_ch_value(I, P) parent; + mln_ch_value(I, unsigned) parent; // Output. mln_ch_value(I, L) output; @@ -271,42 +268,52 @@ // First Pass. { - mln_pixter(const I) p(input); - mln_nixter(const I, N) n(p, nbh); - for_all(p) if (f.handles_(p.offset())) + mln_pixter(const I) px(input); + mln_nixter(const I, N) nx(px, nbh); + for_all(px) { - // Make-Set. - parent(p).val() = p; - f.init_attr_(p.offset()); + unsigned p = px.offset(); + if (! f.handles_(p)) + continue; - for_all(n) - if (input.has(n) && deja_vu(n)) + // Make-Set. + parent.element(p) = p; + f.init_attr_(p); + for_all(nx) + { + unsigned n = nx.offset(); + if (deja_vu.element(n)) { - if (f.equiv_(n.offset(), p.offset())) + if (f.equiv_(n, p)) { // Do-Union. - unsigned r = find_root_fastest(parent, n.val()); + unsigned r = find_root_fastest(parent, n); if (r != p) { parent.element(r) = p; - f.merge_attr_(r, p.offset()); + f.merge_attr_(r, p); } } else - f.do_no_union_(n.offset(), p.offset()); + f.do_no_union_(n, p); } - deja_vu(p) = true; + } + + deja_vu.element(p) = true; } } // Second Pass. { - mln_bkd_pixter(I) p(input); - for_all(p) if (f.handles_(p)) + mln_bkd_pixter(const I) px(input); + for_all(px) { + unsigned p = px.offset(); + if (! f.handles_(p)) + continue; if (parent.element(p) == p) // if p is root { - if (f.labels_(p.offset())) + if (f.labels_(p)) { if (nlabels == mln_max(L)) { @@ -317,7 +324,7 @@ } } else - output.element(p) = output(parent.element(p)); + output.element(p) = output.element(parent.element(p)); } status = true; } Index: tests/morpho/watershed/flooding.cc --- tests/morpho/watershed/flooding.cc (revision 3311) +++ tests/morpho/watershed/flooding.cc (working copy) @@ -36,26 +36,54 @@ #include <mln/core/alias/neighb2d.hh> #include <mln/value/int_u8.hh> +#include <mln/value/int_u16.hh> #include <mln/morpho/watershed/flooding.hh> +#include <mln/level/transform.hh> #include <mln/io/pgm/load.hh> #include <mln/io/pgm/save.hh> -#include "tests/data.hh" +#include <mln/util/timer.hh> + + +struct f_16_to_8 : mln::Function_v2v< f_16_to_8 > +{ + typedef mln::value::int_u8 result; + result operator()(const mln::value::int_u16& v) const + { + if (v == 0) + return 0; + return 1 + (v - 1) % 255; + } +}; int main() { using namespace mln; using value::int_u8; + using value::int_u16; image2d<int_u8> input; - io::pgm::load(input, MLN_IMG_DIR "/squares.pgm"); + io::pgm::load(input, "/squares.pgm"); - typedef int_u8 L; - L nbasins; - image2d<L> output = morpho::watershed::flooding(input, c4(), nbasins); - - io::pgm::save(output, "out.pgm"); + typedef int_u16 L; + L n_basins; + { + util::timer t; + t.start(); + image2d<L> output = morpho::watershed::impl::generic::flooding(input, c4(), n_basins); + std::cout << "gen: " << t << std::endl; + io::pgm::save(level::transform(output, f_16_to_8()), + "tmp_ref.pgm"); + } + { + util::timer t; + t.start(); + image2d<L> output = morpho::watershed::impl::flooding_fastest(input, c4(), n_basins); + std::cout << "fast: " << t << std::endl; + io::pgm::save(level::transform(output, f_16_to_8()), + "tmp_out.pgm"); + } }