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

11777 diff mbox series

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

Signed-off-by: Jean-Michel Hautbois <jeanmichel.hautbois@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

Hi Jean-Michel,

Thank you for the patch.

On Mon, Mar 29, 2021 at 09:18:23PM +0200, Jean-Michel Hautbois wrote:
> This class will be used at least by AGC algorithm when quantiles are
> needed for example.
> 
> Signed-off-by: Jean-Michel Hautbois <jeanmichel.hautbois@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>

<cmath> (and std:: functions below) as explained in
Documentation/coding-style.rst.

> +
> +#include "histogram.h"

Documentation/coding-style.rst:

"For .cpp files, if the file implements an API declared in a header
file, that header file shall be included first in order to ensure it is
self-contained."

histogram.h should thus go first.

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

s/makes possible the implementation of/makes it possible to implement/

> + * to manage algorithms regardless of their specific type.

Did you mean histograms instead of algorithms here ?

More information is needed here, to explain what the class does. In
particular, despite its name, this class doesn't store a histogram, so
that can be confusing.

> + */
> +
> +/**
> + * \brief Cumulative frequency up to a (fractional) point in a bin.
> + * \param[in] bin the number of bins

I don't think this parameter stores the number of bins.

> + * \return The number of bins cumulated

The functions also need better documentation. The reader needs to be
able to understand what the function does and how to use it by reading
the documentation, without reading the code.

One important piece of information here is how the function assumes a
uniform distribution of values within a bin. I think that's an
acceptable compromise, but it should be documented.

The functions below also need better documentation, as they're more
difficult to understand.

> + */
> +uint64_t Histogram::cumulativeFreq(double bin) const
> +{
> +	if (bin <= 0)
> +		return 0;
> +	else if (bin >= bins())
> +		return total();
> +	int b = (int)bin;

Please use C++-style casts (static_cast<int> in this case).

> +	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)

s/optionnal/optional/

> + * \param[in] last high limit (optionnal if -1)
> + * \return The fractionnal bin of the point

s/fractionnal/fractional/

> + */
> +double Histogram::quantile(double q, int first, int last) const
> +{
> +	if (first == -1)
> +		first = 0;

Why can't we then use 0 as the default value for first ? We could then
make it an unsigned int.

> +	if (last == -1)
> +		last = cumulative_.size() - 2;

And you can use UINT_MAX as the default value for max, which will also
allow making it an unsigned int. That way we won't risk the values being
negative.

> +	assert(first <= last);
> +	uint64_t items = q * total();

items or item ?

> +	/* 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]);

You should use ASSERT(), defined in internal/log.h, it will print a
backtrace.

> +	double frac = cumulative_[first + 1] == cumulative_[first] ? 0
> +								   : (double)(items - cumulative_[first]) /
> +									     (cumulative_[first + 1] - cumulative_[first]);

Please rework the code to avoid long lines. You can align the ? or :
with the = if it helps.

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

You can align the * with the =

> +		sumBinFreq += bin * freq;
> +		cumulFreq += freq;
> +	}
> +	/* add 0.5 to give an average for bin mid-points */
> +	return sumBinFreq / cumulFreq + 0.5;

The implementation needs more comments too, it's not trivial.

> +}
> +
> +} /* 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".

We use C-style comments, and avoid comments in header files. You can
drop this one.

> +
> +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
> + 	*/

This belongs to the .cpp file, even for inline functions. There are
plenty of examples in libcamera.

> +	Histogram(T *histogram, int num)

I'd rename histogram to data.

Instead of passing a pointer and a number of elements separately, you
should use a Span<T>. And as the data shouldn't be modified, it should
be a Span<const T>.

> +	{
> +		assert(num);
> +		cumulative_.reserve(num + 1);
> +		cumulative_.push_back(0);
> +		for (int i = 0; i < num; i++)
> +			cumulative_.push_back(cumulative_.back() +
> +					      histogram[i]);

		for (const T &value : data)
			cumulative_.push_back(cumulative_.back() + value);

> +	}

And the constructor shouldn't be inline anyway, as it's not trivial.

> +
> +	/**
> +	 * \brief getter for number of bins
> +	 * \return number of bins
> +	 */

This comment, as well as the next one, also belong to the .cpp file.

> +	uint32_t bins() const { return cumulative_.size() - 1; }

A size is better represented by a size_t than a uin32_t.

> +	/**
> +	 * \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'

4 spaces.

>  ])
>  
>  libipa_sources = files([
>      'algorithm.cpp',
> +    'histogram.cpp'
>  ])
>  
>  libipa_includes = include_directories('..')