| Message ID | 20220323135614.865252-6-kieran.bingham@ideasonboard.com |
|---|---|
| State | Superseded |
| Headers | show |
| Series |
|
| Related | show |
Hi Kieran, Thank you for the patch. On Wed, Mar 23, 2022 at 01:56:14PM +0000, Kieran Bingham via libcamera-devel wrote: > Simplify the accumulation of the total and variance with a ternary > operator. > > Signed-off-by: Kieran Bingham <kieran.bingham@ideasonboard.com> > --- > > This is optional really, it's only really a stylistic preference. > > > src/ipa/ipu3/algorithms/af.cpp | 14 ++++---------- > 1 file changed, 4 insertions(+), 10 deletions(-) > > diff --git a/src/ipa/ipu3/algorithms/af.cpp b/src/ipa/ipu3/algorithms/af.cpp > index ff5e9fb5b3c5..940ed68ea14a 100644 > --- a/src/ipa/ipu3/algorithms/af.cpp > +++ b/src/ipa/ipu3/algorithms/af.cpp > @@ -342,20 +342,14 @@ double Af::afEstimateVariance(Span<const y_table_item_t> y_items, bool isY1) > double mean; > double var_sum = 0; > > - for (auto y : y_items) { > - if (isY1) > - total += y.y1_avg; > - else > - total += y.y2_avg; > - } > + for (auto y : y_items) > + total += isY1 ? y.y1_avg : y.y2_avg; > > mean = total / y_items.size(); > > for (auto y : y_items) { > - if (isY1) > - var_sum += pow((y.y1_avg - mean), 2); > - else > - var_sum += pow((y.y2_avg - mean), 2); > + double avg = isY1 ? y.y1_avg : y.y2_avg; > + var_sum += pow((avg - mean), 2); You can drop the extra parentheses. Reviewed-by: Laurent Pinchart <laurent.pinchart@ideasonboard.com> By, this could also be optimized as double sum = 0; double sqr_sum = 0; for (auto y : y_items) { double avg = isY1 ? y.y1_avg : y.y2_avg; sum += avg; sqr_sum += avg * avg; } double mean = total / y_items.size(); return sqr_sum / y_items.size() - mean * mean; which should be more efficient, especially with a larger number of items. The algorithm is subject to numerical instability though, especially when the variance is small. The two-pass approach is numerically stable (when the number of items is small). > } > > return var_sum / static_cast<double>(y_items.size());
Quoting Laurent Pinchart (2022-03-24 01:06:20) > Hi Kieran, > > Thank you for the patch. > > On Wed, Mar 23, 2022 at 01:56:14PM +0000, Kieran Bingham via libcamera-devel wrote: > > Simplify the accumulation of the total and variance with a ternary > > operator. > > > > Signed-off-by: Kieran Bingham <kieran.bingham@ideasonboard.com> > > --- > > > > This is optional really, it's only really a stylistic preference. > > > > > > src/ipa/ipu3/algorithms/af.cpp | 14 ++++---------- > > 1 file changed, 4 insertions(+), 10 deletions(-) > > > > diff --git a/src/ipa/ipu3/algorithms/af.cpp b/src/ipa/ipu3/algorithms/af.cpp > > index ff5e9fb5b3c5..940ed68ea14a 100644 > > --- a/src/ipa/ipu3/algorithms/af.cpp > > +++ b/src/ipa/ipu3/algorithms/af.cpp > > @@ -342,20 +342,14 @@ double Af::afEstimateVariance(Span<const y_table_item_t> y_items, bool isY1) > > double mean; > > double var_sum = 0; > > > > - for (auto y : y_items) { > > - if (isY1) > > - total += y.y1_avg; > > - else > > - total += y.y2_avg; > > - } > > + for (auto y : y_items) > > + total += isY1 ? y.y1_avg : y.y2_avg; > > > > mean = total / y_items.size(); > > > > for (auto y : y_items) { > > - if (isY1) > > - var_sum += pow((y.y1_avg - mean), 2); > > - else > > - var_sum += pow((y.y2_avg - mean), 2); > > + double avg = isY1 ? y.y1_avg : y.y2_avg; > > + var_sum += pow((avg - mean), 2); > > You can drop the extra parentheses. > > Reviewed-by: Laurent Pinchart <laurent.pinchart@ideasonboard.com> > > By, this could also be optimized as > > double sum = 0; > double sqr_sum = 0; > > for (auto y : y_items) { > double avg = isY1 ? y.y1_avg : y.y2_avg; > > sum += avg; > sqr_sum += avg * avg; > } > > double mean = total / y_items.size(); > return sqr_sum / y_items.size() - mean * mean; > > which should be more efficient, especially with a larger number of > items. The algorithm is subject to numerical instability though, > especially when the variance is small. The two-pass approach is > numerically stable (when the number of items is small). I did wonder if we could get this in a single loop, but I didn't want to break any assumptions that were made on precision or overflows etc, by making fundamental changes to the operation of the code. I presume that when the variance is small, as a double has 15 decimal points I expect we're way into insignificant numbers that don't affect the overall calculation. Kate, JM, what do you think? Any preference on any of the above? -- Kieran > > > } > > > > return var_sum / static_cast<double>(y_items.size()); > > -- > Regards, > > Laurent Pinchart
Hi Kieran, On Thu, Mar 24, 2022 at 10:52:38AM +0000, Kieran Bingham wrote: > Quoting Laurent Pinchart (2022-03-24 01:06:20) > > On Wed, Mar 23, 2022 at 01:56:14PM +0000, Kieran Bingham via libcamera-devel wrote: > > > Simplify the accumulation of the total and variance with a ternary > > > operator. > > > > > > Signed-off-by: Kieran Bingham <kieran.bingham@ideasonboard.com> > > > --- > > > > > > This is optional really, it's only really a stylistic preference. > > > > > > > > > src/ipa/ipu3/algorithms/af.cpp | 14 ++++---------- > > > 1 file changed, 4 insertions(+), 10 deletions(-) > > > > > > diff --git a/src/ipa/ipu3/algorithms/af.cpp b/src/ipa/ipu3/algorithms/af.cpp > > > index ff5e9fb5b3c5..940ed68ea14a 100644 > > > --- a/src/ipa/ipu3/algorithms/af.cpp > > > +++ b/src/ipa/ipu3/algorithms/af.cpp > > > @@ -342,20 +342,14 @@ double Af::afEstimateVariance(Span<const y_table_item_t> y_items, bool isY1) > > > double mean; > > > double var_sum = 0; > > > > > > - for (auto y : y_items) { > > > - if (isY1) > > > - total += y.y1_avg; > > > - else > > > - total += y.y2_avg; > > > - } > > > + for (auto y : y_items) > > > + total += isY1 ? y.y1_avg : y.y2_avg; > > > > > > mean = total / y_items.size(); > > > > > > for (auto y : y_items) { > > > - if (isY1) > > > - var_sum += pow((y.y1_avg - mean), 2); > > > - else > > > - var_sum += pow((y.y2_avg - mean), 2); > > > + double avg = isY1 ? y.y1_avg : y.y2_avg; > > > + var_sum += pow((avg - mean), 2); > > > > You can drop the extra parentheses. > > > > Reviewed-by: Laurent Pinchart <laurent.pinchart@ideasonboard.com> > > > > By, this could also be optimized as > > > > double sum = 0; > > double sqr_sum = 0; > > > > for (auto y : y_items) { > > double avg = isY1 ? y.y1_avg : y.y2_avg; This could be a uint16_t btw. > > > > sum += avg; > > sqr_sum += avg * avg; > > } > > > > double mean = total / y_items.size(); > > return sqr_sum / y_items.size() - mean * mean; > > > > which should be more efficient, especially with a larger number of > > items. The algorithm is subject to numerical instability though, > > especially when the variance is small. The two-pass approach is > > numerically stable (when the number of items is small). > > I did wonder if we could get this in a single loop, but I didn't want to > break any assumptions that were made on precision or overflows etc, by > making fundamental changes to the operation of the code. > > I presume that when the variance is small, as a double has 15 decimal > points I expect we're way into insignificant numbers that don't affect > the overall calculation. It's not about the decimal point, see https://en.wikipedia.org/wiki/Algorithms_for_calculating_variance and https://en.wikipedia.org/wiki/Catastrophic_cancellation (I like the name "catasrophic cancellation" :-)). > Kate, JM, what do you think? Any preference on any of the above? > > > > } > > > > > > return var_sum / static_cast<double>(y_items.size());
Hi Folks, On Thu, Mar 24, 2022 at 8:24 PM Laurent Pinchart via libcamera-devel <libcamera-devel@lists.libcamera.org> wrote: > > Hi Kieran, > > On Thu, Mar 24, 2022 at 10:52:38AM +0000, Kieran Bingham wrote: > > Quoting Laurent Pinchart (2022-03-24 01:06:20) > > > On Wed, Mar 23, 2022 at 01:56:14PM +0000, Kieran Bingham via libcamera-devel wrote: > > > > Simplify the accumulation of the total and variance with a ternary > > > > operator. > > > > > > > > Signed-off-by: Kieran Bingham <kieran.bingham@ideasonboard.com> > > > > --- > > > > > > > > This is optional really, it's only really a stylistic preference. > > > > > > > > > > > > src/ipa/ipu3/algorithms/af.cpp | 14 ++++---------- > > > > 1 file changed, 4 insertions(+), 10 deletions(-) > > > > > > > > diff --git a/src/ipa/ipu3/algorithms/af.cpp b/src/ipa/ipu3/algorithms/af.cpp > > > > index ff5e9fb5b3c5..940ed68ea14a 100644 > > > > --- a/src/ipa/ipu3/algorithms/af.cpp > > > > +++ b/src/ipa/ipu3/algorithms/af.cpp > > > > @@ -342,20 +342,14 @@ double Af::afEstimateVariance(Span<const y_table_item_t> y_items, bool isY1) > > > > double mean; > > > > double var_sum = 0; > > > > > > > > - for (auto y : y_items) { > > > > - if (isY1) > > > > - total += y.y1_avg; > > > > - else > > > > - total += y.y2_avg; > > > > - } > > > > + for (auto y : y_items) > > > > + total += isY1 ? y.y1_avg : y.y2_avg; > > > > > > > > mean = total / y_items.size(); > > > > > > > > for (auto y : y_items) { > > > > - if (isY1) > > > > - var_sum += pow((y.y1_avg - mean), 2); > > > > - else > > > > - var_sum += pow((y.y2_avg - mean), 2); > > > > + double avg = isY1 ? y.y1_avg : y.y2_avg; > > > > + var_sum += pow((avg - mean), 2); > > > > > > You can drop the extra parentheses. > > > > > > Reviewed-by: Laurent Pinchart <laurent.pinchart@ideasonboard.com> > > > > > > By, this could also be optimized as > > > > > > double sum = 0; > > > double sqr_sum = 0; > > > > > > for (auto y : y_items) { > > > double avg = isY1 ? y.y1_avg : y.y2_avg; > > This could be a uint16_t btw. > > > > > > > sum += avg; > > > sqr_sum += avg * avg; > > > } > > > > > > double mean = total / y_items.size(); > > > return sqr_sum / y_items.size() - mean * mean; > > > > > > which should be more efficient, especially with a larger number of > > > items. The algorithm is subject to numerical instability though, > > > especially when the variance is small. The two-pass approach is > > > numerically stable (when the number of items is small). > > > > I did wonder if we could get this in a single loop, but I didn't want to > > break any assumptions that were made on precision or overflows etc, by > > making fundamental changes to the operation of the code. > > > > I presume that when the variance is small, as a double has 15 decimal > > points I expect we're way into insignificant numbers that don't affect > > the overall calculation. > > It's not about the decimal point, see > https://en.wikipedia.org/wiki/Algorithms_for_calculating_variance and > https://en.wikipedia.org/wiki/Catastrophic_cancellation (I like the name > "catasrophic cancellation" :-)). Thanks for JM's detailed description of the variance computation approaches. The y_table length is determined by the grid width and height. If the maximum values are used, the y_table length will be 32x24=768. (A fixed number and based on the grid configuration). Typically, the grid size is set to 16x16=256. Also, the variance value could be very small (for all white and all black images) or large (complicated patterns). A certain level of precision of the floating-point number computation is required. According to the reasons above, I think keeping it simple is good for now since y_table length is not too long. If it still impacts the performance, I can perform some survey on it to see which single pass variance approach is better. > > > Kate, JM, what do you think? Any preference on any of the above? > > > > > > } > > > > > > > > return var_sum / static_cast<double>(y_items.size()); > > -- > Regards, > > Laurent Pinchart > -- BR, Kate
diff --git a/src/ipa/ipu3/algorithms/af.cpp b/src/ipa/ipu3/algorithms/af.cpp index ff5e9fb5b3c5..940ed68ea14a 100644 --- a/src/ipa/ipu3/algorithms/af.cpp +++ b/src/ipa/ipu3/algorithms/af.cpp @@ -342,20 +342,14 @@ double Af::afEstimateVariance(Span<const y_table_item_t> y_items, bool isY1) double mean; double var_sum = 0; - for (auto y : y_items) { - if (isY1) - total += y.y1_avg; - else - total += y.y2_avg; - } + for (auto y : y_items) + total += isY1 ? y.y1_avg : y.y2_avg; mean = total / y_items.size(); for (auto y : y_items) { - if (isY1) - var_sum += pow((y.y1_avg - mean), 2); - else - var_sum += pow((y.y2_avg - mean), 2); + double avg = isY1 ? y.y1_avg : y.y2_avg; + var_sum += pow((avg - mean), 2); } return var_sum / static_cast<double>(y_items.size());
Simplify the accumulation of the total and variance with a ternary operator. Signed-off-by: Kieran Bingham <kieran.bingham@ideasonboard.com> --- This is optional really, it's only really a stylistic preference. src/ipa/ipu3/algorithms/af.cpp | 14 ++++---------- 1 file changed, 4 insertions(+), 10 deletions(-)