A little bit about Hilbert space-filling curve

As a student I have investigated properties of different scanning algorithm to unwrap an N-dimensional array into one dimensional. One of the algorithms was  Hilbert space-filling algorithm. This algorithm can be applied to an array of any dimension and it is known as one of the unwrapping algorithms that preserves spatial relations between array's neighbors very well.

As an experiment I used 2D implementation of the Hilbert space-filling algorithm to unwrap a real world picture into a 1D array to compare it with the line by line scanning algorithm. The original picture has a size of 512x512:

Scanning this picture line by line and then looking at the spectrum of the resulting 1D array one can clearly see energy pulses exactly at the distance of 512 points. These energy pulses arise there where previous line is attached to the next one:

Using Hilbert space-filling algorithm instead on the same picture resulted in:

Firstly the signal energy is distributed over shorted frequency range. Secondly there are no energy pulses as before which means that pixels locality is much better preserved.

Next I removed 99% of all spectral coefficients from 1D array and restored the picture using only 1% of remaining coefficients. In case of line by line scanning the following picture was restored:

Repeating the same procedure with the 1D array unwrapped by Hilbert space-filling algorithm resulted in:

Which means that using different scanning algorithms one can also achieve different compression ratios.

Hilbert space-filling curve in 3D

 

I've also written an implementation to unwrap 3D arrays. For many years this implementation existed as an OpenGL executable on my computer only but I decided to reimplement it using WebGL and put it online. To run the code a browser that supports WebGL is required. Note: it could happen that not the whole cube is shown for higher iterations. This is some kind of a WebGL restriction which is still experimental at the moment.One can rotate the cube with the left mouse button and scale it using scrolling wheel. And here is the page with the 3D implementation. Another implementation also includes 2D representation but it requires QT Creator to compile the application.

Edit 1:

I've found this variant of the Peano curve in the Hans Sagan's Space-Filling Curves.

Most probably this curve is forbidden in Germany : )