[Olena-patches] last-svn-commit-281-g03fc660 Fix and improve the (fast) computation of 2D connectivity numbers.

* mln/topo/is_simple_2d.hh (mln::connectivity_number_2d): Create the configuration number by considering that the first (resp. last) neighbors (in the forward browsing order) represent the least (resp. most) significant bits of the configuration number, as does the algorithm that computed the 8-c and 4-c LUTs (arrays mln::connectivity_number_c8 and mln::connectivity_number_c4). * mln/topo/connectivity_number_2d.hh: New. * mln/topo/is_simple_point2d.hh: Fix dates in copyright header. * tests/topo/connectivity_numbers_2d.cc: New. * tests/topo/Makefile.am (check_PROGRAMS): Add connectivity_numbers_2d. (connectivity_numbers_2d_SOURCES): New. --- milena/ChangeLog | 17 +++ milena/mln/topo/connectivity_number_2d.hh | 130 ++++++++++++++++++++ milena/mln/topo/is_simple_2d.hh | 17 ++- milena/mln/topo/is_simple_point2d.hh | 2 +- milena/tests/topo/Makefile.am | 5 + .../topo/connectivity_numbers_2d.cc} | 94 +++++++------- 6 files changed, 212 insertions(+), 53 deletions(-) create mode 100644 milena/mln/topo/connectivity_number_2d.hh copy milena/{sandbox/lazzara/afp/micro_films/keep_background.cc => tests/topo/connectivity_numbers_2d.cc} (51%) diff --git a/milena/ChangeLog b/milena/ChangeLog index 632bacd..1df7452 100644 --- a/milena/ChangeLog +++ b/milena/ChangeLog @@ -1,5 +1,22 @@ 2011-07-12 Roland Levillain &lt;roland(a)lrde.epita.fr&gt; + Fix and improve the (fast) computation of 2D connectivity numbers. + + * mln/topo/is_simple_2d.hh (mln::connectivity_number_2d): Create + the configuration number by considering that the first (resp. + last) neighbors (in the forward browsing order) represent the + least (resp. most) significant bits of the configuration number, + as does the algorithm that computed the 8-c and 4-c LUTs (arrays + mln::connectivity_number_c8 and mln::connectivity_number_c4). + * mln/topo/connectivity_number_2d.hh: New. + * mln/topo/is_simple_point2d.hh: Fix dates in copyright header. + * tests/topo/connectivity_numbers_2d.cc: New. + * tests/topo/Makefile.am (check_PROGRAMS): + Add connectivity_numbers_2d. + (connectivity_numbers_2d_SOURCES): New. + +2011-07-12 Roland Levillain &lt;roland(a)lrde.epita.fr&gt; + Add more tests. * tests/core/alias/dpoint2d.cc: Exercise the substraction of a diff --git a/milena/mln/topo/connectivity_number_2d.hh b/milena/mln/topo/connectivity_number_2d.hh new file mode 100644 index 0000000..221ca26 --- /dev/null +++ b/milena/mln/topo/connectivity_number_2d.hh @@ -0,0 +1,130 @@ +// Copyright (C) 2011 EPITA Research and Development Laboratory (LRDE) +// +// This file is part of Olena. +// +// Olena is free software: you can redistribute it and/or modify it under +// the terms of the GNU General Public License as published by the Free +// Software Foundation, version 2 of the License. +// +// Olena 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 Olena. If not, see <http://www.gnu.org/licenses/>. +// +// As a special exception, you may use this file as part of a free +// software project 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_TOPO_CONNECTIVITY_NUMBER_2D_HH +# define MLN_TOPO_CONNECTIVITY_NUMBER_2D_HH + +/// \file +/// \brief 2D connectivity numbers computation. + +# include <mln/core/concept/image.hh> + +# include <mln/core/alias/neighb2d.hh> + +# include <mln/value/int_u8.hh> + +// FIXME: This file includes the routine mln::connectivity_number_2d, +// which should be moved into its own file. +# include <mln/topo/is_simple_2d.hh> + + +// FIXME: This implementation used the LUT-based (mask-based) +// computation of 2D connectivity numbers, which may is fast but may +// be inexact on the border of an image. We shoud rename these +// routines with a `_fast' suffix. + +namespace mln +{ + + namespace topo + { + + /** Type of a connectivity number. + + Note: The maximun number of connected components in the + neighborhood of a point is necessarily lower or equal to half + the number of neighbors. This number fits on an + mln::value::int_u8 when the dimension is lower or equal to + 5. */ + typedef mln::value::int_u8 conn_number_t; + + + /** Compute the 2D connectivity number of \a p within \a ima + according to the 4-connectivity. If \a ref_val is set to \c + true, compute the number w.r.t. the foreground, otherwise + compute it w.r.t. the background. + + \param ima The image on which the connectivity number is + computed. + \param p The site the connectivity number of which is + computed. + \param ref_val The reference value, telling whether the + foreground (true) or the background (false) is + considered. */ + template<typename I> + conn_number_t + connectivity_number_2d_c4(const Image<I>& ima, const mln_psite(I)& p, + bool ref_val); + + /** Compute the 2D connectivity number of \a p within \a ima + according to the 8-connectivity. If \a ref_val is set to \c + true, compute the number w.r.t. the foreground, otherwise + compute it w.r.t. the background. + + \param ima The image on which the connectivity number is + computed. + \param p The site the connectivity number of which is + computed. + \param ref_val The reference value, telling whether the + foreground (true) or the background (false) is + considered. */ + template<typename I> + conn_number_t + connectivity_number_2d_c8(const Image<I>& ima, const mln_psite(I)& p, + bool ref_val); + + + +# ifndef MLN_INCLUDE_ONLY + + template<typename I> + conn_number_t + connectivity_number_2d_c4(const Image<I>& ima, const mln_psite(I)& p, + bool ref_val) + { + // Create a copy of mln::c4()'s own neighborhood to avoid + // thread-unsafe accesses to this neighborhood. + neighb2d nbh = c4(); + return mln::connectivity_number_2d(ima, nbh, p, ref_val); + } + + template<typename I> + conn_number_t + connectivity_number_2d_c8(const Image<I>& ima, const mln_psite(I)& p, + bool ref_val) + { + // Create a copy of mln::c8()'s own neighborhood to avoid + // thread-unsafe accesses to this neighborhood. + neighb2d nbh = c8(); + return mln::connectivity_number_2d(ima, nbh, p, ref_val); + } + +# endif // MLN_INCLUDE_ONLY + + } // end of namespace mln::topo + +} // end of namespace mln + +#endif // ! MLN_TOPO_CONNECTIVITY_NUMBER_2D_HH diff --git a/milena/mln/topo/is_simple_2d.hh b/milena/mln/topo/is_simple_2d.hh index 18ffe78..f93bc7c 100644 --- a/milena/mln/topo/is_simple_2d.hh +++ b/milena/mln/topo/is_simple_2d.hh @@ -1,4 +1,4 @@ -// Copyright (C) 2008, 2009 EPITA Research and Development Laboratory (LRDE) +// Copyright (C) 2008, 2009, 2011 EPITA Research and Development Laboratory (LRDE) // // This file is part of Olena. // @@ -139,13 +139,18 @@ namespace mln const N& nbh = exact(nbh_); unsigned res = 0; + unsigned mask = 1; mln_fwd_niter(neighb2d) n(c8(), p); for_all(n) - { - res = (res << 1); - if (ima.has(n) && ima(n) == b) - res = res | 1; - } + { + /* FIXME: The `ima.has(n)' predicate is not meaningful, as the + computation below is wrong as soon as `p' has a number of + neighbors other than 8. We should instead abort or warn if + for any `n' we don't have `ima.has(n)'. */ + if (ima.has(n) && ima(n) == b) + res = res | mask; + mask = mask << 1; + } unsigned number; if (nbh == c4()) diff --git a/milena/mln/topo/is_simple_point2d.hh b/milena/mln/topo/is_simple_point2d.hh index 219789e..8d0d7dd 100644 --- a/milena/mln/topo/is_simple_point2d.hh +++ b/milena/mln/topo/is_simple_point2d.hh @@ -1,4 +1,4 @@ -// Copyright (C) 2010 EPITA Research and Development Laboratory (LRDE) +// Copyright (C) 2010, 2011 EPITA Research and Development Laboratory (LRDE) // // This file is part of Olena. // diff --git a/milena/tests/topo/Makefile.am b/milena/tests/topo/Makefile.am index 608ac92..d9d2096 100644 --- a/milena/tests/topo/Makefile.am +++ b/milena/tests/topo/Makefile.am @@ -19,13 +19,18 @@ include $(top_srcdir)/milena/tests/tests.mk SUBDIRS = skeleton +## FIXME: Also add tests for is_simple_cell, detach_cell, +## is_simple_point2d and detach_point. + check_PROGRAMS = \ complex \ + connectivity_numbers_2d \ detach_pair \ is_facet \ is_simple_pair complex_SOURCES = complex.cc +connectivity_numbers_2d_SOURCES = connectivity_numbers_2d.cc detach_pair_SOURCES = detach_pair.cc is_facet_SOURCES = is_facet.cc is_simple_pair_SOURCES = is_simple_pair.cc diff --git a/milena/sandbox/lazzara/afp/micro_films/keep_background.cc b/milena/tests/topo/connectivity_numbers_2d.cc similarity index 51% copy from milena/sandbox/lazzara/afp/micro_films/keep_background.cc copy to milena/tests/topo/connectivity_numbers_2d.cc index 78373ad..599c02a 100644 --- a/milena/sandbox/lazzara/afp/micro_films/keep_background.cc +++ b/milena/tests/topo/connectivity_numbers_2d.cc @@ -1,4 +1,4 @@ -// Copyright (C) 2009 EPITA Research and Development Laboratory (LRDE) +// Copyright (C) 2011 EPITA Research and Development Laboratory (LRDE) // // This file is part of Olena. // @@ -23,63 +23,65 @@ // exception does not however invalidate any other reasons why the // executable file might be covered by the GNU General Public License. - /// \file -/// -/// Keep the background from a binary image. +/// \brief Exercise the fast (LUT-based) computation of 2D +/// connectivity numbers. #include <mln/core/image/image2d.hh> #include <mln/core/alias/neighb2d.hh> +#include <mln/make/box2d.hh> -#include <mln/pw/all.hh> -#include <mln/core/image/dmorph/image_if.hh> +#include <mln/topo/connectivity_number_2d.hh> #include <mln/data/fill.hh> -#include <mln/io/pbm/all.hh> -#include <mln/labeling/blobs.hh> #include <mln/logical/not.hh> -#include <mln/value/label_16.hh> - -#include <tools/usage.hh> - - -const char *args_desc[][2] = -{ - { "input.pbm", "A binary image. Objects are set to 'true'." }, - { 0, 0 } -}; - - -int main(int argc, char *argv[]) +int +main() { using namespace mln; - if (argc != 3) - return tools::usage(argv, - "Extract the background from a binary image.", - "input.pbm output.pbm", - args_desc, "A binary image. Background is set to 'false'."); - - image2d<bool> input; - io::pbm::load(input, argv[1]); - - logical::not_inplace(input); - - typedef value::label_16 V; - V nlabels; - image2d<V> lbl = labeling::blobs(input, c8(), nlabels); - - image2d<bool> output; - initialize(output, input); - - V bg_lbl = lbl(literal::origin); - - data::fill(output, false); - data::fill((output | (pw::value(lbl) == pw::cst(bg_lbl))).rw(), true); - - io::pbm::save(output, argv[2]); + // Exercise the computation of 2D connectivity numbers using the + // look-up table. + box2d b = make::box2d(-1, -1, + +1, +1); + image2d<bool> ima(b); + data::fill(ima, false); + + point2d p(0, 0); + mln_niter_(neighb2d) n(c4(), p); + for_all(n) + ima(n) = true; + /* Test case 1. + ima = + + - | - + | - | + - | - + */ + mln_assertion(topo::connectivity_number_2d_c4(ima, p, true) == 4); + mln_assertion(topo::connectivity_number_2d_c8(ima, p, true) == 1); + + logical::not_inplace(ima); + ima.at_ (0, 0) = false; + /* Test case 2. + ima = + + | - | + - - - + | - | + */ + mln_assertion(topo::connectivity_number_2d_c4(ima, p, true) == 0); + mln_assertion(topo::connectivity_number_2d_c8(ima, p, true) == 4); + + + /* FIXME: Also exercise the direct computation of connectivity + numbers, using the number of connected components around the + point in the foreground and the background. + + Possibly move this part in another test, especially if the + corresponding routine is located in another file. */ + // ... } - -- 1.7.2.5