Fourier Image Filtering
david.li
david.li
Image filtering is a popular subject these days thanks partly to Instagram, and this subject is on the boundary between art and science, which is nice for a change of pace sometimes.
Anyway, to master image filtering in photoshop/GIMP for example requires learning a (very) large number of words and concepts which seemingly have no organizational structure. These words/concepts exist for historical reasons, and not because they represent some sort of cohesive or unified approach to filtering in general. The exact same problem exists for simulating effects pedals for guitars in programs like Pro Tools, interestingly.
Only Fourier methods can possibly unify this type of filtering, for a number of reasons which are actually obvious to anyone who is familiar with the fundamental role played by these methods in analysis.
The problem seems to be that the people who actually use this stuff all the time do not know Fourier methods and are not in a position to learn it; and this has created a massive inertia against re-formulating the entire UI/UX for image filtering based on the only possible unified approach.
It might be thought that Fourier methods are too hard for a graphic designer to understand, but I believe that it is up to people like us who do understand these things to redo the entire approach to filtering from square one, based on Fourier methods. In fact, I believe such an approach will make this subject much more accessible to everyone, and will be significantly easier for power users as well.
I find this argument funny in general. Just look at sound engineers working with the mixboard and their equalizers. Equalizer basically allows you to do the same as what is done in that webpage. And yet the persons using it won't necessarily even know what the term "Fourier transform" means.
An useful UI so artists can play with it is probably the only thing needed for this.
I actually recently went to a studio and worked with a professional sound engineer. Most of the time, he would right click on a track, and then select from a list of filters to apply to some segment. These filters have a GUI that looks like an effects pedal with knobs etc... Having used many of these programs myself, I can assure you virtually nothing is based on fourier methods, even though this is all that these effects pedals are doing, often with large amounts of redundancy.
A curious fact is that a large majority of the popular types of effects pedals actually correspond to the most well studied convolutions, which is something I hope and plan to research more carefully and write up in a blog post one day soon.
Effects pedals for guitars were originally circuits discovered basically by chance; and it was only much later that these things were made digital. This clearly demonstrates the problem I was talking about when I said there is a "massive inertia against re-formulating the entire UI/UX for ... filtering based on the only possible unified approach"
This is what's going on with the presets at the bottom of the article.. for example, if you took the gaussian blur filter and converted it to image space, you'd have a gaussian blur convolution kernel.
Can I ask where people learn this stuff? Programming computers is pretty easy to learn by yourself, but the more I look at technical subjects other than programming computers, the less I can understand how it's possible to learn that stuff other than someone showing you.
Naturally no-one learns anything in isolation. So bunch of reading is needed regardless of what you do.
Most of the terms are just fancy / specific ways of saying simple things. There are a few key concepts to learn, and then the rest is implementation and learning the vocabulary so you can discuss it unambiguously.
Yehar's DSP Tutorial for the Braindead http://yehar.com/blog/?p=121
It skips over some of the more fundamental math, but it serves as a great introduction to general ideas of digital signal processing. You can then proceed to look up the fiddly bits and deeper theory in more detail as you see fit (start from Wikipedia, hit the external links--that's how I'd do it).
This particular tutorial speaks mainly about digital audio signal processing, which is the 1D case, but it generalizes to 2D image processing just as easily, if you've got the imagination (although you need some tricks if you don't want an IIR filter to look weird on an image).
And in sound engineering the length of the signal is generally far longer than the length of the convolution filter. Thus it's far better to use convolution to calculate it (it becomes advantageous to use Fourier only when the filter and the signal itself are of similar sizes).
However I do think that conceptually things need a big simplification.
Studio EQ is not the same as Fourier filtering. Canonical digital DSP filters are vastly more efficient than Fourier processing. Analog EQ circuits add significant amounts of distortion which add character to the sound. Some of the better digital EQs try to emulate this.
Studio effects, pedals included, do not actually correspond to convolution. Many commercial reverb algorithms use complex time-varying effects that can't be modelled with simple convolution. While you can buy convolution reverbs from a variety of sources - and they're very popular for certain reverb effects - they're a long way from being the whole story.
Bottom line is audio engineering is much more complex than you seem to think it is. Numerical techniques, including Fourier and convolution, have been studied since at least the 1950s, and there are good reasons why they're not a one-size-fits-all solution for audio effects.
The image filter, on the other hand, is a lovely piece of work. I'm surprised no one has made it available as a Photoshop plug-in (although I expect someone will soon.)
Would you be willing to explain in more detail the "good reasons why they're not a one-size-fits-all solution for audio effects"?
Also a lot of the processes we want to apply to audio have much more efficient methods available than FFT or convolution such as IIR filters - which also have no latency apart from whatever phase shift they introduce. Or if the process is time varying or has embedded non-linearities then it lends itself to sample-by-sample processing and not block based like FFT and (efficient) convolution.
The reverberation algorithms mentioned by TheOtherHobbes often bear no resemblance to the methods used for analog gear. The most commonly understood setup, in the first digital reverbs described by Manfred Schroeder [0], uses banks of all-pass delay lines set up in "aesthetically interesting" sequence and series, employing various levels of feedback.
Digital frequency filters (and I'm pretty unclear on all the details myself, not having enough DSP background) generally apply the Z-transform [1] to turn a filter specification into a fast state-variable algorithm. This technique is crucial to modelling certain aspects of analog audio since it allows the filter to behave in more chaotic, animated ways: for example, resonance in analog domain is achieved through filter feedback, which causes the filter to self-oscillate at high gain levels.
Resampling algorithms contain some of the most straightforward applications of Fourier transforms. The theory tells us to treat each sample of the original signal as a point convolved by the sinc function; the resulting output signal is resampled from this convolution, and is thus dependent on the _bandwidth_ of the convolution - as bandwidth goes up, our convolution grows wider, as it goes down, shorter. The bandwidth modulation guarantees that the output signal contains frequencies underneath the Nyquist limit.
However, in practical use, we immediately have to compromise by at least windowing the sinc; thus we get into various approximations to minimize artifacts. Resampling can become a distinctive effect when done with lower fidelity or unusual filter kernels(example: The SPU of the Super Nintendo employs a Gaussian kernel).
[0] http://valhalladsp.wordpress.com/2009/05/30/schroeder-reverb...
Hell, a lot of what is called 'filtering' in the instagram sense doesn't even touch frequency domain - they're global manipulation of color balance, contrast and levels.
There's certainly space for improvement - it would certainly be nice to expose the underlying frequency domain components when manipulating filters, but I really think that you've overstated the level of lack of cohesion in Photoshop terminology, especially as a case for major UI changes.
And certainly, anyone who -has- knowledge of Fourier methods will also understand that by its very nature, spatial formulations of filters are every bit as legitimate as frequency domain formulations. Which one you should use should be based on whatever is more convenient. A nice box/circle blur is certainly easier to reason about than its frequency domain counterpart.
You are wrong in this. The last 60 years of signal processing history involve developing methods that are improvements on the FT.
>>It might be thought that Fourier methods are too hard for a graphic designer to understand
Fourier methods are bad because they are the least efficient basis to represent your image. It is not intuitive to increase the gain of the low frequencies when you want to increase something like the shadow. There is no mapping between features in an object and the Fourier domain.
More advanced, spatial domain techniques might be appropriate and these already exist and are being used by graphics design professionals.
A nice explanation of using image FFTs is also given in the Image Magick docs:
Generally block transform techniques are not that interesting over a whole image because the signal isn't stationary.
But yes, the ringing is ugly— and while there might be some learned elements here, the images are not periodic, they're mixtures of regions with different statistics, and it's inappropriate to spill one to the other.
https://github.com/thearn/game-of-life
This advances the game state image through re-expression of the game rules as a convolution filter.
http://hypftier.de/temp/2014-09-01_182732.png
The FT part seems to work, though.
WebGL systems are actually very promising for a number of computationally intensive areas, such as medical imaging: http://www1.eafit.edu.co/cadcamcae/documents/non_final_paper...
Shoehorning algorithms to work as fragment shader produces a considerable performance and mental overhead compared to compute shaders.
Maybe we could use this to build a human powered custom compression algorithm since they work by discarding components which don't make much of a difference.
(before anyone nitpicks: yes JPEG uses DCT and blablabla, sorry)
It would cool to add a few images with periodicity. I expected the lake bed image to show some quasi-periodic lines, but couldn't make that out in the spectrum.
Just look at what happens when you use only the magnitude or only the phase information to reconstruct an image: http://www.imagemagick.org/Usage/fourier/
Great job tho!
The mathematics assumes the sample is of a (bandlimited) periodic signal, but so what? What is of interest here is the power spectrum of the sample.