Hilbert-Peano curve to scan image of arbitrary size

Question

I have written an implementation of Hilbert-Peano space filling curve in Python (from a Matlab one) to flatten my 2D image:

def hilbert_peano(n):
    if n<=0:
        x=0
        y=0
    else:
        [x0, y0] = hilbert_peano(n-1)
        x = (1/2) * np.array([-0.5+y0, -0.5+x0, 0.5+x0, 0.5-y0])
        y = (1/2) * np.array([-0.5+x0, 0.5+y0, 0.5+y0, -0.5-y0])

    return x,y

However, the classical Hilbert-Peano curve only works for multi-dimensionnal array whose shape is a power of two (ex: 256*256 or 512*512 in case of a 2D array (image)).

Does anybody know how to extend this to an array of arbitrary size?

Answer 1

I finally choose, as suggested by Betterdev as adaptive curves are not that straigthforward [1], to compute a bigger curve and then get rid of coordinates which are outside my image shape:

# compute the needed order
order = np.max(np.ceil([np.log2(M), np.log2(N)]))
# Hilbert curve to scan a 2^order * 2^order image
x, y = hilbert_peano(order)
mat = np.zeros((2**order, 2**order))
# curve as a 2D array
mat[x, y] = np.arange(0, x.size, dtype=np.uint)
# clip the curve to the image shape
mat = mat[:M, :N]
# compute new indices (from 0 to M*N)
I = np.argsort(mat.flat)
x_new, y_new = np.meshgrid(np.arange(0, N, dtype=np.uint), np.arange(0, M, dtype=np.uint))
# apply the new order to the grid
x_new = x_new.flat[I]
y_new = y_new.flat[I]

[1] Zhang J., Kamata S. and Ueshige Y., "A Pseudo-Hilbert Scan Algorithm for Arbitrarily-Sized Rectangle Region"