If you look at the large version, you can see a train crossing the bay.

A rolling average is a common way to implement a low-pass filter in software. Samples are placed in a queue. Each time there is a new data sample, the oldest data in the queue is removed and the new sample added. This filter works great for removing noise caused by electrical interference, but only if that signal is mostly static. If the signal changes this filter method introduces phase-shift.

Here is a plot of the phase-shift introduced by a rolling average filter. The average is taken over 5% of the total data. Note that the filtered signal always levels off to the true signal once the slope becomes zero.

This is the equation for the mean average. *x*_{i} is the array of data to average, and *n* is the number of samples to average together. The value of *n* determines the cut-off frequency of the low-pass filter. The only thing needed to make a mean average into a rolling is a queue for *x*_{i}.

I had a project were the voltage from a linear potentiometer provides feedback on the position of a mechanical device adjusted by a motor. The motor is either on, moving in an increasing or decreasing direction, or off. The result is that the signal from the potentiometer is either static, or increasing/decreasing at a more or less constant rate. The signal required filtering, but I couldn't live with the phase-shift caused by a plain rolling average as the inaccuracy introduced would effect where the motor would end up when commanded to stop moving. To address this problem I thought about a way to preform a rolling average on a signal that is also increasing/decreasing. I first considered that if I knew the rate of increase, I could subtract this off from the signal and use a rolling average. But the rate at which the increase/decrease occurs (the slope) differs from motor to motor, and the direction of travel. So I came up with a filter that combines linear regression with a rolling average. It will act as a low-pass filter on signals that have a constant slope.

Linear-regression takes a set of data and calculates a slope and Y-intercept that approximate the set of data. It can be thought of as calculating a line that represents the average of the data. In fact, on a data set that has zero slope (and equally spaced samples) the Y-intercept will be the mean average of the data. This is because the both the mean average and linear regression are actually instances of the polynomial regression. Linear-regression produces a 1^{st} order polynomial, while the mean average produces a 0^{th} order polynomial (i.e. a number).

For turning this into a filter we need to do three things: keep a queue of some size (like what is used in a rolling average), compute the slope and intercept from this queue, and use this computer slope and intercept to forecast what the current sample should be.

The innards start much like a plain rolling average. Samples are placed in a queue with the oldest sample being discarded when a new sample is added. Normally linear-regression is computed on a set of data points—points that contain both X and Y data. But if the samples in the queue were taken at regular intervals, the X-data can be discarded. I've written already about this in my article on one-dimensional linear-regression. This method can be used for this filtering system, and will give us a slope and Y-intercept value. We assume the oldest samples are first in the queue, and the newest samples last. So to calculate the finial output of the filter we use the slope and intercept value to make a linear equation. The linear equation represents a line average of the data, therefore any input into this equation will yield the approximate value at that time. The first sample represents the past, and the last sample represents the present. So the number of the last sample will represent the most current time, and the last sample is the size of the input queue. Our equation become as follows:

This reduces some when all parts are combine, and can be rewritten in a simplified form:

This implements quite easily in code.

double compute( double const * samples, int sampleCount )

{

//

// Calculate sums.

//

// Sum of all the samples.

double sumY = 0;

// Sum of all each sample times it's index.

double sumXY = 0;

for ( int index = 0; index < sampleCount; ++index )

{

// Accumulate two sums.

sumY += samples[ index ];

sumXY += index * samples[ index ];

}

//

// Extrapolate output.

//

sampleCount -= 1;

double result;

result = 2 * sumY;

result += 6 * sumXY;

result -= 2 * sampleCount * sumY;

result /= ( sampleCount + 1 ) * ( sampleCount + 2 );

return result;

}

{

//

// Calculate sums.

//

// Sum of all the samples.

double sumY = 0;

// Sum of all each sample times it's index.

double sumXY = 0;

for ( int index = 0; index < sampleCount; ++index )

{

// Accumulate two sums.

sumY += samples[ index ];

sumXY += index * samples[ index ];

}

//

// Extrapolate output.

//

sampleCount -= 1;

double result;

result = 2 * sumY;

result += 6 * sumXY;

result -= 2 * sampleCount * sumY;

result /= ( sampleCount + 1 ) * ( sampleCount + 2 );

return result;

}

This code will take buffer of data that is presumably a queue and return the current filtered value. Here is the complete class source code.

Here is an example of the filter in action. This signal has a significant amount of noise, but the filtered signal has significantly reduced the noise. The filter uses 5% of the total data to make a determination about the current state.

One area this filter does not handle well are changes in slope. It will add a distortion to the data should a change in slope occur. In cases where this event can be predicted, it's best simply to reset the filter logic when a slope change occurs. If the slope change can't be predicted, then an other option would be to look at standard error. When the standard error exceeds some threshold, the filter can be reset, but I won't cover that in this article.

Here is an example of the phase-shift at the change of slope. Only the true value is being filtered, and the errors after a change in slope are clearly visible. When the slope goes to zero there is a clear over/undershoot. But there is also a lag when the slope goes from to to non-zero. The more samples that are averaged together, the worse the lags during slope changes. Notice that as the filter run, it does matches the true signal exactly, even along the sloped portions of the curve—the rolling average could not do this.

The filter is significantly more computationally costly than a plain rolling-average. If a running sum is used like in my average class article then adding a new sample to the rolling-average has only two additions/subtractions, and getting the result of the average has one division. By contrast the sloped average requires 2*n*+2 additions/subtractions, *n*+5 multiplies, and 1 divide for each time the average must be computed where *n* is the number of samples to average. Adding samples has negligible overhead—just coping the data to the sample array. For this application the additional overhead is negligible and the system works quite well, but the filter may not be a drop-in replacement for some high-speed applications.

That shift at the slope change looks an awful lot like artifacts from a square wave. I wonder if these are related in any way to how a square wave is produced electronically...?

An experiment I tried shooting through a cutout of a star at some holiday lights out of focus. You can see star patterns in the blue.