April 2008 - Olena-patches

1885: Fix the definitions of graph-related neighborhoods.
by Roland Levillain 22 Apr '08

22 Apr '08

https://svn.lrde.epita.fr/svn/oln/trunk/milena Index: ChangeLog from Roland Levillain <roland(a)lrde.epita.fr> Fix the definitions of graph-related neighborhoods. * mln/core/line_graph_elt_neighborhood.hh: (mln::line_graph_elt_neighborhood::compute_neighbors_): Don't add the reference (central) point to its own neighborhood. * mln/core/p_line_graph.hh: Add a FIXME. * mln/core/p_graph.hh (mln::p_graph::adjacent): New methods. Use them to factor (mln::p_graph::adjacent_or_equal(const node_id&, const node_id&)): ...this method. * mln/core/graph_neighborhood_piter.hh, * mln/core/graph_elt_neighborhood.hh (mln::graph_elt_neighborhood::start) (mln::graph_elt_neighborhood::next_): s/adjacent_or_equal/adjacent/. graph_elt_neighborhood.hh | 4 +- graph_neighborhood_piter.hh | 16 +++++----- line_graph_elt_neighborhood.hh | 3 - p_graph.hh | 64 ++++++++++++++++++++++++++++++----------- p_line_graph.hh | 2 + 5 files changed, 59 insertions(+), 30 deletions(-) Index: mln/core/line_graph_elt_neighborhood.hh --- mln/core/line_graph_elt_neighborhood.hh (revision 1884) +++ mln/core/line_graph_elt_neighborhood.hh (working copy) @@ -107,9 +107,6 @@ Piter& piter = exact(piter_); neighbors_t& neighbors = piter.neighbors(); neighbors.clear(); - // Add the reference piter itself. We might reconsider this, or - // create an elementary neighbors without the reference point. - neighbors.insert(piter.p_ref().id()); /* FIXME: Move this computation out of the window. In fact, this should be a service of the graph, also proposed by the p_line_graph. */ Index: mln/core/p_line_graph.hh --- mln/core/p_line_graph.hh (revision 1884) +++ mln/core/p_line_graph.hh (working copy) @@ -39,6 +39,8 @@ /* FIXME: This class shares a lot with p_graph. Factor as much as possible. */ +// FIXME: We should move the `adjacent_or_equal method' from +// iterators into this class. /// \file mln/core/p_line_graph.hh /// \brief Definition of a point set based on line graph. Index: mln/core/p_graph.hh --- mln/core/p_graph.hh (revision 1884) +++ mln/core/p_graph.hh (working copy) @@ -94,12 +94,19 @@ /// to the edge id \a e. const P& node2(const util::edge_id& e) const; + /// Adjacency tests. + /// \{ + /// Return true if the psites lhs and rhs are adjacent. + bool adjacent(const psite& lhs, const psite& rhs) const; + /// Return true if the nodes lhs and rhs are adjacent. + bool adjacent(const util::node_id& lhs, const util::node_id& rhs) const; + /// Return true if the psites lhs and rhs are adjacent, or equal. bool adjacent_or_equal(const psite& lhs, const psite& rhs) const; - /// Return true if the nodes lhs and rhs are adjacent, or equal bool adjacent_or_equal(const util::node_id& lhs, const util::node_id& rhs) const; + /// \} /// Return the graph associated to the p_graph domain: const graph& to_graph() const; @@ -231,9 +238,42 @@ template <typename P> inline bool + p_graph::adjacent(const psite& lhs, const psite& rhs) const + { + mln_assertion(&lhs.pg() == this && rhs.pg() == this); + return adjacent(lhs.id(), rhs.id()); + } + + /* FIXME: This could be more efficient, if the graph structure had a + richer interface. */ + template <typename P> + inline + bool + p_graph::adjacent(const util::node_id& lhs, + const util::node_id& rhs) const + { + mln_assertion(lhs < this->npoints()); + mln_assertion(rhs < this->npoints()); + + // Check whether RHS and LHS are adjacent (i.e., whether RHS is + // among the neighbors of LHS). + typedef std::vector<util::edge_id> edges_t; + const edges_t& lhs_neighbs = gr_->nodes()[lhs]->edges; + for (edges_t::const_iterator e = lhs_neighbs.begin(); + e != lhs_neighbs.end(); ++e) + if (gr_->edges()[*e]->n1() == rhs || + gr_->edges()[*e]->n2() == rhs) + return true; + + return false; + } + + template <typename P> + inline + bool p_graph::adjacent_or_equal(const psite& lhs, const psite& rhs) const { - assert (&lhs.pg() == this && rhs.pg() == this); + mln_assertion(&lhs.pg() == this && rhs.pg() == this); return adjacent_or_equal(lhs.id(), rhs.id()); } @@ -243,24 +283,14 @@ p_graph::adjacent_or_equal(const util::node_id& lhs, const util::node_id& rhs) const { - // FIXME: This is inefficient. - - assert (lhs < this->npoints()); - assert (rhs < this->npoints()); + mln_assertion(lhs < this->npoints()); + mln_assertion(rhs < this->npoints()); + // Check whether LHS and RHS are equal. if (rhs == lhs) return true; - - // Check whether the iterator is among the neighbors of P_REF_. - typedef std::vector<util::node_id> adjacency_type; - const adjacency_type& lhs_neighbs = gr_->nodes()[lhs]->edges; - - adjacency_type::const_iterator j = - std::find (lhs_neighbs.begin(), lhs_neighbs.end(), rhs); - if (j != lhs_neighbs.end()) - return true; - - return false; + // Check whether RHS and LHS are adjacent. + return adjacent(rhs, lhs); } template <typename P> Index: mln/core/graph_neighborhood_piter.hh --- mln/core/graph_neighborhood_piter.hh (revision 1884) +++ mln/core/graph_neighborhood_piter.hh (working copy) @@ -98,8 +98,8 @@ /// Go to the next point. void next_(); - /// Is the piter adjacent or equal to the reference point? - bool adjacent_or_equal_to_p_ref_() const; + /// Is the piter adjacent to the reference point? + bool adjacent_to_p_ref_() const; /// Update the internal data of the iterator. void update_(); /// \} @@ -180,8 +180,8 @@ /// Go to the next point. void next_(); - /// Is the piter adjacent or equal to the reference point? - bool adjacent_or_equal_to_p_ref_() const; + /// Is the piter adjacent to the reference point? + bool adjacent_to_p_ref_() const; /// Update the internal data of the iterator. void update_(); /// \} @@ -302,9 +302,9 @@ template <typename P, typename N> inline bool - graph_neighborhood_fwd_piter<P, N>::adjacent_or_equal_to_p_ref_() const + graph_neighborhood_fwd_piter<P, N>::adjacent_to_p_ref_() const { - return p_ref_.pg().adjacent_or_equal(p_ref_.id(), id_); + return p_ref_.pg().adjacent(p_ref_.id(), id_); } template <typename P, typename N> @@ -430,9 +430,9 @@ template <typename P, typename N> inline bool - graph_neighborhood_bkd_piter<P, N>::adjacent_or_equal_to_p_ref_() const + graph_neighborhood_bkd_piter<P, N>::adjacent_to_p_ref_() const { - return p_ref_.pg().adjacent_or_equal(p_ref_.id(), id_); + return p_ref_.pg().adjacent(p_ref_.id(), id_); } template <typename P, typename N> Index: mln/core/graph_elt_neighborhood.hh --- mln/core/graph_elt_neighborhood.hh (revision 1884) +++ mln/core/graph_elt_neighborhood.hh (working copy) @@ -104,7 +104,7 @@ { Piter& piter = exact(piter_); piter.first_(); - if (!piter.adjacent_or_equal_to_p_ref_()) + if (!piter.adjacent_to_p_ref_()) next_(piter); } @@ -121,7 +121,7 @@ neighbors in constant time. */ do piter.step_(); - while (piter.is_valid() && !piter.adjacent_or_equal_to_p_ref_()); + while (piter.is_valid() && !piter.adjacent_to_p_ref_()); } # endif // ! MLN_INCLUDE_ONLY

1 0

1884: Remove a name clash ambiguity detected by g++ 4.3.
by Roland Levillain 22 Apr '08

22 Apr '08

https://svn.lrde.epita.fr/svn/oln/trunk/milena Index: ChangeLog from Roland Levillain <roland(a)lrde.epita.fr> Remove a name clash ambiguity detected by g++ 4.3. * mln/core/point.hh (mln::internal::point_to_<M, C>::h_vec): Use a fully qualified name to please g++ 4.3. point.hh | 2 +- 1 file changed, 1 insertion(+), 1 deletion(-) Index: mln/core/point.hh --- mln/core/point.hh (revision 1883) +++ mln/core/point.hh (working copy) @@ -63,7 +63,7 @@ struct point_to_ { typedef algebra::vec<M::dim, C> metal_vec; - typedef h_vec<M::dim, C> h_vec; + typedef mln::h_vec<M::dim, C> h_vec; }; } // end of namespace mln::internal

1 0

milena r1883: Add green and blue getters
by Caroline Vigouroux 22 Apr '08

22 Apr '08

