From patchwork Thu Apr 22 05:18:55 2021 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 8bit X-Patchwork-Submitter: Jean-Michel Hautbois X-Patchwork-Id: 12061 Return-Path: X-Original-To: parsemail@patchwork.libcamera.org Delivered-To: parsemail@patchwork.libcamera.org Received: from lancelot.ideasonboard.com (lancelot.ideasonboard.com [92.243.16.209]) by patchwork.libcamera.org (Postfix) with ESMTPS id F161ABDB15 for ; Thu, 22 Apr 2021 05:19:03 +0000 (UTC) Received: from lancelot.ideasonboard.com (localhost [IPv6:::1]) by lancelot.ideasonboard.com (Postfix) with ESMTP id 4AAD568859; Thu, 22 Apr 2021 07:19:03 +0200 (CEST) Authentication-Results: lancelot.ideasonboard.com; dkim=fail reason="signature verification failed" (1024-bit key; unprotected) header.d=ideasonboard.com header.i=@ideasonboard.com header.b="OSSWBhIO"; dkim-atps=neutral Received: from perceval.ideasonboard.com (perceval.ideasonboard.com [213.167.242.64]) by lancelot.ideasonboard.com (Postfix) with ESMTPS id 00F456884B for ; Thu, 22 Apr 2021 07:19:01 +0200 (CEST) Received: from localhost.localdomain (unknown [IPv6:2a01:e0a:169:7140:e96c:3f42:9018:e1b2]) by perceval.ideasonboard.com (Postfix) with ESMTPSA id 89CC29AA; Thu, 22 Apr 2021 07:19:00 +0200 (CEST) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/simple; d=ideasonboard.com; s=mail; t=1619068740; bh=vBlyRNe1V5PcVhHPCjrd/2ygKuUdp2VPbZTr6cD9jvs=; h=From:To:Cc:Subject:Date:In-Reply-To:References:From; b=OSSWBhIOaHaPGBzJYE8xkDIedtyBiOdrLZ/4w6h8bp30ff9d5V+Q2HBz8zOSEnNnX 1QmO/MsUtGrUgjrFevepGFGdJioZXHzmiCSFTPW0VCy4V9LrmcfrYkgf8wtUcIGMiP /fZHUgbccxf4x5BErgRzpNTrkx4sqRAod39CG77k= From: Jean-Michel Hautbois To: libcamera-devel@lists.libcamera.org Date: Thu, 22 Apr 2021 07:18:55 +0200 Message-Id: <20210422051857.20594-3-jeanmichel.hautbois@ideasonboard.com> X-Mailer: git-send-email 2.27.0 In-Reply-To: <20210422051857.20594-1-jeanmichel.hautbois@ideasonboard.com> References: <20210422051857.20594-1-jeanmichel.hautbois@ideasonboard.com> MIME-Version: 1.0 Subject: [libcamera-devel] [PATCH v6 2/4] ipa: ipu3: Add a histogram class X-BeenThere: libcamera-devel@lists.libcamera.org X-Mailman-Version: 2.1.29 Precedence: list List-Id: List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , Errors-To: libcamera-devel-bounces@lists.libcamera.org Sender: "libcamera-devel" 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 --- 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 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('..')