histogram.hh

// Copyright (C) 2001, 2002, 2003, 2004  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, 59 Temple Place - Suite 330, 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 OLENA_UTILS_HISTOGRAM_HH
# define OLENA_UTILS_HISTOGRAM_HH


# include <oln/core/image1d.hh>

# include <oln/core/image3d.hh>

# include <oln/convert/value_to_point.hh>

# include <oln/core/abstract/image.hh>

# include <ntg/core/pred_succ.hh>

# include <vector>

# define oln_cpt_type(H) mlc_exact_type(H)::cpt_type

# define oln_cpt_type_(H) mlc_exact_type_(H)::cpt_type

namespace oln {
  namespace utils {

    namespace internal {
      template <typename T>
      struct img_max_size
      {
      private:
        typedef typename ntg_is_a(T, ntg::non_vectorial)::ensure_type
                                                                ensure_type;
      public:
        typedef image1d_size size_type;
        typedef T comp_type;

        image1d_size
        operator()()
        {
          size_type s(ntg_max_val(comp_type) - ntg_min_val(comp_type) + 1,
                      1);
          return s;
        }
      };


      template <unsigned Qbits, template <unsigned> class S>
      struct img_max_size<ntg::color<3, Qbits, S> >
      {
      public:
        typedef image3d_size size_type;
        typedef typename ntg::color<3, Qbits, S>::comp_type comp_type;

        image3d_size
        operator()()
        {
          size_type s(ntg_max_val(comp_type) - ntg_min_val(comp_type) + 1,
                      ntg_max_val(comp_type) - ntg_min_val(comp_type) + 1,
                      ntg_max_val(comp_type) - ntg_min_val(comp_type) + 1,
                      1);
          return s;
        }
      };
    } // end of namespace internal

    template <class Exact>
    struct hist_traits
    {
    };


    namespace abstract
    {
      template<class Exact = mlc::final>
      class histogram: public mlc_hierarchy::any<Exact>
      {
      public:
        typedef typename mlc::exact_vt<histogram<Exact>,
                                       Exact>::ret exact_type;
        typedef typename hist_traits<exact_type>::cpt_type cpt_type;
        typedef typename hist_traits<exact_type>::value_type value_type;

        void
        clear()
        {
          this->exact().clear_impl();
        }
        const cpt_type
        operator[](const value_type &v)const
        {
          return this->exact().at(v);
        }
        cpt_type&
        operator[](const value_type &v)
        {
          return this->exact().at(v);
        }
        template <class I>
        void
        init(const oln::abstract::image<I> &img)
        {
          return this->exact().init_impl(img.exact());
        }
      };
    } // end of namespace abstract

    template<typename T,
             typename CPT = unsigned,
             class V2P = oln::convert::value_to_point<T>,
             class Exact = mlc::final>
    class histogram;

    template <typename T,
              typename CPT,
              class V2P,
              class Exact>
    struct hist_traits<histogram<T, CPT, V2P, Exact> >
    {
      typedef CPT cpt_type;             
      typedef T value_type;             
      typedef V2P value_to_point_type;  

      typedef typename value_to_point_type::result_type point_type;
      enum {dim = point_type::dim};     
      typedef typename dim_traits<dim, CPT>::img_type img_type;
    };

    template<typename T,
             typename CPT,
             class V2P,
             class Exact>
    class histogram: public abstract::histogram
      <typename mlc::exact_vt<histogram<T, CPT, V2P, Exact>, Exact>::ret>
    {
    public:
      typedef typename mlc::exact_vt<histogram<T, CPT, V2P, Exact>,
                                     Exact>::ret exact_type;
      typedef typename hist_traits<exact_type>::value_type value_type;
      typedef typename hist_traits<exact_type>::cpt_type cpt_type;
      typedef typename hist_traits<exact_type>::value_to_point_type
                                                value_to_point_type;
      typedef typename hist_traits<exact_type>::point_type point_type;
      enum {dim = hist_traits<exact_type>::dim};
      typedef typename hist_traits<exact_type>::img_type img_type;

      histogram(const value_to_point_type & c2p = value_to_point_type()):
        v2p_(c2p), img_(internal::img_max_size<value_type>()())
      {
        clear();
      }

      template <class I>
      histogram(const oln::abstract::image<I> & input,
                const value_to_point_type & v2p = value_to_point_type()):
        v2p_(v2p), img_(internal::img_max_size<value_type>()())
      {
        clear();
        init(input);
      }

      void
      clear_impl()
      {
        typename img_type::iter_type it(img_ );
        for_all(it)
        img_[it] = ntg_zero_val(cpt_type);
      }

      const cpt_type
      at(const T &v)const
      {
        return img_[v2p_(v)];
      }
      cpt_type&
      at(const value_type &v)
      {
        return img_[v2p_(v)];
      }
      template <class I>
      void
      init_impl(const oln::abstract::image<I> &img)
      {
        oln_iter_type(I) it_img(img);

        for_all(it_img)
        ++img_[v2p_(img[it_img])];
      }

      const img_type &
      image() const
      {
        return img_;
      }

    protected:
      const value_to_point_type v2p_;
      img_type img_;
    };

