URL: https://svn.lrde.epita.fr/svn/oln/trunk/milena ChangeLog: 2007-12-03 Simon Nivault <simon.nivault@lrde.epita.fr> Creation of rle_image and test. * mln/core/internal/run_image.hh: Factorize compression code. * mln/core/p_runs.hh: Fix and add size_mem(). * mln/core/rle_encode.hh: Rewrite algo and add feature for taking zero into account or not. * mln/core/rle_image.hh: Add traits and Fixes. * mln/core/runs_psite.hh: Fix and remove a FIXME. * mln/level/transform.hh: Fix call of transform. * mln/util/lazy_set.hh: Fix and add Doc. * tests/core/Makefile.am: Add test. * tests/core/rle_image.cc: New. --- mln/core/internal/run_image.hh | 28 ++++++++++----- mln/core/p_runs.hh | 15 +++++++- mln/core/rle_encode.hh | 47 ++++++++++++------------- mln/core/rle_image.hh | 54 ++++++++++++++++++++++++----- mln/core/runs_psite.hh | 6 +-- mln/level/transform.hh | 2 - mln/util/lazy_set.hh | 4 +- tests/core/Makefile.am | 2 + tests/core/rle_image.cc | 75 +++++++++++++++++++++++++++++++++++++++++ 9 files changed, 183 insertions(+), 50 deletions(-) Index: trunk/milena/tests/core/rle_image.cc =================================================================== --- trunk/milena/tests/core/rle_image.cc (revision 0) +++ trunk/milena/tests/core/rle_image.cc (revision 1577) @@ -0,0 +1,75 @@ +// 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/labeling/blobs.cc + * + * \brief Test on mln::labeling::blobs. + */ + +#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/rle_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); + std::cout << n << std::endl; + + rle_image<point2d, int_u8> rle = rle_encode(level::transform(labels, fold_t())); + + level::fill(cmp, literal::zero); + level::paste(rle, cmp); + + mln_assertion(cmp == level::transform(labels, fold_t())); +} Index: trunk/milena/tests/core/Makefile.am =================================================================== --- trunk/milena/tests/core/Makefile.am (revision 1576) +++ trunk/milena/tests/core/Makefile.am (revision 1577) @@ -8,6 +8,7 @@ exact \ initialize \ p_runs \ + rle_image \ t_image category_SOURCES = category.cc @@ -15,6 +16,7 @@ exact_SOURCES = exact.cc initialize_SOURCES = initialize.cc p_runs_SOURCES = p_runs.cc +rle_image_SOURCES = rle_image.cc t_image_SOURCES = t_image.cc TESTS = $(check_PROGRAMS) Index: trunk/milena/mln/core/internal/run_image.hh =================================================================== --- trunk/milena/mln/core/internal/run_image.hh (revision 1576) +++ trunk/milena/mln/core/internal/run_image.hh (revision 1577) @@ -33,10 +33,9 @@ * \brief Definition of mln::internal::run_image_ class for internal use only */ -# include <mln/core/internal/image_base.hh> -# include <mln/core/internal/run_pset.hh> -# include <mln/core/internal/run_psite.hh> -# include <mln/value/set.hh> +# include <mln/core/internal/image_primary.hh> +# include <mln/core/p_runs.hh> +# include <mln/core/runs_psite.hh> namespace mln { @@ -46,22 +45,35 @@ /*! \brief Factorization class for run_image. * + * Parameter \c T is the type of the image value. * Parameter \c P is the type of the image point. * Parameter \c E is the Exact type of the image. */ - template <typename P, typename E> - class run_image_ : public internal::image_primary_< internal::run_pset_<P>, E > + template <typename T, typename P, typename E> + class run_image_ : public internal::image_primary_< p_runs_<P>, E > { protected: run_image_(); + + public: + float compression() const; }; # ifndef MLN_INCLUDE_ONLY - template <typename P, typename E> + template <typename T, typename P, typename E> + inline + run_image_<T, P, E>::run_image_() + { + } + + template <typename T, typename P, typename E> inline - run_image_<P, E>::run_image_() + float + run_image_<T, P, E>::compression() const { + return float(exact(this)->data_->size_mem()) / + float (sizeof(T) * exact(this)->data_->domain_->bbox().npoints()); } # endif // ! MLN_INCLUDE_ONLY Index: trunk/milena/mln/core/rle_image.hh =================================================================== --- trunk/milena/mln/core/rle_image.hh (revision 1576) +++ trunk/milena/mln/core/rle_image.hh (revision 1577) @@ -34,8 +34,8 @@ */ # 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> @@ -58,12 +58,37 @@ 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 + namespace trait + { + + template <typename P, typename T> + struct image_< rle_image<P,T> > : default_image_< T, rle_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 RLE image. * @@ -73,15 +98,15 @@ * This image is not point wise accessible. */ template <typename P, typename T> - class rle_image : public internal::run_image_< P, rle_image<P, T> > + class rle_image : public internal::run_image_< T, P, rle_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. @@ -91,7 +116,7 @@ rle_image(); /// Add a new range to the image. - void insert(const P& p, unsigned len, T value); + void insert(const p_run<P>& pr, T value); /// Read-only access to the image value located at point \p p. rvalue operator() (const psite& site) const; @@ -124,12 +149,21 @@ { } + template <typename P, typename T> + inline + unsigned + data_< rle_image<P,T> >::size_mem() const + { + return sizeof(T) * values_.size() + domain_.size_mem(); + } + } // end of namespace mln::internal template <typename P, typename T> inline rle_image<P, T>::rle_image() { + this->data_ = new internal::data_< rle_image<P,T> >(); } template <typename P, typename T> @@ -151,11 +185,13 @@ template <typename P, typename T> inline void - rle_image<P, T>::insert(const P& p, unsigned len, T value) + rle_image<P, T>::insert(const p_run<P>& pr, T value) { if (!this->has_data()) this->data_ = new internal::data_< rle_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); } Index: trunk/milena/mln/core/runs_psite.hh =================================================================== --- trunk/milena/mln/core/runs_psite.hh (revision 1576) +++ trunk/milena/mln/core/runs_psite.hh (revision 1577) @@ -89,7 +89,7 @@ protected: /// Start of the psite range. - P p_; // FIXME: Rename as p_ (like everywhere else!) + P p_; /// Position in the psite range. unsigned range_index_; @@ -106,11 +106,11 @@ runs_psite<P>::runs_psite(const p_runs_<P>& pr, const P& p) { unsigned i = 0; - while (i < pr.nruns() && p < pr[i].first()) + while (i < pr.nruns() && p >= pr[i].first()) ++i; mln_assertion(i != 0); - range_index_ = p[P::dim - 1] - pr[i].first()[P::dim - 1]; + range_index_ = p[P::dim - 1] - pr[i - 1].first()[P::dim - 1]; mln_assertion(pr[i - 1].npoints() > range_index_); Index: trunk/milena/mln/core/rle_encode.hh =================================================================== --- trunk/milena/mln/core/rle_encode.hh (revision 1576) +++ trunk/milena/mln/core/rle_encode.hh (revision 1577) @@ -33,8 +33,7 @@ * \brief Definintion of function which encodes an image in rle_image. */ -# include <mln/core/sparse_image.hh> -# include <vector> +# include <mln/core/rle_image.hh> namespace mln { @@ -48,7 +47,7 @@ */ template <typename I> rle_image<mln_point(I), mln_value(I)> - rle_encode(const Image<I>& input); + rle_encode(const Image<I>& input, bool ignore_zero = true); # ifndef MLN_INCLUDE_ONLY /*! @@ -59,10 +58,10 @@ bool on_the_same_line(const P& p1, const P& p2) { - unsigned dim = P::dim; + const unsigned dim = P::dim; bool same_line = true; - for (int n = dim - 1; same_line and n > 0; --n) + for (unsigned n = 0; same_line && n < dim - 1; ++n) same_line = (p1[n] == p2[n]); return same_line; } @@ -70,38 +69,36 @@ template <typename I> inline rle_image<mln_point(I), mln_value(I)> - rle_encode(const Image<I>& input) + rle_encode(const Image<I>& input, bool ignore_zero) { + typedef mln_point(I) P; + rle_image<mln_point(I), mln_value(I)> output; + const I& ima = exact(input); mln_piter(I) p (exact(input).domain()); - unsigned len = 1; - /// range point start + unsigned len = 0; mln_point(I) rstart; - /// range value mln_value(I) rvalue; - p.start(); - if (!p.is_valid()) - return output; - - rstart = p; - rvalue = exact(input)(p); - p.next_(); - while (p.is_valid()) + for_all(p) + if (!ignore_zero || ima(p) != literal::zero || len) + { + if (len == 0) { - if (rvalue == exact(input)(p) and - on_the_same_line(rstart, mln_point(I)(p))) + ++len; + rstart = p; + rvalue = ima(p); + } + else + if (rvalue == ima(p) + && on_the_same_line(rstart, mln_point(I)(p))) ++len; else { - output.insert(rstart, len, rvalue); - len = 1; - rstart = p; - rvalue = exact(input)(p); + output.insert(p_run<P>(rstart, len), rvalue); + len = 0; } - p.next_(); } - output.insert(rstart, len, rvalue); return output; } Index: trunk/milena/mln/core/p_runs.hh =================================================================== --- trunk/milena/mln/core/p_runs.hh (revision 1576) +++ trunk/milena/mln/core/p_runs.hh (revision 1577) @@ -90,6 +90,9 @@ /// Return the i-th run of the list of runs const p_run<P>& operator[](unsigned i) const; + /// Return the size of the data in memory. + unsigned size_mem() const; + // /// Return the container of the pset (internal use only). // const container& con() const; @@ -162,7 +165,7 @@ break; if (equal) mln_assertion(prec->first()[P::dim - 1] + (signed)prec->length() - < pr.first()[P::dim - 1]); + <= pr.first()[P::dim - 1]); } if (iter != con_.vect().end()) @@ -173,7 +176,7 @@ break; if (equal) mln_assertion(pr.first()[P::dim - 1] + (signed)pr.length() - < iter->first()[P::dim - 1]); + <= iter->first()[P::dim - 1]); } con_.insert(pr); @@ -217,6 +220,14 @@ return con_[i]; } + template <typename P> + inline + unsigned + p_runs_<P>::size_mem() const + { + return nruns() * 2 * (sizeof(P) + sizeof(unsigned)); + } + // template <typename P> // const typename p_runs_<P>::container& // p_runs_<P>::con() const Index: trunk/milena/mln/level/transform.hh =================================================================== --- trunk/milena/mln/level/transform.hh (revision 1576) +++ trunk/milena/mln/level/transform.hh (revision 1577) @@ -129,7 +129,7 @@ mln_precondition(exact(input).has_data()); mln_ch_value(I, mln_result(F)) output; initialize(output, input); - transform_(input, f, output); + transform(input, f, output); trace::exiting("level::transform"); return output; Index: trunk/milena/mln/util/lazy_set.hh =================================================================== --- trunk/milena/mln/util/lazy_set.hh (revision 1576) +++ trunk/milena/mln/util/lazy_set.hh (revision 1577) @@ -171,7 +171,7 @@ /*! \brief Update \a v_ from \a s_. * - * FIXME: explain. + * Make the vector contains the same element than the sorted set.. */ void update_() const; @@ -233,7 +233,7 @@ const E& lazy_set_<E>::element(unsigned i) const { - assert(i < v_.size()); + assert(i < s_.size()); if (needs_update_) update_(); return v_[i];