cft

Noise Removal For A Better Fast Fourier Transformation

Creating a filtered FFT from scratch


user

Mertcan Coskun

3 years ago | 4 min read

What will we do here?

We will define what FFT is, create the code from scratch and adjust it to include a threshold which will exclude noise and output noise free results.

What is the Fast Fourier Transformation?

If you are half interested in this topic, you probably heard the smoothie metaphor for Fast Fourier Transform. If you haven’t, given a smoothie, FFT finds the recipe. It does that by running the smoothie through filters to extract each ingredient.

Fast Fourier Transformation(FFT) is a mathematical algorithm that calculates Discrete Fourier Transform(DFT) of a given sequence. The only difference between FT(Fourier Transform) and FFT is that FT considers a continuous signal while FFT takes a discrete signal as input. DFT converts a sequence into its frequency constituents just like FT does for a continuous signal.

In our case, we have a sequence of amplitudes that were sampled from a continuous audio signal. FFT turns time domain into frequency domain which let’s us identify the ingredients of our smoothie.

Let’s visualize the smoothie to imagine the process better:

Source: GeoGebra
Source: GeoGebra

What is the issue?

You weren’t expecting to receive crystal clear sin waves in real world, were you? In the real world nothing is perfect, meaning there will be noise on top of the main sin waves. This might disrupt our FFT process.

Imagine analyzing earthquake vibrations. If earthquake vibrations can be separated into “ingredients”, i.e vibrations of different speeds & amplitudes, buildings can be designed to avoid interacting with the strongest ones. But in real analysis, a lot of noise will be in earthquake vibrations.

How to deal with noise in real life?

One way to reduce the error is to record the signal for longer or try to get the recording device closer to the source (or increase the amplitude of the signal). Occasionally, neither of these methods are possible, which is when other techniques need to be employed such as windowing or time/frequency filtering. These real life solutions or complex signal processing methods aren’t in scope for this article.

Let’s work on a non-complex sample

A three piece sin wave series will be created with:

N1 = 1000 
t1 = np.random.uniform(0.0, 5.0, N1)
X1 = 1.0 * np.sin(5.0 * 2 * np.pi * t1) + 0.5 * np.sin(8.0 * 2 * np.pi * t1) + 0.6 * np.sin(10 * 2 * np.pi * t1) + 0.1 * np.random.randn(N1)

We can see the components visualized below:

With the added noise, the signal will all but disappear. Let’s take the Fast Fourier Transform of Signal + Noise and see what it looks like in the frequency domain.

Figure: Result of FFT with noise
Figure: Result of FFT with noise

As seen above, there is quite the noise in our FFT result. But we can still identify three peaks in the FFT frequency magnitude chart, also called periodograms.

We can use what is called a threshold noise filter and filter the noise out by only accepting those frequencies whose magnitudes exceed the threshold of the given quantile. Zero out all frequencies below that quantile, take the inverse FFT of it becomes the following graph.

Figure: Cleared noise and the inverse FFT.
Figure: Cleared noise and the inverse FFT.

How did we code it? Where the standard FFT algorithm calculates the amplitudes, we put a filter.

def easyFourierTransformThreshold(time, signal, frequency=None, steps=None,
sorted=False, uniform=False, CI = 99.5):
ts, Xs = sortZip(time, signal)
frequency, steps = frequencyGenerator(ts, steps)
ft = frequency[:, np.newaxis];angle = (ts - ts.min()) * 2 * np.pi * ft
Y = polarToRectangular(Xs, angle)[:, 1:] * np.diff(ts)
amplitude = np.abs(Y.sum(axis=1))
threshold = np.percentile(amplitude, CI)
for i in range(len(amplitude)):
amplitude[i] = 0 if amplitude[i] < threshold else pass
return frequency, amplitude

We have defined a threshold based on the percentage defined by the user(default 99.5). If the value is bigger than that value, it is not noise. And all the values lower than that threshold are noise and have been replaced with 0.

Let’s work on a real audio file

If sound waves can be separated into ingredients (bass and treble frequencies), we can boost the parts we care about, and hide the ones we don’t. The crackle of random noise can be removed. Maybe similar “sound recipes” can be compared (music recognition services compare recipes, not the raw audio clips).

After our exemplary time series, let’s see how our function does in a .wav file.

Figure: Real life example
Figure: Real life example

We can see the amplitudes of our example. Let’s compare the standard FFT with our Threshold FFT.

Figure: Standard FFT vs Threshold FFT
Figure: Standard FFT vs Threshold FFT

It is clearly seen that most of the signals in the original version are left out as noise. The threshold is at 95% so real signals aren’t left out as noise. The threshold should be adjusted based on the original plot. How many signals do we want in our result?

Figure: Inverse of FFT Threshold
Figure: Inverse of FFT Threshold

The inverse FFT of our Threshold FFT technique gives an easier to look at example. This is more believable that its made out of several sin waves.

Conclusion

We have learned that the Fourier Transform finds the set of cycle speeds, amplitudes and phases to match any time signal. We have learned that it turns the time domain the frequency domain.

We also learned that noise might exist in signals and might play with our results. To combat this, I introduced threshold filtering to standard FFT code and got noise free results which turned into nice looking inverse FFT outputs.

Upvote


user
Created by

Mertcan Coskun


people
Post

Upvote

Downvote

Comment

Bookmark

Share


Related Articles