[Olena-patches] 3495: Have all labeling routines be consistent.

https://svn.lrde.epita.fr/svn/oln/trunk/milena Index: ChangeLog from Thierry Geraud &lt;thierry.geraud(a)lrde.epita.fr&gt; Have all labeling routines be consistent. * mln/core/concept/window.hh, * mln/core/concept/neighborhood.hh (positive_offsets_wrt): New. * mln/morpho/tree/compute_parent.hh (todo): New. (doc): Augment. * mln/morpho/tree/data.hh (todo): New. * mln/canvas/labeling.hh: Swap fwd and bkd between both passes. (todo): New. Now it is consistent with labeling::blobs. * tests/level/sort_psites.cc: Test reversibility. * tests/morpho/tree/data.cc: Precise fwd when needed. * tests/labeling/foreground.cc: Upgrade doc style. Augment test. mln/canvas/labeling.hh | 26 +++++------- mln/core/concept/neighborhood.hh | 18 ++++++++ mln/core/concept/window.hh | 30 ++++++++++++++ mln/morpho/tree/compute_parent.hh | 78 ++++++++++++++++++++++++++++++++++---- mln/morpho/tree/data.hh | 7 ++- tests/labeling/foreground.cc | 38 +++++++++++++++--- tests/level/sort_psites.cc | 19 ++++++--- tests/morpho/tree/data.cc | 15 +++++-- 8 files changed, 193 insertions(+), 38 deletions(-) Index: mln/core/concept/window.hh --- mln/core/concept/window.hh (revision 3494) +++ mln/core/concept/window.hh (working copy) @@ -121,6 +121,10 @@ template <typename I, typename W> util::array<int> + positive_offsets_wrt(const Image<I>& ima, const Window<W>& win); + + template <typename I, typename W> + util::array<int> negative_offsets_wrt(const Image<I>& ima, const Window<W>& win); @@ -346,6 +350,32 @@ template <typename I, typename W> inline util::array<int> + positive_offsets_wrt(const Image<I>& ima_, const Window<W>& win_) + { + mln_is_simple_window(W)::check(); + + const I& ima = exact(ima_); + const W& win = exact(win_); + mln_precondition(ima.is_valid()); + mln_precondition(win.is_valid()); + + util::array<int> arr; + unsigned n = win.size(); + + for (unsigned i = 0; i < n; ++i) + { + int offset = ima.delta_index(win.dp(i)); + if (offset > 0) + arr.append(offset); + } + + return arr; + } + + + template <typename I, typename W> + inline + util::array<int> negative_offsets_wrt(const Image<I>& ima_, const Window<W>& win_) { mln_is_simple_window(W)::check(); Index: mln/core/concept/neighborhood.hh --- mln/core/concept/neighborhood.hh (revision 3494) +++ mln/core/concept/neighborhood.hh (working copy) @@ -104,6 +104,10 @@ template <typename I, typename N> util::array<int> + positive_offsets_wrt(const Image<I>& ima, const Neighborhood<N>& nbh); + + template <typename I, typename N> + util::array<int> negative_offsets_wrt(const Image<I>& ima, const Neighborhood<N>& nbh); @@ -166,6 +170,20 @@ template <typename I, typename N> util::array<int> + positive_offsets_wrt(const Image<I>& ima_, const Neighborhood<N>& nbh_) + { + mln_is_simple_neighborhood(N)::check(); + + const I& ima = exact(ima_); + const N& nbh = exact(nbh_); + mln_precondition(ima.is_valid()); + mln_precondition(nbh.is_valid()); + + return positive_offsets_wrt(ima, nbh.win()); + } + + template <typename I, typename N> + util::array<int> negative_offsets_wrt(const Image<I>& ima_, const Neighborhood<N>& nbh_) { mln_is_simple_neighborhood(N)::check(); Index: mln/morpho/tree/compute_parent.hh --- mln/morpho/tree/compute_parent.hh (revision 3494) +++ mln/morpho/tree/compute_parent.hh (working copy) @@ -1,4 +1,5 @@ -// Copyright (C) 2008 EPITA Research and Development Laboratory (LRDE) +// 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 @@ -33,6 +34,11 @@ /// Compute a canonized tree from an image. /// /// \todo Specialize for low quant (and try fastest). +/// +/// \todo Augment and improve documentation. +/// +/// \todo Change level::sort so that the explanations below are valid +/// whatever the choice 'increasing or decreasing'. # include <mln/core/concept/image.hh> # include <mln/core/concept/neighborhood.hh> @@ -55,16 +61,72 @@ /// "natural" childhood relationship. The parenthood is thus /// inverted w.r.t. to \p s. /// - /// It is very convenient since all processing upon the parent - /// tree are performed following \p s (in the default "forward" - /// way). + /// It is very convenient since most processing routines upon + /// the parent tree are performed following \p s (in the default + /// "forward" way). Indeed that is the way to propagate + /// information from parents to children. /// - /// FIXME: Put it more clearly... /// /// The parent result image verifies: \n /// - p is root iff parent(p) == p \n /// - p is a node iff either p is root or f(parent(p)) != f(p). - + /// + /// + /// + /// The choice "s means childhood" is consistent with labeling + /// in binary images. In that particular case, while browsing + /// the image in forward scan (video), we expect to find first a + /// tree root (a first point, representative of a component) and + /// then the other component points. Please note that it leads + /// to increasing values of labels in the "natural" video scan. + /// + /// Since mathematical morphology on functions is related to + /// morphology on sets, we clearly want to keep the equivalence + /// between "component labeling" and "component filtering" using + /// trees. + /// + /// + /// FIXME: Put it more clearly... Insert pictures! + /// + /// A binary image: + /// + /// - | | - - \n + /// - | | - | \n + /// - - - - - \n + /// - - | | - \n + /// + /// where '|' means true and '-' means false. + /// + /// Its labeling: + /// + /// 0 1 1 0 0 \n + /// 0 1 1 0 2 \n + /// 0 0 0 0 0 \n + /// 0 0 3 3 0 \n + /// + /// The corresponding forest: + /// + /// x o . x x \n + /// x . . x o \n + /// x x x x x \n + /// x x o . x \n + /// + /// where 'x' means "no data", 'o' is a tree root + /// (representative point for a component), and '.' is a tree + /// regular (non-root) point (in a component by not its + /// representative point). + /// + /// + /// The forest, with the parent relationship looks like: + /// + /// o < . \n + /// ^ r \n + /// . . o \n + /// \n + /// \n + /// o < . \n + /// + /// template <typename I, typename N, typename S> mln_ch_value(I, mln_psite(I)) compute_parent(const Image<I>& f, const Neighborhood<N>& nbh, @@ -159,7 +221,7 @@ data::fill(deja_vu, false); // Body. - mln_bkd_piter(S) p(s); + mln_bkd_piter(S) p(s); // Backward. mln_niter(N) n(nbh, p); for_all(p) { @@ -183,7 +245,7 @@ // Canonization. { - mln_fwd_piter(S) p(s); + mln_fwd_piter(S) p(s); // Forward. for_all(p) { P q = parent(p); Index: mln/morpho/tree/data.hh --- mln/morpho/tree/data.hh (revision 3494) +++ mln/morpho/tree/data.hh (working copy) @@ -1,4 +1,5 @@ -// Copyright (C) 2008 EPITA Research and Development Laboratory (LRDE) +// 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 @@ -31,6 +32,10 @@ /// \file mln/morpho/tree/data.hh /// /// FIXME: First Attempt. +/// +/// \todo Fix the issue pointed to by Edwin without modifying the way +/// sites are browsed (see the documentation of compute_parent to +/// learn why we want the 1st pass to be in forward scan of s). # include <mln/morpho/tree/compute_parent.hh> # include <mln/core/image/sub_image.hh> Index: mln/canvas/labeling.hh --- mln/canvas/labeling.hh (revision 3494) +++ mln/canvas/labeling.hh (working copy) @@ -1,5 +1,5 @@ -// Copyright (C) 2007, 2008, 2009 EPITA Research and Development Laboratory -// (LRDE) +// Copyright (C) 2007, 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 @@ -33,8 +33,8 @@ /// /// Connected component labeling of the object part in a binary image. /// -/// \todo Make the fastest version work. -/// FIXME: is 'status' useful? +/// \todo Can we get rid of 'deja_vu' (while playing with the border) +/// in the fastest video version? # include <mln/core/concept/image.hh> # include <mln/data/fill.hh> @@ -139,7 +139,7 @@ // Output. mln_ch_value(I, L) output; - bool status; + bool status; // FIXME: Is-it useful? // Initialization. { @@ -157,7 +157,7 @@ // First Pass. { - mln_fwd_piter(S) p(s); + mln_bkd_piter(S) p(s); // Backward. mln_niter(N) n(nbh, p); for_all(p) if (f.handles(p)) { @@ -187,7 +187,7 @@ // Second Pass. { - mln_bkd_piter(S) p(s); + mln_fwd_piter(S) p(s); // Forward. for_all(p) if (f.handles(p)) { if (parent(p) == p) // if p is root @@ -274,10 +274,10 @@ // First Pass. { - util::array<int> dp = negative_offsets_wrt(input, nbh); + util::array<int> dp = positive_offsets_wrt(input, nbh); const unsigned n_nbhs = dp.nelements(); - mln_pixter(const I) px(input); + mln_bkd_pixter(const I) px(input); // Backward. for_all(px) { unsigned p = px.offset(); @@ -311,7 +311,7 @@ // Second Pass. { - mln_bkd_pixter(const I) px(input); + mln_fwd_pixter(const I) px(input); // Forward. for_all(px) { unsigned p = px.offset(); @@ -394,8 +394,7 @@ // First Pass. { - - for (unsigned i = 0; i < n_points; ++i) + for (int i = n_points - 1; i >=0; --i) // Backward. { unsigned p = s[i]; if (! f.handles_(p)) @@ -425,13 +424,12 @@ f.do_no_union_(n, p); } deja_vu.element(p) = true; - } } // Second Pass. { - for (int i = n_points - 1; i >=0; --i) + for (unsigned i = 0; i < n_points; ++i) // Forward. { unsigned p = s[i]; if (! f.handles_(p)) Index: tests/level/sort_psites.cc --- tests/level/sort_psites.cc (revision 3494) +++ tests/level/sort_psites.cc (working copy) @@ -1,5 +1,5 @@ -// Copyright (C) 2007, 2008 EPITA Research and Development Laboratory -// (LRDE) +// Copyright (C) 2007, 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 @@ -31,7 +31,7 @@ /// Tests on mln::level::sort_psites. #include <mln/core/image/image2d.hh> -#include <mln/debug/iota.hh> +#include <mln/make/image2d.hh> #include <mln/level/sort_psites.hh> #include <mln/core/site_set/p_array.hh> @@ -40,11 +40,20 @@ { using namespace mln; - image2d<int> ima(3, 3); - debug::iota (ima); + int vals[] = { 0, 3, 4, + 2, 2, 2, + 0, 1, 4 }; + image2d<int> ima = make::image2d(vals); p_array<point2d> array_inc = level::sort_psites_increasing(ima); p_array<point2d> array_dec = level::sort_psites_decreasing(ima); + { + p_array<point2d>::fwd_piter p1(array_inc); + p_array<point2d>::bkd_piter p2(array_dec); + for_all_2(p1, p2) + mln_assertion(ima(p1) == ima(p2)); + } + p_array<point2d> array_inc_ref; p_array<point2d> array_dec_ref; Index: tests/morpho/tree/data.cc --- tests/morpho/tree/data.cc (revision 3494) +++ tests/morpho/tree/data.cc (working copy) @@ -1,4 +1,5 @@ -// Copyright (C) 2008 EPITA Research and Development Laboratory (LRDE) +// 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 @@ -62,9 +63,17 @@ { std::cout << "nodes = "; - tree_t::nodes_t::piter p(t.nodes()); + tree_t::nodes_t::fwd_piter p(t.nodes()); for_all(p) std::cout << p << ' '; + std::cout << std::endl; + } + { + std::cout << "nodes = "; + tree_t::fwd_piter p(t.domain()); + for_all(p) + if (t.is_a_node(p)) + std::cout << p << ' '; std::cout << std::endl << std::endl; } @@ -73,7 +82,7 @@ { image2d<unsigned> area(ima.domain()); data::fill(area, 1); - tree_t::piter p(t.domain()); + tree_t::fwd_piter p(t.domain()); for_all(p) if (! t.is_root(p)) area(t.parent(p)) += area(p); Index: tests/labeling/foreground.cc --- tests/labeling/foreground.cc (revision 3494) +++ tests/labeling/foreground.cc (working copy) @@ -1,4 +1,5 @@ -// Copyright (C) 2007, 2008 EPITA Research and Development Laboratory (LRDE) +// Copyright (C) 2007, 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 @@ -25,14 +26,15 @@ // reasons why the executable file might be covered by the GNU General // Public License. -/*! \file tests/labeling/foreground.cc - * - * \brief Test on mln::labeling::foreground. - */ +/// \file tests/labeling/foreground.cc +/// +/// Test on mln::labeling::foreground. #include <mln/core/image/image2d.hh> +#include <mln/core/var.hh> #include <mln/io/pbm/load.hh> #include <mln/core/alias/neighb2d.hh> +#include <mln/level/compare.hh> #include <mln/labeling/foreground.hh> #include "tests/data.hh" @@ -42,8 +44,30 @@ { using namespace mln; - image2d<bool> pic = io::pbm::load(MLN_IMG_DIR "/picasso.pbm"); + typedef image2d<bool> I; + mln_VAR(nbh, c4()); + + I pic = io::pbm::load(MLN_IMG_DIR "/picasso.pbm"); + image2d<unsigned> out, ref; + unsigned n; - labeling::foreground(pic, c4(), n); + out = labeling::foreground(pic, nbh, n); // Calls the fastest 'video' + // version. mln_assertion(n == 33); + + { + // Note that labeling::foreground actually is labeling::level + // which calls canvas::labeling_video and its generic dispatch + // leads to canvas::impl::generic::labeling. + + labeling::impl::level_functor<I> f(pic, true); + + unsigned n_; + ref = canvas::impl::generic::labeling(pic, nbh, n_, + pic.domain(), + f); + mln_invariant(n_ == n); + mln_invariant(ref == out); + } + }