5 ms·

I'd love to be able to draw on the Fourier side. What's not neat is the rock-hard cliff cutoff, which leads to a ton of ringing on the image side.

tantalor 6y ago
Exactly. Editing the fourier side directly is really useful to remove periodic artifacts.
vanderZwan 6y ago
Looking at the page source they seem to be using the library from Project Nayuki[0]. I'm actually quite amazed at how few lines of code are required for an FFT implementation[1]. Anyway, I might give a simple draw-on-canvas website a go, give me a few hours. [0] https://www.nayuki.io/page/free-small-fft-in-multiple-languages https://www.nayuki.io/page/free-small-fft-in-multiple-langua... [1] https://www.nayuki.io/res/free-small-fft-in-multiple-languages/fft.js https://www.nayuki.io/res/free-small-fft-in-multiple-languag...
- tzs 6y ago
  If you don't need it in real time and don't have a whole lot of points, you can do discrete Fourier transforms in even less code by just doing FT instead of FFT. Modern computers are fast enough that the most straightforward O(n^2) algorithm that is immediately obvious from the definition of the discrete Fourier transform given in Wikipedia will often be fast enough. E.g., something like this in C: typedef struct { double r; double i; } complex; void fourier(complex * x, complex * y, int np) { int n, k; for (k = 0; k < np; ++k) { y[k].r = y[k].i = 0; for (n = 0; n < np; ++n) { double c = cos(2*M_PI*k*n/np); double s = sin(2*M_PI*k*n/np); y[k].r += x[n].r * c + x[n].i * s; y[k].i += -x[n].r * s + x[n].i * c; } } } 20 years ago, on a middle of the road desktop, that was fast enough that I was able to do an almost real time guitar tuner with it.
- content_sesh 6y ago
  I remember getting a very helpful tip as an undergrad Math major: once you start doing senior undergrad/early graduate level classes, expect each textbook page to take a long time to read. Upwards of an hour is not uncommon. And I found this to be very true in my own experience. I'm always struck by this thought when I see code like this. It's not a lot of code, but if I had to actually go through and internalize it, it would certainly take me a while.
  - vanderZwan 6y ago
    > It's not a lot of code, but if I had to actually go through and internalize it, it would certainly take me a while. Oh yeah, I definitely didn't mean to imply that it was easy code. It has that elegance that you really only see in the kind of concise code that can only be written by people who really grok the underlying system (both programming and FFT).
    - content_sesh 6y ago
      For sure. As Brooks might say, code like that is high in "essential complexity". There's almost no boilerplate - there's a nearly 1:1 ratio of lines of code to important idea.
- nayuki 6y ago
  This canvas activity also uses my FFT library. https://www.nayuki.io/page/gaussian-blur-demo https://www.nayuki.io/page/gaussian-blur-demo
montalbano 6y ago
I don't think this exactly what you want, but you might like it anyway. You draw and it breaks it down into the 2D fourier series, and you can control the number of fourier terms which essentially acts like a crude high pass filter: http://www.jezzamon.com/fourier/ http://www.jezzamon.com/fourier/
enriquto 6y ago
> I'd love to be able to draw on the Fourier side. Notice that the direct and inverse transforms are essentially the same transformation. So you can draw on the image side and swap both images on your mind.
- murgindrag 6y ago
  I don't want to draw an image. I want to draw a filter of an image. Right now, I have a rock-hard cutoff at two frequencies. I'd like to draw a curve, and have it Fourier filter based on that curve.
nyanpasu64 6y ago
You can't just "draw" on the Fourier side because it actually consists of complex numbers, and only the magnitude is plotted. And the Fourier plot needs to be rotationally symmetric. The closest you could get is increasing or decreasing the magnitude of pixel regions. Maybe a DCT would be more amenable to hand-editing because it's real and has no symmetry constraints.
- murgindrag 6y ago
  I should have a 2d line chart, and I should be able to draw magnitude at each frequency. It rotates and filters. Right now, a line chart consists of 1 between two frequencies, and 0 elsewhere. Or I should have a 2d image, and I draw dark/light. It reflects appropriately to get the other half, and multiplies the image (without rotating). Right now, this image looks like a donut. I'm drawing the filter, you see. It applies the filter, and shows me: * The source image FFT(what I drewFFT(image)) The point spread function / convolution kernel FFT(what I drew)

