An Introduction to Signal Smoothing

Noise is everywhere. Whether you’re sampling accelerometer data for a mobile game or trying to measure the temperature of a room, noise will be there. Even if you could remove all the noise from an input device, you’ll still have a certain degree of uncertainty. If a player has tapped on the screen, where did they really wanted to tap? All these scenarios forces to re-think about how we gather and preprocess data.

• Introduction
• Noisy Signals
• Moving Average
• Centred Moving Average
• Weighted Moving Average
• Conclusion

Introduction

Filters are mathematical and computational tools that, taken a series of observations, attempt to find the most likely signal that generated them. Filters are used to tackle the ubiquitous noise and uncertainty that permeates all sensor readings. All modern devices record user input via sensors. Whether it’s a touch screen or a joystick, mobile phones and game controllers are not immune to noise. Consequently, filters play an essential (yet somehow hidden) role in the perceived user experience.

This series on smoothing filters will introduce the most common types of techniques. Applying them to games can lead to significantly improvements in usability.

Noisy Signals

Let’s start with a very simple example which will help us to understand how noise affects signals. Imagine a sensor that is queried at fixed intervals, producing the observation  at time . If you’re a game developer, it could be the input from a controller, such as Input.GetAxis("Vertical"). If you’re an engineer, it could be the voltage reading from a potentiometer, such as analogRead(3). What these time sequences have in common is that they are affected by noise. The following chart shows the above-mentioned signal, and how it is after being affected by noise.

In this example, noise has been artificially injected into the original signal. To each point of the original signal, a random value is added:

   

When this happens, we are talking about additive noise, uniformly distributed. The noise injected here is totally independent from the original signal. Additive uniform noise is often the result of an external interference. Like picking up static with an old CTR monitor.

Moving Average

Is it possible to recover a signal that has been corrupted by noise? The answer is …it depends. It depends on the type of noise (which is a direct consequence of the process that altered the signal), and on its extent. One of the simplest technique to attenuate additive noise is called moving average. It is based on the assumption that independent noise is not going to change the underlying structure of the signal. If this is true, averaging few points should attenuate the contribution of the noise. Moving average is the name of a technique that, for each point in a signal, calculates the average of its neighbouring points. If we average (for instance) three points, the filtered signal is given by:

   

If all the observations of the signal are available, we can define moving average with window size as:

   

In the following chart, a moving average technique (with window size of 6 points) has been applied to the above-mentioned noisy sinusoid:

The original signal is almost entirely recovered. If you’re a developer, this filter can be achieved with the following (very naïve) code:

public float [] MovingAverage (float [] data, int size)
{
    float [] filter = new float [data.length];
    for (int i = points/2; i < data.length-points/2; i++)
    {
        float mean = 0;
        for (var j = -points/2; j < points/2; j++)
            mean += data[i + j];
  
        filter[i] = mean / size;
    }
    return filter;
}

Increasing the window size allows to reduce the effect of the added noise, but is also likely to cause an excessive smoothing of the original signal. Moving average, in fact, works nicely for signals that are continuous and smooth. When big changes are present, this filtering technique is likely to alter the original signal more than the noise itself:

It’s also interesting to notice that the signal is completely recovered in its linear parts. Moving average is the optimal solution when you have linear signals which are affected by additive uniform noise. Such a situation, however, is extremely fictitious. Real world applications are unlikely to have such convenient constraints.

Centred Moving Average

While presenting moving average, we have also introduced a contraint over : it has to be an odd number. This is necessary for this technique to be symmetrical. We sample an equal number of points before and after , and we count itself. This means we count points, which is indeed an odd number. If we want to use moving average with an even number , we have two possibilities. Let’s see an example by taking :

   

   

Both these expressions are valid, and there is no reason to prefer one over the other. For this reason, we can average the together to get a centered moving average. This is often referred as .

   

   

The result obtained looks very similar to a moving average centered on . But is different enough to introduce a new concept.

Weighted Moving Average

Moving average treats each point in the window with the same importance. A more reasonable approach is to value points that are further away from  less. This is what weighted moving average does, introducing a weight for each time step in the window:

   

with the additional contraint that all must sum up to .

The previous code for moving average can be corrected like this:

        for (var j = -points/2; j < points/2; j++)
            mean += data[i + j] * weights[j+points/2];

Looking back at the repeated average, we can now say that is equal to a weighted moving average with weights .

This tool is not incredibly more powerful, but at the drawback of having many more parameters to set. If you are familiar with function analysis, you might have recongised this as a very rough definition of the convolution operator. Carefully chosing the weights results in a variety of interesting effects, from edge detection to gaussian blur.

To give an example of this, we can perform a convolution of a square wave with the Mexican Hat function. To do this, all that is needed is to initialise the weights so that their shape follows this function:

   

With a piece of code like this:

float[] kernel = new float[10];
for (int i = 0; i <= kernel.length; t ++)
{
    float t = i +4;
    kernel[i] = (1-(t*t)) * Math.exp(-(t*t)/2);
}

Convolution with the Mexican Hat function allows to perform edge detection.

This technique extracts rapid changes from the data. If you’re a game developer, it can be used to detect sudden movements in the player’s input. This is the first step towards a reliable gesture detection algorithm.

Conclusion

This post introduced the problem of noisy signals, and discussed two common techniques to tackle it. It’s important to remember that there isn’t an “ultimate” technique that always works. Every algorithm has its own pros and cons. Knowing under which assumptions it has been design is essential.

The next part of this tutorial will explore how the moving average technique here introduced can be used to decompose time series. You’ll need this technique to fully understand (and possibly predict) your revenues on Steam.

Other resources

• Part 1. An Introduction to Signal Smoothing
• Part 2. Time Series Decomposition
• Part 3. The Autocorrelation Function