algorithmimage-processingrasterizinghilbert-curvespace-filling-curve

Hilbert-Peano curve to scan image of arbitrary size


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?


Solution

  • 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"