* mln/make/graph.hh: use an adjacency matrix and a neighborhood. * mln/make/region_adjacency_graph.hh: make a graph from a watershed image. * tests/make/Makefile.am, * tests/make/graph.cc, * tests/make/region_adjacency_graph.cc: add new tests. --- milena/ChangeLog | 13 ++ milena/mln/make/graph.hh | 84 ++++++++---- milena/mln/make/region_adjacency_graph.hh | 202 +++++++++++++++++++++++++++ milena/mln/util/graph.hh | 10 ++ milena/tests/make/Makefile.am | 6 +- milena/tests/make/graph.cc | 58 ++++++++ milena/tests/make/region_adjacency_graph.cc | 59 ++++++++ 7 files changed, 403 insertions(+), 29 deletions(-) create mode 100644 milena/mln/make/region_adjacency_graph.hh create mode 100644 milena/tests/make/graph.cc create mode 100644 milena/tests/make/region_adjacency_graph.cc diff --git a/milena/ChangeLog b/milena/ChangeLog index 7797b25..2282bcd 100644 --- a/milena/ChangeLog +++ b/milena/ChangeLog @@ -1,3 +1,16 @@ +2009-02-16 Guillaume Lazzara <z@lrde.epita.fr> + + Fix make::graph and add make::region_adjacency_graph. + + * mln/make/graph.hh: use an adjacency matrix and a neighborhood. + + * mln/make/region_adjacency_graph.hh: make a graph from a watershed + image. + + * tests/make/Makefile.am, + * tests/make/graph.cc, + * tests/make/region_adjacency_graph.cc: add new tests. + 2009-02-13 Fabien Freling <fabien.freling@lrde.epita.fr> Add unit test for n_max.hh. diff --git a/milena/mln/make/graph.hh b/milena/mln/make/graph.hh index df76416..c9dddb1 100644 --- a/milena/mln/make/graph.hh +++ b/milena/mln/make/graph.hh @@ -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 @@ -34,6 +35,11 @@ /// /// \sa transform::influence_zone_geodesic. +# include <mln/core/concept/image.hh> +# include <mln/core/concept/neighborhood.hh> +# include <mln/core/image/image2d.hh> +# include <mln/core/alias/box2d.hh> +# include <mln/extension/adjust_fill.hh> # include <mln/util/graph.hh> namespace mln @@ -48,8 +54,10 @@ namespace mln /// \param[in] nlabels number of influence zone in \p iz. /// /// \return util::graph Graph based on the adjacency of the influence zones. - template <typename I> - util::graph graph(const Image<I>& iz, mln_value(I) nlabels); + template <typename I, typename N> + util::graph + graph(const Image<I>& iz_, const Neighborhood<N>& nbh, + mln_value(I) nlabels); @@ -59,53 +67,71 @@ namespace mln namespace internal { - template <typename I> + template <typename I, typename N> void - graph_tests(const Image<I>& iz, mln_value(I)) + graph_tests(const Image<I>& iz, const Neighborhood<N>& nbh, + mln_value(I)) { mln_precondition(exact(iz).is_valid()); - + mln_precondition(exact(nbh).is_valid()); (void) iz; + (void) nbh; } } // end of namespace mln::make::internal - namespace impl { namespace generic { - template <typename I> + template <typename I, typename N> util::graph - graph(const Image<I>& iz_, mln_value(I) nlabels) + graph(const Image<I>& iz_, const Neighborhood<N>& nbh_, + mln_value(I) nlabels) { trace::entering("make::impl::generic::graph"); - internal::graph_tests(iz_, nlabels); + internal::graph_tests(iz_, nbh_, nlabels); const I& iz = exact(iz_); + const N& nbh = exact(nbh_); - util::graph g; - g.add_vertices(nlabels.next()); + mln::image2d<bool> adj(mln::box2d(nlabels.next(), nlabels.next())); + data::fill(adj, false); + typedef mln_value(I) L; mln_piter(I) p(iz.domain()); + mln_niter(N) n(nbh, p); for_all(p) { - // Checking 'forward' neighboors and create an edge if necessary. - for (unsigned dim = 0; dim < mln_site_(I)::dim; ++dim) + L l1 = iz(p); + for_all(n) { - mln_site(I) n = p; - ++n[dim]; - - // FIXME: check that calling iz.domain().has() is correct - // and that we don't prefer iz.has(). - if (iz.domain().has(n) && iz(p) != iz(n)) - g.add_edge(iz(p), iz(n)); + if (iz.domain().has(n)) + { + L l2 = iz(n); + if (iz(n) != iz((p))) + { + // l2 is adjacent to l1 + if (l2 < l1) + adj(point2d(l1,l2)) = true; + else + adj(point2d(l2,l1)) = true; + } + } } } + // Construct graph. + util::graph g; + g.add_vertices(nlabels.next()); + for (unsigned i = 0; i < geom::nrows(adj); ++i) + for (unsigned j = 0; j < i; ++j) + if (adj(point2d(i,j))) + g.add_edge(i, j); + trace::exiting("make::impl::generic::graph"); return g; } @@ -119,11 +145,12 @@ namespace mln namespace internal { - template <typename I> + template <typename I, typename N> util::graph - graph_dispatch(const Image<I>& iz, mln_value(I) nlabels) + graph_dispatch(const Image<I>& iz, const Neighborhood<N>& nbh, + mln_value(I) nlabels) { - return make::impl::generic::graph(iz, nlabels); + return make::impl::generic::graph(iz, nbh, nlabels); } } // end of namespace mln::make::internal @@ -132,16 +159,17 @@ namespace mln // Facade - template <typename I> + template <typename I, typename N> inline util::graph - graph(const Image<I>& iz, mln_value(I) nlabels) + graph(const Image<I>& iz, const Neighborhood<N>& nbh, + mln_value(I) nlabels) { trace::entering("make::graph"); - internal::graph_tests(iz, nlabels); + internal::graph_tests(iz, nbh, nlabels); - util::graph g = internal::graph_dispatch(iz, nlabels); + util::graph g = internal::graph_dispatch(iz, nbh, nlabels); trace::exiting("make::graph"); return g; diff --git a/milena/mln/make/region_adjacency_graph.hh b/milena/mln/make/region_adjacency_graph.hh new file mode 100644 index 0000000..695174d --- /dev/null +++ b/milena/mln/make/region_adjacency_graph.hh @@ -0,0 +1,202 @@ +// Copyright (C) 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. +// reasons why the executable file might be covered by the GNU General +// Public License. + +#ifndef MLN_MAKE_REGION_ADJACENCY_GRAPH_HH +# define MLN_MAKE_REGION_ADJACENCY_GRAPH_HH + +/// \file mln/make/region_adjacency_graph.hh +/// +/// Create a region_adjacency_graph from a watershed image. +/// +/// \sa morpho::meyer_wst. + +# include <mln/core/concept/image.hh> +# include <mln/core/concept/neighborhood.hh> +# include <mln/core/image/image2d.hh> +# include <mln/core/alias/box2d.hh> +# include <mln/extension/adjust_fill.hh> +# include <mln/util/graph.hh> + +namespace mln +{ + + namespace make + { + + /// Create a region adjacency graph from a watershed image. + /// + /// \param[in] wshd watershed image. + /// \param[in] nbasins number of influence zone in \p wshd. + /// + /// \return util::graph Graph based on the adjacency of the influence zones. + template <typename I, typename N> + util::graph + region_adjacency_graph(const Image<I>& wshd_, + const Neighborhood<N>& nbh, + mln_value(I) nbasins); + + + +# ifndef MLN_INCLUDE_ONLY + + + namespace internal + { + + template <typename I, typename N> + void + region_adjacency_graph_tests(const Image<I>& wshd, + const Neighborhood<N>& nbh, + mln_value(I)) + { + mln_precondition(exact(wshd).is_valid()); + mln_precondition(exact(nbh).is_valid()); + (void) wshd; + (void) nbh; + } + + } // end of namespace mln::make::internal + + + namespace impl + { + + namespace generic + { + + template <typename I, typename N> + util::graph + region_adjacency_graph(const Image<I>& wshd_, + const Neighborhood<N>& nbh_, + mln_value(I) nbasins) + { + trace::entering("make::impl::generic::region_adjacency_graph"); + + internal::region_adjacency_graph_tests(wshd_, nbh_, nbasins); + const I& wshd = exact(wshd_); + const N& nbh = exact(nbh_); + + mln::image2d<bool> adj(mln::box2d(nbasins.next(), nbasins.next())); + data::fill(adj, false); + extension::adjust_fill(wshd, nbh, 0u); + + typedef mln_value(I) L; + L l1, l2; + mln_piter(I) p(wshd.domain()); + mln_niter(N) n(nbh, p); + for_all(p) + { + if (wshd(p) != 0u) + continue; + // p is in the watershed line. + l1 = l2 = 0; + for_all(n) + if (wshd.has(n) && wshd(n) != 0u) + { + if (l1 == 0u) // First label to be stored. + l1 = wshd(n); + else + if (wshd(n) != l1) // Useless: && l2 == 0) + { // Second label to be stored. + mln_invariant(l2 == 0u); + l2 = wshd(n); + break; + } + } + if (l2 == 0u || l1 == 0u) + continue; + if (l2 < l1) + std::swap(l1, l2); + + // adjacency l1 l2 + adj(point2d(l2,l1)) = true; + } + + // Construct graph. + util::graph g; + g.add_vertices(nbasins.next()); + for (unsigned i = 1; i < geom::nrows(adj); ++i) + for (unsigned j = 1; j < i; ++j) + if (adj(point2d(i,j))) + g.add_edge(i, j); + + + trace::exiting("make::impl::generic::region_adjacency_graph"); + return g; + } + + } // end of namespace mln::make::impl::generic + + } // end of namespace mln::make::impl + + + + namespace internal + { + + template <typename I, typename N> + util::graph + region_adjacency_graph_dispatch(const Image<I>& wshd, + const Neighborhood<N>& nbh, + mln_value(I) nbasins) + { + return make::impl::generic::region_adjacency_graph(wshd, nbh, nbasins); + } + + } // end of namespace mln::make::internal + + + + // Facade + + template <typename I, typename N> + inline + util::graph + region_adjacency_graph(const Image<I>& wshd, + const Neighborhood<N>& nbh, + mln_value(I) nbasins) + { + trace::entering("make::region_adjacency_graph"); + + internal::region_adjacency_graph_tests(wshd, nbh, nbasins); + + util::graph g = internal::region_adjacency_graph_dispatch(wshd, nbh, nbasins); + + trace::exiting("make::region_adjacency_graph"); + return g; + } + + +# endif // ! MLN_INCLUDE_ONLY + + + } // end of namespace mln::make + +} // end of namespace mln + + +#endif // ! MLN_MAKE_REGION_ADJACENCY_GRAPH_HH diff --git a/milena/mln/util/graph.hh b/milena/mln/util/graph.hh index 897deb4..f95e1e8 100644 --- a/milena/mln/util/graph.hh +++ b/milena/mln/util/graph.hh @@ -71,8 +71,11 @@ namespace mln vertices_t vertices_; /// The edges. edges_t edges_; + +# ifndef NDEBUG /// An index of the set of edges, for fast-access purpose. edges_set_t edges_set_; +# endif // ! NDEBUG }; } // end of namespace mln::internal @@ -383,8 +386,10 @@ namespace mln unsigned graph::add_edge(unsigned id_v1, unsigned id_v2) { + //FIXME: to be removed! We should not check that, except in without NDEBUG. // Does this edge already exist in the graph? edge_data_t edge(id_v1, id_v2); +# ifndef NDEBUG if (data_->edges_set_.find(edge) != data_->edges_set_.end ()) { // Return the erroneous value. @@ -392,6 +397,7 @@ namespace mln } else { +# endif // ! NDEBUG // Otherwise insert it into the graph. /* FIXME: This is not thread-proof (these two lines should form an atomic section). */ @@ -404,7 +410,11 @@ namespace mln data_->vertices_[edge.second()].push_back(id); return id; + +# ifndef NDEBUG } +# endif // ! NDEBUG + } inline diff --git a/milena/tests/make/Makefile.am b/milena/tests/make/Makefile.am index 913867c..95eb5ea 100644 --- a/milena/tests/make/Makefile.am +++ b/milena/tests/make/Makefile.am @@ -4,18 +4,22 @@ include $(top_srcdir)/milena/tests/tests.mk check_PROGRAMS = \ dual_neighb \ + graph \ h_mat \ image2d \ image3d \ mat \ + region_adjacency_graph \ w_window \ w_window_directional -dual_neighb_SOURCES = dual_neighb.cc +dual_neighb_SOURCES = dual_neighb.c +graph_SOURCES = graph.cc h_mat_SOURCES = h_mat.cc image2d_SOURCES = image2d.cc image3d_SOURCES = image3d.cc mat_SOURCES = mat.cc +region_adjacency_graph_SOURCES = region_adjacency_graph.cc w_window_SOURCES = w_window.cc w_window_directional_SOURCES = w_window_directional.cc diff --git a/milena/tests/make/graph.cc b/milena/tests/make/graph.cc new file mode 100644 index 0000000..bb88706 --- /dev/null +++ b/milena/tests/make/graph.cc @@ -0,0 +1,58 @@ +// Copyright (C) 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/make/graph.cc +/// +/// Tests on mln::make::graph. + +#include <mln/make/image2d.hh> +#include <mln/core/alias/neighb2d.hh> +#include <mln/util/graph.hh> +#include <mln/make/graph.hh> +#include <mln/value/label_8.hh> + + +int main() +{ + using namespace mln; + + value::label_8 vals[9] = { 1, 1, 3, + 1, 2, 3, + 1, 0, 4 }; + + image2d<value::label_8> ima = make::image2d(vals); + + util::graph g = make::graph(ima, c4(), 4u); + + mln_assertion(g.e_nmax() == 7u); + mln_assertion(g.v_nmax() == 5u); + mln_assertion(g.v_nmax_nbh_edges(0) == 3); + mln_assertion(g.v_nmax_nbh_edges(1) == 3); + mln_assertion(g.v_nmax_nbh_edges(2) == 3); + mln_assertion(g.v_nmax_nbh_edges(3) == 3); + mln_assertion(g.v_nmax_nbh_edges(4) == 2); +} diff --git a/milena/tests/make/region_adjacency_graph.cc b/milena/tests/make/region_adjacency_graph.cc new file mode 100644 index 0000000..7f8cb12 --- /dev/null +++ b/milena/tests/make/region_adjacency_graph.cc @@ -0,0 +1,59 @@ +// Copyright (C) 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/make/graph.cc +/// +/// Tests on mln::make::region_adjacency_graph. + +#include <mln/core/alias/neighb2d.hh> + +#include <mln/util/graph.hh> + +#include <mln/value/label_8.hh> + +#include <mln/make/image2d.hh> +#include <mln/make/region_adjacency_graph.hh> + +int main() +{ + using namespace mln; + + value::label_8 vals[16] = { 1, 0, 3, 3, + 1, 0, 0, 0, + 0, 0, 4, 4, + 2, 2, 0, 4 }; + + image2d<value::label_8> ima = make::image2d(vals); + + util::graph g = make::region_adjacency_graph(ima, c4(), 4u); + + mln_assertion(g.e_nmax() == 4u); + mln_assertion(g.v_nmax() == 5u); + mln_assertion(g.v_nmax_nbh_edges(0) == 0); + for (unsigned i = 1; i < 4; ++i) + mln_assertion(g.v_nmax_nbh_edges(i) == 2); +} -- 1.5.6.5