14 ms·

Fourier Image Filtering

180 points by daviddotli 12y ago

gus_massa 12y ago
It's interesting, but a little slow in my slow machine. Does it use FFT or the "normal" FT?
- daviddotli 12y ago
  It uses an FFT implemented on the GPU via WebGL.
  - ygra 12y ago
    Interesting result on IE: http://hypftier.de/temp/2014-09-01_182732.png http://hypftier.de/temp/2014-09-01_182732.png The FT part seems to work, though.
- jbarrow 12y ago
  I imagine that even using the FFT and not the "normal" DFT, signals processing done in browser is slow for a lot of people.
  - angry_octet 12y ago
    Signal processing in javascript maybe, but webGL is a hardware accelerated native code module, so it can be fast. 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_Web3D_2011.pdf http://www1.eafit.edu.co/cadcamcae/documents/non_final_paper...
    - sharpneli 12y ago
      The current WebGL is just the beginning. Once we get a new one with compute shaders (basically WebGL based on ES 3.1 instead of 2.0) things are really going to pick up. Shoehorning algorithms to work as fragment shader produces a considerable performance and mental overhead compared to compute shaders.
claudius 12y ago
As it wasn’t immediately obvious to me: You can click on parts of the gain/frequency line to fix points and individually move points, causing the gain/frequency function to be not just constant but an interpolation through these points.
- daviddotli 12y ago
  Thanks for pointing this out. I added some brief instructions to the curve editor.
  - claudius 12y ago
    Excellent, thank you! :)
quarterwave 12y ago
Is 'frequency' 1d or 2d? Also, gain transfer function looks like a spline, why not try an FIR? 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.
- sharpneli 12y ago
  In images frequency is 2d. However in that page (and many other image processing applications) we only care about effectively what is 1d frequency (all the frequencies with the same euclidian distance from the center are binned as one).
- chestervonwinch 12y ago
  You've got directional frequencies in 2d - you'd measure it in the direction of some vector. With sinusoids, cos(wx+vy), the "natural" frequency is along the (w,v) direction. The 1D frequency along this direction is |(w,v)|^2. It's like how with the gradient, you have directional derivatives.
calhoun137 12y ago
This is very cool and impressive, really good job! 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.
- sharpneli 12y ago
  "It might be thought that Fourier methods are too hard for a graphic designer to understand" 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.
  - calhoun137 12y ago
    Since you used the example of sound engineer's, I would like to expand on the point I made in my previous comment about pro tools; and also clarify that I believe sound engineer's and graphic designers are a smart bunch, and are more than capable of handling it. 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"
angry_octet 12y ago
This is really cool. A nice explanation of using image FFTs is also given in the Image Magick docs: http://www.imagemagick.org/Usage/fourier/ http://www.imagemagick.org/Usage/fourier/
theoh 12y ago
If you have 3D data instead of 2D rasters, you can not only apply the same filtering techniques but also use the Fourier transform to do volume rendering! https://graphics.stanford.edu/papers/fourier/Levoy_GI92_VolumeRendering.pdf https://graphics.stanford.edu/papers/fourier/Levoy_GI92_Volu...
thearn4 12y ago
Partially related: Here is a Python implementation of Conway's Game Of Life, using numpy.fft https://github.com/thearn/game-of-life https://github.com/thearn/game-of-life This advances the game state image through re-expression of the game rules as a convolution filter.
starmole 12y ago
Somewhat small bug: The edges wrap around, which you certainly don't want for image filters. Especially noticeable with the blur. You want to use either clamping or mirroring at the edges.
- jjoonathan 12y ago
  DCT to the rescue!
TophWells 12y ago
The curve editor works very nicely. Did you write it yourself? I'm working on something similar, and it's really interesting to see all the things you did differently.
Fice 12y ago
Darktable has similar wavelet-based filter: http://www.darktable.org/2011/11/darktable-and-research/ http://www.darktable.org/2011/11/darktable-and-research/
mrcactu5 12y ago
why use Fourier analysis when it is not a repreating signal? I guess any function can be approximated using Fourier series, but it spreads information that is local and localalizes information that is spread out. I think a wavelet analysis would be more appropriate -- or at least separate the features and then use FFT. Great job tho!
- deleted 12y ago
  [deleted]
