CRNHistogram.h

Go to the documentation of this file.

/* Copyright 2006-2016 Yann LEYDIER, INSA-Lyon, CoReNum, Université Paris Descartes, ENS-Lyon
 *
 * This file is part of libcrn.
 *
 * libcrn is free software: you can redistribute it and/or modify
 * it under the terms of the GNU Lesser General Public License as published by
 * the Free Software Foundation, either version 3 of the License, or
 * (at your option) any later version.
 *
 * libcrn 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 Lesser General Public License for more details.
 *
 * You should have received a copy of the GNU Lesser General Public License
 * along with libcrn.  If not, see <http://www.gnu.org/licenses/>.
 *
 * file: SHistogram.h
 * \author Yann LEYDIER, Jean DUONG, Asma OUJI
 */

#ifndef CRNHISTOGRAM_HEADER
#define CRNHISTOGRAM_HEADER

#include <CRNString.h>
#include <CRNStatistics/CRNHistogramPtr.h>
#include <CRNImage/CRNImageFormats.h>
#include <cmath>

namespace crn
{
    /****************************************************************************/
    class Histogram: public Object
    {
        public:
            enum class DesignHeuristic {CUSTOM, SQUARE_ROOT, STURGES, SCOTT, FREEDMAN};

            Histogram():bins(1, 0),compression(1) { }
            Histogram(size_t s, unsigned int v = 0);
            Histogram(const Histogram &src, unsigned int c = 1u);

            /*****************************************************************************/
            template<typename ITER> Histogram(ITER it_begin, ITER it_end, DesignHeuristic m = DesignHeuristic::STURGES, size_t nb_bins = (size_t)1)
            {
                double delta;
                double left_bound = std::numeric_limits<double>::infinity();
                double right_bound = -std::numeric_limits<double>::infinity();

                size_t cardinal = 0;

                // First step : check data

                for (auto it = it_begin; it != it_end; ++it)
                {
                    double v = it->first;
                    size_t c = it->second;

                    if (v < left_bound)
                        left_bound = v;

                    if (v > right_bound)
                        right_bound = v;

                    cardinal += c;
                }

                double range = right_bound - left_bound;

                // Second step : build histogram

                if (m == DesignHeuristic::SQUARE_ROOT)
                {
                    nb_bins = (size_t) sqrt(double(cardinal));
                    delta = range / double(nb_bins);
                }
                else if (m == DesignHeuristic::STURGES)
                {
                    nb_bins = 1 + (size_t) (log(double(cardinal)) / log(2.0));
                    delta = range / double(nb_bins);
                }
                else if (m == DesignHeuristic::SCOTT)
                {
                    double m = 0.0;
                    double v = 0.0;

                    for (auto it = it_begin; it != it_end; ++it)
                        m += it->first * ((double)it->second / (double)cardinal);

                    for (auto it = it_begin; it != it_end; ++it)
                    {
                        double diff = it->first - m;

                        v += (diff * diff) * ((double)it->second / (double)cardinal);
                    }

                    delta = 3.5 * sqrt(v) / pow(double(cardinal), (1.0 / 3.0));
                    nb_bins = 1 + (size_t) ((right_bound - left_bound) / delta);
                }
                else
                {
                    delta = range / double(nb_bins);
                }

                ++nb_bins; // Add one safety bin !

                bins = std::vector<unsigned int>(nb_bins + 1, 0u);
                compression = 1;

                // Third step : fill histogram

                if (nb_bins == 1) // trivial case
                    SetBin(0, (unsigned int)cardinal);
                else
                {
                    for (auto it = it_begin; it != it_end; ++it)
                    {
                        size_t id = (size_t)((it->first - left_bound) / delta);

                        if (id < nb_bins)
                            IncBin(id, it->second);
                    }
                }
            }

            Histogram& operator=(const Histogram&) = delete;
            Histogram(Histogram&&) = default;
            Histogram& operator=(Histogram&&) = default;

            ~Histogram();

            size_t Size() const noexcept {return bins.size();}
            unsigned int* GetBins() {return &(bins.front());}
            const unsigned int* GetBins() const {return &(bins.front());}

            void SetBin(size_t k, unsigned int v);

            void IncBin(size_t k, unsigned int i = 1u);

            unsigned int GetBin(size_t k) const;

            unsigned int& operator[](size_t k) { return bins[k]; }
            const unsigned int& operator[](size_t k) const { return bins[k]; }

            unsigned int CumulateBins() const;

            double Mean() const;

            double Variance(double m) const;
            double Deviation(double m) const {return sqrt(Variance(m));}

            double Variance() const;
            double Deviation() const {return sqrt(Variance());}

            unsigned int Max() const;

            unsigned int Min() const;

            size_t Argmax() const;

            size_t Argmin() const;

            void SetCeiling(unsigned int m);

            void ScaleMaxTo(unsigned int m);

            void AverageSmoothing(size_t d);
            void CircularAverageSmoothing(size_t d);

            std::vector<size_t> Modes() const;
            std::vector<size_t> StableModes() const;

            Histogram MakeIntersection(const Histogram &h) const;

            double IntersectionDivergence(const Histogram &h) const;

            double Correlation(const Histogram &h) const;

            double Chi2(const Histogram &h) const;

            double MinkowskiDistance(const Histogram &h, double r) const;

            double JeffreyDivergence(const Histogram &h) const;

            double MatchDistance(const Histogram &h) const;

            double KolmogorovSmirnovDistance(const Histogram &h) const;

            double EMD(const Histogram &h) const;

            double CEMD(const Histogram &h) const;

            void Append(const Histogram &h);

            void Resize(size_t newsize);

            String ToString() const;

            ImageBW MakeImageBW(size_t height) const;

            ImageBW MakeRadialImageBW(size_t radius) const;

            void Cumulate();

            size_t Fisher() const;

            size_t EntropyThreshold() const;

            double Entropy() const;

            size_t MedianValue() const;

            Histogram MakePopulationHistogram() const;

            std::vector<unsigned int> Std() && { return std::move(bins); }

            void Deserialize(xml::Element &el);
            xml::Element Serialize(xml::Element &parent) const;

        private:
            using datatype = std::vector<unsigned int>; 
            datatype bins; 
            unsigned int compression; 
            CRN_DECLARE_CLASS_CONSTRUCTOR(Histogram)
            CRN_SERIALIZATION_CONSTRUCTOR(Histogram)
    };
    template<> struct IsSerializable<Histogram> : public std::true_type {};
    template<> struct IsClonable<Histogram> : public std::true_type {};
    inline double Distance(const Histogram &h1, const Histogram &h2) { return h1.MinkowskiDistance(h2, 1); }
    template<> struct IsMetric<Histogram> : public std::true_type {};


    inline size_t Size(const Histogram &h) noexcept { return h.Size(); }
}
#endif