[{"id":16343,"web_url":"https://patchwork.libcamera.org/comment/16343/","msgid":"<053465b1-9a58-eab7-0412-abf3754133fe@ideasonboard.com>","date":"2021-04-19T10:00:17","subject":"Re: [libcamera-devel] [PATCH v5 2/4] ipa: ipu3: Add a histogram\n\tclass","submitter":{"id":4,"url":"https://patchwork.libcamera.org/api/people/4/","name":"Kieran Bingham","email":"kieran.bingham@ideasonboard.com"},"content":"Hi JM\n\nOn 16/04/2021 08:49, Jean-Michel Hautbois wrote:\n> This class will be used at least by AGC algorithm when quantiles are\n> needed for example. It stores a cumulative frequency histogram. Going from\n> cumulative frequency back to per-bin values is a single subtraction, while\n> going the other way is a loop.\n> \n> Signed-off-by: Jean-Michel Hautbois \n> ---\n> src/ipa/libipa/histogram.cpp | 150 +++++++++++++++++++++++++++++++++++\n> src/ipa/libipa/histogram.h | 40 ++++++++++\n> src/ipa/libipa/meson.build | 2 +\n> 3 files changed, 192 insertions(+)\n> create mode 100644 src/ipa/libipa/histogram.cpp\n> create mode 100644 src/ipa/libipa/histogram.h\n> \n> diff --git a/src/ipa/libipa/histogram.cpp b/src/ipa/libipa/histogram.cpp\n> new file mode 100644\n> index 00000000..b92d8305\n> --- /dev/null\n> +++ b/src/ipa/libipa/histogram.cpp\n> @@ -0,0 +1,150 @@\n> +/* SPDX-License-Identifier: BSD-2-Clause */\n> +/*\n> + * Copyright (C) 2019, Raspberry Pi (Trading) Limited\n> + *\n> + * histogram.cpp - histogram calculations\n> + */\n> +#include \"histogram.h\"\n> +\n> +#include \n> +\n> +#include \"libcamera/internal/log.h\"\n> +\n> +/**\n> + * \\file histogram.h\n> + * \\brief Class to represent Histograms and manipulate them\n> + */\n> +\n> +namespace libcamera {\n> +\n> +namespace ipa {\n> +\n> +/**\n> + * \\class Histogram\n> + * \\brief The base class for creating histograms\n> + *\n> + * This class stores a cumulative frequency histogram, which is a mapping that\n> + * counts the cumulative number of observations in all of the bins up to the\n> + * specified bin. It can be used to find quantiles and averages between quantiles.\n> + */\n> +\n> +/**\n> + * \\brief Create a cumulative histogram\n> + * \\param[in] data A pre-sorted histogram to be passed\n> + */\n> +Histogram::Histogram(Span data)\n> +{\n> +\tcumulative_.reserve(data.size());\n> +\tcumulative_.push_back(0);\n> +\tfor (const uint32_t &value : data)\n> +\t\tcumulative_.push_back(cumulative_.back() + value);\n> +}\n\nNew line here.\n\n> +/**\n> + * \\fn Histogram::bins()\n> + * \\brief Retrieve the number of bins currently used by the Histogram\n> + * \\return Number of bins\n> + */\n\nand here ...\n\n> +/**\n> + * \\fn Histogram::total()\n> + * \\brief Retrieve the total number of values in the data set\n> + * \\return Number of values\n> + */\n> +\n> +/**\n> + * \\brief Cumulative frequency up to a (fractional) point in a bin.\n> + * \\param[in] bin The bin up to which to cumulate\n> + *\n> + * With F(p) the cumulative frequency of the histogram, the value is 0 at\n> + * the bottom of the histogram, and the maximum is the number of bins.\n> + * The pixels are spread evenly throughout the “bin” in which they lie, so that\n> + * F(p) is a continuous (monotonically increasing) function.\n> + *\n> + * \\return The cumulative frequency from 0 up to the specified bin\n> + */\n> +uint64_t Histogram::cumulativeFrequency(double bin) const\n> +{\n> +\tif (bin <= 0)\n> +\t\treturn 0;\n> +\telse if (bin >= bins())\n> +\t\treturn total();\n> +\tint b = static_cast(bin);\n> +\treturn cumulative_[b] +\n> +\t (bin - b) * (cumulative_[b + 1] - cumulative_[b]);\n> +}\n> +\n> +/**\n> + * \\brief Return the (fractional) bin of the point through the histogram\n> + * \\param[in] q the desired point (0 <= q <= 1)\n> + * \\param[in] first low limit (default is 0)\n> + * \\param[in] last high limit (default is UINT_MAX)\n> + *\n> + * A quantile gives us the point p = Q(q) in the range such that a proportion\n> + * q of the pixels lie below p. A familiar quantile is Q(0.5) which is the median\n> + * of a distribution.\n> + *\n> + * \\return The fractional bin of the point\n> + */\n> +double Histogram::quantile(double q, uint32_t first, uint32_t last) const\n> +{\n> +\tif (last == UINT_MAX)\n\nI wonder if we should use std::numeric_limits for this.\n\nBut that sould be a change on top anyway, this is functional, and we\nhave other uses of UINT_MAX, so if we want to encourage/enforce\nnumeric_limits, then that should all be done in a full sweep, with an\naddition to checkstyle to highlight if it's used.\n\n\n> +\t\tlast = cumulative_.size() - 2;\n> +\tASSERT(first <= last);\n> +\n> +\tuint64_t item = q * total();\n> +\t/* Binary search to find the right bin */\n> +\twhile (first < last) {\n> +\t\tint middle = (first + last) / 2;\n> +\t\t/* Is it between first and middle ? */\n> +\t\tif (cumulative_[middle + 1] > item)\n> +\t\t\tlast = middle;\n> +\t\telse\n> +\t\t\tfirst = middle + 1;\n> +\t}\n> +\tASSERT(item >= cumulative_[first] && item <= cumulative_[last + 1]);> +\n> +\tdouble frac;\n> +\tif (cumulative_[first + 1] == cumulative_[first])\n> +\t\tfrac = 0;\n> +\telse\n> +\t\tfrac = (item - cumulative_[first]) / (cumulative_[first + 1] - cumulative_[first]);\n> +\treturn first + frac;\n> +}\n> +\n> +/**\n> + * \\brief Calculate the mean between two quantiles\n> + * \\param[in] lowQuantile low Quantile\n> + * \\param[in] highQuantile high Quantile\n> + *\n> + * Quantiles are not ideal for metering as they suffer several limitations.\n> + * Instead, a concept is introduced here: inter-quantile mean.\n> + * It returns the mean of all pixels between lowQuantile and highQuantile.\n> + *\n> + * \\return The mean histogram bin value between the two quantiles\n> + */\n> +double Histogram::interQuantileMean(double lowQuantile, double highQuantile) const\n> +{\n> +\tASSERT(highQuantile > lowQuantile);\n> +\t/* Proportion of pixels which lies below lowQuantile */\n> +\tdouble lowPoint = quantile(lowQuantile);\n> +\t/* Proportion of pixels which lies below highQuantile */\n> +\tdouble highPoint = quantile(highQuantile, static_cast(lowPoint));\n> +\tdouble sumBinFreq = 0, cumulFreq = 0;\n> +\n> +\tfor (double p_next = floor(lowPoint) + 1.0;\n> +\t p_next <= ceil(highPoint);\n> +\t lowPoint = p_next, p_next += 1.0) {\n> +\t\tint bin = floor(lowPoint);\n> +\t\tdouble freq = (cumulative_[bin + 1] - cumulative_[bin]) * (std::min(p_next, highPoint) - lowPoint);\n\nLong line here could be split ... ?\n\n> +\t\tdouble freq = (cumulative_[bin + 1] - cumulative_[bin])\n\t\t\t * (std::min(p_next, highPoint) - lowPoint);\n\nI wonder if there's a way to get clang-format to be better tuned for our\ndesired line lengths.\n\n\nReviewed-by: Kieran Bingham \n\n\n\n> +\n> +\t\t/* Accumulate weigthed bin */\n> +\t\tsumBinFreq += bin * freq;\n> +\t\t/* Accumulate weights */\n> +\t\tcumulFreq += freq;\n> +\t}\n> +\t/* add 0.5 to give an average for bin mid-points */\n> +\treturn sumBinFreq / cumulFreq + 0.5;\n> +}\n> +\n> +} /* namespace ipa */\n> +\n> +} /* namespace libcamera */\n> diff --git a/src/ipa/libipa/histogram.h b/src/ipa/libipa/histogram.h\n> new file mode 100644\n> index 00000000..e06f1884\n> --- /dev/null\n> +++ b/src/ipa/libipa/histogram.h\n> @@ -0,0 +1,40 @@\n> +/* SPDX-License-Identifier: BSD-2-Clause */\n> +/*\n> + * Copyright (C) 2019, Raspberry Pi (Trading) Limited\n> + *\n> + * histogram.h - histogram calculation interface\n> + */\n> +#ifndef __LIBCAMERA_IPA_LIBIPA_HISTOGRAM_H__\n> +#define __LIBCAMERA_IPA_LIBIPA_HISTOGRAM_H__\n> +\n> +#include \n> +#include \n> +#include \n> +\n> +#include \n> +\n> +#include \n> +\n> +namespace libcamera {\n> +\n> +namespace ipa {\n> +\n> +class Histogram\n> +{\n> +public:\n> +\tHistogram(Span data);\n> +\tsize_t bins() const { return cumulative_.size() - 1; }\n> +\tuint64_t total() const { return cumulative_[cumulative_.size() - 1]; }\n> +\tuint64_t cumulativeFrequency(double bin) const;\n> +\tdouble quantile(double q, uint32_t first = 0, uint32_t last = UINT_MAX) const;\n> +\tdouble interQuantileMean(double lowQuantile, double hiQuantile) const;\n> +\n> +private:\n> +\tstd::vector cumulative_;\n> +};\n> +\n> +} /* namespace ipa */\n> +\n> +} /* namespace libcamera */\n> +\n> +#endif /* __LIBCAMERA_IPA_LIBIPA_HISTOGRAM_H__ */\n> diff --git a/src/ipa/libipa/meson.build b/src/ipa/libipa/meson.build\n> index 1819711d..038fc490 100644\n> --- a/src/ipa/libipa/meson.build\n> +++ b/src/ipa/libipa/meson.build\n> @@ -2,10 +2,12 @@\n> \n> libipa_headers = files([\n> 'algorithm.h',\n> + 'histogram.h'\n> ])\n> \n> libipa_sources = files([\n> 'algorithm.cpp',\n> + 'histogram.cpp'\n> ])\n> \n> libipa_includes = include_directories('..')\n> \n> \n> _______________________________________________\n> libcamera-devel mailing list\n> libcamera-devel@lists.libcamera.org\n> https://lists.libcamera.org/listinfo/libcamera-devel\n>","headers":{"Return-Path":"","X-Original-To":"parsemail@patchwork.libcamera.org","Delivered-To":"parsemail@patchwork.libcamera.org","Received":["from lancelot.ideasonboard.com (lancelot.ideasonboard.com\n\t[92.243.16.209])\n\tby patchwork.libcamera.org (Postfix) with ESMTPS id 893CABD812\n\tfor ;\n\tMon, 19 Apr 2021 10:00:23 +0000 (UTC)","from lancelot.ideasonboard.com (localhost [IPv6:::1])\n\tby lancelot.ideasonboard.com (Postfix) with ESMTP id E30996880B;\n\tMon, 19 Apr 2021 12:00:22 +0200 (CEST)","from perceval.ideasonboard.com (perceval.ideasonboard.com\n\t[213.167.242.64])\n\tby lancelot.ideasonboard.com (Postfix) with ESMTPS id BED6C602C6\n\tfor ;\n\tMon, 19 Apr 2021 12:00:20 +0200 (CEST)","from [192.168.0.20]\n\t(cpc89244-aztw30-2-0-cust3082.18-1.cable.virginm.net [86.31.172.11])\n\tby perceval.ideasonboard.com (Postfix) with ESMTPSA id 3EC3CD4A;\n\tMon, 19 Apr 2021 12:00:20 +0200 (CEST)"],"Authentication-Results":"lancelot.ideasonboard.com;\n\tdkim=fail reason=\"signature verification failed\" (1024-bit key;\n\tunprotected) header.d=ideasonboard.com header.i=@ideasonboard.com\n\theader.b=\"SSlUtu/6\"; dkim-atps=neutral","DKIM-Signature":"v=1; a=rsa-sha256; c=relaxed/simple; d=ideasonboard.com;\n\ts=mail; t=1618826420;\n\tbh=Fl8d8/+xkDYWDPrn4o7wV9ifIWzMAVEIn9eXqMszS4U=;\n\th=Reply-To:Subject:To:References:From:Date:In-Reply-To:From;\n\tb=SSlUtu/6zhG8XILxREb2FeXHhpP1SOCW0PtTifM+38oyzQqZA/lTHBkI94nkX1GTw\n\tpsU4+dkQ5gqN8frNx2WbMF7m7EbbTQurkr+ZF6/doamP0WFspycOlbZxH1yzuWkBFj\n\tMwmP4oDZSAfp93eQk0feXMDbgU8ryjToxGrQlzBM=","To":"Jean-Michel Hautbois ,\n\tlibcamera-devel@lists.libcamera.org","References":"<20210416074909.24218-1-jeanmichel.hautbois@ideasonboard.com>\n\t<20210416074909.24218-3-jeanmichel.hautbois@ideasonboard.com>","From":"Kieran Bingham ","Organization":"Ideas on Board","Message-ID":"<053465b1-9a58-eab7-0412-abf3754133fe@ideasonboard.com>","Date":"Mon, 19 Apr 2021 11:00:17 +0100","User-Agent":"Mozilla/5.0 (X11; Linux x86_64; rv:78.0) Gecko/20100101\n\tThunderbird/78.7.1","MIME-Version":"1.0","In-Reply-To":"<20210416074909.24218-3-jeanmichel.hautbois@ideasonboard.com>","Content-Language":"en-GB","Subject":"Re: [libcamera-devel] [PATCH v5 2/4] ipa: ipu3: Add a histogram\n\tclass","X-BeenThere":"libcamera-devel@lists.libcamera.org","X-Mailman-Version":"2.1.29","Precedence":"list","List-Id":"","List-Unsubscribe":",\n\t","List-Archive":"","List-Post":"","List-Help":"","List-Subscribe":",\n\t","Reply-To":"kieran.bingham@ideasonboard.com","Content-Type":"text/plain; charset=\"utf-8\"","Content-Transfer-Encoding":"base64","Errors-To":"libcamera-devel-bounces@lists.libcamera.org","Sender":"\"libcamera-devel\" "}}]