[HN Gopher] Experiments with plane-filling curves and Fourier tr...
___________________________________________________________________
Experiments with plane-filling curves and Fourier transform
Author : flockonus
Score : 112 points
Date : 2023-04-16 14:43 UTC (8 hours ago)
(HTM) web link (github.com)
(TXT) w3m dump (github.com)
| wizzwizz4 wrote:
| I wonder what shape those squircles are?
| gregsadetsky wrote:
| 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 wrote:
| Modulo sign, the forward and inverse Fourier transform are the
| same thing.
| jchallis wrote:
| Should generate the same figures in the space domain up to
| constant factors of 2 pi.
| [deleted]
| pxndx wrote:
| 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.
| [deleted]
| DesiLurker wrote:
| 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 wrote:
| I'm not sure I understood your idea, but somewhat related (of
| the inverse representation of your idea?) https://xkcd.com/195/
| DesiLurker wrote:
| 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.
| gus_massa wrote:
| 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 wrote:
| 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...
|
| 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-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/...
|
| 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-experime...
|
| Dragon curve, which is gray but can be discerned from the
| background:
|
| https://raw.githubusercontent.com/mxmlnkn/fft-image-experime...
| thewebcount wrote:
| 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
| bawolff wrote:
| It is kind of striking how the images look like stars and
| galaxies
| akomtu wrote:
| 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.
| drdeca wrote:
| 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 wrote:
| I've messed about with that sort of thing before:
| 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 wrote:
| 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_curv.
| ..
| yarg wrote:
| He's using a different sample set than I did, I only used
| the centre pixel points, but (I believe) he has also
| included points in between.
|
| Hence his version retains the blockiness of the Moore
| curve, whereas mine does not.
___________________________________________________________________
(page generated 2023-04-16 23:00 UTC)