URL: https://svn.lrde.epita.fr/svn/oln/trunk/milena ChangeLog: 2008-04-22 Caroline Vigouroux <vigour_c(a)epita.fr> Add green and blue getters. * cmy/get_blue.hh, cmy/get_green.hh, hsi/get_blue.hh, hsi/get_green.hh, xyz/get_blue.hh, xyz/get_green.hh, yiq/get_blue.hh, yiq/get_green.hh, yuv/get_blue.hh, yuv/get_green.hh: New green and blue getters. * yuv/get_red.hh: New red getter. * yuv/fun.hh: Remove. --- cmy/get_blue.hh | 67 +++++++++++++++++++++++++++++++++++++++++++++++++++++++ cmy/get_green.hh | 56 +++++++++++++++++++++++++++++++++++++++++++++ hsi/get_blue.hh | 67 +++++++++++++++++++++++++++++++++++++++++++++++++++++++ hsi/get_green.hh | 67 +++++++++++++++++++++++++++++++++++++++++++++++++++++++ xyz/get_blue.hh | 56 +++++++++++++++++++++++++++++++++++++++++++++ xyz/get_green.hh | 56 +++++++++++++++++++++++++++++++++++++++++++++ yiq/get_blue.hh | 56 +++++++++++++++++++++++++++++++++++++++++++++ yiq/get_green.hh | 55 +++++++++++++++++++++++++++++++++++++++++++++ yuv/get_blue.hh | 56 +++++++++++++++++++++++++++++++++++++++++++++ yuv/get_green.hh | 56 +++++++++++++++++++++++++++++++++++++++++++++ yuv/get_red.hh | 58 +++++++++++++++++++++++++++++++++++++++++++++++ 11 files changed, 650 insertions(+) Index: trunk/milena/sandbox/vigouroux/yuv/fun.hh (deleted) =================================================================== Index: trunk/milena/sandbox/vigouroux/yuv/get_blue.hh =================================================================== --- trunk/milena/sandbox/vigouroux/yuv/get_blue.hh (revision 0) +++ trunk/milena/sandbox/vigouroux/yuv/get_blue.hh (revision 1883) @@ -0,0 +1,56 @@ +#include <cmath> + +#include <mln/core/image_if_value.hh> +#include <mln/core/inplace.hh> +#include <mln/core/w_window2d_int.hh> +#include <mln/display/show.hh> +#include <mln/io/ppm/save.hh> +#include <mln/display/save_and_show.hh> +#include <mln/level/fill.hh> +#include <mln/math/round.hh> + +#include "../color/my_yuv.hh" + +#ifndef MLN_YUV_BLUE_HH +# define MLN_YUV_BLUE_HH + +namespace mln +{ + + + namespace fun + { + + namespace v2v + { + template <typename T_rgb> + struct f_blue_yuv_ : public Function_v2v< f_blue_yuv_<T_rgb> > + { + typedef T_rgb result; + + template <typename T_yuv> + T_rgb operator()(const T_yuv& yuv) const + { + typedef typename T_rgb::blue_t blue_t; + + static math::round<blue_t> to_b; + + blue_t b = to_b(yuv.y() + 2.03211 * yuv.u()); + + T_rgb rgb(0, 0, b); + + return rgb; + } + }; + + typedef f_blue_yuv_<value::rgb8> f_yuv_blue_t; + + f_yuv_blue_t f_yuv_blue; + + } // end of namespace fun::v2v + + } // end of namespace fun + +} // end of namespace mln + +#endif // ! MLN_YUV_BLUE_HH Index: trunk/milena/sandbox/vigouroux/yuv/get_red.hh =================================================================== --- trunk/milena/sandbox/vigouroux/yuv/get_red.hh (revision 0) +++ trunk/milena/sandbox/vigouroux/yuv/get_red.hh (revision 1883) @@ -0,0 +1,58 @@ +#include <cmath> + +#include <mln/core/image_if_value.hh> +#include <mln/core/inplace.hh> +#include <mln/core/w_window2d_int.hh> +#include <mln/display/show.hh> +#include <mln/io/ppm/save.hh> +#include <mln/display/save_and_show.hh> +#include <mln/level/fill.hh> +#include <mln/math/round.hh> + +#include "my_yuv.hh" + +#ifndef MLN_YUV_FUN_HH +# define MLN_YUV_FUN_HH + +namespace mln +{ + + + namespace fun + { + + namespace v2v + { + template <typename T_rgb> + struct f_yuv_ : public Function_v2v< f_yuv_<T_rgb> > + { + typedef T_rgb result; + + template <typename T_yuv> + T_rgb operator()(const T_yuv& yuv) const + { + int r; + int g; + int b; + + r = int(yuv.y() + 1.13983 * yuv.v()); + g = int(yuv.y() - 0.39465 * yuv.u() - 0.58060 * yuv.v()); + b = int(yuv.y() + 2.03211 * yuv.u()); + + struct value::rgb<8> rgb(r, g, b); + + return (rgb); + } + }; + + typedef f_yuv_<value::rgb8> f_yuv_3x8_t; + + f_yuv_3x8_t f_yuv_3x8; + + } // end of namespace fun::v2v + + } // end of namespace fun + +} // end of namespace mln + +#endif // ! MLN_VALUE_YUV_HH Index: trunk/milena/sandbox/vigouroux/yuv/get_green.hh =================================================================== --- trunk/milena/sandbox/vigouroux/yuv/get_green.hh (revision 0) +++ trunk/milena/sandbox/vigouroux/yuv/get_green.hh (revision 1883) @@ -0,0 +1,56 @@ +#include <cmath> + +#include <mln/core/image_if_value.hh> +#include <mln/core/inplace.hh> +#include <mln/core/w_window2d_int.hh> +#include <mln/display/show.hh> +#include <mln/io/ppm/save.hh> +#include <mln/display/save_and_show.hh> +#include <mln/level/fill.hh> +#include <mln/math/round.hh> + +#include "../color/my_yuv.hh" + +#ifndef MLN_YUV_GREEN_HH +# define MLN_YUV_GREEN_HH + +namespace mln +{ + + + namespace fun + { + + namespace v2v + { + template <typename T_rgb> + struct f_green_yuv_ : public Function_v2v< f_green_yuv_<T_rgb> > + { + typedef T_rgb result; + + template <typename T_yuv> + T_rgb operator()(const T_yuv& yuv) const + { + typedef typename T_rgb::green_t green_t; + + static math::round<green_t> to_g; + + green_t g = to_g(yuv.y() - 0.39465 * yuv.u() - 0.58060 * yuv.v()); + + T_rgb rgb(0, g, 0); + + return rgb; + } + }; + + typedef f_green_yuv_<value::rgb8> f_yuv_green_t; + + f_yuv_green_t f_yuv_green; + + } // end of namespace fun::v2v + + } // end of namespace fun + +} // end of namespace mln + +#endif // ! MLN_YUV_GREEN_HH Index: trunk/milena/sandbox/vigouroux/hsi/get_blue.hh =================================================================== --- trunk/milena/sandbox/vigouroux/hsi/get_blue.hh (revision 0) +++ trunk/milena/sandbox/vigouroux/hsi/get_blue.hh (revision 1883) @@ -0,0 +1,67 @@ +#include <cmath> + +#include <mln/core/image_if_value.hh> +#include <mln/core/inplace.hh> +#include <mln/core/w_window2d_int.hh> +#include <mln/display/show.hh> +#include <mln/io/ppm/save.hh> +#include <mln/display/save_and_show.hh> +#include <mln/level/fill.hh> +#include <mln/math/round.hh> + +#include "../color/my_hsi.hh" + +#ifndef MLN_HSI_BLUE_HH +# define MLN_HSI_BLUE_HH + +namespace mln +{ + + + namespace fun + { + + namespace v2v + { + template <typename T_rgb> + struct f_blue_hsi_ : public Function_v2v< f_blue_hsi_<T_rgb> > + { + typedef T_rgb result; + + template <typename T_hsi> + T_rgb operator()(const T_hsi& hsi) const + { + typedef typename T_rgb::blue_t blue_t; + + static math::round<blue_t> to_b; + + static const float + sqrt3_3 = std::sqrt(3) / 3, + inv_sqrt6 = 1 / std::sqrt(6), + inv_sqrt2 = 1 / std::sqrt(2); + + float + h = hsi.hue() / 180.0 * 3.1415, + alpha = hsi.sat() * std::cos(h), + beta = hsi.sat() * std::sin(h); + + + blue_t b = to_b(sqrt3_3 * hsi.inty() - inv_sqrt2 * alpha - inv_sqrt6 * beta); + + T_rgb rgb(0, 0, b); + + return rgb; + } + }; + + typedef f_blue_hsi_<value::rgb8> f_hsi_blue_t; + + f_hsi_blue_t f_hsi_blue; + + } // end of namespace fun::v2v + + } // end of namespace fun + +} // end of namespace mln + +#endif // ! MLN_HSI_BLUE_HH Index: trunk/milena/sandbox/vigouroux/hsi/get_green.hh =================================================================== --- trunk/milena/sandbox/vigouroux/hsi/get_green.hh (revision 0) +++ trunk/milena/sandbox/vigouroux/hsi/get_green.hh (revision 1883) @@ -0,0 +1,67 @@ +#include <cmath> + +#include <mln/core/image_if_value.hh> +#include <mln/core/inplace.hh> +#include <mln/core/w_window2d_int.hh> +#include <mln/display/show.hh> +#include <mln/io/ppm/save.hh> +#include <mln/display/save_and_show.hh> +#include <mln/level/fill.hh> +#include <mln/math/round.hh> + +#include "../color/my_hsi.hh" + +#ifndef MLN_HSI_GREEN_HH +# define MLN_HSI_GREEN_HH + +namespace mln +{ + + + namespace fun + { + + namespace v2v + { + template <typename T_rgb> + struct f_green_hsi_ : public Function_v2v< f_green_hsi_<T_rgb> > + { + typedef T_rgb result; + + template <typename T_hsi> + T_rgb operator()(const T_hsi& hsi) const + { + typedef typename T_rgb::green_t green_t; + + static math::round<green_t> to_g; + + static const float + sqrt3_3 = std::sqrt(3) / 3, + inv_sqrt6 = 1 / std::sqrt(6), + inv_sqrt2 = 1 / std::sqrt(2); + + float + h = hsi.hue() / 180.0 * 3.1415, + alpha = hsi.sat() * std::cos(h), + beta = hsi.sat() * std::sin(h); + + + green_t g = to_g(sqrt3_3 * hsi.inty() + inv_sqrt2 * alpha - inv_sqrt6 * beta); + + T_rgb rgb(0, g, 0); + + return rgb; + } + }; + + typedef f_green_hsi_<value::rgb8> f_hsi_green_t; + + f_hsi_green_t f_hsi_green; + + } // end of namespace fun::v2v + + } // end of namespace fun + +} // end of namespace mln + +#endif // ! MLN_HSI_GREEN_HH Index: trunk/milena/sandbox/vigouroux/cmy/get_blue.hh =================================================================== --- trunk/milena/sandbox/vigouroux/cmy/get_blue.hh (revision 0) +++ trunk/milena/sandbox/vigouroux/cmy/get_blue.hh (revision 1883) @@ -0,0 +1,67 @@ +#include <cmath> + +#include <mln/core/image_if_value.hh> +#include <mln/core/inplace.hh> +#include <mln/core/w_window2d_int.hh> +#include <mln/display/show.hh> +#include <mln/io/ppm/save.hh> +#include <mln/display/save_and_show.hh> +#include <mln/level/fill.hh> +#include <mln/math/round.hh> + +#include "../color/my_cmy.hh" + +#ifndef MLN_CMY_BLUE_HH +# define MLN_CMY_BLUE_HH + +namespace mln +{ + + + namespace fun + { + + namespace v2v + { + template <typename T_rgb> + struct f_blue_cmy_ : public Function_v2v< f_blue_cmy_<T_rgb> > + { + typedef T_rgb result; + + template <typename T_cmy> + T_rgb operator()(const T_cmy& cmy) const + { + typedef typename T_rgb::blue_t blue_t; + + static math::round<blue_t> to_b; + + static const float + sqrt3_3 = std::sqrt(3) / 3, + inv_sqrt6 = 1 / std::sqrt(6), + inv_sqrt2 = 1 / std::sqrt(2); + + float + h = cmy.hue() / 180.0 * 3.1415, + alpha = cmy.sat() * std::cos(h), + beta = cmy.sat() * std::sin(h); + + + blue_t b = to_b(1 - cmy.yellow()); + + T_rgb rgb(0, 0, b); + + return rgb; + } + }; + + typedef f_blue_cmy_<value::rgb8> f_cmy_blue_t; + + f_cmy_blue_t f_cmy_blue; + + } // end of namespace fun::v2v + + } // end of namespace fun + +} // end of namespace mln + +#endif // ! MLN_CMY_BLUE_HH Index: trunk/milena/sandbox/vigouroux/cmy/get_green.hh =================================================================== --- trunk/milena/sandbox/vigouroux/cmy/get_green.hh (revision 0) +++ trunk/milena/sandbox/vigouroux/cmy/get_green.hh (revision 1883) @@ -0,0 +1,56 @@ +#include <cmath> + +#include <mln/core/image_if_value.hh> +#include <mln/core/inplace.hh> +#include <mln/core/w_window2d_int.hh> +#include <mln/display/show.hh> +#include <mln/io/ppm/save.hh> +#include <mln/display/save_and_show.hh> +#include <mln/level/fill.hh> +#include <mln/math/round.hh> + +#include "../color/my_cmy.hh" + +#ifndef MLN_CMY_GREEN_HH +# define MLN_CMY_GREEN_HH + +namespace mln +{ + + + namespace fun + { + + namespace v2v + { + template <typename T_rgb> + struct f_green_cmy_ : public Function_v2v< f_green_cmy_<T_rgb> > + { + typedef T_rgb result; + + template <typename T_cmy> + T_rgb operator()(const T_cmy& cmy) const + { + typedef typename T_rgb::green_t green_t; + + static math::round<green_t> to_g; + + green_t g = to_g(1 - cmy.magenta()); + + T_rgb rgb(0, g, 0); + + return rgb; + } + }; + + typedef f_green_cmy_<value::rgb8> f_cmy_green_t; + + f_cmy_green_t f_cmy_green; + + } // end of namespace fun::v2v + + } // end of namespace fun + +} // end of namespace mln + +#endif // ! MLN_CMY_GREEN_HH Index: trunk/milena/sandbox/vigouroux/xyz/get_blue.hh =================================================================== --- trunk/milena/sandbox/vigouroux/xyz/get_blue.hh (revision 0) +++ trunk/milena/sandbox/vigouroux/xyz/get_blue.hh (revision 1883) @@ -0,0 +1,56 @@ +#include <cmath> + +#include <mln/core/image_if_value.hh> +#include <mln/core/inplace.hh> +#include <mln/core/w_window2d_int.hh> +#include <mln/display/show.hh> +#include <mln/io/ppm/save.hh> +#include <mln/display/save_and_show.hh> +#include <mln/level/fill.hh> +#include <mln/math/round.hh> + +#include "../color/my_xyz.hh" + +#ifndef MLN_XYZ_BLUE_HH +# define MLN_XYZ_BLUE_HH + +namespace mln +{ + + + namespace fun + { + + namespace v2v + { + template <typename T_rgb> + struct f_blue_xyz_ : public Function_v2v< f_blue_xyz_<T_rgb> > + { + typedef T_rgb result; + + template <typename T_xyz> + T_rgb operator()(const T_xyz& xyz) const + { + typedef typename T_rgb::blue_t blue_t; + + static math::round<blue_t> to_b; + + blue_t b = to_b(0.005 * xyz.x() - 0.014 * xyz.y() + 1.01 * xyz.z()); + + T_rgb rgb(0, 0, b); + + return rgb; + } + }; + + typedef f_blue_xyz_<value::rgb8> f_xyz_blue_t; + + f_xyz_blue_t f_xyz_blue; + + } // end of namespace fun::v2v + + } // end of namespace fun + +} // end of namespace mln + +#endif // ! MLN_XYZ_BLUE_HH Index: trunk/milena/sandbox/vigouroux/xyz/get_green.hh =================================================================== --- trunk/milena/sandbox/vigouroux/xyz/get_green.hh (revision 0) +++ trunk/milena/sandbox/vigouroux/xyz/get_green.hh (revision 1883) @@ -0,0 +1,56 @@ +#include <cmath> + +#include <mln/core/image_if_value.hh> +#include <mln/core/inplace.hh> +#include <mln/core/w_window2d_int.hh> +#include <mln/display/show.hh> +#include <mln/io/ppm/save.hh> +#include <mln/display/save_and_show.hh> +#include <mln/level/fill.hh> +#include <mln/math/round.hh> + +#include "../color/my_xyz.hh" + +#ifndef MLN_XYZ_GREEN_HH +# define MLN_XYZ_GREEN_HH + +namespace mln +{ + + + namespace fun + { + + namespace v2v + { + template <typename T_rgb> + struct f_green_xyz_ : public Function_v2v< f_green_xyz_<T_rgb> > + { + typedef T_rgb result; + + template <typename T_xyz> + T_rgb operator()(const T_xyz& xyz) const + { + typedef typename T_rgb::green_t green_t; + + static math::round<green_t> to_g; + + green_t g = to_g(-0.515 * xyz.x() + 1.425 * xyz.y() + 0.089 * xyz.z()); + + T_rgb rgb(0, g, 0); + + return rgb; + } + }; + + typedef f_green_xyz_<value::rgb8> f_xyz_green_t; + + f_xyz_green_t f_xyz_green; + + } // end of namespace fun::v2v + + } // end of namespace fun + +} // end of namespace mln + +#endif // ! MLN_XYZ_GREEN_HH Index: trunk/milena/sandbox/vigouroux/yiq/get_blue.hh =================================================================== --- trunk/milena/sandbox/vigouroux/yiq/get_blue.hh (revision 0) +++ trunk/milena/sandbox/vigouroux/yiq/get_blue.hh (revision 1883) @@ -0,0 +1,56 @@ +#include <cmath> + +#include <mln/core/image_if_value.hh> +#include <mln/core/inplace.hh> +#include <mln/core/w_window2d_int.hh> +#include <mln/display/show.hh> +#include <mln/io/ppm/save.hh> +#include <mln/display/save_and_show.hh> +#include <mln/level/fill.hh> +#include <mln/math/round.hh> + +#include "../color/my_yiq.hh" + +#ifndef MLN_YIQ_BLUE_HH +# define MLN_YIQ_BLUE_HH + +namespace mln +{ + + + namespace fun + { + + namespace v2v + { + template <typename T_rgb> + struct f_blue_yiq_ : public Function_v2v< f_blue_yiq_<T_rgb> > + { + typedef T_rgb result; + + template <typename T_yiq> + T_rgb operator()(const T_yiq& yiq) const + { + typedef typename T_rgb::blue_t blue_t; + + static math::round<blue_t> to_b; + + blue_t b = to_b(1.186 * yiq.y() - 1.2620 * yiq.i() + 1.8795 * yiq.q()); + + T_rgb rgb(0, 0, b); + + return rgb; + } + }; + + typedef f_blue_yiq_<value::rgb8> f_yiq_blue_t; + + f_yiq_blue_t f_yiq_blue; + + } // end of namespace fun::v2v + + } // end of namespace fun + +} // end of namespace mln + +#endif // ! MLN_YIQ_BLUE_HH Index: trunk/milena/sandbox/vigouroux/yiq/get_green.hh =================================================================== --- trunk/milena/sandbox/vigouroux/yiq/get_green.hh (revision 0) +++ trunk/milena/sandbox/vigouroux/yiq/get_green.hh (revision 1883) @@ -0,0 +1,55 @@ +#include <cmath> + +#include <mln/core/image_if_value.hh> +#include <mln/core/inplace.hh> +#include <mln/core/w_window2d_int.hh> +#include <mln/display/show.hh> +#include <mln/io/ppm/save.hh> +#include <mln/display/save_and_show.hh> +#include <mln/level/fill.hh> +#include <mln/math/round.hh> + +#include "../color/my_yiq.hh" + +#ifndef MLN_YIQ_GREEN_HH +# define MLN_YIQ_GREEN_HH + +namespace mln +{ + + namespace fun + { + + namespace v2v + { + template <typename T_rgb> + struct f_green_yiq_ : public Function_v2v< f_green_yiq_<T_rgb> > + { + typedef T_rgb result; + + template <typename T_yiq> + T_rgb operator()(const T_yiq& yiq) const + { + typedef typename T_rgb::green_t green_t; + + static math::round<green_t> to_g; + + green_t g = to_g(1.026 * yiq.y() - 0.2718 * yiq.i() - 0.1458 * yiq.q()); + + T_rgb rgb(0, g, 0); + + return rgb; + } + }; + + typedef f_green_yiq_<value::rgb8> f_yiq_green_t; + + f_yiq_green_t f_yiq_green; + + } // end of namespace fun::v2v + + } // end of namespace fun + +} // end of namespace mln + +#endif // ! MLN_YIQ_GREEN_HH

