Index: ChangeLog from Nicolas Widynski &lt;nicolas.widynski(a)lrde.epita.fr&gt; * olena/oln/morpho/tree.hh: tree (canva). * olena/oln/morpho/maxtree.hh: creation of maxtree. * olena/oln/morpho/clean_astro_images.hh: maxtree utilisation's sample. clean_astro_images.hh | 268 ++++++++++++++++++++++++++++++++++++++++++ maxtree.hh | 315 ++++++++++++++++++++++++++++++++++++++++++++++++++ tree.hh | 196 +++++++++++++++++++++++++++++++ 3 files changed, 779 insertions(+) Index: olena/oln/morpho/tree.hh --- olena/oln/morpho/tree.hh (revision 0) +++ olena/oln/morpho/tree.hh (revision 0) @@ -0,0 +1,196 @@ +// Copyright (C) 2001-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_MORPHO_CANVAS_TREE_HH +# define OLENA_MORPHO_CANVAS_TREE_HH + +# include <mlc/any.hh> + +# include <oln/core/box.hh> +# include <oln/utils/record.hh> +# include <oln/core/abstract/image_entry.hh> +# include <oln/core/ch_value_type.hh> +# include <oln/level/fill.hh> +# include <oln/basics.hh> + +# include <vector> + +// just for test +#include <ntg/real/int_u.hh> + +namespace oln { + + namespace morpho { + + namespace canvas { + + + template <typename I, typename E> + struct tree : public mlc::any<E> + { + typedef oln_type_of(I, point) point_type; + + // Attribute. + box<const I> input; + oln_type_of(I, concrete) output; + std::vector<std::vector<point_type> > S; + point_type root_point; + + void run_compute_tree() + { + first_pass(); + compute_tree(); + } + + void run_compute_output() + { + init_traitement(); + traitement(); + } + + // Concrete method. + void first_pass() + { + oln_type_of(I, niter) n(input); + + // init + compute_S(); + set_is_processed_to_false(); + set_default_output(); + + typename std::vector<std::vector<point_type> >::reverse_iterator i; + typename std::vector<point_type>::const_iterator j; + for (i = S.rbegin(); i != S.rend(); i++) + { + for (j = i->begin(); j != i->end(); j++) + { + make_set(*j); + for_all_n_of_p (n, *j) + if (input.hold(n) and is_processed(n)) + do_union(n, *j); + set_is_processed(*j); + } + } + root_point = *j; + } + + void do_union(const point_type& n, const point_type& p) + { + point_type r = find_root(n); + if (r != p) + set_father(r, p); + } + + // Abstract methods. + // --------------------------- + + // init + + void init_traitement() + { + this->exact().impl_init_traitement(); + } + + void compute_S() + { + this->exact().impl_compute_S(); + } + void set_default_output() + { + this->exact().impl_set_default_output(); + } + + // about is_processed + void set_is_processed_to_false() + { + this->exact().impl_set_is_processed_to_false(); + } + void set_is_processed(const point_type& p) + { + this->exact().impl_set_is_processed(p); + } + bool is_processed(const point_type& n) const + { + return this->exact().impl_is_processed(n); + } + + const point_type get_father(const point_type& p) const + { + return this->exact().impl_get_father(p); + } + + // core + + void compute_tree() + { + this->exact().impl_compute_tree(); + } + + void traitement() + { + this->exact().impl_traitement(); + } + + void make_set(const point_type& p) + { + this->exact().impl_make_set(p); + } + point_type find_root(const point_type& x) + { + return this->exact().impl_find_root(x); + } + void set_father(const point_type& r, const point_type& p) + { + this->exact().impl_set_father(r, p); + } + + protected: + + // Ctor. + tree(const abstract::image_with_nbh<I>& input) : + input(input), + S() + { + } + + // Check for impls.. + ~tree() + { + // FIXME... mlc_check_method_impl(E, void, init, , ); + } + + }; + + + } // end of namespace oln::morpho::canvas + + } // end of namespace oln::morpho + +} // end of namespace oln + + +#endif // ! OLENA_MORPHO_CANVAS_TREE_HH Index: olena/oln/morpho/maxtree.hh --- olena/oln/morpho/maxtree.hh (revision 0) +++ olena/oln/morpho/maxtree.hh (revision 0) @@ -0,0 +1,315 @@ +// Copyright (C) 2001-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_MORPHO_MAX_TREE_HH +# define OLENA_MORPHO_MAX_TREE_HH + +# include <mlc/any.hh> + +# include <oln/core/box.hh> +# include <oln/utils/record.hh> +# include <oln/core/abstract/image_entry.hh> +# include <oln/core/ch_value_type.hh> +# include <oln/level/fill.hh> + +# include <oln/morpho/tree.hh> +# include <oln/basics.hh> + +# include <cassert> +# include <vector> +# include <functional> +# include <set> + +// just for test +#include <ntg/real/int_u.hh> + + +namespace oln { + + namespace morpho { + + namespace misc { + + struct pair_cmp + { + template<typename L, typename P> + bool operator()(const std::pair<L,P>& lhs, + const std::pair<L,P>& rhs) const + { + return lhs.first < rhs.first + or (lhs.first == rhs.first + and lhs.second.fwd_less(rhs.second)); + } + }; + + template<typename I, typename II, typename O, typename V> + void set_children(abstract::image_with_nbh<I>& marked, + const abstract::image_with_nbh<II>& children, + abstract::image_with_nbh<O>& out, + const oln_type_of(I, point)& p, + const V v) + { + typedef oln_type_of(I, point) point_type; + std::vector<point_type> f = children[p].value(); + typename std::vector<point_type>::const_iterator pt; + for (pt = f.begin(); pt != f.end(); pt++) + { + out[*pt] = v; + marked[*pt] = true; + set_children(marked, children, out, *pt, v); + } + } + + + template <class I> + std::vector<std::vector<oln_type_of(I, point)> > + sort(const abstract::image_with_nbh<I>& input) + { + typedef oln_type_of(I, point) point_type; + std::vector<std::vector<point_type> > S(256); + oln_type_of(I, fwd_piter) p(input.size()); + +#ifdef DEBUG + typedef std::pair<oln_type_of(I, value), point_type> pair_t; + std::set<pair_t,pair_cmp> sc; +#endif // ! DEBUG + + for_all_p (p) + { + S[input[p]].push_back(p); +#ifdef DEBUG + sc.insert(pair_t(input[p], p)); +#endif // ! DEBUG + } + +#ifdef DEBUG + { + unsigned l; + + typename std::set<pair_t,pair_cmp>::const_iterator i = sc.begin(); + typename std::vector<std::vector<point_type> >::const_iterator v; + + for (l = 0, v = S.begin(); + v != S.end(); v++, ++l) + { + for (typename std::vector<point_type>::const_iterator p = v->begin(); + p != v->end(); p++, ++i) + { + assert(input[*p] == l); + assert(i->first == l); + assert(i->second == *p); + } + } + } +#endif // ! DEBUG + + return S; + } + + } // end of oln::morpho::misc + + + template <typename I, typename E> + struct max_tree : public canvas::tree<I, E> + { + typedef canvas::tree<I, E> super_type; + typedef oln_type_of(I, point) point_type; + + // Attributes. + oln_ch_concrete_type(I, bool) is_proc; + oln_ch_concrete_type(I, bool) marked; + oln_ch_concrete_type(I, bool) is_deleted; + oln_ch_concrete_type(I, point_type) father; + oln_ch_concrete_type(I, std::vector<point_type>) children; + std::vector<std::vector<point_type> > v_root_point; + oln_type_of(I, concrete) new_value; + + void impl_compute_S() + { + this->S = misc::sort(this->input); + } + + bool condition_add_root_point(const point_type& f, const point_type& p) + { + if (this->input[f] == this->input[p]) + return false; + return true; + } + + void left_hand_walk(const point_type& p) + { + if (condition_add_root_point(p, father[p])) + v_root_point[this->input[p]].push_back(p); + + std::vector<point_type> f = children[p].value(); + typename std::vector<point_type>::const_iterator pt; + for (pt = f.begin(); pt != f.end(); pt++) + { + left_hand_walk(*pt); + } + } + + void impl_compute_tree() + { + v_root_point[this->input[this->root_point]].push_back(this->root_point); + left_hand_walk(this->root_point); + } + + void impl_set_default_output() + { + } + + void impl_set_is_processed_to_false() + { + oln_type_of(I, fwd_piter) p(is_proc.size()); + for_all_p (p) + is_proc[p] = false; + } + + void impl_set_is_processed(const point_type& p) + { + is_proc[p] = true; + } + + bool impl_is_processed(const point_type& n) const + { + return is_proc[n]; + } + + void init_aux_data(const point_type& p) + { + this->exact().impl_init_aux_data(p); + } + + const point_type impl_get_father(const point_type& p) const + { + return father[p].value(); + } + + void merge_aux_data(const point_type& r , const point_type& p) + { + children[p].call(&std::vector<point_type>::push_back, r); + this->exact().impl_merge_aux_data(r,p); + } + + void impl_make_set(const point_type& p) + { + father[p] = p; + init_aux_data(p); + } + + point_type impl_find_root(const point_type& x) + { + if (is_root(x)) + return x; + return find_root(father[x]); + } + + bool is_root(const point_type& x) const + { + return father[x] == x; + } + + void impl_set_father(const point_type& r, const point_type& p) + { + father[r] = p; + merge_aux_data(r,p); + } + + void eligible_component(const point_type& p) + { + this->exact().impl_eligible_component(p); + } + + void compute_image_is_deleted() + { + for (int i = 0; i <= 255 ;i++) + for (typename std::vector<point_type>::const_iterator p = v_root_point[i].begin(); + p != v_root_point[i].end(); p++) + eligible_component(*p); + } + + void impl_init_traitement() + { + level::fill(this->marked, false); + level::fill(this->is_deleted, false); + this->exact().impl_init_aux_traitement(); + } + + void impl_traitement() + { + compute_image_is_deleted(); + + oln_type_of(I, fwd_piter) p(this->input.size()); + for_all_p (p) + { + if (is_deleted[p]) + this->output[p] = this->new_value[p]; + else + this->output[p] = this->input[p]; + } + } + + protected: + + // Ctor. + max_tree(const abstract::image_with_nbh<I>& input) : + super_type(input) + { + oln_ch_concrete_type(I, bool) tmp1(input.size()); + is_proc = tmp1; + + oln_ch_concrete_type(I, point_type) tmp2(input.size()); + father = tmp2; + + oln_ch_concrete_type(I, std::vector<point_type>) tmp3(input.size()); + children = tmp3; + + oln_type_of(I, concrete) tmp4(input.size()); + this->output = tmp4; + + std::vector<std::vector<point_type> > tmp5(256); + v_root_point = tmp5; + + oln_ch_concrete_type(I, bool) tmp6(input.size()); + marked = tmp6; + + oln_ch_concrete_type(I, bool) tmp7(input.size()); + is_deleted = tmp7; + + oln_type_of(I, concrete) tmp8(input.size()); + new_value = tmp8; + } + + }; + + } // end of namespace oln::morpho + +} // end of namespace oln + + +#endif // ! OLENA_MORPHO_MAX_TREE_HH Index: olena/oln/morpho/clean_astro_images.hh --- olena/oln/morpho/clean_astro_images.hh (revision 0) +++ olena/oln/morpho/clean_astro_images.hh (revision 0) @@ -0,0 +1,268 @@ +// Copyright (C) 2001-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_MORPHO_CLEAN_ASTRO_IMAGES_HH +# define OLENA_MORPHO_CLEAN_ASTRO_IMAGES_HH + +# include <mlc/any.hh> + +# include <oln/core/box.hh> +# include <oln/utils/record.hh> +# include <oln/core/abstract/image_entry.hh> +# include <oln/core/ch_value_type.hh> +# include <oln/level/fill.hh> + +# include <oln/morpho/maxtree.hh> +# include <oln/basics.hh> + +# include <vector> + +// just for test +#include <ntg/real/int_u.hh> + + +namespace oln { + + namespace morpho { + + namespace misc { + + template<typename I> + bool have_the_center_point(const abstract::image_with_nbh<I>& children, + const oln_type_of(I, point)& p, + int row, + int col) + { + typedef oln_type_of(I, point) point_type; + if (((p.row() == (row / 2)) or (p.row() == (row - 1) / 2) or (p.row() == (row + 1) / 2)) + and ((p.col() == (col / 2)) or (p.col() == (col - 1) / 2) or (p.col() == (col + 1) / 2))) + return true; + std::vector<point_type> f = children[p].value(); + typename std::vector<point_type>::const_iterator pt; + for (pt = f.begin(); pt != f.end(); pt++) + { + return have_the_center_point(children, *pt, row, col); + } + return false; + } + + + template <typename I, typename II> + const oln_type_of(I, value) min_nbh(const abstract::image_with_nbh<I>& input, + const abstract::image_with_nbh<II>& children, + const oln_type_of(II, point)& p) + { + typedef oln_type_of(I, point) point_type; + std::vector<point_type> f = children[p].value(); + oln_type_of(I, niter) n(input.exact()); + oln_type_of(I, value) min; + typename std::vector<point_type>::const_iterator pt; + for (pt = f.begin(); pt != f.end(); pt++) + { + min = input[*pt].value(); + for_all_n_of_p (n, *pt) + { + min = ntg::min(min, input[n].value()); + } + + return ntg::min(min, min_nbh(input, children, *pt)); + } + return input[p]; + } + + template <typename I> + struct find_box + { + typedef oln_type_of(I, point) point_type; + + find_box(const point_type& p) { row_min_ = p.row(); row_max_ = p.row(); col_min_ = p.col(); col_max_ = p.col(); } + int row_min_, row_max_, col_min_, col_max_; + + + void box(const abstract::image_with_nbh<I>& children, + const oln_type_of(I, point)& p) + { + std::vector<point_type> f = children[p].value(); + typename std::vector<point_type>::const_iterator pt; + for (pt = f.begin(); pt != f.end(); pt++) + { + if (row_min_ > pt->row()) + row_min_ = pt->row(); + if (row_max_ < pt->row()) + row_max_ = pt->row(); + if (col_min_ > pt->col()) + col_min_ = pt->col(); + if (col_max_ < pt->col()) + col_max_ = pt->col(); + box(children, *pt); + } + } + }; + + + template <typename I> + bool is_a_circle(const abstract::image_with_nbh<I>& children, + const oln_type_of(I, point)& p, + float c_a) + { + find_box<I> fb(p); + fb.box(children,p); + int w = fb.col_max_ - fb.col_min_ + 1; + int h = fb.row_max_ - fb.row_min_ + 1; + float theoric_area = 3.14f * ((h + w) / 4.0) * ((h + w) / 4.0); + +#ifdef DEBUG + std::cout << "POINT : " << p << std::endl; + std::cout << "col_min : " << fb.col_min_ << std::endl; + std::cout << "col_max : " << fb.col_max_ << std::endl; + std::cout << "row_min : " << fb.row_min_ << std::endl; + std::cout << "row_max : " << fb.row_max_ << std::endl; + std::cout << "theoric area : " << theoric_area << std::endl; + std::cout << "computed area : " << c_a << std::endl; + std::cout << "t - sqrt(c) : " << theoric_area - sqrt(c_a) << std::endl; + std::cout << "t + sqrt(c) : " << theoric_area + sqrt(c_a) << std::endl; + std::cout << "w : " << w << std::endl << "h : " << h << std::endl; +#endif // ! DEBUG + if (((theoric_area - sqrt(c_a) < c_a) && + (theoric_area + sqrt(c_a) > c_a)) && + (c_a > (0.9 * 0.75 * w * h)) && + (c_a < (1.1 * 0.75 * w * h))) + return true; + return false; + } + + } // end of oln::morpho::misc + + + template <typename I> + struct clean_astro : public max_tree<I, clean_astro<I> > + { + typedef max_tree<I, clean_astro<I> > super_type; + typedef oln_type_of(I, point) point_type; + + // Attributes. + oln_ch_concrete_type(I, unsigned) area; + oln_type_of(I, value) level_; + unsigned area_; + + + // specific methods + + void set_area(unsigned nb) + { + area_ = nb; + } + + void set_level(unsigned nb) + { + level_ = nb; + } + + void remove_star(const point_type& p) + { + this->is_deleted[p] = true; + misc::set_children(this->marked, this->children, this->is_deleted, p, true); + this->new_value[p] = this->input[this->father[p]].value(); + misc::set_children(this->marked, + this->children, this->new_value, p, this->input[this->father[p]].value()); + } + + void remove_little_surface(const point_type& p) + { + this->is_deleted[p] = true; + misc::set_children(this->marked, this->children, this->is_deleted, p, true); + this->new_value[p] = this->input[this->father[p]].value(); + misc::set_children(this->marked, + this->children, this->new_value, p, this->input[this->father[p]].value()); + } + + bool is_a_star(const point_type& p) + { + if (not (this->marked[p])) + { + if (this->area[p] >= area_) + if (not (misc::have_the_center_point(this->children, p, this->input.size().nrows(), + this->input.size().ncols()))) + if (misc::is_a_circle(this->children, p, this->area[p])) + return true; + } + return false; + } + + bool is_a_little_surface(const point_type& p) + { + if (this->area[p] <= 20 && this->input[p] < 150) + return true; + return false; + } + + // fill the holes + + void impl_init_aux_data(const point_type& p) + { + this->area[p] = 1; + } + + void impl_merge_aux_data(const point_type& r , const point_type& p) + { + this->area[p] = this->area[r].value() + this->area[p].value(); + } + + void impl_eligible_component(const point_type& p) + { + if (this->input[p].value() > this->level_) + { + // if (is_a_little_surface(p)) + // remove_little_surface(p); + if (is_a_star(p)) + remove_star(p); + } + } + + void impl_init_aux_traitement() + { + } + + // Ctor. + clean_astro(const abstract::image_with_nbh<I>& input) : + super_type(input) + { + oln_ch_concrete_type(I, unsigned) tmp(input.size()); + this->area = tmp; + + this->area_ = 0; + this->level_ = 0; + } + + }; + + } // end of namespace oln::morpho + +} // end of namespace oln + + +#endif // ! OLENA_MORPHO_CLEAN_ASTRO_IMAGES_HH