- retroencabulato 12y ago
  How often are frequency-domain tools actually used on perfectly periodic signals? 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.
Elizer0x0309 12y ago
This is awesome! I'm expecting an audio version, soon-ish :)
codehero 12y ago
Is there a similar way to play with the phase component?
- tboerstad 12y ago
  Came here to ask for the same thing. Considering phase is very important when designing filters, and just looking at the magnitude can overly simplify what happens. 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/ http://www.imagemagick.org/Usage/fourier/
nullc 12y ago
Has ugly cyclic artifacts, would probably look better with mirrored extension (where the image is padded with flipped mirrored copies of itself). E.g. lowpass and watch the sky bleed into the bottom. Generally block transform techniques are not that interesting over a whole image because the signal isn't stationary.
- fensterbrett 12y ago
  I wonder whether our agreement upon the ugliness of Fourier artifacts (such as ringing) stems from a learned distaste for low quality image and video compression.
  - nullc 12y ago
    Forget preferences about the ringing, it's actually spilling light from one side of the image to the other, as a result of failure to pad. 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.
gagzilla 12y ago
Strangely for me- neither Chrome nor Firefox seems to load this. Would be helpful if we knew what's missing to make this work.
thewarrior 12y ago
I notice that the low frequency components represent the large scale features of the image while the high frequency components seem to fill in the details. 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.
- darkmighty 12y ago
  http://en.wikipedia.org/wiki/Quantization_%28image_processing%29#Quantization_matrices http://en.wikipedia.org/wiki/Quantization_%28image_processin...
- tripzilch 12y ago
  You just (sort of/kind of) reinvented JPEG ;-) (before anyone nitpicks: yes JPEG uses DCT and blablabla, sorry)
bcheung 12y ago
Wow, so much more accessible than trying to do it with Photoshop. Is there code for this as a library anywhere?

180 points by daviddotli 12y ago

gus_massa 12y ago

It's interesting, but a little slow in my slow machine. Does it use FFT or the "normal" FT?

daviddotli 12y ago
It uses an FFT implemented on the GPU via WebGL.
- ygra 12y ago
  Interesting result on IE: http://hypftier.de/temp/2014-09-01_182732.png http://hypftier.de/temp/2014-09-01_182732.png The FT part seems to work, though.
jbarrow 12y ago
I imagine that even using the FFT and not the "normal" DFT, signals processing done in browser is slow for a lot of people.
- angry_octet 12y ago
  Signal processing in javascript maybe, but webGL is a hardware accelerated native code module, so it can be fast. 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_Web3D_2011.pdf http://www1.eafit.edu.co/cadcamcae/documents/non_final_paper...
  - sharpneli 12y ago
    The current WebGL is just the beginning. Once we get a new one with compute shaders (basically WebGL based on ES 3.1 instead of 2.0) things are really going to pick up. Shoehorning algorithms to work as fragment shader produces a considerable performance and mental overhead compared to compute shaders.

claudius 12y ago

As it wasn’t immediately obvious to me: You can click on parts of the gain/frequency line to fix points and individually move points, causing the gain/frequency function to be not just constant but an interpolation through these points.

daviddotli 12y ago
Thanks for pointing this out. I added some brief instructions to the curve editor.
- claudius 12y ago
  Excellent, thank you! :)

quarterwave 12y ago

Is 'frequency' 1d or 2d? Also, gain transfer function looks like a spline, why not try an FIR? 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.

sharpneli 12y ago
In images frequency is 2d. However in that page (and many other image processing applications) we only care about effectively what is 1d frequency (all the frequencies with the same euclidian distance from the center are binned as one).
chestervonwinch 12y ago
You've got directional frequencies in 2d - you'd measure it in the direction of some vector. With sinusoids, cos(wx+vy), the "natural" frequency is along the (w,v) direction. The 1D frequency along this direction is |(w,v)|^2. It's like how with the gradient, you have directional derivatives.

