Friday, December 4, 2009

Hilbert curve and fourier transform

Hilbert curve is a fractal curve of Hausdorf dimension 2 that fills the interior of a square. It provides continuous mapping from real interval [0;1] to unit square. This mapping is not invertible: some different points of [0;1] are mapped to the same points of the unit square.

Let us assign a color to each point of the unit interval, in simple repeating manner, and map the colored points to the square. This procedure will produce a monotonous flat pattern, which is not actually periodic.

Hilbert curve, 5th approximation (image from the Wikipedia)

Not an exciting sight. However 2D Fourier transform of this pattern reveals amazingly complex fractal structure:

Fourer transform of the Hilbert curve pattern
2D Fourier transform of the above image.

The picture above shows filtered (invert, despeckle and colorization filters were used) and scaled version of the transformed pattern. Apparently, it contains multiple images of some "rounded rectangle" shape. This shape always appears in the Fourier transform of the every repetitive Hilbert curve pattern. What is the equation of this shape? I don't know.