How to flatten 2d matrix (n x n) into 1d array in order of Hilbert Curve?

Question

I want to flatten a 2d (n x n) matrix in python into a 1d array, but instead of row major order, I want it to follow the ordering of hilbert curve?

For example, if my input data is 2x2 -->

    data[[a b] [c d]] 

I want the output to be 1x4 -->

    [c, a, b, d]

but I want to do this with an image of say size 256 x 256

Another example is given data

    [[12 15  5  0]
     [ 3 11  3  7]
     [ 9  3  5  2]
     [ 4  7  6  8]]

I want the output to be

    [ 4  7  3  9  3 12 15 11  3  5  0  7  2  5  6  8]

What is the best way to do this in python?

Answer 1

I suggest you to use hilbertcurve library.

pip install hilbertcurve
or
conda install hilbertcurve 

First of all your matrix size must be 2^n. If you want to transform 4x4 matrix (size=16) you need to specify your number of dimensions(N) and number of iterations used in constructing the Hilbert curve(p)

from hilbertcurve.hilbertcurve import HilbertCurve
import numpy as np

X = np.array(
    [[12, 15,  5,  0],
     [ 3, 11,  3,  7],
     [ 9,  3,  5,  2],
     [ 4,  7,  6,  8]])

p = 3
N = 2
hilbert_curve = HilbertCurve(p, N)

# compute indexes for 2D -> 1D transform
indexes = np.zeros((4*4,N), dtype='int')
for i in range(4*4):
    coords = hilbert_curve.coordinates_from_distance(i)
    indexes[i,:] = coords

# transform 
vector = [X[x,y] for x,y in indexes]

And you get your result

[12, 3, 11, 15, 5, 0, 7, 3, 5, 2, 8, 6, 7, 3, 9, 4]

And your curve look like this:
Hilbert cureve
you can play with p value to get different curves, but I think you get the idea.

Answer 2

You can use the package numpy-hilbert-curve. For example:

import numpy as np
from hilbert import decode


def hilbert_flatten(array):
    D = array.ndim
    S = np.arange(np.array(array.shape).prod())
    L = decode(S, D, 8).T.tolist()

    return array[tuple(L)]


if __name__ == '__main__':
    a = np.array([[12, 15, 5, 0],
                  [3, 11, 3, 7],
                  [9, 3, 5, 2],
                  [4, 7, 6, 8]])

    print(hilbert_flatten(a))

will have the output: [12 3 11 15 5 0 7 3 5 2 8 6 7 3 9 4]

This may not be the fastest method (but the fastest and and easiest I found), and the advantage is that it also works with n-dimensional numpy arrays of (almost) any size.