URL: https://svn.lrde.epita.fr/svn/oln/trunk/milena ChangeLog: 2007-12-06 Simon Nivault &lt;simon.nivault(a)lrde.epita.fr&gt; Add sparse image and test. * mln/core/sparse_encode.hh: Rewrite. * mln/core/sparse_image.hh: Rewrite. * tests/core/Makefile.am: Add test. * tests/core/sparse_image.cc: New. --- mln/core/sparse_encode.hh | 81 ++++++++++++++++++++++++++----------------- mln/core/sparse_image.hh | 83 +++++++++++++++++++++++++++++++++------------ tests/core/Makefile.am | 2 + tests/core/sparse_image.cc | 76 +++++++++++++++++++++++++++++++++++++++++ 4 files changed, 189 insertions(+), 53 deletions(-) Index: trunk/milena/tests/core/sparse_image.cc =================================================================== --- trunk/milena/tests/core/sparse_image.cc (revision 0) +++ trunk/milena/tests/core/sparse_image.cc (revision 1595) @@ -0,0 +1,76 @@ +// 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. + +/*! \file tests/core/sparse_image.cc + * + * \brief Test on mln::sparse_image.hh. + */ + +#include <mln/core/image2d.hh> +#include <mln/value/int_u8.hh> +#include <mln/io/pgm/load.hh> +#include <mln/pw/all.hh> +#include <mln/core/neighb2d.hh> + +#include <mln/labeling/blobs.hh> +#include <mln/level/transform.hh> +#include <mln/level/paste.hh> +#include <mln/level/compare.hh> +#include <mln/io/pgm/save.hh> + +#include <mln/core/sparse_encode.hh> + +struct fold_t : public mln::Function_v2v< fold_t > +{ + typedef mln::value::int_u8 result; + result operator()(unsigned i) const { return i == 0 ? 0 : (i - 1) % 255 + 1; } +}; + + + +int main() +{ + using namespace mln; + using value::int_u8; + + image2d<int_u8> lena; + io::pgm::load(lena, "../../img/tiny.pgm"); + image2d<int_u8> cmp(lena.domain()); + + unsigned n; + image2d<unsigned> labels = labeling::blobs((pw::value(lena) > pw::cst(172u)) | lena.domain(), + c4(), n); + + sparse_image<point2d, int_u8> sparse = sparse_encode(level::transform(labels, fold_t())); + + std::cout << n << ", compression :" << sparse.compression() << std::endl; + + level::fill(cmp, literal::zero); + level::paste(sparse, cmp); + + mln_assertion(cmp == level::transform(labels, fold_t())); +} Index: trunk/milena/tests/core/Makefile.am =================================================================== --- trunk/milena/tests/core/Makefile.am (revision 1594) +++ trunk/milena/tests/core/Makefile.am (revision 1595) @@ -12,6 +12,7 @@ obased_rle_image \ p_runs \ rle_image \ + sparse_image \ t_image category_SOURCES = category.cc @@ -23,6 +24,7 @@ obased_rle_image_SOURCES = obased_rle_image.cc p_runs_SOURCES = p_runs.cc rle_image_SOURCES = rle_image.cc +sparse_image_SOURCES = sparse_image.cc t_image_SOURCES = t_image.cc TESTS = $(check_PROGRAMS) Index: trunk/milena/mln/core/sparse_encode.hh =================================================================== --- trunk/milena/mln/core/sparse_encode.hh (revision 1594) +++ trunk/milena/mln/core/sparse_encode.hh (revision 1595) @@ -30,71 +30,88 @@ /*! \file mln/core/sparse_encode.hh * - * \brief FIXME. + * \brief Definintion of function which encodes an image in sparse_image. */ # include <mln/core/sparse_image.hh> -# include <vector> namespace mln { /*! - ** encode a generic image to a sparse image format + ** encode an image class to a sparse_image ** - ** @param input an Image + ** @param input has to respect the Image concept ** - ** @return a sparse image + ** @return sparse_image */ template <typename I> sparse_image<mln_point(I), mln_value(I)> - sparse_encode(const Image<I>& input); + sparse_encode(const Image<I>& input, bool ignore_zero = true); # ifndef MLN_INCLUDE_ONLY + /*! + ** test if Point p1 and p2 are on the same line + */ + template <typename P> + inline + bool + on_the_same_line(const P& p1, const P& p2, int len) + { + const unsigned dim = P::dim; + bool same_line = true; + + for (unsigned n = 0; same_line && n < dim - 1; ++n) + same_line = (p1[n] == p2[n]); + return same_line && p1[dim - 1] + len == p2[dim - 1]; + } template <typename I> inline sparse_image<mln_point(I), mln_value(I)> - sparse_encode(const Image<I>& input) + sparse_encode(const Image<I>& input, bool ignore_zero) { + typedef mln_point(I) P; + sparse_image<mln_point(I), mln_value(I)> output; + const I& ima = exact(input); mln_piter(I) p(exact(input).domain()); - unsigned len = 1; - // old point first dim coordinate - typename I::coord old = 1; - // range pointstart + unsigned len = 0; mln_point(I) rstart; - // range value - std::vector<mln_value(I)> values; - - p.start(); - if (not p.is_valid()) - return output; + std::vector< mln_value(I) > rvalue; + rvalue.clear(); - rstart = p; - - old = p[0]; - values.push_back(exact(input)(p)); - p.next_(); - while (p.is_valid()) + for_all(p) + if (!ignore_zero || ima(p) != literal::zero || len) { - if (p[0] - 1 == old) + if (len == 0) { ++len; - values.push_back(exact(input)(p)); + rstart = p; + std::cout << "New run " << p << ": *"; + rvalue.push_back(ima(p)); } else + if ((!ignore_zero || ima(p) != literal::zero) && + on_the_same_line(rstart, mln_point(I)(p), len)) + { + std::cout << "*"; + ++len; + rvalue.push_back(ima(p)); + } + else + { + std::cout << std::endl; + output.insert(p_run<P>(rstart, len), rvalue); + rvalue.clear(); + if ((len = (!ignore_zero || ima(p) != literal::zero))) { - output.insert(rstart, len, values); rstart = p; - len = 1; - values.clear(); - values.push_back(exact(input)(p)); + std::cout << "New run " << p << ": "; + rvalue.push_back(ima(p)); + } } - old = p[0]; - p.next_(); } - output.insert(rstart, len, values); return output; } Index: trunk/milena/mln/core/sparse_image.hh =================================================================== --- trunk/milena/mln/core/sparse_image.hh (revision 1594) +++ trunk/milena/mln/core/sparse_image.hh (revision 1595) @@ -30,12 +30,12 @@ /*! \file mln/core/sparse_image.hh * - * \brief Definition of mln::sparse_image + * \brief Definition of an image with sparse encoding. */ # include <mln/core/internal/run_image.hh> -# include <mln/core/internal/run_pset.hh> -# include <mln/core/internal/run_psite.hh> +# include <mln/core/p_runs.hh> +# include <mln/core/runs_psite.hh> # include <mln/value/set.hh> # include <vector> @@ -45,6 +45,7 @@ // Fwd decl. template <typename P, typename T> struct sparse_image; + namespace internal { @@ -55,13 +56,41 @@ /// Image values. std::vector< std::vector<T> > values_; + /// domain of the image - run_pset_<P> domain_; + p_runs_<P> domain_; + + /// Return the size of the data in memory. + unsigned size_mem() const; }; } // end of namespace mln::internal - /*! \brief Sparse image. + + namespace trait + { + + template <typename P, typename T> + struct image_< sparse_image<P,T> > : default_image_< T, sparse_image<P,T> > + { + typedef trait::image::category::primary category; + + typedef trait::image::access::browsing access; + // FIXME: Put the right dimension. + typedef trait::image::space::two_d space; + typedef trait::image::size::regular size; + typedef trait::image::support::aligned support; + + typedef trait::image::border::none border; + typedef trait::image::data::linear data; + typedef trait::image::io::read_only io; + typedef trait::image::speed::slow speed; + }; + + } // end of namespace mln::trait + + + /*! \brief SPARSE image. * * * Parameter \c P is the type of the image points. @@ -69,15 +98,16 @@ * This image is not point wise accessible. */ template <typename P, typename T> - class sparse_image : public internal::run_image_< P, sparse_image<P, T> > + class sparse_image : public internal::run_image_< T, P, sparse_image<P, T> > { public: typedef T value; typedef T& lvalue; typedef const T rvalue; - typedef internal::run_psite<P> psite; + typedef runs_psite<P> psite; typedef mln::value::set<T> vset; - typedef internal::run_pset_<P> pset; + typedef p_runs_<P> pset; + /// Skeleton. typedef sparse_image< tag::psite_<P>, tag::value_<T> > skeleton; @@ -86,13 +116,13 @@ sparse_image(); /// Add a new range to the image. - void insert(const P& p, unsigned len, const std::vector<T>& value); + void insert(const p_run<P>& pr, const std::vector<T>& value); /// Read-only access to the image value located at point \p p. - rvalue operator() (const psite& p) const; + rvalue operator() (const psite& site) const; /// Read-write access to the image value located at point \p p. - lvalue operator() (const psite& p); + lvalue operator() (const psite& site); /// Test if this image has been initialized. bool has_data() const; @@ -102,8 +132,10 @@ /// Give the definition domain. const pset& domain() const; + }; + # ifndef MLN_INCLUDE_ONLY namespace internal @@ -117,12 +149,21 @@ { } + template <typename P, typename T> + inline + unsigned + data_< sparse_image<P,T> >::size_mem() const + { + return sizeof(T) * domain_.npoints() + domain_.size_mem(); + } + } // end of namespace mln::internal template <typename P, typename T> inline sparse_image<P, T>::sparse_image() { + this->data_ = new internal::data_< sparse_image<P,T> >(); } template <typename P, typename T> @@ -144,32 +185,32 @@ template <typename P, typename T> inline void - sparse_image<P, T>::insert(const P& p, unsigned len, - const std::vector<T>& value) + sparse_image<P, T>::insert(const p_run<P>& pr, const std::vector<T>& value) { if (!this->has_data()) this->data_ = new internal::data_< sparse_image<P,T> >(); - this->data_->domain_.insert(p, len); + mln_assertion(this->data_->values_.size() == 0 || + pr.first() > this->data_->domain_[this->data_->domain_.nruns() - 1].first()); + this->data_->domain_.insert(pr); this->data_->values_.push_back(value); } template <typename P, typename T> inline typename sparse_image<P, T>::rvalue - sparse_image<P, T>::operator() - (const typename sparse_image<P, T>::psite& site) const + sparse_image<P, T>::operator() (const typename sparse_image<P, T>::psite& site) + const { - mln_precondition(this->has_data() && - site.pset_pos_() < this->data_->values_.size() && - site.index_() < this->data_->values_[site.pset_pos_()].size()); + mln_precondition(this->has_data()); + mln_precondition(site.pset_pos_() < this->data_->values_.size()); + mln_precondition(site.index_() < this->data_->values_[site.pset_pos_()].size()); return this->data_->values_[site.pset_pos_()][site.index_()]; } template <typename P, typename T> inline typename sparse_image<P, T>::lvalue - sparse_image<P, T>::operator() - (const typename sparse_image<P,T>::psite& site) + sparse_image<P, T>::operator() (const typename sparse_image<P, T>::psite& site) { mln_precondition(this->has_data() && site.pset_pos_() < this->data_->values_.size() &&