Index: olena/ChangeLog from Niels Van Vliet &lt;niels(a)lrde.epita.fr&gt; * oln/morpho/attribute_closing_opening_map.hh: Add file. Attribute closing and opening using std::map. * oln/morpho/attribute_closing_opening_map.hxx: Add file. * oln/utils/special_points.hh: Add file. Point used as a state. * tests/morpho/attributes: Add file. Add tests on attribute closing and opening. Index: olena/oln/morpho/attribute_closing_opening_map.hxx --- olena/oln/morpho/attribute_closing_opening_map.hxx Tue, 10 Feb 2004 19:47:05 +0100 van-vl_n () +++ olena/oln/morpho/attribute_closing_opening_map.hxx Tue, 10 Feb 2004 19:18:13 +0100 van-vl_n (oln/j/48_attribute_ 644) @@ -0,0 +1,194 @@ +// Copyright (C) 2004 EPITA Research and Development Laboratory +// +// 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, 59 Temple Place - Suite 330, 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. + + +namespace oln +{ + namespace morpho + { + template <class I, class D, class Env> + template <class N> + f_tarjan_map<I, D, Env>::f_tarjan_map(bool is_closing, + const typename f_tarjan_map<I, D, Env>::input_type& input, + const abstract::neighborhood<N>& ng, + const typename f_tarjan_map<I, D, Env>::lambda_type& lambda, + const Env & env) : + is_closing(is_closing), + input(input), + lambda(lambda), + parent(input.size()), + is_proc(input.size()), + output(input.size()), + env(env) + { + // init S and parent + typedef typename std::vector<point_type> vector_type; + vector_type S(input.npoints()); + if (is_closing) + utils::distrib_sort(input, S); + else + utils::distrib_sort_inv(input, S); + + level::fill(parent, inactive()); + level::fill(is_proc, false); + + // array S contains sorted pixel list + make_set(S[0]); + is_proc[S[0]] = true; + + for (int ip = 1; ip < int(S.size()); ++ip) + { + point_type p = S[ip]; + + // p_ is the pixel just processed before p + point_type p_ = S[ip - 1]; + if (input[p] != input[p_]) + { + // for all the previous layer + for (int iq = ip - 1; iq >= 0; --iq) + { + point_type q = S[iq]; + if (input[q] != input[p_]) + break; + // if the attribute is 'reached', we do not need + // it anymore + if (parent[q] == active() && !(auxdata[q] < lambda)) + { + parent[q] = inactive(); + auxdata.erase(q); + } + } + } + make_set(p); + + oln_neighb_type(N) n(ng, p); + for_all(n) + if (input.hold(n) && is_proc[n]) + do_union(n, p); + + is_proc[p] = true; + } + + // resolving phase in reverse sort order + + for (int ip = int(S.size()) - 1; ip >= 0; --ip) + { + point_type p = S[ip]; + if (parent[p] == active() || parent[p] == inactive()) + output[p] = input[p]; + else + output[p] = output[parent[p]]; + } + } + + template <class I, class D, class Env> + const typename f_tarjan_map<I, D, Env>::point_type + f_tarjan_map<I, D, Env>::inactive() + { + static const point_type it = utils::internal::mk_point_looking_like<point_type>(-2); + return it; + } + + template <class I, class D, class Env> + const typename f_tarjan_map<I, D, Env>::point_type + f_tarjan_map<I, D, Env>::active() + { + static const point_type it = utils::internal::mk_point_looking_like<point_type>(-1); + return it; + } + + template <class I, class D, class Env> + void + f_tarjan_map<I, D, Env>::make_set(const typename f_tarjan_map<I, D, Env>::point_type& x) + { + precondition(parent[x] == inactive()); + parent[x] = active(); + auxdata[x] = D(input, x, env); + } + + template <class I, class D, class Env> + void + f_tarjan_map<I, D, Env>::link(const typename f_tarjan_map<I, D, Env>::point_type& x, + const typename f_tarjan_map<I, D, Env>::point_type& y) + { + if (parent[x] == active() && parent[y] == active()) + { + auxdata[y] += auxdata[x]; + auxdata.erase(x); + } + else + if (parent[x] == active()) + auxdata.erase(x); + else + { + parent[y] = inactive(); + auxdata.erase(y); + } + parent[x] = y; + } + + template <class I, class D, class Env> + typename f_tarjan_map<I, D, Env>::point_type + f_tarjan_map<I, D, Env>::find_root(const typename f_tarjan_map<I, D, Env>::point_type& x) + { + if (parent[x] != active() && parent[x] != inactive()) + { + parent[x] = find_root(parent[x]); + return parent[x]; + } + return x; + } + + template <class I, class D, class Env> + bool + f_tarjan_map<I, D, Env>::equiv(const typename f_tarjan_map<I, D, Env>::point_type& x, + const typename f_tarjan_map<I, D, Env>::point_type& y) const + { + return input[x] == input[y] || parent[x] == active(); + } + + template <class I, class D, class Env> + void + f_tarjan_map<I, D, Env>::do_union(const typename f_tarjan_map<I, D, Env>::point_type& n, + const typename f_tarjan_map<I, D, Env>::point_type& p) + { + point_type r = find_root(n); + if (r != p) + { + if (equiv(r, p)) + link(r, p); + else + if (parent[p] == active()) + { + parent[p] = inactive(); + auxdata.erase(p); + } + } + } + } // end of namespace morpho +} // end of namespace oln + Index: olena/oln/morpho/attribute_closing_opening_map.hh --- olena/oln/morpho/attribute_closing_opening_map.hh Tue, 10 Feb 2004 19:47:05 +0100 van-vl_n () +++ olena/oln/morpho/attribute_closing_opening_map.hh Tue, 10 Feb 2004 19:18:13 +0100 van-vl_n (oln/j/49_attribute_ 644) @@ -0,0 +1,151 @@ +// Copyright (C) 2004 EPITA Research and Development Laboratory +// +// 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, 59 Temple Place - Suite 330, 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. + +#ifndef OLENA_MORPHO_ATTRIBUTE_CLOSING_OPENING_MAP +# define OLENA_MORPHO_ATTRIBUTE_CLOSING_OPENING_MAP +# include <oln/morpho/attributes.hh> +# include <oln/level/fill.hh> +# include <oln/basics2d.hh> +# include <ntg/int.hh> +# include <oln/utils/histogram.hh> +# include <oln/utils/special_points.hh> + +# include <iterator> +# include <vector> +# include <map> +# include <algorithm> +# include <utility> + + +namespace oln +{ + namespace morpho + { + + /*! Attribute closing using map. Smaller memory usage, but + * slower computation than the attribute_closing_opening + * + * See "Fast morphological attribute operations using Tarjan's union-find + * algorithm" by Michael H. F. Wilkinson and Jos B. T. M. Roerdink + */ + template <class I, class D, class Env = morpho::tarjan::NullEnv> + struct f_tarjan_map + { + public: + typedef abstract::image<I> input_type; + typedef oln_concrete_type(I) img_type; + + typedef oln_point_type(input_type) point_type; + typedef oln_value_type(input_type) value_type; + typedef typename mute<input_type, point_type>::ret parent_type; + typedef typename mute<input_type, bool>::ret is_proc_type; + typedef typename D::lambda_type lambda_type; + + // e.g., + // when I is image2d<int_u8> and D is area_type, we've got: + // +--------------+------------------+ + // | input_type | image2d<int_u8> | + // | point_type | point2d | + // | parent_type | image2d<point2d> | + // | is_proc_type | image2d<bool> | + // | lambda_type | int | + // +--------------+------------------+ + + template <class N> + f_tarjan_map(bool is_closing, + const input_type& input, + const abstract::neighborhood<N>& ng, + const lambda_type& lambda, + const Env & env = Env()); + + template<typename DestValue> + typename mute<I, DestValue>::ret + res() + { + return output; + } + protected: + + static const point_type + inactive(); + + static const point_type + active(); + + void + make_set(const point_type& x); + + void + link(const point_type& x, const point_type& y); + + point_type + find_root(const point_type& x); + + bool + equiv(const point_type& x, const point_type& y) const; + + void + do_union(const point_type& n, const point_type& p); + + const bool is_closing; + const input_type& input; + lambda_type lambda; + parent_type parent; + is_proc_type is_proc; + img_type output; + std::map<point_type, D, oln::internal::default_less<point_type> > auxdata; + Env env; + }; + + + /*! Attribute closing using map. Smaller memory usage, but + * slower computation than the attribute_closing_opening + * + * See "Fast morphological attribute operations using Tarjan's union-find + * algorithm" by Michael H. F. Wilkinson and Jos B. T. M. Roerdink + */ + template <typename DestValue, class I, class D, class Env, class N> + typename mute<I, DestValue>::ret + tarjan_map(bool is_closing, + const abstract::image<I>& input, + const abstract::neighborhood<N>& ng, + const typename D::lambda_type& lambda, + const Env & env = Env()) + { + oln::morpho::f_tarjan_map<I, D, Env > t(is_closing, + input, + ng, + lambda, + env); + return t. template res<DestValue>(); + } + } // end of namespace morpho +} // end of namespace oln + +#include "attribute_closing_opening_map.hxx" + +#endif Index: olena/oln/utils/special_points.hh --- olena/oln/utils/special_points.hh Tue, 10 Feb 2004 19:47:05 +0100 van-vl_n () +++ olena/oln/utils/special_points.hh Tue, 10 Feb 2004 19:18:14 +0100 van-vl_n (oln/j/50_special_po 644) @@ -0,0 +1,58 @@ +// Copyright (C) 2004 EPITA Research and Development Laboratory +// +// 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, 59 Temple Place - Suite 330, 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. + +#ifndef OLENA_UTILS_SPECIAL_POINTS_HH +# define OLENA_UTILS_SPECIAL_POINTS_HH + +# include <oln/core/abstract/point.hh> + +namespace oln { + + namespace utils { + + namespace internal { + /*! Creates a point that is used as a state. + * + * This function should be called with a value unreachable + * for example a negative one. + */ + template <class P> + P + mk_point_looking_like(coord value) + { + P p; + p.nth(0) = value; + return p; + } + + } // end of namespace internal + + } // end of namespace utils + +} // end of namespace oln + +#endif // ! OLENA_UTILS_SPECIAL_POINTS_HH Index: olena/tests/morpho/tests/attribute --- olena/tests/morpho/tests/attribute Tue, 10 Feb 2004 19:47:05 +0100 van-vl_n () +++ olena/tests/morpho/tests/attribute Tue, 10 Feb 2004 19:18:00 +0100 van-vl_n (oln/j/51_attribute 644) @@ -0,0 +1,109 @@ +// -*- c++ -*- + +#include <oln/basics2d.hh> +#include <oln/morpho/attribute_closing_opening.hh> +#include <oln/morpho/attribute_closing_opening_map.hh> +#include <oln/level/compare.hh> +#include <ntg/all.hh> +#include <oln/morpho/extrema_killer.hh> + +#include "check.hh" +#include "data.hh" + +using namespace oln; +using namespace ntg; + +#define OK_OR_FAIL \ + std::cout << "OK" << std::endl; \ + else \ + { \ + std::cout << "FAIL" << std::endl; \ + fail = true; \ + } + +//FIXME some algo are already checked. +bool +check_algo() +{ + bool fail(false); + + typedef image2d<int_u8> img_type; + typedef oln::morpho::tarjan::area_type<unsigned> area_type; + const area_type::lambda_type area = 100; + const neighborhood2d nb = neighb_c8(); + const oln::morpho::tarjan::NullEnv env; + + img_type lena = load(rdata("lena.pgm")); + img_type lena_sure_closing = oln::morpho::sure_minima_killer(lena, area, nb); + img_type lena_sure_opening = oln::morpho::sure_maxima_killer(lena, area, nb); + + img_type lena_tst_opening; + img_type lena_tst_closing; + + std::cerr << "testing tarjan_map..." << std::endl; + lena_tst_closing = morpho::tarjan_map<ntg::int_u8,img_type,area_type>(true, lena, nb, area, env); + lena_tst_opening= morpho::tarjan_map<ntg::int_u8,img_type,area_type>(false, lena, nb, area, env); + + + fail = fail || + !level::is_equal(lena_sure_closing, lena_tst_closing)|| + !level::is_equal(lena_sure_opening, lena_tst_opening); + + std::cerr << "fail:" << fail << std::endl; + + std::cerr << "testing fast_minima_killer..." << std::endl; + lena_tst_closing = oln::morpho::fast_minima_killer(lena, area, nb); + + fail = fail || + !level::is_equal(lena_sure_closing, lena_tst_closing); + std::cerr << "fail:" << fail << std::endl; + + std::cerr << "testing area_closin and area_opeing..." << std::endl; + lena_tst_closing = morpho::tarjan::area_closing(lena, nb, area); + lena_tst_opening = morpho::tarjan::area_opening(lena, nb, area); + fail = fail || + !level::is_equal(lena_sure_closing, lena_tst_closing)|| + !level::is_equal(lena_sure_opening, lena_tst_opening); + std::cerr << "fail:" << fail << std::endl; + //FIXME at least 1 other algo should be checked + + return fail; +} + + +bool +check_attribute() +{ + //FIXME attributes should be checked + return false; +} + + +bool +check_env() +{ + //FIXME env should be checked + return false; +} +bool +check() +{ + bool fail = false; + + std::cerr << "FIXME: check_attribute and check_env are empty." + << std::endl; + + std::cout << "check algo... " << std::flush; + if (check_algo() == false) + OK_OR_FAIL; + + std::cout << "check attribute... " << std::flush; + if (check_attribute() == false) + OK_OR_FAIL; + + std::cout << "check env... " << std::flush; + if (check_env() == false) + OK_OR_FAIL; + + return fail; +}