[libcamera-devel] [PATCH v3 2/5] ipa: ipu3: Add an histogram class

[Jean-Michel Hautbois]

This class will be used at least by AGC algorithm when quantiles are
needed for example.

Signed-off-by: Jean-Michel Hautbois <jeanmichel.hautbois at ideasonboard.com>
---
 src/ipa/libipa/histogram.cpp | 102 +++++++++++++++++++++++++++++++++++
 src/ipa/libipa/histogram.h   |  62 +++++++++++++++++++++
 src/ipa/libipa/meson.build   |   2 +
 3 files changed, 166 insertions(+)
 create mode 100644 src/ipa/libipa/histogram.cpp
 create mode 100644 src/ipa/libipa/histogram.h

diff --git a/src/ipa/libipa/histogram.cpp b/src/ipa/libipa/histogram.cpp
new file mode 100644
index 00000000..bea52687
--- /dev/null
+++ b/src/ipa/libipa/histogram.cpp
@@ -0,0 +1,102 @@
+/* SPDX-License-Identifier: BSD-2-Clause */
+/*
+ * Copyright (C) 2019, Raspberry Pi (Trading) Limited
+ *
+ * histogram.cpp - histogram calculations
+ */
+#include <math.h>
+
+#include "histogram.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
+ *
+ * The Histogram class defines a standard interface for IPA algorithms. By
+ * abstracting histograms, it makes possible the implementation of generic code
+ * to manage algorithms regardless of their specific type.
+ */
+
+/**
+ * \brief Cumulative frequency up to a (fractional) point in a bin.
+ * \param[in] bin the number of bins
+ * \return The number of bins cumulated
+ */
+uint64_t Histogram::cumulativeFreq(double bin) const
+{
+	if (bin <= 0)
+		return 0;
+	else if (bin >= bins())
+		return total();
+	int b = (int)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 (optionnal if -1)
+ * \param[in] last high limit (optionnal if -1)
+ * \return The fractionnal bin of the point
+ */
+double Histogram::quantile(double q, int first, int last) const
+{
+	if (first == -1)
+		first = 0;
+	if (last == -1)
+		last = cumulative_.size() - 2;
+	assert(first <= last);
+	uint64_t items = 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] > items)
+			last = middle;
+		else
+			first = middle + 1;
+	}
+	assert(items >= cumulative_[first] && items <= cumulative_[last + 1]);
+	double frac = cumulative_[first + 1] == cumulative_[first] ? 0
+								   : (double)(items - 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
+ * \return The average histogram bin value between the two quantiles
+ */
+double Histogram::interQuantileMean(double lowQuantile, double highQuantile) const
+{
+	assert(highQuantile > lowQuantile);
+	double lowPoint = quantile(lowQuantile);
+	double highPoint = quantile(highQuantile, (int)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);
+		sumBinFreq += bin * freq;
+		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..a610f675
--- /dev/null
+++ b/src/ipa/libipa/histogram.h
@@ -0,0 +1,62 @@
+/* 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 <assert.h>
+#include <stdint.h>
+#include <vector>
+
+// A simple histogram class, for use in particular to find "quantiles" and
+// averages between "quantiles".
+
+namespace libcamera {
+
+namespace ipa {
+
+class Histogram
+{
+public:
+	template<typename T>
+	/**
+	 * \brief Create a cumulative histogram with a bin number of intervals
+	 * \param[in] histogram a reference to the histogram
+	 * \param[in] num the number of bins
+ 	*/
+	Histogram(T *histogram, int num)
+	{
+		assert(num);
+		cumulative_.reserve(num + 1);
+		cumulative_.push_back(0);
+		for (int i = 0; i < num; i++)
+			cumulative_.push_back(cumulative_.back() +
+					      histogram[i]);
+	}
+
+	/**
+	 * \brief getter for number of bins
+	 * \return number of bins
+	 */
+	uint32_t bins() const { return cumulative_.size() - 1; }
+	/**
+	 * \brief getter for number of values
+	 * \return number of values
+	 */
+	uint64_t total() const { return cumulative_[cumulative_.size() - 1]; }
+	uint64_t cumulativeFreq(double bin) const;
+	double quantile(double q, int first = -1, int last = -1) const;
+	double interQuantileMean(double lowQuantile, double hiQuantile) const;
+
+private:
+	std::vector<uint64_t> 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 585d02a3..53edeef9 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('..')
-- 
2.27.0