4 ms·

Experiments with plane-filling curves and Fourier transform

159 points by flockonus 3y ago

gus_massa 3y ago
Can you add some examples with different levels of recursion? It would be nice to see how the Fourier Transform changes when the level changes. Is there something interesting at the limit when the recursion level is close to infinity?
- mxmlnkn 3y ago
  Interesting question! You can try it out easily by varying the N parameter in the script. I uploaded the resulting images to the Readme in my fork: https://github.com/mxmlnkn/fft-image-experiments#scaling-the-recursion-depth https://github.com/mxmlnkn/fft-image-experiments#scaling-the... To summarize, the FFTs also have a recursive nature, which becomes more fine-granular with each recursion depth in the original. For example, this trippy FFT https://raw.githubusercontent.com/mxmlnkn/fft-image-experiments/master/media/fft-inverted-hilbert-pattern-order-13.png https://raw.githubusercontent.com/mxmlnkn/fft-image-experime... shows that the hierarchical square pattern probably repeats ad infinitum. Note that those details that get added with more recursion get lost when downscaling the images and the nearest-neighbor-upscaled images almost look like they are dithered: https://github.com/mxmlnkn/fft-image-experiments/raw/master/media/fft-inverted-hilbert-curve-order-8.png https://github.com/mxmlnkn/fft-image-experiments/raw/master/... It is interesting though that the Fourier transform has a recursive nature that is still visible when downscaling a larger image. When doing that for any of the space-filling curves you basically just get a gray image because they evenly fill the space. Well, the Dragon curve and the Gosper Diagram do have boundaries that are still visible even when downsampling large-resolutions versions: Hilbert Curve that simply looks gray when downsampled: https://raw.githubusercontent.com/mxmlnkn/fft-image-experiments/master/media/hilbert-pattern-order-13.png https://raw.githubusercontent.com/mxmlnkn/fft-image-experime... Dragon curve, which is gray but can be discerned from the background: https://raw.githubusercontent.com/mxmlnkn/fft-image-experiments/master/media/dragon-diagram-13.png https://raw.githubusercontent.com/mxmlnkn/fft-image-experime...
gregsadetsky 3y ago
Really great! Curious: what about the reverse - draw the plane filling curves in the Fourier domain and then run an inverse transformation? Edit: thanks for the reminder everyone, makes sense that the inverse would be roughly speaking “the same”! Cheers
- cperciva 3y ago
  Modulo sign, the forward and inverse Fourier transform are the same thing.
- jchallis 3y ago
  Should generate the same figures in the space domain up to constant factors of 2 pi.
- deleted 3y ago
  [deleted]
- pxndx 3y ago
  The Fourier transform is almost, but not quite it's own inverse when dealing with reals, so they'd be very similar to the results here.
drdeca 3y ago
Oh! This is applying FFT to the images! I thought it was going to be applying to functions f_n : [0,2pi] -> [0,1]^2 where f_n is the n-th level version of the curve. I guess in that view, higher order curves would have higher frequencies have higher amplitudes, on account of changing direction more often. I guess that view of things wouldn’t have much visual appeal, as it would just be associating to each integer frequency, an individual vector. (I guess a 2d complex-valued vector?) Hm, still, I think there would probably be uh, something to see in the directions of these vectors? And to handle the complex-valued stuff I would think that if you moved from the e^{i t n} basis to the cosines and sines basis, that one could maybe thereby do-away with that? Or... Well, yeah, that should be true, expressing a real valued periodic function as a weighted sum of sine and cosine functions doesn’t require any complex coefficients, but would doing so actually make the vectors which are the pairs of the coefficients for the two axiis, have a particularly clear meaning? I would imagine the direction of these vectors should correspond to something like the different directions the curves move in, or differences between these directions. Oh! One thing that might be nice visually, If you got the Fourier coefficients for the n-th level of the curve, and then took only the first k coefficients and constructed the curve associated with that, then that might be cool looking. I wonder, if you held k constant, but increased n, would the first k coefficients converge? If so, what would the curve from those first k coefficients look like?
- yarg 3y ago
  I've messed about with that sort of thing before: https://www.youtube.com/watch?v=pe4UAmb2wJw https://www.youtube.com/watch?v=pe4UAmb2wJw. I never got that far - I was primarily considering it as a point location definition for an image format, and I wanted a symmetrical curve. You can actually do that, if you relax the constraint that no grid point is shared (it's not really that big a problem, you just need to base the transform on the location between pixels, and not the centres of the pixels).
  - EntrePrescott 3y ago
    interesting. Here's another video where one sees how the precision of this Moore curve drawn with epicycles varies with the frequency range: https://old.reddit.com/r/woahdude/comments/6udj3e/moore_curve_drawn_with_epicycles/ https://old.reddit.com/r/woahdude/comments/6udj3e/moore_curv...
