[{"id":16175,"web_url":"https://patchwork.libcamera.org/comment/16175/","msgid":"<4514990f-cd7a-7a3f-b602-e5db1cb3b33e@ideasonboard.com>","date":"2021-04-12T12:21:03","subject":"Re: [libcamera-devel] [PATCH v4 2/4] WIP: ipa: ipu3: Add an\n\thistogram class","submitter":{"id":4,"url":"https://patchwork.libcamera.org/api/people/4/","name":"Kieran Bingham","email":"kieran.bingham@ideasonboard.com"},"content":"Hi Jean-Michel,\n\nin $SUBJECT\n\ns/an/a/\n\n\n\nOn 30/03/2021 22:12, Jean-Michel Hautbois wrote:\n> This class will be used at least by AGC algorithm when quantiles are\n> needed for example.\n> \n\nIs this really a Histogram class? Or is is a CumulativeFrequency class?\n\nI may likely be mis-interpretting or just wrong - but I thought a\nhistogram stored values like:\n\n\nvalue 0 1 2 3 4 5 6 7 8 9\ncount 5 0 3 5 6 9 2 0 2 5\n\nMeaning that ... you can look up in the table to see that there are 5\noccurrences of the value 9 in the dataset... whereas this stores:\n\n\nvalue 0 1 2 3 4 5 6 7 8 9\ncount 5 8 8 13 19 28 30 30 32 37\n\n\nOk, so now I've drawn that out, I can see that the same information is\nstill there, as you can get the occurrences of any specific value by\nsubtracting from the previous 'bin'?\n\n\n> Signed-off-by: Jean-Michel Hautbois \n> ---\n> src/ipa/libipa/histogram.cpp | 154 +++++++++++++++++++\n> src/ipa/libipa/histogram.h | 40 +++++\n> src/ipa/libipa/meson.build | 2 +\n> src/ipa/raspberrypi/controller/histogram.hpp | 9 +-\n> 4 files changed, 197 insertions(+), 8 deletions(-)\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..46fbb940\n> --- /dev/null\n> +++ b/src/ipa/libipa/histogram.cpp\n> @@ -0,0 +1,154 @@\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> + * The Histogram class defines a standard interface for IPA algorithms. By\n> + * abstracting histograms, it makes it possible to implement generic code\n> + * to manage histograms regardless of their specific type.\n\nI don't think this defines a standard interface for IPA algorithms ;)\n\nI think we can drop that paragraph and keep the one below.\n\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 with a bin number of intervals\n\nI suspect 'bin' was a previous value passed in here.\n\nI think we should describe how data should be passed in.\nI.e. I think perhaps it should be a pre-sorted histogram or something?\n\n\n> + * \\param[in] data a reference to the histogram\n\nI don't think this is a reference anymore.\n\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> +/**\n> + * \\fn Histogram::bins()\n> + * \\brief getter for number of bins\n\nWe don't normally reference them as 'getter's even if that's what they do.\n\nTo be consistent with other briefs, we should put something like:\n\n \\brief Retrieve the number of bins currently stored in the Histogram\n\n\n(stored by, might be 'used by'?)\n\n\n> + * \\return Number of bins\n> + */\n> +/**\n> + * \\fn Histogram::total()\n> + * \\brief getter for number of values\n\nSame here,\n\n \\brief Retrieve the total number of values in the data set\n\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 upon which to cumulate\n\ns/the/The/\n(Capital letter to start after the parameter itself.)\n\nReading below, does it also mean this should say \"up to which\" rather\nthan \"upon which\"?\n\ni.e.\n upon which: to me, counts the values 'in' that bin.\n up to which: to me, counts the values up to that one...\n\n> + *\n> + * With F(p) the cumulative frequency of the histogram, the value is 0 at\n\nWhat is F(p) here?\n\n\n\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 cumulated frequency from 0 up to the specified bin\n> + */\n> +uint64_t Histogram::cumulativeFreq(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> +\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> +\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> +\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..dc7451aa\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 cumulativeFreq(double bin) const;\n\nI'd make this cumulativeFrequency()\n\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\nI see this came from the RPi code.\nDo we really store 64 bit values in here? or are they only 32bit? (or\nsmaller?)\n\nIn fact, I see we now construct with a Span data, so\npresumably this vector can be uint32_t.\n\nWe could template it to accept different sizes if that would help ...\nbut I think supporting 32 bits is probably fine if that's the span we\ncurrently define....\n\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> diff --git a/src/ipa/raspberrypi/controller/histogram.hpp b/src/ipa/raspberrypi/controller/histogram.hpp\n> index 90f5ac78..fc236416 100644\n> --- a/src/ipa/raspberrypi/controller/histogram.hpp\n> +++ b/src/ipa/raspberrypi/controller/histogram.hpp\n\nI'm not sure if the modifications to the RPi histogram below should be\nin this patch.\n\nIt looks like they're unrelated to the actual code move?\n\nPerhaps leave this out, and we can 'convert' RPi controller to use the\n'generic' histogram separately?\n\n\n> @@ -10,9 +10,6 @@\n> #include \n> #include \n> \n> -// A simple histogram class, for use in particular to find \"quantiles\" and\n> -// averages between \"quantiles\".\n> -\n> namespace RPiController {\n> \n> class Histogram\n> @@ -29,12 +26,8 @@ public:\n> \t}\n> \tuint32_t Bins() const { return cumulative_.size() - 1; }\n> \tuint64_t Total() const { return cumulative_[cumulative_.size() - 1]; }\n> -\t// Cumulative frequency up to a (fractional) point in a bin.\n> \tuint64_t CumulativeFreq(double bin) const;\n> -\t// Return the (fractional) bin of the point q (0 <= q <= 1) through the\n> -\t// histogram. Optionally provide limits to help.\n> -\tdouble Quantile(double q, int first = -1, int last = -1) const;\n> -\t// Return the average histogram bin value between the two quantiles.\n> +\tHistogram::quantile(double q, uint32_t first = 0, uint32_t last = UINT_MAX) const;\n> \tdouble InterQuantileMean(double q_lo, double q_hi) const;\n> \n> private:\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 DCE7CBD224\n\tfor ;\n\tMon, 12 Apr 2021 12:21:08 +0000 (UTC)","from lancelot.ideasonboard.com (localhost [IPv6:::1])\n\tby lancelot.ideasonboard.com (Postfix) with ESMTP id 582CB602C8;\n\tMon, 12 Apr 2021 14:21:08 +0200 (CEST)","from perceval.ideasonboard.com (perceval.ideasonboard.com\n\t[IPv6:2001:4b98:dc2:55:216:3eff:fef7:d647])\n\tby lancelot.ideasonboard.com (Postfix) with ESMTPS id 0D643602C8\n\tfor ;\n\tMon, 12 Apr 2021 14:21:07 +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 61B3D3F0;\n\tMon, 12 Apr 2021 14:21:06 +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=\"wbxfLsS5\"; dkim-atps=neutral","DKIM-Signature":"v=1; a=rsa-sha256; c=relaxed/simple; d=ideasonboard.com;\n\ts=mail; t=1618230066;\n\tbh=Ma99LtS9WMNNTwDA3e/y3WBGWI9mkZDkd9dQK3GYG4k=;\n\th=Reply-To:Subject:To:References:From:Date:In-Reply-To:From;\n\tb=wbxfLsS5ds5dpEBYTmvmUrwdN43Vt6m9BCcHwfQRlz30zJPFvf9oclnImQg66mIpB\n\tKGBsKnxAHnj1uUruQoKMh3xSV36qq6AxWV3qooV0UxYJh2cevJnGYITXToP3333M15\n\tWkvtLKAiN0taB/qFPHY/TAwVVwak6m8Jc4IWTSCo=","To":"Jean-Michel Hautbois ,\n\tlibcamera-devel@lists.libcamera.org","References":"<20210330211210.194806-1-jeanmichel.hautbois@ideasonboard.com>\n\t<20210330211210.194806-3-jeanmichel.hautbois@ideasonboard.com>","From":"Kieran Bingham ","Autocrypt":"addr=kieran.bingham@ideasonboard.com; keydata=\n\tmQINBFYE/WYBEACs1PwjMD9rgCu1hlIiUA1AXR4rv2v+BCLUq//vrX5S5bjzxKAryRf0uHat\n\tV/zwz6hiDrZuHUACDB7X8OaQcwhLaVlq6byfoBr25+hbZG7G3+5EUl9cQ7dQEdvNj6V6y/SC\n\trRanWfelwQThCHckbobWiQJfK9n7rYNcPMq9B8e9F020LFH7Kj6YmO95ewJGgLm+idg1Kb3C\n\tpotzWkXc1xmPzcQ1fvQMOfMwdS+4SNw4rY9f07Xb2K99rjMwZVDgESKIzhsDB5GY465sCsiQ\n\tcSAZRxqE49RTBq2+EQsbrQpIc8XiffAB8qexh5/QPzCmR4kJgCGeHIXBtgRj+nIkCJPZvZtf\n\tKr2EAbc6tgg6DkAEHJb+1okosV09+0+TXywYvtEop/WUOWQ+zo+Y/OBd+8Ptgt1pDRyOBzL8\n\tRXa8ZqRf0Mwg75D+dKntZeJHzPRJyrlfQokngAAs4PaFt6UfS+ypMAF37T6CeDArQC41V3ko\n\tlPn1yMsVD0p+6i3DPvA/GPIksDC4owjnzVX9kM8Zc5Cx+XoAN0w5Eqo4t6qEVbuettxx55gq\n\t8K8FieAjgjMSxngo/HST8TpFeqI5nVeq0/lqtBRQKumuIqDg+Bkr4L1V/PSB6XgQcOdhtd36\n\tOe9X9dXB8YSNt7VjOcO7BTmFn/Z8r92mSAfHXpb07YJWJosQOQARAQABtDBLaWVyYW4gQmlu\n\tZ2hhbSA8a2llcmFuLmJpbmdoYW1AaWRlYXNvbmJvYXJkLmNvbT6JAlcEEwEKAEECGwMFCwkI\n\tBwIGFQgJCgsCBBYCAwECHgECF4ACGQEWIQSQLdeYP70o/eNy1HqhHkZyEKRh/QUCXWTtygUJ\n\tCyJXZAAKCRChHkZyEKRh/f8dEACTDsbLN2nioNZMwyLuQRUAFcXNolDX48xcUXsWS2QjxaPm\n\tVsJx8Uy8aYkS85mdPBh0C83OovQR/OVbr8AxhGvYqBs3nQvbWuTl/+4od7DfK2VZOoKBAu5S\n\tQK2FYuUcikDqYcFWJ8DQnubxfE8dvzojHEkXw0sA4igINHDDFX3HJGZtLio+WpEFQtCbfTAG\n\tYZslasz1YZRbwEdSsmO3/kqy5eMnczlm8a21A3fKUo3g8oAZEFM+f4DUNzqIltg31OAB/kZS\n\tenKZQ/SWC8PmLg/ZXBrReYakxXtkP6w3FwMlzOlhGxqhIRNiAJfXJBaRhuUWzPOpEDE9q5YJ\n\tBmqQL2WJm1VSNNVxbXJHpaWMH1sA2R00vmvRrPXGwyIO0IPYeUYQa3gsy6k+En/aMQJd27dp\n\taScf9am9PFICPY5T4ppneeJLif2lyLojo0mcHOV+uyrds9XkLpp14GfTkeKPdPMrLLTsHRfH\n\tfA4I4OBpRrEPiGIZB/0im98MkGY/Mu6qxeZmYLCcgD6qz4idOvfgVOrNh+aA8HzIVR+RMW8H\n\tQGBN9f0E3kfwxuhl3omo6V7lDw8XOdmuWZNC9zPq1UfryVHANYbLGz9KJ4Aw6M+OgBC2JpkD\n\thXMdHUkC+d20dwXrwHTlrJi1YNp6rBc+xald3wsUPOZ5z8moTHUX/uPA/qhGsbkCDQRWBP1m\n\tARAAzijkb+Sau4hAncr1JjOY+KyFEdUNxRy+hqTJdJfaYihxyaj0Ee0P0zEi35CbE6lgU0Uz\n\ttih9fiUbSV3wfsWqg1Ut3/5rTKu7kLFp15kF7eqvV4uezXRD3Qu4yjv/rMmEJbbD4cTvGCYI\n\td6MDC417f7vK3hCbCVIZSp3GXxyC1LU+UQr3fFcOyCwmP9vDUR9JV0BSqHHxRDdpUXE26Dk6\n\tmhf0V1YkspE5St814ETXpEus2urZE5yJIUROlWPIL+hm3NEWfAP06vsQUyLvr/GtbOT79vXl\n\tEn1aulcYyu20dRRxhkQ6iILaURcxIAVJJKPi8dsoMnS8pB0QW12AHWuirPF0g6DiuUfPmrA5\n\tPKe56IGlpkjc8cO51lIxHkWTpCMWigRdPDexKX+Sb+W9QWK/0JjIc4t3KBaiG8O4yRX8ml2R\n\t+rxfAVKM6V769P/hWoRGdgUMgYHFpHGSgEt80OKK5HeUPy2cngDUXzwrqiM5Sz6Od0qw5pCk\n\tNlXqI0W/who0iSVM+8+RmyY0OEkxEcci7rRLsGnM15B5PjLJjh1f2ULYkv8s4SnDwMZ/kE04\n\t/UqCMK/KnX8pwXEMCjz0h6qWNpGwJ0/tYIgQJZh6bqkvBrDogAvuhf60Sogw+mH8b+PBlx1L\n\toeTK396wc+4c3BfiC6pNtUS5GpsPMMjYMk7kVvEAEQEAAYkCPAQYAQoAJgIbDBYhBJAt15g/\n\tvSj943LUeqEeRnIQpGH9BQJdizzIBQkLSKZiAAoJEKEeRnIQpGH9eYgQAJpjaWNgqNOnMTmD\n\tMJggbwjIotypzIXfhHNCeTkG7+qCDlSaBPclcPGYrTwCt0YWPU2TgGgJrVhYT20ierN8LUvj\n\t6qOPTd+Uk7NFzL65qkh80ZKNBFddx1AabQpSVQKbdcLb8OFs85kuSvFdgqZwgxA1vl4TFhNz\n\tPZ79NAmXLackAx3sOVFhk4WQaKRshCB7cSl+RIng5S/ThOBlwNlcKG7j7W2MC06BlTbdEkUp\n\tECzuuRBv8wX4OQl+hbWbB/VKIx5HKlLu1eypen/5lNVzSqMMIYkkZcjV2SWQyUGxSwq0O/sx\n\tS0A8/atCHUXOboUsn54qdxrVDaK+6jIAuo8JiRWctP16KjzUM7MO0/+4zllM8EY57rXrj48j\n\tsbEYX0YQnzaj+jO6kJtoZsIaYR7rMMq9aUAjyiaEZpmP1qF/2sYenDx0Fg2BSlLvLvXM0vU8\n\tpQk3kgDu7kb/7PRYrZvBsr21EIQoIjXbZxDz/o7z95frkP71EaICttZ6k9q5oxxA5WC6sTXc\n\tMW8zs8avFNuA9VpXt0YupJd2ijtZy2mpZNG02fFVXhIn4G807G7+9mhuC4XG5rKlBBUXTvPU\n\tAfYnB4JBDLmLzBFavQfvonSfbitgXwCG3vS+9HEwAjU30Bar1PEOmIbiAoMzuKeRm2LVpmq4\n\tWZw01QYHU/GUV/zHJSFk","Organization":"Ideas on Board","Message-ID":"<4514990f-cd7a-7a3f-b602-e5db1cb3b33e@ideasonboard.com>","Date":"Mon, 12 Apr 2021 13:21:03 +0100","User-Agent":"Mozilla/5.0 (X11; Linux x86_64; rv:68.0) Gecko/20100101\n\tThunderbird/68.10.0","MIME-Version":"1.0","In-Reply-To":"<20210330211210.194806-3-jeanmichel.hautbois@ideasonboard.com>","Content-Language":"en-GB","Subject":"Re: [libcamera-devel] [PATCH v4 2/4] WIP: ipa: ipu3: Add an\n\thistogram class","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\" "}},{"id":16180,"web_url":"https://patchwork.libcamera.org/comment/16180/","msgid":"","date":"2021-04-12T13:29:03","subject":"Re: [libcamera-devel] [PATCH v4 2/4] WIP: ipa: ipu3: Add an\n\thistogram class","submitter":{"id":42,"url":"https://patchwork.libcamera.org/api/people/42/","name":"David Plowman","email":"david.plowman@raspberrypi.com"},"content":"Hi Jean-Michel, Kieran\n\nHappy to see this code getting some use elsewhere! I thought I could\njust add a couple of comments on some of our original thinking...\n\nOn Mon, 12 Apr 2021 at 13:21, Kieran Bingham\n wrote:\n>\n> Hi Jean-Michel,\n>\n> in $SUBJECT\n>\n> s/an/a/\n>\n>\n>\n> On 30/03/2021 22:12, Jean-Michel Hautbois wrote:\n> > This class will be used at least by AGC algorithm when quantiles are\n> > needed for example.\n> >\n>\n> Is this really a Histogram class? Or is is a CumulativeFrequency class?\n>\n> I may likely be mis-interpretting or just wrong - but I thought a\n> histogram stored values like:\n>\n>\n> value 0 1 2 3 4 5 6 7 8 9\n> count 5 0 3 5 6 9 2 0 2 5\n>\n> Meaning that ... you can look up in the table to see that there are 5\n> occurrences of the value 9 in the dataset... whereas this stores:\n>\n>\n> value 0 1 2 3 4 5 6 7 8 9\n> count 5 8 8 13 19 28 30 30 32 37\n>\n>\n> Ok, so now I've drawn that out, I can see that the same information is\n> still there, as you can get the occurrences of any specific value by\n> subtracting from the previous 'bin'?\n\nI think you've pretty much convinced yourself why it stores cumulative\nfrequency. Going from cumulative frequency back to per-bin values is a\nsingle subtraction. Going the other way is a loop. Given that finding\n\"quantiles\" is a fairly useful operation, cumulative frequencies make\nsense.\n\n>\n>\n> > Signed-off-by: Jean-Michel Hautbois \n> > ---\n> > src/ipa/libipa/histogram.cpp | 154 +++++++++++++++++++\n> > src/ipa/libipa/histogram.h | 40 +++++\n> > src/ipa/libipa/meson.build | 2 +\n> > src/ipa/raspberrypi/controller/histogram.hpp | 9 +-\n> > 4 files changed, 197 insertions(+), 8 deletions(-)\n> > create mode 100644 src/ipa/libipa/histogram.cpp\n> > create mode 100644 src/ipa/libipa/histogram.h\n\nWill this header be includable by application code? I've sometimes\nfound myself getting an image and then wanting to do histogram\noperations. (Of course, this class doesn't make the Histogram from\nscratch, you have to start by totting up the bins yourself, but that's\nnot difficult and then you get means, quantiles and stuff for free...)\n\n> >\n> > diff --git a/src/ipa/libipa/histogram.cpp b/src/ipa/libipa/histogram.cpp\n> > new file mode 100644\n> > index 00000000..46fbb940\n> > --- /dev/null\n> > +++ b/src/ipa/libipa/histogram.cpp\n> > @@ -0,0 +1,154 @@\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> > + * The Histogram class defines a standard interface for IPA algorithms. By\n> > + * abstracting histograms, it makes it possible to implement generic code\n> > + * to manage histograms regardless of their specific type.\n>\n> I don't think this defines a standard interface for IPA algorithms ;)\n>\n> I think we can drop that paragraph and keep the one below.\n>\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 with a bin number of intervals\n>\n> I suspect 'bin' was a previous value passed in here.\n>\n> I think we should describe how data should be passed in.\n> I.e. I think perhaps it should be a pre-sorted histogram or something?\n>\n>\n> > + * \\param[in] data a reference to the histogram\n>\n> I don't think this is a reference anymore.\n>\n> > + */\n> > +Histogram::Histogram(Span data)\n> > +{\n> > + cumulative_.reserve(data.size());\n> > + cumulative_.push_back(0);\n> > + for (const uint32_t &value : data)\n> > + cumulative_.push_back(cumulative_.back() + value);\n> > +}\n> > +/**\n> > + * \\fn Histogram::bins()\n> > + * \\brief getter for number of bins\n>\n> We don't normally reference them as 'getter's even if that's what they do.\n>\n> To be consistent with other briefs, we should put something like:\n>\n> \\brief Retrieve the number of bins currently stored in the Histogram\n>\n>\n> (stored by, might be 'used by'?)\n>\n>\n> > + * \\return Number of bins\n> > + */\n> > +/**\n> > + * \\fn Histogram::total()\n> > + * \\brief getter for number of values\n>\n> Same here,\n>\n> \\brief Retrieve the total number of values in the data set\n>\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 upon which to cumulate\n>\n> s/the/The/\n> (Capital letter to start after the parameter itself.)\n>\n> Reading below, does it also mean this should say \"up to which\" rather\n> than \"upon which\"?\n>\n> i.e.\n> upon which: to me, counts the values 'in' that bin.\n> up to which: to me, counts the values up to that one...\n\nAlso, I don't think there's a verb \"to cumulate\", is there?\n\n>\n> > + *\n> > + * With F(p) the cumulative frequency of the histogram, the value is 0 at\n>\n> What is F(p) here?\n\nI think this is defining it to be the cumulative frequency.\n\n>\n>\n>\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 cumulated frequency from 0 up to the specified bin\n\ns/cumulated/cumulative/\n\n> > + */\n> > +uint64_t Histogram::cumulativeFreq(double bin) const\n> > +{\n> > + if (bin <= 0)\n> > + return 0;\n> > + else if (bin >= bins())\n> > + return total();\n> > + int b = static_cast(bin);\n> > + return cumulative_[b] +\n> > + (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> > + if (last == UINT_MAX)\n> > + last = cumulative_.size() - 2;\n> > + ASSERT(first <= last);\n> > +\n> > + uint64_t item = q * total();\n> > + /* Binary search to find the right bin */\n> > + while (first < last) {\n> > + int middle = (first + last) / 2;\n> > + /* Is it between first and middle ? */\n> > + if (cumulative_[middle + 1] > item)\n> > + last = middle;\n> > + else\n> > + first = middle + 1;\n> > + }\n> > + ASSERT(item >= cumulative_[first] && item <= cumulative_[last + 1]);\n> > +\n> > + double frac;\n> > + if (cumulative_[first + 1] == cumulative_[first])\n> > + frac = 0;\n> > + else\n> > + frac = (item - cumulative_[first]) / (cumulative_[first + 1] - cumulative_[first]);\n> > + return 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> > + ASSERT(highQuantile > lowQuantile);\n> > + /* Proportion of pixels which lies below lowQuantile */\n> > + double lowPoint = quantile(lowQuantile);\n> > + /* Proportion of pixels which lies below highQuantile */\n> > + double highPoint = quantile(highQuantile, static_cast(lowPoint));\n> > + double sumBinFreq = 0, cumulFreq = 0;\n> > +\n> > + for (double p_next = floor(lowPoint) + 1.0;\n> > + p_next <= ceil(highPoint);\n> > + lowPoint = p_next, p_next += 1.0) {\n> > + int bin = floor(lowPoint);\n> > + double freq = (cumulative_[bin + 1] - cumulative_[bin]) * (std::min(p_next, highPoint) - lowPoint);\n> > +\n> > + /* Accumulate weigthed bin */\n> > + sumBinFreq += bin * freq;\n> > + /* Accumulate weights */\n> > + cumulFreq += freq;\n> > + }\n> > + /* add 0.5 to give an average for bin mid-points */\n> > + return sumBinFreq / cumulFreq + 0.5;\n> > +}\n\nI always meant to rewrite this so that the highPoint is found during\nthe loop, not by a separate call to quantile(). Job for another day...\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..dc7451aa\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> > + Histogram(Span data);\n> > + size_t bins() const { return cumulative_.size() - 1; }\n> > + uint64_t total() const { return cumulative_[cumulative_.size() - 1]; }\n> > + uint64_t cumulativeFreq(double bin) const;\n>\n> I'd make this cumulativeFrequency()\n>\n> > + double quantile(double q, uint32_t first = 0, uint32_t last = UINT_MAX) const;\n> > + double interQuantileMean(double lowQuantile, double hiQuantile) const;\n> > +\n> > +private:\n> > + std::vector cumulative_;\n>\n> I see this came from the RPi code.\n> Do we really store 64 bit values in here? or are they only 32bit? (or\n> smaller?)\n>\n> In fact, I see we now construct with a Span data, so\n> presumably this vector can be uint32_t.\n>\n> We could template it to accept different sizes if that would help ...\n> but I think supporting 32 bits is probably fine if that's the span we\n> currently define....\n\nI guess 32 bits (rather than 64-bit values) is OK, though it does\nlimit you to images no larger than 4GP (Gigapixels)! Whilst I don't\nsuppose that matters for any current hardware, you might want to\nconsider what future hardware might come along (there are Gigapixel\nimages out there...). The constructor was chosen to work with the\nstatistics that come out of the Pi ISP, which gives you 32-bit bins.\n\nBest regards\n\nDavid\n\n>\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> > diff --git a/src/ipa/raspberrypi/controller/histogram.hpp b/src/ipa/raspberrypi/controller/histogram.hpp\n> > index 90f5ac78..fc236416 100644\n> > --- a/src/ipa/raspberrypi/controller/histogram.hpp\n> > +++ b/src/ipa/raspberrypi/controller/histogram.hpp\n>\n> I'm not sure if the modifications to the RPi histogram below should be\n> in this patch.\n>\n> It looks like they're unrelated to the actual code move?\n>\n> Perhaps leave this out, and we can 'convert' RPi controller to use the\n> 'generic' histogram separately?\n>\n>\n> > @@ -10,9 +10,6 @@\n> > #include \n> > #include \n> >\n> > -// A simple histogram class, for use in particular to find \"quantiles\" and\n> > -// averages between \"quantiles\".\n> > -\n> > namespace RPiController {\n> >\n> > class Histogram\n> > @@ -29,12 +26,8 @@ public:\n> > }\n> > uint32_t Bins() const { return cumulative_.size() - 1; }\n> > uint64_t Total() const { return cumulative_[cumulative_.size() - 1]; }\n> > - // Cumulative frequency up to a (fractional) point in a bin.\n> > uint64_t CumulativeFreq(double bin) const;\n> > - // Return the (fractional) bin of the point q (0 <= q <= 1) through the\n> > - // histogram. Optionally provide limits to help.\n> > - double Quantile(double q, int first = -1, int last = -1) const;\n> > - // Return the average histogram bin value between the two quantiles.\n> > + Histogram::quantile(double q, uint32_t first = 0, uint32_t last = UINT_MAX) const;\n> > double InterQuantileMean(double q_lo, double q_hi) const;\n> >\n> > private:\n> >\n>\n> --\n> Regards\n> --\n> Kieran\n> _______________________________________________\n> libcamera-devel mailing list\n> libcamera-devel@lists.libcamera.org\n> https://lists.libcamera.org/listinfo/libcamera-devel","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 5AB8CBD1F6\n\tfor ;\n\tMon, 12 Apr 2021 13:29:19 +0000 (UTC)","from lancelot.ideasonboard.com (localhost [IPv6:::1])\n\tby lancelot.ideasonboard.com (Postfix) with ESMTP id C6F3A687F8;\n\tMon, 12 Apr 2021 15:29:18 +0200 (CEST)","from mail-oi1-x233.google.com (mail-oi1-x233.google.com\n\t[IPv6:2607:f8b0:4864:20::233])\n\tby lancelot.ideasonboard.com (Postfix) with ESMTPS id E1512602C8\n\tfor ;\n\tMon, 12 Apr 2021 15:29:16 +0200 (CEST)","by mail-oi1-x233.google.com with SMTP id a21so327012oib.10\n\tfor ;\n\tMon, 12 Apr 2021 06:29:16 -0700 (PDT)"],"Authentication-Results":"lancelot.ideasonboard.com;\n\tdkim=fail reason=\"signature verification failed\" (2048-bit key;\n\tunprotected) header.d=raspberrypi.com header.i=@raspberrypi.com\n\theader.b=\"iMwlVzzq\"; dkim-atps=neutral","DKIM-Signature":"v=1; a=rsa-sha256; c=relaxed/relaxed;\n\td=raspberrypi.com; s=google;\n\th=mime-version:references:in-reply-to:from:date:message-id:subject:to\n\t:cc:content-transfer-encoding;\n\tbh=gLBEVj07voxM3HHjbPwYpQa5RQiiUqarXlRn3yaxHB0=;\n\tb=iMwlVzzqryygc+CLeMW8p78QeSi/mSR5nQlkQ1BRZWSBdhtQIXgICmDUAXLM25fP9T\n\tIkNFLtNeoss2syIuNg0T8Wd8VO5S/KGpQxoKvqEOFxDWSu4nlmfncO7379agq8tLUdlG\n\tvhQjLKjvUoWqf0fpXeVtpt2lnGc3ByJ6U9jj+3bttQ5N+t+kDTSCEqAtNtTzecqgLR5E\n\tcQgzVwo1HTRFQp8Y7BtsZ+xqbMO7TkNgGtKptNnSofij21ro/oo5bn3S0B2zTQz/dSNL\n\tF++MBVyZf2MKWMZgc+tTY89xf36aX3lG89vwxybc54aOhG/IS1KMPup6oIn7Uv0MDF+K\n\tS89g==","X-Google-DKIM-Signature":"v=1; a=rsa-sha256; c=relaxed/relaxed;\n\td=1e100.net; s=20161025;\n\th=x-gm-message-state:mime-version:references:in-reply-to:from:date\n\t:message-id:subject:to:cc:content-transfer-encoding;\n\tbh=gLBEVj07voxM3HHjbPwYpQa5RQiiUqarXlRn3yaxHB0=;\n\tb=pTbLNZTPpH/RvkDNUoPLmW+W8OdkaRl1jqe1nKItFXOkhWUlSfWFjYNluRe83U35BN\n\tVAN/X4sHvzqOi/uEZ87oLbQqoAnoLa2qOHkFVXNs9WDAPF3oSECA0EdB2Yxv/mhBD9gB\n\tSYPYtg4iAg9HoXGDpj2p7Ex4VTCkseVOqX0hSeVwN9yjqtcZpwYzB6Gx5BQlOreCZZQM\n\tBCu1pSAsBxoBBG2/ht8P7xHaL7HrSuN/wwqf+fmQLwB39LnZV9vRFk6EFJDgJepT4CYx\n\tpZma+fZJiJZLkxsPV+Fj7bkoQvaWeOTMEPq8Rz74meQGSEl16XuTESj2rdLK53pzWTBu\n\tCuKA==","X-Gm-Message-State":"AOAM5333P8Ar++dJUa4U1QfLD3QeAf2TwsVOYUFWmjWyt3x5EJlipno3\n\tiKSgRqY20gjdgxRTw/a17QPwbuoq6t23kz5D3DAhgw==","X-Google-Smtp-Source":"ABdhPJzDQHj1kpdfYoORSbSDMGvbAXSy/M9lZK95GT+cctFaQNpdOP2+/dYJl6Hp85chm1ursQg/UCblcNu4NkJJVrI=","X-Received":"by 2002:aca:f209:: with SMTP id q9mr1643165oih.55.1618234155240; \n\tMon, 12 Apr 2021 06:29:15 -0700 (PDT)","MIME-Version":"1.0","References":"<20210330211210.194806-1-jeanmichel.hautbois@ideasonboard.com>\n\t<20210330211210.194806-3-jeanmichel.hautbois@ideasonboard.com>\n\t<4514990f-cd7a-7a3f-b602-e5db1cb3b33e@ideasonboard.com>","In-Reply-To":"<4514990f-cd7a-7a3f-b602-e5db1cb3b33e@ideasonboard.com>","From":"David Plowman ","Date":"Mon, 12 Apr 2021 14:29:03 +0100","Message-ID":"","To":"Kieran Bingham ","Subject":"Re: [libcamera-devel] [PATCH v4 2/4] WIP: ipa: ipu3: Add an\n\thistogram class","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","Cc":"libcamera devel ","Content-Type":"text/plain; charset=\"utf-8\"","Content-Transfer-Encoding":"base64","Errors-To":"libcamera-devel-bounces@lists.libcamera.org","Sender":"\"libcamera-devel\" "}},{"id":16187,"web_url":"https://patchwork.libcamera.org/comment/16187/","msgid":"<2baf7d11-f3a4-7db2-1873-1561f2f55b96@ideasonboard.com>","date":"2021-04-12T18:53:58","subject":"Re: [libcamera-devel] [PATCH v4 2/4] WIP: ipa: ipu3: Add an\n\thistogram class","submitter":{"id":4,"url":"https://patchwork.libcamera.org/api/people/4/","name":"Kieran Bingham","email":"kieran.bingham@ideasonboard.com"},"content":"Hi David,\n\nOn 12/04/2021 14:29, David Plowman wrote:\n> Hi Jean-Michel, Kieran\n> \n> Happy to see this code getting some use elsewhere! I thought I could\n> just add a couple of comments on some of our original thinking...\n> \n> On Mon, 12 Apr 2021 at 13:21, Kieran Bingham\n> wrote:\n>>\n>> Hi Jean-Michel,\n>>\n>> in $SUBJECT\n>>\n>> s/an/a/\n>>\n>>\n>>\n>> On 30/03/2021 22:12, Jean-Michel Hautbois wrote:\n>>> This class will be used at least by AGC algorithm when quantiles are\n>>> needed for example.\n>>>\n>>\n>> Is this really a Histogram class? Or is is a CumulativeFrequency class?\n>>\n>> I may likely be mis-interpretting or just wrong - but I thought a\n>> histogram stored values like:\n>>\n>>\n>> value 0 1 2 3 4 5 6 7 8 9\n>> count 5 0 3 5 6 9 2 0 2 5\n>>\n>> Meaning that ... you can look up in the table to see that there are 5\n>> occurrences of the value 9 in the dataset... whereas this stores:\n>>\n>>\n>> value 0 1 2 3 4 5 6 7 8 9\n>> count 5 8 8 13 19 28 30 30 32 37\n>>\n>>\n>> Ok, so now I've drawn that out, I can see that the same information is\n>> still there, as you can get the occurrences of any specific value by\n>> subtracting from the previous 'bin'?\n> \n> I think you've pretty much convinced yourself why it stores cumulative\n> frequency. Going from cumulative frequency back to per-bin values is a\n> single subtraction. Going the other way is a loop. Given that finding\n> \"quantiles\" is a fairly useful operation, cumulative frequencies make\n> sense.\n\nPicture and a thousand words ...\n\nAs soon as I drew out the tables I could see it... ;-)\n\n> \n>>\n>>\n>>> Signed-off-by: Jean-Michel Hautbois \n>>> ---\n>>> src/ipa/libipa/histogram.cpp | 154 +++++++++++++++++++\n>>> src/ipa/libipa/histogram.h | 40 +++++\n>>> src/ipa/libipa/meson.build | 2 +\n>>> src/ipa/raspberrypi/controller/histogram.hpp | 9 +-\n>>> 4 files changed, 197 insertions(+), 8 deletions(-)\n>>> create mode 100644 src/ipa/libipa/histogram.cpp\n>>> create mode 100644 src/ipa/libipa/histogram.h\n> \n> Will this header be includable by application code? I've sometimes\n> found myself getting an image and then wanting to do histogram\n> operations. (Of course, this class doesn't make the Histogram from\n> scratch, you have to start by totting up the bins yourself, but that's\n> not difficult and then you get means, quantiles and stuff for free...)\n\nlibipa is not currently exposed as as a public API.\n\nBut there's lots of code that I'd like to be more re-usable.\n\nThe question is how do we make all the nice helpers available without\ncommitting to never changing them as a public interface ...\n\nI know Laurent has previously discussed moving helpers to separate\nlibrary sections or such.\n\nWe need to work towards being able to expose a stable API/ABI for\nlibcamera - but perhaps we could expose 'helper' libraries which don't\nneed to offer that guarantee?\n\n\n>>>\n>>> diff --git a/src/ipa/libipa/histogram.cpp b/src/ipa/libipa/histogram.cpp\n>>> new file mode 100644\n>>> index 00000000..46fbb940\n>>> --- /dev/null\n>>> +++ b/src/ipa/libipa/histogram.cpp\n>>> @@ -0,0 +1,154 @@\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>>> + * The Histogram class defines a standard interface for IPA algorithms. By\n>>> + * abstracting histograms, it makes it possible to implement generic code\n>>> + * to manage histograms regardless of their specific type.\n>>\n>> I don't think this defines a standard interface for IPA algorithms ;)\n>>\n>> I think we can drop that paragraph and keep the one below.\n>>\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 with a bin number of intervals\n>>\n>> I suspect 'bin' was a previous value passed in here.\n>>\n>> I think we should describe how data should be passed in.\n>> I.e. I think perhaps it should be a pre-sorted histogram or something?\n>>\n>>\n>>> + * \\param[in] data a reference to the histogram\n>>\n>> I don't think this is a reference anymore.\n>>\n>>> + */\n>>> +Histogram::Histogram(Span data)\n>>> +{\n>>> + cumulative_.reserve(data.size());\n>>> + cumulative_.push_back(0);\n>>> + for (const uint32_t &value : data)\n>>> + cumulative_.push_back(cumulative_.back() + value);\n>>> +}\n>>> +/**\n>>> + * \\fn Histogram::bins()\n>>> + * \\brief getter for number of bins\n>>\n>> We don't normally reference them as 'getter's even if that's what they do.\n>>\n>> To be consistent with other briefs, we should put something like:\n>>\n>> \\brief Retrieve the number of bins currently stored in the Histogram\n>>\n>>\n>> (stored by, might be 'used by'?)\n>>\n>>\n>>> + * \\return Number of bins\n>>> + */\n>>> +/**\n>>> + * \\fn Histogram::total()\n>>> + * \\brief getter for number of values\n>>\n>> Same here,\n>>\n>> \\brief Retrieve the total number of values in the data set\n>>\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 upon which to cumulate\n>>\n>> s/the/The/\n>> (Capital letter to start after the parameter itself.)\n>>\n>> Reading below, does it also mean this should say \"up to which\" rather\n>> than \"upon which\"?\n>>\n>> i.e.\n>> upon which: to me, counts the values 'in' that bin.\n>> up to which: to me, counts the values up to that one...\n> \n> Also, I don't think there's a verb \"to cumulate\", is there?\n\nI wondered if it should say to 'accumulate' ... but then I doubted\nmyself ...\n\n>>> + *\n>>> + * With F(p) the cumulative frequency of the histogram, the value is 0 at\n>>\n>> What is F(p) here?\n> \n> I think this is defining it to be the cumulative frequency.\n> \n>>\n>>\n>>\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 cumulated frequency from 0 up to the specified bin\n> \n> s/cumulated/cumulative/\n> \n>>> + */\n>>> +uint64_t Histogram::cumulativeFreq(double bin) const\n>>> +{\n>>> + if (bin <= 0)\n>>> + return 0;\n>>> + else if (bin >= bins())\n>>> + return total();\n>>> + int b = static_cast(bin);\n>>> + return cumulative_[b] +\n>>> + (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>>> + if (last == UINT_MAX)\n>>> + last = cumulative_.size() - 2;\n>>> + ASSERT(first <= last);\n>>> +\n>>> + uint64_t item = q * total();\n>>> + /* Binary search to find the right bin */\n>>> + while (first < last) {\n>>> + int middle = (first + last) / 2;\n>>> + /* Is it between first and middle ? */\n>>> + if (cumulative_[middle + 1] > item)\n>>> + last = middle;\n>>> + else\n>>> + first = middle + 1;\n>>> + }\n>>> + ASSERT(item >= cumulative_[first] && item <= cumulative_[last + 1]);\n>>> +\n>>> + double frac;\n>>> + if (cumulative_[first + 1] == cumulative_[first])\n>>> + frac = 0;\n>>> + else\n>>> + frac = (item - cumulative_[first]) / (cumulative_[first + 1] - cumulative_[first]);\n>>> + return 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>>> + ASSERT(highQuantile > lowQuantile);\n>>> + /* Proportion of pixels which lies below lowQuantile */\n>>> + double lowPoint = quantile(lowQuantile);\n>>> + /* Proportion of pixels which lies below highQuantile */\n>>> + double highPoint = quantile(highQuantile, static_cast(lowPoint));\n>>> + double sumBinFreq = 0, cumulFreq = 0;\n>>> +\n>>> + for (double p_next = floor(lowPoint) + 1.0;\n>>> + p_next <= ceil(highPoint);\n>>> + lowPoint = p_next, p_next += 1.0) {\n>>> + int bin = floor(lowPoint);\n>>> + double freq = (cumulative_[bin + 1] - cumulative_[bin]) * (std::min(p_next, highPoint) - lowPoint);\n>>> +\n>>> + /* Accumulate weigthed bin */\n>>> + sumBinFreq += bin * freq;\n>>> + /* Accumulate weights */\n>>> + cumulFreq += freq;\n>>> + }\n>>> + /* add 0.5 to give an average for bin mid-points */\n>>> + return sumBinFreq / cumulFreq + 0.5;\n>>> +}\n> \n> I always meant to rewrite this so that the highPoint is found during\n> the loop, not by a separate call to quantile(). Job for another day...\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..dc7451aa\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>>> + Histogram(Span data);\n>>> + size_t bins() const { return cumulative_.size() - 1; }\n>>> + uint64_t total() const { return cumulative_[cumulative_.size() - 1]; }\n>>> + uint64_t cumulativeFreq(double bin) const;\n>>\n>> I'd make this cumulativeFrequency()\n>>\n>>> + double quantile(double q, uint32_t first = 0, uint32_t last = UINT_MAX) const;\n>>> + double interQuantileMean(double lowQuantile, double hiQuantile) const;\n>>> +\n>>> +private:\n>>> + std::vector cumulative_;\n>>\n>> I see this came from the RPi code.\n>> Do we really store 64 bit values in here? or are they only 32bit? (or\n>> smaller?)\n>>\n>> In fact, I see we now construct with a Span data, so\n>> presumably this vector can be uint32_t.\n>>\n>> We could template it to accept different sizes if that would help ...\n>> but I think supporting 32 bits is probably fine if that's the span we\n>> currently define....\n> \n> I guess 32 bits (rather than 64-bit values) is OK, though it does\n> limit you to images no larger than 4GP (Gigapixels)! Whilst I don't\n> suppose that matters for any current hardware, you might want to\n> consider what future hardware might come along (there are Gigapixel\n> images out there...). The constructor was chosen to work with the\n> statistics that come out of the Pi ISP, which gives you 32-bit bins.\n\nAha, I saw that the class also supported templates, but that didn't map\nto the underlying storage... I had wondered if the template type should\ndetermine that to be able to match the storage type to the type passed\nin at construction...\n\n\n\n> Best regards\n> \n> David\n> \n>>\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>>> diff --git a/src/ipa/raspberrypi/controller/histogram.hpp b/src/ipa/raspberrypi/controller/histogram.hpp\n>>> index 90f5ac78..fc236416 100644\n>>> --- a/src/ipa/raspberrypi/controller/histogram.hpp\n>>> +++ b/src/ipa/raspberrypi/controller/histogram.hpp\n>>\n>> I'm not sure if the modifications to the RPi histogram below should be\n>> in this patch.\n>>\n>> It looks like they're unrelated to the actual code move?\n>>\n>> Perhaps leave this out, and we can 'convert' RPi controller to use the\n>> 'generic' histogram separately?\n>>\n>>\n>>> @@ -10,9 +10,6 @@\n>>> #include \n>>> #include \n>>>\n>>> -// A simple histogram class, for use in particular to find \"quantiles\" and\n>>> -// averages between \"quantiles\".\n>>> -\n>>> namespace RPiController {\n>>>\n>>> class Histogram\n>>> @@ -29,12 +26,8 @@ public:\n>>> }\n>>> uint32_t Bins() const { return cumulative_.size() - 1; }\n>>> uint64_t Total() const { return cumulative_[cumulative_.size() - 1]; }\n>>> - // Cumulative frequency up to a (fractional) point in a bin.\n>>> uint64_t CumulativeFreq(double bin) const;\n>>> - // Return the (fractional) bin of the point q (0 <= q <= 1) through the\n>>> - // histogram. Optionally provide limits to help.\n>>> - double Quantile(double q, int first = -1, int last = -1) const;\n>>> - // Return the average histogram bin value between the two quantiles.\n>>> + Histogram::quantile(double q, uint32_t first = 0, uint32_t last = UINT_MAX) const;\n>>> double InterQuantileMean(double q_lo, double q_hi) const;\n>>>\n>>> private:\n>>>\n>>\n>> --\n>> Regards\n>> --\n>> Kieran\n>> _______________________________________________\n>> libcamera-devel mailing list\n>> libcamera-devel@lists.libcamera.org\n>> https://lists.libcamera.org/listinfo/libcamera-devel","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 C64CDBD224\n\tfor ;\n\tMon, 12 Apr 2021 18:54:04 +0000 (UTC)","from lancelot.ideasonboard.com (localhost [IPv6:::1])\n\tby lancelot.ideasonboard.com (Postfix) with ESMTP id 2DE66687F6;\n\tMon, 12 Apr 2021 20:54:04 +0200 (CEST)","from perceval.ideasonboard.com (perceval.ideasonboard.com\n\t[213.167.242.64])\n\tby lancelot.ideasonboard.com (Postfix) with ESMTPS id 13565602CD\n\tfor ;\n\tMon, 12 Apr 2021 20:54:02 +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 63DF23F0;\n\tMon, 12 Apr 2021 20:54:01 +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=\"oW2tdUqr\"; dkim-atps=neutral","DKIM-Signature":"v=1; a=rsa-sha256; c=relaxed/simple; d=ideasonboard.com;\n\ts=mail; t=1618253641;\n\tbh=ILw9gX7rnbMi3G7Y/UaqCaqEjruI7YgEN/3Ppr8fd2A=;\n\th=Reply-To:Subject:To:Cc:References:From:Date:In-Reply-To:From;\n\tb=oW2tdUqru6CIvNHw6ybHMysjkF3OTn0rXdX8/rNDpuEF6HdN301HMLgmqvhyPvoRe\n\t9Bpa8f42M3IXwtrA4cRHo59uhoz9XGn/+GsPevU4re3YcOELT33eZWvM9HTffVA56L\n\tse5a9aP7jx3aDZdGVqFcE9RxOdgWg6YT9+yQ3m9o=","To":"David Plowman ","References":"<20210330211210.194806-1-jeanmichel.hautbois@ideasonboard.com>\n\t<20210330211210.194806-3-jeanmichel.hautbois@ideasonboard.com>\n\t<4514990f-cd7a-7a3f-b602-e5db1cb3b33e@ideasonboard.com>\n\t","From":"Kieran Bingham ","Autocrypt":"addr=kieran.bingham@ideasonboard.com; keydata=\n\tmQINBFYE/WYBEACs1PwjMD9rgCu1hlIiUA1AXR4rv2v+BCLUq//vrX5S5bjzxKAryRf0uHat\n\tV/zwz6hiDrZuHUACDB7X8OaQcwhLaVlq6byfoBr25+hbZG7G3+5EUl9cQ7dQEdvNj6V6y/SC\n\trRanWfelwQThCHckbobWiQJfK9n7rYNcPMq9B8e9F020LFH7Kj6YmO95ewJGgLm+idg1Kb3C\n\tpotzWkXc1xmPzcQ1fvQMOfMwdS+4SNw4rY9f07Xb2K99rjMwZVDgESKIzhsDB5GY465sCsiQ\n\tcSAZRxqE49RTBq2+EQsbrQpIc8XiffAB8qexh5/QPzCmR4kJgCGeHIXBtgRj+nIkCJPZvZtf\n\tKr2EAbc6tgg6DkAEHJb+1okosV09+0+TXywYvtEop/WUOWQ+zo+Y/OBd+8Ptgt1pDRyOBzL8\n\tRXa8ZqRf0Mwg75D+dKntZeJHzPRJyrlfQokngAAs4PaFt6UfS+ypMAF37T6CeDArQC41V3ko\n\tlPn1yMsVD0p+6i3DPvA/GPIksDC4owjnzVX9kM8Zc5Cx+XoAN0w5Eqo4t6qEVbuettxx55gq\n\t8K8FieAjgjMSxngo/HST8TpFeqI5nVeq0/lqtBRQKumuIqDg+Bkr4L1V/PSB6XgQcOdhtd36\n\tOe9X9dXB8YSNt7VjOcO7BTmFn/Z8r92mSAfHXpb07YJWJosQOQARAQABtDBLaWVyYW4gQmlu\n\tZ2hhbSA8a2llcmFuLmJpbmdoYW1AaWRlYXNvbmJvYXJkLmNvbT6JAlcEEwEKAEECGwMFCwkI\n\tBwIGFQgJCgsCBBYCAwECHgECF4ACGQEWIQSQLdeYP70o/eNy1HqhHkZyEKRh/QUCXWTtygUJ\n\tCyJXZAAKCRChHkZyEKRh/f8dEACTDsbLN2nioNZMwyLuQRUAFcXNolDX48xcUXsWS2QjxaPm\n\tVsJx8Uy8aYkS85mdPBh0C83OovQR/OVbr8AxhGvYqBs3nQvbWuTl/+4od7DfK2VZOoKBAu5S\n\tQK2FYuUcikDqYcFWJ8DQnubxfE8dvzojHEkXw0sA4igINHDDFX3HJGZtLio+WpEFQtCbfTAG\n\tYZslasz1YZRbwEdSsmO3/kqy5eMnczlm8a21A3fKUo3g8oAZEFM+f4DUNzqIltg31OAB/kZS\n\tenKZQ/SWC8PmLg/ZXBrReYakxXtkP6w3FwMlzOlhGxqhIRNiAJfXJBaRhuUWzPOpEDE9q5YJ\n\tBmqQL2WJm1VSNNVxbXJHpaWMH1sA2R00vmvRrPXGwyIO0IPYeUYQa3gsy6k+En/aMQJd27dp\n\taScf9am9PFICPY5T4ppneeJLif2lyLojo0mcHOV+uyrds9XkLpp14GfTkeKPdPMrLLTsHRfH\n\tfA4I4OBpRrEPiGIZB/0im98MkGY/Mu6qxeZmYLCcgD6qz4idOvfgVOrNh+aA8HzIVR+RMW8H\n\tQGBN9f0E3kfwxuhl3omo6V7lDw8XOdmuWZNC9zPq1UfryVHANYbLGz9KJ4Aw6M+OgBC2JpkD\n\thXMdHUkC+d20dwXrwHTlrJi1YNp6rBc+xald3wsUPOZ5z8moTHUX/uPA/qhGsbkCDQRWBP1m\n\tARAAzijkb+Sau4hAncr1JjOY+KyFEdUNxRy+hqTJdJfaYihxyaj0Ee0P0zEi35CbE6lgU0Uz\n\ttih9fiUbSV3wfsWqg1Ut3/5rTKu7kLFp15kF7eqvV4uezXRD3Qu4yjv/rMmEJbbD4cTvGCYI\n\td6MDC417f7vK3hCbCVIZSp3GXxyC1LU+UQr3fFcOyCwmP9vDUR9JV0BSqHHxRDdpUXE26Dk6\n\tmhf0V1YkspE5St814ETXpEus2urZE5yJIUROlWPIL+hm3NEWfAP06vsQUyLvr/GtbOT79vXl\n\tEn1aulcYyu20dRRxhkQ6iILaURcxIAVJJKPi8dsoMnS8pB0QW12AHWuirPF0g6DiuUfPmrA5\n\tPKe56IGlpkjc8cO51lIxHkWTpCMWigRdPDexKX+Sb+W9QWK/0JjIc4t3KBaiG8O4yRX8ml2R\n\t+rxfAVKM6V769P/hWoRGdgUMgYHFpHGSgEt80OKK5HeUPy2cngDUXzwrqiM5Sz6Od0qw5pCk\n\tNlXqI0W/who0iSVM+8+RmyY0OEkxEcci7rRLsGnM15B5PjLJjh1f2ULYkv8s4SnDwMZ/kE04\n\t/UqCMK/KnX8pwXEMCjz0h6qWNpGwJ0/tYIgQJZh6bqkvBrDogAvuhf60Sogw+mH8b+PBlx1L\n\toeTK396wc+4c3BfiC6pNtUS5GpsPMMjYMk7kVvEAEQEAAYkCPAQYAQoAJgIbDBYhBJAt15g/\n\tvSj943LUeqEeRnIQpGH9BQJdizzIBQkLSKZiAAoJEKEeRnIQpGH9eYgQAJpjaWNgqNOnMTmD\n\tMJggbwjIotypzIXfhHNCeTkG7+qCDlSaBPclcPGYrTwCt0YWPU2TgGgJrVhYT20ierN8LUvj\n\t6qOPTd+Uk7NFzL65qkh80ZKNBFddx1AabQpSVQKbdcLb8OFs85kuSvFdgqZwgxA1vl4TFhNz\n\tPZ79NAmXLackAx3sOVFhk4WQaKRshCB7cSl+RIng5S/ThOBlwNlcKG7j7W2MC06BlTbdEkUp\n\tECzuuRBv8wX4OQl+hbWbB/VKIx5HKlLu1eypen/5lNVzSqMMIYkkZcjV2SWQyUGxSwq0O/sx\n\tS0A8/atCHUXOboUsn54qdxrVDaK+6jIAuo8JiRWctP16KjzUM7MO0/+4zllM8EY57rXrj48j\n\tsbEYX0YQnzaj+jO6kJtoZsIaYR7rMMq9aUAjyiaEZpmP1qF/2sYenDx0Fg2BSlLvLvXM0vU8\n\tpQk3kgDu7kb/7PRYrZvBsr21EIQoIjXbZxDz/o7z95frkP71EaICttZ6k9q5oxxA5WC6sTXc\n\tMW8zs8avFNuA9VpXt0YupJd2ijtZy2mpZNG02fFVXhIn4G807G7+9mhuC4XG5rKlBBUXTvPU\n\tAfYnB4JBDLmLzBFavQfvonSfbitgXwCG3vS+9HEwAjU30Bar1PEOmIbiAoMzuKeRm2LVpmq4\n\tWZw01QYHU/GUV/zHJSFk","Organization":"Ideas on Board","Message-ID":"<2baf7d11-f3a4-7db2-1873-1561f2f55b96@ideasonboard.com>","Date":"Mon, 12 Apr 2021 19:53:58 +0100","User-Agent":"Mozilla/5.0 (X11; Linux x86_64; rv:68.0) Gecko/20100101\n\tThunderbird/68.10.0","MIME-Version":"1.0","In-Reply-To":"","Content-Language":"en-GB","Subject":"Re: [libcamera-devel] [PATCH v4 2/4] WIP: ipa: ipu3: Add an\n\thistogram class","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","Cc":"libcamera devel ","Content-Type":"text/plain; charset=\"utf-8\"","Content-Transfer-Encoding":"base64","Errors-To":"libcamera-devel-bounces@lists.libcamera.org","Sender":"\"libcamera-devel\" "}},{"id":16214,"web_url":"https://patchwork.libcamera.org/comment/16214/","msgid":"","date":"2021-04-13T05:42:36","subject":"Re: [libcamera-devel] [PATCH v4 2/4] WIP: ipa: ipu3: Add an\n\thistogram class","submitter":{"id":75,"url":"https://patchwork.libcamera.org/api/people/75/","name":"Jean-Michel Hautbois","email":"jeanmichel.hautbois@ideasonboard.com"},"content":"Hi David, Kieran,\n\nThanks for your comments !\n\nOn 12/04/2021 20:53, Kieran Bingham wrote:\n> Hi David,\n> \n> On 12/04/2021 14:29, David Plowman wrote:\n>> Hi Jean-Michel, Kieran\n>>\n>> Happy to see this code getting some use elsewhere! I thought I could\n>> just add a couple of comments on some of our original thinking...\n\nIndeed that is your work as a start !\n\n>> On Mon, 12 Apr 2021 at 13:21, Kieran Bingham\n>> wrote:\n>>>\n>>> Hi Jean-Michel,\n>>>\n>>> in $SUBJECT\n>>>\n>>> s/an/a/\n>>>\n>>>\n>>>\n>>> On 30/03/2021 22:12, Jean-Michel Hautbois wrote:\n>>>> This class will be used at least by AGC algorithm when quantiles are\n>>>> needed for example.\n>>>>\n>>>\n>>> Is this really a Histogram class? Or is is a CumulativeFrequency class?\n>>>\n>>> I may likely be mis-interpretting or just wrong - but I thought a\n>>> histogram stored values like:\n>>>\n>>>\n>>> value 0 1 2 3 4 5 6 7 8 9\n>>> count 5 0 3 5 6 9 2 0 2 5\n>>>\n>>> Meaning that ... you can look up in the table to see that there are 5\n>>> occurrences of the value 9 in the dataset... whereas this stores:\n>>>\n>>>\n>>> value 0 1 2 3 4 5 6 7 8 9\n>>> count 5 8 8 13 19 28 30 30 32 37\n>>>\n>>>\n>>> Ok, so now I've drawn that out, I can see that the same information is\n>>> still there, as you can get the occurrences of any specific value by\n>>> subtracting from the previous 'bin'?\n>>\n>> I think you've pretty much convinced yourself why it stores cumulative\n>> frequency. Going from cumulative frequency back to per-bin values is a\n>> single subtraction. Going the other way is a loop. Given that finding\n>> \"quantiles\" is a fairly useful operation, cumulative frequencies make\n>> sense.\n> \n> Picture and a thousand words ...\n> \n> As soon as I drew out the tables I could see it... ;-)\n\nOK, as Kieran wondered and had to draw the tables, I may use your\ncomment David in the commit message ?\n\n\"This class stores a cumulative frequency histogram. Going from\ncumulative frequency back to per-bin values is a single subtraction,\nwhile going the other way is a loop.\"\n\n>>\n>>>\n>>>\n>>>> Signed-off-by: Jean-Michel Hautbois \n>>>> ---\n>>>> src/ipa/libipa/histogram.cpp | 154 +++++++++++++++++++\n>>>> src/ipa/libipa/histogram.h | 40 +++++\n>>>> src/ipa/libipa/meson.build | 2 +\n>>>> src/ipa/raspberrypi/controller/histogram.hpp | 9 +-\n>>>> 4 files changed, 197 insertions(+), 8 deletions(-)\n>>>> create mode 100644 src/ipa/libipa/histogram.cpp\n>>>> create mode 100644 src/ipa/libipa/histogram.h\n>>\n>> Will this header be includable by application code? I've sometimes\n>> found myself getting an image and then wanting to do histogram\n>> operations. (Of course, this class doesn't make the Histogram from\n>> scratch, you have to start by totting up the bins yourself, but that's\n>> not difficult and then you get means, quantiles and stuff for free...)\n> \n> libipa is not currently exposed as as a public API.\n> \n> But there's lots of code that I'd like to be more re-usable.\n> \n> The question is how do we make all the nice helpers available without\n> committing to never changing them as a public interface ...\n> \n> I know Laurent has previously discussed moving helpers to separate\n> library sections or such.\n> \n> We need to work towards being able to expose a stable API/ABI for\n> libcamera - but perhaps we could expose 'helper' libraries which don't\n> need to offer that guarantee?\n> \n\nI wish I could display the histogram in qcam too, for example.\nBut I suppose this class would only be a helper for a higher level one\nin Qt ?\n\n>>>>\n>>>> diff --git a/src/ipa/libipa/histogram.cpp b/src/ipa/libipa/histogram.cpp\n>>>> new file mode 100644\n>>>> index 00000000..46fbb940\n>>>> --- /dev/null\n>>>> +++ b/src/ipa/libipa/histogram.cpp\n>>>> @@ -0,0 +1,154 @@\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>>>> + * The Histogram class defines a standard interface for IPA algorithms. By\n>>>> + * abstracting histograms, it makes it possible to implement generic code\n>>>> + * to manage histograms regardless of their specific type.\n>>>\n>>> I don't think this defines a standard interface for IPA algorithms ;)\n>>>\n>>> I think we can drop that paragraph and keep the one below.\n>>>\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 with a bin number of intervals\n>>>\n>>> I suspect 'bin' was a previous value passed in here.\n>>>\n>>> I think we should describe how data should be passed in.\n>>> I.e. I think perhaps it should be a pre-sorted histogram or something?\n\nMmh, you are right, it should be pre-sorted...\n\n>>>\n>>>> + * \\param[in] data a reference to the histogram\n>>>\n>>> I don't think this is a reference anymore.\n>>>\n>>>> + */\n>>>> +Histogram::Histogram(Span data)\n>>>> +{\n>>>> + cumulative_.reserve(data.size());\n>>>> + cumulative_.push_back(0);\n>>>> + for (const uint32_t &value : data)\n>>>> + cumulative_.push_back(cumulative_.back() + value);\n>>>> +}\n>>>> +/**\n>>>> + * \\fn Histogram::bins()\n>>>> + * \\brief getter for number of bins\n>>>\n>>> We don't normally reference them as 'getter's even if that's what they do.\n>>>\n>>> To be consistent with other briefs, we should put something like:\n>>>\n>>> \\brief Retrieve the number of bins currently stored in the Histogram\n>>>\n>>>\n>>> (stored by, might be 'used by'?)\n>>>\n>>>\n>>>> + * \\return Number of bins\n>>>> + */\n>>>> +/**\n>>>> + * \\fn Histogram::total()\n>>>> + * \\brief getter for number of values\n>>>\n>>> Same here,\n>>>\n>>> \\brief Retrieve the total number of values in the data set\n>>>\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 upon which to cumulate\n>>>\n>>> s/the/The/\n>>> (Capital letter to start after the parameter itself.)\n>>>\n>>> Reading below, does it also mean this should say \"up to which\" rather\n>>> than \"upon which\"?\n>>>\n>>> i.e.\n>>> upon which: to me, counts the values 'in' that bin.\n>>> up to which: to me, counts the values up to that one...\n>>\n>> Also, I don't think there's a verb \"to cumulate\", is there?\n> \n> I wondered if it should say to 'accumulate' ... but then I doubted\n> myself ...\n\n:-/ Sorry for making you doubting on your vocabulary. I have to say I\nlike to translate directly from French :-p.\n\n>>>> + *\n>>>> + * With F(p) the cumulative frequency of the histogram, the value is 0 at\n>>>\n>>> What is F(p) here?\n>>\n>> I think this is defining it to be the cumulative frequency.\n\nWell, I think this is the way to define a function, \"With ... a ...\" ?\nShould I rephrase it ?\n\n>>>\n>>>\n>>>\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 cumulated frequency from 0 up to the specified bin\n>>\n>> s/cumulated/cumulative/\n>>\n>>>> + */\n>>>> +uint64_t Histogram::cumulativeFreq(double bin) const\n>>>> +{\n>>>> + if (bin <= 0)\n>>>> + return 0;\n>>>> + else if (bin >= bins())\n>>>> + return total();\n>>>> + int b = static_cast(bin);\n>>>> + return cumulative_[b] +\n>>>> + (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>>>> + if (last == UINT_MAX)\n>>>> + last = cumulative_.size() - 2;\n>>>> + ASSERT(first <= last);\n>>>> +\n>>>> + uint64_t item = q * total();\n>>>> + /* Binary search to find the right bin */\n>>>> + while (first < last) {\n>>>> + int middle = (first + last) / 2;\n>>>> + /* Is it between first and middle ? */\n>>>> + if (cumulative_[middle + 1] > item)\n>>>> + last = middle;\n>>>> + else\n>>>> + first = middle + 1;\n>>>> + }\n>>>> + ASSERT(item >= cumulative_[first] && item <= cumulative_[last + 1]);\n>>>> +\n>>>> + double frac;\n>>>> + if (cumulative_[first + 1] == cumulative_[first])\n>>>> + frac = 0;\n>>>> + else\n>>>> + frac = (item - cumulative_[first]) / (cumulative_[first + 1] - cumulative_[first]);\n>>>> + return 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>>>> + ASSERT(highQuantile > lowQuantile);\n>>>> + /* Proportion of pixels which lies below lowQuantile */\n>>>> + double lowPoint = quantile(lowQuantile);\n>>>> + /* Proportion of pixels which lies below highQuantile */\n>>>> + double highPoint = quantile(highQuantile, static_cast(lowPoint));\n>>>> + double sumBinFreq = 0, cumulFreq = 0;\n>>>> +\n>>>> + for (double p_next = floor(lowPoint) + 1.0;\n>>>> + p_next <= ceil(highPoint);\n>>>> + lowPoint = p_next, p_next += 1.0) {\n>>>> + int bin = floor(lowPoint);\n>>>> + double freq = (cumulative_[bin + 1] - cumulative_[bin]) * (std::min(p_next, highPoint) - lowPoint);\n>>>> +\n>>>> + /* Accumulate weigthed bin */\n>>>> + sumBinFreq += bin * freq;\n>>>> + /* Accumulate weights */\n>>>> + cumulFreq += freq;\n>>>> + }\n>>>> + /* add 0.5 to give an average for bin mid-points */\n>>>> + return sumBinFreq / cumulFreq + 0.5;\n>>>> +}\n>>\n>> I always meant to rewrite this so that the highPoint is found during\n>> the loop, not by a separate call to quantile(). Job for another day...\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..dc7451aa\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>>>> + Histogram(Span data);\n>>>> + size_t bins() const { return cumulative_.size() - 1; }\n>>>> + uint64_t total() const { return cumulative_[cumulative_.size() - 1]; }\n>>>> + uint64_t cumulativeFreq(double bin) const;\n>>>\n>>> I'd make this cumulativeFrequency()\n>>>\n>>>> + double quantile(double q, uint32_t first = 0, uint32_t last = UINT_MAX) const;\n>>>> + double interQuantileMean(double lowQuantile, double hiQuantile) const;\n>>>> +\n>>>> +private:\n>>>> + std::vector cumulative_;\n>>>\n>>> I see this came from the RPi code.\n>>> Do we really store 64 bit values in here? or are they only 32bit? (or\n>>> smaller?)\n>>>\n>>> In fact, I see we now construct with a Span data, so\n>>> presumably this vector can be uint32_t.\n>>>\n>>> We could template it to accept different sizes if that would help ...\n>>> but I think supporting 32 bits is probably fine if that's the span we\n>>> currently define....\n>>\n>> I guess 32 bits (rather than 64-bit values) is OK, though it does\n>> limit you to images no larger than 4GP (Gigapixels)! Whilst I don't\n>> suppose that matters for any current hardware, you might want to\n>> consider what future hardware might come along (there are Gigapixel\n>> images out there...). The constructor was chosen to work with the\n>> statistics that come out of the Pi ISP, which gives you 32-bit bins.\n> \n> Aha, I saw that the class also supported templates, but that didn't map\n> to the underlying storage... I had wondered if the template type should\n> determine that to be able to match the storage type to the type passed\n> in at construction...\n\nI started with the template type, but could not find a good enough\nreason not to specify a type.\nRockchip ISP also stores u32 for its histograms. I don't think lots of\nISPs are using u64 for the bins ?\n\n> \n> \n>> Best regards\n>>\n>> David\n>>\n>>>\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>>>> diff --git a/src/ipa/raspberrypi/controller/histogram.hpp b/src/ipa/raspberrypi/controller/histogram.hpp\n>>>> index 90f5ac78..fc236416 100644\n>>>> --- a/src/ipa/raspberrypi/controller/histogram.hpp\n>>>> +++ b/src/ipa/raspberrypi/controller/histogram.hpp\n>>>\n>>> I'm not sure if the modifications to the RPi histogram below should be\n>>> in this patch.\n>>>\n>>> It looks like they're unrelated to the actual code move?\n>>>\n>>> Perhaps leave this out, and we can 'convert' RPi controller to use the\n>>> 'generic' histogram separately?\n>>>\n>>>\n>>>> @@ -10,9 +10,6 @@\n>>>> #include \n>>>> #include \n>>>>\n>>>> -// A simple histogram class, for use in particular to find \"quantiles\" and\n>>>> -// averages between \"quantiles\".\n>>>> -\n>>>> namespace RPiController {\n>>>>\n>>>> class Histogram\n>>>> @@ -29,12 +26,8 @@ public:\n>>>> }\n>>>> uint32_t Bins() const { return cumulative_.size() - 1; }\n>>>> uint64_t Total() const { return cumulative_[cumulative_.size() - 1]; }\n>>>> - // Cumulative frequency up to a (fractional) point in a bin.\n>>>> uint64_t CumulativeFreq(double bin) const;\n>>>> - // Return the (fractional) bin of the point q (0 <= q <= 1) through the\n>>>> - // histogram. Optionally provide limits to help.\n>>>> - double Quantile(double q, int first = -1, int last = -1) const;\n>>>> - // Return the average histogram bin value between the two quantiles.\n>>>> + Histogram::quantile(double q, uint32_t first = 0, uint32_t last = UINT_MAX) const;\n>>>> double InterQuantileMean(double q_lo, double q_hi) const;\n>>>>\n>>>> private:\n>>>>\n>>>\n>>> --\n>>> Regards\n>>> --\n>>> Kieran\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 D0287BD224\n\tfor ;\n\tTue, 13 Apr 2021 05:42:39 +0000 (UTC)","from lancelot.ideasonboard.com (localhost [IPv6:::1])\n\tby lancelot.ideasonboard.com (Postfix) with ESMTP id 218A2687F4;\n\tTue, 13 Apr 2021 07:42:39 +0200 (CEST)","from perceval.ideasonboard.com (perceval.ideasonboard.com\n\t[213.167.242.64])\n\tby lancelot.ideasonboard.com (Postfix) with ESMTPS id A13A1605AE\n\tfor ;\n\tTue, 13 Apr 2021 07:42:37 +0200 (CEST)","from [IPv6:2a01:e0a:169:7140:a788:c6cf:fc9d:72e5] (unknown\n\t[IPv6:2a01:e0a:169:7140:a788:c6cf:fc9d:72e5])\n\tby perceval.ideasonboard.com (Postfix) with ESMTPSA id 152216F2;\n\tTue, 13 Apr 2021 07:42:37 +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=\"sIDWLXwK\"; dkim-atps=neutral","DKIM-Signature":"v=1; a=rsa-sha256; c=relaxed/simple; d=ideasonboard.com;\n\ts=mail; t=1618292557;\n\tbh=JmBFMjTg+IcD4gtXU6oOjGUuMNIzPzZcoSER99cMc2Q=;\n\th=Subject:To:Cc:References:From:Date:In-Reply-To:From;\n\tb=sIDWLXwKlYerPlQcuOUFQAoUO8fir7T2w+aT0MplMZVSfq81rePuq2rx5b6FPpAjr\n\tFiTwZmC4AxVy86JNT5eybKjYFTHuSBClluPxSLCtr0W2iemKBEUPWTW2ciepjFFikm\n\t9kZWAwTVy35nsGvxwTd8ZXwxq3SsAWHA7IwgBqLY=","To":"kieran.bingham@ideasonboard.com,\n\tDavid Plowman ","References":"<20210330211210.194806-1-jeanmichel.hautbois@ideasonboard.com>\n\t<20210330211210.194806-3-jeanmichel.hautbois@ideasonboard.com>\n\t<4514990f-cd7a-7a3f-b602-e5db1cb3b33e@ideasonboard.com>\n\t\n\t<2baf7d11-f3a4-7db2-1873-1561f2f55b96@ideasonboard.com>","From":"Jean-Michel Hautbois ","Message-ID":"","Date":"Tue, 13 Apr 2021 07:42:36 +0200","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":"<2baf7d11-f3a4-7db2-1873-1561f2f55b96@ideasonboard.com>","Content-Language":"en-US","Subject":"Re: [libcamera-devel] [PATCH v4 2/4] WIP: ipa: ipu3: Add an\n\thistogram class","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","Cc":"libcamera devel ","Content-Type":"text/plain; charset=\"utf-8\"","Content-Transfer-Encoding":"base64","Errors-To":"libcamera-devel-bounces@lists.libcamera.org","Sender":"\"libcamera-devel\" "}},{"id":16215,"web_url":"https://patchwork.libcamera.org/comment/16215/","msgid":"<6d85e9bd-b216-6c78-47f4-57c2ff435241@ideasonboard.com>","date":"2021-04-13T05:45:16","subject":"Re: [libcamera-devel] [PATCH v4 2/4] WIP: ipa: ipu3: Add an\n\thistogram class","submitter":{"id":75,"url":"https://patchwork.libcamera.org/api/people/75/","name":"Jean-Michel Hautbois","email":"jeanmichel.hautbois@ideasonboard.com"},"content":"On 13/04/2021 07:42, Jean-Michel Hautbois wrote:\n> Hi David, Kieran,\n> \n> Thanks for your comments !\n> \n> On 12/04/2021 20:53, Kieran Bingham wrote:\n>> Hi David,\n>>\n>> On 12/04/2021 14:29, David Plowman wrote:\n>>> Hi Jean-Michel, Kieran\n>>>\n>>> Happy to see this code getting some use elsewhere! I thought I could\n>>> just add a couple of comments on some of our original thinking...\n> \n> Indeed that is your work as a start !\n> \n>>> On Mon, 12 Apr 2021 at 13:21, Kieran Bingham\n>>> wrote:\n>>>>\n>>>> Hi Jean-Michel,\n>>>>\n>>>> in $SUBJECT\n>>>>\n>>>> s/an/a/\n>>>>\n>>>>\n>>>>\n>>>> On 30/03/2021 22:12, Jean-Michel Hautbois wrote:\n>>>>> This class will be used at least by AGC algorithm when quantiles are\n>>>>> needed for example.\n>>>>>\n>>>>\n>>>> Is this really a Histogram class? Or is is a CumulativeFrequency class?\n>>>>\n>>>> I may likely be mis-interpretting or just wrong - but I thought a\n>>>> histogram stored values like:\n>>>>\n>>>>\n>>>> value 0 1 2 3 4 5 6 7 8 9\n>>>> count 5 0 3 5 6 9 2 0 2 5\n>>>>\n>>>> Meaning that ... you can look up in the table to see that there are 5\n>>>> occurrences of the value 9 in the dataset... whereas this stores:\n>>>>\n>>>>\n>>>> value 0 1 2 3 4 5 6 7 8 9\n>>>> count 5 8 8 13 19 28 30 30 32 37\n>>>>\n>>>>\n>>>> Ok, so now I've drawn that out, I can see that the same information is\n>>>> still there, as you can get the occurrences of any specific value by\n>>>> subtracting from the previous 'bin'?\n>>>\n>>> I think you've pretty much convinced yourself why it stores cumulative\n>>> frequency. Going from cumulative frequency back to per-bin values is a\n>>> single subtraction. Going the other way is a loop. Given that finding\n>>> \"quantiles\" is a fairly useful operation, cumulative frequencies make\n>>> sense.\n>>\n>> Picture and a thousand words ...\n>>\n>> As soon as I drew out the tables I could see it... ;-)\n> \n> OK, as Kieran wondered and had to draw the tables, I may use your\n> comment David in the commit message ?\n> \n> \"This class stores a cumulative frequency histogram. Going from\n> cumulative frequency back to per-bin values is a single subtraction,\n> while going the other way is a loop.\"\n> \n>>>\n>>>>\n>>>>\n>>>>> Signed-off-by: Jean-Michel Hautbois \n>>>>> ---\n>>>>> src/ipa/libipa/histogram.cpp | 154 +++++++++++++++++++\n>>>>> src/ipa/libipa/histogram.h | 40 +++++\n>>>>> src/ipa/libipa/meson.build | 2 +\n>>>>> src/ipa/raspberrypi/controller/histogram.hpp | 9 +-\n>>>>> 4 files changed, 197 insertions(+), 8 deletions(-)\n>>>>> create mode 100644 src/ipa/libipa/histogram.cpp\n>>>>> create mode 100644 src/ipa/libipa/histogram.h\n>>>\n>>> Will this header be includable by application code? I've sometimes\n>>> found myself getting an image and then wanting to do histogram\n>>> operations. (Of course, this class doesn't make the Histogram from\n>>> scratch, you have to start by totting up the bins yourself, but that's\n>>> not difficult and then you get means, quantiles and stuff for free...)\n>>\n>> libipa is not currently exposed as as a public API.\n>>\n>> But there's lots of code that I'd like to be more re-usable.\n>>\n>> The question is how do we make all the nice helpers available without\n>> committing to never changing them as a public interface ...\n>>\n>> I know Laurent has previously discussed moving helpers to separate\n>> library sections or such.\n>>\n>> We need to work towards being able to expose a stable API/ABI for\n>> libcamera - but perhaps we could expose 'helper' libraries which don't\n>> need to offer that guarantee?\n>>\n> \n> I wish I could display the histogram in qcam too, for example.\n> But I suppose this class would only be a helper for a higher level one\n> in Qt ?\n> \n>>>>>\n>>>>> diff --git a/src/ipa/libipa/histogram.cpp b/src/ipa/libipa/histogram.cpp\n>>>>> new file mode 100644\n>>>>> index 00000000..46fbb940\n>>>>> --- /dev/null\n>>>>> +++ b/src/ipa/libipa/histogram.cpp\n>>>>> @@ -0,0 +1,154 @@\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>>>>> + * The Histogram class defines a standard interface for IPA algorithms. By\n>>>>> + * abstracting histograms, it makes it possible to implement generic code\n>>>>> + * to manage histograms regardless of their specific type.\n>>>>\n>>>> I don't think this defines a standard interface for IPA algorithms ;)\n>>>>\n>>>> I think we can drop that paragraph and keep the one below.\n>>>>\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 with a bin number of intervals\n>>>>\n>>>> I suspect 'bin' was a previous value passed in here.\n>>>>\n>>>> I think we should describe how data should be passed in.\n>>>> I.e. I think perhaps it should be a pre-sorted histogram or something?\n> \n> Mmh, you are right, it should be pre-sorted...\n> \n>>>>\n>>>>> + * \\param[in] data a reference to the histogram\n>>>>\n>>>> I don't think this is a reference anymore.\n>>>>\n>>>>> + */\n>>>>> +Histogram::Histogram(Span data)\n>>>>> +{\n>>>>> + cumulative_.reserve(data.size());\n>>>>> + cumulative_.push_back(0);\n>>>>> + for (const uint32_t &value : data)\n>>>>> + cumulative_.push_back(cumulative_.back() + value);\n>>>>> +}\n>>>>> +/**\n>>>>> + * \\fn Histogram::bins()\n>>>>> + * \\brief getter for number of bins\n>>>>\n>>>> We don't normally reference them as 'getter's even if that's what they do.\n>>>>\n>>>> To be consistent with other briefs, we should put something like:\n>>>>\n>>>> \\brief Retrieve the number of bins currently stored in the Histogram\n>>>>\n>>>>\n>>>> (stored by, might be 'used by'?)\n>>>>\n>>>>\n>>>>> + * \\return Number of bins\n>>>>> + */\n>>>>> +/**\n>>>>> + * \\fn Histogram::total()\n>>>>> + * \\brief getter for number of values\n>>>>\n>>>> Same here,\n>>>>\n>>>> \\brief Retrieve the total number of values in the data set\n>>>>\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 upon which to cumulate\n>>>>\n>>>> s/the/The/\n>>>> (Capital letter to start after the parameter itself.)\n>>>>\n>>>> Reading below, does it also mean this should say \"up to which\" rather\n>>>> than \"upon which\"?\n>>>>\n>>>> i.e.\n>>>> upon which: to me, counts the values 'in' that bin.\n>>>> up to which: to me, counts the values up to that one...\n>>>\n>>> Also, I don't think there's a verb \"to cumulate\", is there?\n>>\n>> I wondered if it should say to 'accumulate' ... but then I doubted\n>> myself ...\n> \n> :-/ Sorry for making you doubting on your vocabulary. I have to say I\n> like to translate directly from French :-p.\n> \n>>>>> + *\n>>>>> + * With F(p) the cumulative frequency of the histogram, the value is 0 at\n>>>>\n>>>> What is F(p) here?\n>>>\n>>> I think this is defining it to be the cumulative frequency.\n> \n> Well, I think this is the way to define a function, \"With ... a ...\" ?\n> Should I rephrase it ?\n> \n>>>>\n>>>>\n>>>>\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 cumulated frequency from 0 up to the specified bin\n>>>\n>>> s/cumulated/cumulative/\n>>>\n>>>>> + */\n>>>>> +uint64_t Histogram::cumulativeFreq(double bin) const\n>>>>> +{\n>>>>> + if (bin <= 0)\n>>>>> + return 0;\n>>>>> + else if (bin >= bins())\n>>>>> + return total();\n>>>>> + int b = static_cast(bin);\n>>>>> + return cumulative_[b] +\n>>>>> + (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>>>>> + if (last == UINT_MAX)\n>>>>> + last = cumulative_.size() - 2;\n>>>>> + ASSERT(first <= last);\n>>>>> +\n>>>>> + uint64_t item = q * total();\n>>>>> + /* Binary search to find the right bin */\n>>>>> + while (first < last) {\n>>>>> + int middle = (first + last) / 2;\n>>>>> + /* Is it between first and middle ? */\n>>>>> + if (cumulative_[middle + 1] > item)\n>>>>> + last = middle;\n>>>>> + else\n>>>>> + first = middle + 1;\n>>>>> + }\n>>>>> + ASSERT(item >= cumulative_[first] && item <= cumulative_[last + 1]);\n>>>>> +\n>>>>> + double frac;\n>>>>> + if (cumulative_[first + 1] == cumulative_[first])\n>>>>> + frac = 0;\n>>>>> + else\n>>>>> + frac = (item - cumulative_[first]) / (cumulative_[first + 1] - cumulative_[first]);\n>>>>> + return 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>>>>> + ASSERT(highQuantile > lowQuantile);\n>>>>> + /* Proportion of pixels which lies below lowQuantile */\n>>>>> + double lowPoint = quantile(lowQuantile);\n>>>>> + /* Proportion of pixels which lies below highQuantile */\n>>>>> + double highPoint = quantile(highQuantile, static_cast(lowPoint));\n>>>>> + double sumBinFreq = 0, cumulFreq = 0;\n>>>>> +\n>>>>> + for (double p_next = floor(lowPoint) + 1.0;\n>>>>> + p_next <= ceil(highPoint);\n>>>>> + lowPoint = p_next, p_next += 1.0) {\n>>>>> + int bin = floor(lowPoint);\n>>>>> + double freq = (cumulative_[bin + 1] - cumulative_[bin]) * (std::min(p_next, highPoint) - lowPoint);\n>>>>> +\n>>>>> + /* Accumulate weigthed bin */\n>>>>> + sumBinFreq += bin * freq;\n>>>>> + /* Accumulate weights */\n>>>>> + cumulFreq += freq;\n>>>>> + }\n>>>>> + /* add 0.5 to give an average for bin mid-points */\n>>>>> + return sumBinFreq / cumulFreq + 0.5;\n>>>>> +}\n>>>\n>>> I always meant to rewrite this so that the highPoint is found during\n>>> the loop, not by a separate call to quantile(). Job for another day...\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..dc7451aa\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>>>>> + Histogram(Span data);\n>>>>> + size_t bins() const { return cumulative_.size() - 1; }\n>>>>> + uint64_t total() const { return cumulative_[cumulative_.size() - 1]; }\n>>>>> + uint64_t cumulativeFreq(double bin) const;\n>>>>\n>>>> I'd make this cumulativeFrequency()\n>>>>\n>>>>> + double quantile(double q, uint32_t first = 0, uint32_t last = UINT_MAX) const;\n>>>>> + double interQuantileMean(double lowQuantile, double hiQuantile) const;\n>>>>> +\n>>>>> +private:\n>>>>> + std::vector cumulative_;\n>>>>\n>>>> I see this came from the RPi code.\n>>>> Do we really store 64 bit values in here? or are they only 32bit? (or\n>>>> smaller?)\n>>>>\n>>>> In fact, I see we now construct with a Span data, so\n>>>> presumably this vector can be uint32_t.\n>>>>\n>>>> We could template it to accept different sizes if that would help ...\n>>>> but I think supporting 32 bits is probably fine if that's the span we\n>>>> currently define....\n>>>\n>>> I guess 32 bits (rather than 64-bit values) is OK, though it does\n>>> limit you to images no larger than 4GP (Gigapixels)! Whilst I don't\n>>> suppose that matters for any current hardware, you might want to\n>>> consider what future hardware might come along (there are Gigapixel\n>>> images out there...). The constructor was chosen to work with the\n>>> statistics that come out of the Pi ISP, which gives you 32-bit bins.\n>>\n>> Aha, I saw that the class also supported templates, but that didn't map\n>> to the underlying storage... I had wondered if the template type should\n>> determine that to be able to match the storage type to the type passed\n>> in at construction...\n> \n> I started with the template type, but could not find a good enough\n> reason not to specify a type.\n> Rockchip ISP also stores u32 for its histograms. I don't think lots of\n> ISPs are using u64 for the bins ?\n> \n>>\n>>\n>>> Best regards\n>>>\n>>> David\n>>>\n>>>>\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>>>>> diff --git a/src/ipa/raspberrypi/controller/histogram.hpp b/src/ipa/raspberrypi/controller/histogram.hpp\n>>>>> index 90f5ac78..fc236416 100644\n>>>>> --- a/src/ipa/raspberrypi/controller/histogram.hpp\n>>>>> +++ b/src/ipa/raspberrypi/controller/histogram.hpp\n>>>>\n>>>> I'm not sure if the modifications to the RPi histogram below should be\n>>>> in this patch.\n>>>>\n>>>> It looks like they're unrelated to the actual code move?\n>>>>\n>>>> Perhaps leave this out, and we can 'convert' RPi controller to use the\n>>>> 'generic' histogram separately?\n>>>>\n>>>>\n>>>>> @@ -10,9 +10,6 @@\n>>>>> #include \n>>>>> #include \n>>>>>\n>>>>> -// A simple histogram class, for use in particular to find \"quantiles\" and\n>>>>> -// averages between \"quantiles\".\n>>>>> -\n>>>>> namespace RPiController {\n>>>>>\n>>>>> class Histogram\n>>>>> @@ -29,12 +26,8 @@ public:\n>>>>> }\n>>>>> uint32_t Bins() const { return cumulative_.size() - 1; }\n>>>>> uint64_t Total() const { return cumulative_[cumulative_.size() - 1]; }\n>>>>> - // Cumulative frequency up to a (fractional) point in a bin.\n>>>>> uint64_t CumulativeFreq(double bin) const;\n>>>>> - // Return the (fractional) bin of the point q (0 <= q <= 1) through the\n>>>>> - // histogram. Optionally provide limits to help.\n>>>>> - double Quantile(double q, int first = -1, int last = -1) const;\n>>>>> - // Return the average histogram bin value between the two quantiles.\n>>>>> + Histogram::quantile(double q, uint32_t first = 0, uint32_t last = UINT_MAX) const;\n>>>>> double InterQuantileMean(double q_lo, double q_hi) const;\n\nI just saw that I also modified the histogram.hpp file in RPi !\nThat was not intended at first... and it obviously should be removed\nfrom the patch !\n\n>>>>> private:\n>>>>>\n>>>>\n>>>> --\n>>>> Regards\n>>>> --\n>>>> Kieran\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 64C78BD1F6\n\tfor ;\n\tTue, 13 Apr 2021 05:45:18 +0000 (UTC)","from lancelot.ideasonboard.com (localhost [IPv6:::1])\n\tby lancelot.ideasonboard.com (Postfix) with ESMTP id CB755687FF;\n\tTue, 13 Apr 2021 07:45:17 +0200 (CEST)","from perceval.ideasonboard.com (perceval.ideasonboard.com\n\t[213.167.242.64])\n\tby lancelot.ideasonboard.com (Postfix) with ESMTPS id F1B3B605AE\n\tfor ;\n\tTue, 13 Apr 2021 07:45:16 +0200 (CEST)","from [IPv6:2a01:e0a:169:7140:a788:c6cf:fc9d:72e5] (unknown\n\t[IPv6:2a01:e0a:169:7140:a788:c6cf:fc9d:72e5])\n\tby perceval.ideasonboard.com (Postfix) with ESMTPSA id 6A3A96F2;\n\tTue, 13 Apr 2021 07:45:16 +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=\"sdxC3yTZ\"; dkim-atps=neutral","DKIM-Signature":"v=1; a=rsa-sha256; c=relaxed/simple; d=ideasonboard.com;\n\ts=mail; t=1618292716;\n\tbh=Kd8u0JQR0AfakKIbAGqAOcISeoesRRSC2mu4rKNjWhg=;\n\th=Subject:To:Cc:References:From:Date:In-Reply-To:From;\n\tb=sdxC3yTZ2BtpY7/u4AxNcTeE1LmYrrpHfSEtGYm750VmVsVgrPg/kdc4WzzgZvr9m\n\tnTPAqVcgh357J0lIOQkkGNLVPn6ANi4BwVzWmK2COSz3xXIHogqWTSzWZGdr8OyIV5\n\to+tbVpejfmbPfeI20HpiJ8A27Zu6XNtc51NDg/Uo=","To":"Jean-Michel Hautbois ,\n\tkieran.bingham@ideasonboard.com,\n\tDavid Plowman ","References":"<20210330211210.194806-1-jeanmichel.hautbois@ideasonboard.com>\n\t<20210330211210.194806-3-jeanmichel.hautbois@ideasonboard.com>\n\t<4514990f-cd7a-7a3f-b602-e5db1cb3b33e@ideasonboard.com>\n\t\n\t<2baf7d11-f3a4-7db2-1873-1561f2f55b96@ideasonboard.com>\n\t","From":"Jean-Michel Hautbois ","Message-ID":"<6d85e9bd-b216-6c78-47f4-57c2ff435241@ideasonboard.com>","Date":"Tue, 13 Apr 2021 07:45:16 +0200","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":"","Content-Language":"en-US","Subject":"Re: [libcamera-devel] [PATCH v4 2/4] WIP: ipa: ipu3: Add an\n\thistogram class","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","Cc":"libcamera devel ","Content-Type":"text/plain; charset=\"utf-8\"","Content-Transfer-Encoding":"base64","Errors-To":"libcamera-devel-bounces@lists.libcamera.org","Sender":"\"libcamera-devel\" "}},{"id":16230,"web_url":"https://patchwork.libcamera.org/comment/16230/","msgid":"","date":"2021-04-13T09:48:24","subject":"Re: [libcamera-devel] [PATCH v4 2/4] WIP: ipa: ipu3: Add an\n\thistogram class","submitter":{"id":4,"url":"https://patchwork.libcamera.org/api/people/4/","name":"Kieran Bingham","email":"kieran.bingham@ideasonboard.com"},"content":"Hi JM,\n\nOn 13/04/2021 06:42, Jean-Michel Hautbois wrote:\n> Hi David, Kieran,\n> \n> Thanks for your comments !\n> \n> On 12/04/2021 20:53, Kieran Bingham wrote:\n>> Hi David,\n>>\n>> On 12/04/2021 14:29, David Plowman wrote:\n>>> Hi Jean-Michel, Kieran\n>>>\n>>> Happy to see this code getting some use elsewhere! I thought I could\n>>> just add a couple of comments on some of our original thinking...\n> \n> Indeed that is your work as a start !\n> \n>>> On Mon, 12 Apr 2021 at 13:21, Kieran Bingham\n>>> wrote:\n>>>>\n>>>> Hi Jean-Michel,\n>>>>\n>>>> in $SUBJECT\n>>>>\n>>>> s/an/a/\n>>>>\n>>>>\n>>>>\n>>>> On 30/03/2021 22:12, Jean-Michel Hautbois wrote:\n>>>>> This class will be used at least by AGC algorithm when quantiles are\n>>>>> needed for example.\n>>>>>\n>>>>\n>>>> Is this really a Histogram class? Or is is a CumulativeFrequency class?\n>>>>\n>>>> I may likely be mis-interpretting or just wrong - but I thought a\n>>>> histogram stored values like:\n>>>>\n>>>>\n>>>> value 0 1 2 3 4 5 6 7 8 9\n>>>> count 5 0 3 5 6 9 2 0 2 5\n>>>>\n>>>> Meaning that ... you can look up in the table to see that there are 5\n>>>> occurrences of the value 9 in the dataset... whereas this stores:\n>>>>\n>>>>\n>>>> value 0 1 2 3 4 5 6 7 8 9\n>>>> count 5 8 8 13 19 28 30 30 32 37\n>>>>\n>>>>\n>>>> Ok, so now I've drawn that out, I can see that the same information is\n>>>> still there, as you can get the occurrences of any specific value by\n>>>> subtracting from the previous 'bin'?\n>>>\n>>> I think you've pretty much convinced yourself why it stores cumulative\n>>> frequency. Going from cumulative frequency back to per-bin values is a\n>>> single subtraction. Going the other way is a loop. Given that finding\n>>> \"quantiles\" is a fairly useful operation, cumulative frequencies make\n>>> sense.\n>>\n>> Picture and a thousand words ...\n>>\n>> As soon as I drew out the tables I could see it... ;-)\n> \n> OK, as Kieran wondered and had to draw the tables, I may use your\n> comment David in the commit message ?\n> \n> \"This class stores a cumulative frequency histogram. Going from\n> cumulative frequency back to per-bin values is a single subtraction,\n> while going the other way is a loop.\"\n\nThat sounds good but I'd leave out the last\n \", while going the other way is a loop.\"\n\n\n\n> \n>>>\n>>>>\n>>>>\n>>>>> Signed-off-by: Jean-Michel Hautbois \n>>>>> ---\n>>>>> src/ipa/libipa/histogram.cpp | 154 +++++++++++++++++++\n>>>>> src/ipa/libipa/histogram.h | 40 +++++\n>>>>> src/ipa/libipa/meson.build | 2 +\n>>>>> src/ipa/raspberrypi/controller/histogram.hpp | 9 +-\n>>>>> 4 files changed, 197 insertions(+), 8 deletions(-)\n>>>>> create mode 100644 src/ipa/libipa/histogram.cpp\n>>>>> create mode 100644 src/ipa/libipa/histogram.h\n>>>\n>>> Will this header be includable by application code? I've sometimes\n>>> found myself getting an image and then wanting to do histogram\n>>> operations. (Of course, this class doesn't make the Histogram from\n>>> scratch, you have to start by totting up the bins yourself, but that's\n>>> not difficult and then you get means, quantiles and stuff for free...)\n>>\n>> libipa is not currently exposed as as a public API.\n>>\n>> But there's lots of code that I'd like to be more re-usable.\n>>\n>> The question is how do we make all the nice helpers available without\n>> committing to never changing them as a public interface ...\n>>\n>> I know Laurent has previously discussed moving helpers to separate\n>> library sections or such.\n>>\n>> We need to work towards being able to expose a stable API/ABI for\n>> libcamera - but perhaps we could expose 'helper' libraries which don't\n>> need to offer that guarantee?\n> \n> I wish I could display the histogram in qcam too, for example.\n> But I suppose this class would only be a helper for a higher level one\n> in Qt ?\n\nI think I asked about storing histograms in image metadata to send to\napplications when available as I think they're useful data (and if\nprovided by an ISP, that's better than post-processing/counting in\nsoftware) - but Laurent stated it would be hard to define the type and\nwhat it would represent. Plus it may be a lot of data to copy if it's\nused as a control.\n\nAny thoughts here? Is it easy to define a histogram for an image as a\nmetadata control? (i.e. a span...)?\n\nWhat image metadata would we report to applications 'if we could'?\n- Brightness histogram?\n- per-channel histogram?\n\n\n>>>>> diff --git a/src/ipa/libipa/histogram.cpp b/src/ipa/libipa/histogram.cpp\n>>>>> new file mode 100644\n>>>>> index 00000000..46fbb940\n>>>>> --- /dev/null\n>>>>> +++ b/src/ipa/libipa/histogram.cpp\n>>>>> @@ -0,0 +1,154 @@\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>>>>> + * The Histogram class defines a standard interface for IPA algorithms. By\n>>>>> + * abstracting histograms, it makes it possible to implement generic code\n>>>>> + * to manage histograms regardless of their specific type.\n>>>>\n>>>> I don't think this defines a standard interface for IPA algorithms ;)\n>>>>\n>>>> I think we can drop that paragraph and keep the one below.\n>>>>\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 with a bin number of intervals\n>>>>\n>>>> I suspect 'bin' was a previous value passed in here.\n>>>>\n>>>> I think we should describe how data should be passed in.\n>>>> I.e. I think perhaps it should be a pre-sorted histogram or something?\n> \n> Mmh, you are right, it should be pre-sorted...\n> \n>>>>\n>>>>> + * \\param[in] data a reference to the histogram\n>>>>\n>>>> I don't think this is a reference anymore.\n>>>>\n>>>>> + */\n>>>>> +Histogram::Histogram(Span data)\n>>>>> +{\n>>>>> + cumulative_.reserve(data.size());\n>>>>> + cumulative_.push_back(0);\n>>>>> + for (const uint32_t &value : data)\n>>>>> + cumulative_.push_back(cumulative_.back() + value);\n>>>>> +}\n>>>>> +/**\n>>>>> + * \\fn Histogram::bins()\n>>>>> + * \\brief getter for number of bins\n>>>>\n>>>> We don't normally reference them as 'getter's even if that's what they do.\n>>>>\n>>>> To be consistent with other briefs, we should put something like:\n>>>>\n>>>> \\brief Retrieve the number of bins currently stored in the Histogram\n>>>>\n>>>>\n>>>> (stored by, might be 'used by'?)\n>>>>\n>>>>\n>>>>> + * \\return Number of bins\n>>>>> + */\n>>>>> +/**\n>>>>> + * \\fn Histogram::total()\n>>>>> + * \\brief getter for number of values\n>>>>\n>>>> Same here,\n>>>>\n>>>> \\brief Retrieve the total number of values in the data set\n>>>>\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 upon which to cumulate\n>>>>\n>>>> s/the/The/\n>>>> (Capital letter to start after the parameter itself.)\n>>>>\n>>>> Reading below, does it also mean this should say \"up to which\" rather\n>>>> than \"upon which\"?\n>>>>\n>>>> i.e.\n>>>> upon which: to me, counts the values 'in' that bin.\n>>>> up to which: to me, counts the values up to that one...\n>>>\n>>> Also, I don't think there's a verb \"to cumulate\", is there?\n>>\n>> I wondered if it should say to 'accumulate' ... but then I doubted\n>> myself ...\n> \n> :-/ Sorry for making you doubting on your vocabulary. I have to say I\n> like to translate directly from French :-p.\n> \n>>>>> + *\n>>>>> + * With F(p) the cumulative frequency of the histogram, the value is 0 at\n>>>>\n>>>> What is F(p) here?\n>>>\n>>> I think this is defining it to be the cumulative frequency.\n> \n> Well, I think this is the way to define a function, \"With ... a ...\" ?\n> Should I rephrase it ?\n\nI guess we're mixing maths and programming terms ... given that it's a\nmathematical function ... maybe that's appropriate ;-)\n\n\n\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 cumulated frequency from 0 up to the specified bin\n\nIf I try to rewrite this in a way that I would understand better I get\nthe following: (That doesn't mean what I've written is correct though,\nso take it with a pinch of salt)\n\n\"\"\"\nDetermine the cumulative frequency of the histogram up to the desired\nfractional bin position.\n\nBins are assumed to contain an evenly spread set of values, giving a\ncontinuous and monotonically increasing frequency throughout the bin.\n\nThe histogram data is stored internally as a cumulative set to optimise\nthis procedure.\n\"\"\"\n\n\n>>>\n>>> s/cumulated/cumulative/\n>>>\n>>>>> + */\n>>>>> +uint64_t Histogram::cumulativeFreq(double bin) const\n>>>>> +{\n>>>>> + if (bin <= 0)\n>>>>> + return 0;\n>>>>> + else if (bin >= bins())\n>>>>> + return total();\n>>>>> + int b = static_cast(bin);\n>>>>> + return cumulative_[b] +\n>>>>> + (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>>>>> + if (last == UINT_MAX)\n>>>>> + last = cumulative_.size() - 2;\n>>>>> + ASSERT(first <= last);\n>>>>> +\n>>>>> + uint64_t item = q * total();\n>>>>> + /* Binary search to find the right bin */\n>>>>> + while (first < last) {\n>>>>> + int middle = (first + last) / 2;\n>>>>> + /* Is it between first and middle ? */\n>>>>> + if (cumulative_[middle + 1] > item)\n>>>>> + last = middle;\n>>>>> + else\n>>>>> + first = middle + 1;\n>>>>> + }\n>>>>> + ASSERT(item >= cumulative_[first] && item <= cumulative_[last + 1]);\n>>>>> +\n>>>>> + double frac;\n>>>>> + if (cumulative_[first + 1] == cumulative_[first])\n>>>>> + frac = 0;\n>>>>> + else\n>>>>> + frac = (item - cumulative_[first]) / (cumulative_[first + 1] - cumulative_[first]);\n>>>>> + return 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>>>>> + ASSERT(highQuantile > lowQuantile);\n>>>>> + /* Proportion of pixels which lies below lowQuantile */\n>>>>> + double lowPoint = quantile(lowQuantile);\n>>>>> + /* Proportion of pixels which lies below highQuantile */\n>>>>> + double highPoint = quantile(highQuantile, static_cast(lowPoint));\n>>>>> + double sumBinFreq = 0, cumulFreq = 0;\n>>>>> +\n>>>>> + for (double p_next = floor(lowPoint) + 1.0;\n>>>>> + p_next <= ceil(highPoint);\n>>>>> + lowPoint = p_next, p_next += 1.0) {\n>>>>> + int bin = floor(lowPoint);\n>>>>> + double freq = (cumulative_[bin + 1] - cumulative_[bin]) * (std::min(p_next, highPoint) - lowPoint);\n>>>>> +\n>>>>> + /* Accumulate weigthed bin */\n\ns/weigthed/weighted/\n\n\n>>>>> + sumBinFreq += bin * freq;\n>>>>> + /* Accumulate weights */\n>>>>> + cumulFreq += freq;\n>>>>> + }\n>>>>> + /* add 0.5 to give an average for bin mid-points */\n>>>>> + return sumBinFreq / cumulFreq + 0.5;\n>>>>> +}\n>>>\n>>> I always meant to rewrite this so that the highPoint is found during\n>>> the loop, not by a separate call to quantile(). Job for another day...\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..dc7451aa\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>>>>> + Histogram(Span data);\n>>>>> + size_t bins() const { return cumulative_.size() - 1; }\n>>>>> + uint64_t total() const { return cumulative_[cumulative_.size() - 1]; }\n>>>>> + uint64_t cumulativeFreq(double bin) const;\n>>>>\n>>>> I'd make this cumulativeFrequency()\n>>>>\n>>>>> + double quantile(double q, uint32_t first = 0, uint32_t last = UINT_MAX) const;\n>>>>> + double interQuantileMean(double lowQuantile, double hiQuantile) const;\n>>>>> +\n>>>>> +private:\n>>>>> + std::vector cumulative_;\n>>>>\n>>>> I see this came from the RPi code.\n>>>> Do we really store 64 bit values in here? or are they only 32bit? (or\n>>>> smaller?)\n>>>>\n>>>> In fact, I see we now construct with a Span data, so\n>>>> presumably this vector can be uint32_t.\n>>>>\n>>>> We could template it to accept different sizes if that would help ...\n>>>> but I think supporting 32 bits is probably fine if that's the span we\n>>>> currently define....\n>>>\n>>> I guess 32 bits (rather than 64-bit values) is OK, though it does\n>>> limit you to images no larger than 4GP (Gigapixels)! Whilst I don't\n>>> suppose that matters for any current hardware, you might want to\n>>> consider what future hardware might come along (there are Gigapixel\n>>> images out there...). The constructor was chosen to work with the\n>>> statistics that come out of the Pi ISP, which gives you 32-bit bins.\n>>\n>> Aha, I saw that the class also supported templates, but that didn't map\n>> to the underlying storage... I had wondered if the template type should\n>> determine that to be able to match the storage type to the type passed\n>> in at construction...\n> \n> I started with the template type, but could not find a good enough\n> reason not to specify a type.\n> Rockchip ISP also stores u32 for its histograms. I don't think lots of\n> ISPs are using u64 for the bins ?\n\nIn fact, now I re-read this - the cumulative_ is not storing the same\ntype as the input span is it.\n\nIt's changed, as it could be bigger than the input data (as it's additive).\n\nSo ... perhaps leaving it as 64 bit might be fine?\n\nI guess we don't normally have huge amounts of bins, so the memory\nconsumption here is not going to be too exhaustive?\n\n\n--\nKieran\n\n\n>>> Best regards\n>>>\n>>> David\n>>>\n>>>>\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>>>>> diff --git a/src/ipa/raspberrypi/controller/histogram.hpp b/src/ipa/raspberrypi/controller/histogram.hpp\n>>>>> index 90f5ac78..fc236416 100644\n>>>>> --- a/src/ipa/raspberrypi/controller/histogram.hpp\n>>>>> +++ b/src/ipa/raspberrypi/controller/histogram.hpp\n>>>>\n>>>> I'm not sure if the modifications to the RPi histogram below should be\n>>>> in this patch.\n>>>>\n>>>> It looks like they're unrelated to the actual code move?\n>>>>\n>>>> Perhaps leave this out, and we can 'convert' RPi controller to use the\n>>>> 'generic' histogram separately?\n>>>>\n>>>>\n>>>>> @@ -10,9 +10,6 @@\n>>>>> #include \n>>>>> #include \n>>>>>\n>>>>> -// A simple histogram class, for use in particular to find \"quantiles\" and\n>>>>> -// averages between \"quantiles\".\n>>>>> -\n>>>>> namespace RPiController {\n>>>>>\n>>>>> class Histogram\n>>>>> @@ -29,12 +26,8 @@ public:\n>>>>> }\n>>>>> uint32_t Bins() const { return cumulative_.size() - 1; }\n>>>>> uint64_t Total() const { return cumulative_[cumulative_.size() - 1]; }\n>>>>> - // Cumulative frequency up to a (fractional) point in a bin.\n>>>>> uint64_t CumulativeFreq(double bin) const;\n>>>>> - // Return the (fractional) bin of the point q (0 <= q <= 1) through the\n>>>>> - // histogram. Optionally provide limits to help.\n>>>>> - double Quantile(double q, int first = -1, int last = -1) const;\n>>>>> - // Return the average histogram bin value between the two quantiles.\n>>>>> + Histogram::quantile(double q, uint32_t first = 0, uint32_t last = UINT_MAX) const;\n>>>>> double InterQuantileMean(double q_lo, double q_hi) const;\n>>>>>\n>>>>> private:\n>>>>>\n>>>>\n>>>> --\n>>>> Regards\n>>>> --\n>>>> Kieran\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 84ECDBD224\n\tfor ;\n\tTue, 13 Apr 2021 09:48:29 +0000 (UTC)","from lancelot.ideasonboard.com (localhost [IPv6:::1])\n\tby lancelot.ideasonboard.com (Postfix) with ESMTP id F054D687FE;\n\tTue, 13 Apr 2021 11:48:28 +0200 (CEST)","from perceval.ideasonboard.com (perceval.ideasonboard.com\n\t[213.167.242.64])\n\tby lancelot.ideasonboard.com (Postfix) with ESMTPS id BFD7F687F3\n\tfor ;\n\tTue, 13 Apr 2021 11:48:27 +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 24E588AF;\n\tTue, 13 Apr 2021 11:48:27 +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=\"ZEHNrQpX\"; dkim-atps=neutral","DKIM-Signature":"v=1; a=rsa-sha256; c=relaxed/simple; d=ideasonboard.com;\n\ts=mail; t=1618307307;\n\tbh=2hB6c84VsWPYZmcOFKFLuyDIvzZ56JvoKw6vOEpe6F4=;\n\th=Reply-To:Subject:To:Cc:References:From:Date:In-Reply-To:From;\n\tb=ZEHNrQpXpyXLgdHsWPxhwvzu6/Zk9sjrDk1DFuveoA0Zu7XUULKFPJastQ3SEiae1\n\tkw4HFAXzNCmvsAtyqZ8uPSmPosUnPU2HxKqkL2vLj77v7dqQIybSyOHmqXwvY1wPnw\n\te6zA+iFxxImFvSpPnD7PVfRTOldEHrPJv8Dj4Ivw=","To":"Jean-Michel Hautbois ,\n\tDavid Plowman ","References":"<20210330211210.194806-1-jeanmichel.hautbois@ideasonboard.com>\n\t<20210330211210.194806-3-jeanmichel.hautbois@ideasonboard.com>\n\t<4514990f-cd7a-7a3f-b602-e5db1cb3b33e@ideasonboard.com>\n\t\n\t<2baf7d11-f3a4-7db2-1873-1561f2f55b96@ideasonboard.com>\n\t","From":"Kieran Bingham ","Autocrypt":"addr=kieran.bingham@ideasonboard.com; keydata=\n\tmQINBFYE/WYBEACs1PwjMD9rgCu1hlIiUA1AXR4rv2v+BCLUq//vrX5S5bjzxKAryRf0uHat\n\tV/zwz6hiDrZuHUACDB7X8OaQcwhLaVlq6byfoBr25+hbZG7G3+5EUl9cQ7dQEdvNj6V6y/SC\n\trRanWfelwQThCHckbobWiQJfK9n7rYNcPMq9B8e9F020LFH7Kj6YmO95ewJGgLm+idg1Kb3C\n\tpotzWkXc1xmPzcQ1fvQMOfMwdS+4SNw4rY9f07Xb2K99rjMwZVDgESKIzhsDB5GY465sCsiQ\n\tcSAZRxqE49RTBq2+EQsbrQpIc8XiffAB8qexh5/QPzCmR4kJgCGeHIXBtgRj+nIkCJPZvZtf\n\tKr2EAbc6tgg6DkAEHJb+1okosV09+0+TXywYvtEop/WUOWQ+zo+Y/OBd+8Ptgt1pDRyOBzL8\n\tRXa8ZqRf0Mwg75D+dKntZeJHzPRJyrlfQokngAAs4PaFt6UfS+ypMAF37T6CeDArQC41V3ko\n\tlPn1yMsVD0p+6i3DPvA/GPIksDC4owjnzVX9kM8Zc5Cx+XoAN0w5Eqo4t6qEVbuettxx55gq\n\t8K8FieAjgjMSxngo/HST8TpFeqI5nVeq0/lqtBRQKumuIqDg+Bkr4L1V/PSB6XgQcOdhtd36\n\tOe9X9dXB8YSNt7VjOcO7BTmFn/Z8r92mSAfHXpb07YJWJosQOQARAQABtDBLaWVyYW4gQmlu\n\tZ2hhbSA8a2llcmFuLmJpbmdoYW1AaWRlYXNvbmJvYXJkLmNvbT6JAlcEEwEKAEECGwMFCwkI\n\tBwIGFQgJCgsCBBYCAwECHgECF4ACGQEWIQSQLdeYP70o/eNy1HqhHkZyEKRh/QUCXWTtygUJ\n\tCyJXZAAKCRChHkZyEKRh/f8dEACTDsbLN2nioNZMwyLuQRUAFcXNolDX48xcUXsWS2QjxaPm\n\tVsJx8Uy8aYkS85mdPBh0C83OovQR/OVbr8AxhGvYqBs3nQvbWuTl/+4od7DfK2VZOoKBAu5S\n\tQK2FYuUcikDqYcFWJ8DQnubxfE8dvzojHEkXw0sA4igINHDDFX3HJGZtLio+WpEFQtCbfTAG\n\tYZslasz1YZRbwEdSsmO3/kqy5eMnczlm8a21A3fKUo3g8oAZEFM+f4DUNzqIltg31OAB/kZS\n\tenKZQ/SWC8PmLg/ZXBrReYakxXtkP6w3FwMlzOlhGxqhIRNiAJfXJBaRhuUWzPOpEDE9q5YJ\n\tBmqQL2WJm1VSNNVxbXJHpaWMH1sA2R00vmvRrPXGwyIO0IPYeUYQa3gsy6k+En/aMQJd27dp\n\taScf9am9PFICPY5T4ppneeJLif2lyLojo0mcHOV+uyrds9XkLpp14GfTkeKPdPMrLLTsHRfH\n\tfA4I4OBpRrEPiGIZB/0im98MkGY/Mu6qxeZmYLCcgD6qz4idOvfgVOrNh+aA8HzIVR+RMW8H\n\tQGBN9f0E3kfwxuhl3omo6V7lDw8XOdmuWZNC9zPq1UfryVHANYbLGz9KJ4Aw6M+OgBC2JpkD\n\thXMdHUkC+d20dwXrwHTlrJi1YNp6rBc+xald3wsUPOZ5z8moTHUX/uPA/qhGsbkCDQRWBP1m\n\tARAAzijkb+Sau4hAncr1JjOY+KyFEdUNxRy+hqTJdJfaYihxyaj0Ee0P0zEi35CbE6lgU0Uz\n\ttih9fiUbSV3wfsWqg1Ut3/5rTKu7kLFp15kF7eqvV4uezXRD3Qu4yjv/rMmEJbbD4cTvGCYI\n\td6MDC417f7vK3hCbCVIZSp3GXxyC1LU+UQr3fFcOyCwmP9vDUR9JV0BSqHHxRDdpUXE26Dk6\n\tmhf0V1YkspE5St814ETXpEus2urZE5yJIUROlWPIL+hm3NEWfAP06vsQUyLvr/GtbOT79vXl\n\tEn1aulcYyu20dRRxhkQ6iILaURcxIAVJJKPi8dsoMnS8pB0QW12AHWuirPF0g6DiuUfPmrA5\n\tPKe56IGlpkjc8cO51lIxHkWTpCMWigRdPDexKX+Sb+W9QWK/0JjIc4t3KBaiG8O4yRX8ml2R\n\t+rxfAVKM6V769P/hWoRGdgUMgYHFpHGSgEt80OKK5HeUPy2cngDUXzwrqiM5Sz6Od0qw5pCk\n\tNlXqI0W/who0iSVM+8+RmyY0OEkxEcci7rRLsGnM15B5PjLJjh1f2ULYkv8s4SnDwMZ/kE04\n\t/UqCMK/KnX8pwXEMCjz0h6qWNpGwJ0/tYIgQJZh6bqkvBrDogAvuhf60Sogw+mH8b+PBlx1L\n\toeTK396wc+4c3BfiC6pNtUS5GpsPMMjYMk7kVvEAEQEAAYkCPAQYAQoAJgIbDBYhBJAt15g/\n\tvSj943LUeqEeRnIQpGH9BQJdizzIBQkLSKZiAAoJEKEeRnIQpGH9eYgQAJpjaWNgqNOnMTmD\n\tMJggbwjIotypzIXfhHNCeTkG7+qCDlSaBPclcPGYrTwCt0YWPU2TgGgJrVhYT20ierN8LUvj\n\t6qOPTd+Uk7NFzL65qkh80ZKNBFddx1AabQpSVQKbdcLb8OFs85kuSvFdgqZwgxA1vl4TFhNz\n\tPZ79NAmXLackAx3sOVFhk4WQaKRshCB7cSl+RIng5S/ThOBlwNlcKG7j7W2MC06BlTbdEkUp\n\tECzuuRBv8wX4OQl+hbWbB/VKIx5HKlLu1eypen/5lNVzSqMMIYkkZcjV2SWQyUGxSwq0O/sx\n\tS0A8/atCHUXOboUsn54qdxrVDaK+6jIAuo8JiRWctP16KjzUM7MO0/+4zllM8EY57rXrj48j\n\tsbEYX0YQnzaj+jO6kJtoZsIaYR7rMMq9aUAjyiaEZpmP1qF/2sYenDx0Fg2BSlLvLvXM0vU8\n\tpQk3kgDu7kb/7PRYrZvBsr21EIQoIjXbZxDz/o7z95frkP71EaICttZ6k9q5oxxA5WC6sTXc\n\tMW8zs8avFNuA9VpXt0YupJd2ijtZy2mpZNG02fFVXhIn4G807G7+9mhuC4XG5rKlBBUXTvPU\n\tAfYnB4JBDLmLzBFavQfvonSfbitgXwCG3vS+9HEwAjU30Bar1PEOmIbiAoMzuKeRm2LVpmq4\n\tWZw01QYHU/GUV/zHJSFk","Organization":"Ideas on Board","Message-ID":"","Date":"Tue, 13 Apr 2021 10:48:24 +0100","User-Agent":"Mozilla/5.0 (X11; Linux x86_64; rv:68.0) Gecko/20100101\n\tThunderbird/68.10.0","MIME-Version":"1.0","In-Reply-To":"","Content-Language":"en-GB","Subject":"Re: [libcamera-devel] [PATCH v4 2/4] WIP: ipa: ipu3: Add an\n\thistogram class","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","Cc":"libcamera devel ","Content-Type":"text/plain; charset=\"utf-8\"","Content-Transfer-Encoding":"base64","Errors-To":"libcamera-devel-bounces@lists.libcamera.org","Sender":"\"libcamera-devel\" "}}]