FranceBB
13th February 2020, 09:54
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:
https://wikimedia.org/api/rest_v1/media/math/render/svg/b49caba366b94ee1ecb91eee31d5a709f8b0beaa
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
https://wikimedia.org/api/rest_v1/media/math/render/svg/1164c32cf67b07a5a4fa30b4998b54d34e5cb646
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:
https://wikimedia.org/api/rest_v1/media/math/render/svg/97ad0938a279c4846d42a4bbd212f6a1f0ca4c0f
it has all the properties of the Laplace Transform but it's easy to invert:
https://wikimedia.org/api/rest_v1/media/math/render/svg/0d2aab0c0d32f0438d2ccf5bf779458053ba2bd9
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 (http://www.fftw.org/) 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". :)
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:
https://wikimedia.org/api/rest_v1/media/math/render/svg/b49caba366b94ee1ecb91eee31d5a709f8b0beaa
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
https://wikimedia.org/api/rest_v1/media/math/render/svg/1164c32cf67b07a5a4fa30b4998b54d34e5cb646
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:
https://wikimedia.org/api/rest_v1/media/math/render/svg/97ad0938a279c4846d42a4bbd212f6a1f0ca4c0f
it has all the properties of the Laplace Transform but it's easy to invert:
https://wikimedia.org/api/rest_v1/media/math/render/svg/0d2aab0c0d32f0438d2ccf5bf779458053ba2bd9
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 (http://www.fftw.org/) 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". :)