[Olena-patches] milena r1386: Update fllt and fix tree

URL: https://svn.lrde.epita.fr/svn/oln/trunk/milena ChangeLog: 2007-10-24 Guillaume Duhamel &lt;guillaume.duhamel(a)lrde.epita.fr&gt; Update fllt and fix tree. Fix mln::util::tree. * mln/util/tree.hh, * mln/util/tree_to_image.hh, * tests/tree.cc, * tests/tree_to_image.cc: Update. Update fllt. * sandbox/garrigues/fllt.hh, * sandbox/garrigues/test_fllt.cc: Update. Update. * mln/display/save.hh: Update. --- mln/display/save.hh | 30 +++++++ mln/util/tree.hh | 101 ++++++++++++++++++----- mln/util/tree_to_image.hh | 29 ++++-- sandbox/garrigues/fllt.hh | 173 ++++++++++++++++++++++++----------------- sandbox/garrigues/test_fllt.cc | 38 +++++---- tests/tree.cc | 28 ++++-- tests/tree_to_image.cc | 31 ++++--- 7 files changed, 290 insertions(+), 140 deletions(-) Index: trunk/milena/tests/tree.cc =================================================================== --- trunk/milena/tests/tree.cc (revision 1385) +++ trunk/milena/tests/tree.cc (revision 1386) @@ -44,16 +44,22 @@ unsigned elt3 = 3; unsigned elt4 = 4; unsigned elt5 = 5; + unsigned elt6= 42; - util::tree<unsigned> tree(elt1); - tree.add_child(elt2); - tree.add_child(elt3); - util::tree<unsigned>* tree2 = tree.search(elt2); - mln_assertion(tree2); - tree2->add_child(elt4); - tree2->add_child(elt5); - util::tree<unsigned>* tree3 = tree.search(elt4); - mln_assertion(tree3); - tree3 = tree2->search(elt1); - mln_assertion(!tree3); + util::node<unsigned> node(elt1); + node.add_child(elt2); + node.add_child(elt3); + util::node<unsigned>* node2 = node.search(elt2); + mln_assertion(node2); + node2->add_child(elt4); + node2->add_child(elt5); + util::node<unsigned>* node3 = node.search(elt4); + mln_assertion(node3); + node3 = node2->search(elt1); + mln_assertion(!node3); + util::tree<unsigned>* tre = new util::tree<unsigned>(&node); + mln_assertion(tre); + tre->add_tree_up(elt6); + util::tree<unsigned>* trees = tre->tree_get(elt5); + mln_assertion(trees); } Index: trunk/milena/tests/tree_to_image.cc =================================================================== --- trunk/milena/tests/tree_to_image.cc (revision 1385) +++ trunk/milena/tests/tree_to_image.cc (revision 1386) @@ -57,6 +57,7 @@ I s4; I s5; I s6; + I s7; for (int i = 0; i < 100; ++i) for (int j = 0; j < 100; ++j) @@ -82,17 +83,25 @@ for (int j = 50; j < 60; ++j) s6.insert(point2d(i, j)); - util::tree<I> tree(s1); - tree.add_child(s2); - tree.add_child(s3); - - util::tree<I>* tree2 = tree.search(s2); - mln_assertion(tree2); - tree2->add_child(s4); - tree2->add_child(s5); - util::tree<I>* tree3 = tree.search(s4); - mln_assertion(tree3); - tree3->add_child(s6); + for (int i = 0; i < 300; ++i) + for (int j = 0; j < 200; ++j) + s7.insert(point2d(i, j)); + + util::node<I> node(s1); + node.add_child(s2); + node.add_child(s3); + + util::node<I>* node2 = node.search(s2); + mln_assertion(node2); + node2->add_child(s4); + node2->add_child(s5); + util::node<I>* node3 = node.search(s4); + mln_assertion(node3); + node3->add_child(s6); + + util::tree<I> tree (&node); + + tree.add_tree_up(s7); util::tree_to_image(tree, output); Index: trunk/milena/mln/display/save.hh =================================================================== --- trunk/milena/mln/display/save.hh (revision 1385) +++ trunk/milena/mln/display/save.hh (revision 1386) @@ -55,6 +55,10 @@ void save(const Image<I>& input_); + template <typename I> + void + save_color(const Image<I>& input_); + # ifndef MLN_INCLUDE_ONLY namespace impl @@ -79,6 +83,25 @@ map_saved_image_tmp_[(void*)input.id_ ()] = path_tmp; } + template <typename I> + void + save_color(const Image<I>& input_) + { + const I& input = exact (input_); + + /// Use of mkstemp instead tempmap. + char *tmp = (char*)malloc (12 * sizeof (char)); + strcpy(tmp, "/tmp/XXXXXX"); + if (mkstemp(tmp) == -1) + return; + std::string path_tmp = tmp; + + io::ppm::save(input, path_tmp); + + std::cout << input.id_ () << " = " << path_tmp << std::endl; + map_saved_image_tmp_[(void*)input.id_ ()] = path_tmp; + } + } // end of namespace mln::display::impl /// Facade. @@ -89,6 +112,13 @@ return impl::save(input_); } + template <typename I> + void + save_color(const Image<I>& input_) + { + return impl::save_color(input_); + } + # endif // !MLN_INCLUDE_ONLY } // end of namespace mln::display Index: trunk/milena/mln/util/tree_to_image.hh =================================================================== --- trunk/milena/mln/util/tree_to_image.hh (revision 1385) +++ trunk/milena/mln/util/tree_to_image.hh (revision 1386) @@ -37,6 +37,7 @@ */ #include <mln/util/tree.hh> +# include <mln/core/set_p.hh> namespace mln { @@ -46,7 +47,7 @@ template <typename T, typename I> void - tree_to_image_rec(tree<T>& tree, Image<I>& output_, const mln_value(I) lvl); + tree_to_image_rec(node<T>* node, Image<I>& output_); template <typename T, typename I> void @@ -56,20 +57,28 @@ template <typename T, typename I> void - tree_to_image_rec(tree<T>& tree, Image<I>& output_, const mln_value(I) lvl) + tree_to_image_rec(node<T>* node, Image<I>& output_) { I& output = exact(output_); - mln_piter(T) p(tree.elt_); + + mln_piter(set_p<point2d>) p(node->elt_.points); for_all(p) - output(p) = lvl; + { + std::cout << p + << std::endl; + output(p) = node->elt_.value; + } + typename std::vector< util::node<T>* >::const_iterator it = node->child_.begin(); - typename std::vector< util::tree<T>* >::const_iterator it = tree.child_.begin(); - for (; - it != tree.child_.end(); - ++it) - tree_to_image_rec((**it), output, lvl + 1); + for (int i = 0; + it != node->child_.end(); + ++it, ++i) + { + if (*it) + tree_to_image_rec((*it), output); + } } @@ -78,7 +87,7 @@ tree_to_image (tree<T>& tree, Image<I>& output_) { I& output = exact(output_); - tree_to_image_rec(tree, output, 1); + tree_to_image_rec(tree.root_, output); } # endif // ! MLN_INCLUDE_ONLY Index: trunk/milena/mln/util/tree.hh =================================================================== --- trunk/milena/mln/util/tree.hh (revision 1385) +++ trunk/milena/mln/util/tree.hh (revision 1386) @@ -44,37 +44,92 @@ { template <typename T> - struct tree + struct node { - tree(); - tree(T& elt); + node(); + node(T& elt); T& content(); const T& content() const; void add_child(T& elt); - void set_parent(tree<T>* parent); - tree<T>* get_parent(); + void set_parent(node<T>* parent); + node<T>* get_parent(); void print_rec(int n) const; - void print(void) const; - int search_rec(tree<T>** res, T& elt); - tree<T>* search(T& elt); + void print() const; + int search_rec(node<T>** res, T& elt); + node<T>* search(T& elt); T elt_; - tree<T>* parent_; - std::vector< tree<T>* > child_; + node<T>* parent_; + std::vector< node<T>* > child_; }; + template <typename T> + struct tree + { + typedef node<T> node_t; + tree(); + tree(node<T>* root); + + tree<T>* tree_get(T& elt); + void add_tree_up (T& elt); + void add_tree_down (T& elt); + + node<T>* root_; + }; # ifndef MLN_INCLUDE_ONLY template <typename T> tree<T>::tree() + : root_ (0) + { + } + + template <typename T> + tree<T>::tree(node<T>* root) + : root_ (root) + { + mln_assertion (root != 0); + } + + template <typename T> + tree<T>* + tree<T>::tree_get(T& elt) + { + node<T>* n = root_->search(elt); + tree<T>* res = new tree (n); + + return res; + } + + template <typename T> + void + tree<T>::add_tree_up(T& elt) + { + node<T>* n = new node<T> (elt); + root_->parent_ = n; + n->child_.push_back (root_); + root_ = n; + } + + template <typename T> + void + tree<T>::add_tree_down(T& elt) + { + node<T>* n = new node<T> (elt); + root_->child_.push_back (n); + } + + + template <typename T> + node<T>::node() : parent_ (0) { } template <typename T> - tree<T>::tree(T& elt) + node<T>::node(T& elt) : elt_ (elt), parent_ (0) { @@ -82,23 +137,23 @@ template <typename T> const T& - tree<T>::content() const + node<T>::content() const { return elt_; } template <typename T> T& - tree<T>::content() + node<T>::content() { return elt_; } template <typename T> void - tree<T>::add_child(T& elt) + node<T>::add_child(T& elt) { - tree<T>* s = new tree<T>(elt); + node<T>* s = new node<T>(elt); s->parent_ = this; this->child_.push_back(s); @@ -106,7 +161,7 @@ template <typename T> void - tree<T>::set_parent(tree<T>* parent) + node<T>::set_parent(node<T>* parent) { mln_assertion(parent != 0); parent_ = parent; @@ -115,15 +170,15 @@ template <typename T> - tree<T>* - tree<T>::get_parent() + node<T>* + node<T>::get_parent() { return parent_; } template <typename T> int - tree<T>::search_rec(tree<T>** res, T& elt) + node<T>::search_rec(node<T>** res, T& elt) { if (elt == this->elt_) { @@ -132,7 +187,7 @@ } else { - for (typename std::vector<tree<T>* >::iterator it = this->child_.begin(); + for (typename std::vector<node<T>* >::iterator it = this->child_.begin(); it != this->child_.end(); ++it) { if ((**it).search_rec(res, elt)) @@ -143,10 +198,10 @@ } template <typename T> - tree<T>* - tree<T>::search(T& elt) + node<T>* + node<T>::search(T& elt) { - tree<T>* res = 0; + node<T>* res = 0; if (search_rec(&res, elt)) return res; Index: trunk/milena/sandbox/garrigues/fllt.hh =================================================================== --- trunk/milena/sandbox/garrigues/fllt.hh (revision 1385) +++ trunk/milena/sandbox/garrigues/fllt.hh (revision 1386) @@ -72,19 +72,29 @@ # include <mln/pw/value.hh> # include <mln/pw/cst.hh> +# include <mln/util/tree_to_image.hh> +# include <mln/value/int_u8.hh> +# include <mln/level/stretch.hh> +# include <mln/level/compare.hh> +# include <mln/io/pgm/save.hh> + namespace mln { namespace fllt { - template <typename P> + template <typename P, typename V> struct fllt_node { + V value; set_p<P> points; set_p<P> holes; }; - # define fllt_node(P) util::tree< fllt_node<P> > + # define fllt_tree(P, V) util::tree< fllt_node<P, V> > + # define fllt_node(P, V) util::node< fllt_node<P, V> > + // # define fllt_node(P, V) typename fllt_tree(P, V)::node_t + // LOWER LEVEL SET : region = c4, border = c8 @@ -132,14 +142,14 @@ V& g, point2d& x0) { - std::cout << "entering step 1" << std::endl; + //std::cout << "entering step 1" << std::endl; // x0 <- a not tagged local mininum of ima. - std::cout << std::endl << "x0 = " << p << std::endl; + //std::cout << std::endl << "x0 = " << p << std::endl; x0 = p; // g <- u(x0) g = ima(x0); - std::cout << "g = " << g << std::endl; - std::cout << "exiting step 1" << std::endl; + //std::cout << "g = " << g << std::endl; + //std::cout << "exiting step 1" << std::endl; } template <typename P> @@ -148,7 +158,7 @@ set_p<P>& N, point2d& x0) { - std::cout << "entering step 2" << std::endl; + //std::cout << "entering step 2" << std::endl; // A <- {x0} A.clear(); A.insert(x0); @@ -156,7 +166,7 @@ R.clear(); // N <- {} N.clear(); - std::cout << "exiting step 2" << std::endl; + //std::cout << "exiting step 2" << std::endl; } @@ -169,7 +179,7 @@ V& gn) { static bool finished = false; - std::cout << "entering step 3" << std::endl; + //std::cout << "entering step 3" << std::endl; // Stop the algorithm. if (finished) @@ -185,17 +195,17 @@ N.insert (n); } - debug::println(u); + // debug::println(u); - std::cout << "A :" << std::endl; - if (A.npoints()) - debug::println(u | A); - std::cout << "N :" << std::endl; - if (N.npoints()) - debug::println(u | N); - std::cout << "R :" << std::endl; - if (R.npoints()) - debug::println(u | R); +// //std::cout << "A :" << std::endl; +// if (A.npoints()) +// //debug::println(u | A); +// //std::cout << "N :" << std::endl; +// if (N.npoints()) +// //debug::println(u | N); +// //std::cout << "R :" << std::endl; +// if (R.npoints()) +// //debug::println(u | R); // gn <- min u(x) x belongs to N. if ((u | set::inter(N, u.domain())).npoints() > 0) @@ -205,7 +215,7 @@ finished = true; gn += F::inc; } - std::cout << std::endl << "gN = " << gn << std::endl; + //std::cout << std::endl << "gN = " << gn << std::endl; // R <- R union A // tag the pixels of A. @@ -214,7 +224,7 @@ R.insert(qa); tagged(qa) = true; } - std::cout << "exiting step 3" << std::endl; + //std::cout << "exiting step 3" << std::endl; } @@ -226,16 +236,17 @@ set_p<P>& N, V& g, V& gn, - fllt_node(P)* current_region, - image2d<fllt_node(P)*>& regions + fllt_node(P, V)*& current_region, + image2d<fllt_node(P, V)*>& regions ) { - std::cout << "entering step 4_1" << std::endl; + //std::cout << "entering step 4_1" << std::endl; // Create a new conected component. // FIXME : we can make it faster. mln_piter(set_p<P>) p(R); - current_region = new fllt_node(P)(); + current_region = new fllt_node(P, V)(); + current_region->content().value = g; for_all(p) { if (regions(p) == 0) @@ -260,9 +271,8 @@ labeling::level(border_ima, true, F::bdr_nbh(), tmp, n); // debug::println(border_ima); - std::cout << "nb composantes :" << n << std::endl; - debug::println(tmp); - + //std::cout << "nb composantes :" << n << std::endl; + // debug::println(tmp); if (n > 1) { @@ -283,18 +293,18 @@ g = gn; // A <- {x belongs to N / u(x) == g} A.clear(); - A = set::uni(A, N | pw::value(u) == pw::cst(g)); + A = set::uni(A, set::inter(N, u.domain()) | pw::value(u) == pw::cst(g)); // N <- N\{x belongs to N / u(x) == g} - N = set::diff(N, N | pw::value(u) == pw::cst(g)); + N = set::diff(N, set::inter(N, u.domain()) | pw::value(u) == pw::cst(g)); - std::cout << "A :" << std::endl; - if (A.npoints()) - debug::println(u | A); - std::cout << "N :" << std::endl; - if (N.npoints()) - debug::println(u | N); +// std::cout << "A :" << std::endl; +// if (A.npoints()) +// debug::println(u | A); +// std::cout << "N :" << std::endl; +// if (N.npoints()) +// debug::println(u | N); - std::cout << "exiting step 4_1" << std::endl; + //std::cout << "exiting step 4_1" << std::endl; } @@ -304,25 +314,25 @@ set_p<P>& A, set_p<P>& N, V& g, - fllt_node(P)* current_region, - image2d<fllt_node(P)*>& regions + fllt_node(P, V)* current_region, + image2d<fllt_node(P, V)*>& regions ) { - std::cout << "entering step 4_2" << std::endl; + //std::cout << "entering step 4_2" << std::endl; // A <- {x belongs to N / u(x) == g} - A = set::uni(A, N | pw::value(u) == pw::cst(g)); + A = set::uni(A, set::inter(N, u.domain()) | pw::value(u) == pw::cst(g)); // N <- N\{x belongs to N / u(x) == g} - N = set::diff(N, N | pw::value(u) == pw::cst(g)); + N = set::diff(N, set::inter(N, u.domain()) | pw::value(u) == pw::cst(g)); - std::cout << "A :" << std::endl; - if (A.npoints()) - debug::println(u | A); - std::cout << "N :" << std::endl; - if (N.npoints()) - debug::println(u | N); +// std::cout << "A :" << std::endl; +// if (A.npoints()) +// debug::println(u | A); +// std::cout << "N :" << std::endl; +// if (N.npoints()) +// debug::println(u | N); - std::cout << "exiting step 4_2" << std::endl; + //std::cout << "exiting step 4_2" << std::endl; } /// IF g > gn. @@ -332,7 +342,7 @@ const set_p<P>& R, const V& g) { - std::cout << "entering step 4_3" << std::endl; + //std::cout << "entering step 4_3" << std::endl; // set the gray-level of the pixels of R to g. mln_piter(set_p<P>) p(R); @@ -342,13 +352,13 @@ u (p) = g; } - std::cout << "exiting step 4_3" << std::endl; + //std::cout << "exiting step 4_3" << std::endl; } template <typename V, typename F> - fllt_node(point2d)* + fllt_tree(point2d, V)* compute_level_set(const image2d<V>& ima) { typedef point2d P; @@ -358,10 +368,9 @@ typedef mln::image_if< mln::image2d<V>, mln::fun::greater_p2b_expr_<mln::pw::value_<mln::image2d<V> >, - mln::pw::cst_<V> > + mln::pw::cst_<int> > - // Declarations. set_p<P> R, N, A; V g, gn; @@ -370,11 +379,11 @@ image2d<V> u = clone(ima); border::fill(u, 0); - std::cout << "image U:" << std::endl; - debug::println_with_border(u); + //std::cout << "image U:" << std::endl; + // debug::println_with_border(u); image2d<bool> tagged(ima.domain()); - fllt_node(P)* current_region; - image2d<fllt_node(P)*> regions(ima.domain()); + fllt_node(P, V)* current_region; + image2d<fllt_node(P, V)*> regions(ima.domain()); // INIT R.clear(); @@ -392,12 +401,13 @@ unsigned nlabels; F::regional_extremum(ima, F::reg_nbh(), min_locals, nlabels); - debug::println(min_locals); - debug::println(min_locals | (pw::value(min_locals) > pw::cst(0))); +// debug::println(min_locals); +// debug::println(min_locals | (pw::value(min_locals) > pw::cst(0))); /// Algorithm. { // For all locals extremums + //void* x = min_locals | (pw::value(min_locals) > pw::cst(0)); I_IF min_locals_list(min_locals | (pw::value(min_locals) > pw::cst(0))); mln_piter(I_IF) p(min_locals_list.domain()); for_all(p) @@ -409,7 +419,7 @@ step2(A, R, N, x0); while (1) { - std::cout << "g = " << g << std::endl; + //std::cout << "g = " << g << std::endl; step3<V, P, F>(u, tagged, A, R, N, gn); /// step4. if (F::compare(g, gn)) @@ -435,14 +445,35 @@ break; } } + //std::cout << "current_region = " << current_region << std::endl; } } // end of Algorithm std::cout << "END OF ALGORITHM" << std::endl; - debug::println(regions); - //debug::println(ima | regions(make::point2d(-4,-1))->content().points); + image2d<value::int_u8> output (ima.domain ()); + fllt_tree(P, V)& tree = *new fllt_tree(P, V)(current_region); + util::tree_to_image (tree, output); + + + debug::println(output); + std::cout << std::endl; + debug::println(ima); + + if (output != ima) + { + std::cerr << "BUG!!!" << std::endl; + abort(); + } + + io::pgm::save(output, "out.pgm"); + std::cout << "out.pgm generate" + << std::endl; - return (current_region); + + // debug::println(regions); + //debug::println(ima | regions(make:defined reference to `mln::fllt::lower<mln::value::int_u<8u> >::inc':point2d(-4,-1))->content().points); + + return (&tree); } // end of compute_level_set @@ -501,9 +532,9 @@ static const neighb2d& reg_nbh() { return c8(); } }; - template <typename P> - void find_shapes_of_holes(fllt_node(P)* lower, - fllt_node(P)* upper) + template <typename P, typename V> + void find_shapes_of_holes(fllt_node(P, V)* lower, + fllt_node(P, V)* upper) { } @@ -513,14 +544,14 @@ { typedef point2d P; - fllt_node(P)* upper_tree; - fllt_node(P)* lower_tree; + fllt_tree(P, V)* upper_tree; + fllt_tree(P, V)* lower_tree; lower_tree = compute_level_set<V, lower<V> >(ima); - upper_tree = compute_level_set<V, upper<V> >(ima); + // upper_tree = compute_level_set<V, upper<V> >(ima); - find_shapes_of_holes(lower_tree, upper_tree); + //find_shapes_of_holes(lower_tree, upper_tree); } } // end of namespace mln::fllt Index: trunk/milena/sandbox/garrigues/test_fllt.cc =================================================================== --- trunk/milena/sandbox/garrigues/test_fllt.cc (revision 1385) +++ trunk/milena/sandbox/garrigues/test_fllt.cc (revision 1386) @@ -1,30 +1,40 @@ -# include <mln/core/image2d.hh> # 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] = {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,4,2,3,2,1,1, - 1,3,3,4,2,3,2,1,1, - 1,3,3,4,2,3,2,1,1, - 1,3,3,4,2,3,2,1,1}; +// 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); + - w_window2d_int w_win = make::w_window2d(ws); + image2d<value::int_u8> ima = io::pgm::load("../../img/tiny.pgm"); - image2d<int> ima = convert::to_image(w_win); + image2d<int> ima_int(ima.domain()); +level::fill(ima_int, ima); debug::println(ima); - fllt::fllt(ima); - //fllt::fllt(ima); + fllt::fllt(ima_int); }