wizzwizz4 3y ago
I wonder what shape those squircles are?
- mxmlnkn 3y ago
  Might be related to p-norms although it doesn't really fit: https://raw.githubusercontent.com/mxmlnkn/fft-image-experiments/aff22cb6cd109d93fcf0b33bee1c122aee32ed02/media/fft-inverted-hilbert-pattern-order-13-p-norms.png https://raw.githubusercontent.com/mxmlnkn/fft-image-experime... Assuming it is a circle under a p-norm, I calculated p to be 3.504, so because of errors it might be exactly 3.5: https://raw.githubusercontent.com/mxmlnkn/fft-image-experiments/master/media/fft-inverted-hilbert-pattern-order-13-calculate-p.png https://raw.githubusercontent.com/mxmlnkn/fft-image-experime...
DesiLurker 3y ago
Hmm, I was thinking about building a 2d game solver with a LLM and I was wondering the other day if there is a better way to represent 2D data instead of just raster scanning it to a vector. probably a hadamard transform might work out better but the hilbert pattern looks interesting too.
- gus_massa 3y ago
  I'm not sure I understood your idea, but somewhat related (of the inverse representation of your idea?) https://xkcd.com/195/ https://xkcd.com/195/
  - DesiLurker 3y ago
    its basically trying to figure out the best way to represent 2D or 3D data to be vectorized and fed to a LLM for a puzzle game. I am rather new to the field so may not be using the right terminology. The idea is to create a bunch of these random game boards and generate various intermediate player states leading to a solution so the LLM can learn from it & then ask it to come up with steps to solve for a new board config. Its not a serious product, I am just trying to get my feet wet and understand how to use these transformers.
thewebcount 3y ago
The results of the Hilbert and Hilbert-like curves look similar to the Robinson’s aperiodic tiling of the plane[0]. In that picture they use squares and rounded squares, but if you did all rounded squares, I think it would look more similar. [0] https://en.wikipedia.org/wiki/Aperiodic_tiling https://en.wikipedia.org/wiki/Aperiodic_tiling
bawolff 3y ago
It is kind of striking how the images look like stars and galaxies
akomtu 3y ago
It's not plane-fillingness, but fractalness of the inputs that makes the DFTs look interesting. So I'd experiment with other L-space system curves. A fractal has some periodicity that appears as bright lines on DFT, and when you add an extra level of recursion, the original periodicity remains and it gets supplemented with its harmonics. I'd also try to interpret a diagonal scan of the DFT images as a sound waveform, probably scaled down to fit it into the audible range. There's also a related so-called Radon transform that would make the DFT images more roundish.
deleted 3y ago
[deleted]
totetsu 3y ago
Could these be used to make dithering patterns?

159 points by flockonus 3y ago

Can you add some examples with different levels of recursion? It would be nice to see how the Fourier Transform changes when the level changes. Is there something interesting at the limit when the recursion level is close to infinity?

mxmlnkn 3y ago
Interesting question! You can try it out easily by varying the N parameter in the script. I uploaded the resulting images to the Readme in my fork: https://github.com/mxmlnkn/fft-image-experiments#scaling-the-recursion-depth https://github.com/mxmlnkn/fft-image-experiments#scaling-the... To summarize, the FFTs also have a recursive nature, which becomes more fine-granular with each recursion depth in the original. For example, this trippy FFT https://raw.githubusercontent.com/mxmlnkn/fft-image-experiments/master/media/fft-inverted-hilbert-pattern-order-13.png https://raw.githubusercontent.com/mxmlnkn/fft-image-experime... shows that the hierarchical square pattern probably repeats ad infinitum. Note that those details that get added with more recursion get lost when downscaling the images and the nearest-neighbor-upscaled images almost look like they are dithered: https://github.com/mxmlnkn/fft-image-experiments/raw/master/media/fft-inverted-hilbert-curve-order-8.png https://github.com/mxmlnkn/fft-image-experiments/raw/master/... It is interesting though that the Fourier transform has a recursive nature that is still visible when downscaling a larger image. When doing that for any of the space-filling curves you basically just get a gray image because they evenly fill the space. Well, the Dragon curve and the Gosper Diagram do have boundaries that are still visible even when downsampling large-resolutions versions: Hilbert Curve that simply looks gray when downsampled: https://raw.githubusercontent.com/mxmlnkn/fft-image-experiments/master/media/hilbert-pattern-order-13.png https://raw.githubusercontent.com/mxmlnkn/fft-image-experime... Dragon curve, which is gray but can be discerned from the background: https://raw.githubusercontent.com/mxmlnkn/fft-image-experiments/master/media/dragon-diagram-13.png https://raw.githubusercontent.com/mxmlnkn/fft-image-experime...

gregsadetsky 3y ago

Really great! Curious: what about the reverse - draw the plane filling curves in the Fourier domain and then run an inverse transformation? Edit: thanks for the reminder everyone, makes sense that the inverse would be roughly speaking “the same”! Cheers