    template<class T>
    inline oln_value_type(T)
    min(const abstract::histogram<T>& hist)
    {
      typedef typename ntg_is_a(oln_value_type(T),
                                ntg::non_vectorial)::ensure_type ensure_type;

      oln_value_type(T) i;
      for (i = ntg_min_val(oln_value_type(T));
           i != ntg_max_val(oln_value_type(T));
           i = ntg::succ(i))
        if (hist[i] > ntg_zero_val(oln_cpt_type(T)))
          break;
      return i;
    }
    template<class T>
    inline oln_value_type(T)
    max(const abstract::histogram<T>& hist)
    {
      typedef typename ntg_is_a(oln_value_type(T),
                                ntg::non_vectorial)::ensure_type ensure_type;

      oln_value_type(T) i;
      for (i = ntg_max_val(oln_value_type(T));
           i != ntg_min_val(oln_value_type(T));
           i = ntg::pred(i))
        if (hist[i] > ntg_zero_val(oln_cpt_type(T)))
          break;
      return i;
    }

    template< typename T,
              typename CPT = unsigned,
              class V2P = convert::value_to_point<T>,
              class Exact = mlc::final>
    class histogram_minmax;

    template <typename T,
              typename CPT,
              class V2P,
              class Exact>
    struct hist_traits<histogram_minmax<T, CPT, V2P, Exact> >
      : public hist_traits<histogram<T, CPT, V2P, Exact> >
    {};
    template< typename T,
              typename CPT,
              class V2P,
              class Exact>
    class histogram_minmax : public histogram
      <T, CPT, V2P,
       typename mlc::exact_vt<histogram_minmax<T, CPT, V2P, Exact>,
                              Exact>::ret>
    {
    private:
      typedef typename ntg_is_a(T, ntg::non_vectorial)::ensure_type
                                                        ensure_type;
    public:
      typedef typename mlc::exact_vt<histogram_minmax<T, CPT, V2P, Exact>,
                                     Exact>::ret exact_type;
      typedef typename hist_traits<exact_type>::value_type value_type;
      typedef typename hist_traits<exact_type>::cpt_type cpt_type;
      typedef typename hist_traits<exact_type>::value_to_point_type
                                                 value_to_point_type;
      typedef typename hist_traits<exact_type>::point_type point_type;
      enum {dim = hist_traits<exact_type>::dim};
      typedef typename hist_traits<exact_type>::img_type img_type;
      typedef histogram<T, CPT, V2P, exact_type> upper_type;

      histogram_minmax(const value_to_point_type & v2p = value_to_point_type()) :
        upper_type(v2p),
        min_(ntg_min_val(value_type)), max_(ntg_max_val(value_type)) {}

      template <class I>
      histogram_minmax(const oln::abstract::image<I> & input,
                       const value_to_point_type & v2p = value_to_point_type()) :
        upper_type(input, v2p),
        min_(ntg_min_val(value_type)), max_(ntg_max_val(value_type)) {}

      const cpt_type
      at(const value_type& i) const
      {
        adjust(i);
        return img_[v2p_(i)];
      }

      cpt_type&
      at(const value_type& i)
      {
        adjust(i);
        return img_[v2p_(i)];
      }

      value_type
      min()
      {
        for (; min_ != ntg_max_val(value_type); min_ = ntg::succ(min_))
          if (img_[v2p_(min_)] > ntg_zero_val(cpt_type))
            break;
        return min_;
      }
      value_type
      max()
      {
        for (; max_ != ntg_min_val(value_type); max_ = ntg::pred(max_))
          if (img_[v2p_(max_)] > ntg_zero_val(cpt_type))
            break;
        return max_;
      }

    protected:
      void
      adjust(const value_type &idx)
      {
        if (idx > max_)
          max_ = idx;
        if (idx < min_)
          min_ = idx;
      }
      value_type min_, max_;    
    };


