Index: ChangeLog from Simon Odou <simon@lrde.epita.fr> * oln/morpho/cc_tarjan.hh: New. Add the connected component labelling algorithm using the Tarjan Union-Find. cc_tarjan.hh | 234 +++++++++++++++++++++++++++++++++++++++++++++++++++++++++++ 1 files changed, 234 insertions(+) Index: oln/morpho/cc_tarjan.hh --- oln/morpho/cc_tarjan.hh (revision 0) +++ oln/morpho/cc_tarjan.hh (revision 0) @@ -0,0 +1,234 @@ +// Copyright (C) 2005 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_CC_TARJAN_HH +# define OLENA_CC_TARJAN_HH + +# include <vector> + +# include <oln/basics2d.hh> +# include <oln/core/abstract/image_operator.hh> +# include <oln/level/fill.hh> + +// +// Based on "Ruminations on Tarjan's Union-Find algorithm and connected +// operators" of Thierry Geraud. +// + + +namespace oln { + + // fwd decl + namespace morpho { + template <typename T, typename I, typename E> struct cc_tarjan_ret; + } + + // FIXME: this macro is waiting for the mute. + // (we may use a property to do it) + #define tmp_mute(I, T) image2d< T > + + // category + template <typename T, typename I, typename E> + struct set_category< morpho::cc_tarjan_ret<T,I,E> > + { typedef category::image ret; }; + + // super_type + template <typename T, typename I, typename E> + struct set_super_type< morpho::cc_tarjan_ret<T,I,E> > + { + typedef abstract::image_unary_operator + <tmp_mute(I, T), I, morpho::cc_tarjan_ret<T, I, E> > + ret; + }; + + + namespace morpho { + + template <typename T, typename I, typename E> + struct cc_tarjan_ret + : public abstract::image_unary_operator + <tmp_mute(I, T), I, cc_tarjan_ret<T, I, E> > + { + typedef abstract::image_unary_operator + <tmp_mute(I, T), I, cc_tarjan_ret<T, I, E> > + super_type; + typedef typename super_type::output_type output_type; + + const E ng; + + cc_tarjan_ret(const abstract::image<I>& input, + const abstract::neighborhood<E>& ng) : + super_type(input), + ng(ng.exact()) + { + } + + }; + + + namespace impl { + + + namespace misc { + + // FIXME: This code should be generalized. + // While iterating on image and then on a neighborhood, here we do + // not want to see the neighborhood points ever seen. + std::vector<dpoint2d> get_superior(const neighborhood2d& n) + { + std::vector<dpoint2d> output; + for (unsigned i = 0; i < n.card(); ++i) + { + dpoint2d dp = n.dp(i); + if (dp.row() < 0 || (dp.row() == 0 && dp.col() < 0)) + output.push_back(dp); + } + return output; + } + + std::vector<dpoint2d> get_inferior(const neighborhood2d& n) + { + std::vector<dpoint2d> output; + for (unsigned i = 0; i < n.card(); ++i) + { + dpoint2d dp = n.dp(i); + if (dp.row() > 0 || (dp.row() == 0 && dp.col() > 0)) + output.push_back(dp); + } + return output; + } + + } // end of misc namespace + + + template <typename T, typename I, typename N> + struct generic_cc_tarjan : public cc_tarjan_ret<T, I, N> + { + typedef cc_tarjan_ret<T, I, N> super_type; + typedef typename super_type::output_type output_type; + + tmp_mute(I, oln_type_of(I, point)) parent; + T ncomps; + + generic_cc_tarjan(const abstract::image<I>& input, + const abstract::neighborhood<N>& ng) : + super_type(input, ng), + parent(input.size()) + { + } + + void impl_run() + { + mlc::is_true<mlc::type::eq<oln_type_of(I, size), + oln_type_of(N, size)>::ret>::ensure(); + + output_type tmp(this->input.size()); // FIXME: trick + this->output = tmp; + + first_pass(); + second_pass(); + } + + void first_pass() + { + std::vector<dpoint2d> neighb = misc::get_inferior(this->ng); + oln_type_of(I, bkd_piter) p(this->input.size()); + for_all(p) + if (this->input[p]) + { + make_set(p); + for (unsigned v = 0; v < neighb.size(); ++v) + { + oln_type_of(I, point) n = oln_type_of(I, point)(p) + neighb[v]; + if (this->input[n]) + do_union(n, p); + } + } + } + + void second_pass() + { + oln_type_of(I, fwd_piter) p(this->input.size()); + level::fill(output, 0); + ncomps = 0; + for_all(p) + if (this->input[p]) + { + oln_type_of(I, point) q = parent[p]; + // FIXME: test if ncomps > T::max() + output[p] = (q == p ? ++ncomps : output[q]); + } + } + + void make_set(const oln_type_of(I, point)& x) + { + parent[x] = x; + } + + oln_type_of(I, point) find_root(const oln_type_of(I, point)& x) + { + if (parent[x] != x) + { + parent[x] = find_root(parent[x]); + return parent[x]; + } + return x; + } + + void do_union(const oln_type_of(I, point)& n, + const oln_type_of(I, point)& p) + { + oln_type_of(I, point) r = find_root(n); + if (r != p) + parent[r] = p; + } + + + }; + + } // end of namespace oln::morpho::impl + + + /// Connected component labelling via Tarjan Union-Find generic routine. + + // T is the component label type (usually unsigned). + template<typename T, typename I, typename N> + cc_tarjan_ret<T, I, N> cc_tarjan(const abstract::image<I>& input, + const abstract::neighborhood<N>& ng) + { + impl::generic_cc_tarjan<T, I, N> tmp(input, ng); + tmp.run(); + return tmp; + } + + + } // end of namespace oln::morpho + +} // end of namespace oln + + +#endif // ! OLENA_CC_TARJAN_HH