[libcamera-devel] [PATCH v4 2/4] WIP: ipa: ipu3: Add an histogram class
Kieran Bingham
kieran.bingham at ideasonboard.com
Mon Apr 12 14:21:03 CEST 2021
Hi Jean-Michel,
in $SUBJECT
s/an/a/
On 30/03/2021 22:12, Jean-Michel Hautbois wrote:
> This class will be used at least by AGC algorithm when quantiles are
> needed for example.
>
Is this really a Histogram class? Or is is a CumulativeFrequency class?
I may likely be mis-interpretting or just wrong - but I thought a
histogram stored values like:
value 0 1 2 3 4 5 6 7 8 9
count 5 0 3 5 6 9 2 0 2 5
Meaning that ... you can look up in the table to see that there are 5
occurrences of the value 9 in the dataset... whereas this stores:
value 0 1 2 3 4 5 6 7 8 9
count 5 8 8 13 19 28 30 30 32 37
Ok, so now I've drawn that out, I can see that the same information is
still there, as you can get the occurrences of any specific value by
subtracting from the previous 'bin'?
> Signed-off-by: Jean-Michel Hautbois <jeanmichel.hautbois at ideasonboard.com>
> ---
> src/ipa/libipa/histogram.cpp | 154 +++++++++++++++++++
> src/ipa/libipa/histogram.h | 40 +++++
> src/ipa/libipa/meson.build | 2 +
> src/ipa/raspberrypi/controller/histogram.hpp | 9 +-
> 4 files changed, 197 insertions(+), 8 deletions(-)
> 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..46fbb940
> --- /dev/null
> +++ b/src/ipa/libipa/histogram.cpp
> @@ -0,0 +1,154 @@
> +/* 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
> + *
> + * The Histogram class defines a standard interface for IPA algorithms. By
> + * abstracting histograms, it makes it possible to implement generic code
> + * to manage histograms regardless of their specific type.
I don't think this defines a standard interface for IPA algorithms ;)
I think we can drop that paragraph and keep the one below.
> + *
> + * 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 with a bin number of intervals
I suspect 'bin' was a previous value passed in here.
I think we should describe how data should be passed in.
I.e. I think perhaps it should be a pre-sorted histogram or something?
> + * \param[in] data a reference to the histogram
I don't think this is a reference anymore.
> + */
> +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 getter for number of bins
We don't normally reference them as 'getter's even if that's what they do.
To be consistent with other briefs, we should put something like:
\brief Retrieve the number of bins currently stored in the Histogram
(stored by, might be 'used by'?)
> + * \return Number of bins
> + */
> +/**
> + * \fn Histogram::total()
> + * \brief getter for number of values
Same here,
\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 upon which to cumulate
s/the/The/
(Capital letter to start after the parameter itself.)
Reading below, does it also mean this should say "up to which" rather
than "upon which"?
i.e.
upon which: to me, counts the values 'in' that bin.
up to which: to me, counts the values up to that one...
> + *
> + * With F(p) the cumulative frequency of the histogram, the value is 0 at
What is F(p) here?
> + * 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 cumulated frequency from 0 up to the specified bin
> + */
> +uint64_t Histogram::cumulativeFreq(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..dc7451aa
> --- /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 cumulativeFreq(double bin) const;
I'd make this cumulativeFrequency()
> + 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_;
I see this came from the RPi code.
Do we really store 64 bit values in here? or are they only 32bit? (or
smaller?)
In fact, I see we now construct with a Span<uint32_t> data, so
presumably this vector can be uint32_t.
We could template it to accept different sizes if that would help ...
but I think supporting 32 bits is probably fine if that's the span we
currently define....
> +};
> +
> +} /* 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('..')
> diff --git a/src/ipa/raspberrypi/controller/histogram.hpp b/src/ipa/raspberrypi/controller/histogram.hpp
> index 90f5ac78..fc236416 100644
> --- a/src/ipa/raspberrypi/controller/histogram.hpp
> +++ b/src/ipa/raspberrypi/controller/histogram.hpp
I'm not sure if the modifications to the RPi histogram below should be
in this patch.
It looks like they're unrelated to the actual code move?
Perhaps leave this out, and we can 'convert' RPi controller to use the
'generic' histogram separately?
> @@ -10,9 +10,6 @@
> #include <vector>
> #include <cassert>
>
> -// A simple histogram class, for use in particular to find "quantiles" and
> -// averages between "quantiles".
> -
> namespace RPiController {
>
> class Histogram
> @@ -29,12 +26,8 @@ public:
> }
> uint32_t Bins() const { return cumulative_.size() - 1; }
> uint64_t Total() const { return cumulative_[cumulative_.size() - 1]; }
> - // Cumulative frequency up to a (fractional) point in a bin.
> uint64_t CumulativeFreq(double bin) const;
> - // Return the (fractional) bin of the point q (0 <= q <= 1) through the
> - // histogram. Optionally provide limits to help.
> - double Quantile(double q, int first = -1, int last = -1) const;
> - // Return the average histogram bin value between the two quantiles.
> + Histogram::quantile(double q, uint32_t first = 0, uint32_t last = UINT_MAX) const;
> double InterQuantileMean(double q_lo, double q_hi) const;
>
> private:
>
--
Regards
--
Kieran
More information about the libcamera-devel
mailing list