From patchwork Tue Mar 30 21:12:08 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: 11800 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 B0FDFC0DA3 for ; Tue, 30 Mar 2021 21:12:21 +0000 (UTC) Received: from lancelot.ideasonboard.com (localhost [IPv6:::1]) by lancelot.ideasonboard.com (Postfix) with ESMTP id 565006878B; Tue, 30 Mar 2021 23:12:21 +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="MEY3Zri9"; dkim-atps=neutral Received: from perceval.ideasonboard.com (perceval.ideasonboard.com [IPv6:2001:4b98:dc2:55:216:3eff:fef7:d647]) by lancelot.ideasonboard.com (Postfix) with ESMTPS id AABFD602D2 for ; Tue, 30 Mar 2021 23:12:18 +0200 (CEST) Received: from localhost.localdomain (unknown [IPv6:2a01:e0a:169:7140:40dc:d947:395c:88d2]) by perceval.ideasonboard.com (Postfix) with ESMTPSA id 0A2B4102; Tue, 30 Mar 2021 23:12:18 +0200 (CEST) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/simple; d=ideasonboard.com; s=mail; t=1617138738; bh=I5Ut3x5rARrfmv6+wtRztv9qaZu1DOsFyvwcBBXMQR8=; h=From:To:Cc:Subject:Date:In-Reply-To:References:From; b=MEY3Zri9528QJICClhef+fmS2rt8SMCcify0PKWWyssiXTz1xqT/kmjQc9rPXb3ch 62PAP0DL/RDu8eGiihVrKYsPpELPVzjFL6OTuCWn16q+BLmkC6Lu+JdCPg4kVsyEm5 veQ0YBepfpAdsAEGq4rlZum6Pq+PL0kkxMsZza9k= From: Jean-Michel Hautbois To: libcamera-devel@lists.libcamera.org Date: Tue, 30 Mar 2021 23:12:08 +0200 Message-Id: <20210330211210.194806-3-jeanmichel.hautbois@ideasonboard.com> X-Mailer: git-send-email 2.27.0 In-Reply-To: <20210330211210.194806-1-jeanmichel.hautbois@ideasonboard.com> References: <20210330211210.194806-1-jeanmichel.hautbois@ideasonboard.com> MIME-Version: 1.0 Subject: [libcamera-devel] [PATCH v4 2/4] WIP: ipa: ipu3: Add an 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. Signed-off-by: Jean-Michel Hautbois --- 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 + +#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. + * + * 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 + * \param[in] data a reference to the histogram + */ +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 getter for number of bins + * \return Number of bins + */ +/** + * \fn Histogram::total() + * \brief getter for number of values + * \return Number of values + */ + +/** + * \brief Cumulative frequency up to a (fractional) point in a bin. + * \param[in] bin the bin upon 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 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(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..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 +#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 cumulativeFreq(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('..') 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 @@ -10,9 +10,6 @@ #include #include -// 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: