Monday, August 3, 2020

Fourier-Mellin Fractals

The Fourier-Mellin Transform (FMT) seems to be fundamental in encoding 2D fractals.

Here are example kernels of which the FMT composes all shapes:

Notice that these are standard Fourier transformation planar waves, but in log-polar space. Also notice that these are basic components of shapes with single scale symmetry (an image that is invariant to a single similarity transformation), you can build any sort of scale-symmetric spiral from summing these.

If we take a 2D image I:
and get its Fourier transformation F(I) then all shapes in any location will produce the same abs(F(I)):   (zoom in on centre to see):
Now, if we take the log of this log(abs(F(I))) (as though it were on a complex plane), i.e. convert to log polar coordinates: (horiz = angle, vertical = log radius from bottom to top)
The result is vertically periodic only if it is a broad class of scale-symmetric shape. (Above we see the lines getting softer towards the bottom, that is just because there aren't enough pixels close to the abs(F(I)) centre to represent the low spatial frequencies of the red squares shape. The precise result would be periodic).

The height offset of the vertical translation symmetry represents the scale involved in the fractal. In this case it is scale=2.

Next, we take the Fourier transformation of this, and get its absolute, to give the Fourier Mellin Transformation: FMT = abs(F(log(abs(F(I))))):
This gives an encoding of the shape that is now invariant to rotations and scalings.

Let's do it again, this time with a Menger sponge...
                      I                                      abs(F(I))                       log(abs(F(I)))      
                                               FMT = abs(F(log(abs(F(I)))))
and with the 2D Cantor set:
                                   I                                                 FMT(I)
As you can see, the Fourier-Mellin transformation is different to the squares examples. The intermediate images are hard to see, so you'll need to zoom in or brighten them to see better.

Now, this FMT is invariant to translation, rotation and scale. To illustrate, here is the FMT calculated for the Viscek fractal at two different scales and rotations:

Not only does the FMT represent the shape independent of its translation, rotation and scale, but for a large class of fractals, they can represent their infinitely detailed structure.

This is the class of fractal sets S of the form S=X u Ui(TiS)  where X is a set, U is union and Ti are a set of transformations whose scale are mutually rational, and whose rotations are rational multiples of 2PI. The class includes most simple fractals, including the ones above.

For such fractals, the log(abs(F(I))) image is vertically periodic (and horizontally periodic as it represents angle), this means its abs(FFT()) (the FMT of I) fully captures the entire shape.

However, we still need to quantise this FMT to some finite resolution, but the important thing here is that a finite resolution of the FMT does not inverse transform into a finite resolution image, instead the inverse FMT generates an unbounded fractal, with infinite detail as you zoom in to the centre. Further from the centre gets more blurry (faster if the FMT is lower res), but you can move the fractal so any different parts can go under the detailed centre. So there is access to the whole fractal in high detail, you just have a foviated view of it.