tantalor 6y ago

Exactly. Editing the fourier side directly is really useful to remove periodic artifacts.

vanderZwan 6y ago

Looking at the page source they seem to be using the library from Project Nayuki[0]. I'm actually quite amazed at how few lines of code are required for an FFT implementation[1]. Anyway, I might give a simple draw-on-canvas website a go, give me a few hours. [0] https://www.nayuki.io/page/free-small-fft-in-multiple-languages https://www.nayuki.io/page/free-small-fft-in-multiple-langua... [1] https://www.nayuki.io/res/free-small-fft-in-multiple-languages/fft.js https://www.nayuki.io/res/free-small-fft-in-multiple-languag...

tzs 6y ago
If you don't need it in real time and don't have a whole lot of points, you can do discrete Fourier transforms in even less code by just doing FT instead of FFT. Modern computers are fast enough that the most straightforward O(n^2) algorithm that is immediately obvious from the definition of the discrete Fourier transform given in Wikipedia will often be fast enough. E.g., something like this in C: typedef struct { double r; double i; } complex; void fourier(complex * x, complex * y, int np) { int n, k; for (k = 0; k < np; ++k) { y[k].r = y[k].i = 0; for (n = 0; n < np; ++n) { double c = cos(2*M_PI*k*n/np); double s = sin(2*M_PI*k*n/np); y[k].r += x[n].r * c + x[n].i * s; y[k].i += -x[n].r * s + x[n].i * c; } } } 20 years ago, on a middle of the road desktop, that was fast enough that I was able to do an almost real time guitar tuner with it.
content_sesh 6y ago
I remember getting a very helpful tip as an undergrad Math major: once you start doing senior undergrad/early graduate level classes, expect each textbook page to take a long time to read. Upwards of an hour is not uncommon. And I found this to be very true in my own experience. I'm always struck by this thought when I see code like this. It's not a lot of code, but if I had to actually go through and internalize it, it would certainly take me a while.
- vanderZwan 6y ago
  > It's not a lot of code, but if I had to actually go through and internalize it, it would certainly take me a while. Oh yeah, I definitely didn't mean to imply that it was easy code. It has that elegance that you really only see in the kind of concise code that can only be written by people who really grok the underlying system (both programming and FFT).
  - content_sesh 6y ago
    For sure. As Brooks might say, code like that is high in "essential complexity". There's almost no boilerplate - there's a nearly 1:1 ratio of lines of code to important idea.
nayuki 6y ago
This canvas activity also uses my FFT library. https://www.nayuki.io/page/gaussian-blur-demo https://www.nayuki.io/page/gaussian-blur-demo

montalbano 6y ago

I don't think this exactly what you want, but you might like it anyway. You draw and it breaks it down into the 2D fourier series, and you can control the number of fourier terms which essentially acts like a crude high pass filter: http://www.jezzamon.com/fourier/ http://www.jezzamon.com/fourier/

enriquto 6y ago

> I'd love to be able to draw on the Fourier side. Notice that the direct and inverse transforms are essentially the same transformation. So you can draw on the image side and swap both images on your mind.

murgindrag 6y ago
I don't want to draw an image. I want to draw a filter of an image. Right now, I have a rock-hard cutoff at two frequencies. I'd like to draw a curve, and have it Fourier filter based on that curve.

nyanpasu64 6y ago

You can't just "draw" on the Fourier side because it actually consists of complex numbers, and only the magnitude is plotted. And the Fourier plot needs to be rotationally symmetric. The closest you could get is increasing or decreasing the magnitude of pixel regions. Maybe a DCT would be more amenable to hand-editing because it's real and has no symmetry constraints.

murgindrag 6y ago
I should have a 2d line chart, and I should be able to draw magnitude at each frequency. It rotates and filters. Right now, a line chart consists of 1 between two frequencies, and 0 elsewhere. Or I should have a 2d image, and I draw dark/light. It reflects appropriately to get the other half, and multiplies the image (without rotating). Right now, this image looks like a donut. I'm drawing the filter, you see. It applies the filter, and shows me: * The source image FFT(what I drewFFT(image)) The point spread function / convolution kernel FFT(what I drew)