1 0

1882: Address memory leaks in graphs.
by Roland Levillain 22 Apr '08

22 Apr '08

https://svn.lrde.epita.fr/svn/oln/trunk/milena I need to check whether we could get rid of all those dynamic allocations. I think so, but I'm unsure. Index: ChangeLog from Roland Levillain <roland(a)lrde.epita.fr> Address memory leaks in graphs. * mln/util/internal/graph_base.hh (mln::util::internal::graph_base<N, E>::self_t): New typedef. (mln::util::internal::graph_base<N, E>::nodes_t) (mln::util::internal::graph_base<N, E>::edges_t) (mln::util::internal::graph_base<N, E>::edges_set_t): Help the compiler find types util::node and util::egde. (mln::util::internal::graph_base<N, E>::graph_base(const self_t&)): New copy ctor. (mln::util::internal::graph_base<N, E>::operator=(const self_t&)): New assignment operator. (mln::util::internal::graph_base<N, E>::~graph_base): Remove dynamically allocated data. graph_base.hh | 80 ++++++++++++++++++++++++++++++++++++++++++++++++++-------- 1 file changed, 69 insertions(+), 11 deletions(-) Index: mln/util/internal/graph_base.hh --- mln/util/internal/graph_base.hh (revision 1881) +++ mln/util/internal/graph_base.hh (working copy) @@ -151,22 +151,26 @@ template<typename N, typename E> class graph_base { + typedef graph_base<N, E> self_t; + public: /* FIXME: Do we really want handle nodes and edges through pointers? In my (Roland) opinion, this is just a drawback, here. */ /// The type of the set of nodes. - typedef std::vector< node<N>* > nodes_t; + typedef std::vector< util::node<N>* > nodes_t; /// The type of the set of edges. - typedef std::vector< edge<E>* > edges_t; + typedef std::vector< util::edge<E>* > edges_t; /// A set to test the presence of a given edge. - typedef std::set< edge<E>* > edges_set_t; - + typedef std::set< util::edge<E>* > edges_set_t; - /// Constructor. + /// Construction, assignments and destruction. + /// \{ graph_base(); - /// Destructor. + graph_base(const self_t& rhs); + self_t& operator=(const self_t& rhs); ~graph_base(); + /// \} /// Return the node whose id is \a n. /// \{ @@ -243,9 +247,9 @@ namespace internal { - /*----------------. - | Ctor and dtor. | - `----------------*/ + /*--------------------------------------------. + | Construction, assignments and destruction. | + `--------------------------------------------*/ template<typename N, typename E> inline @@ -256,10 +260,64 @@ template<typename N, typename E> inline + graph_base<N, E>::graph_base(const graph_base<N, E>& rhs) + : nodes_(), edges_(), edges_set_() + { + nodes_.reserve(rhs.nodes_.size()); + edges_.reserve(rhs.edges_.size()); + for (typename nodes_t::const_iterator n = rhs.nodes_.begin(); + n != rhs.nodes_.end(); ++n) + nodes_.push_back(new util::node<N>(**n)); + for (typename edges_t::const_iterator e = rhs.edges_.begin(); + e != rhs.edges_.end(); ++e) + edges_.push_back(new util::edge<E>(**e)); + std::copy(edges_.begin(), edges_.end(), + std::insert_iterator<edges_set_t>(edges_set_, + edges_set_.begin())); + } + + template<typename N, typename E> + inline + graph_base<N, E>& + graph_base<N, E>::operator=(const graph_base<N, E>& rhs) + { + if (this != &rhs) + { + /// Free previous nodes and edges. + for (typename nodes_t::iterator n = nodes_.begin(); + n != nodes_.end(); ++n) + delete *n; + for (typename edges_t::iterator e = edges_.begin(); + e != edges_.end(); ++e) + delete *e; + edges_set_.clear(); + /// Assign values from RHS. + nodes_.reserve(rhs.nodes_.size()); + edges_.reserve(rhs.edges_.size()); + for (typename nodes_t::const_iterator n = rhs.nodes_.begin(); + n != rhs.nodes_.end(); ++n) + nodes_.push_back(new util::node<N>(**n)); + for (typename edges_t::const_iterator e = rhs.edges_.begin(); + e != rhs.edges_.end(); ++e) + edges_.push_back(new util::edge<E>(**e)); + std::copy(edges_.begin(), edges_.end(), + std::insert_iterator<edges_set_t>(edges_set_, + edges_set_.begin())); + } + return *this; + } + + template<typename N, typename E> + inline graph_base<N, E>::~graph_base() { - // FIXME: Delete data dynamically allocated in nodes_ and - // edges_. + for (typename nodes_t::iterator n = nodes_.begin(); n != nodes_.end(); + ++n) + delete *n; + for (typename edges_t::iterator e = edges_.begin(); e != edges_.end(); + ++e) + delete *e; + edges_set_.clear(); } /*------------.

1 0

1866: Add red getter.
by Caroline Vigouroux 21 Apr '08

21 Apr '08

https://svn.lrde.epita.fr/svn/oln/trunk/milena Index: ChangeLog from Caroline Vigouroux <vigouroux(a)lrde.epita.fr> Add red getter. * cmy/fun.hh, hsi/fun.hh, yiq/fun.hh, yuv/fun.hh : New red getter. * cmy/my_cmy.hh, hsi/my_hsi.hh, yiq/my_yiq.hh, yuv/my_yuv.hh: Added inheritance from value. * cmy/rgb_to_cmy.hh, hsi/rgb_to_hsi.hh, yiq/rgb_to_yiq.hh, yuv/rgb_to_yuv.hh: Added inheritance from function_v2v. * cmy/test.cc, yiq/test.cc, yuv/test.cc : New test. * cmy/testfun.cc, yiq/testfun.cc, yuv/testfun.cc: New test. * cmy, hsi, yiq, yuv: New folder. * color/is_HSI.cc: change. * color/my_hsi.hh: change. * color/rgb_to_hsi.hh: change. * function.hh: New getter. * testfun.cc: New test.

3 2

1880: Sandbox: ICP: Cleanup directory. Fix comments.
by Ugo Jardonnet 21 Apr '08

21 Apr '08

https://svn.lrde.epita.fr/svn/oln/trunk/milena Index: ChangeLog from Ugo Jardonnet <ugo.jardonnet(a)lrde.epita.fr> Sandbox: ICP: Cleanup directory. Fix comments. * sandbox/jardonnet/registration/cross_cov.hh: New: to be filled. * sandbox/jardonnet/registration/icp_lazy.hh: Remove. * sandbox/jardonnet/registration/icp_subsampled.hh: Remove. * sandbox/jardonnet/registration/icp.hh: Fix comments. cross_cov.hh | 18 ++++++++++++++++++ icp.hh | 7 ++++--- 2 files changed, 22 insertions(+), 3 deletions(-) Index: sandbox/jardonnet/registration/cross_cov.hh --- sandbox/jardonnet/registration/cross_cov.hh (revision 0) +++ sandbox/jardonnet/registration/cross_cov.hh (revision 0) @@ -0,0 +1,18 @@ +#ifndef MLN_ACCU_CROSS_COV_HH_HH +# define MLN_ACCU_CROSS_COV_HH_HH + + +namespace mln +{ + + namespace accu + { + + + + } + +} + + +#endif // ! MLN_ACCU_CROSS_COV_HH_HH Index: sandbox/jardonnet/registration/icp.hh --- sandbox/jardonnet/registration/icp.hh (revision 1879) +++ sandbox/jardonnet/registration/icp.hh (working copy) @@ -97,7 +97,7 @@ float err = 100; //float err_bis; - p_array Ck(C); //FIXME: Xk copy C + p_array Ck(C); algebra::vec<P::dim,float> mu_C = center(C, c_length), mu_Xk; @@ -134,8 +134,8 @@ #ifndef NDEBUG { + /* using namespace std; - //FIXME: Should use Ck box but Ck.bbox() is not correct for c_length image2d<bool> img(box2d(500,800), 0); for (size_t i = 0; i < c_length; i++) @@ -145,8 +145,9 @@ img(p) = true; } - //FIXME: Good but put point qfter c_length + //FIXME: Good but put point after c_length //image2d<bool> img = convert::to_image2d(Ck); + */ stringstream oss; static int pimp = 0; oss << "i_" << pimp++ << ".pbm";

1 0

1879: Clean up the line piter code.
by Nicolas Ballas 21 Apr '08

21 Apr '08

https://svn.lrde.epita.fr/svn/oln/trunk/milena Index: ChangeLog from Nicolas Ballas <ballas(a)lrde.epita.fr> Clean up the line piter code. * tests/line_piter.cc: Update the test. * mln/core/line_piter.hh: Clean up. mln/core/line_piter.hh | 35 ++++++++++++++++---------------- tests/line_piter.cc | 52 +++++++++++++++++++++++++++++++++++++++++++------ 2 files changed, 63 insertions(+), 24 deletions(-) Index: tests/line_piter.cc --- tests/line_piter.cc (revision 1878) +++ tests/line_piter.cc (working copy) @@ -30,22 +30,62 @@ * \brief Tests on mln::line_piter. */ +//FIXME: replace by the necessary include +#include <mln/core/image1d.hh> #include <mln/core/image2d.hh> +#include <mln/core/image3d.hh> #include <mln/core/line_piter.hh> int main() { using namespace mln; - box2d b(make::point2d(1,2), make::point2d(5,8)); const unsigned border = 2; - image2d<int> f(b, border); - image2d<int>::line_piter p(f.domain()); + /// Test with image 1d + { + box1d b1(make::point1d(5), make::point1d(42)); + image1d<int> f1(b1, border); + image1d<int>::line_piter p1(f1.domain()); + for_all(p1) + { + mln_assertion(p1[0] == 5); + std::cout << p1 <<std::endl; + } + } + + + /// Test with image 2d + { + box2d b2(make::point2d(1,2), make::point2d(5,8)); + image2d<int> f2(b2, border); + + image2d<int>::line_piter p2(f2.domain()); int i = 1; - for_all(p) + for_all(p2) { - mln_assertion(p[1] == 0 && p[0] == i++); - std::cout < f3(b3, border); + + image3d<int>::line_piter p3(f3.domain()); + int i = 1; + int j = 2; + for_all(p3) + { + mln_assertion( p3[0] == i && p3[1] == j && p3[2] == 3); + std::cout << p3 << std::endl; + if (i++ == 5) + i = 1; + if (j++ == 8) + j = 2; + } + } + } Index: mln/core/line_piter.hh --- mln/core/line_piter.hh (revision 1878) +++ mln/core/line_piter.hh (working copy) @@ -46,7 +46,8 @@ * The parameter \c P is the type of points. */ template <typename P> - class line_piter_ : public internal::point_iterator_base_< P, line_piter_ > + class line_piter_ : + public internal::point_iterator_base_< P, line_piter_ > { typedef line_piter_ self_; typedef internal::point_iterator_base_< P, self_ > super_; @@ -84,7 +85,8 @@ private: const box_& b_; - P p_, nop_; + P p_; + bool is_valid_; }; @@ -98,14 +100,6 @@ line_piter_::line_piter_(const box_& b) : b_(b) { - nop_ = b_.pmax(); - if (dim == 1) - ++nop_[0]; - else - { - nop_[0] = 0; - ++nop_[1]; - } invalidate(); } @@ -113,7 +107,7 @@ inline line_piter_::operator P() const { - return p_; + return to_point(); } template <typename P> @@ -121,6 +115,7 @@ const P& line_piter_::to_point() const { + mln_precondition(is_valid()); return p_; } @@ -129,8 +124,10 @@ mln_coord(P) line_piter_::operator[](unsigned i) const { + mln_precondition(is_valid()); + mln_precondition(i < dim); + mln_invariant(p_[dim - 1] == b_.pmin()[dim - 1]); - assert(i < dim); return p_[i]; } @@ -139,7 +136,7 @@ bool line_piter_::is_valid() const { - return p_ != nop_; + return is_valid_; } template <typename P> @@ -147,7 +144,7 @@ void line_piter_::invalidate() { - p_ = nop_; + is_valid_= false; } template <typename P> @@ -156,6 +153,7 @@ line_piter_::start() { p_ = b_.pmin(); + is_valid_ = true; } template <typename P> @@ -163,17 +161,18 @@ void line_piter_::next_() { + mln_precondition(is_valid()); + + // Do we want this run for image in 3d? for (int c = dim - 2; c >= 0; --c) { if (p_[c] != b_.pmax()[c]) - { ++p_[c]; - break; - } + else p_[c] = b_.pmin()[c]; } if (p_ == b_.pmin()) - p_ = nop_; + invalidate(); }

1 0

1877: Continue documentation.
by Nicolas Ballas 21 Apr '08

21 Apr '08

https://svn.lrde.epita.fr/svn/oln/trunk/milena Index: ChangeLog from Nicolas Ballas <ballas(a)lrde.epita.fr> Continue documentation. * sandbox/ballas/doc/image_tours.txt: Add run and lut image definition. * sandbox/ballas/doc/draft.txt: Update. draft.txt | 11 - image_tours.txt | 368 +++++++++++++++++++++++++++++++++++++++++++++++++++----- 2 files changed, 345 insertions(+), 34 deletions(-) Index: sandbox/ballas/doc/image_tours.txt --- sandbox/ballas/doc/image_tours.txt (revision 1877) +++ sandbox/ballas/doc/image_tours.txt (working copy) @@ -282,11 +282,6 @@ io = read_only speed = fast ---> properties related to values - -kind =?? -quant =?? -value = fixme --> properties related to the pset @@ -308,40 +303,188 @@ All the run based encoded images have their definition domains encoded by runs. These images types are not morpher types since these do not lie on another -image type.A run is a "continuous" (note this is wrong, cf graph index) set of -sites.It is define by a site start, and a length. All the run based encoded -image are templated by P, T where P is a site type and T a value type. +image type. +All the run based encoded images are templated by P, T where P is a site type +and T a value type. Note: type one shot (const)!!! Do we store the the null value in the rle encoding. -(Do we compress all the images values, or only the image objects...) +( <=> Do we compress all the images values, or only the image objects...) Is there any restriction on P and T? -How the properties are setted and to which values? +*** Notation used: + (a, b) represents a pair composed by two elements.. + {a, b, c...} represents a list of elements. + +*** What is a run? + +**** Definition + +// FIXME choose a better word than continuous. +A run is a "continuous" succession of sites. +All the sites encoded in a same run have the same value in the corresponding +image. + +It is defined by a site "start", and a length. + +ex: + start length of + site the run + ((1, 2), 6 ) + + + see the image: + + 1 - 1 - 2 + | | | + 2 - 2 - 2 + | | | + 3 - 3 - 3 + +Its corresponding runs are: +{ + ( (0, 0), 2 ), + ( (0, 2), 1 ), + ( (1, 0), 3 ), + ( (2, 0), 3 ), +} + +Note: there is two different runs for the value 2: + ( (0, 2), 1 ), + ( (1, 0), 3 ). + +Indeed the points (0, 2) and (1, 0) are not "continuous". + + + +**** Difference between data stored in a linear way and runs. + +A run doesn't represent only a continuous memory zone. +A run has also a localization aspect. +From a run, we can get all the points which compose it. + +For instance, look at the following run: + + + i_run: 0 1 2 3 + +-+-+-+-+ + (0, 4) |1|1|1|1| <=> ( (0, 4), 4 ) + +-+-+-+-+ + +The points composing this run are: +(0, 4), (0, 5), (0, 6), (0, 7) + +This property is really important to guarantee the interoperability +between the different image types. + +**** PieceWise property + +The run is templated by a site type. +But does we have any restriction on the type of site? + +The answer seems to be yes, the run must have a localization aspect. +To allow this localization, we must be able to convert a p_run into its +corresponding sites. +So we must be able to convert a site and i_run index to another site. + +ex: + +(0, 4) + 3 give us the site (0, 7). + +It has two consequences: +- a site must be convertible into a vector of coordinates +- We must a know to which coordinate we add the i_run index to compute another + site. We will choose the coordinate which vary the most. + +This lead us to the PieceWise property: + The site can be represented by a vector of coordinates, and this vector has a +coordinate which vary more than the other. (And we have an access to these +coordinates). + -*** Criteria needed by images to be encoded in runs +**** Why a run has to be a "continuous" succession of sites? -Can we compress all the image types or only the piece wise image type -(cf the on_the_same_line in the encode algorithm). +We can imagine that a run is a succession of noncontinuous sites. +For instance look at the following image: -Currently, *encode function just work with image based on a **Point** set. -cf: -for (unsigned n = 0; same_line && n < dim - 1; ++n) - same_line = (p1[n] == p2[n]); + 1 - 1 - 2 + | | | + 2 - 2 - 2 This image is based on a grid which has its deltaX equal to 10 + | | | and its deltaY equal to 30. + 1 - 1 - 1 -Problem generalization: - A p_run take a Site as a parameter. - a p_run must be able to be casted into the Site (actually, const Site). - The only information that we have in the p_run is a len (integer). - So we must be able to refind all the site in the run from the site start, -and a addition with an integer. +So the points localized on the grid are: - How do we name this property? + (0, 0) - (10, 0) - (20, 0) + | | | + (0, 30) - (10, 30) - (20, 30) + | | | + (0, 60) - (10, 60) - (20, 60) +The corresponding encoded image with "noncontinuous" runs will be: + { ((a,1), 2), ((b,2), 1), ((c,2), 3), ((c,3), 3) } + +with a = (0, 0), b = (20, 0), c = (0, 30), d = (0, 60). + +Another representation of the encoded image is: + + i_run: 0 1 2 + +-+-+ + (0, 0) |1|1| + +-+-+ + (20, 0) |2| + +-+-+-+ + (0, 30) |2|2|2| + +-+-+-+ + (0, 60) |1|1|1| + +-+-+-+ + +Here, we loose the localization aspect of the psite. +Indeed a psite (p_run) is represented by a site (pstart), and an integer +(i_run). With these information, we can access to all the value in the encoded +image. However we can not convert a psite (p_run) into a site (point2d). +For instance: + + psite -> site + (pstart: (0, 60) i_run: 2) -> (2, 60) + +However, the point (2, 60) doesn't belong to the image pset. +The expected result here is (20, 60). +This problem is an outcome of the holes present in the original image grid. +So, this is an outcome of the "noncontinuous" aspect of the run. + +This approach implies one direct drawback: we loose the interoperability +between the encoded image type and other image types (We cannot convert a +p_run into the corresponding site). +So, a run has to be a continuous succession set of points. + +Another solution is to store the deltaX of the grid inside the psite. +This way, we have enough information to convert a p_run into a point2d. +But encoding a graph image will not work either, even with the second +solution. Indeed, nothing assure us that the site on a graph are "continuous". + +Do we need a property for that?. + +Another problem with "noncontinuous" run is the index access ambiguity. +If the image provide an index access, the point represented by the indexes i,j +is not necessarily the same point represented by the indexes i,j in the +encoded image. + + +**** Which kind of image can be encoded? / Conclusion + +We need two condition to encode an image type into a run encoded types. +First the image psite type must be piece wise. +Furthermore, the image must be based on a (regular) grid without any "holes". + +All image{1, 2, 3}d types can be encoded. +Image based on a lut can be encoded too. +Function image with a regular grid can be encoded. +And morphers types based on a regular grid can be encoded too. *** RLE Image @@ -353,7 +496,6 @@ **** Associated types: value = T - site = P psite = runs_psite pset = p_runs_ @@ -384,8 +526,32 @@ support = depend on P // The property setted in the milena code is wrong + +**** Example: + +Consider the following image on regular grid. + + 1 - 1 - 2 + | | | + 2 - 2 - 2 + | | | + 1 - 1 - 1 + +The encoded image is: + +{ + psite value + ( ((0, 0), 2), 1 ), + ( ((0, 2), 1), 2 ), + ( ((1, 0), 3), 2 ), + ( ((2, 0), 3), 1 ), +} + + *** Compact RLE +FIXME + *** Sparse Image A RLE image can be defined as the following: @@ -396,7 +562,6 @@ **** Associated types: value = T - site = P psite = runs_psite pset = p_runs_ @@ -405,9 +570,157 @@ Same properties than the RLE Image type. +**** Examples: + +Consider the following images: + +The empty case denote there is no data at this coordinate. + + 1 - 2 - 3 - - - + | | | | | | + - - - 2 - 2 - 2 + | | | | | | + - - - 4 - 5 - 8 + | | | | | | + - - - - - + + +Its sparse encoding is: + +{ psite values + ( ((0, 0), 3), {1, 2, 3}), + ( ((1, 3), 3), {2, 2, 2}), + ( ((2, 3), 3), {4, 5, 6}), +} + + *** Value encoded image +**** Definition: + +A value image is an image which associate a value to its corresponding psite. +So, we can easily get all the psites/site which have their (in O(1) complexity) + +{ + (v, {runs}) +} + +**** Associate types: + +value = T +site = P +psite = runs_psite +pset = p_runs_ + +**** Properties: + Same as rle image. + +**** Example: + + +See + 1 - 1 - 1 - - - + | | | | | | + - - - 2 - 2 - 2 + | | | | | | + - - - 2 - 2 - 2 + | | | | | | + 3 - 3 - 3 - 4 - 4 - 4 + +The corresponding encoded image is: + + +{ + (1, {((0, 0), 3)} ), + + (2, {((1, 3), 3), + ((2, 3), 3)} ), + + (3, {((3, 0), 3)} ), + + (4, {((3, 3), 3)} ) +} + + +*** Image based on Lut + +**** Definition + +An image based on a lut is primitive image type. +This kind of image use a look up table to retrieve a value +associated to an image site. + +It can be defines as followed: + + ({values}, {lut_values}) + + +FIXME: How do we deal with the dimensions of the images? + + + +**** Associated type + +site=P +psite=P +value=V +pset=pset + + +**** Property: + +--> global properties + +category = primary +border = none +neighb: none +data = stored +io = read_write +speed = fast + +--> properties related to values + +kind = +quant =small +value = V + +--> properties related to the pset + +access = browsing // Why the access property is set to browsing? +space = pset::space +size = regular +support = pset::supper + + +**** Example: + +Consider this image type: + +{ data = + +-----------+ + | 0 2 1 0 2 | + | 0 0 3 2 1 | + | 2 1 2 2 0 | + +-----------+; + lut = + +---+---------------+ + | 0 | (255, 0, 0) | red (r) + | 1 | (127,127,127) | medium grey (m) + | 2 | ( 0, 0,255) | blue (b) + | 3 | (127,127,127) | medium grey (m) again + +---+---------------+ +} + +This image is defined with a look-up table; its external +representation actually is: + + +-----------+ + | r b m r b | + | r r m b m | + | b m b b r | + +-----------+ + ** Graph Image @@ -415,9 +728,6 @@ **** Connectivity based on a graph. - -** Image based on Lut - ** Morpher (Derived Image) Mopher are Image types which transform an Image type into a new type. So, they Index: sandbox/ballas/doc/draft.txt --- sandbox/ballas/doc/draft.txt (revision 1877) +++ sandbox/ballas/doc/draft.txt (working copy) @@ -246,9 +246,6 @@ property of the grid are useless. - - - * Property that we need? ** has(p) @@ -299,7 +296,7 @@ This function can be specialize for image/pset types that provide an access time in O(1). -In this case a method nsite will be present in the pset inteface: +In this case a method nsite will be present in the pset interface: return ima.pset().nsites(); So we need a pset property to define the complexity of accessing to the number @@ -345,7 +342,7 @@ regular grid). An gbox is composed by point2d. If the image is based on a grid, it can return a ibox. We can access to the image values through a couple (i, j). But each couple (i, j) doesn't represent -necessary a point2d (anystrope, unaligned grid...). +necessary a point2d (anisotropic, unaligned grid...). If the image localization is space, we can return a xbox (box which is not based on a grid). @@ -367,3 +364,7 @@ idea: boxed : true, false + +** pieceWise property + +see the image tours files.

1 0

milena r1877: Test a simple fllt
by Matthieu Garrigues 20 Apr '08

20 Apr '08

