Newbies Guide: Fourier Transform usage in Denoise

[FranceBB]

One of the things I kept wondering in my early days as encoder years ago was why pretty much any denoiser uses the Fourier Transform.
What is it good for? Why the Fourier Transform? Those were the doubts I had in my early days, so today I'm gonna try to give a brief explanation of what I learned during the years in the hope to clarify those doubts to new encoders as well.
Let's start with operators; what is an operator? Well, there are two kinds of operators fundamentally, the derivative operator - which we're gonna call "p" - and the integrative operator - which we're gonna call "1/p". Those two operators can be used to avoid to write d/dx and other things for differential equations (we're gonna talk about them later). There are fundamentally two kind of "time", continuous time (which is the time we use in real world and it was used back in the old analog days) and discrete time (which is what we use for digital signals). Whenever we have to work with a certain system which is described by the two equations (input and output) in continuous time, it's inevitable that we're gonna end up with a differential equation. In order to avoid to deal with differential equations - which can be very hard to work with - we use a Transform to bring everything into the frequency domain, do our calculations and get the result we want, then we go back to what we wanted. A particular kind of "Operator" is the Laplace Transform which is:



As you can see, the transform expresses everything in the terms of "s" and there's no longer an f(t). The Laplace transform has many important properties; one of them is linearity which leads to the superposition of effects which is a very important property because it basically says that we can decompose our "problem" into several simple parts and then sum all the "contributions" of each and every one to get the final result. Another important property is derivability (whose dual is integrability), the theorem of the initial and final values, convolution and others. Thanks to all those things the Laplace Transform is extremely useful 'cause it turns rather difficult problems into "easily" solvable ones. So... you may wonder: why isn't it used for denoise then? Well, so far so good, but I didn't actually tell you that there's a catch. Remember when I said that the Laplace Transform was "transforming" a problem from a domain to another turning it into an easily solvable one? Well, once we solved it, we gotta go back to our original domain 'cause it would be useless to get results in the frequency domain and the problem of the Laplace Transform is exactly this: it's hard to invert. There's a formula for the Inverse Laplace Transform which is this one



however it's extremely difficult to invert it using this formula and whenever we have to invert it we use workarounds like bringing our result into expected/easy to invert forms that we know how to invert/whose invert is. Of course, this can or cannot work and although it's possible to choose a route or another for a human being, it's not so easy for a computer for which the intent is to ALWAYS be able to invert the result, no matter how complicated it is. Here comes in help the Fourier Transform which is a particular case of the Laplace Transform:



it has all the properties of the Laplace Transform but it's easy to invert:




Thanks to the fact that it's easy to invert (you can see the anti-transform above), it gained popularity across many engineering subjects including - of course - encoding. Thanks to these properties, many developers created libraries that include calculations with the Fourier Transform like FFTW upon which Avisynth/VapourSynth denoisers are based.
Lastly, it's worth remembering that at the very beginning I talked about "Continuous Time" and "Discrete Time" with the latter being the one used by digital systems; as a matter of fact the same thing applies to discrete time and what we're working with is in fact the Discrete Fourier Transform which works in discrete time (as a side note, we can say that the Zeta Transform is the dual of the Laplace Transform for Discrete Time).


So now, if you ever wondered why when you use things like:

FFMpegSource2("file.mov")
FFT3DFilter()

you need FFTW, now you can think about this topic.

As Dianna Cowern would say "maybe you knew, now you know".

[feisty2]

FFT is a linear transformation with a manually engineered kernel, so last century. lol
take a look at filterflow, we're now past the stage of learning a data-driven mapping which is already one step ahead of manually engineered kernels.
what's currently happening is learning to dynamically generate a mapping that adapts to each sample.
you're only 2 generations behind, meah

[Cary Knoop]

There are far better noise reduction methods (KNLMeans, BM3D) than using Fourier transforms.
I would stay away from it.

[richardpl]

Originally Posted by Cary Knoop

There are far better noise reduction methods (KNLMeans, BM3D) than using Fourier transforms.
I would stay away from it.

BM3D is also using FFT, not directly but use actually DCT.
So I fail to see what are you trying to tell us.

Convolution is usually done with FFT too.

[feisty2]

Originally Posted by richardpl

BM3D is also using FFT, not directly but use actually DCT.

not necessarily.
see: https://arxiv.org/pdf/1810.12575.pdf

[Sharc]

Originally Posted by Cary Knoop

There are far better noise reduction methods (KNLMeans, BM3D) than using Fourier transforms.
I would stay away from it.

It depends on the strength and type of "noise", I'd say.
dfttest (another FFT based filter) can perform better in some cases.