From patchwork Mon Mar 29 19:18:23 2021 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Jean-Michel Hautbois X-Patchwork-Id: 11777 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 19945C32F0 for ; Mon, 29 Mar 2021 19:18:41 +0000 (UTC) Received: from lancelot.ideasonboard.com (localhost [IPv6:::1]) by lancelot.ideasonboard.com (Postfix) with ESMTP id CC52168793; Mon, 29 Mar 2021 21:18:40 +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="n6JDQ0q7"; 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 9EE0968783 for ; Mon, 29 Mar 2021 21:18:35 +0200 (CEST) Received: from localhost.localdomain (unknown [IPv6:2a01:e0a:169:7140:9714:da21:50fd:f63f]) by perceval.ideasonboard.com (Postfix) with ESMTPSA id 4AF22503; Mon, 29 Mar 2021 21:18:35 +0200 (CEST) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/simple; d=ideasonboard.com; s=mail; t=1617045515; bh=4ugc+u64tJwtiF9ySV7Cyo9jk10r8fkAzax7dpg0aIE=; h=From:To:Cc:Subject:Date:In-Reply-To:References:From; b=n6JDQ0q7rvXdNQBE0xmzZ5YTmBOQe+R4DptCJRyN5e4Iyh01fLH29/E2PF7GsAxw8 8oFJ9JH4yibltB2+17bvGCWbEjIB1wboXQ88m9tifw1zydmmpCF6pPGKPCGQQuam+f bLDxTTIZqQ64JVKivqFGEt0wFGgme00JlAk4dEnQ= From: Jean-Michel Hautbois To: libcamera-devel@lists.libcamera.org Date: Mon, 29 Mar 2021 21:18:23 +0200 Message-Id: <20210329191826.77817-3-jeanmichel.hautbois@ideasonboard.com> X-Mailer: git-send-email 2.27.0 In-Reply-To: <20210329191826.77817-1-jeanmichel.hautbois@ideasonboard.com> References: <20210329191826.77817-1-jeanmichel.hautbois@ideasonboard.com> MIME-Version: 1.0 Subject: [libcamera-devel] [PATCH v3 2/5] 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 | 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 + +#include "histogram.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 possible the implementation of generic code + * to manage algorithms regardless of their specific type. + */ + +/** + * \brief Cumulative frequency up to a (fractional) point in a bin. + * \param[in] bin the number of bins + * \return The number of bins cumulated + */ +uint64_t Histogram::cumulativeFreq(double bin) const +{ + if (bin <= 0) + return 0; + else if (bin >= bins()) + return total(); + int b = (int)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 (optionnal if -1) + * \param[in] last high limit (optionnal if -1) + * \return The fractionnal bin of the point + */ +double Histogram::quantile(double q, int first, int last) const +{ + if (first == -1) + first = 0; + if (last == -1) + last = cumulative_.size() - 2; + assert(first <= last); + uint64_t items = 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] > items) + last = middle; + else + first = middle + 1; + } + assert(items >= cumulative_[first] && items <= cumulative_[last + 1]); + double frac = cumulative_[first + 1] == cumulative_[first] ? 0 + : (double)(items - 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 + * \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); + sumBinFreq += bin * freq; + 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..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 +#include +#include + +// A simple histogram class, for use in particular to find "quantiles" and +// averages between "quantiles". + +namespace libcamera { + +namespace ipa { + +class Histogram +{ +public: + template + /** + * \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 + */ + Histogram(T *histogram, int num) + { + assert(num); + cumulative_.reserve(num + 1); + cumulative_.push_back(0); + for (int i = 0; i < num; i++) + cumulative_.push_back(cumulative_.back() + + histogram[i]); + } + + /** + * \brief getter for number of bins + * \return number of bins + */ + uint32_t bins() const { return cumulative_.size() - 1; } + /** + * \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 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' ]) libipa_sources = files([ 'algorithm.cpp', + 'histogram.cpp' ]) libipa_includes = include_directories('..')