URL: https://svn.lrde.epita.fr/svn/oln/trunk/milena ChangeLog: 2008-04-20 Matthieu Garrigues <garrigues(a)lrde.epita.fr> Test a simple fllt. * sandbox/garrigues/fllt/fllt_simple.cc: Start to construct shapes by browsing level lines in interpixels. * sandbox/garrigues/fllt/fllt_simple.svg.1.cc: New, just browse the c4 connected component of an image. * sandbox/garrigues/fllt/fllt_simple.svg.2.cc: New, just browse the c6 connected component of an image. * sandbox/garrigues/fllt/fllt_simple.svg.3.cc: New, build a tree where a connected component is parent of the shapes contained in its holes. It give the same representation than fllt only on simple images. * sandbox/garrigues/fllt/fllt_theo.cc: Old work, a faster version is in sandbox/geraud/fllt.cc --- fllt_simple.cc | 349 ++++++++++++++++++++++++++--- fllt_simple.svg.1.cc | 325 +++++++++++++++++++++++++++ fllt_simple.svg.2.cc | 349 +++++++++++++++++++++++++++++ fllt_simple.svg.3.cc | 612 +++++++++++++++++++++++++++++++++++++++++++++++++++ fllt_theo.cc | 186 +++++++++++++-- 5 files changed, 1764 insertions(+), 57 deletions(-) Index: trunk/milena/sandbox/garrigues/fllt/fllt_simple.svg.1.cc =================================================================== --- trunk/milena/sandbox/garrigues/fllt/fllt_simple.svg.1.cc (revision 0) +++ trunk/milena/sandbox/garrigues/fllt/fllt_simple.svg.1.cc (revision 1877) @@ -0,0 +1,325 @@ +// Copyright (C) 2008 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. + +#include <iomanip> +#include <iostream> +#include <sstream> + +#include <mln/core/image2d.hh> +#include <mln/core/sub_image.hh> +#include <mln/core/neighb2d.hh> +#include <mln/core/p_array.hh> +#include <mln/core/clone.hh> + +#include <mln/value/int_u8.hh> + +#include <mln/io/pgm/load.hh> +#include <mln/io/pgm/save.hh> + +#include <mln/level/fill.hh> +#include <mln/debug/println.hh> +#include <mln/labeling/regional_minima.hh> +#include <mln/accu/bbox.hh> +#include <mln/io/pgm/save.hh> + + +#include <mln/core/cast_image.hh> + +namespace mln +{ + // Un autre version recursive de la fllt. + + // Idee : + // Parcourir l'image en pratant d'un coin de preference, + // le parcour des pixels se fait dans un ordre conexe. + // + + /* + + fonction fllt_rec(racine R, domaine D, marques M, conexite C) + { + pour tout les points du domaine non marquees + recuperer la composante conexe A (en conexite C) qui inclut ce point : + Ceci est fait avec la methode de grossissement de region + pour avoir acces a la bordure externe et donc aux trous + de la composante. + + Cette composante sera fille de R dans l'arbre d'inclusion. + + Marquer les points de A (Peut etre fait en meme temps que la + construction de A) + + Pour chaque trous T de A : + appel recursif : fllt_rec(A, T.domaine(), marques, inv(C)) + T.domaine() sera calculer en recuperant la composante connexe + de la bordure de A lui correspondant (On recupere facilement + les segments horizontaux qui le composent -> parcour ok). + + } + inv(c4) = c8 + inv(c8) = c4 + + + Autre version qui Marche sur les images hexagonales (Plus rapide et plus simple) + car il y a plus le probleme du theoreme de jordan non verifie. + FIXME: Est-ce que rendre l'image hexagonale altere vraiment le resultat? + + pour tout les points du domaine non marquees + recuperer la composante conexe A qui inclut ce point : + Ceci est fait avec la methode de grossissement de region + pour avoir acces a la bordure externe et donc aux trous + de la composante. + + Marquer les points de A (Peut etre fait en meme temps que la + construction de A) + + Marquer les extremites des trou de A. + + Si un point de A est l'extremite d'un trou, + alors on a facilement le pere de A (la forme qui inclue A). + Sinon + C'est qu'il y a une composante connexe adjacente qui + a deja ete construite, et qui a donc deja un pere, qui + est aussi celui de A. + + continuer jusqu'a avoir marquer tout les points + + */ + + namespace my + { + + + void save_u(const image2d<value::int_u8>& u, + const image2d<unsigned char>& is, + box2d R_box) + { + static int id = 0; + std::stringstream filename; + filename << "fllt_u_" << std::setw(5) << std::setfill('0') + << std::right << id++ << ".ppm"; + + image2d<value::int_u8> out = clone(u); + const unsigned in_R = 255; + + mln_piter_(box2d) p(R_box); + for_all(p) + if (is(p) == in_R) + out(p) = 255; + + io::pgm::save(out, filename.str()); + } + + void swap_arrays(p_array<point2d>*& A, + p_array<point2d>*& N) + { + p_array<point2d>* tmp = A; + A = N; + N = tmp; + } + + template <typename I, typename Nbh> + void fllt(const Image& input_, const Neighborhood<Nbh>& nbh_) + { + const I& input = exact(input_); + const Nbh& nbh = exact(nbh_); + + // Variables. + I u = mln::clone(input); + mln_point(I) x0; + mln_value(I) g, gN; + image2d<unsigned char> is(input.domain()); + image2d<bool> tagged(input.domain()); + const unsigned in_R = 255, in_N = 2, in_O = 0; + + typedef p_array<mln_point(I)> arr_t; + arr_t* A = new arr_t(); + arr_t* N = new arr_t(); + + accu::bbox<mln_point(I)> R_box, N_box; + + unsigned n_step_1 = 0, n_step_3 = 0; + + level::fill(tagged, false); + mln_piter(I) min(input.domain()); + min.start(); + // Step 1. + step_1: + { +#ifdef FLLTDEBUG + std::cout << "Step 1" << std::endl; +#endif + ++n_step_1; + for(; min.is_valid(); min.next()) + if (!tagged(min)) + break; + + if (!min.is_valid()) + goto end; + + x0 = min; + g = input(x0); + } + + // Step 2. + step_2: + { +#ifdef FLLTDEBUG + std::cout << "Step 2" << std::endl; +#endif + if (N_box.is_valid()) + level::fill(inplace(is | N_box.to_result()), in_O); + + N_box.init(); + R_box.init(); + A->clear(); + A->append(x0); + N->clear(); + } + + // Step 3. + step_3: + { + ++n_step_3; +#ifdef FLLTDEBUG + std::cout << "Step 3" << std::endl; +#endif + mln_piter(arr_t) a(*A); + mln_niter(Nbh) x(nbh, a); + + // Stop. + if (A->npoints() == 0) + goto end; + + // R <- R U A +#ifdef FLLTDEBUG + std::cout << "Add To R : "; +#endif + for_all(a) + { + tagged(a) = true; + is(a) = in_R; +#ifdef FLLTDEBUG + std::cout << a; +#endif + } +#ifdef FLLTDEBUG + std::cout << std::endl; +#endif + + +#ifdef FLLTDEBUG + std::cout << "points of A : " << A->npoints() << std::endl; +#endif + mln_assertion(A->npoints() > 0); + R_box.take(A->bbox()); + mln_assertion(R_box.is_valid()); + +#ifdef FLLTTRACE + save_u(u, is, R_box); +#endif + // N <- N U { x in nbh of A and not in R / input(x) == g} +#ifdef FLLTDEBUG + std::cout << "Add To N : "; +#endif + for_all(a) + for_all(x) + if (u.has(x) && is(x) == in_O && input(x) == g) + { + mln_assertion(!tagged(x)); + N_box.take(x); + is(x) = in_N; + N->append(x); +#ifdef FLLTDEBUG + std::cout << x; +#endif + } +#ifdef FLLTDEBUG + std::cout << std::endl; +#endif + +#ifdef FLLTDEBUG + std::cout << "g = " << g << std::endl; +#endif + + // Stop if N is empty. + if (N->npoints() == 0) + goto step_1; + else + { + swap_arrays(A, N); + N->clear(); + goto step_3; + } + } + + step_4: + { + // Follow N, find the holes, and browse it. + } + + end: + { + std::cout << n_step_1 << ' ' << n_step_3 << std::endl; + } + } + + } // end of namespace mln::my + +} // end of namespace mln + + +int main() +{ + using namespace mln; + using value::int_u8; + + image2d<int_u8> lena; + + io::pgm::load(lena, "../../../img/lena.pgm"); + + + // int_u8 vs[9][9] = { + + // { 2, 2, 2, 2, 2, 2, 2, 2, 2 }, + // { 2, 2, 2, 2, 2, 2, 2, 2, 2 }, + // { 2, 2, 2, 2, 2, 2, 2, 2, 2 }, + // { 2, 2, 2, 2, 2, 2, 2, 2, 2 }, + // { 2, 2, 2, 2, 2, 2, 2, 2, 2 }, + // { 2, 2, 2, 2, 2, 2, 2, 2, 2 }, + // { 2, 2, 2, 2, 2, 2, 2, 2, 2 }, + // { 2, 2, 2, 2, 2, 2, 2, 2, 2 }, + // { 2, 2, 2, 2, 2, 2, 2, 2, 2 }, + + // }; + + //image2d<int_u8> lena = make::image2d(vs); + + my::fllt(lena, c4()); + io::pgm::save(lena, "./out.pgm"); + +} Index: trunk/milena/sandbox/garrigues/fllt/fllt_simple.svg.3.cc =================================================================== --- trunk/milena/sandbox/garrigues/fllt/fllt_simple.svg.3.cc (revision 0) +++ trunk/milena/sandbox/garrigues/fllt/fllt_simple.svg.3.cc (revision 1877) @@ -0,0 +1,612 @@ +// Copyright (C) 2008 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. + +#include <iomanip> +#include <iostream> +#include <sstream> + +#include <mln/core/image2d.hh> +#include <mln/core/sub_image.hh> +#include <mln/core/neighb2d.hh> +#include <mln/core/p_array.hh> +#include <mln/core/clone.hh> + +#include <mln/value/int_u8.hh> + +#include <mln/io/pgm/load.hh> +#include <mln/io/pgm/save.hh> + +#include <mln/level/fill.hh> +#include <mln/level/compare.hh> +#include <mln/debug/println.hh> +#include <mln/labeling/regional_minima.hh> +#include <mln/accu/bbox.hh> +#include <mln/io/pgm/save.hh> + +#include <mln/util/tree.hh> +#include <mln/util/tree_to_image.hh> +#include <mln/util/branch_iter_ind.hh> + +#include <mln/core/cast_image.hh> +#include <mln/core/p_queue_fast.hh> + +namespace mln +{ + // Un autre version recursive de la fllt. + + // Idee : + // Parcourir l'image en pratant d'un coin de preference, + // le parcour des pixels se fait dans un ordre conexe. + // + + /* + + fonction fllt_rec(racine R, domaine D, marques M, conexite C) + { + pour tout les points du domaine non marquees + recuperer la composante conexe A (en conexite C) qui inclut ce point : + Ceci est fait avec la methode de grossissement de region + pour avoir acces a la bordure externe et donc aux trous + de la composante. + + Cette composante sera fille de R dans l'arbre d'inclusion. + + Marquer les points de A (Peut etre fait en meme temps que la + construction de A) + + Pour chaque trous T de A : + appel recursif : fllt_rec(A, T.domaine(), marques, inv(C)) + T.domaine() sera calculer en recuperant la composante connexe + de la bordure de A lui correspondant (On recupere facilement + les segments horizontaux qui le composent -> parcour ok). + + } + inv(c4) = c8 + inv(c8) = c4 + + + Autre version qui Marche sur les images hexagonales (Plus rapide et plus simple) + car il y a plus le probleme du theoreme de jordan non verifie. + FIXME: Est-ce que rendre l'image hexagonale altere vraiment le resultat? + + pour tout les points du domaine non marquees + recuperer la composante conexe A qui inclut ce point : + Ceci est fait avec la methode de grossissement de region + pour avoir acces a la bordure externe et donc aux trous + de la composante. + + Marquer les points de A (Peut etre fait en meme temps que la + construction de A) + + Marquer les extremites des trou de A. + + Si un point de A est l'extremite d'un trou, + alors on a facilement le pere de A (la forme qui inclue A). + Sinon + C'est qu'il y a une composante connexe adjacente qui + a deja ete construite, et qui a donc deja un pere, qui + est aussi celui de A. + + continuer jusqu'a avoir marquer tout les points + + Cette methode me marche que dans le cas ou les courbes de niveau corespondent + au formes car on creer les formes en parcourant les pixels. + + Le probleme peut etre resolu en grossissant la forme en passant sur les courbes + de niveaux qui se sitent entre les pixels. + */ + + namespace my + { + +# define fllt_tree(P, V) mln::util::tree< fllt_node_elt<P, V> > +# define fllt_node(P, V) mln::util::tree_node< fllt_node_elt<P, V> > +# define fllt_branch(P, V) mln::util::branch< fllt_node_elt<P, V> > +# define fllt_branch_iter_ind(P, V) mln::util::branch_iter_ind< fllt_node_elt<P, V> > + + + template <typename P, typename V> + struct fllt_node_elt + { + V value; + p_array points; + p_array holes; + /// Tell if his parent if brighter or not. Nb : if the parent + /// if brighter, the node come from the lower level set + bool brighter; + unsigned npoints; + + }; + + template <typename P, typename V> + void add_npoints_to(fllt_node(P, V)* node, unsigned npoints) + { + mln_assertion(node); + + node->elt().npoints += npoints; + if (node->parent()) + add_npoints_to(node->parent(), npoints); + } + + + template <typename R> + struct map_cell + { + R* border_of_hole_of; + R* old_border_of_hole_of; + R* belongs_to; + + map_cell() : border_of_hole_of(0), belongs_to(0) {} + + void restore_border() + { border_of_hole_of = old_border_of_hole_of; } + + void set_border_of_hole_of(R* b) + { + old_border_of_hole_of = border_of_hole_of; + border_of_hole_of = b; + } + }; + + + + template <typename P, typename V> + void + draw_tree(const image2d<V>& ima, + fllt_tree(P, V)& tree) + { + fllt_branch_iter_ind(P, V) p(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 + << " value = " << (*p).elt().value << std::endl + << " npoints = " << (*p).elt().npoints << std::endl + << std::endl; + + if ((*p).elt().points.npoints() > 0) + debug::println(ima | (*p).elt().points); + std::cout << std::endl; + } + } + + + template <typename P, typename V> + void + visualize_bounds(image2d<value::int_u8>& output, + fllt_tree(P, V)& tree, + unsigned limit) + { + fllt_branch_iter_ind(P, V) p(tree.main_branch()); + level::fill(output, 255); + for_all(p) + { + if ((*p).elt().npoints > limit) + { + mln_piter(p_array<point2d>) q((*p).elt().points); + for_all(q) + { + output(q) = 0; + } + } + } + } + + void save_u(const image2d<value::int_u8>& u, + const image2d<unsigned char>& is, + box2d R_box) + { + static int id = 0; + std::stringstream filename; + filename << "fllt_u_" << std::setw(5) << std::setfill('0') + << std::right << id++ << ".ppm"; + + image2d<value::int_u8> out = clone(u); + const unsigned in_R = 255; + + mln_piter_(box2d) p(R_box); + for_all(p) + if (is(p) == in_R) + out(p) = 255; + + io::pgm::save(out, filename.str()); + } + + void swap_arrays(p_array<point2d>*& A, + p_array<point2d>*& N) + { + p_array<point2d>* tmp = A; + A = N; + N = tmp; + } + + + template <typename N_t> + void clear_N(N_t& N) + { + for (unsigned i = 0; i < 256; ++i) + N[i]->clear(); + } + + template <typename I, typename CC> + void erase_exterior_border(I& map, const box2d& bbox, const CC& current_cc, const std::vector<dpoint2d> nbh[]) + { + typedef const std::vector<dpoint2d> arr_dp_t; + typedef std::vector<dpoint2d>::const_iterator arr_dp_t_it; + mln_piter(I) p(bbox); + for_all(p) + if (map(p).border_of_hole_of == current_cc) + { + //mln_assertion(map(p).belongs_to != current_cc); + break; + } + mln_assertion(map(p).belongs_to != current_cc); + p_queue_fast<mln_point(I)> qu; + map(p).restore_border(); + qu.push(p); +// std::cout << std::endl; + + while(!qu.is_empty()) + { + mln_point(I) a = qu.pop_front(); + //map(a).border_of_hole_of = 0; + arr_dp_t* n_dp = &nbh[abs(a[1] % 2 > 0)]; + +// unsigned i = 0; + for(arr_dp_t_it x = n_dp->begin(); x != n_dp->end(); x++) + { + mln_point(I) n = mln_point(I)(a) + mln_dpoint(I)(*x); + + if(!map.has(n)) + continue; + if (map(n).border_of_hole_of == current_cc && + map(n).belongs_to != current_cc) + { +// i++; +// std::cout < + fllt_tree(mln_point(I), mln_value(I))& + fllt(const Image& input_) + { + const I& input = exact(input_); + + typedef std::vector<dpoint2d> arr_dp_t; + typedef std::vector<dpoint2d>::const_iterator arr_dp_t_it; + typedef fllt_node(mln_point(I), mln_value(I)) node_type; + typedef fllt_tree(mln_point(I), mln_value(I)) tree_type; + + // C6 neigboohood. + arr_dp_t neighb_c6[2]; + neighb_c6[0].push_back(make::dpoint2d(-1,-1)); + neighb_c6[0].push_back(make::dpoint2d(-1,0)); + neighb_c6[0].push_back(make::dpoint2d(-1,1)); + neighb_c6[0].push_back(make::dpoint2d(0,1)); + neighb_c6[0].push_back(make::dpoint2d(1,0)); + neighb_c6[0].push_back(make::dpoint2d(0,-1)); + + neighb_c6[1].push_back(make::dpoint2d(-1,0)); + neighb_c6[1].push_back(make::dpoint2d(0,1)); + neighb_c6[1].push_back(make::dpoint2d(1,1)); + neighb_c6[1].push_back(make::dpoint2d(1,0)); + neighb_c6[1].push_back(make::dpoint2d(1,-1)); + neighb_c6[1].push_back(make::dpoint2d(0,-1)); + + // Variables. + image2d<map_cell<node_type> > map(input.domain().to_larger(1)); + I u = mln::clone(input); + mln_point(I) x0; + mln_value(I) g, gN; + image2d<unsigned char> is(input.domain().to_larger(1)); + image2d<bool> tagged(input.domain().to_larger(1)); + const unsigned in_R = 255, in_N = 2, in_O = 0; + node_type* root = new node_type(); + node_type* current_cc; + node_type* current_parent = root; + + typedef p_array<mln_point(I)> arr_t; + arr_t* A = new arr_t(); + arr_t* N[256]; + for (unsigned i = 0; i < 256; ++i) + N[i] = new arr_t(); + + accu::bbox<mln_point(I)> R_box, N_box; + + unsigned n_step_1 = 0, n_step_3 = 0; + unsigned cc_cpt = 0; + bool parent_found = false; + + level::fill(tagged, false); + mln_piter(I) min(input.domain()); + min.start(); + // Step 1. + step_1: + { +#ifdef FLLTDEBUG + std::cout << "Step 1" << std::endl; +#endif + ++n_step_1; + for(;min.is_valid(); min.next()) + if (!tagged(min)) + break; + + if (!min.is_valid()) + goto end; + + x0 = min; + g = input(x0); + current_cc = new node_type(); + ++cc_cpt; + current_cc->elt().value = g; + current_cc->elt().npoints = 0; + if (cc_cpt > 1) + current_parent = 0; +#ifdef FLLTDEBUG + std::cout << "current_cc: " << current_cc << std::endl; +#endif + } + + // Step 2. + step_2: + { +#ifdef FLLTDEBUG + std::cout << "Step 2" << std::endl; +#endif + if (N_box.is_valid()) + level::fill(inplace(is | N_box.to_result()), in_O); + + N_box.init(); + R_box.init(); + A->clear(); + A->append(x0); + clear_N(N); + + mln_assertion(map(x0).belongs_to == 0); + if (map(x0).border_of_hole_of != 0) + { + mln_assertion(map(x0).border_of_hole_of != current_cc); + current_parent = map(x0).border_of_hole_of; +// std::cout << "propagation : " << x0 << std::endl; + } + } + + // Step 3. + step_3: + { + ++n_step_3; +#ifdef FLLTDEBUG + std::cout << "Step 3" << std::endl; +#endif + mln_piter(arr_t) a(*A); + + // Stop. + if (A->npoints() == 0) + goto end; + + // R <- R U A +#ifdef FLLTDEBUG + std::cout << "Add To R : "; +#endif + for_all(a) + { + mln_assertion(map(a).belongs_to == 0); + map(a).belongs_to = current_cc; + current_cc->elt().points.append(a); + current_cc->elt().npoints++; + tagged(a) = true; + is(a) = in_R; +#ifdef FLLTDEBUG + std::cout << a; +#endif + } +#ifdef FLLTDEBUG + std::cout << std::endl; +#endif + + +#ifdef FLLTDEBUG + std::cout << "points of A : " << A->npoints() << std::endl; +#endif + mln_assertion(A->npoints() > 0); + R_box.take(A->bbox()); + mln_assertion(R_box.is_valid()); + +#ifdef FLLTTRACE + save_u(u, is, R_box); +#endif + // N <- N U { x in nbh of A and not in R / input(x) == g} +#ifdef FLLTDEBUG + std::cout << "Add To N : "; +#endif + for_all(a) + { + arr_dp_t* nbh = &neighb_c6[a[1] % 2]; + for(arr_dp_t_it x = nbh->begin(); x != nbh->end(); x++) + { + mln_point(I) n = mln_point(I)(a) + mln_dpoint(I)(*x); + if (is(n) == in_O) + { + if (!current_parent) + { + if (map(n).border_of_hole_of != 0 && + map(n).border_of_hole_of != map(n).belongs_to) + { + mln_assertion(map(n).border_of_hole_of != current_cc); + current_parent = map(n).border_of_hole_of; +// std::cout << "propagation : " << n << std::endl; + } + else if (map(n).belongs_to) + { + current_parent = map(n).belongs_to->parent(); + mln_assertion(current_parent != current_cc); + } + } + map(n).set_border_of_hole_of(current_cc); + N_box.take(n); + is(n) = in_N; + if (u.has(n)) + N[u(n)]->append(n); +#ifdef FLLTDEBUG + std::cout << n; +#endif + } + } + } +#ifdef FLLTDEBUG + std::cout << std::endl; +#endif + +#ifdef FLLTDEBUG + std::cout << "g = " << g << std::endl; +#endif + + // Stop if N[g] is empty. + if (N[g]->npoints() == 0) + { + add_npoints_to(current_parent, current_cc->elt().npoints); + // Was : current_parent->elt().npoints += current_cc->elt().npoints; + current_cc->set_parent(current_parent); + erase_exterior_border(map, N_box, current_cc, neighb_c6); + goto step_1; + } + else + { + // CC is growing. + swap_arrays(A, N[g]); + N[g]->clear(); + goto step_3; + } + } + + end: + { + std::cout << "n_step_1 : " << n_step_1 + << " n_step_3 : " << n_step_3 + << " number of cc : " << cc_cpt << std::endl; + } + + return *new tree_type(root); + } + + } // end of namespace mln::my + +} // end of namespace mln + + +int main() +{ + using namespace mln; + using namespace mln::my; + using value::int_u8; + + typedef image2d<int_u8> I; + typedef fllt_node(mln_point_(I), mln_value_(I)) node_type; + typedef fllt_tree(mln_point_(I), mln_value_(I)) tree_type; + +// image2d<int_u8> ima; +// //io::pgm::load(ima, "../../../img/lena.pgm"); +// io::pgm::load(ima, "../tapis.pgm"); + + + // int_u8 vs[9][9] = { + + // { 2, 2, 2, 2, 2, 2, 2, 2, 2 }, + // { 2, 2, 2, 2, 2, 2, 2, 2, 2 }, + // { 2, 2, 2, 2, 2, 2, 2, 2, 2 }, + // { 2, 2, 2, 2, 2, 2, 2, 2, 2 }, + // { 2, 2, 2, 2, 2, 2, 2, 2, 2 }, + // { 2, 2, 2, 2, 2, 2, 2, 2, 2 }, + // { 2, 2, 2, 2, 2, 2, 2, 2, 2 }, + // { 2, 2, 2, 2, 2, 2, 2, 2, 2 }, + // { 2, 2, 2, 2, 2, 2, 2, 2, 2 }, + + // }; + + //image2d<int_u8> lena = make::image2d(vs); + +// int vs[3][6] = { {0, 0, 0, 1, 1, 1}, +// {0, 1, 0, 1, 0, 1}, +// {0, 0, 0, 1, 1, 1} }; + +// int vs[5][5] = { {100, 100, 100, 100, 100}, +// {100, 200, 255, 200, 100}, +// {100, 200, 200, 200, 100}, +// {100, 200, 255, 200, 100}, +// {100, 100, 100, 100, 100} }; + + int vs[9][9] = { {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} }; + +// int vs[7[7] = { {101, 101, 101, 191, 204, 255, 191}, +// {101, 101, 191, 204, 204, 204, 204}, +// {101, 191, 191, 204, 255, 204, 191}, +// {204, 204, 204, 191, 191, 191, 76}, +// {191, 191, 204, 191, 101, 101, 76}, +// {204, 204, 191, 204, 101, 76, 76}, +// {191, 191, 191, 101, 76, 101, 0}}; + + +// int vs[2][1] = { {121}, {101} }; + + image2d<int> ima_(make::image2d(vs)); + image2d<int_u8> ima(ima_.domain()); + level::fill(ima, ima_); + + tree_type tree = my::fllt(ima); + + + draw_tree(ima, tree); + + + + image2d<value::int_u8> output (ima.domain ()); + util::tree_to_image (tree, output); + mln_assertion(output == ima); + io::pgm::save(output, "out.pgm"); + + image2d<value::int_u8> bounds (ima.domain ()); + visualize_bounds(bounds, tree, 2); + io::pgm::save(bounds, "bounds.pgm"); + +} Index: trunk/milena/sandbox/garrigues/fllt/fllt_simple.cc =================================================================== --- trunk/milena/sandbox/garrigues/fllt/fllt_simple.cc (revision 1876) +++ trunk/milena/sandbox/garrigues/fllt/fllt_simple.cc (revision 1877) @@ -41,13 +41,18 @@ #include <mln/io/pgm/save.hh> #include <mln/level/fill.hh> +#include <mln/level/compare.hh> #include <mln/debug/println.hh> #include <mln/labeling/regional_minima.hh> #include <mln/accu/bbox.hh> #include <mln/io/pgm/save.hh> +#include <mln/util/tree.hh> +#include <mln/util/tree_to_image.hh> +#include <mln/util/branch_iter_ind.hh> #include <mln/core/cast_image.hh> +#include <mln/core/p_queue_fast.hh> namespace mln { @@ -108,11 +113,110 @@ continuer jusqu'a avoir marquer tout les points + Cette methode me marche que dans le cas ou les courbes de niveau corespondent + au formes car on creer les formes en parcourant les pixels. + + Le probleme peut etre resolu en grossissant la forme en passant sur les courbes + de niveaux qui se sitent entre les pixels. */ namespace my { +# define fllt_tree(P, V) mln::util::tree< fllt_node_elt<P, V> > +# define fllt_node(P, V) mln::util::tree_node< fllt_node_elt<P, V> > +# define fllt_branch(P, V) mln::util::branch< fllt_node_elt<P, V> > +# define fllt_branch_iter_ind(P, V) mln::util::branch_iter_ind< fllt_node_elt<P, V> > + + + template <typename P, typename V> + struct fllt_node_elt + { + V value; + p_array points; + p_array holes; + /// Tell if his parent if brighter or not. Nb : if the parent + /// if brighter, the node come from the lower level set + bool brighter; + unsigned npoints; + + }; + + template <typename P, typename V> + void add_npoints_to(fllt_node(P, V)* node, unsigned npoints) + { + mln_assertion(node); + + node->elt().npoints += npoints; + if (node->parent()) + add_npoints_to(node->parent(), npoints); + } + + + template <typename R> + struct map_cell + { + R* border_of_hole_of; + R* old_border_of_hole_of; + R* belongs_to; + + map_cell() : border_of_hole_of(0), belongs_to(0) {} + + void restore_border() + { border_of_hole_of = old_border_of_hole_of; } + + void set_border_of_hole_of(R* b) + { + old_border_of_hole_of = border_of_hole_of; + border_of_hole_of = b; + } + }; + + + + template <typename P, typename V> + void + draw_tree(const image2d<V>& ima, + fllt_tree(P, V)& tree) + { + fllt_branch_iter_ind(P, V) p(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 + << " value = " << (*p).elt().value << std::endl + << " npoints = " << (*p).elt().npoints << std::endl + << std::endl; + + if ((*p).elt().points.npoints() > 0) + debug::println(ima | (*p).elt().points); + std::cout << std::endl; + } + } + + + template <typename P, typename V> + void + visualize_bounds(image2d<value::int_u8>& output, + fllt_tree(P, V)& tree, + unsigned limit) + { + fllt_branch_iter_ind(P, V) p(tree.main_branch()); + level::fill(output, 255); + for_all(p) + { + if ((*p).elt().npoints > limit) + { + mln_piter(p_array<point2d>) q((*p).elt().points); + for_all(q) + { + output(q) = 0; + } + } + } + } void save_u(const image2d<value::int_u8>& u, const image2d<unsigned char>& is, @@ -142,27 +246,109 @@ N = tmp; } - template <typename I, typename Nbh> - void fllt(const Image& input_, const Neighborhood<Nbh>& nbh_) + + template <typename N_t> + void clear_N(N_t& N) + { + for (unsigned i = 0; i < 256; ++i) + N[i]->clear(); + } + + template <typename I, typename CC> + void erase_exterior_border(I& map, const box2d& bbox, const CC& current_cc, const std::vector<dpoint2d> nbh[]) + { + typedef const std::vector<dpoint2d> arr_dp_t; + typedef std::vector<dpoint2d>::const_iterator arr_dp_t_it; + mln_piter(I) p(bbox); + for_all(p) + if (map(p).border_of_hole_of == current_cc) + { + //mln_assertion(map(p).belongs_to != current_cc); + break; + } + mln_assertion(map(p).belongs_to != current_cc); + p_queue_fast<mln_point(I)> qu; + map(p).restore_border(); + qu.push(p); +// std::cout << std::endl; + + while(!qu.is_empty()) + { + mln_point(I) a = qu.pop_front(); + //map(a).border_of_hole_of = 0; + arr_dp_t* n_dp = &nbh[abs(a[1] % 2 > 0)]; + +// unsigned i = 0; + for(arr_dp_t_it x = n_dp->begin(); x != n_dp->end(); x++) + { + mln_point(I) n = mln_point(I)(a) + mln_dpoint(I)(*x); + + if(!map.has(n)) + continue; + if (map(n).border_of_hole_of == current_cc && + map(n).belongs_to != current_cc) + { +// i++; +// std::cout < + fllt_tree(mln_point(I), mln_value(I))& + fllt(const Image& input_) { const I& input = exact(input_); - const Nbh& nbh = exact(nbh_); + + typedef std::vector<dpoint2d> arr_dp_t; + typedef std::vector<dpoint2d>::const_iterator arr_dp_t_it; + typedef fllt_node(mln_point(I), mln_value(I)) node_type; + typedef fllt_tree(mln_point(I), mln_value(I)) tree_type; + + // C6 neigboohood. + arr_dp_t neighb_c6[2]; + neighb_c6[0].push_back(make::dpoint2d(-1,-1)); + neighb_c6[0].push_back(make::dpoint2d(-1,0)); + neighb_c6[0].push_back(make::dpoint2d(-1,1)); + neighb_c6[0].push_back(make::dpoint2d(0,1)); + neighb_c6[0].push_back(make::dpoint2d(1,0)); + neighb_c6[0].push_back(make::dpoint2d(0,-1)); + + neighb_c6[1].push_back(make::dpoint2d(-1,0)); + neighb_c6[1].push_back(make::dpoint2d(0,1)); + neighb_c6[1].push_back(make::dpoint2d(1,1)); + neighb_c6[1].push_back(make::dpoint2d(1,0)); + neighb_c6[1].push_back(make::dpoint2d(1,-1)); + neighb_c6[1].push_back(make::dpoint2d(0,-1)); // Variables. + image2d<map_cell<node_type> > map(input.domain().to_larger(1)); I u = mln::clone(input); mln_point(I) x0; mln_value(I) g, gN; - image2d<unsigned char> is(input.domain()); - image2d<bool> tagged(input.domain()); + image2d<unsigned char> is(input.domain().to_larger(1)); + image2d<bool> tagged(input.domain().to_larger(1)); const unsigned in_R = 255, in_N = 2, in_O = 0; + node_type* root = new node_type(); + node_type* current_cc; + node_type* current_parent = root; typedef p_array<mln_point(I)> arr_t; arr_t* A = new arr_t(); - arr_t* N = new arr_t(); + arr_t* N[256]; + for (unsigned i = 0; i < 256; ++i) + N[i] = new arr_t(); accu::bbox<mln_point(I)> R_box, N_box; unsigned n_step_1 = 0, n_step_3 = 0; + unsigned cc_cpt = 0; + bool parent_found = false; level::fill(tagged, false); mln_piter(I) min(input.domain()); @@ -174,7 +360,7 @@ std::cout << "Step 1" << std::endl; #endif ++n_step_1; - for(min.next(); min.is_valid(); min.next()) + for(;min.is_valid(); min.next()) if (!tagged(min)) break; @@ -183,6 +369,15 @@ x0 = min; g = input(x0); + current_cc = new node_type(); + ++cc_cpt; + current_cc->elt().value = g; + current_cc->elt().npoints = 0; + if (cc_cpt > 1) + current_parent = 0; +#ifdef FLLTDEBUG + std::cout << "current_cc: " << current_cc << std::endl; +#endif } // Step 2. @@ -198,7 +393,15 @@ R_box.init(); A->clear(); A->append(x0); - N->clear(); + clear_N(N); + + mln_assertion(map(x0).belongs_to == 0); + if (map(x0).border_of_hole_of != 0) + { + mln_assertion(map(x0).border_of_hole_of != current_cc); + current_parent = map(x0).border_of_hole_of; +// std::cout << "propagation : " << x0 << std::endl; + } } // Step 3. @@ -209,7 +412,6 @@ std::cout << "Step 3" << std::endl; #endif mln_piter(arr_t) a(*A); - mln_niter(Nbh) x(nbh, a); // Stop. if (A->npoints() == 0) @@ -221,6 +423,10 @@ #endif for_all(a) { + mln_assertion(map(a).belongs_to == 0); + map(a).belongs_to = current_cc; + current_cc->elt().points.append(a); + current_cc->elt().npoints++; tagged(a) = true; is(a) = in_R; #ifdef FLLTDEBUG @@ -247,17 +453,39 @@ std::cout << "Add To N : "; #endif for_all(a) - for_all(x) - if (u.has(x) && is(x) == in_O && input(x) == g) { - mln_assertion(!tagged(x)); - N_box.take(x); - is(x) = in_N; - N->append(x); + arr_dp_t* nbh = &neighb_c6[a[1] % 2]; + for(arr_dp_t_it x = nbh->begin(); x != nbh->end(); x++) + { + mln_point(I) n = mln_point(I)(a) + mln_dpoint(I)(*x); + if (is(n) == in_O) + { + if (!current_parent) + { + if (map(n).border_of_hole_of != 0 && + map(n).border_of_hole_of != map(n).belongs_to) + { + mln_assertion(map(n).border_of_hole_of != current_cc); + current_parent = map(n).border_of_hole_of; +// std::cout << "propagation : " << n << std::endl; + } + else if (map(n).belongs_to) + { + current_parent = map(n).belongs_to->parent(); + mln_assertion(current_parent != current_cc); + } + } + map(n).set_border_of_hole_of(current_cc); + N_box.take(n); + is(n) = in_N; + if (u.has(n)) + N[u(n)]->append(n); #ifdef FLLTDEBUG - std::cout << x; + std::cout << n; #endif } + } + } #ifdef FLLTDEBUG std::cout << std::endl; #endif @@ -266,26 +494,32 @@ std::cout << "g = " << g << std::endl; #endif - // Stop if N is empty. - if (N->npoints() == 0) + // Stop if N[g] is empty. + if (N[g]->npoints() == 0) + { + add_npoints_to(current_parent, current_cc->elt().npoints); + // Was : current_parent->elt().npoints += current_cc->elt().npoints; + current_cc->set_parent(current_parent); + erase_exterior_border(map, N_box, current_cc, neighb_c6); goto step_1; + } else { - swap_arrays(A, N); - N->clear(); + // CC is growing. + swap_arrays(A, N[g]); + N[g]->clear(); goto step_3; } } - step_4: - { - // Follow N, find the holes, and browse it. - } - end: { - std::cout << n_step_1 << ' ' << n_step_3 << std::endl; + std::cout << "n_step_1 : " << n_step_1 + << " n_step_3 : " << n_step_3 + << " number of cc : " << cc_cpt << std::endl; } + + return *new tree_type(root); } } // end of namespace mln::my @@ -296,11 +530,16 @@ int main() { using namespace mln; + using namespace mln::my; using value::int_u8; - image2d<int_u8> lena; - - io::pgm::load(lena, "../../../img/lena.pgm"); + typedef image2d<int_u8> I; + typedef fllt_node(mln_point_(I), mln_value_(I)) node_type; + typedef fllt_tree(mln_point_(I), mln_value_(I)) tree_type; + +// image2d<int_u8> ima; +// //io::pgm::load(ima, "../../../img/lena.pgm"); +// io::pgm::load(ima, "../tapis.pgm"); // int_u8 vs[9][9] = { @@ -319,7 +558,55 @@ //image2d<int_u8> lena = make::image2d(vs); - my::fllt(lena, c4()); - io::pgm::save(lena, "./out.pgm"); +// int vs[3][6] = { {0, 0, 0, 1, 1, 1}, +// {0, 1, 0, 1, 0, 1}, +// {0, 0, 0, 1, 1, 1} }; + +// int vs[5][5] = { {100, 100, 100, 100, 100}, +// {100, 200, 255, 200, 100}, +// {100, 200, 200, 200, 100}, +// {100, 200, 255, 200, 100}, +// {100, 100, 100, 100, 100} }; + + int vs[9][9] = { {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} }; + +// int vs[7[7] = { {101, 101, 101, 191, 204, 255, 191}, +// {101, 101, 191, 204, 204, 204, 204}, +// {101, 191, 191, 204, 255, 204, 191}, +// {204, 204, 204, 191, 191, 191, 76}, +// {191, 191, 204, 191, 101, 101, 76}, +// {204, 204, 191, 204, 101, 76, 76}, +// {191, 191, 191, 101, 76, 101, 0}}; + + +// int vs[2][1] = { {121}, {101} }; + + image2d<int> ima_(make::image2d(vs)); + image2d<int_u8> ima(ima_.domain()); + level::fill(ima, ima_); + + tree_type tree = my::fllt(ima); + + + draw_tree(ima, tree); + + + + image2d<value::int_u8> output (ima.domain ()); + util::tree_to_image (tree, output); + mln_assertion(output == ima); + io::pgm::save(output, "out.pgm"); + + image2d<value::int_u8> bounds (ima.domain ()); + visualize_bounds(bounds, tree, 2); + io::pgm::save(bounds, "bounds.pgm"); } Index: trunk/milena/sandbox/garrigues/fllt/fllt_theo.cc =================================================================== --- trunk/milena/sandbox/garrigues/fllt/fllt_theo.cc (revision 1876) +++ trunk/milena/sandbox/garrigues/fllt/fllt_theo.cc (revision 1877) @@ -25,6 +25,10 @@ // reasons why the executable file might be covered by the GNU General // Public License. +#include <iomanip> +#include <iostream> +#include <sstream> + #include <mln/core/image2d.hh> #include <mln/core/neighb2d.hh> #include <mln/core/p_array.hh> @@ -39,7 +43,10 @@ #include <mln/debug/println.hh> #include <mln/labeling/regional_minima.hh> #include <mln/accu/bbox.hh> +#include <mln/io/pgm/save.hh> + +#include <mln/core/cast_image.hh> namespace mln { @@ -47,16 +54,39 @@ namespace my { - template <typename N_t> - unsigned compute_gN(const N_t& N) + + void save_state(const image2d<unsigned char>& out) { - for (unsigned i = 0; i < 256; ++i) - if (N[i].npoints() != 0) - return i; - mln_invariant(0); - return 0; +// static int id = 0; +// std::stringstream filename; +// filename << "fllt_trace_" << std::setw(5) << std::setfill('0') +// << std::right << id++ << ".ppm"; + +// io::pgm::save(cast_image<value::int_u8>(out), filename.str()); + //io::pgm::save(out, filename.str()); } + void save_u(const image2d<value::int_u8>& u, + const image2d<unsigned char>& is, + box2d R_box) + { + static int id = 0; + std::stringstream filename; + filename << "fllt_u_" << std::setw(5) << std::setfill('0') + << std::right << id++ << ".ppm"; + + image2d<value::int_u8> out = clone(u); + const unsigned in_R = 255; + + mln_assertion(R_box.is_valid()); + mln_piter_(box2d) p(R_box); + for_all(p) + if (is(p) == in_R) + out(p) = 255; + + io::pgm::save(out, filename.str()); + //io::pgm::save(out, filename.str()); + } template <typename I, typename Nbh> void fllt(const Image& input_, const Neighborhood<Nbh>& nbh_) @@ -65,14 +95,16 @@ const Nbh& nbh = exact(nbh_); unsigned l = 0, l_max; - mln_ch_value(I, unsigned) reg_min = labeling::regional_minima(input, nbh, l_max); + mln_ch_value(I, unsigned) reg_min = + labeling::regional_minima(input, nbh, l_max); // Variables. I u = mln::clone(input); mln_point(I) x0; mln_value(I) g, gN; image2d<unsigned char> is(input.domain()); - const unsigned in_R = 1, in_N = 2, in_O = 0; + image2d<bool> tagged(input.domain()); + const unsigned in_R = 255, in_N = 2, in_O = 0; typedef p_array<mln_point(I)> arr_t; arr_t A; @@ -80,54 +112,124 @@ accu::bbox<mln_point(I)> R_box; - int cpt = 0; - + level::fill(tagged, false); + mln_piter(I) min(input.domain()); + min.start(); // Step 1. step_1: { +#ifdef FLLTDEBUG + std::cout << "Step 1" << std::endl; +#endif if (l == l_max) return; l += 1; - mln_piter(I) p(input.domain()); - for_all(p) - if (reg_min(p) == l) + for(min.next(); min.is_valid(); min.next()) + if (reg_min(min) !=0 && !tagged(min)) break; - x0 = p; + +#ifdef FLLTDEBUG + std::cout << "min local : " << min << std::endl; +#endif + + if (!min.is_valid()) + goto end; + + x0 = min; g = input(x0); } // Step 2. step_2: { +#ifdef FLLTDEBUG + std::cout << "Step 2" << std::endl; +#endif R_box.init(); level::fill(is, in_O); + A.clear(); A.append(x0); + for (unsigned i = 0; i < 256; ++i) + N[i].clear(); } // Step 3. step_3: { +#ifdef FLLTDEBUG + std::cout << "Step 3" << std::endl; +#endif mln_piter(arr_t) a(A); mln_niter(Nbh) x(nbh, a); // Stop. - if (A.npoints() > 0) + if (A.npoints() == 0) goto end; // R <- R U A +#ifdef FLLTDEBUG + std::cout << "Add To R : "; +#endif for_all(a) + { + tagged(a) = true; is(a) = in_R; +#ifdef FLLTDEBUG + std::cout << a; +#endif + } +#ifdef FLLTDEBUG + std::cout << std::endl; +#endif + + +#ifdef FLLTDEBUG + std::cout << "points of A : " << A.npoints() << std::endl; +#endif mln_assertion(A.npoints() > 0); R_box.take(A.bbox()); + mln_assertion(R_box.is_valid()); +#ifdef FLLTTRACE + save_state(is); + save_u(u, is, R_box); +#endif // N <- N U { x in nbh of A and not in R } +#ifdef FLLTDEBUG + std::cout << "Add To N : "; +#endif for_all(a) for_all(x) - if (u.has(x) && is(x) != in_R) + if (u.has(x) && (is(x) == in_O)) + { + is(x) = in_N; N[u(x)].append(x); - +#ifdef FLLTDEBUG + std::cout << x; +#endif + } +#ifdef FLLTDEBUG + std::cout << std::endl; +#endif // gN = min u(x) for all x in N - gN = compute_gN(N); + unsigned i; + for (i = 0; i < 256; ++i) + if (N[i].npoints() != 0) + { + gN = i; + break; + } +#ifdef FLLTDEBUG + std::cout << "gN = " << gN << ", g = " << g << std::endl; +#endif + + // Stop if N is empty. +#ifdef FLLTDEBUG + std::cout << "i = " < 0); // FIXME: update the number of CC of the border of R } @@ -138,25 +240,39 @@ // a) if (g < gN) { +#ifdef FLLTDEBUG + std::cout << "Step 4a" << std::endl; +#endif // FIXME: DO the hole thing. - A = N[g]; - N[g].clear(); + g = gN; - gN = compute_gN(N); + + A = N[gN]; + N[gN].clear(); + mln_assertion(A.npoints() > 0); + mln_assertion(N[gN].npoints() == 0); goto step_3; } // b) else if (g == gN) { - A = N[g]; - N[g].clear(); - g = gN; - gN = compute_gN(N); +#ifdef FLLTDEBUG + std::cout << "Step 4b" << std::endl; +#endif + A = N[gN]; + N[gN].clear(); + mln_assertion(A.npoints() > 0); + mln_assertion(N[gN].npoints() == 0); goto step_3; } // c) else { + step_4c: +#ifdef FLLTDEBUG + std::cout << "Step 4c" << std::endl; +#endif + mln_assertion(R_box.is_valid()); mln_piter(box_<mln_point(I)>) p(R_box); for_all(p) if (is(p) == in_R) @@ -180,8 +296,26 @@ using value::int_u8; image2d<int_u8> lena; + io::pgm::load(lena, "small.pgm"); + +// int_u8 vs[9][9] = { + +// { 2, 2, 2, 2, 2, 2, 2, 2, 2 }, +// { 2, 2, 2, 2, 2, 2, 2, 2, 2 }, +// { 2, 2, 2, 2, 2, 2, 2, 2, 2 }, +// { 2, 2, 2, 2, 2, 2, 2, 2, 2 }, +// { 2, 2, 2, 2, 2, 2, 2, 2, 2 }, +// { 2, 2, 2, 2, 2, 2, 2, 2, 2 }, +// { 2, 2, 2, 2, 2, 2, 2, 2, 2 }, +// { 2, 2, 2, 2, 2, 2, 2, 2, 2 }, +// { 2, 2, 2, 2, 2, 2, 2, 2, 2 }, + +// }; + + //image2d<int_u8> lena = make::image2d(vs); + my::fllt(lena, c4()); io::pgm::save(lena, "./out.pgm"); Index: trunk/milena/sandbox/garrigues/fllt/fllt_simple.svg.2.cc =================================================================== --- trunk/milena/sandbox/garrigues/fllt/fllt_simple.svg.2.cc (revision 0) +++ trunk/milena/sandbox/garrigues/fllt/fllt_simple.svg.2.cc (revision 1877) @@ -0,0 +1,349 @@ +// Copyright (C) 2008 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. + +#include <iomanip> +#include <iostream> +#include <sstream> + +#include <mln/core/image2d.hh> +#include <mln/core/sub_image.hh> +#include <mln/core/neighb2d.hh> +#include <mln/core/p_array.hh> +#include <mln/core/clone.hh> + +#include <mln/value/int_u8.hh> + +#include <mln/io/pgm/load.hh> +#include <mln/io/pgm/save.hh> + +#include <mln/level/fill.hh> +#include <mln/debug/println.hh> +#include <mln/labeling/regional_minima.hh> +#include <mln/accu/bbox.hh> +#include <mln/io/pgm/save.hh> + + +#include <mln/core/cast_image.hh> + +namespace mln +{ + // Un autre version recursive de la fllt. + + // Idee : + // Parcourir l'image en pratant d'un coin de preference, + // le parcour des pixels se fait dans un ordre conexe. + // + + /* + + fonction fllt_rec(racine R, domaine D, marques M, conexite C) + { + pour tout les points du domaine non marquees + recuperer la composante conexe A (en conexite C) qui inclut ce point : + Ceci est fait avec la methode de grossissement de region + pour avoir acces a la bordure externe et donc aux trous + de la composante. + + Cette composante sera fille de R dans l'arbre d'inclusion. + + Marquer les points de A (Peut etre fait en meme temps que la + construction de A) + + Pour chaque trous T de A : + appel recursif : fllt_rec(A, T.domaine(), marques, inv(C)) + T.domaine() sera calculer en recuperant la composante connexe + de la bordure de A lui correspondant (On recupere facilement + les segments horizontaux qui le composent -> parcour ok). + + } + inv(c4) = c8 + inv(c8) = c4 + + + Autre version qui Marche sur les images hexagonales (Plus rapide et plus simple) + car il y a plus le probleme du theoreme de jordan non verifie. + FIXME: Est-ce que rendre l'image hexagonale altere vraiment le resultat? + + pour tout les points du domaine non marquees + recuperer la composante conexe A qui inclut ce point : + Ceci est fait avec la methode de grossissement de region + pour avoir acces a la bordure externe et donc aux trous + de la composante. + + Marquer les points de A (Peut etre fait en meme temps que la + construction de A) + + Marquer les extremites des trou de A. + + Si un point de A est l'extremite d'un trou, + alors on a facilement le pere de A (la forme qui inclue A). + Sinon + C'est qu'il y a une composante connexe adjacente qui + a deja ete construite, et qui a donc deja un pere, qui + est aussi celui de A. + + continuer jusqu'a avoir marquer tout les points + + */ + + namespace my + { + + void save_u(const image2d<value::int_u8>& u, + const image2d<unsigned char>& is, + box2d R_box) + { + static int id = 0; + std::stringstream filename; + filename << "fllt_u_" << std::setw(5) << std::setfill('0') + << std::right << id++ << ".ppm"; + + image2d<value::int_u8> out = clone(u); + const unsigned in_R = 255; + + mln_piter_(box2d) p(R_box); + for_all(p) + if (is(p) == in_R) + out(p) = 255; + + io::pgm::save(out, filename.str()); + } + + void swap_arrays(p_array<point2d>*& A, + p_array<point2d>*& N) + { + p_array<point2d>* tmp = A; + A = N; + N = tmp; + } + + template <typename I> + void fllt(const Image& input_) + { + const I& input = exact(input_); + + typedef std::vector<dpoint2d> arr_dp_t; + typedef std::vector<dpoint2d>::const_iterator arr_dp_t_it; + + // C6 neigboohood. + arr_dp_t neighb_c6[2]; + neighb_c6[0].push_back(make::dpoint2d(-1,-1)); + neighb_c6[0].push_back(make::dpoint2d(-1,0)); + neighb_c6[0].push_back(make::dpoint2d(-1,1)); + neighb_c6[0].push_back(make::dpoint2d(0,-1)); + neighb_c6[0].push_back(make::dpoint2d(0,1)); + neighb_c6[0].push_back(make::dpoint2d(1,0)); + + neighb_c6[1].push_back(make::dpoint2d(1,-1)); + neighb_c6[1].push_back(make::dpoint2d(1,0)); + neighb_c6[1].push_back(make::dpoint2d(1,1)); + neighb_c6[1].push_back(make::dpoint2d(0,-1)); + neighb_c6[1].push_back(make::dpoint2d(0,1)); + neighb_c6[1].push_back(make::dpoint2d(-1,0)); + + // Variables. + I u = mln::clone(input); + mln_point(I) x0; + mln_value(I) g, gN; + image2d<unsigned char> is(input.domain()); + image2d<bool> tagged(input.domain()); + const unsigned in_R = 255, in_N = 2, in_O = 0; + + typedef p_array<mln_point(I)> arr_t; + arr_t* A = new arr_t(); + arr_t* N = new arr_t(); + + accu::bbox<mln_point(I)> R_box, N_box; + + unsigned n_step_1 = 0, n_step_3 = 0; + + level::fill(tagged, false); + mln_piter(I) min(input.domain()); + min.start(); + // Step 1. + step_1: + { +#ifdef FLLTDEBUG + std::cout << "Step 1" << std::endl; +#endif + ++n_step_1; + for(; min.is_valid(); min.next()) + if (!tagged(min)) + break; + + if (!min.is_valid()) + goto end; + + x0 = min; + g = input(x0); + } + + // Step 2. + step_2: + { +#ifdef FLLTDEBUG + std::cout << "Step 2" << std::endl; +#endif + if (N_box.is_valid()) + level::fill(inplace(is | N_box.to_result()), in_O); + + N_box.init(); + R_box.init(); + A->clear(); + A->append(x0); + N->clear(); + } + + // Step 3. + step_3: + { + ++n_step_3; +#ifdef FLLTDEBUG + std::cout << "Step 3" << std::endl; +#endif + mln_piter(arr_t) a(*A); + + // Stop. + if (A->npoints() == 0) + goto end; + + // R <- R U A +#ifdef FLLTDEBUG + std::cout << "Add To R : "; +#endif + for_all(a) + { + tagged(a) = true; + is(a) = in_R; +#ifdef FLLTDEBUG + std::cout << a; +#endif + } +#ifdef FLLTDEBUG + std::cout << std::endl; +#endif + + +#ifdef FLLTDEBUG + std::cout << "points of A : " << A->npoints() << std::endl; +#endif + mln_assertion(A->npoints() > 0); + R_box.take(A->bbox()); + mln_assertion(R_box.is_valid()); + +#ifdef FLLTTRACE + save_u(u, is, R_box); +#endif + // N <- N U { x in nbh of A and not in R / input(x) == g} +#ifdef FLLTDEBUG + std::cout << "Add To N : "; +#endif + for_all(a) + { + arr_dp_t* nbh = &neighb_c6[a[1] % 2]; +// if (a[1] % 2) +// x = &x2; + for(arr_dp_t_it x = nbh->begin(); x != nbh->end(); x++) + { + mln_point(I) n = mln_point(I)(a) + mln_dpoint(I)(*x); + if (u.has(n) && is(n) == in_O && input(n) == g) + { + mln_assertion(!tagged(n)); + N_box.take(n); + is(n) = in_N; + N->append(n); +#ifdef FLLTDEBUG + std::cout << n; +#endif + } + } + } +#ifdef FLLTDEBUG + std::cout << std::endl; +#endif + +#ifdef FLLTDEBUG + std::cout << "g = " << g << std::endl; +#endif + + // Stop if N is empty. + if (N->npoints() == 0) + goto step_1; + else + { + swap_arrays(A, N); + N->clear(); + goto step_3; + } + } + + step_4: + { + // Follow N, find the holes, and browse it. + } + + end: + { + std::cout << n_step_1 << ' ' << n_step_3 << std::endl; + } + } + + } // end of namespace mln::my + +} // end of namespace mln + + +int main() +{ + using namespace mln; + using value::int_u8; + + image2d<int_u8> lena; + + io::pgm::load(lena, "../../../img/lena.pgm"); + + + // int_u8 vs[9][9] = { + + // { 2, 2, 2, 2, 2, 2, 2, 2, 2 }, + // { 2, 2, 2, 2, 2, 2, 2, 2, 2 }, + // { 2, 2, 2, 2, 2, 2, 2, 2, 2 }, + // { 2, 2, 2, 2, 2, 2, 2, 2, 2 }, + // { 2, 2, 2, 2, 2, 2, 2, 2, 2 }, + // { 2, 2, 2, 2, 2, 2, 2, 2, 2 }, + // { 2, 2, 2, 2, 2, 2, 2, 2, 2 }, + // { 2, 2, 2, 2, 2, 2, 2, 2, 2 }, + // { 2, 2, 2, 2, 2, 2, 2, 2, 2 }, + + // }; + + //image2d<int_u8> lena = make::image2d(vs); + + my::fllt(lena); + io::pgm::save(lena, "./out.pgm"); + +}

