Index: olena/ChangeLog from Giovanni Palma <giovanni@lrde.epita.fr> * oln/topo/tarjan/tarjan.hh: Add comments. * oln/topo/tarjan/tarjan_with_attr.hh: Add comments. Correct the code. * oln/topo/combinatorial-map/cmap.hh: Make cmap use the good flat_zone. * oln/topo/tarjan/flat-zone.hh: Add new version of flat_zone. * oln/topo/tarjan/union.hh: Correct comments. * tests/topo/tests/cmap: Make the test use the good flat_zone. Index: olena/tests/topo/tests/cmap --- olena/tests/topo/tests/cmap Sun, 03 Aug 2003 21:08:04 +0200 burrus_n (oln/r/28_test-cmap. 1.8 640) +++ olena/tests/topo/tests/cmap Fri, 02 Apr 2004 16:36:54 +0200 palma_g (oln/r/28_test-cmap. 1.8 640) @@ -34,7 +34,7 @@ interpixel<input_t> ip(src); - flat_zone<input_t> cc(src); + obsolete::flat_zone<input_t> cc(src); cmap<input_t> cm(src, ip, cc); Index: olena/oln/topo/tarjan/union.hh --- olena/oln/topo/tarjan/union.hh Mon, 15 Mar 2004 17:40:54 +0100 van-vl_n (oln/r/33_union.hh 1.11 640) +++ olena/oln/topo/tarjan/union.hh Fri, 02 Apr 2004 16:48:26 +0200 palma_g (oln/r/33_union.hh 1.11 640) @@ -43,10 +43,7 @@ /*! Tarjan set. ** - ** \todo FIXME: a similar class is defined in - ** oln/morpho/attribute_union_find.hh (oln::morpho::tarjan::tarjan_set). - ** The one in morpho is more general. I think that this class should - ** be removed. + ** \todo FIXME: Obsolete since only obsolete::flat_zone use it. */ template< class I, class aux_data_type> struct tarjan_set Index: olena/oln/topo/tarjan/flat-zone.hh --- olena/oln/topo/tarjan/flat-zone.hh Mon, 15 Mar 2004 15:32:27 +0100 van-vl_n (oln/r/35_flat-zone. 1.12 640) +++ olena/oln/topo/tarjan/flat-zone.hh Fri, 02 Apr 2004 16:47:01 +0200 palma_g (oln/r/35_flat-zone. 1.12 640) @@ -1,12 +1,13 @@ -// Copyright (C) 2001, 2002, 2003, 2004 EPITA Research and Development Laboratory +// Copyright (C) 2001, 2002, 2003, 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 +// 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. // @@ -28,9 +29,10 @@ #ifndef OLENA_TOPO_TARJAN_FLAT_ZONE_HH # define OLENA_TOPO_TARJAN_FLAT_ZONE_HH -# include <oln/basics2d.hh> +# include <oln/basics.hh> +# include <oln/topo/tarjan/tarjan_with_attr.hh> # include <oln/topo/tarjan/union.hh> - +# include <oln/morpho/attributes.hh> # include <map> namespace oln { @@ -41,7 +43,10 @@ /*! Create an image of label of the flat zones. ** - ** \todo FIXME: many assertions are missing. + ** \param T Type of he input image. + ** \param DestType Data type of the output image (label type). + ** \param A Attribute you want to compute. + ** \param Exact Exact type of the class. ** ** \code ** #include <oln/basics2d.hh> @@ -53,6 +58,153 @@ ** typedef oln::image2d<ntg::int_u8> img_type; ** img_type in = oln::load(IMG_IN "test-cmap.pgm"); ** oln::topo::tarjan::flat_zone<img_type> z(in); + ** save(oln::convert::stretch_balance<ntg::int_u8>(z.get_compute(oln::neighb_c4()), 0, 255), + ** IMG_OUT "oln_topo_flat_zone.pgm"); + ** } + ** \endcode + ** \image html test-cmap_pgm.png "input image" + ** \image latex test-cmap_pgm.png "input image" + ** => + ** \image html oln_topo_flat_zone.png "output image" + ** \image latex oln_topo_flat_zone.png "output image" + */ + template<class T, + class DestType = unsigned, + class A = oln::morpho::attr::card_type<>, + class Exact = mlc::final> + struct flat_zone: + public abstract::tarjan_with_attr<typename mlc::exact_vt<flat_zone<T, DestType, A, Exact>, + Exact>::ret> + { + + typedef oln_point_type(T) point_type; ///< Type of input image. + typedef oln_value_type(T) data_type; ///< Data type of the input image. + typedef oln_concrete_type(T) image_type; ///< Concrete type of the input image. + + typedef DestType comp_type; ///< Type of components. + + typedef flat_zone<T, DestType, A, Exact> self_type; ///< Self type of the class. + typedef mlc_exact_vt_type(self_type, Exact) exact_type; ///< Exact type of the class. + typedef abstract::tarjan_with_attr<exact_type> super_type; ///< Type of parent class. + + friend class super_type; + friend class super_type::super_type; + /*! + ** \brief Constructor. + ** + ** \arg ima Input image. + ** \arg env Environment to use to compute the attributes. + */ + flat_zone(const image_type &ima, + const attr_env_type(A) &env = attr_env_type(A)()): super_type(ima, env) + { + } + + std::vector<point_type> + get_processing_order_impl() + { + std::vector<point_type> res; + oln_iter_type(image_type) it(input_); + + res.reserve(input_.npoints()); + for_all(it) + res.push_back(it); + return res; + } + + protected: + + /*! + ** \brief Implementation of mark_set(). + ** + ** \arg x Root of the new component. + ** + ** \warning Do not call this method, use mark_set() instead. + */ + void + mark_set_impl(const point_type &x) + { + if (parent_.size() == parent_.capacity()) + { + capacity = parent_.capacity() + capacity_chunk; + parent_.reserve(capacity); + comp_value_.reserve(capacity); + } + to_comp_[x] = ncomps_ + 1; + data_.push_back(A(input_, x, env_)); + parent_.push_back(ncomps_ + 1); + comp_value_.push_back(ncomps_ + 1); + } + + /*! + ** \brief Implementation of uni(). + ** + ** \arg n A point of the first component. + ** \arg p A point of the second component. + ** + ** \warning Do not call this method, use uni() instead. + */ + void + uni_impl(const point_type& n, const point_type& p) + { + comp_type r = find_root(to_comp_[n]); + precondition(to_comp_[n] <= ncomps_); + precondition(to_comp_[p] <= (ncomps_ + 1)); + if (r != to_comp_[p]) + if (input_[n] == input_[p]) + { + if (to_comp_[p] == (ncomps_ + 1)) // first merge of p component + { + precondition(r < comp_value_.capacity()); + data_[r] += data_[to_comp_[p]]; + precondition(r <= ncomps_); + to_comp_[p] = r; + } + else + { + precondition(r < parent_.capacity()); + data_[parent_[to_comp_[p]]] += data_[parent_[r]]; + parent_[r] = parent_[to_comp_[p]]; + + } + } + } + }; + + /*! + ** \brief Traits specialization for flat_zone. + ** + ** \param T Type of he input image. + ** \param DestType Data type of the output image (label type). + ** \param A Attribute you want to compute. + ** \param Exact Exact type of the flat_zone class. + */ + template <typename T, typename DestType, typename A, typename Exact> + struct tarjan_traits<flat_zone<T, DestType, A, Exact> > + { + typedef T input_type; ///< Type of the input image. + typedef typename mute<T, DestType>::ret output_type; ///< Type of the output image. + typedef A attr_type; ///< Type of attribute to use. + }; + + /*! + ** \brief Namespace containing obsolete implementation of flat zone. + */ + namespace obsolete { + /*! Create an image of label of the flat zones. + ** + ** \todo FIXME: many assertions are missing. + ** + ** \code + ** #include <oln/basics2d.hh> + ** #include <oln/topo/tarjan/flat-zone.hh> + ** #include <oln/convert/stretch.hh> + ** + ** int main() + ** { + ** typedef oln::image2d<ntg::int_u8> img_type; + ** img_type in = oln::load(IMG_IN "test-cmap.pgm"); + ** oln::topo::tarjan::obsolete::flat_zone<img_type> z(in); ** save(oln::convert::stretch_balance<ntg::int_u8>(z.label, 0, 255), ** IMG_OUT "oln_topo_flat_zone.pgm"); ** } @@ -230,6 +382,8 @@ }; + } // end of namespace obsolete + } // end of namespace tarjan } // end of namespace topo Index: olena/oln/topo/combinatorial-map/cmap.hh --- olena/oln/topo/combinatorial-map/cmap.hh Mon, 15 Mar 2004 15:32:27 +0100 van-vl_n (oln/r/36_cmap.hh 1.13 640) +++ olena/oln/topo/combinatorial-map/cmap.hh Fri, 02 Apr 2004 16:46:39 +0200 palma_g (oln/r/36_cmap.hh 1.13 640) @@ -44,6 +44,7 @@ ** FIXME: The documentation is not good enough.\n ** FIXME: Real test are missing. ** FIXME: Some part of this file are inside "#if 0" comments. +** FIXME: This file force to keep an obsolete version of flat-zone. */ namespace oln { @@ -72,7 +73,7 @@ public: cmap(const I& input, const inter_pixel::interpixel<I>& ip, - tarjan::flat_zone<I>& cc) : + tarjan::obsolete::flat_zone<I>& cc) : ndarts_(0), zeta_(input.nrows() + 1, input.ncols() + 1), cc_(cc), @@ -358,7 +359,7 @@ private: unsigned ndarts_; zeta_type zeta_; - tarjan::flat_zone<I> & cc_; + tarjan::obsolete::flat_zone<I> &cc_; internal::level<unsigned> level_; internal::beta<unsigned> beta_; Index: olena/oln/topo/tarjan/tarjan_with_attr.hh --- olena/oln/topo/tarjan/tarjan_with_attr.hh Wed, 31 Mar 2004 19:11:41 +0200 palma_g (oln/m/46_tarjan_wit 1.1 644) +++ olena/oln/topo/tarjan/tarjan_with_attr.hh Fri, 02 Apr 2004 15:57:02 +0200 palma_g (oln/m/46_tarjan_wit 1.1 644) @@ -1,12 +1,12 @@ -// Copyright (C) 2001, 2002, 2003, 2004 EPITA Research and Development Laboratory +// 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 +// 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. // @@ -42,22 +42,57 @@ namespace topo { /// \brief Implementation of tarjan set. namespace tarjan { + /// Abstract classes for tarjan based algorithms. namespace abstract { + /*! + ** \brief Abstract class to perform a tarjan algorithm on an + ** image with attribute computing . + ** + ** \param Exact Exact type of the class. + */ template<class Exact> struct tarjan_with_attr: public tarjan<mlc_exact_vt_type(tarjan_with_attr<Exact>, Exact) > { - typedef oln_tarjan_input_type(Exact) input_type; - typedef oln_point_type(input_type) point_type; - typedef oln_value_type(input_type) data_type; - - typedef oln_concrete_type(input_type) image_type; - typedef oln_tarjan_output_type(Exact) image_out_type; - typedef oln_tarjan_attr_type(Exact) attr_type; - typedef attr_env_type(attr_type) env_type; - typedef oln_value_type(image_out_type) comp_type; + typedef oln_tarjan_input_type(Exact) input_type; ///< Type of input image. + typedef oln_point_type(input_type) point_type; ///< Point type of image to process. + typedef oln_value_type(input_type) data_type; ///< Data type of the input image. + + typedef oln_concrete_type(input_type) image_type; ///< Concrete type of the input image. + typedef oln_tarjan_output_type(Exact) image_out_type; ///< Type of output image. + typedef oln_tarjan_attr_type(Exact) attr_type; ///< Type of attribute to use. + typedef attr_env_type(attr_type) env_type; ///< Environment associated to attribute type. + typedef oln_value_type(image_out_type) comp_type; ///< Type of components. + + typedef mlc_exact_vt_type(tarjan_with_attr<Exact>, + Exact) exact_type; ///< Exact type of the class. + typedef tarjan<exact_type> super_type; ///< Type of parent class. + + // Make parent class able to call implementations. + friend class super_type; + + /*! + ** \brief Return the attribute value associated to a + ** component \a i. + */ + const attr_type &get_attr(const comp_type &i) const + { + return data_[find_root(i)]; + } + + protected: + /*! \brief Constructor. + ** + ** Initialization of data structures. + ** + ** \arg ima Image to process. + ** \arg env Environment to use. + ** + ** \warning This constructor is protected, because this + ** class is abstract. + */ tarjan_with_attr(const image_type &ima, const env_type &env): capacity_chunk((ima.npoints() < 100) ? ima.npoints() : (ima.npoints() / 100)), @@ -73,30 +108,26 @@ data_.reserve(capacity); } - // abstract methods - std::vector<point_type> get_processing_order() - { - mlc_dispatch(get_processing_order)(); - } - - void - mark_set(const point_type &x) - { - mlc_dispatch(mark_set)(x); - } - - void - uni(const point_type& n, const point_type& p) - { - mlc_dispatch(uni)(n, p); - } - - // tells if a point has been proceded - bool is_proc(const point_type &p) const + /*! + ** \brief Implementation of is_proc(). + ** + ** \arg p Point you want to check. + ** + ** \warning Do not call this method, use is_proc() instead. + */ + bool is_proc_impl(const point_type &p) const { return to_comp_[p] != ntg_sup_val(comp_type); }; + /*! + ** \brief Implementation of find_root(). + ** + ** \arg x The component you want to find the root. + ** + ** \warning Do not call this method, use find_root() + ** instead. + */ comp_type find_root(const comp_type& x) const { @@ -105,11 +136,17 @@ return x; } - // bool closing = true -> a closing is performed, - // an opening otherwise. + /*! + ** \brief Implementation of get_compute(). + ** + ** \arg Ng Neighborhood to use. + ** + ** \warning Do not call this method, use get_compute() + ** instead. + */ template<class N> image_out_type - get_compute(const oln::abstract::neighborhood<N> &Ng) + get_compute_impl(const oln::abstract::neighborhood<N> &Ng) { std::vector<point_type> I(get_processing_order()); @@ -167,20 +204,16 @@ return output; } - // access to attributes - // i index of component - const attr_type &get_attr(const comp_type &i) const - { - return data_[find_root(i)]; - } - - comp_type ncomps() const + /*! + ** \brief Implementation of ncomps_impl(). + ** + ** \warning Do not call this method, use ncomps() instead. + */ + comp_type ncomps_impl() const { return ncomps_; } - protected: - unsigned capacity_chunk; unsigned capacity; const image_type &input_; @@ -193,99 +226,6 @@ }; } // !abstract - - - template<class T, class DestType, class A, class Exact = mlc::final> - struct cc: - public abstract::tarjan_with_attr<typename mlc::exact_vt<cc<T, DestType, A, Exact>, - Exact>::ret> - { - - typedef oln_point_type(T) point_type; - typedef oln_value_type(T) data_type; - // typedef abstract::image<T> image_type; - typedef oln_concrete_type(T) image_type; - - typedef unsigned comp_type; - - typedef cc<T, DestType, A, Exact> self_type; /*< Self type of the class.*/ - typedef mlc_exact_vt_type(self_type, Exact) exact_type; - typedef abstract::tarjan_with_attr<exact_type> super_type; - - cc(const image_type &ima, - const attr_env_type(A) &env): super_type(ima, env) - { - } - - std::vector<point_type> get_processing_order_impl() - { - std::vector<point_type> res; - oln_iter_type(image_type) it(input_); - - res.reserve(input_.npoints()); - for_all(it) - res.push_back(it); - return res; - } - - void - mark_set_impl(const point_type &x) - { - if (parent_.size() == parent_.capacity()) - { - capacity = parent_.capacity() + capacity_chunk; - parent_.reserve(capacity); - comp_value_.reserve(capacity); - } - to_comp_[x] = ncomps_ + 1; - data_.push_back(A(input_, x, env_)); - parent_.push_back(ncomps_ + 1); - //comp_value_.push_back(input_[x]); - comp_value_.push_back(ncomps_ + 1); - } - - void - uni_impl(const point_type& n, const point_type& p) - { - comp_type r = find_root(to_comp_[n]); - precondition(to_comp_[n] <= ncomps_); - precondition(to_comp_[p] <= (ncomps_ + 1)); - if (r != to_comp_[p]) - if (input_[n] == input_[p]) - { - if (to_comp_[p] == (ncomps_ + 1)) // first merge of p component - { - precondition(r < comp_value_.capacity()); - //comp_value_[r] = input_[p]; - // comp_value_[to_comp_[p]] = comp_value_[r]; - data_[r] += data_[to_comp_[p]]; - precondition(r <= ncomps_); - to_comp_[p] = r; - } - else - { - precondition(r < parent_.capacity()); - data_[parent_[to_comp_[p]]] += data_[parent_[r]]; - // comp_value_[parent_[to_comp_[p]]] = ntg::min(comp_value_[parent_[r]], - // comp_value_[parent_[to_comp_[p]]]); - parent_[r] = parent_[to_comp_[p]]; - - } - } - // precondition(comp_value_[parent_[r]] <= 255); - } - }; - - // traits specialization - template <typename T, typename DestType, typename A, typename Exact> - struct tarjan_traits<cc<T, DestType, A, Exact> > - { - typedef T input_type; - typedef typename mute<T, DestType>::ret output_type; - typedef A attr_type; - }; - - } // end of namespace tarjan } // end of namespace topo Index: olena/oln/topo/tarjan/tarjan.hh --- olena/oln/topo/tarjan/tarjan.hh Wed, 31 Mar 2004 19:11:41 +0200 palma_g (oln/m/47_tarjan.hh 1.1 644) +++ olena/oln/topo/tarjan/tarjan.hh Thu, 01 Apr 2004 13:49:48 +0200 palma_g (oln/m/47_tarjan.hh 1.1 644) @@ -1,12 +1,12 @@ -// Copyright (C) 2001, 2002, 2003, 2004 EPITA Research and Development Laboratory +// 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 +// 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. // @@ -45,6 +45,7 @@ namespace topo { /// \brief Implementation of tarjan set. namespace tarjan { + /// Forward declaration for tarjan traits. template <typename Exact> struct tarjan_traits; @@ -61,10 +62,10 @@ template <typename Exact> struct tarjan: public mlc_hierarchy::any<Exact> { - typedef oln_tarjan_input_type(Exact) input_type; - typedef oln_tarjan_output_type(Exact) image_out_type; - typedef oln_value_type(image_out_type) comp_type; - typedef oln_point_type(input_type) point_type; + typedef oln_tarjan_input_type(Exact) input_type; ///< Type of input image. + typedef oln_tarjan_output_type(Exact) image_out_type; ///< Type of output image. + typedef oln_value_type(image_out_type) comp_type; ///< Type of components. + typedef oln_point_type(input_type) point_type; ///< Point type of image to process. /*! ** \brief Run the algorithm. -- Giovanni Palma EPITA - promo 2005 - membre d'EpX - LRDE Mob. : +33 (0)6 60 97 31 74