p_psVectorSmoothHistGaussian missing obvious optimisation

[Paul Price]

Given a histogram with bounds x, and values in the bins between the bounds, y,
p_psVectorSmoothHistGaussian uses a binary search on x to find the range for
smoothing (x_i + 5 sigma and x_i - 5 sigma). This neglects an obvious
optimisation: if psHistogram.uniform is true (as is often the case), then the
bins are uniformly distributed (i.e., they have equal spacing). This property
means that finding a bin index is a matter of linear interpolation: to find
value, use

dxInverse = (float)N / (x[N-1] - x[0])
index = (value - x[0]) * dxInverse

dxInverse could be carried in the psHistogram structure if it's useful.

Even in the event that psHistogram.uniform is false (and even if it is true), a
better algorithm than identifying the maximum and minimum bin and then summing
the values within these bins would be to simply move from the central bin (which
is known) up until we fall outside the limit, summing the bins as we go, and
then repeat on the low side. This is more efficient because we're going to sum
these bins anyway.

An even better optimisation would take advantage of the symmetrical property of
the Gaussian, like this:

Initialise the bins to their own current values
float weightAtZero = gaussian(0.0, sigma); To make sure the normalisation is
right
for (int i = 0; i < num; i++) {

weights[i] = weightAtZero;
smoothed[i] = y[i] * weightAtZero;

}
Work through the histogram
for (int i = 0; i < num; i++) {

weights[i] = 0.0;
smoothed[i] = y[i];
float distance = 0.0;
Go out until we fall off the 5 sigma limit
for (int j = i + 1; j < num && (distance = midPoint[j] - midPoint[i]) < 5 *

sigma; j++) {

Because the Gaussian is symmetrical, we can take care of both the

positive and negative side at the same time

weight = gaussian(distance, sigma);
smoothed[i] += y[j] * weight;
weights[i] += weight;
smoothed[j] += y[i] * weight;
weights[j] += weight;

}

}
Normalise by the weights
for (int i = 0; i < num; i++) {

smoothed[i] /= weights[i];

}

[gusciora@…]

I'm aware of this optimization. However,this has not been implemented yet.

[gusciora@…]

The uniform histogram stuff had been implemented for some time. I just
optimized the non-uniform code. This is not tested yet, however, that doesn't
worry me since the non-uniform code is not uesed anywhere in psLib either.

[gusciora@…]

This is coded.

[Paul Price]

Bug has been resolved.... closing.

[Paul Price]

Bugs have been fixed... closing.