[libcamera-devel,v5,2/4] ipa: ipu3: Add a histogram class
diff mbox series

Message ID 20210416074909.24218-3-jeanmichel.hautbois@ideasonboard.com
State Accepted
Headers show
Series
  • Implement IPA algorithms and demo with IPU3
Related show

Commit Message

Jean-Michel Hautbois April 16, 2021, 7:49 a.m. UTC 
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 <jeanmichel.hautbois@ideasonboard.com>
---
 src/ipa/libipa/histogram.cpp | 150 +++++++++++++++++++++++++++++++++++
 src/ipa/libipa/histogram.h   |  40 ++++++++++
 src/ipa/libipa/meson.build   |   2 +
 3 files changed, 192 insertions(+)
 create mode 100644 src/ipa/libipa/histogram.cpp
 create mode 100644 src/ipa/libipa/histogram.h

Comments

Kieran Bingham April 19, 2021, 10 a.m. UTC | #1 
Hi JM

On 16/04/2021 08:49, Jean-Michel Hautbois wrote:
> 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 <jeanmichel.hautbois@ideasonboard.com>
> ---
>  src/ipa/libipa/histogram.cpp | 150 +++++++++++++++++++++++++++++++++++
>  src/ipa/libipa/histogram.h   |  40 ++++++++++
>  src/ipa/libipa/meson.build   |   2 +
>  3 files changed, 192 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..b92d8305
> --- /dev/null
> +++ b/src/ipa/libipa/histogram.cpp
> @@ -0,0 +1,150 @@
> +/* SPDX-License-Identifier: BSD-2-Clause */
> +/*
> + * Copyright (C) 2019, Raspberry Pi (Trading) Limited
> + *
> + * histogram.cpp - histogram calculations
> + */
> +#include "histogram.h"
> +
> +#include <cmath>
> +
> +#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<uint32_t> data)
> +{
> +	cumulative_.reserve(data.size());
> +	cumulative_.push_back(0);
> +	for (const uint32_t &value : data)
> +		cumulative_.push_back(cumulative_.back() + value);
> +}

New line here.

> +/**
> + * \fn Histogram::bins()
> + * \brief Retrieve the number of bins currently used by the Histogram
> + * \return Number of bins
> + */

and here ...

> +/**
> + * \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<int32_t>(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)

I wonder if we should use std::numeric_limits for this.

But that sould be a change on top anyway, this is functional, and we
have other uses of UINT_MAX, so if we want to encourage/enforce
numeric_limits, then that should all be done in a full sweep, with an
addition to checkstyle to highlight if it's used.


> +		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<uint32_t>(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);

Long line here could be split ... ?

> +		double freq = (cumulative_[bin + 1] - cumulative_[bin])
			    * (std::min(p_next, highPoint) - lowPoint);

I wonder if there's a way to get clang-format to be better tuned for our
desired line lengths.


Reviewed-by: Kieran Bingham <kieran.bingham@ideasonboard.com>



> +
> +		/* 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 <assert.h>
> +#include <limits.h>
> +#include <stdint.h>
> +
> +#include <vector>
> +
> +#include <libcamera/span.h>
> +
> +namespace libcamera {
> +
> +namespace ipa {
> +
> +class Histogram
> +{
> +public:
> +	Histogram(Span<uint32_t> 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<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 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('..')
> 
> 
> _______________________________________________
> libcamera-devel mailing list
> libcamera-devel@lists.libcamera.org
> https://lists.libcamera.org/listinfo/libcamera-devel
>

Patch
diff mbox series 

diff --git a/src/ipa/libipa/histogram.cpp b/src/ipa/libipa/histogram.cpp
new file mode 100644
index 00000000..b92d8305
--- /dev/null
+++ b/src/ipa/libipa/histogram.cpp
@@ -0,0 +1,150 @@ 
+/* SPDX-License-Identifier: BSD-2-Clause */
+/*
+ * Copyright (C) 2019, Raspberry Pi (Trading) Limited
+ *
+ * histogram.cpp - histogram calculations
+ */
+#include "histogram.h"
+
+#include <cmath>
+
+#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<uint32_t> 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<int32_t>(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<uint32_t>(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 <assert.h>
+#include <limits.h>
+#include <stdint.h>
+
+#include <vector>
+
+#include <libcamera/span.h>
+
+namespace libcamera {
+
+namespace ipa {
+
+class Histogram
+{
+public:
+	Histogram(Span<uint32_t> 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<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 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('..')