How to implement an efficient arnold image scrambling algorithm?

user_17929907 0
Viewed 193

When I used python to do the arnold scrambling algorithm, I found that the running time of the for loop was not good enough, and the time reached more than 1 second. I wanted to use numpy to speed up, but I don't know how to start. The arnold algorithm mainly uses the pixel coordinates of the original image to do a mapping transformation to obtain new coordinates, and fills the pixel values into the new coordinates.

def arnold(img):
    r, c = img.shape
    pic = np.zeros((r, c), np.uint8)
    for i in range(r):
        for j in range(c):
            x = (i + j) % r
            y = (i + 2 * j) % c
            pic[x, y] = img[i, j]
    return pic
python
2 Answers

This should work:

def arnold(img):
    s = img.shape
    pic = np.zeros(s, np.uint8)
    A = np.array([[1, 1], [1, 2]])
    ind = A@np.indices(s).reshape(2, -1)%(np.array(s)[:, None])
    pic[ind[0], ind[1]] = img.reshape(-1)
    return pic

However, Arnold scambling in this form works only for square images. For other shapes it is in general not possible to recover the original image from the scrambled one.

user_151877280

Looping this way in python is not efficient. If you neeed better performance than the solution presented by @bb1, which only needs numpy, and if you can use other libraries, numba is a JIT compiler for python that can provide better performance. In this case, your original function (that is written with C-coding style) can be rendered efficient by just using the njit decorator.

import numpy as np
import time
from numba import njit

def arnold_numpy(img):
    s = img.shape
    pic = np.zeros(s, np.uint8)
    A = np.array([[1, 1], [1, 2]])
    ind = A@np.indices(s).reshape(2, -1) % (np.array(s)[:, None])
    pic[ind[0], ind[1]] = img.reshape(-1)
    return pic


@njit()
def arnold_numba(img):
    r, c = img.shape
    pic = np.zeros((r, c), np.uint8)
    for i in range(r):
        for j in range(c):
            x = (i + j) % r
            y = (i + 2 * j) % c
            pic[x, y] = img[i, j]
    return pic


if __name__ == "__main__":
    img = np.arange(10000 * 10000, dtype=np.uint8).reshape((10000, 10000))
    st = time.time()
    rv1 = arnold_numpy(img)
    print("With numpy", time.time() - st)

    _ = arnold_numba(img) # first-time run will compile and thus take a bit longer

    st = time.time()
    rv2 = arnold_numba(img)
    print("With numba", time.time() - st)

    print((rv1==rv2).all())

output:

With numpy 4.706800937652588
With numba 1.059769630432129
True
user_174570420
Related