1 0

milena r1876: Start to test another algorithm for FLLT
by Matthieu Garrigues 19 Apr '08

19 Apr '08

URL: https://svn.lrde.epita.fr/svn/oln/trunk/milena ChangeLog: 2008-04-20 Matthieu Garrigues <garrigues(a)lrde.epita.fr> Start to test another algorithm for FLLT. * sandbox/garrigues/fllt/fllt_simple.cc: New. --- fllt_simple.cc | 325 +++++++++++++++++++++++++++++++++++++++++++++++++++++++++ 1 file changed, 325 insertions(+) Index: trunk/milena/sandbox/garrigues/fllt/fllt_simple.cc =================================================================== --- trunk/milena/sandbox/garrigues/fllt/fllt_simple.cc (revision 0) +++ trunk/milena/sandbox/garrigues/fllt/fllt_simple.cc (revision 1876) @@ -0,0 +1,325 @@ +// Copyright (C) 2008 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. + +#include <iomanip> +#include <iostream> +#include <sstream> + +#include <mln/core/image2d.hh> +#include <mln/core/sub_image.hh> +#include <mln/core/neighb2d.hh> +#include <mln/core/p_array.hh> +#include <mln/core/clone.hh> + +#include <mln/value/int_u8.hh> + +#include <mln/io/pgm/load.hh> +#include <mln/io/pgm/save.hh> + +#include <mln/level/fill.hh> +#include <mln/debug/println.hh> +#include <mln/labeling/regional_minima.hh> +#include <mln/accu/bbox.hh> +#include <mln/io/pgm/save.hh> + + +#include <mln/core/cast_image.hh> + +namespace mln +{ + // Un autre version recursive de la fllt. + + // Idee : + // Parcourir l'image en pratant d'un coin de preference, + // le parcour des pixels se fait dans un ordre conexe. + // + + /* + + fonction fllt_rec(racine R, domaine D, marques M, conexite C) + { + pour tout les points du domaine non marquees + recuperer la composante conexe A (en conexite C) qui inclut ce point : + Ceci est fait avec la methode de grossissement de region + pour avoir acces a la bordure externe et donc aux trous + de la composante. + + Cette composante sera fille de R dans l'arbre d'inclusion. + + Marquer les points de A (Peut etre fait en meme temps que la + construction de A) + + Pour chaque trous T de A : + appel recursif : fllt_rec(A, T.domaine(), marques, inv(C)) + T.domaine() sera calculer en recuperant la composante connexe + de la bordure de A lui correspondant (On recupere facilement + les segments horizontaux qui le composent -> parcour ok). + + } + inv(c4) = c8 + inv(c8) = c4 + + + Autre version qui Marche sur les images hexagonales (Plus rapide et plus simple) + car il y a plus le probleme du theoreme de jordan non verifie. + FIXME: Est-ce que rendre l'image hexagonale altere vraiment le resultat? + + pour tout les points du domaine non marquees + recuperer la composante conexe A qui inclut ce point : + Ceci est fait avec la methode de grossissement de region + pour avoir acces a la bordure externe et donc aux trous + de la composante. + + Marquer les points de A (Peut etre fait en meme temps que la + construction de A) + + Marquer les extremites des trou de A. + + Si un point de A est l'extremite d'un trou, + alors on a facilement le pere de A (la forme qui inclue A). + Sinon + C'est qu'il y a une composante connexe adjacente qui + a deja ete construite, et qui a donc deja un pere, qui + est aussi celui de A. + + continuer jusqu'a avoir marquer tout les points + + */ + + namespace my + { + + + void save_u(const image2d<value::int_u8>& u, + const image2d<unsigned char>& is, + box2d R_box) + { + static int id = 0; + std::stringstream filename; + filename << "fllt_u_" << std::setw(5) << std::setfill('0') + << std::right << id++ << ".ppm"; + + image2d<value::int_u8> out = clone(u); + const unsigned in_R = 255; + + mln_piter_(box2d) p(R_box); + for_all(p) + if (is(p) == in_R) + out(p) = 255; + + io::pgm::save(out, filename.str()); + } + + void swap_arrays(p_array<point2d>*& A, + p_array<point2d>*& N) + { + p_array<point2d>* tmp = A; + A = N; + N = tmp; + } + + template <typename I, typename Nbh> + void fllt(const Image& input_, const Neighborhood<Nbh>& nbh_) + { + const I& input = exact(input_); + const Nbh& nbh = exact(nbh_); + + // Variables. + I u = mln::clone(input); + mln_point(I) x0; + mln_value(I) g, gN; + image2d<unsigned char> is(input.domain()); + image2d<bool> tagged(input.domain()); + const unsigned in_R = 255, in_N = 2, in_O = 0; + + typedef p_array<mln_point(I)> arr_t; + arr_t* A = new arr_t(); + arr_t* N = new arr_t(); + + accu::bbox<mln_point(I)> R_box, N_box; + + unsigned n_step_1 = 0, n_step_3 = 0; + + level::fill(tagged, false); + mln_piter(I) min(input.domain()); + min.start(); + // Step 1. + step_1: + { +#ifdef FLLTDEBUG + std::cout << "Step 1" << std::endl; +#endif + ++n_step_1; + for(min.next(); min.is_valid(); min.next()) + if (!tagged(min)) + break; + + if (!min.is_valid()) + goto end; + + x0 = min; + g = input(x0); + } + + // Step 2. + step_2: + { +#ifdef FLLTDEBUG + std::cout << "Step 2" << std::endl; +#endif + if (N_box.is_valid()) + level::fill(inplace(is | N_box.to_result()), in_O); + + N_box.init(); + R_box.init(); + A->clear(); + A->append(x0); + N->clear(); + } + + // Step 3. + step_3: + { + ++n_step_3; +#ifdef FLLTDEBUG + std::cout << "Step 3" << std::endl; +#endif + mln_piter(arr_t) a(*A); + mln_niter(Nbh) x(nbh, a); + + // Stop. + if (A->npoints() == 0) + goto end; + + // R <- R U A +#ifdef FLLTDEBUG + std::cout << "Add To R : "; +#endif + for_all(a) + { + tagged(a) = true; + is(a) = in_R; +#ifdef FLLTDEBUG + std::cout << a; +#endif + } +#ifdef FLLTDEBUG + std::cout << std::endl; +#endif + + +#ifdef FLLTDEBUG + std::cout << "points of A : " << A->npoints() << std::endl; +#endif + mln_assertion(A->npoints() > 0); + R_box.take(A->bbox()); + mln_assertion(R_box.is_valid()); + +#ifdef FLLTTRACE + save_u(u, is, R_box); +#endif + // N <- N U { x in nbh of A and not in R / input(x) == g} +#ifdef FLLTDEBUG + std::cout << "Add To N : "; +#endif + for_all(a) + for_all(x) + if (u.has(x) && is(x) == in_O && input(x) == g) + { + mln_assertion(!tagged(x)); + N_box.take(x); + is(x) = in_N; + N->append(x); +#ifdef FLLTDEBUG + std::cout << x; +#endif + } +#ifdef FLLTDEBUG + std::cout << std::endl; +#endif + +#ifdef FLLTDEBUG + std::cout << "g = " << g << std::endl; +#endif + + // Stop if N is empty. + if (N->npoints() == 0) + goto step_1; + else + { + swap_arrays(A, N); + N->clear(); + goto step_3; + } + } + + step_4: + { + // Follow N, find the holes, and browse it. + } + + end: + { + std::cout << n_step_1 << ' ' << n_step_3 << std::endl; + } + } + + } // end of namespace mln::my + +} // end of namespace mln + + +int main() +{ + using namespace mln; + using value::int_u8; + + image2d<int_u8> lena; + + io::pgm::load(lena, "../../../img/lena.pgm"); + + + // int_u8 vs[9][9] = { + + // { 2, 2, 2, 2, 2, 2, 2, 2, 2 }, + // { 2, 2, 2, 2, 2, 2, 2, 2, 2 }, + // { 2, 2, 2, 2, 2, 2, 2, 2, 2 }, + // { 2, 2, 2, 2, 2, 2, 2, 2, 2 }, + // { 2, 2, 2, 2, 2, 2, 2, 2, 2 }, + // { 2, 2, 2, 2, 2, 2, 2, 2, 2 }, + // { 2, 2, 2, 2, 2, 2, 2, 2, 2 }, + // { 2, 2, 2, 2, 2, 2, 2, 2, 2 }, + // { 2, 2, 2, 2, 2, 2, 2, 2, 2 }, + + // }; + + //image2d<int_u8> lena = make::image2d(vs); + + my::fllt(lena, c4()); + io::pgm::save(lena, "./out.pgm"); + +}

1 0