URL: https://svn.lrde.epita.fr/svn/oln/trunk/milena/sandbox ChangeLog: 2008-09-02 Matthieu Garrigues <garrigues@lrde.epita.fr> * geraud/fllt/fllt.svg.7.hh: Add comments to the working version of FLLT. --- fllt.svg.7.hh | 96 +++++++++++++++++++++++++++++++++++++++++++++++++++------- 1 file changed, 85 insertions(+), 11 deletions(-) Index: trunk/milena/sandbox/geraud/fllt/fllt.svg.7.hh =================================================================== --- trunk/milena/sandbox/geraud/fllt/fllt.svg.7.hh (revision 2163) +++ trunk/milena/sandbox/geraud/fllt/fllt.svg.7.hh (revision 2164) @@ -331,9 +331,6 @@ ++label; - // if (holes.size() == 2) - // std::cout << holes[0] << holes[1] << std::endl; - // std::cout << " <<<<<<<exiting blob." << std::endl; } template <typename P, typename V> @@ -393,7 +390,8 @@ } } - // LOWER LEVEL SET : region = c4, border = c8 + // LOWER LEVEL SET information to compute the max tree. + // -> region = c4, border = c8 template <typename V> struct lower { @@ -421,7 +419,8 @@ }; - // UPPER LEVEL SET : region = c8, border = c4 + // UPPER LEVEL SET information to compute the max tree. + // -> region = c8, border = c4 template <typename V> struct upper { @@ -445,6 +444,14 @@ static const neighb2d& reg_nbh() { return c8(); } }; + /*! Fast computation of a min/max tree. + * + * \param[in] input_ An input image. + * \param[out] smallest_shapes We stock in this image, for each point, a pointer + * to the smallest shape containing it. + * \return The min/max tree built. + * + */ template <typename I, typename Set> fllt_tree(mln_point(I), mln_value(I))& level_set(const Image<I>& input_, @@ -560,7 +567,7 @@ deja_vu(x) = in_N; } } - // gN = min u(x) for all x in N + // gN <- min u(x) for all x in N update_gN(N, gN, Set()); // FIXME: update the number of CC of the border of R @@ -609,7 +616,6 @@ // c) else { - // FIXME: IDEA: this change might be performed while R is constructed(?) n_step_4c++; mln_piter(I) r(N_box); for_all(r) @@ -627,6 +633,15 @@ return *new tree_type(current_cc); } + /*! Get the hole of a shape which contains a given point. + * + * \param[in] node a shape. + * \param[in] p a point. + * \param[in] other_reg The map which associate a point with its smallest shape + * of the oposite tree. + * \return true if A is included in B. + * + */ // F is the set in which we get the node. template <typename P, typename V, typename F> fllt_node(P, V)* @@ -636,6 +651,7 @@ { fllt_node(P, V)* s = other_reg(p); mln_assertion(s); + // Go up the tree. while (s->parent() && F::compare(s->parent()->elt().value, node.elt().value)) { mln_assertion(s); @@ -649,6 +665,14 @@ return s; } + /*! Test the inclusion of two shapes of the same tree + * + * \param[in] A a shape. + * \param[in] B a shape. + * \return true if A is included in B. + * + * \pre The shapes have to come from the same tree. + */ template <typename P, typename V> bool shape_is_included(fllt_node(P, V)* A, fllt_node(P, V)* B) @@ -656,6 +680,17 @@ return A->parent() == B || A == B; } + /*! Associated the points of the holes of the min/max tree's shapes. + * + * \param[in] lower_tree The min tree. + * \param[in] upper_tree The max tree. + * \param[in] low_reg The map which associate a point with its smallest shape + * of the min tree. + * \param[in] upp_reg The map which associate a point with its smallest shape + * of the max tree. + * \return The merged tree. + * + */ template <typename P, typename V> void find_all_holes(fllt_tree(P, V)& lower_tree, fllt_tree(P, V)& upper_tree, @@ -665,6 +700,7 @@ typedef p_array<P> arr_t; typedef fllt_node(P, V) node_type; + // Get the holes of the min tree { fllt_branch_iter_ind(P, V) node_(lower_tree.main_branch()); for_all(node_) @@ -676,6 +712,7 @@ } } + // Get the holes of the max tree { fllt_branch_iter_ind(P, V) node_(upper_tree.main_branch()); for_all(node_) @@ -688,6 +725,17 @@ } } + /*! Merge the Min and the max tree. + * + * \param[in] lower_tree The min tree. + * \param[in] upper_tree The max tree. + * \param[in] low_reg The map which associate a point with its smallest shape + * of the min tree. + * \param[in] upp_reg The map which associate a point with its smallest shape + * of the max tree. + * \return The merged tree. + * + */ template <typename I> fllt_tree(mln_point(I), mln_value(I)) merge_trees(fllt_tree(mln_point(I), mln_value(I))& lower_tree, @@ -706,17 +754,24 @@ typedef p_array<P> arr_t; + // Here, a hole of a shape of the max or min tree is represented + // by a point belonging to this hole. We need to associate each of + // these points with its shape in the oposite tree. find_all_holes(lower_tree, upper_tree, low_reg, upp_reg); std::vector<node_type*> to_fill; fllt_branch_iter_ind(P, V) node_(lower_tree.main_branch()); + // Browse the shapes of the min_tree, in order to put as child of + // min tree's shapes the shapes of the max tree corresponding to + // their holes. for_all(node_) { node_type& node = *node_; + // If the node was not in the min tree at the begining, we ignore it. if (node.elt().set_id != lower<V>::id) continue; - // std::cout << "Fill " << &node << std::endl; + // Browse the holes of the shape. typename std::vector<fllt_node(P, V)*>::iterator hole_; for (hole_ = node.elt().hole_shapes.begin(); hole_ != node.elt().hole_shapes.end(); @@ -724,6 +779,7 @@ { fllt_node(P, V)* hole = *hole_; + // Check if hole_ is contained by a hole of the children of node. bool child_has_bigger_hole = false; typename fllt_node(P, V)::children_t::iterator it; for (it = node.children().begin(); it != node.children().end() && !child_has_bigger_hole; it++) @@ -735,8 +791,6 @@ child_hole_++) { fllt_node(P, V)* child_hole = *child_hole_; - // std::cout << "hole : " << hole << " " << hole->elt().points << " " << std::endl; - // std::cout << "child hole : " << child_hole << " " << child_hole->elt().points << std::endl; if (shape_is_included(hole, child_hole)) { child_has_bigger_hole = true; @@ -744,6 +798,9 @@ } } // end of browsing child's holes. } // end of browsing childs. + + // If no, move the shape of the max tree previously associated to this hole. + // as child of node. if (!child_has_bigger_hole) { // // std::cout << "move " << hole << " as child of " << &node << std::endl; @@ -754,6 +811,12 @@ node.elt().holes.clear(); } // end of browsing lower_tree. + // At this step, we have filled all the holes of the min + // tree. But, by filling these holes, we introduced somes holes of + // the max tree in the result tree. We need to fill them. + + // Thus, we browse the shapes of the max tree previously merged in + // the min tree, in order to check their holes. for(typename std::vector<node_type*>::iterator node_ = to_fill.begin(); node_ != to_fill.end(); node_++) @@ -767,6 +830,7 @@ if (node.elt().set_id != upper<V>::id) continue; + // Check if hole_ is contained by a hole of the children of node. typename std::vector<fllt_node(P, V)*>::iterator hole_; for (hole_ = node.elt().hole_shapes.begin(); hole_ != node.elt().hole_shapes.end(); @@ -785,7 +849,6 @@ child_hole_++) { fllt_node(P, V)* child_hole = *child_hole_; - //if (hole->elt().points <= child_hole->elt().points) if (shape_is_included(hole, child_hole)) { child_has_bigger_hole = true; @@ -794,6 +857,8 @@ } // end of browsing child's holes. } // end of browsing childs. + // If no, move the shape of the max tree previously associated to this hole. + // as child of node. if (!child_has_bigger_hole) node.add_child(hole); @@ -806,6 +871,12 @@ return lower_tree; } + /*! This function compute the fllt tree of an image. + * + * \param[in] input_ An input image. + * \return The computed tree. + * + */ template <typename I> fllt_tree(mln_point(I), mln_value(I)) fllt(const Image<I>& input_) @@ -820,12 +891,15 @@ image2d<fllt_node(P, V)*> low_reg(input.domain()); image2d<fllt_node(P, V)*> upp_reg(input.domain()); + // Compute the Min tree. std::cout << "1/ Compute the lower level set.----------------------------------------" << std::endl; lower_tree = level_set<I, lower<V> >(input, low_reg); + // Compute the Max tree. std::cout << "2/ Compute the upper level set.----------------------------------------" << std::endl; upper_tree = level_set<I, upper<V> >(input, upp_reg); + // Merge the two trees. std::cout << "3/ Merge.---------------------------------------------------------------" << std::endl; fllt_tree(P, V) result_tree = merge_trees(lower_tree, upper_tree, low_reg, upp_reg, input);