URL: https://svn.lrde.epita.fr/svn/oln/trunk/milena ChangeLog: 2007-10-26 Matthieu Garrigues <garrigues@lrde.epita.fr> Improve fllt. Add more tests. * mln/set/is_subset_of.hh: New, Test if a point set is a subset of another. * mln/util/branch_iter.hh: Update * mln/util/tree.hh: (tree<T>::add_child(node<T>*)) New, (tree<T>::main_branch()) New. * sandbox/garrigues/fllt.hh: Improve fllt. * sandbox/garrigues/test_fllt.cc: Update * sandbox/garrigues/test_fllt2.cc, * sandbox/garrigues/test_fllt3.cc, * sandbox/garrigues/test_fllt4.cc, * sandbox/garrigues/test_fllt5.cc, * sandbox/garrigues/test_fllt_tiny.cc: New, differents cases of tests for fllt. --- mln/set/is_subset_of.hh | 75 +++++++++++++++++ mln/util/branch_iter.hh | 17 +++ mln/util/tree.hh | 22 ++++- sandbox/garrigues/fllt.hh | 156 ++++++++++++++++++++++++++++-------- sandbox/garrigues/test_fllt.cc | 44 +++++----- sandbox/garrigues/test_fllt2.cc | 40 +++++++++ sandbox/garrigues/test_fllt3.cc | 40 +++++++++ sandbox/garrigues/test_fllt4.cc | 40 +++++++++ sandbox/garrigues/test_fllt5.cc | 40 +++++++++ sandbox/garrigues/test_fllt_tiny.cc | 24 +++++ 10 files changed, 439 insertions(+), 59 deletions(-) Index: trunk/milena/mln/set/is_subset_of.hh =================================================================== --- trunk/milena/mln/set/is_subset_of.hh (revision 0) +++ trunk/milena/mln/set/is_subset_of.hh (revision 1399) @@ -0,0 +1,75 @@ +// Copyright (C) 2007 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, 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. + +#ifndef MLN_SET_IS_SUBSET_OF_HH +# define MLN_SET_IS_SUBSET_OF_HH + +# include <mln/core/concept/point_set.hh> + +namespace mln +{ + + namespace set + { + /*! \brief Test if a point set is a subset of another point set. + * + * \relates mln::Point_Set + */ + template <typename Pl, typename Pr> + bool + is_subset_of(const Point_Set<Pl>& lhs, const Point_Set<Pr>& rhs); + +# ifndef MLN_INCLUDE_ONL + + template <typename Pl, typename Pr> + bool + is_subset_of(const Point_Set<Pl>& lhs_, const Point_Set<Pr>& rhs_) + { + Pl lhs = exact(lhs_); + Pr rhs = exact(rhs_); + + if (lhs.npoints() > rhs.npoints()) + return false; + + mln_piter(Pl) p(lhs); + for_all(p) + { + if (!rhs.has(p)) + return false; + } + return true; + } + + +# endif // ! MLN_INCLUDE_ONLY + + } // end of namespace mln::set + +} // end of namespace mln + + +#endif // ! MLN_SET_SUBSET_HH Index: trunk/milena/mln/util/tree.hh =================================================================== --- trunk/milena/mln/util/tree.hh (revision 1398) +++ trunk/milena/mln/util/tree.hh (revision 1399) @@ -71,10 +71,14 @@ children_t& children(); /// Access to the parent node. + node<T>* parent(); //node<T>*& parent(); - const node<T>* parent() const; + /// \{ Add a child to the node node<T>* add_child(T elt); + node<T>* add_child(node<T>* node); + /// \} + void set_parent(node<T>* parent); void print_rec(int n) const; void print() const; @@ -147,7 +151,7 @@ branch<T> tree<T>::main_branch() { - return branch<T>(*this, root()); + return branch<T>(*this, *root()); } template <typename T> @@ -222,6 +226,16 @@ return s; } + + template <typename T> + node<T>* + node<T>::add_child(node<T>* node) + { + node->parent_ = this; + this->children().push_back(node); + return node; + } + template <typename T> void node<T>::set_parent(node<T>* parent) @@ -232,8 +246,8 @@ } template <typename T> - const node<T>* - node<T>::parent() const + node<T>* + node<T>::parent() { return parent_; } Index: trunk/milena/mln/util/branch_iter.hh =================================================================== --- trunk/milena/mln/util/branch_iter.hh (revision 1398) +++ trunk/milena/mln/util/branch_iter.hh (revision 1399) @@ -50,6 +50,7 @@ /// Convertion to node. operator util::node<T>&() const; + util::node<T>& operator *(); /// Test the iterator validity. bool is_valid() const; @@ -94,6 +95,14 @@ } template <typename T> + util::node<T>& + branch_iter<T>::operator*() + { + mln_assertion(n_); + return *n_; + } + + template <typename T> bool branch_iter<T>::is_valid() const { @@ -131,7 +140,6 @@ if (s_.top().first == s_.top().second) //if (*(s_.top().first) == 0) { - mln_assertion(n_); s_.pop(); next(); return; @@ -141,6 +149,13 @@ n_ = *(s_.top().first); s_.top().first++; + if (!n_) + { + std::cout << "browsing warning : nul pointer" << std::endl; + next(); + return; + } + mln_assertion(n_); if (n_->children().size() > 0) s_.push(iter_pair(n_->children().begin(), Index: trunk/milena/sandbox/garrigues/fllt.hh =================================================================== --- trunk/milena/sandbox/garrigues/fllt.hh (revision 1398) +++ trunk/milena/sandbox/garrigues/fllt.hh (revision 1399) @@ -61,8 +61,10 @@ # include <mln/set/uni.hh> # include <mln/set/diff.hh> # include <mln/set/inter.hh> +# include <mln/set/is_subset_of.hh> # include <mln/util/tree.hh> +# include <mln/util/branch_iter.hh> # include <mln/labeling/regional_minima.hh> # include <mln/labeling/regional_maxima.hh> @@ -84,15 +86,18 @@ { template <typename P, typename V> - struct fllt_node + struct fllt_node_elt { V value; set_p<P> points; set_p<P> holes; }; - # define fllt_tree(P, V) util::tree< fllt_node<P, V> > - # define fllt_node(P, V) util::node< fllt_node<P, V> > + # define fllt_tree(P, V) util::tree< fllt_node_elt<P, V> > + # define fllt_node(P, V) util::node< fllt_node_elt<P, V> > + # define fllt_branch(P, V) util::branch< fllt_node_elt<P, V> > + # define fllt_branch_iter(P, V) util::branch_iter< fllt_node_elt<P, V> > + // # define fllt_node(P, V) typename fllt_tree(P, V)::node_t @@ -254,7 +259,7 @@ regions(p) = current_region; else { - if (regions(p)->get_parent() == 0) + if (regions(p)->parent() == 0) regions(p)->set_parent(current_region); } } @@ -356,8 +361,9 @@ template <typename V, typename F> - fllt_tree(point2d, V)* - compute_level_set(const image2d<V>& ima) + fllt_tree(point2d, V)& + compute_level_set(const image2d<V>& ima, + image2d< fllt_node(point2d, V)* >& regions) { typedef point2d P; typedef image2d<V> I; @@ -369,6 +375,9 @@ mln::pw::cst_<int> > > I_IF; + // Check + mln_assertion(ima.domain() == regions.domain()); + // Declarations. set_p<P> R, N, A; V g, gn; @@ -381,7 +390,6 @@ // debug::println_with_border(u); image2d<bool> tagged(ima.domain()); fllt_node(P, V)* current_region; - image2d<fllt_node(P, V)*> regions(ima.domain()); // INIT R.clear(); @@ -471,7 +479,7 @@ // debug::println(regions); //debug::println(ima | regions(make:defined reference to `mln::fllt::lower<mln::value::int_u<8u> >::inc':point2d(-4,-1))->elt().points); - return (&tree); + return (tree); } // end of compute_level_set @@ -530,16 +538,71 @@ static const neighb2d& reg_nbh() { return c8(); } }; + template <typename P, typename V> + void + move_shape(fllt_node(P, V)& node, + fllt_node(P, V)& hole, + fllt_tree(P, V)& tree, + const image2d<fllt_node(P, V)*>& other_reg) + { + fill_a_shape(hole, tree, other_reg); + node.elt().points = set::uni(hole.elt().points, node.elt().points); + node.add_child(&hole); + } -// template <> -// void find_shape_of_holes(fllt_node(P, V)* lower, -// fllt_node(P, V)* upper) -// { -// } + template <typename P, typename V> + fllt_node(P, V)* + find_the_hole(fllt_node(P, V)& node, + const P p, + const image2d<fllt_node(P, V)*>& other_reg) + { + fllt_node(P, V)* s = other_reg(p); + + mln_assertion(s); + while (s->parent() && (s->parent()->elt().value < node.elt().value)) + { + mln_assertion(s); + s = s->parent(); + mln_assertion(s); + } + return s; + } + + template <typename P, typename V> + void + fill_a_shape(fllt_node(P, V)& node, + fllt_tree(P, V)& tree, + const image2d<fllt_node(P, V)*>& other_reg) + { + mln_piter(set_p<P>) p(node.elt().holes); + for_all(p) + { + bool h = true; + fllt_node(P, V)* hole = find_the_hole(node, point2d(p), other_reg); + typename fllt_node(P, V)::children_t::iterator it; + for (it = node.children().begin(); + it != node.children().end(); + it++) + { + if (set::is_subset_of(hole->elt().points, + (*it)->elt().points)) + { + h = false; + break; + } + } + if (h) + move_shape(node, *hole, tree, other_reg); + + } + } template <typename P, typename V> - void merge_trees(fllt_node(P, V)* lower, - fllt_node(P, V)* upper) + void + merge_trees(fllt_tree(P, V)& lower, + fllt_tree(P, V)& upper, + const image2d<fllt_node(P, V)*>& low_reg, + const image2d<fllt_node(P, V)*>& upp_reg) { // In order to merge the trees, we only have to find for each shape S @@ -548,35 +611,64 @@ // put the shape of the hole H (and all its descendants) as child of // the shape . - fllt_node(P, V)* it = lower; - - if (lower->elt().holes.size() > 0) - { - - } - // FIXME : add an method to tree to get the childen. - // FIXME : add an iterator to browse a tree. - - mln_piter(set_p<P>) p(lower->child_); + fllt_branch_iter(P, V) p(lower.main_branch()); for_all(p) { - merge_trees(lower, upper); + fllt_node(P, V)& n(p); + fill_a_shape(n, lower, upp_reg); } +// fllt_branch_iter(P, V) q(upper.main_branch()); +// for_all(q) +// { +// fllt_node(P, V)& n(p); +// fill_a_shape(n, upper, low_reg); +// } } template <typename V> // Fixme : return type - void fllt(const image2d<V>& ima) + void + fllt(const image2d<V>& ima) { typedef point2d P; - fllt_tree(P, V)* upper_tree; - fllt_tree(P, V)* lower_tree; + fllt_tree(P, V) upper_tree; + fllt_tree(P, V) lower_tree; + image2d<fllt_node(P, V)*> low_reg(ima.domain()); + image2d<fllt_node(P, V)*> upp_reg(ima.domain()); + + lower_tree = compute_level_set<V, lower<V> >(ima, low_reg); + upper_tree = compute_level_set<V, upper<V> >(ima, upp_reg); - lower_tree = compute_level_set<V, lower<V> >(ima); - upper_tree = compute_level_set<V, upper<V> >(ima); + merge_trees(lower_tree, upper_tree, low_reg, upp_reg); - //merge_trees(lower_tree, upper_tree); + + + image2d<value::int_u8> output (ima.domain ()); + util::tree_to_image (lower_tree, output); + + if (output != ima) + { + std::cerr << "BUG!!!" << std::endl; + abort(); + } + + io::pgm::save(output, "out_final.pgm"); + std::cout << "out_final.pgm generate" + << std::endl; + + + fllt_branch_iter(P, V) p(lower_tree.main_branch()); + for_all(p) + { + std::cout << "region mere : " << (*p).parent() << std::endl; + std::cout << " ^" << std::endl; + std::cout << " |" << std::endl; + std::cout << "region : " << &*p << std::endl; + + debug::println(ima | (*p).elt().points); + std::cout << std::endl; + } } } // end of namespace mln::fllt Index: trunk/milena/sandbox/garrigues/test_fllt.cc =================================================================== --- trunk/milena/sandbox/garrigues/test_fllt.cc (revision 1398) +++ trunk/milena/sandbox/garrigues/test_fllt.cc (revision 1399) @@ -15,26 +15,26 @@ using namespace mln; -// int ws[81] = {3,2,3,3,5,5,5,5,5, -// 2,1,3,4,4,4,4,5,5, -// 2,3,4,2,3,3,2,4,4, -// 1,4,2,1,1,2,1,2,2, -// 1,2,4,2,1,2,1,1,1, -// 1,3,3,3,4,3,2,5,1, -// 1,3,4,3,4,3,2,5,1, -// 1,3,3,3,4,3,2,5,1, -// 1,3,3,4,2,3,2,1,1}; - -// w_window2d_int w_win = make::w_window2d(ws); -// image2d<int> ima = convert::to_image(w_win); -//fllt::fllt(ima); - - - image2d<value::int_u8> ima = io::pgm::load("../../img/tiny.pgm"); - - image2d<int> ima_int(ima.domain()); - -level::fill(ima_int, ima); - debug::println(ima); - fllt::fllt(ima_int); + int ws[81] = {3,2,3,3,5,5,5,5,5, + 2,1,3,4,4,4,4,5,5, + 2,3,4,2,3,3,2,4,4, + 1,4,2,1,1,2,1,2,2, + 1,2,4,2,1,2,1,1,1, + 1,3,3,3,4,3,2,5,1, + 1,3,4,3,4,3,2,5,1, + 1,3,3,3,4,3,2,5,1, + 1,3,3,4,2,3,2,1,1}; + + w_window2d_int w_win = make::w_window2d(ws); + image2d<int> ima = convert::to_image(w_win); +fllt::fllt(ima); + + +// image2d<value::int_u8> ima = io::pgm::load("../../img/tiny.pgm"); + +// image2d<int> ima_int(ima.domain()); + +// level::fill(ima_int, ima); +// debug::println(ima); +// fllt::fllt(ima_int); } Index: trunk/milena/sandbox/garrigues/test_fllt2.cc =================================================================== --- trunk/milena/sandbox/garrigues/test_fllt2.cc (revision 0) +++ trunk/milena/sandbox/garrigues/test_fllt2.cc (revision 1399) @@ -0,0 +1,40 @@ +# include "fllt.hh" +# include <mln/core/image2d.hh> +# include <mln/core/clone.hh> +# include <mln/value/int_u8.hh> +# include <mln/debug/println.hh> +# include <mln/convert/to_w_window.hh> +# include <mln/core/w_window2d_int.hh> +# include <mln/convert/to_image.hh> +# include <mln/level/fill.hh> +# include <mln/io/pgm/load.hh> +# include <mln/io/pbm/load.hh> + +int main() +{ + + using namespace mln; + + int ws[81] = {5,5,5,5,5,5,5,5,5, + 5,5,5,5,5,5,5,5,5, + 5,5,5,5,5,5,8,8,5, + 5,5,1,1,1,5,8,8,5, + 5,5,1,1,1,5,8,8,5, + 5,5,1,1,1,5,8,8,5, + 5,5,5,5,5,5,8,8,5, + 5,5,5,5,5,5,5,5,5, + 5,5,5,5,5,5,5,5,5}; + + w_window2d_int w_win = make::w_window2d(ws); + image2d<int> ima = convert::to_image(w_win); +fllt::fllt(ima); + + +// image2d<value::int_u8> ima = io::pgm::load("../../img/tiny.pgm"); + +// image2d<int> ima_int(ima.domain()); + +// level::fill(ima_int, ima); +// debug::println(ima); +// fllt::fllt(ima_int); +} Index: trunk/milena/sandbox/garrigues/test_fllt3.cc =================================================================== --- trunk/milena/sandbox/garrigues/test_fllt3.cc (revision 0) +++ trunk/milena/sandbox/garrigues/test_fllt3.cc (revision 1399) @@ -0,0 +1,40 @@ +# include "fllt.hh" +# include <mln/core/image2d.hh> +# include <mln/core/clone.hh> +# include <mln/value/int_u8.hh> +# include <mln/debug/println.hh> +# include <mln/convert/to_w_window.hh> +# include <mln/core/w_window2d_int.hh> +# include <mln/convert/to_image.hh> +# include <mln/level/fill.hh> +# include <mln/io/pgm/load.hh> +# include <mln/io/pbm/load.hh> + +int main() +{ + + using namespace mln; + + int ws[81] = {2,2,2,2,2,2,2,2,2, + 2,2,2,2,2,2,2,2,2, + 2,1,1,1,1,1,1,1,2, + 2,1,2,2,1,0,0,1,2, + 2,1,2,2,1,0,0,1,2, + 2,1,2,2,1,0,0,1,2, + 2,1,1,1,1,1,1,1,2, + 2,1,1,1,1,1,1,1,2, + 2,2,2,2,2,2,2,2,2}; + + w_window2d_int w_win = make::w_window2d(ws); + image2d<int> ima = convert::to_image(w_win); +fllt::fllt(ima); + + +// image2d<value::int_u8> ima = io::pgm::load("../../img/tiny.pgm"); + +// image2d<int> ima_int(ima.domain()); + +// level::fill(ima_int, ima); +// debug::println(ima); +// fllt::fllt(ima_int); +} Index: trunk/milena/sandbox/garrigues/test_fllt_tiny.cc =================================================================== --- trunk/milena/sandbox/garrigues/test_fllt_tiny.cc (revision 0) +++ trunk/milena/sandbox/garrigues/test_fllt_tiny.cc (revision 1399) @@ -0,0 +1,24 @@ +# include "fllt.hh" +# include <mln/core/image2d.hh> +# include <mln/core/clone.hh> +# include <mln/value/int_u8.hh> +# include <mln/debug/println.hh> +# include <mln/convert/to_w_window.hh> +# include <mln/core/w_window2d_int.hh> +# include <mln/convert/to_image.hh> +# include <mln/level/fill.hh> +# include <mln/io/pgm/load.hh> +# include <mln/io/pbm/load.hh> + +int main() +{ + + using namespace mln; + + image2d<value::int_u8> ima = io::pgm::load("../../img/tiny.pgm"); + + image2d<int> ima_int(ima.domain()); + + level::fill(ima_int, ima); + fllt::fllt(ima_int); +} Index: trunk/milena/sandbox/garrigues/test_fllt4.cc =================================================================== --- trunk/milena/sandbox/garrigues/test_fllt4.cc (revision 0) +++ trunk/milena/sandbox/garrigues/test_fllt4.cc (revision 1399) @@ -0,0 +1,40 @@ +# include "fllt.hh" +# include <mln/core/image2d.hh> +# include <mln/core/clone.hh> +# include <mln/value/int_u8.hh> +# include <mln/debug/println.hh> +# include <mln/convert/to_w_window.hh> +# include <mln/core/w_window2d_int.hh> +# include <mln/convert/to_image.hh> +# include <mln/level/fill.hh> +# include <mln/io/pgm/load.hh> +# include <mln/io/pbm/load.hh> + +int main() +{ + + using namespace mln; + + int ws[81] = {5,5,5,5,5,1,1,1,1, + 5,5,5,5,5,1,1,1,1, + 5,5,5,5,5,1,1,1,1, + 5,5,5,5,5,1,1,1,1, + 5,5,5,5,5,1,1,1,1, + 5,5,5,5,5,1,1,1,1, + 5,5,5,5,5,1,1,1,1, + 5,5,5,5,5,1,1,1,1, + 5,5,5,5,5,1,1,1,1}; + + w_window2d_int w_win = make::w_window2d(ws); + image2d<int> ima = convert::to_image(w_win); +fllt::fllt(ima); + + +// image2d<value::int_u8> ima = io::pgm::load("../../img/tiny.pgm"); + +// image2d<int> ima_int(ima.domain()); + +// level::fill(ima_int, ima); +// debug::println(ima); +// fllt::fllt(ima_int); +} Index: trunk/milena/sandbox/garrigues/test_fllt5.cc =================================================================== --- trunk/milena/sandbox/garrigues/test_fllt5.cc (revision 0) +++ trunk/milena/sandbox/garrigues/test_fllt5.cc (revision 1399) @@ -0,0 +1,40 @@ +# include "fllt.hh" +# include <mln/core/image2d.hh> +# include <mln/core/clone.hh> +# include <mln/value/int_u8.hh> +# include <mln/debug/println.hh> +# include <mln/convert/to_w_window.hh> +# include <mln/core/w_window2d_int.hh> +# include <mln/convert/to_image.hh> +# include <mln/level/fill.hh> +# include <mln/io/pgm/load.hh> +# include <mln/io/pbm/load.hh> + +int main() +{ + + using namespace mln; + + int ws[81] = {5,5,5,2,2,2,1,1,1, + 5,5,5,2,2,2,1,1,1, + 5,5,5,2,2,2,1,1,1, + 5,5,5,2,2,2,1,1,1, + 5,5,5,2,2,2,1,1,1, + 5,5,5,2,2,2,1,1,1, + 5,5,5,2,2,2,1,1,1, + 5,5,5,2,2,2,1,1,1, + 5,5,5,2,2,2,1,1,1}; + + w_window2d_int w_win = make::w_window2d(ws); + image2d<int> ima = convert::to_image(w_win); +fllt::fllt(ima); + + +// image2d<value::int_u8> ima = io::pgm::load("../../img/tiny.pgm"); + +// image2d<int> ima_int(ima.domain()); + +// level::fill(ima_int, ima); +// debug::println(ima); +// fllt::fllt(ima_int); +}