cperciva 3y ago
Modulo sign, the forward and inverse Fourier transform are the same thing.
jchallis 3y ago
Should generate the same figures in the space domain up to constant factors of 2 pi.
deleted 3y ago
[deleted]
pxndx 3y ago
The Fourier transform is almost, but not quite it's own inverse when dealing with reals, so they'd be very similar to the results here.

drdeca 3y ago

Oh! This is applying FFT to the images! I thought it was going to be applying to functions f_n : [0,2pi] -> [0,1]^2 where f_n is the n-th level version of the curve. I guess in that view, higher order curves would have higher frequencies have higher amplitudes, on account of changing direction more often. I guess that view of things wouldn’t have much visual appeal, as it would just be associating to each integer frequency, an individual vector. (I guess a 2d complex-valued vector?) Hm, still, I think there would probably be uh, something to see in the directions of these vectors? And to handle the complex-valued stuff I would think that if you moved from the e^{i t n} basis to the cosines and sines basis, that one could maybe thereby do-away with that? Or... Well, yeah, that should be true, expressing a real valued periodic function as a weighted sum of sine and cosine functions doesn’t require any complex coefficients, but would doing so actually make the vectors which are the pairs of the coefficients for the two axiis, have a particularly clear meaning? I would imagine the direction of these vectors should correspond to something like the different directions the curves move in, or differences between these directions. Oh! One thing that might be nice visually, If you got the Fourier coefficients for the n-th level of the curve, and then took only the first k coefficients and constructed the curve associated with that, then that might be cool looking. I wonder, if you held k constant, but increased n, would the first k coefficients converge? If so, what would the curve from those first k coefficients look like?

yarg 3y ago
I've messed about with that sort of thing before: https://www.youtube.com/watch?v=pe4UAmb2wJw https://www.youtube.com/watch?v=pe4UAmb2wJw. I never got that far - I was primarily considering it as a point location definition for an image format, and I wanted a symmetrical curve. You can actually do that, if you relax the constraint that no grid point is shared (it's not really that big a problem, you just need to base the transform on the location between pixels, and not the centres of the pixels).
- EntrePrescott 3y ago
  interesting. Here's another video where one sees how the precision of this Moore curve drawn with epicycles varies with the frequency range: https://old.reddit.com/r/woahdude/comments/6udj3e/moore_curve_drawn_with_epicycles/ https://old.reddit.com/r/woahdude/comments/6udj3e/moore_curv...

wizzwizz4 3y ago

I wonder what shape those squircles are?

mxmlnkn 3y ago
Might be related to p-norms although it doesn't really fit: https://raw.githubusercontent.com/mxmlnkn/fft-image-experiments/aff22cb6cd109d93fcf0b33bee1c122aee32ed02/media/fft-inverted-hilbert-pattern-order-13-p-norms.png https://raw.githubusercontent.com/mxmlnkn/fft-image-experime... Assuming it is a circle under a p-norm, I calculated p to be 3.504, so because of errors it might be exactly 3.5: https://raw.githubusercontent.com/mxmlnkn/fft-image-experiments/master/media/fft-inverted-hilbert-pattern-order-13-calculate-p.png https://raw.githubusercontent.com/mxmlnkn/fft-image-experime...

DesiLurker 3y ago

Hmm, I was thinking about building a 2d game solver with a LLM and I was wondering the other day if there is a better way to represent 2D data instead of just raster scanning it to a vector. probably a hadamard transform might work out better but the hilbert pattern looks interesting too.

gus_massa 3y ago
I'm not sure I understood your idea, but somewhat related (of the inverse representation of your idea?) https://xkcd.com/195/ https://xkcd.com/195/
- DesiLurker 3y ago
  its basically trying to figure out the best way to represent 2D or 3D data to be vectorized and fed to a LLM for a puzzle game. I am rather new to the field so may not be using the right terminology. The idea is to create a bunch of these random game boards and generate various intermediate player states leading to a solution so the LLM can learn from it & then ask it to come up with steps to solve for a new board config. Its not a serious product, I am just trying to get my feet wet and understand how to use these transformers.

thewebcount 3y ago

The results of the Hilbert and Hilbert-like curves look similar to the Robinson’s aperiodic tiling of the plane[0]. In that picture they use squares and rounded squares, but if you did all rounded squares, I think it would look more similar. [0] https://en.wikipedia.org/wiki/Aperiodic_tiling https://en.wikipedia.org/wiki/Aperiodic_tiling

bawolff 3y ago

It is kind of striking how the images look like stars and galaxies

akomtu 3y ago

It's not plane-fillingness, but fractalness of the inputs that makes the DFTs look interesting. So I'd experiment with other L-space system curves. A fractal has some periodicity that appears as bright lines on DFT, and when you add an extra level of recursion, the original periodicity remains and it gets supplemented with its harmonics. I'd also try to interpret a diagonal scan of the DFT images as a sound waveform, probably scaled down to fit it into the audible range. There's also a related so-called Radon transform that would make the DFT images more roundish.

deleted 3y ago

[deleted]

totetsu 3y ago

Could these be used to make dithering patterns?