    template< typename T,
              typename CPT = unsigned,
              class V2P = convert::value_to_point<T>,
              class Exact = mlc::final>
    class histogram_min;

    template <typename T,
              typename CPT,
              class V2P,
              class Exact>
    struct hist_traits<histogram_min<T, CPT, V2P, Exact> >
      : public hist_traits<histogram<T, CPT, V2P, Exact> >
    {};

    template< typename T,
              typename CPT,
              class V2P,
              class Exact>
    class histogram_min : public histogram<T, CPT, V2P,
          typename mlc::exact_vt<histogram_min<T, CPT, V2P, Exact>,
                                 Exact>::ret>
    {
    private:
      typedef typename ntg_is_a(T, ntg::non_vectorial)::ensure_type
                                                         ensure_type;

    public:
      typedef typename mlc::exact_vt<histogram_min<T, CPT, V2P, Exact>,
                                     Exact>::ret exact_type;
      typedef typename hist_traits<exact_type>::value_type value_type;
      typedef typename hist_traits<exact_type>::cpt_type cpt_type;
      typedef typename hist_traits<exact_type>::value_to_point_type
                                                value_to_point_type;
      typedef typename hist_traits<exact_type>::point_type point_type;
      enum {dim = hist_traits<exact_type>::dim};
      typedef typename hist_traits<exact_type>::img_type img_type;
      typedef histogram<T, CPT, V2P, exact_type> upper_type;

      histogram_min(const value_to_point_type & v2p = value_to_point_type()) :
        upper_type(v2p), min_(ntg_min_val(value_type)) {}

      template <class I>
      histogram_min(const oln::abstract::image<I> & input,
                    const value_to_point_type & v2p = value_to_point_type()) :
        upper_type(input, v2p), min_(ntg_min_val(value_type)) {}

      const cpt_type
      at(const value_type& i) const
      {
        return img_[v2p_(i)];
      }

      cpt_type&
      at(const value_type& i)
      {
        adjust(i);
        return img_[v2p_(i)];
      }
      value_type
      min()
      {
        for (; min_ != ntg_max_val(value_type); min_ = succ(min_))
          if (img_[v2p_(min_)] > ntg_zero_val(cpt_type))
            break;
        return min_;
      }
      value_type
      res()
      {
        return min();
      }

    protected:
      void
      adjust(const value_type& idx)
      {
        if (idx < min_)
          min_ = idx;
      }
      value_type min_;  
    };

    template< typename T,
              typename CPT = unsigned,
              class V2P = convert::value_to_point<T>,
              class Exact = mlc::final>
    class histogram_max;

    template <typename T,
              typename CPT,
              class V2P,
              class Exact>
    struct hist_traits<histogram_max<T, CPT, V2P, Exact> >
      : public hist_traits<histogram<T, CPT, V2P, Exact> >
    {};

    template< typename T,
              typename CPT,
              class V2P,
              class Exact>
    class histogram_max : public histogram<T, CPT, V2P,
          typename mlc::exact_vt<histogram_max<T, CPT, V2P, Exact>,
                                 Exact>::ret>
    {
    private:
      typedef typename ntg_is_a(T, ntg::non_vectorial)::ensure_type
                                                        ensure_type;

    public:
      typedef typename mlc::exact_vt<histogram_max<T, CPT, V2P, Exact>,
                                     Exact>::ret exact_type;
      typedef typename hist_traits<exact_type>::value_type value_type;
      typedef typename hist_traits<exact_type>::cpt_type cpt_type;
      typedef typename hist_traits<exact_type>::value_to_point_type
                                                value_to_point_type;
      typedef typename hist_traits<exact_type>::point_type point_type;
      enum {dim = hist_traits<exact_type>::dim};
      typedef typename hist_traits<exact_type>::img_type img_type;
      typedef histogram<T, CPT, V2P, exact_type> upper_type;

      histogram_max(const value_to_point_type & v2p = value_to_point_type()) :
        upper_type(v2p),max_(ntg_max_val(value_type)) {}

      template <class I>
      histogram_max(const oln::abstract::image<I> & input,
                    const value_to_point_type & v2p = value_to_point_type()) :
        upper_type(input, v2p),max_(ntg_max_val(value_type)) {}

      const cpt_type
      at(const value_type& i) const
      {
        return img_[v2p_(i)];
      }

      cpt_type&
      at(const value_type& i)
      {
        adjust(i);
        return img_[v2p_(i)];
      }
      value_type
      max()
      {
        for (; max_ != ntg_min_val(value_type); max_ = ntg::pred(max_))
          if (img_[v2p_(max_)] > ntg_zero_val(cpt_type))
            break;
        return max_;
      }
      value_type
      res()
      {
        return max();
      }

    protected:

      void
      adjust(const value_type& idx)
      {
        if (idx > max_)
          max_ = idx;
      }
      value_type max_;  
    };

