From 3ebb692f323eaace79ae4932bd119df2de361650 Mon Sep 17 00:00:00 2001 From: Jean-Michel Hautbois Date: Tue, 13 Apr 2021 07:47:14 +0200 Subject: ipa: ipu3: Add a histogram class This class will be used at least by AGC algorithm when quantiles are needed for example. It stores a cumulative frequency histogram. Going from cumulative frequency back to per-bin values is a single subtraction, while going the other way is a loop. Signed-off-by: Jean-Michel Hautbois Reviewed-by: Kieran Bingham Tested-by: Jacopo Mondi Signed-off-by: Kieran Bingham --- src/ipa/libipa/histogram.cpp | 153 +++++++++++++++++++++++++++++++++++++++++++ src/ipa/libipa/histogram.h | 40 +++++++++++ src/ipa/libipa/meson.build | 2 + 3 files changed, 195 insertions(+) create mode 100644 src/ipa/libipa/histogram.cpp create mode 100644 src/ipa/libipa/histogram.h (limited to 'src') diff --git a/src/ipa/libipa/histogram.cpp b/src/ipa/libipa/histogram.cpp new file mode 100644 index 00000000..d4d7cfdf --- /dev/null +++ b/src/ipa/libipa/histogram.cpp @@ -0,0 +1,153 @@ +/* SPDX-License-Identifier: BSD-2-Clause */ +/* + * Copyright (C) 2019, Raspberry Pi (Trading) Limited + * + * histogram.cpp - histogram calculations + */ +#include "histogram.h" + +#include + +#include "libcamera/internal/log.h" + +/** + * \file histogram.h + * \brief Class to represent Histograms and manipulate them + */ + +namespace libcamera { + +namespace ipa { + +/** + * \class Histogram + * \brief The base class for creating histograms + * + * This class stores a cumulative frequency histogram, which is a mapping that + * counts the cumulative number of observations in all of the bins up to the + * specified bin. It can be used to find quantiles and averages between quantiles. + */ + +/** + * \brief Create a cumulative histogram + * \param[in] data A pre-sorted histogram to be passed + */ +Histogram::Histogram(Span data) +{ + cumulative_.reserve(data.size()); + cumulative_.push_back(0); + for (const uint32_t &value : data) + cumulative_.push_back(cumulative_.back() + value); +} + +/** + * \fn Histogram::bins() + * \brief Retrieve the number of bins currently used by the Histogram + * \return Number of bins + */ + +/** + * \fn Histogram::total() + * \brief Retrieve the total number of values in the data set + * \return Number of values + */ + +/** + * \brief Cumulative frequency up to a (fractional) point in a bin. + * \param[in] bin The bin up to which to cumulate + * + * With F(p) the cumulative frequency of the histogram, the value is 0 at + * the bottom of the histogram, and the maximum is the number of bins. + * The pixels are spread evenly throughout the “bin” in which they lie, so that + * F(p) is a continuous (monotonically increasing) function. + * + * \return The cumulative frequency from 0 up to the specified bin + */ +uint64_t Histogram::cumulativeFrequency(double bin) const +{ + if (bin <= 0) + return 0; + else if (bin >= bins()) + return total(); + int b = static_cast(bin); + return cumulative_[b] + + (bin - b) * (cumulative_[b + 1] - cumulative_[b]); +} + +/** + * \brief Return the (fractional) bin of the point through the histogram + * \param[in] q the desired point (0 <= q <= 1) + * \param[in] first low limit (default is 0) + * \param[in] last high limit (default is UINT_MAX) + * + * A quantile gives us the point p = Q(q) in the range such that a proportion + * q of the pixels lie below p. A familiar quantile is Q(0.5) which is the median + * of a distribution. + * + * \return The fractional bin of the point + */ +double Histogram::quantile(double q, uint32_t first, uint32_t last) const +{ + if (last == UINT_MAX) + last = cumulative_.size() - 2; + ASSERT(first <= last); + + uint64_t item = q * total(); + /* Binary search to find the right bin */ + while (first < last) { + int middle = (first + last) / 2; + /* Is it between first and middle ? */ + if (cumulative_[middle + 1] > item) + last = middle; + else + first = middle + 1; + } + ASSERT(item >= cumulative_[first] && item <= cumulative_[last + 1]); + + double frac; + if (cumulative_[first + 1] == cumulative_[first]) + frac = 0; + else + frac = (item - cumulative_[first]) / (cumulative_[first + 1] - cumulative_[first]); + return first + frac; +} + +/** + * \brief Calculate the mean between two quantiles + * \param[in] lowQuantile low Quantile + * \param[in] highQuantile high Quantile + * + * Quantiles are not ideal for metering as they suffer several limitations. + * Instead, a concept is introduced here: inter-quantile mean. + * It returns the mean of all pixels between lowQuantile and highQuantile. + * + * \return The mean histogram bin value between the two quantiles + */ +double Histogram::interQuantileMean(double lowQuantile, double highQuantile) const +{ + ASSERT(highQuantile > lowQuantile); + /* Proportion of pixels which lies below lowQuantile */ + double lowPoint = quantile(lowQuantile); + /* Proportion of pixels which lies below highQuantile */ + double highPoint = quantile(highQuantile, static_cast(lowPoint)); + double sumBinFreq = 0, cumulFreq = 0; + + for (double p_next = floor(lowPoint) + 1.0; + p_next <= ceil(highPoint); + lowPoint = p_next, p_next += 1.0) { + int bin = floor(lowPoint); + double freq = (cumulative_[bin + 1] - cumulative_[bin]) + * (std::min(p_next, highPoint) - lowPoint); + + /* Accumulate weigthed bin */ + sumBinFreq += bin * freq; + /* Accumulate weights */ + cumulFreq += freq; + } + /* add 0.5 to give an average for bin mid-points */ + return sumBinFreq / cumulFreq + 0.5; +} + +} /* namespace ipa */ + +} /* namespace libcamera */ diff --git a/src/ipa/libipa/histogram.h b/src/ipa/libipa/histogram.h new file mode 100644 index 00000000..e06f1884 --- /dev/null +++ b/src/ipa/libipa/histogram.h @@ -0,0 +1,40 @@ +/* SPDX-License-Identifier: BSD-2-Clause */ +/* + * Copyright (C) 2019, Raspberry Pi (Trading) Limited + * + * histogram.h - histogram calculation interface + */ +#ifndef __LIBCAMERA_IPA_LIBIPA_HISTOGRAM_H__ +#define __LIBCAMERA_IPA_LIBIPA_HISTOGRAM_H__ + +#include +#include +#include + +#include + +#include + +namespace libcamera { + +namespace ipa { + +class Histogram +{ +public: + Histogram(Span data); + size_t bins() const { return cumulative_.size() - 1; } + uint64_t total() const { return cumulative_[cumulative_.size() - 1]; } + uint64_t cumulativeFrequency(double bin) const; + double quantile(double q, uint32_t first = 0, uint32_t last = UINT_MAX) const; + double interQuantileMean(double lowQuantile, double hiQuantile) const; + +private: + std::vector cumulative_; +}; + +} /* namespace ipa */ + +} /* namespace libcamera */ + +#endif /* __LIBCAMERA_IPA_LIBIPA_HISTOGRAM_H__ */ diff --git a/src/ipa/libipa/meson.build b/src/ipa/libipa/meson.build index 1819711d..038fc490 100644 --- a/src/ipa/libipa/meson.build +++ b/src/ipa/libipa/meson.build @@ -2,10 +2,12 @@ libipa_headers = files([ 'algorithm.h', + 'histogram.h' ]) libipa_sources = files([ 'algorithm.cpp', + 'histogram.cpp' ]) libipa_includes = include_directories('..') -- cgit v1.2.1