URL: https://svn.lrde.epita.fr/svn/oln/trunk/milena ChangeLog: 2008-04-25 Matthieu Garrigues <garrigues@lrde.epita.fr> Add delta points array and use it in fllt. * mln/core/dp_array.hh: New. Array for delta points * sandbox/garrigues/fllt/fllt_simple.cc: Use dp_array for c6 neighborhood. Start a test with interpixel browsing. --- mln/core/dp_array.hh | 256 ++++++++++++++++++++++++++++++++++ sandbox/garrigues/fllt/fllt_simple.cc | 222 ++++++++++++++++++++++------- 2 files changed, 426 insertions(+), 52 deletions(-) Index: trunk/milena/mln/core/dp_array.hh =================================================================== --- trunk/milena/mln/core/dp_array.hh (revision 0) +++ trunk/milena/mln/core/dp_array.hh (revision 1894) @@ -0,0 +1,256 @@ +// Copyright (C) 2007 EPITA Research and Development Laboratory +// +// This file is part of the Olena Library. This library is free +// software; you can redistribute it and/or modify it under the terms +// of the GNU General Public License version 2 as published by the +// Free Software Foundation. +// +// This library is distributed in the hope that it will be useful, +// but WITHOUT ANY WARRANTY; without even the implied warranty of +// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU +// General Public License for more details. +// +// You should have received a copy of the GNU General Public License +// along with this library; see the file COPYING. If not, write to +// the Free Software Foundation, 51 Franklin Street, Fifth Floor, +// Boston, MA 02111-1307, USA. +// +// As a special exception, you may use this file as part of a free +// software library without restriction. Specifically, if other files +// instantiate templates or use macros or inline functions from this +// file, or you compile this file and link it with other files to +// produce an executable, this file does not by itself cause the +// resulting executable to be covered by the GNU General Public +// License. This exception does not however invalidate any other +// reasons why the executable file might be covered by the GNU General +// Public License. + +#ifndef MLN_CORE_DP_ARRAY_HH +# define MLN_CORE_DP_ARRAY_HH + +/*! \file mln/core/dp_array.hh + * + * \brief Definition of a point set class based on std::vector. + */ + +# include <vector> + +# include <mln/core/internal/point_set_base.hh> +# include <mln/accu/bbox.hh> + + +namespace mln +{ + + // Fwd decls. + template <typename D> struct dp_array_fwd_piter_; + template <typename D> struct dp_array_bkd_piter_; + + + /*! \brief Point set class based on std::vector. + * + * This is a multi-set of points. + * + * \warning We have some troubles with point set comparison based on + * a call to npoints(). FIXME: Explain! + * + * \todo Make it work with P being a Point_Site. + */ + template <typename D> + class dp_array : public internal::dpoints_base_< D, dp_array<D> > + { + public: + + /// Dpoint associated type. + typedef D dpoint; + + /// Point associated type. + typedef mln_point(D) point; + + /*! \brief Point_Iterator type to browse the points of a generic + * neighborhood w.r.t. the ordering of delta-points. + */ + typedef dpoints_fwd_piter<D> fwd_niter; + + /*! \brief Point_Iterator type to browse the points of a generic + * neighborhood w.r.t. the reverse ordering of delta-points. + */ + typedef dpoints_bkd_piter<D> bkd_niter; + + /// Constructor. + dp_array(); + + /// Constructor from a vector \p vect. + dp_array(const std::vector<D>& vect); + + /// Reserve \p n cells. + void reserve(std::size_t n); + + /// Test is \p p belongs to this point set. + bool has(const D& dp) const; + + /// Give the number of dpoints. + std::size_t ndpoints() const; + + /// Give the exact bounding box. + const box_<point>& bbox() const; + + /// Append a point \p p. + dp_array<D>& append(const D& dp); + + /// Append an array \p other of points. + dp_array<D>& append(const dp_array<D>& other); + + /// Clear this set. + void clear(); + + /// Return the corresponding std::vector of points. + const std::vector<D>& vect() const; + + /// Return the \p i-th point. + const D& operator[](unsigned i) const; + + /// Hook to data. + std::vector<D>& hook_(); + + protected: + + std::vector<D> vect_; + mutable accu::bbox<dpoint> bb_; + mutable bool bb_needs_update_; + + void update_bb_() const; + // FIXME: Add invariant bb_.is_valid() <=> npoints() != 0 + }; + + + +# ifndef MLN_INCLUDE_ONLY + + template <typename D> + inline + dp_array<D>::dp_array() + { + bb_needs_update_ = false; + } + + template <typename D> + inline + dp_array<D>::dp_array(const std::vector<D>& vect) + : vect_(vect) + { + bb_needs_update_ = true; + } + + template <typename D> + inline + void + dp_array<D>::reserve(std::size_t n) + { + vect_.reserve(n); + } + + template <typename D> + inline + std::vector<D>& + dp_array<D>::hook_() + { + return vect_; + } + + template <typename D> + inline + void + dp_array<D>::update_bb_() const + { + bb_.init(); + for (unsigned i = 0; i < vect_.size(); ++i) + bb_.take(vect_[i]); + bb_needs_update_ = false; + } + + template <typename D> + inline + bool + dp_array<D>::has(const D& dp) const + { + for (unsigned i = 0; i < vect_.size(); ++i) + if (vect_[i] == dp) + return true; + return false; + } + + template <typename D> + inline + std::size_t + dp_array<D>::ndpoints() const + { + return vect_.size(); + } + + template <typename D> + inline + const box_<mln_point(D)>& + dp_array<D>::bbox() const + { + mln_precondition(ndpoints() != 0); + if (bb_needs_update_) + update_bb_(); + return bb_.to_result(); + } + + template <typename D> + inline + dp_array<D>& + dp_array<D>::append(const D& dp) + { + vect_.push_back(dp); + if (! bb_needs_update_) + bb_needs_update_ = true; + return *this; + } + + template <typename D> + inline + dp_array<D>& + dp_array<D>::append(const dp_array<D>& other) + { + vect_.insert(vect_.end(), + other.vect().begin(), other.vect().end()); + if (! bb_needs_update_) + bb_needs_update_ = true; + return *this; + } + + template <typename D> + inline + void + dp_array<D>::clear() + { + bb_.init(); + vect_.clear(); + bb_needs_update_ = false; + } + + template <typename D> + inline + const std::vector<D>& + dp_array<D>::vect() const + { + return vect_; + } + + template <typename D> + inline + const D& + dp_array<D>::operator[](unsigned i) const + { + mln_precondition(i < ndpoints()); + return vect_[i]; + } + +# endif // ! MLN_INCLUDE_ONLY + +} // end of namespace mln + +#endif // ! MLN_CORE_DP_ARRAY_HH Index: trunk/milena/sandbox/garrigues/fllt/fllt_simple.cc =================================================================== --- trunk/milena/sandbox/garrigues/fllt/fllt_simple.cc (revision 1893) +++ trunk/milena/sandbox/garrigues/fllt/fllt_simple.cc (revision 1894) @@ -35,6 +35,11 @@ #include <mln/core/p_array.hh> #include <mln/core/clone.hh> +#include <mln/core/cast_image.hh> +#include <mln/core/p_queue_fast.hh> + +#include <mln/core/dp_array.hh> + #include <mln/value/int_u8.hh> #include <mln/io/pgm/load.hh> @@ -51,8 +56,6 @@ #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 { @@ -142,6 +145,146 @@ }; + struct c6_neighb + { + // C6 neigboohood. + //static std::vector<dpoint2d> nbhs[2]; + static dp_array<dpoint2d> nbhs[2]; + + static inline const dp_array<dpoint2d>& get(point2d p) + { + static bool toto = false; + + if (!toto) + { + toto = true; + c6_neighb::nbhs[0].append(make::dpoint2d(-1,-1)); + c6_neighb::nbhs[0].append(make::dpoint2d(-1,0)); + c6_neighb::nbhs[0].append(make::dpoint2d(-1,1)); + c6_neighb::nbhs[0].append(make::dpoint2d(0,1)); + c6_neighb::nbhs[0].append(make::dpoint2d(1,0)); + c6_neighb::nbhs[0].append(make::dpoint2d(0,-1)); + + c6_neighb::nbhs[1].append(make::dpoint2d(-1,0)); + c6_neighb::nbhs[1].append(make::dpoint2d(0,1)); + c6_neighb::nbhs[1].append(make::dpoint2d(1,1)); + c6_neighb::nbhs[1].append(make::dpoint2d(1,0)); + c6_neighb::nbhs[1].append(make::dpoint2d(1,-1)); + c6_neighb::nbhs[1].append(make::dpoint2d(0,-1)); + } + + return nbhs[abs(p[1] % 2)]; + } + }; + dp_array<dpoint2d> c6_neighb::nbhs[2]; + + + struct c6_interpixel + { + c6_interpixel() {} + + c6_interpixel(point2d pt1, point2d pt2, + unsigned i1, unsigned i2) + : pt1(pt1), pt2(pt2), + i1(i1), i2(i2) + { + mln_assertion(pt1 + c6_neighb::get(pt1)[i1] == pt2); + mln_assertion(pt2 + c6_neighb::get(pt2)[i2] == pt1); + } + + bool is_valid() + { + return (pt1 + c6_neighb::get(pt1)[i1] == pt2) && + (pt2 + c6_neighb::get(pt2)[i2] == pt1); + } + + point2d pt1, pt2; + unsigned i1, i2; + }; + + template <typename I> + inline bool is_level_line_in_ip(const Image<I>& ima, + const c6_interpixel& ip, + const mln_value(I)& v) + { + mln_value(I) v1, v2; + v1 = ima(ip.pt1); + v2 = ima(ip.pt2); + + return v1 != v2 && ((v1 >= v && v2 <= v) || (v1 <= v && v2 >= v)); + } + + class c6_interpixel_niter + { + public: + c6_interpixel_niter(const c6_interpixel& ip) + : ip_ref_(ip) + { + } + + bool is_valid() const + { + i_ >= 4; + } + + void invalidate() + { + i_ = 4; + } + + void start() + { + i_ = 0; + ip_.pt1 = ip_ref_.pt1 + c6_neighb::get(ip_ref_.pt1)[ip_ref_.i1 + 1]; + ip_.pt2 = ip_ref_.pt2; + ip_.i1 = ip_ref_.i1 + 1; + ip_.i2 = ip_ref_.i2 - 1; + mln_assertion(ip_.is_valid()); + } + + void next_() + { + mln_assertion(is_valid() && i_ > 0); + i_++; + switch (i_) + { + case 1: + ip_.pt1 = ip_ref_.pt1 + c6_neighb::get(ip_ref_.pt1)[ip_ref_.i1 - 1]; + mln_assertion(ip_.pt2 == ip_ref_.pt2); + ip_.i1 = ip_ref_.i1 - 1; + ip_.i2 = ip_ref_.i2 + 1; + break; + case 2: + ip_.pt1 = ip_ref_.pt1; + ip_.pt2 = ip_ref_.pt2 + c6_neighb::get(ip_ref_.pt2)[ip_.i2 + 1]; + ip_.i1 = ip_ref_.i1 - 1; + ip_.i2 = ip_ref_.i2 + 1; + break; + case 3: + mln_assertion(ip_.pt1 == ip_ref_.pt1); + ip_.pt1 = ip_ref_.pt2 + c6_neighb::get(ip_ref_.pt2)[ip_.i2 - 1]; + ip_.i1 = ip_ref_.i1 + 1; + ip_.i2 = ip_ref_.i2 - 1; + break; + } + mln_assertion(ip_.is_valid()); + } + + private: + unsigned i_; + c6_interpixel ip_; + const c6_interpixel& ip_ref_; + }; + + struct c6_niter : public dpoints_fwd_piter<dpoint2d> + { + typedef dpoints_fwd_piter<dpoint2d> super; + + c6_niter(const point2d& p) + : super(c6_neighb::get(p), p) + {} + }; + template <typename P, typename V> void add_npoints_to(fllt_node(P, V)* node, unsigned npoints) { @@ -152,7 +295,6 @@ add_npoints_to(node->parent(), npoints); } - template <typename R> struct map_cell { @@ -172,8 +314,6 @@ } }; - - template <typename P, typename V> void draw_tree(const image2d<V>& ima, @@ -196,7 +336,6 @@ } } - template <typename P, typename V> void visualize_bounds(image2d<value::int_u8>& output, @@ -246,7 +385,6 @@ N = tmp; } - template <typename N_t> void clear_N(N_t& N) { @@ -255,7 +393,7 @@ } template <typename I, typename CC> - void erase_exterior_border(I& map, const box2d& bbox, const CC& current_cc, const std::vector<dpoint2d> nbh[]) + void erase_exterior_border(I& map, const box2d& bbox, const CC& current_cc) { typedef const std::vector<dpoint2d> arr_dp_t; typedef std::vector<dpoint2d>::const_iterator arr_dp_t_it; @@ -276,21 +414,17 @@ { 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); + + c6_niter n(a); + for_all(n) + { if(!map.has(n)) continue; if (map(n).border_of_hole_of == current_cc && map(n).belongs_to != current_cc) { -// i++; -// std::cout << i << std::endl; -// mln_assertion(i <= 2); map(n).restore_border(); qu.push(n); break; @@ -310,22 +444,6 @@ 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); @@ -454,10 +572,10 @@ #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++) + + c6_niter n(a); + for_all(n) { - mln_point(I) n = mln_point(I)(a) + mln_dpoint(I)(*x); if (is(n) == in_O) { if (!current_parent) @@ -500,7 +618,7 @@ 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); + erase_exterior_border(map, N_box, current_cc); goto step_1; } else @@ -537,9 +655,9 @@ 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"); + image2d<int_u8> ima; + //io::pgm::load(ima, "../../../img/lena.pgm"); + io::pgm::load(ima, "../tapis.pgm"); // int_u8 vs[9][9] = { @@ -568,15 +686,15 @@ // {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[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}, @@ -589,14 +707,14 @@ // int vs[2][1] = { {121}, {101} }; - image2d<int> ima_(make::image2d(vs)); - image2d<int_u8> ima(ima_.domain()); - level::fill(ima, ima_); +// 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); +// draw_tree(ima, tree);