[{"id":33811,"web_url":"https://patchwork.libcamera.org/comment/33811/","msgid":"<174344474740.3394313.13000075577625624912@ping.linuxembedded.co.uk>","date":"2025-03-31T18:12:27","subject":"Re: [PATCH 4/5] libipa: histogram: Fix interQuantileMean() for small\n\tranges","submitter":{"id":4,"url":"https://patchwork.libcamera.org/api/people/4/","name":"Kieran Bingham","email":"kieran.bingham@ideasonboard.com"},"content":"Quoting Stefan Klug (2025-03-24 17:07:39)\n> The interQuantileMean() is supposed to return a weighted mean value\n> between two quantiles. This works for reasonably fine histograms, but\n\nreasonably 'for' fine histograms ...\n\n> fails for coarse histograms and small quantile ranges because the weight\n> is always taken from the lower border of the bin.\n> \n> Fix that by rewriting the algorithm to calculate a lower and upper bound\n> for every (partial) bin that goes into the mean calculation and weight\n> the bins by the middle of these bounds.\n> \n> Signed-off-by: Stefan Klug \n\nI haven't given this the attention and checks through all paths here\nthat it would deserve for a full RB tag, but because you've added tests\nthat validate it, which I'll put my faith in ...\n\nAcked-by: Kieran Bingham \n\n> ---\n> src/ipa/libipa/histogram.cpp | 20 +++++++++++---------\n> 1 file changed, 11 insertions(+), 9 deletions(-)\n> \n> diff --git a/src/ipa/libipa/histogram.cpp b/src/ipa/libipa/histogram.cpp\n> index c19a4cbbf3cd..31f017af3458 100644\n> --- a/src/ipa/libipa/histogram.cpp\n> +++ b/src/ipa/libipa/histogram.cpp\n> @@ -153,22 +153,24 @@ double Histogram::interQuantileMean(double lowQuantile, double highQuantile) con\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> + double sumBinFreq = 0;\n> + double cumulFreq = 0;\n> +\n> + for (int bin = std::floor(lowPoint); bin < std::ceil(highPoint); bin++) {\n> + double lowBound = std::max(static_cast(bin), lowPoint);\n> + double highBound = std::min(static_cast(bin + 1), highPoint);\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])\n> - * (std::min(p_next, highPoint) - lowPoint);\n> + * (highBound - lowBound);\n> \n> /* Accumulate weighted bin */\n> - sumBinFreq += bin * freq;\n> + sumBinFreq += 0.5 * (highBound + lowBound) * freq;\n> +\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> + return sumBinFreq / cumulFreq;\n> }\n> \n> } /* namespace ipa */\n> -- \n> 2.43.0\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 34173C3213\n\tfor ;\n\tMon, 31 Mar 2025 18:12:32 +0000 (UTC)","from lancelot.ideasonboard.com (localhost [IPv6:::1])\n\tby lancelot.ideasonboard.com (Postfix) with ESMTP id 7BA3268985;\n\tMon, 31 Mar 2025 20:12:31 +0200 (CEST)","from perceval.ideasonboard.com (perceval.ideasonboard.com\n\t[213.167.242.64])\n\tby lancelot.ideasonboard.com (Postfix) with ESMTPS id 3D99268967\n\tfor ;\n\tMon, 31 Mar 2025 20:12:30 +0200 (CEST)","from pendragon.ideasonboard.com\n\t(cpc89244-aztw30-2-0-cust6594.18-1.cable.virginm.net [86.31.185.195])\n\tby perceval.ideasonboard.com (Postfix) with ESMTPSA id 8CF8B725;\n\tMon, 31 Mar 2025 20:10:38 +0200 (CEST)"],"Authentication-Results":"lancelot.ideasonboard.com; dkim=pass (1024-bit key;\n\tunprotected) header.d=ideasonboard.com header.i=@ideasonboard.com\n\theader.b=\"S0QRjg+A\"; dkim-atps=neutral","DKIM-Signature":"v=1; a=rsa-sha256; c=relaxed/simple; d=ideasonboard.com;\n\ts=mail; t=1743444638;\n\tbh=+UsJbYeS5wd4E2Ga0+b4gwMB2LgmgXaT07nj2xLJnxE=;\n\th=In-Reply-To:References:Subject:From:Cc:To:Date:From;\n\tb=S0QRjg+ACTdeEsjerxjETl4utqUF3XwgdoQ1E+ft0wQo/g1Rbx4bcQFIy+4fDsRwI\n\tMvkOY3Ut+ZSMpCDT/K3D6b0NenbxheHFmnrHPjFGYLjZ8VuNi13kOvn2pHqBHfXhML\n\t34fXJiCmJ7AgIIWg1c8EWVzjDcWEN1/dpXyMunjY=","Content-Type":"text/plain; charset=\"utf-8\"","MIME-Version":"1.0","Content-Transfer-Encoding":"quoted-printable","In-Reply-To":"<20250324170803.103296-5-stefan.klug@ideasonboard.com>","References":"<20250324170803.103296-1-stefan.klug@ideasonboard.com>\n\t<20250324170803.103296-5-stefan.klug@ideasonboard.com>","Subject":"Re: [PATCH 4/5] libipa: histogram: Fix interQuantileMean() for small\n\tranges","From":"Kieran Bingham ","Cc":"Stefan Klug ","To":"Stefan Klug ,\n\tlibcamera-devel@lists.libcamera.org","Date":"Mon, 31 Mar 2025 19:12:27 +0100","Message-ID":"<174344474740.3394313.13000075577625624912@ping.linuxembedded.co.uk>","User-Agent":"alot/0.10","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","Errors-To":"libcamera-devel-bounces@lists.libcamera.org","Sender":"\"libcamera-devel\" "}},{"id":33822,"web_url":"https://patchwork.libcamera.org/comment/33822/","msgid":"<20250401000214.GN14432@pendragon.ideasonboard.com>","date":"2025-04-01T00:02:14","subject":"Re: [PATCH 4/5] libipa: histogram: Fix interQuantileMean() for small\n\tranges","submitter":{"id":2,"url":"https://patchwork.libcamera.org/api/people/2/","name":"Laurent Pinchart","email":"laurent.pinchart@ideasonboard.com"},"content":"Hi Stefan,\n\nThank you for the patch.\n\nOn Mon, Mar 24, 2025 at 06:07:39PM +0100, Stefan Klug wrote:\n> The interQuantileMean() is supposed to return a weighted mean value\n> between two quantiles. This works for reasonably fine histograms, but\n> fails for coarse histograms and small quantile ranges because the weight\n> is always taken from the lower border of the bin.\n> \n> Fix that by rewriting the algorithm to calculate a lower and upper bound\n> for every (partial) bin that goes into the mean calculation and weight\n> the bins by the middle of these bounds.\n> \n> Signed-off-by: Stefan Klug \n> ---\n> src/ipa/libipa/histogram.cpp | 20 +++++++++++---------\n> 1 file changed, 11 insertions(+), 9 deletions(-)\n> \n> diff --git a/src/ipa/libipa/histogram.cpp b/src/ipa/libipa/histogram.cpp\n> index c19a4cbbf3cd..31f017af3458 100644\n> --- a/src/ipa/libipa/histogram.cpp\n> +++ b/src/ipa/libipa/histogram.cpp\n> @@ -153,22 +153,24 @@ double Histogram::interQuantileMean(double lowQuantile, double highQuantile) con\n> \tdouble lowPoint = quantile(lowQuantile);\n> \t/* Proportion of pixels which lies below highQuantile */\n> \tdouble highPoint = quantile(highQuantile, static_cast(lowPoint));\n\nThose two variables can now be const. You can write\n\n\tASSERT(highQuantile > lowQuantile);\n\t\n\t/* Proportion of pixels which lies below lowQuantile and highQuantile. */\n\tconst double lowPoint = quantile(lowQuantile);\n const double highPoint = quantile(highQuantile, static_cast(lowPoint));\n\n> -\tdouble sumBinFreq = 0, cumulFreq = 0;\n> +\tdouble sumBinFreq = 0;\n> +\tdouble cumulFreq = 0;\n> +\n\nLet's document the algorithm (and see if I understand it correctly :-)).\n\n\t/*\n\t * Calculate the mean pixel value between the low and high points by\n\t * summing all the pixels between the two points, and dividing the sum\n\t * by the number of pixels. Given the discrete nature of the histogram\n\t * data, the sum of the pixels is approximated by accummulating the\n\t * product of the bin values (calculated as the mid point of the bin) by\n\t * the number of pixels they contain, for each bin in the internal.\n\t */\n\n> +\tfor (int bin = std::floor(lowPoint); bin < std::ceil(highPoint); bin++) {\n\nIt looks like bin can be unsigned.\n\n> +\t\tdouble lowBound = std::max(static_cast(bin), lowPoint);\n\nI think you can also write\n\n\t\tdouble lowBound = std::max(bin, lowPoint);\n\nSame for the next line. Up to you. Oh, and you can make them const too.\n\n> +\t\tdouble highBound = std::min(static_cast(bin + 1), highPoint);\n\nIf I understand the code correctly, this is only meaningful for the\nfirst and last iterations. I can't easily find a better construct that\nwouldn't need to be run for each iteration, so this seems fine.\n\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> +\t\t\t* (highBound - lowBound);\n\n\t \t/*\n\t\t * The low and high quantile may not lie at bin boundaries, so\n\t\t * the first and last bins need to be weighted accordingly. The\n\t\t * best available approximation is to multiply the number of\n\t\t * pixels by the partial bin width.\n\t\t */\n\t\tconst double freq = (cumulative_[bin + 1] - cumulative_[bin])\n\t\t\t\t * (highBound - lowBound);\n\n> \n> \t\t/* Accumulate weighted bin */\n> -\t\tsumBinFreq += bin * freq;\n> +\t\tsumBinFreq += 0.5 * (highBound + lowBound) * freq;\n\nI wondered for a moment where the 0.5 came from. I think\n\n\t\tsumBinFreq += (highBound + lowBound) / 2 * freq;\n\nwould better reflect the intent.\n\n> +\n> \t\t/* Accumulate weights */\n> \t\tcumulFreq += freq;\n\nI wonder if we should rename sumBinFreq to sumPixelValues and numPixels.\n\nReviewed-by: Laurent Pinchart \n\n> \t}\n> -\t/* add 0.5 to give an average for bin mid-points */\n> -\treturn sumBinFreq / cumulFreq + 0.5;\n> +\n> +\treturn sumBinFreq / cumulFreq;\n> }\n> \n> } /* namespace ipa */","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 6A177C323E\n\tfor ;\n\tTue, 1 Apr 2025 00:02:43 +0000 (UTC)","from lancelot.ideasonboard.com (localhost [IPv6:::1])\n\tby lancelot.ideasonboard.com (Postfix) with ESMTP id C24D06897A;\n\tTue, 1 Apr 2025 02:02:42 +0200 (CEST)","from perceval.ideasonboard.com (perceval.ideasonboard.com\n\t[213.167.242.64])\n\tby lancelot.ideasonboard.com (Postfix) with ESMTPS id 672BE62C66\n\tfor ;\n\tTue, 1 Apr 2025 02:02:40 +0200 (CEST)","from pendragon.ideasonboard.com (85-76-147-224-nat.elisa-mobile.fi\n\t[85.76.147.224])\n\tby perceval.ideasonboard.com (Postfix) with ESMTPSA id EB6716A6;\n\tTue, 1 Apr 2025 02:00:47 +0200 (CEST)"],"Authentication-Results":"lancelot.ideasonboard.com; dkim=pass (1024-bit key;\n\tunprotected) header.d=ideasonboard.com header.i=@ideasonboard.com\n\theader.b=\"gzBBRaO9\"; dkim-atps=neutral","DKIM-Signature":"v=1; a=rsa-sha256; c=relaxed/simple; d=ideasonboard.com;\n\ts=mail; t=1743465648;\n\tbh=0A/x757/TBr4DnfJG2kjgKB4vdQDkVnC6FApBFscRpg=;\n\th=Date:From:To:Cc:Subject:References:In-Reply-To:From;\n\tb=gzBBRaO9iGtbvNgTCh2wrIGhrHGcZ3y5Otj3tuFL1wabPLc2JiuMgZp2ioxU0mY9S\n\tbuLji8qokvh3jOtM43wNQXlcz8GAMEadhMxG16tE49VUYrH7pimgNZtsMA7ftUxAhI\n\tWfWaeL5nLWqD7WefnNcRC+V7k8Kftwo5pLDFn4HA=","Date":"Tue, 1 Apr 2025 03:02:14 +0300","From":"Laurent Pinchart ","To":"Stefan Klug ","Cc":"libcamera-devel@lists.libcamera.org","Subject":"Re: [PATCH 4/5] libipa: histogram: Fix interQuantileMean() for small\n\tranges","Message-ID":"<20250401000214.GN14432@pendragon.ideasonboard.com>","References":"<20250324170803.103296-1-stefan.klug@ideasonboard.com>\n\t<20250324170803.103296-5-stefan.klug@ideasonboard.com>","MIME-Version":"1.0","Content-Type":"text/plain; charset=utf-8","Content-Disposition":"inline","In-Reply-To":"<20250324170803.103296-5-stefan.klug@ideasonboard.com>","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","Errors-To":"libcamera-devel-bounces@lists.libcamera.org","Sender":"\"libcamera-devel\" "}},{"id":33843,"web_url":"https://patchwork.libcamera.org/comment/33843/","msgid":"","date":"2025-04-01T10:38:52","subject":"Re: [PATCH 4/5] libipa: histogram: Fix interQuantileMean() for small\n\tranges","submitter":{"id":184,"url":"https://patchwork.libcamera.org/api/people/184/","name":"Stefan Klug","email":"stefan.klug@ideasonboard.com"},"content":"Hi Laurent,\n\nThank you for the review. \n\nOn Tue, Apr 01, 2025 at 03:02:14AM +0300, Laurent Pinchart wrote:\n> Hi Stefan,\n> \n> Thank you for the patch.\n> \n> On Mon, Mar 24, 2025 at 06:07:39PM +0100, Stefan Klug wrote:\n> > The interQuantileMean() is supposed to return a weighted mean value\n> > between two quantiles. This works for reasonably fine histograms, but\n> > fails for coarse histograms and small quantile ranges because the weight\n> > is always taken from the lower border of the bin.\n> > \n> > Fix that by rewriting the algorithm to calculate a lower and upper bound\n> > for every (partial) bin that goes into the mean calculation and weight\n> > the bins by the middle of these bounds.\n> > \n> > Signed-off-by: Stefan Klug \n> > ---\n> > src/ipa/libipa/histogram.cpp | 20 +++++++++++---------\n> > 1 file changed, 11 insertions(+), 9 deletions(-)\n> > \n> > diff --git a/src/ipa/libipa/histogram.cpp b/src/ipa/libipa/histogram.cpp\n> > index c19a4cbbf3cd..31f017af3458 100644\n> > --- a/src/ipa/libipa/histogram.cpp\n> > +++ b/src/ipa/libipa/histogram.cpp\n> > @@ -153,22 +153,24 @@ double Histogram::interQuantileMean(double lowQuantile, double highQuantile) con\n> > \tdouble lowPoint = quantile(lowQuantile);\n> > \t/* Proportion of pixels which lies below highQuantile */\n> > \tdouble highPoint = quantile(highQuantile, static_cast(lowPoint));\n> \n> Those two variables can now be const. You can write\n\nDoes that technically help in any way? On compact algorithms I didn't\nthink about putting const anywhere. Anyways I added it.\n\n> \n> \tASSERT(highQuantile > lowQuantile);\n> \t\n> \t/* Proportion of pixels which lies below lowQuantile and highQuantile. */\n> \tconst double lowPoint = quantile(lowQuantile);\n> const double highPoint = quantile(highQuantile, static_cast(lowPoint));\n> \n> > -\tdouble sumBinFreq = 0, cumulFreq = 0;\n> > +\tdouble sumBinFreq = 0;\n> > +\tdouble cumulFreq = 0;\n> > +\n> \n> Let's document the algorithm (and see if I understand it correctly :-)).\n> \n> \t/*\n> \t * Calculate the mean pixel value between the low and high points by\n> \t * summing all the pixels between the two points, and dividing the sum\n> \t * by the number of pixels. Given the discrete nature of the histogram\n> \t * data, the sum of the pixels is approximated by accummulating the\n> \t * product of the bin values (calculated as the mid point of the bin) by\n> \t * the number of pixels they contain, for each bin in the internal.\n> \t */\n\nThat nicely summarizes it. And actually it took me quite a while to\nunderstand the algorithm. So that really helps. Thanks.\n\n> \n> > +\tfor (int bin = std::floor(lowPoint); bin < std::ceil(highPoint); bin++) {\n> \n> It looks like bin can be unsigned.\n\nI don't like unsigned :-) ... anyways, changed it.\n\n> \n> > +\t\tdouble lowBound = std::max(static_cast(bin), lowPoint);\n> \n> I think you can also write\n> \n> \t\tdouble lowBound = std::max(bin, lowPoint);\n\nOh yes. that looks way nicer.\n\n> \n> Same for the next line. Up to you. Oh, and you can make them const too.\n> \n> > +\t\tdouble highBound = std::min(static_cast(bin + 1), highPoint);\n> \n> If I understand the code correctly, this is only meaningful for the\n> first and last iterations. I can't easily find a better construct that\n> wouldn't need to be run for each iteration, so this seems fine.\n> \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> > +\t\t\t* (highBound - lowBound);\n> \n> \t \t/*\n> \t\t * The low and high quantile may not lie at bin boundaries, so\n> \t\t * the first and last bins need to be weighted accordingly. The\n> \t\t * best available approximation is to multiply the number of\n> \t\t * pixels by the partial bin width.\n> \t\t */\n> \t\tconst double freq = (cumulative_[bin + 1] - cumulative_[bin])\n> \t\t\t\t * (highBound - lowBound);\n> \n> > \n> > \t\t/* Accumulate weighted bin */\n> > -\t\tsumBinFreq += bin * freq;\n> > +\t\tsumBinFreq += 0.5 * (highBound + lowBound) * freq;\n> \n> I wondered for a moment where the 0.5 came from. I think\n> \n> \t\tsumBinFreq += (highBound + lowBound) / 2 * freq;\n> \n> would better reflect the intent.\n> \n> > +\n> > \t\t/* Accumulate weights */\n> > \t\tcumulFreq += freq;\n> \n> I wonder if we should rename sumBinFreq to sumPixelValues and numPixels.\n\nDepends on the background. The math people only talk about frequency and\nwe even have a cumulativeFrequency() function. In the docs we often use\npixels as that is mostly what we count.\n\nI left it as is, as that's not wrong either.\n\n> \n> Reviewed-by: Laurent Pinchart \n\nThank you!\n\nBest regards,\nStefan\n\n> \n> > \t}\n> > -\t/* add 0.5 to give an average for bin mid-points */\n> > -\treturn sumBinFreq / cumulFreq + 0.5;\n> > +\n> > +\treturn sumBinFreq / cumulFreq;\n> > }\n> > \n> > } /* namespace ipa */\n> \n> -- \n> Regards,\n> \n> Laurent Pinchart","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 BCF24C3213\n\tfor ;\n\tTue, 1 Apr 2025 10:38:57 +0000 (UTC)","from lancelot.ideasonboard.com (localhost [IPv6:::1])\n\tby lancelot.ideasonboard.com (Postfix) with ESMTP id 9D60768986;\n\tTue, 1 Apr 2025 12:38:56 +0200 (CEST)","from perceval.ideasonboard.com (perceval.ideasonboard.com\n\t[213.167.242.64])\n\tby lancelot.ideasonboard.com (Postfix) with ESMTPS id 6C9CB68947\n\tfor ;\n\tTue, 1 Apr 2025 12:38:55 +0200 (CEST)","from ideasonboard.com (unknown\n\t[IPv6:2a00:6020:448c:6c00:14c7:4fcc:495b:719f])\n\tby perceval.ideasonboard.com (Postfix) with ESMTPSA id 468358DB;\n\tTue, 1 Apr 2025 12:37:03 +0200 (CEST)"],"Authentication-Results":"lancelot.ideasonboard.com; dkim=pass (1024-bit key;\n\tunprotected) header.d=ideasonboard.com header.i=@ideasonboard.com\n\theader.b=\"uGMcZMfD\"; dkim-atps=neutral","DKIM-Signature":"v=1; a=rsa-sha256; c=relaxed/simple; d=ideasonboard.com;\n\ts=mail; t=1743503823;\n\tbh=gawpG5zmE83QMyuNCW5PmFiU8O6hDbS4MET92APmpME=;\n\th=Date:From:To:Cc:Subject:References:In-Reply-To:From;\n\tb=uGMcZMfDDy+thGY78LbUIXVUUHikJAxWP0CD585TKkpc67XBFzf5ZYC8YH282YJap\n\t1gHbAg4tvDBvwYxmVkhMIXXlEMI+MTNRrcR3LewEB65TliNZk2zNfx7HK1VnePAosp\n\tWobm5/JSchRL5qo/G7Ys4HlfNYu4voaQ+mopWkAA=","Date":"Tue, 1 Apr 2025 12:38:52 +0200","From":"Stefan Klug ","To":"Laurent Pinchart ","Cc":"libcamera-devel@lists.libcamera.org","Subject":"Re: [PATCH 4/5] libipa: histogram: Fix interQuantileMean() for small\n\tranges","Message-ID":"","References":"<20250324170803.103296-1-stefan.klug@ideasonboard.com>\n\t<20250324170803.103296-5-stefan.klug@ideasonboard.com>\n\t<20250401000214.GN14432@pendragon.ideasonboard.com>","MIME-Version":"1.0","Content-Type":"text/plain; charset=utf-8","Content-Disposition":"inline","In-Reply-To":"<20250401000214.GN14432@pendragon.ideasonboard.com>","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","Errors-To":"libcamera-devel-bounces@lists.libcamera.org","Sender":"\"libcamera-devel\" "}},{"id":33849,"web_url":"https://patchwork.libcamera.org/comment/33849/","msgid":"<20250401132208.GC11469@pendragon.ideasonboard.com>","date":"2025-04-01T13:22:08","subject":"Re: [PATCH 4/5] libipa: histogram: Fix interQuantileMean() for small\n\tranges","submitter":{"id":2,"url":"https://patchwork.libcamera.org/api/people/2/","name":"Laurent Pinchart","email":"laurent.pinchart@ideasonboard.com"},"content":"On Tue, Apr 01, 2025 at 12:38:52PM +0200, Stefan Klug wrote:\n> On Tue, Apr 01, 2025 at 03:02:14AM +0300, Laurent Pinchart wrote:\n> > On Mon, Mar 24, 2025 at 06:07:39PM +0100, Stefan Klug wrote:\n> > > The interQuantileMean() is supposed to return a weighted mean value\n> > > between two quantiles. This works for reasonably fine histograms, but\n> > > fails for coarse histograms and small quantile ranges because the weight\n> > > is always taken from the lower border of the bin.\n> > > \n> > > Fix that by rewriting the algorithm to calculate a lower and upper bound\n> > > for every (partial) bin that goes into the mean calculation and weight\n> > > the bins by the middle of these bounds.\n> > > \n> > > Signed-off-by: Stefan Klug \n> > > ---\n> > > src/ipa/libipa/histogram.cpp | 20 +++++++++++---------\n> > > 1 file changed, 11 insertions(+), 9 deletions(-)\n> > > \n> > > diff --git a/src/ipa/libipa/histogram.cpp b/src/ipa/libipa/histogram.cpp\n> > > index c19a4cbbf3cd..31f017af3458 100644\n> > > --- a/src/ipa/libipa/histogram.cpp\n> > > +++ b/src/ipa/libipa/histogram.cpp\n> > > @@ -153,22 +153,24 @@ double Histogram::interQuantileMean(double lowQuantile, double highQuantile) con\n> > > \tdouble lowPoint = quantile(lowQuantile);\n> > > \t/* Proportion of pixels which lies below highQuantile */\n> > > \tdouble highPoint = quantile(highQuantile, static_cast(lowPoint));\n> > \n> > Those two variables can now be const. You can write\n> \n> Does that technically help in any way? On compact algorithms I didn't\n> think about putting const anywhere. Anyways I added it.\n\nIt's not mandatory. I think I like it because it shows what variables\nare not meant to be modified, and I can classify such variable\ndeclarations in my mind as aliases when reading the code.\n\n> > \n> > \tASSERT(highQuantile > lowQuantile);\n> > \t\n> > \t/* Proportion of pixels which lies below lowQuantile and highQuantile. */\n> > \tconst double lowPoint = quantile(lowQuantile);\n> > const double highPoint = quantile(highQuantile, static_cast(lowPoint));\n> > \n> > > -\tdouble sumBinFreq = 0, cumulFreq = 0;\n> > > +\tdouble sumBinFreq = 0;\n> > > +\tdouble cumulFreq = 0;\n> > > +\n> > \n> > Let's document the algorithm (and see if I understand it correctly :-)).\n> > \n> > \t/*\n> > \t * Calculate the mean pixel value between the low and high points by\n> > \t * summing all the pixels between the two points, and dividing the sum\n> > \t * by the number of pixels. Given the discrete nature of the histogram\n> > \t * data, the sum of the pixels is approximated by accummulating the\n> > \t * product of the bin values (calculated as the mid point of the bin) by\n> > \t * the number of pixels they contain, for each bin in the internal.\n> > \t */\n> \n> That nicely summarizes it. And actually it took me quite a while to\n> understand the algorithm. So that really helps. Thanks.\n\nIt took me way too long to write those few lines :-)\n\n> > \n> > > +\tfor (int bin = std::floor(lowPoint); bin < std::ceil(highPoint); bin++) {\n> > \n> > It looks like bin can be unsigned.\n> \n> I don't like unsigned :-) ... anyways, changed it.\n> \n> > \n> > > +\t\tdouble lowBound = std::max(static_cast(bin), lowPoint);\n> > \n> > I think you can also write\n> > \n> > \t\tdouble lowBound = std::max(bin, lowPoint);\n> \n> Oh yes. that looks way nicer.\n> \n> > \n> > Same for the next line. Up to you. Oh, and you can make them const too.\n> > \n> > > +\t\tdouble highBound = std::min(static_cast(bin + 1), highPoint);\n> > \n> > If I understand the code correctly, this is only meaningful for the\n> > first and last iterations. I can't easily find a better construct that\n> > wouldn't need to be run for each iteration, so this seems fine.\n> > \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> > > +\t\t\t* (highBound - lowBound);\n> > \n> > \t \t/*\n> > \t\t * The low and high quantile may not lie at bin boundaries, so\n> > \t\t * the first and last bins need to be weighted accordingly. The\n> > \t\t * best available approximation is to multiply the number of\n> > \t\t * pixels by the partial bin width.\n> > \t\t */\n> > \t\tconst double freq = (cumulative_[bin + 1] - cumulative_[bin])\n> > \t\t\t\t * (highBound - lowBound);\n> > \n> > > \n> > > \t\t/* Accumulate weighted bin */\n> > > -\t\tsumBinFreq += bin * freq;\n> > > +\t\tsumBinFreq += 0.5 * (highBound + lowBound) * freq;\n> > \n> > I wondered for a moment where the 0.5 came from. I think\n> > \n> > \t\tsumBinFreq += (highBound + lowBound) / 2 * freq;\n> > \n> > would better reflect the intent.\n> > \n> > > +\n> > > \t\t/* Accumulate weights */\n> > > \t\tcumulFreq += freq;\n> > \n> > I wonder if we should rename sumBinFreq to sumPixelValues and numPixels.\n> \n> Depends on the background. The math people only talk about frequency and\n> we even have a cumulativeFrequency() function. In the docs we often use\n> pixels as that is mostly what we count.\n> \n> I left it as is, as that's not wrong either.\n> \n> > Reviewed-by: Laurent Pinchart \n> \n> Thank you!\n> \n> > > \t}\n> > > -\t/* add 0.5 to give an average for bin mid-points */\n> > > -\treturn sumBinFreq / cumulFreq + 0.5;\n> > > +\n> > > +\treturn sumBinFreq / cumulFreq;\n> > > }\n> > > \n> > > } /* namespace ipa */","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 13448C3213\n\tfor ;\n\tTue, 1 Apr 2025 13:22:35 +0000 (UTC)","from lancelot.ideasonboard.com (localhost [IPv6:::1])\n\tby lancelot.ideasonboard.com (Postfix) with ESMTP id 3095F68985;\n\tTue, 1 Apr 2025 15:22:34 +0200 (CEST)","from perceval.ideasonboard.com (perceval.ideasonboard.com\n\t[213.167.242.64])\n\tby lancelot.ideasonboard.com (Postfix) with ESMTPS id D4C7668947\n\tfor ;\n\tTue, 1 Apr 2025 15:22:32 +0200 (CEST)","from pendragon.ideasonboard.com (81-175-209-231.bb.dnainternet.fi\n\t[81.175.209.231])\n\tby perceval.ideasonboard.com (Postfix) with ESMTPSA id 86016741;\n\tTue, 1 Apr 2025 15:20:40 +0200 (CEST)"],"Authentication-Results":"lancelot.ideasonboard.com; dkim=pass (1024-bit key;\n\tunprotected) header.d=ideasonboard.com header.i=@ideasonboard.com\n\theader.b=\"HdQvYGM2\"; dkim-atps=neutral","DKIM-Signature":"v=1; a=rsa-sha256; c=relaxed/simple; d=ideasonboard.com;\n\ts=mail; t=1743513640;\n\tbh=GR2quhmrY4OUbUKCCkYxOhUJG8ykojH9HQeTwlmawOE=;\n\th=Date:From:To:Cc:Subject:References:In-Reply-To:From;\n\tb=HdQvYGM2Unnc33zum3rru6K2qxUrFvuobkmoggK7WZfoA0H3XBVaCJ0bHrg1fBtI5\n\tIPJGkDNVhUArZC/wkOW4pSJfMxsGCrJkfibqW+QMz70ID+nB5ijPHaT3JckH9poXkD\n\t6SxIvqUVeZlpkdGzre9G/Ttcui8/pSDI9l6UcttI=","Date":"Tue, 1 Apr 2025 16:22:08 +0300","From":"Laurent Pinchart ","To":"Stefan Klug ","Cc":"libcamera-devel@lists.libcamera.org","Subject":"Re: [PATCH 4/5] libipa: histogram: Fix interQuantileMean() for small\n\tranges","Message-ID":"<20250401132208.GC11469@pendragon.ideasonboard.com>","References":"<20250324170803.103296-1-stefan.klug@ideasonboard.com>\n\t<20250324170803.103296-5-stefan.klug@ideasonboard.com>\n\t<20250401000214.GN14432@pendragon.ideasonboard.com>\n\t","MIME-Version":"1.0","Content-Type":"text/plain; charset=utf-8","Content-Disposition":"inline","In-Reply-To":"","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","Errors-To":"libcamera-devel-bounces@lists.libcamera.org","Sender":"\"libcamera-devel\" "}}]