calhoun137 12y ago

This is very cool and impressive, really good job! 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.

sharpneli 12y ago
"It might be thought that Fourier methods are too hard for a graphic designer to understand" 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.
- calhoun137 12y ago
  Since you used the example of sound engineer's, I would like to expand on the point I made in my previous comment about pro tools; and also clarify that I believe sound engineer's and graphic designers are a smart bunch, and are more than capable of handling it. 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"

angry_octet 12y ago

This is really cool. A nice explanation of using image FFTs is also given in the Image Magick docs: http://www.imagemagick.org/Usage/fourier/ http://www.imagemagick.org/Usage/fourier/

theoh 12y ago

If you have 3D data instead of 2D rasters, you can not only apply the same filtering techniques but also use the Fourier transform to do volume rendering! https://graphics.stanford.edu/papers/fourier/Levoy_GI92_VolumeRendering.pdf https://graphics.stanford.edu/papers/fourier/Levoy_GI92_Volu...

thearn4 12y ago

Partially related: Here is a Python implementation of Conway's Game Of Life, using numpy.fft https://github.com/thearn/game-of-life https://github.com/thearn/game-of-life This advances the game state image through re-expression of the game rules as a convolution filter.

starmole 12y ago

Somewhat small bug: The edges wrap around, which you certainly don't want for image filters. Especially noticeable with the blur. You want to use either clamping or mirroring at the edges.

jjoonathan 12y ago
DCT to the rescue!

TophWells 12y ago

The curve editor works very nicely. Did you write it yourself? I'm working on something similar, and it's really interesting to see all the things you did differently.

Fice 12y ago

Darktable has similar wavelet-based filter: http://www.darktable.org/2011/11/darktable-and-research/ http://www.darktable.org/2011/11/darktable-and-research/

mrcactu5 12y ago

why use Fourier analysis when it is not a repreating signal? I guess any function can be approximated using Fourier series, but it spreads information that is local and localalizes information that is spread out. I think a wavelet analysis would be more appropriate -- or at least separate the features and then use FFT. Great job tho!

deleted 12y ago
[deleted]
retroencabulato 12y ago
How often are frequency-domain tools actually used on perfectly periodic signals? 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.

Elizer0x0309 12y ago

This is awesome! I'm expecting an audio version, soon-ish :)

codehero 12y ago

Is there a similar way to play with the phase component?

tboerstad 12y ago
Came here to ask for the same thing. Considering phase is very important when designing filters, and just looking at the magnitude can overly simplify what happens. 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/ http://www.imagemagick.org/Usage/fourier/

nullc 12y ago

Has ugly cyclic artifacts, would probably look better with mirrored extension (where the image is padded with flipped mirrored copies of itself). E.g. lowpass and watch the sky bleed into the bottom. Generally block transform techniques are not that interesting over a whole image because the signal isn't stationary.

fensterbrett 12y ago
I wonder whether our agreement upon the ugliness of Fourier artifacts (such as ringing) stems from a learned distaste for low quality image and video compression.
- nullc 12y ago
  Forget preferences about the ringing, it's actually spilling light from one side of the image to the other, as a result of failure to pad. 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.

gagzilla 12y ago

Strangely for me- neither Chrome nor Firefox seems to load this. Would be helpful if we knew what's missing to make this work.

thewarrior 12y ago

I notice that the low frequency components represent the large scale features of the image while the high frequency components seem to fill in the details. 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.

darkmighty 12y ago
http://en.wikipedia.org/wiki/Quantization_%28image_processing%29#Quantization_matrices http://en.wikipedia.org/wiki/Quantization_%28image_processin...
tripzilch 12y ago
You just (sort of/kind of) reinvented JPEG ;-) (before anyone nitpicks: yes JPEG uses DCT and blablabla, sorry)

bcheung 12y ago

Wow, so much more accessible than trying to do it with Photoshop. Is there code for this as a library anywhere?