Patch Detail
Show a patch.
GET /api/1.1/patches/12061/?format=api
{ "id": 12061, "url": "https://patchwork.libcamera.org/api/1.1/patches/12061/?format=api", "web_url": "https://patchwork.libcamera.org/patch/12061/", "project": { "id": 1, "url": "https://patchwork.libcamera.org/api/1.1/projects/1/?format=api", "name": "libcamera", "link_name": "libcamera", "list_id": "libcamera_core", "list_email": "libcamera-devel@lists.libcamera.org", "web_url": "", "scm_url": "", "webscm_url": "" }, "msgid": "<20210422051857.20594-3-jeanmichel.hautbois@ideasonboard.com>", "date": "2021-04-22T05:18:55", "name": "[libcamera-devel,v6,2/4] ipa: ipu3: Add a histogram class", "commit_ref": "3ebb692f323eaace79ae4932bd119df2de361650", "pull_url": null, "state": "accepted", "archived": false, "hash": "ea1b6ea0101ae426081f5361032479c9ed1e3ffd", "submitter": { "id": 75, "url": "https://patchwork.libcamera.org/api/1.1/people/75/?format=api", "name": "Jean-Michel Hautbois", "email": "jeanmichel.hautbois@ideasonboard.com" }, "delegate": null, "mbox": "https://patchwork.libcamera.org/patch/12061/mbox/", "series": [ { "id": 1960, "url": "https://patchwork.libcamera.org/api/1.1/series/1960/?format=api", "web_url": "https://patchwork.libcamera.org/project/libcamera/list/?series=1960", "date": "2021-04-22T05:18:53", "name": "Implement IPA algorithms and demo with IPU3", "version": 6, "mbox": "https://patchwork.libcamera.org/series/1960/mbox/" } ], "comments": "https://patchwork.libcamera.org/api/patches/12061/comments/", "check": "pending", "checks": "https://patchwork.libcamera.org/api/patches/12061/checks/", "tags": {}, "headers": { "Return-Path": "<libcamera-devel-bounces@lists.libcamera.org>", "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 F161ABDB15\n\tfor <parsemail@patchwork.libcamera.org>;\n\tThu, 22 Apr 2021 05:19:03 +0000 (UTC)", "from lancelot.ideasonboard.com (localhost [IPv6:::1])\n\tby lancelot.ideasonboard.com (Postfix) with ESMTP id 4AAD568859;\n\tThu, 22 Apr 2021 07:19:03 +0200 (CEST)", "from perceval.ideasonboard.com (perceval.ideasonboard.com\n\t[213.167.242.64])\n\tby lancelot.ideasonboard.com (Postfix) with ESMTPS id 00F456884B\n\tfor <libcamera-devel@lists.libcamera.org>;\n\tThu, 22 Apr 2021 07:19:01 +0200 (CEST)", "from localhost.localdomain (unknown\n\t[IPv6:2a01:e0a:169:7140:e96c:3f42:9018:e1b2])\n\tby perceval.ideasonboard.com (Postfix) with ESMTPSA id 89CC29AA;\n\tThu, 22 Apr 2021 07:19:00 +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=\"OSSWBhIO\"; dkim-atps=neutral", "DKIM-Signature": "v=1; a=rsa-sha256; c=relaxed/simple; d=ideasonboard.com;\n\ts=mail; t=1619068740;\n\tbh=vBlyRNe1V5PcVhHPCjrd/2ygKuUdp2VPbZTr6cD9jvs=;\n\th=From:To:Cc:Subject:Date:In-Reply-To:References:From;\n\tb=OSSWBhIOaHaPGBzJYE8xkDIedtyBiOdrLZ/4w6h8bp30ff9d5V+Q2HBz8zOSEnNnX\n\t1QmO/MsUtGrUgjrFevepGFGdJioZXHzmiCSFTPW0VCy4V9LrmcfrYkgf8wtUcIGMiP\n\t/fZHUgbccxf4x5BErgRzpNTrkx4sqRAod39CG77k=", "From": "Jean-Michel Hautbois <jeanmichel.hautbois@ideasonboard.com>", "To": "libcamera-devel@lists.libcamera.org", "Date": "Thu, 22 Apr 2021 07:18:55 +0200", "Message-Id": "<20210422051857.20594-3-jeanmichel.hautbois@ideasonboard.com>", "X-Mailer": "git-send-email 2.27.0", "In-Reply-To": "<20210422051857.20594-1-jeanmichel.hautbois@ideasonboard.com>", "References": "<20210422051857.20594-1-jeanmichel.hautbois@ideasonboard.com>", "MIME-Version": "1.0", "Subject": "[libcamera-devel] [PATCH v6 2/4] ipa: ipu3: Add a histogram class", "X-BeenThere": "libcamera-devel@lists.libcamera.org", "X-Mailman-Version": "2.1.29", "Precedence": "list", "List-Id": "<libcamera-devel.lists.libcamera.org>", "List-Unsubscribe": "<https://lists.libcamera.org/options/libcamera-devel>,\n\t<mailto:libcamera-devel-request@lists.libcamera.org?subject=unsubscribe>", "List-Archive": "<https://lists.libcamera.org/pipermail/libcamera-devel/>", "List-Post": "<mailto:libcamera-devel@lists.libcamera.org>", "List-Help": "<mailto:libcamera-devel-request@lists.libcamera.org?subject=help>", "List-Subscribe": "<https://lists.libcamera.org/listinfo/libcamera-devel>,\n\t<mailto:libcamera-devel-request@lists.libcamera.org?subject=subscribe>", "Content-Type": "multipart/mixed;\n\tboundary=\"===============6243043576526708944==\"", "Errors-To": "libcamera-devel-bounces@lists.libcamera.org", "Sender": "\"libcamera-devel\" <libcamera-devel-bounces@lists.libcamera.org>" }, "content": "This class will be used at least by AGC algorithm when quantiles are\nneeded for example. It stores a cumulative frequency histogram. Going from\ncumulative frequency back to per-bin values is a single subtraction, while\ngoing the other way is a loop.\n\nSigned-off-by: Jean-Michel Hautbois <jeanmichel.hautbois@ideasonboard.com>\nReviewed-by: Kieran Bingham <kieran.bingham@ideasonboard.com>\nTested-by: Jacopo Mondi <jacopo@jmondi.org>\n---\n src/ipa/libipa/histogram.cpp | 153 +++++++++++++++++++++++++++++++++++\n src/ipa/libipa/histogram.h | 40 +++++++++\n src/ipa/libipa/meson.build | 2 +\n 3 files changed, 195 insertions(+)\n create mode 100644 src/ipa/libipa/histogram.cpp\n create mode 100644 src/ipa/libipa/histogram.h", "diff": "diff --git a/src/ipa/libipa/histogram.cpp b/src/ipa/libipa/histogram.cpp\nnew file mode 100644\nindex 00000000..d4d7cfdf\n--- /dev/null\n+++ b/src/ipa/libipa/histogram.cpp\n@@ -0,0 +1,153 @@\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 <cmath>\n+\n+#include \"libcamera/internal/log.h\"\n+\n+/**\n+ * \\file histogram.h\n+ * \\brief Class to represent Histograms and manipulate them\n+ */\n+\n+namespace libcamera {\n+\n+namespace ipa {\n+\n+/**\n+ * \\class Histogram\n+ * \\brief The base class for creating histograms\n+ *\n+ * This class stores a cumulative frequency histogram, which is a mapping that\n+ * counts the cumulative number of observations in all of the bins up to the\n+ * specified bin. It can be used to find quantiles and averages between quantiles.\n+ */\n+\n+/**\n+ * \\brief Create a cumulative histogram\n+ * \\param[in] data A pre-sorted histogram to be passed\n+ */\n+Histogram::Histogram(Span<uint32_t> 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+/**\n+ * \\fn Histogram::bins()\n+ * \\brief Retrieve the number of bins currently used by the Histogram\n+ * \\return Number of bins\n+ */\n+\n+/**\n+ * \\fn Histogram::total()\n+ * \\brief Retrieve the total number of values in the data set\n+ * \\return Number of values\n+ */\n+\n+/**\n+ * \\brief Cumulative frequency up to a (fractional) point in a bin.\n+ * \\param[in] bin The bin up to which to cumulate\n+ *\n+ * With F(p) the cumulative frequency of the histogram, the value is 0 at\n+ * the bottom of the histogram, and the maximum is the number of bins.\n+ * The pixels are spread evenly throughout the “bin” in which they lie, so that\n+ * F(p) is a continuous (monotonically increasing) function.\n+ *\n+ * \\return The cumulative frequency from 0 up to the specified bin\n+ */\n+uint64_t Histogram::cumulativeFrequency(double bin) const\n+{\n+\tif (bin <= 0)\n+\t\treturn 0;\n+\telse if (bin >= bins())\n+\t\treturn total();\n+\tint b = static_cast<int32_t>(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<uint32_t>(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])\n+\t\t\t* (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 */\ndiff --git a/src/ipa/libipa/histogram.h b/src/ipa/libipa/histogram.h\nnew file mode 100644\nindex 00000000..e06f1884\n--- /dev/null\n+++ b/src/ipa/libipa/histogram.h\n@@ -0,0 +1,40 @@\n+/* SPDX-License-Identifier: BSD-2-Clause */\n+/*\n+ * Copyright (C) 2019, Raspberry Pi (Trading) Limited\n+ *\n+ * histogram.h - histogram calculation interface\n+ */\n+#ifndef __LIBCAMERA_IPA_LIBIPA_HISTOGRAM_H__\n+#define __LIBCAMERA_IPA_LIBIPA_HISTOGRAM_H__\n+\n+#include <assert.h>\n+#include <limits.h>\n+#include <stdint.h>\n+\n+#include <vector>\n+\n+#include <libcamera/span.h>\n+\n+namespace libcamera {\n+\n+namespace ipa {\n+\n+class Histogram\n+{\n+public:\n+\tHistogram(Span<uint32_t> data);\n+\tsize_t bins() const { return cumulative_.size() - 1; }\n+\tuint64_t total() const { return cumulative_[cumulative_.size() - 1]; }\n+\tuint64_t cumulativeFrequency(double bin) const;\n+\tdouble quantile(double q, uint32_t first = 0, uint32_t last = UINT_MAX) const;\n+\tdouble interQuantileMean(double lowQuantile, double hiQuantile) const;\n+\n+private:\n+\tstd::vector<uint64_t> cumulative_;\n+};\n+\n+} /* namespace ipa */\n+\n+} /* namespace libcamera */\n+\n+#endif /* __LIBCAMERA_IPA_LIBIPA_HISTOGRAM_H__ */\ndiff --git a/src/ipa/libipa/meson.build b/src/ipa/libipa/meson.build\nindex 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", "prefixes": [ "libcamera-devel", "v6", "2/4" ] }