    template< typename T, typename CPT, class V2P, class Exact >
    inline T
    min(histogram_minmax<T, CPT, V2P, Exact>& hist)
    {
      return hist.min();
    }
    template< typename T, typename CPT, class V2P, class Exact >
    inline T
    min(histogram_min<T, CPT, V2P, Exact>& hist)
    {
      return hist.min();
    }
    template< typename T, typename CPT, class V2P, class Exact >
    inline T
    max(histogram_minmax<T, CPT, V2P, Exact>& hist)
    {
      return hist.max();
    }
    template< typename T, typename CPT, class V2P, class Exact >
    inline T
    max(histogram_max<T, CPT, V2P, Exact>& hist)
    {
      return hist.max();
    }
    template<class I>
    void
    distrib_sort(const oln::abstract::image<I>& im,
                 std::vector<oln_point_type(I)> &v)
    {
      typedef oln_value_type(I) val;

      typedef typename ntg_is_a(val, ntg::non_vectorial)::ensure_type
                                                         ensure_type;

      // check the size
      precondition(v.size() == im.npoints());

      // calculate the histogram of the image
      utils::histogram<val> histo(im);

      // Initialize the array of pointer to the point in the result.
      // With the histogram the number of each color can be deduced and
      // then it calculates an array of pointer for quick access to each
      // value of the image.
      const ntg_cumul_type(val) card = ntg_max_val(val)
                                        - ntg_min_val(val) + 1;
      std::vector<oln_point_type(I)* > ptr(card);
      ptr[0] = &(v[0]);
      for (ntg_cumul_type(val) i = 1; i < card; ++i)
        ptr[i] = ptr[i - 1] + histo[i - 1 + ntg_min_val(val)];

      // Now iterate on the image to sort point in the order of their
      // level
      oln_iter_type(I) p(im);
      for_all(p)
        *(ptr[unsigned(im[p] - ntg_min_val(val))]++) = p;
    }

    template<class I>
    void
    distrib_sort_inv(const oln::abstract::image<I>& im,
                     std::vector<oln_point_type(I)> &v)
    {
      typedef oln_value_type(I) val;

      typedef typename ntg_is_a(val, ntg::non_vectorial)::ensure_type
                                                        ensure_type;

      precondition(v.size() == im.npoints());

      utils::histogram<val> histo(im);

      const ntg_cumul_type(val) card = ntg_max_val(val)
                                        - ntg_min_val(val) + 1;
      std::vector<oln_point_type(I)* > ptr(card);
      ptr[card - 1] = &(v[0]);

      for (ntg_signed_cumul_type(val) i = card - 2; i >= 0; --i)
        ptr[i] = ptr[i + 1] + histo[i + 1 + ntg_min_val(val)];

      oln_iter_type(I) p(im);
      for_all(p)
        *(ptr[unsigned(im[p] - ntg_min_val(val))]++) = p;
    }

    template <bool reverse>
    struct select_distrib_sort
    {
      template <class I>
      void
      operator ()(const oln::abstract::image<I>& im,
                  std::vector<oln_point_type(I)> &v)
      {
        distrib_sort_inv(im, v);
      }
    };

    template <>
    struct select_distrib_sort<true>
    {
      template <class I>
      void
      operator ()(const oln::abstract::image<I>& im,
                  std::vector<oln_point_type(I)> &v)
      {
        distrib_sort(im, v);
      }
    };
  } // end of namespace utils

} // end of namespace oln

#endif // ! OLENA_UTILS_HISTOGRAM_HH

---